Bài giảng môn Mạng máy tính - Chương 4: Tầng mạng

4/28/2011
1
Chương 4 
Tầng mạng – Internet 
Layer
1
Bài giảng có sử dụng nguồn tài liệu cung cấp bởi trường ðại học Keio, Nhật Bản 
2
Giới thiệu về giao thức 
tầng mạng IP
Khái niệm cơ bản
Nguyên lý lưu-và-chuyển tiếp 
ðặc ñiểm giao thức IP
4/28/2011
2

 Host nào nằm cùng mạng LAN với host 
172.16.116.16 /18 ?
a. 172.16.72.16
b. 172.16.26.16
c. 172.16.130.116
d. 172.16.130.16
3

 ðịa chỉ IP nào sau ñây KHÔNG ñược sử 
dụng làm ñịa chỉ mạng ?
a. 16.16.16.0 /19
b. 96.96.96.0 /19
c. 128.128.128.0 /19
d. 160.160.160.0 /19
4
4/28/2011
3
5
6
Internet Protocol

 Là một giao thức ở tầng mạng 

 Hai chức năng cơ bản 

 ñịnh tuyến (Routing): Xác ñịnh ñường ñi của gói tin từ nguồn ñến 
ñích

 Chuyển tiếp (Forwarding): Chuyển dữ liệu từ ñầu vào tới ñầu ra 
của bộ ñịnh tuyển (router)
application
TCP/UDP
IP
data link
physical
application
TCP/UDP
IP
data link
physical
1. Send data 2. Receive data
4/28/2011
4
7
ñịnh tuyến và chuyển tiếp gói tin
payload IP header
IP packet Ver IHL TOS Packet length
FlagIdentification Fragment Offset
Source IP address
TTL Protocol Header Checksum
Destination IP address
• ðường ñi tiếp theo?
• Chuyển tiếp ñến router 
nào?
Host
Host
Router
Router
Router
8
ðặc ñiểm của giao thức IP

 Không tin cậy / nhanh

 Truyền dữ liệu theo phương thức “best effort”

 IP không có cơ chế phục hồi lỗi 

 Khi cần, sẽ sử dụng dịch vụ tầng trên ñể ñảm bảo 
ñộ tin cậy (TCP)

 Giao thức không liên kết

 Các gói tin ñược xử lý ñộc lập
4/28/2011
5
9
ðịa chỉ IP
Lớp ñịa chỉ IP
CIDR – ðịa chỉ IP không phân lớp
Mạng con và mặt nạ mạng
Các ñịa chỉ IP ñặc biệt
10
ðịa chỉ IP (IPv4)

 ðịa chỉ IP : Một số 
32-bit ñể ñịnh danh 
giao diện máy trạm, 
bộ ñịnh tuyến 

 Mỗi ñịa chỉ IP ñược 
gán cho một giao 
diện

 ðịa chỉ IP có tính duy 
nhất 
223.1.1.1
223.1.1.2
223.1.1.3
223.1.1.4 223.1.2.9
223.1.2.2
223.1.2.1
223.1.3.2223.1.3.1
223.1.3.27
223.1.1.1 = 11011111 00000001 00000001 00000001
223 1 11
4/28/2011
6
11
Ký hiệu thập phân có chấm
8 bits
0 – 255 integer
Sử dụng 4 phần 8 bits ñể miêu tả một ñịa chỉ 32 bits
Ví dụ:
203.178.136.63 o
259.12.49.192 x
133.27.4.27 o
0 1 1 0 0 1 0 01 0 0 0 1 1 1 11 1 0 0 1 0 1 1 1 0 1 1 0 0 1 0
203 178 143 100
3417476964
12
ðịa chỉ máy trạm, ñịa chỉ mạng

 ðịa chỉ IP có hai phần

 Host ID – ñịa chỉ máy trạm

 Network ID – ñịa chỉ mạng
0 1 1 0 0 1 0 01 0 0 0 1 1 1 11 1 0 0 1 0 1 1 1 0 1 1 0 0 1 0
203 178 143 100
Network ID Host ID

 Làm thế nào biết ñược phần nào là cho máy trạm, 
phần nào cho mạng? 

 Phân lớp ñịa chỉ

 Không phân lớp – CIDR
4/28/2011
7
13
Phân lớp ñịa chỉ IP
Class A 0
Class B 1 0
Class C 1 1 0
Class D 1 1 1 0
Class E 1 1 1 1 Reserve for future use 
Multicast
5ｂｉｔ
7ｂｉｔ
6bit
H
N
H H
H H
N N H
# of network # of hosts
Class A 128 2^24
Class B 16384 65536
Class C 2^21 256
8bits 8bits 8bits 8bits
14
Hạn chế của việc phân lớp ñịa chỉ

 Lãng phí không gian ñịa chỉ

 Việc phân chia cứng thành các lớp (A, B, C, D, E) làm hạn 
chế việc sử dụng toàn bộ không gian ñịa chỉ 

 CIDR: Classless Inter Domain Routing

 Phần ñịa chỉ mạng sẽ có ñộ dài bất kỳ

 Dạng ñịa chỉ: a.b.c.d/x, trong ñó x (mặt nạ mạng) là số bit 
