In the first, called "Advance with Time", the transmit window
maintains the last TXW_SECS of data in real-time, regardless of
whether any data was sent in that real time period or not. The
actual number of bytes maintained at any instant in time will vary
between 0 and TXW_BYTES, depending on traffic during the last
TXW_SECS. In this case, TXW_MAX_RTE is the cumulative transmit rate
of SPMs and ODATA.
In the second, called "Advance with Data", the transmit window
maintains the last TXW_BYTES bytes of data for repair. That is, it
maintains the theoretical maximum amount of data that could be
transmitted in the time period TXW_SECS, regardless of when they were
transmitted. In this case, TXW_MAX_RTE is the cumulative transmit
rate of SPMs, ODATA, and RDATA.
The third strategy leaves control of the window in the hands of the
application. The API provided by a source implementation for this,
could allow the application to control the window in terms of APDUs
and to manually step the window. This gives a form of Application
Level Framing (ALF). In this case, TXW_MAX_RTE is the cumulative
transmit rate of SPMs, ODATA, and RDATA.
16.2. Advancing with Data
In the first strategy, TXW_MAX_RTE is calculated from SPMs and both
ODATA and RDATA, and NAKs reset TXW_ADV_IVL_TMR. In this mode of
operation the transmit window maintains the last TXW_BYTES bytes of
data for repair. That is, it maintains the theoretical maximum
amount of data that could be transmitted in the time period TXW_SECS.
This means that the following timers are not treated as real-time
timers, instead they are "data driven". That is, they expire when
the amount of data that could be sent in the time period they define
is sent. They are the SPM ambient time interval, TXW_ADV_SECS,
TXW_SECS, TXW_ADV_IVL, TXW_ADV_IVL_TMR and the join interval. Note
that the SPM heartbeat timers still run in real-time.
While TXW_ADV_IVL_TMR is running, a source uses the receipt of a NAK
for ODATA within the increment window to reset timer TXW_ADV_IVL_TMR
to TXW_ADV_IVL so that transmit window advancement is delayed until
no NAKs for data in the increment window are seen for TXW_ADV_IVL
seconds. If the transmit window should fill in the meantime, further
transmissions would be suspended until the transmit window can be
advanced.
A source MUST advance the transmit window across the increment window
only upon expiry of TXW_ADV_IVL_TMR.
This mode of operation is intended for non-real-time, messaging
applications based on the receipt of complete data at the expense of
delay.
16.3. Advancing with Time
This strategy advances the transmit window in real-time. In this
mode of operation, TXW_MAX_RTE is calculated from SPMs and ODATA only
to maintain a constant data throughput rate by consuming extra
bandwidth for repairs. TXW_ADV_IVL has the value 0 which advances
the transmit window without regard for whether NAKs for data in the
increment window are still being received.
In this mode of operation, all timers are treated as real-time
timers.
This mode of operation is intended for real-time, streaming
applications based on the receipt of timely data at the expense of
completeness.
16.4. Advancing under explicit application control
Some applications may wish more explicit control of the transmit
window than that provided by the advance with data / time strategies
above. An implementation MAY provide this mode of operation and
allow an application to explicitly control the window in terms of
APDUs.
17. Appendix G - Applicability Statement
As stated in the introduction, PGM has been designed with a specific
class of applications in mind in recognition of the fact that a
general solution for reliable multicast has proven elusive. The
applicability of PGM is narrowed further, and perhaps more
significantly, by the prototypical nature of at least four of the
transport elements the protocol incorporates. These are congestion
control, router assist, local retransmission, and a programmatic API
for reliable multicast protocols of this class. At the same time as
standardization efforts address each of these elements individually,
this publication is intended to foster experimentation with these
elements in general, and to inform that standardization process with
results from practise.
This section briefly describes some of the experimental aspects of
PGM and makes non-normative references to some examples of current
practise based upon them.
At least 3 different approaches to congestion control can be explored
with PGM: a receiver-feedback based approach, a router-assist based
approach, and layer-coding based approach. The first is supported by
the negative acknowledgement mechanism in PGM augmented by an
application-layer acknowledgement mechanism. The second is supported
by the router exception processing mechanism in PGM. The third is
supported by the FEC mechanisms in PGM. An example of a receiver-
feedback based approach is provided in [16], and a proposal for a
router-assist based approach was proposed in [17]. Open issues for
the researchers include how do each of these approaches behave in the
presence of multiple competing sessions of the same discipline or of
different disciplines, TCP most notably; how do each of them behave
over a particular range of topologies, and over a particular range of
loads; and how do each of them scale as a function of the size of the
receiver population.
Router assist has applications not just to implosion control and
retransmit constraint as described in this specification, but also to
congestion control as described above, and more generally to any
feature which may be enhanced by access to per-network-element state
and processing. The full range of these features is as yet
unexplored, but a general mechanism for providing router assist in a
transport-protocol independent way (GRA) is a topic of active
research [18]. That effort has been primarily informed by the router
assist component of PGM, and implementation and deployment experience
with PGM will continue to be fed back into the specification and
eventual standardization of GRA. Open questions facing the
researchers ([19], [20], [21]) include how router-based state scales
relative to the feature benefit obtained, how system-wide factors
(such as throughput and retransmit latency) vary relative to the
scale and topology of deployed router assistance, and how incremental
deployment considerations affect the tractability of router-assist
based features. Router assist may have additional implications in
the area of congestion control to the extent that it may be applied
in multi-group layered coding schemes to increase the granularity and
reduce the latency of receiver based congestion control.
GRA itself explicitly incorporates elements of active networking, and
to the extent that the router assist component of PGM is reflected in
GRA, experimentation with the narrowly defined network-element
functionality of PGM will provide some of the first real world
experience with this promising if controversial technology.
Local retransmission is not a new idea in general in reliable
multicast, but the specific approach taken in PGM of locating re-
transmitters on the distribution tree for the session, diverting
repair requests from network elements to the re-transmitters, and
then propagating repairs downward from the repair point on the
distribution tree raises interesting questions concerning where to
locate re-transmitters in a given topology, and how network elements
locate those re-transmitters and evaluate their efficiency relative
to other available sources of retransmissions, most notably the
source itself. This particular aspect of PGM, while fully specified,
has only been implemented on the network element side, and awaits a
host-side implementation before questions like these can be
addressed.
PGM presents the opportunity to develop a programming API for
reliable multicast applications that reflects both those
applications' service requirements as well as the services provided
by PGM in support of those applications that may usefully be made
visible above the transport interface. At least a couple of host-
side implementations of PGM and a concomitant API have been developed
for research purposes ([22], [23]), and are available as open source
explicitly for the kind of experimentation described in this section.
Perhaps the broadest experiment that PGM can enable in a community of
researchers using a reasonable scale experimental transport protocol
is simply in the definition, implementation, and deployment of IP
multicast applications for which the reliability provided by PGM is a
significant enabler. Experience with such applications will not just
illuminate the value of reliable multicast, but will also provoke
practical examination of and responses to the attendant policy issues
(such as peering, billing, access control, firewalls, NATs, etc.),
and, if successful, will ultimately encourage more wide spread
deployment of IP multicast itself.
18. Abbreviations
ACK Acknowledgment
AFI Address Family Indicator
ALF Application Level Framing
APDU Application Protocol Data Unit
ARQ Automatic Repeat reQuest
DLR Designated Local Repairer
GSI Globally Unique Source Identifier
FEC Forward Error Correction
MD5 Message-Digest Algorithm
MTU Maximum Transmission Unit
NAK Negative Acknowledgment
NCF NAK Confirmation
NLA Network Layer Address
NNAK Null Negative Acknowledgment
ODATA Original Data
POLL Poll Request
POLR Poll Response
RDATA Repair Data
RSN Receive State Notification
SPM Source Path Message
SPMR SPM Request
TG Transmission Group
TGSIZE Transmission Group Size
TPDU Transport Protocol Data Unit
TSDU Transport Service Data Unit
TSI Transport Session Identifier
TSN Transmit State Notification
19. 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
Joel Bion
Mark Bowles
Steve Deering
Tugrul Firatli
Dan Harkins
Dima Khoury
Gerard Newman
Dave Oran
Denny Page
Ken Pillay
Chetan Rai
Yakov Rekhter
Dave Rossetti
Paul Stirpe
Brian Whetten
Kyle York
20. References
[1] B. Whetten, T. Montgomery, S. Kaplan, "A High Performance
Totally Ordered Multicast Protocol", in "Theory and Practice in
Distributed Systems", Springer Verlag LCNS938, 1994.
[2] S. Floyd, V. Jacobson, C. Liu, S. McCanne, L. Zhang, "A
Reliable Multicast Framework for Light-weight Sessions and
Application Level Framing", ACM Transactions on Networking,
November 1996.
[3] J. C. Lin, S. Paul, "RMTP: A Reliable Multicast Transport
Protocol", ACM SIGCOMM August 1996.
[4] Miller, K., Robertson, K., Tweedly, A. and M. White, "Multicast
File Transfer Protocol (MFTP) Specification", Work In Progress.
[5] Deering, S., "Host Extensions for IP Multicasting", STD 5, RFC
1112, August 1989.
[6] Katz, D., "IP Router Alert Option", RFC2113, February 1997.
[7] C. Partridge, "Gigabit Networking", Addison Wesley 1994.
[8] H. W. Holbrook, S. K. Singhal, D. R. Cheriton, "Log-Based
Receiver-Reliable Multicast for Distributed Interactive
Simulation", ACM SIGCOMM 1995.
[9] Rivest, R., "The MD5 Message-Digest Algorithm", RFC1321, April
1992.
[10] Reynolds, J. and J. Postel, "Assigned Numbers", STD 2, RFC
1700, October 1994.
[11] J. Nonnenmacher, E. Biersack, D. Towsley, "Parity-Based Loss
Recovery for Reliable Multicast Transmission", ACM SIGCOMM
September 1997.
[12] L. Rizzo, "Effective Erasure Codes for Reliable Computer
Communication Protocols", Computer Communication Review, April
1997.
[13] V. Jacobson, "Congestion Avoidance and Control", ACM SIGCOMM
August 1988.
[14] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", BCP, 14, RFC2119, March 1997.
[15] J. Bolot, T. Turletti, I. Wakeman, "Scalable Feedback Control
for Multicast Video Distribution in the Internet", Proc.
ACM/Sigcomm 94, pp. 58-67.
[16] L. Rizzo, "pgmcc: A TCP-friendly Single-Rate Multicast
Congestion Control Scheme", Proc. of ACM SIGCOMM August 2000.
[17] M. Luby, L. Vicisano, T. Speakman. "Heterogeneous multicast
congestion control based on router packet filtering", RMT
working group, June 1999, Pisa, Italy.
[18] Cain, B., Speakman, T. and D. Towsley, "Generic Router Assist
(GRA) Building Block, Motivation and Architecture", Work In
Progress.
[19] C. Papadopoulos, and E. Laliotis,"Incremental Deployment of a
Router-assisted Reliable Multicast Scheme,", Proc. of Networked
Group Communications (NGC2000), Stanford University, Palo Alto,
CA. November 2000.
[20] C. Papadopoulos, "RAIMS: an Architecture for Router-Assisted
Internet Multicast Services." Presented at ETH, Zurich,
Switzerland, October 23 2000.
[21] J. Chesterfield, A. Diana, A. Greenhalgh, M. Lad, and M. Lim,
"A BSD Router Implementation of PGM",
http://www.cs.ucl.ac.uk/external/m.lad/rpgm/
[22] L. Rizzo, "A PGM Host Implementation for FreeBSD",
http://www.iet.unipi.it/~luigi/pgm.html
[23] M. Psaltaki, R. Araujo, G. Aldabbagh, P. Kouniakis, and A.
Giannopoulos, "Pragmatic General Multicast (PGM) host
implementation for FreeBSD.",
http://www.cs.ucl.ac.uk/research/darpa/pgm/PGM_FINAL.html
21. Authors' Addresses
Tony Speakman
EMail: speakman@cisco.com
Dino Farinacci
Procket Networks
3850 North First Street
San Jose, CA 95134
USA
EMail: dino@procket.com
Steven Lin
Juniper Networks
1194 N. Mathilda Ave.
Sunnyvale, CA 94086
USA
EMail: steven@juniper.net
Alex Tweedly
EMail: agt@cisco.com
Nidhi Bhaskar
EMail: nbhaskar@cisco.com
Richard Edmonstone
EMail: redmonst@cisco.com
Rajitha Sumanasekera
EMail: rajitha@cisco.com
Lorenzo Vicisano
Cisco Systems, Inc.
170 West Tasman Drive,
San Jose, CA 95134
USA
EMail: lorenzo@cisco.com
Jon Crowcroft
Department of Computer Science
University College London
Gower Street
London WC1E 6BT
UK
EMail: j.crowcroft@cs.ucl.ac.uk
Jim Gemmell
Microsoft Bay Area Research Center
301 Howard Street, #830
San Francisco, CA 94105
USA
EMail: jgemmell@microsoft.com
Dan Leshchiner
Tibco Software
3165 Porter Dr.
Palo Alto, CA 94304
USA
EMail: dleshc@tibco.com
Michael Luby
Digital Fountain, Inc.
39141 Civic Center Drive
Fremont CA 94538
USA
EMail: luby@digitalfountain.com
Todd L. Montgomery
Talarian Corporation
124 Sherman Ave.
Morgantown, WV 26501
USA
EMail: todd@talarian.com
Luigi Rizzo
Dip. di Ing. dell'Informazione
Universita` di Pisa
via Diotisalvi 2
56126 Pisa
Italy
EMail: luigi@iet.unipi.it
22. Full Copyright Statement
Copyright (C) The Internet Society (2001). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Funding for the RFCEditor function is currently provided by the
Internet Society.