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

1-1
Mạng máy tính
Bộ môn Kỹ thuật máy tính và Mạng
Khoa Công nghệ Thông tin
Đại học Sư phạm Hà Nội
1-2
Chương 4: Tầng mạng
Mục đích:
‰Hiểu các nguyên tắc bên trong dịch vụ tầng
mạng:
 Chọn đường
 Vấn đề quy mô
 Cách làm việc của Router
 Các chủ đề nâng cao: IPv6, mobility
‰ Ví dụ và cài đặt trong Internet
1-3
Chương 4: Tầng mạng
‰ 4.1 Tổng quan
‰ 4.2 Mạng Virtual circuit 
và datagram
‰ 4.3 Bên trong Router
‰ 4.4 IP: Internet Protocol
 Định dạng Datagram
 Địa chỉ IPv4
 ICMP
 IPv6
‰ 4.5 Thuật toán dẫn
đường
 Link state
 Distance Vector
 Hierarchical routing
‰ 4.6 Dẫn đường trong
Internet
 RIP
 OSPF
 BGP
‰ 4.7 Dẫn đường
broadcast và multicast
1-4
Tầng mạng
‰ Chuyển segment từ host 
gửi tới host nhận
‰ Bên gửi đóng gói
segment thành các
datagram
‰ Bên nhận chuyển các
segment tới tầng giao vận
‰ Các giao thức tầng mạng
có trong mọi host, router
‰ Router kiểm tra trường
header trong mọi IP 
datagram chuyển qua nó
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
application
transport
network
data link
physical
application
transport
network
data link
physical
1-5
Chức năng chính của tầng mạng
‰Chuyển tiếp: chuyển
các gói tin từ đầu vào
router sang đầu ra
thích hợp của router
‰Dẫn đường: xác định
đường đi của gói tin từ
nguồn tới đích. 
 Các thuật toán dẫn
đường
Liên hệ:
‰Dẫn đường: Quá trình
lập kế hoạch chuyến đi
từ nguồn đến đích
‰Chuyển tiếp: Quá trình
xử lý qua một điểm
đơn
1-6
1
23
0111
Giá trị trong header
của gói tin đến
Thuật toán dẫn đường
Bảng chuyển tiếp cục bộ
Giá trị header Đường ra
0100
0101
0111
1001
3
2
2
1
Ảnh hưởng giữa chọn đường và chuyển tiếp
1-7
Thiết lập kết nối
‰Chức năng quan trọng thứ 3 trong một số
kiến trúc mạng:
 ATM, frame relay, X.25
‰ Trước luồng datagram, hai host và các router 
ở giữa thiết lập một kết nối ảo
 Router tham gia
‰Dịch vụ tầng mạng và tầng giao vận:
 Tầng mạng: giữa hai host
 Tầng giao vận: giữa hai tiến trình
1-8
Mô hình dịch vụ mạng
Q: Mô hình dịch vụ nào cho kênh truyền các datagram 
từ bên gửi tới bên nhận?
Ví dụ các dịch vụ cho từng
datagram:
‰ Truyền đảm bảo
‰ Truyền đảm bảo độ trễ
nhỏ hơn 40 msec
Ví dụ các dịch vụ cho một
luồng datagram:
‰ Chuyển datagram đúng
thứ tự
‰ Đảm bảo tốc độ tối
thiểu cho luồng
‰ Hạn chế sự thay đổi
khoảng cách giữa các
gói tin
1-9
Các mô hình dịch vụ của tầng mạng
Kiến trúc
mạng
Internet
ATM
ATM
ATM
ATM
Mô hình
dịch vụ
best effort
CBR
VBR
ABR
UBR
Bandwidth
none
tốc độ
hằng số
tốc độ
đảm bảo
đảm bảo
mức tối thiểu
none
Mất gói
Không
Có
Có
Không
Không
Thứ tự
Không
Có
Có
Có
Có
Thời gian
Không
Có
Có
Không
Không
Phản hồi
tắc nghẽn
Không (suy ra
từ loss)
Không
tắc nghẽn
Không
tắc nghẽn
Có
Không
Đảm bảo ?
1-10
Chương 4: Tầng mạng
‰ 4. 1 Tổng quan
‰ 4.2 Mạng Virtual circuit 
và datagram
‰ 4.3 Bên trong Router
‰ 4.4 IP: Internet Protocol
 Định dạng Datagram
 Địa chỉ IPv4
 ICMP
 IPv6
‰ 4.5 Thuật toán dẫn
đường
 Link state
 Distance Vector
 Hierarchical routing
‰ 4.6 Dẫn đường trong
Internet
 RIP
 OSPF
 BGP
‰ 4.7 Dẫn đường
broadcast và multicast
1-11
Dịch vụ hướng kết nối
và không hướng kết nối của tầng mạng
‰Mạng datagram cung cấp dịch vụ không
hướng kết nối ở tầng mạng
‰Mạng VC cung cấp dịch vụ hướng kết nối ở
tầng mạng
‰ Tương tự với các dịch vụ của tầng giao vận, 
nhưng:
 Dịch vụ: host tới host
 Không cho phép chọn: Mạng cung cấp datagram 
hoặc VC
 Cài đặt: trong phần lõi
