Addis Ababa University

Faculty of Informatics
Department of Computer Science

Chapter 4
Routing
 What Is Routing?

• Routing is the act of moving

information across a network from a
source to a destination.
– Occurs at layer 3 – the network layer
– The router is the device that performs
routing, and it connects different LAN
segments so that larger networks can
be created.
– Routing involves two basic activities:
• determining optimal routing paths and
• transporting packets through a network.
 Cont..
Two types of routing
1.Dynamic
2.static
Dynamic routing can be divided in to two ;
1.Distance vector: RIP,IGRP,EIGRP
2. link state: OSPF
 Default routing
 Default routes are used to route packets with destinations that do not match
any of the other routes in the routing table.

 A default route is actually a special static route that uses this format:

 ip route 0.0.0.0 0.0.0.0 [next-hop-address | outgoing interface]

 This is sometimes referred to as a “Quad-Zero” route.

Example using next hop address:

 Router(config)#ip route 0.0.0.0 0.0.0.0 172.16.4.1

 Cont..
 Distance vector routing: The distance vector
routing approach determines the direction
(vector) and distance to any link in the
internetwork.
 It uses different metrics to make decision to
the final destination point.
RIP( routing information protocol)
 Cont..
• An example of a routing configuration is:
• GAD(config)#router rip
GAD(config-router)#network 172.16.0.0
Cont..
 IGRP
• Interior Gateway Routing Protocol (IGRP) is a proprietary
protocol developed by Cisco.
• Some of the IGRP key design characteristics emphasize
the following:

• It is a distance vector routing protocol.

• Routing updates are broadcast every 90 seconds.

• Bandwidth, load, delay and reliability are used to

create a composite metric.
Cont..
 Link State Concepts
• Link-state algorithms are also known as Dijkstras
algorithm or as SPF (shortest path first)
algorithms.
• Link-state routing algorithms maintain a complex
database of topology information.
• Link-state (LS) routers recognize much more
information about the network than their distance-
vector counterparts,Consequently LS routers tend
to make more accurate decisions
Cont..
Link state
 Cont..
• Format:
 Router(config)# router ospf process id
Router(config-router)#network
address inverse-mask area [area-
id]
 Router(config-router)# router
ospf 1
Router(config-router)# network
10.0.0.0 0.255.255.255 area 0
 cont..
• NB: if we use subnetting let assume the
saubnet mask is 255.255.255.240
• Then the inverse mask will be
0.0.0.15
 making a decision and choosing one route
whenever there are multiple routes
 based on some criteria;
 how do you choose a route when you drive?
 may be the condition of your car and the road,
 the shortest one,
 the one that is not congested,
 the one with less traffic lights, avoid forbidden paths,...
 the job of the network layer routing protocol
 a combination of rules and procedures that lets routers in
the internet inform one another of changes (to share
whatever they know about the internet or their
neighborhood); e.g. a failure of a network can be
communicated
 at the heart of such protocol is the routing algorithm that
determines the path for a packet
 routing requires a host or a router to have a routing table which
is constructed by the routing algorithm

 given big internetworks such as the Internet, the number of

entries in the routing table becomes large and table look ups
become inefficient; methods for reducing its size required
• Routers rely on two types of network
protocols to make the routing
– routable protocols and
– routing protocols.
• Large networks need protocols that allow
systems to be identified by the address of
the network to which they are attached
and by an address that uniquely identifies
them on that network.
• Network protocols that provide both of
these features are said to be routable.
• Three routable LAN network protocols are
used today:
– TCP/IP
– IPX/SPX
– AppleTalk
 Routing protocols are the means by which routers
communicate with each other.
 This communication is necessary so that routers
can learn the network topology and changes that
occur in it.
 two kinds of routing algorithms (routing tables): nonadaptive
(static) and adaptive (dynamic)
 nonadaptive (static)
 routing decisions are not based on measurements or
estimates of the current topology or traffic
 the choice of a root is computed in advance, off-line, and
downloaded to the routers when the network is booted
 an administrator enters the route for each destination into the
