9512.net
甜梦文库
当前位置:首页 >> >>

Contents ACM SIGCOMM Workshop on Computer Networking Curriculum Designs and Educational Cha


COMPUTER COMMUNICATION REVIEW
A Publication of ACM SIGCOMM
Volume 32, Number 5 ISSN #: 0146-4833 November, 2002

Contents
Workshop Report
ACM SIGCOMM Workshop on Computer Networking: Curriculum Designs and Educational Challenges ..............................................................................................1

Special Section: ATM: Retrospective on Systems Legacy
Section Introduction Jon Crowcroft and Derek McAuley ................................................................................................................. 11 A Retrospective View of ATM Charles Kalmanek......................................................................................................................................... 13 Rationalizing Key Design Decisions in the ATM User Plane Daniel B. Grossman...................................................................................................................................... 21 A Perspective on how ATM Lost Control Simon Crosby, Sean Rooney, Rebecca Isaacs, Herbert Bos............................................................................ 25 The Influence of ATM on Operating Systems Jonathan Smith............................................................................................................................................. 29

Technical Papers
A Taxonomy and Design Considerations for Internet Accounting Michael Koaudio, Udo Pooch......................................................................................................................... 39 Implementation Experience with MANET Routing Protocols Kwan-Wu Chin, John Judge, Aidan Williams and Roger Kermode.................................................................... 49 Efficient Micro-Mobility using Intra-Domain Multicast-based Mechanisms (M&M) Ahmed Helmy, Muhammad Jaseemuddin, Ganesha Bhaskara......................................................................... 61 Hop by Hop Routing Algorithms for Premium Traffic Jun Wang, Klara Nahrstedt............................................................................................................................ 73 Crossover Scaling Effects in Aggregated TCP Traffic with Congestion Losses Michael Liljenstam and Andy T. Ogielski......................................................................................................... 89

Newsletter Sections
SIGCOMM Award Nominations.................................................................................................................... 101 ACM and SIGCOMM Membership Application Form ..................................................................................... 102

Information for Authors
By submitting your article for distribution in this Special Interest Group publication, you hereby grant to ACM the following non-exclusive, perpetual, worldwide rights: ? ? ? ? to publish in print on condition of acceptance by the editor to digitize and post your article in the electronic version of this publication to include the article in the ACM Digital Library to allow users to copy and distribute the article for noncommercial, educational or research purposes

However, as a contributing author, you retain copyright to your article and ACM will make every effort to refer requests for commercial use directly to you. Additional information for authors is available at the CCR website: http://www.acm.org/sigcomm/ccr

Notice to Past Authors of ACM-Published Articles
ACM intends to create a complete electronic archive of all articles and/or other material previously published by ACM. If you have written a work that was previously published by ACM in any journal or conference proceedings prior to 1978, or any SIG Newsletter at any time, and you do NOT want this work to appear in the ACM Digital Library, please inform permissions@acm.org, stating the title of the work, the author(s), and where and when published.

Workshop Report:

ACM SIGCOMM Workshop on Computer Networking: Curriculum Designs and Educational Challenges
Jim Kurose1, J?rg Liebeherr2, Shawn Ostermann3, Theresa Ott-Boisseau4
1

Department of Computer Science, University of Massachusetts, Amherst, kurose@cs.umass.edu 2 Department of Computer Science, University of Virginia, jorg@cs.virginia.edu 3 Department of Computer Science, Ohio University, ostermann@cs.ohiou.edu 4 San Diego Supercomputing Center, University of San Diego, theresa@sdsc.edu

Abstract
This year’s annual ACM Sigcomm Conference featured a one-day workshop entitled "Computer Networking: Curriculum Designs and Educational Challenges." The goal of the workshop was to bring together faculty from a broad spectrum of four-year colleges and universities, industry engineers and scientists, and others with an interest in networking education to discuss curriculum design and teaching practices in the field of computer networks. Eighty-nine people participated in this first-ever workshop focused solely on the educational aspects of the networking field. Workshop activities included panels on undergraduate curricula, laboratory-based courses, and graduate curricula. This report summarizes the workshop’s presentations, discussions, and findings, as well as plans for future education-related activities.

1. Introduction
Perhaps reflecting the diverse, dynamic, and rapidly expanding set of topics within the field of computer networks itself, curricula and teaching practices in our field are also continuously in flux – with new topics, new courses, and new approaches to teaching being explored at colleges and universities around the world. Among the approaches towards networking curricula, one finds the more quantitative (electrical engineering) style of teaching networking versus a more software/algorithmic (computer science) approach, the more "hands-on" lab-based approach versus more traditional in-class lecture-based approach; the bottom-up approach towards the subject matter versus a topdown approach. New topics, such as peer-to-peer and mobile networking, and increased interest in more established topics, such as security, are further fueling changes to the content of networking courses. And yet, amidst this constant change and growth, the field of networking is arguably entering “middle age” at forty years old, with perhaps a body of “core” topics emerging that many networking educators feel should be mastered by all. The emergence of core networking material is also evidenced by the inclusion of a number of networking topics in the recent IEEE/ACM 2001 Computing Curricula report [IEEE/ACM 2001]. It is against this backdrop of continuing change and evolution, as well as the emergence of fundamental, core topics in our field, that the 2002 Sigcomm Education Workshop was held. The workshop itself consisted of three panels on undergraduate curriculum, laboratory courses, and graduate curriculum. Each panel also had a corresponding breakout session. The topics posed for discussion at the workshop were the following: ? The development of curricula for a first (undergraduate) course in networking. What are the "core" topics that should be covered in a first course? Are there are small set of approaches towards teaching such a course (e.g., a more quantitative EE-style versus a more software/algorithmic CS-style; "hands-on" versus in-class lectures; bottom-up versus top-down approaches)? What are the roles of labs and/or programming projects? Which undergraduate multi-course sequences are possible? What is the relationship of such course(s) to the recent ACM/IEEE 2001 Computing Curricula report? What materials can be shared by instructors? Laboratory courses. What approaches can be taken in developing "hands-on" laboratory-based courses at the undergraduate/graduate level? How do laboratory-based exercises relate to traditional lecture-based courses? What topics might be covered, and how should they best be covered? What software, lab materials, and experiences can be shared?

?

ACM SIGCOMM Computer Communications Review

1

Volume 32, Number 5: November 2002

?

The evolution of graduate-level curricula. A first graduate-level networking course has often been an accelerated/augmented version of an introductory-level undergraduate course, while more advanced graduate courses have often focused on a single sub-area. Several schools have recently introduced multi-course graduate-level course sequences, some within the context of networking/telecommunications MS and PhD programs. What should graduate courses in our field look like? Which courses in specific subareas are desirable, and what might their content be? Is there a set of advanced, foundational material that applies broadly across the field at the graduate level?

Sections 2, 3 and 4 of this report summarize the presentations and discussions in each of these three areas. Section 6 concludes this report with a listing of resources identified by (or prepared by) workshop participants, as well as a discussion of planned future activities. A copy of this report, a collection of 25 white papers prepared by workshop participants in advance of the workshop, a copy of presentation overheads, and additional educated-related information can be obtained from the ACM SICCOMM Education web pages at http://www.acm.org/sigcomm/education.

2. Undergraduate Curriculum
In brief opening remarks, Shawn Ostermann of Ohio University presented the goals for the first session: (i) begin a new discipline-wide discussion of undergraduate networking education; (ii) begin the formation of a task force to create a report describing existing programs and outlining different teaching models that work well; and (iii) make specific recommendations when “rough consensus” is possible.

2.1 Undergraduate Curricula: Presentations
The presentations contained a wealth of valuable information about networking in general, teaching experiences, example classes and curricula, things to try, things to avoid, and things to ponder. The value of these presentations was not just in their detail, but perhaps more importantly in the tone and direction that they helped set for the discussions that followed. The following summary addresses only the salient points of the presentations that led to the recommendations noted at the end of this section. Readers are strongly encouraged to review the presentations in detail at http://www.acm.org/sigcomm/education. Russell Clark from the Georgia Institute of Technology led off the morning with the first presentation. He presented a brief overview of Georgia Tech’s five undergraduate networking courses and then discussed the first, “Introduction to Networking,” in depth. This course is primarily a survey course and does not include a lab component. The course is offered twice a year to groups of up to 120 students at a time. The emphasis is on core concepts and best practices, reinforced with written assignments and socket programming. The presenter set the stage for later discussions with a final slide on “Challenges and Opportunities” that included: ? ? ? ? Top-down vs. bottom-up vs. neither– how should we teach networking? Theory vs. hands-on? How much programming and when? Dealing with large class sizes

Ralph Droms from Cisco Systems followed next, with the perspective of an academic researcher who recently moved from Bucknell University to Cisco Systems. The presentation focused on the experiences gained in teaching a networking course for many years and the lessons learned. Different from the program at Georgia Tech, Bucknell offers an introductory course with hands-on exercises, and involves a smaller number of students. The course includes a weekly lab component that covers topics ranging from packet tracing to implementing application protocols. The course culminates with a final project involving a large, distributed simulation. The presentation concluded with a pair of open questions that many have faced and pondered over the years: (i) how do we get students to use existing tools rather than “reinventing the wheel”; and (ii) how do we foster “problem analysis” and lead students away from their tendency toward “design by emacs”? The third presentation, by Michael Greenwald of the University of Pennsylvania, emphasized his University’s challenges in integrating a large and diverse student population that includes computer scientists, electrical engineers, and telecommunications engineers. The scope of the problem was emphasized by a listing of the university’s 15 courses in networking-related areas. Of particular interest was the discussion of identifying “who are

ACM SIGCOMM Computer Communications Review

2

Volume 32, Number 5: November 2002

our students?” when the population includes CS, EE, Business, and Liberal Arts majors. Each of the student groups has good reasons for needing to understand computer networking, but seemingly tackles the problem from a different angle. His presentation led to discussions on efficient use of classroom and instructor time in the face of these competing demands. The next presentation was by Dave Morgan of Fidelity Investments, who provided insight into the kinds of jobs and experiences that undergraduate students find after leaving the university. He is involved in hiring 5 to 10 new college graduates each year for a unit with roughly 500 IT professionals. Among the skills valued in new undergraduate hires is an ability to use common tools, and experience in working with teams. Experience at Fidelity Investments has shown that a common problem among new hires is their failure to understand and anticipate the amount of network traffic caused by the new network applications that they design. Lack of first hand measurement and monitoring experience in school is seen as contributing to the problem and led to discussions of possible laboratory exercises in class. The final presentation was by Craig Partridge from BBN and the Chair of ACM SIGCOMM. Craig Partridge emphasized the importance of having students “write code”. He stressed that requiring students to write software is the best way to get them to internalize and understand advanced concepts. It has the further benefit of helping them recognize when they do not fully understand the intricacies of a networking topic. Finally, it leaves them with a marketable skill, which he stated should always be a goal in an undergraduate course. In addition to the benefits of having students write code, he added that it carries the usual burdens of forcing the instructor to make judgments about how much one can push the students without losing large portions of the class.

2.2 Undergraduate Curricula: Breakout Session
The afternoon break-out session on undergraduate curricula continued the lively discussion begun during earlier presentations, undertaking the challenge of identifying the most important concepts that needed to be part of an undergraduate networking curriculum. There seemed to be a general consensus throughout the day that much of what a practicing expert in networking needed to understand would need to come from a graduate degree, and that programs with the expertise and critical mass to provide such a high-quality graduate degree would continue to exist only at a relatively small subset of the world’s colleges and universities. At the same time, a widely held belief was that the general concepts of computer networking are sufficiently important that they need to be presented at the undergraduate level to as wide an audience as possible. Supporting this belief is the fact that many colleges and universities now offer (or at least desire to offer) at least one undergraduate course in computer networking. These discussions led to the consideration of the following question: “If students were only to take a single undergraduate networking course, what topics should that course contain?” It was noted that the hypothetical course being considered would have three basic purposes: ? ? ? To teach students enough about computer networks and the implications of their widespread deployment that students can make intelligent choices about how they use such networks; To pique the interest of at least a few students in further studying in the area of computer networks; To lay a common foundation so that graduate programs can make reasonable assumptions about what students already know.

An alternative phrasing of the question helped sharpen the discussion to focus on what truly constitutes core material – “Inadequate coverage of which topics, if not mastered by students who are supposed to be networking-literate, would be deeply embarrassing to us?” Two additional questions were posed and also helped frame the ensuing discussion: “(i) What do students need to understand about the network to use it safely and effectively in their dayto-day activities? (ii) What basic knowledge should students have upon entering a graduate program in networking?” It was noted that the answers to these questions are likely not to be the same, but that a topic appearing in the answer to all of these questions would be an excellent candidate for being considered a “core” topic. With the question of “What would be deeply embarrassing if students did not know?” as a “prod” for identifying core topics, the breakout discussion group began the process of identifying such topics. There seemed to be rough consensus that the topics shown below in Table 1 should all be covered in an undergraduate networking course. We group the topics here by general area for clarity. The reader should not infer from this ordering that we are recommending a “bottom-up” over a “top-down” approach as both approaches have merit, as do their variations.

ACM SIGCOMM Computer Communications Review

3

Volume 32, Number 5: November 2002

Physical network basics ? Digital channels ? Errors and error detection ? Understanding of one shared media access protocol (e.g., CSMA) ? A little bit about wireless LANs ? Shannon and Nyquist limits Concepts ? Circuit switching vs. packet switching ? Framing and encapsulation Network interconnection ? Moving packets through multiple networks (routing, internetworking) ? Addressing and forwarding Protocols ? What a protocol is and how it is specified ? Reliable windowed/pipelined data transfer in the face of errors (including basics of TCP) ? Congestion control Exposure to ? Client/Server programming ? Socket programming ? Managing and configuring a remote device ? Current application protocols and how they work Recurring themes ? Security as a daily reality ? Encryption as a solution ? Elements of performance (transmission, propagation delay)

Table 1: A First Pass at Important Undergraduate Networking Topics

Workshop participants noted that the material on security was particularly important and should be a recurring theme throughout the course. The emphasis should be on “what all students need to understand about network security”, not just (or even) the theory underpinnings of security. In particular, the following topics should be addressed at appropriate points in the class: using checksums to protect data, implications of clear-text passwords, the implications of using credit cards on the web, authentication, privacy (e.g., using PGP in e-mail).

2.3 Where do we go from here?
The topics listed in Table 1 are the result of an admittedly short and time-constrained discussion at the workshop. Nonetheless, we were sufficiently encouraged with the amount of “rough consensus” that we agreed to take the next logical step. Our next goal is, therefore, to begin the evolutionary process of converting the minimal list from Table 1 into a SIGCOMM-sponsored supplement to the IEEE/ACM 2002 Computing Curriculum recommendations. Interested parties are encouraged to contact Shawn Ostermann at ostermann@cs.ohiou.edu to become involved in this process.

ACM SIGCOMM Computer Communications Review

4

Volume 32, Number 5: November 2002

3. Lab-based courses
Traditionally, computer networks courses have not provided students with hands-on access to networking equipment and software. In fact, courses that expose students to actual network environments are still mostly absent in an undergraduate curriculum. While introductory networking courses have a tendency to teach networking concepts at a relatively abstract level, lab courses emphasize how networking concepts are applied in an operational network. The basic assumption for offering a lab-based course is that hands-on lab exercises lead to a deeper understanding of networking principles. Most lab courses are offered as a second course in computer networks. Alternatively, an introductory network course can be supplemented with lab exercises. The lab panel at the workshop surveyed different approaches that can be taken in developing “hands-on” laboratorybased courses at the undergraduate and graduate level. The lab panel consisted of designers and/or instructors of labbased courses, and included Ann Burroughs (Humboldt State University), Magda El Zarki (University of California at Irvine), Doug Comer (Purdue University), Michael Williams (University of Akron), and Nick McKeown (Stanford University). The panel was chaired by J?rg Liebeherr (University of Virginia). Ann Burroughs shared her experience with setting up a network teaching lab at Humboldt State University. The Computing Science Department at Humboldt State offers two undergraduate courses: a breadth-oriented course (Telecommunications) which is a core requirement, and a depth-oriented elected course (Network Design and Implementation). Ann Burroughs’ networking lab is integrated into the Telecommunications course. The lab equipment at Humboldt State was established with an equipment donation of Cisco 7000 routers obtained through the NSF-supported Internet Teaching Lab project [CAIDA], which distributed sets of Cisco 7000 routers to over 25 educational institutions for the purpose of setting up teaching labs. Ann Burroughs discussed issues involved in integrating a lab component into an existing lecture course. Doug Comer’s Xinu lab was one of the first teaching labs for computer networks education. Established in 1984, the Xinu laboratory is used for research and instruction in operating systems and networks, and includes 20 workstations, 24 front-end workstations on Gigabit Ethernet, several back-end systems, and more than 20 network processors, as well as IP routers and switching equipment. Doug Comer gave examples of lab experiments for undergraduate and graduate students in the Xinu Lab. At the undergraduate level, lab exercises include network programming, where students build a client and server application and a concurrent web server, measurement experiments, where students compare the throughput of Ethernet hubs and switches, and protocol analysis experiments, where students study IP fragmentation and trace TCP connections. As examples of graduate-level lab exercises, students design and implement a software-based IP router with certain advanced features, such as multicast, NAT, or SNMP. Other lab exercises ask students to design and implement an IPsec box on a network processor platform, and a voice service over IP. Doug Comer discussed how a lab course fits into a networking curriculum. An undergraduate course in computer networks provides breadth and exposes students to the concepts and the terminology of networking. The outcome of such a course is that students can state the purpose and function of hardware and software components of a network and know the role of communication protocols. In addition, students learn to write programs using a computer network. A graduate curriculum in networking strives for complete mastery of the subject, that is, understanding the design and implementation of protocols, being able to build correct and efficient system components, knowing how to architect large-scale networks, and being able to discuss tradeoffs and limitations of computer networks. Doug Comer emphasized that lab courses are absolutely essential for a networking curriculum. Labs permit students to “learn by doing.” Labs also reinforce concepts that are presented in a lecture and provide a concrete understanding of details. Doug Comer pointed out that the equipment in a lab does not need to use the most recent or fastest technology, and that a lab course with old equipment should always be preferred to not offering a lab course.

ACM SIGCOMM Computer Communications Review

5

Volume 32, Number 5: November 2002

Figure 1: Open Lab Approach
_

