Designing Networks for Tomorrow's Traffic
`
`by
`
`Henry H. Houh
`
`S.M.E.E. Massachusetts Institute of Technology {1991)
`B.S.Phy. Massachusetts Institute of Technology (1990)
`B.S.E.E. Massachusetts Institute of Technology (1989)
`
`Submitted to the Department of Electrical Engineering and Computer Science
`in partial fulfillment of the requirements for the degree of
`
`Doctor of Philosophy
`
`at the
`
`MASSACHUSETTS INSTITUTE OF TECHNOLOGY
`
`February 1998
`
`© 1998, Massachusetts Institute of Technology
`
`The author hereby grants to MIT permission to reproduce and
`to distribute copies of this thesis document in whole or in part.
`I
`
`✓
`
`Signature of Author .. 1 . ..... .. . . 1 . ••• , •••••• • • • • • ••.• • • • • • • · · · · · · · • · • · · · • · • · • · • • • •
`. Department of Electrical Engineering and Computer Science
`January 26, 1998
`
`Certified by ....... __, ... ,~ ....... .. . . . . . .. . .. .. . .. . . ... .... .... . ...... . .......... .
`David L. Tennenhouse
`Senior Research Scientist
`Thesis Supervisor
`
`Certified by . . . .,,, .....•... . . •\•,. . .... ~ .. . .. . . ............... . ........ ... .. ........ ... .
`John V. Guttag
`Professor and Associate Hea__!L.-CGmputer Science an~_ Engineering
`-Tfiesis ~ erv!_sc9r
`
`Acee
`
`···················· · · · · · ·-···-··-·········-·-····--·-··~·--
`s INSTRUTE
`Arthur C. Smith
`OF TECHNOLOGY
`hairman, Departmental Committee on Graduate Students
`
`I MAR n iq~q ]
`
`LIBRARIES
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 1 of 115
`
`

`

`Ex.1015
`CISCO SYSTEMS, INC. / Page 2 of 115
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 2 of 115
`
`

`

`Designing Networks for Tomorrow's Traffic
`by
`Henry H. Houh
`
`Submitted to the Department of Electrical Engineering and Computer Science
`on January 26, i998, in partial fulfillment of the
`requirements for the degree of
`Doctor of Philosophy
`
`Abstract
`
`Today, information transfer on the Internet has rapidly moved to a client/server model.
`This shift has happened rather dramatically. But, descriptions and thought processes re(cid:173)
`garding traffic flows and patterns within the Internet have not shifted as rapidly; they
`have been mired in terminology reflecting the old peer-to-peer model. All prior analyses of
`Internet traffic use symmetric endpoint flows to describe traffic patterns. Advanced flow(cid:173)
`routing methods such as IP switching and flow switching still base their techniques on the
`identification of symmetric endpoint flows.
`
`In this thesis, we examine the asymmetries of network traffic, which are particularly severe
`near servers and identify asymmetric endpoint flows as a means of dealing with this traffic.
`We design a network infrastructure with the flexibility to integrate new flow switching
`techniques with our new asymmetric endpoint flows. Our challenges are t.o achieve better
`methods of flow classification and reduction in the capture delay for packets, i.e., the time
`taken to recognize packets as part of an existing flow. We demonstrate that asymmetric
`endpoint flows address both these challenges.
`
`In order to analyze the capacity gains realized from integrating asymmetric endpoint flows,
`we create a model for IP switching which uses a small number of variables. We simulate IP
`switching using real network traces of wide area and gateway traffic to show the increase in
`routing capacity realized. We have also built a prototype system that implements the core
`concepts.
`
`We use our model to optimize the parameters of the IP switch to achieve optimal perfor(cid:173)
`mance. In an efficient IP switch implementation, our asymmetric endpoint flows and our
`techniques of IP switch optimization can produce a 24-fold increase in routing capacity for
`gateway traffic.
`
`Thesis Supervisor: David L. Tennenhouse
`'fitle: Senior Research Scientist
`
`Thesis Supervisor: John V. Guttag
`Title: Professor and Associate Head, Computer Science and Engineering
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 3 of 115
`
`

