Research Of Network Measurement And Routing Adjustment Algorithm For Internet Traffic Engineering

With the rapid growth of Internet, network performance is facing severe challenge recently. Thus traffic engineering has become a critical issue of further development of Internet. Because network transmission rate increases constantly and new applications emerge frequently, present technique of traffic engineering cannot meet the demand of optimization of high-speed network, let alone the requirement of further development of Internet. This dissertation sets the stage for solving a series of problem in traffic engineering to enhance network performance and quanlity of service. It focuses on several aspects which includes measurement of round trip time of TCP connection, large flow identification in high-speed network, and routing adjustment in backbone network. The main contributions are as follows.1) Passively measuring RTT of TCP connection is of great importance for network design, traffic engineering, optimization of P2P network, and etc. To deal with the shortcomings of present methods, this paper proposes an algorithm named CROSS to estimate RTT of TCP connection from non-sender side. CROSS acquires the correspondence between data packets and ACK packets with cross correlation function, and then it gets RTT of this TCP connection. The experiment upon PlanetLab shows that this algorithm not only precisely measures RTT in any phase of TCP connection, but also works well when RTT fluctuates greatly due to the deterioration of network condition.2) The number of large flows in Internet is small. But a great deal of traffic is composed of them. Therefore it can effectively enhance the performance of congested network that large flows are rapidly and accurately found out and the routes are adjusted. By this means a heavy cost of managing the large number of small flows is avoided. Traditional large flow identification algorithms based on sampling technique or filter structure have deficiency of low accuracy. Hence they cannot satisy the need of Internet applications. This paper presents a dual-LRU based algorithm called LRU~2 to identify and measure large flows. In the two levels of LRU, level one is for filtering small flows, and level two is for accurately counting large flows. We deduce the upper bound of statistical error for large flows at the worst case, and prove by analyzing that the algorithm has processing capacity of 10Gbps line speed. The experiment based on real dataset of Internet shows that the new algorithm has higher accuracy and practicability than old ones.3) Unbalanced distribution of Internet traffic may lead congestion. At this time, changing routes for certain traffic with great impact on congestion will improve the performance of network. This paper presents a routing adjustment algorithm for single large flow. It decreases the largest bandwidth utilization rate on one hand, and on the other hand it guarantees QoS of the flow by confining route length of the flow adjusted within some acceptable bound. The experiment based on real network topology and traffic shows that the new algorithm effectively reliveves congestion with the maximal decrease of largest bandwidth utilization rate approaching 50%. Simulation proves that the new algorithm overmatches existing algorithms for it not only meets the demand of the path length of key flow but also decreases the largest bandwidth utilization rate of network. Inaddition, the computational complexity is O(N~2 log N), which is lower than majority of presentrouting adjustment algorithms.4) Although the probability of multi-link congestion is small in Internet, it does emerge sometimes. This kind of situation is not easy to deal with, and will make difficulties to network optimization. To solve this problem, this paper proposes a key flow routing adjustment algorithm which selects next hop with probability. When more than one link is congested, this algorithm adjusts routes for several key flows simultaneously. With this method, traffic distributes much more evenly than before and network performance improves thereby. Simulation indicates that the new algorithm greatly enhances the throughput of network and makes better distribution of traffic. Besides, it guarantees QoS by confining route length as well.