Detection of load balanced links in internet protocol networks

• US 20040260755A1
• Filed: 06/19/2003
• Published: 12/23/2004
• Est. Priority Date: 06/19/2003
• Status: Active Grant

• Current Assignee: Arlington Technologies, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Avaya Incorporated
• Inventors: Hill, Bruce W., Rankine, Alastair J., Bardzil, Timothy J.
• Granted Patent: US 7,426,577 B2
• Time in Patent Office: Days
• US Class Current: 709/200
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/046 comprising network management agents or mobile agents therefor
• 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/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

A system for detecting load balancing in a distributed processing network is provided that includes:

(a) a memory 204 comprising a baseline topology 216; and

(b) a processor 208 operable to:

(i) select, from the baseline topology 216, first and second addresses associated with first and second routers 224 and 228, respectively, wherein the first router 224 has an associated first hop count relative to a selected node 200 and the second router 228 an associated second hop count relative to the selected node 200 and wherein the first hop count is less than the second hop count;

(ii) transmit at least one test packet, the at least one test packet having a time to live equal to or greater than the second hop count;

(iii) receive at least one response associated with the test packets; and

(iv) determine, based on the at least one response, whether load balancing is in effect at the first router 224.

Claims

1. A method for detecting load balancing in a distributed processing network, comprising:

providing a baseline topology;

selecting, from the baseline topology, first and second addresses associated with first and second routers, respectively, wherein the first router has an associated first hop count relative to a selected node and the second router an associated second hop count relative to the selected node and wherein the first hop count is less than the second hop count;

transmitting at least one test packet, the at least one test packet having a time to live equal to or greater than the second hop count;

receiving at least one response associated with the test packets; and

determining, based on the at least one response, whether load balancing is in effect at the first router.

2. The method of claim 1, further comprising:

selecting a network object;

identifying a first set of unique addresses within the selected network object;

creating a second set of unique addresses, wherein the second set is the union of the first set and a third set of router interface addresses associated with routers between the selected node and the selected subnetwork, wherein the first and second addresses are included within the third set.

3. The method of claim 2, further comprising:

determining whether the second address is contactable, wherein the network object is an edge subnetwork, and the steps of claims 1 and 2 are repeated for each of a plurality of network objects.

4. The method of claim 1, wherein the time to live is equal to the second hop count, wherein the second hop count exceeds the first hop count by one hop, and wherein the steps of claim 1 are repeated for each of a plurality of routers in a set of routers.

5. The method of claim 1, wherein in the determining step per-packet load balancing is in effect when the at least one test packet is a plurality of test packets having a common source and destination addresses and at least two different routers responded to the at least one test packet.

6. The method of claim 5, further comprising, when per-packet load balancing is in effect:

instantiating a cloud between the first router and a selected subnetwork.

7. The method of claim 1, wherein in the determining step one of per-destination and per-source/destination load balancing is in effect when the at least one test packet is a plurality of test packets having a common source address but differing destination addresses and at least two different routers responded to the at least one test packet.

8. The method of claim 1, wherein the determining step comprises:

first determining whether per-packet load balancing is in effect; and

second determining whether at least one of per-destination and per-source/destination load balancing is in effect.

9. The method of claim 8, further comprising:

determining whether or not asymmetry is present between the first and second routers.

10. A computer readable medium containing instructions operable to perform the steps of claim 1.

11. A logic circuit operable to perform the steps of claim 1.

12. A method for identifying per-packet load balancing, comprising:

providing a baseline topology;

selecting, from the baseline topology, first and second addresses associated with first and second routers, respectively, wherein the first router has an associated first hop count relative to a selected node and the second router an associated second hop count relative to the selected node and wherein the first hop count is less than the second hop count;

transmitting a plurality of test packets from a common source address to a common selected destination address, each of the test packets having a time to live equal to or greater than the second hop count;

receiving a plurality of responses associated with the test packets; and

determining, based on the responses, whether per-packet load balancing is in effect at the first router.

13. The method of claim 12, further comprising:

selecting a subnetwork;

identifying a first set of unique addresses within the selected subnetwork;

creating a second set of unique addresses, wherein the second set is the union of the first set and a third set of router interface addresses associated with routers between the selected node and the selected subnetwork, wherein the first and second addresses are included within the third set.

14. The method of claim 12, further comprising:

determining whether the second address is contactable and wherein the second hop count exceeds the first hop count by one hop.

15. The method of claim 12, wherein the time to live is equal to the second hop count.

16. The method of claim 12, wherein in the determining step per-packet load balancing is in effect when at least two different routers responded to the at least one test packet.

17. The method of claim 12, further comprising, when per-packet load balancing is in effect:

instantiating a cloud between the first router and a selected subnetwork.

18. The method of claim 12, wherein the determining step comprises:

first determining whether per-packet load balancing is in effect; and

second determining whether at least one of per-destination and per-source/destination load balancing is in effect.

