Извадка от документацията към дистрибуцията ALTQ – първата свободна
имплементация на HFSC, разработена в Университета Карнеги Мелън за xBSD.
По-късно е пренесена от Патрик МакХарди в Linux 2.4/2.6.
Следният документ представлява добър справочен материал, но е твърде теоретичен.
Ето защо тук ще изложим основите на HFSC.
„A Hierarchical Fair Service Curve Algorithm for Link-Sharing, Real-Time and
Priority Service“ Ion Stoica, Hui Zhang, and T. S. Eugene Ng. SIGCOMM’97.
Документът може да бъде намерен тук:
http://www.minus273.org/wp-content/uploads/2008/01/sigcom97.pdf
Още информация има тук:
http://www.cs.cmu.edu/~hzhang/HFSC/main.html
-
Сервизна крива:
-
Виртуално време:
-
HFSC планиране:
-
Йерархично планиране:
-
Планиране в реално време:
HFSC поддържа 2 сервизни криви – една за реално-времеви критерии, а другата за
критерии на разпределение на линията.
Сервизната крива на HFSC се състои от 2 сегмента. „m1″ и „m2″ са кривините на
двата сегмента, а „d“ е x-проекцията на точката на пресичане, която определя
дължината на първия сегмент. Логично, „m2″ указва производителността,
гарантирана на един поток в дългосрочен план, докато „m1″ указва скоростта, с
която се обслужва един изблик (burst). Когато кривината на първия сегмент е
по-голяма от тази на втория, я наричаме „вдлъбната“. Една сервизна крива може да
бъде или вдлъбната, или изпъкнала.
m2 ________
________-------- /
/ m2 /
/ /
m1 / /
/ m1 = 0 /
/ __________/
<-d-> <-- d --->
concave convex
Една вдлъбната сервизна крива осигурява ограничен изблик (burst), подобно на
token-bucket. Триъгълната област, образувана от първия сегмент приблизително
съответства на дълбочината на token-bucket, а кривината ограничава нейната
пикова стойност.
Разликата се състои в това, че пиковата стойност на token-bucket е горна граница
на скоростта на изпращане и често се установява на скоростта, която позволява
физическата линия. От друга страна, HFSC гарантира скоростта, дефинирана от
първия сегмент, и следователно не може да бъде установена на скоростта на
физическата линия.
Изпъкналата сервизна крива, от друга страна, потиска първоначалния обем трафик.
„m1″ на изпъкналата крива трябва да бъде 0 в настоящата имплементация.
Една линейна сервизна крива е специален случай на изпъкнала крива с първи
сегмент NULL (т.е. празна стойност).
Линейната сервизна крива съответства на традиционния модел на виртуалния
часовник и е добра отправна точка за потребители-новобранци.
Всеки клас пази общия брой байтове, които вече е изпратил. Когато даден клас се
препълни, за пакета на върха на опашката се калкулира виртуално време vt. То
представлява x-проекция на сервизната крива, съответстваща на (total + packet_len).
В резултат на това vt на даден клас се увеличава монотонно.
Като се даде път на пакета с най-малко виртуално време, разпределението на
капацитет става пропорционално на кривината на сервизната крива на всеки клас.
bytes
| /
| /service curve
| /
next -->+ +----------------+
packet | | /|
length | | / |
| | / |
total --> + +------------+ |
bytes | /| |
already | / | |
sent | / | |
/ | |
| |
| |
--------+---+--------------> time
vt for next packet
vt for previous packet
Сервизната крива се обновява всеки път, когато даден клас се препълни.
Операцията по обновяването взема като минимум
(1) Сервизната крива, използвана при предишния период на препълване
и
(2) оригиналната сервизна крива, която започва в (current_time, total_bytes).
Когато един клас бъде неактивен достатъчно дълго, обновената крива е равна на
(2). От друга страна, когато класът е използвал много повече капацитет от
заделеното за него, обновената сервизна крива е равна на (1). (1) и (2) могат да
се пресекат, когато класът е използвал капацитет съвсем малко по-малък от
своя дял. В този случай, обновената крива би имала различна стойност „d“.
Операцията е илюстрирана в следните фигури. Може би е по-лесно да се разглежда
като полу-празна token-bucket.
________
________--------
/ ______
/ ________--------
________---+----
/ /
/ /
total -> / + new coordinate
/
/
service curve |
of +
previous period current
time
Update Operation
______
________--------
+----
/
/
total -> + new coordinate
|
+
current
time
New Service Curve
HFSC има два независими механизма за планиране. Планирането в реално време се
използва, за да се гарантира едновременно закъснението и разпределението на
мрежов капацитет.
Йерархичното планиране се използва, за да се разпредели излишния капацитет, ако
има наличен такъв.
Когато един пакет излиза от опашката, HFSC винаги опитва първо планиране в
реално време. Ако никой пакет не подлежи на планиране в реално време, се
изпълнява йерархично планиране. HFSC не използва йерархията на класовете за
планиране в реално време.
В HFSC само крайните (leaf) класове имат истински пакети, но виртуалното време
на междинните класове също се поддържа, като се сумира общия брой байтове,
използван от техните наследници.
Когато един пакет излиза от опашката, йерархичният scheduler на HSFC минава през
класовете от корена до един краен клас. На всяко ниво от йерархията scheduler-ът
избира класа с най-малко виртуално време измежду неговите наследници. Когато
бъде достигнат краен клас, той се и обслужва.
Обърнете внимание, че scheduler-ът търси само директни наследници на всяко ниво.
Ето защо разпределението на капацитета е пропорционално на кривините на
сервизните криви сред класовете с един родител, но не и сред такива с различни
родители. Например 4 крайни класа в следващата илюстрация ще получат еднакъв
капацитет, въпреки че А, B и C, D имат различни кривини.
С други думи, съотношението между класовете с един родител контролира
разпределението на капацитета, а абсолютните стойности на кривините нямат
значение. (Също стойностите на виртуалното време трябва да са логични само сред
класовете с един и същи родител).
root (100Mbps)
|
+-------+-------+
| |
E (20Mbps) F (20Mbps)
| |
+---+---+ +---+---+
| | | |
A B C D
(10Mbps) (10Mbps) (1Mbps) (1Mbps)
Противоположно на йерархичното планиране, за планирането в реално време се
използва едно единствено последователно време. Всеки клас пази кумулативен брой
байтове, подобен на общия брой байтове, но само за пакетите, които са били
подложени на планиране в реално време.
HFSC изчислява време за избиране и краен срок за всеки клас.
Времето за избиране и крайния срок са x-проекции на главата и опашката на
следващия пакет.
Един клас може да бъде избран за планиране в реално време, когато текущото време
стане по-голямо от времето за избиране на класа.
Планировчикът за реално време избира класа с най-малък краен срок сред
възможните.
bytes
| /
| /service curve
| /
next -->+ +----------------+
packet | | /|
length | | / |
| | / |
cumulative --> + +------------+ |
bytes | /| |
already | / | |
sent | / | |
/ | |
| |
| |
--------+---+--------------> time
eligible deadline
time
В оригиналния документ за HFSC за планирането в реално време и за
разпределението на капацитета се използва една сервизна крива. ALTQ (а оттам и
имплементацията за Linux) е разширена и може да използва независими криви за
реално време и за разпределение на капацитета.
Разделянето на сервизните криви позволява да се контролират независимо
гарантираната скорост и разпределението на излишния капацитет. Например възможно
е да се гарантира минимум капацитет 2Мбита на два класа, но излишния капацитет
на бъде разпределен в различно съотношение.
Възможно е също която и да е от сервизните криви да бъде установена на 0. Когато
кривата на реалното време е 0, класът получава само излишния капацитет.
Когато кривата на разпределението е 0, класът не може да получава излишен
капацитет при наличие на такъв. Обърнете внимание, че нулево разпределение прави
класа не work-conserving.
Забележете, че разпределението на капацитет може да гарантира заделената скорост
само ако кривата на реалното време е равна или по-малка от кривата на
разпределение на капацитет за всички класове. Ако кривата на разпределението на
капацитета е по-малка, скоростта може да не бъде осигурена.
Пишете ми, ако намерите грешки и/или несъответствия в този текст.