`

`4
`
`Ex.1015
`CISCO SYSTEMS, INC./ Page 4 of 115
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 4 of 115
`
`

`

`Acknowledgn1ents
`
`I gratefully acknowledge the contributions of the following people and organizations without
`whose support this thesis would have been impossible:
`
`• David Tennenhouse for all his years of guidance, inspiration, help, support and pa(cid:173)
`tience.
`
`• John Guttag for his support and guidance in helping me to collect my thoughts to(cid:173)
`gether and for his help in pulling together the final document.
`
`• Thesis reader Steve Ward, for his help and support throughout my undergraduate
`and graduate years.
`
`• Thesis reader Anant Agarwal for his helpful and insightful comments and suggestions.
`
`• All past and present members of the Telemedia Networks and Systems Group, now
`Software Devices and Systems. They have made it a fun experience to be at MIT for
`the past 8 years. I especially would like to thank Joel Adam, my former officemate,
`for fun times during the VuNet work and for introducing me to my wife Lisa; Chris
`Lindblad for being a great resource and for his helpful discussions; Bill Stasior for lots
`of late-night discussions; Vanu Bose, Mike Ismert and David Wetherall have all been
`extremely helpfulj Ulana Legedza for helpful discussions and for taking over my group
`support responsibilities.
`
`• All my friends who encouraged me over the years.
`
`• My best friend Derek Chiou for reading my thesis and for being there in good times
`and bad.
`
`• My sister Emily.
`
`• My parents for their continuing support of my education and for giving me endless
`opportunities.
`
`• My wife Lisa for her understanding, comfort, support and patience, who is as happy
`as I am for finally completing my thesis.
`
`5
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 5 of 115
`
`

`

`6
`
`Ex.1015
`CISCO SYSTEMS, INC./ Page 6 of 115
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 6 of 115
`
`

`

`Contents
`
`1 Introduction
`
`1.1 Traffic Growing Rapidly
`
`1.2 Today's Traffic: Server Based
`
`1.3 Today's Architecture: IP . . .
`
`1.3.1 Connectionless vs. Connection-oriented
`
`1.4 Tomorrow's Network: A Flexible Hybrid . . . .
`
`1.4.1 Routers and Switches and Flows, Oh My!
`
`1.4.2
`
`IP Switching: Connectionless/Connection Hybrid .
`
`1.4.3 Challenges to IP Switching
`
`. . . . . . . .
`
`1.4.4 An Asymmetric Endpoint Flow Approach
`
`1.5 Summary of Major Contributions .
`
`1.6 Roadmap
`
`. . . . . . . . . . . .
`
`2 Understanding Traffic Patterns
`
`2.1 Factors Driving Traffic Growth . . . . . . . . .
`
`2.1.1 Growth in the Overall Number of Users
`
`2.1.2 Effect of Home Users on Internet Usage
`
`2.1.3 Higher Utilization
`
`2.1.4 New Services . . .
`
`2.1.5 Traffic Growth Demands More Routing Capability
`
`2.2 Analysis of Existing Traffic Traces
`
`. . . . . . . . . . .
`
`7
`
`17
`
`18
`
`18
`
`19
`
`20
`
`22
`
`22
`
`23
`
`25
`
`26
`
`27
`
`28
`
`29
`
`29
`
`29
`
`30
`
`32
`
`33
`
`33
`
`33
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 7 of 115
`
`

