Method of and system for managing a SONET ring

[0002] The present application is related to application Ser. No. 09/036,392, filed Mar. 6, 1998, titled Method of Optimal Routing in a Bi-Directional Line Switched SONET Ring, assigned to the assignee of the present Application.

[0003] The present invention relates generally to communication network management, and more particularly to a method of and a system for reconfiguring a SONET ring to maintain optimally balanced demand loading.

[0004] Traditionally, network design, network provisioning and management, and network migration are treated as separate tasks that are often done by different organizations within a carrier. The mandate of the network design task is to optimize the routing and resource allocation in order to obtain a minimum cost network. Network design tends to take a long term view by considering the forecast of traffic at the end of a target. The resulting network design has a potential danger of being far from reality or impossible to implement.

[0005] The network migration planning task is based upon available yearly or quarterly capital budget and decisions tend to focus only on a short-term effects to the network, without considering the overall consequences and the life cycle of the network.

[0006] The network provisioning and management task concentrates on meeting day-to-day circuit provisioning requirements and it tends to use simple rules. More often than not, the decision how circuits are provisioned is based on individual discretion. The effect of a decision to provision circuits and the overall consequences to network utilization are normally not considered or understood in day-to-day operations.

[0007] Consequently, there is a gap between an optimized network design and the actual implementation of the network. This gap results largely because optimized network designs are based on global knowledge of traffic demands and specific ways of routing and bundling those demands for minimizing the total cost of the network. In the actual realization of the network, the demands may turn out to be very different from the original forecasts, and the lack of automation and selecting routes for provisioning circuit demands results in inefficient utilization of network capacities. Thus, given the same traffic volume, the actual realized cost of the network is usually significantly higher than the original estimate.

[0008] As the network evolves, new capacities and new fiber routes are added to the network. At the same time, new requirements on the transmission network come from traffic volume growth and new types of services that have different bandwidths. Quality of service and routing constraints also change the network dynamics.

[0009] Typically, because of difficulties in reconfiguring the network, trunk groups that were misrouted due to lack of capacity at the time of provisioning are not re-routed even when new capacities become available at a later time. Over the course of network evolution, the result is often a disorderly set of traffic routes. Comparing the actual traffic routing pattern against the optimal routing, it is usually found that by reconfiguring the network routing, then plenty of capacity can be squeezed out of the network. By reconfiguring the network, overall utilization will be increased and there may not be a need for adding new capacities to the network. Accordingly, the life cycle cost of the network can be reduced greatly.

[0010] Under a mesh architecture, several ways of reconfiguring a network have been proposed. These include AT&T's “Fully Shared Network” concept and TRLab's “Self-Engineered Network” concept. However, when reconfiguring the whole network, the requirement on synchronization and switching time is quite high and current digital cross connect (DXC) and switch technology essentially do not have the capability to support a real time network wide configuration. The estimated risk and cost of reconfiguration of a transmission network under the mesh architecture is prohibitively high for any carrier to consider this option seriously. Another concern that prohibits reconfiguration in a mesh architecture is that when factoring restoration into the overall configuration scheme, complexities make network reconfiguring virtually impossible. Therefore, though transmission network reconfigurations have been proposed by various research organizations in the past, no one has actually implemented a proposed system.

[0011] Recently, there has been a move away from mesh topology for telecommunications networks toward a ring topology. In a bidirectional line switched ring, the demands on the ring are allowed to be routed on either side of the ring, and capacity for all spans of the ring is required to be the same. A ring topology offers advantages over a mesh topology, primarily in that a ring is self-healing and therefore may be restored in a matter of milliseconds after a failure. However, rings are still subject to becoming poorly routed over the course of ring evolution. As ring demands are provisioned and de-provisioned, certain spans of the ring become congested while other spans become under utilized. It is therefore an object of the present invention to provide a management system that reconfigures a ring in real time.

[0012] The present invention provides a method of and system for managing a SONET ring. The method of the present invention computes an optimally balanced demand loading for the SONET ring and generates an updated time slot assignment map for each node of the SONET ring based upon the optimally balanced demand loading. The method causes each node of the SONET ring to switch substantially simultaneously to its updated time slot assignment map, thereby reconfiguring the SONET ring.

