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

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