NCA Use Cases : Estimation of Suppression Timer and Retransmission Timer Values --------------------------------------------------- 2000-05-02 Version: 1.1 In order to facilitate operation of the AER protocol, network-adaptive values for the NAK suppression timer and the NAK retransmission timer are needed. Upon assessment of the behavioral characteristics of AER, the following heuristics seem reasonable: * The suppression timer should be set to some scalar value times the maximum round-trip time between the nearest upstream repair server and members of the NAK originator's peer group. Members of the peer group are identically clients and repair servers that are directly supplied by the originator's upstream repair server (i.e., there are no intervening repair servers between the originator's repair server and any of the members of the originator's peer group) * The retransmission timer should be set to some scalar value times the round trip time from the originator of the NAK to the sender. The above settings directly reflect AER's NAK suppression strategy. Whenever an entity capable of generating a NAK detects a packet loss, the entity first waits for some period of time before transmitting a NAK. During this interval, the entity listens on the multicast channel for repairs or NAKs of the missing packet. If neither a repair nor a NAK for the missing packet arrives during the suppression interval, the NAK processing thread then sends a NAK upstream and subsequently sets and awaits the expiration of a retransmission timer. Alternately, if a repair arrives during the suppression interval, the NAK processing thread simply terminates. Finally, if a NAK arrives during the suppression interval, then the NAK processing thread terminates the suppression timer and subsequently sets and awaits the expiration of a retransmission timer. Repair operations following the initiation of a retransmission timer are straightforward. If no repair arrives during the retransmission interval, then the NAK processing thread assumes that the repair was dropped and begins the NAK processing thread from the top: i.e., a NAK suppression timer is set and the thread begins listening for NAKs or repairs for the missing packet. Nominally, each entity (receiver or repair server) picks a random number uniformly distributed between 0 and 1 as a scalar multiplier on a suppression timer maximum value. The hope is that some of the entities will wait very little time to issue NAKs, while others wait longer periods to see if others have issued NAKs. Assuming that one of the entities issues a NAK immediately, then the minimum time required before the NAK can be observed by a peer is the sum of: the transit time between the NAK originator and the repair server; the queueing delays within the repair server; and the transit time from the repair server to the peer. In the worst case, the entity choosing the smallest uniform random variable value has the longest transit time to the repair server, and its peer has a nearly identical transit time; for this case the minimum observation time is asymptotically the round trip time from the furthest entity to the repair server. Hence we set the suppression timer maximum value to some constant (e.g., 1.5) times the estimated maximum round trip time for the peer group. For establishing the retransmission timer, we assume that in the worst case the repair request must propagate all the way back to the sender in order to be serviced. Hence, we set the retransmission timer for each entity to some constant (e.g., 1.75) times the estimated round trip time between it and the sender. The following discussion describes the mechanism used for estimating the maximum round trip time for the peer group and the round trip time between an entity (repair server or receiver) and the sender. The mechanism is embodied in the Get-RTT algorithm described below. Description of the Get-RTT Algorithm 1. High-level description Both the maximum round trip time for a peer group and the round trip time to the sender are determined via the Get-RTT algorithm. The algorithm functions via request-response messages exchanged between subscribers (receivers or repair servers) and their nearest upstream providers (repair servers or the sender). The Get-RTT request message has the format: -------------------- | xmitTime | upRTT | -------------------- and the Get-RTT response message has the format: --------------------------------------- | xmitTime | peerGroupRTT | globalRTT | --------------------------------------- 2. State variable definitions and initial settings Algorithm Parameters: implosionSuppressionInterval The maximum amount of time that a receiver or repair server should wait before starting the first Get-RTT sequence. Nominal value: 30 milliseconds initialGetRTTCycleTime The initial amount of time that a receiver or repair server should wait before starting the next Get-RTT sequence. Nominal value: 200 milliseconds maxGetRTTCycleTime The maximum amount of time that a receiver or repair server should wait before starting the next Get-RTT sequence. Nominal value: 3 seconds updateWindowLength The maximum amount of time that the sender or a repair server should wait before updating its estimate of the maximum round trip time for its downstream peer group. Nominal value: maxGetRTTCycleTime + 0.5 seconds Sender: Peer Group RTT Variables: maxDownRTTSetTime Time that maxDownRTT was last updated. Initialized to the currentTime in milliseconds. maxDownRTT Value currently being used as the largest RTT received from a directly supplied downstream receiver or repair server. Initialized to -1. maxRecentDownRTT Largest RTT received from a directly supplied downstream receiver or repair server since maxDownRTT was last set. Initialized to 0. Sender RTT Variables: sourceRTT: RTT to the sender. Always 0. Repair servers: Common Variables: resendInterval Time between successive Get-RTT requests. Initialized to the value of initialGetRTTCycleTime. Peer Group RTT Variables: maxDownRTTSetTime Time that maxDownRTT was last updated. Initialized to the currentTime in milliseconds. maxDownRTT Value currently being used as the largest RTT received from a directly supplied downstream receiver or repair server. Initialized to -1. maxRecentDownRTT Largest RTT received from a directly supplied downstream receiver or repair server since maxDownRTT was last set. Initialized to 0. maxUpRTT Largest RTT observed by the nearest upstream repair server (or sender). Value is used to derive the suppression timer value. Initialized to -1. myUpRTT RTT observed to the nearest upstream repair server (or sender). Initialized to -1. Sender RTT Variables: sourceRTT RTT to the sender. Value is used to derive the retransmit timer value. Initialized to -1. Receivers: Common Variables: resendInterval Time between successive Get-RTT requests. Initialized to the value of initialGetRTTCycleTime. Peer Group RTT Variables: maxUpRTT Largest RTT observed by the nearest upstream repair server (or sender). Value is used to derive the suppression timer value. Initialized to -1. myUpRTT RTT observed to the nearest upstream repair server (or sender). Initialized to -1. Sender RTT Variables: sourceRTT RTT to the sender. Value is used to derive the retransmit timer value. Initialized to -1. 3. Estimation Processing Sequence The maximum peer group RTT value is the maximum RTT between a repair server (or the sender) and the next downstream level of repair servers or receivers. The source RTT is the round trip time between the sender and an repair server or receiver. 1) (Initialization: this step is not repeated) Upon receipt of the first SPM packet, each receiver or repair server sets a Get-RTT resend timer to a value that is the product of implosionSuppressionInterval and a random number that is uniformly distrbuted between 0 and 1. 2) Upon expiration of the Get-RTT resend timer, the Get-RTT resend timer is reset using the current value of resendInterval and the process continues at step 3). 3) The receiver or repair server sends a Get-RTT request to the nearest upstream repair server (or sender if it is the first repair server). The host's current time in milliseconds is inserted into the message as the value for xmitTime, and the hosts's current value for myUpRTT is inserted into the message as the value for UpRTT. 4) Upon receipt of a Get-RTT request the upstream repair server (or sender) compares the upRTT in the message with the local value of maxDownRTT. If the value of upRTT is greater than the current value of maxDownRTT, then it sets maxDownRTT to the value of upRTT, the value of maxDownRTTSetTime is set to the current time in milliseconds, and the value of maxRecentDownRTT is set to 0. If the value of upRTT is not greater than maxDownRTT, then a check is made to see if upRTT is greater than maxRecentDownRTT; if it is, the value of maxRecentDownRTT is set to the value of upRTT; i.e., if (upRTT > maxDownRTT) { maxDownRTT = upRTT maxDownRTTSetTime = currentTime in milliseconds maxRecentDownRTT = 0 } else { if (upRTT > maxRecentDownRTT) { maxRecentDownRTT = upRTT } } A check is then made to determine if maxDownRTT should be updated to the value of maxRecentRTT by comparing the update time against the current time in milliseconds. if (currentTime > (maxDownRTTSetTime + updateWindowLength)) { maxDownRTT = maxRecentDownRTT maxDownRTTSetTime = currentTime in milliseconds maxRecentDownRTT = 0 } The repair server (or sender) then sends a Get-RTT response message. The value of xmitTime in the response is set to the value of xmitTime contained in the request. The value of peerGroupRTT in the response is set to the local value of maxDownRTT. The value of globalRTT in the response is set to the local value of sourceRTT. 5) Upon receipt of Get-RTT response message, the repair server or receiver computes the local round trip time as myUpRTT = (currentTime - xmitTime) If the value of maxUpRTT is equal to -1 OR the value of peerGroupRTT is equal to -1, it then: cancels the current Get-RTT resend timer; sets the local value of resendInterval equal to myUpRTT; rearms the Get-RTT timer with the value of resendInterval; and immediately sends another Get-RTT request. The value of resendInterval is then doubled and limited, if necessary, to a maximum value given by maxGetRTTCycleTime. The value for maxUpRTT is either set to the value of peerGroupRTT from the message or the new value of myUpRTT, whichever is greater: i.e., if (myUpRTT > peerGroupRTT) { maxUpRTT = myUpRTT } else { maxUpRTT = peerGroupRTT } If the value of globalRTT in the response message is nonnegative, the receiver or repair server then computes and sets the value of sourceRTT as the sum of the value of globalRTT and the value of myUpRTT; i.e., if (globalRTT >= 0) { sourceRTT = (globalRTT + myUpRTT) } 4. Use Cases R.1 Initialization This use case begins when Get-RTT is initialized. The variables are initialized as follows: Sender: maxDownRTTSetTime = currentTime in milliseconds maxDownRTT = -1 maxRecentDownRTT = 0 sourceRTT = 0 Repair Server: maxDownRTTSetTime = currentTime in milliseconds maxDownRTT = -1 maxRecentDownRTT = 0 maxUpRTT = -1 myUpRTT = -1 sourceRTT = -1 resendInterval = initialGetRTTCycleTime Receiver: maxUpRTT = -1 myUpRTT = -1 sourceRTT = -1 resendInterval = initialGetRTTCycleTime This use case ends when the variables have been initialized. R.2 Processing the First Received SPM Packet This use case begins when the first SPM packet is received at a receiver or repair server. The following processing is performed: Start the Get-RTT resend timer with a duration of a random variate, uniformly distributed between 0 and 1.0, times implosionSuppressionInterval This use case ends when the Get-RTT resend timer has been set. R.3 Get-RTT Resend Timer Service Routine This use case begins when the Get-RTT resend timer expires at a receiver or repair server. The following processing is performed: Unicast a Get-RTT request packet to the nearest upstream repair server (xmitTime = currentTime, upRTT = myUpRTT) Start the Get-RTT resend timer with a duration of resendInterval This use case ends when the Get-RTT request packet has been sent. R.4 Processing a Received Get-RTT Request Packet This use case begins when a Get-RTT request packet is received at a repair server or sender. The following processing is performed (xmitTime and upRTT are Get-RTT request packet fields): if (upRTT > maxDownRTT) { maxDownRTT = upRTT maxDownRTTSetTime = currentTime in milliseconds maxRecentDownRTT = 0 } else { if (upRTT > maxRecentDownRTT) { maxRecentDownRTT = upRTT } } A check is then made to determine if maxDownRTT should be updated to the value of maxRecentRTT by comparing the update time against the current time in milliseconds: if (currentTime > (maxDownRTTSetTime + updateWindowLength)) { maxDownRTT = maxRecentDownRTT maxDownRTTSetTime = currentTime in milliseconds maxRecentDownRTT = 0 } Unicast a Get-RTT response packet back to the requester (xmitTime = xmitTime, peerGroupRTT = maxDownRTT, globalRTT = sourceRTT) This use case ends when the repair server or sender sends a Get-RTT response packet. R.5 Processing a Received Get-RTT Response Packet This use case begins when a Get-RTT response packet is received at a receiver or repair server. The receiver or repair server computes the local round trip time as: myUpRTT = (currentTime - xmitTime) if (myUpRTT < 1) { myUpRTT = 1 } Next, if either the value of maxUpRTT is equal to -1 or the value of peerGroupRTT is equal to -1, it immediately issues another Get-RTT request as follows: if ((maxUpRTT == -1) || (peerGroupRTT == -1)) { resendInterval = myUpRTT Cancel the current Get-RTT resend timer Start the Get-RTT timer with a duration of resendInterval Unicast a Get-RTT request packet (xmitTime = currentTime, upRTT = myUpRTT) } The resend interval is doubled and limited to the value of maxGetRTTCycleTime: resendInterval = (resendInterval * 2) if (resendInterval > maxGetRTTCycleTime) { resendInterval = maxGetRTTCycleTime } maxUpRTT is set to either the value of peerGroupRTT from the packet or the new value of myUpRTT, whichever is greater: if (myUpRTT > peerGroupRTT) { maxUpRTT = myUpRTT } else { maxUpRTT = peerGroupRTT } Finally, if the value of globalRTT in the response packet is nonnegative, the receiver or repair server then computes and sets the value of sourceRTT as the sum of the value of globalRTT and the value of myUpRTT: if (globalRTT >= 0) { sourceRTT = (globalRTT + myUpRTT) }