I

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TRẦN TRỌNG TẤN

ĐIỀU KHIỂN TẮC NGHẼN TRÊN MẠNG
NGANG HÀNG CÓ CẤU TRÚC LUẬN VĂN THẠC SĨ

Ngành: Công nghệ Thông tin
Chuyên ngành: Truyền dữ liệu và mạng máy tính
Mã số: 60 48 15
LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Nguyễn Hoài Sơn

HÀ NỘI - 2011
III
3.4. Phương pháp định tuyến thích nghi 31
Chương 4. Điều khiển tắc nghẽn sử dụng phương pháp thay đổi bảng định tuyến
34
4.1. Đề xuất phương pháp 34
4.2. Nội dung chi tiết 34
4.2.1. Phát hiện tắc nghẽn. 34
4.2.2. Xử lý trong trường hợp có tắc nghẽn 35
4.2.3. Xử lý khi hết tắc nghẽn 36
4.3. Ví dụ minh họa 37
4.4. Nhận xét về phương pháp 39
5. Mô phỏng và kết quả 41
5.1. Mô phỏng 41
5.1.1. Chương trình mô phỏng 41
IV
5.1.2. Các thay đổi đã áp dụng 44
5.2. Kết quả 45
5.2.1. So sánh với mô hình Chord chuẩn 45
5.2.2. Đánh giá hiệu năng khi tiến hành tùy chỉnh các tham số và cải tiến
phương pháp 47
6. Kết luận và hướng phát triển 50

V
Danh mục hình ảnh
Hình 1: Mạng ngang hàng phân tán hoàn toàn 4

38
Hình 19: Mô hình mạng mô phỏng 41
Hình 20: Mô hình lớp Node 42
Hình 21: Biểu đồ số lượng gói tin bị loại bỏ khi áp dụng và không áp dụng việc
điều khiển tắc nghẽn 45
Hình 22: Biểu đồ thể hiện số gói tin trung bình phải sử dụng với mỗi truy vấn
thành công 46
Hình 23: Ảnh hưởng của việc thay đổi giá trị xác định mức độ tắc nghẽn mềm của
nút 47
Hình 24: Ảnh hưởng của số lượng nút được khôi phục bảng định tuyến lên hiệu
năng của hệ thống 48
Hình 25: Hiệu năng của hệ thống thay đổi khi cải tiến phương pháp điều khiển tắc
nghẽn. 48

1
Mở đầu
Ngày nay với mức độ phổ biến của máy tính cá nhân và mạng Internet,
mạng ngang hàng với nhiều đặc tính phù hợp cho các hệ thống phân tán, ngày
càng thu hút được nhiều chú ý của người sử dụng và giới nghiên cứu phát triển
ứng dụng. Cùng với xu thế đó mô hình mạng ngang hàng có cấu trúc cũng dành
được nhiều sự quan tâm và phát triển do đặc điểm là mạng ngang hàng thuần
túy, không yêu cầu có sự tham gia của các máy chủ trung tâm. Đặc điểm này
giúp mạng ngang hàng cấu trúc có khả năng mở rộng tốt hơn, loại bỏ các single-
point-of-failure, tuy nhiên cũng tạo ra nhiều các vấn đề kỹ thuật cần phải giải
quyết.
Rất nhiều ứng dụng phức tạp đã được phát triển trên nền tảng mạng ngang
hàng có cấu trúc như các hệ thống truy vấn dữ liệu, hay hệ thống quản trị cơ sở

Kết quả thu được cho thấy, việc sử dụng giải pháp đã xử lý được vấn đề tắc
nghẽn cục bộ qua đó nâng cao được thông lượng đạt được trên toàn hệ thống.
Khóa luận có cấu trúc như sau:
 Chương 1: Giới thiệu tổng quan về mạng ngang hàng, mạng ngang hàng
có cấu trúc cụ thể là mô hình Chord.
 Chương 2: Trình bày vấn đề điều khiển tắc nghẽn trong mạng ngang hàng
có cấu trúc và tầm quan trọng của nó. Phân tích quá trình sụp đổ của
mạng do tắc nghẽn.
 Chương 3: Trình bày các nghiên cứu liên quan. Phân tích ưu nhược điểm
của các phương pháp đã đưa ra.
 Chương 4: Đề xuất và phân tích giải pháp điều khiển tắc nghẽn dựa trên
việc thay đổi bảng định tuyến.
 Chương 5: Xây dựng chương trình mô phỏng và các kết quả đã đạt được.
 Chương 6: Kết luận và hướng phát triển nhằm giải quyết những tồn đọng
