Tối ưu hóa viễn thông và thích nghi Kỹ thuật Heuristic P10

Chia sẻ: Tien Van Van | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST

Báo xấu

45
lượt xem 4
download

Tối ưu hóa viễn thông và thích nghi Kỹ thuật Heuristic P10

Mô tả tài liệu

Download Vui lòng tải xuống để xem tài liệu đầy đủ

All point-to-point communication networks have a means of directing traffic from a source to a destination via intermediate nodes. This routing function must be performed efficiently as it affects all aspects of network communications including jitter, latency and total bandwidth requirement. Other issues related to routing, such as policing and traffic control are not dealt with in this chapter. There are two distinct approaches to ‘routing’ traffic, namely connection-oriented and connectionless. ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tối ưu hóa viễn thông và thích nghi Kỹ thuật Heuristic P10

Telecommunications Optimization: Heuristic and Adaptive Techniques. Edited by David W. Corne, Martin J. Oates, George D. Smith Copyright © 2000 John Wiley & Sons Ltd ISBNs: 0-471-98855-3 (Hardback); 0-470-84163X (Electronic) 10 Optimization of Restoration and Routing Strategies Brian C.H Turton 10.1 Introduction All point-to-point communication networks have a means of directing traffic from a source to a destination via intermediate nodes. This routing function must be performed efficiently as it affects all aspects of network communications including jitter, latency and total bandwidth requirement. Other issues related to routing, such as policing and traffic control are not dealt with in this chapter. There are two distinct approaches to ‘routing’ traffic, namely connection-oriented and connectionless. Connectionless networks use information contained within the data packet itself. Typically the destination address is all that is required, however explicit routing information may also be contained within the packet. Connection oriented networks establish the route first and subsequently use it for all traffic associated with the connection until it is torn down. In both cases, a method is required for the efficient identification of either a route for the packet or a route for the connection being established. 10.1.1 The Traditional Approach Traditionally, routing has been static with permanent routes established in the switches or dynamic with routes established according to the traffic flow at the time. In static routing manual updates to the routing tables is still a common occurrence for connection oriented networks, and is frequently based on the experience of the network manager. Different forms of shortest path routing method (Steenstrup, 1995) are usually employed to assist in Telecommunications Optimization: Heuristic and Adaptive Techniques, edited by D.W. Corne, M.J. Oates and G.D. Smith © 2000 John Wiley & Sons, Ltd
168 Telecommunications Optimization: Heuristic and Adaptive Techniques designing these routes. It should be noted that the ‘length’ of a link may be associated with time delay, blocking probabilities or financial cost, not just a hop count. In particular flow deviation (Kershenbaum, 1993) can be very effective if a single route between node pairs is required. There are no strong time constraints on this activity. An alternative approach is to establish routes dynamically, allowing the network to respond to changes in traffic, either when a route is established or a packet is received. Different forms of link-state and distance vector routing (Tanenbaum, 1996) are used which are designed to cope with the network’s distributed nature. These are combined with a form of hierarchical addressing in order to make routing tables both manageable and efficient. Occasionally node or link failures occur, which requires rerouting a large number of connections, this activity is known as ‘restoration’. Unlike normal routing, a large number of routes must be re-established in real-time. Although the normal techniques for dynamic routing can be applied, it is likely to be far more efficient to look for the best set of routes for the system as a whole rather than individually route according to the normal methods. However the network must also ensure that the sudden activity generated by the failure does not overwhelm the switches and that restoration occurs on an appropriate time scale (
Optimization of Restoration and Routing Strategies 169 difficulties, for example, time delay is ignored even though it is a critical parameter for real-time interactive voice and video traffic. In addition a simple connection count will not take account of prioritisation. One of the major concerns associated with costing networks is that the users’ view of the worth of a connection does not correlate well with bandwidth. Traffic is not constant bandwidth, so connections may be assigned an effective bandwidth that is believed to be sufficient to ensure the connection can be maintained. In practice, the smallest effective bandwidth cannot be calculated in isolation from the rest of the traffic. Two Variable Bit Rate (VBR) connections can share significant bandwidth if there is little correlation between the two on peak usage. However two Constant Bit Rate (CBR) connections or a VBR plus CBR cannot. At present, traffic on networks is not well enough characterised to allow detailed calculations and even if it can be accurately simulated the time-scale would be prohibitive for evolutionary techniques due to the large number of evaluations required. In practice the following metrics are used, ignoring some of the complexities of real traffic flow. • Average number of hops (or average number of hops per call) • Maximum or average residual link capacity • Maximum or average network delay • Number of unserved circuit demands or packet discards a closely linked alternative is the average utilisation or maximum utilisation levels • Total network throughput As the M/M/1 queuing model is often assumed the average network delay (T) is: 1 l  fi  T= ∑ .   γ i =1  Ci − f i    where γ is the total arrival rate for the network (messages/sec), l is the number of links in the network, fi is the flow rate for link i (bits/sec), and Ci is the capacity of link i (bits/sec). In practice the total network delay is faster to calculate than the mean and differs only by γ. Any more detailed calculations are likely to be extremely network-dependant. Establishing benchmarks for realistic traffic generation and accurate simulations is still a problem for researchers in this area. The following papers contain or refer to some data on topolgies and traffic (Dutta and Kim, 1996; Mann, 1995; Turton and Bentall, 1998; Gavish and Neuman, 1989; Mann and Smith, 1996). In practice the simple M/M/1 queuing model (Mazda, 1996) is used rather than detailed simulation due to time constraints. 10.2.2 Timing and Efficiency All evolutionary techniques require significant computational time. Consequently, the approaches used have either had to deal with small numbers of routes or pre-calculate
170 Telecommunications Optimization: Heuristic and Adaptive Techniques solutions. A reasonable commercial backbone network may well have over fifty nodes and a degree of four. The typical number of routes broken by a single link failure depends on the technology used. In ATM over a hundred paths could be disrupted. Each path is likely to have hundreds of alternate routes if capacity constraints are ignored. If these values are used as reasonable guides to the size of the problem the inherent time scale difficulties are exposed. Despite these problems there are some positive points. Computer power is rising exponentially and networks are not random meshes, operators want to reduce costs and often base their networks on rings with additional chords. Consequently, the number of loop-free alternate routes is much smaller than a worst case scenario indicates. Nevertheless, EAs often have a run time of hours when sub-second times would be ideal. 10.3 An Evolutionary Approach to Routing and Restoration A number of issues have been tackled by researchers relating to routing and restoration. This section will outline some of the approaches taken, followed by more detailed examples. Despite the real-time nature of restoration algorithms, it is possible to use evolutionary algorithms to set up a strategy that is continually updated and provides a set of pre-planned routes to a restoration algorithm. If the system can be informed of traffic requirements before they need to be routed, the same algorithms can be used for routing. Chng et al. (1994) describe a multi-layer restoration strategy which uses this technique and demonstrates its effectiveness. Consequently an evolutionary algorithm is only disadvantaged by the fact the routes are always based on slightly dated information. The nature of the network and traffic will therefore determine the usefulness of this approach. 10.3.1 Evolving Paths A number of authors encode an index to a table of alternate routes (Mann and Smith, 1996; Shimamoto et al., 1993; Sinclair, 1998; Al-Qoahtani et al., 1998; Tanderdtid et al., 1997). Typically the k-shortest paths are used within the table, but as pointed out by Mann and Smith (1996), this may not be the ideal technique. The advantage of this method is that the alternate routes available can be selected appropriately and then uniform, single point or two-point crossover can be used to recombine the chromosomes. Mutation is achieved by simply swapping to another randomly selected path. Results from several authors indicate that this approach compares well with traditional techniques and performs at roughly the same level when compared with simulated annealing. The key disadvantage is that only a limited number of alternate routes are stored and the user, not the algorithm, chooses the set of routes. By making this choice, before running the GA, some viable and effective options may not be considered. Alternatively, if all routes are available in the tables, possibly with limited lengths, a single population cannot contain indices to all routes. The algorithm will find it difficult to search the set of viable routes. Pre-seeding the populations where useful solutions are available has been shown to improve performance by ensuring some good sets of paths are included. Seo and Choi (1998) developed an evolutionary algorithm designed to find a good set of alternate paths. Paths between a particular source and destination are stored as an ordered list of nodes. Where common nodes exist sections of path between the common nodes can
Optimization of Restoration and Routing Strategies 171 be interchanged. A repair operator is used to remove loops caused by the recombination. Mutation selects two nodes at random and generates a new partial path between the two nodes. The fitness function is based on the number of common nodes, the common links ratio and area surrounded by the set of alternate paths. Apart from the computational cost the authors reported good results. Cox, Davis and Qui (1991) used a request permutation technique to route the call requests. For their problem, a series of traffic demands are sent that must be fulfilled at some future time. A set of paths has been predetermined for each source destination pair and call type. They suggeet a k-shortest paths (k ~ 4) approach is used with constraints for the particular call type. In addition a set of path assignment probabilities based on the traffic patterns is stored. Call requests are initially assigned paths according to the static set of path selection probabilities. If the initial path selected is feasible then it is added to the list of pending requests ready to be connected at the assigned time. If the path is not feasible then an evolutionary algorithm is called that uses crossover and mutation to permute the order in which the call requests will be considered. The chromosome decoder will take each request in turn and check if the request can be assigned to any of the k- shortest paths previously calculated for the appropriate source destination pair. If a suitable path is found, its bandwidth is subtracted from the capacity available and the next request is considered. Once all the paths that can be assigned have been placed, a fitness value is calculated based on the cost of the capacity used for the set of paths and the cost of failing to route the outstanding requests. Uniform order-based crossover is used with scramble sublist mutation and an exponential fitness technique (Cox et al., 1991). Once the algorithm has terminated, the solution undergoes a simple pair wise swapping of each adjacent pair of requests in turn. If any swap improves the schedule it is incorporated into the schedule. At this point the new call can be accepted if all requests can be accommodated, or rejected. For small networks greedy heuristics, integer programming and ‘random’ search were effective. The evolutionary approach proved best technique for larger networks (~50 nodes or more). An alternative approach was taken by Bentall et al. (1997), using a two-dimensional encoding with an unusual permutation based crossover technique. They use loopless paths, limited in maximum length, within the chromosome. The procedure is quite different from those discussed so far and so a detailed explanation is given at the end of the chapter. 10.3.2 Evolving Routing Tables An alternative to defining paths for each traffic requirement or source/destination pair is to evolve the routing tables themselves. Sinclair (1993) uses a set of integers for each valid node-pair. The number of integers corresponds to the degree (d) of the originating node. The integers are ordered and the first two integers must be in the range 0 to d–1. All subsequent integers must be in the range 0 to d–2. Each node has an ordered list of connected nodes. The first integer x refers to the (x+1)th node as the first choice node to transmit to. Subsequent integers refer to the xth node where a zero means no more choices are available. When trying to establish a call, if none of the choices result in a successful transmission the call will be referred back to the previous node to ascertain if it can successfully try another route. In the event of backtracking to the source node, and having no choices available, the call is lost. Despite using step change and offset inverse penalty
172 Telecommunications Optimization: Heuristic and Adaptive Techniques functions to discourage loops within the network, results obtained by the author were not as good as previous non-evolutionary work. Munetomo et al. (1998; Chapter 9, this volume) have produced an algorithm which uses the distributed nature of a network to assist in forming routes. Each node is responsible for evolving routes from itself to other nodes. Each chromosome consists of an ordered set of nodes starting at the node holding the population and finishing at any of the other nodes in the network. Recombination is only allowed for chromosomes that share the same destination. The potential crossing sites are those nodes that are held in common by the two parents. The segment between the two common nodes is swapped. Crossover cannot take place if only the source and destination nodes are held in common. Mutation is performed by randomly selecting a node in the network and finding the shortest path from the source to the node and from the node to the destination. If these paths are not disjoint, the mutation is rejected. Network nodes can send information between their respective populations. The best chromosomes are ‘migrated’ from a node to an adjacent node. However, the transferred chromosomes will, initially, have the wrong start node listed in the chromosome. If the receiving node is referred to in the ‘migrated’ chromosome then it is simple to convert by simply deleting the nodes between the original source node and the new node in the chromosome. If the node is not contained within the chromosome it can be added to the front of the chromosome as the receiving node must be connected to the transmitting node (migration occurs between two adjacent nodes). Fitness is assessed by periodically sending messages down the paths and measuring the delay. The delay is then converted to a fitness value. Routing is done by weighting each route according to the fitness of the chromosome. The packets are then statistically transmitted based on the relative weights of the routes. To limit the number of routes, one with a low weight may be deleted from the population. The authors claim that the technique is novel and robust. No comparative results are presented. An alternative approach to encoding the routes in a routing table is to design routing rules that are reasonably fault-tolerant (Kirkwood et al., 1997; Shami et al., 1997). Genetic programming can be used to devise a set of rules that can be used to route traffic. In Shami et al. (1997) the problem specific expression is defined as follows, where X, Y and Z refer to nodes that the traffic should be sent to. An example rule might be (IF-CUR-GO W X Y Z); this means: if the current node is W, send the traffic to X, as long as W and X are directly connected, and node X has not been visited twice before. If W and X are not directly connected, or X has been visited twice before, then send the traffice to Y. If the current node is not W, then send the traffic to Z. A multiple population approach was used so that each epoch five individuals were sent to replace the worst five individuals in an adjacent population. Three sub-populations were used in the form of a ring and a hierarchy. Initial results have proved to be disappointing. However, the authors are planning to investigate evolving software agents in order to make the solution more scaleable. 10.3.3 Ring Loading This area could be considered to be capacity planning or routing. In a ring there are only two possible routes. Once these have been determined the capacity of the ring is forced. As
Optimization of Restoration and Routing Strategies 173 all links have the same capacity the routing algorithm must distribute the load as evenly as possible. More formally (Mann and Smith, 1997):  max     min   ∑ {t (v, w)xt (v, w) + t (v, w)yt (v, w)}  e ∈ E v , w∈V     subject to: xt (v , w) + yt (v, w) = 1 xt (v , w) , yt (v, w ) ∈ {0,1}∀t (v, w) ∈ T where: 1 clockwise xt (v, w) =  0 anti − clockwise 1 anti − clockwise yt (v ,w ) =  0 clockwise in which e is one of m members of the set of edges E. Each edge has a cost c(e). Nodes v and w are members of the set of n nodes N, t(v,w) is the traffic between the two nodes v and w from the set of traffic requirements T, and is routed along the path P(v,w). This problem is difficult because the traffic may not be split. The chromosome is represented by a binary value (clockwise or anti-clockwise) in a gene per node pair. Fitness is evaluated as a weighted sum of the path cost and the maximum load, which allows unnecessarily long paths to be penalised. Uniform, single or multi-point crossover can be used along with single bit mutation. Mann and Smith (1997) have found that simulated annealing and genetic algorithms perform well on this type of problem. The genetic algorithm did not require fine tuning, whereas simulated annealing did, but could potentially produce slightly better solutions by fine tuning. Karunanithi and Carpenter (1997) have also produced good results using the same basic technique, but have compared it to a commercial linear and mixed integer linear programming package. Again, the best results did not differ significantly but the genetic algorithm approach was computationally expensive. 10.3.4 Unusual Applications Concurrent Point-to-Multi-point Routing Multicasting is expected to become an important area of telecommunications as large bandwidth applications between groups of people, such as video conferencing, become more common. Unlike the problems addressed earlier, a permutation based approach was used by Zhu et al. (1998) to identify the best set of trees to route a number of multicast
174 Telecommunications Optimization: Heuristic and Adaptive Techniques requests. In essence, the chromosome represents the order in which each request shall be considered. Each request in turn will be checked against the remaining capacity in the network. Any links that do not have sufficient capacity for the request are removed from consideration. A separate routine is then called to find an optimal or near-optimal Steiner tree. In practice a non-GA approach to this stage may be advisable due to time constraints, however a number of GA methods exist for this sub-problem (Leung et al., 1998). To focus the evolution on the appropriate genes, only the first k out of n requests are considered in forming the fitness function. A GA is run for increasing values of k until the GA is no longer able to find a solution that satisfies the indicated number of requests. For a particular k the object is to minimise the cost (capacity x cost for each link summed over all links). PMX crossover was used for permutation with roulette wheel selection. Adaptive Feedback to Distribute Loading Congestion does not necessarily respond well to non-adaptive feedback mechanisms, because of the time delays inherent in a network. Olsen (1997) suggests that adaptive feedback mechanisms should change their behaviour in the light of previous events, not merely react to changes in link costs. Dijkstra’s Shortest Path First (DSPF) is the algorithm used by Olsen to update routes depending on the link costs. The genetic algorithm determines which routes are best suited for updating. A binary string is used to indicate if a particular route should be updatable by DSPF. The GA uses single point crossover, single bit mutation and roulette wheel selection. Every chromosome in the population is used once, and the routing performance is analysed during that period. The inverse of the total link costs achieved during that period is used to set the fitness of the chromosome. The next generation can then be created. In addition to the aforementioned features, the GA could also adapt its crossover rate and enforce a minimum update rate irrespective of the values within the chromosome. The results were very impressive, 4-to-12 fold reductions in average packet delays and a 44% to 140% increase in average throughput. Some implementation details regarding how the information would be transmitted are also included in Olsen’s study. 10.3.5 Routing Combined with Design An unusual way of routing is to use it to drive the design process, Huang et al. (1997) looked into designing a 3-connected telecommunication network by finding three disjoint routes and using them to help design the network. The objective is to minimise total link costs subject to guaranteeing three disjoint links, a network diameter of less than seven and a maximum node degree of five. It does this by taking a predefined network graph and finding three optimal disjoint paths for every traffic requirement. The resultant sub-graph has minimal total link cost and will define the required capacity for every link. The chromosome is encoded by storing three groups of node numbers that define a path between source and destination. The number of nodes in a group is determined by the network diameter. An entry of 0 in the group indicates that the node number can be disregarded, thus allowing routes of less than the network diameter. No nodes can be repeated so the paths are guaranteed to be disjoint. This encoding enforces the critical diameter and connectivity constraints. Two-point crossover is used with a repair operator
Optimization of Restoration and Routing Strategies 175 that swaps back individual nodes that are duplicated in one chromosome of the offspring. Fitness is evaluated by calculating the cost of carrying the extra capacity along with an offset cost for the first time a link is utilised. The offset cost encourages the GA to choose solutions with fewer links than would otherwise be the case. The costs (Cmax to Cmin) are then linearised between 0 and 1 to produce fitness values. This approach can be adapted to different network diameters and connectivity constraints by increasing the number of nodes per route and the number of groups of nodes. The authors claim that for large networks the GA outperforms a method based on Dijkstra’s algorithm and compares favourably with the approach taken by Davis et al. (1993). Although the routes are defined using this method, since networks change slowly but traffic changes frequently, this may more fairly be considered network topology design using a routing approach. Davis et al. (1993) have combined design and routing into a three part chromosome which they label (X, W′, W′′). The first parameter, X, stores the capacities of each link. W′ encodes the order in which traffic demands are considered for routing. W′′ encodes the order in which traffic is routed for a network whose links have been reduced in capacity by a factor (0 ≤ s ≤ 1). Crossover is performed by applying uniform crossover to X and by applying uniform order-based crossover to W′ and W′′. Mutation randomly selects a link to have its capacity changed. A local mutation called ‘creep’ has a 0.3 probability of modifying a link capacity value, xi, within the range xi ± 5. Finally, ‘zero-link’ sets the value of the capacity of a link in X to zero. Ranking is used to set the fitness value, then a roulette wheel procedure is used for selection with probabilities of 0.4 for crossover, 0.15 for mutation, 0.4 for creep and 0.05 for zero-link The decoder takes each demand in W′ and attempts to route it down the k-shortest paths (typically 10). Routes that have used up their available bandwidth are not included. If there are no paths available the constraint violation parameter C is set to 1,000,000 and the demand is left unrouted. Otherwise as much demand as possible is routed down the available paths. If this still leaves unrouted demand, links on the first path are increased in capacity (repaired) until they can carry all the remaining traffic. An identical process is then followed for W′′. Fitness is then evaluated by assessing the link cost of the network (proportional to bandwidth + offset) plus the constraint violation penalty. The repaired chromosome has a 10% chance of replacing the original chromosome in the population; according to the authors this value may be too high. This method proved to be successful when compared with other methods on large problems. Mixed Integer Programming techniques were better for small problems. However, care had to be taken in controlling the number of shortest paths, and the number of links, available to the program. A very different three segment crossover technique has been proposed by Ko et al. (1997; 1997a). The chromosome is split into topology, routing and capacity assignment. The topology section simply uses a bit per node-pair to indicate if they are connected. The method of obtaining a set of routes for each node-pair is not defined. The routing section holds a list of indices to paths for each source/destination pair. Finally the capacity segment defines the capacity of each link. This is done by having a set of integers determing the number of each type of line for every link. Rules are used to ensure large numbers of low capacity lines are not used in preference to a single large line for a particular link. One- point crossover and random mutation are used on the topology and capacity segments. When assigning the capacity, the link must be able to carry the full flow requirement. Time delays are discouraged by the fitness function. Crossover between the routing segments
176 Telecommunications Optimization: Heuristic and Adaptive Techniques involves copying the shortest path for every requirement from either parent to the offspring, given the capacities defined in the capacity segment. Mutation randomly selects an alternate path with a probability of 5%. The authors demonstrate the results on a ten node problem that represents one of China’s major networks. The methods considered so far tend to use well understood crossover techniques with an unusual encoding. Cuihong (1997) has taken an entirely different approach to crossover. Each chromosome comprises two sections; the first section defines the capacity (type) of each link, the second has an index for each source/destination pair that points to one of a set of predefined legal routes. The initial population is assigned randomly. Fitness is calculated by subtracting the cost of the proposed network from the maximum feasible cost. The key parameters include time delay assuming an M/M/1 queue, a fixed cost per link and a cost per bit using a link. Each parameter is weighted to give an appropriate cost in the summation. Crossover is done by utilising a novel ‘orthogonal crossover’ operator (OCX). In OCX a series of random numbers are generated that define where to cut a chromosome into a number of segments (c). Each segment from two parents cut in this manner can be in one of two children. Clearly, the number of ways of arranging two sets of c segments to c create two children is 2 . This problem is well known in manufacturing and other areas where the number of combinations is too large to permit a full search of possibilities. Instead the best result can be found by doing a small sub-set of experiments by carefully choosing the combinations. Designing such experiments has been subject to a lot of mathematical analysis which is based on orthogonal arrays. However the analysis will not be strictly correct if any two parameters are coupled (epistasis). As a result of this problem some orthogonal arrays have been designed to allow certain parameters in the experiment to be coupled and still produce valid results. The author refers readers to an appropriate text (Montgomery, 1991). In practice, orthogonal arrays have proved to be effective even if the experimenter has not ensured the parameters are truly independent. Once the ‘experiments’ have been done, the best two combinations can be inserted as children into the new population. Mutation randomly chooses a link and calculates the link size by doubling the present size and subtracting a random link size in the legal range. The path is identified by doubling the index number for the existing path and then subtracting a randomly generated index number from the legal range. If the result is beyond the maximum legal value, it is lowered to the legal value; similarly, if it is below zero it is raised to zero. Roulette wheel selection and an elitist strategy select the individual chromosomes. 10.3.6 A Two-dimensional Encoding for Restoration The most common method for evolving routes is a simple index per traffic requirement to an alternate route, however as mentioned earlier, there are limitations to this approach. In this section, a detailed account of a two-dimensional order-based genetic algorithm. The time required is much greater than that used by the previously mentioned techniques, but the results which were obtained are potentially better due to the larger search space and enhanced use of genetic material. As this algorithm is intended for restoration in a heavily loaded ATM network the authors have assumed that all traffic cannot be re-routed. In network design this is often the case because low priority traffic does not need to be guaranteed in the event of link failure. By using effective bandwidths for reserving
Optimization of Restoration and Routing Strategies 177 bandwidth the time delay issue is largely circumvented. However the number of connections permitted is critical. The following description is largely based on work published at GALESIA’97 (Bentall et al., 1997). Figure 10.1 Example test networks based on real networks. Test Problem For each path over a failed link many alternative paths exist. The number of alternative paths is highly dependent on the maximum number of hops each alternative path is allowed to take. For example, in test network ‘net32-65’ (see Figure 10.1) and with a maximum hop count of 5 the number of alternative paths for one particular link is, on average, 14.71. However if the maximum hop count is increased to 8, then the average number of alternative paths increases to 733.65. Within the test network, over 2000 virtual paths are
178 Telecommunications Optimization: Heuristic and Adaptive Techniques randomly generated resulting in between 30 and 250 virtual paths using any particular link. Even for a link with a below average number of paths, for example 80, utilising its capacity, and a maximum hop count of 7 (average of ∼280 virtual path alternatives), contains 28080 possible solutions. A Two-dimensional Structure for Path routing The algorithm is based on an order-based genetic algorithm with each chromosome represented in two dimensions, allowing failed paths and path sets to be evaluated. Figure 10.2 GA population structure. Data Structure Figure 10.2 shows the two-dimensional structure of the population as implemented in the simulator. The restoration order of the failed paths is represented in the first dimension of the chromosome. For each restoration path there exists a number of alternative paths. Each alternative must be tried until an acceptable path is found. The order in which an alternative path will be selected from the set of alternatives is represented in the second dimension. Fitness Function The original purpose of this work was specifically for restoration in heavily loaded networks where some paths would be lost. As it is also connection oriented, effective
Optimization of Restoration and Routing Strategies 179 bandwidths must be assumed for each requirement rather than actual traffic levels. The fitness is based on the success of the chromosome in finding acceptable routes to restore all failed paths. For each chromosome there are two elements representing its fitness. The first element is a direct representation of the number of paths restored. The second element represents the efficiency of the chromosome in keeping spare capacity for future use. The second element can only be fairly compared with other solutions that restore the same number of paths. Consequently, the second element is linearised between 0 and 0.9 for a particular generation and number of restored paths. This figure is then added to the number of paths restored to produce a final fitness value. Figure 10.3 provides an example of a typical score. Note that the second element is only used in the parent selection process and has no meaning outside the current population. 0.9 × ( Ci − C( w ,r ) ) Scorei = ri + ( C( b , r ) − C( w , r ) ) Figure 10.3 Scoring function. The full fitness function is given in equation 10.1, where i is the chromosome under consideration, r is the number of paths successfully restored, C is the capacity remaining, and C(b,r) and C(w,r) represent the capacity remaining for the best and worst case chromosomes respectively with r failed paths restored within this current population. 0.9 × (Ci − C( w, r ) ) Fitnessi = ri + (10.1) (C(b, r ) − C( w, r ) )
180 Telecommunications Optimization: Heuristic and Adaptive Techniques Figure 10.4 Example crossover. This function enables us to ensure that chromosomes restoring a greater number of paths will always have a greater chance of selection. However, chromosomes that have equal scores are also graded according to the spare capacity remaining within the network after restoration. Chromosomes with the most capacity remaining are fitter, and therefore have a better chance of parent selection. Evolution Operators The genetic algorithm is constructed from three evolutionary operations, each fed by a linearised roulette wheel parent selection process. The parent selection process linearises the scores between 0 and 1 before the roulette method is used to select the parent(s). The operators used are order-based mutation, and order-based, 2-dimensional, 2-point crossover. Mutation The mutation process selects two genes within the parent and exchanges their order, producing a single mutated child. The mutated genes’ counterpart chromosomes are exchanged to ensure that each gene maintains its associated path set.
Optimization of Restoration and Routing Strategies 181 Crossover The crossover operator is completed in two phases using a standard two-point order-based crossover on two parents, producing two children. The first phase applies order-based crossover to the first dimension and thus acts on the failed paths’ restoration order (see Figure 10.4). When the children of parents 1 and 2 have been evaluated in the first dimension, second dimension crossover is performed (phase 2). Each gene represents a particular path that should be restored. If the gene is selected for crossover then the corresponding gene, same path, in the other child is used. This ensures that a path set (gene) only evolves with other instances of the same path set within different chromosomes. The probability values used in this implementation are 2% mutation and 70% crossover, with a 50% chance for each gene performing crossover in the second dimension. The remaining 18% constitute reproduction. Figure 10.5 Functional and data flow diagram of network generation and GA operators within the simulator. The simulator is also used to evaluate the genetic algorithm with respect to other techniques. To calculate restoration benchmarks for comparison with restoration algorithms, the topology of the test networks and the assignment of capacity must be decided. The networks selected for testing combine a selection of pre-published, real and evaluation networks. For commercial reasons, the real networks include in this text have slight alterations. The networks’ names represent the number of nodes and the number of links, for example ‘net49-78’ has 49 nodes and 78 links. Two of the test networks are
182 Telecommunications Optimization: Heuristic and Adaptive Techniques shown in Figure 10.1. Random virtual networks of a controlled fitness are created within these networks during each simulation group. Once the topology has been established, the quantity of spare capacity must be decided for each link. This is critically different to all other simulations to date. For network implementation the simplest spare capacity allocation is formed from assigning a minimum load to each link. Therefore, the authors have set a flat rate of 90% load to all links. Using this assignment technique produces a network containing links with differing capacities, therefore allowing the algorithms to be tested under a variety of different conditions in one network. The simulator has several control parameters for the virtual network structure algorithm. The virtual network parameters include Virtual Path (VP) length control, VP capacity control, Number of VPs and Network Load. Figure 10.5 provides a functional and data- flow picture of the operation of the simulator. Further details of the simulator can be found in Bentall et al. (1997). An example of the results can be seen in Figure 10.6, showing the genetic algorithm results compared with random search for a single-link failure scenario. The two- dimensional encoding of this genetic algorithm performs well in terms of the routes restored but is computationally expensive. At present, the GA is too slow to be used as a real-time restoration algorithm because of the time it takes to perform the calculations. At present, the technique is thus best used in establishing a benchmark for other algorithms. 55 50 Re sto red 45 Pat hs 40 GA 35 Random Search GA Average 30 0 50 100 150 200 250 300 350 Generation Figure 10.6 GA vs. random search for a single link failure scenario. 10.4 Future for Evolutionary Algorithms in Restoration/Routing A wide variety of approaches have been tried over the last decade. Most of them have shown great promise but are limited by the time it takes to process the information.
Optimization of Restoration and Routing Strategies 183 However, given the rapid improvements in processing power and the accelerated performance possible with parallel genetic algorithms, this may not be such a large problem in the future. Work on parallel genetic algorithms is continuing and hardware implementations are being studied. Both ordinary and permutation-based crossover techniques have been designed for hardware implementation (Turton and Arslan, 1995; 1995a). The hardware systems envisaged at present have the potential to work over six orders of magnitude faster than a conventional general purpose computer, and when mass- produced would be a tenth of the cost. There are some who keep predicting that soon there will be more bandwidth available than can conveniently be used and therefore routing may not be a problem. However, all the signs at present indicate that greater capacity generates more traffic. In addition, users like to get the greatest possible use from their leased lines. New challenges will appear as mobile communication systems become more prevalent. Routing a call when the destination may suddenly change to a different part of the network, with different and variable error rates is going to cause far more fluctuations in traffic and link failures. Even traditional networks are growing so large that congestion and flow control are proving to be a problem as Olsen’s paper indicates. There is no doubt that evolutionary algorithms hybridised with other techniques and supported by advances in electronics will continue to generate both interesting problems and solutions.

CÓ THỂ BẠN MUỐN DOWNLOAD