Bài giảng Mạng máy tính nâng cao - Chapter 4: Network Layer - Lê Ngọc Sơn

ác láng giềng.
•Ở thời điểm t2, y nhận được các cập nhật của z và cập 
nhật lại các bảng của nó. Do chi phí tối thiểu của y 
không thay đổi và do đó y không gửi bất kỳ thông tin 
nào cho z.
Network Layer 4-95
Distance Vector: link cost changes
Link cost changes:
 good news travels fast 
 bad news travels slow -
“count to infinity” problem!
 44 iterations before 
algorithm stabilizes: see text
Poisoned reverse:
 Nếu Z hướng gói tin đi qua Y 
để đến X:
• Z báo cho Y biết khoảng 
cách từ Z đến X (mà Z 
quản) là vô hạn (do đó Y sẽ 
không hướng gói tin đến X 
ngang qua Z)
 will this completely solve 
count to infinity problem?
x z
14
50
y
60
Network Layer 4-96
Comparison of LS and DV algorithms
Message complexity
 LS: với n nút, E đường truyền, 
O(nE) thông điệp được gửi
 DV: chỉ có các trao đổi giữa 
các láng giềng
 Thời gian hội tụ biến động
Speed of Convergence
 LS: thuật toán O(n2) đòi hỏi 
O(nE) thông điệp
 Có thể có sự dao động
 DV: Thời gian hội tụ biến 
động
 Vấn đề routing loop
 Vấn đề count-to-infinity
Robustness: điều gì sẽ xảy ra 
nếu router hỏng hóc?
LS:
 Nút có thể quảng cáo chi phí 
đường truyền không chính 
xác.
 Mỗi nút chỉ tính bảng của 
chính nó
DV:
 Nút có thể quảng cáo chi phí 
tuyến đường không chính xác
 Bảng của từng nút được các 
nút khác sử dụng
• Lỗi lan truyền qua mạng
Network Layer 4-97
Chapter 4: Network Layer
 4. 1 Introduction
 4.2 Virtual circuit and 
datagram networks
 4.3 What’s inside a 
router
 4.4 IP: Internet Protocol
 Datagram format
 IPv4 addressing
 ICMP
 IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the 
Internet
 RIP
 OSPF
 BGP
 4.7 Broadcast and 
multicast routing
Network Layer 4-98
Hierarchical Routing
scale: với 200 triệu đích 
đến:
 Không thể lưu tất cả các đích 
đến trong routing table!
 Việc trao đổi các routing table 
có thể làm cho các đường 
truyền tràn ngập thông tin 
định tuyến, ko còn chỗ cho 
truyền dữ liệu!
administrative autonomy
 internet = mạng của các mạng
 Mỗi quản trị viên mạng có thể 
muốn kiểm soát việc định 
tuyến trong mạng của họ.
Các giả định nghiên cứu trước đây còn lý tưởng:
 Tất cả các routers đều giống nhau
 network “flat” (i.e không phân cấp)
 không khả thi, vì:
Network Layer 4-99
Hierarchical Routing
 Gom các router vào trong 
1 vùng, gọi là
“autonomous systems” 
(AS)
 Các router trong cùng AS 
sẽ chạy cùng 1 routing 
protocol
 “intra-AS” routing protocol
 Các router trong các AS 
khác nhau có thể chạy các 
intra-AS routing protocol 
khác nhau.
Gateway router
 Nối trực tiếp đến router 
trong AS khác.
3b
1d
3a
1c
2a
AS3
AS1
AS2
1a
2c
2b
1b
3c
Network Layer 4-100
Interconnected ASes
 Forwarding table được 
cấu hình bởi cả intra- và 
inter- AS routing 
protocol
 Intra-AS thiết lập các 
dòng định tuyến cho các 
đích đến bên trong AS.
 Inter-AS và intra-AS thiết 
lập các dòng định tuyến 
cho các đích đến bên 
ngoài.
3b
1d
3a
1c
2a
AS3
AS1
AS2
1a
2c
2b
1b
3c
Intra-AS
Routing 
algorithm
Inter-AS
Routing 
algorithm
Forwarding
table
Network Layer 4-101
3b
1d
3a
1c
2aAS3
AS1
AS2
1a
2c
2b
1b
3c
Inter-AS tasks
 Giả sử rằng router trong 
AS1 nhận được datagram 
hướng ra bên ngoài AS1:
 Router cần chuyển gói 
