United States Patent (19)
`L0Schke et al.
`
`54
`
`(75)
`
`APPARATUS AND METHOD FOR
`CONCURRENT SEARCH CONTENT
`ADDRESSABLE MEMORY CIRCUIT
`Inventors: Jon Ashor Loschke; Charley Michael
`Parks; Mark Franklin; Kenneth
`Wade Jones, all of Austin, TeX.
`Assignee: Motorola, Inc., Schaumburg, Ill.
`
`Appl. No.: 08/722,587
`Filed:
`Sep. 27, 1996
`6
`Int. Cl. ..................................................... H04L 12/28
`U.S. Cl. ........................... 370/392; 370/395; 370/429
`Field of Search ..................................... 370/399, 382,
`370/383,392,393, 395,397, 409, 416,
`429; 365/49, 190, 189.12, 230.02; 395/200,
`200.2, 200.21
`
`56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`USOO5956336A
`Patent Number:
`11
`(45) Date of Patent:
`
`5,956,336
`Sep. 21, 1999
`
`5,467,349 11/1995 Huey et al. ............................ 370/60.1
`5,684,954 11/1997 Kaiserswerth et al. .............. 395/2002
`Primary Examiner Ajit Patel
`ASSistant Examiner-Chiho Andrew Lee
`Attorney, Agent, or Firm-Lee E. Chastain
`57
`ABSTRACT
`A circuit and method is provided for implementing a COntent
`addressable memory circuit (100) in which an output word
`is produced which corresponds to the content of a reference
`word containing an ATM header. According to a first aspect,
`a binary search logic circuit (104) binarily searches the
`memory array (101) to find a match word whose content is
`equal to that of the reference word. Output signals indicate
`either that a match has been found or that the binary
`Searching of the memory array (101) should continue at
`addresses either above or below the location address of the
`match word. According to a Second aspect, the content
`addressable memory circuit (100) performs a concurrent
`Search of Switching identifiers, Virtual circuit identifiers and
`Virtual path identifiers, to determine if a virtual path con
`t or virtual circuit connection exists for an ATM
`
`5,414,707 5/1995 Johnston et al. .......................... 370/79
`5,422,838 6/1995 Lin ............................................ 365/49
`
`12 Claims, 8 Drawing Sheets
`
`
`
`TABLE
`UPDATE
`
`104
`
`
`
`INPUT
`
`
`
`COMPARATOR
`
`
`
`
`
`2 EQUAL /
`VCCMATCH II
`VPCMATCH /
`
`
`
`BINARY
`SEARCH
`CIRCUIT
`
`
`
`
`
`
`
`
`
`
`
`VPCVALID
`
`
`
`OUTPUT
`
`
`
`
`
`120
`
`OUTPUT
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 1 of 16
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 1 of 8
`
`5,956,336
`
`TABLE
`UPDATE
`
`
`
`- - - -
`122
`
`-
`
`- - -
`
`105
`
`INPUT
`
`COMPARAT
`OR
`
`2
`
`104
`
`
`
`A
`EQUAL / ENSE
`vcCMATCH / SEAR
`WPCMATCH
`
`
`
`
`
`
`
`VPCVALID
`
`OUTPUT
`
`
`
`120
`
`100
`
`OUTPUT
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 2 of 16
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 2 of 8
`
`5,956,336
`
`
`
`
`
`
`
`
`
`
`
`SELECT MIDPOINT MATCH - 202
`WORD AND LINK WORD
`FROM MEMORY ARRAY
`
`RECEIVE
`REFERENCE
`WORD
`
`COMPARE SELECTED
`MATCH WORD WITH
`REFERENCE WORD
`
`SELECT NEW MATCH
`WORD AND LINK WORD
`AT MIDPOINT OF
`UNTESTED MEMORY
`
`
`
`
`
`
`
`SELECTED
`MATCH WORD EQUALS
`REFERENCE WORD
`
`206
`
`ENTIRE MEMORY
`ALREADY TESTED
`YES
`
`
`
`302
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 3 of 16
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 3 of 8
`
`5,956,336
`
`
`
`PHYSICAL
`CHANNEL
`
`ATM
`SWITCH
`507
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 4 of 16
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 4 of 8
`
`5,956,336
`
`600
`LOADING VCI AND VPI TABLE
`INTO CAM
`
`602
`RELOADING VCI AND VPI FROM
`ATM CELL, HEADER 10
`
`603
`COMPARING VPI AND VCI OF ATM
`CELL, HEADER 10 WITH VPI AND
`VCI ENTRY N MATCH WORD
`
`
`
`604
`WPI
`AND VC: MATCH
`
`
`
`
`
`
`
`
`
`COMPARING VPI OF ATM
`CELL, HEADER 10 WITH
`WPI IN ENTRY IN CAM AND
`CHECK FOR SPECIAL VPC BIT
`
`
`
`605
`VIRTUAL CIRCUIT
`CONNECTION = 1
`
`
`
`FALSE
`
`WPI
`AND VPC BIT
`MATCH2
`
`END OF SEARCH
`
`VIRTUAL PATH
`CONNECTION = 1
`
`END
`
`600
`A77G. 6
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 5 of 16
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 5 of 8
`
`5,956,336
`
`START
`
`701
`
`INTO CAM 101
`
`
`
`702
`READING VCI AND WPI FROM
`ATM CELL, HEADER 302
`
`1-COMPARE WPI OF ATM CELL, HEADER 302
`WITH VPI FROM MATCH WORD
`2-COMPARE VCI OF ATM CELL, HEADER 302
`WITH WPI FROM MATCH WORD
`3-CHECK FOR SPECIAL VCI VALUE
`
`
`
`
`
`
`
`
`
`
`
`705
`
`COMPARE
`1 AND 2
`VALID?
`
`COMPARE
`1 AND 5
`VALID?
`
`708
`
`NO MATCH
`
`
`
`706
`A VIRTUAL CIRCUIT
`CONNECTION, WCC = 1
`
`
`
`A VIRTUAL PATH
`CONNECTION, WPC = 1
`
`
`
`Af7G. Z
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 6 of 16
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 6 of 8
`
`5,956,336
`
`
`
`
`
`VPI
`
`
`
`COMPARATOR
`
`EQUAL1
`
`108
`
`105
`A77G.S
`
`VCIM(0)
`VCIM(1)
`VCIM(2)
`VCIM(3)
`VCIM(4)
`VCIM(5)
`VCIM(6)
`VCIM(7)
`VCIM(8)
`VCIM(9)
`WCIM(10)
`VCIM(11)
`VCIM(12)
`VCIM(13)
`VCIM(14)
`VCIM(15)
`
`112
`
`114
`
`116
`
`118
`
`EQUAL3
`
`D.
`
`120
`
`108
`A/VG.9
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 7 of 16
`
`

