Unit-4

Network Layer
Introduction,

Virtual Circuit and Datagram

Networks,

Inside Router,

The Internet Protocol (IP),

Routing Algorithms-The Link State

(LS) Routing Algorithm, The Distance
Vector (DV) Routing Algorithm,
Hierarchical Routing
Introduction: Network Layer
 1.Network Layer - Introduction
The Network Layer is responsible for routing data packets from
the source to the destination across multiple networks. It
determines the best path for data transmission and ensures that
packets are delivered efficiently.
Functions of the Network Layer
1. Addressing:
•Assigns unique IP addresses to devices for identification.
•Example: 192.168.1.1 (IPv4) or 2001:db8::ff00:42:8329 (IPv6).
2. Routing:
•Determines the best path for sending data between devices.
•routing algorithms like Link State and Distance Vector.
3.Packet Forwarding:
•Moves packets from one network to another using routers.
•Uses IP-based forwarding tables.
4.Fragmentation and Reassembly and encryption,
decryption:
•Splits large packets into smaller pieces (if needed).
•Reassembles them at the destination. For security encrypt and
decrypt data.
5.Error Handling and Congestion Control:
 Network Layer Protocols
1.IP (Internet Protocol): Gives every device a unique
address and helps send data across networks.
Example: Your phone or computer uses an IP
address to access websites or send emails.

2.ICMP (Internet Control Message Protocol):

Checks network issues and sends error messages.
Example: When you use the ping command to
check if a website is online, ICMP replies with a
response

3.ARP (Address Resolution Protocol): Finds the

physical (MAC) address of a device using its IP
address.
Example: If your computer wants to talk to another
computer in the same Wi-Fi network, ARP helps find its
4. RIP (Routing Information Protocol): Helps
small networks find the best route for data by
checking the number of hops (steps) to the
destination.
Example: Used in small office or home networks
where routers talk to each other to find the best path
for internet traffic.

5.OSPF (Open Shortest Path First): Chooses the

fastest route for data in large networks.
Example: Used in big companies and data centers to
manage internet traffic efficiently.

6.BGP (Border Gateway Protocol): Decides how

data moves between different networks across the
internet.
Example: Used by Internet Service Providers
(ISPs) to connect different parts of the internet
 Network Service Model
The Network Service Model specifies how data is transferred from one
device to another over a network.
Types of Network Service Model
1. Connectionless Service (Datagram Model)
•each packet is independent and can take a different route.
•No prior connection setup is needed.
•Unreliable service (packets may arrive out of order or be lost).
•Example Protocol: IP (Internet Protocol).
Example :
Web browsing (HTTP over IP) – Independent packets are sent.
Online gaming (UDP/IP) – Speed is more important than reliability.
Streaming services (YouTube, Netflix) – Uses UDP for faster delivery.
2. Connection-Oriented Service (Virtual Circuit Model) 🔗
•a predefined route is established before sending data.
•Ensures reliable, in-order delivery of packets.
•Connection must be set up before transmission.
•Example Protocols: MPLS (Multiprotocol Label Switching), ATM
(Asynchronous Transfer Mode).
Example :
Video calls (VoIP over TCP/IP) – Requires continuous, reliable data
flow.
Banking transactions (MPLS-based networks) – Ensures security and
accuracy.
Network Layer Service models
•Internet (Best Effort): No guarantees. Sometimes
fast, sometimes slow. Data may be lost or arrive out of
order.

•ATM CBR(Constant Bit Rate): Sends data at a fixed

speed, ensuring no loss and correct order.

•ATM VBR(Variable bit Rate): Sends data at a

flexible speed but still guarantees order and timing.

•ATM ABR(Available Bit Rate): Ensures a minimum

speed and correct order but may experience some
data loss.

•ATM UBR(Unspecified Bit Rate): No guarantees

except that the data arrives in order, but it may be
slow or lost.
2.Virtual-Circuit Network (Connection
Service)
1. A connection is established before data transfer.
2. All packets follow the same path.
3. Example: ATM, Frame Relay (similar to how TCP works).

Virtual Circuit (VC) Components

1.Path Setup:
A fixed path is set between the source and destination before
sending data.
2.VC Numbers:
1. Each packet carries a VC number in its header.
2. The VC number changes at each router using a
forwarding table.
3.Forwarding Table:
Every router has a table that tells where to send the packet
next based on the VC number.

Phases in Virtual Circuit

1.Setup Phase → The network decides a path.
 Virtual Circuit Setup

application
6. receive data application
transport 5. data flow begins transport
network 4. call connected 3. accept call
network
data link 1. initiate call 2. incoming call
data link
physical physical
 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
