Luận án Giải quyết bài toán định tuyến đảm bảo băng thông, độ trễ

một phương pháp tính trọng số đơn giản dựa trên giá trị băng thông còn lại:
 1
 wri(l) = (3.1)
 bri(l) + relBwri+1(l)
Gọi yêu cầu định tuyến đang xử lý là yêu cầu thứ i : ri, thời điểm xử lý ri là tri, công
thức 3.1 tính trọng số của liên kết l để tìm đường đi cho ri với b(l) là băng thông còn
lại của l tại thời điểm tri, relBw(l) là băng thông sẽ được giải phóng trên liên kết l tại
thời điểm tri+1 khi yêu cầu kế tiếp ri+1 đến. Nói cách khác, mẫu số (b(l) + relBw(l))
là băng thông còn lại của liên kết l tại thời điểm xử lý yêu cầu kế tiếp tri+1.
 Để tính được relBw(l), hệ thống mạng cần có thông tin thời gian giữ băng thông
của các yêu cầu định tuyến đã được chấp nhận. Thông tin này có thể được máy chủ
định tuyến ước tính từ những yêu cầu đã kết thúc. Hoặc thời gian giữ băng thông được
gửi kèm với mỗi yêu cầu định tuyến. Điều này có thể thực hiện được vì bên sử dụng
dịch vụ định tuyến sẽ biết thời gian cần truyền dữ liệu (thời gian giữ băng thông) và
thời gian này được gửi đến hệ thống mạng trong gói tin yêu cầu thiết lập của giao thức
định tuyến. Trong thuật toán đề xuất, yêu cầu định tuyến được giả sử đã bao gồm thời
gian giữ băng thông, nghĩa là yêu cầu ri(s;d;b;h) gồm nút nguồn s, nút đích d, băng
thông cần đảm bảo b, và thời gian giữ băng thông h nếu yêu cầu được chấp nhận.
 Ngoài ra, thời điểm đến của yêu cầu kế tiếp tri+1 không thể xác định một cách chính
xác vì điều kiện bài toán là không biết trước yêu cầu định tuyến. Vì vậy, thuật toán
cần dự đoán thời điểm đến dựa trên những yêu cầu đã nhận được. Với mục đích giảm
thiểu thời gian tính toán, BHGT sử dụng phân phối tam giác [21] để phát sinh thời
điểm đến kế tiếp. Phân phối tam giác là một phân phối liên tục với biến ngẫu nhiên x
nằm trong đoạn [min;max], có yếu vị mode, và có hàm phân phối:
 8 2
 < (x−min) ; nếu min ≤ x ≤ mode
 D(x) = (max−min)(mode−min) (3.2)
 (max−x)2
 :1 − (max−min)(max−mode); nếu mode < x ≤ max
Thuật toán tính khoảng thời gian giữa hai yêu cầu liên tiếp đã nhận được, và áp dụng
phân phối tam giác để phát sinh khoảng thời gian sẽ nhận được yêu cầu kế tiếp. Cụ
 43
thể, khi nhận được yêu cầu ri, thuật toán tính khoảng thời gian giữa ri và yêu cầu trước
đó ri−1: Dti = tri −tri−1. Giá trị Dti này được cập nhật vào ba tham số của phân phối
tam giác min, max, và mode với min là khoảng thời gian giữa hai yêu cầu định tuyến
nhỏ nhất, max là khoảng thời gian lớn nhất, và mode được tính bằng giá trị trung bình
các khoảng thời gian đã biết. Sau đó, phân phối tam giác được sử dụng để phát sinh
một giá trị ngẫu nhiên Dti+1 được xem như khoảng thời gian giữa yêu cầu hiện tại ri
và yêu cầu kế tiếp ri+1. Như vậy, thuật toán dự đoán thời điểm đến của yêu cầu kế
tiếp rr+1 là tri+1 = ti + Dti+1.
 Bảng 3.1 trình bày các bước thực hiện thuật toán định tuyến được đề xuất với tên