trong phần ứng với ñịa chỉ mạng
Cách giải quyết 
4/28/2011
8
15
Mặt nạ mạng

 Mặt nạ mạng chia một ñịa chỉ IP làm 2 phần

 Phần ứng với máy trạm

 Phần ứng với mạng

 Dùng toán tử AND

 Tính ñịa chỉ mạng

 Tính khoảng ñịa chỉ IP
16
Mô tả mặt nạ mạng

 255.255.255.224

 /27

 0xFFFFFFe0

 Sẽ là một 
trong các số:
0 248
128 252
192 254
224 255
240
255 255 255 224
1 1 1 0 0 0 0 01 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
4/28/2011
9
17
Cách tính ñịa chỉ mạng
Netmask (/27) 111 11 111
255 .
111 11 111
255
111 11 111
255
111 00 000
224. .
IP Address 110 10 011
203 .
101 01 010
178
100 10 110
142
100 00 010
130. .
27 (bit)AND
Network address 203.178.142.128/27
Network part Host Part
110 10 011
203 .
101 01 010
178
100 10 111
142
100 00 000
128. .
18
Mặt nạ mạng và kích thước mạng

 Kích thước

 Theo lũy thừa 2

 RFC1878

 Trong trường hợp /26

 Phần máy trạm = 6 bits

 26=64

 Dải ñịa chỉ có thể gán:

 0 - 63

 64 - 127

 128 - 191

 192 - 255
255 255 255 192
1 1 0 0 0 0 0 01 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
4/28/2011
10
19
ðịa chỉ mạng hay máy trạm (1)
1 1 0 0 0 0 0 01 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 0 0 0 00 0 0 0 0 1 0 01 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1
133 27 4 160
1 0 0 0 0 0 0 00 0 0 0 0 1 0 01 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1
133 27 4 128
20
ðịa chỉ mạng hay máy trạm (2)
1 1 1 0 0 0 0 01 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 0 0 0 00 0 0 0 0 1 0 01 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1
133 27 4 160
1 0 0 0 0 0 0 00 0 0 0 0 1 0 01 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1
133 27 4 128
4/28/2011
11
21
Các dạng ñịa chỉ

 ðịa chỉ mạng

 ðịa chỉ IP gán cho một mạng

 ðịa chỉ máy trạm

 ðịa chỉ IP gán cho một card mạng

 ðịa chỉ quảng bá

 ðịa chỉ dùng ñể gửi cho tất cả các máy trạm trong 
mạng

 Toàn bit 1 phần ứng với ñịa chỉ máy trạm
22
ðịa chỉ IP và mặt nạ mạng 
(1) 203.178.142.128 /25
(2) 203.178.142.128 /24
(3) 203.178.142.127 /25
(4) 203.178.142.127 /24

 ðịa chỉ nào là ñịa chỉ máy trạm, ñịa chỉ mạng, 
ñịa chỉ quảng bá? 

 Lưu ý: Với cách ñịa chỉ hóa theo CIDR, ñịa chỉ 
IP và mặt nạ mạng luôn phải ñi cùng nhau
4/28/2011
12
23
Mạng con - subnet

 Là một phần của một 
mạng nào ñó

 ISP thường ñược gán 
một khối ñịa chỉ IP

 Một vài mạng con sẽ 
ñược tạo ra
223.1.1.1
223.1.1.2
223.1.1.3
223.1.1.4 223.1.2.9
223.1.2.2
223.1.2.1
223.1.3.2223.1.3.1
223.1.3.27
Mạng với 3 mạng con
subnet

 Tạo subnet như thế 
nào

 Sử dụng một mặt nạ 
mạng dài hơn
24
11001000 00010111 00010000 00000000
200. 23. 16. 0 /24
Ví dụ: Chia làm 2 subnets
11001000 00010111 00010000 00000000
200. 23. 16. 0 /25
11001000 00010111 00010000 10000000
200. 23. 16. 128 /25
4/28/2011
13
25
Ví dụ: Chia làm 4 subnets

 Mạng với mặt nạ /24 

 Cần tạo 4 mạng con

 Mạng với 14 máy tính

 Mạng với 30 máy tính

 Mạng với 31 máy tính

 Mạng với 70 máy tính
/28 /26 /25/27
/24
/28
/27
/26
/25 
26
Không gian ñịa chỉ IPv4

 Theo lý thuyết

 Có thể là 0.0.0.0 ～ 255.255.255.255

 Một số ñịa chỉ ñặc biệt

 ðịa chỉ IP ñặc biệt (RFC1918)

 ðịa chỉ liên kết nội bộ: 169.254.0.0/16 
Private address
10.0.0.0/8
172.16.0.0/12
192.168.0.0/16
Loopback address 127.0.0.0 /8
Multicast address
224.0.0.0
～239.255.255.255
4/28/2011
14
27
Lưu ý về ñịa chỉ IP

 Internet ñang sử dụng IPv4: 32 bits

 133.113.215.10 (IPv4)

 IPv6 ñã và sẽ ñược sử dụng rộng rãi hơn: 
128bits 

 2001:200:0:8803::53 (IPv6)

 IPv6 sẽ ñược ñề cập kỹ hơn sau.
