Schedule for the Spring 2009
Unless otherwise noted *, seminars are held on Mondays from 4:00PM to 5:30PM in the Graduate Lounge (CS Research Lab)

The advent of virtualization and cloud computing technologies necessitates the development of effective mechanisms for the estimation and reservation of resources needed by content providers to deliver large numbers of video-on-demand (VOD) streams through the cloud. Unfortunately, capacity planning for the QoS-constrained delivery of a large number of VOD streams is inherently difficult as VBR encoding schemes exhibit significant bandwidth variability. In this paper, we present a novel resource management scheme to make such allocation decisions using a mixture of per-stream reservations and an aggregate reservation, shared across all streams to accommodate peak demands. The shared reservation provides capacity slack that enables statistical multiplexing of peak rates, while assuring analytically bounded frame-drop probabilities, which can be adjusted by trading off buffer space (and consequently delay) and bandwidth. Our two-tiered bandwidth allocation scheme enables the delivery of any set of streams with less bandwidth (or equivalently with higher link utilization) than state-of-the-art deterministic smoothing approaches. The algorithm underlying our proposed framework uses three per-stream parameters and is linear in the number of servers, making it particularly well suited for use in an on-line setting. We present results from extensive trace-driven simulations, which confirm the efficiency of our scheme especially for small buffer sizes and delay bounds, and which underscore the significant realizable bandwidth savings, typically yielding losses that are an order of magnitude or more below our analytically derived bounds.
[PDF]

IP prefix hijacking remains a major threat to the security of the Internet routing system due to a lack of authoritative prefix ownership information. Despite many efforts in designing IP prefix hijack detection schemes, no existing design can satisfy all the critical requirements of a truly effective system: real-time, accurate, light-weight, easily and incrementally deployable, as well as robust in victim notification. In this paper, we present a novel approach that fulfills all these goals by monitoring network reachability from key external transit networks to one's own network through lightweight prefix-owner-based active probing. Using the prefix-owner's view of reachability, our detection system, iSPY, can differentiate between IP prefix hijacking and network failures based on the observation that hijacking is likely to result in topologically more diverse polluted networks and unreachability. Through detailed simulations of Internet routing, 25-day deployment in 88 ASes (108 prefixes), and experiments with hijacking events of our own prefix from multiple locations, we demonstrate that iSPY is accurate with false negative ratio below 0.45% and false positive ratio below 0.17%. Furthermore, iSPY is truly real-time; it can detect hijacking events within a few minutes.
[PDF]

The Domain Name System (DNS) is a one of the most widely used services in the Internet. In this talk, we consider the question of how DNS traffic monitoring can provide an important and useful perspective on network traffic in an enterprise. We approach this problem by considering three classes of DNS traffic: canonical (i.e., RFC-intended behaviors), overloaded (e.g., black-list services), and unwanted (i.e., queries that will never succeed). We describe a context-aware clustering methodology that is applied to DNS query-responses to generate the desired aggregates. Our method enables the analysis to be scaled to expose the desired level of detail of each traffic type, and to expose their time varying characteristics. We implement our method in a tool we call TreeTop, which can be used to analyze and visualize DNS traffic in real-time. We demonstrate the capabilities of our methodology and the utility of TreeTop using a set of DNS traces that we collected from our campus network over a period of three months. Our evaluation highlights both the coarse and fine level of detail that can be revealed by our method. Finally, we show how DNS analysis can be coupled with general network traffic monitoring to provide a useful perspective for network management and operations.
[PDF]

This seminar will present a set of preliminary results of an early work that models packet filtering programs through a Finite-State Automata. The presented FSA-based packet filtering technique focuses on safety by ensuring program termination and bounds checking without the need for any additional middleware. In other words, safety is guaranteed by construction and no virtual machines are required for safe filtering execution. This technique enables the generation of a large class of stateless filters that are able to process many common protocol formats and complex protocol encapsulation relationships, extracted from a NetPDL protocol database. Under the simplified computational model employed filter composition can performed simply yet efficiently, enabling optimizations that traditionally require extensive data-flow analysis and complex algorithms. Experimental results show that FSA-based filters perform at the same level as other filters compiled with modern JIT approaches and that the impact of run-time safety checks is extremely low.

