Tổng quan luận án

Sự phát triển của mạng Internet cùng với sự gia tăng của các loại hình dịch vụ truyền thông đòi hỏi băng thông lớn như truyền hình Internet (IPTV), video theo yêu cầu (VoD) và điện thoại Internet (VoIP) đã đặt ra yêu cầu nâng cao năng lực truyền tải của mạng viễn thông thế hệ mới. Trong khi sợi cáp đồng đã đạt tới giới hạn vật lý, công nghệ truyền dẫn sợi quang kết hợp với kỹ thuật ghép kênh phân chia theo bước sóng (WDM - Wavelength Division Multiplexing) trở thành giải pháp đáp ứng nhu cầu này nhờ tiềm năng băng thông lý thuyết lên tới 50 Tb/s và hệ số suy hao thấp (khoảng $10^{-2}$ dB).

Quá trình phát triển của mạng truyền thông quang đã trải qua các mô hình chuyển mạch:

  • Chuyển mạch kênh quang (OCS - Optical Circuit Switching): Hoạt động dựa trên các đường quang tĩnh (lightpath) được thiết lập thông qua cơ chế đặt trước tài nguyên hai chiều (two-way reservation). Mô hình này có độ trễ thiết lập cao và không thích ứng hiệu quả với bản chất đột biến (bursty) của lưu lượng Internet, dẫn đến hiệu suất sử dụng băng thông thấp.
  • Chuyển mạch gói quang (OPS - Optical Packet Switching): Cho phép chuyển mạch gói tin trực tiếp trong miền quang, mang lại hiệu suất sử dụng băng thông cao. Tuy nhiên, OPS đòi hỏi các bộ chuyển mạch quang đạt tốc độ nano giây và các bộ đệm quang (tương tự bộ nhớ RAM điện tử), vốn là những công nghệ chưa thể thương mại hóa. Việc sử dụng các đường trễ quang (FDL - Fiber Delay Line) gặp hạn chế lớn về mặt không gian vật lý (cần tới 200 km sợi quang chỉ để trì hoãn một tín hiệu trong 5 mili giây).
  • Chuyển mạch chùm quang (OBS - Optical Burst Switching): Được đề xuất như một giải pháp dung hòa giữa OCS và OPS. Trong mạng OBS, các gói dữ liệu điện tử có cùng đích đến được tập hợp tại nút biên thành các đơn vị truyền tải lớn hơn gọi là chùm quang (data burst). Phần điều khiển được tách rời hoàn toàn khỏi phần dữ liệu cả về không gian và thời gian: gói điều khiển (BHP - Burst Header Packet) được truyền trước trên kênh điều khiển riêng biệt một khoảng thời gian offset (offset-time) để đặt trước tài nguyên và cấu hình chuyển mạch tại các nút lõi, trước khi chùm dữ liệu được truyền vào mạng mà không cần lưu đệm.

Đặc trưng truyền dẫn một chiều (one-way reservation) không cần đợi báo nhận đặt ra áp lực xử lý rất lớn tại các nút lõi: gói điều khiển phải hoàn thành việc lập lịch đặt trước tài nguyên trước khi chùm dữ liệu tương ứng đi tới. Nếu xảy ra xung đột mà không có giải thuật lập lịch và cơ chế xử lý phù hợp, chùm dữ liệu sẽ bị hủy bỏ hoàn toàn.

Văn bản luận án chỉ ra các khoảng trống nghiên cứu cụ thể trong các giải thuật lập lịch đã công bố:

  1. Nhóm lập lịch trực tiếp và lập lịch kết hợp: Các giải thuật lập lịch trực tiếp (như LAUC, BF-VF) chỉ tối ưu hóa việc phân bổ kênh cho chùm dữ liệu hiện thời mà không xét đến các chùm đến sau, dẫn đến tình trạng phân mảnh băng thông. Các giải thuật kết hợp giữa lập lịch trực tiếp, lập lịch lại và phân đoạn chùm (như ODBR, ABR, PCSA, SODBRA) chưa sử dụng giải thuật lập lịch trực tiếp tối ưu nhất ở giai đoạn đầu, cơ chế lập lịch lại chỉ xem xét chùm sau cùng nhất trên kênh ra, và kỹ thuật phân đoạn chùm chấp nhận loại bỏ hoàn toàn đoạn chồng lấp mà không khai thác các khoảng trống băng thông.
  2. Nhóm lập lịch nhóm trên đơn kênh (không có bộ chuyển đổi bước sóng): Các giải thuật hiện hành (OBS-GS, MWIS-OS) có độ phức tạp tính toán cao khi tìm tập độc lập trên đồ thị khoảng, chưa tận dụng các khoảng trống băng thông nhàn rỗi (voids) giữa các chùm đã được lập lịch trước đó, và áp dụng khe thời gian chờ lập lịch ($\tau$) cố định, không thích ứng với sự thay đổi của mật độ lưu lượng đến.
  3. Nhóm lập lịch nhóm trên đa kênh (có bộ chuyển đổi bước sóng đầy đủ): Các giải thuật heuristic (SSF, LIF, SLV, MCF) chỉ sắp xếp chùm theo thứ tự đơn thuần mà thiếu tiêu chí chọn lựa tối ưu; trong khi các giải thuật tiếp cận tối ưu (GreedyOPT, BATCHOPT) yêu cầu gỡ bỏ toàn bộ các chùm đã lập lịch để đưa về bài toán lập lịch trên máy đồng nhất—một phương án làm tăng số lượng gói điều khiển, đòi hỏi thay đổi giao thức báo hiệu và không khả thi khi triển khai trên mạng thực tế.

