Bài giảng Mạng máy tính (Computer Network): Chương 7 - Lưu Đức Trung

Chia sẻ: Bạch Khinh Dạ Lưu | Ngày: | Loại File: DOC | Số trang:18

Thêm vào BST

Báo xấu

17
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Mạng máy tính (Computer Network): Chương 7 - Lưu Đức Trung cung cấp đến học viên các kiến thức về định tuyến, định tuyến trong chuyển mạch tương tự, định tuyến trong chuyển mạch gói, định tuyến thay thế, thời gian và địa điểm ra quyết định định tuyến,... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Mạng máy tính (Computer Network): Chương 7 - Lưu Đức Trung

MẠNG MÁY TÍNH (COMPUTER NETWORK) Chương 7 – Định tuyến 7.1. Định tuyến trong chuyển mạch tương tự Đa số các kết nối đi qua ít nhất một bộ chuyển mạch Cần định tuyến Tính hiệu quả Ổn định/đàn hồi Có 2 cách định tuyến Static routing: luôn chỉ dùng một phương pháp Dynamic routing: luôn thay đổi tùy theo tình trạng của mạng
Định tuyến thay thế Các tuyến đường có thể giữa các tổng đài được xác định sẵn Bộ switch xuất phát tự chọn một đường phù hợp Danh sách các tuyến được liệt kê có thứ tự Vào các thời điểm khác nhau, tập các tuyến được sử dụng có thể khác nhau Sơ đồ tìm đường thay thế
7.2. Định tuyến trong chuyển mạch gói Định tuyến: một khía cạnh quan trọng và phức tạp trong các mạng chuyển mạch gói Các đặc trưng đòi hỏi Tính chính xác (Correctness) Tính đơn giản (Simplicity) Tính mạnh (Robustness) Tính ổn định (Stability) Tính cân bằng (Fairness)
Tính tối ưu (Optimality) Tính hiệu quả (Efficiency) Các tiêu chuẩn thi hành Được sử dụng để định tuyến Số chặng chuyển mạch tối thiểu Chi phí thấp nhất → Các thuật toán cơ bản Thời gian và địa điểm ra quyết định định tuyến Thời gian Dựa vào gói tin hoặc mạch ảo
Địa điểm Phân tán: Từng nút tự quyết định Tập trung Nguồn phát tin tự tìm (độc lập) Nguồn thông tin và thời điểm cập nhật thông tin Thường (không phải luôn) các quyết định định tuyến dựa trên thông tin có được từ mạng Với chính sách định tuyến phân tán
Các nút sử dụng các thông tin tại chỗ Cũng có thể thu thập từ các nút xung quanh Hoặc lấy từ các nút trên đường đi dự tính Với chính sách định tuyến tập trung Lấy thông tin từ mọi nút Thời điểm cập nhật thông tin Khi nào các nút đã cập nhật (định kỳ) Cố định không cần cập nhật Thích nghi – liên tục cập nhật
7.3 Các chính sách định tuyến Cố định Fixed Làm ngập Flooding Ngẫu nhiên Random Thích nghi – Adaptive Định tuyến cố định Fixed Routing Tìm sẵn một đường đi cho mỗi cặp nguồn đích
Xác định các tuyến bằng thuật toán chi phí thấp nhất Từng tuyến không đổi, chừng nào mà topo mạng không thay đổi Làm ngập Flooding Không cần thông tin mạng Một gói tin được gửi từ nút nguồn tới các nút láng giềng Gói tin được truyền đi tới các nút khác trừ đường đến Sau cùng một số bản sao gói tin sẽ đến đích
Từng gói tin được đánh số (duy nhất)nên các gói trùng lắp được bỏ đi → Các nút đều có khả năng “nhớ” các gói tin đã nhận và truyền → Tránh quá tải Có thể sử dụng giá trị đếm số bước đi trong gói tin Các tính chất làm ngập Tất cả các đường đi có thể đều được thử: là một chiến lược rất mạnh Sẽ có ít nhất một gói tin với ít bước chuyển nhất và nó được dùng để khởi tạo một mạch ảo
Tất cả các nút mạng đều được thăm: rất hữu ích cho chiến lược thu thập thông tin mạng theo hình thức phân tán Định tuyến ngẫu nhiên Mỗi nút chọn cho mình một đường ra để truyền lại gói tin thăm dò nhận được Cách chọn có thể ngẫu nhiên hoặc xoay vòng Có thể chọn đường ra dựa vào tính toán xác suất Không cần có thông tin mạng
Tuyến đường tìm được thường không có chi phí thấp nhất và cũng không phải đường có số chặng chuyển mạch ít nhất Định tuyến thích nghi Được sử dụng trong hầu hết các mạng chuyển mạch gói Các quyết định định tuyến dựa trên các thay đổi của mạng Sự cố → thay đổi topo Nghẽn Cần phải có thông tin mạng, thường xuyên
Việc ra quyết định rất phức tạp Khối lượng tính toán nhiều và định tuyến tốt nhất → Cần phải lựa chọn tiêu chuẩn cân bằng các yếu tố Phản ứng với thay đổi mạng rất nhanh → hiện tượng dao động Phản ứng quá chậm → vô ích Ưu nhược điểm của định tuyến thích nghi Cải thiện hiệu năng thi hành của mạng Có khả năng ngăn ngừa nghẽn mạng
Hệ thống phức tạp 7.4 Các thuật toán chi phí thấp nhất Là nền tảng của chính sách định tuyến Có thể là số chặng tối thiểu Có thể dựa trên trọng số Cho một mạng, đẳng hướng gồm các nút mạng và liên kết giữa chúng Mỗi liên kết có một trọng số theo mỗi hướng
Chi phí đường đi là tổng chi phí đến nút khởi hành cộng với chi phí đến nút kết thúc Chi phi liên kết có thể khác nhau theo các hướng, chẳng hạn do chiều dài hàng đợi theo mối chiều là khác nhau Nhiệm vụ: định tuyến đi ngắn nhất cho mỗi cặp nút Dijkstra’s Algorithm Định tuyến đi ngắn nhất từ nút nguồn đến nút đích.
Phương pháp: triển khai đường đi theo chiều dài tăng dần Gọi : N = Tập các nút mạng s = Nút nguồn T =Tập các nút đã được chấp nhận làm đường đi trước đó w(i, j) = chi phí từ nút i đến nút j w(i, i) = 0 w(i, j) = ∞ Nếu 2 nút không có đường đi trực tiếp
w(i, j) ≥ 0 Nếu có đường đi trực tiếp L(n) = Tổng chi phí từ nút nguồn tới nút n Tại điểm đến, L(n) là chi phí thấp nhất cần tìm Bước 1 [Bắt đầu] T = {s} Nút nguồn được đưa vào tập T L(n) = w(s, n) với n ≠ s Bước 2 [Chọn nút tiếp theo] Tìm nút lân cận chưa có trong T có chi phí đi từ s thấp nhất
Đưa nút tìm được vào tập T Đồng thời sáp nhập đường đi tới nó Bước 3 [Cập nhật chi phí] L(n) = min[L(n), L(x) + w(x, n)] với mọi n Ï T Nếu L(x) + w(x, n) nhỏ hơn L(n), thì đường đi từ s tới n là đường từ s tới x nối với đường từ x tới n Thuật toán kết thúc khi tất cả các nút mạng đã được đưa vào T