Báo Cáo Phân gói tốc độ cao sử dụng cây đoạn

Lời mở đầu


Môn học cấu trúc dữ liệu nâng cao là môn học cơ bản và rất quan trọng với sinh viên ngành công nghệ thông tin. Cấu trúc dữ liệu cùng với giải thuật tạo nên chương trình. Việc phân tích bài toán để chọn ra cấu trúc dữ liệu đúng, phù hợp đặc biệt hiệu quả là việc làm không hề dễ dàng và mang tính quyết định đến việc lựa chọn các giải thuật phù hợp cũng như xác định tính đúng đắn và tính hữu hạn của giải thuật, tính tối ưu của bài toán. Xác định cấu trúc dữ liệu là vấn đề mấu chốt của việc thiết kế phần mềm và có tính quyết định đến thành công của phần mềm.
Mặc dù thời gian tìm hiểu có hạn, song với sự tận tâm của thầy giáo Nguyễn Mạnh Hùng đã giúp chúng em hiểu biết thêm giá trị quan trọng của cấu trúc dữ liệu, đặc biệt được học thêm một số cấu trúc dữ liệu mới mà chúng em chưa biết, chưa được học ở bậc đại học. Mặc dù có được cung cấp bài giảng môn học, tài liệu tham khảo về bài tập lớn cộng với sự cố gắng nỗ lực không ngừng của bản thân nhưng không tránh được các khuyết điểm, sai sót trong quá trình hoàn thành bài tập lớn này. Một lần nữa cho phép chúng em được cảm ơn thầy giáo Nguyễn Mạnh Hùng đã giúp chúng em trong suốt thời gian học tập môn học cũng như giải đáp các thắc mắc, cho chúng em một sự tự tin hơn, một cách nhìn tốt hơn, một phương pháp luận đúng đắn về môn học này.

Phần 1. Nội dung bài báo
I. Giới thiệu
II. Công việc liên quan và đóng góp của chúng ta
III. Gói phân loại, cây phân đoạn, và phân tầng
A. Cây phân đoạn và địa chỉ đích
B. Xếp chồng phân đoạn và địa chỉ nguồn
C. Thuật toán phân gói
IV. Kết quả thực nghiệm
Phần 2. Xây dựng cây đoạn và chương trình Demo
Kèm theo báo cáo này là Slide trình diễn và chương trình Demo thuật toán.
Chúng em xin chân thành cảm ơn!

Hà Nội, ngày tháng 3 năm 2011
Học viên



Phạm Xuân Dưỡng
Trần Quyết Chiến
PHẦN 1
NỘI DUNG CỦA BÀI BÁO
"PHÂN GÓI TỐC ĐỘ CAO SỬ DỤNG CÂY ĐOẠN"

