Widest Shortest Path GVHD: Hoàng Trọng Minh Luận văn
Tìm hiểu thuật toán
Widest Shortest Path
Sinh Viên : Nguyễn Thị Nghĩa

1
Widest Shortest Path GVHD: Hoàng Trọng Minh
Mục Lục

Tổng quan…………………………………………………………1
I. Khái niệm định tuyến……………………………………………3
II. Giải thuật định tuyến……………………………………… 4
2.1. Yêu cầu của giải thuật định tuyến………………… ……… 4
2.2. Giải thuật tìm đường đi ngắn nhất và rộng nhất (WSP)………5
III. Giới thiệu về QoS (quality of service)………………………….…5
3.1.Định nghĩa về QoS…………………… ………5
3.2. Mô hình trạng thái QoS………………………………… 6
3.3. Mục tiêu định tuyến Qos…………… … 7
3.4. Các tham số QoS…………………… ……7
3.5. Các giao thức và tiêu chuẩn liên quan đến QoS………… 9
IV. Các vấn đề về số đo 11
4.1. Số đo 11
4.2. phân phối số đo 12
4.3. Thứ tự số đo 12
V. Kĩ thuật lưu lượng 13
5.1. Định tuyến QoS: tiếp cận khu vực và tổng thể 14
5.2. Định tuyến khoanh vùng 15
5.3. Dịch vụ kết nối và không kết nối 16

băng thông, độ trễ, độ tin cậy, giá thành,v v. Vì vậy, một kỹ thuật định tuyến phải
thực hiện tốt 2 chức năng chính sau đây:
1.Quyết định chọn đường theo những tiêu chuẩn tối ưu nào đó.
2.Cập nhật thông tin định tuyến, tức là thông tin dùng cho chức năng
Trong các mạng máy tính có rất nhiều các kỹ thuật định tuyến khác nhau đã được
đưa ra. Sự phân biệt giữa các kỹ thuật định tuyến chủ yếu căn cứ vào các yếu tố
liên quan đến 2 chức năng chính đã chỉ ra trên đây. Các yếu tố đó thường là:
(a) Sự phân tán của các chức năng chọn đường trên các nút của mạng.
(b) Sự thích nghi với trạng thái hiện hành của mạng.
(c) Các tiêu chuẩn tối ưu để định tuyến.
Tiêu chuẩn tối ưu để định tuyến được xác định bởi người quản lý hoặc người
thiết kế mạng, nó có thể là:
- Độ trễ trung bình của thời gian truyền gói tin.
- Số lượng nút trung gian giữa nguồn và đích của gói tin.
- Độ an toàn của việc truyền tin.
- Nguồn tài nguyên mạng sử dụng cho truyền tin .
- v.v
- Tổ hợp của các tiêu chuẩn trên.
Việc chọn tiêu chuẩn tối ưu như vậy phụ thuộc vào nhiều bối cảnh mạng (topo,
thông lượng, mục đích sử dụng.v.v ). Các tiêu chuẩn có thể thay đổi vì bối cảnh
mạng cũng có thể thay đổi theo thời gian hoặc các triển khai ứng dụng trên mạng,
Sinh Viên : Nguyễn Thị Nghĩa
4
Widest Shortest Path GVHD: Hoàng Trọng Minh
chính vì thế mà vấn đề tối ưu hoá định tuyến luôn được đặt ra trong thời gian triển
khai mạng, nhất là sự đối lập về quan điểm người sử dụng dịch vụ và nhà khai
thác dịch vụ mạng
II. Giải thuật định tuyến
Giải thuật định tuyến (routing algorithm) là giải thuật tìm đường đi cho các gói
từ một máy nguồn đến một máy đích, trong hầu hết các mạng thì các gói sẽ cần

