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

Chương 4
tầng Network
Computer 
Networking: A Top 
Down Approach 
6th edition 
Jim Kurose, Keith Ross
Addison-Wesley
March 2012
A note on the use of these ppt slides:
We’re making these slides freely available to all (faculty, students, readers). 
They’re in PowerPoint form so you see the animations; and can add, modify, 
and delete slides (including this one) and slide content to suit your needs. 
They obviously represent a lot of work on our part. In return for use, we only 
ask the following:
 If you use these slides (e.g., in a class) that you mention their source 
(after all, we’d like people to use our book!)
 If you post any slides on a www site, that you note that they are adapted 
from (or perhaps identical to) our slides, and note our copyright of this 
material.
Thanks and enjoy! JFK/KWR
All material copyright 1996-2012
J.F Kurose and K.W. Ross, All Rights Reserved
Tầng Network 4-1
Tầng Network 4-2
Chương 4: tầng network
Mục tiêu:
 Hiểu các nguyên lý nền tảng của các dịnh vụ
tầng network:
 Các mô hình dịch vụ tầng network
 forwarding so với routing
 Cách mà router hoạt động
 routing (chọn đường)
 broadcast, multicast
 Hiện thực trong Internet
Tầng Network 4-3
4.1 Giới thiệu
4.2 virtual circuit 
network (Mạng mạch 
ảo) và datagram 
network
4.3 Cấu trúc bên trong 
router
4.4 IP: Internet Protocol
 Định dạng datagram
 IPv4 addressing
 ICMP
 IPv6
4.5 các thuật toán routing
 link state
 distance vector
 hierarchical routing
4.6 routing trong Internet
 RIP
 OSPF
 BGP
4.7 broadcast và multicast 
routing
Chương 4: Nội dung
Tầng Network 4-4
Tầng Network
 Vận chuyển Segment từ
host gửi đến host nhận
 Bên phía gửi sẽ đóng gói 
(encapsulate) các segment 
vào trong các datagram
 Bên phía nhận, chuyển các
segment lên tầng transport
 Các giao thức tầng network 
trong mọi host, mọi router
 router sẽ xem xét các 
trường của header trong 
tất cả các IP datagram đi 
qua nó
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
Tầng Network 4-5
2 chức năng chính của tầng network
 forwarding: di chuyển 
các packet từ đầu vào 
đến đầu ra thích hợp 
của router
 routing: xác định 
đường đi cho các gói 
từ nguồn đến đích. 
 Các thuật toán định 
tuyến
Tương tự:
 routing: tiến trình lặp 
kế hoạch cho chuyến 
đi của packet từ
nguồn tới đích
 forwarding: tiến trình 
vận chuyển qua 1 giao 
điểm
Tầng Network 4-6
1
23
0111
Giá trị 
trong header 
của packet đến
Thuật toán routing
local forwarding table
header value output link
0100
0101
0111
1001
3
2
2
1
Tác động qua lại giữa routing và forwarding
Thuật toán routing xác định đường
đi của gói giữa 2 đầu cuối 
thông qua network
Bảng forwarding xác định việc
chuyển gói bên trong một router
Tầng Network 4-7
Thiết lập kết nối
 Chức năng qua trọng thứ 3 trong một số kiến 
trúc mạng:
 ATM, frame relay, X.25
 Trước khi các datagram di chuyển, 2 host đầu 
cuối và router trung gian (intervening routers) 
thiết lặp kết nối ảo
 Các router cũng tham gia
 Dịch vụ kết nối tầng transport so với tầng 
network :
 network: giữa 2 hosts (cũng có thể bao gồm các 
router trung gian trong trường hợp kết nối ảo)
 transport: giữa 2 tiến trình
Tầng Network 4-8
Mô hình dịch vụ Network
Hỏi: mô hình dịch vụ nào cho “kênh” truyền 
các datagram từ bên gửi đến bên nhận?
Ví dụ các dịch vụ cho
các datagram riêng
biệt:
 Giao nhận bảo đảm
 Giao nhận bảo đảm với
độ trễ < 40ms
Ví dụ các dịch vụ cho 
1 luồng các 
datagram:
 Giao nhận datagram 
theo thứ tự
 Băng thông được bảo 
đảm tối thiểu cho luồng
 Hạn chế các thay đổi 
