Tổng quan luận án

Bả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á” do nghiên cứu sinh Kiều Thành Chung thực hiện 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 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ông trình được triển khai nghiên cứu tại phòng thí nghiệm Sedic-Lab cùng sự phối hợp học thuật từ các chuyên gia thuộc Viện Tin học Quốc gia Nhật Bản (National Institute of Informatics – NII). Luận án thuộc chuyên ngành Công nghệ thông tin, tập trung vào lĩnh vực kiến trúc mạng liên kết, mạng truyền thông cho các hệ thống tính toán hiệu năng cao (HPC) và các trung tâm dữ liệu (Data Center - DC).

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

Trong kiến trúc mạng máy tính hiện đại, mạng liên kết đóng vai trò là hạ tầng truyền dẫn lõi kết nối hàng nghìn nút tính toán và lưu trữ. Các cấu trúc tô-pô truyền thống như De Bruijn, Star, Kautz, Mesh, Torus hay cấu trúc cây Fat-Tree bộc lộ nhiều điểm hạn chế lớn khi mở rộng quy mô:

  • Khả năng co giãn (scalability) và tính linh hoạt (flexibility) kém: Khi tăng hoặc giảm số lượng nút tính toán để phục vụ bảo trì, mở rộng hoặc tiết kiệm năng lượng, hệ thống đòi hỏi các thao tác tái cấu hình phức tạp với chi phí phần cứng rất cao.
  • Phụ thuộc vào thiết bị chuyển mạch bậc đỉnh cao: Các mô hình như Fat-Tree đòi hỏi các switch chuyên dụng có số lượng cổng lớn (bậc đỉnh cao) dẫn đến gia tăng chi phí đầu tư hạ tầng.
  • Mô hình mạng ngẫu nhiên (như RSN - Random Shortcut Network, JellyFish) được đề xuất nhằm thu hẹp đường kính mạng, giảm độ trễ và hỗ trợ mở rộng tự nhiên. Tuy nhiên, tính ngẫu nhiên phá vỡ quy luật định tuyến chuẩn tắc (như Dimension-Order Routing - DOR hay giao thức Duato). Nếu áp dụng thuật toán định tuyến đường đi ngắn nhất (Shortest Path Routing - SPR), bảng định tuyến tại mỗi nút mạng phải lưu trữ toàn bộ thông tin tô-pô với kích thước bùng nổ theo cấp số $O(n)$, vượt quá giới hạn bộ nhớ vật lý của các switch khi kích thước mạng tăng lên hàng chục nghìn đến hàng trăm nghìn nút.
  • Khoảng trống về công cụ đánh giá: Việc đánh giá hiệu năng mạng ngẫu nhiên quy mô lớn đòi hỏi phải thực nghiệm nhiều lần để tính giá trị trung bình. Các phần mềm mô phỏng mạng hiện hành như NS2, NS3, Omnet++, Simgrid mô phỏng chi tiết đầy đủ các tầng giao thức, dẫn đến tiêu tốn tài nguyên tính toán và bộ nhớ khổng lồ, không thể chạy được hoặc thực thi rất chậm khi quy mô mạng đạt tới kích thước lớn.

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

Luận án xác định hai mục tiêu nghiên cứu cụ thể được đánh số theo văn bản:

  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ó 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 trung tâm dữ liệu hiện nay.
  2. 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.

Đố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 hiệu năng cao (mạng ngẫu nhiên RSN trên nền lưới cơ sở 2-D, tô-pô lai Bus-RSN).
    • Thuật toán định tuyến rút gọn phân tán tra bảng: thuật toán định tuyến khai thác cầu nối (CORRA) và thuật toán định tuyến khai thác nút đại diện theo vị trí địa lý (GLCR).
    • Kiến trúc phần mềm và phương pháp mô phỏng sự kiện rời rạc hỗ trợ đánh giá hiệu năng mạng liên kết (SSiNET).
  • Phạm vi nghiên cứu:
    • Không gian: Tập trung vào mạng liên kết trong phân vùng mạng vùng hệ thống/lưu trữ (System/Storage Area Networks - SANs) ứng dụng cho tính toán hiệu năng cao (HPC) và trung tâm dữ liệu (DC); nghiên cứu bài toán bố trí mạng trung tâm dữ liệu cỡ vừa và nhỏ trong điều kiện mặt bằng phòng máy phân tán (nhiều phòng hoặc các sàn/tầng khác nhau trong tòa nhà) tại Việt Nam.
    • Quy mô mạng: Khảo sát thực nghiệm từ các mạng kích thước nhỏ vài trăm nút đến các mạng quy mô lớn đạt 100.000 nút tính toán.
    • Thời gian và phương diện công nghệ: Nghiên cứu lý thuyết kết hợp mô phỏng thực nghiệm trên máy tính, đối sánh với các tiêu chuẩn kiến trúc mạng máy tính hiện hành và các bộ công cụ mô phỏng phổ biến.

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

