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

1Chương 4.
Tầng mạng
Tổng quan
Giao thức IP
Định tuyến
1
1. Tổng quan về
tầng mạng
Tổng quan
Giao thức IP
Định tuyến
2
2Tầng mạng trên kiến trúc phân 
tầng
Application
(HTTP, Mail, )
Datalink
(Ethernet, ADSL)
Physical
(bits)
Hỗ trợ các ứng dụng trên mạng
Điều khiển truyền dữ liệu giữa các tiến trình 
của tầng ứng dụng
Điều khiển truyền dữ liệu giữa các 
nút mạng qua môi trường liên mạng
Hỗ trợ việc truyền thông cho các thành 
phần kế tiếp trên cùng 1 mạng
Truyền và nhận dòng bit trên đường 
truyền vật lý
Transport
(UDP, TCP )
Network
(IP, ICMP)
3
Tầng mạng
 Truyền dữ liệu từ host-host
 Cài đặt trên mọi hệ thống 
cuối và bộ định tuyến
 Đơn vị truyền: datagram
 Bên gửi: nhận dữ liệu từ 
tầng giao vận, đóng gói
 Bên nhận: mở gói, chuyển 
phần dữ liệu trong payload 
cho tầng giao vận
 Bộ định tuyến: định tuyến 
và chuyển tiếp
application
transport
network
data link
physical
application
transport
network
data link
physical
network
data link
physical network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physicalnetwork
data link
physical
4
3Chức năng chính
 Định tuyến (Routing): Tìm tuyến đường (qua các nút 
trung gian) để gửi dữ liệu từ nguồn tới đích
 Chuyển tiếp (Forwarding): Chuyển gói tin trên cổng 
vào tới cổng ra theo tuyến đường
 Định địa chỉ (Addressing): Định danh cho các nút 
mạng
 Đóng gói dữ liệu (Encapsulating): Nhận dữ liệu từ 
giao thức ở trên, thêm tiêu đề mang thông tin điều 
khiển quá trình truyền dữ liệu từ nguồn tới đích
 Đảm bảo chất lượng dịch vụ(QoS): đảm bảo các 
thông số phù hợp của đường truyền theo từng dịch 
vụ
5
Định tuyến và chuyển tiếp
6
1
23
Gói tin (tiêu đề chứa 
địa chỉ đích)
Giao thức
định tuyến
Bảng chuyển tiếp
dest address outgoing port
net. address/net.mask
net. address/net.mask
net. address/net.mask
1
2
1
Giao thức định tuyến xác 
định đường đi ngắn nhất 
giữa 2 bên truyền tin
Bảng chuyển tiếp xác 
định cổng ra (outgoing 
port) để chuyển dữ liệu 
tới đích
4Các giao thức tầng mạng
Giao thức định tuyến
• Tìm đường
• RIP, OSPF, BGP
IP
• Định danh
• Đóng gói
• Chuyển tiếp
• QoS
ICMP
• Báo lỗi
• Kiểm tra trạng thái nút mạng
transport layer: TCP, UDP
link layer
physical layer
Tầng
mạng
7
2. Giao thức IP
8
52.1. Đặc điểm giao thức
 Là giao thức cơ sở của tầng 
mạng
 Kết nối liên mạng
 Là giao thức được định tuyến 
(routed protocol)
 Đòi hỏi phải có các giao thức định 
tuyến để xác định trước đường đi 
cho dữ liệu.
 Giúp ứng dụng tầng trên không 
phụ thuộc vào tầng dưới
9
Đặc điểm của giao thức IP
 Giao thức hướng không liên kết
 Các gói tin được xử lý độc lập
 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 nếu có lỗi 
 Khi cần, ứng dụng sẽ sử dụng dịch vụ tầng trên 
để đảm bảo độ tin cậy (TCP)
10
6Chức năng cơ bản của IP
 Định địa chỉ: địa chỉ IP
 Đóng gói dữ liệu
 Dồn kênh/Phân kênh
 Chuyển tiếp: theo địa chỉ IP (sẽ đề cập trong 
phần sau)
 Đảm bảo chất lượng dịch vụ
