Distributed node migration between routing domains

• US 8,934,366 B2
• Filed: 07/16/2012
• Issued: 01/13/2015
• Est. Priority Date: 04/20/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hui, Jonathan W., Hong, Wei, Paek, Jeongyeup, Buonadonna, Philip
• Primary Examiner(s): ROSE, KERRI M
• Application Number:
  US13/550,146
• Publication Number:
  US 20130279365A1
• Time in Patent Office: 911 Days
• Field of Search: 370229-231, 370/252, 370/254, 370/400, 709223-225, 709/238, 709/239, 709/241, 709/242, 455436-439
• US Class Current: 370/252
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion

Abstract

In one embodiment, a device connected to a network receives at a network interface a first network size indicator for a first network and a second network size indicator for a second network. A difference between the first network size indicator and the second network size indicator is determined and a switching probability is calculated if the difference between the network size indicators is greater than a predetermined network size difference threshold. The device may then migrate from the first network to the second network based on the switching probability.

Claims

1. A method, comprising:

receiving, at a network interface of a device connected to a first network, a first network size indicator for the first network;

receiving, at the network interface, a second network size indicator for a second network;

determining, using a processor, a difference between the first network size indicator and the second network size indicator;

calculating, via the processor, a switching probability if the difference between the first network size indicator and the second network size indicator is greater than a predetermined network size difference threshold, the switching probability calculated based on at least a normalized difference between the first network size indicator and the second network size indicator and a weighting factor; and

migrating the device from the first network to the second network based on the switching probability.

2. The method of claim 1, wherein the switching probability is calculated as,

3. The method of claim 2, wherein the weighting factor is between 0 and 1.

4. The method of claim 2, wherein the weighting factor is between 0 and 0.5.

5. The method of claim 1, further comprising the steps of:

prior to calculating the switching probability, delaying for a predetermined switch hold time;

receiving, at the network interface, a new second network size indicator for the second network;

determining, using a processor, a difference between the first network size indicator and the new second network size indicator; and

calculating the switching probability if the difference between the first network size indicator and the new second network size indicator is greater than the predetermined network size difference threshold.

6. The method of claim 1, further comprising the steps of:

receiving at the network interface a first path cost for the first network;

receiving at the network interface a second path cost for the second network;

determining, using the processor, a difference between the first path cost and the second path cost; and

calculating, via the processor, the switching probability if the difference between the first network size indicator and the second network size indicator is greater than a predetermined network size difference threshold and the difference between the first path cost and the second path cost is greater than a predetermined path cost threshold.

7. The method of claim 1, further comprising the steps of:

receiving at the network interface a first resource factor for the first network; and

receiving at the network interface a second resource factor for the second network;

wherein

the switching probability is calculated as,

8. The method of claim 1, further comprising the steps of:

receiving at the network interface a first traffic rate indicator for the first network; and

calculating, using the processor, a local traffic rate comprising a moving window average of traffic generated at the device;

wherein

the switching probability is calculated as,

9. An apparatus, comprising:

a network interface adapted to communicate over a network;

a processor configured to communicate with the network interface; and

a memory configured to communicate with the processor, the memory having instructions stored thereon that, in response to execution by the processor, cause the processor to perform operations comprising;

receiving a first network size indicator for a first network and a second network size indicator for a second network;

determining a difference between the first network size indicator and the second network size indicator;

calculating a switching probability if the difference between the first network size indicator and the second network size indicator is greater than a predetermined network size difference threshold, the switching probability calculated based on at least a normalized difference between the first network size indicator and the second network size indicator and a weighting factor; and

migrating from the first network to the second network based on the switching probability.

10. The apparatus of claim 9, wherein the switching probability is calculated as,

11. The apparatus of claim 10, wherein the weighting factor is between 0 and 1.

12. The apparatus of claim 10, wherein the weighting factor is between 0 and 0.5.

13. The apparatus of claim 9, wherein the network interface is a radio transceiver, a powerline communication, or a wireless link.

14. The apparatus of claim 9, wherein the network is a local area network, a wide area network, a wireless ad-hoc network, a smart object network, a field area network, or a neighborhood area network.

15. The apparatus of claim 9, further comprising the steps of:

prior to calculating the switching probability, delaying for a predetermined switch hold time;

receiving, at the network interface, a new second network size indicator for the second network;

determining, using a processor, a difference between the first network size indicator and the new second network size indicator; and

calculating the switching probability if the difference between the first network size indicator and the new second network size indicator is greater than the predetermined network size difference threshold.

16. The apparatus of claim 9, further comprising the operations of:

receiving at the network interface a first path cost for the first network and a second path cost for the second network;

determining a difference between the first path cost and the second path cost; and

calculating the switching probability if the difference between the first network size indicator and the second network size indicator is greater than a predetermined network size difference threshold and the difference between the first path cost and the second path cost is greater than a predetermined path cost threshold.

17. The apparatus of claim 9, further comprising the operation of:

receiving a first resource factor for the first network and a second resource factor for the second network;

wherein

the switching probability is calculated as,

18. The apparatus of claim 9, further comprising the operations of:

receiving a first traffic rate indicator for the first network; and

calculating a local traffic rate comprising a moving window average of traffic generated at the apparatus;

wherein

the switching probability is calculated as,

19. A tangible non-transitory computer-readable storage medium having computer-executable instructions stored thereon that, when executed by a processor, cause the processor to perform operations comprising:

receiving a first network size indicator for a first network and a second network size indicator for a second network;

determining a difference between the first network size indicator and the second network size indicator;

calculating a switching probability if the difference between the first network size indicator and the second network size indicator is greater than a predetermined network size difference threshold, the switching probability calculated based on at least a normalized difference between the first network size indicator and the second network size indicator and a weighting factor; and

migrating from the first network to the second network based on the switching probability.

20. The computer-readable storage medium of claim 19, wherein the switching probability is calculated as,