gọi thuật toán định tuyến đảm bảo băng thông sử dụng thời gian giữ - Bandwidth
Guaranteed routing algorithm using Holding Time (BGHT). Đầu vào của thuật toán
ngoài sơ đồ mạng, có thêm thời gian giữ băng thông của yêu cầu định tuyến nếu được
chấp nhận và danh sách các đường đi đang đảm bảo băng thông với thời điểm kết
thúc tương ứng. Thông tin về thời gian giữ này giúp thuật toán tính được băng thông
sẽ được giải phóng trong tương lai. Thuật toán BGHT xử lý mỗi yêu cầu định tuyến
với bốn bước đơn giản, có độ phức tạp tính toán thấp. Thứ nhất, tạm thời loại bỏ liên
kết không đủ băng thông còn lại. Thứ hai, tính khoảng cách giữa thời điểm đến của
yêu cầu đang xử lý và yêu cầu trước đó, cập nhật ba tham số phân phối tam giác min,
max, mode và phát sinh khoảng thời gian yêu cầu kế tiếp sẽ đến Dti+1. Thứ ba, tính
băng thông sẽ được giải phóng tại thời điểm tri+1 = ti + Dti+1 và tính trọng số cho mỗi
liên kết theo công thức 3.1. Cuối cùng, sử dụng Dijkstra tìm đường đi trọng số nhỏ
nhất cho yêu cầu định tuyến.
 Bảng 3.1: Thuật toán BGHT
Đầu vào Sơ đồ mạng G(N;L)
 Danh sách đường đi đang đảm bảo
 Yêu cầu định tuyến r(s;d;b;h)
Đầu ra Một đường đi psd
 Hoặc không có đường đi thỏa yêu cầu
Các bước xử lý Với mỗi yêu cầu r(s;d;b;h):
 1. Bỏ qua những liên kết không đủ băng thông yêu cầu b(l) < b
 2. Tính Dti , cập nhật tham số và phát sinh Dti+1 bằng phân phối tam giác
 3. Tính băng thông sẽ giải phóng và trọng số cho các liên kết còn lại w(l) theo
 công thức 3.1
 4. Sử dụng Dijkstra tìm đường đi trọng số nhỏ nhất từ s đến d
 Nếu tìm được: trả về psd và cập nhật các thông tin cần thiết
 Ngược lại: từ chối yêu cầu (không có đường đi).
 44
3.1.2 Ví dụ minh họa
 Kết quả thuật toán BGHT cho ví dụ hình 3.1 như sau:
 • Yêu cầu r1(1;5;1;5), t1 = 1: không tính Dt1;Dt2, và băng thông sẽ giải phóng vì
 đây là yêu cầu đầu tiên, đường đi p1 = (1;2;3;4;5) được chọn sau khi tính trọng
 số liên kết (hình 3.2a)
 • Yêu cầu r2(1;5;1;5), t2 = 4: tính được Dt2 = 3; phát sinh Dt3 = 3 (min = max =
 mode = 3), đường đi p1 = (1;2;3;4;5) được chọn sau khi tính trọng số liên kết
 (hình 3.2b)
 • Yêu cầu r3(8;9;2;5), t3 = 8: tính được Dt3 = 4; phát sinh Dt4 = 4 (min = 3;max =
 4;mode = 3:5), đường đi p2 = (8;6;7;9) được chọn sau khi tính trọng số liên
 kết (hình 3.2c)
 (a) Kết quả BGHT xử lý yêu cầu r1
 (b) Kết quả BGHT xử lý yêu cầu r2
 45
 (c) Kết quả BGHT xử lý yêu cầu r3
 Hình 3.2: Kết quả ví dụ minh họa thuật toán BGHT
3.1.3 Phân tích hoạt động
 Thuật toán đề xuất BGHT gồm bốn bước chỉ xử lý trên liên kết và không tính toán
