<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1>

NGUYỄN HỒNG QUỐC

NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP LẬP LỊCH

TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG

CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ: 62.48.01.01

TĨM TẮT LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH

Người hướng dẫn khoa học:
1. PGS.TS. Võ Viết Minh Nhật
2. TS. Nguyễn Hoàng Sơn

</div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>

Người hướng dẫn:

1. PGS. TS. Võ Viết Minh Nhật. Đại học Huế, Việt Nam.

2. TS. Nguyễn Hoàng Sơn. Trường Đại học Khoa học, Đại học Huế., Việt Nam.

</div>
<span class='text_page_counter'>(3)</span><div class='page_container' data-page=3>

1. Tính cấp thiết của đề tài

Mạng sợi quang từ khi ra đời vào thập niên 90 cho đến nay, đã trải qua nhiều thế hệ
phát triển: từ những mơ hình định tuyến bước sóng (Wavelength-Routed, WR) ban đầu
dựa trên những đường quang (lightpath) đầu-cuối dành riêng, cho đến các mô hình chuyển
mạch gói quang (Optical Packet Switching, OPS) được đề xuất gần đây, với ý tưởng xuất
phát từ các mô hình mạng chuyển mạch gói điện tử. Tuy nhiên với một số hạn chế về
công nghệ, như chưa thể sản xuất các bộ đệm quang (tương tự bộ nhớ RAM trong môi
trường điện tử) hay các chuyển mạch ở tốc độ nano giây, mơ hình chuyển mạch gói quang
chưa thể trở thành hiện thực. Một giải pháp thỏa hiệp được đề xuất là chuyển mạch chùm
quang (Optical Burst Switching, OBS) đã mở ra một hướng nghiên cứu mới và được xem

là công nghệ hứa hẹn cho mạng Internet thế hệ tiếp theo.

Một đặc trưng tiêu biểu của mạng chuyển mạch chùm quang (mạng OBS) là phần
(gói) điều khiển (Burst Header Packet, BHP) được tách rời với phần (chùm) dữ liệu
(Data Burst, DB). Nói một cách khác, để thực hiện việc truyền một chùm vào trong
mạng lõi, gói điều khiển BHP được tạo ra và được gửi đi trước một khoảng thời gian
offset (offset-time). Thời gian offset này phải được tính tốn đủ để đặt trước tài ngun
và cấu hình các chuyển mạch tại các nút trung gian dọc theo hành trình của chùm quang
từ nguồn đến đích. Tuy nhiên, cách truyền tải này cũng đặt ra áp lực là làm thế nào để
một gói điều khiển BHP kịp lập lịch đặt trước tài nguyên và cấu hình chuyển mạch tại
các nút lõi, đảm bảo việc truyền tải chùm quang theo sau; đó chính là nhiệm vụ của hoạt
động lập lịch đặt trước tài nguyên tại các nút lõi mạng. Vì vậy vấn đề lập lịch rất cần
được quan tâm và nghiên cứu nhằm tối đa hiệu suất băng thông, giảm mất mát dữ liệu
và nâng cao hiệu suất hoạt động của mạng OBS.

2. Động lực nghiên cứu

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, lúc này
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 để lập lịch cho
chùm đến.

Mục đích chính của giải thuật lập lịch 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 mà có thể được phân vào trong hai
nhóm tiếp cận chính:

• Phương pháp lập lịch trực tiếp.
• Phương pháp lập lịch nhóm.

</div>
<span class='text_page_counter'>(4)</span><div class='page_container' data-page=4>

Trong số các giải thuật lập lịch trực tiếp, BF-VF là giải thuật lập lịch tốt nhất về hiệu
suất sử dụng băng thông. Tuy nhiên hiệu quả của lập lịch trực tiếp phụ thuộc vào tình
trạng băng thơng của các kênh ra mà trong đó các chùm đã lập lịch phân bố. Một số giải
pháp 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 đã được đề xuất. Cụ
thể khi lập lịch trực tiếp khơng tìm thấy kênh khả dụng, thay vì chùm đến sẽ bị đánh
rơi hoàn toàn, lập lịch lại sẽ sắp xếp lại các chùm đã được lập lịch trên các kênh bước
sóng nhằm tìm kiếm vị trí băng thơng rỗi để lập lịch cho chùm đến hoặc thực hiện phân
đoạn chùm nhằm chỉ đánh rơi một phần của chùm đến bị tranh chấp. Tuy nhiên lập lịch
trực tiếp và lập lịch trực tiếp kết hợp chỉ tối ưu việc lập lịch cho chùm đến hiện thời mà
không quan tâm đến các chùm đến sau đó. Nên sự phân mãnh băng thông được tạo ra
do việc lập lịch chùm hiện thời và có thể ảnh hưởng đến hiệu quả của các lập lịch sau đó.
Phương pháp lập lịch nhóm do đó được đề xuất, trong đó các gói điều khiển đến trong
một khoảng thời gian sẽ tiến hành lập lịch đồng thời các chùm tương ứng của chúng. Tuỳ
thuộc vào các nút lõi mạng có được trang bị bộ chuyển đổi bước sóng đầy đủ hay khơng,
các giải thuật lập lịch nhóm có thể chia thành hai nhóm: Lập lịch nhóm trên đơn kênh
trong trường hợp không sử dụng bộ chuyển đổi và lập lịch nhóm trên đa kênh khi được
trang bị các bộ chuyển đổi bước sóng đầy đủ.

Tuy nhiên các giải thuật lập lịch nêu trên vẫn bộc lộ những tồn tại sau:

• Giải thuật lập lịch kết hợp: 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 1 để lập lịch cho chùm đến. Việc lập lịch lại của các giải thuật ở
giai đoạn 2 chỉ xem xét đối với chùm sau cùng nhất trên các kênh ra. Đoạn chồng
lấp khi sử dụng kỹ thuật phân đoạn chùm ở giai đoạn 3 bị loại bỏ.

• Giải thuật lập lịch nhóm trên đơn kênh: Độ phức tạp tính tốn của các giải
thuật cao; chưa tận dụng các khoảng trống băng thông được tạo ra giữa các chùm

đã được lập lịch để lập lịch cho các chùm đến và khe thời gian chờ lập lịch được
thiết lập với một giá trị cố định mà chưa quan tâm lưu lượng các chùm đến.
• Giải thuật lập lịch nhóm trên đa kênh: Các giải thuật theo hướng tiếp cận

heuristic chưa đưa ra tiêu chí chọn tối ưu lập lịch cho các chùm đến mà chỉ dựa vào
thứ tự sắp xếp. Các giải thuật lập lịch tối ưu làm tăng số lượng gói điều khiển, yêu
cầu hệ thống phải có sự thay đổi về mặt giao thức. Hơn nữa việc gỡ hết các chùm
đã được lập lịch trên các kênh để đưa về bài toán lập lịch trên máy đồng nhất là
không thực tế trên mạng thật.

Những tồn tại nêu trên chính là động lực để Luận án tập trung nghiên cứu, cải tiến và
đề xuất mới các giải thuật lập lịch nhằm tối thiểu mất mất dữ liệu, tối đa băng thông sử
dụng, giảm thời gian chờ lập lịch, giảm độ phức tạp tính tốn và nâng cao hiệu quả hoạt
động mạng OBS.

3. Mục tiêu nghiên cứu của luận án

Mục tiêu 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 của mạng chuyển mạch chùm quang bao gồm: tối thiểu mất
mát dữ liệu, tối đa hiệu suất băng thông, giảm độ trễ và giảm độ phức tạp tính tốn.
Mục tiêu cụ thể của Luận án là:

</div>
<span class='text_page_counter'>(5)</span><div class='page_container' data-page=5>

