INTERNET-DRAFT PGM Reliable Transport Protocol Tony Speakman
Expires 24 December 1999 Nidhi Bhaskar
Richard Edmonstone
Dino Farinacci
Steven Lin
Alex Tweedly
Lorenzo Vicisano
cisco Systems
Jim Gemmell
Microsoft
24 June 1999
PGM Reliable Transport Protocol Specification
<draft-speakman-pgm-spec-03.txt>
Status of this Memo
This document is an Internet-Draft and is in full conformance with all
provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering Task
Force (IETF), its areas, and its working groups. Note that other groups
may also distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet- Drafts as reference material
or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Abstract
Pragmatic General Multicast (PGM) is a reliable multicast transport pro-
tocol for applications that require ordered or unordered, duplicate-
free, multicast data delivery from multiple sources to multiple
receivers. PGM guarantees that a receiver in the group either receives
all data packets from transmissions and repairs, or is able to detect
unrecoverable data packet loss. PGM is specifically intended as a work-
able solution for multicast applications with basic reliability
[Page 1]
INTERNET-DRAFT PGM Specification 24 June 1999
requirements. Its central design goal is simplicity of operation with
due regard for scalability and network efficiency.
[Page 2]
INTERNET-DRAFT PGM Specification 24 June 1999
Revision History
draft-speakman-pgm-spec-00.txt January 1998
Original draft.
draft-speakman-pgm-spec-01.txt January 1998
Deleted reference to proprietary trademark.
draft-speakman-pgm-spec-02.txt August 1998
This revision benefited from general discussions in the forum of
the Reliable Multicast IRTF as well as from individual discussion
with Dan Leshchiner concerning source addressing and NAK elimina-
tion, with Chetan Rai concerning TPDU ordering and local
retransmission, and with Jim Gemmell, Luigi Rizzo, and Lorenzo
Vicisano concerning FEC.
Clarified that RDATA from DLRs and NCFs from network elements must
bear the ODATA source's source NLA.
Added NAK elimination timer and corresponding procedures to net-
work elements.
Added procedures and packet formats to incorporate FEC.
Changed all the packet type encodings to anticipate versioning and
extension.
Added work-in-progress items for RDATA delay at the source and
minimum NAK back-off at receivers.
Added work-in-progress items for SPMRs.
draft-speakman-pgm-spec-03.txt June 1999
The polling and implosion control procedures in this document were
developed jointly with Jim Gemmell who contributed invaluable
review, revision, and critique to this revision. This revision
was edited by Nidhi Bhaskar, Richard Edmonstone, Jim Gemmell, and
Lorenzo Vicisano all of whom contributed to the simplification and
clarification of the text as well as new ideas for PGM operation,
polling, and implosion control. The work on SPMRs arose from dis-
cussions with Dan Leshchiner.
Removed range NAKs for re-working.
[Page 3]
INTERNET-DRAFT PGM Specification 24 June 1999
Generalized and simplified methods for advancing transmit window.
Removed increment sequence number from SPM packets.
Removed Appendix B's information for congestion avoidance.
Removed "local retransmission" in favour of full DLR functional-
ity.
Added generic polling capability within a single PGM hop.
Added procedures to adjust NAK_BO_IVL dynamically and to address
potential NAK implosion problems
Added SPMR procedures and packet formats.
[Page 4]
INTERNET-DRAFT PGM Specification 24 June 1999
Table of Contents
Abbreviations ..................................................... 6
1. Introduction and Overview ..................................... 7
2. Architectural Description ..................................... 13
3. Terms and Concepts ............................................ 15
4. Procedures - General .......................................... 25
5. Procedures - Sources .......................................... 25
6. Procedures - Receivers ........................................ 29
7. Procedures - Network Elements ................................. 33
8. Packet Formats ................................................ 38
9. Options ....................................................... 48
10. Security Considerations ....................................... 58
Appendix A - Forward Error Correction ............................. 60
Appendix B - Congestion Avoidance ................................. 71
Appendix C - Flow Control ......................................... 72
Appendix D - SPM Requests ......................................... 80
Appendix E - Poll Mechanism ....................................... 84
Appendix F - Implosion Prevention ................................. 93
Work in Progress .................................................. 99
Acknowledgements .................................................. 100
References ........................................................ 101
[Page 5]
INTERNET-DRAFT PGM Specification 24 June 1999
Abbreviations
ACK Acknowledgement
AFI Address Family Indicator
ALF Application Level Framing
APDU Application Protocol Data Unit
ARQ Automatic Repeat reQuest
DLR Designated Local Repairer
GSI Globally Unique Source Identifier
FEC Forward Error Correction
MD5 Message-Digest Algorithm
MTU Maximum Transmission Unit
NAK Negative Acknowledgement
NCF NAK Confirmation
NLA Network Layer Address
NNAK Null Negative Acknowledgment
ODATA Original Data
RDATA Repair Data
RSN Receive State Notification
SPM Source Path Message
SPMR SPM Request
TG Transmission Group
TGSIZE Transmission Group Size
TPDU Transport Protocol Data Unit
TSI Transport Session Identifier
TSN Transmit State Notification
[Page 6]
INTERNET-DRAFT PGM Specification 24 June 1999
1. Introduction and Overview
A variety of reliable protocols have been proposed for multicast data
delivery, each with an emphasis on particular types of applications,
network characteristics, or definitions of reliability ([1], [2], [3],
[4]). In this tradition, Pragmatic General Multicast (PGM) is a reli-
able transport protocol for applications that require ordered or unor-
dered, duplicate-free, multicast data delivery from multiple sources to
multiple receivers.
PGM is specifically intended as a workable solution for multicast appli-
cations with basic reliability requirements rather than as a comprehen-
sive solution for multicast applications with sophisticated ordering,
agreement, and robustness requirements. Its central design goal is sim-
plicity of operation with due regard for scalability and network effi-
ciency.
PGM has no notion of group membership. It simply provides reliable mul-
ticast data delivery within a transmit window advanced by a source
according to a purely local strategy. Reliable delivery is provided
within a source's transmit window from the time a receiver joins the
group until it departs. PGM guarantees that a receiver in the group
either receives all data packets from transmissions and repairs, or is
able to detect unrecoverable data packet loss. PGM supports any number
of sources within a multicast group, each fully identified by a globally
unique Transport Session Identifier (TSI), but since these
sources/sessions operate entirely independently of each other, this
specification is phrased in terms of a single source and extends without
modification to multiple sources.
More specifically, PGM is not intended for use with applications that
depend either upon acknowledged delivery to a known group of recipients,
or upon total ordering amongst multiple sources.
Rather, PGM is best suited to those applications in which members may
join and leave at any time, and that are either insensitive to unrecov-
erable data packet loss or are prepared to resort to application
recovery in the event. Through its optional extensions, PGM provides
specific mechanisms to support applications as disparate as stock and
news updates, data conferencing, and low-delay, real-time video
transfer.
In the following text, transport-layer originators of PGM data packets
are referred to as sources, transport-layer consumers of PGM data pack-
ets are referred to as receivers, and network-layer entities in the
intervening network are referred to as network elements. Unless other-
wise specified, the term "repair" will be used to indicate both the
actual retransmission of a copy of a missing packet or the transmission
[Page 7]
INTERNET-DRAFT PGM Specification 24 June 1999
of an FEC repair packet.
1.1. Summary of Operation
PGM runs over a datagram multicast protocol such as IP multicast [5].
In the normal course of data transfer, a source multicasts sequenced
data packets (ODATA), and receivers unicast selective negative ack-
nowledgements (NAKs) for data packets detected to be missing from the
expected sequence. Network elements forward NAKs PGM-hop-by-PGM-hop to
the source, and confirm each hop by multicasting a NAK confirmation
(NCF) in response on the interface on which the NAK was received.
Repairs (RDATA) may be provided either by the source itself or by a
Designated Local Repairer (DLR) in response to a NAK.
Since NAKs provide the sole mechanism for reliability, PGM is particu-
larly sensitive to their loss. To minimize NAK loss, PGM defines a
network-layer hop-by-hop procedure for reliable NAK forwarding.
Upon detection of a missing data packet, a receiver repeatedly unicasts
a NAK to the last-hop PGM network element on the distribution tree from
the source. A receiver repeats this NAK until it receives a NAK confir-
mation (NCF) multicast to the group from that PGM network element. That
network element responds with an NCF to the first occurrence of the NAK
and any further retransmissions of that same NAK from any receiver. In
turn, the network element repeatedly forwards the NAK to the upstream
PGM network element on the reverse of the distribution path from the
source of the original data packet until it also receives an NCF from
that network element. Finally, the source itself receives and confirms
the NAK by multicasting an NCF to the group.
While NCFs are multicast to the group, they are not propagated by PGM
network elements since they act as hop-by-hop confirmations.
To avoid NAK implosion, PGM specifies procedures for subnet-based NAK
suppression amongst receivers and NAK elimination within network ele-
ments. The usual result of this procedure is the propagation of just
one copy of a given selective NAK along the reverse of the distribution
path from any network with directly connected receivers to a source.
The net effect is that unicast NAKs return from a receiver to a source
on the reverse of the path on which ODATA was forwarded, that is, on the
reverse of the distribution tree from the source. More specifically,
they return through exactly the same sequence of PGM network elements
through which ODATA was forwarded, but in reverse. The reasons for han-
dling NAKs this way will become clear in the discussion of constraining
repairs, but first it's necessary to describe the mechanisms for estab-
lishing the requisite source path state in PGM network elements.
[Page 8]
INTERNET-DRAFT PGM Specification 24 June 1999
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 also act to alert receivers that the oldest data in the transmit
window is about to be retired from the transmit window and will,
thereafter, not be available for repair from the source. SPMs are sent
by a source at least at the rate at which the transmit window is
advanced, and they serve to provoke further NAKs from receivers as well
as to maintain receive window state in the receivers.
As a further efficiency, PGM specifies procedures for the constraint of
repairs by network elements so that they reach only those group members
that missed the original transmission. As NAKs traverse the reverse of
the ODATA path (upward), they establish repair state in the network ele-
ments 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, Appen-
dix A specifies Forward Error Correction (FEC) procedures for sources to
provide and receivers to request general error correcting parity packets
rather than selective retransmissions.
Finally, since PGM operates without regular return traffic from
receivers, conventional feedback mechanisms for transport flow and
congestion control cannot be applied. Appendix B will specify some
preliminary strategies for congestion avoidance to be modified and pro-
ven or discarded as experience dictates. Appendix C specifies a basic
and optional flow control supplement native to PGM itself that intro-
duces a degree of receiver feedback, but it is entirely elective and not
meant as a replacement for reservation protocols or other out-of-band
resource and conference management strategies. In its basic operation,
therefore, 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).
[Page 9]
INTERNET-DRAFT PGM Specification 24 June 1999
1.2. Design Goals and Constraints
PGM has been designed to serve that broad range of multicast applica-
tions that have relatively simple reliability requirements, and to do so
in a way that realizes the much advertised but often unrealized network
efficiences of multicast data transfer. The usual impediments to real-
izing these efficiences are the implosion of negative and positive ack-
nowledgements from receivers to senders, repair latency from the source,
and the propagation of repairs to disinterested receivers.
1.2.1. Reliability.
Reliable data delivery across an unreliable network is conventionally
achieved through an end-to-end protocol in which a source (implicitly or
explicitly) solicits receipt confirmation from a receiver, and the
receiver responds positively or negatively. While the frequency of
negative acknowledgements is a function of the reliability of the net-
work and the receiver's resources (and so, potentially quite low), the
frequency of positive acknowledgements is fixed at at least the rate at
which the transmit window is advanced, and usually more often.
Negative acknowledgements primarily determine repairs and reliability.
Positive acknowledgements primarily determine transmit buffer manage-
ment.
When these principles are extended without modification to multicast
protocols, the result, at least for positive acknowledgements, is a bur-
den of positive acknowledgments transmitted to the source that quickly
threatens to overwhelm it as the number of receivers grows. More suc-
cinctly, ACK implosion keeps ACK-based reliable multicast protocols from
scaling well.
One of the goals of PGM is to get as strong a definition of reliability
as possible from as simple a protocol as possible. ACK implosion can be
addressed in a variety of effective but complicated ways, most of which
require re-transmit capability from other than the original source.
An alternative is to dispense with positive acknowledgements altogether,
and to resort to other strategies for buffer management while retaining
negative acknowledgements for repairs and reliability. The approach
taken in PGM is to retain negative acknowledgements, but to dispense
with positive acknowledgements and resort instead to timeouts at the
source to manage transmit resources.
The definition of reliability with PGM is a direct consequence of this
design decision. PGM guarantees that a receiver either receives all
data packets from transmissions and repairs, or is able to detect unre-
coverable data packet loss.
[Page 10]
INTERNET-DRAFT PGM Specification 24 June 1999
PGM includes strategies for repeatedly soliciting NAKs from receivers,
and for adding reliability to the NAKs themselves. By reinforcing the
NAK mechanism, PGM minimizes the probability that a receiver will detect
a missing data packet so late that the packet is unavailable for repair
either from the source or from a designated local repairer (DLR).
Without ACKs and knowledge of group membership, however, PGM cannot
eliminate this possibility.
1.2.2. Group Membership
A second consequence of eliminating ACKs is that knowledge of group
membership is neither required nor provided by the protocol. Although a
source may receive some PGM packets (NAKs for instance) from some
receivers, the identity of the receivers does not figure in the process-
ing of those packets. Group membership may change during the course of
a PGM transport session without the knowledge of or consequence to the
source or the remaining receivers.
1.2.3. Efficiency
While PGM avoids the implosion of positive acknowledgements simply by
dispensing with ACKs, the implosion of negative acknowledgements is
addressed directly.
Receivers observe a random back-off prior to generating a NAK during
which interval the NAK is suppressed by the receiver upon receipt of a
matching NCF. In addition, PGM network elements eliminate duplicate
NAKs received on different interfaces on the same network element. The
combination of these two strategies usually results in the source
receiving just a single NAK for any given lost data packet.
Whether a repair is provided from a DLR or the original source, it is
important to constrain that repair to only those network segments con-
taining members that negatively acknowledged the original transmission
rather than propagating it throughout the group. PGM specifies pro-
cedures for network elements to use the pattern of NAKs to define a
sub-tree within the group upon which to forward the corresponding repair
so that it reaches only those receivers that missed it in the first
place.
1.2.4. Simplicity
PGM is designed to achieve the greatest improvement in reliability (as
compared to the usual UDP) with the least complexity. As a result, PGM
does NOT address conference control, global ordering amongst multiple
sources in the group, nor recovery from network partitions.
[Page 11]
INTERNET-DRAFT PGM Specification 24 June 1999
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 multi-
cast 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 con-
sistent across non-PGM network elements. Note that for NAK suppression
to be most effective, receivers should always have a PGM network element
as a first hop network element between themselves and every path to
every PGM source. If receivers are several hops removed from the first
PGM network element, the efficacy of NAK suppression may degrade.
1.3. Options
In addition to the basic data transfer operation described above, PGM
specifies several end-to-end options to address specific application
requirements. PGM specifies options to support fragmentation, late
joining, time-stamping, reception quality reports, sequence number dro-
pout, redirection, and Forward Error Correction (FEC). Options may be
appended to PGM 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. Fragmentation
is incompatible with the sequence number dropout option.
Late joining allows a source to indicate whether or not receivers may
request all available repairs when they initially join a particular
transport session.
Time stamps may be used in conjunction with NAKs to allow receivers to
specify the interval in which the requested RDATA is relevant to them.
That interval is interpreted by both network elements and sources to
determine whether to continue with or abandon a given repair.
Reception quality reports may be used in conjunction with NAKs to allow
receivers to provide a reception quality metric for local interpretation
[Page 12]
INTERNET-DRAFT PGM Specification 24 June 1999
at the source for the purpose of congestion control.
Sequence number dropout may be used in conjunction with data packets to
allow sources and network elements to selectively eliminate PGM data
packets and convey the resulting sequence-number discontinuity to
receivers so that reliability can be preserved across the dropout.
Sequence number dropout is incompatible with the fragmentation option.
Redirection may be used in conjunction with NCFs to allow a DLR to
respond to normal NCFs with a redirecting NCF advertising its own
address as an alternative to the original source. Recipients of
redirecting NCFs may then direct subsequent NAKs 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.
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 relia-
bility of NAKs and to constrain the propagation of repairs. The divi-
sion of these functions is described in this section and expanded in
detail in the next section.
2.1. Source Functions
Data Transmission
Sources multicast ODATA packets to the group within the transmit
window at a given transmit rate.
Source Path State
Sources multicast SPMs to the group, interleaved with ODATA if
present, to establish source path state in PGM network elements.
NAK Reliability
Sources multicast NCFs to the group in response to any NAKs they
receive.
Repairs
[Page 13]
INTERNET-DRAFT PGM Specification 24 June 1999
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=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 receive window that
advances the receive window.
2.3. Network Element Functions
Network elements forward ODATA without intervention.
[Page 14]
INTERNET-DRAFT PGM Specification 24 June 1999
Source Path State
Network elements intercept SPMs and use them to establish source
path state for the corresponding source and group before multicast
forwarding them in the usual way.
NAK Reliability
Network elements multicast NCFs to the group in response to any
NAK they receive. For each NAK received, network elements create
repair state recording the transport session identifier, the
sequence number of the NAK, and the input interface on which the
NAK was received.
Constrained NAK Forwarding
Network elements repeatedly unicast forward only the first copy of
any NAK they receive to the upstream PGM network element on the
distribution path for the TSI and in addition they may optionally
multicast this NAK upstream with TTL=1. They do this until they
receive an NCF in response.
NAK Elimination
Network elements discard exact duplicates of any NAK for which
they already have repair state (i.e., that has been forwarded
either by themselves or a neighbouring PGM network element), and
respond with a matching NCF.
Constrained RDATA Forwarding
Network elements use NAKs to maintain repair state consisting of a
list of interfaces upon which a given NAK was received, and they
return the corresponding RDATA only on these interfaces.
NAK Anticipation
If a network element hears an upstream NCF (i.e., on the upstream
interface for the distribution tree for the TSI), it establishes
repair state without outgoing interfaces in anticipation of
responding to and eliminating duplicates of the NAK that may
arrive from downstream.
3. Terms and Concepts
Before proceeding from the preceding overview to the detail in the sub-
sequent Procedures, this section presents some concepts and definitions
that make that detail more intelligible.
[Page 15]
INTERNET-DRAFT PGM Specification 24 June 1999
3.1. Transport Session Identifiers
Every PGM packet is identified by a:
TSI transport session identifier
TSIs must be globally unique, and only one source at a time may act as
the source for a transport session. (Note that repairers do not change
the TSI in any RDATA they transmit). TSIs are composed of the concate-
nation of a globally unique source identifier (GSI) and a source-
assigned data-source port.
Since all PGM packets originated by receivers are in response to PGM
packets originated by a source, receivers simply echo the TSI heard from
the source in any corresponding packets they originate.
Since all PGM packets originated by network elements are in response to
PGM packets originated by a receiver, network elements simply echo the
TSI heard from the receiver in any corresponding packets they originate.
3.2. Sequence Numbers
PGM uses a circular sequence number space from 0 through ((2**32) - 1)
to identify and order ODATA packets. Sources must number ODATA packets
in unit increments in the order in which the corresponding application
data is submitted for transmission. Within a transmit or receive window
(defined below), a sequence number x is "less" or "older" than sequence
number y if it numbers an ODATA packet preceding ODATA packet y, and a
sequence number y is "greater" or "more recent" than sequence number x
if it numbers an ODATA packet subsequent to ODATA packet x.
3.3. Transmit Window
The description of the operation of PGM rests fundamentally on the
definition of the source-maintained transmit window. This definition in
turn is derived directly from the amount of transmitted data (in
seconds) a source retains for repair (TXW_SECS), and the maximum
transmit rate (in bytes/second) maintained by a source to regulate its
bandwidth utilization (TXW_MAX_RTE).
The size of the transmit window in seconds is simply TXW_SECS. The size
of the transmit window in bytes (TXW_BYTES) is (TXW_MAX_RTE * TXW_SECS).
The size of the transmit window in sequence numbers (TXW_SQNS) is
(TXW_BYTES / bytes-per-packet).
In terms of sequence numbers, the transmit window is the range of
sequence numbers consumed by the source for sequentially numbering and
transmitting the most recent TXW_SECS of ODATA packets. The trailing
[Page 16]
INTERNET-DRAFT PGM Specification 24 June 1999
(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) must be no
greater than half the PGM sequence number space less one.
The fraction of the transmit window size (in seconds of data) by which
the transmit window is advanced (TXW_ADV_SECS) is called the window
increment. The trailing (oldest) such fraction of the transmit window
itself is called the increment window.
In terms of sequence numbers, the increment window is the range of
sequence numbers that will be the first to be expired from the transmit
window. The trailing (or left) edge of the increment window is just
TXW_TRAIL, the trailing (or left) edge of the transmit window. The
leading (or right) edge of the increment window (TXW_INC) is defined as
one less than the sequence number of the first data packet transmitted
by the source TXW_ADV_SECS after transmitting TXW_TRAIL.
A data packet is described as being "in" the transmit or increment win-
dow, respectively, if its sequence number is in the range defined by the
transmit or increment window, respectively.
The transmit window is advanced across the increment window by the
source when it increments TXW_TRAIL to TXW_INC. When the transmit win-
dow is advanced across the increment window, the increment window is
emptied (i.e., TXW_TRAIL is momentarily equal to TXW_INC), begins to
refill immediately as transmission proceeds, is full again TXW_ADV_SECS
later (i.e., TXW_TRAIL is separated from TXW_INC by TXW_ADV_SECS of
data), at which point the transmit window is advanced again, and so on.
Consider the following example:
Assuming a constant transmit rate of 128kbps and a constant data
packet size of 1500 bytes, if a source maintains the past 30 seconds
of data for repair and increments its transmit window in 5 second
increments, then
TXW_MAX_RTE = 16kBps
TXW_ADV_SECS = 5 seconds,
TXW_SECS = 35 seconds,
TXW_BYTES = 560kB,
TXW_SQNS = 383 (rounded up),
[Page 17]
INTERNET-DRAFT PGM Specification 24 June 1999
and the size of the increment window in sequence numbers
(TXW_MAX_RTE * TXW_ADV_SECS / 1500) = 54 (rounded down).
Continuing this example, the following is a diagram of the transmit win-
dow and the increment window therein in terms of sequence numbers.
TXW_TRAIL TXW_LEAD
| |
| |
|--|--------------- Transmit Window -------------|----|
v | | v
v v
... +-----+-----+-...-+------+------+-...-+-------+-------+ .....
n-1 | n | n+1 | ... | n+53 | n+54 | ... | n+381 | n+382 | n+383
... +-----+-----+-...-+------+------+-...-+-------+-------+ .....
^
^ | ^
|--- Increment Window|---|
|
|
TXW_INC
So the values of the sequence numbers defining these windows are:
TXW_TRAIL = n
TXW_INC = n+53
TXW_LEAD = n+382
NOTA BENE: In this example the window sizes in terms of sequence
numbers can be determined only because of the assumption of a con-
stant data packet size of 1500 bytes. When the data packet sizes are
variable, more or fewer sequence numbers may be consumed transmitting
the same amount (TXW_BYTES) of data.
So, for a given transport session identified by a TSI, a source main-
tains:
TXW_MAX_RTE a maximum transmit rate in kBytes per second, the cumula-
tive transmit rate of some combination of SPMs, ODATA,
and RDATA depending on the transmit window advancement
strategy
TXW_TRAIL the sequence number defining the trailing edge of the
transmit window, the sequence number of the oldest data
packet available for repair
TXW_LEAD the sequence number defining the leading edge of the
[Page 18]
INTERNET-DRAFT PGM Specification 24 June 1999
transmit window, the sequence number of the most recently
transmitted ODATA packet
TXW_INC the sequence number defining the leading edge of the
increment window, the sequence number of the most
recently transmitted data packet amongst those that will
expire upon the next increment of the transmit window
PGM does not constrain the strategies that a source may use for advanc-
ing the transmit window. A source may implement any scheme or number of
schemes. This is possible because a PGM receiver must obey the window
provided by the source in its packets. Three strategies are suggested
within this document.
In the first, called "Advance with Time", the transmit window maintains
the last TXW_SECS of data in real-time, regardless of whether any data
was sent in that real time period or not. The actual number of bytes
maintained at any instant in time will vary between 0 and TXW_BYTES,
depending on traffic during the last TXW_SECS. In this case,
TXW_MAX_RTE is the cumulative transmit rate of SPMs and ODATA.
In the second, called "Advance with Data", the transmit window maintains
the last TXW_BYTES bytes of data for repair. That is, it maintains the
theoretical maximum amount of data that could be transmitted in the time
period TXW_SECS, regardless of when they were transmitted. In this
case, TXW_MAX_RTE is the cumulative transmit rate of SPMS, ODATA, and
RDATA.
The third strategy leaves control of the window in the hands of the
application. The API provided by a source implementation for this,
could allow the application to control the window in terms of APDUs and
to manually step the window. This gives a form of Application Level
Framing (ALF). In this case, TXW_MAX_RTE is the cumulative transmit
rate of SPMs, ODATA, and RDATA.
Happily, everything else in this section is a LOT easier to explain than
the transmit window.
3.4. Receive Window
The receive window at the receivers is determined entirely by PGM pack-
ets from the source. That is, a receiver simply obeys what the source
tells it in terms of window state and advancement.
For a given transport session identified by a TSI, a receiver maintains:
RXW_TRAIL the sequence number defining the trailing edge of the
receive window, the sequence number (known from data
[Page 19]
INTERNET-DRAFT PGM Specification 24 June 1999
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
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 essen-
tial that NAKs return from a receiver to a source on the reverse of the
distribution tree from the source. That is, they must return through
the same sequence of PGM network elements through which the ODATA was
forwarded, but in reverse. There are two reasons for this, the less
obvious one being by far the more important one.
The first and obvious reason is that RDATA is forwarded on the same path
as ODATA and so repair state must be established on this path if it is
to constrain the propagation of RDATA.
The second and less obvious reason is that in the absence of repair
state, PGM network elements do NOT forward RDATA, so the default
behaviour is to discard repairs. If repair state is not properly esta-
blished for interfaces on which ODATA went missing, then receivers on
those interfaces will continue to NAK for lost data and ultimately
experience unrecoverable data loss.
The principle function of SPMs is to provide the source path state
required for PGM network elements to forward NAKs from one PGM network
element to the next on the reverse of the distribution tree for the TSI,
establishing repair state each step of the way. This source path state
is simply the address of the upstream PGM network element on the reverse
of the distribution tree for the TSI. That upstream PGM network element
may be more than one subnet hop away. SPMs establish the identity of
the upstream PGM network element on the distribution tree for each TSI
in each group in each PGM network element, a sort of virtual PGM topol-
ogy. So although NAKs are unicast addressed, they are NOT unicast
[Page 20]
INTERNET-DRAFT PGM Specification 24 June 1999
routed by PGM network elements in the conventional sense. Instead PGM
network elements use the source path state established by SPMs to direct
NAKs PGM-hop-by-PGM-hop toward the source. The idea is to constrain
NAKs to the pure PGM topology spanning the more heterogeneous underlying
topology of both PGM and non-PGM network elements.
The result is repair state in every PGM network element between the
receiver and the source so that the corresponding RDATA is never dis-
carded by a PGM network element for lack of repair state.
SPMs also maintain transmit window state in receivers by advertising the
trailing and leading edges of the transmit window (SPM_TRAIL and
SPM_LEAD). In the absence of data, SPMs may be used to close the
transmit window in time by advancing the transmit window until SPM_TRAIL
and SPM_LEAD are equal.
3.6. Packet Contents
This section just provides enough short-hand to make the Procedures
intelligible. For the full details of packet contents, please refer to
Packet Formats below.
3.6.1. Source Path Messages
3.6.1.1. SPMs
SPMs are transmitted by sources to establish source-path state in PGM
network elements, and to provide transmit-window state in receivers.
SPMs are multicast to the group and contain:
SPM_TSI the source-assigned TSI for the session to which the SPM
corresponds
SPM_SQN a sequence number assigned sequentially by the source in
unit increments and scoped by SPM_TSI
NOTA BENE: this is an entirely separate sequence than is used
to number ODATA and RDATA.
SPM_TRAIL the sequence number defining the trailing edge of the
source's transmit window (TXW_TRAIL)
SPM_LEAD the sequence number defining the leading edge of the
source's transmit window (TXW_LEAD)
SPM_PATH the network-layer address (NLA) of the interface on the
PGM network element on which the SPM is forwarded
[Page 21]
INTERNET-DRAFT PGM Specification 24 June 1999
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 resynchronize to the transport session.
OD_SQN a sequence number assigned sequentially by the source in
unit increments and scoped by OD_TSI
3.6.2.2. RDATA - Repair Data
RDATA packets are repair packets transmitted by sources or DLRs in
response to NAKs.
RDATA packets are multicast to the group and contain:
RD_TSI OD_TSI of the ODATA packet for which this is a repair
RD_TRAIL the sequence number defining the trailing edge of the
source's transmit window (TXW_TRAIL), not necessarily the
same as OD_TRAIL of the ODATA packet for which this is a
repair
RD_SQN OD_SQN of the ODATA packet for which this is a repair
3.6.3. Negative Acknowledgements
3.6.3.1. NAKs - Negative Acknowledgments
NAKs are transmitted by receivers to request repairs for missing data
packets.
NAKs are unicast (PGM-hop-by-PGM-hop) to the source and contain:
[Page 22]
INTERNET-DRAFT PGM Specification 24 June 1999
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 Acknowledgement Confirmations
3.6.4.1. NCFs - NAK confirmations
NCFs are transmitted by network elements and sources in response to
NAKs.
NCFs are multicast to the group and contain:
NCF_TSI NAK_TSI of the NAK being confirmed
NCF_SQN NAK_SQN of the NAK being confirmed
NCF_SRC NAK_SRC of the NAK being confirmed
NCF_GRP NAK_GRP of the NAK being confirmed
3.6.5. Option Encodings
OPT_FRAGMENT - Fragmentation
[Page 23]
INTERNET-DRAFT PGM Specification 24 June 1999
OPT_JOIN - Late Joining
OPT_TIME - Time Stamp
OPT_RXQ - Reception Quality Report
OPT_DROP - Sequence Number Dropout
OPT_REDIRECT - Redirect
OPT_PARITY - Forward Error Correction
[Page 24]
INTERNET-DRAFT PGM Specification 24 June 1999
4. Procedures - General
Since SPMs, NCFs, and RDATA must be treated conditionally by PGM network
elements, they must be distinguished from other packets in the chosen
multicast network protocol if PGM network elements are to extract them
from the usual switching path.
The most obvious way for network elements to achieve this is to examine
every packet in the network for the PGM transport protocol and packet
types. However, the overhead of this approach is costly for high-
performance, multi-protocol network elements. An alternative, and a
requirement for PGM over IP multicast, is that SPMs, NCFs, and RDATA
must be transmitted with the IP Router Alert Option [6]. This option
gives network elements a network-layer indication that a packet should
be extracted from IP switching for more detailed processing.
5. Procedures - Sources
5.1. Data Transmission
Since PGM relies on a purely rate-limited transmission strategy in the
source to bound the bandwidth consumed by PGM transport sessions, an
assortment of techniques is assembled here to make that strategy as con-
servative and robust as possible. These techniques are the minimum
required of a PGM source, and others may be added as experience dic-
tates.
5.1.1. Maximum Cumulative Transmit Rate
A source must number ODATA packets in the order in which they are sub-
mitted for transmission by the application. A source must transmit
ODATA packets in sequence and only within the transmit window beginning
with TXW_TRAIL at no greater a rate than TXW_MAX_RTE.
In the advance with data strategy, TXW_MAX_RTE is the maximum cumulative
transmit rate of SPM, ODATA, and RDATA. The reason for calculating
TXW_MAX_RTE in this way is so that the aggregate bandwidth remains
within TXW_MAX_RATE.
In the advance with time strategy, TXW_MAX_RTE is the maximum cumulative
transmit rate of SPMS and ODATA only. The assumption in calculating
TXW_MAX_RTE in this way is that delivery at a constant rate is the main
concern.
Other transmission strategies may define TXW_MAX_RTE as appropriate for
the implementation.
[Page 25]
INTERNET-DRAFT PGM Specification 24 June 1999
5.1.2. Transmit Rate Regulation
To regulate its transmit rate, a source must use a token bucket scheme
or any other traffic management scheme that yields equivalent behaviour.
A token bucket [7] is characterized by a continually sustainable data
rate (the token rate) and the extent to which the data rate may exceed
the token rate for short periods of time (the token bucket size). Over
any arbitrarily chosen interval, the number of bytes the source may
transmit cannot exceed the token bucket size plus the product of the
token rate and the chosen interval.
In addition, a source must bound the maximum rate at which successive
packets may be transmitted using a leaky bucket scheme drained at a max-
imum transmit rate, or equivalent mechanism.
5.1.3. TPDU Ordering
To preserve the logic of PGM's transmit window, a source must implement
strict priority queueing of pending SPMs, pending RDATA, and pending
ODATA from three separate queues in that order, or implement any mechan-
ism that results in equivalent behaviour.
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 elments
while changes in the underlying distribution tree take place.
5.1.5. Heartbeat SPMs
In the absence of data to transmit, a source should transmit SPMs at a
decaying rate in order to assist early detection of lost data, to main-
tain current source path state in PGM network elements, and to maintain
current receive window state in the receivers.
In this scheme [8], a source maintains an inter-heartbeat timer IHB_TMR
which times the interval between the most recent packet (ODATA, RDATA,
or SPM) transmission and the next heartbeat transmission. IHB_TMR is
initialized to a minimum interval IHB_MIN after the transmission of any
data packet. If IHB_TMR expires, the source transmits a heartbeat SPM
and initializes IHB_TMR to double its previous value. The transmission
of consecutive heartbeat SPMs doubles IHB each time up to a maximum
interval IHB_MAX. The transmission of any data packet initializes
IHB_TMR to IHB_MIN once again. The effect is to provoke prompt
[Page 26]
INTERNET-DRAFT PGM Specification 24 June 1999
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 first timer is just counting down in real-time while the second is
measuring the inter-data-packet interval.
In the presence of data, no heartbeat SPMs will be transmitted since the
transmission of data keeps setting the IHB_TMR back to its initial
value. At the same time however, ambient SPMs must be interleaved into
the data as a matter of course, not necessarily as a heartbeat mechan-
ism. This ambient transmission of SPMs is required to keep the distri-
bution tree information in the network current and to allow new
receivers to synchronize with the session.
It is in the interest of an implementation to de-couple ambient and
heartbeat SPM timers sufficiently to permit them to be configured
independently of each other.
5.2. Negative Acknowledgement Confirmation
A source must immediately multicast an NCF in response to any NAK it
receives. The NCF is required since the alternative of responding
immediately with RDATA would not allow other PGM network elements on the
same subnet to do NAK anticipation, nor would it allow DLRs on the same
subnet to provide repairs. The generation of NCFs should be rate-
limited to protect against a denial of service in the presence of a NAK
storm.
5.3. Repairs
A source must then multicast RDATA (while respecting TXW_MAX_RTE) in
response to any NAK it receives for data packets within the transmit
window. A source should transmit RDATA at priority over concurrent
ODATA. The effect of this priority is to back off the transmission of
ODATA in favour of RDATA.
Note that work in progress is looking at algorithms for delaying RDATA
transmission, to make the overall repair strategy more efficient.
Implementations should not preclude a delay being introduced before
RDATA transmission.
[Page 27]
INTERNET-DRAFT PGM Specification 24 June 1999
5.4. Transmit Window Advance
5.4.1. Advancing across the Increment Window
In anticipation of advancing the transmit window, the source starts a
timer TXW_ADV_IVL_TMR which runs for time period TXW_ADV_IVL.
TXW_ADV_IVL has a value in the range (0, TXW_ADV_SECS). The value may
be configurable or may be determined statically by the strategy used for
advancing the transmit window.
When TXW_ADV_IVL_TMR is running, a source may reset TXW_ADV_IVL_TMR if
NAKs are received for packets in the increment window. In addition, a
source may transmit RDATA in the increment window with priority over
other data within the transmit window.
When TXW_ADV_IVL_TMR expires, a source should advance the trailing edge
of the transmit window from TXW_TRAIL to TXW_INC.
Once the transmit window is advanced across the increment window,
SPM_TRAIL, OD_TRAIL and RD_TRAIL are set to the new value of TXW_TRAIL
in all subsequent transmitted packets, until the next window advance-
ment.
PGM does not constrain the strategies that a source may use for advanc-
ing the transmit window. The source may implement any scheme or number
of schemes. Three suggested strategies are outlined below.
5.4.2. Advancing with Data
In the first strategy, TXW_MAX_RTE is calculated from SPMS and both
ODATA and RDATA, and NAKs reset TXW_ADV_IVL_TMR. In this mode of opera-
tion the transmit window maintains the last TXW_BYTES bytes of data for
repair. That is, it maintains the theoretical maximum amount of data
that could be transmitted in the time period TXW_SECS. This means that
the following timers are not treated as real-time timers, instead they
are "data driven". That is, they expire when the amount of data that
could be sent in the time period they define is sent. They are the SPM
ambient time interval, TXW_ADV_SECS, TXW_SECS, TXW_ADV_IVL,
TXW_ADV_IVL_TMR and the join interval. Note that the SPM heartbeat
timers still run in real-time.
While TXW_ADV_IVL_TMR is running, a source uses the receipt of a NAK for
ODATA within the increment window to reset timer TXW_ADV_IVL_TMR to
TXW_ADV_IVL so that transmit window advancement is delayed until no NAKs
for data in the increment window are seen for TXW_ADV_IVL seconds. If
the transmit window should fill in the meantime, further transmissions
would be suspended until the transmit window can be advanced.
[Page 28]
INTERNET-DRAFT PGM Specification 24 June 1999
A source must advance the transmit window across the increment window
only upon expiry of TXW_ADV_IVL_TMR.
This mode of operation is intended for non-real-time, messaging applica-
tions based on the receipt of complete data at the expense of delay.
5.4.3. Advancing with Time
This strategy advances the transmit window in real-time. In this mode
of operation, TXW_MAX_RTE is calculated from SPMs and ODATA only to
maintain a constant data throughput rate by consuming extra bandwidth
for repairs. TXW_ADV_IVL has the value 0 which advances the transmit
window without regard for whether NAKs for data in the increment window
are still being received.
In this mode of operation, all timers are treated as real-time timers.
This mode of operation is intended for real-time, streaming applications
based on the receipt of timely data at the expense of completeness.
5.4.4. Advancing under explicit application control
Some applications may wish more explicit control of the transmit window
than that provided by the advance with data / time strategies above. An
implementation may provide this mode of operation and allow an applica-
tion to explicitly control the window in terms of APDUs.
6. Procedures - Receivers
6.1. Data Reception
Initial data reception
A receiver should initiate data reception beginning with the first data
packet it receives within the advertised transmit window. This packet's
sequence number (ODATA_SQN) temporarily defines the trailing edge of the
transmit window from the receiver's perspective. That is, it is
assigned to RXW_TRAIL_INIT within the receiver, and until the trailing
edge sequence number advertised in subsequent packets (SPMs or ODATA or
RDATA) increments through RXW_TRAIL_INIT, the receiver must only request
repairs for sequence numbers subsequent to RXW_TRAIL_INIT. Thereafter,
it may request repairs anywhere in the transmit window. This temporary
restriction on repair requests prevents receivers from requesting a
potentially large amount of history when they first begin to receive a
given PGM transport session.
Note that the JOIN option, discussed later, can be used to provide a
different value for RXW_TRAIL_INIT.
[Page 29]
INTERNET-DRAFT PGM Specification 24 June 1999
Receiving and discarding data packets
Within a given transport session, a receiver must receive any ODATA or
RDATA packets within the receive window. A receiver must discard any
data packet that duplicates one already received in the transmit window.
A receiver must discard any data packet outside of the receive window.
Contiguous data
Contiguous data is comprised of those data packets within the receive
window that have been received and are in the range from RXW_TRAIL up to
(but not including) the first missing sequence number in the receive
window. The most recently received data packet of contiguous data
defines the leading edge of contiguous data.
As its default mode of operation, a receiver must deliver only contigu-
ous data packets to the application, and it must do so in the order
defined by those data packets' sequence numbers. This provides applica-
tions with a reliable ordered data flow.
Non contiguous data
PGM receiver implementations may optionally provide a mode of operation
in which data is delivered to an application in the order received.
However, the implementation must only deliver complete application pro-
tocol data units (APDUs) to the application. That is, APDUs that have
been fragmented into different TPDUs must be reassembled before delivery
to the application.
6.2. Source Path Messages
Receivers must receive and sequence SPMs for any TSI they are receiving.
For each TSI, receivers must use the most recent SPM to determine the
NLA of the upstream PGM network element for use in NAK addressing. Note
that a receiver cannot initiate repair requests until it has received at
least one SPM for the corresponding TSI.
6.3. Negative Acknowledgment
Detecting missing data packets
Receivers must detect gaps in the expected data sequence by comparing
the sequence number on the most recently received ODATA or RDATA packet
with the leading edge of contiguous data. If the receiver has not
received all intervening data packets, it must initiate selective NAK
generation for each intervening missing sequence number. Receivers
should temper the initiation of NAK generation to account for simple
mis-ordering introduced by the network.
[Page 30]
INTERNET-DRAFT PGM Specification 24 June 1999
Receivers must also detect gaps in the expected data sequence by compar-
ing SPM_LEAD of the most recently received SPM with the leading edge of
contiguous data. If the receiver has not received all intervening data
packets, it must initiate selective NAK generation for each missing
sequence number.
Generating NAKs
NAK generation requires that a receiver listen to NCFs and NAKs for the
same transport session.
NAK generation also requires that a receiver observe four time out
intervals for any given NAK (i.e., per NAK_TSI and NAK_SQN).
The first time out interval, the NAK random back-off interval
NAK_RB_IVL, randomly delays the transmission of a given NAK from a
receiver. NAK_RB_IVL is counted down from the time a missing data
packet is detected. Expiry of NAK_RB_IVL causes NAK transmission. NAK
transmission is defined as sending a unicast NAK to the PGM upstream
neighbour and a multicast NAK with ttl 1.
The second time out interval, the NAK repeat interval NAK_RPT_IVL, lim-
its the length of time for which a receiver 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 generation and
indicates unrecoverable data loss (due to missing NCF).
The third time out interval, the NAK RDATA interval NAK_RDATA_IVL, lim-
its the length of time for which a receiver will wait for the RDATA
corresponding to a confirmed NAK. NAK_RDATA_IVL is counted down from
the time a matching NCF is received. Expiry of NAK_RDATA_IVL causes the
receiver to select a new value of NAK_RB_IVL, and start again.
The fourth time out interval, the NAK generation interval NAK_GEN_IVL,
limits the length of time for which a receiver will retry a NAK while
waiting for the corresponding RDATA. NAK_GEN_IVL is counted down from
the time a missing data packet is detected. Expiry of NAK_GEN_IVL can-
cels NAK generation and indicates unrecoverable data loss (due to miss-
ing RDATA).
NAK generation follows the detection of a missing data packet and is the
cycle of waiting for NAK_RB_IVL, listening for matching NCFs or NAKs,
transmitting a NAK if a matching NCF or NAK is not heard, waiting
NAK_RDATA_IVL, and recommencing NAK generation if the matching data is
not received. During NAK_RB_IVL, a NAK is said to be pending. During
NAK_RDATA_IVL, a NAK is said to be outstanding.
[Page 31]
INTERNET-DRAFT PGM Specification 24 June 1999
Suspending NAK generation
Suspending NAK generation just means waiting for either NAK_RB_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. A NAK is pending from this receiver
if NAK_RB_IVL for this NAK has been initiated in this receiver but has
not yet passed.
A receiver must suspend NAK generation if a duplicate of the NAK is
already outstanding from this or another receiver. A NAK is outstanding
from this or another receiver if NAK_RDATA_IVL for this NAK has been
initiated in this receiver but has not yet passed.
Backing off NAK transmission
Before transmitting a NAK, a receiver must wait some interval NAK_RB_IVL
chosen randomly and uniformly over NAK_BO_IVL during which it listens
for a matching NAK that may have been transmitted by another receiver or
a matching NCF that may be transmitted in response to the same NAK from
another receiver.
When a receiver has to transmit a sequence of NAKs, it should transmit
the NAKs in order from oldest to newest. The receiver should pace the
NAK sequence so as not to cause a NAK storm on the network.
NAK suppression
A receiver must suspend 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 transmit a NAK to the
upstream PGM network element for the TSI specifying the transport ses-
sion identifier and missing sequence number. It must repeat the NAK at
a rate of NAK_RPT_RTE for an interval of NAK_RPT_IVL until it receives a
matching NCF. It must then wait NAK_RDATA_IVL before recommencing NAK
generation. If it hears a matching NCF during NAK_RDATA_IVL, it must
wait anew for NAK_RDATA_IVL before recommencing NAK generation (i.e.,
NCFs restart NAK_RDATA_IVL).
Receivers should transmit NAKs for data packets in the increment window
at priority over NAKs for data packets in the remainder of the receive
window.
[Page 32]
INTERNET-DRAFT PGM Specification 24 June 1999
Completion of NAK generation
NAK generation is complete only upon the reception of the matching RDATA
(or even ODATA) packet at any time during NAK generation.
Cancellation of NAK generation
NAK generation is canceled upon the advancing of the receive window so
as to exclude the matching sequence number of a pending or outstanding
NAK, or the expiry of NAK_GEN_IVL. Cancellation of NAK generation indi-
cates unrecoverable data loss.
Addressing NAKs
A receiver (unicast) addresses a NAK to the upstream PGM network element
for the TSI. In addition, it may optionally multicast a NAK with TTL=1
to the group. It also records both the address of the source of the
corresponding ODATA and the address of the group in the NAK header.
Receiving NCFs and multicast NAKs
A receiver must discard any NCFs or NAKs it hears for data packets out-
side the receive window.
If a receiver hears an NCF or NAK for a data packet in the receive win-
dow for which it has no repair state, it should discard the NCF/NAK only
if it has already received the matching data packet. If it has not
already received the matching data packet, it should wait NAK_RDATA_IVL
and then commence NAK generation itself, beginning with the random back
off procedure.
7. Procedures - Network Elements
7.1. Source Path State
Upon receipt of an 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 for-
warding 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.
[Page 33]
INTERNET-DRAFT PGM Specification 24 June 1999
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, NCFs
transmitted by network elements must bear the ODATA source's
NLA, not the network element's NLA as might be expected.
The generation of NCFs should be rate-limited to protect against a
denial of service in the presence of a NAK storm.
Simultaneously, network elements must establish repair state for the NAK
if such state does not already exist, and add the interface on which the
NAK was received to the corresponding repair interface list if the
interface is not already listed.
7.3. Constrained NAK Forwarding
The NAK forwarding procedures for network elements are quite similar to
those for receivers, but three important differences should be noted.
First, network elements do NOT back off before forwarding a NAK (i.e.,
there is no NAK_BO_IVL) since the resulting delay of the NAK would com-
pound with each hop. Note that NAK arrivals will be randomized by the
receivers from which they originate, and this factor in conjunction with
NAK anticipation and elimination will combine to forestall NAK storms on
subnets with a dense network element population.
Second, network elements do NOT retry confirmed NAKs (i.e., there is no
NAK_GEN_IVL) if RDATA is not seen; they simply discard the repair state
and rely on receivers to re-request the repair. This approach keeps the
repair state in the network elements relatively ephemeral and responsive
to underlying routing changes.
Third, note that ODATA does NOT cancel NAK forwarding in network ele-
ments since it is switched by network elements without transport-layer
intervention.
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).
The first, the NAK repeat interval NAK_RPT_IVL, limits the length of
time for which a network element will repeat a NAK while waiting for a
corresponding NCF. NAK_RPT_IVL is counted down from the transmission of
[Page 34]
INTERNET-DRAFT PGM Specification 24 June 1999
a NAK. Expiry of NAK_RPT_IVL cancels NAK forwarding (due to missing
NCF).
The second, the NAK RDATA interval NAK_RDATA_IVL, limits the length of
time for which a network element will wait for the corresponding RDATA.
NAK_RDATA_IVL is counted down from the time a matching NCF is received.
Expiry of NAK_RDATA_IVL causes the network element to discard the
corresponding repair state (due to missing RDATA).
During NAK_RPT_IVL, a NAK is said to be pending. During NAK_RDATA_IVL,
a NAK is said to be outstanding.
A Network element must forward NAKs only to the upstream PGM network
element for the TSI.
A network element must repeat a NAK at a rate of NAK_RPT_RTE for an
interval of NAK_RPT_IVL until it receives a matching NCF. A matching
NCF must match NCF_TSI with NAK_TSI, and NCF_SQN with NAK_SQN.
Upon reception of the corresponding NCF, network elements must wait at
least NAK_RDATA_IVL for the corresponding RDATA. Receipt of the
corresponding RDATA at any time during NAK forwarding cancels NAK for-
warding and tears down the corresponding repair state in the network
element.
7.4. NAK elimination
Two NAKs duplicate each other if they bear the same NAK_TSI and NAK_SQN.
Network elements must discard all duplicates of a NAK that is pending.
Once a NAK is outstanding, network elements must discard all duplicates
of that NAK for NAK_ELIM_IVL. Upon expiry of NAK_ELIM_IVL, network ele-
ments must suspend NAK elimination for that TSI/SQN until the first
duplicate of that NAK is seen after the expiry of NAK_ELIM_IVL. This
duplicate must be forwarded in the usual manner. Once this duplicate
NAK is outstanding, network elements must once again discard all dupli-
cates of that NAK for NAK_ELIM_IVL, and so on. NAK_RDATA_IVL must be
reset each time a NAK for the corresponding TSI/SQN is confirmed (i.e.,
each time NAK_ELIM_IVL is reset). NAK_ELIM_IVL must be some small frac-
tion of NAK_RDATA_IVL.
NAK_ELIM_IVL acts to balance implosion prevention against repair state
liveness. That is, it results in the elimination of all but at most one
NAK per NAK_ELIM_IVL thereby allowing repeated NAKs to keep the repair
state alive in the PGM network elements.
[Page 35]
INTERNET-DRAFT PGM Specification 24 June 1999
7.5. NAK Anticipation
An unsolicited NCF is one that is received by a network element when the
network element has no corresponding pending or outstanding NAK. Net-
work elements must process unsolicited NCFs differently depending on the
interface on which they are received.
If the interface on which an NCF is received is the same interface the
network element would use to reach the upstream PGM network element, the
network element simply establishes repair state for NCF_TSI and NCF_SQN
without adding the interface to the repair interface list, and discards
the NCF. If the repair state already exists, the network element res-
tarts the NAK_RDATA and NAK_ELIM_IVL timers and discards the NCF.
If the interface on which an NCF is received is not the same interface
the network element would use to reach the upstream PGM network element,
the network element does not establish repair state and just discards
the NCF.
Anticipated NAKs permit the elimination of any subsequent matching NAKs
from downstream. Upon establishing anticipated repair state, network
elements must eliminate subsequent NAKs only for a period of
NAK_ELIM_IVL. Upon expiry of NAK_ELIM_IVL, network elements must
suspend NAK elimination for that TSI/SQN until the first duplicate of
that NAK is seen after the expiry of NAK_ELIM_IVL. This duplicate must
be forwarded in the usual manner. Once this duplicate NAK is outstand-
ing, network elements must once again discard all duplicates of that NAK
for NAK_ELIM_IVL, and so on. NAK_RDATA_IVL must be reset each time a
NAK for the corresponding TSI/SQN is confirmed (i.e., each time
NAK_ELIM_IVL is reset). NAK_ELIM_IVL must be some small fraction of
NAK_RDATA_IVL.
7.6. NAK Shedding
Network elments may implement local procedures for withholding NAK con-
firmations for receivers detected to be reporting excessive loss. The
result of these procedures would ultimately be unrecoverable data loss
in the receiver.
7.7. Addressing NAKs
A PGM network element uses the *contained* source and group addresses to
find the source/group multicast routing information, 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.
[Page 36]
INTERNET-DRAFT PGM Specification 24 June 1999
7.8. Constrained RDATA Forwarding
Network elements must maintain repair state for each interface on which
a given NAK is received at least once. Network elements must then use
this list of interfaces to constrain the forwarding of the corresponding
RDATA packet only to those interfaces in the list. An RDATA packet
corresponds to a NAK if it matches NAK_TSI and NAK_SQN.
Network elements must maintain this repair state only until either the
corresponding RDATA is received and forwarded, or NAK_RDATA_IVL passes
after forwarding the most recent instance of a given NAK. Thereafter,
the corresponding repair state must be discarded.
Network elements should discard and not forward RDATA packets for which
they have no repair state. Note that the consequence of this procedure
is that, while it constrains repairs to the interested sub-set of the
network, loss of repair state precipitates further NAKs from neglected
receivers.
[Page 37]
INTERNET-DRAFT PGM Specification 24 June 1999
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 source and
destination network-layer addresses (NLAs) are specified in addition to
the format and contents of the transport layer header. Recall from Gen-
eral 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, Options, Checksum, Global Source ID (GSI), and TPDU Length are:
Data-Source Port:
A random port number generated by the source. This port number
must be unique within the source. Source Port together with Glo-
bal Source ID forms the TSI.
Data-Destination Port:
A globally well-known port number assigned to the given PGM appli-
cation.
Options:
This field encodes binary indications of the presence and signifi-
cance of any options. It also directly encodes some options.
bit 0 set => One or more Option Extensions are present
bit 1 set => One or more Options are network-significant
Note that this bit is clear when OPT_FRAGMENT and/or OPT_JOIN
are the only options present.
bit 6 set => Parity packet for a variable-size transmission group
(OPT_VAR_SIZE). This can only be present in parity packets,
i.e. when OPT_PARITY is present
bit 7 set => Packet is a parity packet (OPT_PARITY)
All the other options (option extensions) are encoded in exten-
sions to the PGM header.
[Page 38]
INTERNET-DRAFT PGM Specification 24 June 1999
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 (such as editing the Previous
Sequence Number field of OPT_DROP), it must either recompute the
checksum or clear it. The checksum is mandatory on data packets
(ODATA and RDATA) that do NOT also have OPT_DROP.
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.
TPDU Length:
The length in octets of the PGM packet including the size of the
header and any options.
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).
[Page 39]
INTERNET-DRAFT PGM Specification 24 June 1999
Address Family Indicators (AFIs) are as specified in [10].
[Page 40]
INTERNET-DRAFT PGM Specification 24 June 1999
8.1. Source Path Messages
SPMs are sent by a source to establish source path state in network ele-
ments and to provide transmit window state to receivers.
The source NLA of an SPM is the unicast NLA of the entity that ori-
ginates the SPM.
The destination NLA 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 | TPDU 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:
[Page 41]
INTERNET-DRAFT PGM Specification 24 June 1999
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).
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.
Option Extensions:
SPMs may bear OPT_JOIN.
[Page 42]
INTERNET-DRAFT PGM Specification 24 June 1999
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 source NLA of a data packet is the unicast NLA of the entity that
originates the data packet.
The destination NLA 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 | TPDU Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Trailing Edge Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Data Packet 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
[Page 43]
INTERNET-DRAFT PGM Specification 24 June 1999
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
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 Packet Sequence Number:
OD_SQN, RD_SQN
The sequence number originally assigned to the ODATA packet by the
source.
Option Extensions:
Data packets may bear OPT_FRAGMENT or OPT_DROP (not both)
Data:
Application data.
[Page 44]
INTERNET-DRAFT PGM Specification 24 June 1999
8.3. Negative Acknowledgements and Confirmations
NAK:
Negative Acknowledgements are sent by receivers to request the
repair of an ODATA packet detected to be missing from the expected
sequence.
N-NAK:
Null Negative Acknowledgements are sent by DLRs to provide flow
control feedback to the source of ODATA for which the DLR has pro-
vided the corresponding RDATA.
The source NLA of a NAK is the unicast NLA of the entity that originates
the NAK. The source NLA of NAK is rewritten by each PGM network element
with its own.
The destination NLA 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 destination NLA 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 destination NLA
of a NAK is rewritten by the PGM network element with the unicast NLA of
the original source or the unicast NLA of a DLR.
NCF:
NAK Confirmations are sent by network elements and sources to con-
firm the receipt of a NAK.
The source NLA of an NCF is the ODATA source's NLA, not the network
element's NLA as might be expected.
The destination NLA 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.
[Page 45]
INTERNET-DRAFT PGM Specification 24 June 1999
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 | TPDU 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
[Page 46]
INTERNET-DRAFT PGM Specification 24 June 1999
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.
Option Extensions:
NAKs may bear OPT_TIME
NCFs may bear OPT_REDIRECT
[Page 47]
INTERNET-DRAFT PGM Specification 24 June 1999
9. Options
PGM specifies several end-to-end options to address specific application
requirements. PGM specifies options to support fragmentation, late
joining, time-stamping, reception quality reports, sequence number dro-
pout, and redirection.
Options may be appended to PGM packet headers only by their original
transmitters. While they may be interpreted by network elements,
options are neither added nor removed by network elements.
NOTA BENE: PGM network elements and receivers must pass over
any options for which they do not have a definition and pro-
cess the packet as though it did not bear those undefined
options.
9.1. Option extension length - OPT_LENGTH
When option extensions are appended to the standard PGM header, the
extensions must be preceded by an option extension length field specify-
ing the total length of all option extensions.
In addition, the PGM packet length must be incremented by the total
length of all options, and 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
[Page 48]
INTERNET-DRAFT PGM Specification 24 June 1999
The total length in octets of all option extensions including
OPT_LENGTH.
9.2. Fragmentation Option - OPT_FRAGMENT
Fragmentation allows transport-layer entities at a source to break up
application protocol data units (APDUs) into multiple PGM data packets
(TPDUs) to conform with the MTU supported by the network layer. The
fragmentation option may be applied to ODATA and RDATA packets only.
This option is incompatible with the sequence number dropout
option since dropout is based upon application-layer informa-
tion available only at the beginning of the APDU. Trailing
fragments of such packets would not have sufficient informa-
tion to which to apply the drop out algorithm and so would be
pass through filters designed to discard the APDU as a whole.
Architecturally, the accumulation of TPDUs into APDUs is applied to
TPDUs that have already been received, duplicate eliminated, and con-
tiguously sequenced by the receiver. Thus APDUs may be reassembled
across increments of the transmit window.
9.2.1. OPT_FRAGMENT - Packet Extension Contents
OPT_FRAG_OFF the offset of the fragment from the beginning of the APDU
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.
[Page 49]
INTERNET-DRAFT PGM Specification 24 June 1999
9.2.4. OPT_FRAGMENT - Procedures - Network Elements
This option is not network-significant.
9.2.5. OPT_FRAGMENT - Packet Extension Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Option Length | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Offset |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type = 0x01
Option Length = 12 octets
Offset
The offset of the fragment from the beginning of the APDU
(OPT_FRAG_OFF).
Length
The total length of the original APDU (OPT_FRAG_LEN).
9.3. 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.3.1. OPT_JOIN - Packet Extensions Contents
OPT_JOIN_MIN the minimum sequence number for repair
[Page 50]
INTERNET-DRAFT PGM Specification 24 June 1999
9.3.2. OPT_JOIN - Procedures - Receivers
If a PGM packet (ODATA, RDATA, or SPM) bears OPT_JOIN, a receiver may
initialize the trailing edge of the receive window (RXW_TRAIL_INIT) to
the given Minimum Sequence Number and proceeds with normal data recep-
tion.
9.3.3. OPT_JOIN - Procedures - Network Elements
This option is not network-significant.
9.3.4. OPT_JOIN - Packet Extension Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Option Length | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Minimum Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type = 0x03
Option Length = 8 octets
Minimum Sequence Number
The minimum sequence number defining the initial trailing edge of
the receive window for a late joining receiver.
9.4. Time Stamp Option - OPT_TIME
Time stamps may be used in conjunction with NAKs to allow receivers to
specify the interval in which the requested RDATA is relevant to them.
That interval is interpreted by both network elements and sources to
determine whether to continue with or abandon a given repair.
9.4.1. OPT_TIME - Packet Extensions Contents
OPT_TIME_STAMP absolute time interval in milliseconds
9.4.2. OPT_TIME - Procedures - Receivers
Receivers may append the Time Stamp option to a NAK to indicate the
absolute interval from the time of transmitting the NAK during which the
receiver can usefully receive the corresponding RDATA.
[Page 51]
INTERNET-DRAFT PGM Specification 24 June 1999
9.4.3. OPT_TIME - Procedures - Network Elements
Network elements should use the time stamp of a NAK to age the associ-
ated repair state for the specified interval and discard it if the
corresponding RDATA has not already torn it down.
Network elements must eliminate a time-stamped NAK only if its time
stamp is smaller than the remaining time associated with the matching
repair state. Otherwise, such a NAK must be forwarded instead of elim-
inated, and its time stamp must be used to replace the time stamp of
existing repair state.
9.4.4. OPT_TIME - Procedures - Sources
A source should abandon any attempt to transmit RDATA in response to a
time stamped NAK if that repair cannot be completed within the specified
interval.
9.4.5. OPT_TIME - 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 | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Time Stamp |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type = 0x04
Option Length = 8 octets
Time Stamp
Absolute time interval in milliseconds (OPT_TIME_STAMP).
9.5. Reception Quality Option - OPT_RXQ
Reception quality reports may be used in conjunction with NAKs to allow
receivers to provide a reception quality metric to the source.
9.5.1. OPT_RXQ - Packet Extensions Contents
OPT_RXQ_METRIC A reception quality metric defined by a source's local
flow- and congestion-control procedures.
[Page 52]
INTERNET-DRAFT PGM Specification 24 June 1999
9.5.2. OPT_RXQ - Procedures - Receivers
Receivers may append the Reception Quality option to a NAK to indicate
the rate of packet loss detected at the receiver. Receivers must bias
the transmission of NAKs bearing OPT_RXQ by scaling NAK_BO_IVL with
respect to the reception quality metric. That is, as reception quality
deteriorates, NAK_BO_IVL should be reduced, and as reception quality
improves, NAK_BO_IVL should be increased.
The procedures for NAK suppression apply unchanged with the exception
that NAKs bearing OPT_RXQ are only suppressed by other matching NAKs
bearing OPT_RXQ and a worse reception quality metric.
9.5.3. OPT_RXQ - Procedures - Network Elements
Network elements must eliminate a NAK bearing OPT_RXQ only if its recep-
tion quality metric is larger (worse) than the reception quality metric
associated with the matching repair state. Otherwise, such a NAK must
be forwarded instead of eliminated, and its reception quality metric
must be used to replace the reception quality metric of existing repair
state.
9.5.4. OPT_RXQ - Procedures - Sources
Sources may interpret reception quality reports in a local manner to
adjust their transmission rate.
9.5.5. OPT_RXQ - 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 | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reception Quality Metric |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type = 0x05
Option Length = 8 octets
Reception Quality Metric
TBD
[Page 53]
INTERNET-DRAFT PGM Specification 24 June 1999
9.6. Sequence Number Dropout Option - OPT_DROP
Sequence number dropout may be used in conjunction with data packets to
allow sources and network elements to selectively eliminate PGM data
packets and convey the resulting sequence-number discontinuity to
receivers so that sequencing can be preserved across the dropout.
Sequence number dropout is incompatible with the fragmentation option.
This option is incompatible with fragmentation since dropout
is based upon application-layer information available only at
the beginning of the APDU. Trailing fragments of such packets
would not have sufficient information to which to apply the
drop out algorithm and so would be pass through filters
designed to discard the APDU as a whole.
9.6.1. OPT_DROP - Packet Extensions Contents
OPT_DROP_PREV the sequence number of the packet that should be regarded
by the receiver as the logical predecessor to the packet
bearing this option
9.6.2. OPT_DROP - Procedures - Sources
On a per-packet basis, a source may selectively permit intermediate
application-layer filters to be applied to a data packet by appending
OPT_DROP to ODATA/RDATA packets and setting the value of OPT_DROP_PREV
to OD_SQN/RD_SQN.
9.6.3. OPT_DROP - Procedures - Network Elements
Network elements may apply intermediate application-layer filters only
to ODATA/RDATA packets bearing OPT_DROP. If such a data packet passes
the filters, it must be forwarded out each interface with OPT_DROP_PREV
set to the value of the sequence number of the highest numbered data
packet within OD_TSI/RD_TSI that has already been forward on that inter-
face.
9.6.4. OPT_DROP - Procedures - Receivers
Receivers must do drop detection on packets bearing OPT_DROP by verify-
ing that they have also received the data packet numbered OPT_DROP_PREV
rather than checking for the numerical predecessor of OD_SQN/RD_SQN. If
a receiver has received OPT_DROP_PREV, then no drop has occurred. If a
receiver has not received OPT_DROP_PREV, then a receiver must NAK only
for OPT_DROP_PREV and no other intervening sequence numbers.
[Page 54]
INTERNET-DRAFT PGM Specification 24 June 1999
9.6.5. OPT_DROP - 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 | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Previous Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type = 0x06
Option Length = 8 octets
Previous Sequence Number
The sequence number of the packet that should be regarded by the
receiver as the logical predecessor to the packet bearing this
option (OPT_DROP_PREV).
9.7. Redirect Option - OPT_REDIRECT
Redirection may be used in conjunction with NCFs to allow a designated
local repairer (DLR) to respond to normal NCFs with a redirecting NCF
advertising its own address as an alternative to the original source.
Recipients of redirecting NCFs 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.7.1. OPT_REDIRECT - Packet Extensions Contents
OPT_REDIR_NLA the DLR's own unicast network-layer address to which
recipients of the redirecting NCF may direct subsequent
NAKs for the corresponding TSI.
9.7.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 sourced by neighbouring network elements
(or even by the source itself) by multicasting a repeat of that NCF and
OPT_REDIRECT providing its own network-layer address. if, however, this
NCF completes NAK transmission for this DLR, it must not send a
redirecting NCF.
[Page 55]
INTERNET-DRAFT PGM Specification 24 June 1999
Further, a 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 a 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 neighbour as usual.
NOTA BENE: In order to propagate on exactly the same distribu-
tion tree as ODATA, RDATA packets transmitted by DLRs and
other receivers must bear the ODATA source's NLA, not the
DLR's or the receiver's NLA as might be expected.
9.7.3. OPT_REDIRECT - Procedures - Network Elements
Upon receiving a redirecting NCF, 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 NCF
rather than to the PGM neighbour known via the SPMs. Note, however,
that a redirecting NCF 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.
If, however, a corresponding NCF is not received from the DLR within
NAK_RPT_IVL, the network element must discard the redirecting informa-
tion for the TSI and re-attempt to forward the NAK towards the PGM
upstream neighbour.
A NULL NAK is 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.7.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 NCF from a
DLR on the same IP subnet that the receiver resides on.
Upon receiving a redirecting NCF, receivers should record the redirect-
ing information for the TSI, and may redirect subsequent NAKs for the
same TSI to the network address provided in the redirecting NCF rather
[Page 56]
INTERNET-DRAFT PGM Specification 24 June 1999
than to the PGM neighbour for the corresponding ODATA for which the
receiver is requesting repair. Note, however, that a redirecting NCF is
NOT regarded as matching the NAK that provoked it, so it does not com-
plete the transmission of that NAK. Only a normal matching NCF can com-
plete the transmission of a NAK.
For subsequent NAKs, if the receiver has recorded redirection informa-
tion for the corresponding TSI, it may change the destination network
address of those NAKs and attempt to transmit them to the DLR. If, how-
ever, 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 neighbour for the original source
of the missing ODATA.
9.7.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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Option Length | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 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 NCF may direct subsequent NAKs.
[Page 57]
INTERNET-DRAFT PGM Specification 24 June 1999
10. Security Considerations
In addition to the usual problems of end-to-end authentication, PGM is
vulnerable to a number of security risks that are specific to the
mechanisms it uses to establish source path state, to establish repair
state, to forward NAKs, to identify DLRs, and to distribute repairs.
These mechanisms expose PGM network elements themselves to security
risks since network elements not only switch but also interpret SPMs,
NAKs, NCFs, and RDATA, all of which may legitimately be transmitted by
PGM sources, receivers, and DLRs. Short of full authentication of all
neighbouring sources, receivers, DLRs, and network elements, the proto-
col is not impervious to abuse.
So putting aside the problems of rogue PGM network elements for the
moment, there are enough potential security risks to network elements
associated with sources, receivers, and DLRs alone. These risks include
denial of service through the exhausting of both CPU bandwidth and
memory, as well as loss of (repair) data connectivity through the mud-
dling of repair state.
False SPMs may cause PGM network elements to mis-direct NAKs intended
for the legitimate source with the result that the requested RDATA would
not be forthcoming.
False NAKs may cause PGM network elements to establish spurious repair
state that will expire only upon time-out and could lead to memory
exhaustion in the meantime.
False NCFs may cause PGM network elements to suspend NAK forwarding
prematurely (or to mis-direct NAKs in the case of redirecting NCFs)
resulting eventually in loss of RDATA.
False RDATA may cause PGM network elements to tear down legitimate
repair state resulting eventually in loss of legitimate RDATA.
The development of precautions for network elements to protect them-
selves against incidental or unsophisticated versions of these attacks
is work in progress and includes:
Damping of jitter in the value of either the source NLA of SPMs or
the path NLA in SPMs. While the source NLA is expected to change
seldom, the path NLA is expected to change occasionally as a conse-
quence 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
[Page 58]
INTERNET-DRAFT PGM Specification 24 June 1999
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 NLA, and is PGM conversant.
[Page 59]
INTERNET-DRAFT PGM Specification 24 June 1999
11. Appendix A - Forward Error Correction
11.1. Introduction
The following procedures incorporate packet-level Reed Solomon Erasure
correcting techniques as described in [11] and [12] into PGM. This
approach to Forward Error Correction (FEC) is based upon the computation
of h parity packets from k data packets for a total of n packets such
that a receiver can reconstruct the k data packets out of any k of the n
packets. More specifically, it is characteristic of the parity packets
that any x of them can be used to reconstruct any x of the original k
data packets for x less than or equal to k. The original k data packets
are referred to as the Transmission Group, and the total n packets as
the FEC Block.
These procedures permit any combination of pro-active FEC or on-demand
FEC with conventional ARQ within a given TSI to provide any flavour of
layered or integrated FEC. Once provided by a source, the actual use of
FEC or ARQ for loss recovery in the session is entirely at the discre-
tion of the receivers. Note that receivers may still resort to selec-
tive NAKs even when parity is available, and sources must still provide
selective retransmissions in response. The two approaches can be used
by the same or different receivers in a single transport session without
conflict.
Pro-active FEC refers to the technique of computing parity packets at
transmission time and transmitting them as a matter of course following
the data packets. Pro-active FEC is recommended for providing loss
recovery over simplex or asymmetric multicast channels over which
returning repair requests is either impossible or costly. It provides
increased reliability at the expense of bandwidth.
On-demand FEC refers to the technique of computing parity packets at
repair time and transmitting them only upon demand (i.e., receiver-based
loss detection and repair request). On-demand FEC is recommended for
providing loss recovery of uncorrelated loss in very large receiver
populations in which the probability of any single packet being lost is
substantial. It provides equivalent reliability to selective NAKs (ARQ)
at the expense of no more and typically less bandwidth.
Selective NAKs are NAKs that request the retransmission of specific
packets by sequence number corresponding to the sequence number of any
data packets detected to be missing from the expected sequence (conven-
tional ARQ). Selective NAKs are recommended for recovering losses
occurring in trailing partial transmission groups.
Parity NAKs are NAKs that request the transmission of a specific number
of parity packets by count corresponding to the count of the number of
[Page 60]
INTERNET-DRAFT PGM Specification 24 June 1999
data packets detected to be missing from a group of k data packets (on-
demand FEC).
The objective of these procedures is to incorporate these FEC techniques
into PGM so that:
sources may provide parity packets either pro-actively or on-demand,
interchangeably within the same TSI,
receivers may use either selective or parity NAKs interchangeably
within the same TSI,
network elements may maintain repair state based on either selective
or parity NAKs in the same data structure, altering only search,
RDATA constraint, and deletion algorithms in either case,
and only OPTION additions to the basic packet formats are required.
11.2. Overview
Advertising FEC parameters in the transport session
Sources add OPT_PARITY_PRM to SPMs to provide session-specific parame-
ters such as the number of packets (TGSIZE == k) in a transmission
group. This option lets receivers know how many packets in a transmis-
sion group, and it lets network elements sort repair state by transmis-
sion group number. This option includes an indication of whether pro-
active and/or on-demand parity is available from the source.
Distinguishing parity packets from data packets
Sources send pro-active parity packets as ODATA and on-demand parity
packets as RDATA. A source must add OPT_PARITY to the ODATA/RDATA
packet header of parity packets to permit network elements and receivers
to distinguish them from data packets.
Data and parity packet numbering
Parity packets must be calculated over a fixed number k of data packets
known as the Transmission Group. Grouping of packets into transmission
groups effectively partitions a packet sequence number into a high-order
portion (TG_SQN) specifying the transmission group (TG), and a low-order
portion (PKT_SQN) specifying the packet number (PKT-NUM in the range 0
through k-1) within that group. So 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. So
log2(TGSIZE) is the size in bits of PKT_SQN.
[Page 61]
INTERNET-DRAFT PGM Specification 24 June 1999
This mapping does not diminish the effective sequence number space since
parity packets are marked with OPT_PARITY that allows the sequence space
(PKT_SQN) to be reused to number the h parity packets for as long as h
is not greater than k.
In case 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.
Note that parity NAKs (and consequently their corresponding parity NCFs)
must also be distinguished by the addition of OPT_PARITY, and that in
these packets, PKT_SQN contains PKT-CNT, the number of missing packets,
rather than PKT-NUM, the number of a specific missing packet. More on
all this later.
Variable TPDU length
If a non constant TPDU 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 padding with zeros the original packets up to
the size of the larger. Note that original data packets are transmitted
without padding. Receivers that use a combination of original packets
and FEC packets to rebuild missing packets must pad original packets in
the same way as the sender does before feeding the original packets to
the FEC decoder. The decoder produces original packet padded with zeros
up to the size of the largest original packet in the group. In order to
eliminate the padding, the original size of the packet must be known,
this is accomplished as follows:
The sender, along with the packet payloads, must also encode the TPDU
lengths and append the 2-byte encoded length to the padded FEC pack-
ets.
Receivers which feed the FEC decoder with original packets must also
append their TPDU length to the packets after padding them and before
passing them to the decoder.
This way the decoder produces padded original packets with their origi-
nal TPDU length appended. Receivers use this length to get rid of the
padding.
A sender that transmits variable-size packets must take into account the
fact that FEC packet will have a size equal to the maximum size of the
original packets plus the size of the length field (2 bytes).
[Page 62]
INTERNET-DRAFT PGM Specification 24 June 1999
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 option
OPT_VAR_SIZE in parity packets allows receivers to distinguish between
variable-size transmission groups and fixed-size ones, and behave
accordingly.
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 PGM header
OPT_VAR_SIZE can 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 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 k parity
packets to which the parity packet belongs when more than
k parity packets are provided by the source
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
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
[Page 63]
INTERNET-DRAFT PGM Specification 24 June 1999
missing data packets for which parity packets were
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. If a source elects to provide pro-
active 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 transmis-
sion 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.
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 pro-
active parity packets, possibly scheduled, before starting the transmis-
sion 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. Previously
transmitted pro-active parity packets cannot be reused as on-demand par-
ity packets, these must be computed with new, previously unused,
indexes.
In either case, the source must be prepared to also respond to selective
NAKs in the usual way.
[Page 64]
INTERNET-DRAFT PGM Specification 24 June 1999
In the absence of data to transmit, a source should pad out the
transmission group with padded packets before calculating and providing
parity packets either pro-actively or on demand.
A source may consolidate 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 relatively to a variable-size
transmission group, it must compute parity packets padding the original
packets, must append the encoded TPU lengths and add the OPT_VAR_SIZE
option as specified in the overview description.
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 may 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. Parity pack-
ets 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.
[Page 65]
INTERNET-DRAFT PGM Specification 24 June 1999
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 transmis-
sion 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 popu-
lation.
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 should resort
to selective NAKs for any missing packets in that trailing transmission
group.
When a receiver handles parity packets belonging to a variable-size FEC
block (detected from the presence of the OPT_VAR_SIZE option in the par-
ity packets), it must decode them as specified in the overview descrip-
tion and use the decoded TPDU length to get rid of the padding in the
decoded packet.
11.6. Procedures - Network Elements
Pro-active parity packets (ODATA with OPT_PARITY) are switched by net-
work elements without transport-layer intervention.
On-demand parity packets (RDATA with OPT_PARITY) necessitate modified
request, confirmation and repair constraint procedures for network ele-
ments. 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
[Page 66]
INTERNET-DRAFT PGM Specification 24 June 1999
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 par-
ity 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 for each by one. 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
[Page 67]
INTERNET-DRAFT PGM Specification 24 June 1999
that NNAKs are eliminated only if existing NAK state has a NAK_PKT_CNT
greater than NNAK_PKT_CNT.
11.7. Procedures - DLRs
A DLR with the ability to provide FEC repairs must indicate this by set-
ting the OPT_PARITY bit in the redirecting NCF. It must then process any
redirected FEC NAKs in the usual way.
[Page 68]
INTERNET-DRAFT PGM Specification 24 June 1999
11.8. Packet Formats
11.8.1. OPT_PARITY_PRM - Packet Extension Format
OPT_PARITY_PRM may be appended only to SPMs.
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 | 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.
[Page 69]
INTERNET-DRAFT PGM Specification 24 June 1999
11.8.2. OPT_PARITY_GRP - Packet Extension Format
OPT_PARITY_GRP may be appended only to parity packets.
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 | Parity Group Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type = 0x09
Option Length = 4 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.
[Page 70]
INTERNET-DRAFT PGM Specification 24 June 1999
12. Appendix B - Congestion Avoidance
A source should 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]. This is
work in progress and will be expanded in a later version of this docu-
ment.
[Page 71]
INTERNET-DRAFT PGM Specification 24 June 1999
13. Appendix C - Flow Control
A degree of flow control native to PGM itself is provided through the
exchange of elective, periodic state notifications between sources
(Transmit State Notifications - TSNs) and receivers (Receive State
Notifications - RSNs). The goal of the flow control strategies in PGM
is to conservatively adapt a source's transmit rate so as to minimize
NAKs due to receiver overrun and to do so with as simple and efficient
an exchange of protocol packets as possible. These strategies are
intended to augment, not substitute for, source-based adaptive stra-
tegies for rate-limiting transmissions based solely on the frequency of
NAKs.
Since PGM has no conference control mechanisms, these mechanisms simply
act to modify a source's transmit rate to suit the slowest receiver the
source is willing to accommodate. The use and frequency of TSNs and
RSNs is left to the discretion of the implementation.
TSNs enable a source to adapt its transmit rate as network and receiver
resources permit. A source may distinguish congestion from flow control
by noting that in the absence of RSNs, it is likely that most NAKs the
source may see are the result of congestion and not end-to-end flow con-
trol problems. So a source may also reduce its transmit rate simply in
response to the pattern of NAKs it receives.
These mechanisms are entirely elective and not meant as a replacement
for reservation protocols or other out-of-band resource and conference
management strategies. They are intended simply to provide a workable
strategy in the absence of anything more sophisticated. PGM's reliable
data transfer service is in no way dependent upon the use of TSNs and
RSNs.
13.1. Architectural Description
To provide an optional mechanism for flow, PGM specifies packet formats
and procedures for sources and receivers to exchange resource state
notifications.
13.1.1. Source Functions
A source may periodically multicast TSNs to the group to advertise its
transmit window and its minimum and current transmit rates.
In response to corresponding RSNs, a source must reduce its transmit
rate to at most the least rate specified in any RSN, and reflect this
reduced current rate in subsequent TSNs.
In the absence of corresponding RSNs, a source may conservatively
[Page 72]
INTERNET-DRAFT PGM Specification 24 June 1999
increase its transmit rate, and reflect this increased current rate in
subsequent TSNs.
To find the local maximum current transmit rate, a source may continue
to increase its current transmit rate until it receives RSNs (or NAKs)
in response, and then back off appropriately.
13.1.2. Receiver Functions
A receiver unicasts an RSN to a source in response to a TSN only if the
transmit rate advertised in the TSN exceeds the receiver's capacity. To
prevent RSN implosion, receivers must observe a random back off over an
interval three times the TSN period, and monitor TSNs in the meantime
for a reduction in the current transmit rate.
13.1.3. Network Element Functions
Network elements forward TSNs, and RSNs without intervention.
13.2. Terms and Concepts
For a given transport session identified by a TSI, a source maintains:
TXW_MIN_RTE a fixed minimum transmit rate in kBps, the minimum the
transmitter will consider maintaining, equal to or less
than TXW_MAX_RTE
The reduction of TXW_MAX_RTE to TXW_MIN_RTE is negotiated through
exchanges of TSNs and RSNs.
For a given transport session identified by a TSI, a receiver maintains:
RXW_MAX_RTE a fixed maximum reception rate in kBps, the maximum the
receiver will consider maintaining
The reduction of the current transmit rate (advertised in TSNs) to
RXW_MAX_RTE is negotiated through exchanges of TSNs and RSNs.
13.3. Packet Contents
This section just provides enough short-hand to make the Procedures
intelligible. For the full details of packet contents, please refer to
Packet Formats below.
13.3.1. Transmit State Notification (TSN)
TSNs are formed by adding OPT_TSN to SPMs and contain:
[Page 73]
INTERNET-DRAFT PGM Specification 24 June 1999
TSN_TSI (a.k.a. SPM_TSI) the source-assigned TSI for which RSNs
are solicited
TSN_SQN (a.k.a. SPM_SQN) a sequence number assigned sequentially
by the source in unit increments and scoped by TSN_TSI
NOTA BENE: this is an entirely separate sequence than is used
to number ODATA and RDATA.
TSN_TRAIL (a.k.a. SPM_TRAIL) the source's TXW_TRAIL
TSN_LEAD (a.k.a. SPM_LEAD) the source's TXW_LEAD
TSN_MIN_RTE the source's TXW_MIN_RTE
TSN_MAX_RTE the source's TXW_MAX_RTE
13.3.2. Receive State Notification (RSN)
RSNs are unicast to the source and contain:
RSN_TSI TSN_TSI from the TSN to which this is a response
RSN_SQN TSN_SQN from the TSN to which this is a response
RSN_TRAIL TSN_TRAIL from the TSN to which this is a response
RSN_MAX_RTE the receiver's RXW_MAX_RTE
13.4. Procedures - Sources
13.4.1. Data Transmission Initialization
Sources must sequence TSNs by assigning each a TSN_SQN using a number
sequence separate from that used to number data packets. In addition,
sources associate each TSN with a specific instance of the transmit win-
dow by setting TSN_TRAIL to TXW_TRAIL.
A source may precede initial data transmission to a transport session by
sending TSNs at a rate of TSN_IDL_RTE for an interval of TSN_IDL_IVL.
TSNs are used by the source in this instance simply to provoke RSNs from
any receivers that may protest the advertised TSN_MAX_RTE. A source may
use this procedure to find the largest acceptable initial values for
TXW_MAX_RTE before initiating data transmission.
In the ordinary course of data transmission, a source may periodically
transmit TSNs and adjust the current transmit rate to establish the
optimum rate for the current population of tuned-in receivers.
[Page 74]
INTERNET-DRAFT PGM Specification 24 June 1999
Specifically, a source may increase the values in the TSN without
increasing them in fact until it provokes RSNs. It should then use the
values in the RSNs to back off to the highest acceptable values for
actual use.
Note, then, that a source may advertise higher values for TSN_MAX_RTE in
its TSNs than it actually uses, but it must never actually use higher
values for TXW_MAX_RTE than it advertises in its TSNs.
13.4.2. Transmit Resource Management
An RSN corresponds to a TSN if RSN_TSI matches TSN_TSI, RSN_SQN matches
TSN_SQN, and RSN_TRAIL matches TSN_TRAIL. That is, an RSN corresponds
to a TSN if it bears the same transport session, sequence, and transmit
window identifiers as the TSN.
Sources should respond to RSNs that correspond to the current TSN by
reducing TXW_MAX_RTE to the minimum values heard in any such RSN as long
as these values are no lower than TXW_MIN_RTE.
13.5. Procedures - Receivers
13.5.1. Data Reception Initialization
TSNs must be sequenced by receivers based on a combination of TSN_SQN
(which numbers TSNs separately from data packets) and TSN_TRAIL which
relates the TSN to a specific transmit window. TSNs bearing the same
TSN_TRAIL may be ordered relative to one another using TSN_SQN. The
highest numbered such TSN should be used to maintain the receiver's
notion of the transmit window and the current and maximum transmit
rates. Ordering of TSNs is particularly important for TSNs in which
transmit rates are increasing or decreasing.
For a given transport session identified by TSI, a receiver may precede
initial data reception by first receiving and accepting the values for
TXW_MAX_RTE in a matching TSN. Accepting this value implies that the
receiver is capable of receiving data at the rate of TXW_MAX_RTE.
If a receiver accepts the advertised value for TXW_MAX_RTE in a matching
TSN, it may initiate data reception in the transmit window provided by
the TSN.
If the TSN bears OPT_JOIN, the receiver initializes the trailing edge of
the receive window to TXW_TRAIL and proceeds with normal data reception.
If the TSN does not bear OPT_JOIN, the receiver may initiate data recep-
tion beginning only with the first ODATA_SQN it receives within the
advertised transmit window. This sequence number temporarily defines
[Page 75]
INTERNET-DRAFT PGM Specification 24 June 1999
the trailing edge of the transmit window from the receivers perspective.
That is, it is assigned to RXW_TRAIL_INIT within the receiver, and until
trailing edge sequence number advertised in subsequent packets (TSNs or
ODATA or RDATA or SPMs) increments through RXW_TRAIL_INIT, the receiver
must only request repairs for sequence numbers subsequent to
RXW_TRAIL_INIT. Thereafter, it may request repairs anywhere in the
transmit window. This temporary restriction on repair requests prevents
receivers from requesting a potentially large amount of history when
they first begin to receive a given PGM transport session.
13.5.2. Receive Resource Management
>From a receiver's perspective, an acceptable TSN is one in which
TSN_MIN_RTE is equal to or less than RXW_MAX_RTE. The current value of
TSN_MAX_RTE may or may not be within the receiver's capacity.
If a receiver receives an unacceptable TSN, the receiver must neither
initiate nor continue data reception for the given transport session.
In addition, it must not respond to the TSN with an RSN, although it may
continue to receive and inspect TSNs for an acceptable one.
If a receiver receives an acceptable TSN, but the advertised values of
TSN_MAX_RTE exceed RXW_MAX_RTE, the receiver should respond with a
corresponding RSN advertising the maximum value RSN_MAX_RTE with which
it can operate. The receiver may simultaneously initiate or continue
data reception, and it should continue to respond to subsequent TSNs
with this RSN until it receives a TSN advertising a value of TSN_MAX_RTE
with which it can operate.
[Page 76]
INTERNET-DRAFT PGM Specification 24 June 1999
13.6. Packet Formats
13.6.1. OPT_TSN - Packet Extension Format
The source NLA of a TSN is the unicast address of the entity that
originates the TSN.
The destination NLA of a TSN 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Option Length | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Minimum Transmit Rate |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Maximum Transmit Rate |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type = 0x0A
Option Length = 12 octets
Minimum Transmit Rate (TSN_MIN_RTE)
The minimum rate of transmission required for receivers to parti-
cipate in the group (TXW_MIN_RTE).
Transmit Rate (TSN_MAX_RTE)
The current rate of transmission required by receivers to partici-
pate in the group (TXW_MAX_RTE).
[Page 77]
INTERNET-DRAFT PGM Specification 24 June 1999
13.6.2. RSN - Receive State Notification
The source NLA of an RSN is the unicast address of the entity that
originates the RSN.
The destination NLA of an RSN is the unicast address of the source of
the corresponding TSN.
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 | TPDU Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RSN's Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Trailing Edge Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Receive Rate |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Source Port:
RSN_SPORT
Data-Destination Port
Destination Port:
RSN_DPORT
Data-Source Port, together with Global Source ID forms RSN_TSI
Type:
RSN_TYPE = 0x0D
Options
RSNs may bear only OPT_JOIN.
RSN's Sequence Number (RSN_SQN)
[Page 78]
INTERNET-DRAFT PGM Specification 24 June 1999
TSN_SQN from the corresponding TSN.
Trailing Edge Sequence Number (RSN_TRAIL)
TSN_TRAIL from the corresponding TSN.
Transmit Rate (RSN_MAX_RTE)
The maximum rate of transmission the receiver can sustain
(RXW_MAX_RTE).
[Page 79]
INTERNET-DRAFT PGM Specification 24 June 1999
14. Appendix D - SPM Requests
14.1. Introduction
SPM Requests (SPMRs) may be used to solicit an SPM from a source in a
non-implosive way. The typical application is for late-joining
receivers to solicit SPMs directly from a source in order to be able to
NAK for missing packets without having to wait for a regularly scheduled
SPM from that source.
14.2. Overview
Allowing for SPMR implosion protection procedures, a receiver may uni-
cast an SPMR to a source to solicit the most current session, window,
and path state from that source any time after the receiver has joined
the group. A receiver may learn the TSI and source to which to direct
the SPMR from any other PGM packet it receives in the group, or by any
other means such as from local configuration or directory services. The
receiver must use the usual SPM procedures to glean the unicast address
to which it should direct its NAKs from the solicited SPM.
14.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.
14.3.1. SPM Requests
SPMRs are transmitted by receivers to solicit SPMs from a source.
SPMs are unicast to a source and contain:
SPMR_TSI the source-assigned TSI for the session to which the SPMR
corresponds
14.4. Procedures - Sources
A source must respond immediately to an SPMR with the corresponding SPM
rate limited to once per IHB_MIN per TSI. The corresponding SPM matches
SPM_TSI to SPMR_TSI and SPM_DPORT to SPMR_DPORT.
14.5. Procedures - Receivers
To moderate the potentially implosive behaviour of SPMRs at least on a
densely populated subnet, receivers must use the following back-off and
suppression procedure based on multicasting the SPMR with a TTL of 1
ahead of and in addition to unicasting the SPMR to the source. The role
[Page 80]
INTERNET-DRAFT PGM Specification 24 June 1999
of the multicast SPMR is to suppress the transmission of identical SPMRs
from the subnet.
More specifically, before unicasting a given SPMR, receivers must choose
a random delay on SPMR_BO_IVL (~250 msecs) during which they listen for
a multicast of an identical SPMR. If a receiver does not see a matching
multicast SPMR within its chosen random interval, it must first multi-
cast its own SPMR to the group with a TTL of 1 before then unicasting
its own SPMR to the source. If a receiver does see a matching multicast
SPMR within its chosen random interval, it must refrain from unicasting
its SPMR and wait instead for the corresponding SPM.
In addition, receipt of the corresponding SPM within this random inter-
val should cancel transmission of an SPMR.
In either case, the receiver must wait at least SPMR_SPM_IVL before
attempting to repeat the SPMR by choosing another delay on SPMR_BO_IVL
and repeating the procedure above.
The corresponding SPMR matches SPMR_TSI to SPMR_TSI and SPMR_DPORT to
SPMR_DPORT. The corresponding SPM matches SPM_TSI to SPMR_TSI and
SPM_DPORT to SPMR_DPORT.
14.6. Procedures - Network Elements
There are no SPMR procedures for network elements.
[Page 81]
INTERNET-DRAFT PGM Specification 24 June 1999
14.7. SPM Requests
SPMR:
SPM Requests are sent by receivers to request the immediate
transmission of an SPM for the given TSI from a source.
The source NLA of an SPMR is the unicast NLA of the entity that ori-
ginates the SPMR.
The destination NLA of an SPMR is the unicast NLA of the source from
which the corresponding SPM is requested.
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 | TPDU Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Extensions when present ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- ...
Source Port:
SPMR_SPORT
Data-Destination Port
Destination Port:
SPMR_DPORT
Data-Source Port, together with Global Source ID forms SPMR_TSI
Type:
SPMR_TYPE = 0x0C
Global Source ID:
SPMR_GSI
[Page 82]
INTERNET-DRAFT PGM Specification 24 June 1999
Together with Source Port forms
SPMR_TSI
[Page 83]
INTERNET-DRAFT PGM Specification 24 June 1999
15. Appendix E - Poll Mechanism
15.1. Introduction
These procedures provide PGM network elements and sources with the abil-
ity to poll their downstream PGM neighbours to solicit replies in an
implosion-controlled way.
Both general polls and specific polls are possible. The former provide a
PGM (parent) node with a way to check if there are any PGM (children)
nodes connected to it, both network elements and receivers, and to esti-
mate their number. The latter can be used by PGM parent nodes to search
for nodes with specific properties among its PGM children. An example of
application for this is DLR discovery.
Polling is implemented using two additional PGM packets:
POLL a Poll Request that PGM parent nodes multicast to the group to per-
form the poll. Similarly to NCFs, POLL packets stop at the first
PGM node they reach, as they are not forwarded by PGM network ele-
ments.
POLR a Poll Response that PGM children nodes (either network elements or
receivers) use to reply to a Poll Request by addressing it to the
NLA of the interface from which the triggering POLL was sent.
The polling mechanism dictates that PGM children nodes that receive a
POLL packet reply to it only if certain conditions are satisfied and
ignore the POLL otherwise. Two types of condition are possible: a random
condition that defines a probability of replying for the polled child,
and a deterministic condition. Both the random condition and the deter-
ministic condition are controlled by the polling PGM parent node by
specifying the probability of replying and defining the deterministic
condition(s) respectively. Random-only poll, deterministic-only poll or
a combination of the two are possible.
The random condition in polls allows the prevention of implosion of
replies by controlling their number. Given a probability of replying P
and assuming that each receiver makes an independent decision, the
number of expected replies to a poll is P*N where N is the number of PGM
children relative to the polling PGM parent. The polling node can con-
trol the number of expected replies by specifying P in the POLL packet.
15.2. 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.
[Page 84]
INTERNET-DRAFT PGM Specification 24 June 1999
15.2.1. POLL (Poll Request)
POLL_SQN a sequence number assigned sequentially by the polling
parent in unit increments and scoped by POLL_PATH and the
TSI of the session.
POLL_PATH the network-layer address (NLA) of the interface on the
PGM network element or source on which the POLL is
transmitted
POLL_BO_IVL the back-off interval that must be used to compute the
random back-off time to wait before sending the response
to a poll.
POLL_RAND a random string used to implement the randomness in
replying
POLL_MASK a bit-mask used to determine the probability of random
replies
POLL_S_TYPE the sub-type of the poll request
Poll request may also contain options which specify deterministic condi-
tions for the reply. No options are currently defined.
15.2.2. POLR (Poll Response)
POLR_SQN POLL_SQN of the poll request of which this is a reply
Poll response may also contain options. No options are currently
defined.
15.3. Procedures - General
Although the poll mechanism can be used for both general polls and
specific polls, no specific polls are currently defined. This section
hence will only specify general polls and extension mechanisms to incor-
porate specific polls.
15.3.1. General Polls
General Polls can be used to check for and count PGM children that are 1
PGM hop downstream of an interface of a given node. They have
POLL_S_TYPE equal to PGM_POLL_GENERAL. PGM children that receive a gen-
eral poll decide whether to reply to it only based on the random condi-
tion present in the POLL.
To prevent response implosion, PGM parents that initiate a general poll
[Page 85]
INTERNET-DRAFT PGM Specification 24 June 1999
should establish the probability of replying to the poll, P, so that the
expected number of replies is contained. The expected number of replies
is N * P, where N is the number of children. To be able to compute this
number, PGM parents should already have a rough estimate of the number
of children. If they do not have a recent estimate of this number, they
should send the first poll with a very low probability of replying and
increase it in subsequent polls in order to get the desired number of
replies.
PGM children observe a random back-off in replying to a poll. This
spreads out the replies in time and allows a PGM parent to abort the
poll if too many replies are being received. To abort an ongoing poll a
PGM parent must initiate another poll with different POLL_SQN. PGM
children that receive a POLL must cancel any pending reply for POLLs
with POLL_SQN different from the one of the last POLL received.
For a given poll with probability of replying P, a PGM parent estimates
the number of children as M / P, where M is the number of responses
received. PGM parents should keep polling periodically and use some
average of the result of recent polls as their estimate for the number
of children.
15.3.2. Specific Polls
Specific polls provide a way to search for PGM children that comply to
specific requisites. As an example specific poll could be used to search
for down-stream DLRs. A specific poll is characterized by a POLL_S_TYPE
different from PGM_POLL_GENERAL. PGM children decide whether to reply
to a specific poll or not based on the POLL_S_TYPE, on the random condi-
tion and on options possibly present in the POLL. The way options should
be interpreted is defined by POLL_S_TYPE. The random condition must be
interpreted as an additional condition to be satisfied. To disable the
random condition PGM parents must specify a probability of replying P
equal to 1.
PGM children must ignore a POLL packet if they do not understand
POLL_S_TYPE. Some specific POLL_S_TYPE may also require that the chil-
dren ignore a POLL if they do not fully understand all the PGM options
present in the packet.
15.4. Procedures - PGM Parents (Sources or Network Elements)
A PGM parent (source or network element), that wants to poll the first
PGM-hop children connected to one of its outgoing interfaces must send a
POLL packet on that interface with:
POLL_SQN equal to POLL_SQN of the last POLL sent incremented by
one
[Page 86]
INTERNET-DRAFT PGM Specification 24 June 1999
POLL_PATH set to the NLA of the outgoing interface
POLL_BO_IVL set to the wanted reply back-off interval. As far as the
choice of this is concerned, using NAK_BO_IVL is usually
a conservative option, however a smaller value can be
used, if the number of expected replies can be determined
with a good confidence or if a conservatively low proba-
bility of reply (P) is being used (see POLL_MASK next).
When the number of expected replies is unknown, a large
POLL_BO_IVL should be used, so that the poll can be
effectively aborted if the number of replies being
received is too large.
POLL_RAND should be a random string re-computed each time a new
poll is sent on a given interface
POLL_MASK determines the probability of replying, P, according to
the relationship P = 1 / ( 2 ^ B ), where B is the number
of bit set in POLL_MASK. If this is a deterministic
poll, B must be 0, i.e. POLL_MASK must be a all-zeroes
bit-mask.
POLL_S_TYPE the type of the poll. For general poll use
PGM_POLL_GENERAL
NOTA BENE: POLLs transmitted by network elements must bear the
ODATA source's NLA, not the network element's NLA. POLLs must
also be transmitted with the IP Router Alert Option [6], to be
allow PGM network element to intercept them.
A PGM parent that has started a poll by sending a POLL packet should
wait at least POLL_BO_IVL before starting another poll. During this
interval it should collect all the valid response (the one with POLR_SQN
equal to POLL_SQN of the outstanding POLL) and process them at the end
of the collection interval.
A PGM parent should observe the rules mentioned in the description of
general procedures, to prevent implosion of response. These rules should
in general be observed both for generic polls and specific polls. The
latter however can be performed using deterministic poll (with no implo-
sion prevention) if the expected number of replies is known to be small.
A PGM parent that has started a poll should monitor the number of
replies. If this become too large, the PGM parent should abort the poll
by immediately starting a new poll (different POLL_SQN) and specifying a
very low probability of replying.
[Page 87]
INTERNET-DRAFT PGM Specification 24 June 1999
15.5. Procedures - PGM Children (Receivers or Network Elements)
PGM receivers and network elements must compute a 32-bit random node
identifier (RAND_NODE_ID) at startup time. When a PGM child (receiver
or network element) receives a POLL it must use its RAND_NODE_ID to
match POLL_RAND of incoming POLLs. The match is limited to the bits
specified by POLL_MASK. If the incoming POLL contain a POLL_MASK made
of all zeroes, the match is successful despite the content of POLL_RAND
(deterministic reply). If the match fails, then the receiver or network
element must discard the POLL without any further action, otherwise it
must check the field POLL_S_TYPE and any PGM option included in the POLL
to determine whether it should reply to the poll.
If POLL_S_TYPE is equal to PGM_POLL_GENERAL, the PGM child must schedule
a reply to the POLL despite the presence of PGM options on the POLL
packet.
If POLL_S_TYPE is different from PGM_POLL_GENERAL, the decision on
whether a reply should be scheduled depends on the actual type and on
the options possibly present in the POLL.
If POLL_S_TYPE is unknown to the recipient of the POLL, it must not
reply and ignore the poll. Currently the only POLL_S_TYPE defined is
PGM_POLL_GENERAL.
If a PGM receiver or network element has decided to reply to a POLL, it
must schedule the transmission of a single POLR at a random time in the
future. The random delay is chosen in the interval [0, POLL_BO_IVL].
POLL_BO_IVL is the one contained in the POLL received. When this timer
expires, it must send a POLR using POLL_PATH of the received POLL as
destination address. POLR_SQN must be equal to POLL_SQN. The POLR may
contain PGM options according to the semantic of POLL_S_TYPE or the
semantic of PGM options possibly present in the POLL. If POLL_S_TYPE is
PGM_POLL_GENERAL no option is required.
A PGM receiver or network element must cancel any pending transmission
of POLRs if a new POLL is received with POLL_SQN different from POLR_SQN
of the poll that scheduled POLRs.
15.6. Constant Definition
PGM_POLL_GENERAL is equal to 0x0000. This is the only POLL_S_TYPE value
currently defined.
15.7. Packet Formats
The packet formats described in this section are transport-layer headers
that must immediately follow the network-layer header in the packet.
[Page 88]
INTERNET-DRAFT PGM Specification 24 June 1999
The descriptions of Data-Source Port, Data-Destination Port, Options,
Checksum, Global Source ID (GSI), and TPDU Length are those provided in
Section 8.
15.7.1. Poll Request
POLL are sent by PGM parents (sources or network elements) to initiate a
poll among their first PGM-hop children.
POLLs are sent to the ODATA multicast group. The source NLA of a POLL is
the ODATA source's NLA. POLL must be transmitted with the IP Router
Alert Option.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Port | Destination Port |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Options | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Global Source ID ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... Global Source ID | TPDU Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| POLL's Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NLA AFI | reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Path NLA ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...-+-+
| POLL's Back-off Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Random String |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Matching Bit-Mask |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| POLL's Sub-type | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Extensions when present ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- ... -+-+-+-+-+-+-+-+-+-+-+-+-+-+
Source Port:
POLL_SPORT
Data-Source Port, together with POLL_GSI forms POLL_TSI
[Page 89]
INTERNET-DRAFT PGM Specification 24 June 1999
Destination Port:
POLL_DPORT
Data-Destination Port
Type:
POLL_TYPE = 0x01
Global Source ID:
POLL_GSI
Together with POLL_SPORT forms POLL_TSI
POLL's Sequence Number
POLL_SQN
The sequence number assigned to the POLL by the originator.
Path NLA:
POLL_PATH
The NLA of the interface on the source or network element on which
this POLL was forwarded.
POLL's Back-off Interval
POLL_BO_IVL
The back-off interval used to compute a random back-off for the
reply.
Random String
POLL_RAND
A random string used to implement the random condition in reply-
ing.
Matching Bit-Mask
POLL_MASK
A bit-mask used to determine the probability of random replies.
[Page 90]
INTERNET-DRAFT PGM Specification 24 June 1999
POLL's Sub-type
POLL_S_TYPE The sub-type of the poll request.
Option Extensions:
No option is currently defined.
15.7.2. Poll Response
POLR are sent by PGM children (receivers or network elements) to reply
to a POLL.
The source NLA of a POLR is the unicast NLA of the entity that ori-
ginates the POLR. The destination NLA of a POLR is initialized by the
originator of the POLL to the unicast NLA of the upstream PGM element
(source or network element) known from the POLL that triggered the POLR.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Port | Destination Port |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Options | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Global Source ID ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... Global Source ID | TPDU Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| POLR's Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Extensions when present ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- ... -+-+-+-+-+-+-+-+-+-+-+-+-+-+
Source Port:
POLR_SPORT
Data-Destination Port
Destination Port:
POLR_DPORT
Data-Source Port, together with Global Source ID forms POLR_TSI
Type:
[Page 91]
INTERNET-DRAFT PGM Specification 24 June 1999
POLR_TYPE = 0x02
Global Source ID:
POLR_GSI
Together with POLR_DPORT forms POLR_TSI
POLR's Sequence Number
POLR_SQN
The sequence number (POLL_SQN) of the POLL packet of which this is
a reply.
Option Extensions:
No option is currently defined.
[Page 92]
INTERNET-DRAFT PGM Specification 24 June 1999
16. Appendix F - Implosion Prevention
16.1. Introduction
These procedures are intended to prevent NAK implosion and to limit its
extent in case of the loss of all or part of the suppressing multicast
distribution tree. They also provide a means to adaptively tune the NAK
back-off interval, NAK_BO_IVL.
The PGM virtual topology is established and refreshed by SPMs. Between
one SPM and the next, PGM nodes can have an out-of-date view of the PGM
topology due to multicast routing changes, flapping, or a link/router
failure. If any of the above happens relative to a PGM parent node, a
potential NAK implosion problem arises because the parent node is unable
to suppress the generation of duplicate NAKs as it cannot reach its
children using NCFs. The procedures described below introduce an alter-
native way of performing suppression in this case. They also attempt to
prevent implosion by adaptively tuning NAK_BO_IVL.
16.2. Tuning NAK_BO_IVL
Sources and network elements continuously monitor the number of dupli-
cated NAKs received and use this observation to tune the NAK back-off
interval (NAK_BO_IVL) for the first PGM-hop receivers connected to them.
Receivers learn the current value of NAK_BO_IVL through OPT_NAK_BO_IVL
appended to NCFs or SPMs.
16.2.1. Procedures - Sources and Network Elements
For each TSI, sources and network elements advertise the value of
NAK_BO_IVL that their first PGM-hop receivers should use. They advertise
a separate value on all the outgoing interface for the TSI and keep
track of the last values advertised.
For each interface and TSI, sources and network elements count the
number of NAKs received for a specific repair state (i.e., per sequence
number per TSI) from the time the interface was first added to the
repair state list until the time the repair state is discarded. Then
they use this number to tune the current value of NAK_BO_IVL as follows:
Increase the current value NAK_BO_IVL when the first duplicate NAK is
received for a given SQN on a particular interface.
Decrease the value of NAK_BO_IVL if no duplicate NAKs are received on
a particular interface for the last NAK_PROBE_NUM measurements where
each measurement corresponds to the creation of a new repair state.
An upper and lower limit are defined for the possible value of
[Page 93]
INTERNET-DRAFT PGM Specification 24 June 1999
NAK_BO_IVL at any time. These are NAK_BO_IVL_MAX and NAK_BO_IVL_MIN
respectively. The initial value that should be used as a starting point
to tune NAK_BO_IVL is NAK_BO_IVL_DEFAULT. The policies recommended for
increasing and decreasing NAK_BO_IVL are multiplying by two and dividing
by two respectively.
Sources and network elements advertise the current value of NAK_BO_IVL
through the OPT_NAK_BO_IVL that they append to NCFs. They may also
append OPT_NAK_BO_IVL to outgoing SPMs.
In order to avoid forwarding the NAK_BO_IVL advertised by the parent,
network elements network elements must be able to recognize
OPT_NAK_BO_IVL. Network elements that receive SPMs containing
OPT_NAK_BO_IVL must either remove the option or over-write its content
(NAK_BO_IVL) with the current value of NAK_BO_IVL for the outgoing
interface(s), before forwarding the SPMs.
Sources may advertise the value of NAK_BO_IVL_MAX and NAK_BO_IVL_MIN to
the session by appending a OPT_NAK_BO_RNG to SPMs.
16.2.2. Procedures - Receivers
Receivers learn the value of NAK_BO_IVL to use through the option
OPT_NAK_BO_IVL, when this is present in NCFs or SPMs. The initial value
of NAK_BO_IVL is set to NAK_BO_IVL_DEFAULT.
Receivers that receive an SPM containing OPT_NAK_BO_RNG must use its
content to set the local values of NAK_BO_IVL_MAX and NAK_BO_IVL_MIN.
16.2.3. Adjusting NAK_BO_IVL in the absence of NAKs
Monitoring the number of duplicate NAKs provides a means to track
indirectly the change in the size of first PGM-hop receiver population
and adjust NAK_BO_IVL accordingly. Note that the number of duplicate
NAKs for a given SQN is related to the number of first PGM-hop children
that scheduled (or forwarded) a NAK and not to the absolute number of
first PGM-hop children. This mechanism, however, does not work in the
absence of packet loss, hence a large number of duplicate NAKs is possi-
ble after a period without NAKs, if many new receivers have joined the
session in the meanwhile. To address this issue, PGM Sources and network
elements should periodically poll the number of first PGM-hop children
using the "general poll" procedures described in Appendix E. If the
result of the polls shows that the population size has increased signi-
ficantly during a period without NAKs, they should increase NAK_BO_IVL
as a safety measure.
[Page 94]
INTERNET-DRAFT PGM Specification 24 June 1999
16.3. Containing Implosion in the Presence of Network Failures
16.3.1. Detecting Network Failures
In some cases PGM (parent) network elements can promptly detect the loss
of all or part of the the suppressing multicast distribution tree (due
to network failures or route changes) by checking their multicast con-
nectivity, when they receive NAKs. In some other cases this is not pos-
sible as the connectivity problem might occur at some other non-PGM node
downstream or might take time to reflect in the multicast routing table.
To address these latter cases, PGM uses a simple heuristic: a failure is
assumed for a TSI when the count of duplicated NAKs received for a
repair state reaches the value DUP_NAK_MAX in one of the interfaces.
16.3.2. Containing Implosion
When a PGM source or network element detects or assumes a failure for
which it looses multicast connectivity to down-stream PGM agents (either
receivers or other network elements), it sends unicast NCFs to them in
response to NAKs. Downstream PGM network elements which receive unicast
NCFs and have multicast connectivity to the multicast session send spe-
cial SPMs to prevent further NAKs until a regular SPM sent by the source
refreshes the PGM tree.
Procedures - Sources and Network Elements
PGM sources or network elements which detect or assume a failure that
prevent them from reaching down-stream PGM agents through multicast NCFs
revert to confirming NAKs through unicast NCFs for a given TSI on a
given interface. If the PGM agent is the source itself, than it must
generate an SPM for the TSI, in addition to sending the unicast NCF.
Network elements must keep using unicast NCFs until they receive a regu-
lar SPM from the source.
When a unicast NCF is sent for the reasons described above, it must con-
tain the OPT_NEIGHBOUR_UNREACH option and the OPT_PATH_NLA option. The
former indicates that the sender is unable to use multicast to reach
downstream PGM agents. The latter reports the network layer address of
the sender, namely the NLA of the interface leading to the unreachable
subtree.
When a PGM network element receives an NCF containing the
OPT_NEIGHBOUR_UNREACH option, it must ignore it if OPT_PATH_NLA speci-
fies an upstream neighbour different to the one currently know. Assum-
ing the network element matches the OPT_PATH_NLA to the upstream neigh-
bour address, it must stop forwarding NAKs for the TSI until it receives
a regular SPM for the TSI. In addition, it must also generate a special
[Page 95]
INTERNET-DRAFT PGM Specification 24 June 1999
SPM to prevent downstream receivers from sending more NAKs. This special
SPM must contain the OPT_NEIGHBOUR_UNREACH option and should have a
SPM_SQN equal to SPM_SQN of the last regular SPM forwarded. The
OPT_NEIGHBOUR_UNREACH option invalidates the windowing information in
SPMs (SPM_TRAIL and SPM_LEAD). These fields should be filled with zeros
by the PGM network element that adds the OPT_NEIGHBOUR_UNREACH option.
PGM network elements which receive an SPM containing the
OPT_NEIGHBOUR_UNREACH option and whose SPM_PATH matches the currently
known PGM parent, must forward them in the normal way and must stop for-
warding NAKs for the TSI until they receive a regular SPM for the TSI.
If the SPM_PATH does not match the currently known PGM parent, the SPM
containing the OPT_NEIGHBOUR_UNREACH option must be ignored.
Procedures - Receivers
PGM receivers which receive either an NCF or an SPM containing the
OPT_NEIGHBOUR_UNREACH option must stop sending NAKs until a regular SPM
is received for the TSI.
On reception of a unicast NCF containing the OPT_NEIGHBOUR_UNREACH
option receivers must generate a multicast copy of the packet with TTL
set to one on the RPF interface for the data source. This will prevent
other receivers in the same subnet from generating NAKs.
Receivers must ignore windowing information in SPMs which contain the
OPT_NEIGHBOUR_UNREACH option.
Receivers must ignore NCFs containing the OPT_NEIGHBOUR_UNREACH option
if the OPT_PATH_NLA specifies a neighbour different to the one currently
know to be the PGM parent neighbour. Similarly receivers must ignore
SPMs containing the OPT_NEIGHBOUR_UNREACH option if SPM_PATH does not
match the current PGM parent.
16.4. Packet Formats
16.4.1. OPT_NAK_BO_IVL - Packet Extension Format
[Page 96]
INTERNET-DRAFT PGM Specification 24 June 1999
OPT_NAK_BO_IVL may be appended to NCFs or SPMs.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Option Length | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NAK Backoff Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type = 0x0B
NAK Backoff Interval
The value of NAK-generation Backoff Interval in microseconds.
16.4.2. OPT_NAK_BO_RNG - Packet Extension Format
OPT_NAK_BO_RNG may be appended to SPMs.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Option Length | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Maximum NAK Backoff Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Minimum NAK Backoff Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type = 0x0B
Maximum NAK Backoff Interval
The maximum value of NAK-generation Backoff Interval in
microseconds.
Minimum NAK Backoff Interval
The minimum value of NAK-generation Backoff Interval in
microseconds.
[Page 97]
INTERNET-DRAFT PGM Specification 24 June 1999
16.4.3. OPT_NEIGHBOUR_UNREACH - Packet Extension Format
OPT_NEIGHBOUR_UNREACH may be appended to SPMs and NCFs.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Option Length | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type = 0x0C
When present in SPMs, it invalidates the windowing information.
16.4.4. OPT_PATH_NLA - Packet Extension Format
OPT_PATH_NLA may be appended to NCFs.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Option Length | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Path NLA |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type = 0x0D
Path NLA
The NLA of the interface on the originating PGM network element
that it uses to send multicast SPMs to the recipient of the packet
containing this option.
[Page 98]
INTERNET-DRAFT PGM Specification 24 June 1999
Work in Progress
In addition to the explicitly speculative material in the foregoing,
work is also in progress on:
Congestion avoidance through transmit rate control.
Throughput control through shedding of lossy receivers.
Reducing the latency of the alignment of source-path state with
underlying multicast routing changes.
Header compression.
Strategies for securing PGM against the black-hole attacks outlined
in Security Considerations.
Heuristics for delaying the transmission of RDATA from a source to
balance the tradeoff between the repair latency experienced by
receivers and the overhead of duplicate RDATA packets experienced by
the network.
[Page 99]
INTERNET-DRAFT PGM Specification 24 June 1999
Acknowledgements
The design and specification of PGM has been substantially influenced by
reviews and revisions provided by several people who took the time to
read and critique this document. These include, in alphabetical order:
Bob Albrightson albright@cisco.com
Nidhi Bhaskar nbhaskar@cisco.com
Joel Bion jpbion@cisco.com
Mark Bowles bowles@tibco.com
Jon Crowcroft j.crowcroft@cs.ucl.ac.uk
Steve Deering deering@cisco.com
Richard Edmonstone redmonst@cisco.com
Tugrul Firatli tf@tibco.com
Jim Gemmell jgemmell@microsoft.com
Dan Harkins dharkins@cisco.com
Dima Khoury dkhoury@cisco.com
Dan Leshchiner dleshc@tibco.com
Todd Montgomery tmont@gcast.com
Gerard Newman gkn@network-alchemy.com
Dave Oran oran@cisco.com
Denny Page denny@tibco.com
Ken Pillay ken@cisco.com
Chetan Rai crai@cs.stanford.edu
Yakov Rekhter yakov@cisco.com
Luigi Rizzo luigi@iet.unipi.it
Dave Rossetti rossetti@cisco.com
Paul Stirpe paul.stirpe@reuters.com
Lorenzo Vicisano lorenzo@cisco.com
Brian Whetten whetten@gcast.com
Kyle York kyork@cisco.com
[Page 100]
INTERNET-DRAFT PGM Specification 24 June 1999
References
[1] B. Whetten, T. Montgomery, S. Kaplan, "A High Performance Totally
Ordered Multicast Protocol", in "Theory and Practice in Distributed Sys-
tems", Springer Verlag LCNS938, 1994
[2] S. Floyd, V. Jacobson, C. Liu, S. McCanne, L. Zhang, "A Reliable
Multicast Framework for Light-weight Sessions and Application Level
Framing", ACM Transactions on Networking, November 1996
[3] J. C. Lin, S. Paul, "RMTP: A Reliable Multicast Transport Protocol",
ACM SIGCOMM August 1996
[4] K. Miller, K. Robertson, A. Tweedly, M. White, "Multicast File
Transfer Protocol (MFTP) Specification", INTERNET DRAFT draft-miller-
mftp-spec-02, January 1997
[5] S. Deering, "Host Extensions for IP Multicasting", INTERNET RFC1112,
STD 5, August 1989
[6] D. Katz, "IP Router Alert Option", INTERNET DRAFT draft-katz-
router-alert-04, January 1997
[7] C. Partridge, "Gigabit Networking", Addison Wesley 1994
[8] H. W. Holbrook, S. K. Singhal, D. R. Cheriton, "Log-Based Receiver-
Reliable Multicast for Distributed Interactive Simulation", ACM SIGCOMM
1995
[9] R. Rivest, "The MD5 Message-Digest Algorithm", INTERNET RFC1321,
INFORMATIONAL, April 1992
[10] J. Reynolds, J. Postel, "Assigned Numbers", INTERNET RFC1700, STD
2, October 1994
[11] J. Nonnenmacher, E. Biersack, D. Towsley, "Parity-Based Loss
Recovery for Reliable Multicast Transmission", ACM SIGCOMM September
1997
[12] L. Rizzo, "Effective Erasure Codes for Reliable Computer Communica-
tion Protocols", Computer Communication Review, April 1997
[13] V. Jacobson, "Congestion Avoidance and Control", ACM SIGCOMM August
1988
[Page 101]
INTERNET-DRAFT PGM Specification 24 June 1999
Authors' Addresses
Tony Speakman
speakman@cisco.com
Nidhi Bhaskar
nbhaskar@cisco.com
Richard Edmonstone
redmonst@ciscolcom
Dino Farinacci
dino@cisco.com
Steven Lin
slin@cisco.com
Alex Tweedly
agt@cisco.com
Lorenzo Vicisano
lorenzo@cisco.com
Cisco Systems, Inc.
170 West Tasman Drive,
San Jose, CA 95134
Jim Gemmell
jgemmell@microsoft.com
Microsoft Bay Area Research Center
301 Howard Street
San Francisco, CA. 94105
[Page 102]