IP (logical) addresses are assigned independently from physical (hardware) addresses. The logical address is called a 32-bit IP address, and the physical address is a 48-bit MAC address in Ethernet and token ring protocols.

The delivery of a packet to a host or a router requires two levels of addressing, such as logical (IP) address and physical (MAC) addresses. When a host or a router has an IP datagram forwarding to another host or router, it must know the logical IP address of the receiver.

Since the IP datagram is encapsulated in a form to be passed through the physical network (such as a LAN), the sender needs the physical MAC address of the receiver. Mapping of an IP address to a physical address can be done by either static or dynamic mapping.

Static mapping means creating a table that associates an IP address with a physical address. But static mapping has some limitations because table lookups are inefficient. As a consequence, static mapping creates a huge overhead on the network.

Dynamic mapping can employ a protocol to find the other. Two protocols (ARP and RARP) have been designed to perform dynamic mapping. When a host needs to find the physical address of another host or router on its network, it sends an ARP query packet.

The intended recipient recognises its IP address and sends back an ARP response which contains the recipient IP and physical addresses. An ARP request is broadcast to all devices on the network, while an ARP reply is unicast to the host requesting the mapping. Figure below shows an example of simplified ARP dynamic mapping.

Let a host or router call a machine. A machine uses ARP to find the physical address of another machine by broadcasting an ARP request. The request contains the IP address of the machine for which a physical address is needed. All machines (M1, M2, M3, . . .) on the network receive an ARP request.

If the request matches a M2 machine’s IP address, the machine responds by sending a reply that contains the requested physical address. Note that Ethernet uses the 48-bit address of all 1’s (FFFFFFFFFFFF) as the broadcast address. A proxy ARP is an ARP that acts on behalf of a set of hosts.

Proxy ARP can be used to create a subnetting effect. In proxy ARP, a router represents a set of hosts. When an ARP request seeks the physical address of any host in this set, the router sends its own physical address. This creates a subnetting effect.

Whenever looking for the IP address of one of these hosts, the router sends an ARP reply announcing its own physical address. To make address resolution easy, choose both IP and physical addresses the same length.

Address resolution is difficult for Ethernet-like networks because the physical address of the Ethernet interface is 48 bits long and the high-level IP address is 32 bits long. In order for the 48-bit physical address to encode a 32-bit IP address, the next generation of IP is being designed to allow 48-bit physical (hardware) addresses P to be encoded in IP addresses I by the functional relationship of P = f (I).

Conceptually, it will be necessary to choose a numbering scheme that makes address resolution efficient by selecting a function f that maps IP addresses to physical addresses. As shown in Figure below, the ARP software package consists of the following five components:

• The cache table has an array of entries used and updated by ARP messages. It is inefficient to use the ARP protocol for each datagram destined for the same host or router. The solution is to use the cache table. The cache table is implemented as an array of entries.

When a host or router receives the corresponding physical address for an IP datagram, the address can be saved in the cache table within the next few minutes. However, mapping in the cache should not be retained for an unlimited time, due to the limited cache space.

• A queue contains packets going to the same destination. The ARP package maintains a set of queues to hold the IP packets, while ARP tries to resolve the physical address. The output module sends unresolved packets to the corresponding queue. The input module removes a packet from a queue and sends it to the physical access layer for transmission.

• The output module takes an IP packet from the IP layer and sends it to a queue as well as the physical access layer. The output module checks the cache table to find an entry corresponding to the destination IP address of this packet.

If the entry is found and the state of the entry is resolved, the packet, along with the destination physical address, is passed to the physical access layer (or data link layer) for transmission. If the entry is found and the state of the entry is pending, the packet should wait until the destination physical address is found.

If no entry is found, the module creates a queue and enqueues the packet. A new cache entry (‘pending’) is created for the destination and the attempt field is set to 1. An ARP request is then broadcast.

• The input module waits until an ARP request or reply arrives. The input module checks the cache table to find an entry corresponding to this packet (request or reply).

If the entry is found and the state of the entry is ‘pending’, the module updates the entry by copying the target physical address in the packet to the physical address field of the entry and changing the state to ‘resolved’.

The module also sets the value of the time-out for the entry and then dequeues the packets from the corresponding queue, one by one, and delivers them along with the physical address to the physical access layer for transmission.

If the entry is found and the state is ‘resolved’, the module still updates the entry. This is because the target physical address could have been changed. The value of the time-out field is also reset. If the entry is not found, the module creates a new entry and adds it to the cache table.

Now the module checks to see if the arrived ARP packet is a request. If it is, the input module immediately creates an ARP reply message and sends it to the sender. The ARP reply packet is created by changing the value of the operation field from request to reply and filling in the target physical address.

• The cache-control module is responsible for maintaining the cache table. It checks the cache table periodically, entry by entry. If the entry is free, it continues to the next entry. If the state is ‘pending’, the module increments the value of the attempts field by 1.

It then checks the value of the attempts field. If this value is greater than the maximum number of attempts allowed, the state is changed to ‘free’ and the corresponding queue is destroyed. However, if the number of attempts is less than the maximum, the input module creates and sends another ARP request.

If the state of the entry is ‘resolved’, the module decrements the value of the ‘time-out’ field by the amount of the time elapsed since the last check. If this value is less than or equal to zero, the state is changed to free and the queue is destroyed.