1



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



LÊ ANH TUẤN



ĐỊNH TUYẾN AN TOÀN
TRONG CẤU TRÚC BẢNG BĂM PHÂN TÁN
CHORD KÉP


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ố:

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Nguyễn Đại Thọ

Hà Nội - 2014
2




Lời cam đoan

Tôi xin cam đoan:
- Luận văn này là sản phẩm nghiên cứu của tôi.
- Các số liệu, kết quả nêu trong luận văn chưa từng được cá nhân,
tổ chức nào công bố trong bất kỳ công trình nào khác.
- Các thông tin trích dẫn đã được chỉ rõ nguồn gốc.
Học viên


Lê Anh Tuấn
3



MỤC LỤC
DANH MỤC KÝ HIỆU VÀ CHỮ VIẾT TẮT 5
DANH MỤC CÁC HÌNH ẢNH, ĐỒ THỊ 6
MỞ ĐẦU 8
CHƯƠNG 1: TỔNG QUAN VỀ MẠNG NGANG HÀNG 10
1.1. Khái niệm mạng ngang hàng 10
1.2. Các ứng dụng của mạng ngang hàng 10
1.3. Các mô hình mạng ngang hàng 12
1.3.1. Mạng ngang hàng không có cấu trúc 12

1.3.2. Mạng ngang hàng có cấu trúc 13
1.4. Cấu trúc chỉ mục phân tán Chord 16
CHƯƠNG 2: AN NINH CHO CẤU TRÚC CHỈ MỤC PHÂN TÁN 20
2.1. Giới thiệu 20
2.2. Tấn công dữ liệu và phương pháp phòng chống 20
2.3. Tấn công lợi dụng quá trình cấp phát định danh 21
2.3.1. Tấn công giả mạo và phương pháp phòng chống 21
2.3.2. Tấn công che khuất và phương pháp phòng chống 22
2.4. Tấn công định tuyến và phương pháp phòng chống 23
2.4.1. Định tuyến tương tác 25
2.4.2. Giá trị khoảng cách trung bình 25
2.4.3. Quá trình xác thực 26
2.4.4. Thuật toán quay lui 27
CHƯƠNG 3: CẤU TRÚC CHỈ MỤC PHÂN TÁN CHORD KÉP 29
3.1. Giới thiệu 29
3.2. Cấu trúc chỉ mục Chord kép 29
3.3. Định tuyến trong mạng Chord kép 31
3.4. Hiệu năng của mạng Chord kép 34
CHƯƠNG 4: MÔ PHỎNG VÀ ĐÁNH GIÁ HIỆU NĂNG ĐẢM BẢO AN
NINH ĐỊNH TUYẾN CHO MẠNG CHORD KÉP 37
4.1. Tóm tắt những vấn đề an ninh 37
4.2. Xây dựng thủ tục định tuyến 38
4.3. Chương trình mô phỏng 42
4.3.1. Giới thiệu 42
4



4.3.2. Cấu trúc chương trình thử nghiệm 45
4.3.3. Khảo sát và đánh giá 46

4.3.3.1. Nhiễm độc có tính chất không hồi đáp truy vấn 47
4.3.3.2. Nhiễm độc có tính chất chuyển tiếp ngẫu nhiên các truy vấn 47
4.3.3.3. Các nút nhiễm độc thông đồng tạo vòng định tuyến nhỏ 49
KẾT LUẬN 52
TÀI LIỆU THAM KHẢO 54
PHỤ LỤC 56
1. Cấu trúc chương trình thử nghiệm 56
2. Một số các sửa đổi cơ bản trong chương trình mô phỏng 58

5



DANH MỤC KÝ HIỆU VÀ CHỮ VIẾT TẮT
Chữ viết tắt
Giải thích
BChord
Bi-directional Routing DHT based on Chord: Chord kép
CAN
Content Addressable Network
DHT
Distributed Hash Tables: Bảng băm phân tán
IP
Internet Protocol: Giao thức liên mạng
PPLive
DOnet
GridMedia
Ứng dụng chia sẻ nội dung đa phương tiện trực tuyến
P2P
Peer-to-Peer network: mạng ngang hàng

SHA-1
Secure Hash Algorithm - 1: Các thuật toán băm an toàn phiên
bản 1
TTL
Time-to-live: định khoảng thời gian vòng đời



6



DANH MỤC CÁC HÌNH ẢNH, ĐỒ THỊ
Hình 1.1. Mô tả cấu trúc một mạng ngang hàng. 10
Hình 1.2. Mô tả kỹ thuật tìm kiếm trong mạng Gnutella 13
Hình 1.3. Tìm kiếm và gia nhập mạng CAN 14
Hình 1.4. Trạng thái nút có định danh 10233102 trong Pastry 15
Hình 1.5. Mô hình bảng băm phân tán 16
Hình 1.6. Mô tả mạng Chord có 6-bit định danh 17
Bảng 1.1. Định nghĩa bảng chỉ mục phân tán Chord 17
Hình 1.7. Mô tả bảng chỉ mục phân tán tại một nút trên Chord 18
Hình 1.8. Mã giả thuật toán tìm successor(id) 18
Hình 1.9. Mô tả quá trình tìm successor của khóa K54 19
Hình 1.10. Mô tả quá trình nút N26 gia nhập mạng Chord 19
Hình 2.1. Một kiểu tấn công Sybil 22
Hình 2.2. Mô tả kiểu tấn công che khuất Eclipse 23
Hình 2.3. Ảnh hưởng của nút nhiễm độc đến sự thành công truy vấn 23
Hình 2.4. Mô tả một kiểu tấn công định tuyến nhắm vào bảng chỉ mục 24
Hình 2.5. Mô tả khái niệm khoảng cách trung bình giữa các nút 26
Hình 2.6. Mô tả quá trình xác định chỉ mục trỏ đến f 26

Hình 2.7. Mô tả thuật toán quay lui 28
Hình 3.1. Cấu trúc chỉ mục theo chiều ngược 30
Hình 3.2. Cấu trúc chỉ mục theo chiều thuận 30
Hình 3.3. Mô tả cấu trúc chỉ mục Chord kép của nút N8. 31
Hình 3.4. Mô tả quá trình định tuyến trong Chord so với Chord kép 32
Hình 3.5. Mã giả thủ tục cho nút mới gia nhập mạng 34
Hình 3.6. So sánh pL giữa 2 giao thức trong không gian định danh m=4 34
Hình 3.7. Thông điệp quảng bá trong mạng Chord kép với n=4 35
Hình 3.8. Thông điệp quảng bá trong mạng Chord với n=4 36
Hình 4.1. Mô tả các tính chất của nút nhiễm độc 38
7