tin đến gateway 
router nào?
AS1 phải:
1. Tìm hiểu xem đích đến 
nào là có thể chạm tới 
được thông qua AS2, 
hoặc AS3.
2. Truyền bá khả năng 
này cho tất cả các 
router trong AS1.
Job of inter-AS routing!
Network Layer 4-102
Example: Setting forwarding table in router 1d
 Giả sử AS1 học được thông tin (thông qua inter-AS 
protocol) là có thể đến được subnet x thông qua AS3 
(gateway 1c) nhưng không qua AS2.
 inter-AS protocol truyền thông tin này đến tất cả các 
router bên trong.
 Router 1d xác định được rằng interface I của nó là nằm 
trên đường ngắn nhất đến 1c.
 Thêm/cập nhật dòng (x,I) vào forwarding table
3b
1d
3a
1c
2aAS3
AS1
AS2
1a
2c
2b
1b
3c
x
Network Layer 4-103
Example: Choosing among multiple ASes
 Giả sử AS1 học được từ inter-AS protocol rằng có thể đến 
được subnet x bằng cách đi qua AS3 hoặc qua AS2.
 Để cấu hình forwarding table, router 1d phải xác định 
gateway nào sẽ chịu trách nhiệm chuyển gói tin đến 
mạng x.
 Đây cũng là công việc của inter-AS routing protocol!
3b
1d
3a
1c
2aAS3
AS1
AS2
1a
2c
2b
1b
3c
x
Network Layer 4-104
Example: Choosing among multiple ASes
 Giả sử AS1 học được từ inter-AS protocol rằng có thể đến 
được subnet x bằng cách đi qua AS3 hoặc qua AS2.
 Để cấu hình forwarding table, router 1d phải xác định 
gateway nào sẽ chịu trách nhiệm chuyển gói tin đến 
mạng x.
 Đây cũng là công việc của inter-AS routing protocol!
 hot potato routing: gửi gói tin về hướng router gần nhất.
Học từ inter-AS 
protocol rằng có 
thể đến được 
subnet X qua nhiều 
gateway
Sử dụng thông tin từ
intra-AS protocol để 
xác định chi phí của 
đường đi tối thiểu 
cho từng gateway.
Hot potato routing:
Chọn gateway có 
chi phí đường đi tối 
thiểu bé nhất
Xác định cho forwarding 
table rằng interface I là 
nơi dẫn đến gateway có 
chi phí tối thiểu bé nhất. 
Thêm dòng (x,I) vào 
forwarding table
Network Layer 4-105
Chapter 4: Network Layer
 4. 1 Introduction
 4.2 Virtual circuit and 
datagram networks
 4.3 What’s inside a 
router
 4.4 IP: Internet Protocol
 Datagram format
 IPv4 addressing
 ICMP
 IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the 
Internet
 RIP
 OSPF
 BGP
 4.7 Broadcast and 
multicast routing
Network Layer 4-106
Intra-AS Routing
 Còn gọi là Interior Gateway Protocols (IGP)
 Các giao thức thường gặp nhất thuộc loại này:
 RIP: Routing Information Protocol
 OSPF: Open Shortest Path First
 IGRP: Interior Gateway Routing Protocol (Cisco 
proprietary)
Network Layer 4-107
Chapter 4: Network Layer
 4. 1 Introduction
 4.2 Virtual circuit and 
datagram networks
 4.3 What’s inside a 
router
 4.4 IP: Internet Protocol
 Datagram format
 IPv4 addressing
 ICMP
 IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the 
Internet
 RIP
 OSPF
 BGP
 4.7 Broadcast and 
multicast routing
Network Layer 4-108
RIP ( Routing Information Protocol)
 Là thuật toán distance vector
 Xuất hiện trong bản BSD-UNIX Distribution vào năm 1982
 Độ đo khoảng cách: số lượng hop (tối đa trong 1 AS= 15 
hops)
 Hop: số subnet phải đi qua trên con đường ngắn nhất từ router 
nguồn đến subnet đích, kể cả subnet đích
DC
BA
u v
w
x
y
z
Subnet đích hops
u 1
v 2
w 2
x 3
y 3
z 2
Từ router A đến các subnets:
Network Layer 4-109
RIP advertisements
 distance vectors: được các router láng giềng trao 
đổi sau mỗi 30 giây, được chứa trong Response 
Message (còn được gọi là advertisement)
 Mỗi advertisement: danh sách lên tới 25 subnets 
