5-2_Очереди_и_их_свойтсва (1130316)

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

Текст из файла

Коммутация пакетов: модели сочередямиВведение в компьютерные сетипроф. Смелянский Р.Л.Лаборатория Вычислительных комплексовф-т ВМК МГУСодержание• Простая модель с детерминированной очередью• Сокращение е2е задержки за счет сокращениядлины пакета• Статистическое мультиплексированиеВведение в компьютерные сетипроф.Смелянский Р.Л.2Простая модель очереди маршрутизатораВведение в компьютерные сетипроф.Смелянский Р.Л.3Простая модель очереди маршрутизатораочередьмаршрутизатораСвойстваСвойстваВведение в компьютерные сетипроф.Смелянский Р.Л.невозрастающиеНеубывающиефункции4Простая модель очередиСуммарное число байт поступившихк моменту времени tПропускнаяспособностьканала (Link rate)Суммарное число байтотправленных к моментувремени tВведение в компьютерные сетипроф.Смелянский Р.Л.5Общее число байт,поступивших к моменту t.A(t)Q(t)R LinkrateD(t)Общее число байт,отправленных к моменту t.Введение в компьютерные сетипроф.Смелянский Р.Л.Общее число байтПростая модель очередиA(t)D(t)RвремяСвойства A(t), D(t):- A(t), D(t) неубывающие- A(t) >= D(t)6Простая модель очередиЗадержка в очереди d(t) – время, которое байт, поступивший в момент t,пробыл в очереди, при условии что дисциплина очереди FIFO.Введение в компьютерные сетипроф.Смелянский Р.Л.7Простая модель очереди: пример (а)Q(t)Каждую секунду в очередь поступает 50пакет в 100 бит на скорости 1 000 б/с.Максимальная скорость отправки – 500 б/с.Какова средняя длина очереди?250.1 0.21.0Решение: на каждой секунде очередь заполняется со скоростью 100 б за 0.1 с.За следующие 0.1 с очередь освобождается со скоростью 500 б/с.За первые 0.1 с поступит 100 б и уйдет 50 б, останется 50 б.на второй 0.1 с поступит 0 б, уйдет 50 б, останется 0 б.за последующие 0.8 с ничего не поступит и ничего не уйдетследовательно среднее: (50+0)/2 + 0.8х0= 25 бВведение в компьютерные сетипроф.Смелянский Р.Л.9Суммарное число бит• (b) Какое время в среднем бит находится вочереди?100d(t)0.1A(t)d(t)0.05D(t)0.1s0.2s1.0sвремя0.11.0Задержка бита в среднем = 0.05сВведение в компьютерные сетипроф.Смелянский Р.Л.10(с) Если пакеты в 100 бит будут поступать черезслучайные интервалы времени, то посравнению со случаем равномерногопоступления таких пакетов средняя длинаочереди будет такой же, короче или длиннее?Длиннее.

Когда пакеты поступаютрегулярно, как в случае (a), их биты никогдане находятся в очереди одновременно (непересекаются). При случайном поступленииможет оказаться так, что в очереди будутнаходится одновременно биты разныхпакетов, увеличивая тем самым как времянахождения в очереди, так и длину самойочереди в среднем.Введение в компьютерные сетипроф.Смелянский Р.Л.11Случай с: Наложения пакетов увеличат среднюю длину очереди.Q(t)10050250.1 0.20.42Средняя длина очереди = (1/2с) * ( (0.4с * 50б) + (1.6с * 0б) )= 10 битВведение в компьютерные сетипроф.Смелянский Р.Л.12Коммутация пакетов: почему много мелкихпакетов лучше одного большогоp/r1M/r1R1R1R2R2R3R3Разбиение сообщения на пакеты позволяет передавать их параллельно по всем линиям,сокращая е2е задержку.Введение в компьютерные сетипроф.Смелянский Р.Л.13Коммутация пакетов: статистическоемультиплексированиеПакеты на один итот же выходДлина очереди• Поскольку буфер сглаживает временные всплески(короткие периоды, когда скорость превышает R), то навыходе канал может работать с меньшей скоростью, чемNхR• Поскольку размер буфера ограничен B, то возникнутпотери.Введение в компьютерные сетипроф.Смелянский Р.Л.14Коммутация пакетов: статистическоемультиплексированиеВведение в компьютерные сетипроф.Смелянский Р.Л.15Коммутация пакетов: статистическоемультиплексированиеСкоростьACACBCВремяСкоростьBCВремяВведение в компьютерные сетипроф.Смелянский Р.Л.1616Коммутация пакетов: статистическоемультиплексированиеСкоростьA+B2CR < 2CARBВремяВыигрыш от статистического мультиплексирования = 2C/RВведение в компьютерные сетипроф.Смелянский Р.Л.1717Коммутация пакетов: простая модель сочередями• Для понимания динамики пакетов в сети вполнеподходит простая детерминированная модель.• Разбиение сообщения на пакеты позволяет нампараллельно передавать несколько пакетов,сокращая е2е задержку.• Статистическое мультиплексирование позволяетпередавать несколько потоков через один и тот жеканалВведение в компьютерные сетипроф.Смелянский Р.Л.18Свойства очередейВведение в компьютерные сетипроф.