Luận án đã hệ thống hóa các hướng nghiên cứu lớn trong và ngoài nước liên quan đến thiết kế tô-pô mạng liên kết, giải thuật định tuyến và phần mềm mô phỏng:

Các hướng nghiên cứu trước được điểm lại

  1. Kiến trúc tô-pô mạng liên kết truyền thống và hiện đại:
    • Các cấu trúc tô-pô cơ sở: Bus, Ring, Star, Mesh, Tree, k-ary n-cube Torus đã được Dally và Towles [5], Duato và cộng sự [6, 7] phân tích toàn diện.
    • Các tô-pô trung tâm dữ liệu quy mô lớn: Fat-Tree của Al-Fares và cộng sự [23, 42]; Dragonfly của Kim và cộng sự [21, 30]; JellyFish của Singla và cộng sự [13]; DCell của Guo và cộng sự [17]; BCube [16]; MDCube [19]; HELIOS [15]; Scafida [18].
    • Các mô hình tô-pô dạng đồ thị hỗn hợp (compound graph): BCN [44], R3 [45] kết hợp giữa Hypercube và mạng ngẫu nhiên.
  2. Kỹ thuật chuyển mạch và giải thuật định tuyến:
    • Các cơ chế chuyển mạch: Chuyển mạch mạch (circuit switching), chuyển mạch lưu và chuyển tiếp (store-and-forward / packet switching), chuyển tiếp cắt xuyên ảo (virtual cut-through), và chuyển mạch Wormhole [5, 9] sử dụng các đơn vị dữ liệu nhỏ (flit).
    • Kỹ thuật định tuyến xác định: Dimension-Order Routing (DOR), Destination-Tag Routing (DTR), định tuyến ngẫu nhiên Valiant [5], định tuyến thích ứng dựa trên trạng thái cục bộ của mạng.
  3. Định tuyến phân cấp và định tuyến rút gọn (Compact Routing):
    • Định tuyến phân cấp: Kleinrock và Kamoun [38] khởi xướng phương pháp gom cụm nút mạng để giảm kích thước bảng định tuyến (RTS); Peleg và Upfal [39] phân tích sự đánh đổi (trade-off) giữa hệ số co giãn đường đi (stretch) và RTS.
    • Định tuyến rút gọn phổ quát dựa trên nút đại diện (landmark-based): Cowen [28] đề xuất kịch bản định tuyến stretch-3 với kích thước bảng định tuyến đạt mức $\tilde{O}(n^{2/3})$; Thorup và Zwick [29] cải tiến cơ chế chọn nút đại diện ngẫu nhiên (thuật toán TZ), đạt stretch-3 với kích thước bảng định tuyến tối ưu ở mức $O((n \log n)^{1/2})$.
    • Các nghiên cứu giới hạn lý thuyết: Gavoille [36] chứng minh định tuyến rút gọn cần $O(\sqrt{n})$ bit cho stretch-3; Thorup và Zwick [31] chứng minh định tuyến stretch-5 không thể đạt RTS nhỏ hơn $\Omega(n^{1/2})$.
  4. Công cụ mô phỏng đánh giá hiệu năng mạng:
    • Các phần mềm mô phỏng mạng phổ biến gồm NS2 [1], NS3 [2], Simgrid [3], Omnet++ [4]. Văn bản chỉ ra rằng Simgrid chỉ đánh giá được quy mô 256 nút trên máy thông thường và khoảng 1.024 nút trên máy tính cấu hình mạnh; NS3 và Omnet++ tiêu tốn quá nhiều tài nguyên bộ nhớ và thời gian tính toán khi mô phỏng mạng ngẫu nhiên cỡ lớn.

