MỤC LỤC
Chương 2: CÁC THUẬT TOÁN CỔ ĐIỂN 13
2.1. Tìm kiếm tuần tự 13
2.3. Trie nhị phân (Binary Trie) 17
2.3.1. Tìm kiếm 18
2.3.2. Chèn tiền tố 19
2.3.3. Xoá tiền tố 20
2.3.4. Thực thi 20
2.4. Trie được nén đường dẫn 21
2.5. Cây tiền tố thay đổi (DP trie) 23
2.5.1. Định nghĩa và cấu trúc dữ liệu 23
2.5.2. Thuật toán của DP trie 26
2.5.2.1. Chèn 1 khoá mới 26
2.5.2.2. Xoá một khoá 28
2.5.2.3. Tìm kiếm 30
1
LỜI NÓI ĐẦU
Trước đây, mạng Internet chỉ cung cấp một dịch vụ để giải quyết với
tất cả các gói tin đến cùng một đích xác định, và phục vụ theo phương thức
đến trước phục vụ trước (First Come First Serve). Tuy nhiên, sự phát triển
nhanh chóng của Internet cùng với hàng loạt các dịch vụ mạng là nguyên
nhân làm gia tăng sự tắc nghẽn và mất gói tin tại các thiết bị định tuyến. Do
đó Router Internet cần tiến hành phân loại nhanh chóng các gói tin để giảm
các nút thắt của mạng nhằm phục vụ cho một số lượng lớn các dịch vụ
mạng yêu cầu phân loại gói tin như: định tuyến, điều khiển truy nhập trong
firewalls, mạng riêng ảo (Virtual Private Network - VPN), lập hóa đơn
mạng (Traffic Billing) và chất lượng dịch vụ (Quality of Service - QoS).
Cho đến hiện nay, nhiều chuyên gia đã nghiên cứu nhằm tìm ra các
giải pháp tốt nhất cho việc phân loại gói tin. Phân loại gói tin đa chiều là
một kỹ thuật khó, do đó các nhà nghiên cứu đã đưa ra nhiều thuật toán khác
nhau. Mỗi thuật toán đều có những ưu điểm và nhược điểm riêng về độ

đường đi tốt nhất cho các gói tin qua nhiều kết nối để đi từ trạm gửi thuộc
mạng đầu đến trạm nhận thuộc mạng cuối. Router có thể được sử dụng
trong việc nối nhiều mạng với nhau và cho phép các gói tin đi theo nhiều
đường khác nhau tới đích.
Router có địa chỉ riêng và chỉ tiếp nhận, xử lý các gói tin gửi đến nó
mà thôi. Khi một trạm muốn gửi gói tin qua Router thì trạm đó phải gửi gói
tin tới địa chỉ trực tiếp của Router. Khi có gói tin đến, Router xử lý và gửi
tiếp.
Khi xử lý một gói tin, Router phải tìm được đường đi của gói tin qua
mạng. Để làm được điều đó nó phải tìm được đường đi tốt nhất trong mạng
dựa trên các thông tin đã có về mạng trên bảng định tuyến.
Để ngăn chặn việc mất mát số liệu, Router còn phải nhận biết đường
nào có thể truyền và ngừng truyền khi đường bị tắc bằng cách cài đặt các
phương thức tránh tắc nghẽn.
Các phương thức hoạt động của Router đảm bảo cho nó có thể nối
được với các Router khác, qua đó chia sẻ thông tin về mạng hiện có. Các
chương trình chạy trên Router sẽ xây dựng bảng chỉ đường thông qua việc
trao đổi các thông tin với các Router khác.
4
Trong phương thức vector khoảng cách, mỗi Router luôn truyền đi
các thông tin về bảng định tuyến của mình trên mạng, thông qua đó các
Router khác sẽ cập nhật lên bảng chỉ đường của mình.
Trong phương thức trạng thái tĩnh, các Router chỉ truyền các thông
báo khi phát hiện có sự thay đổi trong mạng và chỉ khi đó các Router tự cập
nhật lại bảng định tuyến, thông tin truyền đi khi đó thường là thông tin về
đường truyền.
1.2 Định tuyến trên Internet
1.2.1 Khái niệm về định tuyến
Định tuyến là tiến trình học tất cả các hướng đi trong một mạng và
chuyển tiếp các gói tin trên các hướng đi này. Một cách cụ thể, định tuyến