và cải tiến giải pháp đã đưa ra.
3
Chương 1. Tổng quan
1.1. Mạng ngang hàng
Mạng ngang hàng được định nghĩa như sau: một cấu trúc mạng phân tán,
nếu như các thành phần tham gia chia sẻ tài nguyên của chúng (như khả năng
tính toán của vi xử lý, dung lượng lưu trữ, đường truyền…). Các tài nguyên
được chia sẻ này dùng để cung cấp các dịch vụ và nội dung. Chúng được truy
cập một các trực tiếp bởi các nút khác, không thông qua các nút trung gian. Các
thành phần tham gia trong mạng vừa đóng vai trò cung cấp tài nguyên và yêu
cầu tài nguyên.[6]
Ta có thể phân biệt mô hình mạng ngang hàng với mô hình khách chủ thông qua
vai trò của các thành phần tham gia trong mạng. Mỗi thành phần trong mạng

hình phân tán hoàn toàn. Tuy nhiên có một số nút đóng vai trò quan trong
hơn các nút khác, trở thành các điểm điều phối cho một số các nút khác.
Các nút này được gọi là siêu nút (supernode) và chúng có thể đảm nhận
các vai trò khác nhau tùy thuộc vào từng thiết kế.

Hình 2: Mạng ngang hàng phân tán một phần

Có một điểm quan trọng cần lưu ý là hệ thống sẽ không lệ thuộc vào một
nút nào, dù nút đó có là supernode, do các nút này được gán động và nếu
có lỗi sẽ được thay thế bằng nút khác.
5
Mô hình phân tán lai: Trong những hệ thống này, tồn tại một máy chủ
trung tâm đóng vai trò duy trì thông tin về các nút và tài nguyên trên các
nút. Hình 3: Mạng ngang hàng lai

Mặc dù việc trao đổi tài nguyên có thể thực hiện trực tiếp giữa các nút,
nhưng máy chủ trung tâm sẽ đóng vai trò tổng hợp và tìm kiếm tài nguyên
trên nút. Về cơ bản mô hình này sẽ xuất hiện single point of failure chính
là máy chủ trung tâm. Mô hình này sẽ khó mở rộng, và tạo các nguy hiểm
tiềm tàng cho hệ thống khi máy chủ trung tâm có sự cố hoặc bị tấn công.
1.1.2. Cấu trúc mạng
Cấu trúc ở đây mang nghĩa xác định rõ việc hình thành mạng phủ, cũng như việc
nút và các tài nguyên được đưa vào mạng có theo một quy luật nhất định nào đó
không. Nhờ đó ta phân loại ra như sau

Để khắc phục nhược điểm này ta sử dụng mạng có cấu trúc với kĩ thuật bảng
băm phân tán (DHT). [9]
Bảng băm phân tán là một hệ thống phân tán cung cấp chức năng tìm kiếm
tương tự như bảng băm thông thường. Một cặp khóa và giá trị được lưu trong
DHT và bất cứ nút nào tham gia vào hệ thống cũng có thể lấy được giá trị ứng
với một khóa xác định. Việc duy trì bảng ánh xạ giữa khóa và các giá trị được
lưu phân tán trên các nút, do đó việc thay đổi của một số nút tham gia vào hệ
thống sẽ chỉ ảnh hưởng đến một số nhỏ các khóa liên quan. Điều này giúp cho
DHT có thể dễ dàng mở rộng với số lượng lớn nút tham gia, và cung cấp khả
năng duy trì hệ thống khi có nút tham gia, rời khỏi mạng, hay bị lỗi.
7

Hình 4: Bảng băm phân tán – DHT

1.2.1. Đặc điểm của DHT
Các đặc điểm của DHT có thể tóm tắt như sau:
 Phân tán: DHT là tập hợp các nút mà không cần bất kì một máy trung tâm nào.
 Chống lỗi: hệ thống hoạt động được trong trường hợp các nút liên tục ra, vào,
hoặc bị lỗi
 Khả năng mở rộng: hệ thống hoạt động ổn định khi có số lượng lớn các nút
tham gia.
Để đạt được các đặc điểm mô tả ở trên kỹ thuật được sử dụng chủ yếu là mỗi nút
phải có liên hệ, trao đổi với một số nút khác có trong mạng – thông thường là
O(log n) với mạng có n nút tham gia. Do đó chỉ cần một số ít điều chỉnh khi có
sự thay đổi về các nút tham gia mạng.
Ngoài ra một hệ thống DHT cũng như bất kỳ hệ thống phân tán khác còn cần
phải quan tâm đến các vấn đề như chống tấn công từ bên trong hay ngoài hệ

