Robust Routing Algorithm Under Uncertain Traffic Matrix

Computer networks have deep influences on everyone's everyday life. The traffic volume carried on networks is dynamic and unpredictable due to following reasons: the way people using networks are different (e g. browsing the website, downloading files in BT networks), the number of person online is different in different time segments (e g. in the midday and midnight), and the existence of network failure and network attacks. However, a predefined traffic matrix has to be known in advance in the network planning phase, where the traffic matrix represents all the demands (traffic volume) between every pair of possible source and destination nodes. Consequently, the variety and dynamic nature of the network traffic results in a dynamic or uncertain traffic matrices. This dynamic nature of traffic matrix is one of the major characteristics of IP networks today, which make the network planning a challenging work. In this thesis, the robust routing problem with uncertain traffic matrices is considered. The problem can be roughly defined as follow: given the changing region of the traffic matrix, how to configure the route to satisfy the absolute performance threshold predefined by network operators. This is a hot topic in literature in recent years.To address the robust routing problem, the second chapter proposes an algorithm, called TM Set Separating Algorithm(TSSA), which can divide the changing region of traffic matrix D according to the absolute performance threshold given by the ISPs (e.g., the maximum link utilization should not exceed a given threshold). Our algorithm can divide D into a number of subsets, and for each subset, TSSA can compute an optimal routing which can guarantee the absolute performance. In our work, two kinds of network performance metrics are considered: minimizing the total network link cost and minimizing the maximum link utilization. In the third chapter, the situation where the changing region of the traffic matrix specified by a polyhedron (infinite number of possible traffic matrices) is discussed. In the forth chapter, the TSSA algorithm is applied to a route planning problem in multi-homing networks. Finally, the fifth chapter gives summary and directions for further study.