Network Layer

Chapter 4

1
Chapter 4: outline
4.1 Introduction 4.5 routing algorithms
4.2 Virtual circuit and  link state
datagram networks  distance vector
4.4 IP: Internet Protocol 4.6 routing in the Internet
 datagram format  RIP
 IPv4 addressing  OSPF
 ICMP  BGP
 IPv6

Network Layer 4-2

2
Network layer
application
 transport segment from transport
network

sending to receiving host data link

physical
network network

 on sending side encapsulates network

data link
data link
physical
data link
physical

segments into datagrams physical network

data link
network
data link

on receiving side, delivers

physical physical

segments to transport layer network
data link
network
data link
physical
physical

network layer protocols in

network
 data link
physical

every host, router network

application
transport

router examines header

data link network network
 network physical data link data link
data link physical physical
fields in all IP datagrams physical

passing through it

Network Layer 4-3

et's break down the process of how data is transported from a sending host to a
receiving host in a computer network, including the roles of routers and the network
layer:
1.Sender: Imagine you have a computer that wants to send some data to another
computer over the internet. The data is divided into small pieces called "segments."
These segments are like individual parts of a message.
2.Sender's Job: The sender's computer takes these segments and puts them inside
something called a "datagram." You can think of a datagram as an envelope that
holds the segments. This datagram is prepared for sending.
3.Sender to Link Layer: The sender's computer then hands over the datagram to
another part of the computer called the "link layer." This link layer is responsible for
getting data ready to be sent over the network.
4.Receiver's Job: Now, let's switch to the receiving end. The datagram arrives at the
receiving computer. The receiving computer's job is to take the datagram apart and
get the segments out. This is like opening the envelope to read the message inside.
5.Delivering Segments: The segments are delivered to the appropriate part of the
receiving computer called the "transport layer protocol." This layer knows how to put
the segments back together in the right order to reconstruct the original data.
Now, let's talk about the role of routers in this process:

3
•Routers: Routers are like traffic cops on the internet. They help in moving data from
one place to another. Here's what routers do:
•a. Examining Header Fields: Routers check the information on the outside of the
datagram, called "header fields." These fields contain important information like the
destination of the datagram.
•b. Moving Datagrams: Routers decide where to send the datagram next based on
the information in the header. They have a map of the network and know which path
to take. So, they move datagrams from one part of the network to another, kind of
like directing traffic on the road.
•c. End-to-End Path: Routers help the datagram travel along the best path from the
sender to the receiver. They make sure it reaches its destination by passing through a
series of routers until it finally arrives at the receiving host.
In a nutshell, the sender prepares data in segments, wraps them in a datagram, and
hands it to the link layer. Routers along the way read the address on the datagram's
envelope and guide it through the network to reach the receiving computer. The
receiving computer then unpacks the segments and delivers them to the transport
layer, which puts them together to complete the data transfer.

3
Two key network-layer functions
 forwarding: move packets
from router’s input to
appropriate router output
 routing: determine route forwarding
taken by packets from
source to dest.
 routing algorithms
routing

Network Layer 4-4

