ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Đặng Ngọc Bền
TỐI ƯU HÓA TOPOLOGY CHO MẠNG NGANG
HÀNG CÓ CẤU TRÚC CHORD
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ Thông tin
Cán bộ hướng dẫn: TS. Nguyễn Hoài Sơn
HÀ NỘI - 2009
LỜI CẢM ƠN
Em xin chân thành cảm ơn các thầy cô giáo trong trường Đại học Công nghệ - Đại
học Quốc gia Hà Nội đã tận tình giúp đỡ và truyền đạt kiến thức cho em trong suốt 4
năm học qua để em có đủ kiến thức hoàn thành khóa luận này.
Đặc biệt, em xin gửi lời cảm ơn sâu sắc tới thầy Nguyễn Hoài Sơn – người đã
nhiệt tình động viên, định hướng em trong quá trình định hình, nghiên cứu và hoàn
thành khóa luận.
Em xin cảm ơn sự nhiệt tình chia sẻ kinh nghiệm, đóng góp ý kiến của nhóm
nghiên cứu do thầy Nguyễn Hoài Sơn hướng dẫn, của các anh chị cao học. Em xin gửi
lời cảm ơn chân thành tới thầy Nguyễn Đại Thọ, người đã giảng dạy cho em những kiến
thức cơ bản liên quan trực tiếp đến đề tài của khóa luận.
Mặc dù đã rất cố gắng hoàn thành khóa luận này, xong khóa luận sẽ khó tránh khỏi
những thiếu sót, kính mong quý thầy cô tận tình chỉ bảo giúp em. Một lần nữa em xin
cảm ơn tất cả mọi người.
Hà Nội, tháng 5 năm 2009
Sinh viên
Đặng Ngọc Bền
Tóm tắt
Ngày nay, Internet đã thực sự phát triển và đi sâu vào đời sống của mỗi con người.
Khả năng chia sẻ những tài nguyên lớn một cách nhanh chóng và hiệu quả luôn nhận
được quan tâm từ những người nghiên cứu cũng như sử dụng Internet. Với những đặc
điểm phù hợp, mạng ngang hàng, đặc biệt là mạng ngang hàng có cấu trúc ngày càng

2.3. Quasi-Chord [7] ............................................................................................................................... 19
Chương 3. Tối ưu Chord dựa trên lựa chọn độ trễ .................................................................................. 24
3.1. Đề xuất ............................................................................................................................................ 24
3.2. Nội dung .......................................................................................................................................... 25
3.3. Ưu nhược điểm .............................................................................................................................. 27
Chương 4. Mô phỏng và đánh giá ............................................................................................................ 28
4.1. Chương trình mô phỏng ................................................................................................................. 28
4.1.1. Kiến trúc mạng mô phỏng ....................................................................................................... 28
4.1.2. Dữ liệu ..................................................................................................................................... 30
4.1.3. Các đối tượng .......................................................................................................................... 31
4.1.4. Thực thi .................................................................................................................................... 33
4.2. Kết quả và đánh giá ........................................................................................................................ 36
4.2.1. Hiệu quả so với Chord truyền thống ....................................................................................... 36
4.2.2. Hiệu quả khi thay đổi tham số ................................................................................................. 37
.................................................................................................................................................................. 40
Chương 5. Kết luận ................................................................................................................................... 42
5.1. Kết luận ........................................................................................................................................... 42
5.2. Hướng phát triển tiếp theo của đề tài ........................................................................................... 42
Tài liệu tham khảo .................................................................................................................................... 44
Phụ lục A ................................................................................................................................................... 45

Danh mục hình ảnh
Hình 1. Mô hình mạng ngang hàng..............................................................................................................3
Hình 2. Mô hình mạng khách chủ................................................................................................................4
Hình 3. Mạng ngang hàng lai thế hệ thứ nhất (Napster)............................................................................7
Hình 4. Mạng ngang hàng thuần túy (Gnutella 0.4, FreeNet).....................................................................8
Hình 5. Kiến trúc siêu ngang hàng(Gnutella 0.6, JXTA)................................................................................9
Hình 6. Cơ chế của bảng băm phân tán (DHT)..........................................................................................11
Hình 7. Mạng ngang hàng có cấu trúc Chord dạng vòng tròn...................................................................11
Hình 8. Một mạng Chord với 3 nút............................................................................................................13

