Method of multicast message distribution

• US 4,864,559 A
• Filed: 09/27/1988
• Issued: 09/05/1989
• 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): NOT, DEFINED
• Assistant Examiner(s): Scutch, III, Frank M.
• Application Number:
  US07/249,958
• Time in Patent Office: 343 Days
• Field of Search: 370/85, 370/86, 370/89, 370/60, 370/94, 370/58, 370/93, 340/825.44, 455/13, 455/14
• US Class Current: 370/256
• 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 having a plurality of interconnected communication nodes, each of which is directly communicating with at least one other of said nodes by virtue of a corresponding list of known nodes maintained within each node wherein those of said nodes which are communicating nodes are capable of transmitting and receiving messages, a method of distributing a multicast message addresses to a corresponding range of nodes in said network, the range of nodes corresponding to said multicast message including the ones of said nodes to which said multicast message is directed, said method comprising the steps of:

determining, by each of said nodes from its corresponding list of known nodes, at least one group of directly communicating nodes containing the node;

calculating, by each of said directly communicating nodes in said group, a corresponding unique set of pathways between the nodes in each corresponding group for distributing multicast messages to said directly communicating nodes in said group; and

distributing said multicast message to all of said nodes in the corresponding range through said unique set of pathways corresponding to the groups containing the nodes in said range.

2. A method according to claim 1 wherein the step of distributing said multicast messages to all of said nodes in the corresponding range includes the substeps of:

determining, by each of said nodes receiving said multicast messages, whether that node is within the range for said multicast message;

determining, by each of said receiving nodes in the range for said message, whether the message is intended for that receiving node; and

forwarding, by each of said receiving nodes in the multicast range, said multicast messages along said unique set of pathways to any other of said nodes in the corresponding group and in said range.

3. A method according to claim 2 wherein said multicast message includes a local area field and an identifier field and wherein the method of distributing a multicast message further includes the step of analyzing the identifier field of received messages to determine if these messages are multicast messages.

4. A method according to claim 3 wherein said identification field contains a multicast bit identifying said message as a multicast message;

and wherein said step of analyzing includes the substep of checking said multicast bit.

5. A method according to claim 3 wherein said step of determining whether that node is within the range of said multicast message includes the substep of analyzing the local area field of said multicast message to determine if the node is in the range of said multicast message.

6. A method according to claim 5

wherein said network is divided into areas of said nodes;

wherein in each of said areas ones of said nodes designated as level one nodes may only communicate directly with other ones of said nodes in the same area;

wherein selected ones of said nodes designated as level two nodes may communicate directly with other ones of said level two nodes throughout the network and may communicate directly with level one nodes within corresponding areas;

wherein said unique set of pathways corresponding to the nodes in the group of directly communicating nodes defined by each of said areas is designated a level one multicast spanning tree;

wherein said unique set of pathways corresponding to the group of directly communicating nodes designated level two nodes is designated as the level two multicast spanning tree;

wherein said method further includes the substeps of;

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

determining, by each of said level two nodes receiving said multicast message forwarded by respective level one nodes, whether the multicast message is a network multicast message having a range including all of said nodes in said network; and

wherein said step of distributing said multicast message to all of said nodes in the corresponding range includes the substep of forwarding, by each of said level two nodes in said corresponding group, the network multicast messages along said level two multicast spanning tree.

7. A method of multicast message distribution according to claim 1 further including the steps of:

designating, by each level two node, one of said level two nodes in each of said groups, except groups only including level two nodes, as a partition designated level two node;

assigning, by each of said partition designated level two nodes, a multicast range for the network mutlicast message for the group for which the Partition designated level two node was designated and

distributing said assigned multicast message to the corresponding multicast range through the unique sets of pathways corresponding to the groups containing the nodes in said corresponding multicast range.

8. A multicast communication node operable for directly communicating with at least one group of interconnected communication nodes in a network wherein the nodes are connected by links and wherein multicast messages are transmitted to selected nodes in said network, said node comprising:

a node memory including

a program memory for storing sequences of instructions including a decision, an update process, and a forwarding process,

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

a data base storage including

a link state packet data base storage for storing a list of all known nodes within a group of nodes with which the node may directly communicate, and

a forwarding data base for storing lists of links over which messages will be forwarded according to the type of message; and

processor means, connected to the node memory, and capable of accessing said working memory, said program memory and said data base storage, for periodically calculating a unique set of pathways between the nodes in the list of know nodes stored in said link state packet data base in response to said update and decision processes, and for forwarding selected ones of said multicast messages along said unique set of pathways to all of said nodes in the list by distributing said multicast message in response to said forwarding process, said selected multicast messages having ranges including the nodes in said list

9. A communication node according to claim 8 wherein said program memory includes a receive process, wherein said multicast messages are distributed to said selected nodes corresponding to respective multicast ranges, wherein said multicast messages include a local area field and an identifier field, and wherein said processor means includes means responsive to said receive process for analyzing the identifier field of messages received by the node to determine if said received messages are multicast messages and for analyzing the local area field of said received multicast messages to determine if the node is in the range of said multicast message.

10. A communication node according to claim 8 wherein said processor means includes means responsive to said decision process for selecting one of the nodes in each group of directly communicating to be a root node for that group and for calculating said unique pathways for each group to connect the root node for that group to every other directly communicating node in that group without causing said pathways to form loops.

11. In a communication network having a plurality of interconnected communication nodes, each of which is directly communicating with at least one other of said nodes by virtue of a corresponding list of know nodes maintained within each node, wherein those of said nodes which are communicating nodes are capable of transmitting and receiving messages, a method of distributing a multicast message addressed to a corresponding range of nodes in said network, the range of nodes corresponding to said multicast message including the ones of said nodes to which said multicast message is directed, said method comprising the steps of:

determining, by each of said nodes from its corresponding list of known nodes, at least one group of directly communicating nodes containing the node;

calculating, by each of said directly communicating nodes in said group, a corresponding unique set of pathways between the nodes in its corresponding group for distributing multicast messages to said directly communicating nodes in said group, said calculating step including the substeps of;

selecting one of the nodes in each group of directly communicating nodes to be a root node for that group, and

calculating said unique pathways for each group to connect the root node for that group to every other directly communicating node in that group without causing said pathways to form loops; and

distributing said multicast message to all of said nodes in the corresponding range through said unique set of pathways corresponding to the groups containing the nodes in said range.