Kỹ thuật phân đoạn chùm trong mạng chuyển mạch chùm quang

ì rơi toàn bộ chùm thì ch có những phân đoạn 
chồng lấp mới bị đánh rơi, như thể hiện trong Hình 2. 
 (a) Đánh rơi phần đầu (b) Đánh rơi phần đuôi 
 Hình 2. Hai cách tiếp cận đánh rơi của phân đoạn chùm 
 Một vấn đề trong phân đoạn chùm là việc lựa chọn phương án đánh rơi các phân đoạn chồng lấp khi có tranh 
chấp xảy ra giữa hai chùm. Có hai cách tiếp cận đối với phương án đánh rơi, gồm: 
 . Đánh rơi phần ầu, trong đó các phân đoạn đầu của chùm bị tranh ch p bị đánh rơi (Hình 2.a). 
 . Đánh rơi phần uôi, trong đó phân đoạn đuôi của chùm ến (Hình 2.b) bị đánh rơi. 
 Ưu điểm của ánh rơi phần uôi so với ánh rơi phần ầu của phân đoạn chùm là không làm thay đổi trật tự 
các các gói tin tại đích đến, giả định rằng các gói tin được truyền lại sau một thời gian [6]. 
 Ngoài ra, để tăng tính hiệu quả của phương pháp phân đoạn trong việc giảm thiểu xác xuất mất chùm, phân 
đoạn chùm có thể được kết hợp với một số giải pháp khác như: phân đoạn kết hợp với lập lịch chùm [1][8], phân đoạn 
kết hợp với FDL, phân đoạn kết hợp với định tuyến lệch hướng và phân đoạn kết hợp với lập lịch lại. 
B. Các kỹ thuật phân đoạn kết hợp 
1. Phân đoạn kết hợp lập lịch 
 Phần này sẽ tập trung vào các giải thuật phân đoạn kết hợp với lập lịch, theo đó sẽ ưu tiên cho việc lập lịch 
trước, nếu không tìm thấy kênh khả dùng thì sẽ tiếp tục thực hiện phương án phân đoạn, điều này sẽ cho ph p làm giảm 
t lệ mất gói tin tốt hơn so với giải thuật lập lịch. 
a) Giải thuật NPMOC 
 Ý tưởng của giải thuật NPMOC là kết hợp giải thuật LAUC và phân đoạn chùm. Giải thuật NPMOC dựa vào 
giá trị LAUT trên mỗi kênh dữ liệu. Khi không tìm thấy kênh nào khả dụng để lập lịch cho chùm thì giải thuật lập lịch 
NPMOC xem x t tất cả các kênh dữ liệu ra và tìm kiếm kênh có khoảng chồng lấp nhỏ nhất để tiến hành phân đoạn và 
lập lịch cho chùm chưa lập lịch. Khoảng chồng lấp được tính bằng Overlap = LAUTi - Tub. Như mô tả ở Hình 3, với 
một chùm mới đến và trạng thái các chùm đã được lập lịch trên 4 kênh, thì giải thuật lập lịch NPMOC sẽ tiến hành 
phân đoạn và lập lịch cho chùm mới (chưa được lập lịch) trên kênh D1 sau khi đã c t bỏ phần chồng lấp nhỏ nhất. 
 Hình 3. Minh họa thuật toán lập lịch NPMOC 
268 KỸ THUẬT PHÂN ĐOẠN CHÙM TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG 
 Giải thuật NPMOC có thể được xây dựng lại dựa theo ý tưởng đã được mô tả trong [6] như sau: 
 Function NPMOC(Tub, Lb, W) 
 Input: Tub, Lb, W 
 Output: selectedChannel, Tub1, Lb1 
 Process 
 1 minOverlap  
 2 selectedChannel  -1 
 3 selectedChannel  LAUC(Tub, Lb, W) 
 4 if (selectedChannel -1) then 
 5 return selectedChannel, Tub, Lb 
 6 for each (i W) 
 7 if (Tub < LAUTi) then 
 8 Overlapi  LAUTi - Tub 
 9 if (Overlapi < minOverlap) then 
 10 minOverlap  Overlapi 
 11 selectedChannel  i 
 12 end if 
 13 end if 
 14 end for 
 15 if (selectedChannel -1) then 
 16 Tub1  Tub + minOverlap 
 17 Lb1  Lb – minOverlap 
 18 return selectedChannel, Tub1, Lb1 
 19 end if 
 20 return selectedChannel, T , L 
 ub b
