Chapter 4 - Internet Layer

Lecture 6:
Internet Layer
Reading 5.1. and 5.6 in Computer Networks,
Tanenbaum
The lecture uses materials provided by Keio University, Japan
1
Contents
l Internet Protocol
l IP address and IP packet format
l ICMP- Protocol for control message
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

School of Information and Communication Technology
2
Introduction about IP
Concepts
Store and forward principles
Characteristic of IP
3
Network layer and Internet protocol
l Role of network layer: Transferring data between distant nodes
l Two main functionalities of Network layer
l Routing: Determine the path for transferring data from the source
to the destination nodes à Role of routing protocol.
l Forwarding: Transferring data from an incoming port to an
outgoing port of a node (router) according to the path defined
above è Role of routed protocol: Internet Protocol (IP)
application
application
TCP/UDP
TCP/UDP
IP
1. Send data IP
data link 2. Receive data
data link
physical
physical

4
Network layer and Internet Protocol (IP)
lLayer 2 devices (switches) allow to connect

limited number of close hosts
lWhen hosts are far from each other or there
are too many hosts, using switch is inefficient.
lForwarding table of switch becomes too big
lè Need intermediates nodes with forwarding
and better path finding functions à Routers
lFinding routes according to destination Network
layer address
lForwarding data

5
IP principles
l Network elements
Switch
l host = end system;
l subnetwork = a collection of hosts that are
connected by layer-2 devices
l Hosts of a subnetwork have similar
addresses: a common prefix Router
l Routers: intermediate nodes interconnect
subnetworks
l Packet forwarding Switch
Router Switch
l Within a subnetwork: hosts communicate
directly through layer-2 device (switch)
l Between subnetworks: one or several
routers forward packets based on the
destination network address.
Switch
A subnetwork
6
Routing and forwarding
Routing protocol
Routing
protocol identifies the shortest
path to a network
Forwarding table
dest address outgoing port Forwarding table
Net 1/net.mask 1 identifies an outgoing
Net 2/net.mask 2 port to send data toward
Net 3/net.mask 1 a destination network
Packet (header Router

contain destination
address)
1
subnetwork
3 2
twork
bne
su
7
IP address
IP address classes
CIDR – Classless Inter-Domain routing
Subnet and netmask
Special IP addresses
8
IP address (IPv4)
• IP address: A 32-bit
number identifying 223.1.1.1
uniquely a network 223.1.2.1

223.1.1.2
interface 223.1.1.4 223.1.2.9
• Interface: 223.1.2.2
• router’s typically have 223.1.1.3 223.1.3.27
multiple interfaces
• host may have multiple
interfaces
223.1.3.1 223.1.3.2
• IP addresses associated
with interface, not host,
router
223.1.1.1 = 11011111 00000001 00000001 00000001

223 1 1 1
9
IP address (IPv4)
• For routing purpose, IP la

address of interfaces in a
subnetwork have the 223.1.1.1
same prefix. 223.1.2.1
223.1.1.2
• A subnetwork from IP 223.1.1.4 223.1.2.9
address perspective is a
part of network where: 223.1.1.3 223.1.3.27
223.1.2.2
• Devices can physically
reach each other without
intervening router (using
layer-2 only technology) 223.1.3.1 223.1.3.2
A subnetwork

10
Dot notation
Example:
203.178.136.63 o
259.12.49.192 x
133.27.4.27 o
8 bits
0 – 255 integer
Use 4 x 8 bits describing a 32 bits address
3417476964
1 1 0 0 1 0 1 1 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 1 0 1 1 0 0 1 0 0
203 178 143 100

11
Host address, network address
• IP address contains two parts

• Host ID – identify a host in a network
• Network ID – identify a network
Network ID Host ID
1 1 0 0 1 0 1 1 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 1 0 1 1 0 0 1 0 0
203 178 143 100
l How to know which bits belong to network ID or host

ID parts?
l Use classful IP address
l Use classless IP address– CIDR
12
Classify IP addresses
8bits 8bits 8bits 8bits
!"#$$%& ' ;89: > > >

!"#$$%( ) ' <=53 ? > >
!"#$$%! ) ) ' 789: ? ? >
!"#$$%* ) ) ) ' 42"356#$3
!"#$$%+ ) ) ) ) ,-$-./-%01.%0232.-%2$-%
!"#$"%&'(#)* !"#$"+#,',
-./,,"0 123 2425
-./,,"6 17835 79987
-./,,"- 2421 297
13
Exercise
lDetermine which classes these IP addresses

belong to:
l10.10.10.9
l192.168.70.5
l129.60.4.7
lWhat are network ID part of each address

14
Limitation of classful IP address
• Inefficient use of addressing space

• Hard classification of addressing space into classes (A, B, C,
D, E) makes it is difficult to use all the address space
Solution…
l CIDR: Classless Inter Domain Routing
l Network ID part will have variable length.
l Length of Network ID part is specified in Network mask
l Address notation: a.b.c.d/x, where x (mask) the number of
bits in Network ID part.

15
Network mask
• Network mask = number of bits in Network ID part

• IP addresses are assigned to hosts in the same network
have the same Network ID part.
• Based on a network mask, it is possible to
• Identify the network where an IP address belongs to
• Calculate how many IP addresses available in the network associated
with the mask.

16
Presentation of network mask
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0
255 255 255 224
• 255.255.255.224 • Last byte may

be:
• /27 0 248
• 0xFFFFFFe0 128 252
192 254
224 255
240
17
Calculation of network address
Network part Host Part
203 . 178 . 142 . 130

IP Address 110 0 1 011 101 1 0 010 100 0 1 110 100 0 0 010
255 . 255 . 255 . 224

Netmask (/27) 111 1 1 111 111 1 1 111 111 1 1 111 111 0 0 000
AND
27 (bit)
203 . 178 . 142 . 128
110 0 1 011 101 1 0 010 100 0 1 110 100 0 0 000
Network address 203.178.142.128/27

18
Different significations of IP address
• Network address
• IP address assigned to a network
• hostID contains all 0
• Broadcast address
• Address used for sending data to all hosts in a
network
• All bit 1 in HostID part.
• Host address
• IP address assigned to a network card
• Should not be a network or a broadcast address

19
Network address or host address (1)
133 27 4 160
10000101000110110000010010100000
11111111111111111111111111000000
10000101000110110000010010000000
133 27 4 128

20
Network address or host address (2)
133 27 4 160
10000101000110110000010010100000
11111111111111111111111111100000
10000101000110110000010010100000
133 27 4 160

21
Exercice: IP address and network mask
l Which of the following IP addresses are host

address, network address, broadcast address?
Which network they belong to? What is the
broadcast address of that network?
(1) 203.178.142.128 /25
(2) 203.178.142.128 /24
(3) 203.178.142.127 /25
(4) 203.178.142.127 /24
l Attn: With CIDR addressing, IP address should
always coming with a network mask
22
Calculation of network size
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0
255 255 255 192

• Network size • In case of mask /26
• Power of 2 • Bits for Host ID = 6 bits
6
• 2 =64 possible address:
• RFC1878
• 0 - 63
• 64 - 127
• 128 - 191
• 192 – 255
• Including network address
and broadcast address