• 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.
• 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.

Trên cơ sở mục tiêu nghiên cứu, Luận án được triển khai theo ba vấn đề nghiên cứu chính:
• Vấn đề 1 : Cải tiến giải thuật 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.

• Vấn đề 2 : Cải tiến và đề xuất mới giải thuật lập lịch nhóm trên đơn kênh.
• Vấn đề 3 : Cải tiến và đề xuất mới giải thuật lập lịch nhóm trên đa kênh.

4. Đóng góp của Luận án

Các đóng góp chính của Luận án bao gồm:

• Đề xuất giải thuật lập lịch trực kết hợp lập lịch lại và phân đoạn chùm iCSA[CT2].
• Đề xuất giải thuật lập lịch nhóm trên đơn kênh LGS[CT8] và các cải tiến

LGS-VF[CT4], LAGS[CT5], LAGS-VF[CT7].

• Đề xuất giải thuật lập lịch nhóm trên đa kênh OPT-GS theo hướng tiếp cận tối
ưu và LGS-MC[CT6], LGS-MC-VF[CT3], MWC-GS[CT1], MWC-VF-GS[CT1] theo
hướng tiếp cận heuristic.

CHƯƠNG 1: TỔNG QUAN VỀ LẬP LỊCH

TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG

1.1. Tóm lược lịch sử phát triển của truyền thơng quang

1.2. Các mơ hình chuyển mạch quang

Các mơ hình chuyển mạch quang có thể được chia thành 3 loại: chuyển mạch kênh
quang, chuyển mạch gói quang và chuyển mạch chùm quang.

1.2.1. Chuyển mạch kênh quang

1.2.2. Chuyển mạch gói quang

1.2.3. Chuyển mạch chùm quang

1.3. Mạng chuyển mạch chùm quang

Mạng OBS được xem như là một công nghệ hứa hẹn cho mạng Internet toàn quang thế
hệ kế tiếp bởi nó có nhiều chức năng và ưu điểm hơn so với các mạng chuyển mạch quang
khác. Một số đặc trưng của mạng OBS như sau: Tách biệt giữa kênh truyền gói điều khiển
và kênh truyền chùm; Dành riêng một chiều; Độ dài chùm thay đổi được; Không cần bộ
đệm quang.

1.3.1. Kiến trúc mạng OBS

</div>
<span class='text_page_counter'>(6)</span><div class='page_container' data-page=6>

1.3.1.1. Cấu trúc nút biên

1.3.1.2. Cấu trúc nút lõi

1.3.2. Các hoạt động bên trong mạng OBS

Các hoạt động bên trong mạng OBS bao gồm: tập hợp, báo hiệu, lập lịch và giải quyết
tranh chấp. Mỗi hoạt động đều đóng vai trị quan trọng và tác động trực tiếp đến hiệu
quả hoạt động của mạng OBS.

1.3.2.1. Tập hợp

1.3.2.2. Báo hiệu

1.3.2.3. Lập lịch

1.3.2.4. Định tuyến

1.4. Lập lịch trong mạng OBS

1.4.1. Giới thiệu bài toán lập lịch

1.4.2. Một số kiến thức liên quan

1.4.3. Các giải thuật lập lịch đã công bố

Lập lịch là một trong những hoạt động quan trọng trong mạng OBS. Khi một gói điều

khiển đến tại một nút, tùy thuộc vào đích đến của chùm tương ứng, tài nguyên sẽ dành
riêng tại cổng ra, bao gồm kênh bước sóng và khoảng thời gian chiếm giữ sẽ được cấp
phát. Đã có nhiều giải thuật lập lịch được đề xuất theo các hướng tiếp cận khác nhau
nhằm nâng cao hiệu quả của hoạt động lập lịch. Các giải thuật lập lịch này có thể được
phân loại vào: lập lịch trực tiếp, lập lịch trực tiếp kết hợp với lập lịch lại và kỹ thuật phân
đoạn và lập lịch nhóm.

1.4.3.1. Lập lịch trực tiếp

Khi một gói điều khiển đến tại một nút, một giải thuật lập lịch được gọi để lập lịch
cho chùm tương ứng trên một kênh dữ liệu ra. Dựa vào thông tin trong gói điều khiển, bộ
lập lịch biết được thời điểm đến, độ dài chùm và tiến hành tìm kênh khả dụng để lập lịch
cho chùm đó. Các giải thuật lập lịch trực tiếp trong mạng OBS có thể được chia thành 2
loại: lập lịch không lấp đầy khoảng trống và lập lịch có lấp đầy khoảng trống.

1.4.3.2. Lập lịch trực tiếp kết hợp

Các giải thuật lập lịch trực tiếp có thể thất bại khi khơng tìm thấy kênh khả dụng
để lập lịch cho chùm đến. Kết quả là chùm sẽ bị loại bỏ và sẽ gây mất mát dữ liệu lớn,
trong khi các chùm đã được lập lịch trên các kênh ra có thể được sắp xếp lại nhằm tạo
ra khoảng băng thơng rỗi để có thể lập lịch cho chùm đến. Trong trường hợp việc loại bỏ
không thể tránh khỏi, kỹ thuật phân đoạn chùm có thể làm giảm mất mát nếu chấp nhận
loại bỏ đoạn chồng lấp và phần còn lại của chùm sẽ được lập lịch. Một hướng tiếp cận
kết hợp do đó được đề xuất nhằm tránh hay giảm việc loại bỏ toàn bộ chùm. Sau đây là
các tiếp cận kết hợp đã được công bố.

1.4.3.2.1. Kết hợp lập lịch trực tiếp và lập lịch lại

</div>
<span class='text_page_counter'>(7)</span><div class='page_container' data-page=7>

thông trên các kênh ra, giảm mất mát chùm và hạn chế các xử lý phức tạp khác.

1.4.3.2.2. Kết hợp lập lịch trực tiếp và phân đoạn chùm

Ý tưởng phân đoạn chùm được đề xuất đầu tiên bởi Vokkarane và cộng sự, chùm được
chia thành các đoạn để khi có xung đột xảy ra chỉ có một vài đoạn bị loại bỏ và các đoạn
còn lại vẫn được truyền qua mạng. Các đoạn bị mất có thể là phần trước (head dropping)
hay phần sau (tail dropping).

1.4.3.2.3. 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

Không chỉ kết hợp lập lịch trực tiếp với phân đoạn, tác giả Umaru, Aydin và cộng sự
đề xuất một tổ hợp khác giữa lập lịch, lập lịch lại và phân đoạn. Cụ thể, PCSA
(Pre-emptive Channel Scheduling Algorithm) dựa trên LAUC-VF, ODBR và phân đoạn chùm.
Sơ đồ lập lịch kết hợp này được thiết kế nhằm thỏa mãn các yêu cầu QoS trong mạng
OBS. Một sự kết hợp khác có tên gọi là SODBRA (Segmentation-based On-Demand Burst
Rescheduling Algorithm), là tổ hợp của FFUC-VF, ODBR và phân đoạn chùm.

1.4.3.3. Lập lịch nhóm

Trong lập lịch nhóm, một giải thuật lập lịch khơng được gọi ngay khi một gói điều
khiển đến, mà các gói điều khiển đến trong một khe thời gian τ sẽ tiến hành lập lịch đồng
thời cho các chùm của chúng.

Lập lịch nhóm có thể được chia thành 2 loại: lập lịch nhóm khơng có chuyển đổi bước
sóng, nghĩa là lập lịch nhóm trên đơn kênh và lập lịch nhóm có chuyển đổi bước sóng,
nghĩa là lập lịch nhóm trên đa kênh.

