DEC-TR-593
`
`A Comparison of
`Hashing Schemes for Address Lookup
`in Computer Networks
`
`Raj Jain
`
`Digital Equipment Corporation
`550 King St. (LKG1-2/A19)
`Littleton, MA 01460
`
`Network Address: Jain%Erlang.DEC@DECWRL.DEC.COM
`
`February 1989
`This report has been released for external distribution.
`Copyright c 1989 Digital Equipment Corporation. All rights Reserved
`
`i
`
`UNIFIED 1022
`UNIFIED v. PLECTRUM LLC
`IPR2017-01430
`
`

`

`A Comparison of Hashing Schemes for Address Lookup in Computer
`Networks
`
`Raj Jain
`Distributed Systems Architecture & Performance
`Digital Equipment Corp.
`550 King St. (LKG 1-2/A19)
`Littleton, MA 01460
`ARPAnet: Jain%Erlang.DEC@DECWRL.DEC.COM
`
`DEC-TR-593
`Copyright c 1989, Digital Equipment Corporation. All rights reserved.
`Version: April 12, 1989
`
`Abstract
`
`The trend toward networks becoming larger and faster, and addresses increasing in size, has impelled a need to
`explore alternatives for fast address recognition. Hashing is one such alternative which can help minimize the
`address search time in adapters, bridges, routers, gateways, and name servers.
`
`Using a trace of address references, we compared the eciency of several dierent hashing functions and found
`that the cyclic redundancy checking (CRC) polynomials provide excellent hashing functions. For software imple-
`mentation, Fletcher checksum provides a good hashing function. Straightforward folding of address octets using
`the exclusive-or operation is also a good hashing function. For some applications, bit extraction from the address
`can be used. Guidelines are provided for determining the size of hash mask required to achieve a speci

ed level
`of performance.
`
`1 INTRODUCTION
`
`The trend toward networks becoming larger and
`faster, addresses becoming larger, has impelled a need
`to explore alternatives for fast address recognition.
`DECnet Phase IV currently allows upto 64,000 nodes
`and DEC's internal network called EasyNet [21] al-
`ready has more than 30,000 nodes. Such large net-
`works obviously need more ecient address lookups.
`The size of the addresses themselves is also grow-
`ing. HDLC, a commonly used datalink protocol stan-
`dard, was designed with 8-bit addresses. All IEEE
`802 LAN protocols and Ethernets support 48-bit ad-
`dresses while the ISO/OSI network layer requires 160-
`bit (20 octets) addresses. This increased length of the
`search key has also necessitated a need to

nd ecient
`ways to look up addresses. Finally, because networks
`are becoming faster, network routers, which previ-
`ously handled a few hundred packets per second are
`now expected to handle 8000 to 16,000 packets per
`second. This fast handling requires squeezing every
`cycle out of the frame forwarding code.
`
`The organization of this paper is as follows. In the
`
`next section, we describe a number of problems in
`networking design that require searching through a
`large database.
`In Section 3, we discuss a number
`of possible solutions including caching and hashing.
`In a companion paper [13], we compared the perfor-
`mance of various cache replacement algorithms. One
`of the unexpected results of this analysis was that in
`some cases, caching could be harmful in the sense that
`the performance would be better without caching.
`We, therefore, tried hashing as a possible solution
`to the problem of fast searching through the address
`database. After a brief introduction to hashing con-
`cepts, we develop a metric to compare various hash-
`ing functions. We then use the trace data to compare
`several dierent hashing functions.
`
`2 A General Problem
`
`One of the performance problems encountered repeat-
`edly in computer systems design is that of search-
`ing through a large information base. Simply stated,
`the problem is that of

nding the information asso-
`ciated with a given key. High performance access to
`
`1
`
`

`

