Xem mẫu
- dce
Thời điểm và nơi quyết định việc tìm đường
2008
• Thời điểm quyết định
– Trên cơ sở mạch ảo hoặc gói
– Datagram: quyết định tìm đường thực hiện riêng cho mỗi
gói
– Virtual circuit: quyết định tìm đường thực hiện lúc kết nối
• Trong nhiều thiết kế, đường đi của mỗi virtual circuit thay đổi theo
điều kiện của mạng
• Nơi quyết định
– Node nào sẽ ra quyết định tìm đường
– Phân tán (Distributed)
• Mỗi node tự ra quyết định tìm đường
– Tập trung (Centralized)
• Nhiệm vụ tìm đường được gán trước cho 1 số node
– Tại nguồn gởi (Source)
• Nguồn gởi chịu trách nhiệm tìm đường
• Cho phép người dùng chọn đường đi theo tiêu chí của họ
Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 11
- Nguồn thông tin mạng và thời điểm cập
dce
2008
nhật thông tin
• Quyết định tìm đường thông thường (không phải luôn luôn)
được dựa trên các thông tin về mạng
– Tải lưu thông
– Chi phí của đường link
• Tìm đường phân tán (Distributed routing)
– Node sử dụng các thông tin cục bộ
– Có thể thu thập thông tin từ các node kế cận
– Có thể thu thập thông tin từ các node trên đường tiềm năng
• Tìm đường tập trung (Central routing)
– Thu thập thông tin từ tất cả các node
• Cập nhật thông tin
– Xác định khi nào các thông tin mạng được lưu trữ tại các node được
cập nhật
– Cố định (Fixed) – không bao giờ được cập nhật
– Động (Adaptive) – cập nhật thường xuyên
– Trade off
Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 12
- dce
Chiến thuật tìm đường
2008
• Chiến thuật (Routing Strategies)
– Fixed routing
– Flooding routing
– Random routing
– Adaptive routing
Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 13
- dce
Fixed Routing
2008
• Một lộ trình cố định cho
mỗi đường đi từ nguồn đến
đích
• Tất cả các đường đi qua
mạng đều đã được thiết lập
từ trước và không cập nhật
theo các biến đổi về các
điều kiện tải, … trong mạng
• Đường đi được xác định
dùng giải thuật chi phí tối
thiểu
• Đường cố định ít ra cho
đến khi có sự thay đổi cấu
hình mạng
• Không có sự khác biệt giữa
datagram và VC
• Đơn giản
• Không đáp ứng lại lỗi và
nghẽn mạng
Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 14
- dce
Flooding Routing
2008
• Không cần thông tin mạng
• Node gởi các gói tới tất cả node kề (láng giềng)
• Các gói nhận được sẽ được truyền trên tất cả các
kết nối ngoại trừ kết nối đến
• Cuối cùng sẽ có một số copy của gói sẽ đến đích
• Mỗi gói được đánh số duy nhất sao cho các copy
trùng nhau sẽ bị loại bỏ
• Node có thể ghi nhớ các gói đã đi qua, giúp cho
mạng không quá tải nhiều
• Có thể chứa số chặng đường (hop) trong các gói,
được dùng để giới hạn hay kết thúc quá trình truyền
Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 15
- dce
Flooding Routing
2008
• Đặc điểm
– Tất cả các lộ trình đều được
thử
• Robust
• Lãng phí băng thông
– Ít nhất sẽ có một gói đi theo lộ
trình với số chặng ít nhất
• Có thể được dùng để thiết
lập đường mạch ảo
– Tất cả các node đều được
“duyệt”
• Dùng để phân tán thông tin
– Gửi các mesg khẩn
• Mạng quân sự
– Thiết lập VC
– Broadcast thông tin
Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 16
- dce
Random Routing
2008
• Node sẽ chọn một đường liên kết ra để truyền đi các
gói nhận được
• Việc chọn lựa có thể là ngẫu nhiên hoặc xoay vòng
(round robin)
• Có thể chọn đường liên kết ra dựa trên việc tính
toán xác suất R
Pi i
R i
i
• Không cần thông tin mạng
• Lộ trình tìm được thông thường không phải là đường
có chi phí tối thiểu hoặc số chặng nhỏ nhất
Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 17
- dce
Adaptive Routing
2008
• Được sử dụng bởi hầu hết các mạng chuyển mạch
gói
• Quyết định tìm đường thay đổi khi các điều kiện trên
mạng thay đổi
– Hư hỏng (Failure): một node hoặc một trunk hư
– Nghẽn (Congestion)
• Cần biết các thông tin về mạng
• Quyết định tìm đường là một hàm phức tạp
• Tradeoff giữa chất lượng của thông tin mạng và chi
phí
• Phản ứng quá nhanh có khả năng gây dao động
• Quá chậm dẫn đến không còn thích hợp
Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 18
- dce
Adaptive Routing
2008
• Ưu điểm
– Hiệu suất được cải thiện
– Trợ giúp điều khiển nghẽn mạng
• Cân bằng tải, tránh tắc nghẽn
– Hệ thống phức tạp để hiện thực
• Có khả năng không thực hiện các ích lợi về mặt lý thuyết
• Phân loại
– Dựa trên các nguồn thông tin
• Cục bộ (isolated)
• Các node kề (distributed)
• Tất cả các node (centralized)
Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 19
- dce
Isolated Adaptive Routing
2008
• Mỗi node trong mạng tự cập nhật bảng tìm đường của mình
dựa vào các thông tin về mạng mà node đó học hỏi được,
không trao đổi thông tin routing với các node khác
• Gởi các gói trên các liên kết ra có hàng đợi ngắn nhất
– Cân bằng tải trên các đường ra
– Đường ra có hàng đợi ngắn nhất có thể không đúng hướng cần đi
• Có thể thêm các độ thiên vị (bias) cho các đường ra
• Một trong những phương pháp đơn giản nhất của tìm đường
động, phù hợp với các mạng có kích thước nhỏ và hoạt động
tương đối ổn định
• Ít dùng (không dùng thông tin có sẵn)
Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 20
nguon tai.lieu . vn
