INTERNET-DRAFT       PGM Reliable Transport Protocol       Tony Speakman
Expires 8 July 1998                                       Dino Farinacci
                                                              Steven Lin
                                                            Alex Tweedly

                                                           cisco Systems
                                                          8 January 1998


             PGM Reliable Transport Protocol Specification
                    <draft-speakman-pgm-spec-01.txt>


Status of this Memo

This document is an Internet-Draft.  Internet-Drafts are working docu-
ments 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."

To view the entire list of current Internet-Drafts, please check the
"1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
ftp.isi.edu (US West Coast).

Abstract

Pragmatic General Multicast (PGM) is a reliable multicast transport pro-
tocol for applications that require ordered, duplicate-free, multicast
data delivery from multiple sources to multiple receivers.  PGM guaran-
tees that a receiver in the group either receives all data packets from
transmissions and retransmissions, or is able to detect unrecoverable
data packet loss.  PGM is specifically intended as a workable solution
for multicast applications with basic reliability requirements.  Its
central design goal is simplicity of operation with due regard for sca-
lability and network efficiency.









Speakman/Farinacci/Lin/Tweedly                                  [Page 1]


INTERNET-DRAFT             PGM Specification              8 January 1998


                           Table of Contents


1.  Introduction and Overview .....................................    3
2.  Architectural Description .....................................    9
3.  Terms and Concepts ............................................   12
4.  Procedures - General ..........................................   21
5.  Procedures - Sources ..........................................   21
6.  Procedures - Receivers ........................................   24
7.  Procedures - Network Elements .................................   29
8.  Packet Formats ................................................   33
9.  Options .......................................................   42
10. Security Considerations .......................................   53
Appendix A - Congestion Avoidance .................................   55
Appendix B - Flow Control .........................................   56
Work in Progress ..................................................   63
Acknowledgements ..................................................   63
References ........................................................   63

































Speakman/Farinacci/Lin/Tweedly                                  [Page 2]


INTERNET-DRAFT             PGM Specification              8 January 1998


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,
duplicate-free, multicast data delivery from multiple sources to multi-
ple 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 in
the absence of negative acknowledgments from any receiver.  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 transmis-
sions and retransmissions, 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.





Speakman/Farinacci/Lin/Tweedly                                  [Page 3]


INTERNET-DRAFT             PGM Specification              8 January 1998


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.
Retransmissions (RDATA) may be provided either by the source itself or
by a Designated Local Retransmitter (DLR) in response to a NAK, or by
another receiver in response to an NCF.

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
retransmissions, but first it's necessary to describe the mechanisms for
establishing the requisite source path state in PGM network elements.

To establish source path state in PGM network elements, the basic data



Speakman/Farinacci/Lin/Tweedly                                  [Page 4]


INTERNET-DRAFT             PGM Specification              8 January 1998


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 retransmission 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
retransmissions 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 retransmit state in
the network elements which is used in turn to constrain the (downward)
forwarding of the corresponding RDATA.

Besides procedures for other receivers to provide retransmissions, PGM
also specifies options and procedures that permit designated local
retransmitters (DLRs) to announce their availability and to redirect
retransmission requests (NAKs) to themselves rather than to the original
source.

Finally, since PGM operates without regular return traffic from
receivers, conventional feedback mechanisms for transport flow and
congestion control cannot be applied.  Appendix A specifies some prelim-
inary strategies for congestion avoidance to be modified and proven or
discarded as experience dictates.  Appendix B specifies a basic and
optional flow control supplement native to PGM itself that introduces 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, there-
fore, PGM relies on a purely rate-limited transmission strategy in the
source to bound the bandwidth consumed by PGM transport sessions and to
define the transmit window maintained by the source.

PGM defines four basic packet types:  three that flow downstream (SPMs,
DATA, NCFs), and one that flows upstream (NAKs).

1.2.  Design Goals and Constraints

PGM has been designed to serve that broad range of multicast



Speakman/Farinacci/Lin/Tweedly                                  [Page 5]


INTERNET-DRAFT             PGM Specification              8 January 1998


applications 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 realizing these efficiences are the implosion of negative and posi-
tive acknowledgements from receivers to senders, retransmission latency
from the source, and the propagation of retransmissions 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 retransmissions and relia-
bility.  Positive acknowledgements primarily determine transmit buffer
management.

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 retransmissions 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 retransmissions, or is able to
detect unrecoverable data packet loss.

PGM includes strategies for repeatedly soliciting NAKs from receivers,



Speakman/Farinacci/Lin/Tweedly                                  [Page 6]


INTERNET-DRAFT             PGM Specification              8 January 1998


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
retransmission either from the source, another receiver, or a designated
local retransmitter (DLR).  Without ACKs and knowledge of group member-
ship, 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 before generating a NAK during which
interval the NAK is suppressed by the receiver upon receipt of a match-
ing NCF.  In addition, PGM network elements eliminate duplicate NAKs
received on different interfaces on the same network element.  The com-
bination of these two strategies usually results in the source receiving
just a single NAK for any given lost data packet.

Whether a retransmission is provided from another receiver, a DLR, or
the original source, it is important to constrain that retransmission to
only those network segments containing members that negatively ack-
nowledged the original transmission rather than propagating it
throughout the group.  PGM specifies procedures for network elements to
use the pattern of NAKs to define a sub-tree within the group upon which
to forward the corresponding retransmission 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.






Speakman/Farinacci/Lin/Tweedly                                  [Page 7]


INTERNET-DRAFT             PGM Specification              8 January 1998


1.2.5.  Operability

PGM is designed to function, albeit with less efficiency, even in the
presence of network elements that have no knowledge of PGM.  To that
end, all PGM data packets can be conventionally multicast routed by
non-PGM network elements with no loss of functionality, but with some
inefficiency in the propagation of RDATA and NCFs.

In addition, since NAKs are unicast to the last-hop PGM network element
and NCFs are multicast to the group, NAK/NCF operation is also con-
sistent across non-PGM network elements.  However, since the NAK
suppression back-off delay is a protocol constant, and receivers rely on
the NCF to suppress NAKs, receivers must always have a PGM network ele-
ment 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, sequence
number ranges, late joining, time-stamping, reception quality reports,
sequence number dropout, 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.

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.