nhiều ưu điểm như khả năng mở rộng, cân bằng tải, định tuyến,... Giống như những
giao thức trên mạng có cấu trúc khác, mỗi nút trong Chord xây dựng một bảng định
tuyến giúp cho việc tìm kiếm thông tin giảm từ O(N) với N là số lượng tối đa nút trong
mạng, xuống còn O(log
2
N).
Trong mạng ngang hàng có cấu trúc nói chung và Chord nói riêng, quan hệ hàng
xóm của các nút được thiết lập mà không xem xét đến topo (topology) tầng dưới. Đó
chính là nguyên nhân gây ra sự sai khác giữa topo của mạng DHT và topo mạng liên kết
vật lý (topology mismatch). Điều này làm cho độ trễ truyền thông báo giữa các nút và
chi phí truyền thông trong mạng P2P. Yêu cầu đặt ra là làm sao để tối ưu mạng phủ,
khắc phục sự khác biệt đó.
Ngoài ra, khi xây dựng bảng định tuyến trong cấu trúc Chord, liên kết tại hàng thứ
i được chọn cố định là nút quản lý định danh k+2
i
. Như vậy, quá trình xây dựng liên kết
trong bảng định tuyến cũng không xem xét đến quan hệ giữa các nút ở tầng dưới. Nếu
như liên kết này có thời gian trễ lớn thì tất cả những truy vấn đi qua nó đều bị ảnh
hưởng bởi độ trễ này. Quá trình chuyển tiếp truy vấn là đưa truy vấn đến vị trí mà khóa
cần tìm kiếm thuộc lân cận của vị trí đó. Vì thế, phương pháp hiện có để xây dựng các
liên kết trong bảng định tuyến là chưa tốt.
1
Khóa luận này sẽ đề xuất một phương pháp mới để giải quyết hai vấn đề nêu trên
xảy ra với mạng ngang hàng có cấu trúc nói chung và cấu trúc Chord nói riêng. Vẫn dựa
trên cấu trúc và định tuyến của Chord truyền thống, trong đề xuất mà khóa luận đưa ra,
thứ nhất, các nút tham gia vào mạng sẽ lựa chọn vị trí theo tiêu chí mà tại đó, nút được
chọn có thời gian trễ tới các nút liền trước và liền sau là nhỏ nhất; thứ hai, bảng định
tuyến của nút sẽ được thay đổi bằng cách lựa chọn lại các nút đích của các liên kết từ
một tập nút nào đó cũng theo tiêu chí thời gian trễ nhỏ nhất, nhằm tiết kiệm chi phí
đường đi của các thông báo. Hai đề xuất sẽ giải quyết lần lượt vấn đề khác biệt về topo

chúng ta sẽ làm quen với cấu trúc Chord, một trong những giao thức phổ biến nhất trong
mạng ngang hàng có cấu trúc.
1.1. Mạng ngang hàng
Định nghĩa
Mạng ngang hàng, là một mạng máy tính trong đó hoạt động của mạng chủ yếu
dựa vào khả năng tính toán và băng thông của các máy tham gia chứ không tập trung
vào một số nhỏ các máy chủ trung tâm như các mạng thông thường. Mạng ngang hàng
thường được sử dụng để kết nối các máy thông qua một lượng kết nối dạng ad hoc.
Mạng ngang hàng có nhiều ứng dụng. Ứng dụng
thường xuyên gặp nhất là chia sẻ tệp tin, tất cả
các dạng như âm thanh, hình ảnh, dữ liệu,... hoặc
để truyền dữ liệu thời gian thực như điện thoại
VoIP.
Một mạng ngang hàng đúng nghĩa không có
khái niệm máy chủ và máy khách, nói cách khác,
tất cả các máy tham gia đều bình đẳng và được
gọi là peer, là một nút mạng đóng vai trò đồng
thời là máy khách và máy chủ đối với các máy
khác trong mạng. Một ví dụ điển hình là dịch vụ
3
Hình 1. Mô hình mạng ngang hàng
truyền dữ liệu. Các nút trong mạng ngang hàng sẽ
liên lạc với nhau, lấy dữ liệu từ nút khác về, đồng
thời chia sẻ dữ liệu đó cho những nút có nhu cầu.
Với mô hình khách chủ, máy khách gửi yêu cầu,
thực hiện việc nhận dữ liệu một chiều từ phía
máy chủ. Đây chính là điểm khác biệt cơ bản nhất
của mô hình ngang hàng so với các mô hình
truyền thống.
Một số mạng hay kênh như Napster, IRC