[0013] The method computes an optimally balanced demand loading for the SONET ring by computing a demand loading for the SONET ring such that each link of said SONET ring carries substantially the same demand as every other link of said SONET ring. The method causes each node of the SONET ring to switch substantially simultaneously to its updated time slot assignment map by downloading to each node of said SONET ring its updated time slot assignment map along with a designated time to make the substitution. The method freezes provisioning activity on the SONET ring while reconfiguring the SONET ring.

[0014] The present invention also provides a method of reconfiguring inter-ring routing by moving circuits from one inter-ring path to another. The method sets up digital cross connect connection for the new path and then downloads to each ring of the network new time slot assignment maps based upon the new path. The method then causes the rings of the new path to switch to the new time slot assignment maps.

[0015] FIG. 1 is block diagram representation of a portion of a network of interconnected rings.

[0016] FIG. 2 is a block diagram of a ring and ring management system according to the present invention.

[0017] FIG. 3 is a pictorial representation of an optical ring.

[0018] FIG. 4 is a high level flowchart of the method of the present invention.

[0019] FIG. 5 is a flowchart of a capacity assignment process of the present invention.

[0020] FIG. 6 is a high level flowchart of the flow routing process of the present invention.

[0021] FIG. 7 is a flowchart of the preprocessing step of FIG. 6.

[0022] FIG. 8 is a flowchart of the processing step A of FIG. 6.

[0023] FIG. 9 is a flowchart of the processing step B of FIG. 6.

[0024] FIG. 10 is a flowchart of the terminating step A of FIG. 6.

[0025] FIG. 11 is a flowchart of the terminating step B of FIG. 6.

[0026] FIG. 12 is a pictorial representation of a demand array according to the present invention.

[0027] FIG. 13 is a pictorial representation of a two-edge cut array according to the present invention.

[0028] FIG. 14 is a pictorial representation of a capacity array according to the present invention.

[0029] Referring now to the drawings, and first to FIG. 1, a portion of a network is designated generally by the numeral 11. Portion 11 includes five bi-directional line switched SONET rings, 13-21. In the illustrated example of FIG. 1, each ring includes four nodes and four links. For example, ring 13 includes nodes that comprise add/drop multiplexors (ADM) 23-31 that are inner-connected by links 33-39. Although each ring of 13-21 of portion 11 includes four nodes, those skilled in the art will recognize that FIG. 1 is for purposes of illustration and that a bi-directional line switched SONET ring may contain any number of nodes up to about sixteen.

[0030] As is well known to those skilled in the art, ADMs 23-31 add and drop circuits to and from ring 13 according a time slot assignment (TSA) map. A TSA map is associated with each ADM 23-31. The TSA map specifies, for each time slot, whether traffic is to be added/dropped at a particular ADM.

[0031] Network portion 11 of FIG. 1 provides for both intra-ring and inter-ring routing. In intra-ring routing, demands originate and terminate at nodes of same ring. For example, a demand between subscribers associated with ADM's 23 and 31 may be carried clockwise or counter-clockwise around ring 13. In the case of inter-ring routing, demands between subscribers associated with different rings are carried. For example, a demand between a subscriber associated with ADM 23 of ring 13 and a subscriber associated with ADM 41 of ring 21 may be carried on any of several paths through the network. Such a demand may be carried between ring 13 and ring 21 through any one of rings 15-19. For example, a demand may be added to ring 13 at ADM 23 and dropped at ADM 25. A DXC 43 is provided to selectively connect the demand dropped at ADM 25 to either an ADM 45 of ring 17 or an ADM 47 of ring 15. If the demand is added to ring 15 at ADM 47, then the demand is dropped from ring 15 at ADM 49. The demand dropped at ADM 49 is added to ring 21 at ADM 51 through a DXC 53. The DXCs allow the inter-ring routing to be reconfigured in order to balance the ring loading across the network.

[0032] It is desirable that each link of a ring carry substantially the same demand. At the time a ring is designed, the demand loading is typically balanced. However, as circuits on the ring are provisioned and deprovisioned, the demand loading typically becomes unbalanced. The unbalanced loading leads to bottle necks.

