BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
--------------------------------------Trần Trung Hiếu

NGHIÊN CỨU MÔ PHỎNG VÀ TÍNH GIÁ THÀNH
CHO TÔ-PÔ MẠNG LIÊN KẾT TRONG SIÊU MÁY TÍNH
SỬ DỤNG CÔNG CỤ SIMGRID

Chuyên ngành: Công nghệ thông tin

LUẬN VĂN THẠC SĨ KỸ THUẬT
CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC:
1. TS. Phan Thanh Liêm
2. PGS. TS. Nguyễn Khanh Văn

Hà Nội – 2015

MỤC LỤC


2


LỜI CAM ĐOAN
Trước tiên tôi xin chân thành gửi lời cảm ơn và lòng biết ơn sâu sắc tới TS
Phan Thanh Liêm, PGS. TS Nguyễn Khanh Văn – Viện Công nghệ Thông tin –
Truyền thông, người đã tận tình hướng dẫn, chỉ bảo tôi trong suốt quá trình hoàn
thiện luận văn. Đồng thời tôi cũng xin bày tỏ lòng biết ơn các thầy cô giáo trong
Viện Công nghệ Thông tin – Truyền thông nói riêng và Đại học Bách Khoa Hà Nội

nói chung đã chỉ dạy, cung cấp những kiến thức quý báu cho tôi trong suốt quá trình
học tập và nghiên cứu tại trường.
Tôi xin gửi lời cảm ơn sâu sắc tới gia đình, bạn bè, những người luôn quan
tâm và giúp đỡ tôi trong suốt thời gian học tập và hoàn thành luận văn.
Tôi cam đoan đây là công trình nghiên cứu của riêng tôi.
Các số liệu, kết quả trong luận văn là trung thực và chưa từng được ai công bố
trong bất kỳ công trình nào khác.

3


DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
ST
T

Từ viết tắt

Giải nghĩa
Mạng liên kết, mạng kết nối

2

Interconnection
network
OCNs

3

SANs


System/storage area networks

4

DSN

Distributed Shortcut Networks

5
6

Logarithmic diameter Tính chất của một mạng mạng liên kết có đường
kính tính bằng hàm logarit của số nút mạng
Throughput
Thông lượng

7

Latency

Độ trễ

8

LSDC

Large- Scale Distributed Computing

9


MSG

Meta Simgrid

10

SMPI

Simulated Message Passing Interface

11

DAG

Direct Acyclic Graph

12

XBT

Extensible Bench of Tools

13

HPC

High-performance computing

14


P2P

Peer to peer

1

On-chip networks

4


DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ

5


MỞ ĐẦU
Trong những năm gần đây, việc sử dụng các siêu máy tính, các trung tâm dữ
liệu hiện đại là nhu cầu thiết yếu ở nhiều nước trên thế giới để xử lý và lưu trữ dữ
liệu phục vụ cho công tác nghiên cứu khoa học, ứng dụng và kinh doanh. Tại Việt
Nam, đã xuất hiện ngày càng nhiều các trung tâm dữ liệu hiện đại ở các trường đại
học như đại học Bách Khoa Hà Nội, đại học Quốc Gia, các doanh nghiệp như FPT
telecom, VNPT, Viettel, VC Corp… Trong lĩnh vực nghiên cứu khoa học, nhiều
nghiên cứu trong và ngoài nước về mạng liên kết là kết quả của mô phỏng. Điều đó
nói lên tầm quan trọng và mức độ ứng dụng rộng rãi của mô phỏng trong nghiên
cứu về mạng liên kết. Mô phỏng cho phép đánh giá được hiệu năng của một hệ
thống mạng với các điều kiện, cấu hình khác nhau trong trường hợp các phương
pháp đánh giá trực tiếp trên các hệ thống thật hoặc qua phân tích tính toán bằng toán
học không khả thi.
Hiện nay, trong các công cụ mô phỏng mạng liên kết, Simgrid nổi lên như