b) Giải thuật NPMOC-VF 
 Ý tưởng giải thuật NPMOC-VF là là kết hợp giải thuật LAUC-VF với phân đoạn chùm và cũng là giải thuật 
cải tiến của giải thuật NPMOC. Giải thuật kết hợp NPMOC-VF tiến hành tìm kiếm các kênh khả dụng. Khi không tìm 
thấy kênh nào khả dụng để lập lịch cho chùm chưa lập lịch (với giải thuật LAUC-VF) thì giải thuật NPMOC-VF ưu 
tiên xem x t tất cả các kênh dữ liệu ra trên nhóm lấp đầy khoảng trống trước và tìm kiếm kênh có khoảng chồng lấp 
nhỏ nhất để tiến hành phân đoạn và lập lịch cho chùm chưa lập lịch. Giải thuật NPMOC-VF được xếp vào nhóm lập 
lịch lấp đầy khoảng trống. Trong giải thuật NPMOC-VF, ta chia ra nhiều phương án đánh rơi chùm bị chồng lấp như: 
đánh rơi phần đầu, đánh rơi phần đuôi, đánh rơi cùng lúc cả phần đầu và phần đuôi[3][6]. 
 Tương tự như NPMOC, giải thuật NPMOC-VF cũng có thể được xây dựng dựa theo [6] như sau: 
 Function NPMOC-VF(Tub, Lb, W) 
 Input: Tub, Lb, W 
 Output: selectedChannel, Tub1, Lb1 
 Process 
 1 minOverlap  
 2 selectedChannel  -1 
 3 selectedChannel LAUC-VF(Tub, Lb, W) 
 4 if (selectedChannel-1) then //trường hợp không phân đoạn 
 5 return selectedChannel, Tub, Lb 
 6 for each (i W) 
 7 if ((Tub < Ei,0) and (Tub+Lb) < Si,1) then //Đánh rơi đoạn đầu 
 8 Overlapi  Tub – Ei,0 
 9 if (Overlapi < minOverlap) then 
 10 minOverlap  Overlapi 
 11 selectedChannel  i 
 12 end if 
 13 end if 
 14 end for 
 15 if (selectedChannel -1) then //Cập nhật lại thông tin chùm mới 
 16 Tub1 = Tub + minOverlap 
 17 Lb1 = Lb - minOverlap 
 18 return selectedChannel, Tub1, Lb1 
 19 end if 
 20 for each (i W) 
 21 if (Tub > Ei,0) and ((Tub+Lb)>Si,1) then //Đánh rơi đoạn đuôi 
 22 Overlapi  Tub + Lb - Si,1 
 23 if (Overlapi < minOverlap) then 
