METHOD OF FINDING RINGS FOR OPTIMAL ROUTING OF DIGITAL INFORMATION

• US 20080175153A1
• Filed: 01/14/2008
• Published: 07/24/2008
• 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.
• Granted Patent: US 8,463,947 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• 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 possible rings in the network satisfying a predetermined condition;

calculating a utilization score for each possible ring based on a combination of predetermined selection criteria;

selecting the possible ring with the highest utilization score;

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

selecting another possible ring if it is determined there are remaining nodes.

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 selected possible ring.

5. A method according to claim 4, further comprising successively selecting another possible ring until all the traffic demands in the matrix are satisfied.

6. A method according to claim 2, wherein the calculating comprises allocating a weight factor to each of the predetermined selection criteria and calculating the utilization score based on a weighted combination of the predetermination selection criteria.

7. A method according to claim 6, wherein the weight factors are allocated according to the 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 determine all possible rings in the network satisfying a predetermined condition,

calculate a utilization score for each possible ring based on a combination of predetermined selection criteria,

select the possible ring with the highest utilization score,

determine whether there are remaining nodes among the plurality of nodes that are not included in the selected possible ring, and

select another possible ring 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 allocates a weight factor to each of the predetermined selection criteria, according to the criticality of each of the predetermined selection criteria and calculates the utilization score based on a weighted combination of the predetermination selection criteria.

13. A network planning apparatus according to claim 11, wherein the processor creates a matrix containing traffic demands and updates the traffic demands by removing demands satisfied by the selected 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 successively selects another possible ring 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 possible rings in the network satisfying a predetermined condition;

selecting a possible ring based on predetermined selection criteria;

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

selecting another possible ring if it is determined there are remaining nodes.

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 another possible ring until all the network conditions in the matrix are satisfied.

20. A method according to claim 16, wherein the selecting comprises allocating a weight value to each of the predetermined selection criteria and calculating a utilization score based on a weighted combination of the predetermination selection criteria.