Hệ tự trị
Tìm đường nội vùng
Tìm đường liên vùng
Hệ tự trị
(Autonomous System)
• Vấn đề tìm đường trong một liên mạng lớn có rất nhiều mạng
• Internet là mạng của các mạng
• Các giải thuật áp dụng với mạng lớn có khó khăn
• Mỗi mạng có thể có chiến lược tìm đường riêng
• Mỗi mạng có chiến lược tìm đường riêng hình thành một Autonomous System
58 trang |
Chia sẻ: candy98 | Lượt xem: 810 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Bài giảng Mạng máy tính - Chương 9: Giao thức định tuyến - Nguyễn Hồng Sơn, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
GIAO THỨC ĐỊNH TUYẾN
CHƯƠNG 9
TI M ĐƯỜNG PHÂN CÂ P
• Hê tự tri
• Tim đường nôi vung
• Tim đường liên vung
Hê tự tri
(Autonomous System)
• Vâ n đê ti m đường trong mô t liên ma ng lớn co râ t
nhiê u ma ng
• Internet la ma ng cu a ca c ma ng
• Ca c gia i thuâ t a p du ng với ma ng lớn co kho khăn
• Mô i ma ng co thê co chiê n lược ti m đường riêng
• Mô i ma ng co chiê n lược ti m đường riêng hi nh
tha nh mô t Autonomous System
Hê tự tri (tt)
• Ca c nu t ma ng trong mô t AS co cu ng chi nh
sa ch ti m đường
• Ca c AS được kê t nô i với nhau qua ca c router
hay gateway
• Mô i AS co sô hiê u riêng go i la ASN, co chiê u
da i 16 hay 32 bit.
Kiê n tru c phân câ p cu a Internet
Phân câ p giao thức ti m đường
• Trong mô t AS: Giao thức ti m đường nô i vu ng;
Intra-AS Routing còn gọi là IGP (Interior
Gateway Protocol)
– RIP: Routing Information Protocol
– OSPF: Open Shortest Path First
– IS-IS, IGRP, EIGRP...
• Giữa ca c AS: Giao thức ti m đường liên vu ng,
Inter-AS Routing còn gọi là EGP (Exterior
Gateway Protocol)
– BGPv4 (Border Gateway Protocol)
Lý do có sự phân biệt định tuyến nội vùng
và liên vùng (Intra và Inter-AS routing)
Chính sách:
• Inter-AS cần điều khiển: định tuyến lưu lượng như thế
nào và chủ thể nào thực hiện định tuyến qua mạng .
• Intra-AS: không cần các quyết định về chính sách
Tính mở rộng:
• Định tuyến phân cấp giảm kích thước bảng cũng như
lưu lượng định tuyến
Hiệu năng:
• Intra-AS: có thể tập trung vào hiệu năng
• Inter-AS: chính sách là ưu tiên hơn
MỘT SỐ GIAO THỨC
r RIP
rOSPF
r BGP
RIP: Các phiên bản
r RIPv1 được đặc tả trong RFC 1058, thuộc
dạng định tuyến distance vector
r RIPv2 được đặc tả trong RFC 2453, khắc
phục một số hạn chế của RIPv1 và hỗ trợ xác
thực.
RIP: Hoạt động căn bản
r Các Node xây dựng các bảng định tuyến bằng cách
lấy thông tin từ các thông điệp đáp ứng (RIP
response messages)
m response messages chứa danh sách các distance vectors
r Khi tìm thấy một tuyến ngắn hơn, sẽ thay giá trị cũ
trong bảng định tuyến.
m Các khoảng cách bằng vẫn giữ nguyên để tiết kiệm thời gian
xử lý.
RIP:Ví dụ
Destination Network Next Router Số chặng (hop) tới đích
w A 2
y B 2
z B 7
x -- 1
. . ....
w x y
z
A
C
D B
Routing/Forwarding table trong D
RIP: Ví dụ
Destination Network Next Router Số chặng (hop) tới đích
w A 2
y B 2
z B A 7 5
x -- 1
. . ....
Routing/Forwarding table trong D
w x y
z
A
C
D B
Dest Next hops
w - 1
x - 1
z C 4
. ...
Advertisement
từ A đến D
Các loại gói RIP
r Trong định dạng có trường command để ký hiệu cho
một trong hai loại gói: request message hay
response message
r Request được truyền bởi các router sau khi có
timeout hay thông tin bị lạc hậu.
r Response được truyền để đáp ứng cho một yêu cầu,
cũng được truyền theo qui định của giao thức
m response message thường chứa danh sách các vector
khoảng cách.
Sử dụng RIP Response message
r Được gửi:
m Đáp ứng một request
m Định kỳ
• Đặc tả RIP chỉ ra rằng nên thông báo về vector khoảng
cách mỗi 30 giây một lần.
m Khi có thể đổi
• Nếu một láng giềng hay liên kết trực tiếp có thay đổi (ví
dụ bị hỏng), một response được gửi cho các tất cả các
node láng giềng để cập nhật.
Danh sách vector khoảng cách
(Distance Vector)
r Mỗi gói RIP response có thể chứa đến 25
DV
r Gồm 3 phần:Contain 3 parts:
m Address family ID: mô tả loại địa chỉ
được chỉ định
m Address: địa chỉ của node mà vector
khoảng cách đề cập
m Metric: khoảng cách tính theo metric (ví
dụ tính theo chặng (hop count), mặc định
15 hop, 16 hop được xem như giá trị vô
cùng lớn)
r Một vùng lớn dành cho địa chỉ (14 octet)
có thể được sử dụng theo nhiều cách
khác nhau.
m Ví dụ trong mạng IP có thể đặt 4 octet
địa chỉ sau 2 octet trống.
command
version
reserved
address family ID
address
metric
1
1
2
2
14
4
Một vector, có thể có
nhiều vector
octets
RIP: liên kết hỏng và phục hồi
Nếu không thấy quảng cáo sau 180 giây thì xem như liên
kết/láng giềng đã tắt
m Tất cả qua láng giềng đó là bất hợp lệ
m Các quảng cáo mới được gửi đến các láng giềng
m Đến lượt các láng giềng lại gửi quảng cáo mới (nếu có
thay đổi)
m Thông tin liên kết hỏng lan truyền nhanh chóng qua
toàn mạng
Xử lý RIP Table
r Các RIP routing table được quản lý bởi quá trình
mức ứng dụng được gọi là route-d (daemon)
r Các quảng cáo được truyền đi trong các gói UDP, lặp
lại theo định kỳ
physical
link
network forwarding
(IP) table
Transport
(UDP)
Route-d
physical
link
network
(IP)
Transport
(UDP)
Route-d
forwarding
table
Trở ngại phát sinh trong DV Routing :
Ví dụ (1/5)
r Xem xét mạng đơn giản sau:
BA C
12C
11B
PortDistDest
21C
11A
PortDistDest
11B
12A
PortDistDest
1 1 12
r Điều gì xảy ra nếu liên kết BC bị hỏng?
r B nhận biết và cố gắng tìm đường khác đến C
BA C
12C
11B
PortDistDest
21C
11A
PortDistDest
11B
12A
PortDistDest
1 1 12
X
Trở ngại phát sinh trong DV Routing :
Ví dụ (2/5)
Trở ngại phát sinh trong DV Routing :
Ví dụ (3/5)
r B sẽ hỏi A liệu có tuyến nào đến C không
r A sẽ đáp ứng?
m Dò bảng định tuyến và trả lời
BA C
12C
11B
PortDistDest
11A
??C
PortDistDest
1 1 12
X
Trở ngại phát sinh trong DV Routing :
Ví dụ (4/5)
r A cho rằng có thể đến C qua hai chặng và trả lời cho
B, đường đó lại qua B nhưng A không biết đây là điều
bất hợp lý.
r B lấy thông tin này và cập nhật bảng với thông tin có
thể đến C qua 3 hop
BA C
12C
11B
PortDistDest
13C
11A
PortDistDest
1 1 12
X
Trở ngại phát sinh trong DV Routing :
Ví dụ (5/5)
r Giả sử B có datagram cần gửi cho C:
m B dựa vào bảng định tuyến gửi sang A
m A sau đó sẽ gửi trở lại B
m A và B sẽ gửi datagram này qua lại, gọi là xuất hiện hiện
tượng định tuyến lặp (routing loop)
BA C
12C
11B
PortDistDest
13C
11A
PortDistDest
1 1 12
X
Đếm vô hạn (Count to Infinity)
(1/7)
r Ví dụ một tuyến hướng đến host D (đích)
D R1 R2 NetworkR3
Đếm vô hạn (Count to Infinity)
(2/7)
r Điều gì xảy ra nếu liên kết giữa R1 và D
hỏng?
m R1 sẽ phát hiện và tìm kiếm tuyến khác
D R1 R2 NetworkR3X
Đếm vô hạn (Count to Infinity)
(3/7)
r R2 sẽ quảng cáo rằng nó có một tuyến đến D (với
distance = 2 hop)
m R1 không nhận thức được tuyến này thông qua chính nó và
bất hợp lý
m Vì chỉ quảng cáo khoảng cách (không phải trạng thái liên
kết) do đó không có cách gì để R1 biết R2 không có tuyến
nào đến D.
D R1 R2 NetworkR3
?
Đếm vô hạn (Count to Infinity)
(4/7)
r R1 sẽ cập nhật thông tin định tuyến đến D qua R2
m Khoảng cách tăng lên 3 (2+1)
m Một distance vector mới lại gửi đến R2
D R1 R2 NetworkR3
?
D 3
Đếm vô hạn (Count to Infinity)
(5/7)
r R2 sẽ cập nhật bảng định tuyến với tuyến đến D qua
R1
m Khoảng cách tăng lên 4 (3+1)
m Distance vector mới được gửi đến R1
D R1 R2 NetworkR3
?
D 4
Đếm vô hạn (Count to Infinity)
(6/7)
r R1 sẽ cập nhật thông tin định tuyến đến D qua R2
m Khoảng cách tăng lên 5 (4+1)
m Một distance vector mới lại gửi đến R2
m ...v.v. (đến vô cùng)
D R1 R2 NetworkR3
?
D 5
Đếm vô hạn (Count to Infinity)
(7/7)
r Một khi giá trị tăng khá lớn, R2 kết luận rằng R1 không thể
phân phối các gói đến D.
r R2 sẽ dùng distance vector từ R3 để tìm đường đi khác đến D
D
r Quá trình này sẽ lan truyền ngược về mỗi nguồn của thông
điệp
D R1 R2 NetworkR3
?
Hội tụ chậm
(Slow Convergence)
r Hội tụ chậm là tình huống:
m Các router trong mạng mất nhiều thời gian ở trạng thái
không nhất quán.
• Vài router biết hư hỏng, nhưng những router khác thì không.
• Trong khoảng thời gian này, thông điệp đến D bị mất hay loop
giữa các router.
m Các router của mạng chậm nhận thức cấu hình đúng để
định tuyến đến D.
Cập nhật Split Horizon (1/2)
r Một giải pháp cho counting to infinity:
m Không gửi distance vector ra cùng với port mà distanve vector
nguồn ban đầu đi vào.
r Ví dụ
m R1 có thể quảng cáo một distance vector đến D (D,1)
m R2 sẽ nhận distance vector này và tạo vector (D,2)
m R2 sẽ không được gửi vector mới tạo này đến R1
Cập nhật Split Horizon (2/2)
r Trở ngại:
m Cần phải lưu giữ thông tin cổng nào distance vector đi vào
trong bảng định tuyến.
m Có thể tạo count to infinity dùng 3 hay nhiều router nối
thành vòng.
• Do đó split horizon không phải là giải pháp triệt để cho vấn đề
count to infinity
Hold Down (1/2)
r Router đợi một khoảng thời gian (timer) trước khi phát tán
thông tin về một mạng nào bị hỏng
m Đối với RIP, các distance vectors hết hạn sau 180 giây
m Trước khoảng thời gian này, các router sẽ tiếp tục chuyển
datgram một cách sai lầm.
m Sau khoảng thời gian này, tất cả các router sẽ bỏ tất cả các
đường đi có chứa liên kết bị hỏng này trong bảng định tuyến
m Distance vector được xem như lỗi thời nếu vector không được
truyền lại
m Sau khoảng thời gian này, thông tin định tuyến mới được phát
tán và các tuyến mới được tạo ra.
m Nếu một route đến đích mới không tìm thấy vào thời điểm này,
router sẽ không có mục tương ứng trong bảng và không thể
đến được đó qua nó.
Hold Down (2/2)
r Trở ngại:
m Các router đợi trong thời gian dài (180s)
m Trong khoảng thời gian này, các router ở
trong trạng thái không đồng nhất.
Route Poisoning và Poison Reverse
r Route Poisoning: được du ng đê đanh dâu môt tuyên
không thê đi trong môt câ p nhât đi nh tuyê n được
gửi đên cac router khac
r Poison reverse: Các Router phát hiện một host hay mạng bị
hỏng,vẫn giữ mục tương ứng trong bảng, nhưng tăng chi phí lên
vô cùng.
m Truyền ngay distance vector mới này
m Điều này nhắc tất cả các router khác tìm một đường khác nếu có
thể.
m Nếu không có đường đi khác, router sẽ khẳng định host hay mạng
là không thể đến được.
Dùng giải pháp
r Cho Count to Infinity
m Vô cùng (Infinity) trong RIP là 16
• Bằng cách này, số thông điệp trong thời gian count to infinity
bị giới hạn
• Tuy nhiên, điều này cũng giới hạn độ rộng của mạng, phải nhỏ
hơn 16.
m Hầu hết các hiện thực của RIP đều dùng split horizon
m Tuy nhiên, một vài hiện thực dùng route poisoning hay
poison reverse
r Cho routing loop
m Hold down timer đê ngăn chă n đinh tuyên lă p
m Khi nhâ n mô t câ p nhâ t chi ra mô t ma ng không co n truy câ p được,
router đa nh dâ u ma ng co thê down va khởi đô ng hold-down timer
m Nêu co môt câ p nhâ t chi ra metric tôt hơn, câ p nhâ t la i va huy
hold-down timer
m Nêu câ p nhâ t co metric giông hay xâ u hơn thi bo qua, va cứ thê
cho đê n khi timer hêt ha n thi tuyên na y xem như down.
NỘI DUNG
r RIP
rOSPF
r BGP
OSPF (Open Shortest Path First)
r Khả dụng, phổ biến
r Dùng giải thuật Link State
m Truyền các gói LS
m Topo mạng tại mỗi node
m Tính toán tuyến dùng giải thuật Dijkstra
r Trong quảng cáo của OSPF, mỗi router láng giềng được
ghi một mục
r Các quảng cáo được truyền đến toàn bộ AS (qua biện
pháp phát tán kiểu nước lũ)
m Được chứa trong thông điệp OSPF trực tiếp qua IP (thay vì
TCP hay UDP)
Các đặc tính cải tiến của OSPF so với RIP
r An ninh: tất cả các bản tin OSPF đều có thể xác thực
r Cho phép nhiều đường đi có cùng chi phí (trong RIP chỉ
có một)
r Trong mỗi liên kết, có thể cấu hình nhiều đại lượng chi
phí tùy theo ToS khác nhau (ví dụ chi phí trên liên kết
vệ tinh cấu hình mức thấp cho dịch vụ best effort và
cấu hình mức cao cho các dịch vụ thời gian thực)
r Hỗ trợ tích hợp unicast và multicast:
m Multicast OSPF (MOSPF) dùng cơ sở dữ liệu topo
tương tự như OSPF
r Phân cấp trong các domain lớn.
Hierarchical OSPF
•Mỗi AS có thể được
cấu hình thành nhiều
area
•Trong mỗi AS, một
area được cấu hình
thành backone area,
chứa tất cả các area
border router và chịu
trách nhiệm định tuyến
gói giữa các area trong
AS
Hierarchical OSPF
r Phân cấp hai mức: local area, backbone.
m Các quảng cáo Link-state chỉ gửi trong nội vùng
m Mỗi node có topo chi tiết của vùng; chỉ biết hướng
(đường ngắn nhất) đi đến các mạng trong các vùng
khác.
r area border router: “tóm lược” về cự li đến các mạng
trong nội vùng, quảng cáo đến các area border router
khác.
r backbone router: chạy định tuyến OSPF giới hạn trong
backbone.
r boundary router: kết nối đến các vùng tự trị (AS) khác.
NỘI DUNG
r RIP
rOSPF
r BGP
BGP (Border Gateway Protocol, RFC 1771)
r Hô trợ định tuyến liên vu ng, tao găn kêt liên mang (yêu
tô găn kêt cu a Internet)
r Trao đôi thông tin NLRI (Network Layer Reachability
Information)
m Cho mô t AS biêt thông tin đi đên AS khac
m Xac đi nh đường đi tô t nhât dựa trên thông tin va chinh sach
định tuyến
r BGP cho phep lâp va thực thi chinh sach
m Quang ba
m Định tuyến
Path vector routing
r Giữa ca c AS dung giải thuật na o?
m Không thê co cu ng chinh sach
m Du ng LS thi chi phi bât nhât, CSDL qua lớn
m Du ng DV mang qua rô ng, kho hôi tu
r Gia i phap: ti m đường theo giải thuật path
vector
r RFC 1322
Gia i thuât path vector
eBGP session va iBGP session
r eBGP session: diê n ra giữa ca c router trong
hai AS kha c nhau. Đây la ca c router kê cân
(adjacency) với router kha c, chia se cung
đường truyê n va mô t mang con.
r iBGP session: diê n ra giữa ca c router trong
cung AS, được du ng đê kê t hợp va đô ng bô
chinh sa ch định tuyến
Lâp chinh sach
r BGP co thê lâ p chi nh sa ch gửi hay nhâ n
thông tin định tuyến
r Du ng bô lo c
r Du ng ca c thuô c ti nh
m AS_PATH
m MED
m LOCAL_PREF
m Và các thuộc tính khác
Bô loc
r Chi trao đô i cho những đường đi đa đăng ky ,
loc vao, lo c ra
Dung thuôc ti nh AS_PATH
Du ng MED
(MULTI_EXIT_DISCRIMINATOR)
r Trong trường hợp hai AS co nhiê u liên kêt với nhau
r Chon MED nho hơn
r A p du ng điêu khiê n lưu lượng
Chia tai với MED
• Đặt giá trị MED khác nhau cho mỗi đường
Sử dung LOCAL_PREF
r Chon gia tri lớn hơn cu a LOCAL_PREF
r Điêu khiê n lưu lượng upbound
BGP: giao thức định tuyến inter-AS
trên Internet
r BGP (Border Gateway Protocol): tiêu chuẩn
phổ biến
r BGP cung cấp cho mỗi AS một phương tiện
để:
1. lấy thông tin về khả năng đến được subnet nào
đó từ các AS láng giềng.
2. phổ biến thông tin về khả năng đến được cho tất
cả các router bên trong AS.
3. Căn cứ vào thông tin về khả năng đến được và
chính sách xác định các tuyến tốt đến các
subnet.
r Cho phép mạng con quảng bá về sự tồn tại
của nó trên mạng Internet
Tìm hiểu thêm
r Các giao thức định tuyến IGRP,
EIGRP, IS-IS
rĐịnh tuyến Broadcast và multicast
(PIM)
HẾT CHƯƠNG 9