Fast and reliable exchange of data in world-wide communication networks has acquired essential importance in our society today, and telecommunications is one of the most important growth sectors in all leading economies. New applications like supercomputer networking, multimedia networking, and real-time medical imaging require transfer rates in the range of several gigabits per second, and they become possible only through advances in the technology and architecture of communication networks: enormous amounts of data can be transmitted through optical fiber using laser beams today, and new network protocols, e.g., ATM, allow flexible bandwidth reservation and enable simultaneous transmission of data with various different characteristics (telephone calls, multimedia data, electronic messages), satisfying the different requirements of all these various traffic types at the same time. The efficient use of modern communication networks is tied to a number of demanding algorithmic problems, in particular concerning the allocation of network resources to individual connections. More specifically, wavelength assignment in all-optical networks and call scheduling in communication networks with bandwidth reservation lead to a number of interesting combinatorial optimization problems. In this thesis, the complexity of such problems, i.e., the difficulty of algorithmic solutions, is determined under various restrictions, and polynomial-time approximation algorithms, i.e., algorithms computing solutions that are provably good (but not always optimal), are presented. The combinatorial optimization problems studied in this thesis pertain to simplified models of real-life communication networks. These combinatorial models capture the essential characteristics of the diverse problems encountered in practice. In all-optical networks with wavelength-division multiplexing, several connections can use the same fiber link simultaneously if the signals are transmitted on different wavelengths. Connections must use the same wavelength on the whole transmitter-receiver path, if wavelength conversion is not available. The path coloring problem is to assign colors (wavelengths) and paths to a given set of connection requests such that paths using the same link are assigned different colors. The goal is to minimize the number of different colors used. This problem is shown to be NP-hard for bidirected trees even in the binary case, for undirected trees of arbitrary degree and for bidirected and undirected rings. A polynomial-time optimal algorithm is given for undirected trees of constant degree. For undirected trees of arbitrary degree, an asymptotic 1.1-approximation is presented. A polynomial-time (5/3)-approximation is given for bidirected trees of arbitrary degree. If the number of available wavelengths is limited, which is the case in practice, the maximum path coloring (MaxPC) problem is of interest as well. Given a set P of connection requests and a number W of available wavelengths, the goal is to select a maximum cardinality subset P' of P and to compute an assignment of colors and paths to the connection requests in P'usingat most W colors. MaxPC is studied for bidirected trees. Polynomial-time optimal algorithms are shown to exist if the tree has depth one or if both W and the degree of the tree are bounded by a constant. Furthermore, MaxPC is proved NP-hard for bidirected trees of constant degree if W can be arbitrary, and for bidirected trees of arbitrary degree even if W=1. In the case W=1 the problem is equivalent to the maximum edge-disjoint paths problem. For every fixed epsilon>0, a polynomial-time (5/3+epsilon)-approximation algorithm for the maximum edge-disjoint paths problem (and, therefore, for MaxPC with W=1) is obtained. Using a known reduction from MaxPC with arbitrary number of wavelengths to MaxPC with W=1, a 2.22-approximation for MaxPC with arbitrary number of wavelengths is derived. While path coloring problems have a mainly graph theoretic flavor, the problem of call scheduling in communication networks with bandwidth reservation is closely related to multiprocessor scheduling and bin packing. When a call is established, the required bandwidth is reserved on all links along a path from sender to receiver for the duration of the call. The communication network is represented by a graph with edge capacities. A call is specified by a pair of vertices, a bandwidth requirement, and a call duration. Call scheduling is the problem of assigning paths and starting times to calls in a communication network such that the sum of bandwidth requirements of simultaneously active calls using the same link does not exceed the capacity of that link. Upper and lower bounds on the approximation ratio achieved by variants of the List-Scheduling (LS) algorithm are obtained for call scheduling in star and tree networks. The variants for calls with arbitrary durations work also if the durations are not known in advance; hence, they are batch-style on-line algorithms. For unit durations, the approximation ratio of LS in stars is shown to be at most 4.875 for arbitrary lists and at most 8/3 if the list of calls is sorted according to non-increasing bandwidth requirements. For arbitrary, unknown durations, the competitive ratio of LS is proved to be at most 5. In tree networks with n nodes, a variant of LS for calls with unit durations has approximation ratio at most 6, and a variant for calls with arbitrary, unknown durations has competitive ratio at most 5*log(n). On the one hand, the obtained results show the difficulty of computing optimum solutions for a number of combinatorial optimization problems concerning the allocation of resources in communication networks. These results resolve substantial open questions regarding the boundary between tractable and intractable versions of the problems under consideration. On the other hand, several efficient approximation algorithms are presented and analyzed; they do not always compute an optimum solution, but a solution that can be worse than the optimum solution only by a small (often constant) factor. These algorithms and their analysis give important insight into the practical benefit of different network architectures and the network utilization achievable in the worst case. Furthermore, the algorithms can be used as a basis for the implementation of resource allocation methods that perform well in practice for optical networks and for networks with bandwidth reservation. Finally, the analysis of the studied list-scheduling variants provides a justification for the use of simple heuristics, which are often preferred in practice due to ease of implementation, under certain conditions.
«
Fast and reliable exchange of data in world-wide communication networks has acquired essential importance in our society today, and telecommunications is one of the most important growth sectors in all leading economies. New applications like supercomputer networking, multimedia networking, and real-time medical imaging require transfer rates in the range of several gigabits per second, and they become possible only through advances in the technology and architecture of communication networks: e...
»
Login
BibTeX