MỘT HƯỚNG TIẾP CẬN LẬP LỊCH NHÓM TỐI ƯU TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG

Tạp chí Khoa học Đại học Huế: Kỹ thuật và Công nghệ; pISSN 2588-1175 | eISSN 2615-9732 Tập 132, Số 2A, 2023, Tr. 5–21; DOI: 10.26459/hueunijtt.v132i2A.7363 * Liên hệ: nhquoc@hueuni.edu.vn Ngày nhận bài: 24–11–2023; Ngày nhận đăng: 14–12–2023 MỘT HƯỚNG TIẾP CẬN LẬP LỊCH NHÓM TỐI ƯU TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG Nguyễn Hồng Quốc1*, Nguyễn Thị Hồng Luyến2, Lê Văn Hòa3, Võ Hồ Thu Sang1 1 Trường Đại học Sư phạm, Đại học Huế, Việt Nam 2 Trường Đại học Nội vụ Hà Nội, Việt Nam 3Trường Du lịch - Đại học Huế, Việt Nam Tóm tắt. Lập lịch là một trong những hoạt động quan trọng trong mạng chuyển mạch chùm quang. Khi gói điều khiển của một chùm đến tại một nút lõi mạng, dựa vào thông tin được chứa trong gói điều khiển như thời điểm đến, thời điểm kết thúc của chùm, một giải thuật lập lịch sẽ được gọi để tìm kênh bước sóng ra khả dụng cho việc lập lịch chùm đến. Mục đích chính của giải thuật lập lịch là sắp xếp các chùm đến trên các kênh bước sóng ra sao cho tối đa hiệu suất sử dụng băng thông và giảm mất mát chùm. Trong bài báo này chúng tôi đề xuất một giải thuật lập lịch nhóm MF_GS nhằm tối ưu kết quả lập lịch trong mỗi khe thời gian chờ lập lịch. Qua phân tích và đánh giá từ kết quả mô phỏng, giải thuật được đề xuất mới đã khẳng định được ưu điểm, đó là giảm xác suất mất gói tin và giảm độ phức tạp của giải thuật. Từ khoá: mạng OBS, lập lịch nhóm, hiệu suất sử dụng băng thông, tỉ lệ mất mát chùm. A optimal approach to group scheduling in optical burst switching networks Nguyen Hong Quoc1*, Nguyen Thi Hong Luyen2, Le Van Hoa3, Vo Ho Thu Sang1

1 University of Education, Hue University, Vietnam 2 Hanoi University of Home Affairs, Vietnam 3 School of Hospitality and Tourism - Hue University, Vietnam Abstract. Scheduling is one of the crucial activities in the optical burst switching network. When the control packet of a burst arrives at a core network node, relying on information contained in the control packet, such as burst arrival time and end time, a scheduling algorithm is invoked to find an available wavelength channel for scheduling the incoming burst. The primary goal of the scheduling algorithm is to arrange incoming bursts on wavelength channels to maximize bandwidth utilization and minimize burst loss. This paper proposes a scheduling algorithm called MF_GS to optimize the scheduling efficiency.

Nguyễn Hồng Quốc và CS. Tập 132, Số 2A, 2023 6 The advantages of this new proposed algorithm have been affirmed through analysis and evaluations based on simulation results. Keywords: OBS network, group scheduling, bandwidth utilization, burst loss ratio 1 Giới thiệu Kỹ thuật ghép kênh phân chia theo bước sóng (Wavelength Division Multiplexing - WDM) đã trở thành giải pháp tốt nhất cho các đường trục truyền thông của các mạng truyền dữ liệu để khai thác hiệu quả băng thông của sợi quang. Chuyển mạch gói luôn là mô hình truyền thông được mong muốn nhất đối với các nhà phát triển mạng. Nhưng do một số giới hạn về công nghệ, chuyển mạch chùm quang (Optical Burst Switching - OBS) là mô hình chuyển mạch gói quang khả thi nhất cho đến nay [12] [18]. Một đặc trưng của mạng OBS là gói điều khiển (Burst Header Packet - BHP) tách rời với phần dữ liệu của nó (chùm dữ liệu, burst) về mặt không gian và thời gian, tức là gói điều khiển sẽ được gửi đi trước trên một kênh điều khiển, tách rời với kênh dữ liệu và thực hiện đặt trước tài nguyên cho chùm của nó tại các nút lõi mạng. Hoạt động đặt trước tài nguyên của một gói điều khiển khi đến tại một nút trung gian thực chất là việc thực hiện một giải thuật lập lịch cho chùm dữ liệu đi sau gói điều khiển trên một kênh bước sóng ra. Lập lịch là một trong những hoạt động quan trọng trong mạng chuyển mạch chùm quang. Khi gói điều khiển của một chùm đến tại một nút lõi mạng, dựa vào thông tin được chứa trong gói điều khiển như thời điểm đến, thời điểm kết thúc của chùm, một giải thuật

lập lịch sẽ được gọi để tìm kênh bước sóng ra khả dụng cho việc lập lịch chùm đến. Mục đích chính của giải thuật lập lịch là sắp xếp các chùm đến trên các kênh bước sóng ra, nhằm tối đa hiệu suất băng thông sử dụng, giảm số lượng chùm bị loại bỏ và nâng cao hiệu suất hoạt động của mạng OBS. Hiện đã có nhiều giải thuật lập lịch được đề xuất và có thể phân loại chúng thành hai nhóm tiếp cận chính: lập lịch trực tiếp [3] và lập lịch nhóm [7]. Đối với lập lịch trực tiếp, khi một gói điều khiển đến một nút lõi mạng, một giải thuật lập lịch trực tiếp sẽ được gọi để tìm kênh bước sóng khả dụng lập lịch cho chùm của nó; nếu có nhiều hơn một kênh bước sóng khả dụng, giải thuật lập lịch này sẽ chọn một kênh lập lịch mà tối ưu tiêu chí đặt ra của giải thuật. Tuy nhiên giải lập lịch trực tiếp chỉ quan tâm đến hiệu quả của việc lập lịch chùm hiện thời, mà không xem xét đến những tác động của nó đến tình trạng tài nguyên cho những lần lập lịch sau. Kết quả là băng thông trên các kênh dữ liệu ra bị phân mảnh và việc sử dụng băng thông của các kênh trở nên không hiệu quả. Một giải pháp cho vấn đề nêu trên là lập lịch nhóm, trong đó các gói điều khiển đến trong mỗi khe thời gian  sẽ tiến hành lập lịch đồng thời cho các chùm tương ứng của chúng. Như đã được chứng minh trong [4] [5] [17], lập lịch nhóm hiệu quả hơn lập lịch trực tiếp dựa trên số chùm bị loại bỏ giảm, mức độ khai thác băng thông tốt hơn và giảm xác suất mất mát dữ