Sequence number ranges may be used in conjunction with NAKs to allow
receivers to negatively acknowledge a contiguous range of missing
sequence numbers in a single NAK.

Late joining allows a source to indicate whether or not receivers may
request all available retransmissions when they initially join a partic-
ular 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.



Speakman/Farinacci/Lin/Tweedly                                  [Page 8]


INTERNET-DRAFT             PGM Specification              8 January 1998


That interval is interpreted by both network elements and sources to
determine whether to continue with or abandon a given retransmission.

Reception quality reports may be used in conjunction with NAKs to allow
receivers to provide a reception quality metric for local interpretation
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, receivers or network elements that
redirect NAKs to a DLR must also send a NULL NAK to provide congestion
feedback to the original source without also provoking a retransmission
from that source.

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 retransmissions.  The
division of these functions is described in this section and expanded in
detail in the next section.

2.1.  Source Functions

   Data Transmission

      Sources multicast ODATA packets to the group within the transmit
      window at a given transmit rate.

   Source Path State

      Sources multicast SPMs to the group, interleaved with ODATA if
      present, to establish source path state in PGM network elements.

   NAK Reliability

      Sources multicast NCFs to the group in response to any NAKs they
      receive.



Speakman/Farinacci/Lin/Tweedly                                  [Page 9]


INTERNET-DRAFT             PGM Specification              8 January 1998


   Data Retransmission

      Sources multicast RDATA packets to the group in response to NAKs
      received for data packets within the transmit window.

   Transmit Window Advance

      Sources multicast SPMs to the group in preparation for advancing
      the transmit window.  Sources may simply advance the window with
      the passage of time, or they may delay advancing the window until
      no NAKs for the expiring fraction of the window are received
      within a given SPM response interval.


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.

   Retransmission Requests

      Receivers unicast NAKs to the last-hop PGM network element 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 is received dur-
      ing the NAK transmit back-off interval.

   Local Retransmission

      Receivers may multicast retransmissions of any data in their
      receive windows for which they receive a matching NCF.

   Local Retransmission Suppression

      Receivers suppress retransmissions for which a matching
      retransmission is received during the retransmit back-off inter-
      val.



Speakman/Farinacci/Lin/Tweedly                                 [Page 10]


INTERNET-DRAFT             PGM Specification              8 January 1998


   Receive Window Advance

      Receivers advance their receive windows as directed by an SPM
      unless they detect that they are missing data packets in the
      expiring fraction of the window.  Receivers should expedite
      retransmission requests for missing data packets in the expiring
      fraction of the window.

      Receivers immediately advance their receive windows upon receipt
      of any PGM data packet within the receive window that advances the
      receive window.

2.3.  Network Element Functions

   Network elements forward ODATA without intervention.

   Source Path State

      Network elements intercept SPMs and use them to establish source
      path state for the corresponding 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
      retransmit 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 only until they receive an NCF
      in response.

   NAK Elimination

      Network elements discard exact duplicates of any NAK for which
      they already have retransmit 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 retransmit state consisting
      of a list of interfaces upon which a given NAK was received, and



Speakman/Farinacci/Lin/Tweedly                                 [Page 11]


INTERNET-DRAFT             PGM Specification              8 January 1998


      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
      retransmit state without outgoing interfaces in anticipation of
      responding to and eliminating duplicates of the NAK that may
      arrive from downstream.

3.  Terms and Concepts

Before proceeding from the preceding overview to the detail in the sub-
sequent Procedures, this section presents some concepts and definitions
that make that detail more intelligible.

3.1.  Transport Session Identifiers

Every PGM packet is identified by a:

TSI            transport session identifier

TSIs must be globally unique, and only one source at a time may act as
the source for a transport session.  (Note that retransmitters do not
change the TSI in any RDATA they transmit).  TSIs are composed of the
concatenation of a globally unique source identifier (GSI) and a
source-assigned 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.





Speakman/Farinacci/Lin/Tweedly                                 [Page 12]


INTERNET-DRAFT             PGM Specification              8 January 1998


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 retransmission (TXW_SECS), and the maximum
transmit rate (in bytes/second) maintained by a source to regulate its
bandwidth utilization (TXW_MAX_RTE).

The size of the transmit window in seconds is simply TXW_SECS.  The size
of the transmit window in bytes (TXW_BYTES) is (TXW_MAX_RTE * TXW_SECS).
The size of the transmit window in sequence numbers (TXW_SQNS) is
(TXW_BYTES / bytes-per-packet).

In terms of sequence numbers, the transmit window is the range of
sequence numbers consumed by the source for sequentially numbering and
transmitting the most recent TXW_SECS of ODATA packets.  The trailing
(or left) edge of the transmit window (TXW_TRAIL) is defined as the
sequence number of the oldest data packet available for retransmission
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



Speakman/Farinacci/Lin/Tweedly                                 [Page 13]


INTERNET-DRAFT             PGM Specification              8 January 1998


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 retransmission and increments its transmit window in 5
   second increments, then

      TXW_MAX_RTE = 16kBps
      TXW_ADV_SECS = 5 seconds,
      TXW_SECS = 35 seconds,
      TXW_BYTES = 560kB,
      TXW_SQNS = 383 (rounded up),

   and the size of the increment window in sequence numbers
   (TXW_MAX_RTE * TXW_ADV_SECS / 1500) = 54 (rounded down).

Continuing 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



Speakman/Farinacci/Lin/Tweedly                                 [Page 14]


INTERNET-DRAFT             PGM Specification              8 January 1998


   constant 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 ODATA plus RDATA

TXW_TRAIL      the sequence number defining the trailing edge of the
               transmit window, the sequence number of the oldest data
               packet available for retransmission

TXW_LEAD       the sequence number defining the leading edge of the
               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

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.

For a given transport session identified by a TSI, a receiver maintains:

RXW_TRAIL      the sequence number defining the trailing edge of the
               receive window, the sequence number (known from data
               packets and SPMs) of the oldest data packet available for
               retransmission 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

RXW_INC        the sequence number defining the leading edge of the
               increment window, the greatest sequence number (known
               from SPMs) amongst the sequence numbers of those data
               packets that will expire upon the next increment of the
               receive window




Speakman/Farinacci/Lin/Tweedly                                 [Page 15]


INTERNET-DRAFT             PGM Specification              8 January 1998


