›
›

Kỹ thuật truyền số liệu - Chương 8: Tìm đường trong mạng chuyển mạch

pdf 39 trang vanle 2970
Download
Bạn đang xem 20 trang mẫu của tài liệu "Kỹ thuật truyền số liệu - Chương 8: Tìm đường trong mạng chuyển mạch", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfky_thuat_truyen_so_lieu_chuong_8_tim_duong_trong_mang_chuyen.pdf

Nội dung text: Kỹ thuật truyền số liệu - Chương 8: Tìm đường trong mạng chuyển mạch

  1. 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 BK TP.HCM 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
  2. dce 2008 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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 2
  3. dce 2008 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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 3
  4. dce 2008 Tìm đường phân cấp FINAL Regional center FINAL HU (high-usage trunks) Sectional center FINAL Primary center FINAL Tol l center Alternate Toll connecting Hierarchical Local (End) tandem Routing office switch Telephone Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 4
  5. dce 2008 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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 5
  6. dce 2008 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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 6
  7. dce 2008 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) Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 8
  8. dce 2008 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) Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 9
  9. dce 2008 Chi phí các đường đi Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 10
  10. dce 2008 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ọ Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 11
  11. dce 2008 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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 12
  12. dce 2008 Chiến thuật tìm đường • Chiến thuật (Routing Strategies) – Fixed routing – Flooding routing – Random routing – Adaptive routing Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 13
  13. dce 2008 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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 14
  14. dce 2008 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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 15
  15. dce 2008 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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 16
  16. dce 2008 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 tốn xác suất Ri Pi = ∑ Ri i • 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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 17
  17. dce 2008 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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 18
  18. dce 2008 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) Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 19
  19. dce 2008 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) Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 20
  20. dce 2008 Isolated Adaptive Routing • Ví dụ • Đường ra được chọn là đường ra cĩ Q+Bi nhỏ nhất Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 21
  21. dce 2008 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 tồ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 tồ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 tồn mạng tập trung về một máy nên khi máy này khơng hoạt động thì tồn mạng sẽ khơng hoạt động được Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 22
  22. dce 2008 Giải thuật tìm đường ngắn nhất • Bài tố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) Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 23
  23. dce 2008 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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 24
  24. dce 2008 Giải thuật Dijkstra 5 3 2 3 5 2 1 2 3 6 1 • Giải thuật 1 – Bước 1: khởi động 1 2 • M = {S} 4 5 • 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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 25
  25. dce 2008 Giải thuật Dijkstra 5 3 2 3 5 2 1 2 3 6 1 1 1 2 4 5 Lần M Node 2 Node 3 Node 4 Node 5 Node 6 chạy 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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 26
  26. dce 2008 Giải thuật Dijkstra Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 27
  27. dce 2008 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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 28
  28. dce 2008 Giải thuật Bellman-Ford 5 • Giải thuật 3 2 3 – Bước 1: khởi động 5 • D(1) = d , ∀N ∈ V\{S} 2 N SN 1 2 3 6 (đường đi ngắn nhất từ S đến N cĩ tối 1 1 đa 1 đoạn) 1 2 4 5 – 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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 29
  29. dce 2008 Giải thuật Bellman-Ford 5 3 2 3 5 2 1 2 3 6 1 1 1 2 4 5 Lần Node 2 Node 3 Node 4 Node 5 Node 6 chạ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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 30
  30. dce 2008 Giải thuật Bellman-Ford Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 31
  31. dce 2008 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 4 1 2 3 3 1 2 6 1 2 3 4 5 3 4 3 1 5 7 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 32
  32. 4 dce 4 2008 0 1 2 Correct? 3 3 7 1 2 6 1 2 3 1 3 4 5 3 4 3 1 5 5 7 4 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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 33
  33. dce 2008 Correct? 4 0 4 1 2 3 3 7 1 2 6 1 2 3 1 3 4 5 3 4 3 1 5 5 7 4 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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 34
  34. dce 2008 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 1 1 E A B 2 1 2 5 2 G C 3 1 D F 2 1 1 4 1 H K J Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 35
  35. dce 2008 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 1 1 1 1 E A B 2 1 2 5 3 2 G C 2 3 1 F D 2 1 3 4 1 5 1 4 H K J 4 6 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 36
  36. dce 2008 Dijkstra vs. Bellman-Ford • Bellman-Ford – Việc tính tố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 tồ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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 37
  37. dce 2008 Đá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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 38
  38. dce 2008 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 Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 39
  39. dce 2008 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 tố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 đĩ Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 40