Nghiên cứu giải pháp định tuyến mạng hiệu năng cao và công cụ đánh giá - Luận án TS

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Kiều Thành Chung 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Á LUẬN ÁN TIẾN SĨ KỸ THUẬT PHẦN MỀM HÀ NỘI – 2021 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Kiều Thành Chung 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Á Ngành: Kỹ thuật phần mềm Mã số: 9480103 LUẬN ÁN TIẾN SĨ KỸ THUẬT PHẦN MỀM NGƯỜI HƯỚNG DẪN KHOA HỌC 1. PHẠM ĐĂNG HẢI HÀ NỘI – 2020 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. 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. 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Ẽ. 9 CHƢƠNG 1: TỔNG QUAN. Tô-pô mạng (Network topology). Giới thiệu giải thuật định tuyến.

Hiệu năng mạng liên kết. Mô phỏng đánh giá hiệu năng mạng. Giới thiệu bài toán và các nghiên cứu liên quan. Bài toán nghiên cứu.

Tình hình nghiên cứu. Các nghiên cứu liên quan. 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ÊN46 2.

Tô-pô mạng ngẫu nhiên và thuật toán định tuyến rút gọn. Tô-pô mạng ngẫu nhiên. Cơ chế định tuyến phân tán tra bảng. Thuật toán định tuyến rút gọn TZ [29].

Định tuyến khai thác các cầu nối giữa các vùng (CORRA). Ý tưởng xây dựng thuật toán định tuyến CORRA. Xây dựng bảng định tuyến. Kỹ thuật địa chỉ hóa.

Đánh giá lý thuyết. Đánh giá thực nghiệm. Kết luận và hướng phát triển. Đị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.

Xây dựng phương thức lựa chọn nút đại diện dựa trên vị trí. Đánh giá thực nghiệm. Kết luận và hướng phát triển. Xây dựng cơ chế tuyển chọn nút đại diện.

Tuyển chọn nút đại diện. Cơ chế tuyển chọn các nút đại diện. Thực nghiệm đánh giá cơ chế tuyển chọn nút đại diện. Kết luận và hướng phát triển của cơ chế tuyển chọn nút đại diện.

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. Kiến trúc tổng quan của công cụ mô phỏng SSiNET. Ý tưởng cơ bản của SSiNET.

Kiến trúc mô-đun chức năng và giao diện. Thiết kế chi tiết kỹ thuật. Thiết kế chi tiết các gói của công cụ phần mềm. Xây dựng cơ chế kỹ thuật.

Đánh giá thực nghiệm. Đánh giá kích thước bảng định tuyến. Đánh giá độ trễ truyền tin. Đánh giá thời gian thực thi.

So sánh kết quả đánh giá giữa SSiNET và Omnet++. Đánh giá thông lượng và thông lượng cực đại. Đánh giá theo phương pháp xấp xỉ. Ứ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ở.

Kiến trúc Bus-RSN. Giải pháp định tuyến. Đánh giá bằng thực nghiệm. Kết luận giải pháp.

Tóm tắt chƣơng 3. 120 KẾT LUẬN VÀ HƢỚNG NGHIÊN CỨU. 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. Định tuyến phân cấp đối với mạng ngẫu nhiên chuẩn tắc. HR-SW: Định tuyến phân cấp trên mô hình đồ thị thế giới nhỏ. Kỹ thuật địa chỉ trong định tuyến phân cấp.

