Luận án Nghiên cứu các giải pháp đảm bảo chất lượng mạng sử dụng kỹ thuật định tuyến

p, lại càng yêu cầu 
khắt khe hơn về chất lượng tuyến truyền, chất lượng của dịch vụ.Kỹ thuật định 
tuyến đảm bảo QoS là một phương cách để thỏa mãn yêu cầu này, đồng thời đảm 
bảo tối ưu hóa việc sử dụng tài nguyên mạng. Trong các kỹ thuật định tuyến, các 
giải thuật định tuyến dùng thông tin toàn cục (TTTC) phải thu thập và cập nhật liên 
tục thông tin trạng thái toàn mạng để từ đó quyết định định tuyến. Cách thức này 
khi áp dụng với các mạng có số lượng nút mạng tăng đột biến, yêu cầu cao về QoS 
53 
thì rất không hiệu quả, hay gây nghẽn mạng do phải chịu tải tính toán tuyến truyền 
cao tại các nút mạng, việc cập nhật thông tin toàn mạng không kịp thời, không 
chính xác  
Để giải quyết các nhược điểm trên, giải thuật định tuyến trong đó nút mạng 
xây dựng trước các tập tuyến truyền, thu thập các thông tin tại nội bộ nút như xác 
suất nghẽn, thống kê thông tin gói tin, luồng tin  để đưa ra quyết định định tuyến 
thông tin trên các tập tuyến truyền đã có,đến các nút trong mạng là một hướng đi 
mới được đánh giá là khá hiệu quả. Mô hình này giúp giảm xác suất nghẽn toàn 
mạng, giảm lượng tính toán tại các nút mạng đồng thời tăng hiệu năng của mạng so 
với các mô hình định tuyến dùng TTTC. 
Chương này đề xuất các giải thuật định tuyến mới, trong đó sử dụng các thông 
số QoS như băng thông, độ trễ hay tỷ lệ mất gói là tiêu chuẩn chọn tuyến truyền. 
Trong các thí nghiệm mô phỏng, luận án so sánh kết quả mô phỏng với các giải 
thuật định tuyến dùng TTNB khác như đã khảo sát ở chương 1 và qua đó đánh giá 
được hiệu năng tốt hơn của các giải thuật đề xuất khi thực hiện trên cùng một môi 
trường mô phỏng. 
3.2 Các nghiên cứu liên quan 
Trong chương này, luận án có sử dụng các giải thuật định tuyến liên quan như 
đã khảo sát trong chương 1 như các giải thuật WSP, CBR, PSR để so sánh và 
đánh giá hiệu năng của các giải thuật đề xuất. Cụ thể, luận án so sánh các giải thuật 
đề xuất với các giải thuậtdùng TTTC và các giải thuật định tuyến dùng TTNB ở các 
tiêu chí như xác suất nghẽn luồng, nghẽn băng thông,giá trị trễ đầu cuối - đầu cuối, 
 Qua đó, luận án có những kết luận đánh giá đối với từng giải thuật cụ thể. 