The receive window is the range of sequence numbers a receiver is
expected to use to identify receivable ODATA.

The increment window is the range of sequence numbers that will be the
first to be made unavailable for retransmission by the source.  It is
the range of the oldest sequence numbers from (and including) RXW_TRAIL
through RXW_INC.

A data packet is described as being "in" the receive or increment window
if its sequence number is in the receive or increment window.

The receive window is advanced by the receiver when it receives an SPM
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 retransmit state required to constrain RDATA, it's
essential that NAKs return from a receiver to a source on the reverse of
the distribution tree from the source.  That is, they must return
through the same sequence of PGM network elements through which the
ODATA was forwarded, but in reverse.  There are two reasons for this,
the less obvious one being by far the more important one.

The first and obvious reason is that RDATA is forwarded on the same path
as ODATA and so retransmit 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 retransmit
state, PGM network elements do NOT forward RDATA, so the default
behaviour is to discard retransmissions.  If retransmit state is not
properly established for interfaces on which ODATA went missing, then
receivers on those interfaces will continue to NAK for lost data and
ultimately experience unrecoverable data loss.

The principle function of SPMs is to provide the source path state
required for PGM network elements to forward NAKs from one PGM network
element to the next on the reverse of the distribution tree for the TSI,
establishing retransmit 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 actual hop away.  SPMs establish the iden-
tity of the upstream PGM network element on the distribution tree for
each TSI in each group in each PGM network element, a sort of virtual
PGM topology.  So although NAKs are unicast addressed, they are NOT uni-
cast routed by PGM network elements in the conventional sense.  Instead
PGM network elements use the source path state established by SPMs to



Speakman/Farinacci/Lin/Tweedly                                 [Page 16]


INTERNET-DRAFT             PGM Specification              8 January 1998


direct NAKs PGM-hop-by-PGM-hop toward the source.  The idea is to con-
strain NAKs to the pure PGM topology spanning the more heterogeneous
underlying topology of both PGM and non-PGM network elements.

The result is retransmit 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 retransmit 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) and the leading edge of the increment window (SPM_INC).  When
SPM_INC is greater than SPM_TRAIL, the SPM is advertising an imminent
advance of the transmit window across the increment window.  When such
an advance is not imminent, SPM_INC and SPM_TRAIL have the same value.
In the absence of data, SPMs may be used to close the transmit window in
time by advancing the transmit window until all three values SPM_TRAIL,
SPM_INC, 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.

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_INC        the sequence number defining the leading edge of the
               source's increment window (TXW_INC)




Speakman/Farinacci/Lin/Tweedly                                 [Page 17]


INTERNET-DRAFT             PGM Specification              8 January 1998


SPM_LEAD       the sequence number defining the leading edge of the
               source's transmit window (TXW_LEAD)

SPM_PATH       the network-layer address (NLA) of the interface on the
               PGM network element on which the SPM is forwarded

3.6.2.  Data Packets

3.6.2.1.  ODATA - Original Data

ODATA packets are transmitted by sources to send application data to
receivers.

ODATA packets are multicast to the group and contain:

OD_TSI         the globally unique source-assigned TSI

OD_TRAIL       the sequence number defining the trailing edge of the
               source's transmit window (TXW_TRAIL)

               OD_TRAIL makes the protocol more robust in the face of
               lost SPMs.  By including the trailing edge of the
               transmit window on every data packet, receivers that have
               missed any SPMs that advanced the transmit window can
               still detect the case, recover the application, and
               potentially 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 - Retransmitted Data

RDATA packets are retransmitted data 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 of which this is a retransmis-
               sion

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 of which this is a
               retransmission

RD_SQN         OD_SQN of the ODATA packet of which this is a retransmis-
               sion




Speakman/Farinacci/Lin/Tweedly                                 [Page 18]


INTERNET-DRAFT             PGM Specification              8 January 1998


3.6.3.  Negative Acknowledgements

3.6.3.1.  NAKs - Negative Acknowledgments

NAKs are transmitted by receivers to request retransmission of missing
data packets.

NAKs are unicast (PGM-hop-by-PGM-hop) to the source and contain:

NAK_TSI        OD_TSI of the ODATA packet for which retransmission is
               requested

NAK_SQN        OD_SQN of the ODATA packet for which retransmission 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 either receivers or network elements that are
redirecting their NAKs to a DLR 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



Speakman/Farinacci/Lin/Tweedly                                 [Page 19]


INTERNET-DRAFT             PGM Specification              8 January 1998


NCF_SRC        NAK_SRC of the NAK being confirmed

NCF_GRP        NAK_GRP of the NAK being confirmed

3.6.5.  Option Encodings

OPT_FRAGMENT - Fragmentation

OPT_RANGE    - Sequence Number Range

OPT_JOIN     - Late Joining

OPT_TIME     - Time Stamp

OPT_RXQ      - Reception Quality Report

OPT_DROP     - Sequence Number Dropout

OPT_REDIRECT - Redirect
































Speakman/Farinacci/Lin/Tweedly                                 [Page 20]


INTERNET-DRAFT             PGM Specification              8 January 1998


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 protocol 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.  Note that
TXW_MAX_RTE is the maximum cumulative transmit rate of SPMs, ODATA and
RDATA.  The reason for calculating TXW_MAX_RTE in this way is so that
retransmissions will act to back off the rate at which ODATA is
transmitted.

5.1.2.  Transmit Rate Regulation

To regulate its transmit rate, a source must use a token bucket scheme
or any other traffic management scheme that yields equivalent behaviour.
A token bucket [7] is characterized by a continually sustainable data
rate (the token rate) and the extent to which the data rate may exceed
the token rate for short periods of time (the token bucket size).  Over
any arbitrarily chosen interval, the number of bytes the source may
transmit cannot exceed the token bucket size plus the product of the
token rate and the chosen interval.



Speakman/Farinacci/Lin/Tweedly                                 [Page 21]


INTERNET-DRAFT             PGM Specification              8 January 1998


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.  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.4.  Heartbeat SPMs

In the absence of data to transmit, a source should transmit SPMs at a
decaying rate in order to assist early detection of lost data, to main-
tain current source path state in PGM network elements, and to maintain
current receive window state in the receivers.

