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

Nghiên cứu sâu về các giải pháp định tuyến hiệu quả cho tô pô mạng liên kết hiệu năng cao. Đánh giá chi tiết hiệu suất và ứng dụng thực tế.

• Tác giả: Kiều Thành Chung
• Người hướng dẫn: PGS.TS. Nguyễn Khánh Văn
• Trường học: Đại học Bách Khoa Hà Nội
• Chuyên ngành: Kỹ thuật máy tính
• Đề tài: 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á
• Loại tài liệu: Luận văn tiến sĩ
• Năm xuất bản: 2021
• Địa điểm: Hà Nội

Tóm tắt

I. Khám phá tổng quan Giải pháp định tuyến mạng liên kết hiệu năng cao

Trong bối cảnh công nghệ thông tin phát triển mạnh mẽ, nhu cầu về các hệ thống xử lý song song và điện toán đám mây ngày càng tăng. Điều này đòi hỏi các mạng liên kết hiệu năng cao có khả năng truyền tải lượng lớn dữ liệu với độ trễ thấp và thông lượng tối đa. Định tuyến mạng liên kết hiệu năng cao đóng vai trò cực kỳ quan trọng trong việc tối ưu hóa luồng dữ liệu, đảm bảo rằng các gói tin được chuyển tiếp một cách hiệu quả nhất từ nguồn đến đích. Một hệ thống định tuyến tối ưu không chỉ nâng cao hiệu quả hoạt động mà còn giảm thiểu tắc nghẽn, tăng khả năng mở rộng của toàn bộ mạng. Luận án nghiên cứu đã tập trung vào việc phát triển và đánh giá các giải pháp định tuyến tiên tiến, nhằm giải quyết những thách thức cố hữu của các tô-pô mạng phức tạp, đặc biệt là trong môi trường mạng ngẫu nhiên và quy mô lớn. Việc hiểu rõ cơ chế hoạt động của các thuật toán định tuyến và cách chúng ảnh hưởng đến hiệu năng mạng là chìa khóa để xây dựng hạ tầng bền vững và hiệu quả.

1.1. Định tuyến trong mạng liên kết Khái niệm và tầm quan trọng

Định tuyến là quá trình chọn lựa đường đi cho các gói tin trong mạng từ điểm nguồn đến điểm đích. Trong bối cảnh mạng liên kết hiệu năng cao, việc này trở nên phức tạp hơn do số lượng nút mạng lớn, đa dạng về tô-pô mạng và yêu cầu khắt khe về hiệu suất. Một thuật toán định tuyến hiệu quả phải đảm bảo gói tin đến đích nhanh chóng, đáng tin cậy và sử dụng tài nguyên mạng một cách tối ưu. Tầm quan trọng của định tuyến hiệu năng cao thể hiện ở khả năng hỗ trợ các ứng dụng đòi hỏi băng thông lớn và độ trễ thấp như tính toán khoa học, phân tích dữ liệu lớn và trí tuệ nhân tạo. Việc lựa chọn một giải pháp định tuyến mạng liên kết hiệu năng cao phù hợp có thể ảnh hưởng trực tiếp đến thông lượng mạng và độ tin cậy của hệ thống. Nghiên cứu đã chỉ ra rằng, cơ chế định tuyến phân tán tra bảng là một trong những phương pháp được sử dụng phổ biến, nhưng cũng tồn tại những hạn chế cần được khắc phục.

1.2. Các chỉ số đánh giá hiệu năng mạng liên kết quan trọng

Để đánh giá khách quan một giải pháp định tuyến mạng liên kết hiệu năng cao, cần dựa trên các chỉ số hiệu năng cụ thể. Các chỉ số quan trọng bao gồm thông lượng mạng (lượng dữ liệu tối đa mạng có thể xử lý trong một đơn vị thời gian), độ trễ (thời gian gói tin di chuyển từ nguồn đến đích), mức độ tắc nghẽn và khả năng chịu lỗi. Thông lượng đượ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). Ban đầu, khi lượng thông tin yêu cầu truyền đi thấp, thông lượng và lưu lượng dữ liệu yêu cầu có giá trị bằng nhau. Khi yêu cầu tăng lên, thông lượng có thể đạt mức bão hòa. Các nghiên cứu gần đây thường sử dụng các công cụ mô phỏng để đo lường các chỉ số này dưới nhiều kịch bản tải và tô-pô mạng khác nhau. Việc đánh giá hiệu năng mạng giúp xác định ưu nhược điểm của các thuật toán định tuyến và định hướng cho việc cải tiến trong tương lai. Công cụ mô phỏng SSiNET được đề xuất là một giải pháp hỗ trợ đắc lực trong quá trình này.

II. Thách thức Giải quyết vấn đề trong định tuyến mạng liên kết quy mô lớn

Việc thiết kế và triển khai các giải pháp định tuyến mạng liên kết hiệu năng cao đối mặt với nhiều thách thức đáng kể, đặc biệt khi mạng đạt đến quy mô lớn. Một trong những vấn đề chính là sự phức tạp của tô-pô mạng khi số lượng nút tăng lên, đòi hỏi các thuật toán định tuyến phải có khả năng mở rộng tốt. Các phương pháp định tuyến truyền thống thường gặp khó khăn trong việc quản lý bảng định tuyến khổng lồ, dẫn đến tốn kém bộ nhớ và tăng độ trễ xử lý. Hơn nữa, sự xuất hiện của các liên kết ngẫu nhiên trong một số tô-pô mạng hiện đại tạo ra cả cơ hội và thách thức trong việc tối ưu hóa đường đi. Định tuyến hiệu năng cao không chỉ là việc tìm ra đường đi ngắn nhất mà còn là cân bằng tải, tránh tắc nghẽn cục bộ và đảm bảo độ tin cậy của dữ liệu. Nghiên cứu sinh đã chỉ ra rằng, việc khai thác các cầu nối và nút đại diện có thể là chìa khóa để vượt qua những rào cản này.

2.1. Hạn chế của định tuyến truyền thống trong mạng quy mô lớn