Trong các giải thuật định tuyến QoS dùng TTTC, luận án so sánh với giải 
thuật phổ biến hiện nay là WSP (tìm đường ngắn nhất rộng nhất), như mô tả trong 
chương 1 và trong các nghiên cứu [39], [57], [67]. 
Trong các giải thuật định tuyến dùng TTNB, luận án khảo sát và so sánh với 
các giải thuật như LDCR [36], CBR [75], PSR [83], HMB [91],  Tất cả các giải 
thuật khi so sánh với giải thuật đề xuất đều được thực hiện trên cùng một môi 
trường mô phỏng, cùng với các mô tả về thông số mô phỏng như nhau. 
54 
3.3 Đề xuất giải thuật định tuyến dùng thông tin nội bộ sử dụng băng thông 
và độ trễ làm tiêu chuẩn chọn đường 
3.3.1. Giới thiệu 
Các giải thuật định tuyến đảm bảo QoS chọn tuyến truyền với các tài nguyên 
mạng đủ đáp ứng các yêu cầu QoS của luồng tin, đồng thời các giải thuật định tuyến 
đảm bảo QoS cũng dung hòa giữa sử dụng tài nguyên mạng và cân bằng tải mạng 
để đạt được hiệu quả định tuyến cao nhất. Các yêu cầu về QoS của một luồng tin 
bao gồm một tập các ràng buộc mà các giải thuật định tuyến phải đáp ứng để tìm ra 
một tuyến truyền khả dĩ để truyền thông tin đi đến nút đích. Các giải thuật định 
tuyến thường sử dụng một hay nhiều thông số QoS để làm tiêu chuẩn chọn tuyến 
truyền. Trong các thông số QoS, băng thông và độ trễ là hai thông số phổ biến nhất 
trong các dịch vụ viễn thông hiện nay như trong chương 1 đã phân tích. Do đó, 
trong phần 3.3 này, luận án đề xuấthaigiải thuật định tuyến đảm bảo QoS lấy băng 
thông và độ trễ làm tiêu chuẩn chọn đường, cụ thể: 
1. Giải thuật sử dụng tỷ lệ luồng truyền thành công làm chỉ số tuyến truyền 
là: “QoS Routing using Bandwidth-Delay based Algorithm” hay RBDA. 
2. Giải thuật sử dụng tỷ lệ luồng nghẽn làm chỉ số tuyến truyềnlà: 
“Bandwidth-Delay Constraint QoS Routing Algorithm” hay BQRA. 
3.3.2. Mô tả giải thuật RBDA 
 Tương tự các giải thuật định tuyến dùng TTNB khác, RBDA cũng xác định 
trước và duy trì tại tất cả các nút mạng các tập các tuyến truyền đến tất cả các nút 
đích. Cụ thể, với mỗi cặp nút nguồn – đích, tại nút nguồn duy trì một tập R các 
tuyến truyền kết nối giữa hai nút đó. Không giống như các giải thuật định tuyến 
dùng TTNB khảo sát ở phần trên như CBR hay PSR,giữa mỗi cặp nút, giải thuật 
RBDA chỉ sử dụng duy nhất một tập tuyến truyền R (kết quả của việc tìm đường 
ngắn nhất) mà thôi. Mỗi tuyến truyền Pi R liên kết với một biến 
Pi.Quality[1,2]=Pi.[Bandwidth,Delay], một chỉ số tuyến truyền Ci, và chỉ số Ni là 
tổng số luồng tin truyền trên tuyến truyền giữa cặp nút nguồn và đích đó. Cách tính 
toán giá trị Ci và Ni được đề cập ở phần sau. Và để chọn đường, tập tuyến truyền R 
được sắp xếp theo giá trị của Ci, và Ni theo thứ tự giá trị lớn nhất của Ci gọi là 
max(Ci), và giá trị nhỏ nhất của Ni gọi là min(Ni). Ta gọi thủ tục sắp xếp tập R như 
trên là max{Ci,Ni}. 
55 
3.3.2.1 Quá trình định tuyến: 
Với mỗi luồng thông tin yêu cầu đến nút nguồn, RBDA sắp xếp tập R theo giá 
trị của max{Ci,Ni}. Sau đó, chọn tuyến truyền Pi có giá trị {Ci,Ni}lớn nhất trong tập 
R đó. Tiếp theo, RBDA kiểm tra yêu cầu về băng thông và độ trễ của luồng dữ liệu 
tới từ thông số SLA (thỏa thuận mức chất lượng giữa mạng và người sử dụng [32]) 
của luồng dữ liệu. Ta gọi giá trị này là RQ.[Bandwidth,Delay] hay đơn giản là RQ, 
và lấy giá trị này để so sánh chọn đường. Nếu như luồng tin không có yêu cầu về 
thông số QoS, luồng tin đầu tiên của tập R sẽ được truyền. 
Nếu có yêu cầu về thông số QoS, thì RBDA sẽ tiến hành so sánh 
Pi.Quality[1,2] với RQ, cụ thể: 
Theo đó, nếu Pi.Quality ≥ RQ: Tuyến truyền được lựa chọn để truyền thông tin 
đi (thủ tục so sánh như đề cập ở chương 1, hình 1.3). 
Nếu Pi.Quality < RQ: RBDA chọn tuyến truyền tiếp theo của tập R, và vòng 
lặp sẽ được tiếp tục cho đến khi tìm ra được một tuyến truyền Pi có giá trị Ci cao 
nhất (với giá trị Ni thấp nhất nếu có giá trị Ci bằng nhau) và Pi.Quality≥RQ. 
Nếu không có tuyến truyền nào trong tập R thỏa mãn Pi.Quality ≥ RQ, thì 
luồng dữ liệu đến bị từ chối (do không có đường nào thỏa mãn yêu cầu chất lượng 
của luồng dữ liệu). 
Ta thấy, RBDA chỉ thay đổi chỉ số tuyến truyền tương ứng với khả năng 
truyền tải dữ liệu của tuyến truyền đã chọn, cụ thể: RBDA tăng Ci, Ninếu luồng tin 
qua Pi đến được nút đích, giảm Ci, giữ Ni nếu không truyền được. Cụ thể cách tính 
Ci, Ni như sau: Ci được đặt là S, và giá trị Ni được đặt là 0. Khi tuyến truyền được 
chọn và giá trị Pi.Quality[Bandwidth, Delay] của tuyến truyền lớn hơn giá trị RQ, 
điều này chỉ dấu rằng tuyến truyền được chọn có đủ chất lượng và các giá trị Ci, Ni 
đều tăng lên 1, theo công thức sau: 
Ci = (Last Ci + 1) (3.1) 
(Ci≤ S, nếu sau công thức (2.1), Ci>S thì Ci bị đặt lại là S) 
 Ni = (Ni + 1) (3.2) 