Hình 4.2. Cấu trúc chỉ mục phân tán Chord kép 39
Hình 4.3. Sơ đồ khối thủ tục định tuyến trong mô hình mạng Chord kép 40
Hình 4.4. Mô tả quá trình tìm kiếm khóa K3 và khóa K29 41
Hình 4.5. Mô tả khái niệm khoảng cách trung bình giữa các nút trong mô hình
mạng Chord kép. 43
Hình 4.6. Giao diện chính của chương trình mô phỏng 44
Hình 4.7. Biểu đồ mô tả mối tương quan về tỷ lệ truy vấn thành công trước
(default) và sau khi áp dụng các giải pháp an ninh (secure) 47
Hình 4.8. Mô tả tỷ lệ truy vấn thành công trước và sau khi áp dụng các biện
pháp an ninh với độ lệch chuẩn =3 48
Hình 4.9. Giá trị trung bình bước nhảy khi áp dụng các giải pháp an ninh 48
Hình 4.10. Mô tả tỷ lệ truy vấn thành công trong môi trường bị nhiễm độc có
tính chất thông đồng với tham số độ lệch chuẩn (std.Deviation)=3 50
Hình 4.11. Sự ảnh hưởng của độ lêch chuẩn với tỷ lệ truy vấn thành công 50
Hình 4.12. Giá trị bước chuyển tiếp truy vấn trung bình dưới sự ảnh hưởng của
độ lêch chuẩn 51





8



MỞ ĐẦU
Mạng ngang hàng là mô hình mạng được ứng dụng rộng rãi trong lĩnh vực
công nghệ thông tin đặc biệt là mạng diện rộng như Internet, từ các ứng dụng đơn
giản như chia sẻ file, dữ liệu, truyền hình trực tuyến, trên nền Internet đến những
ứng dụng phức tạp hơn như hệ thống truy vấn dữ liệu, hệ quản trị cơ sở dữ liệu,
Mô hình mạng ngang hàng không có cấu trúc với ưu điểm dễ triển khai, khả mở
nhưng lại tồn tại những nhược điểm cốt yếu như: không có tính định hướng, mỗi
yêu cầu tìm kiếm thường được chuyển đến một số lượng lớn các nút trong mạng
gây tiêu tốn băng thông, thời gian tìm kiếm và không đảm bảo truy vấn sẽ thành
công vì không có bất kỳ mối quan hệ nào giữa nút mạng với dữ liệu mà nó đang
quản lý. Mạng ngang hàng có cấu trúc với việc ứng dụng bảng băm phân tán định
nghĩa liên kết giữa các nút trong mạng theo một nguyên tắc cụ thể, đồng thời xác
định chặt chẽ mỗi nút chịu trách nhiệm đối với một phần dữ liệu chia sẻ nên đã
khắc phục được những nhược điểm của mô hình mạng ngang hàng không cấu
trúc. Với cấu trúc chỉ mục phân tán dựa trên DHT mạng ngang hàng có cấu trúc
Chord đã cho thấy một kiến trúc định tuyến hiệu quả, có tính tự tổ chức và khả
mở cao [6].
Tuy nhiên, cùng với những ưu điểm của mô hình mạng ngang hàng có cấu
trúc, mạng ngang hành Chord cũng tồn tại những vấn đề về an ninh và đặc biệt là
an toàn trong quá trình định tuyến. Kẻ tấn công khi đã làm chủ được quá trình
định tuyến trong mạng có thể điều khiển, khống chế hoạt động truyền thông của
các nút mạng. Nút bị nhiễm độc thay vì chuyển các truy vấn định tuyến đến đích

thì chúng loại bỏ hoặc chuyển đến một nút đích sai theo ý đổ của kẻ tấn công, từ
đó làm giảm độ tin cậy của toàn mạng. Đã có những giải pháp khắc phục và chống
lại cuộc tấn công vào quá trình định tuyến như giải pháp của Keith Needels (2008)
trong bài

báo [8] hoặc phương pháp cải tiến của Nguyễn Minh Thăng (2013) trong
bài

báo [10] và chúng đã được chứng minh là khá tốt và hiệu quả.
Mạng ngang hàng Chord kép (BChord) [5] được thiết kế dựa trên mạng
Chord, là sự mở rộng của mạng Chord về khả năng định tuyến, giờ đây các nút
9



trong mạng Chord kép có thể định tuyến theo hai chiều, cùng chiều kim đồng hồ
(kế thừa từ Chord) và ngược chiều kim đồng hồ. Với việc xây dựng cấu trúc chỉ
mục mới, mạng Chord kép đã cho thấy khả năng định tuyến hiệu quả hơn mạng
Chord. Tuy nhiên cũng như các mạng ngang hàng khác, nó cũng tồn tại những
vấn đề mất gây mất an toàn trong quá trình định tuyến, nút nhiễm độc có thể không
hồi đáp hoặc loại bỏ các truy vấn chuyển qua nó, thay đổi đích đến của truy vấn
làm sai lệch kết quả truy vấn, vì vậy khắc phục những vấn đề an ninh định tuyến
trên Chord kép cũng cần phải được nghiên cứu và giải quyết.
Hiện tại chưa có giải pháp an ninh định tuyến nào được xây dựng cho mạng
Chord kép. Mục tiêu của luận văn là xây dựng thủ tục định tuyến hiệu quả và ứng
dụng các giải pháp chống tấn công định tuyến của Keith Needels trong bài

báo [8]
trên Chord để áp dụng cho mạng Chord kép.
Cấu trúc của luận văn bao gồm 4 chương:

- Chương 1 giới thiệu các khái niệm, tổng quan về mạng ngang hàng.
- Chương 2 giới thiệu tổng quan các vấn đề an ninh và phòng chống tấn
công trong cấu trúc chỉ mục phân tán.
- Chương 3 trình bày cấu trúc chỉ mục trong mô hình mạng ngang hàng
Chord kép.
- Chương 4 giới thiệu chi tiết việc xây dụng thủ tục định tuyến trong cấu
trúc chỉ mục Chord kép cùng với việc áp dụng các giải pháp an ninh
theo [8] qua việc sửa đổi chương trình mô phỏng đồng thời là các đánh
giá hiệu năng của các giải an ninh định tuyến đã nêu trong mạng Chord
kép.

10



