ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ĐỊNH TUYẾN PHÂN TÁN TỰ ỔN ĐỊNH DỰA TRÊN CỘNG TÁC GIỮA CÁC ĐIỂM ĐÍCH LUẬN VĂN CAO HỌC HƯỚNG DẪN: TS. NGUYỄN ĐẠI THỌ HỌC VIÊN: LÊ ĐÌNH THANH HÀ NỘI, 2007 2 MỤC LỤC LỜI CAM ĐOAN 1 MỤC LỤC 2 DANH SÁCH CÁC HÌNH VẼ 4 MỞ ĐẦU 6 CHƢƠNG 1. HỆ PHÂN TÁN 8 1.1. Khái niệm hệ phân tán 8 1.2. Vai trò của hệ phân tán 8 1.3. Đặc trƣng của các hệ phân tán 9 1.4. Mô hình hóa các hệ phân tán 9 1.4.1. Mô hình chuyển thông báo 10 1.4.2. Mô hình với bộ nhớ dùng chung 10 1.4.3. Mô hình xen kẽ 10 1.4.4. Thực hiện và những tính chất của thực hiện 10 1.5. Đánh giá độ phức tạp 12 CHƢƠNG 2. TỰ ỔN ĐỊNH 14 2.1. Tính chất tự ổn định 14 2.2. Vai trò của tự ổn định 14 2.3. Đánh giá độ phức tạp 15 2.4. Ví dụ 1: Loại trừ lẫn nhau 16 2.5. Ví dụ 2: Xây dựng cây khung 21 CHƢƠNG 3. ĐỊNH TUYẾN 26 3.1. Bài toán định tuyến tổng quát 26 3.2. Một số bài toán định tuyến cụ thể 26 3.2.1. Định tuyến với đường đi ngắn nhất 26 3.2.2. Định tuyến với số chặng ít nhất 27 3.2.3. Định tuyến với băng thông cực đại 27 3.3. Phân loại các giải thuật định tuyến 27 3.3.1. Định tuyến theo véctơ khoảng cánh 28 3.3.2. Định tuyến phân tán có/không có sự cộng tác giữa các điểm đích 30 3.3.3. Định tuyến theo trạng thái liên kết 30 3 3.3.4. So sánh định tuyến theo véctơ khoảng cách và định tuyến theo trạng thái liên kết 32 3.4. Một số giải thuật định tuyến phân tán 33 3.4.1. Giải thuật Netchange 34 3.4.2. Giải thuật Humblet 42 CHƢƠNG 4. ĐỊNH TUYẾN PHÂN TÁN TỰ ỔN ĐỊNH CỦA SHLOMI DOLEV 50 4.1. Mô tả chung 50 4.2. Giải thuật đa cây BFS 50 4.3. Giải thuật đếm 55 CHƢƠNG 5. GIẢI THUẬT ĐỀ XUẤT 57 5.1. Giới thiệu chung 57 5.2. Mạng và những giả thiết cơ sở 57 5.3. Cấu trúc dữ liệu, nhiệm vụ của giải thuật 57 5.4. Giải thuật 59 5.5. Ví dụ một thực hiện 62 5.6. Tính đúng đắn 64 5.7. Đánh giá giải thuật 70 KẾT LUẬN 72 TÀI LIỆU THAM KHẢO 73 4 DANH SÁCH CÁC HÌNH VẼ - Hình 2.1. Giải thuật loại trừ lẫn nhau của Dijstra. (16) - Hình 2.2.a. Cấu hình xuất phát C 0 = (2, 3, 4, 1, 1). (18) - Hình 2.2.b. Cấu hình đạt được sau bước tính tại P 3 , C 1 = (2, 3, 4, 4, 1). (18) - Hình 2.2.c. Cấu hình đạt được sau bước tính tại P 1 , C 2 = (2, 2, 4, 4, 1). (19) - Hình 2.2.d. Cấu hình đạt được sau bước tính tại P 4 , C 3 = (2, 2, 4, 4, 4). (19) - Hình 2.2.e. Cấu hình đạt được sau bước tính tại P 2 , C 4 = (2, 2, 2, 4, 4). (20) - Hình 2.2.f. Cấu hình đạt được sau bước tính tại P 3 , C 5 = (2, 2, 2, 2, 4). (20) - Hình 2.2.g. Cấu hình đạt được sau bước tính tại P 4 , C 6 = (2, 2, 2, 2, 2) (an toàn). (21) - Hình 2.3. Giải thuật cây bao trùm. (22) - Hình 3.1. Định tuyến theo véctơ khoảng cách. (29) - Hình 3.2. Mạng có 3 nút (29) - Hình 3.3. Định tuyến theo trạng thái liên kết. (30) - Hình 3.4. Giải thuật Netchange. (37) - Hình 3.5. Các bất biến P(u, w, v) và L(u, v). (37) - Hình 3.6. Giải thuật của Humblet, mã cho nút I. (45) - Hình 3.7.a. Tôpô mạng. (45) - Hình 3.7.b. Các cây định tuyến cho từng nút. (46) - Hình 3.7.c. Xây dựng cây định tuyến ở nút B. (46) - Hình 3.7.d. Tạo lại cây định tuyến sau tôpô thay đổi. (47) - Hình 4. Giải thuật đa cây BFS của Shlomi Dolev. (52) - Hình 5.1. Giải thuật định tuyến tự ổn định có sự cộng tác giữa các điểm đích và không tạo vòng lặp định tuyến vĩnh viễn, mã cho nút P. (60) 5 - Hình 5.2.a. Tôpô mạng. (62) - Hình 5.2.b. Trạng thái ban đầu của mỗi nút (giả sử trạng thái sau lỗi). (62) - Hình 5.2.c. Trạng thái các nút sau vòng 1. (63) - Hình 5.2.d. Trạng thái các nút sau vòng 2. (63) - Hình 5.2.e. Trạng thái các nút sau vòng 3 (ổn định). (64) 6 MỞ ĐẦU Định tuyến là hoạt động chủ yếu của bất kỳ mạng máy tính nào. Vấn đề định tuyến đã được nghiên cứu rất nhiều. Nhiều cấu trúc dữ liệu cùng giải thuật đã được đề xuất cho vấn đề định tuyến. Tuy nhiên, một thách thức tiếp tục diễn ra trong thập kỷ tới là xây dựng các hệ thống định tuyến thật sự sẵn sàng và đáng tin cậy. Các giải thuật định tuyến truyền thống có thể thích ứng với những thay đổi trong tôpô mạng, cũng như các thay đổi của tình trạng mạng. Tuy nhiên, chúng không bỏ qua được các lỗi treo. Một khi lỗi treo xuất hiện, nó phá vỡ hoạt động của hệ thống. Hậu quả của lỗi, như vậy, có thể rất thê thảm. Ngoài ra, muốn hệ thống hoạt động tốt, nó phải được khởi động một cách đúng đắn. Trong nhiều mạng, việc khởi động mạng rất khó thực hiện. Do vậy, chúng ta rất mong muốn có các hệ thống (giải thuật) định tuyến tự ổn định, tức là hệ thống có thể hoạt động đúng đắn bất kể xuất phát từ trạng thái ban đầu nào và đã gặp lỗi gì. Tự ổn định được giới thiệu đầu tiên bởi Dijkstra [4], đã được nghiên cứu nhiều nơi trên thế giới, nhưng còn tương đối mới mẻ ở Việt Nam. Ngoài tính không tự ổn định, các giải thuật định tuyến thường gặp phải vấn đề về vòng lặp định tuyến [9, 13]. Vòng lặp định tuyến xuất hiện không những làm cho giải thuật không kết thúc mà còn làm cho một số kết quả đường định tuyến luôn luôn sai. Khắc phục vòng lặp định tuyến cũng là yêu cầu tiếp tục đặt ra cho thiết kế các hệ thống định tuyến. Đa số các giải thuật định tuyến phân tán thuộc nhóm độc lập điểm đích [7, 8, 9, 13], nghĩa là việc tính đường định tuyến đến nút này hoàn toàn độc lập với việc tính đường định tuyến đến các nút khác. Nếu có sự cộng tác giữa các điểm đích, tức tính đường định tuyến đến nút này dựa trên đường định tuyến đến các nút khác, thời gian tính toán có thể được rút ngắn, đồng thời có thể khắc phục được vấn đề về vòng lặp định tuyến. Những quan sát nêu trên là lý do tôi chọn đề tài này. Mặc dù vậy, mục đích và công việc của luận văn này không chỉ là nghiên cứu đưa ra một giải thuật định tuyến phân tán tự ổn định, có sự cộng tác giữa các điểm đích và không có vòng lặp định tuyến mà còn thông qua việc làm cụ thể này để trình bày, giới thiệu các nội dung của tự ổn định. 7 Luận văn bắt đầu với Chương 1 bằng việc giới thiệu hệ phân tán, các mô hình hệ phân tán, vai trò, đặc trưng của các hệ phân tán, các khái niệm cơ bản về cấu hình, thực hiện và phương pháp đánh giá độ phức tạp của giải thuật phân tán [2, 5, 6]. Tiếp theo, Chương 2 hệ thống hóa và giới thiệu các nội dung của tự ổn định. Sau phần trình bày khái niệm, mô hình hóa, vai trò tự ổn định, phương pháp đánh giá giải thuật tự ổn định là các phần trình bày ví dụ về giải thuật tự ổn định. Hai giải thuật phân tán tự ổn định được chọn và giới thiệu trong chương này là Giải thuật loại trừ lẫn nhau của Dijstra [4] và Giải thuật xây dựng cây khung của Shlomi Dolev [13]. Chương 3 trình bày những nội dung quen thuộc của định tuyến, nhấn mạnh các tính chất không có vòng lặp định tuyến, có cộng tác giữa các điểm đích làm mục tiêu cho xây dựng giải thuật định tuyến được đề xuất trong Chương 5. Chương kết thúc với hai ví dụ về giải thuật định tuyến phân tán không tự ổn định, một tạo vòng lặp định tuyến (Netchange [9]) và một không tạo vòng lặp định tuyến vĩnh viễn (Humblet [11]). Chương 4 được giành riêng để trình bày giải thuật định tuyến phân tán tự ổn định của Shlomi Dolev [14]. Các giải thuật tự ổn định đa cây BFS và giải thuật đếm được kết hợp để tạo nên một giải thuật định tuyến phân tán tự ổn định. Mặc dù giải thuật của Shlomi Dolev thuộc nhóm độc lập điểm đích, khi thực hiện giải thuật có tạo vòng lặp định tuyến nhưng giải thuật đã cho chúng ta một mẫu điển hình về xây dựng giải thuật định tuyến phân tán tự ổn định. Chương cuối cùng, Chương 5, là phần trình bày giải thuật được đề xuất. Có thể xem giải thuật được đề xuất là sự kết hợp và nâng cấp hai giải thuật định tuyến của Humblet (được trình bày trong Chương 3) và của Shlomi Dolev (được trình bày trong Chương 4). Giải thuật hội tụ ba tính chất tốt: tự ổn định, không tạo vòng lặp định tuyến vĩnh viễn, và có sự cộng tác giữa các điểm đích. Tính đúng và độ phức tạp của giải thuật được phát biểu và chứng minh trong phần cuối chương. Chắc chắn, luận văn còn có những thiếu sót trong nội dung cũng như trong trình bày. Với mong muốn được phát triển hơn nữa trong lĩnh vực đang nghiên cứu, tác giả của luận văn rất mong nhận được sự đóng góp ý kiến của các thầy cô giáo và của các anh/chị học viên. 8 CHƯƠNG 1. HỆ PHÂN TÁN 1.1. Khái niệm hệ phân tán Hệ phân tán là tập hợp các thiết bị tính riêng rẽ có thể giao tiếp với nhau. Đây là một khái niệm hết sức tổng quát, bao trùm một phạm vị rộng các hệ thống máy tính ngày nay, từ các bộ chíp VLSI đến các bộ đa xử lý, các mạng cục bộ, và Internet. Nếu như hệ song song phối hợp nhiều bộ xử lý nhằm giải quyết một vấn đề cho trước một cách nhanh nhất thì hệ phân tán bao gồm một tập các bộ xử lý có chương trình làm việc riêng bán độc lập, vì những lý do gì đó, ví dụ chia sẻ tài nguyên, tăng tính sẵn sàng, khứ lỗi, các bộ xử lý cần phối hợp hành động với nhau. Ta có thể thấy các hệ phân tán ở khắp mọi nơi. Điển hình, các hệ phân tán được sử dụng để chia sẻ tài nguyên và chia sẻ dữ liệu. Các máy tính kết nối mạng với nhau có thể dùng chung máy in, máy quét, chia sẻ các tệp tài liệu, chương trình… Tính toán ngang hàng là một kiểu thực hiện của hệ phân tán ngày càng trở nên phổ biến cho việc cung cấp các thiết bị và dịch vụ tính toán. Các hệ phân tán nhiều tham vọng hơn cho hiệu năng hoạt động cao bằng cách kết hợp giải các bài toán con một cách song song, đồng thời tăng tính sẵn sàng của hệ thống trong trường hợp một số thiết bị gặp lỗi. 1.2. Vai trò của hệ phân tán Hệ phân tán ngày càng trở nên phổ biến vì những vai trò sử dụng quan trọng của chúng. Trước hết, phải kể đến vai trò trao đổi thông tin. Các hệ phân tán cho khả năng chia sẻ thông tin rộng rãi. Thông tin từ hệ thống máy tính của ngân hàng đặt tại trụ sở nước này có thể được sử dụng bởi hệ thống máy tính của ngân hàng đặt tại trụ sở nước khác. Hệ phân tán cũng cho khả năng chia sẻ thông tin giữa các thiết bị hỗn tạp. Một máy tính có thể "nói chuyện" với các máy tính khác loại, các điện thoại cố định, di động, các PDA, … Thứ hai, các hệ phân tán cho khả năng chia sẻ tài nguyên cả phần cứng lẫn phần mềm. Các máy tính kết nối mạng có thể dùng chung máy in, có thể chia sẻ các tệp dữ liệu, các tệp chương trình. Thứ ba, bằng việc sao lặp, nhân bản, các hệ phân tán cho độ tin cậy cao. Nếu toàn bộ dữ liệu của một chi nhánh ngân hàng lưu trong máy tính đột nhiên biến mất, người ta có thể khôi phục lại bằng cách sao phần nhân bản đã được lưu tại một nơi khác trên hệ thống máy tính của ngân hàng. Thứ tư, thông qua song song hóa, các thực thể trong hệ phân tán có thể chia sẻ công việc, thực hiện đồng thời công việc chung, do vậy làm tăng hiệu suất hoạt động của hệ thống. Thứ năm, hệ phân tán làm đơn 9 giản việc thiết kế các hệ thống phức tạp. Người ta thường phân một hệ thống phức tạp thành các hệ thống con chuyên dụng và hợp tác với nhau. Làm như vậy, không những việc thiết kế đơn giản mà việc thực hiện cũng đơn giản. 1.3. Đặc trưng của các hệ phân tán Ba đặc trưng, và cũng là những khó khăn điển hình khi thiết kế, của hệ phân tán là: không đồng bộ, thiếu thông tin toàn cục, và không có cơ chế phát hiện sự cố chính xác. Một hệ phân tán không có đồng hồ chung. Ta cũng không thể đồng bộ hóa đồng hồ của các bộ xử lý khác nhau vì không biết chắc độ trễ truyền thông. Để đạt được tính đồng bộ, ta không thể dùng đồng hồ vật lý mà phải vận dụng các khái niệm và giải thuật nhân quả. Tương tự, một hệ phân tán không có bộ nhớ toàn cục chung. Các bộ xử lý không thể biết được trạng thái toàn cục của hệ thống. "Hiểu biết" của mỗi bộ xử lý chỉ có tính cục bộ. Do vậy, người thiết kế hệ phân tán, cụ thể là người xây dựng giải thuật phân tán phải xây dựng cơ chế đánh giá các tính toàn cục. Ngoài ra, chúng ta không có cơ chế phát hiện sự cố chính xác trong hệ phân tán vì không thể phân biệt được bộ xử lý chậm hay bị sự cố. Khi một bộ xử lý gặp sự cố, các bộ xử lý còn lại vẫn phải tiếp tục làm việc để đạt được kết quả như mong muốn. Những đặc trưng này thực sự là những khó khăn khi thiết kế các hệ phân tán. 1.4. Mô hình hóa các hệ phân tán Trong một hệ phân tán, mỗi thực thể (máy tính, bộ xử lý, tiến trình) chạy một chương trình riêng bao gồm tập các lệnh. Khi thực hiện lệnh, thực thể thay đổi trạng thái cục bộ của nó. Ta có thể mô hình hóa sự thay đổi này bằng cách xem mỗi thực thể là một máy trạng thái. Một hệ phân tán được mô hình hóa bằng tập n máy trạng thái. Ký hiệu máy thứ i là P i . Truyền thông giữa các thực thể có thể thực hiện bằng cách chuyển thông báo hay sử dụng bộ nhớ dùng chung. Truyền thông bằng cách ghi vào và đọc ra từ bộ nhớ dùng chung thường hạn chế hệ thống với các thực thể gần nhau về mặt địa lý, ví như hệ thống đa bộ xử lý hay các máy tính đa nhiệm. Truyền thông theo cách chuyển thông báo không có giới hạn như vậy, có thể thực hiện trong cả hệ thống mà các thực thể rất xa nhau về mặt địa lý như các mạng máy tính. Tùy theo phương pháp truyền thông được sử dụng, ta có mô hình chuyển thông báo hay mô hình với bộ nhớ dùng chung. 10 1.4.1. Mô hình chuyển thông báo Trong mô hình chuyển thông báo, các láng giềng trao đổi thông tin cho nhau bằng cách gửi và nhận thông báo. Liên kết giữa các thực thể có thể đơn hoặc lưỡng hướng. Liên kết đơn hướng từ thực thể P i đến thực thể P j được sử dụng để chuyển thông báo từ P i đến P j . Ta có thể trừu tượng hóa liên kết đơn hướng trên bằng hàng đợi FIFO q i, j chứa tất cả các thông báo được P i gửi cho P j nhưng P j chưa nhận được. Mỗi khi P i gửi cho P j một thông báo m, m được đưa vào hàng đợi q i,j . P j có thể nhận m khi nó trên đỉnh hàng đợi q i,j . Liên kết lưỡng hướng giữa P i và P j có thể được mô hình hóa bằng hai hàng đợi: q i,j cho hướng từ P i đến P j và q j,i cho hướng từ P j đến P i . Trạng thái của hệ thống phân tán chuyển thông báo tại một thời điểm cụ thể được xác định bởi trạng thái của các bộ xử lý và nội dung của các hàng đợi chứa thông báo tại thời điểm đó. Cấu hình hệ thống (hay cấu hình) được dùng để chỉ trạng thái này. Một cấu hình được ký hiệu c = (s 1 , s 2 , …, s n , q 1,2 q 1,3 , …, q i,j , …., q n, n-1 ), trong đó s i , 1 ≤ i ≤ n , là trạng thái của P i và q i, j , i  j, là hàng đợi chứa thông báo P i gửi cho P j nhưng P j chưa nhận được. 1.4.2. Mô hình với bộ nhớ dùng chung Trong mô hình với bộ nhớ dùng chung, các bộ xử lý trao đổi thông tin cho nhau bằng cách sử dụng chung các ô nhớ. Các bộ xử lý có thể ghi vào một tập các ô nhớ và đọc ra từ một tập các ô nhớ khác. Cấu hình hệ thống bao gồm trạng thái của các bộ xử lý và nội dung của các ô nhớ dùng chung. Một cấu hình của hệ thống gồm n bộ xử lý và m ô nhớ dùng chung được ký hiệu c = (s 1 , s 2 , …, s n ,, r 1 , r 2 , …, r m ), trong đó s i , 1 ≤ i ≤ n, là trạng thái của P i , r j , 1 ≤ j ≤ m, là nội dung của ô nhớ dùng chung thứ j. 1.4.3. Mô hình xen kẽ Mô hình xen kẽ được sử dụng để lý giải hành vi của hệ thống phân tán. Trong mô hình này, tại mỗi thời điểm có duy nhất một bộ xử lý thực hiện một bước tính (còn gọi là bước nguyên tử). Mỗi bước nguyên tử bao gồm một số phép tính bên trong bộ xử lý, hay còn gọi là sự kiện tính, và một phép giao, hay còn gọi là sự kiện giao - một phép gửi hoặc nhận trong hệ thống chuyển thông báo hay một phép ghi hoặc đọc trong hệ thống sử dụng bộ nhớ dùng chung. 1.4.4. Thực hiện và những tính chất của thực hiện Trong một hệ thống phân tán, các bộ xử lý có thể thực hiện các bước tính một cách đồng thời; tuy nhiên, chúng ta giả thiết bước tính này không ảnh hưởng đến bước tính [...]... nguồn đến đích Tuy nhiên cách này rất đắt vì kích thước các thông báo lớn Một cách khắc phục hay được sử dụng nhất là mỗi nút lưu các con của mình trên đường định tuyến, không thay đổi cha cho đến khi nhận được hồi báo của tất cả các nút con [7, 8] 3.3.2 Định tuyến phân tán có/không có sự cộng tác giữa các điểm đích Một tính chất có thể dùng để phân loại các giải thuật định tuyến theo véctơ khoảng cách,... cách, hay định tuyến phân tán, là trong thực hiện của giải thuật có sự cộng tác giữa các điểm đích hay không Nếu như quá trình tính đường định tuyến đến mỗi nút được thực hiện một cách độc lập, riêng rẽ thì giải thuật thuộc nhóm độc lập điểm đích (destinationindependent), ngược lại giải thuật thuộc nhóm cộng tác giữa các điểm đích (collaboration between destinations) Như sẽ được trình bày trong các phần... thuật định tuyến phân tán Trong phần này, chúng ta sẽ xem xét một số giải thuật định tuyến dựa trên véctơ khoảng cách Cụ thể, ta sẽ xét giải thuật Netchange [9] và giải thuật của Humblet [11] 34 Giải thuật thứ nhất độc lập điểm đích, có tạo vòng lặp định tuyến Giải thuật thứ hai có sự cộng tác giữa các điểm đích và không tạo vòng lặp định tuyến vĩnh viễn 3.4.1 Giải thuật Netchange Cho một mạng với các. .. đầu tiên trên đường định tuyến đến bộ xử lý đích và cập nhật khoảng cách tương ứng Trong cách thực hiện này, quá trình tính đường định 28 tuyến được thực hiện phân tán Chính vì vậy, định tuyến theo véctơ khoảng cách có một tên gọi khác là định tuyến phân tán (distributed routing) Trong định tuyến theo trạng thái liên kết, mỗi bộ xử lý phát tỏa trạng thái của các liên kết liền kề nó tới tất cả các bộ... K 3.3 Phân loại các giải thuật định tuyến Hầu hết các giải thuật định tuyến được áp dụng hiện nay thuộc một trong hai loại: định tuyến theo trạng thái liên kết (link-state routing) và định tuyến theo véctơ khoảng cách (distance-vector routing) Trong định tuyến theo véctơ khoảng cách, mỗi bộ xử lý gửi tới mỗi láng giềng của nó một bản sao khoảng cách từ nó đến bộ xử lý đích Dựa trên các khoảng cách nhận... có một tên gọi khác là định tuyến phát tỏa (broadcast routing) Chúng ta sẽ lần lượt xét hai phương pháp định tuyến kể trên nhưng tập trung chủ yếu vào phương pháp định tuyến thứ nhất – định tuyến theo véctơ khoảng cách hay định tuyến phân tán 3.3.1 Định tuyến theo véctơ khoảng cánh Định tuyến theo véctơ khoảng cách [12] được biết đến trước đây với những cái tên như Định tuyến ARPANET cũ” gắn liền với... báo là tổng số thông báo (hoặc tổng kích thước các thông báo) được gửi/nhận khi thực hiện giải thuật 14 CHƯƠNG 2 TỰ ỔN ĐỊNH 2.1 Tính chất tự ổn định Khái niệm tự ổn định được Dijkstra đưa ra đầu tiên năm 1973 trong bài báo nổi tiếng “Self-stabilizing systems in spite of distributed control” [4] Tự ổn định, sau đó, được nghiên cứu như một chuyên ngành thuộc tính toán phân tán Một hệ tự ổn định có thể... hiện của hệ thống phân tán đồng bộ đơn giản được ký hiệu là E = (c1, c2, …) và hoàn toàn được xác định từ cấu hình ban đầu, c1 1.5 Đánh giá độ phức tạp Rõ ràng, để xây dựng các hệ phân tán, chúng ta cần xây dựng các giải thuật phân tán Thực hiện của giải thuật phân tán diễn ra phân tán trên nhiều bộ xử lý Cũng như các giải thuật khác, giải thuật phân tán được đánh giá độ phức tạp trên hai khía cạnh:... Cũng như các giải thuật phân tán khác, giải thuật tự ổn định được đánh giá độ phức tạp thời gian dựa trên số vòng không đồng bộ Số vòng trong thực hiện của một giải thuật tự ổn định được dùng để đánh giá độ phức tạp thời gian của giải thuật Giải thuật tự ổn định không bao giờ kết thúc, và các bộ xử lý phải tiếp tục liên lạc với các láng giềng của chúng Trong mô hình với bộ nhớ dùng chung, các bộ xử... hai tác giả là Bellman và Ford là những người đã đề xuất một giải thuật mà phương pháp định tuyến theo véctơ khoảng cách dựa rất nhiều vào nó Theo phương pháp định tuyến này, mỗi bộ xử lý lưu giữ thông tin về khoảng cách từ nó đến mỗi bộ xử lý đích trong một véctơ được gọi là véctơ khoảng cách Các khoảng cách được tính toán sử dụng thông tin trong các véctơ khoảng cách của láng giềng Thủ tục định tuyến . giải thuật định tuyến phân tán tự ổn định của Shlomi Dolev [14]. Các giải thuật tự ổn định đa cây BFS và giải thuật đếm được kết hợp để tạo nên một giải thuật định tuyến phân tán tự ổn định. Mặc. Định tuyến với băng thông cực đại 27 3.3. Phân loại các giải thuật định tuyến 27 3.3.1. Định tuyến theo véctơ khoảng cánh 28 3.3.2. Định tuyến phân tán có/không có sự cộng tác giữa các điểm đích. độc lập với việc tính đường định tuyến đến các nút khác. Nếu có sự cộng tác giữa các điểm đích, tức tính đường định tuyến đến nút này dựa trên đường định tuyến đến các nút khác, thời gian tính