United States Patent
`
`[19]
`
`[11] Patent Number:
`
`5,920,886
`
`Feldmeier
`
`[45] Date of Patent:
`
`Jul. 6, 1999
`
`US005920886A
`
`[54] ACCELERATED HIERARCHICAL ADDRESS
`FILTERING AND TRANSLATION USING
`BINARY AND TERNARY CAMS
`
`_
`Inventor: David C. Feldmeier, Mornstown, N.J.
`
`[75]
`
`Primary Examiner—l:‘.ddie P. Chan
`Assistant Exrim.irier—Kevin Verbrugge
`Attorney, Agent, or Firm—Skjcrve11, Morrill, MacPhcrson
`Franklin & Friel; Alan H. MacPherson; Fabio E. Marino
`[57]
`ABSTRACT
`
`A method and apparatus are provided for performing hier-
`archical address translation by translating each ternary hier-
`archical address into a binary address and a binary priority
`mask and storing the binary addresses in the binary CAM.
`A binary search of the priority masks is then performed by
`searching the CAM with a priority mask and choosing a next
`priority mask depending on the results of the search of the
`CAM until a Correct matching entry (Lew the matching entry
`with the lowest hierarchical level) is found. This technique
`only requires 1og2N searches of the CAM, where N is the
`number of hierarchical levels represented by the priority
`field. A method and apparatus are also provided for per-
`formin
`hierarchical address translation b
`slorin
`table
`%
`Y
`1%
`entries including a priority field in a ternary CAM and
`performing only a fixed number of searches of the
`Finally, a method and apparatus are provided for storing a
`translated hierarchical address in a cache CAM and using
`the cache CAM to perform successive hierarchical address
`translations.
`
`16 Claims, 16 Drawing Sheets
`
`[73] Assignee-2 Music Selllicfllldl-10101‘ C01‘[J0l‘flti0ll,
`HaCk€tlS10WT1, N-1
`
`[21] App1_ No; 03/318,073
`
`[22]
`
`Fflfidi
`
`M312 14, 1997
`
` 6
`
`Int. Cl.
`
`...................................................... G(_)6F_l2/1-0
`[51]
`7]-1/108? 711/2065 365/168
`[521
`[58] Field Of Search .............................. .. 711/108, 206,
`711/207, 2 2; 365/49, 168; 326/'59
`
`56
`
`[
`
`]
`
`-
`C ted
`R f
`1
`e erences
`Us. PATENT DOCUMENTS
`
`.......................... .. 395/200
`7/1994 Moati et al.
`5,329,618
`1/1995 MCAL11°Y 61 a1~ -
`370/'54
`5,335,413
`5/1995 Spinney .......
`370/'60
`5,414,704
`6/1995 Lin ...............
`365,/49
`5,422,838
`5,568,415 10/1996 McLellaii et al.
`...................... .. 365/49
`
`COMPARAND
`\-1000
`
`HIGHEST
`PRIORITY
`
`1070
`
`
`
`
`IIIIIII III
`
`ADDRESS
`ENCODER
`
`
`MATCHING
`ENTRY
`
`
`
`
`
`IIIIIIIII
`
`IIIII
`
`1060
`
`1
`
`ARISTA 1015
`
`1
`
`ARISTA 1015
`
`

`
`U.S. Patent
`
`Jul. 6,1999
`
`Sheet 1 of 16
`
`5,920,886
`
`FIG,
`
`1B (PRIOR ART)
`
`2
`
`

`
`U.S. Patent
`
`Jul. 6,1999
`
`Sheet 2 of 16
`
`5,920,886
`
`
`
`
`
`ROUTING DESTINATION
`
`
`
`
`
`
`
`NUMBER
`
`
`
`908 xxx xxxx
`
`FIG, 2A (PRIOR ART)
`
`ENTRY
`
`NUMBER
`
`NUMBER
`
`ROUTING DESTINATTON
`
`
`
`—_ 9
`
`
`
`
`9=
`
`
`:E F
`
`IG. 2B (PRIOR ART)
`
` ENTRY
`
`NUMBER
`
`LEVEL
`
`ROUTiNG DESTINATION
`
`999 979 99
`E 999 999 >999<
`999 >99 99
`
`II
`
`3
`
`

`
`U.S. Patent
`
`Jul. 6,1999
`
`Sheet 3 of 16
`
`5,920,886
`
`STORE ADDRESSES
`IN CAM IN
`REVERSE
`HIERARCHICAL
`“DER
`
`SEARCH CAM FOR
`ADDRESS
`
`RETRIEVE FIRST
`MATCHING ENTRY
`FROM CAM
`
`310
`
`320
`
`330
`
`FIG. 3A (PRIOR Am)
`
`START
`
`
`
`
`
`340
`
`SEARCH BINARY
`CAM FOR ADDRESS
`AND LOWEST
`PRIORITY MASK
`
`
`
`SEARCH BINARY
`CAM FOR ADDRESS
`AND NEXT HIGHER
`PRIORITY MASK
`
`
`
`
`
` RETRIEVE SINGLE/
`FIRST MATCHING
`
`ENTRY FROM
`BINARY CAM
`
`FIG_ 3B (PRIOR ART)
`
`
`
`4
`
`

`
`U.S. Patent
`
`Jul. 6,1999
`
`Sheet 4 of 16
`
`5,920,886
`
`START
`
`
`
`360
`
`
`
`SEARCH TERNARY
`CAM FOR ADDRESS
`AND PRIORITY LEVEL
`IX...X
`
`
`
`
`
`
`
`REPLACE LEAST
`SIGNIFICANT 1 OF
`PRIORITY MASK WITH
`
`
`
`
`RIORITY MASK‘?
`
`REPLACE MOST
`SIGNIFICANT X
`
`
`SEARCH TERNARY
`CAM WITH
`
`ADDRESS AND NEW
`
`PRIORITY MASK
`
`
`
`
`
`
`SINGLE
`MATCHING
`ADDRESS?
`
`
`
`395
`
`FIG. 3C (PRIOR ART)
`
`
`
`
`
`RETRIEVE
`MATCHING ENTRY
`FROM TERNARY
`CAM
`
`
`
`5
`
`

`
`U.S. Patent
`
`Jul. 6,1999
`
`Sheet 5 of 16
`
`5,920,886
`
`ADDRESS (BINARY)
`
`
`
`MASK (BINARY)
`11111011
`11011011
`10111011
`
`10000011
`
`
`
`NUMBER
`
`A
`11110><00
`11x10><00
`1><111x00
`1><><><xx00
`
`C
`
`(PRIOR ART)
`
`
`
`
`
`ENTRY
`
`NUMBER
`111101xx
`fl 11110100
`
`ADDRESS (BINARY)
`11110100
`11110100
`
`MASK (BINARY)
`11111100
`11111111
`
`
`
`
`FIG_ 4B (PRIOR ART)
`
`6
`
`

`
`U.S. Patent
`
`Jul. 6,1999
`
`Sheet 6 of 16
`
`5,920,886
`
`
`
`START
`
`SEARCH BINARY
`
`CAM FOR ENTRY
`WITH MEDIAN
`
`PRIORITY MASK
`
`
`
`SEARCH BINARY
`
`CAM FOR ENTRY
`
`WITH HIGHER
`
`
`
`MULTIPLE
`MATCHING
`
`
`
`ENTRIES?
`PRIORITY MASK
`
`
`NO
`
`
`
`
`
`
`
`
`MATCHING
`ENTRIES?
`
`RETRIEVE SINGLE/
`FIRST MATCHING
`
`ENTRY FROM
`
`BINARY CAM
`
`FIG. 5
`
`SEARCH BINARY
`
`CAM FOR ENTRY
`WITH LOWER
`
`PRIORITY MASK
`
`7
`
`

`
`U.S. Patent
`
`Jul. 6,1999
`
`Sheet 7 of 16
`
`5,920,886
`
`ENTRY
`
`NUMBER
`
`ADDRESS (BINARY)
`
`MASK (BINARY)
`
`
`
`
`
`II
`
`II
`
`
`
`FIG. 6A
`
`ENTRY ADDRESS (BINARY)
`K so FC 00 00
`ac FC so 00
`ac FC 00 00
`ac FC 00 23
`
`
`
`FIG. 6B
`
`8
`
`

`
`U.S. Patent
`
`Jul. 6,1999
`
`Sheet 8 of 16
`
`5,920,886
`
`
`
`
`
`
`
`
`
`ADDRESS MASK
`
`CAM MASK
`
`MATCHING ENTRIES
`
`FF FF F0 00
`
`O0 00 OF FF
`
`0, 2, 3,
`
`(MULTIPLE MATCHES)
`
`FF FF FF O0
`
`O0 O0 00 FF
`
`2, 3 (MULTIPLE MATCHES)
`
`FF FF FF FF
`
`O0 00 O0 O0
`
`3 (CORRECT MATCHING ADDRESS)
`
`FIG. 6C
`
`ADDRESS MASK
`
`CAM MASK
`
`MATCHING ENTRIES
`
`FF FF F0 00
`
`O0 00 OF FF
`
`0, 2, 3,
`
`(MULTIPLE MATCHES)
`
`FF FF FF O0
`
`00 00 OO FF
`
`2, 3 (MULTIPLE MATCHES)
`
`FF FF FF FF
`
`O0 00 OO 00
`
`(NO MATCHING ADDRESS)
`
`FIG. 6D
`
`
`
`
`
`610
`
`620
`
`630
`
`
`
`
`
`610
`
`620
`
`630
`
`ADDRESS MASK
`
`CAM MASK
`
`MATCHING ENTRIES
`
`610
`
`FF FF F0 00
`
`00 00 OF FF
`
`1
`
`(CORRECT MATCHING ADDRESS)
`
`FIG. 6E
`
`
`
`BIO
`
`640
`
`ADDRESS MASK
`
`CAM MASK
`
`MATCHING ENTRIES
`
`FF FF F0 00
`
`00 00 OF FF
`
`(NO MATCHING ADDRESS)
`
`FF FF O0 O0
`
`O0 00 FF FF
`
`0,
`
`I, 2, 3 (MULTIPLE MATCHES)
`
`FIG. 6F
`
`9
`
`

`
`U.S. Patent
`
`Jul. 6,1999
`
`Sheet 9 of 16
`
`5,920,886
`
`o.R\5&2
`
`0:328m
`
`OE
`
`EownEmax
`
`Ejofizoo
`
`10
`
`5z.§%Io¢z_8bz§m_Qozo._
`
`
`EE
`
`
`SmmoEo§:_,E
`EEIH
`
`_._o:;m5%,:wow
`fig
`
`
`zo_:_,__Eooz_Som_
`Q9%E
`
`
`
`mészzocfim
`
`HE!
`
`ma
`
`E
`
`10
`
`
`

`
`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 10 of 16
`
`5,920,886
`
`START
`
`PRIORITY
`LEVEL TO BIT MASK
`
`REPRESENTATION
`
` TRANSLATE
`
`SEARCH CAM FOR
`
`ENTRY AND
`PRIORITY LEVEL
`
`930
`
`
`
`pEI§’R.II°IE3EL
`WITH MATCHING
`ENTRHES
`
`Mum
`MATCHING
`ENTRIES?
`
`
`
`
`SEARCH CAM FOR
`ENTRY AND
`
`
`HIGHEST
`
`PRIORITY LEVEL
`
`940
`
`
`
`
`RETRIEVE
`MATCHING ENTRY
`
`FROM THE CAM
`
`
`
`
`
`FIG. 9
`
`11
`
`11
`
`

`
`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 11 of 16
`
`5,920,886
`
`COMPARAND
`
`‘1000
`
`FIG. 10A
`
`1060
`
`PRIORITY
`
`12
`
`12
`
`

`
`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 12 of 16
`
`5,920,886
`
`
`
`START
`
`1130
`
`RETMEVE ENTRY
`
`
`
`STORE ADDRESS
`TRANSLANONIN
`CACHE CAM
`
`RETURN MATCWNG
`ENTRY
`
`
`
`FIG.
`
`11
`
`13
`
`13
`
`

`
`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 13 of 16
`
`5,920,886
`
`
`
`
`
`538:_,_o_5§:mmm#_8<
`
`m5m_:oE9:5:8
`
`0éoamz
`
`méogmz
`
`<V2952
`
`@353m$§<n__
`
`2.0
`
`E
`
`14
`
`M38E55Sn_z_
`
`14
`
`

`
`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 14 of 16
`
`5,920,886
`
`
`
`
`
`M3382zo_5sEammyaa
`
`$.09mmgfiA:
`
`E.wE
`
`15
`
`Eéma
`
`<V2252
`
`
`
`M38fi._v_o<n_5%
`
`15
`
`

`
`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 15 of 16
`
`5,920,886
`
`8aa
`
`oneoneoneone
`
`oB_
`
`Eon5&8Eon5&8Eon5&8Eon5&8
`
`
`
`2%,:I023
`
`
`
`
`
`Eommmoomn._oEzoo_§_gm
`
`Eon::z_
`
`IE9:Ez_
`
`22
`
`II%Eaz_
`
`22
`
`Eon5nz_
`
`16
`
`16
`
`
`

`
`U.S. Patent
`
`Jul. 6, 1999
`
`Sheet 16 of 16
`
`5,920,886
`
`oomw
`
`
`
`~:¢z____r|||||||||||||||||1a_IIIIL _mxo<1Ho<mHxm_Ho<mHxm_coo.__mzmgo Ho<m_xm__mmmmQQ<_o<mHxmmamaoH=mz_____________M4390:m¢>h_Wo_zwEm%Broo xmo;_mz1_________M43902o___MJDQQEzocomzzoo xzmmm_Ema;__HgmpgowIIIIIIIIIIIIIIIIIIFF|J_____mmmzgz_¢=¥oo4__mmmmQQ<
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`3.UE
`
`_
`
`17
`
`17
`
`
`
`

`
`5,920,886
`
`1
`ACCELERATED HIERARCHICAL ADDRESS
`FILTERING AND TRANSLATION USING
`BINARY AND TERNARY CAMS
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`
`The present invention relates generally to data commu-
`nication networks and, in particular, to a method and appa-
`ratus for performing accelerated hierarchical address filter-
`ing and translation.
`2. Description of Related Art
`Address translation is the process of mapping an address,
`such as the network address contained in a packet, to some
`desired information. Examples of desired information
`include determining the output port of a switch to which a
`packet is to be sent and determining the address of the
`next—hop router for the routing of Internet Protocol (IP)
`datagrams. Address filtering is a process similar to address
`translation, except that rather than retrieving the data asso-
`ciated with an address,
`the process simply determines
`whether the address exists in a table of addresses. The term
`address translation, as used herein, includes both address
`translation and address filtering operations.
`With respect to routing, addresses can be categorized as
`either flat addresses or hierarchical addresses. FIGS. 1A—1B
`illustrate examples of flat and hierarchical addresses. Flat
`addresses are addresses that have no internal structure that
`
`can be used in protocol processing of the address. Ethernet
`address 110 of FIG. 1A is an example of a flat address.
`Although Ethernet addresses have a structure (e.g., one part
`of the address denotes the manufacturer of the equipment
`using that address), that structure is not relevant to protocol
`processing operations, such as routing. Many techniques
`have been developed for accelerating flat address transla-
`tion. As these techniques are well known to those skilled in
`the art, they are not further discussed herein.
`Hierarchical addresses are addresses that have an internal
`
`structure that can be used in protocol processing of the
`address. Examples of hierarchical addresses include Internet
`Protocol
`(IP) v.4 addresses,
`IP v.6 addresses, E.164
`addresses (used in ATM network protocol processing), and
`telephone numbers.
`Telephone number 120 of FIG. 1B is used to illustrate the
`internal structure of a hierarchical address. Consider tele-
`
`phone number 120. The highest level of the hierarchy is
`denoted by area code 130, which is used to identify tele-
`phone numbers in area 135. The next level of hierarchy is
`central oflice code 140, which is used to identify telephone
`numbers in central oflice zone 145. The lowest level of the
`hierarchy is station number 150, which identifies the specific
`telephone subscriber 155 among those serviced by the
`station for central office zone 145.
`
`The hierarchical structure of a telephone number is used
`when determining how t.o route a call through the telephone
`network. For example, if a call both originates and termi-
`nates in central office zone 145 (i.e., both the source and the
`destination numbers have central oflice code 140), then the
`telephone call pa$es only through the central oflice for
`central office zone 145. If a call both originates and termi-
`nates in area 135 (i.e., both the source and destination
`numbers have area code 130), no long-distance carrier is
`used to carry the call. Note that a flat address can be viewed
`as a hierarchical address with a single level of hierarchy.
`Thus, any address translation technique that operates on
`hierarchical addresses can also be applied to flat addresses.
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`60
`
`65
`
`2
`Hierarchical addresses allow for processing of addresses
`without the need for storing information about all addresses
`to be processed.
`Information about entire classes of
`addresses is stored in a single entry. For example, if a call
`originates within area 135 and terminates in an area having
`a different area code, the correct action is to forward the call
`to a long distance carrier, regardless of the area code of the
`destination telephone number. Thus, a single entry in the
`table determines the handling of any telephone call to an
`area code other than area code 130.
`
`In order to translate a specific telephone number into an
`action to be performed in the protocol processing of a call,
`a look-up table is used to store various hierarchical
`addresses, each corresponding to a specific action to be
`taken in routing the call.
`FIG. 2A illustrates a typical prior art routing table used to
`route calls originating in area 135. In FIG. 2A, entry A
`represents a hierarchical address that matches all telephone
`numbers in the “908” area code and the “979” central oflice
`
`code. This is accomplished by inserting don’t. care (X)
`values into the entries to indicate any valid value in the
`corresponding digit of the address compared to the entry. In
`other words,
`table entry “908-979-XXXX” matches all
`telephone numbers between “908—979-0000” and “908-979-
`9999”. Likewise, entry B represents all telephone numbers
`in the “908” area code and the “S52” central office code.
`
`Entry C, in turn, represents all telephone numbers in the
`“908” area code regardless of their central olfice code.
`Finally, entry D represents all long distance telephone num-
`bers. Any telephone number that is compared to the table
`entries matches one or more entries in the table (since all
`telephone numbers match entry D). For the table to operate
`correctly, however, it is necessary for the correct matching
`entry to be returned. The correct matching entry is the one
`at the lowest hierarchical level (i.e., the entry with the fewest
`X’s).
`For example, if the table is searched for the (908) 979-
`1035 telephone number, the matching entries are A, C and
`D. However, entry Ais the correct matching entry having the
`lowest hierarchical rank and thus allowing for the most
`specific action (i.e., placing the call within the central office).
`Current methods for translating hierarchical addresses are
`implemented in software and use tree structures, such as
`PATRICIA trees. PATRICIA trees are described on pages
`481-493 of “The Art of Computer Programming, Vol. 3:
`Searching and Sorting” by Donald E. Knuth (Reading,
`Mass.: Addison Wesley, 1973), which is herein incorporated
`by reference in its entirety. FIG. 2B illustrates a switching
`table 200 which uses a PATRICIA tree to route calls origi-
`nating in central ofiice Zone 145.
`Telephone numbers are compared with table entries in
`order from top to bottom looking for a matching entry. The
`telephone number is first compared to entry A. If the area
`code of the telephone number is “908,” subentries A.a, A.b
`and A.c are searched; otherwise the telephone number is
`compared to entry B, the long distance point-of-presence
`entry, which matches all telephone numbers.
`This approach, however, is limited by the constraints of a
`software implementation: processing speed is typically
`slower than in equivalent hardware implementations and
`comparisons with table entries are typically performed in a
`sequential order.
`Several techniques that utilize content addressable memo-
`ries (CAMS) for searching a routing table are discussed in
`“Fast Routing Table Lookup Using CAMS” by Anthony J.
`McAuley' and Paul Francis (1993 INFOCOM Proceedings)
`
`18
`
`18
`
`

`
`5,920,886
`
`3
`[hereinafter “the McAuley article”], which is herein incor-
`porated by reference in its entirety. Prior art techniques, such
`as those described in the McAuley article, are summarized
`in FIGS. 3A—3C.
`
`A content addressable memory (CAM) is a memory
`device that allows retrieval of information by specifying part
`of the stored information rather than by specifying a storage
`address. For example, if an entry “abed” were stored in a
`CAM, the CAM could be instructed to return the complete
`contents of all locations containing “ab”. CAMs are some-
`times referred to as associative memories.
`
`CAMs are generally classified as either binary or ternary
`CAMs. Binary CAMs store binary entries, while ternary
`CAMs store ternary entries. Binary entries are entries that
`contain only 0 or 1 values, while ternary entries are entries
`that contain 0, 1 or X (i.e., “don’t care”) values. Note that a
`single ternary entry can be expressed as two or more binary
`entries. In other words, a single ternary entry “1X0” can be
`represented by two binary entries “110” and “100”, or a
`single ternary entry “1XX” can be represented by four
`binary entries “100”, “101”, “110” and “111”, etc. As
`hierarchical addresses often comprise ternary values (e.g.
`“908-979-XXXX”), ternary CAMs require a smaller number
`of table entries to represent each hierarchical address than
`binary CAMS. However, ternary CAMS require more com-
`plex hardware and are generally more expensive than binary
`CAMs.
`
`CAMs may be implemented using a variety of techniques
`and technologies. One common technique is to search all
`CAM entries simultaneously in parallel to find the desired
`entry. Other techniques include hardware implementations
`of techniques commonly associated with software, such as
`hashing, serial search, binary search, and various search
`techniques based on a tree data structure. As these tech-
`niques are well known to those skilled in the art, they are not
`further discussed herein.
`
`The advantages of using CAMs for hierarchical address
`translation are higher performance and better price;’
`performance ratio than using existing techniques.
`A first prior art technique relies on the intrinsic priority
`encoding of entries stored in a CAM. Since the order in
`which entries are retrieved from a CAM can be predicted
`based on the location of the entries, address routing opera-
`tions can be implemented by first storing the addresses in the
`table into the CAM in a given order and then searching the
`table for the address, as shown in FIG. 3A. In FIG. 3A, the
`addresses are first stored in the CAM in reverse hierarchical
`
`order in stage 310. The CAM is then searched for the address
`in stage 320. Since the entries are returned in reverse
`hierarchical order, the first matching entry returned by the
`search is the one with the lowest hierarchical rank, which is
`also the correct matching entry.
`This technique, however, is not very useful in practice
`since it requires all the entries in the CAM to be sorted every
`time a new entry is added to preserve the inverse hierarchical
`ordering. To remedy this problem,
`the McAuley article
`proposes adding a priority field to table entries, as shown in
`FIG. 2C. FIG. 2C illustrates the table of FIG. 2A augmented
`by a priority field added to each entry. The priority field is
`used to represent the hierarchical order of the entries and
`allows the CAM to be searched in hierarchical order without
`
`requiring all entries to be re-sorted when a new entry is
`added to the CAM. For example, in FIG. 2C, entry D, which
`matches all telephone numbers, has the highest hierarchical
`level 1.
`
`While hierarchical addresses can be directly stored in
`ternary CAMs, in order to be stored in binary CAMs they
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`60
`
`65
`
`4
`must first be translated into binary format. As discussed
`above, a ternary address can be translated into two or more
`binary addresses. However, the number of binary addresses
`needed to represent a ternary address is 2”‘ where m is the
`number of don’t care digits in the ternary address. For
`example, ternary address “908-979-XXXX” would be trans-
`lated into 10,000 binary addresses, “908-979-0000” through
`“908-979-9999”. As the cost of CAMs is dependent on the
`number of entries they can store,
`the number of binary
`addresses needed to represent large hierarchical addresses
`renders this solution undesirable.
`
`the McAuley article proposes
`To solve this problem,
`translating a ternary hierarchical address into a binary
`address and a binary priority mask, as shown in FIG. 4A.
`The binary address has a 1 in the positions in which the
`ternary address has a 1, and Os in the other positions. The
`mask contains a 0 in the positions in which the ternary
`address has an X, and 1s in the other positions. As a result,
`each bit in the binary address, together with a corresponding
`bit in the priority mask, accurately indicates the value of a
`corresponding bit in the ternary entry, as shown in FIG. 4A.
`The binary addresses are stored in the CAM, while the
`binary masks indicate which bits of the stored addresses are
`compared to the search address during searches of the CAM.
`As only one binary address is generated for each ternary
`address, the size of the CAM is greatly reduced.
`In order for Values to be correctly stored in the binary
`CAM,
`ternary addresses must be translated into unique
`binary addresses. FIG. 4B, for example, shows two ternary
`entries that generate the same binary address, albeit with
`different masks. If more than one ternary value is translated
`into a single binary address stored in the CAM, only one set
`of data can be stored in the CAM (in the location of the
`binary address) and thus only one ternary address can be
`correctly translated. This problem is remedied by treating
`certain ternary Values as invalid to ensure that all ternary
`values are translated into unique binary addresses. For
`example, in IP v.4, 0 is not a legal value for the lowest level
`of the hierarchical address.
`
`Asecond prior art technique consists of searching a binary
`CAM for portions of an address specified by a priority mask,
`as shown in FIG. 3B. In FIG. 3B, a binary CAM is first
`searched for a binary address using a binary priority field at
`the lowest hierarchical level (i.e., the most specific hierar-
`chical
`level) in stage 340. Stage 345 then determines
`whether the search found any matching entries, in which
`case the first of the matching entries is retrieved in stage 355;
`otherwise the CAM is searched again for the same address
`and a priority field at the next higher hierarchical level. The
`first matching entry is the correct matching entry, as it has
`the lowest hierarchical level of any matching entry.
`This technique, however, requires in the worst case a
`search for each hierarchical level of the entries in the CAM.
`
`A third prior art technique, therefore, uses a ternary CAM
`in place of a binary CAM to reduce the number of searches
`of the CAM needed in the worst case to find a matching
`entry. A ternary CAM is a binary CAM that can handle
`“don’t care” values (represented by the symbol X) which
`match both 1 and 0 values. This technique is illustrated in
`FIG. 3C. Unlike with binary CAMs, ternary addresses are
`stored in the ternary CAM together with the corresponding
`binary priority fields representing the hierarchical level of
`the addresses. The ternary CAM is then searched with an
`address to be translated and a priority field in which all bits,
`except for the most significant bit, have a don’t care Value.
`After each search, a don’t care bit of the priority field is
`
`19
`
`19
`
`

`
`5,920,886
`
`5
`replaced by a 1 or a 0 (as explained below), until a binary
`priority field is obtained. An entry matching the address and
`the binary priority field is the correct matching entry.
`In FIG. 3C, the ternary CAM is first searched for an
`address and a priority field having a l in the most significant
`bit position and an X in all other bit positions, in stage 360.
`Stage 365 then determines if there are any matching entries,
`in which case the operation proceeds to stage 375; otherwise
`the least significant bit in the priority field having a value of
`1 is replaced by a value of 0. Stage 375 then determines
`whether any bits of the priority field have a value of X, in
`which case the most significant bit in the priority field
`having a value of X is replaced by a value of 1 in stage 380.
`The CAM is then searched for the address and the modified
`priority field, in stage 385. Stage 390 determines whether
`there is a single matching entry, in which case the matching
`entry is retrieved from the CAM in stage 395; otherwise
`stages 365-390 are repeated until the test of stage 390 is
`satisfied and the operation terminates. Thus, one X is
`resolved (i.e. replaced by a 1 or a 0) after each search until
`a matching entry is found.
`This technique requires in the worst case a number of
`searches equal to the number of bits used to represent the
`priority field (i.e., if N is the number of hierarchical levels
`represented by the priority field, log2N searches are required
`to find a matching entry at the lowest hierarchical level, as
`all bits of the priority mask must be resolved).
`There is thus a need for an improved method and appa-
`ratus for performing fast hierarchical address translation.
`SUMMARY
`
`The invention provides methods and apparata for per-
`forming hierarchical address translation using either binary
`or ternary CAMs which require a lower number of searches
`of the CAM than prior art techniques.
`In particular, a method and apparatus are provided for
`translating a ternary hierarchical address using a binary
`CAM that require in the worst case only log2N searches of
`the CAM, where N is the number of hierarchical levels of the
`hierarchical address, and only requires one entry to be stored
`in the CAM for each hierarchical address. Prior art tech-
`
`niques for translating hierarchical addresses using a binary
`CAM either require N searches of the CAM to be performed
`in the worst. case or multiple table entries to be stored in the
`CAM for each hierarchical address.
`
`This is achieved by translating each ternary hierarchical
`address into a binary address and a binary priority mask and
`storing the binary addresses in the binary CAM. A binary
`search of the priority masks is then performed by searching
`the CAM with a priority mask and choosing a next priority
`mask depending on the results of the search of the CAM
`until a correct matching entry (ie, the matching entry with
`the lowest hierarchical level) is found.
`Afurther method and apparatus are provided for perform-
`ing hierarchical address translation using a ternary CAM
`that require only a fixed number (2, or 1 when pipelined) of
`searches of the CAM, independent of the number of hier-
`archical addresses or of the number of hierarchical levels of
`the address. Prior art techniques for translating hierarchical
`addresses using ternary CAMs require in the worst case
`log2N searches of the CAM.
`This is achieved by storing a ternary address and a priority
`field representing a hierarchical level of the ternary address
`in a ternary CAM, searching the CAM for an address to be
`translated, comparing the priority fields of all addresses
`stored in the CAM that match the address to determine
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`60
`
`65
`
`6
`which matching entries have the highest hierarchical level,
`and searching the CAM for the address and the priority field
`having the lowest hierarchical level of all matching entries
`generated by the first search. Thus, the number of searches
`of the CAM required to translate an address is always 2 (1
`if the searches are pipelined) regardless of the number of
`addresses stored in the CAM or of the number of hierarchi-
`
`cal levels represented by the priority field.
`A method and apparatus are also provided for performing
`hierarchical address translation using a memory and a CAM
`that require only a single search of the memory once the
`address has been translated using the CAM. This is achieved
`by storing a hierarchical address translated using the CAM
`in the memory and using the memory to perform successive
`hierarchical address translations. Unlike prior art techniques
`that required multiple searches of the CAM, once the
`address has been translated, this technique only requires one
`search of the CAM for successive translations of that
`address.
`
`As a result, the number of searches required to translate
`a hierarchical address using either binary or ternary CAMs
`is reduced and the performance of hierarchical address
`translation operations is improved. This is particularly
`advantageous in applications where fast network routing is
`critical, such as the routing of data packets in network
`switches.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1A illustrates an example of a prior art flat address.
`FIG. 1B illustrates an example of a prior art hierarchical
`address.
`
`FIG. 2A illustrates a typical prior art routing table used to
`route calls originating in a calling area.
`FIG. 2B illustrates a switch which uses a PATRICIA tree
`to route calls originating in a central office zone.
`FIG. 2C illustrates the table of FIG. 2A augmented by a
`priority field added to each entry.
`FIG. 3A is a flow diagram of a prior art technique for
`translating hierarchical addresses using a CAM.
`FIG. 3B is a flow diagram of a di1'I”erent prior art technique
`for translating hierarchical addresses using a binary CAM.
`FIG. 3C is a flow diagram of yet another prior art
`technique for translating hierarchical addresses using a
`ternary CAM.
`FIG. 4A illustrates multiple prior art ternary entries of a
`switching table and their respective encoding as pairs of
`binary addresses and binary masks.
`FIG. 4B illustrates two ternary entries of a switching table
`that are encoded as a same binary address, but different
`binary masks.
`FIG. 5 is a flow diagram of a hierarchical address trans-
`lation operation using a binary CAM, according to one
`embodiment of the invention.
`
`FIG. 6A illustrates multiple entries of an IP routing table
`used in an hierarchical address translation operation, accord-
`ing to one embodiment of the invention.
`FIG. 6B shows the order in which the table entries of FIG.
`6A are stored in a CAM.
`
`FIGS. 6C—6F illustrate the results produced by successive
`searches of the CAM for various addresses during the
`hierarchical address translation operation of FIG. 5.
`FIG. 7 is a schematic diagram of a circuit for performing
`the hierarchical address translation operation of FIG. 5.
`FIG. 8 illustrates a plurality of ternary table entries
`augmented by an N-bit priority field, where N is the number
`
`20
`
`20
`
`

`
`5,920,886
`
`7
`of priority levels stored in the table, according to one
`embodiment of the invention.
`
`FIG. 9 is a flow diagram of an hierarchical address
`translation operation using a ternary CAM, according to one
`embodiment of the invention.
`
`l0A—l0B are schematic diagrams of a circuit
`FIGS.
`during the hierarchical address translation operation of FIG.
`9.
`
`FIG. 11 is a flow diagram of a hierarchical address
`translation operation using a cache CAM, according to one
`embodiment of the invention.
`
`FIG. 12 is a block diagram of a circuit during the
`hierarchical address translation operation of FIG. 11.
`FIG. 13 is a block diagram of an IP router circuit,
`according to one embodiment of the invention.
`FIG. 14 is a block diagram of a network firewall circuit,
`according to one embodiment of the invention.
`FIG. 15 is a block diagram of a network switch circuit,
`according to one embodiment of the invention.
`FIG. 16 illustrates an input port and a switch control
`processor element of the circuit of FIG. 15 in greater detail.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`According to the embodiments of the invention, a content
`addressable memory is used to improve the performance of
`hierarchical address translation systems.
`In one embodiment of the invention, ternary hierarchical
`address values are stored in a binary CAM by breaking the
`ternary address into two components: a binary address and
`a priority mask. The binary address has a 1 in the positions
`in which the ternary address has a 1, and 0s in the other
`positions. The mask contains a O in the positions in which
`the ternary address has an X, and 1s in the other positions.
`Some examples are shown in FIG. 4A.
`Note that only the binary address values are stored in the
`CAM, while the masks are stored in a separate mask list. The
`list of mask values, sorted in hierarchical order,
`is used
`during searches of the CAM to find a desired address. The
`CAM uses the one’s-complement of the address mask
`during searches. As discussed with reference to FIG. 4B,
`ternary addresses are translated into unique binary
`addresses.
`
`Some prior art techniques employ a similar scheme to
`store hierarchical addresses in a binary CAM and to search
`the CAM for table entries matching an address using dif-
`ferent priority masks. These methods, however, require, in
`the worst case, that the binary CAM be searched once for
`each priority mask in the list. By contrast, one embodiment
`of the invention provides a method of translating hierarchi-
`cal addresses using a binary CAM that only requires log2N
`searches of the CAM, where N is the number of hierarchical
`levels of the address.
`
`This is accomplished by first ordering priority masks so
`that a mask with m trailing zeros is used in a search before
`a mask with n trailing zeros, where m<n. In addition, rather
`than searching for all priority masks in the mask list
`sequentially, as taught by the prior art, one embodiment of
`the present
`invention searches the CAM using a binary
`search technique, as shown in FIG. 5. Unlike in prior art
`techniques, in which priority masks are used in reverse
`hierarchical order so that the first matching entry is the
`correct matching entry, using a binary search the first
`matching entry may not be the correct matching entry. This
`is because the priority masks are not used in hierarchical
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`60
`
`65
`
`8
`order, but rather according to the their position in a binary
`search tree. As a result, if a search of the CAM produces
`multiple matching entries,
`the search is repeated with a
`priority mask with a higher hierarchical level until a single
`matching entry (or no matching entry, in which case the
`correct matching entry is the first matching e