[Docs] [txt|pdf] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits]

Versions: 03 04 05 06 07 08 09 RFC 3941

     RMT Working Group                                        B.  Adamson/NRL
     INTERNET-DRAFT                                      C.  Bormann/Tellique
     draft-ietf-rmt-bb-norm-07                              M.  Handley/ACIRI
     Expires: October 2003                                     J.  Macker/NRL
                                                                 October 2003
     
     
             NACK-Oriented Reliable Multicast (NORM) Building Blocks
     
     Status of this Memo
     
       This document is an Internet-Draft and is in full conformance with all
       provisions of Section 10 of RFC2026.
     
       Internet-Drafts are working documents of the Internet Engineering Task
       Force (IETF), its areas, and its working groups.  Note that other
       groups may also distribute working documents as Internet-Drafts.
     
       Internet-Drafts are draft documents valid for a maximum of six months
       and may be updated, replaced, or made obsolete by other documents at
       any time.  It is inappropriate to use Internet-Drafts as reference
       material or to cite them other than as "work in progress."
     
       The list of current Internet-Drafts can be accessed at
       http://www.ietf.org/ietf/1id-abstracts.txt
     
       The list of Internet-Draft Shadow Directories can be accessed at
       http://www.ietf.org/shadow.html.
     
       Copyright Notice
     
       Copyright (C) The Internet Society (2003).  All Rights Reserved.
     
     Abstract
     
       This document discusses the creation the of negative-acknowledgment
       (NACK)-oriented reliable multicast (NORM) protocols.  The rationale
       for NORM goals and assumptions are presented.  Technical challenges
       for NACK-oriented (and in some cases general) reliable multicast
       protocol operation are identified.  These goals and challenges are
       resolved into a set of functional "building blocks" that address
       different aspects of NORM protocol operation.  It is anticipated that
       these building blocks will be useful in generating different
       instantiations of reliable multicast protocols.
     
     1.0 Introduction
     
       Reliable multicast transport is a desirable technology for the
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                   [Page 1]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       efficient and reliable distribution of data to a group on the
       Internet.  The complexities of group communication paradigms
       necessitate different protocol types and instantiations to meet the
       range of performance and scalability requirements of different
       potential reliable multicast applications and users [1].  This
       document addresses the creation of negative-acknowledgment
       (NACK)-oriented reliable multicast (NORM) protocols.  While different
       protocol instantiations may be required to meet specific application
       and network architecture demands [4], there are a number of
       fundamental components that may be common to these different
       instantiations.  This document describes the framework and common
       "building block" components relevant to multicast protocols based
       primarily on NACK operation for reliable transport.  While this
       document discusses a large set of reliable multicast components and
       issues relevant to NORM protocol design, it specifically addresses in
       detail the following building blocks which are not addressed in other
       IETF documents:
     
            1)   Sender transmission strategies,
            2)   NACK-oriented repair process with timer-based feedback
                 suppression, and
            3)   Round-trip timing for adapting NORM timers.
     
       The potential relationships to other reliable multicast transport
       building blocks (Forward Error Correction (FEC), congestion control)
       and general issues with NORM protocols are also discussed.
     
     
     2.0 Rationale
     
       Each potential protocol instantiation using the building blocks
       presented here (and in other applicable building block documents) will
       have specific criteria that may influence individual protocol design.
       To support the development of applicable building blocks, it is useful
       to identify and summarize driving general protocol design goals and
       assumptions.  These are areas that each protocol instantiation will
       need to address in detail.  Each building block description in this
       document will include a discussion of the impact of these design
       criteria.  The categories of design criteria considered here include:
     
            1)   Delivery Service Model,
            2)   Group Membership Dynamics,
            3)   Sender/receiver relationships,
            4)   Group Size Scalability,
            5)   Data Delivery Performance,
            6)   Network Environments, and
            7)   Router/Intermediate System Interactions.
     
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                   [Page 2]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       All of these areas are at least briefly discussed.  Additionally,
       other reliable multicast transport building block documents, [13],
       [14], and [17] have been created to address areas outside of the scope
       of this document.  NORM protocol instantiations may depend upon these
       other building blocks as well as the ones presented here.  This
       document focuses on areas that are unique to NORM but may be used in
       concert with the other building block areas.  In some cases, a
       building block may be able address a wide range of assumptions, while
       in other cases there will be trade-offs required to meet different
       application needs or operating environments.  Where necessary,
       building block features are designed to be parametric to meet
       different requirements.  Of course, an underlying goal will be to
       minimize design complexity and to at least recommend default values
       for any such parameters that meet a general purpose "bulk data
       transfer" requirement in a typical Internet environment.
     
     2.1 Delivery Service Model
     
       The implicit goal of a reliable multicast transport protocol is the
       reliable delivery of data among a group of members communicating using
       IP multicast datagram service.  However, the specific service the
       application is attempting to provide can impact design decisions.  A
       most basic service model for reliable multicast transport is that of
       "bulk transfer" which is a primary focus of this and other related RMT
       working group documents.  However, the same principals in protocol
       design may also be applied to other services models (e.g. more
       interactive exchanges of  small messages such as weith white-boarding
       or text chat.  Within these different models there are issues such as
       the sender's ability  to cache transmitted data (or state referencing
       it) for retransmission or repair.  The needs for ordering and/or
       causality in the sequence of transmissions and receptions among
       members in the group may be different depending upon data content.
       The group communication paradigm differs significantly from the point-
       to-point model in that, depending upon the data content type, some
       receivers may complete reception of a portion of data content and be
       able to act upon it before other members have received the content.
       This may be acceptable (or even desirable) for some applications but
       not for others.  These varying requirements drive the need for a
       number of different protocol instantiation designs.  A significant
       challenge in developing generally useful building block mechanisms is
       accommodating even a limited range of these capabilities without
       defining specific application-level details.
     
     2.2 Group Membership Dynamics
     
       One area where group communication can differ from point-to-point
       communications is that even if the composition of the group changes,
       the "thread" of communication can still exist.  This contrasts with
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                   [Page 3]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       the point-to-point communication model where, if either of the two
       parties leave, the communication process (exchange of data) is
       terminated (or at least paused).  Depending upon  application goals,
       senders and receivers participating in a reliable  multicast transport
       "session" may be able to join late, leave, and/or  potentially rejoin
       while the ongoing group communication "thread"  still remains
       functional and useful.  Also note that this can impact protocol
       message content.  If "late joiners" are supported, some amount of
       additional information may be placed in  message headers to
       accommodate this functionality.  Alternatively, the information may be
       sent in its own message (on demand or intermittently) if the impact to
       the overhead of typical message transmissions is deemed too great.
       Group dynamics can also impact other protocol mechanisms such as NACK
       timing, congestion control operation, etc.
     
     2.3 Sender/Receiver Relationships
     
       The relationship of senders and receivers among group members requires
       consideration.  In some applications, there may be a single sender
       multicasting to a group of receivers.  In other cases, there may be
       more than one sender or the potential for everyone in the  group to be
       a sender _and_ receiver of data may exist.
     
     2.4 Group Size Scalability
     
       Native IP multicast [5] may scale to extremely large group sizes.  It
       may be desirable for some applications to scale along with the
       multicast infrastructure's ability to scale.  In its simplest form,
       there are limits to the group size to which a NACK-oriented protocol
       can apply without NACK implosion problems.  Research suggests that
       NORM group sizes on the order of tens of thousands of receivers may
       operate with modest feedback to the sender using probablistic, timer-
       based suppression techniques[15].  However, the potential for router
       assistance or other NACK suppression heuristics may enable these
       protocols to scale to very large group sizes.  In large scale cases,
       it may be prohibitive for members to maintain state on all other
       members (in particular, other receivers) in the group.  The impact of
       group size needs to be considered in the development of applicable
       building blocks.
     
     2.5 Data Delivery Performance
     
       There is a trade-off between scalability and data delivery latency
       when designing NACK-oriented protocols.  If probablistic, timer-based
       NACK suppression is to be used, there will be some delays built into
       the NACK process to allow suppression to occur and for the sender of
       data to identify appropriate content for efficient repair
       transmission.  For example, backoff timeouts can be used to ensure
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                   [Page 4]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       efficient NACK suppression and repair transmission, but this comes at
       a cost of increased delivery latency and increased buffering
       requirements for both senders and receivers.  The building blocks
       SHOULD allow applications to establish bounds for data delivery
       performance.  Note that application designers must be aware of the
       scalability trade-off that is made when such bounds are applied.
     
     2.6 Network Environments
     
       The Internet Protocol has historically assumed a role of providing
       service across heterogeneous network topologies.  It is desirable that
       a reliable multicast protocol be capable of effectively operating
       across a wide range of the networks to which general purpose IP
       service applies.  The bandwidth available on the links between the
       members of a single group today may vary between  low numbers of
       kbit/s for wireless links and multiple Gbit/s for high speed LAN
       connections, with varying degrees of contention from other flows.
       Recently, a number of asymmetric network services including 56K/ADSL
       modems, CATV Internet service, satellite and other wireless
       communication services have begun to proliferate.   Many of these are
       inherently broadcast media with potentially large  "fanouts" to which
       IP multicast service is highly applicable.  Additionally, policy
       and/or technical issues may result in topologies where multicast
       connectivity is limited to a single source multicast (SSM) model from
       a specific source [16].  Receivers in the group may be restricted to
       unicast feedback for NACKs and other messages.  Consideration must be
       given, in building block development and protocol design, to the
       nature of the underlying networks.
     
     2.7 Router/Intermediate System Assistance
     
       While intermediate assistance from devices/systems with direct
       knowledge of the underlying network topology may be used to leverage
       the performance and scalability of reliable multicast protocols, there
       will continue to be a number of instances where this is not available
       or practical.  Any building block components for NACK-oriented
       reliable multicast SHALL be capable of operating without such
       assistance.  However, it is RECOMMENDED that such protocols also be
       consider utilizing these features when available.
     
     3.0 Functionality
     
       The previous section has presented the role of protocol building
       blocks and some of the criteria that may affect NORM building block
       identification/design. This section describes different building block
       areas applicable to NORM protocols.  Some of these areas are specific
       to NACK-oriented protocols.  Detailed descriptions of such  areas are
       provided.  In other cases, the areas (e.g., node identifiers, forward
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                   [Page 5]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       error correction (FEC), etc) may be applicable to other forms of
       reliable multicast.  In those cases, the discussion below describes
       requirements placed on those other general building block areas from
       the standpoint of NACK-oriented reliable multicast.  Where applicable,
       other building block documents are referenced for possible
       contribution to NORM protocols.
     
       For each building block, a notional "interface description" is
       provided to illustrate any dependencies of one building block
       component upon another or upon other protocol parameters.  A building
       block component may require some form of "input" from another building
       block component or other source to perform its function.  Any "inputs"
       required by a building block component and/or any resultant "output"
       provided will be defined and described in each building block
       components's interface description.  Note that the set of building
       blocks presented here do not fully satisify each other's "input" and
       "output" needs.  In some cases, "inputs" for the building blocks here
       must come from other building blocks external to this document (e.g.,
       congestion control or FEC).  In other cases NORM building block
       "inputs" must be satisfied by the specific protocol instantiation or
       implementation (e.g., application data and control).
     
       The following building block components relevant to NORM are
       identified:
     
       (NORM-Specific)
            1)   NORM Sender Transmission
            2)   NORM Repair Process
            3)   NORM Receiver Join Policies
     
       (General Purpose)
            4)   Node (member) Identification
            5)   Data Content Identification
            6)   Forward Error Correction (FEC)
            7)   Round-trip Timing Collection
            8)   Group Size Determination/Estimation
            9)   Congestion Control Operation
            10)  Router/Intermediate System Assistance
            11)  Ancillary Protocol Mechanisms
     
       Figure 1 provides a pictoral overview of these building block areas
       and some of their relationships.  For example, the content of the data
       messages that sender initially transmits depends upon the "Node
       Identification", "Data Content Identification", and "FEC" components
       whil the rate of message transmission will generally depend upon the
       "Congestion Control" component.  Subsequently, the receivers' response
       to these transmissions (e.g., NACKing for repair) will depend upon the
       data message content and inputs from other building block components.
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                   [Page 6]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       Finally, the sender's processing of receiver responses will feed back
       into its transmission strategy.
     
                                          Application Data and Control
                                                      |
                                                      v
         .---------------------.            .-----------------------.
         | Node Identification |----------->|  Sender Transmission  |<------.
         `---------------------'       _.-' `-----------------------'       |
         .---------------------.   _.-' .'            | .--------------.    |
         | Data Identification |--'   .''             | |  Join Policy |    |
         `---------------------'    .' '              v `--------------'    |
         .---------------------.  .'  '     .------------------------.      |
      .->| Congestion Control  |-'   '      | Receiver NACK          |      |
      |  `---------------------'   .'       | Repair Process         |      |
      |  .---------------------. .'         | .------------------.   |      |
      |  |        FEC          |'.          | | NACK Initiation  |   |      |
      |  `---------------------'` `._       | `------------------'   |      |
      |  .---------------------. ``. `-._   | .------------------.   |      |
      `--|    RTT Collection   |._` `    `->| | NACK Content     |   |      |
         `---------------------' .`- `      | `------------------'   |      |
         .---------------------.  \ `-`._   | .------------------.   |      |
         |    Group Size Est.  |---.-`---`->| | NACK Suppression |   |      |
         `---------------------'`.  ` `     | `------------------'   |      |
         .---------------------.  `  ` `    `------------------------'      |
         |       Other         |   `  ` `             | .-----------------. |
         `---------------------'    `  ` `            | |Router Assistance| |
                                     `. ` `           v  `----------------' |
                                       `.`' .-------------------------.     |
                                          `>| Sender NACK Processing  |_____/
                                            | and Repair Response     |
                                            `-------------------------'
     
                         ^                         ^
                         |                         |
                       .-----------------------------.
                       |         (Security)          |
                       `-----------------------------'
     
                      Fig. 1 - NORM Building Block Framework
     
       The components on the left side of this figure are areas that may be
       applicable beyond NORM.  The most signficant of these components, FEC
       and Congestion Control, are discussed in other building block
       documents [13], [14], and [17].  A brief description of these areas
       and their role in the NORM protocol is given below.  The components on
       the right are seen as specific to NORM protocols, most notably the
       NACK repair process.   These areas are discussed in detail below.
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                   [Page 7]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       Some other components (e.g., "Security") impact many aspects of the
       protocol, and others such as "Router Assistance" may be more
       transparent to the core protocol processing.  The sections below
       describe the "NORM Sender Transmission", "NORM Repair Process", and
       "RTT Collection" building blocks in detail.  The relationships to and
       among the other building block areas are also discussed, focusing on
       issues applicable to NORM protocol design.  Where applicable, specific
       technical recommendations are made for mechanisms that will properly
       satisfy the goals of NORM transport for the Internet.
     
     3.1 NORM Sender Transmission
     
       NORM senders will transmit data content to the multicast session.  The
       data content will be application dependent.  The sender will transmit
       data content at a rate, and with message sizes, determined by
       application and/or network architecture requirements.  Any FEC
       encoding of sender transmissions SHOULD conform with the guidelines of
       [13].  When congestion control mechanisms are needed (REQUIRED for
       general Internet operation), NORM transmission SHALL be controlled by
       the congestion control mechanism.  In any case, it is RECOMMENDED that
       all data transmissions from  NORM senders be subject to rate
       limitations determined by the application or congestion control
       algorithm.  The sender's transmissions SHOULD make good utilization of
       the available capacity (which may be limited by the application and/or
       by congestion control).  As a result, it is expected there will be
       overlap and multiplexing of new data content transmission with repair
       content.  Other factors related to application operation may determine
       sender transmission formats and methods.  For example, some
       consideration needs to be given to the sender's behavior during
       intermittent idle periods when it has no data to transmit.
     
       In addition to data content, other sender messages or commands may be
       employed as part of protocol operation.  These messages may occur
       outside of the scope of application data transfer.  In NORM protocols,
       reliability of such protocol messages may be attempted by redundant
       transmission when positive acknowledgement is prohibitive due to group
       size scalablity concerns.  Note that protocol design SHOULD provide
       mechanisms for dealing with cases where such messages are not received
       by the group.  As an example, a command message might be redundantly
       transmitted by a sender to indicate that it is temporarily (or
       permanently) halting transmission.  At this time, it may be
       appropriate for receivers to respond with NACKs for any outstanding
       repairs they require following the rules of the NORM NACK procedure.
       For efficiency, the sender should allow sufficient time between the
       redundant transmissions to receive any NACK-oriented responses from
       the receivers to this command.
     
       In general, when there is any resultant NACK or other feedback
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                   [Page 8]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       operation, the timing of redundant transmission of control messages
       issued by a sender and other NORM protocol timeouts should be
       dependent upon the group greatest round trip timing (GRTT) estimate
       and any expected resultant NACK or other feedback operation.  The NORM
       GRTT is an estimate of the worst-case round-trip timing from a sender
       to any receivers in the group.  It is assumed that the GRTT interval
       is a conservative estimate of the maximum span (with respect to delay)
       of the multicast group across a network topology with respect to given
       sender.  NORM instantiations SHOULD be able to dynamically adapt to a
       wide range of multicast network topologies.
     
       Sender Transmission Interface Description:
     
       Inputs:
     
            1)   Application data and control
            2)   Sender node identifier
            3)   Data identifiers
            4)   Segmentation and FEC parameters
            5)   Transmission rate
            6)   Application controls
            7)   Receiver feedback messages (e.g., NACKs)
     
       Outputs:
     
            1)   Controlled transmission of messages with headers uniquely
                 identifying data or repair content within the context of the
                 NORM session.
            2)   Commands indicating sender's status or other transport
                 control actions to be taken.
     
     3.2 NORM Repair Process
     
       A critical component of NORM protocols is the NACK repair process.
       This includes the receiver's role in detecting and requesting repair
       needs, and the sender's response to such requests.  There are four
       primary elements of the NORM repair process:
     
            1)   Receiver NACK process initiation,
            3)   NACK suppression,
            2)   NACK message content,
            4)   Sender NACK processing and response.
     
     3.2.1 Receiver NACK Process Initiation
     
       The NORM NACK process (cycle) will be initiated by receivers that
       detect a need for repair transmissions from a specific sender to
       achieve reliable reception.  When FEC is applied, a receiver should
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                   [Page 9]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       initiate the NACK process only when it is known its repair
       requirements exceed the amount of pending FEC transmission for a given
       coding block of data content.  This can be determined at the end of
       the current transmission block (if it is indicated) or upon the start
       of reception of a subsequent coding block or transmission object.
       This implies the NORM data content is marked to identify its FEC block
       number and that ordinal relationship is preserved in order of
       transmission.
     
       Alternatively, if the sender's transmission advertises the quantity of
       repair packets it is already planning to send for a block, the
       receiver may be able to initiate the NACK processor earlier.  Allowing
       receivers to initiate NACK cycles at any time they detect their repair
       needs have exceeded pending repair transmissions may result in
       slightly quicker repair cycles.  However, it may be useful to limit
       NACK process initiation to specific events such as at the end-of-
       transmission of an FEC coding block or upon detection of subsequent
       coding blocks.  This can allow receivers to aggregate NACK content
       into a smaller number of NACK messages and provide some implicit loose
       synchronization among the receiver set to help facilitate effective
       probabilistic suppression of NACK feedback.  The receiver MUST
       maintain a history of data content received from the sender to
       determine its current repair needs.  When FEC is employed, it is
       expected that the history will correspond to a record of pending or
       partially-received coding blocks.
     
       For probabilistic, timer-base suppression of feedback, the NACK cycle
       should begin with receivers observing backoff timeouts.  In
       conjunction with initiating this backoff timeout, it is important that
       the receivers record the current position in the sender's transmission
       sequence at which they initiate the NACK cycle.  When the suppression
       backoff timeout expires, the receivers should only consider their
       repair needs up to this recorded transmission position in making the
       decision to transmit or suppress a NACK.  Without this restriction,
       suppression is greatly reduced as additional content is received from
       the sender during the time a NACK message propagates across the
       network to the sender and other receivers.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 10]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       Receiver NACK Process Initiation Interface Description:
     
       Inputs:
     
            1)   Sender data content with sequencing identifiers from sender
                 transmissions.
            2)   History of content received from sender.
     
       Outputs:
     
            1)   NACK process initiation decision
            2)   Recorded sender transmission sequence position.
     
     3.2.2 NACK Suppression
     
       An effective NORM feedback suppression mechanism is the use of random
       backoff timeouts prior to NACK transmission by receivers requiring
       repairs[6].  Upon expiration of the backoff timeout, a receiver will
       request repairs unless its pending repair needs have been completely
       superseded by NACK messages heard from other receivers (when receivers
       are multicasting NACKs) or from some indicator from the sender.  When
       receivers are unicasting NACK messages, the sender may facilitate NACK
       suppression by forwarding a representation of NACK content it has
       received to the group at large or provide some other indicator of the
       repair information it will be subsequently transmitting.
     
       For effective and scalable suppression performance, the backoff
       timeout periods used by receivers should be independently, randomly
       picked by receivers with a truncated exponential distribution [7].
       This results in the majority of the receiver set holding off
       transmission of NACK messages under the  assumption that the smaller
       number of "early NACKers" will supersede the repair needs of the
       remainder of the group.  The mean of the distribution should be
       determined as a function of the current estimate of sender<->group
       GRTT and a group size estimate that is determined by other mechanisms
       within the protocol or preset by the multicast application.
     
       A simple algorithm can be constructed to generate random backoff
       timeouts with the appropriate distribution.  Additionally, the
       algorithm may be designed to optimize the backoff distribution given
       the number of receivers (R) potentially generating feedback.  This
       "optimization" minimizes the number of feedback messages (e.g., NACK)
       in the worst-case situation where all receivers generate a NACK. The
       maximum backoff timeout (T_maxBackoff) can be set to control reliable
       delivery latency versus volume of feedback traffic.  A larger value of
       T_maxBackoff will result in a lower density of feedback traffic for a
       given repair cycle.  A smaller value of T_maxBackoff results in
       shorter latency which also reduces the buffering requirements of
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 11]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       senders and receivers for reliable transport.
     
       Given the receiver group size (R), and maximum allowed backoff timeout
       (T_maxBackoff), random backoff timeouts (t') with a truncated
       exponential distribution can be picked with the following  algorithm:
     
            1)   Establish an optimal mean (L) for the exponential backoff
                 based on the group size:
     
                 L = ln(R) + 1
     
            2)   Pick a random number (x) from a uniform distribution over a
                 range of:
     
                        L                           L                   L
                --------------------  to   --------------------  +  ----------
               T_maxBackoff*(exp(L)-1)    T_maxBackoff*(exp(L)-1)  T_maxBackoff
     
            3)   Transform this random variate to generate the desired random
                 backoff time (t') with the following equation:
     
                 t' = T_maxBackoff/L * ln(x * (exp(L) - 1) *
                 (T_maxBackoff/L))
     
       This C language function can be used to generate an appropriate random
       backoff time interval:
     
       double RandomBackoff(double maxTime, double groupSize)
       {
           double lambda = log(groupSize) + 1;
           double x = UniformRand(lambda/maxTime) +
                      lambda / (maxTime*(exp(lambda)-1));
           return ((maxTime/lambda) *
                   log(x*(exp(lambda)-1)*(maxTime/lambda)));
       }  // end RandomBackoff()
     
       where UniformRand(double max) returns random numbers with a uniform
       distribution from the range of 0..max.  For example, based on the
       POSIX "rand()" function, the following C code can be used:
     
       double UniformRand(double max) {return (max * ((double)rand()/(double)RAND_MAX));}
     
       The number of expected NACK messages generated (N) within the first
       round trip time for a single feedback event is approximately:
     
                      N = exp(1.2 * L / (2*T_maxBackoff/GRTT))
     
       Thus the maximum backoff time can be adjusted to tradeoff worst-case
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 12]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       NACK feedback volume versus latency.  This is derived from [7] and
       assumes  T_maxBackoff >= GRTT, and L is the mean of the distribution
       optimized for the given group size as shown in the algorithm above.
       Note that other mechanisms within the protocol may work to reduce
       redundant NACK generation further.  It is suggested that T_maxBackoff
       be selected as an integer multiple of the sender's current advertised
       GRTT estimate such that:
     
                       T_maxBackoff = K * GRTT ;where K >= 1
     
       For general Internet operation, a default value of K=4 is RECOMMENDED
       for operation with multicast (to the group at large) NACK delivery and
       a value of K=6 for unicast NACK delivery.  Alternate values may be
       used to for buffer utliization, reliable delivery latency and group
       size scalability tradeoffs.
     
       Given that (K*GRTT) is the maximum backoff time used by the receivers
       to initiate NACK transmission, other timeout periods related to the
       NACK repair process can be scaled accordingly.  One of those timeouts
       is the amount of time a receiver should wait after generating a NACK
       message before allowing itself to initiate another NACK
       backoff/transmission cycle (T_rcvrHoldoff).  This delay should be
       sufficient for the sender to respond to the received NACK with repair
       messages.  An appropriate value depends upon the amount of time for
       the NACK to reach the sender and the sender to provide a repair
       response.  This MUST include any amount of sender NACK aggregation
       period during which possible multiple NACKs are accumulated to
       determine an efficient repair response.  These timeouts are further
       discussed in the section below on "Sender NACK Processing and Repair
       Response".
     
       There are also secondary measures that can be applied to improve the
       performance of feedback suppression.  For example, the sender's data
       content transmissions can follow an ordinal sequence of transmission.
       When repairs for data content occur, the receiver can note that the
       sender has "rewound" its data content transmission position by
       observing the data object, FEC block number, and FEC symbol
       identifiers. Receivers SHOULD limit transmission of NACKs to only when
       the sender's current transmission position exceeds the point to which
       the receiver has incomplete reception. This reduces premature requests
       for repair of data the sender may be planning to provide in response
       to other receiver requests.  This mechanism can be very effective for
       protocol convergence in high loss conditions when transmissions of
       NACKs from other receivers (or indicators from the sender) are lost.
       Another mechanism (particularly applicable when FEC is used) is for
       the sender to embed an indication of impending repair transmissions in
       current packets sent.  For example, the indication may be as simple as
       an advertisment of the number of FEC packets to be sent for the
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 13]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       current applicable coding block.
     
       Finally, some consideration might be given to using the NACKing
       history of receivers to weight their selection of NACK backoff timeout
       intervals.  For example, if a receiver has historically been
       experiencing the greatest degree of loss, it may promote itself to
       statistically NACK sooner than other receivers.  Note this requires
       there is correlation over successive intervals of time in the loss
       experienced by a receiver.  Such correlation MAY not be present in
       multicast networks.  This adjustment of backoff timeout selection may
       require the creation of an "early NACK" slot for these historical
       NACKers.  This additional slot in the NACK backoff window will result
       in a longer repair cycle process that may not be desirable for some
       applications.  The resolution of these trade-offs may be dependent
       upon the protocol's target application set or network.
     
       After the random backoff timeout has expired, the receiver will make a
       decision on whether to generate a NACK repair request or not (i.e., it
       has been suppressed).  The NACK will be suppressed when any of the
       following conditions has occurred:
     
            1)   The accumulated state of NACKs heard from other receivers
                 (or forwarding of this state by the sender) is equal to or
                 supersedes the repair needs of the local receiver.  Note
                 that the local receiver should consider its repair needs
                 only up to the sender transmission position recorded at the
                 NACK cycle initiation (when the backoff timer was
                 activated).
     
            2)   The sender's data content transmission position "rewinds" to
                 a point ordinally less than that of the lowest sequence
                 position of the local receiver's repair needs. (This
                 detection of sender "rewind" indicates the sender has
                 already responded to other receiver repair needs of which
                 the local receiver may not have been aware).  This "rewind"
                 event can occur any time between 1) when the NACK cycle was
                 initiated with the backoff timeout activation and 2) the
                 current moment when the backoff timeout has expired to
                 suppress the NACK.  Another NACK cycle must be initiated by
                 the receiver when the sender's transmission sequence
                 position exceeds the receiver's lowest ordinal repair point.
                 Note it is possible that the local receiver may have had its
                 repair needs satisfied as a result of the sender's response
                 to the repair needs of other receivers and no further
                 NACKing is required.
     
       If these conditions have not occurred and the receiver still has
       pending repair needs, a NACK message is generated and transmitted.
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 14]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       The NACK should consist of an accumulation of repair needs from the
       receiver's lowest ordinal repair point up to the current sender
       transmission sequence position.  A single NACK message should be
       generated and the NACK message content should be truncated if it
       exceeds the payload size of single protocol message.  When such NACK
       payload limits occur, the NACK content SHOULD contain requests for the
       ordinally lowest repair content needed from the sender.
     
       NACK Suppression Interface Description
     
       Inputs:
     
            1)   NACK process initiation decision.
            2)   Recorded sender transmission sequence position.
            3)   Sender GRTT.
            4)   Sender group size estimate.
            5)   Application-defined bound on backoff timeout period.
            6)   NACKs from other receivers.
            7)   Pending repair indication from sender (may be forwarded
                 NACKs).
            8)   Current sender transmission sequence position.
     
       Outputs:
     
            1)   Yes/no decision to generate NACK message upon backoff timer
                 expiration.
     
     3.2.3 NACK Content
     
       The content of NACK messages generated by reliable multicast receivers
       will include information detailing their current repair needs.  The
       specific information depends on the use and type of FEC in the NORM
       repair process.  The identification of repair needs is dependent upon
       the data content identification (See Section 3.5 below).  At the
       highest level the NACK content will identify the sender to which the
       NACK is addressed and the data transport object (or stream) within the
       sender's transmission that needs repair.  For the indicated transport
       entity, the NACK content will then identify the specific FEC coding
       blocks and/or symbols it requires to reconstruct the complete
       transmitted data.  This content may consist of FEC block erasure
       counts and/or explicit indication of missing blocks or symbols
       (segments) of data and FEC content.  It should also be noted that NORM
       can be effectively instantiated without a requirement for reliable
       NACK delivery using the techniques discussed here.
     
       3.2.3.1 NACK and FEC Repair Strategies
     
       Where FEC-based repair is used, the NACK message content will
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 15]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       minimally need to identify the coding block(s) for which repair is
       needed and a count of erasures (missing packets) for the coding block.
       An exact count of erasures implies the FEC algorithm is capable of
       repairing _any_ loss combination within the coding block.  This count
       may need to be adjusted for some FEC algorithms.  Considering that
       multiple repair rounds may be required to successfully complete
       repair, and erasure count also also implies that the quantity of
       unique FEC parity packets the server has available to transmit is
       essentially unlimited (i.e., the server will always be able to provide
       new, unique, previously unsent parity packets in response to any
       subsequent repair requests for the same coding block).  Alternatively,
       the sender may "round-robin" transmit through its available set of FEC
       symbols for a given coding block, and eventually affect repair.  For a
       most efficient repair strategy, the NACK content will need to also
       _explicitly_ identify which symbols (information and/or parity) the
       receiver requires to successfully reconstruct the content of the
       coding block.  This will be particularly true of small to medium size
       block FEC codes (e.g., Reed Solomon) that are capable of provided a
       limited number of parity symbols per FEC coding block.
     
       When FEC is not used as part of the repair process, or the protocol
       instantiation is required to provide reliability even when the sender
       has transmitted all available parity for a given coding block (or the
       sender's ability to buffer transmission history is exceeded by the
       delay*bandwidth*loss characteristics of the network topology), the
       NACK content will need to contain _explicit_  coding block and/or
       segment loss information so that the sender can provide appropriate
       repair packets and/or data retransmissions.  Explicit loss information
       in NACK content may also potentially serve other purposes.  For
       example, it may be useful for decorrelating loss characteristics among
       a group of receivers to help differentiate candidate congestion
       control bottlenecks among the receiver set.
     
       When FEC is used and NACK content is designed to contain explicit
       repair requests, there is a strategy where the receivers can NACK for
       specific content that will help facilitate NACK suppression and repair
       efficiency.  The assumptions for this strategy are that sender may
       potentially exhaust its supply of new, unique parity packets available
       for a given coding block and be required to explicitly retransmit some
       data or parity symbols to complete reliable transfer.  Another
       assumption is that an FEC algorithm where any parity packet can fill
       any erasure within the coding block (e.g., Reed Solomon) is used.  The
       goal of this strategy is to make maximum use of the available parity
       and provide the minimal amount of data and repair transmissions during
       reliable transfer of data content to the group.
     
       When systematic FEC codes are used, the sender transmits the data
       content of the coding block (and optionally some quantity of parity
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 16]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       packets) in its initial transmission.  Note that a systematic FEC
       coding block is considered to be logically made up of the contiguous
       set of data vectors plus parity vectors for the given FEC algorithm
       used.  For example, a coding scheme that provides for 64 data symbols
       and 32 parity symbols per coding block would contain FEC symbol
       identifiers in the range of 0 to 95.
     
       Receivers then can construct NACK messages requesting sufficient
       content to satisfy their repair needs.  For example, if the receiver
       has three erasures in a given received coding block, it will request
       transmission of the three lowest ordinal parity vectors in the coding
       block. In our example coding scheme from the previous paragraph, the
       receiver would explicitly request parity symbols 64 to 66 to fill its
       three erasures for the coding block.  Note that if the receiver's loss
       for the coding block exceeds the available parity quantity (i.e.,
       greater than 32 missing symbols in our example), the receiver will be
       required to construct a NACK requesting all (32) of the available
       parity symbols plus some additional portions of its missing data
       symbols in order to reconstruct the block.  If this is done
       consistently across the receiver group, the resulting NACKs will
       comprise a minimal set of sender transmissions to satisfy their repair
       needs.
     
       In summary, the rule is to request the lower ordinal portion of the
       parity content for the FEC coding block to satisfy the erasure repair
       needs on the first NACK cycle.  If the available number of parity
       symbols is insufficient, the receiver will also request the subset of
       ordinally highest missing data symbols to cover what the parity
       symbols will not fill.  Note this strategy assumes FEC codes such as
       Reed-Solomon for which a single parity symbol can repair any erased
       symbol.  This strategy would need minor modification to take into
       account the possibly limited repair capability of other FEC types.  On
       subsequent NACK repair cycles where the receiver may have received
       some portion of its previously requested repair content, the receiver
       will use the same strategy, but only NACK for the set of parity and/or
       data symbols it has not yet received.  Optionally, the receivers could
       also provide a count of erasures as a convenience to the sender or
       intermediate systems assisting NACK operation.
     
       After receipt and accumulation of NACK messages during the aggregation
       period, the sender can begin transmission of fresh (previously
       untransmitted) parity symbols for the coding block based on the
       highest receiver erasure count _if_ it has a sufficient quantity of
       parity symbols that were _not_ previously transmitted.  Otherwise, the
       sender MUST resort to transmitting the explicit set of repair vectors
       requested.  With this approach, the sender needs to maintain very
       little state on requests it has received from the group without need
       for synchronization of repair requests from the group.  Since all
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 17]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       receivers use the same consistent algorithm to express their explicit
       repair needs, NACK suppression among receivers is simplified over the
       course of multiple repair cycles.  The receivers can simply compare
       NACKs heard from other receivers against their own calculated repair
       needs to determine whether they should transmit or suppress their
       pending NACK messages.
     
       3.2.3.2 NACK Content Format
     
       The format of NACK content will depend on the protocol's data service
       model and the format of data content identification the protocol uses.
       This NACK format also depends upon the type of FEC encoding (if any)
       is used.  Figure 2 illustrates a logical, hierarchical transmission
       content identification scheme, denoting that the notion of objects (or
       streams) and/or FEC blocking is optional at the protocol
       instantiation's discretion.  Note that the identification of objects
       is with respect to a given sender.  It is recommended that transport
       data content identification is done within the context of a sender in
       a given session. Since the notion of session "streams" and "blocks" is
       optional, the framework degenerates to that of typical transport data
       segmentation and reassembly in its simplest form.
     
     
       Session_
                \_
                   Sender_
                           \_
                              [Object/Stream(s)]_
                                                 \_
                                                    [FEC Blocks]_
                                                                 \_
                                                                    Symbols
     
                Figure 2: NORM Data Content Identification Hierarchy
     
       The format of NACK messages should meet the following goals:
     
            1)   Able to identify transport data unit transmissions required
                 to repair a portion of the received content, whether it is
                 an entire missing object/stream (or range), entire FEC
                 coding block(s), or sets of symbols,
     
            2)   Be simple to process for NACK aggregation and suppression,
     
            3)   Be capable of including NACKs for multiple objects, FEC
                 coding blocks and/or symbols in a single message.  FEC
                 erasure counts may also be desirable.
     
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 18]


     Internet Draft            NORM Building Blocks              October 2003
     
     
            4)   Have a reasonably compact format, and
     
            5)   Be capable of working with the Generic Router Assist (GRA)
                 building block.
     
       If the NORM transport object/stream is identified with an <objectId>
       and the FEC symbol being transmitted is identified with and
       <fecPayloadId>, the concatenation of <objectId::fecPayloadId>
       comprises a basic transport protocol data unit (TPDU) identifier for
       symbols from a given source.  NACK content can be composed of lists
       and/or ranges of these TPDU identifiers to build up NACK messages to
       describe the receivers repair needs.  If no hierarchical object
       delineation or FEC blocking is used, the TPDU is a simple linear
       representation of the data symbols transmitted by the sender.  When
       the TPDU represents a hierarchy for purposes of object/stream
       delineation and/or FEC blocking, the NACK content unit may require
       flags to indicate which portion of the TPDU is applicable.  For
       example, if an entire "object" (or range of objects) is missing in the
       received data, the receiver will not necessarily know the appropriate
       range of <sourceBlockNumbers> or <encodingSymbolIds> for which to
       request repair and thus requires some mechanism to request repair (or
       retransmission) of the entire unit represented by an <objectId>.  The
       same is true if entire FEC coding blocks represented by one or a range
       of <sourceBlockNumbers> have been lost.
     
       NACK Content Interface Description
     
       Inputs:
     
            1)   Sender identification.
            2)   Sender data identification.
            3)   Sender FEC Object Transmission Information.
            4)   Recorded sender transmission sequence position.
            5)   Current sender transmission sequence position.
            5)   History of repair needs for this sender.
     
       Outputs:
     
            1)   NACK message with repair requests.
     
     3.2.4 Sender Repair Response
     
       Upon reception of a repair request from a receiver in the group, the
       sender will initiate a repair response procedure.  The sender may wish
       to delay transmission of repair content until it has had  sufficient
       time to accumulate potentially multiple NACKs from the  receiver set.
       This allows the sender to determine the most efficient repair strategy
       for a given transport stream/object or FEC coding block.  Depending
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 19]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       upon the approach used, some protocols may find it beneficial for the
       sender to provide an indicator of pending repair transmissions as part
       of the its current transmitted message content.  This can aid some
       NACK suppression mechanisms.  The amount of time to perform this NACK
       aggregation should be sufficient to allow for the maximum receiver
       NACK backoff window ("T_maxBackoff" from Section 3.2.2) and
       propagation of NACK messages from the receivers to the sender.  Note
       the maximum transmission delay of a message from a receiver to the
       sender may be approximately (1*GRTT) in the case of very asymmetric
       network topology with respect to transmission delay.  Thus, if the
       maximum receiver NACK backoff time is T_maxBackoff = K*GRTT, the
       sender NACK aggregation period should be equal to at least:
     
                T_sndrAggregate = T_maxBackoff + 1*GRTT = (K+1)*GRTT
     
       Immediately after the sender NACK aggregration period, the sender will
       begin transmitting repair content determined from the aggregate NACK
       state and continue with any new transmission.  Also, at this time, the
       sender should observe a "holdoff" period where it constrains itself
       from initiating a new NACK aggregation period to allow propagation of
       the new transmission sequence position due to the repair response to
       the receiver group.  To allow for worst case asymmetry, this "holdoff"
       time should be:
     
                               T_sndrHoldoff = 1*GRTT
     
       Recall that the receivers will also employ a "holdoff" timeout after
       generating a NACK message to allow time for the sender's response.
       Given a sender <T_sndrAggregate> plus <T_sndrHoldoff> time of
       (K+1)*GRTT, the receivers should use holdoff timeouts of:
     
            T_rcvrHoldoff = T_sndrAggregate + T_sndrHoldoff = (K+2)*GRTT
     
       This allows for a worst-case propagation time of the receiver's NACK
       to the sender, the sender's aggregation time and propagation of the
       sender's response back to the receiver.  Additionally, in the case of
       unicast feedback from the receiver set, it may be useful for the
       sender to forward (via multicast) a representation of its aggregated
       NACK content to the group to allow for NACK suppression when there is
       not multicast connectivity among the receiver set.
     
       At the expiration of the <T_sndrAggregate> timeout, the sender will
       begin transmitting repair messages according to the accumulated
       content of NACKs received.  There are some guidelines with regards to
       FEC-based repair and the ordering of the repair response from the
       sender that can improve reliable multicast efficiency:
     
            1)   When FEC is used, it is beneficial that the sender transmit
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 20]


     Internet Draft            NORM Building Blocks              October 2003
     
     
                 previously untransmitted parity content as repair messages
                 whenever possible.  This  maximizes the receiving nodes'
                 ability to reconstruct the entire transmitted content from
                 their individual subsets of received messages.
     
            2)   The transmitted object and/or stream data and repair content
                 should be indexed with  monotonically increasing sequence
                 numbers (within a reasonably large ordinal space).  If the
                 sender observes the discipline of  transmitting repair for
                 the earliest content (e.g., ordinally lowest FEC blocks)
                 first, the receivers can use a strategy of witholding repair
                 requests for later content until the sender once again
                 returns to that point in the object/stream transmission
                 sequence.  This can increase overall message efficiency
                 among the group and help work to keep repair cycles
                 relatively synchronized without dependence upon strict time
                 synchronization among the sender and receivers.  This also
                 helps minimize the buffering requirements of receivers and
                 senders and reduces redundant transmission of data to the
                 group at large.
     
       Sender Repair Response Interface Description
     
       Inputs:
     
            1)   Receiver NACK messages
            2)   Group timing information
     
       Outputs:
     
            1)   Repair messages (FEC and/or Data content retransmission)
            1)   Advertisement of current pending repair transmissions when
                 unicast receiver feedback is detected.
     
     3.3 NORM Receiver Join Policies and Procedures
     
       Consideration should be given to the policies and procedures by which
       new receivers join a group (perhaps where reliable transmission is
       already in progress) and begin requesting repair. If receiver joins
       are unconstrained, the dynamics of group membership may impede the
       application's ability to meet its goals for forward progression of
       data transmission.  Policies limiting the opportunities when receivers
       begin participating in the NACK process may be used to achieve the
       desired behavior.  For example, it may be beneficial for receivers to
       attempt reliable reception from a newly-heard sender only upon non-
       repair transmissions of data in the first FEC block of an object or
       logical portion of a stream.  The sender may also implement policies
       limiting the receivers from which it will accept NACK requests, but
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 21]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       this may be prohibitive for scalability reasons in some situations.
       Alternatively, it may be desirable to have a looser transport
       synchronization policy and rely upon session management mechanisms to
       limit group dynamics that can cause poor performance , in some types
       of bulk transfer applications (or for potential interactive reliable
       multicast applications).
     
       Group Join Policy Interface Description
     
       Inputs:
     
            1)   Current object/stream data/repair content and sequencing
                 identifiers from sender transmissions.
     
       Outputs:
     
            1)   Receiver yes/no decision to begin receiving and NACKing for
                 reliable reception of data
     
     3.4 Reliable Multicast Member Identification
     
       In a NORM protocol (or other multicast protocols) where there is the
       potential for multiple sources of data, it is necessary to provide
       some mechanism to uniquely identify the sources (and possibly some or
       all receivers in some cases) within the group.  Identity based on
       arriving packet source addresses is insufficient for several reasons.
       These reasons include routing changes for hosts with multiple
       interfaces that result in different packet source addresses for a
       given host over time, network address translation (NAT) or firewall
       devices, or other transport/network bridging approaches.  As a result,
       some type of unique source identifier <sourceId> field should be
       present in packets transmitted by reliable multicast session members.
     
     3.5 Data Content Identification
     
       The data and repair content transmitted by a NORM sender requires some
       form of identification in the protocol header fields.  This
       identification is required to facilitate the reliable NACK-oriented
       repair process.  These identifiers will also be used in NACK messages
       generated.  This building block document assumes two very general
       types of data that may comprise bulk transfer session content.  One
       type is static, discrete objects of  finite size and the other is
       continuous non-finite streams.  A given application  may wish to
       reliably multicast data content using either one or both of these
       paradigms.  While it may be possible for some applications to further
       generalize this model and provide mechanisms to encapsulate static
       objects as content embedded within a stream, there are advantages in
       many applications to provide distinct support for static bulk objects
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 22]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       and messages with the context of a reliable multicast session.  These
       applications may include content caching servers, file transfer, or
       collaborative tools with bulk content.  Applications with requirements
       for these static object types can then take advantage of transport
       layer mechanisms (i.e., segmentation/reassembly, caching, integrated
       forward error correction coding, etc) rather than being required to
       provide their own mechanisms for these functions at the application
       layer.
     
       As noted, some applications may alternatively desire to transmit bulk
       content in the form of one or more streams of non-finite size.
       Example streams include continuous quasi-realtime message broadcasts
       (e.g., stock ticker) or some content types that are part of
       collaborative tools or other more complex applications.  And, as
       indicated above, some applications may wish to encapsulate other bulk
       content (e.g., files) into one or more streams within a multicast
       session.
     
       The components described within this building block draft document are
       envisioned to be applicable to both of these models with the
       potential for a mix of both types within a single multicast session.
       To support this requirement, the normal data content identification
       should include a field to uniquely identify the object or stream
       <objectId> within some reasonable temporal or ordinal interval.  Note
       that it is _not_ expected that this data content identification will
       be globally unique.  It is expected that the object/stream identifier
       will be unique with respect to a given sender within the reliable
       multicast session and during the time that sender is supporting a
       specific transport instance of that object or stream.
     
       Since the "bulk" object/stream content usually requires segmentation,
       some form of segment identification must also be  provided.  This
       segment identifier will be relative to any object or stream identifier
       that has been provided.  Thus, in some cases, NORM protocol
       instantiations may be able to receive  transmissions and request
       repair for multiple streams and one or more sets of static objects in
       parallel.  For protocol instantiations employing FEC the segment
       identification portion of the data content identifier may consist of a
       logical concatenation of a coding block identifier <sourceBlockNumber>
       and an identifer for the specific data or parity symbol
       <endcodingSymbolId> of the code block.  The FEC Building Block
       document [13] provides a standard message format for identifying FEC
       transmission content. NORM protocol instantiations using FEC SHOULD
       follow that document's guidelines.
     
       Additionally, flags to determine the usage of the content identifier
       fields (e.g., stream vs. object) may be applicable.   Flags may also
       serve other purposes in data content identification.  It is expected
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 23]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       that any flags defined will be dependent upon individual protocol
       instantiations.
     
       In summary, the following data content identification fields may be
       required for NORM protocol data content messages:
     
            1)   Source node identifier (<sourceId>)
            2)   Object/Stream identifier (<objectId>), if applicable.
            3)   FEC Block identifier (<sourceBlockNumber>), if applicable.
            4)   FEC Symbol identifier (<encodingSymbolId>)
            5)   Flags to differentiate interpretation of identifier fields
                 or identifier structure that implicitly indicates usage.
            6)   Additional FEC transmission content fields per FEC Building
                 Block
     
       These fields have been identified because any generated NACK messages
       will use these identifiers in requesting repair or retransmission of
       data.  NORM protocols that use these data content fields should also
       be compatible with support for intermediate system assistance to
       reliable multicast transport operation when available.
     
     3.6 Forward Error Correction (FEC)
     
       Multiple forward error correction (FEC) approaches have been
       identified that can provide great performance enhancements to the
       repair process of NACK-oriented and other reliable multicast protocols
       [9],[13].  NORM protocols can reap additional benefits since FEC-based
       repair does not _generally_ require explicit knowledge of repair
       content within the bounds of its coding block size (in symbols).  In
       NORM, parity repair packets generated will generally be transmitted
       only in response to NACK repair requests from receiving nodes.
       However, there are benefits in some network environments for
       transmitting some predetermined quantity of FEC repair packets
       multiplexed with the regular data symbol transmissions [8].   This can
       reduce the amount of NACK traffic generated with relatively  little
       overhead cost when group sizes are very large or the network
       connectivity has a large delay*bandwidth product with some nominal
       level of expected packet loss.  While the application of FEC is not
       unique to NORM, these sorts of requirements may dictate the types of
       algorithms and protocol approaches that are applicable.
     
       A specific issue related to the use of FEC with NORM is the mechanism
       used to identify which portion(s) of transmitted data content to which
       specific FEC packets are applicable.  It is expected that FEC
       algorithms will be based on generating a set of parity repair packets
       for a corresponding block of transmitted data packets.  Since data
       content packets are uniquely identified by the concatenation of
       <sourceId::objectId::sourceBlockNumber::encodingSymbolId> during
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 24]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       transport, it is expected that FEC packets will be identified in a
       similar manner.  The FEC Building Block specification [13] provides
       detailed recommendations concerning application of FEC and standard
       formats for related reliable multicast protocol messages.
     
     3.7 Round-trip Timing Collection
     
       The measurement of packet propagation round-trip time (RTT) among
       members of the group is required to support timer-based NACK
       suppression algorithms, timing of sender commands or certain repair
       functions, and congestion control operation.  The nature of the round-
       trip information collected is dependent upon the type of interaction
       among the members of the group.  In the case where only "one-to-many"
       transmission is required, it may be that only the sender require RTT
       knowledge of the greatest RTT (GRTT) among the receiver set and/or RTT
       knowledge of only a portion of the group.  Here, the GRTT information
       might be collected in a reasonably scalable manner.  For congestion
       control operation, it is possible that RTT information may be required
       by each receiver in the group.  In this case, an alternative RTT
       collection scheme may be utilized where receivers collect individual
       RTT measurements with respect to the sender and advertise them to the
       group or sender.  Where it is likely that exchange of reliable
       multicast data will occur among the group on a "many-to-many" basis,
       there are alternative measurement techniques that might be employed
       for increased efficiency [12].  And in some cases, there might be
       absolute time synchronization among hosts that may simplify RTT
       measurement.  There are trade-offs in multicast congestion control
       design that require further consideration before a universal
       recommendation on RTT (or GRTT) measurement can be specified.
       Regardless of how the RTT information is collected (and more
       specifically GRTT) with respect to congestion control or other
       requirements, the sender will need to advertise its current GRTT
       estimate to the group for various timeouts used by receivers.
     
     3.7.1 One-to-Many Sender GRTT Measurement
     
       The goal of this form of RTT measurement is for the sender to learn
       the GRTT among the receivers who are actively participating in NORM
       operation.  The set of receivers participating in this process may be
       the entire group or some subset of the group determined from another
       mechanism within the protocol instantiation.  An approach to collect
       this GRTT information follows.
     
       The sender periodically polls the group with a message (independent or
       "piggy-backed" with other transmissions) containing a <sendTime>
       timestamp relative to an internal clock at the sender.  Upon reception
       of this message, the receivers will record this <sendTime> timestamp
       and the time (referenced to their own clocks) at which it was received
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 25]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       <recvTime>.  When the receiver provides feedback to the sender (either
       explicitly or as part of other feedback messages depending upon
       protocol instantiaon specification), it will construct a "response"
       using the formula:
     
                 grttResponse = sendTime + (currentTime - recvTime)
     
       where the <sendTime> is the timestamp from the last probe message
       received from the source and the (currentTime - <recvTime) is the
       amount of time differential since that request was received until the
       receiver generated the response.
     
       The sender processes each receiver response by calculating a current
       RTT measurement for the receiver from whom the response was received
       using the following formula:
     
                       RTT_rcvr = currentTime - grttResponse
     
       During the each periodic GRTT probing interval, the source keeps the
       peak round trip timing measurement (RTT_peak) from the set of
       responses it has received.  A conservative estimate of GRTT is kept to
       maximize the efficiency redundant NACK suppression and repair
       aggregation.  The update to the source's ongoing estimate of GRTT is
       done observing the following rules:
     
            1)   If a receiver's response round trip time (RTT_rcvr) is
                 greater than the current GRTT estimate, the GRTT is
                 immediately updated to this new peak value:
     
                                       GRTT = RTT_rcvr
     
            2)   At the end of the response collection period (i.e., the GRTT
                 probe interval), if the recorded "peak" response RTT_peak)
                 is less than the current GRTT estimate, the GRTT is updated
                 to:
     
                                GRTT = MAX(0.9*GRTT, RTT_peak)
     
            3)   If no feedback is received, the sender GRTT estimate remains
                 unchanged.
     
            4)   At the end of the response collection period, the peak
                 tracking value (RTT_peak) is reset to ZERO for subsequent
                 peak detection.
     
       The GRTT collection period (i.e., period of probe transmission) could
       be fixed at a value on the order of that expected for group membership
       and/or network topology dynamics.  For robustness, more rapid probing
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 26]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       could be used at protocol startup before settling to a less frequent,
       steady-state interval.  Optionally, an algorithm may be developed to
       adjust the GRTT collection period dynamically in response to the
       current GRTT estimate (or variations in it) and to an estimation of
       packet loss.  The overhead of probing messages could then be reduced
       when the GRTT estimate is stable and unchanging, but be adjusted to
       track more dynamically during periods of variation with
       correspondingly shorter GRTT collection periods.  GRTT collection may
       also be coupled with collection of other information for congestion
       control purposes.
     
       In summary, although NORM repair cycle timeouts are based on GRTT, it
       should be noted that convergent operation of the protocol does not
       _strictly_ depend on highly accurate GRTT estimation.  The current
       mechanism has proved sufficient in simulations and in the environments
       where NORM-like protocols have been deployed to date.  The estimate
       provided by the algorithm tracks the peak envelope of actual GRTT
       (including operating system effect as well as network delays) even in
       relatively high loss connectivity.  The steady-state probing/update
       interval may potentially be varied to accommodate different levels of
       expected network dynamics in different environments.
     
     3.7.2 One-to-Many Receiver RTT Measurement
     
       In this approach, receivers send messages with timestamps to the
       sender.  To control the volume of these receiver-generated messages, a
       suppression mechanism similar to that described for NACK suppression
       my be used.  The "age" of receivers' RTT measurement should be kept by
       receivers and used as a metric in competing for feedback opportunities
       in the suppression scheme.  For example, receiver who have not made
       any RTT measurement or whose RTT measurement has aged most should have
       precedence over other receivers.  In turn the sender may have limited
       capacity to provide an "echo" of the receiver timestamps back to the
       group, and it could use this RTT "age" metric to determine which
       receivers get precedence.  The sender can determine the GRTT as
       described in 3.7.1 if it provides sender timestamps to the group.
       Alternatively, receivers who note their RTT is greater than the sender
       GRTT can compete in the feedback opportunity/suppression scheme to
       provide the sender and group with this information.  It should be
       noted that the TFMCC Congestion Control building block described a
       similar approach to receiver RTT measurement as part of its congestion
       control operation [14].
     
     
     
     
     
     
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 27]


     Internet Draft            NORM Building Blocks              October 2003
     
     
     3.7.3 Many-to-Many RTT Measurement
     
       For reliable multicast sessions that involve multiple senders, it may
       be useful to have RTT measurements occur on a true "many-to-many"
       basis rather than have each sender independently tracking RTT.  Some
       protocol efficiency can be gained when receivers can infer an
       approximation of their RTT with respect to a sender based on RTT
       information they have on another sender and that other sender's RTT
       with respect to the new sender of interest.  For example, for receiver
       "a" and sender's "b" and "c", it is likely that:
     
                       RTT(a<->b) <= RTT(a<->c)) + RTT(b<->c)
     
       Further refinement of this estimate can be conducted if RTT
       information is available to a node concerning its own RTT to a small
       subset of other group members and RTT information among those other
       group members it learns during protocol operation.
     
     3.7.4 Sender GRTT Advertisement
     
       To facilitate deterministic NORM protocol operation, the sender should
       robustly advertise its current estimation of GRTT to the receiver set.
       Common, robust knowledge of the sender's current operating GRTT
       estimate among the group will allow the protocol to progress in its
       most efficient manner.  The sender's GRTT estimate can be robustly
       advertised to the group by simply embedding the estimate into all
       pertinent messages transmitted by the sender.  The overhead of this
       can be made quite small by quantizing (compressing) the GRTT estimate
       to a single byte of information.  The following C-lanquage functions
       allows this to be done over a wide range (RTT_MIN through RTT_MAX) of
       GRTT values while maintaining a greater range of precision for small
       GRTT values and less precision for large values.  Values of 1.0e-06
       seconds and 1000 seconds are RECOMMENDED for RTT_MIN and RTT_MAX
       respectively.  NORM applications may wish to place an additional,
       smaller upper limit on the GRTT advertised by senders to meet
       application data delivery latency constraints at the expense of
       greater feedback volume in some network environments.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 28]


     Internet Draft            NORM Building Blocks              October 2003
     
     
               unsigned char QuantizeGrtt(double grtt)
               {
                   if (grtt > RTT_MAX)
                       grtt = RTT_MAX;
                   else if (grtt < 1.0e-06)
                       grtt = RTT_MIN;
                   if (grtt < (33*RTT_MIN))
                       return ((unsigned char)(grtt * RTT_MIN) - 1);
                   else
                       return ((unsigned char)(ceil(255.0.-
                                               (13.0 * log(RTT_MAX/grtt)))));
               }
     
               double UnquantizeRtt(unsigned char qrtt)
               {
                    return ((qrtt < 31) ?
                    (((double)(qrtt+1))/(double)RTT_MIN) :
                        (RTT_MAX/exp(((double)(255-qrtt))/(double)13.0)));
               }
     
       Note that this function is useful for quantizing GRTT times in the
       range of 1 microsecond to 1000 seconds.  Of course, NORM protocol
       implementations may wish to further constrain advertised GRTT
       estimates (e.g., limit the maximum value) for practical reasons.
     
     3.8 Group Size Determination/Estimation
     
       When NORM protocol operation includes mechanisms that excite feedback
       from the group at large (e.g., congestion control), it may be possible
       to roughly estimate the group size based on the number of feedback
       messages received with respect to the distribution of the
       probabilistic suppression mechanism used.  Note the timer-based
       suppression mechanism described in this document does not require a
       very accurate estimate of group size to perform adequately.  Thus, a
       rough estimate, particularly if conservatively managed, may suffice.
       Group size may also be determined administratively.  In absence of a
       group size determination mechanism a default group size value of
       10,000 is RECOMMENDED for  reasonable management of feedback given the
       scalability of expected NORM usage.
     
     3.9 Congestion Control Operation
     
       Congestion control that fairly shares available network capacity  with
       other reliable multicast and TCP instantiations is REQUIRED for
       general Internet operation.  The TCP-Friendly Multicast Congestion
       Control [14]  or PGMCC specification [17] may be applied to NORM
       operation to meet this requirement.
     
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 29]


     Internet Draft            NORM Building Blocks              October 2003
     
     
     3.10 Router/Intermediate System assistance
     
       NACK-oriented protocols may benefit from general purpose router
       assistance.  In particular, additional NACK suppression where routers
       or intermediate systems can aggregate NACK content (or filter
       duplicate NACK content) from receivers as it is relayed toward the
       sender could enhance NORM group size scalability.  For NORM protocols
       using FEC, it is possible that intermediate systems may be able to
       filter FEC repair messages to provide an intelligent "subcast" of
       repair content to different legs of the multicast toplogy depending on
       the repair needs learned from previous receiver NACKs.  Both of these
       types of Generic Router Assist (GRA) functions would require router
       interpretation of transport data unit content identifiers and flags.
       Additionally, the GRA router should observe NACK repair process
       timeouts based on the NORM sender's GRTT advertisement.
     
     4.0 NORM Applicability
     
       The NORM building block applies to protocols wishing to employ
       negative acknowledgement to achieve reliable data transfer.  Properly
       designed negative-acknowledgement (NACK)-oriented reliable multicast
       (NORM) protocols offer scalability advantages for applications and/or
       network topologies where, for various reasons, it is prohibitive to
       construct a higher order  delivery infrastructure above the basic
       Layer 3 IP multicast service (e.g., unicast or hybrid
       unicast/multicast data distribution trees).  Additionally, the
       scalability property of NACK-oriented protocols [2, 3] is applicable
       where broad "fanout" is expected for a single network hop (e.g.,
       cable-TV data delivery, satellite, or other broadcast communication
       communication services).  Furthermore, the simplicity of a protocol
       based on "flat" group-wide multicast distribution may offer advantages
       for a broad range of distributed services or dynamic networks and
       applications.  NORM protocols can make use of reciprocal (among
       senders and receivers) multicast communication under the Any-Source
       Multicast (ASM) model defined in RFC 1112 [5], and are capable of
       scalable operation in asymmetric topologies such as Single-Source
       Multicast (SSM) [16] where there may only be unicast routing service
       from the receivers to the sender(s).
     
       NORM operation is compatible with transport layer forward error
       correction coding techniques as described in [18] and congestion
       control mechanisms described in [14] and [17].  A principle limitation
       of NORM operation involves group size scalability when network
       capacity for receiver feedback is very limited.  NORM operation is
       also governed by implementation buffering constraints.  Buffering
       greater than that required for typical point-to-point reliable
       transport (e.g., TCP) is recommended to allow for disparity in the
       receiver group connectivity and to allow for the feedback delays
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 30]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       required to attain group size scalability.
     
     5.0 Security Considerations
     
       NORM protocols are expected to be subject to same sort of security
       vulnerabilities as other IP and IP multicast protocols.  NORM is
       compatible with IP security (IPSEC) authentication mechanisms [19]
       that are RECOMMENDED for protection against session intrusion and
       denial of service attacks.  A particular threat for NACK based
       protocols is that of NACK replay attacks that would prevent a NORM
       sender from making forward progress in transmission.  Any standard
       IPSEC mechanisms that can provide protection against such replay
       attacks are RECOMMENDED for use.  Additionally, NORM protocol
       instantiations SHOULD consider providing support for their own NACK
       replay attack protection when network layer mechanisms are not
       available.
     
     6.0 Acknowledgements (and these are not Negative)
     
       The authors would like to thank Rick Jones, and Joerg Widmer for their
       valuable comments on this document.  The authors would also like to
       thank the RMT working group chairs, Roger Kermode and Lorenzo
       Vicisano, for their support in development of this specification, and
       Sally Floyd for her early inputs into this document.
     
     7.0 References
     
     
        [1]      A. Mankin, A. Romanow, S.  Bradner, V.  Paxson, "IETF
                 Criteria for Evaluating Reliable Multicast Transport and
                 Application Protocols", RFC 2357, June 1998.
     
        [2]      S. Pingali, D. Towsley, J.  Kurose, "A Comparison of Sender-
                 Initiated and Receiver-Initiated Reliable Multicast
                 Protocols".  In Proc.  INFOCOM, San Francisco, CA, October
                 1993.
     
        [3]      B.N. Levine, J.J. Garcia-Luna-Aceves, "A Comparison of Known
                 Classes of Reliable Multicast Protocols", Proc.
                 International Conference on Network Protocols (ICNP-96),
                 Columbus, Ohio, Oct 29--Nov 1, 1996.
     
        [4]      D. Clark, D. Tennenhouse, "Architectural Considerations for
                 a New Generation of Protocols".  In Proc.  ACM SIGCOMM,
                 pages 201--208, September 1990.
     
     
     
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 31]


     Internet Draft            NORM Building Blocks              October 2003
     
     
        [5]      S.  Deering, "Host Extensions for IP Multicasting". Internet
                 RFC1112, August 1989.
     
        [6]      S. Floyd, V.  Jacobson, S.  McCanne, C.  Liu, and L.  Zhang.
                 "A Reliable Multicast Framework for Light-weight Sessions
                 and Application Level Framing", Proc.  ACM SIGCOMM, August
                 1995.
     
        [7]      J. Nonnenmacher and E. W. Biersack, "Optimal Multicast
                 Feedback," in IEEE Infocom , (San Francisco, California), p.
                 964, March/April 1998.
     
        [8]      D. Gossink, J.  Macker, "Reliable Multicast and Integrated
                 Parity Retransmission with Channel Estimation", IEEE
                 GLOBECOM 98'.
     
        [9]      J. Metzner, "An Improved Broadcast Retransmission Protocol",
                 IEEE Transactions on Communications, Vol.  Com-32, No.6,
                 June 1984.
     
       [10]      J. Macker, "Integrated Erasure-Based Coding for Reliable
                 Multicast Transmission", IRTF Meeting presentation, March
                 1997.
     
       [11]      J. Macker, "Reliable Multicast Transport and Integrated
                 Erasure-based Forward Error Correction", Proc. IEEE MILCOM
                 97, October  1997.
     
       [12]      V. Ozdemir, S. Muthukrishnan, I. Rhee, "Scalable, Low-
                 Overhead Network Delay Estimation", NCSU/AT&T White Paper,
                 February 1999.
     
       [13]      M. Luby, L. Vicisano, J. Gemmell, L. Rizzo, M. Handley, and
                 J. Crowcroft, "Forward Error Correction (FEC) Building
                 BLock", RFC 3452, December 2002.
     
       [14]      J. Widmer, M. Handley, "TCP-Friendly Multicast Congestion
                 Control (TFMCC) Protocol Specification", Internet Draft
                 draft-ietf-rmt-bb-tfmcc-01.txt, November 2002, work in
                 progress.  Citation for informational purposes only.
     
       [15]      J. Macker, R. Adamson, "Quantitative Prediction of Nack
                 Oriented Reliable Multicast (NORM) Feedback", Proc. IEEE
                 MILCOM 2002, October 2002.
     
     
     
     
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 32]


     Internet Draft            NORM Building Blocks              October 2003
     
     
       [16]      Holbrook, H. W., "A Channel Model for Multicast", Ph.D.
                 Dissertation, Stanford University, Department of Computer
                 Science, Stanford, California, August 2001.
     
       [17]      Rizzo, L., Vicisano, L, Handley, M, "PGMCC Single Rate
                 Multicast Congestion Control Protocol Specification",
                 Internet Draft draft-ietf-rmt-bb-pgmcc-01.txt, June 2002,
                 work in progress.  Citation for informational purposes only.
     
       [18]      Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M.
                 and J. Crowcroft, "The Use of Forward Error Correction (FEC)
                 in Reliable Multicast", RFC 3453, December 2002.
     
       [19]      S. Kent and R. Atkinson, "Security Architecture for the
                 Internet Protocol", RFC 2401, November 1998.
     
     
     
     8.0 Authors' Addresses
     
       Brian Adamson
       adamson@itd.nrl.navy.mil
       Naval Research Laboratory
       Washington, DC, USA, 20375
     
       Carsten Bormann
       cabo@tellique.de
       Tellique Kommunikationstechnik GmbH
       Gustav-Meyer-Allee 25 Geb ude 12
       D-13355 Berlin, Germany
     
       Mark Handley
       mjh@aciri.org
       1947 Center Street, Suite 600
       Berkeley, CA 94704
     
       Joe Macker
       macker@itd.nrl.navy.mil
       Naval Research Laboratory
       Washington, DC, USA, 20375
     
     
     
     
     
     
     
     
     
     
     
     Adamson, Bormann, et al.   Expires April 2004                  [Page 33]
     

Html markup produced by rfcmarkup 1.129b, available from https://tools.ietf.org/tools/rfcmarkup/