Лекция 6. Алгоритм Netchange_ описание_ инварианты_ корректность_ сходимость. Другие виды маршрутизаци (1185656), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Ìîæíî ñîêðàòèòü îáúåì ïàìÿòè èèçäåðæêè, ñâÿçàííûå ñ ïðîñìîòðîì òàáëèö.Îáùàÿ ñòðàòåãèÿ ïîëó÷åíèÿ òàáëèö ìåíüøåãî ðàçìåðà òàêîâà.Äëÿ êàæäîãî êàíàëà ñâÿçè, ïðèìûêàþùåãî ê óçëó, ñòðîèòñÿñïèñîê âåðøèí-àäðåñàòîâ, ìàðøðóòû ê êîòîðûì íà÷èíàþòñÿ ñïðîõîæäåíèÿ ýòîãî êàíàëà. Ýêîíîìèÿ ïàìÿòè áóäåò çàâèñåòü îòòîãî, íàñêîëüêî êîìïàêòíî ìîæíî ïðåäñòàâèòü ìíîæåñòâî âñåõâåðøèí-àäðåñàòîâ, ñîîòâåòñòâóþùèõ êàæäîìó êàíàëó ñâÿçè.×òîáû ýôôåêòèâíî ïðîâîäèòü ïîèñê â òàáëèöàõ, îíè äîëæíûáûòü óñòðîåíû òàê, ÷òîáû äëÿ çàäàííîé âåðøèíû-àäðåñàòà íàîñíîâå òàáëèö ìîæíî áûëî áûñòðî âûáðàòü ñîîòâåòñòâóþùèéåé èñõîäÿùèé êàíàë ñâÿçè.Äðóãèå âèäû ìàðøðóòèçàöèèÑõåìà äðåâåñíîé ðàçìåòêèÝòîò ìåòîä ïîìå÷àåò âåðøèíû öåëûìè ÷èñëàìè îò 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Äðóãèå âèäû ìàðøðóòèçàöèèÑõåìà äðåâåñíîé ðàçìåòêè(* Ïàêåò ñ àäðåñîì d áûë ïîëó÷åí èëè ñîçäàí â óçëå u *)ifd = luthenïàêåò äîñòàâëåí ïî àäðåñóâûáðàòü òàêîå ÷èñëî αi , ÷òî d ∈ [αi , αi+1) ;îòïðàâèòü ïàêåò ïî êàíàëó, ïîìå÷åííîìó αielse beginendÒåîðåìà 3Âåðøèíû äåðåâà T ìîæíî çàíóìåðîâàòü òàêèì îáðàçîì, ÷òîáûäëÿ âñÿêîé âåðøèíû è êàæäîãî èñõîäÿùåãî èç ýòîé âåðøèíûêàíàëà ìíîæåñòâî óçëîâ, ïóòü â êîòîðûå ïðîõîäèò ÷åðåç ýòîòêàíàë, îáðàçîâûâàëî öèêëè÷åñêèé èíòåðâàë.Äðóãèå âèäû ìàðøðóòèçàöèèÑõåìà äðåâåñíîé ðàçìåòêèÄîñòîèíñòâàÄëÿ çàäàíèÿ îäíîãî öèêëè÷åñêîãî èíòåðâàëà ìîæíî îáîéòèñü2 log N áèòàìè, óêàçûâàÿ òîëüêî ãðàíèöû èíòåðâàëà.Äðóãèå âèäû ìàðøðóòèçàöèèÑõåìà äðåâåñíîé ðàçìåòêèÄîñòîèíñòâàÄëÿ çàäàíèÿ îäíîãî öèêëè÷åñêîãî èíòåðâàëà ìîæíî îáîéòèñü2 log N áèòàìè, óêàçûâàÿ òîëüêî ãðàíèöû èíòåðâàëà.Íåäîñòàòêè1.

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

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

Характеристики

Список файлов лекций