LỜI NÓI ĐẦU
Việc định tuyến các gói tin thường tạo ra các điểm thắt nút của
mạng, đặc biệt khi nhu cầu cập nhật các luật trong bảng định tuyến cao. Do
đó đã có rất nhiều nghiên cứu nhằm tìm ra các giải pháp, thuật toán tốt nhất
cho việc định tuyến nhằm giảm thắt nút của mạng. Các giải pháp dựa trên
bảng tiền tố tĩnh đã có nhiều kết quả tốt khi áp dụng đối với địa chỉ IP
ngắn. Tuy nhiên, khi áp dụng trên địa chỉ IP dài, các giải pháp này thông
thường phải xây dựng lại toàn bộ bảng định tuyến nên thời gian cập nhật
chậm do vậy xảy ra trường hợp định tuyến sai gói tin. Thời gian gần đây có
nhiều tác giả đã đưa ra các giải pháp, thuật toán thực hiện trên bảng định
tuyến động - bảng định tuyến cho phép chèn/xóa đồng thời với việc định
tuyến các gói tin.
Trong nội dung đồ án tôi nghiên cứu 02 phương pháp định tuyến trên
bảng IP động: phương pháp khớp tiền tố dài nhất, phương pháp sử dụng độ
ưu tiên cao nhất của các luật.
Nội dung nghiên cứu bao gồm:
- Nguyên tắc hoạt động của Router
- Định tuyến IP theo phương pháp khớp tiền tố dài nhất
- Định tuyến IP theo độ ưu tiên
- Cài đặt minh họa
Trong quá trình thực hiện đồ án, mặc dù có rất nhiều cố gắng trong
việc nghiên cứu, sưu tầm tài liệu và được sự giúp đỡ nhiệt tình của giáo
viên hướng dẫn, nhưng do điều kiện thời gian có hạn, trình độ kiến thức
còn nhiều hạn chế nên tôi không thể tránh được những thiếu sót. Tôi rất
mong nhận được sự đóng góp ý kiến của các thầy cô giáo và những người
quan tâm.
1
Tôi xin chân thành cảm ơn thầy giáo TS. cùng các thầy cô trong Bộ
môn Công nghệ phần mềm, và Khoa CNTT đã tận tình hướng dẫn, tạo
mọi điều kiện giúp đỡ tôi thực hiện đồ án này.
2

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
là quá trình định hướng gói tin về phía địa chỉ đích, hay nói cách khác là
xác định đường đi từ mạng này đến mạng khác. Router sẽ quyết định
đường đi của gói tin đến đúng địa chỉ đích dựa vào bảng định tuyến chứa
trong bộ nhớ. Bảng định tuyến này được khởi tạo giá trị ban đầu, các đầu
vào có thể tạo bằng tay hoặc tự động.
Có thể phân chia thành 3 kiểu định tuyến
- Định tuyến tĩnh
- Định tuyến động
- Định tuyến mặc định: Một gói tin mà Router không biết địa chỉ
đích của nó được gửi ra cổng mặc định.
Ngày nay Internet bao gồm hàng nghìn các gói tin được kết nối trên
các mạng bởi các Router. Khi một máy trạm gửi một gói tin vào Internet,
4
các Router giữ chậm gói tin đó và định hướng đến địa chỉ đích cuối cùng.
Các Router trao đổi thông tin định tuyến với mỗi Router khác, và sử dụng
thông tin thu được để tính toán đường đi cho tất cả các địa chỉ đích có thể
đến được. Mỗi gói tin được xử lý ngay và định hướng tới Router tiếp theo
dựa trên địa chỉ đích của nó.
1.2.2 Thuật toán định tuyến
Một mạng chuyển mạch gói bao gồm các nút mạng (các Router và
switch) được kết nối với nhau bởi các đường truyền thông có cấu trúc