độ tới hạn theo đường đi như phần lớn công trình liên quan. Cụ thể, bước 1 và bước
3 duyệt liên kết để đảm bảo băng thông và tính trọng số, bước 4 áp dụng thuật toán
Dijkstra để tìm đường đi trọng số nhỏ nhất. Giả sử Dijkstra được cài đặt theo phương
pháp cổ điển độ phức tạp O(nm), thuật toán BGHT sẽ có độ phức tạp O(m + nm) với
m là số liên kết và n số nút trong sơ đồ mạng. Độ phức tạp này bằng độ phức tạp của
các công trình liên quan có thời gian tính toán nhanh đã công bố như DORA, BCRA,
BGMRA, và thấp hơn nhiều so với thuật toán MIRA dùng luồng cực đại (MIRA có
độ phức tạp của quá trình tính luồng cực đại - tập cắt cực tiểu và thuật toán Dijkstra
O((k − 1)nm2 + nm)) với k là số cặp nguồn đích.
 Mặt khác, trọng số BGHT bao gồm băng thông sẽ giải phóng khi yêu cầu định
tuyến kế tiếp (được dự đoán) đến, heuristic này có ý nghĩa tham lam lựa chọn đường
đi cân băng tải sao cho có thể tiếp tục giải quyết yêu cầu kế tiếp một cách tốt nhất.
Tuy nhiên, vì thuật toán dự đoán khoảng thời gian đến của yêu cầu kế tiếp dựa trên
các yêu cầu đã nhận được bằng cách phát sinh ngẫu nhiên theo phân phối tam giác,
nên khi thử nghiệm nhiều lần trên cùng một bộ yêu cầu, kết quả BGHT có thể khác
nhau phụ thuộc vào giá trị được phát sinh. Thử nghiệm được trình bày ở mục 3.3 sẽ
chứng minh thuật toán BGHT có kết quả định tuyến rất tốt cả về tỉ lệ chấp nhận yêu
cầu định tuyến và thời gian tính toán định tuyến trung bình.
 46
3.2 TEARD: THUẬT TOÁN ĐỊNH TUYẾN ĐẢM BẢO BĂNG THÔNG SỬ
 DỤNG DỮ LIỆU ĐỊNH TUYẾN
3.2.1 Thuật toán đề xuất TEARD
 Thuật toán định tuyến BGHT được đề xuất với giả sử yêu cầu định tuyến có thêm
thời gian giữ băng thông, với mong muốn giải quyết bài toán với định nghĩa ban đầu
(không bổ sung giả sử), nghiên cứu sinh giới thiệu một thuật toán khác sử dụng dữ
liệu từ quá trình định tuyến bao gồm trạng thái sơ đồ mạng, thông tin từ các yêu cầu
định tuyến và đường đi đã sử dụng trong quá khứ. Thuật toán được đặt tên là Traffic
Engineering routing algorithm using Routing Data (TEARD).
 Trọng số liên kết của thuật toán TEARD bao gồm ba thành phần. Thành phần thứ
nhất xét độ tới hạn của liên kết theo các cặp nút nguồn đích. Đầu tiên, độ tới hạn
được tính theo tỉ lệ xuất hiện của liên kết trên tổng số đường đi. Ví dụ liên kết l thuộc
3 trong tổng số 5 đường đi của cặp nguồn đích ie thì độ tới hạn của l đối với ie là
critie(l) = 3=5. Việc tính toán này chỉ phụ thuộc vào sơ đồ mạng nên được thực hiện
trong pha offline (trước khi có yêu cầu định tuyến) và chỉ thực hiện lại khi sơ đồ mạng
có thay đổi. Sau đó, trong pha online, độ tới hạn theo cặp nguồn đích này được nhân
với xác suất mà cặp đó đã được yêu cầu. Sự điều chỉnh này nhằm giúp giá trị tới hạn
của liên kết linh hoạt với yêu cầu thực tế. Ví dụ khi liên kết l thuộc nhiều đường đi
của cặp ie thì giá trị critie(l) cao, dẫn đến thuật toán hạn chế sử dụng l. Nhưng nếu
cặp ie ít được yêu cầu thì việc hạn chế có thể ảnh hưởng xấu đến hiệu quả định tuyến.
Trong trường hợp này, phép nhân với xác suất thấp của ie giúp giảm giá trị critie(l).
Như vậy, giá trị tới hạn theo cặp nút nguồn đích được tính theo công thức sau:
 crit1(l) = ∑ (prob(ie) ∗ critie(l)) (3.3)
 ie2IE