thay đổi các tuyến (chẳng hạn như mỗi một ΔT giây, khi tải thay đổi hay cấu trúc
liên kết mạng thay đổi ), và số đo nào được sử dụng cho sự tối ưu (chẳng hạn như
khoảng cách, số bước nhảy hay thời gian chuyển tiếp được ước lượng) và ở đoạn
tiếp giải thuật định tuyến đường đi ngắn nhất và rộng nhất (WSP).
2.2. Giải thuật tìm đường đi ngắn nhất và rộng nhất ( WSP )
Thuật toán tìm đường đi ngắn nhất và rộng nhất (WSP)[1] là thuật toán được
nâng cấp từ thuật toán bước nhảy tối thiểu,WSP cố gắng cân bằng tải trọng của
lưu lượng mạng. Trên thực tế thì WSP chọn một đường dẫn khả thi nhất cùng với
số bước nhảy bé nhất và nếu có nhiều hơn một đường dẫn khả thi cùng với số
bước nhảy như vậy thì một đường dẫn sẽ được chọn ra cùng với độ dư băng thông
lớn nhất, như vậy sẽ làm giảm liên kết tải trọng nặng. Mục tiêu của thuật toán
WSP là để chọn một con đường ngắn nhất mà là một con đường có tính khả thi
theo sự rằng buộc về băng thông của lưu lượng. Số đo chính trong thuật toán
WSP là số bước nhảy và số đo thứ 2 là băng thông sẵn có (còn dư), trong giai
đoạn một tồn tại tất cả các con đường ngắn nhất giữa mỗi nguồn và tất cả các đích
trong mạng là một sự tính toán. Trong giai đoạn 2 băng thông được sử dụng. WSP
có thể tính toán bằng phiên bản sửa đổi của Bellman-Ford hoặc thuật toán
Dijkstra. Sự mở rộng để thuật toán Dijkstra thay thế cho sự tính toán của WSP.
Mục đích chính của WSP là để giảm tải chi phí cho mạng. Từ đó sự duy trì tài
nguyên mạng là đặc biệt quan trọng khi mạng bị tắc nghẽn, kiểu thuật toán này
mang lại hiệu quả cao khi mạng có tải trọng cao. WSP thực thi tốt bởi vì tài
nguyên được bảo vệ đồng thời bằng cách chọn con đường ngắn và cân băng tải
trọng bằng cách chọn con đường rộng giữa các con đường có độ dài như nhau
Trong phần sau chúng ta sẽ đi sâu vào tìm hiểu về QoS (quality of service) để biết
được giải thuật WSP hỗ trợ cho định tuyến QoS như thế nào
III. Giới thiệu về QoS (quality of service)
3.1. Định nghĩa về QoS (chất lượng dịch vụ)
Chất lượng dịch vụ QoS [2] là khả năng của mạng để cung cấp dịch vụ tốt cho
lưu lượng mạng xác định qua nhiều công nghệ lớp dưới như Frame-Relay, ATM,
IP và các mạng định tuyến… nói cách khác nó là đặc tính của mạng cho phép

≥ d
k
. Một
kết nối mới có thể được chấp thuận nếu ít nhất tồn tại một đường dẫn khả dụng
giữa v
i
và v
j
.

Sinh Viên : Nguyễn Thị Nghĩa
Hội nghị truyền hình
Âm nhạc theo yêu cầu
Cao
Thấp
Thấp
Thấp
Ứng dụng
Độ tin cậy
Thời gian trì hoãn
Trượt Băng thông
Thư điện tử
Truyền tập tin
Điện thoại
Đăng nhập từ xa
Truy cập Web
Cao
Cao
Cao
Cao

C
jl
F
jl
C
ln
F
ln
C
mn
F
mn
C
km
F
kmm
C
jk
F
jk
C
kl
F
kl
C
jm
F
jm
v
n

