CCIE® Professional Development
`Inside Cisco IOS®
`Softvvare Architecture
`
`An essential guide to understanding the internal
`operation of Cisco routers
`
`ciscopress.com
`
`Vijay Bollapragada, CCIE No. 1606
`Curtis Murphy, CCIE No. 1521
`Russ White, CCIE No. 2635
`
`

`

`Inside Cisco IOS Software
`Architecture
`
`Vijay Bollapragada, CCIE #1606,
`Curtis Murphy, CCIE #1521, & Russ White, CCIE #2635
`
`Cisco SYSTEMS
`
`Cisco PRESS
`
`Cisco Press
`201 W 103rd Street
`Indianapolis, IN 46290 USA
`
`Cisco Systems, Inc.
`Exhibit 1008
`Page 2 of 38
`
`

`

`Inside Cisco IOS Software Architecture
`Vijay Bollapragada, Curtis Murphy, & Russ White
`Copyright© 2000 Cisco Systems, Inc.
`Cisco Press logo is a trademark of Cisco Systems, Inc.
`Published by:
`Cisco Press
`201 West 103rd Street
`Indianapolis, IN 46290 USA
`All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means,
`electronic or mechanical, including photocopying, recording, or by any information storage and retrieval
`system, without written permission from the publisher, except for the inclusion of brief quotations in a
`review.
`Printed in the United States of America 2 3 4 5 6 7 8 9 0
`Library of Congress Cataloging-in-Publication Number: 99-64092
`ISBN: 1-57870-181-3
`
`Warning and Disclaimer
`This book is designed to provide information about Cisco's proprietary Internetwork Operating System
`(IOS) software architecture. Every effort has been made to make this book as complete and as accurate as
`possible, but no warranty or fitness is implied.
`The information is provided on an "as is" basis. The author, Cisco Press, and Cisco Systems, Inc., shall have
`neither liability nor responsibility to any person or entity with respect to any loss or damages arising from
`the information contained in this book or from the use of the discs or programs that may accompany it.
`The opinions expressed in this book belong to the author and are not necessarily those of Cisco Systems, Inc.
`
`Trademark Acknowledgments
`All terms mentioned in this book that are known to be trademarks or service marks have been appropriately
`capitalized. Cisco Press or Cisco Systems, Inc. cannot attest to the accuracy of this information. Use of a
`term in this book should not be regarded as affecting the validity of any trademark or service mark.
`
`Feedback Information
`At Cisco Press, our goal is to create in-depth technical books of the highest quality and value. Each book is
`crafted with care and precision, undergoing rigorous development that involves the unique expertise of
`members from the professional technical community.
`Readers' feedback is a natural continuation of this process. If you have any comments regarding how we could
`improve the quality of this book, or otherwise alter it to better suit your needs, you can contact us through e(cid:173)
`mail at ciscopress@mcp.com. Please make sure to include the book title and ISBN in your message.
`We greatly appreciate your assistance.
`
`Cisco Systems, Inc.
`Exhibit 1008
`Page 3 of 38
`
`

