Chapter 22

Network Layer:
Delivery, Forwarding,
and Routing

22.1 Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 22-1
DELIVERY
The network layer supervises the handling of the
packets by the underlying physical networks. We define
this handling as the delivery of a packet.

Topics discussed in this section:

Direct Versus Indirect Delivery

22.2
 Figure 22.1 Direct and indirect
delivery

22.3
 22-2
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. When a host has a packet to
send or when a router has received a packet to be
forwarded, it looks at this table to find the route to the
final destination.

Topics discussed in this section:

Forwarding Techniques
Forwarding Process
Routing Table

22.4
 Figure 22.2 Route method versus next-hop
method

22.5
 Figure 22.3 Host-specific versus network-specific
method

22.6
 Figure 22.4 Default
method

22.7
 Figure 22.5 Simplified forwarding module in classless
address

22.8
 Note

In classless addressing, we need at least

four columns in a routing table.

22.9
 Example 22.1

Make a routing table router R1, using the

for configuration in Figure
22.6.
Solution
Table 22.1 shows the corresponding table.

22.10
 Figure 22.6 Configuration for Example
22.1

22.11
 Table 22.1 Routing table for router R1 in Figure
22.6

22.12
 Example 22.2

Show the forwarding process if a packet arrives at R1 in

Figure 22.6 with the destination address 180.70.65.140.
Solution
The router performs the following steps:
1. The first mask (/26) is applied to the destination address.
The result is 180.70.65.128, which does not match the
corresponding network address.
2. The second mask (/25) is applied to the destination
address. The result is 180.70.65.128, which matches the
corresponding network address. The next-hop address
and the interface number m0 are passed to ARP for
further processing.
22.13
 Example 22.3

Show the forwarding process if a packet arrives at R1 in

Figure 22.6 with the destination address 201.4.22.35.

Solution
The router performs the following steps:
1. The first mask (/26) is applied to the destination
address. The result is 201.4.22.0, which does not
match the corresponding network address.
2. The second mask (/25) is applied to the destination
address. The result is 201.4.22.0, which does not
match the corresponding network address (row 2).
22.14
 Example 22.3 (continued)

3. The third mask (/24) is applied to the destination

address. The result is 201.4.22.0, which matches the
corresponding network address. The destination
address of the packet and the interface number m3 are
passed to ARP.

22.15
 Example 22.4

Show the forwarding process if a packet arrives at R1 in

Figure 22.6 with the destination address 18.24.32.78.

Solution
This time all masks are applied, one by one, to the
destination address, but no matching network address is
found. When it reaches the end of the table, the module
gives the next-hop address 180.70.65.200 and interface
number m2 to ARP. This is probably an outgoing package
that needs to be sent, via the default router, to someplace
else in the Internet.

22.16
 Figure 22.7 Address
aggregation

22.17
 Figure 22.8 Longest mask
matching

22.18
 Example 22.5

As an example of hierarchical routing, let us

consider Figure 22.9. A regionalISP is granted 16,384
addresses starting from 120.14.64.0. The regional
ISP has decided to dividethis block into four
subblocks, each with 4096 addresses. Three of these
subblocks are assigned to three local ISPs; the second
subblock is reserved for future use. Note that the mask
for each block is /20 because the
original block with mask /18 is divided into 4 blocks.
The first local ISP has divided its assigned subblock into
8 smaller blocks and assigned each to a small ISP. Each
small ISP provides services to 128 households, each using
four addresses.
22.19
 Example 22.5 (continued)

The second local ISP has divided its block into 4 blocks
and has assigned the addresses to four large
organizations.
The third local ISP has divided its block into 16 blocks
and assigned each block to a small organization. Each
small organization has 256 addresses, and the mask is
/24.
There is a sense of hierarchy in this configuration. All
routers in the Internet send a packet with destination
address 120.14.64.0 to 120.14.127.255 to the regional ISP.

22.20
 Figure 22.9 Hierarchical routing with
ISPs

22.21
 Figure 22.10 Common fields in a routing
table

22.22
 Example 22.6

One utility that can be used to find the contents of a

routing table for a host or router is netstat in UNIX or
LINUX. The next slide shows the list of the contents of a
default server. We have used two options, r and n. The
option r indicates that we are interested in the routing
table, and the option n indicates that we are looking for
numeric addresses. Note that this is a routing table for a
host, not a router. Although we discussed the routing table
for a router throughout the chapter, a host also needs a
routing table.