1. Phân phát nhanh và chính xác các gói tin
2. Khả năng thích nghi với những thay đổi cấu hình mạng là kết
quả từ một nút hoặc một đường kết nối bị đứt
3. Thích nghi với việc thay đổi địa chỉ nguồn – đích tải lưu
lượng
4. Khả năng gửi các gói tin ra khỏi các đường liên kết bị tắc tạm
thời
5. Khả năng kiểm tra sự kết nối của mạng
6. Chi phí thấp
1.3 Bảng định tuyến
Router chuyển tiếp các gói tin dựa trên địa chỉ IP đích trong phần
Header của gói tin. Nó so sánh địa chỉ đích với bảng định tuyến để tìm ra
một lối khớp, lối này sẽ cho Router biết gói tin sẽ được chuyển đi đâu tiếp.
6
Nếu Router không khớp một lối nào trong bảng định tuyến và không có
đường mặc định nào thì nó sẽ hủy gói tin. Vì vậy, cần phải có một bảng
định tuyến đầy đủ và chính xác.
Một nút mạng hay một Router phải xem xét bảng định tuyến của
mình trước khi chuyển gói tin đến địa chỉ ở xa. Trong bảng, mỗi địa chỉ
đích được gán tương ứng với một địa chỉ Router cần đến ở chặng tiếp theo.
Mục đích:
- Lưu trữ thông tin về các mạng con khác trong mạng và cách để đến
được các nút mạng trong mạng đó.
- Chỉ ra địa chỉ IP nào trong bài toán định hướng tiếp theo để đến
được nút mạng đích.
- Chỉ ra giao diện mạng được sử dụng để chuyển gói tin tới đích.
Mỗi bảng định tuyến bao gồm rất nhiều thành phần. Trong phạm vi
đồ án ta giả sử đã có một bảng định tuyến như bảng 1.1, bao gồm các
trường sau:
Rule Name: tên của quy tắc

Trong IPv4, W = 32 và trong IPv6, W = 128. Trong bảng 1.1, với W = 5,
tiền tố P1 khớp với tất cả các địa chỉ đích, được gọi là default prefix. Tiền
tố P3 khớp với các địa chỉ từ 16 đến 19. Nếu một địa chỉ tiền tố của một
quy tắc khớp với địa chỉ đích của các gói tin đến, Next Hop của quy tắc này
sẽ được sử dụng để định hướng gói tin.
Khi một địa chỉ đích đến khớp với nhiều quy tắc trong bảng định
tuyến thì việc chọn một Next Hop nào đó phụ thuộc vào phương pháp khớp
tiền tố. Có ba biện pháp so khớp thông dụng khác nhau:
Biện pháp khớp tiền tố đầu tiên, bảng quy tắc giả sử là một danh
sách tuyến tính của các luật với chỉ số từ 1 đến n, cho một bảng có n quy
tắc. Quy tắc đầu tiên khớp với gói tin đến được sử dụng để định tuyến gói
tin. Ví dụ khi địa chỉ đích đến là 19 thì Next Hop là N1, vì tiền tố * là tiền
tố đầu tiên khớp với địa chỉ 19. Nhận thấy quy tắc R1 khớp với tất cả các
địa chỉ đích. Tuy nhiên khi định tuyến tất cả các gói tin theo quy tắc R1 thì
kết quả việc định tuyến khó thể nói sẽ xảy ra điều gì. Do vậy đánh thứ tự
cho các quy tắc phải thay đổi để các quy tắc khác có thể được sử dụng, tiền
tố mặc định nên đặt ở cuối bảng quy tắc.
8
Trong khớp tiền tố có độ ưu tiên cao nhất, mỗi quy tắc được gán một
độ ưu tiên, và một quy tắc với độ ưu tiên cao nhất được chọn từ các quy tắc
khớp với gói tin đến (giả sử rằng các độ ưu tiên của các tiền tố khác nhau).
Để tránh khả năng sử dụng thêm biện pháp quyết định nữa thì phải gán giá
trị ưu tiên khác nhau cho các luật khác nhau. Biện pháp khớp đầu tiên là
biện pháp đặc biệt của khớp có độ ưu tiên cao nhất.
Khớp đặc trưng nhất: trong tất cả các tiền tố cùng khớp với địa chỉ
đích thì tiền tố nào đặc trưng nhất sẽ được chọn để định tuyến gói tin. Bộ
lọc F1 được gọi là đặc trưng hơn bộ lọc F2 nếu F2 khớp với tất cả các gói
tin mà được khớp bởi F1 và ít nhất có một gói tin không khớp với F1. Ví
dụ: đoạn [2,4] đặc trưng hơn [1,6], và [5,9] khớp đặc trưng hơn [5,12]. Vì
[2,4] và [8,14] không chứa nhau nên không thể so sánh đoạn nào đặc trưng

