CCR Papers from July 2008

Find a CCR issue:
  • Petter Holme, Josh Karlin, and Stephanie Forrest

    Modeling Internet growth is important both for understanding the current network and to predict and improve its future. To date, Internet models have typically attempted to explain a subset of the following characteristics: network structure, traffic flow, geography, and economy. In this paper we present a discrete, agent-based model, that integrates all of them. We show that the model generates networks with topologies, dynamics, and more speculatively spatial distributions that are similar to the Internet.

    Jon Crowcroft
  • Joon Ahn, Shyam Kapadia, Sundeep Pattem, Avinash Sridharan, Marco Zuniga, Jung-Hyun Jun, Chen Avin, and Bhaskar Krishnamachari

    In the last few years, several studies have analyzed the performance of flooding and random walks as querying mechanisms for unstructured wireless sensor networks. However, most of the work is theoretical in nature and while providing insights into the asymptotic behavior of these querying mechanisms, does not account for the non-idealities faced by the network in real deployments. In this paper, we propose a 3-way handshake protocol as a reliable implementation of a random walk and compare its performance with °ooding in real environments. The metrics considered are delay, reliability and transmission cost. Our initial results suggest that flooding is better suited for low-interference environments, while random walks might be a better option in networks with high interference. We also present possible research directions to improve the performance of flooding and random walks.

    Kevin Almeroth
  • Grenville Armitage, Lawrence Stewart, Michael Welzl, and James Healy

    A key requirement for IETF recognition of new TCP algorithms is having an independent, interoperable implementation. This paper describes our BSD-licensed implementation of H-TCP within FreeBSD 7.0, publicly available as a dynamically loadable kernel module. Based on our implementation experience we provide a summary description of the H-TCP algorithm to assist other groups build further interoperable implementations. Using data from our live testbed we demonstrate that our version exhibits expected H-TCP behavior, and describe a number of implementation-specific issues that influence H-TCP’s dynamic behavior. Finally, we illustrate the actual collateral impact on path latency of using H-TCP instead of NewReno. In particular we illustrate how, compared to NewReno, H-TCP’s cwnd growth strategy can cause faster fluctuations in queue sizes at, yet lower median latency through, congestion points. We believe these insights will prove valuable predictors of H-TCP’s potential impact if deployed in consumer end-hosts in addition to specialist, high-performance network environments.

    Jithendra Padye
  • Christian Henke, Carsten Schmoll, and Tanja Zseby

    A broad spectrum of network measurement applications demand passive multipoint measurements in which data from multiple observation points has to be correlated. Examples are the passive measurement of one-way delay or the observation of the path that a packet takes through a network. Nevertheless, due to high data rates and the need for fine granular measurements, the resource consumption for passive measurements can be immense. Furthermore, the resource consumption depends on the traffic in the network, which usually is highly dynamic. Packet and ow-selection methods provide a solution to reduce and control the resource consumption for passive measurements. In order to apply such techniques to multipoint measurements the selection processes need to be synchronized. Hash-based selection is a deterministic packet selection based on a hash function computed on selected parts of the packet content. This selection decision is consistent throughout the network and enables packet tracing and the measurement of delay between network nodes. Because the selection is based on deterministic function it can introduce bias which leads to wrong estimation of traffic characteristics. In this paper we define a set of quality criteria and select methods to investigate which hash function is most suitable for hash-based packet selection. We analyze 23 non-cryptographic and 2 cryptographic hash functions. Experiments are performed with real traffic traces from different networks. Based on the results we recommend 2 fast hash functions which show low bias and sample a representative subset of the population.

    Chadi Barakat
  • Frank Kelly, Gaurav Raina, and Thomas Voice

    Rate control protocols that utilise explicit feedback from routers are able to achieve fast convergence to an equilibrium which approximates processor-sharing on a single bottleneck link, and hence such protocols allow short flows to complete quickly. For a network, however, processor-sharing is not uniquely defined but corresponds with a choice of fairness criteria, and proportional fairness has a reasonable claim to be the network generalization of processor-sharing.

    In this paper, we develop a variant of RCP (rate control protocol) that achieves alpha-fairness when buffers are small, including proportional fairness as the case alpha = 1. At the level of theoretical abstraction treated, our model incorporates a general network topology, and heterogeneous propagation delays. For our variant of the RCP algorithm, we establish a simple decentralized sufficient condition for local stability.

    Darryl Veitch
  • Haldane Peterson, Soumya Sen, Jaideep Chandrashekar, Lixin Gao, Roch Guerin, and Zhi-Li Zhang

    With steady improvement in the reliability and performance of communication devices, routing instabilities now contribute to many of the remaining service degradations and interruptions in modern networks. This has led to a renewed interest in centralized routing systems that, compared to distributed routing, can provide greater control over routing decisions and better visibility of the results. One benefit of centralized control is the opportunity to readily eliminate transient routing loops, which arise frequently after network changes because of inconsistent routing states across devices. Translating this conceptual simplicity into a solution with tolerable message complexity is non-trivial. Addressing this issue is the focus of this paper. We identify when and why avoiding transient loops might require a significant number of messages in a centralized routing system, and demonstrate that this is the case under many common failure scenarios. We also establish that minimizing the number of required messages is NP-hard, and propose a greedy heuristic that we show to perform well under many conditions. The paper’s results can facilitate the deployment and evaluation of centralized architectures by leveraging their strengths without incurring unacceptable overhead.

    Dmitri Krioukov
  • Bhaskaran Raman and Kameswari Chebrolu

    This writeup presents a critique of the field of “Wireless Sensor Networks (WSNs)”. Literature in this domain falls into two main, distinct categories: (1) algorithms or protocols, and (2) application-centric system design. A striking observation is that references across these two categories are minimal, and superficial at best. We argue that this is not accidental, and is the result of three main flaws in the former category of work. Going forward, an application-driven, bottom-up approach is required for meaningful articulation and subsequent solution of any networking issues in WSNs.

  • Venkata N. Padmanabhan

    When Jim Kurose invited me to write a piece for the "recommended reading" series in CCR, I thought it would be a fun exercise and accepted the invitation right away. Little did I realize how challenging it would be to put together this list, as much because I was only allowed to pick 10 papers as because I had to steer clear of the many fine papers that had already been picked in previous lists. Rather than focusing on a single topic, I decided to pick papers from across sub-areas of networking that have left a lasting impression on me (and quite possibly on other researchers as well) because of their elegance, the insights they provide, and in many cases both of these. I hope many readers will enjoy reading these papers, if they have not already done so.

  • Tim Strayer, Mark Allman, Grenville Armitage, Steve Bellovin, Shudong Jin, and Andrew W. Moore

    The Internet Research Task Force’s (IRTF) Internet Measurement Research Group (IMRG) continued its practice of sponsoring workshops on current topics in computer network measurement with the Workshop on Application Classification and Identification (WACI) held October 3, 2007, at BBN Technologies in Cambridge, Massachusetts. There has been much general interest within the community recently in finding techniques to identify traffic without examination of the service ports used in the TCP or UDP header, as these increasingly do not accurately indicate the application generating the traffic. The workshop agenda was formed around six abstracts that were selected from an open call by the workshop organizing committee.

  • Michalis Faloutsos

    The goal of this column this time was to address major scientific issues and propose novel scientific methods for doing the same thing under different names. However, it turned out to be too complicated as it required mastery of the english alphabet. Then, I had an epiphany (greek word): Why propose something new, when you can complain about something that already exists? I think I am turning into an angry old man prematurely.

  • Jeffrey C. Mogul and Tom Anderson

    The Workshop on Organizing Workshops, Conferences, and Symposia for Computer Systems (WOWCS) was organized to “bring together conference organizers (past, present, and future) and other interested people to discuss the issues they confront.” In conjunction with WOWCS, we survey some previous publications that discuss open issues related to organizing computer systems conferences, especially concerning conduct and management of the review process. We also list some topics about which we wish WOWCS had received submissions, but did not; these could be good topics for future articles.

  • Xenofontas Dimitropoulos, M. Ángeles Serrano, and Dmitri Krioukov

    Several users of our AS relationship inference data asked us why it contained AS relationship cycles, e.g., cases where AS A is a provider of AS B, B is a provider of C, and C is a provider of A, or other cycle types. Having been answering these questions in private communications, we have eventually decided to write down our answers here for future reference.

  • Natasha Gude, Teemu Koponen, Justin Pettit, Ben Pfaff, Martín Casado, Nick McKeown, and Scott Shenker

    As anyone who has operated a large network can attest, enterprise networks are difficult to manage. That they have remained so despite significant commercial and academic efforts suggests the need for a different network management paradigm. Here we turn to operating systems as an instructive example in taming management complexity...

Syndicate content