Bài giảng Mạng máy tính - Chương 4: Lớp Networ

i phí đến
x
y
z
x y z
x
y
zt
ừ
chi phí đến
0 2 3
x y z
x
y
z
0 2 3
t
ừ
chi phí đến
x y z
z
0 2 7
t
ừ
chi phí đến
x
y
x y z
∞∞ ∞
7 1 0
chi phí đến
∞
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
x
y
z
thời gian
x z
12
7
y
bảng nút x
bảng nút y
bảng 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
Lớp Network 76
Vector khoảng cách: các thay đổi chi phí
kết nối
các thay đổi chi phí kết nối:
ˆ nút kiểm tra thay đổi chi phí kết nối 
ˆ cập nhật thông tin dẫn đường, tính 
toán lại vector khoảng cách
ˆ nếu DV thay đổi, thông báo các lân 
cận
“duyệt
tin tức
tốt 
nhanh”
x z
14
50
y
1
Tại thời điểm t0, y kiểm tra thay đổi chi phí kết nối, cập nhật DV 
và thông báo đến các lân cận của nó
Tại thời điểm t1, z nhận được cập nhật từ y và cập nhật bảng của nó.
Nó tính toán chi phí thấp nhất mới đến x và gửi DV của nó đến các 
lân cận
Tại thời điểm t2, y nhận được cập nhật của z và cập nhật bảng khoảng
cách của nó. Các chi phí thấp nhất của y không thay đổi và hơn nữa
y không gửi bất kỳ thông báo nào đến z.
Lớp Network 77
Vector khoảng cách: các thay đổi chi phí
kết nối
các thay đổi chi phí kết nối:
ˆ duyệt tin tức tốt nhanh
ˆ duyệt tin tức xấu chậm - vấn đề
“đếm đến vô tận”!
ˆ 44 lần duyệt trước khi ổn định
Poisoned reverse:
ˆ Nếu Z dẫn đường từ Y thẳng tới 
X:
 Z nói với Y khoảng cách của nó 
đến X là ∞ (vì thế Y sẽ không 
dẫn đường đến X đi qua Z)
ˆ sẽ giải quyết triệt để vấn đề 
đếm vô tận?
x z
14
50
y
60
Lớp Network 78
So sánh các giải thuật LS và DV
thông báo phức tạp
ˆ LS: với n nút, E kết nối, O(nE) 
các thông báo được gửi 
ˆ DV: chỉ trao đổi giữa các lân 
cận
Tốc độ hội tụ
ˆ LS: giải thuật O(n2) yêu cầu 
O(nE) thông báo
 có thể có các dao động
ˆ DV: thời gian hội tụ thay đổi
 có thể do các quá trình lặp 
tìm đường
 vấn đề đếm vô hạn
sự linh hoạt: điều gì xảy ra nếu 
router hoạt động sai chức 
năng?
LS:
 nút có thể thông báo chi phí
kết nối không chính xác
 mỗi nút chỉ tính toán bảng 
riêng của nó
DV:
 nút có thể thông báo chi phí
đường đi không chính xác
 bảng của nút có thể được nút 
khác dùng
• lỗi lan truyền thông qua mạng
Lớp Network 79
Hierarchical Routing
quy mô: với 200 triệu 
đích
ˆ không thể ghi nhớ tất cả 
đích trong bảng routing!
ˆ bảng routing sẽ kiểm soát 
các kết nối!
quản trị
ˆ internet = mạng của các 
mạng
ˆ mỗi quản trị mạng muốn 
điều hành routing trong 
mạng của họ
nghiên cứu trong môi trường lý tưởng hóa 
ˆ tất cả các router đồng nhất
ˆ mạng “phẳng”
 không đúng trong thực tế
Lớp Network 80
Hierarchical Routing
ˆ các router gom thành các 
vùng, “các hệ thống tự trị-
autonomous systems” (AS)
ˆ các router trong cùng AS 
chạy giao thức routing giống 
nhau
 giao thức “intra-AS”
