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

trường đại học đông đô khoa công nghệ thông tin báo cáo tốt nghiệp nghiên cứu các giải thuật chọn đƯỜng trên mạng more information and additional documents connect with me here: 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 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 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 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) Chọn đường theo véc-tơ khoảng cá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 Các bảng chọn đường trong một liên mạng • “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). Cập nhật bảng chọn đường cho router A Chọn đường theo trạng thái liên kết • 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 tĩnh • 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. • 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 đó. Chọn đường tập trung • 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). • Ư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 Minh họa thuật toán Dijkstra (1) 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 (2) 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. Cài đặt thuật toán Dijkstra Kết luận 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ự.