1.4.3.4. Kết hợp lập lịch và các giải pháp xử lý tắc nghẽn

1.4.3.4.1. Sử dụng đường trễ FDL

1.4.3.4.2. Chuyển đổi bước sóng

1.4.3.4.3. Định tuyến lệch hướng

1.4.4. Một số nhận xét các giải thuật lập lịch đã công bố

Các giải thuật lập lịch đã được công bố theo các hướng tiếp cận khác nhau nhằm giảm
xác suất mất mát dữ liệu, tối ưu hiệu suất băng thông. Tuy nhiêu vẫn cịn những tồn tại
của các mơ hình, giải thuật lập lịch này. Vì vậy việc tiếp tục cải tiến, đề xuất mới các mơ
hình, giải thuật lập lịch là cần thiết nhằm tận dụng băng thông tốt hơn, giảm xác suất
mất gói tin và nâng cao hiệu quả hoạt động lập lịch của mạng OBS.

1.5. Tiểu kết Chương 1

</div>
<span class='text_page_counter'>(8)</span><div class='page_container' data-page=8>

CHƯƠNG 2: MỘT 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

2.1. Giới thiệu

Các giải thuật lập lịch trực tiếp có thể thất bại trong việc lập lịch một chùm đến nếu
băng thông không khả dụng ở các kênh ra. Tuy nhiên, việc lập lịch có thể thực hiện được
nếu có một sắp xếp lại đối với các chùm đã được lập lịch trên các kênh ra, sao cho khoảng
trống băng thông tạo ra có thể lập lịch cho chùm đến. Đây chính là ý tưởng của giải thuật
ODBR và ABR.

Nhưng trong trường hợp loại bỏ chùm là không thể tránh khỏi, phân đoạn chùm là
một giải pháp phù hợp nhằm làm giảm mất mát dữ liệu, trong đó chỉ phần chùm chồng
lấp là bị loại bỏ, trong khi phần chùm còn lại được lập lịch để truyền đi đến nút kế tiếp.
Một kết hợp hoàn chỉnh, bao gồm lập lịch trực tiếp, lập lịch lại và phân đoạn chùm như
PCSA và SODBRA đã được đề xuất nhằm lập lịch hiệu quả hơn đối với chùm đến.

2.2. Phân tích và đánh giá các giải thuật lập lịch kết hợp đã công

bố

Các giải thuật lập lịch kết hợp có thể được phân loại như sau:
• Lập lịch trực tiếp kết hợp với lập lịch lại gồm ODBR và ABR.

• Lập lịch trực tiếp kết hợp với phân đoạn chùm gồm NP-MOC, NP-MOC-VF.
• 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 gồm PCSA và SODBRA.

2.2.1. Giải thuật ODBR

2.2.2. Giải thuật ABR

2.2.3. Kỹ thuật phân đoạn chùm

2.2.4. Giải thuật SODBRA

2.2.5. Giải thuật PCSA

2.3. Giải thuật lập lịch kết hợp đề xuất iCSA

Giải thuật lập lịch kết hợp được Luận án đề xuất iCSA (improved Composite Scheduling
Algorithm) đã được công bố trong [CT2].

Giải thuật iCSA là một kết hợp của lập lịch lấp đầy khoảng trống, lập lịch lại và phân
đoạn chùm, bao gồm 3 giai đoạn được thực hiện tuần tự tùy thuộc vào sự thành công hay
thất bại của giai đoạn trước.

Giai đoạn 1: Khi có một chùm đến, giải thuật lập lịch lấp đầy khoảng trống BFVF
được gọi để tìm khoảng trống khả dụng vừa khít nhất để lập lịch cho chùm này. Nếu lập
lịch thành công giải thuật iCSA kết thúc, ngược lại Giai đoạn 2 được gọi.

</div>
<span class='text_page_counter'>(9)</span><div class='page_container' data-page=9>

Giai đoạn 3: tính tốn độ chồng lập của chùm đến với các chùm đã được lập lịch trên
các kênh và kênh có khoảng chồng lấp nhỏ nhất sẽ được chọn để lập lịch cho chùm đến
sau khi đã cắt phần chồng lấp; Nếu phần bị chồng lấp có thể được lập lịch trên một trong
các kênh còn lại, một chùm mới sẽ được tạo ra và lập lịch trên kênh khả dụng đó(với giả
sử nút lõi OBS có khả năng tạo gói điều khiển).

Giải thuật iCSA được mô tả chi tiết như sau:

Algorithm 2.1: iCSA (improved Composite Scheduling Algorithm)
Input : ub(sub, eub), W = {1, 2, . . . , m}, SBk với k ∈ W ;

Output: bestchannel ;

1 bestchannel := BF V F (ub, W );
2 if (bestchannel 6= −1) then

3 Lập lịch chùm ub trên kênh bestchannel và return;
4 foreach k ∈ W do

5 OBk := ∅;

6 foreach sbi,k ∈ SBk do

7 if (s_ub ∈ [s_i,k, e_i,k]) ∨ (s_i,k ∈ [s_ub, e_ub]) then
8 OB_k := OB_k∪ {sb_i,k}; ref_i,k := 0;
9 else

10 OB := OB ∪ {OB_k};
11 Sort(k, |OB_k|); k := 1;

12 while (k ≤ m) do
13 success := |OBk|;
14 bestchannel := −1 ;
15 foreach sb_i,k ∈ SB_k do

16 bestchannel := BF V F (ub, W \ {k});
17 if (bestchannel 6= −1) then

18 success := success − 1;
19 refi,k := bestchannel;
20 if (success = 0) then
21 foreach sb_i,k ∈ SB_k do

22 Lập lịch lại chùm sb_i,k trên kênh k sang kênh ref_i,k;
23 Gửi lại gói điều khiển cho chùm sbi,k;

24 Gỡ bỏ chùm sbi,k lập lịch trên kênh k ;

25 Lập lịch chùm ub trên kênh bestchannel và return;
26 k := k + 1;

</div>
<span class='text_page_counter'>(10)</span><div class='page_container' data-page=10>

33 while (k ≤ m) ∧ (|OBk| = 1) do

34 if ((sub < s1,k) ∧ (eub− s1,k) < bestlenght) then
35 bestlenght := e_ub− s_1,k;

36 droptype := 0; bestchannel := k;
37 else

38 if ((s_ub > s_1,k) ∧ (e_ub− s_1,k) > bestlenght) then
39 bestlenght := s_1,k − e_ub;

40 droptype := 1; bestchannel := k;
41 if (droptype = 0) then

42 e_ub:= e_ub− bestlenght;

43 Lập lịch chùm ub sau khi loại bỏ đoạn đầu chồng lấp trên kênh bestchannel;
44 eoverlap:= eub; soverlap:= sub− bestlenght;

45 Tạo chùm mới từ đoạn chồng lấp newub(soverlap, eoverlap);
46 ch := BF V F (new_ub, W );

47 if (ch 6= −1) then

48 Lập lịch chùm new_ub trên kênh ch;

49 Tạo gói điều khiển mới cho chùm new_ub và return;
50 if (droptype = 1) then

51 s_ub := s_ub− bestlenght;

52 Lập lịch chùm ub sau khi loại bỏ đoạn đầu chồng lấp trên kênh

bestchannel;

53 eoverlap:= eub; soverlap:= sub− bestlenght;

54 Tạo chùm mới từ đoạn chồng lấp newub(soverlap, eoverlap);

55 ch := BF V F (newub, W );

56 if (ch 6= −1) then

57 Lập lịch chùm new_ub trên kênh ch;

58 Tạo gói điều khiển mới cho chùm new_ub và return;

Function BFVF(ub, W )

1 gap := ∞;