,k
2
) để tính khoảng
cách giữa hai khóa k
1
và k
2
. Khoảng cách này không liên quan gì đến khoảng
cách vật lý hay độ trễ của mạng. Mỗi nút được gán cho một khóa định danh ID.
Một nút với ID là i
x
sẽ có trách nhiệm lưu trữ với tất cả các khóa k
m
nếu như i
x
là
định danh nút gần nhất với các khóa đó, tính toán bằng hàm δ(k
1
,k
2
). Phương
pháp consistent hashing có một tính chất cần thiết cho DHT đó là khi có sự thêm
bớt một nút trong mạng chi có những khóa thuộc nút đó mới cần chuyển sang
các nút lân cận, trong khi không tác động gì đến các nút khác. Điểm này hoàn
toàn khác biệt với phương pháp bảng băm thông thường, khi thay đổi một phần
sẽ khiến cho gần như toàn bộ không gian khóa phải tính toán lại. Do việc chuyển
đổi khóa từ nút này sang nút khác yêu cầu lượng băng thông trong việc chuyển
đổi các dữ liệu, do đó để đáp ứng điều kiện mạng có nhiều biến động (nút ra vào
với tần suất cao) thì việc có ít thay đổi lên cấu trúc mỗi khi có thay đổi là yêu
cầu cấp thiết.

nút do mỗi nút được gán với một số lượng key tương đương nhau. Việc tham gia
và rời khỏi mạng sẽ chỉ khiến cho một số nhỏ các key chuyển từ nút này sang
nút khác. Đặc điểm khiến Chord trở nên thông dụng chính là khả năng mở rộng
mạng. Trong khi với các thuật toán trước đó một nút cần phải duy trì thông tin
về nhiều nút khác trong mạng thì Chord chỉ cần một số lượng cố định. Chính
điều này giúp cho Chord có thể hoạt động hiệu quả trong mạng có số lượng các
nút lớn.
Chord được đưa ra nhằm giải quyết các vấn đề thường gặp trong mạng ngang
hàng:
 Cân bằng tải: Chord đóng vai trò phân phối khóa đến từng nút với số
lượng đồng đều, thông qua đó gián tiếp mang lại hiệu quả cân bằng tải.
 Tính phân tán: Chord là hệ thống phân tán hoàn toàn: trong mạng
không có nút nào đóng vai trò quan trọng hơn các nút khác. Điều này
nâng cao tính ổn định và khiến Chord có thể đáp ứng các ứng dụng
ngang hàng trong môi trường mạng không ổn định.
 Khả năng mở rộng: Độ phức tạp của một truy vấn trong mạng Chord
tăng lên ứng với log của số lượng các nút, do đó có thể đáp ứng cả với
những hệ thống rất lớn.
10
 Khả năng chịu lỗi: Chord có khả năng tự điều chỉnh các bảng định
tuyến trên mỗi nút tương ứng với sự ra vào của các nút, cũng như khi
có một nút đột ngột rời khỏi mạng. Chord đảm bảo trong bất kỳ môi
trường mạng nào với mỗi một khóa bất kỳ đều có một nút tương ứng,
chịu trách nhiệm về khóa đó. Điều này luôn đúng dù trạng thái của hệ
thống liên tục thay đổi.
 Khả năng đặt tên linh hoạt: Chord không có bất kỳ rằng buộc nào trên
cấu trúc khóa mà nó tìm kiếm. Điều này cung cấp cho các ứng dụng sử
Hình 5: Mô hình vòng Chord với khóa có chiều dài 6 bit

Trong hình 5 là vòng Chord với m=6. Vòng Chord có chứa 10 nút và 5 khóa.
Successor của định danh 10 là nút 14 do đó key 10 sẽ được đặt ở nút 14. Tương
tự khóa 24 và 30 sẽ được đặt ở nút 32, khóa 38 tại nút 38 và khóa 54 tại nút 56.
Kĩ thuật consistent hashing được thiết kế để việc các nút tham gia hay rời khỏi
mạng sẽ tạo ra ít ảnh hưởng nhất. Để duy trì bảng mapping khi một nút n tham
gia vào mạng, một số khóa trước đây được đặt tại successcor của n sẽ chuyển
sang cho nút n. Trong ví dụ trên, nếu có một nút với định danh 26 tham gia vào
mạng, nó sẽ nhận được khóa 24 chuyển từ nút 32.
Successor của một nút là nút tiếp sau nút đó trên vòng Chord, predecessor là nút
liền trước trên vòng Chord.
1.3.2. Tìm kiếm trong mạng Chord
Tìm kiếm đơn giản: Đây là thuật toán tìm kiếm đơn giản nhất trong
Chord. Thuật toán này chỉ yêu cầu các nút biết được successor của mình. Truy
vấn cho một định danh được chuyển xung quanh vòng Chord qua các nút
successor cho đến khi gặp nút có chứa khóa với định danh cần tìm.
12

