Luận án 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

ĐẠI HỌC HUẾ

TRƯỜNG ĐẠI HỌC KHOA HỌC

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

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

HUẾ - NĂM 2017

ĐẠI HỌC HUẾ

TRƯỜNG ĐẠI HỌC KHOA HỌC

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

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

Người hướng dẫn khoa học:

PGS. TS. VÕ VIẾT MINH NHẬT

TS. NGUYỄN HOÀNG SƠN

HUẾ - NĂM 2017

LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu do tôi thực hiện dưới sự hướng dẫn

của PGS. TS. Võ Viết Minh Nhật và TS. Nguyễn Hoàng Sơn. Những nội dung trong

các công trình đã được công bố chung với các tác giả khác đã được sự đồng ý của đồng

tác giả khi đưa vào Luận án. Các số liệu và kết quả nghiên cứu được trình bày trong

Luận án là trung thực, khách quan và chưa được công bố bởi tác giả nào trong bất kỳ

công trình nào khác.

Nghiên cứu sinh

Nguyễn Hồng Quốc

i

LỜI CẢM ƠN

Trước hết tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc đến PGS. TS. Võ Viết

Minh Nhật và TS. Nguyễn Hoàng Sơn là những người Thầy đã tận tình hướng dẫn chỉ

bảo, động viên và giúp đỡ để tôi có thể hoàn thành được Luận án này.

Tôi xin trân trọng cảm ơn sự giúp đỡ của Quý Thầy Cô trong Khoa Công nghệ

Thông tin - Trường Đại học Khoa học, Đại học Huế đã quan tâm, giúp đỡ, hướng dẫn

trong suốt quá trình học tập.

Tôi xin chân thành cảm ơn Quý Thầy Cô, Ban chủ nhiệm Khoa Tin học - Trường

Đại học Sư phạm, Đại học Huế đã tạo điều kiện thuận lợi trong công tác để tôi có

đủ thời gian hoàn thành Luận án này. Tôi xin cảm ơn Quý Thầy Cô, cán bộ quản lý

phòng Đào tạo Sau Đại học - Trường Đại học Khoa học, Đại học Huế đã giúp đỡ tôi

hoàn thành kế hoạch học tập.

Cuối cùng tôi xin chân thành cảm ơn các bạn đồng nghiệp, người thân trong gia

đình luôn động viên, giúp đỡ tôi về mọi mặt trong suốt quá trình học tập, nghiên cứu.

Nghiên cứu sinh

Nguyễn Hồng Quốc

ii

MỤC LỤC

Lời cam đoan

i

ii

Lời cảm ơn

Mục lục

iii

v

Danh mục các từ viết tắt

Danh mục bảng biểu

Danh mục hình vẽ

Mở đầu

vii

viii

1

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

MẠCH CHÙM QUANG

7

9

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

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

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

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

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

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

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

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

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

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

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

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

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

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

37

2.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

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ố . . . . 37

2.2.1 Giải thuật ODBR . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.2.2 Giải thuật ABR . . . . . . . . . . . . . . . . . . . . . . . . . . 39

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

2.2.4 Giải thuật SODBRA . . . . . . . . . . . . . . . . . . . . . . . . 42

2.2.5 Giải thuật PCSA . . . . . . . . . . . . . . . . . . . . . . . . . . 42

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

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

iii

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

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

55

3.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

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ố . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.2.1 Giải thuật OBS-GS . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.2.2 Giải thuật MWIS-OS . . . . . . . . . . . . . . . . . . . . . . . . 57

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

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

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

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

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

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

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

72

4.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

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ố . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

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

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

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

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

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

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

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

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

KẾT LUẬN

102

104

105

DANH MỤC CÁC CÔNG TRÌNH LIÊN QUAN ĐẾN LUẬN ÁN

TÀI LIỆU THAM KHẢO

iv

DANH MỤC CÁC TỪ VIẾT TẮT

Viết tắt

ADM

Dạng đầy đủ

Add-Drop Multiplexer

