SMARTech Collection: School of Computer Science Technical Reports

Life (and routing) on the Wireless Manifold

Sun, 29 Oct 2006 22:58:59 GMT

Title: Life (and routing) on the Wireless Manifold

Authors: Kanade, Varun; Vempala, Santosh

Abstract: We present the wireless manifold, a 2-dimensional surface in 3-dimensional space with the property that geodesic distances accurately capture wireless signal strengths. A compact representation of the manifold can be reconstructed from a sparse set of signal measurements. The manifold distance suggests a simple routing algorithm that avoids obstacles, naturally handles mobile nodes without explicitly maintaining the connectivity graph and is more efficient compared to using Euclidean distance as measured by success rate, routing load and failure tolerance. Placing sensors to cover the manifold is more effective than covering the underlying physical space.

Building a Better Mousetrap

Sun, 29 Oct 2006 22:58:59 GMT

Title: Building a Better Mousetrap

Authors: Ramachandran, Anirudh; Seetharaman, Srinivasan; Feamster, Nick; Vazirani, Vijay

Abstract: Routers in the network core are unable to maintain detailed statistics for every packet; thus, traffic statistics are often based on packet sampling, which reduces accuracy. Because tracking large ("heavy-hitter") traffic flows is important both for pricing and for traffic engineering, much attention has focused on maintaining accurate statistics for such flows, often at the expense of small-volume flows. Eradicating these smaller flows makes it difficult to observe communication structure, which is sometimes more important than maintaining statistics about flow sizes. This paper presents FlexSample, a sampling framework that allows network operators to get the best of both worlds: For a fixed sampling budget, FlexSample can capture significantly more small-volume flows for only a small increase in relative error of large traffic flows. FlexSample uses a fast, lightweight counter array that provides a coarse estimate of the size ("class") of each traffic flow; a router then can sample at different rates according to the class of the traffic using any existing sampling strategy. Given a fixed sampling rate and a target fraction of sampled packets to allocate across traffic classes, FlexSample computes packet sampling rates for each class that achieve these allocations online. Through analysis and trace-based experiments, we find that FlexSample captures at least 50% more mouse flows than strategies that do not perform class-dependent packet sampling. We also show how FlexSample can be used to capture unique flows for specific applications.

Overlay Network Assignment in PlanetLab With NetFinder

Sat, 29 Oct 2005 22:58:59 GMT

Title: Overlay Network Assignment in PlanetLab With NetFinder

Authors: Zhu, Yong; Ammar, Mostafa H. (Mostafa Hamed)

Abstract: PlanetLab has been widely used in the networking community to test and deploy user-defined overlays. Serving as a meta testbed to support multiple overlay networks, PlanetLab has significantly lowered the barriers to build new overlays. However, PlanetLab users always face the problem of selecting a set of nodes and interconnecting them to form the desired overlay network. Unfortunately, such a task is usually carried out manually by individual users and sometimes in an ad-hoc manner. In this paper, we develop NetFinder, an automatic overlay network configuration tool to efficiently allocate PlanetLab resources to individual overlays. NetFinder continuously monitors the resource utilization of PlanetLab and accepts a user-defined overlay topology as input and selects the set of PlanetLab nodes and their interconnection for the user overlay. Experimental results indicate that overlay networks constructed by NetFinder have more stable and significantly higher bandwidth than alternative schemes and near optimal available CPU.

How to Lease the Internet in Your Spare Time

Sat, 29 Oct 2005 22:58:59 GMT

Title: How to Lease the Internet in Your Spare Time

Authors: Feamster, Nick; Gao, Lixin; Rexford, Jennifer

Abstract: Today's Internet Service Providers (ISPs) serve two roles: managing their network infrastructure and providing (arguably limited) services to end users. We argue that coupling these roles impedes the deployment of new protocols and architectures. Instead, the future Internet should support two separate entities: infrastructure providers (who manage the physical infrastructure) and service providers (who deploy network protocols and offer end-to-end services). We present a high-level design for Cabo, an architecture that enables this separation, and we describe challenges associated with realizing this architecture.