Chươ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
1
Tổng quan
(cid:1) Tuần trước: Khái niệm chung về chọn
ñường. (cid:1) Chọn ñường tĩnh và chọn ñường ñộng (cid:1) Các giao thức chọn ñường
(cid:1) Tuần này: Các giao thức chọn ñường cụ thể
trên Internet (cid:1) Vấn ñề phân cấp trong chọn ñường (cid:1) Chọn ñường nội vùng (Intra-domain): RIP, OSPF (cid:1) Chọn ñường liên vùng (Inter-domain): BGP
2
Phâ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
3
Tổng quan
(cid:1) Vấn ñề chọn ñường ñã học
ñược xem xét trong ñiều kiện lý tưởng (cid:1) Các nút mạng có vai trò như nhau (cid:1) Chỉ có một mạng duy nhất, mạng
“phẳng”
(cid:1) Thực tế không giống như vậy
(cid:1) Tính mở rộng: Internet có hàng triệu (tỷ) máy trạm,
chọn ñường bằng LS hay DV? (cid:1) LS: Quá tải thông tin chọn ñường (cid:1) DV: Có hội tụ ñược không?
4
s1
Kiến trúc phân cấp của Internet
(cid:1) Internet = Mạng của các mạng (cid:1) 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.
(cid:1) Mỗi mạng như vậy có thể gọi là một hệ tự trị - Autonomous
System (AS)
AS 2
AS 5
AS 1
AS 4
AS 3
5
Slide 5
s1 Combine 5 and 6 sonnh, 3/8/2008
s2
Khái niệm hệ tự trị - AS
(cid:1) 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í…)
(cid:1) Các ASes ñược nối kết thông qua các router hay gateway (cid:1) 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: http://www.cidr-report.org
6
Slide 6
s2 Explain about AS sonnh, 3/8/2008
Số lượng ASN cấp phát bởi IANA
Source: http://www.potaroo.net/
2008
7
Phân cấp giao thức chọn ñường
(cid:1) Trong một hệ tự trị: Giao thức chọn ñường
nội vùng (cid:1) IGP: Interior Gateway Protocol
(cid:1) RIP: Routing Information Protocol (cid:1) OSPF: Open Shortest Path First (cid:1) IS-IS, IGRP, EIGRP (Cisco)…
(cid:1) Giữa các hệ tự trị: Giao thức chọn ñường
liên vùng (cid:1) EGP: Exterior Gateway Protocol
(cid:1) BGP (v4): Border Gateway Protocol
8
Intra-domain và Inter-domain routing
AS2
AS1
IGP
EGP
OSPF domain
EGP
EGP
RIP domain
EGP
IGP
AS4
EGP
AS3
IGP
RIP domain
IGP
OSPF domain
AS5
RIP domain
RIP domain
9
Chọn ñường nội vùng
RIP OSPF
10
RIP ( Routing Information Protocol)
(cid:1) IGP (cid:1) RIP v.1, phiên bản mới RIP v.2 (cid:1) Giao thức dạng vector khoảng cách (cid:1) Chọn ñường ñi theo số nút mạng ñi qua (# of hops,
max = 15 hops)
Từ nút A:
u
v
w
A
B
x
ðích ñến số nút u 1 v 2 w 2 x 3 y 3 z 2
D
C
z
y
11
Nhắc lại: Chọn ñường dạng DV (1)
(cid:1) Bạn của bạn là bạn
Net A 133.27.4.0/24
Router Ｃ
Router A
To 133.27.4.0/24 1 hop
Net B 133.27.5.0/24
Router Ｂ
Router D
12
Nhắc lại: Chọn ñường dạng DV (2)
(cid:1) Bạn của bạn là bạn
Net A 133.27.4.0/24
Router Ｃ
Router A
To 133.27.4.0/24 2 hop
To 133.27.4.0/24 1 hop
Net B 133.27.5.0/24
Router Ｂ
Router D
13
To 133.27.4.0/24 2 hop
Nhắc lại: Chọn ñường dạng DV (3)
(cid:1) Bạn của bạn là bạn
Net A 133.27.4.0/24
Router Ｃ
Router A
To 133.27.4.0/24 2 hop
To 133.27.4.0/24 3 hop
To 133.27.4.0/24 1 hop
Net B 133.27.5.0/24
Router Ｂ
Router D
14
To 133.27.4.0/24 2 hop
s3
s4
Nhắc lại: Chọn ñường dạng DV (4)
(cid:1) Bạn của bạn là bạn
Lưu ý: Tên của router
Net A 133.27.4.0/24
Router Ｃ
Router A
To 133.27.4.0/24 1 hop
Net B 133.27.5.0/24
Router Ｂ
Router D
15
To 133.27.4.0/24 2 hop
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
RIP: Trao ñổi thông tin
(cid:1) Trao ñổi bảng chọn ñường (cid:1) ðịnh kỳ
(cid:1) Các vector khoảng cách ñược trao ñổi ñịnh kỳ - 30s (cid:1) Mỗi thông ñiệp chứa tối ña 25 mục (cid:1) Trong thực tế, nhiều thông ñiệp ñược sử dụng
(cid:1) Sự kiện
(cid:1) Gửi thông ñiệp cho nút hàng xóm mỗi khi có thay ñổi (cid:1) Nút hàng xóm sẽ cập nhật bảng chọn ñường của nó
16
Các bộ ñếm thời gian - RIP timer (1)
(cid:1) Update timer
(cid:1) Dùng ñể trao ñổi thông tin cứ 30s
(cid:1) Invalid timer
(cid:1) Khởi tạo lại mỗi khi nhận ñược thông tin chọn ñường (cid:1) Nếu sau 180s không nhận ñược thông tin -> trạng thái hold-down
(cid:1) Hold down timer
(cid:1) Giữ trạng thái hold-down trong 180s (cid:1) Chuyển sang trạng thái down
(cid:1) Flush timer
(cid:1) Khởi tạo lại mỗi khi nhận ñược thông tin chọn ñường (cid:1) Sau 120s, xóa mục tương ứng trong bảng chọn ñường
17
RIP timer (2)
When it is timeout, hold down timer starts
Invalid timer
When it is timeout, This info will be deleted from RIP database
Hold down timer
When it receives update, Invalid timer restarts
Flush timer
When it is timeout, Routing info will be deleted from routing table
update ↓ update ↓ no update ↓
0 30 60 90 120 150 180 210 240 270 300 330 360 390 420 18
Lỗi lặp vô hạn (Ping-pong failure)
(cid:1) Nếu 192.168.0.0/24 bị lỗi…
(cid:1) B cập nhật thông tin về 192.168.0.0 cho A (cid:1) Các gói tin ñến 192.168.0.0/24 sẽ bị quẩn (cid:1) A cập nhật thông tin về 192.168.0.0 cho B
(cid:1) Luẩn quẩn, vô hạn
192.168.0.0/24 192.168.1.0/24 192.168.2.0/24
conn conn B
192.168.1.0/24 192.168.2.0/24 192.168.0.0/24
conn conn A
A
B
192.168.0.0/24
192.168.1.0/24
19 192.168.2.0/24
s6
OSPF: ðể tranh lỗi lặp vô hạn
(cid:1) Giới hạn số hop tối ña
(cid:1) 16
(cid:1) “Split horizon”
(cid:1) Thông tin chọn ñường không ñược quay về nút
nguồn
(cid:1) “Poison reverse”
(cid:1) Khi liên kết bị lỗi, gửi giá trị của chi phí là 16 (cid:1) Liên kết chuyển sang trạng thái hold-down
20
Slide 20
s6 16 TTL vs. this? sonnh, 3/8/2008
s7
OSPF: Open Shortest Path First
(cid:1) IGP (cid:1) Open: Chuẩn mở của IETF (phiên bản 3,
ñịnh nghĩa trong RFC 2740)
(cid:1) Shortest Path First: Cài ñặt giải thuật Dijkstra. (cid:1) 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
21
Slide 21
s7 Tittle slide sonnh, 3/8/2008
Một số ñặc ñiểm của OSPF
(cid:1) An toàn: thông ñiệp OSPF ñược bảo vệ (cid:1) Với các AS lớn: OSPF phân cấp (cid:1) ðịa chỉ không phân lớp (Variable-Length
Subnet Masking -VLSM )
(cid:1) 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)
22
s9
Phân cấp OSPF
(cid:1) Trong việc chọn ñường, tại sao phải chia mạng
thành các vùng nhỏ hơn?
(cid:1) Nếu có quá nhiều router
(cid:1) Thông tin trạng thái liên kết ñược truyền nhiều lần hơn (cid:1) Phải liên tục tính toán lại (cid:1) Cần nhiều bộ nhớ hơn, nhiều tài nguyên CPU hơn (cid:1) Lượng thông tin phải trao ñổi tăng lên (cid:1) Bảng chọn ñường lớn hơn
(cid:1) Vùng
(cid:1) Nhóm các router có cùng thông tin LSA
23
Slide 23
s9 Explain why we need to reduce the calculaiton sonnh, 3/8/2008
Phân cấp OSPF
24
Các dạng router
(cid:1) ABR - Area border routers: Quản lý 1 vùng và
kết nối ñến các vùng khác
(cid:1) ASBR - Autonomous system boundary
router: Nối ñến các AS khác
(cid:1) BR - backbone routers: thực hiện OSPF
routing trong vùng backbone
(cid:1) Internal Router – Thực hiện OSPF bên trong
một vùng
25
Thông tin chọn ñường?
(cid:1) 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
(cid:1) Ví dụ: nút A
A
20
D
C
10
(cid:1) link to B, cost 30 (cid:1) link to D, cost 20 (cid:1) link to C, cost 10
20
50
30
(cid:1) Ví dụ: nút D
B
E
(cid:1) link to A, cost 20 (cid:1) link to E, cost 20 (cid:1) link to C, cost 50
26
Chi phí trong giao thức OSPF - metric
(cid:1) Giá trị mặc ñịnh
100Mbps / bandwidth of interface (cid:1) Hiện nay người quản trị có thể gán giá trị này
(cid:1) Khi tính toán bảng chọn ñường (cid:1) Chọn ñường ñi chi phí nhỏ nhất
(cid:1) Chi phí bằng nhau
(cid:1) Có thể thực hiện cân bằng tải
27
Chi phí mặc ñịnh của OSPF
Link Bandwidth
Default OSPF cost
56Kbps serial link
1785
64Kbps serial link
1562
T1 (1.544Mbps) serial link
65
E1 (2.048Mbps) serial link
48
4Mbps Token Ring
25
Ethernet
10
16Mbps Token Ring
6
FDDI or Fast Ethernet
1
Gigabit Ethernet / 10G network
1
28
s8
Quảng bá thông tin LSA
LSAX
LSAX
X
A
X
A
X has link to A, cost 10
LSAX
X has link to C, cost 20
C
B
D
C
B
D
(a)
(b)
X
A
X
A
LSAX
C
B
LSAX D
C
B
D
LSAX
(d)
(c)
29
Slide 29
s8 What information is flood sonnh, 3/8/2008
Router ñại diện - DR
(cid:1) ðể tăng hiệu quả của việc quảng bá LSA (cid:1) Mỗi router phải lập quan hệ với router ñại diện -
designated router (DR) (cid:1) Trao ñổi thông tin thông qua DR
(cid:1) DR dự phòng (cid:1) Chọn DR và BDR?
B
A
C
B
A
C
D
E
D
E
Có DR
Không có DR
30
s10
Neighbor & Adjacency
(cid:1) “Neighbor” và “adjacency” là các k/n khác nhau!
(cid:1) Adjacency: có trao ñổi thông tin (cid:1) Neighbor: có ñường nối trực tiếp
(cid:1) Mạng quảng bá ña truy cập (e.g Ethernet)
(cid:1) Neighbor != Adjacency
(cid:1) Mạng ñiểm-nối-ñiểm
(cid:1) Neighbor == Adjacency
31
Slide 31
s10 Chang the order sonnh, 3/8/2008
s11
RIP vs. OSPF
RIP
OSPF
ðặc ñiểm
• 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ỏ
Khả năng mở rộng
x
o
ðộ phức tạp tính toán
Nhỏ
Lớn
Nhanh
Hội tụ
Chậm
Bảng chọn ñường
Trạng thái liên kết
Trao ñổi thông tin
Distant vector
Link-state
Giải thuật
30s
10s (Hello packet)
Cập nhật hàng xóm
ðơn vị chi phí
Số nút mạng
Băng thông
32
Slide 32
s11
Exchanged informatio Rip: OSPF sonnh, 3/8/2008
Giao thức chọn ñường liên vùng
33
BGP – Border Gateway Protocol
(cid:1) Yếu tố gắn kết của Internet, kết nối các hệ tự trị (cid:1) Trao ñổi thông tin NLRI (Network Layer Reachability
Information) (cid:1) Cho phép một AS biết ñược thông tin ñi ñến AS khác (cid:1) Gửi thông tin này vào bên trong AS ñó (cid:1) 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
(cid:1) Cho phép thiết lập các chính sách
(cid:1) Chọn ñường ra (cid:1) Quảng bá các ñường vào
34
s12
BGP: Path vector routing
(cid:1) Giữa các AS nên dùng giao thức nào?
(cid:1) Khó có một chính sách và ñơn vị chi phí chung (cid:1) LS: Chi phí không ñồng nhất, CSDL quá lớn (cid:1) DV: Mạng quá rộng, khó hội tụ
(cid:1) Giải pháp: Chọn ñường theo path-vector
1
2
A
A B→A
A
C
B
3
A C→B→A
1
A
D
E
2
4
A D→A
A D→A best path × C→B→A
35
Slide 35
s12 Change the symbol of router into AS sonnh, 2/29/2008
Cơ chế tránh vòng lặp
(cid:1) Dò lại xem router đã có trên path-vector hay chưa
(cid:1) B hủy ñường ñi tới A
B
C
A
!!LOOP!! A D→C→B→A
A C→B→A
D
36
s13
eBGP và iBGP
(cid:1) External BGP vs. Internal BGP (cid:1) 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
eBGP session
3c
iBGP session
2c
3a
3b
2a
AS3
2b
1c
AS2
1b
1d
1a AS1
37
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
BGP có thể cài ñặt các policy
(cid:1) Khi các router gửi và nhận thông tin chọn
ñường (cid:1) BGP có thể ñặt các chinh sách
(cid:1) Cho ñường vào (cid:1) Cho ñường ra
38
s15
Các thuộc tính của ñường ñi
(cid:1) ORIGIN
(cid:1) Nguồn của thông tin (IGP/EGP/incomplete)
(cid:1) AS_PATH (cid:1) NEXT_HOP (cid:1) MED (MULTI_EXIT_DISCRIMINATOR) (cid:1) LOCAL_PREF (cid:1) ATOMIC_AGGREGATE (cid:1) AGGREGATOR (cid:1) COMMUNITY
39
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
s14
Các bước chọn ñường ñi
(cid:1) Bước 1: NEXT_HOP? (cid:1) Bước 2: So sánh LOCAL_PREF (cid:1) Bước 3: So sánh ñộ dài AS_PATH (cid:1) Bước 4: So sánh ORIGIN (cid:1) Bước 5: So sánh MED (cid:1) Bước 6: So sánh EBGP/IBGP (cid:1) Bước 7: So sánh chi phí tới NEXT_HOP (cid:1) Bước 8: So sánh Router ID
40
Slide 40
s14 Priority of route selection sonnh, 2/29/2008
Cài ñặt cac chính sách ntn?
(cid:1) Bộ lọc (cid:1) Các thuộc tính
(cid:1) AS_PATH PREPEND (cid:1) MED (cid:1) LOCAL_PREF
41
s16
Bộ lọc
(cid:1) Chỉ trao ñổi ñường ñi nào ñã ñược ñăng ký
(cid:1) Hạn chế thông qua bộ lọc vào - In-filter (cid:1) Thông qua bộ lọc ra - Out-filter
AS1
AS3
AS1
AS3
AS2
Example of setting Access List ip as-path access-list 10 permit ^2$ ip as-path access-list 10 permit ^2 1$
Do not receive
AS2 ◎ AS2 AS1 ◎ AS2 AS3 ×
AS4
Setting as “In-filter” on BGP router
42
Slide 42
s16 Move just after policy sonnh, 2/29/2008
Ví dụ về AS PATH
Network 4.79.201.0/26
6.1.0.0/16
6.2.0.0/22
Next Hop Metric LocPrf Weight Path 203.178.136.29 700 500 0 203.178.136.29 700 500 0 203.178.136.29 700 500 0 203.178.136.29 700 500 0 203.178.136.29 700 500 0 203.178.136.29 700 500 0 203.178.136.29 700 500 0
7660 22388 11537 10886 40220 7660 22388 11537 10886 40220 7660 22388 11537 10886 40220 7660 22388 11537 668 7660 22388 11537 668 7660 22388 11537 668 7660 22388 11537 668
43
Chọn ñường với AS_PATH Prepend
AS2 AS3 AS5
AS4 AS5 AS5 AS5
AS1
AS2
AS3 AS5
AS4
AS3
AS5 AS5 AS5
AS5
AS5
44
Ví dụ về AS PATH prepend
Network 8.5.192.0/22
8.5.196.0/24
8.5.200.0/22
Next Hop Metric LocPrf Weight Path 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 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 203.178.136.14 100 0 2516 209 13989 13989 13989 13989 203.178.136.14 100 0 2516 209 13989 13989 13989 13989
45
s17
Chon ñường với MED
(cid:1) trong trường hợp 2 AS với nhiều link (cid:1) Chọn MED nhỏ hơn (cid:1) Áp dụng trong ñiều khiển lưu lượng
172.16.0.0/16 AS1
used route
Routing information of AS1 MED 100
Routing information of AS1 MED 200
How to see routing table at AS2
AS2
Prefix AS_PATH MED 172.16.0.0/16 AS1 100 ◎ 46 172.16.0.0/16 AS1 200
Slide 46
s17
MED is set by distance AS Local-pref set by local AS so local-pre is higher sonnh, 2/29/2008
Phân tải với MED
(cid:1) ðặt giá trị MED khác nhau cho mỗi ñường (cid:1) Cũng ñiều khiển lưu lượng
172.16.0.0/16、、、、172.17.0.0/16 AS1
Routing information of AS1 172.16.0.0/16 = MED 100 172.17.0.0/16 = MED 200
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
Route used for 172.17.0.0/16
AS2
47
Sử dụng LOCAL_PREF
(cid:1) Chọn giá trị lớn hơn của
AS1
AS1
AS1
LOCAL_PREF
(cid:1) ðiểu khiển lưu lượng
upbound
AS2
AS1 AS2
AS4
AS3
AS1 AS4
AS3 AS2 AS1
LOCAL_PREF 100
LOCAL_PREF 80
AS5
48
Tóm tắt
(cid:1) Hierarchical routing (cid:1) RIP (cid:1) OSPF (cid:1) BGP
49
Tuần tới: Transport Layer
(cid:1) Nguyên lý tầng giao vận (cid:1) UDP và TCP (cid:1) ðiều khiển luồng (cid:1) ðiều khiển tắc nghẽn
50
