System and method for providing topology and reliability constrained low cost routing in a network

• US 20070242608A1
• Filed: 04/12/2006
• Published: 10/18/2007
• Est. Priority Date: 04/12/2006
• Status: Active Grant

• Current Assignee: AT&T Knowledge Ventures, L.P. (AT&T, Inc.)
• Original Assignee: AT&T Knowledge Ventures, L.P. (AT&T, Inc.)
• Inventors: Chen, Kaiyan, Li, Zhi, Ou, Canhui, Manthoulis, Orestis, Chiang, Mung, Yi, Xiaochuan
• Granted Patent: US 7,768,935 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

Various embodiments of the disclosed subject matter provide methods and systems to generate node-disjoint routing paths from a root node to each node in a network node set, identify potential intermediate office node (IO) candidate pairs from the generated node-disjoint routing paths, generate a per central office node (CO) serving cost estimate for each IO candidate pair, and identify a low cost IO candidate pair having at least two node-disjoint paths to the root node without traversing nodes along a diverse path between the low cost IO candidate pair and subtending CO nodes.

Claims

1. A method comprising:

generating node-disjoint routing paths from a root node to each node in a network node set;

identifying potential intermediate office node (IO) candidate pairs from the generated node-disjoint routing paths;

generating a per central office node (CO) serving cost estimate for each IO candidate pair; and

identifying a low cost IO candidate pair having at least two node-disjoint paths to the root node without traversing nodes along a diverse path between the low cost IO candidate pair and subtending CO nodes.

2. The method as claimed in claim 1 wherein the per CO serving cost estimate for each IO candidate pair includes an equipment cost.

3. The method as claimed in claim 1 wherein the per CO serving cost estimate for each IO candidate pair includes a transmission cost.

4. The method as claimed in claim 1 further including identifying a plurality of low cost IO candidate pairs to produce a low cost network design.

5. The method as claimed in claim 1 wherein the network node set supports voice, data, or video communication services.

6. The method as claimed in claim 1 wherein the root node is a video headend office (VHO).

7. The method as claimed in claim 1 wherein the low cost IO candidate pair receives a multicast data stream from the root node and serves a unicast data stream to subtending CO nodes.

8. The method as claimed in claim 1 wherein the low cost IO candidate pair is identified without reference to an existing design in a green-field design scenario.

9. The method as claimed in claim 1 wherein the low cost IO candidate pair is identified based on an existing design in a brown-field design scenario.

10. The method as claimed in claim 1 wherein the per central office node (CO) serving cost estimate is based in part on a network traffic forecast.

11. An article of manufacture comprising at least one machine readable storage medium having one or more computer programs stored thereon and operable on one or more computing systems to:

generate node-disjoint routing paths from a root node to each node in a network node set;

identify potential intermediate office node (IO) candidate pairs from the generated node-disjoint routing paths;

generate a per central office node (CO) serving cost estimate for each IO candidate pair; and

identify a low cost IO candidate pair having at least two node-disjoint paths to the root node without traversing nodes along a diverse path between the low cost IO candidate pair and subtending CO nodes.

12. An article of manufacture according to claim 11 wherein the per CO serving cost estimate for each IO candidate pair includes an equipment cost.

13. An article of manufacture according to claim 11 wherein the per CO serving cost estimate for each IO candidate pair includes a transmission cost.

14. The article of manufacture according to claim 11 further operable to identify a plurality of low cost IO candidate pairs to produce a low cost network design.

15. The article of manufacture according to claim 11 wherein the network node set supports voice, data, or video communication services.

16. The article of manufacture according to claim 11 wherein the root node is a video headend office (VHO).

17. The article of manufacture according to claim 11 wherein the low cost IO candidate pair is further operable to receive a multicast data stream from the root node and to serve a unicast data stream to subtending CO nodes.

18. The article of manufacture according to claim 11 wherein the low cost IO candidate pair is identified without reference to an existing design in a green-field design scenario.

19. The article of manufacture according to claim 11 wherein the low cost 10 candidate pair is identified based on an existing design in a brown-field design scenario.

20. The article of manufacture according to claim 11 wherein the per central office node (CO) serving cost estimate is based in part on a network traffic forecast.

21. A system comprising:

a processor;

a memory coupled to the processor to store information related to a network node set; and

a low cost network design generator, operably coupled with the processor and the memory, operable to generate node-disjoint routing paths from a root node to each node in a network node set, identify potential intermediate office node (IO) candidate pairs from the generated node-disjoint routing paths, generate a per central office node (CO) serving cost estimate for each IO candidate pair; and

identify a low cost IO candidate pair having at least two node-disjoint paths to the root node without traversing nodes along a diverse path between the low cost IO candidate pair and subtending CO nodes.

22. A system according to claim 21 wherein the per CO serving cost estimate for each IO candidate pair includes an equipment cost.

23. A system according to claim 21 wherein the per CO serving cost estimate for each IO candidate pair includes a transmission cost.

24. The system according to claim 21 wherein the low cost network design generator being further operable to identify a plurality of low cost 10 candidate pairs to produce a low cost network design.

25. The system according to claim 21 wherein the network node set supports voice, data, or video communication services.

26. The system according to claim 21 wherein the root node is a video headend office (VHO).

27. The system according to claim 21 wherein the low cost IO candidate pair is further operable to receive a multicast data stream from the root node and to serve a unicast data stream to subtending CO nodes.

28. The system according to claim 21 wherein the low cost IO candidate pair is identified without reference to an existing design in a green-field design scenario.

29. The system according to claim 21 wherein the low cost IO candidate pair is identified based on an existing design in a brown-field design scenario.

30. The system according to claim 21 wherein the per central office node (CO) serving cost estimate is based in part on a network traffic forecast.

31. A network comprising:

a root node; and

a plurality of low cost intermediate office node (IO) pairs having at least two node-disjoint paths to the root node without traversing nodes along a diverse path between each of the low cost IO node pairs and subtending central office (CO) nodes, a cost of each IO node pair being based in part upon a CO serving cost estimate for each IO node pair.

32. A network according to claim 31 wherein the CO serving cost estimate for each IO node pair includes an equipment cost.

33. A network according to claim 31 wherein the CO serving cost estimate for each IO node pair includes a transmission cost.

34. The network according to claim 31 wherein the network supports voice, data, or video communication services.

35. The network according to claim 31 wherein the root node is a video headend office (VHO).