In this scheme [8], a source maintains an inter-heartbeat timer IHB_TMR
which times the interval between the most recent packet (ODATA, RDATA,
or SPM) transmission and the next heartbeat transmission.  IHB_TMR is
initialized to a minimum interval IHB_MIN after the transmission of any
data packet.  If IHB_TMR expires, the source transmits a heartbeat SPM
and initializes IHB_TMR to double its previous value.  The transmission
of consecutive heartbeat SPMs doubles IHB each time up to a maximum
interval IHB_MAX.  The transmission of any data packet initializes
IHB_TMR to IHB_MIN once again.  The effect is to provoke prompt detec-
tion of missing packets in the absence of data to transmit, and to do so
with minimal bandwidth overhead.

5.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 retransmissions.  The generation of NCFs should be
rate-limited to protect against a denial of service in the presence of a
NAK storm.

5.3.  Data Retransmission

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



Speakman/Farinacci/Lin/Tweedly                                 [Page 22]


INTERNET-DRAFT             PGM Specification              8 January 1998


ODATA.  The effect of this priority is to back off the transmission of
ODATA in favour of RDATA.

Note that a source does not observe a random back-off interval before
transmitting RDATA, so it is unlikely that any directly connected
receivers will provide local retransmissions.  For this reason, no RDATA
suppression procedures are specified for sources.

5.4.  Transmit Window Advance

5.4.1.  Advancing across the Increment Window

A source must initiate SPM repetition in anticipation of advancing the
trailing edge of the transmit window from TXW_TRAIL to TXW_INC.  SPMs
advise receivers that the range of sequence numbers between SPM_TRAIL
(TXW_TRAIL) and SPM_INC (TXW_INC) are about to be expired from the
transmit window (i.e., the range of sequence numbers that are about to
occupy the increment window).  So if SPM repetition is initiated
SPM_RPT_IVL ahead of the expiry of the increment window, the SPMs must
advertise the range of sequence numbers that will expire in SPM_RPT_IVL.
SPM_RPT_IVL may be in the range (0, TXW_ADV_SECS).  SPM_RPT_IVL should
be at least as large as the worst case round trip delay to any receiver
a source is required to reach.  SPM_RPT_RTE should be at least high
enough to result in the transmission of at least two SPMs within
SPM_RPT_IVL.

A source may simultaneously continue ODATA and RDATA transmission,
TXW_MAX_RTE permitting.

A source must repeat SPMs at a rate of SPM_RPT_RTE for an interval of at
least SPM_RPT_IVL.  Timer SPM_RPT_IVL_TMR is set to SPM_RPT_IVL upon
transmission of the first SPM of SPM repetition.

While SPM_RPT_IVL_TMR is running, a source should transmit RDATA within
the increment window at priority over both concurrent ODATA and other
RDATA outside of the increment window.  The effect of this priority is
to back off the transmission of ODATA and other RDATA in favour of
retransmissions of data packets about to be retired from the transmit
window.

Once the transmit window is advanced across the increment window,
SPM_TRAIL and SPM_INC are both set to the new value of TXW_TRAIL until
the next window advancement.

5.4.2.  Advancing with Data

There are two modes of operation for transmit window advancement.  In
the first, TXW_MAX_RTE is calculated from both ODATA and RDATA, and NAKs



Speakman/Farinacci/Lin/Tweedly                                 [Page 23]


INTERNET-DRAFT             PGM Specification              8 January 1998


reset SPM_RPT_IVL_TMR.

While SPM_RPT_IVL_TMR is running, a source uses the receipt of a NAK for
ODATA within the increment window to reset timer SPM_RPT_IVL_TMR to
SPM_RPT_IVL so that transmit window advancement is delayed until no NAKs
for data in the increment window are seen for SPM_RPT_IVL seconds.  If
the transmit window should fill in the meantime, further transmissions
would be suspended until the transmit window can be advanced.

A source must advance the transmit window across the increment window
only upon expiry of SPM_RPT_IVL_TMR.  This mode of operation is intended
for non-real-time, messaging applications based on the receipt of com-
plete data at the expense of delay.

5.4.3.  Advancing with Time

Alternatively, TXW_MAX_RTE may be calculated from ODATA only to maintain
a constant data rate by consuming extra bandwidth for retransmissions,
and SPM_RPT_IVL_TMR may be run down in real time, advancing the transmit
window without regard for whether NAKs for data in the increment window
are still being received.  This mode of operation is intended for real-
time, streaming applications based on the receipt of timely data at the
expense of completeness.

6.  Procedures - Receivers

6.1.  Data Reception

Initial data reception

A receiver may initiate data reception beginning only with the first
ODATA_SQN it receives within the advertised transmit window.  This
sequence number 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) incre-
ments through RXW_TRAIL_INIT, the receiver must only request retransmis-
sions for sequence numbers subsequent to RXW_TRAIL_INIT.  Thereafter, it
may request retransmissions anywhere in the transmit window.  This tem-
porary restriction on retransmission requests prevents receivers from
requesting a potentially large amount of history when they first begin
to receive a given PGM transport session.

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.



Speakman/Farinacci/Lin/Tweedly                                 [Page 24]


INTERNET-DRAFT             PGM Specification              8 January 1998


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.

A receiver must deliver only contiguous data packets to the application,
and it must do so in the order defined by those data packets' sequence
numbers.

A receiver may maintain full copies of any packet in the receive window
for possible retransmission even after having delivered that data 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 retransmit requests until it has
received at least one SPM for the corresponding TSI.

SPMs in which SPM_INC is greater than SPM_TRAIL advertise an impending
transmit window advance, and receivers should expedite retransmission
requests for missing data packets in the expiring fraction of the win-
dow.

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 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.





Speakman/Farinacci/Lin/Tweedly                                 [Page 25]


INTERNET-DRAFT             PGM Specification              8 January 1998


Generating NAKs

NAK generation requires that a receiver listen to NCFs 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 transmission of the
NAK.

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, transmit-
ting a NAK if a matching NCF is not heard, waiting NAK_RDATA_IVL, and
recommencing NAK generation if the matching data is not received.  Dur-
ing NAK_RB_IVL, a NAK is said to be pending.  During NAK_RDATA_IVL, a
NAK is said to be outstanding.

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



Speakman/Farinacci/Lin/Tweedly                                 [Page 26]


INTERNET-DRAFT             PGM Specification              8 January 1998


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 NCF that may be transmitted in response to the same NAK
from another receiver.

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 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.

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.




