Luận án Tiến sĩ Công nghệ thông tin: 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á

Chia sẻ: Hiền Nguyễn | Ngày: | Loại File: PDF | Số trang:137

Thêm vào BST

Báo xấu

19
lượt xem 6
download

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

Luận án 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; đề 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.

Chủ đề:

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

Lưu

Nội dung Text: Luận án Tiến sĩ Công nghệ thông tin: 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Ờ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
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
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
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
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 https://www.top500.org/ thống mạng máy tính hiện nay. 5
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
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
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
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
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
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
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
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
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
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
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
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
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
(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à, 𝑆𝑃 = 𝑆𝑐1 và đí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
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