Method and system for designing ring-based telecommunications networks

• US 7,668,184 B2
• Filed: 10/02/2006
• Issued: 02/23/2010
• Est. Priority Date: 02/12/2001
• Status: Expired due to Term

• Current Assignee: Tellabs Operations Incorporated (Infinera Corp.)
• Original Assignee: Tellabs Operations Incorporated (Infinera Corp.)
• Inventors: Mills, James D., Lin, Philip J., Chow, Timothy Y.
• Primary Examiner(s): Patel; Jayanti K
• Assistant Examiner(s): CAMPBELL, MATTHEW T
• Application Number:
  US11/537,721
• Publication Number:
  US 20070076636A1
• Time in Patent Office: 1,240 Days
• Field of Search: 370/222, 370/223, 370/258, 370403-406, 370/254, 709/251, 398/4
• US Class Current: 370/404
• CPC Class Codes: H04J 14/0227 Operation, administration, maintenance or provisioning [OAMP] of WDM networks, e.g. media access, routing or wavelength allocation
• CPC Class Codes: H04J 14/0241 Wavelength allocation for communications one-to-one, e.g. unicasting wavelengths
• CPC Class Codes: H04J 14/0283 WDM ring architectures
• CPC Class Codes: H04J 14/0284 WDM mesh architectures
• CPC Class Codes: H04J 14/0286 WDM hierarchical architectures
• CPC Class Codes: H04J 14/0295 Shared protection at the optical channel (1:1, n:m)
• CPC Class Codes: H04J 2203/0042 Ring
• CPC Class Codes: H04J 2203/0055 Network design, dimensioning, topology or optimisation
• CPC Class Codes: H04L 12/28 characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks] wireless communication networks H04W ; arrangements for dividing the transmission path H04W40/00
• CPC Class Codes: H04L 12/42 Loop networks

Abstract

A method and system for designing a bi-connected ring-based network is provided, which designs from scratch or converts an existing network to a dual-homed ring-based network. The network covers the locations capable of being bi-connected with one or more cycles/rings. The traffic demand is then routed via the cycles, in such a way so as to minimize the amount of network traffic management equipment required.

Claims

1. A method for designing a bi-connected ring-based network comprising:

receiving a list of locations where network traffic is at least one of originated and delivered;

receiving a list of pairs of directly connected locations, each defining a corresponding network traffic carrying connection including one or more signal carrying connections between each of the directly connected locations, and a capacity for each of the network traffic carrying connections;

receiving a list of traffic demand between each of the listed pairs of locations;

determining a dual homed cover including one or more dual homed cycles, each cycle comprising a closed loop sequence of directly connected locations and corresponding network traffic carrying connections, wherein each location, which is capable of being bi-connected, is included in at least one of the one or more dual homed cycles;

routing the traffic demand over the one or more cycles via the one or more of the network traffic carrying connections;

at least one of outputting a report and storing a representation containing the designed bi-connected ring-based network;

where determining includes;

finding a list of candidate cycles by finding a minimal length cycle for each unordered pair of locations;

selecting one or more of the candidate cycles from the list and, after routing the traffic demand over the one or more cycles, adding additional traffic carrying capacity for each of the network traffic carrying connections where the routed traffic demand exceeds the available capacity.

2. A method in accordance with claim 1 wherein adding additional traffic carrying capacity includes adding additional signal carrying connections between the corresponding directly connected locations.

3. A method in accordance with claim 2 wherein adding additional signal carrying connections between the corresponding directly connected locations includes routing additional fiber or wire connections between two directly connected locations.

4. A method in accordance with claim 1 wherein adding additional traffic carrying capacity includes increasing the bandwidth of the existing signal carrying connections between the corresponding directly connected locations.

5. A method in accordance with claim 4 wherein increasing the bandwidth of existing signal carrying connections includes compressing multiple data streams onto the same signal carrying connection between the corresponding directly connected locations.

6. A method in accordance with claim 5 wherein compressing multiple data streams onto the same signal carrying connection includes transmitting each of the data streams using a different carrier frequency or wavelength.

7. A method in accordance with claim 1 wherein finding a list of candidate cycles additionally includes removing from the list of candidate cycles any redundant cycles.

8. A method in accordance with claim 1 wherein finding a list of candidate cycles additionally includes removing any cycles containing more than a predetermined maximum number of locations in the cycle sequence.

9. A method in accordance with claim 1 wherein routing the traffic demand includes grooming the traffic demand assigned to the available signal carrying connections of the one or more cycles so as to minimize the amount of network traffic management equipment required for routing the traffic demand.