1.Forwarding:
1. Think of forwarding as the immediate decision a router makes when a packet arrives at it.
It's like a traffic cop at an intersection.
2. Imagine a router as a crossroads where different roads meet (input links). When a packet
comes in, the router quickly figures out which road (output link) the packet needs to take
to continue its journey.
3. The router's job is to make sure the packet goes in the right direction, just like the traffic
cop directing cars to the correct lanes.
2.Routing:
1. Routing is like planning a trip from your home to a friend's house. It's about deciding the
best path for your data packets to travel from the source (your home) to the destination
(your friend's house).
2. In computer networks, routing is the process of determining the most efficient route for
packets to travel through a network of routers to reach their final destination.
3. Imagine you have a map with different routes marked on it. You look at the map and
choose the best path to follow. In networking, routing algorithms do something similar;
they determine the best path for your data packets.
3.Routing Algorithms:
1. These are like smart algorithms or rules that routers and computers use to decide the

4
best path for data packets.
2. Think of routing algorithms as GPS systems for your data. They consider
factors like the shortest route, fastest route, or routes with the least
traffic to decide how to send your data efficiently.
3. These algorithms use information about the network's current conditions
and the destination address to make the right decisions, just like how you
use real-time traffic data on your GPS to avoid congestion.

4
Interplay between routing and forwarding

routing algorithm routing algorithm determines

end-end-path through network

local forwarding table forwarding table determines

header value output link local forwarding at this router
0100 3
0101 2
0111 2
1001 1

value in arriving
packet’s header
0111 1

3 2

Network Layer 4-5

Forwarding refers to the router-local action of transferring a packet from an input link
interface to the appropriate output link interface.
Routing refers to the network-wide process that determines the end-to-end paths
that packets take from source to destination.
Every router has a forwarding table. A router forwards a packet by examining the
value of a field in the arriving packet’s header, and then using this header
value to index into the router’s forwarding table. The value stored in the forwarding
table entry for that header indicates the router’s outgoing link interface to
which that packet is to be forwarded. Depending on the network-layer protocol, the
header value could be the destination address of the packet or an indication of the
connection to which the packet belongs.
In the Figure, a packet with a header field value of 0111 arrives to a router. The router
indexes into its forwarding table and determines that the output link
interface for this packet is interface 2. The router then internally forwards the packet
to interface 2.

5
Connection setup
 3rd important function in some network architectures:
 ATM, frame relay, X.25
 before datagrams flow, two end hosts and intervening
routers establish virtual connection
 routers get involved
 network vs transport layer connection service:
 network: between two hosts (may also involve intervening
routers in case of VCs)
 transport: between two processes

Network Layer 4-6

A three-way handshake is required before data can flow from sender to receiver.
This allows the sender and receiver to set up the needed state information (for
example, sequence number and initial flow-control window size).
Some network-layer architectures require the routers along the chosen path from
source to destination to handshake with each other in order to set up state before
network-layer data packets within a given source-to-destination connection can begin
to flow. In the network layer, this process is referred to as connection setup.

6
Network service model
Q: What service model for “channel” transporting
datagrams from sender to receiver?
example services for example services for a
individual datagrams: flow of datagrams:
 guaranteed delivery  in-order datagram
 guaranteed delivery with delivery
(bounded)delay  guaranteed minimum
bandwidth to flow.
 Guaranteed maximum
jitter
 Security services
specific services that could be provided by the
network layer
Network Layer 4-7

The network service model defines the characteristics of end-to-end transport of packets between
sending and receiving end systems.
In the sending host, when the transport layer passes a packet to the network layer, specific services
that could be provided by the network layer include:
• Guaranteed delivery. This service guarantees that the packet will eventually arrive at its destination.
• Guaranteed delivery with bounded delay. This service not only guarantees delivery of the packet,
but delivery within a specified host-to-host delay bound (for example, within 100 msec).
Furthermore, the following services could be provided to a flow of packets between a given source
and destination:
• In-order packet delivery. This service guarantees that packets arrive at the destination in the order
that they were sent.
• Guaranteed minimal bandwidth. This network-layer service emulates the behavior of a
transmission link of a specified bit rate (for example, 1 Mbps) between sending and receiving hosts.
As long as the sending host transmits bits (as part of packets) at a rate below the specified bit rate,
then no packet is lost and each packet arrives within a prespecified host-to-host delay (for example,
within 40 msec).
• Guaranteed maximum jitter. This service guarantees that the amount of time between the
transmission of two successive packets at the sender is equal to the
amount of time between their receipt at the destination.

7
• Security services. Using a secret session key known only by a source and destination
host, the network layer in the source host could encrypt the payloads of
all datagrams being sent to the destination host. The network layer in the destination
host would then be responsible for decrypting the payloads. Helps with
Confidentiality.

7
Network layer service models:

The Internet’s network layer provides a single service, known as best-effort service.
With best-effort service, timing between packets is not guaranteed
to be preserved, packets are not guaranteed to be received in the order in which they
were sent, nor is the eventual delivery of transmitted packets guaranteed.

Constant bit rate (CBR) ATM network service is used for carrying real-time, constant
bit rate audio and video traffic. The goal of CBR service is to provide a flow of packets
(known as cells in ATM terminology) with a virtual pipe whose properties are the
same as if a dedicated fixed-bandwidth transmission link existed between sending
and receiving hosts.

Available bit rate (ABR) ATM network service might best be characterized as being a
slightly-better-than-best-effort service. A minimum cell transmission rate (MCR) is
guaranteed to a connection using ABR service. ATM ABR service can provide feedback
to the sender that controls how the sender adjusts its rate between the MCR and an
allowable peak cell rate.

8
Chapter 4: outline
4.1 introduction 4.5 routing algorithms
4.2 virtual circuit and datagram  link state
networks  distance vector
4.3 what’s inside a router  hierarchical routing
4.4 IP: Internet Protocol 4.6 routing in the Internet
 datagram format  RIP
 IPv4 addressing  OSPF
 ICMP  BGP
 IPv6 4.7 broadcast and multicast
routing

Network Layer 4-9

9
Connection, connection-less service
 datagram network provides network-layer
connectionless service
 virtual-circuit network provides network-layer
connection service
 analogous to TCP/UDP connecton-oriented /
connectionless transport-layer services, but:
 service: host-to-host
 no choice: network provides one or the other
 implementation: in network core

Network Layer 4-10

Computer networks that provide only a connection service at the network layer are
called virtual-circuit (VC) networks; computer networks that provide only a
connectionless service at the network layer are called datagram networks.

Virtual-circuit and datagram networks are two fundamental classes of computer

networks. They use very different information in making their forwarding decisions.

10
Virtual circuits
“source-to-dest path behaves much like telephone
circuit”
 performance-wise
 network actions along source-to-dest path

 call setup, teardown for each call before data can flow
 each packet carries VC identifier (not destination host
address)
 every router on source-dest path maintains “state” for
each passing connection
 link, router resources (bandwidth, buffers) may be
allocated to VC (dedicated resources = predictable
service)
Network Layer 4-11

While the Internet is a datagram network, many alternative network architectures

including those of ATM and frame relay—are virtual-circuit networks and, there-
fore, use connections at the network layer. These network-layer connections are
called virtual circuits (VCs)

11
VC implementation
a VC consists of:
1. path from source to destination
2. VC numbers, one number for each link along path
3. entries in forwarding tables in routers along path
 packet belonging to VC carries VC number
(rather than dest address)
 VC number can be changed on each link.
 new VC number comes from forwarding table

Network Layer 4-12

A VC consists of
(1) a path (that is, a series of links and routers) between the source and destination
hosts,
(2) VC numbers, one number for each link along the path, and
(3) entries in the forwarding table in each router along the path.

A packet belonging to a virtual circuit will carry a VC number in its header. Because a
virtual circuit may have a different VC number on each link, each intervening router
must replace the VC number of each traversing packet with a new VC number. The
new VC number is obtained from the forwarding table.

12
VC forwarding table
R1
12 22 32

1 3
2
VC number
interface
forwarding table in number
northwest router:
Incoming interface Incoming VC # Outgoing interface Outgoing VC #

1 12 3 22
2 63 1 18
3 7 2 17
1 97 3 87
… … … …

VC routers maintain connection state information!

Network Layer 4-13

The numbers next to the links of R1 are the link interface numbers. Suppose now
that Host A requests that the network establish a VC between itself and Host B.
Suppose also that the network chooses the path A-R1-R2-B and assigns VC numbers
12, 22, and 32 to the three links in this path for this virtual circuit. In this case, when a
packet in this VC leaves Host A, the value in the VC number field in the packet header
is 12; when it leaves R1, the value is 22; and when it leaves R2, the value is 32.

How does the router determine the replacement VC number for a packet traversing
the router? For a VC network, each router’s forwarding table includes VC 4.2 •
number translation. Whenever a new VC is established across a router, an entry is
added to the forwarding table. Similarly, whenever a VC terminates, the appropriate
entries in each table along its path are removed.

13
Virtual circuits
 signaling protocols used to setup, maintain
teardown VC
 used in ATM, frame-relay, X.25
 not used in today’s Internet
Virtual-circuit setup

application application
5. data flow begins 6. receive data
transport transport
network 4. call connected 3. accept call
1. initiate call network
data link 2. incoming call
data link
physical physical

Network Layer 4-14

There are three identifiable phases in a virtual circuit:

• VC setup. • Data transfer. • VC teardown.

There is a subtle but important distinction between VC setup at the network layer
and connection setup at the transport layer. Connection setup at the transport layer
involves only the two end systems. On the other hand, with a VC network layer,
routers along the path between the two end systems are involved in VC setup, and
each router is fully aware of all the VCs passing through it.

The messages that the end systems send into the network to initiate or terminate a
VC, and the messages passed between the routers to set up the VC are known as
signaling messages, and the protocols used to exchange these messages are often
referred to as signaling protocols.

14
Datagram networks
 no call setup at network layer
 routers: no state about end-to-end connections
 no network-level concept of “connection”
 packets forwarded using destination host address

application application
transport transport
network 1. send data 2. receive data network
data link data link
physical physical

Network Layer 4-15

In a datagram network, each time an end system wants to send a packet, it stamps
the packet with the address of the destination end system and then pops the packet
into the network. There is no VC setup and routers do not maintain any VC state
information (because there are no VCs!)

As a packet is transmitted from source to destination, it passes through a series of

routers. Each of these routers uses the packet’s destination address to forward the
packet. Specifically, each router has a forwarding table that maps destination
addresses to link interfaces; when a packet arrives at the router, the router uses the
packet’s destination address to look up the appropriate output link interface in the
forwarding table. The router then intentionally forwards the packet to that output
link interface.

15
Datagram forwarding table
4 billion IP addresses, so
routing algorithm rather than list individual
destination address
local forwarding table
list range of addresses
dest address output link (aggregate table entries)
address-range 1 3
address-range 2 2
address-range 3 2
address-range 4 1

IP destination address in
arriving packet’s header
1
3 2

Network Layer 4-16

Routers in datagram networks maintain forwarding state information in their

forwarding tables. The forwarding tables are modified by the routing algorithms,
which typically update a forwarding table every one-to-five minutes or so.

16
Figure 4.3: A connectionless packet-switched network

4.17

Because forwarding tables in datagram networks can be modified at any time, a

series of packets sent from one end system to another may follow different paths
through the network and may arrive out of order.

1.#
Figure 4.4: Forwarding process in a router when used in a
connectionless network

SA DA Data SA DA Data

4.18

1.18

1.#
Consider the network below.
a. Suppose that this network is a datagram network. Show the forwarding table in router A,
such that all traffic destined to host H3 is forwarded through interface 3.
b. Suppose that this network is a datagram network. Can you write down a forwarding table in
router A, such that all traffic from H1 destined to host H3 is forwarded through interface 3,
while all traffic from H2 destined to host H3 is forwarded through interface 4? (Hint: this is a
trick question.)
c. Now suppose that this network is a virtual circuit network and that there is one ongoing call
between H1 and H3, and another ongoing call between H2 and H3. Write down a forwarding
table in router A, such that all traffic from H1 destined to host H3 is forwarded through interface
3, while all traffic from H2 destined to host H3 is forwarded through interface 4.
d. Assuming the same scenario as (c), write down the forwarding tables in nodes B, C, and D.

a) Taken the given data and figure:

Suppose that the forwarding table in router A, such that all traffic destined to host
H3 is forwarded through interface 3 in datagram network..
It contains,
•Destination address
•Link Interface
The destination address is H3 and link interface is 3.
b)
No.
It is not possible for a forwarding table in router A, such that all traffic from H1
destined to host H3 is forwarded through interface 3, while all traffic from H2
destined to host H3 is forwarded through interface 4.
c)
Suppose that this network is a virtual circuit network and that there is one ongoing
call between H1 and H3, and another ongoing call between H2 and H3.
After clear observations, the forwarding table in router A, such that all traffic from H1
destined to host H3 is forwarded through interface 3, while all traffic from H2
destined to host H3 is forwarded through interface 4 is as follows:

19
Suppose there are three routers between a source host and a destination host.
Ignoring fragmentation, an IP datagram sent from the source host to the
destination host will travel over how many interfaces? How many forwarding tables
will be indexed to move the datagram from the source to the destination?

An IP datagram sent from the source host to the destination host will travel over 8
interfaces.
3 forwarding tables will be indexed to move the datagram from the source to the
destination

20
Datagram forwarding table
Destination Address Range Link Interface

11001000 00010111 00010000 00000000

through 0
11001000 00010111 00010111 11111111

11001000 00010111 00011000 00000000

through 1
11001000 00010111 00011000 11111111

11001000 00010111 00011001 00000000

through 2
11001000 00010111 00011111 11111111

otherwise 3

Q: but what happens if ranges don’t divide up so nicely?

Network Layer 4-21

suppose that our router has four links, numbered 0 through 3, and that packets are
to be forwarded to the link interfaces as shown. Clearly, for this example, it is not
necessary to have 4 billion entries in the router’s forwarding table.

21
Longest prefix matching
longest prefix matching
when looking for forwarding table entry for given
destination address, use longest address prefix that
matches destination address.

Destination Address Range Link interface

11001000 00010111 00010*** ********* 0

11001000 00010111 00011000 ********* 1

11001000 00010111 00011*** ********* 2

otherwise 3

examples:
DA: 11001000 00010111 00010110 10100001 which interface?
DA: 11001000 00010111 00011000 10101010 which interface?
Network Layer 4-22

We could, for example, have the following forwarding table with just four entries
equivalent to the previous one.

With this style of forwarding table, the router matches a prefix of the packet’s
destination address with the entries in the table; if there’s a match, the router
forwards the packet to a link associated with the match.

For example, suppose the packet’s destination address is 11001000 00010111

00010110 10100001; because the 21-bit prefix of this address matches the first entry
in the table, the router forwards the packet to link interface 0. If a prefix doesn’t
match any of the first three entries, then the router forwards the packet to interface
3.

22
Consider a datagram network using 8-bit host addresses.
Suppose a router uses longest-prefix matching, and has the following forwarding table:

1. Suppose a datagram arrives at the router,