22.23
 Example 22.6 (continued)

The destination column here defines the network address.

The term gateway used by UNIX is synonymous with
router. This column actually defines the address of the next
hop. The value 0.0.0.0 shows that the delivery is direct. The
last entry has a flag of G, which means that the destination
can be reached through a router (default router). The Iface
defines the interface.
22.24
 Example 22.6 (continued)

More information about the IP address and physical

address of the server can be found by using the ifconfig
command on the given interface (eth0).

22.25
 Figure 22.11 Configuration of the server for Example
22.6

22.26
Routing Algorithms (protocols)

Distance vector routing

(RIP –routing information protocol)
Link state routing
(OSPF –open shortest path first)
The differences between routing algorithms
are in the way they interpret the least cost
and the way they create the least-cost tree
for each node.
-The source host needs no forwarding table
because it delivers its packet to the default
router in its local network
-only the routers that glue together the
networks in the internet need forwarding
tables.
-each router needs to find the least-cost
route between itself and all the other
routers to be able to route a packet using
this criteria
-If there are N routers in an internet, there
are (N − 1) least-cost paths from each
router to any other router
-A better way to see all of these paths is to
combine them in a least-cost tree.
-A least-cost tree is a tree with the
source router as the root that spans the
whole graph and in which
-the path between the root and any other
node is the shortest.
In distance-vector routing, the first thing
each node creates is its own least-cost tree
with the rudimentary information it has
about its immediate neighbors

In distance-vector routing, a router

continuously tells all of its neighbors what it
knows about the whole internet (although
the knowledge can be incomplete).
the Bellman-Ford equation and the concept of distance
vectors,
heart of distance-vector routing is the famous Bellman-
Ford equation. This equation is used to find the least
cost (shortest distance) between a source node, x, and a
destination node, y, through some intermediary
nodes (a, b, c, . . .) when the costs between the
source and the intermediary nodes and the least costs
between the intermediary nodes and the destination are
given.
The following shows the general case in which
Dij is the shortest distance and
cij is the cost between nodes i and j.
 Figure 20.3: Graphical idea behind Bellman-Ford equation

20.35
Bellman-Ford equation enables us to build a
new least-cost path from previously
established least-cost paths
Bellman-Ford equation and the concept of
distance vectors is used to build least-cost
paths for each node in distance-vector
routing
paths are graphically glued together to form
the tree
A distance vector does not give the path to
the destinations as the least-cost tree does;
it gives only the least costs to the
destinations
the name of the distance vector defines the
root, the indexes define the destinations,
and the value of each cell defines the least
cost from the root to the destination.
The node sends some greeting messages
out of its interfaces and discovers the
identity of the immediate neighbors
makes a simple distance vector by inserting
the discovered distances in the
corresponding
cells and leaves the value of other cells as
infinity
 Table 20.1: Distance-Vector Routing Algorithm for A Node

20.38
Do these distance vectors represent
least-cost paths? They do, considering the
limited information a node has.
When
we know only one distance between two
nodes, it is the least cost.

we can change a distance

vector to a forwarding table
 22-3 UNICAST ROUTING
PROTOCOLS
A routing table can be either static or dynamic. A static
table is one with manual entries. A dynamic table is
one that is updated automatically when there is a
change somewhere in the Internet. A routing protocol
is a combination of rules and procedures that lets
routers in the Internet inform each other of changes.
Topics discussed in this section:
Optimization
Intra- and Interdomain Routing
Distance Vector Routing and RIP
Link State Routing and OSPF
Path Vector Routing and BGP
22.42
 Figure 22.12 Autonomous
systems

22.43
 Figure 22.13 Popular routing
protocols

22.44
 Figure 22.14 Distance vector routing
tables

22.45
 Figure 22.15 Initialization of tables in distance vector
routing

22.46
 Note

In distance vector routing, each node

shares its routing table with its
immediate neighbors periodically and
when there is a change.

22.47
 Figure 22.16 Updating in distance vector
routing

22.48
 Figure 22.17 Two-node instability

22.49
 Figure 22.18 Three-node instability

22.50
  Split Horizon
 instead of flooding the table through each
interface, each node sends only part of
its table through each interface

22.51
  Protocols are based on the corresponding
algorithms
 (RIP- Distance vector)

 (OSPF-Link state)

 Protocol define

domain of operation,
the messages exchanged,
communication between routers,
and interaction with other protocols
routing in the Internet cannot be done using
a single protocol
22.52
 Routing Information