jos.hueuni.edu.vn Tập 132, Số 2A, 2023 7 liệu trên toàn mạng. Hiện đã có một số giải thuật lập lịch nhóm được đề xuất mà chúng có thể được chia thành 2 nhóm: hướng tiếp cận heuristic bao gồm SSF (Smallest Start-time First), LIF (Largest Interval First), SLV (Smallest-Last Vertex) và MCF (Maximal Cliques First) [7]; LGS-MC (Linear Group Scheduling for Multi Channel) [10], MWC-GS (Maximum Weight Clique - Group Scheduling) [17] và hướng tiếp cận tối ưu lập lịch với việc xem xét bài toán lập lịch nhóm trong mạng OBS như bài toán lập lịch trên máy đồng nhất bao gồm GreedyOPT (Gready Optimization) [4], BATCHOPT (Batch Optimization) [5] và OPT-GS (Optimal Group Scheduling) [13]. Các giải thuật lập lịch nhóm theo hướng heuristic có độ phức tạp giải thuật thấp do chỉ dựa trên cách sắp xếp các chùm trước khi thực hiện lập lịch tuần tự, nhưng chúng chưa đạt được kết quả lập lịch tối ưu; trong khi các giải thuật theo hướng tiếp cận tối ưu, như GreedyOPT, BATCHOPT và OPT-GS phải chịu một độ phức tạp lớn về mặt tính toán, hệ thống phải có những thay đổi trong giao thức trong đặt trước lại tài nguyên, số gói điều khiển tăng lên, các nút mạng OBS phải thực hiện nhiều xử lý hơn và tranh chấp tài nguyên do đó sẽ tăng thêm. Ngoài ra việc gỡ tất cả các chùm đã được lập lịch trên các kênh là không thực tế ở trên mạng thật. Trong nghiên cứu này chúng tôi đề xuất một giải thuật lập lịch nhóm tối ưu kết quả lập lịch và giảm được độ phức tạp giải thuật. Cấu trúc tiếp theo của bài viết như sau: Phần II trình bày các nghiên cứu liên quan đến

các công bố, Phần III mô tả giải thuật lập lịch nhóm đề xuất; Phần IV mô phỏng đánh giá giải thuật lập lịch nhóm đề xuất và Phần V là phần kết luận. 2 Một số nghiên cứu liên quan Đã có một số giải thuật lập lịch được công bố nhằm giải quyết bài toán lập lịch nhóm trên đa kênh theo 2 hướng tiếp cận: tối ưu hoá lập lịch [4], [5] [13] hoặc sử dụng giải pháp heuristic [7] [10] [17] để giảm độ phức tạp của giải thuật. Nhóm giải thuật lập lịch heuristic được đề xuất trong [7] [10] [17] bao gồm các giải thuật SSF, LIF, SLV, MCF, LGS-MC và MWC-GS. Nhóm giải thuật lập lịch nhóm theo hướng tiếp cận tối ưu kết quả lập lịch được các tác giả trong [4], [5] đề xuất gồm hai giải thuật GreedyOPT và BATCHOPT. Ý tưởng của hai giải thuật này chuyển từ bài toán S-NIM thành S-IM bằng cách gỡ hết các chùm đã lập lịch trước đó và lập lịch lại chúng đồng thời với các chùm mới đến, với hi vọng sẽ lập lịch được kết quả tốt hơn. Bên cạnh đó các tác giả trong [13] đề xuất giải thuật lập lịch nhóm tối ưu OPT_GS nhằm tìm ra tập các chùm có độ dài lớn nhất để lập lịch trên các kênh. Trong [7] tác giả đề xuất giải thuật SSF với 𝑛 gói điều khiển đến trong khe thời gian 𝜏 yêu cầu lập lịch cho n chùm theo sau tương ứng, giải thuật SSF tiến hành sắp xếp thứ tự không giảm theo thời điểm đến của các chùm. Sau đó giải thuật LAUC-VF (Latest Available Unused

Nguyễn Hồng Quốc và CS. Tập 132, Số 2A, 2023 8 Channel with Void Filling) được gọi để tìm kênh khả dụng lập lịch lần lượt cho các chùm theo thứ tự này; nếu việc lập lịch không thành công, chùm tranh chấp bị loại bỏ. Tương tự như SSF, giải thuật LIF sắp xếp thứ tự không tăng về độ dài của các chùm đến. Sau đó giải thuật LAUC-VF được gọi tìm kênh khả dụng để lập lịch lần lượt cho các chùm đã được sắp xếp theo thứ tự trên; nếu việc lập lịch không thành công, chùm tranh chấp bị loại bỏ. Trong giải thuật SLV, đầu tiên một đồ thị khoảng G được xây dựng và các chùm đến được sắp xếp theo thứ tự không tăng của bậc các đỉnh tương ứng. Dựa trên kết quả sau khi sắp xếp, các chùm tương ứng với đỉnh trong đồ thị được phân phối lên kênh khả dụng đầu tiên trong số 𝑚 kênh ra bằng cách sử dụng giải thuật LAUC-VF. Tiến trình lập lịch được lặp đi lặp lại đối với mỗi chùm lên từng kênh ra hoặc bị loại bỏ (nếu không lập lịch được) cho đến khi không còn đỉnh nào trong danh sách. Tương tự SLV, giải thuật MCF cũng dựa trên đồ thị khoảng được xây dựng với 𝑚 kênh để lập lịch cho 𝑛 chùm đến. Ý tưởng của MCF là: đầu tiên sẽ tìm tất cả các clique cực đại có kích thước lớn hơn m và tập chứa các clique này là 𝐶 = {𝐶1, 𝐶2, . . . , 𝐶𝑚}; với mỗi clique cực đại có thời điểm đến sớm nhất 𝐶𝑖 ∈ 𝐶, MCF lần lượt loại bỏ các đỉnh có thời điểm kết thúc nhỏ nhất cho đến khi kích thước của 𝐶𝑖 bằng hoặc nhỏ hơn 𝑚. Việc loại bỏ các đỉnh rõ ràng sẽ làm thay đổi đến các clique cực đại khác trong C, nên giải thuật MCF lặp lại việc xác định tập C và thực hiện loại bỏ một số