Ngoài ra, do mô hình mạng ngang hàng đơn giản nên dễ cài đặt, tổ chức và quản
trị, chi phí thiết bị thấp. Mô hình khách chủ đòi hỏi một server đủ mạnh với giá thành
cao, thường thì server này ít sự cố, nhưng nếu có sẽ gây thiệt hại lớn về thông tin và cả
chi phí để tái thiết lập lại hệ thống. Hiện nay, máy tính cá nhân đủ mạnh để có thể làm
nhiều hơn công việc của một client, vì thế tham gia vào mạng ngang hàng với nhiều
tiềm năng là khả thi.
Đối với mạng Napster, thuật ngữ ngang hàng nói lên tính chất quan trọng của giao
thức giao tiếp ngang hàng, còn thực ra thành công của Napster phải nhờ vào sự liên kết
chặt chẽ giữa các máy tham gia với máy chủ trung tâm lưu trữ danh sách nội dung tệp
trên các máy tham gia. Nhờ vậy việc tìm kiếm trở nên nhanh và hiệu quả hơn, tuy nhiên,
đây cũng chính là điểm yếu dẫn đến các rắc rối pháp lý mà kết cục là sự sụp đổ của
Napster.
Nhược điểm
Mặc dù có rất nhiều ưu điểm, nhưng mạng ngang hàng cũng bộc lộ khá nhiều
nhược điểm. Các nút tham gia với tính phân tán, trách nhiệm và vai trò là như nhau
trong mạng, ít tuân theo quy luật hay giàng buộc nào. Đáng kể như:
− Kết quả truy vấn trả về có thể là rất nhiều do kết nối đến nhiều nút khác nhau,
sự đồng bộ giữa các nút là khá khó khăn. Hoặc có thể chẳng nhận được trả lời
nào hay dữ liệu cần tìm không tồn tại, do không biết trước nút đích có còn nằm
trong mạng hay không.
− Các nút đột ngột rời khỏi mạng sẽ làm sai bảng định tuyến trong một thời gian
nhất định, làm cho việc truy vấn thiếu chính xác. Dữ liệu mà nút đó phụ trách
cũng có thể bị mất theo.
− Sự bảo mật dữ liệu là kém do dữ liệu phân tán.
Các nhược điểm trên đang dần được san lấp bằng nhiều phương pháp. Đáng chú ý
là đặt ra các luật lệ, nội quy ràng buộc các bên tham gia với quyền lợi và trách nhiệm
nhất định sẽ giúp cho mạng ổn định và an toàn hơn. Số lượng thành viên tham gia mạng
ngang hàng ngày càng nhiều giúp cho tài nguyên mạng trở lên phong phú, hiệu suất
mạng cũng tăng tỉ lệ với số lượng nút tham gia. Ngoài ra, các cơ chế nhân bản giúp cho
xác suất mất dữ liệu khi các nút rời đi trở lên vô cùng nhỏ.

nguyên trong mạng và quá trình truyền file được thực hiện theo đúng cơ
chế của mạng ngang hàng, giữa các host với nhau mà không cần quan
máy chủ trung tâm.
6
Hình 3. Mạng ngang hàng lai thế hệ thứ nhất (Napster)
Ưu điểm:
 Dễ xây dựng.
 Tìm kiếm file nhanh và hiệu quả.
Nhược điểm:
 Vấn đề luật pháp, bản quyền.
 Dễ bị tấn công.
 Cần quản trị (central server).