`

`Publisher
`Editor-In-Chief
`Cisco Systems Program Manager
`Managing Editor
`Senior Acquisitions Editor
`Development Editor
`Project Editor
`Copy Editor
`Technical Editors
`
`Team Coordinator
`Book Designer
`Cover Designer
`Production Team
`Indexer
`
`John Wait
`John Kane
`Jim Le Valley
`Patrick Kanouse
`Brett Bartow
`Christopher Cleveland
`Jennifer Nuckles
`Theresa Wehrle
`Mike Brown, Jennifer DeHaven Carroll,
`Ron Long, Alexander Marhold
`Amy Lewis
`Gina Rexrode
`Louisa Klucznik
`Argosy
`Kevin Fulcher
`
`Crsco PRESS
`
`Cisco SYSTEMS -®
`
`Corporate Headquarters
`Cisco Systems, Inc.
`170 West Tasman Drive
`San Jose, CA 95134-1706
`USA
`http://www.cisco.com
`Tel: 408 526-4000
`800 553-NETS (6387)
`Fax: 408 526-4100
`
`European Headquarters
`Cisco Systems Europe s.a.r.l.
`Pare Evolic, Batiment L1/L2
`16 Avenue du Quebec
`Villebon, BP 706
`91961 Courtaboeuf Cedex
`France
`http://www-europe.cisco.com
`Tel: 33 1 69 18 61 00
`Fax: 33 1 69 28 83 26
`
`American
`Headquarters
`Cisco Systems, Inc.
`170 West Tasman Drive
`San Jose, CA 95134-1706
`USA
`http://www.cisco.com
`Tel: 408 526-7660
`Fax: 408 527-0883
`
`Asia Headquarters
`Nihon Cisco Systems K.K.
`Fuji Building, 9th Floor
`3-2-3 Marunouchi
`Chiyoda-ku, Tokyo 100
`Japan
`http://www.cisco.com
`Tel: 81 3 5219 6250
`Fax: 81 3 5219 6001
`
`Cisco Systems has more than 200 offices in the following countries. Addresses, phone numbers, and fax numbers are listed on
`the Cisco Connection Online Web site at http://www.cisco.com/offices.
`
`Argentina • Australia • Austria • Belgium • Brazil • Canada • Chile • China • Colombia • Costa Rica • Croatia • Czech Republic
`• Denmark • Dubai, UAE Finland • France • Germany • Greece • Hong Kong • Hungary • India • Indonesia • Ireland • Israel
`• Italy • Japan • Korea • Luxembourg • Malaysia • Mexico • The Netherlands • New Zealand • Norway • Peru • Philippines •
`Poland • Portugal • Puerto Rico • Romania • Russia • Saudi Arabia • Singapore • Slovakia • Slovenia • South Africa • Spain •
`Sweden • Switzerland • Taiwan • Thailand • Turkey • Ukraine • United Kingdom • United States • Venezuela
`
`Copyright© 2000 Cisco Systems, Inc. All rights reserved. Printed in the USA. Access Registrar, AccessPath, Any to Any, AtmDirector, CCDA, CCDE, CCDP, CCIE, CCNA,
`CCNP, CCSI, CD~PAC, the Cisco logo, Cisco Certified Internetwork Expert logo, CiscoLink, the Cisco Management Connection logo, the Cisco Net Works logo, the Cisco
`Powered Network logo, Cisco Systems Capital, the Cisco Systems Capital logo, Cisco Systems Networking Academy, the Cisco Systems Networking Academy logo, the
`Cisco Technologies logo, ConnectWay, ControlStream, Fast Step, FireRunner, GigaStack, IGX, Internet Quotient, Kernel Proxy, MGX, Natural Network Viewer, NetSonar,
`Network Registrar, Packet, PIX, Point and Click lnternetworking, Policy Builder, Precept, RouteStream, Secure Script, Service Way, SlideCast, SMARTnet, Stream View, The
`Cell, TrafficDirector, TransPath, ViewRunner, Virtua!Stream, Vision Way, VlanDirector, Workgroup Director, and Workgroup Stack are trademarks; Changing the Way We
`Work, Live, Play, and Learn, Empowering the Internet Generation, The Internet Economy, and The New Internet Economy are service marks; and ASIST, BPX, Catalyst,
`Cisco, Cisco IOS, the Cisco IOS logo, Cisco Systems, the Cisco Systems logo, the Cisco Systems Cisco Press logo, Enterprise/Solver, EtherChannel, EtherSwitch, FastHub,
`FastLink, FastPAD, FastSwitch, GeoTel, IOS, IPfIV, IPX, LightStream, LightSwitch, MICA, NetRanger, Registrar, StrataView Plus, Stratm, TeleRouter, and VCO are
`registered trademarks of Cisco Systems, Inc. and/or its affiliates in the U.S. and certain other countries. All other trademarks mentioned in this document are the property of
`their respective owners. The use of the word partner does not imply a partnership relationship between Cisco and any of its resellers. (9908R)
`
`Cisco Systems, Inc.
`Exhibit 1008
`Page 4 of 38
`
`

