Traffic engineering in multi-service networks: routing, flow control and provisioning perspectives

A possible evolution for current telecommunication networks is towards an architecture which is increasingly connection oriented or based on virtual overlays, e.g., MPLS, as a means to support multiple service types and/or customers. At the same time such networks would continue support large amounts of traffic based on best effort service paradigm currently used in TCP/IP networks. This thesis investigates several aspects in the design and operation of such networks. As technologies continue increasing the capacity of network resources to meet increasing traffic loads the number of users contending for a given congested resource is likely to grow. When such sharing is mediated by a best effort paradigm based on TCP, one might ask whether the effectiveness of the underlying mechanisms will scale. In this thesis we begin by assessing the scalability of active queue management combined with flow control mechanisms for higher capacity links and larger numbers of ongoing flows. We propose and evaluate a simple algorithm for congestion avoidance which doesn’t require that the number of connections be known (or estimated) but exhibits robust performance even when the number of contending flows varies over a wide range. This provides a promising avenue for achieving good performance over a wide range of systems. The ability to perform a flexible routing of traffic loads across network resources is a key to enable providers to support a wide range of typically time varying loads. Nevertheless due to possible instabilities and unpredictability, operators have for the most part been unwilling to use dynamic routing mechanisms that adapt to changing loads on the fly. Instead they have opted to assign fixed administrative weights to links, and have traffic routed based on simple shortest path routing algorithms. In this thesis we consider how to set those weights given a priori information on the traffic loads. This corresponds to solving an inverse problem: determine a set of fixed weights for network links such that shortest path routing of traffic gives a good flow distribution across the network. When the traffic being routed includes connection oriented services, a good distribution of load over the network, must consider both bandwidth and connection processing and maintenance resources. Indeed connection oriented services typically require network resources to process signaling messages for setup and tear down, as well as periodic signaling for maintenance purposes. We propose and evaluate an approach to solving this inverse problem when the objective is to balance loads across both bandwidth and connection signaling resources in the network. One way providers can deal with scalability issues associated with supporting multiple service classes or customer types is to setup overlay networks over a common infrastructure. The last question we address in this thesis is associated with routing and provisioning virtual private networks (VPNs) when only a limited characterization of the traffic demands is available or desirable. Specifically we focus on the ‘hose model’ where only an aggregate characterization/constraints on traffic entering and leaving a collection of endpoints is available. To this end we devise an approach to routing and provisioning VPNs so as to exploit spatio-temporal multiplexing gains to minimize provisioning cost. We study the same questions when the provider’s objective is to maximize the lifetime of the routing decisions and/or capacity to carry new VPN requests rather than minimizing per VPN costs.