Đặt vấn đề : Do Internet phát triển thành một cơ sở hạ tầng thương mại, dịch vụ mạng ngày càng đòi hỏi các bộ định tuyến về phân các gói dữ liệu dựa trên một hoặc nhiều trường trong tiêu đề gói tin cho ra chất lượng dịch vụ(QoS) khác nhau. Thách thức lớn nhất đối với phân gói là giữ cho thời gian phân gói và yêu cầu lưu trữ nhỏ. Trong bài này, chúng ta thiết kế một thuật toán phân gói tin nhanh 2 chiều với yêu cầu bộ nhớ nhỏ. Thuật toán dựa trên kỹ thuật hình hoc máy tính-cây đoạn và xếp chồng phân đoạn để đạt được thời gian phân gói logarit. Đối với một cơ sở dữ liệu N bộ lọc, thuật toán đề xuất có thể hoàn thành một thao tác phân gói trong thời gian O(logN) và yêu cầu bộ nhớ kèm theo là O(NlogN).
I Giới thiệu
1. Mục đích:
Phân gói tốc độ cao sử dụng cây phân đoạn được đề xuất bởi Ching-Fong Su tại hội nghị viễn thông toàn cầu Sanfrancisco USA năm 2000.
Mục đích của bài báo nhằm thiết kế phân gói tin nhanh 2 chiều với yêu cầu bộ nhớ nhỏ. Thuật toán dựa trên cây phân đoạn và xếp chồng phân đoạn để đạt được thời gian phân gói logarit. Đối với một cơ sở dữ liệu N bộ lọc, thuật toán đề xuất có thể hoàn thành một thao tác phân gói trong thời gian O(logN) và yêu cầu bộ nhớ kèm theo là O(NlogN).
2. Giới thiệu:
Hầu hết các bộ định tuyến Internet hiện hành quyết định chuyển tiếp gói tin dựa trên địa chỉ đích. Các gói tin với địa chỉ cùng một điểm đến thường chuyển và xử lý theo cách tương tự. Mặc dù có sự nỗ lực của dịch vụ, mô hình chuyển tiếp là đủ để cung cấp duy nhất, sự khác biệt nó không có khả năng cung cấp chất lượng dịch vụ mà đang trở thành chủ yếu như Internet phát triển thành một cơ sở hạ tầng thương mại. Ví dụ, dịch vụ mạng trong tương lai như: chính sách định tuyến, tường lửa, mạng riêng ảo yêu cầu tất cả các bộ định tuyến phân loại các gói tin dựa trên một hoặc nhiều trường trong tiêu đề gói tin.
Giả sử các bộ định tuyến duy trì một cơ sở dữ liệu gồm có N bộ lọc FI, F2, ., FN, với mỗi K trường tương ứng với các trường của tiêu đề gói tin. Các trường bộ lọc có thể là một tiền tố (ví dụ, nguồn / địa chỉ đích), một số quy định đầy đủ (ví dụ, loại giao thức) hay một vùng (ví dụ, số cổng). Việc phân loại gói tin được định nghĩa là một vấn đề về nhận dạng bộ lọc (hoặc các bộ lọc) mà một gói tin phù hợp dựa trên một hoặc nhiều trường trong tiêu đề gói tin. Để dễ dàng thảo luận, chúng ta giả định có một "chi phí" (hay trọng số) kết hợp với mỗi bộ lọc. Nếu một gói tin phù hợp với nhiều bộ lọc, bộ lọc ít chi phí nhất được ưu tiên và các hành động tương ứng được thực hiện.
Việc phân loại gói tin có thể được coi là một vấn đề điểm vị trí trong tính toán hình học, xem ví dụ [l 0,2]. Cho N đối tượng K-chiều (ví dụ, K-trường bộ lọc) và một điểm (ví dụ, một gói tin) trong một không gian, phân loại gói tin có nghĩa là để tìm kiếm các đối tượng mà điểm đó thuộc về. Lưu ý rằng vấn đề điểm vị trí thường khó khăn. Ví dụ, khi xem xét các vấn đề điểm vị trí của N đối tượng không chồng chéo trong không gian K> không gian 3 chiều, nó đã được chứng minh [2] rằng giải pháp cần phải có thời gian O(1ogN) với không gian O(NK), hoặc O(logK - 1N) thời gian với không gian O(N). Giới hạn không gian thời gian như vậy là không thể chấp nhận để phân loại gói tin tại bộ định tuyến khi N là theo thứ tự của hàng chục ngàn, và hàng triệu phân loại mỗi giây là bắt buộc.
May mắn thay, phân loại gói tin IP khác với vấn đề điểm vị trí nói chung trong nhiều cách mà làm cho nó thêm dể làm. Mặc dù có 5 trường (địa chỉ nguồn/đích, các loại giao thức, và số cổng nguồn/đích đến) trong tiêu đề có thể được xem xét để phân loại, không phải tất cả trong số chúng cùng góp phần phức tạp cho vấn đề. Đối với mục đích chuyển tiếp, các bộ định tuyến có thể phân biệt các gói tin bởi giao thức TCP, UDP, và những loại khác. Độ phức tạp chủ yếu của việc phân loại gói tin là kết quả của trường địa chỉ nguồn và địa chỉ đích đến do sự đa dạng lớn của tiền tố có thể xuất hiện trong các bộ lọc. Do đó trong bài báo này chúng ta sẽ tập trung chủ yếu vào phân loại gói 2 chiều bằng cách sử dụng địa chỉ nguồn và đích.
Vấn đề bảng định tuyến tra cứu là một ví dụ về phân loại một chiều. Đã có nhiều giải pháp hiệu quả, xem (3-121). Ví dụ, một thuật toán hiệu quả dựa trên tìm kiếm nhị phân đã được đề xuất trong [9], trong đó có O(1ogN) thời gian và không gian O(N) yêu cầu. Gần đây, vấn đề phân loại gói tin trên hai hoặc nhiều trường được nghiên cứu sâu, và không gian thời gian khác nhau yêu cầu được thể hiện đối với trường hợp 2-chiều, ví dụ, [13-211. Lưu ý rằng điều quan trọng để giữ cho thời gian phân loại nhỏ do nhu cầu về xử lý gói tốc độ cao. Mặc dù người ta có thể dễ dàng tìm thấy một thuật toán với thời gian nhỏ tìm kiếm tìm kiếm bằng cách sử dụng số lượng lưu trữ, giải pháp đó không mong muốn. Mục tiêu của bài này là để thiết kế một đề án phân loại 2 chiều mà có thời gian tìm kiếm nhỏ (theo thứ tự của O (1ogN)) và yêu cầu bộ nhớ gần như tuyến tính (theo thứ tự của O (N1ogN)). Phần còn lại của bài báo được tổ chức như sau. Trong II, chúng ta mô tả ngắn gọn công việc liên quan và so sánh chúng với các thuật toán của chúng ta. Chúng ta thảo luận về hai cấu trúc dữ liệu quan trọng và thực hiện các thuật toán của chúng ta trong III. Các kết quả thử nghiệm được trình bày trong IV,tiếp theo là các kết luận trong V.