Khoảng trống luận án lựa chọn giải quyết

  • Thuật toán TZ của Thorup và Zwick tuy tối ưu về mặt lý thuyết nhưng cơ chế lấy mẫu ngẫu nhiên thuần túy dẫn đến việc các nút đại diện phân bố không đồng đều trên không gian mạng, gây ra hiện tượng kích thước cụm cục bộ lớn và làm tăng kích thước bảng định tuyến cực đại.
  • Thiếu giải pháp định tuyến rút gọn khai thác các liên kết ngẫu nhiên đóng vai trò là "cầu nối" giữa các vùng mạng ở xa nhau trên mô hình mạng ngẫu nhiên dạng lưới RSN.
  • Thiếu một công cụ mô phỏng chuyên dụng, giản lược tầng mạng để vừa hỗ trợ phân tích đồ thị tĩnh, vừa thực hiện mô phỏng sự kiện rời rạc động, có khả năng áp dụng kỹ thuật xấp xỉ cho mạng ngẫu nhiên lên tới hàng chục nghìn đến hàng trăm nghìn nút.
  • Thiếu một kiến trúc tô-pô mạng lai phù hợp với điều kiện xây dựng trung tâm dữ liệu cỡ vừa và nhỏ tại Việt Nam với ràng buộc về không gian sàn không liền kề và chi phí đầu tư hạn hẹp.

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

Khung lý thuyết và các khái niệm cốt lõi

  • Mô hình đồ thị mạng liên kết: Mạng được mô hình hóa thành đồ thị $G = (V, E)$, trong đó $V$ là tập các đỉnh đại diện cho thiết bị mạng (switch, server) và $E$ là tập các cạnh đại diện cho liên kết cáp truyền thông.
  • Tô-pô mạng ngẫu nhiên RSN (Random Shortcut Network): Xây dựng trên đồ thị cơ sở dạng lưới 2-D ($k$-grid). Các liên kết ngẫu nhiên được bổ sung giữa các cặp nút xa nhau dựa trên phân bố xác suất đều với số lượng liên kết ngẫu nhiên xác định trên mỗi nút ($r = 2k$). Khoảng cách giữa các nút được xác định bằng khoảng cách Manhattan: $|X_s - X_u| + |Y_s - Y_u|$.
  • Băng thông lát cắt (Bisection Bandwidth): Lát cắt mạng $C(N_1, N_2)$ chia tập nút thành hai nửa tương đương. Băng thông lát cắt $BB = \min |B(N_1, N_2)|$ xác định năng lực truyền dẫn tối thiểu qua lát cắt mạng.
  • Mô hình định tuyến và bảng định tuyến: Quan hệ định tuyến được biểu diễn dưới dạng ánh xạ $R: N \times N \rightarrow \mathcal{P}(P)$ hoặc $R: N \times N \rightarrow \mathcal{P}(C)$. Kích thước bảng định tuyến (RTS) đo bằng tổng số bản ghi định tuyến lưu trữ tại mỗi nút.
  • Mô hình độ trễ mạng: Độ trễ truyền tin không tranh chấp tài nguyên được biểu diễn qua công thức: $$\text{latency} = \text{injection_time} + \text{time_to_fly} + \text{switches_latency}$$
  • Hệ số co giãn (Stretch): Tỉ lệ giữa chiều dài đường định tuyến thực tế và chiều dài đường đi ngắn nhất giữa cặp nguồn - đích trong trường hợp xấu nhất.

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

Luận án kết hợp hai phương pháp nghiên cứu chính:

  1. Phương pháp phân tích đồ thị (Graph Analysis): Đánh giá các tham số tĩnh của mạng dựa trên cấu trúc hình học, bao gồm đường kính mạng ($H_{\max}$), chiều dài đường định tuyến trung bình (ARPL), chiều dài đường đi ngắn nhất trung bình (ASPL) và kích thước bảng định tuyến (RTS).
  2. Phương pháp mô phỏng thực nghiệm sự kiện rời rạc (Discrete Event Simulation - DES): Thiết lập mô phỏng động quá trình sinh gói tin, chuyển tiếp qua các bộ chuyển mạch, cơ chế hàng đợi và giải phóng tài nguyên. Đo đạc các thông số động gồm độ trễ truyền tin (latency), thông lượng (throughput) và thông lượng cực đại dưới các kịch bản tải không tải (zeroload) và có tải trọng (weightedload).
  3. Phương pháp xấp xỉ: Cài đặt thuật toán xấp xỉ trong công cụ mô phỏng để tính toán đường kính mạng và độ trễ trung bình trên các cấu hình mạng ngẫu nhiên quy mô rất lớn mà không cần duyệt toàn bộ mọi cặp đỉnh.

Nguồn tư liệu và dữ liệu thực nghiệm

  • Dữ liệu mạng được sinh tự động thông qua công cụ mô phỏng theo các tham số cấu hình: kích thước lưới cơ sở, số lượng liên kết ngẫu nhiên, ngưỡng xác suất $thr = 0.5$, và bán kính hàng xóm $\delta$.
  • Dữ liệu đối chuẩn (benchmarking): Thu thập từ việc cài đặt lại các thuật toán định tuyến chuẩn gồm Shortest Path Routing (SPR), thuật toán Thorup - Zwick (TZ gốc), và so sánh chéo kết quả mô phỏng giữa SSiNET với NS3 và Omnet++.

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