All-Optical Network

Diễn giải ý nghĩa

Bộ thêm/trích kênh

Mạng toàn quang

AON

ATM

Asynchronous Transfer Mode

Burst Header Packet

Chế độ truyền tải không đồng bộ

Gói điều khiển

BHP

CWDM

Coarse Wavelength Division Mul- Ghép kênh phân chia bước sóng

tiplexing thô

DWA

Dynamic Wavelength Allocation Phân bổ bước sóng động

DWDM

Density Wavelength Division Ghép kênh phân chia bước sóng

Multiplexing

mật độ cao

FDL

Fiber Delay Line

Đường trễ quang

FDM

Frequency Division Multiplexing Ghép kênh phân chia tần số

GMPLS Generalized Multiprotocol Label Chuyển mạch nhãn đa giao thức

Switching

suy rộng

JET

Just Enough Time

Giao thức báo hiệu với thời gian

đặt trước tài nguyên vừa đủ

Giao thức báo hiệu với thời gian

đặt trước tức thời

JIT

Just In Time

LAUT

LRWC

Latest Available Unscheduled Thời điểm chưa được lập lịch sau

Time cùng nhất

Limited-Range Wavelength Con- Bộ chuyển đổi bước sóng có phạm

verter

vi giới hạn

MPLS

MWC

O/E/O

OADM

OBS

MultiProtocol Label Switching

Optical/Electronic/Optical

Maximum Weight Clipue

Optical/Electronic/Optical

Optical Add-Drop Multiplexer

Optical Burst Switching

Optical Circuit Switching

Chuyển mạch nhãn đa giao thức

Chuyển đổi quang-điện-quang

Clique có tổng trọng số lớn nhất

Chuyển đổi quang-điện-quang

Bộ thêm/trích kênh quang

Chuyển mạch chùm quang

Chuyển mạch kênh quang

OCS

OEO

Optical-Electrical-Optical con- Chuyển đổi quang-điện-quang

version

v

Viết tắt

OPS

Dạng đầy đủ

Optical Packet Switching

Optical Transport Network

Diễn giải ý nghĩa

Chuyển mạch gói quang

Mạng truyền tải quang

OTN

OTDM

Optical Time Division Multiplex- Ghép kênh quang phân chia thời

ing

gian

OXC

QoS

Optical Cross Connect

Quality of Service

Chuyển mạch quang

Chất lượng dịch vụ

ROADM Reconfigurable Optical Add-Drop Bộ thêm/trích kênh quang có thể

Multiplexer

cấu hình lại

RTT

RAM

RWA

Round-Trip Time

Random Access Memory

Thời gian khứ hồi

Bộ nhớ truy cập ngẫu nhiên

Routing and Wavelength Alloca- Định tuyến và cấp phát bước sóng

tion

SCU

Switching Control Unit

Synchronous Digital Hierarchy

Space Division Multiplexing

Source Initiated Reservation

Synchronous Optical Network

Share-Per-Link

Đơn vị điều khiển chuyển mạch

Hệ phân cấp số đồng bộ

Ghép kênh phân chia không gian

Đặt tài nguyên từ nguồn

Mạng quang đồng bộ

SDH

SDM

SIR

SONET

SPL

Chia sẻ trên mỗi liên kết

Chia sẻ trên mỗi nút

SPN

Share-Per-Node

WADM

Wavelength Add-Drop Multi- Bộ thêm/trích bước sóng

plexer

WC

Wavelength Converters

Bộ chuyển đổi bước sóng

WDM

Wavelength Division Multiplex- Ghép kênh phân chia bước sóng

ing

WR

Wavelength Router

Định tuyến bước sóng

WRN

WXC

Wavelength Routed Network

Wavelength Cross-Connect

Mạng định tuyến bước sóng

Chuyển mạch bước sóng

vi

DANH MỤC BẢNG BIỂU

1.1 So sánh chuyển mạch chùm quang với chuyển mạch kênh quang và

