Nghiên cứu một số giải pháp định tuyến trong tô-pô mạng liên kết hiệu năng cao và công cụ đánh giá. (Routing schemes for..

Nội dung tài liệu: Nghiên cứu một số giải pháp định tuyến trong tô-pô mạng liên kết hiệu năng cao và công cụ đánh giá. (Routing schemes for..

1. LỜI CAM ĐOAN Tôi xin cam đoan tất cả các nội dung trong luận án “Nghiên cứu một số giải pháp định tuyến trong tô-pô mạng liên kết hiệu năng cao và công cụ đánh giá” là công trình nghiên cứu của riêng tôi dưới sự hướng dẫn của tập thể hướng dẫn. Các số liệu, kết quả được trình bày trong luận án là trung thực và chưa từng được tác giả khác công bố trong bất kỳ công trình nào. Việc tham khảo các nguồn tài liệu đã được thực hiện trích dẫn và ghi nguồn tài liệu tham khảo theo quy định. Hà Nội, ngày tháng năm 2021 TẬP THỂ HƯỚNG DẪN NGHIÊN CỨU SINH PGS.TS NGUYỄN KHANH VĂN TS. PHẠM ĐĂNG HẢI KIỀU THÀNH CHUNG 1
2. LỜI CẢM ƠN Trước hết, tôi xin trân trọng cảm ơn Trường Đại học Bách Khoa Hà Nội, Phòng Đào tạo, Viện Công nghệ thông tin và Truyền thông, các thầy cô cùng các bạn, các thành viên trong Sedic-Lab, đã tạo điều kiện thuận lợi và đóng góp nhiều ý kiến quý báu giúp tôi hoàn thành bản luận án này. Đặc biệt, tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc đến hai Thầy hướng dẫn khoa học, PGS.TS. Nguyễn Khanh Văn và TS. Phạm Đăng Hải đã hết lòng hướng dẫn, giúp đỡ và tạo mọi điều kiện thuận lợi cho tôi trong suốt quá trình thực hiện luận án. Đồng thời, tôi xin cảm ơn PGS.TS Michihiro Koibuchi, TS. Ikki Fujiwara, TS. Trương Thảo Nguyên, National Institute of Informatics – Nhật Bản đã tạo điều kiện và giúp đỡ tôi trong quá trình học tập, nghiên cứu. Tôi xin cảm ơn gia đình và người thân đã luôn bên tôi, ủng hộ và động viên tôi trong suốt quá trình nghiên cứu. Tôi xin chân thành cảm ơn! Hà Nội, ngày tháng năm 2021 Nghiên cứu sinh Kiều Thành Chung 2
3. MỤC LỤC LỜI CAM ĐOAN 1 LỜI CẢM ƠN 2 DANH MỤC KÝ HIỆU VÀ CÁC TỪ VIẾT TẮT 5 DANH MỤC CÁC BẢNG 6 DANH MỤC HÌNH VẼ 7 MỞ ĐẦU 9 CHƯƠNG 1: TỔNG QUAN 14 1.1. Cơ sở lý thuyết 15 1.1.1. Tô-pô mạng (Network topology) 15 1.1.2. Giới thiệu giải thuật định tuyến 19 1.1.3. Hiệu năng mạng liên kết 24 1.1.4. Mô phỏng đánh giá hiệu năng mạng 29 1.2. Giới thiệu bài toán và các nghiên cứu liên quan 30 1.2.1. Bài toán nghiên cứu 30 1.2.2. Tình hình nghiên cứu 36 1.2.3. Các nghiên cứu liên quan 38 1.3. Tóm tắt chương 1 45 CHƯƠNG 2: ĐỊNH TUYẾN RÚT GỌN CHO MÔ HÌNH MẠNG NGẪU NHIÊN 46 2.1. Tô-pô mạng ngẫu nhiên và thuật toán định tuyến rút gọn 46 2.1.1. Tô-pô mạng ngẫu nhiên 46 2.1.2. Cơ chế định tuyến phân tán tra bảng 48 2.1.3. Thuật toán định tuyến rút gọn TZ [29] 48 2.2. Định tuyến khai thác các cầu nối giữa các vùng (CORRA) 50 2.2.1. Ý tưởng xây dựng thuật toán định tuyến CORRA 50 2.2.2. Xây dựng bảng định tuyến 52 2.2.3. Kỹ thuật địa chỉ hóa 54 2.2.4. Đánh giá lý thuyết 57 2.2.5. Đánh giá thực nghiệm 59 2.2.6. Kết luận và hướng phát triển 64 2.3. Định tuyến khai thác các nút đại diện và cơ chế tuyển chọn nút đại diện 64 2.3.1. Xây dựng phương thức lựa chọn nút đại diện dựa trên vị trí 66 2.3.2. Đánh giá thực nghiệm 70 2.3.3. Kết luận và hướng phát triển 74 2.4. Xây dựng cơ chế tuyển chọn nút đại diện 74 2.4.1. Tuyển chọn nút đại diện 74 2.4.2. Cơ chế tuyển chọn các nút đại diện 75 2.4.3. Thực nghiệm đánh giá cơ chế tuyển chọn nút đại diện 80 2.4.4. Kết luận và hướng phát triển của cơ chế tuyển chọn nút đại diện 83 2.5. Tóm tắt Chương 2. 83 CHƯƠNG 3: XÂY DỰNG CÔNG CỤ HỖ TRỢ ĐÁNH GIÁ HIỆU NĂNG MẠNG LIÊN KẾT 84 3.1. Kiến trúc tổng quan của công cụ mô phỏng SSiNET 85 3.1.1. Ý tưởng cơ bản của SSiNET 85 3
4. 3.1.2. Kiến trúc mô-đun chức năng và giao diện 87 3.1.3. Thiết kế chi tiết kỹ thuật 90 3.1.4. Thiết kế chi tiết các gói của công cụ phần mềm 93 3.1.5. Xây dựng cơ chế kỹ thuật 97 3.2. Đánh giá thực nghiệm 100 3.2.1. Đánh giá kích thước bảng định tuyến 100 3.2.2. Đánh giá độ trễ truyền tin 101 3.2.3. Đánh giá thời gian thực thi 102 3.2.4. So sánh kết quả đánh giá giữa SSiNET và Omnet++ 102 3.2.5. Đánh giá thông lượng và thông lượng cực đại 103 3.2.6. Đánh giá theo phương pháp xấp xỉ 105 3.3. Ứng dụng công cụ SSiNET trong việc xây dựng mô hình tô-pô lai cho các DC cỡ vừa, tiết kiệm chi phí và đáp ứng không gian mở 106 3.3.1. Kiến trúc Bus-RSN 107 3.3.2. Giải pháp định tuyến 111 3.3.3. Đánh giá bằng thực nghiệm 112 3.3.4. Kết luận giải pháp 120 3.4. Tóm tắt chương 3 120 KẾT LUẬN VÀ HƯỚNG NGHIÊN CỨU 122 4.1. Kết luận 122 4.2. Hướng phát triển nghiên cứu 123 DANH MỤC CÁC CÔNG TRÌNH CÔNG BỐ CỦA LUẬN ÁN 124 TÀI LIỆU THAM KHẢO 125 PHỤ LỤC 130 1. Định tuyến phân cấp đối với mạng ngẫu nhiên chuẩn tắc 130 1.1. HR-SW: Định tuyến phân cấp trên mô hình đồ thị thế giới nhỏ 130 1.2. Kỹ thuật địa chỉ trong định tuyến phân cấp 131 1.3. Thực thi định tuyến HR-SW 132 1.4. Đánh giá hiệu năng mạng 133 1.5. Kết luận 136 2. Các thuật toán trong định tuyến khai thác cầu nối 136 4
5. DANH MỤC KÝ HIỆU VÀ CÁC TỪ VIẾT TẮT STT Kí hiệu Nghĩa tiếng Anh Nghĩa tiếng Việt Trung bình chiều dài đường định 1 ARPL Average Routing Path Length tuyến Định tuyến rút gọn dựa trên các Compact Routing for RAndom liên kết ngẫu nhiên như là các cầu 2 CORRA inter-connection topologies nối giữa các vùng nút mạng ở xa nhau 3 DC Data Center Trung tâm dữ liệu 4 DES Discrete Event Simulation Mô phỏng các sự kiện rời rạc 5 DOR Dimension-Order Routing Định tuyến ưu tiên theo chiều Định tuyến rút gọn dựa trên các Geographic Landmark-based 6 GLCR nút đại diện cho mỗi vùng nút Compact Routing mạng 7 HPC High-performance Computing Tính toán hiệu năng cao Informatiom Communication Công nghệ Thông tin và Truyền 8 ICT Technology thông Chiều dài đường định tuyến lớn 9 MRPL Maximum Routing Path Length nhất (đường kính mạng) Network Structure and 10 NSC Cấu hình và cấu trúc mạng Configuration 11 RSN Random Shortcut Network Mạng ngẫu nhiên 12 RTS Routing Table Size Kích thước bảng định tuyến 13 SPR Shortest Path Routing Định tuyến đường ngắn nhất Tổ chức đánh giá xếp hạng hệ 14 TOP500 thống mạng máy tính hiện nay. 5
6. DANH MỤC CÁC BẢNG Bảng 2.1: Algo1-TZ: Lựa chọn nút đại diện của Thorup và Zwick 49 Bảng 2.2: Xây dựng bảng định tuyến – Routing Table Construction (RTC) 53 Bảng 2.3: Tổ chức bản ghi trong bảng định tuyến của thuật toán CORRA 55 Bảng 2.4: Algo.2- GLCR: Lựa chọn nút đại diện 67 Bảng 2.5: Tổng hợp một số khái niệm sử dụng trong giải pháp GLCR 68 Bảng 2.6: Algo.3-GLCR: Điều chỉnh lựa chọn nút đại diện – AdjustLandmarkSet 68 Bảng 2.7: Algo.4-GLCR: Lựa chọn nút đại diện – 푒푤푆 푙푒(푊, ) 70 Bảng 2.8: Algo.2-IJDST: Loại bỏ nút đại diện yếu 훼 − 퐿푆 76 Bảng 2.9: Algo.3-IJDST: Lựa chọn nút đại diện 훼 − 퐿푆 77 Bảng 2.10: Algo.4-IJDST: Lựa chọn nút đại diện 훽 − 퐿푆. 78 Bảng 3.1: Đường kính mạng theo tỉ lệ xấp xỉ 105 Bảng 3.2: Độ trễ trung bình toàn mạng theo tỉ lệ xấp xỉ 105 Bảng 3.3: Thời gian thực thi tính toán 106 Bảng 3.4: Algo.1-Bus-RSN: Xây dựng tô-pô Bus-RSN 108 Bảng 3.5: Định nghĩa một số kí hiệu được sử dụng 111 Bảng 3.6: Algo. 2-Bus-RSN: Thuật toán định tuyến HRA (alpha-1 HRA) 111 Bảng 3.7: Các ký hiệu trong các hình minh họa thực nghiệm 112 Bảng 3.8: Tổng cáp mạng trong trường hợp khoảng cách giữa các vùng khác nhau . 119 Bảng 5.1: Algo.5-GLCR: Tính toán ( ) trong giải pháp GLCR 136 Bảng 5.2: Algo.6-GLCR: Tính 푙 và 푒 ( 푙) cho mọi nút đại diện 푙 ∈ 퐿 137 6
7. DANH MỤC HÌNH VẼ Hình 1.1: Mạng liên kết (Interconnection Network) 15 Hình 1.2: Các ứng dụng trên mạng [6] 16 Hình 1.3: Các dạng tô-pô mạng cơ bản 17 Hình 1.4: Mạng trực tiếp và gián tiếp 19 Hình 1.5: Ví dụ về định tuyến trên mạng kết 2D-Torus [5] 20 Hình 1.6: Định tuyến thích ứng trên tô-pô RING 8-nút. 22 Hình 1.7: Ví dụ về tắc nghẽn của Wormhole switching 24 Hình 1.8: Độ trễ của một gói tin trên kênh truyền 26 Hình 1.9: Tương quan giữa băng thông và thông lượng 26 Hình 1.10: Tương quan giữa độ trễ và lưu lượng dữ liệu yêu cầu 27 Hình 1.11: Tương quan giữa thông lượng và lưu lượng dữ liệu yêu cầu 29 Hình 1. 12: Mô hình mô phỏng 30 Hình 1.13: Tổ chức bảng định tuyến tại nút mạng 34 Hình 2.1: Tô-pô cơ sở dạng lưới 47 Hình 2.2: Tạo tô-pô mạng ngẫu nhiên ′ từ tô-pô cơ sở dạng lưới 47 Hình 2.3: Cách tiếp cận định tuyến dựa trên nút đại diện của Thorup và Zwick 49 Hình 2.4: Xây dựng tô-pô ngẫu nhiên cho thuật toán CORRA 50 Hình 2.5: Hàng xóm gửi 푠 thông tin cầu 푖 푒1 của nó. 51 Hình 2.6: Nút 푠 lưu thông tin 푖 푒2 từ hàng xóm mà nằm trong khoảng 훿 của 푠 52 Hình 2.7: Ví dụ về việc xây dựng các bản ghi trong bảng định tuyến 55 Hình 2.8: Ví dụ về thực thi định tuyến thông qua nhãn và tọa độ nút mạng 56 Hình 2. 9: Thực thi định tuyến thông qua định danh nút mạng 57 Hình 2.10: Mô hình mở rộng, sử dụng -grid liên kết cơ bản 59 Hình 2.11: Tác động của giá trị 훿 đối với 푅 푆 60 Hình 2.12: Trung bình kích thước bảng định tuyến 60 Hình 2.13: Đánh giá đường kính mạng 61 Hình 2.14: Trung bình chiều dài đường định tuyến ( 푅푃퐿) 62 Hình 2.15: Trung bình độ trễ truyền tin 62 Hình 2.16: 푅푃퐿 của mạng có kích thước lớn 63 Hình 2.17: Trung bình độ trễ truyền tin đối với mạng kích thước lớn 63 Hình 2.18: Lựa chọn các nút đại diện không mong đợi trong thuật toán TZ [29] 65 Hình 2.19: Minh họa điều chỉnh vị trí các nút đại diện 69 Hình 2.20: Tương quan giữa 푅 푆 lớn nhất và kích thước lớn nhất 71 Hình 2.21: Khảo sát 푅 푆 tối đa đối với mỗi khích thước của tập các nút đại diện 72 Hình 2.22: Tương quan giữa 푅푃퐿 và kích thước cụm lớn nhất 72 Hình 2.23: Tương quan giữa 푅푃퐿 với 푅 푆 lớn nhất 73 Hình 2.24: So sánh 푅 푆 của GLCR với TZ-original trong mạng kích thước lớn 73 Hình 2.25: Phân bố các nút đại diện trong đồ thị dạng lưới 79 Hình 2.26: Tương quan giữa số lượng nút đại diện với kích thước cụm lớn nhất đối với mạng có 1.024 nút 80 Hình 2.27: Tương quan giữa kích thước mạng đối với 푖푛푅 푆 81 Hình 2.28: Tương quan giữa số lượng nút đại diện với kích thước lớn nhất của cụm trong mạng có kích thước lớn 81 Hình 2.29: Tương quan giữa số lượng nút đại diện với 푅푃퐿 83 7
8. Hình 3.1: Mô tả cấu trúc nút mạng 85 Hình 3.2: Sơ đồ thiết kế tổng quan 88 Hình 3.3: Lưu đồ tạo tô-pô mạng 90 Hình 3.4: Sơ đồ thiết kế chi tiết 91 Hình 3.5: Lưu đồ quyết định định tuyến 92 Hình 3.6: Thiết kế kỹ thuật chi tiết của SSiNET 92 Hình 3.7: Thiết kế lớp Graph, RoutingAlgorithm và TopoExperiment 93 Hình 3.8: Thiết kế gói graph và routing 94 Hình 3.9: Thiết kế các thành phần vật lý của mạng 95 Hình 3.10: Thiết kế nhóm thực nghiệm mô phỏng 96 Hình 3.11: Thiết kế các gói thực nghiệm mô phỏng zeroload và weightedload 96 Hình 3.12: Thiết kế lớp thực nghiệm đánh giá hiệu năng mạng dựa trên mô phỏng 97 Hình 3.13: Tiến trình hoạt động mô phỏng 97 Hình 3.14: Ví dụ về quản lý sự kiện rời rạc 98 Hình 3.15: Ví dụ về đường đi trên mạng có chiều dài m hop. 99 Hình 3.16: Tính toán kích thước bảng định tuyến 101 Hình 3.17: Độ trễ truyền tin trên mạng 102 Hình 3.18: So sánh thời gian thực thi giữa SSiNET và NS3 102 Hình 3.19: So sánh đánh giá thông lượng mạng giữa SSiNET và Omnet++ 103 Hình 3.20: Đánh giá thông lượng mạng bằng công cụ SSiNET 104 Hình 3.21: Thông lượng cực đại 104 Hình 3.22: (a)–Bus với 5 nút; (b)–RSN 4x4 tạo bởi liên kết lưới và liên kết ngẫu nhiên 107 Hình 3.23: Mô hình tô-pô Bus-RSN 107 Hình 3.24: Mô hình chi tiết của Bus-RSN 108 Hình 3.25: RSN được chia thành các khối, chọn nút trục và tạo đường trục 109 Hình 3.26: Chi tiết về nút thường và nút trục 110 Hình 3.27: Đánh giá tham số hiệu năng mạng theo kịch bản 1 114 Hình 3.28: Đánh giá tham số hiệu năng mạng theo kịch bản 2 116 Hình 3.29: Tổng chiều dài cáp và tổng chi phí triển khai kết nối theo kịch bản 1 117 Hình 3.30: Tổng chiều dài cáp và tổng chi phí triển khai kết nối theo kịch bản 2 119 Hình 5.1: Ví dụ của định tuyến HR-SW 131 Hình 5.2: Địa chỉ hóa phân cấp và bảng định tuyến 132 Hình 5.3: Tương quan giữa 푅푃퐿 và 푅 푆 trong mạng 4.096 nút 134 Hình 5.4: Tương quan giữa đường kính mạng và 푅 푆 trong mạng 4.096 nút 134 Hình 5.5: Đường kính mạng và 푅 푆 trong mạng 8.192 nút 135 Hình 5.6: 푅푃퐿 và 푅 푆 trong mạng 8.192 nút 136 8
9. MỞ ĐẦU Nghiên cứu tô-pô của các mạng liên kết là một chủ đề cơ bản, truyền thống trong lĩnh vực kiến trúc mạng máy tính, tính toán song song và các lưới tính toán. Thiết kế một giải pháp tô-pô hiệu quả sẽ đóng góp quyết định vào các kiến trúc mạng truyền tin lõi của các lưới tính toán lớn như các hệ máy tính hiệu năng cao, lưới điều khiển năng lượng thông minh hay các DC hiện đại với hàng nghìn nút tính toán. Một giải pháp tô-pô bao gồm hai yếu tố là cấu trúc tô-pô và giải thuật định tuyến. Cấu trúc tô-pô là cách sắp xếp các nút mạng (các thiết bị chuyển mạch, máy chủ) và các liên kết (cáp kết nối) giữa chúng được thể hiện dưới dạng đồ thị, trong đó, các nút mạng tương ứng với các đỉnh và các liên kết tương ứng với các cạnh trong đồ thị. Giải thuật định tuyến thể hiện phương thức hoạt động truyền tin được áp dụng trên cấu trúc tô-pô. Sau đây, NCS (nghiên cứu sinh) sẽ trình bày khảo sát khái quát và các định hướng nghiên cứu cụ thể. Nội dung khảo sát khái quát này có sử dụng tham khảo nhưng không được đề cập chi tiết, mà chúng sẽ được trình bày cụ thể trong các Chương sau. Trong thời kỳ xây dựng kiến trúc mạng truyền tin cơ sở trước đây, có nhiều cấu trúc tô-pô mạng cơ bản đã được đề xuất, ví dụ như De Bruijn, Starm Kautz. Chúng đã được sử dụng thành công và được áp dụng khá phổ biến trong các mạng có kích thước nhỏ (cỡ vài trăm nút tính toán). Tuy nhiên, với sự phát triển nhanh chóng về quy mô (số lượng các nút tính toán tăng cao) trong lĩnh vực thiết kế đa xử lý song song hay các lưới tính toán cũng như những đòi hỏi đặc biệt của các DC kiểu mới thì hầu hết các cấu trúc tô-pô truyền thống ít nhiều trở nên lạc hậu với hai vấn đề chính: 1) không đáp ứng được yêu cầu về độ trễ truyền tin thấp, thông lượng cao; 2) tính co giãn quy mô (scalability) và tính linh hoạt (flexibility), tức là sự thay đổi nhanh chóng (về số lượng) các nút tính toán. Cụ thể, việc thêm các nút tính toán để tăng quy mô hoặc công suất, hay bớt các nút để phục vụ bảo trì, sửa chữa hoặc tiết kiệm năng lượng (trong ngắn hạn), sẽ kéo theo các hoạt động cập nhật thay đổi hệ thống phức tạp và chi phí cao. Hạn chế đó có thể gây lãng phí, tạo thành lực cản đối với đà phát triển của các ứng dụng hiện đại. Với kích thước mạng ngày càng tăng, tính mềm dẻo đòi hỏi cao thì các vấn đề như tiết kiệm chi phí thiết bị và cáp kết nối, tiết kiệm năng lượng khi tải thấp, trở thành những chủ đề đáng quan tâm. Các nhà nghiên cứu tích cực đề xuất những dạng kiến trúc mới phù hợp hơn cho các yêu cầu hiện đại như SmallWorld DC, Fat-Tree, JellyFish, Ví dụ, Fat-Tree, được xem là một trong những mô hình hiệu quả đối với DC có kích thước lớn. Mặc dù Fat-Tree có nhiều ưu điểm như đường kính mạng thấp, độ trễ truyền tin thấp, định tuyến đơn giản nhưng nó cũng tồn tại một số hạn chế đáng kể. Như đã đề cập trước đó, khả năng mở rộng của Fat-Tree bị hạn chế bởi sự phụ thuộc vào số cổng thiết bị switch được sử dụng. Ví dụ, khi muốn mở rộng Fat-Tree, phải tiến hành thay thế các thiết bị switch đã được lắp đặt trước đó, việc này làm gia tăng chi phí thiết bị và sự dư thừa (trong trường hợp chỉ bổ sung thêm một vài máy chủ, nhưng phải thay thế các thiết bị switch để đảm bảo cấu trúc chặt chẽ của Fat-Tree). Đồng thời, với cấu trúc cây đặc thù, Fat-Tree phải sử dụng thiết bị chuyển mạch (chuyên dụng) có bậc đỉnh cao (tương ứng với số cổng kết nối) có giá thành cao. 9
10. Một cách tiếp cận mới và hấp dẫn gần đây là sử dụng các mô hình mạng ngẫu nhiên trong việc thiết kế các tô-pô mạng liên kết mà có thể đáp ứng được chất lượng hiệu năng quan trọng như là tính linh hoạt, tính mở rộng tự nhiên. Tô-pô mạng ngẫu nhiên được xây dựng bằng việc bổ sung thêm các liên kết ngẫu nhiên đối với một đồ thị cơ bản và chuẩn tắc như dạng lưới 2-D hoặc 3-D. Các liên kết ngẫu nhiên được tạo bởi một phân bố xác suất nào đó, nhưng thường là phân bố đều. Ví dụ, mô hình mạng ngẫu nhiên RSN (Random Shortcut Network) được tạo ra bởi việc bổ sung các liên kết ngẫu nhiên giữa các nút mạng trên đồ thị cơ sở dạng lưới. Mô hình mạng ngẫu nhiên có thể đạt được đường kính mạng và độ trễ giảm đáng kể so với các tô-pô mạng truyền thống (khi so sánh chúng với cùng kích thước và cùng bậc đỉnh). Hơn nữa, các tô-pô mạng ngẫu nhiên có khả năng mở rộng tự nhiên (có thể thêm hoặc bớt máy chủ nhưng không ảnh hưởng lớn đến cấu trúc toàn mạng), ví dụ JellyFish. Khả năng mở rộng tự nhiên nhằm hạn chế sự cứng nhắc của các cấu trúc tô- pô chuẩn tắc như đã đề cập trên. Mặc dù có sự hấp dẫn về sự gia tăng mở rộng tự nhiên, mô hình mạng ngẫu nhiên cũng tồn tại các hạn chế quan trọng, bao gồm sự giới hạn tính co giãn trong việc định tuyến. Việc tạo ra các liên kết ngẫu nhiên bởi một phân bố xác suất nào đó dẫn đến khó khăn lớn trong việc xây dựng các giải thuật định tuyến. Bởi yếu tố ngẫu nhiên phá vỡ các quy luật định tuyến thông thường như DOR hoặc giao thức Duato, hoặc theo thuật toán đường đi ngắn nhất với việc sử dụng thông tin toàn bộ tô-pô được lưu trữ trong bảng định tuyến tại mỗi nút mạng. Đây chính là hạn chế lớn của cách tiếp cận tô-pô mạng ngẫu nhiên và nó trở thành điểm nghẽn khi số nút mạng tăng cao, do sự giới hạn về bộ nhớ vật lý tại mỗi nút mạng. Ví dụ, tô-pô JellyFish trở nên kém co giãn khi kích thước mạng tăng cao và phải sử dụng các thiết bị chuyển mạch có bậc đỉnh lớn (bậc đỉnh 48). Do đó, vấn đề là làm thế nào để xây dựng giải pháp định tuyến hiệu quả mà sử dụng ít thông tin định tuyến lưu trữ tại các nút mạng cho mạng ngẫu nhiên có kích thước lớn, và hướng tới việc sử dụng các thiết bị chuyển mạch có bậc đỉnh thấp. Bên cạnh việc tìm kiếm giải pháp tô-pô mới, một trong những thách thức lớn của địa hạt nghiên cứu này là làm sao tổ chức đánh giá qua thực nghiệm với một mô hình mạng kích thước lớn, có thể vượt xa các kích thước mạng truyền thống. Việc đánh giá một tô-pô mạng liên kết được thực hiện bởi hai giai đoạn: đánh giá bằng phân tích đồ thị và đánh giá bằng thực nghiệm mô phỏng. Đánh giá bằng phân tích đồ thị được sử dụng để tính toán các yếu tố đồ thị như khoảng cách giữa các nút mạng, sự liên kết của các nút mạng để tính toán các tham số hiệu năng (tĩnh). Đánh giá bằng thực nghiệm thông qua các công cụ mô phỏng thực hiện giả lập quá trình truyền tin để tính toán các tham số động như là thông lượng hay độ trễ. Một vấn đề quan trọng trong việc kiểm chứng một đề xuất giải pháp tô-pô mới là làm thế nào để tính toán, đánh giá hiệu năng của nó. Đối với các tô-pô mạng chuẩn tắc, việc tính toán các tham số hiệu năng khá dễ dàng do tính cấu trúc chặt chẽ của nó và chỉ cần thực hiện một lần. Tuy nhiên, đối với các tô-pô mạng ngẫu nhiên, việc đánh giá hiệu năng trở nên khó khăn do tính chất ngẫu nhiên của các liên kết. Với mỗi sự thay đổi cấu 10
11. trúc của giải pháp tô-pô mạng ngẫu nhiên, các nhà khoa học phải tiến hành thực nghiệm nhiều lần và sử dụng kết quả trung bình để đánh giá hiệu năng. Ví dụ, tính trung bình chiều dài đường định tuyến, tức là phải tính toán chiều dài đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị. Hoạt động này tiêu tốn tài nguyên máy tính toán rất lớn, và chưa có công cụ phần mềm nào có thể thực hiện đối với mạng có kích thước lớn. Ngoài ra, như đã đề cập, do tính chất ngẫu nhiên, nên với mỗi giải pháp tô-pô cần phải tiến hành tính toán lại các tham số hiệu năng đối với mỗi mẫu tô-pô ngẫu nhiên mới (ví dụ, đường đi giữa các cặp đỉnh) để xây dựng thông tin định tuyến. Do đó, cần xây dựng một công cụ phần mềm có cơ chế tính toán các tham số hiệu năng sao cho có thể đáp ứng được việc đánh giá mạng ngẫu nhiên kích thước lớn. Đồng thời, thông qua tiếp cận mới này, chúng ta có thể đánh giá một đề xuất tô-pô mới bằng việc so sánh với các giải pháp đã có trên những cấu hình mạng kích thước lớn mà trước kia chưa thể thực hiện được. Từ những khảo sát trình bày trên, NCS hướng tới hai mục tiêu chính như sau: Mục tiêu 1: nghiên cứu và đề xuất các thuật toán định tuyến rút gọn mà có thể khai thác tốt các tính chất của tô-pô mạng ngẫu nhiên có kích thước lớn, phù hợp với các DC hiện nay. Mục tiêu 2: nghiên cứu và đề xuất kiến trúc công cụ mô phỏng đánh giá hiệu năng mạng ngẫu nhiên có kích thước lớn. Để cụ thể hóa được các mục tiêu trên, NCS đã tiến hành khảo sát các cơ sở lý thuyết liên quan như cấu trúc tô-pô mạng, các nguyên lý định tuyến gói tin trong mạng, hệ thống hóa các nghiên cứu liên quan để làm cơ sở lý thuyết. Trên các cơ sở lý thuyết, NCS phân tích, khái quát hóa những vấn đề xây dựng thuật toán định tuyến mới, đồng thời tiến hành so sánh hiệu năng tô-pô mạng của các nghiên cứu liên quan bao gồm các yếu tố hiệu năng, mối liên quan và sự đánh đổi giữa các yếu tố hiệu năng. Các kết quả được thực nghiệm bởi hai phương pháp để đánh giá hiệu năng, bao gồm phương pháp phân tích đồ thị và phương pháp mô phỏng giả lập được thiết lập trong công cụ phần mềm mô phỏng. Công cụ hỗ trợ mô phỏng đánh giá sẽ tính toán các tham số hiệu năng như đường kính mạng (diameter), độ trễ truyền tin lý tưởng, trung bình chiều dài đường định tuyến ( 푅푃퐿) và kích thước bảng định tuyến (푅 푆) tương ứng với mỗi tô-pô thực nghiệm. Phương pháp mô phỏng giả lập được sử dụng để mô phỏng quá trình truyền tin giữa các cặp nguồn đích trong mạng. Các gói tin được tạo ra, truyền qua mạng, được công cụ mô phỏng ghi nhận lại các hoạt động đó và đưa ra các tham số cần thiết như là độ trễ truyền tin và thông lượng mạng. Công cụ hỗ trợ mô phỏng được kiểm chứng tính đúng đắn bằng việc cài đặt các tô-pô mạng và thuật toán định tuyến tương ứng đã được công bố, tiến hành thực nghiệm theo hai phương pháp trên và so sánh với kết quả thu được với các kết quả đã công bố. Đồng thời, thực nghiệm với các tô-pô mạng và thuật toán mới tương ứng để tìm ra thiết kế có hiệu năng mạng tốt hơn. NCS đã phân tích và hệ thống hóa các thiết kế tô-pô mạng cơ bản truyền thống và các thuật toán định tuyến tương ứng. Từ những phân tích đó, NCS đã góp phần bổ 11
12. sung làm phong phú cơ sở lý luận khoa học trong việc đưa ra các giải pháp cho việc thiết kế tô-pô mạng, thuật toán định tuyến, phù hợp với sự phát triển lớn mạnh của các DC hiện đại có kích thước ngày càng tăng như hiện nay. Các kết quả nghiên cứu đã góp phần xây dựng thiết kế các thuật toán định tuyến, kiến trúc phần mềm công cụ hỗ trợ đánh giá hiệu năng mạng nhằm tăng cường tìm kiếm các giải pháp thiết kế tô-pô mạng mới cũng như là thuật toán định tuyến mới trong tương lai. Đối với lĩnh vực thiết kế thuật toán định tuyến, NCS đã đóng góp 04 công trình nghiên cứu. Đối với lĩnh vực xây dựng phần mềm hỗ trợ mô phỏng đánh giá thực nghiệm, NCS đã đóng góp 02 công trình trên Chuyên san các công trình nghiên cứu phát triển công nghệ thông tin và truyền thông. Dự án nghiên cứu vẫn đang được tiếp tục phát triển và mở rộng các nhánh nghiên cứu chuyên biệt. Đối với cộng đồng nghiên cứu khoa học, các kết quả nghiên cứu sẽ cung cấp thêm nguồn tài liệu tham khảo, các khảo sát hữu ích nhằm phục vụ nghiên cứu và đề xuất các giải pháp thiết kế tô-pô mạng hiệu quả trong tương lai. Kết quả nghiên cứu là tài liệu có giá trị tham khảo đối với các tổ chức, doanh nghiệp xây dựng, triển khai các DC cỡ vừa và nhỏ tại Việt nam như các tổ chức ngân hàng, các DC ngành (Bộ, Ban, tổ chức xã hội). Ngoài ra, kết quả nghiên cứu này cũng có giá trị tham khảo đối với các doanh nghiệp chuyên biệt về tổ chức xây dựng và vận hành các DC hiện đại như Viettel DC, FPT DC, VTC DC, VNPT DC, EVN DC, Trong quá trình thực hiện các nhiệm vụ của các đề tài nghiên cứu khoa học, tại phòng thí nghiệm SedicLab – Viện Công nghệ Thông tin và Truyền thông, Đại học Bách Khoa Hà Nội, dưới sự hướng dẫn của tập thể hướng dẫn và các thành viên nghiên cứu, nhóm nghiên cứu đã hình thành công cụ mô phỏng giả lập truyền tin, SSiNET, được triển khai phục vụ nghiên cứu tại phòng thí nghiệm. Công cụ mô phỏng này hiện nay đang được hoàn thiện, mở rộng thêm các chức năng và các phương thức thực nghiệm, tiến tới công bố rộng rãi trên Internet, hỗ trợ cho các nhà nghiên cứu khác trong cùng lĩnh vực. NCS đã có đóng góp trong định hướng nghiên cứu chung của phòng thí nghiệm. Sau đây, NCS xin trình bày những đóng góp chính với sự đồng ý của tập thể hướng dẫn và các thành viên nhóm nghiên cứu. Những đóng góp mới của nghiên cứu bao gồm hai nội dung chính: (i) Đề xuất giải thuật định tuyến mới + Định tuyến rút gọn (Compact Routing) dựa trên các liên kết ngẫu nhiên như là các cầu nối giữa các vùng nút mạng ở xa nhau (CORRA: CT2). + Định tuyến rút gọn dựa trên các nút đại diện cho mỗi vùng nút mạng (GLCR: CT3), có điều chỉnh phương thức tuyển chọn các nút đại diện (IJDST: CT5). (ii) Đề xuất công cụ thực nghiệm mô phỏng đánh giá hiệu năng mạng: + Xây dựng kiến trúc hệ thống của công cụ phần mềm SSiNET (CT4), thực hiện giả lập cơ chế truyền tin trong mạng. + Ứng dụng công cụ phần mềm để đề xuất mô hình tô-pô lai cho các DC cỡ vừa, tiết kiệm chi phí và đáp ứng không gian mở phù hợp với điều kiện thực tiễn tại Việt Nam (CT6). 12
13. Các đề xuất trong quá trình nghiên cứu và các kết quả nghiên cứu được trình bày trong luận án theo cấu trúc như sau: Trong chương 1, NCS trình bày tổng quan các vấn đề chính, bao gồm: . Tổng quan về tô-pô mạng, các thành phần cơ bản cấu thành tô-pô mạng, thuật toán định tuyến và các yếu tố hiệu năng mạng. . Tình hình nghiên cứu và các nghiên cứu liên quan về thiết kế tô-pô và các thuật toán định tuyến trên thế giới và trong nước. . Nghiên cứu, khảo sát đánh giá thực nghiệm mô phỏng truyền tin trên mạng; Tổng quan về phương pháp và công cụ hỗ trợ mô phỏng đánh giá hiệu năng mạng: các công cụ như NS2 [1], NS3 [2], Simgrid [3], Omnet++ [4],. Trong chương 2, NCS trình bày bài toán nghiên cứu thứ nhất thông qua việc đề xuất phương pháp truyền tin giữa các cặp nguồn – đích trong tô-pô mạng bằng các giải pháp định tuyến rút gọn. Trong đó, bao gồm các nội dung chính như sau: . Tổng quan về phương pháp định tuyến rút gọn và các nghiên cứu liên quan. . Định tuyến theo mô hình phân cấp (Hierarchical Routing). . Định tuyến khai thác thông tin cầu trong vùng hàng xóm của các nút nguồn (CORRA); . Định tuyến khai thác thông tin cầu, có lựa chọn điều chỉnh đồng đều vị trí các nút đại diện (landmark set) (GLCR). Trong chương 3, NCS trình bày về phương pháp giải quyết bài toán về việc thiết kế xây dựng phần mềm hỗ trợ mô phỏng thực nghiệm SSiNET và ứng dụng công cụ phần mềm trong việc đề xuất giải pháp thiết kế tô-pô mạng mới Bus-RSN nhằm giải quyết bài toán xây dựng DC cỡ vừa và nhỏ phù hợp với điều kiện thực tế tại các doanh nghiệp ở Việt Nam. Nội dung trình bày bao gồm các nội dung chính như sau: . Mô hình, phương pháp mô phỏng giản lược. . Phân tích các yêu cầu của công cụ mô phỏng. . Kiến trúc tổng quan của công cụ mô phỏng SSiNET. . Giới thiệu thiết kế chi tiết kỹ thuật và thiết kế chi tiết các gói của công cụ mô phỏng đánh giá hiệu năng của tô-pô mạng . Mô phỏng quá trình truyền tin và đánh giá thực nghiệm bởi SSiNET. . Xây dựng đề xuất giải pháp triển khai tô-pô mạng lai mô phỏng điều kiện thực tiễn và thực nghiệm đánh giá bởi công cụ SSiNET. Kết luận và hướng phát triển: trình bày tổng hợp các đề xuất và hướng phát trong lĩnh vực nghiên cứu tô-pô mang và thuật toán định tuyến. 13
14. CHƯƠNG 1: TỔNG QUAN Mục tiêu chính của luận án là đề xuất giải pháp định tuyến và đề xuất công cụ mô phỏng đánh giá hiệu năng mạng ngẫu nhiên có kích thước lớn. Do vậy, trong Chương này, NCS trình bày hai bài toán nghiên cứu nhằm đáp ứng mục tiêu đó, tương ứng. Trước hết, giới thiệu tổng quan cấu trúc tổ chức của các mạng và các nghiên cứu liên quan đến quá trình xác định đường đi của các gói tin giữa các cặp nguồn – đích trong mạng (mục 1.1). Đây là nội dung cơ bản để cung cấp cho người đọc những khái niệm mang tính cơ sở và những tham số hiệu năng mạng được sử dụng trong việc xây dựng bài toán nghiên cứu. Trong mục 1.2, NCS giới thiệu hai bài toán nghiên cứu: i) bài toán định tuyến rút gọn (compact routing) cho tô-pô mạng ngẫu nhiên tựa đồ thị lưới; ii) xây dựng kiến trúc công cụ mô phỏng giả lập hỗ trợ đánh giá hiệu năng mạng liên kết. Trong nội dung này, các bài toán mới chỉ được phát biểu hình thức, do đó, trong chương 2 và chương 3, NCS trình bày chi tiết nội dung và kết quả đạt được của các bài toán nghiên cứu tương ứng. Để giải quyết bài toán thứ nhất, NCS đã đề xuất hai giải pháp định tuyến là CORRA và GLCR, đối với tô-pô mạng ngẫu nhiên có kích thước lớn, nội dung chi tiết được trình bày trong Chương 2. Giải pháp thứ nhất khai phá ý tưởng mới và phát triển kịch bản định tuyến rút gọn, gọi là CORRA (Compact Routing for RAndom inter- connection topologies). CORRA khai thác các tính chất mô hình ngẫu nhiên, làm cho chiều dài định tuyến gần đạt tối ưu (ngắn hơn các kịch bản định tuyến rút gọn phổ quát) nhưng vẫn đảm bảo 푅 푆 nhỏ. Cụ thể, thuật toán định tuyến CORRA khám phá cách sử dụng các cầu nối giữa các vùng hàng xóm riêng biệt. CORRA có thể đạt được 푅푃퐿 dài hơn không đáng kể nhưng vẫn đảm bảo 푅 푆 nhỏ hơn rất nhiều khi so sánh với thuật toán SPR, và đủ nhỏ để cho phép kích thước mạng tăng lên hàng trăm nghìn nút. Giải pháp định tuyến thứ hai, được gọi là GLCR, là thuật toán định tuyến rút gọn khai thác yếu tố địa lý của các nút đại diện. Đề xuất này cải tiến kịch bản định tuyến phổ quát TZ bằng việc đưa ra kỹ thuật lựa chọn nút đại diện mới. Trong kỹ thuật đó, các nút đại diện được chọn rời xa các nút đại diện khác sao cho chúng được phân bố đều trên toàn mạng. Các kết quả thực nghiệm cho thấy, GLCR đạt được RTS nhỏ hơn, đặc biệt nhỏ hơn đáng kể với kích thước mạng lên tới 100.000 nút, khi so sánh với TZ. Bài toán thứ hai giới thiệu thiết kế tổng thể công cụ đánh giá hiệu năng mạng, gọi là SSiNET và được trình bày chi tiết trong Chương 3. Công cụ này hỗ trợ thực nghiệm cho các giải pháp định tuyến nêu trên. SSiNET cho phép người sử dụng có thể tạo ra các tô-pô mạng mới, thử nghiệm với các thuật toán định tuyến có sẵn (hoặc cài đặt mới). SSiNET cũng được cài đặt phương thức xấp xỉ để người sử dụng có thể thực nghiệm với tô-pô mạng kích thước lớn. Công cụ này cho phép đánh giá và so sánh các tô-pô có kích thước lớn trên các phương diện truyền thống như các đặc tính đồ thị và định tuyến và đặc tính khai thác có tải. Ngoài ra, SSiNET cho phép các nhà nghiên cứu thử nghiệm các thiết kế tô-pô mới một cách đa dạng và linh hoạt mà không phải phát triển chương trình riêng để cài đặt các tô-pô hoặc thuật toán định tuyến có sẵn Ứng dụng công cụ SSiNET để thực nghiệm và đề xuất mô hình tô-pô lai Bus- RSN nhằm giải quyết bài toán xây dựng DC của các doanh nghiệp nhỏ và vừa. Giải pháp 14
15. thiết kế hướng tiết giảm chi phí và triển khai linh hoạt, có thể lắp đặt trong không gian gồm nhiều phòng/sàn phân biệt. Đồng thời, chi phí đầu tư ban đầu để xây dựng DC theo mô hình này phù hợp với các doanh nghiệp có nguồn vốn hạn hẹp. Tính linh hoạt trong khả năng mở rộng giúp doanh nghiệp có thể mở rộng hoặc co hẹp DC một cách dễ dàng. 1.1. Cơ sở lý thuyết 1.1.1. Tô-pô mạng (Network topology) 1.1.1.1. Giới thiệu mạng liên kết Mạng liên kết (Interconnection Network) là một hệ thống các thiết bị (ví dụ máy chủ, thiết bị chuyển mạch switch) được kết nối với nhau, có thể lập trình được và được sử dụng để vận chuyển dữ liệu giữa các thiết bị đầu cuối [5]. Hình 1.1 mô tả mạng liên kết ở mức cao. Trong đó, các thiết bị đầu cuối (kí hiệu từ 1 đến 5) kết nối với mạng liên kết thông qua các kết nối. Các mũi tên biểu diễn kết nối có hai chiều thể hiện khả năng vận chuyển dữ liệu vào và ra mạng liên kết. Khi thiết bị đầu cuối 1 trao đổi dữ liệu với 5, nó gửi một gói tin chứa dữ liệu đến mạng liên kết, quá trình chuyển tiếp các gói tin được diễn ra trên mạng liên kết để đưa gói tin tới 5. TB1 TB2 TB3 TB4 TB5 Interconnection Network Hình 1.1: Mạng liên kết (Interconnection Network) Mạng liên kết được ứng dụng rộng rãi trong các hệ thống máy tính và các hệ thống chuyển mạch thông tin liên lạc. Đặc biệt, mạng liên kết được thiết kế để sử dụng ở các mức độ khác nhau trong các hệ thống máy tính nhằm đáp ứng nhu cầu của các nhóm ứng dụng khác nhau như: tính toán hiệu năng cao, lưu trữ vào ra (storage I/O), các hệ thống cluster/workgroup Mạng liên kết được chia ra làm bốn lĩnh vực ứng dụng chính [6]: On-chip networks (OCNs) hay còn được nhắc tới với thuật ngữ network-on-chip (NoC): được sử dụng để kết nối bên trong các vi kiến trúc giữa các đơn vị chức năng, thanh ghi (register), bộ lưu trữ trung gian (caches), các bộ vi xử lý (processor) trong các mô đun đa chip. Hiện nay, OCNs hỗ trợ các kết nối giữa vài chục thiết bị đặt trong các vi mạch với khoảng cách tối đa khoảng vài centimets. System/storage area networks (SANs): Đây là mạng liên kết được sử dụng để kết nối các bộ vi xử lý liên kết (interprocessor) và các bộ nhớ (processor-memory) trong các hệ thống đa nhân và hệ thống đa máy tính (multicomputer). Ngoài ra SANs cũng được sử dụng để kết nối các thành phần lưu trữ và thành phần xử lý vào ra trong môi trường gồm các máy chủ và các DC. Số lượng thiết bị được kết nối trong SANs có thể lên tới hàng nghìn thiết bị khác nhau phân bố với khách cách khoảng vài trăm mét. 15
16. Hình 1.2: Các ứng dụng trên mạng [6] Local area networks (LANs): Đây của mạng liên kết được sử dụng để kết nối hệ thống máy tính cá nhân. Ban đầu, các mạng LAN chỉ kết nối hàng trăm thiết bị, nhưng với cầu nối (bridges), mạng LAN có thể kết nối lên đến vài nghìn thiết bị. Khoảng cách kết nối tối đa bao phủ khu vực có đường kính một vài kilomet, cho đến vài chục kilomet. Wide area networks (WANs): WANs kết nối các hệ thống máy tính phân bố phân tán trên toàn thế giới với hàng triệu máy tính trên khoảng cách lớn. Hình 1.2 ( [6]) minh họa mối quan hệ giữa các lĩnh vực ứng dụng của mạng liên kết với số lượng thiết bị (được biểu diễn bởi trục ngang) được kết nối trong mạng cũng như khoảng cách giữa chúng (biểu diễn bởi trục dọc). NCS tập trung cho các mạng liên kết ứng dụng trong lĩnh vực SANs. Đặc biệt, các vấn đề liên quan đến mạng liên kết phục vụ tính toán hiệu năng cao, và DC. 1.1.1.2. Cấu trúc mạng liên kết Cấu trúc mạng1 hay còn gọi là tô-pô mạng là mẫu thiết kế thể hiện sự sắp đặt các nút mạng và các kết nối giữa các nút mạng với nhau hay được hiểu là một phương pháp sắp xếp các kênh truyền và nút mạng. Trong mỗi ứng dụng cụ thể, quá trình lựa chọn cấu trúc mạng là rất quan trọng, bởi đây là yếu tố liên quan trực tiếp đến cài đặt chi tiết. Cấu trúc mạng ảnh hưởng tới thông số kĩ thuật của bộ chuyển tiếp trung gian như số cổng kết nối, tốc độ truyền tin cần thiết. Cấu trúc mạng ảnh hưởng tới chi phí của và quyết định đến quá trình định tuyến. Mỗi mẫu kết nối giữa nút mạng yêu cầu các thuật toán định tuyến riêng biệt nhằm đảm bảo hiệu năng của mạng liên kết. Tóm lại, cấu trúc mạng được chọn sử dụng dựa trên chi phí và hiệu năng của nó. Có rất nhiều loại cấu trúc mạng đuợc thiết kế và ứng dụng trong thực tế. Một cách tổng quát, có năm loại cơ bản sau: Tô-pô mạng dạng (Bus): các nút mạng kết nối với nhau thông qua chia sẻ một kênh truyền dùng chung (Hình 1.3-Bus). Bus là cách kết nối các nút mạng đơn giản nhất, dễ cài đặt và mở rộng. Bus tiêu tốn ít dây nối nên rẻ hơn các cấu hình mạng khác. Tuy nhiên sử dụng Bus phải quan tâm đến vấn đề điều khiển luồng khi mà hai nút mạng muốn 1 Cấu trúc hình học thể hiện sự kết nối của các thiết bị trong mạng 16
17. truyền tin tại cùng một thời điểm trên cùng một đường Bus. Tóm lại, Bus chỉ phù hợp sử dụng cho những mạng liên kết nhỏ và không yêu cầu tốc độ cao. RING Fully STAR Connected LINE MESH TREE BUS Hình 1.3: Các dạng tô-pô mạng cơ bản Tô-pô mạng hình sao (Star): cấu hình mạng dạng sao bao gồm một nút mạng trung tâm đóng vai trò như cầu nối để chuyển tiếp dữ liệu (Hình 1.3-Star). Star cũng dễ dàng mở rộng quy mô bằng cách nâng cao số kết nối của nút mạng trung tâm. Nhược điểm của Star là bị phụ thuộc vào khả năng, cấu hình phần cứng của nút mạng trung tâm. Tô-pô mạng dạng hình tròn (Ring): hay còn gọi là mạng hình tròn, trong đó mỗi một nút liên kết trực tiếp với đúng hai nút mạng liền kề tạo thành một vòng tròn khép kín (Hình 1.3-Ring). Trong Ring không có nút mạng trung tâm, mọi nút mạng là bình đẳng. Tuy nhiên Ring dễ gặp vấn đề khi một nút mạng xảy ra sự cố. Thêm nữa, việc thêm, bớt hay bảo trì một nút mạng cũng có thể ảnh hưởng đến sự hoạt động của mạng. Tô-pô mạng dạng lưới (Mesh): Hình 1.3-Mesh, trong đó một nút mạng liên kết trực tiếp với các nút mạng khác theo dạng lưới. Mesh được sử dụng rộng rãi trong các mạng truyền thống nhờ tính chất đơn giản của cấu hình mạng và dễ định tuyến [7]. Tô-pô mạng dạng cây (Tree): Mạng hình cây là sự kết hợp của bus và star (Hình 1.3-Tree). Dựa vào đó, những cấu hình mạng như là -ary 푛-dimensional mesh hoặc là -ary 푛-dimensional torus đã được thiết kế và phát triển [7]. 1.1.1.3. Các thành phần trong mạng liên kết Để đáp ứng được các yêu cầu của từng lĩnh vực ứng dụng cụ thể (ví dụ như độ trễ truyền tin hay chi phí), mạng liên kết được xây dựng thông qua việc cân nhắc các ràng buộc kĩ thuật nhằm cài đặt ba yếu tố cấu hình mạng (topology), định tuyến (routing) và điều khiển luồng (flow control). Trong hầu hết các ứng dụng, thay vì các thiết bị đầu cuối được kết nối với nhau từng đôi một, mạng liên kết được cài đặt dưới dạng một nhóm các bộ chuyển tiếp trung gian (router) dùng chung kết nối thông qua các kênh truyền. Các thiết bị đầu cuối, bộ chuyển tiếp trung gian được gọi là nút mạng (network node). Các gói tin được truyền giữa các thiết bị đầu cuối bằng cách chúng được chuyển tiếp một vài lần thông qua các kênh truyền dùng chung và bộ chuyển tiếp trung gian từ nguồn tới đích. Định tuyến là quá trình lựa chọn và chỉ ra con đường nào sẽ được chọn để gói tin truyền theo. Quá trình định tuyến cần ưu tiên lựa chọn những con đường ngắn 17
18. nhất trong khi vẫn đảm bảo được yêu cầu cân bằng tài nguyên dùng chung trên mạng (bộ chuyển tiếp, kênh truyền). Độ dài của đường đi liên quan tới độ trễ (latency) truyền tin của mạng, trong khi tải (load) thể hiện khối lượng sử dụng của một tài nguyên cụ thể. Tại một thời điểm, một tài nguyên có thể được yêu cầu sử dụng bởi các gói tin khác nhau. Điều khiển luồng là quá trình lựa chọn, ra lệnh cho gói tin nào được quyền truy cập vào một tài nguyên cụ thể tại thời điểm đó. Điều khiển luồng được thực hiện liên tục theo thời gian và đóng vai trò quan trọng trong việc vừa chuyển tiếp các gói tin với độ trễ nhỏ nhất, vừa đảm bảo được các tài nguyên không bị sử dụng quá tải, hoặc không được sử dụng trong thời gian dài. 1.1.1.4. Một số khái niệm liên quan đến mạng liên kết a. Nút mạng và kênh truyền Cấu trúc của mạng liên kết được xác định bởi một tập hợp các nút mạng (kí hiệu ∗) mà chúng được kết nối bởi một tập hợp các kênh (gọi là ). Mỗi một thiết bị chuyển tiếp hoặc tính toán trên mạng được biểu diễn là một nút mạng (thiết bị đầu cuối) trong đó ⊆ ∗. Tất cả các nút mạng được xem như là thiết bị đầu cuối, và mỗi kênh = ( , ) ∈ , kết nối nút nguồn đến nút đích , với , ∈ ∗. Kênh = ( , ) được đặc trưng bởi băng thông (bandwidth) của nó, 푤 hoặc 푤 , số lượng các tín hiệu song song trên kênh ; tần số của nó, hoặc , tốc độ bit được vận chuyển trên mỗi tín hiệu; và độ trễ của nó, 푡 hoặc 푡 , là thời gian cần thiết cho một bit để đi từ đến . Đối với hầu hết các kênh, độ trễ có liên quan trực tiếp đến độ dài vật lý của các kênh, 푙 = 푣 ∗ 푡 , bởi vận tốc truyền 푣. Băng thông của kênh là = 푤 ∗ . Trong trường hợp băng thông của tất cả các kênh đều giống nhau, ký hiệu được xem như là băng thông của mạng. Với mỗi switch (nút mạng trung gian), có một tập kênh = ∪ . Trong đó, = { ∈ | = } là tập kênh vào, và = { ∈ |푆 = } là tập kênh ra. Bậc của là 훿 = | | đó là tổng các bậc vào, 휃 = | |, và bậc ra, 휃 = | |. Trong trường hợp bậc của ∀ ∈ ∗ là như nhau, ký hiệu chung là 휃. b. Kết nối trực tiếp và kết nối gián tiếp Đối với hoạt động truyền thông trong mạng, một nút mạng có thể là một nút nguồn (gửi) và nút đích (nhận) cho các gói tin, một nút chuyển đổi (switch node) chuyển tiếp các gói tin từ cổng vào đến cổng ra, hoặc cả hai. Trong mạng trực tiếp (Direct Network), chẳng hạn như, Hình 1.4 (b), tất cả các nút mạng vừa là thiết bị đầu cuối vừa là một thiết bị chuyển mạch. Trong mạng gián tiếp (Indirect Network), như Hình 1.4 (a), một nút hoặc là một thiết bị đầu cuối (nút hình tròn) hoặc một switch (nút hình chữ nhật). Trong mạng trực tiếp, các gói tin được chuyển tiếp trực tiếp giữa các nút đầu cuối, trong khi trong mạng gián tiếp chúng được chuyển thông qua các nút chuyển mạch, Hình 1.4 (a). Một số mạng như mạng ngẫu nhiên, Hình 1.4 (c), là không trực tiếp hoặc gián tiếp. Mỗi mạng trực tiếp có thể được thiết kế thành mạng gián tiếp bằng cách tách nút đầu cuối thành các nút chuyển mạch. 18
19. (a): mạng 2-ary 3-fly (b): mạng 3 ary 2-cube (c): mạng không đồng nhất Hình 1.4: Mạng trực tiếp và gián tiếp c. Lát cắt và đường đi trong mạng Lát cắt của một mạng, ( 1, 2), là một tập hợp các kênh phân vùng tập của tất ∗ cả các nút mạng thành hai tập hợp con tách rời nhau, 1 và 2. Mỗi phần tử của ( 1, 2) là một kênh với một nguồn trong 1 và đích trong 2, hoặc ngược lại. Số lượng các kênh trong việc cắt giảm là | ( 1, 2)| và tổng băng thông của lát cắt là: ( ) ∑ 1, 2 = ∈ ( 1, 2) (CT 1.1) Lát cắt (Bisection) là đường chia mạng thành hai phần tương đương nhau về số lượng, như vậy | 2| ≤ | 1| ≤ | 2| + 1, và | 2 ∩ | ≤ | 1 ∩ | ≤ | 2 ∩ | + 1. Các kênh chia làm hai đoạn của mạng, là kênh tối thiểu tính trên tất cả các phần của mạng = min | ( 1, 2)| (CT 1.2) 푖푠푒 푡푖표푛푠 Việc chia mạng làm hai tập tương đương nhau về kích thước, dẫn tới băng thông của mạng, , là băng thông tối thiểu trên tất cả các phần của mạng, được tính bằng = min | ( 1, 2)| (CT 1.3) 푖푠푒 푡푖표푛푠 Đối với các mạng băng thông kênh đồng nhất , thì = b. Đường đi trong mạng là tập hợp có thứ tự các kênh 푃 = ( 1, 2, , 푛), trong đó ( ) 푖 = 푆 푖+1 với 푖 = 1,2, , 푛 − 1 . Các nguồn của 푃 là, 푆푃 = 푆 1và đích đến là 푃 = | | 푛. Chiều dài của một đường là 푃 , tính theo hop count. Trong một mạng cụ thể, 2 cặp nút nguồn – đích được gọi là có liên kết với nhau nếu tồn tại đường đi giữa chúng. 1.1.2. Giới thiệu giải thuật định tuyến 1.1.2.1. Khái niệm định tuyến Định tuyến là quá trình lựa chọn và xác định đường để truyền gói tin từ nguồn tới đích trong một mạng xác định. Giải thuật định tuyến là thuật toán dùng để lựa chọn con đường nói trên. Thuật toán định tuyến có vai trò quan trọng bởi một số lý do sau: (i) Thuật toán định tuyến giúp cân bằng tải trong quá trình truyền tin, có nghĩa là lượng thông tin được truyền qua mỗi liên kết là tương đương nhau. Từ đó, việc tranh 19
20. chấp tài nguyên và tắc nghẽn (deadlock) được giảm thiểu. Tải kênh càng cân bằng, thông lượng của mạng càng gần đạt mức lý tưởng. (ii) Một thuật toán định tuyến tốt giúp cho các gói tin được truyền đi theo đường ngắn nhất, làm giảm số lượng hop. Qua đó góp phần làm giảm độ trễ truyền tin. (iii) Ngoài ra, thuật toán định tuyến tốt còn có khả năng chịu lỗi khi một vài nút mạng, hoặc liên kết xảy ra sự cố và không thể hoạt động. Trong trường hợp này, thuật toán định tuyến phải loại bỏ các phương án lựa chọn đường đi xảy ra lỗi và thay thế bằng những đường đi khác nhằm đảm bảo sự hoạt động của mạng liên kết. Thuật toán định tuyến kết hợp với điều khiển luồng (mục 1.1.2.2) và thiết kế tô- pô hợp lý để giải quyết các bài toán liên quan tới khóa chết (deadlock/livelock). Có rất nhiều cách phân loại thuật toán định tuyến khác nhau. Dựa trên số lượng đích tới của một gói tin, truyền đơn tuyến (unicast routing) chỉ các thuật toán định tuyến các gói tin đuợc gửi từ một nút nguồn tới một đích. Trong khi đó, truyền đa tuyến (multicast routing) chỉ các thuật toán gửi tin tới hai hay nhiều đích trong mạng liên kết. Thuật toán định tuyến được phân loại dựa trên địa điểm mà quyết định định tuyến được thực hiện. Một cách đơn giản, đường truyền tin có thể được quyết định ngay tại nguồn (source routing), tại bộ điều khiển tập trung (centralized routing) hoặc được quyết định một cách phân tán (distributed routing) tại các nút mạng trong quá trình truyền tin. Thuật toán định tuyến được cài đặt theo nhiều cách khác nhau. Một vài cách phổ biến nhất được áp dụng đó là sử dụng bảng định tuyến (table lookup routing) hoặc sử dụng máy trạng thái hữu hạn (finite-state machine routing). Trong cả hai trường hợp này thuật toán định tuyến đều có thể là định tuyến xác định (deterministic) hoặc định tuyến thích nghi (adaptive). Định tuyến xác định là các thuật toán định tuyến mà đường đi giữa nút nguồn 푆 và nút đích được chọn trước và không đổi trong mọi lần định tuyến. Định tuyến thích nghi (mục 1.1.2.2) là phương pháp định tuyến dựa vào trạng thái của mạng để xác định đường đi chính xác tại mỗi lần lựa chọn. Trạng thái này bao gồm thông tin về các nút mạng, các liên kết trong mạng, thông tin về yêu cầu sử dụng các liên kết (a) Định tuyến tối thiểu (Minimal routing) (b) Định tuyến không tối thiểu Hình 1.5: Ví dụ về định tuyến trên mạng kết 2D-Torus [5] Trong quá trình định tuyến, nếu tất cả các con đường được lựa chọn đều là ngắn nhất, gọi là minimal routing, ngược lại, giải thuật có tính chất non-minimal. Hình 1.5 ( 20
21. [5]) là một ví dụ về thuật toán định tuyến trên mạng liên kết 4-ary 2-dimentional torus. Thuật toán định tuyến trong Hình 1.5-a là định tuyến tối thiểu do chỉ ra con đường ngắn nhất từ nút mạng 01 đến nút mạng 22 còn Hình 1.5-b là định tuyến không tối thiểu. Nếu các đường định tuyến được xác định tại nút mạng 01 (ngay từ đầu) thì đó là định tuyến nguồn. Nếu đuờng đi từ nút “01” đến nút “22” luôn luôn không đổi tại mọi thời điểm định tuyến, gọi là định tuyến xác định. Định tuyến nguồn và định tuyến xác định thường được cài đặt sử dụng bảng định tuyến. 1.1.2.2. Phân loại các giải thuật định tuyến a. Định tuyến cơ bản Các thuật toán định tuyến đơn giản nhất là định tuyến xác định (deterministic routing) – chúng gửi mỗi gói tin từ nguồn 푆 đến đích trên chính xác cùng một tuyến đường cho mỗi lần phát sinh yêu cầu chuyển tiếp gói tin. Các mối quan hệ cho thuật toán định tuyến xác định là một chức năng – ví dụ, 푅: × → 푃. Sự thiếu đường thay thế có thể tạo ra sự mất cân bằng tải lớn trong mạng. Vì vậy, đối với một nhà thiết kế quan tâm đến trường hợp xấu nhất, các thuật toán xác định sẽ không thể là một sự lựa chọn đầu tiên. Tuy nhiên, thuật toán xác định vẫn có giá trị riêng. Trước đây, nhiều mạng sử dụng định tuyến xác định bởi vì nó rất đơn giản và không tốn kém để thực hiện. Ngày nay vẫn còn tồn tại những mạng sử dụng thuật toán đường đi xác định. Điều này đặc biệt đúng đối với các cấu trúc liên kết bất thường, định tuyến xác định dễ dàng cài đặt hơn so với định tuyến ngẫu nhiên và định tuyến thích nghi. Đối với hầu hết các cấu trúc liên kết, có thể lựa chọn chức năng định tuyến xác định ngắn nhất, đảm bảo độ dài đường đi sẽ là ngắn. Đối với một số cấu trúc liên kết, các phương pháp định tuyến xác định tiếp cận cân bằng tải thực cũng tốt như bất kỳ thuật toán định tuyến tối thiểu khác, bao gồm định tuyến thích ứng. Hai thuật toán định tuyến xác định thường được sử dụng rộng rãi là Destination- Tag Routing (DTR) trong tô-pô Butterfly và Dimension-Order Routing (DOR) trong tô- pô Tori và Mesh. Cả DTR và DOR đều sử dụng địa chỉ nút đích (푛-digit radix- ) để thực hiện định tuyến. Tuy nhiên, kỹ thuật định tuyến của mỗi thuật toán là khác nhau. DTR dựa trên địa chỉ đích đến để quyết định định tuyến theo kỹ thuật UP/ DOWN, trong khi DOR tiến hành định tuyến dựa trên vị trí của nút nguồn và nút đích) Hình 1.5-a minh họa ví dụ về DOR trên tô-pô 2-D Torus, nút nguồn là “01” và nút đích là “22”. Mỗi chiều của Torus thể được định tuyến cùng chiều hoặc ngược chiều (do tính chất nối vòng của tô-pô Torus), do đó, DOR xác định đường ngắn nhất theo chiều thứ nhất và tiếp theo là đường ngắn nhất theo chiều thứ hai (đối với 2-D Torus). b. Định tuyến xác định và định tuyến thích nghi Định tuyến xác định ngẫu nhiên (Oblivious Routing), trong đó, các gói tin được truyền đi mà không xem xét trạng thái mạng. Dạng định tuyến này được thực thi đơn giản bằng cách gửi gói tin đến một nút mạng được chọn ngẫu nhiên và gần nhất đối với nút hiện thời, sau đó, từ nút mạng được chọn sẽ định tuyến đến nút đích, ví dụ, thuật toán 21
22. định tuyến ngẫu nhiên Valiant [5]. Hiệu suất định tuyến có thể được cải thiện nếu kèm theo thông tin mạng, tuy nhiên, sự tính toán thiếu cẩn trọng có thể dẫn đến suy giảm hiệu suất. Sự đánh đổi của định tuyến tức thời là giữa tính cục bộ và cân bằng tải. Khác với định tuyến xác định ngẫu nhiên, định tuyến thích nghi (Adaptive Routing) sử dụng thông tin về trạng thái mạng, sử dụng hàng đợi, lựa chọn đường thay thế (khi cần) để chuyển tiếp gói tin. Định tuyến thích nghi phụ thuộc vào trạng thái mạng, cho nên nó kết hợp mật thiết cùng với các cơ chế điều khiển luồng. Điều này trái ngược với thuật toán định tuyến xác định và định tuyến xác định ngẫu nhiên. Về lý thuyết, định tuyến thích nghi sẽ tốt hơn định tuyến xác định ngẫu nhiên, khi nó được sử dụng thông tin trạng thái mạng. Tuy nhiên, trong thực tế, nhiều thuật toán định tuyến thích nghi cho hiệu suất tồi tệ nhất. Điều này phần lớn do tính chất địa phương tự nhiên của hầu hết các thuật toán định tuyến thích ứng thực tế. Bởi vì chúng sử dụng thông tin trạng thái mạng chỉ địa phương (ví dụ, độ dài hàng đợi cục bộ) trong việc đưa ra quyết định định tuyến, chúng định tuyến để đảm bảo cân bằng tải địa phương nhưng thường dẫn đến sự mất cân bằng toàn cục. Các vấn đề liên quan tới định tuyến thích ứng được minh họa bằng việc xem xét trường hợp mạng RING – 8 nút đơn giản, Hình 1.6. Nút 5 đang gửi một dòng liên tục của các gói tin đến nút 6, sử dụng tất cả băng thông có sẵn trên kênh (5; 6). Hình 1.6: Định tuyến thích ứng trên tô-pô RING 8-nút. Nút (3) muốn gửi một gói tin đến nút (7) và có thể chọn giữa con đường thông qua các nút (4) đến (6) hoặc con đường khác thông qua các nút (2) đến nút (0). Nút (3) không biết lưu lượng truy cập đồng thời giữa các nút (5) và (6). Trong cùng một thời điểm, nút (3) gửi gói tin đến nút (7). Nó có thể chọn một trong hai con đường chiều kim đồng hồ, biểu hiện bằng một mũi tên nét liền, hoặc các tuyến đường ngược chiều, biểu hiện bằng một mũi tên nét đứt, rõ ràng rằng các bộ định tuyến tại nút (3) nên chọn con đường ngược chiều để tránh sự xung đột trên kênh (5; 6). c. Điều khiển luồng (flow control) Điều khiển luồng (flow control) là quá trình xác định cách thức các tài nguyên trên mạng (kết nối, bộ đệm tại các nút mạng ) được phân phối cho các gói tin sử dụng trong quá trình truyền tin. Điều khiển luồng tốt là cách thức phân phối tài nguyên một cách có hiệu quả qua đó truyền tin với độ trễ nhỏ xác định trước. Điều khiển luồng cung cấp cơ chế cho người nhận để kiểm soát tốc độ truyền dẫn, để các nút nhận (receiving node) không phải là quá tải với các dữ liệu từ nút gửi (sending node). Điều khiển luồng nên được phân biệt với điều khiển tắc nghẽn, được sử dụng để kiểm soát luồng của dữ liệu khi tắc nghẽn đã thực sự xảy ra [8]. Kỹ thuật điều khiển luồng có thể được phân loại 22
23. theo nút nhận có gửi phản hồi đến nút gửi hay không. Điều khiển luồng là quan trọng bởi vì nó có thể cho một nút gửi thông tin đi có tốc độ gửi nhanh hơn so với các nút đích có thể nhận và xử lý nó. Điều này có thể xảy ra nếu nút nhận có lưu lượng tải cao so với các nút gửi đi, hoặc nếu nút nhận có sức mạnh xử lý kém hơn so với nút gửi đi. Ví dụ, hai gói tin đến từ hai cổng khác nhau tại một bộ chuyển tiếp tại cùng một thời điểm. Dựa trên giải thuật định tuyến, hai gói tin này cần được chuyển tiếp đến cùng một cổng ra. Trong trường hợp này, điều khiển luồng là cơ chế giải quyết sự xung đột về yêu cầu sử dụng tài nguyên. Một phương pháp đơn giản đó là chọn một gói tin ngẫu nhiên để chuyển tiếp và loại bỏ gói tin còn lại (gói tin này sẽ được gửi lại sau). Đây là cơ chế đơn giản nhất trong điều khiển luồng khi không lưu trữ gói tin tại các bộ chuyển tiếp (bufferless flow-control). Một cơ chế điều khiển luồng khác phức tạp hơn và hiệu quả hơn gọi là chuyển mạch (circuit switching). Trong đó, nút nguồn sẽ gửi gói tin thăm dò đến nút đích. Gói tin thăm dò chỉ bao gồm thông tin truyền tin cơ bản (ví dụ nút nguồn, nút đích) mà không bao gồm dữ liệu. Gói tin thăm dò có tác dụng đăng kí sử dụng tài nguyên tại các nút mạng mà nó đi qua. Khi nút đích nhận được gói tin thăm dò này sẽ gửi trả một gói tin gọi là ACK xác nhận. Nút nguồn sẽ bắt đầu truyền dữ liệu theo con đường được thiết lập bởi gói tin thăm dò trước đó sau khi nhận được ACK. Các tài nguyên trên được gói tin này sử dụng chỉ được giải phóng khi toàn bộ dữ liệu đến với nút đích. Trong trường hợp một gói tin thăm dò không được cấp phát tài nguyên ngay lập tức tại một nút mạng, nó sẽ được lưu trữ lại trong hàng đợi (do kích thước gói tin thăm dò nhỏ) cho đến khi tài nguyên được giải phóng. Với cách điều khiển luồng này, độ trễ truyền tin đôi khi rất lớn khi một gói tin cần phải đợi tài nguyên được giải phóng tại nút mạng được nhiều gói tin truyền qua (nút thắt cổ chai). Một phương pháp điều khiển luồng khác hiệu quả hơn được gọi là “chuyển mạch gói” (packet switching) được áp dụng để chuyển tiếp gói tin. Trong phương pháp này, dữ liệu được chia thành các thành phần nhỏ hơn có độ dài bằng nhau gọi là gói tin (packet). Một vài bytes đầu của gói tin chứa thông tin định tuyến và điều khiển gọi là tiêu đề gói tin (packet header). Trong quá trình truyền tin, nếu xảy ra tranh chấp tài nguyên, các gói tin này sẽ được lưu trữ lại tại nút mạng đó và chờ cho đến khi tài nguyên được giải phóng. Do vậy, chuyển mạch gói còn được gọi là lưu và chuyển tiếp (store- and-forward switching). Với cơ chế này, các phần nhỏ của toàn bộ dữ liệu được truyền trong mạng theo các đường khác nhau nhằm tận dụng các tài nguyên rảnh rỗi. Ngoài ra quá trình chờ đợi để giải phóng tài nguyên cũng ngắn hơn do kích thước của các gói tin là nhỏ hơn rất nhiều so với kích thước dữ liệu cần truyền. Quá trình định tuyến được thực hiện khi toàn bộ gói tin được truyền tới và lưu trữ tại nút trung gian. Tuy nhiên, trong thực tế, tiêu đề gói tin được truyền đến nút mạng này trước khi toàn bộ phần dữ liệu mà gói tin ấy chứa truyền tới. Nhằm giảm độ trễ truyền tin, và giảm thời gian chiếm dụng tài nguyên của một gói tin, quá trình định tuyến và chuyển tiếp tiêu đề gói tin có thể được thực hiện ngay khi tài nguyên yêu cầu sử dụng được rảnh rỗi mà không cần phải chờ đợi toàn bộ gói tin được chuyển đến nút trung gian. 23
24. Với phương pháp điều khiển luồng này, một gói tin sử dụng cùng lúc cổng ra (output port) tại một nút trung gian và cổng vào (input port) tại nút mạng tiếp theo. Phương pháp này được gọi là chuyển tiếp thông qua mạch ảo (virtual cut-though switching). Lưu trữ các gói tin có kích thước lên đến hàng chục bytes gây khó khăn cho việc chế tạo các bộ chuyển tiếp có kích thước nhỏ, giá thành rẻ. Bên cạnh đó, quá trình chờ đợi các gói tin đuợc truyền tin cũng góp phần tạo độ trễ truyền tin. Nhằm khắc phục các yếu điểm này, kỹ thuật Wormhole switching [5] đã ra được đề xuất. Trong phương pháp này, các gói tin đuợc chia nhỏ thành các đơn vị truyền tin (flits). Kích thước bộ đệm tại các cổng ra và cổng vào tại một nút mạng đủ lớn để chứa một vài flits, ví dụ một flits có thể có kích thước cỡ 16 bits. Nhờ đó, yêu cầu về kích thước bộ đệm trong các bộ định tuyến giảm đi đáng kể. Mặt khác, kỹ thuật Wormhole switching có thể khiến quá trình truyền tin bị tắc nghẽn. Trong trường hợp một gói tin phải đợi tài nguyên được giải phóng, gói tin trong Wormhole Switching bị chặn lại tại nhiều bộ chuyển tiếp thay vì một bộ chuyển tiếp duy nhất như kỹ thuật Virtual Cut-through switching. Gói tin B Gói tin A R1 R2 R3 Header Flit Data Flits Hình 1.7: Ví dụ về tắc nghẽn của Wormhole switching Hình 1.7 (nguồn [9]) minh họa trường hợp này. Trong đó, gói tin đang chiếm bộ đệm của một cổng ra tại nút mạng 푅3. Tiêu đề của gói tin truyền tới 푅3 phải đợi bộ đệm ở cổng ra được giải phóng. Trong khi các thành phần dữ liệu của gói tin được lưu trữ trong bộ đệm tại nút mạng 푅1 và 푅2 thay vì được lưu trữ toàn bộ tại 푅3. Lưu ý rằng các bộ đệm trong ví dụ này chỉ có kích thước rất nhỏ 2 flits (cỡ 32 bits). 1.1.3. Hiệu năng mạng liên kết 1.1.3.1. Đường kính mạng và trung bình độ dài đường định tuyến Đường đi ngắn nhất giữa 2 nút mạng bất kỳ là đường đi có số lượng khoảng (hop) bé nhất mà kết nối giữa chúng. Tập hợp các đường đi ngắn nhất giữa bất kỳ cặp nút mạng và 푣, kí hiệu là ( , 푣). Đường kính mạng (Diameter), kí hiệu là , là đường đi lớn nhất trong tất cả các đường đi của mọi cặp nút mạng ( = max (∀ ( , 푣))). Đường kính mạng là một tham số hiệu năng mạng được đánh giá bằng phương pháp phân tích đồ thị. Đây là một trong những tham số hiệu năng thường được các nhà nghiên cứu đánh giá khi xây dựng mạng liên kết dưới dạng đồ thị. Đường kính mạng không thể hiện chiều dài cáp mạng mà chỉ thể hiện số hop tối đa mà một gói tin có thể di chuyển giữa 2 đỉnh xa nhau. Đường kính mạng có ảnh hưởng đến độ trễ truyền tin trung bình. Giá trị đường kính mạng càng lớn thì dự báo độ trễ truyền tin trung bình của 24
25. mạng càng tăng cao. Cho nên, các nhà khoa học tập trung xây dựng các tô-pô mạng mới đảm bảo giá trị đường kính mạng đạt thấp. Ngoài ra, đường kính mạng phụ thuộc vào bậc đỉnh (hoặc theo cách khác, là phụ thuộc vào số liên kết của mỗi đỉnh). Bậc đỉnh càng cao thì đường kính mạng càng giảm, tức là số liên kết tại mỗi đỉnh tăng lên, làm giảm số hop. Đặc biệt, số lượng các liên kết ngẫu nhiên (kết nối giữa các đỉnh ở xa nhau) càng tăng lên, càng có khả năng làm giảm đường kính mạng. Do đó, một trong những cách tiếp cận để xây dựng tô-pô mạng mới hiệu quả là sử dụng các liên kết ngẫu nhiên và tăng số bậc đỉnh. Tuy nhiên, một vấn đề hiển nhiên là khi tăng bậc đỉnh lên đồng nghĩa với chi phí thiết bị tại đỉnh đó tăng cao (ví dụ số cổng tại mỗi thiết bị chuyển mạch). Một tham số thứ hai được các nhà khoa học quan tâm đánh giá là trung bình chiều dài đường đi ngắn nhất (Average Shortest Path Length - ASPL). Đơn vị của 푆푃퐿 tương tự như đường kính mạng, thể hiện trung bình chiều dài đường định tuyến ngắn nhất của mạng tính theo hop. Mặc dù vậy, 푆푃퐿 có ý nghĩa hơn khi cho biết số hop trung bình mà tô-pô mạng có thể đáp ứng cho quá trình truyền tin. Dựa trên chiến lược định tuyến được áp dụng trên tô-pô, tham số 푅푃퐿 (Average Routing Path Length), được định nghĩa như là trung bình chiều dài đường định tuyến. Sở dĩ tham số 푅푃퐿 được đưa ra bởi các chiến thuật định tuyến không tuân theo đường đi ngắn nhất, ví dụ các thuật toán định tuyến rút gọn, các thuật toán khai thác liên kết dài. Về mặt ý nghĩa thì 푆푃퐿 và 푅푃퐿 là tương đồng nhau, tuy nhiên chúng khác nhau bởi việc áp dụng chiến lược định tuyến đường đi ngắn nhất hay không ngắn nhất. 1.1.3.2. Độ trễ truyền tin “Độ trễ (latency) là khoảng thời gian từ khi một gói tin được khởi tạo tại nút nguồn đến khi gói tin đó được nhận ở nút đích” [9]. Nếu nghiên cứu liên quan đến kết nối và các thiết bị mạng, độ trễ được định nghĩa là khoảng thời gian kể từ khi thành phần dữ liệu đầu tiên của gói tin bắt đầu được gửi vào mạng cho đến khi thành phần dữ liệu cuối cùng đến được đích. Mỗi nút mạng có một hàng đợi chứa các gói tin gửi đi và gói tin nhận đuợc để chờ xử lý, do mỗi nút mạng có thể gửi và nhận cùng lúc nhiều gói tin. Nếu quá trình nghiên cứu liên quan đến sự hoạt động của hàng đợi này, độ trễ cần được tính thêm khoảng thời gian trong hàng đợi tại nút nguồn. Ngoài ra, một số nghiên cứu không chỉ tập trung chú ý tới tác động của mạng liên kết đến độ trễ mà còn chú ý tới tác động của các hoạt động được thực hiện tại các bộ vi xử lý nguồn/đích để gửi và nhận tin nhắn từ mạng. Các hoạt động này bao gồm tiến trình chuẩn bị dữ liệu để truyền đi (ví dụ như xây dựng thông tin gói tin – packet header, thành phần kiểm tra lỗi – checksums), quá trình gửi gói tin vào và lấy gói tin ra khỏi mạng. Trong hầu hết các hệ thống, các hoạt động này được cài đặt trong phần mềm gọi là lớp tin nhắn (messaging layer). Đối với những nghiên cứu có cân nhắc và đánh giá tác động của lớp tin nhắn, độ trễ được định nghĩa là khoảng thời gian kể từ khi lời gọi truyền tin của hệ thống được khởi tạo tại nút nguồn cho đến khi lời gọi nhận tin của hệ thống được hoàn thành tại nút nguồn. 25
26. Độ trễ được mô hình hóa thành 3 thành phần chính latency = injection_time + time_to_fly + switches_latency o Thời gian gói tin được gửi vào mạng (Injection_time): hoặc gọi là serialization latency [5] hay transmission time [6], là thời gian gói tin được gửi vào mạng. Cụ thể, đó là khoảng thời gian giữa thành phần dữ liệu đầu tiên của gói tin truyền vào đến khi thành phần dữ liệu cuối cùng truyền vào mạng. Injection_time đuợc tính bằng kích thước của gói tin chia cho băng thông của đường truyền (trong trường hợp toàn bộ đường truyền này được sử dụng để truyền gói tin đó mà không phải chia sẻ để truyền gói tin nào khác). Độ trễ gói tin Bắt đầu Kết thúc I/O Hình 1.8: Độ trễ của một gói tin trên kênh truyền o Thời gian truyền gói tin trên mạng (Time_to_fly hay time_of_flight [5]), khoảng thời gian cần thiết để gói tin được truyền trên đường truyền mạng. Thời gian truyền gói tin trên mạng phụ thuộc vào độ dài của đường truyền mạng. Đơn vị tính thời gian trong các lĩnh vực ứng dụng WANs có đơn vị là mili-giây, micro-giây cho LANs, nano-giây với SANs và pico-giây đối với OCNs. o Độ trễ trên switch (Switches_latency): là khoảng thời gian cần thiết để bộ chuyển mạch xử lý chuyển tiếp gói tin (chọn và gửi gói tin đến cổng ra, định tuyến), nó phụ thuộc vào số lượng bộ chuyển mạch mà gói tin truyền qua trên đường từ nguồn tới đích. Do đó giá trị trung bình độ trễ của mạng liên kết được tính bằng tích của giá trị trung bình của các đường đi (có thể là ngắn nhất) 푣𝑔 nhân với thời gian trễ tại một bộ chuyển mạch bất kì, kí hiệu là 푡 . Công thức tính độ trễ nêu trên được sử dụng khi trong quá trình truyền tin không có tranh chấp về mặt tài nguyên. Trong trường hợp ngược lại, độ trễ cần phải tính thêm khoảng thời gian để các gói tin nằm chờ trong hàng đợi. ) bits ( Băng thông Thông lượng Giao thông Thời gian (giây) Hình 1.9: Tương quan giữa băng thông và thông lượng Biểu đồ độ trễ theo lượng thông tin yêu cầu truyền đi (offered traffic) thể hiện mối tương quan giữa độ trễ và giá trị này. Khi mà lưu lượng dữ liệu yêu cầu còn nhỏ, không xảy ra tranh chấp tài nguyên, độ trễ có hình dạng theo công thức trên. Tuy nhiên, 26
27. khi lưu lượng dữ liệu yêu cầu tăng dần, độ trễ tăng một lượng lớn. Lưu lượng dữ liệu yêu cầu đạt đến giá trị bão hòa khi độ trễ trở nên rất lớn, như Hình 1.10 (nguồn [5]). Hình 1.10: Tương quan giữa độ trễ và lưu lượng dữ liệu yêu cầu 1.1.3.3. Bảng định tuyến và kích thước bảng định tuyến Thuật ngữ kỹ thuật định tuyến (“routing mechanics”) đề cập đến cơ chế sử dụng để thực hiện bất kỳ thuật toán định tuyến: xác định, xác định ngẫu nhiên, hoặc thích nghi. Các bộ định tuyến sử dụng bảng định tuyến hoặc tại nguồn hoặc tại mỗi hop dọc theo tuyến đường để thực hiện các thuật toán định tuyến. Với mỗi bản ghi tại nút đích, thuật toán định tuyến xác định bị hạn chế do chỉ xác định được một bản thông tin định tuyến. Tuy nhiên thuật toán định tuyến xác định ngẫu nhiên và thuật toán định tuyến thích nghi có thể được thực hiện bằng cách cung cấp nhiều bảng cho mỗi nút đích. Một thay thế cho bảng định tuyến là thuật toán định tuyến, trong đó phần cứng chuyên dụng tính toán các tuyến đường hoặc hop kế tiếp của một gói tin tại thời gian thực thi. Tuy nhiên, thuật toán định tuyến thường bị giới hạn đối với các thuật toán định tuyến đơn giản và cấu trúc liên kết thường. Quan hệ định tuyến được biểu diễn dưới 3 dạng: 푅: × → 푃(푃) hoặc 푅: × → 푃( ) hoặc 푅: × → 푃( ). Trong đó, là tập các nút mạng, 푃 là tập các đường đi giữa các nút mạng và là tập các kênh truyền. Giá trị của các mối quan hệ cho mỗi cặp đầu vào được lưu trữ trong bảng và bảng được lập chỉ mục của các đầu vào. Ví dụ, đối với các hình thức đầu tiên của mối quan hệ định tuyến, các thiết lập đường dẫn cho mỗi cặp nút được lưu trữ trong bảng, và bảng được lập chỉ mục của các nút nguồn và đích. Tổng số bản ghi lưu trữ các mối quan hệ định tuyến là kích thước của bản định tuyến đó. Đây là một tham số quan trọng, nó phụ thuộc vào bộ nhớ (vật lý) của mỗi nút chuyển tiếp, ảnh hưởng đến giá thành của các nút chuyển mạch. Ưu điểm chính của định tuyến bảng là có tính phổ quát cao. Tập trung vào khả năng các ràng buộc, một bảng định tuyến có thể hỗ trợ bất kỳ mối quan hệ định tuyến trên bất kỳ cấu trúc liên kết. Một con chip định tuyến có sử dụng định tuyến dựa trên bảng có thể được sử dụng trong cấu trúc liên kết khác nhau bằng cách tái lập trình các 27
28. nội dung của bảng. Có 2 loại định tuyến bảng là định tuyến bảng và định tuyến nguồn. Với định tuyến nguồn, thực hiện các mối quan hệ định tuyến bằng cách tìm lại trên toàn bộ tuyến đường tại nguồn. Với định tuyến bảng, thực hiện định tuyến bằng cách tìm mối quan hệ định tuyến theo từng hop (hop-by-hop) tại mỗi nút dọc theo tuyến đường. Định tuyến nguồn (Source – Routing): Với định tuyến nguồn, tất cả các quyết định định tuyến cho một gói tin được thực hiện hoàn toàn tại các thiết bị đầu cuối nguồn trong bảng tra cứu của một đường đi được tính toán trước đó. Mỗi nút nguồn có chứa một bảng của các tuyến đường, ít nhất là một cho mỗi điểm đến. Để định tuyến một gói tin, bảng được lập chỉ mục bằng cách sử dụng đến gói dữ liệu để tìm kiếm các tuyến đường thích hợp. Nếu một tập thông tin đường đi được trả lại, trạng thái bổ sung được sử dụng để chọn một đường đi từ các thiết lập định tuyến xác định ngẫu nhiên hay định tuyến thích nghi. Đường đi này được thêm vào tiêu đề gói tin và được sử dụng để truyền các gói tin thông qua mạng dọc theo con đường đã chọn mà không có tính toán thêm. Định tuyến bảng tại nút mạng (Node – Table Routing): được thực hiện bằng cách lưu trữ các bảng định tuyến tại các nút trung gian. Định tuyến bảng tại mỗi nút mạng thích hợp hơn cho các thuật toán định tuyến thích nghi bởi vì nó cho phép việc sử dụng các thông tin trạng thái mạng để chọn trong số nhiều các hop tiếp theo ở từng đoạn của tuyến đường. Tuy nhiên, kỹ thuật định tuyến tại nút mạng làm cho chi phí lưu trữ cao và tác động trực tiếp vào hiệu năng hệ thống và làm hạn chế về định tuyến. Với sự sắp xếp này, khi một gói tin tới một nút mạng, tra cứu bảng phải được thực hiện trước khi các cổng ra cho các gói dữ liệu có thể được lựa chọn. Việc thực hiện tra cứu tại mỗi bước của đường đi, làm tăng đáng kể độ trễ cho một gói tin đi qua một nút mạng. Cách tiếp cận này làm giảm khả năng mở rộng, vì mỗi nút phải chứa một bảng đủ lớn để lưu lớn nhất có thể các hop kế tiếp đối với tất cả các điểm đến trong mạng. Ngoài ra, với cách tiếp cận này, không thể để cho các gói dữ liệu từ hai nút nguồn khác nhau, và , xác định cho cùng một nút , đến một nút trung gian 푤, trên cùng một kênh hai con đường khác nhau từ 푤 đến . Mặc dù, điều này rất dễ thực hiện với định tuyến nguồn. 1.1.3.4. Thông lượng mạng Thông lượng được định nghĩa là lượng thông tin tối đa được truyền trong một đơn vị thời gian trong mạng liên kết [9]. Lượng thông tin được truyền trong một đơn vị thời gian còn được gọi là lưu lượng dữ liệu (traffic). Do đó thông lượng còn được hiểu là lưu lượng dữ liệu tối đa mà mạng chấp nhận được (maximum accepted traffic). Thông lượng khác với lưu lượng yêu cầu (hay còn gọi là offered traffic) – tốc độ gói tin (thông tin) được sinh ra bởi nguồn – Hình 1.11 (nguồn [5]) thể hiện mối tương quan giữa thông lượng và yêu cầu. Ban đầu, khi lượng thông tin yêu cầu truyền đi còn thấp, thông lượng và lưu lượng dữ liệu yêu cầu có giá trị bằng nhau. Theo sự tăng lên của yêu cầu truyền tin, thông lượng đạt đến mức bão hòa và mạng không thể đáp ứng truyền tất cả các gói tin với tốc độ ban đầu. Đây cũng là phương thức để đánh giá thông lượng của mạng dưới một yêu cầu truyền tin cụ thể (traffic pattern). 28
29. Hình 1.11: Tương quan giữa thông lượng và lưu lượng dữ liệu yêu cầu Đơn vị thời gian có thể được xác định tương đối bằng đơn vị chu kì đồng hồ (clock cycle), ban đầu người ta sử dụng đơn vị gói tin trong một giây. Do đó, thông lượng cũng có thể tính bằng số gói tin nhận được trong một chu kỳ. Một cách tổng quát, thông lượng tỉ lệ thuận với kích thước của mạng. Mạng có kích thước lớn hơn có khả năng truyền được số lượng gói tin lớn hơn. Mặt khác, với mỗi ứng dụng cụ thể, kích thước của gói tin là khác nhau. Do đó, nhằm mục đích tiêu chuẩn hóa, thông lượng được lượng giá bằng đơn vị bits trên một nút mạng (tính theo micro-giây), hay bits trên một nút mạng (tính theo chu kỳ thời gian). Như vậy, thông lượng của mạng theo đó được hiểu là tốc độ truyền thông tin (bps, bit per cycle) mà mạng chấp nhận trên từng cổng vào [5]. 1.1.4. Mô phỏng đánh giá hiệu năng mạng Phần mềm mô phỏng dựa trên quá trình mô hình hóa một hiện tượng thực tế với một tập hợp các công thức toán học. Về cơ bản, nó là một chương trình cho phép người dùng quan sát một hoạt động thông qua mô phỏng mà không thực sự thực hiện hoạt động đó. Phần mềm mô phỏng được sử dụng rộng rãi để thiết kế thiết bị sao cho sản phẩm cuối cùng sẽ gần với thông số kỹ thuật thiết kế nhất có thể mà không tốn kém trong việc sửa đổi quy trình. Phần mềm mô phỏng với phản hồi thời gian thực mang lại các kết quả có tính tham khảo hữu ích đối với nhà nghiên cứu. Như đã trình bày trong phần Mở đầu, việc đánh giá một tô-pô mạng được thực hiện bởi hai giai đoạn: đánh giá bằng phân tích đồ thị và đánh giá bằng thực nghiệm mô phỏng. Đánh giá bằng phân tích đồ thị được sử dụng để tính toán các yếu tố đồ thị như khoảng cách giữa các nút mạng, sự liên kết của các nút mạng để tính toán các tham số hiệu năng (tĩnh). Đánh giá bằng thực nghiệm thông qua các công cụ mô phỏng thực hiện giả lập quá trình truyền tin để tính toán các tham số động như là thông lượng hay độ trễ. Quá trình mô phỏng được thực hiện bởi các giải thuật, mà chúng được thực hiện trên máy tính vật lý và giả lập quá trình truyền tin giữa các nút mạng [10]. Công cụ mô phỏng hỗ trợ khảo sát hành vi của mạng khi thực hiện truyền tin - ở đây là khả năng chịu tải của mạng trong một chu kỳ quan sát. 29
30. Các công cụ mô phỏng được chia thành 3 khối cơ bản: Thiết lập tham số, Mô phỏng và Kết quả mô phỏng. Trong khối thiết lập tham số, cho phép người sử dụng có thể cài đặt các tham số đầu vào để khởi tạo giá trị ban đầu. Đối với công cụ mô phỏng đánh giá hiệu năng mạng, các tham số cơ bản là loại tô-pô mạng, kích thước tô-pô, kích thước mỗi chiều của tô-pô (số nút mạng tương ứng với mỗi chiều). Ngoài ra, hệ thống có thể cho phép khai báo thêm các tham số khác như số liên kết ngẫu nhiên, hoặc bậc đỉnh tại mỗi nút mạng. Kịch bản định tuyến cũng là một thiết lập tham số đầu vào của hệ thống. Các kịch bản định tuyến cũng có thể được cài đặt sẵn hoặc được khai báo thêm bởi người sử dụng bằng việc bổ sung thêm các thuật toán định tuyến mới. Một giải pháp tô-pô mạng mới bao gồm 2 thành phần: tô-pô mạng và thuật toán định tuyến. Do đó, kịch bản đánh giá sẽ xác định tô-pô mạng và giải thuật định tuyến như là các yếu tố đầu vào để thực hiện mô phỏng. CÔNG CỤ MÔ PHỎNG Thiết lập tham số Mô phỏng Kết quả Tham số hệ thống Theo kịch bản Vẽ sơ đồ tô-pô Kịch bản định tuyến Tái hiện mô phỏng Phân tích dữ liệu Kịch bản đánh giá Hình 1. 12: Mô hình mô phỏng Khối mô phỏng sẽ thực thi quá trình truyền tin giữa các nút mạng trong tô-pô được chọn theo thuật toán định tuyến được chọn tương ứng (từ kịch bản đánh giá). Trong quá trình này, các sự kiện rời rạc sẽ được thực thi để tiến hành gửi các gói tin, quản lý gói tin và tính toán các thông số hiệu năng mạng. Một trong những vấn đề mô phỏng là các Sự kiện rời rạc (Discrete Event Simulation - DES), trong đó, hệ thống sử dụng DES để tạo ra các sự kiện: bắt đầu truyền tin, kết thúc truyền tin, thiết lập thời gian giới hạn truyền tin, quản lý gói tin. Bên cạnh đó, để mô phỏng được hoạt động truyền tin tại mỗi nút mạng (các thiểt bị switch tương ứng), công cụ mô phỏng cũng cần phải được thiết lập các hàng đợi gói tin và lặp sự kiện. Khối kết quả sẽ thực thi việc vẽ lại sơ đồ tô-pô và thực hiện ảo hóa, tuy nhiên, với những kích thước mạng lớn (hơn 1000 nút mạng), việc vẽ lại sơ đồ trở nên không khả thi và khó thực hiện. 1.2. Giới thiệu bài toán và các nghiên cứu liên quan 1.2.1. Bài toán nghiên cứu Trong phần mở đầu, NCS đã trình bày tổng quan lĩnh vực thiết kế giải pháp tô- pô mạng liên kết. Đây là một chủ đề truyền thống của hoạt động nghiên cứu mạng, phát 30
31. triển mở rộng trong vài thập kỷ gần đây được các nhà khoa học quan tâm nhiều, đặc biệt là ứng dụng tại các DC hiện đại. Các phương thức tạo ra các tô-pô mạng hiện đại được chú trọng nghiên cứu nhằm giải quyết các vấn đề mới, cấp bách mà công nghệ của các tô-pô truyền thống không đáp ứng được chất lượng ngày càng cao mà các DC hiện đại yêu cầu. Thông thường, các cấu trúc tô-pô truyền thống đáp ứng kém hiệu quả đối với các ứng dụng khi mà độ trễ toàn mạng tăng cao, như là tính toán song song ồ ạt hoặc chúng ít có khả năng mở rộng do tính chất cấu trúc cứng nhắc khi mà sự mở rộng nhanh chóng trở thành vấn đề thường xuyên, then chốt đối với các DC hiện đại. Ví dụ, trước đây các tô-pô chuẩn tắc dạng - ary 푛-cube, với kỹ thuật định tuyến theo chiều (DOR – Dimension Order Routing) hoặc giao thức Duato [5], thường được sử dụng trong các siêu máy tính như là BlueGene/L Anton-2 [11] hoặc Cray XT5 [12]. Cấu trúc tô-pô này đòi hỏi ( × 푛)/4 trung bình độ dài tính theo hop, và đường kính mạng khá lớn ( × 푛)/2, với chẵn2. Một hạn chế quan trọng của cấu trúc chuẩn tắc này là sự tuân thủ định nghĩa cấu trúc mạng ( 푛 đỉnh), và do đó không thể hỗ trợ mở rộng phát triển mạng một cách dễ dàng, mà vấn đề đó lại là yêu cầu cao của các DC hiện đại, ví dụ, khả năng thêm mới các máy chủ và khả năng mở rộng mạng đối với DC [13, 14]. Với kích thước mạng càng ngày càng lớn, các vấn đề về tiết kiệm chi phí thiết bị và cáp, tiết kiệm năng lượng khi tải thấp, , trở thành những chủ đề rất đáng quan tâm. Có thể thấy điều này trong hàng loạt nghiên cứu trong giai đoạn gần đây về thiết kế mạng trong DC [15, 16, 17, 18, 19, 20, 21]. Các nhà nghiên cứu đang tích cực đề xuất những tiếp cận, những dạng kiến trúc tô-pô mới phù hợp hơn cho các yêu cầu hiện đại [13, 14, 22, 23, 24, 25, 26]. Các kiến trúc tô-pô mới gần đây được thiết kế theo hai dạng chính, dạng thứ nhất là cấu trúc chuẩn tắc (dạng cây), ví dụ như Fat-Tree và dạng thứ hai là cấu trúc mạng ngẫu nhiên, như đã đề cập trên, ví dụ như JellyFish. Ngoài những ưu điểm và hạn chế đã được trình bày sơ lược trong phần mở đầu, các dạng tô-pô nói trên vẫn tồn tại hạn chế chung là sử dụng các thiết bị chuyên dụng có bậc đỉnh cao, giá thành cao. Để khắc phục sự hạn chế về tính phức tạp, tính co giãn quy mô và tính thích nghi nhằm đáp ứng những yêu cầu của DC hiện đại như đã đề cập trong phần Mở đầu, một cách tiếp cận được phát triển gần đây là sử dụng các mô hình mạng ngẫu nhiên (các đồ thị ngẫu nhiên truyền thống, các mạng đồ thị thế giới nhỏ: smallworld network, mạng liên kết ngẫu nhiên, ), trong việc thiết kế các tô-pô mạng mà có thể hỗ trợ hiệu quả để đạt được những hiệu năng quan trọng. Thông thường, tô-pô ngẫu nhiên được xây dựng bằng việc bổ sung các liên kết ngẫu nhiên giữa các cặp nút mạng của tô-pô mạng truyền thống (ví dụ đồ thị dạng lưới). Các liên kết ngẫu nhiên có thể được tạo ra bởi một phân bố xác suất nào đó. Như đã chỉ ra trong bài báo [27], trong mô hình mạng ngẫu nhiên, đường kính đồ thị có thể ngắn hơn và độ trễ truyền thông giảm đáng kể hơn khi so sánh với các tô-pô truyền thống (cùng kích thước mạng, cùng bậc đỉnh tại mỗi nút). Trong khi đó, sự mở rộng của mạng có thể được phát triển tự nhiên với mô hình mạng ngẫu nhiên, 2 Một số cấu trúc tô-pô mạng đồng nhất, như là De Bruijn, Starm Kautz đạt được trung bình đường đi ngắn nhất tốt hơn khi so với cấu trúc tô-pô k-ary n-cube 31
32. tạo ra sự hấp dẫn đối với các mạng trong DC lớn, như tại [13]. Sự gia tăng tự nhiên này nhằm cải tiến sự hạn chế cứng nhắc của các dạng tô-pô chuẩn tắc, như đã đề cập trên. Mặc dù có sự hấp dẫn về sự gia tăng mở rộng tự nhiên, mô hình mạng ngẫu nhiên cũng tồn tại các hạn chế quan trọng, bao gồm sự giới hạn tính co giãn trong việc định tuyến, như đã trình bày trong [27]. Việc tạo ra các liên kết ngẫu nhiên với một phân bố xác suất đều nào đó đều dẫn đến vấn đề khó khăn lớn trong việc xây dựng các giải thuật định tuyến. Bởi yếu tố ngẫu nhiên phá vỡ các quy luật định tuyến thông thường. Đối với các tô-pô chuẩn tắc, việc định tuyến được xác định theo chiều (DOR) hoặc giao thức Duato [5], hoặc thuật toán đường đi ngắn nhất (SPR: Shortest Path Routing) với việc sử dụng thông tin toàn bộ của tô-pô. Tuy nhiên, trên các tô-pô mạng ngẫu nhiên, việc thực thi SPR đòi hỏi mỗi nút mạng phải định dạng bảng định tuyến có kích thước lớn (bao gồm những bản ghi để định tuyến tới tất cả các nút mạng khác với kích thước Ω(푛푙표 푛), và đương nhiên, toàn bộ cài đặt mạng đòi hỏi thời gian xây dựng bảng định tuyến cho mỗi nút mạng là Ω(푛2). Đây chính là điểm yếu lớn của cách tiếp cận tô-pô mạng ngẫu nhiên và trở thành điểm nghẽn (bottle-neck) khi số nút mạng tăng cao, ví dụ, hàng trăm nghìn nút tính toán, bởi sự giới hạn về bộ nhớ3 (lưu trữ các thông tin định tuyến) và tốc độ tính toán của các thiết bị chuyển mạch. Thông tin định tuyến được lưu trữ trong bộ nhớ của các thiết bị chuyển mạch như là các bản ghi trong mỗi bảng định tuyến. Đây chính là sự giới hạn vật lý về việc lưu trữ thông tin. Do vậy, đối với các tô-pô mạng ngẫu nhiên cần xem xét thiết kế định tuyến rút gọn đảm bảo kích thước bảng định tuyến (푅 푆: routing table size) nhỏ trong khi vẫn duy trì 푅푃퐿 đủ ngắn. Như là một tiếp cận mới gần đây, mô hình mạng ngẫu nhiên được sử dụng trong việc thiết kế các tô-pô mạng liên kết mà có thể đáp ứng được chất lượng hiệu năng quan trọng như là tính linh hoạt, tính mở rộng tự nhiên, khai thác các thiết bị có bậc đỉnh thấp và giá thành rẻ. Tuy nhiên, như đã đề cập, việc xác định luật định tuyến là hạn chế lớn đối với tô-pô mạng ngẫu nhiên. Một hướng tiếp cận xây dựng thuật toán định tuyến rút gọn (compact routing) được các nhà nghiên cứu đề xuất (Cowen [28], Thorup&Zwick [29]) hướng tới xây dựng thuật toán định tuyến mà ít sử dụng thông tin được lưu trữ tại các nút trên các tô-pô mạng liên kết. NCS hướng tới tìm kiếm giải pháp định tuyến rút gọn mà có thể khai thác tốt các tính chất đặc trưng của mạng ngẫu nhiên (khai thác tính chất các liên kết dài giữa các nút mạng ở xa, nhằm làm giảm chiều dài đường định tuyến), hay cải tiến thuật toán định tuyến rút gọn phổ quát như đã nêu trên. Với những vấn đề nêu trên, bài toán đặt ra là làm thế nào để xây dựng các giải pháp định tuyến rút gọn cho mô hình mạng ngẫu nhiên hướng tới việc khai thác các tính chất đặc trưng của mô hình ngẫu nhiên (khai thác các liên kết dài để giảm 푆푃퐿) và làm giảm đáng kể 푅 푆 nhưng vẫn duy trì chiều dài định tuyến cận tối ưu (chỉ một vài sai khác so với thuật toán định tuyến SPR). Mục tiêu luận án là nghiên cứu và đề xuất các thuật toán định tuyến rút gọn mà có thể khai thác tốt các tính chất của tô-pô mạng ngẫu nhiên có kích thước lớn, phù hợp 3 48.000 bản ghi đối với các thiết bị Infiniband và 32.000 bản ghi đối với các thiết bị chuyển mạch thông thường 32
33. với các DC hiện nay. Đồng thời, để đánh giá hiệu quả của thuật toán định tuyến trên các tô-pô mạng có kích thước lớn (cỡ hàng trăm nghìn nút tính toán), cần phải có một công cụ phần mềm có khả năng mô phỏng và đánh giá được hiệu năng mạng. Do đó, luận án sẽ tổng hợp và giới thiệu hai bài toán nghiên cứu chính trong nội dung tiếp theo. 1.2.1.1. BÀI TOÁN 1: Thiết kế định tuyến cho mạng ngẫu nhiên với kích thước bảng định tuyến nhỏ trong khi vẫn duy trì tốt các yếu tố hiệu năng Trong hướng nghiên cứu chính này, NCS xem xét giải quyết bài toán định tuyến rút gọn (compact routing) cho tô-pô mạng ngẫu nhiên tựa đồ thị lưới, tức là tô-pô mạng ngẫu nhiên cảm sinh từ đồ thị dạng lưới. Đồ thị dạng lưới có thể xem là một đặc trưng phổ biến của một số lớn các mạng liên kết đã biết (mô tả sơ đồ lắp đặt và kết nối các thiết bị mạng; khảo cứu thêm mục 1.2.3.1) và mô hình tô-pô mạng ngẫu nhiên tựa đồ thị lưới đang được giới nghiên cứu quan tâm nhiều. Cơ chế định tuyến phân tán thông qua thao tác tra bảng thông tin định tuyến lại mỗi nút được xem là lựa chọn phổ biến trong hầu hết mạng liên kết (có thể nói thiết bị chuyển mạch – switch – được sinh ra nhằm phục vụ cho cơ chế này). Vì vậy, nói một cách đơn giản, xây dựng thuật toán định tuyến là xây dựng các bảng tra thông tin định tuyến tại các nút đồ thị để phục vụ cho cơ chế đinh tuyến phân tán tra bảng. Nghiên cứu định tuyến rút gọn cho mô hình mạng ngẫu nhiên dạng lưới chính là tìm cách xây dựng các bảng định tuyến phân tán lưu trữ tại mỗi nút có kích thước nhỏ hợp lý mà đảm bảo duy trì hiệu năng cao (tìm đường đi ngắn hợp lý). Với các thuật toán định tuyến đường đi ngắn nhất, kích thước bảng định tuyến tại mỗi nút mạng là ( ). Tuy nhiên, khi số lượng nút mạng tăng cao, khả năng lưu trữ thông tin định tuyến trở nên bị hạn chế, bởi sự giới hạn về kích thước bộ nhớ vật lý tại mỗi nút mạng. Do vậy, kích thước bảng định tuyến (RTS – Routing Table Size) nhỏ là tiêu chí quan trọng của bài toán nghiên cứu, (푅 푆∀ ∈ → 푖푛). Bài toán định tuyến rút gọn cho mạng ngẫu nhiên dạng lưới: Cho đồ thị dạng lưới = ( , ). Trong đó, là tập đỉnh, thể hiện cho tập các nút mạng (tổng số nút mạng = | |) và là tập cạnh, thể hiện cho tập các liên kết giữa các nút mạng (bao gồm các liên kết ngẫu nhiên giữa các nút mạng). Mỗi nút mạng có 4 liên kết lưới với nút liên kề với nó và có liên kết ngẫu nhiên tới một số nút mạng khác. Yêu cầu: xây dựng thuật toán đánh nhãn các nút mạng và các bảng định tuyến phân tán tại các nút sao cho kích thước bảng định tuyến nhỏ trong khi vẫn duy trì các yếu tố hiệu năng đường kính mạng nhỏ, trung bình chiều dài đường định tuyến nhỏ. Sau đây chúng tôi xin đưa ra các định nghĩa khái niệm chi tiết đã sử dụng. Bảng tra thông tin định tuyến phân tán (gọi tắt: bảng định tuyến) tại mỗi nút mạng là một danh sách của các bộ 3 (Dest, Next, Info), trong đó, “Dest” là đích đến, “Next” là nút mạng tiếp theo mà nút hiện thời (chứa bảng định tuyến này) sẽ chuyển tiếp gói tin đến. Có nghĩa là, từ nút hiện thời, muốn đến Dest thì sẽ thực hiện định tuyến đến “Next”. Phần “Infor” lưu trữ thông tin bổ sung để thực hiện quyết định định tuyến, ví dụ số hop hoặc thứ tự cổng ra của nút mạng hiện thời. Kích thước bảng định tuyến là số các bộ 3 thông tin như trên. 33
34. Bảng định tuyến tại nút “1” Đồ thị Bảng định tuyến tại nút “5” STT Dest Next Infor 4 STT Dest Next Infor 1 2 1 1 2 7 1 1 5 1 2 3 2 2 3 2 2 1 2 3 4 2 2 3 3 5 1 1 6 4 5 1 1 4 4 6 2 5 6 5 2 5 5 7 6 2 Hình 1.13: Tổ chức bảng định tuyến tại nút mạng Ví dụ, tại nút mạng “1” như Hình 1.13, để đến được nút mạng “4”, nút “1” sẽ phải định tuyến tới nút mạng “2” trước với số hop để tới nút mạng “4” là 2. Tương tự, nút “5” sẽ định tuyến tới nút mạng “6” để có thể tới được nút mạng “4” trong 2 hop. Thuật toán đánh nhãn các nút: cung cấp cho các nút một mã định danh sao cho phục vụ hiệu quả cho thuật toán định tuyến. Tiên đề: Khi nút 푠 mà biết mã định danh của nút 푡 có nghĩa là 푠 tính được tọa độ của nút 푡. Khoảng cách ngắn nhất tính theo hop, của đường định tuyến 푃 푡ℎ( , ), được biểu diễn là ( , ). Đường kính mạng là đường đi có khoảng cách dài nhất trong số tất cả ( , ). Đường kính mạng được tính là max 푖푛 ( 푡ℎ( ; )). ∀( , ) ∑ 푙 푡푒푛 ( 푡ℎ( ; )) Độ trễ trung bình → 푖푛, với độ trễ trên mỗi 푃 푡ℎ( ; ) ∑ 푡ℎ( ; ) được tính bằng tổng độ trễ trên mỗi nút mạng nằm trên đường định tuyến và tổng độ trễ trên tổng chiều dài đường định tuyến. 1.2.1.2. BÀI TOÁN 2: xây dựng kiến trúc công cụ mô phỏng giả lập hỗ trợ đánh giá hiệu năng mạng liên kết Với mỗi thiết kế giải pháp tô-pô mạng mới, việc tính toán các tham số hiệu năng đóng vai trò quan trọng trong việc xác định tô-pô đó có đạt hiệu quả kỳ vọng hay không? Với các giải pháp tô-pô có kích thước nhỏ hay có cấu trúc chuẩn tắc, việc đánh giá có thể được thực hiện bởi một thuật toán chuyên dụng nào đó. Tuy nhiên, khi kích thước mạng tăng lên cao, vượt xa các kích thước mạng truyền thống thì vấn đề làm sao tổ chức đánh giá qua thực nghiệm với một mô hình mạng kích thước lớn. Đối với các công cụ mô phỏng mạng phổ biến hiện nay như NS3 [2], OMNET++ [4], hay SIMGRID [3] cũng khó có khả năng thực nghiệm đối với các mạng có kích thước lớn, ngay cả khi được thiết lập trên các máy tính hiện đại, các công cụ này cũng chỉ mới thực nghiệm được với mạng có kích thước khoảng 1.000 nút. Việc tổ chức thực nghiệm của các công cụ mô phỏng đối với các mạng ngẫu nhiên và thuật toán định tuyến tương ứng trở nên khá khó khăn4, chủ yếu là do mỗi nút tính toán trong các công cụ mô phỏng mạng phổ quát trên được thiết kế để mô phỏng đầy đủ các tầng giao thức như các kiến trúc phổ biến (mô hình OSI 4 Mỗi lần thực hiện một thực nghiệm theo một kịch bản mô phỏng cơ bản có thể là hàng giờ trong khi cần thực hiện hàng trăm thực nghiệm để so sánh đánh giá một số tô-pô mạng với nhiều chế độ hoạt động và khai thác 34
35. 7 tầng hay TCP/IP). Khối lượng xử lý lớn ở mỗi nút sẽ giới hạn kích thước tập hợp các đối tượng mạng có thể cài đặt trong hệ mô phỏng. Thông thường, hoạt động chính của các công cụ mô phỏng là tính toán các thành phần hiệu năng như đường đi ngắn nhất giữa các nút mạng được thực hiện thường xuyên. Đặc biệt, đối với mạng ngẫu nhiên, việc tính toán đường đi giữa các nút mạng và xây dựng lại thông tin bảng định tuyến là những hoạt động chính, đòi hỏi thời gian tính toán nhanh, đáp ứng được khả năng thực hiện. Do vậy, công cụ mô phỏng cần tìm kiếm một giải pháp mới nhằm giảm tải các thông tin không cần thiết, mà chỉ giữ lại các yếu tố cốt lõi (bao gồm các yếu tố liên quan đến việc định tuyến như số nút mạng, vị trí đặt nút mạng, và liên kết giữa chúng) để thực hiện đánh giá hiệu năng mạng được hiệu quả. Đồng thời, công cụ mô phỏng cũng cần được thiết lập sẵn các giải pháp tô-pô chuẩn tắc (ví dụ như 3-D Torus, Fat-Tree) và các thuật toán định tuyến đã biết (ví dụ như SPR, TZ) để thực hiện đánh giá và so sánh hiệu năng so với giải pháp tô-pô mạng mới. Ngoài ra, như là một trường hợp cụ thể về việc đề xuất giải pháp tô-pô mới với chi phí triển khai thấp mà vẫn đảm bảo tính linh hoạt cao như dễ mở rộng và đáp ứng điều kiện hạn chế về không gian như: kết hợp nhiều phòng máy chủ có diện tích sàn bị giới hạn, không liền kề. Các kiến trúc tô-pô mạng liên kết được ứng dụng phổ biến trên thế giới là không thực sự phù hợp cho những điều kiện thực tế đặc thù này. Hiện nay, tại Việt Nam cũng chưa có các nghiên cứu cụ thể về vấn đề đã nêu trên. Bài toán này xuất phát từ thực tiễn xây dựng và phát triển các DC có kích thước vừa và nhỏ của các doanh nghiệp (ví dụ như ngân hàng, thư viện dữ liệu số, trung tâm báo chí, ) chưa được quan tâm và nghiên cứu, đặc biệt là tại Việt nam. Ngoài phương án thuê địa điểm đặt máy chủ tại các DC lớn của các doanh nghiệp công nghệ hàng đầu như Viettel, VNPT, FPT , các doanh nghiệp đủ lớn cũng đang mở rộng thêm phương án đầu tư xây dựng mới các DC cỡ nhỏ (khoảng vài chục đến vài trăm máy chủ), nhằm chủ động trong việc đầu tư, khai thác hệ thống. Ban đầu các DC này có thể chỉ phục vụ hoạt động riêng của doanh nghiệp nhưng sau đó nó có thể mở rộng lên khi doanh nghiệp mở rộng kinh doanh và có thể kết hợp cho bên ngoài thuê bao khai thác. Vì thế, nét đặc thù của xu hướng này là việc thiết lập không gian cho DC cần mang tính linh hoạt, mềm dẻo để có thể mở rộng dần, thích hợp với việc các DC có thể tăng trưởng kích thước liên tục (từ cỡ nhỏ, vài chục đến hàng trăm máy, lên cỡ vừa, hàng nghìn máy). Khác với việc xây dựng các DC lớn thường bao gồm việc xây dựng những tòa nhà hay khu vực không gian biệt lập với các điều kiện lý tưởng, việc phương án xây dựng các DC vừa và nhỏ thường ưu tiên tính kinh tế bằng cách khai thác các khoảng không gian còn trống hay được chuyển đổi chức năng trong các tòa nhà doanh nghiệp đã có sẵn. Những không gian mang tính huy động gom lại này thường có những hạn chế như không đủ rộng lớn và liên tục, có thể là sự kết hợp của nhiều phòng hay mặt sàn sử dụng tách rời nhau (thậm chí có thể nằm trên nhiều tầng tách biệt của một tòa nhà). Ở một số tình huống khác, một DC cỡ nhỏ ban đầu có thể được phát triển dần dần về qui mô và có thể “phình ra” vượt quá sự cho phép của không gian thiết kế ban đầu. Thường là do khả năng huy động nguồn vốn ban đầu, DC có thể có kích thước nhỏ và bố trí lắp 35
36. đặt trong một không gian vừa phải, nhưng nếu sau đó hoạt động hiệu quả, doanh nghiệp có thể huy động thêm vốn và muốn tìm cách mở rộng kích thước DC một cách linh hoạt. Do đó không gian lắp đặt ban đầu có thể không còn chỗ và phải tiến hành xem xét việc mở rộng sang khu vực mới (mặt sàn mới) và cần tìm phương án giải quyết việc kết nối giữa 2 khu vực sao cho hiệu quả nhất. NCS nghiên cứu xây dựng một tô-pô mạng liên kết phù hợp nhất, tức là đạt được hiệu năng và tính kinh tế thích hợp, cho dạng DC có tính dễ mở rộng tăng dần đồng thời có thể bố trí lắp đặt trong một không gian thiếu liên tục, tức là có thể là sự kết hợp của nhiều mặt sàn tách rời và có khoảng cách nhất định giữa chúng. 1.2.2. Tình hình nghiên cứu Từ lâu các nhà khoa học đã đặc biệt quan tâm đến vấn đề thiết kế tô-pô dùng bậc đỉnh thấp (low-radix) hay bậc đỉnh cao (high-radix) cho các hệ thống tính toán rất lớn. IBM đã phát triển các 3D Torus cho siêu máy tính BlueGene/L và 5-D Torus cho BlueGene/Q [11] với các mạng bậc thấp, và Dragonfly [30] cho Power 775 với mạng bậc cao (Power 775 được coi như một “data-center-in-a-rack”). Lịch sử phát triển cho thấy các tô-pô bậc đỉnh thấp đã được sử dụng phổ biến trong các hệ thống tính toán hiệu năng cao nhờ có các ưu điểm như: (i) cơ chế quản lý lỗi đơn giản, (ii) dễ dàng tích hợp định tuyến mạng và các lõi tính toán vào từng chip xử lý hay mạch đơn, (iii) cách bố trí switch mạng trong không gian vật lý tương đối tiết kiệm và giao thức truyền thông dễ chỉnh sửa. Chính vì vậy mà 6 trên 10 các siêu máy tính trong xếp hạng TOP500 vào tháng 6/2012 sử dụng các phiên bản của Torus. Trong các nghiên cứu trước đây, đồ thị ngẫu nhiên đã được biết đến với ưu điểm về đường kính nhỏ. Nhờ hiệu ứng thu nhỏ đường kính mạng một cách đáng kể, các liên kết ngẫu nhiên đã được khai thác để mô hình hóa các mạng phức tạp ở thế giới thực như các mạng xã hội, mạng Internet. Đặc tính “thế giới nhỏ” (small-world) của những mạng này đã nhận được nhiều sự quan tâm trong giới khoa học, bắt nguồn từ bài báo kinh điển của Watts và Strogatz [8]. Hiệu ứng thế giới nhỏ nhìn chung thể hiện một mạng có đường kính nhỏ, bậc đỉnh thấp và hỗ trợ tìm kiếm phân tán, nghĩa là kỹ thuật tìm đường chỉ sử dụng thông tin cục bộ. Kleinberg trong bài báo [31] về hiệu ứng thế giới nhỏ từ góc nhìn giải thuật đã chỉ ra rằng việc tăng cường có lựa chọn một số liên kết đi xa có thể giúp giảm thiểu nhanh chóng đường kính mạng và cung cấp khả năng tìm kiếm phân tán. Chính vì vậy, đồ thị thế giới nhỏ và ngẫu nhiên đã được đề xuất để xây dựng các DC với khả năng mở rộng, kháng lỗi và thông lượng cao trong các nghiên cứu gần đây [13, 14]. Tác giả Koibuchi [32], cũng đã giới thiệu tô-pô gọi là 퐿 − − , trong đó, bậc , có đường kính là lô-ga-rit với = 푙표 (푛) và là số liên kết ngẫu nhiên được thêm vào mỗi nút trong 퐿 − . Những đồ thị này có bậc hằng số và đường kính lô- ga-rit với , cố định. Mạng thế giới nhỏ của Kleinberg trong [31] gồm 1 lưới ô vuông với các đường nối tắt được thêm vào cũng đã thể hiện đầy đủ ưu điểm của hiệu ứng đồ thị thế giới nhỏ. Tuy nhiên, những tô-pô này có những nhược điểm quan trọng, 퐿 − log (푛) có đường kính lô-ga-rit nhưng bậc 푙표 (푛) lớn, 퐿 − − có đường kính lô- 36
37. ga-rit và bậc hằng số nhưng giải thuật tìm đường yêu cầu những thông tin của toàn bộ tô-pô, và quan trọng nhất là chi phí cáp nối là quá lớn. Để giảm thiểu chi phí cáp nối trong mạng, có 2 phương pháp đã được đề xuất bởi Koibuchi và đồng sự [27, 33], trong đó họ tạo ra các tô-pô ngẫu nhiên có độ dài đường đi nhỏ gần như các tô-pô ngẫu nhiên hoàn toàn và cải thiện cách bố trí của chúng trong không gian vật lý. Một lợi thế khác của mô hình đồ thị ngẫu nhiên mới được chú ý rất gần đây là khả năng dễ đáp ứng với việc mở rộng liên tục của mạng liên kết, một yêu cầu quan trọng được đặt ra trong thiết kế các DC hiện đại [13, 14]. Việc mở rộng này là do nhu cầu tăng qui mô, tức là bổ sung thêm máy chủ và thiết bị mạng, khi nhu cầu của khách hàng tăng cao hoặc nhu cầu lớn của các ứng dụng tiêu tốn tài nguyên. Mở rộng dần theo kế hoạch được coi là một giải pháp tốt nhằm tránh đầu tư quá lớn ban đầu. Các tô-pô truyền thống rất khó đáp ứng sự thay đổi qui mô này do bị hạn chế về cấu trúc cứng nhắc của tô-pô (thậm chí số nút của mạng liên kết là những giá trị cố định). Trái lại, nhờ bản chất cơ chế tạo liên kết ngẫu nhiên, mạng liên kết sử dụng đồ thị ngẫu nhiên rất dễ đáp ứng tính co giãn qui mô. Hơn nữa sự dư thừa (vừa phải) của các liên kết ngẫu nhiên tạo ra nhiều đường nối dự phòng, rất thích hợp cho các cơ chế dung lỗi hoạt động khi có sự cố của nút tính toán hoặc thiết bị trong mạng. Một vấn đề cần quan tâm khác là làm sao để chống khóa chết (deadlock) cho giải thuật định tuyến mạng [32, 33]. Khóa chết là tình trạng mà một nhóm các thông điệp không thể di chuyển tiếp bởi vì chúng đang đợi thông điệp khác giải phóng tài nguyên, có thể là bộ đệm hoặc các kênh, cuối cùng dẫn tới làm tê liệt toàn bộ mạng. Ngày nay, việc sử dụng các cơ chế chuyển mạch tốc độ cao như virtual cut-through hay wormhole còn dẫn tới nguy cơ bị tắc nghẽn cao hơn nữa, đặt ra yêu cầu kiểm soát việc cấp phát tài nguyên mạng trong cách tiếp cận tránh khóa chết. Tại Việt nam, hiện nay vấn đề nghiên cứu tô-pô mạng kiểu mới chưa được phổ biến, nhưng sự phát triển nhanh chóng về ứng dụng các dạng lưới tính toán mới, các DC hiện đại đang tạo nên một nhu cầu sẽ cấp bách trong tương lai rất gần nhằm tìm ra các giải pháp tô-pô mạng liên kết hữu hiệu, với mục tiêu khai thác hiệu quả, tránh tốn kém lãng phí trong các dự án trung tâm tính toán đầu tư lớn đang và sẽ triển khai. Có hai vấn đề cơ bản cần phải được đặt ra và giải quyết tốt hơn nhiều so với các giải pháp truyền thống: (1) đảm bảo tính co giãn qui mô (scalability) để giảm thiểu chi phí trong vận hành và bảo trì, (2) đưa ra phương pháp giải bài toán kinh tế - kỹ thuật như sau: biết trước kinh phí đầu tư thiết bị phần cứng, thiết kế chi tiết giải pháp tô-pô liên kết hiệu quả, tối ưu các thông số hiệu năng. Điểm qua tình hình công nghệ thông tin liên quan ở Việt nam để thấy được tầm quan trọng của các vấn đề nêu trên. Một trong những điểm nóng về đầu tư công nghệ thông tin ở Việt nam hiện nay là xây dựng các DC hiện đại. Hiện tại, Chính phủ, một số Bộ và các tập đoàn kinh tế viễn thông đều đã đề xuất hay triển khai các dự án DC tiêu chuẩn cao. Ví dụ, các dự án phát triển DC của FPT Telecome năm 2020, dự kiến đầu tư hàng ngàn tỉ đồng, DC Tân Thuận – TP Hồ Chí Minh: 177 tỉ đồng, DC Cầu Giấy – Hà Nội: 213 tỉ đồng, DC Quận 9 – TP Hồ Chí Minh: 150 tỉ đồng, DC Đà Nẵng: 40 tỉ đồng. 37
38. Dự án DC Đà nẵng thuộc Đề án Xây dựng thành phố thông minh của Ủy ban Nhân dân Thành phố Đà Nẵng năm 2019-2021 dự kiến đầu tư 68 tỉ đồng. Với quy mô ngày càng tăng cao, ví dụ, CMC hơn 7000 máy chủ, Viettel IDC với hơn 40,000 máy chủ theo tiêu chuẩn Tier 3 [34] (tiêu chuẩn cao nhất hiện nay để đánh giá một DC ở Việt Nam). Tương tự, các tập đoàn viễn thông khác như VNPT hay VTC đều đang có những dự án lớn, tham vọng trong lĩnh vực đầu tư này. Một số cơ quan bộ như Bộ Tài chính cũng đã công bố dự án xây dựng DC ngành. Các DC hiện đại tại Việt nam đều có tầm cỡ hàng chục nghìn máy chủ, với số tiền đầu tư tính bằng hàng chục triệu đô Mỹ. Những thông tin trên cho thấy sự quyết liệt của chính sách đầu tư CNTT trong xây dựng các DC tại Việt nam. Rõ ràng với tình hình trên, trong tương lai gần vấn đề khai thác và vận hành hiệu quả, bảo trì và nâng cấp sẽ trở nên trọng yếu, nhằm đảm bảo hiệu quả kinh tế mong muốn. Mặc dù ở trên chủ yếu phân tích và lấy ví dụ về các DC hiện đại, các vấn đề và tiếp cận mới đề xuất có thể ứng dụng bao quát hơn, trên nhiều hệ thống lưới tính toán khác. Chẳng hạn trong lĩnh vực xây dựng lưới điện thông minh (smart grid), việc xây dựng tô-pô liên kết cho mạng lõi (backbone WAN) phủ khắp địa bàn một vùng lớn hay quốc gia cũng sẽ phải đối mặt với hai vấn đề đảm bảo tính co giãn qui mô (scalabililty) và bài toán kinh tế - kỹ thuật “xây dựng tô mạng có hiệu năng tối ưu khi biết trước mức chi phí thiết bị”. Hiện nay vấn đề xây dựng lưới điện thông minh đã được đặt ra ở Việt nam và tập đoàn điện lực EVN đang rất tích cực nghiên cứu xây dựng phương án; EVN đã xác định rằng xây dựng lưới điện thông minh là một bước đi hết sức quan trọng theo xu hướng quốc tế, hiện đại hóa mà nhằm sử dụng, khai thác hiệu quả các nguồn cung để giảm thiểu việc đầu tư mới đòi hỏi do tình hình phát triển. Rõ ràng với tình hình trên, trong tương lai gần vấn đề khai thác và vận hành hiệu quả, bảo trì và nâng cấp sẽ trở nên trọng yếu, nhằm đảm bảo hiệu quả kinh tế mong muốn. Việc xây dựng giải pháp tô-pô mạng liên kết phù hợp sẽ trở nên một bài toán kinh tế kỹ thuật then chốt ở đây. Thứ nhất như đã nói ở trên, các tô-pô mạng liên kết truyền thống thường không đáp ứng tốt tính co giãn qui mô; cụ thể là sự thay đổi các nút tính toán sẽ kéo theo các thao tác cập nhật thay đổi hệ thống phức tạp, tốn kém. Đây là một trọng các vấn đề nan giải khi đi vào vận hành và khai thác các hệ thống với tập hợp nút tính toán lớn, thường xuyên có cập nhật như các DC. Thứ hai, các giải pháp tô-pô truyền thống chưa giải quyết được bài toán tối ưu cân bằng giữa chi phí thiết lập (thiết bị và cáp kết nối các nút) và các thông số hiệu năng cơ bản như độ trễ truyền tin và thông lượng. 1.2.3. Các nghiên cứu liên quan Cách tiếp cận cơ bản của các nhà khoa học trong việc đề xuất giải pháp mới bao gồm: i) Thiết kế tô-pô mới và áp dụng các thuật toán định tuyến có sẵn, ví dụ SPR [5, 9], định tuyến rút gọn [28, 29], ; ii) Thiết kế giải thuật định tuyến mới và áp dụng cho các tô-pô có sẵn như 2-D Torus, 3-D Torus, Fat-Tree [23]; iii) Thiết kế tô-pô mới và thuật toán định tuyến mới, ví dụ như tô-pô JellyFish với thuật toán định tuyến -shortest path [13]. Phần này trình bày các nghiên cứu liên quan, được quan tâm đề xuất gần đây. 38
39. 1.2.3.1. Mạng liên kết ngẫu nhiên Như đã được đề cập trong mục 1.1.1.1, mạng ngẫu nhiên được xây dựng dựa trên các tô-pô mạng cơ bản như Mesh, Hyper-cube, Flat Butterfly, , với các liên kết lưới cơ bản hoặc các liên kết vòng, ví dụ, 2-D Torus, 3-D Torus, giữa các nút mạng và nút hàng xóm của nó và được bổ sung các liên kết dài giữa các nút mạng ở xa nhau, mà các liên kết dài đó được tạo ra bởi một phân bố xác suất nào đó. Các tô-pô ngẫu nhiên điển hình như JellyFish [13] và Smallworld [14, 31]. Mạng ngẫu nhiên được trình bày trong [27], trong đó các liên kết ngẫu nhiên còn được gọi là các “đường tắt” (Shortcut), được tạo ra bởi một phân bố xác suất đều (đối với mọi nút mạng). Để đảm bảo tính chuẩn tắc của tô- pô mạng, kỹ thuật này phải đảm bảo các nút có cùng chung bậc đỉnh. Ví dụ, với số liên kết ngẫu nhiên = 2, tại mỗi nút bất kỳ sẽ có một liên kết đi ra (từ nút kết nối tới nút khác) và một liên kết đi vào (từ nút khác kết nối tới nút ). Mạng ngẫu nhiên chuẩn tắc có thể được tạo ra bởi việc bổ sung các liên kết ngẫu nhiên vào các mạng cơ sở điển hình như là mạng vòng (Ring Network) hoặc mạng lưới (Grid Network). Các phân tích tại [27] cho thấy phương thức đó có thể làm giảm đáng kể đường kính mạng bằng việc tận dụng lợi thế việc bổ sung các liên kết ngẫu nhiên, làm gia tăng liên kết các nút mạng ở xa. Mạng mới tạo ra cũng được tận dụng lợi thế tính chất chuẩn tắc của các mạng cơ sở. Ví dụ, tác giả Shin [14] đã đề xuất mạng ngẫu nhiên bậc đỉnh 6 đối với DC, dựa trên mô hình thế giới nhỏ của Kleinberg [31], bắt đầu với tô- pô 2-D Torus (hoặc 3-D Torus) và bổ sung thêm các liên kết ngẫu nhiên. Mô hình mạng thế giới nhỏ của Kleinberg [31] được cấu trúc từ một mạng dạng lưới mà tại đó, mỗi nút mạng có các liên kết tới các nút khác trong khoảng khoảng cách lưới ( _ 푖 _ℎ표 ). Mỗi nút mạng cũng có liên kết ngẫu nhiên được tạo ra bởi một phân bố xác suất liên quan tới khoảng cách liên kết, gọi ( ; 푣) là khoảng cách lưới giữa nút và nút 푣. Mỗi liên kết ngẫu nhiên đi ra từ tới nút 푣 có xác suất là ( ; 푣)−푞, với 푞5 là tham số được gọi là thành phần phân cụm. Ví dụ, Koibuchi [27] đã xây dựng đồ thị ngẫu nhiên, được gọi là TOPO- , trong đó TOPO là tên của đồ thị cơ bản (ví dụ: Torus, Mesh, ), và là số liên kết được thêm tại mỗi nút mạng. Để thêm các liên kết ngẫu nhiên đối với một đồ thị , với bậc đỉnh cơ bản là , tạo thành đồ thị ′ với số bậc đỉnh là + , dễ dàng thêm cặp kết nối giữa hai đỉnh bất kỳ trong đồ thị . Việc bổ sung liên kết ngẫu nhiên được thực hiện bằng việc xét các cặp đỉnh một cách tuần tự. Đường kính mạng và 푅푃퐿 được xem là các yếu tố tác động chính đối với độ trễ khi truyền gói tin giữa bất kỳ cặp nguồn đích nào trong mạng. Mạng ngẫu nhiên có thể được tạo ra với số lượng tùy chọn các thiết bị kết nối và tùy chọn số lượng các liên kết ngẫu nhiên để đảm bảo tính chất co giãn của mạng. Mạng ngẫu nhiên có đường kính mạng nhỏ hơn và độ trễ ít hơn khi so sánh với các tô-pô mạng chuẩn tắc như Torus, Mesh, Hyper-cube [27]. Do mạng ngẫu nhiên khai thác được các liên kết ở xa (giữa các nút mạng) làm giảm số hop khi thực hiện tính toán định tuyến. 5 Theo Kleinberg [31], mạng đồ thị thế giới nhỏ đạt được hiệu năng tốt, theo tiêu chí 푅푃퐿, khi giá trị 푞 = (1.5,2.5) 39