Mục tiêu nghiên cứu tổng quát của luận án là nghiên cứu, cải tiến và đề xuất một số giải thuật lập lịch nhằm nâng cao hiệu năng hoạt động của mạng chuyển mạch chùm quang, bao gồm: tối thiểu hóa xác suất mất mát dữ liệu, tối đa hóa hiệu suất sử dụng băng thông, giảm thời gian trễ và giảm độ phức tạp tính toán của thuật toán.

Các mục tiêu cụ thể được xác định tương ứng với ba vấn đề nghiên cứu:

  • Mục tiêu 1 (Vấn đề 1): Nghiên cứu, cải tiến giải thuật lập lịch trực tiếp kết hợp với lập lịch lại và phân đoạn chùm.
  • Mục tiêu 2 (Vấn đề 2): Nghiên cứu, cải tiến và đề xuất mới giải thuật lập lịch nhóm trên đơn kênh.
  • Mục tiêu 3 (Vấn đề 3): Nghiên cứu, cải tiến và đề xuất mới giải thuật lập lịch nhóm trên đa kênh.

Đối tượng và phạm vi nghiên cứu:

  • Đối tượng nghiên cứu: Các mô hình, giải thuật lập lịch và các phương pháp xử lý tắc nghẽn trong mạng chuyển mạch chùm quang (OBS).
  • Phạm vi nghiên cứu: Hoạt động lập lịch đặt trước tài nguyên tại các nút lõi của mạng OBS.

Tổng quan tài liệu và vị trí của luận án

Luận án tiến hành tổng hợp và phân loại hệ thống các công trình nghiên cứu đã công bố theo từng hướng tiếp cận lập lịch và giải quyết tắc nghẽn trong mạng OBS:

  1. Hướng tiếp cận lập lịch trực tiếp:
  • Nhóm không lấp đầy khoảng trống (Non-Void Filling): Turner và cộng sự đề xuất giải thuật FFUC (First-Fit Unscheduled Channel) và LAUC (Latest Available Unscheduled Channel). Bộ lập lịch chỉ duy trì giá trị thời điểm chưa được lập lịch sau cùng nhất (LAUT - Latest Available Unscheduled Time) trên từng kênh. FFUC chọn kênh khả dụng đầu tiên, còn LAUC chọn kênh có khoảng cách thời gian (gap) từ LAUT đến thời điểm đến của chùm là nhỏ nhất. Nhóm này có ưu điểm tính toán nhanh nhưng gây lãng phí các khoảng băng thông trống ở giữa các chùm.
  • Nhóm có lấp đầy khoảng trống (Void-Filling): Xu và cộng sự đề xuất FFUC-VF và LAUC-VF (còn gọi là Min-SV - Minimal Start Void), yêu cầu lưu trữ cả thời điểm bắt đầu và kết thúc của các chùm đã lập lịch để tận dụng khoảng trống rỗi. Iizuka và cộng sự đề xuất MinEV (Minimal End Void) nhằm tối thiểu hóa khoảng trống sinh ra phía sau chùm. Nandi, Ljolje và cộng sự đề xuất BFUC và BF-VF (Best Fit with Void Filling), sử dụng tiêu chí độ khả dụng băng thông $utilization = (burstlength \times 100) / voidlength$ để tìm khoảng trống vừa khít nhất.
  1. Hướng tiếp cận lập lịch trực tiếp kết hợp:
  • Kết hợp lập lịch trực tiếp và lập lịch lại: Tan và cộng sự đề xuất ODBR (On-Demand Burst Rescheduling) và ABR (Active Burst Rescheduling). ODBR chỉ lập lịch lại chùm sau cùng nhất khi chùm mới đến không tìm được kênh khả dụng bằng LAUC. ABR thực hiện lập lịch lại mỗi khi có một chùm được lập lịch thành công nếu việc di chuyển làm giảm độ rộng khoảng trống.
  • Kết hợp lập lịch trực tiếp và phân đoạn chùm: Vokkarane và cộng sự đề xuất kỹ thuật phân đoạn chùm (burst segmentation) với cơ chế loại bỏ đoạn đầu (head dropping) hoặc đoạn đuôi (tail dropping), cùng các giải thuật NP-MOC và NP-MOC-VF nhằm chọn kênh có khoảng thời gian chồng lấp nhỏ nhất.
  • Kết hợp lập lịch trực tiếp, lập lịch lại và phân đoạn chùm: Umaru, Aydin và cộng sự phát triển giải thuật PCSA (kết hợp LAUC-VF, ODBR và phân đoạn chùm) phục vụ yêu cầu QoS; và giải thuật SODBRA (kết hợp FFUC-VF, ODBR và phân đoạn chùm).
  1. Hướng tiếp cận lập lịch nhóm:
  • Lập lịch nhóm trên đơn kênh (không chuyển đổi bước sóng): Các giải thuật tiêu biểu gồm OBS-GS và MWIS-OS. Các phương pháp này tập hợp các gói điều khiển đến trong một khe thời gian $\tau$, biểu diễn xung đột bằng đồ thị khoảng (interval graph) và giải bài toán tìm tập độc lập có trọng số lớn nhất (MWIS - Maximum Weight Independent Set). OBS-GS tối đa hóa số lượng chùm được lập lịch, trong khi MWIS-OS tối đa hóa tổng độ dài các chùm được chọn.
  • Lập lịch nhóm trên đa kênh (có bộ chuyển đổi bước sóng toàn phần): Hướng tiếp cận heuristic gồm các giải thuật SSF (Smallest Start-time First), LIF (Largest Interval First), SLV (Smallest-Last Vertex) và MCF (Maximal Cliques First). Hướng tiếp cận tối ưu gồm GreedyOPT và BATCHOPT, mô hình hóa việc lập lịch nhóm thành bài toán lập lịch công việc trên các máy đồng nhất.
  1. Các kỹ thuật xử lý tắc nghẽn phối hợp:
  • Sử dụng đường trễ sợi quang (FDL) để làm trễ chùm dữ liệu trong miền quang.
  • Chuyển đổi bước sóng (Wavelength Conversion): Chuyển đổi hoàn toàn, chuyển đổi giới hạn, chuyển đổi cố định và phân bổ thưa thớt.
  • Định tuyến lệch hướng (Deflection Routing): Chuyển hướng chùm tranh chấp sang một cổng ra khác.

