`
`0’
`
`Européiisches Patentamt
`European Patent Office
`Office européen des brevets
`
`Hm"
`
`
`
`
`
`
`
`
`
`@ Publication number: 0 522 743 A1
`
`@
`
`EUROPEAN PATENT APPLICATION
`
`@ Application number: 92305770.7
`
`@ Int. 01.5: H04L 29/06, H04L 12/46
`
`Q2) Date of filing : 24.06.92
`
`Priority: 26.06.91 us 721166
`
`Date of publication of application :
`13.01.93 Bulletin 93/02
`
`Designated Contracting States:
`DE FR GB |T
`
`@ Applicant: DIGITAL EQUIPMENT
`CORPORATION
`146 Main Street
`Maynard, MA 01754 (US)
`
`@ inventor: Jain, Rajendra Kumar
`137 Dutton Road
`Sudbury, Massachusetts 01776 (US)
`Inventor: Yang, Henry S.
`11 Dascomb Road
`Andover, Massachusetts 01810 (US)
`Inventor: Hawe, William R.
`16 Independence Road
`Pepperell, Massachusetts 01463 (US)
`
`Representative : Oliver, Peter Anthony
`BEACHCROFT STANLEYS 20 Furnival Street
`London EC4A 1BN (GB)
`
`
`
`Combined hash table and CAM address recognition in a network.
`
`@ Method and apparatus for comparing a first
`value to a second value to determine if the first
`value equals the second value. Preferably,
`the
`first value is
`represented by (n) address bite
`received from a communication network. An
`address filter (10)
`includes circuitry for storing
`the received address and for applying all or a
`portion of the stored address to a CAM (12)
`containing entries storing one or more target
`addresses. The address fitter also includes a
`Hash fitter (14) for filtering the first value for
`determining if the first value is recognized by a
`Hash mask (16). For example, the received ad-
`dress is first applied to a CRC generator (22, 28)
`and a pluratity of the CRC bits,
`for example
`nine, are used to access the Hash mask. The
`address
`fitter
`further
`includes programmable
`control circuitry (U1, U2, U3) for indicating that
`the received address equals the target address
`if (a) the CAM has an entry that equals all or a
`portion of the received address and/or if (b) the
`CRC of the received address is recognized by
`the Hash fitter. The address filter also includes
`circuitry (28) for correcting the hash function,
`if
`required, for bits that arrive before the (n) ad-
`dress bits.
`
`EP0522743A1
`
`stream
`
`;
`(44
`1
`
`.
`F 2
`5‘8
`
`
`°‘°°"_’
`Zguirir‘er
`4M
`“$56
`
`
`gtfagm 1.. ........... ..2.9?‘Aadie’s's‘i'2'e'gi‘stéi':.._..'
`'
`23bi|sof
`lbitsof
`
`
`
`
`
`
`
`-
`
`m;
`
`21.
`
`15
`
`DccisionI
`LOGIC :
`
`Address
`Mmhofliput
`
`Jouve, 18, rue Saint-Denis, 75001 PARIS
`
`UNIFIED 1003
`
`UNIFIED 1003
`
`