CHƯƠNG 1: TỔNG QUAN VỀ MẠNG NGANG HÀNG
1.1. Khái niệm mạng ngang hàng
Mạng ngang hàng (peer-to-peer network) là mô hình mạng máy tính phân
tán phi tập trung, các thành phần tham gia được gọi là các nút (nodes/ peers) nối
với nhau qua các liên kết, có chức năng vừa là máy chủ, vừa là máy khách.
Mỗi tác vụ (tra cứu, phát lại các đoạn video, tải file, ) được chia sẻ giữa
các nút qua các liên kết mạng, mỗi nút lại tự đóng góp một phần tài nguyên sẵn
có (băng thông, dung lượng bộ nhớ, ) của mình cho hệ thống vì vậy thông tin
được chia sẻ giữa các nút mà không cần thiết phải có máy chủ trung tâm và vẫn
hoạt động tốt cả khi có một số nút gặp sự cố.
Hình 1.1. Mô tả cấu trúc một mạng ngang hàng.
1.2. Các ứng dụng của mạng ngang hàng
Mô hình mạng ngang hàng được ứng dụng rộng rãi trong trong thực tế từ
những ứng dụng cơ bản như chia sẻ file, cung cấp các nội dung video, điện thoại
trực tuyến đến những ứng dụng cho tính toán phân tán, đào tạo trực tuyến,

- Hệ thống chia sẻ tập tin (file): là một loại ứng dụng cơ bản của mô hình
mạng ngang hàng, các ứng dụng này kết nối các nút tham gia cho phép phân phối
và tải về các tệp tin giữa các nút. Tiêu biểu là BitTorrent (với giao thức bitTorrent),
eDonkey2000 (với giao thức overnet), KaZaA (với giao thức fastTrack) và những
hệ thống tương đương, rất hiệu quả trong việc phổ biến và chia sẻ file trên mạng
Internet nhất là các file lớn. BitTorrent sử dụng 1 chương trình ứng dụng có gọi
là BitTorrent client, mỗi BitTorrent client có khả năng so sánh, yêu cầu và vận
chuyển file trên hệ thống sử dụng giao thức bitTorrent, file có thể chứa bất kỳ
thông tin nào, bao gồm cả văn bản, âm thanh, phim và nội dung đã được mã hóa.
Tốc độ tải về của file phụ thuộc vào số lượng các nút tham gia chia sẻ. BitTorrent
11



được đánh giá cao về độ tin cậy và chi phí, theo ước tính chiếm khoảng 30% lưu
lượng trên Internet (Wikipedia). Tuy nhiên, BitTorrent cũng có 1 số nhược điểm:
không giúp ẩn danh địa chỉ người dùng, không khuyến khích các nút tham gia tái
upload dữ liệu,
- Truyền hình trực tuyến: là các ứng dụng phân phát những nội dung đa
phương tiện dựa trên mạng ngang hàng cung cấp cho người xem mọi lúc, mọi nơi
mà không cần đòi hỏi phải có thiết bị đầu cuối hoặc hệ thống mạng, thích nghi
cho những mạng lớn với môi trường có tần suất vào/ ra liên tục, ví dụ các giao
thức PPLive/ DOnet/ GridMedia hoạt động dựa trên phương thức kéo hoặc kéo-
đẩy gói tin giữa các nút, phân phối luồng các nội dung trực tuyến hoặc đã ghi sẵn.
Sự khác biệt giữa các gói tin truyền hình trực tuyến và các gói tin trong ứng dụng
chia sẻ file là phải đáp ứng thời hạn phát lại, đồng thời trong hệ thống phải tồn tại
những điểm nút có chức năng như máy chủ nhằm trợ giúp các nút mới tham gia
vào hệ thống cũng như quản lý thành viên.
- Tính toán phân tán: các ứng dụng được thiết kế nhằm tập trung nguồn lực
tài nguyên từ các máy tính trong mạng. Ý tưởng chính là tận dụng chu kỳ nhàn

rỗi của các máy tính tham gia để phân phối tính toán cho các vấn đề lớn, như
Seti@home [3] một dự án xây dựng một máy tính ảo lớn dựa trên sự nhàn rỗi của
hệ thống các máy thành phần tham gia vào một mạng ngang hàng, hệ thống gồm
có các máy chủ cơ sở dữ liệu, phân phối công việc cho mỗi nút và thu thập, tổng
hợp kết quả khi tính toán xong.
- Các ứng dụng trong đào tạo trực tuyến: được xây dựng như mô hình lớp
học ảo, các nút tham gia vào hệ thống không hưởng thụ các bải giảng được phát
trực tiếp mà còn chủ động phát lại các nội dung thu được cho các nút khác trên
cùng một kênh để tận dụng tối đa băng thông phát của tất cả các nút nhờ đó tăng
độ tin cậy, giảm thiểu chi phí đầu tư vào nguồn phát ban đầu. Mô hình đào tạo
này còn có tính tiện dụng và xã hội hóa cao, người học và giáo viên có thể ở bất
kỳ đâu chỉ cần sử dụng máy tính cá nhân có giao tiếp mạng, người học có thể
xem/ nghe bất cứ lớp học nào mà họ thích, ngoài ra hệ thống còn có tính năng cho
phép người học đặt câu hỏi trực tiếp đến giáo viên hoặc trao đổi với những người
học khác đang cùng tham gia lớp.
- Ứng dụng thoại qua Internet: một số ứng dụng sử dụng mạng Internet như
mạng nền cấu thành hệ thống, tiêu biểu là mạng Skype. Skype là một mạng điện
thoại Internet theo mô hình mạng ngang hàng được thành lập bởi Niklas
Zennström và Janus Friis (những người sáng lập ra ứng dụng chia sẻ file KaZaA).
Trong Skype thư mục người dùng được phân tán hoàn toàn trên các nút là các
máy tính tham gia mạng vì vậy rất dễ dàng trong việc mở rộng mà không đòi hỏi
12



một cơ sở hạ tầng tập trung, phức tạp và đắt tiền (đã có trên 300 triệu người dùng
trên toàn thế giới, số liệu thống kê từ Skype). Skype nổi bật nhờ các tính năng:
hội thoại, hình ảnh miễn phí, tin nhắn. Bên cạnh đó Skype còn sử dụng phương
pháp “giao tiếp an toàn” gồm tập hợp những giải thuật má hóa mạnh mẽ, phổ biến
để mã hóa các thông điệp khiến ứng dụng này trở nên đáng tin cậy.

