USOO7382787B1
`
`(12) United States Patent
`Barnes et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,382,787 B1
`Jun. 3, 2008
`
`(54) PACKET ROUTING AND SWITCHING
`DEVICE
`
`(75) Inventors: Peter M. Barnes, Mountain View, CA
`(US); Nikhil Jayaram, Los Altos, CA
`(US); Anthony J. Li, San Mateo, CA
`(US); William L. Lynch Redwood
`City, CA (US); Sharad Mehrotra, San
`Jose, CA (US)
`
`(73) Assignee: Cisco Technology, Inc., San Jose, CA
`(US)
`
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 1044 days.
`
`(21) Appl. No.: 10/177,496
`(22) Filed:
`Jun. 20, 2002
`O
`O
`Related U.S. Application Data
`(60) Provisional application No. 60/309,042, filed on Jul.
`30, 2001, provisional application No. 60/309,087,
`filed on Jul. 30, 2001.
`
`(51) Int. Cl.
`(2006.01)
`H04L 2/28
`(52) U.S. Cl. ....................... 370/401; 370/414; 370/473
`(58) Field of Classification Search ................ 370/392,
`370/389, 349,395.31
`See application file for complete search history.
`References Cited
`U.S. PATENT DOCUMENTS
`
`(56)
`
`6/1996 Corby, Jr. et al.
`5,524.258 A
`3/1998 Carvey et al.
`5,734,649 A
`7/1998 Wilkinson, III et al. .... 395/600
`5,781,772 A
`9, 1998 Isfeld et al.
`5,802.278 A
`5,838,894 A 11, 1998 Horst
`5,905,725 A
`5/1999 Sindhu et al. .............. 370,389
`
`6/1999 Ferguson et al. ........... 370,389
`5,909,440 A
`7/1999 Higgins et al.
`5,923,643 A
`7/1999 Greene et al.
`5,930,256 A
`1/2000 Varghese et al. ............ 370/392
`6,011,795. A
`1, 2000 Turner et al. .....
`... 370,392
`6,018,524. A
`6/2000 Civanlar et al. ...
`... 709,238
`6,078,963 A
`7, 2000 Cheri
`6,091.725 A
`eriton et al. ..
`... 370,392
`W-1 r.
`8/2000 Wakeland ................... 370,429
`6, 101,192 A
`6,161,139 A 12/2000 Win et al.
`6,308,219 B1* 10/2001 Hughes ...................... TO9,238
`6,430,181 B1
`8/2002 Tuckey
`6,453,413 B1
`9, 2002 Chen et al.
`6,526,055 B1* 2/2003 Perlman et al. ............. 370,392
`
`(Continued)
`OTHER PUBLICATIONS
`"Xelerated Packet Devices'. MicroDesign Resources Presentation,
`Network Processor Forum, pp. 1-11. (Jun. 14, 2001).
`(Continued)
`Primary Examiner Chau Nguyen
`Assistant Examiner Kenneth R Hartmann
`(74) Attorney, Agent, or Firm—Schwegman, Lundberg &
`Woessner, P.A.
`
`(57)
`
`ABSTRACT
`
`A method for routing and Switching data packets from one
`or more incoming links to one or more outgoing links of a
`router. The method comprises receiving a data packet from
`the incoming link, assigning at least one outgoing link to the
`data packet based on the destination address of the data
`packet, and after the assigning operation, storing the data
`packet in a Switching memory based on the assigned out
`going link. The data packet extracted from the Switching
`memory, and transmitted along the assigned outgoing link.
`The router may include a network processing unit having
`one or more systolic array pipelines for performing the
`assigning operation.
`
`29 Claims, 56 Drawing Sheets
`
`40
`
`input-Side of
`Interface
`Subsystem
`NPU)
`
`Perform forwarding table
`look-up using systolic
`amay pipeline to
`determire the outputport
`for the packet
`420
`
`Striper)
`
`wide packet into cells
`pa
`
`Switching Engine
`
`(NCU)
`
`Store cells contiguously
`in memory as function of
`output
`
`Qutput-Sids of
`E.
`Subsystem (LCU)
`
`Extracticells for
`memory; and reassemble
`packet
`480
`
`
`
`transmit packet from
`cutpi
`499
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 1 of 94
`
`