một công cụ có khả năng mô phỏng mạnh mẽ, chính xác, linh hoạt và hiệu năng
cao. Simgrid có khả năng mô phỏng cho các hệ thống tính toán phân tán lớn, trong
đó bao gồm nhiều loại như hệ thống tính toán song song, tính toán lưới (Grid), tính
toán đám mây (Cloud), tính toán hiệu năng cao (HPC), mạng khách chủ, mạng
ngang hàng (P2P).. Simgrid cũng có thể sử dụng cho các ứng dụng lập trình song
song truyền thông điệp MPI. Chính nhờ Simgrid có khả năng đáp ứng nhiều tiêu chí
của các cộng đồng tính toán phân tán khác nhau, nên Simgrid đã trở lên vượt trội so
với các công cụ được xây dựng với một đặc thù hệ thống nhất định, Simgrid có thể
coi như một thước đo chung để so sánh, đánh giá giữa các hệ thống, ứng dụng phân
tán.
Tại Việt Nam, việc các nghiên cứu sử dụng Simgrid chưa thực sự nhiều, hơn
nữa khi thiết lập một mạng liên kết, việc ước đoán, tính giá thành cho tô-pô mạng là
một khâu khá quan trọng vì những lý do trên nên tôi đã chọn đề tài “Nghiên cứu mô

6


phỏng và tính giá thành cho tô-pô mạng liên kết trong siêu máy tính sử dụng công
cụ Simgrid”.

7


CHƯƠNG 1: CƠ SỞ LÝ THUYẾT
1.1. Tổng quan về mạng liên kết (Interconnection Network)
1.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) được hiểu một cách tổng quát là
một hệ thống có thể lập trình được vận chuyển dữ liệu giữa các thiết bị đầu cuối [1].
Hình 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ừ
TB1 đến TB5) 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 TB1 trao đổi dữ liệu với TB5, TB1 gửi một gói tin chứa dữ
liệu đó đến mạng liên kết. Gói tin này tiếp đó được chuyển tiếp tới 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, sau đó cũng có thể được sử dụng để chuyển tiếp gói tin từ TB2 đến
TB5. Tính chất này thể hiện khả năng có thể lập trình được của mạng liên kết. Ở đó,
các kết nối khác nhau giữa các thiết bị đầu cuối khác nhau được thiết lập và thay đổi
theo thời gian nhằm phục vụ nhu cầu truyền tin trong mạng.

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