đích bên trong AS
Network Layer 4-110
RIP: Example
Destination Network Next Router Num. of hops to dest.
w A 2
y B 2
z B 7
x -- 1
. . ....
w x y
z
A
C
D B
Routing/Forwarding table in D
Network Layer 4-111
RIP: Example
Destination Network Next Router Num. of hops to dest.
w A 2
y B 2
z B A 7 5
x -- 1
. . ....
Routing/Forwarding table in D
w x y
z
A
C
D B
Dest Next hops
w - 1
x - 1
z C 4
.  ...
Advertisement
from A to D
Network Layer 4-112
RIP: Link Failure and Recovery
Nếu 1 router không thấy adverstisement nào từ 1 router láng 
giềng của nó trong vòng 180 giây,  xem như router láng 
giềng đó đã không còn liên lạc được (có thể do router đã 
tắt/hư hoặc đường truyền bị gián đoạn)
 Các con đường đi qua router láng giềng đó bị xem là bất 
hợp lệ.
 Cần một advertisements mới để thông báo cho các router 
láng giềng (còn liên lạc được) biết điều này.
 Nếu routing table ở láng giềng có thay đổi, nó cũng sẽ gửi 
advertisement để thông báo.
 Các hỏng hóc về đường truyền được lan truyền nhanh 
chóng trên toàn mạng (về nguyên tắc).
 Kỹ thuật poison reverse được dùng để ngăn tình trạng 
ping-pong loops (infinite distance = 16 hops)
Network Layer 4-113
RIP Table processing
 UNIX: RIP routing tables được một tiến trình của tầng 
application quản lý, được gọi là route-d (daemon)
 Các advertisements được gửi định kỳ bằng UDP
physical
link
network forwarding
(IP) table
Transprt
(UDP)
routed
physical
link
network
(IP)
Transprt
(UDP)
routed
forwarding
table
Network Layer 4-114
Chapter 4: Network Layer
 4. 1 Introduction
 4.2 Virtual circuit and 
datagram networks
 4.3 What’s inside a 
router
 4.4 IP: Internet Protocol
 Datagram format
 IPv4 addressing
 ICMP
 IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the 
Internet
 RIP
 OSPF
 BGP
 4.7 Broadcast and 
multicast routing
Network Layer 4-115
OSPF (Open Shortest Path First)
 “open”: publicly available
 Sử dụng thuật toán Link State
 Gửi quảng bá các gói tin LS đến đến toàn bộ AS
• Khi router phát hiện thấy có thay đổi (chi phí, tình trạng mạng).
• Định kỳ sau mỗi 30 giây dù tình trạng mạng (Link state) có thay đổi hay 
không
 Mỗi nút phải xây dựng bản đồ mạng cho riêng nó
 Tính toán đường đi dựa vào giải thuật Dijkstra
 OSPF advertisement carries one entry per neighbor 
router
 Các advertisements được phát tán đến toàn bộ AS, chứ 
ko chỉ là các router láng giềng
 Được thực hiện nhờ các OSPF message, trên nền IP (thay vì TCP 
hay UDP)
Network Layer 4-116
OSPF “advanced” features (not in RIP)
 security: tất cả các OSPF message đều được chứng thực 
(nhằm ngăn chặn những xâm nhập phá hoại)
 Cho phép nhiều đường đến đích có chi phí bằng nhau 
(nhưng trong RIP thì chỉ có 1 đường)
 Với mỗi đường truyền, có nhiều độ đo chi phí ứng với các 
kiểu dịch vụ (TOS – type of service) khác nhau (e.g., 
satellite link cost set “low” for best effort; high for real 
time)
 Cho phép tích hợp unicast và multicast:
 Multicast OSPF (MOSPF) sử dụng cùng dữ liệu về tình 
trạng mạng như OSPF
 Cho phép AS cỡ lớn được cấu trúc phân cấp (hierarchical) 
và làm việc theo OSPF
Network Layer 4-117
Hierarchical OSPF
Network Layer 4-118
Hierarchical OSPF
 Phân cấp 2 mức: vùng cục bộ, backbone.
 Các link-state advertisement chỉ được gửi trong vùng 
cục bộ
 each nodes has detailed area topology; only know 
direction (shortest path) to nets in other areas.
 area border routers: “summarize” distances to nets in 
own area, advertise to other Area Border routers.
 backbone routers: run OSPF routing limited to backbone.
 boundary routers: connect to other AS’s.
Network Layer 4-119
Chapter 4: Network Layer
 4. 1 Introduction
 4.2 Virtual circuit and 
datagram networks
 4.3 What’s inside a 
router
 4.4 IP: Internet Protocol
 Datagram format
 IPv4 addressing
 ICMP
 IPv6
 4.5 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the 
Internet
 RIP
 OSPF
 BGP
 4.7 Broadcast and 
multicast routing
Network Layer 4-120
Internet inter-AS routing: BGP
 BGP (Border Gateway Protocol): the de facto 
standard
 BGP cung cấp cho mỗi AS phương tiện để:
1. Thu thập thông tin về các subnet có thể liên lạc 
được từ các AS láng giềng.
2. Lan truyền các thông tin về các subnet có thể liên 
lạc được cho tất cả các router bên trong AS
3. Xác định con đường “tốt” đến các subnet dựa trên 
các thông tin về các subnet có thể liên lạc được và 
chính sách của nó.
 Cho phép 1 subnet quảng cáo sự tồn tại của 
nó đến phần còn lại của Internet: “Có tôi đây”
Network Layer 4-121
BGP basics
 Các cặp router (BGP peers) trao đổi thông tin định tuyến thông qua 
kết nối TCP “semi-permanent”: BGP sessions.
 external BGP session vs. internal BGP session
 Các BGP session không cần phải tương ứng với đường truyền vật lý
 Trong BGP: đích đến không phải là host, mà là subnet, biểu diễn 
bằng prefix (Vd 138.16.64/24)
 Khi AS2 quảng cáo một prefix đến AS1:
 AS2 cam kết là nó sẽ chuyển tiếp các datagram về mạng con ứng với 
prefix.
 AS2 có thể gộp các prefix trong gói tin advertisements của nó.
3b
1d
3a
1c
2aAS3
AS1
AS2
1a
2c
2b
1b
3c
eBGP session
iBGP session
Network Layer 4-122
Distributing reachability info
 Sử dụng eBGP session giữa 3a và 1c, AS3 gửi các thông tin 
về mạng con mà có thể liên lạc được (reachable) cho AS1
 Sau đó, 1c có thể sử dụng iBGP để phân phối thông tin 
này đến tất cả các router trong AS1.
 Sau đó, 1b có thể quảng cáo tiếp thông tin này đến AS2, 
nhờ eBGP session từ 1b đến 2a.
 Khi router biết được thông tin mới, nó tạo ra một dòng cho 
một prefix trong forwarding table của nó.
3b
1d
3a
1c
2aAS3
AS1
AS2
1a
2c
2b
1b
3c
eBGP session
iBGP session
Network Layer 4-123
Path attributes & BGP routes
 Các prefix được quảng cáo kèm theo các thuộc 
tính BGP.
 prefix + attributes = “route”
 Hai thuộc tính quan trọng:
 AS-PATH: chứa các AS mà các prefix advertisement 
đi qua, VD: AS 67, AS 17 
 NEXT-HOP: chứa địa chỉ IP của interface của 
gateway router (của AS đầu tiên đi ra subnet được 
xác định bởi prefix)
 Khi một gateway router nhận được một 
advertisement, có sử dụng import policy để 
chấp nhận hoặc từ chối.
Network Layer 4-124
BGP route selection
 Router có thể học được nhiều hơn một 
tuyến đường đến 1 subnet ứng với 1 vài 
prefix. Router phải lựa chọn 1 tuyến đường.
 Quy tắc loại trừ:
1. local preference value attribute: policy decision
2. shortest AS-PATH 
3. closest NEXT-HOP router: hot potato routing
4. additional criteria 
Network Layer 4-125
BGP messages
 Các BGP messages được trao đổi giữa các router, sử 
dụng TCP.
 BGP messages:
 OPEN: mở kết nối TCP đến peer và ủy quyền cho bên 
gửi.
 UPDATE: quảng cáo tuyến đường mới (hoặc rút lại 
tuyến cũ)
 KEEPALIVE keeps connection alive in absence of 
UPDATES; also ACKs OPEN request
 NOTIFICATION: báo lỗi cho các msg trước đó; cũng 
được dùng để đóng kết nối.
Network Layer 4-126
BGP routing policy
 A,B,C là các mạng của nhà cung cấp dịch vụ
 X,W,Y là các mạng khách hàng (của nhà cung cấp)
 X là dual-homed: được nối vào 2 mạng
• X không muốn các tuyến đi từ B đến C qua nó
•  do đó X không quảng cáo đến B con đường tới C
A
B
C
W
X
Y
Ký hiệu: Mạng nhà cung 
cấp dịch vụ
Mạng của khách 
hàng
Network Layer 4-127
BGP routing policy (2)
 A quảng cáo đến B con đường AW
 B quảng cáo đến X đường BAW
 B có nên quảng cáo đến C đường BAW?
• No way! B không có “lợi nhuận” từ việc gánh luồng CBAW, 
do cả W lẫn C đều không phải là khách hàng của B
• B muốn buộc C hướng luồng dữ liệu đến w thông qua A
• B chỉ muốn phục vụ cho khách hàng của nó!
A
B
C
W
X
Y
Ký hiệu: Mạng nhà cung 
cấp dịch vụ
Mạng của khách 
hàng