chuyển mạch gói quang . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4.1 Thống kê số chùm được gỡ ra và lập lịch lại thành công của giải thuật

GreedyOPT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

vii

DANH MỤC HÌNH VẼ

1.1 Kiến trúc mạng chuyển mạch kênh quang . . . . . . . . . . . . . . . . . 10

1.2 Kiến trúc mạng OBS và chức năng của các nút mạng . . . . . . . . . . 15

1.3 Cấu trúc nút biên vào OBS . . . . . . . . . . . . . . . . . . . . . . . . 16

1.4 Cấu trúc nút lõi OBS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.5 Tập hợp theo ngưỡng thời gian . . . . . . . . . . . . . . . . . . . . . . . 18

1.6 Tập hợp theo ngưỡng kích thước (số gói tin tối đa) . . . . . . . . . . . . 18

1.7 Ảnh hưởng của phương pháp tập hợp chùm theo ngưỡng thời gian và

ngưỡng độ dài đối với kích thước chùm được sinh ra . . . . . . . . . . . 19

1.8 Đồ thị khoảng G được xây dựng từ tập các khoảng thời gian chồng lấp

nhau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

1.9 Đồ thị khoảng G được xây dựng từ tập các khoảng thời gian không chồng

lấp nhau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

1.10 Mô tả các giải thuật lập lịch trực tiếp . . . . . . . . . . . . . . . . . . . 26

1.11 Ví dụ so sánh hiệu quả giữa lập lịch trực tiếp và lập lịch nhóm: (a) các

gói điều khiển và chùm đến trong khe thời gian τ, (b) kết quả của lập

lịch trực tiếp và (c) kết quả của lập lịch nhóm dựa trên tối đa tổng số

chùm được lập lịch và (d)dựa trên tối đa tổng độ dài của các chùm được

lập lịch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

1.12 Phân loại các giải thuật lập lịch nhóm đã được công bố . . . . . . . . . 32

1.13 Mô tả giải pháp chuyển đổi bước sóng w₁qua w₂. . . . . . . . . . . . . 33

1.14 Mô tả giải pháp định tuyến lệch hướng . . . . . . . . . . . . . . . . . . 34

2.1 Một ví dụ về lập lịch lại của giải thuật ODBR . . . . . . . . . . . . . . 38

2.2 Một ví dụ cơ chế hoạt động của giải thuật lập lịch lại ABR . . . . . . . 40

2.3 Phân đoạn chùm và cấu trúc bên trong của header của đoạn . . . . . . 41

2.4 Trong trường hợp chùm tranh chấp bị phân đoạn, có 2 khá năng xảy ra:

(a) loại bỏ đoạn đuôi và (b) loại bỏ đoạn đầu của chùm tranh chấp . . . 41

2.5 Ví dụ một chùm đến ub yêu cầu lập lịch trên 3 kênh ra . . . . . . . . . 43

2.6 Ví dụ về một trường hợp giải thuật ODBR không thực hiện được . . . 44

2.7 Mô hình mạng mô phỏng NSFNET . . . . . . . . . . . . . . . . . . . . 48

2.8 So sánh xác suất mất gói tin của LAUC và BFVF . . . . . . . . . . . . 49

2.9 So sánh xác suất mất gói tin của ODBR và ABR . . . . . . . . . . . . 50

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

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

viii

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

2.13 So sánh xác suất mất gói tin của iCSA so với PCSA và SODBRA . . . 52

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

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

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

3.2 Các gói điều khiển đến trong khe thời gian τ, tương ứng với thứ tự đến

của các chùm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.3 (a)Đồ thị khoảng được xây dựng tương ứng trạng thái các chùm đến và

(b)Kết quả tìm tập các tập độc lập cực đại của giải thuật OBS-GS . . . 57

3.4 Kết quả tìm tập các tập độc lập cực đại của giải thuật MWIS-OS . . . 58

3.5 So sánh xác suất mất gói tin của OBS-GS và MWIS-OS . . . . . . . . 58

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

3.7 Ví dụ Các gói điều khiển đến trong thời gian τ và thứ tự đến của các