8


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 (highperformance computing), lưu trữ vào ra (storage I/O), các hệ thống
cluster/workgroup.... Tùy thuộc vào số luơng các thiết bị được kết nối và khoảng
cách giữa các thiết bị, mạng liên kết được chia ra làm bốn lĩnh vực ứng dụng chính
[2]:
- On-chip networks (OCNs) hay còn được nhắc tới với thuật ngữ network-onchip (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 module đ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ớ (processormemory) trong các hệ thống đa nhân và hệ thống đa máy tính (multicomputer).
Ngoài ra loại mạng liên kết này 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ủ (server) và các
trung tâm dữ liệu (data centers). 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 khoảng cách khoảng vài trăm met.
- Local area networks (LANs): Đây là mạng liên kết được sử dụng để kết nối
hệ thống máy tính cá nhân. Kết nối máy tính trong một cụm là một ví dụ điển hình.
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. WANs cũng kết nối hàng triệu các máy tính với nhau
trên khoảng cách lớn.
Hình 2 (nguồn [8]) 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ị được kết nối trong mạng cũng như khoảng cách
9


giữa chúng. Trục hoành (trục ngang) biểu thị số lượng thiết bị trong mạng liên kết.
Trục tung (trục đứng) biểu thị khoảng cách giữa các thiết bị tính theo đơn vị met.

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, người viết nghiên cứu các vấn đề của
mạng liên kết một cách tổng quát nhưng tập trung hơn 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à trung tâm dữ liệu (data center). Do đó, người viết sẽ
trình bày cơ sở lý thuyết cơ bản liên quan đến lĩnh vực nghiên cứu của mình trong
các phần tiếp theo và có thể không bao hàm nội dung liên quan đến các lĩnh vực
khác.

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


thông qua các kênh truyền. Các thiết bị đầu cuối, bộ chuyển tiếp trung gian được
gọi là nút mạng (node). Mẫu thiết kế các kết nối giữa các nút mạng đượ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.
Các gói tin được truyền giữa các thiết bị đầu cuối bằng cách được chuyển
tiếp một vài lần thông qua các kênh truyền dùng chung và bộ chuyển tiếp trung gian
từ nguồn tới đích. Ở đó, một gói tin có thể được truyền đi theo nhiều con đường
khác nhau từ nguồn cho tới đích. Định tuyến (routing) là quá trình lựa chọn và chỉ
ra con đường nào sẽ được chọn để gói tin truyền theo. Quá trình định tuyến cần ưu
tiên lựa chọn những con đường ngắn nhất trong khi vẫn đảm bảo được yêu cầu cân
bằng tài nguyên dùng chung trên mạng (bộ chuyển tiếp, kênh truyền). Độ dài của
đường đi liên quan trực tiếp tới độ trễ (latency) truyền tin của mạng trong khi tải
(load) thể hiện khối lượng sử dụng của một tài nguyên cụ thể.
Tại một thời điểm, một tài nguyên có thể được yêu cầu sử dụng bởi các gói
tin khác nhau. Điều khiển luồng (flow control) là quá trình lựa chọn, ra lệnh cho gói
tin nào được quyền truy cập vào một tài nguyên cụ thể tại thời điểm đó. Điều khiển
luồng được thực hiện liên tục theo thời gian và đóng vai trò quan trọng trong việc
vừa chuyển tiếp các gói tin với độ trễ nhỏ nhất, vừa đảm bảo được các tài nguyên
không bị sử dụng quá tải, hoặc không được sử dụng trong thời gian dài.
Ngoài cấu hình mạng, định tuyến, và điều khiển luồng, một khái niệm quan
trọng ảnh hưởng đến việc nghiên cứu và đánh giá, thử nghiệm các mạng liên kết đó

là “mẫu trao đổi thông tin” (traffic pattern). Traffic pattern là một phương pháp mô
hình hóa sự phân phối của các gói tin được gửi đi trong mạng liên kết. Bảng 1 mô tả
các traffic pattern hay được sử dụng trong quá trình nghiên cứu đánh giá hoạt động
của mạng liên kết. Trong một mạng liên kết gồm N nút mạng, Random traffic thể

11


hiện một gói tin được gửi từ nguồn s đến đích d bất kì một cách ngẫu nhiên. Do đó
lượng thông tin gửi từ s đến d xác định được xác định theo phân phối đều λ sd = 1/N.
Permuation traffic thể hiện mọi gói tin gửi từ một nguồn s được gửi đến một hay
một vài đích xác định. Do đó nút đích được xác định bằng một hàm của nguồn d =
π(s). Bảng 1 liệt kê một vài traffic pattern khác nhau dựa trên phương pháp trộn
(permutation).
Tên mẫu
Random
Permutation
Bit permutation
Bit complement
Bit reverse
Bit rotation
Shuffle
Transpose

Digit permutations
Tornado
Neighbor

Mô tả
λsd = 1/N

d = π(s)
di = sf(i) ⊕ g(i)
di =￢si
di = sb-i-1
di = si+1 mod b
di = si-1 mod b
di = si+b/2 mod b
dx = f(sg(x))
dx = sx + (k/2-1) mod k
dx = sx + 1 mod k

Bảng 1: Bảng các traffic pattern trong mạng liên kết

1.2. Tổng quan về cấu hình mạng
Cấu hình mạng là mẫu thiết kế 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 hình mạng là rất quan trọng do đây là yếu
tố liên quan trực tiếp đến cài đặt chi tiết. Cấu hình 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.
Qua đó, cấu hình mạng ảnh hưởng tới chi phí của mạng liên kết. Cấu hình mạng
cũng quyết định đến quá trình định tuyến (routing). 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 hình mạng được chọn sử dụng dựa trên chi phí và hiệu năng của
nó.

12


Có rất nhiều loại cấu hình mạng đượ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 ở đó 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 3.a). 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 (cable) 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 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.
- Star: hay còn gọi là 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 để truyền dữ liệu (Hình 3.b). 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.

13


Hình 3: Các cấu hình mạng cơ bản
- Ring: hay còn gọi là mạng hình tròn. Ở đó mỗi một nút mạng liên kết trực
tiếp với đúng hai nốt mạng khác tạo thành một vòng tròn khép kín (Hình 3.c).
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 liên kết.
- Mesh: mô tả một mạng liên kết mà ở đó từ mỗi một nút mạng đều tìm được
kết nối đến nút mạng khác. Mesh thường được biết đến với dạng lưới. Hình 3.d mô
tả một mesh mà ở đó một nút mạng liên kết trực tiếp với mọi 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)
Hình 3 minh họa ví dụ của năm cấu hình mạng cơ bản nêu trên. Ở đó, 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

14