`information is particularly interesting if the number
`of keys is large or if the time to access the main infor-
`mation base is long as is the case if the information
`is located remotely. Some of the areas in the design
`and implementation of computer networks where this
`problem is encountered are as follows:
`
`Datalink adapters on local area networks (LAN) need
`to recognize the destination addresses of frames on
`the LAN. Most adapters have only one physical ad-
`dress, which can be easily recognized. However, each
`station also accepts a number of multicast addresses
`and the adapter must quickly decide whether to re-
`ceive a multicast frame. In some token ring networks,
`e.g., Fiber Distributed Data Interface (FDDI) [6,22],
`stations need to set an address recognized ag in the
`frame. For the smallest size frames this means that
`the address has to be recognized within 13 octets
`(1.04 s). This puts an upper bound on the time
`within which end stations have to recognize the mul-
`ticast addresses they want to listen to.
`
`Bridges, used to interconnect two or more LANs, have
`to recognize the destination addresses of every frame
`and decide quickly whether to receive the frame for
`forwarding. In order to learn the relative locations
`of stations, transparent learning bridges [7] need to
`recognize source addresses also.
`
`Routers in wide area networks (WAN) have to look
`through a large forwarding database to decide 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 it does make the routing fast, asso-
`ciation of a destination's unique identi