with destination address 00000110. To which
interface will this datagram be forwarded using
longest-prefix matching?

2. Suppose a datagram arrives at the router,

with destination address 10010000. To which
interface will this datagram be forwarded using
longest-prefix matching?

3. Suppose a datagram arrives at the router,

with destination address 00010111. To which
interface will this datagram be forwarded using
longest-prefix matching?

1. Since the address is 00000110, it will go to interface 1.

2. Since the address is 10010000, it will go to interface 2.

3. Since the address is 00010111, it will go to interface 1.

23
Consider a datagram network using 8-bit host addresses.
Suppose a router uses longest-prefix matching, and has the following
forwarding table:

1. Suppose a datagram arrives at the router,

with destination address 11011101. To
which interface will this datagram be
forwarded using longest-prefix matching?

2. Suppose a datagram arrives at the router,

with destination address 01011100. To
which interface will this datagram be
forwarded using longest-prefix matching?

3. Suppose a datagram arrives at the router,

with destination address 01001011. To
which interface will this datagram be
forwarded using longest-prefix matching?

1. Since the address is 11011101, it will go to interface 6.

2. Since the address is 01011100, it will go to interface 6.

3. Since the address is 01001011, it will go to interface 6.

24
Consider a datagram network using 32-bit host addresses. Suppose a router
has four links, numbered 0 through 3, and packets are to be forwarded to the link
interfaces as follows:

Provide a forwarding table that uses longest prefix matching, and forwards packets to the
correct link interfaces.
Describe how your forwarding table determines the appropriate link interface for
datagrams with destination addresses:
11001000 10010001 01010001 01010101
11100001 01000000 11000011 00111100
11100001 10000000 00010001 01110111

a)
Prefix Match Link Interface
11100000 00 0
11100000 01000000 1
11100000 2
11100001 0 2
otherwise 3

b)
Prefix match for address is 5th entry: link interface 3
Prefix match for address is 4th entry: link interface 2
Prefix match for address is 5th entry: link interface 3

25
Consider a datagram network using 8-bit host addresses. Suppose a router
uses longest prefix matching and has the following forwarding table:

For each of the four interfaces, give the associated range of destination host
addresses and the number of addresses in the range.

Destination Address Range Link Interface

00000000 – 00111111 0
01000000 – 01011111 1
01100000 – 01111111 2
10000000 – 10111111 2
11000000 – 11111111 3
number of addresses for interface 0 = 2pow6 =64
number of addresses for interface 1 = 2pow5 =32
number of addresses for interface 2 = 2pow5 +2pow6 =32+64 =96
number of addresses for interface 3 = 2pow6 =64

26
Datagram or VC network: why?
Internet (datagram) ATM (VC)
 data exchange among  evolved from telephony
computers  human conversation:
 “elastic” service, no strict  strict timing, reliability
timing req. requirements
 need for guaranteed
 many link types service
 different characteristics  “dumb” end systems
 uniform service difficult  telephones
 “smart” end systems  complexity inside network
(computers)
 can adapt, perform control,
error recovery
 simple inside network,
complexity at “edge”

Network Layer 4-27

27
Chapter 4: outline
4.1 introduction 4.5 routing algorithms
4.2 virtual circuit and  link state
datagram networks  distance vector
4.3 what’s inside a router  hierarchical routing
4.4 IP: Internet Protocol 4.6 routing in the Internet
 datagram format  RIP
 IPv4 addressing  OSPF
 ICMP  BGP
 IPv6 4.7 broadcast and multicast
routing

Network Layer 4-28

28
Router architecture overview
two key router functions:
 run routing algorithms/protocol (RIP, OSPF, BGP)
 forwarding datagrams from incoming to outgoing link

forwarding tables computed, routing routing, management

pushed to input ports
processor
control plane (software)

forwarding data
plane (hardware)

high-seed
switching
fabric

router input ports router output ports

Network Layer 4-29

29
Input port functions
lookup,
link forwarding
line layer switch
termination protocol fabric
(receive)
queueing

physical layer:
bit-level reception
data link layer: decentralized switching:
e.g., Ethernet  given datagram dest., lookup output port
see chapter 5 using forwarding table in input port
memory (“match plus action”)
 goal: complete input port processing at
‘line speed’
 queuing: if datagrams arrive faster than
forwarding rate into switch fabric
Network Layer 4-30

30
Switching fabrics
 transfer packet from input buffer to appropriate
output buffer
 switching rate: rate at which packets can be
transfer from inputs to outputs
 often measured as multiple of input/output line rate
 N inputs: switching rate N times line rate desirable
 three types of switching fabrics

memory

memory bus crossbar

Network Layer 4-31

31
Switching via memory
first generation routers:
 traditional
computers with switching under direct control of
CPU
 packet copied to system’s memory
 speed limited by memory bandwidth (2 bus crossings per
datagram)

input output
port memory port
(e.g., (e.g.,
Ethernet) Ethernet)

system bus

Network Layer 4-32

32
Switching via a bus
 datagram from input port memory
to output port memory via a
shared bus
 bus contention: switching speed
limited by bus bandwidth
 32 Gbps bus, Cisco 5600: sufficient bus
speed for access and enterprise
routers

Network Layer 4-33

33
Switching via interconnection network
 overcome bus bandwidth limitations
 banyan networks, crossbar, other
interconnection nets initially
developed to connect processors in
multiprocessor
 advanced design: fragmenting
datagram into fixed length cells, crossbar
switch cells through the fabric.
 Cisco 12000: switches 60 Gbps
through the interconnection network

Network Layer 4-34

34
Output ports This slide in HUGELY important!

datagram
switch buffer link
fabric layer line
protocol termination
queueing (send)

 buffering required when datagrams

Datagram arrivecan
(packets) frombe lost
fabric faster than the transmission rate
due to congestion, lack of buffers
 scheduling discipline chooses among queued
datagrams for transmission
Priority scheduling – who gets best
performance, network neutrality
Network Layer 4-35

35
Output port queueing

switch
switch
fabric
fabric

at t, packets more one packet time later

from input to output

 buffering when arrival rate via switch exceeds

output line speed
 queueing (delay) and loss due to output port
buffer overflow!
Network Layer 4-36