`

`US 7,382,787 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`10/2003 Greene
`6,631,419 B1
`12/2003 Ross et al.
`6,658,002 B1
`1/2004 Greenberger
`6,675, 187 B1
`2/2004 Wynne et al.
`6,687,781 B2
`6,721.316 B1* 4/2004 Epps et al. ................. 370,389
`6,731,633 B1
`5, 2004 Sohor et al.
`6,732,203 B2
`5/2004 Kanapathippillai et al.
`6,751,191 B1
`6/2004 Kanekar et al.
`6,778.490 B1
`8, 2004 Achilles et al.
`6,785,728 B1
`8, 2004 Schneider et al.
`6,795,886 B1
`9/2004 Nguyen
`6,801.950 B1
`10/2004 O'Keeffe et al.
`6,804.815 B1
`10/2004 Kerr et al.
`6,879,559 B1
`4/2005 Blackmon et al.
`6,922,724 B1
`7/2005 Freeman et al.
`6,944, 183 B1
`9/2005 Iyer et al.
`6,944,860 B2
`9, 2005 Schmidt
`6,961,783 B1
`1 1/2005 Cook et al.
`6,965,615 B1 * 1 1/2005 Kerr et al. .................. 370/474
`6,973,488 B1
`12/2005 Yavatkar et al.
`6,990,527 B2
`1/2006 Spicer et al.
`7,006.431 B1
`2, 2006 Kanekar et al.
`7,020,718 B2
`3, 2006 Brawn et al.
`7,028,098 B2
`4/2006 Mate et al.
`7,043,494 B1
`5, 2006 Joshi et al.
`7,051,039 B1
`5/2006 Murthy et al.
`7,051,078 B1
`5, 2006 Cheriton
`7,054,315 B2
`5, 2006 Liao
`7,054,944 B2
`5/2006 Tang et al.
`7,073,196 B1
`7/2006 Dowd et al.
`7,095,713 B2
`8, 2006 Willhite et al.
`7,103,708 B2
`9, 2006 Eatherton et al.
`7,111,071 B1* 9/2006 Hooper ....................... TO9,238
`7,124,203 B2 10/2006 Joshi et al.
`7,139.238 B2 11/2006 Hwang
`7,155,518 B2 12/2006 Forslow
`7,159,125 B2
`1/2007 Beadles et al.
`7,185.365 B2
`2/2007 Tang et al.
`7,200,144 B2
`4/2007 Terrell et al.
`7,200,865 B1
`4/2007 Roscoe et al.
`7,203,171 B1
`4/2007 Wright
`7,225,204 B2
`5/2007 Manley et al.
`7,225,263 B1
`5/2007 Clymer et al.
`7,227,842 B1
`6, 2007 Ji et al.
`7,230,912 B1
`6, 2007 Ghosh et al.
`7,231,661 B1
`6, 2007 Villavicencio et al.
`7,239,639 B2
`7/2007 Cox et al.
`7,249,374 B1
`7/2007 Lear et al.
`7,257,815 B2
`8/2007 Gbadegesin et al.
`7,274,702 B2
`9, 2007 Toutant et al.
`7,280,975 B1 10/2007 Donner
`7,302,701 B2 11/2007 Henry
`3, 2002 Xu
`2002.0035639 A1
`6, 2003 Sindhu et al.
`2003/0108056 A1
`8, 2003 Bunce et al.
`2003,0163589 A1
`2/2004 Davis et al.
`2004.0024.888 A1
`6/2006 Leung et al.
`2006/0117126 A1
`2006, O159034 A1
`7/2006 Talur et al.
`
`OTHER PUBLICATIONS
`Cataldo, Anthony, "Net Processor Startup Takes Pipelined Path to
`40 Gbits/s'.
`EE Times,
`http://www.eetimes.com/story/
`OEG20010702S0061, (Jul. 2, 2001).
`Kung, H. T. et al. “Algorithms for VLSI Processor Arrays'. In
`Introduction to VLSI Systems, Mead C. et al., Eds. Addison-Wesley,
`Reading, Mass., pp. 271-292 (1980).
`Partridge, Craig et al., “A 50-Gb's Router", IEEE/ACM Transac
`tions on Networking, vol. 6, No. 3, (Jun. 1998).
`
`Degermark, Mikael et al., “Small Forwarding Tables for Fast
`Routing Lookups', Lulea University of Technology, (date
`unknown).
`Lampson, B. et al., “IP Lookups Using Multiway and Multicolumn
`Search”. (Aug. 1, 1997).
`Gupta, Pankaj et al., “Routing Lookups in Hardware at Memory
`Access Speeds', Stanford University, IEEE Infocom http://www.
`Stanford.edu, (Apr. 1998).
`McAuley, Anthony J. et al., “Fast Routing Table Lookup Using
`CAMs'. http://www.citeseer.nj.nec.com, Infocom '93, (Mar.-Apr.
`1993).
`Lindberg, Klaus, Multi-gigabit Routers, http://www.tml.hut.fi/
`Opinnot/Tik-1 10.551/1998/papers, (May 3, 1998).
`Belenkiy, Andrey, “Deterministic IP Table Lookp at Wire Speed”.
`New Jersey Institute of Technology, http://www.isoc.org/inet 99/
`proceedings/4/4, 2.htm, (printed Jul. 24, 2000).
`Chiueh, Tzi-cker et al., “High-Performance IP Routing Table
`Lookup Using CPU Caching”, State University of New York,
`Proceedings of IEEE Infocom, http://citeseer.nj.nec.com/216222.
`html, (1999).
`Waldvogel, Marcel et al., “Scalable High Speed IP Routing Look
`ups”. Computer Engineering and Networks Laboratory, http://
`citeseer.nj.nec.com/did/12751. (1997).
`“What's Inside a router?', http://www-net.cs.umass.edu/kurosefnet
`work inside/inside.htm, (observed Aug. 29, 2005), 11 pgs.
`Gupta, P. et al., “Classifying Packets with Hierarchical Intelligent
`Cuttings”, IEEE Micro, 21 (I), (Jan./Feb. 2000), 34-41.
`Gupta, P. et al., “Packet Classification on Multiple Fields'. Pro
`ceedings of the Conference On Applications, Technologies, Archi
`tectures, and Protocols for Computer Communication (ACM
`SIGCOMM '99), (1999), 147-160.
`Lakshman, T.V., et al., “High-Speed Policy-Based Packet Forward
`ing Using Efficient Multi-Dimensional Range Matching”. Proceed
`ings of the Conference on Applications, Technologies, Architectures,
`and Protocols for Computer Communications (ACM SIGCOMM
`'98), (1998), 203-214.
`Qui. L., et al., “Fast Firewall Implementations for Software and
`Hardware-Based Routers'. Microsofi Technical Report MSR-TR
`2001-61. (Jun. 2001), 18 pgs.
`Srinivasan, V., et al., “Fast and Scalable Layer Four Switching”.
`Proceedings of the Conference on Applications, Technologies,
`Architectures, and Protocols for Computer Communications (ACM
`SIGCOMM '98), (1998), 191-202.
`Srinivasan, V., et al., “Packet Classification Using Tuple Space
`Search'. Proceedings of the Conference on Applications, Technolo
`gies, Architectures, and Protocols (ACM SIGCOMM 99), (1999),
`135-146.
`“U.S. Appl. No. 10/177,187, Final Office Action mailed Jun. 29,
`2005”, 9 p.
`“U.S. Appl. No. 10/177, 187, Non-Final Office Action mailed Nov.
`18, 2004”, 13 p.
`“U.S. Appl. No. 10/177, 187, Notice of Allowance mailed Sep.
`22, 2005”, 6 p.
`“U.S. Appl. No. 10/177,187, Response filed Apr. 18, 2005 to
`Non-Final Office Action mailed Oct. 18, 2004, 9 p.
`“U.S. Appl. No. 10/177, 187, Response filed Aug. 29, 2005 to Final
`Office Action mailed Oct. 18, 2004'', 10 p.
`“U.S. Appl. No. 10/407.528 Non-Final Office Action mailed Jun.
`29, 2007, 20 p.
`“U.S. Appl. No. 10/414, 133, Final Office Action mailed Aug. 8,
`2007”. 13 p.
`“U.S. Appl. No. 10/414,133, Non-Final Office Action mailed Feb.
`23, 2007, 11 p.
`“U.S. Appl. No. 10/414,133, Response filed May 22, 2007 to
`Non-Final Office Action mailed Feb. 23, 2007, 9 p.
`“U.S. Appl. No. 10/414.135 Final Office Action mailed Sep. 11,
`2007, 25 p.
`“U.S. Appl. No. 10/414, 135. Non-Final Office Action mailed Mar.
`8, 2007”. 10 p.
`“U.S. Appl. No. 10/414, 135, Response filed Jun. 5, 2007 to Non
`Final Office Action mailed Mar. 8, 2007”. 10 p.
`“U.S. Appl. No. 10/414,137. Final Office Action mailed Sep. 11,
`2007, 3 p.
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 2 of 94
`
`

`

`US 7,382,787 B1
`Page 3
`
`“U.S. Appl. No. 10/418,634. Non-Final Office Action mailed Sep.
`14, 2007, 21 p.
`Ballardie, A., "Core Based Trees (CBT) Multicast Routing Archi
`tecture'. RFC 2201, (Saptember 1997), 1-15.
`Finseth, C. "An Access Control Protocol, Sometimes Called
`TACACS”, RFC 1492, (Jul 1993), 1-21.
`Kille, S., “Representing the O.R. Address Heirarchy in the X.500
`Directory Information Tree'. RFC 2294, (Mar. 1998), 1-13.
`
`Myers, J., “IMAP4 ACL Extension”, RFC 2086, (Jan. 1997), 1-8.
`Stokes, E., et al., “Access Control Requirements for LDAP'. RFC
`2820, (May 2000), 1-9.
`Wijnen, B. et al., “View-Based Access Control Model (VACM) for
`the Simple Network Management Protocoi (SNMP)'. RFC 2575,
`(Apr. 1999), 1-38.
`* cited by examiner
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 3 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 1 of 56
`
`US 7,382,787 B1
`
`
`
`Fig.
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 4 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 2 of 56
`
`US 7,382,787 B1
`
`22
`
`22
`
`interface
`SubsystemO
`
`2O
`-/.
`
`interface
`Subsystem
`
`22.
`
`Switching Engine0
`
`Switching Enginet
`
`Switchting Engine2
`
`24
`
`24
`
`
`
`Fig.2
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 5 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 3 of 56
`
`US 7,382,787 B1
`
`Destination
`
`Packet
`interface
`(IP Destination Address) ? Subsystem
`
`Packet
`aCKG ?
`
`
`
`Media Adapters
`
`
`
`
`
`
`
`
`
`
`
`NetWork
`Processing
`Unit (NPU)
`
`24
`
`Line Card Unit
`(LCU)
`
`ti------ Packet (Queue). T els-HI
`
`Cells
`
`
`
`Cells
`
`Cells
`
`/ 42.
`
`Switching Memory (Queues)
`
`V Switching Engine
`
`Fig. 3A
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 6 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 4 of 56
`
`US 7,382,787 B1
`
`
`
`
`
`
`
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 7 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 5 of 56
`
`US 7,382,787 B1
`
`Receive packet on input
`400
`
`- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ----------------------------------- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
`
`Input-Side of
`interface
`Subsystem
`(NPU)
`
`
`
`Perform forwarding table
`look-up using Systolic
`array pipeline to
`determine the output port
`for the packet
`420
`
`(Striper)
`
`Divide packet into cells
`440
`
`Switching Engine
`
`(MCU)
`
`Store cells Contiguously
`in memory as function of
`Output
`460
`
`:
`
`Output-Side of
`interface
`Subsystem (LCU)
`
`Extract Cells from
`memory; and reassemble
`packet
`480
`
`Transmit packet from
`Output
`499
`
`Fig. 4
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 8 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 6 of 56
`
`US 7,382,787 B1
`
`
`
`Receive packet from
`incoming tink
`402
`
`Media Adapter
`
`Format packet for
`processing by NPU
`404
`
`Transmit packet to NPU
`406
`
`-
`
`Fig. 5A
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 9 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 7 of 56
`
`US 7,382,787 B1
`
`
`
`Parse packet header to extract IP destination address
`422
`
`:
`
`First Parti
`Pe. ca Perform IOD table look-up using systolic array pipeline
`(PxU)
`424
`
`
`
`
`
`
`
`
`
`Second Partial
`Packet Context
`(LxtJ)
`
`Perform VLAN table look-up using systolic array pipeline
`426
`
`Perform forwarding table look-up using systolic array
`pipeline to assign base queue for packet
`428
`
`
`
`
`
`
`
`
`
`Additional stroke
`430
`
`INI
`Peform metering
`432
`
`
`
`
`
`Final
`
`: Packet Context
`(QxU)
`
`
`
`
`
`Peform QOS using systolic array pipeline to assign output
`queue (output) to packet
`434
`
`0.
`
`A
`
`- - - - - - - - - - - - - - - - - - ---------------------------------------------------------------------------------------------------------------------------------
`
`Fig. 5B On D
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 10 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 8 of 56
`
`US 7,382,787 B1
`
`
`
`
`
`
`
`
`
`Receive packet from NPU, the
`packet having a context defining
`the destination gueue for the
`packet
`442
`
`Update detta count table with
`number of cetts packetwitt be
`divided into, and the destination
`queue for the packet
`443
`
`Periodicatly communicate
`detta Count table
`information to LCU
`
`Divide packet into cells
`(34 Byte)
`444
`
`Output stripe cells to attats
`buffer
`446
`
`Output stripe cells to MCUs
`448
`
`Fig. 5C
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 11 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 9 of 56
`
`US 7,382,787 B1
`
`
`
`Receive output striped
`Cells from
`at tatts buffer
`462
`
`Store cells contiguously in
`destination queue
`464
`
`Fig. 5D
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 12 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 10 of 56
`
`US 7,382,787 B1
`
`
`
`Request queue from
`Switching engine
`482
`
`Receive cells
`484
`
`Reassemble the packet
`486
`
`Perform encapsulation
`and fragmentation
`488
`
`Transmit packet to media
`adapter
`
`Transmit packet on
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 13 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 11 of 56
`
`US 7,382,787 B1
`
`Media Adapters
`
`22.
`---4. ---
`32.
`OC-192
`1
`Phy3
`
`OX
`Gigabit
`Ethernet
`Phyo
`
`inahal
`get
`E.
`y1
`
`44
`
`44
`
`4e
`
`; 44
`
`4e
`
`; 44
`4e
`
`4e
`
`Glue Asic
`
`t
`
`tue Asic
`
`Glue Asic
`
`Glue Asic
`
`
`
`NPU
`
`:
`
`LCU
`
`Fig. 6
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 14 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 12 of 56
`
`US 7,382,787 B1
`
`High Speed
`Point-to-Point (ez)
`Connection(s)
`
`Packets in
`
`7e
`
`40Gbps
`
`40Gbps
`
`(
`
`40Gbps
`y
`
`40Gbps
`l
`
`input Packet Arbiter
`
`40Gbps
`it.
`Header Sequencer
`
`
`
`e2
`
`ee
`
`s
`d
`Recirculation
`Packet Queue
`
`:
`:
`
`NPU
`
`24
`
`RP
`Packet
`Buffer
`
`System
`interface
`
`3o
`
`62
`43
`
`63
`
`
`
`
`
`
`
`
`
`
`
`Packet Header
`Parsing Execution Unit
`(PxU)
`Packet Context
`Lookup Execution Unit
`(LXU)
`
`Queuing Execution Unit
`(QxU)
`
`74
`
`g
`VLAN
`IOD Table
`
`
`
`On-Chip
`F
`E. i
`SRAM
`
`External
`SRAM
`interface
`
`
`
`Modified
`Packet Context
`
`Packets Out
`3CKeSUU
`
`High Speed
`Point-to-Point (82)
`Connection(s)
`
`Fig. 7A
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 15 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 13 of 56
`
`US 7,382,787 B1
`
`
`
`Packets in
`
`Media
`32
`U Adapter
`
`22.
`
`Media
`Adapter
`
`22
`
`32
`
`Media
`Adapter
`
`Media
`Adapter
`T
`NPU \
`:----------------------------- 10 Gbps----------- 10Gbps -----------10 Gbps------------ 10Gbps-------
`:
`t
`input
`Packet
`Buffer
`
`2.
`
`
`
`input
`Packet
`Buffer
`
`2.
`
`72
`
`72
`input U input
`Packet
`Packet
`Buffer
`Buffer
`
`
`
`
`
`a
`
`24
`-
`
`40Gbps
`
`|
`40Gbps
`t
`
`- I
`40Gbps
`4.
`
`40 Gbps
`
`
`
`
`
`2é
`
`RP
`Packet
`Buffer
`
`input Packet Arbiter
`
`40Gbps
`
`Header Sequencer
`
`Packet Header
`Parsing Execution Unit
`(PxU)
`Packet Context
`Lookup Execution Unit
`(LXU)
`
`2e
`
`92.
`
`42
`
`Queuing Execution Unit
`(QxU)
`Modified
`Packet Context
`
`ec)
`
`
`
`
`
`
`
`68
`ee
`
`Recirculation
`Packet Cueue
`
`re
`WLAN/
`iOD Table
`
`4t
`64
`
`On-Chip
`F
`di
`E. g
`SRAM
`
`
`
`
`
`External
`SRAM
`interface
`
`i---------- Packet-ri----------------r---------------------------------- -------------
`24
`Switching Engine
`4.
`Ext.
`SRAM
`
`Fig. 7B
`
`Packets Out
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 16 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 14 of 56
`
`US 7,382,787 B1
`
`
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 17 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 15 of 56
`
`US 7,382,787 B1
`
`SCA
`SA
`?
`SJ
`Reg Fle E functual E funcun El Funcun
`s
`III IIIT III
`TITL-IIII se
`reve
`
`Reg Fie C Fict
`
`Funct O
`
`
`
`s2.
`
`-
`s: Regree Erua E route
`s
`III III IIH II III
`
`as
`
`III
`
`OGM
`
`in
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 18 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 16 of 56
`
`US 7,382,787 B1
`
`3e
`
`ge
`
`s-
`
`22
`
`Eton 3
`Bt
`8
`
`Register
`Fe
`
`3
`3.
`O
`
`Execution
`Oatapath
`
`O
`
`
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 19 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 17 of 56
`
`US 7,382,787 B1
`
`1632 Pew
`RF mage
`
`Prev Adder Result
`
`Pew Stiftet Resust
`Prew Logic/Edge Result
`
`
`
`6x4 Write
`Cit
`
`7KO Read
`Cit
`
`6x32 Next
`RF mage
`
`62.
`
`text. Adder Stoc
`ext Addesc2
`Next Siter SrC1
`Next Stifter SC2
`Next LogBogesic
`Next Odge Stica
`
`fektzerodet sect
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 20 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 18 of 56
`
`US 7,382,787 B1
`
`
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 21 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 19 of 56
`
`US 7,382,787 B1
`
`
`
`9
`
`
`
`
`
`
`
`C
`.9
`3
`C
`te
`wi
`c
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 22 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 20 of 56
`
`US 7,382,787 B1
`
`S11
`
`F
`
`r e A
`4. A 2
`
`Qeea
`
`Na2A
`
`S2:12
`
`F
`Buff
`
`Decode
`
`D
`u
`Register
`File
`
`222
`
`
`
`3A
`
`Decode
`
`S-4
`
`22
`
`ti
`E
`Datapath
`
`NeoA
`
`E
`Execution
`Datapath
`
`
`
`S3;3
`7
`AAC
`
`Buff
`
`82d
`
`Decode
`
`Register
`
`Decode
`
`923.
`
`-1
`22c
`
`
`
`S4;4
`-7
`24b
`
`222
`
`Decode
`
`Register
`File
`
`Decode
`
`Execution
`Datapath
`
`3)
`
`Fig. 13A
`
`23D
`
`
`
`inst2
`inst 3
`
`
`
`...
`...
`
`F
`...
`
`D
`F
`
`low
`
`
`
`E W
`D
`E
`
`Time -->
`
`Fig. 13B
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 23 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 21 of 56
`
`US 7,382,787 B1
`
`
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 24 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 22 of 56
`
`US 7,382,787 B1
`
`
`
`Parity Error
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 25 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 23 of 56
`
`US 7,382,787 B1
`
`AO
`
`\AO
`
`
`
`
`
`
`
`Major Stage
`
`Major Stage Stage
`
`Major Stage
`
`Major Stage
`
`Fig. 16
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 26 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 24 of 56
`
`US 7,382,787 B1
`
`
`
`
`
`
`
`Cycle 7
`
`Newpacket arrives every 3 cycles
`
`Fig. 17
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 27 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 25 Of 56
`
`US 7,382,787 B1
`
`
`
`RP
`
`Seage.
`
`(42)
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 28 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 26 of 56
`
`US 7,382,787 B1
`
`
`
`From
`RP
`
`tes
`
`To OxUppe
`
`t 2
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 29 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 27 Of 56
`
`US 7,382,787 B1
`
`
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 30 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 28 of 56
`
`US 7,382,787 B1
`
`Forwarding Table
`- (SRAM)
`(64)
`
`
`
`
`
`to N toN-ot is Y-tuo Nuvo Nuo Yi to
`
`
`
`
`
`
`
`
`
`
`
`Major stage 1 Od)
`Major
`0 Co)
`
`Major stage 11 Gats)
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 31 of 94
`
`

`

