[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
INTERNET DRAFT                                                  Tie Liao
Expires: 13 April 1999                                             INRIA
                                                         13 October 1998



         Light-weight Reliable Multicast Protocol Specification
                      draft-liao-lrmp-00.txt


Status of this memo

   This document is an Internet-Draft.  Internet-Drafts are working
   documents of the Internet Engineering Task Force (IETF), its areas,
   and its working groups.  Note that other groups may also distribute
   working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is not appropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress".

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


Abstract
   This document describes LRMP, the Light-weight Reliable Multicast
   Protocol. LRMP provides a minimum set of functions for end-to-end
   reliable network transport suitable for bulk data transfer to
   multiple receivers. LRMP is designed to work in heterogeneous
   network environments and support multiple data senders. A totally
   distributed control scheme is used for error recovery so that no
   prior configuration and no router support are required. LRMP also
   includes a selective feedback mechanism allowing to monitor the
   quality of service at receivers. In LRMP, flow and congestion
   control is performed based on NACK packets and congestion indication
   from receivers. Forward error correction is supported as an
   independent optional module.









Liao                                                            [Page 1]


INTERNET-DRAFT             LRMP                          13 October 1998


Table of Contents

   1.     Introduction ............................................    3
   1.1    Application Scope .......................................    3
   1.2    Overview ................................................    4
   1.3    Implementation ..........................................    6
   2.     Definitions .............................................    7
   3.     Packet Types and Common Header Fields ...................    8
   4.     Data Transmission .......................................   11
   4.1    Reliable Data Transmission ..............................   11
   4.2    Unreliable Data Transmission ............................   12
   5.     Packet Loss Recovery ....................................   12
   5.1    Organization of Subgroups ...............................   13
   5.2    Enabling/disabling a Subgroup ...........................   14
   5.3    Error Report ............................................   15
   5.4    Duplicate NACK Detection ................................   17
   5.5    Retransmission ..........................................   18
   5.6    Reception Failure .......................................   20
   5.7    Mean Round Trip Time Estimation .........................   21
   6.     Sender and Receiver Reports .............................   23
   6.1    Sender Report ...........................................   23
   6.2    Selective Receiver Report ...............................   23
   7.     Flow and Congestion Control .............................   25
   7.1    Transmission Rate .......................................   26
   7.2    Congestion Control ......................................   26
   7.2.1  Adaptation to the Loss  .................................   26
   7.2.2  Adaptation to the Congestion Indication from Receivers ..   27
   7.2.3  Getting to the Equilibrium: Rate Increase ...............   28
   7.3    The Case of Heterogeneous Receivers .....................   28
   8.     Packet Formats ..........................................   29
   8.1    Unreliable Data .........................................   29
   8.2    Reliable Data ...........................................   29
   8.3    Retransmission Data .....................................   30
   8.4    FEC Redundant Data ......................................   31
   8.5    Error Report ............................................   31
   8.6    NACK Reply ..............................................   32
   8.7    Sender Report ...........................................   33
   8.8    Receiver Report Selection ...............................   34
   8.9    Receiver Report .........................................   35
   9.     Options for Forward Error Correction ....................   36
   9.1    Parameters ..............................................   37
   9.2    Packet Format ...........................................   37
   10.    Security Considerations .................................   38
   A.     Requirements of RFC 2357 ................................   40
   B.     References ..............................................   43
   C.     Acknowledgments .........................................   45
   D.     Author's Address ........................................   45




Liao                                                            [Page 2]


INTERNET-DRAFT             LRMP                          13 October 1998


1. Introduction

   This document describes the Light-weight Reliable Multicast Protocol
   (LRMP) version 1 which is intended to provide reliable multicast
   transport service to applications. The reliable service means source
   ordered and reliable data delivery on an end-to-end basis.

1.1 Application Scope

   Applications that require group communication are continuously
   emerging. In group communication, data sent by one host should arrive
   at multiple receivers. These applications can benefit from IP
   Multicast [1] that allows one-to-many data delivery at network layer,
   making optimization possible by replication of data at routers. LRMP
   (version 1) is intended to be used for a subset of these applications
   that have the following characteristics:

     o large-scale communication group. The users participating in
       group communication are generally dispersed in a wide area
       network environment, thus their network links are heterogeneous,
       i.e., the end-to-end transmission delay and bandwidth differ a
       lot.

     o large-size communication group. The number of users participating
       in group communication may be potentially very large.

     o loose time constraint. This means that the transmission delay is
       not critical for applications. In another extreme, real time
       audio and video conference applications need low transmission
       delay in order for that audio and video data could be played in a
       synchronized fashion.

     o reasonable performance. These applications do not need to reach
       very high data throughput, instead they need to keep data
       transmission at a reasonable rate.

     o loosely coupled group. Applications may join or leave the group
       at any time and at any location.

     o requiring that data is reliably delivered to receivers.

   Typical applications include bulk data transfer (e.g., file
   transfer), multicast chat and some kinds of collaborative work. These
   characteristics allow to adopt conservative approaches when doing
   error recovery and flow control in order to keep the total traffic
   of a multicast session at a reasonable level with regard to data
   traffic.




Liao                                                            [Page 3]


INTERNET-DRAFT             LRMP                          13 October 1998


1.2 Overview

   IP Multicast [1] provides point-to-multipoint datagram delivery
   service to communicating hosts, i.e., transmission of datagrams from
   a sender to a group of simultaneous receivers. IP Multicast itself is
   not reliable, datagrams are not guaranteed to arrive at receivers and
   in the order they are sent. In unicast case, reliable data delivery
   is generally achieved by TCP [2] at the transport layer in the
   Internet environment. In multicast case, reliable multicast transport
   protocols are needed for applications requiring reliable data
   transfer.

   The Light-weight Reliable Multicast Protocol (LRMP) is intended to
   offer end-to-end reliable network transport services suitable for
   bulk data transfer to multiple receivers. While some TCP design
   principles can be applied to reliable multicast, the design
   philosophy for reliable multicast protocols is rather different.
   Reliable multicast protocols have to offer good scalability,
   otherwise they may be potentially dangerous to the Internet if used
   in a wide scale [5].

   A common approach for scalability is to replace positive
   acknowledgements (ACK) by negative acknowledgements (NACK) [6]. This
   can reduce considerably the volume of control traffic under normal
   network conditions. However for large groups, this is insufficient
   for several reasons. First, the number of NACK packets could still
   be very high when packet loss occurs simultaneously at many
   receivers. Second, the resulted control traffic and retransmitted
   packets still go to every receiver in the group. In particular,
   heterogeneous environments make these problems much worse. Other
   techniques are necessary to further improve the scalability, such as
   duplicate NACK and repair suppression [6], and local error recovery.

   LRMP is intended to offer good scalability on the current
   infrastructure of Internet, that is, no routers involved in error
   recovery [10]. The generated control traffic and retransmissions
   should be kept at a low level and in a limited scope. In case of
   reception errors, error recovery is first restricted to its local
   area, i.e., local group. If hopefully it can be done within the
   local area, this will be transparent to the sender and receivers in
   other areas. Local error recovery technique allows to isolate
   reception errors in a limited region when possible. In this way, it
   avoids that NACK and retransmitted packets travel across the whole
   group.

   In LRMP, there are no central control points, namely representatives,
   every receiver plays a strictly equal role. Using centralized control
   places constraints on flexibility [9] [10] [11]. Unless the router



Liao                                                            [Page 4]


INTERNET-DRAFT             LRMP                          13 October 1998


   assisted control scheme can be applied, decentralized control is
   more appropriate for a general use on the Internet. LRMP does not try
   to rebuild a tree structure from the multicast tree, instead a
   totally distributed control scheme is used. Local groups are formed
   implicitly for local error recovery. Therefore all packets to form
   local group and assign local group representatives are not necessary.
   LRMP is a receiver-reliable transport protocol. Each receiver is
   responsible for ensuring its correct reception of data while it may
   be cooperative by allowing to send repair packets to its neighbors.
   The failure at one receiver has generally not much to do with the
   quality of service (QoS) at other receivers.

   LRMP attempts to optimize the message exchange for error recovery.
   For duplicate NACK and repair suppression, some basic mechanisms of
   SRM [6] are adopted, including NACK based loss report, exponential
   back-off timers for sending NACK and missing (repair) packets. While
   there are no representatives in local recovery, a receiver can
   dynamically play this role for a repair process in a local group.
   This can further reduce the probability of duplicate NACK and repair
   packets.

   It is very difficult, if not impossible, to ensure both high
   scalability and full reliability in a large scale. Note that at
   present hosts on the Internet generally have very heterogeneous
   network links. While one encounters failure in reception, others may
   have perfectly received all packets. If the missing packets are
   repeatedly transmitted for a few receivers by the transport protocol
   while the session is going on, infinite buffer size is theoretically
   required. LRMP is not intended to be fully reliable for an arbitrary
   set of receivers, whereas applications could still employ some
   specific mechanisms to cope with this problem, for example, using a
   separate session for some particularly slow receivers. In LRMP,
   receivers either successfully receive all packets or generate
   reception error events in case of failure. Besides LRMP does not make
   effort to recover missing packets that are transmitted before a
   receiver joins a session.

   In order to get feedback information from receivers, a sender
   selective receiver report mechanism is included. That allows to
   trigger the transmission of receiver reports while the required
   bandwidth is totally under control. This technique is also called
   sampling. Receiver reports can be considered in some sense as
   positive ACKs and complement the NACK mechanism to make this
   protocol fully reliable when the number of receivers is low.

   LRMP uses a rate based flow and congestion control mechanism to
   control the traffic sent to the network. Congestion control is
   necessary to ensure that the network bandwidth is fairly shared among



Liao                                                            [Page 5]


INTERNET-DRAFT             LRMP                          13 October 1998


   a number of competing data flows when network congestion occurs. The
   flow and congestion control mechanism included in LRMP is intended to
   be friendly and competitive with other data flows under flow and
   congestion control such as TCP.

   By the name, LRMP is intended to be light-weight. The protocol
   overhead and control traffic is relatively low to increase the
   efficiency in data transfer. LRMP is intended to be embeddable into
   an application.

   LRMP is designed, at least initially, not for use with real time
   continuous media applications. The performance provided by LRMP,
   e.g., the transmission delay and throughput, may not satisfy the
   requirements of these applications. While LRMP is not aimed at
   providing high performance, the data throughput and transmission
   delay should be reasonable compared with the quality of service
   provided by the underlying network.

   This document does not provide any mechanisms either to do membership
   control in group communications or to collect information about each
   session member. Applications are free to join and leave the session
   at any time and at any location.

   In addition this document does not include any mechanism for
   authentication and protection of information conveyed by the
   specified protocol. But it does provide a description on security
   constraints that should be taken into account by applications, see
   section 10 for more details.

1.3 Implementation

   This specification is based on the lower layer network services that
   provide identification of a transport end-point by a transport
   address, transfer of data from or to the given transport address with
   indication of received datagram length. A transport address is
   composed of a network address and a port number. Typical example of
   the target underlying network service is UDP/IP multicast.

   All traffic including data and control is carried on the group
   address and port unless otherwise noted. LRMP operates on a single
   group address/port pair.

   LRMP could be implemented as an independent module following the
   layered design principles or as an integrated part of an application
   following the principles of application level framing [7].

   All integer fields are carried in network byte order, that is, most
   significant byte (octet) first. This byte order is commonly known as



Liao                                                            [Page 6]


INTERNET-DRAFT             LRMP                          13 October 1998


   big-endian. The transmission order is described in detail in [3].

   Unless otherwise noted, numeric constants are in decimal (base 10).
   All header data is aligned to its natural length, i.e., 16-bit fields
   are aligned on even offsets, 32-bit fields are aligned at offsets
   divisible by four, etc. Octets designated as padding have the value
   zero.

   Wallclock time (absolute time) is represented using the timestamp
   format of the Network Time Protocol (NTP), which is in seconds
   relative to 0h UTC on 1 January 1900 [4]. The full resolution NTP
   timestamp is a 64-bit unsigned fixed-point number with the integer
   part in the first 32 bits and the fractional part in the last 32
   bits. In some fields where a more compact representation is
   appropriate, only the middle 32 bits are used; that is, the low 16
   bits of the integer part and the high 16 bits of the fractional part.
   The high 16 bits of the integer part must be determined
   independently.

2. Definitions

   Application: either a higher layer protocol entity or end user
        program. It is the source and/or consumer of the data
        transported by LRMP.

   FEC: forward error correction, a mechanism that adds redundant
        packets in the transmitted data stream so that partial missing
        packets could be recovered without retransmission.

   Subgroup: the set of protocol entities in a local region which is
        reachable using a scope (TTL) value from a particular protocol
        entity.

   Local recovery: a scheme for requesting and sending missing packets
        in a subgroup, i.e., whose scope value is less than the session
        scope value.

   LRMP entity: or protocol entity, an implementation of LRMP that is
        able to send, receive and reply to LRMP data and control packets.

   LRMP receiver: or simply receiver, an LRMP entity that makes efforts
        to receive data packets sent by other LRMP entities.

   LRMP sender: or simply sender, an LRMP entity that sends both data
        and control packets.

   LRMP session: or simply session, the association among a set of LRMP
        entities. For each LRMP entity, the session is defined by a



Liao                                                            [Page 7]


INTERNET-DRAFT             LRMP                          13 October 1998


        particular pair of destination transport addresses (one network
        address plus a port). The destination transport address pair may
        be common for all LRMP entities, as in the case of IP multicast,
        or may be different for each, as in the case of individual
        unicast network addresses plus a common port.

   NACK: negative acknowledgement used to report missing packets.

   Entity Identifier: a 32 bit integer that identifies the source of
        LRMP packets. It is carried in LRMP packet header so as not to
        be dependent upon the network address. All packets from a source
        form part of the same sequence number space, so a receiver
        groups packets by the entity identifier. An LRMP entity should
        use the same identifier during the lifetime of an LRMP session.

   TTL: time-to-live, a parameter used in sending IP multicast packets
        to limit the scope of propagation.

3. Packet Types and Common Header Fields

   This section defines a minimal set of packet types for data transport
   and control. Packets other than reliable data are sent in a best
   effort way, that is, there is no mechanism to recover them. The
   sender should retransmit these packets in need.

   All packets from a single protocol entity should use the same entity
   identifier. Otherwise they are considered coming from a different
   entity.

3.1 Common Fixed Header

   All LRMP packets must contain the following fixed header, followed by
   packet specific options:

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |V=1|P|   PT    |    Scope      |            Length             |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                           Entity ID                           |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   The fields have the following meaning:

   Version (V): 2 bits
        This field identifies the version of LRMP defined by the current
        specification which is one (1).




Liao                                                            [Page 8]


INTERNET-DRAFT             LRMP                          13 October 1998


   Padding (P): 1 bit
        If this bit is set, the packet contains one or more additional
        padding octets at the end which are not part of the application
        data. The last octet of the packet contains a count of how many
        octets should be ignored.

   Packet Type (PT): 5 bits
        This field identifies the type of the packet.

   Scope: 8 bits
        This field indicates the time-to-live (TTL) value used to
        transmit the packet.

   Length: 16 bits
        This field indicates the total length of the packet in number
        of octets, including the header and data.

   Entity ID: 32 bits
        This field contains the entity identifier that uniquely
        identifies the sender of the packet.

   Additional packet specific options, if present, should immediately
   follow this fixed header and should be of an integer number of 32 bit
   words.

3.2 Packet Types

   The following packet type (PT) values are defined in this document
   (for backward compatibility, the type values are not continuous):

   Value        Type                   Abbreviation
     0      Reliable Data                 DATA
     4      Retransmission Data           R_DATA
     8      Unreliable Data               U_DATA
    12      FEC Redundant Data            F_DATA
    17      NACK                          NACK
    18      NACK Reply                    R_NACK
    19      Sender Report                 SR
    20      Receiver Report Selection     RS
    21      Receiver Report               RR

   The values not included in the above list are reserved for future use.

3.3 Entity Identifier

   Every protocol entity is assigned with an entity identifier which is
   a randomly chosen 32 bit integer. The entity identifier must be
   globally unique within a particular session. Though the probability



Liao                                                            [Page 9]


INTERNET-DRAFT             LRMP                          13 October 1998


   of identifier collision is rather low in theory, to further minimize
   collision errors, a protocol entity must detect whether or not there
   is a collision between the received identifiers and its own each time
   it receives a packet. In the case of collision, it's the receiver
   which must change its identifier if another entity is a sender. If
   the concerned protocol entities are receivers, they must all change
   their identifiers to another randomly chosen identifier. It is
   expected that the collision is resolved at the initialization phase
   for senders, i.e., a sender sends several control packets before data
   transmission to detect possible collisions.

   At receivers, if a protocol entity sees that two senders use the same
   identifier from different network locations, it should reject the one
   which was heard later.

   A protocol entity should use only one entity identifier during the
   lifetime of a session. If it changes the identifier during a session,
   it is considered as a completely new entity.

   In data transmission, the entity identifier is used to identify the
   data stream from a sender, i.e., the packets with the same entity
   identifier form a data stream ordered by continuous sequence numbers.
   So as to retransmissions by a third party, the original entity
   identifier is included.

3.4 Scope

   The scope field of an LRMP packet should be set to the same TTL value
   with that the packet is sent to the underlying network layer. In
   LRMP, packets may be transmitted using different TTL values due to
   local error recovery. The scope field is used by a receiver to
   approximatively estimate the distance to the packet sender.

3.5 Maximum Packet Length

   Inadequate data fragmentation may introduce inefficiency in the
   network and should be generally avoided [12]. Optimal solution
   requires the cooperation of applications. Therefore proper data
   fragmentation/reassembly are left to higher layer protocols to
   perform.

   LRMP places a upper bound on the maximum length of packets that can
   be transmitted, in other words, the maximum transmission unit (MTU).
   The MTU should be set to the minimum MTU of the network path. Modern
   internet routers support larger and larger MTU than a decade before.
   Consequently the maximum transmission unit in LRMP is set to 1400
   octets, including packet header. Any packets larger than this length
   are considered not valid and should be dropped by receivers. This



Liao                                                           [Page 10]


INTERNET-DRAFT             LRMP                          13 October 1998


   gives also the advantage to optimize the buffer management at
   receivers.

3.6 Multiplexing

   The length field is included in the packet header for multiplexing
   several data or control packets into one outgoing packet sent to
   the underlying network. It is not allowed to multiplex packets
   with different scope value in one compound packet for obvious
   reasons. LRMP entities need the indication of received data length
   from the underlying network protocol to correctly parse multiplexed
   packets, which is supported by most of UDP/IP implementations.

4. Data Transmission

   This section describes the data transmission mechanism that must be
   implemented by a protocol entity.

   LRMP provides a per packet selective reliability, i.e., application
   data can be sent either reliably or in a best effort way. This allows
   an application to use the same transport protocol to send reliable
   and unreliable data. Application must indicate the reliability
   (a boolean value) when sending data to LRMP.

4.1 Reliable Data Transmission

   In a normal operation scenario, a data source multicasts a number of
   DATA packets to a session. Each DATA packet is ordered by a sequence
   number. A receiver receives these data packets and delivers them to
   the application if they are in order. If packet loss is detected,
   the receiver sends a NACK packet to request the retransmission. Any
   protocol entity that holds the requested lost packets will try to
   send repair packets (see the next section).

   In general, data packets, the first time transmitted, are sent to
   the whole group, that is, the scope field should be set to the
   time-to-live value of the session accordingly. This scope field
   informs receivers the maximum TTL value which should be used to
   report loss and do repair.

   Each reliable data packet contains a sequence number and the sender's
   entity identifier. The sequence number is increased by one for each
   reliable data packet sent, except retransmission. At receivers,
   a data packet is identified by the entity identifier and the sequence
   number. All packets from a single source constitute a data stream.

   The sequence numbers are rounded to 32-bit unsigned integer, thus
   when overflow occurs, they must take a modulo to 2^32. A sender



Liao                                                           [Page 11]


INTERNET-DRAFT             LRMP                          13 October 1998


   should generally choose a non-zero random number as the initial
   sequence number. A receiver learns the initial reception sequence
   number at the time it joins the session. Therefore LRMP implementors
   should be aware of that the initial outgoing sequence number and the
   initial incoming sequence number may be different for a particular
   data sender and receiver.

   At receivers, the sequence numbers are used to correctly order
   packets that may be received out of order and to eliminate
   duplicates. A protocol entity should implement the reordering of
   received packets before delivering them to the application. An
   entity should also provide applications with capabilities to
   configure this option out, so that packets are delivered in
   reception order.

   Reliable data transmission is subject to flow and congestion control
   which is described in section 7. Data sender can send FEC encoded
   redundant data with the original data stream, see section 9 for
   more details.

4.2 Unreliable Data Transmission

   Unreliable packets are not subject to flow control at the sender side
   and not subject to sequence control at the receiver side. They can be
   considered as out-of-band packets which are delivered in priority but
   without guarantee of arrival at receivers. Due to this particularity,
   unreliable packets are expected to be sent occasionally by an
   application.

   When an unreliable packet is received by a receiver, it should be
   delivered immediately to the application. In addition a receiver does
   not need to cache such packets in the buffer.

5. Packet Loss Recovery

   To avoid to generate unnecessary traffic in the whole group, the
   repair of lost packets is first carried out in local regions. To do
   this, a session is divided by a particular receiver into a number of
   subgroups. For a protocol entity, a subgroup represents a subregion
   limited by a distance radius. Packets sent to a subgroup can not
   reach other entities outside the subgroup. By limiting error recovery
   in a subgroup, reception errors could be isolated. Local recovery can
   be performed by alternating the IP scope value in transmission of
   packets.







Liao                                                           [Page 12]


INTERNET-DRAFT             LRMP                          13 October 1998


5.1 Organization of Subgroups

   Yet another way to define the distance between two hosts is to use
   the number of hops, in other words, the number of intermediate
   routers that data packets should transit from the source to the
   destination. The propagation of an IP datagram is controlled by a
   scope value, also known as the time-to-live parameter. This scope
   value can be thus used to control the radius of distance that a
   multicast packet can reach. In practice, a multicast session is
   always created with a scope value to indicate at which scope the
   session is addressed.

   There is a trade-off between the number of subgroup hierarchies and
   the efficiency of error recovery. More the number of hierarchies,
   finer the local error recovery but larger the error recovery time.
   It could be possible to configure the subgroup hierarchies at
   runtime by an application, a protocol entity uses by default the
   following rule for organization of subgroups. Given the time-to-live
   value (the nominal TTL) for a session, the session must be organized
   into the following hierarchical subgroups:

     o the whole group at TTL
     o subgroup at 63 if TTL > 63
     o subgroup at 47 if TTL > 47
     o subgroup at 15 if TTL > 15

   The top level, i.e., the whole group, must be present in every
   session. A descendant subgroup is created only if the nominal TTL is
   greater than the subgroup TTL value. Therefore there could be at
   maximum four levels of subgroups. For example, a session with TTL
   value 63 has three levels. A session with TTL value less than and
   equal to 15 has only one level subgroup. A subgroup contains another
   subgroup if its ttl value is greater than the latter.

   Every LRMP packet carries a scope field equal to the ttl value with
   that the packet is sent to the underlying network. So when a receiver
   receives a packet (data or control), it knows that the packet sender
   is surely within a distance less than the scope value carried in the
   packet. The scope field allows a protocol entity to determine whether
   or not the packet sender belongs to one of its subgroups. It remains
   constant during transmission, it should not be confused with the
   scope field in IP datagrams.

   It is possible that the multicast route between two hosts is
   asymmetric, i.e., the number of hops from host A to host B may be
   different from that from host B to host A. As the gap of the subgroup
   ttl value is enough large, in a given subgroup, if host A can reach
   host B, it is most probable that host B can also reach host A.



Liao                                                           [Page 13]


INTERNET-DRAFT             LRMP                          13 October 1998


   Error recovery should be performed within subgroups in increasing
   distance (ttl) order, i.e., first in the lowest level subgroup, then in
   the second level subgroup and finally in the whole group. In each
   subgroup, every receiver plays a strictly equal role, there is no
   subgroup leader. So no join or leave messages are necessary to

   explicitly form subgroups while they may still be implemented by
   applications in case of strong membership control.

   Each protocol entity is responsible for recovery of its own lost
   packets. However it should keep track of the control messages
   received from other protocol entities to eventually cancel the
   duplicates of control and repair packets.

5.2 Enabling/disabling a Subgroup

   To avoid unnecessary error report to a subgroup, first of all, a
   protocol entity should use the heuristic algorithm described here to
   determine whether or not an error could be recovered in a given
   subgroup. Basically if there are no other protocol entities within
   a subgroup, certainly no need to do error recovery in that subgroup.
   If there are other protocol entities in a subgroup, errors may or may
   not be recoverable in that subgroup. A receiver enables a subgroup if
   it considers that there are some chances to recover errors in that
   subgroup, or disables otherwise. The enable/disable mechanism allows
   to improve the error recovery time for missing packets.

   Enable conditions

   Given a subgroup, enable it if one of the following conditions is
   true:

     o at start-up.

     o a repair packet with the subgroup ttl is heard.

     o the disabled time is greater than the maximum disabled time,
       e.g., 3 minutes.

   The last condition is to prevent the deadlock, that is, all subgroup
   members are in the disabled state. In this case, no receivers will
   send error report packets within that subgroup. So a timeout
   mechanism is necessary to retrigger the error recovery in that
   subgroup.

   Disable condition

   Given a subgroup, disable it if the number of successive subgroup



Liao                                                           [Page 14]


INTERNET-DRAFT             LRMP                          13 October 1998


   scoped error report packets without subgroup scoped reply is greater
   than or equal to a prefixed number, 5.

   The whole group must never be disabled since the sender is surely
   there and will reply to error report packets. If a subgroup is
   disabled for any reason, a receiver should jump to the next higher
   level subgroup to do error recovery.

5.3 Error Report

   The protocol makes no effort to recover packets that were sent before
   a receiver joins the session. The sequence number of the first DATA
   packet or extracted from a SR (sender report) packet is considered
   as the starting sequence number for a particular sender.

   A receiver detects packet loss either by checking if there is a gap
   between the sequence numbers of successive received packets or the
   sequence number given by a SR (sender report) packet does not
   correspond to the expected sequence number for that sender.

5.3.1 Algorithm

   When packet loss is detected, error report is carried out from the
   lowest level subgroup to the whole group until the loss is recovered
   or the number of maximum tries is reached. An exponential back-off
   timer is used for duplicate NACK suppression. The subgroup to start
   error recovery is the lowest level subgroup which is in the enabled
   state. Given the starting subgroup Gi, a receiver must use the
   following algorithm to report packet loss by sending a NACK packet,

     1. Set the number of tries (N) to 0.

     2. Schedules a random timer whose value is uniformly distributed
        in the range [t1, 2*t1], where t1 = MRTT*2^N and MRTT is the
        estimated mean round trip time to other protocol entities
        reachable in the subgroup Gi.

     3. During the timer period, if a NACK packet which contains the
        local NACK is received (see section 5.3.3), goto step 5.

     4. When the timer expires, if all lost packets have been received,
        the repair process terminates, otherwise send a NACK packet to
        the subgroup Gi.

     5. Then check

        o if the subgroup level is not the highest level, the subgroup
          level is increased by one, i <= i + 1, goto step 1;



Liao                                                           [Page 15]


INTERNET-DRAFT             LRMP                          13 October 1998


        o if the subgroup level is the highest level, the number of
          tries (N) is increased by one, N <= N + 1. If the number of
          tries is greater than or equal to 8, the repair process is
          abandoned. Otherwise goto step 2.

   The loss report should be sequential, that is, the lost packets with

   lower sequence number should be reported first. Unless the current
   repair process is terminated normally or abnormally, next loss report
   should not be started. In the worst case, an error report could be
   carried out once in each subgroup, and eight times in the whole
   group.

5.3.2 Timer Adjustment

   As the protocol uses a rate based flow control mechanism (see section
   7), the repair packet sender will send data generally in regular time
   interval. When a NACK packet is received, it is possible that the
   first repair packet will be sent only after a transmission interval.
   To avoid to send excessive NACK packets, a transmission interval
   should be added to the timer value if a NACK packet was already sent
   or heard from the network.

   For estimation of the transmission interval used by a particular
   sender, see section 6.1.

5.3.3 Duplicate NACK Suppression

   A NACK packet is said containing another NACK packet if they are for
   the same sender and the reported lost sequence numbers are a superset
   of the latter. The former is called a super NACK of the latter. For
   example, given the following two NACKs (see section 8.5) for the same
   sender,

        NACK A: lowest seqno = 34567
                bitmask = 0x000000ff

        NACK B: lowest seqno = 34570
                bitmask = 0x0000000f

   NACK A contains NACK B.

   If a super NACK packet is heard from the network, a receiver does not
   need to send its NACK since its lost packets are reported by that
   NACK. Therefore the receiver must not send its NACK packet when the
   current timer expires, but should schedule the next NACK timer to
   keep the repair process active. When the next timer expires, the
   receiver must still suppress its NACK in the following cases, since



Liao                                                           [Page 16]


INTERNET-DRAFT             LRMP                          13 October 1998


   the NACK sender will probably send it again if the lost packets have
   not been repaired:

     o Another super NACK was heard in this timer period.

     o The receiver did not send a NACK at previous timeouts in the
       current repair process.

     o Its entity identifier is higher than that of the super NACK
       packet heard in the last timer period.

   This procedure is intended to further reduce the probability of
   duplicate NACK packets at the following timeouts. Therefore when
   multiple receivers encounter the same lost packets, the receiver with
   the shortest timer value and with the lowest entity identifier will
   act as a representative in that loss repair process.

   To prevent the NACK sender leaving the group or behaving abnormally,
   a receiver should not stop the repair process when a super NACK
   packet is heard and should apply the above delay procedure for at
   most next two timer periods.

5.3.4 Other Delay Conditions

   When the NACK timer expires, a receiver should delay the transmission
   of NACK packet and schedules another timer in the following cases,

     o The first lost packet has been received, it is possible that
       succeeding repair packets are queued for transmission at the
       responder side and will arrive soon, except that a R_NACK was
       received that excludes this possibility.

     o A R_NACK was received during the timer period but the repair
       packets are not yet received.

5.4 Duplicate NACK Detection

   A newly received NACK packet is considered as duplicate if a super
   NACK packet (containing this one) was received just before.
   Duplicates may occur under one of the following conditions:

     o two (or more) protocol entities have a timeout time in an
       interval which is less than the packet propagation time from
       one to another.

     o variable packet propagation time.





Liao                                                           [Page 17]


INTERNET-DRAFT             LRMP                          13 October 1998


     o due to packet loss, a receiver did not see the NACK packet sent
       by another entity.

   To distinguish duplicate NACK packets and not to deteriorate the
   error recovery time, a straightforward way is the following: given
   the time t1 when the last NACK packet was received and the time t2
   when the same reporter will issue the next NACK if the loss is not
   repaired, all NACK packets received between t1 and t2 could be
   treated as duplicates. This way, at least a successive NACK sent by
   the same reporter will not be confused with duplicates. The time
   interval (t2 - t1) between sending two NACK packets by a same
   reporter is greater than twice the mean round trip time plus a
   transmission interval. Therefore a protocol entity should treat a
   newly received NACK packet as duplicate if there is a super NACK
   packet which was received within an interval equal to twice the mean
   round trip time plus a transmission interval.

5.5 Retransmission

   LRMP entities keep recently sent and received data packets in their
   buffer space. The total size of the buffer, depending on the used
   transmission rate, should be enough large to allow loss repair.
   It is recommended that the buffer size should correspond to 10
   seconds - 1 minutes of data packets at the full specified
   transmission rate (e.g., between 80 KB and 480 KB at 64 kb/s).

   A NACK packet allows to report a number of adjacent lost packets and
   contains a scope field that should be used by the NACK responder to
   restrict the retransmissions to the same scope.

   Upon receipt of a NACK packet, a protocol entity is said eligible for
   sending repairs if it holds a part of the requested lost packets. An
   eligible entity must check first if the NACK is a duplicate for the
   purpose to eliminate possible duplicate retransmissions. If a NACK is
   duplicate, it should be ignored.

5.5.1 Algorithm

   If a NACK is not duplicate, an eligible protocol entity schedules a
   random timer whose value is uniformly distributed in the range
   [MRTT, 2*MRTT], where MRTT is the estimated mean round trip time to
   other protocol entities reachable in the corresponding subgroup. When
   the timer expires, if the lost packet(s) or a R_NACK (NACK reply)
   packet have not been heard from other protocol entities, the protocol
   entity sends first a R_NACK and then the lost packet(s).

   To further improve the performance and reduce the number of duplicate
   repair packets, the original sender applies a different algorithm.



Liao                                                           [Page 18]


INTERNET-DRAFT             LRMP                          13 October 1998


   When the sender receives a NACK packet, it checks if this is a
   duplicate. If it is not, the sender should send immediately the
   repair packets since one and only one protocol entity will respond
   immediately.

   In addition, if the scope field of a NACK packet is the session TTL,
   all receivers must not reply to the NACK packet and expect that the
   original sender will send the repair(s) with no delay. This will
   eliminate duplicate repair packets at the session scope level.

   This scheme will get still better performance if there is one fixed
   protocol entity responsible for error control in each subgroup. This
   means if a unique entity can apply the retransmission algorithm of
   the original sender in a subgroup, for example, the router or a
   designated receiver, the error recovery time and duplicate repairs
   will be get even better.

5.5.2 Sending NACK reply

   Before sending the repair data (R_DATA) packets, the protocol entity
   should first send a NACK reply packet. This packet is used to
   identify the repair packet sender and also used to measure the round
   trip time between the NACK sender and the repair packet sender.

   NACK reply packets allow in addition fast partial repair. It is
   possible that a receiver holds only a part of the reported lost
   packets. In this case, it is desirable that this receiver will send
   this part while the remaining lost packets can be repaired by other
   entities or in a higher level subgroup. In the NACK reply packet, the
   LRSN field should be set to the sequence number of the first repair
   packet and the BFRP field to the bitmask of the following repair
   packets, see section 8.6.

   Upon reception of a NACK reply packet, the error reporter can
   determine which packets can not be repaired in the corresponding
   subgroup and can report them to a higher level subgroup. For example,
   suppose that the first lost sequence number and the first repair
   sequence number is the same, the bitmask of the remaining lost
   packets can be determined by,

       loss_bitmask &= ~repair_bitmask;

5.5.3 Sending Repairs

   If a receiver is able to send repair packets to its neighbors, it
   must keep the original data packets intact. Otherwise it should
   not respond to NACK packets. LRMP implementors should be aware that
   accepting packets retransmitted by a third-party represents an



Liao                                                           [Page 19]


INTERNET-DRAFT             LRMP                          13 October 1998


   additional vulnerability to malicious attacks.

   Repair packets should be scoped within the same subgroup as the
   received NACK packet. They should be transmitted with higher priority
   than the transmission of new data. In addition, retransmissions are
   subject to the same flow and congestion control as in data
   transmission, see section 7.

5.5.4 Duplicate Repair Suppression

   In order to avoid duplicate repair packets, all receivers eligible to
   respond to the NACK packet should use NACK reply packets to detect
   possible multiple responses. Since an entity should send first a NACK
   reply before sending the repair packets, upon receipt of such a
   packet, other entities can determine whether there will be duplicate
   repairs if they participate in sending repairs. Thus when a NACK
   reply is received, if a receiver has not yet send a NACK reply, it
   should cancel its reply process. Otherwise if its entity identifier
   is higher than that of the NACK reply sender, it must cancel its
   response, even if they have started to send the repair packets.

   In absence of NACK reply packets, for example, due to loss, if
   repair packets are heard from the network, a receiver should still
   cancel its own retransmissions if its identifier is higher than that
   of the repair sender.

   In any case, if a NACK reply packet or repair packets are heard from
   the original sender, all other entities must cancel their reply and
   retransmissions. It is considered that the original sender has the
   highest priority in sending repair packets.

5.6 Reception Failure

   Reception failure is an event generated when a receiver can not
   synchronize with the data stream sent by a sender. Reception
   failures occur in case of network partition or congestion (a
   receiver behind a slow link), specifically under the following
   conditions:

     o when the number of timeouts for a loss event (NACK timer)
       reaches a threshold, repair packets have still not been received.
       This threshold depends on the number of error recovery subgroups
       and has a maximum value of 10.

     o there is a too large difference between the currently received
       sequence number and the expected sequence number so that the
       cache space is insufficient to hold all packets between this
       difference, which is required for error recovery.



Liao                                                           [Page 20]


INTERNET-DRAFT             LRMP                          13 October 1998


     o there is a too large difference between the sequence number
       announced by a sender report packet and the expected sequence
       number.

   When a reception failure is encountered, a receiver should not try
   anymore to repair the current missing sequence number, instead it
   should try to synchronize with the current sequence number of the
   data stream. Otherwise the sender may not respond to its request
   for retransmission.

   In addition, a receiver should notify the application a reception
   failure event. Some applications may need this notification to drop
   incomplete data objects. It is desirable that higher layer protocols
   might include mechanism for retransmission of missing data objects
   according to the degree of importance.

5.7 Mean Round Trip Time Estimation

   The sender does not necessarily need to know the round trip time to
   the receivers for error recovery except for other purposes since it
   always immediately sends repair packets. Otherwise the round trip
   time plays an extremely important role in sending error reports and
   repairs.

   When sending error reports in a subgroup, a receiver generally
   does not know who will send repair packets. Thus it uses the mean
   round trip time to schedule error reports, so does the repair packet
   sender. All receivers should carefully estimate the mean round trip
   time values to make the error recovery algorithm work more
   efficiently. LRMP offers some mechanism for this purpose.

   At start-up, the initial mean round trip time for each subgroup
   should be set to a relatively conservative value using the following
   expression:

       MRTT = 200*(scope/63)^2 milliseconds

   where the upper bound is set to 800 milliseconds and the lower bound
   is set to 12 milliseconds. Consequently the groups at world, region
   and local site scope have approximatively the following initial mean
   round trip time values,

     o MRTT at scope <= 15: 12 milliseconds.
     o MRTT at scope 63: 200 milliseconds.
     o MRTT at scope >= 127: 800 milliseconds.

   The mean round trip time will get closer to its true value in the
   repair processes. NACK and NACK reply packets allow to measure the



Liao                                                           [Page 21]


INTERNET-DRAFT             LRMP                          13 October 1998


   round trip time between the NACK sender and its responder. Each NACK
   packet carries a timestamp value (t1) which indicates the local time
   the NACK packet is sent. When a protocol entity sends the NACK reply
   packet, it puts this timestamp (t1) and the delay since the NACK
   packet was received into the reply packet. Upon reception of the NACK
   reply, the receiver can get a rough estimation of the round trip time
   as follows:

   NACK sender    t1 (NACK)              t2 (NACK_REPLY)
            ------|-----------------------|---------
                   \                     /
                    \                   /
            ---------|-----------------|------------
   NACK responder    |<---- delay ---->|

       RTT = t2 - t1 - delay

   The mean round trip time in the corresponding subgroup is estimated
   using the following expression:

       MRTT = ALPHA*MRTT + (1 - ALPHA)*RTT

   where ALPHA is a smoothing factor set to 0.875. To avoid
   multiplication, the above formula can expressed as,

       MRTT = MRTT + ((RTT - MRTT) >> 3)

   There are two interesting side effects resulted from this scheme.
   When the network is not congested, the measured round trip time RTT is
   generally lower than the initial value that is relatively high. After
   a receiver sent a NACK packet and has received the repair packet, it
   will hold a mean round trip time lower than those never send a NACK
   packet. The next time packet loss occurs in that domain, it is most
   probably this receiver that will first timeout and send the NACK
   packet. This receiver will then get the mean round trip time even
   lower. In this way error report will tend to be done by a small
   number of receivers. This is a desirable behavior since there will be
   less concurrency in error report and the mean round trip time will
   get more realistic.

   When the network is congested, it is possible that the measured round
   trip time is larger than or around the initial value. In that case,
   error report will be carried out eventually by all receivers. It is
   more difficult to make the mean round trip time realistic.







Liao                                                           [Page 22]


INTERNET-DRAFT             LRMP                          13 October 1998


6. Sender and Receiver Reports

6.1 Sender Report

   Sender report packets are intended to provide receivers with the
   current state in data transmission such as the highest sequence
   number reached, the number of packets and that of octets sent since
   the beginning of the session. By analyzing a sender report, a
   receiver can figure out how many packets or octets it has missed and
   whether it is synchronized with the data transmission.

   A data sender should send some sender report packets in the following
   cases:

     o before the first time it will send data or it will begin to send
       data after a long silent time. This is to inform receivers the
       starting sequence number that will be used in the data
       transmission that follows. Thus a receiver can determine whether
       or not it has missed some starting packets.

     o periodically send a sender report during the data transmission
       to provide some statistics information to receivers. In this
       case, the sender sends either a report every two seconds or for
       every quarter of the send window data sent.

     o at the end of bulk data transfer. A sender report informs what
       is the end sequence number so that receivers can determine
       whether or not it has missed a portion of ending packets.

   When the data sender enters in idle state, i.e., it has no more data
   to send, the interval at which sender reports are sent should be
   doubled every time until the idle time reaches five minutes.

   The actual transmission rate at which the sender sends data can be
   computed from two successive sender reports. That is, the difference
   between the octet counts divided by the time interval. The later can
   be derived from the timestamp field.

   Similarly the transmission interval can also be calculated from two
   successive sender reports. That is, the difference between the packet
   counts divided by the time interval.

6.2 Selective Receiver Report

   Receiver reports are useful for both sender and receivers. They have
   multiple purposes. First they are used for estimation of the session
   population. It could be interesting to know how many participants are
   actually in a session. Based on this estimation, the sender could



Liao                                                           [Page 23]


INTERNET-DRAFT             LRMP                          13 October 1998


   decide, for example, to go on or stop the session.

   Receiver reports are also used to get quality of service feedback
   from receivers, such as the loss rate, the number of packets and
   octets received. The feedback can be used to do flow and congestion
   control and adjust other transmission parameters, for example, the
   redundancy in the data stream. In addition they allow to know where
   there is a serious reception problem.

   By default receivers should not send receiver reports. A data sender
   sends a RS (receiver report selection) packet to tell receivers how
   to send receiver reports. The following ways are prescribed here for
   sending receiver reports:

     o a receiver sends once a report with a specified probability.
       This probability could be adapted by the sender to the number of
       receivers in a session.

     o a receiver sends a report periodically, but the total traffic
       (generated by receiver reports) is limited to a small percentage
       of the total bandwidth, i.e., 5%, like in RTP [23].

   A receiver report selection packet contains a list of receivers
   which selects the receivers which should send receiver report(s).
   The list can be either a list of entity identifiers or a wild card
   address (0xffffffff). If it is a wild card address, that means that
   all receivers are selected. Otherwise only those whose identifier
   is among the list are selected. The selected receivers should use
   the probability and report interval parameters contained in the RS
   packet to control whether and how to send receiver report(s).

   If the probability field is set to zero, the selected receivers
   should send receiver reports periodically at the specified interval.
   However if the total traffic generated by control packets is above
   the bandwidth limit (5%), a receiver should calculate the report
   interval with respect to the bandwidth limit.

   If the probability field is greater than zero, the selected receivers
   should should use a random event generator (by means of a random
   value generator) to trigger whether or not they should send a report.
   If an event is generated with the given probability, the receiver
   should send only once a report.

   If both the probability and interval fields are set to zero, this
   packet must be interpreted as an unselect packet, that is, the
   selected receivers should stop sending receiver reports triggered
   by the previous receiver report selection packet.




Liao                                                           [Page 24]


INTERNET-DRAFT             LRMP                          13 October 1998


   In all cases, the report interval should be randomized to avoid
   receiver report implosion. The randomized interval should be
   uniformly distributed in the range [I/4, I], where I is the interval
   given by the RS packet.

   The receiver report selection is sender specific, that is, a sender
   can select receivers to send reports just for itself, not for other
   senders. The settings carried in an RS packet remain valid until
   another RS packet modifies them. If it is absolutely necessary to
   modify current settings, the sender should send the new RS packet
   more than once to prevent possible loss.

   To have an approximative estimate of the session population, the
   probability field could be set to a non zero value and the list of
   receivers set to a wild card address. After the time corresponding
   to the interval field of the packet has elapsed, both the sender
   and receivers can estimate the number of receivers using the
   following expression,

       population = number of responders/probability.

   Note that due to possible packet loss, the real population is
   generally greater than this estimate.

   The round trip time RTT between a sender and a receiver can also be
   measured using a pair of sender report and receiver report, similar
   to the mechanism described in section 5.7.

7. Flow and Congestion Control

   Flow and congestion control constitutes a vital component of this
   protocol. First applications need flow control to adjust the
   transmission rate so that the data flow does not go above the
   processing capacity of the application. Otherwise packets may be lost
   at end hosts due to lack of processing power. Second the network can
   generally offer limited throughput. Even if there is a single data
   flow, it should still be adapted to the available network bandwidth,
   generally limited by the most bottleneck network path, to avoid
   congestion and achieve better performance. Third when there are
   several data flows in the network, it is extremely important that one
   flow does not shutdown the others. Instead the network bandwidth
   should be fairly shared among them. Besides a data flow should be
   competitive to ensure the responsiveness for applications. The
   rate-based control mechanism described here is intended to be
   friendly with other data flows under flow and congestion control
   such as TCP.





Liao                                                           [Page 25]


INTERNET-DRAFT             LRMP                          13 October 1998


7.1 Transmission Rate

   Data transmission and retransmission must be kept within a range
   specified by an application, in form of [Rmin, Rmax], where Rmin
   and Rmax are the lower and upper bounds of the data rate. If an
   application does not specify the rate range, the default range
   should be applied, for example, in [8 kbits/s, 64 kbits/s]. While the
   specification of rate range requires some experience in network
   communications, it is not a difficult task in most cases.

   At startup, the data rate R should be increased gradually up to the
   maximum rate, similar to the slow start in TCP [14]. The initial
   rate should be set to (Rmin + Rmax)/2. Then for every eighth of send
   window data sent, increase the rate by 0.125R if no contrary
   indications. Under normal network conditions, the data rate will
   reach the maximum rate at most after an amount of data corresponding
   to one and half send window have been sent.

   As a closed-loop approach is adopted, if the network is partitioned
   near the sender, no feedback will be returned from the network. In
   this case, it is desirable that the sender keeps the transmission
   at the minimum rate.

7.2 Congestion Control

   Flow and congestion control is performed at the sender side according
   to the feedback information gathered from the network. A network
   congestion problem can be reflected by the following parameters:

     o the information carried in NACK packets, such as the lowest lost
       sequence number and the bitmask. Congestion will cause more
       packets being lost, thus the number of retransmissions will
       increase.

     o indication from receivers. Due to local error recovery,
       additional traffic can be generated in local region that will not
       be seen by the sender. This may result in local congestion
       problem which needs to be reported to the sender.

   A sender generally maintains transmitted data in its buffer space,
   called send window, for possible retransmissions. Congestion control
   should function adaptively with regard to the above parameters and
   the send window size.

   To reduce unnecessary oscillations of the transmission rate, two
   adjustment operations should not be performed in too small time
   interval. It is recommended that adjustments are regularly carried
   out for every eighth of send window data sent.



Liao                                                           [Page 26]


INTERNET-DRAFT             LRMP                          13 October 1998



7.2.1 Adaptation to the Loss

   NACK packets can be used together with send window to limit the
   number of outstanding packets in the network, similar to ACK packets
   used in unicast. However the number of NACK packets heard from the
   network may not timely indicate a congestion problem due to NACK
   suppression and the fact that one NACK packet can report more than
   one lost packets. Congestion control that only makes use of this
   information will not respond quickly to congestion problem. But the
   lowest sequence number requested for retransmission by a NACK packet
   can be a good indication of congestion problem.

   If the lowest sequence number requested for retransmission is going
   out of the range maintained within the send window, that means that
   the sender is going ahead too fast and the error recovery will be
   soon impossible. If the sender does not slow down the data
   transmission, some receivers will not be able to synchronize with the
   data flow.

   To respond to this problem, a sender should calculate the difference
   between the current sequence number in transmission and the lowest
   sequence number requested for retransmission by a NACK packet. The

   rate should be adjusted as follows, given the current rate R:

     o If the difference is greater than half send window size, the
       transmission rate should be reduced to R/4.

     o If the difference is greater than one third of send window
       size, the transmission rate is reduced to R/2.

     o If the difference is greater than a quarter of send window
       size, the transmission rate is reduced to 3R/4.

   If the rate is not decreased according to the above criteria,
   it should not be increased at the next adjustment in presence
   of loss.

7.2.2 Adaptation to Congestion Indication from Receivers

   As described above, additional flow and congestion control is needed
   for the following reasons. First a receiver may not be able to
   synchronize with the data flow due to the fact that the application
   can not timely process received data. That may cause receive buffer
   overflow. Second the traffic introduced by local error recovery may
   cause local congestion problem. Congestion indication from receiver
   is intended to report possible local congestion problem that is



Liao                                                           [Page 27]


INTERNET-DRAFT             LRMP                          13 October 1998


   useful for congestion avoidance. It was first proposed by [15].

   The congestion flag in receiver report is used for this purpose.
   It should be set if the difference between the last sequence number
   delivered to the application and the highest sequence number heard
   from the sender is greater than half the receive window (buffer)
   size. This means that the number of outstanding packets is going to
   be too high so that the receiver will not be able to repair loss due
   to lack of buffer space. It is thus desirable for the sender to
   reduce the transmission rate in this case.

   Upon reception of a congestion indication, a sender should reduce
   the transmission rate to R/2 [22].

7.2.3 Getting to the Equilibrium: Rate Increase

   If no decrease condition is true and no loss is reported, as
   described above, and one eighth of send window time has elapsed since
   the last decrease or increase, the rate should be increased by a
   factor of 0.125 (1/8) up to the maximum rate. With this control
   policy, one decrease to the half rate requires roughly six increases
   to reach the original rate.

7.3 The Case of Heterogeneous Receivers

   For large groups and in heterogeneous environments, it is often the
   case that a few receivers have very slow network connections than
   the others. In many cases, it is desirable that the slowest receivers
   do not block the data transmission for the majority of receivers. In
   particular, interactive applications require that new data is timely
   presented to the end users. Strictly applying the mechanism described
   above may lead the data rate always to the minimum in presence of
   very slow receivers.

   To avoid this to take place, several precautions should be taken:

     o the application should be advised to use an adequate minimum
       rate. But the minimum rate should be enough low to ensure the
       fairness of adaptive congestion control.

     o a sender can ignore the congestion signals from the slowest
       receivers. To do this, the sender needs to keep trace of the
       hosts that caused most often the rate decreases. In the case
       where the output queue is full most of time, the sender could
       make a heuristic decision to ignore further congestion signals
       from these hosts.





Liao                                                           [Page 28]


INTERNET-DRAFT             LRMP                          13 October 1998


     o a receiver should leave the session if it encounters a high
       loss rate and the data rate is not reduced by the sender
       accordingly. For normal receivers, this is necessary to reject
       too aggressive data flows and possible traffic attacks. For very
       slow receivers, this is particularly necessary not to make their
       congested network links even worse and also not to block the
       session for the majority of receivers. The receiver may try to
       rejoin the session at later time. If the problem persists after
       several rejoin attempts, the receiver may definitely abandon this
       session.

   In particularly heterogeneous environments, layered multicast could
   be useful [24]. That is, an application can use multiple groups,
   each of them addresses a set of receivers with a particular level
   of QoS.

8. Packet Formats

   This section defines the packet formats that a protocol entity should
   implement to send data and control packets. A protocol entity should
   ignore those packets if their types are not recognized.

8.1 Unreliable Data

   Unreliable data packets have no additional options. They are
   transmitted in a best effort way and are not subject to sequence
   control. If they are lost, no efforts should be made for recovery.
   Therefore every unreliable data packet has a fixed header of 8 bytes.

8.2 Reliable Data

   Reliable data packets must contain the following options in addition
   to the common fixed header. In total, reliable data packets have a
   header of 16 bytes.

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                          timestamp                            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                       sequence number                         |
      +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
      |                       application data                        |
      |                             ....                              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   The fields have the following meaning:




Liao                                                           [Page 29]


INTERNET-DRAFT             LRMP                          13 October 1998


   timestamp: 32 bits
        This field indicates the time at which this packet is sent.
        It is encoded as the middle 32 bits of NTP time, i.e., in units
        of fraction of 1/65536 second.

   sequence number: 32 bits
        This field indicates the sequence number of this packet.

   Application data with variable length should follow after the data
   packet header. The length of application data and packet header
   must fit into the maximum transmission unit.

   By doing a difference between the timestamp fields of two successive
   data packets, receivers can get a rough estimate of the transmission
   interval. This interval is only meaningful if the data flow is
   continuous.

8.3 Retransmission Data

   Retransmission data packets are sent in response to NACK packets.
   They must contain the following options in addition to the common
   fixed header:

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                      original entity ID                       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                       sequence number                         |
      +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
      |                       application data                        |
      |                             ....                              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   The fields have the following meaning:

   original entity ID: 32 bits
        This field contains the entity identifier of the original sender
        of the data packet.

   sequence number: 32 bits
        This field gives the sequence number of the packet which should
        be the same as received from the original sender.

   It is prescribed that retransmission data packets have the same
   header length as reliable data packets for two reasons. First, to
   minimize necessary operations for retransmissions. The NACK
   responder just needs to modify  the first few fields in the original



Liao                                                           [Page 30]


INTERNET-DRAFT             LRMP                          13 October 1998


   data packet. Second, to avoid the total packet length exceeding the
   maximum transmission unit by appending additional fields in the
   header.

8.4 FEC Redundant Data

   A protocol entity may implement the forward error correction
   mechanism which is optional. FEC data packet format is specified in
   a way such that the data stream can still be correctly received even
   if FEC is not supported by a particular implementation. See section
   9 for details.

8.5 Error report

   Error report (NACK) packets are used to report a set of adjacent lost
   packets and request the retransmission. NACK packets must contain the
   following options in addition to the common fixed header:

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                           timestamp                           |
      +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
      |                            srcID 1                            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                             LLSN                              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                             BFLP                              |
      +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
      |                        (next srcID ...)                       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   The fields have the following meaning:

   timestamp: 32 bits
        This field indicates the time at which this packet is sent.
        It is encoded as the middle 32 bits of NTP time, i.e., in units
        of fraction of 1/65536 second.

   srcID 1: 32 bits
        This field indicates the entity identifier of the first data
        source to which packet loss is reported.

   LLSN (Lowest Lost Sequence Number): 32 bits
        This field indicates the sequence number of the first lost
        packet.





Liao                                                           [Page 31]


INTERNET-DRAFT             LRMP                          13 October 1998


   BFLP (Bitmask of the Following Lost Packets): 32 bits
        This field indicates the bitmask of the following lost packets.
        In the bitmask, the bit k (1 <= k <= 32) is set to 1 if the
        corresponding sequence number (LLSN + k) is lost. The value
        0x0101 means that packets with sequence number LLSN, LLSN + 1,
        LLSN + 9 are lost.

   next srcID: 32 bits
        This field indicates the entity identifier of the next data
        source to which packet loss is reported, followed by LLSN and
        BFLP fields.

   The timestamp is included for the purpose to measure the round trip
   time between the error reporter and the NACK packet responder.

8.6 NACK Reply

   NACK reply packets are sent in response to NACK packets and before
   sending repairs. They must contain the following options in addition
   to the common fixed header:

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                         NACK Reporter                         |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                         NACK timestamp                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                   delay since received NACK (DSRN)            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                        NACK destinator                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                             LRSN                              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                             BFRP                              |
      +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
      |                    (next NACK Reporter ...)                   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   The fields have the following meaning:

   NACK Reporter: 32 bits
        the entity identifier of the entity which reported the packet
        loss.

   NACK timestamp: 32 bits
        This field is a copy of the timestamp field carried in the NACK
        packet.



Liao                                                           [Page 32]


INTERNET-DRAFT             LRMP                          13 October 1998


   delay since received NACK (DSRN): 32 bits
        This field indicates the time passed from the reception of the
        NACK packet to the reply.  It is encoded in the fractions of
        1/65536 seconds. The NACK reporter can use the NACK timestamp
        and the delay to estimate the round trip time to the responder.

   NACK destinator: 32 bits
        the entity identifier of the original data sender to which the
        packet loss is reported.

   LRSN (Lowest Repair Sequence Number): 32 bits
        This field indicates the lowest sequence number of the repair
        packets that will be sent by the responder.

   BFRP (Bitmask of the Following Repair Packets): 32 bits
        This field indicates the bitmask of the following repair
        packets. In the bitmask, the bit k (1 <= k <= 32) is set to 1 if
        the corresponding sequence number (LRSN + k) will be sent as
        repair. The value 0x0101 means that packets with sequence
        number LRSN, LRSN + 1, LRSN + 9 will be sent.

8.7 Sender Report

   Sender reports must contain the following options in addition to
   the common fixed header:

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                           timestamp                           |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                      next sequence number                     |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                         packet count                          |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                          octet count                          |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   The fields have the following meaning:

   timestamp: 32 bits
        This field indicates the time at which this packet is sent. It
        is encoded as the middle 32 bits of NTP time, i.e., in units
        of fraction of 1/65536 second.







Liao                                                           [Page 33]


INTERNET-DRAFT             LRMP                          13 October 1998


   Next Sequence Number: 32 bits
        This field indicates the sequence number to be used in the next
        data packet. If the sender has not yet sent data packets (i.e.,
        the packet count is 0), this field informs receivers the initial
        sequence number. Upon receipt of this packet, receivers could
        either set the initial sequence number for this sender or check
        that if they have received all packets till this number minus
        one.

   Packet Count: 32 bits
        This field indicates the total number of packets sent by the
        sender since the creation of the session.

   Octet Count: 32 bits
        This field indicates the total number of octets sent by the
        sender since the creation of the session.

8.8 Receiver Report Selection

   Receiver report selection packets must contain the following options
   in addition to the common fixed header:

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                           timestamp                           |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |          probability          |           interval            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                       list of receivers                       |
      |                       (variable length)                       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   The fields have the following meaning:

   Timestamp: 32 bits
        This field indicates the time at which this packet is sent. It
        is encoded as the middle 32 bits of NTP time. Its purpose is to
        measure the round trip time between the sender and a receiver.

   Probability: 16 bit
        This field indicates the probability that a receiver should use
        to trigger the transmission of a receiver report. It is encoded
        in fractions of 1/65536.

   Interval: 16 bit
        This field indicates the time interval to use to randomize
        the report time. It is in number of seconds.



Liao                                                           [Page 34]


INTERNET-DRAFT             LRMP                          13 October 1998


   List of receivers: variable length
        This field contains either a wild card address (0xffffffff)
        or a list of entity identifiers of the receivers that are
        selected to send receiver reports.

8.9 Receiver Report

   Receiver reports are sent only upon selection by the sender. While
   the report selection is sender specific, a receiver report packet
   may contain several receiver reports, each of them destinated to a
   specific sender.

   Receiver reports must contain the following options in addition to
   the common fixed header:

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                            srcID 1                            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                         RS timestamp                          |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                      delay since RS (DSRS)                    |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    expected sequence number                   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |C|  loss rate  |      cumulative number of packets lost        |
      +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
      |                        (next srcID ...)                       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   The fields have the following meaning:

   srcID 1: 32 bits
        the entity identifier of the data source to which the report is
        addressed.

   RS timestamp: 32 bits
        This field is a copy of the timestamp field carried in the
        receiver report selection packet.

   delay since RS (DSRS): 32 bits
        This field indicates the delay between the reception of the
        receiver report selection packet and the reply. It is encoded
        in the fractions of 1/65536 seconds. The sender can use the
        timestamp and the delay to estimate the round trip time to
        the reporter.




Liao                                                           [Page 35]


INTERNET-DRAFT             LRMP                          13 October 1998


   expected sequence number: 32 bits
        This field indicates the expected sequence number from the
        sender. It implies that all packets less than this number have
        been correctly received. Thus it can be considered as a
        positive acknowledgement to all packets till this number minus
        one.

   C (Congestion): 8 bits
        This field is the congestion flag. If set, it indicates that
        the network path is congested between the sender and the
        receiver.

   loss rate: 8 bits
        This field indicates the fraction of packets lost since last
        report or since the receiver joined the session if no report
        was sent before. It is expressed in fractions of 1/128.

   cumulative number of packets lost: 24 bits
        This field indicates the total number of packets lost since
        the receiver joined the session.

9. Options for Forward Error Correction

   This section describes how to integrate forward error correction
   (FEC) into the protocol. Proper use of FEC technique can
   substantially improve the scalability due to the fact that it
   reduces the number of feedback packets from receivers [16] [17]
   [18] [19]. FEC is particularly useful in very large groups and over
   asymmetric network links where no or little bandwidth is available
   on feedback channels.

   Since the use of FEC is optional, the FEC integration scheme
   described here allows that implementations without FEC support can
   correctly receive data stream by ignoring FEC redundant packets.

   There are many ways to send FEC encoded packets. For example, FEC
   encoded packets can be sent either automatically or upon reception
   of NACK packets as repairs. This document is not intended to define
   what transmission schemes should be used by the sender, rather it
   only specifies the necessary elements that allows to implement a
   generic receiver. Thus no restrictions are put on how FEC packets
   should be transmitted as long as they allow correct recovery at
   receivers. Implementations are free to choose an adequate
   transmission scheme.







Liao                                                           [Page 36]


INTERNET-DRAFT             LRMP                          13 October 1998


9.1 Parameters

   FEC is based on the principle of adding some redundant packets to
   the transmitted data stream so that the original data packets can be
   recovered without retransmission up to certain loss. This can avoid
   generating NACK packets [18] [19].

   FEC can be implemented using erasure codes [16]. More specifically,
   the data and redundant packets are grouped into blocks. A block
   contains k data packets and (n-k) redundant packets, where n is the
   size of a block. The (n-k) redundant packets are calculated from
   k data packets. At reception if k out of n packets are received,
   the original data packets can be reconstructed.

   To increase the efficiency of recovery in case of burst loss, a
   spacing parameter is introduced. That is, let the base sequence
   number be b and the spacing between sequence numbers be s. The
   sequence numbers of original data packets in a block are composed of:

        b, b + s, b + 2s, b + 3s, ..., b + (k-1)s

   Larger spacing parameter and large block size (n) requires more
   buffer space at receivers. In addition, for large block size,
   receivers that newly joined the session may need longer time to be
   able to start decoding FEC packets.

   FEC packets that belong to a same block are referenced by the same
   base sequence number, b. In addition, they should contain the block
   size (n), the number of redundant packets (n-k) and the spacing
   parameter.

9.2 FEC Packet Format

   FEC encoded redundant packets have the same header length as DATA
   packets and must contain the following options in addition to the
   common fixed header:

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                              BSN                              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |       BS      |       NR      |    spacing    |      RC       |
      +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
      |                           FEC data                            |
      |                             ....                              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+




Liao                                                           [Page 37]


INTERNET-DRAFT             LRMP                          13 October 1998


   The fields have the following meaning:

   BSN (Base Sequence Number): 32 bits
        This field indicates the starting sequence number of the
        original data packets from which the redundant packets are
        calculated.

   BS (Block Size): 8 bits
        This field is the size of the current block minus one.

   NR (Number of Redundant Packets): 8 bits
        This field is the number of redundant packets in the current
        block minus one.

   spacing: 8 bits
        This field is the spacing between the sequence numbers of
        DATA packets minus one.

   RC (Redundant packet Count): 8 bits
        This field indicates the relative redundant packet number,
        starting from 0, in this block, i.e., 0 <= RC < NR.

   FEC data: variable length
        This field contains the redundant data calculated from the
        original data packets.

10. Security Considerations

   LRMP suffers from the same security liabilities as unicast protocols,
   for example, an imposter can fake source or destination network
   addresses, or change the header or data payload. This section
   describes the security constraints present in this protocol in
   addition to unicast protocols. Multicast is in general more
   vulnerable to malicious attacks. Implementations should take these
   constraints into account in order to ensure the normal working of
   the protocol. It is also desirable that an implementation offers
   possibilities to log detailed trace in the case where a possible
   attack is detected.

10.1 Traffic Attacks

   A malicious or misbehaving site may send as much data as possible to
   a session. This can result in that the session will be flooded by
   excessive data traffic so that the intended data traffic can not be
   transmitted as expected. At the worst, it can lead to a denial of
   service attack. If a protocol entity is detected doing so, the
   packets received from that entity should be dropped before further
   processing. The host doing this attack should also be indicated to



Liao                                                           [Page 38]


INTERNET-DRAFT             LRMP                          13 October 1998


   the network administrator so that possible prevention could be made.

10.2 Error Recovery

   A malicious or misbehaving site may continuously request unnecessary
   retransmissions by sending excessive NACK packets. Since the
   retransmission will take some useful bandwidth, this can slow down
   the transmission of new data. To avoid this problem, a protocol
   entity can place an upper bound to the number of NACKs that can be
   generated by a receiver, for example, in form of ratio of NACKs/DATA
   packets, as well as an upper bound to the number of retransmissions
   of a same data packet. A protocol entity should reject NACK packets
   received from a receiver if the number of NACKs received from this
   receiver is abnormally much higher than any other receivers.

   It is possible that a protocol entity modifies the data packets
   received from the original sender and sends them as repairs. In
   absence of low level authentication, it is recommended that
   applications use some mechanism to authenticate the information
   carried by the protocol.

10.3 Entity Identifier

   A malicious or misbehaving site may use an entity identifier already
   used by another entity to send data or erroneous control packets. In
   this case, it is important that a protocol entity correctly
   implements the mechanism described in section 3.3 to deny packets
   from a forged entity.

   A malicious or misbehaving site may also use a low entity identifier
   in repair process, either for error report or sending repairs. This
   entity may send or respond to NACK packets, then stop the repair
   process. If a protocol entity implements incorrectly the repair
   procedure, loss repair may depend on the entity with low entity
   identifier and thus can be blocked.

   A malicious or misbehaving site may change very frequently its entity
   identifier. If an implementation keeps the list of all entities heard
   in the session, that will make the size of the list continuously
   growing and consequently will increase the memory usage. To avoid
   this type of problems, an implementation can take two precautions.
   First it can limit the size of the list. If the number of entities
   exceeds the maximum size, old entries are removed. Second it can
   reuse an old entry that is from the same network address as the new
   entity and has not been heard since a long time.






Liao                                                           [Page 39]


INTERNET-DRAFT             LRMP                          13 October 1998


10.4 Round Trip Time

   A malicious or misbehaving site may try to make the estimation of
   round trip time inadequate by putting bad delay either in NACK reply
   or receiver report. To prevent this type of attacks, a protocol
   entity should place a lower bound and a upper bound to measured round
   trip time and limit the portion contributed by a single entity to the
   mean round trip time.

10.5 Congestion Control

   A malicious or misbehaving site may try to make the transmission rate
   too low by sending false NACK packets or congestion indication in the
   receiver reports. It is desirable to advise the users to put a
   reasonable lower bound for the transmission rate. In addition,
   implementations can ignore those NACK packets or congestion
   indications if they come too often from the same site.

10.6 Confidentiality

   There is no data encryption prescribed by this protocol. Implementors
   should be aware that as the information is transmitted in clear, all
   receivers can receive and eventually interpret the information. If an
   application wants that only the intended receivers decode the
   information, it should use an encryption algorithm to protect the
   information.

10.7 Level of Redundancy

   Transmission of redundant packets adds additional traffic to the data
   transmission. When packet loss occurs, redundant packets could be
   useful for recovering loss without feedback from receivers. However
   transmission of large amounts of redundant data could increase
   network congestion, leading to a contradictory effect of the use of
   forward error correction. In the worst case, it can lead to a denial
   of service attack. A protocol entity implementing FEC in data
   transmission should use the feedback from receivers such as the
   number of NACKs, round trip time variation to adjust the level of
   redundancy in the data stream.

A. Requirements of RFC 2357

   This section describes how well this specification satisfies the
   criteria of RFC 2357 [5] and future work. LRMP has been implemented
   as a reusable library and a number of tests have been carried out
   [26]. More performance evaluation results will be presented later.





Liao                                                           [Page 40]


INTERNET-DRAFT             LRMP                          13 October 1998


A.1 Scalability

   The basic error recovery scheme of LRMP is derived from SRM and
   thus has similar behavior as SRM which is well analyzed in [6] for
   different network topologies. The parameters that influence the
   scalability are mainly the number of duplicate NACKs and that of
   duplicate repairs in case of loss. From [6], these numbers remain
   enough stable with the group size. From our experiments [26], these
   numbers increase slightly with the group size due to various
   practical reasons, e.g., variable round trip time and transmission
   rate. But they remain enough reasonable.

   LRMP adds some overhead by adopting local error recovery. If
   an error could be recovered in a local group, LRMP will behave
   better than the original scheme of SRM. Otherwise several messages
   could be generated in the local groups. Since NACK packets are of
   small size (24 bytes), the additional traffic is not significant.
   In general, data packets can be considered much costly than NACK
   packets in terms of network resource usage. Besides the NACKs
   sent to the local groups without local repair are not useless, they
   have also a positive effect, called election phase. That is, they
   can be thought to elect the protocol entity which will report the
   packet loss to a higher level group. This can reduce the probability
   of duplicate NACKs in subgroups with larger TTL values.

   The scalability of the error recovery scheme is improved in case of
   burst loss due to the fact that a NACK packet can report up to 33
   lost packets. Compared to one NACK per lost packet, the probability
   of duplicate NACK packets is considerably reduced.

   When there are multiple senders in a session, the packet loss
   for one sender is handled independently of the others. It is
   prescribed that several control packets for different senders can
   be multiplexed into one outgoing packet if they are sent within the
   same scope. In addition of the network bandwidth, the cost of
   multiple senders is the cache space for out-of-order packets. More
   senders require more cache space. Therefore LRMP can generally
   support a limited number of senders which depends on available system
   resources.

   A sender does not need to maintain the state about every receiver.
   It generally needs only to maintain several recently heard receivers
   for the purpose to detect the slowest receivers or possible attacks.
   Similarly receivers only need to maintain the sender state. Thus
   LRMP should be enough scalable to large groups in terms of system
   resource usage.





Liao                                                           [Page 41]


INTERNET-DRAFT             LRMP                          13 October 1998


A.2 Congestion Control

   The congestion control scheme works in function of the send window
   size and loss rate (which is reflected by NACKs). For reasonable
   send window size, e.g., 32 or 64, the congestion control scheme
   reacts rather quickly in case of congestion problems. Overall data
   rate can very quickly drop to the minimum as data retransmission is
   also subject to the same congestion control as transmission of new
   data.

   Further simulation and test are needed to see what fairness can
   be achieved with competing TCP-like data flows [25]. It should be
   noted that it is especially hard to behave the same way as TCP while
   a different algorithm is used. However it could be easier make the
   congestion control less aggressive than TCP.

   For large groups and heterogeneous environments, congestion control
   may often lead the data rate to the minimum due to a few slow
   receivers. A number of heuristic methods are proposed in section 7.3
   to tackle this problem. In particular, a receiver should leave the
   session if it deduces that there is serious mismatch between the
   session data rate and the available bandwidth.

   It is worth noting that though LRMP was designed for heterogeneous
   environments, a significant part of users use it in well controlled
   environments such as private networks where receivers are rather
   homogeneous.

A.3 Congestion Avoidance

   It is hard to do congestion avoidance when packet loss is not
   present. As indicated in [27], in lack of any congestion indication
   from the network, the only available information about the possible
   congested network path is the packet loss and propagation delay.
   The possibility to do rate adaptation according to the round trip
   time variance was explored. To make the rate adaptation pertinent,
   a sender must know the round trip times to all receivers. Yet these
   RTTs need to be enough fresh to be usable for congestion control.
   The need to frequently measure the RTTs to all receivers adds a
   lot of complexity and makes the scalability worse.

   Using the mean RTT to all receivers for rate adaptation leads too
   often to unnecessary adjustments and is not suitable for
   heterogeneous environments due to the diversity of round trip times
   to different receivers.

   Thus LRMP uses only the packet loss information for congestion
   control. LRMP can respond to congestion problem at very early stage



Liao                                                           [Page 42]


INTERNET-DRAFT             LRMP                          13 October 1998


   once packet loss is detected.

   Again we need to look further into the consequences of this scheme
   to see the behavior at both sides (LRMP and TCP) and what is the
   bandwidth share.

A.4 Security Concerns

   A number of security constraints are presented in section 10. They
   should be carefully taken into account by any implementation.
   The current specification does not handle the issues related to the
   authentication and encryption of information. It is recommended
   that an application should make use of adequate techniques to ensure
   the authentication, integrity, and confidentiality of the information
   transported by LRMP.

B. References

   [1] S. Deering, "Host extensions for IP multicasting", RFC 1112,
       August 1989.

   [2] J. Postel, "Transmission Control Protocol", STD 7, RFC 793,
       USC/Information Sciences Institute, Sept. 1981.

   [3] J. Postel, "Internet Protocol", STD 5, RFC 791,
       USC/Information Sciences Institute, Sept. 1981.

   [4] D. Mills, "Network Time Protocol Version 3", RFC 1305, UDEL,
       March 1992.

   [5] A. Mankin, A. Romanow, S. Bradner, V. Paxson., "IETF Criteria
       for Evaluating Reliable Multicast Transport and Application
       Protocols", RFC 2357, June 1998.

   [6] S. Floyd, V. Jacobson, S. McCanne, C. Liu, L. Zhang,
       "A Reliable Multicast Framework for Light-weight Sessions and
       Application Level Framing", ACM Transactions on Networking,
       Nov. 1996.

   [7] D. D. Clark and D. L. Tennenhouse, "Architectural
       considerations for a new generation of protocols," in SIGCOMM
       Symposium on Communications Architectures and Protocols,
       (Philadelphia, Pennsylvania), pp. 200-208, IEEE,  Sept. 1990.
       Computer Communications Review, Vol. 20(4), Sept. 1990.

   [8] J. C. Lin and S. Paul, "RMTP: A Reliable Multicast Transport
       Protocol", Proceedings of IEEE INFOCOM '96, March 1996,
       pp.1414 - 1424.



Liao                                                           [Page 43]


INTERNET-DRAFT             LRMP                          13 October 1998


   [9] B. Whetten et al., "The RMTP-II Protocol", Internet Draft,
       draft-whtten-rmtp-ii-00.txt, April 1998.

  [10] T. Speakman, D. Farinacci, S. Lin, and A. Tweedly, "Pragmatic
       Group Multicast (PGM) Transport Protocol Specification",
       Internet Draft, draft-speakman-pgm-spec-01.txt, Jan. 1998.

  [11] M. Hofmann, "Enabling Group Communication in Global Networks",
       Proc. of Global Networking '97, Volume II, pp321-330, Calgary,
       Alberta, Canada, June 1997.

  [12] C. A. Kent and J. C. Mogul, "Fragmentation Considered Harmful",
       Proc. of SIGCOMM '87, August 1987.

  [13] P. Karn and C. Partridge, "Improving Round-Trip Time Estimates
       in Reliable Transport Protocol", ACM Transactions on Computer
       Systems (TOCS), Vol. 9, No. 4, pp. 364-373, November 1991.

  [14] V. Jacobson, "Congestion Avoidance and Control", Computer
       Communications Review, vol.18, pp314-329, August 1988.

  [15] K.K. Ramakrishnan and R. Jain, "A Binary Feedback Scheme for
       Congestion Avoidance in Computer Networks", ACM Transactions on
       Computer Systems (TOCS), Vol. 8, No. 2, pp 158-181, May, 1990.

  [16] R. E. Blahut, "Theory and Practice of Error Control Codes",
       Addison Wesley, 1984.

  [17] C. Perkins and O. Hodson, "Options for Repair of Streaming
       Media", RFC 2354, UCL, Jube 1998.

  [18] L. Rizzo, "Effective erasure codes for reliable computer
       communication protocols", ACM Computer Communication Review,
       Vol.27, no.2, April 1997.

  [19] J. Nonnenmacher, E. W. Biersack and D. Towsley, "Parity-Based
       Loss Recovery for Reliable Multicast Transmission", Proc. of
       SIGCOMM '97, Sept. 1997.

  [20] D. Meyer, "Administratively Scoped IP Multicast", RFC 2365,
       University of Oregon, July 1998.

  [21] S. Floyd and K. Fall, "Promoting the Use of End-to-End
       Congestion Control in the Internet", submitted to IEEE/ACM
       Transactions on Networking, Feb. 1998.






Liao                                                           [Page 44]


INTERNET-DRAFT             LRMP                          13 October 1998


  [22] Dah Ming Chiu, "Flow and Congestion Control in Reliable
       Multicast", Presentation at IRTF RM group meeting, UCL, July
       1998, available from http://www.east.isi.edu/RMRG/.

  [23] H. Schulzrinne, S. Casner, R. Frederick and V. Jacobson, "RTP:
       A Transport Protocol for Real-Time Applications", RFC 1889,
       January 1996.

  [24] L. Vicisano, L. Rizzo and J. Crowcroft, "TCP-like congestion
       control for layered multicast data transfer", IEEE Infocom '98,
       March 1998.

  [25] M. Handley, "Reference simulations for multicast congestion
       control", Presentation at IRTF RM group meeting, UCL, July
       1998, available from http://www.east.isi.edu/RMRG/.

  [26] T. Liao, "Light-weight Reliable Multicast Protocol", Technical
       report, available at
       http://webcanal.inria.fr/lrmp/lrmp_paper.html, October 1998.

  [27] Jamal Golestani, "Fundamental Observations on Multicast
       Congestion Control in the Internet", Presentation at IRTF RM
       group meeting, UCL, July 1998, available at
       http://www.bell-labs.com/user/golestani/jamal1.ps.

C. Acknowledgments

   Thanks to the IRTF RM group for useful ideas and specially to the
   following people for constructive suggestions and support:
   Jon Crowcroft (UCL), Jean-Francois Abramatic (INRIA/W3C),
   Yves Peynaud (INRIA).

D. Author's Address

   Tie Liao
   INRIA
   Domaine Voluceau - BP 105
   78153 Le Chesnay Cedex
   France

   Email: Tie.Liao@inria.fr










Liao                                                           [Page 45]