`

`8
`
`CONTENTS
`
`2.2.1 Existing Flow Analyses . . . . . . . . .
`
`2.2.2
`
`Interesting Features of Network Traces .
`
`2.3 Summary
`
`. . . . . . . . . . . . . . . . .
`
`3 Network D.Jsign - A Flexible Approach
`
`3.1 VuNet I Architecture .
`
`3.1.1
`
`ATM . . . . . .
`
`3.1.2
`
`Separating Network Mechanism and Policy
`
`3.1.3
`
`Other Design Decisions
`
`. . . . . . . . . . .
`
`3.1.4
`
`VuNet Influence on Other ATM Equipment
`
`3.1.5 Summary . . . . . . . . .
`
`3.2 VuNet Hardware Implementation
`
`3.2.1 Switches .
`
`3.2.2 Links
`
`. .
`
`3.2.3 Host Interface .
`
`3.2.4 Peripherals
`
`. .
`
`3.3 VuNet Protocols and Their Implementation
`
`3.3.1 VudBoard Device Driver Architecture
`
`3.3.2 Network Functions . . . .
`
`3.4 VuNet Device Driver Data Paths
`
`3.4.1
`
`Input Polling
`
`3.4.2
`
`Device Input
`
`3.4.3
`
`Packet Reassembly .
`
`3.4.4
`3.4.5
`
`Packet Delivery .
`
`Data Output . .
`
`3.5 VuNet Performance and Discussion .
`
`3.5.1 VuNet Performance
`
`3.5.2 Discussion .
`
`3.6 Summary
`
`. . . . .
`
`34
`
`36
`
`41
`
`45
`
`47
`
`47
`
`48
`
`49
`
`50
`
`51
`
`51
`
`51
`
`53
`
`55
`
`58
`
`58
`
`59
`
`59
`
`63
`
`63
`
`64
`
`64
`
`65
`
`65
`
`66
`
`66
`
`67
`
`68
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 8 of 115
`
`

`

`CONTENTS
`
`4 IP Switching
`
`4.1 Overview of IP switching
`
`4.1.1 Flow Detection and Classification - A Symmetric Approach
`
`4.1.2
`
`IP Switching Mechanics . . . . .
`
`4.1.3 Drawbacks of Symmetric Flows .
`
`4.2 Asymmetric Endpoint Flows . . . . . .
`
`4.2.1 Asymmetric Endpoint Flow Benefits
`
`4.3 VuNet II: Integrating IP Switching
`
`4.3.1 The VCI Fusing Problem
`
`4.4 Summary
`
`. . . . . . . . . . . . .
`
`5 IP Switching Model and Network Trace Simulations
`
`5.1 Functional Model for Routing and IP Switching.
`
`5.2
`
`IP Switching Work Model
`
`5.2.1 Assumptions
`
`.
`
`5.2.2 Packet Classes
`
`5.2.3 Module Work Models
`
`5.3 Simplification of Work Model
`
`5.3.1 Flow Setups.
`
`5.3.2 Stragglers ..
`
`5.3.3 Deriving Costs as a Function of Switching Threshold .
`
`5.4 Discussion of Work Model and IP Switching .
`
`5.4.1 Fairness . . . .
`
`5.4.2 Flow Timeouts
`
`5.4.3 Balancing the Switching Threshold .
`
`5.4.4 Asymmetric Endpoint Flows
`
`5.4.5 Reduce Flow Accounting Costs
`5.5 Simulation Results and Analysis ...
`
`5.5.1 Using our model with the simulator
`
`9
`
`69
`
`69
`
`72
`
`72
`
`73
`74
`
`75
`
`76
`
`77
`
`78
`
`79
`
`80
`
`81
`
`81
`
`81
`
`83
`
`85
`
`85
`
`86
`
`88
`
`90
`
`91
`
`91
`
`92
`
`92
`
`93
`
`94
`
`94
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 9 of 115
`
`

`

`CONTENTS
`
`5.5.2 Values of Parameters Used . . . . . . . . . . . . . . . . . .
`
`5.5.3 Overall Capacity Gains Using Asymmetric Endpoint Flows
`
`5.6 Summary
`
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`6 Summary, Contributions and Future Work
`
`6.1 Summary ..
`
`6.2 Contributions
`
`6.3 Future Work
`
`6.3.1 Active Flow Switches
`
`6.3.2
`
`Analysis of More Wide Area Traces
`
`6.3.3 Change the Way People Report Information on Network Traffic .
`
`6.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`95
`
`95
`
`104
`
`105
`
`106
`
`107
`
`109
`
`109
`
`109
`
`110
`
`110
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 10 of 115
`
`

