4-3 Простая модель очереди (Лекции 2014 года)

Коммутация пакетов: модели сочередямиКомпьютерные сетипроф. Смелянский Р.Л.Лаборатория Вычислительных комплексовф-т ВМК МГУСодержание• Простая модель с детерминированной очередью• Сокращение е2е задержки за счет сокращениядлины пакета• Статистическое мультиплексированиеКомпьютерные сетипроф.Смелянский Р.Л.10.03.20142Простая модель очередимаршрутизатораКомпьютерные сетипроф.Смелянский Р.Л.10.03.20143Простая модель очереди маршрутизатораочередьмаршрутизатораСвойстваНеубывающие функцииКомпьютерные сетипроф.Смелянский Р.Л.10.03.20144Простая модель очередиСуммарное число байт поступившихк моменту времени tПропускнаяспособностьканала (Link rate)Суммарное число байтотправленных к моментувремени tКомпьютерные сетипроф.Смелянский Р.Л.10.03.20145Общее число байт,поступивших к моменту 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)10.03.20146Простая модель очередиЗадержка в очереди d(t) – время, которое байт, поступивший в момент t,пробыл в очереди, при условии что дисциплина очереди FIFO.Компьютерные сетипроф.Смелянский Р.Л.10.03.20147Простая модель очередиСуммарное число байт(cumulative number)поступивших к моментувремени tСуммарное число байт(cumulative number)отправленных к моментувремени tКомпьютерные сетипроф.Смелянский Р.Л.Свойства функций A(t), D(t):• A(t), D(t) – неубывающие• A(t) ≥ D(t)10.03.20148Простая модель очереди: примерКаждую секунду в очередь поступаетПакет в 100 бит на скорости 1 000 б/с.Максимальная скорость отправки – 500 б/с.Какова средняя длина очереди?Решение: на каждой секунде очередь заполняется со скоростью 500 б/с за 0.1 с.За следующие 0.1 с очередь освобождается со скоростью 500 б/с.На первых 0.2 с средняя длина очереди будет 0.5х(0.1х500) = 25 бит.В течении последующих 0.8 с очередь будет пуста.

Поэтому средняя длина очереди = (0.2 x 25) + (0.8X0) = 5Компьютерные сетипроф.Смелянский Р.Л.10.03.20149Коммутация пакетов: почему много мелкихпакетов лучше одного большогоp/r1M/r1R1R1R2R2R3R3Разбиение сообщения на пакеты позволяет передавать их параллельно по всем линиям,сокращая е2е задержку.Компьютерные сетипроф.Смелянский Р.Л.10.03.201410Коммутация пакетов: статистическоемультиплексированиеПакеты на один итот же выходДлина очереди• Поскольку буфер сглаживает временные всплески(короткие периоды, когда скорость превышает R), то навыходе канал может работать с меньшей скоростью, чемNхR• Поскольку размер буфера ограничен B, то возникнутпотери.Компьютерные сетипроф.Смелянский Р.Л.10.03.201411Коммутация пакетов: статистическоемультиплексированиеКомпьютерные сетипроф.Смелянский Р.Л.10.03.201412Коммутация пакетов: статистическоемультиплексированиеСкоростьACACBCВремяСкоростьBCВремяКомпьютерные сетипроф.Смелянский Р.Л.10.03.201415Коммутация пакетов: статистическоемультиплексированиеСкоростьA+B2CR < 2CARBВремяВыигрыш от статистического мультиплексирования = 2C/RКомпьютерные сетипроф.Смелянский Р.Л.10.03.201416Коммутация пакетов: простая модель сочередями• Для понимания динамики пакетов в сети вполнеподходит простая детерминированная модель.• Разбиение сообщения на пакеты позволяет нампараллельно передавать несколько пакетов,сокращая е2е задержку.• Статистическое мультиплексирование позволяетпередавать несколько потоков через один и тот жеканалКомпьютерные сетипроф.Смелянский Р.Л.10.03.201417.