2 bestchannel := −1;
3 foreach k ∈ W do

4 e_0,k := 0; e|SBk|+1,k := ∞;
5 foreach j ∈ SB_k do

6 if ((sub > ej,k) ∧ (sj+1,k > eub) ∧ ((sj+1,k− ej,k) < gap)) then
7 bestchannel := k;

8 gap := s_j+1,k− e_j,k;
9 return bestchannel;

</div>
<span class='text_page_counter'>(11)</span><div class='page_container' data-page=11>

2.4. Mô phỏng và phân tích kết quả

Để chứng minh tính hiệu quả của giải thuật đề xuất Luận án thực hiện cài đặt mô
phỏng giải thuật lập lịch đề xuất iCSA để so sánh với các giải thuật đã được công bố, bao
gồm LAUC, BFVF, ODBR, ABR, SODBRA và PCSA. Môi trường mơ phỏng sử dụng
gói NS2-obs0.9a và phần mềm C++, cài đặt trên máy tính CPU Intel Core 2 CPU 2.4

GHz, 2G RAM. Mơ hình mạng mơ phỏng NSFNET với 14 nút lõi, trong đó mỗi nút lõi
kết nối với một nút biên.

Qua kết quả mô phỏng được thể ở các Hình từ 2.8 đến 2.15 khi so sánh giải thuật lập
lịch đề xuất iCSA và các giải thuật lập lịch đã được công bố cho thấy xác suất mất gói
tin của giải thuật iCSA thấp hơn nhiều, giảm được số lượng gói điều khiển phải gửi lại
do các chùm bị phân đoạn và có độ phức tạp giải thuật bằng với các giải thuật cùng loại.

Hình 2.8. So sánh xác suất mất
gói tin giữa LAUC và BF-VF

Hình 2.9. So sánh xác suất mất
gói tin giữa ODBR và ABR

Hình 2.10. So sánh số chùm phải
lập lịch lại giữa ODBR và ABR

Hình 2.11. So sánh xác suất mất gói tin
của iCSA so với ODBR và ABR

Hình 2.12. So sánh số chùm phải lập lịch lại
của iCSA so với ODBR và ABR

</div>
<span class='text_page_counter'>(12)</span><div class='page_container' data-page=12>

Hình 2.14. So sánh số chùm lập lịch lại
của iCSA so với SODBRA và PCSA

Hình 2.15. So sánh số chùm phân đoạn
của iCSA so với SODBRA và PCSA

2.5. Tiểu kết Chương 2

Chương này của Luận án đã trình bày, phân tích, đánh giá chi tiết các giải thuật lập
lịch kết hợp giữa lập lịch trực tiếp và lập lịch lại ODBR, ABR và lập lịch trực tiếp kết
hợp lập lịch lại và kỹ thuật phân đoạn chùm đã được cơng bố SODBRA, PSCA.

Trên cơ sở phân tích, đánh giá và đưa ra ưu điểm và tồn tại của các giải thuật, Luận
án đề xuất một giải thuật lập lịch trực tiếp kết hợp lập lịch lại và kỹ thuật phân đoạn
chùm iCSA. Với những ưu điểm:

• Giải thuật đề xuất iCSA sử dụng giải thuật lập lịch trực tiếp BFVF là giải thuật
lập lịch tốt nhất trong các giải thuật lập lịch trực tiếp để lập lịch chùm đến.
• Trong Giai đoạn 2, iCSA thực hiện lập lịch lại cho bất kỳ chùm chồng lấp nào với

chùm đến nên giảm được xác suất mất gói tin và tận dụng băng thơng tốt hơn.
• Trong Giai đoạn 3, iCSA tìm khoảng trống (băng thơng khả dụng) trên một kênh

nào đó để lập lịch cho phần chùm chồng lấp này. Cách làm này sẽ làm giảm xác
suất mất gói tin và sử dụng băng thông các kênh ra tốt hơn.

Các kết quả mô phỏng đã chứng minh giải thuật lập lịch đề xuất iCSA có xác suất mất
gói tin thấp hơn các giải thuật đã được cơng bố trước đó và có độ phức tạp giải thuật
bằng với các giải thuật cùng loạ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

3.1. Giới thiệu

Lập lịch nhóm tại nút lõi OBS là hoạt động mà các gói điều khiển đến trong mỗi khe

thời gian τ , dựa vào thơng tin trong gói điều khiển một giải thuật lập lịch sẽ được gọi
để tiến hành lập lịch đồng thời cho các chùm tương ứng của chúng (như thể hiện ở Hình
3.1). Lập lịch nhóm có thể được thực hiện chỉ trên một kênh dữ liệu ra khi khơng có sự
hỗ trợ của chuyển đổi bước sóng và các chùm đến này được giả sử có cùng bước sóng.
Loại lập lịch này được gọi là lập lịch nhóm trên đơn kênh. Trường hợp lập lịch nhóm có
sự hỗ trợ của chuyển đổi bước sóng, được gọi là lập lịch nhóm trên đa kênh sẽ được trình
bày trong chương tiếp theo.

</div>
<span class='text_page_counter'>(13)</span><div class='page_container' data-page=13>

Hình 3.1: (a) Mơ tả hoạt động lập lịch nhóm trên đơn kênh và (b) đa kênh

3.2. Phân tích và đánh giá các giải thuật lập lịch nhóm trên đơn

kênh đã cơng bố

Có hai giải thuật lập lịch nhóm trên đơn kênh đã được cơng bố: OBS-GS(OBS Group
Scheduling) và MWIS-OS(Maximum Weight Independent Set - Optimal Scheduling).

3.2.1. Giải thuật OBS-GS

3.2.2. Giải thuật MWIS-OS

3.3. Giải thuật lập lịch nhóm trên đơn kênh đề xuất LGS và các

mở rộng

3.3.1. Mơ hình lập lịch nhóm trên đơn kênh

Khơng mất tính tổng qt, giả sử xét một nút lõi OBS có 2 cổng vào, 2 cổng ra như
Hình 3.6a, khơng sử dụng đường trễ FDL, khơng có các bộ chuyển đổi bước sóng và thời
gian offset được thiết lập đủ để các gói điều khiển đặt trước và cấu hình các nút dọc theo
hành trình từ nguồn đến đích. Hình 3.6b mơ tả chi tiết mơ hình lập lịch nhóm đề xuất.
Các gói điều khiển đến trong khe thời gian τ được tính từ thời điểm gói điều khiển đầu
tiên đến. Mơ hình lập lịch nhóm có thể được mơ tả thành q trình 2 giai đoạn như sau:

Hình 3.6. Mơ hình hoạt động của lập lịch nhóm được đề xuất

</div>
<span class='text_page_counter'>(14)</span><div class='page_container' data-page=14>

LAU T trên kênh ra của nó. Dựa vào thơng tin kênh bước sóng đến, các gói điều khiển
(tương ứng các chùm đến) được đưa vào hàng đợi có thể lập lịch cùng nhau. Quá trình
lập lịch tiếp tục được chuyển sang Giai đoạn 2.

Giai đoạn 2: Lập lịch đồng thời cho các chùm tương ứng với các gói điều khiển trong
hàng đợi. Tương tự giải thuật MWIS-OS, danh sách các chùm được chọn lập lịch là các
chùm có tổng độ dài lớn nhất.

Từ mơ hình lập lịch nhóm này, Luận án đề xuất giải thuật lập lịch nhóm như sau.

3.3.2. Giải thuật đề xuất LGS

Giải thuật lập lịch nhóm trên đơn kênh LGS đã được công bố trong [CT7].

Xét n gói điều khiển {BHP1, BHP2, . . . , BHPn} đến trong khe thời gian τ trên một

