RFC 3208
PGM Reliable Transport Protocol Specification
PGM Reliable Transport Protocol Specification 🦋
Okay bestie, this is RFC 3208 💖 It's titled "PGM Reliable Transport Protocol Specification," it's from the Network Working Group, and it came out in December 2001. It's marked Experimental, which means it's not an Internet standard of any kind 🧪
Fourteen people wrote it, and the header lists their affiliations like this: T. Speakman and L. Vicisano at Cisco Systems, J. Crowcroft at UCL, J. Gemmell at Microsoft, D. Farinacci at Procket Networks, S. Lin at Juniper Networks, D. Leshchiner at TIBCO Software, M. Luby at Digital Fountain, T. Montgomery at Talarian Corporation, and L. Rizzo at the University of Pisa. The header doesn't print an affiliation for A. Tweedly, N. Bhaskar, R. Edmonstone, or R. Sumanasekera, so I'm not guessing 🙈
The header doesn't list anything this document obsoletes or updates, so it's a standalone experiment ✨
Status of This Memo ✨
This memo defines an Experimental Protocol for the Internet community. It doesn't specify an Internet standard of any kind. The authors want discussion and suggestions for improvement, and anyone can distribute this memo without limits 🎀
Copyright Notice 💅
Copyright (C) The Internet Society (2001). All Rights Reserved.
Abstract 🌸
Pragmatic General Multicast (PGM) is a reliable multicast transport protocol, and it's built for apps that need ordered or unordered, duplicate-free, multicast data delivery from multiple sources to multiple receivers. PGM guarantees that a receiver in the group either gets all the data packets from transmissions and repairs, or can detect unrecoverable data packet loss. It's specifically meant to be a workable solution for multicast apps with basic reliability needs. 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 .................................. 9
3. Terms and Concepts ......................................... 12
4. Procedures - General ....................................... 18
5. Procedures - Sources ....................................... 19
6. Procedures - Receivers ..................................... 22
7. Procedures - Network Elements .............................. 27
8. Packet Formats ............................................. 31
9. Options .................................................... 40
10. Security Considerations .................................... 56
11. Appendix A - Forward Error Correction ...................... 58
12. Appendix B - Support for Congestion Control ................ 72
13. Appendix C - SPM Requests .................................. 79
14. Appendix D - Poll Mechanism ................................ 82
15. Appendix E - Implosion Prevention .......................... 92
16. Appendix F - Transmit Window Example ....................... 98
17 Appendix G - Applicability Statement ....................... 103
18. Abbreviations .............................................. 105
19. Acknowledgments ............................................ 106
20. References ................................................. 106
21. Authors' Addresses.......................................... 108
22. Full Copyright Statement ................................... 111Nota Bene 📝
This spec is meant to freeze the definition of PGM so people can keep experimenting with the protocol, both current and future experiments 🧊 The goal of those experiments is to get real experience building and deploying a reliable multicast protocol of this kind. That experience then feeds back into the longer-term standardization work going on in the Reliable Multicast Transport Working Group of the IETF 🔥 Appendix G has more detail on the scope and status of some of this experimentation. Reports of experiments include [16-23], and more results and new experiments are very much encouraged 🙌
1. Introduction and Overview ✨
Lots of reliable protocols have been proposed for multicast data delivery, and each one leans toward a particular kind of app, network, or idea of what "reliable" means ([1], [2], [3], [4]). PGM fits right into that tradition. It's a reliable transport protocol for apps that need ordered or unordered, duplicate-free, multicast data delivery from multiple sources to multiple receivers 🦋
PGM is specifically meant to be a workable solution for multicast apps with basic reliability needs. It is not trying to be a full-on solution for apps with fancy ordering, agreement, and robustness requirements. Again, the central design goal is simplicity of operation, with due regard for scalability and network efficiency 💅
PGM has no notion of group membership 🫶 It just provides reliable multicast delivery inside a transmit window that a source moves forward using a purely local strategy. Reliable delivery is provided within a source's transmit window from the time a receiver joins the group until it leaves. PGM guarantees that a receiver in the group either gets all the data packets from transmissions and repairs, or can detect unrecoverable data packet loss. PGM supports any number of sources in a multicast group, and each one is fully identified by a globally unique Transport Session Identifier (TSI). These sources and sessions operate totally independently of each other, so this spec is written in terms of a single source and extends to multiple sources without any modification 🌈
To be clear, PGM is not meant for apps that depend on acknowledged delivery to a known group of recipients, or on total ordering across multiple sources 🙅♀️
Instead, PGM is best for apps where members can join and leave at any time, and that either don't care about unrecoverable data packet loss or are ready to fall back on application-level recovery when it happens 🍓 With its optional extensions, PGM gets specific mechanisms for apps as different as stock and news updates, data conferencing, low-delay real-time video, and bulk data transfer 🧚
In the text that follows, transport-layer originators of PGM data packets are called sources, transport-layer consumers of PGM data packets are called receivers, and network-layer entities in the middle of the network are called network elements 👑
Unless otherwise specified, the term "repair" means either an actual retransmission of a copy of a missing packet, or the sending of an FEC repair packet 💖
Terminology 💜
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [14]. They indicate requirement levels for compliant PGM implementations 🎀
1.1. Summary of Operation ✨
okay bestie, so PGM runs on top of a datagram multicast protocol like IP multicast [5] 🦋. during normal data transfer, a source multicasts sequenced data packets (ODATA), and receivers unicast selective negative acknowledgments (NAKs) whenever they notice a data packet is missing from the expected sequence 💅. the NAKs travel hop-by-hop, PGM-hop-by-PGM-hop, back to the source. each network element confirms the NAK by multicasting a NAK confirmation (NCF) in response, on the interface where the NAK came in 🎀. repairs (RDATA) can come from the source itself or from a Designated Local Repairer (DLR) responding to a NAK 🫶.
NAKs are literally the only reliability mechanism, so losing one is a whole disaster 😭. to keep NAKs from getting lost, PGM defines a network-layer hop-by-hop procedure for reliable NAK forwarding 🔥.
here's the flow: when a receiver detects a missing data packet, it keeps unicasting a NAK to the last-hop PGM network element on the distribution tree from the source 🌸. it repeats this until it gets an NCF multicast to the group from that element. that element answers with an NCF to the first occurrence of the NAK and to any further retransmissions of the same NAK from any receiver ✨. then the network element keeps forwarding the NAK upstream to the previous PGM network element on the reverse of the distribution path, until it gets an NCF back from that one too 🧚. finally the source itself receives and confirms the NAK by multicasting an NCF to the group 👑.
NCFs get multicast to the group, but PGM network elements don't propagate them, since they're just hop-by-hop confirmations 🙈.
to avoid NAK implosion (aka everyone yelling at the source at once 💀), PGM specifies subnet-based NAK suppression among receivers and NAK elimination within network elements 🦋. the usual result is that just one copy of a given NAK travels along the reverse of the distribution path from any network with directly connected receivers to a source 💜.
the net effect? unicast NAKs go back from a receiver to a source along the reverse of the path the ODATA took. they pass through exactly the same sequence of PGM network elements that ODATA went through, just backwards 🍓. the reasons for handling NAKs this way will make sense when we get to constraining repairs, but first we need the mechanisms for setting up the required source path state in PGM network elements 🎀.
to set that up, the basic data transfer gets augmented by Source Path Messages (SPMs) from a source, periodically interleaved with ODATA ✨. SPMs mainly exist to establish source path state for a given TSI in every PGM network element on the distribution tree from the source 🌈. network elements use that info to address returning unicast NAKs directly to the upstream PGM network element toward the source, so 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 a rate that keeps PGM neighbor information up to date 🫶. on top of that, SPMs complement the DATA packets in provoking further NAKs from receivers, and in maintaining receive window state in the receivers 💅.
as an extra efficiency, PGM specifies procedures for constraining repairs at network elements, so that repairs only reach network segments containing group members that missed the original transmission 🦋. as NAKs travel the reverse of the ODATA path (upward), they set up repair state in the network elements, and that state is then used to constrain the (downward) forwarding of the matching RDATA 🔥.
besides procedures for the source to provide repairs, PGM also specifies options and procedures that let designated local repairers (DLRs) announce their availability and redirect repair requests (NAKs) to themselves instead of the original source 🧚. on top of these conventional selective ARQ loss-recovery procedures, Appendix A specifies Forward Error Correction (FEC) procedures, where sources provide and receivers request general error correcting parity packets instead of selective retransmissions 👑.
last but not least, PGM runs without regular return traffic from receivers, so conventional feedback mechanisms for transport flow and congestion control can't be applied 😭. Appendix B specifies a TCP-friendly, NE-based solution for PGM congestion control, and cites a reference to a TCP-friendly, end-to-end solution for PGM congestion control 🌸.
in its basic operation, PGM relies on a purely rate-limited transmission strategy in the source. this bounds the bandwidth used by PGM transport sessions and defines the transmit window the source maintains 🎀.
PGM defines four basic packet types: three flow downstream (SPMs, DATA, NCFs), and one flows upstream (NAKs) 💖.
1.2. Design Goals and Constraints 💜
PGM is designed for the broad range of multicast applications with relatively simple reliability requirements 🦋. it's built to realize the much advertised but often unrealized network efficiencies of multicast data transfer ✨. the usual blockers to those efficiencies are the implosion of negative and positive acknowledgments 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 usually done with an end-to-end protocol, where a source (implicitly or explicitly) asks a receiver for receipt confirmation, and the receiver answers positively or negatively 🫶. NAKs are only as frequent as the network's reliability and the receiver's resources allow (so potentially pretty rare 🌈), but positive acknowledgments happen at least as often as the transmit window moves, and usually more often 😭.
NAKs mainly handle repairs and reliability. positive acknowledgments mainly handle transmit buffer management 🎀.
when you extend these principles to multicast without changing anything, the positive acknowledgments alone become a burden that quickly threatens to overwhelm the source as the number of receivers grows 💀. put simply, ACK implosion keeps ACK-based reliable multicast protocols from scaling well 🙈.
one of PGM's goals is to get as strong a definition of reliability as possible from as simple a protocol as possible ✨. ACK implosion can be handled in a bunch of effective but complicated ways, most of which need re-transmit capability from somewhere other than the original source 🧚.
another option is to drop positive acknowledgments entirely, use other buffer management strategies, and keep negative acknowledgments for repairs and reliability 🦋. PGM goes with keeping NAKs, dropping ACKs, and relying on timeouts at the source to manage transmit resources 💖.
the definition of reliability in PGM follows directly from that design decision. PGM guarantees that a receiver either receives all data packets from transmissions and repairs, or is able to detect unrecoverable data packet loss 👑.
PGM includes strategies for repeatedly provoking NAKs from receivers, and for adding reliability to the NAKs themselves 🌸. by reinforcing the NAK mechanism, PGM makes it less likely that a receiver notices a missing packet so late that it's no longer available for repair from the source or from a designated local repairer (DLR) 🎀. without ACKs and knowledge of group membership, though, PGM can't rule that possibility out completely 😭.
1.2.2. Group Membership
a second consequence of getting rid of ACKs is that knowing group membership is neither required nor provided by the protocol 🫶. a source may get some PGM packets (NAKs, for instance) from some receivers, but the identity of those receivers doesn't factor into processing those packets 💅. group membership MAY change during a PGM transport session without the source or the remaining receivers knowing about it or being affected by it 🧚.
1.2.3. Efficiency ✨
PGM avoids implosion of positive acknowledgments simply by not having ACKs at all 🌈. negative acknowledgment implosion gets handled directly, though 🔥.
receivers wait a random back-off before generating a NAK. during that interval, the NAK is suppressed (it isn't sent, but the receiver acts as though it was) when the receiver gets a matching NCF 🦋. on top of that, PGM network elements eliminate duplicate NAKs received on different interfaces of the same network element 💜.
together, these two strategies usually mean the source gets just a single NAK for any given lost data packet 👑.
whether a repair comes from a DLR or the original source, it's important to constrain it to only the network segments containing members that NAKed the original transmission, rather than spreading it across the whole group 😭. PGM specifies procedures for network elements to use the pattern of NAKs to define a sub-tree within the group for forwarding the matching repair, so it reaches only the receivers that missed it in the first place 🎀.
1.2.4. Simplicity 💅
PGM is designed to get the greatest reliability improvement (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, or recovery from network partitions 🙈.
1.2.5. Operability 🧚
PGM is designed to keep working, albeit less efficiently, even when some or all of the network elements in the multicast tree know nothing about PGM 🌸. to that end, all PGM data packets can be conventionally multicast routed by non-PGM network elements with no loss of functionality, though RDATA and NCFs propagate with some inefficiency 💖.
also, since NAKs are unicast to the last-hop PGM network element and NCFs are multicast to the group, NAK/NCF operation stays consistent across non-PGM network elements 🎀. note that for NAK suppression to work best, receivers should always have a PGM network element as their first hop between themselves and every path to every PGM source 👑. if receivers are several hops away from the first PGM network element, NAK suppression efficacy may degrade 😭✨.
1.3. Options ✨
Okay so, beyond the basic data transfer stuff we just covered, PGM has a whole set of end-to-end options for specific app needs 💅. It specifies options for fragmentation, late joining, redirection, Forward Error Correction (FEC), reachability, and session synchronization/termination/reset 🧚. Options MAY be appended to PGM data packet headers only by their original transmitters. Network elements MAY interpret them, but they don't add or remove options 🫶.
All options are receiver-significant (meaning they must be interpreted by receivers) 💜. Some are also network-significant, so they must be interpreted by network elements too 🔥.
Fragmentation MAY be used together with data packets so a transport-layer entity at the source can break up application-layer data packets into multiple PGM data packets. This keeps them within the maximum transmission unit (MTU) the network layer supports 🍓.
Late joining lets a source say whether receivers may request all available repairs when they first join a particular transport session 🌸.
Redirection MAY be used with Poll Responses so a DLR can answer normal NCFs or POLLs with a redirecting POLR. That POLR advertises its own address as an alternative re-transmitter to the original source 🦋.
FEC techniques MAY be applied by receivers. They can use source-provided parity packets instead of selective retransmissions to recover from loss 🌈.
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 make this data transfer more efficient, PGM also specifies packet formats and procedures for network elements. Those improve the reliability of NAKs and constrain how repairs propagate 🧠. This section describes how those jobs are divided, and the next section goes into the details 🎀.
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 using one of several strategies. Implementations MAY support automatic adjustments, like keeping the window at a fixed size in bytes, a fixed number of packets, or a fixed real-time duration ⏳. They MAY also optionally delay window advancement for a certain period based on NAK-silence 🙈. Some possible strategies are outlined later in this document 👑.
2.2. Receiver Functions 🎧
Source Path State
Receivers use SPMs to figure out which last-hop PGM network element for a given TSI to send their NAKs to 📍.
Data Reception
Receivers receive ODATA within the transmit window and get rid of 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 that are detected as missing from the expected sequence 👀. A receiver MUST repeatedly transmit a given NAK until it receives a matching NCF. No giving up, bestie 💪.
NAK Suppression
Receivers suppress NAKs when a matching NCF or NAK arrives during the NAK transmit back-off interval 🤫.
Receive Window Advance
Receivers immediately advance their receive windows as soon as they get any PGM data packet or SPM within the transmit window that moves the receive window forward 🏃♀️.
2.3. Network Element Functions 🦋
Network elements forward ODATA without intervention. No drama, just vibes 🌊.
Source Path State
Network elements intercept SPMs and use them to establish source path state for the corresponding TSI. After that, they multicast-forward the SPMs in the usual way 🪄.
NAK Reliability
Network elements multicast NCFs to the group in response to any NAK they receive. For each NAK received, they create repair state that records the transport session identifier, the sequence number of the NAK, and the input interface where the NAK arrived 📝.
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, until they get an NCF back in response. They MAY also optionally multicast this NAK upstream with TTL of 1 🎯.
Nota Bene: Once confirmed by an NCF, network elements discard NAK packets. NAKs are NOT retained in network elements beyond this forwarding operation, but state about the reception of them is stored 📌.
NAK Elimination
Network elements discard exact duplicates of any NAK for which they already have repair state (meaning it was forwarded either by themselves or by a neighboring PGM network element), and they respond with a matching NCF 🫶.
Constrained RDATA Forwarding
Network elements use NAKs to maintain repair state, which is a list of the interfaces where a given NAK was received. They forward the matching RDATA only on those interfaces 🎯.
NAK Anticipation
If a network element hears an upstream NCF (meaning on the upstream interface for the distribution tree for the TSI), it sets up repair state with no outgoing interfaces. This is in anticipation of answering and eliminating duplicates of the NAK that may arrive from downstream 🔮.
3. Terms and Concepts 📚
Before we jump from the overview into the detail in the Procedures, this section covers some concepts and definitions that make that detail way easier to follow 🧠✨.
3.1. Transport Session Identifiers 🪪
Every PGM packet is identified by a:
TSI transport session identifierTSIs MUST be globally unique, and only one source at a time may act as the source for a transport session. (Repairers don't change the TSI in any RDATA they transmit, so keep that in mind 👀.) TSIs are made by concatenating a globally unique source identifier (GSI) and a source-assigned data-source port 🧩.
Since all PGM packets originated by receivers are responses to PGM packets from a source, receivers simply echo the TSI they heard from the source in any corresponding packets they send 🔁.
Since all PGM packets originated by network elements are responses to PGM packets from a receiver, network elements simply echo the TSI they heard from the receiver in any corresponding packets they send 🔁.
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 the matching 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 that comes before ODATA packet y. A sequence number y is "greater" or "more recent" than sequence number x if it numbers an ODATA packet that comes after ODATA packet x ⏰.
3.3. Transmit Window 🪟
The whole operation of PGM rests on the source-maintained transmit window 💫. This definition comes straight from two things: the amount of transmitted data (in seconds) a source keeps around for repair (TXW_SECS), and the maximum transmit rate (in bytes/second) a source keeps to manage its bandwidth use (TXW_MAX_RTE) 📊.
In sequence number terms, the transmit window is the range of sequence numbers the source has used to number and transmit the most recent TXW_SECS of ODATA packets 🎀. The trailing (or left) edge of the transmit window (TXW_TRAIL) is the sequence number of the oldest data packet still available for repair from a source 🕰️. The leading (or right) edge of the transmit window (TXW_LEAD) is the sequence number of the most recent data packet a source has transmitted 🚀.
The size of the transmit window in sequence numbers (TXW_SQNS), which is 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 equals TXW_LEAD, the transmit window size is one. When TXW_TRAIL equals TXW_LEAD plus one, the transmit window is empty 🫥.
3.4. Receive Window 📥
The receive window at receivers is determined entirely by PGM packets from the source. In other words, a receiver just does what the source tells it about window state and advancement 🫡.
For a given transport session identified by a TSI, a receiver maintains the following:
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 windowThe receive window is the range of sequence numbers a receiver is expected to use to identify receivable ODATA 🔍. A data packet is described as being "in" the receive window if its sequence number falls in the receive window 🎯.
The receiver advances the receive window when it receives an SPM or ODATA packet within the transmit window that increments RXW_TRAIL. Receivers also advance their receive windows when they receive any PGM data packet within the receive window that moves the receive window forward 🌟.
3.5. Source Path State ✨
okay so to set up the repair state that constrains RDATA, NAKs have to come back from a receiver to the source along the reverse of the distribution tree 🌳. bestie, that means they go back through the exact same sequence of PGM network elements that ODATA went through, just backwards 🔁. there are two reasons for this, and the second one is the real main character 💅
reason one (the obvious one): RDATA gets forwarded on the same path as ODATA, so repair state has to be set up on that path if it's going to limit where RDATA goes 🛤️
reason two (the less obvious one, and SO important 😭): without repair state, PGM network elements do NOT forward RDATA. so the default is to just discard repairs 🗑️. if repair state isn't properly set up on the interfaces where ODATA went missing, receivers on those interfaces keep NAKing for lost data and end up with unrecoverable data loss 💀
the principal job of SPMs is to give PGM network elements the source path state they need to forward NAKs from one PGM network element to the next, going back up the reverse of the distribution tree for the TSI and setting up repair state at every step 🪜. this source path state is simply the address of the upstream PGM network element on that reverse tree, and that upstream 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. it's kind of a virtual PGM topology 🧚
so even though 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 steer NAKs PGM-hop-by-PGM-hop toward the source. the whole idea is to keep NAKs constrained to the pure PGM topology, even though it sits on top of a much messier 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 the matching RDATA never gets thrown away by a PGM network element for lack of repair state 🎀
SPMs also keep transmit window state in receivers by advertising the trailing and leading edges of the transmit window (SPM_TRAIL and SPM_LEAD) ✨. when there's no data, SPMs MAY be used to close the transmit window in time by advancing it until SPM_TRAIL is equal to SPM_LEAD plus one 🦋
3.6. Packet Contents 🎀
this section just gives you enough shorthand to make the Procedures intelligible. for the full details of packet contents, check out 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 correspondsSPM_SQN: a sequence number assigned sequentially by the source in unit increments and scoped bySPM_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:
OD_TSI: the globally unique source-assigned TSIOD_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 re-synchronize to the transport session 🔄
OD_SQN: a sequence number assigned sequentially by the source in unit increments and scoped byOD_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_TSIof the ODATA packet for which this is a repairRD_TRAIL: the sequence number defining the trailing edge of the source's transmit window (TXW_TRAIL). this gets updated to the most current value when the repair is sent, so it is not necessarily the same asOD_TRAILof the ODATA packet for which this is a repair ⏰RD_SQN:OD_SQNof the ODATA packet for which this is a repair
3.6.3. Negative Acknowledgments 🙋♀️
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_TSIof the ODATA packet for which a repair is requestedNAK_SQN:OD_SQNof the ODATA packet for which a repair is requestedNAK_SRC: the unicast NLA of the original source of the missing ODATANAK_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 feedback to a source 🚦
NNAKs are unicast (PGM-hop-by-PGM-hop) to the source and contain:
NNAK_TSI:NAK_TSIof the corresponding re-directed NAKNNAK_SQN:NAK_SQNof the corresponding re-directed NAKNNAK_SRC:NAK_SRCof the corresponding re-directed NAKNNAK_GRP:NAK_GRPof the corresponding re-directed NAK
3.6.4. Negative Acknowledgment 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_TSIof the NAK being confirmedNCF_SQN:NAK_SQNof the NAK being confirmedNCF_SRC:NAK_SRCof the NAK being confirmedNCF_GRP:NAK_GRPof the NAK being confirmed
3.6.5. Option Encodings 🧩
OPT_LENGTH 0x00 - Option's Length
OPT_FRAGMENT 0x01 - Fragmentation
OPT_NAK_LIST 0x02 - List of NAK entries
OPT_JOIN 0x03 - Late Joining
OPT_REDIRECT 0x07 - Redirect
OPT_SYN 0x0D - Synchronization
OPT_FIN 0x0E - Session Fin receivers, conventional
feedbackish
OPT_RST 0x0F - Session Reset
OPT_PARITY_PRM 0x08 - Forward Error Correction Parameters
OPT_PARITY_GRP 0x09 - Forward Error Correction Group Number
OPT_CURR_TGSIZE 0x0A - Forward Error Correction Group Size
OPT_CR 0x10 - Congestion Report
OPT_CRQST 0x11 - Congestion Report Request
OPT_NAK_BO_IVL 0x04 - NAK Back-Off Interval
OPT_NAK_BO_RNG 0x05 - NAK Back-Off Range
OPT_NBR_UNREACH 0x0B - Neighbor Unreachable
OPT_PATH_NLA 0x0C - Path NLA
OPT_INVALID 0x7F - Option invalidated4. Procedures - General ✨
since SPMs, NCFs, and RDATA have to 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 going to extract them from the usual switching path 🔍
the most obvious way for network elements to manage this is to examine every packet in the network for the PGM transport protocol and packet types. but the overhead of that 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 conservative and robust as possible 🛡️. these techniques are the minimum REQUIRED of a PGM source.
5.1.1. Maximum Cumulative Transmit Rate 📈
A source MUST number ODATA packets in the order in which they are submitted 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 behavior. 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 MUST NOT exceed the token bucket size plus the product of the token rate and the chosen interval 🧮
in addition, a source MUST bound the maximum rate at which successive packets may be transmitted, using a leaky bucket scheme drained at a maximum transmit rate, or an equivalent mechanism 💧
5.1.3. Outgoing Packet Ordering 🗂️
to preserve the logic of PGM's transmit window, a source MUST strictly prioritize sending of pending NCFs first, pending SPMs second, and only send ODATA or RDATA when no NCFs or SPMs are pending 🥇. the priority of RDATA versus ODATA is application dependent. The sender MAY implement weighted bandwidth sharing between RDATA and ODATA ⚖️. note that strict prioritization of RDATA over ODATA may stall progress of ODATA if there are receivers that keep generating NAKs so as to always have RDATA pending (e.g. a steady stream of late joiners with OPT_JOIN) 😬. strictly prioritizing ODATA over RDATA may lead to a larger portion of receivers getting unrecoverable losses 💔
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
Okay bestie, what happens when there's no data to send? 🦋 A source SHOULD still keep sending SPMs, but at a decaying rate. This helps catch lost data early, keeps the source path state fresh in PGM network elements, and keeps the receive window state up to date in the receivers. 💅
The scheme [8] works like this. A source runs a timer called IHB_TMR, which measures the gap between its most recent packet (ODATA, RDATA, or SPM) and the next heartbeat. Any data packet resets IHB_TMR to the minimum interval IHB_MIN. If the timer runs out, the source sends a heartbeat SPM and doubles the timer's value. Every consecutive heartbeat doubles IHB again, up to the maximum interval IHB_MAX. The moment a data packet goes out, IHB_TMR goes straight back to IHB_MIN. 🌸 The result is that missing packets get spotted quickly when nothing is being sent, and it all happens with minimal bandwidth overhead. ✨
5.1.6. Ambient and Heartbeat SPMs
Ambient and heartbeat SPMs get their own timers in this spec, and that's on purpose! 🎀 Each one has a different job. Ambient SPMs are driven by a count-down timer that goes off regularly. Heartbeat SPMs are driven by a count-down timer that keeps getting reset by data, and its interval changes once it starts to expire. So the ambient SPM timer is just ticking down in real time, while the heartbeat timer is measuring the gap between data packets. ⏱️
When there's data, no heartbeat SPMs get sent, because every data transmission keeps setting IHB_TMR back to its starting value. ngl that's kinda neat. 🙈 But ambient SPMs MUST be interleaved into the data as a matter of course, not necessarily as a heartbeat mechanism. This ambient SPM transmission is REQUIRED to keep the distribution tree information in the network current and to let new receivers sync up with the session. 🧚
Implementation tip, but make sure it's on the spec: an implementation SHOULD de-couple the ambient and heartbeat SPM timers enough that they can be configured independently of each other. 💜
5.2. Negative Acknowledgment Confirmation
Okay, this one is so important. 😭 A source MUST immediately multicast an NCF in response to any NAK it receives. The NCF is REQUIRED because if the source answered a NAK with RDATA right away, other PGM network elements on the same subnet wouldn't be able to do NAK anticipation, and DLRs on that subnet wouldn't be able to provide repairs either. 🔥
A source SHOULD be able to detect a NAK storm and adopt countermeasures to protect the network against a denial of service. 💀 One possible countermeasure is to send the first NCF immediately in response to a NAK, then delay any further NCFs for identical NAKs by a small interval. That way identical NCFs are rate-limited, and NAK suppression still works. 👑
5.3. Repairs
After multicasting an NCF in response to a NAK, 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. 🍓
To make a particular RDATA packet more efficient, a source MAY delay the RDATA transmission so it can collect NAKs from the whole loss neighborhood. This delay SHOULD not exceed twice the greatest propagation delay in the loss neighborhood. ⭐
6. Procedures - Receivers
6.1. Data Reception
Initial data reception
Receiver, this part is your starting line! 🧚 A receiver SHOULD start data reception with the first data packet it receives within the advertised transmit window. That packet's sequence number (ODATA_SQN) temporarily defines the trailing edge of the transmit window from the receiver's point of view. It gets assigned to RXW_TRAIL_INIT inside the receiver. Until the trailing edge sequence number in later packets (SPMs, ODATA, or RDATA) moves past RXW_TRAIL_INIT, the receiver MUST only request repairs for sequence numbers after RXW_TRAIL_INIT. After that, it MAY request repairs anywhere in the transmit window. 🦋 This temporary limit stops receivers from asking for a potentially huge pile of history the moment they start receiving a PGM transport session. Iconic restraint. 💅
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 accept any ODATA or RDATA packets within the receive window. A receiver MUST discard any data packet that duplicates one it has already received in the transmit window. A receiver MUST discard any data packet outside of the receive window. 🚫
Contiguous data
Contiguous data is made up of the data packets inside the receive window that have been received and fall 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. 🌸
By default, a receiver MUST deliver only contiguous data packets to the application, and it MUST do so in the order defined by those packets' sequence numbers. This gives applications a reliable, ordered data flow. Bestie, that's the dream. ✨
Non contiguous data
Okay, the fancy mode! 🎀 PGM receiver implementations MAY optionally provide a mode in which data is delivered to an application in the order it was received. However, the implementation MUST only deliver complete application protocol data units (APDUs) to the application. That means APDUs that were fragmented into different TPDUs MUST be reassembled before they're delivered. 🧩
6.2. Source Path Messages
Receivers MUST receive and sequence SPMs for any TSI they're 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. A receiver MUST NOT initiate repair requests until it has received at least one SPM for the corresponding TSI. 💖
Here's the lowkey tricky part: SPMs need per-hop processing, so they're likely to be forwarded more slowly than data and arrive out of sync with the data stream. When that happens, the window information the SPMs carry will be out of date. Receivers SHOULD expect this and SHOULD detect it by comparing the packet's lead and trail values with the lead and trail values they've already stored. If the SPM's values are less, they SHOULD be ignored, but the rest of the packet SHOULD be processed as normal. 🫶
6.3. Data Recovery by Negative Acknowledgment ✨
Detecting missing data packets
okay bestie, receivers MUST detect gaps in the expected data sequence in the following manners: 🔍
- by comparing the sequence number on the most recently received
ODATAorRDATApacket with the leading edge of contiguous data - by comparing
SPM_LEADof the most recently receivedSPMwith the leading edge of contiguous data
in both cases, if the receiver hasn't received all the intervening data packets, it MAY initiate selective NAK generation for each missing sequence number 🦋
also, a receiver may detect a single missing data packet by receiving an NCF or multicast NAK for a data packet within the transmit window that it hasn't received. in this case it MAY initiate selective 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 possible mechanism 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 complemented 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 it's basically a 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 generation if the matching data is not received
the entire generation process can be summarized by this state machine, and it's giving main character energy 🦋
|
| detect missing tpdu
| - clear data retry count
| - clear 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 |
| | | ^ - increment NCF |
| NAK_NCF_RETRIES | | | retry count |
| exceeded | | | |
| V ----------- |
| Cancelation matching NAK |
| - restart timer(NAK_RPT_IVL) |
| |
| |
V |--------------------------| |
--------------->| WAIT_DATA_STATE |----------------------->
|start timer(NAK_RDATA_IVL)| timer expires
| | - increment data
|--------------------------| retry count
| | ^
NAK_DATA_RETRIES | | |
exceeded | | |
| -----------
| matching NCF or NAK
V - restart timer(NAK_RDATA_IVL)
Cancellationin any state, receipt of matching RDATA or ODATA completes data recovery and successfully exits the state machine. the state transition stops any running timers 💅
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.
a value for NAK_BO_IVL learned from OPT_NAK_BO_IVL (see 16.4.1 below) MUST NOT be used by a receiver (i.e., the receiver MUST NOT NAK) unless either NAK_BO_IVL_SQN is zero, or the receiver has seen POLL_RND == 0 for POLL_SQN =< NAK_BO_IVL_SQN within half the sequence number space 🙈
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's 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 most recent 🧚
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 generation if a duplicate of the NAK is already pending from this receiver, or if the NAK is 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 identifier and missing sequence number 📮 in addition, it MAY multicast a NAK with TTL of 1 to the group, if the PGM parent isn't directly connected. it also records both the address of the source of the corresponding ODATA and the address of the group in the NAK header.
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 when NAK_DATA_RETRIES / NAK_NCF_RETRIES is exceeded. cancellation of NAK generation indicates unrecoverable data loss 💀
Real talk: cancellation means the data is gone for good, so don't ignore it 😭
Receiving NCFs and multicast NAKs
a receiver MUST discard any NCFs or NAKs it hears for data packets outside the transmit window, or for data packets it has already received. otherwise they're 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 forwarding 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 🦋
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 ✨
7.2. NAK Confirmation
network elements MUST immediately transmit an NCF in response to any unicast NAK they receive. the NCF MUST be multicast to the group on the interface on which the NAK was received 💖
Nota Bene: 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 network element's NLA as might be expected. 🙈
network elements should be able to detect a NAK storm and adopt counter-measures to protect the network against a denial of service 🚨 a possible countermeasure is to send the first NCF immediately in response to a NAK, and then delay the generation of further NCFs (for identical NAKs) by a small interval, so that identical NCFs are rate-limited, without affecting the ability to suppress NAKs 🌈
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 isn't already listed 👑
7.3. Constrained NAK Forwarding ✨
okay so NAK forwarding for network elements is basically the receiver version's cousin 💅 but there are three big differences, bestie, so pay attention 🎀
First, network elements do NOT back off before forwarding a NAK (aka there's no NAK_BO_IVL) 🙅♀️ because the delay would stack up at every hop and that is NOT it. NAK arrivals get randomized by the receivers they come from, and that plus NAK anticipation and elimination literally team up to stop NAK storms on subnets with a dense crowd of network elements 😭🫶
Second, network elements do NOT retry confirmed NAKs if RDATA never shows up. They just toss the repair state and let the receivers re-request the repair. This keeps the repair state relatively ephemeral and responsive to underlying routing changes 🦋
Third, ODATA does NOT cancel NAK forwarding in network elements, since they switch it without any 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 a network element to listen to NCFs for the same transport session 👂 It also requires the network element to watch two timeout intervals for any given NAK (per NAK_TSI and NAK_SQN): NAK_RPT_IVL and NAK_RDATA_IVL ⏱️
NAK_RPT_IVL is the NAK repeat interval. It limits how long a network element keeps repeating a NAK while waiting for a matching NCF. It counts down from the moment the NAK was transmitted, and when it expires, NAK forwarding is cancelled (because the NCF went missing) 🥺
NAK_RDATA_IVL is the NAK RDATA interval. It limits how long a network element waits for the matching RDATA. It counts down from the moment a matching NCF arrives, and when it expires, the network element discards the repair state (because the RDATA went missing) 🙈
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 forwarding and tears down the corresponding repair state in the network element. Bye bye, repair state 👋
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 🙅♀️ When NAK_ELIM_IVL expires, 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. That duplicate MUST be forwarded in the usual manner ➡️ Once this duplicate NAK is outstanding, 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 🍓
NAK_ELIM_IVL is all about balancing implosion prevention against repair state liveness ⚖️ It results in the elimination of all but at most one NAK per NAK_ELIM_IVL, which lets the repeated NAKs keep the repair state alive in the PGM network elements. Iconic balance, honestly 👑
7.5. NAK Anticipation 🔮
An unsolicited NCF is one that a network element receives when it has no corresponding pending or outstanding NAK 👀 Network elements MUST process unsolicited NCFs differently depending on the interface they arrive on 🛤️
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 then discards the NCF. If the repair state already exists, the network element restarts the NAK_RDATA_IVL 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 let the network element eliminate any subsequent matching NAKs coming from downstream 🙌 Upon establishing anticipated repair state, network elements MUST eliminate subsequent NAKs only for a period of NAK_ELIM_IVL. When NAK_ELIM_IVL expires, 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. That duplicate MUST be forwarded in the usual manner. Once this duplicate NAK is outstanding, 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 elements MAY implement local procedures for withholding NAK confirmations from receivers that are detected to be reporting excessive loss 🚧 The result of these procedures would ultimately be unrecoverable data loss in the receiver. Yikes, but it's an option 😬
7.7. Addressing NAKs 📬
A PGM network element uses the source and group addresses (NLAs) in the transport header to find the state for the corresponding TSI 🔍 It then looks up the corresponding upstream PGM network element's address, uses that to re-address the (unicast) NAK, and unicasts it on the upstream interface for the distribution tree for the TSI 🚀
7.8. Constrained RDATA Forwarding 🎯
Network elements MUST maintain repair state for each interface on which a given NAK is received at least once 🗂️ They 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. After that, the corresponding repair state MUST be discarded 🧹
Network elements SHOULD discard and NOT forward RDATA packets for which they have no repair state 🙅 The consequence is that, while this constrains repairs to the interested subset of the network, losing repair state sets off more NAKs from the neglected receivers. Chaotic but also kind of fascinating 💜
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. Remember 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 as follows 📝
Data-Source Port
A random port number generated by the source 🎲 This port number MUST be unique within the source. Source Port together with Global Source ID forms the TSI 🪪
Data-Destination Port
A globally well-known port number assigned to the given PGM application 🌍
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
0x0through0x3represent SPM-like packets (i.e., session-specific, sourced by a source, periodic) 📡 - values in the range
0x4through0x7represent DATA-like packets (i.e., data and repairs) 📦 - values in the range
0x8through0xBrepresent NAK-like packets (i.e., hop-by-hop reliable NAK forwarding procedures) 🔁 - and values in the range
0xCthrough0xFrepresent SPMR-like packets (i.e., session-specific, sourced by a receiver, asynchronous) 🙋♀️
Options
This field encodes binary indications of the presence and significance 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)
Bits are numbered here from left (0 = MSB) to right (7 = LSB).All the other options (option extensions) are encoded in extensions to the PGM header 🌈
Checksum
This field is the usual 1's complement of the 1's complement sum of the entire PGM packet, header included ➕ 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 checksum 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
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 the 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] 🌸
8.1. Source Path Messages ✨
okay so SPMs are the messages a source sends to set up source path state in network elements 🛤️ and to tell receivers what its transmit window looks like 🪟. bestie this is literally the setup call 💅
The network-header source address of an SPM is the unicast NLA of whoever originates the SPM. The network-header destination address 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 🎯
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 the source assigns to the SPM 🔢
Trailing Edge Sequence Number: SPM_TRAIL The sequence number marking the current trailing edge of the source's transmit window (TXW_TRAIL) 🪟
Leading Edge Sequence Number: SPM_LEAD The sequence number marking the current leading edge of the source's transmit window (TXW_LEAD) 🪟
IfSPM_TRAIL == 0andSPM_LEAD == 0x80000000, that means there's no window info in the packet. 🙈
Path NLA: SPM_PATH The NLA of the interface on the network element where this SPM was forwarded. The source sets it to its own NLA to start, and each PGM network element rewrites it when it forwards the SPM 🦋
8.2. Data Packets 🎀
okay data packets are the ones carrying the actual application data from a source or a repairer over to receivers 📦✨
ODATA: Original data packets sent by a source. The OG ones 👑
RDATA: Repairs sent 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 whoever originates it, and the network-header destination address 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 🔑
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 the source originally gave the ODATA packet 🔢
Trailing Edge Sequence Number: OD_TRAIL, RD_TRAIL The sequence number marking the current trailing edge of the source's transmit window (TXW_TRAIL). In RDATA, this MAY not be the same as the OD_TRAIL of the ODATA packet it repairs 🙃
Data: Application data 🍓
8.3. Negative Acknowledgments and Confirmations 💌
okay this section is the feedback loop 🔁 and it has a few different messages:
NAK: Negative Acknowledgments sent by receivers to ask for a repair of an ODATA packet they noticed is missing from the expected sequence 🙋♀️
N-NAK: Null Negative Acknowledgments sent by DLRs to give flow control feedback to the source of ODATA that the DLR already sent the matching RDATA for 💅
The network-header source address of a NAK is the unicast NLA of whoever originates it. Each PGM network element rewrites that source address with its own. 🫧
The network-header destination address of a NAK is set by the originator (a receiver) to the unicast NLA of the upstream PGM network element it learned from SPMs. Each PGM network element rewrites the destination with the unicast NLA of the next upstream PGM network element the NAK gets forwarded to. On the final hop, the PGM network element rewrites the destination with the unicast NLA of the original source or the unicast NLA of a DLR. 🛤️
NCF: NAK Confirmations sent by network elements and sources to confirm they got a NAK 🫶
The network-header source address of an NCF is the ODATA source's NLA, not the network element's NLA as you might expect 👀
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 holds the Data-Destination port and the field DPORT holds the Data-Source port. 🙈 As a general rule, the SPORT/DPORT content depends on which way the flow is going. In packets going downstream, SPORT is the port number chosen in the data source (Data-Source Port) and DPORT is the data destination port number (Data-Destination Port). It's the opposite for packets going upstream. That way DPORT is always the protocol endpoint in the recipient host, no matter which direction the packet travels. ✨
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 🎯
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 that needs a repair 🩹 NNAK_SQN is the sequence number of the RDATA packet a DLR has already repaired 🩹
NCF_SQN NCF_SQN is the 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 🧚
9. Options ✨
okay so PGM has these end-to-end options for when an app has specific needs 🎀 there are options for fragmentation, late joining, and redirection (yes, all three, bestie 💅)
Options MAY be tacked onto PGM data packet headers, but only by their original transmitters 🫶 network elements MAY read them, but they don't add or remove them 🦋
Every option is TLV style, which means Type, Length, Value 🧚 the Type is in the first byte, where bit 0 is the OPT_END bit and the next 7 bits are the type. OPT_END MUST be set in the last option in the list, whichever one that happens to be 🔥 The Length field is the total option length in bytes and sits right after Type. After Length you get 5 reserved bits, the OP_ENCODED flag, the 2 Option Extensibility bits (OPX), and the OP_ENCODED_NULL flag. Last up are 7 bits for option-specific info, which can be defined per option. If an option doesn't define them, they MUST be set to 0 💖
The Option Extensibility bits decide what happens to an option when the network element processing it doesn't recognise it 👑
Nota Bene: only network elements pay any attention to these bits. 🙈
00 - Ignore the option
01 - Invalidate the option by changing the type to OPT_INVALID
= 0x7F
10 - Discard the packet
11 - Unsupported, and reserved for future useSome options that ride along in data packets (ODATA and RDATA) are tied to the packet content (the PGM payload). OPT_FRAGMENT is a great example 🌸 These options need to survive even when the data packet that usually carries them never arrives, but the payload gets rebuilt using FEC. PGM does this with the F (OP_ENCODED) and U (OP_ENCODED_NULL) bits in the option common header 🧚 OP_ENCODED and OP_ENCODED_NULL MUST normally be set to zero, except when the option is used in FEC packets to preserve the original options. Check Appendix A for the details ✨
There's 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 |F|OPX|U|Opt. Specific|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Value ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...+-+-+9.1. Option extension length - OPT_LENGTH 🌈
okay so when option extensions get added to the standard PGM header, they MUST be preceded by an option extension length field that gives the total length of all the extensions 💅
Also, the presence of the options MUST be encoded in the Options field of the standard PGM header before the Checksum gets computed 🔥
All network-significant options MUST be appended before any exclusively receiver-significant options 💜
To signal where the option extensions end, 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 itself.
OPT_LENGTH is NOT network-significant. 🙈
9.2. Fragmentation Option - OPT_FRAGMENT 🎀
Fragmentation lets transport-layer entities at a source chop application protocol data units (APDUs) into several PGM data packets (TPDUs) so they fit the MTU the network layer supports ✨ The fragmentation option MAY be applied to ODATA and RDATA packets only 💖
Architecturally, TSDUs get piled into APDUs only after the receiver has already received, de-duplicated, and contiguously sequenced the TPDUs 🦋 So 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
OPT_FRAG_LEN — the total length of the original APDU
9.2.2. OPT_FRAGMENT - Procedures - Sources
Sources slice APDUs into a contiguous run of fragments, none bigger than the MTU the network layer supports 🌈 A source gives each fragment an OD_SQN that is sequential and unique, in the order the fragments appear in the APDU 🫶 Then it sets OPT_FRAG_OFF to the fragment's offset in the original APDU (the first byte of the APDU is at offset 0, and OPT_FRAG_OFF points at the first byte of the fragment), and sets OPT_FRAG_LEN to the total length of the original APDU 🧚
9.2.3. OPT_FRAGMENT - Procedures - Receivers
Receivers spot fragmented packets and keep collecting them until they have a whole contiguous run of packets that makes up an APDU 🔥 That run starts with the fragment whose OPT_FRAG_OFF is 0, and ends with the fragment where its length plus its OPT_FRAG_OFF equals OPT_FRAG_LEN 💅
9.2.4. 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|E| Option Type | Option Length |Reserved |F|OPX|U| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| First Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Offset |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Option Type = 0x01 🦋
Option Length = 12 octets 🌸
First Sequence Number
The Sequence Number of the PGM DATA/RDATA packet holding the first fragment of the APDU.
Offset
The byte offset of the fragment from the beginning of the APDU (OPT_FRAG_OFF). 🧚
Length
The total length of the original APDU (OPT_FRAG_LEN). 💖
OPT_FRAGMENT is NOT network-significant. 🙈
9.3. NAK List Option - OPT_NAK_LIST 🍓
The NAK List option MAY be used with NAKs so receivers can ask for retransmission of more than one sequence number in a single NAK packet 🫶 The option is capped at 62 listed NAK entries 🌈 The NAK list MUST be unique and duplicate free 💅 It MUST be ordered, and it MUST consist of either a list of selective NAKs or a list of parity NAKs 🔥 In general, network elements, sources and receivers must process a NAK list as though they had received individual NAKs for each sequence number in the list 👑 The detailed procedures for each one are laid out earlier in this document, and any clarifications and differences are spelled out 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 say they want retransmission of a number of RDATA 🦋
Receivers SHOULD back off NAK transmission in a way that's consistent with the procedures for single sequence number NAKs 🌸 Keep in mind that each separate sequence number gets repaired once its own RDATA packet arrives 🧚
Receiving an NCF or multicast NAK that carries the NAK List option suspends NAK generation for every sequence number in the NAK list, plus the sequence number in the NAK header 💜
9.3.3. OPT_NAK_LIST - Procedures - Network Elements
Network elements MUST immediately answer a NAK with an identical NCF that has the same NAK list as the NAK itself 🔥
Network elements MUST forward a NAK containing a NAK List option if any one sequence number the NAK specifies (including the one in the main NAK header) is not currently outstanding. In other words, they MUST forward the NAK if any one sequence number doesn't have an elimination timer running for it. The NAK must be forwarded intact 💅
Network elements MUST eliminate a NAK containing the NAK list option only if every sequence number the NAK specifies (including the one in the main NAK header) is outstanding. That means they're all running an elimination timer 🫶
Upon receiving an unsolicited NCF containing the NAK list option, a network element MUST anticipate data for every sequence number the NAK specifies, just as if it had received an NCF for each one 🌈
9.3.4. OPT_NAK_LIST - Procedures - Sources
A source MUST immediately answer a NAK with an identical NCF that has 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|E| Option Type | Option Length |Reserved |F|OPX|U| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 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 62 additional sequence numbers that the NAK applies to. 🦋
OPT_NAK_LIST is network-significant. 🫶
9.4. Late Joining Option - OPT_JOIN 🧚
Late joining lets a source cap how much repair history receivers can ask for when they first join a transport session 💖
This option says that receivers who join a transport session already in progress MAY request repair of all data back as far as the given minimum sequence number, counting from the moment they join 👑 The default is that receivers only get data starting from the first packet they 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) carries OPT_JOIN, a receiver MAY set the trailing edge of the receive window (RXW_TRAIL_INIT) to the given Minimum Sequence Number, and then carry on with normal data reception 🌈✨
9.4.3. OPT_JOIN - Packet Extension Format 🧚
Okay, the layout bestie 🎀 Here's how the packet looks:
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 |F|OPX|U| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Minimum Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+The option type is Option Type = 0x03 💖 and the option length is Option Length = 8 octets ✨
Minimum Sequence Number 🌸 is the sequence number that sets the starting trailing edge of the receive window for a late joining receiver. Super important stuff!
OPT_JOIN is NOT network-significant. 💅
9.5. Redirect Option - OPT_REDIRECT ✨
Redirection MAY be used by a designated local repairer (DLR) 🦋 to advertise its own address as an alternative to the original source when it's requesting repairs.
These procedures let a PGM Network Element use a DLR that's one PGM hop away from it, either upstream or downstream in the multicast distribution tree. The upstream ones are called upstream DLRs. The downstream ones are called off-tree DLRs. They're called "off-tree" because even though they're downstream of the point of loss, they might not be on the subtree that got hit by the loss. Iconic naming, no cap 😭
A DLR MUST receive any PGM sessions it wants to provide retransmissions for. A DLR SHOULD respond to NCFs or POLLs sent by its PGM parent with a redirecting POLR packet that has an OPT_REDIRECT providing its own network layer address. Recipients of redirecting POLRs MAY then send NAKs for later ODATA sequence numbers to the DLR instead of the original source. Also, DLRs that get redirected NAKs for data they have as RDATA MUST send a NULL NAK to give flow control to the original source, without also triggering a repair from that source. Main character energy 👑
9.5.1. OPT_REDIRECT - Packet Extensions Contents 🍓
OPT_REDIR_NLA: the DLR's own unicast network-layer address. Recipients of the redirecting POLR MAY send subsequent NAKs for the matching TSI to this address.
9.5.2. OPT_REDIRECT - Procedures - DLRs 💜
A DLR MUST receive any PGM sessions it wants to provide a source of repairs for. Besides acting like an ordinary PGM receiver, a DLR MAY respond to NCFs or relevant POLLs sent by parent network elements (or even by the source itself) by sending a POLR that contains an OPT_REDIRECT with its own network-layer address.
If a DLR can provide FEC repairs, it MUST show that by setting OPT_PARITY in the PGM header of its POLR response. 🔥
9.5.2.1. Upstream DLRs 🌈
If the NCF completes a NAK transmission that the DLR started itself, the DLR MUST NOT send a redirecting POLR. Not doing a double-up, periodt 🙈
When a DLR gets an NCF from its upstream PGM parent, it SHOULD send a redirecting POLR, multicast to the group. The DLR SHOULD record that it's acting as an upstream DLR for that 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 like an ordinary PGM source when it responds to any NAK it receives (that is, one directed to it). So it SHOULD respond first with a normal NCF, and then RDATA as usual. On top of that, an upstream DLR that gets redirected NAKs for data it has as RDATA MUST send a NULL NAK to give flow control to the original source. If it can't provide the RDATA, it forwards the NAK to the upstream PGM neighbor as usual.
Nota Bene: In order to propagate on exactly the same distribution 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 gets 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 does respond, it SHOULD record that it's acting as an off-tree DLR for that session.
An off-tree DLR acts in a special way when it responds to any NAK it receives (that is, one 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 then forwards the RDATA down the distribution tree. The DLR uses its own and its 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 every other way, the RDATA header should be "as if" the packet had come from the source. ✨
Again, an off-tree DLR that gets redirected NAKs for data it has as RDATA MUST originate a NULL NAK to give flow control to the original source. It MUST originate the NULL NAK before originating the RDATA. This has to happen to reduce the state held in the network element. 💅
If it can't provide the RDATA for a given NAK, an off-tree DLR SHOULD confirm the NAK with a unicast NCF as normal, and then immediately send a NAK for that data packet back to its parent. 🦋
9.5.2.3. Simultaneous Upstream and Off-Tree DLR operation 👑
It's possible for a DLR to serve its parent and its downstream network elements at the same time. A downstream loss combined with a loss of the same data on some other part of the distribution tree served by its parent could cause this. In that case, it may provide both upstream and off-tree functionality simultaneously. Multitasking queen 💖
Note that a DLR tells apart NAKs from a downstream NE and NAKs from its parent by comparing the network-header source address of the NAK with its 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 🎀
9.5.3.1. Discovering DLRs 🔥
When a PGM router hears about a loss through a NAK, it SHOULD try a known DLR to recover the loss first. If no such DLR is known, it SHOULD start DLR discovery. DLR discovery can happen in two ways. If there are upstream DLRs, the NAK this router sends to its PGM parent will trigger their discovery, through a redirecting POLR. Also, a network element SHOULD start looking 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 show that 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.
When a network element gets a redirecting POLR, it SHOULD record the redirecting information for the TSI, and SHOULD redirect subsequent NAKs for the same TSI to the network address given in the redirecting POLR, rather than to the PGM neighbor it knows about through the SPMs. Note, though, 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 network element has recorded redirection information for the corresponding TSI, it MAY change the destination network address of those NAKs and try to transmit them to the DLR. No NAK for a specific SQN SHOULD be sent to an off-tree DLR if a NAK for that SQN has already 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 that DLR (again, assuming no NAK for them has been seen on the interface to the DLR). 💅
If a matching NCF isn't 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 neighbor. 😭
If a NAK is received from the DLR for a requested SQN, the network element MUST discard the redirecting information for that SQN and re-attempt to forward the NAK towards the PGM upstream neighbor. The network element MAY still direct NAKs for different SQNs to the DLR. 🙈
RDATA and NCFs from upstream DLRs flow down the distribution tree. RDATA and NCFs from off-tree DLRs, however, get unicast to the network element. The network element terminates the NCF, but MUST put the source's NLA and the group address into the network header, and MUST 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 these will arrive before the matching RDATA. Other NULL NAKs are forwarded only if matching repair state hasn't 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 create repair state initially, this fact must be recorded, so that any later non-NULL NAK won't be eliminated, but will instead 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 meant for situations 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 the receiver lives on, since that's likely to suffer the same loss for 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 anyway. Also, note that receivers will never learn of off-tree DLRs. 🍓
Upon receiving a redirecting POLR, receivers SHOULD record the redirecting information for the TSI, and MAY redirect subsequent NAKs for the same TSI to the network address given in the redirecting POLR, rather than to the PGM neighbor for the corresponding ODATA that the receiver is requesting repair for. Note, though, 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 information for the corresponding TSI, it MAY change the destination network address of those NAKs and try to transmit them to the DLR. If a matching NCF isn't received within NAK_RPT_IVL, the receiver MUST discard the redirecting information for the TSI and re-attempt to forward the NAK to the PGM neighbor for the original source of the missing ODATA. 🔥
9.5.5. OPT_REDIRECT - Packet Extension Format ✨
Okay bestie, here's the packet layout for OPT_REDIRECT 🎀
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 |F|OPX|U| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NLA AFI | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| DLR's NLA ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...-+-+The option type is Option Type = 0x07 🦋
The length is Option Length = 4 + NLA length, so it depends on how big the NLA is 💅
DLR's NLA is the DLR's own unicast network address. Recipients of the redirecting POLR can send their later NAKs to it 🌸
OPT_REDIRECT is network-significant 🧚
9.6. OPT_SYN - Synchronization Option 🌈
Okay, so OPT_SYN marks the starting data packet for a session. It must only show up in ODATA or RDATA packets 🫶
The SYN option MAY be used to give applications a handy abstraction that makes app design way easier, because it gives them stream start notification ✨ It MAY also help a late joiner to a session figure out that it is indeed late, since it would not have seen the SYN option 😭
9.6.1. OPT_SYN - Procedures - Receivers
How receivers handle this is implementation dependent 💜 A receiver MAY use the SYN to give its applications abstractions of the data stream 🎀
9.6.2. OPT_SYN - Procedures - Sources
Sources MAY include OPT_SYN in the first data for a session. To be specific, they MAY include it 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.3. OPT_SYN - Procedures - DLRs
Just like sources, DLRs MUST provide OPT_SYN in any retransmitted data that is at the start of a session 👑
9.6.4. 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|E| Option Type | Option Length |Reserved |F|OPX|U| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+The type is Option Type = 0x0D and the length is Option Length = 4 🍓
OPT_SYN is NOT network-significant 🙈
9.7. OPT_FIN - Session Finish Option 💖
This FIN option marks the last data packet for a session and an orderly close down 🔥
The FIN option MAY be used to give applications an abstraction that simplifies app design, since it provides stream end notification ✨
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 is the last known data successfully transmitted for the session 🌸
9.7.1. OPT_FIN - Procedures - Receivers
A receiver SHOULD use receipt of a FIN to know that it can tear down its data structures for the session, but only once a suitable time period has expired (TXW_SECS). It MAY still try to solicit retransmissions within the existing transmit window 🦋
Other than that, procedures for receivers are implementation dependent. A receiver MAY use the FIN to give its applications abstractions of the data stream, and to tell them that the session is ending 💅
9.7.2. OPT_FIN - Procedures - Sources
Sources MUST include OPT_FIN in every SPM sent after it has been determined that the application has closed gracefully. If a source knows at transmission time 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 send it right away 🔥 It can do this by appending it to the last data packet or transmission group, or by immediately sending an SPM and resetting the SPM heartbeat timer. That means it doesn't 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 a time period equal to TXW_SECS has passed 🫶
9.7.3. OPT_FIN - Procedures - DLRs
Just like sources, DLRs MUST provide OPT_FIN in any retransmitted data that is at the end of a session 👑
9.7.4. 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|E| Option Type | Option Length |Reserved |F|OPX|U| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+The type is Option Type = 0x0E and the length is Option Length = 4 🧚
OPT_FIN is NOT network-significant 🙈
9.8. OPT_RST - Session Reset Option 💀
The RST option MAY appear in every SPM sent after the source identifies an unrecoverable error. This tells the receivers that the session is getting aborted 😭 This option MAY appear only in SPMs. The SPM_LEAD sequence number in an SPM with the RST option is the last known data successfully transmitted for the session 🌈
9.8.1. OPT_RST - Procedures - Receivers
Receivers SHOULD treat receiving OPT_RST in an SPM as an abort of the session 🫶
A receiver that gets an SPM with an OPT_RST with the N bit set SHOULD not send any more NAKs for the session towards the source. If the N bit (see 9.8.5) is not set, the receiver MAY continue to try to solicit retransmit data within the current transmit window 🎀
9.8.2. OPT_RST - Procedures - Sources
Sources SHOULD include OPT_RST in every SPM sent after they determine that an unrecoverable error condition has happened 💅 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, the value 0x00 is used 🦋
When a source detects that it needs to send an OPT_RST, it SHOULD send it immediately. It does this by sending an SPM right away and resetting the SPM heartbeat timer, so it doesn't wait for a timer to expire first ✨ After sending an OPT_RST, the session SHOULD not close and stop sending SPMs until a time period equal to TXW_SECS has passed 🌸
9.8.3. OPT_RST - Procedures - DLRs
None. 🍓
9.8.4. 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|E| Option Type | Option Length |Reserved |F|OPX|U|N|Error Code |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+The type is Option Type = 0x0F and the length is Option Length = 4 👑
N bit: this is set to 1 to say that NAKs for previous ODATA will go unanswered from the source. The application tells the source whether to turn this bit on or off 💜
Error Code: this 6 bit field forwards an error code down to the receivers from the source. The value 0x00 means an unknown reset reason. Any other value means the application purposely aborted and gave a reason (that error code value), which may mean something to the end receiver application. These values are entirely application dependent 🔥
OPT_RST is NOT network-significant ✨
10. Security Considerations 🚨
Okay, bestie, this section is seriously important, so read it carefully 😭
In addition to the usual problems of end-to-end authentication, PGM is vulnerable to a bunch of security risks. These are specific to the mechanisms it uses to set up source path state, set up repair state, forward NAKs, identify DLRs, and distribute repairs. These mechanisms also expose PGM network elements to security risks, because network elements don't just switch SPMs, NAKs, NCFs, and RDATA. They also interpret them, and all of those may legitimately be sent by PGM sources, receivers, and DLRs. Unless all neighboring sources, receivers, DLRs, and network elements are fully authenticated, the protocol is not impervious to abuse 💀
Putting aside rogue PGM network elements for now, there are still plenty of potential security risks to network elements that come just from sources, receivers, and DLRs. These risks include denial of service from exhausting both CPU bandwidth and memory, and loss of (repair) data connectivity from muddling repair state 🙈
False SPMs may cause PGM network elements to mis-direct NAKs meant for the legitimate source, so the requested RDATA would not come through 😭
False NAKs may cause PGM network elements to set up spurious repair state. That state only expires on time-out, and it could lead to memory exhaustion in the meantime 💀
False NCFs may cause PGM network elements to suspend NAK forwarding too early (or to mis-direct NAKs when redirecting POLRs). That can eventually lead to loss of RDATA 😭
False RDATA may cause PGM network elements to tear down legitimate repair state, which can eventually lead to loss of legitimate RDATA 💅
Precautions that protect network elements from incidental or unsophisticated versions of these attacks are work outside of this spec. They include:
- Damping of jitter in the value of either the network-header source address of SPMs or the path NLA in SPMs. The network-header source address is expected to change seldom, while the path NLA is expected to change occasionally because underlying multicast routing information changes 🦋
The extension of NAK shedding procedures to control the volume, not just the rate, of confirmed NAKs is also on that list. Either way, these procedures help network elements survive NAK attacks, but at the expense of 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 is another one. It would let a network element be more confident that an alleged DLR is identified by the alleged network-header source address, and is PGM conversant 🎀
11. Appendix A - Forward Error Correction 🧚✨
11.1. Introduction
okay bestie, let's get into it 💖 this bit is about baking packet-level Reed Solomon Erasure correcting techniques into PGM 🎀. The techniques come from [11] and [12]. The basic idea is that you compute h parity packets from k data packets, so you end up with n packets total. The magic part is that a receiver can rebuild all k data packets from any k of the n packets 🧚. The original k data packets are called the Transmission Group, and the whole set of n packets is the FEC Block ✨.
These procedures let you mix and match. Within a given TSI you can use pro-active FEC, on-demand FEC, and conventional ARQ (selective retransmission) in any combo to get any flavor of layered or integrated FEC 🌈. The two approaches can even be used by the same receiver or by different ones in one transport session, with no conflict 🫶. Once a source has provided something, whether FEC or selective retransmission gets used for loss recovery is totally up to the receivers 💅. But here's the tea: receivers SHOULD NOT ask for selective retransmissions when FEC is available 🙈. Sources still MUST provide selective retransmissions in response to selective NAKs from the leading partial transmission group (the most recent transmission group, which isn't full yet) 💀. For any group that is full, the source SHOULD provide FEC on demand in response to a selective NAK ✨.
Pro-active FEC means the source computes parity packets at transmission time and just sends them right after the data packets, no questions asked 🦋. It's RECOMMENDED for loss recovery over simplex or asymmetric multicast channels, where sending repair requests back is either impossible or super costly 😭. The tradeoff is more reliability in exchange for more bandwidth, so it's a whole vibe 💜.
On-demand FEC is the opposite move. The source computes parity packets at repair time and only sends them when someone asks (receiver-based loss detection and repair request) 🍓. It's RECOMMENDED for uncorrelated loss in very large receiver populations, where the chance of any single packet getting lost is pretty high 👑. It gives you the same reliability as selective NAKs (ARQ) for no more bandwidth, and usually less 🌸.
Selective NAKs are NAKs that ask for the retransmission of specific packets, identified by the sequence numbers of data packets that go missing from the expected sequence (that's conventional ARQ) 🔥. They can cover losses in leading partial transmission groups, meaning the most recent group that isn't full yet ⭐. The RECOMMENDED way to handle partial groups, though, is for the data source to use variable-size transmission groups (see below) 🎀.
Parity NAKs are NAKs that ask for a specific number of parity packets, matching how many data packets went missing from a group of k data packets (on-demand FEC) 🧚♀️.
So what's the goal of all this? The objective is to fold 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 (however, in a session where on-demand parity is available, receivers SHOULD only use parity NAKs),
- network elements maintain repair state based on either selective or parity NAKs in the same data structure, altering only search,
RDATAconstraint, 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 📣
okay so sources add OPT_PARITY_PRM to SPMs to hand out session-specific parameters, like the number of packets (TGSIZE == k) in a transmission group 🧚. This option lets receivers know how many packets are in a transmission group, and it lets network elements sort repair state by transmission group number 💅. It also says 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 (NEs do not forward RDATA unless a repair state is present) and on-demand parity packets as RDATA. A source MUST add OPT_PARITY to the ODATA/RDATA packet header of parity packets so that network elements and receivers can tell them apart 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 packets into transmission groups splits a packet sequence number into two parts: a high-order portion (TG_SQN) that names the transmission group (TG), and a low-order portion (PKT_SQN) that gives the packet number (PKT-NUM, in the range 0 through k-1) inside that group 🍓. From an implementation point of view, it's handy if k, the TG size, is a power of 2 🌸. If it is, then TG_SQN and PKT_SQN can sit side-by-side inside the 32 bit SQN, and log2(TGSIZE) is the size in bits of PKT_SQN ✨.
This mapping does not shrink the effective sequence number space, because parity packets marked with OPT_PARITY let the sequence space (PKT_SQN) be completely reused to number the h parity packets, as long as h is not greater than k 🌈.
When h is greater than k, a source MUST add OPT_PARITY_GRP to any parity packet numbered j greater than k-1. That option specifies the number m of the group of k parity packets the packet belongs to, where m is just the quotient from the integer division of j by k. Correspondingly, PKT-NUM for those parity packets is just j modulo k 🧮. So when a source needs to make more parity packets than there were original data packets (maybe because the line is super lossy and a receiver lost not only the original data but some of the parity RDATA too 😭), it uses the OPT_PARITY_GRP option to number and identify the transmission group of the extra packets that would otherwise go past the normal sequential number space 👑.
Note that parity NAKs (and therefore their matching parity NCFs) MUST also contain the OPT_PARITY flag in the options field of the fixed header. In these packets, PKT_SQN MUST contain PKT_CNT, the number of missing packets, rather than PKT_NUM, the SQN of one specific missing packet 💜. More on all this later 🎀.
Variable Transmission Group Size 🎢
The transmission group size advertised in the OPT_PARITY_PRM option on SPMs MUST be a power of 2 and constant for the whole session. However, the actual transmission group size used MAY not be constant for the session, and MAY not be a power of 2 🙈. When a TG size different from the one advertised in OPT_PARITY_PRM is used, the TG size advertised in OPT_PARITY_PRM MUST be interpreted as specifying the maximum effective size of the TG 🔥.
When the actual TG size is not a power of 2, or is smaller than the max TG size, the sequence number space gets sparsely used. Some sequence numbers that would have been eaten up numbering a maximum sized TG won't be assigned to packets in the smaller TG 💀. The start of the next transmission group will always begin on the boundary of the maximum TG size, as though each of those sequence numbers had been used ✨.
When the source decides to use a smaller group size than the one advertised in OPT_PARITY_PRM, it appends OPT_CURR_TGSIZE to the last data packet (ODATA) in the truncated transmission group 🦋. This tells the receiver not to expect any more packets in this transmission group, and that it may start requesting repairs for any missing packets 💖. If the last data packet itself went missing, the receiver will detect the end of the group when it gets a parity packet for the group, an SPM with SPM_LEAD equal to OD_SQN of the last data packet, or the first packet of the next group, whichever comes first 🔍. On top of that, any parity packet from this TG will also carry the OPT_CURR_TGSIZE option, and so will any SPM sent with SPM_LEAD equal to OD_SQN of the last data packet 🌸.
Variable TSDU length 📏
If a non constant TSDU length is used within a given transmission group, the size of parity packets in the corresponding FEC block MUST be equal to the size of the largest original data packet in the block. Parity packets MUST be computed by padding the original packets with zeros up to the size of the largest data packet. Original data packets, though, are transmitted without padding 🫧.
Receivers that use a mix of original packets and FEC packets to rebuild missing packets MUST pad the original packets in the same way the source does. The receiver MUST then feed the padded original packets plus the parity packets to the FEC decoder. The decoder produces the original packets padded with zeros up to the size of the largest original packet in the group. For the receiver to get rid of the padding on the rebuilt data packets, the original size of the packet MUST be known, and it's handled like this 🧩:
The source, along with the packet payloads, encodes the TSDU length and appends the 2-byte encoded length to the padded FEC packets.
Receivers pad the original packets that they received to the largest original packet size and then append the TSDU length to the padded packets. They then pass them and the FEC packets to the FEC decoder.
The decoder produces padded original packets with their original TSDU length appended. Receivers MUST now use this length to get rid of the padding.
A source that transmits variable size packets MUST take into account the fact that FEC packets will have a size equal to the maximum size of the original packets plus the size of the length field (2 bytes) 📐.
If a fixed packet size is used within a transmission group, the encoded length is not appended to the parity packets. The presence of the fixed header option flag OPT_VAR_PKTLEN in parity packets lets receivers tell transmission groups with variable sized packets apart from fixed-size ones, and behave accordingly 🎯.
Payload-specific options 🎁
Some options present in data packets (ODATA and RDATA) are strictly tied to the packet content (PGM payload), OPT_FRAGMENT being one example. These options must be preserved even when the data packet that would normally carry them isn't received, but its payload is recovered through FEC 🛟.
To make that happen, PGM encodes the content of these options into special options that get inserted into parity packets. Two flags in the option common-header are used for this: bit F (OP_ENCODED) and bit U (OP_ENCODED_NULL) 🏷️.
Whenever at least one of the original packets of a TG contains a payload-specific option of a given type, the source MUST include an encoded version of that option type in all the parity packets it transmits. The encoded option is computed by applying FEC encoding to the whole option, except for the first three bytes of the option common-header (E, Option Type, Option Length, OP_ENCODED and OPX fields). The type, length and OPX of the encoded option are the same as the type, length and OPX in the original options. OP_ENCODED is set to 1 (all original options have OP_ENCODED = 0) 🧁.
The encoding uses the same process that computes the payload of the parity packet. That is, the FEC encoder is fed one copy of that option type for each original packet in the TG. If one (or more) original packet of the TG doesn't contain that option type, an all-zeroes option is used for the encoding process. To tell this "dummy" option apart from valid options with an all-zeroes payload, OP_ENCODED_NULL is used. OP_ENCODED_NULL is set to 0 in all the original options, but the value 1 is used in the encoding process if the option didn't exist in the original packet. On the receiver side, all options with OP_ENCODED_NULL equal to 1 are discarded after decoding 🗑️.
When a receiver recovers a missing packet using FEC repair packets, it MUST also recover payload-specific options, if there are any 🦸. Their presence can be unequivocally detected through the presence of encoded options in parity packets (encoded options have OP_ENCODED set to 1). Receivers apply FEC recovery to encoded options and possibly original options, the same way they do to recover packet payloads. The FEC decoding is applied to the whole option, except for the first three bytes of the option common-header (E, Option Type, Option Length, OP_ENCODED and OPX fields). Each decoded option is associated with its relative payload, unless OP_ENCODED_NULL turns out to be 1, in which case the decoded option is discarded 🫠.
The decoding MUST be performed using the 1st occurrence of a given option type in original/parity packets. If one or more original packets don't contain that option type, an option of the same type with zero value must be used. This option MUST have OP_ENCODED_NULL equal to 1 🌟.
11.3. Packet Contents 🗂️
This section just gives enough shorthand to make the Procedures make sense. For the full details of packet contents, please check out Packet Formats below 💅.
OPT_PARITY indicated in pro-active (ODATA) and on-demand
(RDATA) parity packets to distinguish them from
data packets. This option is directly encoded in
the "Option" field of the fixed PGM header
OPT_VAR_PKTLEN MAY be present in pro-active (ODATA) and on-demand
(RDATA) parity packets to indicate that the
corresponding transmission group is composed of
variable size data packets. This option is
directly encoded in the "Option" field of the fixed
PGM header
OPT_PARITY_PRM appended by sources to SPMs to specify session-
specific parameters such as the transmission group
size and the availability of pro-active and/or on-
demand parity from the source
OPT_PARITY_GRP the number of the group (greater than 0) of h
parity packets to which the parity packet belongs
when more than k parity packets are provided by the
source
OPT_CURR_TGSIZE appended by sources to the last data packet and any
parity packets in a variable sized transmission
group to indicate to the receiver the actual size
of a transmission group. May also be appended to
certain SPMs11.3.1. Parity NAKs ✨
NAK_TG_SQN the high-order portion of NAK_SQN specifying the
transmission group for which parity packets are
requested
NAK_PKT_CNT the low-order portion of NAK_SQN specifying the
number of missing data packets for which parity
packets are requestedNota Bene: okay bestie, NAK_PKT_CNT (and NCF_PKT_CNT) are 0-based counters 🧮. So NAK_PKT_CNT = 0 means you're asking for 1 FEC RDATA, and in general NAK_PKT_CNT = k - 1 means you're asking for k FEC RDATA. Counting from zero is giving math class drama, but it's consistent, so we respect it 💅
11.3.2. Parity NCFs 🌸
NCF_TG_SQN the high-order portion of NCF_SQN specifying the
transmission group for which parity packets were
requested
NCF_PKT_CNT the low-order portion of NCF_SQN specifying the
number of missing data packets for which parity
packets were requestedNota Bene: same energy here. NCF_PKT_CNT (and NAK_PKT_CNT) are 0-based counters, so NAK_PKT_CNT = 0 means 1 FEC RDATA is being requested, and in general NAK_PKT_CNT = k - 1 means k FEC RDATA are being requested 🦋
11.3.3. On-demand Parity 🧚
RDATA_TG_SQN the high-order portion of RDATA_SQN specifying the
transmission group to which the parity packet
belongs
RDATA_PKT_SQN the low-order portion of RDATA_SQN specifying the
parity packet sequence number within the
transmission group11.3.4. Pro-active Parity 💜
ODATA_TG_SQN the high-order portion of ODATA_SQN specifying the
transmission group to which the parity packet
belongs
ODATA_PKT_SQN the low-order portion of ODATA_SQN specifying the
parity packet sequence number within the
transmission group11.4. Procedures - Sources 💅
If a source elects to provide parity for a given transport session, it MUST first provide the transmission group size PARITY_PRM_TGS in the OPT_PARITY_PRM option of its SPMs. This becomes the maximum effective transmission group size in the event that the source elects to send smaller size transmission groups. If a source elects to provide proactive parity for a given transport session, it MUST set PARITY_PRM_PRO in the OPT_PARITY_PRM option of its SPMs. If a source elects to provide on-demand parity for a given transport session, it MUST set PARITY_PRM_OND in the OPT_PARITY_PRM option of its SPMs. 🎀
A source MUST send any pro-active parity packets for a given transmission group only after it has first sent all of the corresponding k data packets in that group. Pro-active parity packets MUST be sent as ODATA with OPT_PARITY in the fixed header. ✨
If a source elects to provide on-demand parity, it MUST respond to a parity NAK for a transmission group with a parity NCF. The source MUST complete the transmission of the k original data packets and the proactive parity packets, possibly scheduled, before starting the transmission of on-demand parity packets. Subsequently, the source MUST send the number of parity packets requested by that parity NAK. On-demand parity packets MUST be sent as RDATA with OPT_PARITY in the fixed header. Previously transmitted pro-active parity packets cannot be reused as on-demand parity packets, these MUST be computed with new, previously unused, indexes. Not the recycling of old packets, bestie 🙈
In either case, the source MUST provide selective retransmissions only in response to selective NAKs from the leading partial transmission group. For any group that is full, the source SHOULD provide FEC on demand in response to a selective retransmission request. 🔥
In the absence of data to transmit, a source SHOULD prematurely terminate the current transmission group by including OPT_CURR_TGSIZE to the last data packet or to any proactive parity packets provided. 🌈
If the last data packet has already been transmitted and there is no provision for sending proactive parity packets, an SPM with OPT_CURR_TGSIZE SHOULD be sent. 🍓
A source consolidates requests for on-demand parity in the same transmission group according to the following procedures. If the number of pending (i.e., unsent) parity packets from a previous request for on-demand parity packets is equal to or greater than NAK_PKT_CNT in a subsequent NAK, that subsequent NAK MUST be confirmed but MAY otherwise be ignored. If the number of pending (i.e., unsent) parity packets from a previous request for on-demand parity packets is less than NAK_PKT_CNT in a subsequent NAK, that subsequent NAK MUST be confirmed but the source need only increase the number of pending parity packets to NAK_PKT_CNT. 🧠
When a source provides parity packets relative to a transmission group with variable sized packets, it MUST compute parity packets by padding the smaller original packets with zeroes out to the size of the largest of the original packets. The source MUST also append the encoded TSDU lengths at the end of any padding or directly to the end of the largest packet, and add the OPT_VAR_PKTLEN option as specified in the overview description. 🫶
When a source provides variable sized transmission groups, it SHOULD append the OPT_CURR_TGSIZE option to the last data packet in the shortened group, and it MUST append the OPT_CURR_TGSIZE option to any parity packets it sends within that group. In case the last data packet is sent before a determination has been made to shorten the group and there is no provision for sending proactive parity packets, an SPM with OPT_CURR_TGSIZE SHOULD be sent. The source MUST also add OPT_CURR_TGSIZE to any SPM that it sends with SPM_LEAD equal to OD_SQN of the last data packet. 🦋
A receiver MUST NAK for the entire number of packets missing based on the maximum TG size, even if it already knows that the actual TG size is smaller. The source MUST take this into account and compute the number of packets effectively needed as the difference between NAK_PKT_CNT and an offset computed as the difference between the max TG size and the effective TG size. 👑
11.5. Procedures - Receivers 🌸
If a receiver elects to make use of parity packets for loss recovery, it MUST first learn the transmission group size PARITY_PRM_TGS from OPT_PARITY_PRM in the SPMs for the TSI. The transmission group size is used by a receiver to determine the sequence number boundaries between transmission groups. 💖
Thereafter, if PARITY_PRM_PRO is also set in the SPMs for the TSI, a receiver SHOULD use any pro-active parity packets it receives for loss recovery, and if PARITY_PRM_OND is also set in the SPMs for the TSI, it MAY solicit on-demand parity packets upon loss detection. If PARITY_PRM_OND is set, a receiver MUST NOT send selective NAKs, except in partial transmission groups if the source does not use the variable transmission-group size option. Parity packets are ODATA (pro-active) or RDATA (on-demand) packets distinguished by OPT_PARITY, which lets receivers know that ODATA/RDATA_TG_SQN identifies the group of PARITY_PRM_TGS packets to which the parity may be applied for loss recovery in the corresponding transmission group, and that ODATA/RDATA_PKT_SQN is being reused to number the parity packets within that group. Receivers order parity packets and eliminate duplicates within a transmission group based on ODATA/RDATA_PKT_SQN and on OPT_PARITY_GRP if present. 🧚
To solicit on-demand parity packets, a receiver MUST send parity NAKs upon loss detection. For the purposes of soliciting on-demand parity, loss detection occurs at transmission group boundaries, i.e. upon receipt of the last data packet in a transmission group, upon receipt of any data packet in any subsequent transmission group, or upon receipt of any parity packet in the current or a subsequent transmission group. 🎀
A parity NAK is simply a NAK with OPT_PARITY and NAK_PKT_CNT set to the count of the number of packets detected to be missing from the transmission group specified by NAK_TG_SQN. Note that this constrains the receiver to request no more parity packets than there are data packets in the transmission group. 🧮
A receiver SHOULD bias the value of NAK_BO_IVL for parity NAKs inversely proportional to NAK_PKT_CNT so that NAKs for larger losses are likely to be scheduled ahead of NAKs for smaller losses in the same receiver population. 🔥
A confirming NCF for a parity NAK is a parity NCF with NCF_PKT_CNT equal to or greater than that specified by the parity NAK. 🍓
A receiver's NAK_RDATA_IVL timer is not cancelled until all requested parity packets have been received. ⏳
In the absence of data (detected from SPMs bearing SPM_LEAD equal to RXW_LEAD) on non-transmission-group boundaries, receivers MAY resort to selective NAKs for any missing packets in that partial transmission group. 🌈
When a receiver handles parity packets belonging to a transmission group with variable sized packets (detected from the presence of the OPT_VAR_PKTLEN option in the parity packets), it MUST decode them as specified in the overview description and use the decoded TSDU length to get rid of the padding in the decoded packet. 🫧
If the source was using a variable sized transmission group via the OPT_CURR_TGSIZE, the receiver might learn this before having requested (and received) any retransmission. The above happens if it sees OPT_CURR_TGSIZE in the last data packet of the TG, in any proactive parity packet or in a SPM. If the receivers learns this and determines that it has missed one or more packets in the shortened transmission group, it MAY then NAK for them without waiting for the start of the next transmission group. Otherwise it will start NAKing at the start of the next transmission group. 💜
In both cases, the receiver MUST NAK for the number of packets missing assuming that the size of the transmission group is the maximum effective transmission group. In other words, the receivers cannot exploit the fact that it might already know that the transmission group was smaller but MUST always NAK for the number of packets it believes are missing, plus the number of packets required to bring the total packets up to the maximum effective transmission group size. 👑
After the first parity packet has been delivered to the receiver, the actual TG size is known to him, either because already known or because discovered via OPT_CURR_TGSIZE contained in the parity packet. Hence the receiver can decode the whole group as soon as the minimum number of parity packets needed is received. 🥹✨
11.6. Procedures - Network Elements ✨
Okay so, pro-active parity packets (ODATA with OPT_PARITY) get switched by network elements without any transport-layer intervention 💅
On-demand parity packets (RDATA with OPT_PARITY) need modified request, confirmation and repair constraint procedures for network elements 🎀. Here's the tea: repair state is kept per NAK_TSI and NAK_TG_SQN, and on top of recording the interfaces the matching NAKs came in on, the NE also records the largest NAK_PKT_CNT it has seen in matching NAKs on each interface. That number is called the known packet count 🔢. The largest known packet count is the biggest known packet count recorded for any interface in the repair state for the transmit group, or carried by an NCF.
When a parity NAK comes in, a network element answers with the matching parity NCF. That parity NCF is just an NCF made the usual way (a multicast copy of the NAK with the packet type changed), except it also gets OPT_PARITY added, and NCF_PKT_CNT is set to the larger of NAK_PKT_CNT and the known packet count for the receiving interface. Then the NE creates repair state in the usual way, with these tweaks 🦋
If repair state for the receiving interface does not exist, the NE MUST create it and also record NAK_PKT_CNT from the parity NAK as the known packet count for the receiving interface.
If repair state for the receiving interface already exists, the NE MUST eliminate the NAK only if NAK_ELIM_IVL has not expired and NAK_PKT_CNT is equal to or less than the largest known packet count. If NAK_PKT_CNT is greater than the known packet count for the receiving interface, the NE MUST update the latter with the larger NAK_PKT_CNT.
Upon either adding a new interface or updating the known packet count for an existing interface, the NE MUST determine if NAK_PKT_CNT is greater than the largest known packet count. If so, or if NAK_ELIM_IVL has expired, the NE MUST forward the parity NAK in the usual way with a value of NAK_PKT_CNT equal to the largest known packet count. Main character energy 👑
Upon receipt of an on-demand parity packet, the NE MUST locate existing repair state for the corresponding RDATA_TSI and RDATA_TG_SQN. If no such repair state exists, the NE MUST discard the RDATA as usual.
If corresponding repair state exists, the largest known packet count MUST be decremented by one, then the NE MUST forward the RDATA on all interfaces in the existing repair state, and decrement the known packet count by one for each. Any interfaces whose known packet count is thereby reduced to zero MUST be deleted from the repair state. If the number of interfaces is thereby reduced to zero, the repair state itself MUST be deleted. 💀
Upon reception of a parity NCF, network elements MUST cancel pending NAK retransmission only if NCF_PKT_CNT is greater or equal to the largest known packet count. Network elements MUST use parity NCFs to anticipate NAKs in the usual way, with the addition of recording NCF_PKT_CNT from the parity NCF as the largest known packet count with the anticipated state. That way, any subsequent NAKs received with NAK_PKT_CNT equal to or less than NCF_PKT_CNT will be eliminated, and any with NAK_PKT_CNT greater than NCF_PKT_CNT will be forwarded. Network elements which receive a parity NCF with NCF_PKT_CNT larger than the largest known packet count MUST also use it to anticipate NAKs, increasing the largest known packet count to reflect NCF_PKT_CNT (partial anticipation). ⭐
Parity NNAKs follow the usual elimination procedures, with the exception that NNAKs are eliminated only if existing NAK state has a NAK_PKT_CNT greater than NNAK_PKT_CNT.
Network elements must take extra precaution when the source is using a variable sized transmission group 🙈 They learn that the source is using a TG size smaller than the maximum from OPT_CURR_TGSIZE in parity RDATAs or in SPMs. When this happens, they compute a TG size offset as the difference between the maximum TG size and the actual TG size advertised by OPT_CURR_TGSIZE. Upon reception of parity RDATA, the TG size offset is used to update the repair state as follows:
Any interface whose known packet count is reduced to the TG size offset is deleted from the repair state.
This replaces the normal rule for deleting interfaces that applies when the TG size is equal to the maximum TG size.
11.7. Procedures - DLRs 🌸
A DLR with the ability to provide FEC repairs MUST indicate this by setting the OPT_PARITY bit in the redirecting POLR. It MUST then process any redirected FEC NAKs in the usual way.
11.8. Packet Formats 🧚
11.8.1. OPT_PARITY_PRM - 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|E| Option Type | Option Length |Reserved |F|OPX|U| |P O|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Transmission Group Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Option Type = 0x08
Option Length = 8 octets
P-bit (PARITY_PRM_PRO)
Indicates when set that the source is providing pro-active parity packets.
O-bit (PARITY_PRM_OND)
Indicates when set that the source is providing on-demand parity packets.
At least one of PARITY_PRM_PRO and PARITY_PRM_OND MUST be set.
Transmission Group Size (PARITY_PRM_TGS)
The number of data packets in the transmission group over which the parity packets are calculated. If a variable transmission group size is being used, then this becomes the maximum effective transmission group size across the session.
OPT_PARITY_PRM MAY be appended only to SPMs.
OPT_PARITY_PRM is network-significant. Network-significant, babe 💜
11.8.2. OPT_PARITY_GRP - 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|E| Option Type | Option Length |Reserved |F|OPX|U| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Parity Group Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Option Type = 0x09
Option Length = 8 octets
Parity Group Number (PRM_GROUP)
The number of the group of k parity packets amongst the h parity packets within the transmission group to which the parity packet belongs, where the first k parity packets are in group zero. PRM_GROUP MUST NOT be zero.
OPT_PARITY_GRP MAY be appended only to parity packets.
OPT_PARITY_GRP is NOT network-significant.
11.8.3. OPT_CURR_TGSIZE - 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|E| Option Type | Option Length |Reserved |F|OPX|U| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Actual Transmission Group Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Option Type = 0x0A
Option Length = 8 octets
Actual Transmission Group Size (PRM_ATGSIZE)
The actual number of data packets in this transmission group. This MUST be less than or equal to the maximum transmission group size PARITY_PRM_TGS in OPT_PARITY_PRM.
OPT_CURR_TGSIZE MAY be appended to data and parity packets (ODATA or RDATA) and to SPMs.
OPT_CURR_TGSIZE is network-significant except when appended to ODATA.
12. Appendix B - Support for Congestion Control 🌈
12.1. Introduction 💖
A source MUST implement strategies for congestion avoidance, aimed at providing overall network stability, fairness among competing PGM flows, and some degree of fairness towards coexisting TCP flows [13]. In order to do this, the source must be provided with feedback on the status of the network in terms of traffic load. This appendix specifies NE procedures that provide such feedback to the source in a scalable way. (An alternative TCP-friendly scheme for congestion control that does not require NE support can be found in [16]).
The procedures specified in this section enable the collection and selective forwarding of three types of feedback to the source:
- Worst link load as measured in network elements.
- Worst end-to-end path load as measured in network elements.
- Worst end-to-end path load as reported by receivers.
This specification defines in detail NE procedures, receivers procedures and packet formats. It also defines basic procedures in receivers for generating congestion reports. This specification does not define the procedures used by PGM sources to adapt their transmission rates in response of congestion reports. Those procedures depend upon the specific congestion control scheme.
PGM defines a header option that PGM receivers may append to NAKs (OPT_CR). OPT_CR carries congestion reports in NAKs that propagate upstream towards the source.
During the process of hop-by-hop reverse NAK forwarding, NEs examine OPT_CR and possibly modify its contents prior to forwarding the NAK upstream. Forwarding CRs also has the side effect of creating congestion report state in the NE. The presence of OPT_CR and its contents also influences the normal NAK suppression rules. Both the modification performed on the congestion report and the additional suppression rules depend on the content of the congestion report and on the congestion report state recorded in the NE as detailed below.
OPT_CR contains the following fields:
OPT_CR_NE_WL- Reports the load in the worst link as detected though NE internal measurementsOPT_CR_NE_WP- Reports the load in the worst end-to-end path as detected though NE internal measurementsOPT_CR_RX_WP- Reports the load in the worst end-to-end path as detected by receivers
A load report is either a packet drop rate (as measured at an NE's interfaces) or a packet loss rate (as measured in receivers). Its value is linearly encoded in the range 0-0xFFFF, where 0xFFFF represents a 100% loss/drop rate. Receivers that send a NAK bearing OPT_CR determine which of the three report fields are being reported.
OPT_CR also contains the following fields:
OPT_CR_NEL- A bit indicating that OPT_CR_NE_WL is being reported.OPT_CR_NEP- A bit indicating that OPT_CR_NE_WP is being reported.OPT_CR_RXP- A bit indicating that OPT_CR_RX_WP is being reported.OPT_CR_LEAD- A SQN in the ODATA space that serves as a temporal reference for the load report values. This is initialized by receivers with the leading edge of the transmit window as known at the moment of transmitting the NAK. This value MAY be advanced in NEs that modify the content of OPT_CR.OPT_CR_RCVR- The identity of the receiver that generated the worst OPT_CR_RX_WP.
The complete format of the option is specified later. 🦋
12.2. NE-Based Worst Link Report ✨
Okay bestie, so for network elements to report the worst link, receivers tack OPT_CR onto a NAK with the OPT_CR_NEL bit set and OPT_CR_NE_WL set to zero 💖. When NEs get NAKs carrying OPT_CR_NE_WL, they process the option and update their per-TSI state for it 🦋. The end result is that by the time a NAK leaves a sub-tree, OPT_CR_NE_WL holds a congestion report reflecting the load on the worst link in that sub-tree 👑. To get there, NEs rewrite OPT_CR_NE_WL with the worst value between the loads they measured on their local (outgoing) links for the session and the congestion reports received from those links 💅.
Heads up 🚨: this mechanism can't monitor load on (outgoing) links at non-PGM-capable multicast routers. So NE-Based Worst Link Reports SHOULD be used in pure PGM topologies only, otherwise this mechanism might fail to detect congestion 😭. To work around that, PGM sources MAY use a heuristic that mixes NE-Based Worst Link Reports and Receiver-Based Reports 🌈.
12.3. NE-Based Worst Path Report 🧚
To let NEs report a worst path, receivers append OPT_CR to a NAK with OPT_CR_NEP set and OPT_CR_NE_WP set to zero. It's processed like OPT_CR_NE_WL with one twist 🍓: when a NAK arrives, OPT_CR_NE_WP gets adjusted with the load measured on the interface where that NAK came in, using this formula:
OPT_CR_NE_WP = if_load + OPT_CR_NE_WP * (100% - if_loss_rate)Then the worst of the adjusted OPT_CR_NE_WP values gets written into the outgoing NAK. This means link loss rates pile up hop by hop into a path loss rate 📈.
Just like OPT_CR_NE_WL, the congestion report in OPT_CR_NE_WP may be invalid if the multicast distribution tree includes non-PGM-capable routers 🙈.
12.4. Receiver-Based Worst Report 🎀
To report a packet loss rate, receivers append OPT_CR to a NAK with OPT_CR_RXP set and OPT_CR_RX_WP set to the packet loss rate. NEs that receive NAKs containing OPT_CR_RX_WP process the option and update per-TSI state related to it. The end result: when a NAK leaves a sub-tree, OPT_CR_RX_WP holds a congestion report reflecting the load on the worst receiver in that sub-tree 🫶. To do this, NEs rewrite OTP_CR_RE_WP with the worst value among the congestion reports received on their outgoing links for the session. On top of that, OPT_CR_RCVR MUST contain the NLA of the receiver that originally measured the value of OTP_CR_RE_WP being forwarded 🔥.
12.5. Procedures - Receivers 💜
To enable any type of congestion report, receivers MUST insert OPT_CR in each NAK they generate and provide the corresponding field (OPT_CR_NE_WL, OPT_CR_NE_WP, OPT_CR_RX_WP). The specific fields to be reported get advertised to receivers in OPT_CRQST on the session's SPMs 📣. Receivers MUST provide only those options requested in OPT_CRQST 🙅.
Receivers MUST initialize OPT_CR_NE_WL and OPT_CR_NE_WP to 0, and they MUST initialize OPT_CR_RCVR to their NLA. At the moment of sending the NAK, they MUST also initialize OPT_CR_LEAD to the leading edge of the transmission window ⏰.
Additionally, if a receiver generates a NAK with OPT_CR with OPT_CR_RX_WP, it MUST initialize OPT_CR_RX_WP to the proper value, internally computed 🧮.
12.6. Procedures - Network Elements 🌊
Network elements start processing each OPT_CR by selecting a reference SQN in the ODATA space. The reference SQN selected is the highest SQN known to the NE. Usually this is the OPT_CR_LEAD contained in the NAK received 🎯.
They use the selected SQN to age the value of load measurement, like this:
- locally measured load values (e.g. interface loads) are considered up-to-date
- load values carried in
OPT_CRare considered up-to-date and are not aged, so they stay independent of variance in round-trip times from the network element to the receivers - old load values recorded in the NE are exponentially aged according to the difference between the selected reference SQN and the reference SQN associated with the old load value
The exponential aging is computed so that a recorded value gets scaled down by a factor of exp(-1/2) each time the expected inter-NAK time elapses. Hence the aging formula must include the current loss rate, as follows 🫧:
aged_loss_rate = loss_rate * exp( - SQN_difference * loss_rate /
2)Note that the quantity 1/loss_rate is the expected SQN_lag between two NAKs, so the formula above can also be read as:
aged_loss_rate = loss_rate * exp( - 1/2 * SQN_difference /
SQN_lag)which equates to (loss_rate * exp(-1/2)) when the SQN_difference is equal to the expected SQN_lag between two NAKs 🤓.
All the subsequent computations refer to the aged load values ✨.
Network elements process OPT_CR by handling the three possible types of congestion reports independently 💅. For each congestion report in an incoming NAK, a new value gets computed to be used in the outgoing NAK:
- The new value for
OPT_CR_NE_WLis the maximum of the load measured on the outgoing interfaces for the session, the value ofOPT_CR_NE_WLof the incoming NAK, and the value previously sent upstream (recorded in the NE). All these values are as obtained after the aging process. - The new value for
OPT_CR_NE_WPis the maximum of the value previously sent upstream (after aging) and the value ofOPT_CR_NE_WPin the incoming NAK, adjusted with the load on the interface upon which the NAK was received (as described above). - The new value for
OPT_CR_RX_WPis the maximum of the value previously sent upstream (after aging) and the value ofOPT_CR_RX_WPin the incoming NAK. - If
OPT_CR_RX_WPwas selected from the incoming NAK, the new value forOPT_CR_RCVRis the one in the incoming NAK. Otherwise, it is the value previously sent upstream. - The new value for
OPT_CR_LEADis the reference SQN selected for the aging procedure.
12.6.1. Overriding Normal Suppression Rules 🙋
Normal suppression rules hold to determine if a NAK should be forwarded upstream or not. However, if any of the outgoing congestion reports has changed by more than 5% relative to the one previously sent upstream, this new NAK is not suppressed 🚀.
12.6.2. Link Load Measurement 📊
PGM routers monitor the load on all their outgoing links and record it in the form of per-interface loss rate statistics. "load" MUST be interpreted as the percentage of the packets meant to be forwarded on the interface that were dropped. Load statistics refer to the aggregate traffic on the links, not to PGM traffic only 🌐.
This document does not specify the algorithm to be used to collect such statistics, but it requires that such an algorithm provide both accuracy and responsiveness in the measurement process 🎯. As far as accuracy is concerned, the expected measurement error SHOULD be upper-limited (e.g. less than 10%). As far as responsiveness is concerned, the measured load SHOULD converge to the actual value in a limited time (e.g. converge to 90% of the actual value in less than 200 milliseconds) when the instantaneous offered load changes ⚡. Whenever both requirements cannot be met at the same time, accuracy SHOULD be traded for responsiveness 💖.
12.7. Packet Formats 🎀
12.7.1. OPT_CR - 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|E| Option Type | Option Length |Reserved |F|OPX|U| L P R|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Congestion Report Reference SQN |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NE Worst Link | NE Worst Path |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Rcvr Worst Path | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NLA AFI | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Worst Receiver's NLA ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...-+-+Option Type = 0x10
Option Length = 20 octets + NLA lengthLOPT_CR_NELbit: set indicatesOPT_CR_NE_WLis being reportedPOPT_CR_NEPbit: set indicatesOPT_CR_NE_WPis being reportedROPT_CR_RXPbit: set indicatesOPT_CR_RX_WPis being reported
Congestion Report Reference SQN (OPT_CR_LEAD): a SQN in the ODATA space that serves as a temporal reference point for the load report values 🕰️.
NE Worst Link (OPT_CR_NE_WL): reports the load in the worst link as detected through NE internal measurements 🔗.
NE Worst Path (OPT_CR_NE_WP): reports the load in the worst end-to-end path as detected through NE internal measurements 🛤️.
Rcvr Worst Path (OPT_CR_RX_WP): reports the load in the worst end-to-end path as detected by receivers 👂.
Worst Receiver's NLA (OPT_CR_RCVR): the unicast address of the receiver that generated the worst OPT_CR_RX_WP 📍.
OPT_CR MAY be appended only to NAKs 🫶.
OPT-CR is network-significant 🧠.
12.7.2. OPT_CRQST - 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|E| Option Type | Option Length |Reserved |F|OPX|U| L P R|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Option Type = 0x11
Option Length = 4 octetsLOPT_CRQST_NELbit: set indicatesOPT_CR_NE_WLis being requestedPOPT_CRQST_NEPbit: set indicatesOPT_CR_NE_WPis being requestedROPT_CRQST_RXPbit: set indicatesOPT_CR_RX_WPis being requested
OPT_CRQST MAY be appended only to SPMs 📡.
OPT-CRQST is network-significant 💅.
13. Appendix C - SPM Requests 🌸
13.1. Introduction 🌷
SPM Requests (SPMRs) MAY be used to solicit an SPM from a source in a non-implosive way. The typical application is for late-joining receivers to solicit SPMs directly from a source, so they can NAK for missing packets without waiting for a regularly scheduled SPM from that source 🙌.
13.2. Overview 🔍
Allowing for SPMR implosion protection procedures, a receiver MAY unicast an SPMR to a source to solicit the most current session, window, and path state from that source, any time after the receiver has joined the group 💖. A receiver may learn the TSI and source to which to direct the SPMR from any other PGM packet it receives in the group, or by any other means, such as local configuration or directory services 🧭. The receiver MUST use the usual SPM procedures to glean the unicast address to which it should direct its NAKs from the solicited SPM 🎯.
13.3. 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 📖.
13.3.1. SPM Requests 💌
okay so SPMRs are the messages receivers send when they want an SPM from a source, like a "hey, can I get that SPM rn?" 🦋 Each SPMR has one field:
SPMR_TSI: the source-assigned TSI for the session that this SPMR belongs to 🎀
SPMs are unicast back to the source 💖
13.4. Procedures - Sources 👑
okay bestie, sources have one job here and they MUST do it right away. When an SPMR comes in, the source MUST respond immediately with the matching SPM, but it can only do this once per IHB_MIN per TSI, so nobody gets spammed 🙈 The SPM has to match up: SPM_TSI lines up with SPMR_TSI, and SPM_DPORT lines up with SPMR_DPORT ✨
13.5. Procedures - Receivers 🌸
ngl this section is giving strategy 🔥 SPMRs can get super implosive on a densely packed subnet, so receivers MUST follow a back-off and suppression routine. The trick is that they multicast the SPMR with a TTL of 1 before they unicast it to the source. That multicast is what keeps everyone else on the subnet from sending copies of the same SPMR 🧚
Here's how it goes. Before unicasting an SPMR, a receiver MUST pick a random delay on SPMR_BO_IVL (about 250 msecs) and listen for a multicast copy of the identical SPMR during that time. If it doesn't hear a matching multicast SPMR before its timer runs out, it MUST first multicast its own SPMR to the group with a TTL of 1, and only then unicast its SPMR to the source. But if it does hear a matching multicast SPMR during that window, it MUST refrain from unicasting and just wait for the corresponding SPM instead 🫶
Also, if the corresponding SPM shows up during that random interval, it SHOULD cancel the SPMR transmission 💅
Either way, the receiver MUST wait at least SPMR_SPM_IVL before trying again. Then it picks another delay on SPMR_BO_IVL and runs the whole procedure over 🌈
For matching: the corresponding SPMR has SPMR_TSI matching SPMR_TSI, and SPMR_DPORT matching SPMR_DPORT. The corresponding SPM has SPM_TSI matching SPMR_TSI, and SPM_DPORT matching SPMR_DPORT 🍓
13.6. SPM Requests 🦋
SPMR: SPM Requests are sent by receivers to ask a source for the immediate transmission of an SPM for the given TSI. It's basically an express lane 🚀
The network-header source address of an SPMR is the unicast NLA of whichever entity sends it 💜
The network-header destination address of an SPMR is the unicast NLA of the source that the corresponding SPM is being requested from 🎀
Here's the packet layout, bestie 👀
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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Extensions when present ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- ...Now the fields, one by one 💖
- Source Port:
SPMR_SPORT, which is the Data-Destination Port ✨ - Destination Port:
SPMR_DPORT. The Data-Source Port, together with the Global Source ID, formsSPMR_TSI🌸 - Type:
SPMR_TYPE = 0x0C🔥 - Global Source ID:
SPMR_GSI. Together with the Source Port, it formsSPMR_TSI🧚
14. Appendix D - Poll Mechanism 🌈
14.1. Introduction 🫶
okay so these procedures give PGM network elements and sources a way to poll their downstream PGM neighbors and get replies back in an implosion-controlled way 💅
There are two flavors of poll. General polls let a PGM (parent) node check whether it has any PGM (children) nodes hanging off it, both network elements and receivers, and estimate how many there are 👑 Specific polls let PGM parent nodes hunt for children with particular properties. DLR discovery is an example of this 🦋
Polling uses two extra PGM packets:
POLL: a Poll Request that PGM parent nodes multicast to the group to run the poll. Just like NCFs, POLL packets stop at the first PGM node they reach, because PGM network elements don't forward them 🚫POLR: a Poll Response that PGM children nodes (either network elements or receivers) use to answer a Poll Request. They address it to the NLA of the interface that the triggering POLL was sent from 💜
The polling mechanism says that PGM children who receive a POLL only reply if certain conditions are met, and otherwise they ignore it 🙈 There are two kinds of condition. One is a random condition, which sets a probability of replying for the polled child. The other is a deterministic condition. The polling parent controls both: it sets the probability of replying for the random one, and defines the deterministic condition(s) for the other. A random-only poll, a deterministic-only poll, or a mix of the two are all possible 🎀
The random condition is how polls stop implosion, because it controls how many replies come back. Say the probability of replying is P, and each receiver decides independently. Then the expected number of replies is P*N, where N is the number of PGM children belonging to the polling PGM parent. The polling node controls that expected number by setting P in the POLL packet 🔥
14.2. Packet Contents ✨
This section just gives you enough shorthand to make the Procedures make sense. For the full packet contents, check out Packet Formats below 🌸
14.2.1. POLL (Poll Request) 🎀
Here are the POLL fields:
POLL_SQN: a sequence number that the polling parent assigns in increments of one. It's scoped byPOLL_PATHand the TSI of the session 🧚POLL_ROUND: a poll round sequence number. Multiple poll rounds are possible within aPOLL_SQN💖POLL_S_TYPE: the sub-type of the poll request 🦋POLL_PATH: the network-layer address (NLA) of the interface on the PGM network element or source that the POLL is sent on 🌈POLL_BO_IVL: the back-off interval that MUST be used to compute the random back-off time before sending a response to a poll.POLL_BO_IVLis expressed in microseconds ⏱️POLL_RAND: a random string that provides the randomness in replying 🎲POLL_MASK: a bit-mask used to determine the probability of random replies 🫶
A Poll Request MAY also contain options that specify deterministic conditions for the reply. No options are currently defined 💅
14.2.2. POLR (Poll Response) 💜
Here are the POLR fields:
POLR_SQN: thePOLL_SQNof the poll request this is replying to 👑POLR_ROUND: thePOLL_ROUNDof the poll request this is replying to 🌸
A Poll Response MAY also contain options. No options are currently defined 🍓
14.3. Procedures - General 🔥
14.3.1. General Polls 🦋
General polls are for checking and counting PGM children that sit 1 PGM hop downstream of an interface on a given node 🧚 They have POLL_S_TYPE set to PGM_POLL_GENERAL. PGM children that get a general poll decide whether to reply based only on the random condition in the POLL ✨
To stop response implosion, PGM parents that start a general poll SHOULD pick the probability of replying, P, so that the expected number of replies stays contained. The expected number of replies is N * P, where N is the number of children. To work that out, PGM parents SHOULD already have a rough estimate of how many children there are. If they don't have a recent estimate, they SHOULD send the first poll with a very low probability of replying, then raise it in later polls until they get the number of replies they want 🌈
Here's the tricky bit. A sudden jump in the children population between two polls with rising probabilities could cause a poll-response implosion. To handle that, PGM parents SHOULD use poll rounds. Poll rounds let a parent "freeze" the size of the children population when it starts a poll, and keep it constant across several polls that share the same POLL_SQN but have different POLL_ROUND values. It works like this: children only respond to a poll if its POLL_ROUND is zero, or if they've already received a poll with the same POLL_SQN and a POLL_ROUND of zero 🫶
On top of that, PGM children MUST observe a random back-off before replying to a poll. That spreads the replies out over time and lets a PGM parent abort the poll if too many replies are coming in 💅 To abort an ongoing poll, a PGM parent MUST start another poll with a different POLL_SQN. And PGM children that receive a POLL MUST cancel any pending reply for POLLs whose POLL_SQN is different from the one in the last POLL they received 💜
For a given poll with probability of replying P, a PGM parent estimates the number of children as M / P, where M is the number of responses received. PGM parents SHOULD keep polling periodically and use some average of recent poll results as their estimate of the number of children 👑
14.3.2. Specific Polls 🌸
Specific polls are the way to search for PGM children that meet specific requirements. For example, a specific poll could be used to search for downstream DLRs 🔎 A specific poll is marked by a POLL_S_TYPE that's different from PGM_POLL_GENERAL. PGM children decide whether to reply to a specific poll based on the POLL_S_TYPE, the random condition, and any options that might be in the POLL. How those options get interpreted is defined by POLL_S_TYPE 🍓 The random condition MUST be treated as an additional condition that has to be satisfied. To turn the random condition off, PGM parents MUST specify a probability of replying P equal to 1 🎀
PGM children MUST ignore a POLL packet if they don't understand POLL_S_TYPE. Some specific POLL_S_TYPE values may also require children to ignore a POLL if they don't fully understand all of the PGM options in the packet 🧚
14.4. Procedures - PGM Parents (Sources or Network Elements) 👑
okay bestie, so a PGM parent (that's a source or a network element) that wants to poll the first PGM-hop children on one of its outgoing interfaces MUST send a POLL packet on that interface 📡 and fill in these fields:
POLL_SQN: equal to thePOLL_SQNof the last POLL sent, plus one. If poll rounds are used, this must be equal to thePOLL_SQNof the last group of rounds, plus one. 🔢POLL_ROUND: the round of the poll. If the poll has a single round, this must be zero. If the poll has multiple rounds, this must be one plus the lastPOLL_ROUNDfor the samePOLL_SQN, or zero if this is the first round within thisPOLL_SQN. 🌸POLL_S_TYPE: the type of the poll. For a general poll, usePGM_POLL_GENERAL. 🎀POLL_PATH: set to the NLA of the outgoing interface. 🦋POLL_BO_IVL: set to the reply back-off interval you want. UsingNAK_BO_IVLis usually the safe, conservative choice, but a smaller value MAY be used if the number of expected replies can be figured out with good confidence, or if a conservatively low probability of reply (P) is being used (seePOLL_MASKnext). When the number of expected replies is unknown, a largePOLL_BO_IVLSHOULD be used, so the poll can be aborted effectively if too many replies come in. 🧚POLL_RAND: MUST be a random string that gets re-computed each time a new poll is sent on a given interface. 🎲POLL_MASK: determines the probability of replying, P, using the relationship P = 1 / ( 2 ^ B ), where B is the number of bits set inPOLL_MASK[15]. If this is a deterministic poll, B MUST be 0, i.e.POLL_MASKMUST be a all-zeroes bit-mask. 💜
Nota Bene: POLLs transmitted by network elements MUST bear the ODATA source's network-header source address, not the network element's NLA. POLLs MUST also be transmitted with the IP Router Alert Option [6], to be allow PGM network element to intercept them. 🙈
A PGM parent that has started a poll by sending a POLL packet SHOULD wait at least POLL_BO_IVL before starting another poll. During that interval it SHOULD collect all the valid responses (the ones with POLR_SQN and POLR_ROUND matching the outstanding poll) and process them at the end of the collection interval. ⏳
A PGM parent SHOULD follow the rules in the general procedures description so it doesn't get an implosion of responses. These rules should generally be followed for both generic polls and specific polls. Specific polls, though, can use a deterministic poll (with no implosion prevention) if the expected number of replies is known to be small. 🛡️
A PGM parent that sends a generic poll to estimate the size of its children population SHOULD use poll rounds to "freeze" the children involved in the measurement. This lets the sender "open the door wider" across later rounds (by raising the probability of response) without fear of getting flooded by late joiners. Just know that rounds come with a drawback: they add delay to the population estimate, since the estimate obtained at the end of a round-group refers to the condition present at the time of the first round. ⏰
A PGM parent that has started a poll SHOULD monitor the number of replies during the collection phase. If that number gets too large, the PGM parent SHOULD abort the poll by immediately starting a new poll (with a different POLL_SQN) and specifying a very low probability of replying. 🚨
When polling is used to estimate the receiver population for calculating NAK_BO_IVL, OPT_NAK_BO_IVL (see 16.4.1 below) MUST be appended to SPMs, MAY be appended to NCFs and POLLs, and in all cases MUST have NAK_BO_IVL_SQN set to the POLL_SQN of the most recent complete round of polls, and MUST bear that round's corresponding derived value of NAK_BAK_IVL. This way, OPT_NAK_BO_IVL gives a current value for NAK_BO_IVL at the same time information is being gathered for a future value of NAK_BO_IVL. It's giving multitasking 🧠✨
14.5. Procedures - PGM Children (Receivers or Network Elements) 🌈
PGM receivers and network elements MUST compute a 32-bit random node identifier (RAND_NODE_ID) at startup time. When a PGM child (receiver or network element) receives a POLL, it MUST use its RAND_NODE_ID to match the POLL_RAND of incoming POLLs. The match is limited to the bits specified by POLL_MASK. If the incoming POLL has a POLL_MASK made of all zeroes, the match succeeds no matter what POLL_RAND contains (a deterministic reply). If the match fails, the receiver or network element MUST discard the POLL without any further action. Otherwise, it MUST check the fields POLL_ROUND, POLL_S_TYPE, and any PGM option included in the POLL to decide whether it SHOULD reply to the poll. 🔍
If POLL_ROUND is non-zero and the PGM receiver has not received an earlier poll with the same POLL_SQN and a zero POLL_ROUND, it MUST discard the poll without further action. 🚫
If POLL_S_TYPE is equal to PGM_POLL_GENERAL, the PGM child MUST schedule a reply to the POLL, even if there are PGM options on the POLL packet. 💖
If POLL_S_TYPE is different from PGM_POLL_GENERAL, whether a reply gets scheduled depends on the actual type and on the options possibly present in the POLL. 🎭
If POLL_S_TYPE is unknown to the POLL's recipient, it MUST NOT reply and MUST ignore the poll. Right now the only POLL_S_TYPE values defined are PGM_POLL_GENERAL and PGM_POLL_DLR. 🙅♀️
If a PGM receiver or network element has decided to reply to a POLL, it MUST schedule the transmission of a single POLR at a random time in the future. The random delay is chosen in the interval [0, POLL_BO_IVL], and POLL_BO_IVL is the one contained in the POLL received. When this timer expires, it MUST send a POLR using the POLL_PATH of the received POLL as the destination address. POLR_SQN MUST be equal to POLL_SQN, and POLR_ROUND must be equal to POLL_ROUND. The POLR MAY contain PGM options according to the semantics of POLL_S_TYPE or the semantics of PGM options possibly present in the POLL. If POLL_S_TYPE is PGM_POLL_GENERAL, no option is REQUIRED. 🦋
A PGM receiver or network element MUST cancel any pending transmission of POLRs if a new POLL arrives with a POLL_SQN different from the POLR_SQN of the poll that scheduled the POLRs. 🧹
14.6. Constant Definition 🍓
The POLL_S_TYPE values currently defined are:
PGM_POLL_GENERAL 0
PGM_POLL_DLR 114.7. Packet Formats 🎀
The packet formats in this section are transport-layer headers that MUST immediately follow the network-layer header in the packet. 📦
The descriptions of Data-Source Port, Data-Destination Port, Options, Checksum, Global Source ID (GSI), and TSDU Length are the ones provided in Section 8. 🔁
14.7.1. Poll Request 💅
POLLs are sent by PGM parents (sources or network elements) to start a poll among their first PGM-hop children. 🙌
POLLs are sent to the ODATA multicast group. The network-header source address of a POLL is the ODATA source's NLA. POLL MUST be transmitted with the IP Router Alert Option. 🔔
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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| POLL's Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| POLL's Round | POLL's Sub-type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NLA AFI | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Path NLA ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...-+-+
| POLL's Back-off Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Random String |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Matching Bit-Mask |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Extensions when present ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- ... -+-+-+-+-+-+-+-+-+-+-+-+-+-+Here's the field rundown, bestie 🫶:
- Source Port:
POLL_SPORT, the Data-Source Port. Together withPOLL_GSIit formsPOLL_TSI. 🌷 - Destination Port:
POLL_DPORT, the Data-Destination Port. 🎯 - Type:
POLL_TYPE = 0x01. 🏷️ - Global Source ID:
POLL_GSI. Together withPOLL_SPORTit formsPOLL_TSI. 🌐 - POLL's Sequence Number:
POLL_SQN, the sequence number the originator assigned to the POLL. 🔢 - POLL's Round:
POLL_ROUND, the round number within the poll sequence number. 🔁 - POLL's Sub-type:
POLL_S_TYPE, the sub-type of the poll request. 🧩 - Path NLA:
POLL_PATH, the NLA of the interface on the source or network element where this POLL was forwarded. 🛣️ - POLL's Back-off Interval:
POLL_BO_IVL, the back-off interval used to compute a random back-off for the reply, expressed in microseconds. ⏱️ - Random String:
POLL_RAND, a random string used to implement the random condition in replying. 🎲 - Matching Bit-Mask:
POLL_MASK, a bit-mask used to determine the probability of random replies. 💜
14.7.2. Poll Response 🦋
okay so POLRs are the replies that PGM children (receivers or network elements) send back to a POLL 💌 bestie, this is the answer to the whole POLL situation.
The network-header source address of a POLR is the unicast NLA of whoever originates it. Its network-header destination address gets filled in by the POLL's originator, and it's set to the unicast NLA of the upstream PGM element (a source or network element) that's known from the POLL that triggered the POLR ✨
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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| POLR's Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| POLR's Round | reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Extensions when present ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- ... -+-+-+-+-+-+-+-+-+-+-+-+-+-+Here's the field breakdown, bestie 🎀
- Source Port:
POLR_SPORT. This is the Data-Destination Port. - Destination Port:
POLR_DPORT. This is the Data-Source Port, and together with Global Source ID it formsPOLR_TSI🌸 - Type:
POLR_TYPE = 0x02. - Global Source ID:
POLR_GSI. Together withPOLR_DPORTit formsPOLR_TSI. - POLR's Sequence Number:
POLR_SQN. This is the sequence number (POLL_SQN) of the POLL packet this POLR is replying to. - POLR's Round:
POLR_ROUND. This is the round number (POLL_ROUND) of the POLL packet this POLR is replying to.
15. Appendix E - Implosion Prevention 🌈
15.1. Introduction
okay so these procedures exist to stop NAK implosion and to limit how far it spreads if all or part of the suppressing multicast distribution tree goes down 😭 They also give us a way to adaptively tune the NAK back-off interval, NAK_BO_IVL.
The PGM virtual topology gets set up and refreshed by SPMs. Between one SPM and the next, PGM nodes might have an out-of-date view of the topology because of multicast routing changes, flapping, or a link/router failure. If any of that happens relative to a PGM parent node, a potential NAK implosion problem shows up, because the parent can't suppress duplicate NAKs since it can't reach its children using NCFs 💀 The procedures below add an alternative way to do suppression in this case, and they also try to prevent implosion by adaptively tuning NAK_BO_IVL.
15.2. Tuning NAK_BO_IVL
Sources and network elements keep an eye on the duplicated NAKs they receive and use that to tune the NAK back-off interval (NAK_BO_IVL) for the first PGM-hop receivers connected to them 👑 Receivers learn the current value of NAK_BO_IVL through OPT_NAK_BO_IVL, which gets appended to NCFs or SPMs.
15.2.1. Procedures - Sources and Network Elements
For each TSI, sources and network elements advertise the value of NAK_BO_IVL that their first PGM-hop receivers should use. They advertise a separate value on all the outgoing interfaces for the TSI, and they keep track of the last values advertised.
For each interface and TSI, sources and network elements count the NAKs received for a specific repair state (that's per sequence number per TSI). They count from the time the interface was first added to the repair state list until the repair state is discarded. Then they use that number to tune the current NAK_BO_IVL like this:
- Increase the current value of
NAK_BO_IVLwhen the first duplicate NAK is received for a givenSQNon a particular interface. - Decrease the value of
NAK_BO_IVLif no duplicate NAKs are received on a particular interface for the lastNAK_PROBE_NUMmeasurements, where each measurement corresponds to the creation of a new repair state.
There's an upper and a lower limit for the possible value of NAK_BO_IVL at any time, and those are NAK_BO_IVL_MAX and NAK_BO_IVL_MIN respectively 🔥 The starting point for tuning is NAK_BO_IVL_DEFAULT. The policies RECOMMENDED for increasing and decreasing NAK_BO_IVL are multiplying by two and dividing by two, respectively.
Sources and network elements advertise the current value of NAK_BO_IVL through the OPT_NAK_BO_IVL that they append to NCFs. They MAY also append OPT_NAK_BO_IVL to outgoing SPMs.
To avoid forwarding the NAK_BO_IVL advertised by the parent, network elements must be able to recognize OPT_NAK_BO_IVL. Network elements that receive SPMs containing OPT_NAK_BO_IVL MUST either remove the option or overwrite its content (NAK_BO_IVL) with the current value of NAK_BO_IVL for the outgoing interface(s), before forwarding the SPMs.
Sources MAY advertise the values of NAK_BO_IVL_MAX and NAK_BO_IVL_MIN to the session by appending OPT_NAK_BO_RNG to SPMs.
15.2.2. Procedures - Receivers
Receivers learn the value of NAK_BO_IVL to use through the option OPT_NAK_BO_IVL, whenever it's present in NCFs or SPMs. A value for NAK_BO_IVL learned from OPT_NAK_BO_IVL MUST NOT be used by a receiver unless either NAK_BO_IVL_SQN is zero, or the receiver has seen POLL_RND == 0 for POLL_SQN =< NAK_BO_IVL_SQN within half the sequence number space. The initial value of NAK_BO_IVL is set to NAK_BO_IVL_DEFAULT.
Receivers that receive an SPM containing OPT_NAK_BO_RNG MUST use its content to set the local values of NAK_BO_IVL_MAX and NAK_BO_IVL_MIN ✨
15.2.3. Adjusting NAK_BO_IVL in the absence of NAKs
Keeping an eye on the number of duplicate NAKs gives us an indirect way to track changes in the size of the first PGM-hop receiver population and adjust NAK_BO_IVL to match 🧚 Note that the number of duplicate NAKs for a given SQN relates to how many first PGM-hop children scheduled (or forwarded) a NAK, and not to the absolute number of first PGM-hop children.
This mechanism doesn't work when there's no packet loss, so a big pile of duplicate NAKs is possible after a quiet stretch with no NAKs, if lots of new receivers joined the session in the meantime. To address that, PGM Sources and network elements SHOULD periodically poll the number of first PGM-hop children using the "general poll" procedures described in Appendix D. If the polls show that the population size has increased significantly during a period without NAKs, they SHOULD increase NAK_BO_IVL as a safety measure 🫶
15.3. Containing Implosion in the Presence of Network Failures
15.3.1. Detecting Network Failures
In some cases, PGM (parent) network elements can promptly detect the loss of all or part of the suppressing multicast distribution tree (due to network failures or route changes) by checking their multicast connectivity when they receive NAKs. In some other cases this isn't possible, because the connectivity problem might be happening at some other non-PGM node downstream, or it might take a while to show up in the multicast routing table.
To cover those latter cases, PGM uses a simple heuristic: a failure is assumed for a TSI when the count of duplicated NAKs received for a repair state reaches the value DUP_NAK_MAX on one of the interfaces 🔥
15.3.2. Containing Implosion
When a PGM source or network element detects or assumes a failure where it loses multicast connectivity to downstream PGM agents (either receivers or other network elements), it sends unicast NCFs to them in response to NAKs. Downstream PGM network elements that receive unicast NCFs and have multicast connectivity to the multicast session send special SPMs to prevent further NAKs, until a regular SPM sent by the source refreshes the PGM tree 🌸
Procedures - Sources and Network Elements
PGM sources or network elements that detect or assume a failure preventing them from reaching downstream PGM agents through multicast NCFs revert to confirming NAKs through unicast NCFs for a given TSI on a given interface. If the PGM agent is the source itself, then it MUST generate an SPM for the TSI, in addition to sending the unicast NCF.
Network elements MUST keep using unicast NCFs until they receive a regular SPM from the source.
When a unicast NCF is sent for the reasons described above, it MUST contain the OPT_NBR_UNREACH option and the OPT_PATH_NLA option. OPT_NBR_UNREACH indicates that the sender is unable to use multicast to reach downstream PGM agents. OPT_PATH_NLA carries the network layer address of the NCF sender, namely the NLA of the interface leading to the unreachable subtree.
When a PGM network element receives an NCF containing the OPT_NBR_UNREACH option, it MUST ignore it if OPT_PATH_NLA specifies an upstream neighbour different from the one currently known to be the upstream neighbor for the TSI. Assuming the network element matches the OPT_PATH_NLA to the upstream neighbour address, it MUST stop forwarding NAKs for the TSI until it receives a regular SPM for the TSI. In addition, it MUST also generate a special SPM to prevent downstream receivers from sending more NAKs. This special SPM MUST contain the OPT_NBR_UNREACH option and SHOULD have a SPM_SQN equal to SPM_SQN of the last regular SPM forwarded. The OPT_NBR_UNREACH option invalidates the windowing information in SPMs (SPM_TRAIL and SPM_LEAD). The PGM network element that adds the OPT_NBR_UNREACH option SHOULD invalidate the windowing information by setting SPM_TRAIL to 0 and SPM_LEAD to 0x80000000.
PGM network elements that receive an SPM containing the OPT_NBR_UNREACH option, and whose SPM_PATH matches the currently known PGM parent, MUST forward them in the normal way and MUST stop forwarding NAKs for the TSI until they receive a regular SPM for the TSI. If the SPM_PATH does not match the currently known PGM parent, the SPM containing the OPT_NBR_UNREACH option MUST be ignored.
Procedures - Receivers
PGM receivers that receive either an NCF or an SPM containing the OPT_NBR_UNREACH option MUST stop sending NAKs until a regular SPM is received for the TSI.
On reception of a unicast NCF containing the OPT_NBR_UNREACH option, receivers MUST generate a multicast copy of the packet with TTL set to one on the RPF interface for the data source. This will prevent other receivers in the same subnet from generating NAKs.
Receivers MUST ignore windowing information in SPMs which contain the OPT_NBR_UNREACH option.
Receivers MUST ignore NCFs containing the OPT_NBR_UNREACH option if the OPT_PATH_NLA specifies a neighbour different from the one currently known to be the PGM parent neighbour. Similarly, receivers MUST ignore SPMs containing the OPT_NBR_UNREACH option if SPM_PATH does not match the current PGM parent.
15.4. Packet Formats 💅
15.4.1. OPT_NAK_BO_IVL - Packet Extension Format ✨
okay bestie, OPT_NAK_BO_IVL is the option that carries the NAK back-off interval, and the layout is giving very organized energy 🎀
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 |F|OPX|U| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NAK Back-Off Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NAK Back-Off Interval SQN |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+The option type here is Option Type = 0x04 🌸
- NAK Back-Off Interval: the value of NAK-generation Back-Off Interval, in microseconds.
- NAK Back-Off Interval Sequence Number: this is the
POLL_SQNthat this value of NAK_BO_IVL goes with. Zero is reserved and means NAK_BO_IVL is NOT being determined through polling (see Appendix D), so it can be used right away. Otherwise, NAK_BO_IVL MUST NOT be used unless the receiver has also seenPOLL_ROUND = 0forPOLL_SQN =< NAK_BO_IVL_SQNwithin half the sequence number space. 🙈
OPT_NAK_BO_IVL MAY be appended to NCFs, SPMs, or POLLs.
OPT_NAK_BO_IVL is network-significant. 💜
15.4.2. OPT_NAK_BO_RNG - Packet Extension Format
this one is the range version, and the diagram is literally the same shape, just with max and min values 🦋
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 |F|OPX|U| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Maximum NAK Back-Off Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Minimum NAK Back-Off Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Option Type = 0x05 🎀
- Maximum NAK Back-Off Interval: the maximum value of NAK-generation Back-Off Interval, in microseconds.
- Minimum NAK Back-Off Interval: the minimum value of NAK-generation Back-Off Interval, in microseconds.
OPT_NAK_BO_RNG MAY be appended to SPMs.
OPT_NAK_BO_RNG is network-significant. ✨
15.4.3. OPT_NBR_UNREACH - Packet Extension Format
this is the "hey, that neighbour is gone" option, and it's lowkey iconic 💀
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 |F|OPX|U| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Option Type = 0x0B 🍓
When it shows up in SPMs, it invalidates the windowing information. Rip windowing info 😭
OPT_NBR_UNREACH MAY be appended to SPMs and NCFs.
OPT_NBR_UNREACH is network-significant. 🌈
15.4.4. OPT_PATH_NLA - Packet Extension Format
last one in this section, and it's giving "here's where I came from" vibes 🧚
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 |F|OPX|U| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Path NLA |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Option Type = 0x0C 💖
- Path NLA: the NLA of the interface on the originating PGM network element that it uses to send multicast SPMs to the recipient of the packet containing this option.
OPT_PATH_NLA MAY be appended to NCFs.
OPT_PATH_NLA is network-significant. 👑
16. Appendix F - Transmit Window Example
Nota Bene: the idea of the increment window (TXW_INC) and the window increment (TXW_ADV_SECS) is used all over this document, but it's only for illustration! They're just shorthand for the concept of moving the transmit window forward, and they don't imply any particular implementation or advancement policy. 🫶
the transmit window size in seconds is just TXW_SECS. The size in bytes (TXW_BYTES) is (TXW_MAX_RTE * TXW_SECS), and the size in sequence numbers (TXW_SQNS) is (TXW_BYTES / bytes-per-packet). 🔥
the fraction of the transmit window (in seconds of data) that gets advanced each time (TXW_ADV_SECS) is called the window increment. The trailing, oldest slice of the transmit window is called the increment window. 💅
in sequence-number terms, the increment window is the range of sequence numbers that will be the first to expire from the transmit window. Its trailing (left) edge is just TXW_TRAIL, which is also the trailing edge of the transmit window itself. Its leading (right) edge, TXW_INC, is defined as one less than the sequence number of the first data packet the source transmits TXW_ADV_SECS after it transmits TXW_TRAIL. ✨
a data packet is "in" the transmit window or the increment window if its sequence number falls inside that range. 🦋
the source advances the transmit window across the increment window when it moves TXW_TRAIL up to TXW_INC. Right after that, the increment window is empty (TXW_TRAIL is momentarily equal to TXW_INC), starts refilling as transmission goes on, and is full again TXW_ADV_SECS later (TXW_TRAIL is TXW_ADV_SECS of data away from TXW_INC). Then the window advances again, and the cycle keeps going. 🔁💜
16.1. Advancing across the Increment Window
to get ready to advance the transmit window, the source starts a timer called TXW_ADV_IVL_TMR, which runs for the period TXW_ADV_IVL. TXW_ADV_IVL has a value in the range (0, TXW_ADV_SECS). That value MAY be configurable, or MAY be determined statically by the strategy used for advancing the transmit window. 🌸
while TXW_ADV_IVL_TMR is running, a source MAY reset TXW_ADV_IVL_TMR if NAKs come in for packets in the increment window. A source MAY also transmit RDATA in the increment window with priority over other data in 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 has moved across the increment window, SPM_TRAIL, OD_TRAIL and RD_TRAIL get set to the new value of TXW_TRAIL in every packet sent after that, until the next advancement. 🧚
PGM doesn't limit which strategies a source can use to advance the transmit window. A source MAY implement any scheme or number of schemes. Three suggested strategies are outlined here. 🌈
here's an example to make it click:
Assuming a constant transmit rate of 128kbps and a constant data packet size of 1500 bytes, if a source maintains the past 30 seconds of data for repair and increments its transmit window in 5 second increments, then TXW_MAX_RTE = 16kBps TXW_ADV_SECS = 5 seconds, TXW_SECS = 35 seconds, TXW_BYTES = 560kB, TXW_SQNS = 383 (rounded up), and the size of the increment window in sequence numbers (TXW_MAX_RTE * TXW_ADV_SECS / 1500) = 54 (rounded down).
continuing the example, here's the transmit window and the increment window inside it, in sequence numbers 👀
TXW_TRAIL TXW_LEAD
| |
| |
|--|--------------- Transmit Window -------------|----|
v | | v
v v
n-1 | n | n+1 | ... | n+53 | n+54 | ... | n+381 | n+382 | n+383
^
^ | ^
|--- Increment Window|---|
|
|
TXW_INCso the sequence-number values for these windows are:
TXW_TRAIL = nTXW_INC = n+53TXW_LEAD = n+382
Nota Bene: in this example, the window sizes in sequence numbers only work out because we assumed a constant data packet size of 1500 bytes. When the packet sizes vary, MAY more or fewer sequence numbers be consumed to send the same amount of data (TXW_BYTES). Be careful with that! 🙈
so, for a given transport session identified by a TSI, a source keeps track of:
- TXW_MAX_RTE: a maximum transmit rate in kBytes per second. It's the cumulative transmit rate of some combination of SPMs, ODATA, and RDATA, depending on the transmit window advancement strategy. 💖
- TXW_TRAIL: the sequence number marking the trailing edge of the transmit window, which is the sequence number of the oldest data packet still available for repair. 🌸
- TXW_LEAD: the sequence number marking the leading edge of the transmit window, which is the sequence number of the most recently transmitted ODATA packet. 🫶
- TXW_INC: the sequence number marking the leading edge of the increment window, which is the sequence number of the most recently transmitted data packet among those that will expire on the next increment of the transmit window. 🦋
PGM doesn't limit which strategies a source can use to advance the transmit window. A source MAY implement any scheme or number of schemes. This works because a PGM receiver MUST obey the window the source provides in its packets. Three strategies are suggested in this document. 💅
the first one is called "Advance with Time". The transmit window keeps the last TXW_SECS of data in real time, whether or not any data was sent in that time period. The number of bytes held at any moment will vary between 0 and TXW_BYTES, depending on traffic during the last TXW_SECS. In this case, TXW_MAX_RTE is the cumulative transmit rate of SPMs and ODATA. ⏰
the second one is called "Advance with Data". The transmit window keeps the last TXW_BYTES bytes of data for repair. In other words, it holds the theoretical maximum amount of data that could have been sent in the time period TXW_SECS, no matter when that data was actually sent. In this case, TXW_MAX_RTE is the cumulative transmit rate of SPMs, ODATA, and RDATA. 🌈
the third strategy hands control of the window to the application. The API a source implementation provides for this could let the application control the window in terms of APDUs and step the window manually. That's a form of Application Level Framing (ALF). In this case, TXW_MAX_RTE is the cumulative transmit rate of SPMs, ODATA, and RDATA. 👑
16.2. Advancing with Data 💅
okay so the first strategy works out TXW_MAX_RTE from SPMs and from both ODATA and RDATA, and NAKs reset TXW_ADV_IVL_TMR. 🧚 in this mode the transmit window keeps the last TXW_BYTES bytes of data around for repair. that's basically the theoretical max amount of data that could be sent in the time period TXW_SECS. ✨ the wild part is that these timers aren't real-time clocks, they're "data driven". they expire once the amount of data that could be sent during the time they define has actually gone out. that covers the SPM ambient time interval, TXW_ADV_SECS, TXW_SECS, TXW_ADV_IVL, TXW_ADV_IVL_TMR and the join interval. ⏰ the SPM heartbeat timers still run in real-time, though, so they don't get the data-driven treatment.
while TXW_ADV_IVL_TMR is running, a source uses a NAK for ODATA inside the increment window to reset that timer to TXW_ADV_IVL. so advancement gets delayed until no NAKs for data in the increment window have shown up for TXW_ADV_IVL seconds. 🫶 if the transmit window fills up in the meantime, further transmissions get suspended until the window can advance.
A source MUST advance the transmit window across the increment window only upon expiry of TXW_ADV_IVL_TMR.
this mode is intended for non-real-time, messaging applications that depend on receiving complete data, even if it means waiting longer. 📬
16.3. Advancing with Time ⏩
this strategy moves the transmit window in real-time. in this mode TXW_MAX_RTE is calculated from SPMs and ODATA only, so the data throughput rate stays constant, at the cost of using extra bandwidth for repairs. 🚀 TXW_ADV_IVL has the value 0, which advances the window without caring whether NAKs for data in the increment window are still coming in.
in this mode, every timer is treated as a real-time timer. ⏱️
this mode is intended for real-time, streaming applications that depend on receiving timely data, even if it means giving up some completeness. 🎬
16.4. Advancing under explicit application control 🎀
some applications may want more explicit control of the transmit window than the advance-with-data and advance-with-time strategies above provide. An implementation MAY provide this mode of operation and let an application control the window explicitly in terms of APDUs. 🦋
17. Appendix G - Applicability Statement 🌈
okay so, as the introduction said, PGM was designed with a specific class of applications in mind. that's because a general solution for reliable multicast has proven elusive, tbh. the applicability gets narrowed even more by the prototype nature of at least four of the transport elements the protocol uses. those are congestion control, router assist, local retransmission, and a programmatic API for reliable multicast protocols of this class. 🧠 while standardization efforts tackle each of those elements one by one, this publication is meant to encourage experimentation with them in general, and to feed real results from practice back into that standardization process. 🔥
this section briefly describes some of the experimental aspects of PGM and gives non-normative references to a few examples of current practice based on them. 📝
at least 3 different approaches to congestion control can be explored with PGM: a receiver-feedback based approach, a router-assist based approach, and a layer-coding based approach. 💫 the first is supported by the negative acknowledgement mechanism in PGM, augmented by an application-layer acknowledgement mechanism. the second is supported by the router exception processing mechanism in PGM. the third is supported by the FEC mechanisms in PGM. an example of a receiver-feedback based approach is provided in [16], and a proposal for a router-assist based approach was put forward in [17]. 🤔 open issues for researchers include how each of these approaches behaves in the presence of multiple competing sessions of the same discipline or of different disciplines, TCP most notably. they also include how each of them behaves over a particular range of topologies and over a particular range of loads, and how each of them scales as a function of the size of the receiver population.
router assist has applications not just for implosion control and retransmit constraint, as described in this specification, but also for congestion control as described above, and more generally for any feature that may be enhanced by access to per-network-element state and processing. 🌸 the full range of these features is still unexplored, but a general mechanism for providing router assist in a transport-protocol independent way (GRA) is a topic of active research [18]. that effort has been informed mainly by the router assist component of PGM, and implementation and deployment experience with PGM will keep being fed back into the specification and eventual standardization of GRA. 📚 open questions for researchers ([19], [20], [21]) include how router-based state scales relative to the feature benefit obtained, how system-wide factors (such as throughput and retransmit latency) vary with the scale and topology of deployed router assistance, and how incremental deployment considerations affect the tractability of router-assist based features. router assist may have additional implications for congestion control, to the extent that it may be applied in multi-group layered coding schemes to increase the granularity and reduce the latency of receiver-based congestion control. 💜
GRA itself explicitly incorporates elements of active networking. to the extent that the router assist component of PGM is reflected in GRA, experimenting with the narrowly defined network-element functionality of PGM will provide some of the first real-world experience with this promising, if controversial, technology. 🧚♀️
local retransmission is not a new idea in reliable multicast in general, but PGM's specific approach raises interesting questions. PGM locates re-transmitters on the distribution tree for the session, diverts repair requests from network elements to those re-transmitters, and then propagates repairs downward from the repair point on the distribution tree. 🌳 that leads to questions about where to locate re-transmitters in a given topology, how network elements find those re-transmitters, and how to evaluate their efficiency relative to other available sources of retransmissions, most notably the source itself. this particular aspect of PGM is fully specified, but it has only been implemented on the network element side, and it awaits a host-side implementation before questions like these can be addressed. 🙈
PGM presents the opportunity to develop a programming API for reliable multicast applications. that API would reflect both those applications' service requirements and the services PGM provides in support of them that may usefully be made visible above the transport interface. 🍓 at least a couple of host-side implementations of PGM and a concomitant API have been developed for research purposes ([22], [23]). they are available as open source, explicitly for the kind of experimentation described in this section. 🛠️
perhaps the broadest experiment that PGM can enable, in a community of researchers using a reasonable-scale experimental transport protocol, is simply the definition, implementation, and deployment of IP multicast applications for which the reliability PGM provides is a significant enabler. 🌟 experience with such applications will not just illuminate the value of reliable multicast. it will also provoke practical examination of, and responses to, the attendant policy issues (such as peering, billing, access control, firewalls, NATs, etc.). and if successful, it will ultimately encourage wider deployment of IP multicast itself. 🌈👑
18. Abbreviations 📖
ACK Acknowledgment
AFI Address Family Indicator
ALF Application Level Framing
APDU Application Protocol Data Unit
ARQ Automatic Repeat reQuest
DLR Designated Local Repairer
GSI Globally Unique Source Identifier
FEC Forward Error Correction
MD5 Message-Digest Algorithm
MTU Maximum Transmission Unit
NAK Negative Acknowledgment
NCF NAK Confirmation
NLA Network Layer Address
NNAK Null Negative Acknowledgment
ODATA Original Data
POLL Poll Request
POLR Poll Response
RDATA Repair Data
RSN Receive State Notification
SPM Source Path Message
SPMR SPM Request
TG Transmission Group
TGSIZE Transmission Group Size
TPDU Transport Protocol Data Unit
TSDU Transport Service Data Unit
TSI Transport Session Identifier
TSN Transmit State Notification19. Acknowledgements 🫶
the design and specification of PGM has been substantially influenced by reviews and revisions from several people who took the time to read and critique this document. 💖 these include, in alphabetical order:
- Bob Albrightson
- Joel Bion
- Mark Bowles
- Steve Deering
- Tugrul Firatli
- Dan Harkins
- Dima Khoury
- Gerard Newman
- Dave Oran
- Denny Page
- Ken Pillay
- Chetan Rai
- Yakov Rekhter
- Dave Rossetti
- Paul Stirpe
- Brian Whetten
- Kyle York
20. References 📚✨
okay bestie, this is the bibliography, and it's giving research paper energy 🎀 these are all the papers, RFCs, and drafts the spec leans on. I kept every single entry exactly as written, so you can go find them 🔍
[1] B. Whetten, T. Montgomery, S. Kaplan, "A High Performance
Totally Ordered Multicast Protocol", in "Theory and Practice in
Distributed Systems", Springer Verlag LCNS938, 1994.
[2] S. Floyd, V. Jacobson, C. Liu, S. McCanne, L. Zhang, "A
Reliable Multicast Framework for Light-weight Sessions and
Application Level Framing", ACM Transactions on Networking,
November 1996.
[3] J. C. Lin, S. Paul, "RMTP: A Reliable Multicast Transport
Protocol", ACM SIGCOMM August 1996.
[4] Miller, K., Robertson, K., Tweedly, A. and M. White, "Multicast
File Transfer Protocol (MFTP) Specification", Work In Progress.
[5] Deering, S., "Host Extensions for IP Multicasting", STD 5, RFC
1112, August 1989.
[6] Katz, D., "IP Router Alert Option", RFC 2113, February 1997.
[7] C. Partridge, "Gigabit Networking", Addison Wesley 1994.
[8] H. W. Holbrook, S. K. Singhal, D. R. Cheriton, "Log-Based
Receiver-Reliable Multicast for Distributed Interactive
Simulation", ACM SIGCOMM 1995.
[9] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April
1992.
[10] Reynolds, J. and J. Postel, "Assigned Numbers", STD 2, RFC
1700, October 1994.
[11] J. Nonnenmacher, E. Biersack, D. Towsley, "Parity-Based Loss
Recovery for Reliable Multicast Transmission", ACM SIGCOMM
September 1997.
[12] L. Rizzo, "Effective Erasure Codes for Reliable Computer
Communication Protocols", Computer Communication Review, April
1997.
[13] V. Jacobson, "Congestion Avoidance and Control", ACM SIGCOMM
August 1988.
[14] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", BCP, 14, RFC 2119, March 1997.
[15] J. Bolot, T. Turletti, I. Wakeman, "Scalable Feedback Control
for Multicast Video Distribution in the Internet", Proc.
ACM/Sigcomm 94, pp. 58-67.
[16] L. Rizzo, "pgmcc: A TCP-friendly Single-Rate Multicast
Congestion Control Scheme", Proc. of ACM SIGCOMM August 2000.
[17] M. Luby, L. Vicisano, T. Speakman. "Heterogeneous multicast
congestion control based on router packet filtering", RMT
working group, June 1999, Pisa, Italy.
[18] Cain, B., Speakman, T. and D. Towsley, "Generic Router Assist
(GRA) Building Block, Motivation and Architecture", Work In
Progress.
[19] C. Papadopoulos, and E. Laliotis,"Incremental Deployment of a
Router-assisted Reliable Multicast Scheme,", Proc. of Networked
Group Communications (NGC2000), Stanford University, Palo Alto,
CA. November 2000.
[20] C. Papadopoulos, "RAIMS: an Architecture for Router-Assisted
Internet Multicast Services." Presented at ETH, Zurich,
Switzerland, October 23 2000.
[21] J. Chesterfield, A. Diana, A. Greenhalgh, M. Lad, and M. Lim,
"A BSD Router Implementation of PGM",
http://www.cs.ucl.ac.uk/external/m.lad/rpgm/
[22] L. Rizzo, "A PGM Host Implementation for FreeBSD",
http://www.iet.unipi.it/~luigi/pgm.html
[23] M. Psaltaki, R. Araujo, G. Aldabbagh, P. Kouniakis, and A.
Giannopoulos, "Pragmatic General Multicast (PGM) host
implementation for FreeBSD.",
http://www.cs.ucl.ac.uk/research/darpa/pgm/PGM_FINAL.html21. Authors' Addresses 🦋
these are the people who built this protocol, the actual legends 👑 contact details are kept exactly as they were, so you can slide into their inboxes (professionally, obvi 💅)
Tony Speakman
EMail: speakman@cisco.com
Dino Farinacci
Procket Networks
3850 North First Street
San Jose, CA 95134
USA
EMail: dino@procket.com
Steven Lin
Juniper Networks
1194 N. Mathilda Ave.
Sunnyvale, CA 94086
USA
EMail: steven@juniper.net
Alex Tweedly
EMail: agt@cisco.com
Nidhi Bhaskar
EMail: nbhaskar@cisco.com
Richard Edmonstone
EMail: redmonst@cisco.com
Rajitha Sumanasekera
EMail: rajitha@cisco.com
Lorenzo Vicisano
Cisco Systems, Inc.
170 West Tasman Drive,
San Jose, CA 95134
USA
EMail: lorenzo@cisco.com
Jon Crowcroft
Department of Computer Science
University College London
Gower Street
London WC1E 6BT
UK
EMail: j.crowcroft@cs.ucl.ac.uk
Jim Gemmell
Microsoft Bay Area Research Center
301 Howard Street, #830
San Francisco, CA 94105
USA
EMail: jgemmell@microsoft.com
Dan Leshchiner
Tibco Software
3165 Porter Dr.
Palo Alto, CA 94304
USA
EMail: dleshc@tibco.com
Michael Luby
Digital Fountain, Inc.
39141 Civic Center Drive
Fremont CA 94538
USA
EMail: luby@digitalfountain.com
Todd L. Montgomery
Talarian Corporation
124 Sherman Ave.
Morgantown, WV 26501
USA
EMail: todd@talarian.com
Luigi Rizzo
Dip. di Ing. dell'Informazione
Universita` di Pisa
via Diotisalvi 2
56126 Pisa
Italy
EMail: luigi@iet.unipi.it22. Full Copyright Statement ⚖️
okay this part is legal stuff, so I'm keeping the wording exactly as it is 🫶 it's the rules for copying and sharing the doc, and the bit about who's protected and what's not promised
Copyright (C) The Internet Society (2001). All Rights Reserved.
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.
The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement 🌸
last one, and it's a sweet one 🥹 the RFC Editor function is funded by the Internet Society, so a big thank you to them for keeping the lights on ✨
Funding for the RFC Editor function is currently provided by the
Internet Society.That's the whole thing, bestie, we made it through all 22 parts! 🎉🌈💖
📦 where this page comes from
- ietf: rfc3208 2001-12
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms