Detection of load balanced links in internet protocol netwoks

• US 7,426,577 B2
• Filed: 06/19/2003
• Issued: 09/16/2008
• Est. Priority Date: 06/19/2003
• Status: Active Grant

• Current Assignee: Arlington Technologies, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Avaya Technology Corporation Miami Lakes FLA US
• Inventors: Hill, Bruce W., Rankine, Alastair J., Bardzil, Timothy J.
• Primary Examiner(s): Etienne; Ario
• Assistant Examiner(s): Nano; Sargon N
• Application Number:
  US10/601,158
• Publication Number:
  US 20040260755A1
• Time in Patent Office: 1,916 Days
• Field of Search: 709/223, 709/238, 709/239, 709/241, 709/248
• US Class Current: 709/248
• 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 is provided that includes a memory 204 comprising a baseline topology 216; and a processor 208 that selects, 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 higher second hop count relative to the selected node 200, transmit test packets having a time to live equal to or greater than the first hop count, receive responses associated with the test packets, and determine, based on the response, whether load balancing is in effect at the first router 224.

Claims

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

(a) providing a baseline network topology;

(b) selecting, from the baseline network 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;

(c) 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 first hop count;

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

(e) applying the following rules;

(E1) when all of the responses are from a common router, concluding that per-packet load balancing is not in effect; and

(E2) when the responses are from different routers, concluding that per-packet load balancing is in effect.

2. The method of claim 1, 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.

3. The method of claim 1, further comprising:

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

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

5. 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.

6. The method of claim 1, further comprising:

determining whether or not an assymetric link is present between the first and second routers.

7. The method of claim 1, further comprising:

selecting, from the baseline network 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.

8. A computer readable medium containing processor executable instructions operable to perform the steps of claim 1.

9. The method of claim 1, wherein the time to live is incremented to the second hop count and wherein steps (c) through (e) are subsequently repeated with respect to the second router.

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

(a) providing a baseline network topology;

(b) selecting, from the baseline network 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;

(c) 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 first hop count;

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

(e) applying the following rules;

(E1) when all of the responses are from a common router, concluding that at least one of per-destination and per-source/destination load balancing is not in effect; and

(E2) when the responses are from different routers, concluding that at least one of per-destination and per-source/destination load balancing is in effect.

11. The method of claim 10, 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.

12. The method of claim 10, further comprising:

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

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

14. The method of claim 10, wherein step (e) 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.

15. The method of claim 10, further comprising:

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

16. The method of claim 10, further comprising:

selecting, from the baseline network 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.

17. The method of claim 10, wherein the time to live is incremented to the second hop count and steps (c) through (e) are subsequently repeated with respect to the second router.

18. A computer readable medium containing processor executable instructions operable to perform the steps of claim 10.

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

(a) a memory comprising a baseline network topology; and

(b) a processor operable to;

(i) select, from the baseline network 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 first and second sets of test packets, the test packets having a time to live equal to or greater than the first hop count, wherein the first set of test packets are from a common source address to a common selected destination address and the second set of test packets are from a common source address to a plurality of differing destination addresses;

(iii) receive responses to the first and second sets of test packets; and

(iv) apply the following rules;

(A) when all of the responses to the first set of test packets are from a common router, concluding that no per-packet load balancing is in effect;

(B) when the responses to the first set of test packets are from a different routers, concluding that per-packet load balancing is in effect;

(C) when all of the responses to the second set of test packets are from a common router, concluding that at least one of per-destination and per-source/destination load balancing load balancing is not in effect;

(B) when the responses to the second set of test packets are from different routers, concluding that at least one of per-destination and per-source/destination load balancing is in effect.

20. The system of claim 19, 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.

21. The system of claim 19, 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.

22. The system of claim 19, wherein the time to live is incremented to equal the second hop count and operations (ii)-(iv) repeated using the incremented time to live.

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

24. The system of claim 19, 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.

25. The system of claim 24, wherein the processor is further operable to:

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

26. The system of claim 19, wherein the time to live is incremented to the second hop count and operations (ii) through (iv) are subsequently repeated with respect to the second router.

27. The system of claim 19, wherein the process is further operable to:

(v) select the second address, the second address being logically adjacent to the first address;

(vi) access at least one router table;

(vii) select a first link positioned logically between the first and second addresses; and

(viii) apply the following rules;

when the first link has differing metrics for differing directions of traversing the first link, the first link is deemed to be asymmetric;

when packets have differing hops when traversing the first link in differing directions, the first link is deemed to be asymmetric.

28. A method, comprising:

(a) providing a set of device addresses associated with a plurality of routers, the plurality of routers being interposed between a testing node and a selected network object;

(b) selecting, from the set of device addresses, a first device address, wherein the first device address is a first hop count from the testing node and a second device address, in the set of device addresses, is a second hop count from the testing node and wherein the first hop count is less than the second hop count;

(c) transmitting a first set of test packets to at least one of (i) the first device address and (ii) one or more selected destination addresses, each member of the first set of test packets having a Time To Live (“

TTL”

) equal to or greater than the first hop count, wherein the test device on the one hand and the one or more selected destination addresses on the other are located logically on either side of the first device address;

(d) transmitting a second set of test packets to multiple destination addresses, each member of the second set of test packets having a TTL equal to or greater than the first hop count, wherein the test device on the one hand and each of the multiple destination addresses on the other are located logically on either side of the first device address;

(e) receiving a plurality of responses to the first and second sets of test packets;

(f) applying the following rules;

(F1) when all of the responses to the first set of test packets are from a router associated with the selected device address, concluding that per-packet load balancing is not in effect;

(F2) when one or more of the responses to the first set of test packets are from a router other than the router associated with the selected device address, concluding that per-packet load balancing is in effect;

(F3) when all of the responses to the second set of test packets are from the router associated with the selected device address, concluding that at least one of per-destination and per-source/destination load balancing is not in effect;

(F4) when one or more of the responses to the second set of test packets are from a router other than the router associated with the selected device address, concluding that at least one of per-destination and per-source/destination load balancing is in effect; and

(g) updating a network topology to reflect the results of steps (e) and (f).

29. The method of claim 28, wherein a device address is at least one of a router and a router interface and wherein step (a) comprises:

(A1) selecting, from a network object set comprising a plurality of network object addresses corresponding to a plurality of network objects, a first network object address associated with a first network address;

(A2) generating a set E comprising device addresses associated with routers logically located in the first network object and a device address of a router logically adjacent the first network object; and

(A3) generating a set D comprising device addresses in set E and device addresses located between the testing node and the first network object, wherein the set of device address in step (a)is set D.

30. The method of claim 28, wherein, after step (b), the first device address is pinged to determine if the first device address is valid and, when the first device address is not valid, steps (c) and (d) are not performed.

31. The method of claim 28, wherein the TTL is equal to the first hop count and wherein the at least one of (i) the first device address and (ii) one or more selected destination addresses is (i) the first device address.

32. The method of claim 28, wherein the plurality of test packets have a common destination address and TTL, and wherein the common destination address is an edge subnet address.

33. The method of claim 32, further comprising:

(h) determining whether an asymmetric link is located between the testing node and the one or more selected destination addresses.

34. The method of claim 33, wherein step (h) comprises the substeps:

(H1) selecting a second device address logically adjacent to the first device address;

(H2) accessing at least one router table;

(H3) selecting a first link positioned logically between the testing node and second device address; and

(H3) applying the following rules;

(H3i) when the first link has differing metrics for differing directions of traversing the first link, the first link is deemed to be asymmetric;

(H3ii) when packets have differing hops when traversing the first link in differing directions, the first link is deemed to be asymmetric.

35. The method of claim 28, wherein in step (f) it is first determined whether per-packet load balancing exists and second whether at least one of per-destination and per-source/destination load balancing exists.

36. The method of claim 28, wherein the TTL is incremented to the second hop count and wherein steps (c) through (h) are subsequently repeated with respect to second device address.

37. A computer readable medium containing processor executable instructions operable to perform the steps of claim 28.