11
2.2. Địa chỉ IPv4
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
12
7Địa chỉ IP (IPv4)
 Địa chỉ IP: Một số 32-
bit để định danh cổng 
giao tiếp mạng trên 
nút đầu cuối (PC, 
server, smart phone), 
bộ định tuyến 
 Mỗi địa chỉ IP được 
gán cho một cổng 
duy nhất
 Địa chỉ IP có tính duy 
nhất trong mạng
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 13
Làm thế nào để cấp phát địa chỉ IP?
 Cấp phát cố định(Static IP):
 Windows: Control Panel Network 
Configuration TCP/IP Properties
 Linux: /etc/network/interfaces
 Cấp phát tự động: DHCP- Dynamic Host 
Configuration Protocol
14
8Biểu diễn địa chỉ IPv4
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
15
Địa chỉ IPv4
 Địa chỉ IP có hai phần
 Host ID – phần địa chỉ máy trạm
 Network ID – phần đị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
16
9Các dạng địa chỉ
 Địa chỉ mạng (Network Address):
 Định danh cho một mạng
 Tất cả các bit phần HostID là 0
 Địa chỉ quảng bá (Broadcast Address)
 Địa chỉ dùng để gửi dữ liệu cho tất cả các máy trạm 
trong mạng
 Tất cả các bit phần HostID là 1
 Địa chỉ máy trạm (Unicast Address)
 Gán cho một cổng mạng
 Địa chỉ nhóm (Multicast address): định danh cho 
nhóm
17
Phân lớp địa chỉ IP(Classful 
Addressing)
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 
7 bit
6 bit
H
N
H H
H H
N N H
Multicast
5 bit
# of network # of hosts/1 net
Class A 128 2^24 - 2
Class B 16384 65534
Class C 2^21 254
8bits 8bits 8bits 8bits
18
10
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
 Classless addressing
 Phần địa chỉ mạng sẽ có độ dài bất kỳ
 Dạng địa chỉ: m1.m2.m3.m4 /n, trong đó n (mặt nạ mạng) 
là số bit trong phần ứng với địa chỉ mạng
Cách giải quyết 
19
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
20
11
Mô tả mặt nạ mạng
 Thập phân có chấm 255.255.255.224
 Prefix: /27
 Hexa: 0xFFFFFFe0
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
21
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 110
142
100 00 000
128. .
22
12
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
 2
6
=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
23
Đị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
24
13
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
25
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
26
14
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 
27
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 (tự động cấu hình)
Private address
10.0.0.0/8
172.16.0.0/16 172.31.0.0/16
192.168.0.0/24 192.168.255.0 /24
Loopback address 127.0.0.0 /8
Multicast address
224.0.0.0
～239.255.255.255
28
15
Quản lý địa chỉ IP công cộng
 Internet Corporation for Assigned Names and Numbers 
(ICANN): quản lý toàn bộ tài nguyên địa chỉ IP
 Regional Internet Registries: quản lý địa chỉ IP theo vùng 
(châu Á-Thái Bình Dương, châu Âu và Trung Đông, 
châu Phi, Bắc Mỹ, Nam Mỹ)
 Cơ quan quản lý quốc gia
 Việt Nam: VNNIC
 Nhà cung cấp dịch vụ (ISP)
 Cơ quan, tổ chức
 Ví dụ
ICANN APNIC VNNIC HUST
29
2.3. Khuôn dạng gói 
tin IP
30
16
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
protocol
32 bit destination IP address
Options (if any) E.g. timestamp,
record route
taken, specify
list of routers 
to visit.
31
IP header (1)
 Version: Phiên bản giao thức (4 bits)
 IPv4
 IPv6
 Header length: Độ dài phần đầu: 4bits
 Tính theo từ (4 bytes)
 Min: 5 x 4 (byte)
 Max: 15 x 4 (byte)
 DS (Differentiated Service : 8bits)
 Tên cũ: Type of Service
 Hiện tại được sử dụng trong quản lý QoS
