(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
`
`

`

`US. Patent
`
`Sep. 30, 2003
`
`Sheet 2 0f 14
`
`US 6,628,653 B1
`
`MmAQZ/wm
`
`HmMD/E
`
`UTUQI—
`
`mHmMOad
`
`
`
`GZHOUr—LDO mum/wk
`
`ZOHmHUmQ
`
`
`
`EDM<mmmam/VF
`
`mUZ<ZmHZH<E
`
`Omo
`
`mam<2§<fl©0~5
`
`N.0:—
`
`QmELUmEmm
`mum/\EEEGOMA
`mHmMU<m
`
`MOH<ZH2HMUWHQ
`
`OZEZOUZH
`
`CISCO SYSTEMS, INC. / Page 3 of 24
`
`EX.1007
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 3 of 24
`
`
`
`
`

`

`US. Patent
`
`Sep. 30, 2003
`
`Sheet 3 0f 14
`
`US 6,628,653 B1
`
`OHmamQ
`
`mqup
`
`o N
`
`mqm<2§§©OMm
`
`
`
`\E0m<mmmqmacdk
`
`mUZ<ZmFZH<§
`
`UHOOQ
`
`mqm<§2§©O~E
`
`MOF<ZE>EMUmHQ
`
`
`
`manEDmHmvfiyd
`
`mQM<Om2:
`
`FDAZHIt?
`
`”SDAD
`
`FIIOWL
`
`mom
`
`QUEoi
`
`mQM<Om2:
`
`5650
`
`UHOOA
`
`mqulzngOMLHmMU<m
`GZEMMEMmE/mmmmmmbm
`
`FmOE
`
`CISCO SYSTEMS, INC. / Page 4 of 24
`
`EX.1007
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 4 of 24
`
`
`
`
`
`
`

`

`US. Patent
`
`Sep. 30, 2003
`
`Sheet 4 0f 14
`
`US 6,628,653 B1
`
`mUZ<ZmHZH<E
`
`EUM<mmOH
`
`OHUOA
`
`UHHmEQH—Lm
`
`03
`
`GZEL<ZHEHMUmHQ
`
`mmnrmmvmm
`
`cow
`
`MmrwmfimvmaMm<§
`
`|Page55%EMQEEl.1EuOHo;
`”595528295szQ72
`
`
`
`CISCO SYSTEMS, INC. / Page 5 of 24
`
`EX.1007
`
`EOMmQZ<DADEOME
`
`
`
`OHUOAGZHHMMEMMHZH
`
`Yaw—rm
`
`
`
`
`
`MOH<EEUmHQmam<§§§0©mg
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 5 of 24
`
`
`
`
`
`

`

`US. Patent
`
`4
`
`US 6,628,653 B1
`
`ZOMHSVH
`
`mAmgdL
`
`HDAHHDO
`
`Hqumm
`
`
`
`mHADmmME0m<mm
`
`m
`
`<EEHBOUA<
`
`EUM<mm
`
`\ZOFUmqmm
`
`AOMHZOO
`
` MomEEEOGQ25200?mots/mm53%mom<mm.2593m20%SowonmGEE/EBB203
`2,-33<39memmemQN__w5528w.8quszlmobs/ms5528060;SE-Eflmoma
`
`
`
`
`
`39$
`
`OF0635722522259¢S
`
`
`
`
`owomomcoQUEPC50:Eomag
`
`
`
`
`
`m0<mflmHZH>MELZmBWZQD<SOME
`
`HDAELDO
`
`
`
`
`
`OZHHMOmmMmUCLmEQQm
`
`
`
`
`
`UHGOAUZELWMmmmr—LZHOHDHUOQUZHHMMEMWHZHEOME-AOmr—LZOO
`
`CISCO SYSTEMS, INC. / Page 6 of 24
`
`EX.1007
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 6 of 24
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Sep. 30, 2003
`
`Sheet 6 0f 14
`
`US 6,628,653 B1
`
`Scm.QUE8.
`
`
`
`UHUOAUZHFmMEmr—LZH
`
`
`
`OHUOAEUHxJZdEZUHUOQEOHxJZ
`
`
`
`
`
`
`
`vaqmmZOHHUZDWHUmQMmZOELUZDM
`
`
`
`
`
`QM<UmHQ
`
`H§U<m
`
`2050255
`
`corom.o
`
`mMO>ZH
`
`DAD
`
`mEL<mED
`
`mqm<rw
`
`02mm
`
`HmMU<m
`
`mEL<nED
`
`HmMU<m
`
`ZOEUZDL
`
`ZOHHUZDHH
`
`ZOELOZDm
`
`ZOHr—LUZDm
`
`EEUOMEmM
`
`EUM<Mm
`
`EEEEOOA<
`
`ZOHPOZDm
`
`EEOOMmmM
`
`EEUOMAmM
`
`mOH<ZHEHMUmHQ
`OZHHmMEMmELZH
`
`ZOHr—LUZDL
`
`
`
`ZOEUZDmUHOOQ
`
`CISCO SYSTEMS, INC. / Page 7 of 24
`
`EX.1007
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 7 of 24
`
`
`
`
`
`
`

`

`US. Patent
`
`Sep. 30, 2003
`
`Sheet 7 0f 14
`
`US 6,628,653 B1
`
`a
`
`
`
`mm<mmZOELDUme
`
`mrEmPUEHXm
`
`20”;
`
`0722007:
`
`HmMU<m
`
`EUm<mm
`
`ZOHmHUmQ
`
`mAm/EL
`
`PDQ>MM<U
`
`MOQmEOH<E
`
`QmEUrH<H>Tm=2
`
`ZOELD<
`
`FGE
`
`
`
`.2020365me
`
`
`
`
`
`eonmafia2057:me
`
`
`
`
`
`
`
`“mafiaZOHmMmZ/HOUQZ<EOE/$2mam/NH
`
`EEOOME.
`
`
`
`
`
`@504mm<>>om<m097:
`
`
`
`
`
`mzoEzEmQ9&szmzzaqouSago
`
`cmunoEB55%mania
`
`ow...
`
`
`
`EUm<mmEEGOME
`
`EEHEOOA<
`
`EEGOME
`
`MOF<ZHZHMUmHQ
`
`
`
`
`
`mmEDmEOM<mmmZEm—Q
`
`
`
`anEquofibm30:35dim
`
`
`
`mZOEL<ZHm=>HODE933
`
`
`
`QZOmmm—MMOUHmMOxE
`
`
`
`mZEDAOUEUP<2OH
`
`
`
`5mgzoiommdzfi"53mm55%
`
`$5565sz.zozofio<mzamm
`
`
`
`zoZOE?mzzmm
`
`
`
`Fqumm$0532-92
`
`CISCO SYSTEMS, INC. / Page 8 of 24
`
`EX.1007
`
`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
`
`

`

`US. Patent
`
`Sep. 30, 2003
`
`Sheet 9 0f 14
`
`US 6,628,653 B1
`
`
`
`UHGOQUzpmammmka
`
`
`
`ZOEémmO<OmmmmUZ<EU
`
`
`
`<©nEUZ~©Z<EU>m
`
`MmFmHUmmMOr557:
`
`
`
`mHUmHmQmqm<rw
`
`
`
`mUZ<ZmHZ~<Emqm<rw
`
`HWMU<m
`
`
`
`merm—HmflmAmFQL
`
`UZHHm—mmmmHZH
`
`
`
`mmzwzmmrwmaUHUOA
`
`
`
`mmarfiz‘mmqmaeggmz
`
`
`
`QZHEEEOOMEWM
`
`Emmodad
`
`mgmfir50:
`
`5325222Saw/2minPCSon
`
`
`
`mmaezmmam»?mmEHZmE205358zoiéboazoo252
`
`
`
`$0725053mam/QBmz<9:$0725Samoa/EonPB50:
`
`@ZTUZ<EU
`
`MOHDAZH<09;
`
`MmELmHUmE
`
`<©mmOH
`
`mmEUrEk/mDmUHmOE
`
`QmEDUEZOUmM
`
`HHDUMEU7:<OnE
`
`emo—
`
`o¢ofi
`
`CISCO SYSTEMS, INC. / Page 10 of 24
`
`EX.1007
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 10 of 24
`
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Sep. 30, 2003
`
`Sheet 10 0f 14
`
`US 6,628,653 B1
`
`mqugHmom
`
`HmMO<mcH.mvmrmmUZ<ZmFZH<E
`
`MOH<ZE>=MUmHQ
`
`
`
`mqufltmHUmHmQ
`
`MOH<ZHEHMUmHQ
`
`mHUmFmfl
`
`UZHZEEUOMmmM
`
`HmMU<m
`
`
`$6725063mmzfizmflmaEuSo:m<00mUZ<ZmELZH<E
`
`
`maxi/Hm5mgmmmfiemwzmwnmwmwmmmwzoigboazoo>3292%aPB50:
`
`
`
`UZHUZ<EU
`
`
`
`MOHDmZH<Umm
`
`MmhmHUmE
`
`mmEUrSBmDADHmOE
`
`QEDDEZOUm—m
`
`HHDUMHU7:<©mmOE:
`
`OMS
`
`<UmmOH
`
`CISCO SYSTEMS, INC. / Page 11 of 24
`
`EX.1007
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 11 of 24
`
`
`
`
`
`

`

`US. Patent
`
`Sep. 30, 2003
`
`Sheet 11 0f 14
`
`US 6,628,653 B1
`
`wfimvum
`
`
`
`mqmfi303:3:
`
`mELOZmM
`
`MOZEHmz
`
`one.
`
`mimgg
`
`
`
`MUZ<ZmFZM<EHmom
`
`mmEHZm
`
`
`
`mmUZ<EUUHQOQmmZHzmm—Hmfl
`mmEMELZmmqmdcnwmqm<rwBmZ
`
`
`
`
`<wnE$07220mm<oquomP6So:
`
`wzazéo<9:8EZOE/£50zoiébwazooBmz
`
`CNS_~52:E2_524425222502mm
`
`mEUDMHmZH
`
`UZEZEEUOMmmM
`
`DADHmOE
`
`mNoH
`
`09:
`
`
`
`MOPDQZH(AVE
`
`mmrwmfimvm—M
`
`mmEOHS/mDADHmOE
`
`QEDUEZOUmM
`
`EDUMEOZH<©mm
`
`0mg
`
`1A:
`
`CISCO SYSTEMS, INC. / Page 12 of 24
`
`EX.1007
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 12 of 24
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Sep. 30, 2003
`
`Sheet 12 0f 14
`
`US 6,628,653 B1
`
`UZHOOEDO
`
`mHmMU<m
`
`m2:
`
`m0<mmmrr7m
`
`3:
`
`mqm<EE<MUOMm
`
`
`
`AOMFZOUwagon—L
`
`mqm<EE<MOOMm
`
`MOH<ZE>EMUmHQ
`
`OS
`
`om
`
`ZOHmHOmQ
`
`mum/wk
`
`afimvum
`
`mO<MMmHZH
`
`W724HDmZH
`
`@555me
`
`0752007:
`
`CISCO SYSTEMS, INC. / Page 13 of 24
`
`EX.1007
`
`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
`
`

`

`&
`
`M
`
`M
`
`US. Patent
`
`8flEda
`
`
`
`#052807:52E55
`
`0,oNM..03722385
`omSo:
`
`320553
`
`5mglomezoomam?SS
`
`
`
`
`
`Mom#%oaeomzzoommea
`
`US 6,628,653 B1
`
`mammmbmm956$
`
`
`MOmmmUOMmMMOBFWZREUHmO:
`
`
`
`mU<EmEZH
`
`EDGE/m
`
`Owfi
`
`CISCO SYSTEMS, INC. / Page 15 of 24
`
`EX.1007
`
`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 other programmable
`logic arrays to pro