Điều khiển tắc nghẽn trên mạng ngang hàng có cấu trúc

  • 56 trang
  • file .pdf
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Ĩ
HÀ NỘI - 2011
II
ĐẠ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
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
Mục lục
Mở đầu ..................................................................................................................... 1
Chương 1. Tổng quan .............................................................................................. 3
1.1. Mạng ngang hàng......................................................................................... 3
1.1.1. Mức độ phân tán .................................................................................... 3
1.1.2. Cấu trúc mạng ........................................................................................ 5
1.2. Mạng ngang hàng có cấu trúc ....................................................................... 6
1.2.1. Đặc điểm của DHT ................................................................................ 7
1.2.2. Cấu trúc hệ thống ................................................................................... 7
1.3. Mạng Chord .................................................................................................. 9
1.3.1. Mô hình của Chord .............................................................................. 10
1.3.2. Tìm kiếm trong mạng Chord ............................................................... 11
1.3.3. Quá trình tham gia và ổn định mạng ................................................... 14
Chương 2. Vấn đề điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc ...... 16
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 ...................................................................................... 16
2.2. Phân tích quá trình sụp đổ do tắc nghẽn trong mạng ngang hàng có cấu trúc
............................................................................................................................ 17
2.2.1. Khái quát .............................................................................................. 17
2.2.2. Định nghĩa............................................................................................ 17
2.2.3. Các mô hình ......................................................................................... 19
2.2.4. Tổng tải đến O ..................................................................................... 19
2.2.5. Ví dụ với một triệu nút ........................................................................ 22
2.2.6. Phân tích các trạng thái tiệm cận của A. .............................................. 22
2.2.7. Kết luận ................................................................................................ 25
Chương 3. Các nghiên cứu về điều khiển tắc nghẽn trên DHT ............................. 26
3.1. Phương pháp CSCC .................................................................................... 26
3.2. Phương pháp BPCC .................................................................................... 27
3.3. Phương pháp Marking ................................................................................ 28
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
Hình 2: Mạng ngang hàng phân tán một phần ......................................................... 4
Hình 3: Mạng ngang hàng lai .................................................................................. 5
Hình 4: Bảng băm phân tán – DHT ......................................................................... 7
Hình 5: Mô hình vòng Chord với khóa có chiều dài 6 bit ..................................... 11
Hình 6: Quá trình tìm kiếm đơn giản trên Chord .................................................. 12
Hình 7: Bảng finger của nút 8 ................................................................................ 13
Hình 8: Giả mã của phương pháp tìm kiếm cải tiến .............................................. 13
Hình 9: Quá trình tìm kiếm khóa 54 trên nút 8 ..................................................... 14
Hình 10: (a) tải đến các nút tạo bởi P0, (b) Tải tới và rời khỏi nút ................... 18
Hình 11: Thông lượng đạt được so sánh với tốc độ truy vấn cho hệ thống DHT với
một triệu nút trong hai trường hợp tắc nghẽn M1 và M2. Mạng DHT sụp đổ khi
tải tới đạt đến giá trị xopt ......................................................................................... 22
Hình 12: Phương pháp CSCC ................................................................................ 26
Hình 13: Phương pháp BPCC ................................................................................ 28
Hình 14: Mạng DHT với 8 nút. ............................................................................. 31
Hình 15: Truy vấn thông thường trên mạng Chord (m=8). ................................... 37
Hình 16: Bảng định tuyến ban đầu của nút P8 ....................................................... 38
Hình 17: Bảng định tuyến của nút P8 khi xảy ra tình trạng tắc nghẽn trên nút P42.
................................................................................................................................ 38
Hình 18: Truy vấn được thay đổi đường đi khi áp dụng giải pháp chống tắc nghẽn
................................................................................................................................ 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ở
dữ liệu… Các ứng dụng phức tạp này với số lượng thông điệp được chuyển tải
trong mạng là vô cùng lớn sẽ gây khó khăn cho việc duy trì hệ thống hoạt động
một cách hiệu quả. Thêm nữa mạng ngang hàng nói chung và mạng ngang hàng
có cấu trúc nói riêng thường xuyên xuất hiện việc một số tài nguyên được truy
vấn nhiều lần trong một khoảng thời gian nhất định, do đó có thể gây tăng vọt số
lượng truy vấn trên một số nút trên mạng. Khi trong mạng tồn tại nút có số
lượng truy vấn tới cao hơn khả năng xử lý của nó sẽ gây ra tình trạng tắc nghẽn
cục bộ trên nút. Nếu như không có những cơ chế điều khiển tắc nghẽn hợp lý sẽ
dẫn đến việc tắc nghẽn lan rộng trên mạng và có thể gây sụp đổ mạng. Điều này
có thể gây cản trở đến việc sử dụng mạng ngang hàng có cấu trúc trong các ứng
dụng ở môi trường thực tế nơi các nút tham gia mạng có khả năng xử lý và
đường truyền rất đa dạng. Do đó việc tạo ra một cơ chế điều khiển tắc nghẽn
hiệu quả là nhu cầu thiết yếu với bất kỳ hệ thống mạng ngang hàng có cấu trúc
nào.
Luận văn này thông qua việc tìm hiểu về mạng ngang hàng có cấu trúc
(cụ thể là mô hình mạng Chord) và phân tích quá trình sụp đổ do tắc nghẽn sẽ
nêu bật tầm quan trọng của việc điều khiển tắc nghẽn. Khóa luận còn tìm hiểu
các nghiên cứu có liên quan trước đây, phân tích ưu nhược điểm của chúng
nhằm đề xuất một phương pháp điều khiển tắc nghẽn, bổ sung cho các phương
pháp đã có. Phương pháp này sử dụng việc thay đổi bảng định tuyến của các nút
trong mạng, nhằm chuyển hướng các thông điệp tránh khỏi những nút đang tắc
nghẽn và đi qua những nút còn khả năng phục vụ. Đồng thời giảm thiểu số
lượng thông tin và thông điệp phát sinh từ quá trình điều khiển tắc nghẽn này,
2
cũng như không tạo lên các thay đổi quá lớn trong việc tổ chức và định tuyến so
với mô hình mạng ban đầu.
Giải pháp đã được thử nghiệm trên chương trình mô phỏng mạng Chord.
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
ngang hàng có thể được gọi là Servent được tạo nên từ hai phần: Serv trong từ
server (máy chủ) và ent trong từ client (máy khách), nhằm thể hiện khả năng của
một nút trong mạng ngang hàng có thể vừa đóng cả hai vai trò máy chủ và máy
khách trong cùng một thời điểm. Điều này hoàn toàn khác biệt với môi hình
khách chủ khi nút tham gia chỉ có thể đóng một trong hai vai trò, hoặc máy
khách, hoặc máy chủ tại một thời điểm.
Hoạt động của bất cứ hệ thống mạng ngang hàng nào cũng phụ thuộc vào mạng
bao gồm các nút và kết nối giữa chúng. Mạng này được tạo ở tầng trên và độc
lập với mạng vật lý phía dưới (thường là mạng IP), nên được gọi là “mạng phủ”.
Mô hình, cấu trúc, mức độ tập trung của mạng phủ, và cách thức định tuyến,
định vị trong mạng ảnh hưởng lớn đến hoạt động của hệ thống, do chúng sẽ
quyết định tới khả năng tự bảo trì, tự ổn định mạng, chống lỗi, hiệu năng, khả
năng mở rộng và mức độ bảo mật.
Mạng phủ có thể phân biệt dựa vào mức độ phân tán và cấu trúc [1]
1.1.1. Mức độ phân tán
Mặc dù thiết kế mong muốn của mạng phủ là hoàn toàn phân tán, tuy nhiên
trong thực tế có thể không đúng như vậy. Dưới đây liệt kê các mô hình dựa trên
mức độ phân tán của chúng
Mô hình phân tán hoàn toàn: Tất cả các nút trong mạng thực hiện các
vai trò như nhau. Vừa đóng vai trò là máy chủ, vừa là máy khách. Do đó
không cần phải có bất kỳ thành phần nào đóng vai trò là trung tâm điều
phối.
4
Hình 1: Mạng ngang hàng phân tán hoàn toàn
Mô hình phân tán một phần: Về cơ bản mô hình này tương tự như mô
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ông có cấu trúc: Vị trí của nội dung hoàn toàn không liên quan tới
mô hình của mạng phủ. Trong mạng không có cấu trúc nội dung cần phải
được định vị. Phương thức tìm kiếm rất đa dạng từ việc sử dụng các
phương pháp bruteforce, đẩy truy vấn ra tất cả các nút cho tới khi có được
kết quả, cho đến sử dụng các thuật toán phức tạp và tiết kiệm tài nguyên
hơn truy vấn ngẫu nhiên (random walks) hay dùng bảng đinh tuyến.
6
Phương pháp tìm kiếm có liên hệ mật thiết và tác động sâu sắc tới tính ổn
định, khả năng mở rộng và độ tin cậy của mạng.
Mạng không cấu trúc thương được sử dụng trong môi trường mà các nút
trong mạng luôn thay đổi.
Có cấu trúc: Mạng không cấu trúc gặp nhiều khó khăn khi mở rộng, để
giải quyết vấn đề này mạng có cấu trúc được đưa ra. Trong mạng có cấu
trúc, mô hình của mạng phủ được kiểm soát chặt chẽ, các tài nguyên trong
mạng được đặt ở các vị trí xác định. Hệ thống đảm nhận trách nhiệm ánh
xạ giữa tài nguyên và vị trí của nút chứa tài nguyên đó, dưới dạng bảng
định tuyến phân tán. Khi đó truy vấn có thể tới được nút chứa tài nguyên
một cách hiệu quả. Mạng có cấu trúc cung cấp khả năng mở rộng cho việc
tìm kiếm chính xác truy vấn (truy vấn với định danh chính xác).
Nhược điểm của mạng có cấu trúc là việc duy trì mạng sẽ gặp khó khăn
khi có quá nhiều nút ra vào mạng.
1.2. Mạng ngang hàng có cấu trúc
Mạng không cấu trúc với sự phân bố tự do của nút và tài nguyên sẽ tồn tại
nhược điểm về phương thức tìm kiếm gây tốn kém tài nguyên, đồng thời không
đảm bảo sẽ luôn tìm được kết quả cho mỗi truy vấn. Vấn đề này càng trở nên
khó giải quyết khi số lượng nút trong mạng tăng. Lý do đó khiến mạng không
cấu trúc không được áp dụng trong các hệ thống yêu cầu khả năng mở rộng cao.
Để 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ệ
thống, cân bằng tải, xác thực dữ liệu và hiệu năng của hệ thống
1.2.2. Cấu trúc hệ thống
Cấu trúc của hệ thống DHT có thể gồm nhiều thành phần chính: Phần
quan trọng nhất là không gian khóa ảo, ví dụ như chuỗi có độ dài 160 bit. Cách
thức phân vùng của không gian khóa chia không gian khóa cho từng nút trong
hệ thống. Một mạng phủ kết nối các nút với nhau, giúp các nút này tìm được nút
đang giữ thông tin về một khóa trong không gian khóa.
Với các thành phần như trên DHT có thể sử dụng phương thức sau để lưu trữ và
lấy dữ liệu. Giả sử có không gian khóa gồm các khóa có độ dài 160 bit. Để lưu
một filie với tên file và dữ liệu của nó trong DHT, thuật toán SHA-1 được sử
dụng để tạo mã băm của tên file – là khóa k có độ dài 160 bit. Tiếp đó một thông
8
báo put(k,data) được gửi đến các nút trong mạng DHT. Thông điệp này được
chuyển tiếp qua các nút qua mạng phủ cho đến khi tới được nút giữ trách nhiệm
lưu giữ khóa k được quy định bởi cách phân bổ không gian khóa. Nút đó sẽ thực
hiện lưu giữ khóa và dữ liệu. Các nút khác có thể lấy thông tin của file bằng
cách thực hiện hàm băm trên tên file để lấy được khóa k, sau đó truy vấn bất kỳ
nút nào trong mạng DHT để tìm kiếm dữ liệu ứng với khóa k bằng thông điệp
get(k). Thông điệp này tương tự được truyền trên mạng phủ thông qua các nút
cho đến khi tới nút lưu giữ thông tin về khóa k, nút này sẽ trả lại thông tin về dữ
liệu ứng với khóa.
Cách thức phân bổ không gian khóa và các thành phần của mạng phủ của một hệ
thống DHT cơ bản sẽ được mô tả như ở dưới
Phân bổ không gian khóa
Phần lớn các hệ thống DHT sử dụng các phương pháp consistent hashing để ánh
xạ khóa vào các nút. Kĩ thuật này cung cấp một hàm δ(k1,k2) để tính khoảng
cách giữa hai khóa k1 và k2. 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à ix sẽ có trách nhiệm lưu trữ với tất cả các khóa km nếu như ix là
định danh nút gần nhất với các khóa đó, tính toán bằng hàm δ(k1,k2). 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.
Mạng phủ
Mỗi nút duy trì một tập các đường dẫn đến các nút khác (các nút láng giềng) hay
còn gọi là bảng định tuyến. Tập các đường dẫn này tạo lên mạng phủ. Một nút
chọn các nút láng giềng dựa theo một cấu trúc nhất định gọi là topology của
mạng.
Tất cả các topology của DHT đều chứa các đặc điểm nhất định như: với khóa k
bất kỳ, mỗi nút hoặc sẽ có là nút lưu trữ khóa k hoặc có đường dẫn tới nút có
định danh gần với khóa k hơn, theo nghĩa về khoảng cách giữa các khóa đã nêu
ở trên. Khi đó có thể dễ dàng chuyển tiếp truy vấn tới nút chịu trách nhiệm về
9
khóa sử dụng thuật toán tham lam: nút chỉ cần chuyển tiếp truy vấn đến một nút
khác có định danh gần nhất với khóa cần tìm. Khi không còn nút nào gần với
khóa tìm kiếm hơn thì chứng tỏ truy vấn đã tới nút chịu trách nhiệm về khóa đó.
Phương thức định tuyến này còn được gọi là phương thức định tuyến dựa trên
khóa.
Ngoài việc đảm bảo định tuyến một cách chính xác, một topology cần phải đảm
bảo hai yếu tố quan trọng là đảm bảo số lượng tối đa các nút phải đi qua để trả
lời một truy vấn phải nhỏ để đảm bảo đáp ứng nhanh truy vấn và số lượng láng
giềng của một nút (bậc của nút) phải nhỏ để đảm bảo không làm gây khó khăn
trong việc duy trì hệ thống. Dĩ nhiên nếu muốn giảm số lượng nút phải đi qua thì
sẽ phải tăng số lượng láng giềng trên mỗi nút.
1.3. Mạng Chord [7]
Chord là một trong những giao thức phổ biến nhất được sử dụng trong
bảng băm phân tán. Giao thức Chord hỗ trợ khả năng gán tương ứng một key
cho trước với một nút mạng. Tùy thuộc vào ứng dụng sử dụng Chord, nút đó có
thể đảm nhiệm nhiệm vụ lưu trữ dữ liệu được gán với khóa đó. Chord sử dụng
phương pháp consistent hashing, gián tiếp thực hiện việc cân bằng tải giữa các
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ử
dụng Chord khả năng tùy biến trong việc gán tên với các khóa của
Chord.
Giao thức Chord cung cấp khả năng tính toán phân tán một cách nhanh chóng
nhằm ánh xạ một khóa với nút tương ứng. Chord gán các khóa vào các nút bằng
cách sử dụng phương pháp consistent hashing, phương pháp này có một số khả
năng cần thiết cho giao thức Chord. Với xác suất cao hàm băm sẽ phân bổ đều
khóa đến các nút (các nút ban đầu nhận được cùng một số lượng khóa). Cũng
với xác suất cao khi nút thứ N tham gia hay rời khỏi mạng chỉ một số lượng nhỏ
(O(1/N)) các khóa phải chuyển tới vị trí khác. Điều này rõ ràng giúp cho mạng
luôn giữ được một mức cân bằng tương đối.
Chord nâng cao khả năng mở rộng của phương pháp consistent hashing bằng
cách không yêu cầu một nút phải biết tất cả các nút còn lại trong mạng. Một nút
chỉ cần biết một số thông tin định tuyến giới hạn về một số nút khác. Bởi vì
thông tin này là phân tán do đó một nút tiến hành hàm băm bằng cách liên hệ
với các nút khác. Trong mạng gồm N nút, mỗi nút chỉ cần duy trì thông tin về
O(log N) các nút khác, và mỗi một truy vấn chỉ yêu cầu O(log N) thông điệp.
Phương pháp consistent hashing gán mỗi nút và khóa với một chuỗi định danh
gồm m bit sử dụng SHA-1 làm thuật toán băm cơ sở. Số m phải chọn đủ lớn sao
cho khả năng hai nút hoặc khóa có chung định danh là không đáng kể.
1.3.1. Mô hình của Chord
Các nút trong mạng Chord tạo lên một mạng logic dạng vòng tròn có các
vị trí nút từ 0 đến 2m-1. Khóa k được gán cho nút đầu tiên có định danh bằng
hoặc lớn hơn định danh của k. Nút đó được gọi là nút successor của khóa k hay
successor(k). Trong vòng định danh của Chord successor của một khóa chính là
nút gần nhất theo chiều kim đồng hồ tính từ khóa k.
11
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.
Mở rộng khả năng tìm kiếm: Thuật toán tìm kiếm ở trên sử dụng một số
lượng thông báo tương ứng tuyến tính với số nút có trong mạng. Để tăng tốc độ
quá trình tìm kiếm Chord sử dụng thêm một số thông tin định tuyến. Tương tự
như trên, ví dụ định danh của mỗi nút và khóa có độ dài m bit. Mỗi nút n duy trì
một bảng định tuyến chứa m mục, được gọi là bảng finger. Mục thứ i trong bảng
của nút n chứa định danh của nút s sao cho s là nút đầu tiên trên vòng tiếp sau
khóa n+2i-1 s=successor(n+2i-1), với 1 ≤ i ≤ m (lấy số dư với modun 2 m). Ta gọi s
là finger thứ i của nút n. Finger đầu tiên của một nút cũng chính là successor của
nút đó.
13
Hình 7: Bảng finger của nút 8
Hình 8 thể hiện bảng finger của nút . Finger đầu tiên được trỏ đến nút 14 dó 14
là nút liền sau (8+20) mod 26 = 9. Tương tự finger cuối cùng của nút 8 trỏ đến
nút 42 do 42 là nút liền sau (8+25) mod 26 = 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
mới tham gia vào mạng, rời khỏi mạng và đột ngột rời khỏi mạng. Để tham gia
vào mạng một nút n thực hiện truy vấn tìm kiếm cho chính id của nó thông qua
một số nút ban đầu đã tham gia vào mạng và tự đưa nó vào vòng Chord, ở vị trí
nằm giữa successor s và predecessor của s thông qua quá trình ổn định mạng.
Bảng finger của n được khởi tạo bằng cách sao chép bảng finger của của s hoặc
để s lần lượt tìm kiếm các finger cho n. Các nút cần thay đổi bảng finger khi có
sự tham gia của n sẽ lần lượt thực hiện việc này thông qua quá trình ổn định
mạng chạy định kỳ. Cuối cùng các khóa đang được giữ bởi s, có id nhỏ hơn
hoặc bằng n sẽ được chuyển qua n.
15
Khi một nút tự nguyện dời khỏi mạng, tất các khóa (các item liên quan đến
khóa) được chuyển cho successor, sau đó thông báo cho successor và
predecessor. Bảng finger trên các nút khác sẽ dần dần được điều chỉnh thông
qua quá trình ổn định mạng định kỳ.
Chống lỗi và tạo bản sao: Khi một nút đột ngột rời khỏi mạng sẽ gây ra các hậu
quả như sau: Đầu tiên việc này có thể gây mất các khóa (các item liên quan đến
khóa). Thứ hai: một bộ phận các nút sẽ không truy vấn được một số khóa nhất
định. Chord giải quyết vấn đề này bằng cách lưu trên mỗi nút một danh sách các
nút nằm sau nó trong vòng Chord. Nếu một nút đột ngột không liên lạc được với
successor thì nó sẽ sử dụng các nút liền sau trong danh sách. Tiếp nữa các khóa
(các item liên quan tới khóa) sẽ được sao chép trên các nút có trong danh sách
đó. Do đó một khóa (item liên quan đến khóa) sẽ chỉ bị mất khi có log 2(N)+1
các nút trong danh sách phải đồng
thời rời khỏi mạng.