IP Routing Algorithm

In OSI the network layer functions include routing and switching of a datagram through the telecommunications subnetwork. The IP provides this essential function. It forwards the datagram based upon the network address contained within the IP header. Each datagram is independent and has no relationship with other datagrams. There is no guaranteed delivery of the datagrams from the standpoint of the Internet protocol. However, the next higher layer, the TCP layer, provides for the reliability that the IP lacks. It also carries out segmentation and reassembly function of a datagram to match frame sizes of data-link layer protocols.

Addresses determine routing, and at the far end, equipment (hardware). Actual routing derives from the IP address, and equipment addresses derive from the data-link layer header (typically the 48-bit Ethernet address) (Ref. 5).

User data from upper-layer protocols is passed to the IP layer. The IP layer examines the network address (IP address) for a particular datagram and determines if the destination node is on its own local area network or some other network. If it is on the same network, the datagram is forwarded directly to the destination host. If it is on some other network, it is forwarded to the local IP router (gateway). The router, in turn, examines the IP address and forwards the datagram as appropriate. Routing is based on a look-up table residing in each router or gateway.

12.3.3.1 IP Routing Details. A gateway (router) needs only the network ID portion of the address to perform its routing function. Each router or gateway has a routing table which consists of: destination network addresses and specified next-hop gateway.

Three types of routing are performed by the routing table:

1. Direct routing to locally attached devices

2. Routing to networks that are reached via one or more gateways

3. Default routing to destination network in case the first types of routing are unsuccessful

Suppose a datagram (or datagrams) is (are) directed to a host which is not in the routing table resident in a particular gateway. Likewise, there is a possibility that the network address for that host is also unknown. These problems may be resolved with the address resolution protocol (ARP) (Ref. 7).

First the ARP searches a mapping table which relates IP addresses with corresponding physical addresses. If the address is found, it returns the correct address to the requester. If it cannot be found, the ARP broadcasts a request containing the IP target address in question. If a device recognizes the address, it will reply to the request where it will update its ARP cache with that information. The ARP cache contains the mapping tables maintained by the ARP module.

There is also a reverse address resolution protocol (RARP) (Ref. 8). It works in a fashion similar to that of the ARP, but in reverse order. RARP provides an IP address to a device when the device returns its own hardware address. This is particularly useful when certain devices are booted and only know their own hardware address.

Routing with IP involves a term called hop. A hop is defined as a link connecting adjacent nodes (gateways) in a connectivity involving IP. A hop count indicates how many gateways (nodes) must be traversed between source and destination.

One part of an IP routing algorithm can be source routing. Here an upper-layer protocol (ULP) determines how an IP datagram is to be routed. One option is that the ULP passes a listing of Internet addresses to the IP layer. In this case information is provided on the intermediate nodes required for transit of a datagram in question to its final destination.

Each gateway makes its routing decision based on a resident routing list or routing table. If a destination resides in another network, a routing decision is required by the IP gateway to implement a route to that other network. In many cases, multiple hops are involved and each gateway must carry out routing decisions based on its own routing table.

A routing table can be static or dynamic. The table contains IP addressing information for each reachable network and closest gateway for the network, and it is based on the concept of shortest routing, thus routing through the closest gateway.

Involved in IP shortest routing is the distance metric, which is a value expressing minimum number of hops between a gateway and a datagram's destination. An IP gateway tries to match the destination network address contained in the header of a datagram with a network address entry contained in its routing table. If no match is found, the gateway discards the datagram and sends an ICMP (see next subsection) message back to the datagram source.

12.3.3.2 Internet Control Message Protocol (ICMP). ICMP is used as an adjunct to IP when there is an error in datagram processing. ICMP uses the basic support of IP as if it were a higher-level protocol.; however, ICMP is actually an integral part of IP and is implemented by every IP module.

ICMP messages are sent in several situations: for example, when a datagram cannot reach its destination, when a gateway (router) does not have the buffering capacity to forward a datagram, and when the gateway (router) can direct the host to send traffic on a shorter route.

ICMP messages typically report errors in the processing of datagrams. To avoid the possibility of infinite regress of messages about messages, and so on, no ICMP messages are sent about ICMP messages. There are eight distinct ICMP messages:

1. Destination unreachable message

2. Time exceeded message

3. Parameter problem message

4. Source quench message

5. Redirect message

6. Echo or echo reply message

7. Timestamp or timestamp reply message

8. Information request or information reply message

12.3.3.3 IP Summary. The IP provides connectionless service, meaning that there is no call setup phase prior to the exchange of traffic. There are no flow control or error control capabilities incorporated in IP. These are left to the next higher layer, the transmission control protocol (TCP). The IP is transparent to subnetworks connecting at lower layers; thus different types of networks can attach to an IP gateway or router. To compensate for these deficiencies in IP, the TCP (transmission control protocol) was developed as an upper layer to IP. It should be noted that TCP/IP can be found in both the LAN and WAN environments.

Was this article helpful?

0 0

Post a comment