Μελέτη τεχνικών δρομολόγησης σε δίκτυα μεταβαλλόμενης τοπολογίας

Abstract

This doctoral thesis deals with the study of routing techniques in networks of periodic and stochastically varying topology. To facilitate this research, two types of networks were studied, namely satellite and ad-hoc networks. These two types constitute a remarkable research challenge, besides being in the center of commercial interest. The objective of this thesis was to formulate and analyze the problems inflicted to the routing procedure by a network’s varying topology, as well as to propose new, flexible and efficient routing algorithms able to cope with the aforementioned problems. A thorough review of proposed routing techniques is presented in the first chapter of this thesis. It is accompanied by a detailed classification of routing protocols, which is based on analyzing the routing procedure into three basic mechanisms. This approach enables us to identify the crucial issues that will be addressed in the following chapters. In the second chapter, the problem of routing in satellite networks of Low and Medium Earth Orbit is addressed. Two independent subsystems, namely the space segment and the Up-Down link are identified. The first step of the presented study involves the formulation of problems relevant to routing in the periodic context of the space segment. Examples are, the non-continuous operation of inter-satellite links, the non-uniform and time-varying geographic distribution of traffic, as well as the great size and connectivity of the formatted network. These specific problems were studied in detail through the implementation of a modified Dijksta’s algorithm, which is based on the selection of k-shortest paths. The above-described study led to the proposal of a modified algorithm based on the well-known Flow Deviation method, which belongs to the optimal routing family and was originally proposed for terrestrial networks with fixed topology. The new algorithm, called Modified Flow Deviation (MFD), was amended to overcome the problems of handover and traffic non-uniformity. Some of the modifications include the use of a set of only k paths, the dynamic determination of this set and the forwarding of traffic on connection-oriented basis. MFD is compared with a traffic adaptive Dijkstra algorithm, and is proved to present an improved performance in terms of rerouting actions and uniform network loading. Finally, in the same chapter, some heuristic metrics describing the specific characteristics of satellite systems are proposed and studied. Specifically, two metrics were investigated and proved to perform efficiently when used with a simple shortest path algorithm. To complete the study of satellite systems, in the third chapter the Up-Down link management is investigated. After presenting the algorithms proposed so far, a new one, called Dynamic Doppler Based Handover Prioritization scheme (DDBHP) is presented. The proposed algorithm is based on evaluating the Doppler shift to calculate the position of a mobile user. The detailed mathematical model used for this purpose is also presented. The simulation tests, comparing its performance to that of the two most popular algorithms, prove that DDBHP not only guarantees the handover procedure but also utilizes the system resources more efficiently. Moreover, DDBHP provides a solution to two problems that have never been addressed in the past. The first concerns the procedure of handover when two different satellites are involved. The second one relates to the problems caused by cell overlapping and/or by earth’s motion. Finally in this chapter, a detailed queuing model is presented for approximating the performance of DDBHP’s performance. The results obtained, confirm the validity of the proposed model. In the fourth chapter, our study is broadened to include issues of routing in stochastically varying topologies. Ad-hoc networks constitute the most representative field for this kind of research. After a detailed presentation of the so far proposed algorithms, we concentrate our study on on-demand protocols. First, a modification of the well-known DSR algorithm is presented. This involves permitting the destination host to reply to more than one request packets. This modification is proved to reduce the related routing load when the network topology changes quickly. In the following a new algorithm, named Sequence number Aided Source Routing (SASR), is proposed. SASR makes use of route caching to exploit all discovered routing information and at the same time uses sequence numbers to avoid the spreading of stale routing information. Furthermore, SASR does not use source routing in the discovery phase, in order to avert the waste of system resources. The comparison of SASR with DSR proves that the algorithm not only manages to alleviate the incurred routing load through all the mobility range, but also achieves significantly higher delivery ratio values. Another very important characteristic of the proposed algorithm is that the improvement achieved over DSR’s performance in terms of both delivery ratio and routing load increases with the network size. This fact renders SASR more suitable for networks of increasing size. A detailed asymptotic analysis of SASR is also developed in this chapter. The model proves that the complexity of SASR is significantly lower than this of DSR. Finally, at the end of this chapter, a test-bed implementing multi-hop routing in wireless networks is presented. The test-bed uses an architecture, according to which routing is performed on the data-link level. This fact secures the interoperability of the platform and provides easy and flexible implementation. Finally, the fifth chapter summarizes the proposed solutions in each scientific domain and comments on the benefits of each one. Then, useful conclusions are drawn and an overall evaluation of the scientific research contacted in this thesis is done.