Napster là mạng ngang hàng đặc trưng cho hệ thống mạng ngang hàng của
thế hệ thứ nhất, chúng được dùng cho việc chia sẻ các file giữa các người dùng
Internet, được sử dụng rộng rãi, tuy nhiên nhanh chóng bị mất thị trường bởi yếu
tố về luật pháp. Khái niệm và kiến trúc của Napster vẫn còn được sử dụng trong
các ứng dụng khác như: Audiogalaxy, WinMX.
Với Napster, việc tìm kiếm file bị thất bại khi bảng tìm kiếm trên máy chủ vì
lý do nào đó không thực hiện được. Chỉ có các file truy vấn và việc lưu trữ được
phân tán, vì vậy máy chủ đóng vai trò là một nút cổ chai. Khả năng tính toán và
lưu trữ của máy chủ tìm kiếm phải tương xứng với số nút mạng trong hệ thống, do
đó khả năng mở rộng mạng bị hạn chế rất nhiều.
1.2.2. Mạng ngang hàng thuần túy (Pure Peer-to-peer System)
Mạng ngang hàng thuần túy là một dạng khác của thế hệ thứ nhất trong hệ
thống các mạng ngang hàng. Không còn máy chủ tìm kiếm tập trung như trong
7
mạng Napster, nó khắc phục được vấn đề nút cổ chai trong mô hình tập trung. Tuy
nhiên vấn đề tìm kiếm trong mạng ngang hàng thuần túy lại sử dụng cơ chế
Flooding, yêu cầu tìm kiếm được gửi cho tất cả các nút mạng là láng giềng với nó,
điều này làm tăng đáng kể lưu lượng trong mạng. Đây là một yếu điểm của các

Client-peer và địa chỉ IP của chúng vì vậy nó có thể trả lời ngay lập tức
các yêu cầu truy vấn từ các Client-peer gửi tới.
Ưu điểm:
 Hạn chế việc Flooding các query, làm giảm lưu lượng trong mạng, nhưng
vẫn tránh được hiện tượng nút cổ chai (do có nhiều Super-peers).
 Khắc phục được nhược điểm về sự khác nhau về CPU power,
bandwidth… ở mạng ngang hàng thuần túy, các Super-peer sẽ chịu tải
chính, các nút khác chịu tải nhẹ.
9
Nhược điểm:
 Mỗi điểm Super-peer trở thành điểm gây lỗi cho nhóm siêu ngang hàng
tương ứng trong trường hợp số lượng Client trong nhóm là rất lớn (tuy
nhiên, nhược điểm này đã được giải quyết bằng việc cải tiến mạng siêu
ngang hàng thông thường, đưa ra khái niệm siêu ngang hàng dư cấp k).
1.2.4. Mạng ngang hàng có cấu trúc (Structured)
Hệ thống mạng ngang hàng không cấu trúc thể hiện nhược điểm: không có gì
đảm bảo tìm kiếm sẽ thành công. Đối với tìm kiếm các dữ liệu phổ biến được chia
sẻ trên nhiều máy, tỉ lệ thành công là khá cao, ngược lại, nếu dữ liệu chỉ được chia
sẻ trên một vài máy thì xác suất tìm thấy là khá nhỏ. Tính chất này là hiển nhiên vì
trong mạng ngang hàng không cấu trúc, không có bất kì mối tương quan nào giữa
một máy và dữ liệu nó quản lý trong mạng, do đó yêu cầu tìm kiếm được chuyển
một cách ngẫu nhiên đến một số máy trong mạng. Số lượng máy trong mạng càng
lớn thì khả năng tìm thấy thông tin càng nhỏ. Một nhược điểm khác của hệ thống
này là do không có định hướng, một yêu cầu tìm kiếm thường được chuyển cho
một số lượng lớn máy trong mạng làm tiêu tốn một lượng lớn băng thông của
mạng, dẫn đến hiệu quả tìm kiếm chung của mạng thấp.
Mạng ngang hàng có cấu trúc khắc phục nhược điểm của mạng không cấu
trúc bằng cách sử dụng hệ thống DHT (Distributed Hash Table - Bảng Băm Phân
Tán). Hệ thống này định nghĩa liên kết giữa các nút mạng trong mạng phủ theo
một thuật toán cụ thể, đồng thời xác định chặt chẽ mỗi nút mạng sẽ chịu trách