được gọi là đỉnh cối của đường đi, độ dài của đường đi là n-1(bằng số cạnh trên
đường đi ). Một liên kết a thuộc E từ nốt v
i
đến v
i+1
hay gọi là liên kết (vi,v
i+1
). Mỗi
một liên kết a thuộc E có tải trọng wi(a). w(v
i
,v
i+1
) là tải trọng tương ứng với liên
kết ( vi,v
i+1
) trên đường dẫn P = ( v
1,
v
2
v
n-1
) và W(P) là tải trọng trên toàn bộ
đường truyền
3.3. Mục tiêu định tuyến QoS
Vai trò của định tuyến là tính toán đường dẫn thích hợp cho các kiểu lưu lượng
khác nhau, khi sự tận dụng của tài nguyên mạng lớn, việc đáp ứng mục tiêu phụ
thuộc vào sự phát triển của thuật toán để tìm đường dẫn dựa vào sự tính toán trạng
thái của mạng và lưu lượng yêu cầu, cụ thể là, cần tính đến độ trễ, độ trượt, tỉ lệ
mất mát và băng thông còn dư.
Mục tiêu của định tuyến QoS là để chọn đường dẫn phù hợp theo yêu cầu thông

- vailability - network uptime-tính sẵn sàng của mạng.
+ Các tham số sau đây là cơ sở để định lượng bất kỳ một dịch vụ nào:
- one-way delay -độ trễ một chiều.
- one-way packet delay variation-mức độ thay đổi độ trễ gói tin theo một
chiều.
- capacity- dung lượng.
Sinh Viên : Nguyễn Thị Nghĩa
9
Widest Shortest Path GVHD: Hoàng Trọng Minh
- packet loss- độ mất mát gói tin.
Ngoài danh sách này,có một vài yêu cầu cơ bản cho hoạt động mạng mà ảnh
hưởng lớn đến toàn bộ chất lượng của bất kỳ dịch vụ nào.
- Tỉ số lỗi bít.
- Sự ổn định của lớp vật lý và liên kết số liệu.
- Sự ổn định định tuyến.
- Hiệu năng phần cứng toàn mạng.
- Kiểm tra và thời gian cần để giải quyết sự cố .Bảng 2.2: Phạm vi các tham số
3.5 Các giao thức và tiêu chuẩn liên quan đến QoS
Trong phần này sẽ đề cập và xem xét hai mô hình hỗ trợ QoS trong mạng IP
là : Integrated Services (các dịch vụ tích hợp) và Differentiated Services (các dịch
Sinh Viên : Nguyễn Thị Nghĩa
lớp QoS
1
2
3
4
5

độ ưu tiên giảm
Tách rời hàng đợi
(ưu tiên mức
thấp nhất)
rằng buộc định
tuyến và
khoảng cách
rằng buộc định tuyến
ở mức độ nhỏ hơn và
khoảng cách
rằng buộc định
tuyến và
khoảng cách
rằng buộc định tuyến
ở mức độ nhỏ hơn và
khoảng cách
bất cứ bộ định
tuyến/đường dẫn
bất cứ bộ định
tuyến/đường dẫn
10
Widest Shortest Path GVHD: Hoàng Trọng Minh
vụ sai biệt ). Cả hai mô hình đều hỗ trợ cho việc điều khiển mạng và mang lại khả
năng phát triển mạng tốt hơn
Kĩ thuật Intserv được hiểu một cách tổng quan như sau
- Mỗi node mạng (router) được phân chia thành 2 phần: Xử lý cơ bản và
chuyển tiếp lưu lượng.
- Xử lý cơ bản đảm nhận các chức năng như: định tuyến, thiết lập và duy trì
tài nguyên mạng và điều khiển quản lý.
- Xử lý trong chuyển tiếp lưu lượng: dựa trên thông tin trong cơ sở dữ liệu

