ĐỒ ÁN TỐT NGHIỆP ĐIỆN TỬ TIN HỌC So sánh các thuật toán thiết kế topo logic
NỘI DUNG ĐỒ ÁN
ĐỒ ÁN TỐT NGHIỆP ĐIỆN TỬ TIN HỌC So sánh các thuật toán thiết kế topo logic và tái cấu hình topo logic ứng dụng giải thuật di truyền trong mạng IPWDM
MỤC LỤC
LỜI CAM ĐOAN.. 1
MỤC LỤC.. 2
BẢNG CÁC CHỮ CÁI VIẾT TẮT.. 6
LỜI NÓI ĐẦU.. 8
CHƯƠNG 1. 10
TỔNG QUAN VỀ MẠNG IP/WDM... 10
1.1 Giới thiệu chương. 10
1.2 Giới thiệu chung về IP. 10
1.3 Tổng quan về công nghệ WDM... 11
1.3.1 Giới thiệu chung về WDM... 11
1.3.2 Nguyên lý hoạt động của mạng WDM... 12
1.3.3 Các thành phần trong mạng WDM... 12
1.3.3.1 Thiết bị đầu cuối OLT.. 12
1.3.3.2 Bộ khuếch đại quang OAMP. 13
1.3.3.3 Bộ xen/rớt quang OADM... 14
1.3.3.4 Bộ kết nối chéo quang OXC.. 14
1.3.4 Cấu trúc mạng WDM... 16
1.3.4.1 Cấu trúc mạng WDM điểm – điểm.. 16
1.3.4.2 Cấu trúc mạng WDM định tuyến theo bước sóng quang. 16
1.4 Tổng quan về mạng IP/WDM... 17
1.4.1 Chuyển tải IP trên mạng WDM... 17
1.4.2 Giải thích sự ra đời của công nghệ IP trên WDM... 18
1.5 Các mô hình mạng IP /WDM... 20
1.5.1 Mô hình xếp chồng. 21
1.5.2 Mô hình ngang hàng. 22
1.5.3 Mô hình mở rộng. 23
1.6 Kết luận chương. 23
CHƯƠNG 2. 24
KỸ THUẬT LƯU LƯỢNG TRONG MẠNG IP/WDM... 24
2.1 Giới thiệu chương. 24
2.2 Mục tiêu của kỹ thuật lưu lượng. 24
2.3 Khái niệm kỹ thuật lưu lượng trong mạng IP/WDM... 25
2.3.1 Kỹ thuật lưu lượng IP/MPLS. 26
2.3.1.1 Những hạn chế trong kỹ thuật lưu lượng IP. 26
2.3.1.2 Kỹ thuật lưu lượng MPLS. 27
2.3.1.3 Cơ chế bảo vệ và khôi phục đường dẫn trong MPLS. 30
2.3.2 Kỹ thuật lưu lượng trong mạng WDM... 30
2.3.2.1 Định tuyến và gán bước sóng trong mạng WDM... 30
2.3.2.1.1 Định tuyến và gán bước sóng tĩnh. 30
2.3.2.1.2 Định tuyến và gán bước sóng động. 32
2.3.2.1.3 Cơ chế bảo vệ lưu lượng trong mạng WDM... 33
2.4 Các mô hình thực hiện kỹ thuật lưu lượng trọng mạng IP/WDM... 35
2.4.1 Kỹ thuật lưu lượng chồng lấn. 35
2.4.2 Kỹ thuật lưu lượng tích hợp. 36
2.4.3 So sánh 2 mô hình. 37
2.5 Kết luận chương. 38
CHƯƠNG 3. 39
THIẾT KẾ TOPO LOGIC TRONG MẠNG IP/WDM... 39
3.1 Giới thiệu chương. 39
3.2 Sự cần thiết của việc thiết kế topologic. 39
3.3 Thiết kế topo logic. 40
3.3.1 Giới thiệu về topo trong mạng WDM... 40
3.3.1.1 Topo vật lý. 40
3.3.1.2 Topo logic. 41
3.3.1.3 So sánh giữa topo vật lý và topo logic. 41
3.3.2 Tóm tắt bài toán thiết kế topo logic. 42
3.3.3 Mục tiêu của bài toán thiết kế topo logic. 43
3.3.4 Một số thuật toán thiết kế topo logic. 43
3.3.4.1 Thuật toán thiết kế topo logic HLDA.. 44
3.3.4.2 Thuật toán thiết kế topo logic MLDA.. 45
3.3.4.3 Thuật toán thiết kế topologic TILDA.. 46
3.3.4.4 Thuật toán thiết kế topologic RLDA.. 47
3.4 Kết quả mô phỏng phần thiết kế topo logic dùng thuật toán HLDA, MLDA, TILDA và RLDA ứng dụng Toolbox Matplan của Matlab. 47
3.4.1 Kết quả chạy chương trình thiết kế topo logic. 47
3.4.2 So sánh các tham số đầu ra khi thiết kế topo logic sử dụng thuật toán HLDA, MLDA, TILDA và RLDA 49
3.5 Kết luận chương. 53
CHƯƠNG 4. 55
TÁI CẤU HÌNH TOPOLOGIC ỨNG DỤNG GIẢI THUẬT DI TRUYỀN.. 55
4.1 Giới thiệu chương. 55
4.2 Tại sao phải tái cấu hình topo logic. 55
4.3 Phân tích bài toán tái cấu hình topo logic. 56
4.4 Giới thiệu thuật toán di truyền GA.. 56
4.4.1 GA.. 56
4.4.2 Các tính chất đặc thù của thuật toán di truyền. 57
4.4.3 Ưu nhược điểm của thuật toán di truyền GA.. 57
4.4.4 Các khái niệm của thuật toán GA.. 57
4.4.4.1 Cá thể. 57
4.4.4.2 Chọn lọc. 57
4.4.4.3 Lai ghép. 58
4.4.4.4 Đột biến. 58
4.4.5 Các thông số của thuật toán GA.. 58
4.4.6 Sơ đồ thuật toán di truyền GA.. 59
4.5 Ứng dụng thuật toán di truyền GA vào tái cấu hình topo logic. 59
4.5.1 Quan hệ giữa mạng và thuật toán di truyền. 59
4.5.2 Mã hoá. 60
4.5.3 Hàm thích nghi60
4.5.4 Điều kiện kết thúc điều kiện dừng. 61
4.5.5 Áp dụng thuật toán GA vào bà toán tái cấu hình topo logic cụ thể. 62
4.5.5.1 Khởi tạo quần thể. 62
4.5.5.2 Kiểm tra điều kiện dừng. 62
4.5.5.3 Chọn lọc. 62
4.5.5.4 Lai tạo. 63
4.5.5.5 Đột biến. 63
4.6 Ứng dụng MATLAB mô phỏng thuật toán di truyền GA để tái cấu hình. 63
4.6.1 Giao diện chương trình mô phỏng. 63
4.6.2 Hướng dẫn sử dụng chương trình. 64
4.6.3 Kết quả mô phỏng và nhận xét64
4.7 Kết luận chương. 73
KẾT LUẬN CHUNG VÀ HƯỚNG PHÁT TRIỂN ĐỀ TÀI. 74
TÀI LIỆU THAM KHẢO.. 75
PHỤ LỤC.. 76
ĐỀ TÀI : “SO SÁNH CÁC THUẬT TOÁN THIẾT KẾ TOPO LOGIC VÀ TÁI CẤU HÌNH TOPO LOGIC ỨNG DỤNG THUẬT TOÁN DI TRUYỀN TRONG MẠNG IP/WDM”.
1. Đặt vấn đề
Công nghệ WDM cho dung lượng truyền dẫn cực lớn. Giao thức IP ngày càng phát triển rộng rãi. Do đó tích hợp IP và WDM để chuyển tải lưu lượng IP trên mạng quang WDM đã trở thành vấn đề cấp bách và quan trọng. Tuy nhiên do số lượng bước sóng sử dụng trong hệ thống WDM là hạn chế do đó vấn đề là phải làm thế nào để sử dụng nguồn tài nguyên này một cách hiệu quả nhất. Vì vậy tối ưu hoá việc sử dụng tài nguyên và hiệu năng của mạng là một yêu cầu đặt ra cho các nhà cung cấp dịch vụ.
Vì lẽ đó cuốn đồ án này sẽ xoáy sâu vào vấn đề kỹ thuật lưu lượng trong mạng IP/WDM, tức là làm thế nào để truyền lưu lượng IP trên mạng quang một cách hiệu quả nhất. Đồ án này đưa ra 2 giải pháp đó là khi lưu lượng mạng thay đổi thì “ta thiết kế topo mạng mới hoặc tái cấu hình topo logic dùng thuật toán di truyền GA”
2. Sự ra đời của mạng IP/WDM [1]
Đã có nhiều phương pháp để cung cấp dịch vụ gói IP trên mạng WDM được đề nghị như hình trên. Tuy nhiên việc quản lý mạng theo các phương pháp trêngặpkhôngítkhó khăn.Nguyênnhânchủ yếugâynên sựphứctạptrong quảnlý chínhlàsựphânlớptheotruyềnthốngcủacácgiaothứcmạng.Cácmạngtruyềnthốngcórất nhiềulớpđộclập,dođócónhiềuchứcnăngchồngchéonhauởcáclớpvàthườngxuyêncósự mâu thuẫn lẫn nhau. Vìvậy, một trong những giảipháp để giảmchi phí xây dựng vàquản lý mạngmột cách triệt để đó là giảmsố lớp giao thức.
Hơnnữa,khidunglượngvàkhảnăngkếtnốimạngtrongcảcôngnghệIPvàWDMtăng lênthìcàngcầnthiếttốiưumạngIPvàbỏquatấtcảcáccôngnghệlớptrunggianđểtạonên mạngInternetquangthậtsựhiệuquảvàmềmdẻo.Tuynhiên,cáclớptrunggiancũngcungcấp mộtsốchứcnăngcógiátrịnhưkỹthuậtlưulượng(TrafficEngineering)vàkhôiphục.Những chứcnăngnàycầnphảiđượcgiữlạitrongmạngIP/WDMbằngcáchđưachúnglênlớpIPhoặc xuống lớp quang. Từ đó công nghệ IP/WDM được ra đời.
3. Kỹ thuật lưu lượng trong mạng IP/WDM
Kỹ thuật lưu lượng TE (Traffic Engineering) chính là cách thức điều khiển các luồng lưu lượng đi qua mạng sao cho sử dụng tối ưu hóa tài nguyên và hiệu năng của mạng. [2]
4. Ứng dụng Matplan và giải thuật di truyền để thiết kế và tái cấu hình topo logic trong mạng IP/WDM
4.1 Bài toán thiết kế topo logic : Dữ liệu vào là topo mạng cáp quang cụ thể và traffic yêu cầu. [3]
+ Sử dụng 4 thuật toán HLDA, MLDA, RLDA, TILDA để thiết kế topo logic :
Nhận xét :
+ Number of Virtual Hops (Số hops ảo) : Khi tăng số bước sóng trên sợi quang thì số hop ảo sẽ giảm xuống. Từ đồ thị ta thấy trong trường hợp này thuật toán HLDA là tốt nhất.
+ Number of Lighpaths (Số lighpath) : Khi tăng số bước sóng trên sợi quang thì số lighpath trên sợi cũng tăng. Từ đồ thị ta thấy trong trường hợp này thuật toán RLDA là tốt nhất.
+ Network Congestion (Nghẽn mạng) : Từ đồ thị ta thấy trong khoảng bước sóng từ 10->15 khả năng nghẽn mạng khi sử dụng thuật toán HLDA, MLDA có xu hướng giảm xuống và thuật toán RLDA, TILDA thì tăng lên khi tăng số bước sóng.
+ Number of wavelengths channels (Số kênh bước sóng được sử dụng) : Khi tăng số bước sóng trên sợi quang thì số kênh bước sóng đã được sử dụng cũng tăng lên. Trong trường hợp này thuật toán TILDA là tốt nhất.
4.2 Bài toán tái cấu hình topo logic : Thiết kế lại topo logic dựa trên topo vật lý và topo logic đã có sẵn trước đó cùng với ma trận lưu lượng mới yêu cầu. [4]
- Mô phỏng với mạng Ring 7 node :
- Ma trận lưu lượng ban đầu : X7node =
+ Thiết kế topo logic dùng thuật toán HLDA (Số hop trung bình : H1 = 1.1964), topo được thiết kế như hình vẽ (A) bên dưới
+ Khi lưu lượng mạng thay đổi :
- Ma trận lưu lượng thay đổi : X’7node =
+ Thiết kế lại dùng thuật toán HLDA (H1’’ = 1.1814)
Màu đỏ chỉ số lighpath mới được thiết lập
Nhận xét: So sánh giá trị hop trung bình nhận thấy rằng phương pháp New-Design có giá trị nhỏ hơn nhiều (H1’’ = 1.1814) so với giá trị tối ưu (H1’ = 1.346) ở bài toán New-Design. Tuy nhiên nếu so sánh số lightpath thay đổi ở 2 hình trên ta thấy có 6 lightpath bị xóa và 6 lightpath được cộng vào, tổng số lightpath thay đổi khi chuyển từ trạng thái hiện hành đến trạng thái mới là rất lớn (NoChange =12) phải mất nhiều thời gian chuyển đổi và có thể làm thất thoát một lượng lớn traffic. Do đó bài toán đặt ra tìm topo mới sao cho số lightpath thay đổi ít hơn so với phương pháp New-Design trong khi giá trị hop trung bình có thể chấp nhận được.
Chính vì vậy, khi ta chạy thuật toán GA thấy số hop trung bình H2’ = 1.2424 trong topo logic mới được thiết kế lại là nhỏ hơn rất nhiều so với số hop trung bình H1’ = 1.346, tuy H2’ = 1.2424> H1’’ = 1.1814 nhưng đây là giá trị chấp nhận được. Lúc này sẽ có 1 số lượng nhỏ số lightpath bị huỷ bỏ cũng như được thiết lập (3 thiết lập và 1 hủy bỏ = 4lighpath<12lighpath). Điều này làm nổi bật lên ưu điểm của bài toán tái cấu hình topo logic dùng thuật toán GA.
Giữ nguyên topo logic của ma trận lưu lượng đã thay đổi, chạy thuật toán GA với số lightpath thay đổi lần lượt là 8, 10, 12 :
|
Traffic |
X7node |
X’7node |
||
|
Phương pháp |
LTD |
Reconfigure |
||
|
Topo logic |
T1 |
T1,8 |
T2,10 |
T3,12 |
|
Giá trị hop trung bình |
H1=1.1964 |
H1,8 =1.1997 |
H2,10=1.1829 |
H3,12 = 1.1585 |
|
Số lighpath thay đổi so với X7node |
|
8 |
10 |
12 |
Bảng : Kiểm soát sự thay đổi traffic trong mạng 7 node
Nhận xét : Qua 3 lần chạy chương trình ứng với số lightpath thay đổi khác nhau thì ta thấy số lượng lightpath thay đổi khi chuyển topo logic càng lớn thì số hop trung bình càng nhỏ.
5. Kết luận chung
+ Giải pháp thiết kế topo logic mới sử dụng các thuật toán như HLDA, MLDA, RLDA, TILDA, mỗi thuật toán đều có 1 ưu điểm riêng, tùy thuộc vào yêu cầu bài toán mà lựa chọn thuật toán thiết kế cho phù hợp
+ Việc tái cấu hình dùng thuật toán GA đã đạt được một số kết quả tương đối, thời gian tìm kiếm càng dài thì mức độ tối ưu càng cao đồng thời số lighpath thay đổi lớn thì không gian tìm kiếm càng rộng, kết quả càng gần tối ưu hơn.
+ Cần nghiên cứu kỹ về thuật toán di truyền GA để có thể giải quyết bài toán một cách hiệu quả và tối ưu nhất, thời gian chạy chương trình tái cấu hình topo logic là quá dài. Đây là hướng phát triển của đề tài.
CHƯƠNG 1
TỔNG QUAN VỀ MẠNG IP/WDM
1.1Giới thiệu chương
Tích hợp IP vào mạng quang WDM (Wavelength Division Multiplexing) là một xu hướng của công nghệ mạng kế tiếp. Các chủ đề chương này giới thiệu một số nội dung cơ bản sau : giới thiệu chung về IP, tổng quan về công nghệ WDM, nguyên lý hoạt động của WDM, các thành phần trong mạng WDM, cấu trúc mạng WDM, tổng quan về mạng IP/WDM, giải thích sơ lược về khái niệm và cách thức chuyển tải IP trên nền WDM. Các ưu khuyết điểm của các cấu trúc trong mạng WDM từ đó có thể giúp ta có thể chọn cấu trúc nào cho phù hợp để làm cơ sở cho các chương tiếp theo.
1.2Giới thiệu chung về IP
IP (Internet Protocol) là một giao thức liên mạng nằm ở lớp 3 trong mô hình OSI. IP bao gồm thông tin địa chỉ và điều khiển cho phép các gói tin được định tuyến. IP cung cấp hoạt động không kết nối phân phối nỗ lực tốt nhất cho các datagram thông qua các liên mạng và cung cấp phân mảnh và tái hợp cho các datagram để hỗ trợ các tuyến dữ liệu với kích thước đơn vị dữ liệu khác nhau. Datagram (packets) là đơn vị dữ liệu dùng trong giao thức IP, và là đơn vị cơ bản của việc truyền tin Internet. Giao thức IP rất thông dụng trong mạng Internet ngày nay.
Định tuyến trong IP : Là quá trình chuyển lưu lượng người dùng từ nguồn đến đích. Trong mạng bộ định tuyến Router được dùng để định tuyến lưu lượng. Router cần dựa vào bảng định tuyến để chuyển gói tin đi.
Hoạt động định tuyến :
+ Quá trình tìm đường : Sử dụng thuật toán tìm đường ngắn nhất Dijkstra, dựa vào đơn vị đo lường chuẩn là Metric (độ dài đường đi, độ tin cậy, độ trễ tuyến, băng thông, tải, chi phí truyền thông.
+ Chuyển gói tin theo đường đã chọn : Dựa vào địa chỉ IP và địa chỉ vật lý (địa chỉ MAC) để chuyển gói đi. Địa chỉ vật lý của gói dữ liệu luôn thay đổi khi qua trạm trung gian, ngược lại địa chỉ IP không thay đổi.
1.3 Tổng quan về công nghệ WDM
1.3.1 Giới thiệu chung về WDM
WDM là phương thức ghép kênh quang theo bước sóng (Wavelength Division Multiplexing). WDM truyền song song nhiều bước sóng trên cùng một sợi quang.
Các kênh tín hiệu khác nhau sẽ được chuyển thành các bước sóng khác nhau và được ghép vào một sợi quang tại đầu phát nhờ bộ ghép kênh và được tách ra trở lại tại đầu thu nhờ bộ phân kênh.
Ưu nhược điểm của mạng WDM
- Ưu điểm : So với hệ thống truyền dẫn đơn kênh quang thì WDM có những ưu điểm sau :
- Hệ thống WDM có dung lượng truyền dẫn lớn hơn nhiều so với hệ thống TDM.
- TDM phải tăng tốc độ số liệu khi lưu lượng truyền dẫn tăng, WDM chỉ cần mang vài tín hiệu, mỗi tín hiệu ứng với mỗi bước sóng riêng.
- Đáp ứng linh hoạt việc nâng cấp dung lượng hệ thống, kỹ thuật WDM cho phép tăng dung lượng của mạng hiện có mà không cần phải gắn thêm sợi quang.
- Nhờ việc định tuyến và phân bố bước sóng trong mạng WDM nên có khả năng quản lý băng tần truyền dẫn và cấu hình lại dịch vụ mạng là hiệu quả và mềm dẻo.
- Truyền chương trình truyền hình chất lượng cao, cự ly dài, giảm chi phí đầu tư mới.
- Những tiến bộ trong công nghệ WDM hứa hẹn sẽ tăng băng thông truyền trên sợi quang lên đến hàng Tbps, đáp ứng nhu cầu sử dụng mạng ở nhiều cấp độ khác nhau.
- Nhược điểm :
- Hiện tại WDM chỉ mới tận dụng băng C và băng L .
- Chi phí khai thác và bảo dưỡng tăng do có nhiều hệ thống cùng hoạt động.
1.3.2 Nguyên lý hoạt động của mạng WDM
Hình 1.1 Nguyên lý ghép kênh phân chia theo bước sóng
Từ hình trên ta thấy các luồng tín hiệu quang từ các nguồn có các bước sóng khác nhau sẽ được ghép lại nhờ bộ ghép kênh MUX. Bộ ghép MUX phải đảm bảo ít suy hao và không cho sự xuyên nhiễu giữa các luồng. Các luồng tín hiệu sau khi ghép được truyền trên một sợi quang tới phía thu. Trên một tuyến đường có cự li dài thì chùm sóng quang được khuyếch đại nhờ các bộ khuyếch đại.
Tại đầu thu, luồng sóng quang được tách ra thành các bước sóng riêng lẻ rồi đưa đến bộ thu Rx tương ứng cho từng luồng. Các bộ tách sóng quang trong thiết bị thu Rx khôi phục lại tín hiệu điện từng luồng tương ứng với phía phát.
1.3.3 Các thành phần trong mạng WDM
1.3.3.1 Thiết bị đầu cuối OLT
Bộ đầu cuối quang OLT (Optical Line Terminal) là thiết bị có trong các mô hình mạng điểm-điểm, thực hiện ghép tín hiệu tại đầu phát, truyền đi trên sợi quang, giải ghép ở đầu thu và chuyển các tín hiệu thành phần đến phía khách hàng .
Hình 1.2 Thiết bị đầu cuối OLT
OLT có 3 khối chức năng chính : chuyển đổi tín hiệu (Transponder), ghép tách bước sóng và khuyếch đại quang (bộ khuyếch đại quang không mô tả trong hình trên).
- Bộ chuyển đổi tín hiệu : Chuyển tín hiệu sang bước sóng, mức công suất và các thông số quang cho phù hợp với yêu cầu chung của lớp kênh quang.
- Bộ ghép tách bước sóng : Thực hiện ghép các tín hiệu thuộc các bước sóng khác nhau thành tín hiệu để truyền đi trên sợi quang theo khuyến nghị của ITU-T.
- Bộ khuyếch đại quang : Có chức năng khuyếch đại tín hiệu.
1.3.3.2 Bộ khuếch đại quang OAMP
Hình 1.3 Mô hình tổng quát của 1 bộ khuếch đại quang
Tín hiệu quang bị suy hao khi truyền. Nếu tín hiệu quá yếu, chẳng hạn như qua một cự li dài mà không có bộ khuếch đại quang thì máy thu không thể tách được tín hiệu. Bộ khuếch đại quang sử dụng để tăng cường tín hiệu quang nhờ khuếch đại.
Thiết bị liên quan đến bộ khuếch đại là trạm lặp mà trước đây đã sử dụng rộng rãi để tái tạo hoàn toàn tín hiệu sau một khoảng cách nhất định. Sau này công nghệ phát triển đã xuất hiện nhiều bộ khuếch đại quang trong đó có bộ khuếch đại EDFA. Với những ưu điểm nổi bật của mình EDFA nhanh chóng trở thành bộ khuếch đại được sử dụng một cách rộng rãi.
Hình 1.4 Bộ khuếch đại dùng sợi quang có pha Erbium
1.3.3.3 Bộ xen/rớt quang OADM
Chức năng chính của OADM là để truy nhập, tách hoặc chuyển tiếp các kênh bước sóng trong mạng quang WDM. OADM thường dùng cho mạng đô thị và mạng quang đường dài vì nó có hiệu quả kinh tế cao. Hình 1.5 đưa ra cấu trúc của một OADM.
Hình 1.5 Bộ xen/rớt quang OADM
1.3.3.4 Bộ kết nối chéo quang OXC
Hình 1.6 đưa ra cấu trúc của một OXC. Trong đó, có 4 sợi đầu vào và 4 sợi đầu ra, mỗi sợi có một số bước sóng. Qua bộ tách, các tín hiệu có thể tới các cổng. Phụ thuộc vào cài đặt chuyển mạch, một tín hiệu trên bước sóng nào đó từ một sợi có thể kết nối tới cùng bước sóng nhưng trên một sợi đầu ra khác. Trong thực tế, có thể có nhiều tín hiệu cạnh tranh một kênh bước sóng trên một sợi đầu ra nên gây ra tranh chấp. Để giảm bớt tranh chấp đã đưa vào sử dụng trao đổi bước sóng, theo đó một bước sóng có thể đưa đến một sợi với tần số quang khác nhau. Trao đổi bước sóng là tốn kém và có thể làm giảm chất lượng tín hiệu trong chuyển đổi bước sóng hoàn toàn quang, vì vậy nó chỉ được sử dụng khi cần thiết.
Ngoài chuyển mạch bước sóng ra, OXC còn có thể cung cấp chuyển mạch băng sóng và chuyển mạch sợi. Chuyển mạch băng sóng kết nối đồng thời một tập con bước sóng từ sợi đầu vào đến sợi đầu ra. Chuyển mạch sợi chuyển toàn bộ sợi bao gồm tất cả các kênh bước sóng đến sợi đầu ra. Chuyển mạch bước sóng cung cấp chuyển mạch chi tiết hoá tốt hơn chuyển mạch băng sóng và chuyển mạch sợi.
Hình 1.6Bộ kết nối chéo quang OXC
1.3.4 Cấu trúc mạng WDM
1.3.4.1 Cấu trúc mạng WDM điểm – điểm
Hình 1.7 Cấu trúc mạng WDM điểm-điểm
Trong cấu trúc này, mỗi kênh bước sóng được dùng để truyền tải một luồng tìn hiệu riêng biệt. Bộ WDM sẽ có nhiệm vụ tổ hợp các kênh bước sóng này lại thành một chùm bước sóng sau đó đưa vào sợi quang để truyền dẫn. Ở đầu thu, chùm bước sóng sẽ được tách ra bởi bộ tách kênh WDM, sau đó các tín hiệu này sẽ được chuyển quang thành điện qua bộ biến đổi O/E .
Mạng WDM điểm – điểm có ưu điểm là tăng độ rộng băng thông bằng cách ghép nhiều kênh với chi phí thấp, tuy nhiên mạng này có nhược điểm là độ linh hoạt của cấu trúc mạng này không cao do các kết nối chỉ sử dụng một bước sóng cố định.
1.3.4.2 Cấu trúc mạng WDM định tuyến theo bước sóng quang
Hình 1.8 Cấu trúc mạng WDM định tuyến theo bước sóng quang
Trong cấu trúc trên, mỗi node bao gồm các chuyển mạch định tuyến bước sóng WRS và các end-user, các node này liên kết với nhau bởi liên kết sợi quang và tạo thành topo vật lý. Mỗi node đều trang bị các bộ thu phát. Bộ phát tại mỗi node có nhiệm vụ gửi dữ liệu vào mạng, bộ thu sẽ thu dữ liệu từ mạng. Dữ liệu ở các node trung gian sẽ không qua bất kì bộ xử lí quang điện nào.
Trong hình trên lightpath được thiết lập giữa node A với node C trên kênh bước sóng , giữa B với F qua kênh bước sóng , và giữa G với H qua kênh bước sóng .
Ưu điểm của cấu trúc mạng này: có khả năng sử dụng lại bước sóng, tức là các lightpath không truyền qua trên cùng một kết cấu vật lí sẽ sử dụng được cùng bước sóng, ở ví dụ trên thì lightpath thiết lập giữa A –C và H – G có thể sử dụng chung bước sóng . Do việc sử dụng lại bước sóng nên các mạng định tuyến bước sóng có thể khai thác dung lượng của sợi quang bằng cách dùng kĩ thuật WDM. Chi phí quản lí thấp hơn so với cấu trúc mạng điểm – điểm do các thiết bị quang có chi phí bảo dưỡng thấp hơn. Các lightpath có thể thiết lập hoặc hủy bỏ một cách động do đó có thể hỗ trợ sự thay đổi lưu lượng trong mạng.
1.4 Tổng quan về mạng IP/WDM
1.4.1 Chuyển tải IP trên mạng WDM
IP một giao thức lớp 3, được thiết kế nhằm phối hợp hoạt động mức mạng và định tuyến trên các mạng con khác nhau có các công nghệ lớp 2 khác nhau. Phía trên lớp IP, có sự khác nhau rất nhiều của các dịch vụ . Vì vậy, sự vượt trội không tránh khỏi của lưu lượng IP dẫn tới một điều hiển nhiên là các phương tiện kỹ thuật của cơ sở hạ tầng mạng được tối ưu hoá dành cho IP. Dưới lớp IP, sợi quang trong WDM là công nghệ có dây đầy hứa hẹn, đưa ra dung lượng mạng khổng lồ nhằm duy trì sự tăng trưởng liên tục của Internet.
Công nghệ WDM trở nên hấp dẫn hơn vì giá thành của các hệ thống WDM thấp. Với sự triển khai toàn cầu và liên tục về sợi quang và sự chín muồi của WDM, các mạng quang dựa vào WDM đã phát triển không chỉ trên các đường trục, mà còn trong mạng thành phố, mạng vùng và mạng truy nhập.
Động cơ thúc đẩy tiến tới mạng IP/WDM có thể tóm tắt như sau:
- Các mạng quang WDM có thể hướng vào sự tăng trưởng liên tục của lưu lượng Internet bằng cách khai thác cơ sở hạ tầng sợi hiện có. Việc sử dụng công nghệ WDM có thể làm tăng đáng kể việc sử dụng độ rộng băng tần.
- Hầu hết các mạng mà lưu lượng dữ liệu đi ngang qua đều là IP. Hầu như tất cả các ứng dụng dữ liệu người sử dụng đầu cuối đều sử dụng IP. Lưu lượng thoại truyền thống cũng có thể đóng gói nhờ các kỹ thuật VoIP (Voice-over-IP) .
- IP/WDM hy vọng hướng tới WDM hoặc sự phối hợp hoạt động của các nhà cung cấp và phối hợp hoạt động dịch vụ của phần tử mạng (NE) có trợ giúp của các giao thức IP.
- Mạng IP /WDM tích hợp không chỉ giảm chi phí điều hành mạng, mà còn có thể cung cấp việc phân phối động các nguồn tài nguyên và giám sát dịch vụ theo yêu cầu.
- Rút ra các bài học từ tích hợp IP và WDM, IP và WDM cần tích hợp chặt chẽ hơn với mục đích hiệu quả và linh hoạt. Chẳng hạn giải pháp IP/ATM là phức tạp và không hiệu quả vì topo lớp 2(ATM) có thể khác với topo lớp 3(IP), thiết bị lớp 2 khó biết được thông tin định tuyến lớp 3 và sự khác biệt giữa kết nối có hướng và không kết nối.
1.4.2 Giải thích sự ra đời của công nghệ IP trên WDM
Mạng IP/WDM dùng để truyền lưu lượng IP trên mạng quang WDM nhằm gắn kết các kết nối IP thông dụng và dung lượng độ rộng băng tần WDM cực lớn. Hình 1.9 thể hiện truyền các gói IP hoặc các tín hiệu SONET/SDH trên các mạng.
Hình 1.9 Chuyển tải các gói IP trên các bước sóng
Hình 1.10 chỉ rõ ba giải pháp có khả năng đối với IP trên WDM :
Giải pháp thứ 1 là chuyển tải (IP/ATM) / SONET / SDH và cuối cùng là sợi quang WDM. WDM được sử dụng như là công nghệ truyền dẫn song song trong lớp vật lý, ưu điểm cơ bản của giải pháp này khi sử dụng ATM là có khả năng chuyển tải các loại lưu lượng khác nhau trên cùng một ống có yêu cầu QoS khác nhau.Ưu điểm khác khi sử dụng ATM là khả năng kỹ thuật lưu lượng và tính linh hoạt trong cung cấp mạng nhằm bổ sung định tuyến lưu lượng IP thông thường có nỗ lực cao nhất. Tuy nhiên, giải pháp này phức tạp do IP/ATM phức tạp vì topo lớp 2(ATM) có thể khác với topo lớp 3(IP), thiết bị lớp 2 khó biết được thông tin định tuyến lớp 3 và sự khác biệt giữa kết nối có hướng và không kết nối.
Hình 1.10 Ba giải pháp đối với IP trên WDM
Giải pháp thứ 2 là (IP/MPLS) trên SONET/SDH và WDM . SONET/SDH cung cấp một số đặc trưng hấp dẫn cho giải pháp này:
- Thứ nhất, SONET cung cấp phân cấp ghép tín hiệu quang tiêu chuẩn nhờ vậy mà các tín hiệu tốc độ thấp được ghép thành các tín hiệu tốc độ cao.
- Thứ hai, SONET cung cấp khung truyền dẫn tiêu chuẩn.
- Thứ ba, mạng SONET có khả năng bảo vệ / hồi phục hoàn toàn trong suốt từ các lớp trên, chẳng hạn như lớp IP.
Giải pháp thứ 3 cho IP/WDM sử dụng trực tiếp IP/MPLS trên WDM là giải pháp có hiệu quả nhất trong các giải pháp có khả năng. Tuy nhiên, nó đòi hỏi lớp IP phải chú ý đến bảo vệ và hồi phục tuyến.
Việc quản lý mạng theocác phương pháp trêngặpkhôngítkhó khăn.Nguyênnhânchủ yếugâynên sựphứctạptrong quảnlý chínhlàsựphânlớptheotruyềnthốngcủacácgiaothứcmạng.Cácmạngtruyềnthốngcórất nhiềulớpđộclập,dođócónhiềuchứcnăngchồngchéonhauởcáclớpvàthườngxuyêncósự mâu thuẫn lẫn nhau. Vì vậy, một trong những giảipháp để giảmchi phí xây dựng vàquản lý mạngmột cách triệt để đó là giảmsố lớp giao thức.
Hơnnữa,khidunglượngvàkhảnăngkếtnốimạngtrongcảcôngnghệIPvàWDMtăng lênthìcàngcầnthiếttốiưumạngIPvàbỏquatấtcảcáccôngnghệlớptrunggianđểtạonên mạngInternetquangthậtsựhiệuquảvàmềmdẻo.Tuynhiên,cáclớptrunggiancũngcungcấp mộtsốchứcnăngcógiátrịnhưkỹthuậtlưulượng(TrafficEngineering)vàkhôiphục.Những chứcnăngnàycầnphảiđượcgiữlạitrongmạngIP/WDMbằngcáchđưachúnglênlớpIPhoặc xuống lớp quang.
TừđóngườitamớinghĩđếncôngnghệIPoverWDM.Đâylàmộtcôngnghệmớituy rằngcònnhiềuvấnđềchưagiảiquyếtnhưngvớilợiíchcủanó,thịtrườngrộnglớnvàtươnglai sángsủa,cáctổchứcviễnthôngquốctếđangtriểnkhaicôngtácnghiêncứucôngnghệnày.IP overWDMcungcấpkhảnăngtruyềndẫntrựctiếpgóisốliệuIPtrênkênhquang,giảmsựtrùng lặp chức năng giữa các lớp mạng, giảm bộ phận trung tâm dư thừa tại các lớp SDH/SONET, ATM,giảmthaotácthiếtbị,dẫnđếngiảmchiphíbảodưỡngvàquảnlý.Dokhôngphảiqualớp SDHvàATMnêngóisốliệucóhiệusuấttruyềndẫncaonhất,đồngnghĩavớichiphíthấpnhất. NgoàiracòncóthểphốihợpvớiđặctínhlưulượngkhôngđốixứngcủaIP,tậndụngbăngtần nhằmgiảmgiáthànhkhaithác.Từđógiántiếpgiảmchiphíchothuêbao.Rõràngđâylàmộtkết cấumạngtrựctiếpnhất,đơngiảnnhất,kinhtếnhất,rấtthíchhợpsửdụngchocácmạngđường trục.
1.5 Các mô hình mạng IP /WDM
Mô hình tổng quát của mạng IP /WDM được mô tả trong hình sau :
Hình 1.11 Mô hình tổng quát của mạng IP/WDM
Hình trên thể hiện nhiều mạng quang tồn tại trong miền quang. Giao diện ENNI (External Network to Network interface) được sử dụng để báo hiệu giữa các mạng quang với nhau). Một mạng quang riêng lẻ bao gồm các mạng quang nhỏ hơn và báo hiệu giữa chúng sử dụng giao diện INNI ( Internal Network to Network interface). Một mạng quang nhỏ hơn đó gồm nhiều nút mạng quang (các bộ OXC) được nối với nhau bởi sợi quang . Các mạng khách hàng như IP, ATM, SONET giao tiếp với mạng quang thông qua giao diện UNI ( User to Network Interface). Các kĩ thuật chuyển mạch quang quyết định loại hình dịch vụ mà mạng quang có thể cung cấp cho khách hàng.
1.5.1 Mô hình xếp chồng
Hình 1.12 Mô hình xếp chồng
Mô hình xếp chồng cho phép mỗi router giao tiếp với mạng quang thông qua giao diện UNI .Giao tiếp giữa các mạng con được thực hiện thông qua giao diện NNI . Trong mô hình mạng này, mỗi mạng con được tiến triển độc lập, nhờ đó cho phép các nhà khai thác mạng đưa ra các công nghệ mới mà không bị gánh nặng bởi các công nghệ cũ, đáp ứng các cơ sở hạ tầng thừa kế nó. Mô hình xếp chồng có ưu điểm là khả năng tương thích dễ dàng, kiến trúc trực tiếp và đơn giản hơn so với mô hình ngang hàng. Cho phép đổi mới lại lớp quang độc lập với lớp IP trong khi vẫn cung cấp khả năng kết nối tương thích cần thiết cho các dịch vụ nhanh mà vẫn duy trì tính toàn vẹn thông tin của các nhà khai thác mạng quang.
1.5.2 Mô hình ngang hàng
Hình 1.13 Mô hình ngang hàng
Mô hình ngang hàng cũng hỗ trợ cho các thiết bị luồng động bằng cách sử dụng các luồng đầu cuối ở biên mạng quang và cho phép quản lý chúng từ xa. Mô hình ngang hàng giả định rằng các router điều khiển lớp mạng quang. Mối quan hệ giữa IP router và OXC là bình đẳng về mặt điều khiển. Do đó về mặt định tuyến và báo hiệu sẽ không có sự phân biệt nào giữu UNI, NNI, và giao diện giữa các router. Trong mô hình này cần một khối lượng lớn thông tin trạng thái và điều khiển chuyển qua lại giữa lớp IP và quang. Do đó sẽ khó hơn cho việc kết nối hơn trong môi trường nhiều nhà khai thác so với mô hình xếp chồng.
Mô hình ngang hàng cho phép tích hợp hoàn toàn IP/quang tạo nên mạng Internet quang thống nhất. Do đó việc sử dụng và quản lí mạng trở nên hiệu quả hơn và phù hợp với các ISP hơn.
Bảng 1.1 Bảng tóm tắt so sánh giữa 2 mô hình
1.5.3 Mô hình mở rộng
Đây là mô hình mà kết hợp giữa mô hình ngang hàng và mô hình xếp chồng. Mô hình này cho phép trao đổi thông tin định tuyến giữa lớp IP và lớp WDM. Mô hình này chính là sự kết hợp những thuận lợi giữa mô hình xếp chồng và mô hình ngang hàng đồng thời giảm thiểu các bất lợi của chúng.
1.6 Kết luận chương
Chương này trình bày tổng quan về IP , công nghệ WDM cũng như mạng IP/WDM đồng thời cũng trình bày khá chi tiết nguyên lý hoạt động cơ bản cũng như các thành phần và cấu trúc của mạng WDM. Nó đã cho ta thấy ưu khuyết điểm của cấu trúc mạng WDM định tuyến theo bước sóng quang so với cấu trúc mạng WDM điểm - điểm. Như vậy với cấu trúc mạng WDM định tuyến theo bước sóng quang thì có thể khắc phục được hiện tượng nghẽn cổ chai so với cấu trúc mạng WDM điểm - điểm. Trong chương này đã giới thiệu xu hướng và các thách thức hiện nay trong việc tích hợp mạng IP/WDM. Trong các mô hình kể trên thì mô hình xếp chồng là mô hình đơn giản nhất, không cần sự thống nhất về mặt điều khiển, trong khi đó mô hình ngang hàng cần phải thống nhất về mặt điều khiển cũng như cần một lượng lớn thông tin trạng thái và điều khiển chuyển qua lại giữa lớp IP và lớp quang .Vì vậy tiến trình phát triển đầu tiên trong quá trình triển khai mạng IP/WDM sẽ bắt đầu từ mô hình xếp chồng, vì mô hình này chưa có sự trao đổi thông tin định tuyến giữa IP và mạng WDM, do đó tiến trình tiếp theo có lẽ là sử dụng kết hợp với mô hình ngang hàng để có sự trao đổi liên kết giữa IP và WDM. Chương này đã trình bày tương đối đầy đủ ưu nhược điểm của từng loại mô hình từ đó giúp ta có cơ sở để lựa chọn mô hình phù hợp nhất. Và chương này cũng là tiền đề, cơ sở cho việc trình bày các chương tiếp theo.
CHƯƠNG 4
TÁI CẤU HÌNH TOPOLOGIC ỨNG DỤNG GIẢI THUẬT DI TRUYỀN
4.1 Giới thiệu chương
Trong chương 3 đã trình bày về giải pháp thực hiện kỹ thuật lưu lượng bằng cách thiết kế topo logic. Chương 4 này ta sẽ tìm hiểu về giải thuật di truyền (Generic Algorithm-Viết tắt là GA), do John Holland (1975) và Goldberg (1989) đề xuất và phát triển, là giải thuật tìm kiếm dựa trên cơ chế chọn lọc và di truyền tự nhiên. Giải thuật này sử dụng các nguyên lý di truyền về sự thích nghi và sự sống các cá thể thích nghi nhất trong tự nhiên. Kỹ thuật lưu lượng trong mạng IP/WDM có thể đạt được bằng phương pháp thiết lập các lightpath, tái định tuyến cấu hình topo ảo, giản đồ phục hồi và bảo vệ các lightpath ở lớp quang. Phương pháp tái cấu hình topo logic trong mạng IP/WDM bằng cách sử dụng giải thuật GA nhằm tạo ra topologic tối ưu trong điều kiện ràng buộc về số lượng bước sóng và khả năng phần cứng của mạng nhằm mục tiêu là tối thiểu số hop trung bình.
Trong chương này sẽ trình bày nội dung, mục đích, kết quả của việc tái cấu hình topo logic ứng dụng giải thuật di truyền GA.
4.2 Tại sao phải tái cấu hình topo logic
Khi có sự thay đổi phân bố lưu lượng giữa các cặp node nguồn-đích, topo logic vừa được thiết kế sẽ không còn tối ưu nữa. Như vậy để giải quyết vấn đề này ta có các phương pháp sau:
+ Cách thứ 1: Thiết kế lại topo logic dựa trên topo vật lý và ma trận lưu lượng mới mà không cần quan tâm đến topo logic hiện tại để đạt được sự tối ưu nhất. Tuy nhiên phương pháp này sẽ làm cho số lướng lightpath thay đổi là rất lớn nên sẽ gây ra thất thoát lưu lượng là rất lớn.
+ Cách thứ 2: Thiết kế lại topo logic dựa trên topo vật lý và topo logic đã có sẵn trước đó cùng với ma trận lưu lượng mới yêu cầu sao cho topo logic mới không khác nhiều với topo logic trước đó mà vẫn đáp ứng tốt yêu cầu lưu lượng mới.
Quá trình tái cấu hình topo logic là sự cân bằng giữa mục tiêu thực hiện thiết kế topo logic và mục tiêu giảm sự thay đổi trong topo logic.
Vì tái cấu hình không chỉ thực hiện một lần mà có thể thực hiện nhiều lần bất cứ khi nào mà traffic thay đổi. Do đó vấn đề đặt ra là khi nào tái cấu hình và tái cấu hình bằng cách nào.
4.3 Phân tích bài toán tái cấu hình topo logic
Bài toán tái cấu hình topo logic là bài toán đa mục tiêu, vừa thực thi trong mạng vừa kiểm tra sự thay đổi trong topo logic. Hai mục tiêu được sử dụng để tái cấu hình topo logic là: tối thiểu số hop trung bình và tối thiểu số lightpath thay đổi trong topo logic. Hai mục tiêu này có sự xung đột với nhau, nếu thay đổi topo mới so với topo cũ thì giá trị hàm mục tiêu giảm và ngược lại. Do đó cần phải tương hợp hai mục tiêu của bài toán.
Do đó bài toán lúc này thay vì giải với hai mục tiêu thì ta có thể giải với một mục tiêu là tối thiểu số hop trung bình cùng với các ràng buộc.
Ban đầu đặt số lightpath thay đổi là NoChange, ta có số hop trung bình là luồng traffic phải vượt qua khi truyền từ nguồn đến đích :
Trong đó:
tsd là lượng traffic cần truyền từ nguồn s đến đích d
hsd là số hop mà traffic phải vượt qua khi truyền từ nguồn s đến đích d.
Sau đó ta thêm vào một ràng buộc :
Vsd' là số lightpath từ node s đến node d trong topo logic mới
Vsd là số lightpath từ node s đến node d trong topo logic cũ
Trong đề tài này sẽ thực hiện thuật toán di truyền GA (Generic Algorithm) để giải quyết bài toán tái cấu hình topo logic.
4.4 Giới thiệu thuật toán di truyền GA
4.4.1 GA
Giải thuật di truyền GA là kỹ thuật chung giúp giải quyết vấn đề bài toán bằng cách mô phỏng sự tiến hoá của con người hay sinh vật nói chung dựa trên thuyết tiến hoá muôn loài của Darwin trong điều kiện quy định sẵn của môi trường. GA là một giải thuật và mục tiêu của GA không phải đưa ra lời giải chính xác tối ưu mà là đưa ra lời giải tương đối tối ưu.
4.4.2 Các tính chất đặc thù của thuật toán di truyền
- GA lập luận mang tính chất ngẫu nhiên thay vì chính xác như toán học giải tích
- GA duyệt xét toàn bộ các giải pháp sau đó sẽ chọn lấy giải pháp tốt nhất dựa trên hệ số thích nghi
- GA không chú ý đến chi tiết vấn đề mà chỉ chú ý đên giải pháp đặc biệt là dãy số tượng trưng cho giải pháp
- GA rất thích hợp cho việc tìm kiếm giải đáp các vấn đề, hay tìm điều kiện tối ưu cho việc điều hành và phân nhóm những giải pháp có được.
4.4.3 Ưu nhược điểm của thuật toán di truyền GA
Ưu điểm : GA có tính song song, trong không gian tìm kiếm với nhiều cá thể hơn, vì vậy thuật toán này ít khi bị rơi vào các lời giải tối ưu cục bộ như những phương pháp khác. Thuật toán di truyền cũng dễ thực hiện, chúng ta chỉ phải biểu diễn nhiễm sắc thể (NST) mới để giải quyết các bài toán khác nhau và nếu bài toán nào đó có phương pháp mã hóa NST thì chúng ta chỉ cần viết lại hàm số tính độ thích nghi cho bài toán đó mà thôi.
Nhược điểm : Khuyết điểm của thuật giải di truyền là ở thời gian tính toán của nó, có thể là chậm hơn so với các phương pháp khác.
4.4.4 Các khái niệm của thuật toán GA
4.4.4.1 Cá thể
Cá thể hay còn gọi là nhiễm sắc thể (NST) được xem là giải pháp của bài toán, ở đó NST được xem là các chuỗi bit 0 hoặc 1. Một tập hợp nhiều NST sẽ tạo nên 1 quần thể, các quần thể chính là các lời giải cho bài toán. Quá trình tiến hoá đối với các NST chính là quá trình tìm kiếm để tiếp cận với lời giải tối ưu cho bài toán.
4.4.4.2 Chọn lọc
Chọn lọc chính là quá trình lựa chọn ra những cá thể có độ thích nghi cao hay những cá thể tốt để xây dựng quần thể tiếp theo còn gọi là thế hệ kế tiếp.
4.4.4.3 Lai ghép
Là cách kết hợp các đặc tính trên NST của bố và mẹ để tạo thành 2 cá thể mới bằng cách tráo đổi các đoạn gen.
|
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
Ví dụ : Cha
|
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
Mẹ
Sự trao đổi chéo giữa các gen giữa cha và mẹ tạo thành hai con :
|
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
Con 1 :
|
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
Con 2 :
4.4.4.4 Đột biến
Là sự sửa đổi một vài gen của một NST được chọn bằng cách thay đổi ngẫu nhiên với xác suất là tỷ lệ đột biến.
|
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
BT
|
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
ĐB
NST BT được chọn làm đột biến ở vị trí gen thứ 5, gen này hiện tại là 0, sau khi đột biến sẽ trở thành 1, khi đó NST BT sẽ trở thành ĐB.
4.4.5 Các thông số của thuật toán GA
Kích thước quần thể : là số lượng NST trong quần thể (tính trong 1 thế hệ). Kích thước quần thể có giá trị từ vài chục đến vài trăm, và không đổi qua từng thế hệ.
Xác suất lai ghép Pc : Lai ghép thực hiện với một xác suất nhỏ hơn 1, xác suất lai ghép biểu diễn mức độ xảy ra thường xuyên để thực hiện việc lai ghép. Nếu xác suất lai ghép là 1 thì toàn bộ các cá thể con được tạo ra bằng phép lai ghép.
Xác suất đột biến Pm : Đột biến chỉ được thực hiện với một xác suất rất thấp (thường nhỏ hơn 0,1). Xác suất đột biến biểu diễn mức độ xảy ra thường xuyên của NST bị đột biến tại gen đó.
4.4.6 Sơ đồ thuật toán di truyền GA
4.5 Ứng dụng thuật toán di truyền GA vào tái cấu hình topo logic
4.5.1 Quan hệ giữa mạng và thuật toán di truyền
|
GA |
Mạng |
|
- Một cá thể - Quần thể - Nhiễm sắc thể
- Gen trong nhiễm sắc thể
- Vị trí của gen trong nhiễm sắc thể - Nội dung của gen |
- Một topo cụ thể - Tập hợp nhiều topo - Chuỗi nhị phân diễn tả các kết nối tạo nên topo - Bit trong chuỗi nhị phân thể hiện đường nối trong mạng - Vị trí đường nối trong mạng
- Số lượng đường nối
|
4.5.2 Mã hoá
Dạng topo của một mạng N node có thể được biểu diễn bởi một ma trận kết nối NxN, trong đó Xij sẽ là số đường kết nối từ node i đến node j.
Xij =
Trên thực tế không có đường kết nối từ nó đến chính nó nên ma trận kết nối :
Xij =
Hình 4.1 Topo logic mạng 5 node ứng với ma trận kết nối X5x5
Ma trận kết nối : X5x5 =
4.5.3 Hàm thích nghi
Hàm thích nghi là hàm dùng để đánh giá xem là một cá thể có tốt hay không. Một cá thể tốt thì độ thích nghi của nó càng cao và tiến đến sẽ là lời giải đúng của bài toán. Do đó việc đánh giá hàm thích nghi là rất quan trọng, nếu đánh giá sai chúng ta có thể loại mất một cá thể tốt trogn quần thể.
Công thức hàm thích nghi :
Trong đó :
- A là một số dương quyết định biên độ của F
- Havg là giá trị hop trung bình của mạng
- Khi Havg = Havgmax = N-1 thì F = Fmin = 1
- Khi Havg = Havgmin = 1 thì F = Fmax = A+1
Bài toán tái cấu hình là bài toán tối ưu có ràng buộc nên trong quá trình chọn lọc thì dựa vào hàm thích nghi ta sẽ loại ra những cá thể không phù hợp do không thoả mãn được điều kiện ràng buộc. Để loại những cá thể không phù hợp này ta sẽ dùng phương pháp gọi là hàm phạt. Đây là phương pháp để chuyển bài toán tối ưu có ràng buộc sang bài toán tối ưu không ràng buộc có thêm hệ số phạt vào hàm thích nghi đối với những trường hợp vi phạm điều kiện ràng buộc.
Ta có công thức : fp(x) = f(x).P(x)
Với P(x) thoả mãn điều kiện :
P(x) = 1 nếu x thoả mãn điều kiện ràng buộc
0 < P(x) < 1 nếu x không thoả mãn điều kiện ràng buộc
4.5.4 Điều kiện kết thúc điều kiện dừng
Để kết thúc vòng lặp GA, thường thì sẽ cho trước số thế hệ cần tạo sau đó sẽ kiểm tra hàm thích nghi với những phần tử tốt nhất bằng cách so sánh với bài toán ban đầu.
Các điều kiện GA tuân theo những tiêu chuẩn sau :
- Theo số thế hệ định trước
- Thời gian chạy định trước
- Sau một khoảng thế hệ mà qua đó hàm thích nghi không được cải thiện
- Sau một khoảng thời gian mà qua đó hàm thích nghi không được cải thiện
- Một giá trị thích nghi định trước
4.5.5 Áp dụng thuật toán GA vào bà toán tái cấu hình topo logic cụ thể
4.5.5.1 Khởi tạo quần thể
Khởi tạo quần thể ban đầu một cách ngẫu nhiên, bài toán là áp dụng cho n node nên quần thể sẽ được tạo ra một cách ngẫu nhiên n node với kích thước quần thể cho trước.
4.5.5.2 Kiểm tra điều kiện dừng
Sau khi khởi tạo quần thể, tính giá trị hop trung bình và kiểm tra điều kiện ràng buộc.
Giá trị hop trung bình được tính theo công thức:
Trong đề tài này chọn điều kiện dừng là theo số thế hệ định trước.
4.5.5.3 Chọn lọc
Mỗi cá thể được chọn lọc dựa vào giá trị thích nghi của nó, nếu giá trị thích nghi càng cao thì xác suất chọn lọc càng lớn.
Giá trị thích nghi của mỗi cá thể được tính theo công thức:
Chọn lọc theo bánh xe Routtle với các rãnh được định kích thước theo độ thích nghi.
Quá trình xây dựng bánh xe Roultte được tiến hành như sau:
+ Tính độ thích nghi eval(Ni) của mỗi NST Ni(i= 1…pop_size)
+ Tìm tổng giá trị thích nghi của toàn quần thể :
+ Tính xác suất chọn lọc Pi cho mỗi NST Ni : Pi = eval(Ni)/Tong
+ Tính vị trí xác suất qi cho mỗi NST Ni :
Tiến trình chọn lọc bằng cách quay bánh xe Roultte pop_size lần, mỗi lần sẽ chọn một NST theo cách sau:
- Phát sinh ngẫu nhiên một số r trong khoảng [0…1]
- Nếu r < q1 thì chọn NST đầu tiên (N1); ngược lại thì chọn NST thứ i(Ni) sao cho qi-1
4.5.5.4 Lai tạo
Lai tạo đơn điểm với xác suất lại tạo là pc
- Tạo ngẫu nhiên số r trong khoảng [0…1]
- Nếu r
- Nếu số NST được chọn là lẻ cộng thêm 1 NST nữa rồi tiến hành lai tạo
- Chọn cặp NST làm cha mẹ, cắt ngẫu nhiên vị trí lai tạo
- Tiến hành lai tạo
Lai tạo 2 điểm: Giống như quá trình lai tạo đơn điểm nhưng phải cắt ngẫu nhiên 2 vị trí lai tạo.
Trong đề tài này chọn pc = 0,6.
4.5.5.5 Đột biến
Đột biến đảo bit : với xác suất đột biến pm
Mỗi bit trên 1 NST của tập lời giải :
+ Sinh một số ngẫu nhiên
+ Nếu r < pm ta đảo bit đó (đổi 0 thành 1 và ngược lại)
Trong đề tài này chọn pm = 0,05.
4.6 Ứng dụng MATLAB mô phỏng thuật toán di truyền GA để tái cấu hình
topologic
4.6.1 Giao diện chương trình mô phỏng
Hình 4.2 Giao diện chương trình mô phỏng thuật toán GA
4.6.2 Hướng dẫn sử dụng chương trình
+ Chọn topo vật lý, mẫu traffic phù hợp với topo
+ Nhập số bước song/link, số bộ thu/node, số bộ phát/node sau đó nhấn HLDA để lấy topo logic ứng với lưu lượng ma trận đã chọn.
+ Thay đổi ma trận lưu lượng
+ Chọn số lightpath thay đổi, số bộ thu phát/node, số hop lớn nhất, số cá thể trong quần thể, số thế hệ.
+ Sau khi chọn đầy đủ thì nhấn vào GA để thực hiện tái cấu hình topo logic.
4.6.3 Kết quả mô phỏng và nhận xét
- Bài toán thiết kế topo logic (Logical Topo Design)
Mô phỏng với mạng Ring 7 node :
- Với ma trận lưu lượng X7node =
- Thực hiện thiết kế topo logic dùng thuật toán HLDA với các thông số đầu vào :
+ Số bước sóng/link : 5
+ Số bộ thu/node : 4
+ Số bộ phát/node : 4
Khi thực hiện thiết kế thì
Topo logic sẽ là T1 =
Hình 4.3 Topo logic mạng 7 node ứng với ma trận lưu lượng X7node
Số hop trung bình sẽ là H1 = 1.1964
- Thực hiện thiết kế với thuật toán GA với các thông số :
+ Số lightpath thay đổi : NoChange
+ Số bộ phát thu/ node : 4
+ Số hop lớn nhất : 4
+ Số cá thể trong quần thể : 50
+ Số thế hệ : 150
Khi chạy thuật toán GA thì ta sẽ được topo logic mới T2 =
Số hop trung bình sau khi chạy thuật toán GA sẽ giảm xuống còn H2 = 1.1412
Nhận xét : Như vậy khi chạy thuật toán GA thì số hop trung bình sẽ giảm nhiều so với thuật toán HLDA.
- Bài toán tái cấu hình topo logic :
- Giả sử ma trận lưu lượng thay đổi X’7node =
Nếu chạy luồng lưu lượng này trên topo logic cũ thì số hop trung bình sẽ là H1’=1.346. Giá trị này khá lớn trong khi bài toán đưa ra nhằm mục đích tối thiểu số hop trung bình nhằm giảm tải đi qua lighpath đồng thời giảm việc xử lý traffic trên mỗi node định tuyến. Nên nhất thiết phải tìm phương pháp để làm giảm số hop trung bình.
Nếu ta dùng phương pháp New-Design, tức là thiết kế lại từ đầu sao cho topo logic hợp với luồng lưu lượng thay đổi khi đó ta sẽ có :
+ Topo logic mới ứng với luồng lưu lượng thay đổi khi chạy thuật toán HLDA :
T3 =
Hình 4.4 Topo logic mạng 7 node ứng với ma trận lưu lượng X’7node
Màu đỏ chỉ số lighpath mới được thiết lập. Có 6 lighpath mới đước thiết lập và 6 lighpath bị hủy bỏ, tổng cộng có 12 lighpath thay đổi.
Số hop trung bình H1’’ = 1.1814
+ Khi chạy thuật toán GA cho việc tái cấu hình thì ta có topo logic mới được tạo ra khi chạy thuật toán GA là :
T4 =
Số hop trung bình là : H2’ = 1.2424
Dựa vào T4 ta thấy có 3 lighpath mới được thiết lập và 1 lighpath bị hủy bỏ. Tổng cộng có 4 lighpath thay đổi.
Hình 4.5 Kết quả mô phỏng thuật toán GA khi lưu lượng thay đổi
Hình 4.6 Giá trị hop trung bình phân bố khi số lighpath thay đổi
Hình 4.7 Biểu diễn giá trị hop trung bình theo số thế hệ
Nhận xét: So sánh giá trị hop trung bình nhận thấy rằng phương pháp New-Design có giá trị nhỏ hơn nhiều (H1’’ = 1.1814) so với giá trị tối ưu (H1’ = 1.346) ở bài toán New-Design. Tuy nhiên nếu so sánh số lightpath thay đổi ở hình 4.3 và hình 4.4 ta thấy có 6 lightpath bị xóa và 6 lightpath được cộng vào, tổng số lightpath thay đổi khi chuyển từ trạng thái hiện hành (hình 4.2) đến trạng thái mới (hình 4.3) là rất lớn (NoChange =12) phải mất nhiều thời gian chuyển đổi và có thể làm thất thoát một lượng lớn traffic. Do đó bài toán đặt ra tìm topo mới sao cho số lightpath thay đổi ít hơn so với phương pháp New-Design trong khi giá trị hop trung bình có thể chấp nhận được.
Chính vì vậy, khi ta chạy thuật toán GA thấy số hop trung bình H2’ = 1.2424 trong topo logic mới được thiết kế lại là nhỏ hơn rất nhiều so với số hop trung bình H1’ = 1.346, tuy H2’ = 1.2424> H1’’ = 1.1814 nhưng đây là giá trị chấp nhận được. Lúc này sẽ có 1 số lượng nhỏ số lightpath bị huỷ bỏ cũng như được thiết lập (3 thiết lập và 1 hủy bỏ = 4lighpath<12lighpath). Điều này làm nổi bật lên ưu điểm của bài toán tái cấu hình topo logic dùng thuật toán GA.
Giữ nguyên topo logic của ma trận lưu lượng X’7node, chạy thuật toán GA với số lightpath thay đổi.
- Chạy lần thứ 1 với số lightpath thay đổi là 8 ta được kết quả :
+ Topo logic mới T1,8 =
+ Số hop trung bình : H1,8 = 1.1997
- Chạy lần thứ 2 với số lightpath thay đổi là 10 ta được kết quả :
+ Topo logic mới T2,10 =
+ Số hop trung bình : H2,10 = 1.1829
- Chạy lần thứ 3 với số lightpath thay đổi là 12 ta được kết quả :
Hình 4.8 Kết quả mô phỏng ứng với số lightpath thay đổi là 12
Hình 4.9 Biểu diễn giá trị hop trung bình khi số lightpath thay đổi từ 0->12
Hình 4.10 Biểu diễn số hop trung bình theo số thế hệ ứng với lightpath thay đổi là 12
+ Topo logic mới T3,12 =
+ Số hop trung bình : H3,12 = 1.1585
Kết luận : Qua 3 lần chạy chương trình ứng với số lightpath thay đổi khác nhau thì ta thấy số lượng lightpath thay đổi khi chuyển topo logic càng lớn thì số hop trung bình càng nhỏ. Theo kết quả chạy chương trình thì khi số lượng lightpath thay đổi là 12 = phương pháp New Design thì ta thấy số hop trung bình sẽ là H3,12 = 1.1585 nhỏ hơn rất nhiều so với H2’ = 1.2424. Đây là ưu điển của bài toán di truyền GA.
|
Traffic |
X7node |
X’7node |
||
|
Phương pháp |
LTD |
|
New-Design |
Reconfiguration |
|
Topo logic |
T1 |
T1 |
T3 |
T3,12 |
|
Giá trị hop trung bình |
H1=1.1964 |
H1’=1.346 |
H1’’=1.1814 |
H3,12 = 1.1585 |
|
Số lighpath thay đổi so với X7node |
|
|
12 |
12 |
Bảng 4.1 So sánh các phương pháp kiểm soát sự thay đổi traffic trong mạng 7 node
4.7 Kết luận chương
Chương này đã trình bày một số kết quả mô phỏng bài toán thiết kế topo logic cũng như tái cấu hình topo logic. Ứng với các topo vật lý, khi thay đổi các giá trị của bộ thu phát, số bước sóng, ma trận lưu lượng thì sẽ cho ta topo logic tương ứng. Mặt khác chương này cũng đã trình bày kết quả cụ thể khi sử dụng thuật toán GA trong việc tái cấu hình topo logic. Ứng với mỗi topo logic, các mẫu ma trận lưu lượng khác nhau thì nếu số lightpath thay đổi khác nhau sẽ cho ta kết quả khác nhau. Nếu ta tăng số cá thể trong quần thể cũng như tăng số thế hệ lên thì kết quả sẽ tối ưu hơn, tuy nhiên thời gian chạy chương trình thực hiện sẽ lâu hơn. Thuật toán GA là một thuật toán tìm kiếm ngẫu nhiên để tìm ra lời giải tương đối tối ưu nên các kết quả đạt được có thể khác nhau ứng với các lần chạy chương trình khác nhau. Từ kết quả thu được, ta so sánh số hop trung bình và số lightpath thay đổi sẽ cho ta sẽ thấy được sự tối ưu khi sử dụng thuật toán GA so với các thuật toán thiết kế khác như HLDA.
TÀI LIỆU THAM KHẢO
[1] Vũ Tuấn Lâm, Vũ Hoàng Sơn, “Xu hướng tích hợp IP/Quang trong mạng
NGN”, Tạp chí bưu chính viễn thông, 2003.
[2] Kevin H. Liu, “IP over WDM”, QOptics Inc, Oregon, USA, 2002.
[3] R. Ramaswami and K. N. Sivarajan, “Design of logical topologies for
wavelength-routed optical networks,” IEEE Journal on Selected Areas in
Communications, vol. 14, pp. 840–851, June 1996.
[4] Der-Rong Din, “A Generic Algorithm for Solving Virtual Topology
Configuaration Transition Problem in WDM Networks”, 2006.
PHỤ LỤC
Mã nguồn thuật toán GA
function [Ha_old,Ha_new,T_New] = ttGA(T,n,pop_size,TR,Hm,NoC_lp,Lo,Gnums)
M=[Lo(2,1,:)];
K=[Lo(1,2:n,:)];
for j=2:n-1;
t=j+1:n;
K=[K Lo(j,t,:)];
M=[M Lo(j+1,1:j,:)];
end
%M=[L(2,1,:)];
To=[K M] ;
A=round(rand(n,n,pop_size));
for i=1:n
A(i,i,:)=0;
end
L=A;
L(:,:,pop_size)=Lo;
%N=[L(1,2:5,:) L(2,3:5,:) L(3,4:5,:) L(4,5,:) L(2,1,:) L(3,1:2,:) L(4,1:3,:) L(5,1:4,:)];
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% so the he dinh truoc
Havgcount=rand(1,Gnums); % random number of generation
Number_change=[];
Hop=[];
Topo=rand(n,n,Gnums);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
for G=1:Gnums;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%chuyen tu topo sang nhiem sac the
K=[L(1,2:n,:)];
M=[L(2,1,:)];
for j=2:n-1;
t=j+1:n;
K=[K L(j,t,:)];
M=[M L(j+1,1:j,:)];
end
N=[K M];
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% tinh hop logic
H=L;
% thuat toan Ford
for i= 1:pop_size ;
% so to po random
for s=1:n;
for d=1:n;
if L(s,d,i)==1 &s~=d ;H(s,d,i)=1;
end
if L(s,d,i)==0 &s~=d ;H(s,d,i)=20;
end
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
for w= 1:n;
for s=1:n;
if (s~=w);
for d=1:n;
if ( w~=s & w~=d & s~=d );
t=H(s,w,i)+H(w,d,i);
H(s,d,i)=min(H(s,d,i),t);
end
end
end
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ham muc tieu
format long;
for i=1:pop_size ;
t2=0;
for s=1:n ;
t1=0;
for d=1:n ;
k=T(s,d).*H(s,d,i) ;
t1=t1+k ;
end
t2=t2+t1 ;
end
Ha(1,:,i)=t2;
end
n2=0 ;
for s=1:n ;
k=0;
for d=1:n ;
n1=T(s,d) ;
k=k+n1 ;
end
