Parallelizing Peer-to-Peer Overlays Using Multi-Destination Routing

• US 20090116484A1
• Filed: 09/08/2006
• Published: 05/07/2009
• Est. Priority Date: 09/08/2005
• Status: Abandoned Application

• Current Assignee: Panasonic Corporation (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Buford, John
• Application Number:
  US11/991,633
• Publication Number:
  US 20090116484A1
• Time in Patent Office: Days
• US Class Current: 370/392
• 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 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1046 Joining mechanisms
• CPC Class Codes: H04L 67/1048 Departure or maintenance mechanisms
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services

Abstract

A method is provided for parallelizing overlay operations in an overlay network. The method includes: identifying an overlay operation having a parallel messaging scheme; determining a destination address for each parallel message in the messaging scheme; encoding each destination address into a data packet; and transmitting the data packet over the overlay network using a multi-destination, multicast routing protocol.

Claims

1. A method for parallelizing overlay operations in an overlay network, comprising:

identifying an overlay operation having a parallel messaging scheme;

determining a destination address for each message in the messaging scheme;

formatting a data packet with each of destination addresses; and

transmitting the data packet over the overlay network using a multi-destination, multicast routing protocol.

2. The method of claim 1 further comprises transmitting the data packet in accordance with the Explicit Multicast (Xcast) protocol.

3. The method of claim 1 further comprises receiving the data packet at a routing device and forwarding the data packet using a multi-destination, multicast routing protocol.

4. The method of claim 3 wherein forwarding the data packet further comprises

identifying a next hop for each of the destination addresses in the data packet;

replicating the data packet for each identified next hop;

modifying the destination addresses listed in each data packet so that each data packet only contains the destination addresses which are to be routed through the next hop associated with the data packet; and

forwarding each modified data packet to an applicable next hop.

5. The method of claim 1 further comprises

defining an outgoing message queue at a node in the overlay network;

adding messages to the queue which are associated with an overlay operation;

identifying messages in the queue having different destinations within the overlay network but contain overlapping content;

combining the identified messages into a single data packet prior to transmitting the data packet over the overlay network.

6. The method of claim 5 wherein combining the identified messages further comprises formatting a destination address for each of the different destinations into a header of the data packet.

7. A method for parallelizing overlay operations in an overlay network, comprising:

defining an outgoing message queue at a node in the overlay network;

adding messages to the queue;

identifying messages in the queue having different destinations within the overlay network but containing overlapping content;

combining the identified messages into a single multicast data packet; and

transmitting the multicast data packet from the node using a multi-destination, multicast routing protocol.

8. The method of claim 7 wherein combining the identified messages further comprises encoding a destination address for each of the different destinations into a header of the data packet.

9. The method of claim 8 further comprises combining the identified messages unless the list of destination addresses exceeds a size limit

10. The method of claim 7 further comprises combining the identified messages unless a payload of the data packet exceeds a size limit.

11. The method of claim 7 further comprises transmitting a message in the queue using a unicast routing protocol when a maximum queueing delay metric associated with the message is exceeded.

12. The method of claim 7 further comprises transmitting messages which do not contain overlapping content using a unicast routing protocol.

13. The method of claim 7 further comprises transmitting the data packet in accordance with the Explicit Multicast (Xcast) protocol.

14. A messaging scheme for an overlay network, comprising:

a host node in the overlay network operable to perform at least one overlay operation having parallel messages, wherein the host node determines a destination address for each parallel message, encodes each destination address into a single data packet and transmits the data packet using a multi-destination, multicast routing protocol; and

a plurality of routers residing in an underlying network and operable to forward the data packet to each destination address in accordance with the multi-destination, multicast routing protocol.

15. The messaging scheme of claim 14 wherein each of the routers are adapted to receive the data packet and operable to identify a next hop for each of the destination addresses in the data packet, replicate the data packet for each identified next hop, modify the destination addresses listed in each data packet so that each data packet only contains the destination addresses which are to be routed through the next hop associated with the data packet, and forward each modified data packet to an applicable next hop.

16. The messaging scheme of claim 14 wherein the multi-destination, multicast routing protocol is further defined as Explicit Multicast (Xcast) protocol.

17. A messaging scheme for an overlay network having a plurality of nodes, comprising:

maintaining a hierarchical tree structure that defines data paths between nodes in the overlay network;

configuring nodes in the overlay network to forward data packets in accordance with a multi-destination, multicast routing protocol; and

transmitting data packets between nodes in accordance with the hierarchical tree structure using the multi-destination, multicast routing protocol.

18. The messaging scheme of claim 17, wherein the multi-destination, multicast routing protocol is further defined as the Explicit Multicast (Xcast) protocol.