В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 55
Текст из файла (страница 55)
сколько линий, суммарная внутренняя нагрузка будет выше предложенной; Здесь: + у= суммарная нагрузка на всех линиях сети; + у>=нагрузканалинию>; + А = суммарное количество линий. Внутренняя нагрузка будет зависеть от фактического пути через сеть, по которому идут пакеты.
Мы будем предполагать, что используется такой алгоритм маршрутизации, при котором нагрузка на индивидуальные линии Л> может быть определена по предлагаемой нагрузке у>ь Для любой схемы маршрутизации мы можем по данным параметраи нагрузки определить среднее количество линий, по которым пройдет пакет.
Если неь>ногь> подумать, то становится очевидным, что среднюю длину всех путей можно найти при помощи формулы Е(количество линий в пути) = — . у Теперь наша задача заключается в том, чтобы определить величину средней задержки Тпрохождения пакета через сеть. Для этого можно воспользоваться формулой Литтла (см. табл. 8А в разделе 8.3). Для каждой линии сети среднее число ожидающих и обслуживаемых запросов равно > =Л>Тя.
Здесь Т„представляет собой задержку каждой очереди, которую еше предстоит определить. Предположим, что мы суммируем зти величины. Таким образом, мы получим среднее суммарное количество пакетов, ожидающих во всех очередях сети. Оказывается, что формула Литтла работает для множества очередей. Таким образом, число пакетов в сети, обслуживаемых и ожидающих обслуживания, может быть выражено как уТ. Объединив эти две формулы, получаем: т= '-ч:Л>т„. у= Чтобы найти значение У; нужно определить значения индивидуальных задержек Т„. Поскольку мы предполагаем, что каждая очередь может рассматриваться как независимая со схемой М/М>>1, это несложно вычислит>я Время обслуживания Т, для линии > представляет собой всего лип>ь отношениедли ие длины пакета в битах (М) к скорости передачи данных по втой линии в битах в секунду (К).
Таким образом, Ообраз все эти элементы вместе, мы можем сосчитать среднее время задержки цакетов, отправляемых по сети. 8.9. Другие модели очередей В этой главе мы расслютрели только модели очередей одного типа. В действительности суьцествует множество моделей, различающихся ключевыми факторами: + способом обработки блокированных запросов; + количеством источников трафика. Когда запрос прибывает на сервер и обнаруживает, что сервер я>нят, или поступает на устройство с несколькими серверами и находит, что все серверы заняты, тогда такой запрос называют блокированным (Иосиева). Блокированные запросы могут обрабатываться по-разному.
Во-первых, запрос может быть помещен в очередь и дожидаться, пака какой-либо сервер не освободится. В литературе, посвященной телефонному графику, такая политика называется отложенными неуспешными вызовами (1озг сайз >1е1ауед), хотя в действительности вти вызовы нельзя считать неуспешными. В качестве альтернативы запрос не ставится в очередь. Это, в свою очередь, приводит к принятию двух предположений о действиях запроса.
Запрос может ожидать в течение некоторого случайного интервала времени, а затем повторить попытку. Такая стратегия называется очииьеииыми неуснеи>ными вызовами (!оз1 са11з с1еагег1). Если запрос многократно без перерыва пытается по луч ить обслуживание, его относят к удерживаемым неуспешным вызоваи (1озг са!1з 1>е1б). Модель отложенных неуспешных вызовов более всего подходит для большинства компьютерных проблем н проблем передачи данных. Модель очищенных неуспешных вызовов, как правило, более всего подходит для системы коммутацпи телефонных каналов, Второй ключевой элемент модели трафиьса заключается в том, предполагается ли число источни>к>в конечным или бесконечным.
Для модели с бесконечным количеством источников частота поступления запросов считается фиксированной. Для модели с конечным количеством источников частота поступлеяия запросов будет зависеть от количества уже занятых источников. Таким образом, если каждый из А источников посылает запросы с частотой Л/с, тогда, если очередь свободна, то частота поступления запросов равна Л. Однако если запросы от К 250 Глава 8. Анализ очередей 8.10. Оценка параметров модели 251 источников определенное время находятся в очереди, тогда мгновенная частота поступления запросов в это время будет равна Ць' — Х)/г'..
С моделями с бесконечным количеством источников проще иметь дело. Допугцение о бесконечном количестве источников оправдано, когда количество источников по меныпей мере в 5 или в 10 раз превосхолит возможности системы. 8.10. Оценка параметров модели Для анализа очередей нужно оценить значения входных параметров, а именно среднее значение и среднеквадратичное отклонение частоты поступления запросов и времени обслуживания.
Если мы обдумываем новую систему, то, возможно, эти оценки должны быть основаны на анализе и оценке превалирующего оборудования и работающих образцов. Однако часто для исследования доступна существуюп1ая система. Например, у фирмы имеется множество терминалов, персональных компьютеров и хостов, соединенных при помощи прямых соединений и мультиплексоров. Желательно заменить все подобные соединительные устройства локальной сеп ю.
Чтобы оценить параметры проектируемой локальной сети, можно измерить текущую нагрузку, генерируемую каждым устройством. Выбор дискретных данных Замеры производятся в виде дискретных отсчетов. Отдельные параметры, например частота, с которой терминал генерирует пакеты, оцениваются путем наблюдения за количеством пакетов в течение определенного периода времени. Наиболее важной величиной, которую следует оценить, является среднее значение. Для многих формул из разделов 8А и 8.5 это единственная величина, которую нужно оценить.
Оценку среднего значения называют выборочным средним Х и вычисляют следующим образам: Х= — '~Х,. Фы, Здесь: + У вЂ” размер выборки; + Х, — г-й элемент выборки. Важно отметить, что выборочное среднее само является случайной переменной. Например, если вы производите выборку некоторой совокупности и вычисляете выборочное среднее, причем делаете это несколько раз, то полученные аначения будут различаться. Таким образом, мы можем говорить о среднем значении выборочного среднего и о его среднеквадратичном отклонении илн даже о распределении вероятностей выборочного среднего.
Чтобы не путать зти понятия, обьгчно распределениее вероя пюстей исходной случайной переменной Х называют основным рвснрвделением (нпдег1у(п8 сЬгпЪцг1оп), а распределение вероятностей выборочного срелнего Х вЂ” выборочным рвснределенивм (вашр11пй д)зтпЪць!оп) среднего значения.
Выборочное среднее значение обладает замечательным свойством, заключаю- щимся в том, что практически для всех основных Распределений при увеличении У распределение вероятностей выборочного среднего стремится к нормальному распределению. Предположение о нормальности этого распределения неверно только в том случае, если значение 1т'очень мало либо основное распределение в большой степени анормально. Среднее значение и дисперсия Х могут быть определены ~о следующим формулам: Е[Х]= Е[Х]=р; от ьгаг[ Х ] = — "- .
Ю Таким образом, если вычисляется выборочное среднее, его ожидаемая величина совпадает го средним значением лежицей в основе случайной переменной, а дисперсия выборочного среднего при увеличении гтг уменьшается. Эти характеристики иллюстрирует рис. 8.9. На графике изображено основное экспоненциальное распределение со средним значе~иетн р = 1, Это может быть распределение интервалов времени обслуживания сервера или распределение интервалов времени поступления запросов пуассоновского процесса.
Если для оценки значения р используется выоорка размера 1О, тогда ожидаемое значение равно р, но фактическое значение вполне может отличаться от ожидаемого на 50 М. Если размер выборки равен 100, тогда разброс значений существенно сужается, так что мы можем ожидать величину фактического выборочного среднего для любой заданной выборки гораздо ближе к р. Определенное ранее выборочное среднее может напрямую использоваться для оценки времени обслуживания сервера. Для определения частоты поступления можно наблюдать интервалы между поступлениями Аг запросов, сосчитать выборочное среднее, а затем вычислить оценку частотгы поступления.
Более простой способ определения частоты поступления запросов заключается в использовании следующей формулы: Х = —.' И Т' Здесь %представляет собой число поступивших запросов за период времени Т. В болынинстве случаев для анализа очередей достаточно определить оценку среднего значения. Но для некоторых важных уравнений также требуется оценка дисперсии, лежащей в основаниислучайной переменной ат .
Выборочная дисперсия вычисляется следующим образом: у= 1 ~ч (Х,-Х)'. А -1,ы Ожидаемое значение 5т обладает желаемой величиной Е[5 ] = ол. Дисперсия 5т зависит от основного распределения, и, как правило, ее трудно вычислить. Однако, кзк и следовало ожидать, дисперсия 5т уменыпаегся с увеличением Ф. 8 деькгвительности ато все тот же метод и та же форлгула, так как выоорочяое среднее для шнервл лов времени ностугглепггя вычисляется именно как Т/И. — ПРнкеч- нерее. 262 Глава 8. Анализ очередей 8.11. Рекомендуемые литература н веб-сайты 253 В табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
