Efficient Traffic Engineering With Close-to-Optimal Performance

Internet traffic has been growing steadily. Some study has shown that the traffic volume was doubling every 100 days. While ISPs can add more devices to accommodate more traffic, what's more important is to manage the traffic in an efficient way so that the same investment can maintain the same level of quality of service while carrying more traffic.;An important objective of traffic engineering (TE) is to balance the traffic to reduce congestion in the network, which can be measured by the maximum link utilization(MLU). Thus a main purpose of traffic engineering is to minimize the MLU. The optimization problem can be formulated as a linear programming problem(LP) and solved in polynomial time. But several challenges exist with the linear programming approach: (1). It's time consuming to solve it. Depending on the problem size and the hardware platform, the LP problem may take hours to solve; (2). It needs a complete traffic matrix as an input, which is resource consuming to collect; (3) It needs global network status; (4). It has to be performed in a centralized way. These problems make it impractical to deploy LP solutions in real networks.;In this dissertation, we propose a new on-line traffic engineering scheme, TEA, for the MPLS framework. TEA targets at minimizing maximum link utilization(MLU) and adapting to traffic dynamics. To make it more efficient, we propose an algorithm to infer unknown link state to avoid global network probing and a scheme (named RLS) to select the largest flows in a network to avoid reporting.;TEA adapts to abrupt changes in the network traffic load by efficiently balancing the load on network links. As opposed to existing Traffic Engineering (TE) techniques, TEA's reaction to changing traffic loads only disrupts (reroutes) the minimal set of flows in order to bring the network load to a balance and converges in a small number of steps to a close-to- optimal traffic distribution on the network links. Experimental results, on both synthetic and real topologies, reveal that TEA is responsive to traffic surges, results in an optimal distribution of the network traffic on most of the investigated topologies, while rerouting less than 5% of the network flows.;To avoid global network probing, we propose a scheme to infer link utilization without probing the network. The scheme infers unknown link utilization from a set of known links so that missing network status information can be recovered and network management overhead can be reduced. The performance is compared with existing interpolation methods. Our experiments show that the inference algorithm can achieve a much higher correlation coefficient with an absolute error around a few percent.;To avoid flow selecting and reporting at core routers, we propose RLS, an efficient method to identify the largest flows in a network. Elephant-mice is a well known phenomena in the Internet, it's important to locate the largest flows for various applications including traffic engineering and network management. Our method can identify the top flows efficiently using one snapshot of SNMP link data without measuring the whole traffic matrix. It combines existing linear programming approach with SNMP link data. We test the method using real topologies. The results show that RLS can accurately identify most of the largest flows over all topologies.;In this dissertation, we describe each component. (1). we describe the main TEA approach, which includes a novel traffic allocation algorithm (named BALANCE) to distribute traffic to a given set of paths. BALANCE can distribute traffic to minimize the MLU for each ingress-egress(IE) pair; It's executed by each ingress node in a distributed way; (2). We describe the link utilization inference algorithm which can guess the LU of non-bottleneck links using information from bottlenecks; (3)We describe RLS, which identifies the largest flows in a network.;TEA is efficient in that: (1). The BALANCE algorithm only needs bottleneck links information and traffic vector; (2). Global network probing can be avoided by using the inference algorithm to collect LU information; (3). Large flows can be identified within one snapshot of link data.