Nghiên cứu mô phỏng và tính giá thành
- 79 trang
- file .pdf
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
Danh mục các ký hiệu, các chữ viết tắt .......................................................................6
Danh mục các hình vẽ, đồ thị ......................................................................................7
MỞ ĐẦU .....................................................................................................................9
CHƢƠNG 1: CƠ SỞ LÝ THUYẾT .........................................................................11
1.1. Tổng quan về mạng liên kết (Interconnection Network) ...............................11
1.1.1. Khái niệm, ứng dụng của mạng liên kết .................................................11
1.1.2. Các thành phần cơ bản trong mạng liên kết ............................................13
1.2. Tổng quan về cấu hình mạng .........................................................................15
1.3. Tổng quan về giải thuật định tuyến trên mạng...............................................18
1.4. Tổng quan về điều khiển luồng ......................................................................20
1.5. Hiệu năng của mạng liên kết ..........................................................................23
1.5.1. Thông lƣợng (Throughput) .....................................................................23
1.5.2. Độ trễ (Latency) ......................................................................................25
CHƢƠNG 2: PHƢƠNG PHÁP ĐÁNH GIÁ MẠNG LIÊN KẾT ...........................28
2.1. Đánh giá chi phí .............................................................................................28
2.1.1. Chi phí thiết lập mạng .............................................................................28
2.1.2. Chi phí vận hành mạng ...........................................................................32
2.2. Đánh giá hiệu năng mạng liên kết bằng lý thuyết đồ thị ...............................33
2.2.1. Đánh giá thông lƣợng lý tƣởng bằng lý thuyết đồ thị .............................33
2.2.2. Đánh giá độ trễ bằng lý thuyết đồ thị ......................................................35
2.2.3. Đánh giá khả năng chịu lỗi bằng lý thuyết đồ thị ...................................37
2.3. Đánh giá hiệu năng mạng liên kết bằng công cụ mô phỏng ..........................37
2
2.3.1. Phƣơng pháp đánh giá hiệu năng bằng công cụ mô phỏng ....................37
2.4. Đánh giá hiệu năng của ứng dụng ..................................................................38
2.4.1. Phƣơng pháp đánh giá .............................................................................38
2.4.2. Công cụ mô phỏng ..................................................................................41
CHƢƠNG 3: CÔNG CỤ MÔ PHỎNG SIMGRID ..................................................43
3.1. Giới thiệu sơ lƣợc về các công cụ mô phỏng mạng .......................................43
3.2. Tổng quan về kỹ thuật mô phỏng...................................................................46
3.2.1 Hệ thống, mô hình và mô phỏng ..............................................................46
3.2.2 Các bƣớc trong mô phỏng một hệ thống ..................................................49
3.3. Công cụ mông phỏng Simgrid .......................................................................51
3.3.1. Tổng quan về Simgrid .............................................................................51
3.3.2. Cấu hình căn bản cho các ứng dụng Simgrid..........................................52
3.3.3 Kiến trúc Simgrid .....................................................................................57
CHƢƠNG 4: ỨNG DỤNG MINH HỌA .................................................................68
4.1. Các yêu cầu cho ứng dụng .............................................................................68
4.2. Giải pháp cho ứng dụng .................................................................................69
4.3. Các kết quả đạt đƣợc ......................................................................................73
4.3.1. So sánh kết quả thực thi trên môi trƣờng thực và giả lập Simgrid .........73
4.3.2. So sánh thời gian tính toán, thời gian giả lập khi số tiến trình chạy song
song khác nhau ..................................................................................................73
4.3.3. So sánh thời gian tính toán, thời gian giả lập khi kích thƣớc ma trận khác
nhau ...................................................................................................................74
4.3.4. So sánh thời gian tính toán, thời gian giả lập khi sử dụng các loại
topology khác nhau ...........................................................................................74
3
KẾT LUẬN ...........................................................................................................76
TÀI LIỆU THAM KHẢO .....................................................................................78
4
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.
5
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
STT Từ viết tắt Giải nghĩa
1 Interconnection Mạng liên kết, mạng kết nối
network
2 OCNs On-chip networks
3 SANs System/storage area networks
4 DSN Distributed Shortcut Networks
5 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
6 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
6
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1: Mô hình mức cao của mạng liên kết ............................................................11
Hình 2: Các lĩnh vực ứng dụng của mạng liên kết ....................................................13
Hình 3: Các cấu hình mạng cơ bản ...........................................................................17
Hình 4: Mạng liên kết 2D-Torus gồm 4x4 nút mạng ................................................18
Hình 5: Ví dụ về định tuyến trên mạng kết 2D-Torus ..............................................20
Hình 6: Ví dụ về tắc nghẽn của Wormhole switching ..............................................23
Hình 8: Tƣơng quan giữa latency và offered traffic .................................................27
Hình 9: Minh họa mô hình phòng mạng ...................................................................30
Hình 10: Minh họa tính độ dài dây mạng .................................................................31
Hình 11: Giả code tính năng lƣợng tiêu thụ của mạng liên kết ................................33
Hình 12: Mô hình mạng liên kết bằng đồ thị có trọng số .........................................35
Hình 13: Mô hình hoạt động của SimGrid ................................................................41
Hình 14: So sánh về thông lƣợng với công cụ GTNetS, SSFNet, NS2 ....................45
Hình 15: So sánh thời gian thực thi với công cụ GTNetS (nguồn [14]) ...................46
Hình 16: Một mạng minh họa đơn giản ....................................................................54
Hình 17: Kiến trúc Simgrid .......................................................................................58
Hình 18: Minh họa đồ thị DAG ................................................................................59
Hình 19: Kết quả so sánh khi chạy ứng dụng mô phỏng bằng MSG sử dụng các
ngôn ngữ C, Java (nguồn [18]) .................................................................................65
Hình 20: Chạy SMPI ở chế độ lƣu vết và xem hình ảnh kết quả sử dụng ứng dụng
tiện ích Vite hoặc Viva ..............................................................................................66
Hình 21: Sự khác nhau giữa MPI và SMPI ở môi trƣờng giả lập.............................66
7
Hình 22: Hoạt động diễn ra bên trong Simgrid sau khi đƣợc khởi tạo. Một luồng
đƣợc tạo ra bởi SIMIX ứng với mỗi tiến trình của ngƣời dùng. Một mô hình giả lập
các tài nguyên, nền tảng đƣợc tạo ra bởi lõi giả lập Surf ..........................................67
Hình 23: Luồng công việc giả lập bên trong Simgrid. Surf thực hiện ƣớc đoán thời
gian cho các hoạt động và trả lại thông tin đầu ra.....................................................67
Hình 24: Minh họa một Server room ........................................................................68
Hình 25: Một số kiểu topology 3D torus (4,4,4) ......................................................69
8
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ô
9
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”.
10
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
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
11
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 (high-
performance 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-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 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ớ (processor-
memory) 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
12
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
13
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ể
14
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 Mô tả
Random λsd = 1/N
Permutation d = π(s)
Bit permutation di = sf(i) ⊕ g(i)
Bit complement di =¬si
Bit reverse di = sb-i-1
Bit rotation di = si+1 mod b
Shuffle di = si-1 mod b
Transpose di = si+b/2 mod b
Digit permutations dx = f(sg(x))
Tornado dx = sx + (k/2-1) mod k
Neighbor 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ó.
15
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.
16
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
17
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à k-
ary 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
18
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 non-
minimal. 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
19
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
20
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
Danh mục các ký hiệu, các chữ viết tắt .......................................................................6
Danh mục các hình vẽ, đồ thị ......................................................................................7
MỞ ĐẦU .....................................................................................................................9
CHƢƠNG 1: CƠ SỞ LÝ THUYẾT .........................................................................11
1.1. Tổng quan về mạng liên kết (Interconnection Network) ...............................11
1.1.1. Khái niệm, ứng dụng của mạng liên kết .................................................11
1.1.2. Các thành phần cơ bản trong mạng liên kết ............................................13
1.2. Tổng quan về cấu hình mạng .........................................................................15
1.3. Tổng quan về giải thuật định tuyến trên mạng...............................................18
1.4. Tổng quan về điều khiển luồng ......................................................................20
1.5. Hiệu năng của mạng liên kết ..........................................................................23
1.5.1. Thông lƣợng (Throughput) .....................................................................23
1.5.2. Độ trễ (Latency) ......................................................................................25
CHƢƠNG 2: PHƢƠNG PHÁP ĐÁNH GIÁ MẠNG LIÊN KẾT ...........................28
2.1. Đánh giá chi phí .............................................................................................28
2.1.1. Chi phí thiết lập mạng .............................................................................28
2.1.2. Chi phí vận hành mạng ...........................................................................32
2.2. Đánh giá hiệu năng mạng liên kết bằng lý thuyết đồ thị ...............................33
2.2.1. Đánh giá thông lƣợng lý tƣởng bằng lý thuyết đồ thị .............................33
2.2.2. Đánh giá độ trễ bằng lý thuyết đồ thị ......................................................35
2.2.3. Đánh giá khả năng chịu lỗi bằng lý thuyết đồ thị ...................................37
2.3. Đánh giá hiệu năng mạng liên kết bằng công cụ mô phỏng ..........................37
2
2.3.1. Phƣơng pháp đánh giá hiệu năng bằng công cụ mô phỏng ....................37
2.4. Đánh giá hiệu năng của ứng dụng ..................................................................38
2.4.1. Phƣơng pháp đánh giá .............................................................................38
2.4.2. Công cụ mô phỏng ..................................................................................41
CHƢƠNG 3: CÔNG CỤ MÔ PHỎNG SIMGRID ..................................................43
3.1. Giới thiệu sơ lƣợc về các công cụ mô phỏng mạng .......................................43
3.2. Tổng quan về kỹ thuật mô phỏng...................................................................46
3.2.1 Hệ thống, mô hình và mô phỏng ..............................................................46
3.2.2 Các bƣớc trong mô phỏng một hệ thống ..................................................49
3.3. Công cụ mông phỏng Simgrid .......................................................................51
3.3.1. Tổng quan về Simgrid .............................................................................51
3.3.2. Cấu hình căn bản cho các ứng dụng Simgrid..........................................52
3.3.3 Kiến trúc Simgrid .....................................................................................57
CHƢƠNG 4: ỨNG DỤNG MINH HỌA .................................................................68
4.1. Các yêu cầu cho ứng dụng .............................................................................68
4.2. Giải pháp cho ứng dụng .................................................................................69
4.3. Các kết quả đạt đƣợc ......................................................................................73
4.3.1. So sánh kết quả thực thi trên môi trƣờng thực và giả lập Simgrid .........73
4.3.2. So sánh thời gian tính toán, thời gian giả lập khi số tiến trình chạy song
song khác nhau ..................................................................................................73
4.3.3. So sánh thời gian tính toán, thời gian giả lập khi kích thƣớc ma trận khác
nhau ...................................................................................................................74
4.3.4. So sánh thời gian tính toán, thời gian giả lập khi sử dụng các loại
topology khác nhau ...........................................................................................74
3
KẾT LUẬN ...........................................................................................................76
TÀI LIỆU THAM KHẢO .....................................................................................78
4
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.
5
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
STT Từ viết tắt Giải nghĩa
1 Interconnection Mạng liên kết, mạng kết nối
network
2 OCNs On-chip networks
3 SANs System/storage area networks
4 DSN Distributed Shortcut Networks
5 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
6 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
6
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1: Mô hình mức cao của mạng liên kết ............................................................11
Hình 2: Các lĩnh vực ứng dụng của mạng liên kết ....................................................13
Hình 3: Các cấu hình mạng cơ bản ...........................................................................17
Hình 4: Mạng liên kết 2D-Torus gồm 4x4 nút mạng ................................................18
Hình 5: Ví dụ về định tuyến trên mạng kết 2D-Torus ..............................................20
Hình 6: Ví dụ về tắc nghẽn của Wormhole switching ..............................................23
Hình 8: Tƣơng quan giữa latency và offered traffic .................................................27
Hình 9: Minh họa mô hình phòng mạng ...................................................................30
Hình 10: Minh họa tính độ dài dây mạng .................................................................31
Hình 11: Giả code tính năng lƣợng tiêu thụ của mạng liên kết ................................33
Hình 12: Mô hình mạng liên kết bằng đồ thị có trọng số .........................................35
Hình 13: Mô hình hoạt động của SimGrid ................................................................41
Hình 14: So sánh về thông lƣợng với công cụ GTNetS, SSFNet, NS2 ....................45
Hình 15: So sánh thời gian thực thi với công cụ GTNetS (nguồn [14]) ...................46
Hình 16: Một mạng minh họa đơn giản ....................................................................54
Hình 17: Kiến trúc Simgrid .......................................................................................58
Hình 18: Minh họa đồ thị DAG ................................................................................59
Hình 19: Kết quả so sánh khi chạy ứng dụng mô phỏng bằng MSG sử dụng các
ngôn ngữ C, Java (nguồn [18]) .................................................................................65
Hình 20: Chạy SMPI ở chế độ lƣu vết và xem hình ảnh kết quả sử dụng ứng dụng
tiện ích Vite hoặc Viva ..............................................................................................66
Hình 21: Sự khác nhau giữa MPI và SMPI ở môi trƣờng giả lập.............................66
7
Hình 22: Hoạt động diễn ra bên trong Simgrid sau khi đƣợc khởi tạo. Một luồng
đƣợc tạo ra bởi SIMIX ứng với mỗi tiến trình của ngƣời dùng. Một mô hình giả lập
các tài nguyên, nền tảng đƣợc tạo ra bởi lõi giả lập Surf ..........................................67
Hình 23: Luồng công việc giả lập bên trong Simgrid. Surf thực hiện ƣớc đoán thời
gian cho các hoạt động và trả lại thông tin đầu ra.....................................................67
Hình 24: Minh họa một Server room ........................................................................68
Hình 25: Một số kiểu topology 3D torus (4,4,4) ......................................................69
8
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ô
9
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”.
10
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
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
11
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 (high-
performance 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-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 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ớ (processor-
memory) 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
12
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
13
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ể
14
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 Mô tả
Random λsd = 1/N
Permutation d = π(s)
Bit permutation di = sf(i) ⊕ g(i)
Bit complement di =¬si
Bit reverse di = sb-i-1
Bit rotation di = si+1 mod b
Shuffle di = si-1 mod b
Transpose di = si+b/2 mod b
Digit permutations dx = f(sg(x))
Tornado dx = sx + (k/2-1) mod k
Neighbor 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ó.
15
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.
16
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
17
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à k-
ary 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
18
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 non-
minimal. 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
19
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
20