next up previous
Next: Performance Evaluation Up: Best Fit Algorithm for Previous: Best-Fit (BF) Algorithm

BF-delay and BF-delay-approx algorithms

Here we further introduce two variations of BF: BF-delay and BF-delay-approx. In BF-delay, network delay information is used to break the tie at step 3, i.e., when multiple nodes have paths to the incoming client $N$ with the same amount of bandwidth, the client closest to the requesting client is selected. BF-delay-approx uses a different bandwidth metric in step 2 and step 3. Instead of the actual available bandwidth $B(C,N)$, it uses $I(C,
N)$, where $I(C,
N)$ is 1 if client $C$ has enough bandwidth to support the incoming client $N$'s request, and 0 otherwise. The delay information is used to break the tie. Since BF-delay-approx only needs to test whether a client can admit the incoming client rather than measure the exact amount of available bandwidth as BF and BF-delay algorithm do, the measurement overhead of BF-delay-approx is lower than that of BF and BF-delay. Hence the joining delay in BF-delay-approx is expected to be small.

Yang Guo 2003-03-27