пїњ

јЋ√ќ–»“ћ ѕЋјЌ»–ќ¬јЌ»я QOS — ”„≈“ќћ ‘–ј√ћ≈Ќ“ј÷»» ѕј ≈“ќ¬ ¬ —≈“я’ WIMAX

”ƒ  004.724.4
ј.—.  рупский, ».¬. Ѕойченко
јлгоритм планировани€ QoS с учетом фрагментации пакетов в сет€х WiMax
–ассматриваютс€ известные алгоритмы планировани€ EDF и WFQ в услови€х возникновени€ фрагментации пакетов в сет€х WiMax. ѕредложены модификации этих алгоритмов, позвол€ющие компенсировать потери полосы пропускани€. ƒано сравнение реализаций модифицированных алгоритмов с их эталонным вариантом по критерию соблюдени€ качества обслуживани€ (QoS). ѕриведена методика оценки потерь полосы за счЄт наличи€ фрагментации пакетов.
 лючевые слова: качество обслуживани€, планирование ресурса, фрагментаци€, накладные расходы.
«адача обеспечени€ качества сервиса в сет€х WiMax
Ѕольшинство существующих компьютерных сетей используют принцип Best Effort дл€ распределени€ полосы пропускани€ среди абонентов. ѕри этом качество предоставл€емых услуг передачи не гарантировано, и трафик занимает всю свободную полосу. “ем не менее существуют такие сервисы (трансл€ци€ видеопотока, осуществление управлени€ машинами и агрегатами, производственными системами в реальном времени с заданным временем отклика), которые чувствительны к изменени€м характеристик каналов. ƒл€ обслуживани€ таких сервисов были созданы протоколы RTP [1] и RTCP [2]. ѕервый позвол€ет компенсировать дрожание полосы (англ. jitter) и обнаруживать нарушение последовательности пакетов. ¬торой служит дл€ определени€ QoS (англ. Quality of Service - качество обслуживани€), обеспечени€ обратной св€зи и синхронизации потоков получател€ и отправител€. “о есть осуществл€етс€ попытка компенсировать ухудшение качества при передаче через протокол транспортного уровн€ (на деле, чаще RTP и RTCP реализуютс€ поверх UDP, так как гаранти€ доставки в TCP вызывает дополнительные задержки). ƒл€ обеспечени€ гарантии QoS на основе RTP, RTCP и RSVP [3] были введены модели Integrated Service [4] и Differentiated Service [5] дл€ работы на сетевом уровне. ƒалее будет рассмотрена задача соблюдени€ QoS одним отдельно вз€тым узлом на канальном уровне, на основе спецификации беспроводной сети WiMax [6].
ѕостановка задачи
«адача обеспечени€ QoS на узле может быть представлена как задача оптимизации: максимизировать количество передаваемых данных при заданных ограничени€х QoS дл€ сервисных потоков. ќграничени€ должны учитыватьс€ только в том случае, если у абонента имеютс€ данные дл€ отправки. —тандарт WiMax выдел€ет следующие типы потоков и списки параметров QoS (табл. 1):
“аблица 1
“ипы потоков и их параметры QoS_________________________
ѕриоритет. “ип —писок параметров QoS ѕредполагаемые типы трафика
UGS(Unsolicited Grant Service) Maximum Sustained Traffic Rate (Pmaxj) Maximum Lattency (Lmaxi) Tolerated Jitter (Jmaxi) ѕримен€етс€ дл€ сервисов, требующих фиксированной во времени полосы (T1/E1 and Voice over IP)
ERT(Extended Real Time) Maximum Sustained Traffic Rate(Pmaxi) Minimum Reserved Traffic Rate(Pmini) Maximum Latency(Lmaxi) —очетает в себе UGS и RT - фиксированную полосу в задаваемые клиентом промежутки времени
RT(Real Time) Maximum Sustained Traffic Rate (Pmaxi) Minimum Reserved Traffic Rate (Pmini) Maximum Latency(Lmaxi) ѕредназначен дл€ сервисов, требующих выделени€ измен€ющейс€ во времени полосы на регул€рной основе (MPEG)
NRT(Not Real Time) Maximum Sustained Traffic Rate(Pmaxi) Minimum Reserved Traffic Rate (Pmini) ѕредназначен дл€ сервисов, требующих посто€нной полосы в среднем (FTP)
BE(Best Effort) Maximum Sustained Traffic Rate (Pmaxi) —ервисы, обслуживающиес€ по возможности, стандарт не предоставл€ет гарантий
ћножество допущенных потоков »нформаци€ об изменении QoS
ƒопуск к среде (A dttiis sion — onfcrol) ѕланир ќЅў»≈ (Scheduler)
*
»нф ормаци€ о не с о бтодении Q о s –ис. 1. јрхитектура системы планировани€
јрхитектура системы планировани€
ƒл€ решени€ задачи планировани€ на станци€х "^ћах стандарт [6] предлагает архитектуру, состо€щую из двух блоков (рис. 1).
 ак правило, реализаци€ этих модулей зависит друг от друга. ¬ общем случае допуск нового потока должен осуществл€тьс€ в случае, если выполн€етс€ следующее условие:
