Running multiple virtual networks, customized for different performance objectives, is a promising way to support diverse applications over a shared substrate. Despite being simple, a static division of resources between virtual networks can be highly inefficient, while dynamic resource allocation runs the risk of instability. This paper uses optimization theory to show that adaptive resource allocation can be stable and can maximize the aggregate performance across the virtual networks. In the DaVinci architecture, each substrate link periodically reassigns bandwidth shares between its virtual links; while at a smaller timescale, each virtual network runs a distributed protocol that maximizes its own performance objective independently. Numerical experiments with a mix of delay-sensitive and throughput-sensitive traffic show that the bandwidth shares converge quickly to the optimal values. We demonstrate that running several custom protocols in parallel and allocating resource adaptively can be more efficient, more flexible, and easier to manage than a compromise one-size-fits-all design.

Deploying and managing wide-area network services is exceptionally challenging. Despite having servers at many locations, a service provider must rely on an underlying best-effort network; a network provider can offer services over its own customized network, but only within limited footprint. In this paper, we propose Cabernet (Connectivity Architecture for Better Network Services), a three-layer network architecture that lowers the barrier for deploying wide-area services. We introduce the connectivity layer, which uses virtual links purchased from infrastructure providers to run virtual networks with the necessary geographic footprint, reliability, and performance for the service providers. As an example, we present a cost-effective way to support IPTV delivery through wide-area IP multicast that runs on top of a reliable virtual network.

Network operators connect their backbone networks together at peering points. It is well known that the peering points are the most congested parts of the backbone network. Network operators have little incentive to provision them well, and have few tools to decide how best to route traffic over them. In this paper we propose how peering networks can be congestion free, so long as we know the total amount of traffic between them. In particular, we propose the use of valiant load-balancing (VLB), which has been previously studied for individual backbone networks. In our approach, the backbone networks do not need to use VLB internally - they simply load-balance traffic over their peering links. Our analysis shows how the load-balancing should be done, and we conclude that no other method is more efficient than VLB in achieving a congestion-free network.

Commercial backbone networks must continue to operate even when links and routers fail. Routing schemes such as OSPF, IS-IS, and MPLS reroute traffic, but they cannot guarantee that the resulting network will be congestion-free. As a result, backbone networks are grossly over-provisioned - sometimes running at a utilization below 10% so they can remain uncongested under failure. Yet even with such large over-provisioning, they still cannot guarantee to be uncongested, sometimes even with just a single failure. With our proposed approach, a network can be designed to tolerate an almost arbitrary number of failures, and guarantee no congestion, usually with an extremely small amount of over- provisioning. In a typical case, a 50 node network can continue to run congestion-free when any 5 links or routers fail, with only 10% over-provisioning. The key to the approach is Valiant Load-Balancing (VLB). VLB's path diversity allows it to tolerate k arbitrary failures in an N node network, with over-provisioning ratio of approximately k/N.

Peer-assisted streaming is a promising way for service providers to offer high-quality IPTV to consumers at reasonable cost. In peer-assisted streaming, the peers exchange video chunks with one another, and receive additional data from the central server as needed. In this paper, we analyze how to provision resources for the streaming system, in terms of the server capacity, the video quality, and the depth of the distribution trees that deliver the content. We derive the performance bounds for minimum server load, maximum streaming rate, and minimum tree depth under different peer selection constraints. Furthermore, we show that our performance bounds are actually tight, by presenting algorithms for constructing trees that achieve our bounds.

It is very hard to design a network with performance guarantees, partly because it is hard to estimate the future traffic matrix. With no knowledge of the traffic matrix, one can use the valiant load-balancing (VLB) architecture which can support any traffic satisfying the node capacity constraints. To interconnect N nodes of capacity r, the VLB architecture requires a logical full mesh of link capacity c = 2r/N. Uniform load-balancing can guarantee throughput, but is not necessary if the traffic matrix is known, in which case the amount of load-balancing can be reduced. In this paper we study adaptive load-balancing in two cases: when only local traffic information is known to a node, and when the network traffic matrix is known. We give linear programming formulations to maximize directly routed traffic in both cases, so as to reduce the average hop count of packets. In the case when the traffic matrix is known, we show that direct routing is not always feasible with c = 2r/N, but c = 3r/N sufficient