Tăng tốc độ định tuyến gói tin dựa trên cây đa tiền tố bằng phương pháp sử dụng bộ nhớ đệm

l) then 
4: PT_DELETE(p, s_pointer(v)) 
5: FREE_S-NODE 
6: else if p is in v then 
7: Xoá p trong v 
8: if v là p-node ngoài then 
9: t(v) := t(v) – 1 // giảm số lượng tiền tố trong v 
10: if t(v) = 0 và s_pointer(v) = null then 
666 TĂNG TỐC ĐỘ ĐỊNH TUYẾN GÓI TIN DỰA TRÊN CÂY ĐA TIỀN TỐ BẰNG PHƯƠNG PHÁP SỬ DỤNG BỘ NHỚ ĐỆM 
11: FREE_P-NODE(v) 
12: else 
13: tìm tiền tố y trong childr(v) sao cho len(y) = max{len(p)| p ∈ childi(v) for 0≤ i≤2k-1} 
14: chèn y vào vị trí tiền tố cuối trong v 
15: v := childr(v) 
16: MPT_DELETE(y, v, level + 1) 
17: else 
18: r := GET(p, k . level, k . (level + 1) - 1) 
19: v := childr(v) 
20: MPT_DELETE(p, v, level + 1) 
21: return 
Độ phức tạp tính toán của thuật toán: O(2
k
W/k) 
W là độ dài (tính bằng bit) của một địa chỉ đích 
B. Hiệu quả định tuyến của cây k-MPT [2] 
Dựa vào đặc điểm về cấu trúc và qua nghiên cứu các thuật toán mô tả hoạt động của cây k-MPT , chúng tôi có 
một số nhật xét về hiệu quả định tuyến của CTDL này như sau: 
Thứ nhất: Mỗi nút (nút chính + nút phụ) của cây k-MPT lưu nhiều tiền tố (tương ứng là các luật), nên so với các 
CTDL cây khác (như cây tiền tố), với cùng một tập tiền tố, thì chiều cao của k-MPT thấp hơn nhiều, do đó tốc độ tra 
cứu trên cây k-MPT sẽ nhanh hơn. 
Thứ hai: Trong quá trình tra cứu địa chỉ, LMP có thể được tìm thấy tại các nút không phải là nút lá. Từ đặc 
điểm P4 , ta khẳng định: nếu trường pt(v) khớp với địa chỉ đích, thì tiền tố lưu trong pt(v) chính là LMP. Khi đã tìm 
được LMP thì thuật toán có thể kết thúc ngay. Mặt khác, do các tiền tố sắp xếp theo thứ tự không tăng của độ dài mà 
quá trình tra cứu, so khớp chỉ diễn ra giữa địa chỉ đích DA với những tiền tố nhất định trong nút, chứ không phải với tất 
cả các tiền tố. Do đó chi phí thời gian tìm kiếm LMP giảm khá nhiều. 
Thứ ba: Việc lưu trữ nhiều tiền tố trong một nút giúp k-MPT giảm chi phí lưu trữ thông tin. Mặt khác, nhìn 
chung các tiền tố được lưu trữ trong các nút có mức càng cao (càng xa nút gốc) thì có độ dài càng bé, do đó chi phí lưu 
trữ của các nút ở mức cao ít hơn chi phí lưu trữ của các nút ở mức thấp. Do đó, nếu việc cấp phát bộ nhớ lưu trữ cho 
các nút được lập trình linh hoạt hơn, ta có thể tiết kiệm được dung lượng lưu trữ. 
Thứ tư: Việc lưu giữ nhiều tiền tố trong một nút của cây và việc phân loại các tiền tố theo thứ tự không tăng của 
độ dài làm giảm số nút trên cây, giảm số lần truy cập bộ nhớ, và giảm chi phí tìm kiếm vị trí để chèn và xóa các tiền tố. 
Đặc biệt trong thao tác xóa tiền tố, việc tìm kiếm tiền tố thay thế (để đảm bảo tính chất của cây) có chi phí thấp. Việc 
đảm bảo được các tính chất của cây k-MPT sau các thao tác cập nhật có ý nghĩa quan trọng, đảm bảo hiệu quả của hoạt 
động định tuyến của Router. 
C. Kỹ thuật phân hoạch cây k-MPT [2] 
Khi bước nhảy k tăng thì chiều cao của cây k-MPT giảm, tuy nhiên số nhánh con và sự phức tạp của các quá 
trình xử lý tăng lên, làm hiệu suất định tuyến trung bình giảm. Với mục đích làm giảm chiều cao của cây k-MPT mà 
không tăng bước nhảy k, một kỹ thuật được đề xuất là phân hoạch cây k-MPT. Ý tưởng nhằm thực hiện phân hoạch cây 
k-MPT thành một số các k-MPTs có chiều cao thấp hơn, tạo nên một cấu trúc dữ liệu mới gọi là Cây đa tiền tố chỉ mục 
có bước nhảy k (k-Stride Index Multiprefix Tree - gọi tắt là k-IMPT), dựa trên cây k-MPT đã trình bày. Cây k-IMPT 
phân hoạch một cây k-MPT thành nhiều cây k-MPTs có chiều cao thấp hơn, danh sách các gốc được lưu giữ trong 
mảng một chiều (index table) như sau: tab[ 000, 001,  , 111 ] 
 α α α 
