Nâng cao hiệu năng lập lịch của nút lõi OBS dựa trên phân tích dữ liệu và sử dụng đường trễ FDL

ng tầm quan trọng của các thuộc tính trên cơ 
sở khả năng dự đoán của các thuộc tính và mức độ dư 
thừa của nó. Các tập con (subset) có ít giao thoa nhưng 
tương quan cao với lớp mục tiêu là được ưu tiên. Xếp 
hạng của 3 thuộc tính đầu tiên bao gồm: 1. burst_time, 2. 
burst_length, 3. void_start. Hình 6 chỉ ra thứ hạng các 
thuộc tính được tìm thấy bởi phương pháp CSE. 
Hình 5. Phân bố các lớp head_overlap, LAUT_overlap và 
tail_overlap trong dữ liệu lập lịch không thành công 
CA đánh giá các thuộc tính liên quan đến lớp đích. 
Phương pháp tương quan Pearson được sử dụng để đo 
mối tương quan giữa từng thuộc tính và thuộc tính lớp 
đích. Nó xem xét các thuộc tính trên cơ sở giá trị và mỗi 
giá trị đóng vai trò như một chỉ báo. Bằng cách kết hợp 
cách đánh giá thuộc tính này với phương pháp xếp hạng 
(Ranker) tìm kiếm, xếp hạng của ba thuộc tính đầu tiên 
bao gồm: 1. burst_length, 2. burst_time, 3. LAUT. Hình 7 
chỉ ra thứ hạng các thuộc tính được tìm thấy bởi phương 
pháp CA. 
Hình 6. Kết quả xếp hạng các thuộc tính với CSE 
Hình 7. Kết quả xếp hạng các thuộc tính với CA 
Kết quả phân tích dữ liệu lập lịch trong Hình 5 cho 
thấy rằng chồng lấp đầu (head_overlap) và chồng lấp 
LAUT (LAUT_overlap) là nguyên nhân chính gây nên 
mất chùm (chiếm hơn 90%), trong đó hai thuộc tính thời 
gian đến (burst_time) và độ dài chùm (burst_length) có 
tác động chính đến việc lập lịch không thành công (Hình 
6 và 7). Đây chính là cơ sở của đề xuất sau đây nhằm 
nâng cao hiệu năng lập lịch theo nghĩa tăng tỉ lệ lập lịch 
thành công, giảm mất mát dữ liệu và tăng mức sử dụng 
băng thông tại nút lõi. 
IV NÂNG CAO HIỆU QUẢ LẬP LỊCH DỰA TRÊN 
FDL 
IV.1 Xử lý tranh chấp tài nguyên tại nút lõi 
Khi một chùm đến không thể lập lịch được, các giải 
pháp xử lý có thể gồm: chuyển đổi bước sóng [10] sử 
dụng đường trễ FDL (fiber delay link) [11] hay định tuyến 
lệch hướng đối với chùm tranh chấp [12]. Chuyển đổi 
bước sóng là hoạt động chuyển đổi bước sóng của chùm 
đến sang một bước sóng mới của một kênh ra khả dụng có 
thể lập lịch được chùm này. Trong mô hình mạng OBS 
được xem xét trong bài báo này, chuyển đổi bước sóng 
được giả thuyết là đầy đủ, nên phương pháp này không 
cần xem xét nữa. Định tuyến lệch hướng là định tuyến lại 
chùm tranh chấp ra một cổng ra mới (so với cổng ra dự 
kiến ban đầu) và di chuyển trên một hành trình mới để 
NÂNG CAO HIỆU NĂNG LẬP LỊCH CỦA NÚT LÕI OBS DỰA TRÊN PHÂN TÍCH DỮ LIỆU . 
đến đích. Phương pháp định tuyến lệch hướng là ít tốn 
kém (vì không cần trang cấp thêm thiết bị) nhưng đòi hỏi 
các tính toán phức tạp và làm tăng xác suất tắc nghẽn do 
phát sinh các tuyến mới ngoài dự kiến, đặc biệt khi khi tải 
mạng cao. Giải pháp đường trễ FDL được chúng tôi lựa 
chọn bởi vì dễ cài đặt và phù hợp với mục tiêu là làm trễ 
thời gian đến của chùm nhằm tăng cơ hội lập lịch thành 
công cho nó. 
IV.2 Mô hình điều khiển lập lịch dựa trên FDL 
Dựa trên kết quả phân tích ở Mục III.3, đa số các 
trường hợp lập lịch không thành công là do chồng lấp đầu 
hay chồng lấp LAUT. Thêm vào đó, thuộc tính có tác 
động chính đến việc lập lịch không thành công này là độ 
dài chùm (burst_length) và thời gian đến của chùm 
(burst_time). Tại nút lõi, việc thay đổi độ dài chùm chỉ có 
thể được thực hiện bằng cách phân đoạn chùm [13], theo 
đó phần chồng lấp của chùm tranh chấp sẽ bị loại bỏ và 
một yêu cầu truyền lại phần này sẽ được gửi trở lại nút 
nguồn. Tuy nhiên phương pháp phân đoạn chùm yêu cầu 
nhiều xử lý phức tạp hơn và gây lãng phí băng thông do 
gói điều khiển đặt trước tài nguyên luôn nhiều hơn so với 
nhu cầu băng thông cần sử dụng; thứ tự dữ liệu đến nút 
biên ra là không được đảm bảo. Bài viết này không xem 
xét đến việc thay đổi độ dài chùm mà chỉ tập trung vào 
làm trễ thời gian đến của chùm tại cổng ra. Như mô tả ở 
Hình 8, nếu thời gian đến được làm trễ một khoảng vừa 
đủ t, việc lập lịch sẽ thành công. 
chùm j chùm j+1
chùm k
thời gian(a)
chùm j chùm j+1
chùm k
thời gian(b)
sub
chùm k
chùm k
 t