`

`iv
`
`About the Authors
`
`Vijay Bollapragada, CCIE # 1606, is currently a manager in the Solution Engineering team at Cisco, where
`he works on new world network solutions and resolves complex software and hardware problems with
`Cisco equipment. Vijay also teaches Cisco engineers and customers several courses, including Cisco Router
`Architecture, IP Multicast, Internet Quality of Service, and Internet Routing Architectures. He is also an
`adjunct professor in Duke University's electrical engineering department.
`Curtis Murphy, CCIE #1521, is an engineer in Cisco's Serviceability Design Department in Research Tri(cid:173)
`angle Park, specializing in IOS software products. He has worked in the networking industry since 1989 and
`at Cisco since 1994. While at Cisco, he has worked both as an IBM protocols specialist in the Technical
`Assistance Center and as a software engineer in IOS Software Development for mid-range and high-end
`routers.
`Russ White, CCIE #2635, currently is working on the IOS Network Protocols Deployment and Scalability
`Team, where he is involved in the design and implementation of routing protocols and scalable network
`design. Russ is the co-author of the Cisco Press title CCIE Professional Development: Advanced IP Net(cid:173)
`work Design (ISBN: 1-57870-097-3), published in June 1999.
`
`About the Technical Reviewers
`Michael Brown, CCIE #2249, is an ISP Support engineer for Cisco Systems. He earned his bachelor of sci(cid:173)
`ence degree in electrical engineering from North Carolina State University. In the 11 years he has worked in
`the networking industry, he has supported a variety of customer networks and technologies. He spent three
`and half years supporting customers in the Cisco Technical Assistance Center in Brussels, Belgium, before
`joining the Cisco ISP Support team in Research Triangle Park, NC. He has taught several router architecture
`courses to Cisco internal audiences and to Cisco customers.
`Jennifer DeHaven Carroll, CCIE #1402, is a principal consultant for Lucent Technologies, NetworkCare
`Professional Services. She earned her bachelor of science degree in computer science from University of
`California, Santa Barbara. In the past 11 years, Jennifer has planned, designed, and implemented many
`Cisco-based networks, utilizing all the various IOS switching and packet queuing methods.
`Ron Long is the Director of Internet Development for a large, southwestern integrated communications
`provider. He is responsible for the planning, extension, development, and implementation of Internet ser(cid:173)
`vices and Layer 2-3 access. Ron entered the networking industry in 1995 when he co-founded an ISP in a
`small town in Texas. Since then, Ron has provided consulting services and has implemented Cisco solutions
`to Fortune 1000 companies across the globe.
`Alexander Marhold, CCIE #3324, holds an MSC degree in industrial electronics and an MBA. He works
`as Senior Consultant and Manager at PROIN, a leading European training and consulting company. His
`focus areas are core routing and service provider issues, such as MPLS, Local Loop, Network Design, and
`Implementation. Beside his works as a consultant, Alexander is also a CCSI and develops and holds special(cid:173)
`ized trainings in the service provider area. His previous working experiences also include academic teaching
`at a polytechnical university for telecommunications, as well as working as CIM-Project Manager in the
`chemical industry.
`
`i
`I
`
`Cisco Systems, Inc.
`Exhibit 1008
`Page 5 of 38
`
`

`

`viii
`
`Contents
`
`Introduction
`Objectives
`Organization
`
`xii
`xii
`xiii
`
`Chapter 1
`
`Fundamental IOS Software Architecture 2
`
`Operating Systems Basics 4
`CPU Resource Management and Multitasking 4
`Memory Resource Management 6
`Interrupts 7
`
`IOS Architecture Overview 7
`
`Memory Organization 9
`Memory Pools 12
`
`IOS Processes 13
`Process Life Cycle 14
`IOS Process Priorities 16
`Process Examples 17
`
`IOS Kernel 20
`The Scheduler 20
`The Memory Manager 24
`
`Packet Buffer Management 31
`System Buffers 32
`
`Device Drivers 38
`
`Summary 38
`
`Chapter 2
`
`Packet Switching Architecture 40
`
`Routing 101: Process Switching 42
`Traffic Load Sharing with Process Switching 44
`Disadvantages of Process Switching 46
`
`Fast Switching: Caching to the Rescue 47
`Fast Cache Organization 49
`Maintaining the Cache 53
`Traffic Load Sharing Considerations with Fast Switching 55
`
`Optimum Switching 56
`
`' I '
`I '
`
`Cisco Systems, Inc.
`Exhibit 1008
`Page 6 of 38
`
`