23
Calculation of network size
• Network mask: /n
• Network size: The maximum acceptable number
of hosts in that network, each host must have a
distinguish IP address
• IP address : NetworkID HostID
n bit (32-n) bit
• Number of hosts (Unicast Address):

232-n - 2

24
Subnet
• Subnet is a part of a
network 223.1.1.1
• Hosts of a subnet 223.1.2.1

223.1.1.2
communicate directly 223.1.1.4 223.1.2.9
without reaching to
layer 3. 223.1.2.2
223.1.1.3 223.1.3.27
• Usually is one
department of an subnet
organization
223.1.3.1 223.1.3.2
• Design question: How
to assign addresses of a
network to subnets
A network with 3 subnets.
• Use a longer netmask
25
Example: Divide into 2 subnets
11001000 00010111 00010000 00000000

200. 23. 16. 0 /24
SubnetID
11001000 00010111 00010000 00000000

200. 23. 16. 0 /25
11001000 00010111 00010000 10000000
200. 23. 16. 128 /25

26
Principle
lDivide a IP range into sub-ranges of equal size

lTake some bits from HostID part to distinguish
subnets
leach subnet contains IP addresses with a fixed values
of subnet ID.
Network ID Host ID
subnetID
network ID of each subnet

27
Exercise: Dividing into subnets
lGiven IP addresses in the range 200.23.16.0/24

1) Need to organize into 3 subnets
l Address of each subnetwork? Mask? Number of hosts/subnetwork
2) General question: Need to create as many subnets as possible
so that
l Each network can contain 14 hosts
Network address? Mask?
/28
/27
/26
/25
28
Addressing space of IPv4
• In theory
• All between 0.0.0.0 ～ 255.255.255.255
• Some special IP address (RFC1918)
10.0.0.0/8
Private address 172.16.0.0/12
192.168.0.0/16
Loopback address 127.0.0.0
224.0.0.0
Multicast address
～239.255.255.255
• Self assigned IP address: 169.254.0.0/16

29
Attention about IP
lCurrently IPv4: 32 bits

l133.113.215.10 (IPv4)
lIPv6 is also widely used: 128bits
l2001:200:0:8803::53 (IPv6)
l Fix 64 first bit for subnet ID, 64 last bit belongs to
interface ID.
l Security feature is integrated

30
IP packet
31
Header of IP
total datagram
length (words)
IP protocol version 32 bits
number
ver head. DS length
header length len for
(bytes) fragment
16-bit identifier flgs fragmentation/
offset reassembly
QoS support time to upper header
live layer checksum
max number 32 bit source IP address
remaining hops
32 bit destination IP address
(decremented at
each router) Options (if any) E.g. timestamp,
record route
data taken, specify
upper layer protocol (variable length, list of routers
to deliver payload to typically a TCP to visit.
or UDP segment)
32
IP header (1)
• Version (4 bits)
• IPv4
• IPv6
• Header length: 4bits
• In word unit (4 bytes)
• Min: 5
• Max: 60

33
IP header (2)
• DS (Differentiated Service : 8bits)

• Old name: Type of Service
• Used for QoS management by some router
• Diffserv

34
IP header (3)
• Length: total length including header (16 bits)

• In bytes unit
• Max: 65536
• 16 bits Identifier– ID of the packet
• Used for identifying all fragments of the same packet
when it is fragmented
• Flag
• Fragmentation offset – offset of the first byte of the
fragment in its original packet

35
IP header (4)
• TTL, 8 bits – Time to live

• Maximum number of hops (router) the packet is allowed
to travel
• Max: 255
• Router decreases TTL 1 unit when processing a packet
• The packet will be destroyed when TTL reaches to 0
• Protocol – upper layer protocol
• Transport protocol (TCP, UDP,…)
• Other network layer protocols that are encapsulated in
IP packet (ICMP, IGMP, OSPF )

36
IP header (4)
• Checksum: to detect corruption in the header

of IPv4 data packets
• Source IP address
• 32 bit, address of the sender
• Destination IP address
• 32 bit, address of the receiver.

37
Packet fragmentation (1)
lEach link has a fixed

MTU (Maximum
fragment:
transfering unit) in: 1 big packet
out: 3 smaller packets
lDifferent media have
different MTU
lIf IP packet > MTU, it
reassemblated
should be
l Divided into small fragments
l Gathered at the destination

38
Packet fragmentation (2)
• Offset
• Position of the fragment in the original packet
• In 8 bytes units
0 1399
Offset = 0/8 = 0
0 1400 2800 3999 1400 2799

Offset = 1400/8 = 175
2800 3999
Offset = 2800/8 = 350

39
Network Address
Translation (NAT)
4.3. Chuyển đổi địa chỉ (NAT)
Principal NAT
• Data communication from a LAN (using private IP

address) to the Internet (using public IP address) and
vice-visa
à NAT (Network Address Translation) convert private
address to public address. The task is performed on
routers
• Advantage:
• Solve the problem of limiting public IP address
• Hide the private address inside a LAN from outside
intruders
• Avoid IP address re-assignment within a LAN when change
ISP

41
Static NAT
• The simplest NAT

• A IP private is assigned a public IP
• NAT router store a converting table in its
memory
• Converting table map a private IP address to a
public IP address for internet communication
• This mechanism is often used for servers
located inside a LAN and providing public
service. Ex: dk-sis, soict web server.

42
Static NAT - Example
Src: a.b.c.d
Src: a.b.c.d
Dst: 10.0.0.20
Dst: 202.191.56.65
Src: 202.191.56.65 Src: 10.0.0.20

Dst: a.b.c.d Dst: a.b.c.d
NAT Inside IP Outside IP

Table 10.0.0.10 202.191.56.11
10.0.0.20 202.191.56.65
Dynamic NAT
• NAT router map automatically a range of private

IP to a range of public IP so that computer inside
a LAN can communicate to Internet when it
needs
• No fix mapping
• Any private IP address will be translated
automatically to one (available) public IP address
from the pool of public IP addressed maaged by
the NAT router
5/16/24
Dynamic NAT – Example
Src: 202.191.56.15 Src: 10.0.0.31

Src: a.b.c.d Src: a.b.c.d

Dst: 202.191.56.15 Dst: 10.0.0.31
Src: ? Src: 10.0.0.32

Inside IP Outside IP
NAT Table
10.0.0.31 202.191.56.15
10.0.0.32 202.191.56.16

Port Address Translation
• Port Address Translation= PNAT=NAT overloading

• Special form of dynamic NAT
• Map many private IP to a single public IP public by adding
a port number
• n private IP à 1 public IP
• PAT use sockets information to map
• (private IP : port) <-> (public IP: port)
5/16/24
PAT– Example
Src: 202.191.56.15:2001 Src: 10.0.0.31:6000
Dst: a.b.c.d:443 Dst: a.b.c.d:443
Src: a.b.c.d:443 Src: a.b.c.d:443

Dst: 202.191.56.15:2001 Dst: 10.0.0.31:6000
Src: ? Src: 10.0.0.32:7000

