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.

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 following descriptions summarise the fields in the cache entries:

• IF Index - the physical port (interface)
• Physical Address - the physical address of the device
• IP Address - the IP address corresponding to the physical address
• Type - the type of entry in the ARP cache

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.

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.

• Hardware Type - the type of hardware interface (for example, Ethernet = Type 1)
• Protocol Type - the type of protocol the sending device is using (for example, IPv4 = 0x0800)
• Hardware Address Length - the length (in bytes) of each hardware address in the datagram
• Protocol Address Length - the length (in bytes) of the protocol address in the datagram
• Operation Code (Opcode) - indicates whether a datagram is an ARP request (1) or an ARP reply (2)
• Sender Hardware Address - the hardware address of the sending device
• Sender IP Address - the IP address of the sending device
• Target Hardware Address - the hardware address of the recipient
• Target IP Address - the IP Address of the recipient

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.

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).

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.

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

• Version number - identifies the OSPF version used
• Type - identifies the OSPF packet type as one of the following:
  • Hello - establishes and maintains neighbor relationships
  • Database description - describes the contents of the topological database
  • Link-state request - requests updated link-state information from a neighbour router
  • Link-state update - contains one or more link state advertisements
  • Link-state acknowledgment - acknowledges a link-state update
• Packet length - specifies the packet length, including the header, in bytes
• Router ID - identifies the source of the packet
• Area ID - identifies the area to which the packet belongs
• Checksum - checks the contents of the packet for errors
• Authentication type - contains the authentication type
• Authentication - contains the authentication information
• Data - contains encapsulated upper-layer information