yêu cầu các gói RSVP phải mang một số thông tin “tóm tắt” để định phiên làm
việc của chúng. Các bộ định tuyến trung gian phải có một bảng định tuyến động
chứa phương pháp sử lí các thông tin “tóm tắt” đó và thông tin về việc “dành trước
tài nguyên”. Khi một bộ định tuyến nhận được một gói thuộc phiên làm việc
RSVP nó phải tham chiếu vào bảng để biết cách phải xử lí gói như thế nào.
Trong mô hình tích hợp dịch vụ sử dụng giao thức RSVP có thể đảm bảo
QoS từ đầu cuối đến đầu cuối trên cơ sở mỗi luồng thông qua báo hiệu QoS trên
từng chặng. Các bộ định tuyến dọc theo đường truyền phải duy trì trạng thái cho
mỗi luồng thông tin. Vì vậy tối ưu về sử dụng tài nguyên mạng, nhưng kéo theo đó
là gánh nặng xử lý và tăng kích cỡ mạng
Trong mô hình dịch vụ sai biệt chỉ đảm bảo QoS trên từng chặng thông qua việc
ấn định tài nguyên phần cứng. Gánh nặng xử lý của các bộ định tuyến nhẹ hơn và
đơn giản hơn, nhưng không đảm bảo về QoS từ đầu cuối đến đầu cuối
Hình mô hình tích hợp dịch vụ sử dụng RSVP
VI. Các vấn đề về số đo
4.1 Số đo ( Metric)
Thuật toán chọn đường có mức độ phức tạp được quyết định bởi nhiều yếu tố
khác nhau. Thuật toán chọn đường chọn các đường dẫn khả thi trong một tập
Sinh Viên : Nguyễn Thị Nghĩa
12
Pat
h
Pat
h
Resv
Resv
Bảng định tuyến
Dữ liệu
Điều khiển
path

Các số đo sử dụng phổ biến trên định tuyến QoS và rằng buộc định tuyến căn bản
được tách ra thành 3 loại
Được gọi là các quy tắc cấu tạo hành phần các số đo
- Tính cộng thêm nếu
W(P) = w( u1, u2 ) + w ( u3 , u4 ) +…+ w(ul-1,ul)
- Tính nhân lên nếu
W(P) = w( u1, u2 )
.
w ( u3 , u4 )
.
…
.
w(ul-1,ul)
- Tính lõm nếu
W(P) = min( w( u1, u2 ), w ( u3 , u4 ) ,…, w(ul-1,ul) )
W(P) là tải trọng trên đường truyền, w(ui , uj) là tải trọng của một liên kết trên
đường truyền
4.2. Phân phối số đo ( Metrics Distribution)
Trạng thái của mạng có thể miếu tả bằng một tập hơp số đo, bao gồm băng
thông sẵn có, độ trễ, độ trượt, và mức độ tắc nghẽn. Thông tin về tất cả trạng thái
của mạng cần được phân phối, và giữ lại cập nhật, ở tất cả hoặc một vài bộ định
tuyến trong mạng. Sự phân phối cần được thực hiện thường xuyên hơn trong bộ
định tuyến để cập nhật trạng thái động của mạng. Nhưng nếu thường xuyên cập
nhật thông tin thì nó sẽ gây ra tiêu thụ băng thông nhiều, có thể xảy ra nguy hiểm
cho mạng.
4.3 Thứ tự số đo (Metric Ordering )
Thứ tự số đo phụ thuộc sự xác định của số đo mà có độ ưu tiên cao và có sự
tính toán tương đối tốt nhất theo số đo này. Trong thuật toán WSP thì số đo được
ưu tiên tính toán đầu tiên là số bước nhảy, số đo thứ hai căn cứ trên băng thông
Sinh Viên : Nguyễn Thị Nghĩa

