Multiplex communications – Fault recovery – Bypass an inoperative channel
Reexamination Certificate
2000-08-18
2004-12-07
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Fault recovery
Bypass an inoperative channel
C370S254000, C370S406000, C398S005000, C398S058000, C709S221000
Reexamination Certificate
active
06829216
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates generally to the field of telecommunications and more specifically to a method and system for designing a network.
BACKGROUND OF THE INVENTION
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.
SUMMARY OF THE INVENTION
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.
REFERENCES:
patent: 5170482 (1992-12-01), Shu et al.
patent: 5297137 (1994-03-01), Ofek et al.
patent: 5533016 (1996-07-01), Cook et al.
patent: 6108311 (2000-08-01), Ramaswami et al.
patent: 6122283 (2000-09-01), Lee
patent: 6331905 (2001-12-01), Ellinas et al.
patent: 6646989 (2003-11-01), Khotimsky et al.
A. Kershenbaum, et al.; “Mentor: An Algorithm for Mesh Network Topological Optimization and Routing;”IEEE Transactions on Communications, vol. 39, No. 4; pp. 503-513, Apr. 1991.
H. Harai, et al.; “Topological Design of WDM Networks for Accommodating Wavelength Paths;”Technical Report of IEICE; pp. 13-18.
J. Fingerhut, et al.; “Designing Minimum Cost Nonblocking Communication Networks;” Washington University Department of Computer Science; WUCS-96-06; all, Feb. 5, 1996.
G. Li, et al.; “The Partition Coloring Problem and its Application to Wavelength Routing and Assignment;” College of William and Mary Department of Computer Science; all.
D. Hochbaum; “Approximation Algorithms for NP-Hard Problems;” PWS Publishing Company, pp. 94-143, 1995.
D. Kreher, et al.; “Combinatorial Algorithms: Generation, Enumeration, and Search;” CRC Press; pp. 105-145, 1998.
D. Bertsekas; “Network Optimization: Continuous and Discrete Models;” pp. 467-511, 1998.
R. Cahn; “Wide Area Network Design;” Morgan Kaufmann Publishers; pp. 205-265, 1998.
Baker & Botts L.L.P.
Hitachi Telecom (U.S.A.), Inc.
Hsu Alpus H.
LandOfFree
Method and system for designing a network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for designing a network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for designing a network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3284851