A tabu search algorithm for dynamic routing in ATM cell-switching networks

1 A TABU SEARCH ALGORITHM FOR DYNAMIC ROUTING IN ATM CELL-SWITCHING NETWORKS P Cortes1†, J Muñuzuri1 and J. Fernández1 1 Seville University Grupo Ingeniería Organización. Escuela Superior Ingenieros, Camino de los Descubrimientos s/n. Sevilla 41092. SPAIN †E-mail: [email protected]s † URL: http://io.us.es/P.Cortes/ Abstract This paper deals with the dynamic routing problem in ATM cell-switching networks. We present a mathematical programming model based on cell loss and a Tabu Search algorithm with short-term memory that is reinforced with a long-term memory procedure. The estimation of the quality of the solutions is fast, due to the specific encoding of the feasible solutions. The Tabu Search algorithm reaches good quality solutions, outperforming other approaches such as Genetic Algorithms and the Minimum Switching Path heuristic, regarding both cell loss and the CPU time consumption. The best results were found for the more complex networks with a high number of switches and links. Keywords: Tabu Search, dynamic routing, ATM 1. Introduction The general problem of real time operation in telecommunication networks involves a collection of different complex problems. Consequently, optimisation in real time operation in telecommunication networks arises when communications have to be routed across the network from the origin point to the destination. In this context soft computing can offer additional capabilities with respect to other traditional approaches. The basic and more traditional problem of real time operation is known as routing and can be undertaken in either a static or dynamic way. Static routing makes use of the routing tables that are constructed by means of the capacity assignment and multicommodity flow problem. In this case the network is analysed offline using deterministic and static demands of traffic. Dynamic routing arises when the messages are routed in real time trying to minimise the losses or to minimise the delays experienced by the messages. Several specific problems following on from the basic problem have been tackled. Medhi et al. (2000) have considered solution approaches to a multi-hour combined capacity design and routing problem, which arises in the design of dynamically reconfigurable broadband communication networks that use the virtual path concept. They compared a genetic algorithm, a Lagrangian relaxation based subgradient optimisation method, a generalised proximal point algorithm with subgradient optimisation, and a hybrid approach where the subgradient based method is combined with a genetic algorithm. Also, Xu et al. (1997) presented a tabu search approach that optimises the link capacities in a dynamic routing telecommunications network. The traffic between any pair of nodes in the network is routed over a one-link direct path or, if no direct capacity is available, over a twolink alternate path. Later, Shyur et al. (2001) presented a non-time dependent model to solve the problem of optimising the system of virtual paths using a tabu search approach. Although these two papers make use of tabu search approaches, as ours does, they cannot be directly compared to our paper because they do not use a time horizon with different time scales, as is considered here. More recently, Cortes et al. (2002) have presented a genetic algorithm for dynamic routing in ATM networks. The model objective was to minimise cell loss subject to strict delay conditions. Alternatively, Wille et al. (2006) showed models and algorithms considering at the same time the dynamics of packet network and the grade of service (GoS) user-layer requirements. 2 Another problem in real time operation corresponds to communication admission control. This admission control is a deterministic and informed decision that is made before a communication is established and is based on whether the required network resources are available to provide suitable GoS for the new communication. Yener et al. (1997) presented a paper along these lines, dealing with the cellular call admission control. They define local policies based on genetic algorithms. For the mobile network cases, Sheng et al. (2006) successfully tested a threshold-adaptive call admission control based on genetic algorithms for multiclass services. The dynamic bandwidth allocation is a problem by which traffic bandwidth in a shared telecommunications medium can be allocated on demand and evenly between different users of that bandwidth. Pitsillides et al. (2000) analysed the performance of the traditional constrained optimisation algorithm compared to a new constrained optimisation genetic algorithm for solving the bandwidth allocation for the virtual paths problem. Comparisons were carried out with respect to throughput, fairness and time complexity. More recently, El-Madbouly (2005) has proposed a genetic algorithm for the design of an optimisation algorithm to achieve the bandwidth allocation of ATM networks. Recently, the problem of wavelength-division multiplexing has arisen as a very efficient method of transmission that consists of the simultaneous transmission of more than one information-carrying channel on a single fibre light side, using two or more light sources of different wavelengths. This is currently one of the most efficient methods for the transmission of mass communication. Specifically, WDM technology has emerged as a promising technology for backbone networks. The set of all-optical communication channels (lightpaths) in the optical layer defines the virtual topology for the upper layer applications. Since the traffic demand of upper layer applications fluctuates from time to time, it is required to reconfigure the underlying virtual topology in the optical layer accordingly. Din (2004, 2007) has used genetic algorithms to solve the optimal multiple multicast problem on wavelength division multiplexing ring networks, without wavelength conversion and the virtual topology configuration transition problem. Also, Le et al. (2006) have dealt with the dynamic survivable routing problem, both in optical networks without wavelength conversion and in optical networks with sparse wavelength conversion. They make use of a hybrid algorithm based on the combination of mobile agents technique and genetic algorithms. Finally, Tak et al (2007) have proposed restoration techniques incorporating the concept of k-shortest disjoint paths in survivable WDM optical networks, considering network performance and network costs simultaneously, making use of several soft computing algorithms to do so. Here, we focus our research on the first set of problems described, specifically on the dynamic routing problem in an ATM cell-switching network. The rest of the paper deals with a brief description of the Asynchronous Transfer Mode (ATM) special characteristics, included in the second section. Once the technological background of the paper has been stated, the third section is devoted to the mathematical programming model of the problem, which is based on a cell loss model with bounded delay conditions. The fourth section presents the Tabu Search used to solve the problem. The fifth section outlines the results and the comparison between Tabu Search, Genetic Algorithms, and a fast heuristic algorithm. Finally the last section describes the main conclusions and our further research. 2. A description of the Asynchronous Transfer Mode ATM was created to provide faster communications in both public and private networks. ATM can be characterised as a hybrid transfer mode between circuit and packet switched networks. ATM combines circuit and packet switched networks maintaining the channel structures, by means of timeslot division, as in circuit switched, and the packet structure, by means of ATM cells, as in packet switched. 3 ATM cells are 53 bytes long. These bytes are divided into different length fixed fields. The Virtual Channel Identifier (VCI) and Virtual Path Identifier (VPI) fields specify the circuit and path that each cell should take. The Payload Type Identifier (PTI) field is used to specify the type of information contained in the payload section of the cell. The Cell Loss Priority (CLP) field gives an indication of the severity of the consequences of the loss of this cell in the event that there is insufficient bandwidth in the switch to process all incoming cells. The Header Error Check (HEC) field function is to detect and correct possible errors in the transmission process into any field of the cell header. The payload field is a 48-byte area that contains the user data to be transmitted over the virtual circuit. Figure 1 depicts a Network-Network interface (NNI) cell, i.e., a cell flowing between network switches. Unlike NNI cells, User-Network Interface (UNI) cells substitute the 12-byte VPI field with an 8-byte field, due to the remaining 4 bytes being used for the Generic Flow Control (GFC) field, allowing the flow control that is transmitted from the UNI interface. LOCATION FOR FIGURE 1 The VPI and VCI are transmitted into the header. These identifiers are only valid for each connection link and identify a logic circuit into the physical link. When the cell arrives at the switch, the VPI and VCI are set and the cell is routed through the output port, changing the identifier when necessary. The virtual circuit (or channel) concept is an abstraction representing the cell unidirectional transport associated to an identifier (VCI). The VCI and the VPI indicate an ordered cell flow associated with a concrete connection. The virtual connection channel (VCC) concept means the connection of different virtual paths between the origin of communication and the destination of communication. The concepts are graphically described in Figure 2. LOCATION FOR FIGURE 2 Once the first cell arrives at a switch, the communication is routed from an inflow logic channel onto an outflow logic channel. The ATM switches are characterised by the information volume, the rate of bit error, the delay, the cell loss probability and the delay fluctuation. In ATM the information volume being processed and the rate of bit error are conditioned by the technology and the system dimension. The use of high-speed technologies, such as BICMOS or ECL, easily provides hundreds of Mb/s with acceptable error rates. Cell loss in ATM switches appears when many cells are routed onto the same link, being greater than the buffer size of the switch. The switching delay is the time used by one cell to switch to its destination. The switches can be classified in accordance with the structure of the switching fabric architecture. The matrix switch is one of the most recommended switches, where a connection matrix establishes the interconnection of any input point with any output point. One of the better delay-performance relations is obtained for matrix switches with queues at the end. This option allows more than one cell to be transmitted in the same timeslot. In order to ensure no cell loss, the transference must be N (number of input ports) times faster than the cell homing rate. Moreover, the queue location at the end prevents the line header from blocking. The ATM contract must specify the requested bandwidth, as well as the quality of service. The resultant parameters will be negotiated between the network and the user as a function of the network resources. The service categories are: Constant Bit Rate service (CBR), Variable Bit Rate service (VBR), Available Bit Rate service (ABR) and Unspecified Bit Rate service (UBR). CBR service is chosen to maintain real time communications as video or audio, with a very strict delay requirement. CBR service provides a connection with large bandwidth and very low cell loss probability. VBR service is indicated for frame relay traffic. ABR service is used for 4 unknown characteristics traffic and must be moderately restrictive attending to cell loss and without delay requirement as real time applications. Finally, UBR service uses as much bandwidth as is available. One additional specific characteristic of the ATM switching mode that very much determines the mathematical modelling of the problem refers to the time scales in ATM. The traditional and widely used Erlang model considers one unique time scale: the connection scale or call scale. Bandwidth traffic requires additional scales. Consequently, ATM needs to consider at least two time scale levels: the call time scale to ensure the call connection level and the cell time scale to ensure the quality specifications with respect to cell loss and message integrity. Thus, flow variables are needed for the cell level scale, and path variables for call routing. In fact, once the first cell is routed onto a virtual circuit, the remaining cells follow the first one through the same circuit, so the path variables must be referred to as the call level scale. Figure 3 depicts the different levels and their interrelations. LOCATION FOR FIGURE 3 3. A mathematical programming model for the dynamic routing problem in ATM cellswitching networks ATM networks can be well suited by graphs G = (N,E), with N being the set of switches (nodes) and E the set of links. Messages are sent from communication origin nodes to destination nodes. The messages are divided into cells with message information (payload) and management information (header). These cells are routed onto different switches with the objective of reaching the final destination. In order to construct a tractable mathematical programming model, we consider some limitations and hypotheses, which are described below: - We have considered that the cell loss takes place within the switch. In practice, ATM cells can be lost due to line transmission failures, the Usage Parameter Control in the switching network, buffer sizes or switching fabric limitation. The consideration of cell loss only at the switch is not a strong limitation because it represents the very largest part of cell loss in ATM networks. - We have considered only CBR traffic. In fact, this is not a strong restriction in relation to our objective function. VBR, ABR and UBR traffic are much less restrictive according to cell loss (our objective function) than CBR traffic. - We have not considered capacity constraints supposing links of extra capacity. This is a very realistic supposition because telecommunication links are over dimensioned due to the prevision of future traffic increments at the planning stage. - The delay limitations are considered as a heavy constraint of the mathematical model. Most of the research only considers the delay that is taking place within the switch due to the queue and the real switching process, because the remaining sources of delay, such as electric-optic conversion or signal propagation, are second order factors. The mathematical programming model is defined by the following parameters, variables, data and constraints.  Parameters: - N Set of switches (nodes). - E Set of links. 5 - M Set of communication origin-destination pairs, being O(m) origin of communication m and D(m) destination of communication m. - H(m) Set of feasible paths to establish a connection between each origin-destination pair m. This includes only those paths with a feasible number of switches attending to the delay specifications. - T Temporal horizon at call scale. This horizon is composed by call time division Tt ∈. Subsequently, the call time scale is divided into the cell time scale, t∈ τ . - N(h) Set of nodes belonging to path h. - E(h) Set of links belonging to path h. - B(i) Set of nodes located before node i. - A(i) Set of nodes located after node i.  Variables: - Phm,t Binary variable indicating whether the connection between the origin of communication O(m) and the destination of communication D(m) is established by the path h, referred to the call scale Tt ∈ . - Xh,ijm,τ Continuous flow variable associated to the pair m over the link (i,j) in that specific direction (from i to j), being (i,j) a link of the path h, referred to the cell scale t∈ τ . Expressed in cells/slot. - lh,ijm,τ Continuous variable determining the cell loss at the link (i,j) due to the port j into the switch i in the connection path h used by the pair of communication m, in the timeslot t∈ τ (so it is referred to the cell scale). The variable is expressed in cells/slot. - Fijτ Total cell flow variable that should be routed from node i to node j. It is referred to the cell scale t∈ τ . Expressed in cells/slot. It is important to note the difference between the variables Fij τ and Xh,ij m, τ . The former refers to the total flow of cells that should ideally go through the link (i,j), supposing no cell loss, meanwhile the second variable takes into account the cell loss possibility. Figure 4 depicts an example. In Figure 4 the switches v, w, y, z are before node i, whereas nodes j, k are located after node i. For an instant τ there is a flow of cells from nodes v, w, y, z to node i, the flow from nodes v and z must be routed to node j and the flow from nodes w and y must be routed to the switch k. LOCATION FOR FIGURE 4  Data: - Amτ Demand of the origin-destination pair m in the timeslot t ∈ τ . It is referred to the cell scale and expressed in cell/slot. - GoSm Grade of service. Maximum number of lost cells for each connection m, measured as cells/slot. Finally, the mathematical programming model can be formulated as follows: 6 ),()( , , ∑∑ ∑ ∑ ∑ ∈∈ ∈∈∈TttEjiMmmHh tm ijh lMIN τ s.t. (3.1) PmMt T h mt hHm , () ,=∀∈∀∈ ∈ ∑1 (3.2) ⎪ ⎩ ⎪ ⎨ ⎧ ≠ = =+ −O(m ) i if O(m)i if 1, , , , , , , τ τ ττ m kih tm hm m ijh m ijh X PA lX )(,,/),(),(),(),(:,),(,, hNkjihEikhEjiNiMmmHhTtt ∈ ∈ ∀ ∈ ∀ ∈ ∀ ∈ ∀ ∈ ∀∈∀⊂∀ τ (3.3) TttEjiAXF MmmiMm m hNjhEiq mHhiBq m qihij ∈∀⊂∀∈∀+= ∑ ∑ ∑ ∑ ∈=∈ ∈∈ ∈∈ −,,),( )(0/ )(:)(),( ),()( 1, , τ τττ (3.4) ∑∑ ∈∈ ∈∀⊂∀∈∀∈∀≥ Mm ijij mHh m ijh TttEjiNiFl ,,),(,)( )( , , τ τττ L (3.5) TtMmGoSl m mHhiAjhEji m ijh ∈∀∈∀≤ ∑∑ ∑ ∈∈ ∈∈ , t )()(:)(),( , , τ τ (3.6) TttMmEjilm ijh ∈∀⊂∀∈∀∈∀≥ ,,,),( 0 , , τ τ (3.7) TttMmEjiXm ijh ∈∀⊂∀∈∀∈∀≥ ,,,),( 0 , , τ τ (3.8) TtmHhMmP tm h∈∈∈∀∈ ),(, )1,0( , Constraint 3.1 is referred to the call scale stating that pair m communication must be routed onto only one path, h. Constraint 3.2 refers to the flow balance equation; the term on the left shows the flow through the link (i,j) belonging to path h used to connect the pair m plus the loss in the buffer j of the switch i. The term on the right shows two situations: in the first situation, node i is the origin of communication, so all the generated traffic is routed onto the path h; in the second situation, node i is an intermediate node of the path h, so the expression must include the flow sent by the node before the switch i in the path h, i.e. the link (k,i). This traffic will carry a timeslot delay due to the switching process and includes the losses into the previous switches. This balance equation is imposed at the cell scale. Constraint 3.3 determines the total flow including all the flows homing from nodes before node i and being routed onto the switch j. In constraint 3.4, the cell loss is characterised as ( ) ττ ijij FL for the output port j relative to the switch i in the instant τ when the arrival rate is the total flow homing to the switch i and flowing to port j, that is Fij τ . The term on the left reflects the sum for all the origin-destination pairs and their feasible paths for the connection including the link (i,j), and the term on the right states the losses at the output port j. Finally, constraint 3.5 is bound on the grade of service, so a maximum cell loss is imposed for each path of communication. The objective function includes the total cell loss for all the pairs of communication, for each path, for each link and for the entire horizon. 4. The Tabu Search algorithm Tabu Search was first introduced by Glover (1989, 1990). The simple Tabu Search algorithm uses the best improvement local search as the basis for its movements and uses a short-term memory to escape from local minima. Starting from its solution, the algorithm tries to find a better one in its neighbourhood (defined as a set of near solutions that are found by applying an appropriate transformation of the current solution). The algorithm permits moves that result in a degradation of the objective function value to escape from a local minimum, thus preventing 7 them from being trapped into a local optimum. The algorithm considers some of the previously visited solutions as “tabu” preventing the searching process falling into cycles. Tabu search has been largely used to solve transport problems; it is considered one of the most suitable algorithms to solve a large range of vehicle routing problems. Its applicability to telecommunications has recently been gaining support in scientific literature, as the literature review in Section 1 describes. In this paper, we propose a Tabu Search algorithm for the dynamic routing problem in ATM cell-switching networks. The Tabu Search algorithm is initialised with a minimum switching path algorithm (MSwP), which assigns the communication to that path with a minimum number of switches where no over-buffering is taking place (the MSwP pseudocode is described in the appendix). 4.1. Solutions encoding The feasible solutions are encoded, as is shown in Figure 5.The solution is therefore determined by a binary matrix with the following considerations: - Each solution must contain as many lines as periods of connection. We consider t as the time for an ATM communication (call scale). - Each of the lines is composed by a number of fields, M, representing the different origin-destination pairs of communication. - The field associated to each pair is depicted by so many elements as feasible paths exist between that pair of communication. Only one route is feasible for each communication, setting the value to 1. LOCATION FOR FIGURE 5 Figure 6 illustrates an example regarding the encoding of solutions. It corresponds to the network status for a feasible solution in a hypothetic call time division (period of connection) tx. The network considers four nodes and all the possible connections between them, consequently giving 12 possible connections between pairs of nodes. Each one has a set of feasible paths. It has to be taken into account that paths could be forbidden due to the delay condition, so not all the connections will necessarily have the same number of feasible paths. We address two specific connections in the example, showing three feasible paths for each of them, whose links (pair of nodes) are detailed. The figure only shows the feasible set of paths for the first two connections, in order to gain clarity. The proposal of the example gives a row for the time period, tx, corresponding to the specific row of the binary matrix detailed in Figure 5, which should be given as is described in Figure 6. That is, the binary register corresponding to paths h2 and h6 must be set to 1, while the remaining registers are set to 0. LOCATION FOR FIGURE 6 4.2. Cell loss evaluation The quality of each solution is assessed in terms of the total cell loss. To do so, each feasible solution can be evaluated according to the process described below. Once the variable Ph m,t has been fixed (following the Figure 5 encoding) the conditions and constraints of the model can be rewritten as follows: 8 (4.1) ⎪ ⎩ ⎪ ⎨ ⎧ ≠ = =+ −O(m)i if O(m)i if 1, ,, τ τ ττ m ki m m ij m ij X A lX )(,,/),(),(),(),(:,, hNkjihEikhEjiNiMmt ∈ ∈ ∀ ∈ ∀ ∈∀∈∀⊂∀ τ (4.2) tiAqhEjiAXF MmiBqmOiMm m m qiij ⊂∀∈∈∀+= ∑ ∑ ∑ ∈∈ =∈ − τ τττ ),(:)(),( )()(/ 1, (4.3) ∑ ∈ ⊂∀∈∀∈∀≥ Mm ijij m ij thEjiNiFl τ τττ ),(),(,)( ,L (4.4) tMmEjilm ij ⊂∀∈∀∈∀≥ τ τ ,,),( 0 , (4.4) tMmEjiXm ij ⊂∀∈∀∈∀≥ τ τ ,,),( 0 , By grouping constraints 4.2 and 4.3 into one equation (4.6), the set of constraints of the model is reduced to: (4.5) ⎪ ⎩ ⎪ ⎨ ⎧ ≠ = =+ O(m ) i if O(m)i if , ,, τ τ ττ m ki m m ij m ij X A lX )(,,/),(),(),(),(:,, hNkjihEikhEjiNiMmt ∈ ∈ ∀ ∈ ∀ ∈∀∈∀⊂∀ τ (4.6.) ∑∑∑ ∑ ∈∈∈ =∈ −⊂∀∈∈∀∈∀+≥ MmMmiBqmOiMm m m qiij m ij tiAqhEjiNiAXl τ ττττ ),(:)(),(,)( )()(/ 1,, L (4.7) tMmEjilm ij ⊂∀∈∀∈∀≥ τ τ ,,),( 0 , (4.8) tMmEjiXm ij ⊂∀∈∀∈∀≥ τ τ ,,),( 0 , The grade of service constraint is removed from the model and is considered as a feasible control of the solutions, discarding those solutions that do not satisfy the grade of service control. Once the variable Ph m,t is specified, the model evaluation is much easier and the total cell loss can be calculated by a simple evaluation of the objective function. To do so we introduce the following procedure. Cell Loss evaluation procedure 1. For each τ in t: 1.1. Calculate: ∑ ∑ ∑ ∈∈ ∈=∈ −+= Mm hjiq iBqmOiMm m m qiij AXF ,, )()(/ 1, τττ 1.2. Calculate: )( , ττττ ijij Mm m ijij Fll L== ∑ ∈ 1.3. The cell loss for each connection is calculated by distributing the total τ ij lproportionality to the demand of the pair over the link (i,j). It is therefore calculated as: ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ =∑ ∈)(),(: , mhjim m m ij m ij A A ll τ τ ττ 9 1.4. Xij m,τ is calculated by means of the flow balance constraint (4.5), by substituting the cell loss values obtained in step 1.3. ⎪ ⎩ ⎪ ⎨ ⎧ ≠ = =+ −O(m ) i if O(m)i if 1, ,, τ τ ττ m ki m m ij m ij X A lX )(,,/),(),(),(),(: hNkjihEikhEjiNi ∈ ∈ ∀ ∈ ∀∈∀ 2. Calculate cell loss: ∑∑ ∑ ∑ ∈∈ ∈ ∈Ttt hEjiMm m ij l τ τ )(),( , 3. Test GoS feasibility: ∑ ∑ ∈∈ ≥ thEji mm ij GoSl τ τ )(),( , 4.3. Tabu Search algorithm characteristics The Tabu Search implementation is described in this section. Figure 7 depicts the Tabu Search algorithm. LOCATION FOR FIGURE 7 The algorithm starts from a feasible solution (current solution) that is supplied by the MSwP algorithm. This is a first promising solution. The algorithm consists of short-term memory (STM) and long-term memory (LTM) procedures. Both procedures are iteratively run during a maximum number of iterations. STM is processed every iteration while LTM is considered for processing every iteration although it is not always run (as Figure 7 depicts). The exploration of feasible solutions is carried out by searching the neighbourhood and making a “movement” from one feasible solution to another. Figure 5 depicted the solution encoding structure, and Figure 6 an encoding example. For example of Figure 6, a neighbour solution of the current solution is generated by changing the communication route (path) in a specific pair of communication (m∈M) for a specific period of connection (t∈T). Figure 8 shows a neighbour solution swapping the bit corresponding to the first connection (m = I) and the period tx. The neighbourhood is constructed of all the neighbour solutions of the current solution, that is, for every connection (set M), every possible swap of paths of such connection (set H(m)), and every call period (set T). LOCATION FOR FIGURE 8 Each iteration provides a new solution that is found by making a definitive local movement over the current solution within the neighbourhood. The next solution is selected as the best one within all the possible solutions in the neighbourhood, according to the previous description of the neighbourhood. In this sense a chain of solutions is constituted by all the enchained adjacent solutions. STM is responsible for the optimal enchaining of these solutions, depicting a trajectory. The trajectory is a consequence of the quality of the solutions and a tabu filter depicting an intelligent exploration, meanwhile the LTM periodically analyses whether the trajectory is acceptable or the process should not follow this path and the algorithm should move back to take another more promising path to configure a new trajectory.