Nâng cao hiệu năng lập lịch trong mạng chuyển mạch chùm quang
ThS. PHAN THANH BÌNH (Trường Đại học An Giang, Đại học Quốc gia TP. Hồ Chí Minh)
TÓM TẮT:
Những năm gần đây, tốc độ phát triển nhanh của Internet với sự bùng nổ của các loại hình dịch vụ thông tin, đã làm gia tăng không ngừng nhu cầu về băng thông mạng. Mạng sợi quang đã được công nhận như một giải pháp tốt nhất để đáp ứng những yêu cầu về băng thông hiện tại của người dùng và hỗ trợ cho các dịch vụ khác trong tương lai.
Hiện nay, các công nghệ chuyển mạch quang đã được đề xuất như chuyển mạch kênh quang, chuyển mạch gói quang và chuyển mạch chùm quang. Trong đó, mỗi công nghệ đều có ưu và nhược điểm. Chuyển mạch chùm quang được xem như giải pháp dung hòa ưu và nhược điểm của hai loại chuyển mạch kia và là công nghệ hứa hẹn trong tương lai.
Từ khóa: Mạng chuyển mạch chùm quang, mạng sợi quang, mạng toàn quang.
1. Tổng quan về mạng chuyển mạch chùm quang 1.1. Mạng chuyển mạch chùm quang
Mạng chuyển mạch chùm quang OBS (Optical Burst Switched) được đề xuất vào cuối năm 1990 và được biết đến như là một giải pháp trung gian của quá trình phát triển từ các mạng định tuyến bước sóng WR (Wavelength-Routed) đến các mạng chuyển mạch gói quang OPS (Optical Packet Switched). Thực tế, mạng OBS đã khắc phục được hạn chế về khả năng sử dụng và khai thác không hiệu quả băng thông của các mạng WR, bước đầu đưa mô hình chuyển mạch gói quang thành hiện thực khi mà công nghệ chế tạo vùng đệm quang chưa thực sự phát triển. Do đó, mạng OBS còn được gọi là mạng chuyển mạch gói quang không sử dụng vùng đệm.
Nút biên: Việc liên kết các mạng biên (Client networks) và mạng OBS được thực hiện bởi các nút biên OBS. Mạng biên có thể kể đến như IP, ATM, SONET/ SDH hoặc các mạng khác. Một nút biên (edge node) có thể là nút biên vào hoặc nút biên ra.
- Nút biên vào chịu trách nhiệm biến đổi các tín hiệu dữ liệu từ mạng biên thành định dạng dữ liệu truyền trong mạng OBS.
- Nút biên ra nhận chùm, tách chùm thành những gói tin riêng và chuyển chúng tới đích.
Nút lõi: Chức năng chính trên giao diện vào của nút lõi (core node) là tách các kênh dữ liệu và điều khiển.
Thời gian bù đắp (offset time): Là khoảng thời gian giữa gói điều khiển và chùm dữ liệu. Thời gian bù đắp cung cấp độ trễ để thực hiện xử lý và chuyển mạch tại các nút lõi mà không cần bộ đệm quang. Chùm sẽ bị mất nếu thời gian xử lý gói tin điều khiển dài hơn độ trễ. Do đó, việc thiết lập thời gian bù đắp thích hợp là quyết định quan trọng trong mạng OBS.
1.2. Kiến trúc mạng chuyển mạch chùm quang
Một mạng chuyển mạch chùm quang bao gồm các nút chuyển mạch chùm quang kết nối với nhau thông qua các sợi cáp quang. Mỗi sợi quang có khả năng hỗ trợ các kênh đa bước sóng. Như được trình bày ở Hình 1, các nút trên mạng chuyển mạch chùm quang có hai kiểu là nút biên và nút lõi.
Hình 1: Mạng chuyển mạch chùm quang
Một nút OBS bao gồm cả 2 phần: Quang và Điện.
- Phần quang là các bộ ghép/ tách bước sóng (multiplexer/ demultiplexer) và chuyển mạch quang.
- Phần điện có các module vào/ ra, điều khiển định tuyến và lập lịch. Đơn vị chuyển mạch quang điều khiển các chùm dữ liệu từ một cổng vào và cho ra trên một cổng tương ứng với đích đến của chúng.
Khi một nút biên chuẩn bị truyền một chùm dữ liệu, nó sẽ gửi một gói điều khiển đi trên một bước sóng riêng tới nút lõi. Gói điều khiển thực hiện việc báo hiệu, cấu hình các chuyển mạch tại nút lõi để chuyển chùm từ cổng vào đến cổng ra và giải quyết xung đột nếu xảy ra.
2. Một số cải tiến nhằm nâng cao hiệu năng lập lịch trong mạng chuyển mạch chùm quang
2.1. Một số giải thuật lập lịch truyền thống và những hạn chế
Trong mạng chuyển mạch chùm quang khi một gói điều khiển đến tại một nút lõi, một giải thuật lập lịch được gọi để ấn định chùm chưa được lập lịch trên một kênh dữ liệu (bước sóng) của liên kết ra. Dựa vào thông tin từ gói điều khiển, bộ lập lịch biết được các thông tin cần thiết như: Thời gian đến và Thời gian kết thúc của chùm.
Bộ lập lịch luôn duy trì thời gian chưa lập lịch khả dụng gần nhất LAUT (Lastest Available Unscheduled Time), khoảng trống (void) sau cùng nhất trên mỗi kênh dữ liệu ra. Những thông tin này cho phép bộ lập lịch xác định được bước sóng thích hợp nhat để lập lịch cho chùm dữ liệu đến.
Các giải thuật lập lịch được phân loại dựa trên ý tưởng chủ đạo là có hay không lấp đầy khoảng trống. Một khoảng trống là đoạn băng thông khả dụng trên một kênh, giữa hai chùm đã được lập lịch liên tiếp như mô tả ở Hình 2. Nếu chỉ xem xét việc lập lịch chùm đến đối với các kênh D1 và D2, giải thuật lập lịch là không xét đến việc lấp đầy khoảng trống. Ngược lại, nếu xét trên kênh D0 và D3, thì giải thuật lập lịch là có xét đến việc lấp đầy khoảng trống.
Hình 2: Lập lịch có/ không có lấp đầy khoảng trống
Thực tế, các khoảng trống này được sinh ra khi có những biến thiên quan trọng về mật độ luồng dữ liệu IP đến tại một nút biên vào mạng OBS, cũng như là mật độ các chùm đến tại các nút lõi.
2.1.1. Giải thuật LAUC
Giải thuật tiêu biểu đại diện cho việc lập lịch không xét đến lấp đầy khoảng trống là LAUC (Lastest Available Unused Channel).
Hình 3: Lập lịch không xét lấp đầy khoảng trống
Với giải thuật thuộc nhóm này, cần lưu ý đến 2 tham số: Thời điểm đến tub của chùm và Thời điểm kết thúc của chùm đã được lập lịch sau cùng nhất LAUTi (Latest Available Unscheduled Time) trên kênh dữ liệu khả dụng thứ i. Nếu LAUTi ≤ tub, thì kênh thứ i sẽ được xem xét cho việc lập lịch chùm đến. Như mô tả ở Hình 3, rõ ràng chỉ có kênh D1 và D2 là được xem xét vì thỏa mãn điều kiện LAUT1 ≤ tub và LAUT2 < tub.
Giải thuật LAUC chọn kênh mà khoảng cách giữa chùm đến và chùm đã được lập lịch sau cùng nhất là tối thiểu. Như mô tả ở Hình 3, kênh D2 được chọn vì thỏa mãn điều kiện LAUT2 ≤ tub và gap = tub - LAUT2 là nhỏ nhất.
2.1.2. Giải thuật LAUC-VF
Trên cở sở giải thuật không xét đến lấp đầy khoảng trống, giải thuật tương tự có xét đến lấp đầy khoảng trống đã được đề nghị là LAUC-VF. Hình 4 minh họa cho giải thuật này.
Hình 4: Lập lịch có lấp đầy khoảng trống
Với giải thuật thuộc nhóm này, bộ lập lịch duy trì thời điểm bắt đầu và kết thúc (sij, eij) của các chùm đã được lập lịch trên tất cả các kênh (trong đó i = 0...W-1, W là tổng số kênh, và j = 1...Nb, Nb là tổng số chùm được lập lịch trên một kênh). Như mô tả ở Hình 4, kênh D0 và D3 được xem xét vì thỏa mãn điều kiện ei1 ≤ tub và si2 ³ tub + Lb, i = 0...3.
Chúng ta thấy rằng, giải thuật LAUC-VF tận dụng băng thông của bước sóng tốt hơn và tỷ lệ mất chùm thấp hơn giải thuật LAUC. Tuy nhiên, thời gian thực hiện của giải thuật LAUC-VF (trong trường hợp tốt nhất) là dài hơn so với giải thuật lập lịch LAUC, đặc biệt là khi số khoảng trống lớn đáng kể so với số kênh dữ liệu.
2.1.3. Hạn chế của giải thuật lập lịch truyền thống
Hạn chế lớn nhất đối với các giải thuật truyền thống là việc tìm kiếm kênh bước sóng thỏa mãn điều kiện được thực hiện một cách tuần tự. Nghĩa là, giải thuật duyệt qua tất cả các kênh bước sóng. Trong mạng OBS thực tế, số lượng kênh bước sóng là rất lớn, do đó chi phí cho việc tìm kiếm tuần tự cũng sẽ lớn. Với thời gian tìm kiếm kéo dài rõ ràng không phải là giải pháp phù hợp để triển khai ứng dụng.
Bài toán đặt ra là cần phải rút ngắn thời gian thực hiện của thuật toán. Để giải quyết vấn đề này, nhiều giải thuật đã được đề xuất, trong đó có giải thuật mà nghiên cứu sẽ giới thiệu tại phần tiếp theo.
2.2. Một số tiếp cận cải tiến nhằm nâng cao hiệu năng lập lịch
2.2.1. Nhóm giải thuật BORA
2.2.1.1. Giải thuật lập lịch BORA
T. Li và cộng sự [5] cho rằng, nếu tổng số chùm đến vào cùng một thời điểm vượt quá tổng số kênh và nếu không sử dụng các đường trễ FDL thì việc mất chùm sẽ không thể tránh khỏi. Để mô tả cho hiện tượng này, khái niệm sự chồng lấp được định nghĩa như sau: Cho một liên kết l tại thời điểm t, nếu có nhiều chùm đến tại thời điểm t thì sẽ có sự chồng lấp với nhau.
Hình 5: Sự chồng lấp
Hình 5 cho thấy, LAUC-VF thất bại trong việc lập lịch các chùm đến. Trong ví dụ này, nút OBS trung gian có hai liên kết đến và một liên kết đi, mỗi liên kết có hai kênh dữ liệu và một kênh điều khiển. Giả sử có 4 chùm là b1, b2, b3 và b4 đến từ các liên kết đến và 4 chùm này chồng lấp với nhau từ thời điểm t1 đến t2 với mức độ chồng lấp là 4. Như vậy, 2 trong 4 chùm sẽ bị loại bỏ nếu nút OBS không có FDLs hoặc tất cả FDLs đã được sử dụng hết bởi các chùm khác.
Giả sử có n đường OBS trên một liên kết l trong một mạng OBS được cho. Mỗi đường OBS có một nút vào và một nút ra. Để giảm bớt mức độ chồng lấp chùm trên liên kết l, mỗi đường OBS cần cố gắng giảm sự chồng lấp chùm trên chính nó. Trong một mạng OBS không FDLs, các nút lõi không thể làm trễ một số chùm để giảm sự chồng lấp chùm, tuy nhiên, các nút biên vào với bộ đệm điện tử có thể làm điều đó bằng cách sử dụng giải thuật lập lịch BORA (Burst Overlap Reduction Algorithm).
Theo Hình 5, giải thuật BORA sẽ trì hoãn chùm b2 tại nút nguồn để nó đến liên kết Link X sau chùm b1, và hoàn toàn tương tự chùm b4 sẽ được trì hoãn tại nút nguồn để nó đến liên kết Link Y sau chùm b3. Bằng cách này, nút OBS sẽ không loại bỏ bất kỳ chùm đến nào như trong Hình 6.
Hình 6: Tránh chồng lấp
2.2.1.2. Giải thuật lập lịch BORA-FS
T. Li và cộng sự [5] điều chỉnh thuật toán của BORA bằng cách chỉ cho phép thời gian trễ thêm trên mỗi chùm không vượt quá một giá trị đặt trước, ký hiệu là α. Thuật toán sẽ tìm kiếm kênh thỏa mãn cho việc lập lịch bằng cách duyệt tuần tự trên tất cả các kênh theo một thứ tự cố định. Thuật toán sẽ dừng khi một kênh thích hợp được tìm thấy đáp ứng được các yêu cầu về độ trễ tối đa (nhỏ hơn α) hoặc không có kênh nào thỏa mãn. Thời gian thực hiện cho việc tìm kiếm này là O(k), với k là số kênh của liên kết ra.
Thuật toán điều chỉnh này lập lịch cho các chùm được sinh ra cục bộ đến thời điểm sau cùng gần nhất (từ horizon hay LAUT) được gọi là BORA-FS (BORA with Fixed-ordered Search).
2.2.1.3. Giải thuật lập lịch BORA-FS-VF
Giải thuật lập lịch BORA-FS [5] nếu được thay thế các giá trị LAUT bởi các khoảng trống thì được gọi là BORA-FS-VF (Burst Overlapping Reduction Algorithm with Fixed-ordered Searching and Void Filling).
Hoàn toàn giống như LAUC-VF, BORA-FS-VF cũng thực hiện việc tìm kiếm tuần tự trên tất cả các kênh bước sóng giá trị khoảng trống cho việc lập lịch. Trường hợp không có kênh bước sóng nào thỏa mãn cho việc lập lịch chùm đến thì sẽ được tìm giá trị LAUT thỏa mãn.
2.2.1.4. Giải thuật lập lịch cải tiến Improved-BORA-FS
Vì BORA-FS kiểm tra tuần tự từng kênh một, nó có thể mất thời gian O(k) để lập lịch một chùm. Khi số lượng các kênh là hàng trăm hoặc hàng ngàn, thời gian xử lý của việc tìm kiếm tuần tự này có thể trở nên rất lớn, điều này không phù hợp với ứng dụng thực tế.
Để cải thiện thời gian tìm kiếm của giải thuật BORA-FS, một giải thuật được đề xuất có tên gọi là improved-BORA-FS.
Giải thuật improved-BORA-FS cải thiện đáng kể thời gian tìm kiếm, vốn là điểm hạn chế của giải thuật BORA-FS. Thời gian của việc tìm kiếm so với giải thuật BORA-FS sẽ giảm từ O(k) xuống còn O(logk) (với k là số kênh của liên kết ra) bằng phương pháp tổ chức lại dữ liệu theo cấu trúc của cây nhị phân tìm kiếm như Hình 7.
Hình 7: Cây improved-BORA-FS
Cây nhị phân tìm kiếm cho giải thuật improved-BORA-FS được hình thành như sau:
- Mỗi nút lá có giá trị là LAUT hoặc Horizon tương ứng (bao nhiêu kênh sẽ có bấy nhiêu nút lá);
- Nút cha sẽ có giá trị là con nhỏ nhất của con trái và con phải.
Thuật toán lập lịch bắt đầu từ gốc của cây nhị phân. Nếu giá trị của mục ở gốc lớn hơn tub + α (tub là thời điểm đến của chùm, α là độ trễ tối đa), có nghĩa là không có kênh nào có thể đáp ứng chùm này. Ngược lại, tồn tại ít nhất một kênh có thể lập lịch cho chùm. Trong trường hợp này, thuật toán lập lịch kiểm tra con trái. Nếu giá trị của nó lớn hơn tub + α, thì con phải sẽ được kiểm tra tiếp theo. Nếu không, thuật toán lập lịch tiếp tục tìm kiếm từ con trái của mình một cách đệ quy. Khi việc tìm kiếm kênh dừng lại và một kênh được chọn cho chùm, LAUT của kênh này được cập nhật và cũng cập nhật các giá trị của các nút từ nút lá tương ứng với kênh đã ấn định đến gốc của cây nhị phân.
Giải thuật improved-BORA-FS được mô tả chi tiết như sau:
Tham số vào:
+ Lb : Độ dài chùm đến chưa được lập lịch.
+ tub : Thời gian đến của chùm chưa được lập lịch.
+ W: Số kênh dữ liệu ra tối đa cho việc lập lịch.
+ i: Kênh dữ liệu thứ i = 0...W-1.
+ a: Độ trễ tối đa.
Dữ liệu đầu ra:
sc : Chỉ số kênh được chọn.
Giải thuật:
Bước 1: Khởi tạo cây
Bước 2: So sánh tub + α với gốc
+ Nếu gốc > tub + α thì chuyển sang Bước 6.
+ Ngược lại thì sang Bước 3.
Bước 3: So sánh tub + α với con trái của nút đang xét
+ Nếu con trái ≤ tub + α
+ Nếu con trái là nút lá thì:
+ Chuyển sang Bước 5.
+ Ngược thì quay lại Bước 3.
+ Ngược lại thì sang Bước 4.
Bước 4: Nếu con phải là lá thì:
+ Chuyển sang Bước 5.
+ Ngược lại thì quay về Bước 3 với gốc là nút đang xét.
Bước 5: Thực hiện các công việc:
+ Gán sc = kênh tương ứng với nút lá.
+ Nút lá = tub + Lb.
+ Cập nhật lại cây.
Bước 6: Kết thúc.
3. Kết luận
Hai vấn đề cần quan tâm trong việc lập lịch: (i) Thời gian lập lịch càng ngắn càng tốt và (ii) Số chùm rơi càng ít càng tốt.
Giải thuật improved-BORA-FS được trình bày bên trên đã phần nào giải quyết được vấn đề thứ nhất.
Theo đó, các giải thuật có xét đến lấp đầy khoảng trống luôn hiệu quả hơn so với các giải thuật không có xét đến lấp đầy khoảng trống trong việc hạn chế số chùm rơi. Vấn đề này giải thuật improved-BORA-FS chưa giải quyết được. Nếu được tiếp tục cải tiến improved-BORA-FS theo hướng xem xét đến việc lấp đầy khoảng trống thì cả 2 vấn đề quan trọng trong việc lập lịch đều được giải quyết. Nhờ vậy, giải thuật có thể được sử dụng trong các ứng dụng thực tế của mạng chuyển mạch chùm quang.
TÀI LIỆU THAM KHẢO:
Amit Kumar Garg et al. (2009). A Novel Scheduling Algorithm for Optical Burst Switched Networks.
Journal of Microwaves: Optoelectronics and Electromagnetic Applications,
8(2), 51-58.
C. Papazoglou et al. (2009). Techniques for improved scheduling in optical burst switched networks.
International Symposium on Autonomous Decentralized Systems
, 09, 1-4.
J. Li and C. Qiao. (2004). Schedule burst proactively for optical burst switched networks.
Computer Networks,
44(5), 617–629.
Qiao C., Yoo M. (1999). Optical Burst Switching (OBS) - A New Paradigm for an Optical Internet.
Journal of High Speed Networks,
8(1), 69-84.
Xu L., Perros H.G., Rouskas G. (2001). Techniques for optical packet switching and optical burst switching.
IEEE Communications Magazine,
136-142.
Y. Chen et al. (2004). Optical Burst Switching: a new area in optical networking research.
IEEE Network,
18(3), 16–23.
Yuhua Chen et al. (2007). Optimal Burst Scheduling in Optical Burst Switched Networks.
Journal Of Lightwave Technology,
25(8), 1883- 1894.
ENHANCING THE SCHEDULE PERFORMANCE
IN THE OPTICAL BURST SWITCHED
• Master. PHAN THANH BINH
An Giang University
Vietnam National University - Ho Chi Minh City Campus
ABSTRACT:
In recent years, the rapid growth of the Internet with the infoormation explosion has increased the demand for network bandwidth constantly. Fiber-optic networks have been recognized as the best solution for meeting current bandwidth requirements and future support for other services.
Currently, optical switching technologies such as optical channel switched, optical packet switched and optical burst switched have been proposed. Each switching technology has its advantages and disadvantages. Optical burst switched is considered as a solution to reconcile the pros and cons of the other two types of switching and it is a promising technology in the future.
Keywords: optical burst switched, fiber-optic network, all optical network.