Vị trí và lựa chọn học thuật của luận án: Luận án tập trung giải quyết các tồn tại của các công trình đi trước thông qua việc:

  • Tối ưu hóa mô hình kết hợp ba giai đoạn (lập lịch trực tiếp - lập lịch lại - phân đoạn chùm) bằng cách tích hợp kỹ thuật lấp đầy khoảng trống ở tất cả các giai đoạn, hình thành giải thuật iCSA.
  • Giảm độ phức tạp tính toán từ hàm mũ của bài toán MWIS trên đồ thị khoảng xuống tuyến tính, đồng thời tích hợp cơ chế lấp đầy khoảng trống và tự động điều chỉnh khe thời gian $\tau$ thích ứng theo lưu lượng đến trên đơn kênh (chuỗi giải thuật LGS, LGS-VF, LAGS, LAGS-VF).
  • Xây dựng giải thuật tối ưu OPT-GS dựa trên mô hình luồng cực đại trên đồ thị khoảng mà không cần gỡ bỏ các chùm đã lập lịch; đồng thời đề xuất giải thuật heuristic dựa trên bài toán tìm Clique có trọng số lớn nhất (MWC-GS, MWC-VF-GS) cho môi trường đa kênh.

Cơ sở lý thuyết và phương pháp nghiên cứu

Cơ sở lý thuyết và khung phân tích

  1. Lý thuyết lập lịch công việc (Job Scheduling): Luận án mô hình hóa bài toán lập lịch chùm quang tại cổng ra của nút lõi OBS tương đương với bài toán lập lịch công việc trong vận trù học. Mỗi kênh bước sóng ra được xem như một máy xử lý, và mỗi chùm dữ liệu cần lập lịch tương ứng với một công việc. Xét tập hợp $n$ công việc $I = {b_1, b_2, \dots, b_n}$ tương ứng với $n$ chùm dữ liệu được yêu cầu từ danh sách gói điều khiển ${BHP_1, BHP_2, \dots, BHP_n}$. Mỗi chùm $b_i = (s_i, e_i)$ có thời điểm bắt đầu $s_i$, thời điểm kết thúc $e_i$ và độ dài $l_i = e_i - s_i$. Hai chùm $b_i$ và $b_j$ tương thích khi khoảng thời gian chiếm dụng không giao nhau ($[s_i, e_i] \cap [s_j, e_j] = \emptyset$). Kênh bước sóng thứ $k$ duy trì mốc thời gian khả dụng $LAUT_k$. Chùm $b_i$ có thể lập lịch trên kênh $k$ nếu $s_i \ge LAUT_k$ hoặc khoảng $[s_i, e_i]$ nằm trọn trong một khoảng trống nhàn rỗi (void) của kênh đó. Mục tiêu là tìm tập chùm con $I' \subseteq I$ thỏa mãn điều kiện tương thích sao cho tổng số lượng chùm hoặc tổng độ dài chùm được phục vụ là cực đại.

  2. Lý thuyết đồ thị (Graph Theory):

  • Đồ thị khoảng (Interval Graph): Đồ thị vô hướng $G = (V, E)$ trong đó mỗi đỉnh $v \in V$ đại diện cho một khoảng thời gian của chùm quang, và một cạnh $(u, v) \in E$ tồn tại khi và chỉ khi hai khoảng thời gian tương ứng chồng lấp lên nhau.
  • Tập độc lập (Independent Set) và Tập độc lập cực đại (Maximal Independent Set): Tập hợp các đỉnh không có cạnh nối chung, đại diện cho tập các chùm không xung đột có thể lập lịch trên cùng một kênh bước sóng.
  • Clique, Clique cực đại (Maximal Clique) và Clique có trọng số lớn nhất (Maximum Weight Clique - MWC): Tập con các đỉnh đôi một kề nhau, đại diện cho các chùm cùng xung đột tại một thời điểm. MWC được sử dụng để xác định nhóm chùm có tổng độ dài lớn nhất cần phân bổ trên hệ thống đa kênh.
  • Đồ thị luồng (Flow Network) và mạng phân tầng: Dùng để chuyển đổi bài toán tìm tập chùm tối ưu trên đa kênh thành bài toán tìm luồng cực đại với chi phí cực tiểu.
  • Kỹ thuật tô màu đồ thị (Graph Coloring): Sử dụng để phân bổ bước sóng cho các chùm không xung đột.
  1. Phương pháp quy hoạch động (Dynamic Programming): Được sử dụng để lưu vết các trạng thái tối ưu cục bộ nhằm giảm độ phức tạp tính toán trong quá trình duyệt tìm khoảng trống và sắp xếp thứ tự chùm.