28
Khuôn dạng gói tin IP
4/28/2011
15
29
Phần ñầu gói tin IP
ver length
32 bits
data 
(variable length,
typically a TCP 
or UDP segment)
16-bit identifier
header
checksum
time to
live
32 bit source IP address
IP protocol version
number
header length
(bytes)
max number
remaining hops
(decremented at 
each router)
for
fragmentation/
reassembly
total datagram
length (words)
upper layer protocol
to deliver payload to
head.
len
DS
QoS support 
flgs
fragment
offset
upper
layer
32 bit destination IP address
Options (if any) E.g. timestamp,
record route
taken, specify
list of routers 
to visit.
30
IP header (1)

 Phiên bản giao thức (4 bits)

 IPv4

 IPv6

 ðộ dài phần ñầu: 4bits

 Tính theo từ (4 bytes)

 Min: 5

 Max: 60
4/28/2011
16
31
IP header (2)

 DS (Differentiated Service : 8bits)

 Tên cũ: Type of Service

 Hiện tại ñược sử dụng trong quản lý QoS

 Diffserv
32
IP header (3)

 ðộ dài toàn bộ, tính cả phần ñầu (16 bits)

 Theo bytes

 Max: 65536

 ID – Số hiệu gói tin

 Dùng ñể xác ñịnh một chuỗi các gói tin của một gói tin bị 
phân mảnh

 Flag – Cờ

 Fragmentation offset – Vị trí gói tin phân mảnh trong 
gói tin ban ñầu
4/28/2011
17
33
IP header (4)

 TTL, 8 bits – Thời gian sống

 ðộ dài ñường ñi gói tin có thể ñi qua

 Max: 255

 Router giảm TTL ñi 1 ñơn vị khi xử lý

 Gói tin bị hủy nếu TTL bằng 0

 Protocol – giao thức tầng trên

 Giao thức giao vận phía trên (TCP, UDP,)

 Các giao thức tầng mạng khác (ICMP, IGMP, OSPF ) cũng 
có trường này
34
IP header (4)

 Checksum – Mã kiểm soát lỗi

 ðịa chỉ IP nguồn

 32 bit, ñịa chỉ của trạm gửi

 ðịa chỉ IP ñích

 32 bit, ñịa chỉ của trạm ñích
4/28/2011
18
35
Phân mảnh gói tin (1)

 ðường truyền có một 
giá trị MTU (Kích thước 
ñơn vị dữ liệu tối ña) 

 Các ñường truyền khác 
nhau có MTU khác 
nhau

 Một gói tin IP lớn quá 
MTU sẽ bị

 Chia làm nhiều gói tin 
nhỏ hơn

 ðược tập hợp lại tại trạm 
ñích
Phân mảnh: 
in: 1 gói tin lớn
out: 3 gói tin nhỏ hơn
Hợp nhất
36
Phân mảnh (2)

 Trường Identification

 ID ñược sử dụng ñể tìm các phần của gói tin

 Flags – cờ (3 bits)

 Dự phòng

 Không ñược phép phân mảnh

 Còn phân mảnh

 Dùng ñể tập hợp gói tin
4/28/2011
19
37
Phân mảnh (3)

 ðộ lệch - Offset

 Vị trí của gói tin phân mảnh trong gói tin ban ñầu

 Theo ñơn vị 8 bytes
0 3999
0 1399
1400 2799
2800 3999
Offset = 0/8 = 0
Offset = 1400/8 = 175
Offset = 2800/8 = 350
1400 2800
38
Checksum

 Mã kiểm soát lỗi cho phần ñầu

 Tại bên gửi

 ðặt checksum = 0

 Tổng theo các số 16 bits

 ðảo bit tất cả 

 Tại bên nhận

 Tổng tất cả theo các số 16 bit

 Phải thu ñược toàn các bit 1

 Nếu không, gói tin bị lỗi
4/28/2011
20
39
Tùy chọn

 Dùng ñể thêm vào các chức năng mới

 Có thể tới 40 bytes
Code (8) Length (8) Data (Variable length) 
copy Class Number
Copy:
0: copy only in first fragment
1: copy into all fragment
Class:
00: Datagram control
01: Reserved
10: Debugging and measurement
11: Reserved
Number:
00000: End of option
00001: No operation
00011: Loose source route
00100: Timestamp
00111: Record route
01001: Strict source route
40
Internet Control Message Protocol
Tổng quan
Khuôn dạng gói tin
Ping và Traceroute
4/28/2011
21
41
Tổng quan về ICMP (1)

 IP là giao thức không tin cậy, không liên kết

 Thiếu các cơ chế hỗ trợ và kiểm soát lỗi

 ICMP ñược sử dụng ở tầng mạng ñể trao ñổi 
thông tin

 Báo lỗi: báo gói tin không ñến ñược một máy trạm, 
một mạng, một cổng, một giao thức.

 Thông ñiệp phản hồi 
42
Tổng quan về ICMP (2)

 Cũng là giao thức tầng mạng, song “phía trên” IP:

 Thông ñiệp ICMP chứa trong các gói tin IP

 ICMP message: Type, Code, cùng với 8 bytes ñầu tiên 
của gói tin IP bị lỗi
IP header ICMP message
ICMP message
4/28/2011
22
43
Nhắc lại: IP header và trường Protocol
DS Total LengthHLENVer
Identification
TTL Protocol Header Checksum
Source IP address
Destination IP address
Flags
Fragmentation
offset
Option
Protocol:
1: ICMP
2: IGMP
6: TCP
17: UDP
89: OSPF
Có thể xem số hiệu giao thức tại
/etc/protocols
C:\WINDOWS\system32\drivers\etc\protocols
44
Khuôn dạng gói tin ICMP

 Type: dạng gói tin ICMP

 Code: Nguyên nhân gây lỗi 

 Checksum

 Mỗi dạng có phần còn lại tương ứng