36
How much buffering?
 RFC 3439 rule of thumb: average buffering equal
to “typical” RTT (say 250 msec) times link
capacity C
 e.g., C = 10 Gpbs link: 2.5 Gbit buffer
 recent recommendation: with N flows, buffering
equal to
RTT . C
N

Network Layer 4-37

37
Input port queuing
 fabric slower than input ports combined -> queueing may
occur at input queues
 queueing delay and loss due to input buffer overflow!
 Head-of-the-Line (HOL) blocking: queued datagram at front
of queue prevents others in queue from moving forward

switch switch
fabric fabric

output port contention: one packet time later:

only one red datagram can be green packet
transferred. experiences HOL
lower red packet is blocked blocking

Network Layer 4-38

38
Chapter 4: outline
4.1 introduction 4.5 routing algorithms
4.2 virtual circuit and  link state
datagram networks  distance vector
4.3 what’s inside a router  hierarchical routing
4.4 IP: Internet Protocol 4.6 routing in the Internet
 datagram format  RIP
 IPv4 addressing  OSPF
 ICMP  BGP
 IPv6 4.7 broadcast and multicast
routing

Network Layer 4-39

39
The Internet network layer
host, router network layer functions:

transport layer: TCP, UDP

routing protocols IP protocol

• path selection • addressing conventions
• RIP, OSPF, BGP • datagram format
network • packet handling conventions
layer forwarding
table
ICMP protocol
• error reporting
• router
“signaling”
link layer

physical layer

Network Layer 4-40

40
IP datagram format
IP protocol version 32 bits
number total datagram
header length type of length (bytes)
ver head. length
(bytes) len service for
“type” of data fragment fragmentation/
16-bit identifier flgs
offset reassembly
max number time to upper header
remaining hops live layer checksum
(decremented at
32 bit source IP address
each router)
32 bit destination IP address
upper layer protocol
to deliver payload to options (if any) e.g. timestamp,
record route
how much overhead? data taken, specify
(variable length, list of routers
 20 bytes of TCP
typically a TCP to visit.
 20 bytes of IP
or UDP segment)
 = 40 bytes + app
layer overhead

Network Layer 4-41

41
IP fragmentation, reassembly
 network links have MTU
(max.transfer size) -
largest possible link-level fragmentation:
frame

…
in: one large datagram
 different link types, out: 3 smaller datagrams
different MTUs
 large IP datagram divided
(“fragmented”) within net reassembly
 one datagram
becomes several
datagrams

…
 “reassembled” only at
final destination
 IP header bits used to
identify, order related
fragments Network Layer 4-42

To allow the destination host to perform these reassembly tasks, the designers of IP
(version 4) put identification, flag, and fragmentation offset fields in the IP datagram
header. When a datagram is created, the sending host stamps the datagram with an
identification number as well as source and destination addresses. Typically, the
sending host increments the identification number for each datagram it sends. When
a router needs to fragment a datagram, each resulting datagram (that is, fragment) is
stamped with the source address, destination address, and identification number of
the original datagram. When the destination receives a series of datagrams from the
same sending host, it can examine the identification numbers of the datagrams to
determine which of the datagrams are actually fragments of the same larger
datagram. Because IP is an unreliable service, one or more of the fragments may
never arrive at the destination. For this reason, in order for the destination host to be
absolutely sure it has received the last fragment of the original datagram, the last
fragment has a flag bit set to 0, whereas all the other fragments have this flag bit set
to 1. Also, in order for the destination host to determine whether a fragment is
missing (and also to be able to reassemble the fragments in their proper order), the
offset field is used to specify where the fragment fits within the original IP datagram

42
***IP fragmentation, reassembly
length ID fragflag offset
example: =4000 =x =0 =0
 4000 byte datagram
one large datagram becomes
 MTU = 1500 bytes several smaller datagrams

1480 bytes in length ID fragflag offset

data field =1500 =x =1 =0

offset = length ID fragflag offset

1480/8 =1500 =x =1 =185

length ID fragflag offset

=1040 =x =0 =370

Network Layer 4-43

A datagram of 4,000 bytes (20 bytes of IP header plus 3,980 bytes of IP payload)
arrives at a router and must be forwarded to a link with an MTU of 1,500 bytes. This
implies that the 3,980 data bytes in the original datagram must be allocated to three
separate fragments (each of which is also an IP datagram). Suppose that the original
datagram is stamped with an identification number of 777. The characteristics of the
three fragments are shown in Table. The values in Table reflect the requirement that
the amount of original payload data in all but the last fragment be a multiple of 8
bytes, and that the offset value be specified in units of 8-byte chunks.

43
An IP packet of size 1600 bytes passes through network
segment before it reaches its destination. The header size
of this packet is 30 bytes. The maximum size of an IP
packet in intermediate network (MTU) is 1400 bytes. How
the IP packet would be fragmented in a router. Find all the
information for each fragments.

44
Chapter 4: outline
4.1 introduction 4.5 routing algorithms
4.2 virtual circuit and  link state
datagram networks  distance vector
4.3 what’s inside a router  hierarchical routing
4.4 IP: Internet Protocol 4.6 routing in the Internet
 datagram format  RIP
 IPv4 addressing  OSPF
 ICMP  BGP
 IPv6 4.7 broadcast and multicast
routing

Network Layer 4-45

45
IP addressing: introduction
223.1.1.1
 IP address: 32-bit 223.1.2.1
identifier for host, router
interface 223.1.1.2
223.1.1.4 223.1.2.9
 interface: connection
between host/router and 223.1.3.27
physical link 223.1.1.3
223.1.2.2
 router’s typically have
multiple interfaces
 host typically has one or
two interfaces (e.g., wired 223.1.3.1 223.1.3.2

Ethernet, wireless 802.11)

 IP addresses associated
with each interface 223.1.1.1 = 11011111 00000001 00000001 00000001

223 1 1 1

Network Layer 4-46

46
IP addressing: introduction
223.1.1.1
Q: how are interfaces
actually connected?
223.1.2.1

A: we’ll learn about that223.1.1.2 223.1.1.4 223.1.2.9

in chapter 5, 6.
223.1.3.27
223.1.1.3
223.1.2.2