`

`EP 0 522 743 A1
`
`FIELD OF THE INVENTION:
`
`This invention relates generally to data communication apparatus and method and, in particular, to appa-
`ratus and method enabling a local area network (LAN) station to efficiently recognize a received LAN address.
`
`BACKGROUND OF THE INVENTION:
`
`The subject matter of the following publications is incorporated by reference herein: American National
`Standard for Information Systems, Fiber Distributed Data Interface (FDDI) - Token Ring Media Access Control
`(MAC) ANSI X3. 139-1987; IEEE Standards for Local and Metropolitan Area Networks: Overview and Archi-
`tecture, Std 802-1990; A Primer to FDDI: Fiber Distributed Data Interface, copyright 1991, Digital Equipment
`Corporation.
`Reference is made to the following definitions.
`Station: An addressable logical and physical attachment in a ring, capable of transmitting, receiving, and
`repeating information.
`Ring: Two or more stations connected by a physical medium wherein information is passed sequentially
`between active stations, each station in turn examining or copying and repeating the information, finally re-
`turning the information to the originating station.
`Media Access Control (MAC): A Data Link Layer responsible for the scheduling of data transmissions to
`and for receiving transmissions from a shared medium Local Area Network (e.g., an FDDI ring ).
`Token: A unique symbol stream that indicates the rig ht to transmit on a shared medium. On a Token Ring,
`the Token circulates sequentially through the stations in the ring. At any time, it may be held by no stations or
`by one station.
`Frame: A Protocol Data Unit (PDU) transmitted between cooperating MAC entities on a ring, including a
`starting delimiter, addresses, a variable number of data octets (eight ordered bits that form a pair of data sym-
`bols), and an ending delimiter.
`Protocol Data Unit (PDU): A unit of data transfer between communicating peer layer entities which may
`contain control, address and data information. FDDI MAC PDUs are Tokens and Frames.
`Receive: The action of a station in accepting a Token, Frame, or other symbol sequence from the incoming
`medium.
`
`Transmit: The action of a station in generating a Token, Frame, or other symbol sequence and placing it
`on the outgoing medium.
`Addresses: Aset of 48-bit station addresses, which may be a station’s unique address, a 48-bit Broadcast
`Address (all ones), and any other 48-bit Group Addresses recognized by a station.
`Fig. 1 is an exemplary embodiment of a specific network topology. It should be realized that the teaching
`of the invention also applies to a number of other network topologies, including Carrier Sense Multiple Ac-
`cess/Collision Detect (CSMA/CD) networks.
`As seen in Fig. 1 a token ring 1 includes a set of stations 2 (designated A-N) that are serially connected
`by a transmission medium 3, such as an optical fiber, to form a closed loop. Information is transmitted sequen-
`tially, as a stream of bits, from one active station 2 to the next. Each station 2 generally regenerates and repeats
`each bit and serves as a means for attaching one or more devices to the ring for the purpose of communicating
`with other devices on the ring. A given station that has access to the medium 3 transmits information onto the
`ring, where the information circulates from one station to the next. The format of the circulating information
`includes a destination address, a source address, and a data field. In the IEEE 802 format, the first bit of the
`destination address specifies whether the destination address is an individual address or a group (multicast)
`address. That is, whether the destination address specifies the LAN address of a specific station or, in the case
`of a group address, the stations to which the associated data field is directed. An addressed destination station
`or stations copies the information as it passes. Eventually, the station that originally transmitted the information
`removes the information from the ring 1.
`Each LAN address, as specified by the IEEE 802 standard, consists of 48 bits. Of these, the first, or most
`significant, 24 bits identify the organization owning the address. For example, all group addresses assigned
`to a given organization begin with the same 24 bits that uniquely identify the organization. These first 24 bits
`are referred to as an "Organizationally Unique Identifier" (OUI). In general, in any given LAN the number of
`OUIs is small. The remaining 24 bits, for an individual address, uniquely identify each of the stations for that
`organization that are coupled to the LAN.
`On a token ring a Frame typically also includes a Frame Status field that contains an E-indicator, A-indicator
`and C-indicator. The E-indicator is used to indicate if the Frame has been detected to contain an error. The A-
`
`indicator is used to indicate if the destination address of the Frame has been matched by one or more stations
`2
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`

`

`EP 0 522 743 A1
`
`2 on the ring. The C-indicator is used to indicate if the Frame was received and copied by one or more stations
`2 on the ring.
`Each station 2 contains a Destination Address list. The Destination Address list contains a set of addresses
`
`that the station uses to compare with the Destination Address of each received Frame. If a match is found then
`the Frame is received and copied. On a token ring, if a match is found the station receives and copies the Frame
`and, in addition, sets the A-indicator and C-indicator when repeating the Frame. The Destination Address list
`contains the station's My Address and one or more Alias Addresses. An "alias address" is an address different
`from the station’s individual address but used in a similar manner as the individual address. For example, an
`application may require that an alias address be used as a source address when transmitting Frames. Also the
`"alias address" may be used to compare with the destination address field of a Frame when receiving Frames.
`Atypical implementation of one of the stations 2 may have two individual addresses and 32 group address-
`es in the Destination Address list.
`
`A problem arises as communication networks become larger and faster, and as addresses associated with
`stations increase in size. That is, a need has arisen to optimize a station address comparison function.
`In general, datalink adapters coupled to a LAN are required to recognize destination addresses associated
`with Frames conveyed by the LAN. Many conventional network adapters have only one individual address,
`which may be easily recognized. However, in that each network station may also accept a number of group
`addresses, the adapter is also required to quickly determine whether to receive the group Frame. For example,
`for some token ring networks, e.g., FDDI, receiving stations are required to set an "Address Recognized" flag
`in the received Frame. For the smallest size Frames this implies that the address must be recognized within
`11 octets, or 0.88 microseconds. This requirement places an upper bound on the time within which end stations
`must recognize group addresses. For example, bridges, which are used to interconnect two or more LANs, must
`recognize the destination addresses of every Frame and rapidly decide whether to receive the Frame for for-
`warding. Also, routers in wide area networks (WAN) typically must examine a large forwarding database to de-
`cide the output link for a given destination address.
`Several high-speed networks simplify the problem of address lookup by using a hierarchical address for-
`mat that allows the forwarding path to be looked up directly. Although this approach results in fast routing, the
`association of a destination’s unique identifier (generally a 48-bit individual address) to the corresponding hi-
`erarchical address at the originating station still requires searching through a large address database.
`One method to determine whether to accept the Frame of data is to employ a hardware lookup of the ad-
`dress in a list or a table of acceptable addresses. This is the approach taken in ContentAddressable Memories
`(CAMs). One significant advantage of a CAM is that there is provided perfect address recognition. That is, given
`a network address the CAM determines with certainty whether the address is within a table of acceptable ad-
`dresses. However, CAMs are highly gate-intensive and add significant complexity, power consumption, and
`consume a significant amount of surface area when implemented within an integrated circuit. Furthermore,
`the CAM search time increases as the number of addresses which must be recognized increases. With a trend
`towards a client-server form of distributed computing, the number of group addresses that a given station must
`receive is continuously increasing. As such, the practical limits of the CAM-approach to address recognition is
`quickly reached.
`Another address recognition method employs a hash filter to map the received address into a bit mask.
`Hashing is generally performed in two steps. In the first step, an address A is converted to a hash value f(A).
`In the second step, some m bits of f(A) are extracted so that a total number of hash cells is 2"". The logic state
`of a predetermined bit in the mask indicates whether a given received address is to be accepted or rejected.
`One significant advantage of the hash approach is that the speed of hashing is independent of the number of
`addresses and is thus particularly suitable if the number of acceptable addresses is large. However. a disad-
`vantage of hashing is that if the size of the bit mask is made small, so as to reduce the required circuitry, several
`addresses may map to the same bit. Thus, the hashing approach provides imperfect filtering of the received
`addresses.
`
`In many LANs, the destination address is the first part of the Frame, and the Frame is passed through a
`cyclic redundancy check (CRC) circuit. As a result, it has been recognized that the bits of the CRC provide a
`mechanism for hashing. In that each network station may have a number of group addresses that are to be
`received by the station, the network adapter employs the CRC polynomial as a hash function to reject Frames
`associated with undesired group addresses.
`In one hashing approach, described in a device specification entitled "MK68590 Local Area Network Con-
`troller for Ethernet" (United Technologies Mostek), a group address filter includes a 64 bit mask composed of
`four sixteen bit registers used to accept incoming group addresses. This is an imperfect filter that requires a
`host processor to perform final filtering. The first bitof the incoming address must be a "1" for eitherthe Logical
`Address Filter orthe BroadcastAddress decode to be enabled. Otherwise the incoming address is an individual
`3
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`

`

`EP 0 522 743 A1
`
`address and is compared against the contents of a 48 bit register.
`All incoming data passes through a CRC Generator. In the case of a group address, the six most significant
`bits of the CRC Generator are strobed into the Hash Register after the 48th bit of the group address has passed
`through the CRC Generator. The six bits select one of the 64 bits in the Logical Address Filter such that Hash
`Address 00 selects bit 0 and Hash Address 63 selects bit 63. If the selected mask bit is a "1", the address is
`accepted. However, different organizations can assign group addresses which may map to the same bit of the
`hash mask, resulting in a collision.
`What is not taught by the prior art, and what is thus an object of this invention to provide, is a network ad-
`dress recognition method and apparatus that combines the use of a CAM and a Hash filter, in conjunction with
`a careful allocation of group addresses, to provide perfect address recognition while minimizing a required
`amount of circuitry and complexity.
`The apparatus and method of the invention described herein provide improved flexibility in assigning group
`addresses.
`
`SUMMARY OF THE INVENTION
`
`The foregoing and other problems are overcome by a method and apparatus for comparing a first value
`to a second value to determine if the first value equals the second value. The invention in its broad form resides
`in a method, for a network having a destination address comparator, of comparing a first value comprised of
`(n) bits to a second value to determine if the first value equals the second value, said method comprising the
`steps of: comparing a portion of the first value, the portion being comprised of (n - x) bits, to one or more values
`stored within a memory means for determining if the memory means has a stored value that corresponds to
`the portion ofthe second value; filtering the first value with a hash filter means for determining if the first value
`is recognized by the hash filter means; and declaring that the first value equals the second value only if it is
`determined that (a) the memory means has a stored value that equals the portion of the first value and that
`(b) the first value is recognized by the hash filter means.
`Preferably, the first value is represented by (n) address bits received from a communication network, such
`as a Token ring LAN.
`As described herein, an address comparator includes circuitry for storing the received address and for ap-
`plying all or a portion of the stored address to a CAM containing entries storing one or more target addresses.
`The address comparator also includes a Hash filter for filtering the first value for determining if the first value
`is recognized by a Hash mask. The received address is applied to a hash function generator, such as a CRC
`generator, and a plurality of the resultant bits, for example nine, are used to access the Hash mask. The address
`comparator further includes a programmable control circuitry for indicating that the received address equals
`the target address if (a) the CAM has an entry that equals all or a portion (OUI) of the received address and/or
`if (b) the bits from the hash function generator, resulting from the received address, are recognized by the Hash
`filter. In a presently preferred embodiment of the invention the hash function generator includes a CRC gen-
`erator. A technique is also disclosed for correcting the CRC for bits that arrive before the destination address.
`
`BRIEF DESCRIPTION OF THE DRAWING
`
`A more detailed understanding of the invention may be had from the following description of a preferred
`embodiment, given by way of example and to be understood in conjuction with the accompanying drawing
`wherein:
`
`Fig. 1 schematically depicts a token ring network;
`Fig. 2a is a simplified block diagram showing the combined CAM/Hash filter used to recognize network
`addresses;
`Fig. 2b is a block diagram showing in greater detail the CRC Correction block of Fig. 2a; and
`Figs. 3 and 4 illustrate address storage formats for a 43 bit address and for two Organizationally Unique
`Identifiers, respectively.
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`The ensuing description of a preferred embodimentof the invention is made in the context of a FDDI token
`ring data communications network that conforms to the ANSI and IEEE 802 standard. It should be realized.
`however, that the teaching of the invention is applicable to other networks and standards, such as CSMA/CD,
`OSI, and TCP/IP networks. In general, the teaching of the invention is applicable to any network that operates
`in accordance with IEEE 802 address formats, including, by example, IEEE 802.3, IEEE 802.5, etc..
`4
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`

`

`EP 0 522 743 A1
`
`In this regard reference is made to the following documents: ANSI/IEEE Std. 802.3-1985, "Carrier Sense
`Multiple Access with Collision Detection (CSMA/CD) Access Method and Physical Layer Specifications", Insti-
`tute of Electrical and Electronic Engineers; ANSI/IEEE Std. 802.5—1989, "Token Ring Access Method and Phys-
`ical Layer Specifications", Institute of Electrical and Electronic Engineers; Postel, J., Ed. "Internet Protocol
`Specification", SRI International, Menlo Park, CA, Sept. 1981 RFC-791; Postel, J., Ed. "Transmission Control
`Protocol Specification", SRI International, Menlo Park, CA, Sept. 1981, RFC-793; and Information Processing
`Systems - Open Systems Interconnection (OSI) - Basic Reference Model, International Organization for Stan-
`dardization, Oct. 1984, Draft International Standard 7498.
`Furthermore, and as will be made apparent below, it should be realized that the teaching of the invention
`applies in general to the decoding of information that is expressed in a digital format.
`In recognition of the fact that there are generally but a few OUIs associated with a given LAN, and referring
`to block diagram of Fig. 2a, the invention employs an address filter 10 having a CAM 12 that recognizes the
`DUI portion of the LAN address. The CAM 12 thus confirms whethera specific network address has been as-
`signed to an organization associated with the station 2 that includes the address filter 10. In parallel with the
`operation of the CAM 12, the invention employs a hash filter 14. This combination of CAM Iookup and hash
`filtering results in perfect filtering of network addresses, provided that the addresses are assigned such that
`collisions cannot occur. That is, perfect filtering is achieved so long as no more than one address hashes to
`any given bit in a hash mask 16. Alternately, given a set of addresses, the teaching of the invention enables
`the selection of a hash function that eliminates or minimizes the occurrence of hashing collisions.
`By careful address allocation perfect filtering can be achieved. Careful address allocation entails selecting
`an address, hashing the selected address, and determining if a collision occurs. If collision occurs another ad-
`dress is selected and the process repeated.
`It should be noted that in Fig. 2a a signal line designated USER INPUT is coupled to a plurality of circuit
`blocks. This signal line indicates a data path through which a user programs values into certain of the logic
`blocks, as will be described.
`The incoming bit stream from the LAN 1 is routed in parallel to an address register 20, that includes serially
`connected registers 20a, 20b, and 20c, and to CRC logic 22.
`A bit counter 18 is connected to a bit clock and is enabled to count the bit clocks by a "start of frame" signal.
`The counter 18 is used to give an indication of the arrival of the last bit of the destination address. For example,
`in FDDI the counter 18 counts the bit clocks until it reaches a count of 56. This indicates a condition wherein
`
`56 bits have been received from the LAN 1. The first eight bits of the Frame, which indicate Frame control in-
`formation, are stored in an eight bit Frame control register 20d that has an input serially coupled to an output
`of address register 20c. The next 48 bits, indicating the destination address for the Frame, are stored in the
`address registers 20a—20c. The first bit of the 48 bits is stored in the 1-bit register 20c and indicates whether
`the address is an individual or a group address. This bit is referred to as an I/G bit. The remaining 47 address
`bits are stored in address registers 20a and 20b.
`The CAM 12 includes a plurality of entries, for example four, only one of which is shown in Fig. 2a. The
`CAM entry is comprised of three registers: a 24 bit CAM entry 24a, a 23 bit CAM entry 24b, and a one bit CAM
`entry 240. Each register of the CAM entry has an output coupled to an input of an associated comparator 26a,
`26b, and 26c. The other comparator in put is coupled to the associated 24 bit, 23 bit or one bit address register
`20a-200, respectively.
`There are two output signal lines from the CAM 12. Depending upon the state of mode control registers
`associated with the CAM entries, the first output (x) indicates whether the received address matches the first
`24 bits, the DUI address portion, of any CAM entry. The second output (y) indicates whetherthe address match-
`es all 48 bits ofany CAM entry.
`Specifically, the (x) output is sourced from a gate 12a having as inputs the output of bit counter 18 and the
`outputs of comparators 26b and 26c. Gate 12a asserts an enabling output when, after the reception of 56 bits,
`the first 24 bits of the CAM entry equal the 24 bits of the address stored in address registers 20b and 200. The
`output (y) is sourced from a gate 12b having as inputs the output of gate 12a and comparator 26a. The output
`of gate 12b is asserted when. after the reception of 56 bits. the first 24 bits of the CAM entry equal the 24 bits
`of the address stored in address registers 20b and 20c, as indicated by the output of gate 12a, and also the
`24 bits of CAM entry 24a equal the 24 bits in address register 20a.
`As was previously stated, only one CAM entry is shown in Fig. 2a. Typically, each of the plurality of CAM
`entries includes 48 bits of CAM entry 24a-24c, associated comparators 26a-260 and decoding gates. The mode
`control registers U1. U2 and U3 are associated modes for the matching CAM entry. After the destination ad-
`dress has been received fully the destination address is compared to all of the CAM entries in parallel so as
`to determine if one of the plurality of CAM entries matches the received address.
`Further in accordance with the invention a hashing function generator is supplied to operate upon the re-
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`

`

`EP 0 522 743 A1
`
`ceived bit stream. In a presently preferred embodiment of the invention the hashing function generator is a CRC
`generator, although the teaching of the invention is not limited to only the use of a CRC technique. For example,
`the hash function generator may employ specific bits of the destination address, a correlation of address bits,
`checksums, or XOR folding. A description of these various techniques is made in a technical report entitled "A
`Comparison of Hashing Schemes for Address Lookup in Computer Networks", DEC-TR-593, by R. Jain (1989),
`which is available from the Digital Equipment Corporation, Littleton, MA 01460.
`The CRC logic 22 performs a 32-bit Cyclic Redundancy Check (CRC) of the first 56 bits. By removing the
`effect of the first eight bits, that is, the Frame control field stored in register 20d, the CRC for the destination
`address is obtained. Only the first few bits of the CRC, for example nine bits, are used in hashing. The effect
`of the Frame control field is removed by CRC correction logic 28. Provided with the Frame control field from
`register 20d the CRC correction logic 28 determines the quantity to be exclusive-ored with the output of the
`CRC logic 22 to obtain only the CRC for the received address. The corrected nine bits of CRC are used as an
`index into a hash mask which, in a presently preferred embodiment of the invention, is a 512-bit hash mask
`16 comprised of, by example only, 32 16-bit registers HM00-HM31.
`For embodiments of the invention not having a Frame control field before the destination address no cor-
`rection of the hashing function may be required. Furthermore, for embodiments of the invention that employ
`other than a CRC technique, and that require hash function correction, the correction mechanism is selected
`in accordance with the hash function.
`
`As seen in Fig. 2b the CRC correction logic 28 includes, in a presently preferred embodiment of the in-
`vention, a read only memory (ROM) 28a that stores a set of nine (ROM locations 0-8) n-bit numbers, wherein
`n equals the number of bits of CRC that are used to index the 2n hash mask 16. ROM 28a has address inputs
`coupled to the frame control register 20d. The CRC correction logic 28 also includes an n-bit correction register
`28b which is initialized with the contents of the 0th ROM location. In operation, the content of the ith ROM 28a
`location is exclusive-or’ed with logic 28c to the correction register 28b if and only if the ith bit in the frame control
`register 20d is set. This operation may occur as the frame-type bits are received from the LAN and well before
`the final bit of the destination address is received. After the last bit of the destination address has been received
`
`the content of the correction register 28c and the CRC register 22a are exclusive-or'ed through logic 28d to
`produce the n-bit index into the hash mask 16.
`In accordance with a preferred embodiment of the invention a set of nine 32-bit correction values, ex-
`pressed in hexadecimal notation, is as follows:
`
`0
`
`1
`
`mNODU‘l-FODN
`
`
`
`4F-57-68-11
`
`BB-7E—75-34
`
`2D-DO—EE-65
`
`94-88-F9-E9
`
`08-24-F2-2F
`
`E6-72-F7-CC
`
`73-39-7B-E6
`
`39-90-BD-F3
`
`9E—AE—D0-22
`
`
`
`
`
`Only those bits that are used to form the index into the hash mask need to be stored in the ROM 28a. For
`example, for a nine-bit implementation the ROM 28a contains the following:
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`

`

`
`
`
`
`ROM 28a Location Content
`
`EP 0 522 743 A1
`
`
`
`0
`
`1
`
`O’NCDO‘I-PLON
`
`10011110-1
`01001111-0
`
`10111011-0
`
`00101101-1
`
`10010100-1
`
`11001000—0
`
`11100110-0
`
`01110011-0
`
`00111001-1
`
`
`
`
`
`These are the first nine bits of the 32-bit correction values shown previously and are obtained by evaluating
`the expression:
`
`i). am i.
`modi x<55'
`by setting i=1, 2, ..., 8, where the cyclic redundancy check polynomial is g(x).
`The content of the 0th ROM 28a location is
`
`modl (X56 + X48) '00, 900]-
`In this expression l(x) is a polynomial of degree 31 with all coefficients equal to one.
`As an example, the received frame control is 01010000, which is a Logical Link Control (LLC) frame of pri-
`ority 0 (lowest asynchronous priority). The frame control information is stored within the frame control register
`20d.
`
`After the frame control is received, the computation of the correction factor is begun. In that the second
`and fourth bits in the frame control are set, ROM locations 0, 2, and 4 are exclusive-or’ed as follows.
`
`0
`
`2
`
`4
`
`result
`
`10111011-0
`
`10010100-1
`
`11100110-0
`
`11001001-1
`
`It will be remembered that the correction register 28b was initialized to the content of ROM 28a location
`zero. The result is stored in correction register 28b.
`After 56 bits of the frame are received (i.e., the last bit of the destination address), the CRC register 22a
`contains:
`
`10101110-01011100-10111000-00000110
`
`Employing logic 28d to exclusive-or the first 9-bits of the CRC register 22a with the correction factor stored
`in correction register 28b there is obtained:
`
`10101110-0
`
`11001001-1
`
`result
`
`01100111-1
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`

`

