Ulllted States Patent [19]
`Gobuyan et al.
`
`[54] LOOK-UP ENGINE FOR PACKET-BASED
`NETWORK
`
`[75] Inventors: Jerome Gobuyan, Kanata; Wayne
`BurWell, Ottawa; Nutan Behki,
`Nepean, 9119f Canada
`
`[73] Assignee: Newbridge Networks Corporation,
`Kanata, Canada
`08/663,263
`
`[21] AppL NO‘:
`
`US005917821A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,917,821
`Jun. 29, 1999
`
`[56]
`
`References Cited
`
`U'S' PATENT DOCUMENTS
`3/1992 Fenner .................................. .. 370/238
`5,095,480
`5,463,777 10/1995 Bialkowski et a1. .................. .. 370/256
`
`Primary Examiner—Chau Nguyen
`Attorney, Agent, or Firm—Marks & Clerk
`
`[22] PCT Filed:
`
`Dec. 21, 1994
`
`[57]
`
`ABSTRACT
`
`[86] PCT No.:
`§ 371 Date:
`
`PCT/CA94/00695
`Aug‘ 16’ 1996
`
`§ 102(6) Date? Aug- 16, 1996
`[87] PCT Pub NO‘: W095/18497
`
`PCT Pub Date: Jul- 6’ 1995
`Foreign Application Priority Data
`
`[30]
`
`Dec. 24, 1993 [GB]
`United Kingdom ................. .. 9326476
`[51] Int. Cl? ................................................... .. H04L 12/46
`[52] US. Cl. ........................................... .. 370/392; 370/401
`[58] Field of Search ................................... .. 370/392, 395,
`370/400, 401_405, 465, 466, 351, 389,
`396, 397, 474, 395/200.68
`
`An arrangement is disclosed for parsing packets in a packet
`based data transmission network. The packets include
`packet headers divided into ?elds having values representing
`information pertaining to the packet. The arrangement
`includes an input receiving ?elds from the packet headers of
`incoming packets, a memory for storing information related
`to possible values of said ?elds, and a device for retrieving
`the stored information appropriate to a received ?eld value.
`The retrieving device comprises a look-up engine including
`at least one memory Organized in a hierarchical tree
`Structure, and a Controller for Controlling the Operation of the
`memory The arrangement is Capable of performing fast
`look'up Operations at a low cost of implementation‘
`
`29 Claims, 11 Drawing Sheets
`
`DESTINATION ADDRESS LOOKUP ENGINE
`
`DALE _/~6
`DESTINATIONADDRESS‘/\5
`1J~ LOOKUPCONTROLLER hag/W16
`A
`I
`LOOKUP ENGINE
`CONTROLLER
`“CODE
`EAIQZJM
`8 X
`
`(-11
`FIFON '10 ->
`X
`Output to AXE
`HF0NX18+OutpuHO
`'
`Reassembler
`DALE \
`12
`_
`
`RAM
`
`AXE
`9
`In ut
`N
`p
`I-> I/F
`agINz
`
`Reassembler /
`
`7%
`l/
`SALE J18
`2\,_ SOURCEADDRESS
`LOOKUPCONTROLLER <— 515mm
`
`SOURCE ADDRESS LOOKUP ENGINE
`
`Packet Intelligence LLC Exh 2073
`Juniper Networks, Inc., et al v. Packet Intelligence LLC
`IPR2020-00337
`Page 1 of 30
`
`

`

`U.S. Patent
`
`Jun. 29, 1999
`
`Sheet 1 0f 11
`
`5,917,821
`
`100W
`Best‘
`Address
`
`103w 104w
`102w
`101w
`NLDest‘ NLSource
`‘
`Source‘
`Address NetLayerpmmco'Type Address
`Address
`
`Tree
`Search
`
`Tree
`Search
`
`Microelode
`Comparrsons
`FIG.1
`
`Tree
`Search
`
`Tree
`Search
`
`15
`
`‘Quad
`MAC
`FIG. 2 t
`
`167
`'Centrel
`up
`t
`
`(17
`\
`LUE
`
`y
`
`>TDATM
`
`FrDmATIVI
`
`DESTINATION ADDRESS LOOKUP ENGINE
`
`DALE ,/~6
`DESTINATIONADDRESS‘/\5
`1J~ LOOKUPCONTROLLER <—* RAM
`512Kx16
`A
`E
`9
`IAXEt
`LOOKUPENGINE
`[EL WI
`CODCEONTROLLER
`RIAEVI
`gl?mgg?df
`32x32
`Reassembler / X
`Input
`
`3 7A
`
`r“
`HF0NX18+OMDUHOAXE
`FIFO N X18‘ _>R Output to
`DALE \ eassembler
`RAM
`12
`128KX16~\
`
`/
`SALE Jag
`2\/_ 'SDDRSEADDRESS
`LOOKUP CONTROLLER <— Maw/I16
`FIG. 3
`
`SOURCE ADDRESS LOOKUP ENGINE
`
`Packet Intelligence LLC Exh 2073
`Juniper Networks, Inc., et al v. Packet Intelligence LLC
`IPR2020-00337
`Page 2 of 30
`
`

`

`U.S. Patent
`
`Jun. 29, 1999
`
`Sheet 2 0f 11
`
`5,917,821
`
`2
`
`SIB RAM
`SIB DATA BUS OUT SIB DATA BUS IN
`
`SIB ADDRESS BUS
`
`23
`
`LOOKUP POINTERS
`
`21
`
`INTERFACE RAM
`INTERFACE DATA BUS IN
`INTERFACE ADDRESS BUS
`
`24
`
`25
`
`NIBBLE INDEX
`
`DATA REGISTER
`
`INDEX POINTERS
`
`26
`
`CANADIAN CODE
`
`COMP
`
`OPCODE DIAP PARAMETER
`
`25
`
`TO/FROM
`SALE, DALE
`
`FIG. 4
`
`IICODE ADDRESS BUS
`
`“CODE DATA BUS IN “CODE DATA BUS OUT
`MICROCODE RAIVI
`
`Packet Intelligence LLC Exh 2073
`Juniper Networks, Inc., et al v. Packet Intelligence LLC
`IPR2020-00337
`Page 3 of 30
`
`

`

`U.S. Patent
`
`Jun. 29, 1999
`
`Sheet3 0f 11
`
`5,917,821
`
`AXE
`
`Input44 S
`32|3|TLATCH
`
`1
`DESTINATIONADDRESSLOOKUPENGINE DESTINATIONADDRESS‘P5 DALE M~6
`
`
`LOOKUPCONTROLLER <—‘ RAM
`‘
`512Kx16
`42
`+ /
`L
`3
`F|FONx18 I , l/FRAM
`FIFONX18
`64x16 ‘p21
`+ 23
`LOOKUPENGINE
`CONTROLLER
`MODERNWF4
`8Kx32
`
`\
`
`4
`5?
`32B|TLATCH
`
`'
`
`Fl
`
`Reassembler
`
`57-11
`FONX18+OUWUHOAXE
`HFONX18I+O um
`DALE \
`RAM
`12
`128Kx16-\
`
`Reassembler
`Input
`
`10
`
`A8
`SALE
`SOURCEADDRESS
`-
`2
`v LOOKUPCONTROLLER <— RAM ‘/
`\
`512Kx16
`/
`( SOURCE ADDRESS LOOKUP ENGINE
`7
`
`Fl G.5
`
`Packet Intelligence LLC Exh 2073
`Juniper Networks, Inc., et al v. Packet Intelligence LLC
`IPR2020-00337
`Page 4 of 30
`
`

`

`U.S. Patent
`
`Jun. 29, 1999
`
`Sheet 4 0f 11
`
`5,917,821
`
`(~42, 43
`1
`SNOOPHFOS
`
`(6
`DALE RAM’
`DALE
`DALE
`AD(19:4) A(3:0)
`‘
`1
`DALE
`NIBBLE RAM
`- RAMD(15:0))
`(
`21
`
`(20
`)
`
`83
`‘SALERAAA
`SLBRAAA
`SALE
`SALE
`ANDRESULTFIFOS
`AD(19:4) A(3:0)
`S|BD(15:0) S|BA(3:0) S|BA(19:4)
`1
`A L__‘ 1
`SALE
`NlBBLE RAM
`
`DALE
`SALE
`2“
`IDALE REGISTERI
`| SALE REGISTERI
`L I L
`\
`1
`
`23
`
`n_— I
`LOOKUPPOINTERS
`+
`ALERESULTBUS
`
`MFD(16:0)
`T
`
`x2
`EFbRb
`l——
`RAMA(4:0)
`
`INTERFACE RAAA
`
`__L0AD
`INDEX POINTER _-_+1
`\
`+2
`50
`(
`
`r
`
`*
`
`CHECKSUIVI
`
`CHEGKSUM
`ENGINE
`
`LEGE
`/ UH
`COMP
`
`IREG'
`
`51
`
`MFDATABUS
`
`' LOGICUNITDATABUS
`MICROCODE PARAMETER BUS
`
`‘
`
`XREGISTERS
`55*’
`
`_
`
`53
`
`XREG
`'
`SRESL
`54
`\‘YRES
`
`56
`
`MUX
`
`LU
`
`—|
`OPCODE DIAP PARAMETER
`
`2
`FCLEAR
`5 ,7‘
`PC <—ADD
`‘_+‘
`
`INSTRUCTION
`REGISTER
`
`v
`
`SPDI
`FUNC
`
`MUX
`
`SLARLS
`BITS
`
`FIG. 6
`
`LLC0DED(31:0)
`LLCODEA(11:0)
`IVHCROCODE RAAA
`
`Packet Intelligence LLC Exh 2073
`Juniper Networks, Inc., et al v. Packet Intelligence LLC
`IPR2020-00337
`Page 5 of 30
`
`

`

`U.S. Patent
`
`Jun. 29, 1999
`
`Sheet 5 0f 11
`
`5,917,821
`
`POINTER
`
`NIBBLE mm (0)
`
`SALE/DALE
`
`DALE RAM
`512Kx16
`
`k
`6
`
`DALE RAN
`512Kx16
`
`x
`8
`
`0000 n-FFFFn
`
`8000n-FFFFO
`
`""" " SIRRRN 120K {10%
`0000 n-01EE n
`
`PO'NTERARRAY(MSB=1)
`P
`
`NEXT POiNTER ARRAY POINTER (10-0)
`POlNTER 0R DATA
`NIBBLE INDEX
`
`16x16
`
`POINTERARRAY(MSB=1) S|B(MSB=0)
`
`/
`
`FIG. 8
`
`16x16
`
`16x16
`
`Packet Intelligence LLC Exh 2073
`Juniper Networks, Inc., et al v. Packet Intelligence LLC
`IPR2020-00337
`Page 6 of 30
`
`

`

`U.S. Patent
`
`Jun. 29, 1999
`
`Sheet 6 0f 11
`
`5,917,821
`
`MAC ADDRESS TREE - EXAMPLE $008FC2865739
`
`ROOTPOINTER
`
`NIBBLE2=$0
`
`N|BBLE3=$8
`
`>
`
`|IIIII;IIIIIIIII
`
`'
`
`‘ ~\\ .......... ..
`
`............... '
`
`I
`
`‘
`
`IIIIIIIIIIIIIIII
`NIBBLE5=$0 .... ..4 .... ..
`
`/
`-------- -
`
`NIBBLE6=$2
`N|BBLE7=$8
`NIBBLE8=$6
`
`9 :$5
`N|BBLE10=$7
`N|BBLE11=$3
`
`__'__'_'_'__'
`
`III IIIIIIIIIIIII
`..... .‘..
`------ --\
`
`IQ.- l I I I I II<I
`
`9
`
`IIIIIIIIIIII
`
`SIB
`
`ROOT POINTER
`
`Packet Intelligence LLC Exh 2073
`Juniper Networks, Inc., et al v. Packet Intelligence LLC
`IPR2020-00337
`Page 7 of 30
`
`

`

`U.S. Patent
`
`Jun. 29, 1999
`
`Sheet 7 0f 11
`
`5,917,821
`
`SOURCE ADDRESS LOOKUP ENGINE
`
`s3
`
`MAC->Found/Not Found
`86
`
`S7
`
`88
`
`S10
`
`Address Match
`
`> (m
`
`ACIdIBSS II/Iatch FEIII
`
`> @
`
`FIG. 11
`
`DESTINATION ADDRESS LODKUP ENGINE
`
`0s
`
`|\/IAC->Found/Not Found
`06
`
`D10
`
`Address Match
`
`> @
`
`ADCIIBSS IVIHICII FHII
`
`> @
`
`FIG. 12
`
`Packet Intelligence LLC Exh 2073
`Juniper Networks, Inc., et al v. Packet Intelligence LLC
`IPR2020-00337
`Page 8 of 30
`
`

`

`U.S. Patent
`
`Jun. 29, 1999
`
`Sheet 8 0f 11
`
`5,917,821
`
`igigigigil
`BITS-0 | HCODEWORD
`ll LP
`I
`BlT3-0 I
`SIBADDRESS
`
`lllllllllllllllll
`
`" 1' " I‘ I
`
`Status Flags
`er
`Peer
`
`Flags
`Flags
`Flags
`
`Pretor Area
`Pr0t02Area
`Proto 3 Area
`
`Proto 5 Area
`Flags
`Other Area Pointer
`
`Proto 1 Best Area Proto 2 Best Area
`
`Erre Enc
`
`Pr0t0 3 Best Area
`Ene
`Proto 4 Best Area
`Enc
`Preto 5 Dest Area
`Ene
`OtherDestAreaPointer
`STATION INFORMATION BLOCK
`
`Status Flags EA RX RP
`eraser
`ae-eeuree PDU
`
`Enearr Flags
`
`EN
`0 W
`FU-FUTURE USE
`
`PhOtO FAags
`
`PA
`
`PV
`
`Ml
`
`MH
`
`MLMULTHNTERFACE
`MH-MULTl-HOMED
`
`FIG- 14
`
`Packet Intelligence LLC Exh 2073
`Juniper Networks, Inc., et al v. Packet Intelligence LLC
`IPR2020-00337
`Page 9 of 30
`
`

`

`U.S. Patent
`
`Jun. 29, 1999
`
`Sheet 9 0f 11
`
`5,917,821
`
`lllllllllllllllll
`
`||||l
`
`ll
`
`PortSet
`
`Photo Flags
`
`1
`PV
`PA
`PA-PROTOCOLACTIVE
`PV-PROTOCOLVALID
`
`Flags
`Flags
`Flags
`Flags
`
`lPX 802.2 Area
`lPX SNAP Area
`lPX Raw Area
`lPXEtlrerArea
`
`IPX 802.2 Desi Area
`IPX SNAP Dest Area
`lPX Raw Dest Area
`lPX Ether Desi Area
`
`PORT INFORMATION BLOCK
`
`DestAreanibblel
`Dest Area nibble 2
`Best Area nibble 3
`
`FIG‘ 15
`
`3 nibble destination area
`
`Souree Area
`Pointer
`
`2 nibble destination area
`
`0
`0
`e
`e
`Filtering Rule 0 AR1AR2AR3AR4AR5 0
`ARx-ALLOW ROUTING erroroeor x
`FIG. 16
`
`0
`
`Packet Intelligence LLC Exh 2073
`Juniper Networks, Inc., et al v. Packet Intelligence LLC
`IPR2020-00337
`Page 10 of 30
`
`

`

`U.S. Patent
`
`Jun. 29, 1999
`
`Sheet 10 0f 11
`
`5,917,821
`
`‘FIFO empty
`
`~Reset
`
`~sno0p done
`
`~F|FD not empty
`
`‘stop AND snoop done
`
`~F|F0 not empty
`AND (Gr0up<4)
`
`'HFO empty
`
`y
`
`‘FIFO no
`AND (Gro =
`0R (Gr0up=6)
`
`‘FIFO not empty
`AND (Gr0up=5)
`
`FIG. 17
`
`Packet Intelligence LLC Exh 2073
`Juniper Networks, Inc., et al v. Packet Intelligence LLC
`IPR2020-00337
`Page 11 of 30
`
`

`

`U.S. Patent
`
`Jun.29, 1999
`
`Sheet 11 0f 11
`
`5,917,821
`
`nr ent
`
`Increment Branch Instructions (Group 2, no Wait states)
`PCLK
`I/FAdd
`I/FDa
`Inst Ad
`Inst Re
`Conditi n
`State
`EXEC_CYCLE
`PC_AD
`
`F|G_ 18
`
`Increment/Branchinstruction
`(Condition=TRUE)
`
`Increment/Branch instruction
`(CondItion=FALSE)
`
`SIB RAM Access Instructions (Group 5)
`PCLK mm
`SIB_RQ
`/
`\
`SIB_GR _____/___\_
`SIB_CS
`/
`\
`SIB_TA
`SIB_Addr
`SIB_WEb(Write)
`SIB_Data(WrIteI
`SIB_OEb(Read)
`SIB_Data(Read)
`Inst Addr
`Inst Reg
`State
`EXEC_CYCLE
`
`Valid Oocode
`XS2XS3XSOXSIXS2XS52XS3
`\
`/
`\
`
`SIB RAIVI Access
`(No wait states)
`
`’
`
`FIG. 19
`
`X
`
`\
`
`WWII
`
`XXXXXX><
`X
`PC
`
`/
`
`\
`
`‘
`
`\__/_
`Valid SIB Data
`)OOOOOOI
`/
`Valid sra Data
`XPC+1
`
`Packet Intelligence LLC Exh 2073
`Juniper Networks, Inc., et al v. Packet Intelligence LLC
`IPR2020-00337
`Page 12 of 30
`
`

`

`1
`LOOK-UP ENGINE FOR PACKET-BASED
`NETWORK
`
`BACKGROUND OF THE INVENTION
`
`FIELD OF THE INVENTION
`
`This invention relates to the ?eld of data communications,
`and more particularly to packet-based digital communica
`tions networks.
`There are two broad classes of network: circuit-based and
`packet-based. Conventional telephone networks are circuit
`based. When a call is established in a circuit-based network,
`a hard-wired connection is set up between the calling parties
`and remains in place for the duration of the call. Circuit
`based networks are wasteful of available bandwidth and lack
`?exibility.
`Packet-based networks overcome many of the disadvan
`tages of circuit-based networks. In a packet-based network,
`the data are assembled into packets containing one or more
`address ?elds which de?ne the context of a packet, such as
`protocol type and relative positions of other ?elds embedded
`in the packet. LAN bridges and routers use the information
`in the packet to forward it to the destination.
`In a packet-based network, a packet must be parsed as it
`?ows through the network. Parsing is the process of extract
`ing and analyZing the information, such as source and
`destination address and net layer protocol, contained in the
`packets.
`In known networks, packet parsing is generally performed
`with a microprocessor, which provides ?exibility in han
`dling different packet types and can be upgraded to handle
`new packet types as they are de?ned. Content Addressable
`Memory (CAM) is commonly used for hardware assistance
`to speed up searches through a list of known addresses. This
`is a tedious task. CAMs are also relatively expensive and
`limited in siZe and availability.
`General purpose processor architectures are not speci?
`cally directed toward the types of operations required in
`packet parsing and so they tend to be inef?cient. To meet
`performance requirements, a fast but expensive processor
`based solution can be implemented. In the highest perfor
`mance systems, hardware solutions are implemented to
`increase speed, but at the cost of ?exibility.
`
`SUMMARY OF THE INVENTION
`
`An object of the invention is to provide a fast, but
`inexpensive solution to the problem of packet-parsing in
`packet-based networks.
`According to the present invention there is provided an
`arrangement for parsing packets in a packet-based digital
`communications network, said packets including packet
`headers divided into ?elds having values representing infor
`mation pertaining to the packet, said arrangement compris
`ing an input memory for receiving ?elds from said packet
`headers of incoming packets; and a look-up engine for
`retrieving stored information appropriate to a received ?eld
`value. The look-up engine includes at least one memory
`storing information related to possible values of said ?elds
`in a hierarchical tree structure and associated with a respec
`tive ?eld of packet headers; a memory controller associated
`with each said memory storing information related to pos
`sible values of said ?elds for controlling the operation
`thereof to retrieve said stored information therefrom; and a
`microcode controller for parsing a remaining portion of the
`packet header while said stored information is retrieved and
`controlling the overall operation of said look-up engine.
`The memory and retrieving means constitute a look-up
`engine, which is the central resource containing all infor
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,917,821
`
`2
`mation necessary for forwarding decisions. In a preferred
`embodiment the look-up engine includes a source address
`look-up engine and a destination address look-up engine.
`In a packetiZed data transmission conforming to IEEE802
`standards, the packets have a MAC (medium access control)
`header containing information about the destination and
`source addresses and the net layer protocol. The invention
`permits packet switching to be achieved in a bridge-router,
`for example an Ethernet to ATM bridge-router, at a rate of
`about 178,000 packets per second using 64 byte minimum
`Ethernet packets. This means that the MAC headers are
`interpreted once every 5.6 micro seconds.
`The look-up engine preferably employs table look-ups
`using nibble indexing on variable portions of the packet,
`such as MAC and network layer addresses, and bit pattern
`recognition on ?xed portions for network layer protocol
`determination.
`Each look-up table is organiZed into a hexadecimal search
`tree. Each search tree begins with a 16 word root table. The
`search key (e.g. MAC address) is divided into nibbles which
`are used as indices to subsequent tables. The 16 bit entry in
`the table is concatenated with the next 4 bit nibble to form
`the 20 bit address of the next 16 word table. The ?nal leaf
`entries point to the desired information.
`Bit pattern recognition is achieved by a microcode
`instruction set. The microcode engine has the ability to
`compare ?elds in a packet to preprogrammed constants and
`perform branches and index increments in a single instruc
`tion cycle typically. The microcode engine has complete
`control over the search procedure, so it can be tailored to
`speci?c look-up functions. New microcode is downloaded
`as new functions are required.
`The look-up engine can perform up to two tree searches
`in parallel with microcode execution. Look-up time is quick
`because the microcode determines the packet’s network
`layer format while the source and destination addresses are
`being searched in parallel. The results of the source and
`destination look-ups and the protocol determination arrive at
`roughly the same time, at which point the next level of
`decisions is made.
`The look-up engine also performs protocol ?ltering
`between areas. The system allows devices to be grouped
`arbitrarily into areas on a per protocol basis and de?nes
`?ltering rules among these areas. The look-up engine keeps
`track of each station’s area for each of its protocols. The
`source and destination areas are cross-indexed in a search
`tree, which is used to ?nd the ?ltering rule between the two
`areas. Separate ?ltering rules are de?ned for bridging and
`network layer forwarding; bridging is normally allowed
`within an area while network layer forwarding is selectively
`allowed between areas.
`The parsing controller typically has a pointer to the
`current ?eld in the packet being examined. The controller
`moves this pointer to the next ?eld in the packet after all
`decisions based on the current ?eld are made.
`At each decision point on a tree, the current ?eld is
`compared to a known value or range. If the comparison
`yields a true condition, the controller moves to the next
`decision point by moving the current ?eld pointer. Other
`wise the ?eld pointer is left alone and controller branches to
`new code to compare the current ?eld to a different value or
`range. This process is repeated until a ?nal decision is made.
`Moving to the next decision point requires several dis
`crete steps in a general purpose processor. Unlike a general
`purpose processor, which has the disadvantage that it only
`has a single memory bus for both instruction and data
`fetches, the Look-up engine controller has separate buses for
`instruction and data and typically performs one decision per
`step. Fast decisions are made possible by a special set of
`
`Packet Intelligence LLC Exh 2073
`Juniper Networks, Inc., et al v. Packet Intelligence LLC
`IPR2020-00337
`Page 13 of 30
`
`

`

`3
`instructions Which both conditionally move the pointer and
`conditionally branch to neW code in a single step. The
`comparisons and pointer movements can be byte or Word
`Wide, according to the current ?eld’s siZe.
`The look-up engine implements other optimiZed instruc
`tions Which perform bit level logical comparisons and
`conditional branches Within the same cycle as Well as other
`instructions tailored to retrieving data from nibble-indexed
`data structures.
`The look-up engine is preferably divided into the folloW
`ing sections:
`
`a) one or more nibble tree address look-up engines b) one microcode engine
`
`Each ALE is used to search for addresses in a tree
`structure in its oWn large bank of memory. The result of a
`search is a pointer to pertinent information about the
`address. An ALE is assigned to destination addresses
`(DALE) and source addresses
`The ALEs operate
`independently of each other.
`The microcode engine is used to coordinate the search. It
`invokes the SALE and DALE to search for the source and
`destination addresses respectively and continues on to parse
`the remainder of the packet using an application-speci?c
`instruction set to determine the protocol.
`The SALE, DALE and microcode engine can execute in
`parallel and arrive at their corresponding results at roughly
`the same time. The microcode engine then uses the SALE
`and DALE results along With its oWn to arrive at the
`forWarding decision.
`The advantage of using RAM over a CAM is expand
`ability and cost. Increasing RAM is a trivial and inexpensive
`task compared to increasing CAM siZe.
`The advantage of the microcode engine over a general
`purpose processor is that an ASIC implementation of the
`function is much less expensive and less complex than a
`processor-based design With all the overhead (RAM, ROM)
`associated With it.
`The invention also related to a method of parsing packets
`in a packet-based data transmission netWork, said packets
`including packet headers divided into ?elds having values
`representing information pertaining to the packet, compris
`ing storing information related to possible values of said
`?elds, receiving ?elds from said packet headers of incoming
`packets, and retrieving said stored information appropriate
`to a received ?eld value, characteriZed in that said informa
`tion is stored in a memory organiZed in a hierarchical tree
`structure.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The invention Will noW be described in more detail, by
`Way of example only, With reference to the accompanying
`draWings, in Which:
`FIG. 1 is an example of a MAC layer header of a typical
`packet;
`FIG. 2 shoWs the data paths in a typical bridge-router
`betWeen Ethernet LAN and ATM netWorks;
`FIG. 3 is a block diagram of a ?rst embodiment of a
`look-up engine in accordance With the invention;
`FIG. 4 is a block diagram of a look-up engine controller
`for the look-up engine shoWn in FIG. 3;
`FIG. 5 is a block diagram of a second embodiment of a
`look-up engine in accordance With the invention;
`FIG. 6 is a block diagram of a look-up engine controller
`for the look-up engine shoWn in FIG. 5;
`FIG. 7 is a map of look-up engine Address Look-up
`engine
`memories;
`FIG. 8 is a diagram illustrating search tree operation in an
`ALE;
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`a O
`
`5,917,821
`
`4
`FIG. 9 shoWs one example of a MAC search tree;
`FIG. 10 shoWs the effect of the organiZationally unique
`identi?er of the MAC addresses on the siZe of the search
`tree;
`11 shoWs the source address look-up engine table;
`FIG.
`12 shoWs the destination address look-up table;
`FIG.
`13 illustrates the look-up engine addressing modes;
`FIG.
`FIG.
`14 shoWs a station information block;
`15 shoWs a port information block;
`FIG.
`FIG. 16 shoWs an example of protocol ?ltering;
`FIG. 17 shoWs a look-up engine controller Instruction
`State Machine;
`FIG. 18 shoWs a typical fast timing diagram; and
`FIG. 19 shoWs a typical SIB RAM access instruction
`timing diagram.
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`
`A typical look-up engine (LUE) in accordance With the
`invention is designed to be used in a tWelve-port Wire speed
`Ethernet to ATM bridge-router capable of sWitching about
`178,000 packets per second using 64 byte minimum Ether
`net packets. This packet rate corresponds to a look-up
`request occurring every 5.6 psecs. The LUE is used each
`time a packet is received off the Ethernet or the ATM
`netWork. The type of information that the engine provides
`depends on the direction of packet How and the type of
`packet.
`The look-up engine provides all the information needed to
`?nd the path to each knoWn destination, as Well as default
`information in the case of unknoWn destinations.
`FIG. 1 shoWs a typical MAC layer header format for a
`packet that can be parsed With the aid of the look-up engine
`in accordance With the invention. The header comprises
`destination and source address ?elds 100, 101, a netWork
`layer protocol type ?eld 102, and netWork layer destination
`and source address ?elds 103, 104. FIG. 1 also illustrates
`hoW the header is parsed in accordance With the invention.
`All ?elds except 102 are parsed using a tree search. The Net
`Layer Protocol Type ?eld 102 is parsed by using microcode
`comparisons in the microcode engine to be described.
`On a bridge-router, each port is represented by a corre
`sponding bit in a PortSet (Ports 0—11), Which is a 16 bit value
`that has local signi?cance only. The Control Processor and
`ATM are each assigned a port.
`The folloWing de?nitions are special cases of a PortSet:
`
`SinglePortSet
`a PortSet With a single bit set.
`HostPortSet
`a SinglePortSet corresponding to the Control Processor
`MyPortSet
`a SinglePortSet corresponding to the source port of this packet.
`NullPortSet
`a PortSet of no parts.
`
`A Connection Identi?er (CI), Which is a 16 bit value With
`local signi?cance only, is used to map connections into
`VPI/VCI values.
`The folloWing de?nitions are special cases of CI:
`
`MeshiCI
`a CI corresponding to a path towards the destination endstation’s
`Bridge-router.
`
`Packet Intelligence LLC Exh 2073
`Juniper Networks, Inc., et al v. Packet Intelligence LLC
`IPR2020-00337
`Page 14 of 30
`
`

`

`5
`-continued
`
`NulliCI
`a CI connected to nothing. It is returned when the destination is
`attached to the local Bridge-router or if the connection is not
`allowed.
`RSiCI
`a CI corresponding to a path to the Route Server.
`ABSiCI
`a CI corresponding to a path to the Address/Broadcast Server.
`
`MAC layer addresses are globally unique 48 bit values,
`except in some protocols such as DECNet, where they may
`not be globally unique.
`
`UnicastiDA
`a MAC layer destination address of an end-station.
`RouteriDA
`a MAC layer destination address of the Route Server. An end
`station sends packets to the Route Server when it cannot send to
`the destination directly at the MAC layer.
`BroadcastiDA
`the broadcast MAC layer address (all ones) which is received by
`all end-stations. It cannot be a source address.
`MulticastiDA
`a rnulticast MAC layer address (group bit set) which is received by
`end-stations that recognize that rnulticast address.
`
`5,917,821
`
`6
`The Bridge command instructs the AXE (Transfer
`Engine) to use RFC-1483 bridge encapsulation. BridgeProp
`command instructs the AXE to use bridge-router encapsu
`lation (include source PortSet in encapsulation)
`
`UnknowniSA —> BridgeProp, NulliCI, HostPortSet, MyPortSet
`* Unknown SA — send to HP for Spanning Tree processing
`* HP will decide whether to forward it to ABS for learning,
`depending on Spanning Tree state
`UnicastiDA —> Bridge, MeshiCI, NullPortSet
`* DA in the same area on a different Bridge-router
`UnicastiDA —> Bridge, NulliCI, NullPortSet
`* DA not in the same area (reject)
`* Protocol not allowed to bridge-router
`* DA on the same port
`UnicastiDA —> Bridge, NulliCI, SinglePortSet
`* DA in the same area on the same Bridge-router but on a different
`port
`UnknowniDA —> BridgeProp, ABSiCI, NullPortSet, MyPortSet
`* DA not found in the table — send to ABS for ?ood processing
`BroadcastiDA —> BridgeProp, ABSiCI, NullPortSet, MyPortSet
`* Broadcast DA — Send to Control Processor for broadcast
`processing
`MulticastiDA —> BridgeProp, ABSiCI, NullPortSet, MyPortSet
`* Multicast DA — Send to ABS for rnulticast processing
`MulticastiDA —> Bridgeprop, NulliCI, HostPortSet, MyPortSet
`* Multicast DA is of interest to HP (eg Spanning Tree)
`* HP will decide whether to forward it to ABS for rnulticast
`processing
`
`15
`
`25
`
`Network layer (NL) addresses are network protocol
`dependent. They are generally divided into Network,
`Subnet, and Node portions, although not all protocols have
`all three present. The Network Layer Address Field Sizes (in
`bits) are summarized in the table below.
`
`Protocol
`
`Total Size
`
`Network
`
`Subnet
`
`Node
`
`IP
`IPX
`
`AppleTalk
`DECNet
`
`32
`80
`
`24
`64
`
`8/16/24
`n/a
`
`variable
`32
`
`n/a
`16
`(reserved)
`
`16
`38
`(32 =
`'HIORD')
`(6 = subnet)
`
`35
`
`variable
`48
`(MAC address)
`8
`1O
`
`The look-up engine handles unicast network layer
`addresses.
`When the look-up engine is used in a bridge-router
`providing an interface between an Ethernet and ATM
`network, packets coming from the Ethernet side are fed into
`the Look-up Engine. The result of the look-up has the form:
`
`Input
`
`—>
`
`Command, CI, PortSet
`
`where Input is derived from the ?rst few bytes of the packet
`and Command is an opcode to the AXE (Transfer engine).
`The Quad MAC status word distinguishes between router
`MAC, broadcast and multicast MACs.
`Bridging occurs when the destination address is a unicast
`address other than the Route Server address. Bridging is
`allowed between two endstations in the same area for a
`given protocol.
`Both source and destination MAC addresses must be
`known before automatic bridging/?ltering is performed;
`otherwise, the packet is sent to the Route Server for:
`SA (Source Address) validation if the SA has never been
`seen speaking a given protocol
`DA (Destination Address) resolution if the DA was not
`found in the local MAC cache.
`
`55
`
`65
`
`Routing occurs when the destination address is the unicast
`Route Server address. Filtering rules between areas are
`explicitly de?ned per protocol The per protocol source area
`is an attribute of the source MAC address and the per
`protocol destination area is an attribute of the destination NL
`address.
`Both source MAC and destination NL addresses must be
`known before network layer forwarding can occur.
`The packet will be bridged to the Route Server if any of
`the following are true:
`IP options are present
`Protocol is unknown
`The packet will be dropped if any of the following are
`true:
`Source area is not allowed to send to Destination area for
`this protocol
`Source NL address is invalid (e.g. any IP broadcast
`address)
`Checksum is invalid
`Time-To-Live ?eld expires
`
`UnicastiNLDA —> Route, MeshiCI, NullPortSet
`* NL node on a different bridge-router
`UnicastiNLDA —> Route, NulliCI, SinglePortSet
`* NL node on the same bridge-router (could be same port)
`UnknowniNLDA —> Bridge, RSiCI, NullPortSet
`* unknown NL node — send to Route Server
`UnknowniProtocol —> Bridge, RSiCI, NullPortSet
`* protocol unknown, or packet with options
`
`FIG. 2 shows the data paths in a typical bridge-router.
`Control processor 16 has control over the formatting of
`packets it sends and receives. If the control processor 16
`wants look-up engine 17 to perform a look-up, it formats the
`packet in the same way as Quad Mac 15; otherwise it sends
`it as a raw packet, which does not require a lengthy look-up.
`The control processor predetermines the destination by
`providing a CI (Connection Identi?er) and an output Portset
`as part of the data stream. A bit in the Quad MAC status
`word indicates a raw packet and the look-up engine simply
`retrieves the CI and Portset as part of the data stream. A bit
`
`Packet Intelligence LLC Exh 2073
`Juniper Networks, Inc., et al v. Packet Intelligence LLC
`IPR2020-00337
`Page 15 of 30
`
`

`

`5,917,821
`
`7
`in the Quad MAC status Word indicates a raW packet and the
`look-up engine simply retrieves the CI and Portset from the
`data stream and feeds it to the AXE (Transfer Engine)
`through the result FIFO. The Control processor is respon
`sible for correctly formatting the required encapsulation.
`As shoWn in FIG. 2, packets coming from the ATM side
`are fed into the look-up engine. The look-up engine accepts
`an RFC-1483 encapsulated packet and determines Whether
`to look at a MAC or NL address. The result of the look-up
`Will have the form:
`
`Input
`
`—>
`
`PortSet
`
`Filtering is not performed in this direction. It is assumed
`that the all ?ltering is done at the ingress side. It is also
`assumed that the destination endstation is knoWn to be
`attached to the receiving Bridge-router, so unicast packets
`With unknoWn destination addresses are dropped.
`Flood and broadcast packets are encapsulated in a special
`format Which includes an explicit output PortSet.
`
`UnicastiDA —> SinglePortSet
`* DA on this Bridge-router
`UnknoWniDA —> NullPortSet
`* DA not in the table (drop) — this situation should not occur.
`UnicastiNLDA —> SinglePortSet
`* NLDA on this Bridge-router
`UnknoWniNLDA —> NullPortSet
`* NLDA not in the table (drop) — this situation should not occur.
`BroadcastiDA,PortSet —> PortSet
`* Proprietary Broadcast request received from RS
`MulticastiDA,PortSet —> PortSet
`* Proprietary Multicast request received from RS
`UnknoWniDA,PortSet —> PortSet
`* Proprietary Flood request received from RS
`
`10
`
`15
`
`20
`
`25
`
`30
`
`Turning noW to FIG. 3, the look-up engine consists of
`three functional blocks, namely a destination address look
`up engine (DALE) 1, a source address look-up engine
`(SALE) 2, and a look-up engine controller (LEC) 3, Which
`includes a microcode ram 4. DALE 1 includes a destination
`address look-up controller 5 and DALE RAM 6. SALE 2
`includes a source address look-up controller 7 and SALE
`RAM 8. The input to the look-up engine is through a fast
`16-bit Wide I/F RAM 9 receiving input from the AXE
`(Transfer Engine) and reassembler. The output from the
`look-up engine is through Word-Wide FIFOs 11, 12.
`One embodiment of look-up engine controller (LEC) 3 is
`shoWn in more detail in FIG. 4. This comprises (Station
`Information Block) SIB ram 20, interface ram 21, and
`microcode ram 22. The SIB ram 20 is connected to look-up
`pointers 23. Interface ram 21 is connected to data register 25
`and index pointers 26 connected to ALU (Arithmetic Logic
`Unit) 27. Microcode ram 22 is connected to instruction
`register 28.
`The look-up Engine controller 3 is a microcoded engine
`tailored for ef?cient bit pattern comparisons through a
`packet. It communicates With the Source Address Look-up
`Engine 2 and the Destination Address Look-up Engine 1,
`Which both act as co-processors to the LEC 3.
`The look-up engine snoops on the receive and transmit
`data buses and deposits the header portion of the packet into
`the I/F RAM 9. The look-up response is sent to the appro
`priate FIFO 11, 12.
`FIGS. 5 shoW an alternative embodiment of the