`

`List of Figures
`
`1-1 High performance routers route individual IP packets throughout a IP net(cid:173)
`work backbone. Packet headers must be examined and acted upon at each
`router for all packets traversing the backbone. . . . . . . . . . . . . . . . . .
`
`1-2 Each router between the source and destination must examine the IP header
`in order to determine the proper outbound link. The routing table lookup
`uses a radix tree search to find the longest prefix match. . . . . . . . . . . .
`
`1-3 An IP switch provides same external functionality of a router. The IP switch
`consist of two parts, the IP switch router and an ATM switch.
`. . . . . . .
`
`1-4 Packets on a labeled flow take a bypass path through the ATM switch,
`. . . . . . . . . . . . . . . . . . . . .
`thereby avoiding the IP switch router.
`
`2-1 The number of Internet hosts has grown explosively since the introduce of
`the World-Wide Web in 1991. Source: The Internet Society
`
`2-2 Distribution of packet sizes for packets leaving LCS.
`
`2-3 Distribution of packet sizes for paclc.ets entering LCS. .
`
`2-4 Cumulative distribution of packet sizes for all LCS packets.
`
`2-5 Total bytes traversing LCS gateway, by service.
`
`2-6 Total bytes in FIX-West trace, by service. . . .
`
`3-1 A Desk Area Network where devices are taken out of the workstation and
`attached directly to the network. The workstations coordinate the flow of
`data among devices.
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`3-2 The workstation performs some of the high level networking functions such
`as topology discovery, connection setup, and possibly even admission control.
`Hence, the network "boundary of trust" extends into the workstation.
`
`11
`
`19
`
`20
`
`23
`
`24
`
`30
`
`39
`
`39
`
`40
`
`40
`
`43
`
`46
`
`49
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 11 of 115
`
`

`

`12
`
`LIST OF FIGURES
`
`3-3 The VuNet switch is a 4 or 6 port non-blocking crossbar switch, with both
`input and output port buffering. It has a per-port throughput of 700 Mbps.
`
`3-4 The links in VuNet perform header remapping; and next output port lookup
`for hop-by-hop cell routing.
`. . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`3-5 Cells sent on the reserved VCI are processed by the link to update its lookup
`tables. The cell immediately following the setup cell will be remapped to the
`new VCI and port. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`3-6 An application which needs to communicate to another workstation on the
`network generates data with an internal identifier. This identifier is remapped
`using a table look-up to generate the network VCI and first hop switch output
`port (tport). This information is passed to the switch, which forwards the
`data to the workstation on port 2.
`. . . . . . . . . . . . . . . . . . . . . .
`
`3-7 A block diagram of the VudBoard and the required cell layout in memory.
`
`3-8 Cells are read from the network at and passed to the software reassembly
`process at regular polled intervals. These assembled packets are then passed
`to the IP handler or directly to a VuNet socket. . . . . . . . . . . . . . . . .
`
`4-1 A router within the network is replaced by an IP switch - a combination of an
`IP switch router and an ATM switch. This combination provides the same
`exterior functionality as a standard router. . . . . . . . . . . . . . . . . . . .
`
`4-2 The IP switch router routes packets normally until it receives a redirect mes(cid:173)
`sage from the downstream IP switch. It then forwards all packets matching
`the label on a new VCI, causing the packet to bypass the downstream IP
`switch router. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`52
`
`54
`
`54
`
`56
`
`57
`
`62
`
`70
`
`71
`
`4-3 VuNet hosts and switches are converted for use in an IP switching environment. 76
`
`4-4 When cells from two VCls are simply merged to form a single VCI, it is
`impossible to distinguish the cells to reassemble the packets properly. Other
`techniques must be used.. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`5-1 The functional description of a router is composed of Input, Fowarding and
`Output modules.
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`5-2 The functional description of an IP switch is composed of modules which
`handle flow tracking and setup in addition to those that compose a router. .
`
`5-3 Each packet in a flow can be classified as one of five cla.<,ses. Each of these
`class of packets has a different work function.
`. . . . . . . . . . . . . . . . .
`
`78
`
`80
`
`80
`
`82
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 12 of 115
`
`