routing
 các router trong AS khác 
nhau có thể chạy giao thức 
intra-AS routing 
Gateway router
ˆ trực tiếp kết nối đến 
router trong AS khác
Lớp Network 81
3b
1d
3a
1c
2aAS3
AS1
AS2
1a
2c
2b
1b
g.thuật
Intra-AS
Routing 
g.thuật
Inter-AS
Routing 
bảng
Forwarding
3c
Kết nối các AS
ˆ bảng Forwarding được cấu 
hình bởi cả giải thuật intra-
và inter-AS routing 
 Intra-AS thiết lập các 
điểm đăng nhập vào các 
đích nội mạng
 Inter-AS & Intra-As thiết 
lập các điểm đăng nhập vào 
các đích ngoại mạng
Lớp Network 82
3b
1d
3a
1c
2aAS3
AS1
AS2
1a
2c
2b
1b
3c
các tác vụ Inter-AS
ˆ giả sử router AS1 nhận 
datagram với đích nằm 
ngoài nó
 Router sẽ forward về
một trong những 
gateway router kế tiếp, 
nhưng là cái nào?
AS1 cần:
1. học các đích nào có
thể chạm đến thông 
qua AS2 và AS3
2. lan truyền thông tin 
này đến tất cả các 
router trong AS1
công việc của inter-AS 
routing!
Lớp Network 83
Ví dụ: thiết lập bảng forwarding trong router 1d
ˆ Giả sử AS1 học (thông qua giao thức inter-AS) mà
subnet x có thể chạm đến qua AS3 (gateway 1c) nhưng 
không qua AS2.
ˆ Giao thức Inter-AS lan truyền thông tin này đến tất cả
các router nội mạng.
ˆ Router 1d xác định từ thông tin intra-AS routing và I
sẽ nằm trên đường đi chi phí thấp nhất đến 1c.
ˆ Đưa giá trị (x,I) vào bảng forwarding
3b
1d
3a
1c
2aAS3
AS1
AS2
1a
2c
2b
1b
3c
Lớp Network 84
Ví dụ: Chọn giữa nhiều AS
ˆ Bây giờ giả sử AS1 học từ giao thức inter-AS là
subnet x có thể chạm đến từ AS3 và từ AS2
ˆ Để cấu hình bảng forwarding, router 1d phải xác định 
gateway nào được dùng để chuyển các gói đến đích x. 
ˆ đấy cũng chính là công việc trên giao thức inter-AS 
routing!
3b
1d
3a
1c
2aAS3
AS1
AS2
1a
2c
2b
1b
3c
Lớp Network 85
học từ giao thức 
inter-AS là subnet x 
có thể chạm đến thông 
qua nhiều gateways
dùng thông tin từ
giao thức intra-AS 
để xác định các chi 
phí của các đường 
đi có chi phí thấp 
nhất đến mỗi 
gateway 
Hot potato routing:
chọn gateway
nào có chi phí thấp 
nhất
xác định từ bảng 
forwarding là I có thể
dẫn đến gateway chi 
phí thấp nhất. đưa 
giá trị (x,I) vào bảng
Ví dụ: Chọn giữa nhiều AS
ˆHot potato routing: gởi các gói đến 2 router 
gần nhất
4.6 Routing trong Internet
Lớp Network 86
Lớp Network 87
Intra-AS Routing
ˆ cũng gọi là Interior Gateway Protocols (IGP)
ˆ các giao thức Intra-AS routing phổ biến:
 RIP: Routing Information Protocol
