Лекция 6. Алгоритм Netchange_ описание_ инварианты_ корректность_ сходимость. Другие виды маршрутизаци (1185656), страница 3
Текст из файла (страница 3)
Ïî èíäóêòèâíîìó ïðåäïîëîæåíèþDw [v ] ≤ k , è îòñþäà âñëåäñòâèå ñîîòíîøåíèÿDu [v ] = 1+ min Dw [v ]w ∈Neighuìû ïîëó÷àåì Du [v ] ≤ k + 1 .Êîððåêòíîñòü àëãîðèòìà NetchangeÒåïåðü ïîêàæåì èíäóêöèåé ïî Du [v ] , ÷òî âñÿêèé ðàç, êîãäà, èç âåðøèíû u â âåðøèíó v ñóùåñòâóåò ïóòü, è ïðèýòîì.Du [v ] < Nd(u, v ) ≤ Du [v ]Êîððåêòíîñòü àëãîðèòìà NetchangeÒåïåðü ïîêàæåì èíäóêöèåé ïî Du [v ] , ÷òî âñÿêèé ðàç, êîãäà, èç âåðøèíû u â âåðøèíó v ñóùåñòâóåò ïóòü, è ïðèýòîì.Ñëó÷àé Du[v] = 0 .Èç ôîðìóëû (2) ñëåäóåò, ÷òî Du [v ] = 0 òîëüêî òîãäà, êîãäàu = v .
Ýòî îçíà÷àåò, ÷òî ìåæäó âåðøèíàìè u è v åñòü ïóñòîéïóòü è d(u, v ) = 0 .Du [v ] < Nd(u, v ) ≤ Du [v ]Êîððåêòíîñòü àëãîðèòìà NetchangeÒåïåðü ïîêàæåì èíäóêöèåé ïî Du [v ] , ÷òî âñÿêèé ðàç, êîãäà, èç âåðøèíû u â âåðøèíó v ñóùåñòâóåò ïóòü, è ïðèýòîì.Ñëó÷àé Du[v] = 0 .Èç ôîðìóëû (2) ñëåäóåò, ÷òî Du [v ] = 0 òîëüêî òîãäà, êîãäàu = v . Ýòî îçíà÷àåò, ÷òî ìåæäó âåðøèíàìè u è v åñòü ïóñòîéïóòü è d(u, v ) = 0 .Du [v] = k + 1 < N .Èç ôîðìóëû (2) ñëåäóåò, ÷òî ñóùåñòâóåò òàêàÿ âåðøèíàw ∈ Neighu , äëÿ êîòîðîé Dw [v ] = k .
Ïî èíäóêòèâíîìóïðåäïîëîæåíèþ ìåæäó âåðøèíàìè w è v ñóùåñòâóåò ïóòü èd(w , v ) ≤ k . Îòñþäà ñëåäóåò, ÷òî ìåæäó âåðøèíàìè u è vòàêæå åñòü ïóòü è d(u, v ) ≤ k + 1 .Du [v ] < Nd(u, v ) ≤ Du [v ]Êîððåêòíîñòü àëãîðèòìà Netchangeu = v =⇒ (Du [v ] = 0 ∧ Nbu [v ] = local)(4)(u 6= v ∧ ∃w ∈ Neighu : ndisu [w , v ] < N − 1)⇒ (Du [v ] = 1+ min ndisu [w , v ] = 1+ndisu [Nbu [v ], v ]) (5)w ∈Neighu(u =6 v ∧ ∀w ∈ Neighu : ndisu [w , v ] ≥ N − 1)⇒ (Du [v ] = N ∧ Nbu [v ] = udef )åñëè(6)u = v, 0,1+minDw [v ],u 6= v ∧∃w ∈ Neighu : Dw [v ] < N − 1,Du [v ] =w ∈NeighuN,u 6= v ∧∀w ∈ Neighu : Dw [v ] ≥ N − 1.åñëèåñëèÒàêèì îáðàçîì, åñëè u è v íàõîäÿòñÿ â îäíîé è òîé æåêîìïîíåíòå ñâÿçíîñòè, òî Du [v ] = d(u, v ) , à â ïðîòèâíîìñëó÷àå Du [v ] = N . Îòñþäà, ïðèíèìàÿ âî âíèìàíèå ôîðìóëó (2)è ïðåäëîæåíèå ∀u, v : L(u, v ) , ïîëó÷àåì çàÿâëåííûé âóòâåðæäåíèè òåîðåìû ðåçóëüòàò î òàáëèöàõ Nbu [v ] .Çàâåðøàåìîñòü àëãîðèòìà Netchange×òîáû óáåäèòüñÿ â òîì, ÷òî ñòàáèëüíàÿ ñèòóàöèÿ ðàíî èëèïîçäíî íàñòóïèò, ïîñëå òîãî êàê çàâåðøàòñÿ èçìåíåíèÿòîïîëîãèè, ìû ââåäåì íîðìèðóþùóþ ôóíêöèþ ïî îòíîøåíèþê ïðåäèêàòó.Äëÿ êîíôèãóðàöèè γ íàøåãî àëãîðèòìàáóäåì ïîëàãàòüti =(÷èñëî ñîîáùåíèé òèïà h, .., ii)++ (÷èñëî óïîðÿäî÷åííûõ ïàð u, v , äëÿ êîòîðûõ Du [v ] = i),è çíà÷åíèåì ôóíêöèè f áóäåì ñ÷èòàòü (N + 1) -ìåñòíûé íàáîðstablemydistf (γ) = (t0 , t1 , .
. . , tN ).Íà ìíîæåñòâå òàêèõ íàáîðîâ ââåäåì ëåêñèêîãðàôè÷åñêèéïîðÿäîê ≤l . Çäåñü íóæíî âñïîìíèòü î òîì, ÷òî (NN+1, ≤l )ÿâëÿåòñÿ âïîëíå óïîðÿäî÷åííûì ìíîæåñòâîì.Çàâåðøàåìîñòü àëãîðèòìà NetchangeËåììà 3.Îáðàáîòêà ñîîáùåíèé òèïàçíà÷åíèÿ f .mydistïðèâîäèò ê óìåíüøåíèþÇàâåðøàåìîñòü àëãîðèòìà NetchangeËåììà 3.Îáðàáîòêà ñîîáùåíèé òèïàçíà÷åíèÿ f .Äîêàçàòåëüñòâî.mydistïðèâîäèò ê óìåíüøåíèþÏðåäïîëîæèì, ÷òî â óçåë u , ó êîòîðîãî Du [v ] = d1 , ïîñòóïèëîñîîáùåíèå h, v , d2 i, è ïîñëå âûïîëíåíèÿ ïåðåâû÷èñëåíèÿíîâîå çíà÷åíèå ïåðåìåííîé Du [v ] ñòàíîâèòñÿ ðàâíûì d . Èçîïèñàíèÿ àëãîðèòìà âûòåêàåò, ÷òî d ≤ d2 + 1 .mydistÇàâåðøàåìîñòü àëãîðèòìà NetchangeÑëó÷àé d < d1 .Òîãäà d = d2 + 1 , è îòñþäà ñëåäóåò, ÷òî çíà÷åíèå td (ðàâíîêàê è td ) óìåíüøàåòñÿ íà åäèíèöó, è òîëüêî çíà÷åíèÿ td , óêîòîðûõ d > d2 , óâåëè÷èâàþòñÿ.
Îòñþäà ñëåäóåò, ÷òî çíà÷åíèåôóíêöèè f óìåíüøàåòñÿ.21Çàâåðøàåìîñòü àëãîðèòìà NetchangeÑëó÷àé d < d1 .Òîãäà d = d2 + 1 , è îòñþäà ñëåäóåò, ÷òî çíà÷åíèå td (ðàâíîêàê è td ) óìåíüøàåòñÿ íà åäèíèöó, è òîëüêî çíà÷åíèÿ td , óêîòîðûõ d > d2 , óâåëè÷èâàþòñÿ. Îòñþäà ñëåäóåò, ÷òî çíà÷åíèåôóíêöèè f óìåíüøàåòñÿ.Ñëó÷àé d = d1 .Óçåë u íå îòïðàâëÿåò íèêàêèõ íîâûõ ñîîáùåíèé òèïà,èíà ôóíêöèè f ýòî ñêàçûâàåòñÿ òîëüêî â òîì, ÷òî çíà÷åíèå tdóìåíüøàåòñÿ íà åäèíèöó. Ïîýòîìó çíà÷åíèå f óìåíüøàåòñÿ.21mydist2Çàâåðøàåìîñòü àëãîðèòìà NetchangeÑëó÷àé d < d1 .Òîãäà d = d2 + 1 , è îòñþäà ñëåäóåò, ÷òî çíà÷åíèå td (ðàâíîêàê è td ) óìåíüøàåòñÿ íà åäèíèöó, è òîëüêî çíà÷åíèÿ td , óêîòîðûõ d > d2 , óâåëè÷èâàþòñÿ.
Îòñþäà ñëåäóåò, ÷òî çíà÷åíèåôóíêöèè f óìåíüøàåòñÿ.Ñëó÷àé d = d1 .Óçåë u íå îòïðàâëÿåò íèêàêèõ íîâûõ ñîîáùåíèé òèïà,èíà ôóíêöèè f ýòî ñêàçûâàåòñÿ òîëüêî â òîì, ÷òî çíà÷åíèå tdóìåíüøàåòñÿ íà åäèíèöó. Ïîýòîìó çíà÷åíèå f óìåíüøàåòñÿ.Ñëó÷àé d > d1 .Òîãäà çíà÷åíèå td (ðàâíî êàê è td ) óìåíüøàåòñÿ íà åäèíèöó,è òîëüêî çíà÷åíèÿ td , ó êîòîðûõ d > d1 , óâåëè÷èâàþòñÿ.Îòñþäà ñëåäóåò, ÷òî çíà÷åíèå ôóíêöèè f óìåíüøàåòñÿ.21mydist212Çàâåðøàåìîñòü àëãîðèòìà NetchangeÒåîðåìà 2.Åñëè íà÷èíàÿ ñ êàêîãî-òî ìîìåíòà òîïîëîãèÿ ñåòè îñòàåòñÿíåèçìåííîé, òî ñïóñòÿ êîíå÷íîå ÷èñëî øàãîâ àëãîðèòìäîñòèãàåò ñòàáèëüíîé êîíôèãóðàöèè.Çàâåðøàåìîñòü àëãîðèòìà NetchangeÒåîðåìà 2.Åñëè íà÷èíàÿ ñ êàêîãî-òî ìîìåíòà òîïîëîãèÿ ñåòè îñòàåòñÿíåèçìåííîé, òî ñïóñòÿ êîíå÷íîå ÷èñëî øàãîâ àëãîðèòìäîñòèãàåò ñòàáèëüíîé êîíôèãóðàöèè.Äîêàçàòåëüñòâî.Åñëè òîïîëîãèÿ ñåòè íå ïðåòåðïåâàåò íèêàêèõ èçìåíåíèé, òî âäàëüíåéøåì ïðîèñõîäèò òîëüêî îáðàáîòêà ñîîáùåíèé òèïà, è ñîãëàñíî ïðåäûäóùåé ëåììå ñ êàæäûì òàêèìïåðåõîäîì çíà÷åíèå ôóíêöèè f óìåíüøàåòñÿ. òàêîì ñëó÷àå âñëåäñòâèå ôóíäèðîâàííîñòè ìíîæåñòâàçíà÷åíèé ôóíêöèè f ìîæåò ïðîèçîéòè òîëüêî êîíå÷íîå ÷èñëîïåðåõîäîâ.
Çíà÷èò, ïîñëå êîíå÷íîãî ÷èñëà øàãîâ àëãîðèòìäîñòèãíåò êîíôèãóðàöèè, â êîòîðîé ïðåäèêàòîáðàùàåòñÿ â èñòèíó.mydiststableÎñîáåííîñòè ðåàëèçàöèè àëãîðèòìà NetchangeÊîððåêòíîñòü àëãîðèòìà, ãàðàíòèðóþùàÿ ïîñòðîåíèåïðàâèëüíûõ òàáëèö çà êîíå÷íîå ÷èñëî øàãîâ, ïîñëå ïîñëåäíåãîòîïîëîãè÷åñêîãî èçìåíåíèÿ, ìàëî ÷òî ãîâîðèò íàì îíàñòîÿùåì ïîâåäåíèè àëãîðèòìà.Ïîêà ïðåäèêàòëîæåí, íè÷åãî îïðåäåëåííîãî î òàáëèöàõìàðøðóòèçàöèè íå èçâåñòíî. Îíè ìîãóò ñîäåðæàòü öèêëû èëèäàæå âîîáùå äàâàòü íåâåðíóþ èíôîðìàöèþ î äîñòèæèìîñòèâåðøèí-àäðåñàòîâ. Ïîýòîìó ïðåäëîæåííûé àëãîðèòì ìîæíîèñïîëüçîâàòü òîëüêî â òàêèõ ïðèëîæåíèÿõ, ãäå òîïîëîãè÷åñêèåèçìåíåíèÿ ðåäêè, à âðåìÿ ñõîäèìîñòè àëãîðèòìà íåâåëèêî ïîñðàâíåíèþ ñî ñðåäíèì ïåðèîäîì âðåìåíè ìåæäóâîçíèêíîâåíèåì äâóõ èçìåíåíèé â òîïîëîãèè ñåòè.Åùå áîëåå îñëîæíÿåò ñèòóàöèþ òî îáñòîÿòåëüñòâî, ÷òîïðåäèêàòçàäàåò ãëîáàëüíîå ñâîéñòâî, è ïîýòîìó ñ òî÷êèçðåíèÿ îòäåëüíîãî óçëà ñåòè ñòàáèëüíàÿ êîíôèãóðàöèÿàëãîðèòìà íåîòëè÷èìà îò íåñòàáèëüíîé êîíôèãóðàöèè.stablestableÎñîáåííîñòè ðåàëèçàöèè àëãîðèòìà NetchangeÇàäà÷à.Âûÿñíèòå, êàêèå çíà÷åíèÿ áóäóò èìåòü âñå ïåðåìåííûå âçàêëþ÷èòåëüíîé êîíôèãóðàöèè àëãîðèòìà Netchange â òîìñëó÷àå, êîãäà ýòîò àëãîðèòì ïðèìåíÿåòñÿ ê ñåòè, èìåþùåéñëåäóþùóþ òîïîëîãè÷åñêóþ ñòðóêòóðó:ABCDEFÏîñëå òîãî êàê áûëà äîñòèãíóòà çàêëþ÷èòåëüíàÿêîíôèãóðàöèÿ, â ñåòè âîçíèê íîâûé êàíàë ñâÿçè ìåæäó óçëàìèA è F .
Êàêîå ñîîáùåíèå óçåë F îòïðàâèò óçëó A ïðè îáðàáîòêåóâåäîìëåíèÿ h, Ai? Êàêîå ïîñëàíèå óçåë A îòïðàâèò óçëóF â îòâåò íà ýòî ñîîáùåíèå?repairÎñîáåííîñòè ðåàëèçàöèè àëãîðèòìà NetchangeÀñèíõðîííàÿ îáðàáîòêà óâåäîìëåíèéÌû ñ÷èòàëè, ÷òî óâåäîìëåíèÿ î òîïîëîãè÷åñêèõ èçìåíåíèÿõîáðàáàòûâàþòñÿ ñèíõðîííî ïî îáå ñòîðîíû êàíàëà ñâÿçè.Ìîæíî ó÷èòûâàòü çàäåðæêó îáðàáîòêè òàêèõ óâåäîìëåíèé.Êàíàë ñâÿçè wu ìîäåëèðóåòñÿ ïîñðåäñòâîì òðåõ î÷åðåäåé:1) OQwu âûõîäíàÿ î÷åðåäü óçëà w ;2) TQwu î÷åðåäü ñîîáùåíèé (èëè ïàêåòîâ äàííûõ),êîòîðûå óæå áûëè ïåðåïðàâëåíû;3) IQwu âõîäíàÿ î÷åðåäü óçëà u .Êîãäà â êàíàëå âîçíèêàåò íåèñïðàâíîñòü, èç î÷åðåäåé TQwu èOQwu âûáðàñûâàþòñÿ âñå ñîîáùåíèÿ, à â êîíåö î÷åðåäè IQwuäîáàâëÿåòñÿ ñîîáùåíèå h , w i.
Êîãäà âîçîáíîâëÿåòñÿíîðìàëüíîå ôóíêöèîíèðîâàíèå êàíàëà ñâÿçè, â êîíåö î÷åðåäèIQwu äîáàâëÿåòñÿ ñîîáùåíèå h, w i.  ýòîì ñëó÷àåïðåäèêàòû P(u, w , v ) áóäóò èìåòü ÷óòü áîëåå ñëîæíóþñòðóêòóðó, íî ñàì àëãîðèòì îñòàíåòñÿ áåç èçìåíåíèÿ.failrepairÎñîáåííîñòè ðåàëèçàöèè àëãîðèòìà NetchangeÌàðøðóòèçàöèÿ ïî êðàò÷àéøèì ïóòÿìÊàæäîìó êàíàëó ñâÿçè ìîæíî ïðèïèñàòü âåñîâîé êîýôôèöèåíò;ïîñëå ýòîãî ðàññìîòðåííûé íàìè àëãîðèòì ìîæíîìîäèôèöèðîâàòü òàê, ÷òîáû îí âìåñòî ïóòåé ñ íàèìåíüøèì÷èñëîì çâåíüåâ âû÷èñëÿë êðàò÷àéøèå ïóòè.
Ïðîöåäóðà Updateâ àëãîðèòìå Netchange áóäåò ó÷èòûâàòü âåñ êàíàëà ñâÿçè uwïðè îöåíêå äëèíû êðàò÷àéøåãî ïóòè ÷åðåç óçåë w , åñëèçàìåíèòü êîíñòàíòó 1 íà âåñîâîé êîýôôèöèåíò ωuw . Ïðè ýòîìêîíñòàíòà N äîëæíà áûòü çàìåíåíà â àëãîðèòìå íàêàêóþ-íèáóäü âåðõíþþ îöåíêó äèàìåòðà ñåòè.Ìîæíî äàæå ïðîâåñòè òàêîå îáîáùåíèå ýòîãî àëãîðèòìà, ÷òîáûîí ìîã ðàáîòàòü ñ êàíàëàìè ñâÿçè, èìåþùèìè ïåðåìåííûé âåñ;ðåàêöèåé óçëà u íà èçìåíåíèå âåñîâîãî êîýôôèöèåíòà êàíàëàäîëæíî áûòü ïåðåâû÷èñëåíèå çíà÷åíèé ïåðåìåííûõ Du [v ] äëÿâñåõ âåðøèí v .Äðóãèå âèäû ìàðøðóòèçàöèèÄî ñèõ ïîð ìû èìåëè äåëî ñ àëãîðèòìàìè ìàðøðóòèçàöèè,êîòîðûå â êàæäîì óçëå ñåòè ñîçäàþò è ïîääåðæèâàþò òàáëèöûìàðøðóòèçàöèè ñ îòäåëüíûì âõîäîì äëÿ êàæäîéâåðøèíû-àäðåñàòà.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