32
17
IP header (2)
 Length: Độ dài toàn bộ, tính cả phần đầu (16 bits)
 Theo bytes
 Max: 65536
 Identifier – Số hiệu gói tin (16 bit)
 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ờ báo phân mảnh(3 bit)
 Fragmentation offset – Vị trí gói tin phân mảnh trong 
gói tin ban đầu (13 bit)
33
IP header (3)
 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
 Upper 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
 Sử dụng để dồn kênh/phân kênh
34
18
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 35
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
36
19
IP header (5)
 Options: 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 37
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 có kích 
thước 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 mảnh
38
20
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)
 1st bit: Dự phòng
 2nd bit: Không được phép phân mảnh
 3rd bit: Còn phân mảnh
 Độ 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
39
Phân mảnh (3)
ID
=x
offset
=0
fragflag
=0
length
=4020
ID
=x
offset
=0
fragflag
=1
length
=1500
ID
=x
offset
=185
fragflag
=1
length
=1500
ID
=x
offset
=370
fragflag
=0
length
=1060
Ví dụ:
 Gói tin: 4020 byte 
(header: 20 byte)
 MTU = 1500 bytes
1480 bytes in 
data field
offset =
1480/8 
40
21
2.4.
Chuyển tiếp gói tin IP
41
Chuyển tiếp gói tin IP
 Mỗi nút mạng sử dụng bảng chuyển tiếp 
(Forwarding Table)
 Là một phần của bảng định tuyến (Routing Table)
 Các thông tin:
 Đích đến (Destination): Địa chỉ mạng/Mặt nạ (/n)
 Sử dụng địa chỉ 0.0.0.0/0 đại diện cho một đích bất kỳ 
chưa biết lối ra mặc định
 Cổng ra (Outgoing port): địa chỉ của cổng ra trên 
router để chuyển tới nút kế tiếp trong đường đi
42
22
Bảng chuyển tiếp
1
23
Gói tin với địa chỉ nút đích
trong phần tiêu đề
Giao thức
định tuyến
Bảng chuyển tiếp
dest address outgoing port
net1. address/net.mask
net2. address/net.mask
net3. address/net.mask
1
2
1
43
Ví dụ - Bảng chuyển tiếp trên 
máy trạm
C:\Documents and Settings\tungbt>netstat –r
Route Table
========================================================================
Interface List
0x1 ........................... MS TCP Loopback interface
0x2 ...08 00 1f b2 a1 a3 ...... Realtek RTL8139 Family PCI Fast Ethernet NIC -
========================================================================
Default Gateway: 192.168.1.1
========================================================================
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
Destination Outgoing port
44
23
Ví dụ - Bảng chuyển tiếp trên 
router (rút gọn)
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
Destination Outgoing port
45
Kết hợp đường đi
 Điều kiện:
 Đường đi có chung Outgoing Port và k bit đầu tiên (prefix) trong 
phần NetworkID của địa chỉ đích giống nhau
 Điều gì xảy ra nếu kết hợp không đầy đủ các mạng con được chia 
từ một mạng lớn hơn. Ví dụ kết hợp 1.1.0.0/16 và 1.2.0.0/16 thành 
1.0.0.0 /14?
 Mục đích: giảm kích thước bảng chuyển tiếp, tăng tốc quá 
trình tìm kiếm đường ra
Destination Outgoing Port
1.1.0.0 /16 Se0/2
1.2.0.0 /16 Se0/2
1.3.0.0 /16 Se/01
171.8.0.0 /19 Se0/1
171.8.32.0 /19 Se0/1
Destination Outgoing Port
1.1.0.0 /16 Se0/2
1.2.0.0 /16 Se0/2
1.3.0.0 /16 Se/01
171.8.0.0 /18 Se0/1
46
24
Nguyên tắc tìm kiếm
 So sánh n bit đầu tiên trên địa chỉ đích gói tin với các bit 