A: wired Ethernet interfaces

connected by Ethernet switches
223.1.3.1 223.1.3.2

For now: don’t need to worry

about how one interface is
connected to another (with no
A: wireless WiFi interfaces
intervening router)
connected by WiFi base station

Network Layer 4-47

47
Subnets
 IP address: 223.1.1.1
subnet part - high order
bits 223.1.1.2 223.1.2.1
223.1.1.4 223.1.2.9
host part - low order
bits 223.1.2.2
223.1.3.27
 what ’s a subnet ? 223.1.1.3

device interfaces with subnet

same subnet part of IP
address 223.1.3.1 223.1.3.2

can physically reach

each other without
intervening router network consisting of 3 subnets

Network Layer 4-48

48
Subnets
223.1.1.0/24
223.1.2.0/24
recipe 223.1.1.1

 to determine the 223.1.1.2 223.1.2.1

subnets, detach each 223.1.1.4 223.1.2.9

interface from its host 223.1.2.2

or router, creating 223.1.1.3 223.1.3.27

islands of isolated subnet

networks
223.1.3.2
 each isolated network 223.1.3.1

is called a subnet
223.1.3.0/24

subnet mask: /24

Network Layer 4-49

49
Subnets 223.1.1.2

how many? 223.1.1.1 223.1.1.4

223.1.1.3

223.1.9.2 223.1.7.0

223.1.9.1 223.1.7.1
223.1.8.1 223.1.8.0

223.1.2.6 223.1.3.27

223.1.2.1 223.1.2.2 223.1.3.1 223.1.3.2

Network Layer 4-50

50
IP addressing: CIDR
CIDR: Classless InterDomain Routing
 subnet portion of address of arbitrary length
 address format: a.b.c.d/x, where x is # bits in
subnet portion of address

subnet host
part part
11001000 00010111 00010000 00000000
200.23.16.0/23

Network Layer 4-51

51
IP addresses: how to get one?
Q: How does a host get IP address?

 hard-coded by system admin in a file

 Windows: control-panel->network->configuration-
>tcp/ip->properties
 UNIX: /etc/rc.config
 DHCP: Dynamic Host Configuration Protocol:
dynamically get address from as server
 “plug-and-play”

Network Layer 4-52

52
DHCP: Dynamic Host Configuration Protocol
goal: allow host to dynamically obtain its IP address from network
server when it joins network
 can renew its lease on address in use
 allows reuse of addresses (only hold address while
connected/“on”)
 support for mobile users who want to join network (more
shortly)
DHCP overview:
 host broadcasts “DHCP discover” msg [optional]
 DHCP server responds with “DHCP offer” msg [optional]
 host requests IP address: “DHCP request” msg
 DHCP server sends address: “DHCP ack” msg

Network Layer 4-53

53
DHCP client-server scenario

DHCP
223.1.1.0/24
server
223.1.1.1 223.1.2.1

223.1.1.2 arriving DHCP

223.1.1.4 223.1.2.9
client needs
address in this
223.1.1.3 223.1.3.27
223.1.2.2 network

223.1.2.0/24

223.1.3.1 223.1.3.2

223.1.3.0/24

Network Layer 4-54

54
DHCP client-server scenario
DHCP server: 223.1.2.5 DHCP discover arriving
client
src : 0.0.0.0, 68
Broadcast: is there a
dest.: 255.255.255.255,67
DHCPyiaddr:
server 0.0.0.0
out there?
transaction ID: 654

DHCP offer
src: 223.1.2.5, 67
Broadcast: I’m a DHCP
dest: 255.255.255.255, 68
server!
yiaddrr:Here’s an IP
223.1.2.4
transaction ID:
address you can use654
lifetime: 3600 secs
DHCP request
src: 0.0.0.0, 68
dest:: 255.255.255.255, 67
Broadcast: OK. I’ll take
yiaddrr: 223.1.2.4
that IP address!
transaction ID: 655
lifetime: 3600 secs

DHCP ACK
src: 223.1.2.5, 67
Broadcast: OK. You’ve
dest: 255.255.255.255, 68
yiaddrr: 223.1.2.4
got that IPID:
transaction address!
655
lifetime: 3600 secs

Network Layer 4-55

55
DHCP: more than IP addresses
DHCP can return more than just allocated IP address
on subnet:
 address of first-hop router for client
 name and IP address of DNS sever
 network mask (indicating network versus host portion
of address)

Network Layer 4-56

56
DHCP: example
DHCP DHCP  connecting laptop needs
DHCP UDP its IP address, addr of
IP
first-hop router, addr of
DHCP

DHCP Eth
Phy DNS server: use DHCP
DHCP request encapsulated
DHCP

in UDP, encapsulated in IP,
DHCP DHCP 168.1.1.1 encapsulated in 802.1
DHCP UDP Ethernet
DHCP IP
DHCP Eth router with DHCP
 Ethernet frame broadcast
Phy server built into (dest: FFFFFFFFFFFF) on LAN,
router received at router running
DHCP server
 Ethernet demuxed to IP
demuxed, UDP demuxed to
DHCP

Network Layer 4-57

57
DHCP: example
DHCP DHCP  DCP server formulates
DHCP UDP DHCP ACK containing
DHCP IP client’s IP address, IP
DHCP Eth address of first-hop
Phy router for client, name &
IP address of DNS server
 encapsulation of DHCP
DHCP DHCP server, frame forwarded
DHCP UDP to client, demuxing up to
DHCP IP DHCP at client
DHCP Eth router with DHCP
DHCP
Phy server built into  client now knows its IP
router address, name and IP
address of DSN server, IP
address of its first-hop
router

Network Layer 4-58

