Important Information

Slide content, tables and diagrams are drawn from the

Jan-19 2
Chapter 11

Jan-19 3
Objectives
 Distinguish between intradomain and interdomain
routing
 Understand distance vector routing and RIP
 Ability to calculate routing table entries in RIP
 Understand link state routing and OSPF
 Understand path vector routing and BGP

Jan-19 4
Intradomain and Interdomain
Routing
 The Internet (and internets) are divided into
autonomous systems
 An Autonomous System (AS) is a group of networks
and routers under the authority of a single
administration
 Routing within an AS is referred to as intradomain
routing
 Routing between autonomous systems is referred to
interdomain routing

Jan-19 5
Autonomous Systems

Jan-19 6
Unicast Routing Protocols
 An Internet is a collection of networks connected by
routers.
 Routers determine the path a packet should take based
on a metric (cost).
 A router uses a routing table to specify the optimum
path that a packet should take based on a metric.
 A routing protocol is a combination of rules and
procedures that enables routers to exchange information
in their routing tables.

Jan-19 7
Popular Routing Protocols

Jan-19 8
Distance Vector Routing
 In distance vector routing, the least cost route between
any two nodes is the route with minimum distance.
 Minimum distance is determined by the total of the link
(network) costs to the destination.
 Each node maintains a vector (table) of minimum
distances to every node in its AS.

Jan-19 9
Distance Vector Routing Tables

Jan-19 10
Routing Information Sharing
 In Distance Vector Routing, each node shares its entire
routing table with its immediate neighbours periodically
and when there is a change.
 Nodes can only calculate the distance between
themselves and their nearest neighbour.
 Distance between other nodes should be sent by those
nodes.

Jan-19 11
Initialisation of Tables in Distance
Vector Routing

Jan-19 12
3 Step Updating in Distance Vector
Routing

Jan-19 13
RIP Version 1
 The Routing Information Protocol (RIP) is an
intradomain routing protocol used within an
autonomous system. It is a very simple protocol based
on distance vector routing.
 The distance metric used is that each network link has
the value of 1 (called hop count as the number of links is
also the number of hops to the destination).
 Infinity (not reachable) is defined as 16.
 So largest AS can only have 15 hops between any two
nodes to use RIP.

Jan-19 14
Example of a Domain using RIP

Jan-19 15
RIP Message Format
 Request and reply messages are limited
broadcast.
 Network address section is 14 bytes so as to
accommodate any addressing scheme.

Jan-19 16
Request message

a. Request an update on a particular network link.

Jan-19 17
RIP Timers

Jan-19 18
Periodic Timer
 Controls the advertising of regular update messages.
 Uses a random number between 25 and 35 seconds, to
prevent routers updating simultaneously (on average
every 30 seconds).

Jan-19 19
Expiration Timer
 Governs the validity of a route.
 On receipt of an update, the expiration timer is set to
180 seconds for that particular route.
 Each time a new update is received, the timer is reset.
 If a problem occurs the allotted 180 seconds expires, at
this time the hop count is set to 16 (infinity), which
means the destination is unreachable.

Jan-19 20
Garbage Collection Timer
 When information about a route becomes invalid
(destination unreachable), the router does not
immediately purge the route from its table.
 It continues to advertise the route with a metric of 16.
 At this time the garbage collection timer is set to 120
seconds for the route.
 When the count reaches zero, the route is purged.

Jan-19 21
RIP Version 2
 Advances on RIPv1 to accommodate
 Route tag – information from interdomain routing
protocols.
 Subnet Mask – supports classless addressing (must
include the mask).
 Next hop addressing – in case routers are boundary
routers (need to know next hop outside AS).
 Authentication by using the first repeated segment to
include this information.
 Multicast message so only routers are valid receivers.
 UDP Encapsulation (port 520).

Jan-19 22
RIP Version 2 Format

Jan-19 23
Link State Routing
 Intradomain routing protocol.
 Each node in the domain finds the entire topology of
the domain.
 Nodes know the type, cost and condition of each link.
 Each node uses Dijkstra’s algorithm to calculate its
