| 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 are used for this process: bit F
(OP_ENCODED) and bit U (OP_ENCODED_NULL).
Whenever at least one of the original packets of a TG contains a
payload-specific option of a given type, the source MUST include an
encoded version of that option type in all the parity packets it
transmits. The encoded option is computed by applying FEC encoding
to the whole option with the exception of the first three bytes of
the option common-header (E, Option Type, Option Length, OP_ENCODED
and OPX fields). The type, length and OPX of the encoded option are
the same as the type, length and OPX in the original options.
OP_ENCODED is set to 1 (all original option have OP_ENCODED = 0).
The encoding is performed using the same process that is used to
compute the payload of the parity packet. i.e. the FEC encoder is fed
with one copy of that option type for each original packet in the TG.
If one (or more) original packet of the TG does not contain that
option type, an all zeroes option is used for the encoding process.
To be able to distinguish this "dummy" option from valid options with
all-zeroes payload, OP_ENCODED_NULL is used. OP_ENCODED_NULL is set
to 0 in all the original options, but the value of 1 is used in the
encoding process if the option did not exist in the original packet.
On the receiver side, all option with OP_ENCODED_NULL equal to 1 are
discarded after decoding.
When a receiver recovers a missing packet using FEC repair packets,
it MUST also recover payload-specific options, if any. The presence
of these can be unequivocally detected through the presence of
encoded options in parity packets (encoded options have OP_ENCODED
set to 1). Receivers apply FEC-recovery to encoded options and
possibly original options, as they do to recover packet payloads.
The FEC decoding is applied to the whole option with the exception of
the first three bytes of the option common-header (E, Option Type,
Option Length, OP_ENCODED and OPX fields). Each decoded option is
associated with the relative payload, unless OP_ENCODED_NULL turns
out to be 1, in which case the decoded option is discarded.
The decoding MUST be performed using the 1st occurrence of a given
option type in original/parity packets. If one or more original
packets do not contain that option type, an option of the same type
with zero value must be used. This option MUST have OP_ENCODED_NULL
equal to 1.
11.3. Packet Contents
This section just provides enough short-hand to make the Procedures
intelligible. For the full details of packet contents, please refer
to Packet Formats below.
OPT_PARITY indicated in pro-active (ODATA) and on-demand
(RDATA) parity packets to distinguish them from
data packets. This option is directly encoded in
the "Option" field of the fixed PGM header
OPT_VAR_PKTLEN MAY be present in pro-active (ODATA) and on-demand
(RDATA) parity packets to indicate that the
corresponding transmission group is composed of
variable size data packets. This option is
directly encoded in the "Option" field of the fixed
PGM header
OPT_PARITY_PRM appended by sources to SPMs to specify session-
specific parameters such as the transmission group
size and the availability of pro-active and/or on-
demand parity from the source
OPT_PARITY_GRP the number of the group (greater than 0) of h
parity packets to which the parity packet belongs
when more than k parity packets are provided by the
source
OPT_CURR_TGSIZE appended by sources to the last data packet and any
parity packets in a variable sized transmission
group to indicate to the receiver the actual size
of a transmission group. May also be appended to
certain SPMs
11.3.1. Parity NAKs
NAK_TG_SQN the high-order portion of NAK_SQN specifying the
transmission group for which parity packets are
requested
NAK_PKT_CNT the low-order portion of NAK_SQN specifying the
number of missing data packets for which parity
packets are requested
Nota Bene: NAK_PKT_CNT (and NCF_PKT_CNT) are 0-based counters,
meaning that NAK_PKT_CNT = 0 means that 1 FEC RDATA is being
requested, and in general NAK_PKT_CNT = k - 1 means that k FEC
RDATA are being requested.
11.3.2. Parity NCFs
NCF_TG_SQN the high-order portion of NCF_SQN specifying the
transmission group for which parity packets were
requested
NCF_PKT_CNT the low-order portion of NCF_SQN specifying the
number of missing data packets for which parity
packets were requested
Nota Bene: NCF_PKT_CNT (and NAK_PKT_CNT) are 0-based counters,
meaning that NAK_PKT_CNT = 0 means that 1 FEC RDATA is being
requested, and in general NAK_PKT_CNT = k - 1 means that k FEC
RDATA are being requested.
11.3.3. On-demand Parity
RDATA_TG_SQN the high-order portion of RDATA_SQN specifying the
transmission group to which the parity packet
belongs
RDATA_PKT_SQN the low-order portion of RDATA_SQN specifying the
parity packet sequence number within the
transmission group
11.3.4. Pro-active Parity
ODATA_TG_SQN the high-order portion of ODATA_SQN specifying the
transmission group to which the parity packet
belongs
ODATA_PKT_SQN the low-order portion of ODATA_SQN specifying the
parity packet sequence number within the
transmission group
11.4. Procedures - Sources
If a source elects to provide parity for a given transport session,
it MUST first provide the transmission group size PARITY_PRM_TGS in
the OPT_PARITY_PRM option of its SPMs. This becomes the maximum
effective transmission group size in the event that the source elects
to send smaller size transmission groups. If a source elects to
provide proactive parity for a given transport session, it MUST set
PARITY_PRM_PRO in the OPT_PARITY_PRM option of its SPMs. If a source
elects to provide on-demand parity for a given transport session, it
MUST set PARITY_PRM_OND in the OPT_PARITY_PRM option of its SPMs.
A source MUST send any pro-active parity packets for a given
transmission group only after it has first sent all of the
corresponding k data packets in that group. Pro-active parity
packets MUST be sent as ODATA with OPT_PARITY in the fixed header.
If a source elects to provide on-demand parity, it MUST respond to a
parity NAK for a transmission group with a parity NCF. The source
MUST complete the transmission of the k original data packets and the
proactive parity packets, possibly scheduled, before starting the
transmission of on-demand parity packets. Subsequently, the source
MUST send the number of parity packets requested by that parity NAK.
On-demand parity packets MUST be sent as RDATA with OPT_PARITY in the
fixed header. Previously transmitted pro-active parity packets
cannot be reused as on-demand parity packets, these MUST be computed
with new, previously unused, indexes.
In either case, the source MUST provide selective retransmissions
only in response to selective NAKs from the leading partial
transmission group. For any group that is full, the source SHOULD
provide FEC on demand in response to a selective retransmission
request.
In the absence of data to transmit, a source SHOULD prematurely
terminate the current transmission group by including OPT_CURR_TGSIZE
to the last data packet or to any proactive parity packets provided.
If the last data packet has already been transmitted and there is no
provision for sending proactive parity packets, an SPM with
OPT_CURR_TGSIZE SHOULD be sent.
A source consolidates requests for on-demand parity in the same
transmission group according to the following procedures. If the
number of pending (i.e., unsent) parity packets from a previous
request for on-demand parity packets is equal to or greater than
NAK_PKT_CNT in a subsequent NAK, that subsequent NAK MUST be
confirmed but MAY otherwise be ignored. If the number of pending
(i.e., unsent) parity packets from a previous request for on-demand
parity packets is less than NAK_PKT_CNT in a subsequent NAK, that
subsequent NAK MUST be confirmed but the source need only increase
the number of pending parity packets to NAK_PKT_CNT.
When a source provides parity packets relative to a transmission
group with variable sized packets, it MUST compute parity packets by
padding the smaller original packets with zeroes out to the size of
the largest of the original packets. The source MUST also append the
encoded TSDU lengths at the end of any padding or directly to the end
of the largest packet, and add the OPT_VAR_PKTLEN option as specified
in the overview description.
When a source provides variable sized transmission groups, it SHOULD
append the OPT_CURR_TGSIZE option to the last data packet in the
shortened group, and it MUST append the OPT_CURR_TGSIZE option to any
parity packets it sends within that group. In case the the last data
packet is sent before a determination has been made to shorten the
group and there is no provision for sending proactive parity packets,
an SPM with OPT_CURR_TGSIZE SHOULD be sent. The source MUST also add
OPT_CURR_TGSIZE to any SPM that it sends with SPM_LEAD equal to
OD_SQN of the last data packet.
A receiver MUST NAK for the entire number of packets missing based on
the maximum TG size, even if it already knows that the actual TG size
is smaller. The source MUST take this into account and compute the
number of packets effectively needed as the difference between
NAK_PKT_CNT and an offset computed as the difference between the max
TG size and the effective TG size.
11.5. Procedures - Receivers
If a receiver elects to make use of parity packets for loss recovery,
it MUST first learn the transmission group size PARITY_PRM_TGS from
OPT_PARITY_PRM in the SPMs for the TSI. The transmission group size
is used by a receiver to determine the sequence number boundaries
between transmission groups.
Thereafter, if PARITY_PRM_PRO is also set in the SPMs for the TSI, a
receiver SHOULD use any pro-active parity packets it receives for
loss recovery, and if PARITY_PRM_OND is also set in the SPMs for the
TSI, it MAY solicit on-demand parity packets upon loss detection. If
PARITY_PRM_OND is set, a receiver MUST NOT send selective NAKs,
except in partial transmission groups if the source does not use the
variable transmission-group size option. Parity packets are ODATA
(pro-active) or RDATA (on-demand) packets distinguished by OPT_PARITY
which lets receivers know that ODATA/RDATA_TG_SQN identifies the
group of PARITY_PRM_TGS packets to which the parity may be applied
for loss recovery in the corresponding transmission group, and that
ODATA/RDATA_PKT_SQN is being reused to number the parity packets
within that group. Receivers order parity packets and eliminate
duplicates within a transmission group based on ODATA/RDATA_PKT_SQN
and on OPT_PARITY_GRP if present.
To solicit on-demand parity packets, a receiver MUST send parity NAKs
upon loss detection. For the purposes of soliciting on-demand
parity, loss detection occurs at transmission group boundaries, i.e.
upon receipt of the last data packet in a transmission group, upon
receipt of any data packet in any subsequent transmission group, or
upon receipt of any parity packet in the current or a subsequent
transmission group.
A parity NAK is simply a NAK with OPT_PARITY and NAK_PKT_CNT set to
the count of the number of packets detected to be missing from the
transmission group specified by NAK_TG_SQN. Note that this
constrains the receiver to request no more parity packets than there
are data packets in the transmission group.
A receiver SHOULD bias the value of NAK_BO_IVL for parity NAKs
inversely proportional to NAK_PKT_CNT so that NAKs for larger losses
are likely to be scheduled ahead of NAKs for smaller losses in the
same receiver population.
A confirming NCF for a parity NAK is a parity NCF with NCF_PKT_CNT
equal to or greater than that specified by the parity NAK.
A receiver's NAK_RDATA_IVL timer is not cancelled until all requested
parity packets have been received.
In the absence of data (detected from SPMs bearing SPM_LEAD equal to
RXW_LEAD) on non-transmission-group boundaries, receivers MAY resort
to selective NAKs for any missing packets in that partial
transmission group.
When a receiver handles parity packets belonging to a transmission
group with variable sized packets, (detected from the presence of the
OPT_VAR_PKTLEN option in the parity packets), it MUST decode them as
specified in the overview description and use the decoded TSDU length
to get rid of the padding in the decoded packet.
If the source was using a variable sized transmission group via the
OPT_CURR_TGSIZE, the receiver might learn this before having
requested (and received) any retransmission. The above happens if it
sees OPT_CURR_TGSIZE in the last data packet of the TG, in any
proactive parity packet or in a SPM. If the receivers learns this
and determines that it has missed one or more packets in the
shortened transmission group, it MAY then NAK for them without
waiting for the start of the next transmission group. Otherwise it
will start NAKing at the start of the next transmission group.
In both cases, the receiver MUST NAK for the number of packets
missing assuming that the size of the transmission group is the
maximum effective transmission group. In other words, the receivers
cannot exploit the fact that it might already know that the
transmission group was smaller but MUST always NAK for the number of
packets it believes are missing, plus the number of packets required
to bring the total packets up to the maximum effective transmission
group size.
After the first parity packet has been delivered to the receiver, the
actual TG size is known to him, either because already known or
because discovered via OPT_CURR_TGSIZE contained in the parity
packet. Hence the receiver can decode the whole group as soon as the
minimum number of parity packets needed is received.
11.6. Procedures - Network Elements
Pro-active parity packets (ODATA with OPT_PARITY) are switched by
network elements without transport-layer intervention.
On-demand parity packets (RDATA with OPT_PARITY) necessitate modified
request, confirmation and repair constraint procedures for network
elements. In the context of these procedures, repair state is
maintained per NAK_TSI and NAK_TG_SQN, and in addition to recording
the interfaces on which corresponding NAKs have been received,
records the largest value of NAK_PKT_CNT seen in corresponding NAKs
on each interface. This value is referred to as the known packet
count. The largest of the known packet counts recorded for any
interface in the repair state for the transmit group or carried by an
NCF is referred to as the largest known packet count.
Upon receipt of a parity NAK, a network element responds with the
corresponding parity NCF. The corresponding parity NCF is just an
NCF formed in the usual way (i.e., a multicast copy of the NAK with
the packet type changed), but with the addition of OPT_PARITY and
with NCF_PKT_CNT set to the larger of NAK_PKT_CNT and the known
packet count for the receiving interface. The network element then
creates repair state in the usual way with the following
modifications.
If repair state for the receiving interface does not exist, the
network element MUST create it and additionally record NAK_PKT_CNT
from the parity NAK as the known packet count for the receiving
interface.
If repair state for the receiving interface already exists, the
network element MUST eliminate the NAK only if NAK_ELIM_IVL has not
expired and NAK_PKT_CNT is equal to or less than the largest known
packet count. If NAK_PKT_CNT is greater than the known packet count
for the receiving interface, the network element MUST update the
latter with the larger NAK_PKT_CNT.
Upon either adding a new interface or updating the known packet count
for an existing interface, the network element MUST determine if
NAK_PKT_CNT is greater than the largest known packet count. If so or
if NAK_ELIM_IVL has expired, the network element MUST forward the
parity NAK in the usual way with a value of NAK_PKT_CNT equal to the
largest known packet count.
Upon receipt of an on-demand parity packet, a network element MUST
locate existing repair state for the corresponding RDATA_TSI and
RDATA_TG_SQN. If no such repair state exists, the network element
MUST discard the RDATA as usual.
If corresponding repair state exists, the largest known packet count
MUST be decremented by one, then the network element MUST forward the
RDATA on all interfaces in the existing repair state, and decrement
the known packet count by one for each. Any interfaces whose known
packet count is thereby reduced to zero MUST be deleted from the
repair state. If the number of interfaces is thereby reduced to
zero, the repair state itself MUST be deleted.
Upon reception of a parity NCF, network elements MUST cancel pending
NAK retransmission only if NCF_PKT_CNT is greater or equal to the
largest known packet count. Network elements MUST use parity NCFs to
anticipate NAKs in the usual way with the addition of recording
NCF_PKT_CNT from the parity NCF as the largest known packet count
with the anticipated state so that any subsequent NAKs received with
NAK_PKT_CNT equal to or less than NCF_PKT_CNT will be eliminated, and
any with NAK_PKT_CNT greater than NCF_PKT_CNT will be forwarded.
Network elements which receive a parity NCF with NCF_PKT_CNT larger
than the largest known packet count MUST also use it to anticipate
NAKs, increasing the largest known packet count to reflect
NCF_PKT_CNT (partial anticipation).
Parity NNAKs follow the usual elimination procedures with the
exception that NNAKs are eliminated only if existing NAK state has a
NAK_PKT_CNT greater than NNAK_PKT_CNT.
Network elements must take extra precaution when the source is using
a variable sized transmission group. Network elements learn that the
source is using a TG size smaller than the maximum from
OPT_CURR_TGSIZE in parity RDATAs or in SPMs. When this happens, they
compute a TG size offset as the difference between the maximum TG
size and the actual TG size advertised by OPT_CURR_TGSIZE. Upon
reception of parity RDATA, the TG size offset is used to update the
repair state as follows:
Any interface whose known packet count is reduced to the TG size
offset is deleted from the repair state.
This replaces the normal rule for deleting interfaces that applies
when the TG size is equal to the maximum TG size.
11.7. Procedures - DLRs
A DLR with the ability to provide FEC repairs MUST indicate this by
setting the OPT_PARITY bit in the redirecting POLR. It MUST then
process any redirected FEC NAKs in the usual way.
11.8. Packet Formats
11.8.1. OPT_PARITY_PRM - Packet Extension Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|E| Option Type | Option Length |Reserved |F|OPX|U| |P O|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Transmission Group Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type = 0x08
Option Length = 8 octets
P-bit (PARITY_PRM_PRO)
Indicates when set that the source is providing pro-active parity
packets.
O-bit (PARITY_PRM_OND)
Indicates when set that the source is providing on-demand parity
packets.
At least one of PARITY_PRM_PRO and PARITY_PRM_OND MUST be set.
Transmission Group Size (PARITY_PRM_TGS)
The number of data packets in the transmission group over which
the parity packets are calculated. If a variable transmission
group size is being used, then this becomes the maximum effective
transmission group size across the session.
OPT_PARITY_PRM MAY be appended only to SPMs.
OPT_PARITY_PRM is network-significant.
11.8.2. OPT_PARITY_GRP - Packet Extension Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|E| Option Type | Option Length |Reserved |F|OPX|U| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Parity Group Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type = 0x09
Option Length = 8 octets
Parity Group Number (PRM_GROUP)
The number of the group of k parity packets amongst the h parity
packets within the transmission group to which the parity packet
belongs, where the first k parity packets are in group zero.
PRM_GROUP MUST NOT be zero.
OPT_PARITY_GRP MAY be appended only to parity packets.
OPT_PARITY_GRP is NOT network-significant.
11.8.3. OPT_CURR_TGSIZE - Packet Extension Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|E| Option Type | Option Length |Reserved |F|OPX|U| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Actual Transmission Group Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type = 0x0A
Option Length = 8 octets
Actual Transmission Group Size (PRM_ATGSIZE)
The actual number of data packets in this transmission group.
This MUST be less than or equal to the maximum transmission group
size PARITY_PRM_TGS in OPT_PARITY_PRM.
OPT_CURR_TGSIZE MAY be appended to data and parity packets (ODATA or
RDATA) and to SPMs.
OPT_CURR_TGSIZE is network-significant except when appended to ODATA.
12. Appendix B - Support for Congestion Control
12.1. Introduction
A source MUST implement strategies for congestion avoidance, aimed at
providing overall network stability, fairness among competing PGM
flows, and some degree of fairness towards coexisting TCP flows [13].
In order to do this, the source must be provided with feedback on the
status of the network in terms of traffic load. This appendix
specifies NE procedures that provide such feedback to the source in a
scalable way. (An alternative TCP-friendly scheme for congestion
control that does not require NE support can be found in [16]).
The procedures specified in this section enable the collection and
selective forwarding of three types of feedback to the source:
o Worst link load as measured in network elements.
o Worst end-to-end path load as measured in network elements.
o Worst end-to-end path load as reported by receivers.
This specification defines in detail NE procedures, receivers
procedures and packet formats. It also defines basic procedures in
receivers for generating congestion reports. This specification does
not define the procedures used by PGM sources to adapt their
transmission rates in response of congestion reports. Those
procedures depend upon the specific congestion control scheme.
PGM defines a header option that PGM receivers may append to NAKs
(OPT_CR). OPT_CR carries congestion reports in NAKs that propagate
upstream towards the source.
During the process of hop-by-hop reverse NAK forwarding, NEs examine
OPT_CR and possibly modify its contents prior to forwarding the NAK
upstream. Forwarding CRs also has the side effect of creating
congestion report state in the NE. The presence of OPT_CR and its
contents also influences the normal NAK suppression rules. Both the
modification performed on the congestion report and the additional
suppression rules depend on the content of the congestion report and
on the congestion report state recorded in the NE as detailed below.
OPT_CR contains the following fields:
OPT_CR_NE_WL Reports the load in the worst link as detected though
NE internal measurements
OPT_CR_NE_WP Reports the load in the worst end-to-end path as
detected though NE internal measurements
OPT_CR_RX_WP Reports the load in the worst end-to-end path as
detected by receivers
A load report is either a packet drop rate (as measured at an NE's
interfaces) or a packet loss rate (as measured in receivers). Its
value is linearly encoded in the range 0-0xFFFF, where 0xFFFF
represents a 100% loss/drop rate. Receivers that send a NAK bearing
OPT_CR determine which of the three report fields are being reported.
OPT_CR also contains the following fields:
OPT_CR_NEL A bit indicating that OPT_CR_NE_WL is being reported.
OPT_CR_NEP A bit indicating that OPT_CR_NE_WP is being reported.
OPT_CR_RXP A bit indicating that OPT_CR_RX_WP is being reported.
OPT_CR_LEAD A SQN in the ODATA space that serves as a temporal
reference for the load report values. This is
initialized by receivers with the leading edge of the
transmit window as known at the moment of transmitting
the NAK. This value MAY be advanced in NEs that
modify the content of OPT_CR.
OPT_CR_RCVR The identity of the receiver that generated the worst
OPT_CR_RX_WP.
The complete format of the option is specified later.
12.2. NE-Based Worst Link Report
To permit network elements to report worst link, receivers append
OPT_CR to a NAK with bit OPT_CR_NEL set and OPT_CR_NE_WL set to zero.
NEs receiving NAKs that contain OPT_CR_NE_WL process the option and
update per-TSI state related to it as described below. The ultimate
result of the NEs' actions ensures that when a NAK leaves a sub-tree,
OPT_CR_NE_WL contains a congestion report that reflects the load of
the worst link in that sub-tree. To achieve this, NEs rewrite
OPT_CR_NE_WL with the worst value among the loads measured on the
local (outgoing) links for the session and the congestion reports
received from those links.
Note that the mechanism described in this sub-section does not permit
the monitoring of the load on (outgoing) links at non-PGM-capable
multicast routers. For this reason, NE-Based Worst Link Reports
SHOULD be used in pure PGM topologies only. Otherwise, this
mechanism might fail in detecting congestion. To overcome this
limitation PGM sources MAY use a heuristic that combines NE-Based
Worst Link Reports and Receiver-Based Reports.
12.3. NE-Based Worst Path Report
To permit network elements to report a worst path, receivers append
OPT_CR to a NAK with bit OPT_CR_NEP set and OPT_CR_NE_WP set to zero.
The processing of this field is similar to that of OPT_CR_NE_WL with
the difference that, on the reception of a NAK, the value of
OPT_CR_NE_WP is adjusted with the load measured on the interface on
which the NAK was received according to the following formula:
OPT_CR_NE_WP = if_load + OPT_CR_NE_WP * (100% - if_loss_rate)
The worst among the adjusted OPT_CR_NE_WP is then written in the
outgoing NAK. This results in a hop-by-hop accumulation of link loss
rates into a path loss rate.
As with OPT_CR_NE_WL, the congestion report in OPT_CR_NE_WP may be
invalid if the multicast distribution tree includes non-PGM-capable
routers.
12.4. Receiver-Based Worst Report
To report a packet loss rate, receivers append OPT_CR to a NAK with
bit OPT_CR_RXP set and OPT_CR_RX_WP set to the packet loss rate. NEs
receiving NAKs that contain OPT_CR_RX_WP process the option and
update per-TSI state related to it as described below. The ultimate
result of the NEs' actions ensures that when a NAK leaves a sub-tree,