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 tồn AS s7 Slide 21 s7 Tittle slide sonnh, 3/8/2008 22 Một số đặc điểm của OSPF
An tồ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 tố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 tố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 tố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