`

`LIST OF FIGURES
`
`5-4 Each type of packet talces the same path through the various functional
`modules of an IP switch. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`5-5 The number of Setup and Observe packets in a trace can be derived from the
`distribution of packets per flow. . . . . . . . . . . . . . . . . . . . . . . . . .
`
`5-6 Worst Case Probability of Flow Timeouts for WAN Trace for Various Flow
`Types
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`5-7 Worst Case Probability of Flow Timeouts for LCS Trace for Various Flow
`Types
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`5-8 Performance increase using various flow types as a function of IP switching
`threshold for LCS trace. The fl.ow timeout interval is 90 s except where
`indicated, the flow setup overhead is 4, and the counting overhead is 0.16,
`and the expected stragglers per flow is 0.12. . . . . . . . . . . . . . . . . . .
`
`5-9 Performance increase using Machine flows for not switching ilows of pre(cid:173)
`identified services and switching all flows, versu.q the counting overhead
`Wcounling
`WRouling •
`
`•
`
`·
`
`• • •
`
`·
`
`·
`
`·
`
`·
`
`•
`
`·
`
`·
`
`• •
`
`·
`
`·
`
`·
`
`·
`
`·
`
`• •
`
`•
`
`·
`
`•
`
`·
`
`·
`
`·
`
`·
`
`• •
`
`•
`
`·
`
`·
`
`•
`
`·
`
`•
`
`·
`
`13
`
`82
`
`90
`
`92
`
`93
`
`96
`
`97
`
`99
`
`5-10 Performance increase versus time for Server flows with a switching threshold
`of 2 packets and a flow timeout of 180 seconds using the LCS trace. The
`number of active flows per second are within 10% of the number of active
`flows per second of TCP flows using a 90 second timeout.
`. . . . . . . . . .
`
`5-11 Number of active flows per second for LCS trace using Server flows with a 180
`second timeout. The average number of flows is within 10% of the average
`number of flows when using Machine Hows and TCP flows without short flows. 100
`
`5-12 Performance increase versus switching threshold for Server flows with a flow
`timeout of 180 seconds using various parts of the LCS trace. The optimal
`switching threshold for outbound is 3; for inbound traffic is 2; for web traffic
`is 1; for all but web traffic is 3. We can increase our capacity by almost 10%
`by using web/non web switching threshold discrimination. . . . . . . . . . . 101
`
`5-13 Performance increase using various flow types as a function of IP switching
`threshold for WAN trace. The flow timeout interval is 90 s, the flow setup
`overhead is 4, and the counting overhead is 0.16, and the stragglers vary by
`flow type used as shown in Table 5.1. . . . . . . . . . . . . . . . . . . . . . . 103
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 13 of 115
`
`

`

`14
`
`LIST OF FIGURES
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 14 of 115
`
`

`

`List of Tables
`
`2.1 A flow analysis from Cisco systems, taken over a 40 hour period in 1996,
`illustrates the large proportion of HTTP and DNS flows. . . . . . . . . . . .
`
`2.2 Local Area Traffic: Flow traces from the TNS group's web server network,
`broken down for directionality.
`. . . . . . . . . . . . . . . . . . . . . . . . .
`
`2.3 Analysis of LCS gateway traffic shows the dominant traffic types and a high
`degree of asymmetry in services sucn as HTTP. . . . . . . . . . . . . . . . .
`
`2.4 Wide Area Traffic: Analysis of January 1997 traffic trace from FIX-West
`Backbone with a 60 second flow timeout, taking into account directionality.
`
`35
`
`36
`
`38
`
`42
`
`3.1 Number of copies for data getting from the network to user space. DMAs are
`not considered copies, but the data does trav~rse the system and 1/0 busses. 65
`
`3.2 Number of copies for data getting from user space to the network. DMAs are
`not considered copies, but the data does traverse the system and 1/0 busses. 66
`
`3.3 Bandwidth at various points in the VuNet.
`
`4.1 Two types of flows are defined in the reference implementation. The X's
`indicate identifying characteristics for a flow. Note that these flows are sym(cid:173)
`metric in nature; when a source process endpoint is used to identify a flow,
`a deRtination process endpoint is also used. When only the destination IP
`address is used, only a source IP address is used.
`. . . . . . . . . . . . . . .
`
`67
`
`72
`
`4.2 When flows are redirected, the headers can be compressed, since the packets
`are bound to a VCI for which a flow label with additional information exists. 74
`
`4.3 The new asymmetric endpoint Session and Server flows exploit the aggrega-
`tion of traffic around servers and the asymmetry of traffic flow to and from
`servers.
`
`74
`
`15
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 15 of 115
`
`

`