sự cập nhật tương ứng với thay đổi tình trạng của mạng
Kĩ thuật lưu lượng là một phần quan trọng để điều khiển của sự thực thi mạng:
Lập kế hoach mạng, điều khiển dung lượng, và điều khiển lưu lượng [3]. lập kế
hoạch cho mạng kết hợp cùng với node và kế hoạch truyền tải tăng hỗ trợ lưu
lượng Điều khiển lưu lượng là modul nhằm vào sự thực thi của mạng dưới tất
cả các điều kiện công việc bao gồm điều kiện tải trọng và tình trạng của mạng. Cơ
sở rằng buộc định tuyến là một công cụ mạnh cho kĩ thuật lưu lượng tại modul
điều khiển lưu lượng, từ đó các đường dẫn được chọn theo sự sẵn có tài nguyên
của mạng, sử dụng các giao thức định tuyến QoS.
5.1 Định tuyến QoS: tiếp cận khu vực và tổng thể
Phần lớn sự phối hợp định tuyến QoS, được đề xuất phụ thuộc theo thay đổi
định kỳ của thông tin trạng thái liên kết QoS giữa các bộ định tuyến trong mạng để
đạt được tổng quan chung về trạng thái QoS mạng. Cách tiếp cận này để định
tuyến QoS tham khảo như sự tiếp cận định tuyến QoS chung. Bởi vì tài nguyên
mạng có thể sẵn sàng bị thay đổi cùng với mỗi lưu lượng chuyển đến và đi ra, để
duy trì trạng thái QoS mạng đúng yêu cầu thì thông tin phải được thường xuyên
cập nhật. Sự ngăn cấm truyền thông và chi phí sử lí gây ra sự ngăn cản cập nhật
trạng thái QoS thường xuyên của mỗi node mạng cùng với cái nhìn đúng đắn của
tình trạng mạng hiện thời. Do vậy, thông tin trạng thái QoS mạng có được tại
một nốt nguồn có thể nhanh chóng trở nên out-of-date (qúa hạn ) khi trạng thái
QoS cập nhật trong khoảng thời gian tương đối lớn về lưu lượng động. trong các
trường hợp này sự trao đổi thông tin trạng thái QoS giữa các node trong mạng là
không cần thiết. Hơn nữa đường dẫn được chọn dựa trên thuật toán định tuyến ví
dụ Dijkstra là thuật toán chọn đường ngắn nhất. Trong tính cộng, sự tổng quan
Sinh Viên : Nguyễn Thị Nghĩa
15
Widest Shortest Path GVHD: Hoàng Trọng Minh
chung của trạng thái mạng có thể dẫn đến vấn đề đồng bộ hóa. Khi cập nhật QoS
với khoảng thời gian dài có liên quan đến lưu lượng động, có thể làm cho kế
hoạch định tuyến QoS chung bị giảm sút [4]. Để tránh các tình trạng trên các node

Sinh Viên : Nguyễn Thị Nghĩa
16
Widest Shortest Path GVHD: Hoàng Trọng Minh
để điều chỉnh sự cân đối lưu lượng dọc theo các con đường. Sự ổn định là bản chất
để đảm bảo tận dụng tài nguyên hệ thống và tất cả các thông số lưu lượng. Về các
mục tiêu này, chúng ta đưa ra một khung lý thuyết cho nghiên cứu khả năng đáp
ứng định tuyến tỉ lệ.
Sử dụng công thức Erlang, giới thiệu khái niệm cho dung lượng ảo nó cung cấp
một khả năng tính toán khung để để mô hình các đường dẫn giữa một nốt nguồn
và một nốt đích, cũng như để tính toán tỉ lệ lưu lượng dựa trên sự theo dõi thống
kê khối lưu lượng cục bộ. Khái niệm dung lượng ảo của đường truyền được giới
thiệu để phân chia cùng với phân chia của các liên kết giữa các đường truyền khác
nhau
5.2 Một tập các đường dẫn riêng rẽ từ nguồn đến đích
5.3. Dịch vụ kết nối và không kết nối
Trong mô hình thực hiện nhiệm vụ không kết nối, thì các gói tin được đưa
vào mạng dưới từng gói riêng rẽ và được định tuyến độc lập với các gói khác và
không có sự thiết lập trước nào được cần đến. Nếu dịch vụ hướng kết nối được sử
dụng, một đường dẫn từ bộ định tuyến nguồn đến bộ định tuyến đích phải được
thiết lập trước khi các gói dữ liệu bất kì có thể được truyền, kết nối này được gọi
là mạch ảo (VC). Ý tưởng đằng sau mạch ảo là để tránh việc phải lựa chọn một
tuyến mới cho mỗi gói được truyền. Thay vào đó khi một kết nối được thiết lập,
một tuyến từ máy nguồn đến máy đích được chọn như là một phần của việc thiết
lập kết nối và được lưu giữ trong các bảng bên trong bộ định tuyến. khi kết nối
được giải phóng mạch ảo cũng được kết thúc . Mạch ảo có ưu điểm trong việc
đảm bảo QoS và tránh tắc nghẽn bên trong mạng do bởi các tài nguyên có thể
Sinh Viên : Nguyễn Thị Nghĩa

