| With the explosion of Internet tra?c and multimedia data communication,the Synchronous Optical Network (SONET) has been adopted by many networkservice providers as a faster, more e?cient, and less expensive transport tech-nology. The underlying architecture of SONET is supported by SONET rings,in which ring nodes send, receive and relay messages via add or drop multiplex-ers (ADMs) installed on these nodes. The actual bandwidth available along theSONET ring is determined by the capacity of these multiplexers, so in general,there is a capacity restriction, denoted by an integer C, such that no link of thering may carry more than C units of tra?c.There are many challenging problems in designing and operating of SONETring, such as ring load problem, load-balanced routing problem in undirected orcounter rotated SONET rings, as well as node-capacitated ring routing prob-lem. In fact, these problems fall into the scope of the classical integer multi-commodity ?ow problem in combinatorial optimization, which are in generalNP-hard. However, in some special cases, these problems are exactly solvable inpolynomial time. When SONET ring is undirected, cut criterion plays a crucialrole in characterizing the solutions or designing approximation algorithms. Butwhen SONET ring is directed, the criterion fails to work. In such case, LP-basedrounding technique becomes an important technique for solving the problems,which has been derived some good results on load-balanced routing problems.The main problem concerned in our thesis is an optimization problem arisingfrom the operation of SONET rings: In counter rotated SONET ring with loadrestriction, there is a list of tra?c demands each of which may be routed in oneof the two possible (clockwise and counter-clockwise) ways between its sourceand its sink, we need to identify a routing scheme, that is, to determine whichsubset of demands and which directions for them to be transmitted, subjected to the ring capacity restriction, such that the number of demands transmitted(the throughout of the routing) is maximum. This problem is called routing incounter rotated SONET ring with load restriction (LRRR).By an elegant application of LP rounding technique, we provide a polyno-mial time algorithm for LRRR problem in counter rotated SONET ring. Witha violation of the ring capacity by at most one, the algorithm gives rise to arouting scheme with the number of transmitted demands no less than the opti-mum. With some farther modifications, we get an approximation algorithm forLRRR, of which performance guarantee is 1 ? C2+1, and this result accords withthe requirements of application. To our best knowledge, there are few resultson the study of routing problems under the ring capacity restriction. In ouralgorithm, some modifications and generalizations of the existing techniques areproposed, and some approaches to the related problems in undirected ring arealso employed, in view of the characteristics of the LRRR problem. These im-provements are meaningful in both algorithmic theory and practical applicationsin communication networks. |