Các phương pháp định tuyến truyền thống như định tuyến dựa trên bảng (table-driven routing) thường hoạt động tốt trong các mạng nhỏ hoặc tĩnh. Tuy nhiên, với mạng liên kết hiệu năng cao quy mô lớn, cách tiếp cận này bộc lộ nhiều hạn chế. Mỗi nút phải lưu trữ một bảng định tuyến đủ lớn để chứa thông tin về tất cả các điểm đến, làm giảm khả năng mở rộng. Khi mạng có hàng nghìn hoặc hàng triệu nút, kích thước bảng định tuyến trở nên không thể quản lý được, gây tốn kém tài nguyên bộ nhớ và tăng thời gian tìm kiếm. Hơn nữa, định tuyến truyền thống khó có thể điều chỉnh linh hoạt theo sự thay đổi của tải mạng hoặc sự cố liên kết, dẫn đến tắc nghẽn và giảm thông lượng mạng. Điều này yêu cầu phát triển các giải pháp định tuyến mạng liên kết hiệu năng cao mới, có khả năng thích ứng và phân tán tốt hơn, giảm phụ thuộc vào thông tin toàn cục.

2.2. Khó khăn trong quản lý bảng định tuyến và tối ưu hóa đường đi

Quản lý bảng định tuyến là một thách thức lớn đối với định tuyến hiệu năng cao trong các tô-pô mạng phức tạp. Kích thước bảng định tuyến tỷ lệ thuận với số lượng nút mạng, và việc cập nhật bảng này khi có sự thay đổi trong cấu trúc mạng hoặc trạng thái liên kết có thể gây ra chi phí đáng kể về băng thông và tài nguyên tính toán. Bên cạnh đó, việc tối ưu hóa đường đi không chỉ dừng lại ở việc tìm đường ngắn nhất mà còn phải xem xét các yếu tố như cân bằng tải, tránh các liên kết bị quá tải và giảm thiểu xung đột tài nguyên. Luận án đã đề cập đến việc hai gói dữ liệu từ các nguồn khác nhau, dù cùng đích, không thể đi theo hai con đường khác nhau đến một nút trung gian nếu sử dụng định tuyến truyền thống, điều này dễ dàng thực hiện với định tuyến nguồn. Các thuật toán định tuyến cần phải linh hoạt để tận dụng các liên kết ngẫu nhiên và các nút đại diện để giảm chiều dài đường đi (số hop) và cải thiện hiệu năng mạng tổng thể.

III. Phương pháp đột phá Nâng cao hiệu năng định tuyến với CORRA và TZ

Để vượt qua các thách thức đã nêu, nghiên cứu đã đề xuất và phân tích các giải pháp định tuyến mạng liên kết hiệu năng cao đột phá, đặc biệt là thuật toán định tuyến rút gọn TZ và CORRA. Những phương pháp này tập trung vào việc giảm thiểu kích thước bảng định tuyến và tận dụng cấu trúc đặc biệt của các tô-pô mạng để cải thiện thông lượng mạng và giảm độ trễ. Thuật toán định tuyến TZ [29] là một trong những cơ chế định tuyến rút gọn đã được nghiên cứu, cho thấy tiềm năng trong việc tối ưu hóa định tuyến. Tuy nhiên, CORRA (Định tuyến khai thác các cầu nối giữa các vùng) là một phương pháp mới mẻ hơn, được thiết kế để khai thác hiệu quả các liên kết ngẫu nhiên, giúp các gói tin 'nhảy' qua các khoảng cách lớn một cách hiệu quả hơn. Mục tiêu của các giải pháp này là đạt được hiệu năng mạng cao mà vẫn duy trì khả năng mở rộng và hiệu quả về tài nguyên.

3.1. Định tuyến rút gọn TZ và cơ chế phân tán tra bảng hiệu quả

Thuật toán định tuyến rút gọn TZ là một trong những phương pháp được phát triển nhằm giải quyết vấn đề kích thước bảng định tuyến trong mạng liên kết hiệu năng cao. Cơ chế định tuyến phân tán tra bảng được áp dụng trong TZ cho phép mỗi nút chỉ lưu trữ một phần thông tin định tuyến cục bộ, thay vì toàn bộ bản đồ mạng. Điều này giúp giảm đáng kể yêu cầu về bộ nhớ và khả năng tính toán trên mỗi nút, từ đó nâng cao khả năng mở rộng của mạng. TZ tìm cách rút gọn thông tin định tuyến bằng cách nhóm các nút đích vào các vùng logic hoặc dựa trên một số thuộc tính chung, sau đó chỉ lưu trữ thông tin về cách tiếp cận các vùng đó. Mặc dù TZ đã cho thấy những ưu điểm nhất định trong việc giảm tải cho các nút mạng, nghiên cứu vẫn tiếp tục tìm kiếm các giải pháp tối ưu hơn để đạt được hiệu năng mạng cao nhất, đặc biệt trong các tô-pô mạng phức tạp.

3.2. CORRA Khai thác cầu nối và liên kết ngẫu nhiên giữa các vùng

CORRA (Định tuyến khai thác các cầu nối giữa các vùng) là một giải pháp định tuyến mạng liên kết hiệu năng cao tiên tiến, được thiết kế để tận dụng các đặc tính độc đáo của tô-pô mạng ngẫu nhiên. Ý tưởng cốt lõi của CORRA là khai thác các liên kết ngẫu nhiên (còn gọi là cầu nối) để tạo ra các đường đi ngắn hơn, giảm số hop cần thiết để gói tin đến đích. Thay vì chỉ dựa vào các liên kết lưới cơ sở, mỗi nút mạng tìm kiếm trong vùng hàng xóm của nó những nút có chứa liên kết ngẫu nhiên kết nối tới các vùng nút mạng ở xa. Ví dụ, trong một tô-pô mạng ngẫu nhiên, một nút có thể có các hàng xóm trong bán kính δ hop. Liên kết (u; v) và (p; q) có thể được tạo ra bởi phân bố xác suất ngẫu nhiên đều. Điều này cho phép gói tin 'nhảy' qua các khoảng cách lớn, làm giảm chiều dài đường định tuyến và tăng thông lượng mạng. Việc xây dựng bảng định tuyến trong CORRA cũng được tối ưu hóa để phản ánh khả năng khai thác các cầu nối này. Kỹ thuật địa chỉ hóa được áp dụng để đơn giản hóa quá trình tìm kiếm đường đi.

IV. Ứng dụng Đánh giá Thực nghiệm hiệu năng mạng liên kết với SSiNET

