System and method for a multicast network messaging service

• US 7,054,276 B2
• Filed: 02/07/2001
• Issued: 05/30/2006
• 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
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): RYMAN, DANIEL J
• Application Number:
  US09/778,300
• Publication Number:
  US 20020146008A1
• Time in Patent Office: 1,938 Days
• Field of Search: 370/216, 370/217, 370/218, 370/221, 370/225, 370/256, 370/389, 370/390, 370/396, 370400-408
• US Class Current: 370/256
• 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 receiving cells including a message receiving machine on the selected spanning tree;

selecting a cellule in each of the one or more receiving cells to receive the message, wherein each cellule comprises a set of one or more virtual machines within a cell at an end of a link bundle;

selecting a route to each selected cellule from a routing choice table of the first real machine including potential routing choices to reachable cellules relative to the first real machine;

routing the message to each selected cellule in the one or more receiving cells in the spanning tree; and

delivering the message to each message receiving machine within the one or more 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 virtual machine, wherein each cellule distribution table includes a first distribution set of cellules to be used if the message is received from a neighbor in the same cell and a second distribution set of cellules to be used if the message is received from a neighbor in another cell.

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 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.

7. 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.

8. 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.

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

10. 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.

11. The method of claim 10, 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.

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 receiving cells including a message receiving machine on the selected spanning tree;

selecting a cellule in each of the one or more receiving cells to receive the message, wherein each cellule comprises a set of one or more virtual machines within a cell at an end of a link bundle;

selecting a route to each selected cellule from a routing choice table of the first real machine including potential routing choices to reachable cellules relative to the first real machine;

routing the message to each selected cellule in the one or more receiving cells in the spanning tree; and

delivering the message to each message receiving machine within the one or more receiving cells.

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

determining, by the first subscribing client, whether the publishing client is an external neighbor outside a first cell of the first subscribing client or an internal neighbor inside the first cell of the first subscribing client;

forwarding the message from the first subscribing client to an internal subscribing neighbor client upon determining the publishing client to be an external neighbor; and

forwarding the message from the first subscribing client to an external subscribing neighbor client upon determining the publishing client to be an internal neighbor.

16. The method of claim 15, further comprising excluding a subscribing client in a cellule in which the first subscribing client implements a virtual machine, wherein each cellule is a disjoint subset of virtual machines within a cell.

17. The method of claim 15, further comprising excluding a subscribing external neighbor client in the first cell of the first subscribing client upon determining the publishing client to be an external neighbor.

18. The method of claim 15, further comprising excluding a virtual machine of a subscribing client within the first cell of the first subscribing client upon determining the publishing client to be an internal neighbor.

19. The method of claim 15, further comprising:

determining whether a cellule in a second cell of the first subscribing client in which the first subscribing client implements a virtual machine has received the message via a virtual machine of a second subscribing client; and

excluding a subscribing client within the second cell from receiving the message from the first subscribing client.

20. The method of claim 15, further comprising tagging the message, wherein a tag indicates an intended recipient client, whether the message has been received from an internal neighbor or external neighbor, whether the message has been received from an internal neighbor virtual machine or from an external neighbor virtual machine.