đỉnh của clique cực đại có kích thước lớn hơn m. Giải thuật MCF sẽ dừng khi không còn clique cực đại nào có kích thước lớn hơn 𝑚. Kết quả của giải thuật MCF là danh sách các đỉnh 𝐿 = {𝑏1, 𝑏2, . . . , 𝑏𝑖} mà bậc của chúng không lớn hơn 𝑚 − 1, được nối với danh sách các chùm bị loại bỏ trong các clique có kích thước lớn hơn 𝑚, ký hiệu là 𝑆 = {𝑏𝑖 +1, 𝑏𝑖 +2, . . . , 𝑏𝑛}. Kết quả là 𝐼0 = 𝐿 ∪ 𝑆. Các chùm tương ứng với các đỉnh trong 𝐼0 sau đó lần lượt được phân phối lên m kênh ra theo giải thuật LAUC-VF hoặc bị loại bỏ nếu không lập lịch được cho đến khi không còn đỉnh nào trong danh sách. Một hướng tiếp cận khác của các tác giả trong [10] đã đề xuất giải thuật lập lịch nhóm LGS-MC đây là một mở rộng từ giải thuật lập lịch nhóm trên đơn kênh LGS của nhóm tác giả trong [11] với ý tưởng sắp xếp các kênh theo giá trị LAUT (Latest Available Unscheduled Time), nhằm mục đích với kênh có giá trị LAUT nhỏ nhất là kênh có thể lập lịch được các chùm có tổng độ dài là lớn nhất. Trên mỗi kênh thực hiện gọi giải thuật LGS để lập lịch cho tập các chùm trên kênh đó. Giải thuật dừng lại khi số chùm được lập lịch hết, hoặc lập lịch hết trên m kênh. Đối với giải thuật LGS-MC có độ phức tạp giải thuật thấp (𝑂(𝑛 × 𝑙𝑜𝑔2(𝑛)).), tuy nhiên chỉ tối ưu lập lịch trên từng kênh một nên không có kết quả tối ưu toàn cục. Các tác giả trong [17] đã đề xuất giải thuật MWC-GS. Ý tưởng giải thuật MWC-GS là mô hình hoá bài toán lập lịch nhóm trên đa kênh sang bài toán tìm clique cực đại có tổng trọng số

lớn nhất trên đơn đồ thị khoảng có trọng số. Bước đầu tiên của giải thuật là xây dựng đơn đồ thị khoảng có trọng số tương ứng khả năng lập lịch của các chùm trên các kênh. Trong đó mỗi đỉnh tương ứng một chùm lập lịch được trên một kênh thứ 𝑘 và trọng số trên các đỉnh chiều dài của chùm đó; Có một cạnh nối giữa hai đỉnh, khi và chỉ khi: Hai chùm được lập lịch trên cùng

jos.hueuni.edu.vn Tập 132, Số 2A, 2023 9 một kênh có thời gian đến không chồng lấp nhau. Hoặc được lập lịch trên hai kênh khác nhau. Từ đồ thị được xây dựng, Giải thuật sẽ tìm tập các clique cực đại bắt đầu từ các cạnh trong đồ thị 𝐺 và thực hiện tính tổng trọng số. Các đỉnh trong clique cực đại có tổng trọng số lớn nhất trong tập các clique được tìm thấy chính là tập các chùm lập lịch trên các kênh ra có tổng chiều dài các chùm lập lịch là lớn nhất. Các tác giả trong [4] đã đề xuất giải thuật GreedyOPT với cách tiếp cận là xây dựng vấn đề lập lịch nhóm các chùm đến dưới dạng vấn đề lập lịch công việc trên các máy đồng nhất. Để làm được điều này GreedyOPT gỡ các chùm đã được lập lịch trước đó trên các kênh ra và sử dụng giải thuật lập lịch LAUC để thực hiện lập lịch lại chúng cùng với các chùm mới đến trong khe thời gian 𝜏. Nếu một chùm không thể lập lịch được, giải thuật sẽ cố gắng thay chùm đó bằng một trong những chùm đã được lập lịch mà có thời điểm kết thúc sau cùng nhất. Mục đích của việc làm này nhằm tìm kiếm cơ hội lập lịch cho chùm đang xem xét, cũng như các chùm đến sau (có thời điểm đến lớn hơn) nhằm giảm lượng dữ liệu (số gói tin chứa trong chùm) bị loại bỏ. Theo một hướng tiếp cận khác các tác giả trong [5] đề xuất giải thuật nhóm BATCHOPT lấy ý tưởng từ giải thuật lập lịch công việc [4], tức là xây dựng vấn đề lập lịch nhóm các chùm đến thành vấn đề lập lịch công việc trên k máy đồng nhất cho cả các chùm đã được lập lịch trước đó nhưng chưa được gửi đi. Giải thuật BATCHOPT tiến hành xây dựng một đồ thị

