Một giải thuật lập lịch đảm bảo chất lượng dịch vụ trong mạng chuyển mạch chùm quang

ng, đã làm gia tăng không ngừng nhu cầu về băng thông 
truyền thông. Điều này đã đặt ra một thách thức mới trong việc tìm kiếm công nghệ 
truyền thông phù hợp nhằm nâng cao khả năng vận chuyển của mạng thế hệ mới. Mạng 
sợi quang cùng với sự phát triển của công nghệ ghép kênh bước sóng (Wavelength 
Division Multiplexing), đã mang đến một giải pháp hoàn hảo đáp ứng được nhu cầu 
băng thông bùng nổ của Internet trong tương lai. Từ khi xuất hiện vào thập niên 90, 
mạng sợi quang đã trải qua nhiều thế hệ phát triển [1]: từ những mô hình định tuyến 
bước sóng (Wavelength-Routed) ban đầu dựa trên những đường quang (lightpath) đầu 
cuối dành riêng, cho đến các mô hình chuyển mạch gói quang (Optical Packet 
Switching) được đề xuất gần đây, với ý tưởng xuất phát từ các mô hình mạng chuyển 
mạch gói điện tử. Tuy nhiên với một số hạn chế về công nghệ, như chưa thể sản xuất 
các bộ đệm quang (tương tự bộ nhớ RAM trong môi trường điện tử) hay các chuyển 
mạch ở tốc độ nano giây [1] mô hình chuyển mạch gói quang chưa thể trở thành hiện 
136 NGUYỄN HỒNG QUỐC và cs. 
thực. Một giải pháp thỏa hiệp được đề xuất là chuyển mạch chùm quang (Optical Burst 
Switching) đã mở ra một hướng nghiên cứu mới và được xem là công nghệ hứa hẹn cho 
mạng Internet thế hệ tiếp theo. 
Một đặc trưng tiêu biểu của mạng chuyển mạch chùm quang (mạng OBS) là phần điều 
khiển (Burst Header Packet) được tách rời với phần dữ liệu (Data Burst). Nói một cách 
khác, để thực hiện việc truyền một chùm vào trong mạng OBS, gói điều khiển BHP 
được tạo ra và được gửi đi trước một khoảng thời gian offset(offset-time). Thời gian 
offset này phải được tính toán đủ để đặt trước tài nguyên và cấu hình các chuyển mạch 
tại các nút trung gian dọc theo hành trình của chùm quang từ nguồn đến đích. Thêm vào 
đó, mạng OBS dành riêng một số kênh (bước sóng), được gọi là kênh điều khiển cho 
việc truyền gói điều khiển BHP, trong khi các kênh còn lại được dùng cho việc truyền 
chùm dữ liệu, nên được gọi là kênh dữ liệu. Như vậy việc truyền gói điều khiển BHP 
tách rời hoàn toàn với truyền dữ liệu về mặt không gian và về mặt thời gian. Với cách 
truyền dữ liệu như vậy, rõ ràng mạng OBS không cần đến các bộ đệm quang để lưu tạm 
các chùm dữ liệu trong khi chờ đợi việc xử lý chuyển mạch tại các nút lõi, cũng như 
không yêu cầu các chuyển mạch ở tốc độ nano giây. Tuy nhiên, cách truyền tải này 
cũng đặt ra áp lực là làm thế nào để một gói điều khiển BHP kịp lập lịch đặt trước tài 
nguyên và cấu hình chuyển mạch tại các nút lõi, đảm bảo việc truyền tải chùm quang 
theo sau; đó chính là nhiệm vụ của hoạt động lập lịch đặt trước tài nguyên tại các nút lõi 
mạng. Vì vậy vấn đề lập lịch rất cần được quan tâm và nghiên cứu nhằm tối đa hiệu suất 
băng thông, giảm mất mát dữ liệu, đảm bảo chất lượng cho các dịch vụ khác nhau và 
nâng cao hiệu suất hoạt động của mạng OBS. 
Hiện nay có các giải thuật lập lịch có xét đến chất lượng dịch vụ đã được đề xuất gồm: G-
LAUC-VF (Generalized LAUC-VF) [6], LA-FFVF (Latest Available and First Fit 
Unused Channel with Void Filling) [7], SWG (Static Wavelength Grouping)[2], DWG 
(Dynamic Wavelength Grouping) [3] và LLAC (Load-Level Admission Control) [4]. Với 
giải thuật LA-FFVF sử dụng các giải thuật lập lịch trực tiếp LAUC để lập lịch cho các 
chùm ưu tiên cao và sử dụng giải thuật FFUC-VF để lập lịch cho các chùm ưu tiên thấp 
nhằm giảm độ phức tạp giải thuật và tận dụng các khoảng trống được tạo ra trên các kênh 
để lập lịch cho các chùm đến. Các giải thuật SWG, DWG thực hiện đảm bảo chất lượng 
dịch vụ cho các chùm ưu tiên và không ưu tiên thông qua việc thiết lập cố định các kênh 
bước sóng ra mà không xem xét tải lưu lượng đến của các lớp dịch vụ hay thông tin về tải 
lưu lượng để điều khiển chấp nhận lập lịch hay không của giải thuật LLAC được biết 
trước và không thay đổi. Bên cạnh đó các giải thuật này đều đưa giải pháp ưu tiên tuyệt 
đối đối với các chùm ưu tiên cao, nên trong trường hợp lưu lượng chùm ưu tiên cao đến 
thấp, tài nguyên được phân bổ cho chúng không được sử dụng hết, gây lãng phí băng 
thông trong khi đó chùm ưu tiên thấp không được lập lịch. Trong nghiên cứu, chúng tôi 
đề xuất một giải thuật lập lịch đảm bảo chất lượng dịch vụ với cách phân bổ tài nguyên 
bước sóng linh hoạt dựa trên tải lưu lượng đến của các lớp dịch vụ khác nhau. 
Cấu trúc tiếp theo của bài viết như sau: mục II mô tả giải thuật lập lịch đề xuất; mục III 
mô phỏng đánh giá giải thuật lập lịch đề xuất và mục IV là phần kết luận. 
MỘT GIẢI THUẬT LẬP LỊCH ĐẢM BẢO CHẤT LƯỢNG DỊCH VỤ 137 
2. GIẢI THUẬT LẬP LỊCH ĐỀ XUẤT 
Xét một liên kết (cổng) ra của một nút lõi mạng OBS mà tại đó các chùm đến được giả 
thiết thuộc về một trong hai lớp ưu tiên cao và ưu tiên thấp. Giả sử cổng ra có 𝑊 kênh 
bước sóng, một chùm ưu tiên cao đến có thể được lập lịch lên bất kỳ một trong 𝑊 kênh 
bước sóng; trong khi một chùm ưu tiên thấp đến chỉ được lập lịch trên một trong 𝑊𝐿 
kênh, với 𝑊𝐿 ≤ 𝑊. Cách làm này nhằm để dành tài nguyên kênh bước sóng nhiều nhất 
cho các chùm ưu tiên cao. Rõ ràng việc điều chỉnh phân bổ băng thông kênh bước sóng 
chỉ được thực hiện đối với luồng các chùm ưu tiên thấp đến, trong đó kênh bước sóng 
được cấp phát cho luồng này (𝑊𝐿) và sẽ được xác định qua một hàm tính các giá trị tải 
đến và sẽ thay đổi tương ứng theo lưu lượng tải của lớp ưu tiên cao và thấp. Theo đó, 
vấn đề đặt ra ở đây là cần tính toán lưu lượng tải các chùm (QoS cao và QoS thấp) đến 
trong mỗi khe thời gian quan sát (∆𝑡) để thực hiện phân phối kênh bước sóng (giá trị 
𝑊𝐿 cho các chùm QoS thấp một cách hiệu quả nhất nhằm tránh gây lãng phí băng thông 
trên mỗi kênh cũng như giảm xác suất tắc nghẽn. Khi đó, số kênh bước sóng cấp phát 
cho các chùm QoS thấp 𝑊𝐿(𝑊𝐿 ≤ 𝑊) được xác định là phần nguyên cận trên của Công 
thức (1) như sau: 
𝑊𝐿 = ⌈𝑊 ×
𝛾𝐿
𝛾𝐻 + 𝛾𝐿
⌉ (1) 
Với tải lưu lượng đến của các chùm QoS cao (𝛾𝐻) và chùm QoS thấp (𝛾𝐿) [2] được xác 
định dựa trên tốc độ chùm, độ dài chùm trung bình và băng thông hiện tại trên mỗi kênh 
bước sóng trong mỗi cửa số quan sát ∆𝑡 và được tính toán như sau: 
𝛾𝐿 =
𝐿
𝜇𝐿 × 𝑊
(2) 
𝛾𝐻 =
𝐻
𝜇𝐻 × 𝑊
(3) 
Trong đó 𝐿(𝐻) là tốc độ chùm đến, 𝜇𝐿(𝜇𝐻) là độ dài chùm trung bình của các chùm 
QoS thấp và cao đến trong mỗi cửa số quan sát. Được tính toán như sau: 
𝐿 =
𝑆ố 𝑙ượ𝑛𝑔 𝑐ℎù𝑚 đế𝑛 𝑄𝑜𝑆 𝑡ℎấ𝑝
∆𝑡
(4) 
𝐻 =
𝑆ố 𝑙ượ𝑛𝑔 𝑐ℎù𝑚 đế𝑛 𝑄𝑜𝑆 𝑐𝑎𝑜
∆𝑡
(5) 
𝜇𝐿 =
𝑇ổ𝑛𝑔 độ 𝑑à𝑖 𝑐ℎù𝑚 đế𝑛 𝑄𝑜𝑆 𝑡ℎấ𝑝
𝑆ố 𝑙ượ𝑛𝑔 𝑐ℎù𝑚 đế𝑛 𝑄𝑜𝑆 𝑡ℎấ𝑝
(6) 
𝜇𝐻 =
𝑇ổ𝑛𝑔 độ 𝑑à𝑖 𝑐ℎù𝑚 đế𝑛 𝑄𝑜𝑆 𝑐𝑎𝑜
𝑆ố 𝑙ượ𝑛𝑔 𝑐ℎù𝑚 đế𝑛 𝑄𝑜𝑆 𝑐𝑎𝑜
(7) 
Với cách tiếp cận nêu trên, cho phép đảm bảo ưu tiên cho các chùm ưu tiên cao, phân 
138 NGUYỄN HỒNG QUỐC và cs. 
bổ linh hoạt hơn số lượng kênh bước sóng có thể sử dụng cho các chùm ưu tiên thấp và 
để đánh giá phân tích ở trên, trong bài báo này chúng tôi cũng đề xuất một giải thuật lập 
lịch dưới đây: 
GIẢI THUẬT LẬP LỊCH ĐỀ XUẤT 
Đầu vào: 
- 𝐼 = {𝑏1, 𝑏2, . . . , 𝑏𝑛}, 𝑏𝑖(𝑠𝑖, 𝑒𝑖, 𝑝𝑟𝑖𝑜𝑖), tập 𝑛 chùm đến trong khoảng thời gian mô 
phỏng; 
- 𝑊: Số kênh ra trên mỗi liên kết W={1,2,...,w}; 
- 𝑊𝐿: Số kênh dành riêng cho lớp QoS thấp; 
- 𝑆𝐵𝑘 tập các chùm đã được lập lịch trên kênh thứ k (𝑘 ∈ 𝑊); 
Đầu ra: 
- Tập các chùm được lập lịch lớp QoS thấp (𝐼𝐿); 
- Tập các chùm được lập lịch lớp QoS cao (𝐼𝐻); 
PHƯƠNG PHÁP: 
(Khởi tạo) ∆𝑡 = 0.0001𝑚𝑠; 𝑊𝐿 =
𝑊
2
; 
FOR EACH 𝑏𝑖 ∈ 𝐼 DO 
(Khởi tạo) 𝑠𝑐 = −1; 𝑔𝑎𝑝𝑚𝑖𝑛 = ∞; 
IF (𝑝𝑟𝑖𝑜𝑖 = 0) THEN 
𝑆𝑙𝑐ℎ𝑢𝑚𝑑𝑒𝑛𝐻 = 𝑆𝑙𝑐ℎ𝑢𝑚𝑑𝑒𝑛𝐻 + 1; 
𝑆𝑙𝑔𝑜𝑖𝑑𝑒𝑛𝐻 = 𝑆𝑙𝑔𝑜𝑖𝑑𝑒𝑛𝐻 + (𝑒𝑖 − 𝑠𝑖); 
𝑠𝑐 = 𝐵𝐹𝑉𝐹(𝑏𝑖, 𝑊); 
ELSE 
𝑆𝑙𝑐ℎ𝑢𝑚𝑑𝑒𝑛𝐿 = 𝑆𝑙𝑐ℎ𝑢𝑚𝑑𝑒𝑛𝐿 + 1; 
𝑆𝑙𝑔𝑜𝑖𝑑𝑒𝑛𝐿 = 𝑆𝑙𝑔𝑜𝑖𝑑𝑒𝑛𝐿 + (𝑒𝑖 − 𝑠𝑖); 
𝑠𝑐 = 𝐵𝐹𝑉𝐹(𝑏𝑖, 𝑊𝐿); 
IF (𝑠𝑐 ≠ −1) THEN 
𝑆𝐶𝐻𝐸𝐷𝑈𝐿𝐸(𝑏𝑖, 𝑠𝑐); 
IF (𝑝𝑟𝑖𝑜𝑖 = 0) THEN 
 𝐼𝐿 = 𝐼𝐿 ∪ {𝑏𝑖}; 
ELSE 
 𝐼𝐻 = 𝐼𝐻 ∪ {𝑏𝑖}; 
ENDIF 
IF (𝑡𝑖𝑚𝑒𝑐ℎ𝑜 ≥ ∆𝑡) THEN 
𝐿 =
𝑆𝑙𝑐ℎ𝑢𝑚𝑑𝑒𝑛𝐿
∆𝑡
; 𝐻 =
𝑆𝑙𝑐ℎ𝑢𝑚𝑑𝑒𝑛𝐻
∆𝑡
; 
MỘT GIẢI THUẬT LẬP LỊCH ĐẢM BẢO CHẤT LƯỢNG DỊCH VỤ 139 
𝜇𝐿 =
𝑆𝑙𝑔𝑜𝑖𝑑𝑒𝑛𝐿
𝑆𝑙𝑐ℎ𝑢𝑚𝑑𝑒𝑛𝐿
; 𝜇𝐻 =
𝑆𝑙𝑔𝑜𝑖𝑑𝑒𝑛𝐻
𝑆𝑙𝑐ℎ𝑢𝑚𝑑𝑒𝑛𝐻
; 
𝛾𝐿 =
𝐿
𝜇𝐿×𝑊
; 
𝛾𝐻 =
𝐻
𝜇𝐻×𝑊
; 
𝑊𝐿 = ⌈𝑊 ×
𝛾𝐿
𝛾𝐻+𝛾𝐿
⌉; 
𝑆𝑙𝑐ℎ𝑢𝑚𝑑𝑒𝑛𝐻 = 0; 𝑆𝑙𝑔𝑜𝑖𝑑𝑒𝑛𝐻 = 0; 
𝑆𝑙𝑐ℎ𝑢𝑚𝑑𝑒𝑛𝐿 = 0; 𝑆𝑙𝑔𝑜𝑖𝑑𝑒𝑛𝐿 = 0; 
∆𝑡 = ∆𝑡 + 0.0001𝑚𝑠; 
ENDIF 
ENDFOR 
RETUNR{𝑰𝑳, 𝑰𝑯}; 
FUCNTION BFVF(ub,W): 
INPUT 
- 𝑢𝑏(𝑠𝑢𝑏 , 𝑒𝑢𝑏): chùm đến chưa lập lịch, 
- 𝑊: Số kênh ra trên mỗi liên kết W={1,2,...,w}; 
- 𝑆𝐵𝑘 tập các chùm đã được lập lịch trên kênh thứ k (k ∈ W); 
OUTOUT 
- 𝑠𝑐: kênh tương ứng để lập lịch cho chùm đến. 
PHƯƠNG PHÁP: 
 best_utilisation= ; sc=-1; 
 FOR EACH 𝑘 ∈ 𝑊 DO 
 𝑒0,𝑘 = 0; s|𝑆𝐵𝑘|+1,k =; 
 FOR EACH 𝑗 ∈ |𝑆𝐵𝑘| DO 
 IF(((𝑠𝑢𝑏 ≥ 𝑒𝑗,𝑘) ∧ (𝑠𝑗+1,𝑘 ≥ 𝑒𝑢𝑏)) ∧ ((𝑠𝑗+1,𝑘 − 𝑒𝑗,𝑘) < 𝑏𝑒𝑠𝑡_𝑢𝑡𝑖𝑙𝑖𝑠𝑎𝑡𝑖𝑜𝑛))) 