Speakman/Farinacci/Lin/Tweedly                                 [Page 27]


INTERNET-DRAFT             PGM Specification              8 January 1998


Addressing NAKs

A receiver (unicast) addresses a NAK to the upstream PGM network element
for the TSI.  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

A receiver must discard any NCFs it hears for data packets outside the
receive window.

If a receiver hears an NCF for a data packet in the receive window for
which it has no retransmit state, it should discard the NCF 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 pro-
cedure.

6.4.  Local Retransmission

Detecting retransmit requests

Receivers may detect retransmit requests from other receivers by compar-
ing the sequence number on any NCF received for any data packet in the
receive window.  If the receiver has received the corresponding data
packet, it may initiate RDATA generation for that packet.

Generating RDATA

RDATA generation requires that a receiver listen to NCFs and RDATA for
the same transport session.

RDATA generation also requires that a receiver observe a time out inter-
val for any given RDATA packet (i.e., per RDATA_TSI and RDATA_SQN).

The RDATA random back-off interval RDATA_RB_IVL randomly delays the
transmission of a given RDATA packet from a receiver.  RDATA_RB_IVL is
counted down from the time the retransmit request is detected.  Expiry
of RDATA_RB_IVL causes transmission of the RDATA packet.

During RDATA_RB_IVL, an RDATA packet is said to be pending.

Cancellation of RDATA generation

A receiver must cancel RDATA generation if a duplicate of the RDATA
packet is already pending from this receiver.  An RDATA packet is pend-
ing from this receiver if RDATA_RB_IVL for this RDATA packet has been
initiated in this receiver but has not yet passed.



Speakman/Farinacci/Lin/Tweedly                                 [Page 28]


INTERNET-DRAFT             PGM Specification              8 January 1998


RDATA generation is canceled upon the advancing of the receive window so
as to exclude the matching sequence number of a pending RDATA.

Backing off RDATA transmission

Before transmitting an RDATA packet, a receiver must wait some interval
RDATA_RB_IVL chosen randomly and uniformly over RDATA_BO_IVL during
which it listens for a matching RDATA packet that may be transmitted
from another receiver in response to the same NCF.

RDATA suppression

A receiver must cancel RDATA generation if it hears a matching RDATA
packet during RDATA_RB_IVL.  A matching RDATA packet must match
RDATA_TSI and RDATA_SQN.

Transmitting an RDATA packet

Upon expiry of RDATA_RB_IVL, a receiver may multicast the RDATA packet
to the group.  The RDATA packet, other than its type (and therefore its
checksum), must be an exact duplicate of the corresponding ODATA packet.

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.

7.2.  NAK Confirmation

Network elements must immediately transmit an NCF in response to any NAK
they receive.  The NCF must be multicast to the group on the interface
on which the NAK was received.  The generation of NCFs should be rate-
limited to protect against a denial of service in the presence of a NAK
storm.




Speakman/Farinacci/Lin/Tweedly                                 [Page 29]


INTERNET-DRAFT             PGM Specification              8 January 1998


Simultaneously, network elements must establish retransmit state for the
NAK if such state does not already exist, and add the interface on which
the NAK was received to the corresponding retransmit 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.  Instead, NAK anticipation and elimination act to
prevent NAK storms from network elements.

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 retransmit
state and rely on receivers to re-request the retransmission.  This
approach keeps the retransmit 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
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 retransmit state and cancel NAK forwarding (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 only one copy of any NAK it receives, and
it must forward it only to the upstream PGM network element for the TSI.




Speakman/Farinacci/Lin/Tweedly                                 [Page 30]


INTERNET-DRAFT             PGM Specification              8 January 1998


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 retransmit state in the network
element.

7.4.  NAK elimination

Network elements must discard all duplicates of a NAK that is either
pending or outstanding.  Two NAKs duplicate each other if they bear the
same NAK_TSI and NAK_SQN.

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 retransmit state for NCF_TSI and
NCF_SQN without adding the interface to the retransmit interface list,
and discards the NCF.  If the retransmit state already exists, the net-
work element just 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 retransmit state and just dis-
cards the NCF.

Anticipated NAKs permit the elimination of any subsequent matching NAKs
from downstream.

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



Speakman/Farinacci/Lin/Tweedly                                 [Page 31]


INTERNET-DRAFT             PGM Specification              8 January 1998


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.

7.8.  Constrained RDATA Forwarding

Network elements must maintain retransmit 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 retransmit state only until either
the corresponding RDATA is received and forwarded, or NAK_RDATA_IVL
passes after forwarding the first instance of a given NAK.  Thereafter,
the corresponding retransmit state must be discarded.

Network elements should discard and not forward RDATA packets for which
they have no retransmit state.  Note that the consequence of this pro-
cedure is that, while it constrains retransmissions to the interested
sub-set of the network, loss of retransmit state precipitates further
NAKs from neglected receivers.




























Speakman/Farinacci/Lin/Tweedly                                 [Page 32]


INTERNET-DRAFT             PGM Specification              8 January 1998


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 Source Port, Destination Port,
Options, Checksum, Global Source ID (GSI), and TPDU Length are:

   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.

   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.

      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.

      All option extensions are encoded in extensions to the PGM header.

   Checksum:

      This field is the usual 1's complement of the 1's complement sum
      of the entire PGM packet including header.

      The checksum does not include a network-layer pseudo header for
      compatibility with network address translation.  If the computed



Speakman/Farinacci/Lin/Tweedly                                 [Page 33]


INTERNET-DRAFT             PGM Specification              8 January 1998


      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 Source
      Port forms the TSI.

   TPDU Length:

      The length in octets of the PGM packet including the size of the
      header and any options.

Address Family Indicators (AFIs) are as specified in [10].




























Speakman/Farinacci/Lin/Tweedly                                 [Page 34]


INTERNET-DRAFT             PGM Specification              8 January 1998


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                 |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                   Increment Sequence Number                   |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                 Leading Edge Sequence Number                  |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |            NLA AFI            |          reserved             |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                            Path NLA                     ...   |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...-+-+
        | Option Extensions when present ...                            |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- ... -+-+-+-+-+-+-+-+-+-+-+-+-+-+


   Source Port:

      SPM_SPORT

      Together with SPM_GSI forms SPM_TSI

   Destination Port:

      SPM_DPORT

   Type:



Speakman/Farinacci/Lin/Tweedly                                 [Page 35]


INTERNET-DRAFT             PGM Specification              8 January 1998


      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).

   Increment Sequence Number:

      SPM_INC

      The sequence number defining the current leading edge of the
      source's increment window (TXW_INC).

   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.