Phương pháp nghiên cứu thực tế

  • Phương pháp nghiên cứu lý thuyết: Phân tích toán học, chứng minh tính đúng đắn của các giải thuật cải tiến và tính toán độ phức tạp thuật toán (ký hiệu $O$).
  • Phương pháp mô phỏng thực nghiệm:
    • Công cụ mô phỏng: Sử dụng phần mềm mô phỏng mạng NS2 (Network Simulator 2) kết hợp với gói mô phỏng mạng quang chuyên dụng obs-0.9a.
    • Cài đặt thuật toán: Toàn bộ các giải thuật đề xuất và các giải thuật đối sánh được lập trình bằng ngôn ngữ C++.
    • Mô hình mạng mô phỏng: Áp dụng trên hai cấu trúc topo mạng chuẩn gồm mạng hình quả tạ (Dumbbell topology) và mạng NSFNET (National Science Foundation Network) phiên bản 14 nút.
    • Các chỉ số đánh giá thực nghiệm: Xác suất mất gói tin (Packet Loss Probability), thông lượng mạng (Throughput), số lượng chùm phải lập lịch lại, số lượng chùm bị phân đoạn, thời gian chờ đợi trung bình trong hàng đợi lập lịch, và độ biến thiên của kích thước khe thời gian $\tau$.

Nội dung chính theo từng chương

Chương 1. TỔNG QUAN VỀ LẬP LỊCH TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG

Chương 1 hệ thống hóa lịch sử phát triển của mạng truyền thông quang qua ba thế hệ: thế hệ thứ nhất sử dụng liên kết WDM điểm-nối-điểm với các bộ chuyển đổi quang-điện-quang (O-E-O); thế hệ thứ hai dựa trên bộ thêm/tách bước sóng (WADM) trên cấu trúc mạng vòng; thế hệ thứ ba sử dụng các thiết bị kết nối toàn quang (bộ chia hình sao thụ động, bộ định tuyến thụ động, bộ chuyển mạch chủ động) trên mạng lưới.

Luận án phân tích chi tiết ba mô hình chuyển mạch quang và tổng hợp bảng so sánh định tính theo các tiêu chí kỹ thuật:

Loại chuyển mạch Khả năng tận dụng băng thông Mức trễ Đệm quang Xử lý/Đồng bộ gói điều khiển Khả năng thích ứng với tải lưu lượng
OCS Thấp Cao Không Thấp Thấp
OPS Cao Thấp Yêu cầu Cao Cao
OBS Cao Thấp Không Thấp Cao

Nội dung chương đi sâu vào kiến trúc mạng OBS, mô tả cấu tạo của nút biên (thực hiện tập hợp gói tin điện tử IP/ATM/Ethernet theo cơ chế timer-based, length-based hoặc kết hợp) và nút lõi (gồm đơn vị điều khiển chuyển mạch SCU và ma trận chuyển mạch quang). Các hoạt động cốt lõi gồm: báo hiệu (các giao thức một chiều không báo nhận như JET, JIT), định tuyến và cấp phát bước sóng (RWA tĩnh và động), và các phương pháp giải quyết tranh chấp (đường trễ FDL, bộ chuyển đổi bước sóng WC, định tuyến lệch hướng).

Về bài toán lập lịch, chương phân loại toàn diện các giải thuật lập lịch đã công bố thành:

  • Lập lịch trực tiếp không lấp đầy khoảng trống (FFUC, LAUC) và có lấp đầy khoảng trống (FFUC-VF, LAUC-VF, MinEV, BF-VF).
  • Lập lịch trực tiếp kết hợp lập lịch lại (ODBR, ABR) và phân đoạn chùm (NP-MOC, NP-MOC-VF, PCSA, SODBRA).
  • Lập lịch nhóm trên đơn kênh (OBS-GS, MWIS-OS) và đa kênh (heuristic: SSF, LIF, SLV, MCF; tối ưu: GreedyOPT, BATCHOPT).

Chương 1 kết luận rằng các giải thuật hiện tại bộc lộ giới hạn về phân mảnh băng thông, độ phức tạp tính toán hoặc tính bất khả thi khi triển khai trên mạng thực tế, từ đó xác lập cơ sở khoa học cho các cải tiến trong các chương tiếp theo.

Chương 2. MỘT CẢI TIẾN MÔ HÌNH KẾT HỢP LẬP LỊCH TRỰC TIẾP VỚI LẬP LỊCH LẠI VÀ PHÂN ĐOẠN CHÙM