Protocol (RIP)
 RIP routers advertise the cost of reaching
different networks
 the cost is defined as the number of hops,
which means the number of networks
(subnets) a packet needs to travel through
from the source router to the final
destination host.
 Maximum cost of a path can be 15

22.53
22.54
22.55
  third column is not needed for forwarding
the packet, but it is needed for updating
the forwarding table when there is a
change in the route

22.56
  RIP is implemented as a process that uses
the service of UDP on the well-known
port
number 520.
RIP is a daemon process (a process running
in the background)
 RIP runs at the application layer, but

creates forwarding tables for IP at the

network later
22.57
 RIP has two types of messages: request and
response

22.58
  A request message is sent by a router that
has just come up
 A response (or update) message can be
either solicited or unsolicited
 sent periodically, every 30 seconds or
when there is a change in the
forwarding table.

22.59
  Timers in RIP
RIP uses three timers to support its
operation. The periodic timer controls the
advertising of regular update messages
(25 - 35 seconds)
 Update Messages. The update

messages in RIP have a very simple

format and are sent only to neighbors;
they are local.
 Convergence of Forwarding
Tables.
22.60
RIP uses the distance-vector algorithm
  problems that may slow down
convergence are count-to-infinity and
loops created in the domain
Robustness
each router sends what it knows about the
whole domain to its neighbors
 calculation of the forwarding table

depends on information received from

immediate neighbors

22.61
 Figure 22.19 Example of a domain using
RIP

22.62
 Figure 22.20 Concept of link state
routing

22.63
 Figure 22.21 Link state
knowledge