Dst: a.b.c.d:443 Dst: a.b.c.d:443
NAT Table Inside IP Outside IP

10.0.0.31:6000 202.191.56.15:2001
10.0.0.32:7000 202.191.56.15: 2002
Lecture 7: Routing
Reading 5.2
Computer Networks, Tanenbaum
48
What is routing?
Routing principals
Forwarding mechanism
“Longest matching” rule
49
Routing and Forwarding principles (1)
• When a host send an IP packet to another host:

• If the destination and the source are in the same
network (by IP address):
• the packet is transferred directly to the destination by Layer 2
• If the destination is in a different network with the
source:
• The packet is sent to a router (to choose a route)
• The next router then forward data again until the destination
Router Router
A
B C D
50
Forward IP packets
• Each router has a Forwarding Table

• A part of Routing Table
• Forwarding table contain:
• Destination: Network address/network mask
• Outgoing port: label of the port on the router that
connect to the next router in the part to the
destination
• Defaut network address:
• 0.0.0.0/0 stands for any networks.

51
Routing table
Routing protocol
Forwarding table
dest address outgoing port
net1. address/net.mask 1
Packet with destination

address in the header
1
3 2

52
Some examples of routers…
YAMAHA
RTX-1500 Cisco 2600
BUFFALO PLANEX
BHR-4RV GW-AP54SAG
Router small size
Cisco CRS-1
Hitachi Router for backbone networks

Juniper M10
GR2000-1B
Foundry Networks
http://www.cisco.com.vn
NetIron 800
http://www.juniper.net/
Router medium size http://www.buffalotech.com
Cisco 3700 53
Routing table and forwarding mechanism (1)
Network Next-hop Interface

10.0.0.0/24 A eth1
172.16.0.0/24 C eth2
192.168.0.0/24 direct eth3
Router A Router B Router C

eth1 eth1 eth2 eth1
eth2 eth2
eth3
10.0.0.0/24 192.168.0.0/24 172.16.0.0/24
Rule: No routes, no reachability!

54
Bảng chọn đường và cơ chế chuyển tiếp (1)

10.0.0.0/24 B3 C2
10.0.0.0/24 Direct A1 172.16.0.0/24 Direct C1
172.16.0.0/24 B2 A2 192.168.0.0/2 B3 C2
4
192.168.0.0/24 B2 A2
Router B Router C
Router A A2 B2 B3 C2
A1 B1 C1
10.0.0.0/24 192.168.0.0/24 172.16.0.0/24
Network Next-hop Inf
10.0.0.0/24 A2 B2
Lưu ý quy tắc: No routes,
no reachability!
172.16.0.0/24 C2 B3
192.168.0.0/24 Direct B1
10.0.0.0/24 192.168.0.0/24 172.16.0.0/24
Network Next-hop Q. What should be

the routing table of
10.0.0.0/24 A router C so that all
172.16.0.0/24 C host can send data
to each other?
192.168.0.0/24 Direct

56
Example – Routing table on a host
C:\Documents and Settings\tungbt>netstat –r

Route Table
========================================================================
Interface List
Destination………MS TCP Loopback
0x1 ........................... Outgoing
interfaceport
0x2 ...08 00 1f b2 a1 a3 ...... Realtek RTL8139 Family PCI Fast Ethernet NIC -
========================================================================
Network Netmask Gateway Interface Metric
0.0.0.0 0.0.0.0 192.168.1.1 192.168.1.34 20

127.0.0.0 255.0.0.0 127.0.0.1 127.0.0.1 1
192.168.1.0 255.255.255.0 192.168.1.34 192.168.1.34 20
192.168.1.34 255.255.255.255 127.0.0.1 127.0.0.1 20
192.168.1.255 255.255.255.255 192.168.1.34 192.168.1.34 20
224.0.0.0 240.0.0.0 192.168.1.34 192.168.1.34 20
255.255.255.255 255.255.255.255 192.168.1.34 192.168.1.34 1
Default Gateway: 192.168.1.1

========================================================================
57
Example- Routing table on a router
Destination Outgoing port

Router# show ip route
O 203.238.37.0/24 via 203.178.136.14, FastEthernet0/1

O 203.238.37.96/27 via 203.178.136.26, Serial0/0/0
C 203.238.37.128/27 is directly connected, Serial0/0/0
O 192.68.132.0/24 via 203.178.136.14, FastEthernet0/1
C 203.254.52.0/24 is directly connected, FastEthernet0/1
C 202.171.96.0/24 is directly connected, Serial0/0/1

58
Internet
10.0.0.0/24 192.168.0.0/24 172.16.0.0/24
Router B
Network Next-hop Q. What is the
10.0.0.0/24 A routing table in B?
172.16.0.0/24 C Q: What if C is
192.168.0.0/24 Direct connected to the
Internet?
59
Router X Internet
10.0.0.0/24 192.168.0.0/24 172.16.0.0/24
Router B
Q: What if C is connected
Network Next-hop
to the Internet?
10.0.0.0/24 A
172.16.0.0/24 C What to be change in
192.168.0.0/24 Direct routing table of A,B, and C
0.0.0.0/0 C to communicate with the
Internet
60
Default route
lIf router does not find a route to a destination in its

routing table, default route is necessary
lDefault route is defined for all destination networks that
are not figured in the routing table.
l0.0.0.0/0
l Is a special notation for all destination networks
Router A
Internet
Next Router is always A

61
Longest matching rule
• When a router receive a packet: ...

• The router match n first bits of the destination address
with the networks in the routing table
• /n: Mask of the destination networks in the routing table
• If there is more than 1 matching network, apply “longest
matching” rule:
• Choose the route with the largest mask
Destination Outgoing Port

Destination address of
the packet to be 11.0.0.0 /8 Se0/1
forwarded: 11.1.0.0 /16 Se0/2
11.1.2.10 11.1.2.0/24 Se0/3
0.0.0.0/0 Se0/4 62
“Longest matching” rule (2)
Destination address:
11.1.2.5 = 00001011.00000001.00000010.00000101
Route 3:
11.1.2.0/24 = 00001011.00000001.00000010.00000000
Route 2:
11.1.0.0/16 = 00001011.00000001.00000000.00000000
Route 1:
11.0.0.0/8 = 00001011.00000000.00000000.00000000

63
Route aggregation
• How many networks in the Internet?

• There will be a lot of entries in the routing table?
• The entries to sub-networks of the same “big” network can
be aggregated inorder to reduce the size of routing table.
200.23.1.0/24
200.23.0.0/24
200.23.0.0/23
200.23.1.0/24
200.23.0.0/22
200.23.2.0/24
200.23.1.0/23
200.23.3.0/24
64
Packet processing on routers
• Step 1 : If TTL = 1(or TTL = 0), destroy the packet and send error
message. End.
• Step 2 : If TTL >1, extract the destination IP address of the packet.
Apply the mask of networks in its routing table to destination IP
address to find corresponding network addresses.
• Step 3 : Compare the obtained network addresses with networks
in routing table.
• If find a matching route, forward the packet to the interface of the
route, reduce TTL by 1.
• If find >1 routes matchedè apply longest matching rule to select the
best route, reduce TTL by1
• If no route match, check if there is a default route (with network
0.0.0.0 /0).
• If there is a default route, forward the packet to the corresponding
interface and reduce TTL by 1.
• If there is no default route: destroy the packet, send an error message
back to the source.

