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)
37 trang |
Chia sẻ: maiphuongdc | Lượt xem: 1656 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Bài giảng Tìm đường trong mạng chuyển mạch, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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 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 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)
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 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ọ
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 Communication and Computer Networks
Chiến thuật tìm đường
•
Chiến thuật
(Routing Strategies)
–
Fixed routing
–
Flooding routing
–
Random routing
–
Adaptive routing
2008
dce
©2008, Dr. Dinh Duc Anh Vu 14Data Communication and Computer Networks
Fixed Routing
•
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
2008
dce
©2008, Dr. Dinh Duc Anh Vu 15Data Communication and Computer Networks
Flooding Routing
•
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
2008
dce
©2008, Dr. Dinh Duc Anh Vu 16Data Communication and Computer Networks
Flooding Routing
•
Đặ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
2008
dce
©2008, Dr. Dinh Duc Anh Vu 17Data Communication and Computer Networks
Random Routing
•
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
•
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
i
i
i
i R
RP
2008
dce
©2008, Dr. Dinh Duc Anh Vu 18Data Communication and Computer Networks
Adaptive Routing
•
Đượ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
2008
dce
©2008, Dr. Dinh Duc Anh Vu 19Data Communication and Computer Networks
Adaptive Routing
•
Ư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)
2008
dce
©2008, Dr. Dinh Duc Anh Vu 20Data Communication and Computer Networks
Isolated Adaptive Routing
•
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)
2008
dce
©2008, Dr. Dinh Duc Anh Vu 21Data Communication and Computer Networks
Isolated Adaptive Routing
•
Ví
dụ
•
Đường ra được chọn là đường ra có
Q+Bi
nhỏ
nhất
2008
dce
©2008, Dr. Dinh Duc Anh Vu 22Data Communication and Computer Networks
Adaptive Routing
•
Distributed Adaptive Routing
–
Trong
phương
pháp
này, thông
tin về
tình
trạng
hoạt
động
hiện
hành
của mạng
sẽ được
định
kỳ
trao
đổi, cập nhật giữa
các
node trong
toàn
mạng. Sau
đó
thông
tin này
sẽ được
phân
bố
về
lại
các
node trong
mạng
hay một số
node trong
mạng
làm
nhiệm vụ
tìm
đường
để
các
node này
cập nhật lại bảng
routing
–
Phương
pháp
này
đáp
ứng
được với những
thay
đổi trạng
thái
của
mạng, nhưng
đồng
thời cũng
làm
tăng
lưu lượng
thông
tin trong
mạng
•
Centralized Adaptive Routing
–
Trong
phương
pháp
này, thông
tin về
tình
trạng
hoạt
động
hiện
hành
của mạng
sẽ được
định
kỳ
trao
đổi, cập nhật giữa
các
node trong
toàn
mạng. Sau
đó
thông
tin này
sẽ được tập trung về
một máy chủ
trong
mạng
làm
nhiệm vụ
routing
–
Tuy
đáp
ứng
được với những
thay
đổi tức thời trong mạng
nhưng
phương
pháp
này
có
nhược
điểm
là
thông
tin routing trong
toàn
mạng
tập
trung
về
một
máy
nên
khi
máy
này
không
hoạt
động
thì
toàn
mạng
sẽ
không
hoạt
động
được
2008
dce
©2008, Dr. Dinh Duc Anh Vu 23Data Communication and Computer Networks
Giải
thuật tìm đường
ngắn nhất
•
Bài
toán
–
Cho
mạng
các
node được nối bởi
các
liên
kết
2 chiều, mỗi chiều có giá trị
chi
phí
riêng
–
Chi phí
của
đường
đi giữa
2 node trong
mạng
là
tổng
các
giá
trị
chi phí
của
các
liên
kết
đi
qua
–
Xác
định
đường
đi ngắn nhất
(chi phí
thấp nhất) giữa
2 node
•
Tiêu
chuẩn
đường
ngắn nhất
–
Số
chặng
đường
đi
•
Giá
trị
mỗi
liên
kết là 1
–
Giá
trị
liên
kết
•
Tỉ
lệ
nghịch
tốc
độ
liên
kết
•
Tỉ
lệ
thuận tải
trên
liên
kết
•
Tổ
hợp các đại lượng
trên
•
Giải thuật
–
Forward-search (Dijkstra)
–
Backward-search (Bellman-Ford)
2008
dce
©2008, Dr. Dinh Duc Anh Vu 24Data Communication and Computer Networks
Giải
thuật
Dijkstra
•
Input
–
Đồ
thị
G(V, E) trong
đó V là tập
đỉnh, E là
tập cạnh
có
trọng
số
không
âm
–
Đỉnh
nguồn S: S
V
•
Output
–
Đường
đi ngắn nhất từ đỉnh
nguồn S đến tất cả
các
đỉnh
còn
lại
•
Ký
hiệu
–
Di
: đường
đi ngắn nhất từ
node nguồn S đến
node i tại bước chạy
hiện
hành
của giải thuật
–
M: tập các đỉnh
đã xét tại bước chạy hiện
hành
của giải thuật
–
dij
: trọng
số
trên
cạnh
nối từ
node i đến
node j
dij
= 0 nếu
i trùng
j
dij
= Eij
nếu
i khác
j
2008
dce
©2008, Dr. Dinh Duc Anh Vu 25Data Communication and Computer Networks
Giải
thuật
Dijkstra
•
Giải thuật
–
Bước 1: khởi
động
•
M = {S}
•
Di
= dsi
(các cạnh nối trực tiếp với S)
–
Bước 2: cập nhật
đường
đi ngắn nhất
•
Chọn
đỉnh
N
V sao
cho: DN
= min {Di
} i
V\M
•
M = M U {N}
•
Dj
= min {Dj
, DN
+ dNj
}
j
V\M
–
Bước 3: lặp lại bước 2 cho đến khi M=V
–
Kết quả
Di
sẽ
là
đường
đi ngắn nhất từ
node nguồn S đến
node i
2008
dce
©2008, Dr. Dinh Duc Anh Vu 26Data Communication and Computer Networks
Giải
thuật
Dijkstra
Node 2 Node 3 Node 4 Node 5 Node 6Laàn
chaïy
M
D2 Path D3 Path D4 Path D5 Path D6 Path
1 1 2 1 – 2 5 1 – 3 1 1 – 4 --- ---
2 1 , 4 2 1 – 2 4 1 – 4 – 3 1 1 – 4 2 1 – 4 – 5 ---
3 1 , 4 , 2 2 1 – 2 4 1 – 4 – 3 1 1 – 4 2 1 – 4 – 5 ---
4 1 , 4 , 2 , 5 2 1 – 2 3 1 – 4 – 5 – 3 1 1 – 4 2 1 – 4 – 5 4 1 – 4 – 5 – 6
5 1 , 4 , 2 , 5 , 3 2 1 – 2 3 1 – 4 – 5 – 3 1 1 – 4 2 1 – 4 – 5 4 1 – 4 – 5 – 6
6 1 , 4 , 2 , 5 , 3 ,6 2 1 – 2 3 1 – 4 – 5 – 3 1 1 – 4 2 1 – 4 – 5 4 1 – 4 – 5 – 6
2008
dce
©2008, Dr. Dinh Duc Anh Vu 27Data Communication and Computer Networks
Giải
thuật
Dijkstra
2008
dce
©2008, Dr. Dinh Duc Anh Vu 28Data Communication and Computer Networks
Giải
thuật
Bellman-Ford
•
Input
–
Đồ
thị
G(V, E) trong
đó V là tập
đỉnh, E là
tập cạnh
có
trọng
số
–
Đỉnh
nguồn S: S
V
•
Output
–
Đồ
thị
có
chu
trình
âm
không
tồn tại
đường
đi ngắn nhất
–
Đường
đi ngắn nhất từ đỉnh
nguồn S đến tất cả
các
đỉnh
còn
lại
•
Ký
hiệu
–
D(h)i
: đường
đi ngắn nhất từ
node nguồn S đến
node i có
tối
đa h đoạn
(link).
–
dij
: trọng
số
trên
cạnh
nối từ
node i đến
node j
dij
= 0 nếu
i trùng
j
dij
= Eij
nếu
i khác
j
2008
dce
©2008, Dr. Dinh Duc Anh Vu 29Data Communication and Computer Networks
Giải
thuật
Bellman-Ford
•
Giải thuật
–
Bước 1: khởi
động
•
D(1)N
= dSN
, N
V\{S}
(đường
đi ngắn nhất từ
S đến
N có
tối
đa 1 đoạn)
–
Bước 2: cập nhật
đường
đi ngắn nhất
•
D(h+1)N
= min {D(h)j
+ djN
} j
V\{S}
–
Bước 3: lặp lại bước 2 cho đến khi
không
có
đường
đi mới
nào
ngắn
hơn
được tìm thấy thì dừng
–
Kết quả
D(h)N
sẽ
là
đường
đi ngắn
nhất từ
node nguồn S đến
node N
2008
dce
©2008, Dr. Dinh Duc Anh Vu 30Data Communication and Computer Networks
Giải
thuật
Bellman-Ford
Node 2 Node 3 Node 4 Node 5 Node 6Laàn
chaïy D(h)2 Path D(h)3 Path D(h)4 Path D(h)5 Path D(h)6 Path
1 2 1–2 5 1–3 1 1–4 --- ---
2 2 1–2 4 1–4–3 1 1–4 2 1–4–5 10 1–3–6
3 2 1–2 3 1–4–5–3 1 1–4 2 1–4–5 4 1–4–5–6
4 2 1–2 3 1–4–5–3 1 1–4 2 1–4–5 4 1–4–5–6
2008
dce
©2008, Dr. Dinh Duc Anh Vu 31Data Communication and Computer Networks
Giải
thuật
Bellman-Ford
2008
dce
©2008, Dr. Dinh Duc Anh Vu 32Data Communication and Computer Networks
Bài
tập
•
Tìm
đường
ngắn nhất từ
node 1
–
Theo giải thuật Dijkstra
–
Theo giải thuật
Bellman-Ford
1 2
3 4
5
6
7
1 3
4
2
1
1
2
3
3
5
4
3
2008
dce
©2008, Dr. Dinh Duc Anh Vu 33Data Communication and Computer Networks
Bài
tập
•
Tìm
đường
ngắn nhất từ
node A
–
Theo giải thuật Dijkstra
–
Theo giải thuật
Bellman-Ford
E
G
H
D
K J
F
C
BA1 1
1
1
1
2
1
1
2
3
2
4
5
2
2008
dce
©2008, Dr. Dinh Duc Anh Vu 34Data Communication and Computer Networks
Dijkstra
vs. Bellman-Ford
•
Bellman-Ford
–
Việc
tính
toán
cho
node n phải biết
các
thông
tin về
chi phí
liên
kết của
các
node kề
của n
và
chi phí
tổng
cộng
từ
node s đến
các
node kề
của
node n [i.e., Lh
(j)]
–
Mỗi
node cần lưu trữ
tập
các
chi phí
và
các
đường
đi
tương
ứng
đến
các
node khác
–
Có
thể
trao
đổi
thông
tin với
các
node kề
trực tiếp
–
Có
thể
cập nhật
thông
tin về
chi phí
và
đường
đi dựa trên
các
thông
tin trao
đổi với
các
node kề
và
các
thông
tin về
chi phí
liên
kết
•
Dijkstra
–
Mỗi
node cần biết
topology toàn
bộ
mạng
–
Phải biết
chi phí
liên
kết của tất cả
các
liên
kết
trong
mạng
–
Phải trao đổi
thông
tin với tất cả
các
node khác
trong
mạng
2008
dce
©2008, Dr. Dinh Duc Anh Vu 35Data Communication and Computer Networks
Đánh
giá
•
Phụ
thuộc vào thời gian xử
lý
của
các
giải thuật
•
Phụ
thuộc vào lượng
thông
tin yêu
cầu từ
các
node
khác
•
Phụ
thuộc vào việc hiện thực
•
Cùng
hội tụ
về
một lời giải dưới
điều kiện
topology
tĩnh
và
chi phí
không
thay
đổi
•
Nếu
chi phí
liên
kết
thay
đổi, các
giải thuật sẽ
tính
lại
để
theo
kịp sự
thay
đổi
•
Nếu
chi phí
liên
kết
thay
đổi
theo
lưu
thông, lưu
thông
lại
thay
đổi
theo
đường
đi
được chọn
–
Phản hồi
–
Có
thể
rơi vào trạng
thái
không
ổn
định
2008
dce
©2008, Dr. Dinh Duc Anh Vu 36Data Communication and Computer Networks
ARPANET –
Tìm
đường
•
Thế
hệ đầu tiên
–
1969
–
Distributed adaptive
–
Dùng
thời gian trễ ước
tính
làm
tiêu
chuẩn
để
đánh
giá
hiệu quả–
Dùng
giải thuật tìm đường
Bellman-Ford
–
Các
node trao
đổi
thông
tin (các
vector thời gian trễ) với
các
node kề
–
Cập nhật bảng
tìm
đường
dựa
trên
thông
tin đến
–
Không
quan
tâm
đến tốc
độ
đường
truyền, chỉ
quan
tâm
chiều
dài
hàng
đợi tại
các
node
–
Chiều
dài
hàng
đợi
không
phải là cách đo chính xác của
thời gian trễ–
Đáp
ứng
chậm với
nghẽn mạch
2008
dce
©2008, Dr. Dinh Duc Anh Vu 37Data Communication and Computer Networks
ARPANET –
Tìm
đường
•
Thế
hệ
thứ
2
–
1979
–
Dùng
thời gian trễ
làm
tiêu
chuẩn
đánh
giá
hiệu quả
–
Thời gian trễ được
đo trực tiếp
–
Dùng
giải thuật tìm đường
Dijkstra
–
Thích
hợp cho mạng
có
tải
trung
bình
hoặc nhẹ
–
Khi
mạng
tải nặng, có
ít
tương
quan
giữa thời gian trễ đo
được và thời
gian
trễ
gặp phải
•
Thế
hệ
thứ
3
–
1987
–
Việc
tính
toán
chi phí
của liên kết
đã
được thay đổi
–
Thời gian trễ
trung
bình
được
đo
trong
10 giây
cuối
–
Bình
thường
hóa
dựa trên giá trị
hiện tại và kết quả
trước
đó
Các file đính kèm theo tài liệu này:
- sinhvien-chuong8_mod_565.pdf