[0033] According the present invention, the demand loading of each ring of a network is periodically rebalanced. Rebalancing according to the present invention removes bottle necks in the network and has the effect of squeezing additional capacity out of each ring. Referring to FIG. 2, there is shown a system according to the present invention, which is designated generally by numeral 55. System 55 includes a ring 57 and a network management system 59. Ring 57 includes four ADMs 61-67 inter-connected by links 69-75. Ring 57 is preferably a bi-directional line switched SONET ring. Ring management system 59 includes a computer programmed according to the method of the present invention. Ring management system 59 communicates with each ADM 61-67 through suitable communication links indicated by dashed lines in FIG. 2.

[0034] In the manner known to those skilled in the art, traffic is routed around ring 57 according to working time slot assignment maps at each ADM 61-67. As circuits are provisioned and de-provisioned in ring 57, the time slot assignment maps are modified on a per circuit basis. According to the present invention, ring management system 59 periodically calculates an optimally balanced demand loading for ring 57 and generates for each ADM 61-67 a secondary time slot allocation map based on the optimally balanced demand loading. Ring management system 59 then downloads to each ADM 61-67 the appropriate time slot assignment map along with an instruction to swap the secondary time slot allocation map for the working time slot allocation map. Each ADM 61-67 substantially simultaneously flash cuts from the working time slot assignment map to the secondary time slot assignment map, thereby making the secondary time slot assignment map the new working time slot assignment map. The flash cut operation occurs in about fifty milliseconds so that the load balancing reconfiguration does not affect or disrupt traffic on ring 57.

[0035] The operation of the preferred embodiment of the system of the present invention may be best understood with reference to FIGS. 3-14.

[0036] Referring now to FIG. 3, a ring is designated generally by the numeral 77. Ring 77 includes six nodes n₁-n₆and six links or edges e₁-e₆. Those skilled in the art will recognize that the six node and link ring of FIG. 3 is for purposes of illustration and that optical rings can include any number of nodes up to about sixteen.

[0037] Between each pair of nodes of ring 77 there is a demand. Referring briefly to FIG. 12, there is shown a demand array according to the present invention for ring 77. The demand array of FIG. 12 includes a nodes column 79 and demand column 81. For the sake of clarity, the nodes of column 79 of the demand array of FIG. 10 are referred to by their subscripts.

[0038] The demand between nodes n₁-n₆is carried bi-directionally around ring 77 through link e₁-e₆. For example, the three units of demand between nodes n₁and n₄may be carried clockwise through links e₁-e₃or counterclockwise through link e₄-e₆. Additionally, one unit of the three units of demand can be carried in one direction and the other two units can be carried in the other direction.

[0039] As will be apparent to those skilled in the art, it is not easy to determine the minimum capacity of each link e necessary to route all of the demands or to assign the flow in a ring. The preferred demand load balancing process of the present invention includes two parts. The first part calculates the capacity requirements for satisfying all the demands on the ring. The second part routes demands based upon the capacity generated from the first part.

[0040] The method of the present invention is preferably computer implemented. The data structures utilized in the computer implementation include the demand array of FIG. 12, a two-edge cut array as illustrated in FIG. 13, and a capacity array as illustrated in FIG. 14.

[0041] Referring to FIG. 12, the demand array includes, in addition to node column 79 and demand column 81, a links column 83, which contains a linked list of links that is generated according to the present invention. Referring to FIG. 13, the two-edge cut array includes a two-edge cut column 85 that contains each pair of links of the ring. A two-edge cut is an analytical tool that divides the ring under consideration into two parts. For example, two-edge cut (1,4) is a cut of links e₁and e₄, which divides the nodes of ring 11 into a first subset consisting of nodes n₂-n₄, and a second subset consisting of nodes n₅, n₆, and n₁. An adjacent two-edge cut cuts adjacent links and divides the ring into a first set of nodes consisting of a single node and a second subset consisting of the rest of the nodes. Thus, two-edge cuts (1, 2), (1, 6), (2, 3), (3, 4), (4, 5) and (5, 6) are adjacent two-edge cuts.

[0042] The two-edge cut array of FIG. 13 also includes a capacity column 87, which contains the available capacity of the links of each two-edge cut (e_k, e₁). Capacity column 87 is initially set to zero and it is populated with results of the capacity assignment process of the present invention. The values in capacity column 87 are manipulated during the flow routing process of the present invention.