1-12
Virtual circuit
‰ Thiết lập mỗi cuộc gọi trước khi dữ liệu có thể truyền
‰ Mỗi gói tin mạng một định danh VC (không phải địa chỉ host 
đích)
‰ Mọi router trên đường đi từ nguồn tới đích duy trì trạng thái
cho mỗi kết nối đi qua
‰ Tài nguyên router, đường truyền (bandwidth, vùng đệm) cấp
phát cho VC
“Đường đi từ nguồn tới đích giống như mạng điện thoại”
 Hiệu năng tốt
 Sự kiện mạng theo đường đi từ nguồn tới đích
1-13
Cài đặt VC
Một VC bao gồm:
1. Đường đi từ nguồn tới đích
2. VC number, một số cho mỗi đường truyền dọc
đường đi
3. Điểm vào trong bảng chuyển tiếp trong router 
trên đường đi
‰ Gói tin thuộc về VC mạng số VC.
‰ Số VC phải thay đổi trên mỗi đường truyền.
 Số VC mới từ bảng chuyển tiếp
1-14
Bảng chuyển tiếp
12 22 32
1 2
3
Số VC
Số giao diện
Giao diện đến VC # đến Giao diện đi VC # đi
1 12 2 22
2 63 1 18 
3 7 2 17
1 97 3 87
Bảng chuyển tiếp
của router phía trên bên trái:
Các Router duy trì thông tin trạng thái kết nối!
1-15
Virtual circuit: Giao thức báo hiệu
‰ Sử dụng để thiết lập, duy trì, chấm dứt VC
‰ Sử dụng trong ATM, frame-relay, X.25
‰ Không sử dụng trong Internet hiện nay
application
transport
network
data link
physical
application
transport
network
data link
physical
1. Khởi đầu cuộc gọi 2. Cuộc gói đến
3. Chấp nhận cuộc gọi4. Cuộc gọi được kết nối
5. Luồng dữ liệu bắt đầu 6. Nhận dữ liệu
1-16
Mạng datagram
‰ Không thiết lập cuộc gọi tại tầng mạng
‰ Router: không có trạng thái về các kết nối end-to-end
 Không có khái niệm mức mạng về kết nối
‰ Các gói tin chuyển tiếp sử dụng địa chỉ của host đích
‰ Các gói tin cùng cặp địa chỉ nguồn-đích có thể đi
theo các đường khác nhau
application
transport
network
data link
physical
application
transport
network
data link
physical
1. Gửi dữ liệu 2. Nhận dữ liệu
1-17
Bảng chuyển tiếp
Dải địa chỉ đích Giao diện đường truyền
11001000 00010111 00010000 00000000
tới 0 
11001000 00010111 00010111 11111111
11001000 00010111 00011000 00000000
tới 1
11001000 00010111 00011000 11111111 
11001000 00010111 00011001 00000000
tới 2
11001000 00010111 00011111 11111111 
trường hợp khác 3
4 tỷ điểm vào
1-18
Tương ứng tiền tố dài nhất
Prefix Match Giao diện đường truyền
11001000 00010111 00010 0 
11001000 00010111 00011000 1
11001000 00010111 00011 2
Trường hợp khác 3
DA: 11001000 00010111 00011000 10101010 
Ví dụ
DA: 11001000 00010111 00010110 10100001 Giao diện?
Giao diện?
1-19
Mạng datagram hay mạng VC
Internet
‰ Dữ liệu trao đổi giữa các máy tính
 Dịch vụ co giãn, không yêu
cầu thời gian chặt chẽ. 
‰ Các hệ thống cuối “thông minh”
(máy tính)
 Có thể thích nghi, thực hiện
điều khiển, khôi phục lỗi
 Bên trong mạng đơn giản, 
phía rìa ngoài mạng phức tạp
‰ Nhiều kiểu đường truyền
 Đặc điểm khác nhau
 Dịch vụ không thống nhất
ATM
‰ Phát triển từ điện thoại
‰ Cuộc nói chuyện của con 
người: 
 Yêu cầu thời gian, độ tin 
cậy chặt chẽ
 Cần đảm bảo dịch vụ
‰ Hệ thống cuối không cần “thông
minh”
 Điện thoại
 Sự phức nằm bên trong
mạng
1-20
Chương 4: Tầng mạng
‰ 4. 1 Tổng quan
‰ 4.2 Mạng Virtual circuit 
và datagram
‰ 4.3 Bên trong Router
‰ 4.4 IP: Internet Protocol
 Định dạng Datagram
 Địa chỉ IPv4
 ICMP
 IPv6
‰ 4.5 Thuật toán dẫn
đường
 Link state
 Distance Vector
 Hierarchical routing
‰ 4.6 Dẫn đường trong
Internet
 RIP
 OSPF
 BGP
