Chapter II:

Introduction to
Routing
The slides has been adapted from:
• Computer Networking: A Top-Down
Approach
8th edition
Jim Kurose, Keith Ross
Pearson, 2020

More slides from other references has been

added.
Chapter 2: Introduction to Routing
Chapter goals:
Understand how data packets are routed in the network
 Forwarding versus routing
 Routing algorithms
Classifications:
Static vs. dynamic
Global vs. decentralized
Hierarchical
Algorithms execution and routing table fillings

Network Layer: 4-2

Chapter 2: Outline
Chapter goals:
2.1 Introduction
2.2 Terminology
2.3 Routing algorithms classification
2.4 Static Routing
2.5 Dynamic Routing

Network Layer: 4-3

 7-Layer OSI Model
Layer 7 Application Layer  Layers 1-4 relate to
communications technology.
Layer 6 Presentation Layer
 Layers 5-7 relate to user
Layer 5 Session Layer applications.
Layer 4 Transport Layer

Layer 3 Network Layer

Layer 2 Data Link Layer

Layer 1 Physical Layer

Communications subnet boundary

Network layer

2.5
Source-to-destination delivery

The network layer is

responsible for the
delivery of individual
packets from
the source host to the
destination host.

2.6
Introduction
 All layer 3 network uses IP mobile network

addressing for routing packets national or global ISP

to the final destination

application

 Data packet routing is achieved by transport

network
link
handing off the packet to the physical
network network

adjacent router until the packet

link link
physical physical

reach its destination network

link network

 Data packet delivery is made

physical link
physical network
link datacenter
network
possible by the use of a
physical

destination MAC address, IP application

transport

address, network address, and enterprise

network
network
link

routing table
physical

Network Layer: 4-7

Two key network-layer functions
network-layer functions: analogy: taking a trip
 forwarding: move packets from  forwarding: process of getting
a router’s input link to through single interchange
appropriate router output link  routing: process of planning trip
 routing: determine route taken from source to destination
by packets from source to
destination
• routing algorithms

forwarding

routing
Network Layer: 4-8
Terminology : Default Gateway vs. Gateway of the Last resort
 Default Gateway: is where to send the data packets that need to exit
the LAN.
• Is typically a router
(also known as first-hop router) PCs Default Gateway

 Gateway of the last resort: is the IP

address of the router in your network
where data packets with unknown
routes should be forwarded
- src. default router: source router
- dst. default router: destination router

Network Layer: 4-9

Terminology (2)
 Routing Algorithm: find the best path from the source router
to the destination router
 Typically, the best path is the one that has the least cost
 In practice, real world problems are considered

30 KM
100 KM Dubai Sharjah 30 KM
Cost = distance

Abu Dhabi Ajman

200 KM Sharjah
40 KM

Cost = Number of hops

 Terminology (2)
 Routing Algorithm: find the best path from the source router
to the destination router
 Typically, the best path is the one that has the least cost
 In practice, real world problems are considered
Policy, failure,
traffic load, etc.
Destination
Source Network
Network

Long Distance
 Terminology: Forwarding vs. Routing

routing algorithm Routing:

Forwarding: local forwarding table
 global action:
header value output link determine source-
 aka “switching” 0100
0101
3
2 destination paths
 local action: move 0111
1001
2
1 taken by packets
arriving packets
from router’s input  routing algorithms
link to appropriate 1
router output link 3 2
1
011

destination address in arriving

packet’s header
Introduction: 1-12
Terminology: Routing Table and Next Hop
 A routing Table: is the list of
possible networks that can be used
to route data packets

Each routing entry describers a route to

reach a specific network
Alternative data paths (alternative routs)
are selected to maintain network if a
network route is down
The router examines destination IP, address
of the packet and selects the next hop using
routing table Network Layer: 4-13
Routing Algorithm Classification
Static vs. Dynamic Global or decentralized information?
Static: Global:
 routes change slowly over  all routers have complete topology, link cost
info
time
 Cost = link state
Dynamic:
Decentralized:
 routes change more quickly  router knows physically-connected
• periodic update neighbors, link costs to neighbors
• in response to link cost  iterative process of computation, exchange
changes of info with neighbors
 Cost = distance
2.14
IP Router Routing Table
There three types of routes in a router’s routing table:
• Directly Connected – These routes are automatically added by the router, provided the
interface is active and has addressing.
• Remote – These are the routes the router does not have a direct connection and may be
learned:
• Manually – with a static route
• Dynamically – by using a routing protocol to have the routers share their information with each other
• Default Route – this forwards all traffic to a specific direction when there is not a match in
the routing table
 Static Routing
Static Route Characteristics:
• Must be configured manually
• Must be adjusted manually by the
administrator when there is a
change in the topology
• Good for small non-redundant
networks
• Often used in conjunction with a
dynamic routing protocol for
configuring a default route
 Standard Static Route
Static route can be used to connect to a specific network (like for example
a stub network)
Configure IPv4 Static Routes
Configure a Fully Specified Static Route
Configure IPv4 Static Routes
Verify a Static Route

Along with ping and traceroute, useful commands to

verify static routes include:
 show ip route
 show ip route static
 show ip route network
Configure IPv4 Static Routes
Verify a Static Route
Dynamic
Routing
Dynamic Routes Automatically:
• Discover remote networks
• Maintain up-to-date information
• Choose the best path to the
destination
• Find new best paths when there
is a topology change
Dynamic routing can also share
static default routes with the other
routers.
 Example 2.1

 Part of an internet with two

routers connecting three
LANs
 Each computer is connected
to only one link and
therefore has only one pair
of addresses
 Each router is connected to
three networks (only two are
shown in the figure)
 So, each router has three
pairs of addresses, one for
each connection.
2.22
Routing Strategies
 Fixed
 Flooding
 Random
 Adaptive
Fixed Routing Tables
 Single permanent route
for each source to
destination pair
 Determine routes using a
least cost algorithm
(appendix 10A)
 Route fixed, at least until
a change in network
topology
Flooding
 No network info required
 Packet sent by node to every neighbor
 Incoming packets retransmitted on every link except incoming link
 Eventually a number of copies will arrive at destination
 Each packet is uniquely numbered so duplicates can be discarded
 Nodes can remember packets already forwarded to keep network load in
bounds
 Can include a hop count in packets
Flooding
 No network info required
 Packet sent by node to every
neighbor
 Incoming packets retransmitted on
every link except incoming link
 Eventually a number of copies will
arrive at destination
 Each packet is uniquely numbered
so duplicates can be discarded
 Nodes can remember packets
already forwarded to keep
network load in bounds
 Can include a hop count in packets
Properties of Flooding
 All possible routes are tried
• Very robust
 At least one packet will have taken minimum hop count route
• Can be used to set up virtual circuit
 All nodes are visited
• Useful to distribute information (e.g. routing)
Random Routing
 Node selects one outgoing path for retransmission of incoming
packet
 Selection can be random or round robin
 Can select outgoing path based on probability calculation
 No network info needed
 Route is typically not least cost nor minimum hop
Adaptive Routing - Advantages
 Improved performance
 Aid congestion control
 Complex system
• May not realize theoretical benefits