khoảng vô hướng tương ứng các chùm mới đến và các chùm đã được lập lịch trước đó bị gỡ ra được xây dựng. Tiếp đó giải thuật tìm tất cả các clique cực đại của đồ thị và sắp xếp chúng theo thời điểm đến tăng dần. Một đồ thị luồng sau đó được tạo ra dựa trên các clique cực đại đã được sắp xếp, trong đó mỗi cung được đặc trưng bởi các tham số: chi phí, khả năng thông qua và trọng số (độ dài chùm). Cuối cùng BATCHOPT tìm luồng có chi phí tối thiểu rồi loại bỏ các cung của nó. Trong [13] các tác giả đã để xuất giải thuật lập lịch nhóm tối ưu OPT-GS với ý tưởng của giải thuật là mô hình hoá bài toán lập lịch nhóm trên đa kênh sang bài toán tìm tập các đường đi trên đơn đồ thị khoảng có hướng có trọng số. Để thực hiện việc này, Đầu tiên từ tập các chùm đến yêu cầu lập lịch, giải thuật sẽ xây dựng đồ thị tương ứng. Ở đây mỗi chùm 𝑏𝑖 tương ứng mỗi đỉnh 𝑖 và trọng số của đỉnh chính là độ dài của chùm đó. Có một cung đi từ đỉnh 𝑖 đến đỉnh 𝑗 khi và chỉ khi: thời điểm kết thúc của chùm 𝑏𝑖 nhỏ hơn chùm 𝑏𝑗, và thời gian đến của hai chùm này không chồng lấp nhau. Và không tồn tại một chùm khác xen giữa 2 chùm đó mà thời gian đến của 3 chùm ko chồng lấp nhau. Từ cách xây dựng đồ thị như vậy một đường đi từ một đỉnh không có bậc vào đến 1 đỉnh ko có bậc ra, thì tập các đỉnh trên đường đi chính là tập các chùm có thể lập lịch cùng nhau trên kênh ra đó. Từ tập các đường đi được tìm thấy. Giải thuật thực hiện hợp m được đi trên m kênh và tính tổng trọng số các đỉnh. Kết quả của giải thuật, lập lịch cho các chùm tương ứng các đỉnh trong tập có tổng trọng số lớn nhất.

nhau([𝑠𝑖 , 𝑒𝑖 ] ∩ [𝑠𝑗 , 𝑒𝑗] = ∅). Vấn đề là tìm tập các chùm 𝐼0 ⊆ 𝐼 có thể lập lịch cùng nhau trên 𝑚 kênh ra có tổng độ dài các chùm được lập lịch là lớn nhất Mô hình đề xuất thực hiện như mô tả ở Hình 1: Khi các gói điều khiển đến trong mỗi khe thời gian sẽ được đưa vào một hàng đợi lập lịch cùng nhau. Sau khi hết thời gian chờ, lúc này thực hiện gọi giải thuật lập lịch để lập lịch cho tất cả các chùm tương ứng các gói điều khiển trong hàng trên tất cả các kênh ra. Ví dụ: Xét một tập có 6 gói điều khiển {𝐵𝐻𝑃1, 𝐵𝐻𝑃2, 𝐵𝐻𝑃3, 𝐵𝐻𝑃4, 𝐵𝐻𝑃5, 𝐵𝐻𝑃6} đến trong khe thời gian  , như Hình 1. (a), yêu cầu lập lịch cho 6 chùm tương ứng 𝐼 = {𝑏1, 𝑏2, 𝑏3, 𝑏4, 𝑏5, 𝑏6}, độ dài của các chùm lần lượt là: 𝑙1 = 3, 𝑙2 = 4, 𝑙3 = 3, 𝑙4 = 5, 𝑙5 = 6, 𝑙6 = 4 trên hai kênh dữ liệu ra với giá trị 𝐿𝐴𝑈𝑇1 và 𝐿𝐴𝑈𝑇2 tương ứng.

jos.hueuni.edu.vn Tập 132, Số 2A, 2023 11 Cổng vào Cổng ra Thời gian chờ Các BHP đến Hàng đợi Lập lịch Kênh dữ liệu ra 1 Các giai đoạn của mô hình lập lịch nhóm (a) (b) Kênh dữ liệu ra m Hình 1. Mô tả các giai đoạn của mô hình lập lịch nhóm Các bước thực hiện của Giải thuật lập lịch được thể hiện như sau: Bước 1: Xây dựng mạng 𝐺 = (𝑉, 𝐸) từ tập các chùm tới lập lịch và tập các kênh ra, trong đó tất cả luồng và khả năng thông qua của các cung được khởi tạo lần lượt là 0 và 1. Ví dụ, giả sử có 6 chùm đến lập lịch và 2 kênh ra (xem Hình 2), mạng 𝐺 được xây dựng như Hình 3. BHP1 BHP6 Khe thời gian  LAUT1 b1(3) Kênh điều khiển w1 b4(3) b6(4) b2(4) b3(5) b5(6) LAUT2 LAUT1 LAUT2 w2 w1 w2 b1(3) b5(6) b3(5) b6(4) (a) (b) Hình 2. (a) Một ví dụ về tình trạng các chùm đến yêu cầu lập lịch hai kênh dữ liệu ra và (b) kết quả lập lịch tối ưu các chùm trên hai kênh ra