‰ 4.7 Dẫn đường
broadcast và multicast
1-21
Tổng quan về kiến trúc của Router 
Hai chức năng chính của router
‰ Chạy các giao thức/thuật toán chọn đường (RIP, OSPF, BGP)
‰ Chuyển tiếp các datagram từ đường truyền vào sang đường truyền
ra
1-22
Chức năng của cổng vào
Chuyển tiếp không tập chung:
‰ Dựa vào của datagram, tìm kiếm cổng ra
sử dụng bảng chuyển tiếp trong bộ nhớ
cổng vào
‰ Mục đích: xử lý cổng vào với tốc độ của
đường truyền
‰ Xếp hàng: Nếu các datagram đến nhah
hơn tốc độ chuyển tiếp vào trong switch 
fabric
Tầng vật lý:
nhận mức bít
Tầng liên kết dữ liệu:
ví dụ: Ethernet
chi tiết trong chương 5
1-23
Ba kiểu switch fabric
1-24
Chuyển mạch qua bộ nhớ
Router thế hệ đầu tiên:
‰ Các máy tính truyền thống chuyển mạch dưới sự
điều khiển trực tiếp của CPU
‰ Các gói tin được sao chép vào trong bộ nhớ của hệ
thống
‰ Tốc độ bị hạn chế bởi bandwidth của bộ nhớ (2 lần
truy nhập bus đối với mỗi datagram)
Cổng vào Cổng raBộ nhớ
Bus hệ thống
1-25
Chuyển mạch qua bus
‰ Datagram từ bộ nhớ cổng vào chuyển sang 
bộ nhớ cổng ra thông qua bus dùng chung
‰ Cạnh tranh bus: tốc độ chuyển mạch bị giới
hạn bởi bandwidth của của bus
‰ Bus 1 Gbps, Cisco 1900: tốc độ đủ cho các
router doanh nghiệp (khác router cho vùng, 
mạng backbone)
1-26
Chuyển mạch qua mạng kết nối
‰ Giải quyết hạn chế vấn đề bandwidth của bus
‰ Mạng Banyan, mạng các kết nối ban đầu được phát
triển để kết nối các processor trong multiprocessor
‰ Thiết kế tiên tiến: phân mảnh các datagram thành
các cell có độ dài cố định, chuyển mạch các cell qua 
fabric. 
‰ Cisco 12000: chuyển mạch Gbps qua mạng kết nối
1-27
Cổng ra
‰ Đệm khi datagram đến fabric nhanh hơn tốc độ
truyền
‰ Nguyên tắc lập lịch chọn các datagram đang xếp
hàng để truyền
1-28
Xếp hàng tại cổng ra
‰ Đệm khi tốc độ đến qua switch vượt quá tốc độ
đường ra
‰ Xếp hàng (trễ) và mất gói bởi vì vùng đệm của cổng
ra bị tràn!
1-29
Xếp hàng ở cổng vào
‰ Fabric chậm hơn cổng vào -> xếp hàng có thể xảy ra ở hàng đợi
cổng vào
‰ Head-of-the-Line (HOL) blocking: các datagram xếp hàng tại trước
hàng đợi ngăn không cho datagram khác chuyển tiếp
‰ Độ trễ và mất gói khi xếp hàng bởi vì tràn vùng đệm vào!
1-30
Chương 4: Tầng mạng
‰ 4. 1 Tổng quan
‰ 4.2 Mạng Virtual circuit 
và datagram
‰ 4.3 Bên trong Router
‰ 4.4 IP: Internet Protocol
 Định dạng Datagram
 Địa chỉ IPv4
 ICMP
 IPv6
‰ 4.5 Thuật toán dẫn
đường
 Link state
 Distance Vector
 Hierarchical routing
‰ 4.6 Dẫn đường trong
Internet
 RIP
 OSPF
 BGP
‰ 4.7 Dẫn đường
broadcast và multicast
1-31
Tầng mạng của Internet
Bảng
chuyển tiếp
Chức năng tầng mạng của host, router:
Giao thức dẫn đường
•Chọn đường
•RIP, OSPF, BGP
Giao thức IP
•Quy tắc đánh địa chỉ
•Định dạng datagram
•Quy tắc điều khiển gói tin
Giao thức ICMP
•Thông báo lỗi
•Báo hiệu của router
Tầng giao vận: TCP, UDP
Tầng liên kết dữ liệu
Tầng vật lý
Tầng
mạng
1-32
Chương 4: Tầng mạng
‰ 4. 1 Tổng quan
‰ 4.2 Mạng Virtual circuit 
và datagram
‰ 4.3 Bên trong Router
‰ 4.4 IP: Internet Protocol
 Định dạng Datagram
 Địa chỉ IPv4
 ICMP
 IPv6
‰ 4.5 Thuật toán dẫn
đường
 Link state
 Distance Vector
 Hierarchical routing
‰ 4.6 Dẫn đường trong
Internet
 RIP
 OSPF
 BGP
‰ 4.7 Dẫn đường
broadcast và multicast
1-33
Định dạng IP datagram
ver length
32 bits
dữ liệu
(chiều dài thay đổi,
thường là một TCP 
hoặc UDP segment)
16-bit identifier
Internet
checksum
time to
live
32 bit địa chỉ IP nguồn
Số phiên bản
của giao thức IP
Chiều dài header 
(byte)
Số hop tối đa còn lại
(giảm tại mỗi router)
để phân
mảnh/
ghép phân
mảnh
tổng chiều dài
của datagram
(byte)
Giao thức của tầng trên
để chuyển payload
head.
len
type of
service
“kiểu” dữ liệu flgs fragmentoffset
upper
layer
32 bit địa chỉ IP đích
Tùy chọn Ví dụ: 
timestamp,
bản ghi đường
đi
(danh sách
các router đi
qua)
Overhead của TCP?
‰ 20 byte của TCP
‰ 20 byte của IP
‰ = 40 byte + 
Overhead của
tầng ứng dụng
1-34
Phân mảnh và ghép phân mảnh
IP datagram
‰ Liên kết mạng có MTU (kích
thước truyền tối đa) – frame 
mức liên kết dữ liệu lớn nhất có
thể.
 Các kiểu liên kết khác nhau, 