chùm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

3.8 (a) Thứ tự các chùm sau khi sắp xếp theo thời điểm kết thúc và (b) cách

tính index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

3.9 Khe thời gian lập lịch nhóm τ được điều chỉnh nghịch biến với tốc độ

của luồng các chùm đến . . . . . . . . . . . . . . . . . . . . . . . . . . 64

3.10 Mô hình mạng mô phỏng Dumbbell . . . . . . . . . . . . . . . . . . . . 67

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

3.12 So sánh xác suất mất gói tin giữa OBS-GS, MWIS-OS, LGS và LGS-VF 68

3.13 So sánh thông lượng của OBS-GS, MWIS-OS và LGS-VF . . . . . . . 69

3.14 So sánh xác suất mất gói tin giữa LGS-VF và LAGS-VF . . . . . . . 69

3.15 Phân bố độ rộng khe thời gian τ của MWIS-OS và LAGS-VF trong 300

lần lập lịch nhóm liên tiếp . . . . . . . . . . . . . . . . . . . . . . . . . 70

3.16 So sánh thời gian chờ trung bình (của từng 500 khe liên tiếp) của MWIS-

OS và LAGS-VF (trong 7500 lần lập lịch nhóm liên tiếp) . . . . . . . 70

4.1 (a) Ví dụ tình trạng các gói điều khiển đến lập lịch cho các chùm trong

mỗi khe thời gian τ, và (b) kết quả lập lịch của giải thuật SSF . . . . . 73

4.2 (a) Ví dụ tình trạng các gói điều khiển đến lập lịch cho các chùm trong

mỗi khe thời gian τ, và (b) kết quả lập lịch của giải thuật LIF . . . . . 74

4.3 Đồ thị khoảng được xây dựng từ trạng thái các chùm đến ở Hình 4.1(a)

75

4.4 Ví dụ 3 chùm đến yêu cầu lập lịch trên 2 kênh dữ liệu ra . . . . . . . . 78

4.5 Đồ thị khoảng được xây dựng từ trạng thái các chùm đến và các chùm

đã lập lịch trong Hình 4.4 . . . . . . . . . . . . . . . . . . . . . . . . . 79

4.6 Kết quả các clique cực đại được tìm thấy từ đồ thị khoảng trong Hình 4.5 79

4.7 Đồ thị luồng được xây dựng từ các clique cực đại trong Hình 4.6 . . . . 80

ix

4.8 Ví dụ 6 chùm đến yêu cầu lập lịch trên hai kênh ra . . . . . . . . . . . 80

4.9 (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 . . . . . 84

4.10 Đơn đồ thị có hướng có trọng số được xây dựng từ tập các chùm đến lập

lịch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

4.11 (a) Ví dụ về các chùm đến và (b) kết quả lập lịch tối ưu trên 2 kênh . . 89

4.12 (a)Đồ thị khoảng biểu diễn các khả năng lập lịch của các chùm đến trong

Hình 4.11a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

4.13 (b)MWC được tìm thấy tương ứng với kết quả lập lịch tối ưu trong Hình

4.11b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

4.14 (a)Ví dụ về các chùm đến và (b) kết quả lập lịch tối ưu có lấp đầy khoảng

trống trên 2 kênh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

4.15 (a) Đồ thị khoảng biểu diễn các khả năng lập lịch có lấp đầy khoảng

trống của các chùm đến trong Hình 4.14a và (b) Clique được tìm thấy

tương ứng với kết quả lập lịch trong Hình 4.14b . . . . . . . . . . . . . 95

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

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 trên mô hình mạng NSFNET-14 nút . . . . . . . . . . . . . . 97

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

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

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

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

4.22 So sánh ảnh hưởng của kích thước khe thời gian τ đến hiệu quả lập lịch

nhóm của MWC-VF-GS, OPT-GS với BATCHOPT . . . . . . . . . . . 101

x

MỞ ĐẦU

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

Tốc độ phát triển nhanh của Internet trong những năm gần đây, cùng với sự

bùng nổ của các loại hình dịch vụ truyền thông, đã làm gia tăng không ngừng

nhu cầu về băng thông truyền thông. Điều này đã đặt ra một thách thức mới

trong việc tìm kiếm công nghệ truyền thông phù hợp nhằm nâng cao khả năng

vận chuyển của mạng thế hệ mới. Mạng sợi quang cùng với sự phát triển của

công nghệ ghép kênh bước sóng (Wavelength Division Multiplexing), đã mang

đến một giải pháp hoàn hảo đáp ứng được nhu cầu băng thông bùng nổ của

Internet trong tương lai.

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 [46], [64], [27], [24], [31], [12]: từ những mô hình định

tuyến bước sóng (Wavelength-Routed) 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) đượ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 [8] [12], 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) đã 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) được tách rời với phần (chùm)