`

`ix
`
`1
`
`j
`I I
`
`!
`
`I
`
`Cisco Express Forwarding 58
`How CEF Works 59
`Traffic Load Sharing with CEF 63
`
`Summary 65
`
`Chapter 3
`
`Shared Memory Routers 68
`
`Hardware Architecture for Shared Memory Routers 69
`CPU 70
`Memory 71
`Interface Controllers 74
`
`Packet Buffers for Shared Memory Routers 75
`Private Buffer Pools 75
`Receive Rings and Transmit Rings 77
`
`Packet Switching on a Shared Memory Router 79
`Receiving the Packet 79
`Switching the Packet 81
`Transmitting the Packet 83
`
`Summary 85
`
`Chapter 4
`
`Early Cbus Routers 86
`
`AGS+ Hardware Architecture 87
`
`Packet Switching with the Cbus 90
`Autonomous Switching 90
`Cbus Fast Packet Memory 91
`
`The Cisco 7000 Series Router 92
`
`Summary 93
`
`Chapter 5
`
`Particle-Based Systems 94
`
`Buffer Management Using Particles 95
`Particle Pools 98
`Particle Coalescing 99
`
`The Cisco 7200 Series Routers 99
`Hardware Architecture 101
`Memory 104
`
`Cisco Systems, Inc.
`Exhibit 1008
`Page 7 of 38
`
`

`

`x
`
`Packet Switching on the Cisco 7200 Series Routers 106
`Packet Receive Stage 106
`Packet Switching Stage 108
`Packet Transmit Stage 109
`
`Summary 111
`
`Chapter 6
`
`Cisco 7500 Routers 112
`
`Hardware Architecture of the Cisco 7500 Router 113
`The Data Bus 114
`Route Switch Processor 115
`
`Packet Switching on the Cisco 7500 Router 123
`RSP Switching: Receiving the Packet 124
`RSP Switching: Switching the Packet 126
`RSP Switching: Transmitting the Packet 129
`
`VIP Architecture 131
`VIP Components 132
`VIP Models 134
`VIP Packet Operations: Distributed Switching 135
`VIP Receive Side Buffering 141
`
`. Troubleshooting Tips for the Cisco 7500 Router 142
`High CPU Utilization 142
`Input Drops 144
`Ignores 145
`Output Drops 145
`
`Summary 145
`
`Chapter 7
`
`The Cisco Gigabit Switch Router: 12000 146
`
`Hardware Architecture 147
`Switching Fabric 148
`Maintenance Bus 154
`Gigabit Route Processor 154
`Line Card 155
`
`Packet Switching 161
`Packet Switching: Engine 0 and Engine 1 162
`Packet Switching: Engine 2 LC 164
`Packet Switching: Switching Cells across Fabric 165
`Packet Switching: Transmitting Packets 165
`
`Summary 167
`
`1,
`I
`
`Cisco Systems, Inc.
`Exhibit 1008
`Page 8 of 38
`
`

`

`xi
`
`Chapter 8
`
`Quality of Service 168
`
`QoS Overview 169
`Congestion Management 171
`Congestion Avoidance 172
`
`Priority Queuing 172
`Configuring and Monitoring Priority Queuing 173
`
`Custom Queuing 17 5
`
`Weighted Fair Queuing 178
`Platform-Independent WFQ 179
`Configuring and Monitoring WFQ 182
`Distributed Weighted Fair Queuing 188
`
`Modified Deficit Round Robin 191
`Configuration ofMDRR 194
`
`Weighted Random Early Detection 195
`Configuration and Monitoring of WRED 197
`
`Selective Packet Discard 198
`
`Other QoS Features 199
`
`Summary 199
`
`Appendix A NetFlow Switching 200
`
`Flow Cache Maintenance 202
`
`Flow Export 204
`Router-Based Flow Aggregation Export (RBA) 205
`
`Index 206
`
`Cisco Systems, Inc.
`Exhibit 1008
`Page 9 of 38
`
`

`

