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