Robust Routing with Unknown Traffic Matrices

Abstract

In this paper, we present an algorithm for intra-domain traffic engineering. We assume that the traffic matrix, which specifies traffic load between every source-destination pair in the network, is unknown and varies with time, but that always lies inside an explicitly defined region. Our goal is to compute a fixed robust routing with best worst case performance for all traffic matrices inside the bounding region. We formulate this problem as a semi-infinite programming problem. Then, we focus on a special case with practical merits, where (1) the traffic matrix region is assumed to be a polytope specified by a finite set of linear inequalities, and (2) our objective is to find the routing that minimizes the maximum link utilization. Under these assumptions, the problem can be formulated as a polynomial size linear programming (LP) problem with finite number of constraints. We further consider two specific set of constraints for the traffic matrix region. The first set is based on the hose model and limits the total traffic rate of network point of presence (PoP) nodes. The second set is based on the pipe model and limits the traffic between source-destination pairs. We study the effectiveness of each set of constraints using extensive simulations.