Approximation Algorithms For Call Routing Problems In SONET Ring

Synchronous Optical Network (SONET) has been adopted as an importanttransport technology in network communication. The nodes on a SONET sendand receive messages via add/drop multiplexers (ADMs) that determine the ac-tual bandwidth available on the network, and the cost of a SONET increaseswith its bandwidth. Given a set of calls in the SONET ring, the aim of the load-balanced routing problem is to devise a routing scheme, so that the bandwidthrequired to transmit all the calls is minimized. While in general, the availablebandwidth o?ered is limited. The problem derived from this background is calledcall control and routing problem, the aim of which is to find, for a given set ofcalls, a subset of calls and their routing paths such that the total demand ofaccepted calls is maximum subject to the bandwidth capacity restriction. Thestudy on the call control and routing problem is meaningful and may find manyapplications in practice.The main results of the thesis are as follows:For the load-balanced routing problem in SONET rings, the technique of LPRounding is summarized; the approximation algorithm in general weightedcase the polynomial time exact algorithm in unit weighted case are bothdiscussed.For the call control and routing problem in SONET rings, the NP-hardnessresult are proved; by way of an elegant application of the technique of LPRounding, an approximation algorithm with a good performance ratio isgiven.