kênh i, trong đó n là số gói điều khiển đến, tương ứng n chùm cần lập lịch I =
{b1, b2, . . . , bn}, trong đó bi = (si, ei) là một bộ hai với si là thời điểm đến của chùm, ei là

thời điểm kết thúc (chiều dài của chùm được tính là li = ei− si); hai chùm bi = (si, ei) và

bj = (sj, ej) chỉ có thể được lập lịch với nhau nếu thời điểm đến của chúng không chồng

lên nhau (tức là (([si, ei] ∩ [sj, ej]) = ∅). Giải thuật lập lịch LGS được thể hiện như sau:

Algorithm 3.2: LGS (Linear Group Scheduling)
Input : I = {b1, b2, . . . , bn};

Output: I0 tập các chùm có tổng chiều dài lớn nhất được lập lịch (I0 ⊆ I);

1 Sắp xếp không giảm tập I theo thời điểm kết thúc của mỗi chùm;
2 foreach bj ∈ I do

3 i := j − 1;
4 repeat

5 if (s_j > e_i) then

6 index(j) := i và break;
7 else

8 index(j) := 0;

9 i := i − 1;
10 until i = 0;
11 C(0) := 0;

12 foreach b_j ∈ I do

13 C(j) := max{C(j − 1), l_j + C(index(j))};
14 j := n;

15 cost := C(n);
16 while (j > 0) do

17 if (cost = C(j − 1)) then
18 j := j − 1;

19 else

20 I0 := I0∪ {bj};

21 j := index(j); cost := C(j);
22 Lập lịch cho tất cả các chùm trong I0;

</div>
<span class='text_page_counter'>(15)</span><div class='page_container' data-page=15>

Tuy nhiên để giảm bớt thời gian thực hiện và độ phức tạp của giải thuật, trong khe
thời gian τ chờ lập lịch, mỗi gói điều khiển j đến đều được sắp xếp ngay và tính giá trị
index(j) của nó thì thời gian thực hiện của mơ hình lập lịch sẽ được giảm xuống và độ
phức tạp của giải thuật chỉ cịn là O(n).

Bên cạnh đó để tận dụng các khoảng trống được tạo ra giữa các chùm đã được lập lịch
trên các kênh ra nhằm giảm xác suất mất gói và tăng hiệu quả của giải thuật lập lịch,
trên mỗi kênh bước sóng ra bộ lập lịch thay vì chỉ lưu giá trị LAU T , nó sẽ duy trì thời
điểm bắt đầu(sk

i) và thời điểm kết thúc(eki) của các chùm i đã được lập lịch trên kênh

thứ k đó. Một gói điều khiển đến trong khe thời gian τ được xem là đủ điều kiện để xem
xét lập lịch cho chùm tương ứng (sw

i , ewi ) trên kênh đó nếu w = k, swi > eki và skj+1 > ewi .

Cải tiến này được gọi là giải thuật LGS-VF.

3.3.3. Các giải thuật mở rộng đề xuất từ LGS

Giải thuật lập lịch nhóm thích nghi trên đơn kênh LAGS, LAGS-VF đã được công bố

trong [CT4], [CT5].

Trong mơ hình lập lịch nhóm được trình bày trong Mục 3.3.1, khe thời gian lập lịch
nhóm τ được ấn định cố định trước và không thay đổi trong suốt quá trình vận hành
của mạng. Tuy nhiên, khi tốc độ các chùm đến thay đổi, số gói điều khiển đến trong khe
thời gian này cũng sẽ tăng giảm khác nhau. Số lượng các gói điều khiển thực hiện lập
lịch đồng thời có một ảnh hưởng nhất định đến hiệu quả lập lịch và thời gian lập lịch. Rõ
ràng có một nhu cầu cần thay đổi độ rộng của khe thời gian lập lịch nhóm τ .

Hàm điều chỉnh khe thời gian lập lịch nhóm τ chuyển biến theo tốc độ luồng các chùm
đến được mô tả như sau:

Function AdaptiveTimeslot
Input : τmin, τmax, Vavg;

Output: τ, Vavg;
1 Va :=

Na

τ ;

2 if (V_a > V_avg) then
3 a := −_VVa

avg;
4 else

5 a := _VVa
avg;

6 τ := τ +a ×τ_step;
7 if (τ < 2 × τ_min) then
8 τ := 2 × τ_min;
9 if (τ > τmax) then
10 τ := τmax;
11 V_avg := (Va+V₂avg);
12 return τ, V_avg;

</div>
<span class='text_page_counter'>(16)</span><div class='page_container' data-page=16>

lập lịch nhóm được đề xuất trở nên thích nghi vì khe thời gian lập lịch nhóm lúc này
được điều chỉnh thích nghi chuyển biến theo tốc độ luồng các chùm đến, nên có tên gọi là
LAGS(Linear Adaptive Group Scheduling), LAGS-VF(Linear Adaptive Group Scheduling
– Void Fill ) và được mô tả như sau:

Algorithm 3.3: LAGS (Linear Adaptive Group Scheduling)
Input : I = {b1, b2, . . . , bn}, τmin, τmax, Vavg;

Output: I0 tập các chùm có tổng chiều dài lớn nhất được lập lịch(I0 ⊆ I), τ, Vavg;
1 Sắp xếp không giảm tập I theo thời điểm kết thúc của mỗi chùm;

2 foreach bj ∈ I do
3 i := j − 1;
4 repeat

5 if (s_j > e_i) then

6 index(j) := i và break;
7 else

8 index(j) := 0;

9 i := i − 1;
10 until i = 0;
11 C(0) := 0;

12 foreach b_j ∈ I do

13 C(j) := max{C(j − 1), l_j + C(index(j))};
14 j := n; cost := C(n);

15 while (j > 0) do

16 if (cost = C(j − 1)) then
17 j := j − 1;

18 else

19 I0 := I0∪ {bj}; j := index(j); cost := C(j);
20 Lập lịch cho tất cả các chùm trong I0;

21 AdaptiveT imeslot(τ_min, τ_max, V_avg);

3.4. Mơ phỏng và phân tích kết quả

Mục này sẽ trình bày chi tiết về cài đặt các giải thuật lập lịch nhóm đã đề xuất LGS,
LGS-VF, LAGS-VF và so sánh (về xác suất mất gói tin và độ trễ) với giải thuật lập lịch
trực tiếp LAUC-VF và hai giải thuật lập lịch nhóm OBS-GS, MWIS-OS đã được công bố
trước đây. Với môi trường mô phỏng được trình bày ở trong Mục 2.4.

Mơ hình mạng mơ phỏng Dumbbell bao gồm 2 nút lõi (C1 và C2), trong đó mỗi nút lõi

kết nối với 5 nút biên (Ei, i = 1, . . . , 10).

</div>
<span class='text_page_counter'>(17)</span><div class='page_container' data-page=17>

Hình 3.12. So sánh xác suất mất gói tin
giữa LAUC-VF và LGS

Hình 3.13. So sánh xác suất mất gói tin
của OBS-GS, MWIS-OS, LGS và LGS-VF

Hình 3.14. So sánh thơng lượng của OBS-GS,
MWIS-OS và LGS-VF

Hình 3.15. So sánh xác xuất mất gói tin giữa
LGS-VF và LAGS-VF

Hình 3.16. Phân bố độ rộng khe thời gian τ của
MWIS-OS và LAGS-VF

Hình 3.17. So sánh thời gian chờ trung bình của
MWIS-OS và LAGS-VF

3.5. Tiểu kết Chương 3

Chương này của Luận án đã trình bày, phân tích, đánh giá các giải thuật lập lịch nhóm
trên đơn kênh đã được cơng bố. Qua đó đưa ra được những ưu điểm và một số tồn tại
của các giải thuật lập lịch này.

Trên cơ sở đó Luận án đề xuất giải thuật lập lịch nhóm LGS và các cải tiến LGS-VF và
LAGS-VF có độ phức tạp của các giải thuật thấp hơn so với các giải thuật lập lịch nhóm
đã được cơng bố trước đó. Bên cạnh đó giải thuật đề xuất tận dụng được các khoảng
trống tạo ra giữa các chùm đã lập lịch trước đó để lập lịch cho chùm đến, vì vậy giảm

xác suất mất gói tin và điều khiển tắc nghẽn tốt hơn. Ngoài ra khe thời gian chờ lập lịch
thích nghi theo tốc độ đến các gói điều khiển vì vậy giảm được độ trễ đầu cuối.

</div>
<span class='text_page_counter'>(18)</span><div class='page_container' data-page=18>

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

4.1. Giới thiệu

Trường hợp nút lõi mạng OBS được trang bị các bộ chuyển đổi bước sóng đầy đủ, một
chùm đến trên một kênh bước sóng có thể được lập lịch trên một kênh ra bất kỳ với hỗ
trợ của bộ chuyển đổi bước sóng. Loại lập lịch nhóm với hỗ trợ của các bộ chuyển đổi
bước sóng được gọi là lập lịch nhóm trên đa kênh

4.2. Phân tích và đánh giá các giải thuật lập lịch nhóm trên đa

kênh đã cơng bố

4.2.1. Nhóm các giải thuật lập lịch heuristic

Nhóm giải thuật lập lịch heuristic được đề xuất bởi Kaheel và cộng sự bao 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 ).

