Convergence Time

As control messages are received, each source incrementally calculates its average source weight and adapts accordingly. But because reports arrive only intermittently (not immediately upon a state change) and because the source uses a fixed sample of the receiver population, some amount of time passes before a (perhaps abrupt) change in receiver interest is reflected back to the sources. For example, the active ``speaker'' in a conferencing application might change and thus cause each receiver to shift its interest to the new source; only after some amount of time of monitoring SCUBA control messages do the active sources learn of the change in interest. We call this latency the average source weight convergence time (ASCT). More precisely, the ASCT is the expected time between a change in receiver interest and the point at which a source learns an accurate estimate of its average source weight within the session.

As described in Section 1, the aggregate set of source weights can be viewed as a ``consensus'' on the allocation of bandwidth to sources across the session. The ASCT -- i.e., the time to reach this consensus -- should be small. If too large, the computed source weight can become stale. The ``usability threshold'' is the point where fluctuations in average source weights occur faster than the sources can calculate them. In this case, the weights become invalid even before they have been established. Thus, given that the time-scale of fluctuations in receiver interests is determined by actual users, the average source weights must be computed on the time scale of seconds. In addition, we require that this time bound remain fixed as the number of receivers and/or sources increases.

To limit the report bandwidth and decouple it from the session size, we allocate a fixed share of the overall session bandwidth for this purpose. But to constrain the bandwidth in this fashion, each receiver's individual messaging rate must decrease in proportion to the session population. Consequently, the convergence time scales linearly with the number of receivers. Assume we have n receivers, and for simplicity assume a fixed report size S. Then, if B is the bandwidth of the control channel, the ASCT, t_conv, is given by t_conv = nS/B. This O(n) growth implies that in conferences with large numbers of receivers the ASCT will exceed the ``usability threshold.''

In order to combat the linear time growth of ASCT, we turn to sampling. Rather than relying upon a control message from every receiver to correctly compute receiver interest, we instead use a sample of receiver reports to determine the average source weight. Specifically, we construct a sample of size N from the last N reports received by the source. Our analysis below indicates that a source can compute its average weight within a small confidence interval with high probability using a relatively small number of receiver report samples. This means that a source can calculate its average source weight, within tight probabilistic bounds, in a relatively short amount of time, in particular, within the ``usability threshold.''

We now derive the number of sample receiver reports, N, that a source requires to calculate its average weight within error and confidence . is known as the confidence interval while is known as the confidence level where . More formally, we want to find the smallest N that satisfies:

P( | - | < ) >=

where is the distribution mean, i.e., the actual average source weight, and is the sample mean, i.e., = 1/N * SUM k=1 to N (X_k) where X_k is a random variable whose value is the weight for this source reported by the k'th sampled receiver report. Since the receivers generate reports from independently randomized timers, we can assume that X₁, X₂,... X_N are independent and identically distributed (when receiver interest is stationary).

A consequence of the Central Limit Theorem is that

where is the standard deviation of the weight distribution, and Z_p is the p-quantile of the unit normal variate [14]. Using this result, we can compute the number of samples required to establish the desired confidence level for a given confidence interval. Equation 1 shows that for given confidence bounds the number of samples is a linear function of the variance of the weight distribution which does not depend on the size of the sample space. This is a key result: we have decoupled the convergence time of the algorithm from the session size and thus SCUBA can scale to arbitrarily large sessions. Moreover, we can fine tune the accuracy of the sample mean by trading off convergence time -- larger sample sizes are more accurate but converge more slowly, while small sample sizes converge quickly by sacrificing accuracy.

(a) Number of samples vs. Confidence interval for .	(b) Number of samples vs. variance for = 0.07.

Figure 7: Number of SCUBA reports required to determine the average weight within given confidence bounds. The time values assume a control traffic bandwidth of 6.4 kb/s which is 5% of a 128 kb/s session bandwidth.

Figure 7(a) shows a plot of the number of samples required to determine the average weight versus the confidence interval, for the highest possible variance in a [0,1] distribution . which occurs in a strictly bimodal {0,1}-valued distribution. The plot shows a family of curves, each of which corresponds to a different confidence level, varying from 0.9 to 0.99. As a particular example, Figure 7(b) shows the number of samples required to determine the average weight for a confidence interval of 7%, i.e., = 0.07. Once again, each line in the figure shows the number of samples required for different confidence intervals ranging from 0.9 to 0.99.

To convert these values to an actual convergence time, we must assume an average report packet size. If we assume that each receiver source weight report is 6 bytes (4 bytes for the source id + 2 bytes for the weight) and constrain the number of sources per report to some number, say 5, then including the 28 byte UDP header and an 8 byte SCUBA header we get an average report size of 66 bytes.

  

Figure 8: Time to accumulate N samples vs. Control traffic bandwidth

The right-hand y-axes in Figures 7(a) and (b) show the the amount of time needed to accumulate the corresponding number of samples assuming a session bandwidth of 128 kb/s with 5% of this bandwidth allocated to the SCUBA control traffic.

We see that for given confidence bounds the amount of time required by a source to calculate its average weight varies widely depending on several factors, most significantly the variance of the weight distribution and amount of control traffic. In the figures we assumed a relatively conservative session bandwidth and within it a relatively conservative allocation to report messages. Increasing the control traffic bandwidth leads to a corresponding linear decrease in the convergence time. We illustrate this dependency in Figure 8 which shows a plot of the amount of time needed to accumulate N samples vs. control bandwidth for various values of N. The horizontal line marks a somewhat arbitrary ``usability threshold'' (10 seconds) that we would like to achieve. Thus, according to the desired confidence bounds, we must choose an appropriate control bandwidth. Comparing these results to Figures 7(a) and (b) we see that allocating 20-25 kb/s to control traffic suffices for very tight confidence bounds on the average weight convergence within the 10 second threshold.

These results imply that it is advantageous to modulate the control bandwidth based on event changes to speed up convergence and then slow down the report announcements when the system is idle. For example, a receiver could increase the control bandwidth for 15 seconds after it changes its source weight report allowing this information to be more quickly assimilated by the sources, thereby lowering the convergence time while maintaining an acceptable level of control traffic.

An alternative interpretation of this bandwidth/delay tradeoff is that the delay represents the width of a moving average filter applied to the incoming samples that is required to achieve the desired confidence bounds. In this interpretation, the window size represents a design tradeoff. As the above analysis has shown, setting the window too small reduces our confidence bounds. On the other hand too large a window causes samples to become widely separated in time decreasing the accuracy of the source weight estimation.

In summary, our analysis shows that the use of report sampling combats the linear growth of the ASCT. The set of feasible confidence bounds that conform to our ``usability threshold'' of 10 seconds are independent of the session size but are directly dependent on the amount of control traffic that is allocated to the SCUBA reports. Fortunately, we found that very tight confidence bounds are attained with only 20-25kb/s of control traffic. While this level of control traffic is acceptable in some environments, it is unrealistic for environments like the current MBone where the entire session bandwidth often comprises only 128 kb/s. A more reasonable control bandwidth would be 5 kb/s or so, and in this case, SCUBA is limited to session sizes on the order of 200 to 250 receivers, which in practice, accounts for almost all of the current MBone content. But to scale beyond this, we must resort to an alternative mechanism. Section 5 describes one promising scheme, currently under development, that utilizes hierarchy to enhance SCUBA's scalability.