Type Code Checksum
Rest of the header
Data
0 15 16 317 8
4/28/2011
23
45
Một số dạng gói tin ICMP
IC
M
P
 M
e
ss
a
g
e
 T
yp
e
3
4
5
11
12
8 or 0
13 or 14
17 or 18
9 or 10
Error-reporting
messages
Query
messages
Destination Unreachable
Source quench
Redirection
Time exceeded
Parameter problem
Echo reply or request
Time stamp request or reply
Address mask request or reply
Router advertisement or solicitation
46
ICMP và các công cụ debug

 ICMP luôn hoạt ñộng song trong suốt với 
người sử dụng

 NSD có thể sử dụng ICMP thông qua các 
công cụ debug

 ping

 traceroute
4/28/2011
24
47
Ping và ICMP

 ping

 Sử dụng ñể kiểm tra kết nối 

 Gửi gói tin “ICMP echo request”

 Bên nhận trả về “ICMP echo reply”

 Mỗi gói tin có một số hiệu gói tin

 Trường dữ liệu chứa thời gian gửi gói tin

 Tính ñược thời gian ñi và về - RTT (round-trip 
time) 
48
Ping: Ví dụ
C:\Documents and Settings\admin>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
Reply from 217.12.3.11: bytes=32 time=564ms TTL=237
Reply from 217.12.3.11: bytes=32 time=529ms TTL=237
Reply from 217.12.3.11: bytes=32 time=534ms 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
4/28/2011
25
49
Traceroute và ICMP

 Bên gửi truyền gói tin cho bên nhận

 Gói thứ nhất có TTL =1

 Gói thứ 2 có TTL=2, 

 Khi gói tin thứ n ñến router thứ n:

 Router hủy gói tin

 gửi một gói tin ICMP (type 11, code 0)

 có chứa tên và ñịa chỉ IP của router 

 khi nhận ñược gói tin trả lời, bên gửi sẽ tính ra RTT
50
Traceroute và ICMP
ðiều kiện kết thúc

 Gói tin ñến ñược ñích

 ðích trả về gói tin ICMP “host unreachable” (type 3, 
code 3)

 Khi nguồn nhận ñược gói tin ICMP này sẽ dừng lại

 Mỗi gói tin lặp lại 3 lần
3 probes
3 probes
3 probes
4/28/2011
26
51
Traceroute: Ví dụ
C:\Documents and Settings\admin>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.
ðịnh tuyến
52
4/28/2011
27
53
Cơ bản về ñịnh tuyến (1)

 Khi một máy trạm gửi một gói tin IP tới một máy 
khác

 Nếu ñịa chỉ ñích nằm trên cùng một ñường truyền vật lý: 
Chuyển trực tiếp 

 Nếu ñịa chỉ ñích nắm trên một mạng khác: Chuyển gián 
tiếp qua bộ ñịnh tuyến (ñịnh tuyến)
Router Router
54
ðích ñến（Tìm 
ñường ñi）
ðích ñến? （Tìm 
ñường ñi）
Cơ bản về ñịnh tuyến (2)
4/28/2011
28
55
ðịnh tuyến là gì?

 Cơ chế ñể máy trạm hay bộ ñịnh tuyến 
chuyển tiếp gói tin từ nguồn ñến ñích

 Các thành phần của ñịnh tuyến

 Bảng ñịnh tuyến

 Thông tin ñịnh tuyến

 Giải thuật, giao thức ñịnh tuyến
56
Bộ ñịnh tuyến (router)

 Thiết bị chuyển tiếp các gói tin giữa các 
mạng

 Là một máy tính, với các phần cứng chuyên dụng

 Kết nối nhiều mạng với nhau

 Chuyển tiếp gói tin dựa trên bảng ñịnh tuyến

 Có nhiều giao diện

 Phù hợp với nhiều dạng lưu lượng và phạm 
vi của mạng 
4/28/2011
29
57
Một số ví dụ
Cisco 2600 
Cisco CRS-1 
BUFFALO
BHR-4RV
Router mạng trục
Router ngoại vi 
Router cỡ trung 
Juniper M10
Cisco 3700 
Foundry Networ ... /28/2011
36
71
Biểu diễn mạng bởi ñồ thị
u
yx
wv
z
2
2
1
3
1
1
2
5
3
5

 ðồ thị với các nút (bộ ñịnh tuyến) và các cạnh (liên 
kết)

 Chi phí cho việc sử dụng mỗi liên kết c(x,y) 

 Băng thông, ñộ trễ, chi phí, mức ñộ tắc nghẽn

 Giả thuật ñịnh tuyến: Xác ñịnh ñường ñi ngắn nhất 
giữa hai nút bất kỳ 
72
Cây ñường ñi ngắn nhất - SPT

 SPT – Shortest Path Tree

 Các cạnh xuất phát từ nút gốc và tới các lá

 ðường ñi duy nhất từ nút gốc tới nút v, là ñường ñi ngắn nhất 
giữa nút gốc và nút v

 Mỗi nút sẽ có một SPT của riêng nút ñó
yx
w
u zu
yx
wv
z
2
2
1
3
1
1
2
5
3
5
v
4/28/2011
37
73
Tập trung hay phân tán

 Tập trung

 Thu thập thông tin vào một nút mạng

 Sử dụng các giải thuật tìm ñường ñi trên ñồ thị

 Phân bổ bảng ñịnh tuyến từ nút trung tâm tới các 
