## CS610 Assignment 4 Idea Solution July 2010

a. What is hashing? Does it belong to Address Resolution Techniques?
Hashing means using a smaller table to contain data from what might have been a huge table. It is used to decrease the amount of needed space while keeping it almost as fast as normal random access addressing. It is mainly used when a random access table would be sparse.

An example would be, you have blocks of data which have parameter X and parameter Z as their address. Both X and Z can be from 0 to 99. So all in all there are 10000 possible combination. But let's say you only need to store 100 such blocks at any given time on the average. Setting up a normal table (and storing each block in position [100*X+Y] ) would take the space of 10000 entries which sucks even if they are pointers.

So what you do instead, is make a hash table of say, 50 entries. Each block is stored in the position [(100*X+Y) modulo 50]. The new position is a HASH of the old straightforward one. In each position in the small table, there is a list, so you can store more than one entry there. Now when you need to access a block or check if such a block exists, you do the hash and go on the list until you find the block.
.
The hashing algorithm is called the hash function (and probably the term is derived from the idea that the resulting hash value can be thought of as a "mixed up" version of the represented value). In addition to faster data retrieval, hashing is also used to encrypt and decrypt digital signatures (used to authenticate message senders and receivers). The digital signature is transformed with the hash function and then both the hashed value (known as a message-digest) and the signature are sent in separate transmissions to the receiver. Using the same hash function as the sender, the receiver derives a message-digest from the signature and compares it with the message-digest it also received. They should be the same.

The hash function is used to index the original value or key and then used later each time the data associated with the value or key is to be retrieved. Thus, hashing is always a one-way operation. There's no need to "reverse engineer" the hash function by analyzing the hashed values. In fact, the ideal hash function can't be derived by such analysis. A good hash function also should not produce the same hash value from two different inputs. If it does, this is known as a collision. A hash function that offers an extremely low risk of collision may be considered acceptable.
Yes it belongs to Address Resolution Techniques it contains Table look up (e.g WAN) Closed-form computation and Message Exchange.

b. Differentiate among all Address Resolution Techniques in a tabular format

The mechanism for performing address resolution depends on the protocol and hardware addressing schemes. However, there are three basic categories

cs610.jpg

TCP/IP can use any of the three address resolution methods and uses the Address Resolution Protocol (ARP) to ensure that all hosts use a common format for requests and responses. A request message contains an IP address and requests the corresponding hardware address; a reply message contains both the IP address and the corresponding hardware address