Tiểu Luận: Các Thuật Toán Và Phương Thức Định Tuyến Trong Mạng

Một trong những hoạt động của mạng nói chung là việc truyền dữ liệu từ nguồn tới đích. Định tuyến là một chức năng không thể tách rời của mạng khi truyền dữ liệuh từ nguồn tới đích và có ý nghĩa đặc biệt quan trọng trong việc thiết kế và tối ưu mạng. Cấu trúc mạng, giải pháp công nghệ và phương pháp định tuyến là 3 vấn đề liên quan mật thiết với nhau và quyết định chất lượng hoạt động của mạng. Chính vì vậy, bài toán định tuyến cần được quan tâm nghiên cứu để nhằm tối ưu hóa hiệu suất...
Nội dung trích xuất từ tài liệu:
Tiểu Luận: Các Thuật Toán Và Phương Thức Định Tuyến Trong Mạng TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN ĐIỆN TỬ VIỄN THÔNG ********** ********** BÀI TẬP LỚN MÔN HỌC: TỔ CHỨC VÀ QUY HOẠCH MẠNG VIỄN THÔNG Đề tài: “Các Thuật Toán Và Phương Thức Định Tuyến Trong Mạng ” Giảng viên hướng dẫn: Nguyễn Văn Thắng Nhóm sinh viên thực hiện: Họ và tên Lớp SHSV  HÀ NỘI 4/2012 Mục Lục I. Mở đầu.....................................................................................................................3 Nội dung ..............................................................................................................4 II. Giới thiệu về định tuyến: ...............................................................................4 1. Các khái niệm trong lý thuyết graph:...........................................................5 2. Phân loại định tuyến : ....................................................................................8 3. 3.1. Định tuyến tĩnh: .........................................................................................8 3.2. Định tuyến ngẫu nhiên (random routing): ..............................................9 3.2.1. Định tuyến ngẫu nhiên lan tràn gói (flooding): ....................................9 3.2.2. Định tuyến ngẫu nhiên (random walk): ..............................................11 3.2.3. Định tuyến ngẫu nhiên (hot potato): ...................................................11 3.3. Định tuyến động (dynamic routing): .....................................................12 3.3.1. Định tuyến động (minimum spanning tree):.......................................13 3.3.2. Định tuyến động (shortest path tree): .................................................13 Các thuật toán dùng để định tuyến: ...........................................................14 4. 4.1. Thuật toán Prim: .....................................................................................14 4.2. Thuật toán Kruskal: ................................................................................17 4.3. Thuật toán Dijkstra: ................................................................................19 4.4. Thuật toán Bellman Ford: ......................................................................20 Một số giao thức định tuyến động hiện nay: ..............................................21 5. 5.1. Giao thức định tuyến RIP (Routing Information Protocol): ..............22 5.2. OSPF (Open Shortest Path First): .........................................................23 5.3. EIGRP (Enhanced Interior Gateway Routing Protocol): ...................25 III. Kết luận .............................................................................................................27 IV. Tài liệu tham khảo ...........................................................................................28 2 Mở đầu I. Một trong những hoạt động của mạng nói chung là việc truyền dữ liệu từ nguồn tới đích. Định tuyến là một chức năng không thể tách rời của mạng khi truyền dữ liệuh từ nguồn tới đích và có ý nghĩa đặc biệt quan trọng trong việc thiết kế và tối ưu mạng. Cấu trúc mạng, giải pháp công nghệ và phương pháp định tuyến là 3 vấn đề liên quan mật thiết với nhau và quyết định chất lượng hoạt động của mạng. Chính vì vậy, bài toán định tuyến cần được quan tâm nghiên cứu để nhằm tối ưu hóa hiệu suất sử dụng tài nguyên mạng. Trên thế giới đã có nhiều nghiên cứu về các phương pháp định tuyến, với mục đích chủ yếu là tìm ra những phương pháp định tuyến thích hợp để áp dụng vào thực tế mạng lưới. Trong thời gian gần đây, xu hướng định tuyến theo “giá” trên mạng đã trở thành một chủ đề nghiên cứu quan trọng. Thông thường, lợi ích mang lại trên mạng được tối đa bằng việc tối ưu hóa các hàm mục tiêu. Tùy thuộc vào cấu trúc và các đường truyền trên mạng mà các hàm mục tiêu và ràng buộc đi theo sẽ khác nhau. 3 II. Nội dung Giới thiệu về định tuyến: 1. Định tuyến là quá trình tìm đường đi để truyền tải thông tin trong liên mạng từ nguồn đến đích. Nó là một chức năng được thực hiện ở tầng mạng. Chức năng này cho phép router đánh giá các đường đi sẵn có tới đích. Để đánh giá đường đi, định tuyến sử dụng các thông tin về Topology của mạng. Các thông tin này có thể do người quản trị thiết lập. Quá trình định tuyến cần thỏa mãn các yêu cầu cho trước bao gồm: đường đi ngắn nhất hoặc có băng thông rộng nhất. Đường đi thường phải tối ưu theo một trong hai tiêu chí.các gói tin có thể được gửi đi theo đường này. Nhưng cũng có thể chúng được gửi đi đồng thời trên nhiều đường . Việc định tuyến được sử dụng cho nhiều loại mạng: mạng viễn thông, liên mạng, internet, mạng giao thông. Hình 1: Tìm đường đi tiếp theo Định tuyến có thể được chia ra làm 3 phương pháp định tuyến: định tuyến tĩnh, định tuyến ngẫu nhiên và định tuyến động. Trong môi trường mạng thường xuyên có sự thay đổi ngẫu nhiên nên định tuyến tĩnh chỉ có ý nghĩa ở các gateway và các mạng nhỏ. Trong định tuyến động, có hai phương thức định tuyến: tìm đường theo đường đi ngắn nhất ...