ỨNG DỤNG PHƢƠNG PHÁP TÌM CLIQUE CỰC ĐẠI VÀO TỐI ƢU
HOÁ LẬP LỊCH NHÓM TRÊN MẠNG CHUYỂN MẠCH CHÙM QUANG
Nguyễn Hồng Quốc, Dƣơng Phƣớc Đạt, Nguyễn Chí Công, Võ Viết Minh Nhật
Đại học Huế
Tóm tắt: Lập lịch nhóm trên mạng chuyển mạch chùm quang đã được xem l| một giải ph{p hiệu quả nhằm tối đa
số chùm đến được lập lịch tại một nút lõi OBS, v| do đó giảm đ{ng kế lượng dữ liệu bị đ{nh rơi. Đã có một số đề xuất về
lập lịch nhóm như OBS-GS, MWIS-OS, LGS đối với một kênh ra (không có chuyển đổi bước sóng) v| như SSF, LIF, SLV,
MCF, GreedyOPT, BATCHOPT, LGS-MC đối với đa kênh ra (với hỗ trợ của c{c bộ chuyển đổi bước sóng ho|n to|n). B|i
viết n|y sẽ đề xuất một hướng tiếp cận mới ứng dụng một phương ph{p tìm clique cực đại có tổng trọng số lớn nhất v|o
tối ưu ho{ lập lịch nhóm c{c chùm đến trên đa kênh ra tại nút lõi mạng OBS.
Từ khóa: Mạng OBS, lập lịch nhóm, tối ưu hóa, clique cực đại, tổng trọng số lớn nhất.

1.

Giới thiệu
Chuyển mạch chùm quang (Optical Burst Switching, OBS) được xem l| một thay thế hiệu quả của

chuyển mạch gói, khi m| cần có một sự chuyển dịch từ chuyển mạch kênh quang sang chuyển mạch gói
quang nhằm khai th{c tốt hơn tiềm năng băng thông của c{c sợi dẫn quang. Hơn nữa, với những hạn chế
của công nghệ quang hiện nay, như chưa thể sản xuất c{c bộ đệm quang (như bộ nhớ RAM) v| c{c chuyển
mạch quang tốc độ nano gi}y, kỹ thuật OBS được xem như l| một mô hình khả thi nhất đối với chuyển
mạch gói quang trong một tương lại gần *1+.
Một đặc trưng quan trọng của mạng OBS l| gói điều khiển (Burst Header Packet, BHP) được gửi đi
trước trên một kênh điều khiển d|nh riêng để đặt trước t|i nguyên; sau một khoảng thời gian bù đắp (offsettime), chùm dữ liệu tương ứng mới được gửi theo sau trên một trong những kênh dữ liệu khả dụng. Bởi vì
t|i nguyên đã được đặt trước bởi gói điều khiển BHP, chùm dữ liệu sẽ không chịu một chờ đợi n|o tại mỗi
nút trung gian, nên không cần bộ đệm quang. Mặt kh{c, kích thước của chùm l| kh{ lớn so với c{c gói được
mạng bên trong, nên việc sử dụng c{c chuyển mạch có tốc độ micro gi}y sẽ không l|m giảm quả sử dụng
băng thông. Tuy nhiên, c{ch truyền thông n|y cũng đặt ra {p lực đối với việc l|m thế n|o để một gói điều
khiển BHP đặt trước t|i nguyên v| cấu hình chuyển mạch th|nh công tại c{c nút lõi, đảm bảo cho việc
truyền tải chùm quang đi sau đó. Hoạt động đặt trước t|i nguyên nêu trên thực tế l| một phần của tiến trình
lập lịch *1+.

Một số khái niệm
Cho một đồ thị

trong đó

l| tập c{c đỉnh v|

chúng ta định nghĩa l{ng giềng của u l|
hiệu l|

, l| kích thước của tập

Một clique của một đồ thị
không tồn tại clique

khác trong

l| tập c{c cạnh của G. Với một đỉnh
. Bậc của một đỉnh

,

trong đồ thị G, ký

.

l| một tập
sao cho

sao cho

OBS trở th|nh b|i to{n x{c định một tập I’I tương thích nhau sao cho tổng trọng số (chiều d|i của c{c chùm
được lập lịch) l| lớn nhất.

3.

Các nghiên cứu trƣớc đây
Đã có một số mô hình lập lịch nhóm trên mạng OBS được đề xuất bao gồm:
Hướng tiếp cận heuristics được đề xuất trong *4+ gồm 4 giải thuật: SSF (Smallest Start-time First), LIF

(Largest Interval First), SLV (Smallest-Last Vertex), và MCF (Maximal Cliques First), mà mục đích của chúng l|
tìm kiếm một thứ tự hợp lý của c{c chùm đến v| dựa trên đó giải thuật LAUC-VF được gọi để lập lịch chúng
lên các kênh bước sóng ra.
Đầu tiên, SSF sắp xếp c{c chùm dựa trên thời gian đến của chúng. C{ch l|m n|y đơn giản nhưng
không đảm bảo một kế hoạch tối ưu được tìm thấy. Cải tiến hơn, LIF sắp xếp c{c chùm đến dựa trên trọng
số (độ d|i) của chúng v| chọn chùm lớn nhất để lập lịch trước. C{ch l|m n|y rõ r|ng nhằm tối đa tổng trọng
số c{c chùm được lập lịch, nhưng thực tế c{ch sắp xếp thứ tự n|y cũng không đảm bảo đạt đến một kế
hoạch tối ưu (xem hình 1).
Với SLV, đầu tiên một đồ thị khoảng G được x}y dựng v| dựa trên đó c{c chùm đến được sắp xếp
giảm dần theo bậc của c{c đỉnh tương ứng. SLV cho rằng chùm tương ứng với đỉnh có bậc lớn nhất sẽ l|
chùm d|i nhất vì nó chồng lấp với nhiều chùm kh{c nhất. Tuy nhiên, điều n|y không phải luôn luôn đúng
trong thực tế, nên kết quả lập lịch của SLV cũng không tốt hơn LIF (xem hình 1).
Tương tự SLV, MCF đầu tiên cũng x}y dựng một đồ thị khoảng G v| sau đó cố gắng tô G với m m|u
(số m|u bằng số kênh dữ liệu khả dụng). Để l|m được điều đó, MCF tìm tất cả c{c clique cực đại có kích
thước lớn hơn m. Với clique cực đại có thời gian bắt đầu sớm nhất, MCF loại bỏ c{c đỉnh có thời gian kết
thúc sớm nhất cho đến khi kích thước của clique bằng hoặc nhỏ hơn m. Việc loại bỏ đỉnh n|y rõ r|ng sẽ l|m
ảnh hưởng đến kích thước của c{c clique cực đại kh{c, nên MCF phải lặp lại tiến trình trên cho đến khi
không tìm thấy clique cực đại n|o có kích thước lớn hơn m. Hiệu quả của MCF chủ yếu đến từ c{ch loại bỏ
đỉnh trong c{c clique có kích thươc lớn hơn m. Tuy nhiên việc chọn đỉnh có thời gian kết thúc sớm nhất, vì
cho rằng tương ứng với chùm ngắn nhất, thực tế không đảm bảo một kế hoạch tối ưu sẽ đạt được (xem hình
2).

0.4

0.5

0.04277 0.051224 0.059742 0.06465

0.6

0.7

0.8

0.065941 0.064961 0.062219

Rõ r|ng c{ch l|m n|y giúp BATCHOPT đạt đến một lời giải tối ưu với c{c luồng còn lại cực đại. Hơn
nữa, bằng c{ch g{n gi{ trị trọng số vô cùng cho c{c chùm bị gỡ ra nên BATCHOPT luôn đảm bảo chúng
được lập lịch lại hết. Tuy nhiên, nhược điểm chính của BATCHOPT, v| cả GreedyOPT, l| l|m tăng độ phức
tạp của hệ thống vì phải lập lịch lại c{c chùm đã được lập lịch trước đó, sinh ra nhiều gói điều khiển hơn để
thông b{o về sự thay đổi tình trạng lập lịch v| do đó yêu cầu những cải tiến trong cấu trúc của giao thức. Độ
phức tạp của BATCHOPT được chứng minh l| O(N2log(N)) [5+, trong đó N l| tổng số c{c chùm đến v| c{c
chùm bị gở ra.
Một giải thuật lập lịch nhóm kh{c, có tên gọi LGS-MC, được đề xuất trong *6+, cho kết quả lập lịch xấp
xỉ tối ưu. LGS-MC dựa trên nguyên tắc tối ưu lập lịch nhóm trên mỗi kênh với hy vọng đạt được một kết
quả lập lịch tối ưu trên tất cả c{c kênh. Mặc dù kết quả lập lịch của giải thuật n|y không hiệu quả bằng
BATCHOPT nhưng LGS-MC có độ phức tạp tính to{n thấp hơn (O(nlog(n))) v| không thực hiện lập lịch lại
c{c chùm đã được lập lịch trước đó nên không l|m tăng độ phức tạp của hệ thống.
Một so s{nh dựa trên x{c xuất rơi gói tin giữa c{c giải thuật nêu trên được mô tả trong hình 1 với tốc
độ lưu lượng luồng đến thay đổi.

4

LIF

0.009580661 0.017164599 0.035513779 0.062902565 0.117654902 0.157320762 0.194298618

MCF

0.007850617 0.014453678 0.031808995 0.057821278 0.123653644 0.167862616 0.190685101

SSF

0.006591611 0.013448835 0.031245973 0.05783744 0.119141443 0.150534788 0.186966525

GreedyOPT 0.006366269 0.011976828 0.030716209 0.054277094 0.114705128 0.15013999 0.185026301
LGS-MC

0.006302301 0.013784762 0.028221805 0.052086275 0.109050581 0.149226965 0.184118963

BATCHOPT 0.003692698 0.00829828 0.020936958 0.040632858 0.091673094 0.128557045 0.164950685

Hình 1. Một so sánh dựa trên xác xuất mất gói giữa SLV, LIF, MCF, SSF, GreedyOPT, LGS-MC và BATCHOPT (với
hình thái mạng và các tham số mô phỏng được mô tả trong phần 5).

B|i viết đề xuất một ứng dụng một giải thuật tìm clique cực đại có trọng số lớn nhất để tối ưu hóa việc
lập lịch nhóm c{c chùm đến trên đa kênh ra tại một nút lõi OBS. Giải thuật lập lịch n|y được cải tiến từ giải
thuật được đề xuất trong *8+ với độ phức tạp được chứng minh không vượt qu{ O(|V|4). Do đó đề xuất của
chúng tôi khắc phục được nhược điểm như BATCHOPT nhưng vẫn đạt được một kết quả lập lịch tối ưu v|
có độ phức tạp đa thức.

4.


LAUT1

b3(5)
b5(6)
Kênh dữ liệu 1

LAUT1

Kênh dữ liệu 2

(a)
LAUT1
b5(6)

b1(3)

Kênh dữ liệu 1

LAUT2

b6(4)

b3(5)

Kênh dữ liệu 2

(b)
Hình 2. Một ví dụ về (a) các chùm đến và (b) kết quả lập lịch tối ƣu trên 2 kênh.

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


(a)

b21

b31

b41

b51

b61

b22

b32

b42

b52

b62

(b)

Hình 3. (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 2a và (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 2b.

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

kênh k (si>LAUTk). Khả năng lập lịch n|y được biểu diễn th|nh một đỉnh trên đồ thị khoảng G với trọng số l|
độ d|i của chùm bi (wik=ei-si). Một cạnh nối giữa 2 đỉnh thể hiện khả năng 2 chùm có thể cùng được lập lịch:
trên 2 kênh khác nhau (kh) hoặc trên cùng một kênh (k=h) m| không chồng lấp nhau (si>ej hoặc ei>sj). Hàm
constructGraph(I,W) được mô tả như sau.
Hàm constructGraph(I,W)
Vào: Tập c{c chùm đến I ={b1,b2,...,bn}
Tập c{c kênh dữ liệu W={1,2,…,w}
Ra:

Đồ thị G(V,E)

Bắt đầu
1
2
3

Với mỗi chùm bi trong I
Với mỗi kênh dữ liệu k trong W:
Nếu si>LAUTk

4

Sinh một đỉnh bik với trọng số wik=ei-si và VV{bik}.

5

Với mỗi chùm bjh trong V và ij

6


1

Nếu G l| một clique cực đại (tất cả c{c đỉnh của G đều có bậc |V|-1)

2

Tính tổng trọng số c{c đỉnh của G ký hiệu l| WG

3

Nếu (WG>Wmax)
Gán Wmax=WG và Cmax=V

4
5
6

Nếu không
Tìm đỉnh có bậc nhỏ nhất: đỉnh u

7

Tìm đồ thị con lớn nhất của G có chứa u: G´(V´,E´)

8

findMWC(G´)

9



Một mở rộng của 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 b i trên một kênh k l| thời gian đến của bi sau LAUT 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(I,W)). Các hàm
còn lại, findMWC(G) và scheduleBurstsfromMWC(Cmax) không có thay đổi n|o.

8


Trong giải thuật MWC-GS có lấp đầy khoảng trống, được gọi l| MWC-GS-VF, một chùm đến sẽ được
so s{nh với với khoảng trống trên mỗi kênh. Như được mô tả trong hình 4, nếu điều kiện si>e1k và (si+wi)

Hình 4. Một ví dụ về (a) 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 kênh 2.

b11

b21

b31

b41

b22

b51

b61

b52

b62

(a)

b11

b21

b31

b41


9


E0

E5

10 Gbps

E1

10 Gbps

E2

C0

10 Gbps

10 Gbps

30 Gbps

C1

E7

10 Gbps


0.1
0.05
0
MWC-GS

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.0061598 0.0117447 0.0276303 0.0505262 0.1037465 0.1440548 0.183274

MWC-VF-GS 0.0034615 0.0082238 0.0214964 0.0409093 0.0922748 0.1293155 0.1658007
BATCHOPT 0.0036927 0.0082983 0.020937 0.0406329 0.0916731 0.128557 0.1649507

Hình. 7. Một so sánh dựa trên xác suất mất gói giữa MWC-GS, MWC-GS-VF và BATCHOPT.

6.

Kết luận
Trong b|i viết n|y, chúng tôi đã đề xuất một mô hình lập lịch với việc cải tiến giải thuật tìm clique cực

networks, Proc. of International Conference on Communications, 2005, Vol.3, pp.1713-1719.

5.

G.B. Figueiredo, E.C. Xavier, N.L.S. da Fonseca, “Optimal algorithms for the batch scheduling problem in OBS
networks”, Computer Networks, 2012, Vol.56, Issue 14, pp.3274–3286.

6.

Nguyen Hong Quoc, Vo Viet Minh Nhat, Nguyen Hoang Son, "Group Scheduling for MultiChannel in OBS
Networks", REV Jounal on Electronics and Communications, 2013, vol.3, no.3–4, pp.134-137.

7.

E.M. Arkin, E. B. Silverberg, “Scheduling jobs with fixed start and end times”, Discrete Applied Mathematics, 1987,
vol.18, pp.1–8.

8.

-

9.

-

Applying an approach of the maximum weight clique finding in order to
optimize the group scheduling in OBS networks
Nguyen Hong Quoc, Duong Phuoc Dat, Nguyen Chi Cong, Vo Viet Minh Nhat

Abstract: The group scheduling in optical burst switching networks has been considered an effective solution to