Đề xuất phương pháp thiết kế Topologic trong mạng IP trên nền WDM có xem xét yêu cầu lưu lượng và số chặng vật lý

TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(39).2010 201 ĐỀ XUẤT PHƯƠNG PHÁP THIẾT KẾ TOPOLOGIC TRONG MẠNG IP TRÊN NỀN WDM CÓ XEM XÉT YÊU CẦU LƯU LƯỢNG VÀ SỐ CHẶNG VẬT LÝ PROPOSAL OF DESIGN METHODS FOR LOGICAL TOPOLOGIES IN NETWORKS OF IP OVER WDM IN CONSIDERATION OF BOTH THE TRAFFIC DEMAND AND HOP COUNT OF PHYSICAL ROUTES Nguyễn Quang Như Quỳnh, Nguyễn Văn Tuấn Trường Đại học Bách khoa, Đại học Đà Nẵng TÓM TẮT Những năm gần đây, nhiều phương pháp thiết kế tô pô lô gic trong mạng IP trên nền WDM (IP/WDM) được nghiên cứu rộng rãi, trong đó thuật toán thiết kế topologic tìm kiếm (HLDA) và thuật toán tối thiểu độ trễ (MLDA) được xem như là các thuật toán cơ bản sử dụng mô hình xếp chồng trong mạng IP/WDM [1]. HLDA và MLDA thiết lập các đường quang giữa các cặp node chỉ dựa trên yêu cầu lưu lượng giữa chúng. Trong bài báo này, chúng tôi đề xuất hai thuật toán mới, thuật toán thiết kế topologic đơn chặng tự do (SHFLDA) và thuật toán thiết kế topologic đơn chặng ràng buộc (SHCLDA) trong đó chúng thiết lập các đường quang giữa các cặp node dựa trên cả yêu cầu lưu lượng và số lượng số chặng của đường đi nhỏ nhất giữa chúng. SHFLDA cho lưu lượng cực đại thấp trên các đường quang sau khi được thiết lập và SHCLDA cho độ trễ trung bình thấp. Chúng tôi tiến hành so sánh 4 thông số giữa hai thuật toán: tổng lưu lượng trên topologic, lưu lượng cực đại trên các đường quang sau khi được thiết lập, tổng lưu lượng yêu cầu và phần trăm các bước sóng được sử dụng. Kết quả mô phỏng chỉ ra rằng SHFLDA hiệu quả hơn SHCLDA nếu quy mô mạng đủ lớn và ngược lại nếu quy mô mạng nhỏ thì sử dụng SHCLDA hợp lý hơn. ABSTRACT In recent years, many logical topology designing methods in IP- over - WDM networks (IP/WDM) have been widely investigated, in which Heuristic Logical Topology Design Algorithm (HLDA) and Minimum-Delay Logical Topology Design Algorithm (MLDA) are considered as basic algorithms using the overlay model in IP/WDM [1]. HLDA and MLDA set up lightpaths between the pairs of nodes based on only their traffic demand. In this paper, we propose two new algorithms: Single Hop-Free Logical Topology Design Algorithm (SHFLDA) and Single Hop-Constraint Logical Topology Design Algorithm (SHCLDA). They set up the lightpaths between the pairs of nodes based on the traffic demand and the hop count of the minimum hop route for these pairs of nodes. There is a comparison of four parameters: the total traffic volume on the logical topology, the maximum traffic volume on the established lightpaths, the total demand traffic volume and the percentage of used wavelengths in the network in SHFLDA and SHCLDA. Our simulation results indicate that SHFLDA is more effective than SHCLDA in the event that the scale of network is large. TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(39).2010 202 1. Đặt vấn đề Có nhiều kiến trúc trong mạng IP/WDM, chẳng hạn như kiến trúc mạng IP/WDM điểm nối điểm, cấu hình lại, và kiến trúc mạng IP/WDM chuyển mạch [1]. Trong đó, kiến trúc mạng IP/WDM cấu hình lại cũng được biết như kiến trúc mạng chuyển mạch kênh quang OCS (Optical Circuit Switching), là kiến trúc hứa hẹn nhất trong mạng truyền dẫn Internet đường trục [2]. Trong kiến trúc này, các kênh bước sóng, được gọi là các lightpath (đường quang), được cấu hình trong mạng ghép kênh phân chia theo bước sóng WDM (Wavelength Division Multiplexing) và lưu lượng IP được chuyển tải trên các lightpath [1]. Trong mạng IP/WDM, có ba mô hình liên mạng khác nhau: đồng đẳng, tăng cường và xếp chồng. Chúng tôi xây dựng hai thuật toán, mỗi thuật toán tạo một topologic bằng các đường quang (lightpath) như một mạng xếp chồng lên mạng vật lý WDM, mỗi một đường quang mang lưu lượng IP giữa các node trong kiến trúc mạng OCS. Như đã đề cập trong phần tóm tắt, hai thuật toán đề xuất khác với hai thuật toán HLDA và MLDA về tiêu chí để quyết định cặp node nào được chọn để xử lý trước. HLDA và MLDA không xem xét đến số chặng vật lý giữa các cặp node, và chỉ xem xét đến lưu lượng giữa các cặp node [3]. Trái lại, hai thuật toán đề xuất chọn cặp node để xử lý trước dựa trên cả số chặng vật lý giữa các cặp node và lưu lượng giữa các cặp node đó. Hai thuật toán đề xuất đạt được độ trễ trung bình thấp, giải quyết được vấn đề cân bằng tải nhờ vào cập nhật tích của yêu cầu lưu lượng và số chặng vật lý nhỏ nhất giữa các cặp node sau khi đường quang giữa chúng được thiết lập. Giả thiết rằng số bước sóng trên mỗi kết nối vật lý đều giống nhau. 2. Mô hình mạng Thiết kế và định tuyến trên topologic này dựa trên các giả thiết cho thông số ngõ vào như sau: -Tô pô vật lý cho trước gồm các node có các bộ phát và thu bước sóng, chúng kết nối với nhau bởi sợi quang. Giả sử số bước sóng là bằng nhau trên mỗi kết nối trực tiếp và không có sự chuyển đổi bước sóng tại các node. -Một node gồm có bộ định tuyến điện tử và bộ chuyển mạch quang như hình 1[4]. -Yêu cầu lưu lượng giữa các cặp node (i, j) đến theo tiến trình Poison và được tính theo Gbps và giả thiết luôn có yêu cầu lưu lượng giữa các cặp node. -Dung lượng truyền dẫn của mỗi bước sóng được thiết lập là 10Gbps. -Dung lượng xử lý của các bộ định tuyến điện tử luôn lớn hơn lượng lưu lượng đến tại bộ định tuyến đó. Bộ tách bước sóng (Wavelength Demux) tách các bước sóng từ tín hiệu quang sau đó chúng được chuyển mạch đến đầu ra tương ứng bởi bộ non-blocking switch mà không có sự chuyển đổi bước sóng. Các bước sóng này lại được ghép trở lại trên sợi quang và đi đến node cần đến. Tại các node đầu cuối của một đường quang, tín hiệu quang chuyển sang tín hiệu điện và đưa đến bộ định tuyến điện tử [5]. TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(39).2010 203 3. Đề xuất thuật toán SHFLDA và SHCLDA Thuật toán SHFLDA và SHCLDA chỉ thiết lập đường quang dùng cùng một bước sóng (gọi là đơn chặng) giữa mỗi cặp node nguồn đích, thay vì thiết lập đường quang sử dụng các bước sóng khác nhau giữa mỗi cặp node nguồn đích tại cùng một thời điểm. 3.1. Thuật toán SHFLDA Hình 1. Mô hình kiến trúc của node[5] N Y Y Kết thúc N Tìm cặp node có giá trị lớn nhất trong ma trận F Tìm đường đi vật lý ngắn nhất giữa cặp node đó . Số bước sóng trên các liên kết vật lý đã sử dụng giảm đi 1 khi lightpath giữa cặp node này được thiết lập. Tìm cặp node có giá trị lớn kế tiếp trong ma trận F và cập nhật ma trận F Tính số chặng vật lý nhỏ nhất của từng cặp node(i, j): hij Tạo ma trận F: Fij=qij*hij Các cặp node được xét hết? Gán giá trị của cặp node đó trong ma trận F bằng 0 Tồn tại bước sóng ? Bắt đầu Tô pô vật lý Số bước sóng trên mỗi liên kết vật lý: w Hình 2. Lưu đồ thuật toán thiết kế tô pô lô gic SHFLDA TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(39).2010 204 SHFLDA gán bước sóng sẵn có trên liên kết vật lý sử dụng cho đường quang đầu tiên được thiết lập. Thuật toán trả về topologic được tạo nên bởi các đường quang được thiết lập. Từ tô pô vật lý của mạng, ta có số chặng của đường đi vật lý giữa cặp node (i, j) chính là số kết nối trực tiếp từ node i đến node j gọi là hij. Từ ma trận yêu cầu lưu lượng của các bộ định tuyến ở các cặp node trong mạng cho trước, ta có giá trị qij là yêu cầu lưu lượng từ node i đến node j. Từ đó, ta lập ma trận F có giá trị các phần tử là Fij=qij * hij. Thuật toán SHFLDA chọn cặp node (i, j) sao cho có giá trị Fij lớn nhất để thiết lập đường quang và sử dụng độ trễ để xác định đường đi của nó. SHFLDA chọn đường đi từ node i đến node j sao cho độ trễ giữa chúng là nhỏ nhất bằng thuật toán tìm đường ngắn nhất Dijkstra. Thuật toán đề xuất này được đặt tên là SHFLDA là thuật toán thiết kế topologic đơn chặng vì nó thiết lập các đường quang đơn chặng, nghĩa là mỗi đường quang chỉ sử dụng một bước sóng có sẵn trên liên kết vật lý mà nó đi qua, chữ F (Free) trong SHFLDA ngụ ý việc bước sóng có sẵn được sử dụng trên mỗi liên kết vật lý khi có yêu cầu thiết lập đường quang; điều này khác với thuật toán đề xuất thứ hai: SHCLDA được trình bày như dưới đây. 3.2. Thuật toán SHCLDA Kết thúc Thiết lập các lightpath giữa các cặp node nối trực tiếp nhau Loại bước sóng đã sử dụng này ra khỏi các liên kết vật lý giữa các cặp node đó Thiết lập các lightpath giữa các cặp node còn lại như thuật toán SHFLDA Bắt đầu Chọn tô pô vật lý. Nhập số bước sóng trên mỗi liên kết vật lý. Nhập lưu lượng của từng cặp node(i, j): qij Tính số chặng vật lý từng cặp node(i, j): hij Tạo ma trận F trong đó : Fij=qij*hij Hình 3. Lưu đồ thuật toán thiết kế tô pô lô gic SHCLDA TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(39).2010 205 Thuật toán đề xuất thứ 2 được gọi là SHCLDA, trong đó C là “Constraint” nghĩa là thiết lập các lightpath giữa các cặp node nối trực tiếp trước, và sau đó thiết lập các lightpath giữa các cặp node còn lại tương tự như thuật toán SHFLDA. 4. Đánh giá kết quả 4.1. Mô hình mô phỏng và kết quả mô phỏng Các thuật toán HLDA và MLDA không được so sánh với các thuật toán đề xuất vì chúng không giống nhau về tiêu chí để quyết định cặp node nào được chọn để xử lý trước. Thực hiện thiết kế topologic với cùng các thông số ngõ vào sử dụng hai thuật toán SHFLDA và SHCLDA, tiến hành so sánh bốn thông số được đánh số 1, 2, 3, và 4 của hai thuật toán thể hiện qua đồ thị hình cột như hình 5. - Thông số 1: Tổng lưu lượng trên tô pô lô gic là tổng lưu lượng trên các đường quang sau khi thiết lập. - Thông số 2: Là tổng lưu lượng yêu cầu giữa các cặp node. - Thông số 3: Lưu lượng cực đại của trên các đường quang được thiết lập. - Thông số 4: Tỷ lệ phần trăm các bước sóng được sử dụng là tỷ số các bước sóng được sử dụng trên tổng số bước sóng trong toàn mạng. Trong đó, thông số 1, 2, và 3 được tính theo dơn vị là Gbps, thông số 4 được tính theo đơn vị %. (a) (b) (c) Hình 4. Tô pô vật lý mạng gồm (a) 4 node; (b) 9 node; (c) 14 node TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(39).2010 206 4.2. Nhận xét Ở hình 5(a) và 5(b), thuật toán SHFLDA hiệu quả hơn khi cho giá trị tổng lưu lượng trên topologic thấp hơn so với thuật toán SHCLDA. Điều này được giải thích là do số đường quang được thiết lập bởi SHFLDA để mang các lưu lượng có giá trị lớn giữa các cặp node không có kết nối trực tiếp giữa chúng nhiều hơn bởi SHCLDA vì SHFLDA ưu tiên chọn cặp node có giá trị Fij lớn nhất để xử lý trước. Trái lại SHCLDA ưu tiên chọn các cặp node có kết nối vật lý trực tiếp đề xử lý trước. Trái lại, ở hình 5(c), thuật toán SHFLDA ít hiệu quả hơn khi cho giá trị tổng lưu lượng trên topologic cao hơn so với thuật toán SHCLDA vì do giới hạn số bước sóng trên mỗi liên kết và số yêu (a) (b) (c) (d) Hình 5. So sánh bốn thông số của SHFLDA và SHCLA trong mạng gồm: + 4 node, 3 bước sóng trên mỗi kết nối vật lý + 9 node, 3 bước sóng trên mỗi kết nối vật lý + 14 node, 3 bước sóng trên mỗi kết nối vật lý + 14 node, 6 bước sóng trên mỗi kết nối vật lý TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(39).2010 207 cầu kết nối trong mạng tăng. Nhưng khi tăng số bước sóng trên mỗi kết nối vật lý lên 6 bước sóng (khác với trường hợp ở hình 5(c), chỉ có 3 bước sóng) thì kết quả ở hình 5(d) lại tương tự như ở hình 5(a) và (b). Tổng lưu lượng yêu cầu giữa các cặp node (thông số 2) luôn bằng nhau ở mọi trường hợp. Sở dĩ bài báo đưa thông số này vào mô phỏng để tăng độ tin cậy của các thông số khác vì ta so sánh hai thuật toán dựa trên cùng điều kiện tô pô mạng và yêu cầu lưu lượng. Lưu lượng cực đại trong số các lưu lượng khác trên các một đườn quang được thiết lập và tỷ lệ phần trăm các bước sóng được sử dụng ở thuật toán SHCLDA luôn cao hơn hoặc bằng so với trường hợp ở thuật toán SHCLDA (thông số 3). Điều này được giải thích là do SHCLDA luôn thiết lập các lightpath giữa các node kết nối trực tiếp nhau trước mà không xem xét đến giá trị Fij 5. Kết luận Thuật toán SHFLDA cho hiệu quả tốt về mặt tổng lưu lượng trên topologic hơn thuật toán SHCLDA khi quy mô mạng lớn và ngược lại. Quy mô mạng liên quan đến quan hệ giữa số yêu cầu kết nối của các cặp node và số bước sóng trên mỗi kết nối. Quy mô mạng lớn khi số bước sóng trên các kết nối vật lý là đủ hay thừa so với số yêu cầu kết nối và ngược lại. Trong mục tiêu phát triển đề tài, các tác giả sẽ tiếp tục bổ sung: nghiên cứu các phương pháp dự báo thống kê các luồng lưu lượng, nghiên cứu các phần mềm thực hiện kỹ thuật lưu lượng IP/WDM. TÀI LIỆU THAM KHẢO [1] Kevin H. Liu, “IP over WDM”, QOptics Inc, Oregon, USA, 2002. [2] M. Murata, “Challenges for the next–generation Internet and the role of IP over photonic networks”, IEICE Transaction on Communications, vol. E83-B, pp. 2153–2165, Oct. 2000. [3] Junichi Katou, Shin’ichi Arakawa, and Masayuki Murata, “A design method of logical topology for IP over WDM networks with stable routing”, ONDM 2001, February 2001. [4] Yukinobu Fukushi ma, Shin’ichi Arakawa, Masayuki Murata and Hideo Miyahara, “Design of Logical Topology for Minimizing the Number of Fiber Amplifiers”, Osaka University, Osaka 560-8531 Japan, 2002. [5] Yukinobu Fukushima, “Physical and Logical Design of Flexible and Scalable Wavelength-Routed Networks”, Depart ment of Information Networking Graduate School of Information Science and Technology Osaka University, January 2006.