Tree-based ordered multicasting method
First Claim
1. A concurrent, multicast communication method for transmitting data packets over a network of interconnected nodes, comprising:
- ordering messages on a multicast tree; and
performing aggregation of ordering primitives across said tree to minimize control traffic among nodes.
2 Assignments
0 Petitions
Accused Products
Abstract
A method for performing end-to-end “tree-based ordered multicasting” (TOM) which ensures collective integrity and consistency of distributed operations, and which is applicable to distributed multiparty collaboration and other multipoint applications. The TOM protocol performs cascaded total ordering of messages among on-tree hosts en route from senders to receivers, and does not require the building of a separate propagation graph to compute ordering information. TOM elects sequencer nodes dynamically based on address extensions of the multicast tree. Message ordering is performed by multicasting a message from each source node to receivers, unicasting a control message from a source node across a primary node to an ordering node for the designated multicast group or transmission in the tree, determining a binding sequence number for the message and a multicast to the receiver group, and delivering messages at end hosts according to the agreed-upon sequence numbers.
-
Citations
56 Claims
-
1. A concurrent, multicast communication method for transmitting data packets over a network of interconnected nodes, comprising:
-
ordering messages on a multicast tree; and
performing aggregation of ordering primitives across said tree to minimize control traffic among nodes. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 21, 22, 28, 29, 30, 31, 32, 33, 34, 35)
-
-
14. A concurrent, multicast communication method for transmitting data packets over a network of interconnected nodes, comprising:
-
ordering messages on a multicast tree in a diffusing computation;
wherein said messages are ordered on corresponding delivery paths from sources to receivers; and
wherein each node is responsive only to its parent and child nodes in said tree. - View Dependent Claims (23, 24, 25, 26)
-
-
27. A concurrent, multicast communication method for transmitting data packets over a network of interconnected nodes, comprising:
-
ordering messages on a multicast tree;
multicasting a message from a source to a receiver set; and
sending ordering information for the message to a common node on a tree elected as an ordering node for said receiver set. - View Dependent Claims (36, 37, 38, 39)
-
-
40. A concurrent, multicast communication method for transmitting data packets over a network of interconnected nodes, comprising:
-
multicasting a message from a source node to a receiver group;
unicasting a control message from a source node across a primary node to an ordering node for a designated multicast group or transmission, wherein said primary node aggregates messages from their subtrees and hence staggers the ordering process upward within the tree;
determining a binding sequence number for this message and a multicast to the receiver group; and
delivering messages at end hosts according to agreed-upon sequence numbers. - View Dependent Claims (41, 42, 43, 44)
-
-
45. A concurrent, multicast communication method for transmitting data packets over a network of interconnected nodes, comprising:
-
multicasting a message from a source node to a receiver group;
unicasting a control message from a source node across a primary node to an ordering node for a designated multicast group or transmission, wherein said primary node aggregates messages from their subtrees and hence staggers the ordering process upward within the tree;
determining a binding sequence number for this message and a multicast to the receiver group; and
delivering messages at end hosts according to agreed-upon sequence numbers;
wherein said messages are delivered in an order agreed-upon by all hosts. - View Dependent Claims (46, 47, 48)
-
-
49. A concurrent, multicast communication method for transmitting data packets over a network of interconnected nodes, comprising:
-
multicasting a message from a source node to a receiver group;
unicasting a control message from a source node across a primary node to an ordering node for a designated multicast group or transmission, wherein said primary node aggregates messages from their subtrees and hence staggers the ordering process upward within the tree;
determining a binding sequence number for this message and a multicast to the receiver group; and
delivering messages at end hosts according to agreed-upon sequence numbers;
wherein said messages are delivered in an order agreed-upon by all hosts. - View Dependent Claims (50, 51, 52)
-
-
53. A concurrent, multicast communication method for transmitting data packets over a network of interconnected nodes, comprising:
-
multicasting a message from a source node to a receiver group;
unicasting a control message from a source node across a primary node to an ordering node for a designated multicast group or transmission, wherein said primary node aggregates messages from their subtrees and hence staggers the ordering process upward within the tree;
determining a binding sequence number for this message and a multicast to the receiver group;
delivering messages at end hosts according to agreed-upon sequence numbers;
wherein said messages are delivered in an order agreed-upon by all hosts; and
wherein, for each set of messages destined to a particular multicast group, or set of hosts, an ordering node is elected by virtue of being the node having label that is the longest common prefix among all node labels in the receiver set. - View Dependent Claims (54, 55)
-
-
56. A concurrent, multicast communication method for transmitting data packets over a network of interconnected nodes, comprising:
-
multicasting a message from a source node to a receiver group;
unicasting a control message from a source node across a primary node to an ordering node for a designated multicast group or transmission, wherein said primary node aggregates messages from their subtrees and hence staggers the ordering process upward within the tree;
determining a binding sequence number for this message and a multicast to the receiver group;
delivering messages at end hosts according to agreed-upon sequence numbers;
wherein said messages are delivered in an order agreed-upon by all hosts;
wherein, for each set of messages destined to a particular multicast group, or set of hosts, an ordering node is elected by virtue of being the node having label that is the longest common prefix among all node labels in the receiver set; and
wherein each ordering node gathers sequence number bids set en route by primary nodes deciding on a globally valid number, and multicasts the respective message to the receiver set with a final and binding sequence number directive.
-
Specification