A Versatile Scheme for Routing Highly Variable Traffic in Service Overlays and IP Backbones
📜 Abstract
The emergence of new applications on the Internet like voice-over-IP, peer-to-peer, and video-on-demand has created highly dynamic and changing traffic patterns. In order to route such traffic with Quality-of-Service (QoS) guarantees without requiring detection of traffic changes in real-time or reconfiguring the network in response to it, we consider a routing and bandwidth allocation scheme that allows preconfiguration of the network such that all traffic patterns permissible within the network’s natural ingress-egress capacity constraints can be handled in a capacity efficient manner. The scheme routes traffic in two phases. In the first phase, incoming traffic is sent from the source to a set of intermediate nodes and then, in the second phase, from the intermediate nodes to the final destination. The traffic in the first phase is distributed to the intermediate nodes in predetermined proportions that depend on the intermediate nodes. In this paper, we develop linear programming formulations and a fast combinatorial algorithm for routing under the scheme so as to maximize throughput (or, minimize maximum link utilization). We compare the throughput performance of the scheme with that of the optimal scheme among the class of all schemes that are allowed to even make the routing dependent on the traffic matrix. For our evaluations, we use actual Internet Service Provider topologies collected for the Rocketfuel project. We also bring out the versatility of the scheme in not only handling widely fluctuating traffic but also accommodating applicability to several widely differing networking scenarios, including (i) economical Virtual Private Networks (VPNs), (ii) supporting indirection in specialized service overlay models like Internet Indirection Infrastructure (i3), (iii) adding QoS guarantees to services that require routing through a network-based middlebox, and (iv) reducing IP layer transit traffic and handling extreme traffic variability in IP-over-Optical networks without dynamic reconfiguration of the optical layer. The two desirable properties of supporting indirection in specialized service overlay models and static optical layer provisioning in IP-over-Optical networks are not present in other approaches for routing variable traffic, such as direct source-destination routing along fixed paths.
✨ Summary
Overview
The paper presents a static, traffic-oblivious two-phase routing architecture for networks whose traffic matrix is unknown and may vary substantially over time. It assumes only aggregate ingress and egress bounds at each node, corresponding to the hose model. Rather than routing directly from source to final destination, traffic is first distributed from each source among a set of intermediate nodes using fixed split ratios. Each intermediate node then forwards the traffic to its final destinations.
The key observation is that the required capacity between an ingress node i and intermediate node j, together with the capacity from intermediate node i to an egress node j, can be bounded using only the aggregate ingress and egress limits and the split ratios. The resulting fixed demand is proportional to αⱼRᵢ + αᵢCⱼ, independent of the individual entries of the changing traffic matrix. This permits paths and bandwidth allocations to be configured in advance without real-time traffic measurement or reconfiguration.
The authors formulate maximum-throughput two-phase routing as linear programs. They also derive a primal-dual combinatorial algorithm, MAX-THROUGHPUT, that is an FPTAS: for any desired approximation parameter, it produces a solution within a corresponding multiplicative factor of the optimum in polynomial time. The formulation is extended to model router-to-optical-cross-connect capacity limits in IP-over-Optical networks.
The proposed architecture is applied to several settings: economical VPN provisioning, indirection-based service overlays such as i3, comprehensive middlebox routing, and IP-over-Optical backbones requiring static optical-layer provisioning. In contrast with fixed direct source-destination paths, the scheme does not require the source to know the packet’s final destination and does not require bandwidth reallocation when traffic patterns change.
Experiments using six Rocketfuel-derived ISP topologies found throughput efficiencies between 94.82% and 100% relative to an optimal traffic-dependent routing scheme. The point-to-point pipe model achieved only 3.76%–13.15% efficiency in the same comparison. Maximum-throughput solutions used between one and seven intermediate nodes. Allowing unequal intermediate-node split ratios substantially improved throughput over equal splitting, with reported gains ranging from 12.26% to 151.38% across the evaluated topologies.
Research and industry influence
The work was followed by the authors’ broader journal treatment, Oblivious Routing of Highly Variable Traffic in Service Overlays and IP Backbones, which developed the topic further in IEEE/ACM Transactions on Networking. (orcid.org) A subsequent paper, Traffic Oblivious Routing in the Hose Model, explicitly identifies two-phase routing as prior work and extends the analysis with additional polynomial-size formulations, approximation results, and evaluations against direct routing and optimal traffic-dependent schemes. (microsoft.com)
The original paper is also cited in later networking research on resilient variable-traffic routing and in patent literature concerning network provisioning, indicating influence on both algorithmic follow-up work and network-engineering applications. (citeseerx.ist.psu.edu) The available sources document continued research use of the two-phase and traffic-oblivious-routing concepts, but do not by themselves establish a specific production deployment of this exact scheme. Conference metadata and the author order are corroborated by DBLP and the INFOCOM program records. (dblp.org)