Page 301 - DCAP403_Operating System

Operating System

Notes be translated and removed as they become stale over time. Each arp_table data structure has the
following fi elds:
last used the time that this ARP entry was last used,
last updated the time that this ARP entry was last updated,
flags these describe this entry’s state, if it is complete and so on,

IP address The IP address that this entry describes
hardware address The translated hardware address
hardware header This is a pointer to a cached hardware header,
timer This is a timer_list entry used to time out ARP requests that do not get a
response,
retries The number of times that this ARP request has been retried,
sk_buff queue List of sk_buff entries waiting for this IP address to be resolved
The ARP table consists of a table of pointers (the arp_tables vector) to chains of arp_table entries.
The entries are cached to speed up access to them, each entry is found by taking the last two bytes
of its IP address to generate an index into the table and then following the chain of entries until
the correct one is found. Linux also caches prebuilt hardware headers off the arp_table entries in
the form of hh_cache data structures.
When an IP address translation is requested and there is no corresponding arp_table entry, ARP
must send an ARP request message. It creates a new arp_table entry in the table and queues the
sk_buff containing the network packet that needs the address translation on the sk_buff queue of
the new entry. It sends out an ARP request and sets the ARP expiry timer running. If there is no
response then ARP will retry the request a number of times and if there is still no response ARP
will remove the arp_table entry. Any sk_buff data structures queued waiting for the IP address

to be translated will be notified and it is up to the protocol layer that is transmitting them to cope
with this failure. UDP does not care about lost packets but TCP will attempt to retransmit on
an established TCP link. If the owner of the IP address responds with its hardware address, the
arp_table entry is marked as complete and any queued sk_buff’s will be removed from the queue
and will go on to be transmitted. The hardware address is written into the hardware header of
each sk_buff.

The ARP protocol layer must also respond to ARP requests that specfy its IP address. It registers
its protocol type (ETH_P_ARP), generating a packet_type data structure. This means that it will
be passed all ARP packets that are received by the network devices. As well as ARP replies,
this includes ARP requests. It generates an ARP reply using the hardware address kept in the
receiving device’s device data structure.

Network topologies can change over time and IP addresses can be reassigned to different
hardware addresses. For example, some dial up services assign an IP address as each connection
is established. In order that the ARP table contains up to date entries, ARP runs a periodic timer
which looks through all of the arp_table entries to see which have timed out. It is very careful not
to remove entries that contain one or more cached hardware headers. Removing these entries is
dangerous as other data structures rely on them. Some arp_table entries are permanent and these
are marked so that they will not be deallocated. The ARP table cannot be allowed to grow too
large; each arp_table entry consumes some kernel memory. Whenever the a new entry needs to
be allocated and the ARP table has reached its maximum size the table is pruned by searching out
the oldest entries and removing them.

13.9.7 IP Routing

The IP routing function determines where to send IP packets destined for a particular IP address.
There are many choices to be made when transmitting IP packets. Can the destination be reached
at all? If it can be reached, which network device should be used to transmit it? If there is more
than one network device that could be used to reach the destination, which is the better one? The

294 LOVELY PROFESSIONAL UNIVERSITY