4.2.1.1. Giải thuật SSF

4.2.1.2. Giải thuật LIF

4.2.1.3. Giải thuật SLV

4.2.1.4. Giải thuật MCF

4.2.2. Nhóm các giải thuật lập lịch tối ưu

Các giải thuật heuristic được trình bày ở trên rõ ràng không đạt được kết quả lập lịch
tối ưu. Một hướng tiếp cận khác của tác giả Figueiredo và cộng sự đã đề xuất 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.

4.2.2.1. Giải thuật GreedyOPT

4.2.2.2. Giải thuật BATCHOPT

4.3. Các giải thuật lập lịch nhóm đề xuất trên đa kênh

Như trình bày ở trên 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 đưa ra được tiêu chí chọn tập các chùm tối ưu trong lập lịch. Ngược
lại đối với các giải thuật theo hướng tiếp cận tối ưu lập lịch để đạt được kết quả lập lịch
tối ưu, giải thuật GreedyOPT, BATCHOPT phải chịu một độ phức tạp lớn về mặt tính
tố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.

</div>
<span class='text_page_counter'>(19)</span><div class='page_container' data-page=19>

4.3.1. Giải thuật lập lịch nhóm tối ưu OPT-GS

Xét tập các n gói điều khiển {BHP1, BHP2, . . . , BHPn} đến trong khe thời gian τ ,

yêu cầu lập lịch cho n chùm tương ứng của nó I = {b1, b2, . . . , bn}. Vấn đề là tìm tập các

chùm I0 ⊆ I có thể lập lịch cùng nhau trên m kênh ra có tổng độ dài các chùm được
lập lịch là lớn nhất. Để giải quyết bài toán này, Luận án mơ hình hố bài tốn lập lịch
nhóm trên đa kênh sang bài tốn tìm tập các đường đi trên đơn đồ thị khoảng có hướng
có trọng số. Giải thuật OPT-GS được mô tả chi tiết như sau:

Algorithm 4.4: OPT-GS (Optimal Group Scheduling )
Input : I = {b1, b2, . . . , bn}, W = {1, 2, . . . , m};

Output: I0 tập các chùm được lập lịch trên m kênh ra;

1 Sắp xếp không giảm các kênh theo giá trị LAU T ;

2 Sắp xếp không giảm tập I theo thời điểm kết thúc của mỗi chùm và tập A là tập

các chùm sau khi đã sắp xếp.

3 V := ∅; E := ∅;
4 foreach ai ∈ A do

5 Tạo đỉnh i; V := V ∪ {i};
6 foreach i, j ∈ V sao cho i < j do

