Abstract
The Internet has changed substantially from a limited communication tool to a fully interactive information sharing environment. Quality of Service (QoS) Oblivious applications such as messaging and email have lost their dominance to time-critical and bandwidth-intensive multimedia services such as Voice over Internet Protocol (VoIP), video conferencing and Video on Demand (VoD). This considerable change in QoS demand places a heavy burden on the Internet design, including its underlying network protocols. Solutions such as multipath routing have therefore been proposed to improve data delivery performance and capacity by spreading the distribution of traffic using the network’s inherent path diversity. Although these network-oriented techniques are useful for Internet Service Providers (ISPs) to engineer their resources effectively, they do not necessarily satisfy the requirements of end-users. The reason is that the exclusive control of ISPs in determining the data paths prevents the end-users from reacting to QoS degradation caused by congestion in that path, even after they have noticed such QoS deterioration. On the other hand, granting full source routing capabilities to end-users has its own disadvantages. Firstly, these end-users require regularly updated knowledge of the network topology and its traffic, which is not scalable and would impose a large overhead on the network. Secondly, the computed source routes may violate the ISP traffic engineering policies or may cause network congestions. To address the problems of network-controlled and source-controlled routing paradigms, this thesis considers a middle cooperative approach between ISP and users, which provides a modest amount of control for the end-user to select the path from a limited set of path options, rather than being obliged, as in the current Internet, to follow a single pre-determined path. The path candidates are computed by the ISP based on its performance objectives (such as balanced link utilisations) and presented to the end-user. By restricting the extent of end-user control in the Intradomain path selection process to a few policy-compliant path options, the ISPs’ traffic engineering considerations are not compromised, and the objectives of both communication parties are fulfilled at the same time. Based on the above principle, a cooperative edge selected routing algorithm is presented to demonstrate the viability of this approach and its potential to reach win-win solutions for both communication parties (ISPs and end-users). The algorithm performance is further validated with mathematical analysis. Then, a more scalable version is proposed to increase the efficiency and decrease the memory and processing overhead. Finally, the performance and robustness of the algorithm in the face of network traffic changes is further improved with Genetic Algorithm.