Luận án: Định tuyến trong tô-pô mạng liên kết hiệu năng cao - ĐH Bách Khoa

Tôi sẽ tạo meta tags cho bài viết theo yêu cầu: { "ai_description": "Nghiên cứu các giải pháp định tuyến hiệu năng cao trong mạng liên kết tô pô và công cụ

• Tác giả: Kiều Thành Chung
• Người hướng dẫn: PGS.TS. Nguyễn Khanh Văn
• Trường học: Đại học Bách khoa Hà Nội
• Chuyên ngành: Kỹ thuật phần mềm
• Đề tài: Nghiên cứu giải pháp định tuyến tô-pô mạng liên kết hiệu năng cao
• Loại tài liệu: Luận án tiến sĩ
• Năm xuất bản: 2021
• Địa điểm: Hà Nội

Tóm tắt

I. Tổng quan về định tuyến tô pô mạng hiệu năng cao

Định tuyến trong tô-pô mạng hiệu năng cao là lĩnh vực nghiên cứu quan trọng nhằm tối ưu hóa đường truyền dữ liệu giữa các nút mạng. Luận án tập trung phân tích các giải pháp định tuyến tiên tiến cho mạng liên kết hiệu suất cao, đặc biệt trong ngữ cảnh tô-pô mạng ngẫu nhiên và mạng có cấu trúc đa tầng. Các thuật toán định tuyến hiện đại phải đáp ứng yêu cầu về độ trễ thấp, băng thông ổn định và khả năng mở rộng hệ thống. Nghiên cứu khảo sát các phương pháp định tuyến dựa trên bảng, định tuyến nguồn và định tuyến rút gọn, đồng thời đề xuất công cụ đánh giá hiệu năng toàn diện. Mục tiêu chính là cải thiện hiệu quả truyền tải dữ liệu trong môi trường mạng có độ phức tạp cao, nơi mà các giải pháp truyền thống tỏ ra kém hiệu quả.

1.1. Khái niệm tô pô mạng và định tuyến hiệu năng

Tô-pô mạng đề cập đến cấu trúc liên kết vật lý hoặc logic của hệ thống mạng, ảnh hưởng trực tiếp đến hiệu năng định tuyến. Các tô-pô phổ biến bao gồm mạng hình sao, lưới, hỗn hợp và ngẫu nhiên. Định tuyến hiệu năng cao yêu cầu tối ưu hóa đường đi gói tin dựa trên các tiêu chí như độ trễ, mất mát gói tin và độ ổn định. Trong mạng liên kết hiệu suất cao, định tuyến dựa trên bảng (table-based routing) được ưa chuộng nhờ khả năng linh hoạt thích ứng với các thay đổi cấu trúc mạng. Cơ chế này cho phép cập nhật nhanh chóng bảng định tuyến khi có sự cố hoặc thay đổi tải mạng.

1.2. Vai trò của công cụ đánh giá trong nghiên cứu định tuyến

Công cụ đánh giá đóng vai trò then chốt trong việc kiểm chứng hiệu quả của các giải pháp định tuyến đề xuất. Các công cụ như NS-3, OMNeT++ và Mininet cung cấp môi trường mô phỏng chính xác, cho phép so sánh hiệu năng giữa các thuật toán định tuyến khác nhau. Công cụ đánh giá cần tích hợp các chỉ số định lượng như độ trễ end-to-end, tỷ lệ mất gói tin và thông lượng. Ngoài ra, khả năng mô phỏng các kịch bản mạng thực tế, bao gồm tải động và sự cố mạng, là yếu tố quan trọng để đảm bảo tính khả thi của giải pháp.

II. Phân tích các vấn đề trong định tuyến tô pô mạng hiện nay

Hiện nay, các giải pháp định tuyến truyền thống gặp nhiều hạn chế trong môi trường mạng hiệu suất cao. Vấn đề chính bao gồm sự gia tăng không kiểm soát của kích thước bảng định tuyến, dẫn đến chi phí lưu trữ và xử lý cao tại các nút mạng. Ngoài ra, các thuật toán định tuyến dựa trên khoảng cách ngắn nhất (shortest-path) thường không tối ưu trong môi trường mạng động, nơi cấu trúc liên kết thay đổi liên tục. Sự phức tạp trong quản lý định tuyến cũng làm tăng nguy cơ xung đột đường đi, gây ra tình trạng tắc nghẽn mạng. Luận án phân tích sâu các thách thức này thông qua khảo sát thực nghiệm và lý thuyết, nhằm xác định các giải pháp khả thi.

2.1. Hạn chế của định tuyến truyền thống trong mạng hiệu năng

Định tuyến truyền thống dựa trên bảng (table-driven routing) gặp khó khăn trong việc mở rộng quy mô do yêu cầu lưu trữ thông tin định tuyến lớn. Mỗi nút mạng phải duy trì bảng định tuyến cập nhật cho toàn bộ mạng, dẫn đến chi phí bộ nhớ và băng thông quản lý cao. Ngoài ra, các thuật toán như OSPF hay RIP không thích ứng tốt với sự thay đổi nhanh chóng của cấu trúc mạng, gây ra tình trạng mất ổn định trong định tuyến. Trong môi trường mạng liên kết hiệu suất cao, nơi mà các nút mạng có thể thay đổi vị trí hoặc trạng thái hoạt động liên tục, các giải pháp định tuyến truyền thống tỏ ra kém hiệu quả.

2.2. Thách thức trong định tuyến mạng ngẫu nhiên

Mạng ngẫu nhiên (random network) có cấu trúc liên kết không theo quy luật cố định, khiến cho việc dự đoán đường đi tối ưu trở nên khó khăn. Các thuật toán định tuyến truyền thống thường dựa trên giả định về cấu trúc mạng có tính chất nhất định, do đó không áp dụng được trực tiếp vào mạng ngẫu nhiên. Ngoài ra, sự biến động cao trong mật độ kết nối giữa các nút đòi hỏi các giải pháp định tuyến phải linh hoạt và có khả năng thích ứng nhanh chóng. Luận án khảo sát các phương pháp định tuyến đặc thù cho mạng ngẫu nhiên, bao gồm định tuyến rút gọn và định tuyến dựa trên biểu đồ.

III. Giải pháp định tuyến rút gọn cho mạng hiệu năng cao

Để khắc phục các hạn chế của định tuyến truyền thống, luận án đề xuất giải pháp định tuyến rút gọn (compact routing) nhằm giảm thiểu kích thước bảng định tuyến tại mỗi nút. Giải pháp này dựa trên nguyên lý chia mạng thành các cụm nhỏ, trong đó mỗi cụm có một nút đại diện (landmark node) chịu trách nhiệm định tuyến giữa các cụm. Thuật toán CORRA (Compact Routing with Landmark Nodes) được phát triển nhằm tối ưu hóa đường đi giữa các nút trong cùng cụm hoặc giữa các cụm khác nhau. Giải pháp này đảm bảo độ trễ định tuyến thấp và khả năng mở rộng cao, phù hợp cho các mạng có quy mô lớn và cấu trúc phức tạp.

3.1. Nguyên lý hoạt động của thuật toán CORRA

Thuật toán CORRA chia mạng thành các cụm, mỗi cụm có một nút đại diện chịu trách nhiệm định tuyến giữa các cụm. Các nút thông thường (non-landmark nodes) chỉ lưu trữ thông tin định tuyến trong phạm vi cụm của mình, trong khi nút đại diện lưu trữ thông tin toàn bộ mạng. Khi một gói tin được gửi từ nút A đến nút B, nếu hai nút nằm trong cùng một cụm, gói tin sẽ được định tuyến trực tiếp theo đường ngắn nhất. Nếu hai nút nằm trong các cụm khác nhau, gói tin sẽ được chuyển tiếp đến nút đại diện gần nhất với đích, sau đó định tuyến đến đích thông qua nút đại diện đích.

3.2. Đánh giá hiệu năng và so sánh với các phương pháp khác

Thuật toán CORRA được đánh giá thông qua các thí nghiệm mô phỏng trên mạng ngẫu nhiên và mạng lưới. Kết quả cho thấy CORRA giảm đáng kể kích thước bảng định tuyến tại mỗi nút so với các phương pháp truyền thống, đồng thời duy trì độ trễ định tuyến ở mức chấp nhận được. So sánh với thuật toán định tuyến rút gọn của Cowen, CORRA cải thiện hiệu năng trong môi trường mạng có mật độ kết nối cao. Ngoài ra, thuật toán này cũng cho thấy khả năng thích ứng tốt với sự thay đổi cấu trúc mạng, nhờ cơ chế cập nhật linh hoạt thông tin định tuyến giữa các nút đại diện.

IV. Kết luận và ứng dụng thực tiễn trong mạng hiệu năng

Luận án đã đề xuất và đánh giá thành công giải pháp định tuyến rút gọn CORRA cho mạng hiệu năng cao, chứng minh khả năng cải thiện đáng kể hiệu suất định tuyến so với các phương pháp truyền thống. Kết quả nghiên cứu cung cấp cơ sở lý thuyết và thực nghiệm cho việc triển khai các giải pháp định tuyến tiên tiến trong các hệ thống mạng hiện đại. Giải pháp này có thể ứng dụng rộng rãi trong các lĩnh vực như mạng dữ liệu trung tâm (data center), mạng 5G, và mạng Internet of Things (IoT). Ngoài ra, luận án cũng đóng góp vào việc phát triển các công cụ đánh giá hiệu năng mạng, hỗ trợ cộng đồng nghiên cứu trong việc so sánh và tối ưu hóa các giải pháp định tuyến.

4.1. Tóm tắt đóng góp khoa học của luận án

Luận án đóng góp vào lĩnh vực định tuyến mạng bằng việc đề xuất thuật toán CORRA, một giải pháp định tuyến rút gọn dựa trên nguyên lý nút đại diện. Giải pháp này giảm đáng kể kích thước bảng định tuyến tại mỗi nút, cải thiện hiệu năng định tuyến trong môi trường mạng có cấu trúc phức tạp. Ngoài ra, luận án cũng phát triển công cụ đánh giá hiệu năng mạng toàn diện, tích hợp các chỉ số định lượng như độ trễ, mất mát gói tin và thông lượng. Các kết quả nghiên cứu đã được công bố tại các hội nghị khoa học uy tín, góp phần nâng cao nhận thức về tầm quan trọng của định tuyến hiệu năng cao.

4.2. Hướng phát triển trong tương lai

Trong tương lai, nghiên cứu có thể mở rộng sang các lĩnh vực như định tuyến trong mạng không dây (wireless network) và mạng định nghĩa bằng phần mềm (SDN). Việc tích hợp trí tuệ nhân tạo (AI) vào quá trình định tuyến cũng là một hướng nghiên cứu hứa hẹn, nhằm tối ưu hóa đường đi gói tin dựa trên dữ liệu thời gian thực. Ngoài ra, việc phát triển các công cụ đánh giá hiệu năng mạng tiên tiến hơn, có khả năng mô phỏng các kịch bản mạng phức tạp, cũng là một hướng đi quan trọng để hỗ trợ cộng đồng nghiên cứu.

Trích đoạn nội dung tài liệu

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. Đâ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.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 thiết 14 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. Tô-pô mạng (Network topology) 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].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ừ đến ) 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 trao đổi dữ liệu với , 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. 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.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.

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. 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ế.