(12) United States Patent
`Salim
`
`USOO6628653B1
`US 6,628,653 B1
`Sep. 30, 2003
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) PROGRAMMABLE PACKET SWITCHING
`DEVICE
`
`(75) Inventor: Jamal Hadi Salim, Nepean (CA)
`
`(73) Assignee: Nortel Networks Limited, St. Laurent
`(CA)
`
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/090,285
`(22) Filed:
`Jun. 4, 1998
`(51) Int. Cl. ................................................ H04L 12/56
`(52) U.S. Cl. ........................................ 370/389; 370/401
`(58) Field of Search ................................. 370/389, 392,
`370/401, 402, 403, 404, 405
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,572,512 A * 11/1996 Cutler, Jr. et al. .......... 370/248
`6,188,689 B1 * 2/2001 Katsube et al. ......
`... 370/389
`6,236,654 B1 * 5/2001 Egbert ........................ 370/392
`
`OTHER PUBLICATIONS
`Alexander, D. Scott, et al. “Active Bridging”.SIGCOMM
`97, Cannes, France, Sep. 1997.
`“Telecommunication Routers”, User Manual dated Apr. 16,
`1998, published by Obtek L.L.C., P.O. Box 399, Rockwall,
`Texas 75087-0399 U.S.A.
`* cited by examiner
`Primary Examiner-Chau Nguyen
`ASSistant Examiner-D. Trinh
`(57)
`ABSTRACT
`A packet processing apparatus comprises a programmable
`hardware discriminator for receiving incoming packets, and
`Selecting bits from any part of the incoming packets, a
`decision table for Storing information relating to how the
`packets are to be processed, programmable hardware Search
`ing logic for accessing the information in the table according
`to the Selected bits, and a packet handler for processing the
`packets according to the result of the access. Since many
`networking processing tasks can be broken down into bit
`Selection and table Searching, this generic type of arrange
`ment will Suit a wide variety of applications. It facilitates
`developing logic directly in hardware which can reduce the
`effort needed to convert a working prototype into a product
`ready for use in the field, e.g. for handling new protocol
`components.
`
`1 Claim, 14 Drawing Sheets
`
`INCOMING
`PACKETS
`
`PROGRAMMABLE
`DISCRIMINATOR
`
`
`
`SELECTED
`
`PROGRAMMABLE
`TABLE SEARCH/
`MAINTENANCE
`LOGIC
`
`DECISION
`TABLE
`
`
`
`
`
`PACKET
`HANDLER
`
`
`
`OUTGOING
`PACKETS
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 1 of 24
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 1 of 14
`
`US 6,628,653 B1
`
`
`
`
`
`/ONIHOLIAAS
`
`
`
`
`
`{{OV HORIALNI
`
`JL[\d{NI
`
`JL:HXHOVdI
`
`RIGH H H []{
`
`ÅRHOVNIHWN
`
`080Z
`
`C)SRI}{{HJLTIH
`
`COVJLOEI
`
`00
`
`
`
`
`
`JLRIV RHOIRIGH I’OIGH
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 2 of 24
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 2 of 14
`
`NOISIOHd
`
`TTaVL
`
`OC
`
`HTEVANNVADOdd
`
`
`
`/HOUVASATEVL
`
`YONVNALNIVAL
`
`JIDO'T
`
`LAAOVd
`
`¢Old
`
`CHLOYTHS
`ATEAVNINVaDOdd
`SLAAOVd
`
`YOLVNIATYOSIG
`
`ONINOONI
`
`US 6,628,653 B1
`
`ONIODINOUHTONVH
`
` SLHAOVd
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 3 of 24
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 3 of 24
`
`
`
`
`
`

`

`US 6,628,653 B1
`
`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 3 of 14
`
`TIAVNWVUDOUdATAVNWVYDOUd
`
`PIAVNNVUDOUdLa
`ONLLANAATLNIsava
`
`IN01aaana
`
`sdav)dN
`
`COLOre
`
`SaavVOANIT
`
`LNdLNo
`
`of€
`
`As
`
`DOT
`
`
`
`
`
`ATAVLHONVNALNIVINSuanLAWOVd
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 4 of 24
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 4 of 24
`
`
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 4 of 14
`
`US 6,628,653 B1
`
`NIATAOSIG
`
`WOdANVdOWO
`
`
`
`JIDOTONILAYdaALNI
`
`POW
`
`
`
`YOLVNINTSOSICATAVNNVADOdd
`
`ONILDV
`
`YaLSIDOAa
`
`
`
`YALSIOdaASVA
`
`AONVNALNIVA
`
`HOUVHSOL
`
`JIDOT
`
`wal=AddOLO1P
`aeLAdLNoFTIOLSLAMOVA
`
`
`YOLVUVANODNOLLONOdONY
`
`
`
`00r
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 5 of 24
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 5 of 24
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 5 of 14
`
`US 6,628,653 B1
`
`ataviOF COIOddLSOHWOws/OL
`
`
`
`JIDOTAONVNELNIVW
`
`
`
`FAOVANALNIAULNAMANAdvWOW
`
`
`
`
`
`/ONTIGNVHSYOLVNI
`
`
`
`TOULNOO-WIMOSICJIDO71INdNI
`
`
`
`ONLLLVAYOAIDOI
`
`
`
`-dudVLVGALATAC/ADV
`
`TOULNOO
`
`WOUd/OL
`
`Ld£10
`
`LOATAS
`
`a
`
`VWHLITYOOTV
`TOULNOOD
`
`HOUVAS
`/NOLLOYTES
`
`
`
`06WHLIMODTVWHLYOO'TVYWOLVNI
`
`
`
`HOUVASHOUVAS-WIOSIG
`
`O809
`
`WOW
`
`aTaViL
`
`
`
`SLTONSHaHOAVAS
`
`SOLLSLLVLS
`
`
`
`TOULNODOLNdLNO
`
`ONILYOdaa
`
`
`
`
`
`
`
`JIDOTJZONILAAdaAINIOLJIDOTONILAUNdaALNI|NOU
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 6 of 24
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 6 of 24
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 6 of 14
`
`US 6,628,653 B1
`
`010s¢g5Iq99°
`
`
`
`JDOTONLLAAdva.ENI
`
`
`
`
`
`
`
`JDO0THOLVW-SINQJIDOTHOLVN
`
`davoOsid
`
`LAAOVd
`
`NOILONNA
`
`
`LOATASNOLLONDA
`
`LOATASNOLLONAA
`
`069
`
`AHLVddf)
`
`NOJLONOAATAVL
`
`ALVddf)
`
`LAAOVd
`
`NOILONNA
`
`WVadOddaa
`
`HOUVAS
`
`WVaddOddda
`WVaddOddaa
`
`NOILONOA
`
`WHLYOOTV
`YOLVNIATAOSIG
`NOILONAA
`NOLLONNAOLD0T
`ONDLLAAdaALNI
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 7 of 24
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 7 of 24
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 7 of 14
`
`US 6,628,653 B1
`
`Low
`
`
`
`ASVHdNOILONOYXY
`
`;NOISIOdGANIA
`
`
`
`
`
`008ASVHdNOLLINIAAA
`
`
`
`
`
`
`
`“ASVHdNOISYAANODCNVHOLVWWATEVL
`
`
`
`
`
`
`
`SNOLLINISAGONINYOALSNWN109LAdLNO
`
`
`SLIdLOVULXA
`
`
`Wow
`
`DONTNOONI
`
`LAAOVd
`
`O1IDOTFUVMGUVHOLNI
`
`
`
`OS%JOSLIHOIHMANIAAG
`
`O98
`
`YOLVNIATYOSIGC
`
`WVadDOdd
`
`
`
`CNOdSHaaOOLAAOVd
`
`
`
`SNATODHOLVWOL
`
`HOUVAS
`
`NOISIOdd
`
`HOUVASNAVaDOdd
`
`SATINHOUVYSANIC
`
`4TaVL
`
`WHITYOO'TV
`
`
`
`‘SNANTOO/S.LIAHOIHM“D'd
`
`
`
`SNOLLVNIGWODHOIHM
`
`WVedOOddg
`
`LNOAWAVO
`
`dOCHHOLVN
`
`CHHOLVUCSIN
`
`NOILOV
`
`HOLVWATAVLNOISIONGTILineesTinsau
`
`
`
`WALINGaALNI
`
`
`
`NONOLLOVANITA
`
`
`
`
`
`NONOLLOVINIA
`
`
`
`LTASAYHOLVACSIN
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 8 of 24
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 8 of 24
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 8 of 14
`
`US 6,628,653 B1
`
`
`
`
`
`TORIJLNOO OLYHOEHLETHdHRIGH LNI
`
`{DNIO O LÍQO
`
`SLEIXIOVd
`
`?96ZEITI?IVLTIO?HALNOO
`
`Z VO?IH
`
`096
`
`
`
`NOI LOGHTOEHS
`
`YHO LVNIWTRIOSICI
`
`TORIJLNO O·
`
`Z WOdIH
`
`SS6
`
`SZ60Z6
`
`8° OIH?I 6
`
`
`
`
`
`
`
`
`
`
`
`YHO
`
`NOILON(\'{
`
`| VOCH H
`
`I VOc{H
`
`@HT8IVJL
`
`TORIJLNOO
`
`RIO LVNIWTHOSICI |ONTWOONI
`
`
`
`
`SLOEIXIOVd
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 9 of 24
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`
`
`SHNINUALYCOIOOT
`
`ONILAAdaaNI
`
`
`
`VOddONIONVHDAd
`
`YALSIOdaAOLOdNI
`
`US 6,628,653 B1
`
`Sheet 9 of 14
`
`
`
`SHRLLNYaTaVMAN
`
`
`
`SHONVHOO1D07qTav.lMAN||vOoddSHDNVHOSAVO'INMOdNddLSOH
`
`
`
`ODOTONILAadddLNI
`
`
`
`SLOYULACATAaVL
`
`
`
`NOILLVaddOVOdaSHDNVHO
`
`AONVNALLNIVIAATEaViL
`
`
`
`
`SARLLNAFIAVLSdTaLNAAdNOLLVUddONOILVUNDIANODMAN
`
`
`
`JONVNALLNIVISHNINGALAGAddLSOH
`TIAVLLSOH
`
`
`UALSIOPa
`
`YOLAdNIVOdd
`
`
`
`ONIONVHOVWOddOL
`
`LAMOVd
`
`LAAOVd
`
`SLOALAdATaVtL
`
`
`
`ONINWVaDOadda
`
`SHHD.LIMSNdLSOH
`
`dayNDIINOOWa
`
`LINOUDNIVOdd
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 10 of 24
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 10 of 24
`
`
`
`
`
`
`
`
`

`

`Sheet 10 of 14
`
`ATAVLLSOH
`
`U.S. Patent
`
`Sep. 30, 2003
`
`OLOMAONVNALNIVI
`
`LHaOVd
`
`YOLVNIATAOSIG
`
`
`
`ATEaVLSLOALAG
`
`YOLVNIATAOSTG
`
`S.LOU.LAd
`
`DNINNAVYOOadda
`
`LAAOVd
`
`CVOINMOGNddLSOH
`
`
`
`
`SAONVHOOIDOTSaNIWRLaCoosortSaVvOOHONVNALNIVA
`
`US 6,628,653 B1
`
`ONIONVHO
`
`
`
`YOLAdNIVOdd
`
`YaLSIoda
`
`SHHOLIMSNdOLSOH
`
`CHaNDMNOOWaA
`
`LINOAIDNIVOdd
`
`VOddOL
`
`
`
`SARLLNAATAVLVEwaNONSONVELDNOLLVUNDIINOOMAN
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 11 of 24
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 11 of 24
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 11 of 14
`
`US 6,628,653 B1
`
`Pol
`
`
`
`ATAVLSLONULSNI
`
`HLOWAa
`
`YONALAN
`
`OLO!
`
`qTTedVL
`
`
`
`OZOIWONLAN
`
`SLONULSNI
`
`DNININVaDOdda
`
`SIONVHDIDOTTAVLMAN||vodSADNVHOSACVOINMOGNdOLSOHVSHUNIAMALAGNddLSOH
`
`
`FONVNALNIVIALSOHScOl
`
`SdRLNaAAdNOLLVaadONOLLVUNDIFNOOMAN
`
` ODNIONVHO
`VOddOL
`
`AONVNELLNIVAHLOWAA
`
`
`
`YOLAdNIVOdA
`
`YALSIOda
`
`SHHO.LIMSNdOLSOH
`
`CHaNDIMNOOda
`
`LINOUDNIVOda
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 12 of 24
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 12 of 24
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 12 of 14
`
`US 6,628,653 B1
`
`ONIODLNO
`
`SLAAOVd
`
`HOVAAELINI
`
`OTTT
`
`ANTI
`
`
`TOULNODATAVE
`YOLVNINTAOSIG
`
`ra
`
`ATEAVNNVADOdd
`ATEAVNANVADOdd
`
`ATaVL
`
`
`
`HOVAAAINI
`
`NOISIOAG
`
`O€ANITLOdNI
`
`
`ONINWOONI
`
`SDAAVd
`
`CVO
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 13 of 24
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 13 of 24
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 13 of 14
`
`US 6,628,653 B1
`
`ÇI” OIH
`
`X JLSOH OL
`
`
`
`|
`
`X JLSOH
`
`09 I I
`
`Z£ZIJLSOH
`
`
`
`?HTI@HVJL NOISIO?HCI09 I I
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 14 of 24
`
`

`

`U.S. Patent
`
`Sep. 30, 2003
`
`Sheet 14 of 14
`
`US 6,628,653 B1
`
`NOISIOaG
`
`Oz
`
`0Scl
`
`LAIOVd
`
`Sudan
`
`
`
`
`ONILNOYLAAOWd
`0zc1ky1TOULNOO
`
`dTatHrowinooaay,ATavL|}Ove!
`ne!rol
`
`LSOH
`
`YOSSAOOUdAAUOM.LAN/NdO
`ONILOANNODMALNI
`HOVAAALNI
`
`JOLWNIATYOSIA
`
`O8IT
`
`LNO/NI
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 15 of 24
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 15 of 24
`
`
`

`

`1
`PROGRAMMABLE PACKET SWITCHING
`DEVICE
`
`US 6,628,653 B1
`
`BACKGROUND TO THE INVENTION
`1. Field of the Invention
`The invention relates to packet processing apparatus, to
`methods of reconfiguring a packet processor, and to methods
`of using a packet processor.
`2. Background Art
`It is known to transmit data in packets, each packet having
`header information as part of the packet, for use in proceSS
`ing the packet. The location and meaning of the header
`information within each packet is defined by a protocol.
`Most packet data transmission networks use multiple layers
`of protocols, in a hierarchy, according to the well known ISO
`model. Starting with the raw data from a top level
`application, each protocol adds its own header information
`to that added previously by preceding (higher) protocols. In
`the course of transmission through the network, the packet
`may pass through and be routed, forwarded Switched or
`processed according to information Stored in various parts of
`the packet header, depending on which level of the various
`levels of protocols, is being used.
`Conventionally, in a router or Switch operating according
`to a given one of the protocols, for each incoming packet,
`particular bits in the header relating to that given protocol
`are examined. The packet would be routed using those bits
`and passed to a chosen output port. Dedicated hardware is
`often used for Speed of operation.
`New types of protocol processing using different parts of
`header or payload information with different meanings, are
`always being proposed, at all different layers, to meet new
`requirements for e.g. quality of Service, billing functions,
`error handling, grouping of packets, prioritizing, and So on.
`However, development of appropriate hardware is time
`consuming, even when groups of programmable logic chips
`are used, for a number of reasons. Connections between
`Such chips must be defined and fixed, and changes made to
`the relatively complex logic which is often involved, will
`often have consequences to other parts of the logic, which
`are difficult to manage.
`Software simulations and verifications of hardware
`designs can be carried out, but often do not reveal all the
`problems of a real hardware implementation.
`Programmable chips for Switching packets of particular
`protocols are known, e.g. ethernet Switching chips, and
`protocol-specific dedicated router chips. Such router chips
`can extract destination information from a packet using
`hardcoded logic to achieve higher Speed or throughput. They
`use a routing table whose entries can programmed from an
`external host.
`A chipset produced by Obtek provides multiprotocol
`packet routing. A programmable filter examines the contents
`of each incoming packet to derive the buried protocols and
`retrieve Source and destination addresses. The filter passes a
`packet descriptor to a routing Systems control chip which
`manages memory allocation, input and output queues.
`This filter is programmable using a proprietary language,
`a rule-based language which enables a programmer to define
`actions to be taken according to recognition of bits in a
`packet. AS the filter's active Structure parses and processes
`the unknown incoming packet, it is capable of activating
`other processors (including a host) or special hardware (for
`very high performance) to perform concurrent and Support
`ing tasks.
`
`5
`
`1O
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`SUMMARY OF THE INVENTION
`It is an object of the invention to provide improved
`methods and apparatus.
`According to a first aspect of the invention there is
`provided a packet processing apparatus comprising:
`a programmable hardware discriminator for receiving
`incoming packets, and Selecting bits from any part of
`the incoming packets;
`a decision table for Storing information relating to how the
`packets are to be processed;
`programmable hardware Searching logic coupled to the
`decision table and to the discriminator for accessing the
`information in the table according to the Selected bits,
`and
`a packet handler coupled to the Searching logic, for
`processing the packets according to the result of the
`CCCSS.
`Advantages include the following:
`a) Providing programmable table Searching logic means
`that the Search algorithm and any corresponding table
`maintenance functions can be altered without neces
`Sarily altering the table contents, or the bit Selection
`hardware. This Separation of these functions can make
`it easier to develop and refine applications using new
`protocol components, Since changes to algorithms can
`be made more directly, at a lower level. It may enable
`applications to be developed to run faster, or use
`memory more efficiently for example. This was not
`possible in previous arrangements in which it was only
`possible to define the overall outputs of Such algorithms
`for given States of the bits selected from the packet,
`without being able to define how the selected bits were
`processed, or how a table of all the possible outputS is
`Searched.
`b) Since many networking processing tasks can be broken
`down into bit Selection and table Searching, this generic
`type of arrangement will Suit a wide variety of appli
`cations.
`c) Having the bit selection function programmable, and
`able to Select bits from any part of the incoming packets
`enables a wider range of operations using different
`protocols to be handled. This also makes it easier to
`interface with different input line interfaces, and
`enables Subsequent processing to be streamlined, if all
`the necessary information in the packet can be
`extracted in one step.
`d) Providing the table Searching logic in hardware enables
`the Speed of operation to be faster than equivalent
`Software, and makes it easier for the developer to
`resolve timing issues in the design.
`e) Developing logic directly in hardware can reduce the
`effort needed to convert a working prototype into a
`product ready for use in the field, and thus reduce the
`all important time to market for a product. The arrange
`ment could be used in networks which are designed to
`be reconfigurable in operation, e.g. active networks
`which may be reconfigured to Suit traffic conditions.
`f) Having a programmable Search algorithm enables the
`algorithm to be tailored to reduce Search times, and
`improve throughput, for example by using the mini
`mum number of bits or columns in the table necessary
`for Searching, according to the application.
`g) Having an explicit table can make it easier to maintain
`the contents of the table if it can be accessed directly.
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 16 of 24
`
`

`

`3
`This is in contrast to previous arrangements having an
`implicit table not accessible directly, but defined by
`mappings of output for a given State of bits Selected
`from the packet. If there are many Such mappings
`having the same output, then any change in that one
`output would require changing all the mappings which
`mention that output. Having direct access to the table
`enables one table entry to be changed which may be
`Simpler and quicker than changing multiple mappings
`in Such a case.
`Preferably the apparatus further comprises at least one
`packet output port, and the packet handler comprises a
`programmable hardware interpreting logic coupled to the
`packet output port, for interpreting the result of the access,
`to control the packet output port.
`An advantage of providing a programmable interpreting
`logic is that the reaction to the result of the table Search can
`be separately programmed, without necessarily altering
`other elements.
`Preferably the interpreting logic is arranged to react to
`both a match and a mismatch result.
`An advantage of being able to program action on a
`mismatch is that it broadens the range of applications to
`cover for example those in which a mismatch result can be
`used to alter the table, or to broadcast a packet. This is
`Significant for following the “route once, Switch many”
`principle, which means where a packet is received, if the
`table does not include its destination, it may be routed by for
`example a host CPU based routing algorithm, or by broad
`casting to neighbouring nodes, but thereafter, the table learns
`the destination, and the remaining packets can be Switched
`without the lengthy delay of using the CPU, or the ineffi
`ciency inherent in broadcasting.
`Preferably the programmable hardware Searching logic
`being arranged to be reprogrammable while in operation
`without interrupting the accessing of the information in the
`table.
`One advantage is that changes or upgrades can be made
`more easily, without needing to reinitialize the System. In
`field applications, maintenance or upgrades become easier,
`Since Service can be maintained without interruption.
`Furthermore, it makes the apparatus more Suitable for use as
`an active node in an active network, Since the node can be
`reconfigured more easily with less likelihood of disrupting
`Service.
`Preferably, the apparatus further comprises a table main
`tenance means coupled to the decision table to modify the
`decision table according to parameters derived from the
`incoming packets.
`An advantage of being able to modify the table from
`incoming packets is that the apparatus can better cover
`applications in which the table must be self learning. This
`feature is also significant for following the “route once,
`Switch many' principle. This applies whether the table
`maintenance means receives the derived parameters from
`the host CPU or whether it receives the packets and derives
`the parameters itself.
`Preferably the table maintenance means comprises pro
`grammable hardware logic for deriving the parameters from
`the incoming packet. An advantage of this, is that Such
`modifications can be made more quickly than if the host
`CPU makes the derivation.
`Preferably the apparatus further comprises at least one
`packet output port, and the packet handler comprises pro
`grammable hardware interpreting logic coupled to the
`packet output port, for interpreting the result of the access,
`to control the packet output port, the table maintenance
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,628,653 B1
`
`4
`means being coupled to the interpreting logic, and being
`arranged to modify the decision table on the basis of an
`output of the interpreting logic. An advantage of Such an
`arrangement is that Self learning of the table resulting for
`example from null Search results, can be carried out more
`quickly than if the host CPU needs to be invoked.
`Preferably the apparatus further comprises a host
`processor, the table maintenance means being coupled to the
`host processor and being arranged to modify the decision
`table on the basis of an output of the host processor. An
`advantage is the greater flexibility enabled by having the
`host CPU control the operation.
`Preferably the discriminator further comprises a compara
`tor for receiving the incoming packets, and comparing at
`least a portion of each packet with predetermined data, to
`identify particular types of packet from the incoming
`packets, the table maintenance means being coupled to the
`comparator and being arranged to modify the decision table
`on the basis of an output of the comparator. An advantage of
`being able to modify the table upon identification of a
`predetermined packet is that protocols which include pack
`ets carrying routing information for example, can be handled
`more quickly than if they must be passed to the host CPU.
`Preferably the discriminator further comprises a compara
`tor for receiving the incoming packets, and comparing at
`least a portion of each packet with predetermined data, to
`identify particular types of packet from the incoming
`packets, and process the packet according to its type. An
`advantage is that packets destined for the host CPU for
`example, can be routed there directly without the delay and
`additional processing overhead of a table Search.
`Preferably the programmable hardware Searching logic is
`arranged to access concurrently the information in the table
`relating to a plurality of the incoming packets. An advantage
`arising is an increase in throughput for what may otherwise
`be a bottleneck, particularly if the table is large.
`Preferably the packet handler further comprises a packet
`Switching fabric.
`Preferably the apparatus is part of a programmable packet
`filter.
`Preferably the apparatus is part of a programmable node
`in an active network.
`According to a further aspect of the invention there is
`provided a packet processing apparatus comprising:
`a programmable hardware discriminator for receiving
`incoming packets, and Selecting bits from any part of
`the incoming packets;
`a programmable hardware table processor coupled to the
`discriminator and comprising a decision table contain
`ing information relating to how the packets are to be
`processed, the processor further comprising hardware
`Searching logic for accessing the information in the
`table according to the Selected bits,
`a packet handler coupled to the table processor, for
`processing the packets according to the accessed infor
`mation; and
`and a means to modify the decision table according to
`parameters derived from the incoming packets. Accord
`ing to a further aspect of the invention there is provided
`a method of reconfiguring a packet processor, the
`packet processor comprising:
`a programmable hardware discriminator for receiving
`incoming packets, and Selecting bits from any part of
`the incoming packets;
`a decision table containing information relating to how
`the packets are to be processed; and
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 17 of 24
`
`

`

`S
`programmable hardware Searching logic coupled to the
`decision table and to the discriminator for accessing the
`information in the table according to the Selected bits,
`the method comprising the Steps of
`determining a column Structure for the decision table;
`determining which bits to Select from each packet;
`determining a correspondence between the Selected bits
`and the columns of the table;
`determining which bits are to be used in the Search;
`deriving a new configuration for the discriminator on
`the basis of the determination of which bits to select;
`deriving a new configuration for the Searching logic on
`the basis of the column structure, which bits are to be
`used in the Search, and the correspondence; and
`loading the new configurations into the Searching logic,
`and the discriminator respectively.
`According to a further aspect of the invention there is
`provided a method of reconfiguring a packet processor, the
`packet processor comprising:
`a programmable hardware discriminator for receiving
`incoming packets, and Selecting bits from any part of
`the incoming packets;
`a decision table containing information relating to how
`the packets are to be processed; and
`programmable hardware Searching logic coupled to the
`decision table and to the discriminator for accessing the
`information in the table according to the Selected bits,
`the method comprising the Steps of
`receiving incoming packets, and using the packet pro
`cessor to recognise an incoming packet which indi
`cates that the processor should be reconfigured;
`deriving from the incoming packet new configurations
`for at least one of the discriminator, the Searching
`logic, and the decision table.
`According to a further aspect of the invention there is
`provided a method of using the above mentioned packet
`proceSSOr apparatuS.
`Any of the preferred features may be combined, and
`combined with any aspect of the invention, as would be
`apparent to a perSon skilled in the art. Other advantages will
`be apparent to a person skilled in the art, particularly in
`relation to prior art other than that mentioned above.
`To show, by way of example, how to put the invention into
`practice, embodiments will now be described in more detail,
`with reference to the accompanying drawings.
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 shows a prior art arrangement,
`FIG. 2 shows processing apparatus according to an
`embodiment of the invention;
`FIG. 3 shows an example of the apparatus of FIG. 2;
`FIG. 4 shows an example of the programmable discrimi
`nator of FIG. 2 or 3;
`FIG. 5 shows an example of the programmable table
`Search/maintenance logic of FIG. 3;
`FIG. 6 shows an example of the interpreting logic of FIG.
`3;
`FIG. 7 shows method steps in a definition phase, a
`conversion phase, and an execution phase, related to the
`apparatus of FIG. 3;
`FIG. 8 shows another example of the apparatus of FIG. 2
`with dual redundant;
`FIG. 9 shows alternative reconfiguration possibilities fol
`lowing a reconfiguration indication contained in one of the
`incoming packets,
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,628,653 B1
`
`6
`FIG. 10 shows a number of reconfiguration possibilities
`following detection of a reconfiguration indication in an
`incoming packet, by the discriminator;
`FIG. 11 shows a number of reconfiguration possibilities
`initiated by an instruction from a remote network manage
`ment system to the host CPU;
`FIG. 12 shows an example of the apparatus of FIG. 2,
`Suitable for filtering or conditioning a stream of packets,
`FIG. 13 shows an example of applying the apparatus of
`FIG. 2 to an Ethernet Switch; and
`FIG. 14 shows an example of the apparatus of FIG. 2,
`applied to an IP router.
`DETAILED DESCRIPTION
`The term packet is intended to encompass any bounded
`data unit, such as ATM (Asynchronous transfer Mode) cells,
`frame relay frames, ethernet frames, T1 data units, and IP
`packets. The term programmable is intended to encompass
`hardware whose function can be changed by programming
`all or part of a chip, or by changing the contents of registers,
`or by changing control inputs.
`FIG. 1, Prior Art
`FIG. 1 shows in Schematic form a known arrangement
`based on a router using Obtek chips. The main components
`are the PSP 110 (Packet Script Processor), the RSC (Routing
`Systems Controller) 130, and the ETAC filter 120. Additional
`components shown, include a host CPU 100, an input
`interface 115, a Switch and output interface 140, and packet
`buffer memory 150. The input interface separates the packet
`headers, and feeds them to the ETAC filter. The ETAC filter
`can be programmed to identify protocols, addresses,
`Subnets, or implement firewalls, from packet headers. The
`routing System controller receives descriptorS produced by
`the ETAC filter, and manages memory allocation, input and
`output queues, and other network management taskS.
`The PSP controls the output of packets through the Switch
`140, and may make alterations to outgoing packets based on
`input received from the ETAC. The ETAC can be pro
`grammed to recognise predetermined bits or a signature of
`bits in the header, and map them into a descriptor, which
`indicates how the packet is to be processed. This descriptor
`is sent to the RSC. Furthermore, although there is a pro
`gramming language to enable a developer to Specify a
`mapping, there is no way to program how the mapping is
`achieved within the chip. There is no explicit table, but the
`mappings result in an implicit table. Thus Self learning of
`table elements or any other action as a consequence of
`mismatches apparently cannot be programmed.
`Furthermore, with no explicit table, table maintenance is
`more difficult.
`FIG. 2-Embodiment of the Invention
`FIG. 2 shows the principal elements in Schematic form.
`A programmable discriminator 200 selects bits from
`incoming packets. These are used by programmable table
`search logic 220, to access a decision table 230. The results
`of this access are ultimately used by the packet handler 240
`for processing packets. Some examples of how the indi
`vidual elements can be implemented, and examples of how
`the arrangement can be used in various applications, will be
`described below. The packet handler may be exemplified by
`programmable interpreting logic as described below, or by
`other circuitry for passing the table output directly to a
`packet Switch or packet filter for example. In the case of this
`other circuitry, there may be no need for it to be
`programmable, and the table output may indicate directly an
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 18 of 24
`
`

`

`7
`output port for the packet, or a go/no go instruction, also
`described in more detail below.
`FIG. 3-Example of the Embodiment of FIG. 2
`FIG. 3 shows the programmable discriminator 200, the
`programmable table Search/maintenance logic 220 and the
`decision table 230 of FIG. 2, and in addition shows other
`surrounding elements. Line cards 300 with input packet
`bufferS handle physical and data link layer protocols, and
`feed incoming packets to the programmable discriminator.
`These line cards will make the necessary conversion from
`whichever physical hardware is used for the data transmis
`Sion. Packets are also fed directly to packet buffers 330,
`where they may be queued, ready for Output on appropriate
`output line cards illustrated as 340. In practice, the output
`and input line card functions are usually merged onto a
`Single card.
`A host CPU 320 is connected to the principal elements via
`an interface 325, for the purpose of managing and main
`taining these elements, and for providing high level appli
`cation functions, depending on the purpose of the apparatus.
`The apparatus as shown in FIG. 3 would be configurable
`for use as a packet filter, or a bridge between networks, or
`as a router, for example. It could be used for developing new
`configurations for the hardware, to develop new protocol
`components, or new application features. In principle, the
`Same hardware configuration could then be taken and used
`in the field, to minimize the time to market.
`Connected to the programmable table Search/maintenance
`logic is a programmable interpreting logic 310 which is for
`interpreting the results of the table search. This element will
`be described in more detail below, with reference to FIG. 6.
`Outputs of this logic are shown going back to the program
`mable table Search/maintenance logic, to the packet buffers
`310, and to the programmable discriminator 200 as well as
`to the host CPU. This is one of the ways of making the whole
`System reconfigurable on the basis of incoming packets. For
`example, depending on the results of the Search, the inter
`preting logic may trigger adaptation or Switching to particu
`lar destination output line cards, of packets in the packet
`buffers 330. Alternatively, registers or control lines in the
`programmable discriminator or the programmable table
`Search/maintenance logic may be changed, to change or
`extend the operation of these blocks. Furthermore, the
`interpreting logic can make changes in the decision table, via
`the table maintenance logic.
`The host CPU 320 may perform housekeeping tasks for
`other elements, and, in Service, it may be connected via other
`parts (not shown) to remote centralized network manage
`ment Systems. Reconfiguration in the field may be triggered
`by instructions Sent from Such remote Systems to the host
`CPU. Alternatively, the host CPU may monitor local con
`ditions and initiate reconfiguration on that basis.
`When being used in experimental Set-ups, a separate
`general purpose CPU (not shown) with a general purpose
`operating System may be used to run compilers for devel
`oping programs for the various programmable elements in
`the apparatus. Alternatively, Such development could be
`carried out remotely and compiled programs downloaded to
`the host CPU across the network. In both cases, the host
`CPU could carry out authentication, verification and
`validation, before Such programs are downloaded to the
`programmable elements.
`The programmable hardware elements, the discriminator
`200, the table Search/maintenance logic, and the interpreting
`logic, may be implemented in any form of programmable
`hardware. Preferably it should be electronically program
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,628,653 B1
`
`8
`mable hardware, Such as field programmable gate arrayS
`(FPGA). Alternatives would include ot