65
Exercises
• A router has the following (CIDR) entries in its routing table:

Address/mask Next hop
135.46.56.0/22 Interface 0
135.46.60.0/22 Interface 1
192.53.40.0/23 Interface 2
0.0.0.0/0 Interface 3
• For each of the following IP addresses, what does the router do if a packet with that
address arrives?
(a) 135.46.63.10
(b) 135.46.57.14
(c) 135.46.52.2
(d) 192.53.40.7
(e) 192.53.56.7
Solution:
Apply longest matching rule.

66
Solution
Apply longest matching rule.

(students should explain why by matching binary form of the
addresses)
(a) 135.46.63.10 à Interface 1
(b) 135.46.57.14 à Interface 0
(c) 135.46.52.2 à Interface 3 (default route)
(d) 192.53.40.7 à Interface 2
(e) 192.53.56.7 à Interface 3 (default route)

67
PCM với 64 mức lượng tử.
Exercise
Câu 2 (1 ñiểm) Câu 2 Vẽ tín hiệu số ñiều chế ñược cho dữ liệu số 10110011100
theo kiểu mã hoá NRZ-L
Câu 3 (2 ñiểm) Nêu các phương pháp ñiều khiển truy cập ñường truyền. Giải
thích cơ chế hoạt ñộng của phương pháp CSMA/CD.
lAssume that we have a network with following
topology. chiaWhat should
con. Xác be
ñịnh sốrouting
máy tối ña trongtable
mỗi mạng?of
Câu 4 (2 ñiểm) Cho một mạng với ñịa chỉ IP là 192.168.1.0/24. Mạng này ñược
thành 5 các mạng Mặt
routers B, C, D in order to assure that all hosts
nạ cho các mạng con là bao nhiêu? Xác ñịnh ñịa chỉ mạng của mỗi mạng
con.
can send data to each other and to the Internet.
Câu 5 (2 ñiểm): Cho một sơ ñồ mạng như hình vẽ, thiết lập bảng ñịnh tuyến trên
các router B, C, D, X ñể các mạng có thể kết nối với nhau và Internet.
Câu 6 (1 ñiểm): TCP là một giao thức tin cậy, nó cung cấp các cơ chế kiểm lỗi,
luồng dữ liệu, tắc nghẽn mà IP không có. Tuy thế UDP không có các cơ
chế này. Vậy tại sao vẫn cần dùng UDP ? Tại sao không thể xây dựng các
ứng dụng trực tiếp trên IP? 68

Solution
lRouting table on B lRouting table on C

Network Next hop Network Next hop
133.133.0.0/16 C 133.133.0.0/16 Direct
155.0.0.0/8 Direct 155.0.0.0/8 B
203.203.203.0/24 D 203.203.203.0/24 D
0.0.0.0/0 D 0.0.0.0/0 D
lRouting table on D
Network Next hop
133.133.0.0/16 C
155.0.0.0/8 B
203.203.203.0/24 Direct
0.0.0.0/0 X
69
Internet Control Message Protocol
Packet format
Ping and Traceroute
70
Idea of ICMP (1)
lIP is unreliable, connectionless

l Lack of supporting and error control mechanism
lICMP is used in network layer for providing a
mechanism to exchange information between
sender and receivers
lError information: inform that a packet cannot reach
a host, a network or a port.

71
Idea of ICMP (2)
• Also in network layer but is “above” IP

• ICMP message is encapsulated in IP
• ICMP message: Type, Code, with 8 first bytes of the
error IP message
ICMP message
IP header ICMP message

72
IP header and Protocol field
Ver HLEN DS Total Length

Fragmentation
Protocol:
Identification Flags
offset 1: ICMP
TTL Protocol Header Checksum 2: IGMP
Source IP address 6: TCP
17: UDP
Destination IP address
89: OSPF
Option
Data

73
ICMP message format
• Type: type of ICMP message

• Code: cause of error
• Checksum
• Rest of header varies according on type
0 78 15 16 31
Type Code Checksum
Rest of the header
Data

74
Some ICMP message types
3 Destination Unreachable
4 Source quench (nguồn giảm tốc độ)
Error-reporting
ICMP Message Type
5 Redirection
messages
11 Time exceeded
12 Parameter problem
8 or 0 Echo reply or request
Query 13 or 14 Time stamp request or reply

messages 17 or 18 Address mask request or reply
9 or 10 Router advertisement or solicitation

75
ICMP code: sub-type
• ICMP code = sub-type

76
ICMP and debuging tools
lICMP always works transparently for users

lUsers can use ICMP by using some debuging
tools
lping
ltraceroute

77
Ping and ICMP
• ping
• Test a connection
• Sender sends packet “ICMP echo request”
• Receiver responses with “ICMP echo reply”
• Data field contains the time stamp when the
packet is sent
• For calculating RTT (round-trip time)

78
Ping: Example
C:\Documents and Settings\hongson>ping www.yahoo.co.uk
Pinging www.euro.yahoo-eu1.akadns.net [217.12.3.11] with 32 bytes of data:
Reply from 217.12.3.11: bytes=32 time=600ms TTL=237

Ping statistics for 217.12.3.11:

Packets: Sent = 4, Received = 4, Lost = 0 (0% loss),
Approximate round trip times in milli-seconds:
Minimum = 529ms, Maximum = 600ms, Average = 556ms

79
Traceroute and ICMP
• Sender send many packets to receiver

• First packet has TTL =1
• Second packet has TTL=2, …
• When packet number n arrives to nth router:
• Router destroys the packer
• Router send back an ICMP packet (type 11, code 0)
containing IP address of the router
• Based on the reply message, the sender can calculate RTT

80
Traceroute and ICMP
Termination condition
• When ICMP echo packet arrive to the destination
• When source receives ICMP “host unreachable”
(type 3, code 3)
3 probes 3 probes
3 probes

81
Traceroute: Example
C:\Documents and Settings\hongson>tracert www.jaist.ac.jp
Tracing route to www.jaist.ac.jp [150.65.5.208]

over a maximum of 30 hops:
1 1 ms <1 ms <1 ms 192.168.1.1