Mai Hoàng Thiên, Đặng Thanh Chương 269 
 24 minOverlap  Overlapi 
 25 selectedChannel  i 
 26 end if 
 27 end if 
 28 end for 
 29 if (selectedChannel -1) then //Cập nhật lại thông tin chùm mới 
 30 Tub1  Tub 
 31 Lb1  Lb - Tub 
 32 return selectedChannel, Tub1, Lb1 
 33 end if 
 34 for each (i W) 
 35 if ((Tub Si,1) then //Đánh rơi đoạn đầu và đuôi 
 36 Overlapi  (Ei,0 – Tub) + ((Tub+Lb)-Si,1) 
 37 if (Overlapi < minOverlap) then 
 38 minOverlap  Overlapi 
 39 selectedChannel  i 
 40 end if 
 41 end for 
 42 if (selectedChannel -1) then //Cập nhật thông tin chùm 
 43 Tub1 = sselectedChannel 
 44 Lb1 = Lb - minOverlap 
 45 return selectedChannel, Tub1, Lb1 
 46 end if 
 47 for each (i W)//Kiểm tra trường hợp không lấp đầy khoảng trống 
 48 if (Tub < LAUTi) then 
 49 Overlapi  LAUTi - Tub 
 50 if (Overlapi < minOverlap) then //chọn kênh chồng lấp 
 nhỏ nhất 
 51 minOverlap  Overlapi 
 52 selectedChannel  i 
 53 end if 
 54 end if 
 55 end for 
 56 if (selectedChannel -1) then //Cập nhật lại thông tin chùm 
 57 Tub1  Tub + minOverlap 
 58 Lb1  Lb – minOverlap 
 59 return selectedChannel, Tub1, Lb1 
 60 end if 
 61 return selectedChannel, T , L 
 ub b
 (a) NPMOC-VF với đánh rơi phần đầu 
270 KỸ THUẬT PHÂN ĐOẠN CHÙM TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG 
 (b) NPMOC-VF với đánh rơi phần đuôi 
 (c) NPMOC-VF với đánh rơi cùng lúc phần đầu và phần đuôi 
 Hình 4. Minh họa thuật toán lập lịch không ưu tiên NPMOC-VF 
 Áp dụng giải thuật NPMOC-VF ở ví dụ Hình 4.a, chúng ta nhận thấy rằng, kênh dữ liệu D0 có sự chồng lấp 
nhỏ nhất và chùm chưa lập lịch được lập lịch trên D0. Ở đây, ch các đoạn chồng lấp của chùm không lập lịch bị loại 
bỏ thay vì toàn bộ các chùm chưa lập lịch như trong trường hợp của LAUC-VF. Độ phức tạp của thuật toán NPMOC-
VF là O(log(W Nb)). Ngoài ra, ở các trường hợp như Hình 4.b và Hình 4.c chúng ta cũng xem x t tương tự. 
2. Phân đoạn kết hợp với đường trễ FDL 
 Việc sử dụng FDLs trong mạng quang đã mang lại những cải tiến quan trọng [3][9]. Trong phần này, chúng 
tôi mô tả một số thuật toán lập lịch không thứ tự ưu tiên dựa trên phân đoạn kết hợp FDL, gồm: 
 . Các thuật toán lập lịch độ trễ đầu tiên: Thuật toán NP-DFMOC và NP-DFMOC-VF chính là sự cải tiến của 
 thuật toán LAUC và LAUC-VF kết hợp với FDL và phân đoạn chùm để giải quyết những chùm tại nơi xảy ra 
 tranh chấp. 
 . Các thuật toán lập lịch đoạn đầu tiên: Thuật toán NP-SFMOC và NP-SFMOC-VF thực chất là cải tiến của 
 giải thuật LAUC, LAUC-VF kết hợp với phân đoạn chùm và FDL để truyền lại phân đoạn bị đánh rơi. 
a) Giải thuật NP-DFMOC 
 Ý tưởng của giải thuật NP-DFMOC là kết hợp giải thuật lập lịch LAUC với phân đoạn chùm (dựa trên khoảng 
chồng lấp nhỏ nhất) và đường trễ FDL (dựa trên thời gian MAX_DELAY) để lập lịch cho chùm chưa lập lịch [9]. 
 Hình 5. Minh họa giải thuật NP-DFMOC 
Mai Hoàng Thiên, Đặng Thanh Chương 271 
 Ví dụ ở Hình 5, dữ liệu kênh D1 có khoảng chồng lấp nhỏ nhất và thỏa mãn MAX_DELAY vì thế chùm chưa 
lập lịch được làm trễ và lập lịch trên kênh D1. 
b) Giải thuật NP-DFMOC-VF 
 Giải thuật NP-DFMOC-VF là sự cải tiến giải thuật NP-DFMOC, kh c phục nhược điểm của giải thuật 
NP-DFMOC với việc tận dụng các khoảng trống trên kênh lập lịch. 
 Hình 6. Minh họa giải thuật NP-DFMOC-VF 
 Ví dụ Hình 6, áp dụng thuật toán NP-DFMOC-VF, ta thấy ở kênh D1 có khoảng chồng lấp nhỏ nhất và thỏa 
mãn MAX_DELAY vì thế chùm chưa lập lịch được làm trễ và lập lịch trên kênh D1. 
 III. M PH NG, PHÂN T CH V M H NH MINH H A 
 Những mô phỏng được trình bày trong bài viết được thực hiện trên máy tính với CPU Intel Core 2 CPU 2.4 