Hình 6: Quá trình tìm kiếm đơn giản trên Chord

Trong hình 6 là ví dụ khi nút 8 thực hiện truy vấn cho khóa có định danh 54. Nút
8 gọi hàm find_successor cho khóa 54, kết quả trả về là nút 56 – successor của
khóa 54 này. Truy vấn được chuyển lần lượt qua tất cả các nút trên vòng nằm
giữa nút 8 và 56.

) mod 2
6
= 40. Có thể dễ nhận xét thấy với các
thiết lập như vậy: một nút chỉ lưu thông tin về một số giới hạn các nút có trong
mạng, một nút cũng chỉ biết đến một số nút nằm gần với nó. Một nút cũng
không lưu trữ đủ thông tin để có thể ngay lập tức tìm được successor của một
khóa k.

Hình 8: Giả mã của phương pháp tìm kiếm cải tiến

Hình 8 thể hiện đoạn giả mã ứng với việc thực hiện tìm kiếm successor của key
id có sử dụng bảng finger. Nếu id nằm giữa n và successor của nó,
find_successor sẽ trả lại successor của nó. Nếu không n tìm kiếm trong bảng
14
finger cho nút n‟ – có định danh ngay sau id cần tìm kiếm và thực hiện hàm
find_successor trên nút n‟.

Hình 9: Quá trình tìm kiếm khóa 54 trên nút 8

Như hình 9 ở trên nút 8 tìm kiếm successor của khóa 54. Qua bảng finger của
nút 8 ta thấy nút 42 là nút gần khóa cần tìm kiếm nhất, nên nút 8 sẽ thông qua
nút 42, tương tự query sẽ chuyển qua nút 51 và đến đích là nút 56.
Có thể chứng minh được định lý có nội dung như sau: Với xác suất cao số nút
cần thông qua để tìm kiếm successor trong một mạng N nút là O(log N) [7]

1.3.3. Quá trình tham gia và ổn định mạng
Trên thực tế, mạng Chord cần phải giải quyết các vấn đề như việc một nút

Chương 2. Vấn đề điều khiển tắc nghẽn trong mạng ngang
hàng có cấu trúc
2.1. Tắc nghẽn và tầm quan trọng của việc điều khiển tắc nghẽn
trong mạng ngang hàng có cấu trúc
Mạng ngang hàng có cấu trúc được xây dựng với mục đích đáp ứng được
nhu cầu mở rộng về số lượng node, khóa cũng như khả năng đáp ứng của toàn
mạng. Đối với một hệ thống chia sẻ file đơn giản khi mỗi node chỉ phải đáp ứng
số lượng nhỏ query và chỉ phải index một số giới hạn các tập tin, hệ thống có thể
hoạt động tốt với thiết kế ban đầu. Tuy nhiên trong thời gian gần đây, mạng
ngang hàng có cấu trúc được phát triển để có thể phục vụ cho các ứng dụng có
độ phức tạp cao, ví dụ như hệ thống truy vấn thông tin (P2P Information
Retrieval – P2P-IR) [8] hay hệ thống quản trị cơ sở dữ liệu (P2P Database
Management Systems - P2P-DBMS) [2]. Các ứng dụng ở lớp trên này tạo lượng
truy vấn lớn hơn rất nhiều, ví dụ: với một hệ thống chia sẻ file đơn giản các nút
chỉ phải đánh index và tạo một số lượng khóa nhỏ lấy từ tên của các file, với
một hệ thống truy vấn sử dụng kĩ thuật tìm kiếm full-text số lượng khóa phải
index và đưa vào mạng là vài nghìn với một văn bản.
Trong DHT, cụ thể ở đây là mạng Chord một nút đảm nhận hai chức năng chính
là trả lời truy vấn và chuyển tiếp truy vấn đến nút khác, do đó khi một nút có
vấn đề cũng có thể gây ảnh hưởng tới nhiều nút khác trong mạng. Thông thường
các nút trong mạng có cấu hình phần cứng và băng thông mạng rất đa dạng, do
đó khả năng đáp ứng truy vấn của từng nút cũng hoàn toàn khác nhau. Ngoài ra
với mạng ngang hàng thường xảy ra tình trạng một số lượng tài nguyên được
truy vấn với tần suất cao, chỉ trong một khoảng thời gian nhất định. Những đặc
điểm trên khiến cho mạng ngang hàng có cấu trúc dễ xảy ra tình trạng tắc nghẽn
và có thể gây ảnh hưởng rộng trên toàn mạng. Tắc nghẽn trong DHT thường bắt
đầu khi một nút nhận được số truy vấn vượt quá khả năng xử lý của nó, nếu