р <х рт1п,
г=1
где – - полоса пропускани€, обеспечиваема€ узлом; рл дл€ потока г.
(1)
минимально гарантированна€ полоса
Ќа сумму максимально гарантированных полос Pi условий не налагаетс€. «адача планиров-
щика - обеспечить такую очерЄдность отправки пакетов, чтобы соблюсти требовани€ QoS дл€ каждого из потоков:
pmax > Pi > pmax,
Li < max, (2)
Ji < jmax,
где Pi - объЄм отправленных дл€ потока i данных; pmax и pmm - ограничени€ максимального и минимального трафика соответственно; Lt - наибольша€ задержка среди пакетов в очереди станции на отправку; Lmax - максимально допустима€ задержка; Ji - джиттер: разность между максимальной и минимальной L; J;max - максимально допустима€ величина джиттера.
ѕотери полосы из-за фрагментации пакетов
ќднако даже выполнение услови€ (1) не гарантирует возможности работы системы без нарушени€ QoS из-за наличи€ фрагментации пакетов. ѕакет не может быть распакован до тех пор, пока у принимающей стороны не окажутс€ все его фрагменты. ≈сли в (2) наблюдаетс€ равенство, то при наличии фрагментации и полной востребованности минимальной полосы возникает нарушение QoS
(рис. 2).
Pi
pn I
i I
–ис. 2. ‘рагментаци€ пакета относительно минимальной полосы
‘рагмент минимальной гарантированной полосы, закрашенный чЄрным, фактически потер€н в текущем кадре, и минимальна€ полоса не соблюдаетс€. ќчевидно, что объЄм потерь полосы зависит от величины кадра. ≈сли предположить, что объЄм пакетов, передаваемых по сети, подчин€етс€ нормальному закону распределени€, то можно попробовать оценить среднюю величину потерь от фрагментации пакетов. ¬ ходе эксперимента полоса многократно заполн€лась пакетами, размеры которых определ€лись на основе закона нормального распределени€, фиксировалс€ объЄм фрагмента, не поместившийс€ в полосу.
N
д=pmin-X Pkgi, i=1
(3)
минимальна€ гарантированна€
где ƒ - фрагмент пакета, превысивший размерность рт1п, рта полоса потока; Pkgг - пакет с размером, полученным на основе нормального распределени€.
ѕри этом выбираетс€ наибольшее N при котором величина ƒ положительна. »сходные данные дл€ эксперимента приведены в табл. 2.
2
“аблица 2
»сходные данные дл€ эксперимента________________
¬еличина «начение
—редний размер пакета 50
с размера пакета 20
–ш1и1 (минимальна€ полоса пропускани€ потока) 500
 оличество итераций заполнени€ очереди 10000
