Algorithms for Call Control in Ring Based Networks

Communication networks lend themselves to the study of a variety of optimization problems. A fundamental problem among them that is intensively investigated is that of call admission control, or call control for short. The problem arises in the following setting. The communication network consists of nodes (e.g. terminals, routers, et cetera) which are connected to each other via links (e.g. optical cables). These links carry data between nodes. They have a certain bandwidth capacity associated with them. A call is a communication request between any two nodes of the network. It is associated with a bandwidth requirement, i.e. the rate at which data is communicated between the nodes. A call may be accepted into the network if (i) a route connecting the two nodes exists and (ii) the bandwidth requirement of the call can be reserved along all the links of one such route. Once a call is accepted a profit is accrued by the network. The optimization problem arises due to the fact that the sum of the bandwidth requirements of calls that are routed through any link of the network should not exceed its bandwidth capacity. The call control problem is to maximize the number (or profits) of calls that can be accepted into the network such that the capacity constraints on the links are not violated. A ring topology is one in which the nodes are connected to each other forming a cycle. In all-optical networks, the ring topology is a popular configuration. Bigger networks are formed from individual rings by interconnecting them. Some top reasons that make the ring topology a favoured one are its simplicity, scalability and survivability in the presence of link failures. This thesis mainly investigates several variants of call control on ring based topologies for two reasons. Firstly, all-optical networks are in the forefront of revolutionizing communications today and the ring topology is the building block of such networks. Secondly, rings are simple topologies on which several network optimization problems have been studied in the past and there are several others which have not been resolved. The goal of our research, the outcome of which is the thesis presented here, is to address a few such problems pertaining to call control. There are two basic variants of call control that we consider, namely on- line and off-line. In the off-line version of call control, it is assumed that all the calls that occur in the network are given in advance. An algorithm for this version can decide which calls to accept and which to reject taking this overall picture into consideration. In the online version, calls arrive into the network in a sequence, one after the other. An algorithm for the on-line version makes a decision to accept a call that is presented to it only based on what decisions it made in the past and the current state of the network. In particular, it has no knowledge of the calls that might be presented to it in the future. A tree of rings is a graph obtained by connecting several disjoint rings in a "tree"-like fashion, by identifying vertices in different rings. The tree of rings topology is a natural result of interconnecting rings in all-optical networks to form larger networks. We investigate on-line call control problems on trees of rings. Non-preemptive randomized algorithms with competitive ratios that are best possible up to constant factors are given. Fixed parameter tractability is an emerging area to tackle NP-hard problems. We view call control problems from this perspective. Fixed parameter tractability results are shown for variants of the off-line call control problems on arbitrary graphs, undirected and bidirected trees of rings. To the best of our knowledge, these are the first such results for the call control problem. For two variants of off-line call control problems in rings, we present polynomial time approximation algorithms. When the route of a call can be determined by the algorithm, we present an algorithm that accepts and routes at most 3 calls fewer than what an optimal algorithm can achieve. When the routes are pre-determined we present an algorithm that achieves a profit that is at least one-half of that achieved by an optimal algorithm. For various special cases, we present optimal polynomial time algorithms or approximation schemes. We also give an indication of the difficulty of finding an optimal polynomial algorithm for the general problem. For addressing the off-line call control problem for calls with arbitrary bandwidth requirements, a starting point would be to study it on the simple topology of a line. A line is simply a set of nodes connected to form a path. We identify several restrictions for which algorithms with "nice" ratios are achievable.