Seamlessly switching overlay network relay trees

• US 7,839,798 B2
• Filed: 06/22/2007
• Issued: 11/23/2010
• Est. Priority Date: 06/22/2007
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Tang, Jian, Li, Jiang, Luo, Chong
• Primary Examiner(s): Shah; Chirag G
• Assistant Examiner(s): PERSAUD, AMARNAUTH G
• Application Number:
  US11/766,958
• Publication Number:
  US 20080317044A1
• Time in Patent Office: 1,250 Days
• Field of Search: None
• US Class Current: 370/254
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 65/80 Responding to QoS
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1089 Hierarchical topologies

Abstract

Technologies for switching a set of nodes in an overlay network from one relay tree configuration to another without duplicate packets or packet loss at any of the nodes. A commander node calculates a new relay tree as well as a media stream set configuration for each node in the overlay network, each media stream set corresponding to the new relay tree. Media stream sets include a unique version number or the like that identifies the specific relay tree configuration of which they are a part. Also provided are technologies for associating a media stream with a particular relay tree configuration and the corresponding media stream set of each node in the overlay network.

Claims

1. A system comprising:

a commander node of an overlay network formed over an underlying network, the commander node configured to;

responsive to one or more performance changes of the underlying network, calculate a configuration for a relay tree of the overlay network, wherein the relay tree includes a plurality of nodes forming a sequence traversable by a packet to reach a destination;

calculate multiple media stream set (MSS) configurations for the relay tree, wherein an individual MSS configuration corresponds to an individual node of the plurality of nodes and comprises an MSS configuration version number uniquely identifying the individual MSS configuration and the relay tree;

send the multiple MSS configurations to each of the plurality of nodes;

when a plurality of acknowledgments are received from each of the plurality of nodes within a time-frame, send a switch command to a source node of the plurality of nodes to switch to the relay tree, wherein an individual acknowledgement indicates receipt of a corresponding MSS configuration and creation of an MSS according to the corresponding MSS configuration; and

when at least one acknowledgement is not received from at least one node of the plurality of nodes, calculate another relay tree configuration for another relay tree that does not include the at least one node and calculate other MSS configurations for the another relay tree; and

at least one hardware processor configured to implement the commander node.

2. The system of claim 1, wherein the source node comprises a top-most node of the relay tree.

3. The system of claim 1 further comprising:

a media stream set creator operable to create a MSS based on the individual MSS configuration; and

a MMS router operable to route data packets based on the MSS.

4. The system of claim 3 wherein the MMS router is operable to forward the data packets to an application.

5. The system of claim 3 further comprising a MMS deleter operable to delete the MSS when the MSS is no longer in use.

6. The system of claim 5 wherein the MMS deleter is operable to delete an older MMS when sequence numbers of older data packets corresponding to the older MMS precede a further sequence number of a first data packet corresponding to the MMS.

7. The system of claim 1, wherein the plurality of nodes does not include the commander node.

8. The system of claim 1, wherein the individual MSS configuration further comprises a description of one or more other nodes of the plurality of nodes comprising at least one of:

an inbound link from which the packet will arrive to the individual node or an outbound link to which the individual node will forward the packet.

9. A method implemented at least in part by a computing device, the method comprising:

receiving, on a node, a new media stream set (MMS) configuration from a commander node, the new MMS configuration associated with a new relay tree and comprising;

an MSS configuration version number uniquely identifying the new MSS configuration and the new relay tree; and

a description of one or more other nodes comprising at least one of;

an inbound link from which data packets will arrive to the node or an outbound link to which the node will route the data packets;

creating a new MMS on the node based on the new MMS configuration;

establishing communications with the one or more other nodes as specified by the new MMS, wherein the data packets correspond to the new MMS and are one or both of;

received from the inbound link or routed to the outbound link, as indicated by the new MMS; and

waiting until old data packets associated with an old MMS on the node have been received and then deleting the old MMS.

10. The method of claim 9 further comprising returning an acknowledgement to the commander node, the acknowledgement indicating the node successfully receiving the new MMS configuration and creating the new MMS and establishing communications with the one or more other nodes as specified by the new MMS.

11. The method of claim 9 wherein the waiting includes determining when sequence numbers of the old data packets corresponding to the old MMS set precede a further sequence number of a first data packet of the data packets.

12. The method of claim 9 wherein the new MMS associates port numbers with the new relay tree.

13. The method of claim 12 wherein individual data packets of the date packets are routed via the port numbers indicated by the new MMS.

14. The method of claim 12 wherein the port numbers are used to distinguish between the new relay tree and one or both of:

an old relay tree or any other relay trees.

15. The method of claim 9 wherein the new MMS configuration is associated with the new relay tree using a version number.

16. A method implemented at least in part by a computing device, the method comprising:

responsive to one or more performance changes of an underlying network formed over an underlying network, calculating a configuration for a relay tree of the overlay network, wherein the relay tree includes a plurality of nodes forming a sequence traversable by a packet to reach a destination;

calculating multiple media stream set (MSS) configurations for the relay tree, wherein an individual MSS configuration corresponds to an individual node of the plurality of nodes and comprises an MSS configuration version number uniquely identifying the individual MSS configuration and the relay tree;

sending the multiple MSS configurations to each of the plurality of nodes;

when a plurality of acknowledgments are received from each of the plurality of nodes within a time-frame, sending a switch command to a source node of the plurality of nodes to switch to the relay tree, wherein an individual acknowledgement indicates receipt of a corresponding MSS configuration and creation of an MSS according to the corresponding MSS configuration; and

when at least one acknowledgement is not received from at least one node of the plurality of nodes, calculating another relay tree configuration for another relay tree that does not include the at least one node and calculate other MSS configurations for the another relay tree.

17. The method of claim 16, wherein at least one of calculating the configuration for the relay tree, calculating the multiple MSS configurations, sending the multiple MSS configurations, sending the switch command, or calculating another relay tree configuration is performed by a node other than one of the plurality of nodes.

18. The method of claim 16, wherein the individual MSS configuration further comprises a description of one or more other nodes of the plurality of nodes comprising at least one of:

an inbound link from which the packet will arrive to the individual node or an outbound link to which the individual node will forward the packet.