Автоматика и телемеханика, № 10, 2014
© 2014 г. П.А. МИХЕЕВ, канд. техн. наук (doka.patrick@gmail.com) (Томский государственный университет)
АНАЛИЗ СТРАТЕГИЙ РАЗДЕЛЕНИЯ КОНЕЧНОЙ БУФЕРНОЙ ПАМЯТИ МАРШРУТИЗАТОРА МЕЖДУ ВЫХОДНЫМИ КАНАЛАМИ
Предложена модель транзитного узла сети передачи данных, распределяющего входящий поток по нескольким исходящим направлениям. Исследуются влияние качества каналов связи, распределения долей входящего трафика по исходящим направлениям и стратегий разделения ограниченной буферной памяти транзитного узла между очередями к выходным каналам связи на пропускную способность сетевого фрагмента с различными по быстродействию входящим и исходящими интерфейсами.
1. Введение
В задачах анализа и проектирования компьютерных сетей важнейшим объектом исследования является звездообразный сетевой фрагмент. Одним из основных факторов, определяющих операционные характеристики сетевых структур, являются блокировки ограниченной буферной памяти узлов коммутации (на втором уровне сетевой архитектуры) [1] и узлов маршрутизации (на третьем уровне) [2]. Пропускная способность сетевого фрагмента во многом определяется емкостью буферной памяти транзитного узла, а при распределении входящего в транзитный узел трафика по выходным направлениям объем пропущенного потока в значительной мере зависит от стратегии разделения ограниченной буферной памяти между выходными интерфейсами. Основной вопрос, который приходится решать архитекторам коммуникационных систем и сетей, состоит в том, как разделить совместно используемое буферное пространство для хранения очередей транзитных пакетов данных между выходными каналами связи [3-6]. Одно из первых исследований задачи разделения буферной памяти между выходными каналами выполнено в [7]. Классификация различных схем разделения буферной памяти впервые была предложена в [8]. Систематическое изложение вопросов анализа звездообразного фрагмента сети и обширный обзор полученных в этом направлении результатов выполнен в [9]. Обсуждение, анализ и моделирование предложенных стратегий системами массового обслуживания (СМО) с конечным накопителем и непрерывным временем изложено в [3, 7-12]. Поскольку функционирование компьютерных сетей носит существенно дискретный характер [13-15], в [16, 17] предложено исследование влияния блокировок буферной памяти на быстродействие сетевых фрагментов с помощью СМО с конечным накопителем и дискретным временем. Развитие этих результатов получило в [18], где в терминах СМО с дискретным временем выполнен сравнительный анализ трех стратегий разделения ограниченной буферной памяти по индексу обслуженной нагрузки. Данная работа является дальнейшим
развитием этих исследований. Здесь проведен анализ влияния блокировок буферной памяти транзитного узла на долю обслуженной нагрузки звездообразным сетевым фрагментом с различными по быстродействию входящим и исходящими интерфейсами.
2. Дискретная модель звездообразного фрагмента сети с распределением трафика
Рассмотрим звездообразный фрагмент сети, включающий M + 1 звеньев передачи данных, в котором в центральный транзитный узел по одному входящему каналу связи поступает информационный поток и распределяется по M исходящим направлениям. Предположим, что в узле-отправителе входящего канала всегда имеются пакеты для передачи в центральный транзитный узел. Пусть обмен в каждом звене выполняется полными пакетами и организован в соответствии со стартстопным протоколом [13], согласно которому пакет считается принятым узлом-приемником, если в нем не обнаружены ошибки. При искажении информационного пакета или квитанции, подтверждающей правильность приема пакета получателем, происходит повторная передача. Предположим, что входящему интерфейсу центрального узла выделен специальный буфер для приема пакета и анализа его на наличие ошибок. В случае корректного приема содержащийся в нем пакет переписывается в свободный буфер буферного пула выходного интерфейса, а в качестве специального выделяется другой из того же буферного пула. При отсутствии свободных буферов в пуле выходного канала связи прием полученного пакета не подтверждается, пакет сбрасывается и передается повторно. Такая техника гарантированного обеспечения каждого входного направления буфером для приема пакета широко используется для предупреждения «прямых» блокировок пути [13]. Полагаем, что все исходящие каналы связи имеют одинаковые физические скорости передачи данных, а скорость передачи данных во входящем канале в S раз выше. Кроме того, считаем, что время обработки пакетов при приеме и отправке в узлах-отправителях и узлах-получателях одинаковое. Тогда время полного цикла передачи пакета t будет одинаковым для всех исходящих звеньев рассматриваемого фрагмента, а для входящего звена составит t/S. Будем считать, что пакет, поступивший в транзитный узел в текущем цикле t, начнет передаваться по выходному каналу только в следующем цикле. Отметим, что за время t в транзитный узел по входящему каналу может поступить S пакетов, тогда как может уйти по каждому из выходных направлений только по одному пакету. Пусть безошибочная передача пакета данных во входящем канале определяется вероятностью F, а в исходящих каналах — вероятностями Fm, т = 1,М. Считаем также, что весь входящий в транзитный узел поток пакетов распределяется в m-й выходной канал с вероятностью Bm, ^M=1 Bm = 1. Величины Bm можно интерпретировать как доли входящего потока, направляемые в m-й выходной канал. Нетрудно видеть, что время безошибочной передачи пакета по каждому межузловому соединению является случайной величиной. Если условия первой и повторных передач одинаковы, что, как правило, выполняется в сетях пакетной коммутации, то данная величина имеет геометрический закон распре-
деления с параметром F во входящем канале и Fm, т = 1,М в исходящих каналах связи.
Для хранения пакетов в очередях к выходным интерфейсам транзитного узла выделен пул совместно используемой буферной памяти объема K. Размер очереди qm к каждому выходному каналу m ограничен предельной величиной Nm ^ K, определяемой стратегией разделения буферной памяти между выходными каналами. Для каждого входящего пакета, направляемого в конкретный исходящий канал, выделяется буфер при условии, что выходная очередь qm данного направления не превышает максимального размера qm < Nm и, кроме того, для очередей к выходным каналам связи выполняется ограничение m=i qm < K, соответствующее тому, что пул свободных буферов для хранения пакетов данных не пуст. Очевидно, что в каждом конкретном случае разделения пула буферов между выходными направлениями размер очереди к m-му каналу qm не превышает величины Qm, удовлетворяющей условиям: Qm ^ Nm и Yjm=1 Qm = K.
В общем случае различают пять стратегий разделения буферной памяти между выходными каналами связи [8, 10, 11]. Две из них являются крайними: полнодоступная и стратегия полного разделения. Еще три стратегии являются промежуточными и допускают различные схемы реализации [8, 10, 12]. Проведем анализ трех стратегий: полнодоступной (Nm = K), полного разделения (Nm = K/M) и неполнодоступной с индивидуальными потолками (K/M <Nm < K, £M= 1 Qm = K).
Поведение рассматриваемого сетевого фрагмента представимо в виде марковской системы массового обслуживания (СМО) с дискретным временем, конечным накопителем и M обслуживающими приборами [19]. Входящий поток определяется качеством входящего канала F и параметром быстродействия входящего соединения S, а время обслуживания на каждом приборе СМО — качеством m-го исходящего канала Fm. Распределение поступающих заявок СМО по М обслуживающим приборам задается вероятностями Вт, т = 1,М. Динамика очередей к выходным каналам связи данной СМО в стационарных условиях описывается цепью Маркова в M-мерном пространстве. Множество возможных состояний цепи Маркова по каждому измерению определяется стратегией разделения буферной памяти между исходящими каналами и не превышает величины Nm + 1.
Для дискретной цепи Маркова с конечным числом состояний, описывающей рассматриваемую СМО в установившемся режиме, определим с учетом введенных предположений переходные вероятности п/ из состояния I в состояние J. Здесь I и J — M-разрядные номера соответственно исходного и измененного состояний с областью значений каждого разряда от 0 до Nm: I = ii,..., '¿м; im = 0, Nm; J = ji,.. .'./';/' j,„ = 0,Nm; m = 1, M.
Обозначим через Pjb...,iM, im = 0,Qm, m = 1 ,M вероятности состояний M-мерной цепи Маркова. Очевидно, что запись Pi1,,,,iM эквивалентна записи Pi. Одной из основных характеристик СМО ограниченной емкости является пропускная способность [19]. В рассматриваемом случае этот показатель интерпретируется как пропускная способность входящего звена передачи данных, нормированное значение которого определяется величиной
пропущенного (обслуженного) потока:
М Я1 Ят-1 Ят Ят+1 Ям
(1) = ^ • • £ £ £ •••£ ,
т=1 ¿1=0 ¿т-1=0 ¿т = 1 ¿т+1=0 ¿м = 0
где ^ = {^1, — вектор значений надежностей выходящих кана-
лов т = 1, М, который в случае однородности всех выходящих направлений будем обозначать просто как а В = {В..., Вм} — вектор значений вероятностей направления трафика в т-й канал 13т, т = 1 ,М.
3. Полнодоступная стратегия разделения буферной памяти транзитного узла
Полнодоступная стратегия разделения буферной памяти подразумевает полную доступность всего буферного пула для любого выходящего направления транзитного узла. В этом случае очередь пакетов к любому из выходящих каналов может занять всю буферную память транзитного узла.
Рассмотрим функционирование звездообразного фрагмента сети при полнодоступной стратегии разделения буферной памяти на примере фрагмента со следующими параметрами: два выходящих канала (М = 2) разделяют буферный пул транзитного узла объема К = 2, параметр быстродействия входящего канала 5 = 2. В этом случае Ыт = 2. В табл. 1 приведены переходные вероятности, сгруппированные по признаку одинаковости измененного состояния .].
Таблица 1. Переходные вероятности цепи Маркова при 5 = 2, М = 2, К = 2
7ГЛЛ «142 ч «2 3\ п
1 2 3 4 5
(1 -¥? 0 0 0 0
Р)2 1 0
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.