THEN 
 𝑏𝑒𝑠𝑡_𝑢𝑡𝑖𝑙𝑖𝑠𝑎𝑡𝑖𝑜𝑛 = 𝑠𝑗+1,𝑘 − 𝑒𝑗,𝑘; 
 𝑠𝑐 = 𝑘; 
 ENDIF 
 ENDFOR 
 ENDFOR 
RETURN sc; 
Độ phức tạp giải thuật: O(𝑁 × log(𝑁)), với 𝑁 là số chùm lớn nhất đã được lập lịch 
trên một kênh. 
140 NGUYỄN HỒNG QUỐC và cs. 
3. MÔ PHỎNG PHÂN TÍCH KẾT QUẢ 
Để chứng minh tính hiệu quả của giải thuật đề xuất chúng tôi thực hiện cài đặt mô 
phỏng giải thuật lập lịch đề xuất để so sánh với các giải thuật đã được công bố, bao gồm 
SAC, DAC, LLAC. Môi trường mô phỏng sử dụng gói NS2-obs0.9a [8] và phần mềm 
C++, cài đặt trên máy tính CPU Intel Core i3 CPU 3.6 GHz, 4Gb RAM. 
Mô hình mạng mô phỏng bao gồm 2 nút lõi (𝐶1 và 𝐶2), trong đó mỗi nút lõi kết nối với 5 
nút biên (𝐸𝑖, 𝑖 = 1, . . . , 10) như mô tả ở Hình 1. Giả sử các luồng dữ liệu đến tại các nút 
biên có phân phối Poisson và các chùm sinh ra có kích thước thay đổi. Mỗi liên kết có 16 
kênh dữ liệu và 4 kênh điều khiển. Băng thông của mỗi kênh từ nút biên đến các nút lõi là 
10Gb/s, băng thông giữa 2 nút lõi là 30Gb/s. Mô phỏng được thực hiện với tải lưu lượng 
thay đổi từ 0.1 đến 0.9 trong thời gian 10 giây với khe thời gian dự đoán 100µs. 
Hình 1. Mô hình mạng mô phỏng Dumbell 
Một kết quả thống kê trong 100 khe thời gian dự đoán được thể hiện ở Hình 2a, Hình 2b 
cho thấy khi tải lưu lượng giữa 2 lớp ưu tiên cao và thấp thay đổi giải thuật lập lịch sẽ 
điều chỉnh giá trị 𝑊𝐿 phụ hợp để đáp ứng được tình trạng các chùm đến cho thời điểm 
tiếp theo. 
Hình 2. (a) Tải lưu lượng của lớp ưu tiên và không ưu tiên, (b) số kênh WL tương ứng. 
Qua kết quả mô phỏng được thể hiện ở Hình 3, khi so sánh xác suất mất chùm ưu tiên 
cao của các giải thuật cho thấy, giải thuật đề xuất có xác suất mất chùm thấp nhất điều 
MỘT GIẢI THUẬT LẬP LỊCH ĐẢM BẢO CHẤT LƯỢNG DỊCH VỤ 141 
này cho thấy với cách dự đoán theo tải đến của các chùm trên mỗi lớp sau đó quyết định 
phân phối tài nguyên kênh bước sóng hợp lý tận dụng được tài nguyên tốt hơn và qua 
kết quả này cũng khẳng định giải thuật đề xuất đã giải quyết được vấn đề đảm bảo chất 
lượng dịch vụ tốt nhất cho lớp ưu tiên cao. 
Hình 3. Xác suất mất chùm lớp ưu tiên 
Bên cạnh đó một kết quả được thể hiện ở Hình 4, xác suất mất chùm lớp ưu tiên thấp 
của giải thuật đề xuất giảm so với các giải thuật được công bố trước đó, qua đó cho thấy 
với cách dự đoán dựa trên tải lưu lượng để phân phối tài nguyên kênh bước sóng cho 
mỗi lớp dịch vụ là phù hợp. 
Hình 4. Xác suất mất chùm hai lớp ưu tiên cao và thấp 
142 NGUYỄN HỒNG QUỐC và cs. 
4. KẾT LUẬN 
Bài báo đã đề xuất một giải thuật lập lịch đảm bảo chất lượng dịch vụ với kênh bước 
sóng dành riêng cho chùm ưu tiên thấp thích nghi dựa trên tải lưu lượng đến trong mỗi 
khe thời gian quan sát. Dựa trên các phân tích và kết quả mô phỏng, giải thuật lập lịch 
đề xuất đã thể hiện được các ưu điểm thông qua tỉ lệ mất chùm tổng thể thấp, tỉ lệ mất 
chùm đối với luồng QoS thấp và lượng thông tin cần lưu trữ ít hơn so với các giải thuật 
lập lịch đã công bố và quan trọng nhất có được hiệu quả hơn về tỷ lệ mất chùm ưu tiên 
thấp hơn so với các giải thuật đã công bố trước đây. 
TÀI LIỆU THAM KHẢO 
[1] C. Qiao and M. Yoo (1999). Optical Burst Switching (OBS) - A New Paradigm for an 
Optical Internet, J. High Speed Networks, vol. 8, no. 716, pp. 69–84. 
[2] P. Reviriego, J. A. Hernández, and J. Aracil (2009). Assembly admission control based 
on random packet selection at border nodes in Optical Burst-Switched networks, 
Photonic Netw. Commun., vol. 18, no. 1, pp. 39–48, Aug. 2009. 
[3] Q. Zhang, V. M. Vokkarane, J. P. Jue, and B. Chen (2004). Absolute QoS 
differentiation in optical burst-switched networks, IEEE J. Sel. Areas Commun., vol. 22, 
no. 9, pp. 1781–1795. 
[4] I. M. Moraes and O. C. M. B. Duarte (2010). Using the Network Load for Admission 
Control in OBS Networks: A Multilink Approach, J. Opt. Commun. Netw., vol. 2, no. 3, 
pp. 137–147. 
[5] M. Nandi, A. K. Turuk, D. K. Puthal and S. Dutta (2009). Best Fit Void Filling 
Algorithm in Optical Burst Switching Networks, IEEE Second International 
Conference on Emerging Trends in Engineering and Technology, 609-614. 
[6] Yang, Mei, S. Q. Zheng, and Dominique Verchere (2001). A QoS supporting 
scheduling algorithm for optical burst switching DWDM networks. Global 
Telecommunications Conference, 2001. GLOBECOM'01. IEEE. Vol. 1. IEEE. 
[7] Garg, Amit Kumar (2012). A novel hybrid approach for efficient network utilization of 
OBS. International Journal of Software Engineering and Its Applications 6.1 (2012): 
47-60. 
[8] Pham Trung Duc, Vo Viet Minh Nhat, https://www.isi.edu/nsnam/ns/. 
Title: A SCHEDULING ALGORITHM ASSURANCE QUALITY SERVICE 
 IN OPTICAL BURST SWITCHING NETWORKS 
Abstract: Optical burst switching (OBS) is considered as a promising technology for the next 
generation of optical Internet and ensure the quality of service for the next generation optical 
Internet. However, due to the lack of optical buffers at the core switches, it is more difficult to 
secure the quality of service for different services in a Optical Burst Switching Networks than 
traditional electronic networks. There are already a number of scheduling algorithms available 
to address this problem, but scheduling algorithms ensure quality of service for priority and 
non-priority clusters through fixed the wavelength channel out without considering the 
MỘT GIẢI THUẬT LẬP LỊCH ĐẢM BẢO CHẤT LƯỢNG DỊCH VỤ 143 
incoming traffic of the service layer. In this study, we propose a scheduling algorithm with 
predictive method based on incoming load traffic of clusters to allocate reasonable wavelength 
resources for priority classes in the OBS network. Analyzing and evaluating the effectiveness of 
simulation based scheduling algorithms will confirm the advantages of this proposed model. 
Keywords: OBS networks, scheduling algorithm, service differentiation, resource allocation, 
load traffic prediction.