OSPF: Open Shortest Path First
 IGRP: Interior Gateway Routing Protocol (Cisco 
độc quyền)
Lớp Network 88
RIP ( Routing Information Protocol)
ˆ giải thuật vector khoảng cách
ˆ công bố năm 1982 trong BSD-UNIX Distribution 
ˆ không gian khoảng cách: số lượng hop (tối đa 15 hop)
DC
BA
u v
w
x
y
z
đích số hop
u 1
v 2
w 2
x 3
y 3
z 2
từ router A đến các subset:
Lớp Network 89
các thông báo của RIP
ˆ Các vector khoảng cách: trao đổi giữa các 
lân cận mỗi 30s thông qua Response 
Message (cũng được gọi là thông báo).
ˆMỗi thông báo: danh sách lên đến 25 mạng 
đích trong mỗi AS
Lớp Network 90
RIP: ví dụ
Network đích Router kế tiếp Số hop đến đích
w A 2
y B 2
z B 7
x -- 1
. . ....
w x y
A
C
D
z
B
bảng Routing trong D
Lớp Network 91
RIP: ví dụ
Network đích Router kế tiếp Số hop đến đích
w A 2
y B 2
z B A 7 5
x -- 1
. . ....
bảng Routing trong D
w x y
z
A
C
D B
 Đích Kế tiếpSố hop
w - 1
x - 1
z C 4
.  ...
thông báo
từ A đến D
Lớp Network 92
RIP: kết nối sai & phục hồi
Nếu không có thông báo nào sau 180s Æ lân cận/kết nối 
được xem như đã “chết”
 những đường đi qua lân cận không còn dùng được
 gửi thông báo mới cho các lân cận
 các lân cận tiếp tục gửi ra những thông báo mới đó
(nếu các bảng thay đổi)
 thông tin kết nối lỗi nhanh chóng (?) lan truyền trên 
toàn mạng
 poison reverse dùng để ngăn chặn các vòng lặp ping-
pong (khoảng cách vô hạn = 16 hop)
Lớp Network 93
RIP: xử lý bảng
ˆ các bảng RIP routing được quản lý bởi các tiến trình 
mức application gọi là route-d (daemon) 
ˆ các thông báo gửi trong các gói UDP, lặp lại theo 
chu kỳ
physical
link
network bảng
(IP) forwarding
Transprt
(UDP)
routed
physical
link
network
(IP)
Transprt
(UDP)
routed
bảng
forwarding
Lớp Network 94
OSPF (Open Shortest Path First)
ˆ “open”: sẵn sàng công khai
ˆ dùng giải thuật Link State
 phân phối gói LS
 bản đồ cấu trúc mạng tại mỗi nút
 tính toán đường đi dùng giải thuật Dijkstra
ˆ thông báo OSPF mang 1 entry vào mỗi router lân cận
ˆ các thông báo phân tán đến toàn bộ AS (thông qua cơ 
chế flooding)
 thông điệp OSPF trực tiếp trên IP (chứ không phải là TCP hoặc 
UDP)
Lớp Network 95
các đặc tính OSPF “cao cấp” (không có
trong RIP)
ˆ bảo mật: chứng thực tất cả các thông điệp OSPF (ngăn 
những kẻ có ý đồ xấu)
ˆ cho phép nhiều đường đi có chi phí giống nhau (RIP chỉ
cho 1)
ˆ với mỗi kết nối, có nhiều không gian chi phí cho TOS 
khác nhau (vd: chi phí kết nối vệ tinh được thiết lập 
“thấp” để đạt hiệu quả tốt, “cao” cho thời gian thực)
ˆ hỗ trợ uni- và multicast tích hợp: 
Multicast OSPF (MOSPF) dùng cùng cơ sở dữ liệu 
cấu trúc như OSPF 
ˆ OSPF phân cấp trong những miền lớn.
Lớp Network 96
OSPF phân cấp 
Lớp Network 97
OSPF phân cấp
ˆ phân cấp mức 2: vùng địa phương, backbone.
 các thông báo Link-state chỉ bên trong vùng 