hình mạng và dễ dàng định tuyến [3]. Dựa vào đó, những cấu hình mạng như là kary n-dimensional mesh hoặc là k-ary n-dimensional torus đã được thiết kế và phát
triển [3]. Hình 4 (nguồn [1]) mô tả mạng 4-ary 2-dimentional torus gồm 16 nút
mạng được xắp xếp dưới dạng lưới 4x4 nút mạng. Trong đó, mỗi nút mạng kết nối
với 4 nút mạng khác (gọi là nút mạng có bậc 4). K-ary n-dimensional torus có tính
chất “có quy tắc” (regular). Ở đó, số kết nối trên các nút mạng là như nhau (bậc
không đổi với mọi đỉnh).

Hình 4: Mạng liên kết 2D-Torus gồm 4x4 nút mạng

1.3. Tổng quan về giải thuật định tuyến trên mạng
Định tuyến là quá trình quá trình lựa chọn và chỉ ra con đường để gói tin
truyền từ nguồn tới đích trong một mạng liên kết xác định. Giải thuật định tuyến là
thuật toán dùng để lựa chọn con đường nói trên. Thuật toán định tuyến có vai trò
quan trọng bởi một số lý do sau: (i) Thuật toán định tuyến giúp cân bằng tải trong
quá trình truyền tin. Nghĩa là lượng thông tin được tuyền qua mỗi kết nối là tương
đương nhau trong quá trình hoạt động của mạng liên kết. Từ đó, việc tranh chấp tài
nguyên và tắc nghẽn (deadlock) được giảm thiểu. (ii) Một thuật toán định tuyến tốt

15


sẽ giúp cho các gói tin được truyền đi theo con đường ngắn nhất có thể. Qua đó góp
phần làm giảm thiểu độ trễ truyền tin. (iii) Ngoài ra, thuật toán định tuyến tốt còn có
khả năng chịu lỗi khi một hay một vài nút mạng, liên kết xảy ra sự cố và không thể
hoạt động. Trong trường hợp này, một thuật toán định tuyến phải loại bỏ các
phương án lựa chọn đường đi bao gồm các liên kết bị lỗi và phải lựa chọn những
đường đi khác nhằm đảm bảo sự hoạt động của mạng liên kết.
Có rất nhiều cách phân loại thuật toán định tuyến khác nhau. Dựa trên số
lượng đích tới của một gói tin, unicast routing chỉ các thuật toán định tuyến các gói

tin được gửi từ một nút nguồn tới một đích. Trong khi đó multicast routing chỉ các
thuật toán gửi tin tới hai hay nhiều đích trong mạng liên kết.
Thuật toán định tuyến cũng có thể được phân loại dựa trên địa điểm mà
quyết định định tuyến được thực hiện. Một cách đơn giản, con đường truyền tin có
thể được quyết định ngay tại nguồn (source routing), tại một bộ điều khiển tập
trung (centralized routing) hoặc được quyết định một cách phân tán tại các nút
mạng trong quá trình truyền tin (distributed routing).
Giải thuật định tuyến được cài đặt theo nhiều cách khác nhau. Một vài cách
phổ biến nhất được áp dụng đó là sử dụng bảng định tuyến (table lookup routing)
hay sử dụng máy trạng thái hữu hạn (finite-state machine routing). Trong cả hai
trường hợp này thuật toán định tuyến đều có thể là deterministic hoặc adaptive.
Deterministic routing là các thuật toán định tuyến mà đường đi giữa nút nguồn s và
nút đích d được chọn trước và không đổi trong mọi lần định tuyến (kể cả trong
trường hợp có nhiều con đường từ s đến d). Còn adaptive routing là phương pháp
định tuyến dựa vào trạng thái của mạng liên kết để xác định con đường chính xác
tại mỗi lần lựa chọn. Trạng thái này bao gồm thông tin về các nút mạng, các liên kết
trong mạng (bị lỗi hay không), thông tin về yêu cầu sử dụng các liên kết…
Trong quá trình định tuyến, nếu tất cả các con đường được lựa chọn đều là
ngắn nhất, chúng ta gọi là minimal routing. Ngược lại, giải thuật có tính chất nonminimal. Hình 5 (nguồn [1]) là một ví dụ về thuật toán định tuyến trên mạng liên

16


kết 4-ary 2-dimentional torus. Trong đó thuật toán định tuyến trong Hình 5a là
minimal do chỉ ra 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. Nếu các con đường định tuyến được xác định tại nút mạng 01
(ngay từ đầu) thì đó là source routing. Nếu con đuờng từ 01 đến 22 luôn luôn không
đổi tại mọi thời điểm định tuyến, thuật toán này gọi là deterministic routing. Source
routing và deterministic routing thường được cài đặt sử dụng 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

