Network Layer
Network Layer
Network Layer
to
Network
Layer
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Chapter 18: Outline
NETWORK-LAYER SERVICES
PACKET SWITCHING
IPv4 ADDRESSES
FORWARDING OF IP PACKETS
Routing
Chapter 18: Objective
The first section introduces the network layer by defining the
services provided by this layer. It first discusses packetizing. It
then describes forwarding and routing and compares the two.
The section then briefly explains the other services such as
flow, error, and congestion control.
18.6
18.18.1 Packetizing
18.7
18.18.2 Routing and Forwarding
18.8
18-2 PACKET SWITCHING
18.9
18.2.1 Datagram Approach
18.10
Figure 18.3: A connectionless packet-switched network
18.11
18.2.2 Virtual-Circuit Approach
18.12
Figure 18.5: A virtual-circuit packet-switched network
18.13
18-4 IPv4 ADDRESSES
18.15
Figure 18.16: Three different notations in IPv4 addressing
18.16
Figure 18.17: Hierarchy in addressing
18.17
18.4.2 Classful Addressing
18.18
Figure 18.18: Occupation of the address space in classful addressing
18.19
18.4.3 Classless Addressing
18.21
Figure 18.20: Slash notation (CIDR)
18.22
Figure 18.21: Information extraction in classless addressing
18.23
Example 18.1
A classless address is given as 167.199.170.82/27. We can
find the above three pieces of information as follows. The
number of addresses in the network is 232− n = 25 = 32
addresses. The first address can be found by keeping the
first 27 bits and changing the rest of the bits to 0s.
18.24
Example 18.2
We repeat Example 18.1 using the mask. The mask in
dotted-decimal notation is 256.256.256.224 The AND, OR,
and NOT operations can be applied to individual bytes using
calculators and applets at the book website.
18.25
Example 18.3
In classless addressing, an address cannot per se define the
block the address belongs to. For example, the address
230.8.24.56 can belong to many blocks. Some of them are
shown below with the value of the prefix associated with
that block.
18.26
Figure 18.22: Network address
18.27
Example 18.4
An ISP has requested a block of 1000 addresses. Since 1000
is not a power of 2, 1024 addresses are granted. The prefix
length is calculated as n = 32 − log21024 = 22. An available
block, 18.14.12.0/22, is granted to the ISP. It can be seen
that the first address in decimal is 302,910,464, which is
divisible by 1024.
18.28
Example 18.5
An organization is granted a block of addresses with the
beginning address 14.24.74.0/24. The organization needs to
have 3 subblocks of addresses to use in its three subnets:
one subblock of 10 addresses, one subblock of 60 addresses,
and one subblock of 120 addresses. Design the subblocks.
Solution
There are 232– 24 = 256 addresses in this block. The first
address is 14.24.74.0/24; the last address is 14.24.74.255/24.
To satisfy the third requirement, we assign addresses to
subblocks, starting with the largest and ending with the
smallest one.
18.29
Example 18.5 (continued)
a. The number of addresses in the largest subblock, which
requires 120 addresses, is not a power of 2. We allocate 128
addresses. The subnet mask for this subnet can be found as
n1 = 32 − log2 128 = 25. The first address in this block is
14.24.74.0/25; the last address is 14.24.74.127/25.
18.30
Example 18.5 (continued)
c. The number of addresses in the largest subblock, which
requires 120 addresses, is not a power of 2. We allocate 128
addresses. The subnet mask for this subnet can be found as
n1 = 32 − log2 128 = 25. The first address in this block is
14.24.74.0/25; the last address is 14.24.74.127/25.
18.31
Figure 18.23: Solution to Example 4.5
18.32
Example 18.6
Figure 18.24 shows how four small blocks of addresses are
assigned to four organizations by an ISP. The ISP combines
these four blocks into one single block and advertises the
larger block to the rest of the world. Any packet destined for
this larger block should be sent to this ISP. It is the
responsibility of the ISP to forward the packet to the
appropriate organization. This is similar to routing we can
find in a postal network. All packages coming from outside
a country are sent first to the capital and then distributed to
the corresponding destination.
18.33
Figure 18.24: Example of address aggregation
18.34
18.4.4 DHCP
18.35
Figure 18.25: DHCP message format
18.36
Figure 18.26: Option format
18.37
Figure 18.27: Operation of DHCP
18.38
Figure 18.28: FSM for the DHCP client
18.39
18.4.5 NAT
18.41
Figure 18.30: Address translation
18.42
Figure 18.31: Translation
18.43
Table 18.1: Five-column translation table
18.44
18-5 FORWARDING OF IP PACKETS
18.45
18.5.1 Destination Address Forwarding
18.46
FORWARDING
22.47
Figure 22.2 Route method versus next-hop method
22.48
Figure 22.3 Host-specific versus network-specific method
22.49
Figure 22.4 Default method
22.50
Figure 18.32: Simplified forwarding module in classless address
18.51
Example 18.7
Make a forwarding table for router R1 using the
configuration in Figure 18.33.
Solution
Table 18.2 shows the corresponding table.
18.52
Figure 18.33: Configuration for Example 4.7
18.53
Example 18.8
Instead of Table 18.2, we can use Table 18.3, in which the
network address/mask is given in bits.
Table 18.3: Forwarding table for router R1 using prefix bits
Solution
The router performs the following steps:
18. The first mask (/26) is applied to the destination address.
18.56
Figure 18.35: Longest mask matching
18.57
Example 18.10
As an example of hierarchical routing, let us consider Figure
18.36. A regional ISP is granted 16,384 addresses starting
from 120.14.64.0. The regional ISP has decided to divide
this block into 4 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 figure also shows how local and small ISPs have
assigned addresses.
18.58
Figure 18.35: Hierarchical routing with ISPs
18.59
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.60
Figure 22.12 Autonomous systems
22.61
Figure 22.13 Popular routing protocols
22.62
Figure 22.14 Distance vector routing tables
22.63
Figure 22.15 Initialization of tables in distance vector routing
22.64
Note
22.65
Figure 22.16 Updating in distance vector routing
22.66
Figure 22.17 Two-node instability
22.67
Figure 22.18 Three-node instability
22.68
Figure 22.19 Example of a domain using RIP
22.69
Figure 22.20 Concept of link state routing
22.70
Figure 22.21 Link state knowledge
22.71
Figure 22.22 Dijkstra algorithm
22.72
Figure 22.23 Example of formation of shortest path tree
22.73
Table 22.2 Routing table for node A
22.74
Figure 22.24 Areas in an autonomous system
22.75
Figure 22.25 Types of links
22.76