graphicHomeAdvance ProgramAward Anniversary EventCall for PapersConference CommitteeLocal InformationPaper SubmissionProgram committeeRegistrationStudent Travel AwardsTutorialgraphic Sigcomm logoSigcomm'99


Location: The tutorials will all be held at the Harvard University Science Center. See this map for the location of the Science Center on the Harvard campus.

Voice over IP by David Oran

High-Performance Switches and Routers: Theory and Practice by Nick McKeown and Balaji Prabakar

The Web over IP Networks: Protocols and Workloads by Balachander Krishnamurthy and Jennifer Rexford

The Technical History of the Internet by Vinton Cerf and friends

M1: Monday, 30 August, 9 a.m.­5 p.m.

Voice over IP
David R. Oran

Distinguished Engineer Cisco Systems Acton, Massachusetts, USA

This tutorial will provide a system-level understanding of how voice is carried over the IP protocol suite and how this technology can be applied to both legacy and innovative telephony applications. The tutorial will cover most aspects of VoIP systems, from endpoint audio processing, through media transport and quality of service concerns, to applications in both enterprise and carrier environments.

In particular, the tutorial will cover:

Voice processing including echo cancellation, coding, compression, and voice-quality assessment.
Transport including the relevant aspects of RTP and RTCP, jitter buffers, and error concealment.
QoS, including use of both Diffserv and Intserv approaches and how they match the different deployment scenarios.
Signaling, including the H.323, SGCP/MGCP, and SIP approaches to call processing.
Enterprise applications such as toll bypass, IP PBXs, and conferencing.
Service-provider applications, such as toll arbitrage, IP Centrex, and residential and cellular systems.

Intended Audience: There are three primary audiences: software and hardware engineers developing either IP infrastructure components or pieces of VoIP systems who need a coherent introduction to the subject and a system-level knowledge of how all the pieces fit together; network managers in enterprises, telcos, and ISPs who need to understand how carrying VoIP traffic will affect their network, and what VoIP endpoints will be attached to the network for what purposes; and strategic planners in enterprises, telcos, and ISPs who need to understand the relationship between the technology and the applications it enables, and where the pitfalls in deployment and operations may show up.

Speaker's Biography: David R. Oran is a distinguished engineer at Cisco Systems, where he works on VoIP and other packet telephony systems as part of the system architecture team. He also serves on the Internet Engineering Steering Group as co-area director for routing and is a member of the SIGCOMM'99 program committee. He has served on the program committee of the Hot Interconnects conference, on NSF peer review panels, and as the editor of Computer Communication Review. Under duress, he will admit that he once designed routing protocols (such as parts of IS-IS and IDRP) for a living, and that he occasionally helps design telephony signaling protocols.

M2: Monday, 30 August, 9 a.m.­5p.m.

High-Performance Switches and Routers: Theory and Practice

Nick McKeown
Balaji Prabhakar

Departments of Electrical Engineering and Computer Science
Stanford University Palo Alto, California, USA

This tutorial will describe how high-performance multigigabit and terabit switches and routers are architected, from a theoretical and practical perspective. Although different in their detailed operation, all high-performance packet switches share three common features: "where" (routing/classification/lookup) when a new packet arrives, the packet switch must decide where the packet is going next, and hence through which port(s) it will depart from the packet switch; "how" (interconnection fabric/switching) the packet switch must then deliver the packet across a backplane or through an interconnection fabric to the selected outgoing port(s); and "when" (output link scheduling) finally, the packet switch must decide when the packet departs. This tutorial will review the basic properties of packet switches and go through the three stages outlined above, describing how they are performed in LAN switches, ATM switches, and IP routers.

We will follow our classification above, starting with the background and theory of "where": fast IP routing lookups, longest-prefix matches, and multidimensional packet classification algorithms. We will discuss the early algorithms, such as PATRICIA, followed by the more recent fast lookup and classification algorithms. In the "how" section, we'll describe switch fabrics that have been used for interconnecting linecards in fast routers and switches. These will include traditional shared memory designs and their limitations, fast parallel crossbar-based switches (such as the Tiny Tera and a variety of crossbar scheduling algorithms), and multistage switching fabrics based on Clos, Banyan, and hypercube topologies. Finally, in the "when" section, we'll consider the implementation of QoS-oriented link scheduling algorithms such as WFQ/GPS, and their implementation-friendly versions such as DRR and SFQ. We will also consider the emulation of these algorithms in crossbar-based systems with a small fabric speedup.

