JTO(T) to SDE(T) Broadband Module

Chapter-5
Routing Principles
Course Contents

 Introduction to Router
 Types of Algorithms used
 Various protocols used for Router configuration
 Differences between various protocols
Objectives

After studying this content on router concepts and router configuration, the trainees are
able to understand what is meant by routing and how the routers are configured for
networks

5.1 Routing
The primary function of a packet switching network is to receive packets from a
source and deliver them to the destination. To achieve this, a path or route through the
network has to be determined. More than one route may be possible. This requires a
routing function/ algorithm to be implemented.
The routing function must achieve the following requirements:
 Correctness
 Simplicity
 Robustness
 Stability
 Fairness
 Optimality
 Efficiency
Correctness and Simplicity are self explanatory.
Robustness has to do with the routing of packets through alternate routes in the
network in case of route failures or overloads.
Stability is an important aspect of the routing algorithm. It implies that the routing
algorithm must converge to equilibrium as quickly as possible, however some never
converge, no matter how long they run.

OSI Page 1 of 7

For Restricted Circulation

JTO(T) to SDE(T) Broadband Module
Fairness and optimality are competing requirements. A trade-off exists between the
two. Some performance criteria may give a higher priority to transportation of packets
between adjacent/ nearby stations in comparison to those between distant stations. This
results in higher throughput but is not fair to the stations which have to communicate with
distant stations.
Efficiency of a routing technique/ algorithm gets decided by the quantum of
overhead processing required. Of course these have to be kept to a minimum.
Thus, Routing is essentially a method of path selection and is an overhead activity.
Routed protocol
A routed protocol is a protocol that contains sufficient network-layer addressing
information for user traffic to be directed from one network to another network. Routed
protocols define the format and use of the fields within a packet. Packets that use a routed
protocol are conveyed from one end system to another end system through an
internetwork.
The internet protocol IP and Novell’s IPX are examples of routed protocols.

Routing protocol
A routing protocol provides mechanisms for sharing routing information. Routing
protocol messages move between the routers. A routing protocol allows the routers to
communicate with other routers to update and maintain routing tables. Routing protocol
messages do not carry end-user traffic from network to network. A routing protocol uses
the routed protocol to pass information between routers.

5.2 Types of Routing

Static routing: refers to routes to destinations being setup manually
in the router. Network reach ability in this case is not dependent on the
existence and state of the network itself. Whether a destination is up or
down, the static routes would remain in the routing table, and traffic
would still be sent towards that destination. Static routing generally is not sufficient for
large or complex networks because of the time required to define and maintain static route
table entries.
Default routing : refers to a “last resort” outlet – traffic to destinations
that are unknown to the local router are sent to the default outlet router. Default routing is
the easiest form of routing for a domain connected to a single exit point. A default route is a

OSI Page 2 of 7

For Restricted Circulation

JTO(T) to SDE(T) Broadband Module
path on which a router should forward a packet if it does not have specific knowledge about
the packet’s destination.
Figure 5.1 below illustrate the concept of Static and default Routing.
Static Routing 10.1/16

Traffic to 10.1

R1 R2
WAN
Send all traffic to R1
Default Routing

Figure 5.1 Static and Default Routing

Dynamic routing: refers to routes being learnt via an internal or
external routing protocol. Network reachability is dependent on the existence and state of
the network. If a destination is down, the route would disappear from the routing table, and
traffic will not be sent toward the destination. Dynamic routing is used to enable routers to
build their routing tables automatically and make the appropriate forwarding decisions. This
concept is illustrated in Figure 5.2 below.

OSI Page 3 of 7

For Restricted Circulation

JTO(T) to SDE(T) Broadband Module
R2
Routing update :
I can reach 100.1

X
R2

R3 R1

100.1

Routing update :
I can reach 100.1

Fig. 5.2 Dynamic Routing

5.3 Routing Algorithms
Routing algorithms and protocols form the core of the Internet, because it is here
that all the decisions get made. Network engineers assign costs to network paths, and
routing protocols select the least-cost path to the destination.
Routing algorithms can be grouped into two major classes :
 Non-Adaptive or Static
 Adaptive or Dynamic
Non Adaptive Algorithms do not base their routing decisions on measurements or
estimates of the current traffic and topology. Instead, the choice of the route to use to get
from I to J (for all I to J) is computed in advance, off-line, and downloaded to the routers
when the network is booted. This procedure is also called as Static Routing.
Adaptive algorithms
Adaptive Algorithms change their routing decisions to take into account changes in
the topology, and sometimes the traffic as well. Adaptive algorithms will be classified
depending on :
Where it gets the information from - whether locally, from adjacent Routers, or from
all Routers
When does the algorithm decide to change the routes - whether every T sec, when
the load changes, or when the topology changes, and

OSI Page 4 of 7

For Restricted Circulation