10. A method in accordance with claim 9 wherein grooming the traffic demand includes grouping network traffic originating from a common source location and being delivered to a common destination location onto the same signal carrying connections.

11. A method in accordance with claim 9 wherein the network traffic management equipment includes one or more of add-drop multiplexers and optical line terminals.

12. A method in accordance with claim 1 where in each of the one or more dual homed cycles has at least one location which is present in no other cycle.

13. A method in accordance with claim 1 wherein the traffic demand to be routed is determined by multiplying an already existing demand between each of the locations by a common multiple.

14. A method of designing networks comprising:

defining and storing a plurality of network nodes;

defining and storing a plurality of traffic limited links between the nodes;

defining a plurality of dual-homed communications rings formed of nodes joined by links;

specifying and storing system traffic;

allocating traffic on the links in accordance with link capacity to support the specified traffic; and

storing a representation of at least the rings in a writeable medium; and

which includes representing the nodes and links as a graph having weighted edges wherein the weightings of the edges correspond to numbers of fibers in respective links,

wherein a pre-stored minimal length criterion is applied to the rings and wherein a set of minimum length rings is selected and stored and which includes defining locations of traffic add/drop ports in accordance with a predetermined criterion.

15. A method as in claim 14 which includes displaying the rings in human discernable form.

16. A method as in claim 14 which includes specifying the rings in a multi-dimensional matrix and storing the matrix in a writeable medium.

17. A method as in claim 14 which includes storing the traffic as a matrix in a writeable medium.

18. A method as in claim 17 which includes establishing those rings which include first and second common nodes, and, allocating traffic between those nodes among those rings.

19. A method as in claim 18 wherein the traffic between those first and second nodes is allocated equally among those rings.

20. A method as in claim 18 which includes establishing rings which include a third node, but not a fourth node and those rings which include the fourth node but not the third node and allocating traffic between those nodes to the respective ones of those rings.

21. A method as in claim 18 which includes establishing a bandwidth parameter for each ring for traffic allocated thereon.

22. A method as in claim 21 which includes establishing a required bandwidth parameter for each link of each ring and storing same in a writeable medium.

23. A method as in claim 17 which includes selecting pairs of nodes shared by respective pairs of rings in support of inter-ring traffic.

24. A method as in claim 23 which includes selecting a minimal length traffic route between first and second nodes in accordance with a pre-determined criterion.

25. A method as in claim 24 which includes assigning a first weight to adjacent vertices in a selected ring and a greater weight to common vertices of first and second rings and wherein traffic between selected vertices is routed on a minimal weight path therebetween.

26. Software pre-stored on a computer readable storage medium, for designing communications networks comprising:

a computer readable storage medium;

a first plurality of stored executable instructions pre-stored on the medium, for receiving information defining a network including a plurality of nodes joined by connecting communications links including an indicium of the number of communications paths in each link and a multi-dimensional representation of a traffic pattern;

a second plurality of stored, executable instructions pre-stored on the medium, for forming a biconnected representation of the network;

a third plurality of stored, executable instructions pre-stored on the medium, for forming a file defining connecting links between nodes; and

a fourth plurality of stored executable instructions pre-stored on the medium, for forming a traffic data file; and

which includes a plurality of instructions pre-stored on the medium, for forming a minimal set of dual-homed rings covering the network in accordance with a predetermined criterion and which includes a plurality of instructions for evaluating intra-ring traffic and inter-ring traffic.

27. Software as in claim 26 which includes a plurality of instructions pre-stored on the medium, for evaluating bandwidth requirements on links of the rings in response to the traffic data file.

28. Software as in claim 26 which includes a plurality of instructions pre-stored on the medium, for minimizing traffic flow between rings.

29. A method comprising:

establishing a plurality of locations of traffic add/drop ports in accordance with a previously determined criterion;

establishing a plurality of dual homed cycles which cover at least some of the locations;

establishing a dual homed cover which includes at least some of the members of the plurality;

selecting one or more cycles, wherein selecting one or more cycles comprises;

rating each cycle;

selecting the best rated cycle;

determining if the selected cycles cover all the locations capable of being bi-connected;

if the selected cycles do not cover all locations capable of being bi-connected, selecting an additional cycle, which is bi-connected with at least one of the previously selected cycles, and which in combination with the previously selected cycles has the best rating, and

repeating the selection process for additional cycles until all locations capable of being bi-connected are covered.