mang tính ưu thế của mình. Hai trong số những đặc điểm của Chord không thể không kể
tới đó là khả năng tìm kiếm dữ liệu nhanh và cân bằng tải giữa các nút.
Một đặc điểm của mạng DHT dễ nhận thấy ở Chord là sự phân phát khóa tương
đối đồng đều vào các nút trong mạng. Đây chính là hệ quả của việc sử dụng kỹ thuật
consistent hashing để cấp khóa cho các nút. Phương thức hình thành khóa phổ biến nhất
thường được dùng là băm giá trị của dữ liệu để tạo thành khóa. Giá trị của dữ liệu ở đây
11
Hình 7. Mạng ngang hàng có cấu trúc
Chord dạng vòng tròn.
có thể là địa chỉ, tên tài liệu, những từ xuất hiện nhiều trong một văn bản, nội dung văn
bản đó,… Mỗi loại giá trị dữ liệu có những đặc điểm khác nhau, tùy từng trường hợp
mà giá trị nào được sử dụng sao cho phù hợp với ứng dụng nhất. Sự phân bổ khóa trong
giao thức Chord thường đi kèm với dữ liệu, thường là một cặp (khóa, dữ liệu). Khóa
được coi như phương thức chỉ đường để có thể tìm thấy dữ liệu mong muốn một cách
nhanh nhất.
Có thể nói Chord là đại diện tiêu biểu nhất của hệ thống mạng ngang hàng có cấu
trúc DHT, không những vậy Chord còn là nền tảng cho những nghiên cứu phát triển ứng
dụng sau này. Một số nghiên cứu đã chỉ ra rằng: Chord không chỉ là một mạng DHT
đơn thuần mà còn mang nhiều ưu điểm khác mà một số mạng DHT không có. Nói tới
Chord ta có thể nhắc tới những đặc điểm sau đây:
- Cân bằng tải (Load Balance): Quá trình hình thành và phân bổ khóa của Chord
dựa trên thuật toán Consistent Hashing. Chính những đặc điểm của thuật toán
này đã tạo cho Chord một khả năng cân bằng tải một cách tự nhiên ngay khi
mạng được khởi tạo.
- Sự phân quyền: Trong giao thức Chord, không nút nào quan trọng hơn nút nào,
quyền hạn này được thực hiện rất hiệu quả trong giao thức Chord. Một số
mạng P2P ban đầu cũng có những đặc điểm tương tự nhưng vẫn tồn tại những
yếu điểm mà Chord đã khắc phục được.
- Khả năng mở rộng: Quá trình hình thành mạng, tìm kiếm dữ liệu trong Chord
phụ thuộc nhiều vào sự biến thiên của hàm số logarit. Chính điều này tạo cho

value có thể là 1 address, 1 văn bản, hoặc 1 mục dữ liệu. Chord có thể thực hiện
chức năng này bằng cách lưu các cặp key/value ở các nút mà key được ánh xạ.
Một nút sẽ chịu trách nhiệm lưu giữ một khóa k nếu nút đó là nút có định danh id
nhỏ nhất và lớn hơn k. Một nút khi lưu giữ khóa k cũng sẽ được gọi là
Successor(k).
13
Hình 9. Lưu giữ key trong mạng Chord
1.3.3. Tìm kiếm trong mạng Chord
Khi một nút cần tìm kiếm một khóa có định danh id, nút đó sẽ tìm nút chịu
trách nhiệm lưu giữ id đó. Nếu nút ở xa so với vị trí của nút lưu giữ id, nút có thể
nhờ vào thông tin trong bảng Finger Table để định tuyến đến các nút xa hơn, từ đó
dần dần biết được nút chịu trách lưu giữ id.
Một ví dụ được chỉ trong hình 6, giả sử nút 3 muốn tìm successor của ID
(hoặc còn có thể coi là khóa) 1. ID 1 thuộc khoảng [7, 3), tức là
3.finger[3].interval. nút 3 kiểm tra entry thứ 3 trong bảng định tuyến của nó, là 0.
Bởi vì 0 trước 1, nút 3 sẽ hỏi nút 0 để tìm successor của 1. Quay trờ lại, nút 0 sẽ
suy ra từ bảng định tuyển rằng successor của 1 chính là nút 1, và trả về nút 1 cho
nút 3.
1.3.4. Tham gia và ổn định mạng
Trong 1 mạng động , thường xuyên có sự thay đổi với các nút tham gia và
rời khỏi bất kì lúc nào. Để có thể xác định được vị trí của các khóa ở trong mạng,
Chord cần thỏa mãn 2 điểm sau :
• Mỗi successor của 1 nút phải đc duy trì đúng
• Với mỗi khóa k, nút successor(k) có trách nhiệm quản lý k
Khi tham gia vào một mạng Chord, một nút n cần chọn cho nó một định
danh id và báo cho các nút bên cạnh biết sự tham gia của nó. Các nút Successor và
Predecessor sẽ cần phải cập nhật thông tin về nút mới tham gia vào mạng. Nút n
cũng cần khởi tạo bảng định tuyến Finger Table bằng cách tìm các nút mà
Successor các id trong từng entry của Finger Table. Để mạng vẫn định tuyến đúng
14

