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

This chapter describes the joint application of two soft computing methods – evolutionary algorithms and fuzzy reasoning – to the problem of adaptive distributed routing control in packet-switched communication networks. In this problem, a collection of geographically distributed routing nodes are required to adaptively route data packets so as to minimise mean network packet delay. Nodes reach routing decisions locally using state measurements which are delayed and necessarily only available at discrete sampling intervals. ...
Nội dung trích xuất từ tài liệu:
Tối ưu hóa viễn thông và thích nghi Kỹ thuật Heuristic P8 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)8Routing Control in PacketSwitched Networks using SoftComputing TechniquesBrian Carse, Terence C. Fogarty andAlistair Munro8.1 IntroductionThis chapter describes the joint application of two soft computing methods – evolutionaryalgorithms and fuzzy reasoning – to the problem of adaptive distributed routing control inpacket-switched communication networks. In this problem, a collection of geographicallydistributed routing nodes are required to adaptively route data packets so as to minimisemean network packet delay. Nodes reach routing decisions locally using state measurementswhich are delayed and necessarily only available at discrete sampling intervals. Interactionsbetween different nodes routing decisions are strong and highly non-linear. Extant routingmethods in packet-switched networks (Khanna and Zinky, 1989) mostly employ, in oneform or another, some direct form of least-cost or ‘shortest-path’ algorithm (Dijkstra, 1959)operating at each routing node. Such methods pay little attention to the dynamic interactionsof routing decisions made at different nodes and do not directly address the temporal effectsof delayed measurements and persistence of the effects of routing choices. This contribution proposes a very different approach to the routing problem. The routingpolicy of routing nodes is determined by a fuzzy rule base, which takes as inputs variousnetwork state measurements and provides route selection probabilities as outputs.Telecommunications Optimization: Heuristic and Adaptive Techniques, edited by D.W. Corne, M.J. Oates and G.D. Smith© 2000 John Wiley & Sons, Ltd.138 Telecommunications Optimization: Heuristic and Adaptive TechniquesA Genetic Algorithm (GA) is used to optimise these fuzzy rule bases. At each generation ofthe GA, identical copies of each candidate fuzzy rule base are deployed to routing nodes.Fitness evaluation for each individual fuzzy rule base is based on the network-wideperformance of the distributed assembly of routing controllers. The layout of the chapter is as follows. The following section (section 8.2) concentrateson some preliminaries and offers a background on the adaptive distributed routing problem,and on fuzzy logic and fuzzy control. Section 8.2 also gives a brief overview of some otherapproaches which use the genetic algorithm to optimise fuzzy rule bases. Section 8.3describes two versions of a fuzzy classifier system (a non-temporal version and a temporalversion) used as the basis for experiments; this section then provides experimental results inapplying the fuzzy classifier systems to routing control. Performance of the evolved fuzzyrouting controllers is compared to that of routing using other methods. Finally, section 8.4concludes and offers suggestions for further work.8.2 Preliminaries8.2.1 Adaptive Distributed Routing in Packet Switched NetworksCommunication networks employ two major methods of switching: circuit-switching andpacket-switching (refer to Schwartz (1987), Stallings (1994) and Tanenbaum (1996) fordescriptions of these switching methods). In the former, a dedicated amount of networkbandwidth is allocated to a source-destination pair during a circuit set-up phase and end-to-end delays are usually small and fixed. These characteristics have lead to the widespreadadoption of circuit-switching for telephony and real-time video. However, circuit-switchinghas the drawback of making inefficient use of network resources when information sourcesgenerate ‘bursty’ or sporadic traffic. Packet-switching attempts to overcome this problem byemploying a distributed form of statistical or dynamic multiplexing. Each network useroffers packets to the network and these packets are routed through the network by Packet-Switching Exchanges (PSEs) on a store-and-forward basis. Link bandwidth is no longer pre-allocated at connection set-up time, but instead each PSE maintains a queue of packets to bedelivered over a particular outgoing link. Two main ways of implementing packet-switchednetworks have emerged: virtual-circuit and datagram. In virtual-circuit packet-switchednetworks, a connection set-up phase establishes a fixed path through the network between asource-destination pair (although it does not allocate network bandwidth). For the durationof a connection, all packets follow the same path through the network. In datagramnetworks, no connection set-up phase is involved and subsequent packets between a source-destination pair may take different routes through the network. While packet-switchingmakes better use of network resources for bursty traffic sources, end-to-end delays arevariable and depend on the level of traffic offered to the network. This characteristic hasmeant that such networks have, until recently, been ruled out for conveyance of real-timeinformation sources such as telephony and real-time video. The currently developingBroadband Integrated Services Digital Network (B-ISDN) is intended to convey telephony,video and computer–computer information over the same network. It is almost certain thatB-ISDN networks will employ Asynchronous Transfer Mode (ATM), implying that B-ISDN will be a packet-based network (using fixed size packets called ‘cells’).Routing Control in Packet Switched Networks using Soft Computing Techniques 139 Routing policies in computer ...