dữ liệu (Data Burst). 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 toán

đủ để đặt trước tài nguyên 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. Thêm vào đó, mạng

1

OBS dành riêng một số kênh (bước sóng), được gọi là kênh điều khiển cho việc

truyền gói điều khiển BHP, trong khi các kênh còn lại được dùng cho việc truyền

chùm dữ liệu, nên được gọi là kênh dữ liệu. Như vậy việc truyền gói điều khiển

BHP tách rời hoàn toàn với truyền dữ liệu về mặt không gian (trên kênh truyền

khác) và về mặt thời gian (gửi đi trước một khoảng thời gian offset). Với cách

truyền dữ liệu như vậy, rõ ràng mạng OBS không cần đến các bộ đệm quang để

lưu tạm các chùm dữ liệu trong khi chờ đợi việc xử lý chuyển mạch tại các nút

lõi, cũng như không yêu cầu các chuyển mạch ở tốc độ nano giây. 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ột kênh bước sóng được gọi khả

dụng khi và chỉ khi thời điểm đến của chùm lập lịch lớn hơn LAUT hoặc thời

gian đến của chùm nằm trong một khoảng trống (khoảng băng thông nhàn rồi

trên một kênh nào đó). 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 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.

Đối với phương pháp lập lịch trực tiếp khi một gói điều khiển đến một nút

2

lõi mạng, một trong các giải thuật lập lịch trực tiếp [30], [74], [72], [71], [38], [11],

[68], [18], [42], [6], [13], [2] sẽ được gọi ngay để 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 thì

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. Trong số các giải thuật lập lịch trực tiếp, BF-VF [42] 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à ở đó 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 [55], [56], [49], [40], [66], [65], [57],

[67], [54], [28], [39]. 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 nhàn

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 [25], [75], [15], [29], [9], [22], [21], [20] 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 toá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

3

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

toá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 toán. Mục tiêu cụ thể của Luận án là:

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

• 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

4. Đố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 OBS.

• Phạm vi nghiên cứu: Nút lõi mạng OBS.

5. Phương pháp nghiên cứu

• Phương pháp nghiên cứu lý thuyết: Tổng hợp các công bố liên quan đến các

mô hình, giải thuật lập lịch trong mạng OBS. Phân tích, đánh giá ưu và

khuyết điểm của các công trình đã công bố để làm cơ sở cho việc cải tiến

hoặc đề xuất mới. Đề xuất các giải thuật lập lịch trực tiếp kết hợp, lập lịch

nhóm trên đơn kênh và đa kênh ra nhằm nâng cao hiệu năng mạng, bao

gồm: giảm xác suất mất dữ liệu, tăng mức độ sử dụng băng thông, giảm

độ trễ đầu cuối và giảm độ phức tạp tính toán. Chứng minh tính đúng đắn

và tính toán độ phức tạp của các giải thuật được cải tiến và đề xuất mới.

• Phương pháp mô phỏng, thực nghiệm: Cài đặt các giải thuật cải tiến và đề

xuất mới nhằm chứng minh hiệu quả của các giải thuật này. Hệ mô phỏng