2 15 ms 14 ms 13 ms 210.245.0.42
3 13 ms 13 ms 13 ms 210.245.0.97
4 14 ms 13 ms 14 ms 210.245.1.1
5 207 ms 230 ms 94 ms pos8-2.br01.hkg04.pccwbtn.net [63.218.115.45]
6 * 403 ms 393 ms 0.so-0-1-0.XT1.SCL2.ALTER.NET [152.63.57.50]
7 338 ms 393 ms 370 ms 0.so-7-0-0.XL1.SJC1.ALTER.NET [152.63.55.106]
8 402 ms 404 ms 329 ms POS1-0.XR1.SJC1.ALTER.NET [152.63.55.113]
9 272 ms 288 ms 310 ms 193.ATM7-0.GW3.SJC1.ALTER.NET [152.63.49.29]
10 205 ms 206 ms 204 ms wide-mae-gw.customer.alter.net [157.130.206.42]
11 427 ms 403 ms 370 ms ve-13.foundry2.otemachi.wide.ad.jp [192.50.36.62]
12 395 ms 399 ms 417 ms ve-4.foundry3.nezu.wide.ad.jp [203.178.138.244]
13 355 ms 356 ms 378 ms ve-3705.cisco2.komatsu.wide.ad.jp [203.178.136.193]
14 388 ms 398 ms 414 ms c76.jaist.ac.jp [203.178.138.174]
15 438 ms 377 ms 435 ms www.jaist.ac.jp [150.65.5.208]
Trace complete.

82
Static and dynamic routing
Static routing
Dynamic routing
Advantage – Weakness
83
Problem of update routing table
• When topology change: new networks, a router is out of

power
• It is necessary that routing tables are updated
• In theory, all routers need to be updated
• In reality, only few routers need to be updated
Network Next-hop Network Next-hop Network Next-hop
192.168.0.0/24 B 10.0.0.0/24 A 10.0.0.0/24 B
172.16.0.0/24 B 172.16.0.0/24 C 192.168.0.0/24 B

10.0.0.0/24 Direct 192.168.0.0/24 Direct 172.16.0.0/24 Direct
172.16.1.0/24 B 172.16.1.0/24 C ??
Router A Router B Router C Router D
New Network

10.0.0.0/24 192.168.0.0/24 172.16.0.0/24 172.16.1.0/24

84
How to update routing table?
lStatic routing
lEntries in the routing tables are updated manually
by network administrator.
lDynamic routing
lThe routing table is updated automatically by some
routing protocols running on routers

85
Static routing
• When there is some
failures on a route:
• Impossible to access to Internet
Internet even though
there is an alternative
route
• Admin needs to update
routing table at 10.0.0.1 10.0.0.3 10.0.0.2
Next-hop 10.0.0.3
Extract of routing table at 10.0.0.1
Prefix Next-hop 10.0.0.1
0.0.0.0/0 10.0.0.3
Next-hop 10.0.0.1
Entry causing error
86
Dynamic routing
• When there is failure : Internet

• The entries related on the affected
routes are updated automatically
Extract of routing table of 10.0.0.1

10.0.0.3 10.0.0.2
Prefix Next-hop Alternative route
0.0.0.0/0 10.0.0.2 Next-hop 10.0.0.3
0.0.0.0/0 10.0.0.3 Affected route

10.0.0.1
Next-hop 10.0.0.1

87
Pros/cons
• Static routing
• Pros:
• Stable,
• Secure,
• Not influence by external factor
• Cons:
• Not flexible,
• It is impossible for using automatically backup routes
• Difficult to manage
• Dynamic routing
• Pros
• Easy to manage
• Backup routes are used automatically when there are failures
• Cons
• Not secure
• Complicated routing protocols

88
Routing algorithm and protocols
Dijkstra and Bellman-Ford Algo
link-state and distance-vector protocols
89
Graph representing the networks
• Graph with nodes (routers) and edges (links)
• Weight on each link c(x,y)
• Weigh can be bandwidth, delay, congestion level, cost…
expressing the contribution of the link in the total cost of a
route
• Routing algorithm: Determine the shortest path (in
term of weight) between a pair of two nodes.
3
v w
2 5
u 2 1 z
3
1
2
x y
1
90
Shortest path tree-SPT
v 3 w 5 v w
2
u 2 1 z u z
3
1 2
x 1
y x y
• SPT – Shortest Path Tree

• Compose of shortest paths from a single source node to all other
nodes.
• Each source node has it own SPT

91
Two classes of routing algorithms
lLink-state
lGathering the topology information at a node à
build graph
lRun a path calculation algorithm on the node
lBuild routing table on the node
lOSPF routing protocol
lDistance vector
lEach node build temporary a routing table
lExchange routing tables for finding better routes
through the neighbors
lRIP routing protocol

92
Link-state algorithms- Dijikstra
• Notations:
• G = (V,E) : Graph representing the network: V: set of nodes, E: set
of links
• c(x,y): cost of using link x to y;
• = ∞ f the two nodes are not linked together
• d(v): current cost for going from the source node to node v
• p(v): node right before v on the route from the source to
destination
• T: Set of nodes whose shortest paths have been identified.

93
• Procedures:
• Init():
For each node v, d[v] = ∞, p[v] = NIL
d[s] = 0
• Improve(u,v), where (u,v) is an edge of G
if d[v] > d[u] + c(u,v) then
d[v] = d[u] + c(u,v)
p[v] = u

94
1. Init() ;
2. T = F;
3. Repeat
4. u: u Ï T | d(u) is the smallest;
5. T = T ∪ {u};
6. for all v Î neighbor(u) and v ÏT
7. improve(u,v) ;
8.Until T = V
Browse all vertexes u starting from those are nearest

to the source, and see if it is better (shorter) to go
from the source to a neighbor of u by going through u
95
Dijkstra’s algorithm: Example
Step T 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 Routing table of u:
v w
2 5 destination Next hop
u 2 1 z
3 v v
1 2
x y v w x x
1
u z 10.10.10.0/24 y x
w x
x y
10.10.10.0/24(z) x
SPT of u:
96
Distance-vector algorithm Bellman-Ford (1)
5
v 3 w
2 5
u 2 1 z
3
1 2
x 1
y
Definitions:
du(z) := cost of the shortest path from u to z
We have: Bellman-Ford equation:
du(z) = min {c(u,a) + da(z) }

a
For all a adjacent to x

97
• Vision of u: • u choose the shortest
• Know only neigbour and path to a destination (ex.:
believe on the path z) amongst all paths via
reported by neighbors
its neighbour v, x,w
• Via x:
5 • du(z) = (u,x) + dx(z)
• Via v: Distance reported by x
v w
2 • du(z) = (u,v) + dv(z)
u z • Via w:
1 • du(z) = (u,w) + dw(z)
x y
Amongst all paths from uà z, u chooses to go via the neighbor

that makes the path shortest
Distance vector of u: du(z), du(y), du(x), du(w), du(v)
98
Assume that at the current step: dv(z) = 5, dx(z) = 3, dw(z) = 3
According to B-F eq. :

5
du(z) = min { c(u,v) + dv(z),
v w c(u,x) + dx(z),
2 3
u 5
z c(u,w) + dw(z) }
3 = min {2 + 5,
1
x y 1 + 3,
5 + 3} = 4
Amongst all paths from uà z, u chooses to go via the neighbor
that makes the path shortest
99
• After choosing a path, u advertises its du(z) to

all nodes
• X, v, w… estimate their paths to all other nodes
similarly è shorters distances to other nodes
may be found
• Advertise new distances
• Repeat best path choosing

100
Distance-vector algorithm (2)
Main ideas: At each node:

l Distance vector: vector of all distance
from the current node to all other nodes
l Each node sends periodically its distance
Wait for a DV from
vector to its adjacent nodes neighbor
l When a node x receives a distance
vector, it updates its distance vector by Re-calculate its DV
using equation Bellman-ford
l With some condition, the distance Dx(y)
in each vector will converge to the smallest If DV changes, Inform its
value of dx(y) neighbor

101
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{2+0 , 7+1} = 2
Node x
Cost to Cost to
x y z x y z
x 0 2 7 x 0 2 3 Dx(z) = min{c(x,y) +
y ∞∞ ∞ y 2 0 1 Dy(z), c(x,z) + Dz(z)}
From
from
= min{2+1 , 7+0} = 3
z ∞∞ ∞ z 7 1 0
Node y
Cost to
x y z y
2 1
x ∞ ∞ ∞
x z
y 2 0 1 7
from
z ∞∞ ∞
Node z
Cost to
x y z
x ∞∞ ∞
y ∞∞ ∞
from
z 7 1 0
Time
102
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} Dx(z) = min{c(x,y)+Dy(z), c(x,z)+ Dz(z)}
= min{2+0 , 7+1} = 2 = min{2+1 , 7+0} = 3
Node x
Cost to Cost to Cost to
x y z x y z x y z
x 0 2 7 x 0 2 3 x 0 2 3
y ∞∞ ∞ y 2 0 1 y 2 0 1
từ
từ
từ
z ∞∞ ∞ z 7 1 0 z 3 1 0
Node y
x y z x y z x y z y
2 1
x ∞ ∞ ∞ x 0 2 7 x 0 2 3 x z
y 2 0 1 y 2 0 1 y 2 0 1 7
từ
từ
từ
z ∞∞ ∞ z 7 1 0 z 3 1 0
Node z
x y z x y z x y z
x ∞∞ ∞ x 0 2 7 x 0 2 3
y ∞∞ ∞ y 2 0 1 y 2 0 1
từ
từ
từ
z 7 1 0 z 3 1 0 z 3 1 0
Time
103
Comparison of Link-state and Distance vector
Number of exchange Reliability: If one routers

messages provide incorrect information
lLS: n nodes, E links, O(nE) LS:
messages l The router may send out
incorrect cost
lDV: Exchange only with l Each node calculate its
neighbor own routing table
Convergent time DV:

l Incorrect distance vector
lLS: Complexity O(n2) may be sent out
lDV: Varies l Each node calculate its DV
based to what receives
from the neighbor
l Error propagates in the
network.

104
Implementation of routing protocols
• Link state protocols

• OSPF: open shortest path first
• Implement link information gathering phase for building
topology
• Implement Dijkstra
• IS-IS
• Distance vector protocols
• RIP: routing Information protocol

105
B
Internet
172.16.0.0/24 D
A C
10.0.0.0/24 192.168.0.0/24

Hiarachy in routing
Autonomous system
Intra-domain routing
Inter-domain routing
107
Hierarchical architecture of the Internet
• Internet = Network of networks
• Each network may have a particular routing policy
• Such a network is an Autonomous System (AS)
AS 2
AS 5
AS 1
AS 4
AS 3

108
Concept of Autonomous system
• AS = Set of network nodes that follows a common routing

strategy (protocol, cost convention…)
• ASes are interconnected via routers called gateways
• Each AS is assigned an AS number for identification
• AS Number - 16 bits hay 32 bits.
2914 NTT-COMMUNICATIONS-2914 - NTT America, Inc.

3491 BTN-ASN - Beyond The Network America, Inc.
4134 CHINANET-BACKBONE No.31,Jin-rong Street
6453 GLOBEINTERNET Teleglobe America Inc.
24087 VNGT-AS-AP Vietnam New Generation Telecom
24066 VNNIC-AS-VN Vietnam Internet Network Information Center
17981 CAMBOTECH-KH-AS ISP Cambodia
……………………………….
Source: http://www.cidr-report.org
109
Number of ASN assigned by IANA
Source: http://www.potaroo.net/
2008

110
Hierarchical of routing protocols
• Inside an AS: Intra-domain routing protocol

• IGP: Interior Gateway Protocol
• RIP: Routing Information Protocol
• OSPF: Open Shortest Path First
• IS-IS, IGRP, EIGRP (Cisco)…
• Between AS: Inter-domain routing protocol
• EGP: Exterior Gateway Protocol
• BGP (v4): Border Gateway Protocol

111
Intra-domain and Inter-domain routing
AS2
AS1 IGP EGP

OSPF domain
EGP
RIP domain EGP
EGP
AS4 EGP IGP
IGP AS3
RIP domain
IGP
AS5 OSPF domain
RIP domain
RIP domain
112
Intradomain routing
RIP
OSPF
113
RIP ( Routing Information Protocol)
• RIP v.1, RIP v.2

• Distance vector protocol
• Select best routes according to the number of hop (# of
hops, max = 15 hops)
• RIP v.1: RFC-1058 (www.ietf.org)
From A:
u v Destination number of hops
u 1
A B w v 2
w 2
x 3
x y 3
z C D z 2
y

114
Recall DV route calculation (1)
Net A
133.27.4.0/24
Router A Router Ｃ
To 133.27.4.0/24
1 hop
Net B
Router Ｂ
133.27.5.0/24
Router D

115
Net A
133.27.4.0/24
Router A To 133.27.4.0/24 Router Ｃ

2 hop
To 133.27.4.0/24
1 hop
Net B
Router Ｂ
133.27.5.0/24
Router D
To 133.27.4.0/24
2 hop

116
Net A
133.27.4.0/24
Router A To 133.27.4.0/24 Router Ｃ

2 hop To 133.27.4.0/24
To 133.27.4.0/24 3 hop
1 hop
Net B
Router Ｂ
133.27.5.0/24
Router D
To 133.27.4.0/24
2 hop

117
Net A
133.27.4.0/24
Router A Router Ｃ
To 133.27.4.0/24
1 hop
Net B
Router Ｂ
133.27.5.0/24
Router D
To 133.27.4.0/24
2 hop

118
RIP: Routers exchange information
• Exchange distance vector

• Distance vector are exchanged each 30s
• Each message contains 25 items è May have to send out
more than one message if there are many elements in the
vector

119
OSPF: Open Shortest Path First
• Open: Opened standard of IETF (OSPF v3 is

defined in RFC 2740)
• Shortest Path First: Implement Dijkstra.
• Link-state protocol
• LSA (link state advertisement) is a packet
describing state of some links in a network and is
flooding in the network.
• è all routers in the network has the same database of
link states è Same topology view of the network
• Each link is assigned a weight
• Best path is shortest weighted path.

120
Link state
• Link-State Advertisement (LSA): describes links of a

node and corresponding costs
• Ex: node A
• link to B, cost 30 A 20
• link to D, cost 20 D
• link to C, cost 10 C
10
• Ex: node D 30 50
20
• link to A, cost 20
• link to E, cost 20 B E
• link to C, cost 50
• OSPF metric: weight given to a link
• By default: 100Mbps /bandwidth of interface
• Administator can assign the value