–езультаты эксперимента сведены в гистограмму (рис. 3).
ѕревышение пакетом полосы (байт)
–ис. 3. –аспределение фрагментов пакетов, не поместившихс€ в полосу
ѕолученную картину следует проверить на нормальность распределени€. —ама по себе сумма нормальных случайных величин есть нормальна€ случайна€ величина со средним, €вл€ющимс€ суммой средних, и со среднеквадратическим отклонением (— ќ), €вл€ющимс€ суммой — ќ. ƒалее, следу€ правилу трех сигм, можно минимизировать веро€тность потери полосы за счЄт фрагментации. —ледует отметить, что данна€ картина не всецело характеризует веро€тность нарушени€ QoS вследствие недостатка полосы. Ќа основании этих данных возможно выработать рекомендации дл€ реализации модул€ доступа к среде. ƒл€ полноты требуетс€ рассмотреть ещЄ и веро€тность наличи€ фрагментов, оставшихс€ от предыдущего кадра. ѕолученный же результат характеризует худший вариант, когда фрагментов пакетов на начало текущего кадра не имеетс€. ƒанный вопрос подробнее будет рассмотрен в последующих работах.
јлгоритмы планировани€
–€д авторов (в частности [7]) в качестве алгоритмов дл€ планировани€ QoS предлагают использовать св€зку из DFPQ дл€ планировани€ среди классов потоков (см. табл. 1) и набор из EDF, WFQ, BE или RR дл€ планировани€ в самих классах. ѕотоки типа UGS и ERT получают место в полосе на первом этапе планировани€. ѕоток BE не налагает требований к каналу св€зи, поэтому потоки этого типа получают ту часть полосы, котора€ останетс€ от планировани€ других типов потоков. ќсновными объектами работы алгоритмов €вл€ютс€ потоки типов RT и NRT. DFPQ отдаЄт зарезервированное, но не зан€тое потоком более высокого класса место в полосе следующему за ним по приоритету. ¬ наихудшем случае все потоки будут обладать только минимальным зарезервированным местом дл€ отправки.
ѕри этом WFQ гарантирует равномерную отправку всеми потоками. “о есть гарантируетс€ QoS Pminj дл€ NRT.   отправке выбираетс€ наиболее дискриминированный на прошлых шагах поток. јлгоритм займЄт всю полосу полностью только в идеальном случае, когда будет доступна его реализаци€ в качестве побитового конвейера. ¬ практической его реализации следует учитывать дискрет этого конвейера (чаще всего выбирают пакет). ƒл€ этого целесообразно использовать методику из предыдущего пункта. ¬ дополнение к традиционной реализации, приведЄнной в [7], следует добавить механизм контрол€ за соблюдением верхней границы pmax, не учитыва€ при планировании
те потоки, которые исчерпали свою полосу Pmaxi в текущей секунде.
јлгоритм EDF в его классическом виде также не учитывает один существенный момент: не фиксирует превышение потоком его Pmin . ¬ случае, если один из потоков с небольшим Lmax произведЄт вброс пакетов суммарным объЄмом превышающим Pimax , то при полной загрузке полосы
произойдЄт нарушение QoS дл€ потоков (возможно нескольких) с более низким значением Zjnax в этом или в последующих фреймах. ѕроиллюстрируем эту ситуацию (рис. 4).
TTL = 2

TTL = 3 TTL = 2 TTL = 1

I Pmin I Pmin I Pmin