`16
`
`LIST OF TABLES
`
`5.1 Psiraggler with a setup delay of 25 ms for the LCS and WAN traces, for
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`various flow types.
`
`87
`
`5.2
`
`P~raggler with a setup delay of 25 ms for the LCS and WAN traces, for various
`Setup
`flow types. This can also be read as the expected number of straggler packets
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`per switched flow.
`
`5.3 Cost of the various IP switching modules on a DEC Alpha 3000/400. .
`
`5.4 Cost of the various packet classes on a DEC Alpha 3000/400. . . . . .
`
`5.5 Number of active flow per second, on average, and the performance increase
`for the LCS trace. Flow timeouts are 90 s unless otherwise indicated. . . . .
`
`87
`
`95
`
`95
`
`98
`
`5.6 Comparison of results to maximum possible performance increase using all(cid:173)
`knowing IP switch. The Server flow using 180 s timeout shows results for use
`of an optimal threshold for all web traffic in parentheses, and the bracketed
`number represents gains from using optimal thresholds for all types services
`and direction, and not switching selected flows.
`. . . . . . . . . . . . . . . . 102
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 16 of 115
`
`

`

`Chapter 1
`
`Introduction
`
`In just a few years, the Internet has become widely accepted as a medium for information
`delivery. This has lead to tremendous growth in the number of users and the amount of
`data they transmit and receive. It has also lead to the introduction of new types of real-time
`services not available over the network just a few years ago.
`
`This traffic presents problems to current connectionless IP routed networks as the number of
`packets begins to exceed network routing capacity. In IP networks, routers must determine
`on a hop-by-hop basis the proper next hop. These routers incur a minimum fixed overhead
`cost for each packet processed and forwarded, limiting their performance. Some service
`providers that host large servers already have had to make alternative arrangements for
`receiving traffic, as the main routers serving them can handle no more traffic [Week, 1997).
`
`New methods of designing networks can lead to much greater capacity. High-speed switches
`working in conjunction with IP routers can provide fast paths that bypass per-packet pro(cid:173)
`cessing by the routers. Recognizing that servers aggregate tremendous amounts of traffic
`and providing special network circuits for them can also reduce the amount of overhead
`incurred for delivering this traffic.
`
`In this thesis, we design and implement a flexible connection-oriented network with the
`ability to manage connections from attached hosts. We take advantage of this flexibility to
`incorporate various types of high speed network services - video to the application, static
`meshed workgroup connections, and even connectionless services - on top of our network.
`By further utilizing our flexibility, we extend the IP over ATM model to designate and
`switch special server based flows which greatly reduces the amount of resources devoted to
`providing IP routed services.
`
`17
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 17 of 115
`
`

`