er (generally a
`48-bit physical address) to its hierarchical address at
`the originating station still requires searching through
`a large address database.
`
`Name servers have the ultimate responsibility for as-
`sociating names to characteristics. Among all the
`applications listed here, name servers probably have
`the largest information base and the problem is most
`acute.
`
`In all of the above applications, time to search
`through a large information base has a signi

cant
`impact on the overall performance and an analysis
`similar to that presented here would be helpful in im-
`proving the performance.
`
`3 Possible Solutions
`
`The time to access information is a function of several
`parameters, including the following:
`
`1. Size of the information base
`
`2. Usage pattern
`
`3. Key structure
`
`4. Storage structure
`
`5. Storage location
`
`6. Access method
`
`To make the access more ecient we need to consider
`changing each one of the above six parameters. The
`

rst parameter, the size of the information base, is
`really not under the control of the system designers.
`In the future, the size is only going to grow and make
`the problem worse. We, the system designers, have
`only indirect control, if any, over the second param-
`eter, the usage pattern. By rewarding certain usage
`patterns, for example, by providing a faster response
`to these patterns, we can encourage users to follow
`certain patterns. The key to ecient access lies in
`the remaining four parameters.
`
`By properly organizing key structures, e.g., with hier-
`archical addresses, we can partition the information
`base into manageable chunks. Most large networks
`have several levels of hierarchy. DECnet Phase IV,
`for example, has two levels of hierarchy. The network
`consists of several areas each with up to 1024 end
`stations.
`
`The second way to solve the problem is to organize
`the storage into several levels of hierarchy. For exam-
`ple, most frequently used addresses could be kept in
`a cache. Addresses not found in the cache would be
`looked up in the full database. This is a two-level hi-
`erarchy. An obvious extension is an n-level hierarchi-
`cal storage structure in which addresses not found in
`ith level are then looked up in (i+1)th level. Caching
`is particularly helpful if the reference pattern has a
`locality property [11].
`
`In some cases, the problem is solved by locating dif-
`ferent levels of the storage hierarchy at successively
`more remote locations. For example, the clients of a
`name server could keep a local copy of the frequently
`used names. This is also called caching. In this case,
`the dierence between access time to local copy and
`
`2
`
`

`

`n1
`
`ni
`
`nM
`
`>
`
`r1
`
`>
`
`ri
`
`>
`
`rM
`
`i21
`
`M
`
`>
`
`
`h(Addr)
`
`Hash cells
`
`Subtables
`
`Figure 1: Hashing concepts.
`
`5 Hashing: Concepts
`
`Webster's dictionary de

nes the word `hash' as a verb
`\to chop (as meat and potatoes) into small pieces"
`[31]. Strange as it may sound, this is correct. Basi-
`cally, hashing allows us to chop up a big table into
`several small subtables so that we can quickly

nd the
`information once we have determined the subtable to
`search for. This determination is made using a math-
`ematical function, which maps the given key to hash
`cell i, as shown in Figure 1. The cell i could then
`point us to the subtable. We will use ni to denote the
`size of the ith subtable and M to denote the number
`of hash cells. Ideally, one would like to use a hashing
`function so that each subtable has only one entry so
`that no further searching or subtables are required.
`For most hashing functions, the size of subtables ni
`decreases as the size of the hash table M increases.
`For an very large number of hash cells, one is almost
`guaranteed to be able to

nd the desired key without
`further search.
`
`For

nite hash tables, two or more keys may map to
`the same hash table location leading to a collision.
`Most of the hashing literature is about what to do
`after a collision. If the hash table size is larger then
`or equal to the total number of keys, one does not
`need subtables and use the hash table itself to store
`the keys and other information. Several techniques,
`such as linear probing and double hashing, have been
`devised to resolve the collisions in as few attempts
`as possible. Dynamic hashing schemes allow the ta-
`ble size to increase dynamically as the number of en-
`tries grows [4,16]. Perfect hashing schemes also ex-
`ist, which cause no collisions [3,30]. Minimal perfect
`hashing functions not only avoid collisions, but also
`
`3
`
`remote database is so dierent that caching can be
`justi

ed even if there is very little locality in the us-
`age pattern.
`
`Finally, the time to access can be reduced by devising
`ecient search strategies. Various searching meth-
`ods, such as tree and trie search strategies, have been
`developed to eciently

nd a key in a table of keys
`[25]. One method, which we analyze in this paper,
`is hashing. If properly designed, a hashing algorithm
`can allow a very large information base to be searched
`in constant time.
`In fact, hashing is already being
`used in an existing LAN adapter to recognize multi-
`cast addresses.
`
`4 Measured Environment
`
`In order to compare various hashing strategies, we
`used a trace of destination addresses observed on
`an extended local area network in use at Digital's
`King Street, Littleton facility. The network consists
`of several Ethernet LANs interconnected via bridges.
`The network is a part of Digital's company-wide net-
`work called EasyNet [21], which has more than 30,000
`nodes. The building itself has approximately 1200
`stations on several Ethernet LANs interconnected via
`approximately 80 bridges. A number of routers con-
`nect the extended LAN to the rest of the Easynet.
`There are 30 Level 1 routers and 6 Level 2 routers
`in the building. A promiscuous monitor attached to
`one of the Ethernet LANs produced a time-stamped
`reference string of 2.046 million frames observed over
`a period of 1.09 hours. A total of 495 distinct sta-
`tion addresses were observed in the trace, of which
`296 were seen in the destination

eld. Due to bridge
`

ltering, only those frames whose desinations have a
`short path through the monitored segment are seen
`on the segment.
`
`There are several advantages and disadvantages to
`using a trace. A trace is more credible than refer-
`ences generated randomly using a distribution. On
`the other hand, traces taken on one system may not
`be representative of the workload on another system.
`We hope that others will

nd the methodology pre-
`sented here useful and will apply it to traces taken in
`environments relevant to their applications.
`
`

`

`Table 1: Computing Information in the Last Two
`Bits
`
`Bits
`
`# of
`# of
`Frames Addr.
`1252479
`239
`00
`219989
`71
`01
`148725
`55
`10
`424807
`130
`11
`P 2046000
`496
`
`qi
`
`pi qi log2 pi
`
`0.61
`0.11
`0.07
`0.21
`1.00
`
`0.48
`0.14
`0.11
`0.26
`1.00
`
`0.65
`0.31
`0.22
`0.41
`1.59
`
`equal to pi and the expression P pi log2(pi) would
`be called the entropy of the hashing function. It is
`because of this similarity that we will call the quantity
`P qi log2(pi) the entropy or information content
`of the hashing function.
`It is measured in units of
``bits.' We illustrate its computation using a simple
`example.
`
`In the
`Hashing is usually performed in two steps.
`

rst 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 the total number of hash cells is 2m.
`For example, one could take the last m bits of f(A):
`
`h(A) = Modff(A); 2mg
`
`In the
`Here, f(A) is usually a complex operation.
`simplest case, we could have f(A) = A and take
`the last two bits, for instance, of the address as our
`hashing function. This will break the address table
`into four subtables. The number of address entries in
`these four subtables and the corresponding number of
`frames refering to these subtables using our measured
`trace are shown in Table 1. The ratio of the number
`of frames that refer a subtable and the total number
`of frames gives the probability qi. Similarly, the ratio
`of the number of addresses in a subtable to the total
`number of addresses gives the probability pi. The in-
`formation entropy for each subtable is then computed
`and added to give the total entropy for this hashing
`function. For our trace, we found that the last two
`bits of the address have an entropy of 1.59 bits. In
`other words, if we use the last two bits of the address
`to decide which subtable to search, we would save
`1.59 lookups per frame.
`
`leave no empty space in the hash table [1,2,10,23].
`For surveys of various hashing schemes and issues see
`[14,15,17,18,19,20,25,27].
`
`If the hash table size is less than the total number
`of keys, collisions are unavoidable. We would like
`the hashing function to be such that the addresses
`which are looked up more often are in smaller subta-
`bles. It is desirable to minimize the average number
`of lookups required for the trace. To compute this,
`we de

ne the following symbols:
`
`R = Number of frames in the trace
`N = Number of distinct addresses in the trace
`M = Number of hash cells
`= Number of subtables
`ni = Number of addresses that hash to ith cell
`Pi ni = N
`= Number of frames that hash to ith cell
`Pi ri = R
`pi = Fraction of addresses that hash to ith cell
`= ni
`= Fraction of frames that hash to ith cell
`= ri
`
`ri
`
`qi
`
`N
`
`R
`
`If we perform a regular binary search through all N
`addresses, we need to perform 1+log2(N ) or log2(2N )
`lookups per frame. Given an address that hashes to
`ith cell, we have to search through a subtable of ni
`entries. Using a binary search, we would need only
`log2(2ni) lookups. The total number of lookups is:
`
`Number of lookups for the trace = X
`
`ri(log2(2ni))
`
`X ri(log2(2ni))
`
`i
`
`1 R
`
`Number of lookups per frame =
`
`Compared to log2(2N ) lookups per frame, the net
`saving due to hashing is:
`
`Lookups saved per frame
`ri
`= (log2(2N )) X
`
`(log2(2ni))
`
`R
`
`= X
`
`
`
`i
`
`ri
`
`R
`
`log2(
`
`i
`ni
`
`N
`
`)
`
`= X
`
`i
`
`qi log2(pi)
`
`(1)
`
`Here, qi and pi are probabilities such that Pi qi = 1
`and Pi pi = 1. The goal of a hashing function is to
`maximize the quantity P qi log2(pi). Notice that
`pi and qi are not related. In the special case of all
`addresses being equally likely to be referenced, qi is
`
`We do not have to limit ourselves to the last two
`bits. We could use any two consecutive bits i and
`i + 1. The resulting information as a function of i is
`shown in Figure 2. Here, the most signi

cant bit of
`the address is denoted as the 0th bit, and the least
`
`4
`
`