tương ứng trên địa chỉ mạng đích
 /n: Mặt nạ mạng đích
 Nếu có mạng đích khớp chuyển ra cổng tương ứng
 Nếu không có mạng đích nào khớp, chuyển ra cổng mặc định 
(nếu có)
 Quy tắc “longest matching”: nếu có nhiều mạng đích 
thỏa mãn, chuyển tiếp tới mạng đích có mặt nạ lớn nhất
Destination Outgoing Port
11.0.0.0 /8 Se0/1
11.1.0.0 /16 Se0/2
1 ... ập các nút mà đường đi ngắn nhất đã được xác 
định
111
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) 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
112
57
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
113
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:
114
58
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
115
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)
116
59
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
117
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
118
60
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
119
Quảng bá thông tin LSA-
Flooding
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
B nhận được 
2 thông điệp 
giống nhau
120
61
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
121
Phân cấp OSPF
122
boundary router
backbone router
area 1
area 3
backbone
area
border
routers
internal
routers
62
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 
123
Router đại diện - DR
 Để tăng hiệu quả của việc quảng bá LSA trong mạng 
quảng bá đa truy nhập
 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(Backbone DR)?
A
ED
CB
Không có DR
A
ED
CB
Có DR
124
63
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
125
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
126
64
4.4. Định tuyến liên 
vùng
127
4.4.1. Giới thiệu chung 
về BGP
128
65
Yêu cầu mới với các giao thức 
định tuyến liên vùng
 Mỗi AS có chính sách riêng về định tuyến
 Nhà cung cấp X không muốn truyền dữ liệu của họ qua mạng 
nhà cung cấp Y
 Nhà cung cấp X không muốn dữ liệu của nhà cung cấp Z truyền 
qua hệ thống mạng của họ
 Không thể thể hiện những chính sách này trong khái niệm 
“đường đi ngắn nhất”
 Mỗi AS muốn “tự trị”: tự chọn các giao thức định tuyến 
nội vùng và các chính sách định tuyến đi kèm
 Mỗi AS muốn tính “riêng tư”: tự chọn topology, các chính 
sách điều phối hoạt động
129
Yêu cầu mới với các giao thức 
định tuyến liên vùng
 Xuất hiện các mối quan hệ “kinh doanh” trên 
topology và chính sách của mạng:
 AS X có thể là nhà cung cấp (NCC) của AS Y
 AS X có thể là khách hàng (KH) của AS Y
 AS X và AS Y có thể là đối tác ngang hàng (Peer)
 Quan hệ kinh doanh
 Khách hàng trả tiền cho nhà cung cấp
 Đối tác ngang hàng không cần trả tiền
130
66
Định tuyến theo chi phí
(Routing follows the Money)
A
B C
D E
peer peer
NCC KH
Quan hệ giữa các AS
• KH trả tiền cho NCC
• Đối tác ngang hàng: miễn phí
Quan hệ kinh doanh
D E: Đường 
nào rẻ hơn?
E D: Đường 
nào rẻ hơn?
131
Chọn giải thuật định tuyến nào?
 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: BGP chọn đường theo path-vector
A B C
ED
A
D→A
A
C→B→A
A
D→A best path
C→B→A ×
4
A
1
A
1
2
A
B→A
2
3
Chưa xét yếu 
tố chính sách
132
67
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 đường đi 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
133
BGP: Ý tưởng tìm đường
Mỗi AS tính toán đường đi tốt 
nhất khi nhận được danh 
sách đường đi
Mỗi AS quảng bá
những đường đi tốt nhất 
của nó tới các AS khác
Có vẻ như BGP sử dụng lại ý tưởng nào đó!
134
68
BGP sử dụng ý tưởng của DV
 Quảng bá thông tin về đường đi tới đích
 Không chia sẻ thông tin về topology của 
mạng
 Lặp liên tục cho đến khi hội tụ (tìm thấy 
đường đi tốt nhất)
 Với 4 điểm khác biệt
