Method and system for designing a network

• US 6,829,216 B1
• Filed: 08/18/2000
• Issued: 12/07/2004
• Est. Priority Date: 08/18/2000
• Status: Expired due to Fees

• Current Assignee: Hitachi America Limited (Hitachi, Ltd.)
• Original Assignee: Hitachi Telecom (USA), Inc. (Hitachi, Ltd.)
• Inventors: Nakata, Tsuneo
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US09/642,070
• Time in Patent Office: 1,572 Days
• Field of Search: 370/216, 370/225, 370/228, 370/254, 370/255, 370/351, 370/386, 370/400, 370/406, 398/1, 398/2, 398/5, 398/48, 398/49, 398/58, 398/66, 398/68, 709/220, 709/221, 709/238, 709/239, 714/1, 714/2, 714/3, 714/4
• US Class Current: 370/228
• 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/0295 Shared protection at the optical channel (1:1, n:m)
• CPC Class Codes: H04L 41/0663 Performing the actions predefined by failover planning, e.g. switching to standby network elements
• 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

Abstract

A method and system for designing a network includes generating a representation of a candidate network. The representation includes vertices and edges, where each vertex represents a path and each edge couples at least two vertices representing paths of which at most one path can be included in a network. A set of a maximum number of vertices, where no two vertices are coupled by an edge, is determined. The paths represented by the vertices of the set are included in the network.

Claims

1. A method for designing a network, the method comprising:

generating a representation of a candidate network, the representation comprising a plurality of vertices and a plurality of edges, wherein each vertex represents a path between at least two end nodes within the candidate network and each edge couples at least two vertices representing paths of which at most one path can be included in a network;

determining a maximum independent set comprising a maximum number of vertices, wherein no two vertices are coupled by an edge; and

including the paths represented by the vertices of the set in the network.

2. The method of claim 1, wherein:

each path comprises at least one of a plurality of resources; and

the edges comprise a conflict edge, the conflict edge coupling at least two vertices representing paths comprising a conflicting resource.

3. The method of claim 1, further comprising conducting a maximum independent set search to determine the set.

4. The method of claim 1, wherein the network comprises an optical network.

5. The method of claim 1, wherein each path comprises at least two nodes and at least one link coupling the nodes.

6. The method of claim 5, further comprising:

receiving a demand link coupling at least two end nodes; and

generating the representation, wherein the representation comprises a vertex representing a path comprising the end nodes.

7. The method of claim 5, wherein:

the vertices comprise a first vertex representing a first path and a second vertex representing a second path, each path having at least two end nodes, the first path having the same end nodes as the second path; and

the edges comprise a routing edge coupling the first vertex and the second vertex.

8. The method of claim 1, further comprising:

coupling a resource elimination vertex to at least one vertex representing a path comprising an eliminable resource;

selecting the resource elimination vertex as a member of the set; and

eliminating the eliminable resource from the network.

9. The method of claim 1, further comprising:

coupling a resource elimination vertex to at least one vertex representing a path comprising a candidate resource;

determining whether the resource elimination vertex is a member of the set; and

including the candidate resource in the network if the resource elimination vertex is not a member of the set.

10. The method of claim 1, wherein:

the representation comprises a first layer having a first vertex and a second layer having a second vertex, the vertices comprising the first vertex and the second vertex;

the first vertex represents a first path slot of a path;

the second vertex represents a second path slot of the path; and

the edges comprise a routing edge coupling the first vertex and the second vertex.

11. The method of claim 1, wherein:

the representation comprises a working layer having a first vertex and a protection layer having a second vertex, the vertices comprising the first vertex and the second vertex;

the first vertex represents a working path; and

the second vertex represents a protection path, the protection path operable to transmit data in place of the working path.

12. A system for designing a network, the system comprising:

a computer-processable medium; and

logic encoded in the computer-processable medium, the logic operable to;

generate a representation of a candidate network, the representation comprising a plurality of vertices and a plurality of edges, wherein each vertex represents a path between at least two end nodes within the candidate network and each edge couples at least two vertices representing paths of which at most one path can be included in a network;

determine a maximum independent set comprising a maximum number of vertices, wherein no two vertices are coupled by an edge; and

include the paths represented by the vertices of the set in the network.

13. The system of claim 12, wherein:

each path comprises at least one resource; and

the edges comprise a conflict edge coupling at least two vertices representing paths comprising a conflicting resource.

14. The system of claim 12, wherein the logic is operable to conduct a maximum independent set search to determine the set.

15. The system of claim 12, wherein the network includes an optical network.

16. The system of claim 12, wherein each path comprises at least two nodes and at least one link coupling the nodes.

17. The system of claim 16, wherein the logic is operable to:

receive a demand link coupling at least two end nodes; and

generate the representation, wherein the representation comprises a vertex representing a path comprising the end nodes.

18. The system of claim 16, wherein:

the vertices comprise a first vertex representing a first path and a second vertex representing a second path, each path having at least two end nodes, the first path having the same end nodes as the second path; and

the edges comprise a routing edge coupling the first vertex and the second vertex.

19. The system of claim 12, wherein the logic is operable to:

couple a resource elimination vertex to vertices representing paths comprising an eliminable resource;

select the resource elimination vertex as a member of the set; and

eliminate the eliminable resource from the network.

20. The system of claim 12, wherein the computer is operable to:

couple a resource elimination vertex to vertices representing paths comprising a candidate resource;

determine whether the resource elimination vertex is a member of the set; and

include the candidate resource if the resource elimination vertex is not a member of the set.

21. The system of claim 12, wherein:

the representation comprises a first layer having a first vertex and a second layer having a second vertex, the vertices comprising the first vertex and the second vertex;

the first vertex represents a first path slot of a path;

the second vertex represents a second path slot of the path; and

the edges comprise a routing edge coupling the first vertex and the second vertex.

22. The system of claim 12, wherein:

the representation comprises a working layer having a first vertex and a protection layer having a second vertex, the vertices comprising the first vertex and the second vertex;

the first vertex represents a working path; and

the second vertex represents a protection path, the protection path operable to transmit data in place of the working path.

23. A network designed according to the following:

generating a representation of a candidate network, the representation comprising a plurality of vertices and a plurality of edges, wherein each vertex represents a path between at least two end nodes within the candidate network and each edge couples at least two vertices representing paths of which at most one path can be included in a network;

determining a maximum independent set comprising a maximum number of vertices, wherein no two vertices are coupled by an edge; and

including the paths represented by the vertices of the set in the network.

24. The network of claim 23, wherein:

each path comprises at least one of a plurality of resources; and

the edges comprise a conflict edge, the conflict edge coupling at least two vertices representing paths comprising a conflicting resource.

25. The network of claim 23, wherein the network is designed by conducting a maximum independent set search to determine the set.

26. The network of claim 23, wherein the network comprises an optical network.

27. The network of claim 23, wherein each path comprises at least two nodes and at least one link coupling the nodes.

28. The network of claim 27, wherein the network is designed by:

receiving a demand link coupling at least two end nodes; and

generating the representation, wherein the representation comprises a vertex representing a path comprising the end nodes.

29. The network of claim 27, wherein:

the vertices comprise a first vertex representing a first path and a second vertex representing a second path, each path having at least two end nodes, the first path having the same end nodes as the second path; and

the edges comprise a routing edge coupling the first vertex and the second vertex.

30. The network of claim 23, wherein the network is designed by:

coupling a resource elimination vertex to at least one vertex representing a path comprising an eliminable resource;

selecting the resource elimination vertex as a member of the set; and

eliminating the eliminable resource from the network.

31. The network of claim 23, wherein the network is designed by:

coupling a resource elimination vertex to at least one vertex representing a path comprising a candidate resource;

determining whether the resource elimination vertex is a member of the set; and

including the candidate resource in the network if the resource elimination vertex is not a member of the set.

32. The network of claim 23, wherein:

the representation comprises a first layer having a first vertex and a second layer having a second vertex, the vertices comprising the first vertex and the second vertex;

the first vertex represents a first path slot of a path;

the second vertex represents a second path slot of the path; and

the edges comprise a routing edge coupling the first vertex and the second vertex.

33. The network of claim 23, wherein:

the representation comprises a working layer having a first vertex and a protection layer having a second vertex, the vertices comprising the first vertex and the second vertex;

the first vertex represents a working path; and

the second vertex represents a protection path, the protection path operable to transmit data in place of the working path.