path metric and build the routing table.

Jan-19 24
Building Routing Tables
 Create a Link State Packet (LSP) to advertise the state
of links for the node.
 Flood AS (multicast) with this information.
 Each router calculates the shortest path tree for each
node.
 Update routing table based on new/additional
information.
 LSP’s are created when
 Triggered update – change in the network
 Periodic – refresh function every 60 – 120 minutes

Jan-19 25
Concept of Link State Routing

Jan-19 26
Link State Knowledge

Jan-19 27
Routing Table for Node A

Jan-19 28
Open Shortest Path First (OSPF)
 The Open Shortest Path First (OSPF) protocol is an
intradomain routing protocol based on link state
routing.
 OSPF categorises the AS into different areas:
 An area is a collection of networks, hosts and routers.
 Area Border Routers summarise area information and
pass between areas.

Jan-19 29
Areas in an Autonomous System

Jan-19 30
OSPF Metrics
 OSPF allows administrators to assign a cost (metric) to
each route.
 The metric is usually based on type of service
(minimum delay, maximum throughput etc.).

Jan-19 31
OSPF Links
 Connections in OSPF are called links
 There are 4 different types of links:
 Point-to-point: connects 2 routers without any other
host or router between them.
 Transient: a network with several routers attached to
it.
 Stub: a network connected to only one router (end).
 Virtual: created when a link is broken and a new path
is created.

Jan-19 32
Example of an AS and its Graphical
Representation in OSPF

Jan-19 33
Types of OSPF Packets

Jan-19 34
OSPF Common Header

Jan-19 35
Link State Update Packet

Jan-19 36
OSPF Other Packets
 Hello message: creates neighbourhood relationships
and tests reachability of neighbours (first step).
 Database Description message: sent in response to a
Hello message from a new router, contains the outline of
the routing table.
 Link State Request message (LSR): sent so a router can
complete its table.
 Link State Acknowledgment message (LSAck): sent in
response to every LSU packet received.

Jan-19 37
Path Vector Routing
 Used for Interdomain routing.
 Path Vector Routing is similar to Distance Vector
Routing.
 There is at least one node, called the speaker node,
that acts on behalf of each AS.
 The speaker node creates a routing table and
advertises it to speaker nodes in neighbouring ASs.

Jan-19 38
Path Vector Routing
 The speaker node advertises the full path and not the
metric inside its AS
 Distance Vector Routing is unstable with too many hops.
 Link State Routing uses huge resources and adds a large
amount of traffic.

Jan-19 39
Path Vector Routing
 Loops are prevented by checking the path list to
ensure the node is not already listed.
 Policy routing can be implemented as the entire path
is known and therefore, routers can be checked against
policy information.
 Metrics are not included when shared as each network
may have different criteria they place on links and each
AS may use different routing protocols.
 The optimum path is the path that fits the
organisation and depends on what is important.

Jan-19 40
Initial Routing Tables in Path Vector Routing

Jan-19 41
Stabilised Tables for Four Autonomous Systems

Jan-19 42
Border Gateway Protocol (BGP)
 Border Gateway Protocol (BGP) is an Interdomain
routing protocol using path vector routing
 It first appeared in 1989 and has gone through four
versions
 BGP supports Classless InterDomain Routing (CIDR)
 Uses TCP port 179

Jan-19 43
Types of BGP Messages

Jan-19 44
Types of BGP Messages (contd.)
 Open message creates a neighbourhood
relationship, the other routers reply with a
Keepalive message.
 Update message is used to advertise new routes
or change/delete existing ones.
 Keepalive message only contains the common
header with type set to 3.
 Notification message is sent when immediate
changes need to be made due to error or need to
close a connection (graceful shutdown).

Jan-19 45
After the lecture…
 Review the lecture material at least once.
 Read all relevant sections in the textbook.
 Attempt all tutorial problems.
 Complete the relevant questions from the
assignment.
 Check if you are competent with the objectives
mentioned at the beginning of each topic.

Jan-19 46