Luận văn: Tìm hiểu thuật toán Widest Shortest Path

Ngày nay việc gia tăng các giá trị gia tăng hứa hẹn một tương lai phát triển mạnh mẽ cho hệ thống mạng với các dịch vụ thời gian thực, băng thông rộng hay các dịch vụ liên quan đến tính kinh tế, bảo mật, chất lượng dịch vụ cao như mạng riêng ảo ( VPN). Bên cạnh sự ra đời của các mạng công nghệ cao thì vấn đề phải làm sao đảm bảo được tốc độ tính toán nhanh nhất và đạt hiệu suất tổng thể cho luồng lưu lượng khác nhau.....
Nội dung trích xuất từ tài liệu:
Luận văn: Tìm hiểu thuật toán Widest Shortest PathWidest Shortest Path GVHD: Hoàng Trọng Minh Luận văn Tìm hiểu thuật toán Widest Shortest PathSinh Viên : Nguyễn Thị Nghĩa 1Widest Shortest Path GVHD: Hoàng Trọng Minh Mục Lục Tổng quan…………………………………………………………1 I. Khái niệm định tuyến……………………………………………3 II. Giải thuật định tuyến………………………………………................4 2.1. Yêu cầu của giải thuật định tuyến…………………..………...4 2.2. Giải thuật tìm đường đi ngắn nhất và rộng nhất (WSP)………5 III. Giới thiệu về QoS (quality of service)………………………….…5 3.1.Định nghĩa về QoS…………………….................………5 3.2. Mô hình trạng thái QoS…………………………………..6 3.3. Mục tiêu định tuyến Qos…………….......................…......7 3.4. Các tham số QoS…………………….......................……7 3.5. Các giao thức và tiêu chuẩn liên quan đến QoS…………........9 IV. Các vấn đề về số đo ...........................................................................11 4.1. Số đo ........................................................................................11 4.2. phân phối số đo.........................................................................12 4.3. Thứ tự số đo..............................................................................12 V. Kĩ thuật lưu lượng...............................................................................13 5.1. Định tuyến QoS: tiếp cận khu vực và tổng thể........................14 5.2. Định tuyến khoanh vùng..........................................................15 5.3. Dịch vụ kết nối và không kết nối.............................................16 5.4. Mô hình lưu lượng ảo..............................................................16VI. Giao thức đường đi ngắn nhất (OSPF-open Shortest First)...........18Sinh Viên : Nguyễn Thị Nghĩa 2Widest Shortest Path GVHD: Hoàng Trọng MinhVII. Tìm hiểu về thuật toán Dijkstra và thuật toán A*…....................21 1. Thuật toán Dijkstra……………………………………...21 2. Thuật toán A*……………………………..……………..23 VIII. Ứng Dụng và kết luận…………………………………….24 TỔNG QUAN Ngày nay việc gia tăng các giá trị gia tăng hứa hẹn một tương lai phát triểnmạnh mẽ cho hệ thống mạng với các dịch vụ thời gian thực , băng thông rộng haycác dịch vụ liên quan đến tính kinh tế, bảo mật, chất lượng dịch vụ cao như mạngriêng ảo (VPN) Bên cạnh sự ra đời của các mạng công nghệ cao thì vấn đề là phải làm sao đảmbảo được tốc độ tính toán nhanh nhất và đạt hiệu năng tổng thể cho luồng lưulượng khác nhau. Hơn nữa cải thiện hiệu năng định tuyến là một bài toán đượcquan tâm hàng đầu trong mạng, Trong đề tài này chúng ta tập chung tìm hiểu về thuật toán WSP ( Widestshortest path alogorithm ). Thuật toán này chọn đường đi ngắn nhất dựa trên sốbước nhảy, và tìm đường rộng nhất dựa trên độ rộng băng thông. Để hiểu thuậttoán này trước hết chúng ta phải tìm hiểu về QoS (quality of service ) và đi đếnđịnh tuyến đảm bảo QoS (chất lượng dịch vụ ) qua thuật toán này như thế nàoSinh Viên : Nguyễn Thị Nghĩa 3Widest Shortest Path GVHD: Hoàng Trọng MinhI. khái niệm định tuyến Mục tiêu cơ bản của các phương pháp định tuyến nhằm sử dụng tối đa tàinguyên mạng, và tối thiểu hoá giá thành mạng. Để đạt được điều này kỹ thuật địnhtuyến phải tối ưu được các số mạng và người sử dụng như : Xác suất tắc ngẽn,băng thông, độ trễ, độ tin cậy, giá thành,v..v. Vì vậy, một kỹ thuật định tuyến phảithực hiện tốt 2 chức năng chính sau đây: 1.Quyết định chọn đường theo những tiêu chuẩn tối ưu nào đó. 2.Cập nhật thông tin định tuyến, tức là thông tin dùng cho chức năng Trong các mạng máy tính có rất nhiều các kỹ thuật định tuyến khác nhau đã đượcđưa ra. Sự phân biệt giữa các kỹ thuật định tuyến chủ yếu căn cứ vào các yếu tốliên quan đến 2 chức năng chính đã chỉ ra trên đây. Các yếu tố đó thường là: (a) Sự phân tán của các chức năng chọn đường trên các nút của mạng. (b) Sự thích nghi với trạng thái hiện hành của mạng. (c) Các tiêu chuẩn tối ưu để định tuyến. Tiêu chuẩn tối ưu để định tuyến được xác định bởi người quản lý hoặc ngườithiết kế mạng, nó có thể là: - Độ trễ trung bình của thời gian truyền gói tin. - Số lượng nút trung gian giữa nguồn và đích của gói tin. - Độ an toàn của việc truyền tin. - Nguồn tài nguyên mạng sử dụng cho truyền tin . - v.v.. - Tổ hợp của các tiêu chuẩn trên.Việc chọn tiêu chuẩn tối ư ...