mỗi nút có cấu trúc vùng chi tiết; chỉ biết hướng 
(đường đi ngắn nhất) đến các mạng trong các vùng 
khác
ˆ các router ngoài biên vùng: “tổng hợp” khoảng cách 
đến các mạng trong vùng của nó, thông báo đến các 
router ngoài biên vùng
ˆ các Backbone routers: chạy OSPF routing hạn chế 
đến backbone.
ˆ các router ngoài biên: kết nối đến các AS khác.
Lớp Network 98
Internet inter-AS routing: BGP
ˆ BGP (Border Gateway Protocol): chuẩn thực tế
ˆ BGP hỗ trợ cho mỗi AS:
1. Lấy thông tin khả năng chạm subnet đích từ các AS lân 
cận.
2. lan truyền thông tin đó đến tất cả các router bên trong 
AS.
3. Xác định đường đi “tốt” đến các subnet dựa trên thông tin 
khả năng chạm subnet đích và chính sách.
ˆ cho phép subnet thông báo sự tồn tại của nó trên 
Internet
Lớp Network 99
các cơ sở BGP
ˆ Các cặp router (BGP peers) trao đổi thông tin 
routing trên các kết nối TCP bán bền vững: BGP 
sessions
 các phiên BGP không cần các kết nối vật lý tương xứng
ˆ Khi AS2 thông báo 1 prefix đến AS1, AS2: 
 AS2 có thể tích hợp các prefix trong thông báo của nó
3b
1d
3a
1c
2aAS3
AS1
AS2
1a
2c
2b
1b
3c
eBGP session
iBGP session
Lớp Network 100
Phân phối thông tin khả chạm đích
ˆ Với phiên eBGP giữa 3a và 1c, AS3 gửi thông tin khả chạm cho 
AS1.
ˆ 1c sau đó có thể dùng iBGP phân phối thông tin khả chạm đến 
tất cả router trong AS1.
ˆ 1b sau đó có thể thông báo lại thông tin khả chạm đến AS2 
trên phiên eBGP từ 1b-đến-2a
ˆ Khi router học xong prefix mới, tạo entry cho prefix trong 
bảng forwarding của nó.
3b
1d
3a
1c
2aAS3
AS1
AS2
1a
2c
2b
1b
3c
eBGP session
iBGP session
Lớp Network 101
các thuộc tính đường đi & BGP 
ˆ khi thông báo 1 prefix, trong đó có chứa các 
thuộc tính BGP
 prefix + các thuộc tính = “dẫn đường”
ˆ 2 thuộc tính quan trọng:
 AS-PATH: chứa các AS qua đó thông báo prefix 
truyền đi: AS 67 AS 17 
NEXT-HOP: Chỉ định router bên trong AS là hop kế
tiếp (có nhiều kết nối từ AS hiện tại đến AS hop kế
tiếp)
ˆ Khi gateway router nhận thông báo tìm đường, 
nó dùng import policy để chấp nhận/từ chối.
Lớp Network 102
chọn BGP route
ˆ Router có thể học nhiều hơn một nhưng chỉ 
được chọn một. 
ˆ Các quy tắc hạn chế:
1. Thuộc tính giá trị ưu tiên cục bộ: quyết định 
chính sách
2. AS-PATH ngắn nhất
3. NEXT-HOP router gần nhất: hot potato routing
4. Tiêu chuẩn bổ sung 
Lớp Network 103
các thông điệp BGP
ˆ trao đổi các thông điệp BGP dùng TCP
ˆ các thông điệp BGP:
OPEN: mở kết nối TCP đến peer và chứng thực người 
gửi 
 UPDATE: thông báo đường đi mới 
 KEEPALIVE giữ kết nối sống (alive), cũng gọi là yêu 
cầu OPEN các ACK 
NOTIFICATION: thông báo các lỗi trong thông 
điệp trước đó, dùng để đóng kết nối
Lớp Network 104
chính sách BGP routing
Figure 4.5-BGPnew: a simple BGP scenario 
A 
B 
C 
W 
X 
Y 
legend: 
customer 
network: 
provider 
network 
ˆ A,B,C là những nhà cung cấp mạng
ˆ X,W,Y là khách hàng (của những nhà cung cấp mạng)
ˆ X là dual-homed: gắn vào 2 mạng
 X không muốn dẫn đường từ B qua X đến C
 .. vì thế X sẽ không thông báo với B về đường đến C