`

`12345678
`
`20
`40
`60
` First Bit of the Sequence
`
`80
`
`Figure 3: Information in address bits.
`
`8
`
`6
`
`4
`
`2
`
`0
`
`0
`
` Information in Bits
`
`The

rst observation is not surprizing considering
`that the

rst three octets of the IEEE 802 addresses
`used on IEEE 802 LANs are assigned by the IEEE
`and, thus, most stations have the same

rst three
`octets. The

rst two bits corresponding to the
`global/local assignment and multicast/unicast ad-
`dresses may be dierent in dierent addresses. Given
`these two bits, other bits can be easily predicted. In
`multivendor environments the

rst 3 octets may have
`a little more information. However, in general, these
`bits are not good for hashing purposes.
`
`The second observation says that the

fth octet of
`the address has the highest information in our envi-
`ronment. This observation, if applicable, leads to the
`following types of conclusions:
`
`If
`1. Use the

fth octet as the hashing function.
`one were hashing solely based upon the address
`bits, the bits in this octet would provide a max-
`imum savings in the number of lookups. If one
`were using this hashing function to

lter out
`unwanted frames, these bits would provide the
`least number of them.
`
`2. When comparing two addresses, compare the
`

fth octet

rst. If the addresses are not equal,
`the very

rst comparison will fail more often
`than when using other octets.
`
`3. Use the

fth octet as the branching function at
`
`5
`
`20
`40
`60
` First Bit of the sequence
`
`80
`
`3.2
`
`2.4
`
`1.6
`
`0.8
`
`0.0
`
`0
`
` Information in Bits
`
`Figure 2: Information in two consecutive bits of ad-
`dresses.
`
`signi