Nguyễn Hồng Quốc và CS. Tập 132, Số 2A, 2023 12 S b1 b3 b6 w1 b5 b2 b4 Luồng Khả năng thông qua FS,bi=0 CS,bi=1 w2 T Fbi,wj=0 Cbi,wj=1 Fw1,T=0 Cw1,T=6 Fw2,T=0 Cw1,T=5 Luồng Khả năng thông qua Hình 3. Mạng 𝐺 = (𝑉, 𝐸) được xây dựng từ tập 6 chùm đến lập lịch và 2 kênh ra; trong đó, đỉnh 𝑏𝑖 tương ứng với chùm đến thừ i, đỉnh 𝑤𝑖 tương tương với kênh thứ 𝑖, và 𝑠, 𝑡 là hai đỉnh ảo được thêm vào cho chức năng đỉnh phát và đỉnh thu Bước 2: Tìm luồng cực đại trên mạng 𝐺. Các bước thực hiện như thể hiện ở Hình 4 a, b, c và kết quả tìm được đường tăng luồng lớn nhất 𝐿 = 𝐿1 ∪ 𝐿2; Bước 3: Lập lịch các chùm trong tập 𝐿 = 𝐿1 ∪ 𝐿2; Giải thuật lập lịch được mô tả như sau: Giải thuật MF_GS (Maximum Flow Group Scheduling) Đầu vào: - Tập 𝑛 chùm cần lập lịch 𝐼 = {𝑏1, 𝑏2, … , 𝑏𝑛 }, trong đó mỗi 𝑏𝑖 = (𝑠𝑖, 𝑒𝑖) với 𝑠𝑖 biểu diễn thời điểm đến và 𝑒𝑖 biểu diễn thời điểm kết thúc của chùm 𝑖 (𝑖 = 1,2, … 𝑛); - Tập 𝑊 kênh dữ liệu ra 𝑊 = {𝑤1, 𝑤2, … , 𝑤𝑚}; Đầu ra: - 𝐼′ (𝐼′ ⊆ 𝐼) là tập các chùm được lập lịch trên các kênh ra sao cho tổng độ dài các chùm trong tập 𝐼’ là lớn nhất. Giải pháp: Bước 1: Xây dựng mạng 𝐺 = (𝑉, 𝐸); 𝐺(𝑉, 𝐸) = 𝑐𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝐺𝑟𝑎𝑝ℎ(𝐼, 𝑊) Bước 2: Tìm đường tăng luồng từ đỉnh phát 𝑠 đến đỉnh thu 𝑡; 𝐿 = 𝐹𝑀𝐹_𝑂𝑃𝑇(𝐺) Bước 3: Lập lịch các chùm trong tập 𝐿; 𝐼’ = 𝑠𝑐ℎ𝑒𝑑𝑢𝑙𝑒𝐵𝑢𝑟𝑠𝑡𝑠𝑓𝑟𝑜𝑚𝑀𝑊𝐶(𝐿) Bước 4: Kết thúc;

jos.hueuni.edu.vn Tập 132, Số 2A, 2023 13 1. Xây dựng mạng 𝑮 = (𝑽, 𝑬) như sau: • Tập các đỉnh 𝑉 = {𝐼} ∪ {𝑊} ∪ { 𝑆, 𝑇}, trong đó, 𝐼 là tập các chùm, 𝑊 là tập các kênh, 𝑆 là đỉnh phát, và 𝑇 là đỉnh thu. • Tập các cạnh 𝐸 = {(𝑆, 𝑏𝑖=1:𝑛), (𝑤𝑗=1:𝑚, 𝑇)} ∪ {(𝑏𝑖 , 𝑤𝑗)| 𝑠𝑖 ≥ 𝐿𝑎𝑢𝑡𝑤𝑗 ; ∀𝑏𝑖 ∈ 𝐼, 𝑤𝑗 ∈ 𝑊} • Khả năng thông qua của các cung của 𝐺 được khởi tạo như sau: 𝑐𝑆,𝑖 = 1, 𝑐𝑖,𝑗 = 1, 𝑐𝑗,𝑇 = deg−(𝑤𝑗 ); ; trong đó deg−(𝑤𝑗) là tổng số các cung đi vào đỉnh 𝑤𝑗 , 𝑖 = 1,2, … , 𝑛 và 𝑗 = 1,2, … , 𝑚. • Luồng trên tất cả các cung của 𝐺 được khởi tạo bằng 0. S b1 b3 b6 w1 b5 b2 b4 w2 T F=1 L1={b1} L2= Æ S b1 b3 b6 w1 b5 b2 b4 w2 T F=1 L1={b2} L2= Æ (a) (b) S b1 b3 b6 w1 b5 b2 b4 w2 T F=1 L1={b1,b5} f=1 L2={b3, b6} (c) Hình 4. Các bước tìm đường tăng luồng trên mạng 𝐺 = (𝑉, 𝐸) Hình 5. mô tả mạng 𝐺, luồng (flow) và khả năng thông qua (capacity) của nó. Sau khi có mạng 𝐺, bài toán lập lịch nhóm có thể được giải quyết bằng việc tìm luồng cực đại trên 𝐺. Giả sử

Nguyễn Hồng Quốc và CS. Tập 132, Số 2A, 2023 14 𝑓 là một luồng trên mạng 𝐺 thì luồng cực đại 𝑓∗ cần tìm được định nghĩa bởi công thức bên dưới. 𝑓∗ = 𝑓 𝑎𝑟𝑔𝑚𝑎𝑥 ∑ ∑ (𝑒𝑖 − 𝑠𝑖)𝑓𝑖,𝑗 𝑏𝑖∈𝐿𝑗 𝑚 𝑗=1 (1) trong đó 𝐿𝑗 = {𝑏𝑖 |𝑓𝑖,𝑗 = 1} là tập các đỉnh 𝑏𝑖 có luồng đến 𝑤𝑗 bằng 1; chú ý, 𝐿𝑗 có thể bằng rỗng trong quá trình tìm luồng cực đại. Hình 5. Mạng G cùng với các giá trị luồng và khả năng thông qua ban đầu của nó Chi tiết giải thuật như sau: Function 𝑐𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝐺𝑟𝑎𝑝ℎ(𝐼, 𝑊); Input: - Tập 𝑛 chùm cần lập lịch 𝐼 = {𝑏1, 𝑏2, … , 𝑏𝑛}, trong đó mỗi 𝑏𝑖 = (𝑠𝑖, 𝑒𝑖) với 𝑠𝑖 và 𝑒𝑖 lần lượt là thời điểm đến và kết thúc của chùm i; - Tập 𝑊 kênh dữ liệu ra 𝑊 = {𝑤1, 𝑤2, … , 𝑤𝑚}; Output: 𝑮 = (𝑽, 𝑬) Process Khởi tạo đỉnh phát 𝑆 và đỉnh thu 𝑇 ; 𝐸 = ∅; foreach 𝑏𝑖 ∈ 𝐼 do Tạo đỉnh 𝑏𝑖, 𝑉 = 𝑉 ∪ {𝑏𝑖}; Tạo cung từ đỉnh 𝑆 đến đỉnh 𝑏𝑖, 𝐸 = 𝐸 ∪ {(𝑆, 𝑏𝑖)}, 𝑐𝑆,𝑖 = 1; deg−(𝑤𝑗 ) = 0; foreach 𝑤𝑗 ∈ 𝑊 do Tạo đỉnh 𝑤𝑗 , 𝑉 = 𝑉 ∪ {𝑤𝑗 };