r,
b
r
) , vc
r
=E
vc
-1
(v
r,
b
r
) biểu thị hàm nghịch đảo của công thức Erlang cùng
với đánh giá dung lượng, và đưa ra bởi
vc
r
=E
vc
-1
(v
r,
b
r
):= min{c>=0: E(v
r
,c)<=b
r
}
Khái niệm về dung lượng ảo cung cấp một khung chính xác thỏa thuận cùng với
chia sẻ các liên kết xung quanh các đường truyền. ví dụ m đường truyền ,r

vc
-1
(v
i,
b
i
)=E
vc
-1
(v
i,
b).
b
i
biểu thị khả năng xảy ra khối của đường truyền r
i
. Trong trường hợp ngoại lệ,
cho đường dẫn r
i
, phần lớn yêu cầu tải trọng v
i
là phần lớn là dung lượng ảo vc
i
.
Phản ánh này phần lớn “chia sẻ dung lượng” của cổ chai quan sát bởi đường
truyền r
i
bởi vì nó yêu cầu tải trọng cao
Căn cứ trên khái niệm dung lượng ảo, chúng ta có thể mô hình hóa các đường
truyền giữa một nguồn và một đích là các đường tách biệt và có dung lượng nghẽn

2
2
thể hiện
các đường truyền 2->5->6 và 2->4->6 theo thứ tự định sẵn. Một cách tổng quan
dung lượng ảo của 2 cặp nguồn- đích là cho trong hình 3(b) , ở các đường dẫn
r
2
1
,r
2
2
đến mỗi node nguồn như các đường riêng rẽ cùng các dung lượng vc
2
1
, vc
2
2
theo thứ tự định sẵn, và không có chia sẻ các liên kết với các đường dẫn khác
VI. Giao thức đường đi ngắn nhất (OSPF-open Shortest First)
Sinh Viên : Nguyễn Thị Nghĩa
19
d
2
5
4
3
6
1S1
S2
C1

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
Sinh Viên : Nguyễn Thị Nghĩa
20
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 6.các khu vực trong một hệ thông tự trị
Widest Shortest Path GVHD: Hoàng Trọng Minh
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.

