Routing Fundamentals
Ejaz Ahmed
Delivery, Forwarding,
and Routing of IP Packets
Objectives
Understand the different types of delivery and the
connection
Understand forwarding techniques in classful
addressing
Understand forwarding techniques in classless
addressing
Understand how a routing table works
DELIVERY
The network layer supervises delivery,
the handling of the packets by the
underlying physical networks. Two
important concepts are the type of
connection and direct versus indirect
delivery.
Connection Types
Direct Versus Indirect Delivery
Note:
IP is a connectionless protocol.
Routing
Routing is an act of moving information
across an internetwork from a source to
destination
Both the hosts and routers participate in
routing the datagram to their destination
Routing is done at layer 3 (Network Layer)
Direct delivery
Transmission of datagram from one machine to
another, when both are attached to the same
underling physical transmission system, is
called Direct Delivery
Indirect delivery
Indirect Delivery
When two machines are not directly
connected to the same network and
packets must go through at least one
router for delivery.
B wants to deliver the datagram to D
B checks the network prefix and realizes
that D is outside of L1
In an internet, every host can reach a
router directly
B sends the packet to R1 and lets R1
handle the delivery
FORWARDING
Forwarding means to place the packet in its route to
its destination. Forwarding requires a host or a
router to have a routing table. .
IP Routing Table
IP routing involves the use of IP Routing Table that
stores information about possible destinations and how
to reach them
Both host and routers route datagrams, and thus have
routing tables
Routing Table contains the Next-Hop required to
reach the destination
Routes to every possible destination is not possible
Insufficient Space
Impossible to keep the routing table current
Next-Hop Routing
Routing tables only need to contain network IDs
and not the full IP addresses
A routing table contains pairs (N, R) where N is
the IP of destination network, and R is the IP
address of next router along the path
The routing table only knows the next router for a
specific destination and the not the complete route
Basically each router listed in the table can be
reached via a direct connection
Next-Hop Routing
Types of routes
Host Specific routes
Default routes
Static routes
Dynamic routes
Network-specific method
Host-Specific Routes
Routes for specific hosts can also be added to the
routing table
Gives more control to the administrator
Better routing flexibility, at the expense of larger
routing tables
Host-specific routing
Default Routes
Helps in keeping the routing table size small
If no route for a destination is available, the
datagram is forwarded as indicated by the default
route
Useful for hosts with only one router attached
They only have two choices Local network or the
default that takes care of all the destinations outside
local network
If no route to destination & no default route is available,
DU message is sent back to sender
The basic disadvantage is; misaddressed packets may get
forwarded for a number of hops, and consume processing
and bandwidth
Default routing
Static Routes
Routing tables are manually populated
Simple for very small networks, but administrative
nightmare for large networks
Does not adjust to topology changes or network
failures
If all routes are static, router dont need to
exchange routing information
Dynamic Routes
Routing tables are updated automatically
Adjust to topology changes and network failures
automatically
Routers exchange routing updates to share
information
Protocols like RIP, OSPF are used for information
exchange
Less administrative overhead, but more processing
and overhead
10
Configuration
Address aggregation
11
Figure 6-9
Configuration for routing example
Mask
Dest.
Next Hop
I.
255.0.0.0
111.0.0.0
--
m0
255.255.255.224
193.14.5.160
m2
255.255.255.224
193.14.5.192
m1
------------------------------------------------------------------------------------255.255.255.255
194.17.21.16
111.20.18.14
m0
------------------------------------------------------------------------------------255.255.255.0
192.16.7.0
111.15.17.32
m0
255.255.255.0
194.17.21.0
111.20.18.14
m0
------------------------------------------------------------------------------------0.0.0.0
0.0.0.0
111.30.31.18
m0
12
Example 1
Router R1 receives 500 packets for destination
192.16.7.14; the algorithm applies the masks
row by row to the destination address until a
match (with the value in the second column) is
found:
Solution
Direct delivery
192.16.7.14 & 255.0.0.0
192.0.0.0 no match
192.16.7.14 & 255.255.255.224 192.16.7.0 no match
192.16.7.14 & 255.255.255.224 192.16.7.0
no match
Host-specific
192.16.7.14 & 255.255.255.255 192.16.7.14 no match
Network-specific
192.16.7.14 & 255.255.255.0
192.16.7.0 match
13
Example 2
Router R1 receives 100 packets for destination
193.14.5.176; the algorithm applies the masks
row by row to the destination address until a
match is found:
Solution
Direct delivery
193.14.5.176 & 255.0.0.0
193.0.0.0
193.14.5.176 & 255.255.255.224 193.14.5.160
no match
match
14
Longest mask matching
IP Routing Table
Destination
Gateway
Flags
Interface
Ref
Use
195.78.112.0
195.78.112.1
Eth0
1726
127.0.0.1
127.0.0.1
UH
Lo0
90026
Default
195.78.112.254
UG
Eth0
25000
U: The route is up
G: The route is to a gateway (not set dest directly connected)
H: The route is to a Host
15
IP Routing Table
Destination: The final destination of the packet
Gateway: The next hop for this packet
Flags:
U: The route is up and operational
G: The destination is not directly connected to this router/host
H: The destination entry in the table belongs to a host. If H is not
present, then the entry denotes a network
Ref: Number of times the entry is referred to establish a
connection
Use: Number of packets forwarded using the entry
IP Routing
RouteDatagram(Datagram, RoutingTable)
Extract destination IP address in D
Extract the network prefix in N
if N matches any directly connected network
deliver datagram directly to destination D over that network
else if the table contains a host-specific route for D
send datagram to the next-hop specified in the table
else if the table contains a route for network N
send datagram to the next-hop specified in the table
else if the table contains a default route
send datagram to the default router specified
else
declare a routing error!
16
IP Routing
IP routing does not alter the original datagram
except for:
Decrementing the time-to-live
Re-computing the checksum
When a router receivers a datagram:
If the destination IP is the routers IP, it passes the
datagram to higher levels
Otherwise, it routes the datagram
IP Routing
Hosts are forbidden from forwarding datagrams
that are not destined for them
Reasons
Something has gone wrong
It will cause unnecessary network traffic
Routers report errors but host do not
17
Summary
IP uses routing information to route datagrams.
Direct delivery is considered as the final step in routing.
The result of routing is the IP address of the next hop.
IP routing algorithm is table-driven and in most cases
based on the network addresses.
Using a default route keeps the routing tables small.
Routes can be configured statically and dynamically.
Hosts do not forward datagrams.
Reference Reading
Chapter 6
TCP/IP Protocol Suite, Second Edition,
Behoruz A. Forouzan
Chapter 10
Internetworking with TCP/IP, Principles,
Protocols and Architectures, Fourth Edition,
Douglas E. Comer
18