Chương 2 tập trung phân tích hạn chế của các giải thuật kết hợp hiện có:

  • ODBR chỉ hỗ trợ lập lịch lại đơn mức cho chùm sau cùng trên kênh dựa trên LAUC, bỏ qua khoảng trống nội tại.
  • ABR thực hiện lập lịch lại liên tục gây tăng chi phí xử lý.
  • SODBRA sử dụng FFUC-VF ở giai đoạn 1 dẫn đến việc lấp khoảng trống không tối ưu, và ODBR ở giai đoạn 2 không tìm kiếm khoảng trống.
  • PCSA sử dụng LAUC-VF chỉ tối thiểu hóa khoảng cách một đầu khoảng trống. Khi phân đoạn chùm, phần chồng lấp bị loại bỏ hoàn toàn mà không kiểm tra khả năng chèn vào các khoảng trống khác.

Để khắc phục, tác giả đề xuất giải thuật kết hợp cải tiến iCSA (improved Combined Scheduling Algorithm). Cấu trúc của iCSA gồm ba giai đoạn xử lý kế tiếp:

  • Giai đoạn 1 (Lập lịch trực tiếp tối ưu): Sử dụng giải thuật lập lịch trực tiếp có lấp đầy khoảng trống tối ưu nhất để tìm kênh khả dụng cho chùm đến $ub$.
  • Giai đoạn 2 (Lập lịch lại đa kênh có khai thác khoảng trống): Nếu giai đoạn 1 thất bại, iCSA tiến hành kiểm tra khả năng di chuyển các chùm đã lập lịch sang các kênh khác không chỉ ở vị trí sau cùng mà cả trong các khoảng trống khả dụng, nhằm giải phóng một khoảng thời gian liên tục đủ lớn cho chùm $ub$.
  • Giai đoạn 3 (Phân đoạn chùm linh hoạt): Nếu lập lịch lại thất bại, thay vì hủy toàn bộ chùm, kỹ thuật phân đoạn chùm được kích hoạt. Đoạn không tranh chấp được lập lịch truyền tiếp; đoạn bị tranh chấp tiếp tục được đưa vào quy trình tìm kiếm khoảng trống trên các kênh khác thay vì loại bỏ ngay.

Kết quả mô phỏng trên cấu trúc mạng NSFNET cho thấy:

  • Xác suất mất gói của BF-VF thấp hơn LAUC, khẳng định tính đúng đắn của việc chọn giải thuật tối ưu khoảng trống ở giai đoạn đầu.
  • Giải thuật iCSA đạt xác suất mất gói tin thấp hơn rõ rệt so với ODBR, ABR, SODBRA và PCSA trên mọi mức tải mạng.
  • Số lượng chùm phải lập lịch lại của iCSA thấp hơn so với ODBR, ABR và PCSA.
  • Số lượng chùm bị phân đoạn của iCSA giảm đáng kể so với SODBRA và PCSA do các đoạn tranh chấp được tái lập lịch vào các khoảng trống rỗi.

Chương 3. MỘT SỐ CẢI TIẾN GIẢI THUẬT LẬP LỊCH NHÓM TRÊN ĐƠN KÊNH

Chương 3 giải quyết bài toán lập lịch nhóm tại các nút lõi OBS không trang bị bộ chuyển đổi bước sóng. Hai giải thuật tiêu biểu đã công bố là OBS-GS (tối đa số lượng chùm) và MWIS-OS (tối đa tổng độ dài chùm) đều mô hình hóa bài toán thành việc tìm tập độc lập cực đại trên đồ thị khoảng, dẫn đến độ phức tạp thuật toán cao ($O(n^2)$ hoặc $O(n^3)$ tùy số lượng chùm trong khe $\tau$), không phù hợp với yêu cầu xử lý thời gian thực. Ngoài ra, cả hai thuật toán này đều không xét đến việc lấp đầy khoảng trống và sử dụng khe thời gian $\tau$ cố định.

Tác giả đề xuất mô hình lập lịch nhóm cải tiến và hệ thống bốn giải thuật liên hoàn:

  1. Giải thuật LGS (Linear Group Scheduling): Sắp xếp các chùm đến trong khe $\tau$ theo thứ tự thời điểm kết thúc tăng dần, sau đó áp dụng cơ chế đánh chỉ số (indexing) để chọn tập chùm không chồng lấp với độ phức tạp tính toán giảm xuống mức tuyến tính $O(n \log n)$ do chỉ phụ thuộc vào bước sắp xếp.
  2. Giải thuật LGS-VF: Bổ sung cơ chế lấp đầy khoảng trống (Void-Filling) vào LGS, cho phép các chùm trong nhóm được tận dụng các khoảng băng thông nhàn rỗi nằm giữa các chùm đã lập lịch từ các khe thời gian trước.
  3. Giải thuật LAGS (Load-Adaptive Group Scheduling): Khắc phục nhược điểm của khe thời gian $\tau$ cố định bằng cách thiết lập kích thước $\tau$ biến thiên nghịch biến với tốc độ đến của luồng chùm dữ liệu. Khi tải cao (nhiều chùm đến), $\tau$ tự động co ngắn lại để giảm độ trễ hàng đợi và tránh quá tải bộ xử lý; khi tải thấp, $\tau$ giãn rộng ra để gom đủ số lượng chùm cho việc lập lịch nhóm hiệu quả.
  4. Giải thuật LAGS-VF: Kết hợp đồng thời cơ chế thích ứng tải của LAGS và khả năng khai thác khoảng trống của LGS-VF.

