ACM SIGCOMM'96 
ACM SIGCOMM'96
| August 26 | IPv6: The Next-Generation Internet Protocol Dr. Steve Deering | Algorithmic Techniques for Efficient Protocol Implementations Dr. George Varghese |
| August 27 | Wireless and Mobile Networking Dr. David B. Johnson | An Introduction to Internet Measurement and Modeling Vern Paxson |
A new version of the Internet's core protocol, IP, has been developed by the Internet Engineering Task Force (IETF) and is now entering the IETF Standards track. The new IP, known as IPng or IP version 6, is designed to meet the scaling requirements imposed by the explosive growth of the Internet, and to meet the demand for greater functionality at the internet layer, including strong security, automated configuration, and support for multimedia traffic. In this tutorial, the lead designer of IPng will present a detailed walkthrough of the protocol, describing what it is, why it is, and what role it is expected to play in the evolution of the Internet.
Dr. Steve Deering is a member of the research staff at Xerox PARC, engaged in research on advanced internetwork technologies, including multicast routing, mobile internetworking, scalable addressing, and support for multimedia applications over the Internet. He is co-chair of the IETF's IPng Working Group and a member of the IPng Directorate. He received his doctorate from Stanford University.
At Gigabit link speeds, a number of optimizations will be needed beyond the dramatic optimizations caused by restructuring implementations. This tutorial attempts to provide a thorough collection of efficient solutions for commonly used protocol tasks. The tutorial should be of interest to both router and end system implementors in academia and industry.
There have been a number of tutorials on efficient protocol implementation that have emphasized proper structuring techniques and methods of avoiding data touching overhead. This tutorial will overview the above techniques, but will concentrate on algorithmic techniques for efficient implementation of common protocol implementation tasks. The course will describe 15 principles for efficient network protocol implementation. These include 10 systems principles and 5 principles specially useful for network protocols. The principles will be illustrated with concrete examples and we show how existing optimizations (e.g., header prediction, active messages etc.) relate to these principles. A highlight of the course will be a set of 16 real-world problems situations where we show how to apply the principles to solve these problems. For example, one problem is that of designing a binary search lookup algorithm for wide word network addresses without examining each word on every binary search probe. Other sample problems include incrementally reading a large Web database, converting bridge hardware into a network monitor, and efficient validation of Application Device Channel buffers. The intention is to have the audience participate so that they apply the principles and arrive at the answers (some of which are subtle) themselves.
Wherever possible, we will describe quantative studies that describe performance improvements using these techniques. We will examine ideas for hardware assist including search and sorting engines, and switching architectures. The last part of the tutorial will focus on new developments and more speculative techniques. These include proposals for performance improvement that require changes to existing protocols and headers, and the promising new direction of automatically generating optimizations (e.g., header prediction) using compiler techniques.
George Varghese worked at DEC for several years in the DECNET Architecture and A/D group. With colleagues at DEC, he has been awarded 6 patents and has 4 more pending patents, many of them in the field of protocol implementation techniques. He received his Ph.D. from MIT in 1992 and was jointly awarded the Sprowls award for his thesis. Since 1992, he has been an Associate Professor at Washington University where he continues to work on his twin interests: protocol design and efficient protocol implementation. The author invented timing wheels for efficient timer implementations and compressed trie lookup methods for routers, both of which are used in a number of real systems. He received the ONR Young Investigator Award in 1996.
Mobile hosts such as laptop and palmtop computers are becoming widely available at very affordable prices, and many new wireless networking products and services are becoming available based on technologies such as spread-spectrum radio, infrared, cellular, and satellite. However, wireless networks have funda mentally different properties than typical wired networks, including higher error rates, lower bandwidths, nonuniform transmission propagation, increased usage costs, and increased susceptibility to interference and eavesdropping. Similarly, mobile hosts behave differently and have fundamentally different limitations than stationary hosts. For example, a mobile host may move and become disconnected from or change its point of connection to the network, and mobile hosts generally operate on limited battery power.
This tutorial will focus on the challenges presented by these differences and on the network protocol solutions that address them. After reviewing the important properties of wireless network transmissions, the tutorial will summarize a number of wireless networking products or services available now or under development. We will then examine support for wireless networking and mobile hosts at the data link layer, the network layer, and at the transport and higher layers. At the data link layer, we will study the transparent roaming of wireless mobile hosts among wireless LAN base stations, exemplified by the AT&T WaveLAN protocols. At the network layer, we will study support for routing of data packets to mobile hosts in a large internetwork such as the Internet. We will cover Mobile IP and CDPD as examples of protocols that support internetwork host mobility. Mobile IP is currently being developed by the IETF (Internet Engineering Task Force) as standard for mobile hosts in the Internet, and CDPD (Cellular Digital Packet Data) has been developed by a consortium of cellular telephone companies to support IP packet routing to mobile hosts over the existing AMPS cellular telephone system. We will also cover protocols used for routing within an ad hoc network of wireless mobile hosts, forming a temporary network without the aid of any established infrastructure or centralized administration. At the transport and higher layers, we will study the problems that arise in reliable transport protocols due to the use of wireless networks and mobile hosts, and will cover several proposed solutions to these problems published in the literature. We will also cover support for dynamic notification to transport and higher layer protocols and applications when the qualities of a mobile host's network connection changes as it moves from one location to another, including possible changes from one type of wireless network product or service to another.
David B. Johnson is an Assistant Professor in the School of Computer Science at Carnegie Mellon University. He also holds a courtesy appointment as an Assistant Professor in the Electrical and Computer Engineering Department at Carnegie Mellon, and is a member of Carnegie Mellon's Information Networking Institute. His research interests include network protocols, distributed systems, and operating systems. Prior to joining the faculty at Carnegie Mellon in 1992, he was on the faculty at Rice University for three years as a Research Scientist and Lecturer in the Computer Science Department. He holds a B.A. in computer science and mathematical sciences, an M.S. in computer science, and a Ph.D. in computer science, all from Rice University.
At Carnegie Mellon, Professor Johnson is currently leading the Monarch Project, which is developing networking protocols and protocol interfaces to allow truly seamless wireless and mobile host networking. Related to this research, he has worked actively within the Mobile IP Working Group of the Internet Engineering Task Force (IETF) for the past three years and is one of the principal designers of the current IETF Mobile IP protocol. Professor Johnson is a member of the Editorial Board of the new ACM/Baltzer journal on Mobile Networks and Nomadic Applications (NOMAD), and is a member of the IEEE Computer Society, IEEE Communications Society, ACM, USENIX, Sigma Xi, and the Internet Society.
Considering the Internet's pervasiveness, much less is known about its behavior than one might expect. The two main reasons for the lack of knowledge are the difficulty of making accurate, meaningful measurements and the dearth of realistic models for analyzing and predicting its behavior. Both of these areas have seen progress in recent years.
In this tutorial we'll look at a wide range of Internet measurement and modeling issues. We set the stage with a discussion of what makes Internet measurement exceptionally hard; the tools available for taking raw measurements; common measurement errors to avoid; and basic techniques from the theory of probability and stochastic processes. Next we survey the state of the art -- what's known about today's Internet traffic and how we know it.
In the past three years, network modeling has undergone a paradigm shift away from Poisson modeling, in which traffic correlations are assumed to be minor, and towards "self-similar" or "fractal" modeling, in which large-scale traffic correlations play a major role. This shift has been fundamentally driven by traffic measurement studies. We'll discuss these studies, along with techniques for assessing the presence and strength of fractal correlations; explanations for what causes the fractal structure; techniques for synthesizing fractal traffic (and common pitfalls in doing so); and the implications of fractal traffic for network performance.
We finish with a case study: how to measure network throughput, including the numerous, subtle errors that are unforunately easy to make.
Vern Paxson is a staff scientist with the Lawrence Berkeley National Laboratory's Network Research Group and a doctoral candidate at the University of California, Berkeley. He has published a number of Internet measurement studies and given talks on the subject at SIGCOMM, SIGMETRICS, IETF, INET, NANOG, INFORMS, and NLUUG conferences, as well as serving on the program committee for the 1996 NSF Workshop on Internet Statistics, Measurement, and Analysis. He is cofounder and moderator of the Internet Traffic Archive, a repository for Internet traffic traces and analysis software. Reach him at: vern@ee.lbl.gov
return to ACM SIGCOMM Homepage
return to ACM
last updated 4/26/1996