chính và bộ lưu trữ của bảng làm việc được xóa. Trong kiểu cập nhật này,
nhiều gói tin phân loại sai được định tuyến, do việc copy không được thực
hiện ngay lập tức. Số lượng các gói tin bị phân loại sai phụ thuộc vào chu
kỳ cập nhật của bảng làm việc. Do vậy cần giảm thời gian tiền xử lý để
giảm số gói tin đã phân loại bị định tuyến sai.
Hơn nữa, để cập nhật bảng tĩnh, phải thêm bộ nhớ cho bảng phụ và
cho việc xây dựng lại theo chu kỳ của bảng làm việc.
Qua các đặc điểm cơ bản của bảng định tuyến tĩnh, ta nhận thấy loại bảng
này có một số ưu nhược điểm nhất định. Việc cập nhật được thực hiện bằng
tay nên người quản trị có toàn quyền điều khiển thông tin trong bảng định
tuyến. Tuy vậy, khi kích thước của mạng tăng lên
3
, độ phức tạp của việc
cấu hình tăng lên. Bảng định tuyến kiểu này không có khả năng thích ứng
với mạng có cấu trúc thay đổi. Trên thực tế, loại bảng này rất ít được sử
dụng.
1.3.2 Bảng định tuyến động
Định tuyến động là quá trình mà trong đó giao thức định tuyến phải
tìm ra đường tốt nhất trong mạng và duy trì chúng. Gói tin có thể đến được
3
Giả sử một mạng có n Router thì cần phải cấu hình n*(n-1) câu lệnh trên tất cả các Router.
10
đích tùy thuộc vào sự tồn tại và trạng thái của mạng đó. Nếu một đích rời
khỏi mạng, đường đi tới đích đó sẽ bị mất đi trong bảng định tuyến, và gói
tin sẽ không được gửi tới đích đó.
Có rất nhiều cách để xây dựng bảng định tuyến động. Nhưng tất cả
đều thực hiện theo quy tắc chung sau: Router sẽ khám phá tất cả các tuyến
đường đến đích có thể và thực hiện một số quy tắc đã định trước để xác
định ra đường tốt nhất đến đích.
Trong một bảng quy tắc động, các quy tắc được chèn/xóa thường

động để giảm thời gian cập nhật của bảng.
12
Chương 2: CÁC THUẬT TOÁN CỔ ĐIỂN
Với sự phát triển mạnh mẽ của Internet, thì việc tối ưu hóa vấn đề
tìm kiếm địa chỉ IP đã được rất nhiều nhà nghiên cứu chú ý đến. Dưới đây
là một số thuật toán tìm kiếm địa chỉ IP cổ điển:
2.1. Tìm kiếm tuần tự
Danh sách liên kết là một trong những cấu trúc dữ liệu đơn giản nhất.
Việc tạo ra danh sách mọi tiền tố cho bảng chuyển tiếp cũng khá dễ dàng.
Cần phải duyệt hết danh sách liên kết mới có thể tìm ra tiền tố dài nhất
khớp.
Tiền tố Chuỗi
P
1
0*
P
2
00001*
P
3
001*
P
4
1*
P
5
1000*
P
6
1001*