VC Forwarding Table
 3.Datagram Network

A datagram network is a type of network

where each packet (datagram) is treated
independently and can take different paths
to reach the destination.

application application
transport transport
network 1. send datagrams 2. receive datagrams network
data link data link
physical physical
Datagram Forwarding Table
A datagram forwarding table helps a router decide
where to send packets based on their destination
address.

How It Works?

•Each incoming packet has a destination address.

•The router checks this table to find the correct
link (interface) to forward the packet. When a
router receives a destination address, it checks the
forwarding table to find the longest matching
prefix.

•If the address matches a range, the packet is sent

through the corresponding link interface (0, 1, or 2).
•If the address doesn’t match any range, it is sent
 Datagram forwarding table

routing algorithm 4 billion IP

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

IP destination address in
arriving packet’s header

1
3 2

Network Layer
 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
How Longest Prefix Match Works

The router takes an incoming destination address

and follows these steps:

1.Check all matching prefixes in the forwarding

table.
2.Select the longest (most specific) match.

Example 1:

Destination Address: 11001000 00010111 00011000

00000101
Matches:
/20 (Interface 0) → Covers 11001000 00010111
00010000 00000000 to 11001000 00010111
00010111 11111111
/21 (Interface 1) → Covers 11001000 00010111
Example 2:

Destination Address: 11001000 00010111 00011010

00000101
Matches:
/20 (Interface 0) → Covers 11001000 00010111
00010000 00000000 to 11001000 00010111
00010111 11111111
/19 (Interface 2) → Covers 11001000 00010111
00011001 00000000 to 11001000 00010111
00011111 11111111
Longest Match: /19
Forward to: Interface 2

Example 3:

Destination Address: 11001000 00010111 00100000

00000000
 4.INSIDE A ROUTER

A router is a networking device that connects

multiple networks and directs data packets between
them.
Functions of a Router
1.Find the Best Route (Using Routing Protocols)
•Uses protocols like RIP, (Routing Information Protocol) OSPF(Open
Shortest Path First), or BGP(Border Gateway Protocol) to determine the
best path for data.
•Creates a routing table to decide where to send packets.
2. Forward Packet
•Reads the destination address of incoming packets.
•Chooses the best outgoing link and sends the packet
forward.

Components of a Router
1. Input Ports – Receive incoming data packets.
2. Switching Fabric – Moves packets inside the router.
 Fig: Components of a
Router

forwarding tables computed, routing

pushed to input ports routing, management
processor
control plane (software)

forwarding data
plane (hardware)

high-seed
switching
fabric

router input ports router output ports

 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
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
Input Port Functions
1.Receives Data (Physical Layer) – Takes in bits from incoming
packets.
2.Processes Data Link Layer – Understands Ethernet or other link-
layer protocols.
3.Looks Up Destination – Uses a forwarding table to decide where
to send the packet.
4.Queues Packets – Holds packets temporarily if they arrive faster
than they can be forwarded.
5.Sends to Switch Fabric – Transfers packets to the next stage for
forwarding.
Let me know if you need further simplification!kj
 Input Port Functions

• It performs the physical layer function of terminating an incoming

physical link at a router.

• It performs link-layer functions needed to interoperate with the

link layer at the other side of the incoming link; this is represented
by the middle boxes in the input and output ports.

• A lookup function is performed at the input port; this will occur in

the rightmost box of the input port.
• The forwarding table is consulted to determine the router output
port to which an arriving packet will be forwarded via the
switching fabric.

• Control packets (for example, packets carrying routing protocol

information) are forwarded from an input port to the routing
processor.
 Switching Fabrics
• It connects the router’s input ports to its output ports.
• It is completely contained within the router - a network inside of
a network router.
• Switching rate: A rate at which packets can be transfer from
inputs to outputs.
• Also measured as multiple of input/output line rate.
• Three types of switching fabrics:

memory

memory bus crossbar

 Switching via Memory
input output
port memory port
(e.g., (e.g.,
Ethernet) Ethernet)

system bus
• Like traditional computers, with switching between input and
output ports being done under direct control of the CPU (routing
processor).

• Packet signalled a routing processor via an interrupt then copied

from the input port into processor memory.
• Routing processor extracted the destination address from the
header, from forwarding table, and copied the packet to the
output port’s buffers.

• If the memory bandwidth is such that B packets per second can

be written into, or read from, then the overall forwarding
throughput must be less than B/2.

• Two packets cannot be forwarded at the same time, even if they

have different destination ports.

• Only one memory read/write over the shared system bus can be
done at a time.
 Switching via bus
• An input port transfers a packet to the output
port over a shared bus, without intervention by
the routing processor.