22.64
Link state routing
This method uses the term link-state to
define the characteristic of a link (an edge)
that represents a network in the internet.
cost associated with an edge defines the
state of the link
each node needs to have a complete map of
the network, which means it needs to know
the state of each link.
In the distance-vector routing algorithm,
each router tells its neighbors what
it knows about the whole internet; in the
link-state routing algorithm, each router tells
the whole internet what it knows about its
neighbors
  There is only one LSDB((link-state
database). for the whole internet; each
node needs to have a duplicate of it to be
able to create the least-cost tree
 each node needs to have a duplicate of it
to be able to create the least-cost tree.
 how each node can create this LSDB?
 send some greeting messages to all its
immediate neighbors
 identity of the node and the cost of the
link. LS packet (LSP);
22.67
create this LSDB with flooding
collect two pieces of information for each
neighboring node: the identity of the node
and the cost of the link
after receiving all new LSPs, each node
creates the comprehensive
LSDB
This LSDB is the same for each node and
shows the
whole map of the internet.
In the distance-vector routing algorithm,
each router tells its neighbors what
it knows about the whole internet; in the
link-state routing algorithm, each router tells
the whole internet what it knows about its
neighbors
To create a least-cost tree for itself, using
the shared LSDB, each node needs to run
the famous Dijkstra Algorithm
1. The node chooses itself as the root of the
tree, creating a tree with a single node,
and sets the total cost of each node based on the
information in the LSDB.
2. The node selects one node, among all
nodes not in the tree, which is closest to the
root, and adds this to the tree. After this node is
added to the tree, the cost of all other
nodes not in the tree needs to be updated because
the paths may have been changed.
3. The node repeats step 2 until all nodes are
added to the tree
Lines 4 to 13 implement step 1 in the
algorithm. Lines 16 to 23 implement step 2
in the algorithm. Step 2 is repeated until all
nodes are added to the tree
22.72
22.73
22.74
 Figure 22.22 Dijkstra
algorithm

22.75
 Figure 22.23 Example of formation of shortest path
tree

22.76
 Table 20.2: Dijkstra’s Algorithm

20.77
 Table 22.2 Routing table for node
A

22.78
 OSPF
 each link (network) can be
assigned a weight based on the
throughput, round-trip time,
reliability
 OSPF router can create a forwarding table

after finding the shortest-path tree

between itself and the destination using
Dijkstra’s algorithm
 if we use the hop count for OSPF,

the tables will be exactly the same as

22.80
22.81
22.82
 • the formation of shortest-path trees in
OSPF requires that all routers flood
the whole AS with their LSPs to
create the global LSDB
• the AS needs to be divided into small
sections called areas (to avoid large
traffic)
• OSPF uses level of hierarchy in
routing:
• the first level is the autonomous
system, the second is the area
22.83
 Figure 22.24 Areas in an autonomous
system

22.84
 Figure 20.23: OSPF message formats (Part I)

Attention

20.85
 Figure 20.23: OSPF message formats (Part II)

Attention

20.86
IP datagram that carries a message from
OSPF sets the value of the protocol field to
89
  hello message (type 1) is used by a router
to introduce itself to the neighbors
 database description message (type 2) is
normally sent in response to the hello
message to allow a newly joined router to
acquire the full LSDB.
 Linkstate request message (type 3) is sent
by a router that needs information about
a specific LS.

22.88
  link-state update message (type 4) is the
main OSPF message used for building
the LSDB
 link-state acknowledgment message
(type
5) is used to create reliability in OSPF;
each router that receives a link-state
update message needs to
acknowledge it.

22.89
SR.NO RIP OSPF
1 RIP Stands for Routing Information Protocol. OSPF stands for Open Shortest Path First.

2 RIP works on Bellman Ford algorithm. OSPF works on Dijkstra algorithm.

It is a Distance Vector protocol and it uses the distance It is a link state protocol and it analyzes different sources
3 like the speed, cost and path congestion while identifying
or hops count to determine the transmission path. the shortest path.

It is basically use for larger size organization in the

4 It is basically use for smaller size organization.
network.

5 It allows a maximum of 15 hops. There is no such restriction on the hop count.

6 It is not a more intelligent dynamic routing protocol. It is a more intelligent routing protocol than RIP.

7 The networks are classified as areas and tables here. The networks are classified as areas, sub areas,
autonomous systems and backbone areas here.

8 Its administrative distance is 120. Its administrative distance is 110.

9 RIP uses UDP(User Datagram Protocol) Protocol. OSPF works for IP(Internet Protocol) Protocol.

10 It calculates the metric in terms of Hop Count. It calculates the metric in terms of bandwidth.
 Figure 22.25 Types of links

22.91
 Figure 22.26 Point-to-point
link

22.92
 Figure 22.27 Transient link

22.93
 Figure 22.28 Stub
link

22.94
A point-to-point link connects two routers without any
other host or router in between.

A transient link is a network with several routers attached

to it. network itself is represented by a node

while there is a metric from each node to the designated

router, there is no metric from the designated router to any
other node.

A stub link is a network that is connected to only one

router.

When the link between two routers is broken, the

administration may create a virtual link between them,
using a longer path that probably goes through
several routers.
 Figure 22.29 Example of an AS and its graphical representation in
OSPF

22.96
Path Vector Routing
Distance vector and link state routing are both intradomain
routing protocols.
They can be used inside an autonomous system
Cannot be used for interdomain routing mostly because of
scalability
Distance vector routing is subject to instability if there are
more than a few hops in the domain of operation.
Link state routing needs a huge amount of resources to
calculate routing tables, heavy traffic because of
flooding
principle of path vector routing is similar to that of
distance vector routing
One node in each autonomous system that acts on behalf
of the entire autonomous system. Speaker node
A speaker node advertises the path, not the metric of the
nodes

Sharing Just as in distance vector routing, in path vector

routing, a speaker in an autonomous system shares its
table with immediate neighbours.

After a while each speaker has a table and knows how to

reach each node in other ASs.

if router Al receives a packet for nodes A3, it knows that

the path is in ASI (the packet is at home

Loop prevention When a router receives a message, it

checks to see if its autonomous system is in the path list to
the destination. If it is,looping is involved and the message
is ignored.
Policy routing. Policy routing can be easily
implemented through path vector
routing. When a router receives a message, it can check
the path. If one of the autonomous systems listed in the
path is against its policy, it can ignore that path
and that destination.

Optimum path.
We definitely cannot include metrics in this route because
each autonomous system that is included in the path may
use a different criterion for the metric.
 Figure 22.30 Initial routing tables in path vector
routing

22.
 Figure 22.31 Stabilized tables for three autonomous
systems

22.
Border Gateway Protocol (BGP)
• Border Gateway Protocol (BGP) is used to Exchange
routing information for the internet and is the protocol
used between ISP which are different ASes.
• The protocol can connect together any internetwork of
autonomous system using an arbitrary topology.
• The only requirement is that each AS have at least one
router that is able to run BGP and that is router connect
to at least one other AS’s BGP router.
• BGP’s main function is to exchange network reach-ability
information with other BGP systems.
• Border Gateway Protocol constructs an autonomous
systems’ graph based on the information exchanged
between BGP routers.
Characteristics of Border Gateway Protocol (BGP):
Inter-Autonomous System Configuration:
The main role of BGP is to provide communication between
two autonomous systems.
BGP supports Next-Hop Paradigm.
Coordination among multiple BGP speakers within the AS
(Autonomous System).
Path Information: BGP advertisement also include path
information, along with the reachable destination and next
destination pair.
Policy Support: BGP can implement policies that can be
configured by the administrator. For ex:- a router running
BGP can be configured to distinguish between the routes
that are known within the AS and that which are known
from outside the AS.
Runs Over TCP.
BGP conserve network Bandwidth.
BGP supports CIDR.
BGP also supports Security.
 Figure 22.32 Internal and external BGP
sessions

22.
Stub AS. A stub AS has only one connection to another
AS. The interdomain data traffic in a stub AS can be either
created or terminated in the AS.
Multihomed AS. A multihomed AS has more than one
connection to other ASs, but it is still only a source or sink
for data traffic.
Transit AS. A transit AS is a multihomed AS that also
allows transient traffic
The path was presented as a list of autonomous systems
but is, in fact, a list of
Attributes well known and optional
A well-known mandatory attribute is one that must appear
in the description of a route.
A well-known discretionary attribute is one that must be
recognized by each router, but is not required to be
included in every update message

ORIGIN AS_PATH. NEXT-HOP

optional attributes transitive and nontransitive.
BGP Sessions A session is a connection that
is established between two BGP
routers only for the sake of exchanging
routing information
 22-4 MULTICAST ROUTING
PROTOCOLS
In this section, we discuss multicasting and multicast
routing protocols.

Topics discussed in this section:

Unicast, Multicast, and Broadcast
Applications
Multicast
Routing Routing
Protocols
22.
 Figure 22.33 Unicasting

22.
 Note

In unicasting, the router forwards the

received packet through
only one of its interfaces.

22.
 Figure 22.34 Multicasting

22.
 Note

In multicasting, the router may

forward the received packet
through several of its interfaces.

22.
 Figure 22.35 Multicasting versus multiple
unicasting

22.
 Note

Emulation of multicasting through

multiple unicasting is not
efficient and may create long
delays, particularly with a large
group.

22.
 Note

In unicast routing, each router in the

domain has a table that defines
a shortest path tree to possible
destinations.

22.
 Figure 22.36 Shortest path tree in unicast
routing

22.
 Note

In multicast routing, each involved

router needs to construct
a shortest path tree for each group.

22.
 Figure 22.37 Source-based tree
approach

22.
 Note

In the source-based tree approach, each

router needs to have one shortest path
tree for each group.

22.
 Figure 22.38 Group-shared tree
approach

22.
 Note

In the group-shared tree approach,

only the core router, which has a
shortest path tree for each group, is
involved in multicasting.

22.
 Figure 22.39 Taxonomy of common multicast protocols

22.
 Note

Multicast link state routing uses the

source-based tree approach.

22.
 Note

Flooding broadcasts packets, but

creates loops in the systems.

22.
 Note

RPF eliminates the loop in the

flooding process.

22.
 Figure 22.40 Reverse path forwarding
(RPF)

22.
 Figure 22.41 Problem with
RPF

22.
 Figure 22.42 RPF Versus RPB

22.
 Note

RPB creates a shortest path broadcast

tree from the source to each destination.
It guarantees that each destination
receives one and only one copy
of the packet.

22.
 Figure 22.43 RPF, RPB, and RPM

22.
 Note

RPM adds pruning and grafting to

RPB to create a multicast shortest
path tree that supports dynamic
membership changes.

22.
 Figure 22.44 Group-shared tree with rendezvous
router

22.
 Figure 22.45 Sending a multicast packet to the rendezvous
router

22.
 Note

In CBT, the source sends the multicast

packet (encapsulated in a unicast
packet) to the core router. The core
router decapsulates the packet and
forwards it to all interested interfaces.

22.
 Note

PIM-DM is used in a dense multicast

environment, such as a LAN.

22.136
 Note

PIM-DM uses RPF and pruning and

grafting strategies to handle
multicasting.
However, it is independent of the
underlying unicast protocol.

22.137
 Note

PIM-SM is used in a sparse multicast

environment such as a WAN.

22.138
 Note

PIM-SM is similar to CBT but uses a

simpler procedure.

22.139
 Figure 22.46 Logical
tunneling

22.140
 Figure 22.47 MBONE

22.141