- 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
Prefix Name: tên tiền tố
Prefix: tiền tố được đưa ra bởi CIDR
1
Next Hop: bước truyền tiếp theo
Ranges Start: giá trị bắt đầu của đoạn, khi coi một tiền tố là một đoạn
1
Classless Inter-Domain Routing
6
Ranges Finish: giá trị kết thúc của đoạn
Priority: trường ưu tiên, là giá trị để đánh giá độ ưu tiên của các nhóm
địa chỉ. Có nhiều cách để đánh giá độ ưu tiên cho các nhóm địa chỉ ví dụ
như dựa vào băng thông của mạng, dựa vào khoảng cách các vùng, dựa vào
chiều dài tiền tố…
Rule
Name
Prefix
Name
Prefix Next Hop
Ranges
Start
Ranges
Finish
Priority

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. Tiền
tố 110* đặc trưng hơn tiền tố 11*. Khi các tiền tố cùng khớp với một địa
chỉ đích d thì tiền tố đặc trưng nhất là tiền tố dài nhất
2
nên biện pháp khớp
đặc trưng nhất còn gọi là khớp tiền tố dài nhất.
Trong trường hợp bảng 1.1, các quy tắc P1, P3, P4 đều khớp với địa
chỉ 19. Với biện pháp này, quy tắc P4 được chọn.
1.3.1 Bảng định tuyến tĩnh
Là cách mà các quy tắc được đưa vào bảng định tuyến bằng tay.
Trong trường hợp này, gói tin vẫn được gửi đến đích mà không căn cứ vào
trạng thái của mạng. Đích có hoạt động hay không, các đường tĩnh vẫn giữ
nguyên trong bảng đầu ra, lưu lượng vẫn được gửi tới đích đã được xác
định trước.
2
Độ dài của một tiền tố là số bit trong tiền tố đó (không sử dụng đến kí tự * khi xác định độ dài). Với
bảng dữ liệu trên, độ dài của P1 là 0 và của P2 là 4.
8
Đặc điểm của bảng Router tĩnh:
1. Thời gian xử lý một gói tin đến: là thời gian cần thiết để tìm trên bảng
một quy tắc để sử dụng. Chúng ta thường gọi đây là phép tìm kiếm.
2. Thời gian tiền xử lý: là thời gian tạo cấu trúc dữ liệu cho bảng quy tắc.
3. Yêu cầu về bộ nhớ: dung lượng bộ nhớ cần thiết để cấu trúc lại bảng quy
tắc.
Đối với bảng tĩnh để thực hiện các thao tác cập nhật, người ta sử
dụng 2 bảng: bảng làm việc (working) và bảng phụ (shadow). Việc tìm
kiếm được thực hiện trên bảng làm việc còn việc cập nhật được thực hiện
trên bảng phụ (theo thời gian thực hoặc là cập nhật theo gói với khoảng
thời gian thích hợp). Sau một chu kỳ, bảng phụ sẽ được sao chép sang bảng

xuyên. Kiểu bảng này không chèn/xóa theo từng khối, và việc chèn/xóa
được thực hiện trong thời gian thực.
Đầu tiên, việc cập nhật được thực hiện thường xuyên trong vùng
Backbone. Bảng định tuyến cần phải cập nhật để phản ánh sự thay đổi của
Router. Tốc độ cập nhật đạt tới 1000 trên giây [Labovitz]. Mạng sẽ cập
nhật các lỗi phát sinh từ một Router bị hỏng, Router chỉnh sửa.
Thứ hai, một tiến trình cập nhật nhanh được ưu tiên hơn vì trong quá
trình cấu trúc lại, thời gian trễ từ điểm này sang điểm khác tăng lên, số gói
tin bị mất tăng lên đột ngột và một phần kết nối mạng bị lỗi.
Với bảng định tuyến động, ta nên nhắc đến thời gian cần để chèn/xóa
một quy tắc. Trong bảng quy tắc động, ban đầu cấu trúc dữ liệu được khởi
tạo với một cấu trúc dữ liệu tĩnh và sau đó chèn từng quy tắc một.
Các đặc điểm của bảng định tuyến động:
1. Thời gian tìm kiếm địa chỉ tiền tố trong bảng
10
2. Thời gian chèn. Thời gian cần để chèn một quy tắc mới vào bảng
3. Thời gian xóa. Thời gian để xóa một quy tắc từ bảng.
4. Yêu cầu bộ nhớ
Bảng định tuyến động chỉ làm việc trên một bảng làm việc và sự cập
nhật được làm trực tiếp trên bảng đó trong thời gian thực. Trong kiểu cập
nhật này, không gói tin nào được phân lớp không thích hợp. Tuy nhiên,
việc phân lớp và chuyển tiếp gói tin có khi bị trễ cho đến khi tiến trình cập
nhật hoàn thành. Để giảm thiểu thời gian trễ này, việc cập nhật phải thực
hiện nhanh.
Với kiểu bảng động, yêu cầu xử lý của CPU của Router cao hơn kiểu
bảng tĩnh. Tuy nhiên, việc cấu hình và tự động tìm ra những tuyến đường
thay thế nếu như mạng thay đổi lại đơn giản hơn rất nhiều.
Ngày nay, số lượng các hệ thống tự trị đang tiếp tục tăng lên, đó là lý
do đòi hỏi việc tăng tốc độ cập nhật của các bảng định tuyến động. Trong
phạm vi đồ án, ta xây dựng một cấu trúc và giải thuật cho bảng định tuyến