Magda El Zarki discussed the design of a lab course with an open lab approach, where open lab refers to the fact that the lab equipment is located in a public area and that students perform lab experiments without supervision. The equipment for the open lab networking course is shown in Figure 1. It consists of four Linux PCs, four routers, and four Ethernet hubs. The PCs and routers are controlled from a single keyboard and monitor which is attached to a Keyboard-Video-Monitor (KVM) switch. The lab equipment is not connected to the Internet. An advantage of a rack-based lab is that the lab equipment can be easily duplicated. Currently, UC Irvine has five of the racks shown in Figure 1, and additional racks are being added. Using the open lab approach, an instructor can manage a lab course with 50 - 70 students with only one teaching assistant and one grader. The lab course is taught every quarter to senior graduate students and first year graduate students. In the lab course, students complete eight labs over a period of 10 weeks. The lab topics include single segment networks, static routing, routing protocols, LAN switching, TCP and UDP, multicast, NAT, DHCP, DNS, and SNMP. The lecture component of the lab course consists of one three-hour long lecture per week. Each lecture gives an overview of the topics of a specific lab and demonstrates some of the experiments on equipment that is located in the lecture room. Each lab is structured in three phases. In the first phase, the “prelab”, students read material and answer prelab questions which prepare them for the lab exercises. In the second phase, the “lab exercises”, students work on the lab equipment, following step-by-step instructions given in a lab manual. Lab experiments consist of traffic measurements with a protocol analyzer tool. In the third phase, the “postlab report“, students analyze the data that was gathered in the lab and prepare a report. Michael Williams gave a presentation on the participation of the University of Akron in the Cisco Networking Academy program. The Cisco academy is a partnership program of Cisco Systems with educational, business, government, and other organizations, that evolved from a program to support a network curriculum at high schools. Cisco academy courses are offered as a combination of hands-on lab exercises and online study programs. Colleges and universities participate in the program by providing space, purchasing equipment for lab exercises, and providing personnel for teaching and supervision. The teaching material is supplied by Cisco Systems. The Cisco academy generally offers two certification programs, the Cisco Certified Network Associate (CCNA) and the Cisco Certified Network Professional (CCNP). At the University of Akron, the CCNA and CCNP program each consist of four eight-week courses, which are designed to be completed in two semesters each. Students enroll in the courses as for any other credit course. The courses can be applied to some bachelor’s and associate degree programs at the University of Akron. In his presentation, Nick McKeown gave an overview of his network infrastructure labs. The goal of the labs is to have students design, implement, deploy and debug their own infrastructure elements, such as IP routers, Ethernet switches, and elements of their own creation. The networking labs developed by Nick McKeown have a hardware component and a software component. NetFPGA [NetFPGA] is a hardware platform, which consists of a circuit board with eight Ethernet interfaces and user-programmable FPGAs. Students use these boards to architect, design and deploy their own hardware in an operational network. For example, students implement an Ethernet switch, an

ACM SIGCOMM Computer Communications Review

6

Volume 32, Number 5: November 2002

IP router, or a firewall. The design process follows the industry standard flow. That is, students start with an implementation on a Verilog platform, followed by a simulation and verification phase, and a synthesis phase. At the end of the design process, the software is downloaded to the circuit boards and tested on a network that is connected to the campus network. A prototype of the NetFPGA platform has been developed in 2002, and classroom use is planned for 2003. The software component of Nick McKeown’s lab is called virtual router [Virtual Router]. The virtual router labs are intended for large networking classes with more than one hundred students, where it is not practical to provide each student with a dedicated computer with kernel-level access. In the virtual router lab exercises, students architect, design and deploy an IP router as a user-level system. Virtual router clients can be interconnected to form a virtual network topology for routing IP packets. The virtual router implementations have been used since 2001, and a release of the platform to other institutions is planned for summer 2003. In the breakout session, which was led by Shiv Kalyanaraman (Rensselaer Polytechnic Institute), workshop participants identified different styles of labs that are being offered at various institutions. One broad group of lab exercises focuses on network programming. Some programming exercises focus on socket programming exercises, where students build application-layer services. Other programming exercises ask students to build network components, generally involving kernel-level programming or special hardware, such as FPGAs or network processors. Another group of lab exercises focuses on configuration and measurements of networking equipment. These labs try to find a balance between teaching an understanding of networking hardware and software and vendor-specific configuration skills. There are numerous network simulation tools available that can be used in a lab course (ns-2 [NS], Opnet [Opnet], SSFnet [SSFnet] and GloMoSim [GloMoSim]). Simulation packages seem to have advantages when teaching very large classes. Recently, several emulation environments have become available that offer the opportunity to conduct lab exercises in a mixed hardware and software environment. The X-Bone [X-Bone] software can be used to deploy network-level services by tunneling IP traffic between X-bone capable systems. Some emulation platforms (Entrapid [Huang 1999], Vmware [Vmware]) can execute multiple operating system images, and can emulate a network with multiple routers and hosts on a single workstation. Emulab [Emulab] is a network emulator at the University of Utah that consists of several hundred PCs in racks that can be remotely configured. The discussions in the panel and the breakout sessions showed a broad spectrum of lab courses that are used in computer networks education. A comparison of the different approaches (programming, configuration, measurement, and simulation/emulation) made clear that each approach has a distinct set of advantages for teaching certain aspects of computer networks. The fact that most of the lab courses discussed at the workshop were introduced only recently points to a trend of faculty beginning to introduce labs into the networking curriculum. Instructors commented on the significant student interest in lab courses, and the generally overwhelmingly positive feedback. A problem with creating a new lab course is the considerable initial time commitment by instructors. Thus, the community could greatly benefit from a repository of existing computer networks lab courses that allow instructors to take advantage of earlier efforts at other institutions.

4. Graduate Curriculum
Just as schools are experiencing changes within their undergraduate networking curricula, so too are they experiencing change at the graduate level. These changes are being fueled by increased student interest in networking at both the undergraduate and graduate level, as well as by developments within the field itself. With more undergraduate students taking an introductory networking course, workshop participants noted that more students are arriving to graduate school ready to take advanced networking courses. Workshop participants also noted a marked increase in the number of graduate students interested in network-related courses. The increase in student preparedness, the increase in interest, and the ever-increasing growth in the scope of the field itself has resulted in tremendous demand for a larger and richer selection of graduate-level courses. Several schools have responded to this demand by creating MS and PhD level programs with specializations in networking and/or telecommunications. The goal of the session on the graduate curricula was to survey various schools’ approaches towards defining a graduate networking curricula. A number of questions were posed to the panel (and later discussed during the breakout session): (i) to what extent are the first graduate courses being taught an accelerated first (introductory)

ACM SIGCOMM Computer Communications Review

7

Volume 32, Number 5: November 2002

course in networking versus an advanced course that would build on a prerequisite introductory course? (ii) is there an emerging set of graduate-level “core” material, that might build on undergraduate core material, such as that listed in Table 1? (iii) to what extent do graduate level courses focus on theory versus practice, (iv) what are expectations of industry regarding graduate-level courses, and (v) what is being done at your school? The graduate curriculum panel participants were Ken Calvert (U. Kentucky), Scott Jordan (UC Irvine), Raj Yavatkar (Intel), and Ty Znati (U. Pittsburgh, and Program Director in the NSF CISE Division of Advanced Network Infrastructure and Research). The panel was chaired by Jim Kurose (University of Massachusetts). Ken Calvert began the graduate curricula panel by describing the first networking course at the graduate level at the University of Kentucky. The course is an advanced introductory course that does not assume a previous course in networking. Topics covered include many of those listed in Table 1: channels, bandwidth and coding; framing, errors and ARQ; routing; transport protocols; queueing models; congestion control and avoidance; QoS; MAC protocols; application protocols (HTTP and SMTP); digital media, and the future Internet. The course emphasizes principles – important topics that have a more-than-5-year half-life, and illustrates these principles with real-world examples. There is a significant programming component to the course. One important aspect of an introductory graduate-level course noted by Calvert (and seconded by many others at the workshop) was the varying degree of background and preparedness among incoming students. While some students have had no previous exposure to networking, other students may have already had an introduction to networking at the undergraduate level. Backgrounds even varied among those who have had previous exposure to networking – some students have had a more theoretically-oriented first course, while others have had more of a standards-based course, while yet others have had primarily a programming-oriented course. Calvert suggested that defining a topical interface between an undergraduate course, and a subsequent first graduate-level course would be a good first step in solving this problem. Scott Jordan of the University of California at Irvine (UCI) was the next panelist. He described the proposed Masters and PhD program in “Networked Systems” at UCI. The new program is a collaborative effort between the Department of Electrical and Computer Engineering, and the Department of Information and Computer Science. The program defines three core courses (Computer Networks, Computer Network Laboratory, Network Systems Seminar); five concentration areas (networks, performance, middleware, communications, and operations research), each with a number of courses; and two breadth areas (computer systems engineering, and management of technology). Ty Znati from the University of Pittsburgh, also currently a Program Director in the Advanced Networking Infrastructure and Research Division at the National Science Foundation, then described the Telecommunications Ph.D. program at the University of Pittsburgh. The degree is awarded as a Ph.D. in Information Science with a Telecommunications concentration. Like the proposed PhD program at UCI, the Pitt program clusters graduate courses into different areas: networking, communication systems, computer communications, telecommunications administration, telecommunications economics and policy, human communications, and wireless communications. The program offers a 24-credit certificate program, a 36-credit masters degree, and the PhD degree. Raj Yavatkar from Intel provided an industry perspective on graduate education. He began by noting two particular deficiencies that he often finds in incoming students: that they have little hands-on experience, and not enough of an understanding of system design and architecture. He then identified the background that he would like to see in all graduate-level students: the basics of efficient protocol design, security as a first class object, performance analysis and evaluation, and system design and architecture. Raj Yavatkar then outlined the contents of two graduate-level courses that would prepare students well for industry positions. He noted that these two courses built on an assumed undergraduate course in networking, and emphasized that one hands-on project and one simulation-oriented project were a critically important component of such courses. The Intel IXA network processor program was noted as an example of how projects have (and could be) integrated into graduate level courses. While the undergraduate breakout session was able to find a rough consensus on core topics that might be taught in a first undergraduate networking course, no such consensus was reached in the graduate curriculum discussion. The one common theme that did emerge was the recognized need to teach students advanced foundational material that “has a long shelf life” (i.e., would be useful to students for many years to come), and much of the discussion centered on what specific topics should be taught in such a course. Performance evaluation (modeling, simulation, and experimental design), a “science” of protocol design, and large-scale system building were topics that many felt should be taught in such a graduate “core” course.

ACM SIGCOMM Computer Communications Review

8

Volume 32, Number 5: November 2002