NS2, gói mô phỏng obs-0.9a được sử dụng để tạo dữ liệu mô phỏng và các

giải thuật lập lịch được cài đặt bằng ngôn ngữ C++.

6. Nội dung và bố cục của luận án

Nội dung của Luận án bao gồm mở đầu, bốn chương nội dung, phần kết

luận, danh mục các công trình liên quan đến Luận án và danh mục tài liệu tham

khảo. Bốn chương nội dung cụ thể như sau:

• Chương 1: "Tổng quan về lập lịch trong mạng chuyển mạch chùm quang"

trình bày các kiến thức cơ bản về mạng chuyển mạch chùm quang bao

gồm lịch sử phát triển của truyền thông quang, các mô hình chuyển mạch

quang, kiến trúc mạng chuyển mạch chùm quang, các hoạt động bên trong

mạng và tổng quan về các hướng tiếp cận lập lịch trong mạng chuyển mạch

chùm quang.

• 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" trình bày tổng hợp các nghiên cứu trước đây về

5

mô hình 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.

Trên cơ sở các phân tích, so sánh và đánh giá, Luận án đề xuất một cải

tiến 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 nhằm

giảm xác suất mất gói tin, giảm số chùm phải lập lịch lại và giảm số chùm

bị phân đoạn.

• 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" trình

bày tổng hợp các nghiên cứu liên quan đến lập lịch nhóm trong trường hợp

không sử dụng chuyển đổi bước sóng. Trên cơ sở các phân tích, so sánh và

đánh giá, Luận án xây dựng mô hình lập lịch nhóm, đề xuất một số giải

thuật cải tiến về lập lịch nhóm trên đơn kênh nhằm nâng cao hiệu suất lập

lịch bao gồm: giảm xác suất mất mát dữ liệu, giảm độ phức tạp giải thuật

và tăng tính thích nghi mô hình lập lịch chuyển biến theo lưu lượng chùm

đến.

• 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" trình

bày tổng hợp, phân tích, so sánh và đánh giá các nghiên cứu liên quan đến

lập lịch nhóm có sử dụng bộ chuyển đổi bước sóng đầy đủ. Từ đó Luận

án đề xuất một số giải thuật lập lịch nhóm trên đa kênh theo hai hướng

tiếp cận: tối ưu kết quả lập lịch và heuristic nhằm nâng cao hiệu suất lập

lịch bao gồm: giảm xác suất mất mát dữ liệu, giảm độ phức tạp giải thuật,

giảm độ phức tạp hệ thống và thực tế có thể triển khai trên mạng OBS.

7. Đó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.

6

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

Trong hơn hai thập kỷ qua, mạng truyền thông đã có một sự tăng trưởng

mạnh mẽ. Việc mở rộng nhanh chóng phạm vi bao phủ, cùng với sự bùng nổ

các loại hình dịch vụ yêu cầu nhiều băng thông cao như truyền hình Internet

(IPTV ), video theo yêu cầu (VoD), điện thoại Internet (VoIP). . . đã làm tăng

áp lực nhu cầu băng thông mạng; trong khi khả năng truyền tải của sợi cáp

đồng đã đạt đến ngưỡng tới hạn. Điều này đòi hỏi phải phát triển những công

nghệ truyền dẫn mới có khả năng đáp ứng những nhu cầu ngày càng cao không

chỉ cho hiện tại mà cho cả tương lai.

Mạng sợi quang [27], [8], [31] đã được công nhận như một giải pháp tốt nhất

có thể đáp ứng những yêu cầu của các dịch vụ băng thông cao nhờ vào những

đặc tính có lợi của sợi quang, như độ suy giảm thấp, tiềm năng băng thông rất

lớn và khả năng miễn nhiễm đối với nhiễu điện từ. Theo lý thuyết mỗi sợi dẫn

quang (hay sợi quang) có thể hỗ trợ băng thông lên đến 50Tb/s [31]. Ngoài ra

sợi quang có chi phí sản xuất và độ lỗi bit khá thấp (khoảng 10⁻²dB).