1.4. Tổng quan về điều khiển luồng
Điều khiển luồng (flow control) là quá trình xác định cách thức các tài
nguyên trên mạng (kết nối, bộ đệm tại các nút mạng…) được phân phối cho các gói
tin sử dụng trong quá trình truyền tin. Điều khiển luồng tốt là cách thức phân phối
tài nguyên một cách có hiệu quả qua đó truyền tin với độ trễ nhỏ xác định trước.
Ví dụ, hai gói tin đến từ hai cổng khác nhau tại một bộ chuyển tiếp tại cùng
một thời điểm. Dựa trên giải thuật định tuyến, hai gói tin này cần được chuyển tiếp
đến cùng một cổng ra. Trong trường hợp này, điều khiển luồng là cơ chế giải quyết
sự xung đột về yêu cầu sử dụng tài nguyên. Một phương pháp đơn giản đó là chọn
một gói tin ngẫu nhiên để chuyển tiếp và loại bỏ gói tin còn lại (gói tin này sẽ được

17


gửi lại sau). Đây là cơ chế đơn giản nhất trong điều khiển luồng khi không lưu trữ
gói tin tại các bộ chuyên tiếp (bufferless flow-control).
Một cơ chế điều khiển luồng khác phức tạp hơn và hiệu quả hơn gọi là
chuyển mạch (circuit switching). Trong đó, nút nguồn sẽ gửi gói tin thăm dò đến
nút đích. Gói tin thăm dò chỉ bao gồm thông tin truyền tin cơ bản (ví dụ nút nguồn,
nút đích) mà không bao gồm dữ liệu. Gói tin thăm dò có tác dụng đăng kí sử dụng
tài nguyên tại các nút mạng mà nó đi qua. Khi nút đích nhận được gói tin thăm dò
này sẽ gửi trả một gói tin gọi là ACK xác nhận. Nút nguồn sẽ bắt đầu truyền dữ liệu
theo con đường được thiết lập bởi gói tin thăm dò trước đó sau khi nhận được ACK.
Các tài nguyên trên được gói tin này sử dụng chỉ được giải phóng khi toàn bộ dữ
liệu đến với nút đích. Trong trường hợp một gói tin thăm dò không được cấp phát
tài nguyên ngay lập tức tại một nút mạng, nó sẽ được lưu trữ lại trong hàng đợi (do
kích thước gói tin thăm dò nhỏ) cho đến khi tài nguyên được giải phóng. Với cách

điều khiển luồng này, độ trễ truyền tin đôi khi rất lớn khi một gói tin cần phải đợi
tài nguyên được giải phóng tại nút mạng được nhiều gói tin truyền qua (nút thắt cổ
chai).
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). Trong phương pháp này, dữ liệu được
chia thành các thành phần nhỏ hơn có độ dài bằng nhau gọi là packet. Một vài bytes
đầu của packet chứa thông tin định tuyến và điều khiển gọi là packet header. Trong
quá trình truyền tin, nếu xảy ra tranh chấp tài nguyên, các packet này sẽ được lưu
trữ lại tại nút mạng đó và chờ cho đến khi tài nguyên được giải phóng. Do vậy,
chuyển mạch gói còn được gọi là store-and-forward switching. Với cơ chế này, các
phần nhỏ của toàn bộ dữ liệu được truyền trong mạng theo các đường khác nhau
nhằm tận dụng các tài nguyên rảnh rỗi. Ngoài ra quá trình chờ đợi để giải phóng tài
nguyên cũng ngắn hơn do kích thước của các packet là nhỏ hơn rất nhiều so với
kích thước dữ liệu cần truyền.

18


Trong quá trình chuyển mạch gói, quá trình định tuyến được thực hiện khi
toàn bộ packet được truyền tới và lưu trữ tại nút trung gian. Tuy nhiên, trong thực
tế, packet header truyền đến nút mạng này trước khi toàn bộ phần dữ liệu mà packet
ấy chứa truyền tới. Nhằm giảm độ trễ truyền tin, và giảm thời gian sử dụng tài
nguyên của một packet, quá trình định tuyến và chuyển tiếp packet header có thể
được thực hiện ngay khi tài nguyên yêu cầu sử dụng được rảnh rỗi mà không cần
phải chờ đợi toàn bộ packet đến được nút trung gian. Với phương pháp điều khiển
luồng này, một packet sử dụng cùng lúc cổng ra (output port) tại một nút trung gian
và cổng vào (input port) tại nút mạng tiếp theo. Phương pháp này được gọi là
virtual cut-though switching.
Lưu trữ các packet có kích thước lên đến hàng chục bytes gây khó khăn cho
việc chế tạo các bộ chuyển tiếp (hay bộ chuyển mạch) có kích thước nhỏ, giá thành

