Một tiếp cận thiết kế công cụ phần mềm đánh giá hiệu năng mạng liên kết kích thước lớn
Tóm tắt: Bài báo này giới thiệu một cách tiếp cận riêng biệt để thiết kế công cụ phần mềm chuyên dụng cho đánh giá
hiệu năng mạng liên kết kích thước lớn, nhờ đề xuất cơ chế mô phỏng giản lược nhưng vẫn đảm bảo đánh giá được
những đặc tính chính của các tô-pô và thuật toán định tuyến mới. Chúng tôi đề xuất kiến trúc tổng thể, trong đó cho
phép thực hiện thí nghiệm với các tô-pô được định nghĩa sẵn hoặc tự định nghĩa, với nhiều kịch bản hay cấu hình traffic
khác nhau,và hỗ trợ xây dựng tô-pô hiệu năng cao với các tính năng đánh giá cách triển khai cài đặt trên mặt sàn thực
tế cho trước. Với bản phần mềm công cụ đầu tiên xây dựng trên kiến trúc đề xuất này chúng tôi đã tiến hành một số
thực nghiệm với một số tô-pô mạng loại mới có kích thước hàng chục nghìn node trong khoảng thời gian ngắn khả quan,
nhanh hơn khá nhiều lần so với khi tiến hành trên các công cụ mô phỏng phổ quát quen thuộc như NS3, OMNET++.
Tóm tắt nội dung tài liệu: Một tiếp cận thiết kế công cụ phần mềm đánh giá hiệu năng mạng liên kết kích thước lớn
![Một tiếp cận thiết kế công cụ phần mềm đánh giá hiệu năng mạng liên kết kích thước lớn Một tiếp cận thiết kế công cụ phần mềm đánh giá hiệu năng mạng liên kết kích thước lớn](https://s1.tailieuvn.net/xb70nb5jd4llaq8g/thumb/2021/11/22/mot-tiep-can-thiet-ke-cong-cu-phan-mem-danh-gia-hieu-nang-ma_tHagZUBUSg.jpg)
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 Một tiếp cận thiết kế công cụ phần mềm đánh giá hiệu năng mạng liên kết kích thước lớn Bài báo mời Kiều Thành Chung1,2, Nguyễn Tiến Thành2, Nguyễn Khanh Văn2 1Trường Cao đẳng nghề Công nghệ cao Hà Nội 2Trường Đại học Bách khoa Hà Nội Tác giả liên hệ: Nguyễn Khanh Văn, vannk@soict.hust.edu.vn Ngày nhận bài: 28/08/2019, ngày sửa chữa: 03/09/2019, ngày duyệt đăng: 08/09/2019 Xem sớm trực tuyến: 08/09/2019, định danh DOI: 10.32913/mic-ict-research-vn.v2019.n1.889 Biên tập lĩnh vực điều phối phản biện và quyết định nhận đăng: PGS.TS. Nguyễn Linh Trung Tóm tắt: Bài báo này giới thiệu một cách tiếp cận riêng biệt để thiết kế công cụ phần mềm chuyên dụng cho đánh giá hiệu năng mạng liên kết kích thước lớn, nhờ đề xuất cơ chế mô phỏng giản lược nhưng vẫn đảm bảo đánh giá được những đặc tính chính của các tô-pô và thuật toán định tuyến mới. Chúng tôi đề xuất kiến trúc tổng thể, trong đó cho phép thực hiện thí nghiệm với các tô-pô được định nghĩa sẵn hoặc tự định nghĩa, với nhiều kịch bản hay cấu hình traffic khác nhau,và hỗ trợ xây dựng tô-pô hiệu năng cao với các tính năng đánh giá cách triển khai cài đặt trên mặt sàn thực tế cho trước. Với bản phần mềm công cụ đầu tiên xây dựng trên kiến trúc đề xuất này chúng tôi đã tiến hành một số thực nghiệm với một số tô-pô mạng loại mới có kích thước hàng chục nghìn node trong khoảng thời gian ngắn khả quan, nhanh hơn khá nhiều lần so với khi tiến hành trên các công cụ mô phỏng phổ quát quen thuộc như NS3, OMNET++. Từ khóa: Tô-pô mạng, hiệu năng mạng, mô phỏng mạng, mạng liên kết, công cụ mô phỏng. Title: An Approach to Designing Software Tool Specified for Evaluating Performance of Interconnection Topologies with Large Sizes Abstract: This paper introduces a special approach to designing a software tool that is specified for evaluating performance of interconnection topologies with large sizes. This is based on a proposed network simulation mechanism that is heavily reduced (much simplified from the popular network simulation standard) in order to do just enough for evaluating the performance factors related to topology and routing mechanism characteristics. We propose a general architecture for such a system that allows to experiment with pre-defined or newly defined topologies by using different experiment scripts with different traffic patterns, and also to support the designing of new high-performance topologies with features for evaluating deployment layouts. Using our initial version of this software tool we are able to perform some interesting experimental evaluation of a few modern topologies with sizes as large as tens of thousands in very encouragingly short periods of time, multiple times faster than performed in popular general simulators such as NS3 or OMNET++. Keywords: Network topology, network performance, network simulation, interconnection network, simulation software. I. GIỚI THIỆU VẤN ĐỀ NGHIÊN CỨU Nghiên cứu tô-pô1 của các mạng liên kết (MLK: Inter- connection Network) [1, 2] có vai trò quan trọng trong lĩnh vực tính toán song song và kiến trúc mạng máy tính. Một giải pháp tô-pô hiệu quả sẽ đóng góp quyết định vào hiệu năng của các mạng lưới tính toán lớn như các hệ máy tính hiệu năng cao (HPC: High-Performance Computer) [2] hay trung tâm dữ liệu hiện đại (TTDL: Data Center) đang ngày càng trở thành nhu cầu cấp nhiết nhằm phục vụ các dịch vụ tính toán lớn. Một thách thức hiện nay đối với giới chuyên môn là thiết kế các hệ thống MLK hiệu năng cao trong TTDL với kích 1Topology: Cấu trúc tổ chức hình học của mạng máy tính. thước lớn, có thể lên đến hàng trăm nghìn máy. Bản thân việc tổ chức thực nghiệm để đánh giá hiệu năng một tô-pô mạng (network topology) đề xuất mới đã là một vấn đề không tầm thường vì hầu hết các công cụ mô phỏng mạng phổ quát hiện nay chỉ đáp ứng cho kích thước mạng lên đến hàng ngàn nút. Với sự phát triển vũ bão của các ứng dụng và dịch vụ Internet, của công nghệ Dữ Liệu Lớn (Big Data), các trung tâm dữ liện hiện đại đang được quan tâm đầu tư nhiều, trong đó một yêu cầu đặc thù phục vụ cho xu hướng mới này là thiết kế MLK nhằm đảm bảo tốt tính mềm dẻo (flexibility) và khả năng mở rộng (scalability). Cụ thể là việc bổ sung thêm các nút (node) mạng, tăng/giảm kích thước mạng có thể thực hiện nhiều lần với qui mô đa dạng, nhưng vẫn phải đảm bảo hiệu năng mạng. 27 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 Với kích thước mạng càng ngày càng lớn, các vấn đề về tiết kiệm chi phí thiết bị và cáp, tiết kiệm năng lượng khi tải thấp, v.v. trở thành những chủ đề rất đáng quan tâm. Có thể thấy điều này trong hàng loạt nghiên cứu trong giai đoạn gần đây về thiết kế MLK trong TTDL HELIOS [3], BCUBE [4], DCELL [5], Scafida [6], MD- Cube [7], VL2 [8]. Vì vậy các dạng tô-pô truyền thống trở nên phần nào lạc hậu, giới nghiên cứu đang tích cực đề xuất những tiếp cận, những dạng kiến trúc tô-pô mới phù hợp hơn cho các yêu cầu hiện đại, như Smallworld Data- Center [9], JellyFish [10], Space Shuffle [11], FatTree [12], SKYWALK [13], Dragonfly [14]. Một trong những thách thức lớn của địa hạt nghiên cứu này cũng là vấn đề đã đề cập trên: làm sao tổ chức đánh giá qua thực nghiệm với một mô hình mạng kích thước lớn, có thể vượt xa các kích thước mạng truyền thống. Để đánh giá một tô-pô MLK, bên cạnh các phương pháp đánh giá dựa trên cài đặt các thuật toán chuyên dụng để tính toán các đặc trưng hiệu năng (xoay quanh phân tích đồ thị), thực nghiệm qua công cụ mô phỏng mạng được coi là yếu tố có tiếng nói quyết định. Tuy nhiên việc thực hiện cài đặt các mạng kích thước lớn đến hàng chục nghìn nút tính toán trên các công cụ mô phỏng mạng hay hệ phân tán phổ biến hiện nay như NS3 [15], OMNET++ [16], SIMGRID [17], được xem là bất khả thi. Thậm chí với cấu hình máy tính tân tiến hàng đầu, cài đặt mạng lên đến 1000 nút đã là khá khó khăn2. Khó khăn chủ yếu là do mỗi nút tính toán trong các công cụ mô phỏng mạng phổ quát này được thiết kế để mô phỏng đầy đủ các tầng giao thức như các kiến trúc phổ biến (mô hình OSI bảy tầng hay mô hình TCP/IP). Khối lượng xử lý lớn ở mỗi nút sẽ giới hạn kích thước tập hợp các đối tượng mạng có thể cài đặt trong hệ mô phỏng. Tuy nhiên chúng tôi nhận thấy rằng với mô hình MLK, các nhà nghiên cứu chỉ quan tâm tới các yếu tố hiệu năng xoay quanh việc thực hiện các nhiệm vụ tầng giao vận và ứng dụng khi tải lớn chứ không quan tâm thực sự tới các tầng thấp. Quan sát này mở ra một tiếp cận mới là có thể cải tiến lõi hệ phần mềm mô phỏng nhằm hướng tới mạng kích thước lớn hơn thông qua việc rút gọn giản lược các chức năng của các tầng dưới (tầng mạng trở xuống). Thậm chí các quá trình truyền tin có thể thay thế bằng các mô hình ngẫu nhiên tương ứng (mô phỏng lỗi đường truyền) để sinh độ trễ phù hợp. Việc giản lược các tầng dưới đương nhiên là không phù hợp cho mô phỏng một quá trình hoạt động đầy đủ của một hệ thống mạng trong thực tế, nhưng lại không thực sự ảnh hưởng tới việc so sánh đánh giá giữa các tô-pô mạng với nhau theo các tiêu chí hiệu năng cơ bản. 2Mỗi lần thực hiện một thực nghiệm theo một kịch bản mô phỏng cơ bản có thể là hàng giờ trong khi cần thực hiện hàng trăm thực nghiệm để so sánh đánh giá một số tô-pô mạng với nhiều chế độ hoạt động và khai thác. Trong bài báo này chúng tôi đề xuất một tiếp cận mới: thiết kế phần mềm đánh giá tô-pô MLK thông qua thực nghiệm có mô phỏng, trong đó tập trung giản lược hóa các tầng thấp (chủ yếu là địa bàn để xây dựng các thuật toán định tuyến mới khi cần) và tập trung vào tổ chức các thí nghiệm chuyên dụng cho MLK ở các tầng trên (giao vận và ứng dụng). Thông qua tiếp cận mới này, chúng ta có thể đánh giá một đề xuất mới bằng việc so sánh với các giải pháp đã có trên những cấu hình mạng kích thước lớn mà trước kia chưa thể thực hiện được. Bài báo này trình bày những nét chính của tiếp cận mới trên và đề xuất một kiến trúc cơ sở cho hệ công cụ phần mềm đánh giá tô-pô MLK theo hướng này. Dựa vào kiến trúc cơ sở này, chúng tôi xây dựng những mô-đun nền móng đầu tiên, cho phép thực hiện các đánh giá so sánh tô-pô trên các tiêu chí hiệu năng cơ bản liên quan đến thông số đồ thị và định tuyến. Các đóng góp cụ thể như sau: • Đề xuất thiết kế tổng thể công cụ đánh giá hiệu năng MLK, kết hợp tính toán theo mô hình và mô phỏng giản lược (SSiNET). Công cụ này cho phép người dùng tạo các tô-pô mạng mới, cài đặt với các tham số cho trước (kích thước lớn được hỗ trợ cơ chế tự động sinh theo mẫu) thử nghiệm với các thuật toán định tuyến có sẵn và cài mới. Từ đó đánh giá hiệu năng theo các tiêu chí cơ bản và nâng cao, hỗ trợ thiết kế mặt sàn (layout) cho trước và tính toán giá thành. • Thực hiện các mô-đun cơ bản cho phép tính toán các thông số đồ thị và định tuyến. • Tạo cơ chế cho việc cài đặt thuật toán định tuyến và cài đặt sẵn một số tô-pô đã biết (ví dụ: 2-D Torus [9], Fat-tree [12], Kleinberg Small-world [9]) và thuật toán định tuyến đã biết (ví dụ: Shortest Path Routing [1], Two-level Table [12], Compact Routing [18]). • Với bản phần mềm công cụ đầu tiên, tiến hành thực nghiệm để đánh giá so sánh một số tô-pô mới đang được quan tâm và thuật toán định tuyến tương ứng để đánh giá độ trễ truyền tin (latency). Nội dung chính được tổ chức như sau. Mục II trình bày các nghiên cứu liên quan. Mục III đề xuất thiết kế SSiNET. Mục IV nghiên cứu đánh giá thử nghiệm. II. CÁC NGHIÊN CỨU LIÊN QUAN Để nghiên cứu và thiết kế một MLK hiệu quả, các nhà nghiên cứu tập trung vào hai vấn đề chính: (i) thiết kế tô-pô mạng; (ii) xây dựng thuật toán định tuyến, để khai thác tối đa các tính chất đặc thù của tô-pô tương ứng. Các cách thực hiện có thể theo ba hình thức như sau: (i) chỉ xây dựng tô-pô và sử dụng các thuật toán định tuyến đã tồn tại; (ii) chỉ xây dựng thuật toán định tuyến cho các tô-pô đã biết; (iii) xây dựng mới cả tô-pô và thuật toán định tuyến tương ứng. 28 Tập 2019, Số 1, Tháng 9 1. Tô-pô và thuật toán định tuyến Một tô-pô mạng, tức cấu trúc hình học của mạng, được biểu diễn bằng đồ thị G = (V,E), mỗi thiết bị chuyển mạch (switch) hoặc máy tính toán (host) trong mạng máy tính thực tế được biểu diễn bởi một nút mạng (node) trong đồ thị G. Tập hợp các switch hoặc host trong mạng được biểu diễn bởi tập đỉnh V trong đồ thị G và tập hợp các liên kết (link) giữa các switch hoặc host được biểu diễn bằng tập cạnh E . Các tô-pô và thuật toán định tuyến (RA: Routing Algo- rithm) đã được nghiên cứu từ lâu, nhiều tô-pô trong số đó đã được triển khai áp dụng phổ biến trên thực tế. Ví dụ, tô- pô siêu khối cơ sở k, số chiều n (k-ary n-cube hypercube) định tuyến theo giao thức Duato [1] được sử dụng trong các siêu máy tính như là BlueGene/L Anton-2 hoặc Cray XT5 [19]. Gần đây, các tô-pô truyền thống được xem là không đáp ứng được các tiêu chí hiệu năng hiện đại như độ trễ truyền tin thấp và tính co giãn qui mô. Vì vậy như là một tiếp cận mới, thiết kế tô-pô mạng dựa trên mô hình đồ thị ngẫu nhiên [9] đã được quan tâm và đem lại nhiều cải tiến hiệu năng nổi bật. Tô-pô ngẫu nhiên (RSN: Random Shortcut Network), được cấu trúc dựa trên một tô-pô cơ bản như là Mesh, Torus, Hypercube, Flattened Buttery, v.v. và bổ sung thêm các liên kết dài giữa các nút ở xa nhau. Các liên kết dài được tạo ra bởi việc sử dụng một phân bố xác suất ngẫu nhiên nào đó. Các RSN đã được công bố như là Jellyfish [10], Small-world [9]. Một số tiêu chí cơ bản của hiệu năng mạng được đánh giá dựa trên việc tính toán các tham số chính như đường kính mạng (diameter), độ dài trung bình đường định tuyến (ARPL: Average Routing Path Length), độ trễ truyền tin [1], kích thước bảng định tuyến (RTS: Routing Table Size). Độ trễ truyền tin là khoảng thời gian gói tin bắt đầu được khởi tạo tại nút nguồn (source node), gửi đi trên kênh truyền và nhận được tại nút đích (destination node). Độ trễ đạt giá trị thấp là dấu hiệu của hiệu năng cao. Độ trễ lý thuyết tối thiểu có thể được tính toán thông qua mô hình hóa mạng như một cặp đồ thị và thuật toán định tuyến cho trước. Định tuyến là quá trình định hướng cho một gói tin di chuyển từ nút nguồn S đến nút đích T trong mạng. Các thuật toán định tuyến lựa chọn và xác định đường đi (path) để gói tin truyền từ nguồn tới đích trong một MLK xác định. Thuật toán định tuyến đường đi ngắn nhất (SPR: Shortest Path Routing, còn gọi là Minimal Routing) [1] được sử dụng trong các mạng dạng chuẩn tắc (regular). Minimal Routing đảm bảo yếu tố stretch–13 [20]. Ví dụ: 2-D Torus, 3-D Torus [1], FatTree [12], Hypercube sử dụng SPR. Các thuật toán định tuyến tùy chọn (Custom Routing) được thiết 3Tỉ lệ giữa chiều dài đường định tuyến với chiều dài ngắn nhất trên tô-pô mạng giữa cặp đỉnh bất kỳ trong mạng. kế riêng cho từng loại tô-pô cụ thể (còn gọi là Non-Minimal Routing), với stretch–3 [18, 21], thông thường là các mạng dạng không chuẩn tắc (irregular). RSN sử dụng thuật toán SPR hoặc TZ (Thorup & Zwick [18]), JellyFish [10] sử dụng k-SPR. 2. Công cụ mô phỏng mạng Hiện nay các nhà nghiên cứu thường tự phát triển phần mềm tính toán đặc trưng và đánh giá các tô-pô MLK (và thuật toán định tuyến), và khi cần thực hiện thực nghiệm mô phỏng có thể sử dụng các phần mềm mô phỏng mạng phổ quát, phổ biến hiện nay như NS2 [22], NS3 [15], OMNET++ [16], SIMGRID [17]. Hệ công cụ NS2 [22] thường được sử dụng thực nghiệm đối với các mạng không dây. NS2 có nhược điểm là quá trình mô hình hóa mạng khá phức tạp và tốn nhiều thời gian và bộ nhớ. Ngoài ra, nó cũng không định nghĩa sẵn các thiết bị như switch, router và không có giao diện người sử dụng (GUI: Graphic User Interface) để hiển thị kết quả. Là thế hệ đời sau, NS3 [15] cũng mô phỏng hệ thống bằng cách cấu hình các node mạng một cách đầy đủ, do đó NS3 cũng chỉ thực thi được với mạng kích thước nhỏ từ vài trăm tới nghìn nút. OMNET++ [16] hỗ trợ mô phỏng song song thông qua việc sử dụng các thư viện MPI (Message Passing Interface), thực hiện mô phỏng lưu lượng trong mạng, tạo mô hình các giao thức, xây dựng mô hình các hàng đợi trong mạng, xây dựng các bộ vi xử lý đa nhiệm và các hệ thống phân tán khác, kiểm tra lại kiến trúc phần cứng, đánh giá khía cạnh về hiệu suất của các hệ thống phần mềm phức tạp. SIMGRID [17] là một công cụ cung cấp các chức năng cơ bản để mô phỏng các ứng dụng phân tán quy mô lớn như Grid, P2P hay Cloud. Công cụ mô phỏng SIMGRID có thể được sử dụng để đánh giá thuật toán định tuyến, các ứng dụng MPI. Kích thước mạng được sử dụng để đánh giá chỉ đạt khoảng 256 nút đối với máy tính toán thông thường và đạt 1024 đối với máy tính toán có cấu hình mạnh. Nhìn chung, các phần mềm trên có tính phổ quát cao, tập trung mô phỏng các thiết bị và các giao thức mạng một cách chi tiết và đầy đủ. Nhằm đảm bảo phản ánh tương đối trọn vẹn các quá trình và yếu tố kỹ thuật đa dạng trong thực tiễn, các hệ này tập trung mô phỏng chi tiết. Lớp mạng với thư viện cấu hình đối tượng phân cấp phức tạp, mô phỏng rất sát thực tế các quá trình truyền tin. D ... ị. Kỹ thuật này khai thác một đặc điểm quan sát thấy là trong các MLK kiểu mới, đặc biệt là các tô-pô được tạo theo mô hình ngẫu nhiên, việc xây dựng định tuyến giữa hai cặp nguồn–đích bất kỳ là hầu như độc lập với nhau. Ví dụ, nhìn chung xây dựng đường đi giữa một cặp nút (u, v), không phụ thuộc vào việc xây dựng cho một cặp (u′, v′) khác. Từ đó, ta thấy không cần thiết phải có một quá trình khởi đầu xây dựng bảng định tuyến cho tất cả nút mạng, mà có thể tiến hành on-the-fly, tức là khi nào có một nhiệm vụ định tuyến nảy sinh thì các bảng định tuyến cho các nút nguồn và trung gian sẽ được xây dựng phục vụ trực tiếp cho nhu cầu tại chỗ (và tích lũy cho sau này). Hơn nữa một số đặc tính hiệu năng như ARPL có thể tính xấp xỉ bằng cách: thay vì tính độ dài đường đi của tất cả các 34 Tập 2019, Số 1, Tháng 9 cặp nút nguồ– đích có thể rồi lấy trung bình, chỉ cần thực hiện với một tỷ lệ tương đối thấp (vài phần trăm) các cặp nguồn–đích. Phần IV dưới đây sẽ báo cáo một số kết quả thực nghiệm khả quan khi chúng tôi tôi khảo sát áp dụng kỹ thuật xấp xỉ này. IV. KẾT QUẢ THỰC NGHIỆM Đây là một dự án phần mềm có yêu cầu tương đối cao nên chúng tôi mới thực hiện được một số khối chức năng cơ bản, trong đó có khối chức năng đánh giá trên phương diện phân tích đồ thị. Sau đây chúng tôi trình bày một số kết quả thực nghiệm với hệ công cụ về phân tích đồ thị, một trong những yêu cầu đánh giá cốt lõi nhất. Chúng tôi cũng minh họa sự hiệu quả của công cụ mô phỏng SSiNET bằng cách giả lập các mạng với kích thước khác nhau, và so sánh với thời gian thực thi các giả lập đó trên bộ công cụ NS3 [15]. Với mỗi loại tô-pô cụ thể, chúng thường được áp dụng một vài thuật toán định tuyến để đánh giá hiệu năng MLK. Do vậy, trong các mục IV.1 và IV.2, chúng tôi thử nghiệm với các tô-pô và thuật toán định tuyến tương ứng như sau: FatTree [12] – SPR, Kleinberg – Small-world – SPR, 2-D Torus [1] – Gready, RSN – TZ [18]. Kết quả thực nghiệm không đánh giá cặp tham số tô-pô và thuật toán định tuyến nào hiệu quả hơn, mà chỉ xác định khả năng thực nghiệm của SSiNET. Chúng tôi lần lượt thí nghiệm trên các bộ kích thước 210, 211, 212, 213. Ngoài ra, do cấu trúc đặc thù của FatTree [12], chúng tôi sử dụng kích thước 2000 và 4394 tương ứng với 211 và 212 tương ứng với các tô-pô còn lại. Ở thời điểm hiện nay sản phẩm công cụ của chúng tôi mới tập trung vào lớp thực nghiệm phân tích đồ thị, nên chưa có nhiều thông tin để so sánh đánh giá năng lực thực thi với các công cụ khác, ngoại trừ một so sánh thu được khi đang triển khai bước đầu phần mô phỏng thông lượng tại mục IV.3. 1. Kích thước bảng định tuyến) SPR xây dựng bảng định tuyến với kích thước O(N), với N là kích thước mạng. Do đó, trong thử nghiệm, chúng tôi không trình bày kết quả của SPR trên tô-pô Kleinberg – Smallworld. Hình 7 biểu diễn RTS của 2-D Torus không đổi với mọi kích thước mạng, do tính chất cấu trúc vòng đặc thù của Torus. Trong khi đó, FatTree – SPR có RTS đạt 1,25% và 0,31% kích thước mạng 210 và 213 tương ứng, RSN – TZ[18] có RTS 7,78% và 2,57% tương ứng. 2. Độ trễ truyền tin (Latency) Chúng tôi tiến hành thực nghiệm tính toán độ trễ với các tham số độ trễ trên switch là 100 nano giây, độ trễ 0 50 100 150 200 250 0 2000 4000 6000 8000 10000 R o u ti n g T ab le S iz e Number of network nodes RSN - TZ Fat Tree - SPR Torus - Greedy Hình 7. Tính toán kích thước bảng định tuyến. 0 1000 2000 3000 4000 5000 6000 0 2000 4000 6000 8000 10000 L at en cy ( se co n d s) Number of network nodes Torus - Greedy RSN - TZ SmallWorld - SPR Fat Tree - SPR (N = 4394) Hình 8. Độ trễ truyền tin trên mạng. trên đường truyền cáp quang là 5 nano giây trên mỗi mét dài [1, 13]. Độ trễ truyền tin toàn mạng L được tính toán dựa trên công thức sau: L = N∑ i=1 N∑ j=1 (Pathhop(i, j) ∗ 100 + Pathlength(i, j) ∗ 5), (1) trong đó, Pathhop(i, j) là số “hop”4 trên đường đi ngắn nhất và Pathlength(i, j) là chiều dài đường đi ngắn nhất giữa i và j. Với tổng số cặp đường đi Σpair(i, j), độ trễ trung bình được tính theo công thức: AvgLatency = L Σpair(i, j) . (2) Hình 8 chỉ ra kết quả thử nghiệm tính toán độ trễ. Trong đó, với cấu trúc đặc thù dạng cây, đường kính mạng bé, FatTree [12], đạt độ trễ thấp nhất trong mọi kích thước 4Số “khoảng” giữa hai nút liền kề trên đường định tuyến. 35 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 0 2,000 4,000 6,000 8,000 10,000 12,000 14,000 16,000 2,000 2,662 3,456 4,394 5,488 6,750 E x ec u ti o n T im e (s ec o n d s) Number of Network nodes SSiNET NS3 Hình 9. Thời gian thực thi của SSiNET và NS3. Bảng I ĐƯỜNG KÍNH MẠNG VỚI CÁC TỈ LỆ KÍCH THƯỚC MẠNG Diameter 1024 2048 4096 8192 1% 6,30 7,00 7,90 8,00 2% 6,80 7,00 8,00 8,00 5% 7,00 7,00 8,00 8,00 10% 7,00 7,00 8,00 8,00 100% 7,00 7,00 7,90 8,00 thử nghiệm. Trong khi đó, Torus có độ trễ cao do sử dụng định tuyến (DOR: Dimension Order Routing [1]), số hop trên đường định tuyến cao hơn so với các mạng ngẫu nhiên Kleinberg – Smallworld. Các kết quả so sánh tương đối giữa các tô-pô (và thuật toán định tuyến) nói trên phản ánh khớp với nhận định của chúng tôi thu được từ những khảo sát thông qua [12, 18, 20]. 3. Kết quả bước đầu về đánh giá thông lượng Cuối cùng, chúng tôi minh hoạ việc giả lập của MLK Fat Tree [12] với việc giá trị k thay đổi từ 20 đến 30. Để đo đạc hiệu năng của SSiNET, chúng tôi sử dụng máy tính Intel Core i7 2,3 GHz với bộ nhớ chính 8 GB. Hình 9 cho thấy thời gian thực thi của chương trình giả lập hoạt động trên SSiNET và NS3 [15], và hình này cung cấp cho người đọc thấy rõ ràng rằng SSiNET chỉ mất thời gian khoảng 40 phút (2564 giây) để giả lập mạng Fat-tree với k = 30 (ở đây mạng sẽ có k ∗ k ∗ k/4 = 6750 nodes) trong khi NS3 yêu cầu tới khoảng 4 giờ. 4. Phương pháp xấp xỉ Trong phương pháp này, chúng tôi tiến hành lấy ngẫu nhiên một số cặp nguồn–đích theo một tỉ lệ p% so với Bảng II ĐỘ TRỄ TRUNG BÌNH AvgLatency 1024 2048 4096 8192 1% 536,80 628,24 712,59 850,08 2% 536,05 628,11 712,35 850,46 5% 535,92 628,13 712,40 850,48 10% 536,15 628,22 712,31 850,49 100% 612,85 767,49 723,18 850,41 Bảng III THỜI GIAN THỰC THI Kích thước mạng 1024 8192 Tỉ lệ thử nghiệm 100% 5% 100% 5% Diameter 7,00 7,00 8,10 8,00 ARPL 4,51 4,52 5,93 5,93 AvgLatency 612,85 535,92 850,08 850,48 RunTime 5,74 1,02 1083,38 68,24 kích thước mạng. Tập các ứng viên được tính toán theo công thức (N ∗ (N − 1)) ∗ p%, p=1, 2, 5, 10, với N là kích thước mạng. Bảng I cho thấy kết quả thực nghiệm tính đường kính mạng với các tỉ lệ 1%, 2%, 5%, 10%, 100%. Trường hợp 100% là tính toán toàn bộ các cặp nguồn đích, tức là thực hiện đầy đủ như thông lệ. Các trường hợp 1% và 2% có giá trị đường kính mạng sai khác 10% và 3% với trường hợp 100%, tương ứng. Tuy nhiên với tỉ lệ 5% và 10% thì sự sai khác không có hoặc tương đối nhỏ so với 100%. Ngay cả độ trễ trung bình cũng chỉ sai khác trên 10%, đặc biệt với mạng kích thước 4096, sự sai khác đó chỉ là 1% và 2% tương ứng như Bảng II. Với phương pháp xấp xỉ như trên, thời gian thực thi của mạng giảm đáng kể. Ví dụ, thời gian thực thi giảm 82,25% và 93,70% với kích thước mạng 1024 và 8192 tương ứng, như Bảng III. Những kết quả thực nghiệm này cho thấy rõ phương pháp thực nghiệm xấp xỉ đã đề xuất là hứa hẹn và nên được triển khai đầy đủ. V. KẾT LUẬN Trong nghiên cứu này, chúng tôi đã đề xuất một cách tiếp cận mới cho việc thiết kế công cụ thực nghiệm đánh giá các tô-pô MLK theo phương châm mô phỏng giản lược và trình bày một bản thiết kế tổng quan và chi tiết cho sản phẩm công cụ SSiNET, phát triển theo tiếp cận này. Công cụ 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 khi đã hoàn thiện, công cụ còn cho phép tiến hành thực nghiệm 36 Tập 2019, Số 1, Tháng 9 đánh giá bố trí triển khai trên mặt sàn. Qua đó 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. Sản phẩm mới chỉ được thực hiện ở phần cơ bản, nên trong bài báo này chúng tôi tập trung giới thiệu thiết kế chi tiết các phần cơ bản đó và giới thiệu một vài kết quả thực nghiệm liên quan. Trong giai đoạn phát triển tiếp theo, chúng tôi sẽ tiếp tục hoàn thiện SSiNET, trong đó có việc hoàn thiện các chức năng mô phỏng cho phép đánh giá các yếu tố hiệu năng quan trọng khác như thông lượng mạng. Đồng thời kỹ thuật và phương pháp thực nghiệm xấp xỉ sẽ được hoàn thiện hơn để nâng cao hơn nữa tính khả thi của công cụ với việc đánh giá MLK có kích thước lớn và rất lớn. GHI NHẬN TÀI TRỢ Nghiên cứu này được tài trợ bởi Trường Đại học Bách khoa Hà nội trong đề tài mã số T2017-LN-15. TÀI LIỆU THAM KHẢO [1] W. J. Dally and B. P. Towles, Principles and practices of interconnection networks. Elsevier, 2004. [2] M. Koibuchi, H. Matsutani, H. Amano, D. F. Hsu, and H. Casanova, “A case for random shortcut topologies for HPC interconnects,” in 2012 39th Annual International Symposium on Computer Architecture (ISCA). IEEE, 2012, pp. 177–188. [3] N. Farrington, G. Porter, S. Radhakrishnan, H. H. Bazzaz, V. Subramanya, Y. Fainman, G. Papen, and A. Vahdat, “Helios: a hybrid electrical/optical switch architecture for modular data centers,” ACM SIGCOMM Computer Commu- nication Review, vol. 41, no. 4, pp. 339–350, 2011. [4] C. Guo, G. Lu, D. Li, H. Wu, X. Zhang, Y. Shi, C. Tian, Y. Zhang, and S. Lu, “BCube: a high performance, server- centric network architecture for modular data centers,” ACM SIGCOMM Computer Communication Review, vol. 39, no. 4, pp. 63–74, 2009. [5] C. Guo, H. Wu, K. Tan, L. Shi, Y. Zhang, and S. Lu, “Dcell: a scalable and fault-tolerant network structure for data centers,” in ACM SIGCOMM Computer Communication Review, vol. 38, no. 4. ACM, 2008, pp. 75–86. [6] L. Gyarmati and T. A. Trinh, “Scafida: A scale-free network inspired data center architecture,” ACM SIGCOMM Com- puter Communication Review, vol. 40, no. 5, pp. 4–12, 2010. [7] H. Wu, G. Lu, D. Li, C. Guo, and Y. Zhang, “MDCube: a high performance network structure for modular data center interconnection,” in Proceedings of the 5th international conference on Emerging networking experiments and tech- nologies. ACM, 2009, pp. 25–36. [8] A. Greenberg, J. R. Hamilton, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. A. Maltz, P. Patel, and S. Sengupta, “VL2: a scalable and flexible data center network,” in ACM SIG- COMM computer communication review, vol. 39, no. 4. ACM, 2009, pp. 51–62. [9] J.-Y. Shin, B. Wong, and E. G. Sirer, “Small-world data centers,” in Proceedings of the 2nd ACM Symposium on Cloud Computing. ACM, 2011, p. 2. [10] A. Singla, C.-Y. Hong, L. Popa, and P. B. Godfrey, “Jellyfish: Networking data centers randomly,” in Presented as part of the 9th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 12), 2012, pp. 225–238. [11] Y. Yu and C. Qian, “Space shuffle: A scalable, flexible, and high-bandwidth data center network,” in 2014 IEEE 22nd International Conference on Network Protocols. IEEE, 2014, pp. 13–24. [12] M. Al-Fares, A. Loukissas, and A. Vahdat, “A scalable, commodity data center network architecture,” in ACM SIG- COMM Computer Communication Review, vol. 38, no. 4. ACM, 2008, pp. 63–74. [13] I. Fujiwara, M. Koibuchi, H. Matsutani, and H. Casanova, “Skywalk: A topology for HPC networks with low-delay switches,” in 2014 IEEE 28th International Parallel and Distributed Processing Symposium. IEEE, 2014, pp. 263– 272. [14] J. Kim, W. J. Dally, S. Scott, and D. Abts, “Technology- driven, highly-scalable dragonfly topology,” in 2008 Interna- tional Symposium on Computer Architecture. IEEE, 2008, pp. 77–88. [15] D. Wong, K. T. Seow, C. H. Foh, and R. Kanagavelu, “Towards reproducible performance studies of datacenter network architectures using an open-source simulation ap- proach,” in 2013 IEEE Global Communications Conference (GLOBECOM). IEEE, 2013, pp. 1373–1378. [16] “OMNeT++ discrete event simulator.” [Online]. Available: https://www.omnetpp.org [17] “Simgrid: Versatile simulation of distributed systems.” [Online]. Available: [18] M. Thorup and U. Zwick, “Compact routing schemes,” in Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures. ACM, 2001, pp. 1– 10. [19] S. Lederer, Y. Wang, and J. Gao, “Connectivity-based local- ization of large-scale sensor networks with complex shape,” ACM Transactions on Sensor Networks (TOSN), vol. 5, no. 4, p. 31, 2009. [20] M. Benito, E. Vallejo, and R. Beivide, “On the use of commodity ethernet technology in exascale HPC systems,” in 2015 IEEE 22nd International Conference on High Per- formance Computing (HiPC). IEEE, 2015, pp. 254–263. [21] L. J. Cowen, “Compact routing with minimum stretch,” Journal of Algorithms, vol. 38, no. 1, pp. 170–183, 2001. [22] “Network simulation: NS2.” [Online]. Available: https://ns2tutor.weebly.com [23] K. Pagiamtzis and A. Sheikholeslami, “Content-addressable memory (CAM) circuits and architectures: A tutorial and survey,” IEEE journal of solid-state circuits, vol. 41, no. 3, pp. 712–727, 2006. [24] H. Liu, “Routing table compaction in ternary CAM,” IEEE Micro, vol. 22, no. 1, pp. 58–64, 2002. [25] C. Basso, J. L. Calvignac, G. T. Davis, and P. C. Patel, “Longest prefix match lookup using hash function,” Apr. 20 2010, US Patent 7,702,630. 37 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ều Thành Chung tốt nghiệp Kỹ sư Công nghệ Thông tin năm 2003 và Thạc sĩ Công nghệ Thông tin năm 2010 tại Trường Đại học Bách Khoa Hà Nội. Năm 2016, tác giả nghiên cứu tại Viện Công nghệ Thông tin Quốc gia Nhật Bản (NII), hiện nay là nghiên cứu sinh tại Viện Công nghệ Thông tin và Truyền thông (SoICT), Trường Đại học Bách khoa Hà Nội. Lĩnh vực nghiên cứu bao gồm: mạng liên kết, thuật toán định tuyến. Nguyễn Tiến Thành tốt nghiệp Kỹ sư Công nghệ Thông tin năm 2008 và Thạc Sĩ ngành Công nghệ Thông tin năm 2011 tại Đại học Bách Khoa Hà Nội. Hiện nay tác giả đang là giảng viên 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. Lĩnh vực nghiên cứu của tác giả bao gồm: công nghệ phần mềm, kiểm chứng mô hình và mạng tự điều khiển (self-driving networks). Nguyễn Khanh Văn tốt nghiệp Kỹ sư Tin học tại Trường Đại học Bách Khoa vào năm 1992, Thạc sỹ Khoa học Máy tính tại Đại học Wollongong (Úc) vào năm 2000 và Tiến sĩ Khoa học Máy tính tại Đại học California-Davis (Mỹ) vào năm 2006. Hiện nay ông là Phó Giáo sư, giảng dạy và nghiên cứu 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ác lĩnh vực nghiên cứu chính bao gồm: thuật toán và các mô hình lý thuyết trong tính toán phân tán và mạng máy tính (mạng liên kết, mạng cảm biến không dây), an toàn thông tin. 38
File đính kèm:
mot_tiep_can_thiet_ke_cong_cu_phan_mem_danh_gia_hieu_nang_ma.pdf