tiền tố hoặc địa chỉ đích. Khi bít i là 0, thì ta di chuyển đến cây con trái; khi
bit i là 1 thì ta di chuyển đến cây con phải. Hình 2.4 là ví dụ 8 tiền tố và
biểu diễn tương ứng của chúng trên cây 1 bit.
Với bất kỳ địa chỉ đích d nào, tất cả các tiền tố mà khớp với d nằm
trên đường tìm kiếm sẽ được xác định bằng các bit của d. Bằng cách theo
đường tìm kiếm, ta có thể xác định được tiền tố khớp dài nhất, tiền tố đầu
14
tiên trong bảng khớp với d cũng như độ ưu tiên cao nhất của tiền tố khớp
trong thời gian O(W). Hơn nữa các tiền tố có thể được chèn hoặc xóa trong
thời gian O(W). Không gian nhớ yêu cầu là O(nW)
Hình 2.3: 8 tiền tố và biểu diễn tương ứng trên cây 1 bit
Router backbone IPV4 có thể có nhiều hơn 100 ngàn tiền tố. Thậm
chí các tiền tố trong một router backbone có thể có chiều dài bất kỳ giữa 0
và W, các tiền tố tập trung ở chiều dài từ 16 đến 24, bởi vì ở thời kỳ đầu thì
địa chỉ Internet được phân phối theo các lớp. Tất cả các địa chỉ trong mạng
lớp B có cùng 16 bit đầu tiên, trong khi các địa chỉ trong lớp C có cùng 24
bit đầu tiên, các địa chỉ trong lớp A có cùng 8 bit đầu tiên. Tuy nhiên, có
thể có nhiều nhất 256 mạng lớp A (tương đương với nhiều nhất 256 tiền tố
8 bit trong bảng luật).
2.2.2 Cây tìm kiếm ưu tiên
Cây tìm kiếm ưu tiên là một cấu trúc dữ liệu được sử dụng để biểu
diễn một bộ có dạng (key1, key2, data) với
,key key³ ³1 0 2 0
và không có
hai bộ nào có cùng giá trị key1. Cấu trúc dữ liệu đồng thời xảy ra là cây
nhỏ nhất trên key2 (nghĩa là giá trị key2 trong mỗi node của cây thì
key£ 2

trong mỗi node con) và cây tìm kiếm trên key1. Có hai cây PST phổ biến
là:

top
) =
enumerateRectangle(d,
¥
,d) của một PST (y
bottom
luôn bằng 0)
Khi một RPST được sử dụng để biểu diễn tập điểm P thì độ phức tạp
của enumerateRectangle(x
left
,x
right
,y
top
) là O(logmaxX + s) với maxX là giá
trị x lớn nhất trong P và s là số lượng điểm trong truy vấn hình chữ nhật.
Khi tập điểm được biểu diễn như một RBPST thì độ phức tạp là O(logn+s),
với n= |P|. Một điểm (x,y)có thể được chèn vào hoặc xóa khỏi RPST (hoặc
RBPST) trong thời gian O(log maxX) (hoặc O(log n)).
Cho R là một tập đoạn tiền tố. Để đơn giản, ta giả sử rằng R bao gồm
các đoạn tương ứng với các tiền tố *. Với giả sử này, LMP(d) được định
nghĩa cho mỗi d. Có thể xác nhận rằng LMP(d) là tiền tố mà đoạn của nó là
[maxStart(ranges(d)),minFinnish(ranges(d))]. Để tìm kiếm đoạn này một
cách dễ dàng, đầu tiên ta chuyển đổi P=map1(R) thành một tập điểm
transform1(P) để không có hai điểm nào của transform1(P) có cùng giá trị
16
x. Sau đó, ta biểu diễn transform1(P) như một PST. Với mỗi (x,y)
Î
P, định
nghĩa transform1(x,y)=(x’,y’)=(2

X c gle d d d- + - ¥2 2 1
thực hiện trên PST1 thu được
LMP(P).
Để chèn một tiền tố mà đoạn của tiền tố là [u,r], ta chèn
tranform1(map1[u,v])) từ PST1.
Do đó, minXin Rectangle, chèn, xóa tốn thời gian O(W)(O(log n)) khi
PST1 là một RPST (hoặc RBPST).
2.3. Trie nhị phân (Binary Trie)
Binary Trie hoặc còn gọi là trie. Trie là viết tắt của từ
“retrieval”.Trong trie các nhánh được gán nhãn, nhánh trái của một nút
được gán nhãn “0”, nhánh phải được gán nhãn “1”. Mỗi nút n trong một
trie đại diện cho một chuỗi bit, Chuỗi bit này chính là nhãn của các nhánh
dẫn từ nút gốc tới nút n này.
Ví dụ: nút P
3
trong hình 2.3 là đại diện cho tất cả các địa chỉ bắt đầu
bằng chuỗi 001. Những nút có màu xám là những nút ứng với các tiền tố.
Những nút này chứa thông tin chuyển tiếp.
Lưu ý: các tiền tố không những được định vị ở các nút lá mà còn ở một vài
nút nhánh.
17
Hình 2.4 Trie nhị phân tương ứng với tiền tố trong bảng 2.1
Nhận thấy rằng, tiền tố P
2
và P
3
là trường hợp cụ thể của tiền tố P
1
.
Địa chỉ của P