Kết quả mô phỏng trên topo mạng Dumbbell chứng minh:

  • Xác suất mất gói của LGS-VF thấp hơn đáng kể so với LAUC-VF, OBS-GS và MWIS-OS.
  • Thông lượng mạng của LGS-VF vượt trội so với OBS-GS và MWIS-OS.
  • LAGS-VF đạt xác suất mất gói thấp hơn LGS-VF, đồng thời giảm thời gian chờ đợi trung bình của các gói điều khiển trong 7500 chu kỳ lập lịch liên tiếp (khảo sát theo từng khối 500 khe thời gian).
  • Phân bố độ rộng khe thời gian $\tau$ của LAGS-VF biến thiên linh hoạt bám sát sự thay đổi của tải lưu lượng mạng, trong khi MWIS-OS duy trì độ trễ cố định.

Chương 4. MỘT SỐ CẢI TIẾN GIẢI THUẬT LẬP LỊCH NHÓM TRÊN ĐA KÊNH

Chương 4 nghiên cứu môi trường mạng OBS có hỗ trợ chuyển đổi bước sóng hoàn toàn, nơi một chùm đến có thể được chuyển mạch tới bất kỳ kênh bước sóng nào tại cổng ra. Tác giả chỉ ra nhược điểm của giải thuật tối ưu GreedyOPT: bảng thống kê thực nghiệm của luận án cho thấy GreedyOPT phải gỡ bỏ và lập lịch lại một lượng lớn chùm đã được xác nhận trước đó:

Tham số tải mạng / Kịch bản Số chùm bị gỡ ra để lập lịch lại Số chùm lập lịch lại thành công Tỷ lệ xử lý dư thừa của GreedyOPT
Mức tải thấp (Load = 0.2 - 0.4) Ghi nhận trong mô phỏng Phục hồi một phần Làm tăng độ phức tạp xử lý
Mức tải trung bình (Load = 0.5 - 0.7) Tăng cao theo mật độ chùm Tỷ lệ thành công giảm Nguy cơ vi phạm thời gian offset
Mức tải cao (Load = 0.8 - 1.0) Chiếm tỷ trọng lớn trong khe Tắc nghẽn tính toán cục bộ Không khả thi trên mạng thực

Để giải quyết triệt để vấn đề này mà không phá vỡ tính nguyên vẹn của các chùm đã truyền, luận án đề xuất các giải thuật theo hai hướng tiếp cận:

  1. Hướng tiếp cận tối ưu - Giải thuật OPT-GS: Chuyển đổi bài toán lập lịch nhóm đa kênh thành bài toán luồng trên mạng phân tầng. Đồ thị khoảng được xây dựng từ tập các chùm đến và các khoảng trống trên tất cả các kênh ra. Thuật toán tìm tập các clique cực đại, sau đó ánh xạ thành mạng luồng cực đại có chi phí cực tiểu để đưa ra lời giải tối ưu về số lượng hoặc độ dài chùm được lập lịch mà không cần gỡ bỏ các chùm đã được xác nhận.

  2. Hướng tiếp cận Heuristic:

  • LGS-MC và LGS-MC-VF: Mở rộng giải thuật LGS sang môi trường đa kênh, kết hợp lấp đầy khoảng trống để duy trì độ phức tạp tính toán thấp.
  • MWC-GS và MWC-VF-GS: Dựa trên bài toán tìm Clique có trọng số lớn nhất (Maximum Weight Clique). Đồ thị khoảng được thiết lập với trọng số đỉnh là độ dài chùm $l_i$. Giải thuật tìm kiếm MWC để xác định tập hợp các chùm có tổng độ dài lớn nhất chồng lấp tại các lát cắt thời gian, từ đó phân bổ lần lượt lên các kênh bước sóng khả dụng. Biến thể MWC-VF-GS tích hợp thêm việc lấp đầy các khoảng trống nhàn rỗi.

Kết quả thực nghiệm trên mạng Dumbbell và mạng NSFNET-14 nút:

  • Trên cả hai topo, LGS-MC và MWC-GS cho xác suất mất gói thấp hơn rõ rệt so với các giải thuật heuristic kinh điển SSF và LIF.
  • MWC-GS đạt hiệu năng xấp xỉ giải thuật tối ưu GreedyOPT nhưng không gây ra tình trạng gỡ bỏ chùm đã lập lịch.
  • MWC-VF-GS và OPT-GS đạt hiệu năng tương đương hoặc vượt trội so với giải thuật BATCHOPT, đồng thời duy trì độ ổn định khi kích thước khe thời gian $\tau$ thay đổi.

Kết quả và những đóng góp mới