121
Default metric in OSPF
Link Bandwidth Default OSPF metric

56Kbps serial link 1785
64Kbps serial link 1562
T1 (1.544Mbps) serial link 65
E1 (2.048Mbps) serial link 48
4Mbps Token Ring 25
Ethernet 10
16Mbps Token Ring 6
FDDI or Fast Ethernet 1
Gigabit Ethernet / 10G network 1

122
Hierachical OSPF
• Divide big network in smaller part to make routing

more efficient?
• If there are too many routers
• More link state messages to be circulated in the network
• More computational effort is required
• Bigger routing table
• Routing table may be changed more oftenly
l Divide network into areas

123
Hierachical OSPF

124
RIP vs. OSPF comparison
RIP OSPF
Characteristic • Router are equal • Hierachical

• easy to configure • Complex to configure
• Small size network • Medium and big size
network
Scalability x o
Complexity Low High
Convergence Slow Fast
Information exchange Distant vector linkstate
Algorithm Distant vector Link-state

Update neighbor 30s 10s (Hello packet)
Metrics Hop Bandwidth (default)
125
Interdomain routing protocol
126
BGP – Border Gateway Protocol
• Protocol to exchange routing information between autonomous

systems
BGP session: two BGP routers (“peers”) exchange BGP
messages over semi-permanent TCP connection:
• One message is path advertisement
• advertising paths to different destination network prefixes (BGP is a
“path vector” protocol)
• when AS3 border router 3a advertises path AS3,X to AS2 border router
2c: AS3 promises to AS2 it will forward datagrams towards X
AS 3 3b
AS 1b 3a 3c
1
1a 1c AS 2 3d X
2b
1d AS3, X
AS2,AS3,X 2a 2c
2d

127
eBGP and iBGP
• Router connects one AS to another one is called border router

• External BGP vs. Internal BGP
• External BGP is used to exchange routing information between border router of different AS
• Internal BGP is used to exchange routing information between border router of the same AS
• Disseminate routing informaiton
1. 3a sends to 1c by eBGP
2. 1c sends internal routing information to (1b, 1d, …) within AS1 by iBGP
3. 2a receives routing information from 1b by eBGP
eBGP session
3c iBGP session
3a 2c
3b 2a
AS3 2b
1c AS2
1a 1b
AS1 1d
128
BGP: Path vector routing
• Which routing protocol can be used to connect multiple ASes?
• No universal metric – policy decisions
• LS: No, Metric are not the same, LS database too large – entire
Internet
• DV: Bellman-Ford algorithm may not converge
• Solution: Path vector routing.
• The whole path 1is advertise instead of only distance
2 A
A
A B B→A C
3 A
1 C→B→A
A
D E
2 A 4 A
D→A D→A best path
C→B→A ×
129
Path attributes
BGP advertised route: prefix + attributes

• prefix: destination being advertised
• two important attributes:
• AS-PATH: list of ASes through which prefix advertisement has passed. Ex:
4.79.201.0/26 7660 22388 11537 10886 40220
• NEXT-HOP: indicates specific internal-AS router to next-hop AS
• Other attributes: ORIGIN, MED (MULTI_EXIT_DISCRIMINATOR),
LOCAL_PREF, ATOMIC_AGGREGATE, AGGREGATOR, COMMUNITY
policy-based routing:
• Border router receiving route advertisement uses import policy to
accept/decline path (e.g., never route through AS Y).
• AS export policy also determines whether to advertise path to other
other neighboring ASes

Network Layer: 5-130

BGP path advertisement
AS 3 3b
AS 1b 3a 3c
1
1a 1c AS 2 3d X
2b
1d AS3, X
AS2,AS3,X 2a 2c
2d
AS2 router 2c receives path advertisement AS3,X (via eBGP) from AS3 router 3a
based on AS2 policy, AS2 router 2c accepts path AS3,X, propagates (via iBGP) to all
AS2 routers
based on AS2 policy, AS2 router 2a advertises (via eBGP) path AS2, AS3, X to
AS1 router 1c


BGP path advertisement (more)
AS 3 3b
AS 1b AS3,X 3a 3c
1 AS3,X
AS3,X
1a 1c AS 2 3d X
2b
AS3,X
1d AS3, X
AS2,AS3,X 2a 2c
2d
border router may learn about multiple paths to destination:

AS1 border router 1c learns path AS2,AS3,X from 2a
AS1 border router 1c learns path AS3,X from 3a
è based on policy, AS1 border router 1c chooses path AS3,X and advertises path
within AS1 via iBGP


Best route selection steps
If a BGP router receives an advertised route for an known

destination, it compares the new routes with the existing
one on different attributes to find the best:
• Step 1: Compare the value of LOCAL_PREF
• Step 2: Compare the length of AS_PATH
• Step 3: Compare the value of ORIGIN
• Step 4: Compare MED
• Step 5: Compare EBGP/IBGP
• Step 6: Compare the cost to the NEXT_HOP
• Step 7: Compare Router ID

133
Example of BGP routes in routing table
Network Next Hop Metric LocPrf Weight Path

4.79.201.0/26 203.178.136.29 700 500 0 7660 22388 11537 10886 40220
203.178.136.29 700 500 0 7660 22388 11537 10886 40220
203.178.136.29 700 500 0 7660 22388 11537 10886 40220
6.1.0.0/16 203.178.136.29 700 500 0 7660 22388 11537 668
203.178.136.29 700 500 0 7660 22388 11537 668
203.178.136.29 700 500 0 7660 22388 11537 668
6.2.0.0/22 203.178.136.29 700 500 0 7660 22388 11537 668

134
ARP protocol
4.7. Giao thức ARP
MAC address and ARP
• Address Resolution Protocol

• Identify MAC address (used by Datalink layer) of an
interface given its IP address
• Why ARP is necessary?
• Data transmission in network layer uses IP address
• Data transmission in datalink layer uses MAC address
• On sender side, when data is forwarded from network layer to
data link layer:
• If sending data within the same LAN : sender needs to know
MAC address of destination for using layer 2 forwarding
mechanism
• If sending data outside the LAN: sender needs the MAC address
of the default router.

136
ARP operation
• Each network node (host) has an ARP Table:

• Contains mapping <IP address, MAC address, TTL>
• TTL: Time to live of the mapping information in the table (300
seconds)
• For asking MAC address of another node, the node
broadcasts the ARP Request message in the network.
• ARP Request packet contains the IP address of the node to be
searched.
• The node holding the requested IP address should reply
with its MAC address in an ARP Reply message