Thực thi định tuyến HR-SW. Đánh giá hiệu năng mạng. 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 2 CORRA inter-connection topologies cầu 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.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 .2: Xây dựng bảng định tuyến – Routing Table Construction (RTC).3: Tổ chức bản ghi trong bảng định tuyến của thuật toán CORRA .2- GLCR: Lựa chọn nút đại diện .5: Tổng hợp một số khái niệm sử dụng trong giải pháp GLCR.3-GLCR: Điều chỉnh lựa chọn nút đại diện – AdjustLandmarkSet.4-GLCR: Lựa chọn nút đại diện – .2-IJDST: Loại bỏ nút đại diện yếu .3-IJDST: Lựa chọn nút đại diện .4-IJDST: Lựa chọn nút đại diện .1: Đường kính mạng theo tỉ lệ xấp xỉ .2: Độ trễ trung bình toàn mạng theo tỉ lệ xấp xỉ .3: Thời gian thực thi tính toán.1-Bus-RSN: Xây dựng tô-pô Bus-RSN .5: Định nghĩa một số kí hiệu được sử dụng. 2-Bus-RSN: Thuật toán định tuyến HRA (alpha-1 HRA) .7: Các ký hiệu trong các hình minh họa thực nghiệm .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 .5-GLCR: Tính toán trong giải pháp GLCR .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) .2: Các ứng dụng trên mạng [6] .3: Các dạng tô-pô mạng cơ bản .4: Mạng trực tiếp và gián tiếp.5: Ví dụ về định tuyến trên mạng kết 2D-Torus [5] .6: Định tuyến thích ứng trên tô-pô RING 8-nút.7: Ví dụ về tắc nghẽn của Wormhole switching .8: Độ trễ của một gói tin trên kênh truyền .9: Tương quan giữa băng thông và thông lượng .10: Tương quan giữa độ trễ và lưu lượng dữ liệu yêu cầu .11: Tương quan giữa thông lượng và lưu lượng dữ liệu yêu cầu. 12: Mô hình mô phỏng .13: Tổ chức bảng định tuyến tại nút mạng .1: Tô-pô cơ sở dạng lưới .2: Tạo tô-pô mạng ngẫu nhiên từ tô-pô cơ sở dạng lưới .3: Cách tiếp cận định tuyến dựa trên nút đại diện của Thorup và Zwick.4: Xây dựng tô-pô ngẫu nhiên cho thuật toán CORRA .5: Hàng xóm gửi thông tin cầu của nó.6: Nút lưu thông tin từ hàng xóm mà nằm trong khoảng của .7: Ví dụ về việc xây dựng các bản ghi trong bảng định tuyến .8: Ví dụ về thực thi định tuyến thông qua nhãn và tọa độ nút mạng.

9: Thực thi định tuyến thông qua định danh nút mạng .10: Mô hình mở rộng, sử dụng -grid liên kết cơ bản .11: Tác động của giá trị đối với .12: Trung bình kích thước bảng định tuyến .13: Đánh giá đường kính mạng .14: Trung bình chiều dài đường định tuyến ( ) .15: Trung bình độ trễ truyền tin .16: của mạng có kích thước lớn .17: Trung bình độ trễ truyền tin đối với mạng kích thước lớn .18: Lựa chọn các nút đại diện không mong đợi trong thuật toán TZ [29] .19: Minh họa điều chỉnh vị trí các nút đại diện .20: Tương quan giữa lớn nhất và kích thước lớn nhất.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 .22: Tương quan giữa và kích thước cụm lớn nhất .23: Tương quan giữa với lớn nhất .24: So sánh của GLCR với TZ-original trong mạng kích thước lớn .25: Phân bố các nút đại diện trong đồ thị dạng lưới .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.27: Tương quan giữa kích thước mạng đối với .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 .29: Tương quan giữa số lượng nút đại diện với .1: Mô tả cấu trúc nút mạng .2: Sơ đồ thiết kế tổng quan .3: Lưu đồ tạo tô-pô mạng .4: Sơ đồ thiết kế chi tiết .5: Lưu đồ quyết định định tuyến .6: Thiết kế kỹ thuật chi tiết của SSiNET .7: Thiết kế lớp Graph, RoutingAlgorithm và TopoExperiment .8: Thiết kế gói graph và routing .9: Thiết kế các thành phần vật lý của mạng .10: Thiết kế nhóm thực nghiệm mô phỏng .11: Thiết kế các gói thực nghiệm mô phỏng zeroload và weightedload .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 .13: Tiến trình hoạt động mô phỏng .14: Ví dụ về quản lý sự kiện rời rạc .15: Ví dụ về đường đi trên mạng có chiều dài m hop.16: Tính toán kích thước bảng định tuyến.17: Độ trễ truyền tin trên mạng .