Browse Prior Art Database

Encoding of Multicast-Tree Routes

IP.com Disclosure Number: IPCOM000114135D
Original Publication Date: 1994-Nov-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 142K

Publishing Venue

IBM

Related People

Bird, RF: AUTHOR [+3]

Abstract

A method of encoding a multicast-tree route is disclosed. This method allows the originator of the multicast to send out only one copy of the message. The routing information encoded in this message header directs the message to traverse the multicast tree, and generates copies of the message as it hits the branching points on the tree. Therefore, there is no need for the user to send multiple copies of the same message to multiple destinations; and the network resource usage is kept to a minimum.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 40% of the total text.

Encoding of Multicast-Tree Routes

      A method of encoding a multicast-tree route is disclosed.  This
method allows the originator of the multicast to send out only one
copy of the message.  The routing information encoded in this message
header directs the message to traverse the multicast tree, and
generates copies of the message as it hits the branching points on
the tree.  Therefore, there is no need for the user to send multiple
copies of the same message to multiple destinations; and the network
resource usage is kept to a minimum.

      Multicast is the act of one user sending the same message
content to a selected (pre-defined) set of target users.  A multicast
tree is the collection of paths emanating from the source node (the
root of the tree) to the set of target nodes (the leaves of the
tree), in a tree-like structure.  The multicast message(s) traverses
from the root through the tree branches to the leaves without ever
getting into looping situations.  This disclosure assumes that the
set of target nodes and the multicast tree to reach these target
nodes have been determined by methods outside of the scope of this
paper.  The only concerned is an efficient way to encode and decode
the routing information on the multicast message.

      A route in the network is represented by a string of link
labels or Automatic Network Routing (ANR) labels.  Each ANR label
represents a (physical or logical) link in the network, and is
defined locally by the node that attaches to this link.  A link that
connects two nodes, A and B, then has two ANR labels: one as seen by
A, and one as seen by B.  An ANR string of (x,y,z) in the routing
field of a message tells the node to route the message to the link
pointed by the first ANR label x, and strips off this ANR label x
before transmitting the message.  The node at the other end of the
link then strips off label y, and transmits the message to its link
with ANR label=y, and so on.  The last label in the ANR string can be
used as a pointer that points to the end user in the destination
node.  This ANR concept has been described elsewhere, and is used as
a building block in our multicast tree encoding.

      Following are the rules for encoding the multicast tree paths
into the routing field using ANR labels.
 1.  The part of linear path ANR encoding is unchanged as previously
      described, except we reserve a special 'branching point' ANR
      label (e.g., 1 byte 'FE' in hex when in multicast mode).  We
      shall denote this ANR label as <BP> in this disclosure.  All
      nodes in the network must recognize this ANR label.
 2.  When the path reaches a branching point, the next ANR label will
      be this <BP>, followed by the length of the ANR string for the
      left-most (or right-most) branch, and then the actual entire
ANR
      string for this branch.  (Note that within this branch, there
may
      be furth...