Trong đó prob(ie) là xác suất cặp ie được yêu cầu. Trong cài đặt hiện tại, prob(ie)
được tính đơn giản là tỉ lệ giữa số yêu cầu định tuyến cho cặp ie trên tổng số yêu cầu
đã nhận được. Ngoài ra critie(l) là độ tới hạn của liên kết l đối với cặp nguồn đích ie
tính trong pha offline:
 ∑ vl
 p 2P(ie)
 crit (l) = ie (3.4)
 ie jP(ie)j
 47
 8
 <0 if l 2= pie
 vl =
 :1 if l 2 pie
 P(ie) là tập hợp đường đi từ i tới e
 pie là một đường đi trong tập hợp P(ie)
 jP(ie)j là tổng số đường đi từ i tới e
 Thành phần trọng số thứ hai xem xét giá trị băng thông, đặc biệt là băng thông
còn lại của liên kết. Để tránh tình trạng nghẽn mạng, một liên kết còn ít băng thông
không nên được sử dụng. Tương tự, một liên kết đã sử dụng nhiều băng thông cũng
không nên tiếp tục sử dụng. Áp dụng ý tưởng trên, giá trị tới hạn theo băng thông
được tính tỉ lệ nghịch với băng thông còn lại và tỉ lệ thuận với băng thông đã sử dụng
theo công thức sau:
 used(l) c(l) − b(l)
 crit (l) = = (3.5)
 2 r(l) b(l)
Trong đó, c(l) và b(l) lần lượt là dung lượng và băng thông còn lại của liên kết l.
Theo công thức 3.5, đối với hai liên kết cùng dung lượng, liên kết nào còn ít băng
thông hơn sẽ có giá trị trọng số lớn hơn và sẽ được thuật toán tìm đường đi ngắn nhất
Dijkstra hạn chế lựa chọn. Điều này giúp thuật toán cân bằng tải và tránh hiện tượng
thắt cổ chai. Với ý nghĩa tương tự, trong hai liên kết có cùng băng thông còn lại, liên
kết nào có dung lượng lớn (dẫn đến giá trị trọng số lớn) cũng sẽ được hạn chế sử dụng
vì liên kết này đang đảm bảo lượng băng thông lớn hơn liên kết còn lại.
 Thành phần trọng số liên kết thứ ba được tính theo tần suất sử dụng liên kết trong
các đường đi đã được thiết lập (công thức 3.6). Mục đích của thành phần này cũng
nhằm cân bằng việc lựa chọn liên kết trong đó liên kết đã được chọn nhiều lần sẽ có
giá trị cao.
 jEstP j
 crit (l) = l (3.6)
 3 jEstPj
 jEstPlj là tổng số đường đi đã được thiết lập có chứa liên kết l
 jEstPj là tổng số đường đi đã được thiết lập
 Cuối cùng, công thức 3.7 tổng hợp ba giá trị tới hạn trên thành trọng số liên kết
 48
của thuật toán đề xuất TEARD:
 w(l) = k1:crit1(l) + k2:crit2(l) + k3:crit3(l) (3.7)
 k1;k2;k3 là tham số điều chỉnh
 0 < k1;k2;k3 và k1 + k2 + k3 = 1
 Bảng 3.2 trình bày các bước của thuật toán định tuyến được đề xuất TEARD. Trong
pha offline, thuật toán depth-first search [14] được sử dụng để tìm đường đi cho các
cặp nguồn đích. Lưu ý pha offline thực hiện trước khi có yêu cầu định tuyến và chỉ
thực hiện lại khi sơ đồ mạng thay đổi (thêm hoặc giảm liên kết trong sơ đồ mạng).
Trong khi đó, pha online là quá trình tìm đường đi khi nhận được yêu cầu.
 Bảng 3.2: Thuật toán TEARD
Đầu vào Sơ đồ mạng G(N;L)
 Yêu cầu định tuyến r(s;d;b)
Đầu ra Một đường đi psd
 Hoặc không có đường đi thỏa yêu cầu
