Nghiên cứu các giải thuật chọn đường trên mạng

nghiên cứu các giải thuật chọn đƯỜng trên mạng Giáo viên hướng dẫn : GS. TS. Nguyễn Thúc Hải Sinh viên thực hiện : Nguyễn Viết Ngọc Lớp : K96C2 Cỏc file liờn quan tới đồ ỏn: Giai thuat chon duong tren mang.rar 302 KB https://mega.co.nz/#!Eg9ygITR!EE5cx1T1r4DbWgwyCMQ JaEdvQn5idN5jhY2hkg8joG4 báo cáo tốt nghiệp trường đại học đông đô khoa công nghệ thông tin more information and additional documents connect with me here: Nội dung báo cáo tốt nghiệp  Các kỹ thuật chọn đƯỜng trong mạng  Kỹ thuật chọn đường thích nghi  Chọn đường theo véc-tơ khoảng cách  Chọn đường theo trạng thái liên kết  Kỹ thuật chọn đường không thích nghi  Chọn đường tĩnh  Chọn đường tập trung  Cài đặt thử nghiệm thuật toán chọn đƯỜng  Thuật toán Dijkstra  Cài đặt thuật toán Dijkstra  kết luận Các tiêu chuẩn thường đợc chọn để xác định đường đi tối ưu :  Độ dài đường dẫn (path length)  Độ tin cậy của việc truyền tin (reliability)  Độ trễ (delay)  Chi phí truyền tin (communication cost) Các kỹ thuật chọn đường trong mạng Chọn đường trong mạng là việc lựa chọn đường đi tối u để truyền một đơn vị dữ liệu từ trạm nguồn tới trạm đích • Mỗi router chia xẻ bảng chọn đường với các router lân cận • Bảng chọn đường (thông tin về toàn bộ mạng) gồm : ID mạng đích, “chi phí”, ID router kế tiếp • “Chi phí” là số chặng (hop) và là 1 đơn vị với mọi liên kết • Chu kỳ cập nhật bảng chọn đường ngắn (khoảng 30 giây/lần). Chọn đường theo véc-tơ khoảng cách Các bảng chọn đường trong một liên mạng Cập nhật bảng chọn đường cho router A • Mỗi router chia xẻ bảng chọn đường với toàn bộ các router trong mạng • Bảng chọn đường (thông tin về các router lân cận) gồm : ID quảng cáo, ID mạng lân cận, “chi phí”, ID router lân cận. • “Chi phí” là 1 giá trị đợc tính dựa trên sự biến đổi của yếu tố an toàn hay trạng thái liên kết • Chu kỳ cập nhật bảng chọn đường lớn (khoảng 30 phút/lần). Chọn đường theo trạng thái liên kết • Mỗi nút mạng có một bảng chọn đường gồm : nút mạng đích mà gói tin có thể đợc chuyển đến & các đường đi khác nhau tới đích. Chọn đường tĩnh • Bảng chọn đường đợc ngời quản trị mạng tính toán trớc và cài đặt trong mạng cố định. • Trớc khi gửi gói tin, một nút mạng tạo ra một số ngẫu nhiên và chọn ra một đường đi thích hợp dựa trên số ngẫu nhiên đó. • Trong mạng có một vài trung tâm điều khiển chọn đường RCC (Routing Control Center) để cất giữ thông tin tổng thể về mạng. • Các nút mạng có thể không gửi thông tin nào về mạng tới trung tâm hoặc (chọn đường tĩnh) gửi theo định kỳ (chọn đường động). Chọn đường tập trung • Ưu điểm : thông tin trong RCC đầy đủ nên đa ra quyết định chọn đường nhanh và chính xác. Giải phóng các nút mạng khỏi việc tính toán chọn đ- ường. • Nhợc điểm : dễ xảy ra tắc nghẽn do sự tập trung lu l- ợng cao tại các trung tâm điều khiển chọn đường. Thuật toán Dijkstra • lij : khoảng cách giữa 2 nút mạng ij. lij=vc nếu ktt đ- ường. • Nk : tập hợp của k+1 phần 1. Sơ đồ mạng ví dụ 2. A là đỉnh nguồn. Nhãn của các đỉnh đợc gán giá trị vô cùng lớn. 3. Nhãn của các đỉnh lân cận A đợc gán giá trị bằng khoảng cách giữa chúng 4. D là đỉnh có "giá trị" nhỏ nhất đợc chọn. Nhãn của các đỉnh lân cận D đợc gán giá trị bằng khoảng cách giữa chúng với giá trị nhãn của D Minh họa thuật toán Dijkstra (1) 5. C là đỉnh tiếp theo có nhãn nhỏ nhất đợc chọn. Cập nhật lại các nhãn lân cận C, đánh dấu lại đường đi CF (do CF<DF). 6. D đợc chọn tơng tự nh bớc 5. Đánh dấu lại BE (BE<DE) 7. Chọn đỉnh E tiếp theo Do EG = DG nên không cập nhật lại G 8. Chọn đỉnh F và cập nhật lại G (FG < DG). Các mũi tên đỏ là cây đường ngắn nhất từ A đến tất cả các đỉnh. Minh họa thuật toán Dijkstra (2) Cài đặt thuật toán Dijkstra Kết quả nghiên cứu :  Tìm hiểu, phân tích và đánh giá đợc các kỹ thuật chọn đ- ường tiêu biểu nhất.  Cài đặt thử nghiệm đợc thuật toán Dijkstra và mô phỏng quá trình chọn đường trên mạng. Hạn chế :  Cha tìm hiểu thực tế đợc quá trình chọn đường của các loại mạng khác nhau.  Cha cài đặt đợc thuật toán chọn đường trên một mạng thực sự. Kết luận