cant bit is the 47th bit. Notice that the best two
`bits for this trace are bits 36 and 37. These provide
`a full two bits of information, the maximum that one
`could expect of two bits.
`
`6 Hashing Using Address Bits
`
`We can now generalize the concept of hashing using
`address bits to m bits with m = 1, 2, . . . . In general,
`we could hash using bits i, i + 1, ..., i + m 1 of
`the address to 2m subtables. The number of lookups
`saved, as we saw in the last section, is equal to the
`information entropy of the bits. For our trace, this is
`plotted in Figure 3. The starting position i of the bit
`sequence is plotted along the horizontal axis and the
`information in bits i through i+m1 computed using
`Equation 1 is plotted along the vertical axis. Eight
`curves corresponding to m consecutive bits with m =
`1, 2, . . . , 8 are plotted.
`
`From Figure 3, we observe that:
`
`1. All 8-bit sequences between bits 0 and 24 have
`less than two bits of information.
`
`2. The bits 32 through 39, in general, have a high
`information content.
`
`

`

`the root of a tree database. If the addresses are
`stored in a tree [28] or trie structure [25] and the
`address bits are used to decide the branch to be
`taken, using bits from this octet would provide
`maximum discrimination. Compare this to us-
`ing the bits from the

rst three octets. Most of
`the bits in the

rst three octets are the same
`in all addresses and we would end up following
`the same

rst step for all searches.
`
`4. Use the

fth octet as the load balancing func-
`tion for dierent paths. Given several alterna-
`tive paths to a set of destinations, one way to
`balance the load on dierent paths is to select
`a path randomly. This causes out-of-order ar-
`rivals at the destination. A better alternative
`is to decide the path based on a few bits of the
`address. This ensures that all frames going to a
`particular destination follow a single path and
`load balancing is achieved by dierent destina-
`tions using dierent paths.
`
`It should be obvious that the

fth octet may not
`be the most informative octet for all environments.
`Nonetheless, the above recommendations are useful
`providing that one uses the appropriate, most infor-
`mative octet instead.
`
`7 Correlation of Address Bits
`
`In the last section we saw that many bits in the
`address had much less than one bit of information.
`Even though many bits may have one bit of infor-
`mation each, the combined information of these bits
`may not be much. This is due to a correlation among
`bits. Statistically, the correlation between two ran-
`dom variables x and y is computed as follows:
`
`Correlation(x; y) =
`
`E[(x x)(y y)]
`pE[(x x)2]E[(y y)2]
`
`Here, x is the mean of x. The correlation always lies
`between 1 and +1.
`
`If two bits are independent, their correlation is zero
`and the combined information of the two bits is equal
`to the sum of their individual information. On the
`other hand, if two bits are related such that one is
`always identical to the other or one is always a com-
`plement of the other, their correlation is 1, and the
`combined information content of the two bits is the
`same as that of one of the bits. Thus, when using
`several bits from the address, one should choose bits
`that have the least correlation.
`
`Bit #
`
`6
`
`47. 25000505000000005545050014100000111021321265256A
`1500050500000000555505001500000011121211135424A6
`170007070000000077670700261000000101033115444A45
`44000404000000004464040055200000213231010223A422
`0500050500000000554505001410000011111131155A3445
`060006060000000066560600042000000021113103A52456
`07000707000000007767070005200000011002212A352532
`40. 0200020200000000221202001010000011101012A2010111
`120002020000000022120200121000002111011A21111112
`13000303000000003333030003000000100110A112330313
`3300030300000000332303001210000023110A0102111321
`210001010000000011110100210000001111A01010113012
`31000101000000001101010021100000022A111100112120
`2100010100000000110101001110000010A2110111213011
`310001010000000011010100200000003A02130111011111
`32. 20000000000000000010000011000000A310121210012011
`10A0A0A0AAAAAAAA0000A0AA101AAAAA0000000000000000
`10A0A0A0AAAAAAAA0000A0AA101AAAAA0000000000000000
`10A0A0A0AAAAAAAA0000A0AA101AAAAA0000000000000000
`10A0A0A0AAAAAAAA0000A0AA101AAAAA0000000000000000
`10A0A0A0AAAAAAAA0000A0AA101AAAAA0000000000000000
`02101212111111112222121102A111110011010112212101
`1800080800000000889808004A2000001011123205445654
`24. 511011111111111122411111A40111111212210110015211
`10A1A0A0AAAAAAAA0000A0AA101AAAAA0000000000000000
`10A0A0A0AAAAAAAA0000A0AA101AAAAA0000000000000000
`1A000A0A00000000AA9A0A00182000000111133227654755
`10A0A0A0AAAAAAAA0000A0AA101AAAAA0000000000000000
`1A000A0A00000000AA9A0A00182000000111133227654755
`290009090000000099A90900492000001000123116546654
`1A000A0A00000000AA9A0A00282000000111133227654755
`16. 1A000A0A00000000AA9A0A00282000000111133227654755
`10A0A0A0AAAAAAAA0000A0AA101AAAAA0000000000000000
`10A0A0A0AAAAAAAA0000A0AA101AAAAA0000000000000000
`10A0A0A0AAAAAAAA0000A0AA101AAAAA0000000000000000
`10A0A0A0AAAAAAAA0000A0AA101AAAAA0000000000000000
`10A0A0A0AAAAAAAA0000A0AA101AAAAA0000000000000000
`10A0A0A0AAAAAAAA0000A0AA101AAAAA0000000000000000
`10A0A0A0AAAAAAAA0000A0AA101AAAAA0000000000000000
`8. 10A0A0A0AAAAAAAA0000A0AA101AAAAA0000000000000000
`1A000A0A00000000AA9A0A00182000000111133227654755
`10A0A0A0AAAAAAAA0000A0AA101AAAAA0000000000000000
`1A000A0A00000000AA9A0A00182000000111133227654755
`10A0A0A0AAAAAAAA0000A0AA101AAAAA0000000000000000
`000A00000000000000000001000000000000000000000000
`10A0A0A0AAAAAAAA0000A0AA101AAAAA0000000000000000
`1A000A0A00000000AA9A0A00182000000111133227654755
`0. A11011111111111111211111510111112323231100004112
`.
`.
`.
`.
`.
`.
`.
`0
`8
`16
`24
`32
`40
`47
`Bit #
`
`-
`
`Figure 4: Correlation among address bits.
`
`Using our trace, we measured correlation between dif-
`ferent bits. The results are shown schematically in
`Figure 4. The

gure shows a 48  48 matrix of corre-
`lation. Only the