MTU khác nhau
‰ Sự phân mảnh IP datagram:
 Một datagram thành nhiều
datagram
 Chỉ ghép lại tại đích
 Sử dụng thông tin trong IP 
header để xác định, xếp thứ
tự các phân mảnh
Phân mảnh: 
Vào: một datagram lớn
Ra: 3 datagram nhỏ hơn
Ghép phân mảnh
1-35
Sự phân mảnh và ghép phân mảnh
IP datagram
ID
=x
offset
=0
fragflag
=0
length
=4000
ID
=x
offset
=0
fragflag
=1
length
=1500
ID
=x
offset
=185
fragflag
=1
length
=1500
ID
=x
offset
=370
fragflag
=0
length
=1040
Một datagram lớn chia thành
nhiều datagram nhỏ hơn
Ví dụ
‰ Datagram: 4000 
byte
‰ MTU = 1500 byte
1480 bytes in 
data field
offset =
1480/8 
1-36
Chương 4: Tầng mạng
‰ 4. 1 Tổng quan
‰ 4.2 Mạng Virtual circuit 
và datagram
‰ 4.3 Bên trong Router
‰ 4.4 IP: Internet Protocol
 Định dạng Datagram
 Địa chỉ IPv4
 ICMP
 IPv6
‰ 4.5 Thuật toán dẫn
đường
 Link state
 Distance Vector
 Hierarchical routing
‰ 4.6 Dẫn đường trong
Internet
 RIP
 OSPF
 BGP
‰ 4.7 Dẫn đường
broadcast và multicast
1-37
Địa chỉ IP
‰ Địa chỉ IP: 32-bit định
danh cho giao diện của
host, router
‰ Giao diện: kết nối giữa
host/router và liên kết
vật lý
 Thông thường, router có
nhiều giao diện
 host có thể có nhiều
giao diện
 Địa chỉ IP gán cho mỗi
giao diện
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
1-38
Subnet
‰ Địa chỉ IP:
 Phần subnet (các bít
phần cao)
 Phần host (các bít phần
thấp)
‰ Khái niệm subnet ?
 Giao diện của thiết bị
mà địa chỉ IP có cùng
phần subnet
 Có thể kết nối với không
không cần thông qua 
router
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
LAN
Mạng chứa 3 subnet
1-39
Subnet 223.1.1.0/24 223.1.2.0/24
223.1.3.0/24
Công thức
‰ Để xác định các subnet, 
tách giao diện của host 
hoặc router, tạo mạng
cô lập. Mỗi mạng cô lập
gọi là một subnet.
Subnet mask: /24
1-40
Subnet
Số subnet ? 223.1.1.1
223.1.1.3
223.1.1.4
223.1.2.2223.1.2.1
223.1.2.6
223.1.3.2223.1.3.1
223.1.3.27
223.1.1.2
223.1.7.0
223.1.7.1
223.1.8.0223.1.8.1
223.1.9.1
223.1.9.2
1-41
Địa chỉ IP: CIDR
CIDR: Classless InterDomain Routing
 Phần địa chỉ subnet có độ dài tùy ý
 Định dạng địa chỉ: a.b.c.d/x, trong đó x là số bít của phần
subnet trong địa chỉ
11001000 00010111 00010000 00000000
Phần
subnet
Phần
host
200.23.16.0/23
1-42
Địa chỉ IP: Cách gán địa chỉ IP?
Q: Cách để host có địa chỉ IP?
‰ Khai báo bởi người quản trị
Windows: Control Panel->Network->Configuration-
>TCP/IP->Properties
 UNIX: /etc/rc.config
‰ DHCP: Dynamic Host Configuration Protocol: lấy địa
chỉ IP động từ server
1-43
Địa chỉ IP: Cách gán địa chỉ IP?
Q: Cách xác định subnet từ địa chỉ IP?
A: Tính dựa vào phần không gian địa chỉ được
cấp
Khối của ISP 11001000 00010111 00010000 00000000 200.23.16.0/20 
Tổ chức 0 11001000 00010111 00010000 00000000 200.23.16.0/23 
Tổ chức 1 11001000 00010111 00010010 00000000 200.23.18.0/23 
Tổ chức 2 11001000 00010111 00010100 00000000 200.23.20.0/23 
... .. . .
Tổ chức 7 11001000 00010111 00011110 00000000 200.23.30.0/23
1-44
Địa chỉ phân cấp: Gửi kết tập
“Gửi cho tôi gói tin có địa chỉ bắt đầu bằng
200.23.16.0/20”
200.23.16.0/23
200.23.18.0/23
200.23.30.0/23
Fly-By-Night-ISP
Tổ chức 0
Tổ chức 7
Internet
Tổ chức 1
ISPs-R-Us “Gửi cho tôi gói tin có địa chỉ bắt đầu bằng199.31.0.0/16”
200.23.20.0/23
Tổ chức 2
...
...
Địa chỉ phân cấp cho phép thông báo hiệu quả thông tin dẫn đường:
1-45
Địa chỉ phân cấp
ISPs-R-Us có hơn một đường đi tới tổ chức 1
“Gửi cho tôi gói tin có địa chỉ bắt đầu bằng
200.23.16.0/20”
200.23.16.0/23
200.23.18.0/23
200.23.30.0/23
Fly-By-Night-ISP
Tổ chức 0
Tổ chức 7
Inte ... tocol
OSPF: Open Shortest Path First
 IGRP: Interior Gateway Routing Protocol (sở hữu
của Cisco)
1-90
Chương 4: Tầng mạng
‰ 4.1 Tổng quan
‰ 4.2 Mạng Virtual circuit 
và datagram
‰ 4.3 Bên trong Router
‰ 4.4 IP: Internet Protocol
 Định dạng Datagram
 Địa chỉ IPv4
 ICMP
 IPv6
