Editor's Note
Dynamic Routing
New Sub Domains
News from METU-CC
Health & Computers
Thermal Printers
Fun Stuff
CISN Archive
Send Feedback


Computing & Information Services Newsletter
 Dynamic Routing
     
 

In Internet world, information is moved across some kind of networks and terminates at destination point. In this process, a data packet can pass several check points. These points, usually called as router that finds the path to which they transmit the data packet. A router needs some way of deciding upon the optimal path for transmission of a packet to a destination address. If the destination is not directly connected, the router needs more information about its address. They use routing information from the administrator or other routers to build routing tables. Routers can keep each other informed about the state of the network by exchanging messages. One such message is a routing update which consists of part, or all, of a routing table from one router. Another type is a link-state advertisement which contains information on the state of the senders links. Information may be shared between routers at regular time intervals which are defined by the routing protocols used.

Routing algorithms are used to compare the available options and select the best possible route to a given destination. They must be flexible enough to react rapidly to changing conditions on the network such as changing in network bandwidth, delay, and the size of router queues. When the network become stable again, it is said to be converged. Rapid convergence is an important design goal for routing algorithms.

Routing metrics are used by the routing algorithm to select the best route. Common metrics include: -hop count, -reliability, -load, -delay, bandwidth, and -maximum transmission unit. The hop count metric counts the number of links, or hops, on the path from source to destination network. Reliability is a metric that assesses the extent to which a link is inclined to fail. It is expressed as a fraction of 255 denoting the percentage of time an interface has been up over the period of the statistics. Load tries to measure how busy a link is by calculating packets processed per second and measuring CPU utilization. The information-carrying capacity of the network link is measured by bandwidth and is usually expressed as bits per second (bps). The MTU is the maximum length for a message that can be handled by all the devices on the route. Routing protocols use these data to decide the path dynamically. A dynamic routing protocol is configured to respond to changes so that it optimizes the paths in a changing network. Once enabled, dynamic routing is automatically updated as the network topology changes.

The two major types of routing protocol are Interior Gateway Protocol (IGP), and Exterior Gateway Protocol (EGP). The difference is, IGPs function within an autonomous system, whereas EGPs function between autonomous systems. An autonomous system is a collection of networks within a common administrative domain. METU, for example, is an autonomous system. Each autonomous system has an unique autonomous system number. (METU's AS number is 1967) Examples of IGPs include Routing Information Protocol (RIP) and Interior Gateway Routing Protocol (IGRP). Border Gateway Protocol (BGP) is an example of an EGP, that means BGP is used for routing Autonomous Systems.

Routers are constantly receiving routing information from the surrounding network, but not all information sources are equally reliable. To reflect the level of trustworhiness of the information source, different routing protocols are assigned different administrative distances. Administrative distances can range in value from 0 to 255. The router will choose the route, selected by the routing protocol, with the lowest administrative distance.

 

 
 
Route Source Default Admin. Dist.
connected interface 0
static route address 1
EIGRP 90
IGRP 100
OSPF 110
RIP 120
External EIGRP 170

 

 
 

If routing information is available from both an IGRP source and an RIP source, the IGRP option will be choosen because it has the lower default value.

Algorithms used by IGPs can generally be classified as one of three types: Distance vector, link state and balanced hybrid.

Distance vector protocols use fewer system resources but can suffer from slow convergence and may use metrics that do not scale well to larger systems. They are based on finding the direction (vector) and distance to any link on the internetwork. The algorithms involved pass copies of a complete routing table from router to router on a periodic basis. distance vector protocols do not send trigerred updates. (Trigerred updates are updates that are sent when changes occur in network topology) Routing Information Protocol -RIP which is a distance vector protocol uses a simple hop-count metric. It measures reducing distance as a reduction in hop count. RIP routers send and receive routing updates, consist of the full routing table, every 30 seconds. The receiving routers analyse the information and alter routing tables accordingly. RIP sets a maximum hop-count value 15. If the destination has a hop count higher than 15, it is seen as unreachable.

IGRP is another distance vector protocol that was designed by CISCO in the 1980s to overcome problems faced by RIP in dealing with the growing size and increasingly complex nature of networks. In IGRP, a number of metrics- including delay, reliability and load are combined into a user-definable algorithm.

Link state (or Shortest Path First) algorithms use link-state discovery mechanisms to create a map of the whole network. Each router sends all its neighbours packets of information containing descriptions of the network or networks that it is linked to. The routers assemble all the information into a complete view of the internetwork topology to calculate the shortest path to all known sites on the network. It then generates routing tables showing the best path for any destination on the network. Link state protocols use small update packets, which contain only changes rather than copies of routing tables. Update packets are passed rapidly across the network in event-trigerred updates, so convergence is fast. In general, link state algorithms have higher convergence which means they are less prone to routing errors, but they use more system resources.

Open Shortest Path First (OSPF) and NetWare Link Services Protocol (NLSP) are two common link-state protocols. The third type of dynamic routing protocol adapts certain aspects of distance vector and link state protocols to create balanced hybrid protocol. The balanced hybrid protocol uses the distance vector approach to gathering information about the network. These protocols use topology changes as a trigger for network updates. Like link-state protocols, balanced hybrid protocols converge rapidly. Two examples of balanced hybrid protocols are Intermediate System to Intermediate System ( IS-IS) and Cisco's Enhanced IGRP.

As mentioned above, Border Gateway protocol is an inter-autonomous system routing protocol created for use in the Internet. However it can be used for routing packets both within and between ASs. BGP uses The Transport Control Protocol (TCP). When two routers running BGP form a TCP connection they exchange messages to open and confirm the connection parameters. Unlike some other routing protocols, BGP does not require a periodic refresh of the entire routing table. Instead routers running BGP receive incremental updates that contain the latest version of each peer's routing table. It maintains a routing table with all feasible paths to a particular network. But it advertises only the optimal path in its update messages.

In METU network, we use BGP, RIP and EIGRP routing protocols. The traffic that goes out of campus is directed by BGP. Two ULAKNET connections use EIGRP routing protocol. RIP serves to inner network.

 
     
  - TOP -  
2001 METU CC
Design: CC - INFO