`

`US. Patent
`
`Sep. 21, 1999
`
`Sheet 7 0f 8
`
`5,956,336
`
`f--------------
`
`¢4m>MS
`
`n4m>MS
`
`um<mzoo
`
`mm<mzoo
`
`«Illfilllllllill
`l'l'l'll1"
`
`mm<mzoo
`
`N4m>MA
`
`mm<¢zoo
`
`_4m>mS
`
`QNNUNBN
`
`mm<¢zoo
`
`_MS=ooz
`
`mm<¢zoo
`
`OMSDQOE
`
`«.238
`
`Nmm._.<mmo
`
`mm<mzoo
`
`mm<¢zoo
`
`nMSsooz
`
`mm<mzoo
`
`NMADQOE
`
`mm<mzoo
`
`_mA=ooz
`
`mm<mzoo
`
`omgaooz
`
`mm<mzoo
`
`NMADQOE
`
`mm<mzoo
`
`¢MAzooz
`
`mm<mzoo
`
`mMSzaoz
`
`um<mzoo
`
`OMADQOE
`
`m_MJ=ooz
`
`mm<mzoo
`
`wMAzoo:
`
`mm<mzoo
`
`“”4300:
`
`mx<mzoo
`
`OMAsooz
`
`CISCO SYSTEMS, INC. / Page 8 of 16
`
`EX.1015
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 8 of 16
`
`
`