‰ 4.5 Thuật toán dẫn
đường
 Link state
 Distance Vector
 Hierarchical routing
‰ 4.6 Dẫn đường trong
Internet
 RIP
 OSPF
 BGP
‰ 4.7 Dẫn đường
broadcast và multicast
1-91
RIP ( Routing Information Protocol)
‰ Thuật toán Distance vector
‰ Trong BSD-UNIX Distribution, 1982
‰ Độ đo khoảng cách: số hop (tối đa = 15 hop)
DC
BA
u v
w
x
y
z
đích hop
u 1
v 2
w 2
x 3
y 3
z 2
1-92
Thông báo của RIP
‰Distance vector: trao đổi giữa các hàng xom
mỗi 30s qua Response Message (còn gọi là
advertisement – thông báo)
‰Mỗi thông báo: danh sách tới 25 mạng đích
trong AS
1-93
RIP: Ví dụ
Mạng đích Router tiếp Số hop để tới đích
w A 2
y B 2
z B 7
x -- 1
. . ....
w x y
A
C
D
z
B
Bảng dẫn đường trong D
1-94
RIP: Ví dụ
Mạng đích Router tiếp Số hop tới đích
w A 2
y B 2
z B A 7 5
x -- 1
. . ....
Bảng dẫn đường trong D
w x y
z
A
C
D B
Đích Tiếp Hop
w - -
x - -
z C 4
.  ...
Thông báo
từ A tới D
1-95
RIP: Lỗi liên kết và khôi phục
Nếu không nghe thấy bản tin thông báo sau 180 giây -> 
hàng xóm/liên kết đã không hoạt động
 Đường qua hàng xóm mất hiệu lực
 Không gửi thông báo đến các hàng xóm đó
 Các hàng xóm gửi thông báo mới (nếu bảng thay
thay đổi)
 Thông tin lỗi liên kết nhanh chóng lan truyền toàn
mạng
 poison reverse sử dụng để ngăn chặn vòng lặp ping-
pong (khoảng cách không giới hạn = 16 hops)
1-96
RIP: Xử lý bảng
‰ Bảng dẫn đường của RIP quản lý bởi tiến trình mới
ứng dụng gọi là route-d (daemon)
‰ Các thông báo được gửi trong các gói tin UDP, lặp
lại định kỳ
physical
link
network bảng
(IP) chuyển tiếp
Transport
(UDP)
routed
physical
link
network
(IP)
Transprt
(UDP)
routed
bảng
chuyển tiếp
1-97
Chương 4: Tầng mạng
‰ 4.1 Tổng quan
‰ 4.2 Mạng Virtual circuit 
và datagram
‰ 4.3 Bên trong Router
‰ 4.4 IP: Internet Protocol
 Định dạng Datagram
 Địa chỉ IPv4
 ICMP
 IPv6
‰ 4.5 Thuật toán dẫn
đường
 Link state
 Distance Vector
 Hierarchical routing
‰ 4.6 Dẫn đường trong
Internet
 RIP
 OSPF
 BGP
‰ 4.7 Dẫn đường
broadcast và multicast
1-98
OSPF (Open Shortest Path First)
‰ “open”: không thương mại
‰ Sử dụng thuật toán Link State 
 Phổ biến gói tin LS
 Bản đồ Topology tại mỗi nút
 Tính toán đường đi sử dụng thuật toán Dijkstra
‰ Các thông báo OSPF mang một điểm vào cho mỗi router 
hàng xóm
‰ Thông báo phổ biến trong toàn AS (bằng cách làm tràn)
 Mang bản tin OSPF trực tiếp qua IP (không phải qua TCP, UDP)
1-99
Các đặc điểm tiến bộ của OSPF 
(không có trong RIP)
‰ An toàn bảo mật: Tất cả các bản tin OSPF được xác
thực (ngăn chặn việc cố tình xâm nhập) 
‰ Cho phép nhiều đường đi cùng chi phí (trong RIP chỉ 1 
đường đi)
‰ Đối với mỗi liên kết, chi phí khác nhau cho TOS khác
nhau (ví dụ: chi phí liên kết vệ tinh thiết lập thấp cho dịch
vụ best effort, cao cho các dịch vụ thời gian thực)
‰ Hỗ trợ cả unicast và multicast: 
Multicast OSPF (MOSPF) sử dụng cùng dữ liệu
topology như OSPF
‰ OSPF phân cấp trong các miền lớn.
1-
100
OSPF phân cấp
1-
101
OSPF phân cấp
‰ Phân cấp 2 mức: vùng cục bộ, backbone
 Thông báo Link-state chỉ trong vùng