Lớp Network 105
chính sách BGP routing (2)
Figure 4.5-BGPnew: a simple BGP scenario 
A 
B 
C 
W 
X 
Y 
legend: 
customer 
network: 
provider 
network 
ˆ A thông báo với B về đường AW 
ˆ B thông báo với X về đường BAW 
ˆ B sẽ thông báo với C về đường BAW?
 Không có cách nào! B không có "lợi ích" về đường CBAW cũng như W 
không phải là những khách hàng của B, C
 B muốn buộc C phải tìm đường đến W thông qua AB
 B chỉ muốn tìm đường đến/từ khách hàng của nó!
Lớp Network 106
Tại sao phải routing Intra- và Inter-AS khác 
nhau?
chính sách: 
ˆ Inter-AS: người quản trị muốn điều hành hoạt động lưu 
thông routing, ai routing thông qua mạng của họ
ˆ Intra-AS: 1 người quản trị, vì thế không cần các quyết 
định chính sách 
linh hoạt:
ˆ routing phân cấp tiết giảm kích thước bảng, giảm lưu 
lượng cập nhật
hiệu suất:
ˆ Intra-AS: có thể tập trung vào hiệu suất
ˆ Inter-AS: chính sách quan trọng hơn hiệu suất
4.7 Broadcast và multicast 
routing
Lớp Network 107
Lớp Network 108
R1
R2
R3 R4
nguồn 
trùng lặp 
R1
R2
R3 R4
trùng lặp 
trong mạng
tạo/truyền dẫn
trùng lặp trùng lặp
trùng lặp
Broadcast Routing
ˆ Chuyển các gói từ nguồn đến tất cả các nút khác
ˆNguồn trùng lặp thì không có hiệu quả
ˆNguồn trùng lặp: làm sao xác định địa chỉ 
người nhận?
Lớp Network 109
Trùng lặp trong mạng
ˆ Ngập lụt: khi nút nhận gói broadcast và gửi đến tất 
cả các lân cận
 các vấn đề: bão broadcast & lặp lại
ˆ Ngập lụt có điều khiển: nút chỉ gửi broadcast nếu nó
không gửi gói nào giống như vậy trước đó
 nút phải theo dõi các gói đã broadcast 
 hoặc reverse path forwarding (RPF): chỉ forward gói nếu 
nó đến trên đường ngắn nhất giữa nút và nguồn
ˆ Cây mở rộng
 tại bất kỳ nút nào cũng đều không nhận thừa các gói
Lớp Network 110
A
B
G
D
E
c
F
A
B
G
D
E
c
F
(a) Broadcast khởi đầu tại A (b) Broadcast khởi đầu tại D
Cây mở rộng
ˆĐầu tiên xây dựng Cây mở rộng 
ˆ Các nút forward các bản sao chỉ trên Cây 
mở rộng
Lớp Network 111
A
B
G
D
E
c
F
1
2
3
4
5
(a) các bước xây dựng 
một cây mở rộng
A
B
G
D
E
c
F
(b) cây mở rộng đã xây 
dựng xong
Cây mở rộng: tạo
ˆ Nút trung tâm
ˆ Mỗi nút gửi thông điệp gia nhập unicast đến nút 
trung tâm
 Thông điệp forward cho đến khi gặp một nút đã nằm trên 
cây mở rộng
Multicast Routing: phát biểu vấn đề
ˆMục tiêu: tìm một cây (trong các cây) kết nối 
các router có các thành viên nhóm Multicast 
 cây: không phải tất cả các đường đi giữa các router được dùng
 cây dựa trên nguồn: cây khác nhau từ nơi gửi đến nơi nhận
 cây chia sẻ: cây giống nhau dùng bởi tất cả các thành viên 