- Cây được xây dựng min theo giá trị y (ở gốc giá trị của y là nhỏ
nhất)
- Thao tác tìm kiếm chủ yếu theo giá trị x.
Cây tìm kiếm ưu tiên có hai kiểu khác nhau:
(1)Cây tìm kiếm là một cây tìm kiếm nhị phân cân bằng: Red-black
Priority Search Tree (RBPST)
(2)Cây tìm kiếm là cây tìm kiếm theo cơ số gọi là cây Radix Priority
Search Tree (RPST)
2.1 Radix Priority Search Tree
Cây tìm kiếm ưu tiên được giới thiệu đầu tiên bởi E.McCreight năm
1985 với các đặc điểm như sau.
2.1.1 Tính chất cây
- Các giá trị của x khác nhau và thuộc đoạn [0, k - 1]
- Mỗi nút của cây tìm kiếm ưu tiên có đúng 1 phần tử
4
Priority search tree (PST)
13
- Giá trị y của nút w phải nhỏ hơn hoặc bằng giá trị y của các nút con
của w (cây được định nghĩa theo giá trị min ở gốc)
- Khoảng của nút gốc w là [a, b)
- Khoảng của nút con trái là [a, floor((a+b)/2))
- Khoảng của nút con phải là [floor((s+b)/2), b)
2.1.2 Xây dựng một cây
Cho S là tập hợp các điểm (x
i
, y
j
). Ta sắp xếp các điểm theo thứ tự
tọa độ x tăng dần từ trái sang phải, tọa độ y tăng dần từ dưới lên trên.
Thuật toán tạo một cây RPST:

Lặp 4:
Cây hoàn chỉnh:
16
Hình 2.1. Các bước xây dựng một cây RPST
Ánh xạ cây vừa xây dựng qua trục hoành, thêm chỉ số đoạn, bỏ trục
tọa độ ta có được cách biểu diễn cây thông thường như sau:
Hình 2.2. Cây RPST
2.1.3 Chèn một nút vào cây RPST
Thuật toán chèn nút P(x, y) vào trong cây có nút gốc R.
• Nếu y < R(y) chèn nút P vào vị trí nút gốc. Nút P gán bằng nút gốc.
17
o Nếu P(x) thuộc khoảng [a, (floor(a+b)/2)) thực hiện thuật toán
chèn nút P trên cây con trái, nếu P(x) thuộc [floor((a+b)/2), b)
thực hiện thuật toán chèn trên cây con phải.
• Nếu y > R(y)
o P(x) thuộc khoảng [a, (floor(a+b)/2)) tiếp tục đi xuống và so
sánh P với các nút trên cây con trái
o P(x) thuộc [floor((a+b)/2), b) tiếp tục đi xuống và so sánh P
với các nút trên cây con phải.
Ví dụ: khi chèn (7, 1) ta thực hiện như sau:
Hình 2.3. Chèn một nút vào cây RPST
• Insert (7,1).
• (7,1) sẽ thay thế cặp khóa ở gốc, vì 1 < 8.
• (5,8) được đẩy xuống con trái,vì 5 thuộc khoảng của nút con trái.
18
5,
8
6,
9
7,1

Hình 2.4. Xóa một nút từ cây RPST
Thời gian thực hiện xóa một nút mất O(h), với h là chiều cao cây tìm
kiếm nhị phân.
2.2 Red-Black Priority Search Tree
19
[0, 4)
[8, 16)
[4, 8)
7,
1
6,
9
[0, 16)
[0, 8)
2,12
11,
5
[0, 4)
[8, 16)
7,
1
[0, 16)
[0, 8)
2,12
11,
5
5,
8
6,
9