• The packet is received by all output ports, but

only the port that matches the label will keep
the packet.
bus
• The label is then removed at the output port,
and only used within the switch to cross the
bus.

• Switching speed of the router is limited to the

bus speed.
 Switching via an interconnection network
• Crossbar switch consists 2N buses.

• N input ports to N output ports.

• Its overcome the bandwidth limitation of shared

bus; used to interconnect processors in a
multiprocessor computer architecture.

• Cross-point connection can be opened or closed

at any time by the switch fabric controller.

• Crossbar networks are capable of forwarding

multiple packets in parallel.
 Output ports

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

buffering required when datagrams arrive from fabric faster than the
transmission rate
scheduling discipline chooses among queued datagrams for
transmission

Datagram (packets) can be

lost due to congestion, lack of
buffers
Priority scheduling – who gets best
performance, network neutrality
 Output Port

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

• It buffers packets received from the switching fabric and

transmits these packets on the outgoing link.

• Packets can be lost due to congestions lacks of buffers.

• When a link is bidirectional, an output port will typically be

paired with the input port for that link on the same line card.
 Output port queuing

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!
 Routing Processor

• The routing processor executes the routing protocols, maintains

routing tables and attached link state information and computes the
forwarding table for the router.
• It also performs the network management functions.
 Internet Network Layer

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
• Internet’s network layer has three major components.
• The first component is the IP protocol

• The second major component is the routing component, which determines the path a
datagram follows from source to destination and compute the forwarding tables that
are used to forward packets through the network.

• The final component of the network layer is a facility to report errors in datagrams and
respond to requests for certain network-layer information
 IPv4 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
data taken, specify
(variable length, list of routers
typically a TCP to visit.
or UDP segment)
• Version number: These 4 bits specify the IP protocol version of
the datagram. It determines how to interpret the header. Currently
the only permitted values are 4 (0100) or 6 (0110).

• Header length: Specifies the length of the IP header, in 32-bit

words.

• Type of service: The type of service (TOS) bits were included in

the IPv4 header to allow different types of IP datagrams (for
example, datagrams particularly requiring low delay, high
throughput, or reliability) to be distinguished from each other.

• Datagram length: This is the total length of the IP datagram

(header plus data), measured in bytes.
• Identifier:
• Uniquely identifies the datagram. It is incremented by 1 each time a
datagram is sent.
• All fragments of a datagram contain the same identification value.
• This allows the destination host to determine which fragment belongs
to which datagram.

• Flags:
• 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.

• Fragmentation offset:
• When fragmentation of a message occurs, this field specifies the
offset, or position, in the overall message where the data in this
fragment goes.
• It is specified in units of 8 bytes (64 bits).
• Time-to-live:
• Specifies how long the datagram is allowed to “live” on the network. Each router
decrements the value of the TTL field (reduces it by one) prior to transmitting it.
• If the TTL field drops to zero, the datagram is assumed to have taken too long a route
and is discarded.

• Protocol:
• This field is used only when an IP datagram reaches its final destination.
• The value of this field indicates the specific transport-layer protocol to which the
data portion of this IP datagram should be passed.
• For example, a value of 6 indicates that the data portion is passed to TCP, while a
value of 17 indicates that the data is passed to UDP.

• Header checksum: The header checksum aids a router in detecting bit

errors in a received IP datagram.
• Source and destination IP addresses:
• When a source creates a datagram, it inserts its IP address into the source IP
address field and inserts the address of the ultimate destination into the
destination IP address field.

• Options: The options fields allow an IP header to be extended.

• Data (payload): The data to be transmitted in the datagram, either an

entire higher-layer message or a fragment of one.
 IP fragmentation, reassembly
• network links have MTU
(max.transfer size) - largest
possible link-level frame
• different link types, different
MTUs fragmentation:

…
in: one large datagram
out: 3 smaller datagrams
• large IP datagram divided
(“fragmented”) within net
• one datagram becomes several
datagrams reassembly
• “reassembled” only at final
destination
• IP header bits used to identify, …
order related fragments
 IP fragmentation, reassembly

length ID fragflag offset

example: =4000 =x =0 =0
 4000 byte
datagram one large datagram becomes
several smaller datagrams
 MTU = 1500
bytes
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
 IP Address
• IP addresses are useful in identifying a specific host in a network.

• IP addresses are 32 bit numbers which are divided into 4 octets. Each octet
represents 8 bit binary number. Below is an example of an IP address:

10101100 00010000 11111110 00000001

172 16 254 1

IP addresses are divided into 2 parts:

Network ID & Host ID
<NID> <HID> = IP Address
 IP Addressing - Example