135
BGP khác DV (1)
Không chọn đường đi ngắn nhất
 Đường đi ngắn nhất(qua ít AS nhất) là mục tiêu 
rất quan trọng trong định tuyến liên vùng (vì 
sao?) nhưng không phải là ưu tiên hàng đầu.
 BGP ưu tiên chọn đường theo chính sách trước
2 3
1
Nút 2 có thể chọn
 “2, 3, 1” thay vì “2, 1”
136
69
BGP khác DV (2)
Định tuyến theo vector đường đi
 Ý tưởng chính: quảng bá toàn bộ các chặng trên 
đường đi
 Distance vector: chọn đường dựa trên chi phí của 
đường đi tới các đích có thể xuất hiện đường đi 
quẩn do vấn đề đếm tới vô cùng (count-to-infinity)
 Path vector: chọn đường dựa trên các chặng của 
đường đi tới đích dễ dàng phát hiện các đường đi 
quẩn (loop)
3
2 1
“d: path (2,1)” “d: path (1)”
“d: path (3,2,1)”
d
137
BGP khác DV (3)
Kết hợp đường đi
 BGP có khả năng kết hợp các đường đi tới 
các mạng con không đầy đủ 
VNPT
a.0.0.0/8
HUST
a.b.0.0/16
VNU
a.c.0.0/16
đường đi tới a.*.*.*
foo.com
a.d.0.0/16
138
70
BGP khác DV (4)
Quảng bá có chọn lựa
 Một AS có thể chọn để không quảng bá đường 
đi tới một đích nào đó
 Nói một các khác, một AS có đường đi tới AS 
đích nhưng không đảm bảo sẽ vận chuyển mọi 
lưu lượng mạng tới đó 
Ví dụ: AS2 không muốn
vận chuyển thông tin
từ AS1 tới AS3 
139
AS1 AS3
AS2
Quảng bá có chọn lựa
 Lựa chọn: Đường đi nào được dùng để chuyển 
dữ liệu tới AS đích?
 Kiểm soát thông tin ra khỏi AS
 Quảng bá: Quảng bá cho AS khác đường đi nào?
 Kiểm soát thông tin vào AS
Đường đi
tới đích X
Lựa chọn
Khách hàng
Đối thủ
cạnh tranh
A
B
C
Quảng bá
140
71
Quảng bá có chọn lựa:
Một số chính sách điển hình
 Thay đổi mục tiêu khi định tuyến:
 Tối thiểu hóa chi phí, tối đa hóa lợi nhuận
 Tối đa hóa hiệu năng (đường đi qua ít AS nhất)
 Tối thiểu hóa lưu lượng qua AS (định tuyến kiểu “hot 
potato”)
 ...
 BGP có cơ chế gán thuộc tính cho các tuyến 
đường để thực hiện các mục tiêu trên
141
Quảng bá có chọn lựa
Ví dụ: Định tuyến theo chi phí
 Quan hệ ngang hàng (peer-
peer)
 B quảng bá đường đi của AS 
nào cho A?
 B quảng bá đường đi của A 
cho những AS nào?
 Quan hệ NCC-KH 
(provider-customer)
 B quảng bá đường đi của D 
cho những AS nào?
 B quảng bá đường đi của C 
cho những AS nào?
A
B C
D E
NCC KH
peerpeer
142
72
4.4.2. Hoạt động của 
BGP
143
eBGP, iBGP và IGP
 BGP cài đặt trên các router biên của AS(kết nối tới các 
AS khác): 2 phiên hoạt động
 External BGP (eBGP): thực hiện trao đổi thông điệp với các 
router biên trên AS khác để tìm đường đi tới đích nằm ngoài AS 
của nó
 Internal BGP (iBGP): trao đổi thông điệp với các router biên và 
router nội vùng cùng AS để quảng bá đường đi tới đích nằm 
ngoài AS của nó
 IGP : Interior Gateway Protocol = Intra-domain Routing 