CHƯƠNG 1: TỔNG QUAN

Chương 1 cung cấp nền tảng lý thuyết toàn diện về mạng liên kết, phân tích các tham số hiệu năng cốt lõi và hệ thống hóa các nghiên cứu liên quan.

  • Phân loại mạng liên kết: Luận án phân chia mạng liên kết theo bốn lĩnh vực ứng dụng gồm On-chip networks (OCNs/NoC), System/storage area networks (SANs), Local area networks (LANs) và Wide area networks (WANs), trong đó xác định trọng tâm nghiên cứu thuộc về SANs và mạng cho trung tâm dữ liệu.
  • Phân tích các dạng tô-pô cơ bản: So sánh ưu nhược điểm của Bus, Star, Ring, Mesh, Tree; phân biệt giữa mạng trực tiếp (Direct Network) và mạng gián tiếp (Indirect Network); phân tích các cấu trúc tô-pô trung tâm dữ liệu hiện đại như Fat-Tree, Dragonfly, JellyFish, DCell.
  • Cơ chế định tuyến và điều khiển luồng: Trình bày chi tiết các cơ chế định tuyến phân tán tra bảng, định tuyến nguồn, định tuyến xác định (DOR, DTR), định tuyến thích ứng; phân tích kỹ thuật điều khiển luồng Wormhole switching, cơ chế đệm flit và nguy cơ tắc nghẽn (deadlock/livelock).
  • Các tham số hiệu năng và bài toán tối ưu: Phân tích mối tương quan và sự đánh đổi (trade-off) giữa đường kính mạng, ARPL, độ trễ truyền tin, thông lượng và kích thước bảng định tuyến (RTS).
  • Phát biểu hai bài toán nghiên cứu chính:
    • Bài toán 1: Thiết kế thuật toán định tuyến rút gọn cho mạng ngẫu nhiên tựa đồ thị lưới nhằm đạt RTS nhỏ, ARPL gần tối ưu, cho phép mở rộng quy mô lên hàng trăm nghìn nút.
    • Bài toán 2: Xây dựng kiến trúc công cụ mô phỏng SSiNET hỗ trợ đánh giá hiệu năng mạng liên kết quy mô lớn và ứng dụng đề xuất mô hình tô-pô lai Bus-RSN cho trung tâm dữ liệu cỡ vừa và nhỏ.

CHƯƠNG 2: ĐỊNH TUYẾN RÚT GỌN CHO MÔ HÌNH MẠNG NGẪU NHIÊN

Chương 2 trình bày chi tiết các giải pháp định tuyến rút gọn được đề xuất trên mô hình mạng ngẫu nhiên RSN xây dựng trên đồ thị cơ sở dạng lưới $G = (V, E)$.

Bảng tổng hợp các thông số kỹ thuật của các thuật toán định tuyến trong Chương 2
Thuật toán Cơ chế định tuyến chính Kích thước bảng định tuyến (RTS) Hệ số Stretch Đặc điểm cấu trúc
SPR Đường đi ngắn nhất toàn cục $O(n)$ Stretch-1 Lưu toàn bộ bảng định tuyến tại mỗi nút
TZ [29] Lấy mẫu landmark ngẫu nhiên $O((n \log n)^{1/2})$ Stretch-3 Landmark chọn ngẫu nhiên, cụm $M = 4n/z$
CORRA Khai thác cầu nối ngẫu nhiên Giảm mạnh so với SPR, lớn hơn TZ Gần tối ưu Bán kính hàng xóm $\delta$, khai thác liên kết xa
GLCR Landmark theo vị trí địa lý Nhỏ hơn TZ trên mạng lớn Stretch-3 Điều chỉnh phân bố đều landmark, lọc $\alpha$-LS, $\beta$-LS