jos.hueuni.edu.vn Tập 132, Số 2A, 2023 15 Tạo cung 𝑤𝑗 đến đỉnh thu 𝑇, 𝐸 = 𝐸 ∪ {(𝑤𝑗, 𝑇)}; if (𝑠𝑖 > 𝐿𝑎𝑢𝑡𝑤𝑗 ) then Tạo cung từ 𝑏𝑖 đến kênh 𝑤𝑗 , 𝐸 = 𝐸 ∪ {(𝑏𝑖, 𝑤𝑗 )}; deg−(𝑤𝑗) = deg−(𝑤𝑗); 𝑐𝑖,𝑗 = 1; 𝑐𝑗,𝑇 = deg−(𝑤𝑗); return 𝑮 = (𝑽, 𝑬); 2. Tìm đường tăng luồng: Sau khi mạng 𝐺 = (𝑉, 𝐸) được xây dựng thực hiện các cộng việc sau. • Đường tăng luồng là đường đi từ 𝑆 đến 𝑇 sao cho làm tăng giá trị lát cắt 𝐶 = (𝑉 − {𝑇}, {𝑇}), giá trị này được tình theo công thức dưới đây: 𝑉𝑎𝑙𝑢𝑒(𝐶) = ∑ ∑ (𝑒𝑖 − 𝑠𝑖)𝑓𝑖,𝑗 𝑏𝑖∈𝐿𝑗 𝑚 𝑗=1 (2) • Tăng luồng lên một đơn vị trên cung (𝑢, 𝑣) cần thảo mãn các điều kiện tăng luồng trên mạng 𝐺 như sau: − Có thể tăng luồng: 𝑓𝑢,𝑣 < 𝑐𝑢,𝑣 đối với tất cả các cung (𝑢, 𝑣); − Cân bằng luồng: Nếu cung (𝑢, 𝑣) là cung nối hai đỉnh 𝑏𝑖 và 𝑤𝑗 thì giảm luồng trên các cung (𝑏𝑘, 𝑤𝑗 ), (𝑠, 𝑏𝑘) trong đó 𝑏𝑘 là đỉnh thuộc 𝐿𝑗 và chồng lấp với 𝑏𝑖 (chồng lấp của hai đỉnh thuộc 𝐼 chính là chồng lấp của hai chùm tương ứng). Để tìm các đỉnh 𝑏𝑘 chúng tôi sử dụng phương pháp tìm kiếm nhị phân. Nếu luồng tới đỉnh 𝑤𝑗 được tăng hoặc giảm thì cập nhật lại danh sách 𝐿𝑗. Chi tiết giải thuật như sau: Function 𝐹𝑀𝐹_𝑂𝑃𝑇(𝐺): Input: Mạng 𝐺 = (𝑉, 𝐸); Output: Tập các đỉnh trong 𝐿𝑗 với mọi 𝑗 thuộc 𝑊; Process Khởi tạo 𝐺′ = 𝐺 và 𝑓𝑢,𝑣 = 0 với mọi 𝑢, 𝑣 ∈ 𝑉; 𝐿𝑗 = ∅ với mọi 𝑗 thuộc 𝑊; 𝑉𝑎𝑙𝑢𝑒 = 0; Do 𝑃𝑎𝑡ℎ = ∅; foreach 𝑖, 𝑗 ∈ 𝑉 − {𝑆, 𝑇} do if (𝑓𝑆,𝑖 < 𝑐𝑆,𝑖) ∧ (𝑓𝑖,𝑗 < 𝑐𝑆,𝑗) ∧ (𝑓𝑗,𝑇 < 𝑐𝑗,𝑇) then 𝑅 = {𝑘} trong đó 𝑏𝑘 ∈ 𝐿𝑗 và chồng lấp với 𝑏𝑖;

Nguyễn Hồng Quốc và CS. Tập 132, Số 2A, 2023 16 𝑑𝑒𝑙𝑡𝑎 = (𝑒𝑖 − 𝑠𝑖 ) − ∑ (𝑒𝑘 − 𝑠𝑘) 𝑘∈𝑅 if (𝑑𝑒𝑙𝑡𝑎 > 0) then 𝑝𝑎𝑡ℎ = [𝑆, 𝑖, 𝑗, 𝑇]; break; if (𝑝𝑎𝑡ℎ ≠ ∅) then Tăng luồng trên đường đi 𝑝𝑎𝑡ℎ lên 1 đơn vị; Giảm luồng trên cung (𝑗, 𝑡) xuống |𝑅| đơn vị với mọi 𝑗 ∈ 𝑝𝑎𝑡ℎ; Giảm luồng cho các cung (𝑆, 𝑘), (𝑘, 𝑗) xuống 1 đơn vị với mọi 𝑘 ∈ 𝑅 và 𝑗 ∈ 𝑝𝑎𝑡ℎ; 𝐿𝑗 = 𝐿𝑗 − {𝑏𝑘} và 𝐿𝑗 = 𝐿𝑗 ∪ {𝑏𝑖} với mọi 𝑘 ∈ 𝑅 và 𝑖 ∈ 𝑝𝑎𝑡ℎ; 𝑉𝑎𝑙𝑢𝑒 = 𝑉𝑎𝑙𝑢𝑒 + 𝑑𝑒𝑙𝑡𝑎 While (𝑝𝑎𝑡ℎ ≠ ∅) return (𝑉𝑎𝑙𝑢𝑒, 𝐿 = {𝐿𝑗 |𝑗 ∈ 𝑊}); 3. Lập lịch lên các kênh: Sau khi đã tìm được luồng cực đại, chúng ta có các danh sách 𝐿. Như vậy, ta có được các chùm được lập lịch trên các kênh chính là các đỉnh tương ứng thuộc 𝐿𝑗. 4. Phân tích giải thuật tính đúng đắn vầ độ phức tạp: 4.1. Tính đúng đắn: Chứng minh lát cắt cực đại cho ta cách lập lịch tối ưu. • Ta có: Với mọi 𝑤𝑗 = 1 , . . . 𝑚, 𝐿𝑗 ≠ ∅ chính là tập các chùm được lập lịch. Với mỗi 𝑏𝑖 ∈ 𝐿𝑗 ta có 𝑓𝑖,𝑗 = 1 nên ∑ (𝑒𝑖 − 𝑠𝑖 )𝑓𝑖,𝑗 𝑏𝑖∈𝐿𝑗 chính là tổng độ dài các chùm được lập lịch lên kênh j. • Giải thuật tìm được luồng cực đại nên giá trị 𝑉𝑎𝑙𝑢𝑒(𝐶) đạt lớn nhất, do đó tổng chiều dài các chùm được lập lịch là lớn nhất. 4. 2. Độ phức tạp tính toán: Giải thuật gồm 3 bước độc lập và rõ ràng. Bước 3 có độ phức tạp tính toán là thấp nhất chỉ là 𝑂(𝑛), bây giờ chúng tôi phân tích độ phức tạp của hai bước còn lại: • Xây dựng mạng 𝑮 = (𝑽, 𝑬): Dễ thấy rằng, việc xây dựng tập cung nối các đỉnh thuộc 𝐼 và 𝑊 là có chi phí lớn nhất, việc này có độ phức tạp 𝑂(𝑛 × 𝑚);