`xii
`
`Introduction
`
`Venture into any bookstore today and you can find numerous books on internetworking covering a wide
`range of topics from protocols to network design techniques. There’s no question that internetworking has
`become a popular field with the enormous growth of the Internet and the increasing convergence of voice,
`video, and data. Cisco has built a very successful business selling the equipment that forms the network
`infrastructure—by some accounts, Cisco has more than 85 percent of the market—and at the same time has
`seen its Cisco IOS Software become a de facto industry standard. Yet, although plenty of material is written
`about network design and the protocols IOS supports, very little information is available from sources other
`than Cisco.
`
`This lack of information is understandable—IOS is proprietary, after all—but it nevertheless leaves network
`implementers at a disadvantage. During our experience helping design and troubleshoot IOS—based net—
`works, we’ve seen many cases where limited IOS architectural knowledge either contributed to a problem or
`made it more difficult to solve. In addition, we collectively have answered countless numbers of questions
`(and dispelled some myths) from bewildered Cisco customers about the workings of various IOS features.
`
`This book is an attempt to bring together, in one place, the wealth of information about the architecture and
`the operation of IOS. Some of this information has been made public previously through forums, Cisco pre~
`sentations, and the Cisco Technical Assistance Center. Most of the information you cannot find in the Cisco
`IOS documentation.
`
`Objectives
`Inside Cisco IOS Software Architecture is intended to be an IOS “shop manua ” for network designers,
`implementers, and administrators. The objective of this book is to describe key parts of the architecture and ‘
`the operation of the IOS software. This book also covers the architecture of some of Cisco’s hardware plat—
`forms. Because IOS is a specialized embedded operating system tightly coupled to the underlying hardware,
`it’s difficult to describe the software without also considering the hardware architecture. Note, however, that
`this book is not meant to be an exhaustive manual for Cisco hardware. The hardware descriptions are pro-
`vided only to help illustrate unique features in the IOS software. You might notice that this book does not
`cover many of the Cisco platforms; in particular, this book does not cover any of the Catalyst switch prod—
`ucts, and it omits many of the access routers. In most cases, the missing platforms either are similar to ones
`that are covered or, in the case of the Catalyst switches, would be best treated in a separate text of their own.
`
`’ 1sco"S‘"ste‘rns-dnc; ,,
`
`
`‘
`
`,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Cisco Systems, Inc.
`Exhibit 1008
`Page 10 of 38
`
`

`

`I
`
`Organization
`The book is divided into three general sections. The first covers the general architecture of IOS, including its
`software infrastructure and packet switching architecture. The second section, beginning with Chapter 3,
`examines the IOS implementations on a few selected Cisco hardware platforms, covering the design and
`operation of the platform-specific features. Finally, Chapter 8 describes how IOS implements select Quality
`of Service (QoS) mechanisms. The book is organized into the following chapters:
`Chapter 1, "Fundamental IOS Software Architecture"-Provides an introduction to operating
`system concepts and then covers the IOS software infrastructure, including processes, memory
`management, CPU scheduling, packet buffers, and device drivers.
`Chapter 2, "Packet Switching Architecture"-Gives an overview of the switching architecture
`and describes the theory of operation of several platform-independent switching methods, includ(cid:173)
`ing process switching, fast switching, optimum switching, and Cisco Express Forwarding.
`Chapter 3, "Shared Memory Routers"-Shows how the features discussed in Chapter 1 and
`Chapter 2 actually are implemented on a platform using the relatively simple shared memory rout(cid:173)
`ers as an example.
`Chapter 4, "Early Cbus Routers"-Covers platform-specific switching features in the IOS
`implementation for the early Cbus routers. Describes the architecture of the AGS+ and Cisco 7000
`routers.
`Chapter 5, "Particle-Based Systems"-Describes the particle-based packet buffering scheme
`using the Cisco 7200 router IOS implementation example. Covers the packet switching implemen(cid:173)
`tation on the Cisco 7200.
`Chapter 6, "Cisco 7500 Routers"-Continues the description of the Cbus architecture focusing
`on the Cisco 7500 router IOS implementation. Also examines the IOS distributed switching imple(cid:173)
`mentation on the Versatile Interface Processor (VIP).
`Chapter 7, "The Cisco Gigabit Switch Router: 12000"-Covers the IOS implementation on the
`Cisco 12000 series routers.
`• Chapter 8, "Quality of Service"-Gives an overview of IOS Quality of Service (QoS) and
`describes several QoS methods, including priority queuing, custom queuing, weighted fair queu(cid:173)
`ing, and modified deficit round robin.
`Appendix A, "NetFlow Switching"-Covers the NetFlow feature in IOS used for traffic monitor(cid:173)
`ing and billing.
`
`Cisco Systems, Inc.
`Exhibit 1008
`Page 11 of 38
`
`

