6 Алгоритм Netchange. Разнообразие алгоритмов маршрутизации, страница 3

. . , tN ).Íà ìíîæåñòâå òàêèõ íàáîðîâ ââåäåì ëåêñèêîãðàôè÷åñêèéïîðÿäîê ≤l . Çäåñü íóæíî âñïîìíèòü î òîì, ÷òî (NN+1, ≤l )ÿâëÿåòñÿ âïîëíå óïîðÿäî÷åííûì ìíîæåñòâîì.Çàâåðøàåìîñòü àëãîðèòìà 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 óìåíüøàåòñÿ.Ñëó÷àé d = d1 .Óçåë u íå îòïðàâëÿåò íèêàêèõ íîâûõ ñîîáùåíèé òèïà,èíà ôóíêöèè f ýòî ñêàçûâàåòñÿ òîëüêî â òîì, ÷òî çíà÷åíèå tdóìåíüøàåòñÿ íà åäèíèöó. Ïîýòîìó çíà÷åíèå f óìåíüøàåòñÿ.Ñëó÷àé d > d1 .Òîãäà çíà÷åíèå td (ðàâíî êàê è td ) óìåíüøàåòñÿ íà åäèíèöó,è òîëüêî çíà÷åíèÿ td , ó êîòîðûõ d > d1 , óâåëè÷èâàþòñÿ.Îòñþäà ñëåäóåò, ÷òî çíà÷åíèå ôóíêöèè f óìåíüøàåòñÿ.21mydist212Çàâåðøàåìîñòü àëãîðèòìà 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 .Äðóãèå âèäû ìàðøðóòèçàöèèÄî ñèõ ïîð ìû èìåëè äåëî ñ àëãîðèòìàìè ìàðøðóòèçàöèè,êîòîðûå â êàæäîì óçëå ñåòè ñîçäàþò è ïîääåðæèâàþò òàáëèöûìàðøðóòèçàöèè ñ îòäåëüíûì âõîäîì äëÿ êàæäîéâåðøèíû-àäðåñàòà.

Ìîæíî ñîêðàòèòü îáúåì ïàìÿòè èèçäåðæêè, ñâÿçàííûå ñ ïðîñìîòðîì òàáëèö.Îáùàÿ ñòðàòåãèÿ ïîëó÷åíèÿ òàáëèö ìåíüøåãî ðàçìåðà òàêîâà.Äëÿ êàæäîãî êàíàëà ñâÿçè, ïðèìûêàþùåãî ê óçëó, ñòðîèòñÿñïèñîê âåðøèí-àäðåñàòîâ, ìàðøðóòû ê êîòîðûì íà÷èíàþòñÿ ñïðîõîæäåíèÿ ýòîãî êàíàëà. Ýêîíîìèÿ ïàìÿòè áóäåò çàâèñåòü îòòîãî, íàñêîëüêî êîìïàêòíî ìîæíî ïðåäñòàâèòü ìíîæåñòâî âñåõâåðøèí-àäðåñàòîâ, ñîîòâåòñòâóþùèõ êàæäîìó êàíàëó ñâÿçè.×òîáû ýôôåêòèâíî ïðîâîäèòü ïîèñê â òàáëèöàõ, îíè äîëæíûáûòü óñòðîåíû òàê, ÷òîáû äëÿ çàäàííîé âåðøèíû-àäðåñàòà íàîñíîâå òàáëèö ìîæíî áûëî áûñòðî âûáðàòü ñîîòâåòñòâóþùèéåé èñõîäÿùèé êàíàë ñâÿçè.Äðóãèå âèäû ìàðøðóòèçàöèèÑõåìà äðåâåñíîé ðàçìåòêèÝòîò ìåòîä ïîìå÷àåò âåðøèíû öåëûìè ÷èñëàìè îò 0 äî N − 1òàê, ÷òîáû äëÿ êàæäîãî êàíàëà ñâÿçè ìíîæåñòâîâåðøèí-àäðåñàòîâ, ñîîáùåíèå ñ êîòîðûìè îñóùåñòâëÿåòñÿ÷åðåç ýòîò êàíàë, ïðåäñòàâëÿëî ñîáîé èíòåðâàë.Öèêëè÷åñêèì èíòåðâàëîì [a, b) íà ìíîæåñòâå Z áóäåìíàçûâàòü âñÿêîå ìíîæåñòâî öåëûõ ÷èñåë, óäîâëåòâîðÿþùååñëåäóþùåìó ñîîòíîøåíèþ:{a, a + 1, .

. . , b − 1},åñëè a < b,[a, b) ={0, . . . , b − 1, a, . . . , N − 1}, åñëè a ≥ b.Äðóãèå âèäû ìàðøðóòèçàöèèÑõåìà äðåâåñíîé ðàçìåòêè(* Ïàêåò ñ àäðåñîì d áûë ïîëó÷åí èëè ñîçäàí â óçëå u *)ifd = luthenïàêåò äîñòàâëåí ïî àäðåñóâûáðàòü òàêîå ÷èñëî αi , ÷òî d ∈ [αi , αi+1) ;îòïðàâèòü ïàêåò ïî êàíàëó, ïîìå÷åííîìó αielse beginendÒåîðåìà 3Âåðøèíû äåðåâà T ìîæíî çàíóìåðîâàòü òàêèì îáðàçîì, ÷òîáûäëÿ âñÿêîé âåðøèíû è êàæäîãî èñõîäÿùåãî èç ýòîé âåðøèíûêàíàëà ìíîæåñòâî óçëîâ, ïóòü â êîòîðûå ïðîõîäèò ÷åðåç ýòîòêàíàë, îáðàçîâûâàëî öèêëè÷åñêèé èíòåðâàë.Äðóãèå âèäû ìàðøðóòèçàöèèÑõåìà äðåâåñíîé ðàçìåòêèÄîñòîèíñòâàÄëÿ çàäàíèÿ îäíîãî öèêëè÷åñêîãî èíòåðâàëà ìîæíî îáîéòèñü2 log N áèòàìè, óêàçûâàÿ òîëüêî ãðàíèöû èíòåðâàëà.Íåäîñòàòêè1.

