Tài liệu Điṇ h tuyến Multicast trong maṇ g cáp quang

Đinh ̣ tuyế n Multicast trong ma ̣ng cáp quang Bùi Thị Ngọc Tú Đại học khoa học tự nhiên; Khoa Toán-Cơ-Tin Chuyên ngành: Đảm bảo toán cho máy tiń h và HTTT Mã số: 60 46 35 Người hướng dẫn: TS Lê Tro ̣ng Viñ h Năm bảo vệ: 2011 Abstract. Giới thiệu về mạng cáp quang, các vấn đề chính trong mạng cáp quang: Công nghệ WDM; Kiến trúc mạng cáp quang ; Các vấn đề trong mạng cáp quang . Trình bày chi tiết về bài toán định tuyến multicast trong mạng quang: Các khái niệm và định nghĩa; Bài toán; Các cách tiếp cận giải bài toán. Áp dụng giải thuật GA cho bài toán MRWA: Giải thuật di truyền; Giải thuật di truyền giải bài toán; Các kết quả thực nghiệm và thảo luận. Keywords. Mạng cáp quang Toán tin; Thuật di truyền; Định tuyến multicast; Mạng truyền thông Content: Chương I: MẠNG CÁP QUANG – NỀN TẢNG CHO MẠNG THẾ HỆ MỚI I.1 Công nghệ WDM WDM là phương thức ghép kênh quang theo bước sóng. Thông thường trong tuyến thông tin quang điểm nối điểm, mỗi một sợi quang cho một tia laser với một bước sóng ánh sáng truyền qua, tại đầu thu, bộ tách sóng quang tương ứng sẽ nhận tín hiệu từ sợi này. Mỗi một sóng laser mang một số tín hiệu điện với một phổ nhất định. Từ những năm 1980, công nghệ sợi quang có nhiều tiến bộ nên phương thức ghép kênh quang theo bước sóng được ứng dụng trong mạng viễn thông đường trục và quốc tế. Ở đây, WDM cho phép ta tăng dung lượng kênh mà không cần tăng tốc độ bit của đường truyền và cũng không dùng thêm sợi dẫn quang. Nó cho phép khai thác một cách đơn giản và kinh tế lượng thông tin vào một sợi quang đơn mode trên cự ly dài và tăng độ 1 mềm dẻo của cấu trúc phân phối. Những đường truyền dẫn thử nghiệm đã đạt được tốc độ lưu lượng 160Gbit/s phân phối trên 8 kênh ghép theo bước sóng. Hơn nữa, ghép theo WDM không chỉ giảm bớt ảnh hưởng của tán sắc mà còn chống được tổn hao do phân cực. Các hệ thống thông tin quang hiện đại có sử dụng bộ khuếch đại quang để ghép nhiều kênh theo WDM. Nếu với lưu lượng là 2,5Gbit/s, ghép theo WDM từ 8 đến 16 luồng thì ta thực hiện được một đường thông tin quang với lưu lượng là 20Gbit/s đến 40Gbit/s trên một sợi đơn mode mà vẫn dùng lại được các thiết bị ghép kênh và phân kênh hiện có. Nói một cách khác, WDM cho phép tăng tích số lưu lượng nhân với cự ly trên một sợi quang. I.2 Kiến trúc mạng quang Một mạng cáp quang bao gồm các nút OCXs được kết nối với nhau bởi những liên kết điểm tới điểm theo một topo bất kỳ như hình 1.2. Mỗi nút cuối (liên kết với người dùng) kết nối tới một nút định tuyến thông qua một liên kết quang. Tập hợp những nút cuối gắn với một nút định tuyến tạo nên một nút mạng. Mỗi nút có các đầu truyền và các đầu nhận tương ứng để gửi dữ liệu vào trong mạng và nhận dữ liệu từ mạng về. B C 1 1 A OCX OCX 2 OCX 1 OCX 1 2 OCX F OCX 2 D E Hình 1.2: Kiến trúc mạng cáp quang Các thông điệp được gửi từ nút này đến nút khác thông qua một lightpath. Một lightpath là một đường dẫn quang được thiết lập giữa hai nút và ấn định cho các bước sóng trên toàn bộ đường dẫn quang đó. Trong trường hợp mạng không có sự biến đổi các bước sóng (wavelength conversion) thì các bước sóng trên toàn bộ các liên kết của đường dẫn được yêu cầu là giống nhau. Điều này được biết đến như là ràng buộc về sự liên tục bước sóng 2 (wavelength continuty constraint). Một điều hiển nhiên là hai lightpaths không được gán cùng một bước sóng trên cùng một liên kết (link). I.3 Các vấn đề trong mạng cáp quang I.3.1 Các kiểu truyền thông trên mạng  Unicast: Truyền thông loại này cho phép các gói tin được gửi từ một nút nguồn đến một nút đích.  Broadcast: Các gói tin được gửi từ một nút (nút nguồn) đến tất cả các nút còn lại trong mạng.  Multicast: Các gói được gửi từ một nút nguồn s đến một nhóm các nút đích D. Rõ ràng, định tuyến multicast là trường hợp tổng quát nhất: |D| = 1 sẽ tương ứng với unicast, |D| = n-1 (n là số nút mạng) tương ứng với broadcast. I.3.2 Các yêu cầu truyền thông trên mạng Yêu cầu truyền thông trên mạng có hai dạng: Dạng tĩnh (static): Còn gọi là off-line, trong đó một tập các yêu cầu kết nối đã được biết trước và mục tiêu là thiết lập các kết nối để thỏa mãn yêu cầu này với chi phí thấp nhất. Vì bài toán là off-line, nên các thuật toán cho dạng này không quan tâm nhiều về thời gian thực hiện mà quan tâm nhiều đến độ chính xác. Dạng động (dynamic): Còn gọi là on-line, trong đó các yêu cầu kết nối đến và rời khỏi mạng một cách ngẫu nhiên nào đó. Do các yêu cầu là on-line, nên các thuật toán cho dạng này khác với dạng tĩnh là yêu cầu về thời gian thực hiện nhanh. I.3.3 Định tuyến và gán bước sóng Thuật toán để chọn tuyến (path hoặc tree) và gán bước sóng (wavelength) cho việc thiết lập các lightpath được gọi là thuật toán định tuyến và ấn định bước sóng RWA (MRWA). Bài toán RWA (MRWA) là bài toán NP đầy đủ nên thường được chia thành hai bài toán nhỏ và giải độc lập: định tuyến và gán bước sóng. 3 a. Định tuyến Phương pháp định tuyến cố định ( fixed routing) Tìm một cây cố đinh, ̣ khi có yêu cầ u kế t nố i ta dùng cây đó để setup Đinh ̣ tuyế n luân phiên cố đinh ̣ (fixed alternate routing) Chúng ta không sử dụng một đường (một cây) cố định như mà dùng nhiều đường (cây) cố định để thiết lập lightpath cho chúng. Có nghĩa là khi yêu cầu kết nối đến, chúng ta có thể tìm các bước sóng trên tất cả các đường (cây) này để thiết lập lightpath (light-tree). Thông thường k đường đi ngắn nhất giữa nút nguồn và đích (tính offline theo thuật toán kshostest paths) được dùng làm các đường cố định đó. Phương pháp định tuyến thích nghi (adaptive routing) Trong định tuyến thích nghi, với mỗi cặp nút nguồn s và nút đích d, không một đường (cây) cố định nào được chọn trước cho nó. Khi yêu cầu kết nối đến, thuật toán sẽ tìm đường đi ngắn nhất giữa s và d (tập D)có bước sóng rỗi dựa trên trạng thái mạng để thiết lập lightpath (light-tree) cho nó. Khi không tìm được đường đi như vậy, kết nối sẽ bị block. b. Gán bước sóng  Gán bước sóng ngẫu nhiên (Random).  Gán bước sóng dựa trên bước sóng sử dụng ít nhất (LU Least Used).  Gán bước sóng theo số bước sóng sử dụng nhiều nhất ( MU Most Used).  Gán bước sóng theo thứ tự cố định( Fixed oder). I.3.4. Sự cần thiết của các thiết bị chuyển đổi bước sóng. Sự chuyển đổi bước sóng là khả năng chuyền tín hiệu từ bước sóng này (w1) thành bước sóng khác (w2). Bộ chuyển đổi rất có ích trong việc giảm xác suất tắc nghẽn mạng. Các bộ chuyển đổi bước sóng giúp loại trừ sự bắt buộc tính liên tục về bước sóng. Nếu không có các thiết bị chuyển đổi bước sóng thì phải có sự ràng buộc cần thiết về bước sóng. Sự ràng buộc này làm giảm hiệu quả sử dụng các tài nguyên mạng. Các trường hợp chuyển đổi bước sóng. 4 - Chuyển đổi hoàn toàn - Chuyển đổi giới hạn - Chuyển đổi cố định. Chương II: ĐỊNH TUYẾN MULTICAST TRONG MẠNG CÁP QUANG II.1 Các khái niệm và định nghĩa - MC node (Multicast Capble): Có khả năng chia ánh sáng , chuyể n 1 tín hiê ̣u từ cổ ng đế n thành nhiề u tiń hiê ̣u ở cổ ng ra trên cùng mô ̣t bước sóng. - MI node (Multicast Incapble): Chuyể n 1 tín hiệu từ cổ ng đến đến đúng 1 cổ ng ra . Trong đó, nút ToC chỉ có khả năng trích (lấy để sử dụng) hoặc chuyển tiếp tín hiệu đến một cổng ra. Nút TaC có cả hai khả năng này. - VS node (Virtual Source): Là nút MC trang bị thêm khả năng chuyển đổi bước sóng. => Mạng có một số MC node và các MI node còn lại gọi là mạng có khả năng phân chia bước sóng thưa. II.2 Bài toán Với các khái niệm đã trình bày như trên, bài toán định tuyến và gán bước sóng đáp ứng yêu cầu multicast có thể phát biểu như sau: Topo mạng: Một mạng cáp quang có thê biểu diễn như một đồ thị G(V, E), trong đó V là số nút trong mạng và E là tập các kết nối, mạng chỉ có một số nút là MC, VS tại các nút chiến lược, các nút còn lại là MI với khả năng TaC. Kiểu truyền thông: Mutlicast, nút nguồn s cần gửi các gói tin đến một tập các D các nút đích (D là tập con của V). Yêu cầu truyền thông: tuân theo quá trình Poisson. Thời gian nắm giữ đường truyền theo phân bố mũ. Mục tiêu: Thiết lập các light-tree (hoặc light-forest) cho các yêu cầu kết nối multicast này xác suất tắc nghẽn là ít nhất. 5 Gọi N là số các yêu cầu kết nối đến trong khoảng thời gian T nào đó, với mỗi một yêu cầu kết nối i, gọi di là tổng số các nút đích. Gọi ri là số các nút đích không được phục vụ trong yêu cầu kết nối i. Khi đó, xác suất tắc nghẽn p của mạng được tính theo công thức sau: N p r i 1 N i d i 1 (1) i II.3 Các cách tiếp cận giải bài toán II.3.1 Thuật toán Member-Only Các ký hiệu và định nghĩa: F(s, D): là tập các cây multicast (rừng –forest) cho một yêu cầu kết nối multicast với nút nguồn s và tập các nút đích D. V: Là tập các nút được dùng cho việc mở rộng (phát triển) cây. V’: Là tập các nút không được dùng cho việc mở rộng cây. Z: Tập các nút nguồn ảo VS. UV: Tập các nút đích chưa được thêm vào cây F(s, D) T: Tập các nút trong cây multicast. P (x, y): là đường đi ngắn nhất giữa nút x và y. d(x, y): là giá của đường đi P (x, y) được tính dựa trên số hop. Nút VS có độ ưu tiên cao nhất, sau là các nút MC và thấp nhất là các nút MI. thuật toán Member-Only có thể tóm tắt như sau: 1: F (s, D) = ø, UV = D; UV được sắp xếp theo thứ tự không giảm theo khoảng cách của chúng đến nguồn s. 2: V = s, V’ = ø, Z = ø, T = ø 3: Xét các nút đích trong UV lần lượt. Giả sử rằng, chúng ta đang xét nút u. 4: Tìm P (v, u): v ∈V,  x ∈ P (v, u): x  V’ 5: If tồn tại một tập các nút v: lựa chọn nút v với độ ưu tiên cao nhất 6: duv = d(u, v); dus = d (u, s) 6 7: IF (  P (v, u)) { 8: 9: if (dus ≥duv ) Thêm mọi link e ∈ P (v, u) tới T 10: else { 11: Tìm P (w, u):w ∈Z; 12: duw = d (u, w) 13: if (dus ≥duw ) Thêm mọi link e ∈ P (w, u) to T; 14: 15: else Thêm mọi link e ∈ P (s, u) to T; 16: } 17: if (v = MI node) chuyển v từ V sang V’ 18: for  x ∈ P (v, u) or P(s, u) or P (w, u): 19: if (x ≠ v (or x ≠ s or x ≠ w) && x ≠ u){ 20: if (x = MI node) chuyển x tới V’; 21: if (x = MC node) chuyển x tới V; 22: if (x = VS node) chuyển x tới Z; } 23: Chuyển u từ UV sang V 24: if (UV = ø) 26: STOP. 27: else 28: Go to (3) } 29:ELSE (!  P (v, u)) 30: Chuyển các nhánh từ T tới F (s, D) và chuyể n về bước (2) Mặc dù thuật toán này có thể tìm được light-forest trong phần lớn các trường hợp, nhưng nó vẫn có lỗi trong một số trường hợp được mô tả dưới đây. II.3.2 Những thiếu sót của thuật toán Member-Only Để dễ dàng nhận ra các thiếu sót của thuật toán Member-Only, chúng tôi sẽ trình bày thông qua các ví dụ dưới đây. 7  Ví dụ 1 Xét mạng đơn giản như trong hình 2.1, nhãn của các cạnh là giá của chúng. Giả sử rằng, chúng ta có một yêu cầu multicast (s, {d1, d2, d3}) - Theo thuâ ̣t toán: light-forest ({s-MI-d1-d2-d3}) với giá 2+2+4+5 = 13 - Nhìn thấy: light-forest {s-MI-d1-d3-d2}) với giá ít hơn 2+2+3+5 =12. - Thực tế: Sau khi thêm một nút từ UV tới cây T, thứ tự các nút còn lại trong UV có thể thay đổi theo nghĩa khoảng cách giữa chúng đến cây hiện s hành. 2 Hình 2.1: Mạng đơnMIgiản 1 2 4  Ví dụ 2 d3 3 d1 Xét mạng đơn giản được mô tả trong hình 2.2 và một yêu cầu multicast (s, 3 4 5 {d1, d2}), tìm thấy light-forest bởi thuật toán Member-Only sẽ là ({s-VS-MId1-d2}) với giá 3 +2+1+6 =12. Tuy nhiên, một light-forest khác ({s-VS-MI-d1}, d2 {VS-MI-d2}) với giá 3+2+1+ 3+2 = 11 cũng đáp ứng yêu cầu kết nối này. Lý do của sự thiếu sót này đó là thuật toán Member-Only đã sử dụng dus tại bước 6 như là một ngưỡng (threshold) cho việc tạo một nhánh mới hoặc một cây s mới và ngưỡng này là cố định. 3 vs 2 7 MI 3 d2 1 6 d1 Hình 2.2: Mạng đơn giản.2 Thuật toán cải tiến: - Nhượ c điể m thứ nhấ t tại bước 3: Xét u ∈UV gần nhất với V. - Nhượ c điể m thứ nhấ t tại bước 6: duv = d(u, v); dus = min {d (u, x)} : x ∈Z; Nhươ ̣c điể m thứ ba là cách tiếp cận dựa trên nút nguồn (source-based), như được chỉ ra trong ví dụ sau: 8  Ví dụ 3 Xét mạng đơn giản trong hình 2.3 và một yêu cầu multicast (s, {d1, d2}). s 1 MI 2 1 MC 1 d1 3 d 2 Hình 2.3: Mạng đơn giản 3 Dựa theo chiến lược Source-based đó là xây dựng light-forest dựa trên các đường đường đi ngắn nhất, chúng ta sẽ tìm được light-forest ({s-MI-d1-MCd2}) đáp ứng yêu cầu multicast với giá 1+2+1+3 = 7, tròn khi một light-forest khác ({s-MI-MC-d2}, {MC-d1}) có giá ít hơn là 1+1+3 + 1 = 6 nên được sử dụng. Để vượt qua nhược điểm này, chúng tôi sẽ trình bày thuật toán di truyền GA Chương III: ÁP DỤNG GIẢI THUẬT DI TRUYỀN CHO ĐỊNH TUYẾN MULTICAST III.1 Giải thuật di truyền III.1.2 Ý tưởng của thuật toán di truyền Thuật toán di truyền được xây dựng dựa trên quy luật tiến hóa sinh học hay phát triển tự nhiên của một quần thể sống. Các cá thể trải qua một quá trình phát triển và sinh sản để tạo ra những cá thể mới cho thế hệ tiếp theo. Trong quá trình tăng trưởng và phát triển những cá thể xấu (theo một tiêu chuẩn nào đó hay còn gọi là độ thích nghi với môi trường) sẽ bị đào thải, ngược lại, những cá thể tốt sẽ được giữ lại (đây chính là quá trình chọn lọc) và được lai ghép (quá trình lai ghép) để tạo ra những cá thể mới cho thế hệ sau. Những cá thể mới được sinh ra mang những tính trạng của cá thể cha-mẹ (còn gọi là hiện tượng di truyền). 9 III.1.3 Các vấn đề cơ bản về thuật toán di truyền - Sự diểu diễn của cá thể (encoding mechanism) - Đánh giá độ thích nghi (fitness function) Hàm Fitness là hàm dùng để đánh giá độ tốt của một lời giải hoặc cá thể. Hàm Fitness nhận vào một tham số là xâu mã hóa nhị phân của một cá thể và trả ra một số thực. Tùy theo giá trị của số thực này mà ta biết độ tốt của cá thể đó. Lai ghép (crossover operator) + Lai ghép đơn điểm (single-point crossover) + Lai ghép đa điểm (multi-point crossover) + Quá trình lai ghép: Phép lai xảy ra với xác suất là pc (đây là tham số do người dùng tự định nghĩa). Xác suất pc này cho ta số cá thể tham gia lai ghép là pc* pop_size (pop_size là kích thước quần thể). - Đột biến (mutation operator) Là quá trình tạo ra cá thể mới từ một cá thể ban đầu bằng cách thay đổi một số gen của nó. Nếu sử dụng biểu diễn nhị phân thì phép đột biết thường sử dụng là bit flipping, nghĩa là nếu gen là 1 thì được đổi thành 0 và ngược lại. - Chọn lọc và thay thế (slection and replacement) Chọn lọc và thay thế (cũng được biết như là reproduction) là quá trình chọn những cá thể từ quần thể hiện tại để tạo ra thế hệ sau của nó. Trong quá trình này diễn ra sự đào thải những cá thể xấu chỉ giữ lại những cá thể tốt. - Điều kiện dừng (stopping conditions) Thuật toán di truyền là một quá trình ngẫu nhiên, nên ta phải đặt điều kiện dừng. Nó sẽ dừng sau một số hữu hạn các thế hệ hoặc tối ưu toàn cục đã đạt được, hoặc giá trị trung bình của độ thích nghi trên tất cả các cá thể của quần thể không thay đổi... Tóm lại, mã giả của một thuật toán di truyền được viết như sau: Bắt đầu t=0; Khởi tạo p(t); 10 Tính độ thích nghi cho các cá thể thuộc P(t); Khi (điều kiện dừng chưa thoả mãn) lặp t=t+1; Tái sinh P’(t) từ P(t); Lai Q(t) từ P(t-1); Đột biến R(t) từ P(t-1); Chọn lọc P(t) từ P(t-1)  Q(t)  R(t)  P(t); Hết lặp; Kết thúc; III.2 Giải thuật di truyền giải bài toán Để áp dụng thuật toán GA cho bài toán định tuyến multicast, các nút mạng cần được trang bị một bảng địnhv1tuyến, trong đó chứa K đường v0 v5 v2 v3 v4 Route table of V0->V4 Route no. 0 1 … K-1 Route list V0-V4 V0-V5-V4 ….. V0-V5-V1-V2-V3-V4 Hình 3.1. Ví dụ của bảng định tuyến Các bước chính của thuật toán định tuyến multicast dựa trên thuật toán di truyền được mô tả như sau 1) Sự biểu diễn của các cá thể - 1 Multicast có n nút đić h , tương ứng 1 cá thể có n số nguyên go ̣i là 1 gen. Mỗi gi biể u diễn cho 1 nút đích di nhận giá trị từ 0->K-1. Các cá thể tạo bằng cách kết hợp n số nguyên, từ các cá thể này hình thành quần thể g1 g2 ……… . …… gi gi =1 Route table of s->di Route no. 0 1 … K-1 Route list s-di s-….-di ….. 11 s-…………. -di gn Hình 3.2: Sự quan hệ giữa cá thể, gen và bảng định tuyến • Giải mã của một cá thể - Ghép các đường đi từ nút nguồ n s đế n tấ t cả các nút đić h d thành 1 đồ thị. Cắ t đi những nhánh không cần thiết (sử dụng thuật toán MST-Prim). Cây thu đươ ̣c là cây Multicast. 3) Hàm đo độ thích nghi (Fitness Function) * Đinh ̣ nghiã : - C(i) là số các liên kết của light-forest được xây dựng từ các đường biểu diễn bởi cá thể i, L là số các link của mạng. F(i) = 1- C(i)/L. - Mục tiêu: Tối ưu số liên kết của light-forest. Nhận xét: Điều này có thể dẫn tới một light-forest có giá nhỏ hơn nhưng khó để thực hiện, bởi vì light-forest này có vài nút đích trên các nhánh không với bước sóng rỗi. Do vậy, để đảm bảo sự thỏa hiệp (trade-off) giữa giá của lightforest và sự thực hiện, chúng tôi định nghĩa hàm đo độ thích nghi mới sau: * Định nghĩa mới: - Gọi d(i) là số các nút đích của một yêu cầu multicast, l(i) là số bước sóng, r(i) là số các đích thuộc các nhánh không có bước sóng rỗi của light-forest f(i) được xây dựng từ cá thể i. Chúng tôi định nghĩa giá C(i) của f(i) là: - Nếu r(i) = d(i), C = +∞; - Ngược lại C(i) = l(i) + α r(i), trong đó α >0 là tham số thiết kế. F(i) = 1/ C(i). 4) Thao tác lai ghép Thao tác này bắt trước quá trình giao hợp trong tự nhiên. Để thực hiện lai ghép, hai cá thể được chọn (cá thể cha mẹ) đầu tiên, và một số nguyên (điểm lai ghép) được sinh ngẫu nhiên trong khoảng [2, n-1] ( trong đó n là số nút 12 Crossover pointer g1 g 2 ….. gi-1 gi gi+1 ….. gn-1 gn đích của yêu cầu multicast). Sau đó, các cá thể mới (con) được sinh ra bằng cách bằng cách thay đổi phần thứ hai của các cá thể cha mẹ của nó như được mô tả trong hình 3.3 dưới đây. Hình 3.3: Sự lai ghép 5) Thao tác đột biến Thao tác đột biết là một kiểu thay đổi ngẫu nhiên trong một cá thể. Trong thuật toán này, đột biến một điểm được sử dụng. Đó là, một gen của cá thể được thay đổi với một xác suất nào đó (được hiểu như là xác suất đột biến). Quá trình này cũng được thực hiện khi kích thước quần thể tăng gấp đôi hoặc tất cả các cá thể trong quần thể hiện thời được xem xét. Mutation pointer Parent g1 g2 g1 g2 Child ….. ….. gi-1 gi = r gi+1 ….. gn-1 gn gi-1 gi = r’ gi+1 ….. gn-1 gn Hình 3.4: Thao tác đột biến 6) Quá trình chọn lọc Sau khi áp dụng các thao tác lai ghép và đột biến. Quá trình chọn lọc sẽ lựa chọn P có độ thích nghi cao nhất từ cả các cá thể cha mẹ và cá thể con cho thế hệ tiếp theo. Quá trình này được lặp lại cho đến khi điều kiện dừng được thỏa mãn. 7) Điều kiện dừng Sự thực hiện của thuật toán di truyền có thể dừng khi hoặc giá trị trung bình hoặc giá trị cao nhất của độ đo thích nghi không thay đổi hoặc số thế hệ đã vượt quá G (G là tham số thiết kế). III.3 Các kết quả thực nghiệm và thảo luận Trong phần này, chung tôi sẽ trình bày hiệu năng của thuật toán di truyền trong sự so sánh với thuật toán Member-Only. Các kết quả thực nghiệm được mô phỏng trên bộ công cự ns-2 [8] với hai topo đặc trưng được mô tả như hình 3.5 dưới đây: 13 12 11 1 10 0 13 7 3 4 6 9 2 8 5 (a) 17 18 15 14 16 0 8 3 2 9 4 1 7 5 13 10 12 6 2 11 (b) Hình 3.5 Topo: (a) NSF với 14 nút và 21 links. (b) EON với19 nút và 35 links. Đối với thuật toán GA, chúng tôi đặt K = 8, P = 16, G = 8, và xác suất của thao tác đột biến là 0.4. Hình 3.6 kết quả mô phỏng của thuật toán Member-Only và sự cải tiến của nó. Xác suất tắc nghẽn Đối với mạng NSF với 25 phiên multicast, xác suất tắc nghẽn của thuật toán cải tiến (MemO-New) là 0.061 trong khi thuật toán nguyên gốc là 0.69. 0.1 0.09 0.08 0.07 0.06 0.05 0.04 0.03 0.02 0.01 0 MemO MemO-New 10 15 20 25 30 Số phiên multicast Hình 3.6: So sánh thuật toán Member-Only và sự cải tiến Hình 3.7 mô tả hiệu năng của thuật toán GA với hai hàm đo độ thích nghi 14 0.07 GA Xác suất tắc nghẽn 0.06 GA-New 0.05 0.04 0.03 0.02 0.01 0 10 15 20 25 30 Số phiên multicast Hình 3.7: So sánh hiệu năng thuật toán di truyền với hai hàm đo độ thích nghi Sự so sánh trong hình 3.7 chi ra rõ ràng thuật toán di truyền với hàm đo độ thích nghi mới (GA-NewF) luôn giành được xác suất tắc nghẽn thấp hơn. 0.09 Xác suất tắc nghẽn 0.08 MemO-New 0.07 GA-NewF 0.06 0.05 0.04 0.03 0.02 0.01 0 10 15 20 25 30 Số phiên multicast Hình 3.8: So sánh hiệu quả của thuật toán di truyền và Member-Only Với 25 phiên multicast, xác suất tắc nghẽn của Member-Only và GA là 0.061 và 0.036 tương ứng. References : [1] C. S.R Murthy and M. Gurusamy, “Chapter 8: Optical Multicast Routing - WDM Optical Networks: Concepts, Design, and Algorithms”, Prentice Hall Inc, 2002 [2] X. Zang, J.Wei, and C. Qiao, “Constrained Multicast Routing in Networks with Sparse Light Splitting”, INFOCOM 2000. [3] N. Sreenath, G. Mohan, and C. Siva Ram Murthy, “Virtual source based multicast routing in WDM optical networks,” Photonic Network Communications, vol 3, no. 3, pp. 217-230, July 2001 [4] D.E. Goldberg, “Genetic Algorithms in Search, Optimization, and Machine Learning,” Addison-Wesley Publishing Company, Inc., 1997 15 [5] Z. Michalewicz, “Genetic Algorithms + Data Structres = Evolution programs,” Springer-Verlag, 1992 [6] R. H. Hwang, W.Y. Do and S. C. Yang, “Multicast Routing Based on Genetic Algorithms”, Journal of Information Science and Engineering, 2000, pp.885-901. [7] M. T. Chen and S.S. Tseng, ”A Genetic Algorithm for Multicast Routing Under Delay Constraint in WDM Network with Different Light Splitting”, Journal of Information Science and Engineering, 2005, pp.85-108. [8] http://www.isi.edu/nsnam/ns/index.html, 2003. 16