Đồ Án Nghiên cứu bài toán so khớp tiền tố dài nhất áp dụng trong Router(TM+ chương trình)

1. Tên đồ án:
“Nghiên cứu bài toán so khớp tiền tố dài nhất áp dụng trong Router”
2. Các số liệu ban đầu: . .
3. Nội dung bản thuyết minh:
Chương 1: Tổng quan về định tuyến.
Chương 2: Cây tìm kiếm ưu tiên.
Chương 3: Định tuyến IP theo phương pháp khớp tiền tố dài nhất.
Chương 4: Định tuyến IP theo độ ưu tiên.
4. Số lượng, nội dung các bản vẽ: .


MỤC LỤC

TOC o "1-4" h z u LỜI NÓI ĐẦU PAGEREF _Toc201078474 h 1 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400370034000000
Chương 1 TỔNG QUAN VỀ ĐỊNH TUYẾN PAGEREF _Toc201078475 h 3 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400370035000000
1.1 Thiết bị định tuyến - Router. PAGEREF _Toc201078476 h 3 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400370036000000
1.2 Định tuyến trên Internet PAGEREF _Toc201078477 h 4 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400370037000000
1.2.1 Khái niệm về định tuyến. PAGEREF _Toc201078478 h 4 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400370038000000
1.2.2 Thuật toán định tuyến. PAGEREF _Toc201078479 h 5 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400370039000000
1.3 Bảng định tuyến. PAGEREF _Toc201078480 h 6 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400380030000000
1.3.1 Bảng định tuyến tĩnh. PAGEREF _Toc201078481 h 8 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400380031000000
1.3.2 Bảng định tuyến động. PAGEREF _Toc201078482 h 10 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400380032000000
Chương 2 CÂY TÌM KIẾM ƯU TIÊN PAGEREF _Toc201078483 h 12 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400380033000000
2.1 Radix Priority Search Tree. PAGEREF _Toc201078484 h 12 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400380034000000
2.1.1 Tính chất cây. PAGEREF _Toc201078485 h 12 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400380035000000
2.1.2 Xây dựng một cây. PAGEREF _Toc201078486 h 13 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400380036000000
2.1.3 Chèn một nút vào cây RPST PAGEREF _Toc201078487 h 16 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400380037000000
2.1.4 Xóa một nút khỏi cây RPST PAGEREF _Toc201078488 h 18 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400380038000000
2.2 Red-Black Priority Search Tree. PAGEREF _Toc201078489 h 19 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400380039000000
2.2.1 Tính chất cây. PAGEREF _Toc201078490 h 19 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400390030000000
2.2.2 Chèn một nút vào cây RBPST PAGEREF _Toc201078491 h 22 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400390031000000
2.2.3 Xóa một nút từ cây RBPST PAGEREF _Toc201078492 h 27 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400390032000000
2.3 Các truy vấn trong cây tìm kiếm ưu tiên. PAGEREF _Toc201078493 h 29 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400390033000000
2.3.1 MinXinRectangle. PAGEREF _Toc201078494 h 29 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400390034000000
2.3.2 MaxXinRectangle. PAGEREF _Toc201078495 h 31 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400390035000000
2.3.3 MinYinXRange(x[SUB]0[/SUB], x[SUB]1[/SUB]) PAGEREF _Toc201078496 h 32 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400390036000000
2.3.4 EnumerateRectangle. PAGEREF _Toc201078497 h 34 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400390037000000
Chương 3 ĐỊNH TUYẾN IP THEO PHƯƠNG PHÁP KHỚP TIỀN TỐ DÀI NHẤT   PAGEREF _Toc201078498 h 36 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400390038000000
3.1 Mở đầu. PAGEREF _Toc201078499 h 36 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003400390039000000
3.1.1 Khớp tiền tố dài nhất PAGEREF _Toc201078500 h 36 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500300030000000
3.1.2 Lý thuyết về đoạn. PAGEREF _Toc201078501 h 37 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500300031000000
3.2 Ứng dụng cây tìm kiếm ưu tiên trong bài toán định tuyến router theo phương pháp khớp tiền tố dài PAGEREF _Toc201078502 h 48 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500300032000000
3.2.1 Biểu diễn tập các đoạn trên cây tìm kiếm ưu tiên. PAGEREF _Toc201078503 h 48 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500300033000000
3.2.2 Biểu diễn tiền tố trên cây tìm kiếm ưu tiên. PAGEREF _Toc201078504 h 50 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500300034000000
3.2.3 Đoạn không giao nhau. PAGEREF _Toc201078505 h 52 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500300035000000
3.2.4 Các đoạn Conflict free. PAGEREF _Toc201078506 h 53 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500300036000000
3.2.4.1 Xác định msr(d) PAGEREF _Toc201078507 h 53 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500300037000000
3.2.4.2 Chèn một đoạn. PAGEREF _Toc201078508 h 53 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500300038000000
3.2.4.3 Xóa một đoạn. PAGEREF _Toc201078509 h 54 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500300039000000
3.2.4.4 Độ phức tạp. PAGEREF _Toc201078510 h 55 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500310030000000
Chương IV. ĐỊNH TUYẾN IP THEO ĐỘ ƯU TIÊN PAGEREF _Toc201078511 h 57 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500310031000000
4.1 Cấu trúc cây nhị phân trên cây nhị phân - BOB PAGEREF _Toc201078512 h 57 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500310032000000
4.1.1 Cấu trúc dữ liệu. PAGEREF _Toc201078513 h 57 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500310033000000
4.1.1.1 Cấu trúc cây ngoài PAGEREF _Toc201078514 h 57 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500310034000000
4.2.1.2 Cấu trúc cây bên trong. PAGEREF _Toc201078515 h 60 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500310035000000
4.1.2 Tìm kiếm PAGEREF _Toc201078516 h 61 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500310036000000
4.1.3 Chèn một đoạn. PAGEREF _Toc201078517 h 61 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500310037000000
4.1.4 Phép quay cây. PAGEREF _Toc201078518 h 63 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500310038000000
4.1.5 Xóa một đoạn. PAGEREF _Toc201078519 h 66 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500310039000000
4.1.6 Độ phức tạp của BOB PAGEREF _Toc201078520 h 68 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500320030000000
4.2 Bảng tiền tố có độ ưu tiên cao nhất - PBOB PAGEREF _Toc201078521 h 69 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500320031000000
4.3.1 Cấu trúc dữ liệu. PAGEREF _Toc201078522 h 69 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500320032000000
4.3.2 Tìm kiếm PAGEREF _Toc201078523 h 69 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500320033000000
4.3.3 Chèn và xóa. PAGEREF _Toc201078524 h 71 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500320034000000
4.3 Bảng tiền tố khớp dài nhất – LMPBOB PAGEREF _Toc201078525 h 72 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500320035000000
4.3.1 Cấu trúc dữ liệu. PAGEREF _Toc201078526 h 72 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500320036000000
4.3.2 Tìm kiếm PAGEREF _Toc201078527 h 72 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500320037000000
4.4.3 Chèn và xóa trong LMPT PAGEREF _Toc201078528 h 74 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500320038000000
KẾT LUẬN ĐỒ ÁN PAGEREF _Toc201078529 h 76 08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003200300031003000370038003500320039000000









Tran Thi Thanh Huyen