kết cụ thể. Khi hai router muốn trao đổi các gói miêu tả cơ sở dữ liệu, một router
đóng vai trò làm chủ (master) và một router đóng vai trò làm tớ (slave). Do thông
tin cơ sở dữ liệu có thể rất lớn, nên nội dung của nó được chia ra thành nhiều gói.
* Gói yêu cầu trạng thái liên kết
Đây là gói được gửi bởi một router cần thông tin về một hay nhiều tuyến cụ
thể. Nó được trả lời bằng một gói cập nhật trạng thái liên kết. Các router mới kết
nối tới hệ thống gửi gói này để yêu cầu thêm thông tin về một tuyến sau khi đ•
nhận gói miêu tả cơ sở dữ liệu. Ba trường trong gói này là một phần của tiêu đề
LSA. Mỗi tập 3 trường lặp này là một yêu cầu cho một LSA. Tập này được lặp
nếu router yêu cầu nhiều quảng bá.
*Gói cập nhật trạng thái liên kết
Gói cập nhật trạng thái liên kết là trung tâm hoạt động của OSPF. Nó được
router sử dụng để quảng bá trạng thái của các liên kết. Mỗi gói cập nhật có thể
chứa nhiều LSA khác nhau. Ví dụ một gói cập nhật trạng thái liên kết có thể chứa
14 LSA, trong đó 4 LSA là quảng bá liên kết router, 3 LSA là quảng bá liên kết
mạng, 2 LSA là quảng bá liên kết tóm tắt tới mạng, 2 LSA là quảng bá liên kết
tóm tắt tới router biên AS và 3 LSA là quảng cáo liên kết ngoài.
V. Tìm hiểu về thuật toán Dijkstra và thuật toán A*(a-star)
1. thuật toán Dịkstra
Thuật toán định tuyến WSP chạy trên cơ sở thuật toán Dijsktra vì bài toán tìm
đường đi ngắn nhất là vấn đề quan trọng trong lý thuyết đồ thị, nó được nghiên
cứu từ lâu và ứng dụng trong nhiều nghành khoa học nói chung và ngành khoa học
máy tính nói riêng. Nhiều giải thuật (Dijkstra,Bellman-ford, floyd) đã được phát
triển đề tìm đường đi ngắn nhất cho một cặp đỉnh hay tất cả các cặp đỉnh và nó
được áp dụng để giải rất nhiều bài tóan trên thực tế như điều khiển tối ưu, giao
thông vận tải, mạng viễn thông
1.Giải thuật Dijktra
Sinh Viên : Nguyễn Thị Nghĩa
22
Widest Shortest Path GVHD: Hoàng Trọng Minh

k-1
có nhãn
nhỏ nhất.Khi đỉnh u được gộp vào s
k
chúng ta sủa đổi nhãn của các đỉnh không
thuộc S
k
sao cho L
k
(v), nhãn của v đạt tại bước k, là độ dài của đường đi ngắn nhất
từ a tới v mà đường đi này chỉ chứa các đỉnh thuộc S
k
( tức là các đỉnh đã thuộc
tập đặc biệt các đỉnh cùng với u )
Giả sử v là một đỉnh không thuộc S
k
. Để sửa nhãn của v ta thấy L
k
(v) là độ dài
của đường đi ngắn nhất từ a tới v và chỉ chứa các đỉnh thuộc S
k
. Để sửa đổi nhãn
ta lưu ý rằng đường đi ngắn nhất từ a tới v chứa chỉ các phần tử của S
k
hoặc là
đường đi ngắn nhất từ a tới v chỉ chứa các phần tử của S
k-1
hoặc là đường đi ngắn
nhất từ a tới u ở bước k-1 cùng với cạch ( u,v ). Nói cách khác là ta có
L

i ,
v
j
),
với w(v
i
, v
j
) = ∞ nếu {v
i
, v
j
} không là một cạnh trong G }
for i := 1 to n
L(v
i
) := ∞
L(a) := 0
S: = Ø
{ Ban đầu các nhãn được khởi tạo sao cho nhãn của a bằng không, các đỉnh
khác bằng ∞, tập S là rỗng }

While z không thuộc S
begin
u := đỉnh không thuộc S có nhãn L(u) nhỏ nhất.
S := S là tập con của {u}
for tất cả các đỉnh v không thuộc S
if L(u) + w(u,v) <L(v) then L(v) := L(u) + w(u,v)
{ thêm vào S đỉnh có nhãn nhỏ nhất, và sửa đổi nhãn
của các đỉnh không thuộc S }

Sinh Viên : Nguyễn Thị Nghĩa
25
THUẬT TOÁN DIJKSTRA
Procedure Dijkstra (G: đơn đồ thị liên thông có trọng số, với trọng số
dương )
{G có các đỉnh a = v
o
, v
1,…,
v
n
= z và trọng số w(v
i ,
v
j
),
với w(v
i
, v
j
) = ∞ nếu {v
i
, v
j
} không là một cạnh trong G }
for i := 1 to n
L(v
i
) := ∞
L(a) := 0