`18
`
`CHAPTER 1.
`
`INTRODUCTION
`
`1.1 Traffic Growing Rapidly
`
`The Internet began in the late 1960's as the ARPANET, and by July 1997, it was estimated
`that almost 20,000,000 computers worldwide were connected [Zakon, 1997]. The early 1990's
`marked a turning point for the Internet, which rapidly changed from a network utilized by
`educators, students and researchers to a mass-market medium.
`
`The World-Wide Web (WWW) has been a primary driving force behind this transformation;
`the clients, or browsers, provide the user interface to the growing amounts of information
`available on the Internet. Today, Web traffic is dominated by text, image, and file retrieval,
`but we are beginning to see real-time audio and video. As this multimedia traffic makes its
`way into the wide area, it is becoming a rapidly growing burden on backbone networks. In
`many cases, the traffic growth has outstripped the pace of increase in network and router
`capacity. These problems must be addressed before today's rapidly growing multimedia
`data delivery can be well handled by the network backbones.
`
`1.2 Today's 'I'raffi.c: Server Based
`
`Network data is also increasingly being delivered by servers, since the primary mode of
`information retrieval on the Internet is the use of a WWW client.
`
`Data taken from gateways and backbones indicate that roughly 50-55% of all packets are
`Hypertext Transport Protocol (HTTP, or WWW) packets, and in some wide a.rea traces,
`almost 25% of all packets are Domain Name System (DNS) packets. In both cases, these
`packets are destined to or generated by WWW and DNS servers. The number of WWW
`servers has increased from 163 in 1993 to an estimated 1,269,800 in August 1997, while the
`number of domains have grown from 3,900 in 1989 to 1,301,000 in July 1997.
`
`The data flow to WWW servers is highly asymmetric since the servers are primarily deliv(cid:173)
`ering information to the clients. The number of packets fl.owing in each direction is roughly
`on par, since TCP requires an acknowledgment packet for every data segment sent so that
`sender can release the buffer and send more data. This leads to a high degree of asymmetry
`in the number of bytes per packet flowing away from the server as opposed to flowing toward
`the server. Since the work in routing packets toward and away from a server is roughly
`equivalent for any given TCP session, the amount of work done by the network is much
`greater per byte - by a factor of 10 to 1 or more - for the little amount of information
`flowing toward the server.
`
`For example, in a sample web browsing session at www.cnn.com that retrieved the main
`page and a roughly six news stories, 676 packets were exchanged between the client and
`the server. 373 packets containing 421119 bytes of data (not including protocol headers)
`were sent from the server to the client, with almost two-thirds of these packets of size 1460
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 18 of 115
`
`

`

`1.3. TODAY'S ARCHITECTURE: iP
`
`19
`
`Figure 1-1: High performance routers route individual IP packets throughout a IP network
`backbone. Packet headers must be examined and acted upon at each router for all packets
`traversing the backbone.
`
`bytes. 303 packets containing 16881 bytes of data were sent back to the server, with 242
`cf these being empty protocol acknowledgement packets of no data. The remainder of the
`packets were smaller than 324 bytes.
`
`1.3 Today's Architecture: IP
`
`Most of today's network is based upon a connectionless IP model. A connectionless model
`is one in which packets are sent to one or more destinations independently of each other,
`with each packet's header containing addressing information. IP routers forward packets
`based on their universal destination addresses. Routers collect the information required for
`them to determine the best next-hop for any given packet. No unrecoverable connection
`related hard state resides in the network.
`
`Figure 1-1 diagrams the Internet, where high-performance routers within the network back(cid:173)
`bone route traffic between Metropolitan Area Networks. Currently, the fastest routers
`handle roughly 5001000 packets per second, and these backbone routers often strain from
`the loads presented at peak periods.
`··
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 19 of 115
`
`

`

`20
`
`CHAPTER 1.
`
`INTRODUCTION
`
`IP Packetj
`
`:p Packel i -
`
`link I
`
`Radiit lree
`search
`
`link I
`
`Figure 1-2: Each router between the source and destination must examine the IP header in
`order to determine the proper outbound link. The routing table lookup uses a radix tree
`search to find the longest prefix match.
`
`IP routing is time consuming. All routers perform a rather simple function: they determine
`a specific outbound interface based on the destination IP address contained in every packet.
`However, because IP addresses are long (32 bits1 ), it has been impractical to provide simple
`table lookups on IP addresses at network speeds. Routers resort to building much smaller
`routing tables - tens of thousands of entries as opposed to billions - that are efficiently
`search-able. In addition, if an exact match is not found, then the "best" match must be
`returned, with the "best" match defined as the entry having the most number of prefix bits
`in common with the destination address.
`
`1.3.1 Connectionless vs. Connection-oriented
`
`An IP network is connectionless, that is to say, information contained in each packet de(cid:173)
`termines the destination without relying on any hard state contained within the network.
`Packets from the same source to the same destination may take different paths through the
`network, and may even be delivered out-of-order.
`
`11Pv6 will move to 128 bit IP addresses.
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 20 of 115
`
`