rst digit after the decimal point is
`shown and the sign is omitted. For example, a corre-
`lation of 0.6 is shown as 6. A correlation of +1 or
`1 is shown by the letter `A.' From this

gure, we see
`that bits 1 through 31 are highly correlated to each
`other. The occurrence of `A' is limited to these bits.
`The diagonal of the correlation matrix is always `A'
`since every bit is always fully correlated with itself.
`This explains why combining the

rst 32 bits did not
`improve the information.
`
`6
`
`

`

`8
`
`7
`
`6
`
`5
`
`4
`
`3
`
`2
`
`1
`
`32
`
`8
`16
`24
` First Bit of the Sequence
`
`Figure 5: Information in CRC bits.
`
`8
`
`6
`
`4
`
`2
`
`0
`
`0
`
` Information in Bits
`
`8 Hashing Using CRC
`
`So far, we assumed that the subtable to be looked up
`be decided by extracting a few bits from the address.
`Given that in many LANs, the destination address is
`the

rst part of the frame, and the frame is passed
`through the cyclic redundancy check (CRC) circuit,
`the bits of the CRC provide another alternative for
``no cost' hashing. This scheme is, in fact, employed
`in American Micro Device's LANCE chip, used in
`many Ethernet adapters. Each station has a number
`of multicast addresses that it wants to receive. The
`adapter uses the CRC polynomial as a hash function
`to quickly reject frames with undesired multicast ad-
`dresses. The chip uses the most signi