`

`This chapter covers the following key topics:
`
`• Process Switching
`• Fast Switching
`• Optimum Switching
`Cisco Express Forwarding
`
`I
`
`.
`ii
`i
`1:1
`; I;
`iii
`
`Cisco Systems, Inc.
`Exhibit 1008
`Page 12 of 38
`
`

`

`2
`
`Packet Switching Architecture
`
`A multiprotocol router's primary purpose is, of course, to switch packets from one network
`segment to another. If the scheduler and memory manager are the router's software
`infrastructure, then the IOS switching architecture is the router's very foundation. The
`switching methods and structures used by IOS essentially dictate how well the router
`performs its primary task-so, as you can imagine, a great deal of effort has been put into
`designing and refining this important part of IOS.
`
`In spite of all the fanfare surrounding packet switching, the operation itself is fairly
`straightforward:
`
`Step 1 A packet comes into an interface.
`
`Step 2 The packet's destination address is inspected and compared against a list
`of known destinations.
`
`Step 3 If a match is found, the packet is forwarded out the appropriate interface.
`
`Step 4 If a match is not found, the packet is dropped.
`
`Clearly, this isn't rocket science. Indeed, the problem to be solved isn't so much how to
`switch packets, but how to switch them quickly. Switching packets is a data-intensive
`operation as opposed to a computation-intensive one; speeding up the operation isn't as
`simple as just using a faster CPU. Other factors, such as I/O bus performance and data
`memory speed, can have a big impact on switching performance. The challenge for IOS
`developers is to create the highest possible switching performance given the limits of
`available CPU, I/O bus, and memory technology.
`
`As the size and number of routed networks grow, IOS developers continuously look for
`better ways to solve this performance challenge, resulting in a continuous redesign and
`refinement of IOS switching methods. When IOS was first developed, there was only one
`switching method, known today as process switching. Later releases introduced newer
`improved methods of switching; some of these methods rely on hardware-specifiG
`optimizations, others use software techniques that work well on many platforms. Today,
`IOS can switch several hundred thousand packets per second using routing tables
`containing hundreds of thousands of routes.
`
`Cisco Systems, Inc.
`Exhibit 1008
`Page 13 of 38
`
`