Protocol
 Cài đặt trên router nội vùng
 Tìm đường đi tới đích nằm trong vùng AS
 Dữ liệu tới đích ngoài AS sẽ được chuyển tới router biên 
144
73
eBGP và iBGP – Ví dụ
 Quảng bá thông tin đường đi
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
 1b: Router biên cài BGP
 1a,1d: Router nội vùng cài IGP
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
145
Các thông điệp BGP cơ bản
 OPEN:
 Thiết lập phiên trao đổi thông tin đường đi
 Sử dụng TCP, cổng 179
 NOTIFICATION: thông báo các sự kiện bất thường
 UPDATE:
 Thông báo về đường đi mới
 Thông báo về đường đi không còn khả dụng
 KEEPALIVE: thông báo duy trì kết nối TCP
 Kết nối của TCP cung cấp cho BGP là nửa duy trì (semi-
persistent)
146
74
Phiên trao đổi thông tin của BGP
OPEN: Thiết lập
kết nối TCP cổng 179
Trao đổi thông tin
đường đi đang có
Trao đổi thông điệp
UPDATE, NOTIFICATION
AS1
AS2
Duy trì kết nối
BGP session
UPDATE = 
 IP prefix: địa chỉ của đích
 Thuộc tính gán cho đường đi: sử dụng cho mục 
đích lựa chọn/quảng bá đường đi nào:
 Các thuộc tính nội bộ: chỉ dùng cho các thông điệp 
trao đổi trong AS. Ví dụ: LOCAL-PREF
 Các thuộc tính sử dụng cho eBGP: ORIGIN, AS-
PATH, NEXT-HOP, MED
 Các thuộc tính khác: ATOMIC_AGGREGATE, 
AGGREGATOR, COMMUNITY...
148
75
Thuộc tính(1): AS-PATH
149
 Thông tin về đường đi tới một đích (IP prefix)
 Liệt kê số hiệu các AS trên đường đi tới đích 
(theo thứ tự gần đích tới xa đích)
AS 7018
AT&T 
AS 12654
128.112.0.0/16
AS-PATH = 7018 88
AS 88
Princeton,
 128.112/16
IP prefix = 128.112.0.0/16
AS-PATH = 88
Thuộc tính(2): NEXT-HOP
150
 Địa chỉ IP của router tiếp theo trên đường đi tới 
đích
 Cập nhật trên thông điệp UPDATE ra khỏi AS
AS 88
Princeton,
128.112/16
IP prefix = 128.112.0.0/16
AS path = 88
Next Hop = 192.0.2.1
AS 7018
AT&T 
AS 12654
192.0.2.1
128.112.0.0/16
AS path = 7018 88
Next Hop = 12.127.0.121
12.127.0.121
76
Thuộc tính(3): MED
 Multi-Exit Discriminator
 Dùng cho eBGP
 Sử dụng trong trường hợp 
một AS có nhiều liên kết tới 
một AS khác:
 AS quảng bá đường đi với giá 
trị MED khác nhau qua các liên 
kết khác nhau
 AS nhận thông tin sẽ chọn 
đường đi có MED nhỏ hơn
 điều khiển lưu lượng vào
151
AS1
IP Prefix: 1.0.0.0/10
NEXT-HOP: 1.0.0.1
MED: 50
IP Prefix: 1.0.0.0/10
NEXT-HOP: 1.0.0.2
MED: 100
AS2
1.0.0.1 1.0.0.2
Thuộc tính(3): MED
Routing follow the Money
 Nhà cung cấp (NCC) có 2 điểm 
cáp quang quốc tế cập bờ ở Hải 
Phòng và Vũng Tàu
 Khách hàng(KH) đấu nối với 
NCC tại 2 điểm trên
 Giả sử có lưu lượng Internet 
quốc tế tới AS của NCC tại 
Vũng Tàu và đích là nút mạng 
đặt tại Hà Nội thuộc AS của KH 
 Đặt MED như thế nào?
 Nếu quan hệ là ngang hàng?