Để kiểm chứng hiệu quả của các giải pháp định tuyến mạng liên kết hiệu năng cao như CORRA và TZ, việc tiến hành đánh giá thực nghiệm là không thể thiếu. Nghiên cứu đã tập trung vào việc xây dựng và sử dụng công cụ mô phỏng mạng chuyên biệt để đánh giá hiệu năng mạng dưới nhiều điều kiện khác nhau. Công cụ này không chỉ giúp đo lường các chỉ số như thông lượng mạng, độ trễ mà còn cho phép phân tích hành vi của các thuật toán định tuyến trong các tô-pô mạng đa dạng, bao gồm cả mạng ngẫu nhiên. Việc đánh giá hiệu năng mạng một cách khách quan và toàn diện là yếu tố then chốt để xác định tính khả thi và ưu điểm của từng giải pháp định tuyến hiệu năng cao. Các kết quả thực nghiệm đóng vai trò là bằng chứng quan trọng, hỗ trợ các nhà nghiên cứu đưa ra kết luận và định hướng phát triển cho tương lai.

4.1. SSiNET Công cụ hỗ trợ mô phỏng và đánh giá hiệu năng mạng

SSiNET là một công cụ mô phỏng mạng được thiết kế đặc biệt để hỗ trợ đánh giá hiệu năng mạng liên kết hiệu năng cao. Ý tưởng cơ bản của SSiNET là cung cấp một môi trường linh hoạt, nơi các nhà nghiên cứu có thể triển khai và kiểm thử các thuật toán định tuyến mới mà không cần phải xây dựng hạ tầng vật lý tốn kém. SSiNET cho phép định cấu hình các loại tô-pô mạng khác nhau, từ mạng lưới truyền thống đến các mạng ngẫu nhiên phức tạp, và mô phỏng các kiểu tải lưu lượng (traffic patterns) đa dạng. Công cụ này cung cấp khả năng đo lường chính xác các chỉ số hiệu năng quan trọng như thông lượng mạng, độ trễ trung bình, tỷ lệ mất gói và mức độ tắc nghẽn. Nhờ SSiNET, quá trình phân tích và so sánh các giải pháp định tuyến mạng liên kết hiệu năng cao trở nên khoa học và đáng tin cậy hơn, từ đó đẩy nhanh quá trình nghiên cứu và phát triển.

4.2. Kết quả thực nghiệm Đánh giá hiệu quả của CORRA trên mạng ngẫu nhiên

Các thực nghiệm đánh giá hiệu năng mạng sử dụng SSiNET đã chứng minh hiệu quả vượt trội của giải pháp định tuyến mạng liên kết hiệu năng cao CORRA trên các tô-pô mạng ngẫu nhiên. Nghiên cứu đã trình bày cấu trúc tô-pô ngẫu nhiên với tính chất xây dựng vùng hàng xóm trong bán kính δ hop, được áp dụng cho thuật toán CORRA. Ví dụ, xét nút s với bán kính δ = 2, nút u và p là hàng xóm của nút s, liên kết giữa chúng là các liên kết của đồ thị lưới cơ sở. Các kết quả cho thấy CORRA giúp giảm đáng kể chiều dài đường định tuyến (số hop) và tăng thông lượng mạng so với các thuật toán định tuyến truyền thống. Đặc biệt, khả năng khai thác các liên kết ngẫu nhiên của CORRA đã giúp giảm thiểu tắc nghẽn và cải thiện hiệu quả sử dụng tài nguyên mạng. Đánh giá hiệu năng mạng thực nghiệm này không chỉ khẳng định tiềm năng của CORRA mà còn cung cấp dữ liệu quý giá cho việc tinh chỉnh và phát triển các giải pháp định tuyến hiệu năng cao trong tương lai, hướng tới các ứng dụng thực tiễn.

V. Kết luận Tương lai Phát triển định tuyến hiệu năng cao bền vững

Việc nghiên cứu và phát triển các giải pháp định tuyến mạng liên kết hiệu năng cao là một lĩnh vực không ngừng tiến hóa, đóng vai trò then chốt trong sự phát triển của công nghệ thông tin. Các phương pháp như CORRA và việc sử dụng các nút đại diện đã mở ra những hướng đi mới để giải quyết vấn đề về hiệu quả và khả năng mở rộng của mạng liên kết hiệu năng cao. Tuy nhiên, vẫn còn nhiều tiềm năng để cải thiện. Tương lai của định tuyến hiệu năng cao sẽ tập trung vào việc phát triển các thuật toán định tuyến thích ứng thông minh hơn, có khả năng học hỏi từ hành vi mạng và tự động tối ưu hóa đường đi trong thời gian thực. Việc tích hợp các kỹ thuật trí tuệ nhân tạo và học máy vào các giải pháp định tuyến mạng liên kết hiệu năng cao hứa hẹn sẽ mang lại những đột phá đáng kể, giúp các mạng không chỉ nhanh hơn mà còn thông minh và linh hoạt hơn trước các thay đổi và thách thức.

5.1. Tóm tắt những đóng góp chính của các giải pháp định tuyến

Luận án đã đóng góp đáng kể vào lĩnh vực định tuyến mạng liên kết hiệu năng cao bằng cách đề xuất và phân tích các giải pháp định tuyến rút gọn tiên tiến. Đặc biệt, thuật toán định tuyến CORRA đã chứng minh khả năng vượt trội trong việc khai thác các cầu nối và liên kết ngẫu nhiên trên các tô-pô mạng phức tạp, giúp giảm số hop và tăng thông lượng mạng. Bên cạnh đó, việc phát triển công cụ mô phỏng mạng SSiNET đã cung cấp một nền tảng mạnh mẽ để đánh giá hiệu năng mạng một cách khoa học và toàn diện. Những đóng góp này không chỉ giải quyết các thách thức hiện tại trong việc quản lý bảng định tuyến và tối ưu hóa đường đi mà còn mở ra những hướng nghiên cứu mới cho các giải pháp định tuyến hiệu năng cao, hướng tới sự hiệu quả và khả năng mở rộng tối ưu.

5.2. Hướng phát triển và tiềm năng của định tuyến mạng tương lai

