Routing in an Intranet, a Basic Introduction

Why Should I Know About Routing

When any application sends messages across the network the messages are sent to their destination via other networks and routers. It is vitally important for any network manager to be aware how their networks are operating. They must know where different types of traffic go, through which routers and which other networks, so that they can effectively organise their network topology and keep the network running at peak performance levels. By understanding the way their networks operate they can redeploy equipment and cater for specific needs. In this article I talk about the two most commonly used Intranet routing protocols, RIP and OPSF.

What is a Routing Protocol

When a computer is turned on it uses routing information that is specified in .some configuration file to be able to initiate communication with other computers. This information is known as static routing information. In this article I concentrate on dynamic routing. This is the routing data that is constantly changing. Routers send dynamic routing information to other routers in order to find the best (cheapest, fastest etc.) paths to other routers and networks. This routing information is used whenever any messages are sent across the net.

Across the Internet there are two basic types of dynamic routing protocols in use. The first of these is known as an interior gateway protocol (an IGP) and the second is known as an exterior gateway protocol (an EGP, not to be confused with the particular protocol of the same name) or an interdomain routing protocol.

Interior and Exterior Protocols

Interior gateway protocols are used between routers within an autonomous system (AS). An autonomous system is usually a company or organisation that is administered by a single entity. The entire Internet can be thought of as a set of autonomous systems. Exterior gateway protocols are used to communicate routing information between autonomous systems.

Each autonomous system can use whichever interior gateway protocol they choose. There are two such protocols that are in common use. RIP, Routing Information Protocol and OPSF, Open Shortest Path First.

RIP - Routing Information Protocol

RIP, Routing Information Protocol, is the most widely used interior protocol. Early versions of RIP were in use in the first versions of Unix that provided networking software. The initial implementations of RIP predate the RFC (RFC 1058) that defines the protocol. RIP is intended to allow routers to exchange information for computing routes through networks.

One of the most important pieces of information exchanged between RIPs is what is known as the metric. Metrics are described below but can be considered as a cost associated with sending a message to a destination. Each RIP message essentially contains a list of destination and metric pairs. A RIP that receives such a message knows that to reach a particular destination the cost is the associated metric. RIP uses UDP (User Datagram Protocol) as an underlying transport layer.

A RIP message is made up of a header, which is 4 bytes followed by up to 25 routes (destination, metric pairs) each 20 bytes long. So an entire RIP message can be at most 504 (4+ (20x25)) bytes long. The header of a RIP message contains a command field, a version field and 2 byte field of zeros.

The command field can have one of the following values:

1 - request A request for the responding system to send all or part of its routing table.

2 - reply A message containing all or part of the sender's routing table. This message may be sent in response to a request, or it may be an unsolicited routing update generated by the sender.

3 - traceon This is an obsolete command. Messages containing this command are to be ignored.

4 - traceoff This is another obsolete command. Messages containing this command are to be ignored.

5 - poll This is an undocumented command. It was originally meant to be reserved for Sun Microsystems for its own purposes.

6 - poll-entry This is another undocumented command.

The version field of a RIP header is 1 for the version of RIP I am discussing here. I will note some changes implemented in version 2 of RIP below.

The rest of the RIP message is a list of route entries. Each route entry in this list contains an address family identifier, destination address and the cost to reach that address - the metric. As well as this there are several fields of zeros. The value of the address family is always 2 for Internet Protocol addresses. The destination address field is a standard 32 bit IPv4 address. The RIP metric field is an integer between 1 and 15, inclusive (16 is used to indicate there is no route). This value of this metric is not specified by the protocol itself but is usually implemented as the number of routers that a message must pass through to reach a network. Any network directly connected to a router usually has a metric of 1. Note, however, it is possible to set a different values for metrics. Different values would be used to show preference for some networks over others (for example to indicate differences in reliability or bandwidth).

The Routing Table

RIP running on a router stores destination, metric pairs in a routing table. The metric for a particular destination in a routing table is the sum of all metrics associated with the networks that must be traversed to get to that destination. It is, essentially, a sum of costs. In a network where routers directly connected to networks all have a metric of 1, this will simply be the sum of the number of hops required to get from the router to the destination.

To be more complete, the routing table has entries with the following fields:

The IP address of the destination.
A metric.
The 32 bit IPv4 address of the next gateway along the path to the destination.
A flag to indicate that information about the route has changed recently. This is called the "route change flag".
Timers associated with the route. These timers indicate when routing tables should be sent to neighbouring routers and when updates should be expected from neighbouring routers.

RIP Sequence of Events

RIP has five states.

Initialisation When RIP starts it determines all interfaces on the router that are active and sends a request message out each interface asking for the next routers complete routing table. This is a special request, the address family field is set to 0 and the metric is set to 16.

Request Received If the request is a special request (as described above) then the entire routing table is sent to the requestor. Otherwise each entry in the request is processed.

Response Received The response is validated (by checking that the values of the fields make sense, for example that the family identifier is 2). Once validated the response may update existing entries in the routing table or may cause a new entry to be added.

Send Regular Update Every 30 seconds all or part of the routers entire routing table is sent to neighbouring routers.

Send Triggered Update Whenever a metric for a route changes that route is sent to neighbouring routers.

RIP Version 2