nút

 Phân tán

 Mỗi nút tự xây dựng bảng chọn ñường riêng

 Giao thức ñịnh tuyến: Link-state hoặc distance-
vector

 ðược sử dụng phổ biến trong thực tế
74
Giải thuật dạng distance-vector (1)
Phương trình Bellman-Ford (quy hoach ñộng)
ðịnh nghĩa
dx(y) := chi phí của ñường ñi ngắn nhất 
từ x tới y
Ta có
dx(y) = min {c(x,v) + dv(y) }
cho tất cả các v là hàng xóm của x 
v
4/28/2011
38
75
Minh họa Bellman-Ford Eq.
u
yx
wv
z
2
2
1
3
1
1
2
5
3
5
Dễ thấy, dv(z) = 5, dx(z) = 3, dw(z) = 3
du(z) = min { c(u,v) + dv(z),
c(u,x) + dx(z),
c(u,w) + dw(z) }
= min {2 + 5,
1 + 3,
5 + 3} = 4
Nút nào làm giá trị trên nhỏ nhất ➜ Lựa chọn là 
nút kế tiếp trong bảng ñịnh tuyến
B-F eq. cho ta biết:
76
Giải thuật dạng distance-vector (2)
ý tưởng cơ bản:

 DV: Vector khoảng cách, tạm coi là 
ñường ñi ngắn nhất của từ một nút tới 
nút khác

 Mỗi nút ñịnh kỳ gửi DV của nó tới các 
nút bên cạnh

 Khi nút x nhận ñược 1 DV, nó sẽ cập 
nhật DV của nó qua pt Bellman-ford

 Với một số ñiều kiện, ước lượng Dx(y) 
