Giáo trình Mạng máy tính - Chương 7: Định tuyến

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