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.