Mỗi nút có topology vùng chi tiết; chỉ biết hướng
(đường đi ngắn nhất) tới các mạng trong các vùng
khác
‰ Area border router: tóm tắt các khoảng cách tới các
mạng trong vùng của nó, thông báo cho các Area Border 
router khác
‰ Backbone router: chạy dẫn đường OSPF giới hạn
trong backbone
‰ Boundary router: kết nối tới các AS khác
1-
102
Chương 4: Tầng mạng
‰ 4.1 Tổng quan
‰ 4.2 Mạng Virtual circuit 
và datagram
‰ 4.3 Bên trong Router
‰ 4.4 IP: Internet Protocol
 Định dạng Datagram
 Địa chỉ IPv4
 ICMP
 IPv6
‰ 4.5 Thuật toán dẫn
đường
 Link state
 Distance Vector
 Hierarchical routing
‰ 4.6 Dẫn đường trong
Internet
 RIP
 OSPF
 BGP
‰ 4.7 Dẫn đường
broadcast và multicast
1-
103
Dẫn đường Internet inter-AS: BGP
‰ BGP (Border Gateway Protocol): chuẩn phố
biến (nhưng không chính thức)
‰ BGP cung mỗi mỗi AS cách thức để:
1. Có thông tin tới subnet từ các AS hàng xóm.
2. Lan truyền thông tin tới các subnet tới mọi router 
trong AS
3. Xác định các đường đi tốt tới các subnet dựa trên
thông tin tới các subnet
‰ Cho phép một subnet quảng cáo thông tin về
sự tồn tại của nó tới phần còn lại của
Internet: “I am here”
1-
104
Cơ bản về BGP
‰ Các cặp router (BGP peer) trao đổi thông tin dẫn
đường qua các kết nối TCP bán cố định: Phiên BGP
‰ Chú ý: Các phiên BGP không tương ứng với liên kết
vật lý
‰ Khi AS2 quảng cáo prefix tới AS1, AS2 hy vọng nó sẽ
chuyển tiếp bất kỳ datagram dự định tới prefix
 AS2 có thể kết tập các prefix trong các thông báo của nó
3b
1d
3a
1c
2aAS3
AS1
AS2
1a
2c
2b
1b
3c
Phiên eBGP
Phiên iBGP
1-
105
Phân phối thông tin tới đích
‰ Với phiên eBGP giữa 3a và 1c, AS3 gửi thông tin tới đích prefix 
tới AS1
‰ Sau đó, 1c có thể sử dụng iBGP để phân phối thông tin tới đích
prefix mới tới mọi router trong AS1
‰ Sau đó, 1b có thể quảng báo lại thông tin mới tới AS2 qua phiên
eBGP 1b-tới-2a
‰ Khi router học về prefix mới, nó tạo một điểm vào cho prefix 
trong bảng chuyển tiếp của nó
3b
1d
3a
1c
2aAS3
AS1
AS2
1a
2c
2b
1b
3c
Phiên eBGP
Phiên iBGP
1-
106
Path attribute và BGP route
‰ Khi quảng cáo một prefix, quảng cáo bao gồm các
BGP attribute. 
 prefix + attributes = “route”
‰ Hai attribute quan trọng:
 AS-PATH: chứa các AS qua đó quảng cáo cho prefix 
chuyển qua: AS 67 AS 17 
 NEXT-HOP: chỉ định internal-AS router cụ thể tới next-hop 
AS. (Có thể có nhiều liên kết từ AS hiện tại tới next-hop-AS)
‰ Khi gateway router nhận quảng cáo đường đi, sử
dụng import policy để chấp nhận hoặc từ chối
1-
107
Chọn đường của BGP
‰ Router có thể học về nhiều hơn 1 đường đi
từ một số prefix. Router phải chọn đường đi.
‰ Quy tắc loại trừ:
1. Local preference value attribute: quyết định của
chính sách
2. AS-PATH ngắn nhất
3. NEXT-HOP router gần nhất: hot potato routing
4. Các tiêu chuẩn khác
1-
108
Bản tin BGP
‰ Các bản tin BGP trao đổi sử dụng TCP.
‰ Bản tin BGP:
OPEN: mở kết nối TCP tới peer và xác thực bên gửi
 UPDATE: quảng cáo đường đi mới (hoặc thu hồi
đường đi cũ)
 KEEPALIVE giữ kết nối khi không có UPDATE, tương
tự ACK tới yêu cầu OPEN
 NOTIFICATION: thông báo về các lỗi trong bản tin 
trước, cũng sử dụng để đóng kết nối
1-
109
Chính sách dẫn đường của BGP
Figure 4.5-BGPnew: a simple BGP scenario 
A 
B 
C 
W 
X 
Y 
legend: 
customer 
network: 
provider 
network 
‰ A,B,C là mạng của nhà cung cấp
‰ X,W,Y là khách hàng (của mạng nhà cung cấp)
‰ X là dual-homed: nối tới 2 mạng
 X không muốn dẫn từ B qua X tới C
 .. vì vậy, X sẽ không quảng cáo tới B đường đi tới C
1-
110
Chính sách dẫn đường của BGP (2)
Figure 4.5-BGPnew: a simple BGP scenario 
A 
B 
C 
W 
X 
Y 
legend: 
customer 
network: 
provider 
network 
‰ A quảng cáo tới B đường đi AW
‰ B quảng cáo tới X đường đi BAW 
‰ B quảng cáo tới C đường đi BAW?
 Không! B không nhận được “thu nhập” cho việc dẫn đường