58
DHCP: Wireshark Message type: Boot Reply (2)
reply
output (home LAN) Hardware type: Ethernet
Hardware address length: 6
Hops: 0
Transaction ID: 0x6b3a11b7
Seconds elapsed: 0
Message type: Boot Request (1) Bootp flags: 0x0000 (Unicast)
Hardware type: Ethernet Client IP address: 192.168.1.101 (192.168.1.101)
Hardware address length: 6 Your (client) IP address: 0.0.0.0 (0.0.0.0)
Hops: 0
Transaction ID: 0x6b3a11b7
request Next server IP address: 192.168.1.1 (192.168.1.1)
Relay agent IP address: 0.0.0.0 (0.0.0.0)
Seconds elapsed: 0 Client MAC address: Wistron_23:68:8a (00:16:d3:23:68:8a)
Bootp flags: 0x0000 (Unicast) Server host name not given
Client IP address: 0.0.0.0 (0.0.0.0) Boot file name not given
Your (client) IP address: 0.0.0.0 (0.0.0.0) Magic cookie: (OK)
Next server IP address: 0.0.0.0 (0.0.0.0) Option: (t=53,l=1) DHCP Message Type = DHCP ACK
Relay agent IP address: 0.0.0.0 (0.0.0.0) Option: (t=54,l=4) Server Identifier = 192.168.1.1
Client MAC address: Wistron_23:68:8a (00:16:d3:23:68:8a) Option: (t=1,l=4) Subnet Mask = 255.255.255.0
Server host name not given Option: (t=3,l=4) Router = 192.168.1.1
Boot file name not given Option: (6) Domain Name Server
Magic cookie: (OK) Length: 12; Value: 445747E2445749F244574092;
Option: (t=53,l=1) DHCP Message Type = DHCP Request IP Address: 68.87.71.226;
Option: (61) Client identifier IP Address: 68.87.73.242;
Length: 7; Value: 010016D323688A; IP Address: 68.87.64.146
Hardware type: Ethernet Option: (t=15,l=20) Domain Name = "hsd1.ma.comcast.net."
Client MAC address: Wistron_23:68:8a (00:16:d3:23:68:8a)
Option: (t=50,l=4) Requested IP Address = 192.168.1.101
Option: (t=12,l=5) Host Name = "nomad"
Option: (55) Parameter Request List
Length: 11; Value: 010F03062C2E2F1F21F92B
1 = Subnet Mask; 15 = Domain Name
3 = Router; 6 = Domain Name Server
44 = NetBIOS over TCP/IP Name Server
……

Network Layer 4-59

59
IP addresses: how to get one?
Q: how does network get subnet part of IP addr?
A: gets allocated portion of its provider ISP’s address
space

ISP's block 11001000 00010111 00010000 00000000 200.23.16.0/20

Organization 0 11001000 00010111 00010000 00000000 200.23.16.0/23

Organization 1 11001000 00010111 00010010 00000000 200.23.18.0/23
Organization 2 11001000 00010111 00010100 00000000 200.23.20.0/23
... ….. …. ….
Organization 7 11001000 00010111 00011110 00000000 200.23.30.0/23

Network Layer 4-60

60
Hierarchical addressing: route aggregation
hierarchical addressing allows efficient advertisement of routing
information:

Organization 0
200.23.16.0/23
Organization 1
“Send me anything
200.23.18.0/23 with addresses
Organization 2 beginning
200.23.20.0/23 . Fly-By-Night-ISP 200.23.16.0/20”
.
. . Internet
.
Organization 7 .
200.23.30.0/23
“Send me anything
ISPs-R-Us
with addresses
beginning
199.31.0.0/16”

Network Layer 4-61

61
Hierarchical addressing: more specific routes

ISPs-R-Us has a more specific route to Organization 1

Organization 0
200.23.16.0/23

“Send me anything
with addresses
Organization 2 beginning
200.23.20.0/23 . Fly-By-Night-ISP 200.23.16.0/20”
.
. . Internet
.
Organization 7 .
200.23.30.0/23
“Send me anything
ISPs-R-Us
with addresses
Organization 1 beginning 199.31.0.0/16
or 200.23.18.0/23”
200.23.18.0/23

Network Layer 4-62

62
IP addressing: the last word...

Q: how does an ISP get block of addresses?

A: ICANN: Internet Corporation for Assigned
Names and Numbers http://www.icann.org/
 allocates addresses
 manages DNS
 assigns domain names, resolves disputes

Network Layer 4-63

63
NAT: network address translation
rest of local network
Internet (e.g., home network)
10.0.0/24 10.0.0.1

10.0.0.4
10.0.0.2
138.76.29.7

10.0.0.3

all datagrams leaving local datagrams with source or

network have same single destination in this network
source NAT IP address: have 10.0.0/24 address for
138.76.29.7,different source source, destination (as usual)
port numbers
Network Layer 4-64

64
NAT: network address translation
motivation: local network uses just one IP address as far
as outside world is concerned:
 range of addresses not needed from ISP: just one
IP address for all devices
 can change addresses of devices in local network
without notifying outside world
 can change ISP without changing addresses of
devices in local network
 devices inside local net not explicitly addressable,
visible by outside world (a security plus)

Network Layer 4-65