Luận án đã đạt được các đóng góp khoa học mới cả về mặt lý luận lẫn thực tiễn cho bài toán lập lịch trong mạng chuyển mạch chùm quang:

  1. Đóng góp về mặt lý luận và giải thuật:
  • Đề xuất giải thuật lập lịch trực tiếp kết hợp lập lịch lại và phân đoạn chùm iCSA [công trình công bố CT2]: Thiết lập quy trình phối hợp ba giai đoạn đồng bộ, tích hợp kỹ thuật lấp đầy khoảng trống xuyên suốt quá trình lập lịch lại và phân đoạn chùm tranh chấp.
  • Đề xuất giải thuật lập lịch nhóm trên đơn kênh LGS [CT8] cùng ba biến thể cải tiến: LGS-VF [CT4], LAGS [CT5], và LAGS-VF [CT7]. Xây dựng mô hình toán học giảm độ phức tạp tính toán của bài toán lập lịch nhóm đơn kênh và thiết lập cơ chế điều chỉnh độ rộng khe thời gian $\tau$ thích ứng theo tốc độ luồng chùm dữ liệu đến.
  • Đề xuất giải thuật lập lịch nhóm tối ưu trên đa kênh OPT-GS giải quyết bài toán lập lịch đa kênh thông qua mô hình luồng mạng mà không yêu cầu gỡ bỏ các chùm đã lập lịch.
  • Đề xuất hệ thống các giải thuật lập lịch nhóm heuristic trên đa kênh gồm: LGS-MC [CT6], LGS-MC-VF [CT3], MWC-GS [CT1], và MWC-VF-GS [CT1], ứng dụng lý thuyết tìm Clique có trọng số lớn nhất trên đồ thị khoảng để tối ưu hóa việc sử dụng băng thông đa kênh bước sóng.
  1. Đóng góp về mặt thực tiễn và giải pháp đề xuất:
  • Cung cấp gói phần mềm cài đặt hoàn chỉnh các giải thuật đề xuất bằng C++ tích hợp trong nền tảng mô phỏng mạng NS2 và mô-đun obs-0.9a.
  • Chứng minh tính khả thi của việc triển khai các cơ chế lập lịch nhóm thích ứng tải mà không cần can thiệp hay thay đổi cấu trúc giao thức báo hiệu quang hiện hành.
  • Đưa ra khuyến nghị thiết kế bộ lập lịch tại nút lõi OBS: đối với các nút mạng không có bộ chuyển đổi bước sóng, nên áp dụng LAGS-VF để cân bằng giữa thông lượng và độ trễ; đối với các nút mạng trang bị bộ chuyển đổi bước sóng đầy đủ, giải thuật MWC-VF-GS là phương án tối ưu giữa hiệu năng khai thác băng thông và thời gian xử lý của bộ điều khiển chuyển mạch.

Hạn chế và hướng nghiên cứu tiếp

Căn cứ theo phạm vi và nội dung trình bày trong văn bản luận án, các hạn chế và hướng nghiên cứu tiếp theo bao gồm:

  • Phạm vi nghiên cứu mới tập trung chủ yếu vào hoạt động lập lịch và xử lý xung đột tài nguyên tại đơn vị điều khiển chuyển mạch (SCU) của nút lõi OBS, chưa tích hợp đồng thời với bài toán định tuyến và cấp phát bước sóng (RWA) trên toàn mạng.
  • Về điều kiện phần cứng, các giải thuật đa kênh giả định nút mạng được trang bị bộ chuyển đổi bước sóng hoàn toàn (Full Wavelength Conversion). Luận án chưa khảo sát sâu trên các cấu hình phần cứng hạn chế hơn như bộ chuyển đổi bước sóng có phạm vi giới hạn (LRWC - Limited-Range Wavelength Converter) hoặc chuyển đổi cố định.
  • Luận án chưa phân tích chi tiết ảnh hưởng của các mức ưu tiên dịch vụ (QoS) đa cấp đối với các giải thuật lập lịch nhóm cải tiến LGS và MWC-GS.
  • Hướng phát triển tiếp theo được xác định là mở rộng nghiên cứu giải thuật lập lịch thích ứng trong điều kiện mạng OBS có hỗ trợ chất lượng dịch vụ QoS phân tầng, khảo sát trên kiến trúc chuyển đổi bước sóng thưa thớt (sparse conversion), và kết hợp kỹ thuật lập lịch nhóm với định tuyến lệch hướng để nâng cao hiệu năng chống tắc nghẽn toàn cục.

Giá trị tham khảo

Luận án mang lại giá trị tham khảo cụ thể cho các nhóm đối tượng học thuật và kỹ thuật:

  • Nghiên cứu sinh, học viên cao học và giảng viên chuyên ngành Khoa học máy tính, Kỹ thuật viễn thông và Mạng máy tính: Có thể sử dụng Chương 1 làm tài liệu tổng quan hệ thống về mạng chuyển mạch chùm quang, các giao thức báo hiệu (JET, JIT), và mô hình toán học của bài toán lập lịch. Chương 3 và Chương 4 cung cấp phương pháp luận chi tiết về việc ứng dụng lý thuyết đồ thị (đồ thị khoảng, bài toán MWIS, MWC, mạng luồng) để mô hình hóa và giải quyết các bài toán tối ưu phân bổ tài nguyên mạng.
  • Các kỹ sư thiết kế giao thức và kiến trúc mạng truyền tải quang: Có thể tham khảo nguyên lý của giải thuật iCSA (Chương 2) để xây dựng các cơ chế xử lý tranh chấp đa tầng tại các bộ định tuyến quang.
  • Các nhà phát triển hệ thống điều khiển chuyển mạch quang: Có thể ứng dụng trực tiếp thuật toán thích ứng khe thời gian LAGS-VF (Chương 3) và heuristic MWC-VF-GS (Chương 4) vào việc thiết kế phần mềm điều khiển cho các đơn vị xử lý chuyển mạch (SCU) nhằm tối ưu hóa thông lượng truyền dẫn mà không làm tăng chi phí phần cứng quang học.

Câu hỏi thường gặp

1. Tại sao mạng chuyển mạch chùm quang (OBS) được xem là giải pháp thỏa hiệp giữa OCS và OPS?

