Download miễn phí Bài giảng Tìm đường trong mạng chuyển mạch
Mỗi node trongmạngtựcậpnhậtbảngtìmđườngcủamình
dựavàocácthôngtin vềmạngmànode đóhọchỏi được,
khôngtraođổi thôngtin routing với cácnode khác
• Gởi cácgóitrêncácliên kếtracóhàngđợingắnnhấ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êmcácđộthiên vị (bias) chocácđường ra
• Mộttrongnhữngphươngphápđơngiảnnhấtcủatìmđường
động, phùhợpvớicácmạngcókíchthướcnhỏvàhoạtđộng
tươngđối ổnđịnh
• Ítdùng(khôngdùngthôngtin cósẵn)
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
BKTP.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 2Data 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 3Data 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 4Data 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
Alternate
ierarchical
Routing
Tìm đường phân cấp
2008
dce
©2008, Dr. Dinh Duc Anh Vu 5Data 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 đ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
2008
dce
©2008, Dr. Dinh Duc Anh Vu 6Data Communication and Computer Networks
Alternate routing
•
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
2008
dce
©2008, Dr. Dinh Duc Anh Vu 7Data Communication and Computer Networks
Adaptive routing
•
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
2008
dce
©2008, Dr. Dinh Duc Anh Vu 8Data Communication and Computer Networks
Tìm
đường trong mạng chuyển mạch gói
•
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 hay 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)
2008
dce
©2008, Dr. Dinh Duc Anh Vu 9Data Communication and Computer Networks
Tiêu chuẩn đo tính hiệu quả
•
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)
2008
dce
©2008, Dr. Dinh Duc Anh Vu 10Data Communication and Computer Networks
Chi phí
các
đường
đi
2008
dce
©2008, Dr. Dinh Duc Anh Vu 11Data Communication and Computer Networks
Thời điểm và nơi quyết định việc tìm đường
•
Thời
điểm
quyết
định
–
Trên
cơ
sở
mạch
ảo hay 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ọ
2008
dce
©2008, Dr. Dinh Duc Anh Vu 12Data Communication and Computer Networks
Nguồn thông tin mạng và
thời điểm cập
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
2008
dce
©2008, Dr. Dinh Duc Anh Vu 13Data Co...