Tóm tắt luận án tiến sĩ kỹ thuật: Giải pháp nâng cao hiệu quả sử dụng tài nguyên trong mạng quang WDM cấu hình Ring

Chia sẻ: Trần Thị Bích | Ngày: | Loại File: PDF | Số trang:14

Thêm vào BST

Báo xấu

59
lượt xem 8
download

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

Phạm vi ứng dụng của WDM ngày càng mở rộng và đang được triển khai rộng rãi từ cấp mạng đường trục đến nội hạt. Những mạng WDM với những kiến trúc và cấu hình khác vẫn đang được nghiên cứu và áp dụng. Mời các bạn tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt luận án tiến sĩ kỹ thuật: Giải pháp nâng cao hiệu quả sử dụng tài nguyên trong mạng quang WDM cấu hình Ring

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Luận án được hoàn thành tại: ********************* HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: 1. PGS. TS. Bùi Trung Hiếu 2. TS. Hoàng Ứng Huyền Vũ Hoàng Sơn Phản biện 1: GS.TSKH. Đào Khắc An GIẢI PHÁP NÂNG CAO HIỆU QUẢ SỬ DỤNG Phản biện 2: TÀI NGUYÊN TRONG MẠNG QUANG WDM PGS.TS. Phùng Quốc Bảo CẤU HÌNH RING Phản biện 3: TS. Bùi Việt Khôi Chuyên ngành: Kỹ thuật viễn thông Mã số: 62.52.70.05 Luận án được bảo vệ tại Học viện Công nghệ Bưu chính Viễn thông vào lúc 14 giờ 00 , ngày 06 tháng 01 năm 2012 . TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT Có thể tìm hiểu luận án tại: - Thư viện Quốc gia, - Thư viện Học viện Công nghệ Bưu chính Viễn thông. Hà nội – 2012
1 2 MỞ ĐẦU tổng chi phí hay tối thiểu tài nguyên cần sử dụng. Các giải pháp được đề xuất Trong những năm gần đây, với sự bùng nổ của dịch vụ trên nền giao thức cho kết quả chính xác dựa trên quy hoạch tuyến tính nguyên (ILP) và cho kết Internet (IP) và với sự phát triển nhảy bậc về công nghệ quang nói chung và quả gần đúng theo phương pháp Heuristic sẽ được sử dụng để phân tích, mô công nghệ ghép kênh theo bước sóng (WDM) nói riêng đã cho phép cũng như phỏng đánh giá kiểm chứng hiệu quả sử dụng tài nguyên theo cách tiếp cận thúc đẩy phát triển mạng quang thế hệ sau theo hướng tích hợp IP/quang với này. dung lượng lớn, cự ly xa và đặc biệt có khả năng điều khiển mềm dẻo để cung Ý nghĩa khoa học và thực tiễn của đề tài cấp các dịch vụ băng tần theo nhu cầu hay tổ chức thành các mạng riêng ảo. Các kết quả nghiên cứu đạt được trong luận án cho thấy phương pháp thiết Phạm vi ứng dụng của WDM ngày càng mở rộng và đang được triển khai kế và giải pháp tối ưu theo ILP và heuristic được đề xuất đem lại hiệu quả sử rộng rãi từ cấp mạng đường trục đến nội hạt. Những mạng WDM với những dụng tài nguyên mạng rất cao (trên 20%) so với các kết quả nghiên cứu trước kiến trúc và cấu hình khác vẫn đang được nghiên cứu và áp dụng, mà nhiều đây theo cách tuần tự truyền thống. Các kết quả này có thể áp dụng cho quá nhất là các mạng WDM cấu hình Ring nhờ tính đơn giản, tốc độ khôi phục trình thiết kế mạng Ring quang trong môi trường mạng đô thị. nhanh và hiệu quả về kinh tế, nhất là trong môi trường mạng đô thị (MAN) do Hướng nghiên cứu này cũng có thể được phát triển cho các cấu hình khác tận dụng được cơ sở hạ tầng hiện có. Vì lý do đó các kiến trúc Ring vẫn được và cũng phù hợp với xu hướng giải quyết các vấn đề tích hợp đa lớp mạng phát triển cho các công nghệ mạng quang tiên tiến sau này. trong mạng quang thế hệ sau theo IP/quang. Tính cấp thiết của đề tài Một trong những vấn đề quan trọng trong quản lý và sử dụng tài nguyên Hiện nay trên thế giới, song song với các nghiên cứu về vật lý để khai thác mạng quang được nghiên cứu trong luận án đó là việc phân luồng lưu lượng băng thông cực lớn của sợi quang, các nghiên cứu về mạng quang nói chung và thiết kế topology, đây là công việc rất có ý nghĩa không chỉ trong quá trình và các nghiên cứu về điều khiển, quản lý tài nguyên mạng nói riêng được chú xây dựng và khai thác mạng mà còn trong nghiên cứu phát triển. ý rất mạnh mẽ theo hướng đáp ứng yêu cầu dịch vụ và phù hợp với sự phát Trong nghiên cứu, việc sử dụng các mô hình, công cụ toán học và mô triển của công nghệ cũng như các điều kiện triển khai thực tế. Hướng nghiên phỏng tiên tiến để phân tích, đánh giá về khả năng điều khiển, quản lý tài cứu này mở ra rất nhiều vấn đề mới có ý nghĩa khoa học và thực tiễn lớn, điển nguyên mạng quang cũng góp phần tạo ra sự giao thoa kết hợp giữa các hình là các vấn đề về thiết kế và tối ưu sử dụng tài nguyên trong quá trình phát môn/phương pháp nghiên cứu khoa học cơ bản và nghiên cứu ứng dụng trong triển mạng lưới. Các nghiên cứu này cũng có ảnh hưởng lớn đến sự phát triển viễn thông nói chung và thông tin quang nói riêng. của lĩnh vực công nghệ quang mới và cũng nhanh chóng tạo ra các dịch vụ Nội dung của luận án được tổ chức thành 4 chương chính, bao gồm: mới cho khách hàng. Vì vậy, nghiên cứu sinh đã chọn hướng nghiên cứu theo Chương 1 giới thiệu tổng quan về mạng quang và vấn đề tối ưu tài nguyên cách tìm kiếm và đề xuất giải pháp nâng cao hiệu quả sử dụng tài nguyên trong mạng quang cấu hình Ring. Trong chương này đưa ra xu hướng phát mạng để có thể áp dụng trong quá trình thiết kế và khai thác mạng quang triển mạng truyền tải quang và xác định hướng nghiên cứu của luận án về tối WDM cấu hình Ring, phù hợp với môi trường áp dụng thực tế và khả năng ưu tài nguyên trong mạng quang cấu hình Ring trên cơ sở khảo cứu các kết phát triển các dịch vụ mới trong tương lai. quả nghiên cứu liên quan đã được công bố. Mục đích nghiên cứu của luận án là nhằm xác định được ảnh hưởng Chương 2 tập trung xây dựng bài toán tối ưu topology và định tuyến trong đồng thời của các yếu tố về lưu lượng, topology và định tuyến đến kết quả mạng quang WDM cấu hình Ring trên cơ sở tổng hợp những phương pháp thiết kế tối ưu mạng. Trên có sở đó xây dựng được phương pháp thiết kế và đề thiết kế và phân bổ tài nguyên truyền thống trong mạng quang nói chung và xuất các giải pháp tối ưu để nâng cao hiệu quả sử dụng tài nguyên mạng. mạng cấu hình Ring nói riêng, và qua đó thấy rõ hơn tính hiệu quả về phân bổ Đối tượng và phạm vi nghiên cứu trong luận án là phương pháp thiết kế và quản lý tài nguyên của cấu trúc mạng đang nghiên cứu. mạng quang WDM cấu hình Ring hai hướng có khả năng áp dụng trong môi Chương 3 đề xuất giải pháp nâng cao hiệu quả sử dụng tài nguyên trong trường mạng MAN hay Ring ảo. mạng quang WDM cấu hình Ring theo hướng tối ưu đồng thời topology và Cho đến nay, các nghiên cứu về vấn đề thiết kế tối ưu mạng quang WDM định tuyến sử dụng phương pháp qui hoạch nguyên (ILP) và Heuristic. cấu hình Ring thường được thực hiện tuần tự theo cách tối ưu topology rồi Chương 4 mô tả kết quả mô phỏng giải bài toán tối ưu topology và định định tuyến và có các mục tiêu khác nhau; các kết quả đạt được nói chung chỉ tuyến để đánh giá hiệu quả của các giải pháp được đề xuất ở chương 3. là tối ưu cục bộ. Phần kết luận trình bày các kết quả đã đạt được, các đóng góp mới của luận Cách tiếp cận của luận án được chọn cho vấn đề tối ưu này là theo hướng án và khuyến nghị một số vấn đề, hướng nghiên cứu mới. tối ưu đồng thời topology với định tuyến cân bằng tải theo hàm đa mục tiêu
3 4 CHƯƠNG 1. TỔNG QUAN VỀ MẠNG QUANG VÀ 1.1.2 Kiến trúc và công nghệ mạng quang cấu hình Ring VẤN ĐỀ TỐI ƯU TÀI NGUYÊN TRONG MẠNG CẤU HÌNH RING Mạng quang truyền tải dung lượng lớn và yêu cầu về chất lượng dịch vụ 1.1. TỔNG QUAN VỀ PHÁT TRIỂN MẠNG TRUYỀN TẢI QUANG ngày càng cao và đa dạng, do đó mạng cần có khả năng cung cấp cơ chế bảo vệ hay hồi phục nhanh, tin cậy để duy trì được dịch vụ ngay cả khi có các sự 1.1.1 Sự phát triển của cấu trúc và công nghệ mạng truyền tải quang cố. Kiến trúc mạng quang cấu hình Ring chia thành hai loại chính tương ứng Mạng truyền tải quang thế hệ sau hiện đang được phát triển theo hướng cơ chế sử dụng tài nguyên/ băng thông trong bảo vệ: cơ chế bảo vệ riêng tích hợp công nghệ mạng IP và công nghệ mạng quang. Hình 1-1 cho thấy (DPRing) hay bảo vệ chia sẻ (SPRing) tài nguyên. Trong DPRing mỗi bước mạng truyền tải quang đa lớp đang dần được tổ chức tối ưu hơn, giảm thiểu sóng làm việc trên Ring có một bước sóng bảo vệ riêng còn ở SPRing dung các thiết bị, các lớp mạng và các giao thức trung gian để tiến tới tích hợp lượng bảo vệ được chia sẻ cho một vài đường làm việc. Cơ chế bảo vệ chia sẻ mạng theo hướng IP/quang trên nền kỹ thuật WDM. Xu hướng chung có thể phức tạp hơn trong thực hiện và quản lí song nó lại tiết kiệm được tài nguyên thấy mạng IP/quang ngày càng trở nên thông minh hơn, đáp ứng động hơn hơn so với cơ chế bảo vệ riêng. Cơ chế này cho phép sử dụng lại các bước theo nhu cầu như từ thiết lập kênh tĩnh đến điều khiển động, chuyển mạch sóng hay khe thời gian trên các chặng khác nhau của Ring, do vậy thuộc tính kênh (OCS) hay đến chuyển mạch chùm/gói quang (OBS/OPS) và ngày càng này được gọi là cấu trúc mạng có khả năng tái sử dụng không gian. được phát triển từ cấu trúc đơn giản như điểm-điểm, đến Ring, Ring lai Mesh Kiến trúc Ring hai hướng hay SPRing có khả năng tái sử dụng không gian và tiến tới cấu trúc Mesh. Với khả năng tích hợp và điều khiển động, mạng cho phép sử dụng hiệu quả băng thông hơn so với DPRing nhất là trong môi quang WDM có thể cung cấp các luồng dịch vụ băng tần lớn theo nhu cầu hay trường mạng lõi vùng đô thị. Tuy nhiên, tính hiệu quả này còn phụ thuộc vào các dịch vụ tiên tiến như mạng riêng ảo. Tuy nhiên, việc phát triển tới kiến mẫu lưu lượng, phương pháp thiết kế mạng và thuật toán định tuyến. trúc mạng động và Mesh hoàn toàn còn có nhiều thách thức về mặt công nghệ Do SPRing có nhiều ưu điểm trên, nên kiến trúc này vẫn được phát triển và cũng như triển khai thực tế. nghiên cứu ứng dụng cho các công nghệ truyền tải quang khác như: Ring gói tự hồi phục (RPR) theo chuẩn IEEE 802.17; Ethernet Ring (ERPS); T-MPLS Ring; OBS/OPS Ring. 1.2. PHÂN BỔ, SỬ DỤNG TÀI NGUYÊN MẠNG QUANG CẤU HÌNH RING Trong luận án này sử dụng thuật ngữ lưu lượng được hiểu như sau: Lưu lượng (traffic hay demand volume) trong mạng truyền tải là lượng nhu cầu kết nối được xác định từ các dịch vụ lớp trên cần truyền tải và được đặc trưng bởi: các nút kết cuối, độ rộng băng (đơn vị dung lượng), kích cỡ và các tham số liên quan đến chất lượng. Trong mạng truyền tải quang, các kết nối có lưu lượng lớn và thường có giá trị nguyên. Đối với WDM, đơn vị lưu lượng là bước sóng. Trong mạng dịch vụ như mạng điện thoại, lưu lượng có bản chất thống kê và thường được đo bằng đơn vị Erlang. Tập hợp các lưu lượng giữa Hình 1-1: Xu hướng phát triển mạng quang theo hướng IP/quang. các nút mạng cần xét thường được biểu diễn bằng một ma trận lưu lượng. Phạm vi ứng dụng của công nghệ WDM ngày càng mở rộng, từ mạng 1.2.1 Vị trí của phân bổ, sử dụng tài nguyên trong quản lý mạng đường trục đến nay đã xâm nhập vào vùng mạng MAN để đáp ứng nhu cầu Tài nguyên mạng quang nói chung có thể ở nhiều dạng khác nhau, phụ phát triển của các mạng truy nhập băng rộng (xDSL, Wimax, XG-PON,…). thuộc vào công nghệ và phạm vi nghiên cứu như: dung lượng hệ thống, băng Trên thế giới cũng như ở Việt Nam, mạng quang hiện được triển khai phổ thông, sợi và các thiết bị, thành phần. Việc phân bổ, sử dụng tài nguyên hữu biến với cấu hình Ring. Dưới sức ép của cạnh tranh, các nhà khai thác mạng hạn của mạng cần đảm bảo hiệu quả, đúng thời điểm, thỏa mãn lưu lượng và không muốn đầu tư quá nhiều vào hạ tầng mạng và đồng thời cũng yêu cầu giảm chi phí. Hoạt động của quản lý, sử dụng tài nguyên mạng truyền tải có khi nâng cấp, phát triển mạng cần duy trì tính liên tục của cấu trúc mạng. Vì mặt trong các giai đoạn phát triển, quản lý mạng và thường được chia ra 3 vậy, các công nghệ quang mới phát triển cần kế thừa ưu điểm các công nghệ mức độ cơ bản theo thời gian: đang dùng và tận dụng cơ sở hạ tầng hiện có.
5 6 • Mức 1: Quản lý và xử lý luồng lưu lượng, tài nguyên ở thời gian thực hay Các thuật toán tìm kiếm metaheuristic; 4) Phân tích đồ thị Graph; 5) Phương gần thực, hay nhờ chức năng hồi phục, bảo vệ, và được phân loại như kỹ pháp tổ hợp, lai các phương pháp trên. thuật lưu lượng (Traffic Enginnering - TE). Mức này có đặc trưng là: Đưa Việc lựa chọn các phương pháp nào rất quan trọng, phụ thuộc vào bài toán luồng lưu lượng vào chỗ có băng thông và tài nguyên khả dụng. cụ thể, kinh nghiệm và khả năng nhạy cảm đối với từng vấn đề của người sử • Mức 2: Chức năng tối ưu hoạt động mạng (Network Enginnering - NE) có dụng. Dựa trên các phân tích ưu nhược điểm của các phương pháp trên, các thời gian mức giờ đến ngày và có đặc trưng là: Đặt, phân bổ băng thông, tài phương pháp được lựa chọn trong luận án để giải bài toán tối ưu topology và nguyên hiện có vào chỗ có lưu lượng và định tuyến bao gồm: • Mức 3: Chức năng qui hoạch mạng (Network Planning –NP) có thời gian 1. Phương pháp heuristic: Theo cách tự nhiên, phương pháp này bước đầu mức tháng đến năm và có đặc trưng: Đặt, phân bổ băng thông, tài nguyên được sử dụng để đánh giá sơ bộ theo kinh nghiệm về các giả định, bài toán vào chỗ sẽ có lưu lượng. mới xây dựng và cũng có thể áp dụng cho bài toán mức ở qui mô lớn sau Phạm vi nghiên cứu của luận án này chủ yếu tập trung vào các vấn đề và khi có sự khảo sát về mức độ gần đúng; giải pháp ứng dụng trong NE và NP; áp dụng cho các mạng WDM có cấu trúc 2. Phương pháp giải chính tắc dựa theo quy hoạch tuyến tính nguyên (ILP): Ring theo hướng tích hợp mạng đa lớp và cung cấp các dịch vụ tiên tiến như Phương pháp này cho kết quả chính xác với qui mô mạng nhất định và cho mạng riêng ảo trong mạng quang thế hệ sau. thấy rõ các yếu tố ảnh hưởng đến kết quả của bài toán. 1.2.2 Khái quát những nghiên cứu đã công bố về phân bổ tài nguyên trong mạng quang cấu hình Ring CHƯƠNG 2. XÂY DỰNG BÀI TOÁN TỐI ƯU TOPOLOGY VÀ Hiện có nhiều cách tiếp cận khác nhau về tối ưu sử dụng tài nguyên trong ĐỊNH TUYẾN TRONG MẠNG QUANG WDM CẤU HÌNH RING thiết kế mạng quang WDM cấu hình Ring phụ thuộc vào mục tiêu tối ưu và các điều kiện cho trước khác nhau. Tuy nhiên, vẫn chưa có nghiên cứu về ảnh 2.1 GIỚI THIỆU hưởng đồng thời của yếu tố như: lưu lượng, topology/thứ tự nút và định tuyến Bài toán thiết kế mạng quang cấu hình Ring theo cách tối ưu đồng thời đến kết quả thiết kế mạng Ring hai hướng. Các nghiên cứu trước đây chỉ chủ topology và định tuyến được xây dựng trên cơ sở phân tích các cách tiếp cận yếu tập trung giải pháp tối ưu mạng theo cách khảo sát ảnh hưởng của từng trong thiết kế mạng, các đặc trưng về mạng lõi quang vùng đô thị và các kết yếu tố một và cố định các yếu tố còn lại, hoặc thực hiện tuần tự bằng cách chia quả nghiên cứu về thiết kế mạng quang cấu hình Ring theo phương pháp nhỏ bài toán lớn thành hai bước và kết quả nói chung đạt được là tối ưu cục truyền thống. Các thuật toán và một số kết quả thiết kế mạng quang cấu hình bộ: Ring theo phương pháp truyền thống cũng được giới thiệu và được phân tích + Bước 1: Thiết kế topology của Ring - xác định số nút, thứ tự kết nối các để thấy rõ được các yếu tố ảnh hưởng đến kết quả của bài toán thiết kế cũng nút trên Ring; như làm cơ sở cho việc phát triển các giải pháp được đề xuất ở chương sau. + Bước 2: Định tuyến lưu lượng trên topology Ring sao cho tối thiểu tải cực 2.2 PHƯƠNG PHÁP THIẾT KẾ MẠNG QUANG CẤU HÌNH RING đại trên các cạnh của Ring. Vì vậy, vấn đề tối ưu đồng thời cả hai bước 1 và 2 trong mạng truyền tải 2.2.1 Mô hình mạng truyền tải quang quang cấu hình Ring được nghiên cứu trong phạm vi của luận án. Cụ thể, là Mạng truyền tải quang có qui mô rất lớn và phức tạp, do đó được tổ chức nghiên cứu về phương pháp thiết kế mạng quang WDM cấu hình Ring hai theo mô hình chồng phủ đa lớp mạng và mỗi lớp mạng lại được phân tích hướng theo cách tối ưu đồng thời topology và định tuyến cân bằng tải với hàm thành một số vùng và lớp mạng con tương đối độc lập nhau theo khuyến nghị mục tiêu tối thiểu tải hay tổng chi phí. ITU-T G.805. Liên kết giữa lớp mạng được thực hiện theo cách: mạng lớp trên 1.2.3 Hướng nghiên cứu của luận án về giải pháp nâng cao hiệu quả sử sử dụng các dịch vụ kết nối, truyền tải do mạng ở lớp dưới cung cấp. Các vùng dụng tài nguyên mạng quang cấu hình Ring hay mạng con có thể được tổ chức theo các kiến trúc mạng cơ sở (như Các bài toán thiết kế tối ưu mạng truyền tải quang được xét trong nghiên SPRing, DPRing, …) và kết nối giữa chúng bởi các tuyến và nút mạng. Trong cứu này thuộc lớp các bài toán tối ưu tổ hợp và có thể được mô hình hóa theo mô hình mạng đa lớp này, thì topology của lớp mạng trên chính là đầu vào của qui hoạch tuyến tính nguyên (ILP) hoặc hỗn hợp (MLP). Để giải quyết các bài ma trận lưu lượng của mạng lớp dưới và sau đó lưu lượng được định tuyến toán tối ưu mạng, hiện có nhiều phương pháp và thuật toán tối ưu được sử trên topology mạng lớp dưới. dụng như: 1) Phương pháp heuristic; 2) Phương pháp qui hoạch toán học; 3)
7 8 2.2.2 Các bước trong thiết kế mạng quang Sau đây giới thiệu phương pháp thiết kế mạng quang theo cấu trúc Ring Việc thiết kế mạng quang lớn và phức tạp thường được thực hiện theo theo cách tiếp cận tuần tự truyền thống, để làm cơ sở cho việc đề xuất bài toán phương pháp chia nhỏ thành các giai đoạn, bài toán con tương đối độc lập và thiết kế mạng quang cấu hình Ring theo cách tiếp cận tích hợp. thực hiện tuần tự. Hình 2-3 minh họa các bước hay các bài toán chính trong 2.2.3 Phương pháp thiết kế mạng quang cấu hình Ring theo tiếp cận tuần thiết kế mạng tương ứng với các phân lớp, phân vùng trong mạng truyền tải. tự Tùy thuộc vào nhiệm vụ thiết kế, tối ưu mạng và bài toán cụ thể mà hàm mục Việc thiết kế Ring đơn thỏa mãn lưu lượng cũng như độ tin cậy và với mục tiêu có thể là tối thiểu tổng chi phí mạng với các ràng buộc về chất lượng, kỹ tiêu tối thiểu tổng chi phí được thực hiện theo các bước tương ứng các bài toán thuật xác định; hay tối thiểu chiếm giữ tài nguyên mạng; hay tối đa thông con sau: lượng. Bài toán 1. Trên cơ sở ma trận tuyến kết nối cho trước C={cij}, xác định Phương pháp thiết kế tuần tự và chia nhỏ thành các bài toán con độc lập topology của mạng có cấu hình Ring bao gồm: thứ tự/vị trí nút kết nối tạo tương ứng như các bước ở trên thì dễ thực hiện và tận dụng được các thuật thành Ring và các tuyến kết nối giữa chúng; toán đã phát triển, nhưng nói chung chỉ cho kết quả tối ưu cục bộ. Bài toán 2. Định tuyến lưu lượng trên Ring đã xác định, sao cho thỏa mãn Cách tiếp cận giải tích hợp là coi các bước, các bài toán con như một bài ma trận lưu lượng D={dsd} cho trước. toán lớn hơn. Nói chung cách này cho kết quả tốt hơn, nhưng phức tạp hơn và Bài toán 1 là tìm topology của Ring với mục tiêu thường là tổng chi phí/ khó áp dụng đối những bài toán có kích cỡ lớn, yêu cầu xử lý nhanh. Tuy cự ly giữa các nút tạo nên tuyến của Ring là nhỏ nhất. Bài toán này có dạng nhiên, chúng cũng thường được sử dụng cho qui mô nhỏ hay để khảo sát các bài toán người du lịch (TSP) hay tìm chu trình hamilton kinh điển. Hiện có mô hình mới và đánh giá chính xác các thuật toán khi áp dụng trong phạm vi nhiều phương pháp giải theo mô hình ILP hay các thuật toán heuristic. nhỏ. Xu hướng mạng truyền tải quang thông minh, tích hợp đa lớp và có Đối với DPRing, bài toán 2 dễ dàng xác định theo nguyên tắc định tuyến tương tác, do đó sẽ nảy sinh những ứng dụng mới và những yêu cầu về tích và phân bổ bước sóng đơn giản là: mỗi một lưu lượng luồng quang điểm - hợp cần giải quyết đồng thời. điểm sẽ sử dụng một bước sóng riêng trên toàn Ring. Do đó, số bước sóng hay dung lượng tối thiểu cần thiết chính là tổng số lưu lượng chạy trên Ring. Thông tin đầu vào Đối với SPRing hay Ring hai hướng, bài toán 2 cần xác định tuyến đường Ma trận lưu Mô hình thiết Kiến trúc mạng Địa lý, lượng bị, chi phí ứng cử(Ring,…) Quản lý,… đi cho mỗi lưu lượng trên Ring với mục tiêu tối thiểu dung lượng cực đại chiếm giữ trên các tuyến/cạnh của Ring hay còn gọi là Tải của Ring (Z). Phần sau giới thiệu bài toán này. Phạm vi nghiên cứu Thiết kế topology 2.2.4 Phân bổ tài nguyên trong mạng quang cấu hình Ring WDM hai Vị trí nút Kết nối hướng 2.2.4.1 Giới thiệu bài toán Trong mạng WDM khi không có bộ chuyển đổi bước sóng, bài toán này Định tuyến và Định cỡ bao gồm 2 phần: định tuyến và phân bổ/gán bước sóng –RWA. Phần định Phân bổ Định tuyến dung lượng kết nối tuyến (R) yêu cầu xác định tuyến cho mỗi luồng lưu lượng quang và phần phân bổ bước sóng (WA) thực hiện gán bước sóng cụ thể cho mỗi luồng lưu Phân tích giải pháp Tối ưu lại lượng sao cho trên mỗi chặng trên tuyến đường mà nó đi qua không có 2 bước Đánh giá kỹ Phân tích sóng trùng nhau, ràng buộc này còn gọi là tính liên tục của bước sóng. Do vậy, thuật chi phí bài toán trở lên phức tạp hơn và đã được chứng minh là loại NP-đầy đủ. Để tránh nhầm lẫn giữa tên gọi trong chức năng định tuyến, bài toán này cũng Hình 2-3: Các bước cơ bản trong thiết kế mạng. thường gọi là phân bổ tài nguyên hay băng thông mạng. Ở Việt Nam hiện nay, việc giải bài toán chia mạng truyền tải quang thành Sử dụng bộ chuyển đổi bước sóng làm tăng hiệu quả dung lượng của mạng các vùng/Ring thường được xác định theo phân cấp các thiết bị chuyển mạch, nhưng sẽ làm tăng đáng kể chi phí của mạng. Khi có chuyển đổi bước sóng, tổng đài lớp trên và phân cấp quản lý; số nút trong từng cấp này nhỏ. Vì vậy, bài toán RWA chỉ còn phần định tuyến (R) và cũng là chủ đề rất được quan bài toán điển hình là thiết kế hiệu quả mạng quang cấu hình Ring đơn. tâm của định tuyến trong Ring SDH có hoán đổi khe thời gian. Tuỳ thuộc vào công nghệ và cách quản lý các luồng khác nhau, mà có các cách định tuyến
9 10 khác nhau: Định tuyến có tách hay không cho tách lưu lượng trên Ring. Lưu Bước 2: Phân bổ hay gán bước sóng lượng được định tuyến tách trên Ring khi luồng lưu lượng của nó được chia Phân bổ bước sóng là một trong những đặc trưng riêng của WDM. Bài làm hai phần và được định tuyến trên hai hướng của Ring. Nói chung định toán phân bổ bước sóng được xem là NP-đầy đủ, và có thể áp dụng một số tuyến có tách lưu lượng cho kết quả tốt hơn khi không tách lưu lượng. cách giải sau: Tập trung vào giải quyết vấn đề phân bổ băng thông cho Ring WDM cho 1. Phương pháp tối ưu theo ILP. Cách này cho kết quả tối ưu chính xác tuy các ứng dụng NE và NP, cho nên các tham số đầu vào như ma trận lưu lượng nhiên chỉ phù hợp khi kích cỡ bài toán nhỏ; quang lớp trên và topology của Ring WDM lớp dưới đã xác định trước. Việc 2. Các giải thuật Heuristic, theo đó sẽ cố gắng “điền” bước sóng theo cách tốt tính toán định tuyến và gán bước sóng có thể được thực hiện trước khi thiết nhất có thể. Trong phần này của luận án đã giới thiệu một thuật toán hiệu lập cấu hình Ring để thỏa mãn nhu cầu ma trận lưu lượng và thường với mục quả đã được phát triển trong [6]. tiêu tối thiểu số bước sóng cần sử dụng. Thuật toán hai bước tuần tự kiểu như trên đã được thử trên rất nhiều mẫu Tương tự như đã đề cập ở trên, nói chung có hai cách tiếp cận để giải bài lưu lượng ngẫu nhiên và hầu hết cho kết quả tối ưu toàn cục. Chẳng hạn, trong toán RWA trong mạng quang WDM cấu hình SPRing: lần thử với mạng Ring 11 nút, lưu lượng giữa các cặp nút theo phân bố đều - Cách 1: Giải quyết đồng thời cả hai bài toán R và WA. Phương pháp thường giữa 0 và 5 kênh. Kết quả trung bình về yêu cầu số bước sóng lớn nhất là 35. được sử dụng là mô hình theo ILP và có thể sử dụng các kỹ thuật như nhánh- Trong 1000 phép thử, thuật toán phân bổ bước sóng chỉ cho kết quả không tối cận, tạo cột, làm tròn… để giải và cho kết quả tối ưu. ưu trong 5 bước sóng. Tổn thất do thiếu bộ chuyển đổi bước sóng chỉ xấp xỉ: 5 - Cách 2: phân tách bài toán thành hai bài toán con riêng rẽ và giải tuần tự: bước sóng /(1000x35) = 0,01%. Kết quả này cũng phù hợp với kết quả trên thế + Bài toán định tuyến luồng lưu lượng trên Ring (R-Routing problem) và giới khi thực hiện giải tối ưu chính xác theo mô hình ILP cho bài toán RWA. + Bài toán gán hay phân bổ bước sóng cho các luồng lưu lượng đã định Thảo luận tuyến (WA- Wavelength Allocation /Assignment problem). Những phân tích trên đây chỉ ra rằng trong trường hợp ma trận lưu lượng Cách 1 cho kết quả tối ưu chính xác, nhưng phức tạp. Cách 2 dễ giải biết trước, thì có thể phân bổ luồng quang rất hiệu quả trong các SPRing quyết, đơn giản hơn, tận dụng được các thuật toán đã phát triển. WDM bằng các thuật toán theo cách giải hai bước. Lợi ích đem lại nhờ sử Phần sau giới thiệu một số kết quả và phương pháp giải theo 2 bước tuần dụng các bộ chuyển đổi bước sóng rất nhỏ với các giải thuật hiệu quả. Do đó tự (cách 2) dựa trên một số kết quả nghiên cứu trước đây trên thế giới, và của cho phép thiết kế mạng Ring với chi phí thấp hơn. Vì vậy, đây cũng là một cơ tác giả đã phát triển [6], [8] và qua các thử nghiệm cũng cho thấy kết quả tối sở để chương sau đưa ra giải pháp cho bài toán tích hợp trong phạm vi tối ưu ưu trong hầu hết các trường hợp. topology với phần định tuyến (R), không bao gồm phần gán bước sóng (W). 2.2.4.2 Cận của bài toán Một mặt để giảm tính phức tạp của bài toán tích hợp nếu đưa cả phần gán Như đã nói ở trên trong trường hợp có chuyển đổi bước sóng thì bài toán bước sóng, mặt khác bài toán sẽ có phạm vi áp dụng rộng hơn, tức là có thể áp RWA chỉ còn phần định tuyến (R). Vì vậy, giới hạn lời giải của bài toán RWA dụng cho cả các công nghệ Ring hai hướng khác mà không yêu cầu có phần tối thiểu sẽ là cận dưới của bài toán khi có chuyển đổi bước sóng. Cận dưới gán tài nguyên hay bước sóng chẳng hạn như trong mạng WDM có chuyển đổi của bài toán định tuyến theo lý thuyết Okamura-Seymour là kích cỡ của nhát bước sóng. Tiếp theo sẽ giới thiệu bài toán thiết kế tối ưu topology và định cắt cực đại MaxCut trên Ring. Trong đó, kích cỡ nhát cắt được định nghĩa như tuyến theo cách tiếp cận này. tổng lưu lượng không được định tuyến trên Ring do nhát cắt gây ra đi qua hai 2.3 BÀI TOÁN TỐI ƯU TOPOLOGY VÀ ĐỊNH TUYẾN RING QUANG cạnh và chia Ring thành hai phần. HAI HƯỚNG 2.2.4.3 Phương pháp giải tuần tự 2.3.1 Đặt vấn đề Bước 1: Định tuyến lưu lượng trong Ring Phương pháp và thuật toán thiết kế mạng Ring WDM hai hướng theo cách Trong bước này cần phải xác định tuyến lưu lượng thuận hoặc ngược chiều tiếp cận tuần tự cho thấy tổng chi phí của Ring bao gồm chi phí tuyến và chi kim đồng hồ với giả định có bộ chuyển đổi bước sóng. Để phục vụ cho phát phí thiết bị. Chi phí tuyến phụ thuộc vào tổng chu trình các tuyến kết nối tạo triển giải pháp ở chương 3, phần này của chương đã phát biểu bài toán dưới nên Ring, còn chi phí thiết bị phụ thuộc vào dung lượng đường truyền của dạng các mô hình toán học theo ILP cả định tuyến tối ưu cân bằng tải có hoặc thiết bị. không tách lưu lượng. Các mô hình này có thể được sử dụng để giải cho kết Việc xác định topology của Ring thường thông qua giải bài toán dạng tìm quả tối ưu chính xác bằng giải thuật nhánh–cận nhờ các công cụ AMPL, Cplex chu trình Haminton nhỏ nhất (hay bài toán người du lịch - TSP) đi qua tất cả hay Scip.
11 12 các nút có trọng số là chi phí hay cự ly của từng tuyến. Đối với mạng có chi Các đầu vào: phí đường truyền chiếm tỉ trọng lớn (đường trục hay cấp vùng) thì việc tìm 1. Gọi topology có thể kết nối của mạng là Go= (V, Eo) là đồ thị vô hướng, chu trình nhỏ nhất theo cự ly là hợp lý. Nhưng trong môi trường mạng ảo hay trong đó V là tập N nút và Eo là tập các tuyến có trọng cij có thể thiết lập mạng đô thị có khoảng cách trung bình giữa các nút ngắn (
13 14 Chương 4 sẽ giới thiệu kết quả mô phỏng đánh giá các giải pháp này. • Phương án 2: Hàm trọng x= -dij tương ứng lời giải TSP(-dij) {có thể sử 3.2 ĐỀ XUẤT PHƯƠNG PHÁP THIẾT KẾ TOPOLOGY VÀ ĐỊNH dụng TSP(1/dij)} đây là trường hợp thuận lợi cho SPRing về mặt lưu lượng: TUYẾN THEO TIẾP CẬN TUẦN TỰ cặp lưu lượng có số luồng lớn sẽ có số chặng nhỏ nhất là 1 (liền kề), các cặp nút có lưu lượng nhỏ sẽ có số chặng lớn, từ đó có thể coi MaxCut là nhỏ Phương pháp này dựa theo cách tiếp cận hai bước truyền thống là: giải bài nhất. Trường hợp này không tính đến chi phí đường truyền cij khi xác định toán xác định topology tối ưu cho Ring theo TSP(x) với hàm trọng x, tiếp theo topology. giải bài toán định tuyến lưu lượng, phân bổ tài nguyên trên topology đã xác định như lưu đồ Hình 3-1. Ý tưởng của phương pháp này là bằng cách xây • Phương án 2’: Hàm trọng x= dij tương ứng lời giải TSP(dij) - đây là trường dựng hàm trọng x phù hợp cho bài toán xác định topology sẽ làm thay đổi vị hợp bất lợi nhất cho SPRing: cặp lưu lượng có số luồng lớn sẽ có số chặng trí tương đối các nút trong ma trận lưu lượng trên Ring từ đó có ảnh hưởng lớn nhất, các cặp nút liền kề sẽ có lưu lượng nhỏ dẫn đến MaxCut là lớn đến kết quả định tuyến lưu lượng trên Ring. nhất- đây có thể coi là cận trên; • Phương án 3: Hàm trọng x= cij -k×(C1/D0)×dij, với k là hệ số chỉ mức độ Bắt đầu quan trọng của phần lưu lượng (chi phí thiết bị) so với chi phí đường truyền. Với hàm trọng này, lời giải TSP(cij- k x (C1/D0) x dij) sẽ bao gồm cả chi phí Nhập đầu vào đường truyền và lợi ích từ các cạnh có luồng lớn và sẽ cải thiện hơn về mặt MaxCut của phương án 1. Với k=0, thì TSP(x)= TSP(cij), C3=C1 và Z3=Z1; Thiết kế các Topo Ring tối ưu: TSP theo các ij ij hàm trọng: (cij), (-d ), (cij-k×C1/D0×d ) với k >>1, thì TSP(x)= TSP(–dij), C3=C2 và Z3=Z2; nếu k
15 16 xij∈ {0,1}, ui ≥ 0 cho ∀ i, j = 1, ..., N; (3-5) 3-5) là thuộc loại NP-đầy đủ, do đó bài toán (3-15) với các ràng buộc (3-1) xij là các biến nhị phân và ui là số các nút đã đi qua đến khi gặp nút i. đến (3-11) cũng là thuộc loại NP-đầy đủ. Không gian lời giải của bài toán phụ b. Ràng buộc xác định cách định tuyến có tách lưu lượng trên Ring thuộc vào tổng số các biến xij, fsdij với các phần tử dsd ≠0 và các hệ phương Gọi fsdij là phần lưu lượng giữa nguồn s và d định tuyến trên tuyến i, j : s, trình ràng buộc. Tuy nhiên, do số nút trong thực tế triển khai là nhỏ và số lưu d, i, j = 1..N. lượng dsd ≠0 không nhiều, do đó có thể giải trực tiếp bài toán này bằng giải fsdij nguyên ≥ 0 và ≤ dsd (3-6) thuật Nhánh-Cận trong thời gian cho phép. Ràng buộc này cho phép định tuyến tách lưu lượng trên 2 hướng. Bài toán (3-12) với các ràng buộc (3-1) đến (3-11) có hàm mục tiêu là tối Σj fsdij - Σj fsdji = 0 , với ∀ s, d, i = 1..N: s
17 18 • Để so sánh với các mô hình mô phỏng tương tự trên thế giới, hàm mục tiêu tối thiểu băng thông cực đại hay tải của Ring được áp dụng. Với mỗi mẫu CHƯƠNG 4. MÔ PHỎNG GIẢI BÀI TOÁN TỐI ƯU TOPOLOGY lưu lượng, thực hiện theo 3 phương án sau: VÀ ĐỊNH TUYẾN TRONG MẠNG QUANG CẤU HÌNH RING 1. Phương án 1: Giải pháp tích hợp tối ưu topology và định tuyến tối ưu có 4.1 GIỚI THIỆU tách lưu lượng và không tách lưu lượng theo hàm mục tiêu (3-12) và các Để đánh giá kiểm chứng các giải pháp đã đề xuất ở chương 3, trong hệ ràng buộc tương ứng. chương này sẽ giới thiệu một số kết quả tính toán mô phỏng, với mục tiêu: 2. Phương án 2: Giải pháp hàm trọng theo tiếp cận tuần tự: Xác định + Đánh giá so sánh tương đối với các kết quả tương tự trên thế giới; topology Ring tối ưu với các hàm trọng tối đa tổng lưu lượng giữa các + Đánh giá hiệu năng của các giải pháp để từ đó xác định miền áp dụng; cạnh liền kề theo hàm mục tiêu (3-14); rồi định tuyến tối ưu cân bằng tải + Khảo sát một số nhân tố ảnh hưởng đến kết quả bài toán. có tách và không tách lưu lượng trên topology đã xác định; 4.2 THIẾT LẬP MÔ PHỎNG 3. Phương án 3: topology của Ring được xác định theo thứ tự ngẫu nhiên, rồi định tuyến tối ưu cân bằng tải tương ứng có tách và không tách lưu Sử dụng các giả định, thiết lập và tính toán các tham số đánh giá tương tự lượng. như các kết quả đã thực hiện trên thế giới về tối ưu topology cấu hình Ring hai • Các giá trị dung lượng hay tải của Ring và tổng chi phí của mỗi phương án hướng. Cụ thể như sau: được tính toán và so sánh cho mỗi mẫu mô phỏng. a. Tham số đầu vào cho mỗi mẫu: • Tham số so sánh giữa các phương án với cùng số liệu đầu vào là mức độ • Ma trận lưu lượng D={dsd} và ma trận chi phí tuyến C= {cij} đều có mẫu cải thiện (hay độ lợi) tương đối về mặt dung lượng PI (%) giữa hai phương dạng lưới ngẫu nhiên với mỗi phần tử có giá trị ngẫu nhiên theo phân bố án được định nghĩa theo công thức sau: đều từ 0 – 16; + So sánh giữa phương án 1 so với phương án 2 : b. Số lượng mẫu mô phỏng được thực hiện: PIO-H = (ZH - ZO)/ ZO (%) (4-1) • Để giảm sự thăng giáng của các kết quả mô phỏng, các tác giả trên thế giới Với ZO, ZH là giá trị tải của Ring tương ứng với phương án 1 và 2. đã thử nghiệm trên số mẫu 100 và 50 tương ứng. Để tăng độ chính xác, + Giữa phương án 1 so với phương án 3: chúng tôi đã thực hiện mô phỏng cho mỗi loại Ring có số nút N= 4 .. 7, và PIO-R = (ZR – ZO)/ ZO (%) (4-2) 8 tương ứng với số mẫu là 1000 và 100. Với số nút N=9, do thời gian tính Trong đó ZO, ZR là giá trị tải của Ring tương ứng với phương án 1 và 3. toán lớn, nên số mẫu được thực hiện là 5. • Tương ứng với mỗi loại Ring có số nút nhất định, thực hiện tính toán các c. Cách thực hiện mô phỏng: giá trị thống kê trên số mẫu mô phỏng để so sánh và đánh giá, bao gồm các • Để đánh giá và so sánh chính xác giữa các giải pháp tuần tự và tích hợp, thông số sau: Giá trị trung bình của thời gian giải mô hình ILP bằng giải luận án sử dụng các mô hình theo ILP để giải cho kết quả chính xác, cụ thể thuật nhánh- cận cho kết quả tối ưu chính xác của phương án 1; Giá trị là: trung bình PI(%); Khoảng tin cậy CI(%) của giá trị trung bình PI(%) với 1. Mô hình ILP cho bài toán giải đồng thời tối ưu topology và định tuyến có độ tin cậy 95%; Tần suất xuất hiện (%) tương ứng với một dải PI(%) nhất tách lưu lượng và không tách lưu lượng, theo hàm mục tiêu (3-12) và các định là tỷ số giữa số mẫu có PI(%) thuộc dải đó trên tổng số mẫu mô hệ phương trình ràng buộc tương ứng. phỏng. 2. Mô hình ILP cho bài tóan TSP theo các hàm trọng cij và –dij tương ứng với hàm mục tiêu theo biểu thức (3-13) và (3-14) cùng các hệ phương 4.3 KẾT QUẢ MÔ PHỎNG TỐI ƯU TOPOLOGY VỚI ĐỊNH TUYẾN trình ràng buộc tương ứng; CÓ TÁCH NHU CẦU 3. Mô hình ILP cho bài toán định tuyến tối ưu cân bằng tải có tách và Các kết quả nhận được cho các giải pháp 1, 2 và 3 đều cho kết quả tối ưu không tách lưu lượng như đã giới thiệu trong mục 2.2.4.3 chương 2; tuyệt đối. Ngoài ra, giai đoạn đầu chưa có điều kiện tiếp cận Cplex, chúng tôi • Sử dụng ngôn ngữ AMPL để mã hóa các mô hình trên. Sử dụng bộ công cũng thử nghiệm giải bài toán trên phần mềm không thương mại Scip và sau cụ thương mại Cplex 9.0 và phần mềm không thương mại Scip với giải này khi có điều kiện chạy trên Cplex, so sánh cho thấy kết quả giống nhau, thuật nhánh – cận để giải tối ưu các mô hình ILP trên và tính toán so sánh ngoại trừ khi số nút tăng thời gian xử lý của Cplex nhanh hơn Scip. giữa các giải pháp. Hình 4-3 biểu diễn các đồ thị về giá trị trung bình của thời gian tính toán • Môi trường mô phỏng: Pentium IV, 3 Ghz, Windows XP II. và PI(%) giữa các phương án 1 với phương án 2 và phương án 1 với phương
19 20 án 3. Kết quả cho thấy thời gian tính toán theo hàm số mũ thể hiện rõ bài toán Do vậy, cách giải theo phương án 2 cũng cho kết quả hợp lý và có thể áp dụng thuộc loại NP- đầy đủ. Mức độ gần đúng của phương án 2 so với phương án 1 đối với bài toán cỡ lớn. Qua đây cũng cho thấy, mặc dù tổng các lưu lượng là nhỏ, và mức độ cải thiện về dung lượng trung bình khá lớn của phương án 1 giữa các nút liền kề trên các cạnh của Ring trong phương án 2 luôn lớn hơn (tối ưu đồng thời topology và định tuyến) so với phương án 3 (thiết kế truyền hoặc bằng phương án 1, nhưng tải cực đại của phương án 1 luôn nhỏ hơn thống- không tối ưu topology theo lưu lượng). phương án 2, từ đó cho thấy sự bố trí tương đối giữa các lưu lượng có ảnh Kết quả mô phỏng cho thấy với tất cả các trường hợp, phương án 1 (tối ưu hưởng đến kết quả định tuyến tối ưu. đồng thời cả về topology và định tuyến) luôn cho kết quả tốt hơn so với 4.4 KẾT QUẢ MÔ PHỎNG TỐI ƯU TOPOLOGY VỚI ĐỊNH TUYẾN phương án 2 (Heuristic hàm trọng theo tiếp cận 2 bước) và phương án 3 KHÔNG TÁCH LƯU LƯỢNG (topology ngẫu nhiên và định tuyến tối ưu). Thực hiện mô phỏng giải bài toán tối ưu topology cấu hình Ring và định Với số nút càng tăng từ 4 – 8, tần suất phương án 1 tốt hơn 3 càng tăng và tuyến tối ưu không tách lưu lượng cũng được thực hiện với cùng số liệu đầu PI càng lớn. Chẳng hạn, với số nút n=7, và trong 1000 mẫu thử ngẫu nhiên, số vào tương tự như trên. Để đánh giá hiệu quả của các giải pháp đề xuất, các kết trường hợp phương án 1 tốt hơn phương án 3 chiếm 99% và giá trị trung bình quả theo phương án 1, 2 và 3 tương ứng các giải pháp cũng được tính toán và PI nằm trong dải 22% ± 0,63% với độ tin cậy 95%. Tức là, để thoả mãn cùng so sánh. một ma trận lưu lượng giữa các nút, nếu sử dụng phương pháp thiết kế tối ưu Các kết quả thu được tương ứng với định tuyến không tách lưu lượng cả topology và định tuyến, về trung bình dung lượng yêu cầu chiếm giữ trên cũng tương tự như trường hợp định tuyến có tách lưu lượng ở phần trên. Hình Ring chỉ bằng 78% dung lượng của trường hợp theo thiết kế thông thường hai 4-4 biểu diễn đồ thị kết quả so sánh về mức độ hiệu quả dung lượng PI(%) bước. Định tuyến tối ưu cho phép tách nhu cầu lưu lượng giữa các phương án 1, 2 và 3. Kết quả cho thấy mức độ cải thiện giữa phương 30% 100000 án 1 tốt hơn nhiều so phương án 3. Định tuyến tối ưu không cho phép tách nhu cầu lưu lượng 30% 24% 10000 25% 26% 22% 27% 21% 25% 26% 26% 1000 23% 20% 18% Thời gian( Sec) 20% 21% 100 PI(%) 18% 15% PI (%) 15% 10 10% 10% 1 10% 6% 5% 5% 4% 5% 6% 0,1 5% 2% 4% 1% 3% 3% 0% 1% 0% 0,01 0% 4 5 6 số nút 7 8 9 3 4 5 6 Nodes 7 8 9 10 PI(%) trung bình của Phương án 1 (Tối ưu tích hợp) so với phương án 2 (Hàm trọng) PI(%) trung bình của Phương án 1 (tối ưu tích hợp) so với phương án 3 ( Ngẫu nhiên) PI(%) trung bình của Phương án 1 (tối ưu tích hợp) so với phương án 3 ( Ngẫu nhiên) PI(%) trung bình của Phương án 1 (Tối ưu tích hợp) so với phương án 2 (Hàm trọng) Thời gian giải ILP (sec) Hình 4-4: Kết quả so sánh giữa các phương án 1, 2 và 3 với định tuyến Hình 4-3: Kết quả so sánh giữa các phương án 1, 2 và 3 với định tuyến có không tách lưu lượng. tách lưu lượng. 4.5 PHÂN TÍCH VÀ THẢO LUẬN Khi số nút nhỏ, cả 2 phương án 1 và 2 cho kết quả tương tự nhau, khi số Trên cơ sở các kết quả mô phỏng trên, sau đây sẽ đưa ra một số quan sát và nút tăng lên thì mới thấy rõ hơn sự chênh lệch giữa 2 phương án. Tuy nhiên, nhận xét sau: tần suất xuất hiện không nhiều và PI(%) giữa 2 giải pháp là không lớn, chẳng 1. Trong tất cả các mẫu mô phỏng, kết quả của phương án 1 luôn tốt hơn hạn với số nút N=7, giá trị trung bình của PI(%) (chính là độ chênh lệch tương hoặc bằng kết quả của phương án 2 và 3. Do đó, về mặt thực nghiệm mô đối) giữa phương án 1 và 2 nằm trong khoảng (4 ± 0.29)% với độ tin cậy 95%.
21 22 phỏng cũng cho thấy phương án 1 bao gồm tối ưu cả topology và định tuyến yêu cầu) của Ring đó là topology và định tuyến. Mức độ đóng góp của tối ưu chính là cận dưới có thể đạt được của bài toán tối ưu topology và định chúng trong phần hệ số cải thiện PI(%) cũng phụ thuộc vào nhau. Nếu sử tuyến. Đây cũng là một ưu điểm của giải pháp tối ưu tuyệt đối theo ILP đó là dụng phương pháp định tuyến tốt (chẳng hạn tối ưu cân bằng tải có tách cho phép so sánh chính xác giữa các giải pháp - là một trong những kết quả lưu lượng), thì phần PI(%) do yếu tố tối ưu topology đóng góp sẽ nhỏ. đạt được mà các nghiên cứu tương tự trước đây chưa chỉ rõ. Ngược lại, nếu phương pháp định tuyến kém hơn (ví dụ: tối ưu không 2. Thời gian tính toán của giải pháp tích hợp theo ILP tăng nhanh theo hàm tách lưu lượng hay ngắn nhất…), thì phần đóng góp của tối ưu topology mũ; N < 10 cho kết quả tối ưu có thể áp dụng trong thiết kế mạng quang vào PI(%) sẽ lớn. trong thực tế (N=9, thời gian ~ 10 h). Vì số biến và ràng buộc phụ thuộc vào c. Định tuyến với tách lưu lượng luôn cho kết quả tốt hơn không tách lưu số nút N và số phần tử trong ma trận lưu lượng khác 0, do đó trong thực tế lượng, và độ chênh lệch giảm dần khi số nút tăng. Tức là với số nút đủ nếu ma trận lưu lượng có nhiều phần tử bằng 0, thì bài toán với số nút N ≥ lớn ( >6) thì lợi ích nhờ định tuyến tách lưu lượng không nhiều (4-5%), 10 có thể thực hiện được. do đó cần cân nhắc trong thiết kế và quản lý vì chức năng định tuyến tách 3. Giải pháp tích hợp cho kết quả lợi về mặt dung lượng tốt hơn nhiều so với lưu lượng sẽ làm tăng phức tạp của quản lý và điều khiển, nhưng mặt trường hợp ngẫu nhiên (20% -25%) với tần suất xuất hiện cao. Tham khảo khác nhờ chức năng này cũng nâng cao độ khả dụng của dịch vụ do lưu một số kết quả nghiên cứu tương tự trên thế giới với định tuyến cố định theo lượng được tách làm hai hướng trên Ring nên dịch vụ luôn luôn được đường ngắn nhất không tách lưu lượng cho thấy giá trị trung bình của PI(%) duy trì. giữa giải pháp tốt nhất so với trường hợp ngẫu nhiên với Ring có số nút N= So sánh định tuyến tối ưu với tách hoặc không tách lưu lượng 18,0% 10 là 19,6% ± 6,5% với độ tin cậy 95%. Một kết quả nghiên cứu trên thế dsd= dsd+ + dsd- giới khác có hàm mục tiêu tối thiểu tổng của tích lượng lưu lượng dsd với số 16,0% chặng mà lưu lượng được định tuyến trên Ring (tương tự như tổng băng d sd - d sd 14,0% thông/tải trên các cạnh của Ring) và với Ring có số nút N= 16 thì kết quả đạt d sd + được về giá trị trung bình của PI(%) giữa giải pháp theo thuật toán mô 12,0% phỏng tôi luyện SA so với trường hợp ngẫu nhiên là khoảng 10%. 10,0% r 4. Kết quả của phương pháp Heuristic hàm trọng xấp xỉ với kết quả chính xác theo ILP với tần suất xuất hiện cao, do đó có thể áp dụng phương pháp PI(%) 8,0% heuristic với số nút lớn. Giải pháp hàm trọng này khá đơn giản dễ tận dụng các thuật toán đã có và có thể nghiên cứu mở rộng cho cấu hình khác. 6,0% 5. Phân tích ảnh hưởng của cách định tuyến có tách và không tách lưu lượng 4,0% đến kết quả tối ưu: Với cùng mẫu lưu lượng lời giải của 2 cách định tuyến của từng phương án 1 hoặc 2 hoặc 3 được so sánh với nhau. Hình 4-6 biểu 2,0% diễn đồ thị PI(%) giữa hai cách định tuyến có tách so với không tách lưu 0,0% lượng. Kết quả cho thấy: 4 5 6 7 8 # Nút 9 10 11 12 13 14 15 16 a. Số nút tăng từ 4 đến 8, độ lệch giữa 2 cách định tuyến giảm từ 10% ÷ 2% PI(%) so giữa định tuyến có tách và không tách nhu cầu lưu lượng với giải pháp theo phương án 1 (Tối ưu đồng thời đối với giải pháp tích hợp, và từ 16% ÷ 2% đối với giải pháp topology Topology và định tuyến) ngẫu nhiên. Điều đó chứng tỏ là với nút nhỏ thì nhờ có tối ưu topology PI(%) so giữa định tuyến có tách và không tách nhu cầu lưu lượng với giải pháp theo phương án 2 (Topology theo hàm trọng rồi định tuyến) mà hiệu quả dung lượng tăng lên bù lại với định tuyến. PI(%) so giữa định tuyến có tách và không tách nhu cầu lưu lượng theo phương án 3 (Topology ngẫu nhiên và định b. Với cùng số nút, quan sát giá trị trung bình của PI(%) phương án 1 so với tuyến) phương án 3 với định tuyến không tách lưu lượng (xem Hình 4-4) lớn Hình 4-6: So sánh định tuyến tối ưu với tách hoặc không tách lưu lượng. hơn khi định tuyến có tách lưu lượng (xem Hình 4-3). Chẳng hạn với số 6. Khi xét đến hàm mục tiêu là tổng chi phí của Ring, với hệ số cb =1, kết quả nút N= 7, giá trị trung bình của PI(%) phương án 1 so với phương án 3 mô phỏng cũng cho thấy giải pháp của phương án 1 luôn lớn hơn phương 2 của định tuyến không tách lưu lượng và có tách lưu lượng tương ứng là và 3. Tổng chi phí phụ thuộc vào hệ số điều chỉnh tương đối cb và 2 yếu tố 26% và 22%. Điều này cho thấy khi xét trên cùng một ma trận lưu lượng, chi phí tuyến và thiết bị tương ứng với chúng là 2 ma trận ngẫu nhiên: chi thì có hai yếu tố góp phần đồng thời đến việc giảm tải (hay dung lượng phí C = {cij} và lưu lượng D= {dsd}. Thực hiện mô phỏng với 100 mẫu với
23 24 Ring có số nút N=7, các phần tử trong ma trận chi phí tuyến C = {cij} theo KẾT LUẬN phân bố đều có giá trị từ 0-16; hàm mục tiêu là Tổng chi phí tuyến và thiết bị Ở Việt Nam nói riêng, trên thế giới nói chung, mạng truyền tải quang được là TC = Ctuyến + cb x Z, và cb =1 (Trong trường hợp này, tỉ trọng giữa Ctuyến triển khai phổ biến với cấu hình Ring, cả trước đây, hiện nay và trong mạng và Cthiết bị chiếm khoảng 50% trên tổng chi phí). Kết quả về PI(%) của TC so thế hệ tiếp theo (NGN). Theo hướng tìm kiếm giải pháp nâng cao hiệu quả sử giữa phương án 1 (tối ưu cả topology và định tuyến với hàm mục tiêu tổng dụng tài nguyên trong mạng truyền tải quang, luận án này là kết quả nghiên chi phí) với phương án 2 (tối ưu chi phí tuyến và định tuyến cân tối thiểu tải) cứu góp phần giải quyết một vấn đề đã, đang và sẽ còn được tiếp tục nghiên có giá trị từ 0%- 16% và trung bình là 3,4%. Để so sánh được chính xác cần cứu, đó là tối ưu cấu trúc (topology) và định tuyến bước sóng trong mạng xác định được tỷ trọng của từng yếu tố đóng góp và tính toán theo số liệu truyền tải quang nhiều kênh ghép theo bước sóng (WDM) có cấu hình Ring thực. Triển khai thực tế mạng quang trong môi trường mạng đô thị ở Việt phổ biến hiện nay và cấu hình mắt lưới (Mesh) trong tương lai. nam các tuyến có cự ly ngắn (< 10 km), lưu lượng lớn, chi phí thiết bị chiếm Ngoài tổng hợp những nội dung lý luận để làm sáng tỏ cho những giải tỷ trọng lớn trên 80%. Qua kết quả mô phỏng tối ưu về mặt băng thông trên pháp đề xuất, luận án có những đóng góp mới : cũng có thể cho ta đánh giá sơ bộ về đóng góp của các yếu tố chi phí thông • Phát triển phương pháp thiết kế tối ưu mới thông qua việc xây dựng và qua ví dụ như sau: Nếu yếu tố chi phí thiết bị và chi phí tuyến chiếm tỉ trọng giải bài toán tối ưu đồng thời topology và định tuyến cân bằng tải cho tương ứng trong tổng chi phí là 80% và 20%, khi tối ưu topology và định mạng quang WDM cấu hình Ring; tuyến có mức độ cải thiện về mặt thông lượng là 26% thì phần đóng góp về • Phát triển phương pháp giải bài toán tối ưu đồng thời topology và định mặt cải thiện chi phí thiết bị trong tổng chi phí là 80% x 26%= 20,8%. Nếu tuyến cân bằng tải bằng sử dụng phương pháp theo quy hoạch tuyến tính chi phí tuyến trong trường hợp đó mà tăng lên 20% thì phần đóng góp của nguyên (ILP) và phương pháp heuristic hàm trọng đơn giản; chi phí tuyến là: 20% x (-20%) = -4%. Mức độ cải thiện về tổng chi phí sẽ • Thực hiện mô phỏng để kiểm chứng; là: 20,8% - 4 % = 16,8%. Do đó, phương pháp thiết kế mạng quang cấu hình • Đưa ra kiến nghị áp dụng phương pháp thiết kế đề xuất cho các mạng Ring khi tối ưu đồng thời cả topology và định tuyến nói chung sẽ đem lại quang. hiệu quả cao hơn so với phương pháp thiết kế tuần tự thông thường, nhất là HƯỚNG NGHIÊN CỨU TIẾP THEO trong môi trường mạng đô thị hoặc khi thiết kế Ring ảo chạy trên WDM. Trên cơ sở những kết quả đã đạt được trong quá trình thực hiện luận án, trong thời gian tới nghiên cứu của nghiên cứu sinh vẫn sẽ chủ yếu theo hướng nâng cao hiệu quả sử dụng tài nguyên trong mạng truyền tải quang. Trong một vài năm trước mắt, tiếp tục một số nghiên cứu theo hướng mở rộng áp dụng bài toán tích hợp tối ưu topology và định tuyến bước sóng cho mạng quang WDM với các điều kiện và cấu hình khác, cụ thể: + Giải bài toán tích hợp 3 lớp: Tối ưu topology Ring ảo, định tuyến lưu lượng trên Ring ảo và định tuyến bảo vệ Ring ảo trên mạng quang WDM; + Mở rộng các điều kiện ràng buộc bài toán: cho tải đối xứng/ bất đối xứng, lưu lượng động, lưu lượng Multicast, khi có các yêu cầu về tham số vật lý (tán sắc, bước sóng, công suất, nhiễu...), các mức chất lượng dịch vụ hay với các cơ chế bảo vệ/khôi phục khác nhau,... + Nghiên cứu xây dựng và giải bài toán nhóm lưu lượng (Traffic grooming) trong mạng với mục tiêu tối thiểu số thiết bị và có khả năng thay đổi thứ tự nút trên Ring. Về lâu dài, nghiên cứu sinh sẽ tiếp tục những nghiên cứu phát triển theo hướng chuyên sâu vào mạng truyền tải quang thế hệ tiếp theo (mạng quang đa bước sóng, chuyển mạch quang, cấu hình hỗn hợp và có sự tương tác giữa các lớp mạng). Những vấn đề nghiên cứu cụ thể là cùng nhịp với nghiên cứu trên thế giới và phù hợp với ứng dụng ở Việt Nam.
25 DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ [1] Vu Hoang Son, Bui Trung Hieu (2008), Integrated Bidirectional Ring Design with Splittable Traffic Routing, 2008 International Conference on Advanced Technologies for Communications, ATC 2008, Hanoi 6-9 Oct. 2008 Page(s):384 – 387. http://ieeexplore.ieee.org/Xplore/login.jsp?url=/stamp/stamp.jsp?arnumber=47 60603&isnumber=4760486 [2] Vũ Hoàng Sơn, Bùi Trung Hiếu, Hoàng Ứng Huyền (2008), Thiết kế topology và định tuyến tối ưu Ring quang hai hướng trong mạng quang thế hệ sau với cách tiếp cận ILP, Kỷ yếu hội thảo khoa học Quốc gia lần thứ tư về Nghiên cứu, Phát triển và Ứng dụng công nghệ Thông tin và Truyền thông- ICT.rda’08, Hà nội 8-9/8/2008, trang 321-327. [3] Vũ Hoàng Sơn, Bùi Trung Hiếu, Hoàng Ứng Huyền (2008), Giải pháp bảo vệ và định tuyến vòng gói tự hồi phục ảo trên mạng quang thế hệ sau, Kỷ yếu hội thảo khoa học Quốc gia lần thứ tư về Nghiên cứu, Phát triển và Ứng dụng công nghệ Thông tin và Truyền thông- ICT.rda’08, Hà nội 8- 9/8/2008, trang 328-335. [4] Vũ Hoàng Sơn, Bùi Trung Hiếu, Hoàng Ứng Huyền (2006), Phương pháp thiết kế tối ưu mạng quang WDM cấu hình Ring, Kỷ yếu hội thảo khoa học Quốc gia lần thứ ba về Nghiên cứu, Phát triển và Ứng dụng công nghệ Thông tin và Truyền thông- ICT.rda’06, Hà nội 20-21/5/2006, trang 18-24. [5] Vu Hoang Son, Le xuan Trung (2006), Method for optimizing optical ring topology in Metropolitan Area Network (MAN) in Vietnam, Proceedings of 34th Asian Info-communications Council Conference, Doc. No. 124, 15-19 May 2006. [6] Vũ Hoàng Sơn, Bùi Trung Hiếu, Vũ Tuấn Lâm (2003), Phân bổ băng tần trong mạng vòng quang WDM và ứng dụng, Tạp chí Bưu chính Viễn thông chuyên san “Các công trình nghiên cứu triển khai Viễn thông và CNTT”, Bộ Bưu chính viễn thông, số 9, 3-2003, trang 21- 29. [7] Vũ Tuấn Lâm, Vũ Hoàng Sơn (2003), Xu hướng tích hợp IP/quang trong mạng quang thế hệ sau, Tạp chí Bưu chính Viễn thông, sô 5,2003, trang 20-23. http://www.tapchibcvt.gov.vn/News/PrintView.aspx?ID=17076 [8] Vũ Hoàng Sơn (2001), Phương pháp thiết kế mạng truyền tải quang SDH, Tạp chí Bưu chính Viễn thông chuyên san “Các công trình nghiên cứu triển khai Viễn thông và CNTT”, Bộ Bưu chính viễn thông, số 5, 3/2001, trang 5-13.