CBAW vì W và C không là khách hàng của B
 B muốn ép C dẫn đường tới w qua A
 B muốn dẫn đường chỉ tới/từ các khách hàng của nó!
1-
111
Tại sao dẫn đường Intra-AS và Inter-AS khác
nhau ?
Chính sách:
‰ Inter-AS: Người quản trị muốn điều khiển việc dẫn
đường lưu lượng của nó, ai dẫn đường qua mạng của
nó
‰ Intra-AS: một người quản trị vì thế không cần policy 
decision
Sự co giãn:
‰ Dẫn đường phân cấp tiết kiệm kích thước bảng, giảm
lưu lượng cập nhật
Hiệu năng:
‰ Intra-AS: có thể tập chung vào hiệu năng
‰ Inter-AS: policy có thể ảnh hưởng lớn tới hiệu năng
1-
112
Chương 4: Tầng mạng
‰ 4.1 Tổng quan
‰ 4.2 Mạng Virtual circuit 
và datagram
‰ 4.3 Bên trong Router
‰ 4.4 IP: Internet Protocol
 Định dạng Datagram
 Địa chỉ IPv4
 ICMP
 IPv6
‰ 4.5 Thuật toán dẫn
đường
 Link state
 Distance Vector
 Hierarchical routing
‰ 4.6 Dẫn đường trong
Internet
 RIP
 OSPF
 BGP
‰ 4.7 Dẫn đường
broadcast và multicast
1-
113
R1
Source-duplication và in-network duplication. 
(a) source duplication, (b) in-network duplication
R2
R3 R4
(a)
R1
R2
R3 R4
(b)
duplicate
creation/transmissionlặp
lặp
1-
114
A
Reverse path forwarding
B
G
D
E
c
F
1-
115
Broadcast dọc theo spanning tree 
A
B
G
D
E
c
F
A
B
G
D
E
c
F
(a) Broadcast khởi tạo tại A (b) Broadcast khởi tạo tại D
1-
116
Xây dựng kiểu Center-based của một spanning tree 
A
B
G
D
E
c
F
1
2
3
4
5
(a) Bước xây dựng
A
B
G
D
E
c
F
(b) Spanning tree đã xây
dựng
Dẫn đường Multicast: Bài toán
‰Mục đích: Tìm một tree (hoặc các tree) kết nối
các router có local mcast group members 
 tree: Không phải mọi đường giữa các router được sử dụng
 source-based: Cây khác nhau từ mỗi bên gửi tới bên nhận
 shared-tree: Cây giống nhau sử dụng bởi tất cả các group 
member
Shared tree Source-based tree
Các cách tiếp cận để xây dựng mcast 
tree
Cách tiếp cận:
‰ source-based tree: một cây cho mỗi nguồn
 Cây đường đi ngắn nhất
 Reverse path forwarding
‰ group-shared tree: Group sử dụng một cây
minimal spanning (Steiner) 
 center-based tree
Chúng ta xem xét các cách tiếp cận một cách cơ bản, 
sau đó xem xét các giao thức sử dụng các cách tiếp cận
đó
Cây đường đi ngắn nhất
‰mcast forwarding tree: cây đường đi ngắn
nhất dẫn đường từ nguồn tới mọi đích
 Thuật toán Dijkstra
R1
R2
R3
R4
R5
R7
2
R6
1
6
3 4
5
i
router nối với group member
router không nối với
group member
Liên kết sử dụng để chuyển tiếp,
i chỉ thứ tự liên kết được thêm
bởi thuật toán
Ghi chú:S: nguồn
Reverse Path Forwarding
if (mcast datagram nhận trên liên kết đến trên
đường ngắn nhất trở lại trung tâm)
then làm tràn datagram trên mọi liên kết đi
else bỏ qua datagram
‰Dựa vào kiến thức của router về đường đi
ngắn nhất unicast từ nó tới bên gửi
‰Mỗi router có hành vi chuyển tiếp đơn giản:
Reverse Path Forwarding: Ví dụ
• Kết quả là một source-specific reverse SPT
– có thể là sự lựa chọn tồi với các liên kết không đối
xứng
R1
R2
R3
R4
R5
R6 R7
router nối với group member
router không nối với
group member
datagram sẽ được
chuyển tiếp
Chú thíchS: nguồn
datagram sẽ không được
chuyển tiếp
Reverse Path Forwarding: Tỉa
‰ forwarding tree chứa các cây con mà subtree con đó
không có mcast group member
 Không cần chuyển tiếp các datagram xuống subtree
 “Tỉa” các bản tin gửi lên bởi router mà không có
downstream group members
R1
R2
R3
R4
R5
R6 R7
router nối với
group member
router không nối với
group member
Tỉa bản tin
Chú ýS: nguồn
Liên kết với multicast
forwarding
P
P
P
Shared-Tree: Steiner Tree
‰ Steiner Tree: minimum cost tree kết nối tất cả
các router nối với group member
‰ Bài toán là NP-complete
‰ Tồn tại các kỹ thuật heuristic
‰ Không sử dụng trong thực tế:
 Độ phức tạp tính toán
 Cần thông tin về toàn bộ mạng
 Chạy lại khi một router gia nhập hay rời khỏi