table; not automatically updated when there is a change; may
be used in a small internet, but not for big internet like the
Internet
• Disadvantages of static routing
– manually entering routes is time-
consuming and susceptible to human
error.
– if the topology of the network
changes, the routers must be manually
reconfigured.
 adaptive (dynamic)
 routing decisions are made periodically (every  sec) to reflect
changes in the topology, traffic, a shutdown of a router, a
break in the link, a better route has been created, ...
 metrics used
 a metric is a cost assigned for passing through a network
 the cost could be the level of congestion of a link (mean
queue length, transmission delay, average traffic), bandwidth,
the geographic distance traversed by the link, number of hops,
estimated transit time, communication cost, ...
 which cost to choose depends on the application
 the total metric of a particular route is equal to the sum of the
metrics of networks that comprise the route
 a router chooses the route with the shortest (smallest) metric
• Two routing protocols
– distance-vector
– link-state
• A router that uses distance-vector
protocols need only maintain a small
database of the routes accessible by
the routers to which it is directly
connected.
• A router that uses link-state protocols
must maintain a database of the
routers in the entire network.
i. RIP - Routing Information Protocol
 uses distance vector routing algorithm (dynamic)
 each router maintains a table (one entry per router)
giving the best known distance to each destination
 the tables are updated by exchanging information with
neighbors
 in the general case, the metrics could be: number of
hops, time delay in milliseconds, total number of packets
queued along the path, ...
 it is the original ARPANET routing algorithm (using
queue length as a metric) and was used until 1979
 the distance metric used in RIP is the number of hops
all networks are treated as equals, i.e., the cost of passing
through each network is the same, it is one hop count
ii. OSPF - Open Shortest Path First
 became a standard in 1990 by the IETF (Internet Engineering
Task Force)
 aim: to simplify the implementation at the boundaries
between Autonomous Systems by having a standard for the
interior routing
Next Other
 IETF identified some requirements Netwo Co Route Informati
rk st
 has to be published in the open r on
literature - proprietary solutions N1 5 C
are not good N2 7 D
N3 10 B
 has to support a variety of distance N4 11 D

metrics (physical distance, delay, ...)N5 15 C

 it has to be dynamic
 has to do load balancing for better performance (the best
route is not always the best)
  has to support routing based on type of service
 support for hierarchical systems - routers are not
expected to know the entire topology
 introduce security so that spoofing routers by sending
false routing information is avoided
 uses link state routing algorithm (dynamic)
 replaced distance vector routing in ARPANET
 since distance vector routing does not consider
bandwidth (no need initially since all lines were 56 Kbps;
later some lines were upgraded) and other metrics
• Another classification of routing
protocols is interior and exterior
protocols.
 since an internet can be large, one routing protocol
cannot handle the task of updating the routing tables of
all routers
 hence, an internet is divided into autonomous systems
 an autonomous system (AS) is a group of networks
and routers under the authority of a single administration
 routing inside an autonomous system is referred to as
interior routing; each AS can choose its own routing
protocol
 routing between autonomous systems is referred to as
exterior routing; one protocol is usually chosen to
handle routing between autonomous systems; usually
used for routing in the Internet
 R1, R2, R3, and R4 use both interior and exterior routing
protocols
 the rest use only interior routing protocols
 solid lines - communication between routers
 broken lines - communication between the routers that use an
exterior routing protocol
 why an exterior routing protocol apart from size of an
internet? - politics
 political - I hate country X hence I will not handle its
traffic
 security - my information is confidential and should not
pass through a hostile country
 economic
 it should not pass through a competitor’s network
 I am not paid for it and hence don’t want to carry a
transit packet
 such policies are typically manually configured into each
router and are not part of the protocol itself
• Interior and Exterior routing protocols
are more commonly referred to as
Interior Gateway Protocols (IGP) and
Exterior Gateway Protocols (EGP).
• For the most part, the network
administrator is concerned with IGP
protocols. RIP and OSPF are the two
most implemented IGPs.
• BGP (Border Gateway Protocol) is
distance vector exterior routing protocol.