Quá trình phát triển của mạng sợi quang có thể chia thành 3 giai đoạn chính.

Thế hệ đầu tiên của mạng sợi quang bao gồm các liên kết WDM điểm-nối-điểm

(point-to-point WDM links), mà tại đó tín hiệu quang đến tại một nút được

chuyển đổi từ quang sang điện (Optical-to-Electrical), được xử lý trong miền

điện và được chuyển đổi ngược lại từ điện sang quang (Electrical-to-Optical)

trước khi truyền đến nút khác. Việc tách (dropping) và thêm (adding) lưu lượng

tại các nút trong mạng do đó phải chịu thêm độ phức tạp và chi phí xử lý điện

tử, đặc biệt phần lớn các lưu lượng chỉ chuyển tiếp qua các nút này. Để giảm

thiểu chi phí, các thiết bị toàn quang (all-optical) có thể được sử dụng.

7

Kiến trúc mạng quang thế hệ thứ hai dựa trên các bộ thêm/tách bước sóng

(Wavelength Add-Drop Multiplexers) [37], [12], [31], trong đó lưu lượng có thể

được thêm và tách tại các bộ WADM. Các bộ WADM cho phép lựa chọn kênh

bước sóng kết thúc tại nút này trên một sợi quang, trong khi để các bước sóng

khác chuyển tiếp qua mà không chịu một xử lý nào. Nhìn chung, lượng lưu chuyển

tiếp qua các nút trong mạng phổ biến hơn so với lượng lưu được thêm/tách tại

một nút cụ thể. Do đó, bằng cách sử dụng các bộ WADM, tổng chi phí của

mạng có thể được giảm. Các bộ WADM chủ yếu được sử dụng để xây dựng các

mạng WDM hình vòng (ring), loại mạng dự kiến sẽ được triển khai tại các khu

vực đô thị.

Việc xây dựng một mạng hình lưới (mesh) bao gồm các sợi quang hỗ trợ đa

bước sóng và các thiết bị kết nối sợi quang thích hợp là cần thiết. Kiến trúc

mạng quang thế hệ thứ ba dựa trên các thiết bị kết nối toàn quang. Các thiết

bị này có thể chia thành 3 nhóm: các bộ chia hình sao thụ động (passive star

couplers), các bộ định tuyến thụ động (passive routers) và các bộ chuyển mạch

chủ động (active switches). Các bộ chia hình sao là một thiết bị phát sóng. Một

tín hiệu đến trên một bước sóng nào đó tại một cổng vào của bộ chia sẽ được

chia đều về mặt năng lượng (power) đến tất cả các cổng ra. Một bộ định tuyến

thụ động có thể định tuyến một cách riêng biệt mỗi bước sóng đến trên một

sợi quang vào đến một sợi quang ra trên cùng bước sóng. Bộ định tuyến thụ

động là một thiết bị tĩnh, do đó cấu hình tuyến cố định. Một chuyển mạch chủ

động cũng định tuyến các bước sóng từ sợi quang vào đến sợi quang ra và có

thể hỗ trợ nhiều kết nối đồng thời. Không giống như bộ định tuyến thụ động,

bộ chuyển mạch chủ động có thể được cấu hình lại để thay đổi mô hình kết nối

của các bước sóng vào và ra. Trong các mạng quang thế hệ thứ ba, dữ liệu được

phép chuyển tiếp qua các nút trung gian mà không trải qua bất kỳ một chuyển

đổi quang-điện-quang (Optical-Electrical-Optical) nào, do đó làm giảm chi phí

liên quan đến việc cung cấp các chuyển mạch và định tuyến điện tử tốc độ cao

tại mỗi nút.

Các hệ thống mạng toàn quang đang nổi lên, dự kiến sẽ cung cấp các kết nối

chuyển mạch kênh quang (Optical Circuit Switching) hoặc đường quang(lightpaths)

giữa các bộ định tuyến biên qua một mạng lõi quang [37], [3]. Bởi vì các kết

8