`U.S. Patent
`
`Jun.3, 2008
`
`Sheet 29 of 56
`
`US 7,382,787 B1
`
`Flow
`Data
`
`
` RQ
`S$aw
`
`MMA
`MXQUO
`QQGW
` QAQ_QQ_Qq
`RQ_avr 8
`99444
`XQQGQ°[_™$@§™
`MQAN
`QG®AAA
`
`QQGU
`
`-—- EEN
`
`
`Aag
`Ua Re
`Z
`
`
`Y L
`
`
`ForwardingTable
` Wy
`
` ActiveMinorStages
`
`aanecneen<2pean
`
`
` VW
`QQQQ
`OMAN
`
`YQQAQAQQ@DB
` BRS
`YQQaQQaqg
`U.
`MAG
`
`SQQQAQAA
`QQ
`MXQAGW
`
`
`
`<zpo0
`<sfo~<
`LEM co
`
`
`
`]W
`
`Fig.22
`
`
`Stage(no)
`
`
`Ex. 1015
`CISCO SYSTEMS, INC./ Page 32 of 94
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 32 of 94
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 30 of 56
`
`US 7,382,787 B1
`US 7,382,787 B1
`
`an\
`
`ohn!)
`
`Oh)Ohl
`
`
`
`
`
`yOoyJeuIO
`
`SOPON
`
`ez‘Big
`
`
`
`Yh)(@PON300%)
`
`ovo
`
`Wh|
`
`eu‘ONWas
`
`(}@pON)
`
`Bs|
`
`JANI
`
`Ex. 1015
`CISCO SYSTEMS, INC./ Page 33 of 94
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 33 of 94
`
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 31 of 56
`
`US 7,382,787 B1
`
`
`
`
`
`
`
`
`
`
`
`Parse most significant 12 bits of
`P destination to obtain location
`of the root node of the trie
`Search
`
`Read root node; set current
`node <- rootnode
`
`4-8
`
`So
`
`
`
`- é2.
`
`Extract Queue
`ED
`
`Address Match?
`
`
`
`Any R-Bit = 1
`
`Compute Branch Address
`
`FoWard to RF
`
`
`
`Branch Address E OR
`
`Read next node; get current
`node <--next node
`
`
`
`AS2s
`
`Fig.24
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 34 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 32 of 56
`
`US 7,382,787 B1
`
`e
`
`Text String -le
`
`R
`
`Branch Address B-Field
`
`Root Node
`
`7
`S.
`SRAM_NO
`
`79.
`- ?.
`0 0 1
`
`8O
`
`(
`1
`
`(82.
`
`SRAM N1
`
`01
`
`Node 1
`
`SRAM_NO+1 - -
`
`OO
`
`Node 2
`
`
`
`
`
`
`
`o
`
`Longest Prefix
`Match
`
`Node 5
`
`Node 6
`
`Fig. 25
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 35 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 33 of 56
`
`US 7,382,787 B1
`
`
`
`
`
`
`
`
`
`
`
`
`folayOF68l9gy€z|0iInow!l|now!Inow!][now][now][nownow!Inow!|now![now][now]jnow
`hehehebebebene1
`
`
`
`
`SOQD0PerrSAGOP--reneneeeeeeeSAGOPrrereereeereSASOpererrerrerSUDOprenseoroneerseeSOGOOpnSAGOPreeSU
` Suyyoums\[evUveeeeeeerenuerTUTTITYOUsTCIUNNTTENNCreCNSEYOeSYOeOET,PPECEETEESETEUEELYOYPSECUTENTETUEUUETRETTHTETYTTT:creerFETTOTeTSOsHHewessEReuTerNseeewesseRENECUESOWECCETEUNITYECLYYEVELINaTETHUNTETEUEEEY
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`sdgoozsdqoozsdagozsdqgozsdaoozsdqoozsdaoozsdqmozsdqgozsdqoozsdqaozsdaooz
`LZNdN=SNdNPNdNENdNiminaONdN
`bbOL68Z9gv€&b0alvalyaLV@LVdlvalyaLlvalvalyalyalyalv
`9OhOnah©ohohon2onohobb2
`C22"eto22o2zC22oz2022G22%
`
`oO2oe
`
`eubuy
`
`92%“B13
`
`Jeduys
`
`2
`
`Ex. 1015
`CISCO SYSTEMS, INC./ Page 36 of 94
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 36 of 94
`
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 34 of 56
`
`US 7,382,787 B1
`
`v.
`
`Celt
`
`222
`
`Cell
`
`222-
`
`Cett
`
`2
`
`a2-
`
`Cel.
`
`3.
`
`a.
`Celt
`
`4.
`
`222
`
`Celt
`
`S
`
`222.
`
`Celt
`Buffer
`
`S
`
`222
`
`Cell
`Brfer
`
`7
`
`2.
`
`a
`
`Fo
`
`22
`?
`FIFo
`
`st
`
`t
`
`Flo
`
`2.
`
`22
`
`Fo
`
`22-
`
`Fo
`
`
`
`- 12.
`
`Fo
`
`2-
`
`22
`
`2-
`
`Fo
`
`22
`
`st
`
`Fo
`
`Fo
`
`9
`
`222
`
`Celt
`
`222.
`
`Celt
`
`27
`Cet
`Buffer
`
`2
`
`222
`
`Celt
`
`13
`
`22.
`
`Celt
`Buffer
`
`14
`
`222.
`
`Cet
`Bier
`
`t
`
`MCUo
`
`Fig.27
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 37 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 35 of 56
`
`US 7,382,787 B1
`
`97 Byte Packet
`
`al
`
`
`
`
`
`30+4 Byte
`(Head Cell)
`
`(a
`
`Fig.28A
`
`22+4 Byte
`(Tait Celt)
`
`
`
`
`
`3044 Byte
`(Body Cet)
`
`18-4 Byte
`(Tat Cet)
`
`Fig.28B
`
`22
`
`2O
`
`
`
`(
`30-4 Byte 30-4 Byte 16+4 Byte 15+4 Byte
`(Head Cet) (Body Cet) (Body Cell)
`(Tatt Cet)
`2
`
`Fig. 28C
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 38 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 36 of 56
`
`US 7,382,787 B1
`
`Detta Count FOW
`
`Striper receives a packet for
`a queue
`
`24O
`
`
`
`
`
`
`
`
`
`
`
`
`
`Counts number of cells in
`packet; adds number of cells
`to the detta count value in the
`table corresponding to the
`queue
`
`
`
`242
`
`Send delta count value for
`each queue to CU
`
`24
`
`Clear detta count values in
`striper's detta counttable
`
`Fig.29
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 39 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 37 of 56
`
`US 7,382,787 B1
`
`
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 40 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 38 of 56
`
`US 7,382,787 B1
`
`
`
`Writing cells of a packet to a
`queue of the MCU (S-R-R)
`
`Striper accesses NMT to find next MCU
`for the queue and writes the head cett
`of the packet to next MCU
`
`242,
`
`Write remaining cells of packet
`sequentially to MCUs following MCU
`with head Cet
`
`
`
`Update NM for the queue to change
`MCUpointerto MCU following the
`MCU that the
`tatt Was Written to
`
`2s2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Repeat for next packet
`
`Fig. 31
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 41 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 39 of 56
`
`US 7,382,787 B1
`
`
`
`Storing cells in memory
`(S-R-R)
`
`Receive cell at MCU from
`striper, the cell destined for a
`cqueue
`
`Write cett sequentially to next
`available memory Space for
`the cqueue
`
`Fig. 32
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 42 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 40 of 56
`
`US 7,382,787 B1
`
`P: Qt, 7 cel
`
`
`
`
`
`Fig. 33A
`
`Fig. 33C
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 43 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 41 of 56
`
`US 7,382,787 B1
`
`2-
`
`MEEO/
`Mist
`Table
`
`
`
`
`
`Accounting
`Table
`
`e
`
`24
`
`Switching Engine
`
`--Detta Counts f Celts--------------------------------
`MCU interface Unit 21
`Striper interface Unit
`MU
`-1
`SU
`(MEU)
`(SU)
`
`A
`
`t E.
`
`SRAM
`interface
`
`
`
`in Pool
`
`Unit
`
`CU
`
`26
`
`GA interface Unit (GU)
`
`
`
`Media
`Adapter
`
`22
`
`Fig. 34
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 44 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 42 of 56
`
`US 7,382,787 B1
`
`LCU determines queue to request
`from striper using discipline
`
`278
`
`LCU sends dueue request to striper,
`the queue request including: queue
`number, MCU (number for head Cet;
`and number of cells
`
`22d
`
`CU receives the requested cells from
`MCUS
`
`222.
`
`LCU parses number of cells from
`received cells
`
`eft
`2
`
`
`
`
`
`
`
`
`
`site
`gueue number
`number of cetts in
`queue; and head
`inter
`po
`
`Update queue
`table in CU:
`Decement
`number of cells in
`queue by number
`of cells requested;
`increment head
`pointer by number
`of cells requested
`
`
`
`
`
`
`
`CU sends request to striper for
`remainting cells in packet, the request
`including: cueue number MCU
`number for next cell; and the number
`of cells
`
`
`
`
`
`232)
`
`Fig. 35
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 45 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 43 of 56
`
`US 7,382,787 B1
`
`
`
`Receive queue request from LCU:
`queue number, MCU of head cell; and
`number of Celts
`
`Generate Command to each MCU for
`request beginning with MCU of head
`Celt, and sequentially thereafter for
`number of cells
`
`Each MCU transmits cell to CU
`
`Fig. 36
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 46 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 44 of 56
`
`US 7,382,787 B1
`
`
`
`
`
`Detect at cells for a
`packet have arrived
`
`2ae
`
`
`
`Mutticast
`
`Read MED from Packet
`
`272,
`
`Read MED table using
`MED from packetas
`index
`
`Zoo
`
`Read Mist table On
`external SRAM using
`pointer from MED table
`
`go2.
`
`Unicast
`
`Fanout, UED of each Fanout
`
`Scheduler
`
`Read UED table using
`UED provided by
`Scheduler as todex
`
`ge
`
`
`
`
`
`
`
`Fig. 37
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 47 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 45 of 56
`
`US 7,382,787 B1
`
`
`
`Next Encapsulation
`
`2O2
`
`Generate L2 encapsulation
`
`Fragmentation?
`
`
`
`Fragmentation
`Complete?
`
`
`
`
`
`
`
`
`
`
`
`2e
`
`Fait
`
`Drop
`Packet
`
`Assemble packet using Cells
`from CHB, prepend L2
`encapsulation, and regenerate
`checkSun
`
`
`
`
`
`ransmit packet when
`tinterface ready
`
`Fig. 38
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 48 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 46 of 56
`
`US 7,382,787 B1
`
`
`
`.
`
`S.
`
`2
`
`f
`
`N Y
`|
`| .
`X) 3
`Y 9. O
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 49 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 47 of 56
`
`US 7,382,787 B1
`
`Receive packet from NPU, the
`packet having a context defining
`the destination dueue for the
`packet
`
`Update detta count table
`
`Stripe cells across remapped
`MCUs, and remapped gueues
`
`Receive queue request from CU
`
`
`
`Translate queue request to
`remapped queues and MCUs
`
`2%
`
`Transmit cells to CU
`
`232
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 50 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 48 of 56
`
`US 7,382,787 B1
`
`No Redundancy
`
`
`
`
`
`NPuy NPu" NPuy Neus NPunpu
`6 (MMRIMMMMIMMMMM r
`cut cus cus cult
`cul
`
`Fig. 41D
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 51 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 49 of 56
`
`US 7,382,787 B1
`
`1-1 Redundancy
`
`
`
`Fig. 42B
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 52 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 50 of 56
`
`US 7,382,787 B1
`
`
`
`2+ Redundancy
`
`Fig43C
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 53 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 51 of 56
`
`US 7,382,787 B1
`
`
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 54 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 52 of 56
`
`US 7,382,787 B1
`
`
`
`Ae4A 2
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 55 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 53 of 56
`
`US 7,382,787 B1
`
`22.
`
`2.
`
`22
`
`22.
`
`
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 56 of 94
`
`

`

`U.S. Patent
`
`Jun. 3
`
`9
`
`2008
`
`Sheet 54 of 56
`
`US 7,382,787 B1
`
`
`
`(S
`L
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 57 of 94
`
`

`

`U.S. Patent
`
`Jun. 3
`
`2008
`
`Sheet 55 of 56
`
`US 7,382,787 B1
`
`
`
`Jy '613
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 58 of 94
`
`

`

`U.S. Patent
`
`Jun. 3, 2008
`
`Sheet 56 of 56
`
`US 7,382,787 B1
`
`CLCU
`
`CMA
`
`Queue Index
`
`0.11
`
`0.3
`
`0.767 or RP values
`
`FIG. 48
`
`
`
`FIG. 49
`
`Ex. 1015
`CISCO SYSTEMS, INC. / Page 59 of 94
`
`

`

`US 7,382,787 B1
`
`1.
`PACKET ROUTING AND SWITCHING
`DEVICE
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`
`This application claims priority under 35 U.S.C. 119(e) to
`U.S. provisional patent application entitled “PACKET
`ROUTING AND SWITCHING DEVICE, Ser. No. 60/309,
`042 filed Jul. 30, 2001, the disclosure of which is hereby
`incorporated by reference in its entirety. This application is
`also related to the co-pending, commonly assigned patent
`application entitled “PROCESSING UNIT FOR EFFI
`CIENTLY DETERMINING A PACKETS DESTINATION
`INA PACKET-SWITCHED NETWORK, filed on Jul 30,
`2001, Application No. 60/309,087, the disclosure of which
`is hereby incorporated by reference in its entirety.
`
`10
`
`15
`
`FIELD OF THE INVENTION
`
`This invention relates, in general, to network routers, and
`more particularly to a device for performing routing and
`Switching in a packet-switched computer network.
`
`BACKGROUND OF THE INVENTION
`
`25
`
`2
`packet. The header may also contain quality of service
`(QoS) data, which designates the priority with which the
`packet should be serviced by the router.
`The IP destination address (or Layer 3 destination
`address) is a 32-bit identifier assigned to a device on a
`TCP/IP packet-switched network. The 32-bit IP address is
`subdivided into four numbers between 0 and 255 separated
`by periods, e.g., 10.230.15.255. The subdivisions of the IP
`address are hierarchical, representing from left to right
`greater specificity as to the destination for the packet. For
`example, the left most “10 portion of the exemplary address
`may represent the East Coast, the “230 portion may rep
`resent New York City, the “15” portion may represent a local
`area network (“LAN”) in the Empire State Building, and
`“255” may represent the intended final destination in the
`LAN for the packet. To properly route a packet, a router 16
`need only have an output port associated with a portion of
`the IP destination address, such as one of the subdivision.
`For example, the router might transmit all packets having an
`IP destination address beginning with “10 on the outgoing
`link attached with a second router on the East Coast, which
`will then determine where to send the packet to next.
`Accordingly, a packet may make several hops along its path
`from the source 12 to the destination 14.
`The IP addressing scheme of a packet-switched network
`10 provides for scalability of the network, in that each router
`16 need not be directly connected with the destination 14 for
`the packet. To manage scalability, the addition or removal of
`devices from the network is tracked and updated by the
`routing or forwarding table, which is typically dynamic.
`Routing protocol software provides communication between
`routers on the network and updates the forwarding table in
`each router to reflect changes in the topology of the network.
`Conventional routers can suffer from a “denial of service
`attack” wherein the route processor of a conventional router
`is i