Nâng cao hiệu năng lập lịch trong mạng chuyển mạch link chuẩn của w88 quang

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áccô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 link chuẩn của w88 quang. Trong đó, mỗi công nghệ đều có ưu và nhược điểm. Chuyển mạch link chuẩn của w88 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 link chuẩn của w88 quang, mạng sợi quang, mạng toàn quang.

1. Tổng quan về mạng chuyển mạch link chuẩn của w88 quang

1.1. Mạng chuyển mạch link chuẩn của w88 quang

Mạng chuyển mạch link chuẩn của w88 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ácmạ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 link chuẩn của w88, tách link chuẩn của w88 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à link chuẩn của w88 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. link chuẩn của w88 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 link chuẩn của w88 quang

Một mạng chuyển mạch link chuẩn của w88 quang bao gồm các nút chuyển mạch link chuẩn của w88 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 link chuẩn của w88 quang có hai kiểu là nút biên và nút lõi.

Hình 1: Mạng chuyển mạch link chuẩn của w88 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 link chuẩn của w88 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 link chuẩn của w88 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 link chuẩn của w88 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 link chuẩn của w88 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 link chuẩn của w88 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 link chuẩn của w88 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 link chuẩn của w88.

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 link chuẩn của w88 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 link chuẩn của w88 đã đượ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 link chuẩn của w88 đế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 link chuẩn của w88 đế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 t_ubcủa link chuẩn của w88 và Thời điểm kết thúc của link chuẩn của w88 đã đượ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 LAUT_i≤ t_ub, thì kênh thứ i sẽ được xem xét cho việc lập lịch link chuẩn của w88 đế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 LAUT₁≤ t_ubvà LAUT₂< t_ub.

Giải thuật LAUC chọn kênh mà khoảng cách giữa link chuẩn của w88 đến và link chuẩn của w88 đã đượ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 LAUT₂≤ t_ubvà gap = t_ub- LAUT₂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 (sⁱ_j, eⁱ_j) của các link chuẩn của w88 đã đượ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...N_b, N_blà tổng số link chuẩn của w88 đượ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 eⁱ₁≤  t_ubvà sⁱ₂ ³ t_ub+ L_b, 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 link chuẩn của w88 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ố link chuẩn của w88 đế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 link chuẩn của w88 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 link chuẩn của w88 đế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 link chuẩn của w88 đế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 link chuẩn của w88 là b₁, b₂, b₃và b₄đến từ các liên kết đến và 4 link chuẩn của w88 này chồng lấp với nhau từ thời điểm t₁đến t₂với mức độ chồng lấp là 4. Như vậy, 2 trong 4 link chuẩn của w88 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 link chuẩn của w88 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 link chuẩn của w88 trên liên kết l, mỗi đường OBS cần cố gắng giảm sự chồng lấp link chuẩn của w88 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ố link chuẩn của w88 để giảm sự chồng lấp link chuẩn của w88, 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 link chuẩn của w88 b₂tại nút nguồn để nó đến liên kết Link X sau link chuẩn của w88 b₁, và hoàn toàn tương tự link chuẩn của w88 b₄sẽ được trì hoãn tại nút nguồn để nó đến liên kết Link Y sau link chuẩn của w88 b₃. Bằng cách này, nút OBS sẽ không loại bỏ bất kỳ link chuẩn của w88 đế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 link chuẩn của w88 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 link chuẩn của w88 đượ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 link chuẩn của w88 đế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 link chuẩn của w88. 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 t_ub+ α (t_ublà thời điểm đến của link chuẩn của w88, α là độ trễ tối đa), có nghĩa là không có kênh nào có thể đáp ứng link chuẩn của w88 này. Ngược lại, tồn tại ít nhất một kênh có thể lập lịch cho link chuẩn của w88. 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 t_ub+ α, 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 link chuẩn của w88, 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:

+ L_b: Độ dài link chuẩn của w88 đến chưa được lập lịch.

+ t_ub: Thời gian đến của link chuẩn của w88 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 t_ub+ α với gốc

+ Nếu gốc t_ub+ α thì chuyển sang Bước 6.

+ Ngược lại thì sang Bước 3.

Bước 3: So sánh t_ub+ α với con trái của nút đang xét

+ Nếu con trái ≤ t_ub+ α

+ 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á = t_ub+ L_b.

+ 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ố link chuẩn của w88 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ố link chuẩn của w88 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 link chuẩn của w88 quang.

TÀI LIỆU THAM KHẢO:

1. 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.
2. C. Papazoglou et al. (2009). Techniques for improved scheduling in optical burst switched networks.International Symposium on Autonomous Decentralized Systems, 09, 1-4.
3. J. Li and C. Qiao. (2004). Schedule burst proactively for optical burst switched networks.Computer Networks,44(5), 617–629.
4. 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.
5. Xu L., Perros H.G., Rouskas G. (2001). Techniques for optical packet switching and optical burst switching.IEEE Communications Magazine,136-142.
6. Y. Chen et al. (2004). Optical Burst Switching: a new area in optical networking research.IEEE Network,18(3), 16–23.
7. 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.

[Tạp chí Công Thương - Các kết quả nghiên cứu khoa học và ứng dụng công nghệ, Số 2, tháng 1 năm 2021]