cần tìm là 1, nên ta sẽ đi sang nhánh phải (đây chính là nút chứa tiền tố d).
Như vậy ta sẽ lưu lại d, và d chính là BMP hiện thời. Sau đó ta di chuyển
sang nhánh trái, bởi nút thứ 2 trong địa chỉ là 0. Tại thời điểm này nút được
18
duyệt không lưu một tiền tố nào (vì vậy d vẫn là BMP). Vị trí thứ 3 trong
địa chỉ là 1. Nhưng nút này không có nhánh nào được gán nhãn 1, vì vậy
việc tìm kiếm kết thúc và d chính là tiền tố khớp cuối cùng và là tiền tố tốt
nhất.
Đánh giá thuật toán tìm kiếm: Một trie cần O(NW) ô nhớ với N là số
tiền tố, W là số bit của tiền tố. Để tìm ra tiền tố khớp dài nhất cần W lần
truy nhập trong trường hợp xấu nhất. Vậy độ phức tạp của thuật toán tìm
kiếm là O(W).
2.3.2. Chèn tiền tố
Để chèn một tiền tố mới, trước hết ta cần tìm kiếm cho tới khi tới
được nút không có nhánh tương ứng, lúc đó ta sẽ chèn nút mới vào.
Hình 2.5 Chèn tiền tố vào trie nhị phân
Ví dụ: chèn tiền tố 110 và 0110 vào trie. Ta giả sử đó là tiền tố P
10
và
P
11
. Bít đầu tiên của P
10
là 1, ta dịch xuống nhánh phải đó là nút P
4.
Tiếp
theo là bit thứ 2 ta cũng dịch chuyển về nhánh phải. Bit thứ 3 là 0 vì vậy ta
cần dịch xuống nhánh trái, tuy nhiên nút không có nhánh trái vì vậy nút P
10
được tạo mới và đính vào vị trí này. Tiếp theo ta chèn tiền tố P

Trie được nén đường dẫn chính là Trie nhị phân, tuy nhiên một số
phần của trie được nén lại bằng cách loại bỏ các nút không cần thiết nhằm
làm giảm thời gian tìm kiếm và bộ nhớ cần thiết để lưu trữ.
Tuy nhiên, để có thể loại bỏ một số nút mà việc tìm kiếm vẫn chính xác, ta
cần phải bổ sung một số thông tin vào các nút còn lại.
Nhận xét: Trie nhị phân có thể đưa ra những tiền tố có chiều dài tuỳ ý, tuy
nhiên đôi khi tồn tại những nút có chiều dài tuần tự rất lớn.
Ví dụ: Ta thấy rằng nút P
2
có chiều dài đến nút tiền tố P
1
khá lớn, vùng chứa
tiền tố P
2
không có một nút nào khác ngoài P
2
, ở đây ta thấy có 3 vị trí
không là tiền tố và không được sử dụng. Vì vậy vùng này cần được nén lại
(loại bỏ những nút không cần thiết) để giảm thời gian tìm kiếm và giảm bộ
nhớ cần thiết để lưu trữ. Đây chính là ý tưởng của trie nén đường dẫn
Hình 2.7 Cấu trúc dữ liệu trie nén đường dẫn cho các tiền tố bảng 2.1
21
Nhận thấy rằng nút P
2
, P
3
được chuyển trực tiếp tới làm nút con của
nút P
1
. Hai nút đứng trước P