• IP address: It is 32-bit 223.1.1.1
identifier for host, router
interface 223.1.1.2
223.1.2.1

223.1.1.4 223.1.2.9

• Interface: It is a connection
between host/router and 223.1.3.27
physical link. 223.1.1.3
223.1.2.2

• A router’s typically have multiple

interfaces
• A host typically has one or two
223.1.3.1 223.1.3.2
interfaces

• IP addresses associated with

each interface.
223.1.1.1 = 11011111 00000001 00000001 00000001

223 1 1 1
 Interface Example
223.1.1.1
Q: how are interfaces actually
connected? 223.1.2.1

223.1.1.2
223.1.1.4 223.1.2.9

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

A: wireless WiFi interfaces

connected by WiFi base station
 Classification of IP Addresses (Classful
Addressing)
Class: A
0

7 Bit 24 Bit
Fix Network ID Host ID
Class: B
1 0

Fix 14 Bit 16 Bit

Network ID Host ID
Class: C
1 1 0

Fix 21 Bit 8 Bit

Network ID Host ID
Class: D
1 1 1 0

Fix
Class: E Multicast address
1 1 1 1

Fix Reserved address

 Subnet
• Subnet: high order bits defines 223.1.1.0/24
subnet 223.1.2.0/24
223.1.1.1
• Host: low order bits defines host
223.1.1.2 223.1.2.1
• Subnet : 223.1.1.4 223.1.2.9
• device interfaces with same subnet part
of IP address 223.1.2.2
223.1.1.3 223.1.3.27
• can physically reach each other without
intervening router subnet
• https://www.youtube.com/
watch?v=OqsXzkXfwRw 223.1.3.1 223.1.3.2

223.1.3.0/24

Network consisting of 3 subnets

To determine the subnets,
detach each interface from 223.1.1.0/24
its host or router, creating 223.1.2.0/24
223.1.1.1
islands of isolated networks
223.1.1.2 223.1.2.1
each isolated network is 223.1.1.4 223.1.2.9

called a subnet 223.1.2.2

223.1.1.3 223.1.3.27

subnet

223.1.3.1 223.1.3.2

223.1.3.0/24
 Type of addresses in IPv4 Network
• Network address - The address by which we refer to the network.
• E.g.: 10.0.0.0

• Broadcast address - A special address used to send data to all

hosts in the network.
• The broadcast address uses the highest address in the network range.
• E.g.: 10.0.0.255

• Host addresses - The addresses assigned to the end devices in the

network.
• E.g.: 10.0.0.1
Type of addresses
 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
 Classless Inter-Domain Routing(CIDR)
• CIDR is a slash notation of subnet mask. CIDR tells us number of
on bits in a network address.

subnet host
part part
11001000 00010111 00010000 00000000
200.23.16.0/23
• A single IP address can be used to designate many unique IP
addresses with CIDR.

• A CIDR IP address looks like a normal IP address except that it

ends with a slash followed by a number, called the IP network
prefix.

• CIDR addresses reduce the size of routing tables and make more IP
addresses available within organizations.
 Subnetting
• Subnetting take places when we extend the default subnet mask.

• We cannot perform subnetting with default subnet mask and every

classes have default subnet mask.

• Now find the host bits borrowed to create subnets and convert them
in decimal.

• For example find the subnet mask of address 188.25.45.48/20 ?

1. Class B, Default Subnet mask: 255.255.0.0
2. Borrowed 4 bit from host part so mask is now:
11111111 11111111 11110000 00000000
255 255 240 0
 How many subnets from given subnet mask?
• To calculate the number of subnets provided by given subnet mask
we use 2N , where N = number of bits borrowed from host bits to
create subnets.

• For example in 192.168.1.0/27, N is 3.

• By looking at address we can determined that this address is belong

to class C and default subnet mask 255.255.255.0 [/24 in CIDR].

• In given address we borrowed 27 - 24 = 3 host bits to create

subnets.

• Now 23 = 8, so our answer is 8.

 What are the valid subnets?
• Calculating valid subnet is two steps process.

• First calculate total subnet by using formula 2N.

• In second step find the block size and count from zero in block until
subnet mask value.

• For example calculate the valid subnets for 192.168.1.0/26

1. Borrowed host bits are 2 [26-24]
2. Total subnets are 22 = 4
3. Subnet mask would be 255.255.255.192
4. Block size would be 256-192 = 64
5. Start counting from zero at blocks of 64, so our valid subnets would be
0,64,128,192
 What are the total hosts?
• Total hosts are the hosts available per subnet

• To calculate total hosts use formula 2H = Total hosts

• H is the number of host bits

• For example in address 192.168.1.0/26

