Luận văn Tìm hiểu các giao thức định tuyến trên nền công nghệ Cisco

A. CƠ SỞ LÝ THUYẾT LÝ THUYẾT VÀ THUẬT TOÁN ĐỊNH TUYẾN (ROUTING) Khái niệm cơ bản Khái niệm cơ bản về routing Định nghĩa routing Định tuyến (Routing) là tiến trình hướng các gói (packet) từ mạng này đến mạng khác thông qua router. Routing hoạt động ở lớp thứ ba của mô hình OSI (lớp network) và là một chức năng quan trọng của router trong lớp network. Router là thiết bị mạng hoạt động ở lớp network và sử dụng chức năng routing để truyền thông với router của những mạng khác. Địa chỉ vật lý được router sử dụng để xác định các hệ thống mạng cũng như từng thiết bị trong hệ thống mạng này. Hình 1.1 Mô hình OSI Routing thường được so sánh với switching (chuyển gói) vì hai chức năng này đều cùng hoạt động trên router. Điểm khác biệt cơ bản là routing có chức năng tìm đường còn switching thì có chức năng gửi gói tin (packet) đi ra khỏi interface của router để đến đích. Nguyên tắc hoạt động của switching sẽ được trình bày ở phần dưới đây. Bảng định tuyến Là bảng chứa các thông tin về mạng mà router đang kết nối và mạng đích. Router sẽ tìm trong bảng định tuyến để quyết định đường đi của packet. Ví dụ về bảng định tuyến: Mạng đích Subnet mask Gateway Flags Interface 10.1.2.0 255.255.255.0 10.1.2.1 U eth0 10.1.1.0 255.255.255.0 10.1.1.1 U To0 10.8.4.0 255.255.255.0 10.8.4.1 U S0 Hình 1.2. Ví dụ về bảng định tuyến. Nguyên tắc định tuyến Sau khi router nhận một gói tin , để định tuyến ta cần phải giải quyết các vấn đề sau: Giao thức định tuyến cho gói tin thuộc về giao thức đó có được cài đặt trên router và đang hoạt động hay không? Và giao thức định tuyến này có thể hoạt động trong môitrường nào? (IP, IPX, AppleTalk…). Nếu giao thức định tuyến đã được cài đặt thì đường đi nào đến một hệ thống mạng ở xa tồn tại trong bảng định tuyến hay không? Nếu địa chỉ mạng đích không có trong bảng định tuyến, có tuyến đường mặc định nào được cấu hình trên router hay không? Nếu có thì địa chỉ đích có đến được không? Nếu địa chỉ mạng đích nằm trong bảng định tuyến thì interface nào trên router mà packet sẽ được truyền đi? Nếu có nhiều đường đi để đến mạng đích , router sẽ chọn đường nào? Khi không có đường đi nào để đến mạng đích, router sẽ huỷ bỏ packet và gửi một thông điệp ICMP (Internet Control Message Protocol) đến mạng nguồn. Mỗi lần packet được hướng vào hoặc hướng đến interface được chọn, router phải gói gọn packet vào trong một vị trí nào đó. Kỹ thuật này được gọi là truyền theo khung (framing) và nó được yêu cầu để hướng packet đến hop kế tiếp của thiết bị vật lý. Mỗi lần packet được truyền theo khung, nó sẽ truyền theo hướng từ hop đến hop (hop được hiểu là liên kết giữa 2 router) cho đến khi nó đến được thiết bị đích cuối cùng. Bảng định tuyến được sử dụng để chuyển packet đến chính xác hệ thống mạng cần đến. Router – chức năng và nguyên tắc hoạt động Router là thiết bị mạng truyền thông trực tiếp giữa các host. Router hoạt động ở tầng thứ ba (Network Layer) của mô hình OSI. Router xây dựng những bảng định tuyến chứa những thông tin được chọn lọc về những đường đi tối ưu để tới nơi cần đến và làm cách nào để đi tới đó. Router được chế tạo với hai mục đích chính: Phân cách các mạng máy tính thành các segment riêng biệt để giảm hiện tượng đụng độ và thực hiện chức năng bảo mật. Kết nối các mạng máy tính hay kết nối người sử dụng với mạng máy tính ở các khoảng cách xa với nhau thông qua các đường truyền thông: điện thoại, ISDN, T1, X.25… Router có các chức năng: Xác định đường đi (Path determination). Sự chuyển hướng (Switching). Xác định đường đi Hình 1.3. Sự kết hợp với hop kế tiếp (hay hop đích) xác định đường truyền tối ưu Như đã được đề cập ở phần trên, router có nhiệm vụ chuyển dữ liệu theo một đường liên kết tối ưu. Đối với một hệ thống gồm nhiều router kết nối với nhau, trong đó các router có nhiều hơn hai đường liên kết với nhau, vấn đề xác định đường truyền dữ liệu (path determination) tối ưu đóng vai trò rất quan trọng. Router phải có khả năng lựa chọn đường liên kết tối ưu nhất trong tất cả các đường có thể, mà dữ liệu có thể truyền đến đích nhanh nhất. Việc xác định đường dựa trên các thuật toán routing, các giao thức định tuyến, từ đó rút ra được một số đo gọi là metric để so sánh giữa các đường với nhau. Sau khi thực hiện việc kiểm tra trạng thái của các đường liên kết bằng các thuật toán dựa trên giao thức định tuyến, router sẽ rút ra được các metric tương ứng cho mỗi đường, cập nhật vào routing table. Router sẽ chọn đường nào có metric nhỏ nhất để truyền dữ liệu. Sự chuyển mạch Quá trình chuyển dữ liệu (switching) là quá trình cơ bản của router, được dựa trên ARP protocol. Khi một máy muốn gửi packet qua router cho một máy thuộc mạng khác, nó gửi packet đó đến router theo địa chỉ MAC của router, kèm theo địa chỉ protocol (network address) của máy nhận. Router sẽ xem xét network address của máy nhận để biết xem nó thuộc mạng nào. Nếu router không biết được phải chuyển packet đi đâu, nó sẽ loại bỏ packet. Nếu router nhận thấy có thể chuyển packet đến đích, nó sẽ bổ sung địa chỉ MAC của máy nhận vào packet và gởi packet đi. Việc chuyển dữ liệu có thể phải đi qua nhiều router, khi đó mỗi router phải biết được thông tin về tất cả các mạng mà nó có thể truyền dữ liệu tới. Vì vậy, các thông tin của mỗi router về các mạng nối trực tiếp với nó sẽ phải được gửi đến cho tất cả các router trong cùng một hệ thống. Trong quá trình truyền địa chỉ MAC của packet luôn thay đổi nhưng địa chỉ network sẽ không thay đổi. Hình 1.4. Quá trình truyền dữ liệu qua hệ thốnggồm nhiều router. Nguyên tắc hoạt động của router Để định tuyến, một router cần phải: Biết được địa chỉ đích. Xác định cách tìm đường mà nó có thể học. Tìm ra đường đi có thể thực hiện. Chọn con đường tối ưu. Duy trì và kiểm tra lại thông tin định tuyến. Sau đó router sẽ chuyển packet theo các bước sau: Đọc packet. Gỡ bỏ dạng format quy định bởi protocol của nơi gửi. Thay thế phần gỡ bỏ đó bằng dạng format của protocol của đích đến. Cập nhật thông tin về việc chuyển dữ liệu: địa chỉ, trạng thái của nơi gửi, nơi nhận. Gứi packet đến nơi nhận qua đường truyền tối ưu nhất. Sau đây là nguyên tắc hoạt động của router: Router chạy chương trình được nạp vào như giao thức định tuyến để truyền và nhận thông tin đã được định hướng đi và từ những router khác trong mạng. Các router sử dụng thông tin này để quảng cáo bảng định tuyến để có thể liên kết với nhau. Router sẽ tìm trong bảng định tuyến từ những giao thức định tuyến khác (nếu có hơn một giao thức định tuyến đang hoạt động) và chọn ra đường đi tối ưu đến mỗi đích đến. Router kết hợp với thiết bị đích của hop kế tiếp gắn liền với địa chỉ lớp liên kết dữ liệu (data link) và giao diện cục bộ được sử dụng khi hướng packet đến đích. Lưu ý rằng thiết bị của hop kế tiếp có thể là một router khác, hoặc có thể là máy chủ đích. Thiết bị của hop kế tiếp định hướng thông tin (trên giao diện nơi đến của địa chỉ lớp liên kết dữ liệu) và đưa vào bảng định hướng router. Khi router nhận được một packet, router sẽ kiểm tra thông tin của phần header của packet để xác định địa chỉ đích. Router tìm trong bảng định hướng chứa giao diện nơi đến và địa chỉ hop kế tiếp để tìm đích đến. Router sẽ tìm bất kỳ chức năng thêm vào được yêu cầu (như là sự giảm bớt TTL IP hay là thao tác thiết lập TOS IP) và hướng packet đến thiết bị thích hợp. Điều này tiếp tục cho đến khi máy chủ đích được tìm thấy. Phương thức này giống như mô hình định tuyến hop-by-hop mà thường được sử dụng trong mạng chuyển hướng packet. Hình 1.5. Router phải học đường đến đích khi mà nó chưa kết nối đến. Address Resolution Protocol (ARP) và nguyên tắc hoạt động Như ta đã biết tại tầng network của mô hình OSI, chúng ta thường sử dụng các loại địa chỉ mang tính chất quy ước như IP, IPX… Các địa chỉ này là các địa chỉ có hướng, nghĩa là chúng được phân thành hai phần riêng biệt là phần địa chỉ network và phần địa chỉ host. Cách đánh số địa chỉ như vậy nhằm giúp cho việc tìm ra các đường kết nối từ hệ thống mạng này sang hệ thống mạng khác được dễ dàng hơn. Các địa chỉ này có thể được thay đổi theo tùy ý người sử dụng. Trên thực tế, các card mạng chỉ có thể kết nối với nhau theo địa chỉ MAC, địa chỉ cố định và duy nhất của phần cứng. Do vậy ta phải có một phương pháp để chuyển đổi các dạng địa chỉ này qua lại với nhau. Từ đó ta có giao thức phân giải địa chỉ: Address Resolution Protocol (ARP). ARP là một protocol dựa trên nguyên tắc: Khi một thiết bị mạng muốn biết địa chỉ MAC của một thiết bị mạng nào đó mà nó đã biết địa chỉ ở tầng network (IP, IPX…) nó sẽ gửi một ARP request bao gồm địa chỉ MAC address của nó và địa chỉ IP của thiết bị mà nó cần biết MAC address trên toàn bộ một miền broadcast. Mỗi một thiết bị nhận được request này sẽ so sánh địa chỉ IP trong request với địa chỉ tầng network của mình. Nếu trùng địa chỉ thì thiết bị đó phải gửi ngược lại cho thiết bị gửi ARP request một packet (trong đó có chứa địa chỉ MAC của mình). Trong một hệ thống mạng đơn giản như hình 1.6, ví dụ như máy A muốn gửi packet đến máy B và nó chỉ biết được địa chỉ IP của máy B. Khi đó máy A sẽ phải gửi một ARP broadcast cho toàn mạng để hỏi xem “địa chỉ MAC của máy có địa chỉ IP này là gì” Khi máy B nhận được broadcast này, nó sẽ so sánh địa chỉ IP trong packet này với địa chỉ IP của mình. Nhận thấy địa chỉ đó là địa chỉ của mình, máy B sẽ gửi lại một packet cho máy B trong đó có chứa địa chỉ MAC của B. Sau đó máy A mới bắt đầu truyền packet cho B. Hình 1.6 Ví dụ truyền nhận packet giữa các host. Trong một môi trường phức tạp hơn (hình 1.7): hai hệ thống mạng gắn với nhau thông qua một router C. Máy A thuộc mạng A muốn gửi packet đến máy B thuộc mạngB. Do các broadcast không thể truyền qua router nên khi đó máy A sẽ xem router C như một cầu nối để truyền dữ liệu. Trước đó, máy A sẽ biết được địa chỉ IP của router C (port X) và biết được rằng để truyền packet tới B phải đi qua C. Tất cả các thông tin như vậy sẽ được chứa trong một bảng gọi là bảng routing (routing table). Bảng định tuyến theo cơ chế này được lưu giữ trong mỗi máy. Bảng định tuyến chứa thông tin về các gateway để truy cập vào một hệ thống mạng nào đó. Ví dụ trong trường hợp trên trong bảng sẽ chỉ ra rằng để đi tới LAN B phải qua port X của router C. Bảng định tuyến sẽ có chứa địa chỉ IP của port X. Quá trình truyền dữ liệu theo từng bước sau: Máy A gửi một ARP request (broadcast) để tìm địa chỉ MAC của port X. Router C trả lời, cung cấp cho máy A địa chỉ MAC của port X. Máy A truyền packet đến port X của router. Router nhận được packet từ máy A và chuyển packet ra port Y của router, trong packet có chứa địa chỉ IP của máy B. Router sẽ gửi ARP request để tìm địa chỉ MAC của máy B. Máy B sẽ trả lời cho router biết địa chỉ MAC của mình. Sau khi nhận được địa chỉ MAC của máy B, router C gửi packet của máy A đến máy B. Hình 1.7. Ví dụ về truyền nhận packet giữa các host thông qua router . Trên thực tế ngoài dạng bảng định tuyến này người ta còn dùng phương pháp proxy ARP, trong đó có một thiết bị đảm nhận nhiệm vụ phân giải địa chỉ cho tất cả các thiết bị khác. Quá trình này được trình bày trong hình 1.8. Hình 1.8. Phân giải địa chỉ dùng proxy ARP. Theo đó các máy trạm không cần giữ bảng routing table nữa router C sẽ có nhiệm vụ thực hiện, trả lời tất cả các ARP request của tất cả các máy trong các mạng kết nối với nó. Router sẽ có một bảng định tuyến riêng biệt chứa tất cả các thông tin cần thiết để chuyển dữ liệu. IP routing – Định tuyến trong môi trường IP Khái niệm về IP routing Internet là mạng toàn cầu bao gồm nhiều nhóm mạng liên kết với nhau, cho phép truyền thông giữa hầu hết các công ty, các tổ chức nghiên cứu, các trường đại học và rất nhiều tổ chức khác trên thế giới. Router có thể được sử dụng để kết nối các mạng riêng với nhau dưới sự quản lý của nhà quản trị. Router được sử dụng trong trao đổi thông tin trong mạng riêng được gọi là router trong, sử dụng những giao thức cổng trong Interior Gateway Protocol (IGP). Router được sử dụng để truyền thông tin giữa các hệ thống nội bộ (Autonomous Sytem) được gọi là router ngoài, và sử dụng giao thức cổng ngoài Exterior Gateway Protocol (EGP) hay là giao thức cổng biên Border Gateway Protocol (BGP). Định tuyến trong môi trường IP có thể là định tuyến động hoặc định tuyến tĩnh. Định tuyến động (dynamic routing) sử dụng các giao thức định tuyến được tích hợp trong router để tính toán đường đi. Do vậy định tuyến động thích ứng với những thay đổi trong mạng và tự động chọn đường đi tối ưu. Ngược lại định tuyến tĩnh được thiết lập trên router bởi nhà quản trị mạng. Định tuyến tĩnh không thay đổi cho đến khi nhà quản trị mạng thay đổi chúng. Hệ thống nội bộ – Autonomous System (AS) Hệ thống nội bộ là một nhóm mạng riêng, có thể là một công ty, có thể là một nhóm trong công ty, và cũng có thể là một nhóm các công ty với nhau. Giao thức dạng IGP chỉ đến một giao thức định tuyến để xử lý định tuyến trong một mạng nội bộ. Giao thức dạng IGP bao gồm RIP, IGRP, EIGRP, OSPF. Giao thức dạng EGP xử lý định tuyến giữa các hệ thống nội bộ khác nhau. Giao thức dạng EGP là BGP. BGP được sử dụng để định tuyến đường truyền dọc theo xương sống (backbone) của Internet giữa các mạng nội bộ khác nhau. Không phải tất cả giao thức định tuyến đều hiểu được về AS. Một AS có thể cung cấp những đường biên riêng cho một giao thức định tuyến, và một số thuận lợi nhất định.Ví dụ như ta có thể quản lý khi mạng được quảng cáo rộng rãi bởi router. Thêm vào đó ta có thể quản lý việc router nào sẽ quảng cáo đến hệ thống nội bộ khác và định tuyến từ những hệ thống này. Để phân biệt các hệ thống nội bộ với nhau thì một AS được cấp một số duy nhất từ 1 đến 65535. Hệ thống cấp số trên Internet gọi là Internet Assigned Numbers Authority (IANA) sẽ cung cấp số cho các hệ thống nội bộ. Giống như địa chỉ IP riêng và chung, ta cũng có số AS chung và riêng. Nếu ta kết nối đến backbone của Internet, và chạy BGP, và muốn chấp nhận BGP định tuyến từ Internet, ta sẽ cần một số AS chung. Tuy nhiên nếu ta chỉ cần chạy mạng nội bộ trong hệ thống khác, thì chỉ cần dùng số AS riêng. Giao thức định tuyến hiểu được AS là IGRP, EIGRP, OSPF, IS-IS, BGP. RIP không hiểu hệ thống AS, OSPF thì hiểu nhưng OSPF không yêu cầu ta phải cấu hình số AS, ngược lại IGRP và EIGRP thì lại yêu cầu số AS. Internet Control Message Protocol - ICMP Như chúng ta thấy, định tuyến IP xác định biểu đồ di chuyển trong một mạng nội bộ đến hop của một router tại một thời điểm. Toàn bộ đường đi không biết trước thời điểm bắt đầu. Thay vì vậy, tại mỗi lần dừng, hop của router kế tiếp được xác định bằng cách tìm địa chỉ đích trong biểu đồ với một entry trong nút hiện tại của bảng routing. Mỗi nút trong tiến trình định tuyến chỉ hướng packets dựa trên thông tin ở bên trong. IP không cung cấp bảng thông báo lỗi ngược trở lại nguồn khi có sự định tuyến khác thường xảy ra. Nhiệm vụ này được chuyển đến giao thức Internet khác — đó là giao thức quản lý thông điệp trên Internet (Internet Control Message Protocol – ICMP). ICMP thực hiện một số nhiệm vụ ở một mạng riêng trong môi trường IP. Đó là lý do chính để tạo ra bảng thông báo lỗi định tuyến gửi ngược lại nơi bắt đầu. Thuật toán routing Mục đích và yêu cầu Tínhï tối ưu Tính đơn giản và chi phí thấp Tính ổn định Tính hội tụ nhanh Tính linh hoạt Tính tối ưu Là khả năng chọn đường truyền tốt nhất của thuật toán.Mỗi một thuật toán có thể có cách phân tích đường truyền với các số đo riêng, khác biệt với các thuật toán khác, tuy nhiên mục đích chính vẫn là để xác định đường truyền nào là đường truyền tốt nhất. Ví dụ một thuật toán định tuyến có thể sử dụng số hop và thời gian chờ, nhưng nó có thể mất thời gian lâu hơn để tính toán. Tất nhiên là những giao thức định tuyến phải định nghĩa các thuật toán một cách chính xác. Tính đơn giản và chi phí thấp Một thuật toán đòi hỏi phải đơn giản, dễ thực hiện, tính hiệu quả cao, ít chiếm dụng băng thông đường truyền, giảm thiểu chi phí đến mức tối đa trong đó tính hiệu quả là rất quan trọng trong việc sử đụng thuật toán. Tính ổn định, nhanh chóng, chính xác Thuật toán phải ổn định và chính xác để bảo đảm hoạt động tốt khi xảy ra các trường hợp hư hỏng phần cứng, quá tải đường truyền … bởi vì các router được đặt ở các điểm giao của các mạng nên khi router bị lỗi sẽ gây ra ảnh hưởng rất nghiêm trọng. Thuật toán tối ưu phải được kiểm tra qua thời gian sử dụng và hoạt động ổn định trong những điều kiện mạng khác nhau.Mặt khác thuật toán phải bảo đảm sự nhanh chóng để tránh tình trạng lặp trên đường truyền do không cập nhật kịp trạng thái đường truyền. Tính hội tụ nhanh Thuật toán đòi hỏi tính hội tụ nhanh. Sự hội tụ nhanh là tiến trình qui ước của tất cả các router trên đường đi tối ưu. Trong quá trình định tuyến, router sẽ cập nhật thông điệp định tuyến khắp trên mạng, để tính toán lại đường đi tối ưu và cuối cùng yêu cầu để tất cả router chấp nhận đường đi đó. Thuật toán định tuyến mà có tính hội tụ chậm có thể gay ra lặp định tuyến hoặc là mạng ngưng hoạt động. Trong hình 2.1, một packet được chuyển đến router 1 tại thời điểm t1.Router 1 đã được cập nhật định hướng và biết được đường đi tối ưu đến đích phải qua router 2 và hướng packet đến router 2, nhưng bởi vì router 2 chưa được cập nhật nên nó chỉ biết hop tối ưu kế tiếp là router 1. Vì thế router 2 hướng packet trở lại router 1, và packet cứ được đưa qua lại như thế giữa router 1 và router 2 cho đến khi router 2 nhận được cập nhật định hướng của nó hoặc là đến khi packet bị chuyển hướng vì đã vượt quá thời gian cho phép. Thời gian để đến mạng Nơi gửi đến 27 Node A 57 Node B 17 Node C 24 Node A 52 Node A 16 Node B 26 Node A . . Hình1.9. Sự hội tụ chậm và lặp định tuyến làm trở ngại tiến trình định tuyến. Tính linh hoạt Tính năng này bảo đảm sự thay đổi kịp thời và linh hoạt trong bất cứ mọi trường hợp xảy ra trong hệ thống. Ví dụ có một nhánh mạng không hoạt động. Nếu như một thuật toán định tuyến có thể biết được vấn đề, chúng sẽ nhanh chóng chọn đường đi tối ưu tiếp theo cho tất cả các router đang hoạt động trên nhánh mạng đó. Thuật toán định tuyến có thể được lập trình để thay đổi băng thông trên mạng, kích thước hàng đợi router và thời gian chờ trên mạng và những thay đổi khác … Các kiểu thuật toán routing Static hay dynamic Single path hay Multipath Flat hay Hierachical Link State hay Distance Vector. Host - intelligent hay Router - intelligent Intradomain hay Interdomain Static hay dynamic Thuật toán Static Static routing là cơ chế trong đó người quản trị quyết định, gán sẵn protocol cũng như địa chỉ đích cho router: đến mạng nào thì phải truyền qua port nào, địa chỉ là gì… Các thông tin này chứa trong routing table và chỉ được cập nhật hay thay đổi bởi người quản trị. Static routing thích hợp cho các hệ thống đơn giản, có kết nối đơn giữa hai router, trong đó đường truyền dữ liệu đã được xác định trước. Thuật toán Dynamic Dynamic routing dùng các giao thức định tuyến để tự động cập nhật các thông tin về các router xung quanh. Tùy theo dạng thuật toán mà cơ chế cập nhật thông tin của các router sẽ khác nhau. Dynamic routing thường dùng trong các hệ thống phức tạp hơn, trong đó các router được liên kết với nhau thành một mạng lưới, ví dụ như các hệ thống router cung cấp dịch vụ internet, hệ thống của các công ty đa quốc gia. Single path hay Multipath Thuật toán Single path Thuật toán single path không thể tổng hợp dữ liệu trên nhiều liên kết khác nhau nên lưu lượng dữ liệu không đủ và độ tin cậy không cao. Thuật toán Multipath Thuật toán multipath cho phép việc tổng hợp dữ liệu trên nhiều liên kết khác nhau. Multi path cung cấp một lưu luợng dữ liệu và độ tin cậy cao hơn single path. Flat hay Hierarchical Thuật toán Flat Thuật toán flat routing dùng trong các hệ thống có cấu trúc ngang hàng với nhau, được trải rộng với chức năng và nhiệm vụ như nhau.Thuật toán flat thường chỉ được dùng ở những mô hình mạng ngang hàng nhỏ. Thuật toán Hierachical Thuật toán hierachical là thuật toán phân cấp, có cấu trúc cây như mô hình phân cấp của một domain hay của một công ty. Tùy theo dạng hệ thống mà ta có thể lựa chọn thuật toán thích hợp. Hệ thống định tuyến định rõ các nút của nhóm logic gọi là domain, hệ thống nội bộ hoặc là vùng. Trong hệ thống hierarchical, một vài router trong một domain có thể truyền thông với các router trong domain khác, trong khi những router còn lại chỉ có thể truyền với các router trong cùng domain. Trong hệ thống mạng lớn, các mức hierarchical có thể tồn tại, cùng với router tại mức hierarchical cao nhất để định hình backbone của routing. Lợi ích chính của hierarchical routing là giả lập như tổ chức của các công ty và do vậy nó hỗ trợ mô hình truyền thông tốt. Hầu hết sự truyền thông mạng hiện nay là trong những nhóm công ty nhỏ (domain). Link State or Distance Vector Thuật toán Link State  Hình 1.10. Thuật toán Link-state. Thuật toán link state (còn được gọi là thuật toán shortest path first) cập nhật tất cả các thông tin vể cơ chế routing cho tất cả các nút trên hệ thống mạng. Mỗi router sẽ gửi một phần của routing table, trong đó mô tả trạng thái của các liên kết riêng của mình lên trên mạng. Chỉ có các thay đổi mới được gửi đi. Về mặt bản chất, thuật toán link state gửi các bảng cập nhật có kích thước nhỏ đến khắp nơi trong mạng. Thuật toán link state có ưu điểm là có tốc độ cao, không chiếm dụng băng thông nhiều như thuật toán distance vector. Tuy nhiên thuật toán này đòi hỏi cao hơn về bộ nhớ, CPU cũng như việc thực hiện khá phức tạp. Thuật toán link state được sử dụng trong giao thức định tuyến: OSPF, NLSP… và thích hợp cho các hệ thống cỡ trung và lớn. Thuật toán Distance Vector Hình 1.11. Thuật toán Distance Vector. Thuật toán distance vector (còn gọi là thuật toán Bellman-Ford) bắt buộc mỗi router phải gửi toàn bộ hay một phần routing table của mình cho router kết nối trực tiếp với nó theo một chu kỳ nhất định (Hình 2.3) Về mặt bản chất, thuật toán distance vector gửi các bảng cập nhật có kích thước lớn hơn chỉ cho router kết nối với nó. Thuật toán distance vector có ưu điểm là dễ thực hiệ