Theory and Applications of Oblivious Routing

As new networking applications rapidly arise to support the growing needs of various communication services, the traffic patterns in networks have become more and more difficult to predict. It is therefore important for the routing infrastructure to be reliable and robust to accommodate unpredictable traffic patterns and guarantee the Quality of Service (QoS). Conventional routing schemes, however, require accurate traffic matrix knowledge to achieve good performance. But real traffic patterns are difficult to predict and as a result, can differ from the traffic matrix assumed in the planning phase. This makes it difficult to design a reliable routing scheme and provide QoS guarantees. Therefore, developing a routing scheme that can handle unpredictable traffic patterns has become a critical task.;This thesis addresses the above mentioned problem by focusing on the theories and applications of oblivious routing — a routing discipline that can maintain a stable performance even when the traffic matrix changes. Through static pre-configured paths, a network with oblivious routing need not constantly re-calculate and re-deploy routing paths. The major challenge, however, lies in how to reduce the capacity cost or increase the throughput of such a network. Optimization problems are formulated and solved for this purpose in unicast networks. The main contribution of this thesis can be grouped in two parts, one is related to the theories and the other related to the applications of oblivious routing.;On the theory side, we focus on multicast networks and discrete-bandwidth networks. For multicast networks, we show that network coding can be used to achieve oblivious routing with high throughput. We prove that the optimal paths between a source-destination pair in a unicast network are also the optimal paths for the pair in a multicast network with network coding; and that a multicast network can admit the same amount of traffic as a unicast network. For discrete-bandwidth networks, we present a framework for designing a discrete-bandwidth nonblocking network by combining theories from both oblivious routing and Clos switching networks. As for applications, we apply the theories developed for oblivious routing in designing new Networks-on-Chip (NoCs) architectures. We propose a new design methodology that will lead to NoCs with a predicable performance regardless of the traffic pattern produced by an application, and the network cost is minimized under the given model. We also explore ways to design oblivious-routing Wireless Mesh Networks (WMNs). We explore how to incorporate the new constraints imposed by link interferences into the throughput optimization formulation and obtain optimal routing and link scheduling.