phải xử lý và so sánh với khả năng của nút đã được cho trước: c, qua đó ta có thể
tính p và thông lượng đạt được A là một hàm của x. p là đại lượng không thứ
nguyên, còn x,O và A có đơn vị là số truy vấn/giây.

2.2.2. Định nghĩa
Thông lượng đến: Mỗi nút khởi tạo các truy vấn, được chuyển qua các nút
trong mạng. Để tính tổng tải đến O trước hết ta định nghĩa thông lượng đến
o
d
h
là thông lượng đến với đích là d trước khi qua h nút. Như đã giả thiết ở
trên, các nut có cùng khả năng đáp ứng truy vấn, và các nút cùng khởi tạo một
số lượng truy vấn. Do đó, thông lượng đến độc lập với nguồn sinh truy vấn.
Để đơn giản ta xét một mạng Chord nhỏ, tuy nhiên kết quả sẽ vẫn đúng cho bất
kì mạng DHT log n nào.
18

Hình 10: (a) tải đến các nút tạo bởi P
0
, (b) Tải tới và rời khỏi nút

Hình 10a thể hiện thông lượng đến các nút khác được sinh bởi nút P
0
.
Mỗi nút có log
2
n = l (ở đây n=8 và l=3) mục trong bảng định tuyến, mỗi mục

1
≤ o
7
1
là thông lượng với đích là nút 7 sau khi qua nút đầu tiên, ứng
với thông lượng tới nút 4.
Xác suất xử lý: thông lượng đã xử lý được định nghĩa bởi công thức:
p= min (1, c/O) (1)
ở đó c là khả năng xử lý của nút và O là tổng tải đến. Khi một nút không quá tải
O≤c tất cả thông lượng tới đều được xử lý, khi đó p=1, ngược lại p <1. Giả sử
nếu thông lượng đến lớn gấp 2 lần khả năng xử lý của nút thì khi đó xác suất xử
lý là 0.5.
19
Nếu truy vấn đến nút đích đi qua một số các nút, tại các nút tiếp theo thông
lượng đến được tính theo công thức:
(2)
2.2.3. Các mô hình
Mỗi nút phải xử lý các truy vấn đến và đi hình 10b: truy vấn đến bao gồm
tổng thông lượng tới O
final,
được xử lý bởi ứng dụng phía trên và thông lượng
truyền qua O
rel
là các truy vấn được chuyển đến các nút khác. Ta xet hai trường
hợp tắc nghẽn:
Trường hợp 1: Đường truyền lên (uplink) là bottleneck: Trên thực tế rất nhiều
máy tính cá nhân có đường truyền bất đối xứng với tốc độ download lớn hơn tốc

= 1/8 · x (3)
Ta sẽ tính tổng thông lượng O đến mỗi nút sinh bởi P
0
. Sử dụng công thức 2 và
3 ta có:
Thông lượng tạo bởi ứng dụng đến tất cả các đích trong mạng DHT trước khi
qua nút đầu tiên:

Thông lượng đạt được tại tất cả các đích sau khi đi qua nút cuối cùng, được xử
lý bởi ứng dụng và không chuyển tiếp nữa được tính bởi công thức:

Thông lượng chuyển tiếp được chuyển qua các nút lân cận được tính bởi công
thức:

Thông lượng đến và đi có thể được tính như sau:

Với trường hợp có n nút: với bất kỳ mạng DHT log n nào với n=2
l
trong đó mỗi
nút có l=log
2
n liên kết đến các nút khác trong mạng. Tổng tải trên mỗi nút với
đích đến là d ở nút đầu tiên là:
∀ d, 0 < d < n, o
d
1
= x/n = x/2
l

Chúng ta có các tổng tải tương ứng là: