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
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.
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.