[0043] The two-edge cut array of FIG. 13 includes a two-edge cut demand column 89. Demand column 89 contains for each two-edge cut (e_k, e_l) a demand D(e_k, e_l) that is the demand between the sets of nodes formed by each two-edge cut (e_k, e_l). Demand column 89 is initially set to zero. The values in demand column 89 are computed in the capacity assignment process of the present invention and recomputed during the flow routing process of the present invention.

[0044] The two-edge cut array of FIG. 13 also includes a cut difference column 91. Cut difference column 25 includes a cut_diff(e_k, e_l) value for each two-edge cut (e_k, e_l). The values of cut difference column 91 are calculated during flow routing processing according to the invention and cut difference column 91 contains the difference between the values of capacity column 87 and demand column 89 for each two-edge cut (e_k, e_l). According to the present invention, a value in cut difference column 91 can never be less than zero.

[0045] The two-edge cut array of FIG. 13 also includes a flag column 93. The values in flag column 93 are initially set to zero. As will be explained in detail hereinafter, a flag is set to one whenever a two-edge cut (e_k, e_l) is processed during a processing step A of flow routing processing of the present invention.

[0046] Referring now to FIG. 14, a capacity array includes a link column 95 and a capacity column 97. Capacity column 97 contains the available capacity of each link e_kof the ring. Capacity column 97 is populated during capacity processing according to the present invention. The values of capacity column 97 are updated during flow routing according to the present invention.

[0047] Referring now to FIG. 4, there is shown a high level flow chart of ring management system processing according to the present invention. The network management system first poll the network elements, at block 98, to make sure that none of the elements is in maintenance or protection mode. If, at decision block 99, each network element is not in a good state, then processing ends. If each network element is OK, then the ring management system freezes provisioning activity, at block 100, to ensure that the demands carried by the ring are stable during reconfiguration. Then, the demand, capacity, and two-edge cut arrays are initialized at block 101 and the ring topology and demand data are loaded at block 103. The demand data is loaded into demand column 81 of FIG. 12. After the ring topology and demand data are loaded, the method of the present invention performs capacity assignment processing, as indicated generally at block 105 and shown in detail with respect to FIG. 5. Then, the method of the present invention performs flow routing, as indicated generally at block 107, and shown in detail with respect to FIG. 6.

[0048] After performing flow routing at block 107, the ring management system of the present invention generates a secondary time slot assignment map for each node of the ring, at block 108. The secondary time slot assignment map is generated from the result of flow routing processing at block 107. Then, the ring management system again polls each network element to make sure none of the elements are in maintenance or protection mode, at block 109. If, at decision block 110, each network element is OK, then the ring management system transmits the respective secondary time slot assignment map to each node with a time to swap the secondary time slot assignment map for the working time slot assignment map of the node, at block 111. Then, the ring management system waits for the time to swap, at block 113, and unfreezes provisioning activity, at block 115.

[0049] Referring now to FIG. 5, the capacity assignment method of the present invention calculates, for each two-edge cut (e_k, e_l), a demand D(e_k, e_l), at block 117. Demand D(e_k, e_l) is equal to the sum of all demands between the subsets of nodes on either side of two-edge cut (e_k, e_l). It will be recalled that a two-edge cut divides the ring into two subsets of nodes. A first set of nodes X is the set of nodes between links e_kand e_l. The second subset of nodes (N-X) is the set of nodes between links e_land e_k. For example, two-edge cut (e₁, e₄) divides the nodes of ring 11 into a subset X consisting of nodes n₁, n₃, and n₄, and a second subset (N-X) consisting nodes n₁, n₅, and n₆. Demand D(e₁, e₄) is equal to the sum of all demands between nodes n₂-n₄and nodes n₅-n₁, which in the illustrated example is equal to thirty-six demand units. Computationally, the capacity assignment process of the present invention calculates the demand D(e_k, e_l) as the sum of all demands D(n_i, n_j) wherein i is greater than k and equal to or less than l and wherein j is greater than l and equal to or less than k.