chùm k
chùm k
 t 
Hình 8. Chồng lấp LAUT (a) hay chồng lấp đầu (b) đều 
có thể được khắc phục nhờ thay đổi thời gian chùm đến 
Có 2 kiến trúc đường trễ FDL đã được đề xuất trong 
mạng OBS [14]: truyền thẳng (feed-forward) hay hồi quy 
(feed-back). Cụ thể, như mô tả trong Hình 9a các FDL 
được đặt tại các cổng ra và chỉ được sử dụng bởi các 
chùm đến cổng ra đó, trong khi các FDL hồi quy được đặt 
tại nút lõi và các chùm đến trên cổng vào bất kỳ đều có 
thể sử dụng nếu chúng khả dụng (Hình 9b). Trong bài báo 
này, chúng tôi sử dụng kiểu đường trễ truyền thẳng do 
tính đơn giản về cài đặt và điều khiển của chúng [14]. 
 (a) FDL truyền thẳng (b) FDL hồi quy 
Hình 9. Hai mô hình đường trễ chính trong mạng OBS 
Việc điều khiển lập lịch dựa trên đường trễ FDL được 
đề xuất như trong Hình 10, trong đó khi một chùm đến 
không thể lập lịch được, việc kiểm tra chồng lấp đầu và 
chồng lấp LAUT sẽ được xem xét (phần hình chữ nhật nét 
đứt). Nếu có chồng lấp đầu hay chồng lấp LAUT, chùm 
sẽ được đưa vào đường trễ để làm thay đổi (làm trễ) thời 
gian đến của nó. Trong trường hợp chồng lấp đuôi, chùm 
sẽ bị loại bỏ (dropped). 
Chùm đến
Lập lịch trên một 
trong W kênh ra
Lập lịch 
chùm đến
Nếu lập lịch 
thành công
no
yes
FDL
Đánh rơi 
chùm
Nếu chông
 lấp đầu hoặc LAUT
Độ trễ chùm >
 độ trễ đường trễ