Pha offline 1. Với mỗi cặp nguồn đích ie, tính critie(l) theo công thức (3.4)
Pha online Với mỗi yêu cầu r(s;d;b):
 1. Bỏ qua những liên kết không đủ băng thông yêu cầu b(l) < b
 2. Tính trọng số cho các liên kết còn lại w(l) theo công thức 3.7
 3. Cập nhật dữ liệu định tuyến để xử lý yêu cầu kế tiếp
 4. Sử dụng Dijkstra tìm đường đi trọng số nhỏ nhất từ s đến d
 Nếu tìm được: trả về psd
 Ngược lại: từ chối yêu cầu (không có đường đi).
3.2.2 Ví dụ minh họa
 Xét một ví dụ minh họa với sơ đồ mạng và yêu cầu định tuyến như hình 3.3. Có
hai cặp nút nguồn đích 1-6 và 9-10, dung lượng liên kết được lựa chọn để thể hiện sự
khác nhau của thuật toán đề xuất với các công trình liên quan, cụ thể cặp nguồn đích
1-6 có 2 đường đi, trong đó đường đi ngắn hơn có băng thông lớn hơn đường còn lại.
Ba yêu cầu định tuyến r1;r2;r3 đến tuần tự và có thời gian giữ lâu, không ảnh hưởng
đến quá trình định tuyến.
 49
 Hình 3.3: Ví dụ minh họa thuật toán TEARD
 Kết quả thuật toán TEARD với trọng số k1 = 0:3;k2 = 0:4;k3 = 0:3 cho ví dụ hình
3.3 như sau:
 • Pha offline: cặp nguồn đích 1-6 có 2 đường đi p1 = (1;2;3;4;5;6) và p2 =
 (1;7;8;6), cặp 9-10 chỉ có 1 đường p3 = (9;7;8;10). Độ tới hạn của liên kết đối
 với mỗi cặp nguồn đích được thể hiện trong hình 3.4a
 • Pha online: xử lý yêu cầu r1(1;6;1): đây là yêu cầu đầu tiên, các liên kết chưa
 được sử dụng nên trọng số bằng e (một giá trị dương rất nhỏ để Dijkstra hoạt
 động). Thuật toán lựa chọn đường đi ngắn nhất p2 = (1;7;8;6) cho cặp nguồn
 đích 1-6 (hình 3.4b, đường đi được chọn được in đậm)
 • Xử lý yêu cầu r2(1;6;2): các liên kết của đường p2 = (1;7;8;6) đã được sử
 dụng nên được tính giá trị trọng số lớn hơn so với các liên kết trên đường p1 =
 (1;2;3;4;5;6). Sau khi tính trọng số liên kết, đường đi p1 có trọng số wp1 = 0
 nhỏ hơn wp2 = 0 nên được sử dụng (hình 3.4c).
 • Xử lý yêu cầu r3(9;10;2): đường đi duy nhất p3 = (9;7;8;10) có thể được sử
 dụng vì yêu cầu r2 đã được đáp ứng bằng đường p1 = (1;2;3;4;5;6).
 50
 (a) Kết quả TEARD pha offine
(b) Kết quả TEARD xử lý yêu cầu r1
(c) Kết quả TEARD xử lý yêu cầu r2
 51
 (d) Kết quả TEARD xử lý yêu cầu r3
 Hình 3.4: Kết quả ví dụ minh họa thuật toán TEARD
 Trong ví dụ này, thuật toán TEARD đã chọn đường đi p1 = (1;2;3;4;5;6) khi
