Hai hệ thông tự trị sử dụng IGP bên trong và sử dụng EGP để giao tiếp giữa hai exterrior Router R1 và R

g, độ dài đường truyền,tỉ lệ lỗi trên tuyến truyền. .. Tuy nhiên, ngoài giá thành, một số thông số khác cũng phải tính đến khi thiết lập đường truyền: Dung lượng của đường truyền Số lượng các gói đang chờ để đưa vào đường truyền Phân bố tải trên mạng Các yêu cầu bảo mật đối với đường truyền Kiểu truyền tải so với dạng của đường truyền Số lượng các đường nối trung gian giữa trạm truyền và trạm nhận Khả năng ghép nối với trạm trung gian và cả trạm nhận cuối cùng Dù cho thông số mạng có thay đổi theo tiêu chuẩn nào thì vẫn phải tính đến ba điều kiện: + Trễ trung bình gói (Delay) + Khả thông (Throughput) + Khả nối (Connectivity) Như chúng ta đã nói trong phần chức năng,việc chọn tuyến truyền có hai nhiệm vụ cơ bản: thứ nhất là phải chọn tuyến sao cho đạt được hoạt tính cao, có nghĩa là phải chọn được đường dẫn có hiệu quả nhất; thứ hai là phải phổ cập thông tin liên quan đến chọn tuyến bao gồm cả các sự cố của các nút mạng cũng như các đường truyền và tình hình khắc phục giữa chúng, tới tất cả các nút chuyển mạch trong mạng. Tương ứng với hai công việc này đòi hỏi phải có hai loại kỹ thuật thực hiện riêng cho từng loại. Việc thực hiện nhiệm vụ thứ nhất chính là cách tính toán tìm đường dẫn mà ta hay gọi là thuật toán tìm tuyến truyền. Các lý thuyết giải thuật để tìm tuyến truyền thì có rất nhiều và rất đa dạng, nhưng kỹ thuật chuyển mạch gói quan tâm tới hai thể loại chính: chọn tuyến truyền phân nhánh (Bifurcated Routing) và chọn tuyến truyền ngắn nhất (Shortest-Path Routing). Kĩ thuật thứ nhất còn có tên là chọn tuyến nhiều đường dẫn gói (Multipath Routing), được thiết kế sao cho nó có thể tối thiểu hoá trễ trung bình của gói trên phạm vi toàn mạng. Kĩ thuật thứ hai, chọn tuyến ngắn nhất, chủ yếu quan tâm tới trễ người sử dụng và nó chọn ra đường dẫn có giá thành tối thiểu cho một cặp người sử dụng. Việc thực hiện nhiệm vụ cơ bản thứ hai của việc chọn đường do các thuật toán thu nhận và truyền thông tin chọn đường thực hiện. Mỗi giao thức chọn đường có những phương pháp khác nhau để lấy được thông tin chọn đường và truyền thông tin chọn đường. Nếu dựa vào việc các thông tin chọn đường có thường xuyên được cập nhật hay không thì ta có thể phân thành hai loại: Thuật toán chọn đường thích nghi (Adaptive) và thuật toán chọn đường không thích nghi (Nonadaptive). Các thuật toán không thích nghi thì không quyết định đường truyền gói dựa trên cơ sở phép đo thông số truyền tải tức thời và topology của mạng. Các đường dẫn từ một nút i tới một nút j nào đó được tính toán trước và nạp vào mạng khi mạng khởi hoạt (Network Booting).Vì thế loại hình này đôi khi còn được gọi là chọn tuyến tĩnh (Static Routing). Ngược lại, các thuật toán chọn đường thích nghi sẽ cho phép thay đổi tuyến truyền gói dựa vào các thay đổi thông số truyền tải và cấu hình của mạng. Có ba nhóm thuật toán loại này: Chọn tuyến tập trung (Centralized Routing) gồm các thuật toán tổng thể sử dụng các thông tin thu thập được từ toàn bộ mạng để đưa ra các kết quả tối ưu. Chọn tuyến cách ly (Isolated Routing) có các thuật toán vận hành trên từng trạm riêng biệt và dựa vào thông tin nó thu thập được tại trạm này, ví dụ như độ dài của hàng, . .. Chọn tuyến phân bố (Distributed Routing) là tổ hợp của cả hai hình thức trên. Thực chất, các thuật toán hiện nay đang được sử dụng đều là các thuật toán thích nghi, chúng cũng chính là các thuật toán chọn tuyến truyền ngắn nhất đã trình bày ở trên. Sự đa dạng chỉ là do cách gọi khác nhau tạo nên. Trong phần sau, ta sẽ xét sơ lược thuật toán phân nhánh (đa đường dẫn ), vì nó ít được sử dụng, phần còn lại chủ yếu tập trung vào các thuật toán chọn tuyến ngắn nhất. 3.2 Thuật toán chọn tuyến phân nhánh 3.2.1 Thuật toán phân nhánh (Bifurcated Routing) Muốn đảm bảo thông tin giữa một cặp người sử dụng, đôi khi mạng không phải chỉ chọn ra một đường dẫn duy nhất để chuyển các gói từ nguốn tới đích mà phải sử dụng nhiều đường để phân bớt lượng tải của từng đường dây. Thí dụ hình 1.4 mô tả chi tiết vấn đề này. Tất cả các đường dây ghép nối trong mạng hình 1.4 đều có dung lượng là 10 đơn vị (các đơn vị đo ở đây chỉ là các thông số đánh giá tương đối và không được xác định chi tiết ) . Có một đích (nút số 6 ) và hai nút nguồn (nút số 1 và nút số 2), nút 1 có lượng tải đưa đén là 5 đơn vị, nút 2 có lượng tải là L. Ta sẽ xét hai trường hợp cụ thể tương ứng với hai giá trị của L: a ) Trường hợp với L = 5 Với lượng tải của tất cả các nút như trên,so với dung lượng đường dây nối giữa nguồn và đích thì có thể xem là nhỏ, do vậy có thể chọn các tuyến truyền gói theo đường bên trái (1 - 3 - 6) và bên phải (2 - 5 - 6) ứng với các nút 1 và 2. Nếu ta chọn tuyến ở giữa, 1 - 4 - 6 cho nút 1 và 2 - 4 - 6 cho nút 2, thì luồng thông tin trên đường nối (4,6) sẽ bằng với dung lượng của đường nên trễ sẽ cao. Thu 5 L Hình 3.4: Ví dụ về yêu cầu thiết lập thuật toán nhiều đường b ) Trường hợp L = 15 Khi tải áp đặt vào nút 2 tăng thêm 10 đơn vị nữa, tức là tải tổng thể là 15 đơn vị, nếu ta tiếp tục chọn theo một trong hai đường dẫn đã xét ở trên cho nút 2 thì có thể dễ dàng nhận thấy là một phần thông tin ( 5 đơn vị ) đưa tới nút này sẽ bị từ chối do dung lượng đường truyền bị hạn chế. Mặt khác, nếu ta chọn tuyến cho nút 1 theo nhánh bên trái (1 ® 3 ® 6), còn nút 2 theo nhánh (2 ® 5 ® 6) và (2 ® 4 ® 6) thì lượng tải tới không vượt quá 75% dung lượng của từng đường, trễ truyền gói tổng thể được đảm bảo tương đối nhỏ và điều quan trọng là không một phần tải nào bị từ chối. Để đảm bảo cho việc nâng cao hoạt tính của mạng, phương thức chuyển mạch phân nhánh đã được thiết lập, mặc dù nó không có ứng dụng cụ thể nhưng người ta vẫn phải dùng đến nó trong việc thiết kế cấu hình mạng (Topological Design). Việc chọn ra đường dẫn trong mạng nhằm mục đích tối thiểu hoá trễ trung bình trong toàn mạng thông qua việc đánh giá nguồn - đích. Kỹ thuật này có thể sử dụng cho cả mạng dữ liệu đồ DG và cả mạng ảo VC. Với mạng DG, khi các gói đén trạm chuyển mạch, các trạm sẽ chọn tuyến cho từng gói riêng biệt, độc lập với các phép chọn cho các gói đến cùng một đích trước đó. Với mạng VC, bất cứ khi nào VC được thiết lập thì tuyến cũng đồng thời được chọn, song các VC khác nhau được chọn tuyến độc lập với nhau. Đích Chọn 1 Chọn 2 Chọn 3 A A 0.63 I 0.21 H 0.16 B A 0.45 H 0.31 I 0.23 C A 0.34 I 0.33 H 0.33 D H 0.50 A 0.25 I 0.25 E A 0.40 I 0.40 H 0.20 F A 0.35 H 0.32 I 0.33 G H 0.47 A 0.30 K 0.23 H H 0.63 K 0.21 A 0.16 I I 0.65 A 0.22 H 0.13 A B C D I J K L J K K 0.67 H 0.22 A 0.11 L K 0.42 H 0.42 A 0.16 Hình 3.5: Ví dụ minh hoạ phương thức chọn tuyến phân nhánh ( Bảng chọn tuyến cho nút J ) Phép chọn tuyến phân nhánh được thực hiện như sau: mỗi trạm chuyển mạch có một bảng chọn tuyến ( Routing Table ) để tới tất cả các trạm khác, trên đó mỗi hàng chỉ ra khả năng dẫn gói tới tới một trạm khác theo thứ tự là tuyến tốt nhất, tốt thứ hai, thứ ba... theo đánh giá trọng số (Weight). Trước khi chuyển gói đi, trạm tạo ra một số ngẫu nhiên và sử dụng nó để chọn tuyến dựa trên việc so sánh nó với trọng số của bảng chọn tuyến. Các bảng này do các vận hành viên của mạng tự thiết lập,nạp vào cho các trạm trước khi vận hành mạng và giữ không đổi từ đó trở đi. Sau đây ta đưa ra một ví dụ để miêu tả việc chọn tuyến phân nhánh. Xét mạng hình 3.5, A, B, C, D, E, F, G, H, I, J, K, L là các nút chuyển mạch của mạng.Giả sử nút J nhận được gói cần phải chuyển cho nút A, nó sử dụng hàng đánh dấu A trong bảng chọn tuyến của mình, trên đó chỉ rõ tuyến là phép chọn thứ nhất, JI và JH là phép chọn thứ hai và thứ ba. Để quyết định tuyến nào, trạm J tạo ra một số ngẫu nhiên giữa khoảng 0.00 và 0.99. Nếu số đó nhỏ hơn 0.63 thì trạm dùng tuyến JA; nếu số đó giữa 0.63 và 0.83 thì trạm dùng tuyến JI; còn lại trạm sử dụng tuyến JH. Các trọng số ở đây dược coi như các xác xuất sử dụng của A, I và H. Một ưu điểm của chọn tuyến phân nhánh là khả năng gửi các loại truyền tải khác nhau theo những đưoừng dẫn khác nhau. Ví dụ, ghép nối giữa terminal và các máy tính ở xa chỉ có các gói tin nhỏ có thể dẫn theo tuyến mặt đất, trong khi đó việc truyền các tập tin dài (Long file Transfer) đòi hỏi dải băng rộng và có thể thực hiện được qua đường truyền vệ tinh. 3.2.2 Thuật toán Flooding Flooding là một thuật toán định đường tĩnh, trong đó mọi gói đưa vào một nút được gửi tới tất cả các đường ra trừ đường nó đã tới. Flooding đã tạo ra một số lượng lớn các bản sao. Do đó cần có một công cụ để ngăn cản quá trình tăng này. Một giới hạn như vậy là bộ đếm hop (hop counter), chứa trong header của mỗi gói, và nó được giảm mỗi khi đi qua một node. Khi bộ đếm hop có giá trị zero thì gói sẽ bị huỷ. Bộ đếm hop phải được phải được khởi tạo ban đầu với giá trị hop bằng với khoảng cách từ nguồn tới đích. Nếu không biết độ dài đường đi này thì nó được tính với trường hợp xấu nhất, đó là tính theo giá trị đường kính lớn nhất của mạng. Như vậy, trong Flooding tất cả các đường đều được thử nên các bản sao đến được đích theo một đường đi ngắn nhất. Một kĩ thuật “làm đập” ngăn Flood là theo dõi những gói đã được Flooding, không gửi nó đi lần thứ hai. Người ta cho phép Router nguồn đặt một số thứ tự trong mỗi gói mà nó nhận được từ nguồn của nó. Mỗi node cần một danh sách ứng với mỗi node nguồn cho biết các số thứ tự của các gói hình thành tại nguồn đã được xem xét. Nếu gói mới đến có trong danh sách thì nó không Flood, nếu là bản sao thì sẽ bị huỷ. Tóm lại, Flooding là một thuật toán định đường tĩnh (vì nó không có sự cập nhật thông tin trong quá trình định đường). Tuy nhiên, khi trong mạng có một node bị hỏng thì Flooding vẫn làm việc tốt,mặc dù nó định đường không tối ưu và thường gây tắc nghẽn trong mạng. Ví dụ Cho một mạng chuyển mạch gói như sau: Giả sử có một gói đi từ nút 1 đến nút 6, tại hop đầu tiên có 3 bản sao được tạo ra và gửi tới các nút 2,3 và 4. ậ hop thứ 2 có 9 bản sao được tạo ra. Đến hop thứ 3 đã có tất cả 22 bản sao. Nút 6 sẽ nhận được 4 bản sao. 3.3 Các thuật toán đường dẫn ngắn nhất (Shortest-path Routing) Phần lớn các mạng chuyển mạch gói sử dụng các thuật toán khác nhau của phương pháp chọn tuyến đường ngắn nhất do lớp mạng thực hiện.Một số mạng chọn tuyến theo theo cách thức tập trung, thiết lập đường dẫn giữa nút nguồn và nút đích ở trung tâm điều hành mạng NMC ( Network Management Center) hay trung tâm điều khiển chọn tuyến RCC (Routing Control Center) rồi sau đó phân phối các thông tin chọn tuyến tới tất cả các nút chuyển mạch trong mạng. Các mạng khác sử dụng cách thức phi tập trung hay còn gọi là cách thức phân bố, từng nút trao đổi thông tin chọn tuyến và giá thành với các nút khác trong mạng trên cơ sở tương tác cho đến khi các bảng chọn tuyến đáp ứng được yêu cầu chọn tuyến ngắn nhất. Trong phần này chúng ta mô tả hai thuật toán chọn đường ngắn nhất.Trong một số mạng, người ta chọn ra một loạt các đường dẫn, được xếp thứ tự theo giá thành, khi trên một đường dẫn xảy ra sự cố, ta có thể thay bằng đường khác theo danh mục đã có. 3.3.1 Thuật toán A (Thuật toán Dijkstra) Xét mạng hình 3.6, trên mỗi đường ghép nối có các trọng số tương ứng với giá thành của từng đường, để cho đơn giản ta coi các trọng số này theo cả hai chiều là như nhau, dù rằng trên thực tế chúng có thể có giá trị khác nhau. Để chọn được đường dẫn ngắn nhất từ một nguồn tới tất cả các nút trong mạng, đòi hỏi phải có kiến thức về cấu hình tổng thể của mạng ( danh sách các nút và các ghép nối giữa chúng) cũng như giá thành của từng đường nối. Điều đó dẫn đến việc tính toán tập trung dựa trên thông tin đầy đủ lưu trong các cơ sở dữ liệu trung tâm (Central Database). Trong thí dụ này, chúng ta tìm đường dẫn ngắn nhất từ nút 1 tới tất cả các nút trong mạng. Thuật toán được thực hiện theo từng bước, xây dựng mô hình cây đường ngắn nhất (Shortest-path Tree) có gốc tại nút nguồn ( nút 1). Các đường dẫn ngắn nhất tới k nút khác được tính toán trong k bước, chúng được tập hợp lại trong tập N. 2 1 2 3 3 2 1 5 Hình 3.6 Coi D(v) là khoảng cách (tổng của các trọng số đường nối dọc theo đường dẫn ) từ nút nguồn 1 tới nút v. Coi l(i,j) là giá thành đã cho giữa hai nút i và j. Thuật toán gồm hai bước: Bước khởi đầu Đặt N = {1} (tập N ban đầu chỉ gồm duy nhất nút 1), với mỗi nút v không thuộc N đặt D(v) = l(1,v), với các nút không nối trực tiếp với nút 1 ta coi giá thành bằng ¥. Bước lặp Tìm nút w không thuộc N sao cho D(w) là tối thiểu và bổ sung w vào tập N. Sau đó thay D(v) cho toàn bộ các nút không thuộc N còn lại bằng cách tính: D(v) ¬ Min [D(v), D(w) + l(w, v)] Bước này dược lặp lại cho đến khi tất cả các nút đèu có trong N. Sau khi thực hiện, ta lần lượt có được các bước mô tả bởi bảng thống kê sau: Bảng 3-1 Bảng mô tả thuật toán Bước Tập N D(2) D(3) D(4) D(5) D(6) 0 1 2 3 4 5 {1} {1,4} {1,4,5} {1,2,4,5} {1,2,3,4,5} {1,2,3,4,5,6} 2 2 2 2 2 2 5 4 3 3 3 3 1 1 1 1 1 1 ¥ 2 2 2 2 2 ¥ ¥ 4 4 4 4 Mô hình cây đường ngắn nhất nếu lấy nút 1 làm nút nguồn có thể mô tả như hình vẽ sau: 2 1 2 1 1 Hình 3-7 a Đích Nút tiếp theo 2 3 4 5 6 2 4 4 4 4 Hình 3.7: Thuật toán được áp dụng cho mạng hình 2-6 với nút 1 là nút nguồn Hình (a) Mô hình cây đường ngắn nhất Hình (b) Bảng chọn tuyến cho nút 1 Hình 3-7 b Thuật toán chọn tuyến đường ngắn nhất trên có thể được minh hoạ bằng chương trình sau: { Tìm đường dẫn ngắn nhất giữa nguồn và các nút còn lại trong mạng } Const n =. ..; {số lượng các nút} infinity =. ..; {số lớn hơn mọi trọng số} Type node = 0..n; nodelist = array [1..n] of node; matrix = array [1..n, 1..n] of integer; Procedure ShortestPath (a: matrix; s, t: node; var path: nodelist); { Tìm đường dẫn ngắn nhất từ nguồn s tới ma trận a và trả kết quả về path } Type lab = (perm, tent) ; {Nhãn cố định hay tạm thời} NodeLabel = record predecessor: node; length: integer; labl: lab; end; GraphState = array [1..n] of NodeLabel; var state: GraphState; i,k: node; min: integer; begin for i: = 1 to n do with state [i] do begin predecessor: =0; length:= infinity; labl:=tent end; state [t].length:=0;state [t].labl:=perm; k:=t; {k là nút làm việc khởi đầu} repeat {tìm xem có nút nào tốt hơn k không} for i:=1 to n do if (a[k,i] 0) and (state[i].labl = tent) then {i là nút kế cạnh và tạm thời} if (state[k].length + a[k,i] < state[i].length) then begin state[i].predecessor:=k; state[i].length:= state[i].length + a[k,i]; end; {tìm nút có nhãn tạm thời với nhãn nhỏ nhất} for i:=1 to n do if (state[i].length < min) and (state[i].labl = tent) then begin min:= state[i].length; k:=i; end; until k = s; {lặp cho đến khi đạt đến nguồn} {Ghi đường dẫn vào mảng ra} k:=s; i:=0; repeat i:= i+1; path[i]:=k; k:= state[k].predecessor; until k=0; End; {Kết thúc thủ tục tính đường ngắn nhất} Với thuật toán tính này ta có thể tính được các tuyến đường có đường dẫn ngắn nhất cho từng nút, cụ thể ta coi nút đó là nút nguồn rồi thực hiện các bước kể trên. Trong trường hợp chọn tuyến theo phương thức tập trung, NMC sẽ gửi các bảng chọn tuyến cho từng nút một sau khi đã thiết lập xong, còn nếu mạng sử dụng phương thức phân bố thì từng nút phải tự tính lấy bảng chọn tuyến, cùng sử dụng các thông tin tổng thể như trên (được cung cấp bởi các nút lân cận hoặc bởi NMC ) và chọn ra cây đường dẫn cho riêng nó. Trong phần tiếp theo chúng ta sẽ mô tả một thuật toán khác cũng là loại thuật toán chọn tuyến ngắn nhất. 3.3.1Thuật toán B (Thuật toán Bellman - Furkerson) Thuật toán này cũng gồm hai phần: bước khởi đầu và bước lặp cho tới khi tính xong các tuyến đường dẫn. Sự khác biệt với thuật toán đã trình bày là ở chỗ thay vì coi nút 1 là nút nguồn thì ta coi nó là nút đích, đồng thời từ tất cả các nút khác ta tìm đường dẫn ngắn nhất tới đích 1 này. Trong bảng chọn tuyến ta sẽ chỉ ra khoảng cách (nhớ rằng đây cũng chỉ là giá trị trọng số trừu tượng để mô tả giá thành của tuyến truyền) từ nút bất kỳ tới nút 1 và nút lân cận để truyền tới đích 1 theo tuyến ngắn nhất. Việc tạo bảng chọn tuyến sử dụng thuật toán này đòi hỏi phải lặp đi lặp lại cho từng nút một, và cuối cùng cho ghi tất cả vào trong một tập các nhãn cho từng nút, mỗi nhãn có thông tin chọn tuyến (nút tiếp theo) và khoảng cách tới đích cuối cùng. Mỗi nút v có nhãn (n, D(v)), với D(v) là giá trị hiện thời của khoảng cách ngắn nhất từ nút đó tới đích, còn n là số hiệu của nút tiếp theo trên đường dẫn ngắn nhất tạm thời. Bước thứ nhất Coi nút 1 là nút đích, đặt D(v) = 0 và gán (, ¥) cho tất cả các nút khác. Bước lặp: dán nhãn khoảng cách cho các nút còn lại Với từng nút khác 1 ta thực hiện như sau: Thay D(v) bởi giá trị hiện thời D(w) với từng nút lân cận w để tính giá trị D(w) + l(w, v) và thực hiện phép toán D(v) ¬ min [D(w] = l(w, v) (*) Sau đó, gán nhãn mới của v bằng cách thay n bởi nút lân cận tương ứng với biểu thức (*) tính được và thay giá trị mới tìm được vào D(v). Với mạng ví dụ như hình 3-6, ta thiết lập bảng các vòng thực hiện sau: Bảng 3-2 thuật toán thứ hai dùng cho mạng hình 3-6: Vòng Nút đích /Nhãn 2 3 4 5 6 0 1 2 1 1 1 (., ¥) (1, 2) (1, 2) (., ¥) (1, 5) (5, 3) (., ¥) (1, 1) (1, 1) (., ¥) (4, 2) (4, 2) (., ¥) (5, 4) (5, 4) Sau hai vòng lặp, các giá trị nhãn trở nên bất biến, có nghĩa rằng thuật toán đã được thực hiện xong. Như vậy, trong vòng 1 nhận thấy nút 2 là “gần nhất” đối với nút 1, giá thành mới của nó là D(v) = D(1) + l(1,2) = 2, và nhãn của nó chuyển thành (1,2). Chuyển tới nút 3, ta có thể chọn hoặc D(2) + l(2,3) =5 hoặc D(1) + l(1,3) = 5; giả sử ta chọn D(1) + l(1,3) thì nhãn mới của nó là (1,5) (ta cũng có thể chọn D(2) + l(2,3) vì kết quả cuối cùng như nhau). ậ vòng lặp thứ hai,ta có thể thay tại nút 3 nhãn mới vì giá trị tối thiểu mới là D(w) + l(w, 3) = D(5) + l(5,3) = 3, do vậy nhãn của nó là (5,3). Từ đó trở đi, các giá trị không thay đổi nên quá trình có thể coi là hoàn thành. Nếu ta xây dựng sơ dồ cây trên cơ sở các kết quả nhận được thì ta có mô hình của hình 3-7a, với nút 1 là gốc. Thuật toán này đã được áp dụng cho một số trường hợp cụ thể,ví dụ như trong TYMNET, theo phương thức tập trung. Nếu sử dụng thuật toán này theo phương thức phân bố, ta được một biến dạng mới của nó, gọilà thuật toán B dạng phi tập trung (Decentralized Version of Algorithm B) hay thuật toán phân bố. 3.3.3 Thuật toán B phân bố (Bellman - Ford hay Vector - Distance) Một vấn đề chúng ta cần phải đề cập là ảnh hưởng của các thuật toán chọn tuyến tới việc truyền dữ liệu trong đường truyền. Nếu chúng ta áp dụng phương thức phân bố cho mạng truyền dữ liệu thì có thể xảy ra hiện tượng trong khi các gói đang được truyền trong mạng, do nhận được thông tin về mạng mới được cung cấp, trạm có thể tự ý thay đổi tuyến truyền tin, như vậy có nghĩa là các gói có thể tới đích không theo thứ tự định trước. Điều này không làm ảnh hưởng đến mạng DG (Datagram), nhưng lại có tác động lớn tới mạng VC (Virtual Circuit), vì vậy đôi khi xảy ra hiện tượng sau khi một trạm gửi gói đi, sau một khoảng thời gian lại hiện diện tại chính trạm đó. Chúng ta sẽ trở lại vấn đề này sau. Trong phương thức phân bố, mỗi nút trong mạng phải có hai bảng, một bảng gọi là khoảng cách (Distance Table) ghi giá thành từng đích theo từng đường nối ra (xem hình3-8b). Bảng thứ hai gọi là bảng chọn tuyến như ở phần trước đã xét. Trên hình 3-8a là ví dụ minh hoạ cho các bảng kể trên, trong đó hai bảng trên thuộc nút N, các nút X,Y, Z là các nút lân cận. Mỗi nút trong trường hợp này phải có khả năng thu thập các thông tin về giá thành của từng đường nối (bao gồm cả việc các nút và đường truyền có sự cố hay được phục hồi). Nếu có sự thay đổi, tất cả các nút nhận thông tin thay đổi này, tính lại bảng khoảng cách và tìm ra khoảng cách tối thiểu tới tất cả các nút còn lại. Nếu nó phát hiện có sự thay đổi trong bảng khoảng cách thì nó có nhiệm vụ thông báo sự thay đổi khoảng cách tới tất cả các nút khác. Các nút này dựa vào đó để tính lại các bảng của mình. Nếu một nút mới được khôi phục, nó phải gửi thông báo tới tất cả các nút khác trong mạng đẻ chúng thiết lập lại bảng khoảng cách và bảng chọn tuyến của mình.Quá trình trao đổi thông tin này diễn ra liên tục cho đến khi nào hết các sự thay đổi. Cụ thể thuật toán có 3 phần, tương ứng với ba khả năng có thể xảy ra: nút hoặc đường nối được phục hồi, giá thành của đường nối thay đổi và nhận được thông tin điều khiển. Giả sử nút v là nút thực hiên thuật toán; D(v) là khoảng cách tối thiểu từ v tới đích d; w là nút lân cận của v và giá thành đường nối từ v tới w là l(w,v). Thông số (d,w) trong bảng khoảng cách của nút v chứa giá thành Cd(v,w) từ v tới đích d qua nút w. Tối thiểu hoá Cd(v,i) với iÎ W, W là tập các nút lân cận của v cho ta Dd(v). Giả sử nút lân cận m cho ta khoảng cách tối thiểu này, khi đó dòng d trong bảng chọn tuyến của v sẽ có cặp số (m,Dd(v)). Thuật toán được mô tả như sau: Phần 1. Phục hồi đường nối (m,v). Khi nhận được thông tin này,nút v sẽ làm như sau: Đặt giá trị (m,m) trong bảng khoảng cách của mình là l(m,v). Tính min Cm(v,w), wÎW. Xác định nút p gần nhất. Nếu min Cm(v,w) = Dm(v), có nghĩa là khoảng cách tối thiểu từ nút v tới nút m không đổi, thì đặt n = p trong bảng chọn tuyến ; nếu không, thì thay Dm(v) ¬ min Cm(v,w), wÎW, và dòng m trong bảng chọn tuyến thay bằng (p, Dm(v)) và nội dung mới [m, Dm(v)] được gửi tới tất cả các nút lân cận của v. Ta đánh số cho tập đích (các hàng cho bảng chọn tuyến của nút v) là (a, b, c,. .., r). Sau đó, v gửi thông tin điều khiển [a, Dm(v)], [b, Dm(v)],. .., [r, Dm(v)] tới nút m. Thủ tục này cũng có thể được áp dụng khi một nút chuyển mạch m được phục hồi, chỉ cần thay thế các giá trị cũ và bổ sung thêm vào các bảng nút m này. Phần 2. Thay đổi giá thành đường m, v. Cũng tương tự như phần 1, kho nhận thấy giá thành của đường m, v thay đổi đi D(m,v), nút v sẽ làm như sau: Cộng thêm D(m,v) vào các giá trị cột m trong bảng khoảng cách của v. (Nếu đường m,v có sự cố thì thay chúng bằng giá trị vô cùng ). Với tất cả các nút đích d, tính min Cd(v,w), w Î W, ví dụ nút p cho giá trị tối thiểu này. Nếu min Cd(v,w) = Dd(v), gán n = q. Ngược lại, Dd(v) ¬ min Cd(v,w), w Î W giá trị dòng d trong bảng chọn tuyến chuyển thành (p, Dd(v)) và nội dung điều khiển [d, Dd(v)] được gửi tới tất cả các nút lân cận. Chú ý rằng tin này không cần phải gửi tới các nút đích mà giá thành tới chúng không thay đổi. (a) Nút làm việc N và nút lân cận cận Bảng khoảng cách Bảng chọn tuyến Đích Giá thành nút X Y Z Đích Nút bên cạnh Giá thành A B C D . . 3 5 4 3 . . 2 6 4 6 . . 5 3 2 5 . . A B C D . . Z Z Z X . . 2 3 2 3 . . (b) (c) Phần 3: Nút v nhận được thông tin điều khiển [d, Dd(w)]. Nếu d = v thì chính v là đích nên bỏ qua. Nếu d ¹ v, nút v sẽ thực hiện các bước sau: 1. Thực hiện chuyển Cd(v,w) ¬ Dd(w) + l(w, v)  Nếu Dd(w) = ¥ hoặc rất lớn thì Cd(w) được gán giá trị đó. 2. Tính min Cd(v, w), w Î W. Ví dụ tìm được nút p. Nếu min Cd(v, w) = Dd(w) thì đặt n = p. Ngược lại cho Dd(w) ¬ min Cd(v, w), wÎ Wvà thay dòng d trong bảng chọn tuyến của v bằng (p, Dd(v)) và gửi thông tin điều khiển [d, Dd(w)] tới tất cả các nút bên cạnh. Thuật toán này cho thấy việc tối thiểu hoá giá trị của dòng trong bảng khoảng cách sau khi đã thay thế các giá trị tương ứng chính kà toán tử D(v ) ¬ min [D(w) + l(w, v)] , w Î Wdo thuật toán B thực hiện. Để so sánh với hai thuật toán đã trình bày ở trên, ta xét việc áp dụng thuật toán này cho mạng ở hình 3- 6, trong đó nút 1 là nút nguồn vừa được phục hồi. Bảng 3-3 chỉ ra dòng 1 của các bảng khoảng cách và chọn tuyến ở năm nút khác trong mạng sau mỗi vòng lặp của thuật toán. Mỗi vòng lặp ứng với việc có ít nhất một nút nhận thông tin điều khiển. Khi bắt đầu thực hiện thuật toán, các nút 2, 3, 4 lân cận nút 1 nhận ra rằng nút 1 đã được phục hồi nên liền tiến hành phần 1 của thuật toán, thay đổi các thông số ở cột 1 trong bảng kheoảng cách (“đường qua nút 1”), từ giá trị vô cùng thành các gí trị xác định l(1, v), v = 2, 3, 4. Sự thay đổi này kéo theo sự thay đổi trong bảng chọn tuyến và việc gửi các thông tin điều khiển tới các nút khác. Trong ví dụ này các nút 2, 3, 4 sẽ thay đổi giá trị khoảng cách của chúng tới nút 1 và gửi thông tin điều khiển tới tất cả các nút có liên quan. Các nút nhận được thông tin này sẽ thực hiện phần 3 của thuật toán có nghĩa là bổ sung giá thành đường nối vào trong bảng khoảng cách, tính khoảng cách tối thiểu, đưa vào bảng chọn tuyến nếu có sự thay đổi, và gửi lại tin đi tới tất cả các nút liên quan. Trong bảng 3-3 đó là sự gán nhãn của vòng lặp 1. Mặc dù các thông số của bảng khoảng cách tại tất cả các nút đếu thay đổi theo kết quả của vòng lặp này, bảng chọn tuyến chỉ thay đổi tại nút 3, 5 và 6 thôi. Ba nút này lại gửi các nội dung điều khiển về giá thành tới đích 1 cho tất cả các nút lân cận của chúng. Sau vòng lặp 2 mô tả việc các nút nhận được nội du