rẻ. Bên cạnh đó, quá trình chờ đợi các packet được truyền tin cũng góp phần tạo độ
trễ truyền tin. Nhằm khắc phục các yếu điểm này, Wormhole switching đã được đề
xuất. Trong phương pháp này, các packets đuợc chia nhỏ thành các đơn vị truyền
tin (flits). Kích thước bộ đệm tại các cổng ra và cổng vào tại một nút mạng đủ lớn
để chứa một vài flits. Ví dụ một flits có thể có kích thước cỡ 16 bits. Nhờ đó, yêu
cầu về kích thước bộ đệm trong các bộ định tuyến giảm đi đáng kể. Mặt khác,
phương pháp điều khiển luồng Wormhole switching có thể khiến quá trình truyền
tin bị tắc nghẽn. Trong trường hợp một packet phải đợi tài nguyên được giải phóng,
packet trong Wormhole Switching bị chặn lại tại nhiều bộ chuyển tiếp thay vì một
bộ chuyển tiếp duy nhất như ở Virtual Cut-through switching. Hình 6 (nguồn [4])
minh họa trường hợp này. Trong đó, gói tin B đang chiếm tài nguyên bộ đệm của
một cổng ra tại nút mạng R3. Packet header của gói tin A truyền tới R3 phải đợi bộ
đệm ở cổng ra được giải phóng. Trong khi các thành phần dữ liệu của gói tin A
được lưu trữ trong bộ đệm tại nút mạng R1 và R2 thay vì được lưu trữ toàn bộ tại
R3. Lưu ý rằng các bộ đệm trong ví dụ này chỉ có kích thước rất nhỏ 2 flits (cỡ 32
bits).

19


Hình 6: Ví dụ về tắc nghẽn của Wormhole switching

1.5. Hiệu năng của mạng liên kết
Như đã đề cập trong 1.2, cấu hình mạng được chọn dựa trên chi phí và hiệu
năng của nó. Trong phần này, người viết sẽ trình bày hai độ đo hiệu năng chính bao
gồm: thông lượng (throughput), độ trễ (latency).

1.5.1. Thông lượng (Throughput)
Thông lượng được định nghĩa là lượng thông tin tối đa được truyền trong
một đơn vị thời gian trong mạng liên kết [4]. Lượng thông tin được truyền trong

một đơn vị thời gian còn được gọi là traffic. Do đó thông lượng còn được hiểu là
traffic tối đa mà mạng liên kết chấp nhận được (maximum accepted traffic).
Để định lượng thông lượng, ban đầu người ta sử dụng đơn vị gói tin trong
một giây. Tuy nhiên, trong quá trình nghiên cứu hiệu năng của mạng liên kết thông
qua các công cụ giả lập đơn vị thời gian có thể được xác định tương đối bằng đơn vị
chu kì đồng hồ (clock cycle). Do đó, thông lượng cũng có thể tính bằng số gói tin
trong một clock cycle. Một cách tổng quát, thông lượng tỉ lệ thuận với kích thước
của mạng liên kết (số lượng nút mạng hay số cổng vào dữ liệu). Mạng liên kết có
kích thước lớn hơn có khả năng truyền được số lượng gói tin lớn hơn. Mặt khác, với
mỗi ứng dụng cụ thể, kích thước của gói tin là khác nhau. Do đó, nhằm mục đích

20


tiêu chuẩn hóa, thông lượng được lượng giá bằng đơn vị bits trên một nút mạng và
micro-giây, hay bits trên một nút mạng và clock cycle. Như vậy, thông lượng
(throughput) của mạng theo đó được hiểu là tốc độ truyền thông tin (bps, bit per
cycle) mà mạng chấp nhận trên từng cổng vào (input port) [1].

Hình 7: Tương quan giữa throughput và offered traffic

Thông lượng mang ý nghĩa trái ngược với giao thông yêu cầu (hay còn gọi là
offered traffic) – tốc độ gói tin (thông tin) được sinh ra bởi nguồn – Hình 7 (nguồn
[1]) thể hiện mối tương quan giữa thông lượng và yêu cầu. Ban đầu, khi lượng
thông tin yêu cầu truyền đi còn thấp, thông lượng và offered traffic có giá trị bằng
nhau. Theo sự tăng lên của yêu cầu truyền tin, thông lượng đạt đến mức bão hòa và
mạng liên kết không thể đáp ứng truyền tất cả các gói tin với tốc độ ban đầu. Đây
cũng là phương pháp để đánh giá thông lượng của mạng liên kết dưới một yêu cầu
truyền tin cụ thể (traffic pattern).


