Method for optimizing a network having virtual circuit routing over virtual paths

• US 5,274,643 A
• Filed: 12/11/1992
• Issued: 12/28/1993
• Est. Priority Date: 12/11/1992
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: StrataCom, Inc. (Cisco Systems, Inc.)
• Inventors: Fisk, Benjamin W.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): VU, HUY DUY
• Application Number:
  US07/989,093
• Time in Patent Office: 382 Days
• Field of Search: 370/54, 370/94.1, 370/94.3, 370/60, 370/60.1, 370/17, 370/13.1, 370/112, 370/94.2, 370/95.1, 370/118, 379/221, 379/207, 340/825.52, 340/825.03, 340/826, 340/827, 395/800
• US Class Current: 370/238
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: H04J 2203/0051 Network Node Interface, e.g. tandem connections, transit switching
• CPC Class Codes: H04L 2012/5619 Network Node Interface, e.g. tandem connections, transit switching
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections
• CPC Class Codes: H04Q 3/62 for connecting to private branch exchanges

Abstract

Virtual circuits are routed and grouped into virtual paths during an interactive topology design process. Virtual circuits are assigned to virtual paths that provide minimum cost to each pass through a topology design. Virtual paths are dispersed into subgroups that minimize bandwidth consumption and maximize routing flexibility. This topology optimization process is constrained to minimize use of network resources.

Claims

1. A method for designing a telecommunications network topology comprising at least one site, each site comprising a number of nodes and virtual circuits between nodes, each node comprising resources for accommodating a predetermined number of virtual circuits and a predetermined number of virtual path connections, each virtual path comprising a predetermined number of virtual circuits, said method comprising the steps of:

configuring an initial network topology;

optimizing the network topology by utilizing the virtual path resources at the nodes comprising the steps of;

grouping virtual circuits at each node into virtual paths for routing comprising a step of merging virtual circuits at each node which have common characteristics including common node points into virtual paths, and

if the number of virtual paths at a node does not exceed the predetermined number of virtual paths at the node, splitting at least one virtual path at the node into two new virtual paths until the predetermined number of virtual paths at the node is reached, to maximize resource usage and efficiency;

wherein the network topology incorporating virtual paths is optimized.

2. The method as set forth in claim 1, wherein the step for merging virtual circuit comprises the steps of:

determining a cost measure for each virtual circuit between nodes;

sorting the virtual circuits by the cost measure;

examining each virtual circuit in sorted order; and

merging the virtual circuit into a virtual path as a virtual path member if the maximum number of virtual path members has not been reached and if the virtual circuit has the same characteristics as other virtual path members.

3. The method as set forth in claim 2, wherein the cost measure is determined according to a measure of consumption of a link bandwidth between nodes and a minimum routing between nodes.

4. The method as set forth in claim 3, wherein the measure of consumption of link bandwidth between nodes is determined according to a minimum information rate for the node.

5. The measure as set forth in claim 3, wherein the minimum routing between nodes is determined according to a minimum hop.

6. The method as set forth in claim 2, wherein the step for determining the cost measure for each virtual circuit between nodes comprises the step of computing the cost measure according to the following equation:

space="preserve" listing-type="equation">VIRTUAL CIRCUIT.sub.-- COST=MIR * MIN.sub.-- HOP

wherein VIRTUAL CIRCUIT_-- COST represents the cost measure, MIR represents the minimum information rate has the network and MIN_-- HOP represents the minimum hop for the virtual circuit for the network topology.

7. The method as set forth in claim 2, wherein if a virtual circuit does not have the same characteristics as other virtual path members, said method further comprises the step of establishing an additional virtual path if the predetermined number of virtual paths for a node has not been exceeded, said virtual path having the characteristics of the virtual circuit, such that the virtual circuit becomes the leader for the virtual path.

8. The method as set forth in claim 2, wherein the step of splitting comprises the steps of:

determining if a virtual path can be split by determining if both end nodes of the virtual path have not exceeded the predetermined number of virtual paths specified for a node and there is more than one virtual circuit in the virtual path;

if the virtual path can be split, moving a portion of the virtual circuits to a new virtual path.

9. The method as set forth in claim 8, wherein alternate virtual path members are moved into a new virtual path.

10. The method as set forth in claim 9, wherein the virtual circuit having a lowest cost measure becomes a virtual path leader for the new virtual path.

11. The method as set forth in claim 8, further comprising the step of sorting the virtual paths according to a virtual paths cost measure and examining each virtual path in sorted order to determine if the virtual path can be split.

12. The method as set forth in claim 11, wherein the virtual path cost measure is determined according to the minimum number of hops to route the virtual path and bandwidth utilization.

13. The method as set forth in claim 8, wherein the step of splitting is continued until the resources at the node are exhausted or until all possible virtual paths have been split.

14. The method as set forth in claim 1, wherein a site comprises a plurality of nodes, and steps of grouping virtual circuits and splitting virtual paths are performed on a site by site basis.

15. A method for designing a telecommunications network topology comprising multiple sites and virtual circuits between sites, each site comprising a number of nodes, each node comprising resources for accommodating a predetermined number of virtual circuits and a predetermined number of virtual path connections, each virtual path comprising a predetermined number of virtual circuits, said method comprising the steps of:

(a) configuring an initial network topology;

(b) optimizing the network topology by utilizing the virtual path resources at the nodes comprising the steps of;

grouping the virtual circuits at each node into virtual paths for routing comprising the steps of;

determining a cost measure for each virtual circuit between nodes, and

merging virtual circuits at each node which have common characteristics including common node points into virtual paths, and if the number of virtual paths at a node does not exceed the predetermined number of virtual paths at the node, splitting at least one virtual path at the node into two new virtual paths until the predetermined number of virtual paths at the node is reached, to maximize resource usage and efficiency;

(c) determining a network cost for the topology;

(d) configuring an alternate topology based on the network cost;

(e) repeating steps (b), (c) and (d) until the network cost is minimized;

wherein the network topology incorporating virtual paths is optimized.

16. A telecommunications network designed to incur minimum costs comprising at least one site comprising a plurality of nodes and virtual circuits between nodes, said network comprising at least one virtual path between nodes, each virtual path comprising a plurality of virtual circuits having like characteristics, the characteristics of the virtual path specified according to the characteristics of the virtual circuit which is a virtual path leader for the virtual path, each node accommodating a maximum number of virtual paths, the number of virtual paths and characteristics of virtual paths specified by merging virtual circuits at each node which have common characteristics including common node points into virtual paths, said virtual circuits merged in order of a cost measure determined for each virtual circuit, and splitting at least one virtual path at the node into two new virtual paths until the maximum number of virtual paths at the node is reached, to distribute resource usage and maximize efficiency.

17. The telecommunications network as set forth in claim 16 wherein the virtual circuit having a lowest cost measure in each new virtual path formed by splitting virtual paths is identified as the virtual path leader for the new virtual path.