Тема 18.

Задръствания и управление на потоците в мрежата.


страницата се нуждае от дописване/преглеждане


Пакетните мрежи са пример за система за масово обслужване. В тези системи1 се наблюдава случаен елемент при натоварването. Конкретно при мрежите, често една линия се натоварва много несъразмерно, при което се запълват пакетните буфери на хоста, а това води до понижаване производителността на мрежата. Добра аналогия са уличните задръствания: дори цялото Цариградско шосе да е свободно, светофарите около Орлов мост, където се пресичат няколко булеварда, винаги създават тапа.

netlimit.png

Рутърите (които са частен случай на мрежови хостове) трябва някак да се борят със задръстванията. За тази цел има 5 класически подхода:

1. Пререгулиране на буферите

Този подход най-добре се осъществява чрез виртуални канали. В такива случаи се изпраща сервизен пакет за установяване на виртуален канал: в устройствата, през които минава пакетът, се записва номерът на виртуалния канал. След това този канал се ползва монополно чак до неговото разпадане в края на връзката.2.

В добавка към виртуалния канал идва схемата за регулация на буферите: при установяване на канала, междинният хост си заделя 1-2 буфера за него. Тези буфери обслужват само този канал и нищо друго.Същевременно, по канала вървят единствено пакети, предназначени за него, за които пък каналът е единственият допустим маршрут. Получава се така, че пакетите се движат и пристигат в реда, в който са изпратени, и каналът не се задръства от чужд трафик.

Проблем се появява, когато твърде много буфери бъдат ангажирани за канали и не останат достатъчно, че да обслужват бъдещи канали. Тъй като установените канали могат да стоят свободни през голяма част от съществуването си, това означава пилеене на мрежов ресурс. Ако в това време бъде направен опит за установяване на нов канал, той ще се провали.

2. Отстраняване на пакети

При този подход хостът премахва пакети, когато преносната среда (мрежата) се претовари.
Тъй като в някакъв момент източникът ще трябва да препрати изхвърления пакет, не е добре пакет да бъде изхвърлян към края на пътя си. Ако пък той съдържа прикрепено потвърждение, тогава става още по-лошо. Тези две неща важат най-силно за протоколите, които установяват връзки (connection-oriented) и се стремят да постигнат надеждна (reliable) комуникация (IP не е такъв).

За да се избегнат тези неприятни положения, трябва да не се стига дотам, че всички буфери да са разпределени за една и съща опашка. За целта, на всеки вход на хоста стои по един свободен буфер, в който се приемат пакети. При нужда от изхвърляне на пакети, новополучените се разглеждат, и ако не са важни и не съдържат ACK, се премахват. Ако пък са важни, се премахва някой от предишните пакети.

packetbuffers.png
Свободните буфери се разпределят по опашки. Ако всичките отидат на една опашка, не е хубаво: на всички входни линии ще има буфер за приемане, но само от една опашка ще може да се предава. Затова се ограничава дължината на опашката. Ако броят свободни буфери е k, а броят изходящи интерфейси - s, едно възможно решение е всяка опашка да не става по-дълга от ${k \over s}$. След проучване, се оказва, че е достатъчно да няма опашка, по-дълга от ${k \over \sqrt{s}}$. Ограниченията се налагат локално, в устройството, поради което методът е прост и ефективен.

3. Ограничаване броя на пакетите

При този подход в мрежата се движат разрешителни пакети (permits). Мрежово устройство, което има буферирани пакети за изпращане, трябва първо да получи такова разрешително. При получаване разрешителното се унищожава и се изпраща един от чакащите пакети. Нови разрешителни се създават централизирано (от един мрежови център), или разпределено, между устройствата - при доставка до крайния получател, съответният рутър пуска ново разрешително. Идеята на схемата е по всяко едно време броят на пакетите с данни и на разрешителните пакети в мрежата да е константен. Това гарантира, че мрежата няма да се препълни с пакети.

Проблемите при такава логика на работа са няколко. Ако се случи така, че разрешителните започнат да изчезват (авария в устройството, проблем по трасето), намалява и общата пропускателна способност на мрежата. Освен това, разрешителните се движат по неопределен начин: една част от мрежата да е затлачена от пакети, но да няма достатъчно разрешителни, докато в друга част да има много разрешителни и малко пакети. Самите разрешителни също допринасят за натоварването на мрежата. Възстановяването на липсващите рарешителни е сложно, тъй като мрежовото устройство не знае колко разрешителни съществуват в момента. Устройствата пък трябва да могат да обработват (да се съобразяват с) тези разрешителни, което води до тяхното усложняване. Всичко това прави успешното осъществяване на тази идея трудно.

4. Контрол над потока (flow control)

Когато абонатът (крайният хост) трябва да изпрати голям трафик, обичайно е да се регулира темпото, с което той изпраща информацията. Пример за това са механизмите на TCP: при претоварване на получателя, той сигнализира на изпращача да забави темпото. Управлението обикновено се осъществява на OSI ниво 4.
Управлението на трафика между крайните абонати, обаче, регулира трафика между крайните абонати. То влияе слабо върху натовареността в междинните устройства (рутърите, суичовете), тъй като там обработката се извършва на по-ниски нива.

5. Ограничаване (управление) на входа

ИЗвършва се автоматично регулиране - обратна отрицателна връзка: когато хостът усети усилено натоварване, той уведомява другия хост да забави темпото. Пример за такава връзка е ICMP Source Quench съобщението3.
Хостът следи каква част от буферите му са заети. При 60% запълване той изпада в състояние натоварен; при 80% - претоварен ; при 100% - задръстен. При преминаването на границата от 60%, хостът сигнализира на изпращача с жълт пакет (yellow packet). При преминаване 80% се изпраща червен пакет (red packet). Схемата е аналогична на фуния, в която влизат пакетите и излизат контролни пакети.4.

Този подход се счита за най-добър, тъй като решава локални проблеми5, като работи с предвиждане и се стреми да не позволи загуба на трафик. Трудност при него е това, че е нужно хостовете да могат да боравят със специалните пакети. За целта има множество разработки, които целят повишаване на QoS (Quality of Service). Един от тях е Differentiated services. Работата с цветовата схема6, е описана в RFC-та като 2697.

Ситуации без изход (Deadlocks)

deadlock.png
В тази картинка се наблюдава следното: четирите рутъра, които имат максимална дължина на опашковите буфери 4, са разпределили всичките си буфери за изпращащите си интерфейси. Така те не могат да разпределят буфер за входящи пакети, които на свой ред седят в буферите на техните рутъри, не ги освобождават, тези рутъри също не могат да приемат… и мрежата замръзва. От тази ситуация няма изход (то си го пише горе).

Съществува просто решение на проблема: някой от рутърите да изхвърли един пакет. Освобождавайки буфер, той ще приеме пакет от друг рутър, който също ще освободи и приеме, и тъй нататък. Проблемът обаче се корени във факта, че рутърите не знаят, че са в мъртва хватка, и, гонейки максимално качество на услугата, няма да изхвърлят пакет.

Ситуации без изход се срещат във всякакви системи7, и с тях отдавна се води борба чрез предотвратяване (превенция). При мрежовите протоколи, алгоритмите за пренос се правят така, че да не позволяват появата на затворени контури, които при запълването си биха довели до deadlock.

Още четива

Network congestion - Wikipedia
Congestion control
Quality of Service и други животни

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License