Đồ án Chọn đường và ứng dụng trong thiết kế mạng WAN

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. Đồ án tốt nghiệp Chọn đ−ờng vμ ứng dụng trong thiết kế mạng WAN Nguyễn xuân tr−ờng - đtth2 - k40 48 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. 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 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 Đồ án tốt nghiệp Chọn đ−ờng vμ ứng dụng trong thiết kế mạng WAN Nguyễn xuân tr−ờng - đtth2 - k40 49 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.2 1 H 0.1 6 B A 0.45 H 0.3 1 I 0.2 3 C A 0.34 I 0.3 3 H 0.3 3 D H 0.50 A 0.2 5 I 0.2 5 E A 0.40 I 0.4 0 H 0.2 0 F A 0.35 H 0.3 2 I 0.3 3 G H 0.47 A 0.3 0 K 0.2 3 H H 0.63 K 0.2 1 A 0.1 6 I I 0.65 A 0.2 2 H 0.1 3 J K K 0.67 H 0.2 2 A 0.1 1 L K 0.42 H 0.4 2 A 0.1 6 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, A B C D I J K L 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 ) Đồ án tốt nghiệp Chọn đ−ờng vμ ứng dụng trong thiết kế mạng WAN Nguyễn xuân tr−ờng - đtth2 - k40 50 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: Đồ án tốt nghiệp Chọn đ−ờng vμ ứng dụng trong thiết kế mạng WAN Nguyễn xuân tr−ờng - đtth2 - k40 51 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 Đồ án tốt nghiệp Chọn đ−ờng vμ ứng dụng trong thiết kế mạng WAN Nguyễn xuân tr−ờng - đtth2 - k40 52 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. 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: 1. 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 ∞. 2. 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 2 1 2 3 3 2 1 5 Hình 3.6 Đồ án tốt nghiệp Chọn đ−ờng vμ ứng dụng trong thiết kế mạng WAN Nguyễn xuân tr−ờng - đtth2 - k40 53 Đích Nút tiếp theo 2 3 4 5 6 2 4 4 4 4 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 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 Đồ án tốt nghiệp Chọn đ−ờng vμ ứng dụng trong thiết kế mạng WAN Nguyễn xuân tr−ờng - đtth2 - k40 54 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) Đồ án tốt nghiệp Chọn đ−ờng vμ ứng dụng trong thiết kế mạng WAN Nguyễn xuân tr−ờng - đtth2 - k40 55 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. 1. 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. 2. 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 Đồ án tốt nghiệp Chọn đ−ờng vμ ứng dụng trong thiết kế mạng WAN Nguyễn xuân tr−ờng - đtth2 - k40 56 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: 1. Đặt giá trị (m,m) trong bảng khoảng cách của mình là l(m,v). 2. Tính min Cm(v,w), w∈W. Xác định nút p gần nhất. 3. 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 Đồ án tốt nghiệp Chọn đ−ờng vμ ứng dụng trong thiết kế mạng WAN Nguyễn xuân tr−ờng - đtth2 - k40 57 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. 4. 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 Δ(m,v), nút v sẽ làm nh− sau: 1.Cộng thêm Δ(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 ). 2.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. 3. 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. 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 3 5 2 6 5 3 A B Z Z 2 3 (a) Nút làm việc N và nút lân cận cận Đồ án tốt nghiệp Chọn đ−ờng vμ ứng dụng trong thiết kế mạng WAN Nguyễn xuân tr−ờng - đtth2 - k40 58 C D . . 4 3 . . 4 6 . . 2 5 . . C D . . Z X . . 2 3 . . 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. 3. Nếu min Cd(v, w) = Dd(w) thì đặt n = p. Ng−ợc lại cho Dd(w) ← min Cd(v, w), w∈ W và 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 ∈ W do 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ẽ