cant 6 bits in
`the CRC shift register as an index into a 64-bit mask.
`If the 6 bits constitute an index i and the ith bit in
`the mask is set, the frame is accepted, otherwise it is
`rejected.
`
`Given an address fa0; a1; a2; . . . ; a47g, the 32-bit CRC
`of the address can be computed by forming the fol-
`lowing polynomial:
`
`6
`
`aix47i
`
`(2)
`
`47
`
`X i
`
`=32
`
`aix47i +
`
`31
`
`X i
`
`=0
`
`a(x) =
`
`and computing the remainder when the above poly-
`nomial is divided by the following CRC polynomial
`(used in IEEE802 protocols):
`
`g(x) = x32 + x26 + x23 + x22 + x16 + x12 + x11 +
`x10 + x8 + x7 + x5 + x4 + x2 + x + 1
`
`The coecient of the remainder polynomial can be
`used as a hashing function. Notice that in Equation
`2, the

rst 32 bits of the address are complemented.
`For details of this process see [12,8]. Although, an al-
`gebraic description of CRC computation as presented
`above sounds tedious, its hardware implementation
`using shift registers is straightforward.
`
`The LANCE chip uses the most signi

cant 6 bits of
`the CRC as a hashing function. We are interested
`in

nding out how well this hashing function works
`and if we can extend it to more bits. To do this, we
`computed the information content of m-bit sequences
`consisting of bits i through i+m1 of the 32-bit CRC
`for m = 1, 2, . . . , 8, and i = 0, 1, . . . , 31. Again,
`i = 0 represents the most signi

cant bit of the CRC.
`The results are shown in Figure 5.
`
`It is interesting to compare Figures 3 and 5. Notice
`the following:
`
`31. 1000210011113001100111001412221A
`101012011101111101200021111121A1
`00211211110110301312131100110A12
`1111120203112311220110110110A022
`011121122111100001112020110A0112
`12021111121121101011000221A01111
`0001320000113102001012010A111014
`24. 220121212201112211010211A0210011
`12111012112301000031111A11201110
`1110011110000220230100A110021120
`032211013022015212201A0122000301
`21330121102201101021A10101021101
`1011001100010201121A101110111201
`132121200131101001A1220301110120
`21002011222110322A12023010012310
`16. 1213112011010211A201112010102101
`211110100020130A1201020022001011
`10111101302120A01310152020101310
`1320000102012A032002112111103010
`110030201210A2210110000013212113
`11131311000A01101111220311111111
`2112011012A010220230220201111001
`102001221A2022001210000120213111
`8. 10111010A11010301200131120120111
`0411120A020101100101111210122110
`412110A0121120012121201120110100
`22101A02011300101010111012112221
`1101A111100130111220010123121112
`002A1011102300113011320111211100
`22A20121121102111021321100011210
`1A201214001113012130131220211000
`0. A1201240112111121211201120101011
`.
`.
`.
`.
`.
`0
`8
`16
`24
`31
`Bit #
`
`-
`
`Figure 6: Correlation among CRC bits.
`
`Bit #
`
`7
`
`

`

`8
`
`7
`
`6
`
`5
`
`4
`
`3
`
`2
`
`1
`
`4
`8
`12
` First Bit of the Sequence
`
`16
`
`8
`
`6
`
`4
`
`2
`
`0
`
`0
`
` Information in Bits
`
`Figure 7: Information in Fletcher checksum bits.
`
`Fletcher's procedure is more general than that de-
`scribed above in the sense that the checksum can be
`more than two octets long. However, OSI transport
`uses a two-octet checksum, which is what we analyze
`here. We computed the the information in m con-
`secutive bits of address checksums. The results are
`shown in Figure 7.
`
`From the

gure we observe that each of the 16 bits
`individually have one bit of information and that the
`information content of m bits is approximately m.
`This is, therefore, also a good hashing function.
`
`The correlation among the bits of the Fletcher check-
`sum is shown in Figure 8. Notice that the correlation
`is small.
`
`10 Hashing Using Another Checksum
`
`Another popular checksum algorithm used to guard
`against memory errors in network address databases
`is [9]:
`
`C = M od 28(4b[1] + 2b[3] + b[5])+
`(4b[2] + 2b[4] + b[6]); 216 1
`
`Here, b[i] is the ith octet of the address and C is
`the 16-bit checksum. Since we are not aware of its
`name, we will call it the `mod-checksum.' The infor-
`mation content of the bits of this checksum are shown
`
`8
`
`1. Almost all 32 bits have a high information con-
`tent very close to one bit. Thus, it does not
`matter which bit of the CRC we use.
`
`2. All curves are (almost) horizontal straight lines.
`Thus, the information content of all bit combi-
`nations is identical. It does not matter which
`m bits are chosen for m = 1, 2, ...
`
`3. The information content of m bits is approxi-
`mately m. This means that CRC provides an
`almost optimal hashing function.
`
`4. The curve for m = 8 is not so straight, but
`this is expected since we had only 296 dis-
`tinct destination addresses and, thus, the to-
`tal information content of the trace itself is
`log2(296) = 8:21 bits.
`
`We also computed the correlation among CRC bits.
`The results are shown in Figure 6. As discussed ear-
`lier, only the

