Khóa luận Cơ chế khắc phục lỗi kênh khi kết nối Multicast trong mạng MPLS

ng qua LER chứ không nối trực tiếp với nhau hay nối với nhau thông qua mạng khác. ¾ Kênh nối giữa LER của mạng đang xét và máy chủ đầu cuối hoặc bộ định tuyến của mạng khác được gọi là kênh truy nhập. ¾ Nhóm Multicast là một tập hợp các máy chủ trao đổi thông tin với nhau. ¾ Dữ liệu được một thành viên của nhóm Multicast truyền đi sẽ được nhận bởi tất cả các thành viên khác trong nhóm. Trong mục này chúng ta mô hình hoá mạng như một đồ thị G = (V,E). Trong đó V là tập hợp các đỉnh của đồ thị chứa các bộ định tuyến (LSR và LER) của mạng. E là tập hợp các cạnh của đồ thị chính là các kênh của mạng. Tập hợp E không bao gồm các kênh truy nhập. Tất cả các kênh được giả thiết là kênh song công. Hơn nữa chúng ta giả sử truyền thông Multicast đã được thiết lập trong mạng. Ký hiện cây định tuyến Multicast ( )TT EVT ,= là một cây vô hướng có trọng số. Cây định tuyến Multicast có thể là cây đường ngắn nhất hoặc cây nút cơ sở. Trong trường hợp cây nút cơ sở, chúng ta giả thiết rằng nút cơ sở không phải là một LER. Ta ký hiện S là nút nguồn của cây khi T là cây đường ngắn nhất hoặc là nút cơ sở khi T là cây nút cơ sở. VT là tập hợp các nút của cây định tuyến Multicast, ET là tập hợp các kênh của cây định tuyến Multicast. Cây T nằm trong đồ thị G, vì vậy và . VVT ⊂ EET ⊂ Trong một cây, nút “con” của nút i là tập hợp các nút liền kề nằm trên Downstream (tính từ nút S) và nút “cha” của nút i là nút liền kề và nằm trên Upstream (tính từ --37-- nút S). Ta ký hiệu là tập các nút “con” của nút i và là nút “cha” của nút i. Tương tự như vậy đối với một kênh l, ký hiệu là tập các kênh Downstream liền kề của kênh l tính từ nút S. Ký hiệu Ti Vchild ⊂ Ti Vparent ⊂ Tl Edown ⊂ ( ) ( ) ( )( )isubisubT TT EVisub ,= là cây “con” của cây T tính từ nút S và có gốc là nút i. Ký hiệu ( ) ( ) ( )( )llsubllsubT TT EVllsub ,= là đồ thị “con” của T bao gồm: nút i các kênh Upstream của l (tính từ nút S), kênh l và cây con có gốc tại nút j kênh Downstream của l (tính từ nút S). Theo định nghĩa, ( ) {} ( ) { } ( )( )jsubjsubT TT ElVillsub ∪∪= , là một cây. Ta định nghĩa trọng số của kênh lTw , TEl∈ như sau. Xét một nút TVi∈ và là kênh Upstream nối trực tiếp vào nút i tính từ nút S. Nếu i là một LER, thì là số thành viên của nhóm Multicast gửi hoặc nhận lưu lượng Multicast thông qua các kênh truy nhập kết nối với nút i. Nếu i là một LSR, thì Tt Eup ∈ iupT w , 0, =iupTw . Các bộ định tuyến LER trong mạng MPLS có thể sử dụng giao thức báo hiệu chẳng hạn như IGMPv3 [16] để xác định số máy chủ Multicast kết nối qua kênh truy nhập. Nếu như không có thông tin về số máy chủ Multicast kết nối qua kênh truy nhập trong mạng MPLS, thì ta gán giá trị “1” cho trọng số của Upstream của LER với giả thiết nó gửi và nhận lưu lượng Multicast của nhóm Multicast đang xét thông qua ít nhất một kênh truy nhập của nó. Nói tóm lại, ta coi như trọng số của kênh đã được biết từ trước trong giai đoạn thiết lập cây định tuyến Multicast. Ta gọi nút nhận là nút nối trực tiếp với Downstream tính từ nút S của kênh l với . Các nút nhận là các LER truyền lưu lượng đến hoặc từ một nhóm Multicast trên một kênh truy nhập. Nút ““lá”” của cây T là nút 0≠lw TVi∈ sao cho childi = Ø. Ta gọi là tập hợp các nút ““lá”” của cây T. Lưu ý rằng tất cả các nút ““lá”” là nút nhận nhưng một nút nhận không nhất thiết phải là một nút ““lá””. Thực vậy, một LER chuyển tiếp lưu lượng từ một cây qua các kênh truy nhập cũng có thể đồng thời chuyển tiếp cũng lưu lượng này tới các LSR hoặc các LER khác của cây trước khi lưu lượng này tới một kênh truy nhập. Trong thực tế, LER thực hiện việc cắt bỏ nhãn trước TT VL ⊂ --38-- khi gửi các gói tin trên kênh truy nhập và tráo đổi nhãn trước khi gửi các gói tin tới các bộ định tuyến khác nằm trong miền MPLS. Như đã trình bày trong mục I.2.4, tính năng này được gọi là chuyển tiếp hỗn hợp L2/L3. Ví dụ như trên Hình III-1, bộ định tuyến LER 2 thực hiện chuyển tiếp hỗ hợp L2/L3. Nếu như chỉ có một máy chủ nối với LER 2 qua một kênh truy nhập của LER 2, khi đó trọng số của kênh nối giữa LER 2 và LSR 2 có giá trị là “1” trong khi LER 2 không phải là nút ““lá”” của cây T. Hình III-2. Trọng số tốc độ lỗi kênh Ta giả sử rằng kênh chỉ có lỗi duy nhất đó là đứt kênh. Khi một kênh l lỗi, nó sẽ bị loại bỏ khỏi E. Tốc độ lỗi Fl của kênh El∈ là số lần lỗi trung bình của kênh l trong một đơn vị thời gian. Thời gian trung bình giữa các lỗi (MTBF) của một kênh là khoảng thời gian trôi qua trước khi kênh lỗi. Nếu như biết trước thời gian trung bình giữa các lỗi của một kênh l là MTBFl thì l l MTBFF 1= . Ta giả sử rằng đã biết trước tốc độ lỗi của toàn bộ các kênh trong mạng và tốc độ lỗi đủ nhỏ để có thể coi tại một thời điểm trong mạng chỉ có một kênh lỗi. Ta định nghĩa một đại lượng dương fl là trọng số tốc độ lỗi kênh của mỗi kênh El∈ , nó tỷ lệ với tốc độ lỗi kênh và có quan hệ với tốc độ lỗi của các kênh khác trong mạng. Ví dụ như nếu như mạng được cấu thành từ hai loại kênh khác nhau và các kênh loại thứ nhất có tốc độ lỗi gấp đôi so với các kênh loại thứ hai thì f = 2 đối với loại kênh thứ nhất và f = 1 đối với loại kênh thứ hai. Trong trường hợp không có thông tin về tốc độ lỗi kênh ta giả sử rằng tất cả các kênh trong mạng có cùng tốc độ lỗi, có nghĩa là: 1, =∈∀ lfEl --39-- Nếu như kênh lỗi thì cây T sẽ bị tách thành hai cây là TTEl∈ 1 và T2. Trong đó T1 là cây có chứa nút S và T2 là cây còn lại. Tất cả các máy chủ Multicast kết nối với LER của T2 đều bị tách rời khỏi nhóm Multicast và tất cả các LER của T2 đều bị tách khỏi cây T. Nếu như bộ định tuyến LER i bị tách khỏi cây T thì máy chủ Multicast sẽ bị tách rời khỏi nhóm Multicast. Trong luận văn này ta coi một kênh có tốc độ lỗi bằng 1 khi lỗi làm cô lập 2 máy chủ (Hình III-2(a)) sẽ tương đương với một kênh có tốc độ lỗi 2 khi lỗi làm cô lập 1 máy chủ (Hình III-2(b)). iupT, w Đường giữa hai đỉnh N PNN P ,1 1 và Np của đồ thị G là chuỗi các đỉnh (N1, N2,..., Np) sao cho [ ] ( ) ENNpi ii ∈−∈∀ +1,,1..1 và ji VVji ≠≠∀ , . Ta ký hiệu [ ]{ }piNV iP pNN ..1,1 ∈= là tập hợp các nút của và PNNP ,1 ( ) [ ]{ }1..1, 1,1 −∈= + piNNE iiP pNN là tập hợp các kênh của . Đối với một cây , chỉ tồn tại một đường duy nhất giữa hai nút bất kỳ . Vì vậy chỉ tồn tại một đường giữa nút gốc S và nút A trên một hướng và một đường giữa S và B trên hướng khác. Ký hiệu nút là nút sao cho PNN P ,1 ( TT EVT ,= ) A, TVB∈ ASP , BSP , ' ,BAS qN ( )ANNNNSP rqAS ,...,,...,,, 21, = , ( )BNNNNSP sqBS ,...,,...,,, 21, = và . Nút được gọi là nút chung gần nhất (LCA) của A và B. sr NN ≠ ' ,BAS Định nghĩa 1: Đường được bảo vệ là đường duy nhất jiPP , ( )pNN ,...1 giữa hai nút sao cho: TVji ∈, jNiN p == ,1 và [ ] ( )( )TiiTi ENNVNpi ∈∧∈−∈∀ +1,,1..1 Định nghĩa 2: Đường dự phòng là một đường jiBP , ( )pNN ,...1 giữa hai nút TVji ∈, sao cho: jNiN p == ,1 và [ ] ( ) { }( )jiVVNpi Ti ,\,1..2 ∪∈−∈∀ và [ ]( )( )Tii EENNpi \,1..1 1 ∈−∈∀ + --40-- Trong khi đường được bảo vệ là duy nhất thì đường dự phòng có thể không duy nhất đối với một cặp nút. Các đường dự phòng bảo vệ cây khỏi lỗi kênh bằng cách cung cấp các đường dự trữ (redundancy). Đường dự phòng và cây T không có kênh chung vì vậy lỗi một kênh trên cây không ảnh hưởng đến việc định tuyến lại lưu lượng sang đường dự phòng. Tương tự như vậy đường dự phòng và cây T không có đỉnh chung (ngoại trừ hai đỉnh đầu mút của đường dự phòng) vì vậy tránh được hiện tượng nhầm giữa lưu lượng thông thường và lưu lượng định tuyến lại tại tất cả các nút của đường dự phòng. Như đã thể hiện ở trên, đối với một cặp nút cho trước i và j của một cây T, nếu như lỗi một kênh của đường được bảo vệ thì có thể định tuyến lại lưu lượng sang đường dự phòng mà không gây cô lập bất cứ một thành viên nào của nhóm Multicast. Hơn nữa cây jiPP , jiBP . 'T mới tạo thành do việc ghép cây T với đường dự phòng sẽ có tổng trọng số bằng cây T.. Định lý 1: Ứng với một tập hợp bao gồm: một cây cho trước , hai nút , một đường được bảo vệ , một đường dự phòng và một kênh ; tồn tại một cây ( TT EVT ,= ) TVji ∈, jiPP , jiBP , jiPP Eb ,, ∈ ( )'' ,' TT EVT = sao cho 1. jiBPTT VVV ,' ∪= 2. { } { }bEEE jiBPTT \ ,' ∪= 3. ∑∑ ∈∈ = TT El lT El lT ,,' ' ϖϖ Chứng minh: Ta ký hiệu ( ) 11 ,1 TT EVT = và ( )22 ,2 TT EVT = là hai cây nhỏ hơn sinh ra do loại bỏ kênh b khỏi cây T. Các cây T và T1 có gốc tại nút S. Không mất tính tổng quát ta giả sử và . Với i là gốc của cây T 1T Vj ∈ 2T Vi∈ 2. Các cây T1 và T2 có nút và kênh tách rời nhau vì vậy đồ thị { } { }( )bEEVVT jiji BPTBPT \, ,, ' ∪∪= là kết quả của việc hợp nhất T1 --41-- và T2 thông qua đường dự phòng sẽ tạo thành một cây, do đó mệnh đề (1) và (2) đúng. Với S là gốc của cây jiBP , 'T . Tổng ∑ ∈ TEl lT ,ω là tổng số các máy chủ Multicast kết nối với tất cả các LER của cây T. Tương tự như vậy ∑ ∈ ' ' , T El lT ω là tổng số các máy chủ Multicast nối với tất cả các LER của cây 'T . Do { }( )jiVVVVV jiji BPTBPTT ,\ ,,' ∪=∪= và không có một máy chủ Multicast nào được kết nối với một đỉnh của { }jiV jiBP ,\ , , vì vậy số lượng máy chủ Multicast kết nối tới tất cả các LER của cây T và 'T là bằng nhau, do đó mệnh đề (3) đúng. Nót nhËn Kª nh kh¸ c S b i j w=1 w=1 w=1 w=1 w=0 w=0 S i j w=1 w=1 w=1 w=0 w=0 w=1 T2 T1 Nót kh¸ c § - êng dù phßng § - êng ®- î c b¶o vÖ (a) C©y tr- í c khi lçi kª nh (b) C©y sau khi lçi kª nh Hình III-3. Bảo vệ cây định tuyến bằng một đường dự phòng khi lỗi một kênh Như đã được trình bày ở trên, khi lỗi một kênh trên cây T có gốc tại S, cây T sẽ bị chia thành hai cây nhỏ hơn là T1 và T2 trong đó tất cả các nút nhận trên cây T2 đều bị cô lập khỏi nút S. Nếu như một đường dự phòng được chèn vào cây T (xem Hình III-3(a)), khi đó nếu lỗi bất cứ kênh b nào trên đường được bảo vệ thì cây jiBP , jiPP , 'T sẽ thay thế cây T để tải lưu lượng Multicast và không có một nút nhận nào bị ”rớt” (xem Hình III-3(b)). Nhờ đó tăng được tính chất “đàn hồi” của cây như đã được trình bày ở phần trên. --42-- Hình III-4 Giá trị w, tdrop và adrop của các kênh của một cây Ký hiệu là số lượng Host kết nối với các nút nhận bị cô lập khỏi cây T khi kênh lỗi trong trường hợp không có đường dự phòng nào được thiết lập. là tập hợp đồng thời kênh l và tất cả các kênh trên cây “con” của T có gốc tại nút nằm trên Downstream của kênh l tính từ nút S, vì vậy theo định nghĩa của ta có: ltdrop TEl ∈ ( )ll TE sup ltdrop ( ) ∑ ∈ = lTlEk kltdrop sup ω Tương tự như vậy ta ký hiệu là số lượng Host kết nối tới các nút nhận bị cô lập khỏi cây T khi lỗi kênh l hoặc lỗi bất cứ Downstream nào của l khi không có đường dự phòng nào được thiết lập. Theo định nghĩa ta có: ladrop ( )∑∈= lEk kkl Tl tdropfadrop sup Trong ví dụ trên Hình III-4 đưa ra các giá trị trọng số ω , tdrop và adrop của tất cả các kênh. Tiếp theo đây ta sử dụng tham số tdrop để định nghĩa độ “đàn hồi” của cây, và tham số adrop để tính nhanh độ “đàn hồi”. Sau đây là định nghĩa độ “đàn hồi” của cây. Như ta đã biết, khi một kênh lỗi thì cây T sẽ bị chia thành hai cây T1 và T2. Nếu như một đường dự phòng được thiết lập đối với cây T, thì theo Định lý 1 có thể thiết lập một cây jiBP , 'T sao cho không có một nút nhận nào bị cô lập khỏi cây khi xảy ra lỗi một kênh nằm trên đường được --43-- bảo vệ . Vì vậy trọng số của các nút nhận bị cô lập khỏi nhóm truyền thông Multicast sử dụng cây được bảo vệ bởi đường dự phòng khi lỗi một kênh là: jiPP , jiBP , ( ) ( ) ∑ ∉ ∈ == jiPP T Ek Ek kkdd tdropfijRjiR , ,, Hơn nữa, giả sử không có đường dự phòng nào được thiết lập ứng với cây T, khi đó số lượng máy chủ cô lập khỏi nhóm Multicast khi xảy ra lỗi một kênh là: ∑ ∈ = TEk kkt tdropfR Độ lớn là một hằng số và nó chỉ phụ thuộc vào Topo của cây trong khi đó còn phụ thuộc vào các nút hai đầu i và j của đường dự phòng . Độ lớn của biểu thị mức độ ảnh hưởng của lỗi một kênh trên cây không được bảo vệ bởi bất cứ đường dự phòng nào, trong khi đó biểu thị mức độ ảnh hưởng của lỗi một kênh trên cây đã thiết lập một đường dự phòng. Mức chênh lệch của hai giá trị này biểu thị số lượng Host không bị “rớt” khỏi nhóm Multicast sau khi lưu lượng được định tuyến lại sang tải trên đường dự phòng. tR dR jiBP , tR dR Định nghĩa 3: Độ “đàn hồi” của cây ( )TT EVT ,= được bảo vệ bởi một đường dự phòng giữa hai nút TVji ∈, là đại lượng tính bằng: ( ) ( )jiRRjiR dt ,, −= Trong Chương II chúng ta đã định nghĩa tính “đàn hồi” của mạng là khả năng mạng có thể duy trì cung cấp dịch vụ ngay cả khi xảy ra lỗi. Vì vậy theo định nghĩa trong Chương II thì một cây được bảo vệ bởi đường dự phòng sẽ có tính “đàn hồi” khi lỗi một kênh trên cây đã thiết lập đường dự phòng thì số lượng thành viên của nhóm bị cô lập khỏi nhóm là nhỏ. Đại lượng ( )jiR , biểu thị độ tối ưu của đường dự phòng sử dụng để bảo vệ một cây định tuyến Multicast và vì vậy phù hợp với định nghĩa độ “đàn hồi” trong Chương II. Đại lượng ( )jiR , có giá trị càng lớn thì độ “đàn hồi” của cây được bảo vệ bởi đường dự phòng càng cao. Độ “đàn hồi” có giá --44-- trị nằm trong khoảng 0 và Rt. Độ “đàn hồi” có giá trị bằng Rt có nghĩa là khi lỗi bất cứ kênh nào trên cây thì không có thành viên nào bị cô lập khỏi nhóm Multicast. Nói một cách khác, độ “đàn hồi” có giá trị bằng 0 có nghĩa là đường dự phòng không bảo vệ được bất cứ thành viên nào khỏi bị rớt khi xảy ra lỗi một kênh. Định nghĩa 4: Một đường dự phòng là đường bảo vệ tối ưu trên cây T khi nó thoả mãn: BABP , ( ) ( )jiRBAR dVjid T ,min, , ∈= Theo Định nghĩa 3, ( ) ( )jiRRjiR dt ,, −= trong đó là hằng số, vì vậy cực đại độ “đàn hồi” cũng có nghĩa là cực tiểu giá trị tR ( jiR , ) ( )jiRd , . Một đường dự phòng làm cho độ “đàn hồi” của cây lớn nhất thì sẽ là đường tối ưu về mặt bảo vệ cây. Trong phần tiếp theo chúng tôi trình bày một thuật toán xác định đường dự phòng làm cho độ “đàn hồi” của cây được bảo vệ là lớn nhất bằng cách tối thiểu hoá đại lượng . dR III.2. Cực đại độ “đàn hồi” của cây với một đường dự phòng Trong mục này chúng tôi trình bày một thuật toán xác định đường dự phòng làm cho độ “đàn hồi” của cây được bảo vệ là lớn nhất. Việc tìm đường dự phòng được thực hiện dựa trên thuật toán đường ngắn nhất. Ở đây chúng tôi trình bày một phiên bản bổ sung của thuật toán này có xem xét đến sự thay đổi của cây được sử dụng để mô hình hoá nhóm Multicast khi một Host có thể tuỳ ý rời bỏ hoặc gia nhập nhóm. III.2.1. Thuật toán chính Ở đây ta giả sử chưa có đường dự phòng nào đã được tính toán và thiết lập cho cây T. Thuật toán được thực hiện theo các bước như sau (xem Thuật toán 1). Trước hết ta tính hai đại lượng tdrop và adrop cho mỗi kênh của cây, tiền xử lý cây qua đó đẩy nhanh quá trình xác định LCA để tính đại lượng Rd. Sau đó ta tính Rd cho lần lượt từng cặp tạo thành từ một nút ““lá”” và một nút khác của cây. Ta ký hiệu (A,B) là cặp nút của cây có Rd nhỏ nhất. Thuật toán đường ngắn nhất sẽ đi tính --45-- đường dự phòng giữa A và B. Nếu như thuật toán đường ngắn nhất không tìm được đường dự phòng tức là không có đường dự phòng nào là đường bảo vệ tối ưu của cây T. Định lý 2: Nếu như kết quả của Thuật toán 1 là một đường dự phòng thì ứng với đường dự phòng đó, độ “đàn hồi” của cây T là cực đại. Chứng minh: Giả sử ta đã biết giá trị các đại lượng adrop và tdrop ứng với từng kênh của cây (bước 1 đến 3 của Thuật toán 1). Trước hết chúng ta chứng minh bằng phản chứng rằng ít nhất một nút đầu cuối của đường dự phòng có Rd nhỏ nhất là nút ““lá”” của cây T. Giả sử rằng ta biết trước hai nút đầu cuối i và j của đường dự phòng có giá trị đại lượng Rd là nhỏ nhất, chứng minh bằng phản chứng ta giả sử i không phải là nút “lá” của cây T. Ký hiệu (k là nút thuộc tập nút con của i, xem Hình III-5) khi đó: ichildk ∈ ( ) ikd adropKjiR +=, và ( ) ∑ ∈ += kchildh khd adropKjkR , trong đó K là một phần của đại lượng , nó là phần chung của dR ( )jiRd , và . Cụ thể hơn , K tương ứng với tất cả các kênh ngoại trừ kênh (i, k) và các kênh Downstream của nút k tính từ nút gốc S. Vì vậy: ( jkRd , ) ∑ ∈ += kchildh khikikik adroptdropfadrop khi đó: ( ) ( )jiRjkR dd ,, < đo đó cặp nút không tối thiểu hoá , trái với giả thiết. ( ji, ) dR Vì vậy nếu đường dự phòng làm cây T có độ đàn hồi lớn nhất thì ít nhất có một trong số hai nút đầu cuối A và B của nó là nút ““lá””. Giả sử nút cuối A là nút “lá”, nút cuối còn lại là B không nhất thiết phải là nút “lá”. Các nút A và B được xác định trong các bước từ 5 đến 8 với đường dự phòng giữa A và B đảm bảo R BABP , d cực --46-- tiểu và vì vậy độ “đàn hồi” của cây cực đại. Đường dự phòng được tính toán ở bước thứ 9 sử dụng thuật toán đường ngắn nhất giữa A và B trên đồ thị ( ) { }( TT EEBAVVG \,,\' ∪= ) vì vậy đường dự phòng và cây có các nút và kênh tách rời nhau. Thuật toán 1: Tính toán đường dự phòng tối ưu cực đại khả năng “đàn hồi” của cây T trong một graph G TÌM ĐƯỜNG DỰ PHÒNG TỐI ƯU (cây T, graph G) 1. For mỗi TEl∈ do 2. Tính và ; ltdrop ladrop 3. Endfor 4. Tiền xử lý cây T để đẩy nhanh quá trình xác định LCA; 5. For mỗi cặp ( ) ZYVLZY TT ≠×∈, do 6. Tính ( )ZYRd , ; 7. Endfor 8. Tìm cặp nút (A,B) sao cho ( ) ( )ZYRBAR d ZY VZ LYd T T ,min, ≠ ∈ ∈= 9. Tính đường ngắn nhất giữa A và B trong graph ( ) { }( )TT EEBAVVG \,,\' ∪= Định nghĩa 5: Một đường dự phòng “cận” tối ưu là đường dự phòng thoả mãn: ( ) ( )jiRBAR d existsBP Vjid ji T ,min, , , ∈= Nếu như không tìm thấy đường dự phòng tối ưu, ta mở rộng Thuật toán 1 để đi tìm đường dự phòng “cận” tối ưu. Thuật toán mở rộng (xem Thuật toán 2) bao gồm các bước sau. Tương tự như Thuật toán 1, các đại lượng tdrop và adrop của tất cả các kênh của cây T được tính từ các bước 1 đến 3 để đẩy nhanh quá trình tính LCA ở bước 4. --47-- Hình III-5. Chứng minh thuật toán Đối với mỗi cặp nút TTk VVn ×∈ , giá trị đại lượng không phụ thuộc vào trình tự của nút trong cặp và có giá trị bằng 0 khi hai nút chập làm một. Vì vậy trong một Graph có chứa dR TV nút, thì tổng số cặp nút có thể là nút cuối của đường dự phòng sẽ là ( ) 2 1−= TTpairs VVN . Thuật toán 2: Tính toán đường dự phòng “cận” tối ưu TÌM ĐƯỜNG DỰ PHÒNG “CẬN” TỐI ƯU (cây T, graph G) 1. For mỗi TEl∈ do 2. Tính và ; ltdrop ladrop 3. Endfor 4. Tiền xử lý cây T để đẩy nhanh quá trình xác định LCA; 5. For mỗi cặp ( ) ZYVVZY TT ≠×∈, do 6. Tính ( )ZYRd , ; 7. Endfor 8. Định nghĩa chuỗi cặp nút ( )pairsnnn ,...,, 10 thoả mãn với [ ] TTkpairs VVnNk ×∈∈∀ ,..0 thì ( ) ( )jdid nRnRji ≤≤∀ , ; 9. ; 0:=i 10. repeat 11. Tính đường ngắn nhất giữa các cặp nút ni trên Graph ; ( ) { }( )TT EEBAVVG \,,\' ∪= 12. 1: += ii 13. until tìm được một đường dự phòng Trong các bước từ 5 đến 7 của Thuật toán 2, đại lượng Rd được tính cho tất cả cặp của tất cả các nút trên cây như đã được định nghĩa ở trên sau đó chúng được xắp xếp lại theo trình tự từ nhỏ đến lớn tại bước 8. Trong các bước từ 9 đến 13, xem xét từng cặp nút theo trình tự đã xắp xếp ở trên bắt đầu từ nút có R pairsN d nhỏ nhất, sử dụng thuật toán tìm đường ngắn nhất để tính đường dự phòng giữa hai nút của cặp cho đến khi tìm ra đường dự phòng. Cũng giống như đường dự phòng tối ưu, không --48-- phải lúc nào cũng tồn tại đường dự phòng “cận” tối ưu. Cụ thể là, Thuật toán 2 xem xét từng cặp nút của cây và tìm đường dự phòng ngắn nhất giữa hai nút trong cặp cho đến khi tìm ra được đường dự phòng, nếu như không tồn tại đường dự phòng “cận” tối ưu thì cũng không tồn tại đường dự phòng tối ưu cho cây. Ví dụ trong trường hợp TVV = và thì sẽ không tồn tại đường dự phòng tối ưu cũng như “cận” tối ưu cho cây T. TEE = Hình III-6. Sự thay đổi cấu trúc cây khi một nút “lá” rời bỏ hoặc gia nhập nhóm III.2.2. Phiên bản mở rộng Các thành viên có thể gia nhập hoặc rời bỏ nhóm Multicast tại bất cứ thời điểm nào làm cho nhóm Multicast và cây là động. Khi Topo của một cây thay đổi, ta có thể không cần phải thực hiện lại từng bước của Thuật toán 1 để tính đường dự phòng mới. Ở đây ta giả sử thông qua Thuật toán 1, một đường dự phòng đã được thiết lập giữa hai nút A và B cho cây T. Thuật toán 3 xử lý vấn đề thay đổi của cây định tuyến Multicast T. Khi một nút C rời bỏ (hoặc gia nhập) một nhóm Multicast, một số lượng nhất định các nút và kênh sẽ bị loại bỏ khỏi (hoặc bổ sung vào) cây định tuyến Multicast. Xét một đường trên cây T. Ký hiệu D là nút đầu tiên của , nó có thể là một LER hoặc có nhiều hơn một nút “con” trên cây T. Vì vậy khi nút C rời bỏ (hoặc gia nhập) nhóm Multicast, thì tất cả các kênh và nút ngoại trừ nút D của đường đều bị loại bỏ khỏi cây như được thể hiện trên Hình III-6. Ta ký hiện SCP , SCP , DCP , 'T là cây đã được sửa đổi và là giá trị mới của của cây 'tdrop tdrop 'T . Nếu như là giá ltdrop --49-- trị đại lượng của kênh l trên cây T, thì là giá trị đại lượng của kênh l trên cây tdrop 'ltdrop tdrop 'T . Theo định nghĩa của tdrop , nếu như thay đổi kênh Downstream (tính từ nút S) của nút D, thì chỉ giá trị của các kênh Upstream (tính từ nút S) của nút D sẽ bị thay đổi theo. tdrop Thuật toán 3: Tính toán đường dự phòng tối ưu trên một graph G sao cho cực đại độ “đàn hồi” của cây 'T là kết quả của việc sửa đổi luồng Downstream (tính từ nút gốc S của cây T) của nút D trên cây T. CẬP NHẬT ĐƯỜNG DỰ PHÒNG (tree T, graph G, node D) 1. For mỗi do SDP El , ∈ 2. tính ; 'ltdrop 3. Endfor 4. For mỗi cặp ( ) YVLZY TT ≠×∈, Z do 5. cập nhật ; ( )ZYRd , 6. Endfor 7. ( ) ( ) ( ) ( )ZYRZYRVLZYBA d ZY VZ LYdTT T T ,min,,:, ≠ ∈ ∈=×∈= 8. Tính đường ngắn nhất giữa A và B trên graph ( ) { }( )TT EEBAVVG \,,\' ∪= ; Thuật toán 3 được thực hiện theo các bước sau. Trước tiên tính lại đại lượng tdrop cho tất cả các kênh trên đường giữa các nút D và S tại các bước từ 1 đến 3. Sau đó tại các bước từ 4 đến 6, đại lượng Rd được cập nhật cho tất cả các cặp nút của cây 'T . Ký hiệu ( )jiRd ,' là giá trị mới của Rd giữa hai nút i và j của cây 'T . Ta có thể tính của cây ( jiRd ,' ) 'T dựa vào các giá trị ( )jiRd , của cây T và vì vậy không cần phải thực hiện việc tính toán lại toàn bộ từ đầu. Chẳng hạn như, nếu ta sử dụng Định nghĩa 3 để tính các đại lượng Rd và , sau đó khi nút C rời bỏ nhóm thì: ' dR --50-- ( ) ( )∑∑∑ ∑ ∪∪∈∈∈ ∈ ++= = SDPDCPjiPPTjiPPSDPjiPPDCP jiPPT EEEEk kk EEk kk EEk kk EEk kkd tdropftdropftdropf tdropfjiR ,,,,,,, , \\\ \ , Vì tất cả các nút nằm trên đều bị loại bỏ khỏi cây khi nút C rời bỏ nhóm, do đó cả hai nút i và j đều không thể nằm giữa C và D. Vì vậy ta có: DCP , ∑∑ ∈∈ = jiPPCDPjiPPDCP EEk kk EEk kk tdropftdropf ,,,, \\ Nếu ta gọi l là kênh đầu tiên trên đường từ D đến C, khi đó biểu thức ở trên có thể được viết đơn giản như sau: l EEk kk adroptdropf jiPPDCP =∑ ∈ ,, \ và vì vậy: ( ) ( )∑∑ ∪∪∈∈ ++= SDPDCPjiPPTjiPPSDP EEEEk kkEEk kkld tdropftdropfadropjiR ,,,,, \\, hơn nữa: ( ) ( ) ( )∑ ∑ ∑ ∑∑ ∑ ∈ ∪∈ ∈ ∪∪∈∈ ∈ ++= ++= = jiPPSDP SDPjiPPT jiPPSDP SDPDCPjiPPTjiPPDCP jiPPT EEk EEEk kkkk EEk EEEEk kkkk EEk kk EEk kkd tdropftdropf tdropftdropftdropf tdropfjiR ,, ,,' ,, ,,,',, ,' \ \ ' \ \ '' \ ' \ '' 0 , Kết quả là: ( ) ( ) ( )( )∑∈ −+−= jiPPSDP EEk kkkldd tdroptdropfadropjiRjiR ,, \ '' ,, (III.1) Tương tự như vậy đối với trường hợp nút C gia nhập nhóm. Vì vậy thay vì tính lại toàn bộ các giá trị của , ta có thể nhận được giá trị mới của bằng cách lấy R'dR ' dR d trừ đi đại lượng adrop và cộng thêm giá trị ( )kkk tdroptdropf −' đối với kênh k nằm trên một đường của cây. Sau khi tất cả các giá trị của Rd đã được cập nhật, đường --51-- dự phòng được tính toán trong các bước 7 và 8 sử dụng thuật toán tìm đường ngắn nhất giữa hai nút của một cặp với tập giá trị Rd đạt giá trị lớn nhất giống như Thuật toán 1. Thuật toán 3 có thể xử lý tất cả các thay đổi của cây định tuyến Multicast khi bất cứ nút nào gia nhập hoặc rời bỏ nhóm. Trong trường hợp một nút rời bỏ nhóm và nút đó không phải là nút cuối của đường dự phòng đã được tính trước khi Topo của cây thay đổi, không nhất thiết phải cập nhật lại đường dự phòng mặc dù nó sẽ không đảm bảo tính tối ưu. Để giảm khối lượng tính toán cần thiết để cập nhật đường dự phòng khi Topo của cây thay đổi, ta có thể đặt ra một ngưỡng thay đổi đối với cây định tuyến Multicast và sẽ không cập nhật đường dự phòng chừng nào ngưỡng này bị vượt quá. Khi đó mới sử dụng Thuật toán 3 để tính lại đường dự phòng. III.3. Tính toán các đại lượng Phần này trình bày phương pháp tính nhanh đại lượng Rd dựa trên định nghĩa của nó và phương pháp tính các đại lượng tdrop và adrop. Đại lượng Rd cho tất cả các cặp nút trên cây T được tính toán trong các bước từ 5 đến 7 của Thuật toán 1. Ta có thể tính Rd