trong khoảng trống 
giữa các packet
Tầng Network 4-9
Các mô hình dịch vụ tầng Network:
Kiến trúc
Network
Internet
ATM
ATM
ATM
ATM
Mô hình
dịch vụ
best effort
CBR
VBR
ABR
UBR
Băng thông
không
Tốc độ
không đổi
Tốc độ
bảo đảm
Tốc độ
bảo đảm
không
Mất 
không
có
có
no
no
Thứ tự
không
có
có
có
có
Định thì
không
có
có
không
không
Phản hồi
tắt nghẽn
no (inferred
via loss)
Không
tắt nghẽn
Không
tắt nghẽn
có
không
Bảo đảm?
Tầng Network 4-10
4.1 Giới thiệu
4.2 virtual circuit 
network (Mạng mạch
ảo) và datagram 
network
4.3 Cấu trúc bên trong
router
4.4 IP: Internet Protocol
 Định dạng datagram
 IPv4 addressing
 ICMP
 IPv6
4.5 các thuật toán routing
 link state
 distance vector
 hierarchical routing
4.6 routing trong Internet
 RIP
 OSPF
 BGP
4.7 broadcast và multicast 
routing
Chương 4: Nội dung
Tầng Network 4-11
Dịch vụ connection (hướng kết nối) và
connection-less (phi kết nối)
 Mạng datagram cung cấp dịch vụ
connectionless tại tầng network
 Mạng mạch ảo (virtual-circuit network) 
cung cấp dich vụ connection tại tầng
network
 Tương tự như các dịch vụ kết nối định
hướng và không định hướng của tầng
transport, nhưng:
 Dịch vụ: host-to-host
 Không lựa chọn: network chỉ cung cấp 1 
dịch vụ
 Thực hiện: trong mạng lõi
Tầng Network 4-12
Các mạch ảo (Virtual circuits)
 Thiết lặp cuộc gọi, chia nhỏ mỗi cuộc gọi trước khi 