rst decimal digit of the correlation is
`shown. Notice that the correlation is very low and
`that occurrence of `A' is limited to the diagonal. This
`once again con

rms the conclusion that CRC is an
`excellent hashing function.
`
`We repeated the analysis with several other 8-bit and
`16-bit CRC polynomials. In general, we found that
`if a polynomial provides a good CRC, it can serve as
`an excellent hash function.
`
`9 Hashing Using Fletcher Checksum
`
`One problem with CRC is that its computation in
`software is complex (unless we use a tabular method,
`for example, that described in [24]). The ISO/OSI
`transport uses a checksum instead of CRC since it
`is so easy to compute in software. Although the
`checksum became widely known only after Fletcher
`proposed and analyzed it [5], it was discussed earlier
`by Samoylenko [26]. For a discussion on implement-
`ing it eciently see [29]. Given an n-octet message
`b[1]...b[n], a two-octet checksum C[0] and C[1] is com-
`puted as follows:
`
`C[0] = 0; C[1] =0;
`For i = 1 step 1 until n do
`C[0] = C[0] + b[i];
`C[1] = C[1] + C[0];
`EndFor;
`
`

`

`78
`
`6
`
`5
`
`4
`
`3
`
`2
`
`1
`
`4
`8
`12
` First Bit of the Sequence
`
`16
`
`8
`
`6
`
`4
`
`2
`
`0
`
`0
`
` Information in Bits
`
`Figure 9: Information in mod-checksum bits.
`
`Bit #
`
`6
`
`15. 320012111101102A
`21200121012202A2
`0143001001001A20
`110123132111A101
`00113022013A1021
`0114000210A31020
`231100113A011111
`8. 11101212A3102001
`1210031A21223011
`021100A111021121
`10111A0320003012
`2112A10010032001
`011A211001411300
`21A1111111110420
`2A11102213101112
`0. A220210112001023
`.
`.
`.
`0
`8
`15
`Bit #
`
`-
`
`Figure 8: Correlation among bits of the Fletcher
`checksum.
`
`in Figure 9. Comparing this

gure with that for the
`Fletcher checksum, we

nd that the mod-checksum is
`not as good a hashing function as the Fletcher check-
`sum even though it is more complex to compute. The
`key lesson is that complexity does not necessarily get
`us better performance.
`
`The correlation among the bits of mod-checksum is
`shown in Figure 10.
`
`11 Hashing Using XOR Folding
`
`The

nal alternative that we investigated is that of
`the straightforward exclusive-or operation on the six
`octets of the address to produce 8 bits.
`
`6
`
`15. 201112022121101A
`42220121211132A1
`2101010122102A20
`021101105423A231
`02210112112A3011
`0111101044A22112
`131120216A414211
`8. 11111010A6415222
`2110202A01020112
`100201A212111020
`10010A1000011112
`1110A00212100001
`110A012011111121
`13A0100111121021
`1A31100113122120
`0. A111111211000242
`.
`.
`.
`0
`8
`15
`Bit #
`
`-
`
`Figure 10: Correlation among bits of mod-checksum.
`
`C = b[1]  b[2]  b[3]  b[4]  b[5]  b[6]
`
`Bit #
`
`The information content and correlation of the bits
`in the `XOR-fold' so obtained are shown in Figures
`11 and 12, respectively. To our surprise, this func-
`tion, which is so simple to implement, is an excellent
`hashing function.
`In software, the folding may be
`preferable to Fletcher's checksum if exclusive-or op-
`erations take less time than additions. Implementing
`folding in hardware is simpler than CRC.
`
`It should be pointed out that XOR-folding can be
`done with any number of bits. For example, a 11-bit
`fold can be obtained by dividing each 48-bit address
`in to

ve segments of which four are 11-bit long and
`
`9
`
`

`

`in several commercial media access controller (MAC)
`chips. Such a hash

lter is a perfect rejection

lter
`in the sense that if the mask bit is zero, we can be
`certain that the address is not wanted, and there is