Báo cáo: Giao thức Đường đi ngắn nhất OSPF

Chia sẻ: Nguyen Minh Khang Khang | Ngày: | Loại File: DOC | Số trang:35

Thêm vào BST

Báo xấu

340
lượt xem 210
download

Báo cáo: Giao thức Đường đi ngắn nhất OSPF

Mô tả tài liệu

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bưu chính viễn thông và công nghệ thông tin ngày nay rất phát triển.Cuộc cách mạng thông tin đã và đang diễn ra trên hầu hết các nước tiên tiến trên thế giới . Có thể nói thông tin ngày nay đóng vai trò hết sức quan trọng trong cuộc sông hàng ngày của mỗi con người từ việc ăn gì ở đâu ,xem gì trong những ngày tới đến vấn cổ phiếu tăng giá hay giảm giá hay những vấn đề quan trọng của cả thế giới đều được phản ánh qua thông tin được cập nhật hàng ngày. Điều...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo: Giao thức Đường đi ngắn nhất OSPF

Giao Thức Đường Đi Ngắn Nhất GVHD: Hoàng Trọng Minh TEÂN ÑEÀ TAØI Giao thức Đường đi ngắn nhất OSPF SV: Phạm Tiến Khánh- A06300 1
Giao Thức Đường Đi Ngắn Nhất GVHD: Hoàng Trọng Minh MỤC LỤC Lời mở đầu ....................................................................................................... 4 Danh mục các từ viết tắt và công thức toán học ............................................ 1 Danh mục bảng biểu và hình vẽ ..................................................................... 2 I: Các khái niệm cơ bản .................................................................................. 3 1. Khái niệm về định tuyến : .......................................................................... 3 2.Khái niệm về giao thức : .............................................................................. 3 II: Các giao thức .............................................................................................. 3 1.Tổng quan chung về các giao thức : .......................................................... 3 2. Giao thức định tuyến RIPvà OSPF( Lý do ra đời OSPF) ......................... 4 III: Giao thức đường đi ngắn nhất (OSPF-open shoter Path Fist).............. 5 1.Giao thức đường đi ngắn nhất (OSPF-Open Shortest Path First) ............ 5 1.1Định tuyến động và thuật toán LSA ....................................................................................... 7 1.2Thuật toán trạng thái liên kết LSA ......................................................................................... 7 2.So sánh liên kết động và liên kết tĩnh: ........................................................ 7 2.1:Giao thức định tuyến vecto khoảng cách .............................................................................. 9 2.2: Các Giao thức định tuyến trạng thái liên kết ..................................................................... 11 3:V ùng OSPF................................................................................................ 14 4:Kiểu router .................................................................................................. 15 Trong hình trên đã chỉ ra 3 liểu router gồm :router mạng lõi (Backbone- router) , Router biên khu vực (Area boder router), router nội miền(Internal router) ............................................................................................................. 15 5:Kiểu đ ịnh tuyến ......................................................................................... 15 6:Cập nhật định tuyến ................................................................................... 17 7:Định dạng của gói tin OSPF: OSPF sử dụng 5 loại gói khác nhau. ...... 19 SV: Phạm Tiến Khánh- A06300 2
Giao Thức Đường Đi Ngắn Nhất GVHD: Hoàng Trọng Minh 7.1 Gói chào (Hello) của OSPF ................................................................................................. 21 7.2:Gói mô tả cơ sở dữ liệu của OSPF: ..................................................................................... 22 7.3Gói yêu cầu trạng thái liên kết ............................................................................................. 24 7.4Gói cập nhật trạng thái liên kết ............................................................................................ 24 Tổng Kết : ....................................................................................................... 31 Danh mục các sách tham khảo ..................................................................... 32 SV: Phạm Tiến Khánh- A06300 3
Giao Thức Đường Đi Ngắn Nhất GVHD: Hoàng Trọng Minh Lời mở đầu Bưu chính viễn thông và công nghệ thông tin ngày nay rất phát triển.Cuộc cách mạng thông tin đã và đang diễn ra trên hầu hết các nước tiên tiến trên thế giới . Có thể nói thông tin ngày nay đóng vai trò hết sức quan trọng trong cuộc sông hàng ngày của mỗi con người từ việc ăn gì ở đâu ,xem gì trong những ngày tới đến vấn cổ phiếu tăng giá hay giảm giá hay những vấn đề quan trọng của cả thế giới đều được phản ánh qua thông tin được cập nhật hàng ngày. Điều đó cho thấy mạng lưới viễn thông đã bao trùm trên toàn thế giới . Ngày nay chúng ta cũng không phải lo về việc thiếu hụt băng thông cho truyền tin như trước kia thay vào đó là việc làm sao để sử lý gói tin tại các nút là nhanh nhất Giao thức là một kiểu cách thức giao tiếp , đối thoại . Cũng như con người máy móc muốn làm việc với nhau cũng cần có những cách thức giao tiếp riêng . Trong việc truyền tin cũng vậy các Router muốn giao tiếp với nhau cũng cần phải có những giao thức để làm việc với nhau . Các giao thức đó thường là RIP , IGRP, EGRP, IS-IS,BGP4 và OSPF SV: Phạm Tiến Khánh- A06300 4
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh Danh mục các từ viết tắt và công thức toán học Các từ viết tắt Tiếng Anh Tiếng Việt DBD Database description Gói mô tả cơ sở dữ liệu paket LSU Link state update Cập nhật thông tin trạng thái liên kết LSACK Link state Tin báo nhận trạng thái acknowledgement liên kết OSPF Open shorter path fist Giao thứ đường đi ngắn nhất LSA Link state age Tuổi trạng thái liên kết TOS Type of sevice Loại dịch vụ SPF shorter path fist Các loại dịch vụ AS Autonomous system Vùng tự trị SV : Phạm Tến Khánh 1
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh Danh mục bảng biểu và hỡnh vẽ Bảng Tên bảng Trang Bảng 1.0 Các giao thức định tuyến và tiêu chí so sánh 5 Bảng 1.1 Các kiểu gói OSPF 16 Bảng 1.2 Tiêu đề gói tin OSPF 16 Bảng 1.3 Giá trị kiểu xác nhận 17 Bảng 1.4 Tiêu đề gói chào OSPF 18 Bảng 1.5 Định dạng gói miêu tả cơ sở dữ liệu 20 Bảng 1.6 :Định dạng gói yêu cầu trạng thái liên kết 21 Bảng 1.7 Định dạng chung của gói cập nhật trạng thái liên kết 21 Bảng 1.8 Tiêu đề chung của LSA 22 Bảng 1.9 LSA liên kết router 23 Bảng 2.0 Các loại liên kết ID 24 Bảng 2.1 Giá trị trường TOS 25 Bảng 2.2 Định dạng LSAliên kết mạng 26 Bảng 2.3 Đinh dạng LSA liên kết tóm tắt tới mạng 26 Bảng 2.4 Định dang LSA liên kết router biên 27 Bảng 2.5 LSA liên kết bên ngoài 27 Bảng 2.6 LSA liên kết bên ngoài 27 Hình 1.0 Các khu vực tự trị 7 Hình 1.1 Mô tả 10 Hinh1.2 Đơn mạng OSPF 13 Hình1.3 3 kiểu router 13 Hình 1.4 định tuyến miền trong 14 Hình 1.5 Khu vực tự trị 15 Hình 1.6 Định tuyến vùng ngoài 16 Hình 1.7 Định tuyến liên khu vực 16 Hình 1.8 Cập nhật bảng định tuyến nội miền 17 Hình 1.9 Cập nhật bảng định tuyến 2 vùng 17 Hình 2.0 Cập nhật bảng định tuyến ơ r mạng lõi 19 SV : Phạm Tến Khánh 2
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh I: Các khái niệm cơ bản 1. Khái niệm về định tuyến : Định tuyến là một tiến trỡnh lựa chọn con đường cho thực thể thông tin chuyển qua mạng, nó cũn được coi là khả năng của một nút trong vấn đề lựa chọn đường dẫn cho thông tin qua mạng. Định tuyến là một khái niệm cốt lừi của mạng IP và nhiều loại mạng khỏc nhau. Định tuyến cung cấp phương tiện tỡm kiếm các tuyến đường theo các thông tin mà thực thể thông tin được chuyển giao trên mạng 2.Khái niệm về giao thức : Để đơn giản ta chỉ cần hiểu giao thức là cách thức giao tiếp. Trong mạng thông tin giữa các máy tính thỡ giao thức rất quan trọng , giao thức chính là cầu nối giữa các máy tính , các hệ thống máy tính và các hệ thống mạng . II: Các giao thức 1.Tổng quan chung về các giao thức : Các giao thức hiênc có gồm có RIP (RIP-1, RIP-2) ; OSPF, IGRP, EIGRP, IS-IS, BGP4. Trong đó thỡ phõn ra làm hai loại Giao thức nội miền và giao thức đa miền Giao thức liên miền gồm: RIP, OSPF … Giao thức liên miền gồm: OSPF, IS_IS… Trong đó thỡ cỏc giao thức đều có những ưu nhược đỉêm riêng được thể hiện qua bảng sau : Tiêu chí Giao thức thông tin dịnh tuyến Định RIP-1 RIP-2 IGRP EIGRP IS-IS OSPF BGPS tuyến tĩnh Thích hợp cho mạng lớn và khó khăn khi Có Không Không Không Có Có Có Có thực thi mạng Dễ cho thi Không Có Có Có Có Không Không không hành Kiểu thuật Không DVP DVP DVP DUAL LSP LSP DVP toán Hỗ chợ địa chỉ Có Có Có Có Có Có Có Có SV : Phạm Tến Khánh 3
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh Hỗ trợ CIDRR và VLSM Có Không Có Không Có Không Có Có Hỗ chợ chia Không Không Không Có Có Có Có Có tải Hỗ chợ chứng Không Không Có Không Có Có Có Có thực Cho phép đánh Không Không Không Có Có Có Có Có trọng số Hội tụ nhanh Không Không Không Có Có Có Có Có Thủ tục mời Không Không Không Có Có Có Không chào cho Không Router láng riềng Sử dụng quảng Không Có Có Có Có Có Có Không bá cho việc cập nhật bảng định tuyến Bảng 1:các giao thức định tuyến và tiêu chí so sánh 2. Giao thức định tuyến RIPvà OSPF( Lý do ra đời OSPF) Qua bảng so sánh trên đây ta nhận thấy ngay được các khả năng của các giao thức định tuyến và các hạn chế của nó . Trong đó giao thứcRIP là một giao thức định tuyến miền trong được sử dụng cho các hệ thống tự trị. Giao thức thông tin định tuyến thuộc loại giao thức định tuyến khoảng cách vectơ, giao thức sử dụng giá trị để đo lường đó là số bước nhảy (hop count) trong đường đi từ nguồn đến đích. Mỗi bước đi trong đường đi từ nguồn đến đích được coi như có giá trị là 1 hop count. Khi một bộ định tuyến nhận được 1 bản tin cập nhật định tuyến cho các gói tin thỡ nú sẽ cộng 1 vào giỏ trị đo lường (hop count) đồng thời cập nhật vào bảng định tuyến . Trong đó đáng chú ý là RIP- 1 và RIP-2 RIP thực hiện việc ngăn cản vũng lặp định tuyến vô hạn bằng cách thực hiện giới hạn số đường đi cho phép trong 1 đường đi từ nguồn tới đích. Số hop tối đa trong một đường đi là 15. Nếu 1 bộ định tuyến nhận được một bản tin cập nhật định tuyến và tại đây giá trị đo lường trở thành 16 thỡ đích coi như là nút mạng không thể đến được. Nhược điểm của RIP chính là giới hạn đường kính tối đa của 1 mạng RIP là dưới 16 hops. RIP có đặc điểm hoạt động ổn định nhưng khả năng thay đổi chậm. Khi có thay đổi về cấu hỡnh mạng, RIP luụn thực hiện chế độ chia rẽ tầng và áp đặt cơ chế ngăn SV : Phạm Tến Khánh 4
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh chặn các thông tin định tuyến sai được phát tán trong các bộ định tuyến. RIP sử dụng các bộ định thời để điều chỉnh hoạt động của mỡnh. Bộ định thời cập nhật định tuyến theo khoảng thời gian định trước, thông thường 30s là bộ định thời lại được khởi động lại để cập nhật lại các thông tin định tuyến được gởi từ các bộ định tuyến lân cận. Điều này cũng giúp ngăn chặn sự tắc nghẽn trong mạng khi tất cả các bộ định tuyến cùng 1 thời điểm cố gắng cập nhật các bảng định tuyến lân cận.Chính vỡ điều đó mà người ta đó ghĩ ra cách khắc phục những nhược điểm của RIP để cho ra OSPF một giao thức vừa áp dụng cho đa miền vừa áp dụng cho nội miền III: Giao thức đường đi ngắn nhất (OSPF-open shoter Path Fist) 1.Giao thức đường đi ngắn nhất (OSPF-Open Shortest Path First) Giao thức OSPF là một giao thức định tuyến miền trong được sử dụng rộng rói. Phạm vi hoạt động của nó cũng là một hệ thống tự trị (AS). Các router đặc biệt được gọi là các router biên AS có trách nhiệm ngăn thông tin về các AS khác vào trong hệ thống hiện tại. Để thực hiện định tuyến hiệu quả, OSPF chia hệ thống tự trị ra thành nhiều khu vực nhỏ. Mỗi AS có thể được chia ra thành nhiều khu vực khác nhau. Khu vực là tập hợp các mạng, trạm và router nằm trong cùng một hệ thống tự trị. Tất cả các mạng trong một khu vực phải được kết nối với nhau. Tại biờn của khu vực, cỏc router biờn khu vực túm tắt thụng tin về khu vực của mỡnh và gửi cỏc thụng tin này tới cỏc khu vực khỏc. Trong số cỏc khu vực bờn trong AS, cú một khu vực đặc biệt được gọi là đường trục; tất cả các khu vực trong một AS phải được nối tới đường trục. Hay nói cách khác là đường trục được coi như là khu vực sơ cấp cũn cỏc khu vực cũn lại đều được coi như là các khu vực thứ cấp. Khu vực 1 Khu vực 2 Router biên khu vực Tới AS khác Khu vực đường trục Router đường trục Router biên AS SV : Phạm Tến Khánh 5 Hệ thống tự trị (AS)
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh Các router bên trong khu vực đường trục được gọi là các router đường trục, các router đường trục cũng có thể là một router biên khu vực. Nếu vỡ một lý do nào đó mà kết nối giữa một khu vực và đường trục bị hỏng thỡ người quản trị mạng phải tạo một liên kêts ảo (virtual link) giữa các router để cho phép đường trục tiếp tục hoạt động như một khu vực sơ cấp. OSPF là giao thức định tuyến trạng thái liên kết, được thiết kế cho các mạng lớn hoặc các mạng liên hợp và phức tạp. Các giải thuật định tuyến trạng thái sử dụng các giải thuật Shortest Path First (SPF) cùng với một cơ sở dữ liệu phức tạp về cấu hỡnh của mạng. Cơ sở dữ liệu về cấu hỡnh mạng về cơ bản bao gồm tất cả dữ liệu về mạng có liên kết đến bộ định tuyến chứa cơ sở dữ liệu. Giải thuật chọn đường dẫn ngắn nhất SPF là cơ sở cho hệ thống OSPF. Khi 1 bộ định tuyến sử dụng SPF được khởi động, bộ định tuyến sẽ khởi tạo cấu trúc cơ sở dữ liệu của giao thức định tuyến và sau đó đợi chỉ báo từ các giao thức tầng thấp hơn dưới dạng các hàm. Bộ định tuyến sẽ sử dụng các gói tin OSPF Hello để thu nhận các bộ định tuyến lân cận của mỡnh. Bộ định tuyến gửi gói tin Hello đến các lân cận và nhận các bản tin Hello từ các bộ định tuyến lân cận. Ngoài việc sử dụng gói tin Hello để thu nhận các lân cận, bản tin Hello cũn được sử dụng để xác nhận việc mỡnh vẫn đang hoạt động đến các bộ định tuyến khác. Mỗi bộ định tuyến định kỳ gửi các gói thông báo về trạng thái liên kết (LSA) để cung cấp thông tin cho các bộ định tuyến lân cận hoặc cho các bộ định tuyến khác khi một bộ định tuyến thay đổi trạng thái. Bằng việc so sánh trạng thái liên kết của các bộ định tuyến lion kề đ• tồn tại trong cơ sở dữ liệu, các bộ định tuyến bị lỗi sẽ bị phát hiện ra nhanh chóng và cấu hỡnh mạng sẽ được biến đổi thích hợp. Tờ cấu trúc dữ liệu được sinh ra do việc cập nhật liên tục các gói LSA, mỗi bộ định tuyến sẽ tính toán cây đường đi ngắn nhất của mỡnh và tự mỡnh sẽ làm gốc của cõy. Sau đó từ cây đường đi ngắn nhất sẽ sinh ra bảng định tuyến. SV : Phạm Tến Khánh 6
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh 1.1Định tuyến động và thuật toán LSA Định tuyến động lựa chọn tuyến dựa trên thông tin trạng thái hiện thời của mạng. Thông tin trạng thái có thể đo hoặc dự đoán và tuyến đường có thể thay đổi khi topo mạng hoặc lưu lượng mạng thay đổi. Thông tin định tuyến cập nhật vào trong các bảng định tuyến của các nút (node) mạng trực tuyến, và đáp ứng tính thời gian thực nhằm tránh tắc nghẽn cũng như tối ưu hiệu năng mạng. Định tuyến động xây dựng trên hai yếu tố cơ bản: Mô hỡnh tớnh toỏn và thụng tin trạng thỏi 1.2Thuật toán trạng thái liên kết LSA: Trong thuật toỏn trạng thỏi liờn kết, cỏc node mạng quảng bỏ giỏ trị liờn kết của nú với cỏc node xung quanh tới cỏc node khỏc. Sau khi quảng bỏ tất cả cỏc node đều biết rừ topo mạng và thuật toỏn sử dụng để tớnh toỏn con đường ngắn nhất tới node đớch được mụ tả hỡnh thức như sau: Giả thiết : r là node nguồn, d là node đớch Cdr là giỏ thấp nhất từ node r tới đớch d Nrd là node tiếp theo của r trờn đường tới d Crs(r,s) là giỏ của liờn kết từ r tới s, Tớnh toỏn: Bảng định tuyến trong mỗi node r được khởi tạo như sau: Crr = 0; s : s ≠ Nrd thỡ Crs = ∞; Gọi  là tập cỏc nút sau khi thực hiện sau k bước thuật toỏn : Khởi tạo: Crd (r,d) = ∞,  d   Bước 1:  = r Crs(r,s) = Min Crs (r,s); Nrd =s,  r  s; Bước k:  =   w ( w   ) Crd(r,d) = Min [Crs(r,s) + Csd (s,d)] ,  s  . Thuật toỏn dừng khi tất cả cỏc node thuộc  . Khi tớnh toỏn đường đi ngắn nhất sử dụng cỏc thuật toỏn trờn đõy, thụng tin trạng thỏi của mạng thể hiện trong hệ đo lượng (metric), cỏc bộ định tuyến phải được cập nhật giỏ trờn tuyến liờn kết. Một khi cú sự thay đổi topo mạng hoặc lưu lượng cỏc node mạng phải khởi tạo và tớnh toỏn lại tuyến đường đi ngắn nhất, tuỳ theo giao thức được sử dụng trong mạng. 2.So sánh liên kết động và liên kết tĩnh: SV : Phạm Tến Khánh 7
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh Định tuyến động lựa chọn tuyến dựa trên thông tin về trạng thái hiện thời của mạng. Thông tin trạng thái có thể đo hoặc dự đoán và tuyến đường có thể thay đổi khi topo mạng hoặc lưu lượng mạng thay đổi. Thông tin định tuyến cập nhật vào trong các bảng định tuyến của các nút mạng trực tuyến và đáp ứng tính thời gian thực nhằm tránh tắc nghẽn cũng như tối ưu hiệu năng mạng. Định tuyến động xây dựng trên hai yếu tố cơ bản: Mô hình tính toán và thông tin trạng thái. Có hai kiểu mô hình tính toán sử dụng trong định tuyến động là mô hình tập trung và mô hình phân tán. Mô hình tập trung được xây dựng từ hệ thống tính toán định tuyến nhưng trong các điều kiện mạng phát triển rất nhanh và mạnh, mô hình phân tán thực sự chiếm được ưu thế với độ động lớn hơn vì các chức năng định tuyến được thực hiện trên nhiều thực thể mạng, các thông tin được lưu tại nhiều thực thể và vì thế độ tin cậy của mạng tăng lên. Ưu điểm lớn nhất của định tuyến động là nó có thể thiết lập tuyến đường tới tất cả các thiết bị trong mạng, tự động thay đổi tuyến đường khi cấu hình mạng thay đổi. Nó rất thích hợp khi:  Thêm thiết bị và địa chỉ mới vào mạng.  Loại bỏ thiết bị và địa chỉ khỏi mạng.  Tự động cấu hình phù hợp với sự thay đổi của mạng. Trong một mạng phức hợp sử dụng định tuyến động, một mạng có thể bị tái tạo lại cấu hình một cách liên tục vì sự khác nhau về thiết bị và chính sách của rất nhiều nhà khai thác cùng hoạt động. Điều đó có thể gây nên những tổn thất trên mạng về sử dụng tài nguyên. Điều đó cũng có nghĩa là sử dụng định tuyến động cũng sẽ tạo ra sự phức tạp cao nhất. Ví dụ sau nhằm minh hoạ sự cần thiết của định tuyến động trên Internet. Mạng ở hình 1.1 sẽ thích ứng khác nhau đối với các thay đổi về tôpô mạng, tuỳ thuộc việc nó sử dụng cơ chế định tuyến tĩnh hay định tuyến động. R1 R2 R3 R4 SV : Phạm Tến Khánh 8
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh Hỡnh 1.1:mô tả sự thích ứng khác nhau về topo mạng Định tuyến tĩnh cho phép các router định tuyến gói tin từ mạng này tới mạng khác dựa trên các thông tin được cấu hình nhân công. Trong ví dụ này, router R1 luôn gửi lưu lượng có đích là router R4 qua router R3. Router R1 tham chiếu tới bảng định tuyến của nó và dựa theo các thông tin tĩnh để chuyển tiếp gói tới router R3. Router R3 cũng thực hiện các công việc tương tự và chuyển tiếp gói tới router R4. Router R4 chuyển gói tới trạm đích. Nếu đường đi giữa router R1 và router R3 bị lỗi, router R1 không thể chuyển gói tới Router R4 thông qua tuyến tĩnh đó thiết lập này. Như vậy, truyền thông với mạng đích không thể thực hiện được cho đến khi router R1 được cấu hình lại để chuyển gói qua router R2. Đây chính là một nhược điểm của định tuyến tĩnh. Định tuyến động hoạt động linh hoạt hơn. Theo bảng định tuyến của router R1, gói có thể tới đích của nó qua router R3. Tuy nhiên, cũng có một đường đi sẵn khác tới đích, đó là đi qua router R2. Khi router R1 nhận ra rằng liên kết tới router R3 bị lỗi, nó điều chỉnh bảng định tuyến và đường đi tới mạng đích sẽ qua router R2. Khi liên kết giữa router R1 và router R3 được khôi phục, router R1 có thể một lần nữa thay đổi bảng định tuyến để chuyển đường đi tới đích là qua router R3. Định tuyến động sử dụng các giao thức định tuyến để thực hiện xây dựng nên các bảng định tuyến trên các bộ định tuyến. Các giao thức định tuyến động được chia thành 2 nhóm chính: Giao thức định tuyến véctơ khoảng cách và giao thức định tuyến trạng thái liên kết. Ngoài ra còn có nhóm giao thức thứ 3 là nhóm các giao thức định tuyến lai ghép giữa hai nhóm trên hay nói cách khác có các tính chất của cả hai nhóm giao thức: Định tuyến véctơ khoảng cách và định tuyến trạng thái liên kết. 2.1:Giao thức định tuyến vecto khoảng cách (distance-vecto: gọi tắt là định tuyến véctơ): Dựa vào các giải thuật định tuyến có cơ sở hoạt động là véctơ khoảng cách. Theo định kỳ các bộ định tuyến chuyển toàn bộ các thông tin có SV : Phạm Tến Khánh 9
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh trong bảng định tuyến đến các bộ định tuyến lân cận đấu nối trực tiếp với nó và cũng theo định kỳ nhận các bảng định tuyến từ các bộ định tuyến lân cận. Sau khi nhận được các bảng định tuyến từ các bộ định tuyến lân cận, bộ định tuyến sẽ so sánh với bảng định tuyến hiện có và quyết định về việc xây dựng lại các bảng định tuyến theo thuật toán của từng giao thức hay không. Trong trường hợp phải xây dựng lại, bộ định tuyến sau đó sẽ gửi bảng định tuyến mới cho các lân cận và các lân cận lại thực hiện các công việc tương tự. Các bộ định tuyến tự xác định các lân cận trên cơ sở thuật toán và các thông tin thu lượm từ mạng.  Từ việc cần thiết phải gửi các bảng định tuyến mới lại cho các lân cận và các lân cận sau khi xây dựng lại bảng định tuyến lại gửi trở lại bảng định tuyến mới, định tuyến thành vòng có thể xảy ra nếu sự hội về trạng thái bền vững của mạng diễn ra chậm trên một cấu hình mới. Các bộ định tuyến sử dụng các kỹ thuật bộ đếm định thời để đảm bảo không nảy sinh việc xây dựng một bảng định tuyến sai. Có thể diễn giải điều đó như sau:  Khi một bộ định tuyến nhận một cập nhật từ lân cận chỉ rằng một mạng có thể truy xuất trước đây nay không thể truy xuất được nữa, bộ định tuyến đánh dấu tuyến không thể truy xuất và khởi động một bộ định thời.  Nếu tại bất kỳ thời điểm nào mà trước khi bộ định thời hết hạn một cập nhật được tiếp nhận cũng từ lân cận đó chỉ ra rằng mạng đã được truy xuất trở lại, bộ định tuyến đánh dấu là mạng có thể truy xuất và giải phóng bộ định thời.  Nếu một cập nhật đến từ một bộ định tuyến lân cận khác với giá trị định tuyến tốt hơn giá trị định tuyến được ghi cho mạng này, bộ định tuyến đánh dấu mạng có thể truy xuất và giải phóng bộ định thời. Nếu giá trị định tuyến tồi hơn, cập nhật được bỏ qua.  Khi bộ định thời được đếm về 0, giá trị định tuyến mới được xác lập, bộ định tuyến có bảng định tuyến mới. Việc tính toán tuyến trong giao thức định tuyến véctơ khoảng cách sử dụng thuật toán tính toán con đường ngắn nhất theo kỹ thuật chọn đường phân tán mà điển hình là thuật toán chọn đường Ford& Fulkerson. Kỹ thuật chọn đường này cho phép ta tìm tất cả các con đường đi ngắn nhất từ tất cả các đỉnh tới một đỉnh đích cho trước. Giải thuật này được thực hiện bằng các bước lặp, sau k bước, mỗi đỉnh được đánh dấu bởi một cặp giá trị (nk(v),Dk(v)) trong đó: SV : Phạm Tến Khánh 10
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh Dk(v) là giá trị cực tiểu từ đỉnh v đến đích tại bước thứ k Nk(v) là đỉnh tiếp theo trên con đường từ v đến đích tại bước thứ k Quá trình lặp sẽ dừng lại khi cặp giá trị đánh dấu của mỗi đỉnh được giữ nguyên không thay đổi nữa. Thuật toán Ford-Fulkerson được mô tả như sau: -Đầu vào: Đồ thị có hướng G=(V,E) với n đỉnh a(u,v):ma trận trọng số không âm, s là đỉnh đích -Đầu ra:N(v) ghi nhận đỉnh trước v trên đường đi đến đích Bước 0 (Khởi tạo): D0(s)=0 và tất cả các nút đượcđánh dấu (.,vô cùng) Bước k (Tính và cập nhật): Với mọi v khác s (đích), cập nhật lại Dk(v) như sau: Dk(v)=min[Dk-1(w) + l(v,w)] với w thuộc Nv trong đó Nv là tập các nút lân cận của v. Cập nhật nk(v) như sau: nk(v)=w1 với w1 thoả mãn biểu thức” Dk-1(w1)+ l(v,w1)= min[Dk-1(w) + l(v,w)] với w thuộc Nv Kiểm tra điều kiện lặp: Nếu tồn tại Dk(v) khác Dk-1(v) thì tiếp bước (k+1). Ngượclại thì kết thúc quá trình tính toán. 2.2: Các Giao thức định tuyến trạng thái liên kết (link-state: gọi tắt là định tuyến trạng thái): Các giải thuật định tuyến trạng thái, cũng được gọi là SPF (shortest path first-chọn đường dẫn ngắn nhất), duy trì một cơ sở dữ liệu phức tạp chứa thông tin về cấu hình mạng. Trong khi giải thuật véc tơ không có thông tin đặc biệt gì về các mạng ở xa và cũng không biết các bộ định tuyến ở xa, giải SV : Phạm Tến Khánh 11
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh thuật định tuyến trạng thái biết được đầy đủ về các bộ định tuyến ở xa và biết được chúng liên kết với nhau như thế nào. Giao thức định tuyến trạng thái sử dụng:  Các thông báo về trạng thái liên kết: LSA (Link State Advertisements).  Một cơ sở dữ liệu về cấu hình mạng.  Giải thuật SPF và cây SPF sau cùng.  Một bảng định tuyến liên hệ các đường dẫn và các cổng đến từng mạng. Hoạt động tìm hiểu khám phá mạng trong kiểu định tuyến trạng thái được thực hiện như sau:  Các bộ định tuyến trao đổi các LSA cho nhau. Mỗi bộ định tuyến bắt đầu với các mạng được kết nối trực tiếp để lấy thông tin.  Mỗi bộ định tuyến đồng thời với các bộ định tuyến khác tiến hành xây dung một cơ sở dữ liệu về cấu hình mạng bao gồm tất cả các LSA đến từ liên mạng.  Giải thuật SPF tính toán mạng có thể đạt đến. Bộ định tuyến xây dựng cấu hình mạng luận lý như một cây, tự nó là gốc, gồm tất cả các đường dẫn có thể đến mỗi mạng trong toàn bộ mạng đang chạy giao thức định tuyến trạng thái. Sau đó, nó sắp xếp các đường dẫn này theo chiến lược chọn đường dẫn ngắn nhất.  Bộ định tuyến liệt kê các đường dẫn tốt nhất của nó và các cổng dẫn đến các mạng đích trong bảng định tuyến của nó. Nó cũng duy trì các cơ sở dữ liệu khác về các phần tử cấu hình mạng và các chi tiết về hiện trạng của mạng. Khi có thay đổi về cấu hình mạng, bộ định tuyến đầu tiên nhận biết được sự thay đổi này gửi thông tin đến các bộ định tuyến khác hay đến một bộ định tuyến định trước được gán là tham chiếu cho tất cả các bộ định tuyến trên mạng làm căn cứ cập nhật.  Theo dõi các lân cận của nó, xem xét có hoạt động hay không, và giá trị định tuyến đến lân cận đó. SV : Phạm Tến Khánh 12
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh  Tạo một gói LSA trong đó liệt kê tên của tất cả các bộ định tuyến lân cận và các giá trị định tuyến đối với các lân cận mới, các thay đổi trong giá trị định tuyến và các liên kết dẫn đến các lân cận đã được ghi.  Gửi gói LSA này đi sao cho tất cả các bộ định tuyến đều nhận được.  Khi nhận 1 gói LSA, ghi gói LSA vào cơ sở dữ liệu để sao cho cập nhật gói LSA mới nhất được phát ra từ mỗi bộ định tuyến.  Hoàn thành bản đồ của liên mạng bằng cách dùng dữ liệu từ các gói LSA tích luỹ được và sau đó tính toán các tuyến dần đến tất cả các mạng khác sử dụng thuật toán SPF. Có hai vấn đề lưu ý đối với giao thức định tuyến trạng thái:  Hoạt động của các giao thức định tuyến trạng thái trong hầu hết các trường hợp đều yêu cầu các bộ định tuyến dùng nhiều bộ nhớ và thực thi nhiều hơn so với các giao thức định tuyến theo véc tơ. Các yêu cầu này xuất phát từ việc cần thiết phải lưu trữ thông tin của tất cả các lân cận, cơ sở dữ liệu mạng đến từ các nơi khác và thực thi các thuật toán định tuyến trạng thái. Người quản lý mạng phải đảm bảo rằng các bộ định tuyến mà họ chọn có khả năng cung cấp các tài nguyên cần thiết này.  Các nhu cầu về băng thông cần phải tiêu tốn để khởi động sự phát tán gói trạng thái. Trong khi khởi động quá trình khám phá, tất cả các bộ định tuyến dùng các giao thức định tuyến trạng thái để gửi các gói LSA đến tất cả các bộ định tuyến khác. Hành động này làm tràn ngập mạng khi mà các bộ định tuyến đồng loạt yêu cầu băng thông và tạm thời làm giảm lượng băng thông khả dụng dùng cho lưu lượng dữ liệu thực được định tuyến. Sau khởi động phát tán này, các giao thức định tuyến trạng thái thường chỉ yêu cầu một lượng băng thông tối thiểu để gửi các gói LSA kích hoạt sự kiện không thường xuyên nhằm phản ánh sự thay đổi của cấu hình mạng. Việc tính toán tuyến trong giao thức định tuyến véctơ khoảng cách sử dụng thuật toán tính toán con đường ngắn nhất theo kỹ thuật chọn đường tập trung mà điển hình là thuật toán tìm đường đi ngắn nhất Dijkstra. Thuật toán được đưa ra để tìm đường đi ngắn nhất từ đỉnh s đến tất cả các đỉnh còn lại trong đồ thị có hướng dựa SV : Phạm Tến Khánh 13
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh trên cơ sở gán cho các đỉnh các nhãn tạm thời (Khác với Ford&Fulkerson tìm đường đi từ tất cả các đỉnh đến 1 đích). Thuật toán Dijkstra được mô tả như sau: -Đầu vào: Đồ thị có hướng G=(V,E) với n đỉnh s thuộc V là đỉnh xuất phát, a[u,v]: ma trận trọng số d(v) là khoảng cách từ đỉnh xuất phát s đến v -Đầu ra: Truoc[v]:ghi nhận đỉnh đi trước v trong đường đi ngắn nhất từ sv Bước 0 (Khởi động): N0={s} D0(v)=l(s,v) với v không thuộc N0 Bước k (Tính và cập nhật): Nk=Nk-1 giao {w} trong đó w thoả mãn biểu thức: Dk-1(w)=min[Dk-1(v)] với v o thuộc Nk-1 Cập nhật: với mọi v o thuộc Nk: Dk(v)= min [Dk-1(v), Dk-1(w)+l(w,v)] Kiểm tra điều kiện lặp: Nếu Nk khác V thì lặp bước k+1 ngược lại thì dừng quá trình tính toán. 3:V ùng OSPF Hình1.2 :miêu tả đơn mạng OSPF Trong một mạng OSPF có thẻ được chia ra làm hai vùng chính .Vùng mạng lõi ( vùng sơ cấp) và vùng thứ cấp .Trong hai vùng này có khả năng thay đổi .Khi mạng SV : Phạm Tến Khánh 14
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh lõi bi lỗi thì người quản trị sẽ tạo ra một liên kết ảo và chạy liên kết ảo này như một mạng lõi thông thường 4:Kiểu router Có 3 kiểu router trong một mạng OSPF ,Chúng đóng vai trò khác nhau trong một mạng OSPF đó là : Router mạng lõi Router biên khu vực Router nội miền Hình1.3 : chỉ ra 3 kiểu router Như trên hình ta thấy ,mạng được chia thành 3 vùng, vùng 0, vùng1, vùng2 Trong hình trên đã chỉ ra 3 liểu router gồm :router mạng lõi (Backbone- router) , Router biên khu vực (Area boder router), router nội miền(Internal router) 5:Kiểu đ ịnh tuyến Trên hình trên ta đã thấy có 3 liểu router khac nhau.Nhưng chỉ có 2 kiểu định tuyến cho mạng sử dụng OSPF Định tuyến nội miền Định tuyến liên miền Định tuyến miền trong Có nghĩa là định tuyến trong nội miền SV : Phạm Tến Khánh 15
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh Hình1.4 biểu thị định tuyến miền trong Như hình trên thì một PC muốn truy nhập đến một sever trong nội miền thì router trong miền đó sẽ hướng tuyến đi trong miền mà không hướng ra ngoài Định tuyến liên miền Trong định tuyến liên miền ta nhận thấy rõ một vùng tự trị được phân làm 3 khu vực Khu vực 1 Khu vực 2 Router biên khu vực Tới AS khác Khu vực đường trục Router đường trục Router biên AS Hệ thống tự trị (AS) Hình 1.5: Các khu vực trong một hệ thống tự trị Trong đó quan trọng nhất là khu vực mạng lõi hay khu vực đường trục Ví dụ về địng tuyến mạng ngoài : SV : Phạm Tến Khánh 16

CÓ THỂ BẠN MUỐN DOWNLOAD