IP Routing

 Routing is the technique by which data finds its way from one host computer to another.

  In the Internet context there are three major aspects of routing

    1. Physical Address Determination: This is necessary when an IP datagram is to be transmitted from a computer. It is necessary to encapsulate the IP datagram within whatever frame format is in use on the local network or networks to which the computer is attached. This encapsulation clearly requires the inclusion of a local network address or physical address within the frame.
    2. Selection of Internetwork Gateways: This is necessary because the Internet consists of a number of local networks interconnected by one or more gateways. Such gateways, generally known as routers, sometimes have physical connections or ports onto many networks. The determination of the appropriate gateway and port for a particular IP datagram is called routing and also involves gateways interchanging information in standard ways.
    3. Symbolic and Numeric Addresses: This aspect involves address translation from a reasonably human friendly form to numeric IP addresses is performed by a system known as the Domain Name System or DNS for short.

 

The routing algorithm is as follows:
      1. Extract the destination host IP address from datagram.
      2. Compute the destination network IP address.
      3. If the network address matches any directly connected network address, then send the datagram directly to that machine.
      4. Else if destination address appears as a host-specific route, then route the datagram as specified in it.
      5. Else if destination network address appears in the routing table, then route datagram as specified in the table.
      6. Else if a default route has been specified, then route the datagram to the default gateway.
      7. Else declare a routing error.

 Within each host there is a routing table that the host uses to determine which physical interface address to use for outgoing IP datagrams.

 There are four basic items of information in such a table

    1. A destination IP address.
    2. A gateway IP address. This will be the same as the destination IP address for directly connected destinations.
    3. Various flags usually displayed as U, G, H and sometimes D and M. U means the route is up. G means the route is via a gateway. H means the destination address is a host address as distinct from a network address.
    4. The physical interface identification.

 A host dedicated to providing a gateway service between several networks is known as a Router and may have a very large routing table (64 MB is not unknown) and will run special protocols to interchange routing information with other hosts and routers.

 Routers are basically Network Layer Relays.

 Two methods are used for information dissemination:
      1. Distance Vector:
      2. Link State:

DISTANCE VECTOR

LINK STATE
Loops are sometimes formed. Looping is not formed, since each router has the complete network topology.
Slow convergence problems. Faster convergence.
Bandwidth intensive process because updates are sent every 60 secs. Routing updates are sent every 15-30 minutes or when there is a change in network topology.
Low processing overhead. Increased route calculation processing.

 Routers use dynamic routing protocols to communicate with each other.

 An Autonomous System (AS) is an individually administered entity (network).

 All autonomous systems have a distinctive and unique number.

 Details of autonomous systems are available from the whois servers in the same way as details of IP networks.

 Unfortunately the syntax of such queries differs between the various servers, the ripe server requires ASnnnn whereas the arin server requires just the number.

 Routing protocols can be broadly classified into two types:
    1. Interior Gateway Protocol (IGP): Basically Intra-domain and hence is valid within the same AS. Examples are RIP, OSPF and BGP.
    2. Exterior Gateway Protocol (EGP): Basically Inter-domain and hence is valid between two different AS. Examples are EGP and BGP.

 Routing Information Protocol (RIP)

 Uses a datagram (UDP) for proliferating routing tables.

 The maximum number of hops allowed is 15 (A limitation!)

 RIP recognizes two types of user devices:

      1. Active: Examples are routers. They can actively broadcast their routes.
      2. Passive: Examples are hosts and servers. They can receive and update their route information but cannot broadcast the information.

 The active users send updates every 30 seconds.

 Routes are considered disconnected unless updates are received. (i.e. they timeout after 180 seconds).

 RIP information is processed by daemon processes (either routed or gated on Unix hosts) listening on the well known port number 520.

 Exterior Gateway Protocol (EGP)

 A distance vector routing protocol.

 It does not employ routing tables.

 It uses point-point communication rather than broadcast.

 Border Gateway Protocol (BGP)

 It enhances EGP.

 A distance vector external routing protocol.

 The enhancements are:

 Read the BGP Frequently Asked Questions.

 For detailed information, look into the BGP Page.

 Open Shortest Path First (OSPF)

 The O means open, i.e. a non-proprietary protocol.

 It is a link state internal gateway protocol.

 OSPF uses IP directly.

 A router using OSPF calculates the shortest path to the other routers in the AS by considering itself as a ROOT.

 The advantages of using OSPF are as follows:
      1. It authenticates the routing update information to ascertain that it is valid.
      2. It converges rapidly upon network topology changes.
      3. It is resilient to routing loops.
      4. It supports load balancing across multiple links.
      5. It supports Type-of-Service routing, eg: link bandwidth or expected link latency.

References:

    1. Cisco TCP/IP routing handbook, Chris Lewis, Mc.Graw Hill, 1997.
    2. Inside TCP/IP. Mathew Flint Arnett et.al., New Riders, 1995.
    3. Internetworking with TCP/IP, Douglas E. Comer, Prentice-Hall, 1991.
    4. TCP/IP and Related Protocols, Uyless Black, McGraw-Hill, 1992.
    5. TCP/IP Illustrated, W. Richard Stevens, Addison-Wesley, 1996.

Back to IP / Back to Main

Maintained by Mohan Atreya , Last update April 8, 1999

First created on November 10, 1998