AER Repair Service Use Cases ---------------------------- 1999-12-08 TEST Version: 1.0 Section A: Sender Protocol State Information: nextSeq - The sequence number to use for the next original data packet sent. A.1 Instantiation of the Protocol This use case begins when the sender protocol is instantiated (by upper layers). The protocol data structures are initialized and endpoints (e.g., sockets) are opened for the transmission and reception of packets. The state information is initialized as follows: nextSeq = 1 A number of source path message (SPM) packets (e.g, 10) are formed and sent to the multicast group address (obtained from the entity that instantiates the protocol). The SPM packet format is described in Appendix A. Each SPM packet contains the IP address of the sender, a multicast group address and a port number, and the current highest data packet sequence number of the transmitted data packets, which is equal to (nextSeq - 1). A highest data packet sequence number of 0 indicates that no data packets have been transmitted by the sender. The SPM timer is started after sending out the SPM packets. The duration of the SPM timer is set to some constant value (e.g., 4 seconds). This use case ends when the protocol is taken to a wait state (waiting for the events described in use cases A.2 - A.5. A.2 SPM Timer Service Routine This use case begins when the SPM timer expires. An SPM packet is transmitted to the destination multicast address. The SPM packet contains the current highest data packet sequence number sent, whic is equal to nextSeq minus 1. The SPM timer is then reset. This use case ends when the SPM timer is reset. A.3 Sending Data This use case begins when data (a variable length data block) is received from the upper layer. This data is placed in one or more data packets. The first data packet always has the first segment flag set, and all data packets except the last have the segmentation flag set. Each data packet has the retransmission flag cleared and is assigned a sequence number of nextSeq, then nextSeq is incremented for the next data packet. All data packets are then buffered in a retransmission buffer. The current sender NAK count (maximum value of NAK count seen in NAK packets so far) for each data packet is initialized to 0. These data packets are then sent out to the multicast group as the Testing if an Original Data Packet Can Be Sent Use Case in the rate control algorithm allows. The timestamp of each data packet is filled in with the current time in milliseconds just before the data packet is sent. The data packet format is described in Appendix A. This use case ends when the data packet transmission(s) are completed. A.4 Processing a Received NAK Packet This use case begins when a NAK packet is received from the lower layer. The NAK packet contains the sequence number of the data packet whose retransmission has been requested. It also contains a NAK count for that data packet. The NAK packet format is shown in Appendix A. If the NAK packet NAK count is greater than the current sender NAK count of that data packet in the retransmission buffer, then the current sender NAK count for the data packet in retransBuf is set to the NAK packet NAK count, the requested data packet is fetched from the retransmission buffer retransBuf, and the data packet is sent out to the multicast group address. Otherwise, the NAK packet is ignored and no retransmission is sent out. This use case ends when the repair data packet is sent or the NAK packet is ignored. A.5 Processing a Stop This use case begins when a stop protocol request is received from the upper layer. All of the resources allocated to the protocol layer are freed. This use case ends when the resources are freed. Section B: Receiver Protocol State Information: fastRepairFlag - If true, the repair procedure should not be delayed. If false, NAK suppression is used. repairServer - The address of the repair server for the receiver. readNextSeq - The sequence number of the last data packet delivered to the application. smoothedRTT - The smoothed receiver to sender RTT estimate in milliseconds. rttVariance - The mean deviation of the receiver to sender RTT estimate in milliseconds. retransTO - The current NAK retransmission timer duration in milliseconds. suppressTO - The current NAK suppression timer duration in milliseconds before being adjusted by a uniform random variate. B.1 Instantiation of the Protocol This use case begins when the receiver protocol is instantiated (by upper layers). The protocol data structures are initialized and endpoints (e.g., sockets) are opened for the transmission and reception of packets. This is followed by a multicast join operation for joining the multicast group on which data and NAK packets are expected. The multicast address and port numbers are received from the entity that instantiates the protocol.The state information is initialized as follows: fastRepairFlag = false repairServer = 0 readNextSeq = initial data packet sequence number smoothedRTT = 0 rttVariance = 3000 retransTO = (smoothedRTT + (2 * rttVariance)) suppressTO = 100 This use case ends when the protocol is taken to a wait state where it waits to receive data, NAK or SPM packets and also waits for expiration of timers as described below. B.2 Processing a Received SPM Packet This use case begins when an SPM packet is received. The following processing is performed (rs and maxSeq are the SPM packet repair server address and highest data packet sequence number): repairServer = rs if (maxSeq != 0) { Call Use Case B.4 using (maxSeq + 1) } This use case ends when either repairServer has been updated or Use Case B.4 returns. B.3 Processing a Received Data Packet This use case begins when a data packet is received. The following processing is performed (seq is the received data packet sequence number): Cancel any NAK retransmission timer for data packet seq Cancel any NAK suppression timer for data packet seq if ((data packet seq is not currently buffered in dataBuf) AND (seq >= readNextSeq)) { Buffer received data packet Call Use Case B.8 } else { Discard received data packet } This use case ends when either Use Case B.8 returns or the received data packet is discarded. B.4 Detecting Gaps in Data Packet Sequence Numbers This use case begins when gaps in received data packet sequence numbers must be detected and handled. The following processing is performed (seq is the sequence number passed to this use case): nakSeq = (seq - 1) while (nakSeq >= readNextSeq) { if ((data packet nakSeq is currently buffered) OR (NAK count for data packet nakSeq in dataBuf > 0)) { break while loop } NAK count for data packet nakSeq = 1 Call Use Case B.9 nakSeq = (nakSeq - 1) } This use case ends when the above processing is complete. B.5 NAK Suppression Timer Service Routine This use case begins when the NAK suppression timer for a missing data packet expires. The following processing is performed (seq is the sequence number of the missing data packet): if ((data packet seq is currently buffered) OR (seq < readNextSeq)) { End Use Case } if (NAK count for data packet seq > 48) { Error, connection is broken, cannot continue } Unicast a NAK packet for data packet seq with the receiver's NAK count and fastRepairFlag to repairServer Start a NAK retransmission timer for data packet seq with a duration of retransTO This use case ends when either the timer is ignored, an unrecoverable error occurs or a NAK retransmission timer for the data packet is started. B.6 NAK Retransmission Timer Service Routine This use case begins when the NAK retransmission timer for a missing data packet expires. The following processing is performed (seq is the sequence number of the missing data packet): if ((data packet seq is currently buffered) OR (seq < readNextSeq)) { End Use Case } NAK count for data packet seq is incremented by 1 Call Use Case B.9 This use case ends when either the timer is ignored or Use Case B.9 returns. B.7 Processing a Received NAK Packet This use case begins when a NAK packet is received. The following processing is performed (seq and nakCount are the NAK packet sequence number and NAK count): if ((data packet seq is currently buffered) OR (seq < readNextSeq)) { End Use Case } if (nakCount >= NAK count for data packet seq) { NAK count for data packet seq in dataBuf = nakCount Cancel any NAK retransmission timer for data packet seq Cancel any NAK suppression timer for data packet seq Start a NAK retransmission timer for data packet seq with a duration of retransTO } This use case ends when either the NAK packet is ignored or the NAK retransmission timer is started. B.8 Processing a Buffered Data Packet This use case begins when a received data packet is buffered. The following processing is performed (seq is the data packet sequence number): Call Use Case B.4 using seq if (application is using an asynchronous receive mode) { Check for data packets to deliver to the application Update readNextSeq } Note that in delivering any data packets to application, a "Reassembly" process is performed using readNextSeq along with the "First Segment" and "Segmentation" flags in the data packet headers. This use case ends when either Use Case B.4 returns or when readNextSeq is updated. B.9 Start Suppression Interval This use case begins when a NAK suppression interval is to be started for the missing data packet sequence number seq. The following processing is performed: if (fastRepairFlag == false) { Start a NAK suppression timer for data packet seq with a duration of a random variate, uniformly distributed between 0 and an upper limit (e.g., 1.5), times suppressTO } else { Call Use Case B.5 } This use case ends when the either the NAK suppression timer is started or Use Case B.5 returns. B.10 Enable Fast Repair This use case begins when the fast repair option is to be enabled. fastRepairFlag is set to true. This use case ends when fastRepairFlag is set to true. B.11 Disable Fast Repair This use case begins when the fast repair option is to be disabled. fastRepairFlag is set to false. This use case ends when fastRepairFlag is set to false. B.12 Processing a Stop This use case begins when a stop protocol request is received from the upper layer. All of the resources allocated to the protocol layer are freed. This use case ends when the resources are freed. B.13 Updating Round Trip Time Estimates This use case begins when a new RTT estimate is available. The following processing is performed (senderRTT is a new sender RTT estimate in milliseconds and maxUpRTT is a new maximum peer group RTT estimate in milliseconds. The maximum peer group RTT is the maximum RTT between this receiver's repair server and all receivers and repair servers serviced by it.): if (smoothedRTT == 0) { smoothedRTT = senderRTT rttVariance = (senderRTT / 4) } else { error = (senderRTT - smoothedRTT) smoothedRTT = (smoothedRTT + (error / 8)) rttVariance = (rttVariance + ((ABS(error) - rttVariance) / 4)) } retransTO = (smoothedRTT + (4 * rttVariance)) suppressTO = maxUpRTT This use case ends when suppressTO has been updated. B.13 Processing a Stop This use case begins when a stop protocol request is received from the upper layer. All of the resources allocated to the protocol layer are freed. This use case ends when the resources are freed. Section C: Repair Server Protocol State Information: repairServer - The address of the repair server for this repair server. maxSeqRcvd - The maximum data packet sequence number received. smoothedRTT - The smoothed repair server to sender RTT estimate in milliseconds. rttVariance - The mean deviation of the repair server to sender RTT estimate in milliseconds. retransTO - The current NAK retransmission timer duration in milliseconds. suppressTO - The current NAK suppression timer duration in milliseconds before being adjusted by a uniform random variate. C.1 Instantiation of the Protocol This use case begins when the active node receives the first SPM packet. The active node searches for the repair server object for the source address and multicast group and, not finding any, creates a new repair server object for the stream. The source address and multicast group are extracted from the SPM packet and stored by the repair server. The repair server object is added to the active node cache using the source address and multicast group. The state information is initialized as follows: repairServer = 0 maxSeqRcvd = 0 smoothedRTT = 0 rttVariance = 3000 retransTO = (smoothedRTT + (2 * rttVariance)) suppressTO = 100 Use Case C.3 is then called for further SPM packet processing. This use case ends when Use Case C.3 returns. C.2 SPM Wait Timer Service Routine This use case begins when the SPM wait timer expires. This event indicates that either no packets are being sent by the sender anymore on this multicast group or the routes have changed. All timers for the repair server are canceled, all buffer resources for the repair server are freed and the repair server object is removed from the active node cache. This use case ends when the protocol state is destroyed. C.3 Processing a Received SPM Packet in the Wait State This use case begins when an SPM packet is received in the wait state. The SPM packet is processed in this use case and is not forwarded down the multicast tree until this use case subcasts it. The following processing is performed (rs and maxSeq are the SPM packet repair server address and highest data packet sequence number): Cancel any current SPM wait timer Start an SPM wait timer with a fixed duration (e.g., 60 seconds) Call Use Case C.5 using (maxSeq + 1) repairServer = rs Subcast SPM packet downstream with the SPM packet repair server address field set to the local outgoing interface address Note that when subcasting the SPM packet downstream, it is sent once out each outgoing interface for the multicast tree, and each of these SPM packets has the outgoing interface IP address in the repair server field. This use case ends when the the SPM packet is subcast downstream. C.4 Processing a Received Data Packet This use case begins when a data packet with sequence number seq is received by the repair server. Note that original data packets are first forwarded out all outgoing interfaces for the multicast tree before this processing takes place. Repair data packets are processed first and forwarded out all outgoing interfaces for the multicast tree only when these use cases call for subcasting the repair data packet downstream. The following processing is performed: if (data packet seq is not currently buffered) { if (NAK state exists for data packet seq) { if ((data packet seq is a repair data packet) AND (NAK pending flag for data packet seq == true)) { Subcast data packet seq downstream } Cancel any current NAK suppression timer for data packet seq Cancel any current NAK retransmission timer for data packet seq NAK pending flag for data packet seq = false } Buffer data packet seq Call Use Case C.5 using seq if (seq > maxSeqRcvd) { maxSeqRcvd = seq } } else { Discard received data packet } Note that the repair server data packet buffer uses a certain buffer management policy (e.g., limited size FIFO). Also, the NAK state consists of a NAK pending flag, a NAK count and a downstream NAK count. This use case ends when either Use Case C.4 returns, maxSeqRcvd is updated or the data packet is discarded. C.5 Detecting Gaps in Data Packet Sequence Numbers This use case begins when lost data packets must be detected and handled. The following processing is performed (seq is the sequence number passed to this use case): if (maxSeqRcvd == 0) { End Use Case } if (seq > (maxSeqRcvd + 1)) { for (i = (seq - 1); i > maxSeqRcvd; i--) { if (no NAK state exists for data packet seq) { Call Use Case C.6 using i } } } This use case ends when either Use Case C.6 returns for the last missing data packet or no action is taken. C.6 Starting Data Packet Recovery This use case begins when data packet seq is detected as missing and the data packet recovery process must be started. The following processing is performed: Create nakState for data packet seq NAK count for data packet seq = 1 Downstream NAK count for data packet seq = 1 NAK pending flag for data packet seq = true Subcast a NAK packet for data packet seq with the repair server's NAK count and the fast repair flag set to false to the multicast group Start a NAK suppression timer for data packet seq with a duration of a random variate, uniformly distributed between 0 and an upper limit (e.g., 1.5), times suppressTO This use case ends when either a NAK suppression timer for data packet seq is started. C.7 Processing a Received Multicast NAK Packet from Upstream This use case begins when a multicast NAK packet is received from upstream. The following processing is performed (seq and nakCount are the NAK packet sequence number and NAK count): if (data packet seq is not currently buffered) { if (NAK state exists for data packet seq) { if (nakCount > NAK count for data packet seq) { NAK count in nakState for data packet seq = nakCount Downstream NAK count for data packet seq = nakCount Subcast a NAK packet for data packet seq with nakCount and the fast repair flag set to false to the multicast group } Cancel any current NAK suppression timer for data packet seq Cancel any current NAK retransmission timer for data packet seq } else { Create nakState for data packet seq NAK count in nakState for data packet seq = nakCount Downstream NAK count for data packet seq = nakCount NAK pending flag in nakState for data packet seq = true Subcast a NAK packet for data packet seq with nakCount and the fast repair flag set to false to the multicast group } Start a NAK retransmission timer for data packet seq with a duration of retransTO } This use case ends when either the NAK retransmission timer is started. C.8 Processing a Received Unicast NAK Packet from Downstream This use case begins when a unicast NAK packet is received from downstream. The following processing is performed (seq, nakCount and fastRepairFlag are the NAK packet sequence number, NAK count and fast repair flag): if (no NAK state exists for data packet seq) { Create NAK state for data packet seq Call Use Case C.9 using seq, nakCount, fastRepairFlag and true } else { if (nakCount > NAK count for data packet seq) { Call Use Case C.9 using seq, nakCount, fastRepairFlag and false } else { if (data packet seq is not currently buffered) { if (nakCount > downstream NAK count for data packet seq) { Downstream NAK count for data packet seq = nakCount Subcast NAK packet for data packet seq with nakCount and the fast repair flag set to false to the multicast group } } } } Note that the repair server downstream NAK count is the highest NAK count seen be the repair server from unicast NAK packets for data packet seq sent from downstream. It is used only for the purpose of preventing unnecessary downstream multicasts of NAK packets for NAK suppression. This use case ends when either C.9 returns, a NAK packet is subcast downstream or no action is taken. C.9 Processing a New NAK Packet with NAK State This use case begins when a received unicast NAK packet is a new NAK packet. The following processing is performed (seq, nakCount, fastRepairFlag and newNakStateFlag are passed into this use case.): NAK count for data packet seq = nakCount Downstream NAK count for data packet seq = nakCount if (data packet seq is currently buffered) { NAK pending flag for data packet seq = false Get data packet seq from buffer Set the retransmission flag in the data packet seq Subcast data packet seq downstream } else { NAK pending flag for data packet seq = true Subcast NAK packet for data packet seq with nakCount and the fast repair flag set to false to the multicast group Call Use Case C.10 using seq, nakCount, fastRepairFlag and newNakStateFlag } This use case ends when either data packet seq is subcast downstream or Use Case C.10 returns. C.10 Start Suppression Interval This use case begins when a received unicast NAK packet is a new NAK packet. The following processing is performed (seq, nakCount, fastRepairFlag and newNakStateFlag are passed into this use case): if (fastRepairFlag == false) { if (newNakStateFlag == true) { Start a NAK suppression timer for data packet seq with a duration of a random variate, uniformly distributed between 0 and an upper limit (e.g., 1.5), times suppressTO } } else { if (newNakStateFlag == false) { Cancel any current NAK suppression timer for data packet seq Cancel any current NAK retransmission timer for data packet seq } Unicast a NAK packet for data packet seq with nakCount and fastRepairFlag to repairServer Start a NAK retransmission timer for data packet seq with a duration of retransTO } This use case ends when either a NAK suppression timer is started, a NAK retransmission timer is started, or no action is taken. C.11 NAK Suppression Timer Service Routine This use case begins when the NAK suppression timer for data packet seq expires. The following processing is performed: if ((data packet seq is currently buffered) OR (No NAK state exists for data packet seq) OR (NAK pending flag for data packet seq == false)) { End Use Case } Unicast a NAK packet for data packet seq with the NAK count for data packet packet and fastRepairFlag set to false to repairServer Start a NAK retransmission timer for data packet seq with a duration of retransTO This use case ends when the NAK retransmission timer is started. C.12 NAK Retransmission Timer Service Routine This use case begins when the NAK retransmission timer for data packet seq expires. The following processing is performed: if ((data packet seq is currently buffered) OR (No NAK state exists for data packet seq) OR (NAK pending flag for data packet seq == false)) { End Use Case } NAK count for data packet seq is incremented by 1 Subcast a NAK packet for data packet seq including repair server NAK count and fastRepairFlag set to false downstream Start a NAK suppression timer for data packet seq with a duration of a random variate, uniformly distributed between 0 and and upper limit (e.g., 1.5), times suppressTO This use case ends when the NAK suppression timer is started. C.13 Updating Round Trip Time Estimates This use case begins when a new RTT estimate is available. The following processing is performed (senderRTT is a new sender RTT estimate in milliseconds and maxUpRTT is a new maximum peer group RTT estimate in milliseconds. The maximum peer group RTT is the maximum RTT between this receiver's repair server and all receivers and repair servers serviced by the it.): if (smoothedRTT == 0) { smoothedRTT = senderRTT rttVariance = (senderRTT / 4) } else { error = (senderRTT - smoothedRTT) smoothedRTT = (smoothedRTT + (error / 8)) rttVariance = (rttVariance + ((ABS(error) - rttVariance) / 4)) } retransTO = (smoothedRTT + (4 * rttVariance)) suppressTO = maxUpRTT This use case ends when suppressTO has been updated. Appendix A: Packet Formats SPM: Version Number, Packet Type, Multicast Group Address, Port Number, Repair Server Address, Maximum Transmitted Data Packet Sequence Number. The IP header of an SPM contains the SPM option. Data Packet: Version Number, Packet Type, Sequence Number, Timestamp, First Segment Flag, Segmentation Flag, Retransmission Flag, Payload Unicast NAK: Version Number, Packet Type, Data Packet Sequence Number, NAK Count, Fast Repair Flag, Source Address Repair Packet: Same as Data Packet. In addition, the IP header contains the repair/NAK option. Multicast NAK: Same as Unicast NAK Packet. In addition, the IP header contains the repair/NAK option. ----------------------------------------------------------------------------- NCA Use Cases : Estimation of Suppression Timer and Retransmission Timer Values --------------------------------------------------- 1999-12-08 Version: 1.0 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 distributed 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. Each receiver or repair server starts a 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. Each receiver or repair server resets the Det-RTT resend timer using the current value of resendInterval, and subsequently sends a Get-RTT request packet to the nearest upstream repair server (or sender). The Get-RTT request packet fields are set as follows: xmitTime = currentTime upRTT = myUpRTT 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 } The repair server or sender then sends a Get-RTT response packet. The Get-RTT response packet fields are set as follows: 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) 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 Send 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) } ----------------------------------------------------------------------------- NCA Use Cases : Nomination Algorithm ------------------------------------- 1999-12-08 Version: 1.0 Section D: Sender Protocol State Information: csmNominee - The address of the current nominee receiver. csmLPE - The current loss probability estimate reported by the nominee receiver. csmRTT - The current round trip time to the sender reported by the nominee receiver. csmSetTime - The time, in milliseconds, when csmLPE, csmRTT and csmNominee were set. D.1 Initialization This use case begins when the sender is instantiated. The state information is initialized as follows: csmNominee = 0 csmLPE = -1.0 csmRTT = 0 csmSetTime = currentTime in milliseconds This use case ends when the state information is initialized. D.2 Processing a Received CSM Packet This use case begins when a CSM packet arrives at the sender. The following test is performed (addr, lpe and rtt are the CSM packet receiver address, loss probability estimate and source to receiver round trip time in milliseconds. currentTime is the current time in milliseconds. The timeout parameter is set to some constant (e.g., 17000 milliseconds).): if ((csmNominee == 0) OR (addr == csmNominee) OR ((0.0 <= lpe <= 1.0) AND (csmLPE < 0.0)) OR ((0.0 <= lpe <= 1.0) AND (0.0 <= csmLPE <= 1.0) AND (g(lpe, rtt) > g(csmLPE, csmRTT))) OR ((lpe < 0.0) AND (csmLPE < 0.0) AND (rtt > csmRTT)) OR (currentTime > (csmSetTime + 17000))) { Call Use Case D.3 } The function g(lpe,rtt) is as follows: g(lpe,rtt) = (rtt * squareroot(lpe)), 0 <= lpe <= 1, rtt >= 0 = 0, otherwise This use case ends when either Use Case D.3 returns or the CSM packet is ignored. D.3 Update Nominee Receiver Parameters This use case begins when a CSM is receiver from the nominee receiver. The CSM packet is processed as follows: oldNominee = csmNominee csmNominee = CSM packet receiver address csmLPE = CSM packet loss probability estimate csmRTT = CSM packet receiver to source round trip time csmSetTime = currentTime in milliseconds if (oldNominee != csmNominee) { if (csmNominee != 0) { Send a NAM packet to csmNominee (nominee address = csmNominee) } if (oldNominee != 0) { Send a NAM packet to oldNominee (nominee address = csmNominee) } Cancel NAM Timer Start NAM Timer with a constant duration (e.g., 7000 milliseconds) } This use case ends when either NAM Timer is restarted or csmSetTime is set. D.4 NAM Timer Service Routine This use case begins when the NAM Timer expires. The following processing is performed: if (csmNominee != 0) { Send a NAM packet to csmNominee (nominee address = csmNominee) Restart NAM Timer with a constant duration (e.g., 7000 milliseconds) } This use case ends when either the NAM Timer is restarted or no action is taken. Section E: Receiver Protocol State Information : isNomineeFlag - If true, indicates that this receiver has been nominated to send congestion control signals to the sender, otherwise false. E.1 Initialization This use case begins when the receiver protocol is initialized by the upper layers. The state information is initialized as follows: isNomineeFlag = false A sliding loss probability estimate (LPE) window with a fixed maximum size (e.g., 200 packets) is created for recording the arrival of original data packets and computing the LPE. The CSM Timer is started with a duration of a random variate, uniformly distributed between 0 and 1.0, times some fixed time value (e.g., 5000 milliseconds). This use case ends when the CSM Timer has been started. E.2 Processing a Received Original Data Packet This use case begins when an original data packet (not a retransmitted data packet) is received. The sliding LPE window is updated to record the reception of the data packet using the following rules: - the window may expand from being empty to the maximum size (e.g., 200) - the window never shrinks in size - once at the maximum window size, the window may be slid forward while the window size remains constant - the window may only be slid forward (never backward) This use case ends when the sliding LPE window has been updated. E.3 CSM Timer Service Routine This use case begins when the CSM Timer expires. A CSM packet is created with the LPE and sourceRTT fields set as follows: if (current sliding LPE window size < 250) { CSM packet LPE field = -1 } else { CSM packet LPE field = (1000 * (windowSize - capsulesReceived) / windowSize) } if (receiver to source round trip time (RTT) is unavailable) { CSM packet source RTT field = -1 } else { CSM packet source RTT field = current receiver to source RTT estimate in milliseconds } The completed CSM packet is unicast to the receiver's upstream repair server. The CSM Timer is restarted using a constant duration (e.g., 5000 milliseconds). This use casse ends when the CSM Timer is restarted. E.4 Processing a Received NAM Packet This use case begins when a NAM packet is received. The following processing is performed: if (NAM packet nominee address == receiver's local address) { isNomineeFlag = true Call Enable Fast Repair Use Case in the repair service algorithm } else { isNomineeFlag = false Call Disable Fast Repair Use Case in the repair service algorithm } This use case ends when isNomineeFlag has been updated. Section F: Repair Server Protocol State Information: csmAddress - The address of the worst receiver downstream. csmLPE - The current loss probability estimate reported by the worst receiver downstream. csmRTT - The current round trip time to the sender reported by the worst receiver downstream. csmSetTime - The time, in milliseconds, when csmLPE, csmRTT and csmNominee were set. F.1 Initialization This use case begins when the repair server receives the first SPM packet. The state information is initialized as follows: csmAddress = 0 csmLPE = -1.0 csmRTT = 0 csmSetTime = currentTime in milliseconds The CSM Timer is started using a constant duration (e.g., 7000 milliseconds). This use case ends when the CSM Timer has been started. F.2 Processing a Received CSM Packet This use case begins when a CSM packet arrives at the repair server. The following test is performed (addr, lpe and rtt are the CSM packet receiver address, loss probability estimate and sender to receiver round trip time in milliseconds. currentTime is the current time in milliseconds. The timeout parameter is set to some constant (e.g., 17000 milliseconds)): if ((csmAddress == 0) OR (addr == csmAddress) OR ((0.0 <= lpe <= 1.0) AND (0.0 <= csmLPE <= 1.0) AND (g(lpe, rtt) > g(csmLPE, csmRTT))) OR ((lpe < 0.0) AND (csmLPE < 0.0) AND (rtt > csmRTT)) OR (currentTime > (csmSetTime + 17000))) { Call Use Case F.3 } The function g(lpe,rtt) is as follows: g(lpe,rtt) = (rtt * squareroot(lpe)), 0 <= lpe <= 1, rtt >= 0 = 0, otherwise This use case ends when either Use Case F.3 returns or the CSM packet is ignored. F.3 Update Worst Receiver Parameters This use case begins when a CSM packet is received from the worst receiver downstream. The CSM packet is processed as follows: csmAddress = CSM packet receiver address csmLPE = CSM packet loss probability estimate csmRTT = CSM packet receiver to source round trip time csmSetTime = currentTime if (csmAddress != 0) { Send a CSM packet upstream to this repair server's repair server (lpe = csmLPE, sourceRTT = csmRTT, receiver's address = csmAddress) } Cancel the CSM Timer Start the CSM Timer with a constant duration (e.g., 7000 milliseconds) This use case ends when the CSM Timer is restarted. F.4 CSM Timer Service Routine This use case begins when the CSM Timer expires. The following processing is performed: if (currentTime in milliseconds > (csmSetTime + 17000)) { csmAddress = 0 csmLPE = -1.0 csmRTT = 0 csmSetTime = currentTime in milliseconds } if (csmAddress != 0) { Send a CSM packet with the receiver address set to csmAddress, the LPE set to csmLPE and the sender RTT set to csmRTT to this repair server's repair server } Restart the CSM Timer with a constant duration (e.g., 7000 milliseconds) This use case ends when the CSM Timer has been started. Appendix A: Packet Formats Congestion Status Message (CSM) Packet: CSM packets are unicast from a receiver or repair server to its upstream repair server, which may be the sender. Fields: Version Number, Packet Type, Multicast Group Address, Port Number, Loss Probability Estimate, Source to Receiver RTT. Nominee Activation Message (NAM) Packet: Unicast from the sender to a receiver with no intervention by any repair servers. Fields: Version Number, Packet Type, Multicast Group Address, Port Number, Nominee Address ---------------------------------------------------------------------------- NCA Use Cases : Rate Control Algorithm -------------------------------------- 1999-12-08 Version: 1.0 Section G: Sender Protocol State Information: nominee - The current nominee receiver address. There is no nominee if equal to 0. timerNominee - The address of the nominee receiver when the CCM Timer was set. winSize - The current congestion window sizer. Must be greater than or equal to 1.0 at all times. ssThreshold - The slow start threshold window size. winLowerSeq - The sequence number of the oldest original data packet that has not received a CCM packet response. Always the lower end of the congestion window. Must be greater than or equal to 0. dupLowerSeq - The number of duplicate CCM packets received for the winLowerSeq data packet. maxSeqSent - The sequence number of the most recent original data packet sent. This may be either in or outside of the congestion window. Must be greater than or equal to 0. smoothedRTT - The smoothed RTT estimate in milliseconds. rttVariance - The mean deviation of the RTT estimate in milliseconds (a la TCP). ccmTimeout - The maximum amount of time in milliseconds to wait for a CCM packet. If this time expires and no CCM packet is received, then the congestion window size is dropped to 1.0. backoffFactor - The exponential backoff factor used in case of successive timeouts. fastRecovFlag - A flag for recording if fast recovery is active or not. fastRecovSeq - The sequence number of the last data packet in the congestion window when fast recovery is activated. Set to 0 when fast recovery is not active. maxBurstCount - The number of original data packets sent since the last CCM packet was received. G.1 Initialization This use case begins when the sender is instantiated. The constants used by NCA are as follows: MAX_WINDOW = 256 MAX_BURST = 4 FR_MAX_BURST = 2 MIN_SS_THRESH = 2 MAX_BACKOFF = 64 The state information is initialized as follows: nominee = 0 timerNominee = 0 winSize = 1.0 ssThreshold = 64 winLowerSeq = initial data packet sequence number dupLowerSeq = 0 maxSeqSent = (winLowerSeq - 1) smoothedRTT = 0 rttVariance = 0 ccmTimeout = 1000 backoffFactor = 1 fastRecovFlag = false fastRecovSeq = 0 maxBurstCount = 0 This use case ends when the state information has been initialized. G.2 Processing a Received CCM Packet This use case begins when a CCM packet arrives at the sender. The CCM packet is processed as follows (ccmAddr, ccmRetransFlag, seq and timestamp are the CCM packet IP source address, retransmission flag, sequence number and time stamp): if (ccmAddr == nominee) { backoffFactor = 1 maxBurstCount = 0 if (ccmRetransFlag == false) { Call Use Case G.3 passing timestamp } Call Use Case G.5 passing seq if (winLowerSeq > maxSeqSent) { Cancel CCM Timer } } This use case ends when either Use Case G.4 returns or the CCM Timer is canceled. G.3 Updating the RTT Estimate This use case begins when the sender receives a CCM and has to update its RTT estimate. The CCM packet is processed as follows (timestamp is the time stamp value of the CCM packet passed to this use case): newRTT = (timestamp - currentTime in milliseconds) if (smoothedRTT == 0) { smoothedRTT = newRTT ccmTimeout = smoothedRTT } else { Call Use Case c.4 passing the value of newRTT } This use case ends when either smoothedRTT and ccmTimeout are updated or Use Case G.4 returns. G.4 Updating the RTT Estimate and Variance This use case begins when both the RTT estimate and variance must be updated given a new value of newRTT. The following processing is performed: error = (newRTT - smoothedRTT) smoothedRTT = (smoothedRTT + (error / 8)) if (rttVariance == 0) { rttVariance = ABS(error) } else { rttVariance = (rttVariance + ((ABS(error) - rttVariance) / 4)) } ccmTimeout = (smoothedRTT + (4 * rttVariance)) Note that ABS() is the absolute value function. This use case ends when ccmTimeout has been updated. G.5 Updating the Congestion Window This use case begins when the congestion window needs to be updated due to the arrival of a CCM packet. The congestion window is updated as follows (seq is the sequence number of the CCM packet passed to this use case): if (seq == winLowerSeq) { dupLowerSeq = (dupLowerSeq + 1) } else { if (seq > winLowerSeq) { Call Use Case C.6 } if (fastRecovFlag == true) { if (winLowerSeq > fastRecovSeq) { Call Use Case G.9 } else { Call Use Case G.8 } } else { if (dupLowerSeq >= 3) { Call Use Case G.10 } } This use case ends when the congestion window has been updated. G.6 Sliding the Congestion Window Forward This use case begins when the congestion window is ready to be slid forward. The congestion window is updated as follows (seq is the sequence number of the CCM packet passed to this use case): if (fastRecovFlag == false) { Call Use Case G.7 } winLowerSeq = seq dupLowerSeq = 0 This use case ends when dupLowerSeq is set to 0. G.7 Increasing the Congestion Window Size This use case begins when a CCM packet is received and the congestion window size must be increased while not in fast recovery. The congestion window is updated as follows: if (winSize <= ssThreshold) { winSize = (winSize + 1.0) } else { winSize = (winSize + (1.0 / FLOOR(winSize))) } winSize = MIN(winSize, MAX_WINDOW) winSize = MAX(winSize, 1.0) Note that the FLOOR() function returns the largest value that is not greater than the argument and is equal to a mathematical integer. This use case ends when winSize has been updated. G.8 Increasing the Congestion Window Size in Fast Recovery This use case begins when a CCM packet is received and the congestion window size must be increased while in fast recovery. The congestion window is updated as follows: winSize = (winSize + 1.0) winSize = MIN(winSize, MAX_WINDOW) winSize = MAX(winSize, 1.0) This use case ends when winSize has been updated. G.9 Leaving Fast Recovery This use case begins when the sender must exit the fast recovery state. The following processing is performed: fastRecovFlag = false fastRecovSeq = 0 winSize = ssThreshold winSize = MIN(winSize, MAX_WINDOW) winSize = MAX(winSize, 1.0) This use case ends when winSize has been updated. G.10 Entering Fast Recovery This use case begins when the sender must enter the fast recovery state. The following processing is performed: fastRecovFlag = true fastRecovSeq = (winLowerSeq + FLOOR(winSize) - 1) ssThreshold = MAX((winSize / 2.0), MIN_SS_THRESH) winSize = (ssThreshold + 3.0) winSize = MIN(winSize, MAX_WINDOW) winSize = MAX(winSize, 1.0) This use case ends when winSize has been updated. G.11 Testing if an Original Data Packet Can Be Sent This use case begins when an original data packet with a sequence number of (maxSeqSent + 1) is to be sent. The following processing is performed: if (maxSeqSent >= (winLowerSeq + FLOOR(winSize) - 1)) { The original data packet cannot be sent at the current time End Use Case } if (fastRecovFlag == true) { if (maxBurstCount >= FR_MAX_BURST) { The original data packet cannot be sent at the current time End Use Case } } else { if (maxBurstCount >= MAX_BURST) { The original data packet cannot be sent at the current time End Use Case } } The original data packet can be sent at the current time This use case ends when the determination is made to either allow or disallow the original data packet to be sent. G.12 Sending an Original Data Packet This use case begins when an original data packet with a sequence number of (maxSeqSent + 1) is ready to be sent and Use Case G.11 allows the packet to be sent. The following processing is performed: maxSeqSent = (maxSeqSent + 1) maxBurstCount = (maxBurstCount + 1) Cancel CCM Timer if (maxSeqSent >= winLowerSeq) { timerNominee = nominee Start the CCM Timer with a duration of (backoffFactor * ccmTimeout) } This use case ends when the CCM Timer is either canceled or canceled and restarted. G.13 CCM Timer Service Routine This use case begins when the CCM Timer expires. The following processing is performed: if (timerNominee == 0) { ssThreshold = 64 backoffFactor = 1 } else { ssThreshold = MAX((winSize / 2.0), MIN_SS_THRESH) backoffFactor = MIN((backoffFactor * 2), MAX_BACKOFF) } winSize = 1.0 winLowerSeq = (maxSeqSent + 1) fastRecovFlag = false fastRecovSeq = 0 maxBurstCount = 0 This use case ends when winLowerSeq has been updated. G.14 Updating the Nonimee Receiver This use case begins when the nominee receiver address has changed and must be updated. The following processing is performed (addr is the new nominee address): nominee = addr if (nominee == 0) { ccmTimeout = the initial value (e.g., 1000 milliseconds) } This use case ends when nominee has been updated. Section H: Receiver Protocol State Information: isNomineeFlag - If true, indicates that this receiver has been nominated to send congestion control signals to the sender, otherwise false (from NCA Nomination Algorithm). H.1 Processing a Received Data Packet This use case begins when a data packet is received. All receivers must maintain the lowest sequence number of all outstanding data packets at all times. The following processing is performed: if ((isNomineeFlag == true) AND (the data packet has not been received before)) { Send a CCM packet to the sender (seq = lowest outstanding data packet sequence number, timestamp = data packet timestamp, retrans = data packet retransmission flag) } This use case ends when either a CCM packet is sent to the sender or no processing occurs. Appendix A: Packet Formats Congestion Control Message (CCM) Packet: Unicast from the nominated receiver to the sender. Fields: Version Number, Packet Type, Multicast Group Address, Port Number, Sequence Number, Timestamp, Retransmission Flag