[0050] As the capacity assignment method of the present invention calculates demands D(e_k, e_l), the capacity assignment method of the present invention inserts a demand D(e_k, e_l) for each two-edge cut (e_k, e_l) into the two-edge cut array of FIG. 13, at block 119. Referring to FIG. 13, the demand values are inserted into demand column 89. Then, the capacity assignment process of the present invention lets z equal the maximum demand D(e_k, e_l) over all two-edge cuts, at block 121. Referring to FIG. 13, the demands D(e_k, e_l) have been computed and inserted into demand column 89. It will be noted that the maximum demand is thirty-seven demand units, which is the demand for two-edge cuts (e₂, e₅) and (e₃, e₆). Referring again to FIG. 5, the capacity assignment process of the present invention lets the capacity c(e) equal to z divided by two, plus 0.5 capacity units, for all edges e of the ring, at block 123. Since the maximum two-edge cut demand is thirty-seven, z is equal to 18.5 capacity units. Accordingly, the capacity for each edge e_kis set to nineteen capacity units and that value is inserted into the capacity column 97 of capacity array of FIG. 14 for each link, at block 125.

[0051] Referring now to FIG. 6, there is shown a high level flow chart of flow routing processing according to the present invention. The flow routing process of the present invention performs preprocessing, as indicated generally at block 127, and shown in detail with respect to FIG. 7. Then, the flow routing process of the present invention checks for three terminating conditions at decision blocks 129-133. At decision block 129, the flow routing process of the present invention tests whether or not the demand D(n_i, n_j) is equal to zero for all node pairs (n_i, n_j). If each value in demand column 81 of FIG. 12 is equal to zero, then there are no more demands to route and the process is finished. If, at decision block 129, not all demands D(n_i, n_j) are equal to zero, then the flow routing process of the present invention tests, at decision block 131 if any capacity c(e) is equal to zero or 0.5. The test of decision block 131 is processed with respect to the capacity array of FIG. 14. If any value in capacity column 97 is equal to zero or 0.5, processing proceeds to a terminating processing step A, as indicated generally at block 135, and shown in detail with respect to FIG. 10.

[0052] The flow routing process of the present invention tests for the third terminating condition at decision block 133, by determining whether any adjacent two-edge cut (e_k, e_k+1) is critical. As will be explained in detail hereinafter, a critical cut is a two-edge cut for which the cut difference is equal to zero or one. A critical adjacent two-edge cut indicates that all commodities remaining have the same origin and the flow routing problem effectively becomes a single commodity problem. If, at decision block 133, an adjacent two-edge cut is critical, then the system performs a terminating process step B, as indicated generally at block 137, and shown in detail with respect to FIG. 11.

[0053] If, at decision block 133, it is determined that there are no terminating conditions, then the flow routing method of the present invention tests, at decision block 139, if any two-edge cut (e_k, e_l) is critical and its flag is set to zero. A two-edge cut (e_k, e_l) is a critical cut if the cut difference cut_diff (e_k, e_l) is equal to zero or one. Referring to FIG. 13, it will be observed that two-edge cuts (e₂, e₅) and (e₃, e₆) are critical cuts. It will also be observed that in FIG. 13, the flag for those two-edge cuts is set to zero.

[0054] Referring again to FIG. 6, if there is a critical cut (e_k, e_l) for which the flag is set to zero, then the flow routing method of the present invention performs a processing step A, as indicated generally at block 141, and shown in detail with respect to FIG. 8. If there is no critical cut for which the flag is set to zero, then the flow routing method of the present invention performs a processing step B, as indicated generally at block 143, and shown in detail with respect to FIG. 7. After performing processing steps A or B, processing returns to decision block 129 to test for the terminating conditions. Thus, the flow routing method of the present invention performs either processing step A at block 141, or processing step B at block 143, until the occurrence of a terminating condition.

[0055] Referring now to FIG. 7, there is shown preprocessing according to the flow routing method of the present invention. During preprocessing, the method calculates for each two-edge cut (e_k, e_l) a capacity c(e_k) plus c(e_l), at block 145. The calculation of block 145 is done with reference to the capacity array of FIG. 14. Referring to FIG. 14, initially, the available capacity of each link is nineteen capacity units. Thus, the capacity for each pair of links is equal to thirty-eight capacity units. The preprocessing method of the present invention inserts the calculated capacity into the two-edge cut array of FIG. 13, at block 147. Preprocessing calculates the cut difference cut_diff(e_k, e_l) for each two-edge cut (e_k, e_l), at block 149. Referring to FIG. 13, the cut differences in cut difference column 91 range from one to nineteen.

