[ RFC Index | RFC Search | Usenet FAQs | Web FAQs | Documents | Cities ]
Alternate Formats: rfc3208.txt | rfc3208.txt.pdf
RFC 3208 - PGM Reliable Transport Protocol Specification
|
 |
RFC3208 - PGM Reliable Transport Protocol Specification
Network Working Group T. Speakman
Request for Comments: 3208 Cisco Systems
Category: Experimental J. Crowcroft
UCL
J. Gemmell
Microsoft
D. Farinacci
Procket Networks
S. Lin
Juniper Networks
D. Leshchiner
TIBCO Software
M. Luby
Digital Fountain
T. Montgomery
Talarian Corporation
L. Rizzo
University of Pisa
A. Tweedly
N. Bhaskar
R. Edmonstone
R. Sumanasekera
L. Vicisano
Cisco Systems
December 2001
PGM Reliable Transport Protocol Specification
Status of this Memo
This memo defines an Experimental Protocol for the Internet
community. It does not specify an Internet standard of any kind.
Discussion and suggestions for improvement are requested.
Distribution of this memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2001). All Rights Reserved.
Abstract
Pragmatic General Multicast (PGM) is a reliable multicast transport
protocol for applications that require ordered or unordered,
duplicate-free, multicast data delivery from multiple sources to
multiple receivers. PGM guarantees that a receiver in the group
either receives all data packets from transmissions and repairs, or
is able to detect unrecoverable data packet loss. PGM is
specifically intended as a workable solution for multicast
applications with basic reliability requirements. 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 ................................... 111
Nota Bene:
The publication of this specification is intended to freeze the
definition of PGM in the interest of fostering both ongoing and
prospective experimentation with the protocol. The intent of that
experimentation is to provide experience with the implementation and
deployment of a reliable multicast protocol of this class so as to be
able to feed that experience back into the longer-term
standardization process underway in the Reliable Multicast Transport
Working Group of the IETF. Appendix G provides more specific detail
on the scope and status of some of this experimentation. Reports of
experiments include [16-23]. Additional results and new
experimentation are encouraged.
1. Introduction and Overview
A variety of reliable protocols have been proposed for multicast data
delivery, each with an emphasis on particular types of applications,
network characteristics, or definitions of reliability ([1], [2],
[3], [4]). In this tradition, Pragmatic General Multicast (PGM) is a
reliable transport protocol for applications that require ordered or
unordered, duplicate-free, multicast data delivery from multiple
sources to multiple receivers.
PGM is specifically intended as a workable solution for multicast
applications with basic reliability requirements rather than as a
comprehensive solution for multicast applications with sophisticated
ordering, agreement, and robustness requirements. Its central design
goal is simplicity of operation with due regard for scalability and
network efficiency.
PGM has no notion of group membership. It simply provides reliable
multicast data delivery within a transmit window advanced by a source
according to a purely local strategy. Reliable delivery is provided
within a source's transmit window from the time a receiver joins the
group until it departs. PGM guarantees that a receiver in the group
either receives all data packets from transmissions and repairs, or
is able to detect unrecoverable data packet loss. PGM supports any
number of sources within a multicast group, each fully identified by
a globally unique Transport Session Identifier (TSI), but since these
sources/sessions operate entirely independently of each other, this
specification is phrased in terms of a single source and extends
without modification to multiple sources.
More specifically, PGM is not intended for use with applications that
depend either upon acknowledged delivery to a known group of
recipients, or upon total ordering amongst multiple sources.
Rather, PGM is best suited to those applications in which members may
join and leave at any time, and that are either insensitive to
unrecoverable data packet loss or are prepared to resort to
application recovery in the event. Through its optional extensions,
PGM provides specific mechanisms to support applications as disparate
as stock and news updates, data conferencing, low-delay real-time
video transfer, and bulk data transfer.
In the following text, transport-layer originators of PGM data
packets are referred to as sources, transport-layer consumers of PGM
data packets are referred to as receivers, and network-layer entities
in the intervening network are referred to as network elements.
Unless otherwise specified, the term "repair" will be used to
indicate both the actual retransmission of a copy of a missing packet
or the transmission 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] and
indicate requirement levels for compliant PGM implementations.
1.1. Summary of Operation
PGM runs over a datagram multicast protocol such as IP multicast [5].
In the normal course of data transfer, a source multicasts sequenced
data packets (ODATA), and receivers unicast selective negative
acknowledgments (NAKs) for data packets detected to be missing from
the expected sequence. Network elements forward NAKs PGM-hop-by-
PGM-hop to the source, and confirm each hop by multicasting a NAK
confirmation (NCF) in response on the interface on which the NAK was
received. Repairs (RDATA) may be provided either by the source
itself or by a Designated Local Repairer (DLR) in response to a NAK.
Since NAKs provide the sole mechanism for reliability, PGM is
particularly sensitive to their loss. To minimize NAK loss, PGM
defines a network-layer hop-by-hop procedure for reliable NAK
forwarding.
Upon detection of a missing data packet, a receiver repeatedly
unicasts a NAK to the last-hop PGM network element on the
distribution tree from the source. A receiver repeats this NAK until
it receives a NAK confirmation (NCF) multicast to the group from that
PGM network element. That network element responds with an NCF to
the first occurrence of the NAK and any further retransmissions of
that same NAK from any receiver. In turn, the network element
repeatedly forwards the NAK to the upstream PGM network element on
the reverse of the distribution path from the source of the original
data packet until it also receives an NCF from that network element.
Finally, the source itself receives and confirms the NAK by
multicasting an NCF to the group.
While NCFs are multicast to the group, they are not propagated by PGM
network elements since they act as hop-by-hop confirmations.
To avoid NAK implosion, PGM specifies procedures for subnet-based NAK
suppression amongst receivers and NAK elimination within network
elements. The usual result is the propagation of just one copy of a
given NAK along the reverse of the distribution path from any network
with directly connected receivers to a source.
The net effect is that unicast NAKs return from a receiver to a
source on the reverse of the path on which ODATA was forwarded, that
is, on the reverse of the distribution tree from the source. More
specifically, they return through exactly the same sequence of PGM
network elements through which ODATA was forwarded, but in reverse.
The reasons for handling NAKs this way will become clear in the
discussion of constraining repairs, but first it's necessary to
describe the mechanisms for establishing the requisite source path
state in PGM network elements.
To establish source path state in PGM network elements, the basic
data transfer operation is augmented by Source Path Messages (SPMs)
from a source, periodically interleaved with ODATA. SPMs function
primarily to establish source path state for a given TSI in all PGM
network elements on the distribution tree from the source. PGM
network elements use this information to address returning unicast
NAKs directly to the upstream PGM network element toward the source,
and thereby insure that NAKs return from a receiver to a source on
the reverse of the distribution path for the TSI.
SPMs are sent by a source at a rate that serves to maintain up-to-
date PGM neighbor information. In addition, SPMs complement the role
of DATA packets in provoking further NAKs from receivers, and
maintaining receive window state in the receivers.
As a further efficiency, PGM specifies procedures for the constraint
of repairs by network elements so that they reach only those network
segments containing group members that did not receive the original
transmission. As NAKs traverse the reverse of the ODATA path
(upward), they establish repair state in the network elements which
is used in turn to constrain the (downward) forwarding of the
corresponding RDATA.
Besides procedures for the source to provide repairs, PGM also
specifies options and procedures that permit designated local
repairers (DLRs) to announce their availability and to redirect
repair requests (NAKs) to themselves rather than to the original
source. In addition to these conventional procedures for loss
recovery through selective ARQ, Appendix A specifies Forward Error
Correction (FEC) procedures for sources to provide and receivers to
request general error correcting parity packets rather than selective
retransmissions.
Finally, since PGM operates without regular return traffic from
receivers, conventional feedback mechanisms for transport flow and
congestion control cannot be applied. Appendix B specifies 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 to bound the bandwidth consumed
by PGM transport sessions and to define the transmit window
maintained by the source.
PGM defines four basic packet types: three that flow downstream
(SPMs, DATA, NCFs), and one that flows upstream (NAKs).
1.2. Design Goals and Constraints
PGM has been designed to serve that broad range of multicast
applications that have relatively simple reliability requirements,
and to do so in a way that realizes the much advertised but often
unrealized network efficiencies of multicast data transfer. The
usual impediments to realizing these 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 conventionally
achieved through an end-to-end protocol in which a source (implicitly
or explicitly) solicits receipt confirmation from a receiver, and the
receiver responds positively or negatively. While the frequency of
negative acknowledgments is a function of the reliability of the
network and the receiver's resources (and so, potentially quite low),
the frequency of positive acknowledgments is fixed at at least the
rate at which the transmit window is advanced, and usually more
often.
Negative acknowledgments primarily determine repairs and reliability.
Positive acknowledgments primarily determine transmit buffer
management.
When these principles are extended without modification to multicast
protocols, the result, at least for positive acknowledgments, is a
burden of positive acknowledgments transmitted to the source that
quickly threatens to overwhelm it as the number of receivers grows.
More succinctly, ACK implosion keeps ACK-based reliable multicast
protocols from scaling well.
One of the goals of PGM is to get as strong a definition of
reliability as possible from as simple a protocol as possible. ACK
implosion can be addressed in a variety of effective but complicated
ways, most of which require re-transmit capability from other than
the original source.
An alternative is to dispense with positive acknowledgments
altogether, and to resort to other strategies for buffer management
while retaining negative acknowledgments for repairs and reliability.
The approach taken in PGM is to retain negative acknowledgments, but
to dispense with positive acknowledgments and resort instead to
timeouts at the source to manage transmit resources.
The definition of reliability with PGM is a direct consequence of
this design decision. PGM guarantees that a receiver either receives
all data packets from transmissions and repairs, or is able to detect
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 minimizes the probability that a receiver will
detect a missing data packet so late that the packet is unavailable
for repair either from the source or from a designated local repairer
(DLR). Without ACKs and knowledge of group membership, however, PGM
cannot eliminate this possibility.
1.2.2. Group Membership
A second consequence of eliminating ACKs is that knowledge of group
membership is neither required nor provided by the protocol.
Although a source may receive some PGM packets (NAKs for instance)
from some receivers, the identity of the receivers does not figure in
the processing of those packets. Group membership MAY change during
the course of a PGM transport session without the knowledge of or
consequence to the source or the remaining receivers.
1.2.3. Efficiency
While PGM avoids the implosion of positive acknowledgments simply by
dispensing with ACKs, the implosion of negative acknowledgments is
addressed directly.
Receivers observe a random back-off prior to generating a NAK during
which interval the NAK is suppressed (i.e. it is not sent, but the
receiver acts as if it had sent it) by the receiver upon receipt of a
matching NCF. In addition, PGM network elements eliminate duplicate
NAKs received on different interfaces on the same network element.
The combination of these two strategies usually results in the source
receiving just a single NAK for any given lost data packet.
Whether a repair is provided from a DLR or the original source, it is
important to constrain that repair to only those network segments
containing members that negatively acknowledged the original
transmission rather than propagating it throughout the group. PGM
specifies procedures for network elements to use the pattern of NAKs
to define a sub-tree within the group upon which to forward the
corresponding repair so that it reaches only those receivers that
missed it in the first place.
1.2.4. Simplicity
PGM is designed to achieve the greatest improvement in reliability
(as compared to the usual UDP) with the least complexity. As a
result, PGM does NOT address conference control, global ordering
amongst multiple sources in the group, nor recovery from network
partitions.
1.2.5. Operability
PGM is designed to function, albeit with less efficiency, even when
some or all of the network elements in the multicast tree have no
knowledge of PGM. To that end, all PGM data packets can be
conventionally multicast routed by non-PGM network elements with no
loss of functionality, but with some inefficiency in the propagation
of RDATA and NCFs.
In addition, since NAKs are unicast to the last-hop PGM network
element and NCFs are multicast to the group, NAK/NCF operation is
also consistent across non-PGM network elements. Note that for NAK
suppression to be most effective, receivers should always have a PGM
network element as a first hop network element between themselves and
every path to every PGM source. If receivers are several hops
removed from the first PGM network element, the efficacy of NAK
suppression may degrade.
1.3. Options
In addition to the basic data transfer operation described above, PGM
specifies several end-to-end options to address specific application
requirements. PGM specifies options to support fragmentation, late
joining, redirection, Forward Error Correction (FEC), reachability,
and session synchronization/termination/reset. Options MAY be
appended to PGM data packet headers only by their original
transmitters. While they MAY be interpreted by network elements,
options are neither added nor removed by network elements.
All options are receiver-significant (i.e., they must be interpreted
by receivers). Some options are also network-significant (i.e., they
must be interpreted by network elements).
Fragmentation MAY be used in conjunction with data packets to allow a
transport-layer entity at the source to break up application-layer
data packets into multiple PGM data packets to conform with the
maximum transmission unit (MTU) supported by the network layer.
Late joining allows a source to indicate whether or not receivers may
request all available repairs when they initially join a particular
transport session.
Redirection MAY be used in conjunction with Poll Responses to allow a
DLR to respond to normal NCFs or POLLs with a redirecting POLR
advertising its own address as an alternative re-transmitter to the
original source.
FEC techniques MAY be applied by receivers to use source-provided
parity packets rather than selective retransmissions to effect loss
recovery.
2. Architectural Description
As an end-to-end transport protocol, PGM specifies packet formats and
procedures for sources to transmit and for receivers to receive data.
To enhance the efficiency of this data transfer, PGM also specifies
packet formats and procedures for network elements to improve the
reliability of NAKs and to constrain the propagation of repairs. The
division of these functions is described in this section and expanded
in detail in the next section.
2.1. Source Functions
Data Transmission
Sources multicast ODATA packets to the group within the
transmit window at a given transmit rate.
Source Path State
Sources multicast SPMs to the group, interleaved with ODATA if
present, to establish source path state in PGM network
elements.
NAK Reliability
Sources multicast NCFs to the group in response to any NAKs
they receive.
Repairs
Sources multicast RDATA packets to the group in response to
NAKs received for data packets within the transmit window.
Transmit Window Advance
Sources MAY advance the trailing edge of the window according
to one of a number of strategies. Implementations MAY support
automatic adjustments such as keeping the window at a fixed
size in bytes, a fixed number of packets or a fixed real time
duration. In addition, they MAY optionally delay window
advancement based on NAK-silence for a certain period. Some
possible strategies are outlined later in this document.
2.2. Receiver Functions
Source Path State
Receivers use SPMs to determine the last-hop PGM network
element for a given TSI to which to direct their NAKs.
Data Reception
Receivers receive ODATA within the transmit window and
eliminate any duplicates.
Repair Requests
Receivers unicast NAKs to the last-hop PGM network element (and
MAY optionally multicast a NAK with TTL of 1 to the local
group) for data packets within the receive window detected to
be missing from the expected sequence. A receiver MUST
repeatedly transmit a given NAK until it receives a matching
NCF.
NAK Suppression
Receivers suppress NAKs for which a matching NCF or NAK is
received during the NAK transmit back-off interval.
Receive Window Advance
Receivers immediately advance their receive windows upon
receipt of any PGM data packet or SPM within the transmit
window that advances the receive window.
2.3. Network Element Functions
Network elements forward ODATA without intervention.
Source Path State
Network elements intercept SPMs and use them to establish
source path state for the corresponding TSI before multicast
forwarding them in the usual way.
NAK Reliability
Network elements multicast NCFs to the group in response to any
NAK they receive. For each NAK received, network elements
create repair state recording the transport session identifier,
the sequence number of the NAK, and the input interface on
which the NAK was received.
Constrained NAK Forwarding
Network elements repeatedly unicast forward only the first copy
of any NAK they receive to the upstream PGM network element on
the distribution path for the TSI until they receive an NCF in
response. In addition, they MAY 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 (i.e., that has been forwarded
either by themselves or a neighboring PGM network element), and
respond with a matching NCF.
Constrained RDATA Forwarding
Network elements use NAKs to maintain repair state consisting
of a list of interfaces upon which a given NAK was received,
and they forward the corresponding RDATA only on these
interfaces.
NAK Anticipation
If a network element hears an upstream NCF (i.e., on the
upstream interface for the distribution tree for the TSI), it
establishes repair state without outgoing interfaces in
anticipation of responding to and eliminating duplicates of the
NAK that may arrive from downstream.
3. Terms and Concepts
Before proceeding from the preceding overview to the detail in the
subsequent Procedures, this section presents some concepts and
definitions that make that detail more intelligible.
3.1. Transport Session Identifiers
Every PGM packet is identified by a:
TSI transport session identifier
TSIs MUST be globally unique, and only one source at a time may act
as the source for a transport session. (Note that repairers do not
change the TSI in any RDATA they transmit). TSIs are composed of the
concatenation of a globally unique source identifier (GSI) and a
source-assigned data-source port.
Since all PGM packets originated by receivers are in response to PGM
packets originated by a source, receivers simply echo the TSI heard
from the source in any corresponding packets they originate.
Since all PGM packets originated by network elements are in response
to PGM packets originated by a receiver, network elements simply echo
the TSI heard from the receiver in any corresponding packets they
originate.
3.2. Sequence Numbers
PGM uses a circular sequence number space from 0 through ((2**32) -
1) to identify and order ODATA packets. Sources MUST number ODATA
packets in unit increments in the order in which the corresponding
application data is submitted for transmission. Within a transmit or
receive window (defined below), a sequence number x is "less" or
"older" than sequence number y if it numbers an ODATA packet
preceding ODATA packet y, and a sequence number y is "greater" or
"more recent" than sequence number x if it numbers an ODATA packet
subsequent to ODATA packet x.
3.3. Transmit Window
The description of the operation of PGM rests fundamentally on the
definition of the source-maintained transmit window. This definition
in turn is derived directly from the amount of transmitted data (in
seconds) a source retains for repair (TXW_SECS), and the maximum
transmit rate (in bytes/second) maintained by a source to regulate
its bandwidth utilization (TXW_MAX_RTE).
In terms of sequence numbers, the transmit window is the range of
sequence numbers consumed by the source for sequentially numbering
and transmitting the most recent TXW_SECS of ODATA packets. The
trailing (or left) edge of the transmit window (TXW_TRAIL) is defined
as the sequence number of the oldest data packet available for repair
from a source. The leading (or right) edge of the transmit window
(TXW_LEAD) is defined as the sequence number of the most recent data
packet a source has transmitted.
The size of the transmit window in sequence numbers (TXW_SQNS) (i.e.,
the difference between the leading and trailing edges plus one) MUST
be no greater than half the PGM sequence number space less one.
When TXW_TRAIL is equal to TXW_LEAD, the transmit window size is one.
When TXW_TRAIL is equal to TXW_LEAD plus one, the transmit window
size is empty.
3.4. Receive Window
The receive window at the receivers is determined entirely by PGM
packets from the source. That is, a receiver simply obeys what the
source tells it in terms of window state and advancement.
For a given transport session identified by a TSI, a receiver
maintains:
RXW_TRAIL the sequence number defining the trailing edge of the
receive window, the sequence number (known from data
packets and SPMs) of the oldest data packet available
for repair from the source
RXW_LEAD the sequence number defining the leading edge of the
receive window, the greatest sequence number of any
received data packet within the transmit window
The receive window is the range of sequence numbers a receiver is
expected to use to identify receivable ODATA.
A data packet is described as being "in" the receive window if its
sequence number is in the receive window.
The receive window is advanced by the receiver when it receives an
SPM or ODATA packet within the transmit window that increments
RXW_TRAIL. Receivers also advance their receive windows upon receipt
of any PGM data packet within the receive window that advances the
receive window.
3.5. Source Path State
To establish the repair state required to constrain RDATA, it's
essential that NAKs return from a receiver to a source on the reverse
of the distribution tree from the source. That is, they must return
through the same sequence of PGM network elements through which the
ODATA was forwarded, but in reverse. There are two reasons for this,
the less obvious one being by far the more important.
The first and obvious reason is that RDATA is forwarded on the same
path as ODATA and so repair state must be established on this path if
it is to constrain the propagation of RDATA.
The second and less obvious reason is that in the absence of repair
state, PGM network elements do NOT forward RDATA, so the default
behavior is to discard repairs. If repair state is not properly
established for interfaces on which ODATA went missing, then
receivers on those interfaces will continue to NAK for lost data and
ultimately experience unrecoverable data loss.
The principle function of SPMs is to provide the source path state
required for PGM network elements to forward NAKs from one PGM
network element to the next on the reverse of the distribution tree
for the TSI, establishing repair state each step of the way. This
source path state is simply the address of the upstream PGM network
element on the reverse of the distribution tree for the TSI. That
upstream PGM network element may be more than one subnet hop away.
SPMs establish the identity of the upstream PGM network element on
the distribution tree for each TSI in each group in each PGM network
element, a sort of virtual PGM topology. So although NAKs are
unicast addressed, they are NOT unicast routed by PGM network
elements in the conventional sense. Instead PGM network elements use
the source path state established by SPMs to direct NAKs PGM-hop-by-
PGM-hop toward the source. The idea is to constrain NAKs to the pure
PGM topology spanning the more heterogeneous underlying topology of
both PGM and non-PGM network elements.
The result is repair state in every PGM network element between the
receiver and the source so that the corresponding RDATA is never
discarded by a PGM network element for lack of repair state.
SPMs also maintain transmit window state in receivers by advertising
the trailing and leading edges of the transmit window (SPM_TRAIL and
SPM_LEAD). In the absence of data, SPMs MAY be used to close the
transmit window in time by advancing the transmit window until
SPM_TRAIL is equal to SPM_LEAD plus one.
3.6. Packet Contents
This section just provides enough short-hand to make the Procedures
intelligible. For the full details of packet contents, please refer
to Packet Formats below.
3.6.1. Source Path Messages
3.6.1.1. SPMs
SPMs are transmitted by sources to establish source-path state in PGM
network elements, and to provide transmit-window state in receivers.
SPMs are multicast to the group and contain:
SPM_TSI the source-assigned TSI for the session to which the
SPM corresponds
SPM_SQN a sequence number assigned sequentially by the source
in unit increments and scoped by SPM_TSI
Nota Bene: this is an entirely separate sequence than is used to
number ODATA and RDATA.
SPM_TRAIL the sequence number defining the trailing edge of the
source's transmit window (TXW_TRAIL)
SPM_LEAD the sequence number defining the leading edge of the
source's transmit window (TXW_LEAD)
SPM_PATH the network-layer address (NLA) of the interface on
the PGM network element on which the SPM is forwarded
3.6.2. Data Packets
3.6.2.1. ODATA - Original Data
ODATA packets are transmitted by sources to send application data to
receivers.
ODATA packets are multicast to the group and contain:
OD_TSI the globally unique source-assigned TSI
OD_TRAIL the sequence number defining the trailing edge of the
source's transmit window (TXW_TRAIL)
OD_TRAIL makes the protocol more robust in the face of
lost SPMs. By including the trailing edge of the
transmit window on every data packet, receivers that
have missed any SPMs that advanced the transmit window
can still detect the case, recover the application,
and potentially re-synchronize to the transport
session.
OD_SQN a sequence number assigned sequentially by the source
in unit increments and scoped by OD_TSI
3.6.2.2. RDATA - Repair Data
RDATA packets are repair packets transmitted by sources or DLRs in
response to NAKs.
RDATA packets are multicast to the group and contain:
RD_TSI OD_TSI of the ODATA packet for which this is a repair
RD_TRAIL the sequence number defining the trailing edge of the
source's transmit window (TXW_TRAIL). This is updated
to the most current value when the repair is sent, so
it is not necessarily the same as OD_TRAIL of the
ODATA packet for which this is a repair
RD_SQN OD_SQN of the ODATA packet for which this is a repair
3.6.3. Negative 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_TSI of the ODATA packet for which a repair is
requested
NAK_SQN OD_SQN of the ODATA packet for which a repair is
requested
NAK_SRC the unicast NLA of the original source of the missing
ODATA.
NAK_GRP the multicast group NLA
3.6.3.2. NNAKs - Null Negative Acknowledgments
NNAKs are transmitted by a DLR that receives NAKs redirected to it by
either receivers or network elements to provide flow-control feed-
back to a source.
NNAKs are unicast (PGM-hop-by-PGM-hop) to the source and contain:
NNAK_TSI NAK_TSI of the corresponding re-directed NAK.
NNAK_SQN NAK_SQN of the corresponding re-directed NAK.
NNAK_SRC NAK_SRC of the corresponding re-directed NAK.
NNAK_GRP NAK_GRP of the corresponding re-directed NAK.
3.6.4. Negative 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_TSI of the NAK being confirmed
NCF_SQN NAK_SQN of the NAK being confirmed
NCF_SRC NAK_SRC of the NAK being confirmed
NCF_GRP NAK_GRP of the NAK being confirmed
3.6.5. Option Encodings
OPT_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 invalidated
4. Procedures - General
Since SPMs, NCFs, and RDATA must be treated conditionally by PGM
network elements, they must be distinguished from other packets in
the chosen multicast network protocol if PGM network elements are to
extract them from the usual switching path.
The most obvious way for network elements to achieve this is to
examine every packet in the network for the PGM transport protocol
and packet types. However, the overhead of this approach is costly
for high-performance, multi-protocol network elements. An
alternative, and a requirement for PGM over IP multicast, is that
SPMs, NCFs, and RDATA MUST be transmitted with the IP Router Alert
Option [6]. This option gives network elements a network-layer
indication that a packet should be extracted from IP switching for
more detailed processing.
5. Procedures - Sources
5.1. Data Transmission
Since PGM relies on a purely rate-limited transmission strategy in
the source to bound the bandwidth consumed by PGM transport sessions,
an assortment of techniques is assembled here to make that strategy
as 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 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
In the absence of data to transmit, a source SHOULD transmit SPMs at
a decaying rate in order to assist early detection of lost data, to
maintain current source path state in PGM network elements, and to
maintain current receive window state in the receivers.
In this scheme [8], a source maintains an inter-heartbeat timer
IHB_TMR which times the interval between the most recent packet
(ODATA, RDATA, or SPM) transmission and the next heartbeat
transmission. IHB_TMR is initialized to a minimum interval IHB_MIN
after the transmission of any data packet. If IHB_TMR expires, the
source transmits a heartbeat SPM and initializes IHB_TMR to double
its previous value. The transmission of consecutive heartbeat SPMs
doubles IHB each time up to a maximum interval IHB_MAX. The
transmission of any data packet initializes IHB_TMR to IHB_MIN once
again. The effect is to provoke prompt detection of missing packets
in the absence of data to transmit, and to do so with minimal
bandwidth overhead.
5.1.6. Ambient and Heartbeat SPMs
Ambient and heartbeat SPMs are described as driven by separate timers
in this specification to highlight their contrasting functions.
Ambient SPMs are driven by a count-down timer that expires regularly
while heartbeat SPMs are driven by a count-down timer that keeps
being reset by data, and the interval of which changes once it begins
to expire. The ambient SPM timer is just counting down in real-time
while the heartbeat timer is measuring the inter-data-packet
interval.
In the presence of data, no heartbeat SPMs will be transmitted since
the transmission of data keeps setting the IHB_TMR back to its
initial value. At the same time however, ambient SPMs MUST be
interleaved into the data as a matter of course, not necessarily as a
heartbeat mechanism. This ambient transmission of SPMs is REQUIRED
to keep the distribution tree information in the network current and
to allow new receivers to synchronize with the session.
An implementation SHOULD de-couple ambient and heartbeat SPM timers
sufficiently to permit them to be configured independently of each
other.
5.2. Negative Acknowledgment Confirmation
A source MUST immediately multicast an NCF in response to any NAK it
receives. The NCF is REQUIRED since the alternative of responding
immediately with RDATA would not allow other PGM network elements on
the same subnet to do NAK anticipation, nor would it allow DLRs on
the same subnet to provide repairs. A source SHOULD be able to
detect a NAK storm and adopt countermeasure 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.
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.
In the interest of increasing the efficiency of a particular RDATA
packet, a source MAY delay RDATA transmission to accommodate the
arrival of NAKs from the whole loss 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
A receiver SHOULD initiate data reception beginning with the first
data packet it receives within the advertised transmit window. This
packet's sequence number (ODATA_SQN) temporarily defines the trailing
edge of the transmit window from the receiver's perspective. That
is, it is assigned to RXW_TRAIL_INIT within the receiver, and until
the trailing edge sequence number advertised in subsequent packets
(SPMs or ODATA or RDATA) increments past RXW_TRAIL_INIT, the receiver
MUST only request repairs for sequence numbers subsequent to
RXW_TRAIL_INIT. Thereafter, it MAY request repairs anywhere in the
transmit window. This temporary restriction on repair requests
prevents receivers from requesting a potentially large amount of
history when they first begin to receive a given PGM transport
session.
Note that the JOIN option, discussed later, MAY be used to provide a
different value for RXW_TRAIL_INIT.
Receiving and discarding data packets
Within a given transport session, a receiver MUST accept any ODATA or
RDATA packets within the receive window. A receiver MUST discard any
data packet that duplicates one already received in the transmit
window. A receiver MUST discard any data packet outside of the
receive window.
Contiguous data
Contiguous data is comprised of those data packets within the receive
window that have been received and are in the range from RXW_TRAIL up
to (but not including) the first missing sequence number in the
receive window. The most recently received data packet of contiguous
data defines the leading edge of contiguous data.
As its default mode of operation, a receiver MUST deliver only
contiguous data packets to the application, and it MUST do so in the
order defined by those data packets' sequence numbers. This provides
applications with a reliable ordered data flow.
Non contiguous data
PGM receiver implementations MAY optionally provide a mode of
operation in which data is delivered to an application in the order
received. However, the implementation MUST only deliver complete
application protocol data units (APDUs) to the application. That is,
APDUs that have been fragmented into different TPDUs MUST be
reassembled before delivery to the application.
6.2. Source Path Messages
Receivers MUST receive and sequence SPMs for any TSI they are
receiving. An SPM is in sequence if its sequence number is greater
than that of the most recent in-sequence SPM and within half the PGM
number space. Out-of-sequence SPMs MUST be discarded.
For each TSI, receivers MUST use the most recent SPM to determine the
NLA of the upstream PGM network element for use in NAK addressing. A
receiver MUST NOT initiate repair requests until it has received at
least one SPM for the corresponding TSI.
Since SPMs require per-hop processing, it is likely that they will be
forwarded at a slower rate than data, and that they will arrive out
of sync with the data stream. In this case, the window information
that the SPMs carry will be out of date. Receivers SHOULD expect
this to be the case and SHOULD detect it by comparing the packet lead
and trail values with the values the receivers have stored for lead
and trail. If the SPM packet values are less, they SHOULD be
ignored, but the rest of the packet SHOULD be processed as normal.
6.3. Data Recovery by Negative Acknowledgment
Detecting missing data packets
Receivers MUST detect gaps in the expected data sequence in the
following manners:
by comparing the sequence number on the most recently received
ODATA or RDATA packet with the leading edge of contiguous data
by comparing SPM_LEAD of the most recently received SPM with the
leading edge of contiguous data
In both cases, if the receiver has not received all intervening data
packets, it MAY initiate selective NAK generation for each missing
sequence number.
In addition, a receiver may detect a single missing data packet by
receiving an NCF or multicast NAK for a data packet within the
transmit window which it has not received. In this case it MAY
initiate 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 to achieve this is to assume loss only
after the reception of N packets with sequence numbers higher than
those of the (assumed) lost packets. A possible value for N is 2.
This method SHOULD be 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 is
the cycle of:
waiting for a random period of time (NAK_RB_IVL) while listening
for matching NCFs or NAKs
transmitting a NAK if a matching NCF or NAK is not heard
waiting a period (NAK_RPT_IVL) for a matching NCF and recommencing
NAK generation if the matching NCF is not received
waiting a period (NAK_RDATA_IVL) for data and recommencing NAK
generation if the matching data is not received
The entire generation process can be summarized by the following
state machine:
|
| 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)
Cancellation
In any state, receipt of matching RDATA or ODATA completes data
recovery and successful exit from the state machine. State
transition stops any running timers.
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 is requesting an equal or
larger number of parity packets.
When a receiver has to transmit a sequence of NAKs, it SHOULD
transmit the NAKs in order from oldest to 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 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 is not
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 NAK_DATA_RETRIES / NAK_NCF_RETRIES being
exceeded. Cancellation of NAK generation indicates unrecoverable
data loss.
Receiving NCFs and multicast NAKs
A receiver MUST discard any NCFs or NAKs it hears for data packets
outside the transmit window or for data packets it has received.
Otherwise they are treated as appropriate for the current repair
state.
7. Procedures - Network Elements
7.1. Source Path State
Upon receipt of an in-sequence SPM, a network element records the
Source Path Address SPM_PATH with the multicast routing information
for the TSI. If the receiving network element is on the same subnet
as the 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: In order to avoid creating multicast routing state for
PGM network elements across non-PGM-capable clouds, the network-
header source address of NCFs transmitted by network elements MUST
be set to the ODATA source's NLA, not the network element's NLA as
might be expected.
Network elements should be able to detect a NAK storm and adopt
counter-measure 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 is not already listed.
7.3. Constrained NAK Forwarding
The NAK forwarding procedures for network elements are quite similar
to those for receivers, but three important differences should be
noted.
First, network elements do NOT back off before forwarding a NAK
(i.e., there is no NAK_BO_IVL) since the resulting delay of the NAK
would compound with each hop. Note that NAK arrivals will be
randomized by the receivers from which they originate, and this
factor in conjunction with NAK anticipation and elimination will
combine to forestall NAK storms on subnets with a dense network
element population.
Second, network elements do NOT retry confirmed NAKs if RDATA is not
seen; they simply discard the repair state and rely on receivers to
re-request the repair. This approach keeps the repair state in the
network elements relatively ephemeral and responsive to underlying
routing changes.
Third, note that ODATA does NOT cancel NAK forwarding in network
elements since it is switched by network elements without transport-
layer intervention.
Nota Bene: Once confirmed by an NCF, network elements discard NAK
packets; they are NOT retained in network elements beyond this
forwarding operation.
NAK forwarding requires that a network element listen to NCFs for the
same transport session. NAK forwarding also requires that a network
element observe two time out intervals for any given NAK (i.e., per
NAK_TSI and NAK_SQN): NAK_RPT_IVL and NAK_RDATA_IVL.
The NAK repeat interval NAK_RPT_IVL, limits the length of time for
which a network element will repeat a NAK while waiting for a
corresponding NCF. NAK_RPT_IVL is counted down from the transmission
of a NAK. Expiry of NAK_RPT_IVL cancels NAK forwarding (due to
missing NCF).
The NAK RDATA interval NAK_RDATA_IVL, limits the length of time for
which a network element will wait for the corresponding RDATA.
NAK_RDATA_IVL is counted down from the time a matching NCF is
received. Expiry of NAK_RDATA_IVL causes the network element to
discard the corresponding repair state (due to missing RDATA).
During NAK_RPT_IVL, a NAK is said to be pending. During
NAK_RDATA_IVL, a NAK is said to be outstanding.
A Network element MUST forward NAKs only to the upstream PGM network
element for the TSI.
A network element MUST repeat a NAK at a rate of NAK_RPT_RTE for an
interval of NAK_RPT_IVL until it receives a matching NCF. A matching
NCF must match NCF_TSI with NAK_TSI, and NCF_SQN with NAK_SQN.
Upon reception of the corresponding NCF, network elements MUST wait
at least NAK_RDATA_IVL for the corresponding RDATA. Receipt of the
corresponding RDATA at any time during NAK forwarding cancels NAK
forwarding and tears down the corresponding repair state in the
network element.
7.4. NAK elimination
Two NAKs duplicate each other if they bear the same NAK_TSI and
NAK_SQN. Network elements MUST discard all duplicates of a NAK that
is pending.
Once a NAK is outstanding, network elements MUST discard all
duplicates of that NAK for NAK_ELIM_IVL. Upon expiry of
NAK_ELIM_IVL, network elements MUST suspend NAK elimination for that
TSI/SQN until the first duplicate of that NAK is seen after the
expiry of NAK_ELIM_IVL. This duplicate MUST be forwarded in the
usual manner. Once this duplicate NAK is 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 acts to balance implosion prevention against repair
state liveness. That is, it results in the elimination of all but at
most one NAK per NAK_ELIM_IVL thereby allowing repeated NAKs to keep
the repair state alive in the PGM network elements.
7.5. NAK Anticipation
An unsolicited NCF is one that is received by a network element when
the network element has no corresponding pending or outstanding NAK.
Network elements MUST process unsolicited NCFs differently depending
on the interface on which they are received.
If the interface on which an NCF is received is the same interface
the network element would use to reach the upstream PGM network
element, the network element simply establishes repair state for
NCF_TSI and NCF_SQN without adding the interface to the repair
interface list, and discards the NCF. If the repair state already
exists, the network element 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 permit the elimination of any subsequent matching
NAKs from downstream. Upon establishing anticipated repair state,
network elements MUST eliminate subsequent NAKs only for a period of
NAK_ELIM_IVL. Upon expiry of NAK_ELIM_IVL, network elements MUST
suspend NAK elimination for that TSI/SQN until the first duplicate of
that NAK is seen after the expiry of NAK_ELIM_IVL. This duplicate
MUST be forwarded in the usual manner. Once this duplicate NAK is
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 for receivers detected to be reporting excessive loss.
The result of these procedures would ultimately be unrecoverable data
loss in the receiver.
7.7. Addressing NAKs
A PGM network element uses the source and group addresses (NLAs)
contained in the transport header to find the state for the
corresponding TSI, looks up the corresponding upstream PGM network
element's address, uses it to re-address the (unicast) NAK, and
unicasts it on the upstream interface for the distribution tree for
the TSI.
7.8. Constrained RDATA Forwarding
Network elements MUST maintain repair state for each interface on
which a given NAK is received at least once. Network elements MUST
then use this list of interfaces to constrain the forwarding of the
corresponding RDATA packet only to those interfaces in the list. An
RDATA packet corresponds to a NAK if it matches NAK_TSI and NAK_SQN.
Network elements MUST maintain this repair state only until either
the corresponding RDATA is received and forwarded, or NAK_RDATA_IVL
passes after forwarding the most recent instance of a given NAK.
Thereafter, the corresponding repair state MUST be discarded.
Network elements SHOULD discard and not forward RDATA packets for
which they have no repair state. Note that the consequence of this
procedure is that, while it constrains repairs to the interested
subset of the network, loss of repair state precipitates further NAKs
from neglected receivers.
8. Packet Formats
All of the packet formats described in this section are transport-
layer headers that MUST immediately follow the network-layer header
in the packet. Only data packet headers (ODATA and RDATA) may be
followed in the packet by application data. For each packet type,
the network-header source and destination addresses are specified in
addition to the format and contents of the transport layer header.
Recall from General Procedures that, for PGM over IP multicast, SPMs,
NCFs, and RDATA MUST also bear the IP Router Alert Option.
For PGM over IP, the IP protocol number is 113.
In all packets the descriptions of Data-Source Port, Data-Destination
Port, Type, Options, Checksum, Global Source ID (GSI), and Transport
Service Data Unit (TSDU) Length are:
Data-Source Port:
A random port number generated by the source. This port number
MUST be unique within the source. Source Port together with
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 0x0 through 0x3 represent SPM-like
packets (i.e., session-specific, sourced by a source,
periodic),
values in the range 0x4 through 0x7 represent DATA-like
packets (i.e., data and repairs),
values in the range 0x8 through 0xB represent NAK-like
packets (i.e., hop-by-hop reliable NAK forwarding
procedures),
and values in the range 0xC through 0xF represent SPMR-like
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 including header.
The checksum does not include a network-layer pseudo header for
compatibility with network address translation. If the
computed checksum is zero, it is transmitted as all ones. A
value of zero in this field means the transmitter generated no
checksum.
Note that if any entity between a source and a receiver
modifies the PGM header for any reason, it MUST either
recompute the 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
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
SPMs are sent by a source to establish source path state in network
elements and to provide transmit window state to receivers.
The network-header source address of an SPM is the unicast NLA of the
entity that originates the SPM.
The network-header destination address of an SPM is a multicast group
NLA.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Port | Destination Port |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Options | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Global Source ID ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... Global Source ID | TSDU Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SPM's Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Trailing Edge Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Leading Edge Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NLA AFI | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Path NLA ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...-+-+
| Option Extensions when present ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- ... -+-+-+-+-+-+-+-+-+-+-+-+-+-+
Source Port:
SPM_SPORT
Data-Source Port, together with SPM_GSI forms SPM_TSI
Destination Port:
SPM_DPORT
Data-Destination Port
Type:
SPM_TYPE = 0x00
Global Source ID:
SPM_GSI
Together with SPM_SPORT forms SPM_TSI
SPM's Sequence Number
SPM_SQN
The sequence number assigned to the SPM by the source.
Trailing Edge Sequence Number:
SPM_TRAIL
The sequence number defining the current trailing edge of the
source's transmit window (TXW_TRAIL).
Leading Edge Sequence Number:
SPM_LEAD
The sequence number defining the current leading edge of the
source's transmit window (TXW_LEAD).
If SPM_TRAIL == 0 and SPM_LEAD == 0x80000000, this indicates that
no window information is present in the packet.
Path NLA:
SPM_PATH
The NLA of the interface on the network element on which this SPM
was forwarded. Initialized by a source to the source's NLA,
rewritten by each PGM network element upon forwarding.
8.2. Data Packets
Data packets carry application data from a source or a repairer to
receivers.
ODATA:
Original data packets transmitted by a source.
RDATA:
Repairs transmitted by a source or by a designated local
repairer (DLR) in response to a NAK.
The network-header source address of a data packet is the unicast NLA
of the entity that originates the data packet.
The network-header destination address of a data packet is a
multicast group NLA.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Port | Destination Port |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Options | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Global Source ID ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... Global Source ID | TSDU Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Data Packet Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Trailing Edge Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Extensions when present ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- ... -+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Data ...
+-+-+- ...
Source Port:
OD_SPORT, RD_SPORT
Data-Source Port, together with Global Source ID forms:
OD_TSI, RD_TSI
Destination Port:
OD_DPORT, RD_DPORT
Data-Destination Port
Type:
OD_TYPE = 0x04 RD_TYPE = 0x05
Global Source ID:
OD_GSI, RD_GSI
Together with Source Port forms:
OD_TSI, RD_TSI
Data Packet Sequence Number:
OD_SQN, RD_SQN
The sequence number originally assigned to the ODATA packet by the
source.
Trailing Edge Sequence Number:
OD_TRAIL, RD_TRAIL
The sequence number defining the current trailing edge of the
source's transmit window (TXW_TRAIL). In RDATA, this MAY not be
the same as OD_TRAIL of the ODATA packet for which it is a repair.
Data:
Application data.
8.3. Negative Acknowledgments and Confirmations
NAK:
Negative Acknowledgments are sent by receivers to request the
repair of an ODATA packet detected to be missing from the
expected sequence.
N-NAK:
Null Negative Acknowledgments are sent by DLRs to provide flow
control feedback to the source of ODATA for which the DLR has
provided the corresponding RDATA.
The network-header source address of a NAK is the unicast NLA of the
entity that originates the NAK. The network-header source address of
NAK is rewritten by each PGM network element with its own.
The network-header destination address of a NAK is initialized by the
originator of the NAK (a receiver) to the unicast NLA of the upstream
PGM network element known from SPMs. The network-header destination
address of a NAK is rewritten by each PGM network element with the
unicast NLA of the upstream PGM network element to which this NAK is
forwarded. On the final hop, the network-header destination address
of a NAK is rewritten by the PGM network element with the unicast NLA
of the original source or the unicast NLA of a DLR.
NCF:
NAK Confirmations are sent by network elements and sources to
confirm the receipt of a NAK.
The network-header source address of an NCF is the ODATA source's
NLA, not the network element's NLA as might be expected.
The network-header destination address of an NCF is a multicast group
NLA.
Note that in NAKs and N-NAKs, unlike the other packets, the field
SPORT contains the Data-Destination port and the field DPORT contains
the Data-Source port. As a general rule, the content of SPORT/DPORT
is determined by the direction of the flow: in packets which travel
down-stream SPORT is the port number chosen in the data source
(Data-Source Port) and DPORT is the data destination port number
(Data-Destination Port). The opposite holds for packets which travel
upstream. This makes DPORT the protocol endpoint in the recipient
host, regardless of the direction of the packet.
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 for which a
repair is requested.
NNAK_SQN is the sequence number of the RDATA packet for which a
repair has been provided by a DLR.
NCF_SQN
NCF_SQN is NAK_SQN from the NAK being confirmed.
Source NLA:
NAK_SRC, NNAK_SRC, NCF_SRC
The unicast NLA of the original source of the missing ODATA.
Multicast Group NLA:
NAK_GRP, NNAK_GRP, NCF_GRP
The multicast group NLA. NCFs MAY bear OPT_REDIRECT and/or
OPT_NAK_LIST
9. Options
PGM specifies several end-to-end options to address specific
application requirements. PGM specifies options to support
fragmentation, late joining, and redirection.
Options MAY be appended to PGM data packet headers only by their
original transmitters. While they MAY be interpreted by network
elements, options are neither added nor removed by network elements.
Options are all in the TLV style, or Type, Length, Value. The Type
field is contained in the first byte, where bit 0 is the OPT_END bit,
followed by 7 bits of type. The OPT_END bit MUST be set in the last
option in the option list, whichever that might be. The Length field
is the total length of the option in bytes, and directly follows the
Type field. Following the Length field are 5 reserved bits, the
OP_ENCODED flag, the 2 Option Extensibility bits OPX and the
OP_ENCODED_NULL flag. Last are 7 bits designated for option specific
information which may be defined on a per-option basis. If not
defined for a particular option, they MUST be set to 0.
The Option Extensibility bits dictate the desired treatment of an
option if it is unknown to the network element processing it.
Nota Bene: Only network elements pay any attention to these bits.
The OPX bits are defined as follows:
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 use
Some options present in data packet (ODATA and RDATA) are strictly
associated with the packet content (PGM payload), OPT_FRAGMENT being
an example. These options must be preserved even when the data
packet that would normally contain them is not received, but its the
payload is recovered though the use of FEC. PGM specifies a
mechanism to accomplish this that uses the F (OP_ENCODED) and U
(OP_ENCODED_NULL) bits in the option common header. OP_ENCODED and
OP_ENCODED_NULL MUST be normally set to zero except when the option
is used in FEC packets to preserve original options. See Appendix A
for details.
There is a limit of 16 options per packet.
General Option Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|E| Option Type | Option Length |Reserved |F|OPX|U|Opt. Specific|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Value ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...+-+-+
9.1. Option extension length - OPT_LENGTH
When option extensions are appended to the standard PGM header, the
extensions MUST be preceded by an option extension length field
specifying the total length of all option extensions.
In addition, the presence of the options MUST be encoded in the
Options field of the standard PGM header before the Checksum is
computed.
All network-significant options MUST be appended before any
exclusively receiver-significant options.
To provide an indication of the end of option extensions, OPT_END
(0x80) MUST be set in the Option Type field of the trailing option
extension.
9.1.1. OPT_LENGTH - Packet Extension Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Option Length | Total length of all options |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type = 0x00
Option Length = 4 octets
Total length of all options
The total length in octets of all option extensions including
OPT_LENGTH.
OPT_LENGTH is NOT network-significant.
9.2. Fragmentation Option - OPT_FRAGMENT
Fragmentation allows transport-layer entities at a source to break up
application protocol data units (APDUs) into multiple PGM data
packets (TPDUs) to conform with the MTU supported by the network
layer. The fragmentation option MAY be applied to ODATA and RDATA
packets only.
Architecturally, the accumulation of TSDUs into APDUs is applied to
TPDUs that have already been received, duplicate eliminated, and
contiguously sequenced by the receiver. Thus APDUs MAY be
reassembled across increments of the transmit window.
9.2.1. OPT_FRAGMENT - Packet Extension Contents
OPT_FRAG_OFF the offset of the fragment from the beginning of the
APDU
OPT_FRAG_LEN the total length of the original APDU
9.2.2. OPT_FRAGMENT - Procedures - Sources
A source fragments APDUs into a contiguous series of fragments no
larger than the MTU supported by the network layer. A source
sequentially and uniquely assigns OD_SQNs to these fragments in the
order in which they occur in the APDU. A source then sets
OPT_FRAG_OFF to the value of the offset of the fragment in the
original APDU (where the first byte of the APDU is at offset 0, and
OPT_FRAG_OFF numbers the first byte in the fragment), and set
OPT_FRAG_LEN to the value of the total length of the original APDU.
9.2.3. OPT_FRAGMENT - Procedures - Receivers
Receivers detect and accumulate fragmented packets until they have
received an entire contiguous sequence of packets comprising an APDU.
This sequence begins with the fragment bearing OPT_FRAG_OFF of 0, and
terminates with the fragment whose length added to its OPT_FRAG_OFF
is OPT_FRAG_LEN.
9.2.4. OPT_FRAGMENT - 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
Sequence Number of the PGM DATA/RDATA packet containing 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 in conjunction with NAKs to allow
receivers to request transmission for more than one sequence number
with a single NAK packet. The option is limited to 62 listed NAK
entries. The NAK list MUST be unique and duplicate free. It MUST be
ordered, and MUST consist of either a list of selective or a list of
parity NAKs. In general, network elements, sources and receivers
must process a NAK list as if they had received individual NAKs for
each sequence number in the list. The procedures for each are
outlined in detail earlier in this document. Clarifications and
differences are detailed here.
9.3.1. OPT_NAK_LIST - Packet Extensions Contents
A list of sequence numbers for which retransmission is requested.
9.3.2. OPT_NAK_LIST - Procedures - Receivers
Receivers MAY append the NAK List option to a NAK to indicate that
they wish retransmission of a number of RDATA.
Receivers SHOULD proceed to back off NAK transmission in a manner
consistent with the procedures outlined for single sequence number
NAKs. Note that the repair of each separate sequence number will be
completed upon receipt of a separate RDATA packet.
Reception of an NCF or multicast NAK containing the NAK List option
suspends generation of NAKs for all sequence numbers within the NAK
list, as well as the sequence number within the NAK header.
9.3.3. OPT_NAK_LIST - Procedures - Network Elements
Network elements MUST immediately respond to a NAK with an identical
NCF containing the same NAK list as the NAK itself.
Network elements MUST forward a NAK containing a NAK List option if
any one sequence number specified by the NAK (including that in the
main NAK header) is not currently outstanding. That is, it MUST
forward the NAK, if any one sequence number does not have an
elimination timer running for it. The NAK must be forwarded intact.
Network elements MUST eliminate a NAK containing the NAK list option
only if all sequence numbers specified by the NAK (including that in
the main NAK header) are outstanding. That is, they are all running
an elimination timer.
Upon receipt of an unsolicited NCF containing the NAK list option, a
network element MUST anticipate data for every sequence number
specified by the NAK as if it had received an NCF for every sequence
number specified by the NAK.
9.3.4. OPT_NAK_LIST - Procedures - Sources
A source MUST immediately respond to a NAK with an identical NCF
containing 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 to which the NAK
applies.
OPT_NAK_LIST is network-significant.
9.4. Late Joining Option - OPT_JOIN
Late joining allows a source to bound the amount of repair history
receivers may request when they initially join a particular transport
session.
This option indicates that receivers that join a transport session in
progress MAY request repair of all data as far back as the given
minimum sequence number from the time they join the transport
session. The default is for receivers to receive data only from the
first packet they receive and onward.
9.4.1. OPT_JOIN - Packet Extensions Contents
OPT_JOIN_MIN the minimum sequence number for repair
9.4.2. OPT_JOIN - Procedures - Receivers
If a PGM packet (ODATA, RDATA, or SPM) bears OPT_JOIN, a receiver MAY
initialize the trailing edge of the receive window (RXW_TRAIL_INIT)
to the given Minimum Sequence Number and proceeds with normal data
reception.
9.4.3. OPT_JOIN - Packet Extension Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|E| Option Type | Option Length |Reserved |F|OPX|U| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Minimum Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type = 0x03
Option Length = 8 octets
Minimum Sequence Number
The minimum sequence number defining the initial trailing edge of
the receive window for a late joining receiver.
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,
for requesting repairs.
These procedures allow a PGM Network Element to use a DLR that is one
PGM hop from it either upstream or downstream in the multicast
distribution tree. The former are referred to as upstream DLRs. The
latter are referred to as off-tree DLRs. Off-Tree because even
though they are downstream of the point of loss, they might not lie
on the subtree affected by the loss.
A DLR MUST receive any PGM sessions for which it wishes to provide
retransmissions. A DLR SHOULD respond to NCFs or POLLs sourced by
its PGM parent with a redirecting POLR response packet containing an
OPT_REDIRECT which provides its own network layer address.
Recipients of redirecting POLRs MAY then direct NAKs for subsequent
ODATA sequence numbers to the DLR rather than to the original source.
In addition, DLRs that receive redirected NAKs for which they have
RDATA MUST send a NULL NAK to provide flow control to the original
source without also provoking a repair from that source.
9.5.1. OPT_REDIRECT - Packet Extensions Contents
OPT_REDIR_NLA the DLR's own unicast network-layer address to which
recipients of the redirecting POLR MAY direct
subsequent NAKs for the corresponding TSI.
9.5.2. OPT_REDIRECT - Procedures - DLRs
A DLR MUST receive any PGM sessions for which it wishes to provide a
source of repairs. In addition to acting as an ordinary PGM
receiver, a DLR MAY then respond to NCFs or relevant POLLs sourced by
parent network elements (or even by the source itself) by sending a
POLR containing an OPT_REDIRECT providing its own network-layer
address.
If a DLR can provide FEC repairs it MUST denote this by setting
OPT_PARITY in the PGM header of its POLR response.
9.5.2.1. Upstream DLRs
If the NCF completes NAK transmission initiated by the DLR itself,
the DLR MUST NOT send a redirecting POLR.
When a DLR receives an NCF from its upstream PGM parent, it SHOULD
send a redirecting POLR, multicast to the group. The DLR SHOULD
record that it is acting as an upstream DLR for the said session.
Note that this POLR MUST have both the data source's source address
and the router alert option in its network header.
An upstream DLR MUST act as an ordinary PGM source in responding to
any NAK it receives (i.e., directed to it). That is, it SHOULD
respond first with a normal NCF and then RDATA as usual. In
addition, an upstream DLR that receives redirected NAKs for which it
has RDATA MUST send a NULL NAK to provide flow control to the
original source. If it cannot provide the RDATA it forwards the NAK
to the upstream PGM 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 receives a POLL with sub-type PGM_POLL_DLR MUST respond
with a unicast redirecting POLR if it provides the appropriate
service. The DLR SHOULD respond using the rules outlined for polling
in Appendix D of this text. If the DLR responds, it SHOULD record
that it is acting as an off-tree DLR for the said session.
An off-tree DLR acts in a special way in responding to any NAK it
receives (i.e., directed to it). It MUST respond to a NAK directed
to it from its parent by unicasting an NCF and RDATA to its parent.
The parent will then forward the RDATA down the distribution tree.
The DLR uses its own and the parent's NLA addresses in the network
header for the source and destination respectively. The unicast NCF
and RDATA packets SHOULD not have the router alert option. In all
other ways the RDATA header should be "as if" the packet had come
from the source.
Again, an off-tree DLR that receives redirected NAKs for which it has
RDATA MUST originate a NULL NAK to provide flow control to the
original source. It MUST originate the NULL NAK before originating
the RDATA. This must be done to reduce the state held in the network
element.
If it cannot provide the RDATA for a given NAK, an off-tree DLR
SHOULD confirm the NAK with a unicast NCF as normal, then immediately
send a NAK for the said data packet back to its parent.
9.5.2.3. Simultaneous Upstream and Off-Tree DLR operation
Note that it is possible for a DLR to provide service to its parent
and to downstream network elements simultaneously. A downstream loss
coupled with a loss for the same data on some other part of the
distribution tree served by its parent could cause this. In this
case it may provide both upstream and off-tree functionality
simultaneously.
Note that a DLR differentiates between NAKs from an NE downstream or
from its parent by comparing the network-header source address of the
NAK with it's upstream PGM parent's NLA. The DLR knows the parent's
NLA from the session's SPM messages.
9.5.3. OPT_REDIRECT - Procedures - Network Elements
9.5.3.1. Discovering DLRs
When a PGM router receives notification of a loss via a NAK, it
SHOULD first try to use a known DLR to recover the loss. If such a
DLR is not known it SHOULD initiate DLR discovery. DLR discovery may
occur in two ways. If there are upstream DLRs, the NAK transmitted
by this router to its PGM parent will trigger their discovery, via a
redirecting POLR. Also, a network element SHOULD initiate a search
for off-tree DLRs using the PGM polling mechanism, and the sub-type
PGM_POLL_DLR.
If a DLR can provide FEC repairs it will denote this by setting
OPT_PARITY in the PGM header of its POLR response. A network element
SHOULD only direct parity NAKs to a DLR that can provide FEC repairs.
9.5.3.2. Redirected Repair
When it can, a network element SHOULD use upstream DLRs.
Upon receiving a redirecting POLR, network elements SHOULD record the
redirecting information for the TSI, and SHOULD redirect subsequent
NAKs for the same TSI to the network address provided in the
redirecting POLR rather than to the PGM neighbor known via the SPMs.
Note, however, that a redirecting POLR is NOT regarded as matching
the NAK that provoked it, so it does not complete the transmission of
that NAK. Only a normal matching NCF can complete the transmission
of a NAK.
For subsequent NAKs, if the network element has recorded redirection
information for the corresponding TSI, it MAY change the destination
network address of those NAKs and attempt to transmit them to the
DLR. No NAK for a specific SQN SHOULD be sent to an off-tree DLR if
a NAK for the SQN has been seen on the interface associated with the
DLR. Instead the NAK SHOULD be forwarded upstream. Subsequent NAKs
for different SQNs MAY be forwarded to the said DLR (again assuming
no NAK for them has been seen on the interface to the DLR).
If a corresponding NCF is not received from the DLR within
NAK_RPT_IVL, the network element MUST discard the redirecting
information for the TSI and re-attempt to forward the NAK towards the
PGM upstream neighbor.
If a NAK is received from the DLR for a requested SQN, the network
element MUST discard the redirecting information for the 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 will flow down the distribution
tree. However, RDATA and NCFs from off-tree DLRs will be unicast to
the network element. The network element will terminate the NCF, but
MUST put the source's NLA and the group address into the network
header and MUST add router alert before forwarding the RDATA packet
to the distribution subtree.
NULL NAKs from an off-tree DLR for an RDATA packet requested from
that off-tree DLR MUST always be forwarded upstream. The network
element can assume that these will arrive before the matching RDATA.
Other NULL NAKs are forwarded only if matching repair state has not
already been created. Network elements MUST NOT confirm or retry
NULL NAKs and they MUST NOT add the receiving interface to the repair
state. If a NULL NAK is used to initially create repair state, this
fact must be recorded so that any subsequent non-NULL NAK will not be
eliminated, but rather will be forwarded to provoke an actual repair.
State created by a NULL NAK exists only for NAK_ELIM_IVL.
9.5.4. OPT_REDIRECT - Procedures - Receivers
These procedures are intended to be applied in instances where a
receiver's first hop router on the reverse path to the source is not
a PGM Network Element. So, receivers MUST ignore a redirecting POLR
from a DLR on the same IP subnet that the receiver resides on, since
this is likely to suffer identical loss to the receiver and so be
useless. Therefore, these procedures are entirely OPTIONAL. A
receiver MAY choose to ignore all redirecting POLRs since in cases
where its first hop router on the reverse path is PGM capable, it
would ignore them 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 provided in the redirecting
POLR rather than to the PGM neighbor for the corresponding ODATA for
which the receiver is requesting repair. Note, however, that a
redirecting POLR is NOT regarded as matching the NAK that provoked
it, so it does not complete the transmission of that NAK. Only a
normal matching NCF can complete the transmission of a NAK.
For subsequent NAKs, if the receiver has recorded redirection
information for the corresponding TSI, it MAY change the destination
network address of those NAKs and attempt to transmit them to the
DLR. If a corresponding NCF is not received within NAK_RPT_IVL, the
receiver MUST discard the redirecting information for the TSI and
re-attempt to forward the NAK to the PGM neighbor for the original
source of the missing ODATA.
9.5.5. OPT_REDIRECT - 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| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NLA AFI | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| DLR's NLA ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...-+-+
Option Type = 0x07
Option Length = 4 + NLA length
DLR's NLA
The DLR's own unicast network address to which recipients of the
redirecting POLR may direct subsequent NAKs.
OPT_REDIRECT is network-significant.
9.6. OPT_SYN - Synchronization Option
The SYN option indicates the starting data packet for a session. It
must only appear in ODATA or RDATA packets.
The SYN option MAY be used to provide a useful abstraction to
applications that can simplify application design by providing stream
start notification. It MAY also be used to let a late joiner to a
session know that it is indeed late (i.e. it would not see the SYN
option).
9.6.1. OPT_SYN - Procedures - Receivers
Procedures for receivers are implementation dependent. A receiver
MAY use the SYN to provide its applications with abstractions of the
data stream.
9.6.2. OPT_SYN - Procedures - Sources
Sources MAY include OPT_SYN in the first data for a session. That
is, they MAY include the option in:
the first ODATA sent on a session by a PGM source
any RDATA sent as a result of loss of this ODATA packet
all FEC packets for the first transmission group; in this case it
is interpreted as the first packet having the SYN
9.6.3. OPT_SYN - Procedures - DLRs
In an identical manner to sources, DLRs MUST provide OPT_SYN in
any retransmitted data that is at the start of a session.
9.6.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| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type = 0x0D
Option Length = 4
OPT_SYN is NOT network-significant.
9.7. OPT_FIN - Session Finish Option
This FIN option indicates the last data packet for a session and
an orderly close down.
The FIN option MAY be used to provide an abstraction to
applications that can simplify application design by providing
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 indicates 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 let it know that it can
tear down its data structures for the said session once a suitable
time period has expired (TXW_SECS). It MAY still try to solicit
retransmissions within the existing transmit window.
Other than this, procedures for receivers are implementation
dependent. A receiver MAY use the FIN to provide its applications
with abstractions of the data stream and to inform its
applications that the session is ending.
9.7.2. OPT_FIN - Procedures - Sources
Sources MUST include OPT_FIN in every SPM sent after it has been
determined that the application has closed gracefully. If a
source is aware at the time of transmission that it is ending a
session the source MAY include OPT_FIN in,
the last ODATA
any associated RDATAs for the last data
FEC packets for the last transmission group; in this case it is
interpreted as the last packet having the FIN
When a source detects that it needs to send an OPT_FIN it SHOULD
immediately send it. This is done either by appending it to the last
data packet or transmission group or by immediately sending an SPM
and resetting the SPM heartbeat timer (i.e. it does not wait for a
timer to expire before sending the SPM). After sending an OPT_FIN,
the session SHOULD not close and stop sending SPMs until after a time
period equal to TXW_SECS.
9.7.3. OPT_FIN - Procedures - DLRs
In an identical manner to sources, DLRs MUST provide OPT_FIN in any
retransmitted data that is at the end of a session.
9.7.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| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type = 0x0E
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 an unrecoverable
error is identified by the source. This acts to notify the receivers
that the session is being aborted. This option MAY appear only in
SPMs. The SPM_LEAD sequence number in an SPM with the RST option
indicates the last known data successfully transmitted for the
session.
9.8.1. OPT_RST - Procedures - Receivers
Receivers SHOULD treat the reception of OPT_RST in an SPM as an abort
of the session.
A receiver that receives an SPM with an OPT_RST with the N bit set
SHOULD not send any more NAKs for the said session towards the
source. If the N bit (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 it has been
determined that an unrecoverable error condition has occurred. The N
bit of the OPT_RST SHOULD only be sent if the source has determined
that it cannot process NAKs for the session. The cause of the
OPT_RST is set to an implementation specific value. If the error
code is unknown, then the value of 0x00 is used. When a source
detects that it needs to send an OPT_RST it SHOULD immediately send
it. This is done by immediately sending an SPM and resetting the SPM
heartbeat timer (i.e. it does not wait for a timer to expire before
sending the SPM). After sending an OPT_RST, the session SHOULD not
close and stop sending SPMs until after a time period equal to
TXW_SECS.
9.8.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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type = 0x0F
Option Length = 4
N bit
The N bit is set to 1 to indicate that NAKs for previous ODATA
will go unanswered from the source. The application will tell the
source to turn this bit on or off.
Error Code
The 6 bit error code field is used to forward an error code down
to the receivers from the source.
The value of 0x00 indicates an unknown reset reason. Any other
value indicates the application purposely aborted and gave a
reason (the error code value) that may have meaning to the end
receiver application. These values are entirely application
dependent.
OPT_RST is NOT network-significant.
10. Security Considerations
In addition to the usual problems of end-to-end authentication, PGM
is vulnerable to a number of security risks that are specific to the
mechanisms it uses to establish source path state, to establish
repair state, to forward NAKs, to identify DLRs, and to distribute
repairs. These mechanisms expose PGM network elements themselves to
security risks since network elements not only switch but also
interpret SPMs, NAKs, NCFs, and RDATA, all of which may legitimately
be transmitted by PGM sources, receivers, and DLRs. Short of full
authentication of all neighboring sources, receivers, DLRs, and
network elements, the protocol is not impervious to abuse.
So putting aside the problems of rogue PGM network elements for the
moment, there are enough potential security risks to network elements
associated with sources, receivers, and DLRs alone. These risks
include denial of service through the exhausting of both CPU
bandwidth and memory, as well as loss of (repair) data connectivity
through the muddling of repair state.
False SPMs may cause PGM network elements to mis-direct NAKs intended
for the legitimate source with the result that the requested RDATA
would not be forthcoming.
False NAKs may cause PGM network elements to establish spurious
repair state that will expire only upon time-out and could lead to
memory exhaustion in the meantime.
False NCFs may cause PGM network elements to suspend NAK forwarding
prematurely (or to mis-direct NAKs in the case of redirecting POLRs)
resulting eventually in loss of RDATA.
False RDATA may cause PGM network elements to tear down legitimate
repair state resulting eventually in loss of legitimate RDATA.
The development of precautions for network elements to protect
themselves against incidental or unsophisticated versions of these
attacks is work outside of this spec and includes:
Damping of jitter in the value of either the network-header source
address of SPMs or the path NLA in SPMs. While the network-header
source address is expected to change seldom, the path NLA is
expected to change occasionally as a consequence of changes in
underlying multicast routing information.
The extension of NAK shedding procedures to control the volume, not
just the rate, of confirmed NAKs. In either case, these procedures
assist network elements in surviving NAK attacks at the expense of
maintaining service. More efficiently, network elements may use the
knowledge of TSIs and their associated transmit windows gleaned from
SPMs to control the proliferation of repair state.
A three-way handshake between network elements and DLRs that would
permit a network element to ascertain with greater confidence that an
alleged DLR is identified by the alleged network-header source
address, and is PGM conversant.
11. Appendix A - Forward Error Correction
11.1. Introduction
The following procedures incorporate packet-level Reed Solomon
Erasure correcting techniques as described in [11] and [12] into PGM.
This approach to Forward Error Correction (FEC) is based upon the
computation of h parity packets from k data packets for a total of n
packets such that a receiver can reconstruct the k data packets out
of any k of the n packets. The original k data packets are referred
to as the Transmission Group, and the total n packets as the FEC
Block.
These procedures permit any combination of pro-active FEC or on-
demand FEC with conventional ARQ (selective retransmission) within a
given TSI to provide any flavor of layered or integrated FEC. The
two approaches can be used by the same or different receivers in a
single transport session without conflict. Once provided by a
source, the actual use of FEC or selective retransmission for loss
recovery in the session is entirely at the discretion of the
receivers. Note however that receivers SHOULD NOT ask for selective
retransmissions when FEC is available, nevertheless sources MUST
provide selective retransmissions in response to selective NAKs from
the leading partial transmission group (i.e. the most recent
transmission group, which is not yet full). For any group that is
full, the source SHOULD provide FEC on demand in response to a
selective NAK.
Pro-active FEC refers to the technique of computing parity packets at
transmission time and transmitting them as a matter of course
following the data packets. Pro-active FEC is RECOMMENDED for
providing loss recovery over simplex or asymmetric multicast channels
over which returning repair requests is either impossible or costly.
It provides increased reliability at the expense of bandwidth.
On-demand FEC refers to the technique of computing parity packets at
repair time and transmitting them only upon demand (i.e., receiver-
based loss detection and repair request). On-demand FEC is
RECOMMENDED for providing loss recovery of uncorrelated loss in very
large receiver populations in which the probability of any single
packet being lost is substantial. It provides equivalent reliability
to selective NAKs (ARQ) at no more and typically less expense of
bandwidth.
Selective NAKs are NAKs that request the retransmission of specific
packets by sequence number corresponding to the sequence number of
any data packets detected to be missing from the expected sequence
(conventional ARQ). Selective NAKs can be used for recovering losses
occurring in leading partial transmission groups, i.e. in the most
recent transmission group, which is not yet full. The RECOMMENDED
way of handling partial transmission groups, however, is for the data
source to use variable-size transmission groups (see below).
Parity NAKs are NAKs that request the transmission of a specific
number of parity packets by count corresponding to the count of the
number of data packets detected to be missing from a group of k data
packets (on-demand FEC).
The objective of these procedures is to incorporate these FEC
techniques into PGM so that:
sources MAY provide parity packets either pro-actively or on-
demand, interchangeably within the same TSI,
receivers MAY use either selective or parity NAKs interchangeably
within the same TSI (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,
RDATA constraint, and deletion algorithms in either case,
and only OPTION additions to the basic packet formats are
REQUIRED.
11.2. Overview
Advertising FEC parameters in the transport session
Sources add OPT_PARITY_PRM to SPMs to provide session-specific
parameters such as the number of packets (TGSIZE == k) in a
transmission group. This option lets receivers know how many packets
there are in a transmission group, and it lets network elements sort
repair state by transmission group number. This option includes an
indication of whether pro-active and/or on-demand parity is available
from the source.
Distinguishing parity packets from data packets
Sources send pro-active parity packets as ODATA (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 to permit network elements and receivers to
distinguish them from data packets.
Data and parity packet numbering
Parity packets MUST be calculated over a fixed number k of data
packets known as the Transmission Group. Grouping of packets into
transmission groups effectively partitions a packet sequence number
into a high-order portion (TG_SQN) specifying the transmission group
(TG), and a low-order portion (PKT_SQN) specifying the packet number
(PKT-NUM in the range 0 through k-1) within that group. From an
implementation point of view, it's handy if k, the TG size, is a
power of 2. If so, then TG_SQN and PKT_SQN can be mapped side-by-
side into the 32 bit SQN. log2(TGSIZE) is then the size in bits of
PKT_SQN.
This mapping does not reduce the effective sequence number space
since parity packets marked with OPT_PARITY allow the sequence space
(PKT_SQN) to be completely reused in order to number the h parity
packets, as long as h is not greater than k.
In the case where h is greater than k, a source MUST add
OPT_PARITY_GRP to any parity packet numbered j greater than k-1,
specifying the number m of the group of k parity packets to which the
packet belongs, where m is just the quotient from the integer
division of j by k. Correspondingly, PKT-NUM for such parity packets
is just j modulo k. In other words, when a source needs to generate
more parity packets than there were original data packets (perhaps
because of a particularly lossy line such that a receiver lost not
only the original data but some of the parity RDATA as well), use the
OPT_PARITY_GRP option in order to number and identify the
transmission group of the extra packets that would exceed the normal
sequential number space.
Note that parity NAKs (and consequently their corresponding parity
NCFs) MUST also contain the OPT_PARITY flag in the options field of
the fixed header, and that in these packets, PKT_SQN MUST contain
PKT_CNT, the number of missing packets, rather than PKT_NUM, the SQN
of a 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 duration of the
session. However, the actual transmission group size used MAY not be
constant for the duration of 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, there will be sparse utilization of the sequence number
space since some of the sequence numbers that would have been
consumed in numbering a maximum sized TG will not 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 the sequence numbers had been utilized.
When the source decides to use a smaller group size than that
advertised in OPT_PARITY_PRM, it appends OPT_CURR_TGSIZE to the last
data packet (ODATA) in the truncated transmission group. This lets
the receiver know that it should not 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 receives 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. In addition, any parity packet from this TG will also
carry the OPT_CURR_TGSIZE option as 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. Note
that original data packets are transmitted without padding.
Receivers using a combination of original packets and FEC packets to
rebuild missing packets MUST pad the original packets in the same way
as 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. In order for the receiver to
eliminate the padding on the reconstructed data packets, the original
size of the packet MUST be known, and this is accomplished as
follows:
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
allows receivers to distinguish between transmission groups with
variable sized packets and fixed-size ones, and behave accordingly.
Payload-specific options
Some options present in data packet (ODATA and RDATA) are strictly
associated with the packet content (PGM payload), OPT_FRAGMENT being
an example. These options must be preserved even when the data
packet that would normally contain them is not received, but its the
payload is recovered though the use of FEC.
To achieve this, PGM encodes the content of these options in special
options that are inserted in parity packets. Two flags present in
the the option common-header ar