Patent ID: 6229815
Filing Date: 2001-05-08
Classification: H04J,H04Q,Y10S

Abstract:
A method of routing flow in a bi-directional line switched SONET ring, said bi-directional line switched SONET ring comprising nodes n interconnected by links e, with a demand d(n.sub.i,n.sub.j) between each pair of nodes (n.sub.i,n.sub.j) and each link e.sub.k having a capacity c(e.sub.k), which comprises the steps of:(a) for each pair of links (e.sub.k,e.sub.l), calculating a cut difference cutdiff(e.sub.k,e.sub.l);(b) if there is pair of links (e.sub.k,e.sub.l) having a cut difference of zero or one and demands d(n.sub.i,n.sub.j)>0 for k<i,j<=l and demands d(n.sub.o,n.sub.p)>0 for k=>o,p>l, routing the demands d(n.sub.i,n.sub.j) on a line L(n.sub.k+1,n.sub.l) and routing the demands d(n.sub.o,n.sub.p) on a line L(n.sub.l+1,n.sub.k)(b) if there is no pair of links (e.sub.k,e.sub.l) having a cut difference of zero or one and demands d(n.sub.i,n.sub.j)>0 for k<i,j<=l and demands d(n.sub.o,n.sub.p)>0 for k=>o,p>l, routing on a line L(n.sub.i,e.sub.k,n.sub.p) a flow q(n.sub.i,n.sub.p) equal to:(i) the minimum of the demand d(n.sub.i,n.sub.p),(ii) the minimum capacity of a link e.sub.k of line L(n.sub.i,e.sub.k,n.sub.p), and(iii) one-half the minimum cut difference of all two-edge cuts with both edges on line L(n.sub.i,e.sub.k,n.sub.p); and,(d) repeating steps (a) through (c) until the first to occur of:(i) the demand d(n.sub.i,n.sub.j) for all node pairs (n.sub.i,n.sub.j) is equal to zero;(ii) the capacity c(e.sub.k) of any link e.sub.k is less than one; and,(iii) any adjacent two-edge cut (e.sub.k,e.sub.k+1) has a cut difference of zero or one.