The tutorial will conclude with some (wild) predictions about what's coming next.

Intended Audience: This tutorial is intended for architects and designers of high-performance IP routers, Ethernet switches, Frame-Relay switches, and ATM switches. It is also appropriate for advanced graduate students who are studying high-performance network systems. Attendees will require a solid understanding of IP and Ethernet (such as provided by an introductory course or textbook). A basic understanding of ATM would be useful but is not required.

Speakers' Biographies: Nick McKeown is an assistant professor of electrical engineering and computer science at Stanford University. He received a PhD from the University of California at Berkeley in 1995. From 1986 to 1989, he worked for Hewlett-Packard Labs in their network and communications research group in Bristol, England. During the spring of 1995, he worked briefly for Cisco Systems, where he helped architect the GSR 12000 router. Nick researches techniques for high-speed networks, including high-speed Internet routing and architectures for high-speed switches. More recently, he has worked on the analysis and design of cell For more information, see Tutorials scheduling algorithms, switch and buffer architectures, and lookup algorithms. Nick is currently on leave from Stanford at Abrizio Inc.

Balaji Prabhakar is an assistant professor of electrical engineering, computer science, and (by courtesy) engineering-economic systems and operations research at Stanford University. He received a PhD in electrical engineering and an MA in mathematics from UCLA in 1994. From 1995 to 1997, he was with Hewlett-Packard Labs' Basic Research Institute in the Mathematics Sciences (BRIMS) in Bristol, England. During 1997 and 1998, he was with the Electrical Engineering and Computer Science Department at MIT. Balaji's research interests are in design and analysis of high-speed networks, pricing network services, distributed algorithms, and information and probability theories.

M3: Monday, 30 August, 9 a.m.­5 p.m.

The Web over IP Networks: Protocols and Workloads
Balachander Krishnamurthy
Jennifer Rexford

AT&T Labs­Research Florham Park, New Jersey, USA

During the past few years, the World Wide Web has rapidly evolved into the Internet's dominant application, accounting for over 70% of the traffic. Consequently, the HyperText Transport Protocol, Web components (such as clients, proxies, and servers), and user access patterns have a significant impact on Internet workload characteristics. In turn, the Transmission Control Protocol, and its interaction with HTTP, plays a crucial role in Web performance. An understanding of the details of HTTP, and the role of TCP, can aid researchers and developers in improving the performance of the Web, and in using accurate workloads to evaluate the impact of potential changes to the IP protocols, TCP implementations, and network components. Additionally, with the imminent standardization of HTTP/1.1, the changes to the HTTP protocol will be examined closely to consider their impact on Web traffic and avenues for improving performance. This tutorial will briefly cover the basics of HTTP and Web components (clients, proxies, servers), and will then focus in greater depth on the differences between HTTP/1.0 and HTTP/1.1, the interaction of HTTP with TCP, the characteristics and use of Web workloads, and the interaction of Web caching and networking issues.

Intended Audience: This tutorial targets researchers and developers who are familiar with networking (IP, TCP, etc.) and are interested in understanding how the IP and TCP protocols interact with HTTP, and how these protocols impact the design of Web clients, proxies, and servers. The emphasis of this tutorial will be on protocols and their impact on Web performance and traffic patterns. The tutorial attendee will leave with a knowledge of the key differences between HTTP/1.0 and HTTP/1.1, the interaction of HTTP and TCP, and the state of the art in Web measurement and workload characterization. The tutorial does not assume prior knowledge of HTTP; a basic understanding of IP networking and the operation of TCP would be useful. Tutorial attendees will receive an annotated bibliography covering the key topics.

Speakers' Biographies: Balachander Krishnamurthy is a member of technical staff at AT&T Labs­Research in Florham Park, New Jersey. He has published several papers dealing with the HTTP protocol and Web caching. He is co-author of an Internet Draft on adding delta encoding to HTTP/1.1. He is a member of the Web Characterization Group of the World Wide Web Consortium and was invited to speak on Web caching at InterOp98.

