The Buffer Memory Lock Influence on Throughput ofStar Network .pdf В задачах анализа и проектирования компьютерных сетей важнейшим объектом исследования является звездообразный сетевой фрагмент. Всесторонний анализ звездообразного топологического образования необходим при решении задач выбора пропускных способностей, распределения потоков, реализации алгоритмов маршрутизации, разработке методов управления информационными потоками и ресурсами буферной памяти транзитных узлов передачи данных. Математические модели такой структурной конфигурации позволяют изучать пропускную способность входящих и исходящих каналов связи центрального узла коммутации с ограниченной памятью, проводить расчет емкости и оптимизацию структуры его буферного накопителя (схемы использования конечной буферной памяти для хранения очередей пакетов к выходным каналам связи) [1, 2]. Кроме того, здесь возможен анализ различных схем локального управления транзитными потоками. Одним из основных факторов, определяющих операционные характеристики сетевых структур, являются блокировки ограниченной буферной памяти узлов коммутации (на втором уровне сетевой архитектуры) и узлов маршрутизации (на третьем уровне). Основная задача исследования звездообразной конфигурации состоит в выборе наилучшей в смысле некоторого критерия (обычно вероятности блокировки или пропускной способности данного структурного образования) схемы распределения ограниченной буферной памяти центрального узла между очередями пакетов к выходным каналам связи [2]. Простейшей схемой является полное разделение буферной памяти между каналами связи (фиксированное разбиение). Согласно этой схеме, каждому выходному направлению предоставлется отдельный буферный пул. Причем сумма размеров индивидуальных пулов равна общему обьему буферной памяти узла коммутации. Противоположная данной схеме - полнодоступная стратегия, в соответствии с которой очередь к каждому из каналов связи может занимать всю имеющуюся буферную память (равнодоступная стратегия). Существует ряд промежуточных стратегий разделения памяти, наиболее общей среди которых является неполнодоступная схема с индивидуальными потолками [2]. В данной схеме каждому каналу связи выделено определенное количество индивидуальных буферов. Кроме того, имеется пул буферов, общих для всех каналов, некоторую часть которых (индивидуальную для каждого канала) может занимать очередь к конкретному выходному направлению. Основным инструментом моделирования звездообразной конфигурации являются системы массового обслуживания с ограниченным накопителем, позволяющие анализировать влияние на функционирование элементов топологической структуры ближайшего сетевого окружения.1. Дискретная модель фрагмента сети с расщеплением трафикаРассмотрим звездообразый фрагмент сети, включающий M+1 звено передачи данных, в котором в центральный транзитный узел по одному входящему каналу связи поступает информационный поток и распределяется по M исходящим каналам связи. Предположим, что в узле-отправителе входящего канала всегда имеются пакеты для передачи в центральный транзитный узел. Пусть обмен в каждом звене выполняется полными кадрами и организован в соответствии со старт-стопным протоколом [2], согласно которому кадр считается принятым узлом-приемником, если в нем не обнаружены ошибки. При искажении информационного кадра или квитанции, подтверждающей правильность приема кадра получателем, происходит повторная передача. Предположим, что входному каналу связи выделен специальный буфер для приема кадра и анализа его на наличие ошибок. В случае корректного приема кадра, содержащийся в нем пакет переписывается в свободный буфер буферного пула выходного канала связи или (что эквивалентно) занимает данный буфер, а в качестве специального выделяется другой из того же буферного пула. При отсутствии свободных буферов в пуле выходного канала связи кадр, так же, как и при искажении, передается повторно. Такая техника гарантированного обеспечения каждого входного направления буфером для приема кадра широко используется для предупреждения «прямых» блокировок пути [2]. Полагаем, что все каналы связи имеют одинаковые физические скорости передачи данных, а узлы-отправители и узлы-получатели - одинаковое время обработки кадров при приеме и отправке. Тогда время полного цикла передачи кадра t будет одинаковым для всех звеньев рассматриваемого фрагмента. Будем считать кроме того, что кадр, поступивший в транзитный узел в текущем цикле t, начнет передаваться по выходному каналу только в следующем цикле. Полагаем также, что безошибочная передача кадра данных во входящем канале определяется вероятностью F, а в исходящих каналах - вероятностями Fm, m = 1, M . Считаем также, что весь входящий в транзитный узел поток кадров одного канала распределяетсяMв m-й выходной канал с вероятностью Bm, £ Bm = 1. Величины Bm определяютструктуру расщепления трафика, и их можно интерпретировать как доли входящего потока, направляемые в m-й выходной канал. Нетрудно видеть, что время безошибочной передачи кадра по каждому межузловому соединению является случайной величиной, кратной t. Если условия первой и повторных передач одинаковы, что, как правило, выполняется в сетях пакетной коммутации, то данная величина имеет геометрический закон распределения с параметром F во входя-щем канале и Fm, m = 1, M, - в исходящих каналах связи. Будем считать также,что для хранения пакетов в выходных очередях в транзитном узле выделен пул совместно используемой буферной памяти объема К. Размер очереди qm к каждому выходному каналу m ограничен предельной величиной Nm < K, определяемой стратегией распределения буферной памяти между выходными каналами. Для каждого входящего пакета, направляемого в конкретный исходящий канал, выделяется буфер при условии, что выходная очередь qm данного направления непревышает максимального размера qm < Nm и, кроме того, для очередей к выход-Mным каналам связи выполняется ограничение У 4m < K , соответствующее тому,что пул свободных буферов для хранения пакетов данных не пуст. Очевидно, что в каждом конкретном случае распределения пула буферов между выходными направлениями размер очереди к m-му каналу qm не превышает величины Qm,Mудовлетворяющей условиям: Qm < Nm и £ Qm = K . В общем случае различаюттри стратегии распределения буферной памяти между выходными каналами связи - равнодоступную Nm = K, фиксированное разбиение Nm = K / M (для однородных выходных каналов связи), промежуточную политикуmK / M < Nm < K, Qm = K . Основной вопрос, который приходится решать архитекторам коммуникационных систем и сетей, состоит в том как распределить совместно используемое буферное пространство для хранения очередей транзитных пакетов данных между выходными каналами связи. Поведение рассматриваемого сетевого фрагмента представимо в виде марковской системы массового обслуживания (СМО) с дискретным временем, конечным накопителем и M обслуживающими приборами [3]. Входящий поток определяется качеством входящего канала F, а время обслуживания на каждом приборе СМО - качеством m-го исходящего канала Fm . Распределение поступающих заявок СМО по M обслуживающим приборам задается вероятностями Bm, m = 1, M . Динамика очередей к выходным каналам связи данной СМО в стационарных условиях описывается цепью Маркова в M-мерном пространстве. Множество возможных состояний цепи Маркова по каждому измерению определяется политикой распределения буферной памяти между исходящими каналами и не превышает величины Nm +1.Для дискретной цепи Маркова с конечным числом состояний, описывающей рассматриваемую СМО в установившемся режиме, определим с учетом введенных предположений переходные вероятности пJ из состояния I в состояние J, гдеI = 1Х, i2iM ; J = J\, J2Jm ; im = °> Nm ; Jm = °' Nm ; m = Ъ M , - М-разрядныеномера соответственно исходного и измененного состояний с областью значений каждого разряда от 0 до Nm . Обозначим через ^ ,im = 0,Qm,m = 1,M , вероятности состояний М-мерной цепи Маркова. Важнейшей характеристикой СМО ограниченной емкости является пропускная способность. В рассматриваемомслучае этот показатель интерпретируется как пропускная способность входящего звена передачи данных, нормированное значение которого определяется величиной пропущенного (обслуженного) потока:MQ Qm Qm+1 QMZ(F,Fi,...,FM,Bl,...,BM) = X Fm X ... X X ... X pд.m=1=0 im =1 im +1 =0 !m =0(1)Кроме данного интегрального показателя можно ввести также дифференцированные индексы пропущенных потоков по каждому из М исходящих направлений:Ol Qm Qm+1 Qm Zm(F,Fi,...,FM,Bi,...,BM) = Fm £ ... £ £ ... £ P1jWm ,m = 1,M .2. Модель равнодоступной стратегииНайдем функциональную зависимость вероятностей состояний СМО в стационарных условиях и индексов производительности от параметров рассматриваемого фрагмента сети. Начнем рассмотрение с простейшего случая, когда между М выходными каналами разделяется единственный буфер транзитного узла(K=1). Переходные вероятности л/ в этом случае имеют видFn FBm ,J == 1,0,..., 0; I = 0,..,0;m =1, M; J =U- Jm z= 1,0,..., 0; I = 0,in = 1,0,..., 0;m =1, M; n =1, M; m Ф n;

Скачать электронную версию публикации