`EP 0 522 743 A1
`
`The 9-bit index into the hash mask 16 is thus 1-11100110. or 486.
`If an B-bit index is desired instead of a 9-bit index, it is preferred to use bits 2 through 9 (rather than bits
`1 through 9). The 8-bit index using these bits would be 1-1110011, or 243.
`Having thus described a presently preferred embodiment of the CRC correction logic 28, the discussion
`of the remainder of Fig. 2a will now be continued.
`The user specifies acceptable address match patterns by programming, for each CAM entry. the associ-
`ated mode control registers U1 , U2 and U3. This programming is accomplished in accordance with the following
`Table.
`
`U1
`
`U2
`
`U3
`
`48-bit
`
`OUI
`
`Hash-mask
`
`control
`
`control
`
`control
`
`Resulting mode
`
`N
`
`N
`
`N
`
`Y
`
`Y
`
`Y
`
`Y
`
`N
`
`N
`
`Y
`
`Y
`
`N
`
`N
`
`Y
`
`Y
`
`N
`
`Y
`
`N
`
`Y
`
`N
`
`Y
`
`N
`
`Y
`
`N
`
`Accept all Frames
`
`having Hash mask
`
`comparison only
`
`All Frames having 001
`
`match are accepted
`
`A11 Frames having OUI
`
`match *and* Hash are
`
`accepted
`
`Full 48-bit match
`
`(Normal CAM Mode)
`
`Full 48-bit match
`
`*or* Hash mask
`
`comparison
`
`Full 48-bit match
`
`*or* OUI match
`
`Full 4a-bit *or*
`
`(OUI Match 1*and*
`
`Hash mask match)
`
`None
`
`A Decision Logic Block 32 includes gates connected as shown and decodes the output of Counter 18, the
`outputs Aand B of the CAM 12, the outputs of mode registers U1, U2, and U3, and the outputofthe Hash Mask
`16 so as to provide a signal designated ADDRESS MATCH OUTPUT. ADDRESS MATCH OUTPUT is asserted
`if the received address is accepted, otherwise ADDRESS MATCH OUTPUT is deasserted. Other circuitry, not
`shown, receives the ADDRESS MATCH OUTPUT signal and performs further MAC functions.
`It should be noted that 48—bit or OUl-match user choices are per-CAM entry choices, whereas the hash
`match choice applies globally to all CAM entries. For example, a user may specify two OUl’s: one to be accepted
`unconditionally while the other is to be accepted only if the corresponding hash-bit is also set.
`Another mode of use employs a plurality of the hash masks 16, with the user specifying a specific hash
`mask number for use with each CAM 12 OUI. For this embodiment, and by example, four 128-bit hash masks
`are provided. Afirst CAM entry is associated with a first hash mask, a second CAM entry is associated with
`a second hash mask etc. An OUI match with a particular one of the CAM entries selects the corresponding
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`

`

`EP 0 522 743 A1
`
`hash mask to be used for the hash filter. The dashed line shown in Fig. 2a indicates a hash mask select input
`from the CAM 12.
`
`Although the hash technique may used for both individual and group addresses, it is most effective if used
`only for group addresses. This is because the group address assignments may be readily controlled to avoid
`all hash collisions, while individual address assignments are not normally as readily controlled. The output sig-
`nal line from the 1-bit register, the l/G bit, is depicted to show a preference that the hash mask be used only
`for group addresses. This signal line is not required if individual addresses are also to be recognized using the
`hash mask.
`
`In summary, an embodiment of the invention includes for each of a plurality, for example four, of addresses
`(ADDRESS 1-ADDRESS 4), a set of mode control registers (U1-U3), a set of address registers (20a-20c), and
`a set of CAM entry registers 24a-24c and associated supporting circuitry, including the comparators 26a-26c.
`The hashing function for all address entries is accomplished with the CRC logic 22, the CRC correction logic
`28, and the Hash mask 16. The address size used is 48 bits, which includes the 24 bit OUI. Filtering of addresses
`is accomplished with a 512 bit hash function indexed by nine bits of the corrected CRC.
`Afeature of the invention is the use of a 48-bit CAM entry to store two 24-bit OUls, referred to herein as
`OUI Aand OUI B. T