Hình 2. Một cây k-IMPT 
00000000 
. 
. 
. 
. 
111111111 
Index Table 
. 
. 
. 
. 
k-MPT
k-MPT
k-MPT. 
.
α 
Nguyễn Mạnh Hùng, Phạm Huy Đông 667 
Với một chiều dài α cố định, bảng chỉ mục có không quá 2α phần tử, mỗi phần tử tab[b0b1bα-1] trỏ tới gốc 1 
cây k-MPT con mà có chứa các tiền tố với tiền tố con chung dạng b0b1bα-1 có độ dài α bít (xem hình 2). 
Để thực hiện các thao tác bảng định tuyến (tìm kiếm, chèn, xóa) trong một k-MPT, trước hết chúng ta đối chiếu 
với mảng chỉ số và thực hiện các thao tác này trong cây k-MPT tương ứng. 
Ví dụ: nếu chèn 1 tiền tố p vào một k-MPT, đầu tiên chúng ta lấy α bít của p để xác định giá trị chỉ mục của gốc 
trong mảng. 
Nếu len(p) ≥ α chắc chắn p được chèn vào cây k-MPT có gốc là giá trị chỉ mục. 
Ngược lại nếu len(p) < α thì ta phải mở rộng tiền tố p thành một tập tiền tố có độ dài α. Ví dụ, với p = 101000* 
và α = 8 (tức là 8 bít đầu của tiền tố biểu diễn giá trị của chỉ mục). Vì tiền tố 101000* mở rộng thành 10100000, 
10100001, 10100010, và 10100011, và do đó tiền tố 101000* được chèn vào 4 cây k-MPT được biểu diễn bởi 
tab[10100000], tab[10100001], tab[10100010] và tab[10100011]. 
Quá trình thực hiện các thao tác của bảng định tuyến (chèn, tra cứu địa chỉ và xóa ) trên cây k-MPT đều được 
bắt đầu bằng việc xác định gốc của cây con k-MPT, bằng cách xác định giá trị thập phân của α bit đầu tiên của tiền tố 
sẽ trả lại giá trị tương ứng của gốc trong mảng chỉ mục, sau đó thực hiện các hoạt động chèn, tra cứu hoặc xóa tiền tố 
trên cây k-MPT con đó. 
Việc mở rộng tiền tố và chèn vào các cây tương ứng như trên có thể dẫn tới sự bùng nổ số lượng tiền tố được 
lưu giữ trên cây. Tức là số tiền tố được lưu giữ lớn hơn nhiều so với số lượng tiền tố đầu vào, và việc lưu giữ các tiền 
tố trùng lặp gây ra tốn kém bộ nhớ và xử lý phức tạp. Chúng ta phải chọn một giá trị α phù hợp để giảm bộ nhớ cần 
thiết, α không nên quá lớn (vì với α cố định, sẽ có 2α cây k-MPT được tạo ra), nhưng nếu α quá nhỏ thì hiệu quả làm 
giảm chiều cao của cây cũng không cao. Trên thực tế, sau quá trình thử nghiệm, chọn giá trị α bằng độ dài tiền tố ngắn 
nhất của bảng định tuyến được đánh giá là một sự lựa chọn phù hợp. 
III. ĐỀ XUẤT KỸ THUẬT TĂNG TỐC ĐỘ ĐỊNH TUYẾN DỰA TRÊN CÂY ĐA TIỀN TỐ 
SỬ DỤNG BỘ NHỚ ĐỆM 
A. Kỹ thuật tăng tốc cho k-MPT sử dụng bộ nhớ đệm (Cache) 
Một lượng dữ liệu được truyền đi trong hệ thống mạng có thể có rất nhiều gói tin có trường địa chỉ đích giống 
nhau. Mặc dù việc nhận các địa chỉ đích gói tin đến của router là ngẫu nhiên, nhưng một địa chỉ đích có thể bị tra cứu 
lặp lại nhiều lần trong một khoảng thời gian lân cận. Để hạn chế sự tra cứu lặp lại đó, chúng tôi đề xuất kỹ thuật sử 
dụng bộ nhớ đệm cache, để lưu kết quả tra cứu của một số địa chỉ đích gói tin vừa được tra cứu. 
Việc sử dụng bộ nhớ cache để tăng tốc độ định tuyến được chia thành 2 hướng nghiên cứu chính: 1) áp dụng 
cache cho tập luật trong bảng định tuyến (tập luật nào được sử dụng nhiều sẽ được lưu vào cache) như sử dụng Rule 
Caching[10], Popular Rule Caching, và 2) áp dụng cache cho việc định tuyến gói tin đến địa chỉ đích (địa chỉ đích 
nào được định tuyến đến nhiều sẽ được lưu vào cache) như Digest Cache[11], LFU cache. Trong bài báo, chúng tôi sử 
dụng kết hợp hàng đợi và bảng băm để giúp tăng tốc độ tìm kiếm trong cache khi định tuyến gói tin dựa vào địa chỉ 
đích, dựa vào ưu thế về thời gian tìm kiếm của bảng băm. 
1. Cách xây dựng cache 
Cache được thiết kế dùng một bảng băm để lưu các khoá [key] phục vụ tra cứu trong cache và một hàng đợi sắp 
xếp theo một trật tự nhất định để lưu các giá trị gói tin cần định tuyến (Tiền tố địa chỉ đích và Cổng đích nexthop). Khi 
cache đầy, sẽ xoá các phần tử cuối hàng đợi (ít dùng nhất) ra khỏi cache và đưa phần tử mới vào đầu hàng đợi. Việc 
tìm kiếm các key trong bảng băm của cache sẽ nhanh hơn các CTDL khác. 
Hình 3. Mô hình sử dụng bộ nhớ cache 
668 TĂNG TỐC ĐỘ ĐỊNH TUYẾN GÓI TIN DỰA TRÊN CÂY ĐA TIỀN TỐ BẰNG PHƯƠNG PHÁP SỬ DỤNG BỘ NHỚ ĐỆM 
Để thao tác với cache, dùng hàm put để đưa 1 phần tử vào cache, còn hàm exists để kiểm tra 1 phần tử đã có 
trong cache hay chưa. Mô hình hoạt động của cache được thiết kế như sau: 
2. Hoạt động tra cứu khi áp dụng cache 
Khi gói tin đi vào Router và yêu cầu tra cứu địa chỉ, trước hết Router sẽ kiểm tra xem địa chỉ đích của gói tin 
cần tra cứu có trong cache không, nếu có thì lấy thông tin nexthop tương ứng với địa chỉ đích đó đã được lưu trong 
cache làm kết quả, ngược lại nếu địa chỉ đích đó không có trong cache, thì thực hiện tra cứu địa chỉ đó trên cây k-MPT, 
sau đó đưa thông tin địa chỉ đích vừa tra cứu với nexthop tương ứng thu được vào cache. Khi cache đầy, cần loại bớt 
những dữ liệu cũ, ít sử dụng hơn và cập nhật dữ liệu mới hơn cho cache. 
Tuy nhiên sẽ nảy sinh vấn đề: lựa chọn dung lượng bao nhiêu cho cache để đạt hiệu quả tối ưu, vì chi phí tra 
cứu địa chỉ khi sử dụng kỹ thuật này bao gồm chi phí tìm kiếm trong cache, chi phí cập nhật cache. 
Vấn đề nữa là khi có luật cần thêm hoặc xoá, thì khi tiến hành thêm hoặc xoá tiền tố trong cây, ta phải tiến hành 
tìm kiếm tiền tố này trong cache để cập nhật lại nexthop hoặc xoá. Để đảm bảo rằng dữ liệu trong cache luôn lưu giữ 
đúng giá trị mới nhất khi bảng định tuyến có sự thay đổi. 
Thực tế kiểm nghiệm cho thấy với lượng gói tin ít, cache ít phát huy tác dụng, nhưng với số lượng gói tin đến 
lớn, cache tỏ ra khá hiệu quả khi định tuyến vì số lần tra cứu trên cây k-MPT phải thực thi ít hơn. 
B. k-MPT có sử dụng cache: 
Để áp dụng cache trong việc hỗ trợ định tuyến trong cây k-MPT, chúng tôi tiến hành cài đặt bộ nhớ cache theo 
thiết kế ở trên vào thuật toán tìm kiếm (định tuyến gói tin) MPT_LOOKUP của cây k-MPT [2]. Khi một địa chỉ đích 
được tra cứu, trước tiên chúng ta sẽ tìm kiếm địa chỉ này có tồn tại trong cache hay không (bằng kỹ thuật tìm kiếm hàm 
băm theo thiết kế ở trên). Nếu địa chỉ này có tồn tại trong cache, cổng đích (nexthop) của nó được trả về và hoàn tất 
quá trình tìm kiếm. Nếu địa chỉ đích không nằm trong cache, sẽ tiến hành tìm kiếm địa chỉ này trên cây theo thuật toán 
MPT_LOOKUP gốc. Xảy ra 2 trưởng hợp 
- Nếu không tìm thấy địa chỉ đích trong cây, thông báo không tìm thấy và kết thúc tìm kiếm. 
- Nếu tìm thấy địa chỉ đích, trả về cổng đích nexthop và lưu thông tin địa chỉ đích và cổng đích vừa tìm thấy 
vào cache. Nếu cache đầy, tiến hành loại bỏ phần tử ít dùng nhất trong cache. 
begin
input DA,v, level
Tnext_hop = MPT_LOOKUP(DA, v, level);put(DA, next_hop(DA)) vào cache
End
next_hop = next_hop(DA)
trong cacheDA có trong cache?F
Output next_hop
Sử dụng cache tăng 
tốc độ trac cứu trên 
k-MPT
Hình 4. Sơ đồ thuật toán 
Khi áp dụng cache, mỗi khi bảng định tuyến có sự thay đổi, tuyến đã đưa vào cache có thể không còn đúng nữa, 
ta phải tiến hành tìm luật này trong cache rồi update lại theo luật mới thêm. Việc tìm kiếm trong cache dựa vào hàm 
băm không bị ảnh hưởng nhiều về mặt thời gian. 
C. k-IMPT có sử dụng cache 
Tương tự ý tưởng dùng cache cho k-MPT, khi tiến hành sử dụng cache cho k-IMPT, chúng ta có thể sử dụng 1 
bộ nhớ cache cho tất cả các cây phân hoạch k-MPTs thành phần theo cách tương tự cho cây k-MPT nguyên thuỷ. Tuy 
nhiên nếu cây k-IMPT có độ cao thấp, thì việc sử dụng cache cho nó sẽ kém hiệu quả, nên chúng ta sẽ sử dụng bộ nhớ 
cache cho những cây k-IMPT có độ cao tương đối lớn. Toàn bộ quá trình tìm kiếm trên các cây k-IMPT sẽ sử dụng 
thuật toán IMPT_LOOKUP [2], các tình huống xảy ra cũng tương tự khi sử dụng cache cho cây k-MPT: 
- Nếu không tìm thấy địa chỉ đích trong các cây k-IMPT, thông báo không tìm thấy và kết thúc tìm kiếm. 
- Nếu tìm thấy địa chỉ đích, trả về cổng đích nexthop và kiểm tra độ cao của cây k-IMPT mà địa chỉ được tìm 
thấy, nếu cây này có độ cao đạt ngưỡng theo quy định thì lưu thông tin địa chỉ đích và cổng đích vừa tìm thấy vào 
cache. Nếu cache đầy, tiến hành loại bỏ phần tử ít dùng nhất trong cache. 
Nguyễn Mạnh Hùng, Phạm Huy Đông 669 
begin
input α, p, DA
TNext_hop = IMPT_LOOKUP(α , p, DA)
End
next_hop = next_hop(DA)
trong cacheDA có trong cache?F
Output next_hop
Sử dụng cache tăng 
tốc độ trac cứu trên 
k-IMPT
Độ cao của k-MPT đạt 
ngưỡng quy định
put(DA, next_hop(DA)) vào cache
T
F
Hình 5. Sơ đồ chi tiết thuật toán 
IV. CÀI ĐẶT THỬ NGHIỆM VÀ ĐÁNH GIÁ 
Để đảm bảo sát với ứng dụng thực tế, chương trình sử dụng các bộ dữ liệu được tạo bằng bộ công cụ 
ClassBench do David E. Taylor, Jonathan S. Turner thuộc Phòng Nghiên cứu ứng dụng, Khoa Khoa học Máy tính, Đại 
học Washington, Saint Louis tạo ra []. Bộ dữ liệu bao gồm các tập luật và các tập 
tham số gói tin được sinh bởi bộ công cụ trên có dữ liệu đầu vào là những bộ dữ liệu thực của các nhà cung cấp dịch vụ 
Internet. Đây là bộ công cụ được cộng đồng nghiên cứu sử dụng để đánh giá các thuật toán và các thiết bị phân loại gói 
tin. 
A. Đánh giá hiệu quả của thuật toán xây dựng cây có sử dụng cache 
Các thí nghiệm trên bộ cơ sở dữ liệu tiền tố đề cập ở trên, thực hiện với cây k-MPT và k-IMPT (biến k=2), thực 
hiện trên cùng một máy tính BXL Core I5 4430 có tốc độ 3.0 GHz và bộ nhớ RAM là 8GB; đơn vị tính thời gian là 
mili giây. 
Thuật toán cải tiến k-IMPT khi xây dựng cây sẽ phân hoạch thành nhiều cây con, do đó chiều cao của các cây 
được giảm đi khá nhiều, thời gian xây dựng cây cũng diễn ra nhanh hơn so với cây k-MPT. Chúng tôi đã tiến hành đo 
thời gian xây dựng cây với số luật biến thiên từ 3.000 đến 8.000 luật, kết quả thể hiện ở bảng 1: 
Bảng 1. Bảng đo thời gian xây dựng cây của 2-MPT và 2-IMPT(đơn vị miliseconds) 
Số lượng luật: 3000 luật 4000 luật 5000 luật 6000 luật 7000 luật 8000 luật 
2-MPT 129.3 152.8 205.5 240.88 280.83 329 
2-IMPT 110.8 133.63 161.88 185.14 205.5 225.42 
Từ kết quả trên, ta có biểu đồ so sánh thời gian xây dựng cây của 2-MPT và 2-IMPT như sau: 
Hình 6. Thời gian xây dựng cây của 2-MPT so với 2-IMPT 
670 TĂNG TỐC ĐỘ ĐỊNH TUYẾN GÓI TIN DỰA TRÊN CÂY ĐA TIỀN TỐ BẰNG PHƯƠNG PHÁP SỬ DỤNG BỘ NHỚ ĐỆM 
B. Đánh giá hiệu quả của việc định tuyến gói tin dựa trên cây k-MPT và k-IMPT cây có sử dụng cache 
Để chứng minh hiệu quả thuật toán tra cứu của 2-IMPT so với 2-MPT, cùng với thuật toán 2-MPT và 2-IMPT 
có sử dụng bộ nhớ cache, chúng tôi cố định 8000 luật và cho biến thiên số lượng gói tin đến. Chi phí thời gian tra cứu 
trung bình đo được thể hiện trong bảng 2: 
Bảng 2. Bảng đo thời gian tra cứu của 2-MPT và 2-IMPT với 8000 luật (đơn vị miliseconds) 
Số gói tin: -> 100.000 gói tin 
115.000
gói tin 
130.000
gói tin 
145.000
gói tin 
160.000 
gói tin 
175.000 
gói tin 
MPT 589.4 695.6 786.4 877.25 975 1085.8 
MPT (cache) 430.6 476 528 577.25 652.5 733.6 
IMPT 358.2 426.8 505.43 546.33 608 657.83 
IMPT (cache) 338 395.6 439.8 467 529.6 575.17 
Từ bảng trên, ta có biểu đồ so sánh, thể hiện hiệu quả của thuật toán 2-MPT và 2-IMPT cùng với khi chúng sử 
dụng thêm bộ nhớ cache như sau: 
Hình 7. Hiệu quả tra cứu của 2-MPT so với 2-IMPT 
Tiếp theo, chúng tôi đã thực hiện đo thời gian tra cứu của 2-IMPT so với 2-MPT với số lượng gói tin đến cố 
định là 150.000 gói tin, số lượng luật biến thiên từ 7000 đến 8000 luật, chi phí thời gian tra cứu trung bình thu được 
như bảng 3 dưới đây: 
Bảng 3. Bảng đo thời gian tra cứu 150.000 gói tin đến của 2-MPT và 2-IMPT (đơn vị miliseconds) 
Số luật: -> 7.000 luật 7.200 luật 7.400 luật 7.600 luật 7.800 luật 8.000 luật 
MPT 903 906.25 904.83 912.5 915 916.25 
MPT (cache) 560 570 576.5 573.25 578.75 579.5 
IMPT 599.2 608 604.5 611.75 616.6 619 
IMPT (cache) 507 508.6 514 514.75 511.5 514.2 
Từ bảng trên, ta có biểu đồ thể hiện sự ảnh hưởng của số lượng luật trong bảng định tuyến tới chi phí tra cứu 
của 2-MPT và 2-IMPT như sau: 
Hình 8. Biểu đồ thể hiện sự ảnh hưởng của số luật tới thời gian tra cứu của 2-MPT so với 2-IMPT 
Từ các biểu đồ trên, chúng ta nhận thấy, tốc độ tra cứu của các thuật toán 2-MPT và 2-IMPT được cải thiện 
đáng kể khi sử dụng bộ nhớ đệm (cache). Tuy nhiên việc lựa chọn cache phải nằm trong một khoảng nào đó ở mức độ 
Nguyễn Mạnh Hùng, Phạm Huy Đông 671 
phù hợp để tránh lãng phí bộ nhớ và tối ưu tốc độ cho thuật toán. Chúng tôi cũng tiến hành thử nghiệm với cố định 
8000 luật và tra cứu 150.000 gói tin đến của bộ dữ liệu thử nghiệm trong mục 6.1. 
Trong quá trình đo kết quả thử nghiệm, để đơn giản chúng tôi sử dụng đơn vị đo của cache được tính theo block 
thông tin, mỗi block được thể hiện cho một bộ gồm khoá Key và một bản ghi lưu thông tin của địa chỉ đích và nexthop 
tương ứng. Kết quả đo thời gian tra cứu được thể hiện trong bảng sau: 
Bảng 4. Bảng đo thời gian tra cứu 150.000 gói tin đến của 2-MPT theo dung lượng cache (đơn vị miliseconds) 
Dung lượng cache 
(block) 
Thời gian tra cứu 150.000 gói tin của 2-MPT 
(đơn vị miliseconds) 
50000 586.8 
10000 586 
5000 585.3 
3000 574.2 
1000 577 
Hình 9. Biểu đồ thể hiện sự ảnh hưởng của dung lượng cache tới thời gian tra cứu của 2-MPT 
V. KẾT LUẬN 
Bài báo đã trình bày tổng quan về bài toán xây dựng bảng định tuyến động nhằm tăng tốc độ định tuyến gói tin 
trong router. Phân tích đặc điểm cấu trúc, các thao tác và tính hiệu quả của CTDL cây k-MPT và k-IMPT. Trên cơ sở 
các phân tích về cây k-MPT và k-IMPT, bài báo đã đề xuất kỹ thuật tăng tốc độ tra cứu cho k-MPT và k-IMPT sử dụng 
bộ đệm. Thử nghiệm kỹ thuật đề xuất trên bộ dữ liệu chuẩn[3], kết quả cho thấy việc sử dụng bộ đệm cho quá trình 
định tuyến có hiệu quả rõ rệt, nhất là với lượng gói tin cần định tuyến lớn. 
VI. TÀI LIỆU THAM KHẢO 
[1] M. Berger, “IP Lookup with Low Memory Requirement and Fast Update”, Proc. IEEE High Performance 
Switching and Routing, pp. 287-291, June 2003. 
[2] Sun-Yuan Hsieh,Senior Member, IEEE, Yi-Ling Huang, and Ying-Chi Yang, “Multiprefix Trie: A New Data 
Structure for Designing Dynamic Router-Tables”, IEEE TRANSACTIONS ON COMPUTERS, 2011. 
[3] David E. Taylor, Jonathan S. Turner, ClassBench: A Packet Classification Benchmark, IEEE INFOCOM, 2005. 
[4] Sartaj Sahni, Kun Suk Kim, Efficient construction of variable-stride multibit tries for IP lookup, Proceedings 
Symposium on Applications and the Internet, 2002. 
[5] Sartaj Sahni, Kun Suk Kim, Efficient Construction Of Multibit Tries For IP Lookup, ACM Transactions on 
Networking, 2003. 
[6] Sartaj Sahni, Kun Suk Kim, Efficient Construction Of Fixed-Stride Multibit Tries For IP Lookup, Proceedings 8th 
IEEE Workshop on Future Trends of Distributed Computing Systems, 2001. 
[7] Yi Jiang, Fengju Shang, Research on Multibit-Trie Tree IP Classification Algorithm, International Conference on 
Communications, Circuits and Systems Proceedings, 2006. 
[8] Lee, Chae-Y. ; Park, Jae-G., IP Lookup Table Design using LC-trie with Memory Constraint, Journal of Korean 
Institute of Industrial Engineers, Volume 27, Issue 4, 2001. 
[9] Jing Fu, Olof Hagsand and Gunnar Karlsson, Improving and Analyzing LC-Trie Performance for IP-Address 
Lookup, JOURNAL OF NETWORKS, VOL. 2, NO. 3, JUNE 2007. 
[10] Nitesh B. Guinde, Roberto Rojas-Cessa and Sotirios G. Ziavras, Packet Classification using Rule Caching, IEEE 
International Conference on Information, Intelligence, Systems and Applications, July 2013. 
672 TĂNG TỐC ĐỘ ĐỊNH TUYẾN GÓI TIN DỰA TRÊN CÂY ĐA TIỀN TỐ BẰNG PHƯƠNG PHÁP SỬ DỤNG BỘ NHỚ ĐỆM 
[11] Francis Chang, Wu-chang Feng, Wu-chi Feng, Kang Li, EfficientPacket Classification with Digest Caches, in 
Proc. of the Third Workshop on Network Processors & Applications (NP3), February 2004. 
IMPROVING PACKET ROUTING SPEED BASED ON 
MULTIPREFIX-TRIE BY USING CACHING 
Nguyen Manh Hung, Pham Huy Dong 
Abstract - In current networks, improving routing speed for the router to enhance the network speed was researched and developed 
in two main directions: improved hardware quality and improved algorithms based on software. Many algorithms based on the data 
structure as Multi-bit trie, LC-Trie, Prefix Tree, Multiprefix Trie ... have been researching by scientists, applied to the construction 
of the router-tables. In this paper we analyzed and evaluated the effectiveness of the routing of Multiprefix Tree data structure and 
proposed a technique to improve the efficiency of routing based on the use of caching. Technical proposals are evaluated, compared 
with routing techniques based on multi-prefix tree. 
Keywords - improving routing speed, building dynamic routing table, routing packets.