65
NAT: network address translation
implementation: NAT router must:

 outgoing datagrams: replace (source IP address, port #) of

every outgoing datagram to (NAT IP address, new port #)
. . . remote clients/servers will respond using (NAT IP
address, new port #) as destination addr

 remember (in NAT translation table) every (source IP address,

port #) to (NAT IP address, new port #) translation pair

 incoming datagrams: replace (NAT IP address, new port #) in

dest fields of every incoming datagram with corresponding
(source IP address, port #) stored in NAT table

Network Layer 4-66

66
NAT: network address translation
NAT translation table 1: host 10.0.0.1
2: NAT router WAN side addr LAN side addr
changes datagram sends datagram to
source addr from 138.76.29.7, 5001 10.0.0.1, 3345 128.119.40.186, 80
10.0.0.1, 3345 to …… ……
138.76.29.7, 5001,
updates table S: 10.0.0.1, 3345
D: 128.119.40.186, 80
10.0.0.1
1
S: 138.76.29.7, 5001
2 D: 128.119.40.186, 80 10.0.0.4
10.0.0.2
138.76.29.7 S: 128.119.40.186, 80
D: 10.0.0.1, 3345
4
S: 128.119.40.186, 80
D: 138.76.29.7, 5001 3 10.0.0.3
4: NAT router
3: reply arrives changes datagram
dest. address: dest addr from
138.76.29.7, 5001 138.76.29.7, 5001 to 10.0.0.1, 3345

Network Layer 4-67

67
NAT: network address translation
 16-bit port-number field:
 60,000 simultaneous connections with a single
LAN-side address!
 NAT is controversial:
 routers should only process up to layer 3
 violates end-to-end argument
NAT possibility must be taken into account by app
designers, e.g., P2P applications
 address shortage should instead be solved by
IPv6

Network Layer 4-68

68
NAT traversal problem
 client wants to connect to
server with address 10.0.0.1
 server address 10.0.0.1 local to 10.0.0.1
client
LAN (client can’t use it as
destination addr) ?
 only one externally visible NATed 10.0.0.4
address: 138.76.29.7
 solution1: statically configure 138.76.29.7 NAT
NAT to forward incoming router
connection requests at given
port to server
 e.g., (123.76.29.7, port 2500)
always forwarded to 10.0.0.1 port
25000

Network Layer 4-69

69
NAT traversal problem
 solution 2: Universal Plug and Play
(UPnP) Internet Gateway Device
(IGD) Protocol. Allows NATed 10.0.0.1
host to: IGD
 learn public IP address
(138.76.29.7)
 add/remove port mappings
(with lease times) NAT
router

i.e., automate static NAT port

map configuration

Network Layer 4-70

70
NAT traversal problem
 solution 3: relaying (used in Skype)
 NATed client establishes connection to relay
 external client connects to relay
 relay bridges packets between to connections

2. connection to
relay initiated 1. connection to 10.0.0.1
by client relay initiated
by NATed host
3. relaying
client established
138.76.29.7 NAT
router

Network Layer 4-71

71
Chapter 4: outline
4.1 introduction 4.5 routing algorithms
4.2 virtual circuit and  link state
datagram networks  distance vector
4.3 what’s inside a router  hierarchical routing
4.4 IP: Internet Protocol 4.6 routing in the Internet
 datagram format  RIP
 IPv4 addressing  OSPF
 ICMP  BGP
 IPv6 4.7 broadcast and multicast
routing

Network Layer 4-72

72
ICMP: internet control message protocol

 used by hosts & routers to

communicate network- Type Code description
0 0 echo reply (ping)
level information 3 0 dest. network unreachable
 error reporting: 3 1 dest host unreachable
unreachable host, network, 3 2 dest protocol unreachable
port, protocol 3 3 dest port unreachable
 echo request/reply (used 3 6 dest network unknown
by ping) 3 7 dest host unknown
 network-layer “above” IP: 4 0 source quench (congestion
 ICMP msgs carried in IP control - not used)
datagrams 8 0 echo request (ping)
9 0 route advertisement
 ICMP message: type, code 10 0 router discovery
plus first 8 bytes of IP 11 0 TTL expired
datagram causing error 12 0 bad IP header

Network Layer 4-73

73
Traceroute and ICMP
 source sends series of UDP  when ICMP messages
segments to dest arrives, source records
 first set has TTL =1 RTTs
 second set has TTL=2, etc.
 unlikely port number stopping criteria:
 when nth set of datagrams  UDP segment eventually
arrives to nth router: arrives at destination host
 router discards datagrams  destination returns ICMP
 and sends source ICMP “port unreachable”
messages (type 11, code 0) message (type 3, code 3)
 ICMP messages includes
 source stops
name of router & IP address

3 probes 3 probes

3 probes
Network Layer 4-74

74
IP Security
 To communicate securely in the nonsecure public
Internet. E.g. VPN

 The services provided by an IPsec session include:

• Cryptographic agreement.
• Encryption of IP datagram payloads.
• Data integrity.
• Origin authentication.

IPsec, which stands for Internet Protocol Security, is a set of protocols and security
services used to secure Internet Protocol (IP) communications. It provides a
framework for securing network communication at the IP layer, which is the layer
responsible for routing packets of data between devices on a network.
The services provided by an IPsec session include:
• Cryptographic agreement. Mechanisms that allow the two communicating hosts to
agree on cryptographic algorithms and keys.
• Encryption of IP datagram payloads. When the sending host receives a segment
from the transport layer, IPsec encrypts the payload. The payload can only be
decrypted by IPsec in the receiving host.
• Data integrity. IPsec allows the receiving host to verify that the datagram’s header
fields and encrypted payload were not modified while the datagram was en route
from source to destination.
• Origin authentication. When a host receives an IPsec datagram from a trusted
source, the host is assured that the source IP address in the datagram is the actual
source of the datagram.

When two hosts have an IPsec session established between them, all TCP and UDP
segments sent between them will be encrypted and authenticated. IPsec there-

75
fore provides blanket coverage, securing all communication between the two hosts
for all network applications.

75
Consider a router that interconnects three subnets:
Subnet 1, Subnet 2, and Subnet 3. Suppose all of the
interfaces in each of these three subnets are
required to have the prefix 223.1.17/24. Also
suppose that Subnet 1 is required to support at
least 60 interfaces, Subnet 2 is to support at least 90
interfaces, and Subnet 3 is to support at least 12
interfaces. Provide three network addresses (of the
form a.b.c.d/x) that satisfy these constraints.

76
Consider sending a 2400-byte datagram into a link that has
an MTU of 700 bytes. Suppose the original datagram is
stamped with the identification number 422. How many
fragments are generated? What are the values in the various
fields in the IP datagram(s) generated related to
fragmentation?

Suppose datagrams are limited to 1,500 bytes (including

header) between source Host A and destination Host B.
Assuming a 20-byte IP header, how many datagrams would
be required to send an MP3 consisting of 5 million bytes?
Explain how you computed your answer.

77
Suppose two packets arrive to two different input ports of a router at
exactly the same time. Also suppose there are no other packets
anywhere in the router.
a. Suppose the two packets are to be forwarded to two different output
ports. Is it possible to forward the two packets through the switch fabric
at the same time when the fabric uses a shared bus?
b. Suppose the two packets are to be forwarded to two different output
ports. Is it possible to forward the two packets through the switch fabric
at the same time when the fabric uses a crossbar?
c. Suppose the two packets are to be forwarded to the same output port.
Is it possible to forward the two packets through the switch fabric at the
same time when the fabric uses a crossbar?

78