1. Thuật toán định tuyến rút gọn CORRA (Compact Routing for RAndom inter-connection topologies)

  • Ý tưởng: Xây dựng vùng hàng xóm $N_\delta(s)$ trong phạm vi bán kính $\delta$ hop tính từ nút nguồn $s$ theo khoảng cách Manhattan. Thay vì chỉ sử dụng các liên kết lưới cục bộ, thuật toán tìm kiếm và lưu trữ thông tin về các liên kết ngẫu nhiên xuất phát từ các nút hàng xóm trong vùng $\delta$ đóng vai trò như các “cầu nối” (bridge) vươn tới các vùng nút mạng ở xa.
  • Quy trình hoạt động: Nút nguồn $s$ tra cứu bảng định tuyến; nếu đích đến nằm trong vùng lân cận của cầu nối, gói tin được chuyển tiếp qua cầu nối đó để nhảy vọt qua khoảng cách lớn, giúp giảm số lượng hop truyền tin.
  • Kết quả thực nghiệm:
    • Khảo sát tham số bán kính $\delta$: Khi $\delta$ tăng, kích thước bảng định tuyến (RTS) tăng lên nhưng ARPL và độ trễ truyền tin giảm rõ rệt.
    • So sánh hiệu năng: CORRA đạt ARPL dài hơn không đáng kể so với thuật toán đường đi ngắn nhất SPR, độ trễ truyền tin thấp hơn thuật toán TZ, trong khi kích thước RTS nhỏ hơn rất nhiều so với SPR, cho phép mạng mở rộng lên hàng trăm nghìn nút.

2. Thuật toán định tuyến rút gọn GLCR (Geographic Landmark-based Compact Routing)

  • Hạn chế của TZ nguyên bản: Thuật toán TZ khởi tạo tập nút đại diện $L$ với kích thước $z = \sqrt{n/\log n}$ qua thủ tục lấy mẫu ngẫu nhiên sample(W, z). Tính ngẫu nhiên thuần túy dẫn đến việc các landmark có thể tập trung dày đặc ở một vùng và thưa thớt ở vùng khác, khiến kích thước cụm $C(w)$ của một số nút vượt ngưỡng $M = 4n/z$, làm tăng RTS tối đa.
  • Cải tiến trong GLCR: Đưa yếu tố vị trí địa lý và tọa độ vào quá trình tuyển chọn nút đại diện. Bổ sung các giải thuật điều chỉnh:
    • Thuật toán NewSample(W, b) và AdjustLandmarkSet: Lựa chọn các nút đại diện phân bố rời xa nhau, trải đều trên toàn bộ không gian đồ thị dạng lưới.
    • Cơ chế tuyển chọn nâng cao (công bố IJDST): Thiết lập các thuật toán loại bỏ nút đại diện yếu $\alpha\text{-LS}$, thuật toán lựa chọn $\alpha\text{-LS}$ và $\beta\text{-LS}$.
  • Kết quả thực nghiệm: Phân bố các nút đại diện của GLCR đạt độ đồng đều cao trên không gian lưới. Kích thước cụm lớn nhất giảm rõ rệt so với TZ. Trên các mô phỏng mạng có kích thước lên tới 100.000 nút, GLCR đạt RTS nhỏ hơn đáng kể so với TZ nguyên bản trong khi vẫn duy trì ARPL ở mức tối ưu.

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 thiết kế kiến trúc phần mềm công cụ mô phỏng SSiNET và ứng dụng công cụ này để phát triển giải pháp kiến trúc tô-pô lai Bus-RSN.

1. Thiết kế và cài đặt công cụ phần mềm SSiNET

  • Mục tiêu thiết kế: Giản lược hóa việc mô hình hóa các tầng mạng không cần thiết vốn có ở các bộ mô phỏng truyền thống (như NS3, Omnet++), tập trung tối đa vào cấu trúc tô-pô đồ thị và quá trình chuyển tiếp gói tin, hỗ trợ đánh giá các mạng ngẫu nhiên quy mô lớn.
  • Kiến trúc mô-đun:
    • Gói cấu trúc đồ thị (graph): Quản lý các lớp Graph, RoutingAlgorithm, TopoExperiment.
    • Gói thành phần vật lý: Mô hình hóa các thiết bị mạng (nút, cổng vào/ra, kênh truyền, bộ chuyển mạch).
    • Gói thực nghiệm mô phỏng: Cung cấp tiến trình mô phỏng sự kiện rời rạc với hai chế độ tải zeroload (không tải) và weightedload (tải trọng có trọng số).
  • Kết quả đối chuẩn (benchmarking):
    • Thời gian thực thi: SSiNET thực hiện tính toán và mô phỏng với thời gian nhanh hơn đáng kể so với NS3 trên các mô hình mạng cùng kích thước.
    • Thông lượng mạng: Kết quả đánh giá thông lượng trên SSiNET tương thích chặt chẽ với kết quả từ Omnet++, khẳng định độ tin cậy của mô hình mô phỏng giản lược.
    • Phương pháp xấp xỉ: Cài đặt thành công kỹ thuật xấp xỉ để tính toán đường kính mạng và độ trễ trung bình toàn mạng cho các mạng ngẫu nhiên kích thước lớn mà các công cụ trước đây không thể xử lý do cạn kiệt tài nguyên tính toán.

