METHODS AND APPARATUS TO DESIGN A SURVIVABLE INTERNET PROTOCOL LINK TOPOLOGY

• US 20110085445A1
• Filed: 10/14/2009
• Published: 04/14/2011
• Est. Priority Date: 10/14/2009
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Klincewicz, John, Choudhury, Gagan
• Granted Patent: US 8,681,654 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• 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

Abstract

Methods and apparatus to design a survivable Internet Protocol link topology are disclosed. An example method to generate a network topology is described, which includes identifying a plurality of potential express links based on a first subset of a plurality of physical links coupling a plurality of communication network nodes, wherein one or more of the potential express links includes a network layer link traversing more than one of the physical links, determining an amount of network layer traffic that may be carried on a first potential express link, selecting the first potential express link as a chosen express link based on at least one of the traffic or a first number of network layer links on the physical links, adding the chosen express link to a list of express links, generating a plurality of network topologies by selecting one or more different numbers of express links from the list of express links, and selecting one of the generated network layer topologies based on a cost of the generated network layer topologies.

Claims

1. A method to generate a network topology, comprising:

identifying a plurality of potential express links based on a first subset of a plurality of physical links coupling a plurality of communication network nodes, wherein one or more of the potential express links comprises a network layer link traversing more than one of the physical links;

determining an amount of network layer traffic that may be carried on a first potential express link;

selecting the first potential express link as a chosen express link based on at least one of the traffic or a first number of network layer links on the physical links;

adding the chosen express link to a list of express links;

generating, using a microprocessor, a plurality of network topologies by selecting one or more different numbers of express links from the list of express links; and

selecting one of the generated network layer topologies based on a cost of the generated network layer topologies.

2. A method as defined in claim 1, wherein determining the amount of network layer traffic comprises:

selecting a traffic element comprising two of the communication network nodes and a traffic demand;

identifying a path between the traffic element nodes, the path comprising a subset of the communication network nodes;

determining whether the subset of the communication network nodes includes endpoint nodes of the first potential express link; and

adding the traffic element to the traffic when the subset of communication network nodes includes the endpoint nodes.

3. A method as defined in claim 1, wherein selecting the first potential express link comprises determining the first number of the network layer links on the physical links that result from choosing the first potential express link, and choosing the first potential express link when the first number of the network layer links associated with the first potential express link is lower than numbers of network layer links associated with other potential express links.

4. A method as defined in claim 3, further comprising choosing the first potential express link when the first number of the network layer links associated with the first potential express link is equal to a second number of the network layer links associated with one or more second potential express links and lower than the other potential express links and the traffic associated with the first potential express link is higher than traffic associated with the one or more second potential express links.

5. A method as defined in claim 3, wherein the first number of the network layer links comprises the lowest number of network layer links on any of the physical links.

6. A method as defined in claim 1, wherein the first number of the network layer links comprises a number of network layer links on a shared risk link group, wherein the shared risk link group comprises one or more of the physical links that carry one or more network layer links in common.

7. A method as defined in claim 1, further comprising determining a topology capacity associated with selecting the express links, wherein the cost is based on the topology capacity.

8. A method as defined in claim 7, wherein determining the topology capacity comprises determining a capacity for the network layer links associated with the physical links and the selected express links.

9. A method as defined in claim 1, further comprising receiving a physical link topology and a plurality of traffic elements, wherein the traffic elements correspond to traffic sent between the plurality of communication network nodes via the physical links.

10. A method as defined in claim 1, wherein the chosen express link comprises a network layer link traversing a plurality of physical links.

11. (canceled)

12. (canceled)

13. An apparatus, comprising:

a topology database to store a plurality of physical links between a plurality of communication network nodes;

a potential express links database to store a plurality of potential express links based on a subset of the plurality of communication network nodes;

an express link identifier to identify the plurality of potential express links based on the topology database;

a traffic evaluator to determine an amount of network layer traffic on a first potential express link;

an express link evaluator coupled to the traffic evaluator to select the first potential express link as a chosen express link based on at least one of the potential traffic or a number of network layer links on the physical links; and

a topology evaluator coupled to the express link evaluator to generate a plurality of network layer topologies by selecting one or more different numbers of express links from a list of express links, and to select one of the generated topologies based on a cost.

14. An apparatus as defined in claim 13, further comprising a traffic database to store a plurality of traffic elements, wherein the traffic elements correspond to traffic demands between the plurality of communication network nodes via the physical links, wherein the express link identifier identifies the plurality of potential express links based on the traffic elements.

17. An apparatus as defined in claim 13, wherein the topology evaluator generates a first network topology comprising a plurality of network layer links corresponding to the plurality of physical links in the topology database and one or more of the top express links in the list of chosen express links.

18. An apparatus as defined in claim 13, wherein the traffic evaluator determines the potential traffic by:

selecting a traffic element comprising two of the communication network nodes and a traffic demand;

identifying a path between the traffic element nodes, the path comprising a second subset of the communication network nodes;

determining whether the second subset includes endpoint nodes of the first potential express link; and

adding the traffic element to the potential traffic when the second subset includes the endpoint nodes.

15. (canceled)

16. (canceled)

19. (canceled)

20. (canceled)

21. An article of manufacture comprising machine readable instructions which, when executed, cause a machine to:

identify a plurality of potential express links based on a first subset of a plurality of physical links coupling a plurality of communication network nodes;

determine an amount of network layer traffic on a first potential express link;

select the first potential express link as a chosen express link based on at least one of the traffic or a first number of network layer links on the physical links;

add the chosen express link to a list of express links;

generate a plurality of network topologies by selecting one or more different numbers of express links from the list of express links; and

select one of the generated network layer topologies based on a cost of the generated network layer topologies.

22. An article of manufacture as defined in claim 21, wherein determining the potential traffic comprises:

selecting a traffic element comprising two of the communication network nodes and a traffic demand;

identifying a path between the traffic element nodes, the path comprising a subset of the communication network nodes;

determining whether the subset of communication network nodes includes endpoint nodes of the first potential express link; and

adding the traffic element to the traffic when the subset of communication network nodes includes the endpoint nodes.

23. An article of manufacture as defined in claim 21, wherein selecting the first potential express link comprises determining the first number of the network layer links on the physical links that result from choosing the first potential express link, and choosing the first potential express link when the first number of the network layer links associated with the first potential express link is lower than numbers of network layer links associated with other potential express links.

26. An article of manufacture as defined in claim 21, wherein the instructions further cause the machine to determine a topology capacity associated with selecting the express links, wherein the cost is based on the topology capacity.

27. An article of manufacture as defined in claim 26, wherein determining the topology capacity comprises determining a capacity for the network layer links associated with the physical links and the selected express links.

28. An article of manufacture as defined in claim 21, wherein the instructions further cause the machine to receive a physical link topology and a plurality of traffic elements, wherein the traffic elements correspond to traffic demands sent between the plurality of communication network nodes via the physical links.

24. (canceled)

25. (canceled)

29. (canceled)

30. (canceled)

31. (canceled)

32. (canceled)