Speakman/Farinacci/Lin/Tweedly                                 [Page 36]


INTERNET-DRAFT             PGM Specification              8 January 1998


8.2.  Data Packets

Data packets carry application data from a source or a retransmitter to
receivers.

   ODATA:

      Original data packets transmitted by a source.

   RDATA:

      Retransmissions transmitted by a source or by a designated local
      retransmitter (DLR) in response to a NAK, or a by a receiver in
      response to an NCF.

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

      Together with Global Source ID forms:

         OD_TSI, RD_TSI



Speakman/Farinacci/Lin/Tweedly                                 [Page 37]


INTERNET-DRAFT             PGM Specification              8 January 1998


   Destination Port:

      OD_DPORT, RD_DPORT

   Type:

      OD_TYPE =  0x10
      RD_TYPE =  0x11

   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 of which it is a
      retransmission.

   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.











Speakman/Farinacci/Lin/Tweedly                                 [Page 38]


INTERNET-DRAFT             PGM Specification              8 January 1998


8.3.  Negative Acknowledgements and Confirmations

   NAK:

      Negative Acknowledgements are sent by receivers to request the
      retransmission 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 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 unicast NLA of the entity that ori-
ginates the NCF.

The destination NLA of an NCF is a multicast group NLA.

















Speakman/Farinacci/Lin/Tweedly                                 [Page 39]


INTERNET-DRAFT             PGM Specification              8 January 1998



         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, NCF_SPORT

      Together with Global Source ID forms:

         NAK_TSI, NNAK_TSI, NCF_TSI

   Destination Port:

      NAK_DPORT, NNAK_DPORT, NCF_DPORT

   Type:

      NAK_TYPE =  0x20
      NNAK_TYPE = 0x21

      NCF_TYPE =  0x30

   Global Source ID:

      NAK_GSI, NNAK_GSI, NCF_GSI



Speakman/Farinacci/Lin/Tweedly                                 [Page 40]


INTERNET-DRAFT             PGM Specification              8 January 1998


      Together with 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
      retransmission is requested.

      NNAK_SQN is the sequence number of the RDATA packet for which
      retransmission 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_RANGE and/or OPT_TIME
      NCFs may bear OPT_RANGE and/or OPT_REDIRECT

















Speakman/Farinacci/Lin/Tweedly                                 [Page 41]


INTERNET-DRAFT             PGM Specification              8 January 1998


9.  Options

PGM specifies several end-to-end options to address specific application
requirements.  PGM specifies options to support fragmentation, sequence
number ranges, late joining, time-stamping, reception quality reports,
sequence number dropout, 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.

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

      The total length in octets of all option extensions including
      OPT_LENGTH.






Speakman/Farinacci/Lin/Tweedly                                 [Page 42]


INTERNET-DRAFT             PGM Specification              8 January 1998


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.

9.2.4.  OPT_FRAGMENT - Procedures - Network Elements

This option is not network-significant.




Speakman/Farinacci/Lin/Tweedly                                 [Page 43]


INTERNET-DRAFT             PGM Specification              8 January 1998


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.  Sequence Number Range Option - OPT_RANGE

Sequence number ranges may be used in conjunction with NAKs (and
corresponding NCFs) to allow receivers to negatively acknowledge a con-
tiguous range of missing sequence numbers in a single NAK.

In this section, a matching NCF must match NCF_TSI with NAK_TSI, NCF_SQN
with NAK_SQN, and NCF_OPT_RANGE_MAX with NAK_OPT_RANGE_MAX.  Correspond-
ing ODATA/RDATA must match OD_TSI/RD_TSI with NAK_TSI, and OD_SQN/RD_SQN
with any value in the range from NAK_SQN through NAK_OPT_RANGE_MAX,
inclusive.

9.3.1.  OPT_RANGE - Packet Extensions Contents

OPT_RANGE_MAX  the largest sequence number in the range

9.3.2.  OPT_RANGE - Procedures - Receivers

When a receiver detects a contiguous range of sequence numbers missing
from the receive window, it may request their retransmission individu-
ally with one NAK for each sequence number in the range, or it may
request their retransmission collectively with one NAK, augmented by



Speakman/Farinacci/Lin/Tweedly                                 [Page 44]


INTERNET-DRAFT             PGM Specification              8 January 1998


OPT_RANGE, for the entire range.

To specify the range, the receiver must set NAK_SQN to the value of the
smallest sequence number in the range, and it must set OPT_RANGE_MAX to
the value of the largest sequence number in the range.

In addition, the following modifications to the Procedures for NAK and
NCF processing in receivers apply.

Receipt of corresponding ODATA/RDATA during NAK_BO_IVL or NAK_RPT_IVL
does NOT complete NAK generation unless the entire range of packets is
received.

The receipt of corresponding ODATA/RDATA during NAK_RDATA_IVL restarts
NAK_RDATA_IVL.  Upon expiry of NAK_RDATA_IVL, a receiver must re-examine
the receive window to determine any remaining outstanding ranges of
missing packets.

9.3.3.  OPT_RANGE - Procedures - Network Elements

Network elements must confirm NAK ranges with a corresponding NCF.
Other than that, the Procedures for confirming and forwarding NAKs, and
for constraining RDATA are unchanged for this option.

9.3.4.  OPT_RANGE - Procedures - Sources

The following modifications to the Procedures for NAK and NCF processing
in sources apply.

A source must confirm a NAK range with a matching NCF if ANY fraction of
the specified range of packets is in the transmit window.  A source need
only retransmit those packets corresponding to that fraction of the
range in the transmit window.

9.3.5.  OPT_RANGE - 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 |                               |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                    Maximum Sequence Number                    |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   Option Type = 0x02

   Option Length = 8 octets



Speakman/Farinacci/Lin/Tweedly                                 [Page 45]


INTERNET-DRAFT             PGM Specification              8 January 1998


   Maximum Sequence Number

      The largest sequence number in the range (OPT_RANGE_MAX).