nhóm
cây chia sẻ cây dựa trên nguồn
Các cách tiếp cận xây dựng các cây 
multicast 
ˆ cây dựa trên nguồn: một cây mỗi nguồn
 các cây đường đi ngắn nhất
 cây đường đi ngược
ˆ cây chia sẻ nhóm: nhóm dùng 1 cây
mở rộng tối thiểu (Steiner) 
 các cây trung tâm
nghiên cứu các cách tiếp cận cơ bản
Cây đường đi ngắn nhất
ˆ cây đường đi ngược multicast: cây đường đi ngắn 
nhất dẫn đường từ nguồn đến tất cả các điểm nhận
 giải thuật Dijkstra
R1
R2
R3
R4
R5
R7
2
R6
1
6
3 4
5
i
router với các thành viên của 
nhóm đã gắn vào
kết nối dùng cho forward, 
i chỉ thứ tự kết nối thêm 
vào bởi giải thuật
Ký hiệuS: nguồn
router không có các thành 
viên của nhóm gắn vào
Cây đường đi ngược forward:
if (multicast datagram nhận được trên kết nối đến trên 
đường đi ngắn nhất kể từ trung tâm)
then tràn ngập datagram lên tất cả các kết nối ra
else lờ đi datagram
‰ phụ thuộc tri thức của router của đường đi 
ngắn nhất unicast từ nó đến nơi gửi
‰mỗi router có cách xử lý forwarding đơn giản
Cây đường đi ngược forward: ví dụ
• kết quả là một cây SPT đảo ngược
– có thể là một lựa chọn tồi với các kết nối không 
đồng bộ
R1
R2
R3
R4
R5
R6 R7
router với các thành viên 
của nhóm đã gắn vào
router không có các thành 
viên của nhóm gắn vào
datagram sẽ được 
forward
Ký hiệuS: nguồn
datagram sẽ không được 
forward
Cây đường đi ngược forward: cắt 
giảm
ˆ cây forward chứa các cây con với các thành viên 
nhóm không multicast 
 không cần forward các datagram xuống cây con
 “cắt giảm” các thông điệp gửi lên bởi router 
R1
R2
R3
R4
R5
R6 R7
thông điệp cắt giảm
Ký hiệuS: nguồn
các kết nối với multicast
forward
P
P
P
router với các thành viên 
của nhóm đã gắn vào
router không có các thành 
viên của nhóm gắn vào
Cây chia sẻ: cây Steiner
ˆ cây Steiner: cây chi phí thấp nhất kết nối 
tất cả các router với các thành viên nhóm 
đã gắn vào
ˆ vấn đề là NP-complete
ˆ đã có các heuristic rất tốt
ˆ không 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
monolithic: chạy lại bất cứ khi nào 1 router cần 
gia nhập/rời khỏi
Các cây trung tâm
ˆmột cây truyền nhận chia sẻ cho tất cả
ˆ 1 router được gọi là “trung tâm” của cây
ˆ để gia nhập:
 bên ngoài gửi thông điệp gia nhập unicast cho 
router trung tâm
 thông điệp gia nhập “được xử lý” bởi các router 
trung gian và chuyển đến router trung tâm
 thông điệp gia nhập gặp nhánh của cây đã tồn tại 
hoặc đến được trung tâm
 đường đi thu được khi thông điệp gia nhập đến 
trở thành nhánh mới của cây cho router này
Các cây trung tâm: ví dụ
giả sử R6 được chọn làm trung tâm:
R1
R2
R3
R4
R5
R6 R7
thứ tự đường đi trong ấy 
các thông điệp gia nhập đã 
sinh ra
Ký hiệu
2
1
3
1
router với các thành viên 
của nhóm đã gắn vào
router không có các thành 
viên của nhóm gắn vào
Internet Multicasting Routing: DVMRP
ˆDVMRP: giao thức multicast routing dùng 
vector khoảng cách, RFC1075
ˆ flood & prune: forward đường đi ngược, cây 
dựa trên nguồn
 cây RPF dựa trên các bảng routing của DVMRP 