Version 2 of RIP extends RIP version 1. It addresses some issues that have become relevant since version 1 RIPs were implemented and some issues that were left out of RIP version 1. The extensions to the protocol define new fields in a RIP message. These new fields are placed in fields that were 0 in RIP version 1 messages. Providing that RIP version 1 implementations do not try to validate the fields of zeros, RIP 1 and RIP 2 can coexist on the same network.

The new fields added by RIP version 2 are:

Routing Domain This is a field in the RIP header. The value placed in here allows routes to belong to some logical domain. It means that multiple instances of the routing program can be run for different logical domains.

Authentication A simple authentication mechanism has been set into place with RIP version 2. If the first 2 bytes of the message (after the header) has an address family field with the value 0xffff and the route tag field has a value of 2 then the remaining 16 bytes of that route entry contain a cleartext password.

Route Tag This field is simply an attribute assigned to a route somehow indicating the source of the route. It is intended to provide a method of separating internal routes with routes obtained from external sources (some EGP).

Subnet Mask This field contains the subnet mask which is applied to the IP address.

Next Hop This field indicates the immediate next hop IP address to which messages specified by this route should be sent.

RIP Authentication

One of the main areas where RIP is likely to be extended is in the security area. There is a current Internet Draft (draft-ietf-ripv2-md5-auth-00.txt, Baker, January 1997) that recommends encrypting RIP messages. The main problem with non encrypted messages is that hostile processes on the network can intercept RIP and RIPv2 messages and overcome the network.

RIP Limitations

Most of the limitations of RIPv1 have been addressed in RIPv2 (such as lack of subnetting). There are still, however, some problems with the RIP protocol in general. The limit of 15 for the metric is particularly constraining. If the metric is used as a hop count (only using a metric of 1 for a directly attached network) it is bad enough, but if administrators use higher numbers for the metric then this is an extremely limiting factor. The other main problem with RIP is that it takes a long time to stabilise after some network change. During this period of instability routing loops can occur.

OSPF, Open Shortest Path First

OSPF (Open Shortest Path First) is another interior gateway protocol. It is newer than RIPv1 and addresses some of the limitations of RIP. It is designed in a totally different way to RIP. Whereas RIP is what is known as a distance vector protocol (RIP messages contain a list, or vector, of address and metric, or distance, pairs) OSPF is a link state protocol.

The way that this link state method works in OSPF is that each router actively tests the state of its links. It then sends information about itself (about the state of its links) to its neighbours which propagate this information throughout the autonomous system. Each router maintains a database describing the autonomous system's topology which is updated by these link state messages. Every router's topological database is identical. Each individual element of this database is information about a particular router's local state, for example it's usable interfaces and reachable neighbours. With this database, each router can easily find the shortest path from itself to a destination. If there are several routes to a destination of equally short length, then OSPF distributes traffic equally among the routes. This is known as load balancing. Figure 4 shows what could be typical corporate network, with six routers and 7 networks. Each link in the network is assigned some value. In this example there is only one value assigned per link, however there could just as easily be a separate value for each direction of the link. Figure 5 shows the network from the point of view of one of the routers, Router 2. This figure is in the form of a tree. In this tree there is only one path from Router 2 to any other router or network.

Another key aspect of OSPF is that it can assign a metric to a type of service as well as to an interface. This means that certain services can be made to traverse particular routes. This flexibility is a huge advantage over other routing protocols - major arteries of the network can be guaranteed to be unclogged by certain types of traffic. Other, say critical, types of traffic can be made to traverse particularly reliable routes. In figures 4 and 5 I have only shown a single metric per link, for simplicity, but there could be several, one for each type of service.

How Does OSPF Work

When an OSPF router starts up it first checks that its interfaces are up and running. This is done by the lower level protocols. Once it has determined which interfaces are up it sends out packets to neighbouring routers. On networks that support it the router sends packets to a designated multicast address, otherwise it needs some configuration information to know where neighbouring routers are. When communication has been established with other routers, OSPF forms what are called adjacencies. An adjacency is a relationship with a neighbouring router for the sake of sharing information. This is done so that OSPF messages (usually) only have to travel one hop, to the next router. After adjacencies are formed, OSPF routers synchronise topological databases. It is very important for all routers' topological databases to stay synchronised. OSPF simplifies the synchronisation process by only requiring adjacent routers to remain synchronised. Periodically a router will advertise its state, which is called its link state. The link state is also advertised whenever the router's state changes.

One of the most interesting aspects of OSPF is that it doesn't use TCP or UDP as a transport layer. It defines its own transport mechanism.

OSPF Authentication

OSPF version 2 supports cleartext passwords similar to RIPv2 cleartext passwords. As with RIP there is also an internet draft for OSPF authentication. This draft (draft-murphy-ospf-signature-03.txt, March 1997) describes the extensions to OPSF required to add digital signature authentication to link state data and to provide a certification mechanism for router data.

Conclusion

OSPF is a much more flexible protocol than RIP, the fact that it can route messages based on the type of service is a major win. The downside, however, is that like anything that is more flexible, it is more complicated to implement and more difficult to maintain. RIP although not as versatile as OPSF, especially in the face of network changes, is easier to implement (which means less bugs in the implementation). As well as this, RIP has less overhead in terms of management and configuration time and bandwidth.