INTERNET-DRAFT PGM Reliable Transport Protocol Tony Speakman Expires 10 October 2000 cisco Systems Dino Farinacci Jon Crowcroft Jim Gemmell Procket Networks UCL Microsoft Steven Lin Alex Tweedly Dan Leshchiner Michael Luby Nidhi Bhaskar TIBCO Software Digital Fountain Richard Edmonstone Kelly Morse Johnson Todd Montgomery Luigi Rizzo Rajitha Sumanasekera WhiteBarn/WVU University of Pisa Lorenzo Vicisano cisco Systems 10 April 2000 PGM Reliable Transport Protocol Specification Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Speakman et al. [Page 1] INTERNET-DRAFT PGM Specification 10 April 2000 Abstract Pragmatic General Multicast (PGM) is a reliable multicast transport pro- tocol for applications that require ordered or unordered, duplicate- free, multicast data delivery from multiple sources to multiple receivers. PGM guarantees that a receiver in the group either receives all data packets from transmissions and repairs, or is able to detect unrecoverable data packet loss. PGM is specifically intended as a work- able solution for multicast applications with basic reliability require- ments. Its central design goal is simplicity of operation with due regard for scalability and network efficiency. Table of Contents 1. Introduction and Overview ..................................... 3 2. Architectural Description ..................................... 8 3. Terms and Concepts ............................................ 11 4. Procedures - General .......................................... 19 5. Procedures - Sources .......................................... 19 6. Procedures - Receivers ........................................ 22 7. Procedures - Network Elements ................................. 27 8. Packet Formats ................................................ 32 9. Options ....................................................... 42 10. Security Considerations ....................................... 57 Appendix A - Forward Error Correction ............................. 59 Appendix B - Support for Congestion Control ....................... 73 Appendix C - SPM Requests ......................................... 80 Appendix D - Poll Mechanism ....................................... 84 Appendix E - Implosion Prevention ................................. 93 Appendix F - Transmit Window Example .............................. 99 Abbreviations ..................................................... 103 Acknowledgements .................................................. 104 Revision History .................................................. 105 References ........................................................ 107 Speakman et al. [Page 2] INTERNET-DRAFT PGM Specification 10 April 2000 1. Introduction and Overview A variety of reliable protocols have been proposed for multicast data delivery, each with an emphasis on particular types of applications, network characteristics, or definitions of reliability ([1], [2], [3], [4]). In this tradition, Pragmatic General Multicast (PGM) is a reli- able transport protocol for applications that require ordered or unor- dered, duplicate-free, multicast data delivery from multiple sources to multiple receivers. PGM is specifically intended as a workable solution for multicast appli- cations with basic reliability requirements rather than as a comprehen- sive solution for multicast applications with sophisticated ordering, agreement, and robustness requirements. Its central design goal is sim- plicity of operation with due regard for scalability and network effi- ciency. PGM has no notion of group membership. It simply provides reliable mul- ticast data delivery within a transmit window advanced by a source according to a purely local strategy. Reliable delivery is provided within a source's transmit window from the time a receiver joins the group until it departs. PGM guarantees that a receiver in the group either receives all data packets from transmissions and repairs, or is able to detect unrecoverable data packet loss. PGM supports any number of sources within a multicast group, each fully identified by a globally unique Transport Session Identifier (TSI), but since these sources/sessions operate entirely independently of each other, this specification is phrased in terms of a single source and extends without modification to multiple sources. More specifically, PGM is not intended for use with applications that depend either upon acknowledged delivery to a known group of recipients, or upon total ordering amongst multiple sources. Rather, PGM is best suited to those applications in which members may join and leave at any time, and that are either insensitive to unrecov- erable data packet loss or are prepared to resort to application recovery in the event. Through its optional extensions, PGM provides specific mechanisms to support applications as disparate as stock and news updates, data conferencing, low-delay real-time video transfer, and bulk data transfer. In the following text, transport-layer originators of PGM data packets are referred to as sources, transport-layer consumers of PGM data pack- ets are referred to as receivers, and network-layer entities in the intervening network are referred to as network elements. Unless other- wise specified, the term "repair" will be used to indicate both the actual retransmission of a copy of a missing packet or the transmission Speakman et al. [Page 3] INTERNET-DRAFT PGM Specification 10 April 2000 of an FEC repair packet. 1.1. Summary of Operation PGM runs over a datagram multicast protocol such as IP multicast [5]. In the normal course of data transfer, a source multicasts sequenced data packets (ODATA), and receivers unicast selective negative ack- nowledgements (NAKs) for data packets detected to be missing from the expected sequence. Network elements forward NAKs PGM-hop-by-PGM-hop to the source, and confirm each hop by multicasting a NAK confirmation (NCF) in response on the interface on which the NAK was received. Repairs (RDATA) may be provided either by the source itself or by a Designated Local Repairer (DLR) in response to a NAK. Since NAKs provide the sole mechanism for reliability, PGM is particu- larly sensitive to their loss. To minimize NAK loss, PGM defines a network-layer hop-by-hop procedure for reliable NAK forwarding. Upon detection of a missing data packet, a receiver repeatedly unicasts a NAK to the last-hop PGM network element on the distribution tree from the source. A receiver repeats this NAK until it receives a NAK confir- mation (NCF) multicast to the group from that PGM network element. That network element responds with an NCF to the first occurrence of the NAK and any further retransmissions of that same NAK from any receiver. In turn, the network element repeatedly forwards the NAK to the upstream PGM network element on the reverse of the distribution path from the source of the original data packet until it also receives an NCF from that network element. Finally, the source itself receives and confirms the NAK by multicasting an NCF to the group. While NCFs are multicast to the group, they are not propagated by PGM network elements since they act as hop-by-hop confirmations. To avoid NAK implosion, PGM specifies procedures for subnet-based NAK suppression amongst receivers and NAK elimination within network ele- ments. The usual result is the propagation of just one copy of a given NAK along the reverse of the distribution path from any network with directly connected receivers to a source. The net effect is that unicast NAKs return from a receiver to a source on the reverse of the path on which ODATA was forwarded, that is, on the reverse of the distribution tree from the source. More specifically, they return through exactly the same sequence of PGM network elements through which ODATA was forwarded, but in reverse. The reasons for han- dling NAKs this way will become clear in the discussion of constraining repairs, but first it's necessary to describe the mechanisms for estab- lishing the requisite source path state in PGM network elements. Speakman et al. [Page 4] INTERNET-DRAFT PGM Specification 10 April 2000 To establish source path state in PGM network elements, the basic data transfer operation is augmented by Source Path Messages (SPMs) from a source, periodically interleaved with ODATA. SPMs function primarily to establish source path state for a given TSI in all PGM network elements on the distribution tree from the source. PGM network elements use this information to address returning unicast NAKs directly to the upstream PGM network element toward the source, and thereby insure that NAKs return from a receiver to a source on the reverse of the distribution path for the TSI. SPMs are sent by a source at least at the rate at which the transmit window is advanced, and they serve to provoke further NAKs from receivers as well as to maintain receive window state in the receivers. As a further efficiency, PGM specifies procedures for the constraint of repairs by network elements so that they reach only those group members that did not receive the original transmission. As NAKs traverse the reverse of the ODATA path (upward), they establish repair state in the network elements which is used in turn to constrain the (downward) for- warding of the corresponding RDATA. Besides procedures for the source to provide repairs, PGM also specifies options and procedures that permit designated local repairers (DLRs) to announce their availability and to redirect repair requests (NAKs) to themselves rather than to the original source. In addition to these conventional procedures for loss recovery through selective ARQ, Appen- dix A specifies Forward Error Correction (FEC) procedures for sources to provide and receivers to request general error correcting parity packets rather than selective retransmissions. Finally, since PGM operates without regular return traffic from receivers, conventional feedback mechanisms for transport flow and congestion control cannot be applied. Appendix B specifies some prelim- inary strategies for congestion avoidance to be modified and proven or discarded as experience dictates. In its basic operation, PGM relies on a purely rate-limited transmission strategy in the source to bound the bandwidth consumed by PGM transport sessions and to define the transmit window maintained by the source. PGM defines four basic packet types: three that flow downstream (SPMs, DATA, NCFs), and one that flows upstream (NAKs). 1.2. Design Goals and Constraints PGM has been designed to serve that broad range of multicast applica- tions that have relatively simple reliability requirements, and to do so in a way that realizes the much advertised but often unrealized network Speakman et al. [Page 5] INTERNET-DRAFT PGM Specification 10 April 2000 efficiencies of multicast data transfer. The usual impediments to real- izing these efficiencies are the implosion of negative and positive ack- nowledgements from receivers to sources, repair latency from the source, and the propagation of repairs to disinterested receivers. 1.2.1. Reliability. Reliable data delivery across an unreliable network is conventionally achieved through an end-to-end protocol in which a source (implicitly or explicitly) solicits receipt confirmation from a receiver, and the receiver responds positively or negatively. While the frequency of negative acknowledgements is a function of the reliability of the net- work and the receiver's resources (and so, potentially quite low), the frequency of positive acknowledgements is fixed at at least the rate at which the transmit window is advanced, and usually more often. Negative acknowledgements primarily determine repairs and reliability. Positive acknowledgements primarily determine transmit buffer manage- ment. When these principles are extended without modification to multicast protocols, the result, at least for positive acknowledgements, is a bur- den of positive acknowledgments transmitted to the source that quickly threatens to overwhelm it as the number of receivers grows. More suc- cinctly, ACK implosion keeps ACK-based reliable multicast protocols from scaling well. One of the goals of PGM is to get as strong a definition of reliability as possible from as simple a protocol as possible. ACK implosion can be addressed in a variety of effective but complicated ways, most of which require re-transmit capability from other than the original source. An alternative is to dispense with positive acknowledgements altogether, and to resort to other strategies for buffer management while retaining negative acknowledgements for repairs and reliability. The approach taken in PGM is to retain negative acknowledgements, but to dispense with positive acknowledgements and resort instead to timeouts at the source to manage transmit resources. The definition of reliability with PGM is a direct consequence of this design decision. PGM guarantees that a receiver either receives all data packets from transmissions and repairs, or is able to detect unre- coverable data packet loss. PGM includes strategies for repeatedly soliciting NAKs from receivers, and for adding reliability to the NAKs themselves. By reinforcing the NAK mechanism, PGM minimizes the probability that a receiver will detect a missing data packet so late that the packet is unavailable for repair Speakman et al. [Page 6] INTERNET-DRAFT PGM Specification 10 April 2000 either from the source or from a designated local repairer (DLR). Without ACKs and knowledge of group membership, however, PGM cannot eliminate this possibility. 1.2.2. Group Membership A second consequence of eliminating ACKs is that knowledge of group membership is neither required nor provided by the protocol. Although a source may receive some PGM packets (NAKs for instance) from some receivers, the identity of the receivers does not figure in the process- ing of those packets. Group membership may change during the course of a PGM transport session without the knowledge of or consequence to the source or the remaining receivers. 1.2.3. Efficiency While PGM avoids the implosion of positive acknowledgements simply by dispensing with ACKs, the implosion of negative acknowledgements is addressed directly. Receivers observe a random back-off prior to generating a NAK during which interval the NAK is suppressed by the receiver upon receipt of a matching NCF. In addition, PGM network elements eliminate duplicate NAKs received on different interfaces on the same network element. The combination of these two strategies usually results in the source receiving just a single NAK for any given lost data packet. Whether a repair is provided from a DLR or the original source, it is important to constrain that repair to only those network segments con- taining members that negatively acknowledged the original transmission rather than propagating it throughout the group. PGM specifies pro- cedures for network elements to use the pattern of NAKs to define a sub-tree within the group upon which to forward the corresponding repair so that it reaches only those receivers that missed it in the first place. 1.2.4. Simplicity PGM is designed to achieve the greatest improvement in reliability (as compared to the usual UDP) with the least complexity. As a result, PGM does NOT address conference control, global ordering amongst multiple sources in the group, nor recovery from network partitions. 1.2.5. Operability PGM is designed to function, albeit with less efficiency, even when some or all of the network elements in the multicast tree have no knowledge of PGM. To that end, all PGM data packets can be conventionally Speakman et al. [Page 7] INTERNET-DRAFT PGM Specification 10 April 2000 multicast routed by non-PGM network elements with no loss of functional- ity, but with some inefficiency in the propagation of RDATA and NCFs. In addition, since NAKs are unicast to the last-hop PGM network element and NCFs are multicast to the group, NAK/NCF operation is also con- sistent across non-PGM network elements. Note that for NAK suppression to be most effective, receivers should always have a PGM network element as a first hop network element between themselves and every path to every PGM source. If receivers are several hops removed from the first PGM network element, the efficacy of NAK suppression may degrade. 1.3. Options In addition to the basic data transfer operation described above, PGM specifies several end-to-end options to address specific application requirements. PGM specifies options to support fragmentation, late joining, redirection, Forward Error Correction (FEC), reachability, and session synchronisation/termination/reset. Options may be appended to PGM data packet headers only by their original transmitters. While they may be interpreted by network elements, options are neither added nor removed by network elements. All options are receiver-significant (i.e., they must be interpreted by receivers). Some options are also network-significant (i.e., they must be interpreted by network elements). Fragmentation may be used in conjunction with data packets to allow a transport-layer entity at the source to break up application-layer data packets into multiple PGM data packets to conform with the maximum transmission unit (MTU) supported by the network layer. Late joining allows a source to indicate whether or not receivers may request all available repairs when they initially join a particular transport session. Redirection may be used in conjunction with Poll Responses to allow a DLR to respond to normal NCFs or POLLs with a redirecting POLR advertis- ing its own address as an alternative retransmitter to the original source. FEC techniques may be applied by receivers to use source-provided parity packets rather than selective retransmissions to effect loss recovery. 2. Architectural Description As an end-to-end transport protocol, PGM specifies packet formats and procedures for sources to transmit and for receivers to receive data. To enhance the efficiency of this data transfer, PGM also specifies Speakman et al. [Page 8] INTERNET-DRAFT PGM Specification 10 April 2000 packet formats and procedures for network elements to improve the relia- bility of NAKs and to constrain the propagation of repairs. The divi- sion of these functions is described in this section and expanded in detail in the next section. 2.1. Source Functions Data Transmission Sources multicast ODATA packets to the group within the transmit window at a given transmit rate. Source Path State Sources multicast SPMs to the group, interleaved with ODATA if present, to establish source path state in PGM network elements. NAK Reliability Sources multicast NCFs to the group in response to any NAKs they receive. Repairs Sources multicast RDATA packets to the group in response to NAKs received for data packets within the transmit window. Transmit Window Advance Sources may advance the trailing edge of the window according to one of a number of strategies. Implementations may support automatic adjustments such as keeping the window at a fixed size in bytes, a fixed number of packets or a fixed real time duration. In addition, they may optionally delay window advancement based on NAK-silence for a certain period. Some possible strategies are outlined later in this document. 2.2. Receiver Functions Source Path State Receivers use SPMs to determine the last-hop PGM network element for a given TSI to which to direct their NAKs. Data Reception Receivers receive ODATA within the transmit window and eliminate Speakman et al. [Page 9] INTERNET-DRAFT PGM Specification 10 April 2000 any duplicates. Repair Requests Receivers unicast NAKs to the last-hop PGM network element and may optionally multicast a NAK with TTL of 1 to the local group for data packets within the receive window detected to be missing from the expected sequence. A receiver must repeatedly transmit a given NAK until it receives a matching NCF. NAK Suppression Receivers suppress NAKs for which a matching NCF or NAK is received during the NAK transmit back-off interval. Receive Window Advance Receivers immediately advance their receive windows upon receipt of any PGM data packet or SPM within the transmit window that advances the receive window. 2.3. Network Element Functions Network elements forward ODATA without intervention. Source Path State Network elements intercept SPMs and use them to establish source path state for the corresponding TSI before multicast forwarding them in the usual way. NAK Reliability Network elements multicast NCFs to the group in response to any NAK they receive. For each NAK received, network elements create repair state recording the transport session identifier, the sequence number of the NAK, and the input interface on which the NAK was received. Constrained NAK Forwarding Network elements repeatedly unicast forward only the first copy of any NAK they receive to the upstream PGM network element on the distribution path for the TSI and in addition they may optionally multicast this NAK upstream with TTL of 1. They do this until they receive an NCF in response. NOTA BENE: Once confirmed by an NCF, network elements discard Speakman et al. [Page 10] INTERNET-DRAFT PGM Specification 10 April 2000 NAK packets; they are NOT retained in network elements beyond this forwarding operation. NAK Elimination Network elements discard exact duplicates of any NAK for which they already have repair state (i.e., that has been forwarded either by themselves or a neighbouring PGM network element), and respond with a matching NCF. Constrained RDATA Forwarding Network elements use NAKs to maintain repair state consisting of a list of interfaces upon which a given NAK was received, and they return the corresponding RDATA only on these interfaces. NAK Anticipation If a network element hears an upstream NCF (i.e., on the upstream interface for the distribution tree for the TSI), it establishes repair state without outgoing interfaces in anticipation of responding to and eliminating duplicates of the NAK that may arrive from downstream. 3. Terms and Concepts Before proceeding from the preceding overview to the detail in the sub- sequent Procedures, this section presents some concepts and definitions that make that detail more intelligible. 3.1. Transport Session Identifiers Every PGM packet is identified by a: TSI transport session identifier TSIs must be globally unique, and only one source at a time may act as the source for a transport session. (Note that repairers do not change the TSI in any RDATA they transmit). TSIs are composed of the concate- nation of a globally unique source identifier (GSI) and a source- assigned data-source port. Since all PGM packets originated by receivers are in response to PGM packets originated by a source, receivers simply echo the TSI heard from the source in any corresponding packets they originate. Since all PGM packets originated by network elements are in response to PGM packets originated by a receiver, network elements simply echo the Speakman et al. [Page 11] INTERNET-DRAFT PGM Specification 10 April 2000 TSI heard from the receiver in any corresponding packets they originate. 3.2. Sequence Numbers PGM uses a circular sequence number space from 0 through ((2**32) - 1) to identify and order ODATA packets. Sources must number ODATA packets in unit increments in the order in which the corresponding application data is submitted for transmission. Within a transmit or receive window (defined below), a sequence number x is "less" or "older" than sequence number y if it numbers an ODATA packet preceding ODATA packet y, and a sequence number y is "greater" or "more recent" than sequence number x if it numbers an ODATA packet subsequent to ODATA packet x. 3.3. Transmit Window The description of the operation of PGM rests fundamentally on the definition of the source-maintained transmit window. This definition in turn is derived directly from the amount of transmitted data (in seconds) a source retains for repair (TXW_SECS), and the maximum transmit rate (in bytes/second) maintained by a source to regulate its bandwidth utilization (TXW_MAX_RTE). The size of the transmit window in seconds is simply TXW_SECS. The size of the transmit window in bytes (TXW_BYTES) is (TXW_MAX_RTE * TXW_SECS). The size of the transmit window in sequence numbers (TXW_SQNS) is (TXW_BYTES / bytes-per-packet). In terms of sequence numbers, the transmit window is the range of sequence numbers consumed by the source for sequentially numbering and transmitting the most recent TXW_SECS of ODATA packets. The trailing (or left) edge of the transmit window (TXW_TRAIL) is defined as the sequence number of the oldest data packet available for repair from a source. The leading (or right) edge of the transmit window (TXW_LEAD) is defined as the sequence number of the most recent data packet a source has transmitted. The size of the transmit window in sequence numbers (TXW_SQNS) (i.e., the difference between the leading and trailing edges plus one) must be no greater than half the PGM sequence number space less one. When TXW_TRAIL is equal to TXW_LEAD, the transmit window size is one. When TXW_TRIAL is equal to TXW_LEAD plus one, the transmit window size is empty. NOTA BENE: The concept of and all references to the increment window (TXW_INC) and the window increment (TXW_ADV_SECS) throughout this document are for illustrative purposes only. They provide the shorthand with which to describe the concept Speakman et al. [Page 12] INTERNET-DRAFT PGM Specification 10 April 2000 of advancing the transmit window without also implying any particular implementation or policy of advancement. The fraction of the transmit window size (in seconds of data) by which the transmit window is advanced (TXW_ADV_SECS) is called the window increment. The trailing (oldest) such fraction of the transmit window itself is called the increment window. In terms of sequence numbers, the increment window is the range of sequence numbers that will be the first to be expired from the transmit window. The trailing (or left) edge of the increment window is just TXW_TRAIL, the trailing (or left) edge of the transmit window. The leading (or right) edge of the increment window (TXW_INC) is defined as one less than the sequence number of the first data packet transmitted by the source TXW_ADV_SECS after transmitting TXW_TRAIL. A data packet is described as being "in" the transmit or increment win- dow, respectively, if its sequence number is in the range defined by the transmit or increment window, respectively. The transmit window is advanced across the increment window by the source when it increments TXW_TRAIL to TXW_INC. When the transmit win- dow is advanced across the increment window, the increment window is emptied (i.e., TXW_TRAIL is momentarily equal to TXW_INC), begins to refill immediately as transmission proceeds, is full again TXW_ADV_SECS later (i.e., TXW_TRAIL is separated from TXW_INC by TXW_ADV_SECS of data), at which point the transmit window is advanced again, and so on. 3.4. Receive Window The receive window at the receivers is determined entirely by PGM pack- ets from the source. That is, a receiver simply obeys what the source tells it in terms of window state and advancement. For a given transport session identified by a TSI, a receiver maintains: RXW_TRAIL the sequence number defining the trailing edge of the receive window, the sequence number (known from data packets and SPMs) of the oldest data packet available for repair from the source RXW_LEAD the sequence number defining the leading edge of the receive window, the greatest sequence number of any received data packet within the transmit window The receive window is the range of sequence numbers a receiver is expected to use to identify receivable ODATA. Speakman et al. [Page 13] INTERNET-DRAFT PGM Specification 10 April 2000 A data packet is described as being "in" the receive window if its sequence number is in the receive window. The receive window is advanced by the receiver when it receives an SPM or ODATA packet within the transmit window that increments RXW_TRAIL. Receivers also advance their receive windows upon receipt of any PGM data packet within the receive window that advances the receive window. 3.5. Source Path State To establish the repair state required to constrain RDATA, it's essen- tial that NAKs return from a receiver to a source on the reverse of the distribution tree from the source. That is, they must return through the same sequence of PGM network elements through which the ODATA was forwarded, but in reverse. There are two reasons for this, the less obvious one being by far the more important. The first and obvious reason is that RDATA is forwarded on the same path as ODATA and so repair state must be established on this path if it is to constrain the propagation of RDATA. The second and less obvious reason is that in the absence of repair state, PGM network elements do NOT forward RDATA, so the default behaviour is to discard repairs. If repair state is not properly esta- blished for interfaces on which ODATA went missing, then receivers on those interfaces will continue to NAK for lost data and ultimately experience unrecoverable data loss. The principle function of SPMs is to provide the source path state required for PGM network elements to forward NAKs from one PGM network element to the next on the reverse of the distribution tree for the TSI, establishing repair state each step of the way. This source path state is simply the address of the upstream PGM network element on the reverse of the distribution tree for the TSI. That upstream PGM network element may be more than one subnet hop away. SPMs establish the identity of the upstream PGM network element on the distribution tree for each TSI in each group in each PGM network element, a sort of virtual PGM topol- ogy. So although NAKs are unicast addressed, they are NOT unicast routed by PGM network elements in the conventional sense. Instead PGM network elements use the source path state established by SPMs to direct NAKs PGM-hop-by-PGM-hop toward the source. The idea is to constrain NAKs to the pure PGM topology spanning the more heterogeneous underlying topology of both PGM and non-PGM network elements. The result is repair state in every PGM network element between the receiver and the source so that the corresponding RDATA is never dis- carded by a PGM network element for lack of repair state. Speakman et al. [Page 14] INTERNET-DRAFT PGM Specification 10 April 2000 SPMs also maintain transmit window state in receivers by advertising the trailing and leading edges of the transmit window (SPM_TRAIL and SPM_LEAD). In the absence of data, SPMs may be used to close the transmit window in time by advancing the transmit window until SPM_TRAIL and SPM_LEAD are equal. 3.6. Packet Contents This section just provides enough short-hand to make the Procedures intelligible. For the full details of packet contents, please refer to Packet Formats below. 3.6.1. Source Path Messages 3.6.1.1. SPMs SPMs are transmitted by sources to establish source-path state in PGM network elements, and to provide transmit-window state in receivers. SPMs are multicast to the group and contain: SPM_TSI the source-assigned TSI for the session to which the SPM corresponds SPM_SQN a sequence number assigned sequentially by the source in unit increments and scoped by SPM_TSI NOTA BENE: this is an entirely separate sequence than is used to number ODATA and RDATA. SPM_TRAIL the sequence number defining the trailing edge of the source's transmit window (TXW_TRAIL) SPM_LEAD the sequence number defining the leading edge of the source's transmit window (TXW_LEAD) SPM_PATH the network-layer address (NLA) of the interface on the PGM network element on which the SPM is forwarded 3.6.2. Data Packets 3.6.2.1. ODATA - Original Data ODATA packets are transmitted by sources to send application data to receivers. ODATA packets are multicast to the group and contain: Speakman et al. [Page 15] INTERNET-DRAFT PGM Specification 10 April 2000 OD_TSI the globally unique source-assigned TSI OD_TRAIL the sequence number defining the trailing edge of the source's transmit window (TXW_TRAIL) OD_TRAIL makes the protocol more robust in the face of lost SPMs. By including the trailing edge of the transmit window on every data packet, receivers that have missed any SPMs that advanced the transmit window can still detect the case, recover the application, and potentially resynchronize to the transport session. OD_SQN a sequence number assigned sequentially by the source in unit increments and scoped by OD_TSI 3.6.2.2. RDATA - Repair Data RDATA packets are repair packets transmitted by sources or DLRs in response to NAKs. RDATA packets are multicast to the group and contain: RD_TSI OD_TSI of the ODATA packet for which this is a repair RD_TRAIL the sequence number defining the trailing edge of the source's transmit window (TXW_TRAIL), not necessarily the same as OD_TRAIL of the ODATA packet for which this is a repair RD_SQN OD_SQN of the ODATA packet for which this is a repair 3.6.3. Negative Acknowledgements 3.6.3.1. NAKs - Negative Acknowledgments NAKs are transmitted by receivers to request repairs for missing data packets. NAKs are unicast (PGM-hop-by-PGM-hop) to the source and contain: NAK_TSI OD_TSI of the ODATA packet for which a repair is requested NAK_SQN OD_SQN of the ODATA packet for which a repair is requested NAK_SRC the unicast NLA of the original source of the missing ODATA. Speakman et al. [Page 16] INTERNET-DRAFT PGM Specification 10 April 2000 NAK_GRP the multicast group NLA 3.6.3.2. NNAKs - Null Negative Acknowledgments NNAKs are transmitted by a DLR that receives NAKs redirected to it by either receivers or network elements to provide flow-control feed-back to a source. NNAKs are unicast (PGM-hop-by-PGM-hop) to the source and contain: NNAK_TSI NAK_TSI of the corresponding re-directed NAK. NNAK_SQN NAK_SQN of the corresponding re-directed NAK. NNAK_SRC NAK_SRC of the corresponding re-directed NAK. NNAK_GRP NAK_GRP of the corresponding re-directed NAK. 3.6.4. Negative Acknowledgement Confirmations 3.6.4.1. NCFs - NAK confirmations NCFs are transmitted by network elements and sources in response to NAKs. NCFs are multicast to the group and contain: NCF_TSI NAK_TSI of the NAK being confirmed NCF_SQN NAK_SQN of the NAK being confirmed NCF_SRC NAK_SRC of the NAK being confirmed NCF_GRP NAK_GRP of the NAK being confirmed 3.6.5. Option Encodings OPT_FRAGMENT - Fragmentation OPT_NAK_LIST - List of NAK entries OPT_JOIN - Late Joining OPT_REDIRECT - Redirect OPT_SYN - Synchronisation OPT_FIN - Session Finish Speakman et al. [Page 17] INTERNET-DRAFT PGM Specification 10 April 2000 OPT_RST - Session Reset OPT_PARITY_PRM - Forward Error Correction Parameters OPT_PARITY_GRP - Forward Error Correction Group Number OPT_CURR_TGSIZE - Forward Error Correction Group Size OPT_CR - Congestion Report OPT_CRQST - Congestion Report Request OPT_NAK_BO_IVL - NAK Back-Off Interval OPT_NAK_BO_RNG - NAK Back-Off Range OPT_NBR_UNREACH - Neighbor Unreachable OPT_PATH_NLA - Path NLA OPT_INVALID - Option invalidated Speakman et al. [Page 18] INTERNET-DRAFT PGM Specification 10 April 2000 4. Procedures - General Since SPMs, NCFs, and RDATA must be treated conditionally by PGM network elements, they must be distinguished from other packets in the chosen multicast network protocol if PGM network elements are to extract them from the usual switching path. The most obvious way for network elements to achieve this is to examine every packet in the network for the PGM transport protocol and packet types. However, the overhead of this approach is costly for high- performance, multi-protocol network elements. An alternative, and a requirement for PGM over IP multicast, is that SPMs, NCFs, and RDATA must be transmitted with the IP Router Alert Option [6]. This option gives network elements a network-layer indication that a packet should be extracted from IP switching for more detailed processing. 5. Procedures - Sources 5.1. Data Transmission Since PGM relies on a purely rate-limited transmission strategy in the source to bound the bandwidth consumed by PGM transport sessions, an assortment of techniques is assembled here to make that strategy as con- servative and robust as possible. These techniques are the minimum required of a PGM source, and others may be added as experience dic- tates. 5.1.1. Maximum Cumulative Transmit Rate A source must number ODATA packets in the order in which they are sub- mitted for transmission by the application. A source must transmit ODATA packets in sequence and only within the transmit window beginning with TXW_TRAIL at no greater a rate than TXW_MAX_RTE. TXW_MAX_RTE is typically the maximum cumulative transmit rate of SPM, ODATA, and RDATA. Different transmission strategies may define TXW_MAX_RTE as appropriate for the implementation. 5.1.2. Transmit Rate Regulation To regulate its transmit rate, a source must use a token bucket scheme or any other traffic management scheme that yields equivalent behaviour. A token bucket [7] is characterized by a continually sustainable data rate (the token rate) and the extent to which the data rate may exceed the token rate for short periods of time (the token bucket size). Over any arbitrarily chosen interval, the number of bytes the source may transmit cannot exceed the token bucket size plus the product of the token rate and the chosen interval. Speakman et al. [Page 19] INTERNET-DRAFT PGM Specification 10 April 2000 In addition, a source must bound the maximum rate at which successive packets may be transmitted using a leaky bucket scheme drained at a max- imum transmit rate, or equivalent mechanism. 5.1.3. Outgoing Packet Ordering To preserve the logic of PGM's transmit window, a source should imple- ment strict priority queueing of pending SPMs, pending RDATA, and pend- ing ODATA from three separate queues in that order, or implement any mechanism that results in equivalent behaviour. In the interest of sup- porting specific application requirements for timely delivery of ODATA, a source may schedule ODATA and RDATA so as to achieve weighted bandwidth sharing between the two rather than strict priority of RDATA over ODATA. 5.1.4. Ambient SPMs Interleaved with ODATA and RDATA, a source must transmit SPMs at a rate at least sufficient to maintain current source path state in PGM network elements. Note that source path state in network elements does not track underlying changes in the distribution tree from a source until an SPM traverses the altered distribution tree. The consequence is that NAKs may go unconfirmed both at receivers and amongst network elements while changes in the underlying distribution tree take place. 5.1.5. Heartbeat SPMs In the absence of data to transmit, a source should transmit SPMs at a decaying rate in order to assist early detection of lost data, to main- tain current source path state in PGM network elements, and to maintain current receive window state in the receivers. In this scheme [8], a source maintains an inter-heartbeat timer IHB_TMR which times the interval between the most recent packet (ODATA, RDATA, or SPM) transmission and the next heartbeat transmission. IHB_TMR is initialized to a minimum interval IHB_MIN after the transmission of any data packet. If IHB_TMR expires, the source transmits a heartbeat SPM and initializes IHB_TMR to double its previous value. The transmission of consecutive heartbeat SPMs doubles IHB each time up to a maximum interval IHB_MAX. The transmission of any data packet initializes IHB_TMR to IHB_MIN once again. The effect is to provoke prompt detec- tion of missing packets in the absence of data to transmit, and to do so with minimal bandwidth overhead. 5.1.6. Ambient and Heartbeat SPMs Ambient and heartbeat SPMs are described as driven by separate timers in this specification to highlight their contrasting functions. Ambient Speakman et al. [Page 20] INTERNET-DRAFT PGM Specification 10 April 2000 SPMs are driven by a count-down timer that expires regularly while heartbeat SPMs are driven by a count-down timer that keeps being reset by data, and the interval of which changes once it begins to expire. The ambient SPM timer is just counting down in real-time while the heartbeat timer is measuring the inter-data-packet interval. In the presence of data, no heartbeat SPMs will be transmitted since the transmission of data keeps setting the IHB_TMR back to its initial value. At the same time however, ambient SPMs must be interleaved into the data as a matter of course, not necessarily as a heartbeat mechan- ism. This ambient transmission of SPMs is required to keep the distri- bution tree information in the network current and to allow new receivers to synchronize with the session. An implementation should de-couple ambient and heartbeat SPM timers suf- ficiently to permit them to be configured independently of each other. 5.2. Negative Acknowledgement Confirmation A source must immediately multicast an NCF in response to any NAK it receives. The NCF is required since the alternative of responding immediately with RDATA would not allow other PGM network elements on the same subnet to do NAK anticipation, nor would it allow DLRs on the same subnet to provide repairs. The generation of NCFs should be rate- limited to protect against a denial of service in the presence of a NAK storm. 5.3. Repairs A source must then multicast RDATA (while respecting TXW_MAX_RTE) in response to any NAK it receives for data packets within the transmit window. A source should transmit RDATA at priority over concurrent ODATA. The effect of this priority is to back off the transmission of ODATA in favour of RDATA. In the interest of increasing the efficiency of a particular RDATA packet, a source may delay RDATA transmission to accommodate the arrival of NAKs from the whole loss neighbourhood. In addition, a source may delay the retransmission of recently transmitted RDATA to allow for the propagation of RDATA to the whole loss neighbourhood. In either case, this delay should not exceed twice the greatest propagation delay in the loss neighbourhood. 5.4. Transmit Window Advance 5.4.1. Advancing across the Increment Window In anticipation of advancing the transmit window, the source starts a Speakman et al. [Page 21] INTERNET-DRAFT PGM Specification 10 April 2000 timer TXW_ADV_IVL_TMR which runs for time period TXW_ADV_IVL. TXW_ADV_IVL has a value in the range (0, TXW_ADV_SECS). The value may be configurable or may be determined statically by the strategy used for advancing the transmit window. When TXW_ADV_IVL_TMR is running, a source may reset TXW_ADV_IVL_TMR if NAKs are received for packets in the increment window. In addition, a source may transmit RDATA in the increment window with priority over other data within the transmit window. When TXW_ADV_IVL_TMR expires, a source should advance the trailing edge of the transmit window from TXW_TRAIL to TXW_INC. Once the transmit window is advanced across the increment window, SPM_TRAIL, OD_TRAIL and RD_TRAIL are set to the new value of TXW_TRAIL in all subsequent transmitted packets, until the next window advance- ment. PGM does not constrain the strategies that a source may use for advanc- ing the transmit window. The source may implement any scheme or number of schemes. Three suggested strategies are outlined in Appendix F. 6. Procedures - Receivers 6.1. Data Reception Initial data reception A receiver should initiate data reception beginning with the first data packet it receives within the advertised transmit window. This packet's sequence number (ODATA_SQN) temporarily defines the trailing edge of the transmit window from the receiver's perspective. That is, it is assigned to RXW_TRAIL_INIT within the receiver, and until the trailing edge sequence number advertised in subsequent packets (SPMs or ODATA or RDATA) increments through RXW_TRAIL_INIT, the receiver must only request repairs for sequence numbers subsequent to RXW_TRAIL_INIT. Thereafter, it may request repairs anywhere in the transmit window. This temporary restriction on repair requests prevents receivers from requesting a potentially large amount of history when they first begin to receive a given PGM transport session. Note that the JOIN option, discussed later, may be used to provide a different value for RXW_TRAIL_INIT. Receiving and discarding data packets Within a given transport session, a receiver must receive any ODATA or RDATA packets within the receive window. A receiver must discard any Speakman et al. [Page 22] INTERNET-DRAFT PGM Specification 10 April 2000 data packet that duplicates one already received in the transmit window. A receiver must discard any data packet outside of the receive window. Contiguous data Contiguous data is comprised of those data packets within the receive window that have been received and are in the range from RXW_TRAIL up to (but not including) the first missing sequence number in the receive window. The most recently received data packet of contiguous data defines the leading edge of contiguous data. As its default mode of operation, a receiver must deliver only contigu- ous data packets to the application, and it must do so in the order defined by those data packets' sequence numbers. This provides applica- tions with a reliable ordered data flow. Non contiguous data PGM receiver implementations may optionally provide a mode of operation in which data is delivered to an application in the order received. However, the implementation must only deliver complete application pro- tocol data units (APDUs) to the application. That is, APDUs that have been fragmented into different TPDUs must be reassembled before delivery to the application. 6.2. Source Path Messages Receivers must receive and sequence SPMs for any TSI they are receiving. An SPM is in sequence if its sequence number is greater than that of the most recent in-sequence SPM and within half the PGM number space. Out- of-sequence SPMs must be discarded. For each TSI, receivers must use the most recent SPM to determine the NLA of the upstream PGM network element for use in NAK addressing. Note that a receiver cannot initiate repair requests until it has received at least one SPM for the corresponding TSI. Since SPMs require per-hop processing, it is likely that they will be forwarded at a slower rate than data, and that they will arrive out of sync with the data stream. In this case, the window information that the SPMs carry will be out of date. Receivers should expect this to be the case and should detect it by comparing the packet lead and trail values with the values the receivers have stored for lead and trail. If the SPM packet values are less, they should be ignored, but the rest of the packet should be processed as normal. Speakman et al. [Page 23] INTERNET-DRAFT PGM Specification 10 April 2000 6.3. Data Recovery by Negative Acknowledgement Detecting missing data packets Receivers must detect gaps in the expected data sequence in the follow- ing manners: by comparing the sequence number on the most recently received ODATA or RDATA packet with the leading edge of contiguous data by comparing SPM_LEAD of the most recently received SPM with the leading edge of contiguous data In both cases, if the receiver has not received all intervening data packets, it may initiate selective NAK generation for each missing sequence number. In addition, a receiver may detect a single missing data packet by receiving an NCF or multicast NAK for a data packet within the transmit window which it has not received. In this case it may initiate selec- tive NAK generation for the said sequence number. In all cases, receivers should temper the initiation of NAK generation to account for simple mis-ordering introduced by the network. A possi- ble mechanism to achieve this is to assume loss only after the reception of N packets with sequence numbers higher than those of the (assumed) lost packets. A possible value for N is 2. This method should be com- plemented with a timeout based mechanism that handles the loss of the last packet before a pause in the transmission of the data stream. The leading edge field in SPMs should also be taken into account in the loss detection algorithm. Generating NAKs NAK generation follows the detection of a missing data packet and is the cycle of: waiting for a random period of time (NAK_RB_IVL) while listening for matching NCFs or NAKs transmitting a NAK if a matching NCF or NAK is not heard waiting a period (NAK_RPT_IVL) for a matching NCF and recommencing NAK generation if the matching NCF is not received waiting a period (NAK_RDATA_IVL) for data and recommencing NAK gen- eration if the matching data is not received Speakman et al. [Page 24] INTERNET-DRAFT PGM Specification 10 April 2000 The entire generation process can be summarised by the following state machine: | | detect missing tpdu | - reset data retry count | - reset NCF retry count V matching NCF |--------------------------| <---------------| BACK-OFF_STATE | <---------------------- | | start timer(NAK_RB_IVL) | ^ ^ | | | | | | |--------------------------| | | | matching | | timer expires | | | NAK | | - send NAK | | | | | | | | V V | | | |--------------------------| | | | | WAIT_NCF_STATE | | | | matching NCF | start timer(NAK_RPT_IVL) | | | |<--------------| |------------> | | |--------------------------| timer expires | | | | ^ | | NAK_NCF_RETRIES | | | | | exceeded | | | | | V ----------- | | Cancellation matching NAK | | - restart timer(NAK_RPT_IVL) | | | | | V |--------------------------| | --------------->| WAIT_DATA_STATE |-----------------------> |start timer(NAK_RDATA_IVL)| timer expires | | |--------------------------| | | ^ NAK_DATA_RETRIES | | | exceeded | | | | ----------- | matching NCF or NAK V - restart timer(NAK_RDATA_IVL) Cancellation In any state, receipt of matching RDATA or ODATA completes data recovery and successful exit from the state machine. State transition stops any running timers. Speakman et al. [Page 25] INTERNET-DRAFT PGM Specification 10 April 2000 In any state, if the trailing edge of the window moves beyond the sequence number, data recovery for that sequence number terminates. During NAK_RB_IVL a NAK is said to be pending. When awaiting data or an NCF, a NAK is said to be outstanding. Backing off NAK transmission Before transmitting a NAK, a receiver must wait some interval NAK_RB_IVL chosen randomly over some time period NAK_BO_IVL. During this period, receipt of a matching NAK or a matching NCF will suspend NAK generation. NAK_RB_IVL is counted down from the time a missing data packet is detected. When a parity NAK (Appendix A, FEC) is being generated, the back-off interval should be inversely biased with respect to the number of parity packets requested. This way NAKs requesting larger numbers of parity packets are likely to be sent first and thus suppress other NAKs. A NAK for a given transmission group suppresses another NAK for the same transmission group only if it is requesting an equal or larger number of parity packets. When a receiver has to transmit a sequence of NAKs, it should transmit the NAKs in order from oldest to newest. Suspending NAK generation Suspending NAK generation just means waiting for either NAK_RB_IVL, NAK_RPT_IVL or NAK_RDATA_IVL to pass. A receiver must suspend NAK gen- eration if a duplicate of the NAK is already pending from this receiver or the NAK already outstanding from this or another receiver. NAK suppression A receiver must suppress NAK generation and wait at least NAK_RDATA_IVL before recommencing NAK generation if it hears a matching NCF or NAK during NAK_RB_IVL. A matching NCF must match NCF_TSI with NAK_TSI, and NCF_SQN with NAK_SQN. Transmitting a NAK Upon expiry of NAK_RB_IVL, a receiver must unicast a NAK to the upstream PGM network element for the TSI specifying the transport session iden- tifier and missing sequence number. In addition, it may optionally mul- ticast a NAK with TTL of 1 to the group. It also records both the address of the source of the corresponding ODATA and the address of the group in the NAK header. Speakman et al. [Page 26] INTERNET-DRAFT PGM Specification 10 April 2000 It must repeat the NAK at a rate governed by NAK_RPT_IVL up to NAK_NCF_RETRIES times while waiting for a matching NCF. It must then wait NAK_RDATA_IVL before recommencing NAK generation. If it hears a matching NCF or NAK during NAK_RDATA_IVL, it must wait anew for NAK_RDATA_IVL before recommencing NAK generation (i.e. matching NCFs and NAKs restart NAK_RDATA_IVL). Completion of NAK generation NAK generation is complete only upon the receipt of the matching RDATA (or even ODATA) packet at any time during NAK generation. Cancellation of NAK generation NAK generation is cancelled upon the advancing of the receive window so as to exclude the matching sequence number of a pending or outstanding NAK, or NAK_DATA_RETRIES / NAK_NCF_RETRIES being exceeded. Cancellation of NAK generation indicates unrecoverable data loss. Receiving NCFs and multicast NAKs A receiver must discard any NCFs or NAKs it hears for data packets out- side the transmit window or for data packets it has received. Otherwise they are treated as appropriate for the current repair state. 7. Procedures - Network Elements 7.1. Source Path State Upon receipt of an in-sequence SPM, a network element records the Source Path Address SPM_PATH with the multicast routing information for the TSI. If the receiving network element is on the same subnet as the for- warding network element, this address will be the same as the address of the immediately upstream network element on the distribution tree for the TSI. If, however, non-PGM network elements intervene between the forwarding and the receiving network elements, this address will be the address of the first PGM network element across the intervening network elements. If SPM_PATH is 0, no path information is present in the packet. The network element then forwards the SPM on each outgoing interface for that TSI. As it does so, it encodes the network address of the outgoing interface in SPM_PATH in each copy of the SPM it forwards. However, if the SPM_PATH was 0, it should not be modified. 7.2. NAK Confirmation Network elements must immediately transmit an NCF in response to any Speakman et al. [Page 27] INTERNET-DRAFT PGM Specification 10 April 2000 unicast NAK they receive. The NCF must be multicast to the group on the interface on which the NAK was received. NOTA BENE: In order to avoid creating multicast routing state for PGM network elements across non-PGM-capable clouds, the network-header source address of NCFs transmitted by network elements must be set to the ODATA source's NLA, not the net- work element's NLA as might be expected. The generation of NCFs should be rate-limited to protect against a denial of service in the presence of a NAK storm. Simultaneously, network elements must establish repair state for the NAK if such state does not already exist, and add the interface on which the NAK was received to the corresponding repair interface list if the interface is not already listed. 7.3. Constrained NAK Forwarding The NAK forwarding procedures for network elements are quite similar to those for receivers, but three important differences should be noted. First, network elements do NOT back off before forwarding a NAK (i.e., there is no NAK_BO_IVL) since the resulting delay of the NAK would com- pound with each hop. Note that NAK arrivals will be randomized by the receivers from which they originate, and this factor in conjunction with NAK anticipation and elimination will combine to forestall NAK storms on subnets with a dense network element population. Second, network elements do NOT retry confirmed NAKs (i.e., there is no NAK_GEN_IVL) if RDATA is not seen; they simply discard the repair state and rely on receivers to re-request the repair. This approach keeps the repair state in the network elements relatively ephemeral and responsive to underlying routing changes. Third, note that ODATA does NOT cancel NAK forwarding in network ele- ments since it is switched by network elements without transport-layer intervention. NOTA BENE: Once confirmed by an NCF, network elements discard NAK packets; they are NOT retained in network elements beyond this forwarding operation. NAK forwarding requires that a network element listen to NCFs for the same transport session. NAK forwarding also requires that a network element observe two time out intervals for any given NAK (i.e., per NAK_TSI and NAK_SQN). Speakman et al. [Page 28] INTERNET-DRAFT PGM Specification 10 April 2000 The first, the NAK repeat interval NAK_RPT_IVL, limits the length of time for which a network element will repeat a NAK while waiting for a corresponding NCF. NAK_RPT_IVL is counted down from the transmission of a NAK. Expiry of NAK_RPT_IVL cancels NAK forwarding (due to missing NCF). The second, the NAK RDATA interval NAK_RDATA_IVL, limits the length of time for which a network element will wait for the corresponding RDATA. NAK_RDATA_IVL is counted down from the time a matching NCF is received. Expiry of NAK_RDATA_IVL causes the network element to discard the corresponding repair state (due to missing RDATA). During NAK_RPT_IVL, a NAK is said to be pending. During NAK_RDATA_IVL, a NAK is said to be outstanding. A Network element must forward NAKs only to the upstream PGM network element for the TSI. A network element must repeat a NAK at a rate of NAK_RPT_RTE for an interval of NAK_RPT_IVL until it receives a matching NCF. A matching NCF must match NCF_TSI with NAK_TSI, and NCF_SQN with NAK_SQN. Upon reception of the corresponding NCF, network elements must wait at least NAK_RDATA_IVL for the corresponding RDATA. Receipt of the corresponding RDATA at any time during NAK forwarding cancels NAK for- warding and tears down the corresponding repair state in the network element. 7.4. NAK elimination Two NAKs duplicate each other if they bear the same NAK_TSI and NAK_SQN. Network elements must discard all duplicates of a NAK that is pending. Once a NAK is outstanding, network elements must discard all duplicates of that NAK for NAK_ELIM_IVL. Upon expiry of NAK_ELIM_IVL, network ele- ments must suspend NAK elimination for that TSI/SQN until the first duplicate of that NAK is seen after the expiry of NAK_ELIM_IVL. This duplicate must be forwarded in the usual manner. Once this duplicate NAK is outstanding, network elements must once again discard all dupli- cates of that NAK for NAK_ELIM_IVL, and so on. NAK_RDATA_IVL must be reset each time a NAK for the corresponding TSI/SQN is confirmed (i.e., each time NAK_ELIM_IVL is reset). NAK_ELIM_IVL must be some small frac- tion of NAK_RDATA_IVL. NAK_ELIM_IVL acts to balance implosion prevention against repair state liveness. That is, it results in the elimination of all but at most one NAK per NAK_ELIM_IVL thereby allowing repeated NAKs to keep the repair state alive in the PGM network elements. Speakman et al. [Page 29] INTERNET-DRAFT PGM Specification 10 April 2000 7.5. NAK Anticipation An unsolicited NCF is one that is received by a network element when the network element has no corresponding pending or outstanding NAK. Net- work elements must process unsolicited NCFs differently depending on the interface on which they are received. If the interface on which an NCF is received is the same interface the network element would use to reach the upstream PGM network element, the network element simply establishes repair state for NCF_TSI and NCF_SQN without adding the interface to the repair interface list, and discards the NCF. If the repair state already exists, the network element res- tarts the NAK_RDATA and NAK_ELIM_IVL timers and discards the NCF. If the interface on which an NCF is received is not the same interface the network element would use to reach the upstream PGM network element, the network element does not establish repair state and just discards the NCF. Anticipated NAKs permit the elimination of any subsequent matching NAKs from downstream. Upon establishing anticipated repair state, network elements must eliminate subsequent NAKs only for a period of NAK_ELIM_IVL. Upon expiry of NAK_ELIM_IVL, network elements must suspend NAK elimination for that TSI/SQN until the first duplicate of that NAK is seen after the expiry of NAK_ELIM_IVL. This duplicate must be forwarded in the usual manner. Once this duplicate NAK is outstand- ing, network elements must once again discard all duplicates of that NAK for NAK_ELIM_IVL, and so on. NAK_RDATA_IVL must be reset each time a NAK for the corresponding TSI/SQN is confirmed (i.e., each time NAK_ELIM_IVL is reset). NAK_ELIM_IVL must be some small fraction of NAK_RDATA_IVL. 7.6. NAK Shedding Network elments may implement local procedures for withholding NAK con- firmations for receivers detected to be reporting excessive loss. The result of these procedures would ultimately be unrecoverable data loss in the receiver. 7.7. Addressing NAKs A PGM network element uses the source and group addresses (NLAs) con- tained in the transport header to find the state for the corresponding TSI, looks up the corresponding upstream PGM network element's address, uses it to re-address the (unicast) NAK, and unicasts it on the upstream interface for the distribution tree for the TSI. Speakman et al. [Page 30] INTERNET-DRAFT PGM Specification 10 April 2000 7.8. Constrained RDATA Forwarding Network elements must maintain repair state for each interface on which a given NAK is received at least once. Network elements must then use this list of interfaces to constrain the forwarding of the corresponding RDATA packet only to those interfaces in the list. An RDATA packet corresponds to a NAK if it matches NAK_TSI and NAK_SQN. Network elements must maintain this repair state only until either the corresponding RDATA is received and forwarded, or NAK_RDATA_IVL passes after forwarding the most recent instance of a given NAK. Thereafter, the corresponding repair state must be discarded. Network elements should discard and not forward RDATA packets for which they have no repair state. Note that the consequence of this procedure is that, while it constrains repairs to the interested sub-set of the network, loss of repair state precipitates further NAKs from neglected receivers. Speakman et al. [Page 31] INTERNET-DRAFT PGM Specification 10 April 2000 8. Packet Formats All of the packet formats described in this section are transport-layer headers that must immediately follow the network-layer header in the packet. Only data packet headers (ODATA and RDATA) may be followed in the packet by application data. For each packet type, the network- header source and destination addresses are specified in addition to the format and contents of the transport layer header. Recall from General Procedures that, for PGM over IP multicast, SPMs, NCFs, and RDATA must also bear the IP Router Alert Option. For PGM over IP, the IP protocol number is 113. In all packets the descriptions of Data-Source Port, Data-Destination Port, Type, Options, Checksum, Global Source ID (GSI), and Transport Service Data Unit (TSDU) Length are: Data-Source Port: A random port number generated by the source. This port number must be unique within the source. Source Port together with Glo- bal Source ID forms the TSI. Data-Destination Port: A globally well-known port number assigned to the given PGM appli- cation. Type: The high-order two bits of the Type field encode a version number, 0x0 in this instance. The low-order nibble of the type field encodes the specific packet type. The intervening two bits (the low-order two bits of the high-order nibble) are reserved and must be zero. Within the low-order nibble of the Type field: values in the range 0x0 through 0x3 represent SPM-like packets (i.e., session-specific, sourced by a source, periodic), values in the range 0x4 through 0x7 represent DATA-like packets (i.e., data and repairs), values in the range 0x8 through 0xB represent NAK-like packets (i.e., hop-by-hop reliable NAK forwarding procedures), and values in the range 0xC through 0xF represent SPMR-like Speakman et al. [Page 32] INTERNET-DRAFT PGM Specification 10 April 2000 packets (i.e., session-specific, sourced by a receiver, asyn- chronous). Options: This field encodes binary indications of the presence and signifi- cance of any options. It also directly encodes some options. bit 0 set => One or more Option Extensions are present bit 1 set => One or more Options are network-significant Note that this bit is clear when OPT_FRAGMENT and/or OPT_JOIN are the only options present. bit 6 set => Packet is a parity packet for a transmission group of variable sized packets (OPT_VAR_PKTLEN). Only present when OPT_PARITY is also present. bit 7 set => Packet is a parity packet (OPT_PARITY) All the other options (option extensions) are encoded in exten- sions to the PGM header. Checksum: This field is the usual 1's complement of the 1's complement sum of the entire PGM packet including header. The checksum does not include a network-layer pseudo header for compatibility with network address translation. If the computed checksum is zero, it is transmitted as all ones. A value of zero in this field means the transmitter generated no checksum. Note that if any entity between a source and a receiver modifies the PGM header for any reason, it must either recompute the check- sum or clear it. The checksum is mandatory on data packets (ODATA and RDATA). Global Source ID: A globally unique source identifier. This ID must not change throughout the duration of the transport session. A recommended identifier is the low-order 48 bits of the MD5 [9] signature of the DNS name of the source. Global Source ID together with Data- Source Port forms the TSI. TSDU Length: Speakman et al. [Page 33] INTERNET-DRAFT PGM Specification 10 April 2000 The length in octets of the transport data unit exclusive of the transport header. Note that those who require the TPDU length must obtain it from sum of the transport header length (TH) and the TSDU length. TH length is the sum of the size of the particular PGM packet header (type_specific_size) plus the length of any options that might be present. Address Family Indicators (AFIs) are as specified in [10]. Speakman et al. [Page 34] INTERNET-DRAFT PGM Specification 10 April 2000 8.1. Source Path Messages SPMs are sent by a source to establish source path state in network ele- ments and to provide transmit window state to receivers. The network-header source address of an SPM is the unicast NLA of the entity that originates the SPM. The network-header destination address of an SPM is a multicast group NLA. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source Port | Destination Port | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Options | Checksum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Global Source ID ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... Global Source ID | TSDU Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | SPM's Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Trailing Edge Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Leading Edge Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | NLA AFI | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Path NLA ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...-+-+ | Option Extensions when present ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- ... -+-+-+-+-+-+-+-+-+-+-+-+-+-+ Source Port: SPM_SPORT Data-Source Port, together with SPM_GSI forms SPM_TSI Destination Port: SPM_DPORT Data-Destination Port Speakman et al. [Page 35] INTERNET-DRAFT PGM Specification 10 April 2000 Type: SPM_TYPE = 0x00 Global Source ID: SPM_GSI Together with SPM_SPORT forms SPM_TSI SPM's Sequence Number SPM_SQN The sequence number assigned to the SPM by the source. Trailing Edge Sequence Number: SPM_TRAIL The sequence number defining the current trailing edge of the source's transmit window (TXW_TRAIL). Leading Edge Sequence Number: SPM_LEAD The sequence number defining the current leading edge of the source's transmit window (TXW_LEAD). If SMP_TRAIL == 0 and SPM_LEAD == 0x80000000, this indicates that no window information is present in the packet. Path NLA: SPM_PATH The NLA of the interface on the network element on which this SPM was forwarded. Initialized by a source to the source's NLA, rewritten by each PGM network element upon forwarding. SPM_PATH may have a value of 0, indicating that no path informa- tion is present in the SPM. If the field is 0, it should not be modified by network elements when they forward the SPM. Speakman et al. [Page 36] INTERNET-DRAFT PGM Specification 10 April 2000 8.2. Data Packets Data packets carry application data from a source or a repairer to receivers. ODATA: Original data packets transmitted by a source. RDATA: Repairs transmitted by a source or by a designated local repairer (DLR) in response to a NAK. The network-header source address of a data packet is the unicast NLA of the entity that originates the data packet. The network-header destination address of a data packet is a multicast group NLA. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source Port | Destination Port | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Options | Checksum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Global Source ID ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... Global Source ID | TSDU Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Data Packet Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Trailing Edge Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Extensions when present ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- ... -+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Data ... +-+-+- ... Source Port: OD_SPORT, RD_SPORT Data-Source Port, together with Global Source ID forms: OD_TSI, RD_TSI Speakman et al. [Page 37] INTERNET-DRAFT PGM Specification 10 April 2000 Destination Port: OD_DPORT, RD_DPORT Data-Destination Port Type: OD_TYPE = 0x04 RD_TYPE = 0x05 Global Source ID: OD_GSI, RD_GSI Together with Source Port forms: OD_TSI, RD_TSI Data Packet Sequence Number: OD_SQN, RD_SQN The sequence number originally assigned to the ODATA packet by the source. Trailing Edge Sequence Number: OD_TRAIL, RD_TRAIL The sequence number defining the current trailing edge of the source's transmit window (TXW_TRAIL). In RDATA, this may not be the same as OD_TRAIL of the ODATA packet for which it is a repair. Data: Application data. Speakman et al. [Page 38] INTERNET-DRAFT PGM Specification 10 April 2000 8.3. Negative Acknowledgements and Confirmations NAK: Negative Acknowledgements are sent by receivers to request the repair of an ODATA packet detected to be missing from the expected sequence. N-NAK: Null Negative Acknowledgements are sent by DLRs to provide flow control feedback to the source of ODATA for which the DLR has pro- vided the corresponding RDATA. The network-header source address of a NAK is the unicast NLA of the entity that originates the NAK. The network-header source address of NAK is rewritten by each PGM network element with its own. The network-header destination address of a NAK is initialized by the originator of the NAK (a receiver) to the unicast NLA of the upstream PGM network element known from SPMs. The network-header destination address of a NAK is rewritten by each PGM network element with the uni- cast NLA of the upstream PGM network element to which this NAK is for- warded. On the final hop, the network-header destination address of a NAK is rewritten by the PGM network element with the unicast NLA of the original source or the unicast NLA of a DLR. NCF: NAK Confirmations are sent by network elements and sources to con- firm the receipt of a NAK. The network-header source address of an NCF is the ODATA source's NLA, not the network element's NLA as might be expected. The network-header destination address of an NCF is a multicast group NLA. Note that in NAKs and N-NAKs, unlike the other packets, the field SPORT contains the Data-Destination port and the field DPORT contains the Data-Source port. As a general rule, the content of SPORT/DPORT is determined by the direction of the flow: in packets which travel down- stream SPORT is the port number chosen in the data source (Data-Source Port) and DPORT is the data destination port number (Data-Destination Port). The opposite holds for packets which travel upstream. This makes DPORT the protocol endpoint in the recipient host, regardless of the direction of the packet. Speakman et al. [Page 39] INTERNET-DRAFT PGM Specification 10 April 2000 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source Port | Destination Port | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Options | Checksum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Global Source ID ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... Global Source ID | TSDU Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Requested Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | NLA AFI | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source NLA ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...-+-+ | NLA AFI | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multicast Group NLA ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...-+-+ | Option Extensions when present ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- ... Source Port: NAK_SPORT, NNAK_SPORT Data-Destination Port NCF_SPORT Data-Source Port, together with Global Source ID forms NCF_TSI Destination Port: NAK_DPORT, NNAK_DPORT Data-Source Port, together with Global Source ID forms: NAK_TSI, NNAK_TSI NCF_DPORT Data-Destination Port Speakman et al. [Page 40] INTERNET-DRAFT PGM Specification 10 April 2000 Type: NAK_TYPE = 0x08 NNAK_TYPE = 0x09 NCF_TYPE = 0x0A Global Source ID: NAK_GSI, NNAK_GSI, NCF_GSI Together with Data-Source Port forms NAK_TSI, NNAK_TSI, NCF_TSI Requested Sequence Number: NAK_SQN, NNAK_SQN NAK_SQN is the sequence number of the ODATA packet for which a repair is requested. NNAK_SQN is the sequence number of the RDATA packet for which a repair has been provided by a DLR. NCF_SQN NCF_SQN is NAK_SQN from the NAK being confirmed. Source NLA: NAK_SRC, NNAK_SRC, NCF_SRC The unicast NLA of the original source of the missing ODATA. Multicast Group NLA: NAK_GRP, NNAK_GRP, NCF_GRP The multicast group NLA. NCFs may bear OPT_REDIRECT and/or OPT_NAK_LIST Speakman et al. [Page 41] INTERNET-DRAFT PGM Specification 10 April 2000 9. Options PGM specifies several end-to-end options to address specific application requirements. PGM specifies options to support fragmentation, late joining, and redirection. Options may be appended to PGM data packet headers only by their origi- nal transmitters. While they may be interpreted by network elements, options are neither added nor removed by network elements. Options are all in the TLV style, or Type, Length, Value. The Type field is contained in the first byte, where bit 0 is the OPT_END bit, followed by 7 bits of type. The OPT_END bit must be set in the last option in the option list, whichever that might be. The Length field is the total length of the option in bytes, and directly follows the Type field. Following the Length field are 6 reserved bits plus the 2 Option Extensibility bits OPX. Last are 8 bits designated for option specific information which may be defined on a per-option basis. If not defined for a particular option, they must be set to 0. The Option Extensibility bits dictate the desired treatment of an option if it is unknown to the network element processing it. NOTA BENE: Only network elements pay any attention to these bits. The OPX bits are defined as follows: 0x00 - Ignore the option 0x01 - Invalidate the option by changing the type to OPT_INVALID = 0x7F 0x10 - Discard the packet 0x11 - Unsupported, and reserved for future use There is a limit of 16 options per packet. General Option Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |E| Option Type | Option Length | Reserved |OPX| Opt. Specific | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Value ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...+-+-+ Speakman et al. [Page 42] INTERNET-DRAFT PGM Specification 10 April 2000 9.1. Option extension length - OPT_LENGTH When option extensions are appended to the standard PGM header, the extensions must be preceded by an option extension length field specify- ing the total length of all option extensions. In addition, the presence of the options must be encoded in the Options field of the standard PGM header before the Checksum is computed. All network-significant options must be appended before any exclusively receiver-significant options. To provide an indication of the end of option extensions, OPT_END (0x80) must be set in the Option Type field of the trailing option extension. 9.1.1. OPT_LENGTH - Packet Extension Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Type | Option Length | Total length of all options | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Option Type = 0x00 Option Length = 4 octets Total length of all options The total length in octets of all option extensions including OPT_LENGTH. 9.2. Fragmentation Option - OPT_FRAGMENT Fragmentation allows transport-layer entities at a source to break up application protocol data units (APDUs) into multiple PGM data packets (TPDUs) to conform with the MTU supported by the network layer. The fragmentation option may be applied to ODATA and RDATA packets only. Architecturally, the accumulation of TPDUs into APDUs is applied to TPDUs that have already been received, duplicate eliminated, and con- tiguously sequenced by the receiver. Thus APDUs may be reassembled across increments of the transmit window. 9.2.1. OPT_FRAGMENT - Packet Extension Contents OPT_FRAG_OFF the offset of the fragment from the beginning of the APDU Speakman et al. [Page 43] INTERNET-DRAFT PGM Specification 10 April 2000 OPT_FRAG_LEN the total length of the original APDU 9.2.2. OPT_FRAGMENT - Procedures - Sources A source fragments APDUs into a contiguous series of fragments no larger than the MTU supported by the network layer. A source sequentially and uniquely assigns OD_SQNs to these fragments in the order in which they occur in the APDU. A source then sets OPT_FRAG_OFF to the value of the offset of the fragment in the original APDU (where the first byte of the APDU is at offset 0, and OPT_FRAG_OFF numbers the first byte in the fragment), and set OPT_FRAG_LEN to the value of the total length of the original APDU. 9.2.3. OPT_FRAGMENT - Procedures - Receivers Receivers detect and accumulate fragmented packets until they have received an entire contiguous sequence of packets comprising an APDU. This sequence begins with the fragment bearing OPT_FRAG_OFF of 0, and terminates with the fragment whose length added to its OPT_FRAG_OFF is OPT_FRAG_LEN. 9.2.4. OPT_FRAGMENT - Procedures - Network Elements This option is not network-significant. 9.2.5. OPT_FRAGMENT - Packet Extension Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Type | Option Length | Reserved |OPX| | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Offset | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Option Type = 0x01 Option Length = 12 octets Offset The offset of the fragment from the beginning of the APDU (OPT_FRAG_OFF). Length Speakman et al. [Page 44] INTERNET-DRAFT PGM Specification 10 April 2000 The total length of the original APDU (OPT_FRAG_LEN). 9.3. NAK List Option - OPT_NAK_LIST The NAK List option may be used in conjunction with NAKs to allow receivers to request transmission for more than one sequence number with a single NAK packet. The option is limited to 64 listed NAK entries. The NAK list must be unique and duplicate free. It must be ordered, and must consist of either a list of selective or a list of parity NAKs. In general, network elements, sources and receivers must process a NAK list as if they had received individual NAKs for each sequence number in the list. The procedures for each are outlined in detail earlier in this document. Clarifications and differences are detailed here. 9.3.1. OPT_NAK_LIST - Packet Extensions Contents A list of sequence numbers for which retransmission is requested. 9.3.2. OPT_NAK_LIST - Procedures - Receivers Receivers may append the NAK List option to a NAK to indicate that they wish retransmission of a number of RDATA. Receivers should proceed to back off NAK transmission in a manner con- sistent with the procedures outlined for single sequence number NAKs. Note that the repair of each separate sequence number will be completed upon receipt of a separate RDATA packet. Reception of an NCF or multicast NAK containing the NAK List option suspends generation of NAKs for all sequence numbers within the NAK list, as well as the sequence number within the NAK header. 9.3.3. OPT_NAK_LIST - Procedures - Network Elements Network elements must immediately respond to a NAK with an identical NCF containing the same NAK list as the NAK itself. Network elements must forward a NAK containing a NAK List option if any one sequence number specified by the NAK (including that in the main NAK header) is not currently outstanding. That is, it must forward the NAK, if any one sequence number does not have an elimination timer running for it. The NAK must be forwarded intact. Network elements must only eliminate a NAK containing the NAK list option if all sequence numbers specified by the NAK (including that in the main NAK header) are outstanding. That is, they are all running an elimination timer. Speakman et al. [Page 45] INTERNET-DRAFT PGM Specification 10 April 2000 Upon receipt of an unsolicited NCF containing the NAK list option, a network element must anticipate data for every sequence number specified by the NAK as if it had received an NCF for every sequence number speci- fied by the NAK. 9.3.4. OPT_NAK_LIST - Procedures - Sources A source must immediately respond to a NAK with an identical NCF con- taining the same NAK list as the NAK itself. It must then multicast RDATA (while respecting TXW_MAX_RTE) for every requested sequence number. 9.3.5. OPT_NAK_LIST - Packet Extension Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Type | Option Length | Reserved |OPX| | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Requested Sequence Number 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ..... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Requested Sequence Number N | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Option Type = 0x02 Option Length = 4 + (4 * number of SQNs) octets Requested Sequence Number A list of up to 64 additional sequence numbers to which the NAK applies. If the NAK option contains more than 64 list entries, the entire NAK must be ignored. 9.4. Late Joining Option - OPT_JOIN Late joining allows a source to bound the amount of repair history receivers may request when they initially join a particular transport session. This option indicates that receivers that join a transport session in progress may request repair of all data as far back as the given minimum sequence number from the time they join the transport session. The default is for receivers to receive data only from the first packet they Speakman et al. [Page 46] INTERNET-DRAFT PGM Specification 10 April 2000 receive and onward. 9.4.1. OPT_JOIN - Packet Extensions Contents OPT_JOIN_MIN the minimum sequence number for repair 9.4.2. OPT_JOIN - Procedures - Receivers If a PGM packet (ODATA, RDATA, or SPM) bears OPT_JOIN, a receiver may initialize the trailing edge of the receive window (RXW_TRAIL_INIT) to the given Minimum Sequence Number and proceeds with normal data recep- tion. 9.4.3. OPT_JOIN - Procedures - Network Elements This option is not network-significant. 9.4.4. OPT_JOIN - Packet Extension Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Type | Option Length | Reserved |OPX| | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Minimum Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Option Type = 0x03 Option Length = 8 octets Minimum Sequence Number The minimum sequence number defining the initial trailing edge of the receive window for a late joining receiver. 9.5. Redirect Option - OPT_REDIRECT Redirection may be used by a designated local repairer (DLR) to adver- tise its own address as an alternative to the original source, for requesting repairs. These procedures allow a PGM Network Element to use a DLR that is one PGM hop from it either upstream or downstream in the multicast distribu- tion tree. The former are referred to as upstream DLRs. The latter are referred to as off-tree DLRs. Off-Tree because even though they are downstream of the point of loss, they might not lie on the subtree Speakman et al. [Page 47] INTERNET-DRAFT PGM Specification 10 April 2000 affected by the loss. A DLR must receive any PGM sessions for which it wishes to provide retransmissions. A DLR should respond to NCFs or POLLs sourced by its PGM parent with a redirecting POLR response packet containing an OPT_REDIRECT which provides its own network layer address. Recipients of redirecting POLRs may then direct NAKs for subsequent ODATA sequence numbers to the DLR rather than to the original source. In addition, DLRs that receive redirected NAKs for which they have RDATA must send a NULL NAK to provide flow control to the original source without also provoking a repair from that source. 9.5.1. OPT_REDIRECT - Packet Extensions Contents OPT_REDIR_NLA the DLR's own unicast network-layer address to which recipients of the redirecting POLR may direct subsequent NAKs for the corresponding TSI. 9.5.2. OPT_REDIRECT - Procedures - DLRs A DLR must receive any PGM sessions for which it wishes to provide a source of repairs. In addition to acting as an ordinary PGM receiver, a DLR may then respond to NCFs or relevant POLLs sourced by parent network elements (or even by the source itself) by sending a POLR containing an OPT_REDIRECT providing its own network-layer address. If a DLR can provide FEC repairs it must denote this by setting OPT_PARITY in the PGM header of its POLR response. 9.5.2.1. Upstream DLRs If the NCF completes NAK transmission initiated by the DLR itself, the DLR must not send a redirecting POLR. When a DLR receives an NCF from its upstream PGM parent, it should send a redirecting POLR, multicast to the group. The DLR should record that it is acting as an upstream DLR for the said session. Note that this POLR must have both the data source's source address and the router alert option in its network header. An upstream DLR must act as an ordinary PGM source in responding to any NAK it receives (i.e., directed to it). That is, it should respond first with a normal NCF and then RDATA as usual. In addition, an upstream DLR that receives redirected NAKs for which it has RDATA must send a NULL NAK to provide flow control to the original source. If it cannot provide the RDATA it forwards the NAK to the upstream PGM neigh- bour as usual. Speakman et al. [Page 48] INTERNET-DRAFT PGM Specification 10 April 2000 NOTA BENE: In order to propagate on exactly the same distribu- tion tree as ODATA, RDATA and POLR packets transmitted by DLRs must bear the ODATA source's NLA as the network-header source address, not the DLR's NLA as might be expected. 9.5.2.2. Off-Tree DLRs A DLR that receives a POLL with sub-type PGM_POLL_DLR must respond with a unicast redirecting POLR if it provides the appropriate service. The DLR should respond using the rules outlined for polling in Appendix D of this text. If the DLR responds, it should record that it is acting as an off-tree DLR for the said session. An off-tree DLR acts in a special way in responding to any NAK it receives (i.e., directed to it). It must respond to a NAK directed to it from its parent by unicasting an NCF and RDATA to its parent. The parent will then forward the RDATA down the distribution tree. The DLR uses its own and the parent's NLA addresses in the network header for the source and destination respectively. The unicast NCF and RDATA packets should not have the router alert option. In all other ways the RDATA header should be "as if" the packet had come from the source. Again, an off-tree DLR that receives redirected NAKs for which it has RDATA must originate a NULL NAK to provide flow control to the original source. It must originate the NULL NAK before originating the RDATA. This must be done to reduce the state held in the network element. If it cannot provide the RDATA for a given NAK, an off-tree DLR should confirm the NAK with a unicast NCF as normal, then immediately send a NAK for the said data packet back to its parent. 9.5.2.3. Simultaneous Upstream and Off-Tree DLR operation Note that it is possible for a DLR to provide service to its parent and to downstream network elements simultaneously. A downstream loss cou- pled with a loss for the same data on some other part of the distribu- tion tree served by its parent could cause this. In this case it may provide both upstream and off-tree functionality simultaneously. Note that a DLR differentiates between NAKs from an NE downstream or from its parent by comparing the network-header source address of the NAK with it's upstream PGM parent's NLA. The DLR knows the parent's NLA from the session's SPM messages. 9.5.3. OPT_REDIRECT - Procedures - Network Elements Speakman et al. [Page 49] INTERNET-DRAFT PGM Specification 10 April 2000 9.5.3.1. Discovering DLRs When a PGM router receives notification of a loss via a NAK, it should first try to use a known DLR to recover the loss. If such a DLR is not known it should initiate DLR discovery. DLR discovery may occur in two ways. If there are upstream DLRs, the NAK transmitted by this router to its PGM parent will trigger their discovery, via a redirecting POLR. Also, a network element should initiate a search for off-tree DLRs using the PGM polling mechanism, and the sub-type PGM_POLL_DLR. If a DLR can provide FEC repairs it will denote this by setting OPT_PARITY in the PGM header of its POLR response. A network element should only direct parity NAKs to a DLR that can provide FEC repairs. 9.5.3.2. Redirected Repair When it can, a network element should use upstream DLRs. Upon receiving a redirecting POLR, network elements should record the redirecting information for the TSI, and should redirect subsequent NAKs for the same TSI to the network address provided in the redirecting POLR rather than to the PGM neighbour known via the SPMs. Note, however, that a redirecting POLR is NOT regarded as matching the NAK that pro- voked it, so it does not complete the transmission of that NAK. Only a normal matching NCF can complete the transmission of a NAK. For subsequent NAKs, if the network element has recorded redirection information for the corresponding TSI, it may change the destination network address of those NAKs and attempt to transmit them to the DLR. No NAK for a specific SQN should be sent to an off-tree DLR if a NAK for the SQN has been seen on the interface associated with the DLR. Instead the NAK should be forwarded upstream. Subsequent NAKs for different SQNs may be forwarded to the said DLR (again assuming no NAK for them has been seen on the interface to the DLR). If a corresponding NCF is not received from the DLR within NAK_RPT_IVL, the network element must discard the redirecting information for the TSI and re-attempt to forward the NAK towards the PGM upstream neighbour. If a NAK is received from the DLR for a requested SQN, the network ele- ment must discard the redirecting information for the SQN and re-attempt to forward the NAK towards the PGM upstream neighbour. The network ele- ment may still direct NAKs for different SQNs to the DLR. RDATA and NCFs from upstream DLRs will flow down the distribution tree. However, RDATA and NCFs from off-tree DLRs will be unicast to the net- work element. The network element will terminate the NCF, but must put the source's NLA and the group address into the network header and must Speakman et al. [Page 50] INTERNET-DRAFT PGM Specification 10 April 2000 add router alert before forwarding the RDATA packet to the distribution subtree. NULL NAKs from an off-tree DLR for an RDATA packet requested from that off-tree DLR must always be forwarded upstream. The network element can assume that these will arrive before the matching RDATA. Other NULL NAKs are forwarded only if matching repair state has not already been created. Network elements must not confirm or retry NULL NAKs and they must not add the receiving interface to the repair state. If a NULL NAK is used to initially create repair state, this fact must be recorded so that any subsequent non-NULL NAK will not be eliminated, but rather will be forwarded to provoke an actual repair. State created by a NULL NAK exists only for NAK_ELIM_IVL. 9.5.4. OPT_REDIRECT - Procedures - Receivers These procedures are intended to be applied in instances where a receiver's first hop router on the reverse path to the source is not a PGM Network Element. So, receivers must ignore a redirecting POLR from a DLR on the same IP subnet that the receiver resides on, since this is likely to suffer identical loss to the receiver and so be useless. Therefore, these procedures are entirely optional. A receiver may choose to ignore all redirecting POLRs since in cases where its first hop router on the reverse path is PGM capable, it would ignore them any- way. Also, note that receivers will never learn of off-tree DLRs. Upon receiving a redirecting POLR, receivers should record the redirect- ing information for the TSI, and may redirect subsequent NAKs for the same TSI to the network address provided in the redirecting POLR rather than to the PGM neighbour for the corresponding ODATA for which the receiver is requesting repair. Note, however, that a redirecting POLR is NOT regarded as matching the NAK that provoked it, so it does not complete the transmission of that NAK. Only a normal matching NCF can complete the transmission of a NAK. For subsequent NAKs, if the receiver has recorded redirection informa- tion for the corresponding TSI, it may change the destination network address of those NAKs and attempt to transmit them to the DLR. If a corresponding NCF is not received within NAK_RPT_IVL, the receiver must discard the redirecting information for the TSI and re-attempt to for- ward the NAK to the PGM neighbour for the original source of the missing ODATA. 9.5.5. OPT_REDIRECT - Packet Extension Format Speakman et al. [Page 51] INTERNET-DRAFT PGM Specification 10 April 2000 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Type | Option Length | Reserved |OPX| | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | NLA AFI | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | DLR's NLA ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...-+-+ Option Type = 0x07 Option Length = 4 + NLA length DLR's NLA The DLR's own unicast network address to which recipients of the redirecting POLR may direct subsequent NAKs. Speakman et al. [Page 52] INTERNET-DRAFT PGM Specification 10 April 2000 9.6. OPT_SYN - Synchronisation Option The SYN option indicates the starting data packet for a session. It must only appear in ODATA or RDATA packets. The SYN option may be used to provide a useful abstraction to applica- tions that can simplify application design by providing stream start notification. It may also be used to let a late joiner to a session know that it is indeed late (i.e. it would not see the SYN option). 9.6.1. OPT_SYN - Procedures - Receivers Procedures for receivers are implementation dependent. A receiver may use the SYN to provide its applications with abstractions of the data stream. 9.6.2. OPT_SYN - Procedures - Network Elements None. 9.6.3. OPT_SYN - Procedures - Sources Sources may include OPT_SYN in the first data for a session. That is, it may include the option in: the first ODATA sent on a session by a PGM source any RDATA sent as a result of loss of this ODATA packet all FEC packets for the first transmission group; in this case it is interpreted as the first packet having the SYN 9.6.4. OPT_SYN - Procedures - DLRs In an identical manner to sources, DLRs must provide OPT_SYN in any retransmitted data that is at the start of a session. 9.6.5. OPT_SYN - Packet Extension Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Type | Option Length | Reserved |OPX| | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Option Type = 0x0D Speakman et al. [Page 53] INTERNET-DRAFT PGM Specification 10 April 2000 Option Length = 4 9.7. OPT_FIN - Session Finish Option This FIN option indicates the last data packet for a session and an ord- erly close down. The FIN option may be used to provide an abstraction to applications that can simplify application design by providing stream end notifica- tion. This option may be present in the last data packet or transmission group for a session. The FIN PGM option must appear in every SPM sent after the last ODATA for a session. The SPM_LEAD sequence number in an SPM with the FIN option indicates the last known data successfully transmit- ted for the session. 9.7.1. OPT_FIN - Procedures - Receivers A receiver should use receipt of a FIN to let it know that it can tear down its data structures for the said session once a suitable time period has expired (TXW_SECS). It may still try to solicit retransmis- sions within the existing transmit window. Other than this, procedures for receivers are implementation dependent. A receiver may use the FIN to provide its applications with abstractions of the data stream and to inform its applications that the session is ending. 9.7.2. OPT_FIN - Procedures - Network Elements None. 9.7.3. OPT_FIN - Procedures - Sources Sources must include OPT_FIN in every SPM sent after it has been deter- mined that the application has closed gracefully. If a source is aware at the time of transmission that it is ending a session the source may include OPT_FIN in: the last ODATA any associated RDATAs for the last data FEC packets for the last transmission group; in this case it is interpreted as the last packet having the FIN When a source detects that it needs to send an OPT_FIN it should Speakman et al. [Page 54] INTERNET-DRAFT PGM Specification 10 April 2000 immediately send it. This is done either by appending it to the last data packet or transmission group or by immediately sending an SPM and resetting the SPM heartbeat timer (ie it does not wait for a timer to expire before sending the SPM). After sending an OPT_FIN, the session should not close and stop sending SPMs until after a time period equal to TXW_SECS. 9.7.4. OPT_FIN - Procedures - DLRs In an identical manner to sources, DLRs must provide OPT_FIN in any retransmitted data that is at the end of a session. 9.7.5. OPT_FIN - Packet Extension Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Type | Option Length | Reserved |OPX| | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Option Type = 0x0E Option Length = 4 9.8. OPT_RST - Session Reset Option The RST option may appear in every SPM sent after an unrecoverable error is identified by the source. This acts to notify the receivers that the session is being aborted. This option may appear only in SPMs. The SPM_LEAD sequence number in an SPM with the RST option indicates the last known data successfully transmitted for the session. 9.8.1. OPT_RST - Procedures - Receivers Receivers should treat the reception of OPT_RST in an SPM as an abort of the session. A receiver that receives an SPM with an OPT_RST with the N bit set should not send any more NAKs for the said session towards the source. If the N bit is not set, the receiver may continue to try to solicit retransmit data within the current transmit window. 9.8.2. OPT_RST - Procedures - Network Elements None. Speakman et al. [Page 55] INTERNET-DRAFT PGM Specification 10 April 2000 9.8.3. OPT_RST - Procedures - Sources Sources should include OPT_RST in every SPM sent after it has been determined that an unrecoverable error condition has occurred. The N bit of the OPT_RST should only be sent if the source has determined that it cannot process NAKs for the session. The cause of the OPT_RST is set to an implementation specific value. If the error code is unknown, then the value of 0x00 is used. When a source detects that it needs to send an OPT_RST it should immediately send it. This is done by immediately sending an SPM and resetting the SPM heartbeat timer (ie it does not wait for a timer to expire before sending the SPM). After sending an OPT_RST, the session should not close and stop sending SPMs until after a time period equal to TXW_SECS. 9.8.4. OPT_RST - Procedures - DLRs None. 9.8.5. OPT_RST - Packet Extension Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Type | Option Length | Reserved |OPX|N| Error Code | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Option Type = 0x0F Option Length = 4 N bit The N bit is set to 1 to indicate that NAKs for previous ODATA will go unanswered from the source. The application will tell the source to turn this bit on or off. Error Code The 7 bit error code field is used to forward an error code down to the receivers from the source. The value of 0x00 indicates an unknown reset reason. Any other value indicates the application purposely aborted and gave a rea- son (the error code value) that may have meaning to the end receiver application. These values are entirely application depen- dent. Speakman et al. [Page 56] INTERNET-DRAFT PGM Specification 10 April 2000 10. Security Considerations In addition to the usual problems of end-to-end authentication, PGM is vulnerable to a number of security risks that are specific to the mechanisms it uses to establish source path state, to establish repair state, to forward NAKs, to identify DLRs, and to distribute repairs. These mechanisms expose PGM network elements themselves to security risks since network elements not only switch but also interpret SPMs, NAKs, NCFs, and RDATA, all of which may legitimately be transmitted by PGM sources, receivers, and DLRs. Short of full authentication of all neighbouring sources, receivers, DLRs, and network elements, the proto- col is not impervious to abuse. So putting aside the problems of rogue PGM network elements for the moment, there are enough potential security risks to network elements associated with sources, receivers, and DLRs alone. These risks include denial of service through the exhausting of both CPU bandwidth and memory, as well as loss of (repair) data connectivity through the mud- dling of repair state. False SPMs may cause PGM network elements to mis-direct NAKs intended for the legitimate source with the result that the requested RDATA would not be forthcoming. False NAKs may cause PGM network elements to establish spurious repair state that will expire only upon time-out and could lead to memory exhaustion in the meantime. False NCFs may cause PGM network elements to suspend NAK forwarding prematurely (or to mis-direct NAKs in the case of redirecting POLRs) resulting eventually in loss of RDATA. False RDATA may cause PGM network elements to tear down legitimate repair state resulting eventually in loss of legitimate RDATA. The development of precautions for network elements to protect them- selves against incidental or unsophisticated versions of these attacks is work in progress and includes: Damping of jitter in the value of either the network-header source address of SPMs or the path NLA in SPMs. While the network-header source address is expected to change seldom, the path NLA is expected to change occasionally as a consequence of changes in underlying mul- ticast routing information. The extension of NAK shedding procedures to control the volume, not just the rate, of confirmed NAKs. In either case, these procedures assist network elements in surviving NAK attacks at the expense of Speakman et al. [Page 57] INTERNET-DRAFT PGM Specification 10 April 2000 maintaining service. More efficiently, network elements may use the knowledge of TSIs and their associated transmit windows gleaned from SPMs to control the proliferation of repair state. A three-way handshake between network elements and DLRs that would permit a network element to ascertain with greater confidence that an alleged DLR is identified by the alleged network-header source address, and is PGM conversant. Speakman et al. [Page 58] INTERNET-DRAFT PGM Specification 10 April 2000 11. Appendix A - Forward Error Correction 11.1. Introduction The following procedures incorporate packet-level Reed Solomon Erasure correcting techniques as described in [11] and [12] into PGM. This approach to Forward Error Correction (FEC) is based upon the computation of h parity packets from k data packets for a total of n packets such that a receiver can reconstruct the k data packets out of any k of the n packets. More specifically, it is characteristic of the parity packets that any x of them can be used to reconstruct any x of the original k data packets for x less than or equal to k. The original k data packets are referred to as the Transmission Group, and the total n packets as the FEC Block. These procedures permit any combination of pro-active FEC or on-demand FEC with conventional ARQ within a given TSI to provide any flavour of layered or integrated FEC. Once provided by a source, the actual use of FEC or ARQ for loss recovery in the session is entirely at the discre- tion of the receivers. Note that receivers may still resort to selec- tive NAKs even when parity is available, and sources must still provide selective retransmissions in response. The two approaches can be used by the same or different receivers in a single transport session without conflict. Pro-active FEC refers to the technique of computing parity packets at transmission time and transmitting them as a matter of course following the data packets. Pro-active FEC is recommended for providing loss recovery over simplex or asymmetric multicast channels over which returning repair requests is either impossible or costly. It provides increased reliability at the expense of bandwidth. On-demand FEC refers to the technique of computing parity packets at repair time and transmitting them only upon demand (i.e., receiver-based loss detection and repair request). On-demand FEC is recommended for providing loss recovery of uncorrelated loss in very large receiver populations in which the probability of any single packet being lost is substantial. It provides equivalent reliability to selective NAKs (ARQ) at no more and typically less expense of bandwidth. Selective NAKs are NAKs that request the retransmission of specific packets by sequence number corresponding to the sequence number of any data packets detected to be missing from the expected sequence (conven- tional ARQ). Selective NAKs are recommended for recovering losses occurring in trailing partial transmission groups. Parity NAKs are NAKs that request the transmission of a specific number of parity packets by count corresponding to the count of the number of Speakman et al. [Page 59] INTERNET-DRAFT PGM Specification 10 April 2000 data packets detected to be missing from a group of k data packets (on- demand FEC). The objective of these procedures is to incorporate these FEC techniques into PGM so that: sources may provide parity packets either pro-actively or on-demand, interchangeably within the same TSI, receivers may use either selective or parity NAKs interchangeably within the same TSI, network elements may maintain repair state based on either selective or parity NAKs in the same data structure, altering only search, RDATA constraint, and deletion algorithms in either case, and only OPTION additions to the basic packet formats are required. 11.2. Overview Advertising FEC parameters in the transport session Sources add OPT_PARITY_PRM to SPMs to provide session-specific parame- ters such as the number of packets (TGSIZE == k) in a transmission group. This option lets receivers know how many packets there are in a transmission group, and it lets network elements sort repair state by transmission group number. This option includes an indication of whether pro-active and/or on-demand parity is available from the source. Distinguishing parity packets from data packets Sources send pro-active parity packets as ODATA and on-demand parity packets as RDATA. A source must add OPT_PARITY to the ODATA/RDATA packet header of parity packets to permit network elements and receivers to distinguish them from data packets. Data and parity packet numbering Parity packets must be calculated over a fixed number k of data packets known as the Transmission Group. Grouping of packets into transmission groups effectively partitions a packet sequence number into a high-order portion (TG_SQN) specifying the transmission group (TG), and a low-order portion (PKT_SQN) specifying the packet number (PKT-NUM in the range 0 through k-1) within that group. From an implementation point of view, it's handy if k, the TG size, is a power of 2. If so, then TG_SQN and PKT_SQN can be mapped side-by-side into the 32 bit SQN. log2(TGSIZE) is then the size in bits of PKT_SQN. Speakman et al. [Page 60] INTERNET-DRAFT PGM Specification 10 April 2000 This mapping does not reduce the effective sequence number space since parity packets marked with OPT_PARITY allow the sequence space (PKT_SQN) to be completely reused in order to number the h parity packets, as long as h is not greater than k. In the case where h is greater than k, a source must add OPT_PARITY_GRP to any parity packet numbered j greater than k-1, specifying the number m of the group of k parity packets to which the packet belongs, where m is just the quotient from the integer division of j by k. Correspond- ingly, PKT-NUM for such parity packets is just j modulo k. In other words, when a source needs to generate more parity packets than there were original data packe