`

`42 Chapter 2: Packet Switching Architecture
`
`The following list summarizes the switching methods developed as of Cisco IOS
`Release 12.0:
`
`41 Process switching
`
`• Fast switching
`• Autonomous switching
`• Silicon switching engine (SSE) switching
`
`• Optimum switching
`
`• Distributed fast switching
`• Cisco Express Forwarding (CEF)
`• Distributed Cisco Express Forwarding ( dCEF)
`
`This chapter covers in detail four of these methods-process switching, fast switching,
`optimum switching, and Cisco Express Forwarding (CEF). Autonomous and SSE
`switching are platform-specific and aren't commonly used in today's networks, so they
`aren't covered here. Distributed fast switching is actually an implementation of the
`optimum switching method on intelligent line cards, and isn't covered any further than the
`coverage provided to optimum switching itself.
`
`It's worth noting that although IP routing examples are used here to illustrate the switching
`methods, many of these methods also apply to other network protocols, such as IPX and
`bridging. Although the structures used are often independent for each protocol (for
`example, there is a separate Fast Cache for IP and IPX), the contents of the switching
`structures are similar, and switching occurs in essentially the same way for each protocol.
`
`Routing 101: Process Switching
`Process switching was the first switching method implemented in IOS. Basically, it uses the
`brute-force method to switch packets. Although process switching contains the least
`amount of performance optimizations and can consume large amounts of CPU time, it does
`have the advantage of being platform-independent, making it universally available across
`all Cisco !OS-based products. Process switching also provides some traffic load sharing
`capabilities not found in most of the other switching methods, which are discussed in detail
`in the section, "Traffic Load Sharing with Process Switching."
`
`To understand just how process switching works, take a look at the steps required to process
`switch a packet. Figure 2-1 illustrates the process-switched path for an IP packet.
`
`Cisco Systems, Inc.
`Exhibit 1008
`Page 14 of 38
`
`

`

`Routing 101: Process Switching
`
`43
`
`Figure 2-1
`
`The Process Switched Path
`
`ip_input
`
`4
`
`5
`
`2
`
`1/0 memory
`
`6
`
`Interface Processor
`
`(:~~~
`ed1a_J
`-----··
`This example begins with the network interface on the router sensing there is a packet on
`the wire that needs to be processed. The interface hardware receives the packet and transfers
`it into input/output (I/O) memory-Step 1 in Figure 2-1.
`
`The network interface interrupts the main processor, telling it there is a received packet
`waiting in I/O memory that needs to be processed; this is called the receive interrupt. The
`IOS interrupt software inspects the packet's header information (encapsulation type,
`network layer header, and so on), determines that it is an IP packet, and places the packet
`on the input queue for the appropriate switching process-Step 2 in Figure 2-1. For IP
`packets, the switching process is named ip_input.
`
`After at least one packet is in the input queue of the ip_input process, ip_input becomes
`eligible to run-Step 3 in Figure 2-1.
`
`After the ip_input process is running (Step 4 in Figure 2-1), the actual packet-forwarding
`operation can begin. It is here that all the decisions are made about where to direct the
`received packet. In this example, ip_input looks in the routing table to see whether a route
`exists to the destination IP address. If one is found, it retrieves the address of the next hop
`(the next router in the path or the final destination) from the routing table entry. It then looks
`into the ARP cache to retrieve the information needed to build a new Media Access Control
`(MAC) header for the next hop. The ip_input process builds a new MAC header:, writing
`over the old one in the input packet. Finally, the packet is queued for transmission out the
`outbound network interface-Step 5 in Figure 2-1.
`
`g,
`
`~y
`
`:i the
`
`hing
`md
`
`)COL
`
`s the
`
`does
`ross
`ng
`etail
`
`cess
`
`Cisco Systems, Inc.
`Exhibit 1008
`Page 15 of 38
`
`

`

`44 Chapter 2: Packet Switching Architecture
`
`When the outbound interface hardware senses a packet waiting for output, it dequeues the
`packet from I/O memory and transmits it on to the network-Step 6 in Figure 2-1. After the
`outbound interface hardware finishes transmitting the packet, it interrupts the main
`processor to indicate that the packet has been transmitted. IOS then updates its outbound
`packet counters and frees the space in I/O memory formerly occupied by the packet. This
`is the final step in Figure 2-1, Step 7.
`
`Traffic load Sharing with Process Switching
`One of the advantages of process switching is its per-packet load sharing capability. Per(cid:173)
`packet load sharing provides a relatively simple way to route traffic over multiple links
`when multiple routes (paths) exist to a destination. When multiple paths exist, process(cid:173)
`switched packets are automatically distributed among the available paths based on the
`routing metric (referred to as the path cost) assigned to each path.
`
`The metric or cost of each path in the routing table is used to calculate a load share counter,
`which is actually used to determine which path to take. To better understand how this
`works, take a look at Figure 2-2.
`
`Figure 2-2 Traffic Sharing Across Equal Cost Paths
`
`Packets 1, 3, 5, 7, 9 ...
`
`""' 10.1.3.0/24
`~·~
`
`!l>".1/
`A /
`10.1.2.0/24
`Packets 2, 4, 6, 8, 10 ...
`
`B
`
`10.1 .4.0/24
`
`Router A has two paths to the 10.1.4.0/24 network (as illustrated in Figure 2-2). From the
`output in Example 2-1, you can see these are equal-cost paths.
`
`Example 2-1 Routing Table for Router A in Figure 2-2
`
`RouterA#show ip route 10.1.4.0 255.255.255.0
`Routing entry for 10.1 .4.0/24
`Known via "static", distance 1, metric 0
`Routing Descriptor Blocks:
`10.1 .2.1
`Route metric is 0, traffic share count is 1
`* 10.1 .3 .1
`Route metric is 0, traffic share count is
`
`Note the asterisk (*) next to one of the two network paths in Example 2-1. This indicates
`the path that will be used for the next packet switched toward 10.1.4.0/24. The traffic-share
`
`Cisco Systems, Inc.
`Exhibit 1008
`Page 16 of 38
`
`