• We have 32 - 26
1. [Total bits in IP address - Bits consumed by network address] = 6
2. Total hosts per subnet would be 26 = 64
 Network Prefixes
• For Class C, Default subnet mask of class C is 255.255.255.0

• CIDR notation of class C is /24, which means 24 bits from IP

address are already consumed by network portion. We have 8
host bits remain.

• Subnetting moves from left to right. So Class C subnet masks

can only be the following:
CIDR Decimal Binary
/25 128 10000000

/26 192 11000000

/27 224 11100000

/28 240 11110000

/29 248 11111000

/30 252 11111100

 Dynamic Host Configuration Protocol - DHCP
• Dynamic Host Configuration Protocol is a protocol for assigning
dynamic IP addresses to devices on a network.

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.3.27
223.1.2.2 network
223.1.1.3

223.1.2.0/24

223.1.3.1 223.1.3.2

223.1.3.0/24
• With dynamic addressing, a device can have a different IP address
every time it connects to the network.

• In some systems, the device's IP address can even change while it

is still connected.

• It allows reuse of addresses (only hold address while connected

“on”).

• It also support mobile users who want to join network.

 DHCP Client Server Interaction

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
DHCP server
yiaddr: 0.0.0.0out
transaction
there?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
223.1.2.4an IP
transaction
address youID:can
654 use
lifetime: 3600 secs
DHCP request
src: 0.0.0.0, 68
dest:: 255.255.255.255, 67
Broadcast: OK. I’ll
yiaddrr: 223.1.2.4
take that IPID:address!
transaction 655
lifetime: 3600 secs

DHCP ACK
src: 223.1.2.5, 67
dest: 255.255.255.255,
Broadcast: 68
OK. You’ve
yiaddrr: 223.1.2.4
gottransaction
that IPID:address!
655
lifetime: 3600 secs
 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)

 DHCP: example

DHCP DHCP connecting laptop needs

UDP
DHCP
DHCP IP
its IP address, addr of first-
DHCP Eth hop router, addr of DNS
Phy server: use DHCP
DHCP
 DHCP request

encapsulated in UDP,
DHCP DHCP 168.1.1.1 encapsulated in IP,
DHCP UDP encapsulated in 802.1
DHCP IP  Ethernet frame
DHCP Eth router with DHCP
Phy server built into broadcast (dest:
router FFFFFFFFFFFF) on LAN,
received at router
running DHCP
 Ethernet demuxedserver to
IP demuxed, UDP
demuxed to DHCP
DHCP DHCP • DCP server formulates DHCP
DHCP UDP ACK containing client’s IP
DHCP IP address, IP address of first-
DHCP Eth hop router for client, name
Phy & IP address of DNS server

 encapsulation of
DHCP DHCP DHCP server, frame
DHCP UDP forwarded to client,
DHCP IP demuxing up to
Eth router with DHCP
DHCP
DHCP at client
DHCP
Phy server built into  client now knows its
router IP address, name
and IP address of
DSN server, IP
address of its first-
hop router
 Network Address Translation
• NAT is a method that is used to translate Private IP addresses to
Public IP addresses.
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

network have same single datagrams with source or
source NAT IP address: destination in this network
138.76.29.7,different source have 10.0.0/24 address for
port numbers source, destination (as usual)
• Local network uses just one IP address as far as outside world is
concerned.

• This means that only a single, unique IP address is required to

represent an entire group of computers.

• The technique was originally used for ease of rerouting traffic in

IP networks without readdressing every host.

• The concept of NAT as developed to solve two problems:

• Solve shortage of IPv4 IP addresses
• To Hide the Network Address
 NAT Terminology
• Inside Local Address: The name of the inside source address before
translation. This would be a Private IP.

• Inside Global Address: The name of the inside host after translation. This
would be the Public IP.

• Outside Local Address: The name of the destination host before translation.

• Outside Global Address: The name of the destination host after translation.

• Where:
• Global Addresses → Public
• Local Addresses → Private
• Inside Hosts → Within Local Network
• Outside Hosts → Outside Local Network
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
 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
 Internet Control Message Protocol - ICMP
• When something unexpected occurs, the event is reported by the
ICMP, which is also used to test the Internet.

• Some of the ICMP messages are defined and are listed below.
Each ICMP message type is encapsulated in an IP packet.

Message Type Description

Destination unreachable Packet could not be delivered
Time exceeded Time to live field hit 0
Parameter problem Invalid header field
Source quench Choke packet
Redirect Teach a router about geography
Echo Ask a machine if it is alive
Echo reply Yes, I am alive
Timestamp request Same as Echo request, but with timestamp
Timestamp reply Same as Echo reply, but with timestamp
 IPv6: motivation
