Novel Algorithms to Improve Internet Traffic Distribution Management

This dissertation, "Novel Algorithms to Improve Internet Traffic Distribution Management" by Tat-wing, Chim, 詹達榮, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Abstract of thesis entitled NOVEL ALGORITHMS TO IMPROVE NOVEL ALGORITHMS TO IMPROVE INTERNET TRAFFIC DISTRIBUTION MANAGEMENT INTERNET TRAFFIC DISTRIBUTION MANAGEMENT submitted by Chim Tat Wing Chim Tat Wing for the Degree of Master of Philosophy at The University of Hong Kong in October 2004 The aim of traffic engineering is to reduce congestion hotspots and improve resource utilization across a network. For an Internet Service Provider (ISP), successful traffic engineering depends on the effective management of traffic distribution. This study proposes original algorithms for traffic splitting and transit traffic route configuration to improve Internet traffic distribution management. For traffic splitting, we focus on splitting traffic over multiple equal-cost-multi-paths (ECMPs). Based on the load sharing statistics collected, some active flows are selectively reassigned from over-utilized to under-utilized paths. The reassignment process is managed in such a way that the packet out-of-order problem is minimized. Transit traffic route configuration aims at managing transit traffic flows inside an autonomous system (AS). Three original route configuration algorithms are designed, - ii - based on the concept of most popular prefix first. The first algorithm is a basic scheme that selects only egress edges for transit traffic coming from different neighboring ASs and going to different destination prefix networks. We show that our basic scheme can achieve the same performance as existing algorithms, but with a much lower time complexity. Our second algorithm provides the same features as the basic algorithm, but also allows the selection of ingress edges. Simulation results show that our second algorithm consumes 12% less network resources than those required by an alternative heuristic based on the concept of biggest traffic first. Our third algorithm extends the capabilities of the second algorithm by allowing traffic to follow non-shortest paths. This greatly helps to balance the traffic load inside the local AS. We also show that all three route configuration algorithms can be easily extended to networks involving an external cost matrix such as hop count to destination prefix. (280 words) - iii - DOI: 10.5353/th_b2979832 Subjects: Routers (Computer networks) Telecommunication - Traffic Computer algorithms