dữ liệu có thể truyền 
 Mỗi packet mang định dạng của kết nối ảo (VC 
identifier) (không phải là địa chỉ của 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 mà gói đi qua.
 Đường link, các tài nguyên router (băng thông, bộ
nhớ đẹm) có thể được cấp phát cho kết nối ảo
“đường đi từ nguồi tới đích tương tự như
mạng điện thoại (telephone circuit)”
 Hiệu quả
 Các hoạt động của mạng dọc theo đường đi từ
nguồn tới đích
Tầng Network 4-13
Sự thực hiện kết nối ảo (VC)
Một kết nối ảo bao gồm:
1. Đường đi (path) từ nguồn tới đích
2. Số hiệu kết nối ảo (VC numbers), một số cho
một kết nối dọc theo đường đi
3. Các mục trong các bảng forwarding ở trong các
router dọc theo đường đi
 packet thuộc về kết nối ảo mang số hiệu
(chứ không phải là điểm đến)
 Số hiệu của kết nối ảo có thể được thay
đổi trên mỗi kết nối.
 Số hiệu mới của kết nối ảo được cấp phát từ
bảng forwarding
Tầng Network 4-14
Bảng forwarding của kết nối ảo
12 22 32
1
2
3
VC number
interface
number
Cổng vào 
1 12 3 22
2 63 1 18 
3 7 2 17
1 97 3 87
Bảng forwarding trong router
ở góc trái trên cùng:
Các router kết nối ảo duy trì thông tin trạng thái kết nối!
số hiệu của 
kết nối ảo vào Cổng ra
số hiệu của 
kết nối ảo ra
Tầng Network 4-15
application
transport
network
data link
physical
Các mạch ảo: các giao thức gửi tín hiệu
 Được dùng để thiết lập, duy trì kết nối ảo
 Được dùng trong ATM, frame-relay, X.25
 Không được sử dụng trong Internet ngày 
nay
1. Khởi tạo 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. Bắt đầu dòng dữ liệu 6. Nhận dữ liệu
application
transport
network
data link
physical
Tầng Network 4-16
Mạng Datagram
 Không thiết lập cuộc gọi tại tầng network
 Các router: không có trạng thái về các kết nối 
giữa 2 điểm cuối
 Không có khái niệm về mức network của “kết nối”
 Các packet được chuyển dùng địa chỉ của host 
đích
1. Gởi các datagram
application
transport
network
data link
physical
application
transport
network
data link
physical
2. Nhận datagram
Tầng Network 4-17
1
23
Bảng Datagram forwarding
Địa chỉ IP đích trong 
header của packet đến
Thuật toán routing
local forwarding table
dest address output link
address-range 1
address-range 2
address-range 3
address-range 4
3
2
2
1
4 tỉ địa chỉ IP, vì liệt 
kê ra 1 dãy các địa chỉ
hơn là liệt kê ra từng 
địa chỉ (các mục tổng 
hợp)
Tầng Network 4-18
Dãy địa chỉ đích
11001000 00010111 00010000 00000000
đến
11001000 00010111 00010111 11111111
11001000 00010111 00011000 00000000
đến
11001000 00010111 00011000 11111111
11001000 00010111 00011001 00000000
đến
11001000 00010111 00011111 11111111
khác
Link Interface
0
1
2
3
Q: nhưng cái gì sẽ xảy ra nếu các dãy địa chỉ này 
không được chia hợp lý?
Bảng Datagram forwarding
Tầng Network 4-19
So trùng prefix dài nhất
Dãy địa chỉ đích
11001000 00010111 00010*** *********
11001000 00010111 00011000 *********
11001000 00010111 00011*** *********
otherwise
Khi tìm kiếm 1 mục trong bảng forwarding 
table cho địa chỉ đích, dùng prefix dài nhất 
của địa chỉ cái mà trùng với địa chỉ đích.
So trùng prefix dài nhất
Link interface
0
1
2
3
Tầng Network 4-20
Mạng datagram hoặc mạch ảo: 
tại sao?
Internet (datagram)
 Dữ liệu trao đổi giữa các 
máy tính
 Dịch vụ “mềm dẻo, không 
định thì chặt chẽ.
 Nhiều kiểu link
 Các đặc tính khác nhau
 Khó đồng nhất dịch vụ
 Các hệ thống đầu cuối 
“thông minh” (các máy 
tính)
 Có thể thích ứng, điều 
khiển và sửa lỗi
 Mạng bên trong đơn 
giản, phức tạp tại “mạng 
bên ngoài”
ATM (mạch ảo)
 Được phát triển từ hệ
thống điện thoại
 Đàm thoại của con 
người: 
 Qui định chặt chẽ, yêu 
cầu về độ tin cậy
 Cần cho các dịch vụ có 
yêu cầu bảo đảm cao
 Các hệ thống đầu cuối 
“ít thông minh”
 Điện thoại
 Bên trong mạng phức 
tạp
Tầng Network 4-21
4.1 Giới thiệu
4.2 virtual circuit 
network (mạng mạch
ảo) và datagram 
network
4.3 Cấu trúc bên trong
router
4.4 IP: Internet Protocol
 Định dạng datagram
 IPv4 addressing
 ICMP
 IPv6
4.5 các thuật toán routing
 link state
 distance vector
 hierarchical routing
4.6 routing trong Internet
 RIP
 OSPF
 BGP
4.7 broadcast và multicast 
routing
Chương 4: Nội dung
Tầng Network 4-22
Tổng quan kiến trúc Router
2 chức năng chính của router:
 Chạy các giao thức/thuật toán routing (RIP, OSPF, BGP)
 Chuyển tiếp các datagram từ đường link vào tới đường
link ra
high-seed 
switching
fabric
routing 
processor
router input ports router output ports
forwarding data 
plane (hardware)
routing, management
control plane (software)
forwarding tables computed,
pushed to input ports
Tầng Network 4-23
line
termination
link 
layer 
protocol
(receive)
lookup,
forwarding
queueing
Các chức năng của cổng Input
decentralized switching:
 Với đích của datagram biết trước., tìm 
output port (cổng ra) bằng cách dùng 
bảng forwarding trong bộ nhớ của input 
port (cổng vào) (“match plus action”)
 Mục tiêu: hoàn tất xử lý input port tại 
“tốc độ dòng” (‘line speed’)
 Xếp hàng: nếu datagram đến nhanh hơn 
tốc độ chuyển tiếp bên trong switch
Tầng physical :
Tiếp nhận mức bit
Tầng data link:
Như là Ethernet
Xem chương 5
switch
fabric
Tầng Network 4-24
Switching fabrics
 Truyền packet từ bộ nhớ đệm đầu vào đến bộ 
nhớ đệm đầu ra thích hợp
 Tốc độ switching: tốc độ mà các packet có thể 
được truyền từ đầu vào (inputs) đến đầu ra 
(outputs)
 Thường được đo như nhiều tốc độ dòng của đầu vào/đầu ra
 N inputs: switching rate N times line rate desirable
 3 kiểu switching fabrics
memory
memory
bus crossbar
Tầng Network 4-25
Switching thông qua bộ nhớ (memory)
Các router thế hệ đầu tiên:
 Các máy tính cổ điển với switching dưới sự điều 
khiển của CPU
 packet được sao chép đến bộ nhớ của hệ thống
 Tốc độ bị giới hạn bởi băng thông của bộ nhớ (2 bus 
qua mỗi datagram)
input
port
(như
Ethernet)
memory
output
port
(như
Ethernet)
Bus hệ thống
Tầng Network 4-26
Switching thông qua 1 bus
 datagram từ bộ nhớ của port 
vào đến bộ nhớ của port ra
thông qua một bus được chia 
sẻ
 Sự tranh chấp bus: tốc độ
switching bị giới hạ bởi băng
thông của bus
 32 Gbps bus, Cisco 5600: tốc
độ đủ cho truy cập và các
enterprise router
bus
Tầng Network 4-27
Switching thông qua interconnection 
network
 Vượt qua các giới hạn của băng
thông bus
 Đa mạng, crossbar, các mạng kết
nối nội bộ khác lúc đầu được
phát triển để kết nối các bộ vi 
xử lý trong bộ đa xử lý
 Thiết kế được nâng cao: phân
mảnh datagram vào các ô có độ
dài cố định, chuyển các ô thông
qua fabric. 
 Cisco 12000: chuyển 60 Gbps
thông qua interconnection 
network
crossbar
Tầng Network 4-28
Các cổng ra (Output)
 Đệm (buffering) được yêu cầu khi các
datagram đến từ fabric nhanh hơn tốc độ
truyền
 scheduling discipline chọn trong số các
datagram xếp hàng để truyền
line
termination
link 
layer 
protocol
(send)
switch
fabric
datagram
buffer
queueing
Tầng Network 4-29
Sắp hàng tại cổng ra
 Đệm khi tốc độ đến qua switch vượt quá tốc 
độ dòng ra (output line)
 Sắp hàng (trễ) và mất gói vì bộ nhớ đệm tại 
cổng ra bị tràn (overflow)!
at t, các packet nhiều hơn 
từ đầu vào đến đầu ra
one packet time later
switch
fabric
switch
fabric
Tầng Network 4-30
Bao nhiêu đệm?
 RFC 3439 quy tắc ngón tay cái: đệm trung 
bình bằng với thời gian RTT “điển hình” 
(250 msec) nhân với dung lượng đường link 
C
 Ví dụ C = 10 Gpbs link: 2.5 Gbit buffer
 Khuyến nghị gần đây: với N luồng, đệm bằng 
với RTT C.
N
Tầng Network 4-31
Sắp hàng tại cổng vào
 fabric chậm hơn sự phối hợp của các cổng vào -> sắp hàng 
có thể xảy ra tại các hàng vào
 Sắp hàng chậm trễ vào mất gói do tràn bộ đệm đầu 
vào!
 Head-of-the-Line (HOL) blocking: datagram được sắp 
hàng tại phía trước hàng đợi ngăn cản các datagram khác 
trong hàng đợi di chuyển lên trước
Sự cạnh tranh tại cổng ra:
Chỉ có một datagram màu đỏ
có thể được truyền.
packet màu đỏ thấp hơn bị
chặn lại
switch
fabric
one packet time 
later: packet màu 
xanh lá trải qua 
HOL blocking
switch
fabric
Tầng Network 4-32
4.1 Giới thiệu
4.2 virtual circuit 
network và datagram 
network
4.3 Cấu trúc bên trong
router
4.4 IP: Internet Protocol
 Định dạng datagram
 IPv4 addressing
 ICMP
 IPv6
4.5 các thuật toán routing
 link state
 distance vector
 hierarchical routing
4.6 routing trong Internet
 RIP
 OSPF
 BGP
4.7 broadcast và multicast 
routing
Chương 4: Nội dung
Tầng Network 4-33
Tầng Internet network
forwarding
table
Các chức năng tầng network của host và router:
Các giao thức routing
• chọn đường đi
• RIP, OSPF, BGP
Giao thức IP
• các quy ước định địa chỉ
• định dạng datagram
• các quy ước quản lý gói
Giao thức ICMP
•Thông báo lỗi
• “tín hiệu” router
transport layer: TCP, UDP
Tầng link
Tầng physical
Tầng
network
Tầng Network 4-34
ver length
32 bits
Dữ liệu
(độ dài thay đổi,
thông thường là một 
segment TCP 
hoặc UDP)
16-bit identifier
header
checksum
time to
live
32 bit source IP address
head.
len
type of
service
flgs
fragment
offset
upper
layer
32 bit destination IP address
Tùy chọn (nếu có)
Định dạng IP datagram
Số hiệu phiên bản 
giao thức IP
Độ dài header
(bytes)
Giao thức lớp trên
để đưa payload đến
Tổng độ dài
datagram(byte)
“kiểu” dữ liệu
Dành cho 
phân mảnh/
tổng hợpSố hop còn lại 
tối đa (giảm xuống 
tại mỗi router)
Ví dụ: trường 
timestamp ghi lại
đường đi, danh 
các router đi đến
how much overhead?
 20 bytes of TCP
 20 bytes of I ... outer có thể học hơn 1 route tới AS đích, 
chọn route dựa trên:
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: định tuyến hot 
potato
4. Tiêu chuẩn bổ sung
Tầng Network 4-120
Các thông điệp BGP
 Các thông điệp BGP được trao đổi giữa các peer trên kết 
nối 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: quảng cáo đường đi mới(hoặc là lấy lại cái 
cũ)
 KEEPALIVE: giữ kết nối sống khi các UPDATES không 
được cập nhật; còn 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 đó; cũng được sử dụng để đóng kết nối
Đặt các giao thức định tuyến
lại với nhau:
Làm thế nào một entry đưa vào
trong bảng forwarding của 1 
router?
 Câu trả lời rất phức tạp!
 Buộc các định tuyến phân cấp (mục 4.5.3) lại 
với nhau với BGP (4.6.3) và OSPF (4.6.2).
 Cung cấp tổng quan về BGP!
123
Dest IP
Thuật toán định 
tuyến
Bảng local forwarding
prefix output port
138.16.64/22
124.12/16
212/8
..
3
2
4
Làm thế nào để entry được đưa vào
bảng forwarding?
entry
Giả sử prefix 
là trong AS khác.
1. Router nhận thức được prefix
2. Router xác định port ra (output port) cho 
prefix
3. Router đưa cổng cho prefix đó vào trong 
bảng forwarding
Làm thế nào để entry được đưa vào
bảng forwarding?
Router nhận thức được prefix
AS3
AS2
3b
3c
3a
AS1
1c
1a
1d
1b
2a
2c
2b
other
networks
other
networks
Thông điệp
BGP 
 Thông điệp BGP chứa “các route” 
 “route” là 1 prefix và các thuộc tính: AS-PATH, 
NEXT-HOP,
 Ví dụ: route:
 Prefix:138.16.64/22 ; AS-PATH: AS3 AS131 ; 
NEXT-HOP: 201.44.13.125
Router có thể nhận được nhiều
route
AS3
AS2
3b
3c
3a
AS1
1c
1a
1d
1b
2a
2c
2b
other
networks
other
networks
Thông điệp
BGP 
 Router có thể nhận được nhiều route cho 
cùng prefix
 Phải chọn 1 route
 Router chọn route dựa trên AS-PATH ngắn 
nhất
Chọn route BGP tốt nhất tới prefix
 Ví dụ:
 AS2 AS17 to 138.16.64/22 
 AS3 AS131 AS201 to 138.16.64/22 
 Điều gì sẽ xảy ra nếu có mối ràng buộc? 
Chúng ta sẽ bàn sau!
Chọn
Tìm route nội bộ tốt nhất đến
route BGP
 Dùng thuộc tính NEXT-HOP của route được lựa 
chọn
 Thuộc tính NEXT-HOP của Route là địa chỉ IP của 
interface của router đó, cái mà bắt đầu AS PATH đó.
 Ví dụ: 
 AS-PATH: AS2 AS17 ; NEXT-HOP: 111.99.86.55
 Router sử dụng OSPF để tìm ra đường đi ngắn nhất 
từ 1c tới 111.99.86.55
AS3
AS2
3b
3c
3a
AS1
1c
1a
1d
1b
2a
2c
2b
other
networks
other
networks
111.99.86.55
Router xác định port cho route
 Xác định port theo đường đi OSPF ngắn nhất
 Thêm prefix-port entry vào bảng forwarding 
của nó:
 (138.16.64/22 , port 4) 
AS3
AS2
3b
3c
3a
AS1
1c
1a
1d
1b
2a
2c
2b
other
networks
other
networks
router
port
1
2 3
4
Định tuyến Hot Potato
 Giả sử có 2 hoặc nhiều route liên tuyến tốt
nhất (best inter-routes).
 Sau đó chọn route với NEXT-HOP gần nhất
 Dùng OSPF để xác định cổng nào là gần nhất
 Hỏi: từ 1c, chọn AS3 AS131 hoặc AS2 AS17?
 Đáp: route AS3 AS201 vì nó gần hơn
AS3
AS2
3b
3c
3a
AS1
1c
1a
1d
1b
2a
2c
2b
other
networks
other
networks
Tóm tắt
1. Router có nhận thức về prefix
 Thông qua các quảng cáo route BGP từ các router khác
2. Xác định port ra của router cho prefix đó
 Dùng route BGP vừa chọn để tìm ra route liên AS 
(inter-AS ) tốt nhất
 Dùng OSPF để tìm ra route tốt nhất trong nội bộ AS 
(intra-AS ) cái mà dẫn đến route liên AS tốt nhất
(inter-AS route)
 Router xác định port của router cho route tốt nhất đó
3. Đưa prefix-port entry vào trong bảng forwarding
Làm thế nào để entry được đưa vào
bảng forwarding?
Tầng Network 4-131
Chính sách BGP routing
 A,B,C là các nhà cung cấp mạng
 X,W,Y là khách hàng (của nhà cung cấp mạng)
 X là dual-homed: được kết nối vào 2 mạng
 X không muốn có tuyến đường từ B thông qua X tới C
 .. Vì vậy X sẽ không quảng cáo cho B tuyến đường tới 
C
A
B
C
W
X
Y
Ký hiệu:
Mạng của 
khách hàng
Mạng của 
nhà cung cấp
Tầng Network 4-132
Chính sách BGP routing (2)
 A quảng cáo đường đi AW cho B
 B quảng cáo đường đi BAW cho X 
 B có nên quảng cáo đường đi BAW cho C hay không?
 Không nên! B không nhận được “thu nhập” cho việc định tuyến 
CBAW vì cả W và C không phải là khách hàng của B
 B muốn bắt buộc C đi tới w thông A
 B chỉ muốn dẫn đường đi/đến các khách hàng của nó!
A
B
C
W
X
Y
Ký hiệu: Mạng của 
nhà cung cấp
Mạng của 
khách hàng
Tầng Network 4-133
Tại sao phải định tuyến Intra-, 
Inter-AS khác nhau?
Chính sách:
 inter-AS: người quản trị muốn kiểm soát cách 
mà traffic của nó được định tuyến, ai mà định 
tuyến thông qua mạng của nó . 
 intra-AS: 1 người quản trị, vì vậy không cần 
các quyết định chính sách
Linh hoạt:
 Định tuyến phân cấp làm giảm kích thước bảng 
định tuyến, 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
Tầng Network 4-134
4.1 Giới thiệu
4.2 virtual circuit 
network và datagram 
network
4.3 Cấu trúc bên trong
router
4.4 IP: Internet Protocol
 Định dạng datagram
 IPv4 addressing
 ICMP
 IPv6
4.5 các thuật toán routing
 link state
 distance vector
 hierarchical routing
4.6 routing trong Internet
 RIP
 OSPF
 BGP
4.7 broadcast và multicast 
routing
Chương 4: Nội dung
Tầng Network 4-135
R1
R2
R3 R4
Nguồn 
trùng lặp
R1
R2
R3 R4
Trùng lặp
trong mạng
duplicate
creation/transmission
duplicate
duplicate
Broadcast routing
 Chuyển các packet từ nguồn tới tất cả các node 
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 được địa 
chỉ người nhận?
Tầng Network 4-136
Trùng lặp trong mạng
 flooding: khi node nhận được packet 
broadcast, nó gởi bản sao đến tất cả các 
neighbor
 Vấn đề: lặp lại & bão broadcast
 Flooding có điều khiển: node chỉ broadcast 
packet nếu nó không gửi broadcast giống 
như vậy trước đó
 node theo dõi các packet đã broadacst
 Hoặc reverse path forwarding (RPF): chỉ chuyển 
các packet nếu nó đã đến trên đường đi ngắn 
nhất giữa node và nguồn
 spanning tree:
 Không có các packet dư thừa được nhận tại bất 
cứ node nào
Tầng Network 4-137
A
B
G
D
E
c
F
A
B
G
D
E
c
F
(a) broadcast được khởi tạo tại A (b) broadcast được khởi tạo tại D
Spanning tree
 Đầu tiên xây dựng một spanning tree
 Sau đó các node chuyển tiếp/tạo các bản
sao chỉ dọc theo spanning tree
Tầng Network 4-138
A
B
G
D
E
c
F
1
2
3
4
5
(a) Các bước xây dựng 
spanning tree (center: E)
A
B
G
D
E
c
F
(b) spanning tree đã được 
xây dựng xong
Spanning tree: tạo
 Node trung tâm
 Mỗi node gởi thông điệp gia nhập unicast
(unicast join message) đến node trung tâm
 Thông điệp này được chuyển tiếp cho đến khi nó
đến tại một node đã nằm trên spanning tree
Tầng Network 4-139
Multicast routing: phát biểu vấn đề
Mục tiêu: tìm một cây (hoặc các cây) kết nối các router 
có các thành viên trong nhóm multicast
 Cây (tree): không phải tất cả các đường đi giữa các
router đều được sử dụng
 Cây chia sẽ (shared-tree): cây giống nhau được sử dụng bởi
các thành viên trong nhóm
Cây chia sẽ Cây dựa trên nguồn
group 
member
not group 
member
router
with a
group 
member
router
without
group 
member
Ký hiệu Cây dựa trên nguồn(source-based): cây 
khác nhau từ nơi gửi tới nơi nhận
Tầng Network 4-140
Các cách tiếp cận để xậy dựng các
cây multicast
Các hướng tiếp cận:
 Cây dựa trên nguồn (source-based tree): một
cây cho 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 dựa trên trung tâm (center-based trees)
tìm hiểu các cách tiếp cận cơ bản, sau đó các giao thức 
cụ thể áp dụng cho các hướng tiếp cận này
Tầng Network 4-141
Cây đường đi ngắn nhất
 Cây chuyển tiếp multicast (mcast forwarding 
tree): cây đường đi ngắn nhất dẫn đường từ
nguồn tới tất cả các nơi nhận
 Thuật toán Dijkstra
i
router với các thành viên
của nhóm đã được gắn vào
router không có các thành viên
nào của nhóm được gắn vào
Đường kết nối được sử dụng
cho forwarding,
i chỉ thứ tự đường link được 
thêm vào bởi thuật toán
Ký hiệu
R1
R2
R3
R4
R5
R6 R7
2
1
6
3 4
5
s: nguồn
Tầng Network 4-142
Reverse path forwarding
if (datagram multicast được nhận trên đường
kết nối đến trên đường đi ngắn nhất kể từ
trung tâm)
then flood datagram lên tất cả các kết nối ra
else bỏ qua datagram
 Dựa vào kiến 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:
Tầng Network 4-143
Reverse path forwarding: ví dụ
 Kết quả là một cây SPT đảo ngược
 Có thể là một lựa chọn không tốt với các 
kết nối không đồng bộ
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ệu
R1
R2
R3
R4
R5
R6 R7
s: nguồn
datagram sẽ không 
được forward
Tầng Network 4-144
Reverse path forwarding: 
cắt giảm (pruning)
 Cây forwarding chứa các cây con không có các thành 
viên trong nhóm multicast
 Không cần forward các datagram xuống cây con
 “cắt giảm” các thông điệp được gửi lên trên bởi 
router không có các thành viên nhóm downstream
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
thông điệp cắt giảm
Ký hiệu
các kết nối với multicast
forward
P
R1
R2
R3
R4
R5
R6
R7
s: nguồn
P
P
Tầng Network 4-145
Cây chia sẽ (Shared-tree): cây steiner
 Cây steiner : cây có chi phí thấp nhất kết
nối đến tất cả các router với các thành viên
nhóm đã được gắn vào
 Vấn đề là NP-complete
 Các heuristics rất tốt tồn tại
 Không sử dụng trong thực tế:
 Độ phức tạp tính toán
 Cần thông tin về về toàn bộ mạng
 monolithic: chạy lại mỗi khi router cần gia
nhập/rời khỏi
Tầng Network 4-146
Cây dựa vào trung tâm
(Center-based trees)
 Một cây truyền nhận được chia sẽ cho tất 
cả
 Một router được xác định như là “trung 
tâm” của cây
 Để gia nhập:
 router biên (edge ) gửi thông điệp gia nhập 
unicast đến router trung tâm
 Thông điệp gia nhập (join-msg ) “được xử lý” bởi 
các router trung gian và chuyển đến các router 
trung tâm 
 Thông điệp gia nhập, hoặc đến nhánh cây của 
trung tâm này, hoặc đến ngay trung tâm
 Đường đi được thực hiệu bởi thông điệp gia nhập
trở thành nhánh cây mới của router này
Tầng Network 4-147
Cây dựa vào trung tâm: ví dụ
Giả sử R6 được chọn là trung tâm:
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
thứ tự đường đi trong ấy 
các thông điệp gia nhập đã 
sinh ra
LEGEND
2
1
3
1
R1
R2
R3
R4
R5
R6
R7
Tầng Network 4-148
Internet Multicasting Routing: DVMRP
 DVMRP: distance vector multicast routing 
protocol, RFC1075
 flood và prune: forwarding đường đi ngược 
(reverse path forwarding), cây dựa vào 
nguồn (source-based tree)
 Cây RPF dựa trên các bảng định tuyến của 
DVMRP của nó được xây dựng bởi truyền thông 
các router DVMRP
 Không có các giả thuyết về unicast bên dưới
 datagram ban đầu đến nhóm multicast được 
flood mọi nơi thông qua RPF
 Các router không phải nhóm: gửi thông điệp cắt 
giảm lên trên
Tầng Network 4-149
DVMRP: tiếp tục
 Trạng thái mềm: router DVMRP chu kỳ (1 
phút) “quên” các nhánh cây bị cắt giảm: 
 Dữ liệu mcast một lần nữa đổ xuống các nhánh 
không được cắt giảm
 Router phía dưới: cắt giảm lần nữa 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 lá
 Còn lại
 Thường được thực hiện trong router thương mại
Tầng Network 4-150
Tunneling
Q: làm cách nào để kết nối “các đảo” của các 
router muticast trong một “biển” của các 
router unicast? 
 datagram multicast được đóng gói trong datagram 
“thông thường” (không có multicast)
 datagram IP thông thường được gửi thông qua “đường 
hầm” (“tunnel”) và qua IP unicast đến router muticast 
nhận (xem lại IPv6 bên trong đường hầm IPv4)
 router mcast nhận mở gói để lấy datagram multicast
Cấu trúc vật lý Cấu trúc logic
Tầng Network 4-151
PIM: Protocol Independent Multicast
 Không phụ thuộc vào bất kỳ thuật toán định
tuyến unicast bên dưới nào (underlying 
unicast routing algorithm) (làm việc với tất
cả)
 2 ngữ cảnh phân phối multicast khác nhau:
Dầy đặc:
 Các thành viên nhóm 
đóng gói dày đặc, 
trong khoảng cách 
“gần”.
 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 
”được phân bố thưa thớt”
 Băng thông không dư thừa
Tầng Network 4-152
Kết quả của sự phân chia thưa thớt-dày
đặc:
Dày đặc
 Nhóm các thành viên bởi 
các router được giả định 
cho đến khi các router 
cắt giảm thực sự
 Kiến trúc data-driven
trên cây mcast (ví dụ
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 router thực
sự gia nhập
 Kiến trúc receiver- driven
của cây mcast (ví dụ cây
dựa vào trung tâm)
 Băng thông và router 
không thuộc nhóm xử lý
vừa phải
Tầng Network 4-153
PIM- kiểu dày đặc
flood-and-prune RPF: tương tự như
DVMRP nhưng
 Giao thức bên dưới cung cấp thông tin RPF 
cho datagram đến
 flood xuống dưới (downstream) ít phức 
tạp (ít hiệu quả) hơn so với DVMRP giảm sự
phụ thuộc vào thuật toán định tuyến cơ
bản
 Có cơ chế giao thức cho router để phát 
hiện có phải là router ở node lá (leaf-
node)
Tầng Network 4-154
PIM – kiểu thưa thớt
 Tiếp cận dựa vào trung 
tâm (center-based)
 router gởi thông điệp gia 
nhập (join msg) đế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 thông qua 
RP, router có thể chuyển 
sang cây xác định nguồn 
(source-specific tree)
 Hiệu xuất tăng: ít tập 
trung, các đường đi 
ngắn hơn
Tất cả dữ liệu 
multicast đến từ
rendezvous
point
rendezvous
point
join
join
join
R1
R2
R3
R4
R5
R6
R7
Tầng Network 4-155
(Các) 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 (stop msg) 
nếu không có bên nhận 
nào được ngắn vào
 “không có ai đang lắng 
nghe!”
Tất cả dữ liệu 
multicast đến từ
rendezvous
point
rendezvous
point
join
join
join
R1
R2
R3
R4
R5
R6
R7
PIM – kiểu thưa thớt
Tầng Network 4-156
4.1 Giới thiệu
4.2 Mạng mạch ảo và 
mạng datagram (virtual 
circuit and datagram 
networks)
4.3 bên trong router
4.4 IP: Internet Protocol
 datagram định dạng, 
định địa chỉ IPv4, ICMP, 
IPv6
4.5 các thuật toán định tuyến
 link state, distance vector, 
định tuyến phân cấp
4.6 định tuyến trong Internet
 RIP, OSPF, BGP
4.7 broadcast and multicast 
routing
Chapter 4: Hoàn thành!
 Hiểu về các nguyên tắt đằng sau các dịch vụ tầng 
network:
 Các mô hình dịch vụ tầng network, so sánh cách 
mà router forwarding và routing dữ liệu, định 
tuyến(chọn đường đi), broadcast, multicast
 Hiện thực trên Internet