Coordination-based optimization of path bandwidth allocation for large-scale telecommunication networks

Abstract

In this paper, the authors propose a new optimization method of path bandwidth allocation for large-scale telecommunication networks. By using the decomposition–coordination method to get an optimal solution of path bandwidth allocation for large-scale communication networks, a big network is divided into small and inter-connected sub-networks. The path bandwidth allocation procedure is composed of three phases. Firstly, the large-scale network is divided into small sub-networks; then, a decomposition–coordination procedure is imposed to allocate path bandwidths between nodes within each sub-network and to find the bottleneck subnet of the whole network and to evaluate the worst call blocking probability of it; finally, path bandwidths of source–destination pairs between different sub-networks are computed out by successive use of an ordinary optimization algorithm. Comparing with existing algorithms, our results show that the Decomposition–Coordination Large-scale Path Bandwidth Management (DCLPBM) algorithm can get results with high accuracy and both spatial and time complexities are reduced. As the coordination procedure in our model is quite simple, the DCLPBM can be converted to a distributed computing version easily. This is fascinating from a point of view of managing the network in a real network environment.

Introduction

High speed integrated services networks (such as ATM and newly proposed Internet architectures) aim to support various classes of multimedia traffic with different bit rates and quality of service requirements. Traffic control and resource management play a decisive role in guaranteeing the desired grade of service. In modern telecom networks the establishment of a bandwidth provision strategy that will allow us to dynamically reallocate the bandwidth capacities of the virtual paths is an urgent objective, due to the unpredictable nature of traffic, especially of the emerging multimedia services. The traditional strategy, where the network is configured in advance, based on busy hour point-to-point traffic data and satisfying a prescribed quality-of-service (QoS), becomes absolutely inadequate. This is due to traffic fluctuations, where over-dimensioning would happen in some virtual paths, while at the same time in some other paths under-dimensioning may occur. The ideal bandwidth allocation strategy must be able to realize a flexible network that will dynamically adapt to any traffic variation.

Path Bandwidth Management (PBM) forms a large part of the call-level traffic management in telecommunication networks and has close relation to the strategy of path bandwidth allocation. It is in fact a medium or long-term network control [6]. The call blocking probability (CBP) is an important measurement of its performance. In cooperation with a bandwidth reservation scheme, PBM changes the installed bandwidth in the virtual paths periodically so as to improve the global performance of the network under constraints imposed by the limited capacities of the transmission links. The resultant distribution of the totally installed bandwidth in the network to the virtual paths is the virtual path bandwidth allocation (VPBA). The bandwidth reservation scheme, which aims at guaranteeing the QoS requirement of each service-class provided by the network, is widely adopted and can be incorporated into a function evaluating CBP [1].

The problem of PBM, including dynamic path bandwidth allocation, has been widely studied during the last decade, especially for telecom networks that provide service-classes with QoS guarantees. Since the 90s of the last century, computing-power and progress in switching and transmitting technology have been giving rise to global optimization of telecommunication networks. Many heuristic but efficient algorithms that can solve global network optimization problems have been proposed for PBM [2], [4], [5], [6], [12]. Besides, Logothetis and coworkers have proposed an analytical algorithm [13], which lead to optimal results. It can be named ‘optimal PBM algorithm’ (OPBM).

In this paper, we try to solve the problem of PBM in large-scale telecom networks by applying the decomposition–coordination theory of operations research. Although we suppose central PBM in large-scale networks to achieve optimality, the method can be converted to a distributed computing version with ease. Optimality necessitates the use of a network administration center that gathers information about traffic loads carried by the end-to-end links and, possibly aided by a traffic prediction model, defines the traffic demand matrix of the network that drives the PBM. We focus on long-term control and think PBM as a network-planning tool. This is due to the fact that a medium-term control interval (e.g. 20 min) cannot be defined accurately, for two reasons:

• The bandwidth rearrangement time-delay (BRT) cannot be predicted undoubtedly and, most of all, the maximum delay cannot be restricted to a medium term period (e.g. less than 20 min). The probability of BRT to exceed the expected maximum increases as the network size increases.

