Feedback Algorithm

  To conduct the distributed polling process, each receiver associates a weight with every active media source. Qualitatively, the weights define the relative priorities of each source with respect to a given receiver. These weights might be explicitly specified by the user, but more likely (and more naturally), they would be inferred through the user-interface (e.g., when the user manipulates the application to display a given source, the application would automatically instruct SCUBA to give maximum weight to that source).

Each receiver periodically advertises a source weight report, which is simply a vector of sources and their corresponding weights with respect to that receiver. Report intervals are dynamically sized to limit the control bandwidth to a fixed percentage of the session bandwidth. This scaling mechanism is employed by several announce/listen control protocols [18], including RTCP control traffic in RTP, Scalable Reliable Multicast (SRM) [7] session messages, and the Session Announcement Protocol (SAP) [9]. We analyze the scalability of the announce/listen metaphor with respect to SCUBA in Section 3.

As each receiver announces its source weight report by multicasting it to the session, each source listens for these reports, collects them up, and combines them into an aggregate metric, which we call the average source weight. Ideally, this metric would be the arithmetic mean across all reported values for that source, but in practice, we can only approximate the exact mean because maintaining a globally consistent view of every receiver's preference for every source would entail costly if not outright unrealistic overhead. Consequently, we approximate the average source weight as the mean of a sample of reported values taken from the last M reports received by the source. Let S₀,...,S_N-1 be the set of senders, and R₀,...,R_M-1 be the set of receivers. The average source weight for S_k, or w_k, is then computed as follows:

w_k = 1/M * SUM i=0 to M-1 (w_k,i/SUM j=0 to N-1 (w_j,i)) where M is the size of the sample of reporting receivers, w_k is the weight for source w_j,i reported by receiver S_j, and N is the number of sources weighted in each report.

To simplify the calculation and reduce the amount of state maintained at the source, we constrain the sum of weights in a report to be 1, i.e.,

SUM j=0 to N-1 (w_j,i) = 1 forall i Now the expression for w_k is simply: w_k = 1/M * SUM i=0 to M-1 (w_k,i)

To enhance SCUBA's robustness, we deliberately designed the protocol using only soft state [6]. Sources and receivers can join and leave the session at will without impacting other session members. None of the state maintained at any source alone is critical to the correct execution of the algorithm since all state eventually times out and is refreshed by receiver reports. Hence, failure recovery is built into the protocol; we need no further mechanism to handle network partitions, host failures, and so forth. Finally, SCUBA control messages are idempotent -- each message supersedes all previously sent messages -- further enhancing the protocol's scalability and its resilience to packet loss.

Not only is the SCUBA protocol robust and scalable, but it is also quite simple. The algorithm run at each source can be implemented in just a few lines of code. The following pseudo-code implements the weight calculation algorithm:

foreach src in active_source_list {
	w = 0
	foreach rcvr in sample_receiver_list {
		w = w + last_reported_weight(rcvr,src)
	}	
	avg_weights[src] = w/nsamples

	update_rate_controller(avg_weights)
}

The first stage here computes a weight for each reported source, including the local source. In the second stage, the rate controller is invoked to carry out the consequent action. While the method of computing the source weight is identical for both the flat and layered delivery models, the rate-control action in the second stage is not. In the following two subsections, we detail how the average source weight or weights are translated into the sender's rate-control decision in each of the two delivery models.