BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG
HỌC VIỆN KỸ THUẬT QUÂN SỰ
NGHIÊN CỨU VÀ CÀI ĐẶT BẢNG ĐỊNH TUYẾN ĐỘNG
SỬ DỤNG CẤU TRÚC DỮ LIỆU CÂY PHÂN LOẠI ĐA HẬU TỐ (CMST)
ĐỀ TÀI:
HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN MẠNH HÙNG
NGHỆ AN, 7 - 2013
HỌC VIÊN THỰC HIỆN : NGUYỄN TUẤN NGHĨA
1
VẤN ĐỀ NÂNG CAO HIỆU QUẢ ĐỊNH TUYẾN
TÍNH KHOA HỌC
TÍNH THỰC TIỄN
TĂNG CHẤT LƯỢNG PHẦN CỨNG
CẢI TIẾN CTDL
VÀ THUẬT TOÁN
ĐANG PHÁT TRIỂN
BỊ GIỚI HẠN
NGHIÊN CỨU VÀ CÀI ĐẶT BẢNG ĐỊNH TUYẾN ĐỘNG
SỬ DỤNG CẤU TRÚC DỮ LIỆU CÂY PHÂN LOẠI ĐA HẬU TỐ(CMST)
ĐỀ TÀI:
2
NHỮNG ĐÓNG GÓP KHOA HỌC CHÍNH
NGHIÊN CỨU CTDL CMST
VÀ CẢI TIẾN
NỀN TẢNG LÝ THUYẾT
ĐỊNH TUYẾN,
BẢNG ĐỊNH TUYẾN
BINARY TRIE
LỊCH SỬ VẤN ĐỀ
GIAO THỨC
ĐỊNH TUYẾN

t

h
ó
a
1

t
i
ề
n

t
ố

t
r
o
n
g

1

n
ú
t
Nén mức
Nhược điểm:
5
- Cây có số node lớn

(v)
F
2^k-1
(v) Port
2^k-1
(v) Child
2^k-1
(v)
Le (w) s(w)
Nexthop
(port(s(w)))
Right(w)
Nút Thứ cấp (s_node)
Same
Prefix Tree node
CẤU TRÚC CỦA MỘT NÚT CÂY k - CMST
6
THAO TÁC BẢNG ĐỊNH TUYẾN
Thao tác chèn tiền tố: CMST_INSERT(p, v)
Input: tiền tố p; Cây k-CMST gốc v
Output: p được chèn vào k-CMST
Độ phức tạp tính toán: O(W/k);
7
MÔ TẢ HOẠT ĐỘNG THUẬT TOÀN CHÈN
CHƯƠNG 3: ÁP DỤNG CTDL CMST ĐỂ GIẢI QUYẾT
BÀI TOÁN XÂY DỰNG BẢNG ĐỊNH TUYẾN ĐỘNG
8
8
8
Chèn : ( 00100* , Q )

- Số tiền tố tối đa trong nút chính: 2
k+1
,
trong nút thứ cấp: 2
k-1
- Sự phân loại các hậu tố:
Chiều cao cây: h < (W/k+k-1)
p: hậu tố trong u, có tiền tố nguyên thủy là p’
q: hậu tố trong v, có tiền tố nguyên thủy là q’
q’ là tiền tố con của p’
Len(p) < k  PT of (v)
Len(p) = k  port
r
(v)
Len(p) > k  f
r
(v)
Level(u) < Level(v)
TC1
TC2
TC3
13
(u gần nút gốc hơn v)
CHƯƠNG 3: ÁP DỤNG CTDL CMST ĐỂ GIẢI QUYẾT
BÀI TOÁN XÂY DỰNG BẢNG ĐỊNH TUYẾN ĐỘNG
- Nhiều hậu tố trong 1 nút
- Sự phân loại các tiền tố:
k-CMST là cấu trúc có nhiều ưu điểm so với các cấu trúc khác (trong chương 2) trong ứng dụng làm bảng định
tuyến động
14

KỸ THUẬT PHÂN HOẠCH k-CMST THÀNH k-PCMST
- Mảng A[i] không quá 2
β
phần tử, mỗi phần tử có 2 trường: Output_port và pointer
(trỏ tới nút gốc của một k-CMST con)
17
- Chiều cao cây giảm mà không làm tăng bước nhảy k
CÁC KỸ THUẬT CẢI TIẾN K-CMST: KỸ THUẬT PHÂN HOẠCH (2)
18
THỬ NGHIỆM ĐÁNH GIÁ HIỆU QUẢ k-CMST và k-IPCMST
SO SÁNH THỜI GIAN TRA CỨU CỦA 2-CMST VÀ 2-IPCMST
VỚI SỐ LUẬT CỐ ĐỊNH 4000 LUẬT
19
k-IPCMST: là thuật toán cải tiến k-CMST trên cơ sở áp dụng tổng hợp 3 kỹ thuật tăng tốc nói trên
THỬ NGHIỆM ĐÁNH GIÁ HIỆU QUẢ k-CMST và k-IPCMST
SỰ ẢNH HƯỞNG CỦA SỐ LƯỢNG LUẬT TỚI THỜI GIAN TRA CỨU
 Sự ảnh hưởng này là không lớn
20
KẾT LUẬN & KIẾN NGHỊ
KẾT LUẬN:
HƯỚNG PHÁT TRIỂN:
21
Kết quả nghiên cứu thu được có tính khoa học, chính xác và ổn định cao:
- Khẳng định ưu thế của CTDL cây k-CMST trong ứng dụng làm BĐTĐ
- Đề xuất thuật toán k-IPCMST có hiệu quả định tuyến cao hơn
Nhằm khắc phục một số hạn chế:
- Chi phí bộ nhớ k-IPCMST cao hơn k-CMST
- Chưa cấp phát bộ nhớ theo mức tối ưu (mức nút càng cao, yêu cầu bộ nhớ càng giảm)
- Một số phần của các quá trình xử lý có thể xử lý song song chưa được áp dụng
- Hệ thống lại nền lý thuyết và lịch sử vấn đề nghiên cứu