Method of finding rings for optimal routing of digital information

• US 8,463,947 B2
• Filed: 01/14/2008
• Issued: 06/11/2013
• Est. Priority Date: 08/28/2002
• Status: Active Grant

• Current Assignee: Tellabs Operations Incorporated (Infinera Corp.)
• Original Assignee: Tellabs Operations Incorporated (Infinera Corp.)
• Inventors: Jenkins, David W.
• Primary Examiner(s): JAKOVAC, RYAN J
• Application Number:
  US12/013,785
• Publication Number:
  US 20080175153A1
• Time in Patent Office: 1,975 Days
• Field of Search: 709/238, 709/251, 709/200, 370/258
• US Class Current: 709/251
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 12/423 with centralised control, e.g. polling
• CPC Class Codes: H04L 12/4637 Interconnected ring systems
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network

Abstract

A method for planning a network having a plurality of nodes. The method may include determining all possible rings in the network satisfying a predetermined condition and calculating a utilization score for each possible ring based on a combination of predetermined selection criteria. The method may include selecting the possible ring with the highest utilization score and determining whether there are remaining nodes among the plurality of nodes that are not included in the selected possible ring. The method may further include selecting another possible ring if it is determined there are remaining nodes.

Claims

1. A method for planning a network having a plurality of nodes, comprising:

determining all rings in the network satisfying a predetermined condition;

calculating a utilization score for each of the determined rings satisfying the predetermined condition based on a combination of predetermined selection criteria, the calculating being performed by multiplying each of a plurality of weight factors by a magnitude of the predetermined selection criteria and summing resultant weighted values for all the selection criteria;

selecting a first ring among the determined rings satisfying the predetermined condition, the first ring having the highest utilization score among the utilization scores calculated for the determined rings satisfying the predetermined condition;

determining whether there are remaining nodes among the plurality of nodes that are not included in the first ring; and

selecting a second ring among the determined rings satisfying the predetermined condition if it is determined there are remaining nodes,

wherein the determination of all rings satisfying the predetermined condition and the determination of whether there are remaining nodes are performed on a network planning system that includes at least one computer.

2. A method according to claim 1, wherein the predetermined selection criteria include at least two of:

amount of traffic in a ring, cost of ring components, ring circumference, and number of nodes per ring.

3. A method according to claim 2, further comprising creating a matrix containing traffic demands, wherein the calculating uses the matrix.

4. A method according to claim 3, further comprising updating the traffic demands in the matrix by removing demands satisfied by the first ring.

5. A method according to claim 4, further comprising successively selecting unselected rings among the determined rings satisfying the predetermined condition until all the traffic demands in the matrix are satisfied.

6. A method according to claim 2, wherein the calculating further comprises allocating the weight factors to respective predetermined selection criteria.

7. A method according to claim 6, wherein the weight factors are allocated according to a criticality of each of the predetermined selection criteria.

8. A method according to claim 6, wherein the weight factors are allocated automatically.

9. A method according to claim 6, wherein the weight factors are allocated by a user.

10. An apparatus adapted to plan a network having a plurality of nodes, comprising:

at least one memory device to store information about the nodes; and

a processor adapted to

(i) determine all rings in the network satisfying a predetermined condition,

(ii) calculate a utilization score for each of the determined rings satisfying the predetermined condition based on a combination of predetermined selection criteria, by multiplying each of a plurality of weight factors by a magnitude of the predetermined selection criteria and summing resultant weighted values for all the selection criteria,

(iii) select a first ring among the determined rings satisfying the predetermined condition, the first ring having the highest utilization score among the utilization scores calculated for the determined rings satisfying the predetermined condition,

(iv) determine whether there are remaining nodes among the plurality of nodes that are not included in the first ring, and

(v) select a second ring among the rings satisfying the predetermined condition if it is determined there are remaining nodes.

11. A network planning apparatus according to claim 10, wherein the predetermined selection criteria include at least two of:

amount of traffic in a ring, cost of ring components, ring circumference, and number of nodes per ring.

12. A network planning apparatus according to claim 11, wherein the processor is further adapted to allocate the weight factors to respective predetermined selection criteria, according to a criticality of each of the predetermined selection criteria.

13. A network planning apparatus according to claim 11, wherein the processor is further adapted to create a matrix containing traffic demands, and update the traffic demands by removing demands satisfied by the first ring.

14. A network planning apparatus according to claim 12, wherein the weight factors are allocated by a user.

15. A network planning apparatus according to claim 13, wherein the processor is adapted to successively select unselected rings among the determined rings satisfying the predetermined condition until all the traffic demands in the matrix are satisfied.

16. A method for planning a network having a plurality of nodes, comprising:

determining all rings in the network satisfying a predetermined condition;

selecting a first ring among the determined rings satisfying the predetermined condition based on predetermined selection criteria;

determining whether there are remaining nodes among the plurality of nodes that are not included in the selected ring; and

selecting a second ring among the determined rings satisfying the predetermined condition if it is determined there are remaining nodes,

wherein the determination of all rings satisfying the predetermined condition and the determination of whether there are remaining nodes are performed on a network planning system that includes at least one computer, and at least one of the selectings includes multiplying each of a plurality of weight factors by a magnitude of the predetermined selection criteria and summing resultant weighted values for all the selection criteria.

17. A method according to claim 16, wherein the predetermined selection criteria is amount of traffic in a ring.

18. A method according to claim 16, further comprising creating a matrix containing network conditions, wherein the selecting uses the matrix.

19. A method according to claim 18, further comprising successively selecting unselected rings among the determined rings satisfying the predetermined condition until all the network conditions in the matrix are satisfied.

20. A method according to claim 16, wherein the at least one of the selectings further comprises allocating the weight values to respective predetermined selection criteria.