Khi tuyến truyền không được chọn (khi Pi.Quality < RQ) hay bị từ chối, thì: 
 Ci = (Last Ci – 1) (3.3) 
(Ci≥ 1, nếu Ci nhỏ hơn 1, Ci lại được đặt là 1) 
56 
Trong đó, S là một thông số hệ thống được cài đặt trước, tùy thuộc vào khả 
năng của mạng. Còn giá trị Last Ci là giá trị của Ci trước khi luồng tin đến với nút 
nguồn, Ni là số luồng tin được chấp nhận truyền trên tuyến truyền đó. 
Sau đó, luồng tin tiếp theo sẽ sử dụng các giá trị của {Ci, Ni} làm tiêu chuẩn 
chọn tuyến truyền và vòng lặp lại tiếp tục như vậy. Vì thế giá trị của {Ci, Ni} sẽ 
phản ảnh xác suất được lựa chọn của tuyến truyền cho luồng tin tiếp theo. 
Giá trị S phụ thuộc vào khả năng của mạng, thường ta đặt S = 10 15 cho 
mạng có từ 18-60 nút (như trong mô phỏng ở phần sau). Giá trị S này nhằm để giới 
hạn sử dụng một tuyến truyền nào đó trong tập tuyến truyền. Vì nếu để một tuyến 
truyền nào đó trong tập tuyến truyền có giá trị Ci quá lớn, đến khi tuyến truyền đó bị 
nghẽn, thì do giá trị Ci trên vẫn còn cao, RBDA sẽ dùng giá trị này so sánh và tuyến 
truyền trên sẽ lại được chọn. Do đó, với giá trị chặn trên S (ta luôn có: Ci≤ S), 
đảm bảo việc sử dụng đồng đều hơn các tuyến truyền trong tập tuyến truyền tại nút 
nguồn. 
3.3.2.2 Lưu đồ của giải thuật: 
Từ các bước mô tả ở trên, ta có lưu đồ giải thuật như sau: 
Hình 3.1 Lưu đồ hoạt động của RBDA 
57 
Theo các bước như trên, RBDA chỉ thay đổi các chỉ số Ci, Nicủa tuyến truyền, 
và các giá trị của Ci, Niđược dùng để so sánh giữa các tuyến truyền. Nếu tuyến 
truyền có tỷ số cao hơn, có nghĩa là nó có tiềm năng hơn, và nó sẽ được chọn cho 
luồng thông tin tiếp theo. Cho nên, sau khi truyền một luồng thông tin, RBDA cập 
nhật giá trị Ci, Ni, và sử dụng nó để chọn đường cho luồng kế tiếp. 
3.3.2.3 Mã giả ngẫu nhiên của giải thuật RBDA: 
Hình 3.2Mã giả ngẫu nhiên của RBDA 
3.3.3. Mô phỏng đánh giá hiệu năng giải thuật định tuyến RBDA 
Trong phần này, luận án sẽ mô phỏng giải thuật RBDA và so sánh kết quả với 
các giải thuật đã mô tả ở chương 1 như WSP, CBR và PSR. Các kết quả đánh giá sẽ 
được nêu ở phần sau. 
3.3.3.1 Mô hình mô phỏng 
Luận án dùng chương trình mô phỏng OMNeT++ [22], thu thập kết quả như 
giới thiệu trong phần 2.2.4. Các mô hình mô phỏng (tô-pô mạng) được phỏng theo 
Initialize 
Building R 
Set S=15 
Set Ci=SPi R 
Set Ni=0, 
RBDA 
1. Range max{Ci,Ni} for flow-in 
2. Set P.success = false; 
3. Get RQ from flow-in 
4. P=first(Pi.(Ci,Ni): Pi R) 
5. While !(P.success or R(end)) 
6. if(P.Quality≥RQ) 
7. Route flow along path P 
8. if P is accepted 
9. {Compute Pi.(Ci,Ni) (increase Ci(≤S), Ni) 
10. P.success=true} 
11. elseif { 
12. P= next(Pi.(Ci,Ni): Pi R) 
13. Compute Pi.Ci (decrease Ci(≥1)) 
14. endif} 
15. ElseIf 
16. P= next(Pi.(Ci,Ni): Pi R) 
17. Compute Pi.Ci (decrease Ci(≥1)) 
18. Endif 
19. Endwhile 
20. END. 
58 
các mạng lõi của các ISP trên thế giới, và đã được sử dụng trong các nghiên cứu 
liên quan. Với mô phỏng trong phần này, Luận án sử dụng hai mô hình mạng là các 
mạng lõi của các ISP được dùng trong các nghiên cứu [39], [40], [82], [83], [92] 
như giới thiệu ở mục 2.2,cụ thể: 
Mạng mô phỏng 32 nút (hình 3.3), gọi là mạng ISP1, được thiết lập như sau: 
các liên kết là song hướng với cùng một dung lượng C (C=150Mbps) và một độ trễ 
là D (D=10ms) trên mỗi hướng; số liên kết là 108 liên kết, độ dài trung bình của 
một tuyến truyền trên mạng (tính theo số bước nhảy) là 3,137. 
Mạng mô phỏng 18 nút (hình 3.3), gọi là mạng ISP2, được thiết lập như sau: 
các liên kết là song hướng với cùng một dung lượng C (C=20Mbps) và một độ trễ là 
D (D=20ms) trên mỗi hướng; số liên kết là 60 liên kết, độ dài trung bình của một 
tuyến truyền trên mạng (tính theo số bước nhảy) là 2,36. 
Các luồng dữ liệu đến các nút nguồn trong cả hai mạng tuân theo luật Poisson 
với tốc độλ và các nút đích được chọn lựa ngẫu nhiên (mỗi nút đều có thể là nút 
nguồn, cũng như nút đích); thời gian giữ mỗi luồng dữ liệu tuân theo quy luật phân 
bố hàm mũ với giá trị trung bình 1/μ = 60 giây, băng thông yêu cầu của mỗi luồng 
tuân theo quy luật phân bố uniform với giá trị trong khoảng [0.5-4MB], độ trễ yêu 
cầu của mỗi luồng tuân theo quy luật phân bố uniform với giá trịtrong khoảng 
20ms-250ms. 
Theo tính toán tại [19], [20], tải trung bình toàn mạng được tính theo công 
thức: 
  bwh/LC (3.4) 