1.3. Các mô hình mạng ngang hàng
Dựa vào cấu trúc liên kết giữa các nút mạng trong lớp mạng phủ, mạng
ngang hàng có thể được chia thành hai loại sau:
- Mạng ngang hàng không có cấu trúc,
- Mạng ngang hàng có cấu trúc.
1.3.1. Mạng ngang hàng không có cấu trúc
Là mô hình mạng có đặc điểm: liên kết giữa các nút trong mạng được thiết
lập một cách ngẫu nhiên, không theo theo 1 luật nhất định nào, vì vậy cũng không
có mỗi liên quan nào giữa nút với dữ liệu mà nó đang lưu trữ, quản lý. Một nút
khi mới gia nhập mạng sẽ kết nối với nút đang ở trong mạng, nó sao chép các liên
kết có sẵn của nút này, sau đó dần dần tự bản thân nó sẽ thêm vào các liên kết mới
cho mình. Chúng có thể đột ngột rời mạng mà không cần phải hoàn thiện bất cứ
1 thủ tục nào.
Về cơ bản để tìm kiếm dữ liệu trong mô hình này, mỗi nút sẽ sử dụng một
kỹ thuật gửi yêu cầu tìm kiếm (ví dụ: gửi tràn, ) truyền lên cả mạng, vì vậy mà
các yêu cầu tìm kiếm luôn lặp lại giữa các nút. Khi nút nhận được 1 truy vấn, nó
sẽ gửi trả lại một danh sách các nội dung đúng hoặc phù hợp với truy vấn. Hiệu
quả truy vấn thành công phụ thuộc vào số lượng nút tham gia chia sẻ dữ liệu. Các
mạng ngang hàng không cấu trúc phổ biến trong thực tế: Napster, Gnutella,…
Gnutella [13] sử dụng kỹ thuật gửi tràn để quảng bá yêu cầu tìm file lên
mạng. Có 4 kiểu thông điệp trong Gnutella, Ping: gửi yêu cầu tới máy chủ nhất
định, Pong: thông điệp trả lời ping trong đó có thông tin về địa chỉ IP/ số hiệu
cổng và số lượng file chia sẻ của máy chủ, Query: thông điệp truy vấn chứa nội
dung truy vấn có yêu cầu tốc độ chia sẻ tối thiểu, Query hit: thông điệp trả lời
query có chứa thông tin về địa chỉ IP/ số hiệu cổng/ tốc độ đáp ứng tối thiểu từ
máy chia sẻ và danh sách file chia sẻ có nội dung gần nhất với truy vấn yêu cầu.
Khi một nút đăng nhập Gnutella, nó sẽ gửi thông điệp ping tới các nút mà nó kết
nối được, các nút này gửi lại pong trả lời đồng thời quảng bá thông điệp ping của
nút mới tới các nút hàng xóm của nó. Gnutella có sử dụng tham số TTL để duy trì
thông điệp ping và query (truy vấn), gán định danh cho mỗi thông điệp để tránh

đụng độ và trùng lặp. Cuối cùng, khi nút nguồn nhận được thông điệp query hit
13



(hồi đáp), file yêu cầu sẽ được xác định trên 1 nút nào đó, nó sẽ kết nối với nút đó
và tải về thông tin. Hình dưới đây mô tả quá trình gửi tràn tìm kiếm file.
Truy vấn TTL = 2
Hồi đáp
Kết nối giữa các nút

Hình 1.2. Mô tả kỹ thuật tìm kiếm trong mạng Gnutella
Nhược điểm của mô hình mạng này là các mẫu dữ liệu được tìm kiếm, chia
sẻ nhiều thì tốc độ tìm kiếm nhanh và tỷ lệ thành công cao, ngược lại các mẫu dữ
liệu ít được chia sẻ, chỉ luân chuyển qua 1 vài nút thì yêu cầu tìm kiếm đối với
chúng ít có khả năng thành công.
1.3.2. Mạng ngang hàng có cấu trúc
Khắc phục nhược điểm của mạng ngang hàng không có cấu trúc, mạng
ngang hàng có cấu trúc sử dụng hệ thống bảng băm phân tán (DHT). Hệ thống
này định nghĩa liên kết giữa các nút trong mạng phủ theo một thuật toán cụ thể:
xác định khóa (key) cho mẫu dữ liệu, ánh xạ khóa vào nút mạng, đồng thời xác
định chặt chẽ mỗi nút sẽ chịu trách nhiệm đối với một phần dữ liệu chia sẻ. Với
cấu trúc này, khi một nút cần tìm một mẫu dữ liệu, nó “băm” dữ liệu lấy khóa và
áp dụng một giao thức chung để xác định nút nào sẽ chịu trách nhiệm cho dữ liệu
đó, sau đó liên lạc trực tiếp đến nút đó để lấy kết quả. Các mạng ngang hàng có
cấu trúc phổ biến trong thực tế: CAN, Pastry, Chord, Tapestry, Phần dưới đây
sẽ xem xét một vài mô hình mạng ngang hàng có cấu trúc.
- Mô hình mạng CAN [13]: là mô hình mạng được thiết kế cho khả năng
chống chịu lỗi, tự tổ chức, khả mở. CAN được xây dựng dựa trên kỹ thuật phân
hoạch nhiều vùng nhỏ ảo có tính chất hợp tác qua lại lẫn nhau. Không gian khóa

được chia thành các vùng ảo và phân chia cho các nút quản lý. Mỗi cặp (khóa, giá
trị) được ánh xạ vào nút quản lý vùng khóa tương ứng bởi các hàm băm. Các nút
sẽ duy trì thông tin định tuyến với các nút hàng xóm của nó, là các nút có vùng
quản lý tiếp giáp với nhau. Các nút hàng xóm này sẽ liên lạc với nhau để định
14



tuyến tìm tới các nút lưu giữ khóa ở xa hơn. Mỗi thông điệp tìm kiếm chứa tọa độ
điểm đích, một nút khi nhận được thông điệp truy vấn sẽ chuyển tiếp đến nút quản
lý vùng gần với tọa độ cần tìm nhất.
Tiến trình 3 bước khi một nút mới tham gia mạng: nút mới tìm và kết nối
với nút đã ở trong mạng; sử dụng cơ chế định tuyến CAN để tìm ra nút quản lý
vùng sẽ phân chia, gán vùng đó cho nút; tập hàng xóm của vùng phân chia sau đó
được cập nhật lại cho nút mới. Hình 1.3.a dưới đây mô tả quá trình nút 1 định
tuyến tìm nút có tọa độ (x,y). Nút 1 có tập hàng xóm là các nút {2, 3, 4, 5}, nút 1
qua nút 4 có vùng quản lý gần với nút có tọa độ (x,y) để chuyển truy vấn sang nút
4. Hình 1.3.b mô tả nút 7 gia nhập mạng CAN, vùng do nút 1 quản lý được chia
đôi, tập tập hàng xóm của nút 1 sau khi phân chia gồm {2, 3, 4, 7} và nút 7 gồm
{1, 2, 4, 5}
26
513
4
(x, y)
26
513
4
7
(a) (b)


