5 (1130536), страница 2
Текст из файла (страница 2)
при случайном поступлении в среднем приходиться ждатьдольше, чем при регулярномКомпьютерные сетипроф.Смелянский Р.Л.10.03.20147Свойство 3: Формула ЛиттлаL - среднее число заявок в системе (в очереди + в обслуживании)λ – средняя скорость поступления заявок в секундуd – средне время пребывания заявки в системе (в очереди + в обслуживании, т.е. задержка)Это свойство верно если ни одна заявка не теряется/сбрасываетсяКомпьютерные сетипроф.Смелянский Р.Л.10.03.20148Пуассоновский процесс• Процесс поступления является Пуассоновским если:o Вероятность поступления k заявок за t секунд − () =!o Интервалы между последовательными поступленияминезависимы (нет регулярности)• Тогда число заявок поступивших за время tСвойство 4E = λt• Пуассоновские процессы хорошо моделируют многиеслучайные процессы (телефонные звонки, распад частиц,шумы в электрических цепях и т.д.)• Удобный математический аппаратКомпьютерные сетипроф.Смелянский Р.Л.10.03.20149Пуассоновский процесс• Сетевой трафик очень не регулярный• Поступление пакетов не является Пуассоновским процессом• Вполне подходит для моделирования поступления новыхпотоковКомпьютерные сетипроф.Смелянский Р.Л.10.03.201410М/М/1 очередьПуассонКомпьютерные сетипроф.Смелянский Р.Л.Экспоненциальный10.03.201411Свойства очередейПоступлениепакетовОтправкипакетовКомпьютерные сетипроф.Смелянский Р.Л.10.03.201412Свойства очередей• Свойства очередей:o Нерегулярность увеличивает задержкуo Формула Литтла: L = λd• Поступление пакетов не Пуассоновский процесс,но такие процессы как поступление web запросов,новых потоков, могут быть описаны какПуассоновские процессы• М/М/1– простая модель очередиКомпьютерные сетипроф.Смелянский Р.Л.10.03.201413Коммутация пакетов: как работаетпакетный коммутаторКомпьютерные сетипроф.
Смелянский Р.Л.Лаборатория Вычислительных комплексовф-т ВМК МГУСодержание• Как выглядит пакетный коммутатор• Что делает пакетный коммутатор:o Ethernet switcho Internet router• Как устроен поиск адресов в:o Ethernet switcho Internet router• Виды буферизации в коммутаторахКомпьютерные сетипроф.Смелянский Р.Л.10.03.20142Пакетный коммутаторDataHLookupAddressUpdateHeaderQueuePacketDestinationEgress linkAddressForwardingTableКомпьютерные сетипроф.Смелянский Р.Л.BufferMemory10.03.20143Пакетный коммутаторDataHLookupAddressUpdateHeaderBufferMemoryForwardingTableDataHLookupAddressUpdateHeaderHLookupAddressForwardingTableКомпьютерные сетипроф.Смелянский Р.Л.QueuePacketBufferMemoryForwardingTableDataQueuePacketUpdateHeaderQueuePacketBufferMemory10.03.20144Ethernet коммутатор1.
Проверяет заголовок каждого прибывающегокадра2. Если адрес DA есть в таблице коммутации, то кадрпередают на надлежащий выходной порт3. Если адрес DA нет в таблице, кадр рассылается повсем портам, кроме того на который пришел.4. Когда придет ответ на разосланный пакет, то поего адресу отправителя мы узнаем , куда надонаправлять пакеты с такими адресамиполучателей.Компьютерные сетипроф.Смелянский Р.Л.10.03.20147Интернет маршрутизатор1.2.3.4.5.6.7.Если Ethernet DA поступившего кадра есть Ethernet адресмаршрутизатора, то принять кадр, иначе сбросить его.Просмотреть поля IP version и длина дейтаграммыСократить поле TTL, пересчитать контрольную сумму IPзаголовкаПроверить TTL на 0Если IP DA есть в таблице маршрутизации, переслать нанадлежащий выходной порт для следующего скачка (hop)Найти Ethernet DA для следующего маршрутизатораПостроить новый Ethernet кадр и отправить егоКомпьютерные сетипроф.Смелянский Р.Л.10.03.20148Базовые операции коммутатора1.
Поиск адреса: как адрес ищется в таблицемаршрутизации?2. Коммутация: как пакет пересылают нанадлежащий выходной порт?Компьютерные сетипроф.Смелянский Р.Л.10.03.20149Поиск адреса: EthernetТаблица Ethernet адресовEthernet DAДействие0xA8B72340E678Передать на порт 70xB3D22571053BПередать на порт 3…….…..Адреса хранятся в хэш-таблицеИщем в хэш-таблице точное совпадениеКомпьютерные сетипроф.Смелянский Р.Л.10.03.201410Поиск адреса: IPТаблица IP адресов в маршрутизатореIP DAДействие127.43.57.99Передать на 56.99.32.16123.66.44.xПередать на 22.45.21.12676.9.x.xПередать на 56ю99ю32ю16…….…..Ищут совпадение по самому длинному префиксу,а не точное совпадение.Компьютерные сетипроф.Смелянский Р.Л.10.03.201411Поиск совпадения по самому длинномупрефиксуКомпьютерные сетипроф.Смелянский Р.Л.10.03.201412Поиск совпадения самого длинногопрефиксаКомпьютерные сетипроф.Смелянский Р.Л.10.03.201413Поиск совпадения самого длинногопрефикса (ТСАМ - Ternary Content Addressable Mamory)Компьютерные сетипроф.Смелянский Р.Л.10.03.201414Поиск адреса< Совпадение, Действие>СовпадениеДействиеIP DA = XПередать на порт 7EthDA=Y & IP DA = ZСброс пакетаОбобщение поиска и коммутации в коммутаторах,маршрутизаторах и т.п.Компьютерные сетипроф.Смелянский Р.Л.10.03.201415Как работает коммутатор: заключение• Пакетный коммутатор выполняет две базовыеоперации:o Поиск адресов в таблице коммутацииo Передача на надлежащий выходной порт• По сути, Ethernet коммутаторы и маршрутизаторывыполняют одинаковые действия• Поиск адреса в коммутаторе и маршрутизаторепроисходить по-разному.Компьютерные сетипроф.Смелянский Р.Л.10.03.201416Содержание• Буферизация на выходе и разделяемая память• Буферизация на входе и блокировки на линии• Виртуальная буферизация на входе:Компьютерные сетипроф.Смелянский Р.Л.10.03.201417Блокировки на входной линииКомпьютерные сетипроф.Смелянский Р.Л.10.03.201420Виртуальные выходные очередиКомпьютерные сетипроф.Смелянский Р.Л.10.03.201421Буферизация на выходеDataHLookupAddressUpdateHeaderBufferMemoryForwardingTableDataHLookupAddressUpdateHeaderHLookupAddressForwardingTableКомпьютерные сетипроф.Смелянский Р.Л.QueuePacketBufferMemoryForwardingTableDataQueuePacketUpdateHeaderQueuePacketBufferMemory10.03.201422Буферизация на входеDataHLookupAddressUpdateHeaderForwardingTableDataBufferMemoryHLookupAddressUpdateHeaderForwardingTableDataHLookupAddressForwardingTableКомпьютерные сетипроф.Смелянский Р.Л.QueuePacketQueuePacketBufferMemoryUpdateHeaderQueuePacketBufferMemory10.03.201423Блокировка на входеКомпьютерные сетипроф.Смелянский Р.Л.10.03.201424Виртуальные очереди на выходеКомпьютерные сетипроф.Смелянский Р.Л.10.03.201425Пакетный коммутатор с буферизациейна выходеКомпьютерные сетипроф.Смелянский Р.Л.10.03.201426Свойства OQ коммутатора1.
Работают с минимальными потерями2. Максимальная пропускная способность3. Ожидаемая задержка минимальнаКомпьютерные сетипроф.Смелянский Р.Л.10.03.201427Пакетный коммутатор с буферизациейна входеБлокировки на входеOQ ком-торКомпьютерные сетипроф.Смелянский Р.Л.10.03.201428Пакетный коммутатор с буферизацией на входе(с виртуальными очередями на выходе)OQ ком-торКомпьютерные сетипроф.Смелянский Р.Л.10.03.201429Компьютерные сетипроф.Смелянский Р.Л.10.03.2014301. Пакетный коммутатор: заключение• Пакетный коммутатор выполняет две базовыеоперации:o Поиск соответствия в таблице коммутацииo Передачу на надлежащий выходной порт• Самый простой и самый медленный коммутаториспользует буферизацию на выходе сминимальной задержкой пакета• Высокоскоростные коммутаторы используютбуферизацию на входе с виртуальными очередямина выходах для увеличения пропускнойспособности.Компьютерные сетипроф.Смелянский Р.Л.10.03.201431Коммутация пакетов: приоритеты игарантированная скорость потокаКомпьютерные сетипроф.
Смелянский Р.Л.Лаборатория Вычислительных комплексовф-т ВМК МГУПакетный коммутатор с буферизациейна выходеDataHLookupAddressUpdateHeaderBufferMemoryForwardingTableDataHLookupAddressUpdateHeaderHLookupAddressForwardingTableКомпьютерные сетипроф.Смелянский Р.Л.QueuePacketBufferMemoryForwardingTableDataQueuePacketUpdateHeaderQueuePacketBufferMemory10.03.20143Пакетный коммутатор: FIFO• Как можно обеспечить строгие приоритеты?• Как регулировать качество сервиса (скорость)?Компьютерные сетипроф.Смелянский Р.Л.10.03.20144Пакетный коммутатор: строгиеприоритетыКомпьютерные сетипроф.Смелянский Р.Л.10.03.20145Пакетный коммутатор: приоритеты свесамиКомпьютерные сетипроф.Смелянский Р.Л.10.03.20146Пакетный коммутатор: приоритеты свесамиКомпьютерные сетипроф.Смелянский Р.Л.10.03.20147Пакетный коммутатор: чтобы хотелосьКомпьютерные сетипроф.Смелянский Р.Л.10.03.20148Пакетный коммутатор: как на практикеКомпьютерные сетипроф.Смелянский Р.Л.10.03.20149Заключение• FIFO очередь – нет приоритетов, не гарантированаскорость• Строгие приоритеты: высокоприоритетный трафик«не видит» низкоприоритетного трафика в сети.Полезно, когда высокоприоритетного трафикаограниченное количество• Waited Fair Queuing (WFQ) позволяет каждомупотоку обеспечить гарантированный сервис,планируя их в порядке bit-by-bit finishing timeКомпьютерные сетипроф.Смелянский Р.Л.10.03.201411Коммутация пакетов: гарантированнаязадержкаКомпьютерные сетипроф.
Смелянский Р.Л.Лаборатория Вычислительных комплексовф-т ВМК МГУФакторы влияющие на задержкуAl1, r1l2, r2Q1(t)l3, r3Q2(t)l4, r4BQ3(t) p lie2e задержка, Qi t ci riЕсли мы знаем верхние границы Q1(t), Q2(t) and Q3(t), то мы знаемверхнюю границу для е2е задержки.Компьютерные сетипроф.Смелянский Р.Л.10.03.2014 2Пакетный коммутатор: гарантированнаязадержкаКомпьютерные сетипроф.Смелянский Р.Л.10.03.20144Пакетный коммутатор: управлениезадержкой пакетаМы знаем уже как управлять1.
Скоростью обслуживания очереди (WFQ)2. Длиной каждой очередиКак можно было бы гарантировать,что ни один пакет не будет сброшен ?Компьютерные сетипроф.Смелянский Р.Л.10.03.20145Пакетный коммутатор: zoom однойочередиКомпьютерные сетипроф.Смелянский Р.Л.10.03.20146Пакетный коммутатор: zoom однойочередиОбщеечислобайтКомпьютерные сетипроф.Смелянский Р.Л.Поскольку мы неможем управлятьпроцессомпоступления,давайте егоограничим.10.03.20147Ограничение трафикаОбщеечислобайтЧисло бит, которые могутпоступить за период t,ограничено величиной σ+ρtВ нашем примереσ = B, ρ = 1Компьютерные сетипроф.Смелянский Р.Л.10.03.20148(σ,ρ) ограничение поступления иминимальная скорость обслуживанияОбщеечислобайтЕсли нет потерипакетов, B ≥ σ.Если 1 ≥ ρ, тоd(t) ≤ B/ 1Если поток ограничен текущим буфером и маршрутизатор используетдисциплину обслуживания WFQ, то можно гарантировать е2е задержку.Компьютерные сетипроф.Смелянский Р.Л.10.03.20149Пакетный коммутатор: текущий буфер (идея)Сети ЭВМпроф.
Смелянский Р.Л.10 марта 2014 г.10Примеры формирования нагрузкиСети ЭВМпроф. Смелянский Р.Л.10 марта 2014 г.11Текущий буфер с маркерамиСети ЭВМпроф. Смелянский Р.Л.10 марта 2014 г.12Текущий буфер с маркерами• ОбозначимS - длительность временного увеличения трафика навходе; - скорость поступления маркеров Б/с;M - максимальная скорость входного трафика Б/с;C - емкость корзины в байтах.ТогдаC + S = MS.Откуда получаем, чтоS= C/(M - ).Сети ЭВМпроф. Смелянский Р.Л.10 марта 2014 г.13Трафик для M = 25MB/sec,ЗдесьM =и25MB/sec, = 2MB/sec и C = 250,500750 KB соответственно. = 2MB/sec и C = 250, 500 и 750 KB соответственноСети ЭВМпроф.
Смелянский Р.Л.10 марта 2014 г.14Пакетный коммутатор: задержкаТекущийТекущийбуфербуферКомпьютерные сетипроф.Смелянский Р.Л.10.03.201415Пакетный коммутатор: примерДля приведенного фрагмента сети приложению требуется скоростьв 10 Mb/с и е2е задержка не более 5 mс при пакетах в 1 000 байтКомпьютерные сетипроф.Смелянский Р.Л.10.03.201416Пакетный коммутатор: примерДля приведенного фрагмента сети приложению требуется скоростьв 10 Mb/с и е2е задержка не более 5 mс при пакетах в 1 000 байтНесмотря на то, что технически это возможно, лишь некоторыесети могут управлять е2е задержкой.Причины:• Слишком сложно и хлопотно• В большинстве сетей комбинация прогнозирования и• приоритетов дает вполне приемлемые результаты.Компьютерные сетипроф.Смелянский Р.Л.10.03.201417Заключение• Если мы знаем длину очереди и дисциплину ееобслуживания, то мы можем ограничить величинузадержки в ней.• Выбрав длину очереди, и, используя WFQ, мыможем определить скорость обслуживания.• Поэтому самое главное не допустить сбросапакетов.
Для этого можно использовать текущийбуфер.• Таким образом, мы можем ограничить величинуе2е задержки.Компьютерные сетипроф.Смелянский Р.Л.10.03.201418.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