yes
no
yes
no
Mô đun bổ sung
Hình 10. Mô hình điều khiển lập lịch tại nút lõi OBS 
Độ dài đường trễ FDL cũng có những tác động đáng kể 
đến kích thước của nút chuyển mạch và tăng thêm độ trễ 
cho các chùm. Độ dài đường trễ cần được trang bị phụ 
thuộc vào thời gian cần làm trễ cho các chùm, mà cụ thể ở 
đây là t của khoảng chồng lấp đầu hay chồng lấp LAUT. 
Tuy nhiên, đường trễ cũng cần phải đủ dài để chứa trọn 
vẹn một chùm có kích thước lớn nhất; đó cũng chính là 
ngưỡng độ dài tập hợp chùm trong mạng OBS được xem 
xét. Các đường trễ được sử dụng trong bài viết này có độ 
dài bằng ngưỡng độ dài tập hợp chùm. 
V. MÔ PHỎNG VÀ PHÂN TÍCH KẾT QUẢ 
Với các tham số cài đặt như trong Mục III.2, chúng tôi 
tiến hành mô phỏng để so sánh tỉ lệ mất chùm (được tính 
bằng số chùm bị loại bỏ / tổng số chùm đến tại cổng ra) 
của 3 trường hợp: không sử dụng đường trễ và có sử dụng 
đường trễ với giá trị đường trễ lần lượt là 1 và 1,5 lần 
Phạm Trung Đức, Võ Viết Minh Nhật, Đặng Thanh Chương 
ngưỡng độ dài tập hợp chùm. Chúng tôi chỉ cài đặt trường 
hợp làm trễ 1 lần với FDL đối với các chùm không thành 
công ở lần lập lịch đầu tiên. 
V.1 Phân tích tỉ lệ mất chùm khi sử dụng FDL 
Chúng tôi tiến hành so sánh tỉ lệ mất chùm trong 3 
trường hợp không sử dụng đường trễ (No_FDL), sử dụng 
đường trễ với giá trị đường trễ là ngưỡng độ dài tập hợp 
chùm (FDL (100 µs)) và bằng 1,5 lần ngưỡng độ dài tập 
hợp chùm (FDL (150 µs)). 
Hình 11 cho thấy rằng việc sử dụng đường trễ FDL cho 
tỉ lệ mất chùm trong khoảng tải chuẩn hóa từ 0.1 đến 0.6 
giảm nhiều nhất khoảng 60% so với không sử dụng 
đường trễ. Nhưng khi tải tăng từ 0.7 đến 0.9 thì tỉ lệ mất 
giảm rất ít (khoảng 4%). Điều này là do khi tải cao, với số 
lượng chùm đến nhiều thì các chùm bị làm trễ tiếp tục bị 
chồng lấp với các chùm đã được lập lịch trước đó, nên bị 
loại bỏ. 
Hình 11. So sánh tỉ lệ mất chùm khi có và không sử dụng 
đường trễ FDL 
FDL với độ trễ 100 µs cho tỉ lệ mất chùm thấp hơn so 
FDL với độ trễ 150 µs. Nguyên nhân là do khi tăng độ dài 
đường trễ thì các trường hợp chồng lấp LAUT (như được 
chỉ ra ở Hình 8a) sẽ không bị tác động, nhưng các trường 
hợp chồng lấp đầu (như được chỉ ra ở Hình 8b) sẽ có có 
khả năng trở thành chồng lấp đuôi với chùm đã được lập 
lịch trước đó. Trong trường hợp này, chùm tiếp tục bị loại 
bỏ. Do đó việc chọn độ dài đường trễ phù hợp sẽ có ảnh 
hưởng đáng kể đến hiệu quả lập lịch. 
V.2 Phân tích độ trễ khi sử dụng FDL 
Như thể hiện trong Hình 12 tỉ lệ độ trễ trung bình của 
các chùm tăng thêm khi sử dụng đường trễ FDL. Chúng 
ta nhận thấy rằng khi độ dài FDL càng lớn thì độ trễ trung 
bình càng cao hơn. Cụ thể ở đây là khi sử dụng FDL với 
độ trễ 150µs thì độ trễ chùm tăng thêm trung bình khoảng 
21% so với gần 16% khi sử dụng FDL với độ trễ 100 µs. 
Hình 12 cũng cho chúng ta thấy rằng khi tải cao thì độ 
tăng thêm do sử dụng đường trễ cũng tăng cao. Điều này 
là do khi tải cao thì sẽ có nhiều chùm không thành công 
trong lần lập lịch đầu nên phải sử dụng đường trễ để thử 
lại lập lịch ở lần tiếp theo; kết quả là tỉ lệ độ trễ trung bình 
của các chùm tăng lên. 
Hình 12. Tỉ lệ phần trăm độ trễ trung bình tăng thêm khi 
sử dụng đường trễ FDL 
Tóm lại, việc sử dụng đường trễ đối với trường hợp 
chồng lấp đầu và chồng lấp LAUT rõ ràng đã mang lại 
hiệu quả về giảm tỉ lệ mất chùm như được chỉ ra ở Hình 
11. Tuy nhiên việc sử dụng đường trễ FDL cũng làm gia 
tăng độ trễ tăng thêm cho các chùm không thành công ở 
lần lập lịch đầu tiên. Việc sử dụng đường trễ FDL trong 
trường hợp tải cao thì sẽ làm tăng thêm độ trễ lớn nhưng 
không làm giảm đáng kể tỉ lệ mất chùm. Do đó, việc sử 
dụng đường trễ chỉ phù hợp ở các mức tải thấp, mà cụ thể 
nên dưới mức tải chuẩn hóa 0.6. 
VI KẾT LUẬN 
Bài báo đã đề xuất một hướng tiếp cận phân tích 
nguyên nhân mất chùm dựa trên dữ liệu trạng thái lập 
lịch. Để làm được điều này, chúng tôi đã mô phỏng và 
trích xuất dữ liệu trạng thái lập lịch tại các nút lõi của một 
mạng OBS với hình thái mạng NSFNET. Dữ liệu trạng 
thái lập lịch sau đó được phân tích bằng ứng dụng Weka. 
Kết quả phân tích cho thấy rằng chồng lấp đầu và chồng 
lấp LAUT là các nguyên nhân chính gây nên mất chùm. 
Từ đó, chúng tôi đề xuất giải pháp sử dụng đường trễ 
FDL để thay đổi thời gian đến của chùm không thể lập 
lịch được trong lần đầu tiên. Kết quả mô phỏng đã chỉ ra 
rằng đường trễ FDL đã giúp giảm tỉ lệ mất chùm, nhưng 
làm tăng độ trễ trung bình của chùm. Kết quả mô phỏng 
cũng khuyến cáo rằng việc làm trễ bằng FDL chỉ phù hợp 
với tải mạng chuẩn hóa trong khoảng [0.1, 0.6]. Khi tải 
mạng cao, việc làm trễ bằng FDL chỉ làm tăng thêm tắc 
nghẽn. 
VII. TÀI LIỆU THAM KHẢO 
[1] S. J. B. Yoo, “Optical packet and burst switching 
technologies for the future photonic internet,” J. Light. 
Technol., vol. 24, no. 12, pp. 4468–4492, 2006, doi: 
10.1109/JLT.2006.886060. 
[2] A. Zalesky, “To burst or circuit switch?,” IEEE/ACM 
Trans. Netw., vol. 17, no. 1, pp. 305–318, 2009, doi: 
10.1109/TNET.2008.923718. 
[3] N. H. Q. Vo Viet Minh Nhat, “Phân tích hiệu quả các giải 
thuật lập lịch trên mạng chuyển mạch chùm quang,” Tạp 
chí khoa học, Đại học Huế, vol. 74A, no. 5, pp. 85–97, 
2012. 
[4] https://www.cs.waikato.ac.nz/ml/weka/ 
[5] J. S. Turner, “Terabit burst switching,” J. High Speed 
Networks, vol. 8, no. 1, pp. 3–16, 1999, doi: 
10.7936/K7FJ2F2T. 
[6] J. Xu, C. Qiao, J. Li, and G. Xu, “Efficient channel 
NÂNG CAO HIỆU NĂNG LẬP LỊCH CỦA NÚT LÕI OBS DỰA TRÊN PHÂN TÍCH DỮ LIỆU . 
scheduling algorithms in optical burst switched networks,” 
in IEEE INFOCOM 2003. Twenty-second Annual Joint 
Conference of the IEEE Computer and Communications 
Societies (IEEE Cat. No.03CH37428), 2003, vol. 3, pp. 
2268–2278, doi: 10.1109/INFCOM.2003.1209247. 
[7] M. Iizuka, M. Sakuta, Y. Nishino, and I. Sasase, “A 
scheduling algorithm minimizing voids generated by 
arriving bursts in optical burst switched WDM network,” 
in Global Telecommunications Conference, 2002. 
GLOBECOM ’02. IEEE, 2002, vol. 3, no. May, pp. 2736–
2740, doi: 10.1109/GLOCOM.2002.1189127. 
[8] M. Nandi, A. K. Turuk, D. K. Puthal, and S. Dutta, “Best 
Fit Void Filling Algorithm in Optical Burst Switching 
Networks,” in 2009 Second International Conference on 
Emerging Trends in Engineering & Technology, 2009, pp. 
609–614, doi: 10.1109/ICETET.2009.46. 
[9] https://www.isi.edu/nsnam/ns/. 
[10] F. Z. Khan, M. F. Hayat, T. Holynski, and M. J. Khan, 
“Towards dynamic wavelength grouping for QoS in 
optical burst-switched networks,” in 2017 40th 
International Conference on Telecommunications and 
Signal Processing (TSP), Jul. 2017, pp. 79–85, doi: 
10.1109/TSP.2017.8075941. 
[11] Y. Lee, “Dynamic burst length controlling algorithm-
based loss differentiation in OBS networks through shared 
FDL buffers,” Photonic Netw. Commun., vol. 31, no. 1, 
pp. 36–47, Feb. 2016, doi: 10.1007/s11107-015-0527-x. 
 [12] P. Khumalo, B. Nleya, and A. Mutsvangwa, “A 