• Tìm luồng cực đại: Do mạng 𝐺 có khả năng thông qua và luồng trên nó là số nguyên, nên giải thuật đảm bảo dừng. Chúng tôi sử dụng một biến thể của giải thuật Ford- Fulkerson là Edmonds-Karp [1] để tìm luồng cực đại kết hợp với giải thuật tìm kiếm nhị phân trong việc tìm đỉnh không chồng lấp (như đã trình bày ở mục 2. Tìm đường tăng luồng nên độ phức tạp tính toán của bước này là 𝑂(|𝑉| × |𝐸|2 × 𝑙𝑜𝑔 (|𝑉|)). Độ phức tạp tính toán của giải thuật: 𝑂(|𝑉| × |𝐸|2 × 𝑙𝑜𝑔 (|𝑉|)).

jos.hueuni.edu.vn Tập 132, Số 2A, 2023 17 4 Mô phỏng và phân tích kết quả Chúng tôi thực hiện cài đặt giải thuật lập lịch nhóm MF_GS và các giải thuật lập lịch nhóm đã được công bố trường đó trong môi trường mô phỏng là NS2 với gói mở rộng obs0.9a [20], trên máy tính CPU Intel Core 2 CPU 2.4 GHz, 2G RAM. Mô hình mạng dùng để mô phỏng là NSFNET14 với 14 nút lõi (𝐶𝑖, 𝑖 = 0. . .13), trong đó mỗi nút lõi kết nối với một nút biên (𝐸𝑖 , 𝑖 = 0. . .13) như mô tả ở Hình 7. Các luồng dữ liệu đến theo phân phối Poisson giữa các cặp nút 𝐸𝑖 và 𝐸𝑗 (𝑖, 𝑗 = 0. . .13). Các chùm được sinh theo phân phối Poisson tại các thời điểm thay đổi và cũng như có kích thước các chùm được sinh ra theo phân phối hàm mũ. Mỗi liên kết có 6 kênh dữ liệu và 2 kênh điều khiển. Băng thông trên mỗi kênh là 10Gb/s. Các tham số mô phỏng: timeslot được thiết lập 700 s. Mô phỏng được thực hiện từ tải 0.1 đến 0.9 Erlangs. Hình 6. Mô hình mạng mô phỏng Các mục đích mô phỏng bao gồm: • So sánh xác suất mất gói tin của các giải thuật lập lịch nhóm trên đa kênh trước đây với giải thuật lập lịch đề xuất theo hai hướng tiếp cận: heuristic và tối ưu kết quả lập lịch. • Đánh giá sự ảnh hưởng của khe thời gian τ đến hiệu quả lập lịch của các giải thuật lập lịch nhóm trên đa kênh. • So sánh thời gian thực hiện của các giải thuật lập lịch nhóm trên đa kênh với giải thuật lập lịch đề xuất.

Nguyễn Hồng Quốc và CS. Tập 132, Số 2A, 2023 18 Hình 7. So sánh xác suất mất gói tin của các giải thuật lập lịch nhóm theo hướng heuristic Với 6 giải thuật lập lịch nhóm trên đa kênh đã được công bố theo hướng tiếp cận heuristic, qua kết quả mô phỏng trên mô hình mạng được thể hiện ở Hình 7 khi so sánh xác suất mất gói trên các giải thuật này cho thấy 2 giải thuật LGS-MC, MWC-GS cho kết quả tốt hơn so với 4 giải thuật còn lại. Bởi vì giải thuật LGS-MC, MWC-GS với điều kiện chọn lập lịch tối ưu hơn nên kết quả lập tốt hơn. Trong đó giải thuật MWC-GS cho kết quả tốt nhất. Hình 8. So sánh xác suất mất gói tin của các giải thuật lập lịch nhóm theo hướng tối ưu kết quả lập lịch Với kết quả mô phỏng thể hiện ở Hình 8 cho thấy giải thuật đề xuất MF_GS và OPT_GS có xác xuất mất gói thấp hơn so nhiều với giải thuật GreedyOPT, do đối với giải thuật

jos.hueuni.edu.vn Tập 132, Số 2A, 2023 19 GreedyOPT dựa trên ý tưởng của giải thuật tham lam khi sắp xếp các chùm theo thời gian đến sớm nhất và thực hiện lập lịch cho các chùm trong danh sách đó, với cách làm này GreedyOPT chỉ tối ưu trong trường hợp các chùm có độ dài bằng nhau. Tuy nhiên các chùm sinh ra trong mạng OBS có độ dài khác nhau, mặt khác giải thuật GreedyOPT gỡ các chùm đã được lập lịch ra và thực hiện lập lịch lại với các chùm đến, tuy nhiên các chùm đã được lập lịch trước đó có thể được lập lịch qua kênh khác hoặc bi loại bỏ, điều này sẽ dẫn đến phải gửi lại các gói điều khiển cho các chùm đó. Bên cạnh đó qua mô phỏng cũng cho thầy xác suất mất gọi tin của giải thuật OPT_GS và MF_GS là bằng nhau bởi vì 2 giải thuật đều tối ưu kết quả lập lịch, tuy nhiên độ phức tạp giải thuật MF_GS chỉ là 𝑂(|𝑉| × |𝐸|2 × 𝑙𝑜𝑔 (|𝑉|)) thấp hơn nhiều so với giải OPT_GS với độ phức tạp 𝑂(𝑛𝑘) và điều này được thể hiện ở Hình 9 khi mô phỏng thời gian thực hiện của 2 giải thuật này. Hình 9. So sánh thời gian thực hiện của 2 giải thuật OPT_GS và MF_GS 5 Kết luận Lập lịch nhóm không được gọi ngay khi một gói điều khiển đến, các gói điều khiển đến trong một khoảng thời gian (timeslot) sẽ tiến hành lập lịch đồng thời cho các chùm của chúng. Kết quả của lập lịch nhóm dựa trên tổng số chùm được lập lịch nhiều nhất và tổng độ dài của các chùm được lập lịch lớn nhất. Cách làm này rõ ràng sẽ giúp khai thác băng thông các kênh ra tốt hơn. Trong bài báo đề xuất một giải thuật lập lịch nhóm tối ưu trên mạng chuyển mạch

chùm quang theo hướng tiếp cận xây dựng mạng, sau đó tìm luồng cực đại trên đồ thị này để

Nguyễn Hồng Quốc và CS. Tập 132, Số 2A, 2023 20 tìm ra tập các chùm có độ dài lớn nhất có thể lập lịch cùng nhau trên các kênh ra. Qua phân tích và kết quả thực nghiệm mô phỏng cho thấy giải thuật đề xuất giảm xác suất mất chùm, độ phức tạp của giải thuật chỉ là 𝑂(|𝑉| × |𝐸|2 × 𝑙𝑜𝑔 (|𝑉|)). Tài liệu tham khảo 1. Akter, Dilruba, Md Sharif Uddin, and Faria Ahmed Shami. "Modification of EDMONDS-KARP Algorithm for Solving Maximum Flow Problem." International Journal of Innovation and Applied Studies 31.4 (2021): 703- 711. 2. Argibay-Losada, Pablo Jesus, Dominique Chiaroni, and Chunming Qiao. "Optical packet switching and optical burst switching." Springer Handbook of Optical Networks (2020): 665-701. 3. Arun Kumar, Krishnan, et al. "Scheduling approach for optical burst switching nodes based on hybrid multipriority algorithm." Optical Engineering 61.3 (2022): 036112-036112. 4. G. B. Figueiredo and N. L. S. Da Fonseca. “Algorithm with linear computational complexity for batch scheduling in OBS networks.” In IEEE International Conference on Communications, 2011 5. G. B. Figueiredo, E. Candido Xavier, and N. L. S. D. Fonseca. Optimal algorithms for the batch scheduling problem in OBS networks. Computer Networks, 56(14):3274–3286, 2012. 6. K. Janicki, P. Mrozicki, and P. Wiatr. “Management platform for next generation optical networks.” 2009 7. Kaheel and H. Alnuweiri. “Batch scheduling algorithms for optical burst switching networks.” Lecture notes in computer science, 3462:90–101, 2005.

8. M. F. Hayat, F. Z. Khan, and H. R. van As. “Performance model for an OBS node with a shared wavelength converter pool and an FDL buffer per link”. Optical Network Design and Modeling (ONDM), 2011 15th International Conference on, pages 1–6, 2011. 9. Naji, L. A. W. A., et al. "Performance analysis comparison of optical burst switching networks’ contention resolution techniques." Indonesian Journal of Electrical Engineering and Computer Science 25.3 (2022): 1539- 1548. 10. Nguyen Hong Quoc, Vo Viet Minh Nhat, Nguyen Hoang Son. “An Algorithm of Group Scheduling with Void Filling in OBS Core Nodes.” Advanced in Computer Science and its Applications, Lecture Notes in Electrical Engineering, 2014, No: 279, pp: 107-114. 11. P. K. Chandra, A. K. Turuk, and B. Sahoo. “Survey on optical burst switching in WDM networks”. In 2009 International Conference on Industrial and Information Systems (ICIIS), pages 83–88, 2009 12. Parsons, Nick, and Nicola Calabretta. "Optical switching for data center networks." Springer Handbook of Optical Networks (2020): 795-825. 13. Nguyễn Hồng Quốc, Võ Viết Minh Nhật, Nguyễn Hoàng Sơn. "Một giải thuật lập lịch nhóm tối ưu trong mạng chuyển mạch chùm quang." Hue University Journal of Science: Techniques and Technology 127.2A (2018): 5- 17. 14. R. Shenai, S. Gowda, and K. Sivalingam. Oirc obs-ns simulator, 2006. 15. Vo Viet Minh Nhat, Nguyen Hong Quoc, Nguyen Hoang Son. “A Group Scheduling Algorithm with Void Filling for Multi-Channel in OBS Networks.” Journal of Science, Hue University, Vol. 107, No. 08, 2015, pp. 77-87, 2015. (ISSN: 1859-1388).

jos.hueuni.edu.vn Tập 132, Số 2A, 2023 21 16. Vo Viet Minh Nhat, Nguyen Hong Quoc, Nguyen Hoang Son. “Group Scheduling for MultiChannel in OBS Networks.” REV Journal on Electronics and Communications, 2014, Vol: 3, No: 3–4, pp: 134-137. 17. Vo Viet Minh Nhat, Nguyen Hong Quoc, Nguyen Hoang Son. “Near-Optimal Algorithm for Group Scheduling in OBS Networks”. ETRI Journal (SCIE), 2015, Vol: 37, No: 5, pp: 888-897. 18. Y. Chen, C. Qiao, and X. Yu. “Optical burst switching: a new area in optical networking research”. Network, IEEE, 18(3):16–23, 2004. 19. Zeghid, Medien, et al. "Modified optical burst switching (OBS) based edge node architecture using real-time scheduling techniques." IEEE Access 9 (2021): 167305-167321. 20. Network Simultor, http://www.isi.edu/nsnam/ns/.