In the Best Fit algorithm, the requesting client starts the process by
contacting the server.
procedure is followed by the requesting client.
Step 1. The requesting client contacts a candidate
parent , starting with the server.
Step 2. estimates the bandwidth from to , . Meanwhile, it sends messages to all of its children in the
base tree, denoted as , asking them to measure their respective bandwidth
to the requesting client.
Step 3. collects the measured bandwidth from its children, and
identifies the child node that has the fattest pipe to , i.e.,
A tie is broken arbitrarily. Depending on the measurement reported
back to , there
follow two scenarios: (a) Candidate node has the fattest pipe
to the requesting node ,
and (b) one of the children has the fattest pipe to ,
We discuss in turn each of these scenarios.
has the fattest pipe to and is able to
support at least one stream. If only requires the base stream,
it can join the base tree using as its parent node.
If the patch is required, and arrives earlier than ,
then becomes 's
If both the base stream and the patch are required, the patch has the
priority over the base stream. If can serve the patch, it will
become 's patch server. If has sufficient leftover bandwidth to serve the
base stream, joins the base tree with as parent
If cannot fully
fulfill 's request,
is re-directed to ,
and starts from the step 1 again.
, then is re-directed to
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
clients report zero bandwidth,
the algorithm randomly selects one client to which is re-directed.
Next:BF-delay and BF-delay-approx algorithms Up:Best Fit Algorithm for Previous:Best Fit Algorithm for