Êàíàëû, íå ïðèíàäëåæàùèå äåðåâó T , íå èñïîëüçóþòñÿ, àýòî îçíà÷àåò, ÷òî ðåñóðñû ñåòè ðàñõîäóþòñÿ íåýêîíîìíî.2. Âåñü òðàôèê ñîñðåäîòî÷åí â äåðåâå, à ýòî ïðèâîäèò êïåðåãðóçêàì â ñåòè.3. Âñÿêàÿ íåèñïðàâíîñòü â îäíîì êàíàëå äåðåâà T ïðèâîäèò êðàçðûâó ñåòè.Äðóãèå âèäû ìàðøðóòèçàöèèÑõåìà èíòåðâàëüíîé ðàçìåòêèÎáîáùåíèå ñõåìû äðåâåñíîé ðàçìåòêè, êîòîðîå ïîçâîëèëîïðèìåíÿòü ýòó ñõåìó ê ïðîèçâîëüíûì ñåòÿì òàêèì îáðàçîì,÷òî ïî÷òè êàæäûé êàíàë îêàçûâàåòñÿ çàäåéñòâîâàííûì âïðîäâèæåíèè ïàêåòîâ.Ïðåôèêñíàÿ ìàðøðóòèçàöèÿ ïðåôèêñíîé ìàðøðóòèçàöèè ïîìåòêàìè âåðøèí è êàíàëîâñëóæàò ñòðîêè. ×òîáû âûáðàòü êàíàë, ïî êîòîðîìó íóæíîïðîäâèãàòü ïàêåò, àëãîðèòì ðàññìàòðèâàåò âñå ïîìåòêèêàíàëîâ, ÿâëÿþùèåñÿ ïðåôèêñîì àäðåñà âåðøèíû íàçíà÷åíèÿ.Âûáèðàåòñÿ íàèáîëåå äëèííàÿ èç òàêèõ ïîìåòîê, èïðîäâèæåíèå ñîîáùåíèÿ ïðîâîäèòñÿ ïî ñîîòâåòñòâóþùåìóêàíàëó.Èåðàðõè÷åñêàÿ ìàðøðóòèçàöèÿÈåðàðõè÷åñêèé ìåòîä ìàðøðóòèçàöèè ïðåäïîëàãàåò ðàçáèåíèåñåòè íà êëàñòåðû.ÊÎÍÅÖ ËÅÊÖÈÈ 5-2..