System and method for a multicast network messaging service

• US 20020146008A1
• Filed: 02/07/2001
• Published: 10/10/2002
• Est. Priority Date: 02/07/2001
• Status: Active Grant

• Current Assignee: X Corp. (f/k/a Twitter, Inc.) (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Kaplan, Marc Adam
• Granted Patent: US 7,054,276 B2
• Time in Patent Office: Days
• US Class Current: 370/390
• CPC Class Codes: H04L 12/1859 adapted to provide push services, e.g. data channels
• CPC Class Codes: H04L 12/1877 Measures taken prior to transmission
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/76 Routing in software-defined topologies, e.g. routing between virtual machines

Abstract

A method for the multicast distribution of a message is provided. A first real machine multicasts the message through a network of message processing machines to one or more message receiving machines, wherein the network is organized into two or more cells including machines, and wherein one or more links between cells comprise link bundles. The method includes selecting a spanning tree rooted in the cell including the first real machine, and comprised of the cells and the link bundles. The method determines one or more cells for receiving the message based on the selected spanning tree and the location of the receiving machines, and selects one or more routes from among the machines and links within the cells and link bundles to a next cell. The method further routes the message to the receiving cells in the spanning tree, and delivering the message to the receiving machines within the receiving cells.

Claims

1. A method for the multicast distribution of a message from a first real machine through a network of message processing machines to one or more message receiving machines, wherein the network is organized into two or more cells including machines, and wherein one or more links between cells comprise link bundles, the method comprising the steps of:

selecting a spanning tree rooted in the cell containing the first real machine, and comprised of the cells and the link bundles;

determining one or more cells for receiving the message based on the selected spanning tree and the location of the receiving machines;

selecting one or more routes from among the machines and links within the cells and link bundles to a next cell;

routing the message to the receiving cells in the spanning tree; and

delivering the message to each receiving machine within the receiving cells.

2. The method of claim 1, further comprising the step of implementing one or more virtual machines within a real machine.

3. The method of claim 1, wherein a link is one of a virtual link between two virtual machines, and a real link between two real machines.

4. The method of claim 1, wherein the multicast distribution of the message is along links and further comprises the step of routing the message through the selected spanning tree according to precomputed cellule distribution tables associated with the each real machine, wherein a cellule comprises one or more virtual machines within a cell at an end of a link bundle.

5. The method of claim 4, wherein the step routing further comprises the step of determining a routing choice table for each real machine.

6. The method of claim 4, wherein the multicast distribution is according to the cellule distribution table and a message distribution tag including a flagged list of virtual machines.

7. The method of claim 5, wherein the routing choice table selects machines and links according to one of random choice, round-robin least busy, least-busy, preserve message order, and preserve message order by hashing on origin identification.

8. The method of claim 5, wherein the step of determining a routing choice table further includes the step of determining a failover route for redirecting a message.

9. The method of claim 5, wherein the step of determining a routing choice table further includes the step of exchanging routing information included in the routing choice table of each machine upon the happening of an event.

10. The method of claim 9, wherein an event includes one of a machine failure and a machine recovery.

11. The method of claim 6, wherein the message distribution tags can be one of compressed, factored between internal and external machines relevant to a sending machine, and compressed and factored.

12. The method of claim 11, further comprising the step of determining an updated message distribution tag for the message relevant to the internal and external machines of the sending machine, wherein the sending machine can be one of the first real machine and a receiving machine for forwarding the message to one or more additional receiving machines.

13. The method of claim 1, further comprising the step of scaling the message handling capacity of the network.

16. The method of claim 15, wherein the routing choice table selects machines and links according to one of random choice, round-robin least busy, least-busy, preserve message order, and preserve message order by hashing on origin identification.

17. The method of claim 15, wherein the step of determining a routing choice table further includes the step of determining a failover route for redirecting a message.

18. The method of claim 15, wherein the step of determining a routing choice table further includes the step of exchanging routing information included in the routing choice table of each machine upon the happening of an event.

19. The method of claim 18, wherein an event includes one of a machine failure and a machine recovery.

20. The method of claim 15, wherein the message distribution tags can be one of compressed, factored between internal and external machines relevant to a sending machine, and compressed and factored.

21. The method of claim 20, further comprising the step of determining an updated message distribution tag for the message relevant to the internal and external machines of the sending machine, wherein the sending machine can be one of the first real machine and a receiving machine for forwarding the message to one or more additional receiving machines.

22. The method of claim 15, further comprising the step of scaling the message handling capacity of the network.

14. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for the multicast distribution of a message from a first real machine through a network of message processing machines to one or more message receiving machines, wherein the network is organized into two or more cells including machines, and wherein one or more links between cells comprise link bundles, the method steps comprising:

selecting a spanning tree rooted in the cell containing the first real machine, and comprised of the cells and the link bundles;

determining one or more cells for receiving the message based on the selected spanning tree and the location of the receiving machines;

selecting one or more routes from among the machines and links within the cells and link bundles to a next cell;

routing the message to the receiving cells in the spanning tree; and

delivering the message to each receiving machine within the receiving cells.

15. A method for the multicast distribution of a message from a first real machine through a network of message processing machines to one or more message receiving machines, wherein the network is organized into two or more cells including machines, and wherein one or more links between cells comprise link bundles, the method comprising the steps of:

selecting a spanning tree rooted in the cell containing the first real machine, and comprised of the cells and the link bundles;

determining one or more cells for receiving the message based on the selected spanning tree and the location of the receiving machines;

selecting one or more routes from among the machines and links within the cells and link bundles to a next cell, wherein a link is one of a virtual link between two virtual machines, and a real link between two real machines;

routing the message to the receiving cells in the spanning tree;

delivering the message to each receiving machine within the receiving cells;

implementing one or more virtual machines within a real machine; and

routing the message through the selected spanning tree according to precomputed cellule distribution tables associated with the each real machine, wherein a cellule comprises one or more virtual machines within a cell at an end of a link bundle, a routing choice table corresponding to each real machine, and a message distribution tag including a flagged list of virtual machines.