`

`~ues the
`lfter the
`l
`~bound
`~t. This
`
`f. Per(cid:173)
`inks
`:ess(cid:173)
`the
`
`ounter,
`1is
`
`m the
`
`:ates
`;hare
`
`Routing 101: Process Switching
`
`45
`
`count on both paths is 1, meaning packets are switched out each path in a round-robin
`fashion.
`
`In this example, the very next packet arriving for this network will be routed to next
`hop 10.1.3.1. The second packet arriving will be routed to next hop 10.1.2.1, the third to
`10.1.3.1, and so on (as shown by the packet numbers in Figure 2-2).
`
`Some IP routing protocols, in particular Interior Gateway Routing Protocol (IGRP) and
`Enhanced IGRP (EIGRP), can install unequal cost paths in the routing table; in cases where
`path costs differ, the traffic-sharing algorithm changes slightly. If a link is changed in the
`setup in Figure 2-2, for example, so one path has about twice the bandwidth of the other,
`the resulting network is shown in Figure 2-3.
`
`Figure 2-3 Traffic Sharing Across Unequal Cost Paths
`
`Packets 1, 2, 4, 5, 7 ...
`
`""' 10.1.3.0/24
`"®. ,f,..
`
`.2
`
`10.1.4.0/24
`
`B
`
`The routing table would look something like Example 2-2.
`
`Example 2-2 Routing Table for Router A in Figure 2-3
`
`RouterA#show ip route 10.1.4.0 255.255.255.0
`Routing entry for 10.1 .4.0/24
`Known via 'EIGRP', distance 90, metric 284600
`Routing Descriptor Blocks:
`10.1 .2.1
`Route metric is 569200, traffic share count is
`* 10.1 .3 .1
`Route metric is 284600, traffic share count is 2
`
`Note the traffic share counts in this show ip route output. The lower-cost path through
`10.1.3.1 has a traffic share count of 2; the higher-cost path through 10.1.2.1 has a traffic
`share count of 1. Now for every two packets switched out the higher-cost path, one packet
`is switched out the lower-cost path, as indicated by the packet numbers in Figure 2-3.
`
`NOTE
`
`Although per-packet traffic sharing is very good at balancing traffic load across multiple
`links, it does have one significant drawback: It can result in packets arriving out of order at
`the destination. This is especially true if there is a wide variation in latency among the
`available routes. Out-of-order packet processing can significantly degrade end-station
`performance.
`
`Cisco Systems, Inc.
`Exhibit 1008
`Page 17 of 38
`
`

`

`46 Chapter 2: Packet Switching Architecture
`
`Disadvantages of Process Switching
`As noted before, a key disadvantage of process switching is its speed-or lack thereof.
`Process switching requires a routing table lookup for every packet; as the size of the routing
`table grows, so does the time required to perform a lookup (and hence the total switching
`time). Recursive routes require additional lookups in the routing table (to resolve the
`recursion), increasing the length of the lookup time.
`
`Longer lookup times also increase the main processor utilization, an effect multiplied by
`the incoming packet rate. Although this effect might not be noticeable on very small
`networks with few routes, large networks can have hundreds or even thousands of routes.
`For these networks, routing table size can significantly impact main processor utilization
`and routing latency (the delay between the time the packet enters and exits the router).
`
`Another major factor affecting process-switching speed is in-memory data transfer time.
`On some platforms, process switching requires received packets to be copied from I/O
`memory to another memory area before they can be switched. After the routing process
`finishes, the packets must be copied back to I/O memory before being transmitted. Memory
`data copy operations are very CPU intensive, so on these platforms, process switching can
`be a very poor performer.
`
`It became quite clear to the early IOS developers that a better switching method would be
`required if IOS was to be viable in the world of ever-growing routed networks. To
`understand the solution they devised, take a look at some of the more obvious areas for
`improvement in process switching.
`
`Looking back at the IP process switching example, the ip_input process needs three key
`pieces of data to switch the packet:
`
`•
`
`• Reachability-Is this destination reachable? If so, what is the IP network address of
`the next hop toward this destination? This data is in the routing table (also called the
`forwarding table).
`Interface-W