CƠ SỞ LÝ THUYẾT
Tổng quan về mạng liên kết (Interconnection Network)
2.1.1 Khái niệm, ứng dụng của mạng liên kết
Mạng liên kết (Interconnection Network) là hệ thống có thể lập trình, cho phép vận chuyển dữ liệu giữa các thiết bị đầu cuối Hình 1 minh họa mạng liên kết ở mức cao, trong đó các thiết bị đầu cuối từ TB1 đến TB5 kết nối với mạng thông qua các kết nối hai chiều, cho phép truyền dữ liệu vào và ra Khi TB1 muốn trao đổi dữ liệu với TB5, nó sẽ gửi một gói tin chứa thông tin đến mạng liên kết, và gói tin này sẽ được chuyển tiếp đến TB5.
Tại một thời điểm, mạng liên kết trong Hình 1 có thể chuyển tiếp gói tin từ TB1 đến
TB5 có khả năng chuyển tiếp gói tin từ TB2, thể hiện tính linh hoạt và khả năng lập trình của mạng liên kết Các kết nối giữa các thiết bị đầu cuối được thiết lập và điều chỉnh theo thời gian, đáp ứng nhu cầu truyền tin trong mạng một cách hiệu quả.
Hình 1: Mô hình mức cao của mạng liên kết
Hiện nay, 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à hệ thống chuyển mạch thông tin Mạng liên kết được thiết kế để sử dụng ở nhiều mức độ khác nhau, đáp ứng nhu cầu đa dạng trong các hệ thống máy tính.
Mạng liên kết (Interconnection Network)
Có năm nhóm ứng dụng chính bao gồm tính toán hiệu năng cao, lưu trữ vào ra, và các hệ thống cluster/workgroup Mạng liên kết được phân loại thành bốn lĩnh vực ứng dụng chủ yếu, tùy thuộc vào số lượng thiết bị kết nối và khoảng cách giữa chúng.
- On-chip networks (OCNs) hay còn được nhắc tới với thuật ngữ network-on-chip
NoC (Network on Chip) được sử dụng để kết nối các đơn vị chức năng, thanh ghi, bộ lưu trữ trung gian và bộ vi xử lý trong các module đa chip Hiện nay, OCNs hỗ trợ kết nối giữa hàng chục thiết bị trong vi mạch, với khoảng cách tối đa chỉ vài centimet.
Mạng lưu trữ (SANs) là một loại mạng kết nối các bộ vi xử lý và bộ nhớ trong các hệ thống đa nhân và đa máy tính SANs cũng được sử dụng để kết nối các thành phần lưu trữ với các thiết bị xử lý trong môi trường máy chủ và trung tâm dữ liệu Số lượng thiết bị kết nối trong SANs có thể lên tới hàng nghìn, với khoảng cách phân bố lên đến vài trăm mét.
Mạng diện địa (LAN) là hệ thống kết nối các máy tính cá nhân trong một khu vực cụ thể, ví dụ như trong một cụm máy tính Ban đầu, mạng LAN có khả năng kết nối hàng trăm thiết bị, nhưng nhờ vào cầu nối (bridges), số lượng thiết bị kết nối có thể tăng lên đến vài nghìn Khoảng cách kết nối tối đa của mạng LAN có thể bao phủ một khu vực với đường kính từ vài kilomet đến vài chục kilomet.
Mạng diện rộng (WAN) kết nối các hệ thống máy tính phân tán trên toàn cầu, cho phép hàng triệu máy tính giao tiếp với nhau qua khoảng cách lớn.
Hình 2 minh họa mối quan hệ giữa các lĩnh vực ứng dụng của mạng liên kết với số lượng thiết bị kết nối và khoảng cách giữa chúng Trục hoành biểu thị số lượng thiết bị trong mạng, trong khi trục tung thể hiện khoảng cách giữa các thiết bị tính theo mét.
Hình 2: Các lĩnh vực ứng dụng của mạng liên kết
Trong quá trình thực hiện luận văn, tác giả tập trung nghiên cứu các vấn đề của mạng liên kết, đặc biệt là trong lĩnh vực SANs 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à trung tâm dữ liệu sẽ được trình bày chi tiết Bài viết sẽ cung cấp cơ sở lý thuyết cơ bản liên quan đến lĩnh vực nghiên cứu mà không mở rộng sang các lĩnh vực khác.
2.1.2 Các thành phần cơ bản trong mạng liên kết Để đáp ứng được các yêu cầu của từng lĩnh vực ứng dụng cụ thể (ví dụ như độ trễ truyền tin hay chi phí), mạng liên kết được xây dựng thông qua việc cân nhắc các ràng buộc kĩ thuật nhằm cài đặt ba yếu tố cấu hình mạng (topology), định tuyến (routing) và điều khiển luồng (flow control) Trong hầu hết các ứng dụng, thay vì các thiết bị đầu cuối được liên kết với nhau từng đôi một, mạng liên kết được cài đặt dưới dạng một nhóm các bộ chuyển tiếp trung gian (router) dùng chung kết nối thông qua các kênh truyền dùng chung Mẫu thiết kế các kết nối giữa các nút mạng (bao gồm thiết bị đầu cuối và các bộ chuyển tiếp) được gọi là cấu hình mạng – topology Trong nhiều trường hợp cụ thể, bộ chuyển tiếp còn gắn liền với thuật ngữ thiết bị chuyển mạch (switch) vì quá trình chuyển tiếp thông tin được thực hiện nhờ kĩ thuật chuyển mạch Khái niệm nút mạng cũng được hiểu trong phạm vi hẹp chỉ bao gồm các bộ chuyển tiếp hay bộ chuyển mạch do sự thay đổi các thiết bị đầu cuối không ảnh hưởng nhiều đến kết quả nghiên cứu
Gói tin được truyền giữa các thiết bị đầu cuối thông qua các kênh truyền dùng chung và bộ chuyển tiếp trung gian, có thể đi qua nhiều con đường khác nhau từ nguồn đến đích Định tuyến là quá trình lựa chọn con đường tối ưu để gói tin truyền đi, ưu tiên những con đường ngắn nhất trong khi vẫn đảm bảo cân bằng tài nguyên mạng Độ dài của đường đi ảnh hưởng trực tiếp đến độ trễ truyền tin, trong khi tải thể hiện khối lượng sử dụng của tài nguyên cụ thể trong mạng.
Điều khiển luồng là quá trình quản lý quyền truy cập của các gói tin vào tài nguyên cụ thể tại một thời điểm, nhằm đảm bảo chuyển tiếp với độ trễ thấp nhất Quá trình này diễn ra liên tục và đóng vai trò quan trọng trong việc ngăn chặn tình trạng quá tải hoặc không sử dụng tài nguyên, từ đó tối ưu hóa hiệu suất mạng.
Ngoài cấu hình mạng, định tuyến và điều khiển luồng, mẫu trao đổi thông tin (traffic pattern) là một yếu tố quan trọng trong nghiên cứu và đánh giá mạng liên kết Traffic pattern mô hình hóa sự phân phối của các gói tin trong mạng Trong một mạng với N nút, traffic ngẫu nhiên thể hiện gói tin được gửi từ nguồn s đến đích d một cách ngẫu nhiên, với xác suất λ sd = 1/N Trong khi đó, traffic hoán vị (permutation traffic) cho phép gói tin từ nguồn s được gửi đến một hoặc nhiều đích xác định thông qua hàm d = π(s) Bảng 1 trình bày các traffic pattern phổ biến được sử dụng trong nghiên cứu hiệu suất mạng.
Bảng 1: Bảng các traffic pattern trong mạng liên kết
Tổng quan về cấu hình mạng
Trong mạng liên kết, cấu hình mạng là cách sắp xếp các kênh truyền và nút mạng, bao gồm thiết bị đầu cuối và bộ chuyển tiếp trung gian Việc lựa chọn cấu hình mạng là rất quan trọng vì nó ảnh hưởng trực tiếp đến cài đặt chi tiết Mỗi cấu hình yêu cầu chọn bộ chuyển tiếp với thông số về số cổng kết nối và tốc độ truyền tin khác nhau Do đó, cấu hình mạng được xác định dựa trên chi phí và hiệu năng.
Có rất nhiều loại cấu hình 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ấu hình mạng cơ bản sau:
Bus là một kiến trúc mạng cho phép các nút kết nối qua một kênh truyền chung, mang lại sự đơn giản trong cài đặt và mở rộng Với việc tiêu tốn ít dây nối, bus trở thành lựa chọn kinh tế hơn so với các cấu hình mạng khác Tuy nhiên, việc điều khiển luồng dữ liệu là một yếu tố quan trọng cần xem xét, đặc biệt khi nhiều nút muốn truyền tin đồng thời Do đó, bus thích hợp cho các mạng nhỏ không yêu cầu tốc độ cao.
Cấu hình mạng dạng sao (Star) bao gồm một nút mạng trung tâm đóng vai trò cầu nối truyền dữ liệu Một ưu điểm nổi bật của mạng sao là khả năng mở rộng quy mô dễ dàng bằng cách tăng số lượng kết nối với nút trung tâm Tuy nhiên, nhược điểm chính của cấu hình này là sự phụ thuộc vào khả năng và cấu hình phần cứng của nút mạng trung tâm.
Hình 3: Các cấu hình mạng cơ bản
Mạng hình tròn, hay còn gọi là ring, là một cấu trúc mạng trong đó mỗi nút mạng kết nối trực tiếp với hai nút khác, tạo thành một vòng tròn khép kín Trong mạng ring, không có nút trung tâm, và tất cả các nút đều có quyền hạn như nhau Tuy nhiên, mạng này dễ gặp sự cố khi một nút xảy ra vấn đề, và việc thêm, bớt hoặc bảo trì nút mạng cũng có thể ảnh hưởng đến toàn bộ hoạt động của mạng.
Mesh là một mạng lưới liên kết, trong đó mỗi nút mạng đều có khả năng kết nối với các nút mạng khác Thường được hình dung dưới dạng lưới, mesh cho phép sự kết nối trực tiếp giữa từng nút Hình 3.d minh họa một mạng mesh, nơi mỗi nút kết nối trực tiếp với tất cả các nút mạng khác.
- Tree: Mạng hình cây là sự kết hợp của bus và star (Hình 3.e)
Mạng truyền thống thường sử dụng cấu hình mesh nhờ vào tính đơn giản và khả năng định tuyến dễ dàng Từ đó, các cấu hình mạng như k-ary n-dimensional mesh và k-ary n-dimensional torus đã được phát triển Ví dụ, mạng 4-ary 2-dimensional torus gồm 16 nút mạng được sắp xếp theo lưới 4x4, trong đó mỗi nút kết nối với 4 nút khác, tạo thành mạng có bậc 4 K-ary n-dimensional torus có đặc điểm là tính chất "có quy tắc", với số kết nối giữa các nút mạng đồng đều, đảm bảo bậc không đổi cho mọi đỉnh.
Hình 4: Mạng liên kết 2D-Torus gồm 4x4 nút mạng
Tổng quan về giải thuật định tuyến trên mạng
Định tuyến là quá trình lựa chọn con đường để gói tin truyền từ nguồn đến đích trong mạng liên kết Thuật toán định tuyến đóng vai trò quan trọng trong việc cân bằng tải, giúp giảm thiểu tranh chấp tài nguyên và tắc nghẽn Một thuật toán định tuyến hiệu quả cho phép gói tin di chuyển theo con đường ngắn nhất, từ đó giảm độ trễ truyền tin Hơn nữa, thuật toán này còn có khả năng chịu lỗi, tự động loại bỏ các liên kết bị lỗi và tìm kiếm các đường đi thay thế để đảm bảo hoạt động liên tục của mạng.
Có nhiều cách phân loại thuật toán định routing, trong đó unicast routing là thuật toán gửi gói tin từ một nút nguồn đến một đích duy nhất Ngược lại, multicast routing là thuật toán cho phép gửi gói tin đến hai hoặc nhiều đích trong mạng.
Thuật toán định tuyến có thể được phân loại theo vị trí quyết định định tuyến, bao gồm ba phương pháp chính: định tuyến tại nguồn (source routing), định tuyến tập trung (centralized routing) và định tuyến phân tán (distributed routing) Trong định tuyến tại nguồn, con đường truyền tin được xác định ngay tại điểm khởi đầu Định tuyến tập trung sử dụng một bộ điều khiển để quyết định lộ trình, trong khi định tuyến phân tán cho phép các nút mạng tự quyết định lộ trình trong quá trình truyền tin.
Thuật toán định tuyến có nhiều phương pháp triển khai khác nhau, trong đó hai cách phổ biến nhất là sử dụng bảng định tuyến và máy trạng thái hữu hạn Các thuật toán này có thể thuộc loại định hướng (deterministic) hoặc thích ứng (adaptive) Định hướng là khi đường đi giữa nút nguồn và nút đích được xác định trước và không thay đổi, trong khi thích ứng dựa vào trạng thái của mạng để chọn con đường tối ưu tại mỗi lần định tuyến, bao gồm thông tin về các nút và liên kết trong mạng cũng như tình trạng hoạt động của chúng.
Trong quá trình định tuyến, nếu tất cả các con đường được chọn đều là ngắn nhất, được gọi là minimal routing, ngược lại là non-minimal Hình 5 minh họa thuật toán định tuyến trên mạng liên kết 4-ary 2-dimensional torus, trong đó Hình 5a thể hiện minimal routing với con đường ngắn nhất từ nút mạng 01 đến nút mạng 22, còn Hình 5b là non-minimal Khi các con đường định tuyến được xác định tại nút mạng 01 từ đầu, đó là source routing Nếu con đường từ 01 đến 22 luôn không đổi trong quá trình định tuyến, thuật toán này được gọi là deterministic routing Cả source routing và deterministic routing thường được triển khai thông qua bảng định tuyến (table lookup routing).
Hình 5: Ví dụ về định tuyến trên mạng kết 2D-Torus
Tổng quan về điều khiển luồng
Điều khiển luồng là quá trình quản lý phân phối tài nguyên mạng như kết nối và bộ đệm cho các gói tin trong quá trình truyền Một hệ thống điều khiển luồng hiệu quả giúp tối ưu hóa việc sử dụng tài nguyên, đảm bảo truyền tin với độ trễ thấp và ổn định.
Khi hai gói tin đến từ hai cổng khác nhau tại một bộ chuyến tiếp cùng lúc, giải thuật định tuyến yêu cầu chúng phải được chuyển tiếp đến cùng một cổng ra Để giải quyết xung đột về tài nguyên, cơ chế điều khiển luồng được áp dụng Một phương pháp đơn giản là chọn ngẫu nhiên một gói tin để chuyển tiếp và loại bỏ gói tin còn lại, gói tin này sẽ được gửi lại sau Đây là cơ chế điều khiển luồng đơn giản nhất khi không lưu trữ gói tin tại các bộ chuyên tiếp.
Chuyển mạch (circuit switching) là một cơ chế điều khiển luồng phức tạp và hiệu quả, trong đó nút nguồn gửi gói tin thăm dò đến nút đích để đăng ký sử dụng tài nguyên tại các nút mạng Gói tin thăm dò chỉ chứa thông tin cơ bản mà không có dữ liệu, và khi nút đích nhận gói tin này, nó sẽ phản hồi bằng gói tin xác nhận (ACK) Sau khi nhận được ACK, nút nguồn bắt đầu truyền dữ liệu theo con đường đã được thiết lập Tài nguyên sẽ chỉ được giải phóng khi toàn bộ dữ liệu đã đến nút đích Nếu một gói tin thăm dò không được cấp phát tài nguyên ngay lập tức, nó sẽ được lưu trữ trong hàng đợi cho đến khi tài nguyên được giải phóng Tuy nhiên, với cơ chế này, độ trễ truyền tin có thể lớn khi gói tin phải chờ tài nguyên tại các nút mạng bị tắc nghẽn.
Do đó, một phương pháp điều khiển luồng khác hiệu quả hơn được để ra gọi là
Chuyển mạch gói (packet switching) là phương pháp chia dữ liệu thành các thành phần nhỏ gọi là packet Mỗi packet có một vài bytes đầu chứa thông tin định tuyến và điều khiển, được gọi là packet header Trong trường hợp xảy ra tranh chấp tài nguyên, các packet sẽ được lưu trữ tại nút mạng và chờ đến khi tài nguyên được giải phóng, do đó phương pháp này còn được gọi là store-and-forward switching Cơ chế này cho phép các phần nhỏ của dữ liệu được truyền qua các đường khác nhau trong mạng, tối ưu hóa việc sử dụng tài nguyên rảnh rỗi Hơn nữa, thời gian chờ để giải phóng tài nguyên cũng ngắn hơn nhờ kích thước nhỏ của các packet so với dữ liệu cần truyền.
Trong quá trình chuyển mạch gói, định tuyến diễn ra khi toàn bộ packet được gửi đến và lưu trữ tại nút trung gian Tuy nhiên, packet header thường được truyền đến nút mạng trước khi toàn bộ dữ liệu được gửi Để giảm độ trễ và thời gian sử dụng tài nguyên của packet, quá trình định tuyến và chuyển tiếp packet header có thể diễn ra ngay khi tài nguyên rảnh rỗi, mà không cần chờ toàn bộ packet đến Phương pháp này được gọi là virtual cut-through switching Tuy nhiên, việc lưu trữ các packet lớn gây khó khăn cho việc chế tạo bộ chuyển tiếp nhỏ và rẻ, đồng thời tạo độ trễ trong quá trình truyền tin Để khắc phục, phương pháp Wormhole switching được đề xuất, trong đó packets được chia thành các đơn vị truyền tin (flits) Kích thước bộ đệm tại các cổng đủ lớn để chứa một vài flits, giúp giảm yêu cầu về kích thước bộ đệm trong bộ định tuyến Khi một packet phải chờ tài nguyên, nó sẽ bị chặn tại nhiều bộ chuyển tiếp thay vì một bộ chuyển tiếp duy nhất như trong virtual cut-through switching, cho phép các thành phần dữ liệu của packet được lưu trữ tại các nút mạng khác nhau.
Hình 6: Ví dụ về tắc nghẽn của Wormhole switching
Hiệu năng của mạng liên kết
Cấu hình mạng được lựa chọn dựa trên chi phí và hiệu năng, trong đó hai độ đo hiệu năng chính là thông lượng và độ trễ.
Thông lượng được định nghĩa là lượng thông tin tối đa có thể truyền trong một đơn vị thời gian trong mạng liên kết, thường được gọi là traffic Thông lượng thể hiện traffic tối đa mà mạng có thể chấp nhận và được đo bằng số gói tin trong một giây Trong nghiên cứu hiệu năng mạng, đơn vị thời gian có thể được tính bằng chu kỳ đồng hồ, do đó thông lượng cũng có thể được xác định bằng số gói tin trong một chu kỳ đồng hồ Thông lượng phụ thuộc vào kích thước gói tin và cấu trúc mạng, bao gồm số lượng nút mạng và khả năng xử lý dữ liệu Để tiêu chuẩn hóa, thông lượng được đánh giá bằng bits trên một nút mạng và micro-giây, hoặc bits trên một nút mạng và chu kỳ đồng hồ, từ đó xác định tốc độ truyền thông tin (bps) mà mạng hỗ trợ trên từng cổng vào.
Thông lượng là khái niệm trái ngược với giao thông yêu cầu (offered traffic), thể hiện tốc độ gói tin do nguồn phát sinh Khi lượng thông tin yêu cầu thấp, thông lượng và offered traffic có giá trị tương đương Tuy nhiên, khi yêu cầu truyền tin tăng lên, thông lượng sẽ đạt đến mức bão hòa, khiến mạng không thể đáp ứng truyền tất cả các gói tin với tốc độ ban đầu Điều này cho thấy cách đánh giá thông lượng của mạng dưới một yêu cầu truyền tin cụ thể.
Hình 7: Tương quan giữa throughput và offered traffic
Độ trễ là thời gian từ khi một gói tin được khởi tạo tại nút nguồn đến khi nó được nhận ở nút đích Đối với nghiên cứu kết nối và thiết bị mạng, độ trễ được xác định từ khi thành phần dữ liệu đầu tiên (message header) bắt đầu gửi vào mạng cho đến khi thành phần cuối cùng đến đích Trong một nút mạng, nhiều gói tin có thể được gửi và nhận đồng thời, dẫn đến việc tồn tại một hàng đợi chứa các gói tin đang chờ xử lý Nếu nghiên cứu tập trung vào hoạt động của hàng đợi, độ trễ cần được tính thêm thời gian chờ tại nút nguồn.
Nghiên cứu không chỉ tập trung vào tác động của mạng liên kết đến độ trễ mà còn xem xét các hoạt động tại bộ vi xử lý nguồn và đích trong việc gửi và nhận tin nhắn Các hoạt động này bao gồm chuẩn bị dữ liệu truyền đi, như xây dựng thông tin gói tin và kiểm tra lỗi, cũng như quá trình gửi và nhận gói tin vào và ra khỏi mạng Thông thường, những hoạt động này được thực hiện trong phần mềm gọi là messaging layer Đối với các nghiên cứu đánh giá tác động của messaging layer, độ trễ được định nghĩa là khoảng thời gian từ khi hệ thống khởi tạo lời gọi truyền tin tại nút nguồn đến khi hoàn thành lời gọi nhận tin tại nút đích.
Trong các hệ thống yêu cầu sự cộng tác giữa các nút mạng, độ trễ được đo từ khi một hoạt động được khởi tạo cho đến khi tất cả các nút hoàn thành nhiệm vụ Cụ thể, trong nghiên cứu về kết nối và thiết bị mạng, độ trễ của thao tác truyền tin đa điểm (multicast) được xác định từ thời điểm dữ liệu đầu tiên được gửi từ nút nguồn đến khi dữ liệu cuối cùng được nhận tại nút đích.
Trong quá trình thực hiện luận văn, người viết chú trọng đến các nghiên cứu về kết nối và thiết bị mạng, đồng thời bỏ qua các yếu tố liên quan đến hàng đợi và lớp messaging Độ trễ được mô hình hóa thành ba thành phần chính: độ trễ tiêm (injection time), thời gian truyền (time to fly) và độ trễ của bộ chuyển mạch (switches latency) Độ trễ tiêm, còn được gọi là độ trễ serialization, là thời gian mà gói tin được chuyển qua mạng, tính bằng kích thước gói tin chia cho băng thông của đường truyền Thời gian truyền phụ thuộc vào độ dài của đường truyền mạng và có các đơn vị khác nhau cho các ứng dụng WANs, LANs, SANs và OCNs Cuối cùng, độ trễ của bộ chuyển mạch là thời gian cần thiết để gói tin được xử lý tại các bộ chuyển mạch trên đường truyền, và giá trị trung bình của nó được tính bằng tích của giá trị trung bình của các đường đi và thời gian trễ tại một bộ chuyển mạch bất kỳ.
Công thức tính độ trễ áp dụng khi không có tranh chấp về tài nguyên trong quá trình truyền tin Nếu có tranh chấp, cần cộng thêm thời gian chờ của các gói tin trong hàng đợi vào độ trễ.
Hình 8: Tương quan giữa latency và offered traffic
Biểu đồ độ trễ theo lượng thông tin yêu cầu truyền đi (offered traffic) cho thấy mối liên hệ giữa độ trễ và giá trị offered traffic Khi offered traffic thấp, không có sự tranh chấp tài nguyên, độ trễ duy trì theo công thức đã nêu Tuy nhiên, khi offered traffic tăng, độ trễ cũng tăng đáng kể Offered traffic sẽ đạt đến mức bão hòa khi độ trễ trở nên rất cao Hình 8 [7] minh họa rõ ràng tương quan này giữa độ trễ và offered traffic.
PHƯƠNG PHÁP ĐÁNH GIÁ VÀ CÔNG CỤ MÔ PHỎNG MẠNG LIÊN KẾT
Đánh giá chi phí
Trong nghiên cứu về tính toán hiệu năng cao và trung tâm máy tính, tác giả tập trung vào việc đánh giá chi phí mạng liên kết trong hai giai đoạn: cài đặt và vận hành hệ thống Chi phí cài đặt mạng liên kết bao gồm các khoản chi cho việc mua sắm thiết bị, dây nối và lắp đặt Bên cạnh đó, tác giả cũng chú ý đến việc tiêu tốn tài nguyên điện năng trong quá trình vận hành hệ thống.
3.1.1 Chi phí thiết lập mạng
Chi phí đầu tư cho thiết bị mạng chiếm tỷ lệ lớn trong tổng chi phí cài đặt mạng liên kết Mô hình hóa mạng liên kết tổng quát có thể hiểu là mạng kết nối các thiết bị chuyển mạch Để đơn giản hóa việc tính toán chi phí, chúng tôi đã chọn mức chi phí 500$ cho mỗi cổng chuyển mạch, dựa trên khảo sát trong tài liệu [11] Mỗi cổng này tương ứng với một liên kết của nút mạng trong cấu trúc mạng liên kết.
Chi phí cài đặt mạng bao gồm cả chi phí cho cáp mạng dùng để kết nối các thiết bị Khi xây dựng hệ thống cáp mạng cho hiệu năng cao, có nhiều giải pháp khác nhau, mỗi giải pháp tương ứng với mức chi phí cụ thể cho cáp và đầu kết nối tại các thiết bị.
Hiện nay, hai giải pháp phổ biến cho kết nối mạng là cáp đồng và cáp quang Cáp đồng có chi phí thấp hơn cáp quang, chủ yếu do giá thành đầu kết nối rẻ hơn, chỉ bằng khoảng 1/10 so với cáp quang Tuy nhiên, cáp đồng không đảm bảo chất lượng đường truyền khi kết nối các thiết bị ở khoảng cách lớn hơn 5m Vì vậy, giải pháp lý tưởng trong thực tế là kết hợp sử dụng cả cáp đồng và cáp quang.
Chi phí Loại cáp mạng
Chi phí trên 1m dây (Cost_per_m)
Chi phí đầu kết nối (Connector_Cost)
Bảng 2: So sánh chi phí cáp đồng và cáp quang
Trong nghiên cứu này, chúng tôi áp dụng mô hình từ tài liệu [11] để tính toán chi phí một cách tổng quát Cụ thể, chi phí cho cáp mạng được xác định theo công thức trong Bảng 3 Chi phí cho mỗi kết nối bao gồm giá trị dây nối (bao gồm chi phí dây nối và chi phí đầu kết nối) cộng thêm 25% chi phí trung bình của nhà sản xuất, bao gồm chi phí sản xuất, phân phối và lợi nhuận, cùng với chi phí lắp đặt thực tế.
Cable_cost = (Cable_length * Cost_per_m + Connector_Cost) * 1.25 + Installation _ Cost
Bảng 3 trình bày cổng tính chi phí cáp mạng theo độ dài, đặc biệt cho các mạng liên kết ứng dụng trong tính toán hiệu năng cao và trung tâm dữ liệu lớn Các thiết bị chuyển mạch thường được đặt trong các tủ mạng, và chi phí của tủ mạng được bỏ qua vì nó không thay đổi giữa các cách sắp xếp bộ chuyển mạch Tuy nhiên, tủ mạng vẫn ảnh hưởng đến chi phí lắp đặt thực tế Cụ thể, chi phí trung bình để cài đặt kết nối giữa hai nút mạng trong cùng một tủ mạng là 2.5$, trong khi chi phí kết nối giữa hai nút mạng ở hai tủ khác nhau là 6.5$.
Khi nối hai nút mạng cách nhau 10m ở hai tủ mạng khác nhau, việc sử dụng dây cáp quang là cần thiết để đảm bảo chất lượng đường truyền Với chi phí 5$/m cho cáp và 188$/1 connector, tổng chi phí cho kết nối này được tính toán như sau: (10*5 + 188*2) * 1.25 + 6.5, dẫn đến tổng chi phí là 539$.
Khi đánh giá lý thuyết chi phí cho một mạng liên kết, việc xác định mô hình tính toán độ dài dây cáp là rất quan trọng Mạng trung tâm dữ liệu thường được lắp đặt trong phòng máy lớn với các hệ thống làm mát, điện và dây mạng chuyên dụng Các tủ mạng được sắp xếp theo dạng lưới AxB, trong đó A là số hàng và B là số tủ mạng trong mỗi hàng Mỗi tủ mạng chứa nhiều thiết bị chuyển mạch xếp theo chiều thẳng đứng Các tủ mạng trên cùng một hàng được đặt cách nhau một khoảng cố định để tạo không gian cho luồng khí nóng và lạnh, trong khi giữa các hàng cũng có khoảng cách để đảm bảo hiệu quả làm mát.
Hình 9: Minh họa mô hình phòng mạng
Trong nghiên cứu này, chúng tôi áp dụng mô hình trình bày từ tài liệu [12] để mô phỏng một phòng máy với diện tích không giới hạn, nhằm nghiên cứu các mạng liên kết có kích thước đa dạng Các tủ mạng được bố trí trong một lưới AxB, mỗi tủ chứa cùng một số lượng thiết bị chuyển mạch.
Trong đó A = ⌈√ ⌉ và B = ⌈ ⌉ với m là số lượng tủ mạng
Dây nối giữa hai nút mạng ở hai tủ mạng khác nhau được xác định theo khoảng cách Mahatan, tính bằng tổng khoảng cách theo trục X và Y Khoảng cách giữa hai bộ chuyển mạch theo trục X, bao gồm chiều rộng tủ mạng và lối đi, là 0.6m Độ dài dây nối giữa hai bộ chuyển mạch theo trục Y phụ thuộc vào chiều sâu tủ mạng và lối đi hàng.
2.1m Vậy độ dài này được tính bằng công thức 0.6*∆X + 2.1*∆Y (m) (còn được gọi là inter-cabinets cable) Bên cạnh đó, độ dài dây cáp giữa hai bộ chuyển mạch trong cùng một tủ mạng (còn gọi là intra-cabinets cable) được lấy giá trị trung bình 2m/1 dây cáp Ngoài ra, với mỗi một dây cáp mạng được tính thêm một khoảng dôi ra (overhead) trung bình là 2m [13]
Hình 10: Minh họa tính độ dài dây mạng
Hình 10 minh họa độ dài dây mạng giữa hai hàng liên tiếp của tủ mạng, trong đó độ dài dây nối giữa nút A và nút C được tính theo khoảng cách Manhattan, cụ thể là d AC = d AB + d BC = (0.6*1 + overhead) + (2.1*1 + overhead) = 4.7 (m) Ngoài ra, độ dài dây nối giữa các nút D và E, cũng như giữa D và F, đều bằng 2(m) vì nằm trong cùng một tủ mạng.
3.1.2 Mức tiêu thụ năng lƣợng họat động Độ dài dây cáp và cách bố trí thiết bị mạng trong phòng mạng (layout) có ảnh hưởng lớn đến chi phí cài đặt ban đầu mạng liên kết Không chỉ vậy, độ dài dây cáp cũng ảnh hưởng tới chi phí khi vận hành mạng Chúng tôi đánh giá chi phí này dựa trên tiêu thụ điện năng (power consumtion) trên một cổng (switch port) và tiêu thụ năng lượng (energy consumtion) khi truyền một gói tin
< 0.7m >=0.7 m Điện năng tiêu thụ trên một cổng (nW) 6600 12400
Năng lượng tiêu thụ khi truyền 1 gói tin (pJ) 2 60
Bảng 4: Tiêu thụ năng lượng trên cáp mạng
Khảo sát các bộ chuyển mạch phổ biến hiện nay cho thấy chi phí phụ thuộc vào độ dài dây cáp Chúng tôi đánh giá tiêu thụ năng lượng toàn mạng khi thiết kế và hoạt động, bao gồm năng lượng tiêu thụ của các bộ chuyển mạch và năng lượng hoạt động theo thời gian Hình 11 minh họa cách tính năng lượng tiêu thụ của mạng liên kết qua giả code, trong đó việc đánh giá năng lượng tiêu tốn cho quá trình truyền tin phụ thuộc vào kịch bản giả lập trao đổi thông tin được định nghĩa trong traffic.
#Total power and energy of network total_power = 0 # total power consumption total_energy = 0 # total energy consumption for each (i,j,w) in cables {
# i, j is two nodes of cable
# w is cable total_power =+ power_of(length_of(cable)) total_energy =+ traffic[i, j] * energy_of(length_of(cable))
# Power consumption per switch port power_of(len){ if(len p − log p Đường kính của mạng đạt giá trị lớn nhất là 2.5p + r, trong đó r = n mod p, và đường kính định tuyến không vượt quá 3p + r Khi chọn ngẫu nhiên cặp nguồn s và t từ n nút mạng, giá trị trung bình của đường đi theo thuật toán định tuyến là ≤ 2p, trong khi giá trị đường đi nhỏ nhất là ≤ 1.5p Độ dài trung bình của các shortcuts trong mạng DSN là ≤ n/p, dẫn đến tổng độ dài cáp mạng ≤ n²/p + 2n So với mạng DLN-2-2, có bậc trung bình tương đương, độ dài trung bình của shortcut là n/3, cho thấy tổng độ dài cáp mạng của DSN nhỏ hơn DLN-2-2 khoảng p/3.
4.1.3.2 Đường kính và giá trị trung bình của đường đi ngắn nhất
Chúng tôi tiến hành so sánh đường kính và giá trị trung bình của đường đi ngắn nhất (average shortest path length) của mạng liên kết DSN với các mạng liên kết có cùng số đỉnh và số cạnh Cụ thể, chúng tôi lựa chọn mạng 2D-Torus không sử dụng tính ngẫu nhiên và mạng DLN-2-2 sử dụng tính chất ngẫu nhiên Các mạng liên kết được đặt tên lần lượt là DSN, TORUS và RANDOM (cho DLN-2-2).
Hình 18: Đường kính và trung bình đường đi ngăn nhất vs kích thước mạng DSN
DSN-α và giải thuật định tuyến hiệu quả
DSN được thiết kế nhằm tối ưu chi phí cài đặt mạng liên kết bằng cách giảm thiểu tổng chiều dài cáp mạng Dựa trên phương pháp luận trong thiết kế và thử nghiệm, chúng tôi phát triển mạng liên kết sử dụng hiệu ứng thế giới nhỏ để tạo ra cơ chế định tuyến hiệu quả và ổn định với độ trễ thấp Chúng tôi đề xuất một biến thể mở rộng gọi là DSN-α, với giải thuật định tuyến mới, được trình bày chi tiết trong [20] Trong phần này, người viết sẽ tóm tắt thiết kế và kết quả đạt được, đồng thời nhấn mạnh những đóng góp của mình trong quá trình thực hiện đồ án.
Phương pháp xây dựng mạng liên kết DSN-α bao gồm các bước trong DSN, với N nút mạng được sắp xếp theo hình tròn Các nút mạng được đánh số ID từ 0 đến n-1, trong đó mỗi nút i liên kết với hai nút hàng xóm (i-1) mod n và (i+1) mod n, được gọi là Pred và Succ Mỗi nút cũng được gán nhãn từ 1 đến p = ⌈ ⌉, xác định level của nút đó Level l được gán cho các nút có ID k x p + l -1 với k thuộc {0, 1, 2,…, ⌊ ⌋} Đặc biệt, các nút có level l ≤ p − ⌊log p⌋ sẽ có một liên kết dài Shortcut tới nút j có level l+1, với khoảng cách tới nút i ít nhất bằng ⌊ ⌋ Shortcut này được gọi là level-l shortcut, với độ dài ngắn nhất là n/2^l.
Chúng tôi đã bổ sung một số liên kết mới với các mục đích cụ thể trong mạng Đầu tiên, các liên kết Up links được thiết lập cho mỗi nút mạng có level l > 1, kết nối đến nút gần nhất có level l-1 theo chiều kim đồng hồ Thứ hai, Walk links được thêm vào giữa các nút mạng liên tiếp, với q = ⌊log p⌋ và x = ⌈p/q⌉, tạo ra q liên kết giữa các nút kp−1+ix và kp−1+(i+1)x Cuối cùng, Cycle Breaking links (CBL) được thiết lập cho mọi nút mạng trong khoảng từ 1 đến 2p, kết nối đến nút gần nhất theo chiều ngược chiều kim đồng hồ nhằm mục đích giảm tắc nghẽn trong mạng.
Chúng tôi sử dụng các thuật ngữ như Up, Walk và Shortcut để mô tả các kết nối theo chiều kim đồng hồ Các thuật ngữ c-Up, c-Walk và c-Shortcut được áp dụng cho các trường hợp khác Hình 21 minh họa tập liên kết của một nút mạng điển hình.
Hình 21: Minh họa các liên kết của một nút mạng trong DSN- α
4.2.2 Giải thuật định tuyến hiệu quả
Giải thuật định tuyến ba bước của DSN-α được mô tả trong Bảng 8 và Bảng 9
1: procedure DSN-ROUTING(s,t) 2: u ← s, l u − level of u
3: Call the PRE-WORK Procedure 4: if u is not too close to destination t then 5: Call the MAIN-PROCESS Procedure 6: end if
Bảng 8: Giải thuật định tuyến trên mạng liên kết DSN α
The new PRE-WORK Phase
3: if t in next super-node and l u > 1 then
5: jump to FINISH when overshooting
7: l ← ⌊log (n/d ut )⌋+ 1 ›› i.e n/2 l ≤ d ut ≤ n/2 l-1 8: while l u > l do
The new MAIN-PROCESS phases
Bảng 9:Chi tiết ba bước giải thuật định tuyến trên mạng liên kết DSN- α
Trong bước PRE_WORK, gói tin từ nút mạng t sẽ di chuyển qua các uplink để tới nút mạng chứa shortcut phù hợp, đảm bảo quá trình truyền tải diễn ra hiệu quả.
Dòng 3 đến dòng 5 mô tả trường hợp đặc biệt khi nút đích gần nút hiện tại (super-node tiếp theo theo chiều kim đồng hồ) Trong tình huống này, gói tin sẽ được chuyển tiếp đến super-node qua Up link Sau đó, quá trình định tuyến sẽ tiếp tục với bước MAIN_PROCESS hoặc kết thúc nếu đã nhảy qua nút đích.
Bước MAIN_PROCESS lặp lại việc di chuyển qua các Shortcut, giúp đi được quãng đường dài hơn nửa quãng đường từ nút hiện tại đến nút đích Trong quá trình di chuyển tới nút chứa Shortcut trong mỗi super-node, chúng tôi áp dụng phương pháp Succ như trong DSN hoặc sử dụng Walk để giảm số bước nhảy MAIN_PROCESS sẽ dừng lại khi gói tin truyền vượt qua nút đích trên mạng hình tròn theo chiều kim đồng hồ Tương tự, trong bước FINISH, c-Walk có thể được sử dụng để tăng tốc độ nhảy quay lui đến đích t.
Chúng tôi đề xuất một biến thể cho bước PRE-WORK, trong đó áp dụng BACKWARD-MODE khi nút hiện tại gần nút đích theo hướng ngược chiều kim đồng hồ, với nút đích nằm ở super-node ngay phía trước Ngược lại, FORWARD-MODE được sử dụng khi nút hiện tại gần nút đích theo chiều kim đồng hồ Bảng 10 mô tả chi tiết bước PRE-WORK sử dụng BACKWARD-MODE.
The PRE-WORK phase with BACKWARD-MODE
1: procedure PRE-WORK-BW 2: u ← s, l u − level of u
3: if d ut ≤ n/2 or l u = 1 or > p − q then
4: if t in next super-node and l u > 1 then
5: u ← u.Up 6: jump to FINISH when overshooting 7: else
10: u ← u.Up 11: l ← ⌊log (n/d ut )⌋+ 1 12: end while
13: end if 14: else ›› BACKWARD-MODE ————
15: if t in previous super-node and l u < p then
16: u ← u.c − Up 17: jump to FINISH when not overshooting 18: else if d ut ≤ p then
21: repeat 22: u ← u.c− Shortcut 23: until overshooting t 24: end if
Bảng 10: Giải thuật định tuyến trên mạng DSN- α sử dụng BACKWARD-MODE
Những điều chỉnh trong cấu hình mạng liên kết và thuật toán định tuyến nhằm xây dựng một giải pháp định tuyến với độ trễ thấp và cân bằng tải hiệu quả Cơ chế định tuyến này có khả năng mở rộng, giúp nâng cao khả năng chịu lỗi của hệ thống.
4.2.3 Các kết quả đạt đƣợc
4.2.3.1 Đánh giá bằng lý thuyết
Kích thước của super-node không đầy đủ được xác định là r = n mod p, với chỉ một super-node không đầy đủ nếu n không chia hết cho p Độ dài của các Walk Links được biểu diễn bằng w = ⌈ ⌉ Các nghiên cứu đã chỉ ra rằng hầu hết các nút mạng có bậc là 6, với giá trị lớn nhất không vượt quá 11, và có tối đa 2logp nút mạng có khả năng có bậc lớn nhất Phương pháp định tuyến đề xuất, có hoặc không có BACKWARD-MODE, cho thấy độ dài đường đi lớn nhất không vượt quá 2p + 2q + 2w, trong khi giá trị lớn nhất của đường đi nhỏ nhất không vượt quá p + 2.5q + 4w.
Trong nghiên cứu về mạng liên kết DSN-α-x với x > p-logp, chúng tôi đã chỉ ra rằng độ dài trung bình của đường đi dựa trên thuật toán định tuyến của chúng tôi cho hai cặp nguồn s và đích t bất kỳ là nhỏ hơn hoặc bằng 1.5p + 0.5q + w Độ dài trung bình của đường đi ngắn nhất nằm trong khoảng p và p + 0.5q + 2w, cho thấy rằng độ dài đường đi theo thuật toán định tuyến trên DSN-α gần gấp rưỡi so với đường đi ngắn nhất, trong khi với DSN, giá trị này là 1,7 lần Điều này chứng tỏ DSN-α vượt trội hơn DSN về mặt độ trễ Hơn nữa, băng thông của DSN-α xấp xỉ 2n/p + 2p, và việc sử dụng thuật toán định tuyến trong DSN-α không xảy ra tắc nghẽn, khẳng định sức mạnh và hiệu quả của thuật toán mà chúng tôi đề xuất.
4.2.3.2 Đường kính và độ dài cáp mạng
Chúng tôi đã so sánh mạng DSN-α với các mạng liên kết tương đương như 3D-Torus và DLN-6, tập trung vào số nút và số liên kết Bảng 11 cho thấy mối tương quan về đường kính mạng, trong khi Bảng 12 trình bày kết quả so sánh độ dài cáp mạng trung bình, với giá trị nhỏ hơn mang lại lợi ích về độ trễ và chi phí cài đặt Như mong đợi, DSN-α có đường kính nhỏ hơn 3D-Torus và luôn duy trì độ dài cáp mạng trung bình ngắn nhất Ngược lại, DLN-6 gặp khó khăn trong việc mở rộng quy mô do độ dài cáp mạng tăng nhanh khi kích thước mạng tăng.
Bảng 11: Bảng so sánh về đường kính mạng của 3D-Torus, DSN-α và DLN-6
Bảng 12: Bảng so sánh về độ dài cáp mạng của 3D-Torus, DSN-α và DLN-6
4.2.3.3 Đánh giá hiệu năng bằng phương pháp giả lập
Chúng tôi đã sử dụng phương pháp giả lập và các tham số tương tự như trong mục 4.1.3.4 để đánh giá hiệu năng của mạng liên kết với các giải thuật định tuyến khác nhau Mạng liên kết giả lập bao gồm 256 bộ chuyển mạch, mỗi bộ chuyển mạch có 4 nút tính toán Các giải thuật định tuyến được sử dụng bao gồm R27 và R28 cho DSN-α với chế độ BACKWARD-MODE và không có chế độ này, trong khi R23 đại diện cho giải thuật định tuyến của DSN Cuối cùng, Up*/down* là giải thuật định tuyến được trình bày trong tài liệu [21].
Hình 22 thể hiện sự thay đổi của thông lượng (accepted traffic) tính bằng Gbits/sec/host trong mạng khi áp dụng 4 giải thuật định tuyến Giải thuật Up*/Down* đạt thông lượng tối đa khoảng 2,3 Gbits/sec, nhưng nhanh chóng giảm khi requested traffic tăng cao Ngược lại, R27 (định tuyến sử dụng BACKWARD-MODE) không chỉ duy trì thông lượng lớn mà còn đảm bảo hiệu năng tốt trong điều kiện requested traffic nặng (heavy traffic).
(a) Uniform traffic (b)Bit reversal traffic
Hình 22: Đánh giá thông lượng của DSN-α
Độ trễ được đánh giá dựa trên lưu lượng yêu cầu, cho thấy cả 4 giải thuật định tuyến có độ trễ tương đương khi lưu lượng còn thấp Tuy nhiên, khi lưu lượng tăng, độ trễ của cả 4 giải thuật đều tăng nhanh chóng Đặc biệt, R27 thể hiện độ trễ thấp hơn khoảng 50% so với các giải thuật định tuyến khác.
(a) Uniform traffic (b)Bit reversal traffic
Hình 23: Đánh giá độ trễ của DSN-α
DSN-F và giải thuật định tuyến tích hợp với khả năng mở rộng
Tính co giãn và khả năng mở rộng quy mô là những yếu tố quan trọng bên cạnh hiệu năng như độ trễ truyền tin, cân bằng tải và khả năng chịu lỗi trong các mạng liên kết ứng dụng cho siêu máy tính và trung tâm dữ liệu Theo thời gian, nhu cầu nâng cao khả năng tính toán của các siêu máy tính trong TOP500 ngày càng cấp thiết Để giải quyết vấn đề này hiệu quả, cần nâng cao khả năng phần mềm và ứng dụng trên siêu máy tính, đồng thời xem xét khả năng bổ sung chip xử lý sau khi cài đặt ban đầu nhằm giảm chi phí Ngoài ra, các trung tâm dữ liệu cũng thường yêu cầu mở rộng hệ thống theo thời gian hoạt động.
Khi thêm một hoặc nhiều nút mạng vào một mạng liên kết đã được cài đặt, cần chú ý đến ba yếu tố quan trọng: tối thiểu hóa số lượng dây cáp mạng cần phải nối lại, giảm độ dài trung bình của cáp mạng trong mạng mới, và đảm bảo sự biến đổi hiệu năng của mạng liên kết.
Chúng tôi đề xuất một biến thể của mạng DSN gọi là DSN-F, được thiết kế để dễ dàng mở rộng quy mô mà vẫn giữ được các ưu điểm của DSN như bậc đỉnh nhỏ, đường kính logarit và tổng độ dài cáp mạng nhỏ Phương pháp mở rộng mà chúng tôi đưa ra cho phép thêm nút mạng vào mạng liên kết một cách tự nhiên và dễ dàng, giúp DSN-F có thể có kích thước tùy ý và khả năng mở rộng quy mô linh hoạt.
Thiết kế mới của chúng tôi được phát triển dựa trên một số nhận định quan trọng Đầu tiên, chúng tôi chú trọng đến vấn đề super-node không đầy đủ trong thiết kế nguyên bản của DSN-x Super-node I được xem là không đầy đủ nếu nó không đáp ứng các tiêu chí nhất định.
Gọi r = n mod p, super-node không đầy đủ là super-node cuối cùng bao gồm r nút mạng Sự tồn tại của super-node này ảnh hưởng đến quá trình định tuyến, làm tăng độ dài đường đi Theo thuật toán định tuyến của DSN, độ dài tối đa từ nguồn đến đích bất kỳ là 3p + r (chứng minh trong [3]) Giá trị này có thể được giảm nếu loại bỏ super-node không đầy đủ.
Để giải quyết vấn đề mở rộng quy mô, có thể thêm nút mạng giữa hai nút mạng chính, với nút mới gọi là nút mạng phụ Nút mạng phụ chỉ có liên kết cục bộ trong cùng supernode mà không có shortcut Phương pháp này hiệu quả khi thêm một số lượng nhỏ nút mạng, nhưng nếu số lượng lớn, nó có thể làm giảm hiệu ứng thế giới nhỏ, tăng độ dài đường đi và độ trễ truyền tin Do đó, việc mở rộng nên tạo ra mạng liên kết mới tương tự như mạng ban đầu Chúng tôi chuẩn hóa số lượng super-node và kích thước của nó trong mạng liên kết là 2^p super-node, tạo thành một mạng hình tròn với mỗi super-node bao gồm ít nhất p nút mạng.
Thiết kế mạng DLN-logn cho phép mạng DLN-x có đường kính logarit, với cấu trúc bao gồm các super-node Bên trong mỗi super-node, các nút mạng được sắp xếp thành các lớp tên là layer-{0,1,2…} Layer-0 chứa p nút mạng, mỗi nút đều có 1 shortcut, trong khi các layer-1, 2… chỉ có các liên kết cục bộ mà không có shortcut Cách thiết kế này giúp dễ dàng thêm nút mạng vào mạng liên kết bằng cách thêm vào một layer hiện có hoặc tạo layer mới, mà không cần phải cài đặt lại các shortcut.
Mạng liên kết DSN-F bao gồm n nút mạng, mỗi nút có một ID i từ 0 đến n-1, xác định thông qua ba số: Level l (1 ≤ l ≤ p), Layer k (0 ≤ k ≤ ⌈N/p⌉), và ID của supernode s (0 ≤ s ≤ 2^p - 1) Level của nút i được tính bằng công thức l = i mod (p+1), trong khi Layer được xác định dựa trên số lượng nút mạng tối đa trong một layer Các nút mạng được phân nhóm vào 2^p super-node, và nút i thuộc super-node s nếu i/p mod 2^p = s Bên trong mỗi super-node, các nút trong cùng một layer được sắp xếp thành vòng tròn, với mỗi nút có hai kết nối Local_Pred và Local_Succ đến các nút mạng liền kề Các nút ở layer lớn hơn 0 có một liên kết Layer_Link tới nút cùng level ở layer nhỏ hơn, trong khi các nút tại layer-0 kết nối qua Succ và Pred giống như trong DSN Đặc biệt, mỗi nút mạng có level l < p trong super-node s còn có một Shortcut đến nút j có level l+1 tại super-node cách s theo chiều kim đồng hồ với khoảng cách 2^p / 2^l, và chỉ các nút ở layer-0 mới có Shortcut.
Mạng liên kết DSN-F với 32 nút và 3 shortcuts có độ dài khác nhau được minh họa trong hình 25 Mạng này có cấu trúc hình tròn với 8 super-nodes, mỗi super-node gồm 2 layers Nút mạng từ 0 đến 23 nằm trong layer-0, trong khi các nút còn lại thuộc layer-1 Các shortcuts kết nối các nút trong layer-0, ví dụ, nút mạng số 0 tại super-node 0 có shortcut với nút mạng số 13 tại super-node 4 Khoảng cách giữa hai super-nodes được định nghĩa là ∆(s j , s i ) = s j - s i, trong đó ∆(0,4) = 4 – 0 = 4, thỏa mãn điều kiện 4 ≥ 2 p-l = 2 3-1 = 4.
Hình 25: Minh họa mạng liên kết DSN-F gồm 32 nút mạng
DSN-F có cấu hình mạng linh hoạt với kích thước tùy ý và khả năng mở rộng quy mô Số lượng các loại shortcut có độ dài khác nhau, ký hiệu là p, là một yếu tố quan trọng trong việc xây dựng DSN-F Đối với bất kỳ giá trị nào của số nút mạng n, luôn tồn tại một số nguyên p tương ứng, điều này cho thấy DSN-F có khả năng tùy chỉnh kích thước mạng một cách linh hoạt.
Quá trình thêm một nút mạng vào cấu hình mạng DSN-F với n nút, p levels và K layers được thực hiện bằng cách thêm nút mới vào layer-(K-1) nếu layer này có r = n mod N < p nút Nếu r = p, một layer mới gọi là layer-K sẽ được tạo ra và nút mới sẽ được thêm vào đó Nhờ vào cách dán nhãn miêu tả, cấu trúc bên trong các super-node được duy trì, đảm bảo rằng bậc trung bình của đỉnh không đổi và đường kính mạng chỉ tăng tối đa 1 đơn vị khi thêm layer mới Phương thức này cũng không yêu cầu cài đặt lại cáp mạng.
Khi số lượng nút mạng trong một mạng liên kết lớn tăng lên, chúng tôi đề xuất một phương pháp thực hiện với số lượng cáp mạng thay đổi chấp nhận được Ý tưởng chính là tiếp tục thêm nút mạng cho đến khi số lượng nút trong tất cả các super-nodes đạt ngưỡng 2p + 2 Khi đó, chúng tôi sẽ chia super-node lớn thành hai super-nodes nhỏ hơn, mỗi super-node chứa p + 1 nút, và thêm các shortcut để đảm bảo mỗi super-node có p + 1 shortcuts Mạng liên kết mới sau quá trình này vẫn duy trì các đặc tính của DSN-F, với tham số số lượng p chuyển thành p + 1 Chúng tôi khẳng định rằng DSN-F có khả năng mở rộng quy mô nhờ vào khả năng liên tục thêm các nút mạng mới thông qua quy trình này.
Hình 26: Minh họa phương thức chia super-node lớn thành hai super-nodes nhỏ
Hình 26 minh họa phương thức chia một super-node lớn với 2p+2 nút mạng phân bố trong 3 layers thành 2 super-nodes có kích thước p+1 nút mạng và 1 layer Sau khi phân chia, super-node S ban đầu được biến đổi thành hai super-node SA và SB, trong đó các nút còn lại được sắp xếp vào SB Tất cả các Layer-Link bị xóa bỏ, bao gồm p liên kết giữa layer-0 và layer-1 cùng với 2 liên kết giữa layer-1 và layer-2 Tại super-node SA, hầu hết các liên kết cục bộ không bị ảnh hưởng; một nút mạng mới được thêm vào giữa nút mạng 0 và p-1, đóng vai trò là nút mạng có level p+1 tại layer-0 Tương tự, trong super-node SB, một nút mạng 2p+1 được thêm vào Các shortcut cũ từ nút mạng 0 đến p-1 được giữ lại, trong khi một shortcut mới được thêm từ nút p-1 đến nút mạng tương ứng trong super-node (S+1)A Tại super-node SB, p shortcut được thêm vào các nút từ p đến 2p-1, kết nối đến các nút có level l+1 của super-node (S+2p+1-l)B, cùng với một Succ từ nút mạng 2p+1 của SB đến nút mạng level 1 của super-node (S+1)A.
Hình 26 minh họa phương thức phân chia super-node, trong đó các đường kẻ màu xanh biểu thị các liên kết mạng đã bị loại bỏ, các đường màu đỏ thể hiện các liên kết mới được thêm vào, và các đường màu đen thể hiện các liên kết vẫn được giữ lại.
4.3.2 Giải thuật định tuyến tích hợp khả năng mở rộng
Cấu trúc mạng liên kết DSN-F đã có những điều chỉnh nhỏ so với DSN, dẫn đến việc giải thuật định tuyến trên mạng DSN-F được cải tiến với khả năng mở rộng quy mô khác biệt so với giải thuật định tuyến ban đầu.
