Link Layer Protocols


Address Resolution Protocol (ARP)

Address Resolution Protocol is a mechanism that dynamically maps an IP address to the hardware (MAC) address of a network host. If a host computer on a LAN wants to send data to another host computer on the same LAN, it can do so using the hardware address of the destination computer. If it wants to send data to a host on another network, however, it must address a datagram to the target machine's IP address, and send it to the LAN's gateway router using the local datalink layer protocol (Ethernet, for example).

The router on the destination network has the task of delivering the datagram, but in order to do so it must determine the hardware address of the target machine. To achieve this, it broadcasts an ARP request packet to all hosts on the network, which includes both the target IP address and the IP address of the router, together with the router's hardware address. The host that recognises the target IP address as its own sends a reply to the router that includes its hardware address. The router then encapsulates the datagram using the local datalink layer protocol, and transmits the resulting frame to the target hardware address. If the target machine fails to respond to the ARP request packet, or the packet is lost, the router waits briefly, and then tries again. The ARP messages themselves are encapsulated using the local datalink layer protocol. On an Ethernet network, for example, the frame containing the ARP message will contain a value in the type field indicating that it carries an ARP message. Any TCP/IP host on a LAN can use ARP to dynamically determine the hardware address of an intended recipient on the same LAN.


An ARP packet encapsulated in an Ethernet Frame

An ARP packet encapsulated in an Ethernet Frame


To reduce the number of ARP request packets traversing the network, a host computer caches previously used hardware addresses for a short period of time, and will search the cache for a stored address before sending further requests. If a current entry is found, the host sends the datagram using the stored address. If not, it broadcasts an ARP request. Because the size of the cache is limited, it is periodically flushed to delete old entries and make room for new ones. The layout of the ARP cache is shown below.


The layout of the ARP cache

The layout of the ARP cache


The following descriptions summarise the fields in the cache entries:

ARP processes operate on all computers using IP over Ethernet, and are normally implemented as part of the NIC driver software. An ARP message can be one of two types - ARP request or ARP reply. The message type is identified by the Operation field in an ARP message, the format of which is shown below.


The ARP nessage format

The ARP nessage format


In an ARP request, all the fields are used except the Recipient Hardware Address field. In an ARP reply, all the fields are used. The fields and their functions are listed below.

The following diagram shows how ARP interacts with ICMP when a user pings another host computer on the same LAN, assuming no IP datagrams have been received from that computer recently. ARP is used to obtain the MAC address of the remote host.


ARP working with ICMP

ARP working with ICMP


The ARP request message "who is x.x.x.x tell y.y.y.y", where x.x.x.x and y.y.y.y are IP addresses, is broadcast to all computers on the same LAN. If the target host is connected to the network, it will receive a copy of the ARP request message and send a reply (the other systems simply discard the packet). The reply takes the form "x.x.x.x is hh:hh:hh:hh:hh:hh", where hh:hh:hh:hh:hh:hh is the hardware address of the target host.


Open Shortest Path First (OSPF)

Open Shortest Path First (OSPF) is an interier link-state routing protocol developed for IP networks, and is based on the shortest path first (SPF) algorithm. Routers within the same hierarchical area send each other link-state advertisements (LSAs) containing information about their attached interfaces, and the metrics used. They use this information together with the SPF algorithm to calculate the shortest path to each node. OSPF can operate within a hierarchy, usually an internetwork with a single administration and a common routing strategy. This routing domain (or autonomous system) can be split into a number of areas. Routers with a connection to two or more areas are called area border routers, and maintain a separate topological databasefor each area.

The database holds the information extracted from link-state advertisements received from other routers in the same area. Because the routers share the same information, they have identical databases. OSPF uses either intra-area routing (if the source and destination are in the same area), or inter-area routing (if they are in different areas). Routing information is distributed through the OSPF backbone, which consists of all area border routers and any other routers to which they are connected that do not reside within a specific area. In the diagram below, the backbone consists of routers 4-6, and 10-12. If host H1 wants to send a packet to H2, the packet is sent to router 12 via intra-area router 13, then along the backbone to area border router 10 via router 11. Router 10 forwards the packet to H2 via intra-area routers 9 and 7. Border routers running OSPF learn about external routes using an exterior routing protocol such as Border Gateway Protocol (BGP).


Routing areas

Routing areas


When a router is powered up, it "acquires" neighbors (routers to which it has a connection) by exchanging Hello messages with them. Neighbouring routers continue to exchange these messages to let let each other know that they are still functional. On networks supporting more than two routers, a designated router is elected, and takes responsibility for generating link-state advertisements, which are exchanged only between adjacent (neighbouring) routers.


OSPF packet format

OSPF packet format


All OSPF packets employ a 24-byte header (see above). The header fields are described below.