21


1.5.2. Độ trễ (Latency)
“Độ trễ là khoảng thời gian trải qua từ khi một gói tin được khởi tạo tại nút
nguồn đến khi gói tin đó được nhận ở nút đích” [4]. Định nghĩa này có thể hiểu theo
nhiều mức độ khác nhau. Nếu nghiên cứu chỉ liên quan đến kết nối và các thiết bị
mạng, độ trễ được định nghĩa là khoảng thời gian kể từ khi thành phần dữ liệu đầu
tiên của gói tin (thường gọi là message header) bắt đầu được gửi vào mạng cho đến
khi thành phần dữ liệu cuối cùng đến được đích. Một nút mạng có thể gửi và nhận
cùng lúc nhiều gói tin. Do đó, trong mỗi nút mạng có một bộ phận hàng đợi chứa
các gói tin gửi đi và gói tin nhận được để chờ xử lý. Nếu quá trình nghiên cứu liên
quan đến sự hoạt động của hàng đợi này, độ trễ nêu trên cần được tính thêm khoảng
thời gian trong hàng đợi tại nút nguồn.
Ngoài ra, một số nghiên cứu không chỉ tập trung chú ý tới tác động của mạng
liên kết tới độ trễ mà còn chú ý tới tác động của các hoạt động được thực hiện tại
các bộ vi xử lý nguồn, đích để gửi và nhận tin nhắn từ mạng. Các hoạt động này bao
gồm tiến trình chuẩn bị dữ liệu để truyền đi (ví dụ như xây dựng thông tin gói tin –
packet header, thành phần kiểm tra lỗi – checksums), quá trình gửi gói tin vào
(inject) và lấy gói tin ra (eject) khỏi mạng liên kết. Trong hầu hết các hệ thống, các
hoạt động này được cài đặt trong phần mềm gọi là messaging layer. Đối với những
nghiên cứu cân nhắc và đánh giá tác động của messaging layer, độ trễ được định
nghĩa là khoảng thời gian kể từ khi lời gọi truyền tin của hệ thống được khởi tạo tại
nút nguồn cho đến khi lời gọi nhận tin của hệ thống được hoàn thành tại nút nguồn.
Trong các hệ thống yêu cầu các hoạt động hoàn thành nhờ sự cộng tác, trao
đổi thông tin giữa một nhóm các nút mạng (collective communication operations),
độ trễ được đánh giá bằng thời gian kể từ khi một hoạt động được khởi tạo tại một
hay một vài nút mạng cho đến khi tất cả các nút mạng tham gia vào quá trình thực
hiện hoàn thành nhiệm vụ của mình. Ví dụ, trong nghiên cứu chỉ liên quan đến kết
nối và các thiết bị mạng, độ trễ của thao tác truyền tin đến tất cả các nút mạng khác

(multicast) được xác định là khoảng thời gian thành phần dữ liệu đầu tiên được gửi

22


vào trong mạng liên kết tại nút nguồn cho đến khi thành phần dữ liệu cuối cùng
được nhận bởi nút đích cuối cùng.
Trong quá trình thực hiện luận văn, người viết quan tâm đến các nghiên cứu
tập trung vào kết nối và các thiết bị mạng và bỏ qua các yếu tố liên quan đến hàng
đợi và messaging layer. Độ trễ được mô hình hóa thành 3 thành phần chính
latency = injection_time + time_to_fly + switches_latency
o Injection time: một số tài liệu còn gọi là serialization latency [1] hay
transmission time [2]. Đây là thời gian gói tin được gửi vào mạng (inject). Cụ thể
hơn, khoảng thời gian giữa thành phần dữ liệu đầu tiên của gói tin truyền vào mạng
đến khi thành phần dữ liệu cuối cùng truyền vào mạng. Theo định nghĩa, injection
time được tính bằng kích thước của gói tin chia cho băng thông của đường truyền
mạng (trong trường hợp toàn bộ đường truyền này được sử dụng để truyền gói tin
đó mà không phải chia sẻ để truyền gói tin nào khác).
o Time to fly: hay còn gọi là time of flight [1], là khoảng thời gian cần thiết
để truyền trên đường truyền mạng. Time to fly phụ thuộc vào độ dài của đường
truyền mạng. Time to fly trong các lĩnh vực ứng dụng WANs có đơn vị là mili-giây,
micro-giây cho LANs, nano-giây với SANs và pico-giây đối với OCNs.
o Switches latency: là khoảng thời gian tiêu tốn để gói tin được xử lý tại các
bộ chuyển mạch (switch) trên đường truyền (định tuyến truyền tin, gửi tin đến các
cổng…) Theo định nghĩa, switches latency phụ thuộc vào số lượng bộ chuyển mạch
mà gói tin truyền qua trên đường từ nguồn tới đích. Do đó giá trị trung bình của
switches latency của mạng liên kết được tính bằng tích của giá trị trung bình của các
đường đi (có thể là ngắn nhất) Havg nhân với thời gian trễ tại một bộ chuyển mạch
bất kì tr.
Công thức tính độ trễ nêu trên được sử dụng khi trong quá trình truyền tin