JTO(T) to SDE(T) Broadband Module
What metric (parameter) is used for optimisation i.e. either distance, number of
hops, or estimated transit time.
5.4 Convergence
Information about the network topology needs to be very accurate and also
consistent from Router to Router. This consistency and accuracy is referred to as
Convergence. The network is considered to have converged when all the Routers contain
consistent information.
5.5 Representing Distance With Metrics
When a routing algorithm updates the routing table, its primary goal is to determine
the best information to include in the table. Each routing algorithm will interpret “best” in
its own way. The algorithm generates a number – called the metric- for each path through
the network. Typically, the smaller the metric, the better is the path.
Metrics can be calculated based on a single characteristic of the path or by
combining several key characteristics such as:
1) Hop Count: Refers to the number of routers a packet must go through, to reach a
destination. The lower the hop count, the better is the path. Path length is used to
indicate the sum of the hops to a destination.
2) Cost: Path cost is the sum of cost associated with each link to
a destination. Costs are assigned (automatically or manually) to the process of
crossing a network. Slower networks typically have a higher cost than faster
networks. The lowest ‘cost” route is the one believed to be the fastest route
available.
3) Bandwidth: The rating of a link’s throughput. Routing through links with greater
bandwidth does not always provide the best routes. For example, if a high-speed link
is busy, sending a packet through a slower link might be faster.
4) Delay: Depends on many factors, including the bandwidth of network links, the length
of queues at each router in the path, network congestion on links, and the physical
distance to be travelled. A conglomeration of variables that change with
internetwork conditions, delay is common and useful metric.
5) Load: Dynamic factor that can be based on a variety of measures, including CPU and
packet processed per second. Monitoring these parameters on a continual basis can
be resource intensive.
Modern computer networks generally use dynamic routing algorithms rather than
the static ones. Two dynamic algorithms in particular,
 distance vector routing algorithms
 link state routing algorithms

OSI Page 5 of 7

For Restricted Circulation

JTO(T) to SDE(T) Broadband Module

5.6 Distance Vector Routing

Distance Vector Routing algorithms require that each router maintain a table (a
vector) indicating the best known distance to each destination and which line/ port to use
to reach there. These tables are constantly updated by exchanging information with the
neighbours. The algorithms periodically pass copies of a routing table from router to router.
Updates between routers also communicate topology changes immediately when they
occur.
The distance vector routing is also known by other names, via; the distributed
Bellman-Ford routing algorithm and the Ford-Fulkerson algorithm, after the researchers
who developed it (Bellman, 1957; and Ford and Fulkerson, 1962). It was the original
ARPANET routing algorithm and was also used in the Internet under the name RIP and in
early versions of Decent and Novell’s IPX.
Examples of distance vector routing protocols are IPX RIP and IP RIP.
5.7 Link State Routing
Link State Routing replaced the Distance Vector Routing (used in the ARPANET) in
1979. Two problems caused the demise of Distance Vector algorithm. First, since the delay
metric was queue length, it did not take line bandwidth into account when choosing the
routes. It would have been possible to change the delay metric to take into account the line
bandwidth, but a second problem existed, namely, the algorithm often took too long to
coverage, even with enhancements like split horizon. For these reasons, it was replaced by
an entirely new algorithm now called link state routing. Variants of link state routing are
now widely used.
The 5 step concept is stated below:
1. Discover the neighbors and learn their network addresses
2. Measure the delay or cost to each of the neighbors
3. Construct a packet telling all that has just been learnt
4. Send this packet to all other routers
5. Compute the shortest path to every other router
When a router is booted, its first task is to learn who its neighbours are. This task is
accomplished by sending a special Hello packet on each point-to-point line. The router on
the other end is expected to send back a reply telling who it is.
Link-state routing algorithms - also known as shortest path first (SPF) algorithm
maintain a complex database of topology information. Whereas the distance vector
algorithm has entries for distant networks and a metric value to reach those networks but

OSI Page 6 of 7

For Restricted Circulation

JTO(T) to SDE(T) Broadband Module
no knowledge of distant routers, a link state routing algorithm maintains full knowledge of
distant routers and how they interconnect. Examples of link-state routing protocols are:
NLSP, OSPF, and IS-IS.
Link state routing is widely used in actual networks. The OSPF protocol, which is
increasingly being used in the Internet, uses a link state algorithm.
5.8 Comparison Of Distance Vector Routing & Link-State Routing
Table 5.1 shows comparison between distance-vector routing and link-state routing
Table 5. 1
Distance Vector Link State

Network Topology is viewed from Entire Network Topology is common to all

neighbours perspective Routers

Metrics are incremented as the update Shortest Path to other Routers is

crosses one Router calculated

Periodic & Frequent Updates results in Updates are triggered by events. Results in
slow convergence faster convergence

Copies of Routing Tables are passed to Link State Packets are passed to other
neighbouring Routers Routers
5.9 Interior Routing And Exterior Routing
Interior routing occurs within an autonomous system. Most common interior routing
protocols are RIP and OSPF. The basic routable element is the IP network or subnetwork, or
CIDR prefix for newer protocols.
Exterior routing occurs between autonomous systems, and is of concern to service
providers and other large or complex networks. Eg BGP-4 (Border Gateway Protocol Version
4) is exterior routing protocol.

IGP

Autonomous
System

BGP

IGP IGP

BGP
OSI Page 7 of 7

For Restricted Circulation