Bài giảng Kỹ thuật truyền dữ liệu - Chương 8 Tìm đường trong mạng chuyển mạch (Phần 1)
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 đó
Bạn đang xem trước 20 trang tài liệu Bài giảng Kỹ thuật truyền dữ liệu - Chương 8 Tìm đường trong mạng chuyển mạch (Phần 1), để 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
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 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ẽ (robustness)
• 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
1
2 3
4 5
61
1
1 2
2
2 3
3
5
5
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 6 Laà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
1
2 3
4 5
61
1
1 2
2
2 3
3
5
5
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
1
2 3
4 5
61
1
1 2
2
2 3
3
5
5
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 6 Laà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
1
2 3
4 5
61
1
1 2
2
2 3
3
5
5
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 Correct?
L M D2 N2 D3 N3 D4 N4 D5 N5 D6 N6 D7 N7
1 1 4 1-2 1 1-3 3 1-4 - - - - - -
2 1, 3 4 1-2 1 1-3 3 1-4 4 1-3-5 - - 5 1-3-7
3 1, 3, 4 4 1-2 1 1-3 3 1-4 4 1-3-5 - - 5 1-3-7
4 1, 3, 4, 2 4 1-2 1 1-3 3 1-4 4 1-3-5 7 1-2-6 5 1-3-7
5 1, 3, 4, 2, 5 4 1-2 1 1-3 3 1-4 4 1-3-5 7 1-2-6 5 1-3-7
6 1, 3, 4, 2, 5, 7 4 1-2 1 1-3 3 1-4 4 1-3-5 7 1-2-6 5 1-3-7
7 1, 3, 4,2,5,7,6 4 1-2 1 1-3 3 1-4 4 1-3-5 7 1-2-6 5 1-3-7
©2008, Dr. Dinh Duc Anh Vu 33Data Communication and Computer Networks
1 2
3 4
5
6
7
1 3
4
2
1
1
2
3
3
5
4
3
4
7
3
5
4
0
1
2008
dce Correct?
©2008, Dr. Dinh Duc Anh Vu 34Data Communication and Computer Networks
h D2 N2 D3 N3 D4 N4 D5 N5 D6 N6 D7 N7
1 4 1-2 1 1-3 3 1-4 - - - - - -
2 4 1-2 1 1-3 3 1-4 4 1-3-5 7 1-2-6 5 1-2-7
3 4 1-2 1 1-3 3 1-4 4 1-3-5 7 1-2-6 5 1-2-7
1 2
3 4
5
6
7
1 3
4
2
1
1
2
3
3
5
4
3
4
7
3
5
4
0
1
2008
dce
©2008, Dr. Dinh Duc Anh Vu 35Data 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 36Data 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
6
2
1
1
3
4
5
3
4
2008
dce
©2008, Dr. Dinh Duc Anh Vu 37Data 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 38Data 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 39Data 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 40Data 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:
- slide_ki_thuat_truyen_so_lieu_chuong_8_phan_1_8063.pdf