Bài giảng Mạng máy tính - Chương 5: Các giao thức chọn đường - Ngô Hồng Sơn

1Chương 5:
Các giao thức chọn ñường
Dự án HEDSPI
Khoa CNTT- ðHBK Hà Nội
Giảng viên: Ngô Hồng Sơn
Bộ môn Truyền thông và Mạng máy tính
Bài giảng có sử dụng nguồn tài liệu cung cấp bởi trường ðại học Keio, Nhật Bản
2Tổng quan

 Tuần trước: Khái niệm chung về chọn
ñường.

 Chọn ñường tĩnh và chọn ñường ñộng

 Các giao thức chọn ñường

 Tuần này: Các giao thức chọn ñường cụ thể
trên Internet

 Vấn ñề phân cấp trong chọn ñường

 Chọn ñường nội vùng (Intra-domain): RIP, OSPF

 Chọn ñường liên vùng (Inter-domain): BGP
3Phân cấp trong chọn
ñường
Các hệ tự trị
Chọn ñường nội vùng
Chọn ñường liên vùng
4Tổng quan

 Vấn ñề chọn ñường ñã học
ñược xem xét trong ñiều kiện lý
tưởng

 Các nút mạng có vai trò như nhau

 Chỉ có một mạng duy nhất, mạng
“phẳng”

 Thực tế không giống như vậy

 Tính mở rộng: Internet có hàng triệu (tỷ) máy trạm, 
chọn ñường bằng LS hay DV?

 LS: Quá tải thông tin chọn ñường

 DV: Có hội tụ ñược không?
5Kiến trúc phân cấp của Internet
AS 1
AS 5
AS 4AS 3
AS 2

 Internet = Mạng của các mạng

 Mỗi mạng có thể lựa chọn riêng cho mình một chiến lược chọn
ñường riêng.

 Mỗi mạng như vậy có thể gọi là một hệ tự trị - Autonomous 
System (AS)
s1
Slide 5
s1 Combine 5 and 6
sonnh, 3/8/2008
6Khái niệm hệ tự trị - AS

 Tập hợp các nút mạng có cùng chính sách chọn ñường (Giao
thức, quy ước chi phí)

 Các ASes ñược nối kết thông qua các router hay gateway

 Mỗi hệ tự trị có một số hiệu riêng – AS number (ASN - 16 bits 
hay 32 bits).
2914 NTT-COMMUNICATIONS-2914 - NTT America, Inc. 
3491 BTN-ASN - Beyond The Network America, Inc.
4134 CHINANET-BACKBONE No.31,Jin-rong Street 
6453 GLOBEINTERNET Teleglobe America Inc. 
24087 VNGT-AS-AP Vietnam New Generation Telecom 
24066 VNNIC-AS-VN Vietnam Internet Network Information Center
17981 CAMBOTECH-KH-AS ISP Cambodia
.
Source: 
s2
Slide 6
s2 Explain about AS 
sonnh, 3/8/2008
7Số lượng ASN cấp phát bởi
IANA
Source: 
2008
8Phân cấp giao thức chọn
ñường

 Trong một hệ tự trị: Giao thức chọn ñường
nội vùng

 IGP: Interior Gateway Protocol

 RIP: Routing Information Protocol 

 OSPF: Open Shortest Path First

 IS-IS, IGRP, EIGRP (Cisco)

 Giữa các hệ tự trị: Giao thức chọn ñường
liên vùng

 EGP: Exterior Gateway Protocol

 BGP (v4): Border Gateway Protocol
9Intra-domain và Inter-domain 
routing
AS3
EGP
IGP
EGP
EGP
IGP
IGP
IGP
EGP
EGP
AS1
AS4
AS2
AS5 OSPF domainRIP domain
RIP domain
RIP domain
OSPF domain
RIP domain
10
Chọn ñường nội vùng
RIP
OSPF
11
RIP ( Routing Information Protocol)

 IGP

 RIP v.1, phiên bản mới RIP v.2

 Giao thức dạng vector khoảng cách

 Chọn ñường ñi theo số nút mạng ñi qua (# of hops, 
max = 15 hops)
DC
BA
u v
w
x
y
z
ðích ñến số nút
u 1
v 2
w 2
x 3
y 3
z 2
Từ nút A:
12

 Bạn của bạn là bạn