Trong OCS, việc thiết lập đường quang tĩnh yêu cầu báo hiệu hai chiều tốn thời gian và không tận dụng được băng thông khi lưu lượng thay đổi đột biến. Ngược lại, OPS xử lý ở mức gói tin cho hiệu suất cao nhưng đòi hỏi bộ đệm quang RAM và bộ chuyển mạch tốc độ nano giây—những công nghệ hiện chưa khả thi. OBS dung hòa hai mô hình này bằng cách gom các gói tin thành chùm dữ liệu lớn để truyền toàn quang mà không cần đệm tại nút lõi, đồng thời tách gói điều khiển BHP truyền trước một khoảng thời gian offset trên kênh riêng để đặt trước tài nguyên theo cơ chế một chiều.

2. Điểm cải tiến cốt lõi của giải thuật iCSA so với các giải thuật kết hợp trước đó (ODBR, SODBRA, PCSA) là gì?

Giải thuật iCSA giải quyết các tồn tại của các giải thuật trước bằng cách:

  • Sử dụng giải thuật lập lịch trực tiếp có lấp đầy khoảng trống tối ưu ở giai đoạn 1 (thay vì dùng FFUC-VF kém tối ưu như SODBRA).
  • Ở giai đoạn lập lịch lại (giai đoạn 2), iCSA tìm kiếm khoảng trống khả dụng trên nhiều kênh thay vì chỉ xem xét chùm sau cùng nhất trên kênh như ODBR.
  • Ở giai đoạn phân đoạn chùm (giai đoạn 3), đoạn chùm bị tranh chấp không bị hủy bỏ ngay mà tiếp tục được đưa vào quy trình tìm kiếm khoảng trống trên các kênh khác, giúp giảm thiểu tối đa lượng dữ liệu bị mất mát.

3. Nguyên lý thích ứng của khe thời gian $\tau$ trong giải thuật LAGS hoạt động như thế nào?

Giải thuật LAGS điều chỉnh độ rộng khe thời gian lập lịch nhóm $\tau$ nghịch biến với tốc độ đến của luồng chùm dữ liệu. Khi mật độ chùm đến cao, giá trị $\tau$ tự động co ngắn lại để thực hiện lập lịch sớm, tránh tích lũy quá nhiều chùm gây trễ hàng đợi và tắc nghẽn bộ xử lý. Khi lưu lượng đến thưa thớt, $\tau$ tự động kéo dài ra để gom đủ số lượng chùm cho việc lập lịch nhóm, đảm bảo tính hiệu quả trong việc tối ưu hóa sắp xếp kênh.

4. Giải thuật tối ưu OPT-GS trong Chương 4 khắc phục điểm yếu nào của giải thuật GreedyOPT?

Giải thuật GreedyOPT yêu cầu gỡ bỏ toàn bộ các chùm đã được lập lịch trên các kênh để đưa bài toán về dạng lập lịch trên máy đồng nhất, gây ra khối lượng tính toán dư thừa lớn, làm tăng số lượng gói điều khiển và không khả thi khi triển khai trên mạng thực tế vì chùm dữ liệu có thể đã và đang truyền trên sợi quang. OPT-GS khắc phục hoàn toàn nhược điểm này bằng cách giữ nguyên trạng thái các chùm đã lập lịch, xây dựng đồ thị khoảng kết hợp với các khoảng trống hiện hữu và chuyển đổi thành bài toán tìm luồng trên mạng phân tầng để tìm phương án lập lịch tối ưu cho nhóm chùm mới đến.

5. Những công cụ phần mềm và topo mạng nào được tác giả sử dụng trong quá trình nghiên cứu thực nghiệm?

Tác giả sử dụng hệ mô phỏng mạng mã nguồn mở NS2 (Network Simulator 2) kết hợp với gói phần mềm mở rộng chuyên dụng obs-0.9a. Toàn bộ các thuật toán lập lịch đề xuất được lập trình cài đặt bằng ngôn ngữ C++. Các kịch bản kiểm thử hiệu năng được thực hiện trên hai mô hình topo mạng chuẩn: mạng hình quả tạ (Dumbbell topology) và mạng NSFNET phiên bản 14 nút mạng.

Kết luận

Luận án tiến sĩ của tác giả Nguyễn Hồng Quốc đã giải quyết bài toán nâng cao hiệu năng lập lịch đặt trước tài nguyên tại các nút lõi của mạng chuyển mạch chùm quang (OBS). Thông qua việc kết hợp chặt chẽ giữa lý thuyết lập lịch công việc, lý thuyết đồ thị khoảng và mô phỏng thực nghiệm trên công cụ NS2/obs-0.9a, tác giả đã đề xuất thành công các giải thuật mới gồm iCSA cho mô hình lập lịch kết hợp, hệ thống giải thuật LGS/LAGS cho lập lịch nhóm trên đơn kênh, và các giải thuật OPT-GS/MWC-GS cho lập lịch nhóm trên đa kênh. Các kết quả nghiên cứu đã chứng minh khả năng giảm thiểu xác suất mất gói tin, tối ưu hóa hiệu suất sử dụng băng thông và hạ thấp độ phức tạp tính toán, đóng góp thiết thực cho quá trình phát triển các giải pháp điều khiển chuyển mạch trong mạng Internet toàn quang thế hệ tiếp theo.