19. The method of claim 12, further comprising:

determining whether or not asymmetry is present between the first and second routers.

20. The method of claim 12, further comprising:

selecting, from the baseline topology, a third address associated with a third router, wherein the third router has an associated third hop count relative to the selected node and wherein the second hop count is less than the third hop count;

transmitting a plurality of second test packets from the common source address to the common selected destination address, each of the second test packets having a time to live equal to or greater than the third hop count;

receiving a plurality of second responses associated with the second test packets; and

determining, based on the responses, whether per-packet load balancing is in effect at the second router.

21. A computer readable medium containing instructions operable to perform the steps of claim 12.

22. A logic circuit operable to perform the steps of claim 12.

23. A method for identifying per-packet load balancing, comprising:

providing a baseline topology;

selecting, from the baseline topology, first and second addresses associated with first and second routers, respectively, wherein the first router has an associated first hop count relative to a selected node and the second router an associated second hop count relative to the selected node and wherein the first hop count is less than the second hop count;

transmitting a plurality of test packets from a common source address to a plurality of differing destination addresses, each of the test packets having a time to live equal to or greater than the second hop count;

receiving a plurality of responses associated with the test packets; and

determining, based on the at least one response, whether one of per-destination and per-source/destination packet load balancing is in effect at the first router.

24. The method of claim 23, further comprising:

selecting a subnetwork;

identifying a first set of unique addresses within the selected subnetwork;

creating a second set of unique addresses, wherein the second set is the union of the first set and a third set of router interface addresses associated with routers between the selected node and the selected subnetwork, wherein the first and second addresses are included within the third set.

25. The method of claim 23, further comprising:

determining whether the second address is contactable and wherein the second hop count exceeds the first hop count by one hop.

26. The method of claim 23, wherein the time to live is equal to the second hop count.

27. The method of claim 23, wherein, in the determining step, one of per-destination and per-source/destination load balancing is in effect when at least two different routers responded to the at least one test packet.

28. The method of claim 23, wherein the determining step comprises:

first determining whether per-packet load balancing is in effect; and

second determining whether at least one of per-destination and per-source/destination load balancing is in effect.

29. The method of claim 23, further comprising:

determining whether or not asymmetry is present between the first and second routers.

30. The method of claim 23, further comprising:

selecting, from the baseline topology, a third address associated with a third router, wherein the third router has an associated third hop count relative to the selected node and wherein the second hop count is less than the third hop count;

transmitting a plurality of second test packets from the common source address to the plurality of differing destination addresses, each of the second test packets having a time to live equal to or greater than the third hop count;

receiving a plurality of second responses associated with the second test packets; and

determining, based on the responses, whether per-packet load balancing is in effect at the second router.

31. A computer readable medium containing instructions operable to perform the steps of claim 23.

32. A logic circuit operable to perform the steps of claim 23.

33. A system for detecting load balancing in a distributed processing network, comprising:

(a) a memory comprising a baseline topology; and

(b) a processor operable to;

(i) select, from the baseline topology, first and second addresses associated with first and second routers, respectively, wherein the first router has an associated first hop count relative to a selected node and the second router an associated second hop count relative to the selected node and wherein the first hop count is less than the second hop count;

(ii) transmit at least one test packet, the at least one test packet having a time to live equal to or greater than the second hop count;

(iii) receive at least one response associated with the test packets; and

(iv) determine, based on the at least one response, whether load balancing is in effect at the first router.

34. The system of claim 33, wherein the processor is further operable to:

(v) select a subnetwork;

(vi) identify a first set of unique addresses within the selected subnetwork;

(vii) create a second set of unique addresses, wherein the second set is the union of the first set and a third set of router interface addresses associated with routers between the selected node and the selected subnetwork, wherein the first and second addresses are included within the third set.

35. The system of claim 33, wherein the processor is further operable to:

(v) determine whether the second address is contactable and wherein the second hop count exceeds the first hop count by one hop.

36. The system of claim 33, wherein the time to live is equal to the second hop count.

37. The system of claim 33, wherein the processor is operable to conclude that per-packet load balancing is in effect when the at least one test packet is a plurality of test packets having a common source and destination addresses and at least two different routers responded to the at least one test packet.

38. The system of claim 37, wherein, when per-packet load balancing is in effect, the processor is further operable to:

(v) instantiate a cloud between the first router and a selected subnetwork.

39. The system of claim 33, wherein the processor is operable to conclude that one of per-destination and per-source/destination load balancing is in effect when the at least one test packet is a plurality of test packets having a common source address but differing destination addresses and at least two different routers responded to the at least one test packet.

40. The system of claim 33, wherein the processor is operable in operation (iv) to:

(a) first determine whether per-packet load balancing is in effect; and

(b) second determine whether at least one of per-destination and per-source/destination load balancing is in effect.

41. The system of claim 40, wherein the processor is further operable to:

(v) determine whether or not asymmetry is present between the first and second routers.