щ TTL = 3 TTL = 2 1 TTL = 2 TTL = 1
б
I Pmin I Pmin I Pmin
–ис. 4. ѕример нарушени€ QoS в EDF при отсутствии контрол€ за P,mm потока; а - ситуаци€ до вставки; б - после
јлгоритм гарантирует, что пакеты будут отправлены без нарушени€ максимального времени ожидани€, если это вообще возможно дл€ данного набора пакетов. –ассмотрим предельный случай (рис. 4, а), когда выполн€етс€ равенство дл€ услови€ (1) и дл€ пакетов, отправл€емых в кадре N, врем€ жизни составл€ет также N. “о есть все потоки исчерпали свой минимум pmin.
ƒопустим, одна из станций с Lmax , равным двум, производит вставку (рис. 4, б). ¬ этом случае отправка всех пакетов с меньшим TTL сдвигаетс€ на более поздний срок. ѕри этом часть пакетов из последующих кадров не сможет быть отправлена в срок (на рисунке отмечена чЄрным). ѕри этом возможны нарушени€ QoS сразу дл€ нескольких потоков. “о есть система обеспечени€ QoS должна гарантировать потоку, по крайней мере, полосу не меньшую чем pmax с задержкой не более LЩax . ≈сли приложение отправл€ет пакеты сверх этой меры, то их своевременна€ отправка не гарантирована, что может привести к нарушению QoS.
ѕредлагаетс€ ввести в EDF контроль над количеством отправл€емых потоком данных таким образом, чтобы при избытке пакетов в очереди требовани€ QoS нарушались только дл€ одного этого потока. ј именно: сохраним приоритетную очередь дл€ пакетов по TTL, но будем на первом этапе выбирать из очереди только пакеты дл€ тех потоков, дл€ которых Pimin за текущую секунду ещЄ не был заполнен. “аким образом, мы гарантируем, что каждый из потоков получит свою минимальную полосу. ≈сли остаЄтс€ ещЄ неизрасходованна€ полоса - производитс€ второй проход по очереди, на этот раз без огл€дки на pmin. ќднако следует дл€ потоков RT, NRT, BE не допускать превышени€ pmax . ѕри достижении верхней границы, до истечени€ текущей секунды, следует считать, что очередь данного потока на отправку пуста.
«аключение
¬ результате проведЄнного исследовани€:
1. Ѕыла предложена методика оценки величины дополнительной полосы, требуемой дл€ передачи фрагментированных пакетов.
2. Ѕыла произведена оценка дополнительной полосы дл€ пакетов с заданным законом распределени€ размера.
3. Ѕыла предложена модификаци€ алгоритма EDF с целью минимизации количества потоков с отказом QoS.
»сследовани€ выполн€ютс€ в рамках государственных контрактов є 13.G25.31.0011 от 07 сент€бр€ 2010 г., и є 14.740.11.0398 от 20 сент€бр€ 2010 г.
Ћитература
1. RTP: A Transport Protocol for Real-Time Applications [Ёлектронный ресурс]. - –ежим доступа: http://tools.ietf.org/html/rfc3550, свободный (дата обращени€: 25.04.2012).
2. Real Time Streaming Protocol (RTSP) Applications [Ёлектронный ресурс]. - –ежим доступа: http://tools.ietf.org/html/rfc2326, свободный (дата обращени€: 25.04.2012).
3. Resource ReSerVation Protocol (RSVP) [Ёлектронный реcурс]. - –ежим доступа: http://www.ietf.org/rfc/rfc2205.txt, свободный (дата обращени€: 25.04.2012).
4. Integrated Services in the Internet Architecture: an Overview [Ёлектронный реcурс]. - –ежим доступа: http://tools.ietf.org/html/rfc1633, свободный (дата обращени€: 25.04.2012).
5. An architecture for differentiated services [Ёлектронный реcурс]. - –ежим доступа: http://tools.ietf.org/html/rfc2475, свободный (дата обращени€: 25.04.2012).
6. IEEE Standard for local and metropolitan area networks. Part 16: Air interface for broadband wireless access systems // IEEE Std 802.16-2009 (Revision of IEEE Std 802.16-2004), vol., no., pp.C1-2004, May 29 2009 doi: 10.1109/IEEESTD.2009.5062485) [Ёлектронный ресурс]. - –ежим доступа: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5062485&isnumber=5062484, дл€ зарегистрированных пользователей (дата обращени€: 25.04.11).
7. јунг ћьо ћаунг. »сследование и разработка алгоритмов планировани€ и приоритетного управлени€ доступом в сет€х WiMax: автореф. дис. ... канд. техн. наук. - ћ.: ћ»Ё“, 2010. - 25 с.
 рупский јлександр —ергеевич
јспирант каф. автоматизированных систем управлени€ “”—”–а
“ел.: 8-923-420-93-52
Ёл. почта: kas@asu.tusur.ru
Ѕойченко »ван ¬алентинович
 анд. техн. наук, доцент, докторант “”—”–а
“ел.: 8-906-958-24-83
Ёл. почта: biv@asu.tusur.ru
Krupskiy A.S., Boichenko I.V.
Fragmentation aware QoS scheduling algorithms in WiMax networks
The practical application of algorithms EDF and WFQ is reviewed in sphere of QoS scheduling. The differences in the practical application and in the ideal occasion of application is given. The method of grading of fragmentation overhead is represented.
Keywords: QoS, scheduling, fragmentation, overhead

пїњ