Method of multicast message distribution

• US 5,079,767 A
• Filed: 08/25/1989
• Issued: 01/07/1992
• Est. Priority Date: 09/27/1988
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Perlman, Radia
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Chin, Wellington
• Application Number:
  US07/398,472
• Time in Patent Office: 865 Days
• Field of Search: 370/85.9, 370/85.13, 370/94.3, 370/93, 370/60, 370/94.1, 370/85.14, 370/60.1
• US Class Current: 370/408
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• CPC Class Codes: H04Q 2213/13349 Network management
• CPC Class Codes: H04Q 2213/1338 Inter-exchange connection
• CPC Class Codes: H04Q 2213/13383 Hierarchy of switches, main and subexchange, e.g. satellite exchange
• CPC Class Codes: H04Q 2213/13388 Saturation signaling systems
• CPC Class Codes: H04Q 3/0016 Arrangements providing connection between exchanges

Abstract

A method for multicast communication wherein a multicast message is distributed to all the nodes in a multicast range. If a multicast message has a multicast range which is larger than one link in the network then the message is forwarded along a unique set of pathways through the range. The unique set of pathways is called a multicast spanning tree and is unique to all nodes which can communicate directly by virtue of a list of known nodes. The network is divided into areas each of which contains a group of directly communicating nodes. A group of nodes designated as level two nodes facilitates communication between the nodes in different areas.

Claims

1. In a communication network including a plurality of communication nodes interconnected by a plurality of communication links, a method of distributing a multicast message to each of the communication nodes, the method being executed by each of the nodes and comprising the steps of:

selecting a multicast pathway constructed from a set of said links, said set of links being selected such that said multicast pathway contains no loops, and such that each of said communication nodes is connected to at least one of said links in said set and is able to send a message along the links within the set to any other of said communication nodes, the selection of the multicast pathway including the substeps of

selecting one of said communication nodes as root node, and

selecting said set of links to form a spanning tree for said plurality of communication nodes using the selected root node;

receiving the multicast message by each of the communication nodes from a corresponding receiving one of said of links; and

forwarding the received multicast message along every link, other than the corresponding receiving link, which is within the set and which is connected to the node forwarding the message.

2. The method of claim 1 wherein the multicast message includes a range to which the multicast message is addressed, and

wherein said the forwarding step includes the substep, executed by each node receiving the multicast message, of

determining whether the node receiving the multicast message is within the range of the multicast message.

3. The method of claim 1 wherein said network is divided into areas of communication nodes such that in each of said areas ones of nodes designated as level one nodes may only communicate directly with other ones of said nodes in the same area, and ones of said nodes designated as level two nodes may communicate directly both with level one nodes within the same areas and with other ones of said level two nodes throughout the network;

and

wherein said forwarding step further includes the substeps of

forwarding, by each of said level one communication nodes, said multicast message to one of said level two communication nodes in the corresponding area if said multicast message is not addressed to any of the nodes in the area containing that level one node; and

forwarding the multicast message from the level two node receiving the multicast messages to one or more level two nodes on the network.

4. A first communication node for use in a communication network also including other communication nodes to form a group of communication nodes interconnected by a plurality of communication links, said first communication node comprising:

means for selecting a set of said communication links, in common with the other communication nodes in the group, which form a multicast pathway having no loops and which permits any communication nodes in the group to send a message along the links in said multicast pathway to any other of said communication nodes in the group;

means for receiving a multicast message from the ones of said set of links which are coupled to said first communication node; and

means, coupled to said receiving means, for forwarding the received multicast message along every one of the links in said set, if any, which is connected to said first communication ode except the link over which the message was received.

5. A first communication node according to claim 4, wherein the selecting means includes

means for designating one of the communication nodes in the group, in common with the other nodes in the group, as a root node;

and

means for choosing, as said multicast pathway, a spanning tree for the nodes in the group, said spanning tree being determined using said root node as the root of said spanning tree.

6. The first communication node of claim 4, further comprising:

a node memory including

a program memory for storing sequences of instructions,

a working memory for temporarily storing data and messages to be forwarded, and

a forwarding data base storing a list of links over which the multicast messages will be forwarded.