7 if (e_i > s_j) ∧ (@k(∀k ∈ (i + 1, j − 1)|((e_i > s_k) ∧ (e_k> s_j))) then
8 Tạo cung (i, j) đi từ i đến j; E := E ∪ {(i, j)};

9 Trọng số của đỉnh i là li := ei− si;
10 foreach w ∈ W do

11 D_w = ∅;

12 foreach i ∈ V sao cho ((si > LAU Tw) ∧ ((j, i) /∈ E) ∧ (sj > LAU Tw)) do
13 Tìm tất cả các đường đi dw_i xuất phát từ đỉnh i trên kênh w có dạng

{r1, r2, . . . , rl} trong đó r1 = i, (ri, ri+1) ∈ E, với ∀i = 1, 2, . . . , l − 1 và

(rl, rk) /∈ E với ∀k > l;
14 D_w := D_w∪ {dw_i };
15 foreach j ∈ |D₁| do

16 p_j := d1_j; P := P ∪ {p_j};
17 Q := ∅; h := 0;

18 foreach w ∈ {2, 3, . . . , m} do
19 foreach i ∈ |P | do

20 foreach dw_i ∈ D_w do

21 h := h + 1; q_h := p_i∪ {dw_j} r {p_i}; Q := Q ∪ {q_h};
22 P := Q; h := 0; Q := ∅;

23 p_max := ∅; L_max := 0;
24 foreach p_i ∈ P do

25 Tính tổng trọng số các đỉnh trong p_i ký hiệu là L_i;
26 if (Li > Lmax) then

27 Lmax := Li; pmax := pi;

</div>
<span class='text_page_counter'>(20)</span><div class='page_container' data-page=20>

Độ phức tạp giải thuật OPT-GS là: O(|P | × |D|).

4.3.2. Giải thuật lập lịch nhóm heuristic LGS-MC

Giải thuật lập lịch nhóm trên đa kênh LGS-MC đã được công bố trong [CT6]. Giải
thuật LGS-MC (Linear Group Scheduling for Multi Channel ) là một mở rộng của giải

thuật lập lịch nhóm trên đơn kênh LGS. Tư tưởng của giải thuật LGS-MC là tối ưu lập
lịch trên mỗi kênh. Giải thuật LGS-MC được mô tả chi tiết như sau:

Algorithm 4.5: LGS-MC(Linear Group Scheduling for Multi Channel )
Input : I = {b1, b2, . . . , bn}, W = 1, 2, . . . , m;

Output: I0 tập các chùm có tổng chiều dài các chùm được lập lịch trên mỗi
kênh là lớn nhất;

1 I0 := ∅;

2 Sắp xếp không giảm các kênh theo giá trị LAU T ;
3 while (w ≤ m) ∧ (I 6= ∅) do

4 foreach b_i ∈ I do

5 if (si < LAU Tw) then
6 I := I r {bi};

7 Sắp xếp không giảm tập I theo thời điểm kết thúc của mỗi chùm;
8 foreach bj ∈ I do

9 k := j − 1;

10 repeat

11 if (s_j > e_k) then

12 index(j) := k và break;
13 else

14 index(j) := 0;

15 k := k − 1;

16 until k = 0;
17 C(0) := 0;

18 foreach b_j ∈ I do

19 C(j) := max{C(j − 1), l_i+ C(index(j))};
20 j := n; cost := C(n);

21 while (j > 0) do

22 if (cost = C(j − 1)) then

23 j := j − 1;

24 else

25 I0 := I0∪ {bj}; I := I r {bj}; j := index(j); cost := C(j);
26 w := w + 1;

Độ phức tạp của giải thuật LGS-MC là: O(n × log(n)).

4.3.3. Giải thuật lập lịch nhóm heuristic MWC-GS

Luận án mơ hình hố khả năng lập lịch của các chùm đến trên các kênh ra bằng một
đồ thị khoảng G = (V, E), trong đó mỗi đỉnh bk_i ∈ V biểu diễn một khả năng lập lịch của

chùm bi trên kênh k và mỗi cạnh {bki, bhj} ∈ E tương ứng với một trong 2 trường hợp: 2

</div>
<span class='text_page_counter'>(21)</span><div class='page_container' data-page=21>

hoặc chúng được lập lịch trên 2 kênh phân biệt (k 6= h).

Vấn đề tìm một giải pháp lập lịch tối ưu (chẳng hạn có tổng trọng số/độ dài lớn nhất)
các chùm đến trên các kênh dữ liệu lúc này trở thành bài tốn tìm một clique cực đại có
tổng trọng số lớn nhất (Maximum Weight Clique, MWC), được gọi Cmax, trên G. Tập các

chùm I0 ⊆ I tương ứng với các đỉnh trong Cmax, chính là lời giải lập lịch tối ưu.

Giải thuật lập lịch nhóm dựa trên tìm MWC-GS của Luận án bao gồm 3 bước chính:
Algorithm 4.6: MWC-GS

Input : I = {b1, b2, . . . , bn}, W = 1, 2, . . . , m;

Output: I0 tập các chùm có tổng chiều dài các chùm được lập lịch trên mỗi
kênh là lớn nhất I0 ⊆ I;

1 Bước 1: Xây dựng đồ thị khoảng vô hướng G(V, E) từ lời gọi hàm:

G(V, E) = constructGraph;

2 Bước 2: Tìm clique cực đại có tổng trọng số lớn nhất trong G trên mỗi cạnh:

Cmax = f indM W C;

3 Bước 3: Lập lịch cho các chùm trong C_max: I0 = scheduleBurstsf romM W C;

Sau đây là mô tả chi tiết của các hàm.

4.3.3.1. Xây dựng đồ thị khoảng biểu diễn khả năng lập lịch

Hàm constructGraph được mô tả như sau:
Function ConstructGraph

Input : I = {b1, b2, . . . , bn}, W = 1, 2, . . . , m;

Output: G = (V, E);

1 foreach b_i ∈ I do
2 foreach k ∈ W do

3 if (si > LAU Tk) then

4 Tạo đỉnh bk_i với trọng số đỉnh là li := ei− si;
5 V := V ∪ {bk_i};

6 foreach (bk_i, bh_j) ∈ V do

7 if ((k 6= h) ∨ ((k = h) ∧ ([si, ei] ∩ [sj, ej] = ∅)) then
8 Tạo cạnh (bk_i, bh_j); E := E ∪ {(bk_i, bh_j)}

9 return G = (V, E);

Độ phức tạp của hàm ConstructGraph là: O(n2_)).

4.3.3.2. Tìm clique cực đại có tổng trọng số lớn nhất

Chi tiết của hàm findMWC được mô tả như sau.
Function findMWC

Input : G = (V, E);
Output: Cmax;
1 foreach v ∈ V do

2 adj(v) := {u ∈ V |(u, v) ∈ E};
3 C_max := ∅;

</div>
<span class='text_page_counter'>(22)</span><div class='page_container' data-page=22>

5 foreach (u, v) ∈ E do

6 L(u,v) := F alse; W(u,v) := 0;

7 foreach (u, v) ∈ E và L_(u,v) 6= true do
8 C_(u,v) := {u, v};

9 W_(u,v) := lu+ lv;

10 VCad := adj(u) ∩ adj(v); VCad là tập các đỉnh ứng cử viên
11 while (V_Cad 6= ∅) do

12 C_(u,v) := C_(u,v)∪ {u0} với u0 ∈ V_Cad;
13 W_(u,v) := W_(u,v)+ l_(u0₎;

14 V_Cad := V_Cad_{r {u}0};

15 Loại bỏ tất cả u1 ∈ VCad ra khỏi tập VCad nếu (u0, u1) ∈ E;
16 if (|C_(u,v)| = n) then

17 C_max := C_(u,v);
18 return C_max;

19 else

20 if (W_(u,v) > W_max) then

21 W_max := W_(u,v); C_max:= C_(u,v);
22 foreach v ∈ V do

23 if (adj(v) = ∅) then
24 C_v := v; W_v := l_v;
25 if (Wv > Wmax)) then
26 W_max := W_v; C_max := C_v;
27 return Cmax;

Độ phức tạp của hàm findMWC tìm clique cực đại Cmax có trọng số lớn nhất là

O(|E| × |V | × log |V |).

4.3.3.3. Lập lịch các chùm từ clique cực đại

C

max

Do các đỉnh (bk_i) của clique cực đại Cmax chứa đầy đủ thông tin về chùm nào được lập

lịch trên kênh nào nên giải thuật lập lịch các chùm từ clique cực đại chỉ đơn giản phân
phối mỗi chùm bi lên kênh k tương ứng.

Hàm ScheduleBurstsfromMWC được mô tả như sau:
Function scheduleBurstsfromMWC

Input : Cmax;

Output: I0;

1 foreach bk_i ∈ Cmax do

2 Lập lịch chùm b_i trên kênh thứ k;
3 I0 := I0∪ {b_i};

4 return I0;

</div>
<span class='text_page_counter'>(23)</span><div class='page_container' data-page=23>

4.3.3.4. Độ phức tạp của giải thuật MWC-GS

Độ phức tạp của giải thuật MWC-GS là O(|E| × |V | × log |V |).

4.3.3.5. Mở rộng giải thuật MWC-GS với lấp đầy khoảng trống

Giải thuật MWC-GS được mô tả ở trên chỉ xem xét đối với trường hợp không lấp đầy
khoảng trống, tức là điều kiện để lập lịch đối với một chùm đến bi trên một kênh k là thời

điểm đến của bi sau LAU T của kênh k. Tuy nhiên, trong trường hợp có lấp đầy khoảng

trống, phần băng thơng nhàn rỗi được sinh ra giữa các chùm đã được lập lịch trước đó sẽ
được xem xét để sử dụng. Cải tiến của MWC-GS với lấp đầy khoảng trống chỉ đơn giản
được thực hiện trong khi xây dựng đồ thị khoảng (hàm constructGraph). Các hàm cịn
lại, findMWC và scheduleBurstsfromMWC khơng có thay đổi nào.

Trong giải thuật MWC-GS có lấp đầy khoảng trống (with Void Filling), được gọi là
MWC-VF-GS, một chùm đến sẽ được so sánh với với khoảng trống trên mỗi kênh. Với
trường hợp có lấp đầy khoảng trống, điều kiện ở dòng 3 của hàm constructGraph được
sửa thành: (si > ekj) ∧ ((si+ li) < sk(j+1)).

4.4. Mô phỏng và phân tích kết quả

Luận án thực hiện cài đặt các mơ hình lập lịch nhóm đã đề xuất LGS-MC, MWC-GS,
MWC-VF-GS, OPT-GS và so sánh dựa trên xác suất mất gói tin và thời gian thực hiện
với các giải thuật đã được đề xuất trước đó trong mơi trường mơ phỏng được trình bày
ở mục 2.4. Các tham số mơ phỏng: τ được thiết lập 700µs. Mơ phỏng được thực hiện
từ tải lưu lượng 0.1 đến 0.9. Luận án sử dụng 2 mơ hình mạng mơ phỏng: một là mạng
Dumbbell (Hình 3.10 ở Mục 3.4) và mạng NSFNET (Hình 2.7 ở Mục 2.4).

Qua kết quả mơ phỏng được thể hiện ở Hình 4.16 đến Hình 4.22 cho thấy giải thuật
lập lịch nhóm trên đa kênh đề xuất theo hướng tiếp cận heuristic LGS-MC, MWC-GS,
MWC-VF-GS có xác xuất mất gói tin thấp hơn so với các giải thuật cùng loại đã được
công bố, bên cạnh đó độ phức tạp giải thuật khơng cao hơn. Ngoài ra giải thuật đề xuất
GS-OPT theo hướng tiếp cận tối ưu khơng làm gia tăng số lượng gói điều khiển, thay đổi
giao thức truyền thông hiện tại và thực tế có thể triển khai trên mạng thật.

Hình 4.16. So sánh xác suất mất gói tin của
LGS-MC, MWC-GS với các giải thuật heuristic

trên mơ hình mạng Dumbbell

Hình 4.17. So sánh xác suất mất gói tin của
LGS-MC, MWC-GS với các giải thuật heuristic

</div>
<span class='text_page_counter'>(24)</span><div class='page_container' data-page=24>

Hình 4.18. So sánh xác suất mất gói tin của
LGS-MC, MWC-GS với GreedyOPT

trên mơ hình mạng Dumbbell

Hình 4.19. So sánh xác suất mất gói tin của
LGS-MC, MWC-GS với GreedyOPT

trên mơ hình mạng NSFNET-14 nút

Hình 4.20. So sánh xác suất mất gói tin của
MWC-VF-GS, OPT-GS với BATCHOPT

trên mơ hình mạng Dumbbell

Hình 4.21. So sánh xác suất mất gói tin của
MWC-VF-GS, OPT-GS với BATCHOPT

trên mơ hình mạng NSFNET-14 nút

</div>
<span class='text_page_counter'>(25)</span><div class='page_container' data-page=25>

4.5. Tiểu kết Chương 4

Chương này của Luận án đã trình bày, phân tích và đánh giá chi tiết các giải thuật lập
lịch nhóm trên đa kênh ra đã được công bố của các tác giả theo hai hướng tiếp cận tối ưu
lập lịch và heuristic, từ đó đưa ra được những ưu điểm và tồn tại của các giải thuật này.
Để khắc phục những tồn tại của các giải thuật trên nhằm cải thiện tốt hoạt động
lập lịch, giảm xác suất mất mát dữ liệu và nâng cao hiệu năng băng thông, Luận án đã
xây dựng bài toán lập lịch và đề xuất 3 giải thuật lập lịch nhóm LGS-MC, MWC-GS,
MWC-VF-GS và OPT-GS dựa trên hai hướng tiếp cận heuristic và tối ưu lập lịch.

Trong đó giải thuật MWC-GS, MWC-VF-GS và OPT-GS mơ hình hố bài tốn lập
lịch nhóm trên đa kênh qua bài tốn tìm clique cực đại và tìm đường đi trên đơn đồ thị
khoảng vơ hướng có trọng số và đơn đồ thị có hướng có trọng số.

</div>
<span class='text_page_counter'>(26)</span><div class='page_container' data-page=26>

KẾT LUẬN

Chuyển mạch chùm quang (OBS) trên mạng WDM được xem là một công nghệ đầy
triển vọng đối với mạng Internet thế hệ tiếp theo, bởi vì mạng OBS khắc phục được những

hạn chế về cơng nghệ của chuyển mạch gói quang hiện tại và khai thác băng thông linh
hoạt, tốt hơn hơn chuyển mạch kênh quang. Tuy nhiên như các loại mạng chuyển mạch
gói khác, tắc nghẽn có thể xảy ra khi một gói điều khiển đến yêu cầu lập lịch cho chùm
của nó nhưng khơng tìm kênh khả dụng; trong trường hợp này chùm đến sẽ bị đánh rơi.
Vì vậy vấn đề lập lịch trong mạng OBS rất quan trọng trong việc giảm mất mát dữ liệu
và tăng hiệu suất của mạng. Với mục đích đó Luận án đã tập trung nghiên cứu các mơ
hình, giải thuật lập lịch trong mạng OBS với các hướng tiếp cận khác nhau. Kết quả mà
Luận án đã đạt được bao gồm:

1. Tổng hợp phân tích, đánh giá và phân lớp các giải thuật lập lịch đã được công bố
theo các hướng tiếp cận khác nhau trong mạng OBS. Qua đó đưa ra được những
ưu điểm và tồn tại của các giải thuật và đây chính là cơ sở để đề xuất và cải tiến
các giải thuật lập lịch nhằm tối thiểu mất mát dữ liệu, tối đa hiệu suất băng thông,
giảm độ trễ và giảm độ phức tạp tính tốn.

2. Đề xuất giải thuật lập lịch iCSA kết hợp giữa lập lịch trực tiếp, cải tiến lập lịch lại
và kỹ thuật phân đoạn chùm. Kết quả cài đặt mô phỏng đã chứng minh giải thuật
lập lịch đề xuất iCSA có xác suất mất gói tin thấp hơn và giảm số lượng chùm bị
phân đoạn so với các giải thuật đã được công bố trước đó[CT2].

3. Đề xuất giải thuật lập lịch nhóm trên đơn kênh LGS và các giải thuật lập lịch cải
tiến LGS-VF và LAGS-VF có độ phức tạp thấp hơn so với các giải thuật lập lịch
nhóm đã được cơng bố trước đó. Kết quả cài đặt mơ phỏng đã chỉ ra rằng giải thuật
lập lịch nhóm đề xuất có xác suất mất gói tin thấp hơn các giải thuật lập lịch cùng
loại. Bên cạnh đó, giải thuật LAGS và LAGS-VF còn cải thiện đáng kể độ trễ nên
mang lại hiệu quả lâu dài đối với các hoạt động lập lịch tại các nút khác và các hoạt
động truyền thông khác trong mạng[CT4], [CT5], [CT7], [CT8].

</div>
<span class='text_page_counter'>(27)</span><div class='page_container' data-page=27>

DANH MỤC CÁC CƠNG TRÌNH

LIÊN QUAN ĐẾN LUẬN ÁN

CT1. 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.

CT2. Vo Viet Minh Nhat, Nguyen Hong Quoc. An Improved Composite Scheduling Approach for
Reducing Data Loss in OBS Networks. Proceeding of SoICT 2015 (ACM ICPS,
ISBN:978-1-4503-3843-1), pp: 143-148.

CT3. Vo Viet Minh Nhat, Nguyen Hong Quoc, Nguyen Hoang Son. A Group Scheduling
Al-gorithm 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)

CT4. 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.

CT5. Vo Viet Minh Nhat, Nguyen Hong Quoc. A Model of Adaptive Grouping Scheduling in
OBS Core Nodes. Journal of Convergence, 2014, Vol: 5, No: 1, pp: 9-13.

CT6. Vo Viet Minh Nhat, Nguyen Hong Quoc, Nguyen Hoang Son. Group Scheduling for
Multi-Channel in OBS Networks. REV Journal on Electronics and Communications, 2014, Vol:
3, No: 3–4, pp: 134-137.

CT7. Vo Viet Minh Nhat, Nguyen Hong Quoc, Nguyen Hoang Son. A New Algorithm of Group
Scheduling in OBS Core Nodes. Proceedings of IEEE 2013 International Conference on
Advanced Technologies for Communications (ATC2013), 2013, pp: 592-596.

</div>

<!--links-->