2. Ứng dụng SSiNET đề xuất tô-pô lai Bus-RSN cho trung tâm dữ liệu

  • Bối cảnh thực tế tại Việt Nam: Các doanh nghiệp vừa và nhỏ thường phải thiết lập phòng máy chủ trong các không gian không liền kề, diện tích sàn bị giới hạn hoặc nằm ở các tầng khác nhau trong tòa nhà, nguồn vốn đầu tư ban đầu thấp.
  • Kiến trúc Bus-RSN: Kết hợp giữa đường trục Bus và cấu trúc mạng ngẫu nhiên RSN. Đường trục Bus đóng vai trò kênh kết nối liên vùng (giữa các phòng hoặc các sàn), trong khi mỗi vùng máy chủ cục bộ được kết nối bằng một cấu trúc tô-pô ngẫu nhiên RSN với bậc đỉnh thấp.
  • Giải thuật định tuyến HRA ($\alpha$-1 HRA): Áp dụng định tuyến phân cấp phân tách giữa định tuyến nội vùng (khai thác các liên kết trong khối RSN) và định tuyến liên vùng (thông qua các nút trục và đường Bus).
  • Kết quả thực nghiệm so sánh với Fat-Tree và JellyFish:
Bảng so sánh hiệu năng và chi phí của Bus-RSN với JellyFish trên kịch bản 2 sàn lắp đặt
Tiêu chí đánh giá Tô-pô JellyFish [13] Tô-pô đề xuất Bus-RSN Mức độ chênh lệch
Bậc đỉnh switch Bậc cao (bậc 48) Bậc thấp, linh hoạt Giảm độ phức tạp phần cứng
Tổng chi phí cáp và thiết bị Mức chuẩn 100% Tiết kiệm 26% Giảm 26% chi phí triển khai
Độ trễ truyền tin trung bình Mức tối ưu Thua kém 12% Độ trễ chỉ tăng 12%
Tính linh hoạt mở rộng Phức tạp khi mở rộng cục bộ Dễ dàng thêm/bớt nút theo vùng Phù hợp điều kiện phòng máy rời

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

Luận án đã đạt được các kết quả khoa học và đóng góp mới cụ thể về mặt lý luận và thực tiễn:

1. Đóng góp về lý luận và giải thuật

  • Đề xuất thuật toán định tuyến rút gọn CORRA, khai thác thành công tính chất cầu nối ngẫu nhiên giữa các vùng hàng xóm trong bán kính $\delta$, chứng minh khả năng đạt ARPL gần tối ưu và giảm mạnh kích thước bảng định tuyến so với thuật toán đường đi ngắn nhất SPR.
  • Đề xuất thuật toán định tuyến rút gọn GLCR, giải quyết hạn chế phân bố không đều của kịch bản phổ quát TZ bằng việc kết hợp thông tin vị trí địa lý, các thuật toán lấy mẫu điều chỉnh NewSample, AdjustLandmarkSet và cơ chế tuyển chọn landmark $\alpha\text{-LS}$, $\beta\text{-LS}$. Thuật toán đạt kích thước bảng định tuyến nhỏ hơn đáng kể so với TZ trên mạng có quy mô lên tới 100.000 nút.

2. Đóng góp về phần mềm và thực tiễn

  • Xây dựng thành công kiến trúc công cụ phần mềm SSiNET dựa trên kỹ thuật mô phỏng sự kiện rời rạc giản lược, cho phép đánh giá hiệu năng cả về đặc tính đồ thị tĩnh và mô phỏng động có tải, tích hợp phương pháp xấp xỉ giúp đánh giá các mạng ngẫu nhiên kích thước lớn vượt qua giới hạn của các công cụ NS3, Omnet++, Simgrid.
  • Đề xuất giải pháp kiến trúc tô-pô lai Bus-RSN cùng thuật toán định tuyến phân cấp HRA, đem lại phương án khả thi cho các trung tâm dữ liệu cỡ vừa và nhỏ tại Việt Nam: tiết kiệm tới 26% chi phí thiết bị và cáp mạng so với JellyFish trong khi độ trễ chỉ tăng 12%.
  • Các kết quả của luận án đã được công bố qua 06 công trình khoa học, bao gồm 04 bài báo về giải pháp định tuyến rút gọn và 02 bài báo về công cụ phần mềm mô phỏng 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.

