Multiplex communications – Channel assignment techniques – Adaptive selection of channel assignment technique
Reexamination Certificate
1998-03-06
2001-05-08
Nguyen, Chau (Department: 2663)
Multiplex communications
Channel assignment techniques
Adaptive selection of channel assignment technique
C370S907000
Reexamination Certificate
active
06229815
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to communication network design and management, and more particularly to a method of assigning capacity and routing flow in a bi-directional line switched SONET ring.
DESCRIPTION OF THE PRIOR ART
Modern digital telecommunications systems are built upon a network consisting of a plurality of nodes or sites that are interconnected by spans or transmission facilities. The primary goal of telecommunications network design is to serve the demand in capacity between the nodes at the least cost, while maintaining an acceptable level of survivability in the event of failures. Two elements of cost in a network are transmission costs and equipment costs. Transmission cost is generally based upon the transmission distance. Equipment cost is based upon the cost of digital cross-connects and add-drop multiplexers.
Recently, there has been a move away from mesh topology for telecommunications networks toward a ring topology. In a bi-directional line switched ring, the demands on the ring are allowed to be routed on either side of the ring, and the 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, if the routing of traffic is not done properly, then there can be large amounts of capacity not utilized and the total capacity deployed on the ring can be significantly higher than what is really required. It is therefore a problem to load traffic on a bi-directional line switched ring so that the number of ring layers can be minimized.
The traffic loading problem has two components. The first component is to find the minimum capacity required for the ring. The second requirement is to find an integer multiflow that satisfies both capacity and demand constraints. The ring loading traffic problem has received much attention. Linear programming approaches and heuristic algorithms have been proposed for solving the problem. None of the previous known methods of routing in a mesh network, such as shortest path, least hop, or min-cost flow routing is appropriate for loading traffic on a ring or for determining the ring capacity requirement. The methods developed in connection with mesh networks do not consider the fact that ring capacities need to be the same for every span in the ring. Therefore, mesh routing techniques tend to congest certain spans of the ring and underutilize other spans.
Accordingly, a new method is needed to balance traffic loads on a ring so that the overall capacity requirement of the ring can be minimized.
SUMMARY OF THE INVENTION
The present invention provides method of assigning capacity and routing flow in a bi-directional line switched SONET ring based upon ring topology and demand data. The bi-directional line switched SONET ring includes N nodes n
i
connected in a ring by N links e
k
. There is a demand d(n
i
,n
j
) between each pair of nodes (n
i
,n
j
).
The capacity assignment method of the present invention defines for each pair of links (e
k
,e
l
) of the ring a two-edge cut. Each two-edge cut divides the ring into two sets of nodes, i.e. a set of nodes X between link e
k
and link e
l
, and a set of nodes (N-X) between link e
l
and link e
k
. For each two-edge cut (e
k
,e
l
), the capacity assignment method calculates a demand D(e
k
,e
l
) equal to the sum of all demands d(n
i
,n
j
) wherein node n
i
is in set X and n
j
is in set (N-X) . The capacity assignment method then determines the maximum demand D(e
k
,e
l
) and sets the capacity c(e
k
) of each link e
k
equal to one-half the maximum demand D(e
k
,e
l
) plus one-half demand unit.
The flow routing method of the present invention calculates a cut difference cut_diff(e
k
,e
l
) for each two-edge cut (e
k
,e
l
). Cut_diff(e
k
,e
l
) is the difference between the capacity of a two-edge cut (e
k
,e
l
), which is equal to the sum of c(e
k
) and c(e
l
), and the demand D(e
k
,e
l
) of the two-edge cut (e
k
,e
l
)
Each cut difference cut_diff(e
k
,e
l
) is always a positive number. A critical cut is a two-edge cut (e
k
,e
l
) having a cut difference cut_diff(e
k
,e
l
) equal to or less than one. If there is a critical cut (e
k
,e
l
) with demands d(n
i
,n
j
) greater than zero between nodes (n
i
,n
j
) in X and demands d(n
o
,n
p
) greater than zero between nodes (n
o
,n
p
) in (N-X), then the flow routing method of the present invention performs a first processing routine. In the first processing routine, the method routes the demands d(n
i
,n
j
) on the line formed by the nodes of X and routes the demands d(n
o
,n
p
) on the line formed by the nodes of (N-X). Thus, in the first processing routine, the method routes demands on either side of critical cut (e
k
,e
l
).
If there is no critical cut (e
k
,e
l
) with demands d(n
i
,n
j
) greater than zero between nodes (n
i
,n
j
) in X and demands d(n
o
,n
p
) greater than zero between nodes (n
o
,n
p
) in (N-X), then the flow routing method of the present invention performs a second processing routine. In the second processing routine, the flow routing method of the present invention routes a flow q(n
i
,n
p
) on a line L(n
i
,e
k
,n
p
), which is the line between nodes n
i
and n
p
that includes link e
k
of critical cut (e
k
,e
l
). Thus, the second processing routine routes flow q(n
i
,n
p
) across critical cut (e
k
,e
l
). The amount of flow q(n
i
,n
p
) is equal to the minimum of: (i) the demand d(n
i
,n
p
); (ii) the minimum capacity of a link e
k
of line L(n
i
,e
k
,n
p
); and, (iii) one-half the minimum cut difference of all two-edge cuts with both edges on line L(n
i
,e
k
,n
p
).
The flow routing method of the present invention repeats either the first or second processing routine until a terminating condition occurs. A first terminating condition occurs when the demand d(n
i
,n
j
) for all node pairs (n
i
,n
j
) is equal to zero, which indicates that all demands have been routed. Upon the occurrence of the first terminating condition, the flow routing method is finished.
A second terminating condition occurs when the capacity c(e
k
) of any link e
k
is less than one. If the capacity c(e
k
) of link e
k
is equal to zero, then the flow routing method routes all remaining demands d(n
i
,n
j
) on the line formed by deleting link e
k
. If the capacity c(e
k
) of link e
k
is equal to 0.5 capacity units, the flow routing method of the present invention adds 0.5 capacity units to each link of the ring and routes one unit of demand d(n
i
,n
j
) on line L(n
i
,e
k
,n
j
), which reduces the capacity c(e
k
) of link e
k
to zero. Then the flow routing method routes all remaining demands d(n
i
,n
j
) on the line formed by deleting link e
k
.
A third terminating condition occurs when any adjacent two-edge cut (e
k
,e
k+1
) has a cut difference of zero or one. If the initial capacity c(e) of each link e is an integer number of capacity units, the flow routing method routes a flow q(n
i
,n
j
) on line L(n
i
,e
k
,n
j
) until c(e
k
) is equal to zero. The flow q(n
i
,n
j
) is equal to the minimum of (i) d(n
i
,n
j
) and (ii) the integer capacity of link e
k
. When the capacity c(e
k
) of link e
k
is reduced to zero, the method routes all remaining demands d(n
i
,n
j
) on the line formed by deleting link e
k
. If the initial capacity c(e) of each link e is a non-integer number of capacity units, the method adds 0.5 capacity units to each link and routes one unit of demand d(n
i
,n
j
) for one node pair (n
i
,n
j
) on line L(n
i
,e
k
,n
j
)
Preferably, the flow routing method of the present invention performs certain preprocessing steps. The flow routing method of the present invention routes any adjacent demands d(n
i
,n
i+1
) on link e
i
connecting nodes n
i
and n
i+1
prior to performing the first or second processing routine. If the flow routing method is done in connection with the capacity assignment method of the present invention, there will always be at least one critical cut at the beginning
Huang Jennifer Shu-Chen
Nathan Sridhar S.
Weston-Dawkes Jonathan
Boakye Alexander
MCI Communications Corporation
Nguyen Chau
LandOfFree
Method of optimal routing in a bi-directional line switched... 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 of optimal routing in a bi-directional line switched..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of optimal routing in a bi-directional line switched... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2475806