9.4.  Late Joining Option - OPT_JOIN

Late joining allows a source to bound the amount of retransmission his-
tory receivers may request when they initially join a particular tran-
sport session.

This option indicates that receivers that join a transport session in
progress may request retransmission of all data as far back as the given
minimum sequence number from the time they join the transport session.
The default is for receivers to receive data only from the first packet
they receive and onward.

9.4.1.  OPT_JOIN - Packet Extensions Contents

OPT_JOIN_MIN   the minimum sequence number for retransmission

9.4.2.  OPT_JOIN - Procedures - Receivers

If a PGM packet (ODATA, RDATA, or SPM) bears OPT_JOIN, a receiver may
initialize the trailing edge of the receive window (RXW_TRAIL_INIT) to
the given Minimum Sequence Number and proceeds with normal data recep-
tion.

9.4.3.  OPT_JOIN - Procedures - Network Elements

This option is not network-significant.

9.4.4.  OPT_JOIN - Packet Extension Format

         0                   1                   2                   3
         0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |  Option Type  | Option Length |                               |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                    Minimum Sequence Number                    |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   Option Type = 0x03

   Option Length = 8 octets

   Minimum Sequence Number




Speakman/Farinacci/Lin/Tweedly                                 [Page 46]


INTERNET-DRAFT             PGM Specification              8 January 1998


      The minimum sequence number defining the initial trailing edge of
      the receive window for a late joining receiver.

9.5.  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 retransmission.

9.5.1.  OPT_TIME - Packet Extensions Contents

OPT_TIME_STAMP absolute time interval in milliseconds

9.5.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.

9.5.3.  OPT_TIME - Procedures - Network Elements

Network elements should use the time stamp of a NAK to age the associ-
ated retransmit 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
retransmit state.  Otherwise, such a NAK must be forwarded instead of
eliminated, and its time stamp must be used to replace the time stamp of
existing retransmit state.

9.5.4.  OPT_TIME - Procedures - Sources

A source should abandon any attempt to retransmit RDATA in response to a
time stamped NAK if that retransmission cannot be completed within the
specified interval.

9.5.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                          |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+




Speakman/Farinacci/Lin/Tweedly                                 [Page 47]


INTERNET-DRAFT             PGM Specification              8 January 1998


   Option Type = 0x04

   Option Length = 8 octets

   Time Stamp

      Absolute time interval in milliseconds (OPT_TIME_STAMP).

9.6.  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.6.1.  OPT_RXQ - Packet Extensions Contents

OPT_RXQ_METRIC A reception quality metric defined by a source's local
               flow- and congestion-control procedures.

9.6.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.6.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 retransmit 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
retransmit state.

9.6.4.  OPT_RXQ - Procedures - Sources

Sources may interpret reception quality reports in a local manner to
adjust their transmission rate.

9.6.5.  OPT_RXQ - Packet Extension Format





Speakman/Farinacci/Lin/Tweedly                                 [Page 48]


INTERNET-DRAFT             PGM Specification              8 January 1998



         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

9.7.  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.7.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.7.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.






Speakman/Farinacci/Lin/Tweedly                                 [Page 49]


INTERNET-DRAFT             PGM Specification              8 January 1998


9.7.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.7.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.

9.7.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.8.  Redirect Option - OPT_REDIRECT