• The time needed for traffic measurements, plus the time taken by traffic prediction and, especially, for searching a new optimal bandwidth allocation is considerably long for large-scale networks and can vary apparently with different network sizes [6].

It should be noted that the rapid developments in computer techniques and new efficient algorithms make the time span standard of telling apart long-term and medium-term bandwidth management more vague. This leads to the possibility that achievements in long-term PBM can be transplanted into medium-term even short-term cases.

From the above discussions it is obvious that the peculiarity of a large-scale telecom network arises from its size, or the number of network-nodes and transmission links. Since an OPBM aims at solving a global network optimization problem, the applicability of most existing algorithms is restricted to small or medium size networks. One exception is the LPBM algorithm developed by Dr Logothetis et al. [1]. In their paper, a three-phase method of optimizing the path bandwidth allocation between network node pairs is proposed. In the first phase, a network is divided into some ‘basic subnets’. Path bandwidth allocation within each sub-network is optimized by an ordinary PBM procedure in the second phase. The third and final phase is imposed to optimize the path bandwidth allocation between nodes from different subnets. Their method seems a good remedy to the difficulty of path bandwidth allocation in large-scale telecom networks, but some shortcomings reside in their algorithm. Their large-scale PBM algorithm (LPBM) produces a maximum relative error of about 30% from those which applying OPBM directly over the whole network. By studying Logothetis' LPBM algorithm carefully, we realize that they have not dealt with the problem of boundary conditions between adjacent networks very well. Taking physical principles of network traffic into consideration and by applying the decomposition–coordination method of optimizing large-scale systems, we propose a new method of optimizing path bandwidth allocation in large telecom networks. The method also consists of three phases:

• Dividing the large network into small sub-networks, this can be called decomposition.

• Optimizing path bandwidth allocation in each sub-network by considering physical connections between different sub-networks and the most important factors indicating the overall state of the whole network. This procedure can be referred to as coordination.

• Path bandwidth allocation between end-to-end node pairs of different subnets.

The first and the last phases are similar to those of Logothetis' method, but in the first phase, it is not necessary in our method that a sub-network should be a ‘basic sub-network’ [1]. The above mentioned three-phase optimization algorithm for PBM in large-scale networks will be referred to as DCLPBM hereafter.

The DCLPBM algorithm brings the light of distributed computing on the optimization of path bandwidth allocation for large-scale telecom networks. The second phase will prove to be the most time-consuming one in the three phases of the DCLPBM algorithm if we do not take the advantage of parallel computing. By setting up a computation agent in each sub-network and tasking each agent to allocate path bandwidths within the corresponding sub-network, the coordination phase can be a process of parallel computing simultaneously run on many agents. In the DCLPBM algorithm, the coordination messages are assumed as generated centrally by the coordinator. The coordinator plays the simple role that it should select the largest one from the numbers (namely the worst CBPs of each sub-net) reported by each agent and that it should broadcast the value back to every sub-network. So it is easy to break the central coordinator and let it be contained in each agent. One way to ‘break the center’ is letting each agent know the messages all the other agents report. The technology of multicast can serve our purpose. Now we come to the point that the ‘coordinator’ is only a logical concept and it can be physically distributed. Similarly, most of the computations of the third phase are parallel and thus can also be distributed to the computation agents.

This paper is organized as follows: Section 2 defines mathematical symbols used in the following sections. A brief introduction of the OPBM is also provided in this section. Section 3 gives specific illustrations to our decomposition–coordination algorithm. Section 4 shows numerical results of our algorithm against that by applying OPBM directly over the whole network and that of LPBM through an example. Section 5 contains an approximate method of calculating the call blocking probabilities. The exact worst CBPs of three different cases are also compared in Section 5. The three cases are: (I) DCLPBM plus approximate algorithm of evaluating CBP; (II) OPBM plus strict algorithm of evaluating CBP; (III) LPBM plus strict algorithm of evaluating CBP. The results show that DCLPBM combined with the approximate algorithm of calculating CBP is both much faster and more accurate than LPBM combined with strict algorithm of evaluating CBP. Section 6 is the concluding part in which a summation of our research work and topics on further related study are given.