Ghz, 2G bộ nhớ RAM. Kết quả mô phỏng dựa trên gói mô phỏng trên phần mềm mô phỏng NS2-OBS0.9a [11][12] và 
kết hợp với phần mềm Microsoft Excel 2013 để phân tích kết quả. 
 Mô phỏng tập trung trên các giải thuật lập lịch đã được đề xuất cho mạng chuyển mạch chùm quang. Topo 
của mạng chuyển mạch chùm quang thực hiện mô phỏng là một mạng dumbbell được tạo thành từ 2 nút lõi (Ci, i=1,2), 
mỗi nút lõi kết nối với 18 nút biên như mô tả ở Hình 7, các luồng dữ liệu đến theo phân phối Poisson. Các chùm do đó 
được sinh ra tại các thời điểm thay đổi và cũng như có kích thước thay đổi. Có 4 kênh dữ liệu và 2 kênh điều khiển trên 
mỗi liên kết. Băng thông trên mỗi kênh là 10Gb/s. Lưu lượng dữ liệu đến tại một nút có phân bố Poisson với mật độ từ 
0.1 đến 0.9 Erlang. 
 Hình 7. Mô hình mạng mô phỏng 
 Chúng ta sẽ đánh giá các giải thuật lập lịch kết hợp phân đoạn chùm dựa trên xác xuất rơi gói tin theo mô hình 
mạng mô phỏng ở Hình 7. 
272 KỸ THUẬT PHÂN ĐOẠN CHÙM TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG 
 Xác xuất rơi gói Xác gói xuấttin rơi 
 Tải (Erlang) 
 Hình 8. So sánh xác xuất rơi gói tin trên toàn mạng đối với 2 giải thuật LAUC và NPMOC 
 Ở kết quả mô phỏng Hình 8 ch ra rằng các giải thuật lập lịch kết hợp phân đoạn NPMOC hiệu quả hơn 
LAUC, thể hiện ở việc xác xuất rơi gói tin ít hơn. Vì như đã trình bày ở phần 2, giải thuật NPMOC giảm thiểu được t 
lệ mất chùm trên kênh dữ liệu tốt hơn giải thuật LAUC vì giải thuật NPMOC ch đánh rơi các phân đoạn bị chồng lấp 
thay vì đánh rơi toàn bộ chùm như giải thuật LAUC. 
 Xác xuất rơi gói Xác gói xuấttin rơi 
 Tải (Erla ng) 
 Hình 9. So sánh xác xuất rơi gói tin trên toàn mạng với 2 giải thuật LAUC-VF và NPMOC-VF.HEAD 
 Trong kết quả mô phỏng Hình 9 đã ch ra rằng giải thuật lập lịch NPMOC-VF.HEAD hiệu quả hơn giải thuật 
LAUC-VF thể hiện ở việc xác xuất rơi gói tin ít hơn giải thuật LAUC-VF. 
 Xác xuất rơi gói Xác gói xuấttin rơi 
 Tải (Erlang) 
 Hình 10. So sánh xác xuất rơi gói tin trên toàn mạng với các giải thuật NPMOC-VF, 
 NPMOC-VF.HEAD, NPMOC-VF.TAIL, NPMOC-VF.HEAD_TAIL 
 Dựa vào kết quả mô phỏng ở Hình 10, ta có thể thấy rằng, trong các phương án đánh rơi thì phương án đánh 
rơi các phân đoạn bị chồng lấp ở đoạn đuôi luôn tốt nhất so với các phương án đánh rơi phần đầu và phương án đánh 
rơi cùng lúc cùng lúc cả phần đầu và đuôi. Như trình bày trong phần 2, thì phương án đánh rơi phần đuôi sẽ không làm 
thay đổi trật tự s p xếp các gói tin trong chùm chưa được lập lịch nên xác xuất rơi gói tin luôn thấp nhất. 
Mai Hoàng Thiên, Đặng Thanh Chương 273 
 Xác xuất rơi gói Xác gói xuấttin rơi 
 Tải (Erlang) 
 Hình 11. So sánh xác xuất rơi gói tin trên toàn mạng với 2 giải thuật NPMOC và NPMOC-VF 
 Ở kết quả mô phỏng Hình 11, ta thấy được xác xuất rơi gói tin của giải thuật NPMOC-VF tốt hơn giải thuật 