controllable deflection routing and wavelength assignment 
algorithm in OBS networks,” J. Opt., vol. 48, no. 4, pp. 
539–548, 2019, doi: 10.1007/s12596-019-00578-2. 
[13] V. M. Vokkarane and J. P. Jue, “Segmentation-based 
nonpreemptive channel scheduling algorithms for optical 
burst-switched networks,” J. Light. Technol., vol. 23, no. 
10, pp. 3125–3137, Oct. 2005, doi: 
10.1109/JLT.2005.856265. 
 [14] C. McArdle, D. Tafani, and L. P. Barry, “Analysis of a 
buffered optical switch with general interarrival times,” J. 
Networks, vol. 6, no. 4, pp. 536–548, 2011, doi: 
10.4304/jnw.6.4.536-548. 
IMPROVING THE SCHEDULING 
PERFORMANCE OF CORE OBS NODES BASED 
ON DATA ANALYSIS AND USING FDL 
Abstract: The scheduling performance of the core node 
plays an important role in the overall communication 
performance of OBS networks. In order to improve the 
scheduling performance of the core node, many studies 
have been carried out combining scheduling techniques 
with wavelength conversion, deflection routing or using 
FDL. The scheduling performance at an output of a core 
node depends on many factors, including the arrival time 
of burst, the start and end time of voids and the latest 
available unscheduled time (LAUT) of each channel. It is 
the factors that have a major influence on scheduling 
performance. This paper therefore proposes a method for 
analyzing scheduling data to find the cause of scheduling 
failure. Based on the results of the analysis, the article 
shows that using FDL to avoid head- and LAUT overlaps 
is the most appropriate solution to increase the success 
scheduling rate, reduce the burst loss and thus increase 
the efficient use of bandwidth in OBS networks. 
Phạm Trung Đức nhận học vị Thạc 
sĩ Khoa học Máy tính tại Đại học 
Khoa học, Đại học Huế năm 2012; 
Hiện đang là nghiên cứu sinh tại Đại 
học Khoa học, Đại học Huế. 
Các lĩnh vực nghiên cứu: Mạng 
OBS, QoS trong mạng OBS, điều 
khiển chấp nhận lập lịch. 
Email: phamtrungduc@hueuni.edu.vn 
Võ Viết Minh Nhật nhận học hàm 
Phó Giáo sư năm 2016, học vị Tiến 
sỹ năm 2007 tại đại học UQAM, 
Canada; Hiện công tác tại ĐH Huế. 
Lĩnh vực nghiên cứu gồm: Mạng 
OBS, mạng cảm biến tích hợp RFID, 
tính toán mềm (mạng nơ ron nhân 
tạo, giải thuật tiến hóa, di truyền). 
Email: vvmnhat@hueuni.edu.vn 
Đặng Thanh Chương nhận học vị 
tiến sĩ về Đảm bảo toán học cho máy 
tính năm 2014 tại Viện Công nghệ 
thông tin, Viện HL KH&CN VN. 
Lĩnh vực nghiên cứu gồm: mạng 
OBS, lý thuyết hàng đợi 
Email: dtchuong@hueuni.edu.vn