Hình 1.3. Tìm kiếm và gia nhập mạng CAN
- Mô hình mạng Pastry [12]: được thiết kế cho những ứng dụng mạng ngang
hàng lớn có khả năng tự tổ chức, chống chịu lỗi, tin cậy và khả mở. Mỗi nút trong
Pastry được cấp một định danh số riêng không trùng lặp trong không gian định
danh m-bit (m = 128) và được phân hoạch trên vòng tròn logic có giá trị tăng theo
chiều kim đồng hồ. Khóa k là giá trị khi băm nội dung dữ liệu được ánh xạ vào
nút có định danh gần với định danh của khóa nhất. Mỗi nút chịu trách nhiệm quản
lý môt hoặc một tập hợp các khóa. Để định tuyến, mỗi nút lưu giữ các thông tin
gồm: bảng định tuyến (routing table) chứa các tham chiếu tới nút khác trong
không gian định danh; tập các nút cận (neightborhood set) và tập các lá (leaf set)
chứa các định danh gần với định danh của nút nhất. Bảng định tuyến tại một nút
trong Pastry bao gồm L/b hàng, với 2
b
-1 mục trong mỗi hàng, thứ tự hàng trong
bảng định tuyến được tính từ 0, hàng 0 là hàng trên cùng của bảng, trong bảng
định tuyến của nút n, mục ở hàng thứ i chứa các định danh của nút có i số đầu tiên
15



trong nodeID giống với i số đầu tiên trong nodeID của nút n, việc so sánh này
được tính lần lượt từng vị trí tương ứng với nhau của hai định danh và bắt đầu từ
số đầu tiên bên trái. Nếu không có định danh của nút nào thỏa mãn tính chất trên
thì vị trí đó trong bảng định tuyến để trống. Để định tuyến tìm khóa k, ban đầu nút
sẽ kiểm tra trong phạm vi tập lá, chuyển tới nút đánh số gần với khóa k nhất. Nếu
khóa k không nằm trong tập lá, nút sẽ tìm kiếm trong bảng định tuyến chuyển truy
vấn tới nút có số lượng chữ số đầu trong định danh giống với số đầu trong khóa k
nhất.
Hình dưới đây mô tả thông tin lưu tại nút có định danh nodeID = 10233102,
tập nút lá lưu trữ các nút có tiền tố 10. Bảng định tuyến với tiền tố 3 để trống do

không có nút nào thỏa mãn. Tập các nút hàng xóm chứa tham chiếu đến nút gần
với nút 10233102.

Hình 1.4. Trạng thái nút có định danh 10233102 trong Pastry
- Mô hình mạng Chord: ra đời năm 2001, ứng dụng DHT trong việc xây
dựng cấu trúc dữ liệu biểu diễn mối quan hệ giữa các nút trong mạng, gọi tắt là
bảng chỉ mục phân tán (Finger table). Mỗi nút trong mạng Chord được gán 1 định
danh duy nhất nhờ băm địa chỉ IP, định danh của khóa có được nhờ băm nội dung
thông điệp/ dữ liệu. Các nút được tổ chức trên vòng tròn modulo 2
m
(Chord ring)
có giá trị tăng theo chiều kim đồng hồ. Khóa được gán cho nút có định danh gần
với giá trị khóa nhất. Nút lưu giữ khóa k được gọi là successor(k). Quá trình định
tuyến là quá trình tìm vị trí các successor(k) được mô tả tại phần dưới đây.
16



1.4. Cấu trúc chỉ mục phân tán Chord
Bảng băm phân tán: được xem như là một cấu trúc dữ liệu phân tán, có khả
năng cung cấp dịch vụ tra cứu/ tìm kiếm tương tự như một bảng băm, các cặp
(khóa, giá trị) được lưu trữ trong DHT và ánh xạ vào các nút của hệ phân tán. Bất
kỳ 1 nút nào trong hệ thống cũng có thể tìm và lấy được giá trị liên kết với một
khóa cho trước một cách hiệu quả.
Text/
Documents
Images/
videos
Other data
Hash

function
DFCE3453
FFE2379E
46042841
Data Key Ditributed network

Hình 1.5. Mô hình bảng băm phân tán (Wikipedia)
Mạng ngang hàng Chord: sử dụng hàm băm SHA-1 (hàm băm được giới
thiệu năm 1995 bởi Cơ quan an ninh Quốc gia Mỹ, gồm 160 bit định danh) và kỹ
thuật “consistent hashing” để gán khóa cho mỗi nút. Trong đó, định danh của nút
(identifier) có được nhờ “băm” địa chỉ IP, “băm” nội dung thông điệp, dữ liệu,
sẽ cho giá trị định danh của khóa (key).
Các định danh được tổ chức trên một mạng logic hình tròn modulo 2
m
(m
là số bit định danh) tăng theo chiều kim đồng hồ với m vị trí nút từ 0 đến 2
m-1
.
Một khóa k được gán cho nút đầu tiên có giá trị định danh bằng hoặc lớn hơn gần
nhất so với khóa k, nút đó được gọi là successor của khóa k, ký hiệu successor(k).
Ngược lại, một nút có định danh liền sau khóa k được gọi là predecessor(k).
Hình dưới đây mô tả mạng Chord được tổ chức trên vòng tròn có m=6 bit
định danh. Với 6 bít định danh sẽ có 32 vị trí nút tính từ vị trí 0, có 10 nút tham
gia lưu trữ 5 giá trị khóa. Successor(10) - successor của key có giá trị bằng 10 -
là nút có định danh bằng 14 vì N14 là nút đầu tiên trên vòng tròn có giá trị định
danh lớn hơn gần với K10 nhất, tương tự nút N32 lưu trữ 2 khóa có giá trị K24,
K30. Như vậy trong mạng Chord cho phép một nút có thể lưu giữ nhiều giá trị
khóa nhưng định danh mỗi nút là duy nhất.
17





