Bài giảng Mạng máy tính (Computer Network): Chương 7 - Lưu Đức Trung
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (391.69 KB, 18 trang )
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: ln chỉ dùng một phương pháp
Dynamic routing: ln 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 tố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 ln) 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 tố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 q 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 tố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 xun
Việc ra quyết định rất phức tạp
Khối lượng tính tố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 q 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 tố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 tốn kết thúc khi tất cả các nút mạng đã được đưa vào
T