We propose an embedding and routing scheme for arbitrary network connectivity graphs, based on greedy routing and utilizing virtual node coordinates. In dynamic multihop packet-switching communication networks, routing elements can join or leave during network operation or exhibit intermittent failures. We present an algorithm for online greedy graph embedding in the hyperbolic plane that enables incremental embedding of network nodes as they join the network, without disturbing the global embedding. Even a single link or node removal may invalidate the greedy routing success guarantees in network embeddings based on an embedded spanning tree sub- graph. As an alternative to frequent reembedding of temporally dynamic network graphs in order to retain the greedy embedding property, we propose a simple but robust generalization of greedy distance routing called Gravity–Pressure (GP) routing. Our rout- ing method always succeeds in finding a route to the destination provided that a path exists, even if a significant fraction of links or nodes is removed subsequent to the embedding. GP routing does not require precomputation or maintenance of special spanning subgraphs and, as demonstrated by our numerical evaluation, is particularly suitable for operation in tandem with our proposed algorithm for online graph embedding.
[PDF]

In this talk I will present our in-progress work on a new economic-based model for AS topology generation. Compared to traditional mathematical models, economic-based models reveal more practical situations during the formation and evolution of the network. Based on observations from publicly available facts, we designed a new economic-based AS topology generation model. It incorporates some recent results from the network community and reveals more constraints in reality compared to existing models. In our model, each AS selfishly optimizes its own utility, and its optimized decision has influence over the whole network and thus all ASs. We model the optimization problem for each AS, devise mechanism to solve the problem and discuss the properties of generated topologies from different parameter settings.

As we enter an era of ubiquitous computing, theoreticians are faced with a new scenario for distributed computation: large numbers of small, heterogeneous, wireless devices competing to use the same unlicensed bands of the radio spectrum. The resulting conflicts ensure that unpredictable (sometimes even adversarial) interference is endemic throughout these bands. Traditional radio network models -- which typically assume a single predictable communication frequency used only by devices running the same algorithm -- do not adequately capture this reality. This begs the question: can theoreticians effectively model and prove useful bounds in this chaotic setting? In this talk, I will propose the answer is "yes." Specifically, I will describe recent research in which my collaborators and I model an unlicensed band by incarnating the diversity of different interference behavior in an abstract adversary. This allows us to prove strong bounds that remain applicable to real world disrupted radio channels. As a case study, I will discuss the problem of ad hoc leader election, which requires the safe election of a single leader among an unknown number of devices, activated at unknown times on a radio band suffering from unpredictable interference. I will conclude by outlining some of the useful open problems motivated by this research direction.

The InetDim project at Cornell aims at developing an algorithmic and geometric framework for exploring properties of real networks. A rigorous understanding of such properties can potentially guide the design of effective large scale distributed systems. In this talk, we present the partial results of our current investigation, which is concerned with the characterization of the dimensionality properties of the Internet delay space, i.e., the matrix of measured round-trip latencies between Internet hosts. Previous work on network coordinates has indicated that this matrix can be embedded, with reasonably low distortion, into a 4- to 9-dimensional Euclidean space. The application of Principal Component Analysis (PCA) reveals the same dimensionality values. Our work addresses the following questions: to what extent is the dimensionality an intrinsic property of the delay space, defined without reference to a host metric such as Euclidean space? Is the intrinsic dimensionality of the Internet delay space approximately equal to the dimension determined using embedding techniques or PCA? If not, what explains the discrepancy? What properties of the network contribute to its overall dimensionality? Is the Internet delay space dimensionality homogeneous or it is made up of many lower-dimensional pieces? Using measured Internet latency data, we propose tools for characterizing the delay space dimensionality and demonstrate ways in which they can be employed so as to shed light on the above questions.

This is joint work with Robert Kleinberg and appeared in IMC 2008
[PDF]

Past NRG schedules

• Fall'08 Schedule
• Spring'08 Schedule
• Fall'07 Schedule
• Fall'06 Schedule
• Spring'06 Schedule
• Fall'05 Schedule
• Summer'05 Schedule
• Spring'05 Schedule
• Fall'04 Schedule
• Summer'04 Schedule
• Spring'04 Schedule
• Fall'03 Schedule
• Spring'03 Schedule
• Fall'02 Schedule
• Summer'02 Schedule