[0056] Referring again to FIG. 7, preprocessing tests, at decision block 151, if there is a critical cut. If the capacity routing process of the present invention is performed following the capacity assignment process of the present invention, there will always be a critical cut. However, the flow routing process of the present invention may be performed with a preassigned set of capacities, not formed according to the capacity assignment method of the present invention. The flow routing method of the present invention requires at least one critical cut. Accordingly, if, at decision block 151, there is no critical cut then the method sets the capacity c(e) equal to c(e) minus 0.5 capacity units for each link e, at block 153 and returns to block 145. Processing loops through decision block 151 and process block 153 until there is a critical cut. Then, the preprocessing tests, at decision block 155, if there are any adjacent demands D(n_i, n_i+1) greater than zero. If so, preprocessing routes a flow q(n_i, n_i+1) equal to the minimum of the demand D(n_i, n_i+1) and the integer capacity C(n_i, n_i+1) on the edge e_iconnecting nodes n_iand n_i+1, at block 157. Referring to FIG. 12, it will be noted that there is a demand greater than zero between each pair of adjacent nodes. Thus, during preprocessing, those demands are routed. When a demand is routed, the links column 83 of FIG. 12 is updated to show how the links are routed. Also, when a demand is routed, the method of the present invention adjusts the capacity c(e_i) in the capacity array and the demand D(n_i, n_i+1) in the demand array, at block 159. Then, preprocessing returns to block 145. Preprocessing continues until, at decision block 155, there are no adjacent demands greater than zero.

[0057] Referring again to FIG. 6, after preprocessing of Block 127, the flow routing method of the present invention tests for the occurrence of a terminating condition at decision blocks 129-133. If there is no terminating condition, then the system tests at decision block 139 if there is any critical two-edge cut (e_k, e_l) for which the flag of column 93 of FIG. 13 is set to zero. If so, the flow routing method of the present invention performs processing step A as indicated generally at block 141, and shown in detail with respect to FIG. 8. Referring to FIG. 8, in processing step A, the method of the present invention routes all commodities (n_i, n_j) wherein both n_iand n_jare on one side of critical cut (e_k, e_l) on the line formed by the nodes on that side of the critical cut. Computationally, the method routes all commodities (n_i, n_j) wherein i and j are greater than k and equal to or less than l on the line l(n_k+1, n_l), at block 161. Processing step A also routes all commodities (n_o, n_p) on the other side of the critical cut on the line formed by the nodes on that side of the critical cut, at block 163. Computationally, processing step A routes all commodities (n_o, n_p) wherein o and p are equal to or less than k and greater than l on the line l (n_i+1, n_k). Then, processing adjusts the demand array of FIG. 12 by reducing the appropriate value in demand column 81 by the amount of flow routed and by inserting the appropriate links in links column 83, and adjusts the capacity array of FIG. 14 by reducing the available capacity in capacity column 97 for the link or links used in routing the demand, and updates the demand list of column 98, at block 165. Then, processing step A calculates for each two-edge cut (e_k, e_l), the demand D(e_k, e_l), and the cut difference cut_diff(e_k, e_l), at block 167, and adjusts the two-edge cut array of FIG. 13 accordingly, at block 169. Then, preprocessing step A sets the cut flag to one for two-edge cut (e_k, e_l) at block 171. When the flag is set to one, it indicates that processing step A does not need to be performed again with respect to that two-edge cut. After setting the critical cut flag, at block 171, processing returns to FIG. 6.

[0058] Referring again to FIG. 6, if, at decision block 139, there is no critical cut with a flag equal to zero, then the flow routing method of the present invention performs processing step B, as indicated generally at block 143 and shown in detail with respect to FIG. 9. Referring to FIG. 9, processing step B finds a commodity or demand (n_i, n_j) greater than zero for which i is greater than k and equal to or less than l and for which j is less than or equal to k and greater than l, at block 173. Thus, at block 173, processing step B finds a demand to be routed between a pair of nodes on opposite sides of a critical cut. Then, at block 175, processing step B routes a flow q(n_i, n_j) on a line L(n_i, n_k, n_j). Flow q(n_i, n_j) is equal to the minimum of:

[0059] (i) the minimum demand d(n_i, n_j) between nodes n_iand n_j;

[0060] (ii) a quantity m(n_i, n_j, e_k) divided by two (m(n_i, n_j, e_k) is the minimum cut difference of all two-edge cuts with both edges on line L(n_i, n_k, n_j); and,

[0061] (iii) a capacity c(n_i, e_k, n_j), which is the minimum capacity among the edges on the line L(n_i, e_k, n_j) Preferably, line L(n_i, n_k, n_j) is selected to have the fewest number of nodes. After routing flow q(n_i, n_j) at block 175, processing step B adjusts the demand array of FIG. 12 and the capacity array of FIG. 14, at block 177. Then, processing step B calculates for each two-edge cut (e_k, e_l) the demand D (e_k, e_l) and the cut difference cut_diff (e_k, e_l), at block 179. Then, processing step B adjusts the two-edge cut array of FIG. 13, at block 181 and returns to FIG. 6 processing.

[0062] Referring again to FIG. 6, the flow routing method of the present invention performs either processing step A or processing step B until the occurrence of a terminating condition. If, at decision block 129, there are no demands left to be routed, then processing stops. If, at decision block 131, any capacity c(e) is equal to zero or 0.5, then the flow routing method of the present invention performs terminating processing step A, as indicated at block 135 and shown in detail with respect to FIG. 8.

[0063] Referring to FIG. 10, terminating step A tests, at decision block 183, if the capacity c(e_k) that is equal to 0.5. If not, terminating step A routes all remaining demands D(n_i, n_j) on the line formed by deleting edge e_k, at block 185, and returns to FIG. 6 processing where processing ends. If, at decision block 183, capacity c(e_k) is equal to 0.5, then terminating step A adds 0.5 capacity units to each edge e, at block 187 and routes one unit of demand of D(n_i, n_j) on line L(n_i, e_k, n_j), at block 189. After routing one unit of demand at block 113, processing continues at block 185 and terminating step A routes all remaining demands on the line formed by deleting edge e_k.

[0064] Referring again to FIG. 6, if, at decision block 133, any adjacent two-edge cut D(e_k, e_k+1) is critical, then the flow routing method of the present invention performs terminating step B, as indicated generally at block 137 and shown in detail with respect to FIG. 11. Referring to FIG. 11, terminating step B tests, at decision block 191 if the initial capacity of edges e is equal to an integer. In the present invention, the initial capacity is always either an integer value or a integer value plus 0.5 capacity units. If, at decision block 191, the initial capacity is an integer, then terminating step B routes a flow q(n_i, n_j) equal to the minimum of the demand D(n_i, n_j), and the integer value of the capacity c(e_k) on the line L(n_i, n_k, n_j), at block 193. Terminating step B then adjusts the capacity c(e_k) in the capacity array of FIG. 14, at block 195, and tests, at decision block 197 if capacity c(e_k) is equal to zero. If not, processing returns to block 193 and terminating step B routes another flow on line L(n_i, e_k, n_j), until the capacity of link e_kis determined at decision block 197 to be equal to zero. Then, terminating step B routes all remaining demands D(n_i, n_j) on the line L(n_i, e_k+1, n_j), at block 199 and returns to FIG. 6 processing where processing ends.

[0065] If, at decision block 191 the initial capacity of the links of the ring is not an integer value, then terminating step B adds one-half capacity unit to each edge e, at block 201, and routes one unit of demand D(n_i, n_j) on link e_k, at block 203. Then, processing continues at block 193.

[0066] From the foregoing, it may be seen that the present invention provides an efficient method and system for reconfiguring a ring in real time without disrupting traffic carried by the ring. As the ring becomes unbalanced due to provisioning and deprovisioning circuits, the method of the present invention allows the ring to be reconfigured dynamically so as to maintain optimally balanced demand loading. The method of the present invention also allows the network to be dynamically reconfigured in real time by changing the inter-ring routing plan. The system calculates an optimally balanced demand loading based upon the new inter-ring routing plan and generates secondary time slot assignment maps for the ADMs of the affected rings. The ADMs of the affected rings flash cut to the secondary TSAs and the DXCs switch the inter-ring connections substantially simultaneously, thereby implementing the new inter-ring routing plan.