Xem mẫu
- dce
2008
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
BK
TP.HCM
Các giải thuật tìm đường đi ngắn nhất
- dce
Tìm đường trong mạng chuyển mạch mạch
2008
• 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
Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 2
- dce
Tìm đường phân cấp
2008
• 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
Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 3
- dce
Tìm đường phân cấp
2008
FINAL
Regional
center
FINAL
HU (high-usage trunks)
Sectional
center
FINAL
Primary
center
FINAL
Toll
center
Alternate
Alternate Toll connecting
Hierarchical
Hierarchical
Local (End)
Routing
tandem Routing
office
switch
Telephone
Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 4
- dce
Tìm đường động
2008
• 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
Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 5
- dce
Alternate routing
2008
• Các đường đi có thể giữa 2
trạm (end office) được liệt
kê trước
• Bộ chuyển mạch nguồn
chọn lựa các đường thích
hợp
• Các đường được liệt kê
theo thứ tự ưu tiên
– Ưu tiên kết nối trực tiếp
– Thứ tự ưu tiên dựa vào thống
kê lưu thông trên mạng
– Fixed alternate routing
• Thay đổi thứ tự ưu tiên của
các đường đi theo từng thời
điểm khác nhau
– Dynamic alternate routing
Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 6
- dce
Adaptive routing
2008
• Cho phép các bộ chuyển mạch phản ứng lại với tình hình lưu
thông trên mạng
• Chi phí lớn hơn cho việc quản trị
– Các bộ chuyển mạch phải trao đổi thông tin để biết tình trạng mạng
• DTM (dynamic traffic management)
– Northern Telecom
– Dùng bộ điều khiển trung tâm để tìm đường dự phòng khi có sự nghẽn
mạng
– Mỗi bộ chuyển mạch A cập nhật các thông tin sau cho bộ điều khiển
trung tâm
• Số trung kế rảnh để đi đến các điểm lân cận A
• Hiệu suất sử dụng CPU của A
• Đo lưu lượng từ A đến B (không thể nối trực tiếp)
– Bộ chuyển mạch trung tâm sẽ cho biết đường đi “tốt” khi các đường
nối trực tiếp không còn khả năng
Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 7
- dce
Tìm đường trong mạng chuyển mạch gói
2008
• Vấn đề phức tạp, quyết định đối với mạng chuyển mạch gói
• Các đặc tính yêu cầu
– Chính xác
– Đơn giản
– Mạnh mẽ
• Khả năng chuyển các gói trong điều kiện lỗi và quá tải
• Không mất gói hoặc không làm đứt virtual circuit
– Ổn định
• Hệ thống có khả năng thay đổi theo điều kiện mạng thường có xu hướng
không ổn định và đáp ứng chậm
• Congestion oscillation
– Công bằng vs. tối ưu
• Một số hệ thống ưu tiên chuyển các gói đến trạm gần hơn
• Tối ưu thông lượng nhưng không công bằng
– Hiệu quả
• Tìm đường đòi hỏi phải tăng cường xử lý và tăng cường lưu thông trên
mạng
• Chi phí cho tìm đường phải ít hơn lợi ích (ví dụ tăng tính mạnh mẽ, công
bằng)
Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 8
- dce
Tiêu chuẩn đo tính hiệu quả
2008
• Là tiêu chuẩn được dùng để chọn đường
– Số chặng đường (hop) là tối thiểu
• Đơn giản
• Tối thiểu việc sử dụng tài nguyên
– Chi phí (cost) tối thiểu
• Mỗi đường link được gán một chi phí
• Chi phí có thể là
– Data rate (tỉ lệ nghịch)
– Delay do các gói xếp hàng (tỉ lệ thuận)
Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 9
- dce
Chi phí các đường đi
2008
Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 10
nguon tai.lieu . vn