152
77
Định tuyến kiểu “hot potato”
 AS chuyển dữ liệu ra khỏi nó nhanh nhất có thể
 Là chiến lược mặc định của các giao thức định tuyến nội 
vùng (IGP)
 Router nội vùng tìm router biên gần nó nhất để chuyển dữ liệu ra 
ngoài AS
 Có thể mâu thuẫn với MED khi cần thì chuyển qua chiến lược 
“cold potato”
153
A
B
C
D
G
EF
4
5
3
9
3
4
108
8
dst
Thuộc tính(4): LOCAL_REF
 Local reference
 Trao đổi trên các thông điệp iBGP
 Gán cho các đường đi tới cùng đích
 Chọn đường đi có LOCAL_REF lớn hơn điều khiển lưu lượng ra
 Không nhầm lẫn với MED
154
AS1
AS2 AS3
AS4
IP Prefix: 7.0.0.0/12
AS-PATH: 2 1
LOCAL_REF: 200
IP Prefix: 7.0.0.0/12
AS-PATH: 3 1
LOCAL_REF: 100
7.0.0.0 /8
78
Thuộc tính (5): ORIGIN
 Chỉ ra nguồn gốc của thông tin về đường đi
 Sử dụng 1 trong 3 giá trị:
 0-IGP: thông tin đường đi học được từ trong AS qua giao thức IGP
 1-EGP: thông tin đường đi học được từ ngoài AS qua giao thức 
EGP (Exterior Gateway Protocol) [RFC904]
 ?-INCOMPLETE: đường đi học được từ nguồn không xác định 
(thường do định tuyến tĩnh)
155
BGP
AS1
EGP 
AS3
BGP
AS2
1.0.0.0 /82.0.0.0 /8IP Prefix: 1.0.0.0/8
ORIGIN: 1
IP Prefix: 2.0.0.0/8
ORIGIN: 0
Sử dụng các thuộc tính
 Thứ tự ưu tiên khi chọn đường
156
Độ ưu tiên Tiêu chí Mục tiêu
1 LOCAL PREF Cao nhất
2 ASPATH Qua ít AS nhất
3 MED Thấp nhất
4 eBGP > iBGP Chọn đường đi học từ AS khác
5 iBGP path Đường đi tới router biên gần nhất
6 Router ID Địa chỉ IP nhỏ nhất
79
Quá trình xử lý thông điệp UPDATE
157
Chính sách
lựa chọn
Cập nhật bảng 
đường đi
tốt nhất
Chọn đường 
đi tốt nhất
Cập nhật bảng 
chuyển tiếp
Chính sách 
quảng bá
Thông điệp
UPDATE 
Cập nhật
thuộc tính
Chấp nhận
đường đi
Từ chối
đường đi
Quảng bá 
(eBGP, iBGP)
Một số vấn đề tồn tại của BGP
 An toàn bảo mật:
 Tấn công vào BGP có thể gây thiệt hại lớn
 Không đảm bảo hiệu năng
 Vì ưu tiên tìm đường theo chính sách trước tìm đường ngắn nhất
 Hội tụ chậm
 Dưới 35% router có thời gian hoạt động 99.99%
 Khoảng 10% có thời gian hoạt động dưới 95%
 40% số đường bị lỗi cần 30 phút để cập nhật xong
 May mắn là hầu hết đường đi đều ổn định.
 Phức tạp khi cần triển khai các chính sách
158
80
Còn rất nhiều vấn đề về tầng 
mạng
 Giao thức IPv6
 Mobile IP
 Định tuyến trên mạng cáp quang
 Định tuyến trên mạng không dây
 Broadcast và Multicast
 An toàn bảo mật thông tin tầng mạng
 An toàn bảo mật cho các giao thức định 
tuyến...
159
Tài liệu tham khảo
 Keio University
 “Computer Networking: A Top Down Approach”, 
J.Kurose
 “Computer Network”, Berkeley University
160