Center-based tree
‰ Tất cả dùng chung một cây
‰Một router được xác định là “trung tâm” của
cây
‰Gia nhập:
 edge router gửi unicast join-msg tới center router
 join-msg được xử lý bởi intermediate routers và
chuyển tiếp tới center
 join-msg hoặc tới nhánh của cây có trung tâm này, 
hoặc đến trung tâm
 Đường đi mà join-msg tham gia trở thành một
nhánh mới của cây cho router này
Center-based tree: ví dụ
Giả sử R6 được chọn làm trung tâm:
R1
R2
R3
R4
R5
R6 R7
router nối với
group member
router không nối với
group member
Thứ tự đường đi trong đó
các join msg sinh ra
Chú thích
2
1
3
1
Internet Multicasting Routing: DVMRP
‰DVMRP: Giao thức dẫn đường multicast kiểu
distance vector, RFC1075
‰ Làm tràn và tỉa: reverse path forwarding, 
source-based tree
 RPF tree dựa trên chính bảng dẫn đường của nó
DVMRP được xây dựng bởi sự giao tiếp của các
DVMRP router 
 Không giả sử về unicast ở dưới
 Datagram ban đầu tới mcast group được làm tràn
mọi nơi qua RPF
 Router không muốn trong group: gửi upstream 
prune msgs
DVMRP (tiếp)
‰ Trạng thái mềm: DVMRP router định kỳ (1 phút) 
“quên” branches bị tỉa:
mcast data đưa lại xuông các nhánh không được tỉa
 downstream router: tỉa lại hoặc tiếp tục nhận dữ liệu
‰ router có thể nhanh chónh ghép lại vào cây
 Theo IGMP gia nhập tại lá
‰ odds và ends
 Thường cài đặt trong các router thương mại
 Dẫn đường Mbone sử dụng DVMRP
Tunneling
Q: Làm thế nào để kết nối tới các “đảo” của các
multicast router trong “biển” các unicast router? 
‰ mcast datagram được đóng gói trong datagram “thông thường”
(không đánh địa chỉ multicast)
‰ IP datagram thông thường gửi qua “tunnel” qua IP unicast router 
bình thường tới mcast router nhận
‰ mcast router nhận sẽ bỏ đóng gói để nhận mcast datagram
topology vật lý topology lôgíc
PIM: Protocol Independent Multicast
‰ Không phụ thuộc vào bất kỳ thuật toán dẫn đường
unicast cụ thể nào phía dưới (làm việc với tất cả)
‰ Hai kịch bản phân phối multicast khác nhau:
Đông đúc:
‰ group member tồn tại
dày đặc, tồn tại gần
nhau.
‰ Bandwidth lớn
Thưa thớt:
‰ Số mạng với group member 
nhỏ
‰ group member phân tán rộng
‰ bandwidth không lớn
So sánh kiểu đông đúc và thưa thớt
Đông đúc:
‰ Thành viên nhóm tới khi
router chính thức tỉa
‰ Xây dựng data-driven
dựa trên mcast tree (ví
dụ: RPF)
‰ bandwidth và non-group-
router xử lý thoải mái
Thưa thớt:
‰ Không là thành viên tới khi
router chính thức gia nhập
‰ Xây dựng receiver- driven
của mcast tree (ví dụ: 
center-based)
‰ bandwidth và non-group-
router xử lý dè dặt
PIM- Chế độ đông đúc
flood-and-prune RPF, tương tự DVMRP 
nhưng
‰ Giao thức unicast phía dưới cung cấp thông tin 
RPF cho datagram tới
‰ Downstream flood ít phức tạp hơn (kém hiệu quả
hơn) DVMRP giảm sự tin cậy vào thuật toán dẫn
đường phía dưới
‰ Có cơ chế giao thức cho router phát hiện nó là
router nút lá
PIM – Chế độ thưa thớt
‰ Cách tiếp cận center-
based
‰ Router gửi join msg tới
điểm hẹn (RP)
 Các intermediate router 
cập nhật trạng thái và
chuyển tiếp join
‰ Sau khi gia nhập qua 
RP, router có thể
chuyển tới source-
specific tree
 Tăng hiệu năng: giảm tập
chung, đường đi ngắn
hơn
R1
R2
R3
R4
R5
R6
R7
gia nhập
gia nhập
gia nhập
Mọi dữ liệu multicast
từ điểm hiẹn
Điểm hẹn
PIM – Chế độ thưa thớt
Bên gửi (s):
‰ Dữ liệu unicast tới RP, 
nó phân phối xuống
RP-rooted tree
‰ RP có thể mở rộng
mcast tree upstream tới
nguồn
‰ RP có thể gửi stop msg 
nếu không có người
nhận nối vào
 “không ai đang nghe!”
R1
R2
R3
R4
R5
R6
R7
gia nhập
gia nhập
gia nhập
Tất cả dữ liệu
multicast
từ điểm hẹn
điểm hẹn
1-
134
Tầng mạng: Tổng kết
Tiếp:
Tầng liên kết dữ liệu!
Các vấn đề đã xem xét:
‰ Các dịch vụ của tầng mạng
‰ Nguyên tắc dẫn đường: link state 
và distance vector
‰ Dẫn đường phân cấp
‰ IP
‰ Các giao thức dẫn đường trong
Internet: RIP, OSPF, BGP
‰ Bên trong router?
‰ IPv6