137
ARP operation – Example
ARP Request
(broadcast) Host B: 10.0.0.2
Who has 10.0.0.2? MAC: 12-29-9C-E8-FF-12
Host C: 10.0.0.3
Host A: 10.0.0.1 MAC: 13-29-9C-E8-FF-13
MAC: 11-29-9C-E8-FF-11 ARP Request
(broadcast)
Who has 10.0.0.2?
Host B: 10.0.0.2
MAC: 12-29-9C-E8-FF-12
Host C: 10.0.0.3
Host A: 10.0.0.1 ARP Request MAC: 13-29-9C-E8-FF-13
MAC: 11-29-9C-E8-FF-11 (broadcast)
Who has 10.0.0.2?
ARP Reply (unicast)
10.0.0.2 is at 12-29-9C-E8-FF-12
Host B: 10.0.0.2
MAC: 12-29-9C-E8-FF-12
Host C: 10.0.0.3
Host A: 10.0.0.1 MAC: 13-29-9C-E8-FF-13
MAC: 11-29-9C-E8-FF-11
138
Data transmission between LANs
Ex: A sends data to B via router R (according to routing table of A)
• A creates an IP packet with source address is A and destination address is B
• The packet is forwarded to the datalink layer of A to be packed in a layer 2 frame
with MAC source address of A and MAC destination address of R
MAC src: 74-29-9C-E8-FF-55

MAC dest: E6-E9-00-17-BB-4B Figure taken from: “Computer Networking: A Top
IP src: 111.111.111.111 Down Approach”, Jim Kurose
IP dest: 222.222.222.222
Net Next hop
IP
Eth 222.222.222.0 111.111.111.110
Phy
A B
R
111.111.111.111
Switch Switch 222.222.222.222
74-29-9C-E8-FF-55
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112 111.111.111.110 222.222.222.221

CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 88-B2-2F-54-1A-0F 139
v Frame is forwarded from A to R by learning mechanism of

switch or multiple access mechanism of layer 2
v At R: the header of the frame is removed and the content is
delivered to the network layer as an IP packet
MAC src: 74-29-9C-E8-FF-55
MAC dest: E6-E9-00-17-BB-4B
Figure taken from: “Computer Networking: A Top
IP src: 111.111.111.111
IP dest: 222.222.222.222 Down Approach”, Jim Kurose
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP IP
Eth Eth
Phy Phy
A B
R1
R R2
111.111.111.111 switch switch 222.222.222.222
74-29-9C-E8-FF-55
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112 111.111.111.110 222.222.222.221

CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B Net Next Inter 88-B2-2F-54-1A-0F
hop face
222.222.222.0 Diirect R2
140
v R chooses the next hop to forward the IP packet with source A and
destination B according to its routing table
v The IP packet is then packaged in a frame of layer 2 with MAC
address of R as source and MAC address of B as destination.
MAC src: 1A-23-F9-CD-06-9B
Figure is taken from: “Computer Networking: A MAC dest: 49-BD-D2-C7-56-2A
Top Down Approach”, Jim Kurose IP src: 111.111.111.111
IP dest: 222.222.222.222
IP
IP Eth
Eth Phy
Phy
A B
R
111.111.111.111 switch R1 R2
switch 222.222.222.222
74-29-9C-E8-FF-55
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112 111.111.111.110 222.222.222.221

CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 88-B2-2F-54-1A-0F
Net Next Inter
hop face
222.222.222.0 Diirect R2
141
DHCP
4.8. DHCP
Introduction
• Dynamic Host Configuration Protocol

• A service of the application layer that distributes
configurations to hosts. Configuration includes
• IP address
• Network mask
• default router, default gateway
• Possibly the address of default DNS servers
• DHCP works using client/server model: DHCP
client hosts use IP addresses given by DHCP
servers.

143
DHCP : IP address distribution process
Server DHCP
3. Request: Cient choose a configuration
1. Discover : search for an available server
2. Offer : Send a configuration 4. Ack : confirm

Offer the configuration
5. Release: realease the configurarion.
Client DHCP Server DHCP

School of Information and Communication Technology 144
DHCP messages
Client Server
• DHCP Discover: search for • DHCP Offer: provide
DHCP Server
configuration including
• DHCP Request: register an IP address
IP address
• DHCP ACK: Accept
• DHCP Release: return the
used IP address to the the registration
pool • DHCP NAK: Refuse
• DHCP Decline: Refuse an the registration
assigned IP address

145
Provide new configuration
DHCP Client DHCP Server
• B1: Client broadcasts DHCP
Discover message to look for
a Server DHCP Discover
• B2: If there is a DHCP Server (broadcast)
in the network,the server
sends DHCP Offer with
address information DHCP Offer
• B3: Client chooses one DHCP Request

configuration from received (broad cast)
DHCP Offers and send
DHCP Request to register
the configuration DHCP ACK
)
• B4: DHCP Server sends a (time period: T
DHCP ACK to accept.

146
Extend the configuration
DHCP Client DHCP Server
• Each configuration is valid in a
time period T à client needs
to extend the validation of the DHCP Request
t = 0.5*T
configuration (unicast)
• When t = 0.5*T, client sends DHCP ACK
DHCP Request to DHCP (time period: T)
Server to extend the lease
Other Server
• If there is no DHCP ACK, at t= DHCP Request
0.875*T, client broadcasts t = 0.875*T
(broadcast)
DHCP Request
• If there is still no DHCP ACK, DHCP ACK
at t = T, client sends DHCP (time period: T)
Discover DHCP Discover
t=T
(broadcast)

147
DHCP Relay
• DHCP Server belong to a different network with the

DHCP client à broadcasting messages are not forwarded
by routers
• à install DHCP Relay on router
DHCP Client Router DHCP Server

DHCP Discover (broadcast) DHCP Discover (unicast)
DHCP Offer DHCP Offer
DHCP Discover (broadcast) DHCP Discover (unicast)
DHCP ACK/NAK DHCP ACK/NAK

148

Chapter 4 - Internet Layer

Uploaded by

Document Informationclick to expand document information

Document Informationclick to expand document information

Copyright:

Available Formats

Chapter 4 - Internet Layer

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chapter 4 - Internet Layer

Uploaded by

Copyright:

Available Formats

Lecture 6:

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

lLayer 2 devices (switches) allow to connect

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Packet (header Router

uniquely a network 223.1.2.1

223.1.1.1 = 11011111 00000001 00000001 00000001

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

• For routing purpose, IP la

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Use 4 x 8 bits describing a 32 bits address

203 178 143 100

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

• IP address contains two parts

203 178 143 100

l How to know which bits belong to network ID or host

8bits 8bits 8bits 8bits

!"#$$%& ' ;89: > > >

lDetermine which classes these IP addresses

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

• Inefficient use of addressing space

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

• Network mask = number of bits in Network ID part

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

255 255 255 224

• 255.255.255.224 • Last byte may

Network part Host Part

203 . 178 . 142 . 130

255 . 255 . 255 . 224

Network address 203.178.142.128/27

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

l Which of the following IP addresses are host

255 255 255 192

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

n bit (32-n) bit

• Number of hosts (Unicast Address):

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

• Hosts of a subnet 223.1.2.1

11001000 00010111 00010000 00000000

11001000 00010111 00010000 00000000

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

lDivide a IP range into sub-ranges of equal size

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

network ID of each subnet

lGiven IP addresses in the range 200.23.16.0/24

• Self assigned IP address: 169.254.0.0/16

lCurrently IPv4: 32 bits

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

• DS (Differentiated Service : 8bits)

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

• Length: total length including header (16 bits)

TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

• TTL, 8 bits – Time to live