Смелянский Р.Л.Лаборатория Вычислительных комплексовф-т ВМК МГУОчереди со случайным процессомпоступления• Обычно процесс поступления пакетов сложен итрудно предсказуем Поэтому его частомоделируют случайным процессом.• Изучает очереди с такими процессами ТеорияОчередей (Queuing Theory – теория массовогообслуживания).• Здесь мы рассмотрим некоторые свойства такихочередей.Введение в компьютерные сетипроф.Смелянский Р.Л.20Эволюция очереди со временемПоступлениепакетовОтправкипакетовtimeRQ(t)Введение в компьютерные сетипроф.Смелянский Р.Л.22Свойства очередей: нерегулярностьувеличивает задержкуПериодические одиночные поступленияПоступлениепакетовОтправкипакетовВведение в компьютерные сетипроф.Смелянский Р.Л.23Свойство 1 очередей: нерегулярностьувеличивает задержкуПериодические множественные поступленияПоступлениепакетовОтправкипакетовВведение в компьютерные сетипроф.Смелянский Р.Л.24Свойство 2 очередей: случайностьувеличивает задержкуСлучайное поступленияПоступлениепакетовОтправкипакетовПри случайном поступлении пакетов в среднем в очередиприходиться ждать дольше, чем при регулярномВведение в компьютерные сетипроф.Смелянский Р.Л.25Свойство 3: Формула ЛиттлаL - среднее число заявок в системе (в очереди + в обслуживании)λ – средняя скорость поступления заявок в секундуd – средне время пребывания заявки в системе (в очереди + в обслуживании, т.е.

задержка)Это свойство верно если ни одна заявка не теряется/сбрасываетсяВведение в компьютерные сетипроф.Смелянский Р.Л.26Пуассоновский процесс• Процесс поступления является Пуассоновским если:o Вероятность поступления k заявок за t секунд − () =!o Интервалы между последовательными поступленияминезависимы (нет регулярности)• Тогда число заявок поступивших за время tСвойство 4E = λt• Пуассоновские процессы хорошо моделируют многиеслучайные процессы (телефонные звонки, распад частиц,шумы в электрических цепях и т.д.)• Удобный математический аппаратВведение в компьютерные сетипроф.Смелянский Р.Л.27Пуассоновский процесс• Сетевой трафик очень не регулярный• Поступление пакетов не является Пуассоновским процессом• Вполне подходит для моделирования поступления новыхпотоковВведение в компьютерные сетипроф.Смелянский Р.Л.28Простая модель очередиПуассонВведение в компьютерные сетипроф.Смелянский Р.Л.Экспоненциальный29Модель очереди в маршрутизатореПоступлениепакетовОтправкипакетовВведение в компьютерные сетипроф.Смелянский Р.Л.30Свойства очередей• Свойства очередей:o Нерегулярность увеличивает задержкуo Формула Литтла: L = λd• Поступление пакетов не Пуассоновский процесс,но такие процессы как поступление web запросов,новых потоков, могут быть описаны какПуассоновские процессы• М/М/1– простая модель очередиВведение в компьютерные сетипроф.Смелянский Р.Л.31.

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

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