Luận văn thạc sĩ: Ứng dụng thuật toán Lauc-VF trong truyền tải dữ liệu mạng OBS

Chia sẻ: Sdfas Vfdtg | Ngày: | Loại File: PDF | Số trang:14

Thêm vào BST

Báo xấu

79
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong giai đoạn hiện nay kỹ thuật ghép kênh phân chia theo bước sóng WDM là một giải pháp được lựa chọn để cung cấp một cơ sở hạ tầng mạng nhanh hơn nhằm đáp ứng sự phát triển bùng nổ của Internet.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn thạc sĩ: Ứng dụng thuật toán Lauc-VF trong truyền tải dữ liệu mạng OBS

-1- B GIÁO D C VÀ ĐÀO T O Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG Đ I H C ĐÀ N NG ĐÀO NG C TU N ANH Ngư i hư ng d n khoa h c : PGS.TS LÊ VĂN SƠN NG D NG THU T TOÁN LAUC-VF TRONG Ph n bi n 1: TRUY N T I D LI U M NG OBS Chuyên ngành: Khoa h c máy tính Ph n bi n 2: Mã s : 60.48.01 Lu n văn s ñư c b o v t i H i ñ ng ch m Lu n văn t t nghi p th c sĩ k thu t h p t i Đ i h c Đà N ng vào ngày tháng năm 2012. TÓM T T LU N VĂN TH C SĨ K THU T Có th tìm hi u lu n văn t i: - Trung tâm Thông tin - H c li u, Đ i h c Đà N ng - Trung tâm H c li u, Đ i h c Đà N ng Đà N ng - Năm 2012 M Đ U
-2- -3- 1. Lý do ch n ñ tài phân chia bư c sóng (WDM) cho phép truy n t i lưu lư ng tr c ti p Trong vài th p niên g n ñây, lư ng thông tin trao ñ i trong các qua m ng mà không c n b ñ m quang t i các node m ng. h th ng thông tin ngày nay tăng lên r t nhanh. Bên c ch gia tăng v M t trong các v n ñ c a m ng OBS ñó là: “làm th nào t n s lư ng truy n thông trên m ng cũng thay ñ i. D ng d li u ch y u d ng ñư c băng thông m ng và gi m suy hao lu ng m t cách t i là lưu lư ng Internet. Ph n l n nhu c u hi n nay liên quan ñ n vi c ña?”. Vi c nghiên c u các gi i thu t l p l ch kênh t i các node m ng truy n s li u hơn là ti ng nói. S lư ng s d ng Internet ngày càng ñư c coi là v n ñ quan tr ng và ý nghĩa. Đó là lý do tôi ch n ñ tài: ñông và th i gian m i l n truy c p thư ng dài hơn nhi u l n m t “ ng d ng thu t toán LAU-VF trong truy n t i d li u m ng cu c g i ñi n tho i. Bên c ch ñó, các doanh nghi p cũng thư ng d a OBS” vào các m ng t c ñ cao ñ ñi u hành công vi c, nh ng ñi u này ñã 2. M c ñích nghiên c u t o ra m t nhu c u s d ng băng thông l n, nh ng ñư ng truy n t c M c ñích c a ñ tài là tìm hi u các thu t toán l p l ch kênh, ñ ñ cao, tin c y và chi phí th p. xu t m t thu t toán l p l ch kênh m i và công ngh gi m thi u tranh M ng thông tin quang ra ñ i ñã ñáp ng ñư c nh ng yêu c u ch p, t ñó th y ñư c phương pháp nào cho hi u xu t cao nh t cho trên. Thông tin quang cung c p băng thông l n và t l l i r t th p. toàn m ng. Bên c nh dung lư ng cao, môi trư ng quang còn cung c p kh năng 3. Đ i tư ng và ph m vi nghiên c u trong su t. Tính trong su t cho phép các d ng d li u khác nhau chia - Tìm hi u lý thuy t v m ng thông tin quang s cùng m t môi trư ng truy n và ñi u này r t phù h p v i vi c - Th o lu n v các gi i thu t l p l ch kênh mang các tín hi u có nh ng ñ c ñi m khác nhau. K thu t ghép kênh - Phân tích và so sánh ưu như c ñi m c a các gi i thu t l p l ch ñư c quan tâm nh t hi n nay là ghép kênh phân chia bư c sóng kênh và ñ xu t m t gi i thu t l p l ch kênh m i. WDM và ghép kênh phân chia th i gian TDM. K thu t ghép kênh - Môi trư ng ki m th (ph n m m NS2), gói h tr (OBS-0.9a) phân chia bư c sóng ñư c ưu chu ng hơn vì chi phí k thu t và thi t - Phân tích ñánh giá hi u năng m ng qua vi c mô ph ng. b l p ñ t các h th ng TDM tương ñ i cao. Đ tài thu c lo i hình nghiên c u. Trong k thu t ghép kênh phân chia bư c sóng thì m ng chuy n 4. Phương pháp nghiên c u m ch chùm quang (OBS) ñã ñư c ñ xu t như là m t công ngh h a - Thu th p và phân tích các tài li u liên quan ñ n ñ tài h n cho Internet toàn quang c a th h m i b i vì: OBS k th a ñư c - Th o lu n, l a ch n phương pháp gi i quy t v n ñ nh ng ưu ñi m c a các m ng chuy n m ch ñã ñư c ñ xu t trư c ñó - L a ch n công ngh cài ñ t chương trình (ph n m m NS2). Và và kh c ph c ñư c nh ng h n ch nh s d ng k thu t ghép kênh gói h tr (OBS-0.9a). - Phân tích và ki m ñ nh k t qu ñ t ñư c.
-4- -5- 5. Ý nghĩa khoa h c và th c ti n CHƯƠNG 1 - Cung c p m t cách nhìn t ng quan v m ng thông tin quang và T NG QUAN V M NG THÔNG TIN QUANG các yêu c u ñ t ra trong th c t . 1.1 Gi i thi u - Đưa ra cái nhìn khái quát v quá trình l p l ch kênh và các v n Khác v i các m ng thông tin h u tuy n và vô tuy n: ñ c a m ng chùm quang. - Các lo i thông tin s d ng các môi trư ng truy n d n tương - Qua mô ph ng có th ñánh giá ñư c gi i pháp nào t t trong ng là dây d n và không gian vi c s d ng kênh và gi m suy hao lu ng t i các node. Qua ñó, làm - Thông tin quang là m t h th ng truy n tin qua s i quang. ti n ñ ñ xây d ng m t gi i pháp m i t i ưu hơn trong vi c truy n Đi u ñó có nghĩa là thông tin ñư c chuy n thành ánh sáng và sau ñó t i d li u t i các node m ng. ánh sáng ñư c truy n qua s i quang. T i nơi nh n, nó l i ñư c bi n 6. C u trúc c a lu n văn ñ i thành thông tin ban ñ u. Chương 1: Gi i thi u t ng quan v m ng thông tin quang 1.2 Các th h m ng quang Trong chương này, cho ta cái nhìn t ng quan v m ng thông tin Có th chia thành 3 giai ño n chính: quang, làm ti n ñ nghiên c u các chương ti p theo - M ng quang th h th nh t: V i th h m ng quang ñ u tiên Chương 2: Th o lu n v các gi i thu t l p l ch trong m ng các cáp ñ ng ñư c thay th b i cáp quang ñ truy n d n. S i quang Trong chương này, ñi sâu tìm hi u nguyên lý ho t ñ ng c a ñây ñã ñ t ñư c t c ñ truy n l n hơn 10Mbs. Trong th h này, khi m ng chùm quang và trình bày ng n v các gi i thu t l p l ch kênh. tín hi u quang ñi vào m t nút chuy n m ch, nó s ñư c chuy n ñ i So sánh ưu như c ñi m c a các gi i thu t l p l ch và ñ xu t gi i thành tín hi u ñi n, x lí và chuy n tr l i thành tín hi u quang trư c thu t l p l ch m i. khi ra kh i nút ñó. Vi c chuy n ñ i tín hi u t i các nút m ng cùng Chương 3: Xây d ng, mô ph ng và ñánh giá v i t c ñ x lí c a các thành ph n ñi n t gây tr l n Trong chương này, th c hi n cài ñ t; so sánh và ñánh giá các - M ng quang th h th 2: M ng th h này ñã s d ng k k t qu ñ t ñư c. thu t cho phép ghép nhi u bư c sóng ñ có th truy n trên cùng m t Ph n k t lu n, trình bày tóm t t các v n ñ ñã ñư c nghiên c u s i quang. Vì v y, làm tăng băng thông truy n trên m i liên k t và k trong lu n văn. Đ ng th i ñưa ra hư ng nghiên c u phát tri n c a ñ thu t này ñư c g i là k thu t ghép kênh quang WDM (Wavelength tài. Division Multiplexing). Ưu ñi m chính ñó là s k t h p ch t ch v ch c năng gi a chuy n m ch và ñ nh tuy n trong mi n quang, và có kh năng trong su t v i khuôn d ng c a tín hi u, giao th c và t c ñ bit.
-6- -7- - M ng quang th h th 3: M ng quang th h ti p theo là bư c sóng, bư c sóng trung tâm c a kênh, m c xuyên âm c a các m ng toàn quang (All-Optical) và s d ng OPS quang. T t c các kênh, suy hao.. công vi c như vùng ñ m, chuy n m ch, ñ nh tuy n ñ u th c hi n - Truy n d n tín hi u: Quá trình truy n d n tín hi u trong s i trong mi n quang. quang ch u s nh hư ng c a nhi u y u t : suy hao quang, tán s c, 1.3 Ghép kênh phân chia bư c sóng WDM các hi u ng phi tuy n, các v n ñ v khu ch ñ i tín hi u… 1.3.1 Ghép kênh phân chia bư c sóng WDM - Khu ch ñ i tín hi u: Đư c s d ng trong các h th ng truy n 1.3.2 Đ nh nghĩa d n có kho ng cách xa nh m ñ m b o ch t lư ng tín hi u nơi nh n. Ghép kênh bư c sóng WDM (Wavelength Devision Có ba ch ñ khu ch ñ i tín hi u: khu ch ñ i công su t, khu ch ñ i Multiplexing) là m t công ngh “truy n d n ñ ng th i nhi u tín hi u ñư ng và ti n khu ch ñ i. quang trên nhi u bư c sóng khác nhau trong m t s i quang”. ñ u - Thu tín hi u: Thu tín hi u trong các h th ng WDM cũng s phát, nhi u tín hi u quang trên các bư c sóng khác nhau ñư c t h p d ng các b tách sóng quang như các h th ng thông tin quang thông l i (ghép kênh) ñ cùng truy n ñi trên m t s i quang. ñ u thu, tín thư ng: PIN, APD. hi u t h p ñó ñư c phân gi i (tách kênh), khôi ph c l i tín hi u g c 1.4 Các công ngh chuy n m ch quang r i ñưa vào các ñ u cu i khác nhau. M t s công ngh khác nhau ñã ñư c phát tri n ñ truy n d 1.3.3 Ch c năng h th ng WDM li u trên WDM, như Optical Circuit Switching (OCS), Optical Packet H th ng WDM bao g m các các ch c năng sau: Switching (OPS) và Optical Burst Switching (OBS). K thu t OBS - Phát tín hi u: H th ng WDM s d ng ngu n tín hi u laser. là m t gi i pháp k thu t trung gian gi a OCS và OPS nh m ñáp ng Yêu c u ñ i v i ngu n phát laser là ph i có ñ r ng ph h p, bư c ñ y ñ các tính năng m i trong giai ño n t i. sóng phát ra n ñ nh, m c công su t phát ñ nh, ñ r ng ph , bư c 1.5 Đ i tư ng và ph m vi nghiên c u sóng trung tâm ph i n m trong gi i h n cho phép. - Hoàn thành nghiên c u thu t toán l p l ch kênh, - Ghép/Tách tín hi u: Ghép tín hi u là s k t h p m t s bư c - Đ xu t m t thu t toán l p l ch kênh m i, sóng ánh sáng khác nhau thành m t tín hi u t ng h p ñ truy n d n - Đ xu t m t công ngh gi m thi u tranh ch p trong m ng qua s i quang. Tách tín hi u là phân tách lu ng tín hi u t ng h p ñó OBS, thành các bư c sóng tín hi u riêng r t i m i c ng ñ u ra c a b - Nghiên c u các ñ xu t trên thông qua vi c mô ph ng. tách. Khi nói ñ n các b tách/ghép tín hi u, ta ph i xét ñ n các tham 1.6 Tóm t t chương s như kho ng cách gi a các kênh, ñ r ng băng t n c a các kênh
-8- -9- ñ chuy n burst t c ng vào ñ n c ng ra và gi i quy t xung ñ t n u x y ra. CHƯƠNG 2 2.2 T p h p burst TH O LU N V CÁC GI I THU T X P L CH Hi n nay có hai k thu t ñư c quan tâm nh t là t p h p burst TRONG M NG CHÙM QUANG d a vào ngư ng th i gian (timer-based) và d a trên ngư ng ñ dài 2.1 Ki n trúc m ng chuy n m ch chùm quang burst (threshold -based). - Phương pháp t p h p burst d a trên ngư ng th i gian, m t burst ñư c t o ra và g i vào trong m ng theo chu kỳ th i gian, ñúng b ng th i gian ñã ñư c ñ nh s n vì v y mà không quan tâm ñ n kích thư c burst dài hay ng n. Do ñó, chi u dài c a burst bi n ñ i tuỳ theo t n su t ñ n c a gói, trong nh ng kho ng th i gian b ng nhau. - Phương pháp t p h p burst d a trên giá tr ngư ng ñ dài burst , m t gi i h n d a trên s lư ng t i ña gói tin ch a trong m i burst . Vì v y, nh ng burst ñư c t o ra có kích thư c c ñ nh. Hình 2.1 Ki n trúc c a m ng chuy n m ch chùm V n ñ quan tr ng ñư c ñ t ra ñây là: “làm th nào ñ ch n M t nút OBS bao g m c 2 ph n: quang và ñi n. Ph n quang là m t giá tr ngư ng th i gian ho c ngư ng ñ dài burst t i ưu?” ñ các b ghép/tách bư c sóng (multiplexer/demultiplexer) và chuy n gi m s lư ng gói tin ñi n t b m t khi x y ra tranh ch p burst , m ch quang. Ph n ñi n có các module vào/ra, ñi u khi n ñ nh tuy n cũng như tăng hi u su t s d ng m ng OBS. và b l p l ch. Đơn v chuy n m ch quang ñi u khi n các burst d 2.3 Giao th c thi t l p k t n i li u t m t c ng vào và ra m t c ng tương ng v i ñích ñ n c a 2.3.1 Giao th c TAG chúng. Khi m t nút biên chu n b truy n m t burst d li u, nó s g i 2.3.2 Giao th c JIT m t gói ñi u khi n ñi trên m t bư c sóng riêng t i nút lõi. Gói ñi u khi n th c hi n vi c báo hi u, c u hình các chuy n m ch t i nút lõi
- 10 - - 11 - b l p l ch bi t ñư c th i gian ñ n, th i gian k t thúc c a burst . Bên c nh ñó, b l p l ch duy trì th i gian chưa l p l ch kh d ng g n nh t (LAUT), các kho ng h (gap) và các kho ng tr ng (void) trên m i JIT là giao th c ñ t trư c t c th i trong m ng OBS, trong ñó kênh d li u ra. D a vào nh ng thông tin này, nút lõi s xác ñ nh m t bư c sóng ngõ ra s ñư c ñ t trư c cho burst ngay sau khi ñư c kênh bư c sóng thích h p nh t dành cho burst d li u nh gi i thông ñi p SETUP tương ng ñ n. N u tài nguyên không ñư c ñ t thu t l p l ch c a b l p l ch. M c ñích chính c a các gi i thu t này trư c ngay th i ñi m ñó, thông ñi p SETUP s ñư c h y b và burst là ph i l p l ch ñư c th t nhi u burst trên cùng m t kênh bư c sóng s b ñánh r t. ñ t i ưu hóa lưu lư ng và gi m s m t burst . N u vi c l p l ch không th th c hi n ñư c t i th i ñi m burst ñ n thì burst có th 2.3.3 Giao th c JET ñư c làm tr m t kho ng th i gian n u s d ng ñư ng tr FDL và có th ñư c l p l ch th i gian khác, n u không burst b r t. Bên c ch ñó, b l p l ch c n s d ng nh ng gi i thu t ñơn gi n hơn là các gi i thu t ph c t p. B i vì, các nút ñ nh tuy n ho t ñ ng v i t c ñ r t cao ñ x lý m t s lư ng r t l n burst d li u. M t gi i thu t ph c t p có th d n ñ n tình tr ng m t burst khi burst d li u ñ n trư c khi gói tin ñi u khi n c a burst ñó ñư c x lý xong. 2.4.1 Phân lo i Hình 2.3: Minh h a cho giao th c JET Có th phân làm 2 lo i gi i thu t l p l ch kênh: Đây là giao th c thi t l p có tr , trong ñó tài nguyên ch ñư c - Gi i thu t Horizon (without Void filling) c p phát trong kho ng th i gian burst ñ n nút chuy n m ch cho ñ n - Gi i thu t Void filling (with Void filling) khi burst ñư c truy n qua h t. Do ñó tài nguyên ch dành riêng cho 2.4.2 Gi i thu t Horizon kho ng th i gian nó th c s ñư c s d ng, nh v y giao th c này giúp ti t ki m ñư c tài nguyên. 2.4 Các thu t toán l p l ch kênh Trong m ng OBS, khi m t gói ñi u khi n ñ n nút lõi, m t gi i thu t l p l ch s ñư c g i ñ gán burst chưa ñư c l p l ch vào m t kênh d li u trên liên k t ra. D a vào thông tin trong gói ñi u khi n,
- 12 - - 13 - Bư c 3: Th l p l ch burst ñ n cho kênh i (LAUTi < tub): N u thành công, kênh i ñư c ch n cho vi c l p l ch burst ñ n và k t thúc; N u không, quay l i bư c 2 th ñ i v i kênh i=i+1. 2.4.2.2 Gi i thu t LAUC LAUC, L a ch n m t kênh d li u chưa l p l ch t i ñó kho ng tr ng (gap) t o ra gi a các burst d li u ñư c l p l ch liên ti p là t i thi u. Hình 2.5 L p l ch không xét ñ n l p ñ y kho ng tr ng Gi i thu t ñư c mô t như sau: Đ i v i lo i gi i thu t này, chúng ta c n lưu ý ñ n 2 tham s : Bư c 1: Kh i t o i=0; sc=-1; gapmin=; th i ñi m ñ n tub c a burst so v i th i ñi m k t thúc c a burst sau Bư c 2: N u v n còn kênh i (i
- 14 - - 15 - ñ n s m nh t và th i gian k t thúc c a burst d li u ñã ñư c l p l ch trư c ñó. 2.4.3.3 Gi i thu t Min-EV M t bi n th c a gi i thu t LAUC-VF là Min-EV. Min-EV, tìm ki m t t c các kênh d li u ñ tìm ra m t kênh kho ng tr ng kh d ng cho burst d li u ñ n s m nh t. Sau ñó, l a ch n m t kênh sao cho v trí c a burst d li u m i t o ra kho ng tr ng t i thi u gi a Hình 2.5 L p l ch có xét ñ n l p ñ y kho ng tr ng (void filling) th i gian b t ñ u c a burst d li u ñã ñư c l p l ch và th i gian k t Trên c s 2 gi i thu t không xét ñ n l p ñ y kho ng tr ng, 2 thúc c a burst d li u ñ n s m nh t. gi i thu t tương t có xét ñ n l p ñ y kho ng tr ng (Void-Filling) ñã 2.4.3.4 Gi i thu t Max-EV ñư c ñ ngh : FFUC-VF và LAUC-VF. Khác v i Min-EV. Max-EV, l a ch n m t kênh sao cho v trí V i lo i gi i thu t này, chúng ta c n lưu ý ñ n th i ñi m b t ñ u c a burst d li u m i t o ra kho ng tr ng t i ña gi a th i gian b t và k t thúc c a các burst : (s,e) c a burst ñ n c n ñư c l p l ch và ñ u c a burst d li u ñã ñư c l p l ch và th i gian k t thúc c a burst ( , ) c a các burst ñã l p l ch trên t t c các kênh (trong ñó d li u ñ n s m nh t. i=(0..W-1), W là t ng s kênh, và k=1..m, m là t ng s burst ñang 2.4.3.5 Gi i thu t k t h p Min-EV và Min-SV ñư c l p l ch trên m t kênh). Như mô t hình 2.5, kênh D0 và D3 Gi i thu t k t h p s l a ch n m t kênh sao cho th a mãn: là ñư c xem xét vì th a mãn ñi u ki n < s và > e, i = 0,.. 3. - Burst d li u m i t o ra kho ng tr ng t i thi u gi a th i gian 2.4.3.1 Gi i thu t FFUC-VF b t ñ u c a burst d li u ñã ñư c l p l ch và th i gian k t thúc c a Gi ng v i gi i thu t FFUC, nhưng gi i thu t FFUC-VF s ưu burst d li u ñ n s m nh t. tiên xem xét t t c các kho ng tr ng có th ñư c tìm th y và t i tr ng - Burst d li u m i t o ra kho ng tr ng t i thi u gi a th i gian ñư c l p l ch vào kênh kho ng tr ng kh d ng ñ u tiên phù h p ñ b t ñ u c a burst d li u ñ n s m nh t và th i gian k t thúc c a truy n. burst d li u ñã ñư c l p l ch trư c ñó. 2.4.3.2 Gi i thu t LAUC-VF Tuy nhiên, vi c k t h p c hai ñi u ki n này s t o khó khăn Gi ng v i gi i thu t LAUC, gi i thu t LAUC-VF tìm ki m t t c trong vi c ch n kênh. các kênh d li u ñ tìm ra m t kênh kho ng tr ng kh d ng trong 2.5 Gi i quy t xung ñ t kho ng th i gian (s,e). Sau ñó, l a ch n m t kênh sao cho v trí c a 2.6 H n ch c a các gi i thu t lâp l ch và ñ xu t m t s burst d li u m i t o ra kho ng tr ng t i thi u gi a burst d li u gi i thu t l p l ch m i
- 16 - - 17 - 2.6.1 H n ch c a các gi i thu t l p l ch Bư c1: L a ch n t t c kênh tr ng có th l p l ch. Kênh - Đ i v i gi i thu t Horizon kho ng tr ng i có th l p l ch n u startb > startv(i) và lengthb < + S d ng tài nguyên m ng th p lengthv(i). N u không th l p l ch trên kênh kho ng tr ng thì chuy n + Xác su t rơi burst cao (do gi i thu t Horizon không xem xét qua bư c 4. ñ n các kho ng th i gian tr ng t o ra gi a các burst trên m i kênh Bư c2: tính toán h s s d ng kênh cho t t c kho ng tr ng tìm d li u.) th y trong bư c 1. - Đ i v i gi i thu t Void filling Bư c3: tìm 1 kênh j sao cho nó có h s s d ng kênh t i ña Ch xét m t m t c a kho ng tr ng (burst d li u có ñ dài nh như tìm th y bư c2. Xu t kênh j và tr v data channel. D ng ñôi khi nó ñư c l p l ch trên kênh có kho ng tr ng l n trong khi ñó Bư c 4: l p l ch cho burst d li u chuy n qua gi i thu t LAUC. burst d li u có kích thư c l n có th b h y). D ng 2.6.2 Gi i thu t t i ưu Bư c 1 c a gi i thu t là tìm 1 kênh kho ng tr ng l p l ch có th . 2.6.2.1 Gi i thu t BFUC-VF N u không s n có kênh kho ng tr ng kh d ng thì burst d li u s Trong ph n này, tôi ñ xu t m t gi i thu t l p l ch kênh g i là ñư c l p l ch như trong gi i thu t LAUC. BFUC-VF, Nó c g ng s d ng kênh t i ña và t i thi u kh năng m t 2.6.2.2 Các gi i thu t l p l ch phân ño n burst burst . Tôi ñ xu t thu t toán ñ u tiên l a ch n t t c các kênh a. Kênh tr ng chéo nh nh t (Non-preemptive Mininum Overlap kho ng tr ng kh d ng, trên ñó burst d li u có th ñư c l p l ch. Channel NP-MOC) Gi i thu t BFUC-VF có th ñư c trình bày t ng quát như sau: Gi i thu t NP-MOC là s c i ti n c a gi i thu t LAUC. Gi i Tham s ñ u vào: thu t l p l ch NP-MOC d a vào LAUT trên m i kênh d li u. Khi - Lengthb: ñ dài burst d li u ñ n không tìm th y kênh nào kh d ng ñ l p l ch cho burst thì gi i thu t - Lengthv(i): ñ dài kho ng tr ng trên kênh i l p l ch NP-MOC xem xét t t c các kênh d li u ra và tính toán ñ - Startb : th i gian b t ñ u c a m t burst d li u ch ng chéo trên m i kênh và l a ch n kênh có ñ ch ng chéo nh - Startv(i) : th i gian b t ñ u c a kho ng tr ng trong kênh i nh t ñ l p l ch cho burst ñó. Đ ch ng chéo ñư c tính LAUTi -tub. - Data channel: kênh d li u l a ch n b i gi i thu t l p l ch b. Gi i thu t l p l ch NP-MOC-VF burst d li u Duy trì th i ñi m b t ñ u và k t thúc c a m i burst d li u trên Mô t : m i kênh. M c ñích c a gi i thu t là t n d ng các kho ng tr ng gi a Input: startb, lengthb các burst ñã ñư c l p l ch trên m i kênh d li u. Kênh có Gapi nh Output: data channel nh t s ñư c ch n l a trong trư ng h p có nhi u hơn m t kênh s n
- 18 - - 19 - có. N u không có kênh nào r i thì kênh có s lư ng các gói tin rơi ít Chúng ta có th phân các lo i phương th c báo hi u như sau: nh t ñư c ch n l p l ch cho burst . - Báo hi u m t chi u, hai chi u hay h n h p 2.8 Tóm t t - Dành riêng b t ñ u t ngu n, ñích ho c nút trung gian CHƯƠNG 3 - Dành riêng b n v ng và không b n v ng CÀI Đ T MÔ PH NG VÀ PHÂN TÍCH K T QU - Dành riêng t c th i hay dành riêng sau m t th i gian tr . 3.1 Đ t v n ñ - Gi i phóng tài nguyên tư ng minh ho c ng m ñ nh. Nh ng năm g n ñây, nhu c u băng thông m ng tăng nhanh do - K thu t báo hi u t p trung hay phân tán. s phát tri n m nh m c a Internet toàn c u v i s bùng n c a 3.4 Gi i thi u chương trình mô ph ng nhi u lo i hình d ch thông tin. Đi u này ñ t ra nh ng thách th c ñ i 3.4.1 T ng quan v NS2 v i h th ng truy n thông v n ñư c xây d ng ch y u ph c v cho NS-2 là chương trình mô ph ng mã ngu n m dành cho m c nhu c u tho i và truy n thông tin không c n t c ñ cao. Do ñó, yêu ñích nghiên c u. Không ch là công c mô ph ng, NS-2 còn là c u ñ t ra là “làm th nào ñ có th truy n m t lư ng l n d li u trên chương trình có nhi u module h tr và m t b thư vi n r t ti n ích m i kênh mà t l burst m t là nh nh t?”. cho vi c mô ph ng các s ki n riêng l . NS-2 g m m t s module 3.2 Đ nh tuy n bư c sóng như: b phát s ng u nhiên (Random Number Generator), b l p l ch Đ nh tuy n là s l a ch n ñư ng ñi cho m t k t n i th c hi n s ki n (Event Scheduler), hàng ñ i (Queue), h tr toán h c,… vi c g i d li u. Đ nh tuy n ch ra hư ng d ch chuy n c a các gói 3.4.2 C u trúc NS2 (d li u), t ngu n ñ n ñích và qua các nút trung gian; thi t b 3.5 K ch b n mô ph ng chuyên dùng cho vi c ñ nh tuy n là b ñ nh tuy n (router). Quá trình 3.5.1 Topo m ng dùng ñ mô ph ng ñ nh tuy n ch hư ng ñi thư ng d a vào b ng ñ nh tuy n, b ng ch a Mô ph ng các gi i thu t l p l ch ñư c th c hi n trên gói OBS- các l trình t t nh t ñ n các ñích khác nhau trên m ng. 0.9a c a ph n m m mô ph ng NS. Topo c a m ng OBS th c hi n mô 3.3 Báo hi u trong m ng quang ph ng là m ng ring ñư c t o thành t 11 node lõi (Ci, i = 0..10), m i Trong m ng chuy n m ch chùm quang, khi m t burst ñư c g i node lõi k t h p v i m t node biên (Ei, i = 0 ..11) như mô t hình t i m t nút lõi, ti n trình báo hi u ñư c th c hi n trư c ñ d tr tài 3.1. Các lu ng d li u ñ n theo phân ph i poisson gi a các c p nút nguyên và c u hình cho b chuy n m ch quang t i m i nút ñó sao Ei và Ej (i, j = 0 ..11). Các burst do ñó ñư c sinh ra t i các th i ñi m cho phù h p v i burst d li u tương ng. Ti n trình báo hi u trong thay ñ i và cũng như có ích thư c thay ñ i. S kênh d li u và kênh m ng chuy n m ch burst quang ñư c th c hi n b i các gói ñi u ñi u khi n tương ng là 8 và 3 trên m i liên k t. Băng thông trên m i khi n và các gói này ñư c truy n ñ c l p v i các burst d li u. kênh là 10Gb/s.
- 20 - - 21 - 12000 11 0 10000 S burst b r t 1 10 0 1 8000 2 6000 2 LAUC 10 4000 9 9 FFUC 3 3 2000 0 8 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 4 8 4 Th i gian mô ph ng 7 5 6 7 5 6 Hình 3.2: Hi u qu l p l ch c a gi i thu t 12000 10000 S burst b r t 8000 Hình 3.1: Hình thái m ng mô ph ng ñư c t o ra t 6000 LAUC FFUC 11 node lõi và 12 node biên 4000 FFUC-VF 2000 LAUC-VF 0 3.5.2 Phân tích các k t qu mô ph ng 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 Th i gian mô ph ng 3.5.2.1 Các gi i thu t l p l ch không s d ng ñư ng tr FDL Mô ph ng ñư c th c hi n trong các kho ng th i gian khác Hình 3.3: So sánh hi u qu c a các gi i thu t l p l ch có nhau (t 0.01 ñ n 0.09 giây), k t qu mô ph ng (hình 3.2) ch ra r ng Bên c ch ñó t các k t qu mô ph ng gi i thu t l p l ch có và các gi i thu t l p l ch LAUC hi u qu hơn FFUC vì t i ưu kho ng không l p ñ y kho ng tr ng. Ta th y, gi i thu t LAUC _VF có t l cách gi a các burst . m t burst th p nh t như mô ph ng trên hình 3.3(vì t i thi u ñư c Qua k t qu mô ph ng hình 3.2 và 3.3, ta th y gi i thu t kho ng cách gi a các burst ñư c l p l ch trên m i kênh). Horizon không xét ñ n các kho ng tr ng t o ra trên 2 burst ñã ñư c K t qu mô ph ng hình 3.4, gi i thu t c i ti n Min-EV t gi i l p l ch trư c ñó nên t l burst r t l n. Hình 3.3 cho ta th y gi i thu t LAUC-VF ta th y s lư ng burst b r t g n b ng nhau. Trong thu t s d ng Void filling(l p ñ y kho ng tr ng) hi u qu hơn nhi u, ñó gi i thu t Min-EV có hi u qu hơn nhưng không ñáng k . b i vì chúng t n d ng ñư c băng thông nhàn r i trong các kho ng 3000 tr ng ñư c sinh ra khi l p l ch, so v i các gi i thu t l p l ch không 2500 S burst b r t 2000 xét ñ n l p ñ y kho ng tr ng. 1500 1000 LAUC-VF Min-EV 500 0 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 Th i gian mô ph ng Hình 3.4: So sánh hi u qu c a các gi i thu t l p
- 22 - - 23 - 3000 2500 thích nghi (ch n l a gi i thu t phù h p nh t trong các gi i thu t có S burst b r t 2000 1500 LAUC-VF th ) s tìm ki m ñư c gi i pháp t i ưu cho vi c l p l ch t i m i nút. 1000 Min-EV 500 BFUC-VF Đây là hư ng m cho vi c c i ti n các mô hình l p l ch trong tương 0 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 lai. Th i gian mô ph ng Vi c l p l ch có th th c hi n theo nhóm, khi m t t p các burst Hình 3.5: So sánh hi u qu c a gi i thu t l p l ch c n l p l ch ñ n ñ ng th i. Gi s , t i th i ñi m ñó t i m t nút ñang ñ xu t BFUC-VF xem xét có m t t p các kho ng tr ng kh d ng. M c tiêu ñư c ñ t ra Ngoài ra, qua k t qu mô ph ng hình 3.5 v i gi i thu t ñư c là t i ña s burst có th l p l ch ñư c vào các kho ng tr ng (n u s ñ xu t BFUC-VF; so v i các gi i thu t s d ng Void filling hi u burst ñ n nhi u hơn s kho ng tr ng có th l p l ch), ho c là t i ưu qu như: LAUC-VF và Min-EV thì ta th y s lư ng burst b r t hóa vi c ch n các kho ng tr ng v a khít nh t cho các burst ñ n (n u trong gi i thu t BFUC-VF th p hơn. Gi i thu t BFUC-VF cho th y s burst ñ n ít hơn s kho ng tr ng có th l p l ch). K t qu l p l ch hi u qu hơn trong vi c gi m thi u kh năng m t burst d li u. có th ñ t ñư c v i hư ng ti p c n này thư ng là x p x t i ưu, thay Hi u qu c a các gi i thu t l p l ch ph thu c nhi u vào t c ñ vì là t i ưu. Đây cũng là m t hư ng m khác cho vi c c i ti n các mô ñ n, ñ dài c a burst , và m t ñ lu ng mà ñó các kho ng tr ng hình l p l ch. ñư c sinh ra. Quan tr ng nh t là s ñ ng nh p gi a th i ñi m ñ n c a burst ngay sau th i ñi m b t ñ u c a kho ng tr ng. Đ i v i gi i 3.5.2.2 Các gi i thu t l p l ch s d ng ñư ng tr FDL thu t LAUC-VF hay Min-EV, khi t c ñ burst ñ n cao (kho ng cách K t qu mô ph ng (hình 3.6), ñ i v i gi i thu t l p l ch LAUC – c a các burst ñ n liên ti p là nh ), m t kho ng tr ng không ñư c VF ch ra r ng khi có s d ng ñư ng tr FDL (3-FDL ) thì s burst ch n ñ l p l ch cho burst ñ n hi n th i v n có th ñư c s d ng rơi trên toàn m ng gi m ñáng k (63.74%) so v i khi không s d ng cho các burst ñ n sau. Do ñó, vi c t i thi u kho ng (s - em-1i) s t i ñư ng tr FDL (0-FDL ). ña s burst ñư c l p l ch (gi i thu t LAUC-VF). Nhưng khi t c ñ 3000 2500 S burst b r t burst ñ n th p (kho ng cách c a các burst ñ n liên ti p là l n), vi c 2000 ch n kho ng tr ng cho burst ñ n hi n th i có kho ng (smi - e) t i 1500 1000 LAUC-VF thi u (gi i thu t Min-EV) s t o cơ h i cho các kho ng tr ng khác 500 LAUC-VF with FDL 0 phù h p v i các burst ñ n sau. 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 Tóm l i, không có gi i thu t l p l ch nào t i ưu cho t t c các Th i gian mô ph ng nút m ng. M i gi i thu t ch phù h p v i m t s tình tr ng m t ñ Hình 3.6: So sánh hi u qu c a gi i thu t l p l ch LAUC-VF có lu ng và tình tr ng burst ñ n c n l p l ch. M t mô hình l p l ch và không s d ng ñư ng tr FDL
- 24 - - 25 - Như v y là trong chương này, tôi ñã ti n hành mô ph ng các thu t toán l p l ch và so sánh các k t qu trên ñ th . Qua k t qu mô ph ng các thu t toán l p l ch ñã trình bày, ñã th y ñư c ưn ñi m c a các thu t toán s d ng Void filling trong vi c l a ch n kênh kho ng tr ng và gi m t l m t burst so v i các thu t toán không s d ng Void filling. Ti n hành mô ph ng và so sánh gi i thu t l p l ch kênh ñư c ñ xu t BFUC-VF v i gi i thu t l p l ch LAUC-VF và Min-EV ñ th y ñư c hi u xu t s d ng kênh t i ña và gi m thi u ñáng k t Hình 3.7: Burst ñư c làm tr MaxDelay giây trong hai trư ng l m t burst c a thu t toán BFUC-VF so v i các gi i thu t ñó. h p tìm ñư c và không ñư c Ngoài ra, so sánh hi u qu c a vi c k t h p s d ng ñư ng tr V n ñ trên ñư c gi i thích như sau: Khi s d ng ñư ng tr và vi c không s d ng ñư ng tr FDL (trong thu t toán LAUC-VF) FDL cho vi c tránh t c ngh n trong khi l p l ch, m t burst ñ n s qua ñó th y ñư c vi c k t h p các thu t toán l p l ch v i s d ng ñư c làm tr m t kho ng th i gian MaxDelay (ñúng b ng ñ dài ñư ng tr FDL s làm gi m thi u ñáng k t l m t burst t i các ñư ng tr FDL ) ñ hy v ng s có tài nguyên kh d ng cho nó sau node. kho ng th i gian này (Hình 3.7 (a)). Tuy nhiên, s t c ngh n có th v n ti p t c n u t i th i ñi m burst ra kh i ñư ng tr nhưng không K T LU N tìm th y tài nguyên kh d ng (Như hình 3.7 (b)). Nói m t cách khác hi u qu c a vi c s d ng ñư ng tr FDL 1. K t qu ñ t ñư c còn ph thu c vào ñ dài (giá tr MaxDelay). M t câu h i ñư c ñ t K t qu ñ t ñư c ra là: “làm th nào ñ xác ñ nh ñư c ñ dài t i ưu c a ñư ng tr ?” Sau m t th i gian nghiên c u tôi ñã hoàn thành ñ án và ñ t Trên th c t , ñ dài ñư ng tr FDL t i ưu t i m i nút ph thu c ñư c nh ng m c tiêu ñ ra ban ñ u ñó là: vào m t ñ lu ng mà ñó các kho ng tr ng sinh ra; t c ñ ñ n và ñ - Hoàn thành nghiên c u các thu t toán l p l ch kênh, dài c a burst ñ n. Do ñó, vi c tìm ra quy lu t v s ph thu c c a ñ - Nghiên c u các ñ xu t trên thông qua vi c mô ph ng. dài ñư ng tr ñ i v i m t ñ lu ng, t c ñ ñ n và ñ dài c a burst H n ch ñ n s giúp gi m t i thi u s burst rơi t i m i nút m ng. - Ph n lý thuy t d ng l i vi c nghiên c u t ng quan v m ng thông tin quang và trình bày ng n g n v các thu t toán l p l ch 3.6 Tóm t t kênh.
- 26 - - K t qu mô ph ng ch m i ñưa ra mô hình topo ñơn gi n (g m 11 node lõi và 12 node biên) và h n tr s lư ng kênh trên m i liên k t (8 kênh d li u và 3 kênh ñi u khi n). Do ñó, chưa ñánh giá ñư c chính xác hi u qu c a các thu t toán l p l ch kênh. 2. Hư ng phát tri n Trong ñ án này thông qua mô ph ng và nghiên c u ñã cho th y r ng trong m ng OBS không có gi i thu t l p l ch nào t i ưu cho t t c các nút m ng. M i gi i thu t ch phù h p v i m t s tình tr ng m t ñ lu ng và tình tr ng burst ñ n. Vi c xây d ng và ñưa vào mô hình l p l ch thích nghi s là gi i pháp t i ưu cho vi c l p l ch t i m i nút m ng. Tìm hi u thêm nh ng y u t nh hư ng ñ n hi u qu c a các gi i thu t l p l ch. Đây là hư ng m cho vi c c i ti n mô hình l p l ch trong tương lai. Các k thu t l p l ch khác nhau trên m ng chuy n m ch chùm quang th c t ñã ñư c ñ xu t r t nhi u và ñã có r t nhi u c i ti n và k t h p gi i thu t l p l ch v i các k thu t khác. Do ñó cũng ñ t ra m t thách th c ñáng k ñ i v i hư ng phát tri n ti p v lĩnh v c này. Hư ng phát tri n c a ñ tài là c i ti n mô hình l p l ch tìm ra thu t toán t i ưu cho vi c l p l ch t i m i nút m ng và k t h p v i vi c xây d ng thu t toán ñ nh tuy n cho m ng toàn quang.