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 3
SV: Phạm Tiến Khánh- A06300
2
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

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

Kiểu thuật
toán
Không DVP DVP DVP DUAL LSP LSP DVP
Hỗ chợ địa chỉ
Có Có Có Có Có Có Có Có
Hỗ trợ CIDRR
và VLSM
Có Không Có Không Có Không Có Có
SV : Phạm Tến Khánh 3
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh
Hỗ chợ chia
tải
Không Không Không Có Có Có Có Có
Hỗ chợ chứng
thực
Không Không Có Không Có Có Có Có
Cho phép đánh
trọng số
Không Không Không Có Có Có Có Có
Hội tụ nhanh
Không Không Không Có Có Có Có Có
Thủ tục mời
chào cho
Router láng
riềng
Không
Không Không Không Có Có Có Không
Sử dụng quảng
bá cho việc
cập nhật bảng

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.
SV : Phạm Tến Khánh 5
Hệ thống tự trị (AS)
Khu vực 1
Khu vực 2
Router biên khu vực
Khu vực đường trục
Router đường trục
Tới AS
khác
Router
biên AS
Hình 1.0: Các khu vực trong một hệ thống tự trị
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh

SV : Phạm Tến Khánh 6
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh
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
C
d
r
là giỏ thấp nhất từ node r tới đớch d
N
r
d
là node tiếp theo của r trờn đường tới d
C
r
s
(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:
C
r
r

d
=s,
∀
r
≠
s;
Bước k:
Ω
=
Ω

∪
w ( w
∉
Ω
)
C
r
d
(r,d) = Min [C
r
s
(r,s) + C
s
d
(s,d)] ,
∀
s
∉
Ω

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.

SV : Phạm Tến Khánh 8
R1 R2
R3
R4
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ậ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ị (n
k
(v),D
k
(v)) trong đó:
D
k
(v) là giá trị cực tiểu từ đỉnh v đến đích tại bước thứ k
N
k
(v) là đỉnh tiếp theo trên con đường từ v đến đích tại bước thứ k
SV : Phạm Tến Khánh 10
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh
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

k-1
(w
1
)+ l(v,w
1
)= min[D
k-1
(w) + l(v,w)]
với w thuộc N
v
Kiểm tra điều kiện lặp: Nếu tồn tại D
k
(v) khác D
k-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
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:
SV : Phạm Tến Khánh 11
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh
• 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

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
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

D
k
(v)= min [D
k-1
(v), D
k-1
(w)+l(w,v)]
Kiểm tra điều kiện lặp: Nếu N
k
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 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
SV : Phạm Tến Khánh 14
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh
đó 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

Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh
Hình1.6 biều diễn về định tuyến mạng ngoài
Theo ví dụ trên thì khu vực 0 đóng vai trò là một mạng lõi khi thông tin muốn
truyền từ mạng 1 sang mạng 2 hay ngược lại bắt buộc phải qua mạng 0 rồi sau đó
đi tiếp . Hay có thể nói mang 0 đóng vai trò là mạng sơ cấp còn mạng 1,mạng2
đóng vai trò là các mang thứ cấp
Định tuyến giữa các mạng
Định tuyến giữa các mạng hoàn toàn có thể được thông qua các router biên vùng
tự trị. Thật quá dễ dàng khi định tuyến giữa 2 mạng sử dụng OSPF khi đó các
router biên khu vục không phải tổng hợp thông tin đi tới ,sử lý thông tin và chuyến
tiếp vào vùng mạng trong . Lúc này router biên vùng tự trị chỉ làm nhiệm vụ
chuyển iêp gói tin vào trong khu vực cần đến.
Thông tin định tuyến giữa mạng không sử dụng OSPF được tổng hợp và phân phối
lại tới mạng OSPF thông qua router biên khu vực ,khi đó router biên khu vực làm
nhiệm vụ sử lý gói tin đI tới và chuyển tiếp ra khu vưc ngoài.
Hình 1.7Biểu diễn 2 khu vực tự trị thông qua router biên khu vực kết nối với nhau
6:Cập nhật định tuyến
Cập nhật định tuyến có 4 loại khác nhau sử dụng trong các trường hợp khác nhau
Thứ nhất:Cập nhật định tuyến trong một khu vực của vùng tự trị
Thứ hai:Cập nhật định tuyến giữa hai khu vực trong vùng tự trị
Thứ ba:Cập nhật định tuyên dựa vào router mạng lõi
Thứ tư:Cập nhật định tuyến dựa vao router biên vùng tự trị
Cập nhật định tuyến trong một khu vực của vùng tự trị
SV : Phạm Tến Khánh 17
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh
Hình 1.8:biểu diễn cập nhật định tuyến trong nội vùng
Hình trên miêu tả cập nhật định tuyến dựa vào router trong một khu vực của vùng
tự trị. Lúc này các router trong một khu vực sẽ thường xuyên cập nhật trạng thái
liên kết đẻ đảm bảo thông tin về trạng thái mạng tốt nhất
Cập nhật định tuyến giữa hai khu vực trong vùng tự trị

Kiểu 5: Tin báo nhận trạng thái liên
kết(LSACK)
Xác nhận trạng thái liên kết của các
Router lân cận
Bảng 1.1:Các kiểu gói OSPF
Tất cả các gói OSPF đều có cùng phần tiêu đề gồm 9 trường có độ dài 24 byte.
1-octet
Version
number
field
1-octet
Type
field
2-octet
Packet
length
field
4-octet
Router
ID
Field
4-
octet
Area
ID
2-octet
Check-
sum
field
2-octet

• Authentication: Chỉ ra các thông tin xác thực.
SV : Phạm Tến Khánh 20
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh
bảng 1.3: Giá trị kiểu xác nhận
7.1 Gói chào (Hello) của OSPF
OSPF sử dụng các gói chào để tạo các mối quan hệ lân cận và kiểm tra khả
năng có thể tới của các lân cận. Đây là bước đầu tiên trong định tuyến trạng thái
liên kết. Trước khi một router có thể trao đổi các thông tin định tuyến với các lân
cận thỡ nú phải “chào hỏi” cỏc lõn cận để biết xem các lân cận có hoạt động hay
không và có thể tới được các lân cận hay không?.Định dạng của gói chào như sau:
Bảng 1.4 :Tiêu đề gói chào OSPF
Các trường chức năng trong gói chào:
SV : Phạm Tến Khánh 21
Giao thức định tuyến OSPF GVHD: Hoàng Trọng Minh
• Tiêu đề (Header): Tiêu đề chung gồm 24 byte trong đó trường Type được
thiết lập bằng 1.
• Khoảng chào(Hello Interval): Trường 16 bít này dùng để định nghĩa
khoảng thời gian tính bằng giây giữa các gói chào.
• Chưa sử dụng (Unused): Trường 6 bít này được thiết lập mặc định là 0.
• Cờ E (Flag E): Khi cờ 1 bít này được thiết lập thỡ đây là khu vực gốc (khu
vực chỉ có một kết nối tới khu vực đường trục).
• Cờ T (Flag T): Khi cờ 1 bít này được thiết lập nghĩa là router này có hỗ trợ
nhiều giá trị đo lường.
• Ưu tiên (Priority): Trường 8 bít này chỉ ra độ ưu tiên của router, được sử
dụng để chọn router chỉ định. Sau khi tất cả các router khai báo độ ưu tiên thỡ
router nào cú độ ưu tiên cao nhất sẽ được chọn làm router chỉ định. Nếu giá trị này
bằng 0 có nghĩa là router này không muốn được chọn làm router chỉ định hay
router chỉ định dự phũng.
• Khoảng thời gian không hoạt động (Dead Interval): Trường 32 bít này định
nghĩa khoảng thời gian tính bằng giây trước khi một router cho rằng lân cận của