NPMOC, vì giải thuật NPMOC-VF kh c phục được nhược điểm của giải thuật NPMOC là tận dụng được các khoảng 
trống trên các kênh lập lịch mà giải thuật NPMOC không tận dụng được. 
 IV. KẾT LUẬN 
 Bài viết đã nêu lên được một số k thuật phân đoạn chùm kết hợp với lập lịch, trong đó đã làm rõ các phương 
án đánh rơi đầu, đánh rơi đuôi, đánh rơi phần đầu, đánh rơi phần đầu và đuôi cũng như việc kết hợp cả ba phương án. 
Kết quả phân tích cũng như vấn đề xây dựng cài đặt thuật toán cho thấy tính hiệu quả của k thuật phân đoạn chùm. 
Ngoài ra, k thuật phân đoạn chùm cũng có thể kết hợp được với các bài toán lập lịch khác trong mạng OBS nói riêng 
và mạng truyền thông nói chung. 
 T I LIỆU THAM KHẢO 
[1] A. Mandloi and V. Mishra (2012), “A Segmentation based Channel Scheduling Scheme in Optical Burst Switching Networks”, 
 International Journal of Computer Applications (0975 – 8887), Volume 51– No.6, August. 
[2] GUAN Ai-hong and WANG Bo-yun (2012), “A burst segmentation-deflection routing contention resolution mechanism in 
 OBS networks”, Optoelectronics Letters, Vol.8 No.1, 1 January. 
[3] Jason p. Jue, Vinod M., Vokkarane (2005), “Optical Burst Switched Networks”, Springer Science + Business Media, Inc. 
[4] M. Neuts, H. L. Vu and M. Zukerman (2002), “Insight into the benefit of burst segmentation in optical burst switching”. 
 Proceedings of International Conference on Optical Internetand Photonics in Switching, 126–128. 
[5] Phung Duc, T., Masuyama, H., Kasahara, S., and Takahashi, Y.(2009), “Performance Analysis of Optical Burst Switched 
 Networks with Limited-Range Wavelength Conversion, Retransmission and Burst Segmentation,” Journal of the Operations 
 Research Society of Japan, Vol. 52, No. 1, pp. 58-74, 
[6] V. M. Vokkarane, J. P. Jue and S. Sitaraman (2002), “Burst segmentation: an approach for reducing packet loss in optical burst 
 switched networks”, Proceedings of IEEE International Conference on Communications , 2673–2677. 
[7] V. M. Vokkarane and J. P. Jue (2002), “Prioritized Routing and Burst Segmentation for QoS in Optical Burst-Switched 
 Networks,” Proceedings, IEEE/OSA Optical Fiber Communication Conference, Anaheim, CA, March 
[8] V. M. Vokkarane and J. P. Jue (2003), “Prioritized burst segmentation and composite burst-assembly techniques for QoS 
 support in optical burst-switched networks”, IEEE Journalon Selected Areas in Communications, 21, 1198–1209. 
[9] T. Venkatesh, A. Jayaraj, and C. Siva Ram Murthy (2009), “Analysis of Burst Segmentation in Optical Burst Switching 
 Networks Considering Path Correlation”, Journal of Lightwave Technology, Vol. 27, No. 24, December 15, . 
[10] Won Seok Park, Minsu Shin, Hyang-Won Lee, Associate Member (2009), “A Joint Design of Congestion Control and Burst 
 Contention Resolution for Optical Burst Switching Networks”, Journal of Lightwave Technology, Vol. 27, NO. 17, September 1, 
[11] Obs-ns Simulator.  
[12] Ns2 Simulator.  
 TECHNICAL BURST SEGMENTATION 
 IN OPTICAL BURST SWITCHING NETWORKS 
 Mai Hoang Thien, Dang Thanh Chuong 
ABSTRACT—The problem of congestion in optical burst-switched networks (OBS) is considered an important problem to be 
solved. Burst segmentation in OBS networks can appear when two burst of optical data from two different ports to try to come out 
on the same port, on the same wavelength channels, and at the same time. The congestion processing solutions now include 
implementing wavelength conversion, fiber delay lines and deflection routing. In this paper aims to analyze some technical burst 
segmentation with scheduling and fiber delay lines. The results of the paper is evaluated through simulation package obs-0.9a on 
NS-2 software.