Tương lai của giải pháp định tuyến mạng liên kết hiệu năng cao sẽ tập trung vào việc nâng cao khả năng tự thích ứng, tự học và tự phục hồi của các thuật toán định tuyến. Các hướng phát triển tiềm năng bao gồm việc áp dụng trí tuệ nhân tạo và học máy để dự đoán các điểm tắc nghẽn, tối ưu hóa đường đi dựa trên dữ liệu lịch sử và tự động cấu hình lại mạng khi có sự cố. Ngoài ra, việc nghiên cứu các tô-pô mạng mới và phức tạp hơn, cùng với các giải pháp định tuyến hỗ trợ ảo hóa và điện toán biên, cũng là những lĩnh vực đầy hứa hẹn. Mục tiêu cuối cùng là xây dựng các mạng liên kết hiệu năng cao không chỉ đáp ứng được nhu cầu hiện tại mà còn có khả năng đối phó với những yêu cầu ngày càng tăng của các ứng dụng công nghệ tương lai, đảm bảo một hiệu năng mạng bền vững và mạnh mẽ.

Nội dung chính

Tổng quan luận án

Luận án tiến sĩ với đề tài "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á" được thực hiện bởi nghiên cứu sinh Kiều Thành Chung, dưới sự hướng dẫn khoa học của PGS.TS. Nguyễn Khanh Văn và TS. Phạm Đăng Hải tại phòng thí nghiệm Sedic-Lab, Viện Công nghệ Thông tin và Truyền thông, Trường Đại học Bách Khoa Hà Nội, có sự phối hợp nghiên cứu cùng các chuyên gia từ Viện Tin học Quốc gia Nhật Bản (National Institute of Informatics – NII) gồm PGS.TS. Michihiro Koibuchi, TS. Ikki Fujiwara và TS. Trương Thảo Nguyên (hoàn thành năm 2021).

Tính cấp thiết và khoảng trống nghiên cứu

Nghiên cứu tô-pô mạng liên kết (Interconnection Network) là chủ đề nền tảng trong kiến trúc máy tính, hệ thống tính toán song song, tính toán hiệu năng cao (HPC) và các trung tâm dữ liệu (Data Center - DC) hiện đại. Một giải pháp tô-pô hoàn chỉnh bao gồm hai cấu phần then chốt: cấu trúc tô-pô vật lý và giải thuật định tuyến.

• Các cấu trúc tô-pô truyền thống (như De Bruijn, Star, Kautz, Mesh, Torus) chỉ hoạt động hiệu quả ở quy mô nhỏ (vài trăm nút). Khi quy mô hệ thống tăng lên hàng nghìn đến hàng trăm nghìn nút, các kiến trúc này bộc lộ hai hạn chế lớn: không đáp ứng được yêu cầu về độ trễ thấp kết hợp thông lượng cao, đồng thời thiếu tính co giãn (scalability) và tính linh hoạt (flexibility) khi thực hiện thêm hoặc bớt các nút tính toán.
• Các kiến trúc hiện đại như Fat-Tree tuy có đường kính mạng thấp và định tuyến đơn giản nhưng bị giới hạn khả năng mở rộng do phụ thuộc vào số cổng của switch, đòi hỏi sử dụng các thiết bị chuyển mạch chuyên dụng có bậc đỉnh cao với giá thành lớn. Ngược lại, mô hình mạng ngẫu nhiên (như JellyFish, Random Shortcut Network - RSN) có khả năng mở rộng tự nhiên và đường kính mạng nhỏ, nhưng tính ngẫu nhiên lại phá vỡ các quy tắc định tuyến thông thường (như DOR hay giao thức Duato). Việc áp dụng định tuyến đường đi ngắn nhất (Shortest Path Routing - SPR) đòi hỏi mỗi nút phải lưu toàn bộ thông tin tô-pô ($O(n)$ bản ghi), tạo thành điểm nghẽn nghiêm trọng về bộ nhớ bảng định tuyến (Routing Table Size - RTS) tại các switch có bậc đỉnh thấp.
• Về phương diện đánh giá, tính chất ngẫu nhiên của tô-pô đòi hỏi phải thực hiện tính toán và mô phỏng lặp lại nhiều lần trên các mẫu ngẫu nhiên để lấy giá trị trung bình. Các công cụ mô phỏng phổ biến hiện nay như NS2, NS3, Omnet++, Simgrid tập trung mô phỏng quá chi tiết các tầng giao thức nên tiêu tốn tài nguyên tính toán lớn, chỉ chạy được với quy mô mạng nhỏ (vài trăm đến khoảng 1.024 nút) và không đáp ứng được yêu cầu đánh giá mạng ngẫu nhiên quy mô lớn.
• Tại Việt Nam, nhu cầu xây dựng các DC quy mô vừa và nhỏ đối mặt với thách thức về nguồn vốn hạn chế và không gian lắp đặt phân tán (nhiều phòng hoặc sàn không liền kề), khiến các mô hình DC quy mô lớn trên thế giới không hoàn toàn phù hợp.

Mục tiêu nghiên cứu

Luận án xác định 02 mục tiêu nghiên cứu cụ thể:

1. 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 (compact routing) có khả năng khai thác các tính chất của tô-pô mạng ngẫu nhiên kích thước lớn, đảm bảo kích thước bảng định tuyến nhỏ mà vẫn duy trì chiều dài đường định tuyến và độ trễ ở mức thấp, phù hợp với các DC hiện nay.
2. Mục tiêu 2: Nghiên cứu và đề xuất kiến trúc công cụ phần mềm mô phỏng hỗ trợ đánh giá hiệu năng mạng ngẫu nhiên kích thước lớn.

Đối tượng và phạm vi nghiên cứu

• Đối tượng nghiên cứu: Cấu trúc tô-pô mạng liên kết, mô hình mạng ngẫu nhiên tựa đồ thị lưới (RSN), các giải thuật định tuyến rút gọn phân tán tra bảng, cơ chế điều khiển luồng và công cụ mô phỏng sự kiện rời rạc cho mạng liên kết hiệu năng cao.
• Phạm vi nghiên cứu: Tập trung vào các mạng liên kết ứng dụng trong mạng vùng hệ thống/lưu trữ (System/Storage Area Networks - SANs) phục vụ tính toán hiệu năng cao và trung tâm dữ liệu; khảo sát các cấu hình mạng quy mô lớn lên đến 100.000 nút; nghiên cứu giải pháp thiết kế tô-pô lai cho DC cỡ vừa và nhỏ trong điều kiện không gian phân tán tại Việt Nam.

---