To 133.27.4.0/24
1 hop
Net A
133.27.4.0/24
Net B
133.27.5.0/24
Router A
Router Ｂ
Router Ｃ
Router D
Nhắc lại: Chọn ñường dạng DV (1)
13
Nhắc lại: Chọn ñường dạng DV (2)

 Bạn của bạn là bạn
To 133.27.4.0/24
1 hop
Net A
133.27.4.0/24
Net B
133.27.5.0/24
Router A
Router Ｂ
Router Ｃ
Router D
To 133.27.4.0/24
2 hop
To 133.27.4.0/24
2 hop
14
Nhắc lại: Chọn ñường dạng DV (3)

 Bạn của bạn là bạn
To 133.27.4.0/24
1 hop
Net A
133.27.4.0/24
Net B
133.27.5.0/24
Router A
Router Ｂ
Router Ｃ
Router D
To 133.27.4.0/24
2 hop
To 133.27.4.0/24
2 hop
To 133.27.4.0/24
3 hop
15
Nhắc lại: Chọn ñường dạng DV (4)

 Bạn của bạn là bạn
To 133.27.4.0/24
1 hop
Net A
133.27.4.0/24
Net B
133.27.5.0/24
Router A
Router Ｂ
Router Ｃ
Router D
To 133.27.4.0/24
2 hop
Lưu ý: Tên của router
s3
s4
Slide 15
s3 Explain in opposite way: How B is annouced
sonnh, 3/8/2008
s4 Expain that we announce networks address. not router id
sonnh, 3/8/2008
16
RIP: Trao ñổi thông tin

 Trao ñổi bảng chọn ñường

 ðịnh kỳ

 Các vector khoảng cách ñược trao ñổi ñịnh kỳ - 30s

 Mỗi thông ñiệp chứa tối ña 25 mục

 Trong thực tế, nhiều thông ñiệp ñược sử dụng

 Sự kiện

 Gửi thông ñiệp cho nút hàng xóm mỗi khi có thay ñổi

 Nút hàng xóm sẽ cập nhật bảng chọn ñường của nó
17
Các bộ ñếm thời gian - RIP 
timer (1)

 Update timer

 Dùng ñể trao ñổi thông tin cứ 30s

 Invalid timer

 Khởi tạo lại mỗi khi nhận ñược thông tin chọn ñường

 Nếu sau 180s không nhận ñược thông tin -> trạng thái hold-down

 Hold down timer

 Giữ trạng thái hold-down trong 180s

 Chuyển sang trạng thái down

 Flush timer

 Khởi tạo lại mỗi khi nhận ñược thông tin chọn ñường

 Sau 120s, xóa mục tương ứng trong bảng chọn ñường
18
RIP timer (2)
0 30 60 90 120 150 180 210 240 270 300 330 360 390 420
update
↓
update
↓
no
update
↓
Invalid timer
Hold down timer
Flush timer
When it is timeout,
hold down timer starts
When it is timeout,
Routing info will be deleted 
from routing table
When it is timeout,
This info will be deleted 
from RIP database
When it receives update,
Invalid timer restarts
19
Lỗi lặp vô hạn (Ping-pong 
failure)

 Nếu 192.168.0.0/24 bị lỗi

 B cập nhật thông tin về 192.168.0.0 cho A

 Các gói tin ñến 192.168.0.0/24 sẽ bị quẩn

 A cập nhật thông tin về 192.168.0.0 cho B

 Luẩn quẩn, vô hạn
192.168.0.0/24 192.168.1.0/24 192.168.2.0/24
192.168.0.0/24
192.168.1.0/24
192.168.1.0/24
192.168.2.0/24
conn
conn
conn
conn
A B
192.168.2.0/24 B 192.168.0.0/24 A
20
OSPF: ðể tranh lỗi lặp vô hạn

 Giới hạn số hop tối ña

 16

 “Split horizon”

 Thông tin chọn ñường không ñược quay về nút
nguồn

 “Poison reverse”

 Khi liên kết bị lỗi, gửi giá trị của chi phí là 16

 Liên kết chuyển sang trạng thái hold-down
