This invention relates generally to the field of telecommunications and more specifically to a method and system for designing a network.
Telecommunications networks allow parties and systems at different locations to communicate with each other. A network includes an arrangement of nodes and links. The nodes serve as points of contact into the network and perform switching, control, and other functions of the network. The links provide communication between the nodes. Data travels along paths that include the links and nodes.
Known methods for network design include exhaustive methods and tree-finding methods. Exhaustive methods generate multiple routing assignments for the paths, individually check the routing assignments for optimal assignments, and select a routing assignment. These methods, however, are generally inefficient and slow. Tree-finding methods utilize heuristics to select a tree representing a network and then attempt to adjust the tree to satisfy network demands. These methods, however, typically fail to provide optimal solutions that satisfy network demands.
In accordance with the present invention, a method and system for designing a network are provided that substantially eliminate or reduce the disadvantages and problems associated with previous systems and methods.
According to one embodiment of the present invention, 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. Each edge couples at least two vertices representing paths of which only one path can 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.
Technical advantages of the present invention include providing an improved method and system for designing networks. In a particular embodiment, network demands are represented to design an optimized network. The optimized network meets the network demands while using minimal node and link resources. Other embodiments of the invention may provide additional technical advantages. In one embodiment, an improved method and system for upgrading an existing network to meet new network demands are provided. In the embodiment, existing resources are fixed in the representation, while candidate resources are added if selected.
Another technical advantage of one embodiment is a method and system for designing a network that satisfies path protection demands are provided. In the embodiment, a representation of the candidate network represents both working and protection paths. An optimized arrangement of the working and protection paths are determined from the representation.
Other technical advantages are readily apparent to one skilled in the art from the following figures, descriptions, and claims.