Hình 1.6. Mô tả mạng Chord có 6-bit định danh
Mỗi nút có lưu một cấu trúc dữ liệu dạng bảng chứa thông tin là vị trí các
nút lân cận, bảng này gồm có m mục gọi là bảng chỉ mục phân tán (finger table).
Mục thứ i trong bảng chỉ mục phân tán của nút n trỏ tới định danh của nút s, là
nút đầu tiên trên vòng Chord kế tiếp giá trị n + 2
i-1
, hay s = successor(n+2
i-1
) (lấy
modulo 2
m
) với 1 ≤ i ≤ m. Node s được gọi là chỉ mục (finger) thứ i của node n,
ký hiệu n.finger[i] (chi tiết xem bảng 1.1 dưới đây):
Ký hiệu
Định nghĩa
finger[i]
Nút đầu tiên trên vòng tròn định danh kế tiếp giá trị:
(n+2
i-1
) mod 2
m
, 1 ≤ i ≤ m
successor
Nút tiếp theo trên vòng tròn định danh
finger[1].node
predecessor
Nút liền trước trên vòng tròn định danh

Bảng 1.1. Định nghĩa bảng chỉ mục phân tán Chord
Ví dụ: tổ chức bảng chỉ mục phân tán của nút N8 trên vòng tròn định danh
có 6-bit, chỉ mục thứ nhất của N8 trỏ đến nút N14 vì N14 là nút đầu tiên kế tiếp
sau (8 + 2
0
) mod 2
6
= 9. Chỉ mục tiếp theo trỏ đến nút N14 vì N14 là nút gần nhất
so với giá trị (8 + 2
1
) mod 2
6
= 10
18



Chỉ mục cuối cùng (8 + 2
4
) mod 2
6
= 40 sẽ trỏ đến nút có định danh = 42
Hình 1.7. Mô tả bảng chỉ mục phân tán tại một nút trên Chord
Tìm kiếm: để tìm kiếm giá trị gắn với khóa k, nút tìm kiếm phải định vị
được nút successor(k) trên vòng tròn, thuật toán dưới đây mô tả quá trình tìm
kiếm/ định tuyến successor(k) tại một nút trong Chord
Hình 1.8. Mã giả thuật toán tìm successor(id)
Ví dụ, nút N8 cần tìm khóa K54, trên vòng Chord khóa K54 được lưu tại
nút có định danh N56 (giá trị K54 nằm giữa giá trị N51 và N56, N56 là nút lớn
hơn gần K54 nhất trên vòng tròn định danh).

Ban đầu N8 tìm successor(K54) trong khoảng (N8, N14], tuy nhiên giá trị
K54 > giá trị N14 nên nó sẽ chuyển sang tìm kiếm successor gần K54 nhất trong
khoảng (N14:N42]. Chỉ mục cuối của nút N8 trỏ đến nút N42 là nút có định danh
gần với giá trị K54, N8 chuyển truy vấn đến N42. N42 tiếp tục tìm kiếm
successor(K54) trong khoảng (N42, N48], vì không có kết quả phù hợp, N42
19



chuyển truy vấn đến N51. N51 lặp lại quá trình trên và tìm được successor(K54)
= N56, kết quả được trả về cho N8 thông qua tuyến định tuyến đã đi qua. Quá
trình cần 3 bước chuyển (hop) để tìm được nút đích.
Hình 1.9. Mô tả quá trình tìm successor của khóa K54
Nút mới tham gia mạng: trong mạng thực, nút có thể vào/ ra ngẫu nhiên.
Có 3 bước thủ tục cần cho các tình huống này, giải sử nút n tham gia mạng
- Thiết lập nút predecessor và bảng chỉ mục cho n,
- Cập nhật bảng chỉ mục và nút predecessor,
- Thông báo đến các tầng trên về việc gia nhập thành công và sẵn sàng hồi
đáp truy vấn đến khóa mà nó vừa được trao.
Hình dưới đây mô tả quá trình nút N26 gia nhập mạng. Nút N26 được đặt
vào khoảng giữa nút N21 và N32, N26 tìm nút successor của nó và trỏ tới N32,
N21 trở thành nút predecessor của N26 (hình 1.11.b). Tiếp theo N26 sao chép các
giá trị khóa nằm trong khoảng từ 26 đến 31 (hình 1.11.c). Cuối cùng nó khởi chạy
thủ tục ổn định để trở thành nút successor của N21 (hình 1.11.d).

Hình 1.10. Mô tả quá trình nút N26 gia nhập mạng Chord
20




CHƯƠNG 2: AN NINH CHO CẤU TRÚC CHỈ MỤC PHÂN TÁN
2.1. Giới thiệu
DHT cung cấp một cơ chế cho phép triển khai những hệ thống mạng ngang
hàng phân tán không tập trung có khả năng mở rộng và chống chịu lỗi tốt. Không
thể phủ nhận những lợi điểm mà cơ chế DHT tạo ra.Tuy nhiên nó cũng luôn tồn
tại những vấn đề an ninh, an toàn định tuyến nhất là với cấu trúc chỉ mục phân tán
dựa trên DHT. Dưới đây sẽ xem xét các cách thức mà kẻ tấn công có thể lợi dụng
và hậu quả mà chúng gây ra cho hệ thống cũng như các giải pháp phòng tránh.
Dựa theo cách thức, hình thức tấn công, có thể chia thành các loại sau đây
- Tấn công dữ liệu [8]
- Tấn công lợi dụng quá trình cấp phát định danh [7], [16]
- Tấn công định tuyến [8]
2.2. Tấn công dữ liệu và phương pháp phòng chống
Đây là cách tấn công đơn giản nhất nhắm vào giao thức sử dụng DHT, kẻ
tấn công có thể từ chối cung cấp dữ liệu liên kết với khóa được yêu cầu truy vấn,
thay đổi dữ liệu hiện đang lưu trữ. Tính toàn vẹn dữ liệu được coi như vấn đề an
ninh mức ứng dụng. Tuy nhiên sẽ ra sao nếu như một nút đã định vị đúng nút chứa
khóa k chịu trách nhiệm về dữ liệu gắn với khóa nhưng lại không được cung cấp
nội dung dữ liệu đó.
Giải pháp khắc phục cuộc tấn công này dùng kỹ thuật “tạo bản sao”
(replication) rất phổ biến trong hệ quản trị cơ sở dữ liệu, bằng cách kết hợp khóa
với nhiều nút khác nhau.
Nhiều giao thức dựa trên DHT có thiết kế sẵn cơ chế tạo bản sao. Trong
mạng Chord, cơ chế tạo bản sao được triển khai với một nhóm các nút cùng nắm
giữ một khóa. Pastry tổ chức các bản sao tới các nút xung quang nút gốc trên vòng
tròn. CAN sử dụng nhiều hàm băm khác nhau sinh khóa cho cùng một mẫu dữ
liệu, các khóa này sẽ được phân phối ngẫu nhiên đến các định danh trong mạng.
Tuy nhiên, khi kẻ tấn công từ chối cung cấp dữ liệu gắn với khóa tại nút
nhiễm độc, việc tra cứu sẽ phải kiểm tra các bản sao của khóa để chắc chắn dữ
liệu không tồn tại, nghĩa là sẽ phải sử dụng song song nhiều hàm băm, việc này

