Multicast communication tree creation and control method and apparatus

• US 5,355,371 A
• Filed: 06/18/1982
• Issued: 10/11/1994
• Est. Priority Date: 06/18/1982
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chow, Chee-Seng, Kaplan, Marc A., Ward, Michael J., Peters, Marcia L., Auerbach, Joshua S., Drake, John E. Jr., Hervatic, Elizabeth A., Gopal, Prabandham M.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Nguyen, Chau T.
• Application Number:
  US07/900,628
• Time in Patent Office: 4,498 Days
• Field of Search: 370/94.1, 370/60, 370/60.1, 370/85.13, 370/85.14, 370/54, 370/94.3, 340/825.02, 340/825.03
• US Class Current: 370/255
• 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

Abstract

In a multicast network communication system, administration of the communication path making up the multicast tree itself has been separated from control and administration of the network. Creation of a multicast distribution tree and control over the membership thereof, is separately controlled independently from the creation and use of the tree transmission path used to communicate among the members of a multicast set. Transmission distribution trees are set up when a transmission request is received and the properties of the transmission path that is required are known. Transmission paths are created and controlled by all nodes in the communications system, each node having necessary control code and processors for responding to requests from set members to transmit a message to groups of users by creating and activating the necessary tree communication path distribution linkages. A distribution tree is created by the Tree Leader by generating a tree address using a random number generator. A tree address correlator is generated utilizing network and node identifiers unique for the network, and a list of subnodes or users connected for each member of the multicast tree set is generated. Using this information, a tree distribution path is computed to cover all of the subnodes required and a tree set up request message is sent by the Tree Leader along a computed path to each involved subnode. Each subnode returns a message indicating whether the tree address is already in use or is available for use. Successfully negotiated tree addresses are marked at the path link initiation and termination points at each node through the network.

Claims

1. A communications network having a plurality of nodes interconnected to one another by communications links, via which links messages are sent and delivered to communications network users located at said nodes, said network being organized for communications among members of defined subsets of said network users included in at least one Distribution tree, wherein each of said nodes comprises

means for operating as a Distribution Tree Leader for each subset, said Distribution Tree Leader means including first means for generating a Distribution tree address;

and

second means receiving said Distribution tree address for generating a Distribution tree address correlation index and means for combining said index with said Distribution tree address to, uniquely identify said Distribution tree at all other said nodes having members of said subset included by said Distribution Tree Leader in said Distribution tree; and

third means for generating and sending via said communications links, to all other said nodes having members served by said Distribution tree, a Distribution tree creation request message; and

fourth means at all others of said nodes for receiving Distribution tree creation request messages and, responsive thereto, for generating and sending over said communications links a reply message indicating to said node sending said Distribution tree creation request message whether said Distribution tree address is currently in use at each said other node and said reply message also containing an indication of what Distribution tree, addresses are currently available for use at said node; and

fifth means responsive to received replies from all other said nodes for enabling the distribution of messages to all other said nodes included in said Distribution tree using an address not in conflict with any of said received replies.

2. The network as claimed in claim 1, further comprising:

sixth means at each said node for associating said Distribution tree address not in conflict with said reply messages with the outbound said communications links included in said Distribution tree at each said node.

3. The network as claimed in claim 1, wherein:

said first means further comprises a random number generator for generating said Distribution tree address.

4. The network as claimed in claim 2, wherein:

said first means further comprises a random number generator for generating said Distribution tree address.

5. The network of any of claims 1 through 4, wherein:

said address correlation index comprises the node identification of said node at which said Tree Leader resides and an arbitrary counter value.

6. The network as claimed in any of claims 1 through 4, wherein:

said fifth means, upon receiving said reply message indicating that said Distribution tree address is currently in use at any said node, utilizes said indications received of currently available Distribution tree addresses, and chooses a new Distribution tree address from said available Distribution tree addresses.

7. A Distribution Tree Leader for use at at least one node in a plural node interconnected node network, comprising:

first means for generating a Distribution tree address; and

second means receiving said Distribution tree address for generating a Distribution tree address correlation index and means for combining said index with said Distribution tree address to uniquely identify said Distribution tree at all of said nodes included by said Distribution Tree Leader in said Distribution tree; and

third means at said at least one node for generating and sending via said interconnected node network to all others of said nodes having users served by said Distribution tree, a Distribution tree creation request message; and

fourth means at all others of said nodes for receiving said Distribution tree creation request message and, responsive thereto, for generating and sending a reply message indicating whether said Distribution tree address is currently in use at each said other node and said reply also containing an indication of what Distribution tree addresses are currently available for use at each said node; and

fifth means at said at least one node responsive to said reply messages from each of said other nodes for enabling the distribution of messages to all of said other nodes included in said Distribution tree using a said Distribution tree address not in conflict with any of said reply messages.

8. A Distribution Tree Leader as claimed in claim 7, further comprising:

sixth means at each said node for associating said Distribution tree address not in conflict with said reply messages with outbound communications links included in said Distribution tree at each said node.

9. A Distribution Tree Leader as claimed in claim 7, wherein:

said first means further comprises a random number generator for generating said Distribution tree address.

10. A Distribution Tree Leader as claimed in claim 8, wherein:

said first means further comprises a random number generator for generating said Distribution tree address.

11. A Distribution Tree Leader as claimed in any one of claims 7 through 10, wherein:

said fifth means, upon receiving said reply message indicating that said Distribution tree address is currently in use at said node, utilizes said indications of said currently available Distribution tree addresses to choose a new Distribution address.

12. A method of managing a communications network having a plurality of nodes interconnected to one another by communication links via which messages are sent and delivered to users located at said nodes, wherein said network is organized for communication among members of a defined subset of said users into at least one Distribution tree, said method comprising steps of:

at a first node, selecting a Distribution Tree Leader for said subset;

at the first node, generating at said Tree Leader, a Distribution tree address;

at the first node, generating a Distribution tree address correlation index and combining said index with said Distribution tree address to uniquely identify said Distribution tree for said defined subset in said network;

at the first node, generating and sending over said network links to all said nodes having users served by said Distribution tree, a Distribution tree creation request message;

at all said nodes having users served by said Distribution tree, receiving said Distribution tree creation request message and generating and sending a reply message indicating whether said Distribution tree address is currently in use and an indication of what Distribution tree addresses are currently available for use at each receiving node; and

at the first node, receiving said reply messages and choosing a Distribution tree address different from any Distribution tree address identified in a received reply message as being currently in use.

13. The method of claim 12, further comprising steps of:

assigning said unique Distribution tree address to each said communication link at each said node in said network which is a part of said Distribution tree for said defined subset of users.

14. A communications network having a plurality of nodes interconnected to one another by communications links, via which links messages are sent and delivered to communications network users located at said nodes, said network being organized for communications among members of defined subsets of said network users included in at least one Distribution tree, wherein each of said nodes comprises:

means for operating as a Distribution Tree Leader for each subset, said Distribution Tree Leader means including first means for generating a Distribution tree address; and

second means receiving said Distribution tree address for generating a Distribution tree address correlation index and means for combining said index with said Distribution tree address to uniquely identify said Distribution tree at all other said nodes having members of said subset included by said Distribution Tree Leader in said Distribution tree; and

third means for generating and sending via said communications links to all other said nodes having members served by said Distribution tree, a Distribution tree creation request message; and

fourth means for receiving from all other said nodes reply message indicating whether said Distribution tree address is currently in use at a node sending a reply message, each said reply message also containing an indication of what Distribution tree addresses are currently available for use at the node sending the reply message; and

fifth means responsive to received reply messages from all other said nodes for enabling the distribution of messages to all other said nodes included in said Distribution tree using a selected Distribution tree address not in conflict with a Distribution tree address identified in any reply message as being currently in use at another of said nodes.

15. The network as claimed in claim 14, further comprising:

sixth means for associating said selected Distribution tree address with the outbound said communications links included in said Distribution tree.

16. The network as claimed in claim 15, wherein:

said first means further comprises a random number generator for generating said Distribution tree address.

17. A Distribution Tree Leader for use in at least one note in a network having a plurality of interconnected nodes, comprising:

first means for identifying a set of nodes to be served by a Distribution tree;

second means for generating a Distribution tree address; and

third means receiving said Distribution tree address for generating a Distribution tree address correlation index and combining said index with said Distribution tree address to uniquely identify said Distribution tree at each node in the identified set of nodes included in said Distribution tree; and

fourth means for generating and sending via said network to all nodes in the identified set of nodes served by said Distribution tree a Distribution tree creation request message; and

fifth means for receiving a reply message from each node in the identified set of nodes, each reply message indicating whether said Distribution tree address is currently in use at the replying node and also containing an indication of what Distribution tree addresses are currently available for use at the replying node; and

sixth means responsive to said reply messages for enabling the distribution of messages to all of said nodes included in said Distribution tree using a selected Distribution tree address selected from a set of Distribution tree addresses other than those identified in reply messages as being in use at any of the replying nodes.

18. A Distribution Tree Leader as claimed in claim 17, further comprising:

seventh means for associating said selected Distribution tree address with outbound communications links included in said Distribution tree.

19. A method of managing a communications network having a plurality of nodes interconnected to one another by communication links via which messages are sent and delivered to users located at said nodes, wherein said network is organized for communication among members of a defined subset of said users into at least one Distribution tree, said method being performed at a given node and comprising steps of:

selecting a Distribution Tree Leader for said subset;

generating at said Tree Leader, a Distribution tree address;

generating a Distribution tree address correlation index and combining said index with said Distribution tree address to uniquely identify said Distribution tree for said defined subset in said network;

generating and sending over said network links to all said nodes having users served by said Distribution tree, a Distribution tree creation request message;

receiving reply messages from nodes to which the Distribution tree creation message was sent, each said reply message indicating whether said Distribution tree address is currently in use at the responding node and an indication of what Distribution tree addresses are currently available for use at the responding node; and

choosing a Distribution tree address different from any Distribution tree address identified in a received reply message as being currently in use.