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
Dat a Com m unica t ion a nd Com puter N e t w or k s
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
Dat a Com m unica t ion a nd Com puter N e t w or k s
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
Dat a Com m unica t ion a nd Com puter N e t w or k s
Local (End)
office
Regional
center
Sectional
center
Primary
center
Tol l
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
Dat a Com m unica t ion a nd Com puter N e t w or k s
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 điểm thiết lập kết nối
– Phức tạp và linh động hơn
• Một số phương pháp tìm đường động
– Dựa vào thống kê biến động trong mạng (tải, băng thông, ...) theo thời
gian, còn gọi là Time-dependent Routing
•Alternate routing
– Dựa vào biến động trong mạng (tải, băng thông, ...) để trao đổi cập
nhật thông tin tìm đường đi giữa các node trong mạng, từ đó tìm ra
được đường đi tối ưu và cập nhật vào bảng routing ở các node
chuyển mạch trong mạng, còn gọi là State-dependent Routing
•Adaptive routing
– Kết hợp cả hai phương pháp này