Bài giảng Mạng máy tính - Chương 4: Chọn đường-Routing - Ngô Hồng Sơn

1Chương 4: Chọn đường - Routing 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
Giao thức IP
ðịa chỉ IP và cấu trúc gĩi tin IP
Giao thức ICMP
Tuần này: Tiếp tục về tầng mạng
Thế nào là chọn đường?
Chọn đường tĩnh và chọn đường động
Giải thuật và giao thức chọn đường 3Chọn đường là gì? Các nguyên lý chọn đường Cơ chế chuyển tiếp gĩi tin Quy tắc “Longest matching” 4Cơ bản về chọn đường (1)
Khi một máy trạm gửi một gĩi tin IP tới một máy khác
Nếu địa chỉ đích nằm trên cùng một đường truyền vật lý: Chuyển trực tiếp
Nếu địa chỉ đích nắm trên một mạng khác: Chuyển gián tiếp qua bộ định tuyến (chọn đường) Router Router 5ðích đến（Tìm đường đi） ðích đến? （Tìm đường đi） Cơ bản về chọn đường (2) 6Chọn đường là gì?
Cơ chế để máy trạm hay bộ định tuyến chuyển tiếp gĩi tin từ nguồn đến đích
Các thành phần của chọn đường
Bảng chọn đường
Thơng tin chọn đường
Giải thuật, giao thức chọn đường 7Bộ định tuyến?
Thiết bị chuyển tiếp các gĩi tin giữa các mạng
Là một máy tính, với các phần cứng chuyên dụng
Kết nối nhiều mạng với nhau
Chuyển tiếp gĩi tin dựa trên bảng chọn đường
Cĩ nhiều giao diện
Phù hợp với nhiều dạng lưu lượng và phạm vi của mạng 8Một số ví dụ Cisco 2600 Cisco CRS-1 BUFFALO BHR-4RV Router mạng trục Router ngoại vi Router cỡ trung Juniper M10 Cisco 3700 Foundry Networks NetIron 800 Hitachi GR2000-1B YAMAHA RTX-1500 PLANEX GW-AP54SAG 9Bảng chọn đường
Chỉ ra danh sách các đường đi cĩ thể, được lưu trong bộ nhớ của router
Các thành phần chính của bảng chọn đường
ðịa chỉ đích/mặt nạ mạng
Router kế tiếp 10 Router B C172.16.0.0/24 A10.0.0.0/24 Next-hopNetwork Router CRouter A 10.0.0.0/24 192.168.0.0/24 172.16.0.0/24 10.0.0.0/24 172.16.0.0/24 Bảng chọn đường và cơ chế chuyển tiếp (1) Lưu ý quy tắc: No routes, no reachability! 11 Quy tắc “Longest matching”(1)
Giả sử một địa chỉ mạng đích lại cĩ nhiều hơn một mục trong bảng chọn đường
ðịa chỉ đích : 11.1.2.5
Router kế tiếp nào sẽ được sử dụng? C11.1.2.0/24 B11.1.0.0/16 A11.0.0.0/8 Next hopNetwork 12 Quy tắc “Longest matching”(2) ðịa chỉ đích: 11.1.2.5 = 00001011.00000001.00000010.00000101 ðường đi 1: 11.1.2.0/24 = 00001011.00000001.00000010.00000000 ðường đi 2: 11.1.0.0/16 = 00001011.00000001.00000000.00000000 ðường đi 3: 11.0.0.0/8 = 00001011.00000000.00000000.00000000 “Longest matching” là gì? Tại sao phải cần quy tắc này? 13 Router B C172.16.0.0/24 Direct192.168.0.0/24 A10.0.0.0/24 Next-hopNetwork Router CRouter A 10.0.0.0/24 192.168.0.0/24 172.16.0.0/24 10.0.0.0/24 172.16.0.0/24 Bảng chọn đường và cơ chế chuyển tiếp (2) Q. Mơ tả bảng chọn đường trên C Nếu C nối vào Internet? Internet 14 ðường đi mặc định
Nếu đường đi khơng tìm thấy trong bảng chọn đường
ðường đi mặc định trỏ đến một router kết tiếp
Trong nhiều trường hợp, đây là đường đi duy nhất
0.0.0.0/0
Là một trường hợp đặc biệt, chỉ tất cả các đường đi Internet Router A Router kế tiếp luơn là A 15 Kết hợp đường đi (Routing aggregation) 200.23.1.0/24 200.23.2.0/24 200.23.3.0/24 200.23.4.0/24 200.23.0.0/22 200.23.0.0/23 200.23.2.0/23
Cĩ bao nhiêu mạng con trên mạng Internet?
Sẽ cĩ rất nhiều mục trong bảng chọn đường?
Các mạng con kế tiếp với cùng địa chỉ đích cĩ thể được tổng hợp lại để làm giảm số mục trong bảng chọn đường. 16 Kết hợp đường đi (2)
Ví dụ về Viettel
Khơng gian địa chỉ IP: khá lớn
203.113.128.0-203.113.191.255
ðể kết nối đến một mạng con của Vietel (khách hàng): Chỉ cần chỉ ra đường đi đến mạng Viettel
ðường đi mặc định chính là một dạng của việc kết hợp đường
0.0.0.0/0 17 Ví dụ về bảng chọn đường – máy trạm C:\Documents and Settings\hongson>netstat -rn Route Table =========================================================================== Interface List 0x1 ........................... MS TCP Loopback interface 0x2 ...08 00 1f b2 a1 a3 ...... Realtek RTL8139 Family PCI Fast Ethernet NIC - =========================================================================== Active Routes: Network Netmask Gateway Interface Metric 0.0.0.0 0.0.0.0 192.168.1.1 192.168.1.34 20 127.0.0.0 255.0.0.0 127.0.0.1 127.0.0.1 1 192.168.1.0 255.255.255.0 192.168.1.34 192.168.1.34 20 192.168.1.34 255.255.255.255 127.0.0.1 127.0.0.1 20 192.168.1.255 255.255.255.255 192.168.1.34 192.168.1.34 20 224.0.0.0 240.0.0.0 192.168.1.34 192.168.1.34 20 255.255.255.255 255.255.255.255 192.168.1.34 192.168.1.34 1 Default Gateway: 192.168.1.1 =========================================================================== 18 #show ip route Prefix Next Hop 203.238.37.0/24 via 203.178.136.14 203.238.37.96/27 via 203.178.136.26 203.238.37.128/27 via 203.178.136.26 203.170.97.0/24 via 203.178.136.14 192.68.132.0/24 via 203.178.136.29 203.254.52.0/24 via 203.178.136.14 202.171.96.0/24 via 203.178.136.14 Ví dụ về bảng chọn đường – Router (trích) 19 Chọn đường tĩnh và chọn đường động Chọn đường tĩnh Chọn đường động Ưu điểm – nhược điểm 20 Router B C172.16.0.0/24 A10.0.0.0/24 Next- hop Network Router CRouter A 10.0.0.0/24 192.168.0.0/24 172.16.0.0/24 B192.168.0.0/24 B10.0.0.0/24 Next- hop Network B172.16.0.0/24 B192.168.0.0/24 Next- hop Network Vấn đề cập nhật bảng chọn đường
Sự thay đổi cấu trúc mạng: thêm mạng mới, một nút mạng bị mất điện
Sự cần thiết phải cập nhật bảng chọn đường
Cho tất cả các nút mạng (về lý thuyết)
Thực tế, chỉ một số nút mạng phải cập nhật 172.16.1.0/24 172.16.1.0/24 B 172.16.1.0/24 C New Network 21 Làm thế nào để cập nhật?
Chọn đường tĩnh
Các mục trong bảng chọn đường được sửa đổi thủ cơng bởi người quản trị
Chọn đường động
Tự động cập nhật bảng chọn đường
Bằng các giao thức chọn đường 22 Chọn đường tĩnh
Khi cĩ sự cố:
Khơng thể nối vào Internet kể cả khi cĩ tồn tại đường đi dự phịng
Người quản trị mạng cần thay đổi Internet Next-hop 10.0.0.3 10.0.0.1 10.0.0.3 10.0.0.2 Next-hop 10.0.0.1 Bảng chọn đường của 10.0.0.1 (1 phần) 10.0.0.30.0.0.0/0 Next-hopPrefix Kết nối bị lỗi 23 Chọn đường động
Khi cĩ sự cố:
ðường đi thay thế được cập nhật một cách tự động Bảng chọn đường của 10.0.0.1 (1 phần) 10.0.0.30.0.0.0/0 10.0.0.20.0.0.0/0 Next-hopPrefix Kết nối bị lỗi Kết nối dự phịng Internet Next-hop 10.0.0.3 10.0.0.1 10.0.0.3 10.0.0.2 Next-hop 10.0.0.1 24 ðặc điểm của chọn đường tĩnh
Ưu
Ổn định
An tồn
Khơng bị ảnh hưởng bởi các yếu tố tác động
Nhược
Cứng nhắc
Khơng thể sử dụng tự động kết nối dự phịng
Khĩ quản lý 25 Chọn đường động
Ưu
Dễ quản lý
Tự động sử dụng kết nối dự phịng
Nhược
Tính an tồn
Các giao thức chọn đường phức tạp và khĩ hiểu
Khĩ quản lý 26 Các giải thuật và giao thức chọn đường Giải thuật Dijkstra và Bellman-Ford Giao thức dạng link-state và dạng distance-vector 27 Biểu diễn mạng bởi đồ thị u yx wv z 2 2 1 3 1 1 2 5 3 5
ðồ thị với các nút (bộ định tuyến) và các cạnh (liên kết)
Chi phí cho việc sử dụng mỗi liên kết c(x,y)
Băng thơng, độ trễ, chi phí, mức độ tắc nghẽn
Giả thuật chọn đường: Xác định đường đi ngắn nhất giữa hai nút bất kỳ 28 Cây đường đi ngắn nhất - SPT
SPT – Shortest Path Tree
Các cạnh xuất phát từ nút gốc và tới các lá
ðường đi duy nhất từ nút gốc tới nút v, là đường đi ngắn nhất giữa nút gốc và nút v
Mỗi nút sẽ cĩ một SPT của riêng nút đĩ yx w u zu yx wv z 2 2 1 3 1 1 2 5 3 5 v 29 Tập trung hay phân tán
Tập trung
Thu thập thơng tin vào một nút mạng
Sử dụng các giải thuật tìm đường đi trên đồ thị
Phân bổ bảng chọn đường từ nút trung tâm tới các nút
Phân tán
Mỗi nút tự xây dựng bảng chọn đường riêng
Giao thức chọn đường: Link-state hoặc distance- vector
ðược sử dụng phổ biến trong thực tế 30 Tập trung hay phân tán
Thơng tin chọn đường là cần thiết để xây dựng bảng chọn đường
Tập trung hay phân tán?
Tập trung:
Mỗi router cĩ thơng tin đầy đủ về trạng thái của mạng
Giải thuật dạng “link state”
Phân tán:
Các nút chỉ biết được trạng thái của liên kết vật lý tới nút kế bên
Liên tục lặp lại việc tính tốn và trao đổi thơng tin với nút kế bên
Giải thuật dạng “distance vector”
“Bạn của bạn cũng là bạn” 31 Giải thuật dạng link-state Giải thuật Dijkstra’s
Mỗi nút đều cĩ sơ đồ và chi phí mỗi link
Quảng bá “Link-state”
Mỗi nút cĩ cùng thơng tin
Tìm đường đi chi phí nhỏ nhất từ một nút (‘nguồn’) tới tất cả các nút khác
dùng để xây dựng bảng chọn đường 32 Ký hiệu
G = (V,E) : ðồ thị với tập đỉnh V và tập cạnh E
c(x,y): chi phí của liên kết x tới y; = ∞ nếu khơng phải 2 nút kế nhau
d(v): chi phí hiện thời của đường đi từ nút nguồn tới nút đích. v
p(v): nút ngay trước nút v trên đường đi từ nguồn tới đích
T: Tập các nút mà đường đi ngắn nhất đã được xác định 33 Các thủ tục
Init(): Với mỗi nút v, d[v] = ∞, p[v] = NIL d[s] = 0
Improve(u,v), trong dĩ (u,v) u, v là một cạnh nào đĩ của G if d[v] > d[u] + c(u,v) then d[v] = d[u] + c(u,v) p[v] = u 34 Dijsktra’s Algorithm 1. Init() ; 2. T = Φ; 3. Repeat 4. u: u ∈ T | d(u) là bé nhất ; 5. T = T ∪ {u}; 6. for all v ∈ neighbor(u) và v ∉T 7. update(u,v) ; 8. Until T = V 35 Dijkstra’s algorithm: Ví dụ Step 0 1 2 3 4 5 T u ux uxy uxyv uxyvw uxyvwz d(v),p(v) 2,u 2,u 2,u d(w),p(w) 5,u 4,x 3,y 3,y d(x),p(x) 1,u d(y),p(y) ∞ 2,x d(z),p(z) ∞ ∞ 4,y 4,y 4,y yx w u z u yx wv z 2 2 1 3 1 1 2 5 3 5 v v x y w z (u,v) (u,x) (u,x) (u,x) (u,x) destination link Bảng chọn đường của u: SPT của u: 36 Giải thuật dạng distance-vector (1) Phương trình Bellman-Ford (quy hoach động) ðịnh nghĩa dx(y) := chi phí của đường đi ngắn nhất từ x tới y Ta cĩ dx(y) = min {c(x,v) + dv(y) } cho tất cả các v là hàng xĩm của x v 37 Minh họa Bellman-Ford Eq. u yx wv z 2 2 1 3 1 1 2 5 3 5 Dễ thấy, dv(z) = 5, dx(z) = 3, dw(z) = 3 du(z) = min { c(u,v) + dv(z), c(u,x) + dx(z), c(u,w) + dw(z) } = min {2 + 5, 1 + 3, 5 + 3} = 4 Nút nào làm giá trị trên nhỏ nhất➜ Lựa chọn là nút kế tiếp trong bảng chọn đường B-F eq. cho ta biết: 38 Giải thuật dạng distance-vector (2) ý tưởng cơ bản:
DV: Vector khoảng cách, tạm coi là đường đi ngắn nhất của từ một nút tới những nút khác
Mỗi nút định kỳ gửi DV của nĩ tới các nút bên cạnh
Khi nút x nhận được 1 DV, nĩ sẽ cập nhật DV của nĩ qua pt Bellman-ford
Với một số điều kiện, ước lượng Dx(y) sẽ hội tụ dần đến giá trị nhỏ nhất dx(y) Chờ (Thay đổi trong DV của nút bên cạnh) Tính lại ước lượng DV Nếu DV thay đổi, Báo cho nút bên cạnh Mỗi nút: 39 x y z x y z 0 2 7 ∞ ∞ ∞ ∞ ∞ ∞ t ừ chi phí tới t ừ t ừ x y z x y z 0 t ừ chi phí tới x y z x y z ∞ ∞ ∞ ∞ ∞ chi phí tới x y z x y z ∞ ∞ ∞ 7 1 0 chi phí tới ∞ 2 0 1 ∞ ∞ ∞ 2 0 1 7 1 0 thờigian x z 12 7 y nút x nút y nút z Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2 Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = 3 32 40 x y z x y z 0 2 7 ∞ ∞ ∞ ∞ ∞ ∞ t ừ chi phí tới t ừ t ừ x y z x y z 0 2 3 t ừ chi phí tới x y z x y z 0 2 3 t ừ chi phí tới x y z x y z ∞ ∞ ∞ ∞ ∞ chi phí tới x y z x y z 0 2 7 t ừ chi phí tới x y z x y z 0 2 3 t ừ chi phí tới x y z x y z 0 2 3 t ừ chi phí tới x y z x y z 0 2 7 t ừ chi phí tới x y z x y z ∞ ∞ ∞ 7 1 0 chi phí tới ∞ 2 0 1 ∞ ∞ ∞ 2 0 1 7 1 0 2 0 1 7 1 0 2 0 1 3 1 0 2 0 1 3 1 0 2 0 1 3 1 0 2 0 1 3 1 0 thờigian x z 12 7 y nút x nút y nút z Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2 Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = 3 41 So sánh các giải thuật LS và DV Thơng điệp trao đổi
LS: n nút, E cạnh, O(nE) thơng điệp
DV: Chỉ trao đổi giữa các hàng xĩm
Thời gian hội tụ thay đổi Tốc độ hội tụ
LS: Thuật tốn: O(n2) cần O(nE) thơng điệp
DV: Thay đổi Sự chắc chắn: Giải sử một router hoạt động sai LS:
nút gửi các chi phí sai
Mỗi nút tính riêng bảng chọn đường -> cĩ vẻ chắc chắn hơn DV:
DV cĩ thể bị gửi sai
Mỗi nút tính tốn dựa trên các nút khác
Lỗi bị lan truyền trong mạng 42 Tĩm tắt
Nguyên lý của bài tốn chọn đường
Tĩnh vs. động, tập trung vs. phân tán
Link-state vs. distance-vector 43 Tuần tới: Các giao thức chọn đường trên Internet
Chọn đường phân cấp
RIP
OSPF
BGP