Tìm kiếm
Việc tìm kiếm trong trie nén đường dẫn được tiến hành tương tự như
trong trie nhị phân, đó là căn cứ vào bit địa chỉ có giá trị 0 hay 1, ta sẽ
quyết định tới nhánh trái hoặc nhánh phải. Tuy nhiên khác với trie nhị phân
cần phải duyệt mọi bit kiểm tra, ta chỉ cần duyệt những bit cần thiết (những
bit này được chỉ định). Khi gặp những nút có màu xám (tương ứng với một
tiền tố), ta sẽ tiến hành so sánh với tiền tố trên thực tế. Nếu khớp, nó sẽ
được lưu với tư cách là BMP và lại tiếp tục tìm kiếm thêm. Công việc tìm
kiếm sẽ kết thúc nếu gặp được nút lá, hoặc phát hiện ra có lỗi.
Ví dụ: Tìm kiếm một địa chỉ bắt đầu với 001010 trong trie nén đường dẫn
trong hình 2.6. Tìm kiếm bắt đầu từ nút gốc, nút này chỉ ra rằng bit số 1 cần
được kiểm tra. Do bit số 1 trong địa chỉ 001010 là 0 vì vậy ta đi xuống
nhánh trái và gặp nút tiền tố P
1
. Bây giờ ta sẽ so sánh địa chỉ với tiền tố P
1
,
tương ứng với phần địa chỉ là 0. Ta thấy khớp, tiền tố P
1
được đưa vào là
BMP. Bây giờ ta tiếp tục kiểm tra thông tin về bit kế tiếp được duyệt (lưu
trong P
1
), đó chính là bit thứ 3. Đối chiếu sang địa chỉ cần tìm (001010), ta
22
thấy bit thứ 3 có giá trị là 1. Như vậy, ta tiếp tục kiểm tra nhánh phải. Một
lần nữa ta lại kiểm tra tiền tố P
3
(001*) có khớp một phần của địa chỉ
(001010). Ta thấy khớp, ngoài ra P

Để minh hoạ cho cấu trúc dữ liệu và mối quan hệ đặc biệt giữa các nút này
chúng ta sẽ xây dựng một DP trie gồm tập các mẫu (1000100, 1001, 10,
1111, 11).
Hình 2.9 Chèn nút 1000100 vào DP trie
- Với khoá đầu tiên 1000100 được chèn vào trie ta được 1 DP trie gồm
duy nhất một nút (là nút gốc) a. Khi khoá 1000100 chỉ là một khoá
của nút a, trường index sẽ mang giá trị lớn nhất của độ rộng của khoá
đó là 6. Và tại vị trí số 6 khoá có giá trị là 0 vì vậy khoá 1000100 sẽ
là leftkey của gốc.
- Tiếp tục chèn 1001 vào DP trie. Index của nút a bây giờ bằng 3 (vị trí
đầu tiên mà 2 nút khác nhau) và 3 tiền tố chung đầu tiên sẽ được bỏ
qua. Ta thấy tại vị trí số 3 của khoá mới (1001) ta có giá trị 1 vậy
khoá này sẽ là rightkey của gốc a. (Chú ý: Nếu như vị trí bit của khoá
mới là 0, và vị trí cũ lại là 1 thì khoá cũ sẽ được chuyển thành
24
rightkey và khoá mới sẽ là leftkey). Trong cây này, việc tìm kiếm
được hướng dẫn bởi khoá được lưu trữ. Đó chính là giá trị của bit
nằm ở vị trí thứ 3 [Index(a)] của khoá cần tìm. Vì vậy, bit ở vị trí
0,1,2 sẽ được bỏ qua.
Hình 2.10 Chèn nút 1001 vào DP trie
- Tiếp tục chèn 10 vào DP trie. Vì 10 là tiền tố của cả 2 khoá của a, vì
vậy một nút b được tạo mới và là nút cha của nút a. Index của nút b
là 1. Khoá 10 là Leftkey của nút b và a sẽ là Leftsubtrie của nút b bởi
vì tại vị trí bit số 1 của các khoá đều là 0.
- Chèn khoá 1111 vào cây DP trie. Khoá mới này khác khoá 10 ở bit
có vị trí là 1. Vì vậy, ta không cần thay đổi giá trị của trường Index
của nút b.
- Chèn khoá 11 vào DP trie. Vì 11 khoá là tiền tố của khoá 11111, vì
vậy khoá 11111 sẽ được thay thế bởi khoá 11, một nút c mới chứa
khoá này sẽ được tạo, và nút c này sẽ là Rightsubtrie của nút b.