home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / drafts / draft_s_z / draft-yong-sarp-00.txt < prev    next >
Text File  |  1996-08-19  |  30KB  |  694 lines
  1.  
  2.  
  3. Network Working Group                                           Yong Xie
  4. Internet-Draft                                              Myung J. Lee
  5.                                                         Tarek N. Saadawi
  6.                                             The City College of New York
  7.                              August 20, 1996
  8.  
  9.  
  10.    Sink-Assisted Routing Protocol (SARP) For General IP Multicasting
  11.  
  12.                 <draft-yong-sarp-00.txt>
  13.  
  14. Status of this Memo
  15.  
  16.    This document is an Internet-Draft. Internet-Drafts are working
  17.    documents of the Internet Engineering Task Force (IETF), its areas,
  18.    and its working groups. Note that other groups may also distribute
  19.    working documents as Internet-Drafts.
  20.  
  21.    Internet-Drafts are draft documents valid for a maximum of six months
  22.    and may be updated, replaced, or obsoleted by other documents at any
  23.    time. It is inappropriate to use Internet-Drafts as reference
  24.    material or to cite them other than as ``work in progress.''
  25.  
  26.    To learn the current status of any Internet-Draft, please check the
  27.    1id-abstracts.txt listing contained in the Internet-Drafts Shadow
  28.    Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
  29.    munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
  30.    ftp.isi.edu (US West Coast).
  31.  
  32.  
  33. Abstract
  34.  
  35.    This Internet-Draft proposes a routing protocol for  supporting  
  36.    real-time multicast service over the Internet. The work is
  37.    motivated by the fact that the existing multicast routing protocols 
  38.    are designed under the assumption of symmetric paths, which is not
  39.    necessarily true especially in the real-time applications. 
  40.    The essence of the proposed protocol is using the inter-subnet  
  41.    Routing Guide Message (RGM) flows generated by sink-subnets 
  42.    to form  multicast spanning trees. 
  43.  
  44.    The underlying algorithms enable source and intermediate nodes
  45.    to construct minimal end-to-end delay paths to sink-subnets
  46.    based on the path and the session information conveyed by
  47.    incident RGM-flows. 
  48.  
  49.  
  50.  
  51.  
  52.  
  53.  
  54.  
  55. Expires February 20, 1997                                    [Page 1]
  56.  
  57. Internet Draft         <draft-yong-sarp-00.txt>         August 20, 1996
  58.  
  59.  
  60. 1. Introduction
  61.  
  62.    The primary function of a multicast routing protocol is to select a
  63.    subset of the Internet topology to form the group-specific spanning
  64.    trees over which multicast datagrams are delivered from their
  65.    sources to their sinks. Practically, a multipoint-to-multipoint tree
  66.    is constructed by multiple point-to-multipoint subtrees. Multicast
  67.    routers need to look up the actual source or the sinks of a
  68.    particular datagram in order to make the forwarding decisions.
  69.  
  70.    There have been a number of multicast routing protocols and
  71.    associated algorithms proposed by the Internet community. A
  72.    typical example is the Distance Vector Multicast Routing Protocol 
  73.    (DVMRP) [4] which employs the Reverse Path Multicast (RPM) algorithm
  74.    in the latest mrouted version 3.5 and some vender implementations. As
  75.    well surveyed by [3], RPM is an enhancement to the Reverse Path
  76.    Broadcast (RPB) and the Truncated Reverse Path Broadcasting (TRPB).
  77.    
  78.    RPM defines a way to form the source-rooted spanning trees. The
  79.    distance back to the source of datagrams is the main factor in
  80.    determining the forwarding paths. It assumes the symmetricity of 
  81.    paths which becomes a fundamental limitation of entire "reverse 
  82.    optimal path" routing algorithm family, including RPB, TRPB, and 
  83.    RPM. In fact, a shortest path does not necessarily guarantee 
  84.    a shortest reverse path because of the possibility that a
  85.    full-duplex link could have substantially imbalanced loads on each
  86.    direction. Furthermore, using fixed "metrics" (e.g., hop count) to 
  87.    compare alternative routes is inappropriate for the situations where 
  88.    routes need to be chosen based on real-time parameters 
  89.    (e.g., real-time delay)(see [2]). These two problems, symmetric path
  90.    assumption and fixed metric, poses significant challenge for any IP 
  91.    multicast routing protocols should they support real-time applications.  
  92.    The proposed Sink-Assisted Routing Protocol (SARP) is an attempt to
  93.    address aforementioned two issues. That is, SARP focuses on 
  94.    computing the minimal-delay path from sources to sinks using 
  95.    a real-time delay metric. In contrast,  DVMRP is derived from 
  96.    the Routing Information Protocol (RIP) and concerned with computing 
  97.    the shortest path, in terms of fixed metrics, back to the source of a
  98.    multicast datagram. In short, SARP is to form sink-rooted rather than
  99.    source-rooted spanning trees using the inter-gateway primitive called 
  100.    the Routing Guide Message (RGM).
  101.  
  102.    In order to search for potential multicast source groups, it is
  103.    assumed that the sink-subnet periodically generates and multicasts
  104.    RGMs to every possible subnets within a limited scope of the
  105.    Internet. A source-subnet starts multicasting datagrams out only
  106.    after intercepting the corresponding RGM flow(s). The information
  107.    conveyed by a RGM includes a list of the requested multicast groups
  108.    on behalf of the entire sink-subnet, and the path status as well.
  109.    
  110.  
  111.  
  112.  
  113. Expires February 20, 1997                                    [Page 2]
  114.  
  115. Internet Draft         <draft-yong-sarp-00.txt>         August 20, 1996 
  116.  
  117.  
  118.    RGMs are to be forwarded using a typical Reverse Path Broadcast
  119.    algorithm, except that the optimal path is determined based on the   
  120.    measure of Reverse-Relative-Delay (RRD). In other words, RGMs are
  121.    routed along the paths whose reverse paths are optimal in term of
  122.    real-time delay back to the sink-subnets.  
  123.  
  124.    Currently, multicast service is considered connectionless, due to the
  125.    genetic property of IP. Conventional higher layer handshake-type
  126.    setup of point-to-point connection is often too expensive for most
  127.    real-time and multicast applications. Also, flow control and error
  128.    correction could be really complicated when maintaining a dynamic
  129.    multicast session group. Nevertheless, there is an emerging demand
  130.    for a quality assured IP multicast service, which requires certain
  131.    degree of connectivity between sources and sinks.
  132.     
  133.    Towards that end, SARP is also intended to introduce the concept 
  134.    of "loose-IP-connectivity". That is, the logical connectivity between 
  135.    two IP end-points can be loosely defined by the continuity of 
  136.    end-to-end control-message-flow, while using the basic IP support. 
  137.    In SARP, multicast spanning tree is completely specified by the 
  138.    incidence relations between the RGM-flows and the source nodes. 
  139.    The sink-nodes send periodic RGMs as requests, wait for data arrival, 
  140.    and regard the data arrival as receiving the natural acknowledgement, 
  141.    while a source-node is aware of the existence of the sink-nodes and 
  142.    maintains transmission only if RGM-flows are engaged, giving a sense 
  143.    of data connection. We strongly believe that, as far as multicasting 
  144.    and routing are part of the IP functions, it is necessary to extend 
  145.    IP to provide an unacknowledged connection-oriented service. 
  146.    First, such service is beneficial to IP multicasting in which the
  147.    point-to-point addressing is impossible and the data connection is 
  148.    more important than the logical connection. Second, it is capable of
  149.    conjoining the routing and the resource reservation, which are 
  150.    naturally two inseparable issues.
  151.  
  152.    Throughout this draft, the term "IP-entity" is used generally to cover
  153.    a single network or a subnet, in which all hosts share the same subnet 
  154.    IP address. It has at least one full-duplex link to its neighbor. 
  155.    The access point of an IP-entity to the link is called the port. 
  156.    The abstraction of the Internet can be considered as a planar graph 
  157.    with a set of IP-entities as the nodes, and pairs of the directed 
  158.    edges connecting adjacent nodes. Thus, we shall frequently call 
  159.    the IP entity as a node, for example, the source-node, the sink-node, 
  160.    and the intermediate-node.
  161.  
  162.  
  163. 2. Model of Operation
  164.  
  165.    Multicast routing within an entity is transparent to IP. That means,
  166.    as long as a datagram remains on a subnet, it can reach any sink 
  167.  
  168.  
  169.  
  170.  
  171. Expires February 20, 1997                                    [Page 3]
  172.  
  173. Internet Draft         <draft-yong-sarp-00.txt>         August 20, 1996
  174.  
  175.    
  176.    application within the subnet using the technology that is specific
  177.    to that subnetwork. For example, on the Ethernet, multicasting is 
  178.    handled by mapping a class-D address into  an Ethernet address. On 
  179.    connection-oriented networks, such as an ATM network, it can be
  180.    done by using some signaling mechanism to establish the host-to-host 
  181.    or host-to-gateway Virtual Circuits (VCs).
  182.    As with the task of IP multicast routing being primarily a matter of
  183.    finding gateways among networks, the proposed protocol is concerned 
  184.    only with routing multicast datagrams across an internetwork,
  185.    along the minimal-delay paths from source-subnets to sink-subnets. 
  186.    
  187.    SARP depends on the participations of the sinks to establish the 
  188.    group-specific multicast spanning trees.  According the standardized
  189.    host implementation for supporting IP multicasting [1], incoming
  190.    multicast IP datagrams are received by upper-layer protocol modules
  191.    using the same "Receive IP" operation as for normal unicast datagram,  
  192.    an application process need to explicitly ask its IP module to join
  193.    the group through a service interface. In addition, SARP assumes
  194.    that the process claim itself as the "sink" by opening the file
  195.    descriptor in a read or read/write mode. The host IP module must be
  196.    extended to inform the multicast session information to the subnet-
  197.    router, so that the routing protocol module is able to summarize the
  198.    demands of sub-hosts into the per subnet sink-group-table. As long as
  199.    the table is not empty, RGMs are generated. 
  200.  
  201.  
  202. 3. Algorithms for SARP 
  203.    
  204. 3.1. Measuring the Reverse-Relative-Delay of a Path
  205.  
  206.    Considering the real-time properties of most multicast applications, 
  207.    it is desirable that the distance between two nodes is quantified in 
  208.    term of the real-time delay. The absolute delay, however, is costly 
  209.    to measure since network clocks usually are not accurately 
  210.    synchronized enough for real-time interactive applications. 
  211.    Moreover, the current network synchronization protocols (e.g., [5])
  212.    assume symmetric network paths and use the round-trip-delay as an
  213.    approximation.  We call the delay measured by referencing
  214.    asynchronous clocks the "relative-delay". It is the real-time delay
  215.    measure with a clock-offset error in it. 
  216.    
  217.    In a best-effort service packet-switching internetwork, "optimal" is
  218.    quite a relative term. When a source/intermediate-node intercepts
  219.    only one RGM-flow from a given sink-node, the route of the incoming RGM-
  220.    flow is certainly the only and therefore the optimal route to forward
  221.    datagrams. In case when multiple RGM-flows incident with a source-
  222.    node are rooted at the same sink-node but via different routes, the
  223.    decision of the optimal route back to the sink-node can be reached by
  224.    simply comparing relative-delays of distinct paths. This is possible 
  225.    
  226.  
  227.  
  228.  
  229. Expires February 20, 1997                                    [Page 4]
  230.  
  231. Internet Draft         <draft-yong-sarp-00.txt>         August 20, 1996
  232.  
  233.    
  234.    because that incurred relative-delays result in the same amount of
  235.    the clock-offset for any path between a pair of nodes.  
  236.  
  237.    To measure the relative-delay of a path, each node in the Internet
  238.    that participates in the routing protocol is assumed to send periodic
  239.    delay-probe-packets to every possible adjacent node. Thus, the
  240.    receiving node is able to compute the directional One-Hop-Relative-
  241.    Delays (OHRDs) from (not to) its neighbors. It is required that each 
  242.    node maintains an OHRD cache which has entries for each neighbor. No
  243.    further routine information exchange or propagation among routing
  244.    entities is required by the protocol. This ensures the algorithm
  245.    against from slow-convergence. RGM is designed to convey the "run-
  246.    time" relative-delay information across the internetwork.
  247.  
  248.    Let d(i,i+1) represent the absolute-delay from node i to adjacent 
  249.    node i+1. The OHRD d'(i,i+1) can be measured by sending a probe 
  250.    IP datagram from i to i+1, whose departure time t(i) and arrival 
  251.    time t(i+1) are time-stamped according to the clocks at i and i+1, 
  252.    respectively. d'(i,i+1) actually consists of two components: 
  253.  
  254.      d'(i,i+1) = d(i,i+1) + o(i,i+1)
  255.       
  256.    where o(i,i+1) denotes the clock-offset between i and i+1.  
  257.    
  258.    Obviously, a single trial of the delay measurement would be
  259.    insufficient to represent the statistics of the path. It is assumed
  260.    that the OHRD database maintained by each node is updated with 
  261.    moving-averages of instantaneous measures. The measure interval and 
  262.    the averaging window size are critical to both sensibility and
  263.    stability of the routing protocol. The basic criterion is that, OHRD 
  264.    database is expected to reflect link statistics, while minimal 
  265.    computation is most desirable. Further studies are required for 
  266.    determination of those parameters.  From now on, we shall refer 
  267.    d'(i,i+1) as the measure of the mean OHRD from node i to its neighbor
  268.    i+1. It is recorded by node i+1, and available for reference at any 
  269.    time instant.
  270.  
  271.    When a RGM traverses along a multi-hop path from node j to node i, 
  272.    the relative delay of the reverse path, denoted as D'(i,j), can be   
  273.    calculated by adding the OHRD of every hop along the path. Among
  274.    other information, each RGM-datagram carries a Reverse-Relative-Delay
  275.    (RRD) parameter, which is the sum of the OHRDs added every time
  276.    before the RGM crossing the hop. Thus, the receiving node is able to
  277.    exam the reverse path by simply reading the value of the RRD field:
  278.  
  279.      D'(i,j) = d'(j-1,j) + d'(j-2,j-1) + ... + d'(i-1,i)
  280.          = d(j-1,j) + d(j-2,j-1)+ ...+ d(i-1,i) + o(i,j)
  281.     
  282.    where o(i,j) is the clock-offset between node i and node j. It is
  283.  
  284.  
  285.  
  286.  
  287. Expires February 20, 1997                                    [Page 5]
  288.  
  289. Internet Draft         <draft-yong-sarp-00.txt>         August 20, 1996
  290.  
  291.  
  292.    equal to the sum of the clock-offset components of all OHRDs along 
  293.    the path. Let c(i) represent the value of node-i's clock at a given 
  294.    time instance, o(i,j) is always independent of the intermediate
  295.    clocks, and the path as well:
  296.  
  297.      o(i,j) = c(i) - c(j)
  298.         = c(i) - c(i+1) + c(i+1) - c(i+2) + ... + c(j-1) - c(j)
  299.         = o(i,i+1) + o(i+1, i+2) + ... + o(j-1, j)
  300.  
  301.    As shown in the example topology below, two RGM-flows originating at
  302.    node-A destinating at node-D via B and C. If D'(D,B,A) < D'(D,C,A),  
  303.    the port to B is considered by node-D as the optimal route to forward
  304.    datagrams of certain multicast group to sink-node A, vice versa.
  305.  
  306.  
  307.         B---------D    D'(D,B,A) = d'(B,A) + d'(D,B)
  308.        /         /               = d(B,A) + o(B,A) + d(D,B) + o(D,B)
  309.       /         /                = D(D,B,A) + o(D,A)
  310.      A---------C       D'(D,C,A) = D(D,C,A) + o(D,A)
  311.     
  312.    
  313.  
  314. 3.2. Forming the Sink-Rooted Spanning Trees 
  315.  
  316.    As mentioned in the foregoing, RGMs are used to search for multicast 
  317.    source-node groups on behalf of multicast sink-node groups, and 
  318.    to convey the information about the end-to-end RRD measures. The IP
  319.    header of a RGM datagram contains the sink-subnet-id as its Source 
  320.    Address, and a well-known multicast address in the Destination 
  321.    Address field particularly assigned to the routing protocol. The
  322.    initial Time-To-Live (TTL) parameter is set to a number greater than
  323.    1 and less than 255 to limit the sink-rooted tree to span within a 
  324.    given scope. RGMs also carry other information which will be
  325.    discussed later.
  326.  
  327.    RGMs are to be forwarded using the typical Reverse Path Broadcasting
  328.    (RPB) algorithm. It is assumed that each node that has more than one 
  329.    port maintains a session database, called the "RGM-flow table", to 
  330.    cache the information about every incidence RGM-flow. An entry is 
  331.    created for a sink-node in the cache upon receiving the first RGM
  332.    from that node. Successive arrivals from the same sink-node will make
  333.    the entry stay effective. 
  334.    
  335.    For a node on the edge of the Internet, i.e., it has only one port 
  336.    connecting to the outside world, it only has to record the union of 
  337.    the multicast-group-lists of all incoming RGMs. The actual source 
  338.    addresses of RGMs are not interested because the node ought to send 
  339.    datagrams through the only port any way, if it is the source node of 
  340.  
  341.  
  342.  
  343.  
  344.  
  345. Expires February 20, 1997                                    [Page 6]
  346.  
  347. Internet Draft         <draft-yong-sarp-00.txt>         August 20, 1996
  348.  
  349.    the requested multicast group.
  350.    
  351.    In case that an intermediate/source node has direct connections with 
  352.    multiple adjacent nodes, it possibly intercepts multiple RGM-flows 
  353.    sourced by the same sink-node but via different routes. Nevertheless
  354.    , only one RGM flow from a given sink-node is accepted and possibly 
  355.    forwarded to form the segment of the sink-rooted spanning tree. In 
  356.    the RGM-flow table, an incoming RGM-flow is represented by the
  357.    (SinkNode, InPort) pair. RRD is recorded for the respective RGM-flow
  358.    whenever a RGM arrives. Any other ports that are currently not being
  359.    contacted by the same sink-node are considered having RRD value of
  360.    infinite.
  361.    
  362.    Suppose that node-A has three neighboring nodes, it receives RGMs 
  363.    rooted at sink-subnet S (134.74.60.0) from port p0 and port p2, 
  364.    respectively. According to the RRD measurement, the route via p0 is 
  365.    the optimal reverse path back to node-S. The RGMs arriving at p0 are 
  366.    to be forwarded through ports p1 and p2 to the downstream neighbors
  367.    (with respect to RGM-flows), whereas, those arriving at p1 are 
  368.    discarded. The RGM-flow table of node-A should look like as follows:
  369.    
  370.  
  371.       SinkNode     InPort     RRD   FlowTTL
  372.       --------------------------------------
  373.       134.74.60.0    p0      12345     2
  374.              p1      inf       /
  375.              p2      23456     3
  376.  
  377.  
  378.    As shown in the table, each (SinkNode, InPort) pair also has a Flow 
  379.    Time-To-Live (FlowTTL) counter to monitor the continuity of the RGM-
  380.    flow. FlowTTLs will be decreased by one every unit time, and reset
  381.    after receiving a successive RGM.  The RRD value of a sub-entry is
  382.    set to infinite if no more RGM arriving at the port and the FlowTTL
  383.    has expired. The entry for a given SinkNode is cleaned up only if all
  384.    sub-entries have infinite RRD values. It is mandatory that the
  385.    interval between any sink-node sending two consecutive RGMs along the
  386.    same outgoing path must have a protocol-specific up-bound, in order
  387.    to quantify the continuity of the RGM-flow. Since packet-loss and
  388.    delay-jitter are expected in the Internet, the duration of FlowTTL is
  389.    supposed to cover several such maximal RGM-intervals.
  390.     
  391.    In summary, a source/intermediate node records the RRD information
  392.    for each incoming RGM-flow, and only forwards RGMs that arrive via
  393.    the optimal reverse path (with smallest RRD for a given sink-node)
  394.    to downstream neighbors through all ports except the incoming port.
  395.    Any RGM-flow will be terminated by the receiving node if the TTLs of
  396.    RGM-datagrams are exhausted, and/or the reverse path of RGMs is not
  397.    considered as the optimal reverse path back to their origins.
  398.  
  399.  
  400.  
  401.  
  402.  
  403. Expires February 20, 1997                                    [Page 7]
  404.  
  405. Internet Draft         <draft-yong-sarp-00.txt>         August 20, 1996
  406.  
  407.  
  408. 3.3. Forwarding Multicast Datagrams to Sink-Subnets  
  409.  
  410.    Once the sink-rooted trees are formed, delivery of datagrams seems 
  411.    straight-forward. The Forwarding-Table of a source/intermediate node
  412.    is derived from its RGM-flow-table. It contains entries for each
  413.    multicast group that is interested by at least one active sink-node.
  414.    Each multicast group in the table is mapped to a set of ports that
  415.    represents the union of the optimal routes to every sink-node within
  416.    the group. Thus, the basic forwarding rule is that, any node that has
  417.    either local-generated or received datagrams will forward them to
  418.    selected downstream neighbors according to the MulticastGroup-to-
  419.    OutPorts map. However, multiple sink-rooted trees might conjoin each
  420.    other so that the aggregated spanning graph contains circuits. In
  421.    order to form the group-specific spanning tree, circuits must be
  422.    broken.
  423.  
  424.  
  425.    #----------------------------------------------------------------#
  426.    |                                                                |
  427.    |  +++++p0      +++++                  G-E      G E              |
  428.    |  + G @--------@ E @-------           |        |  \             |
  429.    |  ++@++      p1+++++p0     \          A-B-D    A-B-D            |
  430.    |  p1|                       \           |        |              |
  431.    |    |p1                      \ p0     F-C (A)  F-C (B)(C)(F)    |
  432.    |  ++@++      p1+++++      p1++@++                               |
  433.    |  + A @--------@ B @--------@ D +     G-E      G-E     G-E      |
  434.    |  +++++p0      ++@++p0      +++++        \     |  \    |  \     |
  435.    |               p2|                    A-B-D    A B-D   A-B D    |
  436.    |                 |p0                    |        |       |      |
  437.    |  +++++p0    p1++@++                  F-C (D)  F-C (E) F-C (G)  |
  438.    |  + F @--------@ C +                                            |
  439.    |  +++++        +++++                 the tree rooted at a given |
  440.    |                                     sink-node                  |
  441.    |                                                                |
  442.    |                                     (*) represents sink node.  |
  443.    #----------------------------------------------------------------#
  444.  
  445.  
  446.  
  447.    The above figure illustrates an example topology and a possible
  448.    set of trees rooted at every potential sink-node in the graph.
  449.    Suppose that (A,C,G) is a set of active sink-nodes of a given
  450.    multicast group 239.10.10.1, accordingly, the forwarding-table of
  451.    each node should contain information as follows:
  452.  
  453.  
  454.  
  455.  
  456.  
  457.  
  458.  
  459.  
  460.  
  461. Expires February 20, 1997                                    [Page 8]
  462.  
  463. Internet Draft         <draft-yong-sarp-00.txt>         August 20, 1996
  464.  
  465.  
  466.         MulticastGroup  OutPorts  SinkNodes
  467.         -----------------------------------
  468.       node-A:   239.10.10.1     p0        C
  469.                 p1        G
  470.              
  471.       node-B:   239.10.10.1     p1        A,G
  472.                 p2        C
  473.  
  474.       node-C:   239.10.10.1     p0        A,G
  475.              
  476.       node-D:   239.10.10.1     p1        A,C
  477.              
  478.       node-E:   239.10.10.1     p0        C
  479.                 p1        A,G
  480.  
  481.       node-F:   239.10.10.1     p0        A,C,G
  482.  
  483.    The problem arises if node-E serves as one of the sources of the
  484.    multicast group, while the branches of tree(A) and tree(C) intersect
  485.    at source-node E from different directions. According to the basic
  486.    forwarding rule, datagrams are to be multicasted out through both
  487.    port p0 and port p1 of node-E. Upon receiving datagrams from its
  488.    port p0, intermediate-node B is supposed to further forward them
  489.    via port p1 and port p2, since both routes are optimal from B's
  490.    view point to sink-nodes A/G and C, respectively. Similarly, node-A
  491.    considers its OutPort p0 as the optimal route to sink-node C.
  492.    Obviously, this is a case of "mutual confusion", in which both node-A
  493.    and node-B will forward and receive duplicated datagrams to and from
  494.    each other.
  495.    
  496.    The basic cause of such error is that, the sink-rooted routing
  497.    algorithm works, so far, in a manner that is totally transparent to 
  498.    the source address of the multicast datagram. The protocol has defined 
  499.    the mechanisms to enable an intermediate-node to explicitly determine 
  500.    the downstream optimal route to a given sink-node. However, the node 
  501.    has no idea whether an upstream path is also optimal for the same 
  502.    sink-node. It is evident that the "mutual confusion" problem exists
  503.    between a pair of sink/intermediate nodes on a circuit, only because 
  504.    they are receiving datagrams from a particular source/intermediate 
  505.    node that forks multiple data-flows by duplicating datagrams. In the
  506.    previous example, only node A and node B are confused when receiving
  507.    datagrams sourced by node E. Any node other than node-E will not
  508.    cause the same problem. 
  509.  
  510.    The simplest solution to the circuit-problem is that, any node that
  511.    receives identical datagrams from different neighbors always forward 
  512.    the early copy of a datagram and discards the later one. In so doing,
  513.    any intermediate-node that has multiple OutPorts for a given
  514.  
  515.  
  516.  
  517.  
  518.  
  519. Expires February 20, 1997                                    [Page 9]
  520.  
  521. Internet Draft         <draft-yong-sarp-00.txt>         August 20, 1996
  522.  
  523.  
  524.    multicast group has to check the source address and the sequence
  525.    number of every incoming datagram. Furthermore, the node may send
  526.    messages to suggest its neighbors not to forward datagrams from a
  527.    particular source-node. The link that has such messages on both
  528.    directions must be the one causing the trouble. The problem is that,
  529.    in addition to the processing overhead and the potential "flip-flop"
  530.    situation, link-waste is inevitable. 
  531.  
  532.    Since any source/intermedia node knows exactly who are expecting the
  533.    data and binds them to corresponding OutPorts, a deterministic 
  534.    solution is suggested: If a source/intermediate node "splits" the
  535.    data-flow, i.e., forwards a single incoming data-flow to more than
  536.    one OutPort, it is responsible for specifying the sink-information
  537.    regarding the departure-port in each outgoing datagram. The
  538.    information can be a list of sink-nodes either exclusive or inclusive
  539.    of the OutPort. Also, a receiving intermediate-node will check and
  540.    possibly re-specify the applicable sink information only if it is the
  541.    next splitting point of the data-flow. The proposed forwarding-algorithm
  542.    can be expressed as the following pseudo-code, in which inclusive
  543.    sink-specification is assumed.
  544.  
  545.       while ( receiving datagram D(G) of group G from InPort(D) ) {
  546.      if ( G has entry in forwarding-table && TTL(D) != 0 ) {
  547.         outport[] = OutPorts(D) - InPort(D);
  548.         dup = number of entries in outport[];
  549.         if ( dup == 0 )
  550.            discard D;
  551.         else if ( dup == 1) {
  552.            TTL(D) = TTL(D) -1;
  553.            forward D through outport[0]; /* only active port */
  554.         }
  555.         else {
  556.            for (i=0; i<dup; i++) {
  557.           if ( sinks(D) && sinks(output[i]) ) {
  558.              sinks(D) = sinks(output[i]);
  559.              TTL(D) = TTL(D) -1;
  560.              forward D through outport[i];
  561.           } 
  562.            }
  563.         }
  564.      } else
  565.         discard D;
  566.       }
  567.  
  568.    Where, sinks(D) is the inclusive sink-node list coming with datagram
  569.    D, and sinks(output[i]) is the set of sink-nodes bound to a given
  570.    OutPort of multicast group G. Discarding datagram is only for the
  571.    purpose of resolving possible protocol error. In the steady state,
  572.  
  573.  
  574.  
  575.  
  576.  
  577. Expires February 20, 1997                                   [Page 10]
  578.  
  579. Internet Draft         <draft-yong-sarp-00.txt>         August 20, 1996
  580.  
  581.  
  582.    the algorithm guarantees that any node intercepts data-flows only 
  583.    from the optimal upstream paths. Therefore, delivery paths of
  584.    multicast datagrams are guaranteed end-to-end optimal. An additional
  585.    advantage is that any source/intermediate node is capable of
  586.    rejecting a particular sink-node for the purpose of security or
  587.    resource-reservation.
  588.  
  589.  
  590. 4. Discussion
  591.  
  592.    One of the limitations of SARP is the additional overhead for
  593.    processing RGMs. With the basic algorithm of SARP, the size
  594.    of system memory required by the protocol is proportional to the
  595.    number of active sink-nodes. Any node are potentially saturated by
  596.    RGM-flows, especially when routing is taking place in an internetwork
  597.    with a regular mesh topology. 
  598.    
  599.    The protocol is expected to be further improved in terms of the
  600.    protocol efficiency and scalability with other supplementary means.
  601.    Since the multicast spanning tree is completely specified by the
  602.    incidence relations between RGM-flows and nodes, the optimalization
  603.    can be achieved by reducing unnecessary or redundant forwarding of
  604.    RGMs. An immediate justification to be made is using RPM algorithm
  605.    instead of RPB algorithm to forward RGMs. Moreover, an intermediate-
  606.    node that interconnects two disjoined sub-topology of the Internet, 
  607.    such as the node on the multicast backbone, can be used to merge
  608.    RGM-flows from both directions to represent two groups of sink-nodes. 
  609.    
  610.    The current focus of SARP is to find minimal-delay paths with respect
  611.    to every sink-node, and the overall network load for a given multicast
  612.    group is not necessarily optimized. We reconize that realization of
  613.    minimal network load is equivalent to finding minimal RGM-flow
  614.    pattern. This issue will also remain under further study. 
  615.  
  616. Reference
  617.  
  618.    [1] Steve Deering, "Host Extensions for IP Multicasting," RFC1112, 
  619.        August 1989.
  620.  
  621.    [2] Hedrick, C., "Routing Information Protocol," RFC 1058, Rutgers
  622.        University, June 1988.
  623.  
  624.    [3] C. Semeria, T. Maufer, "Introduce to IP Multicast Routing,"
  625.        draft-rfced-info-semeria-00.txt, 3Comy Corporation, March 1996.
  626.  
  627.    [4] D. Waitzman, C. Partridge, and S. Deering, "Distance Vector
  628.        Multicast Routing Protocol," RFC1057, November 1988.
  629.  
  630.    [5] D. Mills, "Internet Time Synchronization: The Network Time 
  631.        Protocol," IEEE Trans. on Commun., Vol.39, Oct. 1991.
  632.  
  633.  
  634.  
  635. Expires February 20, 1997                                   [Page 11]
  636.  
  637. Internet Draft         <draft-yong-sarp-00.txt>         August 20, 1996
  638.  
  639.  
  640. Author's Address
  641.  
  642.     Yong Xie
  643.     Phone: 212-650-7261
  644.     Email: xyong@ee-mail.engr.ccny.cuny.edu
  645.  
  646.     Myung J. Lee
  647.     Phone: 212-650-7260
  648.     Email: mjlee@ee-mail.engr.ccny.cuny.edu
  649.  
  650.     Tarek N. Saadawi
  651.     Phone: 212-650-7263
  652.     Email: eetns@ee-mail.engr.ccny.cuny.edu
  653.  
  654.     
  655.     Department of Electrical Engineering
  656.     City University of New York, City College
  657.     New York, NY 10031
  658.  
  659.  
  660.  
  661.  
  662.  
  663.  
  664.  
  665.  
  666.  
  667.  
  668.  
  669.  
  670.  
  671.  
  672.  
  673.  
  674.  
  675.  
  676.  
  677.  
  678.  
  679.  
  680.  
  681.  
  682.  
  683.  
  684.  
  685.  
  686.  
  687.  
  688.  
  689.  
  690.  
  691.  
  692.  
  693. Expires February 20, 1997                                   [Page 12]
  694.