`

`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 8 of 8
`
`5,956,336
`
`
`
`80 (b–
`o a (b–
`
`['0IJA
`JO (H0IOA
`
`[W0IJA
`JO ?MOIOA
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 9 of 16
`
`

`

`5,956,336
`
`1
`APPARATUS AND METHOD FOR
`CONCURRENT SEARCH CONTENT
`ADDRESSABLE MEMORY CIRCUIT
`
`2
`example, Setting an error flag bit. In an ATM application, the
`reference word consists of Switching identifiers. The Switch
`ing identifiers consist of a virtual path identifier (“VPI”,
`hereafter) and a virtual channel identifier (“VCI”, hereafter).
`The CAM compares the VPI and VCI in the header with the
`VPI and VCI entries in the CAM. The switching identifiers
`determine if a virtual path connection (“VPC”, hereafter)
`exists or a virtual circuit connection (“VCC”, hereafter)
`exists.
`Smaller sized CAMs often provide this function in hard
`ware Such that the reference word is simultaneously com
`pared with every word in the match word table, thereby
`operating in a full parallel mode in which the output word is
`produced in one clock cycle. However, as the need for larger
`CAMS grows, the parallel mode is not possible due to longer
`Search times.
`A previously known technique for implementing a large
`CAM is to presort the memory into distinct classes. For
`example, a 4,096 word deep CAM is preclassified into four
`separate, shallower 1,024 word CAMs wherein particular
`match and link word pairs could only be Stored in one of the
`CAMS. However, this approach has a disadvantage in that
`the CAM corresponding to one of the classes could be filled
`while others had substantial vacancies, thereby effectively
`reducing the depth of the CAM. Adding logic to the CAM
`for dynamically adjusting the size of each CAM as needed
`would Substantially increase the complexity and cost of the
`CAM.
`Furthermore, in order to establish a VCC or VPC, two
`Searches to each CAM entry are required, whether a parallel
`or Serial Search Strategy is used. The first Search checks for
`a VCC, comparing the input header and the Switching
`identifiers. The second search is for the VPC, comparing the
`input header and the Switching identifiers.
`Two known approaches are used to perform parallel
`Searches. One method uses one CAM array, interrogating
`each entry twice. Another method uses two Separate CAMs,
`with each CAM only storing either VCI or VPI. The one
`CAM approach will take more time than the dual CAM
`approach. However, the dual CAM approach adds more
`hardware and cost to a Switch network.
`
`15
`
`25
`
`35
`
`40
`
`FIELD OF THE INVENTION
`The present invention generally relates to digital elec
`tronic devices, and more Specifically to devices used to
`manage header information in a Switching network.
`BACKGROUND OF THE INVENTION
`Communication and computer networks consist of a vari
`ety of hardware equipment and Software and are increasing
`in use and complexity. The popularity of computer networks
`as a computer paradigm and the growth in amount of data
`transferred between network users has forced the capacity of
`networks and protocols to increase with time. A variety of
`network communication protocols transfer data between
`devices coupled by a network. Ethernet and ASynchronous
`Transfer Mode are examples of Such communication proto
`cols.
`Asynchronous Transfer Mode ("ATM", hereafter) pro
`vides bandwidths as low as 25 megabits/second using
`twisted cables and as high as 10 gigabits/second using
`optical cables. An ATM Switch transfers cells between
`various points in a network. A cell contains control
`information, a header, and a data packet. The header within
`the cell contains switching identifiers enabling the ATM
`Switch to route the data. The ATM Switch interrogates each
`Switching identifier it receives against a programmed list to
`determine which output channel the cell should be output.
`When the data packets are received by the intermediate
`node, destination information is contained in header which
`accompanies the data packet. The node determines whether
`it has previously agreed to route the data packets for that
`transmission by examining its memory to determine whether
`the destination information has previously been stored. If it
`has, a forwarding address has also been Stored and the node
`forwards the data packet to the next node in the route toward
`the destination address. AS it receives each data
`transmission, the node interrogates the contents of its
`memory to determine if it has agreed to forward the trans
`mission. If the destination information is present, the
`memory produces a forwarding address associated with the
`destination information for routing the data packet to the
`next node.
`Content addressable memories ("CAM", hereafter) store
`the Switching identifiers for the ATM Switch. In an associa
`tive or content addressable memory, match words and
`Switching identifiers are Stored in associated pairs in
`memory. When the CAM receives a reference word it
`determines whether a match word equal to the reference
`word is Stored in memory. If So, it produces the link word
`asSociated with the matched reference word. An important
`aspect of a CAM is the association between the match word
`and its associated link word, much like a dictionary, where
`each word is Stored in association with its definition. In a
`dictionary, a provided word is looked up and the definition
`associated with the word is produced. In a CAM, a provided
`reference word is looked up, i.e., compared with a match
`word and, if they are equal, a link word associated with the
`match word is produced.
`In general, the memory array of an ATM CAM is orga
`nized into a match word table and a link word table. If a
`reference word matches an entry from a match word table
`the associated link word is produced at the output. If no
`match is found, the output word indicates the failure by, for
`
`45
`
`50
`
`55
`
`60
`
`65
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 depicts a block diagram of a content addressable
`memory circuit implemented in accordance to the present
`invention;
`FIG. 2 depicts a flow diagram of a method for imple
`menting a content addressable memory circuit in accordance
`with the present invention;
`FIG.3 depicts an asynchronous transfer mode (ATM) cell
`header in accordance with the present invention;
`FIG. 4 depicts a physical channel containing virtual
`circuit identifiers and virtual path identifiers in accordance
`with the present invention;
`FIG. 5 depicts an ATM Switch containing virtual circuit
`connections and virtual path connections in accordance with
`the present invention;
`FIG. 6 depicts, in flow chart form, a known method of an
`ATM cell header search;
`FIG. 7 depicts, in flow chart form, an ATM cell header
`Search in accordance with the present invention;
`FIG. 8 depicts a block diagram of a comparator in
`accordance with the present invention;
`FIG. 9 depicts a circuit schematic of a comparator illus
`trated in FIG. 8:
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 10 of 16
`
`

`

`5,956,336
`
`15
`
`35
`
`40
`
`25
`
`3
`FIG. 10 depicts a detailed block diagram of the compara
`tor illustrated in FIG. 8; and
`FIG. 11 depicts a circuit Schematic of a two bit compara
`tor illustrated in FIG. 10.
`DETAILED DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram of a content addressable
`memory (CAM) circuit 100 as used in a network data
`routing circuit in accordance with the present invention.
`CAM 100 stores data in and accesses data for comparison
`according to a novel method. This Scheme reduces acceSS
`time without artificially excluding header information from
`portions of CAM 100. CAM 100 is thereby both fast and
`efficient in its use of memory. Furthermore, each individual
`comparison for a VCC or a VPC match is accelerated
`according to a Second aspect of the disclosed invention.
`Continuing with FIG. 1, the CAM 100 comprises an array
`of memory words 101, a comparator circuit 105, a binary
`search logic circuit 104, and an entry queue 106. CAM 100
`has an output at terminal 120 for providing an output word
`based on the content of a reference word. AS used herein, the
`term “terminal” refers to a single electrical conduction line
`and also includes bus lines comprising multiple electrical
`conduction lines. The CAM 100 has an input at terminal 121
`for receiving a destination header Signal or other transmitted
`data from the network. The reference word is transmitted as
`part of the destination header Signal.
`The array of memory words 101 comprises a core of static
`RAM cells and is configured as a match word table 102 and
`a link word table 103 Such that at each location address the
`Stored memory word is made up of a match word and an
`associated link word. In one embodiment each static RAM
`cell is comprised of four transistors and has an access time
`of five nanoSeconds. Depending on the application, the array
`of memory words 101 can alternatively be comprised of
`dynamic RAMs or flash memory. An input at terminal 124
`receives the location address Signal which Selects a memory
`word from the array, and first and Second outputs at termi
`nals 122 and 123 respectively provide the selected match
`word and link word.
`The comparator circuit 105 has first and second inputs at
`terminals 121 and 122 for respectively receiving the refer
`ence word and the Selected match word, and an output at
`terminal 125 for providing five output signals, a GREATER
`signal, an EQUAL signal, a VCCMATCH signal, a VPC
`45
`MATCH signal, and a VPCVALID signal. Comparator cir
`cuit 105 compares the contents of the reference word and the
`Selected match word and asserts the output signal corre
`sponding to the logical result of the comparison. For
`instance, if the input reference word is greater than the
`selected match word, then comparator 105 asserts the
`GREATER signal. The VCCMATCH and VPCMATCH are
`asserted for a VCC and VPC match, respectively. If a VPC
`match exists, then comparator 105 asserts the VPCVALID
`signal. Comparator 105 and the GREATER signal, the
`55
`EQUAL signal, the VCCMATCH signal, the VPCMATCH
`signal, and the VPCVALID signal are discussed below in
`connection with FIG. 8 and FIG. 10.
`The entry queue 106 receives reference words for table
`updates. Reference words to be added to or deleted from
`CAM 100 are buffered. In Some embodiments, the buffered
`entries in entry queue 106 may be Searched linearly prior to
`Searching the match word table. The method of Searching the
`match word table is described immediately below. In yet
`another embodiment, the entry queue 106 is removed and
`the reference words are sorted as Soon as the CAM 100 is
`available.
`
`50
`
`60
`
`65
`
`4
`The binary search logic circuit 104 performs a binary
`search of the match word table 102 to determine whether an
`entry in the match word table 102 has the same content as
`the reference word. Abinary Search requires that the table to
`be searched be sorted into a predetermined order. Therefore,
`at System Startup, and prior to accepting a reference word,
`the array of memory words 101 is sorted into a predeter
`mined order based on the entries in match word table 102.
`In the depicted embodiment, the reference word-link word
`pair having the Smallest reference word is Stored in the first
`entry of array of memory words 101, the reference word
`having the Second Smallest reference word is Stored in the
`Second entry of the array of memory words, etc.
`In theory, the match word table can be Sorted into any
`predetermined order. However, the order must be discernible
`by the comparator circuit 105 such that when it compares a
`given reference word with a Selected match word it can
`determine whether a matching match word, if it is to be
`found in the match word table 102, has a higher or lower
`address than the Selected match word.
`FIG. 2 is a flow diagram of the CAM implementation of
`the binary Search algorithm used by the binary Search logic
`circuit 104 to binarily search the array of memory words 101
`to determine if a match word is stored which matches the
`reference word. It is assumed that the match table has
`previously been Sorted from, for example, low to high in
`order of increasing location addresses. At Step 201 the
`reference word is received from, for example, a network bus.
`At Step 202, a location address corresponding to the mid
`point of the memory array is provided for Selecting a match
`word and an associated link word from the array. Step 203
`compares the Selected match word to the reference word. If
`they are equal, (step 204), then the selected link word is
`provided at the output of the CAM at step 205 and the binary
`Search ends.
`If the Selected match word is not equal to the reference
`word, (step 204), then the binary Search logic circuit deter
`mines at step 206 whether the entire array has already been
`compared with the reference word. If the entire array of
`memory words 101 has not already been tested, then a new
`location address is provided which corresponds to the mid
`point of the half of the memory array in which a match word
`which matches the reference word can possibly be found. It
`is a characteristic of this binary Search method that after each
`comparison according to steps 203 and 204 one-half of the
`memory is eliminated from possibly containing a matching
`match word because of the previous Sorting of the memory
`array into a predetermined order. Therefore, each cycle of
`the binary Search progressively reduces by one-half the
`untested portion of the memory array.
`If step 206 determines that the entire memory array has
`been tested with no matching match word found, then an
`error flag is set at the output at step 207 and the binary search
`terminates. If a portion of the memory array remains to be
`tested (Step 206), however, a new location address is pro
`vided at step 208 which corresponds to the midpoint of the
`untested portion of the memory array. The new location
`address selects new match and link words at step 202 and the
`cycle repeats until the binary Search terminates.
`Returning to FIG. 1, the binary search logic circuit 104
`has a first output at terminal 124 for providing a location
`address Signal to the array of memory words. At any cycle
`of the binary Search, the location address is chosen to be at
`essentially the midpoint of the untested portion of the array
`of memory words 101. If there are an even number of entries
`in the match word table, as is generally the case, there is no
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 11 of 16
`
`

`

`5,956,336
`
`15
`
`25
`
`35
`
`40
`
`S
`exact midpoint location address, So that the next higher or
`lower location address is chosen, i.e., the lowest address in
`the upper half of the array.
`When this location address signal is received by the array
`of memory words 101 a selected match word and a selected
`link word are respectively produced at the first and Second
`outputs at terminals 122 and 123. The selected match word
`is compared with the reference word in comparator circuit
`105, which produces an output Signal corresponding to the
`result of the comparison. The output Signal indicates one of
`Six results of the comparison: first, the reference word and
`match word are equal; Second, continue Searching at higher
`location addresses; and third, continue Searching at lower
`location addresses; and fourth, end searching if a VPC
`occurs, and fifth, end Searching if a VCC occurs, and Sixth,
`the comparator 105 asserts the VPCVALID signal which
`propagates to a output logic pin.
`The binary search logic circuit 104 has a first input at
`terminal 125 which receives the output signal from the
`comparator circuit 105. A second input at terminal 123
`receives from the link word table 103 the selected link word
`which is associated with the selected match word. If the
`contents of the reference and Selected match words are
`equal, the binary Search logic circuit 104 produces the
`selected link word at its output at terminal 120, which is
`coupled to the output of the CAM 100. The output of the
`CAM 100 therefore includes the selected link word, possibly
`adding a flag bit to indicate that the match was Successful.
`Other information can be provided at the output of the CAM
`100 including but not limited to number of searches, the
`amount of time of the Search, and Successful hit percentage
`within the CAM.
`If the reference and Selected match words do not match,
`then the output signal from the comparator circuit 105
`indicates whether a matching match word, if it is Stored in
`the match word table 102, is located above or below the
`midpoint location address. If, for example, the comparator
`circuit 105 indicates that the search should continue in the
`half of the match word table 102 above the previous mid
`point location address, then the binary Search logic circuit
`104 provides a new location address at the midpoint of the
`region of the match word table immediately above the
`region just tested. A new match word corresponding to the
`new midpoint location address is compared to the reference
`word and the cycle repeats itself.
`In a binary Search, each comparison of the reference word
`to a new match word either produces a match or eliminates
`one-half of the match word table 102 as a possible location
`address where a match can be found. Successive cycles
`effectively treat the remaining portion of the match word
`table 102 as if it were a new table, sending a new location
`address corresponding to the midpoint of the remaining
`portion of the array of memory words 101.
`The time needed for completing each cycle of the binary
`Search is generally determined by the Speed of the Static
`RAM core which comprises the array of memory words 101.
`In an embodiment in which the array of memory words 101
`is 4,096 memory entries deep, the time needed for complet
`ing each cycle is ten nanoSeconds. Twelve Successive bisec
`tions are needed for reducing the 4,096 memory words to
`one memory word, the array of memory words 101 can be
`binarily Searched in at most twelve cycles. A complete
`Search is therefore completed in 120 nanoSeconds. For an
`array of memory words 101 with a capacity of 16,384
`memory words, two additional binary Search cycles must be
`provided for, So the Search is completed in 140 nanoSeconds.
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`It is possible for the binary search to be completed with
`no match word found that matches the reference word. In
`that case, no link word is provided at the output of the CAM
`100, and an error flag bit indicating that no match was found
`or that the Search is completed is generally provided.
`In Some applications it is necessary to update the match
`word table 102 and link word table 103 to include new
`entries or to delete entries which are no longer useful. For
`that reason, the binary search logic circuit 104 has a third
`input connected to terminal 121 for receiving the new
`entries. If the array of memory words 101 is full and no
`existing entries can be deleted, the new entry is not pro
`cessed any further, and an error bit is Set in the output word
`to indicate that the new entry is not accepted.
`If the array of memory words 101 has a vacant location a
`new entry is accepted and inserted. Recall that the new entry
`must be inserted So as to preserve the predetermined order
`of the array of memory words 101. In one embodiment, the
`binary Search logic circuit 104 begins at the vacant location,
`say the top of the array of memory words 101, and examines
`the stored memory word in light of the new entry and the
`need to maintain the predetermined order of the array of
`memory words 101. The new entry is inserted in the vacant
`location if doing So maintains the predetermined order. The
`binary Search logic circuit 104 determines the proper loca
`tion of the new entry.
`If the CAM 100 is otherwise idle during the insertion
`process, an array of memory words 101 which is 4,096
`words deep requires an average of about twenty
`microSeconds, with a worst case of about forty
`microSeconds, to insert the new entry at the correct location.
`FIG. 3 depicts an asynchronous transfer model (ATM)
`cell 300 in accordance with the present invention. The ATM
`cell contains a header 302 which itself contains routing
`information for Switching networks. The header 302 infor
`mation is input to comparator 105 in FIG. 1 via terminal 121.
`The Switching identifiers route the data packet based on VCI
`and VPI contained in the header 302. Byte 1 contains 4 bits
`for a generic flow control(“GFC”, hereafter) and contains 4
`bits for the VPI in a user network interface (“UNI”,
`hereafter) protocol. However, in a network network inter
`face (“NNI”, hereafter) protocol, Byte 1 contains 8 bits for
`the VPI. Byte 2 contains 4 bits for the VPI and contains 4
`bits for the VCI. Byte 3 contains 8 bits for the VCI. Byte 4
`contains 4 bits for the VCI and 4 bits for the payload type
`identifier(“PTI”, hereafter), for both UNI and NNI proto
`cols. The remaining bytes contain the data packet. The data
`packet(“data”, hereafter) could consist of computer code,
`telephone communication, or any information to be routed.
`FIG. 4 depicts a physical channel 400 containing VCI and
`VPI in accordance with the present invention. The physical
`channel 400 represents a physical data transmission Struc
`ture Such as optical cables, twisted cables, and phone cables.
`The physical channel 400 contains VPCs and VCCs,
`wherein the VPCs and VCCS contain individual VPI and
`VCI. A VPC can be conceptualized as a trunk of multiple
`circuits, all with the same VPI and all being Switched in the
`same manner. A VCC is one specific VCI within a VPI
`routing to a different VCI within a different VPI. Routing for
`VCC and VPC is discussed below in FIG. 5. In this
`embodiment, up to 4,096 VPI are possible and up to 65,536
`VCI per VPI are possible.
`FIG. 5 depicts an ATM switch 507 containing VCC and
`VPC in accordance with the present invention. The ATM
`Switch 507 receives multiple input paths and generates
`multiple output paths with a variety of data. The ATM Switch
`
`Ex.1015
`CISCO SYSTEMS, INC. / Page 12 of 16
`
`

`

`5,956,336
`
`15
`
`35
`
`40
`
`25
`
`7
`507 handles data within the input and output paths and
`routing of paths occurs instantaneously (on the fly). The
`ATM Switch 507 illustrates a Switching network with a
`plurality of physical channels 400. In one example, the ATM
`Switch 507 receives a physical channel 501, a physical
`channel 502, and a physical channel 503. The ATM switch
`507 routes the input cells, VCI and VPI, based on the
`individual header 302, to a physical channel 504, a physical
`channel 505, and a physical channel 506.
`The CAM 100 compares the VPI and VCI in the header
`302 with the VPI and VCI entries in the CAM 100. A VPC
`exists if a match occurs for the VPI and a special VCI value
`in the CAM 100 identifying a VPC. The match data tells the
`ATM Switch 507 where to route the data and how to translate
`all or a portion of the data in the header 302.
`In one example, the physical channel 501 contains a VPI
`value of 5 with a VCI value of 1, a VCI value of 2, and a VCI
`value of 3. The CAM 100 searches the match word table 102
`and a match occurs for the VPI and VCI values above with
`a special VCI value identifying a VPC. The link word
`asSociated with the match word contains a translate value for
`the VPI of 7. The ATM switch 507 routes physical channel
`501 to the physical channel 504 and translates the VPI value
`from 5 to 7; however, the VCI retain the values of 1, 2, and
`3. Therefore, for a VPC, the VPI value is translated but the
`VCI value remains the same.
`In another example, the physical channel 502 contains a
`VPI value of 1 with a VCI value of 1, a VCI value of 2, and
`a VCI value of 3, in the header 302. The CAM 100 searches
`the match word table 102 and a match occurs for both the
`VPI and VCI values, resulting in a VCC. The link word
`asSociated with the match word contains a translate value for
`VPI of 5 and a translate value for VCI of 12, 13, and 14, for
`the VCI values of 1, 2, and 3, respectively. The ATM Switch
`507 routes the physical channel 502 to the physical channel
`506 and translates the VPI value from 1 to 5, and translates
`the VCI values from 1, 2 and 3 to 12, 13, and 14 respectively.
`Therefore, for the VCC, both the VPI value and the VCI
`value are translated.
`FIG. 6 depicts, in flow chart form, a known method of the
`header 302 search. A predetermined set of VPI and VCI
`values are loaded into the CAM 100 to route the data in the
`header 302, a step 601. The first search begins by reading the
`VCI and VPI values from the header 302, a step 602. The
`first search is for a VCC by comparing the VPI and VCI
`values in the header 302 with the VPI and VCI values in the
`match word table 102, a step 603. A decision is made
`whether the VPI and VCI values match, a step 604. If the
`decision is true (a match), the VCC is valid, a step 605. The
`VPI and VCI values are translated to the values defmed in
`the associated link word. However, if the decision is false
`(no match), compare the VPI value in the header 302 with
`the VPI value in the match word table 102 and check for a
`special VPC bit in the match table 102, a step 606. A
`55
`decision is made whether the VPI values match and if the
`special VPC bit exists in the match word table 102, a step
`607. If the decision is true, the VPC is valid, a step 608. The
`VPI value is translated to the value defined in the associated
`link word. However, if the decision is false (no match), then
`the search ends without a match. One skilled in the art will
`readily appreciate that this known algorithm requires two
`separate CAM look-ups: one CAM is used twice or two
`CAMS are used once each. In either case, time or Silicon is
`used excessively.
`FIG. 7 depicts, in flow chart form, a header 302 search in
`accordance with the present invention. A predetermined Set
`
`45
`
`50
`
`60
`
`65
`
`8
`of VPI and VCI values are loaded into the CAM 100 to route
`the data in the header 302, a step 701. In the depicted
`embodiment, the VCI and VPI values are sorted and stored
`in increasing number, as described above in FIG. 1.
`However, both aspects of the disclosed invention may be
`practiced independent of each other or can be combined.
`Both searches begin with reading the VCI and VPI values
`from the header 302, a step 702. A step 703 consists of three
`comparisons: the first comparison consists of comparing the
`VPI from the header 302 with the VPI from the match word
`table 102, the Second comparison consists of comparing the
`VCI from the header 302 with the VCI from the match word
`table 102, the third comparison consists of comparing the
`VCI from the match word table 102 for a special VCI value
`of logic ones. The following steps, 704 and 705, are per
`formed simultaneously, though depicted as occurring Seri
`ally. A decision is made whether the first comparison (VPI
`from header 302 is equal to VPI from match word) and the
`second comparison (VCI from header 302 is equal to VCI
`from match word) are true (a match), a step 704. If the
`decision is true(a match), the VCC is valid in step 706 and
`the VPI and VCI values are translated to the values in the
`asSociated link word. However, if the decision is false, then
`the VCC search ends without a match. The VPC search
`compares the VPI value of the