Redirection may be used in conjunction with NCFs to allow a designated
local retransmitter (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, receivers
or network elements that redirect their NAKs to a DLR must send a NULL
NAK to provide congestion feedback to the original source without also



Speakman/Farinacci/Lin/Tweedly                                 [Page 50]


INTERNET-DRAFT             PGM Specification              8 January 1998


provoking a retransmission from that source.

9.8.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.8.2.  OPT_REDIRECT - Procedures - DLRs

A DLR must receive any PGM sessions for which it wishes to provide a
source of retransmissions.  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 with TTL of 1 and OPT_REDIRECT providing its own network-layer
address.  The TTL constrains the redirecting NCF to the same subnet as
the source of the normal NCF.  This is to ensure that DLRs provide
retransmissions only if they are directly on the reverse path to the
original source.

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.

9.8.3.  OPT_REDIRECT - Procedures - Network Elements

Upon receiving a redirecting NCF, network elements should record the
redirecting information for the TSI, and may redirect subsequent NAKs
for the same TSI to the network address provided in the redirecting NCF
rather than to the network address those NAKs bear upon reception.
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 as originally
addressed.  In addition, for any NAK it redirects, a network element
must also unicast a NULL NAK toward the original source (i.e., the
source from which it is receiving session ODATA) so that the original
source's congestion avoidance procedures remain well informed.

Network elements must treat NULL NAKs just as they would any other NAK
with the exception that they must not add the receiving interface to the



Speakman/Farinacci/Lin/Tweedly                                 [Page 51]


INTERNET-DRAFT             PGM Specification              8 January 1998


retransmit state.  They must otherwise confirm and eliminate or forward
NULL NAKs in the usual way.  A NULL NAK would be forward only if match-
ing retransmit state has not already been created.  If a NULL NAK is
used to initially create retransmit 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 retransmission.

9.8.4.  OPT_REDIRECT - Procedures - Receivers

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
than to the network address of the corresponding ODATA for which the
receiver is requesting retransmission.  Note, however, that a redirect-
ing 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 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 original source of the missing ODATA.

9.8.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.




Speakman/Farinacci/Lin/Tweedly                                 [Page 52]


INTERNET-DRAFT             PGM Specification              8 January 1998


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
retransmit state, to forward NAKs, to identify DLRs, and to distribute
retransmissions.  These mechanisms expose PGM network elements them-
selves 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 authen-
tication of all neighbouring sources, receivers, DLRs, and network ele-
ments, the protocol is not impervious to abuse.

So putting aside the problems of rogue PGM network elements for the
moment, there are enough potential security risks to network elements
associated with sources, receivers, and DLRs alone.  These risks include
denial of service through the exhausting of both CPU bandwidth and
memory, as well as loss of (retransmit) data connectivity through the
muddling of retransmit 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
retransmit 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
retransmit 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



Speakman/Farinacci/Lin/Tweedly                                 [Page 53]


INTERNET-DRAFT             PGM Specification              8 January 1998


   knowledge of TSIs and their associated transmit windows gleaned from
   SPMs to control the proliferation of retransmit state.

   Matching of the source NLA of NCFs against the path NLA in SPMs (or
   the DLR's NLA in OPT_REDIR) to verify that the confirmation is at
   least apparently coming from the expected entity.

   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 in fact on the same subnet, is identified by the
   alleged NLA, and is PGM conversant.

   Since PGM's Local Retransmission procedures allow any receiver to
   provide RDATA, the source NLA of RDATA may vary widely in value.  At
   the expense of the efficiencies of local retransmission, a PGM net-
   work element could reduce its vulnerability to false RDATA by accept-
   ing RDATA only from the source, but as with all of these procedures,
   this is still no protection against full falsification of the
   network-layer header.
































Speakman/Farinacci/Lin/Tweedly                                 [Page 54]


INTERNET-DRAFT             PGM Specification              8 January 1998


11.  Appendix A - Congestion Avoidance

A source must implement a couple of strategies for congestion avoidance
derived in principle from the ones described in [11], but rephrased in
terms of transmit rates rather than window sizes, and adapted to account
for PGM's lack of ACKs.  As yet, neither of these adaptations has either
the analytic basis nor the practical credentials of those described in
[11], and they are proposed here entirely as experimental strategies to
be modified and proven or discarded as experience dictates.

The first congestion avoidance strategy governs the rate at which a
source may increase its transmit rate up to TXW_MAX_RTE upon initially
starting transmission or restarting transmission after receiving a NAK.
Specifically, upon initial transmission or after receiving a NAK, a
source must reduce its transmit rate to TXW_INC_RTE << TXW_MAX_RTE, and
may double its transmit rate every TXW_INC_SECS only for as long as no
NAKs are received for TXW_INC_SECS and the resulting transmit rate is
less than TXW_MAX_RTE.

   A good choice for TXW_INC_RTE would be something conservative such as
   TXW_MAX_RTE/256 to allow for 8 left shifts to get back up to
   TXW_MAX_RTE.

   A good choice for TXW_INC_SECS would be the worst case round trip
   delay to any receiver a source is required to reach (see SPM_RPT_IVL
   below).

The second congestion avoidance strategy governs the rate at which a
source must reduce its maximum transmit rate in the face of congestion,
and the rate at which it may then increase its maximum transmit rate up
to TXW_MAX_RTE.  More specifically, a source must apply a multiplicative
decrease in its maximum transmit rate in the face of congestion, and a
linear increase in its maximum transmit rate in the absence of conges-
tion.  That is, upon receipt of a NAK, a source must reduce its maximum
transmit rate by half, and thereafter increase it linearly over time
only for as long as no NAKs are received and the transmit rate does not
exceed TXW_MAX_RTE.

   A good choice for "over time" is every TXW_INC_SECS.

Upon receipt of a NAK, these two strategies will combine first to reduce
a source's transmit rate to TXW_INC_RTE from which it will increase
exponentially up to half the transmission rate in use when the NAK was
received, and thereafter to increase it linearly up to TXW_MAX_RTE for
as long as no further NAKs are received.






Speakman/Farinacci/Lin/Tweedly                                 [Page 55]


INTERNET-DRAFT             PGM Specification              8 January 1998


12.  Appendix B - 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.

12.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.

12.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



Speakman/Farinacci/Lin/Tweedly                                 [Page 56]


INTERNET-DRAFT             PGM Specification              8 January 1998


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.

12.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.

12.1.3.  Network Element Functions

Network elements forward TSNs, and RSNs without intervention.

12.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.

12.3.  Packet Contents

12.3.1.  Transmit State Notification (TSN)

TSNs are formed by adding OPT_TSN to SPMs and contain:

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



Speakman/Farinacci/Lin/Tweedly                                 [Page 57]


INTERNET-DRAFT             PGM Specification              8 January 1998


               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

12.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

12.4.  Procedures - Sources

12.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.  Specifi-
cally, 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.




Speakman/Farinacci/Lin/Tweedly                                 [Page 58]


INTERNET-DRAFT             PGM Specification              8 January 1998


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.

12.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.

12.5.  Procedures - Receivers

12.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
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 retransmissions for sequence numbers subsequent to



Speakman/Farinacci/Lin/Tweedly                                 [Page 59]


INTERNET-DRAFT             PGM Specification              8 January 1998


RXW_TRAIL_INIT.  Thereafter, it may request retransmissions anywhere in
the transmit window.  This temporary restriction on retransmission
requests prevents receivers from requesting a potentially large amount
of history when they first begin to receive a given PGM transport ses-
sion.

12.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.



























Speakman/Farinacci/Lin/Tweedly                                 [Page 60]


INTERNET-DRAFT             PGM Specification              8 January 1998


12.6.  Packet Formats


12.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 = 0x08

   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).

















Speakman/Farinacci/Lin/Tweedly                                 [Page 61]


INTERNET-DRAFT             PGM Specification              8 January 1998


12.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                           |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   Type:

      RSN_TYPE = 0x40

   Options

      RSNs may bear only OPT_JOIN.

   RSN's Sequence Number (RSN_SQN)

      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).




Speakman/Farinacci/Lin/Tweedly                                 [Page 62]


INTERNET-DRAFT             PGM Specification              8 January 1998


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.

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
Joel Bion               jpbion@cisco.com
Mark Bowles             bowles@tibco.com
Jon Crowcroft           j.crowcroft@cs.ucl.ac.uk
Steve Deering           deering@cisco.com
Tugrul Firatli          tf@tibco.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
Yakov Rekhter           yakov@cisco.com
Dave Rossetti           rossetti@cisco.com
Paul Stirpe             paul.stirpe@reuters.com
Brian Whetten           whetten@gcast.com

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




Speakman/Farinacci/Lin/Tweedly                                 [Page 63]


INTERNET-DRAFT             PGM Specification              8 January 1998


[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",
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", 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] V. Jacobson, "Congestion Avoidance and Control", SIGCOMM August
1988

Authors' Addresses

        Tony Speakman
        speakman@cisco.com

        Dino Farinacci
        dino@cisco.com

        Steven Lin
        slin@cisco.com

        Alex Tweedly
        agt@cisco.com

        Cisco Systems, Inc.
        170 West Tasman Drive,
        San Jose, CA 95134



Speakman/Farinacci/Lin/Tweedly                                 [Page 64]