Page 302 - DCAP403_Operating System

Unit 13: Case Study: Linux

IP routing database maintains information that gives answers to these questions. There are two Notes
databases, the most important being the Forwarding Information Database. This is an exhaustive
list of known IP destinations and their best routes. A smaller and much faster database, the route
cache is used for quick lookups of routes for IP destinations. Like all caches, it must contain
only the frequently accessed routes; its contents are derived from the Forwarding Information
Database.

Routes are added and deleted via IOCTL requests to the BSD socket interface. These are passed
onto the protocol to process. The INET protocol layer only allows processes with superuser

privileges to add and delete IP routes. These routes can be fixed or they can be dynamic and

change over time. Most systems use fixed routes unless they themselves are routers. Routers run
routing protocols which constantly check on the availability of routes to all known IP destinations.
Systems that are not routers are known as end systems. The routing protocols are implemented
as daemons, for example GATED, and they also add and delete routes via the IOCTL BSD socket
interface.

Route Cache

Whenever an IP route is looked up, the route cache is first checked for a matching route. If there

is no matching route in the route cache the Forwarding Information Database is searched for a
route. If no route can be found there, the IP packet will fail to be sent and the application notifi ed.
If a route is in the Forwarding Information Database and not in the route cache, then a new entry
is generated and added into the route cache for this route. The route cache is a table (ip_rt_hash_
table) that contains pointers to chains of rtable data structures. The index into the route table is a
hash function based on the least significant two bytes of the IP address. These are the two bytes

most likely to be different between destinations and provide the best spread of hash values.
Each rtable entry contains information about the route; the destination IP address, the network
device to use to reach that IP address, the maximum size of message that can be used and so on.
It also has a reference count, a usage count and a timestamp of the last time that they were used

(in jiffies). The reference count is incremented each time the route is used to show the number
of network connections using this route. It is decremented as applications stop using the route.
The usage count is incremented each time the route is looked up and is used to order the rtable
entry in its chain of hash entries. The last used timestamp for all of the entries in the route cache
is periodically checked to see if the rtable is too old. If the route has not been recently used, it is
discarded from the route cache. If routes are kept in the route cache they are ordered so that the
most used entries are at the front of the hash chains. This means that finding them will be quicker

when routes are looked up.
Forwarding Information Database

The forwarding information database (shown in Figure 13.16 contains IP’s view of the routes
available to this system at this time. It is quite a complicated data structure and, although it is
reasonably efficiently arranged, it is not a quick database to consult. In particular it would be very

slow to look up destinations in this database for every IP packet transmitted. This is the reason
that the route cache exists: to speed up IP packet transmission using known good routes. The
route cache is derived from the forwarding database and represents its commonly used entries.
Each IP subnet is represented by a fi b_zone data structure. All of these are pointed at from the
fib_zones hash table. The hash index is derived from the IP subnet mask. All routes to the same

subnet are described by pairs of fi b_node and fib_info data structures queued onto the fz_list of
each fi b_zone data structure. If the number of routes in this subnet grows large, a hash table is
generated to make fi nding the fib_node data structures easier.

LOVELY PROFESSIONAL UNIVERSITY 295