không có tranh chấp về mặt tại nguyên. Trong trường hợp ngược lại, độ trễ cần phải
cộng thêm khoảng thời gian để các gói tin nằm chờ trong hàng đợi.

23


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) thể
hiện mối tương quan giữa độ trễ và giá trị này. Khi mà offered traffic còn nhỏ,
không xảy ra tranh chấp tài nguyên, độ trễ có hình dạng theo công thức trên. Tuy
nhiên, khi offered traffic tăng dần, độ trễ tăng một lượng lớn. Offered traffic đạt đến
giá trị bão hòa khi độ trễ trở nên rất lớn. Hình 8 (nguồn [1]) là một ví dụ của tương
quan giữa độ trễ và offered traffic.

24


CHƯƠNG 2: PHƯƠNG PHÁP ĐÁNH GIÁ MẠNG LIÊN KẾT
Trong chương này, người viết trình bày về các phương pháp và công cụ đánh
giá được sử dụng trong quá trình thực hiện nghiên cứu đề tài. Với mục tiêu xây
dựng một mạng liên kết trao đổi dữ liệu và giải thuật định tuyến có độ trễ nhỏ, có
khả năng mở rộng, chúng tôi tập trung đánh giá các tiêu chí liên quan đến (i) chi phí
cài đặt, vận hành mạng, (ii) hiệu năng của mạng khi sử dụng (cụ thể là thông lượng
và độ trễ truyền dữ liệu), và (iii) khả năng chịu lỗi của mạng.

2.1. Đá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 (data
centers), người viết tập trung đánh giá chi phí của mạng liên kết ở hai quá trình cài
đặt và vận hành hệ thống. Chi phí cài đặt mạng liên kết được hiểu là lượng tiền cần
thiết để thiết lập được một hệ thống mạng liên kết trong thực tế bao gồm chi phí cho

việc mua sắm các thiết bị, dây nối, và chi phí lắp đặt. Ngoài ra, người viết cũng chú
ý tới tiêu tốn tài nguyên (điện năng) khi vận hành hệ thống trong thực tế.

2.1.1. Chi phí thiết lập mạng
Chi phí đầu tư cho mua sắm thiết bị mạng chiếm một phần lớn chi phí cài đặt
mạng liên kết. Mô hình hóa một mạng liên kết tổng quát có thể hiểu là một mạng
kết nối của các thiết bị chuyển mạch (switches). Nhằm đơn giản hóa mô hình tính
toán chi phí, chúng tôi lựa chọn chi phí cho một thiết bị chuyển mạch ở mức 500$
cho mỗi cổng (port) dựa trên khảo sát trong [5]. Mỗi cổng tương ứng với một liên
kết của thiết bị chuyển mạch đó trong mạng liên kết.
Chi phí cài đặt mạng còn bao gồm cả chi phí cho các dây nối – cáp mạng
(cable) dùng để liên kết các thiết bị với nhau. Có nhiều giải pháp khác nhau khi lựa
chọn xây dựng hệ thống cáp mạng cho mạng yêu cầu hiệu năng cao. Mỗi giải pháp
tương ứng với một mức chi phí cụ thể dành cho cáp mạng, đầu kết nối (connector)
tại các thiết bị. Hiện nay, có hai giải pháp được sử dủng phổ biến là dùng cáp đồng
và cáp quang. Sử dụng cáp đồng có giá thành rẻ hơn cáp quang do chi phí của đầu
25