• Initial motivation: 32-bit address space soon to be completely
allocated.

• additional motivation:
• header format helps speed processing/forwarding
• header changes to facilitate QoS

IPv6 datagram format:

• fixed-length 40 byte header
• no fragmentation allowed
IPv6 Datagram Format
• Version: The size of the Version field is 4 bits. The Version field shows the
version of IP and is set to 6.

• Traffic Class:
• The size of Traffic Class field is 8 bits. Traffic Class field is similar to the IPv4 Type
of Service (ToS) field.
• The Traffic Class field indicates the IPv6 packet’s class or priority.

• Flow Label:
• The size of Flow Label field is 20 bits.
• The Flow Label field provide additional support for real-time datagram delivery and
quality of service features.
• The purpose of Flow Label field is to indicate that this packet belongs to a specific
sequence of packets between a source and destination and can be used to prioritized
delivery of packets for services like voice.
• Payload Length: The size of the Payload Length field is 16 bits. The Payload
Length field shows the length of the IPv6 payload, including the extension
headers and the upper layer protocol data

• Next Header: The size of the Next Header field is 8 bits. The Next Header
field shows either the type of the first extension (if any extension header is
available) or the protocol in the upper layer such as TCP, UDP, or ICMPv6.

• Hop Limit: The size of the Hop Limit field is 8 bits The Hop Limit field shows
the maximum number of routers the IPv6 packet can travel. This Hop Limit
field is similar to IPv4 Time to Live (TTL) field.

• Source Address: The size of the Source Address field is 128 bits. The Source
Address field shows the IPv6 address of the source of the packet.
 Difference between IPv4 & IPv6
IPv4 IPv6
 32 bit length  128 bit length
 Fragmentation is done by sender  Fragmentation is done only by sender
and forwarding routers
 No packet flow identification  Packet flow identification is available within
the IPv6 header using the Flow Label field
 Checksum field in header  No checksum field in header
 Options fields are available in  No option fields, but Extension headers are
header available
 Address Resolution Protocol (ARP)is  Address Resolution Protocol (ARP) is
available to map IPv4 addresses replaced with Neighbor Discovery Protocol
to MAC addresses

 Broadcast messages are available  Broadcast messages are not available

 Static IP addresses or DHCP is  Auto-configuration of addresses is available
required to configure IP addresses
 Routing Algorithms
• Routing algorithms, operating in network routers, exchange and
compute the information that is used to configure these
forwarding tables.

• The purpose of a routing algorithm is then simple: given a set of

routers, with links connecting the routers, a routing algorithm
finds a “good” path from source router to destination router.

• Typically, a good path is one that has the least cost.

Graph : Formulating Routing Problems
• Graph G = (N,E) is a set N of nodes and a collection E of edges,
where each edge is a pair of node from N.

• Wrt network-layer routing-

• the nodes in the graph represent routers—the points at which packet-forwarding
decisions are made—and
• the edges connecting these nodes represent the physical links between these routers.

• As shown in Figure , an edge also has a value representing its cost.

• Typically, an edge’s cost may reflect the physical length of the

corresponding link , the link speed, or the monetary cost associated
with a link.
 Routing algorithm classification
First way
1. global:
• all routers have complete topology, link cost info
• “link state” algorithms

2. decentralized:
• router knows physically-connected neighbors, link costs to
neighbors
• iterative process of computation, exchange of info with neighbors
• “distance vector” algorithms
 Second way
1. Static:
routes change slowly over time

2. Dynamic:
routes change more quickly
 periodic update
 in response to link cost changes
 Third way
1. Load-sensitive algorithm
• In link costs vary dynamically to reflect the current level of
congestion in the underlying link.
• If a high cost is associated with a link that is currently congested,
a routing algorithm will tend to choose routes around such a
congested link.
•
2. Load-insensitive :
• Today’s Internet routing algorithms (such as RIP, OSPF, and BGP)
are load-insensitive, as a link’s cost does not explicitly reflect its
current (or recent past) level of congestion.
 Link State Routing Algorithm
• Also known as Dijkstra’s Algorithm.

• It computes the least-cost path from one node (source node) to all
other nodes in the network.

• Its iterative and after the kth least-cost paths are known to k
destination nodes.

• Notation:
• c(x,y): link cost from node x to y; = ∞ if not direct neighbours
• D(v): current value of cost of path from source to destination v
• p(v): predecessor node along path from source to v
• N': set of nodes whose least cost path definitively known
 Basics of Dijkstra's Algorithm
• Dijkstra's Algorithm basically starts at the node that you choose (the source
node) and it analyses the graph to find the shortest path between that node
and all the other nodes in the graph.