`

`1.3. TODAY'S ARCHITECTURE: IP
`
`21
`
`In a connection-oriented network on the other hand, a specific end-to-end circuit is assigned
`for communication between two users, and this circuit's setup must take place before any
`information can be exchanged. This "virtual circuit" determines the route at the time that
`the circuit is set up that all future packets transmitted on the circuit. All traffic follows
`the same path and does not get reordered. While this is inefficient for short-lived flows,
`packets in long-lived flows experience lower latency and need not be processed at every hop.
`Header sizes may be smaller, as there is no need to add universal address information to
`every packet once an end-to-end circuit is established.
`
`Both types of networks have their advantages. In a connectionless network, new hosts can
`be more easily added. Once a host is configured locally, it may communicate globally,
`without any lengthy delays to set up connections. The overall network is able to recover
`from internal router failures.
`
`Connection-oriented networks can more easily provide service guarantees. Once a connec(cid:173)
`tion is established, packets traverse the network without being examined at every node
`along the way. Also, since the packets are generally switched at the hardware level, the
`latency for packets is much lower than in a connectionless network.
`
`On the other hand, both types of networks have their disadvantages. In a connection(cid:173)
`oriented network such as the telephonf" network, when an internal switch fails, a user's
`call is dropped. The state of the circuit in this case is usually encoded into the switching
`hardware, and is not generally dynamically re-allocated. And for short lived connections,
`the circuit setup overhead is quite large compared to the data transfer time. Even long
`lived flows must wait for circuits to be set up.
`
`Though a connectionless network may transmit packets without lengthy circuit setup, every
`packet must be examined at every router. This is one of the largest costs of maintaining
`the connectionless IP network. This involves searching the routing table, which may total
`to tens of thousands of entries for networks, subnetworks, and hosts. While hosts are
`often grouped hierarchically into networks, the process of determining the proper outbound
`interface can be lengthy - even a high end Cisco backbone router can only route 10,000
`packets per second when each packet needs a table lookup, while low end routers handle
`around 1,800 [Kaeo, 1996].
`
`Searching methods have been streamlined to use the best algorithms, and entries are also
`cached so that packets in a flow that are local in time generally experience less processing
`delay. However, routers must still process every single packet flowing between machines,
`even in a flow that is well established. While the first packet may take a relatively long
`time to route, all succeeding packets still must be processed.
`
`Thus, it is difficult for routers to increase capacity due to the overhead of the basic routing
`function.
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 21 of 115
`
`

`

`22
`
`CHAPTER 1.
`
`INTRODUCTION
`
`1.4 Tomorrow's Network: A Flexible Hybrid
`
`As traffic continues to grow, current IP networks will become stressed. There are already
`signs of this, and network pundits have predicted major outages in the near future. Thus a
`new network design for handling the growth in traffic is needed.
`
`1.4.1 Routers and Switches and Flows, Oh My!
`
`Before continuing, we will define terms that will be used throughout this thesis. The
`terminology is confusing because we will be describing the joint operation of devices which
`ordinarily would be functioning in distinct layers within the network.
`
`Our definitions are as follows:
`
`• Router: A device which is able to forward a packet from the input port to one output
`port that guides the packet towards the destination whose address (with global scope)
`is contained in the packet's header. An IP router is a router for packets with IP
`protocol headers. The determination of the proper output port generally requires a
`complex lookup function, and the packet's header remains unchanged. 2 Routers are
`considered slow devices.
`
`• Switch: A device which is able to f01 ward a packet from the input port to one output
`port that guides the packet towards the destination based on a label (with only local
`scope) contained in the packet's header. The determination of the proper output port
`is a simple lookup function, and the label