tiêu tốn đáng kể thời gian truy vấn.
21



2.3. Tấn công lợi dụng quá trình cấp phát định danh
Loại hình tấn công này nhắm vào các lỗ hổng của quá trình cấp phát định
danh cho một nút mới tham gia mạng. Dưới đây xem xét 2 loại hình tấn công phổ
biến gồm
- Tấn công giả mạo (Sybil attack) [7],
- Tấn công che khuất (Eclipse attack) [16].
2.3.1. Tấn công giả mạo và phương pháp phòng chống
Tấn công giả mạo trong mạng ngang hàng là cuộc tấn công phá hoại dựa
vào sự không an toàn của hệ thống cấp phát định danh, bằng cách tạo ra một lượng
lớn các nút ảo và sử dụng chúng để gây ảnh hưởng đến hệ thống mạng.
Lợi dụng đặc tính của mạng ngang hàng dựa trên DHT, mỗi nút trong mạng
cần duy trì một cơ sở dữ liệu là các định danh của các nút mà nó liên kết đến. Cấu
trúc của tập này được hình thành theo quy tắc riêng đối với từng loại mạng cụ thể.
Khi một nút mới gia nhập mạng, hệ thống sẽ cấp phát cho nó 1 định danh. Kẻ tấn
công khi biết định danh của nút có thể sinh ra một tập các định danh ảo nhằm đưa
các định danh ảo này vào tập các nút liên kết (tập nút hàng xóm), quá trình sẽ dần
thành công và kẻ tấn công dựa vào các định danh ảo để kiểm soát lưu lượng, kiểm
soát định tuyến, dữ liệu và các thông tin truyền trong mạng.
Các loại tấn công giả mạo nhắm vào cấu trúc chỉ mục:
- Kẻ tấn công tạo ra hàng loạt nút Sybil có định danh nhất định, chúng sẽ
chặn bắt các truy vấn sau đó trả lại thông tin sai hoặc vứt bỏ.
- Kẻ tấn công nhắm vào 1 nút nào đó, để tiến hành tấn công, kẻ tấn công
phỏng đoán định danh của nút sau đó tạo ra một loạt các nút có định danh gần
giống định danh của nút nạn nhân và gây ảnh hưởng tới các truy vấn đến khóa.
Nút nạn nhân

Nút Sybil

22



Hình 2.1. Một kiểu tấn công Sybil
Giải pháp chống lại cuộc tấn công giả mạo là hệ thống phải đảm bảo mỗi
định danh được cấp cho mỗi nút là duy nhất và hạn chế khả năng xác định danh
tính bằng sự tin cậy từ trung tâm chứng thực ủy quyền. [1] có đề xuất phương án
dùng trung tâm chứng thực có thu phí để cấp định danh nhằm hạn chế việc sinh
định danh. Một số ý tưởng khác đề xuất buộc nút mới tham gia phải giải quyết
các câu đố ngẫu nhiên. Tuy nhiên đây là một thách thức không nhỏ khi câu đố
phải đơn giản để máy gia nhập dễ dàng giải quyết nhưng cũng phải đủ mạnh để
ngăn chặn kẻ tấn công.
2.3.2. Tấn công che khuất và phương pháp phòng chống
Cũng như kiểu tấn công giả mạo, tấn công che khuất cũng lợi dụng quá
trình cấp phát định danh ban đầu để thâm nhập mạng. Kẻ tấn công sẽ cố gắng tìm
cách điều khiển một lượng lớn các đối tượng là các nút thành viên trong tập hàng
xóm của nút nạn nhân, các nút bị điều khiển gọi là các nút gây hại sẽ “che khuất”
nút nạn nhân đối với các nút khác trong mạng, khi nút nạn nhân muốn gửi dữ liệu
hoặc chuyển tiếp các thông tin định tuyến, nó sẽ phải liên lạc với các nút trong
tập hàng xóm, trong trường hợp tồi nhất tất cả các nút của tập hàng xóm đều nhiễm
độc thì mọi thông tin vào ra từ nút nạn nhân sẽ bị kiểm soát và điều khiển, dữ liệu
hoặc các thông tin định tuyến có thể không bao giờ tới đích.
Lỗ hổng an ninh trong hệ thống cấp phát định danh ban đầu khi nút mới
tham gia mạng sẽ bị kẻ tấn công lợi dụng để đưa vào mạng một số lượng nút
nhiễm độc ban đầu, các nút này lại có thể đưa thêm các nút nhiễm độc khác tham
gia hệ thống.
Một cách khác cũng có thể khiến nút nhiễm độc xâm nhập vào tập hàng

xóm của nút nạn nhân đó là thực hiện theo chu kỳ quá trình duy trì liên kết mạng
vốn là các đặc tính của loại mạng dựa trên DHT, quá trình sẽ tìm và loại bỏ các
nút bị lỗi ra khỏi các tập hàng xóm đồng thời thay thế vào đó các nút khác đang
hoạt động. Các nút nhiễm độc sẽ lợi dụng thời điểm này này để làm tăng số lượng
các nút nhiễm độc trong các tập hàng xóm của các nút nạn nhân
Tuy nhiên, cuộc tấn công che khuất cần 1 lượng nhất định các nút nhiễm
độc thông đồng với nhau để đảm bảo “che khuất” làm cho các nút nạn nhân chỉ
biết đến chúng, mọi liên hệ khác với mạng đều bị chi phối và khống chế bởi các
nút nhiễm độc.
Giải pháp khắc phục cuộc tấn công che khuất dựa vào các ràng buộc trong
việc lựa chọn tập các nút hàng xóm, phải đảm bảo tập này luôn luôn an toàn trước
23



