OSPF – The Open Shortest Path First là giao thức định tuyến nội miền (IGP – interior Gateway) được sử dụng để phân phối thông tin định tuyến trong một AS (Autonomous System – miền tự trị).
Giao thức OSPF dựa trên công nghệ trạng thái đường link (link-state). Link State là giao thức xây dựng đường đi tốt nhất (Shortest path first) thông qua giải thuật Dijkstra. Các router chỉ cần trao đổi thông tin của nhau qua gói tin Hello mà không cần gửi cả bảng định tuyến. Sau khi có thông tin nó sẽ xây dựng ra một bảng định tuyến và đường đi tốt nhất.
Tất cả router trong mạng gửi đi bản tin LSAs (link-state advertisements) đến các route lân cận. Các bản tin LSA nhận được sẽ được lưu trữ trong một database local gọi là LSDB (link-state database). Sau một thời gian trao đổi, các router sẽ đồng nhất được bảng cơ sở dữ liệu trạng thái đường link (Link State Database – LSDB) với nhau, mỗi router đều có được bản đồ mạng của cả vùng. Từ đó mỗi router sẽ chạy giải thuật Dijkstra tính toán ra một cây đường đi ngắn nhất (Shortest Path Tree) và dựa vào cây này để xây dựng nên bảng định tuyến.Tất cả router trong mạng gửi đi bản tin LSAs (link-state advertisements) đến các route lân cận. Các bản tin LSA nhận được sẽ được lưu trữ trong một database local gọi là LSDB (link-state database). Sau một thời gian trao đổi, các router sẽ đồng nhất được bảng cơ sở dữ liệu trạng thái đường link (Link State Database – LSDB) với nhau, mỗi router đều có được bản đồ mạng của cả vùng. Từ đó mỗi router sẽ chạy giải thuật Dijkstra tính toán ra một cây đường đi ngắn nhất (Shortest Path Tree) và dựa vào cây này để xây dựng nên bảng định tuyến.
Dijkstra’s Shortest Part First algorithm: OSPF sử dụng thuật toán Dijktra để tìm đường đi ngắn nhất từ root (router thực hiện thuật toán) đến các node mạng trong topo mạng mà nó học được khi Exchange link-state database. Nguyên tắc cơ bản của thuật toán dựa trên nhận xét “để đi từ nguồn tới đích thì path từ root đến từng node trên đường đi cũng phải là ngắn nhất”. Từ nhận xét trên, thuật toán này sẽ thực hiện tìm đường ngắn nhất đến các node lân cận nó trước, sau đó sẽ tiếp tục tìm đường ngắn nhất đến các node lân cận vừa tìm được. Cứ như vậy cho đến khi tìm được đường ngắn nhất đến tất cả các node trọng mạng.
Leaf-node: Trên một “cây” đường đi, OSPF coi các LSA Type 3, 4, 5 và 7 là các leaf-node.
1 giờ ago