Kiến nghị và giải pháp đề xuất

  • Khuyến nghị các doanh nghiệp viễn thông, trung tâm dữ liệu ngành tại Việt Nam cân nhắc ứng dụng mô hình tô-pô lai Bus-RSN khi đầu tư hạ tầng máy chủ trong các tòa nhà có diện tích sàn phân tán nhằm tối ưu hóa chi phí cáp và thiết bị chuyển mạch.
  • Đề xuất sử dụng công cụ SSiNET trong các phòng thí nghiệm nghiên cứu về mạng máy tính để thử nghiệm nhanh các giải pháp tô-pô và thuật toán định tuyến mới trước khi triển khai cấu hình phần cứng vật lý.

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

Dựa trên nội dung văn bản luận án trình bày, công trình còn một số hạn chế và định hướng phát triển như sau:

  • Phạm vi mô hình đồ thị cơ sở: Các giải pháp định tuyến rút gọn (CORRA, GLCR) chủ yếu được thiết kế và thực nghiệm trên đồ thị cơ sở dạng lưới 2-D mesh có bổ sung liên kết ngẫu nhiên. Hướng nghiên cứu tiếp theo cần mở rộng đánh giá trên các dạng đồ thị cơ sở khác như 3-D mesh, Torus hoặc các dạng đồ thị bất quy tắc tổng quát.
  • Cơ chế chịu lỗi và tắc nghẽn: Luận án tập trung giải quyết bài toán tối ưu kích thước bảng định tuyến, đường kính và độ trễ. Hướng phát triển tiếp theo cần nghiên cứu sâu hơn về định tuyến thích ứng có khả năng chịu lỗi (fault-tolerance) khi các nút hoặc liên kết ngẫu nhiên gặp sự cố đứt gãy.
  • Hoàn thiện công cụ SSiNET: Nhóm nghiên cứu tại phòng thí nghiệm Sedic-Lab đang tiếp tục hoàn thiện, bổ sung thêm các mô-đun chức năng, mở rộng phương thức thực nghiệm và tiến tới công bố công cụ SSiNET rộng rãi trên Internet phục vụ cộng đồng học thuật.

Giá trị tham khảo

Bản luận án mang lại giá trị tham khảo chuyên môn rõ ràng cho nhiều nhóm đối tượng:

  • Đối với nghiên cứu sinh, học viên cao học và giảng viên chuyên ngành Mạng máy tính: Là tài liệu chuyên khảo chi tiết về lý thuyết định tuyến rút gọn (Compact Routing), cơ chế phân cấp landmark, các kỹ thuật điều khiển luồng và phương pháp luận thiết kế công cụ mô phỏng sự kiện rời rạc.
  • Đối với các kỹ sư và kiến trúc sư hệ thống trung tâm dữ liệu: Cung cấp giải pháp kỹ thuật cụ thể (Bus-RSN) kèm theo các phân tích định lượng về chi phí cáp, lựa chọn switch bậc thấp và khả năng mở rộng từng phần cho các trung tâm dữ liệu quy mô vừa.
  • Đối với các doanh nghiệp vận hành hạ tầng số tại Việt Nam: Các số liệu thực nghiệm và kịch bản triển khai là tài liệu tham khảo thực tiễn hữu ích cho các đơn vị như Viettel DC, FPT DC, VNPT DC, VTC DC, EVN DC, cũng như các trung tâm dữ liệu của khối ngân hàng và các cơ quan quản lý nhà nước.

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

1. Thuật toán định tuyến CORRA khai thác đặc trưng nào của mạng ngẫu nhiên để tối ưu hóa đường truyền?

Thuật toán CORRA khai thác các liên kết ngẫu nhiên xuất phát từ các nút hàng xóm trong phạm vi bán kính $\delta$ hop (tính theo khoảng cách Manhattan trên đồ thị lưới cơ sở) như những “cầu nối” (bridge) nối liền các vùng mạng ở xa nhau. Thay vì chỉ truyền tin tuần tự qua các liên kết lưới cục bộ, nút nguồn tìm kiếm trong vùng hàng xóm của nó nút có cầu nối hướng tới vùng đích, giúp gói tin nhảy vọt qua khoảng cách lớn, giảm trung bình chiều dài đường định tuyến (ARPL) và giảm độ trễ truyền tin.

2. Điểm khác biệt căn bản giữa cơ chế chọn nút đại diện của GLCR và thuật toán TZ gốc là gì?