Jennifer Rexford is a member of technical staff at AT&T Labs­Research in Florham Park, New Jersey. She is co-author of several papers on using server hints to improve Web proxy performance, and on exploiting Web traffic characteristics in networking architectures. She also works on proxy caching techniques for Web-initiated multimedia streams, and on IP traffic measurement and analysis.

T1: Tuesday, 31 August, 8:30 a.m.­3:30 p.m.

The Technical History of the Internet
Vinton G. Cerf

Senior Vice President, MCI WorldCom

Dr. Cerf will be joined by a stellar cast of original technical contributors to the history of internetworking, including Paul Baran, Bob Braden, Dave Clark, Danny Cohen, Dave Farber, Sandy Fraser, Van Jacobson, Steve Kent, Peter Kirstein, Len Kleinrock, Larry Landweber, Dave Mills, Craig Partridge, Louis Pouzin, Larry Roberts, Dave Walden, Steve Wolff, and Hubert Zimmermann.

The Internet that is everywhere today began a long, long time ago in a world without personal computers, VCRs, or cellular telephones. How did it evolve from a few radical ideas about packet switching in the early 1960s into the global Internet that dominates the communications landscape today?

The preliminary schedule for the tutorial is as follows:

0. Introduction and global context setting (8:30-8:45am) - Vint Cerf
1. Laying the foundation (8:45-9:45am) - Larry Roberts
Early thinking about packet networks. Foundational research. Baran, Fraser, Green, Kleinrock, Pouzin
2. Building early packet networks (9:45-10:45am) - Vint Cerf
Getting the ARPANET and other packet nets built and working. Roughly 1969-1980. Cohen, Kleinrock, Roberts, Walden, Zimmerman

Break - 10:45-11am

3. Creating the internet (11am-12:15pm) - Bob Braden
Development of Internet standards. Roughly 1973-1983. Cerf, Clark, Cohen, Mills

Lunch - 12:15-1:15pm

4. Fixing the internet (1:15-2:30pm) - Craig Partridge
The Internet shakedown cruise. Roughly 1980-1990. Braden, Clark, Jacobson, Kent, Mills
5. Connecting the world (2:30-3:30pm) - Larry Landweber
Reaching the many. Connecting different networks. Farber, Kirstein, Partridge, Wolff

This tutorial will present the technical history of the Internet - the evolution of thinking about the architecture and technologies of packet networks and internetworking, starting roughly with the early 1960s work on packet switching and extending to the present day. It will be told by many of the people who were there, but it will focus on the technical debates and decisions rather than on "who did what, when, and where." Did you know that experiments with packet voice in the early 1970s played a crucial role in the decision to create separate TCP and IP protocols? Or that the 1968 decision to use an error detection scheme consisting of a 24-bit parity check BCH code with retransmission for the original ARPA network was based on the "fundamental premise" that the mean time between undetected errors should be at least an order of magnitude larger than the debugging time for the network? At this tutorial, you will learn what worked, what didn't work, and what had to be fixed later and how the technical issues were confronted, avoided, redefined, argued, and ultimately resolved. This tutorial will be presented in a highly interactive, collective oral history format.

Intended Audience: Everyone who is interested in understanding the technical sources of today's Internet should attend this tutorial. Because its appeal is expected to be very broad, no other tutorials have been scheduled for Tuesday.

Speaker's Biography: Vinton G. Cerf is senior vice president of Internet Architecture and Technology for MCI WorldCom. Cerf's team of architects and engineers design advanced Internet frameworks for delivering a combination of data, information, voice, and video services for business and consumer use. Cerf is the co-designer of the TCP/IP protocol, the computer language that gave birth to the Internet and which is commonly used today. In December 1997, President Clinton presented the U.S. National Medal of Technology to Cerf and his partner, Robert E. Kahn, for founding and developing the Internet. His personal interests include fine wine, gourmet cooking, and science fiction. Cerf and his wife, Sigrid, were married in 1966 and have two sons, David and Bennett.

Advance Technical Program | Schedule At a Glance