s6
Slide 20
s6 16 TTL vs. this? 
sonnh, 3/8/2008
21
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
s7
Slide 21
s7 Tittle slide
sonnh, 3/8/2008
22
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)
23
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
s9
Slide 23
s9 Explain why we need to reduce the calculaiton
sonnh, 3/8/2008
24
Phân cấp OSPF
25
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
26
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 2050
27
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
28
Chi phí mặc ñịnh của OSPF
1Gigabit Ethernet / 10G network
1FDDI or Fast Ethernet
616Mbps Token Ring
10Ethernet
254Mbps Token Ring
48E1 (2.048Mbps) serial link
65T1 (1.544Mbps) serial link
156264Kbps serial link
178556Kbps serial link
Default OSPF costLink Bandwidth
29
Quảng bá thông tin LSA
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
s8
Slide 29
s8 What information is flood
sonnh, 3/8/2008
30
Router ñại diện - DR

 ðể tăng hiệu quả của việc quảng bá LSA

 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?
A
ED
CB
Không có DR
A
ED
CB
Có DR
31
Neighbor & Adjacency

 “Neighbor” và “adjacency” là các k/n khác nhau!

 Adjacency: có trao ñổi thông tin

 Neighbor: có ñường nối trực tiếp

 Mạng quảng bá ña truy cập (e.g Ethernet)

 Neighbor != Adjacency

 Mạng ñiểm-nối-ñiểm

 Neighbor == Adjacency
s10
Slide 31
s10 Chang the order 
sonnh, 3/8/2008
32
RIP vs. OSPF
Trạng thái liên kếtBảng chọn ñườngTrao ñổi thông tin
Băng thôngSố nút mạngðơn vị chi phí
10s (Hello packet)30sCập nhật hàng xóm
Link-stateDistant vectorGiải thuật
NhanhChậmHội tụ
LớnNhỏðộ phức tạp tính toán
oxKhả năng mở rộng
• Phân câp
• Cấu hình phức tạp
• Mạng cỡ vừa và lớn
• Router bình ñẳng
• Cấu hình dễ dàng
• Mạng cỡ nhỏ
ðặc ñiểm
OSPFRIP
s11
Slide 32
s11 Exchanged informatio
Rip:
OSPF
sonnh, 3/8/2008
33
Giao thức chọn ñường liên vùng
34
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 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
35
BGP: Path vector routing

 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: Chọn ñường theo path-vector
A B C
ED
A
A
D→A
A
B→A
A
C→B→A
A
A
D→A best path
C→B→A ×
4
1
1
2
2
3
s12
Slide 35
s12 Change the symbol of router into AS
sonnh, 2/29/2008
36
Cơ chế tránh vòng lặp

 Dò lại xem router đã có trên path-vector hay chưa

 B hủy ñường ñi tới A
A
B
C
D
A
C→B→A
!!LOOP!!
A
D→C→B→A
37
eBGP và iBGP

 External BGP vs. Internal BGP

 Phân tán thông tin chọn ñường
1. 3a gửi tới 1c bằng
2. 1c gửi thông tin nội bộ tới (1b, 1d, ) trong AS1 bằng iBGP
3. 2a nhận thông tin từ 1b bằng eBGP
3b
1d
3a
1c
2aAS3
AS1
AS2
1a
2c
2b
1b
3c
eBGP session
iBGP session
s13
Slide 37
s13 - We have to explain why we have two kind of BGP
(Or we ask student)
- iBGP: internal
-e: external
sonnh, 2/29/2008
38
BGP có thể cài ñặt các policy 

 Khi các router gửi và nhận thông tin chọn
ñường

 BGP có thể ñặt các chinh sách

 Cho ñường vào

 Cho ñường ra
39
Các thuộc tính của ñường ñi

 ORIGIN 

 Nguồn của thông tin (IGP/EGP/incomplete) 

 AS_PATH

 NEXT_HOP

 MED (MULTI_EXIT_DISCRIMINATOR) 

 LOCAL_PREF

 ATOMIC_AGGREGATE

 AGGREGATOR 

 COMMUNITY 
s15
Slide 39
s15 Add a new slide to explain about policy
Explain only attributes here
and then, explain the step 
Put the slide 103 of Keio slide just be fore slide about policy: howto implement policy
Add AS prepend just after filtering
and others come following
sonnh, 2/29/2008
40
Các bước chọn ñường ñi

 Bước 1: NEXT_HOP?

 Bước 2: So sánh LOCAL_PREF

 Bước 3: So sánh ñộ dài AS_PATH

 Bước 4: So sánh ORIGIN 

 Bước 5: So sánh MED 

 Bước 6: So sánh EBGP/IBGP

 Bước 7: So sánh chi phí tới NEXT_HOP

 Bước 8: So sánh Router ID 
