BK
TP.HCM
2008
dce
Chương 8
Tìm đường trong mạng chuyển mạch
Tìm đường trong mạng chuyển mạch mạch
Tìm đường trong mạng chuyển mạch gói
Các giải thuật tìm đường đi ngắn nhất
2008
dce
©2008, Dr. Dinh Duc Anh Vu
2
Data Communication and Computer Networks
Tìm đường trong mạng chuyển mạch mạch
• Tìm đường
– Tìm đường đi kết nối qua mạng giữa 2 node đầu cuối sao
cho mạng được sử dụng hiệu quả nhất
• Chức năng
– Xác định kết nối từ thuê bao gọi đến thuê bao được gọi
qua một loạt các chuyển mạch và trung kế
• Các yêu cầu đặt ra trong vấn đề tìm đường
– Hiệu quả
• Xử lý được tải trên mạng vào giờ cao điểm
• Giảm thiểu số lượng thiết bị trong mạng (node và trunk)
– Khả năng co giãn
• Có những trường hợp lưu thông trên mạng vượt quá tải đã thiết kế
• Mạng phải đảm bảo khả năng hoạt động ở một mức độ nào đó
trong những trường hợp như vậy
2008
dce
©2008, Dr. Dinh Duc Anh Vu
3
Data Communication and Computer Networks
Tìm đường phân cấp
• Static Hierachical Routing
• Các chuyển mạch được kết nối theo cấu trúc phân
cấp (thông thường theo cấu trúc cây)
– Đường đi được hình thành từ node lá đi lên
• Tăng tính co giãn
– Các trung kế (trunk) được kết nối thêm vào cắt ngang cấu
trúc cây
– Cung cấp các đường đi thay thế
• Tĩnh
– Không thích nghi theo các điều kiện thay đổi trên mạng
– Mạng phải được thiết kế để chịu được tải nặng oversize
– Cấu trúc tĩnh đáp ứng kém với lỗi
2008
dce
©2008, Dr. Dinh Duc Anh Vu
4
Data Communication and Computer Networks
Local (End)
office
Regional
center
Sectional
center
Primary
center
Toll
center
tandem
switch
Telephone
Toll connecting
FINAL
FINAL
FINAL
FINAL
HU (high-usage trunks)
Alternate
Hierarchical
Routing
Tìm đường phân cấp
2008
dce
©2008, Dr. Dinh Duc Anh Vu
5
Data Communication and Computer Networks
Tìm đường động
• Tìm đường động (Dynamic Routing)
– Cho phép thay đổi trong việc tìm đường tùy theo lưu thông trong mạng
– Dùng cấu trúc ngang cấp cho các node trong mạng
– Đường đi thiết lập giữa hai thuê bao thay đổi tùy theo khả năng tải và
băng thông của đường truyền tại thời