gian địa chỉ - tránh sự tập trung của nút và tài liệu trên toàn dải địa chỉ, đồng thời hỗ trợ
việc bảo mật thông tin địa chỉ giữa các tầng cũng như các nút tham gia mạng, nhưng lại
gây ra sự không đồng bộ về topo như trên. Theo đó, hai nút ở rất gần nhau về đường
truyền vật lý có thể sẽ trở lên xa nhau trên dải địa chỉ của Chord và ngược lại. Trong các
ứng dụng ngang hàng Chord, các truy vấn ngắn thường có tần suất lớn hơn các truy vấn
dài do quá trình tìm kiếm ưu tiên các nút hàng xóm trước. Như vậy, hậu quả rõ rệt là với
một truy vấn bất kỳ, thời gian đáp ứng cho truy vấn đó có thể rất lớn, hiệu suất của ứng
dụng giảm.
Một cách tiếp cận để giải quyết vấn đề Topology mismatch là dựa vào các đặc
điểm vật lý. Đặc điểm vật lý chúng ta nói ở đây là vị trí của nút, địa chỉ của nút. Với các
thông tin này, chúng ta có thể làm mới cấu trúc của mạng phủ sao cho phù hợp với
mạng vật lý nhất. Nhưng giá phải trả cho phương pháp này là không nhỏ. Trước hết, cấu
16
trúc gần với mạng vật lý trong nhiều trường hợp lại tỏ ra kém hiệu quả, đặc biệt là sự
khó kiểm soát giao thông trên mạng tại từng vùng, từng điều kiện và thời điểm. Thứ hai,
rất quan trọng, là làm mất đi tính trong suốt giữa các tầng. Tầng ứng dụng phải nắm
được rất nhiều thông tin về tầng dưới không chỉ của máy local, các máy khác cũng phải
cung cấp thông tin. Điều này ảnh hưởng đến an toàn giao thông mạng, các hình thức tấn
công và hơn hết là sự riêng tư của những người tham gia mạng ngang hàng.
Tối ưu bảng định tuyến (Finger Table)
Một điểm cải tiến rất lớn lớn trong cấu trúc Chord (DHT nói chung) so với các thế
hệ mạng ngang hàng trước chính là việc bổ xung thêm bảng định tuyến. Thay vì phát
tràn các truy vấn hay thực hiện phát truy vấn theo một thuật toán ưu tiên nào đó như
trong mạng ngang hàng không có cấu trúc, hoặc truy vấn tuyến tính trên dải địa chỉ băm
của mạng có cấu trúc, bảng định tuyến giúp cho việc gửi các yêu cầu truy vấn diễn ra
nhanh chóng, hiệu quả. Số lượng truy vấn phát ra từ nút tìm kiếm là duy nhất, và sau tối
đa log
2
n bước chuyển tiếp, truy vấn sẽ tới đích. Cơ chế này dựa trên thuật toán tìm kiếm
nhị phân, điều này lý giải tại sao entry thứ i trong bảng định tuyến sẽ lưu nút là