IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII|lII||III|II||lIlIIlIIIIIlIIlIlIlIlIIl
`
`USOOS917821A
`
`5,917,821
`[11] Patent Number:
`United States Patth [19]
`
`Gobuyan et al.
`[45] Date. of Patent:
`Jun. 29, 1999
`
`[54] LOOK-UP ENGINE FOR PACKET-BASED
`NETWORK
`.
`
`[75]
`
`.
`Inventors: Jerome Gobuyan, Ka’nata‘; Wayne
`~th rivet};0ttawa;«~N:=tanBehkt, ,
`Nepea11,zlllofCanada .
`
`[73] Assignee: Newbridge Networks CorporatiOn,
`Kana‘ta, Canada V
`'
`
`[21] Appl. No.:
`
`08/663,263
`
`[22] PCT Filed:
`
`Dec. 21, 1994
`
`[86] PCT No.2
`
`PCT/CA94/00695
`
`§ 371 Date:
`
`Aug. 16, 1996
`
`§ 102(6) Date: Aug. 16, 1996
`PCT Pub. No.: W095/18497
`
`[871
`
`PCT Pub. Date: Jul. 6, 1995
`
`Foreign Application Priority Data
`[30]
`United Kingdom ................... 9326476
`Dec. 24, 1993
`[GB]
`
`Int. Cl.5 ................................................... H04L 12/46
`[51]
`[52] US. Cl.
`.................
`370/392; 370/401
`
`[58] Field of Search
`Wye/392,395,
`370/400, 4 14 5, 465, 466, 351, 389,
`396, 397, 474;, 395/20068
`
`[56]
`
`References Cited
`
`Tv
`.s. '
`PATEN DO
`U
`3/1992-«Eeimer
`5,095,480
`5,463,777 10/1995 Bialkowski et a1.
`
`CUMENTS
`'
`
`370mg
`.................... 370/256
`
`Primary Examiner—«Chm Nguyen
`Attorney, Agent, or Firm—Marks & Clerk
`
`[57]
`
`ABSTRACT
`
`An arrangement is dishlosed for parsing [packets in a packet—
`bascd data transmission network. The packets include
`packet headers divided into fields having values representing
`information pertaining to the packet. The arrangement
`includes an input receiving fields from the packet headers of
`incoming packets, a memory for storing information related
`to possible values of said fields, and a’ device for retrieving
`the stored information appropriate to a received field value.
`The retrieving device comprises a lookuup 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
`
`1
`
`DESTINATION ADDRESS
`
`LOOKUP CONTROLLER
`
`DALE
`RAM
`512KX16
`
`5
`
`AXE
`' t
`Inpu
`
`-
`
`9
`
`LOOKUP ENGINE
`
`CONTROLLER
`
`
`
`
`
`[iii/E
`
`'Rea'sregmbler 3 d 128K x 16
`
`4
`
`’
`
`»
`
`7
`
`11
`
`Output to AXE
`
`' Output to
`Reassembler
`12 '
`
`1o
`
`2
`
`LOOKUP CONTROLLER 512KX16
`SOURCEADDRESS
`__
`ENNI
`
`
`
`
`
`8,
`
`SOURCE ADDRESS LOOKUP ENGINE
`
`UNIFIED 1011
`
`UNIFIED 1011
`
`

`

`US. Patent
`
`,
`
`,Jun..29,1999
`
`‘
`
`Sheetlof 11
`
`5,917,821
`
`100
`
`104
`103
`102
`101
`
`
`
`
`
`
`NLDesT ~ NL-r’Sour-ce
` Addrebs8 Net Layer Protocol Type
`
`
`Address
`Address
`
`
`
`
`
`,
`
`Tree
`Search
`
`“ Tree
`Search
`
`Microcode
`Comparisons
`
`Tree
`Search
`
`Tree
`Search
`
`FIG. 1
`
`1 5
`
`FIG. 2
`
`To ATM
`ControlIII.
`
`From‘ATM
`
`DESTINATION ADDRESS LDOKUP ENGINE
`
`DALE
`RAM
`
`6
`
`
`DESTINATION ADDRESS
`NTR L
`R
`1
`LOOKUPco
`OLE -512KX1:|
`
`IAXE’L 911
`n up
`LOOKUPENGINE
`OutputtoAXE
`
`3%
`pCODCEONTR:LLER
`_FIONX18BROutputglr
`
`Reassembler
`.EQMN-12
`Input
`X
`
`37
`
`eassem er
`
`10
`
`2
`
`_
`SALE
`SOURCE ADDRESS
`RAM
`LOOKUP CONTROLLER
`512K x 16
`,
`’
`FIG. 3
`SOURCE ADOREss LOOKUP ENGINE
`
`8
`
`

`

`US. Patent
`
`Jun. 29, 199-9
`
`.
`
`SheetZof 11
`
`5,917,821
`
`_ 20
`
`'
`I SIB RAM
`SIB DATA BUS OUT I SIB DATA BUS IN
`
`SIB ADDRESS BUS
`
`
`219
`
`INTERFACE RAM
`
`INTERFACE DATA BUS IN
`
`INTERFACE ADDRESS BUS
`
`
`
`
`I D
`
`NIBBLE INDEX
`
`CANADIAN CODE
`
`
`
`OPCODE DIAP PARAMETER
`
`
`
`REGISTER
`
`4o
`
`25
`
`.
`
`IMPORT
`Pom
`
`3 w
`, H
`
`TO/FROM
`SALE, DALE
`
`'
`
`‘
`
`”CODE ADDRESS BUS
`
`ILCDDE DATA BUS IN
`
`ILCODE DATA BUS OUT
`
`- FIG. 4
`
`MICROCODE RAM
`
`'
`
`

`

`US. Patent
`
`Jun..29,.1999
`
`Sheet 3 0f 11
`
`5,917,821
`
`1
`
`'
`DESTINATION ADDRESS LOOKUP ENGINE
`DALE
`DESTINATION ADDRESS
`LOOKUP CONTROLLER
`RAM
`
`512K x 16
`
`
`6
`
`AXE
`Input 44
`.
`32 BIT LATCH
`I
`
`4.2
`
`FIFDNX18
`FIFONx18
`
`-
`
`. I 43
`328|TLATCH
`ReassembIer
`2
`
`Input
`
`4
`
`~
`
`FIFO N x18 11Outputto AXE
`"Home
`Output t0
`“AH?
`558 me
`4
`.28XX16
`10
`-
`'
`’
`
`'LDSNKUURPCEILNIPRRDELSLSER - RAIN/IE
`I 8
`
`
`SOURCEADDRESS’LOOKUP ENGINE
`
`.
`
`Rea
`
`m
`
`r
`
`RAM
`
`12
`
`-
`
`512I<xIG
`
`I/FRAM
`64”
`
`LOOKUP ENGINE
`CONTROLLER
`8Kx32
`DCODERAM
`
`
`
`
`
`FIG. 5
`
`

`

`US. Patent
`
`Jun.29,-1999I
`
`Sheet 4 of 11
`
`.
`
`5,917,821
`
`
`
`520
`
`SIB RAM
`AND RESULTTFIFOS‘
`313mm 'SIBA(3:0) SIBA(19:4)
`
`3
`
`SALE RAM
`SALE
`SALE
`AD(19:4>)-A(3:0)
`
`.
`
`{Gk
`DALE RAM
`DALE
`DALE
`AD(I9:4) A(3:0)
`
`_
`NIBBLE RAM
`
`SALE'
`NIBBLE RAM
`
`DALE
`
`(—42, 43
`
`SNOOP FIFOS
`
`MFD(16:0)
`
`II X2
`
`EFb Rb
`
`INTERFACE RAM
`
`RAM DII 5:0)
`
`RAM A(4:0)
`
`
`
`50
`
`LE GE
`
`m
`
`INSTRUCTION
`REGISTER
`
`
`
`
`YREG
`
`.-
`- -__-
`SPDI
`
`-
`
`BITS
`
`IICODED(31:0)
`pCODEAULO)
`MICROCODE RAM
`
`

`

`US. Patent
`
`11111.29, 1999
`
`Shéet 5 0f 11
`
`5,917,821
`
`‘
`
`' ARR
`
`INIBBLEINDEMR)
`
`POINTER _
`
`
`DALE RAM
`512K X 16
`
`
`
`
`
`FIG. 7
`
`8000 n-FFFF n
`
`DALE RAM
`512K X 16
`
`8000 n—FFFF n
`
`SIBRAM128KX16
`:
`0000 n-omn
`.
`
`POWER ARRAY (058 = 0
`
`NEXT POINTER ARRAY POINTER (19-0)
`
`X .
`
`
`
`
`
`POINTER ARRAY (M38: 1)
`
`SIB (MSB = 0)
`
`FIG. 8
`
`16x16
`
`0
`
`16x16
`
`

`

`U.S. Patent
`
`Jun. 29, 1999
`
`Sheet 6 of 11
`
`5,917,821
`
`MAC ADDRESS TREE - EXAMPLE $008FC2865739.
` ROOT POINTER
`‘
`.
`‘N‘BWER
`'
`"1/45...
`NIBBLE2=$0
`/" \ ........
`
`~
`
`»
`
`NIBBLE4
`
`NTBBLE9=$5
`
`NIBBLE10=$7
`
`NIBBLE1=1 $3
`NIBBLE12: 39
`
`NTBBLE3=$8 /’4\-\~\ 4
`
`NIBBLE5_so _____ ______ fi............
`NIBBLE6:$2
`II/IIIsIIIIII'I III
`NiBBLE8:$6
`...-......ll...TRIEPTII'I-I.I€Z:\\IIIIILIX
`« NIBBLE7=$8
`\ ________
`
`
`~
`.....\
`"4'3:/ .\ __
`
`III IIIIIIIIIIII
`
`--
`
`x
`
`. """"'-
`
`FIG. 9
`
`SIB "
`
`ROOT POINTER
`
`OUT #1
`
`.
`
`:
`
`00m
`
`‘
`
`OUI #3
`
`
`
`

`

`‘
`
`» US. Patent
`
`'Jun.29, 1999
`
`Sheet70f 11
`
`5,917,821
`
`
`
`SOURCE ADDRESS LDDKUPENGWE
`
`Address Match
`Address Match Fail
`.
`
`FIG. 11.
`
`313 Pointer
`
`Null Painter
`
`
`
`
`
`
`DESTINANON ADDRESS LOOKUP ENGINE
`
`Address Match
`
`Address Match Fail
`
`FIG. 12
`
`818 Pointer
`
`Null Pomter
`
`

`

`US. Patent
`
`Jun. 29,1999
`
`Sheet 8 0f 11
`
`5,917,821
`
` ’
`
`‘ pCODE’WORD
`
`LP
`
`BTT TO 44.
`
`.
`
`BIT 3 —O
`
`STBADDRESS
`
`FIG. 13
`
`
`
`
`
`Status Flags
`
`Purser
`~
`_NNEN§§:
`
`
`
`Status Flags III'iTiIII
`NANTN
`RP~ROUTEDPDU
`
`,
`Encap Flags II.-
`'
`FU-FUTUREUSE
`EN-MACENCAPFORMAT
`.
`
`W0 Flags
`
`PA-PROTOCOLACNVE
`NITA‘ETNNETNCDE
`MH-MULTl-HOMED
`
`v
`
`.
`FIG' 14
`
`
`
`,
`
`
`
`
`
`
`
`
`
`
`STATION INFORMATION BLOCK
`
`2.
`
`Prom Area
`Prom 2 Area
`ProtoBArea
`PmMArea
`Pr0t05Area
`Other Area Pointer
`.Prot01 DesrArea
`Prom 2 WW
`ProrosDesrArea
`Proto 4 Desi Area
`Proto‘ 5 Best Area
`-Enc
`Other D‘estAre‘a Pointer
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Jun..29,1999
`
`Sheet 9 0f 11
`
`5,917,821
`
`
`
`PA-PROTOCOL ACTlVE
`PV-PROTOCOL VALlD
`
`!
`|—-——J———-—J——.~L_....L..___I___I_L..__J
`L..L..J_LJ....J_J.._1_LJ_LL_L_LJ_J_J
`]
`,
`,1
`- OPhoteFlage}
`L
`IPA it’ll L
`r
`'l
`r
`1|
`
` IPX Raw Area
`
`
`
`
`
`I
`
`Has
`
`lPX'EtberArea
`
`_— I
`
`PX 802.2 Desi Area
`
`lPX SNAP Desi Area
`lPX Raw DestArea
`
`’
`
`lPX Ether Desi Area
`-
`
`
`—_
`
`,
`
`PORT INFORMATION BLOCK
`
`Desi Area nibble i
`Desi Area nibble 2
`Dest Area nibble 3
`
`FIG. 15
`
`
`
`
`Source Area
`Pointer
`
`E 3 nibble destination area
`
`.2 nibble destination area
`
`/\
`
`ARX-ALLOW ROUTING PROTOCOL X
`FIG. 16
`
`
`
`Filtering Rule
`
`
`
`

`

`US. Patent
`
`Jun. 29, 1999
`
`Sheet 10 0f 11
`
`5,917,821
`
`-FIFO not empty
`
`
`
`osltop AND snpop
`not done
`
`
`
`OHFO not empty
`AND (Group=7)
`
`'
`
`
`,
`
`-FIFO not empty
`
`
`
`
`~HFO not empty
`AND (Group=7)
`
`
`oFlFO empty
`
`AND (Group<4)
`0R (Groupz6)
`
`
`
`
`OFIFO not empty
`AND (Group=5)
`
`0SI.B_TA true
`
`FIG. 17
`
`-S|B_TA false
`
`

`

`US. Patent
`
`’Ju11.29,1999
`
`Sheet 11 0f 11
`
`5,917,821
`
`increment Branch instructions (Group 2 no wait states)
`
`.FL/“L/fifi,
`p [L
`PCLK/ \ /\
`vrAddr -
`
`I/F Data
`.OOOOOOir'O
`Valrd i/F Datam
`OOOOOOirO
`VaiidiFDatin
`IOIOIIIOOOII
`instAddt
`PC
`IPC+i
`PC+disnI
`inst Re
`IOIOIOIOIIOOIOIOI VardOcode
`OOOOOOO
`VaiidOnoode
`OIIOIOIOIIOI
`W
`Condition
`
`
`
`TRUE.OOOOOOOOOOOOOOOOOOOOOOOOO'OOOOOOOOOOOOO FALSEIOIOIIIIOOOI
`State '-.--|'
`EXEC‘CYCLE umPCaADD
`
`PC
`
`F|G_ 18
`
`i—ncrement/Branchinstruction increment/Branchinstruction
`.
`(Condition;TRUE)
`,(Condition=FALSE)
`
`SIB RAM Access Instructions (Group 5)
`POLK I
`- U U U \
`sre_no
`
`
`
`/
`
`sre_cn
`
`SiB_CS
`
`’
`
`
`
`SIB_Addr
`I
`srBtWEbiWrrer —_—
`S’iB_Data(Write)
`'O'OIOIOIOIOIOIOIOIOIOIOIOIOIOu-.OIOIOIOIOIOIO
`. SiB_OEb(Read)-
`_
`SiB_Data(Read)
`IOIOIOOIOIOIIOIOIOIOIOIOIOIOIOIOIOIOIOIOIOIOIOIOI-IOIOIOIOIOIOIO
`
`Inst Addr
`-PC
`.'PC+1
`inst Reg
`IOIIIOOO..OOIOIOI Vaiid Oncode
`.OIO.I.OOOOIO
`State
`I 82' 83 II
`I
`I
`I
`EXEC_CYCLE - .
`' -
`
`
`
`
`w—§|B RAM Access
`(No wait states)
`‘FIG. 19
`
`

`

`5,917,821
`
`1
`
`LOOK-UP ENGINE FOR PACKET—BASED
`NETWORK
`
`BACKGROUND OF THE- INVENTION
`FIELD OF THE INVENTION
`
`This inventionrelates torthe fieldof 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
`flexibility;
`Packet-based networks overcome many of the disadvan—
`tages of circuit—based networks. In a packetnbased network,
`the data are assembled into packets containing one or more
`address fields which define the context of a packet, such as
`protocol type and relative positions of other fields 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-
`flows 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 flexibility in han-
`dling different packet types and can be upgraded to handle
`new packet types as they are defined. 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 specifi—
`cally directed toward the types of operations required in
`packet parsing and so they tend to. be inefficient. 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 flexibility.
`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 —b ased 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 fields having values representing infor-
`mation pertaining to the packet, said arrangement compris-
`ing an input memory for receiving fields. from said packet
`headers of incoming packets; and a look-up engine for
`retrieving stored information appropriate to a received field
`value. The look-up engine includes at least one memory-
`storing information related to possible values of said fields
`in a hierarchical tree structure and associated with a respec—
`tive field of packet headers; a memory centroller associated
`with each said memory storing information related to pos—
`sible values of said fields 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 or said look-up engine.
`The memory and retrieving means constitute a look-up
`engine, which is the central resource containing all infor—
`
`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 switchingto be" achieved in a briclge4router,
`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 56 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 fixed 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 (cg. MAC‘ address) is divided into nibbles which
`are used as indices to subsequent tables. The 1.6 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 final 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 fields 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
`specific 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.
`
`filtering
`The look—up engine also performs protocol
`between areas. The system allows devices to be grouped
`arbitrarily into areas on a per protocol basis and defines
`filtering 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 find the filtering rule between the two
`areas. Separate filtering rules are defined 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 field in the packet being examined. The controller
`moves this pointer to the next field in the packet after all
`decisions based on the current field are made.
`
`the current field is
`At each decision point on a tree,
`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 field pointer. Other—
`wise the field pointer is left alone and controller branches to
`new code to compare the current field to a different value 01‘
`range. This process is repeated'until a final 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
`
`u:
`
`30
`
`15
`
`20
`
`25
`
`3O
`
`35
`
`4O
`
`45
`
`SO
`
`60
`
`65
`
`

`

`5,917,821
`
`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 field’s size.
`The look-up engine implements other optimized instruc-
`tions which perform. bit
`level
`logical comparisons and
`conditionalbranches within the same Cycle as well as other
`instructions tailored to retrieving data from nibble—indexed
`data structures.
`
`5
`
`10
`
`15
`
`4
`FIG. 9 shows one example of a MAC search tree;
`FIG. 10 shows the effect of the organizationally unique
`identifier of the MAC addresses on the size of the search
`tree;
`
`FIG. 11 shows the source address look—up engine table;
`FIG. 12 shows the destination address look-up table;
`FIG. 13 illustrates thelleoleup-engine addressing modes;
`FIG. 14 shows a station information block;
`FIG. 15 shows a port information block;
`FIG. “shows an example of protocol filtering;
`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 engin'e‘(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—
`25 net packets. This packet rate corresponds to a lock—up
`request occurring every 5.6 ,usecs. The LUE is used each
`time a packet
`is received 011’
`the Ethernet or the ATM
`network. The type of information that the engine provides
`depends on the direction of packet flow and the type of
`packet.
`‘
`The look-up engine provides all the information needed to
`find 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 fields 100, 101, a network
`layer protocol type field 102, and network layer destination
`and source address fields 103, 104. FIG. 1 also illustrates
`how the header is parsed in accordance with the invention.
`All fields execpt'lOZ are parsed using a tree searchiThe Net
`Layer Protocol Type field 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 significance only. The Control Processor and
`ATM are each assigned a port.
`The following definitions are special cases of a PortSet:
`
`The look—up engine is preferably divided into the follow~
`ing sections:
`a) one or more nibble tree' address look—up engines (ALE)
`b) one ‘micrOcode engine
`Each ALE is ’uSed to search for addreSSes in a tree
`structure in its oWn large bank 01’ 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 (SALE). 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-specific
`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 fields having values
`representing information pertaining to the packet, compris-
`ing storing information related to possible values of said
`fields, receiving fields from said packet headers of incoming
`packets, and retrieving said stored information appropriate
`to a received field value, characterized in that said informa-
`tion is stored in a memory organized in. a hierarchical tree
`structure.
`
`20
`
`4O
`
`45
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The invention will 110w 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 first embodiment of a
`lock-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 (ALE) memories;
`FIG. 8 is a diagram illustrating search tree operation in an
`AIE;
`
`50
`
`SinglePortSet
`a l’ortSet with a single bit set.
`,
`HostPortSct
`'
`a SinglePortSet corresponding to the Control Processor
`Myl’ortSet
`a SinglePortSet corresponding to the source port of this packet.
`Nulll’ortSct
`a l’ortSet of no, parts.
`
`60
`
`A Connection Identifier (CI), which is a 16 bit value with
`local significance only,
`is used to map connections into
`VPI/VCI values.
`
`The: following definitions are special cases of CI:
`
`65
`
`Mesh_____CI
`:1 CI corresponding to a path towards the destination endstalion’s
`Brid ge-router.
`
`

`

`5,917,821
`
`5
`—continued
`Nullm,.CI
`a CI connected to nothing. It is returned when the destination is
`attached lo, the local Bridge-router or if the connection is not
`allowed.
`RS,»CI
`a (31 corresponding to a path to the Route Server.
`ABS‘_C‘E”
`'
`'
`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.
`
`
`Unicast_DA
`a MAC layer destination address of an end-station.
`RouterMDA
`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.
`BroadcastfiDA
`the brcadcast MAC layer address (all ones) which is received by
`all endvstations. It cannot be a source address;
`'
`Multicast_DA
`a multicast MAC layer address (group bit set) which is received by
`end—stations that recognize that multicast address.
`
`U1
`
`10
`
`15
`
`20
`
`25
`
`3O
`
`40
`
`45
`
`50
`
`60
`
`6
`The Bridge command instructs the AXE (Transfer
`Engine) to use RFC—1483 bridge encapsulation. BridgeProp
`command instructs the AXE to use bridgc~router encapsu—
`lation (include source Portset in encapsulation)
`
`
`i
`
`UnknownMSA »> Bridgel’rop, anLWCI, I—IostPortSet, MyPortSet
`"‘ Unknowns», - sendto 1:1me Spanning Tree processing
`" HP will decide whether to forward it to ABS for learning,
`depending on Spanning Tree state
`Unicast_DA —> Bridge, Meshicl, NullPortSet
`“ DA in the same area on a different Bridge-router
`UnionstiDA ~> Bridge, NulthI, NullPortSet
`* DA not in the satire areatreject)
`" Protocol not allowed to bridge-router
`* DA on the same port
`Unicast_'DA —> Bridge, Null_‘CI_, SinglePortSet
`* DA in the same area on the same Bridge-router but on a different
`port
`Uu'knownuDA ~> Bridgel’rop, ABSHCI, Nulll’ortSet, Myl’ortSet
`* DA not found in the table — send to ABS for flood processing
`BroadcasthA ~> .ISridchrop, ABSWCI, NullPortSet, Myl’ortSct
`‘* Broadcast DA — Send to Control Processor for broadcast
`processing
`MulticastMDA —> BridgeProp> ABSMCI, NullPortSet, MyPortSet
`* Multicast DA ~ Send to ABS for multicast processing
`MulticasthA —> Bridgeprop, NulleI, HostPortSet, MyPorlSet
`” Multicast DA is of interest to HP (eg Spanning Tree)
`* HP will decide whether to forward it to ABS for inulticast
`processing
`
`p Routing occurs when the destination address is the unicast
`Route Server address. Filtering rules between areas are
`explicitlydefined 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 field expires _
`
`Unicast_NLDA —> Route, Mesh_Cl, NullPortSet
`* NL node on a different bridge~router
`Unicast._NLDA —> Route, NulleI, Singlel’ortSet
`* NL node on the same bridge-router (could be same port)
`' Unknown_NLDA M> Bridge, RS__Cl, NullPortSet
`* unknown NL node — send to Route Server
`UnknownmProtocol
`~> Bridge, RS,_CI, 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 Identifier) 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. Abit
`
`(NL) addresses are network protocol
`Network layer
`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 Suhnet Node
`
`
`1r
`32
`8/16/24
`variable
`variable
`IPX’
`80
`n/a
`32
`48
`(MAC address)
`8
`10
`
`'1 6
`38
`(32 =
`'HIORD')
`(6 = srtbnet)
`
`AppleTalk
`DECNet
`
`24
`64
`
`n/a
`16
`(reserved)
`
`The look«'up engine handles unicas’t 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, PortSct
`
`where Input is derived from the first 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 unieast
`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/filtering is performed;
`'othcrwise, 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.
`
`

`

`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 NI address There'sult of th’e‘look—u’p
`will have the form:
`
`
`
`
`
`
`—>Input ‘PortSet
`
`Filtering is not performed in this direction. It‘is assumed
`that the all filtering 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.
`
`
`Unicast__DA —> SinglePortSet
`* DA on this Bridge-router
`Unknown_DA —> NullPortSct
`* DA not in the table (drop) ~ this situation should not occur.
`UnicastmNLDA —> Singlel’ortSet
`* NLDA on this Bridge—router
`Unknown_NI:/DA —> Nulll’ortSet
`* NLDA not in the table (drop) -- thissituation should not occur.
`Broadcast,,,,,,DA,PortSet
`—> PortSet
`"‘ Proprietary Broadcast request received from RS
`MulticasL‘DAJ’ortSet
`~> PortSet
`" Proprietary Multicast request. received from RS
`Uiflmown_..J)A,PortSet
`~>
`I’olrtSet
`* Proprietary Flood request received from RS
`
`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 rant 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 m‘icrocoded engine
`tailored for efficient 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-processorsto 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 appr0~
`priate FIFO 11, 12.
`FIGS. 5 show an alternative embodiment of the loop-up
`engine and controller. In FIG. ‘5, the LEC3 includes a 64x16
`l/F (Interface) ram41 connected to FlFO’s 42, 43 (First-in,
`First—out memories) respectively connected to latches 44, 45
`receiving AXE (Transfer Engine) and reassembler input.
`Referring now to FIG. 6, the LEC 3 also contains several
`registers, Which will now be described. Register select
`instructions are provided for the register banks (XPO—7,
`1.,130—7).
`
`8
`Index Pointer register (IP) 50 is a byte index into the UP
`RAM 21. Under normal operation, the index pointer register
`50 points to the enrrent packet field being examined in the
`I/F RAM 21 but it can be used whenever random access to
`the UP RAM 21 is required.
`The IP 50 can be modified in one of the following ways:
`1) loaded by the LOADIP instruction (cg. to point to the
`. beginning. of the packet) ,
`,.
`.
`.
`2) incremented by 1 (byte compare) or 2 (word compare) if
`a branch condition is not met.
`3) incremented by 2 by a MOVE (IP)+ type instruction.
`Data Register 51 contains the 16 bit value read from I/F
`RAM 21 using the current IP. The DR 51 acts like a one
`word cache; the LEC keeps its centents valid at all times.
`Program Counter 52 points to the current microcode
`instruction. It is incremented by one if a branch condition is
`true, otherwise the displacement field is added to it.
`The hookup Pointers (LPIF7) 23 are 16 bit registers
`which contain pointers to the SIB RAM 20. The Ll’s are
`used to store pointers whenever milestones are reached in a
`search. One LP will typically point to a source SIB and
`another will point to a destination SIB. The LP provides the
`upper 16 bits of the pointer; the lower 4 bits are provided by
`the microcode word for indexing into a given SIB.
`The LPs are also used to prime the SALE and DALE with
`their respective root pointers.
`X,Y Registers 53, 54 are general purpose registers where
`logic manipulations can be made (AND, OR, XOR). They
`are used for setting and clearing bits in certain werds in the
`SIB RAM (e. g. Age bit) and to test for certain bits (cg. status
`bits). The 'X Register 53 can be selected as Operand A’to the
`Logic Unit While the Y Register can be selected as Operand
`B.
`
`The BYZ and BYNZ instructions conditionally branch on
`Y=0 and Y<>0 respectively.
`The Y Register 54 is the only register source for moves to
`the result FIFOs.
`The X Register 53 can be saved to or restored from X‘
`Registers (X’O—X’7) 55. The mnemonic symbol for the
`currently selected X‘ register is XP.
`The S Register 56 is a pipelining stage between SIB RAM
`20 and the L