Bài giảng Mạng máy tính - Chương 5: Cơ sở giao thức định tuyến - Hoàng Thanh Hòa

BÀI GIẢNG MÔN: MẠNG MÁY TÍNH Giảng viên: Hoàng Thanh Hòa CHƢƠNG 5. CƠ SỞ GIAO THỨC ĐỊNH TUYẾN 2 Các khái niệm cơ bản trong định tuyến 5.1. 5.2. Các thuật toán định tuyến 5.3. Một số giao thức định tuyến thông dụng thanhhoa48dhv@gmal.com 5.1. Các khái niệm cơ bản trong định tuyến  Định tuyến  Bảng định tuyến  Metric  Giao thức định tuyến  Giao thức đƣợc định tuyến  Khoảng cách địa lý 3 thanhhoa48dhv@gmal.com Khái niệm định tuyến  Là phƣơng pháp xác định đƣờng đi cho việc vận chuyển các gói tin từ nguồn đến đích hiệu quả nhất.  Do các thiết bị thuộc lớp 3 của mô hình OSI, thƣờng là Router.  Router phải xây dựng cho mình một bảng chứa các thông tin cần thiết => đƣờng đi tối ƣu nhất đến đích 4 thanhhoa48dhv@gmal.com Bảng định tuyến  Là một bảng chứa thông tin về các tuyến đƣờng trên mạng, đƣợc lƣu trữ trong RAM của Router.  Bảng có thể đƣợc lập bởi ngƣời quản trị hoặc bằng các giao thức định tuyến. 5 thanhhoa48dhv@gmal.com Bảng định tuyến  Gồm có các thông tin: - Địa chỉ đích của mạng, mạng con của hệ thống. - Địa chỉ IP của Router chặng kế tiếp phải đến. - Cổng đi đến Router kế tiếp. - Mặt nạ mạng của địa chỉ đích. - Khoảng cách để đến đích. - Thời gian từ khi Router cập nhật lần cuối. 6 thanhhoa48dhv@gmal.com Khái niệm Metric  Là một số đo mà giao thức định tuyến sử dụng để từ đó chọn ra con đƣờng tối ƣu nhất.  Một giao thức định tuyến có thể sử dụng nhiều metric khác nhau 7 thanhhoa48dhv@gmal.com Khái niệm Metric  Các metric thường được sử dụng là: - Path Length (chiều dài tuyến đƣờng): là metric cơ bản, đƣợc xác định bằng số Hop giữa nguồn và đích. - Reliability (độ tin cậy): là khái niệm chỉ độ tin cậy của một liên kết. - Delay (độ trễ): Chỉ thời gian cần để chuyển một packet từ nguồn tới đích. - Bandwith (băng thông): Chỉ lƣu lƣợng dữ liệu tối đa có thể truyền trên liên kết. 8 thanhhoa48dhv@gmal.com Giao thức định tuyến  Là các giao thức để các Router sử dụng để trao đổi thông tin định tuyến với các Router khác.  Đƣợc cài đặt tại các Router, đƣợc sử dụng để tạo bảng định tuyến.  Có 2 loại giao thức định tuyến: - Giao thức định tuyến nội vùng: Rip, OSPF, IGRP, EIGRP. - Giao thức định tuyến ngoại vùng: BGP. 9 thanhhoa48dhv@gmal.com Giao thức định tuyến  Chức năng của giao thức định tuyến: - Học thông tin định tuyến về các mạng từ Router kế cận. - Quảng bá thông tin định tuyến về các mạng đến các Router kế cận. - Nếu có nhiều hơn một tuyến đƣờng đến một mạng, chọn tuyến đƣờng tốt nhất dựa vào metric. - Chức năng hội tụ định tuyến. 10 thanhhoa48dhv@gmal.com Giao thức đƣợc định tuyến  Là giao thức đƣợc sử dụng để định hƣớng cho gói dữ liệu của ngƣời dùng.  Cung cấp đầy đủ thông tin về địa chỉ lớp mạng để gói dữ liệu có thể truyền từ host này tới host khác dựa trên cấu trúc địa chỉ đó.  Các giao thức đƣợc định tuyến gồm có: - Internet Protocol (IP). - Internetwork Packet Exchange (EPX). 11 thanhhoa48dhv@gmal.com Khoảng cách địa lý  Administrative Distance (AD): là thông số để đánh giá độ tin cậy của thông tin định tuyến mà Router nhận đƣợc từ Router hàng xóm.  AD là một số nguyên có giá trị từ 0 đến 255.  Mỗi giao thức định tuyến có một giá trị AD tƣơng ứng: - Kết nối trực tiếp: 0 - Tuyến đường tĩnh: 1 - Rip: 120 - OSPF: 110 - IGRP: 100 12 thanhhoa48dhv@gmal.com 5.2. Các thuật toán định tuyến 5.2.1. Thuật toán tìm đƣờng đi ngắn nhất 5.2.2. Thuật toán định tuyến vector khoảng cách. 5.2.3. Thuật toán trạng thái đƣờng liên kết 5.2.4. So sánh các thuật toán 13 thanhhoa48dhv@gmal.com Thuật toán tìm đƣờng đi ngắn nhất  Thuật toán Bellman- Ford: Bài toán: cho đồ thị G với các đỉnh A,B,C,D có độ dài và đƣờng đi nhƣ hình dƣới, tìm đƣờng đi ngắn nhất từ B đến D. 14 thanhhoa48dhv@gmal.com Thuật toán tìm đƣờng đi ngắn nhất  Thuật toán Bellman- Ford: Bƣớc 0: Ta đánh dấu đỉnh xuất phát B là 0, các đỉnh còn lại là vô cực. 15 thanhhoa48dhv@gmal.com Thuật toán tìm đƣờng đi ngắn nhất  Thuật toán Bellman- Ford: Bƣớc 1: Cập nhật lại chi phí các đỉnh A,C 16 thanhhoa48dhv@gmal.com Thuật toán tìm đƣờng đi ngắn nhất  Thuật toán Bellman- Ford: Bƣớc 2: Cập nhật lại chi phí các đỉnh C, D 17 thanhhoa48dhv@gmal.com Thuật toán tìm đƣờng đi ngắn nhất  Thuật toán Bellman- Ford: Bƣớc 3: Cập nhật lại chi phí đỉnh D 18 thanhhoa48dhv@gmal.com Thuật toán tìm đƣờng đi ngắn nhất  Thuật toán Bellman- Ford: Bài toán: Tìm đƣờng đi từ nút u đến các nút còn lại Gọi: D(v) là độ dài đƣờng đi ngắn nhất từ một đỉnh nào đó tới v T(v) là đỉnh nằm phía trƣớc v trên đƣờng đi ngắn nhất 19 thanhhoa48dhv@gmal.com Thuật toán tìm đƣờng đi ngắn nhất  Thuật toán Bellman- Ford: Dùng thuật toán Bellman- Ford ta có bảng: 20 Lặp D(v), T(v) D(x), T(x) D(w), T(w) D(y), T(y) D(z), T(z) Khởi tạo 2,u 1,u 5,u ∞,u ∞,u K=1 2,u 1,u 4,x 2,x 10,w K=2 2,u 1,u 3,y 2,x 8,w K=3 2,u 1,u 3,y 2,x 4,y K=4 2,u 1,u 3,y 2,x 4,y thanhhoa48dhv@gmal.com Thuật toán tìm đƣờng đi ngắn nhất  Thuật toán Bellman- Ford: Nhƣ vậy ta có bảng định tuyến cho nút u: 21 Network Next hop Cost v v 2 x x 1 w x 4 y x 2 z x 4 thanhhoa48dhv@gmal.com Thuật toán tìm đƣờng đi ngắn nhất  Thuật toán Dijkstra: Xét bài toán tƣơng tự nhƣ trên, xác định bảng định tuyến của nút u: 22 thanhhoa48dhv@gmal.com Thuật toán tìm đƣờng đi ngắn nhất  Thuật toán Dijkstra: Áp dụng Dijsktra ta có bảng phân tích nhƣ sau: 23 Lặp T D(v), T(v) D(x), T(x) D(w),T(w) D(y), T(y) D(z), T(z) Khởi tạo vxwyz 2,u 1,u 5,u ∞,u ∞,u K=1 vwyz 2,u 4,x 2,x 10,w K=2 wyz 3,y 2,x 8,w K=3 wz 3,y 4,y K=4 z 4,y K=5 Rỗng thanhhoa48dhv@gmal.com Thuật toán tìm đƣờng đi ngắn nhất  Thuật toán Dijkstra: Từ bảng phân tích ta có bảng định tuyến của nut u là: 24 Network Next hop Cost v v 2 x x 1 w x 3 y x 2 z x 4 thanhhoa48dhv@gmal.com Thuật toán Vector khoảng cách  Distance Vector gồm 2 phần: Distance và Vector. Trong đó: - Distance là khoảng cách (metric) để đến đích - Vector là hƣớng để đi đến đích, nó đƣợc xác định bởi next-hop của tuyến đƣờng.  Mỗi Router chỉ cần biết 2 yếu tố khi chọn đƣờng: chọn theo hƣớng nào, khoảng cách tới đích là bao nhiêu. 25 thanhhoa48dhv@gmal.com Thuật toán Vector khoảng cách 26 Là thuật toán nhằm chọn ra đƣờng đi tốt nhất đến đích dựa trên Bellman- Ford thanhhoa48dhv@gmal.com Thuật toán Vector khoảng cách  Các giao thức sử dụng Distance Vector gửi các cập nhật định tuyến theo chu kỳ hoặc khi cấu trúc mạng có sự thay đổi.  Mỗi Router sẽ gửi toàn bộ bảng định tuyến của mình cho các Router kết nối trực tiếp với nó.  Khi tất cả các Router cập nhật đầy đủ thông tin về các tuyến đƣờng tới các mạng đích => mạng đã hội tụ. 27 thanhhoa48dhv@gmal.com Thuật toán Vector khoảng cách  Ưu điểm: - Giao thức đơn giản, cấu hình dễ dàng, dễ duy trì và sử dụng. - Thích hợp với các mạng quy mô nhỏ.  Nhược điểm: - Khi xảy ra sự cố hoặc có thay đổi trong mạng thì cần thời gian để hội tụ. - Có thể xảy ra lặp do những mâu thuẫn giữa các lần định tuyến. => Chậm hội tụ, không thích hợp với mạng lớn 28 thanhhoa48dhv@gmal.com Thuật toán trạng thái đƣờng liên kết  Các Router tự thu tập thông tin về đƣờng đi của mạng từ tất cả các Router khác.  Mỗi Router sẽ tự tính toán để chọn đƣờng đi tốt nhất cho nó đến các mạng đích.  Sử dụng các gói tin Hello để mang thông tin về các mạng kết nối trực tiếp vào Router.  Sử dụng các gói tin LSA mang thông tin cập nhật về trạng thái đƣờng liên kết của các Router khác trong mạng. 29 thanhhoa48dhv@gmal.com Thuật toán trạng thái đƣờng liên kết  Cơ chế hoạt động: - Sử dụng thông tin từ gói tin Hello và LSA nhận đƣợc từ Router hàng xóm để xây dựng cơ sở dữ liệu về cấu trúc hệ thống mạng. - Sử dụng thuật toán SPF (Dijkstra) để tìm ra đƣờng ngắn nhất đến từng mạng. - Lƣu kết quả chọn đƣờng trong bảng định tuyến 30 thanhhoa48dhv@gmal.com Thuật toán trạng thái đƣờng liên kết  Ưu điểm: - Thời gian hội tụ mạng nhanh hơn. - Mỗi router có một sơ đồ đầy đủ và đồng bộ về toàn bộ cấu trúc hệ thống mạng. Do đó chúng rất khó bị vòng lặp. - Router sử dụng thông tin mới nhất để quyết định chọn đƣờng đi. - Các giao thức định tuyến trạng thái đƣờng liên kết có hỗ trợ chia mạng con và phân vùng. 31 thanhhoa48dhv@gmal.com Thuật toán trạng thái đƣờng liên kết  Nhược điểm: - Đòi hỏi Router phải có nhiều dung lƣợng bộ nhớ và năng lực xử lý cao hơn. - Đòi hỏi hệ thống mạng thiết kế theo mô hình phân cấp. - Tiến trình phát các gói tin LSA có thể chiếm dụng nhiều dung lƣợng đƣờng truyền 32 thanhhoa48dhv@gmal.com 5.3. Một số giao thức định tuyến  Giao thức RIP (Routing Information Protocol)  Giao thức IGRP (Interior Gateway Routing Protocol)  Giao thức OSPF (Open Short Path First) 33 thanhhoa48dhv@gmal.com Giao thức định tuyến RIP  RIP là giao thức định tuyến véc tơ khoảng cách.  RIP gửi toàn bộ bảng định tuyến ra tất cả các cổng đang hoạt động đều đặn theo chu kỳ là 30 giây.  RIP sử dụng Metric là hop count để tính ra tuyến đƣờng tốt nhất đến đích.  Thuật toán mà RIP sử dụng để xây dựng nên bảng định tuyến là Bellman-Ford. 34 thanhhoa48dhv@gmal.com Giao thức định tuyến RIP  Các giá trị thời gian: - Update time: 30 giây - Invalid time: 180 giây - Holddown time: 180 giây - Flush time: 240 giây. 35 thanhhoa48dhv@gmal.com Giao thức định tuyến RIP  Cơ chế hoạt động: - Tất cả các gói tin của RIP đều đƣợc đóng gói vào UDP segment với cả hai trƣờng source và destination Port là 520. - Request message: đƣợc sử dụng để gửi một yêu cầu tới router hàng xóm để gửi update. - Reponse message: mang thông tin update 36 thanhhoa48dhv@gmal.com Giao thức định tuyến RIP  Cơ chế hoạt động: - Router gửi broadcast bản tin Request ra tất cả các cổng đang hoạt động => đợi - Các router hàng xóm nhận đƣợc các Request message rồi gửi Response message chứa toàn bộ bảng định tuyến - Khi nhận đƣợc thông tin định tuyến: → tuyến đƣờng đang tồn tại sẽ bị thay thế bởi tuyến đƣờng mới có hop count nhỏ hơn. → bỏ qua nếu hop count lớn hơn 37 thanhhoa48dhv@gmal.com Giao thức định tuyến RIP  Cấu trúc gói tin RIP: 38 thanhhoa48dhv@gmal.com Giao thức định tuyến IGRP  IGRP là giao thức định tuyến véc tơ khoảng cách, có chu kỳ update là 90 giây.  IGRP không sử dụng hopcount trong metric của mình, tuy nhiên nó vẫn theo dõi đƣợc hopcount.  Kích thƣớc của mạng cài đặt IRGP có thể lên tới 255 hop. 39 thanhhoa48dhv@gmal.com Giao thức định tuyến IGRP  Các giá trị về thời gian: - Update time: 90 giây - Invalid time: 270 giây - Holddown time: 280 giây - Flush timer: 630 giây 40 thanhhoa48dhv@gmal.com Giao thức định tuyến IGRP  Cơ chế hoạt động: - IGRP gửi broadcast Request packet tới tất cả các Router kết nối trực tiếp với nó. - IGRP sử dụng 3 loại tuyến đƣờng sau trong thông tin cập nhật:  Đƣờng nội bộ (Interior route): đƣờng nối trực tiếp với Router  Đƣờng hệ thống (System route): là những đƣờng đi giữa các mạng trong cùng một AS.  Đƣờng ngoại vi (Exterior route): là những đƣờng đi ra ngoài AS. 41 thanhhoa48dhv@gmal.com Giao thức định tuyến IGRP  Cấu trúc gói tin IGRP: 42 thanhhoa48dhv@gmal.com Giao thức định tuyến OSPF  OSPF là giao thức định tuyến theo trạng thái đƣờng liên kết, sử dụng thuật toán Dijkstra.  OSPF có ƣu điểm là hội tụ nhanh, hỗ trợ mạng có kích thƣớc lớn và không xảy ra vòng lặp định tuyến.  OSPF có thể chia một AS thành nhiều vùng (Area) khác nhau để giảm lƣu lƣợng định tuyến, dễ quản trị.  Là giao thức hỗ trợ chia mạng con 43 thanhhoa48dhv@gmal.com Giao thức định tuyến OSPF  Cơ chế hoạt động: gồm có 3 hoạt động - Tìm kiếm và xác lập mối quan hệ với Router hàng xóm. - Trao đổi cơ sở dữ liệu (LSDB exchange). - Sử dụng thuật toán Dijkstra để tính toán con đƣờng tốt nhất đặt vào bảng định tuyến. 44 thanhhoa48dhv@gmal.com Bài tập định tuyến  Sử dụng thuật toán Bellman –Ford, Dijkstra lập bảng định tuyến cho Node A 45 thanhhoa48dhv@gmal.com A B D C G E F H 3 5 2 7 1 4 3 6 4 6 2 3 5 1 Đề kiểm tra lại Cho địa chỉ IP: 192.168.10.210/27 1. Cho biết địa chỉ IP trên thuộc mạng có chia mạng con không? Tại sao? 2. Tìm địa chỉ mạng, địa chỉ broadcast và dải đia chỉ host của mạng con chứa IP trên. 3. Hãy chia mạng con vừa tìm đƣợc thành 4 mạng con mới, liệt kê các địa chỉ mạng, địa chỉ Broadcast, dải địa chỉ host của 4 mạng con này. 46 thanhhoa48dhv@gmal.com Kiểm tra 47 Cho địa chỉ IP của một số Host nhƣ sau: IP1: 134.135.30.10/20 IP2: 134.135.40.100/20 IP3: 134.135.50.20/20 IP4: 134.135.60.70/20 Hãy cho biết trong các host trên, host nào nằm cùng mạng con. Hãy cho biết địa chỉ mạng con đó, địa chỉ Broadcast của mạng và liệt kê các host hợp lệ, tính số lƣợng host trong mạng? Bài tập Giả sử ta có một địa chỉ Host là: 172.16.40.32/255.255.240.0 1. Host trên thuộc mạng có chia mạng con không? tại sao? Nếu có thì có bao nhiêu mạng con và mỗi mạng con có bao nhiêu host. 2. Tìm địa chỉ mạng, địa chỉ Broadcast của mạng chứa host trên 3. Liệt kê dãy địa chỉ host của mạng con vừa tìm đƣợc 48 thanhhoa48dhv@gmal.com Bài tập Cho hệ thống mạng gồm 228 host và địa chỉ IP đƣợc thiết lập ở lớp 192.168.1.0/24. Hãy chia hệ thống này thành 4 mạng con (Net 1: 120 host, Net 2: 60 host, Net 3: 30 host, Net 4: 18 host) dựa theo kỹ thuật VLSM gồm các thông tin: - Địa chỉ mạng con (Network ID) - Subnet Mask của mạng con - Dải địa chỉ host của mỗi mạng con - Địa chỉ Broadcast - Diệp hoàng bảo bảo 49 thanhhoa48dhv@gmal.com