• The algorithm keeps track of the currently known shortest distance from each
node to the source node and it updates these values if it finds a shorter path.

• Once the algorithm has found the shortest path between the source node and
another node, that node is marked as "visited" and added to the path.

• The process continues until all the nodes in the graph have been added to the
path. This way, we have a path that connects the source node to all other
nodes following the shortest path possible to reach each node.
 Dijkstra’s Algorithm

1 Initialization:
2 N' = {u}
3 for all nodes v
4 if v adjacent to u
5 then D(v) = c(u,v)
6 else D(v) = ∞
7
8 Loop
9 find w not in N' such that D(w) is a minimum
10 add w to N'
11 update D(v) for all v adjacent to w and not in N' :
12 D(v) = min( D(v), D(w) + c(w,v) )
13 /* new cost to v is either old cost to v or known
14 shortest path cost to w plus cost from w to v */
15 until all nodes in N'
 Dijkstra’s Algorithm – Example:1
D(v) D(w) D(x) D(y) D(z)
Step N' p(v) p(w) p(x) p(y) p(z)
0 u 7,u 3,u 5,u ∞ ∞
1 uw 6,w 5,u 11,w ∞
2 uwx 6,w 11,w 14,x
3 uwxv 10,v 14,x
x
4 uwxvy 12,y 9
5 uwxvyz
5 7
4
notes: 8
 construct shortest path 3
tree by tracing u w y z
2
predecessor nodes
 ties can exist (can be 3
broken arbitrarily) 7 4
v
 Dijkstra’s Algorithm – Example:2

Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)

0 u 2,u 5,u 1,u ∞ ∞
1 ux 2,u 4,x 2,x ∞
2 uxy 2,u 3,y 4,y
3 uxyv 3,y 4,y
4 uxyvw 4,y
5 uxyvwz

5
3
v w 5
2
u 2 1 z
3
1 2
x 1
y
 Distance Vector Algorithm
• Distance-vector (DV) algorithm is iterative, asynchronous, and
distributed.

• It is distributed in that each node receives some information from

one or more of its directly attached neighbours, performs a
calculation, and then distributes the results of its calculation back
to its neighbours.

• It is iterative. so, process continues on until no more information is

exchanged between neighbours.

• The algorithm is asynchronous. It does not require all of the nodes

to operate with each other.
• Let dx(y) be the cost of the least-cost path from node x to node y.

• Then least costs are related by the celebrated Bellman-Ford

equation:
dx(y) = cost of least-cost path from x to y then

dx(y) = min
v
{c(x,v) + d v(y) }

cost from neighbor v to destination

cost to neighbor v

min taken over all neighbors v of x

iterative,
asynchronous: each
local iteration
caused by: each node:
 local link cost
change wait for (change in local link cost
or message from neighbor)
 DV update message
from neighbor
distributed: recompute estimates
 each node notifies
neighbors only when if DV to any destination has
its DV changes changed, notify neighbors
neighbors then
notify their
neighbors if
necessary
 Distance Vector Algorithm - Example
node x cost to cost to
table x y z x y z
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
x 0 2 7 x 0 2 3
= min{2+0 , 7+1} = 2

from
from

y ∞∞ ∞ y 2 0 1
z ∞∞ ∞ z 7 1 0
Dx(z) = min{c(x,y) +
node y cost to
table x y z Dy(z), c(x,z) + Dz(z)}
x ∞ ∞ ∞ = min{2+1 , 7+0} = 3
y 2 0 1
from

z ∞∞ ∞
y
2 1
node z cost to
table x y z x z
7
x ∞∞ ∞
from

y ∞∞ ∞
z 7 1 0
time
 Distance Vector Algorithm - Example
node x cost to cost to cost to
table x y z x y z x y z
x 0 2 7 x 0 2 3 x 0 2 3

from
from

y ∞∞ ∞ y 2 0 1 y 2 0 1

from
y
z ∞∞ ∞ z 7 1 0 z 3 1 0 2 1

node y cost to
x z
cost to cost to 7
table x y z x y z x y z
x ∞ ∞ ∞ x 0 2 7 x 0 2 3
from

y 2 0 1 y 2 0 1
from

y 2 0 1

from
z ∞∞ ∞ z 7 1 0 z 3 1 0

node z cost to cost to cost to

table x y z x y z x y z

x ∞∞ ∞ x 0 2 7 x 0 2 3
from

from

y 2 0 1 y 2 0 1
from

y ∞∞ ∞
z 7 1 0 z 3 1 0 z 3 1 0
time
 Difference: LS and DV Routing Algorithm
