Network Reading Group

Netread

The Network Reading Group is a weekly forum for students and faculty to discuss current, interesting, and influential papers in the area of computer networks. At each meeting, the group will focus on one paper which the group members select. Papers with any connection to networking are fair game. The group's goal is to not only familiarize members with the current literature in the area of networks, but also to encourage members to meet others with similar interests, exchange ideas, and to stimulate new directions of research.
Snacks and refreshments are provided!

If you would like to submit a suggestion for a paper, volunteer to lead a discussion, or subscribe to the netread mailing list, please send mail to netread-request@salsa.lcs.mit.edu.

Upcoming Readings

9/27/2000	Title: Memory-Efficient State Lookups with Fast Updates
	Authors: Sandeep Sikka (Inktomi) George Varghese (UCSD)
	Netread presenter: David G. Andersen dga@lcs.mit.edu
	Download: sigcomm2000-9-3.ps.gz
	Abstract:
	Routers must do a best matching prefix lookup for every packet; solutions for Gigabit speeds are well known. As Internet link speeds move to OC-192 (10 Gbps) and higher, IP lookups must complete in tens of nanoseconds, requiring the use of on-chip or off-chip SRAM, which is limited by either expense or manufacturing process. In this paper, we propose an IP lookup scheme that can scale with memory speeds and yet provide worst-case guarantees. We show that doing so requires new algorithms and the breaking down of traditional abstraction boundaries between hardware and software. A particular focus of this paper is to have a lookup chip provide guarantees on the number of IP prefixes it can support. To do so we introduce new memory allocators that have provable worst-case memory utilization guarantees that can reach 100%; this is contrast to all standard allocators that can only guarantee 20% utilization when (for example) the requests can come in the range 1..32. An optimal version of our algorithm requires a new (but feasible) SRAM memory design that allows shifted access in addition to normal word access. This small extra feature in the memory design can double the guaranteed number of prefixes the chip can support.Our techniques generalize to other state lookups besdes prefix lookup.

10/4/2000	Title: The End of the End to End Argument?
	Author: David P. Reed
	Netread presenter: Steven Bauer bauer@mit.edu
	Download: 1. The End of End-to-End Argument?
	2. Active Networking and the End-To-End Arguments
	3. End-To-End Arguments in System Desgin
	Abstract:
	I thought we would do something a bit different for this Wednesday's meeting. A page at David Reed's web site caught my attention entitled "The End of the End-to-End Argument?" It is an interesting commentary on the direction that the internet architecture is being pushed. Another article linked off his site (by Reed , Saltzer, and Clark) "Active Networking and End-To-End Arguments" also proved to be an interesting exposition of the end-to-end argument. So I thought we could explore the following questions: 1. Is the end-to-end argument little more then a catch phrase or is it still a guiding principle of network design? 2. Are Reeds objections relevant? Do current or proposed architectures violate the end-to-end principle in important ways?

10/11/2000	Title: Energy Efficient Battery Management
	Authors:Carla-Fabiana Chiasserini (Politecnico di Torino), Ramesh Rao (University of California, San Diego)
	Netread presenter: Allen Miu aklmiu@lcs.mit.edu
	Download: http://www.ieee-infocom.org/2000/papers/89.pdf
	Abstract:
	So far we have discussed high level network design principles and memory management algorithms and problems. This next week we will be diving a bit further down and discussing energy efficiency and battery management. I think this is an interesting area of research that would serve us well to be aware of. Power concerns are of growing importance in the networking community. Abstract: A challenging aspect of mobile communications consists in exploring ways in which the available run time of the terminals can be maximized. In this paper we investigate battery management techniques that can dramatically improve the energy efficiency of radio communication devices. We consider an array of electrochemical cells connected in parallel. Through simple scheduling algorithms the discharge from each cell is properly shaped to optimize the charge recovery mechanism, without introduction any additional delay in supplying the required power. Then, a traffic management scheme, that exploits the knowledge of the cells state of charge, is implemented to achieve a further improvement in the battery performances. In this case, the discharge demand may be delayed. Results indicate that the proposed battery management techniques improve system performance no matter which parameters values are chosen to characterize the cells behavior.

11/1/2000	Title: Content-Based Addressing and Routing: A General Model and its Application
	Authors: A. Carzaniga, D. S. Rosenblum, and A. L. Wolf
	Netread presenter: Joanna Kulik jokulik@lcs.mit.edu
	Download: http://www.cs.colorado.edu/~carzanig/siena/cucs-902-00.ps.gz
	Abstract:
	The designers of communication networks are being challenged by the emergence of a new class of addressing and routing scheme referred to as content-based addressing and routing. This new approach differs from traditional unicast and multicast schemes in that it performs routing based on the data being transported in a message rather than on any specialized addressing and routing information attached to, or otherwise associated with, the message. An example of an application for content-based addressing and routing is an event notification service, which is a general-purpose facility for asynchronously and implicitly conveying information from generators of events to any and all parties expressing interest in those events. In order to implement content-based addressing and routing, we can adopt well-known and successful network architectures and protocols, provided that we understand how to map the core concepts and functionalities of content-based addressing and routing onto this established infrastructure. Toward that end, we have formulated a general, yet powerful model of addressing and routing that allows us to formalize the crucial aspects of content-based addressing and routing in a surprisingly simple manner. Furthermore, it allows us to treat traditional unicast and multicast addressing and routing uniformly as instances of this more general model. This paper presents our model and demonstrates its utility by showing its application to the design of an existing event notification service.

11/08/2000	Title: Mitigating Routing Misbehavior in Mobile Ad Hoc Networks
	Authors: Sergio Marti, Thomas Giuli, Kevin Lai and Mary Baker (Stanford University, USA) nbsp;
	Netread presenter: Doug De Coute decouto@new-york.lcs.mit.edu
	Download: http://www.research.att.com/conf/mobicom2000/papers/marti.ps
	Abstract:
	This paper describes two techniques that improve throughput in an ad hoc network in the presence of nodes that agree to forward packets but fail to do so. To mitigate this problem, we propose categorizing nodes based upon their dynamically measured behavior. We use a watchdog that identi es misbehaving nodes and a pathrater that helps routing protocols avoid these nodes. Through simulation we evaluate watchdog and pathrater using packet throughput, percentage of overhead (routing) transmissions, and the accuracy of misbehaving node detection. When used together in a network with moderate mobility, the two techniques increase throughput by 17% in the presence of 40% misbehaving nodes, while increasing the percentage of overhead transmissions from the standard routing protocol's 9% to 17%. During extreme mobility, watchdog and pathrater can increase network throughput by 27%, while increasing the overhead transmissions from the standard routing protocol's 12% to 24%.

Links

UC Berkeley's Network Reading Group
1999-2000 LCS Network Reading Group
1998-1999 LCS Network Reading Group
1997 LCS Networks Reading Group