Tổng quan tài liệu và vị trí của luận án

Luận án đã tiến hành hệ thống hóa các hướng nghiên cứu trong nước và quốc tế liên quan đến cấu trúc tô-pô, giải thuật định tuyến và công cụ mô phỏng:

Nhóm nghiên cứu	Các công trình và tác giả tiêu biểu	Đặc điểm và hạn chế đã được ghi nhận
Tô-pô cơ bản & truyền thống	De Bruijn, Star, Kautz, 2D-Torus, Mesh, Ring, Tree (Dally & Towles [5], [7])	Phù hợp quy mô nhỏ; kém linh hoạt khi mở rộng, độ trễ tăng nhanh khi số nút lớn.
Tô-pô trung tâm dữ liệu	Fat-Tree (Al-Fares et al. [23, 42]), JellyFish (Singla et al. [13]), Dragonfly (Kim et al. [21, 30]), HELIOS [15], BCube [16], DCell [17], Scafida [18], MDCube [19]	Fat-Tree đắt đỏ và khó nâng cấp lẻ nút; JellyFish mở rộng tốt nhưng khó định tuyến và cần switch 48 cổng.
Tô-pô lai (Compound Graph)	BCN [44], DCell [17], R3 [45]	R3 kết hợp Hypercube và liên kết ngẫu nhiên, song đường kính mạng còn lớn và khó truy vết định tuyến.
Định tuyến phân cấp & rút gọn	Kleinrock & Kamoun [38], Peleg & Upfal [39], Gavoille [36], Cowen [28], Thorup & Zwick [29]	Kleinrock & Kamoun khởi xướng định tuyến phân cấp; Cowen đề xuất định tuyến dựa trên nút đại diện (stretch-3, RTS $\tilde{O}(n^{2/3})$); Thorup & Zwick (TZ) tối ưu RTS về $O((n\log n)^{1/2})$.
Công cụ mô phỏng mạng	NS2 [1], NS3 [2], Omnet++ [4], Simgrid [3]	Mô phỏng chi tiết các tầng mạng dẫn đến quá tải bộ nhớ và thời gian; khó thực thi trên mạng trên 1.000 nút.

Khoảng trống nghiên cứu luận án lựa chọn giải quyết

1. Khắc phục hạn chế của thuật toán định tuyến rút gọn TZ: Cơ chế chọn mẫu ngẫu nhiên của TZ có thể chọn phải các nút đại diện phân bố không đều, dẫn đến kích thước cụm ($M$) cục bộ bị phình to và tăng RTS. Luận án chọn hướng khai thác vị trí địa lý của nút đại diện và các liên kết ngẫu nhiên đóng vai trò cầu nối liên vùng.
2. Xây dựng công cụ mô phỏng sự kiện rời rạc mức giản lược chuyên biệt cho mạng liên kết, hỗ trợ tính toán xấp xỉ nhằm xử lý các mạng ngẫu nhiên quy mô siêu lớn mà các phần mềm như NS3 hay Omnet++ không thực hiện được.
3. Thiết kế kiến trúc tô-pô lai (Bus-RSN) tối ưu hóa chi phí cáp và thiết bị chuyển mạch cho các DC quy mô vừa có mặt bằng phân tán.

---

Cơ sở lý thuyết và phương pháp nghiên cứu

Cơ sở lý thuyết và khái niệm sử dụng

• Lý thuyết đồ thị trong mạng liên kết: Mạng được mô hình hóa bởi đồ thị $G = (V, E)$ với tập đỉnh $V$ (máy chủ, switch) và tập cạnh $E$ (kênh truyền, cáp mạng). Kênh truyền $c = (x, y) \in C$ có băng thông $b_c = w_c \cdot f_c$, độ trễ $t_c = l_c / v$. Bậc đỉnh $\delta_x = |C_x| = \theta_{Ix} + \theta_{Ox}$. Băng thông lát cắt tối thiểu $B_B = \min |B(N_1, N_2)| = b \cdot B_C$.
• Giải thuật định tuyến: Phân loại theo cơ chế phân tán tra bảng (Distributed Table Lookup Routing), định tuyến xác định (Deterministic) như Dimension-Order Routing (DOR), Destination-Tag Routing (DTR); định tuyến ngẫu nhiên (Valiant); định tuyến thích nghi (Adaptive Routing); định tuyến tối thiểu (Minimal) và không tối thiểu (Non-minimal).
• Cơ chế điều khiển luồng (Flow Control): Bufferless, chuyển mạch kênh (Circuit Switching với gói tin thăm dò và ACK), chuyển mạch gói lưu và chuyển tiếp (Store-and-Forward), cắt xuyên ảo (Virtual Cut-Through) và kỹ thuật Wormhole Switching (chia nhỏ gói tin thành các flits 16-bit, giảm kích thước bộ đệm tại switch).
• Các tham số hiệu năng cốt lõi:
  • Đường kính mạng ($H_{\max} = \max(\forall H(u, v))$) và Chiều dài đường đi ngắn nhất trung bình (ASPL).
  • Chiều dài đường định tuyến trung bình (ARPL) và Độ trễ truyền tin trung bình (Latency).
  • Kích thước bảng định tuyến (RTS) - tính theo số lượng bản ghi lưu trữ tại mỗi nút.
  • Thông lượng (Throughput) và Thông lượng cực đại (Maximum Throughput).
  • Hệ số dãn đường đi (Stretch) - tỉ lệ giữa chiều dài đường định tuyến thực tế và khoảng cách ngắn nhất giữa nguồn và đích (stretch-1 là định tuyến đường ngắn nhất, stretch-3 cho phép đường đi gấp tối đa 3 lần).

Phương pháp nghiên cứu

• Phương pháp phân tích lý thuyết đồ thị: Tính toán các tham số hình học tĩnh của mạng ($H_{\max}$, ASPL, ARPL lý thuyết, RTS, Bisection bandwidth) dựa trên cấu trúc liên kết và tọa độ đỉnh.
• Phương pháp thực nghiệm mô phỏng sự kiện rời rạc (Discrete Event Simulation - DES): Xây dựng môi trường mô phỏng giả lập quá trình sinh gói tin, truyền flits qua các kênh truyền, xếp hàng tại bộ đệm, điều khiển luồng và ghi nhận độ trễ động, thông lượng mạng dưới các kịch bản tải không (zeroload) và tải trọng số (weightedload).
• Phương pháp tính toán xấp xỉ (Approximation method): Áp dụng kỹ thuật xấp xỉ mẫu để ước lượng ARPL và độ trễ trên các đồ thị ngẫu nhiên quy mô siêu lớn.
• Phương pháp thực nghiệm so sánh đối chuẩn (Benchmarking): Cài đặt các thuật toán đối chứng (TZ, SPR, DOR) và đối chiếu kết quả đo kiểm của công cụ SSiNET với phần mềm chuẩn quốc tế (NS3, Omnet++).