Thuật toán TZ gốc của Thorup và Zwick sử dụng thủ tục lấy mẫu ngẫu nhiên thuần túy sample(W, z), dẫn tới nguy cơ các nút đại diện phân bố không đồng đều (tập trung dày đặc ở một số khu vực và thưa thớt ở khu vực khác), làm kích thước cụm của một số nút phình to và tăng kích thước bảng định tuyến (RTS) tối đa. GLCR khắc phục điều này bằng cách tích hợp tọa độ địa lý, áp dụng thuật toán NewSample và AdjustLandmarkSet kết hợp cơ chế tuyển chọn $\alpha\text{-LS}$, $\beta\text{-LS}$ để điều chỉnh các nút đại diện phân bố rời xa nhau và trải đều toàn mạng, qua đó giảm kích thước cụm lớn nhất và giảm RTS tối đa.

3. Tại sao các công cụ mô phỏng mạng phổ biến như NS3 hay Omnet++ lại gặp khó khăn khi đánh giá mạng ngẫu nhiên quy mô lớn?

Các phần mềm như NS2, NS3, Omnet++ có tính phổ quát cao, tập trung mô phỏng chi tiết đầy đủ các tầng giao thức, các đối tượng mạng phân cấp phức tạp và hành vi gói tin rất sát thực tế. Với mạng ngẫu nhiên, để thu được kết quả chính xác cần phải tiến hành mô phỏng nhiều lần trên nhiều mẫu tô-pô khác nhau để lấy giá trị trung bình. Khối lượng tính toán và lượng thông tin lưu trữ đồ sộ của các công cụ này dẫn đến tình trạng cạn kiệt bộ nhớ và thời gian thực thi kéo dài quá mức khi số nút mạng đạt tới hàng nghìn hoặc hàng chục nghìn nút.

4. Mô hình tô-pô lai Bus-RSN đem lại lợi ích kinh tế và kỹ thuật cụ thể nào cho các trung tâm dữ liệu cỡ vừa và nhỏ?

Bus-RSN kết hợp đường trục Bus giữa các vùng máy chủ riêng biệt (các phòng hoặc các sàn khác nhau) với cấu trúc mạng ngẫu nhiên RSN bên trong mỗi vùng. Giải pháp này cho phép sử dụng các thiết bị chuyển mạch bậc đỉnh thấp, tiết kiệm chi phí phần cứng và dây cáp. Kết quả thực nghiệm trên kịch bản 2 sàn lắp đặt cho thấy Bus-RSN tiết kiệm tới 26% tổng chi phí thiết bị và cáp kết nối so với mô hình JellyFish, trong khi độ trễ truyền tin chỉ kém hơn 12%, giải quyết tốt bài toán không gian phân tán và kinh phí đầu tư ban đầu hạn hẹp.

5. Trong kịch bản định tuyến rút gọn dựa trên nút đại diện, kích thước bảng định tuyến tại mỗi nút thường được cấu thành từ những thành phần nào?

Trong kịch bản định tuyến rút gọn dựa trên nút đại diện (như của Cowen và Thorup - Zwick), tập nút mạng được chia thành nút thường và tập nút đại diện $L$. Mỗi nút thường $u$ chỉ cần lưu trữ thông tin đường đi ngắn nhất tới các nút thường khác nằm trong cụm của nó $C(u)$ (những nút gần $u$ hơn so với bất kỳ nút đại diện nào) và toàn bộ thông tin đường đi tới các nút đại diện trong tập $L$. Do đó, kích thước bảng định tuyến tại nút $u$ được tính bằng tổng $|C(u)| \cup |L|$, nhỏ hơn rất nhiều so với việc lưu trữ toàn bộ $n$ nút của mạng.

Kết luận

Luận án tiến sĩ của tác giả Kiều Thành Chung đã giải quyết thành công hai bài toán cốt lõi trong lĩnh vực mạng liên kết hiệu năng cao: thiết kế các giải pháp định tuyến rút gọn (CORRA, GLCR) giúp giảm kích thước bảng định tuyến mà vẫn duy trì độ dài đường truyền gần tối ưu trên mạng ngẫu nhiên quy mô lớn, và xây dựng bộ công cụ mô phỏng SSiNET hỗ trợ phân tích hiệu năng mạng kích thước lớn bằng phương pháp xấp xỉ và mô phỏng sự kiện rời rạc. Bên cạnh các đóng góp học thuật về mặt thuật toán và lý thuyết định tuyến, công trình còn đề xuất kiến trúc tô-pô lai Bus-RSN có giá trị ứng dụng thực tiễn cao đối với bài toán xây dựng trung tâm dữ liệu cỡ vừa và nhỏ trong điều kiện mặt bằng và kinh phí hạn chế tại Việt Nam. Toàn bộ các đề xuất lý thuyết và mô hình kỹ thuật đều được kiểm chứng thực nghiệm chặt chẽ, đóng góp các công bố học thuật trên các chuyên san khoa học chuyên ngành.