. Sau khi
cây đã được xây dựng xong, có N – 1 nút lá được tạo thành chỗ đứng (với
N là số điểm trong tập dữ liệu). Các nút lá luôn được sắp xếp tăng dần theo
giá trị x của các điểm.
Bước 2: Áp dụng tính chất cây đỏ đen để tô màu cho các nút
Sau khi các điểm được đặt vào đúng vị trí các nút, ta tô màu cho các
nút giống như quy tắc tô màu cho cây đỏ đen.
Hình 2.5 minh họa tiến trình xây dựng sử dụng một ví dụ nhỏ gồm 8
nút.
Thuật toán xây dựng cây RBPST
1. Sắp xếp các điểm theo giá trị x tăng dần.
2. Trận đấu bắt đầu với các cặp điểm, các điểm có y cao hơn sẽ thắng
cuộc.
3. Khi một điểm thắng ở vòng thi đấu cao hơn, điểm bị thua ở vòng
trước sẽ di chuyển lên và lấp đầy nút rỗng.
4. Khi cây xây dựng xong, n-1 nút lá trở thành các vị trí đứng.
5. Tô màu các nút.
Xây dựng cây theo cách này thực hiện trong thời gian là O(N). Tuy
nhiên, bước đầu tiên trong tiến trình sắp xếp các điểm thực hiện mất O(N
logN) thời gian, toàn bộ tiến trình xây dựng cây mất O(N logN) thời gian.
5
placehodler
21
Hình 2.5. Xây dựng cây RBPST sử dụng quy tắc trận đấu từ dưới lên
Như ta đã biết một cây đỏ đen là một cây tìm kiếm nhị phân đặc biệt,
với thuộc tính màu của các nút và tính chất độ dài đường đi tới một nút lá
nên dùng cây đỏ đen khi lưu trữ thông tin rất hiệu quả. Vì một cây đỏ đen
cho phép chèn/xóa các phần tử nhanh chóng. Đây cũng là lý do ta sử dụng
phương pháp tô màu của cây đỏ đen cho cây PST. Các tiến trình này được
trình bày trong phần sau.

nút mới và nút gốc đó (khóa của nút gốc là giá trị của điểm mới, khóa nút
mới sẽ là khóa của nút gốc), phương thức push-down lại tiếp tục với nút
6
split line
23
gốc vừa bị hoán đổi giống như một nút mới. Tiến trình tiếp tục được lặp lại
cho đến khi tất cả các điểm được đặt vào các nút. Cây thứ 3 trong hình
trong hình 2.6 minh họa tiến trình này.
Hình 2.6. Chèn một nút vào cây RBPST
Khi một nút mới được chèn vào, dẫn đến tất cả các giá trị phân chia
phải được cập nhật lại. Giá trị phân chia của một nút được xác định là một
nửa giá trị x của nút con phải nhất trong cây con trái và nút con trái nhất
trong cây con phải. Khi một nút con mới được chèn vào, điều kiện này có
thể bị thay đổi, và do vậy việc cập nhật là cần thiết.
24
Sau phép chèn, nếu một tính chất bất kỳ nào của cây đỏ đen bị vi
phạm thì cây sẽ phải cân bằng lại. Hình 2.6 không có trường hợp nào bị vi
phạm. Nhưng trong hình 2.7 thì bị vi phạm và phải xây dựng lại.
Một nút mới chèn vào một cây đỏ đen thì luôn được tô màu đỏ, và
quy tắc có cùng số nút đen trên bất kỳ đường nào từ nút gốc tới một nút lá
không xảy ra. Quy tắc không có nút đỏ nào có một nút con đỏ (một nút đỏ
phải có hai nút con đen), ta có thể dễ dàng nhận thấy quy tắc này bị vi
phạm khi chèn một nút đỏ và ta gọi đây là lỗi đỏ-đỏ. Khi lỗi đỏ-đỏ xuất
hiện, màu sắc của các nút gần kề quyết định việc làm tiếp theo. Nếu cả nút
cha và nút chú là nút đỏ, sửa lại màu của nút cha và nút chú thành màu đen,
nút ông thành màu đỏ. Việc này lại có thể dẫn đến nút ông lại vi phạm lỗi
đỏ - đỏ với cha của nó. Nếu trường hợp này xảy ra, tiến trình sẽ được lặp.
Nếu chỉ có nút cha màu đỏ, và nút chú đen, thực hiện một phép quay.
Hình 2.7 minh họa các trường hợp vi phạm tính chất cây đỏ đen khi
chèn nút mới vào cây.