›
›

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

pdf 49 trang hapham 2520
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Mạng máy tính - Chương 5: Cơ sở giao thức định tuyến - Hoàng Thanh Hoà", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_mang_may_tinh_chuong_5_co_so_giao_thuc_dinh_tuyen.pdf

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

  1. BÀI GIẢNG MÔN: MẠNG MÁY TÍNH Giảng viên: Hoàng Thanh Hòa
  2. CHƢƠNG 5. CƠ SỞ GIAO THỨC ĐỊNH TUYẾN Các khái niệm cơ bản trong 5.1. định tuyến 5.2. Các thuật toán định tuyến Một số giao thức định tuyến 5.3. thông dụng thanhhoa48dhv@gmal.com 2
  3. 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ý thanhhoa48dhv@gmal.com 3
  4. 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 thanhhoa48dhv@gmal.com 4
  5. 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. thanhhoa48dhv@gmal.com 5
  6. 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. thanhhoa48dhv@gmal.com 6
  7. 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 thanhhoa48dhv@gmal.com 7
  8. 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. thanhhoa48dhv@gmal.com 8
  9. 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. thanhhoa48dhv@gmal.com 9
  10. 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. thanhhoa48dhv@gmal.com 10
  11. 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). thanhhoa48dhv@gmal.com 11
  12. 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 thanhhoa48dhv@gmal.com 12
  13. 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 thanhhoa48dhv@gmal.com 13
  14. 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. thanhhoa48dhv@gmal.com 14
  15. 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. thanhhoa48dhv@gmal.com 15
  16. 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 thanhhoa48dhv@gmal.com 16
  17. 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 thanhhoa48dhv@gmal.com 17
  18. 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 thanhhoa48dhv@gmal.com 18
  19. 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 thanhhoa48dhv@gmal.com 19
  20. 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: 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 20
  21. 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: Network Next hop Cost v v 2 x x 1 w x 4 y x 2 z x 4 thanhhoa48dhv@gmal.com 21
  22. 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: thanhhoa48dhv@gmal.com 22
  23. 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: 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 23
  24. 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à: Network Next hop Cost v v 2 x x 1 w x 3 y x 2 z x 4 thanhhoa48dhv@gmal.com 24
  25. 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. thanhhoa48dhv@gmal.com 25
  26. Thuật toán Vector khoảng cách 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 26
  27. 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ụ. thanhhoa48dhv@gmal.com 27
  28. 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 thanhhoa48dhv@gmal.com 28
  29. 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. thanhhoa48dhv@gmal.com 29
  30. 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 thanhhoa48dhv@gmal.com 30
  31. 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. thanhhoa48dhv@gmal.com 31
  32. 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 thanhhoa48dhv@gmal.com 32
  33. 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) thanhhoa48dhv@gmal.com 33
  34. 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. thanhhoa48dhv@gmal.com 34
  35. 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. thanhhoa48dhv@gmal.com 35
  36. 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 thanhhoa48dhv@gmal.com 36
  37. 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 thanhhoa48dhv@gmal.com 37
  38. Giao thức định tuyến RIP  Cấu trúc gói tin RIP: thanhhoa48dhv@gmal.com 38
  39. 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. thanhhoa48dhv@gmal.com 39
  40. 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 thanhhoa48dhv@gmal.com 40
  41. 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. thanhhoa48dhv@gmal.com 41
  42. Giao thức định tuyến IGRP  Cấu trúc gói tin IGRP: thanhhoa48dhv@gmal.com 42
  43. 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 thanhhoa48dhv@gmal.com 43
  44. 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. thanhhoa48dhv@gmal.com 44
  45. 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 7 B E 3 3 1 2 H 5 A C 1 6 F 2 4 5 4 3 6 D G thanhhoa48dhv@gmal.com 45
  46. Đề 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. thanhhoa48dhv@gmal.com 46
  47. Kiểm tra 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? 47
  48. 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 thanhhoa48dhv@gmal.com 48
  49. 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 thanhhoa48dhv@gmal.com 49