các nút gây hại như ràng buộc mạnh mẽ trong cấu trúc, ràng buộc gần hoặc cơ chế
giới hạn bậc, kiểm tra ẩn danh.

Hình 2.2. Mô tả kiểu tấn công che khuất Eclipse
2.4. Tấn công định tuyến và phương pháp phòng chống
Tìm kiếm và định tuyến trong cấu trúc chỉ mục tại mỗi nút phụ thuộc nhiều
vào sự liên kết giữa các nút xung quanh vì vậy việc đảm bảo an toàn cho quá trình
định tuyến là yếu tố quan trọng nhất, kẻ tấn công có thể điều khiển một lượng nhỏ
các nút nhiễm độc nhưng có thể gây ảnh hướng lớn đến hệ thống, hình 3.3 dưới
đây cho thấy chỉ tối đa 20% nút nhiễm độc đã gây ảnh hưởng đến 60% sự thành
công của các truy vấn

Hình 2.3. Ảnh hưởng của nút nhiễm độc đến sự thành công truy vấn
Có 2 phương pháp định tuyến dựa vào bảng chỉ mục: phương pháp lặp và
đệ quy. Đệ quy là phương pháp mà một yêu cầu tra cứu xuất phát từ 1 nút, theo

0
10
20
30
40
50
60
70
80
90
100
0 5 10 15 20
Tỷ lệ thành công của truy vấn tìm kiếm
Tỷ lệ % nút nhiễm độc
24



bảng chỉ mục nó gửi yêu cầu này tới nút hàng xóm, các nút này lại tiếp tục gửi đi
yêu cầu tới các nút khác cho đến khi tìm được nút đích, nghĩa là truy vấn được
chuyển tiếp từ nút này đến nút khác, nút đích theo đường định tuyến đã định sẽ
gửi hồi đáp về nút nguồn, nút nguồn không điều khiển quá trình tìm đường đến
nút đích. Ngược lại, định tuyến lặp cho phép nút nguồn điều khiển quá trình tìm
đường đến đích, khi phát ra yêu cầu truy vấn gửi tới 1 nút, nó sẽ đợi câu trả lời
của nút đó về nút đến tiếp theo của truy vấn sau đó sẽ quyết định chuyển tiếp truy
vấn. Nhược điểm của phương pháp lặp là tiêu tốn gấp 2 lần thời gian so với định
tuyến đệ quy.
Cả 2 phương pháp định tuyến trên đều rất dễ bị tổn thương khi gặp phải nút
nhiễm độc trên tuyến đường định tuyến. Nút nhiễm độc có thể không hồi đáp truy
vấn, hoặc chuyển tiếp truy vấn đến 1 đích sai hoặc đến 1 nút nhiễm độc khác,

Nút bị nhiễm độc theo 1 cách tự nhiên, không cần nhắm đến lỗ hổng cấp phát định
danh vì ban đầu chúng là các nút sạch nhưng bị kẻ tấn công lợi dụng biến chúng
trở thành nút nhiễm độc.
Hình 2.4. Mô tả một kiểu tấn công định tuyến nhắm vào bảng chỉ mục
Giải pháp chống lại tấn công định tuyến của [8] và giải pháp cải tiến [12]
áp dụng trên mạng Chord đã chứng minh được sự hiệu quả khi sử dụng kết hợp
các phương pháp theo mô hình:
- Định tuyến tương tác: giám sát quá trình định tuyến đến đích.
- Xác thực mỗi bước chuyển tiếp truy vấn.
- Quay lui khi xác thực thất bại.
Tìm(Hanoi)
Hash
Fuction
Hash(Hanoi)
Return 1665
130-295
296-203
504-667
668-800
801-111
122-195
110-255
Host
142.21.63.157
1665: Hanoi
11: Kline
99-150
Lookup(1665)
Return 66.65.66.65
Host

66.65.66.65
1665: Hanoi
25



2.4.1. Định tuyến tương tác
Theo thiết kế định tuyến trong Chord, mỗi nút sẽ dựa vào bảng chỉ mục của
mình để chuyển các yêu cầu tra cứu, một nút nào đó có định danh trong bảng chỉ
mục sẽ nhận được yêu cầu tra cứu từ nút nguồn, chúng tiếp tục chuyển yêu cầu
đó tới các nút tiếp theo, quá trình được lặp lại cho đến khi gặp nút đích là successor
của khóa muốn tìm. Như vậy nút nguồn chỉ trao yêu cầu tra cứu cho nút hàng xóm
của mình, sau đó chờ kết quả mà không có bất cứ trao đổi hoặc điểu khiển nào
với các nút hàng xóm. Đây chính là lỗ hổng mà kẻ tấn công sẽ nhắm vào để thay
đổi kết quả truy vấn.
Để điều khiển, giám sát quá trình định tuyến thay vì việc trao truy vấn tới
mỗi nút tham chiếu thì sử dụng phương pháp định tuyến có sự tương tác. Nút
nguồn sẽ chuyển yêu cầu định tuyến cho các nút hàng xóm của nó, sau đó nhận
thông tin chuyển tiếp sang nút mới từ các nút này, nút nguồn sẽ tự quyết định
chuyển tiếp hay không qua quá trình xác thực.
2.4.2. Giá trị khoảng cách trung bình
Quá trình xác thực nút sẽ dựa trên sự tính toán giá trị khoảng cách trung
bình giữa các nút liên tiếp nhau. Để tính giá trị trung bình, bảng chỉ mục giờ đây
lưu thêm các thông tin định danh của các nút successor, predecessor. Đồng thời
sử dụng cơ chế xén-tỉa để loại bỏ các khoảng cách tới những nút bị nhiễm độc
(những nút bị nhiễm độc có xu hướng tạo ra các “khoảng cách” lớn hoặc nhỏ hơn
khoảng cách trung bình). Trong suốt quá trình định tuyến sẽ sử dụng giá trị này
để xác thực nút đích của mỗi bước chuyển của tuyến đường định tuyến. Nếu nút
tiếp theo của tuyến đường định tuyến thất bại trong việc xác thực (có tỷ lệ cao là
nút nhiễm độc) thì nút này sẽ được thêm vào danh sách đen, đồng thời tiến trình

định tuyến sẽ lùi lại 1 nút trước nút hiện tại và tiếp tục định tuyến theo hướng mới
Nút khởi tạo truy vấn
Khoảng cách giữa các nút liên tiếp
Nút tham chiếu trong bảng chỉ mục