---

Nội dung chính theo từng chương

Chương 1: Tổng quan

Chương 1 thiết lập bức tranh tổng thể về mạng liên kết, phân tích các thành phần cấu tạo, cơ chế định tuyến và các công cụ đánh giá hiệu năng.

• Phân loại ứng dụng mạng liên kết: Bao gồm On-chip networks (OCNs/NoC, khoảng cách vài cm), System/Storage area networks (SANs, hàng nghìn thiết bị, cự ly vài trăm mét), Local area networks (LANs) và Wide area networks (WANs). Luận án định vị trọng tâm vào lĩnh vực SANs cho HPC và DC.
• Đánh giá các cơ chế điều khiển luồng: Phân tích sự đánh đổi tài nguyên giữa Store-and-Forward, Virtual Cut-Through và Wormhole Switching; trong đó Wormhole switching tối ưu bộ đệm flit nhưng có nguy cơ tắc nghẽn dọc chuỗi switch.
• Khảo sát các giải pháp định tuyến rút gọn: Phân tích nguyên lý phân cấp (Kleinrock & Kamoun) và nguyên lý nút đại diện (Cowen, Thorup & Zwick). Thuật toán TZ đạt kích thước bảng định tuyến $O((n\log n)^{1/2})$ với stretch-3 nhờ thuật toán chọn mẫu ngẫu nhiên Algo1-TZ.
• Đánh giá giới hạn của các công cụ mô phỏng hiện có: NS2, NS3, Omnet++, Simgrid gặp rào cản tính toán lớn khi mô phỏng mạng ngẫu nhiên vượt quá $1.024$ nút do mô hình hóa chi tiết tất cả các tầng giao thức.
• Đề xuất sơ bộ bài toán tô-pô cho DC tại Việt Nam: Phân tích hạn chế chi phí của Fat-Tree, tính phức tạp định tuyến của JellyFish và đưa ra định hướng mô hình tô-pô lai Bus-RSN.

Chương 2: Định tuyến rút gọn cho mô hình mạng ngẫu nhiên

Chương 2 tập trung giải quyết bài toán định tuyến trên mô hình mạng ngẫu nhiên xây dựng từ đồ thị cơ sở dạng lưới 2-D $G = (V, E)$ kích thước $8 \times 4$ (và mở rộng dạng $k$-grid) bổ sung $r = 2 \cdot k$ liên kết ngẫu nhiên theo phân bố xác suất đều (với ngưỡng ngẫu nhiên $thr = 0.5$). Nghiên cứu sinh đề xuất hai giải pháp định tuyến phân tán tra bảng:

1. Giải pháp định tuyến CORRA (Compact Routing for RAndom inter-connection topologies):

   • Ý tưởng: Mỗi nút nguồn $s$ xây dựng vùng hàng xóm $N_\delta(s)$ trong bán kính $\delta$ hop (theo khoảng cách Manhattan $|X_s - X_u| + |Y_s - Y_u| \le \delta$). Thay vì chỉ đi theo liên kết lưới cơ sở, nút $s$ tìm kiếm và sử dụng các liên kết ngẫu nhiên xuất phát từ các nút hàng xóm $u \in N_\delta(s)$ đóng vai trò như các "cầu nối" (bridges) dài vượt vùng.
   • Cơ chế: Nút hàng xóm $u$ gửi thông tin cầu nối ($bridge_1$) cho $s$; $s$ lưu trữ thông tin cầu nối ($bridge_2$) nằm trong phạm vi $\delta$. Bảng định tuyến ghi nhận các bản ghi gồm đích đến, nhãn và tọa độ nút.
   • Kết quả: Tham số $\delta$ kiểm soát trực tiếp kích thước bảng định tuyến RTS. CORRA có ARPL dài hơn không đáng kể so với đường đi ngắn nhất (SPR), độ trễ thấp hơn thuật toán TZ, trong khi RTS nhỏ hơn rất nhiều so với SPR, cho phép mạng mở rộng lên quy mô hàng trăm nghìn nút.

2. Giải pháp định tuyến GLCR (Geographic Landmark-based Compact Routing):

   • Ý tưởng: Cải tiến thuật toán TZ bằng cách khai thác tọa độ địa lý nhằm khắc phục hiện tượng các nút đại diện phân bố co cụm.
   • Cơ chế kỹ thuật: Sử dụng thuật toán điều chỉnh tập nút đại diện AdjustLandmarkSet và hàm lấy mẫu mới NewSample(W, b) để các nút đại diện phân bố đều trên toàn mạng. Phát triển cơ chế tuyển chọn nâng cao (IJDST) gồm: thuật toán loại bỏ nút đại diện yếu $\alpha-LS$, lựa chọn nút đại diện $\alpha-LS$ và lựa chọn nút đại diện $\beta-LS$.
   • Kết quả: Khảo sát tương quan giữa kích thước tập nút đại diện $L$, kích thước cụm lớn nhất $M$, $RTS_{\max}$ và ARPL. Trên mạng có quy mô lên tới 100.000 nút, GLCR đạt RTS nhỏ hơn đáng kể so với thuật toán TZ nguyên bản (TZ-original) trong khi duy trì ARPL ổn định.

Chương 3: Xây dựng công cụ hỗ trợ đánh giá hiệu năng mạng liên kết

Chương 3 trình bày việc xây dựng phần mềm mô phỏng SSiNET và ứng dụng công cụ này vào thiết kế mô hình mạng thực tế:

• Kiến trúc công cụ phần mềm SSiNET (Simple Simulator for Interconnection NETworks):
  • Được thiết kế dựa trên mô hình mô phỏng sự kiện rời rạc (DES) giản lược, loại bỏ các tầng giao thức không cần thiết để tập trung vào hiệu năng truyền gói tin trên mạng liên kết.
  • Cấu trúc hệ thống gồm giao diện người dùng (GUI) và các gói mô-đun: gói graph (quản lý lớp Graph, cấu trúc nút, kênh truyền), gói routing (quản lý lớp RoutingAlgorithm, thuật toán CORRA, GLCR, TZ, SPR), gói thực nghiệm (TopoExperiment, zeroload, weightedload).
  • Tích hợp phương pháp xấp xỉ cho phép tính toán đường kính mạng, ARPL, độ trễ và thông lượng trên các mạng quy mô lớn vượt bậc.
• Thực nghiệm kiểm chứng công cụ:
  • Thời gian thực thi: SSiNET có tốc độ thực thi tính toán vượt trội so với NS3 trên cùng cấu hình mạng.
  • Độ chính xác: Đánh giá thông lượng và thông lượng cực đại cho kết quả tương đương với phần mềm Omnet++, chứng minh tính đúng đắn của giải thuật mô phỏng.
• Ứng dụng SSiNET đề xuất mô hình tô-pô lai Bus-RSN cho trung tâm dữ liệu:
  • Kiến trúc: Kết hợp tô-pô Bus làm đường trục (backbone) liên kết giữa các phòng/sàn máy chủ riêng biệt; bên trong mỗi phòng/sàn, các máy chủ được kết nối theo mô hình mạng ngẫu nhiên RSN ($4 \times 4$). Mạng phân chia thành các nút thường và nút trục.
  • Giải thuật định tuyến: Áp dụng thuật toán định tuyến phân cấp HRA ($\alpha-1\text{ HRA}$).
  • Đánh giá hiệu quả kinh tế - kỹ thuật: Tiến hành thực nghiệm 2 kịch bản lắp đặt trên không gian 2 sàn riêng biệt. Kết quả cho thấy Bus-RSN tiết kiệm đến 26% chi phí thiết bị mạng so với mô hình JellyFish trong khi độ trễ truyền tin chỉ kém 12%; đồng thời giảm thiểu đáng kể tổng chiều dài cáp kết nối và chi phí triển khai.

---

Kết quả và những đóng góp mới

Các kết quả nghiên cứu chính của luận án được tổng hợp cụ thể qua bảng sau:

STT	Tên giải pháp / Đóng góp	Bản chất kỹ thuật	Kết quả định lượng & Giá trị thực tiễn
1	Thuật toán định tuyến CORRA	Định tuyến rút gọn khai thác liên kết ngẫu nhiên làm cầu nối trong vùng lân cận $\delta$-hop	Đạt ARPL gần tối ưu, độ trễ thấp hơn TZ, RTS giảm sâu so với SPR; hỗ trợ mạng mở rộng hàng trăm nghìn nút.
2	Thuật toán định tuyến GLCR & cơ chế IJDST	Định tuyến rút gọn điều chỉnh phân bố nút đại diện theo vị trí địa lý; loại bỏ $\alpha-LS$, chọn $\beta-LS$	Giảm kích thước cụm tối đa $M$, đạt RTS nhỏ hơn rõ rệt so với thuật toán TZ trên quy mô mạng tới 100.000 nút.
3	Công cụ mô phỏng SSiNET	Phần mềm mô phỏng sự kiện rời rạc giản lược tích hợp phương pháp đánh giá xấp xỉ	Thời gian thực thi nhanh hơn NS3, kết quả thông lượng khớp với Omnet++; hỗ trợ mô phỏng mạng ngẫu nhiên quy mô lớn.
4	Tô-pô lai Bus-RSN & thuật toán HRA	Kiến trúc lai dùng Bus làm đường trục kết nối các khối RSN cục bộ đặt tại các phòng/sàn	Tiết kiệm 26% chi phí thiết bị mạng so với JellyFish, độ trễ chỉ chênh lệch 12%; giảm tổng chiều dài cáp cho DC cỡ vừa tại Việt Nam.

Danh mục công trình khoa học đã công bố của tác giả

Nghiên cứu sinh đã công bố 06 công trình khoa học (CT1 đến CT6), gồm:

• 04 công trình về thuật toán định tuyến: Gồm công trình về định tuyến CORRA (CT2), định tuyến GLCR (CT3), cơ chế tuyển chọn nút đại diện IJDST (CT5) và các bài báo liên quan.
• 02 công trình về công cụ mô phỏng và ứng dụng: Gồm bài báo xây dựng kiến trúc phần mềm SSiNET (CT4) và giải pháp thiết kế tô-pô lai Bus-RSN cho DC (CT6) đăng trên Chuyên san Các công trình nghiên cứu, phát triển và ứng dụng Công nghệ Thông tin và Truyền thông.

---

Hạn chế và hướng nghiên cứu tiếp

Hạn chế của nghiên cứu

• Các thuật toán định tuyến rút gọn CORRA và GLCR chủ yếu được khảo sát và thực nghiệm trên mô hình mạng ngẫu nhiên xây dựng từ đồ thị cơ sở dạng lưới 2-D và $k$-grid; chưa mở rộng đánh giá toàn diện trên các đồ thị cơ sở phức tạp khác.
• Công cụ mô phỏng SSiNET được xây dựng phục vụ nghiên cứu nội bộ tại Sedic-Lab, hiện vẫn đang trong quá trình tiếp tục hoàn thiện giao diện và bổ sung thêm các mô-đun chức năng.

Hướng nghiên cứu tiếp theo

1. Tiếp tục hoàn thiện, mở rộng các chức năng và phương thức thực nghiệm của công cụ mô phỏng SSiNET, tiến tới công bố rộng rãi trên Internet nhằm phục vụ cộng đồng nghiên cứu mạng liên kết.
2. Mở rộng các nhánh nghiên cứu chuyên biệt về thuật toán định tuyến cho các dạng cấu trúc tô-pô mạng ngẫu nhiên và tô-pô lai mới trong các hệ thống tính toán quy mô siêu lớn.

---

Giá trị tham khảo

Luận án mang lại giá trị tham khảo khoa học và ứng dụng thực tiễn cho nhiều nhóm đối tượng:

• Cộng đồng nghiên cứu, giảng viên và nghiên cứu sinh: Cung cấp tài liệu chuyên khảo về lý thuyết đồ thị trong mạng liên kết, cơ chế điều khiển luồng, phương pháp thiết kế thuật toán định tuyến rút gọn (CORRA, GLCR) và kỹ thuật xây dựng công cụ mô phỏng sự kiện rời rạc mức hệ thống.
• Các tổ chức, doanh nghiệp triển khai DC vừa và nhỏ tại Việt Nam: Mô hình Bus-RSN cung cấp phương án thiết kế thực tế giúp các cơ quan ban ngành, ngân hàng, tổ chức xã hội tối ưu hóa ngân sách đầu tư, tận dụng không gian các phòng máy chủ sẵn có mà vẫn đảm bảo khả năng mở rộng.
• Các nhà cung cấp dịch vụ viễn thông và trung tâm dữ liệu lớn: Các doanh nghiệp vận hành hạ tầng số như Viettel DC, FPT DC, VNPT DC, VTC DC, EVN DC có thể tham khảo phương pháp đánh giá xấp xỉ của SSiNET để phân tích hiệu năng các kiến trúc mạng quy mô lớn trước khi triển khai thực tế.

---

Câu hỏi thường gặp

1. Ý tưởng cốt lõi của giải thuật định tuyến CORRA là gì và giải thuật này giải quyết vấn đề gì của mạng ngẫu nhiên?

CORRA (Compact Routing for RAndom inter-connection topologies) khai thác đặc trưng của mạng ngẫu nhiên bằng cách xây dựng vùng lân cận $N_\delta(s)$ trong bán kính $\delta$ hop quanh nút nguồn $s$ (theo khoảng cách Manhattan). Thay vì chỉ đi theo các liên kết lưới truyền thống, nút nguồn sẽ tìm và sử dụng các liên kết ngẫu nhiên xuất phát từ các nút hàng xóm đóng vai trò như các "cầu nối" dài liên kết trực tiếp tới các vùng mạng ở xa. Giải pháp này giúp chiều dài đường định tuyến (ARPL) và độ trễ đạt mức gần tối ưu tương đương định tuyến đường ngắn nhất (SPR), nhưng kích thước bảng định tuyến (RTS) giảm đi rất nhiều, cho phép mạng mở rộng lên hàng trăm nghìn nút.

2. Thuật toán GLCR cải tiến thuật toán định tuyến rút gọn phổ quát TZ (Thorup & Zwick) ở điểm nào?

Thuật toán TZ nguyên bản sử dụng cơ chế chọn mẫu ngẫu nhiên thuần túy, dễ dẫn đến việc các nút đại diện phân bố không đều, tạo ra các cụm nút có kích thước $M$ quá lớn và làm tăng RTS cục bộ. GLCR (Geographic Landmark-based Compact Routing) cải tiến thuật toán TZ bằng cách tích hợp yếu tố vị trí địa lý: sử dụng quy trình AdjustLandmarkSet và hàm NewSample(W, b) để điều chỉnh các nút đại diện phân bố đồng đều trên toàn bộ không gian mạng. Đồng thời, GLCR bổ sung cơ chế tuyển chọn IJDST để loại bỏ các nút đại diện yếu ($\alpha-LS$) và chọn lọc các nút đại diện tối ưu ($\beta-LS$), giúp giảm đáng kể $RTS$ trên các mạng quy mô lớn đến 100.000 nút.

3. Công cụ mô phỏng SSiNET có gì khác biệt so với các phần mềm mô phỏng mạng như NS3 hay Omnet++?

Các công cụ như NS2, NS3, Omnet++, Simgrid là các phần mềm mô phỏng mạng phổ quát, mô hình hóa chi tiết đầy đủ các tầng giao thức và đối tượng mạng phân cấp, dẫn đến tiêu tốn bộ nhớ và thời gian tính toán rất lớn, chỉ chạy được với mạng từ vài trăm đến khoảng 1.024 nút. SSiNET áp dụng mô hình mô phỏng sự kiện rời rạc giản lược, tập trung chuyên biệt vào cơ chế truyền flits và chuyển tiếp gói tin của mạng liên kết, đồng thời tích hợp phương pháp tính toán xấp xỉ. Nhờ đó, SSiNET đạt tốc độ thực thi nhanh hơn NS3, kết quả thông lượng tương đương Omnet++, và có khả năng đánh giá các tô-pô mạng ngẫu nhiên quy mô siêu lớn.

4. Kiến trúc tô-pô lai Bus-RSN đem lại lợi ích kinh tế - kỹ thuật gì cho trung tâm dữ liệu cỡ vừa tại Việt Nam?

Bus-RSN kết hợp đường trục dạng Bus để kết nối các phòng/sàn máy chủ phân tán, trong khi bên trong mỗi phòng/sàn sử dụng mô hình mạng ngẫu nhiên RSN cục bộ. Dưới sự điều khiển của thuật toán định tuyến phân cấp HRA ($\alpha-1\text{ HRA}$), thực nghiệm trên công cụ SSiNET với không gian 2 sàn riêng biệt chứng minh Bus-RSN giúp tiết kiệm đến 26% chi phí thiết bị mạng so với mô hình JellyFish trong khi độ trễ truyền tin chỉ kém 12%. Giải pháp này đồng thời giảm tổng chiều dài cáp mạng, đáp ứng tốt bài toán mặt bằng không liền kề và nguồn vốn hạn chế của các doanh nghiệp tại Việt Nam.

---

Kết luận

Luận án tiến sĩ của nghiên cứu sinh Kiều Thành Chung đã giải quyết trọn vẹn hai bài toán lớn trong lĩnh vực mạng liên kết hiệu năng cao: đề xuất các giải thuật định tuyến rút gọn (CORRA, GLCR) giúp thu nhỏ kích thước bảng định tuyến trên mạng ngẫu nhiên quy mô lớn, và phát triển thành công công cụ mô phỏng SSiNET hỗ trợ đánh giá hiệu năng mạng tốc độ cao. Các kết quả nghiên cứu không chỉ làm phong phú thêm cơ sở lý thuyết về định tuyến phân tán mà còn mang lại giải pháp thực tiễn có tính ứng dụng cao thông qua mô hình tô-pô lai Bus-RSN cho các trung tâm dữ liệu tại Việt Nam. Toàn bộ các đề xuất đã được kiểm chứng thực nghiệm chặt chẽ và công bố qua 06 công trình khoa học chuyên ngành.

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

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 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. 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ừ 𝑇𝐵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.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ế. 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.

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

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