5. Conclusions
While a one-day workshop can only begin to address the many issues facing networking educators, the general consensus was that the workshop had been an extremely valuable forum for learning about what others are doing, exchanging ideas, and promoting thought-provoking discussion. A number of resources and ongoing activities have resulted from the workshop, and can be accessed via the ACM SIGCOMM Education web page (http://www.acm.org/sigcomm/education): ? A listing of networking courses is being maintained by Maurice Aburdene at http://www.eg.bucknell.edu/~aburdene/networkcourses/. In addition, a list of courses; has been maintained by the Internet Engineering Curriculum group at CAIDA: http://www.caida.org/outreach/iec/courses/; A listing of lab-related courses and resources is being maintained by Sanjay Jha at http://www.cse.unsw.edu.au/~sjha/netlab.html; A mailing list for people interested in discussing issues related to networking education: sigcomm_education@cs.umass.edu; A compendium of white papers submitted in advance of this workshop to stimulate thought and discussion; Organizational planning for a follow-up workshop.

? ? ? ?

More information about these activities can be found at http://www.acm.org/sigcomm/education. All members of the networking community are invited to become involved in these efforts.

Acknowledgements
Travel grants, awarded to selected workshop participants, were made possible with support from the Division of Advanced Networking Infrastructure and Research at the National Science Foundation, under award ANIR0226866.

References
[CAIDA] ITL – Internet Teaching Laboratories, http://www.caida.org/outreach/itl [Emulab] netlab – Based on emulab, http://www.emulab.net [GloMoSim] GloMoSim – Global Mobile Information Systems Simulation Library, http://pcl.cs.ucla.edu/projects/glomosim/ [Huang 1999] X.W. Huang, R. Sharma, and S. Keshav, The ENTRAPID Protocol Development Environment, Proc. IEEE Infocom '99, March 1999. http://www.cs.cornell.edu/skeshav/papers/entrapid.pdf [IEEE/ACM 2001] CC-2001 Task Force, Computing Curriculum (Final Draft), http://www.computer.org/education/cc2001/final [NetFPGA] The NetFPGA Project, http://klamath.stanford.edu/NetFPGA/ [NS] The Network Simulator – ns2, http://www.isi.edu/nsnam/ns/ [OPNET] OPNET homepage, http://www.opnet.com [SSFnet] The Scalable Simulation Framework, http://www.ssfnet.org [Virtual Router] The Virtual Router Project, http://klamath.stanford.edu/vr/vr.html [Vmware] The vmware Homepage, http://www.vmware.com/ [X-Bone] The X-Bone – A System for Automated Overlay Network Deployment, http://www.isi.edu/xbone

ACM SIGCOMM Computer Communications Review

9

Volume 32, Number 5: November 2002

ACM SIGCOMM Computer Communications Review

10

Volume 32, Number 5: November 2002

ATM: A Retrospective on Systems Legacy or “A technology with a fabulous future behind it?”
Jon Crowcroft & Derek McAuley
jon.crowcroft@cl.cam.ac.uk, derek.mcauley@intel.com

Abstract The following four papers were selected from submissions for a proposed workshop that was to have been held during the 2002 ACM SIGCOMM Conference. Due to time, we cancelled the event, but the papers capture some of the past, present and future lessons to be gleaned from the whole ATM experience, and we felt that these lessons should be provided with a forum.

Broadband ISDN is not a very catchy phrase; nor is Asynchronous Transfer Mode. However, networking research, development and standards groups in the last two decades of the 20th century were alive with a debate over the merits of these technologies. At the same time, the Internet grew from a research baby to a commercial adult. In some places, there was tension, in others, harmony, between the work carried out on ATM and on IP. Last year, some folks in the SIGCOMM community felt that it would be good to have a retrospective look at ATM, so that we could pull out some lessons for the future. The broad remit we felt we had was to examine the political, technical and economic pressures that bore on networking during this period of very rapid innovation and growth. The four papers here cover four aspects of ATM and we’ve chosen them to span the problems and the solutions, as well as the past and the future: The Technology Charles Kalmanek, from AT&T, describes the actual technology behind ATM, including the range of di?erent visions that di?erent networking communities had. He takes us from the early days of a uni?ed replacement for the SDH/SONET system that the telcos required, through to today’s reality of widespread use of ATM as a layer 2 technology in much of the broadband access networks (DSL) and in some ISP’s and corporate network cores where hard QoS is required. Performance Dan Grossman, from Motorola, takes a look at the performance trade-o?s inherent in the architectural technology choices of Cell Switching, and the Virtual Channel style of network service. The goals of low latency for voice, and of QoS assurance proved to have perhaps unexpected costs. Control Planes Simon Crosby, Sean Rooney, Rebecca Isaacs and Herbert Bos, from Cplane, IBM, Microsoft and LIACS respectively, examine signalling systems in the most general sense of the term. They also include an informal analysis of the business case for end-to-end ATM services versus IP. End Systems Jonathan Smith, from the University of Pennsylvania, shows how many of the ideas that ATM forced us to revisit in operating systems’ networking support have re-emerged as the performance curve gets to the point where the time to service an IP packet is similar to
ACM SIGCOMM Computer Communications Review 11 Volume 32, Number 5: November 2002

that of ATM cells in older systems. This is one of the more important technical lessons that can be generalised in the old adage: “What goes around comes around”. Between the lines you may read many things in these four contributions. We don’t want to spoil things by spelling all of them out, but the way that di?erent Fora develop standards is an important factor in the breadth of the success of those standards. An open approach has the advantages of being susceptible to close technical, but also business case analysis by the broader community. We should not neglect the role and in?uence of government funding in growing technologies too. Thus socio-economic comparisons between the 3G and ATM communities are inevitable, as are comparisons between the government research agencies’ e?ect in funding say Active Networks, Grid and Peer-To-Peer, with the 1990s funding of B-ISDN in Europe and the US. Enjoy.

ACM SIGCOMM Computer Communications Review

12

Volume 32, Number 5: November 2002

A Retrospective View of ATM
AT&T Labs Research 180 Park Avenue, Room A113 Florham Park, NJ 07932

Charles Kalmanek

crk@research.att.com

ABSTRACT

ATM was the focus of active research and significant investment in the early to mid 1990’s. This paper discusses several visions for ATM prevalent at the time, and analyzes how ATM evolved during this period. The paper also considers the implications of this history for current connection-oriented technologies, such as optical transport networks and MPLS.

there is a perception in the network research community that ATM “failed.” Indeed, when compared with the grandiose visions that many of its proponents had, ATM was not as successful as it might have been. This paper explores some of the visions for ATM that were pursued both by telecommunications service providers and the research community in the early to mid 1990’s and presents some of the technical and business issues that drove the evolution of ATM.

Keywords

ATM, transport networks, flow switching, MPLS.

2. MANY VISIONS FOR ATM

1. INTRODUCTION

Asynchronous Transfer Mode (ATM) networking had its origins as a switching and multiplexing technology suitable for the design of high capacity switches. The essential features of ATM are a fixed-length packet (called a cell), which is switched based on a virtual circuit identifier in the cell header. End-hosts request that the network set up a virtual circuit via a signaling (control) protocol that allows them to specify the desired quality of service. Quality of service per virtual circuit is provided through admission control and switch scheduling algorithms, allowing delay-constrained traffic, such as voice and circuit-emulated TDM traffic, to share a single network infrastructure with bursty data traffic. The cell size was kept small to support low delay for voice (although introducing enough delay that echo cancellation is needed.) For a period of time in the early to mid 1990’s, investment and research on ATM exploded, based on an expectation that ATM would revolutionize networking. For telecom providers, ATM promised to unify a number of disparate networks (voice, private line, data) on a single switching network. The fixed cell size fit well with designs for large self-routing switch fabrics suitable for the construction of very high-capacity switches. ATM’s proponents anticipated that ATM would be ubiquitous, and that end-to-end quality of service would enable an entirely new class of network applications to be built. The reality today is far different. ATM is used today to provide Virtual Private Network (VPN) services to businesses, consisting primarily of point-to-point virtual circuits connecting customer sites. ATM services represented a $ 2B business in 2001. ATM also provides the underpinnings of Digital Subscriber Loop (DSL) services, which are growing rapidly. In DSL access networks, ATM enables local exchange carriers to switch subscriber traffic to different Internet Service Providers. ATM is also used as the core network infrastructure for large Frame Relay networks and for some IP networks. While these uses of ATM are important and should be viewed as a mark of success for ATM technology,

Starting from a small set of initial design principles, the development of ATM technology progressed in a number of different directions, based on the business and technical visions of the companies and individuals who were driving the technology. This section summarizes several of the early visions for ATM prevalent in the research community and industry. While attempting to give a balanced overview of the work that was going on, I have no illusions that this survey is exhaustive or that is does justice to any one of these visions. However, I hope that it gives some notion of the tremendous scope that the ATM community was trying to address. One vision of ATM’s role in telecom networks was that it would provide a single multi-service network. I distinguish between two variants of this vision. One is that it would serve as a multiservice core network supporting primarily data services such as Frame Relay, IP, and ATM service, possibly with some DS1, DS3 or higher rate private line and voice services. The other is that it would eventually replace the circuit-switched TDM hierarchy and provide a next-generation transport network, supporting longterm capacity (bandwidth) management for all services. In the first instance, an ATM core network would support multiple service edges, such as frame relay, IP, ATM, and possibly private line and voice. A high level view of this architecture is shown in Figure 1, which gives an example of multiple networks, each with its own “edge” switches connected over dedicated links. Figure 2 utilizes a single core network to connect edge switches for each service. This approach optimizes link utilization through statistical multiplexing of edge-to-edge traffic over the core network. It was also understood that the introduction of hierarchy could improve the scalability of the network from a routing perspective. Rather than scaling independent networks as the number of customers grew, the networks within each region could be scaled independently, and interconnected over a core network running the ATM PNNI routing and signaling protocol. The edge-core approach also had the potential to reduce network operations expense through the consolidation of individual service networks.

ACM SIGCOMM Computer Communications Review

13

Volume 32, Number 5: November 2002

IP ATM FR

Edge Switch

IP ATM FR

management below OC-48 is done at the ATM layer. In the figure, ATM and IP layer demands are carried over an optical cross-connect (OXC) layer, which takes on the restoration function supported in the SONET layer in Figure 3. Since bandwidth management on the ATM network occurs on a slow time scale, ATM VC setup only occurs on provisioning time scales. By eliminating the hierarchical transport network architecture below OC-48, ATM promised to simplify the task of managing the transport network and to improve overall network efficiency.
IP Router

Figure 1: Multiple Edge Networks
IP ATM FR IP ATM FR Core Switch

Edge Switch

DS1 PL DS1 trunks

DCS-3/1 DS3 OC3 OC12

Edge Switch

DS3 PL

DCS-3/3 DS3

Figure 2: Edge-Core Architecture To consider ATM as a next-generation transport network, we first need to understand how transport networks are built. Transport networks have traditionally been based on a hierarchy of timedivision multiplex (TDM) switches. Figure 3 presents typical network architecture, simplified from [1]. DS1 private line or voice trunks are aggregated and/or switched in a Digital Crossconnect System with DS3 interfaces and a switching granularity of DS1, denoted as a DCS-3/1. DS3 private line or aggregated traffic demands are switched in a DCS-3/3 supporting DS3 interfaces and a switching granularity of DS3. These DS3s and other higher rate signals are carried over SONET rings1 or linear chains that provide restoration in case of link or interface failure. SONET links are transported between central offices by an Optical Transmission System (OTS). Due to the existence of multiple layers of network hierarchy, this network architecture often results in inefficient overall network utilization, for a number of reasons. One is that the partial utilization at each network layer is compounded as you go up the hierarchy. Another reason is that circuits at a given layer may end up being routed inefficiently as a result of capacity planning processes that are designed to maximize the utilization of the layer that carries them. For example, a DS1 circuit may not follow the shortest path between two central offices because it is routed over a preexisting DS3 circuit following a less efficient path. From its earliest design, ATM was intended to support virtual circuits across a wide range of rates. With the promise of ATM switches with aggregate capacities of 10’s of Gbps in the mid 1990’s growing to 100’s of Gbps by the end of the decade, network designers began to seriously consider using ATM in the transport layer, supporting multiple services and consolidating several layers of the TDM hierarchy. Figure 4 illustrates a network architecture in which all transport bandwidth
1

OC3 PL OC12 PL

SONET Ring/Chain OC48 OTS OTS

Figure 3: Traditional Transport Network
IP DS1 PL DS1 trunks DS3 PL OC3 PL OC12 PL Router OC3 OC12 ATM OC48 OXC OC48 OTS OC48

Figure 4: ATM-based Transport Network A second vision of ATM, fostered by the research community, envisioned the use of ATM as a universal end-to-end packet service [2]. ATM’s emphasis on end-to-end quality-of-service was an important part of this vision. In the end-to-end vision, desktop computers, networked appliances and large servers would all support ATM, and set up end-to-end connections with qualityof-service when needed. There was a tremendous amount of work on ATM host interfaces, low cost ATM interface chips, and ATM LAN switches. Protocol stacks were developed for end-hosts by extending the Berkeley socket layer to allow applications to directly establish ATM virtual circuits [3]. ATM’s small cell size seemed particularly well suited to managing quality-of-service in access networks, where bandwidth is scarce, such as DSL and wireless networks [4], etc. Small cells implied that links could be

While SONET ring technology does not scale very well to large networks, large SONET cross-connects were not yet available in the early to mid 1990’s.

ACM SIGCOMM Computer Communications Review

14

Volume 32, Number 5: November 2002

scheduled on a fine time scale, allowing delay-sensitive applications to be supported alongside elastic applications. There was also a significant amount of research on ATM signaling. In addition to ATM standards, ATM signaling was adapted to support connection handoff for mobile wireless devices [5]. A lightweight ATM signaling protocol was proposed in [6] which established forwarding state for a connection very efficiently, while allowing additional signaling along the slow path to establish QoS for the connection. The “open signaling” community proposed that ATM switches should support a standard low-level control protocol [25], allowing service providers to customize their ATM control plane. The research community also pursued even more radical ideas, such as deskarea networks [7], in which ATM was used as the fabric in a deskarea distributed computing environment comprising processing resources, I/O devices, and storage. As a result of the investment by the vendor community, leading edge products were available causing some enterprises to start to use ATM in their server environment, and to gear up to push ATM to the desktop. The above vision of ATM was of interest to ATM purists. At the same time, there began to be significant interest in IP flow switching concepts [8] that promised to better integrate ATM with IP. If one looks at IP traffic, a significant fraction of the “flows” are small transactions, such as DNS lookups, for which the overhead of ATM connection setup is on par with or larger than the duration of the transaction. Rather than setting up a connection for short transactions, IP flow switching proposed to setup ATM shortcut connections only for long-lived flows [9, 10], offloading slow IP routers and leveraging high-performance ATM switches. The basic idea is illustrated in Figure 5, which shows “default” connectivity via ATM permanent virtual circuits ( PVCs) using solid lines, and a shortcut connection that has been set up dynamically between two routers using a dashed line. The flow switching architecture proposed to enhance ATM switches by putting smart algorithms for detecting IP “flows” on ATM line cards. Service providers began to investigate how they could use ATM flow switching as a way of more tightly integrating the IP layer with the ATM layer than was envisioned in the architecture shown in Figure 2.

forwarding onto ATM’s connection-oriented services. MARS is based on point-to-multipoint VC’s and uses either VC meshes or multicast servers to support the IP multicast service. A Multicast Address Resolution Server maintains a mapping from IP address to a set of ATM addresses in a Logical IP Subnet (LIS), and is updated by a host in the LIS when it joins or leaves an IP multicast group. Another set of activities focused on enabling ATM to support the large embedded base of software built on bridged LANs. Initial implementations of LAN emulation on ATM were available around 1994, and the ATM Forum developed the LAN Emulation (LANE) specification [13]. LANE provides transparent support for Layer 2 Ethernet bridging services: the ATM LAN emulation protocol stack is shown in Figure 6. LANE’s primary goal was to support common end-host drivers, such as Network Driver Interface Specification (NDIS) from Microsoft, which runs over bridged LANs. The function of the LAN emulation layer was to exactly mimic the MAC layer interface of a bridged LAN, so the higher layers would think they were running over a standard Ethernet or token ring network. An ATM LAN bridge would support fragmentation of MAC frames into ATM cells, emulating all of the functions supported by LAN bridges on top of ATM and inter-working with existing bridged networks. Applications NDIS Driver LAN Emulation AAL5 ATM Phys. Layer Bridging LAN Emul. Applications NDIS Driver MAC Phys. Layer

ATM Phys. Phys.

MAC AAL5 ATM Phys. Phys.

Figure 6: LAN Emulation None of these visions of how ATM would evolve proved to be correct. The question is why?

3. HOW IT PLAYED OUT

Router Router Shortcut connection Router Router

ATM Network

Figure 5: IP Flow Switching The flow switching concepts were further developed in both the IETF and the ATM Forum. Using the Next-Hop Resolution Protocol (NHRP) [11], a router queries a Next-Hop Server to determine the ATM address of the next IP hop towards an IP destination. An alternative approach [10] utilized extensions to IP routing to carry the ATM address of the next-hop router. In addition, the Multicast Address Resolution Server (MARS) architecture [12] addressed the problem of mapping IP multicast

The vision of end-to-end ATM with quality-of-service was extremely compelling to many people. Internet service was widely seen to be unpredictable, and ATM promised a solution. The ATM Forum developed a comprehensive Traffic Management framework, supporting five classes of service: CBR, VBR-rt, VBR-nrt, ABR and UBR2. This framework developed many of the key traffic management concepts that are in common use today: traffic descriptors, shapers, policers, priority and weighted fair scheduling, as well as signaling support for connection admission control and QoS routing. CBR defines mechanisms to support delay-constrained constant bit rate traffic, while ABR supports network feedback to sources allowing them to adapt their sending rate to the max-min fair rate of the bottleneck link along the path of the connection [14, 15]. This

2

CBR = constant bit rate; VBR-rt = Variable Bit Rate (real time); VBR-nrt = Variable Bit Rate (non real time); ABR = Available Bit Rate; UBR = Unspecified Bit Rate.

ACM SIGCOMM Computer Communications Review

15

Volume 32, Number 5: November 2002

work contributed a significant number of innovations to packet networking. However, end-to-end ATM faced a deployment challenge due to the law of network externalities. Until ATM deployment reached a critical mass, end-to-end ATM QoS couldn’t be realized. Since most existing applications were based on IP, use of ATM QoS for IP applications would need to be mediated by a (non-existent) IP QoS application programming interface. Moreover, ATM deployments would bear the burden of inter-working with existing applications and hosts that had not been upgraded to ATM. Another factor limiting the realization of end-to-end QoS is that, despite the variability of Internet performance, new network technologies are often initially deployed in enterprises. Here, the application drivers for end-to-end QoS never really materialized. And in this environment, high-speed Ethernet-based LANs began to dominate the desktop thereby reducing the perceived need for ATM’s traffic management framework. Nonetheless, the momentum behind ATM deployment was strong enough that for a period of time, it seemed possible that ATM to the desktop might succeed. Economic forces worked against it, however. In the early 1990’s, an ATM host adaptor cost roughly $3K. By the mid 1990’s, this price had fallen to roughly $1K. At that time, Ethernet adaptors cost about $100. This price difference was a significant impediment to widespread adoption of ATM. We can also consider the vision of ATM as a future core data or transport network. Since ATM provides a flexible bandwidth management capability, it seemed very well suited to the role of a multi-service core network or even core transport network, replacing SONET rings with a more efficient mesh structured bandwidth management layer. Unfortunately, there were a number of factors that made it difficult to realize this vision. One factor is that growth for data services through the mid 1990’s dramatically exceeded expectations. This growth included Frame Relay, IP, ATM and private line services. When the total Frame Relay, ATM, IP and DS1 private line demands were considered, the switch capacities of commercially available ATM switches were not adequate to support the requirements of large central offices. Another issue is that each service emphasized a slightly different set of requirements, such that the union of the service requirements was difficult for vendors and service providers to cope with. For example, private line has stringent requirements on reliability and restoration capabilities, and requires ATM line card support for TDM circuit emulation; voice has requirements for high switched virtual circuit (SVC) setup rates; and ATM PVC and SVC services for data likely require high port densities and reasonable reliability, at a significantly different target for price/performance than either voice or private line. If we focus specifically on transport network evolution, switch reliability was an issue. Digital Cross-connect Systems typically are designed to meet less than 3 minutes per year of downtime: relatively immature ATM switches could not meet this requirement. One way of dealing with some of these problems would have been to select different vendors for the edge and core switch nodes. However, due to relatively slow progress on ATM signaling standards, vendor inter-operability was delayed. As a result of these considerations, service providers gave up on the idea of a single core network, and took the more conservative approach of

evolving separate IP, transport, and ATM networks. The one exception was Frame Relay networks, which evolved to run over ATM core networks since higher speed ATM interfaces and switch capacities were needed to support growing Frame Relay demand. It is also important to recognize that ATM was being standardized and deployed just as IP was beginning to pick up steam. To be successful, ATM clearly needed to provide some inherent advantages (and few disadvantages) in carrying IP traffic. To some, ATM’s high-speed and the emerging flow switching technologies seemed at the time like a winning combination. However, flow switching actually introduced uncertainty in how the IP layer would best utilize ATM. This uncertainty and the complexity of the underlying technical issues may have slowed rather than accelerated ATM deployments in large-scale data networks. Standardization in the IETF and ATM Forum’s MultiProtocol over ATM (MPOA) group [24] seemed likely to take a long time. In addition, flow switching introduced another layer of complexity into the architecture, requiring vendors to understand and be competitive in ATM switching, IP routing, and IP flow switching. To utilize flow switching effectively, service providers would need to provision IP flow detection algorithms on edge switches. Before developing software tools to do this, there needed to be strong evidence that flow switching would provide either significant cost savings or end-user performance improvements. Demonstrating cost savings in a large service provider network would depend on a combination of factors, including the ratio of router interface costs to ATM interface costs, the amount of traffic that would actually utilize shortcuts, etc. Demonstrating end-user performance improvements would depend on being able to deliver shortcut traffic with better end-toend performance (e.g., throughput, delay) than routed traffic. While this might have been possible, the improvement would have to be significant to justify a new architecture. Another issue with IP over ATM was support for IP multicast. The IP multicast community was extremely vocal about both the need for IP multicast and the difficulties of supporting it in ATM. As a result, ATM standards evolved to include support for pointto-multipoint unidirectional virtual circuits, and [12] defined a set of mechanisms to support IP layer multicast using them. An alternative multicast model using core-based trees was defined in [16]. Nonetheless, the debate about IP multicast over ATM contributed to the uncertainty about ATM, despite the fact that IP multicast has still not been widely deployed. While these issues were being played out in the marketplace, there was also significant investment in IP router technology, due to the tremendous growth in IP traffic demands. Improvements in silicon technology and algorithms for IP forwarding table lookups [17, 18] resulted in a situation where commercially available ATM switches did not offer any speed advantage over commercially available IP routers. For a multiplexing layer to make sense, it needs to offer some speed advantage over the demands that it will be carrying. In fact, router vendors began to use ATM switch technology to increase their aggregate switching capacity, and interface rates on ATM switches often lagged behind those of IP routers. It is also useful to consider the evolution of link technologies and their impact on ATM. Around 1992, when work on ATM was getting started, 100 Mbps shared FDDI rings were the fastest

ACM SIGCOMM Computer Communications Review

16

Volume 32, Number 5: November 2002

switching technology in widespread use. There was no other cost effective high-speed link technology for the LAN – Fast Ethernet was not yet available. ATM took advantage of the newly developed Fibre channel line coding chips, which promised relatively inexpensive 155 Mbps LAN links. In the WAN, ATM SONET interfaces at 155 Mbps and 622 Mbps were commonly used as the interface between backbone routers. Then, in 1994 1995 Fast Ethernet came out, and around 1997, Gigabit Ethernet appeared. In 1997, Packet over Sonet (POS) also appeared, supporting high-speed IP over HDLC over SONET without the overheads of ATM. When compared with IP router technology, ATM had a number of initial advantages: high capacity switching, high-speed links, etc., but lost advantage after advantage as IP router technologies advanced. The end result was that ATM never reached critical mass for going to the desktop, given the cost of network adaptors, network externalities and the existence of competing Ethernet technology. ATM was also not ready to support the needs of a multi-service core network or core transport network. Finally, proposals to integrate ATM and IP, such as IP flow switching, were complex and were ultimately superceded by advances in IP router design, which incorporated many of the innovations that had been developed in ATM. It is clear that ATM fell short of the technological vision that many people had. Where ATM succeeded was as a Layer 2 switching technology that is used in access/aggregation networks and as a core network for Frame Relay and native ATM services. Layer 2 VPNs consisting of point-to-point PVC’s provide high reliability connectivity services to enterprises at a lower price point than private line services. ATM is also widely deployed as part of DSL access networks. The latter application is shown in Figure 7, where traffic from a DSL Access Multiplexer is carried over ATM to an ISP. It is important to note that ATM networks today carry a significant amount of Frame Relay traffic, DSL traffic, both enterprise and carrier voice traffic, and some backbone IP traffic.

within a single ISP, is difficult. In time, MPLS may be able to support these features well, but ATM will be the technology of choice for some customers for many years to come.

4. LESSONS FOR TODAY

One natural question given this background is what lessons can be learned from ATM that might be applicable in the latest incarnations of connection-oriented technology: optical transport networks and MPLS. Large SONET cross-connects, typically with OC-48 or OC-192 ports and STS-1 switching granularity are now commercially available and are the basis of a new generation of transport infrastructure. These switches use variants of ATM’s PNNI signaling or MPLS signaling (called Generalized MPLS) protocols [19] to set up and manage connections. For the foreseeable future, SONET technology appears to be the likely basis of the transport infrastructure, perhaps augmented by the use of transparent optical switching for managing large optical bit pipes at some point in the future. For IP networks, MPLS is being touted as providing a routing and switching layer that can enable multiple types of traffic to share a common packet switched infrastructure. This sounds familiar, and it is worth understanding how MPLS is evolving in order to understand whether it will succeed where ATM failed. Like ATM, MPLS is a virtual circuit technology. In fact, MPLS has borrowed a number of the essential ideas of ATM: virtual circuit switching, fast re-route, and the notion of a single network infrastructure. However, MPLS does not attempt to solve an endto-end problem, but rather focuses on a single administrative domain and is tightly integrated with the IP forwarding paradigm. To support quality of service, MPLS reuses IP differentiated services. MPLS does not support fast/dynamic connection setup like ATM SVC’s. One key application of MPLS is support for Layer 2 and Layer 3 virtual private networks (VPNs) on an MPLS label switched core network. As with ATM, the opportunity here is to reduce network operations expense through the consolidation of individual service networks. The IETF “Martini” encapsulation [20] allows frame relay, ATM, Ethernet, and IP packets to be transported over an MPLS network. An MPLS tunnel between ingress and egress label-switched routers (LSRs) can carry packets associated with different services – the egress LSR uses the innermost label to distinguish the service to which packets are to be de-multiplexed. This approach is designed to support ATM permanent virtual circuits, although it does have some deficiencies. For example, the Martini encapsulations do not support service inter-working such as between Frame Relay and ATM. In addition, the related signaling extensions [21] were not designed to support switched virtual circuit setup. However, another approach to ATM over MPLS provisions an overlay ATM network on MPLS tunnels, and runs PNNI among the overlay network edges. This approach allows switched virtual circuits to be supported. In addition to supporting ATM, Frame Relay and Ethernet “virtual circuits,” MPLS protocols are also being developed to support Transparent (bridged) LAN service over MPLS [22]. Layer 3 VPNs are supported using extensions [23] of the IP Border Gateway Protocol (BGP) that provide support for private address spaces and virtual private IP networks on a shared MPLS core network. Given that many enterprises use private IP addressing and do not want mission-critical applications exposed

Router
DSLAM

IP network

ATM switch

DSLAM

Figure 7: ATM-based DSL Access ATM services continue to provide some technical advantages over IP services. ATM is more mature than IP in its ability to provide stringent quality of service guarantees. While IP differentiated services support class-based quality of service, IP differentiated services face a number of deployment challenges in large ISPs, including the difficulty getting good traffic data as an input to traffic engineering, and performance problems in legacy routers when quality of service features are enabled. In addition, ATM’s guaranteed bandwidth on demand, fast re-route, and OAM features are important to many large customers. None of these features has been thoroughly integrated into IP as yet. Identifying and sectionalizing problems with end-to-end service in IP, even

ACM SIGCOMM Computer Communications Review

17

Volume 32, Number 5: November 2002

to the Internet, the isolation provided by Layer 3 VPNs based on MPLS are likely to be important, and will compete with Layer 2 and IPsec-based VPN’s. Note also that the ability to run virtual private IP networks on a shared core network allows large Internet service providers to resell IP backbone network capacity. Since the cost structure of an ISP depends on economies of scale, this drives down costs. The RFC2547 approach may eventually change the way that ISPs handle Internet routing. While IP forwarding and MPLS label switching currently co-exist in core network routers, in time IP forwarding tables could essentially disappear from core routers in an MPLS enabled network – Internet default-free routes would only exist as one of the virtual routing and forwarding tables in an MPLS provider edge router. While it is impossible to predict the future, it is clear that MPLS has avoided a number of the pitfalls that plagued earlier visions for ATM. First, MPLS is not attempting to provide an end-toend solution -- it is clearly targeted at service provider core networks. As a result, MPLS doesn’t need to be ubiquitous to be successful. Second, MPLS protocols are an extension of existing IP protocols, while ATM’s control plane evolved to be quite complex, including signaling, routing, MPOA, LANE, etc – all of which were needed in addition to IP protocols. This may simplify development and deployment. Third, MPLS is riding the same technology curve as IP routers, which suggests that switch capacity will not put MPLS at a disadvantage relative to IP. There are still interesting questions about the role of MPLS in ISP networks. For example, the cost and performance tradeoffs among restoration alternatives at different layers (IP layer rerouting, MPLS fast re-route, and transport network restoration) are an active area of research. In addition, as mentioned earlier, transport networks and ATM networks are traditionally more reliable than IP networks – in part because routing problems in one ISP’s network can affect other providers. RFC2547 isolates routing in Layer 3 VPNs from Internet routing, which directly addresses this problem for VPN customers.

significant, if largely invisible, role in data networks at Layers 1.5 and 2 for some time.

6. ACKNOWLEDGMENTS

The author gratefully acknowledges the contributions of Tom Afferton, Elie Francis, Han Nguyen and K.K. Ramakrishnan, for their careful feedback on early drafts of this paper. K.K. Ramakrishnan provided the perspective on the evolution of datalink technologies and ATM.

7. REFERENCES

[1] R. D. Doverspike, S. Phillips, and J. R. Westbrook, Future
Transport Network Architectures, IEEE Communications Magazine, August 1999. Everywhere?, IEEE Network Magazine, March 1993.

[2] I. M. Leslie, D. R. McAuley, and D. L. Tennenhouse, ATM [3] R. Sharma and S. Keshav, Signaling and Operating Systems
Support for a Native ATM Applications, Proc. SIGCOMM ’94. Network using Infrared Links, Proc. MOBICOM ’95.

[4] J. Condon, et al., Rednet: A Wireless ATM Local Area [5] R. Yuan et al., A Signaling and Control Architecture for

Mobility Support in Wireless ATM Networks, Mobile Networks and Applications, Special Issue on Wireless ATM, Vol. 1, Issue 3, December 1996. Architecture for Lightweight Signaling in ATM Networks, Proc. Infocom ’98. Operating Systems Review, Vol. 25, No. 4, pp. 14-21, 1991. under IP, IEEE/ACM Transactions on Networking, Vol. 6, No. 2, April 1998. of Long-Lived Flows, Proc. SIGCOMM ’99.

[6] G. Hjalmtysson and K.K. Ramakrishnan, UNITE: An

[7] M. Hayter and D. McAuley, The Desk Area Network,

[8] P. Newman, G. Minshall, and T. Lyon, IP Switching: ATM

5. CONCLUSION
This paper surveys several of the visions for ATM explored by the networking community in the early to mid 1990’s. Many of the traffic management concepts developed in ATM have become part of networking practice, and ATM is widely used to support VPN’s, DSL access networks, and as a core networking technology for Frame Relay and some voice and IP services. Nonetheless, ATM did not succeed in revolutionizing networking. Economic factors, network externalities, the complexity of emerging standards and implementations, and the rapid development of alternative technologies were all factors which made it difficult for ATM to take over the world as many people expected. From an historical perspective, the debate between connectionoriented and connectionless networking technologies has existed since the early days of packet switching. Even with the explosive growth in IP communications over the last decade, it appears that the tension between the two technologies is alive and well. Connection-oriented technologies are the basis of the optical transport networks that underlie most data networks below OC-48 rates, while MPLS is now becoming mature enough to support VPN services in large ISP backbones. It seems likely that connection-oriented technologies will continue to play a

[9] A. Shaik, J. Rexford, and K. G. Shin, Load-Sensitive Routing [10] C.R. Kalmanek, A. Lauck, and K.K. Ramakrishnan,

SUBMARINE: An Architecture for IP Routing over Large NBMA Subnetworks, Proc. INFOCOM ’99. Request for Comments 2332, April 1998.

[11] J. Luciani et al., NBMA Next-Hop Resolution Protocol, IETF [12] G. Armitage, Support for Multicast over UNI 3.0/3.1 based
ATM Networks, IETF Request for Comments 2022, November 1996. ATM Forum, AF-LANE-0084.000, 1997.

[13] LAN Emulation over ATM Version 2.0 – LUNI Specification, [14] A. Charny, K.K. Ramakrishnan, and T. Lauck, Time Scale Analysis and Scalability Issues for Explicit Rate Allocation in ATM Networks, IEEE/ATM Transactions on Networks, Vol. 4, No. 4, August 1996. [15] Traffic Management Specification Version 4.0, ATM Forum, AF-TM-0056.00, 1996, available at:ftp://ftp.atmforum.com/pub/approved-specs/af-tm0056.000.pdf.

ACM SIGCOMM Computer Communications Review

18

Volume 32, Number 5: November 2002

[16] M. Grossglauser, K.K. Ramakrishnan, SEAM: A Simple and Efficient Architecture for ATM Multipointto-Multipoint Communication, Proc. Infocom’97. [17] M. Waldvogel et al., Scalable High-Speed IP Routing Lookups, Proc. Sigcomm ’97. [18] M. Degermark et al., Small Forwarding Tables for Fast Routing Lookups, Proc. Sigcomm ’97. [19] E. Mannie (ed.), Generalized Multi-protocol Label Switching (GMPLS) Architecture, IETF Work in Progress. [20] L. Martini et al., Encapsulation Methods for Transport of [Ethernet frame, ATM Cells, etc.] over MPLS Networks, IETF Work in Progress.

[21] L. Martini et al., Transport of Layer 2 Frames over MPLS, IETF Work in Progress. [22] L. Andersson et al., PPVPN L2 Framework, IETF Work in Progress. [23] E. Rosen and Y. Rekhter, BGP/MPLS VPNs, IETF Request for Comments 2547, March 1999. [24] Multi-Protocol over ATM Technical Specification Version 1.0, ATM Forum, AF-MPOA-0087.000, 1997. [25] Newman P., et al., Ipsilon’s General Switch Management Protocol Specification Version 2.0, Request for Comments 2297, March 1998.

ACM SIGCOMM Computer Communications Review

19

Volume 32, Number 5: November 2002

ACM SIGCOMM Computer Communications Review

20

Volume 32, Number 5: November 2002

Rationalizing Key Design Decisions in the ATM User Plane
Daniel B. Grossman Motorola, Inc. dan.grossman@motorola.com

Abstract
Any technology requires some number of key design decisions. In the case of the ATM user plane, the choices to use ?xed length, 53 byte cells and virtual connections were unorthodox from the perspective of many in the networking research community. This paper attempts a technical justi?cation for those design decisions.

ATM, and many other design decisions, ?owed from the ?xed size cell.

2.1

Deterministic service times

1

Introduction

Technological superiority is not the sole determinant of market success in technology wars; witness, for example, the results of the Betamax vs VHS wars. ATM, which was once hoped to be the underlying substrate for next generation multiservice networks, never achieved its potential. Its proponents permitted it to be drawn into a technology war with IP, and in the end, it was badly battered in the marketplace. Its opponents were able to portray it as complex and ine?cient, and this image did much to undermine it. ATM’s largest vulnerability in the war of perception was in three related design decisions: its use of ?xed sized protocol data units (PDUs), or cells, the 48-octet cell payload size, and its stateful, or connection-oriented nature. These were very di?erent from design decisions made in IP, and thus unorthodox from the perspective of many in the networking research community. Some of the overhead that resulted from these decisions quickly attracted a derisive tag: the cell tax. This stuck, and contributed signi?cantly to ATM’s image problem. This paper presents a technical defense for these design decisions.

Fixed length PDUs have deterministic service times. Deterministic service times reduce average waiting times in congested systems. As an approximation, recall that an M/D/1 queuing system has half the average waiting time of an M/M/1 queueing system [1]. This means that cell-based networks can operate with higher link utilization than variable packet based networks while maintaining acceptable delay and loss. Anecdotally, the Internet backbone is engineered to 30% average loading, while ATM networks can be engineered to 80% average loading [2]. Deterministic service also leads to tighter upper bounds on delay for real-time tra?c than non-deterministic service times. This is especially useful when realtime and non-real time tra?c shares the same physical links, for low-rate links, and in the presence of constant rate real-time tra?c having dissimilar rates. Queueing systems with deterministic service times are easier to analyse than those with general service times. This property can be used to simplify the design and reduce the runtime complexity of admission control, scheduling and other networking algorithms.

2.2

Granularity mismatch

2

Fixed Size Cells

Fixed sized PDUs are the most singular design decision in the ATM technology. Much of the bene?t of
ACM SIGCOMM Computer Communications Review 21

Variable length packet forwarders can only forward integral packets, yet must account for rate and other functions of time in units of bytes. This inconsistency can perturb network dynamics and add complexity. In the ATM forwarding path, the cell is only unit of interest, and no such inconsistency exists. For example, policers in variable length packet networks accumulate credits in units of bytes, while admit/mark/ drop decisions must occur on packet boundaries. Thus, if a packet arrives when the number of available credits is positive and non-zero but
Volume 32, Number 5: November 2002

less than the packet length, the policer must either mark or drop the whole packet, or ’borrow’ credits against future packets. Each of these alternatives discriminates against larger or smaller packets (respectively), and over or under polices (respectively) [3]. Since policers in cell-based networks make admit/mark/drop decisions and accumulate credits on units of one cell, they more precisely police to tra?c contracts. Thus, admission control decisions can be more aggressive without violating service guarantees. Similarly, schedulers in variable length packet forwarder can decide which of several queues to service next next only on a per-packet basis. When the scheduling policy is fairness (or weighted fairness), a simple scheduling algorithm, such as (weighted) round robin or (weighted) fair queueing is biased against sources that send small packets. More sophisticated algorithms, such as de?cit (weighted) round robin, are required to correct this bias, but they add complexity and discriminate to a lesser extent against sources that send larger packets [4]. In networks with ?xed length PDUs, the unit of scheduling is the size of the PDU, and therefore no such discrimination can occur: simpler schedulers are fair. For real time ?ows, it is desirable to service PDUs as close as possible to an ideal departure time. Various kinds of calendar scheduling schemes have been used to do this. Fixed sized PDUs greatly simplify the calendar scheduling problem, since the size of the PDU need not be taken into account in determining whether it can be scheduled before a more urgent one.

3

53 Octets

The 48-octet payload and 5-octet header of the ATM cell were a notorious political compromise between the needs of speech and data transmission. At the time that the cell size needed to be set, the French Administration planned a telephony transport network with budgeted packetization delays of 4 ms, or 32 octets per cell with 64 kbit/s PCM; this was small enough to avoid the need for echo cancellation on calls within continental France. Opinion at the time was that optimal cell size for data transport would be between 64 and 256 octets. The compromise, debated over several meetings of the former CCITT SG 13 [5], is not quite optimal for either telephony or data, but may be globally optimal for the mix of tra?c that would be carried in a multiservice network. ? For PCM telephony, a full cell has a packetization delay of 6 ms, which is usually within the delay budgets of modern Voice-over-ATM systems, even those designed for transcontinental calls. ? Measured packet size distributions in the Internet have a sharp peak at 40 octets, which is the size of an IPv4 datagram containing a TCP SYN, FIN or ACK, with neither IP nor TCP options. Such a packet ?ts exactly into a single cell when AAL5 is used. Unfortunately, LLC/SNAP encapsulation is frequently used instead of the so-called null encapsulation. It adds 6 octets of overhead, and therefore forces TCP control packets to cross a cell boundary. ? Two MPEG2 transport streams packets exactly ?t into eight cells when AAL5 is used. In addition, most switch implementations require some internal overhead to be prepended to each PDU to form an internal forwarding unit. Switch hardware usually operates in units of bytes that are powers of 2; thus a 64 bytes internal forwarding unit (including 16 bytes of overhead) can be extremely convenient. The “cell tax” slur arises from the ?ve octets of overhead required for 48 octets of payload. Recollect that all packet-based networks have header overhead. ATM cell header overhead is 9.5%. PCM telephony systems that can accommodate a 6 ms packetization time su?er only this overhead. MPEG2 transport over ATM su?ers an additional 3.2% overhead due to the AAL5 trailer, in the default mode of operation (two MPEG2 TS packets in an AAL5 PDU). For IP
Volume 32, Number 5: November 2002

2.3

Hardware Implementation

Queueing systems, bu?er managers, interconnects and other datapath elements can be greatly simpli?ed by ?xing the size of the PDUs they carry. Complexity metrics such as interconnect width, memory sizing, number of control lines, and amount of handshaking can be reduced by ?xing the length of PDUs. These metrics can a?ect die size, clock speed and pin counts. For example, a ?xed sized PDU allows pipeline stages to be made synchronous, permits parallel processing without having to perform internal bu?ering to avoid misordering, and requires only a single size bu?er pool, without need for fragmentation. Deterministic service times remove blocking, and facilitate cycle count budgeting. These advantages are so signi?cant that many Ethernet switches and IP routers use ?xed size data units in their fabrics.
ACM SIGCOMM Computer Communications Review 22

transport over AAL5, including LLC/SNAP encapsulation, overhead as measured in the Internet is 20 percent [6]. Without LLC/SNAP encapsulation, it would be 15%, leading one to speculate that if header overhead were truly meaningful to network operators, LLC/SNAP encapsulation would have been eliminated. More important, operators can more than compensate for ATM header overhead by more aggressive tra?c engineering, which is made possible by deterministic queueing.

[8]. Ternary CAM devices help, but are complex and presently expensive. Forwarding tables scaled to global Internet presently need tens of thousands of entries. State information is required by policers, shapers, markers, schedulers, per-connection queues, ?ow control and admission control, which are needed to support services with QoS guarantees. In an ATM network, this state information is inherently associated with a virtual connection link through the VPI/VCI. In connectionless networks, packet classi?cation is necessary to associate a packet with its state information. Classi?ers have between O(logN) and O(N) 4 Virtual Connections complexity, and mechanisms and policies for con?gPacket-based networking systems may be character- uring classi?ers (especially in the core) are complex ized as being either connection oriented or connec- and likely to be imprecise. tionless. Selection of one of these design approaches State information can be used in conjunction with has broad implications on the network architecture per-connection queues and scheduling algorithms to and its implementations. This has been a deeply con- enforce network policies (e.g., fairness) among best troversial subject since the early 1970s. For the en- e?ort connections. Connections that transmit at a vironment for which ATM was intended, connections rate exceeding their share of link bandwidth ?ll their and their attendant state information have a number queues, invoking discard policy. As a result, these of advantages, and some disadvantages. connections do not interfere with better-behaved conMuch processing is done once in connection- nections. Forwarders for connectionless networks oriented systems during connection establishment, may, of course, implement classi?cation and per-?ow but done for each packet in connectionless systems. queueing, at cost in complexity as noted above. OthThis makes connection-oriented systems better op- erwise, misbehaved connections can at best be dealt timized for long-lived communications, as would be with in a statistical fashion, using an active queue expected for telephony, video delivery, and similar management algorithm such as RED. While there is applications. Connectionless systems are better op- some evidence that such algorithms improve the statimized for short lived communications such as DNS bility of the Internet [9], there is also evidence that lookups. A majority of packets in the Internet are as- they are not e?ective [10,11], that they are hypersociated with long-lived ?ows, even though the ma- sensitive to con?gurable parameters [12], and that jority of ?ows are short lived [7]. Attempts by the they do not address non-responsive ?ows. Per-?ow ATM Forum to create a native connectionless mode queueing and longest queue discard are a far better to complement the connection oriented mode were solution. unfortunately not successful. On the other hand, one Connection-oriented networks do not su?er from could imagine that applications might have evolved many of the security vulnerabilities that are often exdi?erently if the underlying network encouraged de- ploited in connectionless networks; for example, atsign for long-lived ?ows. tacks that depend on address spoo?ng, such as the Per-packet forwarding decisions in ATM nodes are SYN attack, are not possible in connection oriented can be implemented with simple table lookups or networks. State information also makes tracing an binary content-addressable memories, over the VPI attack back to its originating interface signi?cantly and/or VCI ?elds, with O(1) computational com- easier. Further, state information is useful as a baplexity. The size of these tables can scale with the sis for security associations and audits, and simpli?es number of VP and/or VC links expected to cross security design and implementation. In addition, useach interface. IP requires longest match lookup over age accounting, as required for usage-based billing, the IPv4 or IPv6 destination address ?elds. To the requires state information. In cases such as virtual author’s knowledge, the least computationally com- private networks, IP-in-IP and IPSEC tunnels, with plex longest match algorithm has lookup complex- their considerable overhead, are used as a substitute ity of O(LogN) and update complexity of O(kLogkN) for connection state.
23 Volume 32, Number 5: November 2002

ACM SIGCOMM Computer Communications Review

5

Conclusions

[7] ibid. [8] Ruiz-Sanchez, M.A.; Biersack, E.W.; Dabbous, W. , “Survey and taxonomy of IP address lookup algorithms” IEEE Network , Volume: 15 Issue: 2 , March-April 2001 pp. 8 -23 [9] Braden, B. et al, “Recommendations on Queue Management and Congestion Avoidance in the Internet”, RFC 2309 (April 1998) [10] May, M.; Bolot, J.; Diot, C.; Lyles, B., “Reasons not to deploy RED”, technical report, June 1999. [11] Christiansen, M; Je?ay, K; Ott, D; Smith, F.D. “Tuning RED for Web Tra?c”, Proc. ACM SIGCOMM, August 2000 [12] Firoiu, V.; Borden, M., “A Study of Active Queue Management for Congestion Control”, Proc. IEEE Infocom 2000

ATM’s key design objectives were to operate in a public network environment, to carry real time and non-real time tra?c and to be optimized for hardware implementation in switches. A series of design decisions ?owed from those objectives, including virtual connections and ?xed size, 53-octet cells. From a technology perspective, it can be argued that those decisions withstood the test of time. Unfortunately, the arguments for these decisions are subtle, and the counter-arguments were simple and were made persuasive by repetition. It is not clear how much the “cell tax” slur contributed to limiting the success of ATM. There were other issues, such as the experience curve resulting from a large previously installed base of Ethernet, slow deployment of capabilities to simplify con?guration (especially SVCs), lack of ATM-aware applications software, delays in critical standards, and numerous business decisions made by some industry players. Nonetheless, market perception was an important factor, both directly and in its e?ects these other issues. Perhaps the most important lesson that can be drawn from this paper is that proponents of novel networking technologies need to justify their design trade-o?s in a way that will be understood by the market, and to reinforce their justi?cation. They must also be prepared respond forcefully and credibly when these trade-o?s are attacked. ATM’s proponents did neither.

References
[1] Kleinrock, Leonard Queueing Systems vol. 1 (New York, John Wiley and Sons, 1975) p. 191 [2] Private conversations [3] Bernet, Y; Blake, S. Grossman, D; Smith, A “An Informal Management Model for Di?serv Routers” RFC 3290 (April, 2002) [4] Shreedhar, M.; Varghese, G. “E?cient Fair Queueing using De?cit Round Robin” ACM Computer Communication Review, vol. 25, no. 4, pp. 231–242, Oct. 1995. [5] Reports of the meetings of CCITT SG 13, 1988 [6] Thompson, K.; Miller, G.J.; Wilder, R. “Widearea Internet tra?c patterns and characteristics” IEEE Network, Volume: 11 Issue: 6 , Nov.-Dec. 1997 pp. 10 -23
ACM SIGCOMM Computer Communications Review 24 Volume 32, Number 5: November 2002

A Perspective on how ATM Lost Control
Simon Crosby? Sean Rooney? Rebecca Isaacs? Herbert Bos§ , , ,
fered by IP is inadequate for enterprise customers who have relied for years on the dependable alternaContrary to the initial high expectations, ATM failed tives of leased lines, Frame Relay and ATM. to become the universal network technology covering Notwithstanding the ubiquity of IP at the edges all services and running from the desktop to the back- of the network, ATM still has very healthy growth bone. This paper tries to identify the technological numbers. All DSL tra?c crosses ATM, it comprises problems that contributed to this failure. the core of most IP networks, ATM VPNs are commonplace and there is even a considerable market for circuit emulation services, including voice over ATM. 1 Introduction The lack of any kind of service guarantees together From a service provider perspective, the Internet is a with the di?culty for service providers to charge for nightmare. Although enterprises are reaping tremen- value added to an IP network, suggests that ATM is dous bene?t from lower communications costs and a missed opportunity. So what went wrong? new IP-based applications, the anticipated pro?ts to service providers from the Internet economy have not The ATM value proposition materialised, and record numbers of carriers and their 2 suppliers are going out of business. The roots of the problem lie in the architectural principles of IP which Borrowing from earlier control planes, speci?cally delivers just one service: unreliable, insecure, best the narrowband Q.931 signalling standard, the e?ort connectivity. Although tremendous bene?t is ATM standardization community developed a Usergained from IP at the edge of the network due to its Network Interface (UNI), and subsequent Networkinherent simplicity and because it allows the applica- Network Interface (NNI), that would allow users to tion provider to be entirely freed from network con- dynamically signal for connectivity with the approstraints, there is an assumption that the providers priate bandwidth and QoS guarantees that applicawill continue to increase capacity so that IP based tions required. The notion of a User-Network sigapplications will deliver high quality. Thus in the IP nalling interface was seen as a crucial part of the value model the provider has to deliver constantly grow- proposition for ATM. From the point of view of the service provider, IP ing amounts of bandwidth, but is totally excluded is ?awed because there is no way to link revenues to from the value chain. E?ectively the provider takes the role of a bit pipe, with no way to link their rev- the value customers derive from the network. In this enues to the value their customers derive from the respect, ATM had the potential to gain advantage network1 . Furthermore, the best e?ort service of- over IP, provided that a suitable UNI could be developed. However, the UNI standardised by the ATM ? simon@cplane.com, CPLANE Inc, USA Forum was defective in at least three ways. Firstly, ? sro@zurich.ibm.com, IBM Research, Switzerland ? risaacs@microsoft.com, Microsoft Research, UK it was ?awed because the UNI was tied to a speci?c
LIACS, The Netherlands has grown to roughly 60% of the tra?c volume in some carriers but accounts for a tiny fraction of the pro?ts
1 Data § herbertb@liacs.nl,

Abstract

so providers are being forced to put more assets in place to support their lowest margin business.

ACM SIGCOMM Computer Communications Review

25

Volume 32, Number 5: November 2002

technology (ATM) requiring the signalling layer to be implemented ‘on the box’. This means that every access interface, in particular every operating system, edge router and device that might be attached to the network in the future, must implement a complex, heavyweight signalling stack. It doesn’t take much insight to see that to require that every OS implement the signalling stack was an act of insanity which doomed ATM to failure. Secondly, the model provided no accountability for signalling. That is, when the user exercises the UNI, and signals for an ATM connection, there is no hook into the billing system that allows the provider to account for and therefore bill for the value delivered over the interface. Finally, the ATM UNI was extraordinarily heavyweight and complex. Because it tried to de?ne all possible service models for all possible applications, present and future, it became bulky and di?cult to understand. At the same time, its closed nature made it impossible to provide new services for applications with speci?c requirements that were not catered to by the standards. Thus the ATM UNI signalling protocol was crippled from the outset, imposing impossible burdens on both service providers and the users of the network. Perhaps it is time to re-evaluate the need for signalling across the User-Network interface, and this time to get it right. The key requirements are clear: separate the UNI from the underlying network delivery technology, make it easy for application users at the edge of the network, and allow providers to bill for services delivered using it. Let’s step back for a moment to Signalling System Number 7 (SS7), a network of signalling channels used in the Public Switch Telecommunication Network. Why was it valuable? The answer is remarkably simple: It separated the signalling from the equipment. The SS7 Service Control Point allowed the provider to implement value propositions (albeit limited ones) independent of the underlying switched network. The provider owned the application (eg 800 number or ‘follow me’) and on the basis of performing some function in response to a user interaction via the ‘UNI’, the provider could charge, and make money. Although designed on this model, ATM control is too complex and presents the wrong level of ab-

straction to application developers and users. Small wonder then that almost all ATM connections are set up using the hopelessly impoverished pseudo signalling protocol SNMP: Providers ‘provision’ connections (usually sPVCs or PVCs), turning the dynamic nature of ATM into a sham, and its capabilities simply into a ?exible virtual topology on top of ?xed TDM capacity. This allows providers to tra?c engineer for IP, deliver basic DSL ‘pipes’ and some voice tra?c, with QoS, but the oft-touted B-ISDN dynamic service interface has never been deployed.

3

Open Signalling

SS7 on the PSTN was successful because it o?ered service providers a way to add value to the network and to charge accordingly, but the system is closed to third parties, inhibiting the development and deployment of new and innovative services. The need for an open network was not recognised by the ATM Forum, who, by not specifying the interface between the control plane and the physical network, tied the control software to the physical devices. Although architecturally distinct, cell forwarding and connection establishment functions tend to be integrated, and this results in switch-speci?c control systems which can only be maintained and evolved by vendors. In academia such concerns led to the establishment of the OPENSIG forum to develop a more ?exible control plane for ATM. Open signalling systems require that there be a clear divide between the control plane and the data plane, with an open, switchindependent control API. Open signalling ideas were heavily in?uenced by the industrially developed IP Switching[4] which discarded entirely the standard ATM control plane. An IP Router built over an ATM switch made a local decision as to whether the packets of a ?ow should be forwarded at the software IP layer or, if the ?ow was su?ciently longlived, to cut through onto the ATM hardware layer. IP Switching was ultimately not successful because hardware IP routers became commonplace, but its General Switch Management Protocol for communication between the IP control layer and the ATM forwarding layer is an example of a switch-independent

ACM SIGCOMM Computer Communications Review

26

Volume 32, Number 5: November 2002

Ultimately open signalling failed; ATM’s control plane has been abandoned and ATM is used as one of many layer-2 protocols in the public internet. Retrospectively it can be seen that simplicity of deployment was the killer argument for IP. However, ease of deployment does not equate with simplicity of management and IP’s lack of precise control over the data 4 Lessons learnt with ATM path makes it hard for network operators and service providers to di?erentiate their o?erings in a meanIP is the basic uni?er of the enterprise application suite, and is the primary vehicle for applications of ingful way. ATM’s relegation as nothing more than value. This indicates that the control procedures for a ?exible way to compensate for the most blatant interacting with the network should occur at a much failings of IP, as far as reliability and predictability higher layer, speci?cally the application layer, to al- of service are concerned, is a result of over-complex low applications to directly interact with the network protocols without an adequate understanding of the to dynamically request the security, bandwidth QoS business driver. and other attributes that are required. Pipe based services (whether ATM or IP based) 6 Acknowledgments relegate the service provider to the role of simple bit shifter, but the value proposition has moved outside Thanks are due to Kobus van der Merwe for his valuthe network. The right way to solve the control prob- able insights and discussions. lem is to ensure that it is out of band so it allows customers to dynamically request network services References to meet application speci?c needs (bandwidth, QoS, etc). It should also be technology independent, so [1] Bos, H. Open extensible network control. Journal of Network and Systems Management 8, 1 (Mar. 2000). that the service layer concepts of value can be deliv[2] Isaacs, R., and Leslie, I. Support for resource-assured ered independent of the underlying delivery technoland dynamic virtual private networks. IEEE Journal on ogy (ATM, GigE, MPLS, IP or whatever comes next). Selected Areas in Communications 19, 3 (Mar. 2001), 460– This motivates for development of ‘application layer 472. Special Issue on Active and Programmable Networks. signalling’ which enables direct interaction between [3] Newman, P., Edwards, W., Hinden, R., Hoffman, E., Ching, F., Lyon, T., and Minshall, G. Ipsilon’s Genapplication components and the network, without reeral Switch Management Protocol speci?cation version 2.0. quiring detailed knowledge of the network infrastrucRFC 2297, Mar. 1998. ture, and encompassing both servers and networks. [4] Newman, P., Minshall, G., and Lyon, T. IP switching: Why is application layer signalling important? PriATM under IP. IEEE/ACM Transactions on Networking marily because the only successful service provider 6, 2 (Apr. 1998), 117–129.

control API which has since been standardized by the IETF[3]. The large number of proposals to replace the ATMF control plane seriously questions the basic assumption of the standardization bodies that there is a single control interface which will provide for the needs of all applications and services. In response to this, the open signalling community addressed the need to support a plurality of ATM control systems. Work done at Cambridge, using virtual resource partitioning, showed how this could be achieved[7] and was extended to support novel control planes[5, 1] and a virtual network service[8, 6, 2]. These academic e?orts have in turn been adopted by industry through the Multiservice Switching Forum and the IEEE P1520 proposed standard for network APIs.

models are those that allow customer-network interaction. This is possible in the PSTN, but it is impossible in the ‘best e?ort pipes’ based IP network. Providers need to be able to interact with their customers, to implement services for which their customers are prepared to pay a premium. If they are unable to do so, they will become just utility bitsper-second providers.

5

Conclusion

ACM SIGCOMM Computer Communications Review

27

Volume 32, Number 5: November 2002

[5] Rooney, S. The Hollowman: An innovative ATM control architecture. In Integrated Network Management V (San Diego, USA, May 1997), A. Lazar, R. Saracco, and R. Stadler, Eds., IFIP & IEEE, Chapman & Hall, pp. 369– 380. [6] Rooney, S., van der Merwe, J. E., Crosby, S. A., and Leslie, I. M. The Tempest: A framework for safe, resource-assured programmable networks. IEEE Communications Magazine 36, 10 (Oct. 1998), 42–53. [7] van der Merwe, J. E., and Leslie, I. Switchlets and dynamic virtual ATM networks. In Integrated Network Management V (San Diego, USA, May 1997), A. Lazar, R. Saracco, and R. Stadler, Eds., IFIP & IEEE, Chapman & Hall, pp. 355–368. [8] van der Merwe, J. E., Rooney, S., Leslie, I., and Crosby, S. The Tempest—a practical framework for network programmability. IEEE Network Magazine 12, 3 (May/June 1998), 20–28.

ACM SIGCOMM Computer Communications Review

28

Volume 32, Number 5: November 2002

The In?uence of ATM on Operating Systems
Jonathan M. Smith? CIS Department, University of Pennsylvania jms@cis.upenn.edu

Abstract
The features of ATM o?ered many attractions to the application community, such as ?ne-grained multiplexing and high-throughput links. These created considerable challenges for the O.S. designer, since a small protocol data unit size (the 48 byte “cell”) and link bandwidths within a (binary) order of magnitude of memory bandwidths demanded considerable rethinking of operating system structure. Using an historical and personal perspective, this paper describes two aspects of that rethinking which I participated in directly, namely, those of new event signalling and memory bu?ering schemes. Ideas and techniques stemming from ATM network research in?uenced ?rst research operating systems and then commercial operating systems. The positive results of ATM networking, although indirect, have bene?tted applications and systems far beyond the original design goals.

1

Introduction

The various technical contributions of the US “Gigabit Testbed” program[Computer 90] were both manifold and undersold. Amongst the more signi?cant contributions were those made in the AURORA Gigabit Testbed, which linked Penn, Bellcore, IBM Research and MIT in the Northeast corridor of the United States [Clark 93]. While AURORA experimented with two packet formats, “Packet Transfer Mode” (PTM) and “Asynchronous Transfer Mode” (ATM), in retrospect the ATM-centric research had signi?cantly more impact on modern operating system software.
? Work supported by the NSF and ARPA under Cooperative Agreement NCR-8919038 with CNRI, by Bell Communications Research under Project DAWN, by an IBM Faculty Development Award, and by the Hewlett-Packard Corporation.

It is is worthwhile to set the stage. While AURORA was initiated in 1990 under the HPCA (“Gore Bill”) the research was actually kicked o? at Penn and MIT in 1989 under Project DAWN, funded by Bellcore. The goal was to build an integrated LAN/WAN infrastructure using an OC-48 SONET channel provided by Bell Atlantic, MCI and Nynex. Using a clever OC-12 cross-connect topology devised by Dave Sincoskie of Bellcore, we were able to concurrently operate PTM over SONET from Penn to IBM and MIT, and ATM over SONET from Penn to Bellcore to MIT. While supercomputers were used in several other testbeds, AURORA focused on workstation technology, as it was believed (correctly, in retrospect) that delivering high throughputs to this class of machine would have more long-term impact. The available workstation technology was the ?rst generation of RISC computers, which were characterized by an increased number of simpler instructions executed per clock cycle, higher clock rates, and relatively poor DRAM and I/O throughputs given the computational performance. As it is today, multiple levels of cache memory were used to resolve some of the CPU/DRAM performance “gap” [Patterson 02]. A major problem that we faced as network subsystem architects was that the advantages of caching only apply once the data is in the memory hierarchy, while a major role of the network subsystem is moving the data into the hierarchy, before any such advantages apply. One major research direction pursued at Penn was an architectural study of the challenges in delivering the substantial bandwidths (while not so impressive today, the OC-3c bandwidths we targeted to in 1989/1990 were over 13 times as fast as the commonly used LAN technology). This architectural study took the form of a hardware/software codesign, where a hardware subsystem, in the form of an ATM host interface [Traw 91, Traw 93], was designed in concert with new operating system supVolume 32, Number 5: November 2002

ACM SIGCOMM Computer Communications Review

29

port [Smith 90, Smith 93, Chung 95] designed to expose the strengths of the ATM technology, in particular its substantial bandwidth. While a secondary consideration at the time, another lasting contribution came from exposing the ?ne-grained control of multiplexing possible with ATM [Nahrstedt 96]. The remainder of this paper is organized in three sections. The next section, on “Bu?er Management”, discusses some of the challenges associated with memory architectures in the early 1990s and connects a thread of research results which led to changes in many commercial operating systems. Section 3 covers changes in event-signalling architectures, which have had considerable in?uence on the research community but perhaps less on the commercial front. Finally, in Section 4 we conclude the paper, observing ?rst that ATM-driven advances in software paved the way for Fast Ethernet and faster LANs, and second that the same fundamental stresses amongst trendlines are still in place as network engineers and workstation designers continue to march to di?erent drummers.

These included (quoting from the paper): ? UPWARDS scheduling is entirely synchronous; the only “interrupt” allowed is that of the system clock driving the scheduler. Interrupts complicate device drivers and are really an artifact of a desire for high levels of multiprocessing, rather than high performance computing with low levels of multiprogramming. In addition, interrupts defeat architectural features necessary for very high performance, since as caches and pipelines. ? The UPWARDS interprocess communication mechanism is shared memory. While like many operating systems designs, UPWARDS was never fully realized, it provided considerable guidance in what was to follow. Others were of course working in this space, in particular Clark and Tennenhouse [Clark 90] had likewise noted the importance of memory bandwidth, with their focus being on protocol architectures. The vision of UPWARDS IPC being shared memory was driven, in fact, by a belief that a distributed shared memory model for distributed computing [Smith 91] would provide an appropriate basis for a high-performance protocol architecture.

2

Bu?er Management

David Farber, my colleague at the University of Pennsylvania, had worked with Bob Kahn to get the Gigabit Testbed initiative underway. Kahn had set a “Gigabit litmus test”, which demanded a gigabit per second throughput, delivered to or from a single application. In early 1990, I began considering the shape of an operating system appropriate for the support of a workstation in an environment with very high performance networks. While it was by then quite clear that a supercomputer [Borman 89] could deliver or accommodate such throughputs, it was also clear that workstations would be extremely challenged if they were called upon to meet the “litmus test”. Even if the technical challenges of the host adaptor hardware were met, it was unclear if the workstation could handle the data ?ow from the adaptor. While the merits of the RISC workstation technology were clear from a computational perspective, it was unclear how they would handle data management, particularly in the performance regimes the ATM technology required. I laid out principles for a new operating system called “UPWARDS” [Smith 90] (for “U Penn Wide Area Research Distributed System”) intended for a network with bandwidth within an order of magnitude of memory bandwidth.
ACM SIGCOMM Computer Communications Review 30

2.1

Hardware Context, O.S. Presumptions and Basic Arithmetic

Working with IBM gave AURORA researchers access to a particularly potent workstation technology, the RS/6000, which was just being made available at the time the testbeds were forming. The IBM RS/6000 had been recently introduced [Bakoglu 90] and was IBM’s entry in the engineering workstation market. All indications were that it was quite competitive [Simmons 90], being equal to supercomputers one generation old (on computational workloads). The outstanding feature of the RS/6000 was its relatively large memory bandwidth (using a tool we developed, we measured a Model 320 to have 1 Gbit/s of bandwidth, the Model 530 to have 1.8 Gbit/s of memory bandwidth, and the Model 580 to have 2.5 Gbit/s of memory bandwidth). Others con?rmed this later with benchmarks [McVoy 96]. The I/O bus technology, the Microchannel, was an apparent limitation. We chose to work around this by applying a specialized style of direct-memory-access transfer called streaming, which provided twice the throughput of
Volume 32, Number 5: November 2002

normal DMA, giving us some hope of reaching the application performance targets for AURORA. The Microchannel throughput in this mode was 320 Mbit/s, adequate for the OC-3c data rate of the adaptor. Looking at some basic performance metrics for this machine, it appeared to be a reasonable platform, but it was clear that some new thinking was required: the o?-the-shelf operating system (AIX) would have to be modi?ed, both to reduce copying and to support multimedia. I began to examine how the UPWARDS ideas could be implemented using AIX (IBM’s version of UNIX) as a starting point on the RS/6000.

2.2

Reducing Copying

Even with the Gbit/s range memory throughputs on the RS/6000, it was clear [Watson 87] that reducing bu?er copying would have considerable impact on performance. We avoided some software-driven copying by use of a hardware feature of the IBM RS/6000, a set of Translation Control Words (TCWs) that provided virtual addressing capability to I/O devices such as our host adaptor. The challenge of structuring memory and choosing where it was addressed for adaptor transfers, as well as scheduling transfers to allow maximum concurrency with other processing (such as that required by the application), led to a “double bu?ering” strategy.
read(fd, buf, size) Kernel Buffer #0 ATM Adaptor Buffer Kernel Buffer #1 DMA Cells

using large 32KB or 64KB datagrams. However, the performance of the system for small bu?ers was less impressive, dropping into the tens of megabits per second for packet sizes more typical of application tra?c (50-1000 bytes). The shared memory communication model of UPWARDS led to exploring a lighter-weight data transfer mechanism between user processes and the ATM adaptor. Recoding of the driver support for the UNIX read()/write() calls 1 allowed transfers directly to or from a user bu?er passed to the system call, as shown in Figure 2. Even with the heavyweight control operations involved in interpreting the system calls, this essentially achieved “zero-copy” operation for the data transfers, as only the required DMA from the adaptor was required to get the data into application memory.
read(fd, buf, size)

User DMA of Packets Buffer ATM Adaptor Cells

User Address Space

Kernel Address Space

Figure 2: No copy (other than required DMA), but no concurrency Of course, the application was blocked while this occurred, so there was little concurrent activity for the process using the mapped bu?er. Thus we sought to remove the system call overhead for small packets by implementing a shared memory region between kernel and user space, with a carefully orchestrated passing of control of the shared regions between user process and kernel to ensure that all available concurrent operation of the hardware could be exploited. The architecture is illustrated in Figure 3. While all of these con?gurations were implemented and were able to fully utilize the ATM link at the larger packet sizes, the shared memory interface far outperformed the system-call based scheme on small packets, had the least e?ect on other applications, and fully exploited the ability of the bus-mastering
1 I/O to a UNIX[Thompson 78] “raw” device is passed to a device-speci?c routine, e.g. atm read() and atm write()

User

Data Copying

User Address Space

Kernel Address Space

Figure 1: Kernel Bu?er Ring - Concurrency with Copying Management of a pair of bu?ers (this is a fairly standard scheme for network adaptor device drivers, sometimes generalized as a bu?er ring), as shown in Figure 1, gave the system considerable throughput (up to about 110 Mbps), and considerable concurrency. This performance was achieved by spreading the per-packet overheads over many bytes of data by
ACM SIGCOMM Computer Communications Review 31

Volume 32, Number 5: November 2002

read(fd, buf, size) User Access to Data

Shared Buffer #0 Shared Buffer #1 Packet DMA

ATM Adaptor

Cells

User Address Space

Kernel Address Space

Figure 3: Memory bu?ers shared between user and kernel address spaces adaptor to operate concurrently with the processor. These implementations were used to support applications ranging from a wide-area distributed shared memory [Sha?er 96] to a telerobotics system [Nahrstedt 96]. The applications used a TCP/IP [Alexander 94] implemented using a virtual device abstraction2 used to cope with the fact that the ATM adaptor was implemented as two Microchannel cards, one for ATM segmentation, with the other for ATM reassembly. These experiments demonstrated that one of the basic intuitions of the initial UPWARDS, that shared memory models for communications would lead to high performance, were experimentally sound. We address the interrupt issue below in Section 3.

bu?ers called “fbufs”. Fbufs’ data typing allowed implementation of the bu?er control protocol without the extra overheads of address space setup and teardown for virtual address translation, showing that the bu?ering schemes we developed could be made even more e?cient. Druschel [Druschel 94] demonstrated fbufs in an implementation for Bruce Davie’s Osiris ATM adaptor. Druschel’s design exhibited adaptor to host memory transfers at over 500 Mbps for UDP packets [Druschel 94] on an extremely fast processor, the Alpha, which had just been introduced by the Digital Equipment Corporation. A host-to-host UDP throughput of about 300 Mbps could be inferred from the upper bound on the TurboCHANNEL write throughput reported in the paper. While as far as I am aware, TCP was never demonstrated with this system,3 fbufs are a nice improvement over the basic shared memory abstraction which started with UPWARDS. It also nicely illustrates how work done initially for networking goals can in?uence mainstream operating systems research. Indeed, this in?uence can persist; re?nement of this architecture continued with LRP [Druschel 96].

The most important work done concurrently was by the Hewlett-Packard Laboratories [Dalton 93, Banks 93, Edwards 94] in Bristol, UK. There, a high performance host adaptor architecture was developed which allowed a direct mapping of substantial bu?er memory on the adaptor directly into application address space. The power of this approach was that it was then reasonably straightforward to write an 2.3 Related and Follow-On Work; application-level TCP stack which directly manipCommercial Impact ulated bu?er memory on the adaptor, minimizing copying across the bus to which the adaptor was atThe most important follow-on work in the research community was that of Peterson and Druschel. In tached. In many ways, this user-level TCP/IP set a paper presented in Tucson in 1992 [Traw 92], we directions for the user-implemented protocols in verdiscussed the basic double-bu?ering strategy which tically structured operating systems such as the exallowed application processing of data in one bu?er okernel [Engler 95]. while allowing a streaming transfer into another Commercial vendors paid considerable attention to bu?er. Druschel [Druschel 93], moving bu?er man- the software architectures we developed. One examagement issues into the mainstream operating sys- ple is the work of Chu [Chu 96], who adapted the tems community, adopted this basic strategy in his shared memory techniques and fbufs to the commer“fbuf” bu?er management architecture. However, cial Solaris operating system supplied with Sun Mirather than using VM protection coupled to double- crosystems computers. The Chu work supported a bu?ering, Druschel used the type system of his im- 622 Mbit/s ATM adaptor developed by Sun. plementation language to control access to specialized

2 The virtual device was de?ned by constructing a driver overlay which redirected system calls for the virtual device to appropriate invocations of driver entry points for the physical devices.

3 A problematic DMA controller was rumored to have made repeatable measurements di?cult.

ACM SIGCOMM Computer Communications Review

32

Volume 32, Number 5: November 2002

3

Event Signalling

Event-signalling within the network subsystem between the hardware network interface device and the software device driver is typically accomplished via polling or device-generated interrupts. In our implementation of an OC-3c ATM host interface for the IBM RS/6000 family of workstations [Traw 93, Smith 93], we replaced the traditional forms of this crucial function with “clocked interrupts.” Clocked interrupts, like polling, examine the state of the network interface to observe events which require host operations to be performed. Unlike polling, which requires a thread of execution to continually examine the network interface’s state, clocked interrupts perform this examination periodically upon the expiration of a ?ne-granularity timer. In comparison to interrupts, clock interrupts are generated indirectly by the timer and not directly by the state change event.

interrupt service schemes can be improved, e.g., by aggregating tra?c into larger packets (this reduces λ signi?cantly, while typically causing a slight increase in α), by using an interrupt on one channel to prompt scanning of other channels, or masking interrupts and polling some tra?c intensity threshold. One would therefore expect that for application workloads characterized by high throughput, heavy multiplexing, and/or “real-time” tra?c, clocked interrupts should be more e?ective than either traditional polling or interrupts.

3.2

Clocked Interrupts

3.1

Hardware/Software Context, O.S. Presumptions and Basic Arithmetic

Consider a system with an interrupt service overhead of C seconds per interrupt, and k active channels, each with events arriving at an average rate of λ events per second. Independent of interrupt service, each event costs α seconds to service, e.g., to transfer the data from the device. The o?ered tra?c is λ ? k, and in a system based on an interrupt-per-event, the total overhead will be λ ? k ? (C + α). Since the maximum number of events serviced per second will be 1/C + α, the relationship between parameters is that 1 > λ ? k ? (C + α). Assuming that C and α are for the most part ?xed, we can increase the number of active channels and reduce the arrival rate on each, or we can increase the arrival rate and decrease the number of active channels. However, for clocked interrupts delivered at a rate β per second, the capacity limit is 1 > β ?C +λ?k ?α. Since α is very small for small units such as characters, and C is very large, it makes sense to use clocked interrupts, especially when a reasonable value of β can be employed. In the case of modern workstations, C is about a millisecond. Note that as the tra?c level rises, more work is done on each clock “tick,” so that the data transfer rate λ ? k ? α asymptotically bounds the system performance, rather than the interrupt service rate. We note that traditional
ACM SIGCOMM Computer Communications Review 33

The ATM host adaptor we developed for the IBM RS/6000 [Traw 93] was designed with clockedinterrupt based event-signalling in mind. One artifact of this was that there was no support for interrupt generation, an omission that would plague us later, when we were evaluating whether the clocked interrupt scheme performed as we had intended and needed comparison against interrupts to make the case. While a comparative evaluation would have strengthened the technical case for clocked interrupts, we were able to demonstrate two key assertions. First, clocked interrupts could deliver throughputs up to the hardware limits of the RS/6000, in this case slightly over 130 Mbit/s on the Model 580 processor. Second, clocked interrupts provided excellent support for applications with multimedia streams; this was demonstrated by teleoperating [Nahrstedt 96] a robot arm over an ATM network using several RS/6000s. The question of whether any advantage actually accrued to clocked interrupts intrigued us, so we set out to study it in a second generation of our host interface architecture. The second generation combined segmentation and reassembly in a single board, and absorbed other useful features from the design of the Afterburner [Banks 93, Dalton 93]. It also operated at OC-12c, or four times the link rate of the RS/6000 adaptor which operated at the OC-3c link rate of 155 Mbit/s. To get tight control of the clock on the PARisc we altered the clock support subsystem to perform clock division, and used the basic single-copy TCP/IP stack developed by HP Bristol [Edwards 94, Edwards 95]. We were then able to construct a polling based scheme using a user process, apply traditional interrupts, and operate clocked interrupts at a variety of clock rates. We used a 640+ SONET compliant link to interconnect two HP 9000 Model
Volume 32, Number 5: November 2002

small socket bu?er sizes. Another important factor in networking performance, and perhaps a more important parameter for distributed applications is the round-trip latency induced by the software supporting the adaptor. Since the hardware was a constant, we could directly compare the software overheads of the three schemes. This was done with the following test. An arti?cial network load was created using netperf with a socket bu?er size of 262144 bytes and operating it continuously. Against this background load, ICMP ECHO packets of 4K bytes were sent to the TCP/IP receiver, which was where the event-signaling performance di?erences would be evident. Sixty tests were done to remove anomalies. Our results showed that traditional interrupts and clocked interrupts at 500 Hz performed similarly, yielding minimum, average and worst case times of 5/12/18 ms, and 4/11/25 TCP/IP Throughput, Afterburner ATM Link Adapter on HP 755s, 32KB messages (unloaded) ms, respectively. When the systems were not loaded, the performances were 3/3/3 ms and 4/4/6 ms. This suggests that clocked interrupts performed slightly better under heavy load, but slightly worse under unloaded conditions. We draw three conclusions about this eventsignalling architecture. First, clocked interrupts can Socket Buffer Size (KB) provide throughput equivalent to the best throughput available from traditional interrupts; both methFigure 4: Throughput versus clocking, unloaded ma- ods provide better performance than polling as implemented here. Second, clocked interrupts prochine vide higher throughput when the processor is loaded by a computationally-intensive process; this suggests that clocked interrupts may be a viable mechanism TCP/IP Throughput, Afterburner ATM Link Adapter on HP 755s, 32KB messages (loaded) for heavily loaded systems such as servers, which might also su?er from Ramakrishnan’s receive livelock. Third, clocked interrupts provide better roundtrip delay performance when systems are heavily loaded for large ICMP ECHO packets.
240 220 200 180 160 140 120 100 80 60 40 20 0

755s back-to-back, and then performed experiments using the netperf [IND 95] performance analysis tool, with machines both unloaded (Figure 4) and loaded with a computationally intensive workload (Figure 5). While the experimental setup and results here are covered in [Chung 95] and [Smith 99], we have the data graphically in this paper rather than in the previous tabular format. For these two diagrams, the label “Poll” with a rate indicates the clocked interrupt service rate, that is, how many times per second the device status is checked. 0.4Khz means that the device is checked 400 times per second. There is considerable variability in performance, and this is relatively more important for small bu?er sizes, as the performance for large bu?ers will be dominated by data transfer limits.

Throughput

1

2

4

8

16

32

64

128

256

Trad.intr

Poll

Poll.500Hz

Poll.1KHz

Poll.2KHz

Poll.4KHz

Poll.2.5KHz

240 220 200 180 160 140 120 100 80 60 40 20 0

Throughput

1

2

4

8

16

32

64

128

256

Socket Buffer Size (KB)
Trad.intr
Poll
Poll.500Hz
Poll.1KHz
Poll.2KHz
Poll.4KHz
Poll.2.5KHz

3.3

Figure 5: Throughput versus clocking, loaded machine It is clear from these results that at high polling rates, the clocked interrupt scheme is able to keep up with the traditional interrupt scheme, which is almost everywhere the best performer, with the exception of polling, which does best for small packet sizes. In a lightly-loaded environment, interrupts would appear to be the best solution, except for some anomalous, but repeatable results which show polling best for
ACM SIGCOMM Computer Communications Review 34

Related and Follow-On Commercial Impact

Work;

The work by Ramakrishnan [Ramakrishnan 93] on “receive livelock” pointed out a real problem with O.S. management of interrupts on fast network adaptors. While Ramakrishnan studied FDDI, the basic problems of an operating system entering a completely interrupt-driven state were applicable to ATM, and where SAR was not done in hardware (as in ?rst generation ATM host interfaces from Fore Systems, which did SAR in software), could be far worse than for FDDI. Mogul and Ramakrishnan [Mogul 97]
Volume 32, Number 5: November 2002

noted that clocked interrupts were immune from such considerations, but developed a hybrid architecture, which was interrupt-driven under light load, but switched to polling when a certain threshold of load was passed. A large and in?uential body of work at the University of Cambridge [Black 95, Roscoe 95, Hyden 94, Leslie 96] was driven by the need to support multimedia. The resulting Nemesis operating system had many features, including Black’s scheduling scheme [Black 95] and its architecture as a single address space operating system [Roscoe 95] which enabled high-performance. In many ways this operating system was well-suited to the ?ne-grained resource multiplexing of which ATM was capable. This is not surprising, as a variety of ATM technologies had their origin at Cambridge in, or slightly before, this period. The most important derivative work was done by Peter Druschel. In his work on Soft Timers [Aron 00], he con?rmed that clock-driven activity was a powerful paradigm for networking subsystems. In a heavily multiplexed subsystem, Morris [Morris 99] demonstrated the value of a polling-like scheme, supporting the basic analysis of traditional interrupts versus polling we presented above. The Click router has had direct commercial impact, as it has been productized by Mazu Networks, Inc.

nalling, both for processing of network tra?c and for delivery of that tra?c to host applications. If there is a single lesson to take home from this paper, it is that the ATM technology served as a vanguard to force a rethinking of operating system architecture that might otherwise have been delayed until today, and while operating systems continue to evolve, the e?ects of this rethinking have already been felt.

5

Acknowledgments

I appreciate the great work of my former graduate students Brendan Traw, Je?rey Chung, Klara Nahrstedt, Michael Massa, John Sha?er, and Scott Alexander which pushed the state of operating systems for networks ahead considerably. I learned a good deal about hardware working with Brendan Traw and Bruce Davie; I hope they learned some roughly equivalent amount about system software. I also appreciate the insightful comments of Craig Partridge on both a variety of technical points and their presentation in this paper. I apologize in advance to anyone whose work I left out; the paper was not intended as a comprehensive survey.

4

Conclusions

References
[Alexander 94] D. Scott Alexander, C. Brendan S. Traw and Jonathan M. Smith, “Embedding High Speed ATM in UNIX IP” USENIX High-Speed Networking Symposium, Oakland, CA pp. 119121 (August 1994) [Aron 00] M. Aron and P. Druschel, “Soft timers: ef?cient microsecond software timer support for network processing”, ACM TOCS 18(3), pp. 197-228 (2000). [Bakoglu 90] H. B. Bakoglu, G. F. Grohoski and R. K. Montoye, “The IBM RISC System/6000 processor: Hardware overview”, IBM Journal of Research and Development, 34(1), pp. 12-22 (January, 1990). [Banks 93] D. Banks and M. Prudence, “A HighPerformance Network Architecture for a PARISC Workstation,” IEEE JSAC, 11(2), pp. 191202 (Feb. 1993).
Volume 32, Number 5: November 2002

In our discussion of changes in operating system technology, we noted that RISC architectures relied heavily on caches to overcome mismatches in speed between CPUs and DRAMs. Bu?er copying tracks DRAM performance rather than base processor performance. In the network attachment arena, the small ATM cell size of ca. 50 bytes took about 3 microseconds to arrive at 130 Mbps; 1500 bytes arrives in 12 microseconds at 1 Gbps and 1.2 microseconds at 10 Gbps, or within a rough order of magnitude of the ?gures with ATM in the early 1990s. We have shown in this paper how operating systems were revamped to meet the challenges posed by the ATM networks of the early 1990s, and as the paragraph above illustrates, those challenges have not retreated but have in some sense regrouped and reappeared. At the same time, the use of the Internet to bear various forms of multimedia, such as voice and streaming media, has again required operating systems [Muir 01] to examine scheduling and event sigACM SIGCOMM Computer Communications Review 35

[Black 95] R. J. Black, “Explicit Network Scheduling”, Ph.D. Thesis, University of Cambridge, (April 1995). [Borman 89] D. A. Borman, “Implementing TCP/IP on a Cray Computer”, ACM Computer Communications Review, 19(2), pp. 11-15, (April 1989). [Chu 96] J. Chu, “Zero-Copy TCP in Solaris”, Proceedings, 1996 USENIX, pp. 253-264 (January 1996). [Chung 95] J. D. Chung, C. B. S. Traw and J. M. Smith, “Event-Signaling within HigherPerformance Network Subsystems,” Proceedings, HPCS ’95, Mystic, CT, pp. 220-225 (August 1995). [Clark 90] D. D. Clark and D. L. Tennenhouse, “Architectural Considerations for a New Generation of Protocols”, Proc. SIGCOMM 1990, Philadelphia, PA (September 1990). [Clark 93] David D. Clark, Bruce S. Davie, David J. Farber, Inder S. Gopal, Bharath K. Kadaba, W. David Sincoskie, Jonathan M. Smith, and David L. Tennenhouse, “The AURORA Gigabit Testbed,” Computer Networks and ISDN Systems 25(6), pp. 599-621, North-Holland (January 1993). [Computer 90] IEEE Computer Sta?, “Gigabit Network Testbeds,” IEEE Computer, 23(9), pp. 7780 (September 1990). [Dalton 93] C. Dalton, et al., “Afterburner: A network-independent card provides architectural support for high-performance protocols,” IEEE Network, pp. 36-43 (July 1993). [Davie93] Bruce S. Davie, “The Architecture and Implementation of a High-Speed Host Interface”, IEEE JSAC 11(2), pp. 228-239 (Feb. 1993). [Druschel 93] Peter Druschel and Larry Peterson, “Fbufs: A high-bandwidth cross-domain data transfer facility”, Proc. SOSP, 1993.

[Druschel 96] Peter Druschel and Gaurav Banga, “Lazy Receiver Processing (LRP): A Network Subsystem Architecture for Server Systems”, Proc. OSDI, pp. 261-275, 1996. [Edwards 94] A. Edwards, G. Watson, J. Lumley, D. Banks, C. Calamvokis and C. Dalton, “Userspace protocols deliver high performance to applications on a low-cost Gb/s LAN,” in Proceedings, 1994 SIGCOMM Conference, London, UK, 1994. [Edwards 95] Aled Edwards and Steve Muir, “Experiences implementing a high-performance TCP in user-space”, in Proceedings, ACM SIGCOMM Conference, Cambridge, MA, pp. 196205, (August-September 1995), [Engler 95] D. Engler, M. F. Kaashoek, and J. O’Toole, “Exokernel: An Operating System Architecture for Application-Level Resource Management”, Proc. SOSP, December 1995. [Hyden 94] E. Hyden, “Operating System Support for Quality of Service”, Ph.D. Thesis, University of Cambridge (February 1994). [IND 95] Hewlett-Packard Information Networks Division, “Netperf: A Network Performance Benchmark (Revision 2.0)”, February 15, 1995. [Leslie 96] Ian M. Leslie, Derek McAuley, Richard Black, Timothy Roscoe, Paul T. Barham, David Evers, Robin Fairbairns and Eoin Hyden, “The Design and Implementation of an Operating System to Support Distributed Multimedia Applications”, IEEE Journal of Selected Areas in Communications, 14(7), pp. 1280-1297, (1996). [McVoy 96] Larry McVoy and Carl Staelin, “lmbench: Portable tools for Performance Analysis”, Proceedings, 1996 USENIX Conference, San Diego, CA, pp. 279-294 (January 1996). [Mogul 97] J. Mogul and K. K. Ramakrishnan, “Eliminating Receive Livelock in an InterruptDriven Kernel”, ACM TOCS, 15(3), pp. 217252, 1997. [Morris 99] R. Morris, E. Kohler, J. Jannotti and M. F. Kaashoek, “The Click Modular Router”, Proc. SOSP, pp. 217-231 (1999).

[Druschel 94] Peter Druschel, Larry Peterson and Bruce Davie, “Experiences with a High-speed Network Adaptor: A Software Perspective”, [Muir 01] Steve Muir, “Piglet: An Operating System Proc. ACM SIGCOMM, pp. 2-13, (Augustfor Network Appliances”, Ph.D. Thesis, CIS DeSeptember 1994). partment, University of Pennsylvania, 2001.
ACM SIGCOMM Computer Communications Review 36

Volume 32, Number 5: November 2002

[Nahrstedt 96] K. Nahrstedt and J. M. Smith, “Design, Implementation and Experiences of the OMEGA End-Point Architecture”, IEEE JSAC 14(7), pp. 1263-1279 (September 1996). [Patterson 02] D. A. Patterson and J. L. Hennessy, “Computer Architecture: A Quantitative Approach (3d Ed.)”, Morgan Kau?man, 2002.

[Traw 91] C. Brendan S. Traw and Jonathan M. Smith, “A High Performance ATM Host Interface for ATM Networks”, Proceedings, ACM SIGCOMM Conference, Zurich, SWITZERLAND, pp. 317-325 (September 1991).

[Traw 92] C. Brendan S. Traw and Jonathan M. Smith, “Implementation and Performance of an ATM Host Interface for Workstations”, Proceed[Ramakrishnan 93] K. K. Ramakrishnan, “Perforings, IEEE Workshop on the Architecture and Implementation of High-Performance Commumance Considerations in Designing Network Interfaces,” IEEE JSAC 11(2), pp. 203-219 (Feb. nications Subsystems (HPCS ’92), Tucson, AZ, 1993). pp. 101-104 (February 1992). [Roscoe 95] T. Roscoe, “The Structure of a MultiService Operating System”, Ph.D. Thesis, University of Cambridge (August 1995). [Sha?er 96] John H. Sha?er, “The E?ects of HighBandwidth Networks on Wide-Area Distributed Systems”, Ph.D. Thesis, University of Pennsylvania, 1996. [Simmons 90] M. L. Simmons and H. J. Wasserman, “Los Alamos Experiences with the IBM RS/6000 Workstation”, Technical Report LA-11831-MS (March 1990). [Smith 90] Jonathan M. Smith, “UPWARDS Operating System: Goals and Relevance to Supercomputing,” Lawrence Livermore Laboratories/IDA Supercomputing Research Center Workshop on Supercomputer Operating Systems, Livermore, CA (July 10-12 1990). [Smith 91] Jonathan M. Smith and David J. Farber, “Tra?c Characteristics of a Distributed Memory System”, in Computer Networks and ISDN Systems, 22(2), September 1991, pp. 143–154. [Smith 93] Jonathan M. Smith and C. Brendan S. Traw, “Giving Applications Access to Gb/s Networking,” IEEE Network 7(4), pp. 44-52, (July 1993). [Smith 99] J. M. Smith, J. D. Chung and C. B. S. Traw, “Interrupts”, Encyclopedia of Electrical and Electronics Engineering, Volume 10, Wiley(1999), pp. 667-673. [Thompson 78] K. L. Thompson, “UNIX Implementation,” The Bell System Technical Journal, 6(2), pp. 1931-1946, (July-August 1978).
ACM SIGCOMM Computer Communications Review 37 Volume 32, Number 5: November 2002

[Traw 93] C. Brendan S. Traw and Jonathan M. Smith, “Hardware/Software Organization of a High-Performance ATM Host Interface,” IEEE JSAC 11(2), pp. 240-253 (Feb. 1993). [Watson 87] Richard W. Watson and Sandy A. Mamrak, “Gaining E?ciency in Transport Services by Appropriate Design and Implementation Choices” ACM Transactions on Computer Systems, 5(2), pp. 97-120 (May 1987).

ACM SIGCOMM Computer Communications Review

38

Volume 32, Number 5: November 2002

A Taxonomy and Design Considerations for Internet Accounting
Michel Kouadio* mkouadio@acm.org
(* Corresponding Author)

Udo Pooch pooch@cs.tamu.edu

Dept. of Computer Science, Texas A&M University, 501B Harvey Bright Bldg., College Station TX. 77843-3112.

ABSTRACT
Economic principles are increasingly being suggested for addressing some complex issues related to distributed resource allocation for QoS (Quality of Service) enhancement. Many proposals have been put forth, including various strategies from Pricing Theory and market-based insights for security in the Internet. A central need of these endeavors lies in the design of efficient accounting architecture for collecting, storing, processing and communicating relevant technical information to parties involved in transactions. This paper proceeds to a systematic classification of the major characteristics of accounting models with the aim of highlighting important features to optimize for building effective architectures.

Categories and Subject Descriptors:
C.2. Computer-Communication Networks. C.2.3. Network Operations: Network Management, Network Monitoring. C.2.4. Performance of Systems: Design Studies, Measurement Techniques. C.2.5. Local and Wide-Area Networks: Internet.

General Terms:
Measurement, Economics, Management.

Keywords:
Accounting Architecture, Pricing, Classification.

1. INTRODUCTION
The development of protocols for resource request and allocation is central to QoS provisioning efforts on the Internet. Two major architectures and protocols have been proposed to allow users to negotiate the availability and reservation of resources prior to initiating transactions. The first was the Integrated Services Networks (IntServ) with the Reservation Setup Protocol (RSVP) [3], [36], and [43]. The

second, the Differentiated Services Networks (DiffServ), requires that users negotiate a Service Level Agreement (SLA) that provides upfront their traffic expected profile and terms of service provision with the network [2], [29]. In DiffServ, SLA is negotiated through a Bandwidth Broker (BB), which is an entity in a domain that keeps track of all resource allocated, and accepts or rejects new requests accordingly. BB is also designed to cooperate with its peers in other domains to confirm resource availability from source to destination. In recent years, economic models of network management have emerged as complements to these architectures, or alternative frameworks purporting to contribute flexible solutions to distributed resource allocation issues and enhance QoS. Network economic approaches are fundamentally frameworks based on Game Theory and Pricing Theory that require resource owner (producer) to set “rules of the game” and leave to each user (consumer) the selection of an algorithmic behavior that optimizes his utility [9], [16], and [44]. Pricing studies generally posit that putting a price tag on network services will moderate and lead to self-regulation in user requests, thus ultimately resulting in the equilibrium of supply and demand of resources. Application of economic principles to network operations introduces specific challenges encompassing modeling, computational complexities and user-network interactions. How to operate a network by auctioning resources? What signaling protocol may allow users and networks to exchange information on resource supply and demand to sustain tight real-time QoS constraints? Efficient accounting mechanisms should therefore play an important role in this picture by appropriately providing the necessary technical information to assess resource availability and support different charging policies. We define an accounting architecture as the set of components for monitoring resource availability, and for collecting, storing, processing and communicating various parameter data that define user QoS profile and consumption of network resources. This paper investigates issues in the design of accounting architecture that may be used to support economic models of network management. In Section 2, we highlight the relationship between accounting and pricing. Section 3 provides a review of some of the main accounting studies found in the literature. Next, in Section 4, we propose six main criteria around which to organize and understand accounting models. Then we go on from Sections 5 through 10, to explore the implications of each of these characteristics from an overall performance and efficiency perspective. We wrap up our classification in Section 11, by stressing important design considerations and elements to optimize for building an effective accounting architecture.

ACM SIGCOMM Computer Communications Review

39

Volume 32, Number 5: November 2002

2. ACCOUNTING AND PRICING
A great deal of research in economic models for the Internet has concentrated on pricing policies and strategies. Tutorials on pricing and the economics of networks may be found in [10] and [19]. General surveys of pricing models are conducted in [11], and recent trends in charging studies for Integrated Internet Services are reviewed in [40]. While pricing studies deal mainly with policy and charging strategies, they are closely dependent on accounting architectures and protocols for collecting, processing and communicating the supporting technical data. Hence, accounting architecture appears to be an enabling technology for economic-based resource allocation and management in networking. Figure 1 presents the relationships between pricing model, accounting architecture and the network. As an example, pricing strategies such as auction and dynamic pricing require that the underlying accounting monitor the availability of resource and communicate relevant information to parties involved in the transaction (e.g. network and user agents). Pricing policies and accounting mechanisms have reciprocal influences. Accounting architecture and protocols determine the scope of feasible pricing models, and pricing models set out features and requirements for accounting. IETF (the Internet Engineering Task Force) has created a working group in Authentication, Authorization and Accounting (AAA) to investigate some of the issues involved [1], [5], [6], [31].

3. REVIEW OF ACCOUNTING STUDIES
This review includes explicitly designed accounting models as well as some “implied” architectures put forth as part of pricing studies. Indeed, there is a natural interplay between pricing and accounting; and these fields being relatively new, their terminology is still evolving and is not standard in all studies.

3.1. Accounting for Opt imal Pricing Models
Optimal pricing models aim to achieve maximal efficiency in the distribution of resources and maximal welfare in the use of network resources. They form the bulk of recent research in pricing and most are based on Game Theory [42]. The theoretical economical foundations of optimal pricing models is explained in [27] and [39]. Optimality refers to the perfect equilibrium of the supply of network resource and the demand by users, due to the regulating effect of the pricing strategy. Basically, the network is modeled as a supplier of QoS provisioning resources (bandwidth, buffer etc.), and users as consumers, are represented by agents, each endowed with a budget. The repeated interaction between the network advertising its resources (lightly loaded, overloaded etc.), and competing users adapting their strategies to optimize their QoS allocations is bound to reach an optimal point of convergence where each user is most satisfied with his gain and has no incentive to deviate for another QoS profile [16] and [24]. Example proposals are introduced in [9], [25], [30] and [44]. Typical strategies to reach optimality include dynamic pricing of congestion and auction [26], [28] and [34]. There is a diverse body of accounting mechanisms intertwined with these pricing models, to provide the architectural support. The architectures are generally not explicitly defined in these studies, but rather implied by the charging strategies. They share some common characteristics that follow from their features:

PRICING MODELS Auction, Static Pricing, Dynamic Pricing, Priority Pricing, Time of the Day Pricing

1. Resource monitoring: each network element (e.g. router,
switch, and server) is endowed with mechanisms to collect data on aggregate resource consumption and availability (bandwidth, buffer, CPU), and sets conditions for release to users accordingly.

ACCOUNTING Traffic Measurement, Transaction Record Processing, Resource “Supply” Monitoring, Communication of Control Information

2. User-network signaling:

NETWORK Data Transmission, QoS Provisioning Resources

there are typically two options that include interactive signaling like those used for auction models, or a one-way dynamic price advertising from the network. In the first option, a communication protocol allows network elements to advertise resource availability and current clearance conditions. Users submit resource requests and possibly their utility (valuation of transaction). The interaction continues until supply equals demands. The second option involves only the network setting clearance price and simply feeding it back to users who then may choose to adapt their QoS parameters accordingly. That was the option used in the network game simulator built at Microsoft Research and Cambridge [18] and [20]. The signaling load is often an issue with these models because of the frequent exchanges between users and networks, especially for auction-like strategies.

3. Data collection: typically data sent by users is measured in
each network node and rated against the clearance price, based on the local resource availability conditions. At issue is the scalability of these mechanisms and their real-time performance when multiple nodes are involved from source to destination.

Figure 1: Layered Presentation of Pricing, Accounting and the Network.

ACM SIGCOMM Computer Communications Review

40

Volume 32, Number 5: November 2002

4.

accounting architectures designed for these models may in principle work with most of QoS-enhanced protocols. Furthermore, they may be seen as alternatives to IntServ (RSVP) and DiffServ models of resource allocations. Reservation and classes of service are superseded by dynamic user appropriation of resources based on price level; therefore each application may be viewed as having their own class of service and continuously reserving the resources that they need. However, the communication model supported is unicast and does not extend to multicast.

Network models:

The significance of this architecture is best understood in relation with some popular activities on the Internet, such as web browsing, or emerging multimedia applications, such as videoconferencing and video-on-demand. As a matter of fact, in these cases, it is natural that pricing models target receivers of transactions, instead of charging the sender only. It is then important that accounting architectures provide mechanisms to support such cost sharing.

3.4. Internet Demand Experiment (INDEX)
Developed at UC Berkeley, INDEX is a field experiment that provides an architecture for charging and billing users for Internet traffic [12], [32]. The primary goal was to study user reaction to different QoS and usage sensitive pricing, as opposed to the currently flat pricing system used in the Internet. That study proposes exact data measurement over sampling for charging purposes to enhance credibility of collected data to users. The system is made up of many components. Users are equipped with a security agent that authenticates operations with the network and a purchasing agent that makes payment decisions. At the network entry point sits a billing gateway, a dedicated device such as a router that provides transaction metering and consolidates accounting records. An access controller coordinates user authentication procedures. That architecture can support different static charging models, and provides a way to select which of the sender or the receiver to account for by explicitly asking confirmation from each end-user involved before allowing a transaction establishment. It deals with unicast traffic and does not support multicast. It is designed to work in the traditional Internet and does not extend to IntServ or DiffServ.

3.2. Edge Pricing Architecture
In an attempt to deal with the practical scalability and flexibility issues of the accounting structures of optimal pricing models, Shenker suggested an architecture paradigm aimed at making accounting local to each network provider [35]. It is of interest to note that the induced architecture of optimal pricing models may require that uniform accounting mechanisms be implemented in different network domains. Such close inter-dependencies limits the flexibility that each network provider would have in the selection of different accounting schemes and charging models. The main idea of the Edge Pricing architecture is to advocate that all accounting mechanisms be set up at the edge of each provider network, and appropriate cost approximations be performed to support different pricing models. Such approximations include the expected congestion conditions and traffic path from source to destination. That architecture fosters interconnection agreements between network providers, and has the advantage of breaking down the accounting complexity into local issues. The design approach is intended to provide flexibility in the scope of charging models that may be supported by each network domain. Still, the Edge Pricing architecture is more a design framework than a detailed accounting model. It does not address either detailed data collection method, or data communication between parties. It left as open issues how to support models that charge receivers and multicast, which are not local issues to each provider.

3.5. Generic Charging and Accounting (GenCA)
Departing from accounting schemes that are designed to support a few specific pricing models, Hartanto and Carle proposed a policy-based configurable accounting architecture for the European Information Infrastructure and Services Pilot, also known as SUSIE [21]. Their study developed a general architecture and billing system framework made of the following layers and functions: Metering Layer: tracks and records usage of resources. Collecting Layer: accesses data provided by meters and forwards them to accounting entities. Accounting Layer: consolidates the collected data into accounting records. Charging Layer: assesses costs of usage from the accounting records. Billing Layer: collects all charges for a customer over a time period and creates a bill. In that framework, each new transaction by a user triggers the retrieval of his profile from a policy database to collect accounting and charging related parameters. These parameters are sent to metering entities to collect data relevant to the charging formula from the contract between the user and the provider. Typical parameters include volume, bandwidth, priority and duration. The data collected is sent to accounting consolidation entities to form records that later serve for charging. GenCA accounting model is flexible and adaptable. Each user may have a custom-charging and service level agreement contract with a provider, and the accounting system is configured to measure, record and process traffic parameter data for the QoS resources in that contract. The system can support Integrated Services and Differentiated Services Networks. Provisions are made to support both unicast and multicast. That accounting model is bound for implementation in some European countries.

3.3. Zone -based Cost Sharing Model
Clark is one of the first to consider cost sharing between sender and receiver [8]. The proposed accounting architecture recommends that the Internet be subdivided into zones where service would be provided at a uniform, distance-insensitive way. Zones might be site, city, region or country. Both sender and receiver would exchange signaling information on the zones for which they are willing to pay. That information is to be put into each packet header by the sending source when transmission starts. Each router is to be configured to examine the packet header to determine if any of the sender or the receiver is willing to pay for QoS resources in the zone where they are located, and to perform the relevant traffic metering. Therefore the accounting involves willingness-to-pay signaling messages, payment aware packet header and traffic measurement in routers along the path from source to destination. In the case of multicast, in order to limit the load of signaling messages from receivers to the source, routers in the zone where the sender has expressed interest in paying, provide enhanced services and simply forward the packets. Then, as packets leave the sender-paying zone, routers in subsequent zones would mark packets to explicitly request from receivers whether they are willing to pay for enhanced services. Each receiver would be equipped with an agent “Receiver Traffic Meter” that makes decision on packet payment for zones of interest and would respond to such demands.

ACM SIGCOMM Computer Communications Review

41

Volume 32, Number 5: November 2002

3.6.

CATI (Charging and Accounting Technologies for the Internet)

4. CHARACTERIZING ARCHITECTURES FOR INTERNET ECONOMICS
Accounting models for network economics differ by many characteristics. The design principles, parameters handled and components involved are crucial to the overall efficiency of each model. A taxonomy provides a general picture that helps highlight main model components, patterns and possible points that deserve more attention and efforts. Accounting models may have many characteristics and this taxonomy, although broad is not meant to be exhaustive. Remember that accounting characteristics may be as broad as the set of architectural requirements of all conceivable pricing models. Still, we believe that the most recurrent characteristics can be classified in six major concepts: 1. Policy scope: describes the different charging policies and economic principles that may be directly supported, or with minor adaptation, by the architecture. That often results from the design approach. 2. Source of data collection: specifies where in the network data is collected to feed the accounting system. 3. Methods of data collection: is a concept for understanding the granularity of data collection. 4. Collected elements: refers to the different kind of data measured and provided by the accounting model; this provides insights in the kind of charging and pricing policies that may be supported. 5. Interactivity: determines whether the accounting model has any provision to allow users to submit various parameters such as their valuation of utility and prices, or if all rules and parameters are set by network providers. 6. Supported network protocols: indicates the scope of enhanced network service protocols and thus environments where the accounting system may operate. Figure 2 synthesizes the classification of these characteristics, while Sections 5 through 10, provide further explanations.

CATI is a project developed in Switzerland as part of a charging program on Electronic Commerce transactions initiated by the Swiss National Science Foundation [17]. The accounting scheme encompasses many network protocols including Integrated and Differentiated Services Networks, ATM and MPLS. CATI accounting model uses pre-defined user profiles that contains default information on: ? Sender identity ? Default IP provider ? Payment method ? Invoice/billing information ? Default QoS ? Default cost-sharing scheme Users have the opportunity to change some of the default parameters in their configuration file before initiating a transaction. Two components are used in a network provider domain: Internal Service Broker (ISB) that manages service local to the provider and External Service Broker (ESB) that negotiates service with neighboring domains. Service Level Agreements (SLA) between a provider and his internal users or his peer providers are negotiated in form of volume of traffic, duration and price before the start of a session and can be dynamically updated. Accounting signaling is performed through an extended RSVP protocol. The extension includes new objects on pricing scheme, identity of the payer of the transaction (e.g. sender or receiver), bidding fields where auction is applicable, fields for the type of service requested, and network provider information. The new RSVP objects extensions allow for example the implementation of auction pricing models by the use of bidding fields. That architecture was also used to implement dynamic pricing models between network providers, or Service Level Agreement Trading (SLAT), for an automatic negotiation of traffic volume for interconnection agreement.

3.7. Accounting and Charging Multicast
Herzog suggested a distributed architecture called “One Pass Accounting”, consisting of an accounting message that flows from the source through the multicast tree [22]. As the message traverses the tree, multicast nodes allocate costs to connected members. The accounting scheme of this approach requires the configuration of each network node in the multicast tree for running the costing algorithm. It is designed to support charging models based on link costs, and therefore this study appears to be more relevant to integrated network environments with the RSVP protocol that works with pre-determined paths. This architecture may not easily be extended to support other network models, such as DiffServ, where traffic path may vary. Overall, a link-by-link accounting mechanism may appear limited in flexibility and scalability, due to the complexity of node configuration. Another multicast accounting architecture was proposed as an extension of the Generic Accounting Architecture [7]. This model sets up metering devices in edge nodes and all multicast routers of each domain. For a given multicast session, data collected in these meters is fed back to the traffic sender provider domain where the accounting server proceeds to a consolidation and compute the allocation share of each participant. In both studies, the accounting architectures are designed to work across domains, on the whole multicast tree, which require somehow uniform mechanisms and inter-domain standards.

5. POLICY
The scope of charging policies supported by an accounting architecture is typically determined by its design principles. Accounting models may thus be subdivided into two major groups: those that are driven by charging and pricing policies, and those that start from architectural grounds.

5.1. Close-Policy Accounting Models
Most of the works reviewed in the Section 3, start with investigating some specific pricing policy to eventually reach an accounting model that may support the proposed model. This may be considered a topdown approach or accounting driven by pricing-policy. Specific economic principles or pricing policy permeate the architecture and therefore the scope of policies, which it may directly support, is limited to those it embodies. Such accounting systems can readily support the pricing model and policy they relate to. However, they are generally not very flexible insofar as substantial effort may be needed to adapt them to support other policies. Whether they are centralized or distributed, their design entails the support of a limited set of policies. That may be particularly so, if the model implementation involves multiple network nodes. Obviously, adapting the accounting mechanisms in all nodes involved to support other policies may be demanding for an internetwork the size of the

ACM SIGCOMM Computer Communications Review

42

Volume 32, Number 5: November 2002

Unicast

Multicast

Close policy

Open policy

Diffserv (No Reservation)

Intserv -RSVP (Reservation)

User Input

Provider Centric

Policy Scope

Network Protocols

Interactivity

AC C O U N T I N G

MODELS

Sources Data Collection

Collection Methods

Collected Elements

Core Network

Edge Node

Precise

Approximation

Duration

Volume

Node Resources

Distance

Sender Side

Receiver Side

Figure 2: Taxonomy of Accounting Architecture Characteristics.

Internet. Hence, these models lean towards uniformity in accounting and policy across the Internet. Such models may be called close-policy accounting models, because by virtue of their design, they are more or less explicitly geared to support one or a fixed set of policies. They may require, depending on the policies that they embody, minor or substantial change in the network architecture for their implementation. Examples include the induced accounting model of Smart-Market [28], One-Pass Accounting protocol for multicast suggested in [22], and some architectures for auctions and optimal pricing models [18] and [26].

example of this category [35]. It recommends an architectural design that would allow every provider to implement at the edge of his network a local accounting suitable to his economic policies and leaves inter-domain accounting to interconnection agreements. Other examples that may be viewed as open-policy accounting include Arrow [15], CATI [17] and Generic Charging and Accounting (GenCA) [21].

6. SOURCES OF DATA COLLECTION
An important aspect of an accounting model lies in the source of data collection. That is typically carried out in the edge or the core of the network, and may target one side of the transaction.

5.2. Open-Policy Accounting Models
Accounting architecture may be independent of any specific pricing policy. Such model may be general so that a wide variety of economic models may be built on top of it. The scope of the pricing models supported, represents an important element that determines the flexibility of an accounting model. Accounting models whose design start by investigating architectural issues may be viewed as using a bottom-up approach. The advantage of such architecturaldriven accounting models is that they fully integrate network architecture and protocol from the start. However, being independent of any specific policy, they may require systematic though limited adaptation work, in order to support any particular economic model. Since they generally provide a flexible foundation for supporting multiple pricing models, we will describe them as open-policy accounting models. Edge-Pricing architecture is an

6.1. Network Nodes
6.1.1. Network Core
This requires the configuration of multiple, if not all network nodes (routers/switches) in a domain or the Internet. This approach has the advantage of providing very detailed measurements at all stages of the network topology. It may provide a basis for dynamic pricing models that are based on the general network status, the actual path of traffic and multicast cost allocation schemes that assess imputations on a link basis. However, it does not scale well and it may bring more complexity in the engineering of the network. The overhead incurred may be very high and that may adversely affect network performance. Systems based on this approach may be involved as far as implementation, maintenance and upgrade are concerned. They are not very flexible, because any change in the

ACM SIGCOMM Computer Communications Review

43

Volume 32, Number 5: November 2002

mode of operation requires change in each node. Examples of accounting models that require data collection in the core of the network include the induced accounting models of Smart-market [28], congestion-based optimal pricing models [33], and that of “Link Weighting” charging model [13].

7.1. Precise-Collection
The accuracy and fine-grained collection of cost elements is important for providing a full picture of resource consumption to users and help providers assess the availability of resource supply. Yet, the accuracy of the collection adds up to the complexity of the accounting system and increases the overhead in the computational load brought onto the system, especially if the data collected is the packet volume of traffic or congestion status [4], [21].

6.1.2. Network Edge
Data is collected from some few nodes that serve as interfaces between users and the rest of the network, typically ingress or/and egress nodes. All accounting and pricing decisions may thus be managed at that local level. That leaves the internal structure of the network less complex with no additional overhead. However, this approach does not provide enough detailed elements on operations involving inner nodes such as multicast branching points and congestion bottlenecks. In general, it does not readily provide useful information for pricing and cost allocation to be applied to receivers. A typical example is Edge-Pricing architecture [35].

7.2. Approximation
Traffic measurements may be approximated to avoid costly accurate collection. Sampling may be used to that purpose, by exploiting statistical properties of traffic. Data is collected at various frequency intervals and extrapolated to determine the approximate resource consumption of each user. Sampling is typically used for volume of traffic, the packets sent over the network. The main limitation of sampling stems from its inability to provide a detailed figure of transactions, which may be necessary in case of disagreement between providers and users. Approximation may also take the form of estimating user consumption from overall parameters of a negotiated SLA. The concept of effective bandwidth is a case in point [23] and [37].

6.2. Side of Data Collection
The source of data collection may further be concerned with the side of transaction where elements are collected; that may lie with either the sender or the receiver. The implications of this architectural decision have a direct impact on pricing policies that may thus be supported.

8. COLLECTED COST OBJECTS
The collected cost objects provide a measurement of the resources to be charged for. There may actually be a great variety of elements to be collected based on the potential range of charging policies. In this sense, close-policy accounting models have the advantage of narrowing down these elements since they are designed to support specific policies. Open-policy models that are general and not designed to support explicit policies may collect more elements than necessary in many instances, and may need proper configuration to avoid needless overhead. Still, from an architectural viewpoint, there are commonly selected elements that are very representative of those found in most accounting models: duration, volume, distance, and node resources. A combination of several of these elements may be found in an accounting architecture proposal. A. Duration: this refers to measurement for the length of time that traffic from a given source uses the network resources. It is more applicable to reservation-based transactions such as RSVP in IntServ, where it is easier to predict the amount of resources used per unit of time. In DiffServ, accounting for duration may also suit transactions in “Expedited Forwarding” class, which provides virtually no delay. Collecting traffic duration is easy to carry out with only a modest level of overhead. B. Volume: the count of bytes or packets sent over the network during a session by a transaction is a commonly collected cost object. Contrary to duration measurement, volume metering involves dealing with the actual load put on the network. Measuring volume may require detailed metering, which may be costly from an overhead perspective. Volume-based accounting is used in NZGate [4]. In practice, a combination of volume and duration is quite frequent in the form of rate (i.e. Rate=Volume/Duration). C. Distance: this generally represents the number of hops traversed by packets from source to destination. Distance may be evaluated from the network topology. Geographical information and IP address may also be used, although Internet address structure is

6.2.1. Sender Side
Accounting on the sender side is the most popular form found in the literature. It has the advantage that information about the originator of the traffic is readily available to the network provider before any transactions take place. That also helps support pricing systems with built-in incentives for efficient network resource usage at the source of transmission, and auction models that require frequent reactions from the traffic sender. The main limitation of accounting on the sender side lies with the difficulty of dealing with charging models involving protocols such as multicast where costs are to be distributed among all participants (receivers), and require collecting information on both sides. Examples of this category include the accounting architectures of auction models [26], [34], that of INDEX [32], and Edge-Pricing architecture [35].

6.2.2. Receiver Side
Setting up accounting mechanisms on the side of the receiver of Internet transactions, is an option mostly used in multicast studies. Accounting on receiver sides is also used in unicast models that suggest ways to charge the traffic initiator. The difficulty of such systems is that in most cases, receiver information is only available in a remote region or domain, and it is not readily available for use where the traffic starts. Accounting mechanisms may therefore involve significant signaling and trusted relationships among Internet Service Providers etc. An example of such models may be found in [38]. Zone-based Cost Sharing architecture [8] and GenCA [21] also have provisions for accounting on the receiver side.

7. METHODS OF DATA COLLECTION
The methods used to collect data are important to accounting models, because different approaches determine the granularity of the collected elements and have implications on audit capacities, as well as the production of billing records. A good design must minimize the level of complexity and overhead that its implementation may incur.

ACM SIGCOMM Computer Communications Review

44

Volume 32, Number 5: November 2002

generally not directly expressive. Another m ethod for distance evaluation involves the exploitation of IP packet TTL (Time To Live), which is decremented anytime that a packet crosses a router. Distance evaluation for accounting is used in [13]. D. Network Node Resources: packets need to use some amount of node resources (CPU and buffer) in order to meet QoS requirements such as low delay, low jitter and specific Per Hop Behavior (PHB) in DiffServ. There are accounting models that collect the usage of those elements, to typically support routing optimization policy, congestion control and distributed resource allocations [14], [33].

B. Multicast: accounting methods for this mode require a distributed collection of information on many users. However, the identity of participants is not directly provided by standard multicast protocols. Heterogeneous QoS requests and traffic merging over shared trees, require that a method be devised to collect and consolidate accounting data in order to determine the cost to be attributed to each user. Multicast accounting models are proposed in [7] and [22].

10. INTERACTIVITY
Communication among users on one hand, and between users and the network on the other, may be indispensable in some approaches and therefore various parameters need to be exchanged. For instance, charges may be negotiated or determined solely on the basis of the cost elements collected. The interactivity component of an accounting system provides the opportunity to exchange custom information. A. User input: users may submit their valuation of utility and reach an agreement through interaction with the network provider. In this case, accounting protocols or mechanisms provide the necessary elements for collecting such inputs, process them and send feedback to users. User input may take various forms: a bid to have a transaction completed, adaptive resource requests such as a strategy in Game Theory or utility characterization. INDEX architecture [32], and CATI [17] have provisions for user input. The level of interactivity may be a source for overhead in the accounting scheme and deserves careful design. B. Provider-centric: accounting systems may operate solely from rules determined by providers, and standardized parameters are indiscriminately collected from traffic flows. The network provider is thus the only one involved in determining resource allocation policies and conditions. Such an approach has the potential advantage of reducing the level of signaling characteristic of interactive systems, and may have better performance. Yet, that approach limits user choices and self-optimization strategies. For example, the lack of interactive feature in accounting scheme may preclude implementation of auction like models.

9. SUPPORTED NETWORK PROTOCOLS
Accounting models may be designed for specific network protocols and environments. The two main Internet QoS protocols that have major different accounting requirements are IntServ (Integrated Services Networks) and DiffServ (Differentiated Services Networks). Along each of these network environments, the accounting architecture may also target unicast or multicast.

9.1. QoS Protocols
A. IntServ: accounting for Integrated Services Networks with the RSVP protocol involves dealing with reserved and guaranteed resources, and pre-determined paths. In such an environment, all traffic parameters are well known in advance (e.g. duration, volume, and class of service). Data collection is hence made easier. Therefore, these QoS reservation parameters may be collected for accounting purposes as soon as resource availability and reservation are confirmed. Examples of accounting models for Integrated Services networks include Arrow [15], OCIT [41], One-Pass Accounting [22]. B. DiffServ: in Differentiated Services Networks, resources availability is checked and confirmed either by Bandwidth Brokers or light-weight RSVP across domains. There is no formal reservation in the sense that these resources are made available to other traffic if and when they are not used. Therefore, in DiffServ data must be collected on the fly and that brings about more performance constraints. Accounting needs to be multiform to cope with the heterogeneous systems and policy requirements of the various interconnected domains. Since there is no strict reservation per se, and no guarantee of QoS provisioning, it is important to use various adaptation strategies to account for packets whose class of service gets demoted from one domain to another. Interconnection may therefore be more relevant and accounting models need to be flexible enough to accommodate all these strategies and policies. Some representative studies in this category may be found in [7] and [17].

11. DESIGN ISSUES
The design of accounting architecture and protocol needs to meet some important performance requirements. The taxonomy helps highlight some desirable characteristics. These may be very challenging to achieve in practice. Each proposal may show strengt h in some areas and limitations in some others. We further propose minimum engineering design requirements that should not be overlooked in order to optimize efficiency and effectiveness.

9.2. Communication Mode
The Internet has two major mode of transmission with very different accounting requirements. A. Unicast: most pricing studies have implicit accounting mechanisms for unicast. In this case, communication is on a one-toone basis and the identity of parties involved, is available in the packet header. Other information may be fairly easily collected.

11.1. Scalability
This characteristic of accounting mechanisms refers to the ability for a model to be extended to multiple network nodes, domains, users etc., without incurring any significant additional load or overhead. This feature is all the more important in a large and heterogeneous network like the Internet, that accounting systems should be able to handle the high growth in the user population and the domains. For example, an architecture to support dynamic pricing and auction, should reliably provide price information from

ACM SIGCOMM Computer Communications Review

45

Volume 32, Number 5: November 2002

and to users, most probably within some deadline. How to design a real-time, reliable communication mechanism to reach all users without much overhead? The characteristics of the taxonomy that are more relevant to scalability are the source of data collection and collected objects.

12. CONCLUSION AND FUTURE DIRECTIONS
In this paper, we investigated some of the main features of accounting architectures and how they contribute to overall efficiency. The features considered are not exhaustive; nevertheless they are very relevant in building effective accounting architecture. The insights provided by this taxonomy lay the ground for understanding and assessing models. The effectiveness and the efficiency of accounting models are crucial in implementing viable pricing and economic based resource allocation models in the Internet. The bulk of research in network economics has focused on pricing models, and accounting architecture is still in need of further investigations. The design of efficient accounting is all the more difficult that some of the design issues described in this paper are hard to optimize altogether. Design approach must hence perform some trade-off, and optimization may ultimately depend on the class of pricing models that are likely to be implemented in a specific domain or by a set of cooperating providers. We see multicast accounting as a fertile research area. As a matter of fact, multicast was designed to help improve network performance by having users share a single copy of QoS intensive applications. From an economic and game theoretic perspectives, users will cooperatively go for multicast, only if the cost allocation schemes allow clear saving over unicast. The support of equitable and incentive compatible cost allocation methods, requires detailed accounting of each user contribution to the global cost. The issues are that members are anonymous, have heterogeneous QoS demands; traffic is aggregated, the multicast tree topology has several splitting points where traffic diverges, and the tree crosses several domains under different administrative authorities. Hence, sophisticated accounting is important to capture the different cost relevant parameters in order to extract the share of each participant. It is still an open issue on whether, and how to make multicast accounting a local issue to each domain, so that each network provider may have more choice in the selection of their accounting model and cost allocation schemes. Guided by the considerations made in this paper, we designed a new token-based accounting architecture (TOKENAC), with the aim of optimizing several of the components that we identified. It is designed to s

赞助商链接

更多相关文章:
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图