với N là số nút, bw là giá trị băng thông trung bình yêu cầu bởi một luồng dữ 
liệu, h là độ dài trung bình của một tuyến truyền trên mạng (tính theo số bước nhảy) 
và L là số liên kết trên mạng. 
Vì việc hoạt động của các giải thuật định tuyến thay đổi tùy theo các điều kiện 
tải khác nhau, nên trong các thí nghiệm, giải thuật đã được thực hiện với nhiều loại 
tải từ thấp đến cao qua giá trị thông số λ từ thấp đến cao tương ứng. 
59 
Hình 3.3Các mạng mô phỏng có 32 nút (ISP1) và 18 nút (ISP2) 
3.3.3.2 Các tiêu chí đánh giá: 
Để so sánh kết quả giữa các giải thuật, ta chọn các giá trị xác suất nghẽn luồng 
và xác suất nghẽn băng thông là các tiêu chí so sánh tương tự như các thí nghiệm 
mô phỏng tại [75], [83], được mô tả ở phần 2.3, theo các công thức (2.1) và (2.2). 
Các giá trị xác suất trên được tính dựa trên giá trị thu thập của 100.000 luồng liên 
tục sau hơn 2,5 triệu luồng dữ liệu đã phát sinh. 
Ngoài ra, luận án cũng tính giá trị trễ đầu cuối – đầu cuối trên toàn mạng 
củagiải thuật RBDA để so sánh với WSP khi mô phỏng ở tải thấp đến tải cao. 
3.3.3.3 Kết quả mô phỏng: 
a. Trên mạng mô phỏng ISP1: 
Với các kết quả từ các thí nghiệm mô phỏng, ta thu thậpdữ liệu về xác suất 
nghẽn luồng của RBDA và so sánh với giá trị xác suất nghẽn luồng của các giải 
thuật khác, như trên hình 3.4. 
Hình 3.4 Xác suất nghẽn luồng trên ISP1 
60 
Hình 3.4 mô tả kết quả xác suất nghẽn luồng của giải thuật RBDA so sánh với 
các giải thuật khác như CBR, PSR và WSP với giá trị thu thậpxác suất nghẽn luồng 
khi tải thay đổi giữa 0,2 và 0,5. Qua hình trên ta thấy được sự khác nhau của các 
giải thuật chủ yếu khi tải tăng lên cao. Điều này dễ hiểu là vì khi tải tăng cao, thì 
các nút mạng mới trở nên nghẽn, và các luồng tin mới sắp hàng chờ nhiều tại các 
nút. Do có so sánh thời gian trễ, nên nhiều gói tin đã bị loại bỏ khi không thỏa mãn 
phép so sánh tuần tự như đã đề cập ở phần trên. 
Giải thuật định tuyến đã đề xuất RBDA do có cơ chế so sánh cũng như sử 
dụng chỉ số để thay đổi tuyến truyền khi nút mạng nghẽn, nên dễ dàng thấy là 
RBDA có giá trị tốt nhất. 
Giải thuậtWSP có giá trị cao nhất với lý do là giải thuật cứ căn cứ vào giá trị 
thông tin toàn mạng tìm được, sử dụng thuật toán tìm đường, và tìm đường ngắn 
nhất, và thực hiện điều này đến khi gây nghẽn. Do đó, WSP có giá trị xác suất 
nghẽn luồng cao nhất. 
Khi tải tăng cao, nhiều luồng dữ liệu bị nghẽn dẫn đến xác suất nghẽn luồng 
bắt đầu tăng cao, kéo theo xác suất nghẽn băng thông theo lên theo như mô tả ở 
hình 3.5. Do RBDA đã xây dựng và sử dụng tập tuyến truyền để định tuyến thông 
tin, nên khi có nghẽn xảy ra, chỉ số tuyến truyền thay đổi, và giải thuật thay đổi 
tuyến truyền, dẫn đến xác suất nghẽn luồng thấp hơn, và chỉ số tuyến truyền này lại 
tiếp tục được sử dụng để định tuyến tiếp  từ đó, giải thuật có xác suất nghẽn thấp 
nhất như các hình 3.4 và 3.5. 
Hình 3.5 Xác suất nghẽn băng thông trên ISP1 
61 
Trong thí nghiệm mô phỏng tiếp theo, ta lấy thông tin về thông số trễ đầu 
cuối-đầu cuối với các dạng tải thông tin thay đổi (với tải = 0,2 đến 0,8). Tính toán 
và so sánh kết quả giữa giải thuật RBDA và WSP, kết quả như biểu diễn ở hình 3.6. 
Từ hình 3.6, ta có thể thấy được rằng khi số lượng các luồng tin tăng lên, có 
thêm nhiều luồng tin trên mạng thì giá trị trễ đầu cuối- đầu cuối tăng lên, và giải 
thuật RBDA cho thấy đạt được hiệu năng tốt hơn. 
Hình 3.6 Giá trị trễ đầu cuối trung bình khi thay đổi tải 
Sự chênh lệch giữa hai giải thuật là tương đối bé khi = 0,2, nhưng khi tải lớn 
hơn > 0,4, mức chênh lệch giữa hai giải thuật sẽ cao hơn như hình biểu diễn.Nghĩa 
là khi với tải cao hơn thì nghẽn xảy ra thường xuyên hơn, vì thế giá trị này cao hơn. 
Trong trường hợp của giải thuật RBDA, do các luồng tin thay đổi tuyến truyền 
thường xuyên hơn dựa vào chỉ số Ci, Ni, nên khi nghẽn xảy ra, chỉ số của tuyến 
truyền giảm xuống, và tuyến truyền khác có chỉ số (Ci, Ni) cao hơn sẽ thay thế. Vì 
thế, giá trị trễ trung bình toàn mạng của RBDA sẽ tốt hơn trường hợp WSP. 
b. Trên mạng mô phỏng ISP2: 
Hình 3.7 Xác suất nghẽn luồng trên ISP2 
62 
Hình 3.7 mô tả xác suất nghẽn luồng của giải thuật RBDA so sánh với các giải 
thuật khác như CBR, PSR và WSP trên mô hình ISP2. Tương tự như ở mô hình 
ISP1, sự khác nhau của các giải thuật chủ yếu khi tải tăng lên cao. Bởi vì khi tải 
tăng cao ( > 0,3), các nút mạng trở nên nghẽn làm cho xác suất nghẽn tăng lên như 
hình mô tả. RBDA sử dụng chỉ số để thay đổi tuyến truyền khi nút mạng nghẽn, nên 
khi nghẽn xảy ra, RBDA thay đổi tuyến truyền và hạn chế sử dụng tuyến truyền đã 
gây nghẽn nên có giá trị tốt nhất. 
Giải thuật WSPcó giá trị cao nhất với lý do là giải thuật cứ căn cứ vào giá trị 
thông tin toàn mạng tìm được, sử dụng thuật toán tìm đường, và tìm đường ngắn 
nhất, và thực hiện điều này đến khi gây nghẽn. Do đó, WSP có giá trị nghẽn luồng 
cao nhất. 
Trong các thí nghiệm tiếp theo, luận án thu thập dữ liệu về thông số trễ đầu 
cuối - đầu cuối với các dạng tải thông tin thay đổi (với tải = 0,2 và 0,5). Tính toán 
và so sánh kết quả giữa giải thuật RBDA và WSP, kết quả như biểu diễn ở hình 3.8. 
Hình 3.8 Giá trị trễ đầu cuối trung bình khi tải cao và thấp trên ISP2 
Từ hình 3.8, ta có thể thấy được rằng khi số lượng các luồng tin tăng lên, thì 
giá trị trễ đầu cuối- đầu cuối tăng lên, và giải thuật RBDA cho thấy đạt được hiệu 
năng tốt hơn. Sự chênh lệch giữa hai giải thuật là tương đối bé khi = 0,2, nhưng 
khi tải = 0,5, mức chênh lệch giữa hai giải thuật sẽ cao hơn như hình biểu diễn. 
Điều này là do khi tải cao thì nghẽn xảy ra thường xuyên hơn, vì thế giá trị này cao 
hơn. Trong trường hợp của giải thuật RBDA, tương tự với mô hình ISP1, do các 
63 
luồng tin thay đổi tuyến truyền thường xuyên hơn dựa vào chỉ số Ci, Ni. Nên khi 
nghẽn xảy ra, chỉ số của tuyến truyền giảm xuống, và tuyến truyền khác có chỉ số 
(Ci, Ni) cao hơn sẽ thay thế. Vì thế, giá trị trễ trung bình toàn mạng của RBDA sẽ 
tốt hơn trường hợp WSP. 
Tóm lại, với các kết quả mô phỏng như các phần trên, có thể thấy được giải 
thuật đề xuất RBDA có hiệu năng tốt hơn các trường hợp được khảo sát như trong 
các thí nghiệm mô phỏng. 
3.3.4. Mô tả giải thuật BQRA 
Giống như giải thuật RBDA, BQRA cũng xác định trước và duy trì tại tất cả 
các nút mạng các tập hợp R các tuyến truyền đến tất cả các nút đích. Mỗi tuyến 
truyền Pi R cũng liên kết với một biến Pi.Quality=Pi.[Bandwidth,Delay] và một chỉ 
số tuyến truyền βi. Khác với giải thuật RBDA, các giá trị βi liên quan đến tỷ lệ 
luồng bị nghẽn trong quá trình định tuyến.Gọi BFi là số luồng bị nghẽn trên tuyến 
truyền đó, và Ti là tổng số luồng sử dụng tuyến truyền đó. Trong đó: 
βi = (1-BFi/Ti) (3.5) 
Để chọn đường, tương tự giải thuật RBDA, tập R sẽ được sắp xếp theo giá trị 
của βi.Với mỗi luồng thông tin yêu cầu đến nút nguồn, BQRA chọn tuyến truyền Pi 
có giá trị βi lớn nhất trong tập R đó hay gọi tắt là max(βi). Tiếp theo, BQRA cũng 
kiểm tra yêu cầu về băng thông và độ trễ của luồng dữ liệu tới từ thông số SLA 
(thỏa thuận mức chất lượng giữa mạng và người sử dụng [32]) của luồng dữ liệu. Ta 
gọi giá trị này là SLA, và lấy giá trị này để so sánh chọn đường. Nếu không có yêu 
cầu về QoS cho luồng này, tuyến truyền Pi sẽ được chọn để truyền thông tin. Nếu có 
yêu cầu về QoS, BQRA so sánh Pi. Qualityvà SLA (cách so sánh tuần tự như mô tả 
ở thủ tục ở hình 1.3. 
Nếu Pi.Quality ≥ SLA: Tuyến truyền được lựa chọn để truyền thông tin đi. 
Nếu Pi.Quality < SLA: BQRA chọn tuyến truyền tiếp theo của tập R, và vòng 
lặp sẽ được tiếp tục cho đến khi tìm ra được một tuyến truyền Pi có giá trị βi cao 
nhất và Pi.Quality ≥ SLA. 
64 
Nếu không có tuyến truyền nào trong tập R thỏa mãn Pi.Quality ≥ SLA, thì 
luồng dữ liệu đến bị từ chối (do không có đường nào thỏa mãn yêu cầu chất lượng 
của luồng dữ liệu), các chỉ số Ti, BFi sẽ tăng. Nếu truyền thành công một luồng đến 
đích, thì chỉ có giá trị Ti tăng thôi. 
Ta thấy, BQRA chỉ thay đổi chỉ số βi của tuyến truyền tương ứng với khả năng 
truyền tải dữ liệu của tuyến truyền đã chọn. Khi tuyến truyền truyền thành công, 
hay không thành công, giải thuật sẽ tăng hay giảm các giá trị Ti, BFi tương ứng, hay 
là tăng hay giám giá trị βi. Từ đó, giá trị βi quyết định khả năng chọn đường tiếp 
theo, trên các tuyến truyền qua nút nguồn đến nút đích trên mạng. 
Các mô tả khác về giải thuật BQRA tương tự giải thuật RBDA ở trên. 
3.3.5. Mô phỏng đánh giá hiệu năng giải thuật định tuyến BQRA 
Trong phần này, giải thuật BQRA được mô phỏng, tính toán các giá trị cân 
bằng tải qua hệ số DBM và các giá trị độ trễ đầu cuối – đầu cuối khi thay đổi tải 
mạng, đồng thời so sánh với giải thuật định tuyến