Best-Fit (BF) Algorithm

In the Best Fit algorithm, the requesting client starts the process by contacting the server. The following procedure is followed by the requesting client. $\bullet$ Step 1. The requesting client $N$ contacts a candidate parent $P$, starting with the server. $\bullet$ Step 2. $P$ estimates the bandwidth from $P$ to $N$, $B(P,N)$. Meanwhile, it sends messages to all of its children in the base tree, denoted as $C(P)$, asking them to measure their respective bandwidth to the requesting client. $\bullet$ Step 3. $P$ collects the measured bandwidth from its children, and identifies the child node $C_{max}$ that has the fattest pipe to $N$, i.e., $C_{max} = argmax_{C \in C(P)} \{ B(C, N) \}$. A tie is broken arbitrarily. Depending on the measurement reported back to $P$, there follow two scenarios: (a) Candidate node $P$ has the fattest pipe to the requesting node $N$, $B(P, N) > B(C_{max}, N)$; and (b) one of the children has the fattest pipe to $N$, $B(P, N) \leq B(C_{max}, N)$. We discuss in turn each of these scenarios. (1) If $B(P, N) > B(C_{max}, N)$, $P$ has the fattest pipe to $N$ and is able to support at least one stream. If $N$ only requires the base stream, it can join the base tree using $P$ as its parent node. If the patch is required, and $P$ arrives earlier than $N$, then $P$ becomes $N$'s patch server. If both the base stream and the patch are required, the patch has the priority over the base stream. If $P$ can serve the patch, it will become $N$'s patch server. If $P$ has sufficient leftover bandwidth to serve the base stream, $N$ joins the base tree with $P$ as parent node. If $P$ cannot fully fulfill $N$'s request, $N$ is re-directed to $C_{max}$, and starts from the step 1 again. (2) If $B(P, N) \leq B(C_{max}, N)$, then $N$ is re-directed to $C_{max}$, and starts from step 1. In step 3, if a client has out-degree constraint and would not support any more clients, it can return the available bandwidth of zero to its parent client without conducting bandwidth measurement. If all candidate parent clients report zero bandwidth, the algorithm randomly selects one client to which $N$ is re-directed.