xử lý yêu cầu r2(1;6;2 nên yêu cầu r3(9;10;2) có thể được đáp ứng bằng đường đi
p3 = (9;7;8;10). So sánh với thuật toán BGMRA (khi xử lý yêu cầu r2), trọng số
được tính tỉ lệ nghịch với băng thông còn lại, vì băng thông còn lại của p2 = (1;7;8;6)
lớn nên BGMRA tiếp tục chọn p2 = (1;7;8;6) cho r2 từ đó không đáp ứng được yêu
cầu r3. Tương tự với thuật toán MIRA, vì liên kết (7;8) có băng thông còn lại lớn hơn
luồng cực đại của cặp 9-10 nên (7;8) không được xem là liên kết tới hạn và MIRA
cũng chọn đường đi p2 = (1;7;8;6).
3.2.3 Phân tích hoạt động
 Thuật toán đề xuất TEARD có hai pha hoạt động. Pha offline tìm đường đi cho
mỗi cặp nguồn đích bằng cách điều chỉnh và áp dụng thuật toán depth first search đệ
qui. Như vậy pha offline có độ phức tạp đệ qui và thời gian thực hiện tương đối lâu.
Tuy nhiên quá trình này thực hiện một lần khi bắt đầu quá trình định tuyến và chỉ cần
thực hiện lại khi sơ đồ mạng có sự thay đổi (trong quá trình hoạt động, nhà cung cấp
dịch vụ mạng cố gắng hạn chế sự thay đổi này). Hơn nữa, pha offline có thể thực hiện
độc lập với pha online, nghĩa là nếu có yêu cầu định tuyến khi chưa tính toán xong
các giá trị critie thì thuật toán vẫn có thể tính trọng số liên kết mà bỏ qua giá trị crit1
hoặc sử dụng giá trị critie cũ đã tính trước khi sơ đồ mạng thay đổi.
 Mặt khác, pha online của thuật toán TEARD có độ phức tạp O(km+mn) với k;m;n
lần lượt là số cặp nguồn đích, số liên kết và số nút mạng. Trong đó, O(km) là độ phức
tạp của các bước xử lý tính trọng số liên kết bao gồm tính độ tới hạn theo từng cặp
nguồn đích, O(mn) là độ phức tạp của thuật toán tìm đường Dijkstra. Bảng 3.3 so
 52
sánh độ phức tạp xử lý yêu cầu định tuyến (pha online) của các thuật toán định tuyến
đảm băng thông. Có thể thấy thuật toán sử dụng luồng cực đại có độ phức tạp cao
hơn hẳn các thuật toán tính trọng số liên kết sử dụng giá trị khác. Ngoài ra, hai thuật
toán sử dụng kĩ thuật máy học đua ngẫu nhiên không xác định được độ phức tạp vì
quá trình đua phụ thuộc vào yêu cầu định tuyến.
 Bảng 3.3: Độ phức tạp của thuật toán định tuyến đảm bảo băng thông
 Thuật toán Độ phức tạp
 MHA [22], BCRA [32]
 DORA [11], BGMRA [33] O(m + mn)
 BGHT
 TEARD O(km + mn)
 MIRA [27], NewMIRA [65] O((k − 1)nm2 + nm)
 Trọng số liên kết của thuật toán TEARD được tính từ các dữ liệu khác nhau trong
quá trình định tuyến. Thứ nhất, sơ đồ mạng được sử dụng để tính độ tới hạn theo từng
cặp nguồn đích với ý nghĩa liên kết càng nằm trong nhiều đường đi thì càng có nhiều
ảnh hưởng nếu được sử dụng, giá trị này còn được điều chỉnh bởi tỉ lệ yêu cầu của cặp
nguồn đích trong thực tế nhằm tăng sự linh động của trọng số. Thứ hai, thuộc tính
quan trọng băng thông, không chỉ băng thông còn lại mà cả băng thông đang đảm bảo
của liên kết được thể hiện trong trọng số. Cuối cùng, lịch sử sử dụng liên kết cũng
được xem xét trong thành phần trọng số liên kết thứ ba. Ý tưởng heuristic của việc sử
dụng dữ liệu định tuyến này là cố gắng tính trọng số một cách linh động, phù hợp với
quá trình đã qua và chuẩn bị tốt nhất cho những yêu cầu sắp đến.
 Mục kết quả mô phỏng kế tiếp sẽ chứng tỏ hiệu quả của hai thuật toán định tuyến
đảm bảo băng thông đề xuất BGHT và TEARD so với các công trình liên quan đã
công bố.
3.3 KẾT QUẢ MÔ PHỎNG
 Các thuật toán định tuyến đảm bảo băng thông liên quan bao gồm MHA, BCRA,
MIRA, NewMIRA, DORA, BGMRA, RRATE, POOA và hai thuật toán nghiên cứu
sinh đề xuất BGHT, TEARD được thử nghiệm, so sánh, đánh giá dựa trên ba tiêu chí
tỉ lệ chấp nhận yêu cầu định tuyến (đơn vị %), thời gian tính toán định tuyến trung
bình (đơn vị mili giây), và độ lệch chuẩn tải liên kết (đơn vị %). Như đã giới thiệu ở
mục 2.4, ba sơ đồ mạng thử nghiệm là MIRA, CESNET, và ANSNET. Có hai kịch
bản cho yêu cầu định tuyến: định tuyến tĩnh và định tuyến động. Trong kịch bản thứ
 53
nhất, đường đi, nếu được thiết lập, sẽ giữ băng thông đến khi kết thúc thử nghiệm.
Kịch bản này dùng minh họa khả năng của thuật toán nhưng ít có ý nghĩa trong hoạt
động thực tế. Trong kịch bản thứ hai, đường đi sẽ trả băng thông sau một thời gian sử
dụng. Kịch bản động gồm hai trường hợp nhỏ: điều kiện tải bình thường và điều kiện
tải cao. Điều kiện tải bình thường có số lượng yêu cầu và số yêu cầu đến trong một
đơn vị thời gian ít hơn điều kiện tải cao. Hơn nữa, thời gian giữ băng thông của yêu
cầu tải bình thường cũng ngắn hơn.
 Mô phỏng được thực hiện trên hệ thống máy tính có cùng cấu hình: sử dụng
Microsoft .NET Framework 4.0, bộ xử lý Intel Dual Core 3.1 GHz, bộ nhớ 2048 MB
RAM. Tiểu mục 3.3.1 phân tích các đặc điểm của kết quả mô phỏng khi thay đổi tham
số yêu cầu định tuyến như thay đổi băng thông, thay đổi số cặp nguồn đích. Tiểu mục
3.3.2 so sánh hiệu quả định tuyến của hai thuật toán đã đề xuất với các công trình
liên quan trên số lượng lớn (900) bộ dữ liệu đã được phát sinh. Cuối cùng, tiểu mục
3.3.3 phân tích kĩ hơn hoạt động của thuật toán đề xuất TEARD bằng cách thay đổi
các tham số liên quan.
 Ngoài ra, giá trị tham số của các thuật toán được sử dụng trong quá trình mô phỏng
là giá trị đã được tác giả của các thuật toán này trình bày trong các công trình tương
ứng, cụ thể:
 • Thuật toán MIRA [27]: tham số điều chỉnh aie = 1;8ie, có ý nghĩa các cặp
 nguồn đích cùng mức độ quan trọng.
 • Thuật toán DORA [11]: tham số điều chỉnh a = 0:9, có ý nghĩa thành phần liên
 quan đến băng thông còn lại chiếm tỉ lệ 90% trong trọng số liên kết. Theo kết
 quả trình bày trong công trình này, DORA đạt tỉ lệ chấp nhận yêu cầu định tuyến
 cao nhất với giá trị 0:9 (cao hơn tỉ lệ của a = 0:5).
 • Thuật toán RRATE [47]: số đường chọn trước k = 25, số lần đua N = 10, giá trị
 hai tham số điều chỉnh k1 = k2 = 0:5. Theo các tác giả của RRARE các tham số
 heuristic này có ảnh hưởng lớn đến kết quả định tuyến, tuy nhiên phương pháp
 xác định giá trị không được đề cập. Vì vậy, nghiên cứu sinh tự lựa chọn giá trị từ
 các thử nghiệm đã thực hiện.
 • Tương tự RRATE, thuật toán POOA [35] có tham số k = N = 20.
 • Thuật toán đề xuất TEARD sử dụng tham số k1 = 0:3, k2 = 0:4, k3 = 0:3 với ý
 nghĩa ba thành phần đều có ảnh hưởng tương đương nhau trong trọng số liên kết.
 Tiểu mục 3.3.3 sẽ báo cáo chi tiết hơn về sự ảnh hưởng của các tham số này.
 54
3.3.1 Kết quả k