sẽ hội tụ dần ñến giá trị nhỏ nhất dx(y)
Chờ (Thay ñổi trong DV của 
nút bên cạnh)
Tính lại ước lượng DV
Nếu DV thay ñổi, Báo cho 
nút bên cạnh 
Mỗi nút:
4/28/2011
39
77
x y z
x
y
z
0 2 7
∞ ∞ ∞
∞ ∞ ∞
từ
chi phí tới
từ
từ
x y z
x
y
z
0
từ
chi phí tới
x y z
x
y
z
∞ ∞
∞ ∞ ∞
chi phí tới
x y z
x
y
z
∞ ∞ ∞
7 1 0
chi phí tới
∞
2 0 1
∞ ∞ ∞
2 0 1
7 1 0
thờigian
x z
12
7
y
nút x
nút y
nút z
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{2+0 , 7+1} = 2
Dx(z) = min{c(x,y) +
Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
32 
78
x y z
x
y
z
0 2 7
∞ ∞ ∞
∞ ∞ ∞
từ
chi phí tới
từ
từ
x y z
x
y
z
0 2 3
từ
chi phí tới
x y z
x
y
z
0 2 3
từ
chi phí tới
x y z
x
y
z
∞ ∞
∞ ∞ ∞
chi phí tới
x y z
x
y
z
0 2 7
từ
chi phí tới
x y z
x
y
z
0 2 3
từ
chi phí tới
x y z
x
y
z
0 2 3
từ
chi phí tới
x y z
x
y
z
0 2 7
từ
chi phí tới
x y z
x
y
z
∞ ∞ ∞
7 1 0
chi phí tới
∞
2 0 1
∞ ∞ ∞
2 0 1
7 1 0
2 0 1
7 1 0
2 0 1
3 1 0
2 0 1
3 1 0
2 0 1
3 1 0
2 0 1
3 1 0
thờigian
x z
12
7
y
nút x
nút y
nút z
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{2+0 , 7+1} = 2
Dx(z) = min{c(x,y) +
Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
4/28/2011
40
Vấn ñề ñếm tới vô cùng

 Count-to-infinity

 Xảy ra khi có một máy bị down hoặc ñường 
liên kết bị ñứt

 Mỗi router không biết ñường ñi ñến router 
khác lại ñi qua chính nó

 Sau mỗi lần trao ñổi và cập nhật bảng ñịnh 
tuyến, khoảng cách ước lượng sẽ tăng dần 
ñến vô cùng
79
80
RIP ( Routing Information Protocol)

 IGP

 RIP v.1, phiên bản mới RIP v.2

 Giao thức dạng vector khoảng cách

 Chọn ñường ñi theo số nút mạng ñi qua (# of hops, 
max = 15 hops)
DC
BA
u v
w
x
y
z
ðích ñến số nút
u 1
v 2
w 2
x 3
y 3
z 2
Từ nút A:
4/28/2011
41
81

 Bạn của bạn là bạn
To 133.27.4.0/24
1 hop
Net A
133.27.4.0/24
Net B
133.27.5.0/24
Router A
Router Ｂ
Router Ｃ
Router D
Nhắc lại: Chọn ñường dạng DV (1)
82
Nhắc lại: Chọn ñường dạng DV (2)

 Bạn của bạn là bạn
To 133.27.4.0/24
1 hop
Net A
133.27.4.0/24
Net B
133.27.5.0/24
Router A
Router Ｂ
Router Ｃ
Router D
To 133.27.4.0/24
2 hop
To 133.27.4.0/24
2 hop
4/28/2011
42
83
Nhắc lại: Chọn ñường dạng DV (3)

 Bạn của bạn là bạn
To 133.27.4.0/24
1 hop
Net A
133.27.4.0/24
Net B
133.27.5.0/24
Router A
Router Ｂ
Router Ｃ
Router D
To 133.27.4.0/24
2 hop
To 133.27.4.0/24
2 hop
To 133.27.4.0/24
3 hop
84
Nhắc lại: Chọn ñường dạng DV (4)

 Bạn của bạn là bạn
To 133.27.4.0/24
1 hop
Net A
133.27.4.0/24
Net B
133.27.5.0/24
Router A
Router Ｂ
Router Ｃ
Router D
To 133.27.4.0/24
2 hop
Lưu ý: Tên của router
s7
s8
Slide 84
s7 Explain in opposite way: How B is annouced
sonnh, 3/8/2008
s8 Expain that we announce networks address. not router id
sonnh, 3/8/2008
4/28/2011
43
85
RIP: Trao ñổi thông tin

 Trao ñổi bảng chọn ñường

 ðịnh kỳ

 Các vector khoảng cách ñược trao ñổi ñịnh kỳ - 30s

 Mỗi thông ñiệp chứa tối ña 25 mục

 Trong thực tế, nhiều thông ñiệp ñược sử dụng

 Sự kiện

 Gửi thông ñiệp cho nút hàng xóm mỗi khi có thay ñổi

 Nút hàng xóm sẽ cập nhật bảng chọn ñường của nó
86
Các bộ ñếm thời gian - RIP 
timer (1)

 Update timer

 Dùng ñể trao ñổi thông tin cứ 30s

 Invalid timer

 Khởi tạo lại mỗi khi nhận ñược thông tin chọn ñường

 Nếu sau 180s không nhận ñược thông tin -> trạng thái hold-down

 Hold down timer

 Giữ trạng thái hold-down trong 180s

 Chuyển sang trạng thái down

 Flush timer

 Khởi tạo lại mỗi khi nhận ñược thông tin chọn ñường

 Sau 120s, xóa mục tương ứng trong bảng chọn ñường
4/28/2011
44
87
RIP timer (2)
0 30 60 90 120 150 180 210 240 270 300 330 360 390 420
update
↓
update
↓
no
update
↓
Invalid timer
Hold down timer
Flush timer
When it is timeout,
hold down timer starts
When it is timeout,
Routing info will be deleted 
from routing table
When it is timeout,
This info will be deleted 
from RIP database
When it receives update,
Invalid timer restarts
88
RIP: ðể tranh lỗi lặp vô hạn

 Giới hạn số hop tối ña

 v1 : 16

 v2 : 30

 “Split horizon”

 Thông tin chọn ñường không ñược quay về nút 
nguồn

 “Poison reverse”

 Khi liên kết bị lỗi, gửi giá trị của chi phí là 16 
(hoac 30)

 Liên kết chuyển sang trạng thái hold-down
s9
Slide 88
s9 16 TTL vs. this? 
sonnh, 3/8/2008
4/28/2011
45
89
Giải thuật dạng link-state

 Mỗi nút thu thập thông tin từ các nút khác ñể xây 
dựng topo của mạng

 Áp dụng giải thuật tìm ñường ñi ngắn nhất tới mọi 
nút trong mạng

 Khi có sự thay ñổi bảng ñịnh tuyến, mỗi nút gửi 
thông tin thay ñổi cho tất cả các nút khác trong 
mạng.
90
Ký hiệu

 G = (V,E) : ðồ thị với tập ñỉnh V và tập cạnh E

 c(x,y): chi phí của liên kết x tới y; = ∞ nếu không 
phải 2 nút kế nhau

 d(v): chi phí hiện thời của ñường ñi từ nút nguồn tới 
nút ñích. v

 p(v): nút ngay trước nút v trên ñường ñi từ nguồn tới 
ñích

 T: Tập các nút mà ñường ñi ngắn nhất ñã ñược xác 
ñịnh
4/28/2011
46
91
Các thủ tục

 Init():
Với mỗi nút v, d[v] = ∞, p[v] = NIL
d[s] = 0

 update(u,v), trong dó (u,v) u, v là một cạnh 
nào ñó của G
if d[v] > d[u] + c(u,v) then
d[v] = d[u] + c(u,v)
p[v] = u
92
Dijsktra’s Algorithm
1. Init() ;
2. T = Φ;
3. Repeat
4. u: u ∈ T | d(u) là bé nhất ;
5. T = T ∪ {u};
6. for all v ∈ neighbor(u) và v ∉T
7. update(u,v) ;
8. Until T = V
4/28/2011
47
93
Dijkstra’s algorithm: Ví dụ
Step
0
1
2
3
4
5
T
u
ux
uxy
uxyv
uxyvw
uxyvwz
d(v),p(v)
2,u
2,u
2,u
d(w),p(w)
5,u
4,x
3,y
3,y
d(x),p(x)
1,u
d(y),p(y)
∞
2,x
d(z),p(z)
∞ 
∞ 
4,y
4,y
4,y
yx
w
u z
u
yx
wv
z
2
2
1
3
1
1
2
5
3
5
v
v
x
y
w
z
(u,v)
(u,x)
(u,x)
(u,x)
(u,x)
destination link
Bảng ñịnh tuyến của u:
SPT của u:
94
OSPF: Open Shortest Path First

 IGP

 Open: Chuẩn mở của IETF (phiên bản 3, 
ñịnh nghĩa trong RFC 2740)

 Shortest Path First: Cài ñặt giải thuật Dijkstra.

 Thông tin về trạng thái liên kết - LSA (link 
state advertisement) ñược quảng bá “tràn 
ngập” trên toàn AS
s1
Slide 94
s1 Tittle slide
sonnh, 3/8/2008
4/28/2011
48
95
Một số ñặc ñiểm của OSPF

 An toàn: thông ñiệp OSPF ñược bảo vệ

 Với các AS lớn: OSPF phân cấp

 ðịa chỉ không phân lớp (Variable-Length 
Subnet Masking -VLSM )

 Mỗi link sẽ có nhiều giá trị về chi phí khác 
nhau dựa trên TOS (tuy nhiên hơi phức tạp 
và chưa ñược sử dụng)
96
Phân cấp OSPF

 Trong việc chọn ñường, tại sao phải chia mạng 
thành các vùng nhỏ hơn?

 Nếu có quá nhiều router

 Thông tin trạng thái liên kết ñược truyền nhiều lần hơn

 Phải liên tục tính toán lại

 Cần nhiều bộ nhớ hơn, nhiều tài nguyên CPU hơn

 Lượng thông tin phải trao ñổi tăng lên

 Bảng chọn ñường lớn hơn

 Vùng

 Nhóm các router có cùng thông tin LSA
s2
Slide 96
s2 Explain why we need to reduce the calculaiton
sonnh, 3/8/2008
4/28/2011
49
97
Phân cấp OSPF
98
Các dạng router

 ABR - Area border routers: Quản lý 1 vùng và 
kết nối ñến các vùng khác

 ASBR - Autonomous system boundary 
router: Nối ñến các AS khác

 BR - backbone routers: thực hiện OSPF 
routing trong vùng backbone

 Internal Router – Thực hiện OSPF bên trong 
một vùng 
4/28/2011
50
99
Thông tin chọn ñường?

 Link-State Advertisement (LSA): Chỉ ra một nút 
ñược nối tới nút nào (link) và chi phí (cost) tương 
ứng

 Ví dụ: nút A

 link to B, cost 30

 link to D, cost 20

 link to C, cost 10

 Ví dụ: nút D

 link to A, cost 20

 link to E, cost 20

 link to C, cost 50
A
B
C
D
E
20
30
10
20
50
100
Chi phí trong giao thức OSPF -
metric

 Giá trị mặc ñịnh
100Mbps / bandwidth of interface

 Hiện nay người quản trị có thể gán giá trị này

 Khi tính toán bảng chọn ñường

 Chọn ñường ñi chi phí nhỏ nhất

 Chi phí bằng nhau

 Có thể thực hiện cân bằng tải
4/28/2011
51
101
Chi phí mặc ñịnh của OSPF
Link Bandwidth Default OSPF cost
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
102
Quảng bá thông tin LSA
X A
C B D
(a)
X A
C B D
(b)
X A
C B D
(c)
X A
C B D
(d)
X has link to A, cost 10
X has link to C, cost 20
LSAX
LSAX
LSAX
LSAX
LSAX
LSAX
s3
Slide 102
s3 What information is flood
sonnh, 3/8/2008
4/28/2011
52
103
Router ñại diện - DR

 ðể tăng hiệu quả của việc quảng bá LSA

 Mỗi router phải lập quan hệ với router ñại diện -
designated router (DR)

 Trao ñổi thông tin thông qua DR

 DR dự phòng

 Chọn DR và BDR?
A
ED
CB
Không có DR
A
ED
CB
Có DR
104
Neighbor & Adjacency

 “Neighbor” và “adjacency” là các k/n khác nhau!

 Adjacency: có trao ñổi thông tin

 Neighbor: có ñường nối trực tiếp

 Mạng quảng bá ña truy cập (e.g Ethernet)

 Neighbor != Adjacency

 Mạng ñiểm-nối-ñiểm

 Neighbor == Adjacency
s4
Slide 104
s4 Chang the order 
sonnh, 3/8/2008
4/28/2011
53
105
So sánh các giải thuật LS và DV 
Thông ñiệp trao ñổi

 LS: n nút, E cạnh, O(nE) 
thông ñiệp

 DV: Chỉ trao ñổi giữa các 
hàng xóm

 Thời gian hội tụ thay 
ñổi
Tốc ñộ hội tụ

 LS: Thuật toán: O(n2) cần 
O(nE) thông ñiệp

 DV: Thay ñổi
Sự chắc chắn: Giải sử một 
router hoạt ñộng sai
LS:

 nút gửi các chi phí sai

 Mỗi nút tính riêng bảng 
chọn ñường -> có vẻ chắc 
chắn hơn
DV:

 DV có thể bị gửi sai

 Mỗi nút tính toán dựa trên 
các nút khác 

 Lỗi bị lan truyền trong 
mạng
106
RIP vs. OSPF
RIP OSPF
ðặc ñiểm • Router bình ñẳng
• Cấu hình dễ dàng
• Mạng cỡ nhỏ
• Phân câp 
• Cấu hình phức tạp
• Mạng cỡ vừa và lớn
Khả năng mở rộng x o
ðộ phức tạp tính toán Nhỏ Lớn
Hội tụ Chậm Nhanh
Trao ñổi thông tin Bảng chọn ñường Trạng thái liên kết
Giải thuật Distant vector Link-state
Cập nhật hàng xóm 30s 10s (Hello packet)
ðơn vị chi phí Số nút mạng Băng thông
s6
Slide 106
s6 Exchanged informatio
Rip:
OSPF
sonnh, 3/8/2008
4/28/2011
54
ðịnh tuyến liên vùng
107
108
BGP – Border Gateway 
Protocol

 Yếu tố gắn kết của Internet, kết nối các hệ tự trị

 Trao ñổi thông tin NLRI (Network Layer Reachability 
Information)

 Cho phép một AS biết ñược thông tin ñi ñến AS khác

 Gửi thông tin này vào bên trong AS ñó

 Xác ñịnh ñường ñi tốt nhất dựa trên thông tin ñó và các 
chính sách chọn ñường

 Cho phép thiết lập các chính sách

 Chọn ñường ra

 Quảng bá các ñường vào
4/28/2011
55
109
BGP: Path vector routing

 Giữa các AS nên dùng giao thức nào?

 Khó có một chính sách và ñơn vị chi phí chung

 LS: Chi phí không ñồng nhất, CSDL quá lớn

 DV: Mạng quá rộng, khó hội tụ

 Giải pháp: Chọn ñường theo path-vector
A B C
ED
A
A
D→A
A
B→A
A
C→B→A
A
A
D→A best path
C→B→A ×
4
1
1
2
2
3
s12
110
eBGP và iBGP

 External BGP vs. Internal BGP

 Phân tán thông tin chọn ñường
1. 3a gửi tới 1c bằng eBGP
2. 1c gửi thông tin nội bộ tới (1b, 1d, ) trong AS1 bằng iBGP
3. 2a nhận thông tin từ 1b bằng eBGP
3b
1d
3a
1c
2a
AS3
AS1
AS2
1a
2c
2b
1b
3c
eBGP session
iBGP session
s13
Slide 109
s12 Change the symbol of router into AS
sonnh, 2/29/2008
Slide 110
s13 - We have to explain why we have two kind of BGP
(Or we ask student)
- iBGP: internal
-e: external
sonnh, 2/29/2008
4/28/2011
56
Chuyển tiếp gói tin
111
Chuyển tiếp gói tin

 Nhắc lại:

 Gói tin có

 ðịa chỉ ñích (Destination Address - DA)

 Thời gian sống (TTL)

 Bảng ñịnh tuyến có :

 Mạng ñích (Destination Network/Netmask – DN/NM)

 Cổng ra : Outgoing port

 Có thể có cổng ra mặc ñịnh: Default gateway
112
4/28/2011
57
Chuyển tiếp gói tin

 B1 : Nếu TTL = 0, hủy gói tin. Kết thúc.

 B2 : Nếu TTL >0, lấy ñịa chỉ ñích DA 
của gói tin

 B3 : Trên dòng ñầu tiên của bảng ñịnh 
tuyến, mặt nạ hóa M = DA and NM

 B4 : Nếu M = DN, chuyển gói tin ra 
Outgoing Port tương ứng. Kết thúc.

 B5 : Nếu M # DN, chuyển sang dòng 
tiếp theo

 B6 : Nếu hết các dòng, kiểm tra Default 
gateway.

 B7 : Nếu có Default gateway, chuyển 
gói tin ra Default gateway. Kết thúc.

 B8 : Nếu không có default gateway, hủy 
gói tin. Kết thúc.
113
Destination Outgoing 
Port
Destination 
Address
TT
L
45.45.160.0 /19 E3 45.45.100.64 0
45.45.64.0 /19 E1 45.45.100.64 5
45.45.96.0 /20 E3 45.45.145.144 15
45.64.0.0 /10 E2
45.45.96.144 /26 E1
114
Cho bảng ñịnh tuyến của một router trong bảng 1. Hãy 
cho biết router xử lý như thế nào khi nhận ñược các gói 
tin có các thông số trong bảng 2.
4/28/2011
58
DHCP
115
Cấp phát cấu hình mới
116
4/28/2011
59
Gia hạn sử dụng
117
Chuyển tiếp DHCP
118
4/28/2011
60
NAT
119
NAT

 NAT : Network Address Translation

 Chuyển ñổi IP cục bộ sang IP công cộng

 Và ngược lại

 PAT : Port Address Translation

 NAT with overloading sử dụng thêm cổng ứng dụng

 Lợi ích:

 Tiết kiệm ñịa chỉ IP công cộng

 Che giấu ñịa chỉ riêng

 Giảm chi phí cấu hình khi thay ñổi ISP
120
4/28/2011
61
NAT
121

 Các thuật ngữ

 ðịa chỉ cục bộ bên trong (ILA)

 ðịa chỉ công cộng bên trong (IGA)

 ðịa chỉ cục bộ bên ngoài (OLA)

 ðịa chỉ công cộng bên ngoài (OGA)

 NAT Table

 PAT Table
ILA IGA OGA
192.168.1.2 1.1.1.1 2.2.2.2
192.168.1.3 1.1.1.1 2.2.2.2
ILA IGA
192.168.1.2 : 1000 1.1.1.1 : 2000
192.168.1.2 : 1000 1.1.1.1 : 2001
NAT tĩnh – Static NAT
122
4/28/2011
62
NAT ñộng (Dynamic NAT)
123
PAT (NAT with overloading)
124