Distance Vector Protocol Link State Protocol
Entire routing table is sent as an update Updates are incremental & entire routing table is
not sent as update
Distance vector protocol send periodic Updates are triggered not periodic
update at every 30 or 90 second
Update are broadcasted Updates are multicasted

Updates are sent to directly connected Update are sent to entire network & to just
neighbour only directly connected neighbour
Routers don't have end to end visibility Routers have visibility of entire network of that
of entire network. area only.
It is prone to routing loops No routing loops
 Hierarchical Routing
• As networks grow in size, the router routing tables grow
proportionally.

• Router memory, CPU time and more bandwidth consumed to send

status reports about them.

• When hierarchical routing is used, the routers are divided into

what called regions.

• Each router knowing all the details about how to route packets to
destinations within its own region.

• But knowing nothing about the internal structure of other regions.

• LS and DV algorithms are viewed as the network simply as a
collection of interconnected routers.

• One router was indistinguishable from another in the sense that all
routers executed the same routing algorithm to compute routing
paths through the entire network.

• In practice, this model and its view of a homogenous set of routers

all executing the same routing algorithm is a bit simplistic for at
least two important reasons:
1. Scale :
• As the number of routers becomes large, the overhead involved in
computing, storing, and communicating routing information.

• As networks grow in size, the router routing tables grow proportionally.

• Clearly something must be done to reduce the complexity of route

computation in networks as large as the public Internet.

• Not only is router memory consumed by ever-increasing tables, but more

CPU time is needed to scan them and more bandwidth is needed to send
status reports about them.

• At a certain point the network may grow to the point where it is no longer
feasible for every router to have an entry for every other router, so the
routing will have to be done hierarchically, as it is in the telephone
network.
2. Administrative autonomy.
• Although researchers tend to ignore issues such as a company’s
desire to run its routers as it pleases (for example, to run whatever
routing algorithm it chooses) or to hide aspects of its network’s
internal organization from the outside, these are important
considerations.
• Ideally, an organization should be able to run and administer its
network as it wishes, while still being able to connect its network
to other outside networks.

Both of these problems can be solved by organizing routers into

autonomous systems (ASs), with each AS consisting of a group of
routers that are typically under the same administrative control
(e.g., operated by the same ISP or belonging to the same company
network).
• Routers within the same AS all run the same routing algorithm (for
example, an LS or DV algorithm) and have information about each
other.
• The routing algorithm running within an autonomous system is
called an intra-autonomous system routing protocol.

• It will be necessary, of course, to connect ASs to each other, and

thus one or more of the routers in an AS will have the added task of
being responsible for forwarding packets to destinations outside the
AS; these routers are called gateway routers.

• When hierarchical routing is used, the routers are divided into what
called regions, with each router knowing all the details about how
to route packets to destinations within its own region, but knowing
nothing about the internal structure of other regions.
• Both of these problems can be solved by organizing routers into
autonomous systems (ASs), with each AS consisting of a group of
routers that are typically under the same administrative control
(e.g., operated by the same ISP or belonging to the same company
network).

• Routers within the same AS all run the same routing algorithm (for
example, an LS or DV algorithm)

• The routing algorithm running within an autonomous system is

called an intra-autonomous system routing protocol.

• To connect ASs to each other, and thus one or more of the routers in
an AS will have the added task of being responsible for forwarding
packets to destinations outside the AS; these routers are called
gateway routers.
• When hierarchical routing is used, the routers are divided into what called
regions, with each router knowing all the details about how to route packets
to destinations within its own region, but knowing nothing about the
internal structure of other regions.

• Figure below provides a simple example with three ASs: AS1, AS2, and AS3.

• In figure, the heavy lines represent direct link connections between pairs of
routers.

• The thinner lines hanging from the routers represent subnets that are
directly connected to the routers.
 Interconnected ASes

3c
3a 2c
3b 2a
AS3 2b
1c AS2
1a 1b AS1
1d forwarding table
configured by both intra-
and inter-AS routing
Intra-AS
Routing
Inter-AS
Routing
algorithm
algorithm algorithm  intra-AS sets entries for internal
dests
Forwarding  inter-AS & intra-AS sets entries
table
for external dests
 Inter-AS tasks
suppose router in AS1 AS1 must:
receives datagram destined 1. learn which dests are
outside of AS1: reachable through AS2,
 router should forward packet to
gateway router, but which one?
which through AS3
2. propagate this
reachability info to all
routers in AS1
job of inter-AS routing!
3c
3a
3b
AS3 2c other
1c 2a networks
other 1a 2b
networks 1b AS2
AS1 1d
Hierarchical Routing - Example
THANK YOU