s14
Slide 40
s14 Priority of route selection
sonnh, 2/29/2008
41
Cài ñặt cac chính sách ntn? 

 Bộ lọc

 Các thuộc tính

 AS_PATH PREPEND

 MED 

 LOCAL_PREF
42
Bộ lọc

 Chỉ trao ñổi ñường ñi nào ñã ñược ñăng ký

 Hạn chế thông qua bộ lọc vào - In-filter

 Thông qua bộ lọc ra - Out-filter
AS1
AS2
AS3
AS4
AS1 AS3
Example of setting Access List
ip as-path access-list 10 permit ^2$
ip as-path access-list 10 permit ^2 1$
Setting as “In-filter” on BGP router
AS2 ◎
AS2 AS1 ◎
AS2 AS3 × Do not receive
s16
Slide 42
s16 Move just after policy
sonnh, 2/29/2008
43
Ví dụ về AS PATH
Network Next Hop Metric LocPrf Weight Path
4.79.201.0/26 203.178.136.29 700 500 0 7660 22388 11537 10886 40220 
203.178.136.29 700 500 0 7660 22388 11537 10886 40220
203.178.136.29 700 500 0 7660 22388 11537 10886 40220 
6.1.0.0/16 203.178.136.29 700 500 0 7660 22388 11537 668 
203.178.136.29 700 500 0 7660 22388 11537 668 
203.178.136.29 700 500 0 7660 22388 11537 668 
6.2.0.0/22 203.178.136.29 700 500 0 7660 22388 11537 668
44
Chọn ñường với AS_PATH 
Prepend
AS1
AS2
AS3
AS5
AS4
AS5 AS5 AS5
AS4 AS5 AS5 AS5
AS5
AS3 AS5
AS2 AS3 AS5
45
Ví dụ về AS PATH prepend
Network Next Hop Metric LocPrf Weight Path
8.5.192.0/22 203.178.136.14 100 0 2516 209 13989 13989 13989 13989
203.178.136.14 100 0 2516 209 13989 13989 13989 13989
203.178.136.14 100 0 2516 209 13989 13989 13989 13989
8.5.196.0/24 203.178.136.14 100 0 2516 209 13989 13989 13989 13989
203.178.136.14 100 0 2516 209 13989 13989 13989 13989
203.178.136.14 100 0 2516 209 13989 13989 13989 13989
8.5.200.0/22 203.178.136.14 100 0 2516 209 13989 13989 13989 13989
203.178.136.14 100 0 2516 209 13989 13989 13989 13989
46
Chon ñường với MED

 trong trường hợp 2 AS với nhiều link

 Chọn MED nhỏ hơn

 Áp dụng trong ñiều khiển lưu lượng
172.16.0.0/16
AS1
AS2
Routing information 
of AS1
MED 100
Routing information of 
AS1
MED 200
How to see routing table at AS2
Prefix AS_PATH MED
172.16.0.0/16 AS1 100 ◎
172.16.0.0/16 AS1 200
used route
s17
Slide 46
s17 MED is set by distance AS
Local-pref set by local AS
so local-pre is higher 
sonnh, 2/29/2008
47
Phân tải với MED

 ðặt giá trị MED khác nhau cho mỗi ñường

 Cũng ñiều khiển lưu lượng
172.16.0.0/16、172.17.0.0/16
AS1
AS2
Routing information of AS1
172.16.0.0/16 = MED 200
172.17.0.0/16 = MED 100
Route used for 
172.16.0.0/16
Routing information of AS1
172.16.0.0/16 = MED 100
172.17.0.0/16 = MED 200
Route used for 
172.17.0.0/16
48
Sử dụng LOCAL_PREF

 Chọn giá trị lớn hơn của
LOCAL_PREF

 ðiểu khiển lưu lượng
upbound
AS1
AS2
AS3
AS5
AS4
AS1 AS4
AS1
AS3 AS2 AS1
AS1 AS2
AS1
LOCAL_PREF 100 LOCAL_PREF 80
49
Tóm tắt

 Hierarchical routing

 RIP

 OSPF

 BGP
50
Tuần tới: Transport Layer

 Nguyên lý tầng giao vận

 UDP và TCP

 ðiều khiển luồng

 ðiều khiển tắc nghẽn