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

As Internet connectivity is reaching the global community, information systems are becoming more and more distributed. Inevitably, this overnight exponential growth has also caused traffic overload at various places in the network. Until recently, it was believed that scaling the Internet was simply an issue of adding more resources, i.e. bandwidth and processing power could be brought to where they were needed.
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 P13 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)13Adaptive Demand-basedHeuristics for Traffic Reductionin Distributed InformationSystemsGeorge Bilchev and Sverrir Olafsson13.1 IntroductionAs Internet connectivity is reaching the global community, information systems arebecoming more and more distributed. Inevitably, this overnight exponential growth has alsocaused traffic overload at various places in the network. Until recently, it was believed thatscaling the Internet was simply an issue of adding more resources, i.e. bandwidth andprocessing power could be brought to where they were needed. The Internet’s exponentialgrowth, however, exposed this impression as a myth. Information access has not been andwill not be evenly distributed. As it has been observed, user requests create ‘hot-spots’ ofnetwork load, with the same data transmitted over the same network links again and again.These hotspots are not static, but also move around, making it impossible to accuratelypredict the right network capacity to be installed. All these justify the requirement todevelop new infrastructure for data dissemination on an ever-increasing scale, and thedesign of adaptive heuristics for traffic reduction. In this chapter, we develop a distributed file system model and use it as an experimentalsimulation tool to design, implement and test network adaptation algorithms. Section 13.2describes in detail the distributed file system model and explains the implementedsimulation environment. Two adaptation algorithms are developed in section 13.3. One isTelecommunications Optimization: Heuristic and Adaptive Techniques, edited by D.W. Corne, M.J. Oates and G.D. Smith© 2000 John Wiley & Sons, Ltd224 Telecommunications Optimization: Heuristic and Adaptive Techniquesbased on the ‘greedy’ heuristic principle and the other is a genetic algorithm tailored tohandle the constraints of our problem. Experiments are shown in section 13.4, and section13.5 gives conclusions and discusses possible future research directions. 1(7:25.Figure 13.1 A schematic representation of the network and the distributed file system.13.2 The Adaptation Problem of a Distributed File SystemThe World Wide Web is rapidly moving us towards a distributed, interconnectedinformation environment, in which an object will be accessed from multiple locations thatmay be geographically distributed worldwide. For example, a database of customers’information can be accessed from the location where a salesmen is working for the day. Inanother example, an electronic document may be co-authored and edited by several users. In such distributed information environments, the replication of objects in thedistributed system has crucial implications for system performance. The replication schemeaffects the performance of the distributed system, since reading an object locally is fasterand less costly than reading it from a remote server. In general, the optimal replicationscheme of an object depends on the request pattern, i.e. the number of times users requestthe data. Presently, the replication scheme of a distributed database is established in a staticfashion when the database is designed. The replication scheme remains fixed until thedesigner manually intervenes to change the number of replicas or their location. If therequest pattern is fixed and known a priori, then this is a reasonable solution. However, inpractice the request patterns are often dynamic and difficult to predict. Therefore, we needAdaptive Demand-based Heuristics for Traffic Reduction in Distributed Information Systems 225an adaptive network that manages to optimize itself as the pattern changes. We proceedwith the development of a mathematical model of a distributed information/file system. A distributed file system consists of interconnected nodes where each node i, i = 1,N hasa local disk with capacity d i to store files – see Figures 13.1 and 13.2. There is a collectionof M files each of size s j , j = 1, M . Copies of the files can reside on any one of the disksprovided there is enough capacity. The communication cost c i ,k between nodes i and k(measured as transferred bytes per simulated second) is also given. User Community NETWORK ...