của riêng nó được xây dựng bởi truyền thông các 
router DVMRP 
 không có các giả thiết về unicast bên dưới
 datagram ban đầu đến nhóm multicast làm tràn 
ngập mọi nơi thông qua RPF 
 các router không phải nhóm: gửi các thông điệp 
cắt giảm 
DVMRP: (tt)
ˆ trạng thái “mềm”: router DVMRP chu kỳ (1 
phút) “quên” các nhánh đã cắt giảm: 
 dữ liệu mcast một lần nữa đổ xuống các nhánh không 
cắt giảm
 router dòng xuống: tái cắt giảm hoặc tiếp tục nhận 
dữ liệu
ˆ các router có thể nhanh chóng tái cắt giảm 
 gia nhập IGMP tại các nút lá
ˆ còn lại
 đã hiện thực phổ biến trong các router thương mại
 hoàn thành routing dùng DVMRP
Tunneling
Hỏi: Làm sao kết nối các “đảo” multicast 
router trong một “biển” các unicast router? 
‰ multicast datagram được đóng gói trong datagram “thông 
thường” (không có multicast)
‰ datagram IP thông thường gửi thông qua “đường ống” và qua IP 
unicast đến router multicast nhận
‰ router multicast nhận mở gói để lấy multicast datagram 
cấu trúc vật lý cấu trúc logic
PIM: Protocol Independent Multicast
ˆ không phụ thuộc vào bất kỳ giải thuật unicast 
routing bên dưới nào 
ˆ hai kịch bản phân phối multicast khác nhau
Trù mật:
‰ các thành viên nhóm 
đóng gói trù mật
‰ băng thông dư thừa
Thưa thớt:
‰ số lượng các mạng với các 
thành viên nhóm ít
‰ các thành viên nhóm “phân 
bố thưa thớt”
‰ băng thông không dư thừa
Hậu quả sự phân chia thưa thớt-trù mật
Trù mật:
ˆ nhóm các thành viên 
router là giả cho đến khi 
các router cắt giảm thực 
sự
ˆ kiến trúc hướng dữ liệu 
trên cây multicast (vd: 
RPF)
ˆ băng thông và router 
không thuộc nhóm xử lý 
phung phí
Thưa thớt:
ˆ không có thành viên cho 
đến khi có các router gia 
nhập thực sự
ˆ kiến trúc hướng người 
nhận trên cây multicast 
(vd: cây trung tâm)
ˆ băng thông và router 
không thuộc nhóm xử lý 
vừa phải
PIM- kiểu trù mật
flood-and-prune RPF, tương tự DVMRP, 
nhưng:
‰ giao thức unicast bên dưới cung cấp thông tin 
RPF cho datagram đến
‰ ít phức tạp (ít hiệu quả) 
‰ có cơ chế giao thức cho router để kiểm tra có
phải router là nút lá
PIM – kiểu thưa thớt
ˆ tiếp cận hướng trung 
tâm
ˆ router gửi thông điệp 
gia nhập đến 
rendezvous point (RP) 
 các router trung gian 
cập nhật trạng thái và 
forward thông điệp gia 
nhập
ˆ sau khi gia nhập bằng 
RP, router có thể
chuyển sang cây xác 
định nguồn
 hiệu suất tăng: ít tập 
trung, các đường đi ngắn
R1
R2
R3
R4
R5
R6
R7
join
join
join
tất cả dữ liệu 
multicast
đến từ RP
RP
PIM – kiểu thưa thớt
bên gửi:
ˆ dữ liệu unicast đến RP, 
RP phân phối xuống cây 
có nút gốc là RP
ˆ RP có thể mở rộng cây 
multicast dòng lên đến 
nguồn
ˆ RP có thể gửi thông 
điệp dừng nếu không có
bên nhận nào được gắn 
vào
 “không có ai đang lắng 
nghe!”
R1
R2
R3
R4
R5
R6
R7
join
join
join
tất cả dữ liệu 
multicast
đến từ RP
RP