On aggregate data link throughput of star network.pdf В задачах анализа и синтеза структуры сетей передачи данных важнейшим объектом исследования является звездообразный сетевой фрагмент [1], выпол-няющий функции мультиплексирования местных абонентских потоков данных локальных сетей подразделений организации в магистральный канал глобальной сети. Всесторонний анализ звездообразной топологической структуры необходим не только для решения задач выбора пропускных способностей, распределения потоков и синтеза управляющих параметров при демультиплексировании магист-ральных потоков [2], но и при реализации алгоритмов маршрутизации, разработке методов управления информационными потоками и ресурсами буферной памяти транзитных узлов передачи данных, агрегирующих трафик абонентских соедине-ний в единый интегральный поток. Математические модели такого сетевого обра-зования, агрегирующего клиентские потоки в глобальную сеть, позволяют изу-чать влияние параметров входящих потоков на пропускную способность исходя-щих каналов связи маршрутизатора с ограниченной памятью, проводить расчет емкости буферного накопителя.1. Модель фрагмента сети с мультиплексированием трафикаРассмотрим звездообразный фрагмент сети, состоящий из M+1-го звена пере-дачи данных, в котором в центральный транзитный узел одновременно по M вхо-дящим каналам связи поступают информационные потоки и агрегируются в один исходящий канал (см. рис.1). Предположим, что в узлах-отправителях входящих каналов всегда имеются пакеты для передачи в центральный транзитный узел. Пусть обмен в каждом звене выполняется полными кадрами и организован в со-ответствии со старт-стопным протоколом [3], согласно которому кадр считается принятым узлом-приемником, если в нем не обнаружены ошибки. При искажении информационного кадра или квитанции, подтверждающей правильность приема кадра получателем, происходит повторная передача. Полагаем, что каждым зве-98П.А. Михеев, С.П. Сущенконом фрагмента переносится симметричный трафик [4], все входящие каналы связи имеют одинаковое быстродействие, а физическая скорость исходящего канала в S≥1 раз выше. Считаем, что узлы-отправители и узлы-получатели имеют одинаковое время обработки кадров при приеме и отправке. Тогда за время полного цикла передачи кадра t по входящим звеньям рассматриваемого фрагмента в исходящий канал может быть отправлено S кадров. Будем считать, кроме того, что кадр, поступивший в транзитный узел в текущем цикле t, начнет передаваться по выходному каналу только в следующем цикле. Полагаем также, что безошибочная передача кадра данных во входящих каналах определяется вероятностямиFm,m=1,M , а в исходящем канале - вероятностью F. Нетрудно видеть, что время безошибочной передачи кадра по каждому межузловому соединению является случайной величиной, кратной t. Если условия первой и повторных передач одинаковы, то данная величина имеет геометрический закон распределения с параметром Fm во входящих каналах и параметром F - в исходящем канале связи. Будем считать также, что для хранения пакетов в выходной очереди в транзитном узле выделен пул совместно используемой буферной памяти объема K≥M. Тогда поведение рассматриваемого сетевого фрагмента представимо в виде марковской системы массового обслуживания (СМО) с дискретным временем, конечным накопителем, групповым входящим потоком и одним прибором с групповым характером обслуживания [5]. Групповой входящий поток СМО определяется качеством входящих каналов Fm, а время и число обслуженных заявок - качеством исходящего канала F и его быстродействием S. Динамика очереди к выходному каналу связи данной СМО описывается цепью Маркова. Множество возможных состояний цепи Маркова определяется размерами буферной памяти.О ОРис. 1. Структурная схема звездообразного фрагмента сетиВажнейшей характеристикой СМО ограниченной емкости в стационарных ус-ловиях является пропускная способность. В рассматриваемом случае данная опе-рационная характеристика интерпретируется как интегральная пропускная спо-собность входящих звеньев, нормированное значение которой определяется вели-чиной пропущенного (обслуженного) потока:Z(K,F,F1,...,FM)=F{∑ SkPk+S ∑ K Pk } ,где Pk - вероятности состояний цепи Маркова, образующие полную группу событий: ∑Pk=1.k=0О быстродействии агрегирующего канала звездообразного сетевого фрагмента992. Анализ быстродействия сетевого фрагмента с однородными скоростями каналовНайдем функциональную зависимость вероятностей состояний СМО в ста-ционарных условиях от параметров фрагмента сети с одинаковыми физическими скоростями передачи данных во всех звеньях звездообразной структуры. Начнем рассмотрение со случая двух входящих каналов (M=2), которые разделяют буфер транзитного узла емкостью K≥M . Для дискретной цепи Маркова с конечным числом состояний, описывающей рассматриваемую СМО в установившемся ре-жиме, система уравнений равновесия для вероятностей состояния имеет следую-щий вид:P0 (F1+F2-F1F2)=P1F (1-F1)(1-F2);P1[F1+F2-F1F2+F (1-2F1-2F2+3F1F2)]=P0 (F1+F2-2F1F2)+P2F (1-F1)(1-F2);P2 [F1+F2-F1F2+F (1-2F1-2F2+3F1F2)]=P0F1F2+P1[(1-F)(F1+F2-2F1F2 )+FF1F2]++P3F (1-F1)(1-F2); Pi [F1+F2-F1F2+F (1-2F1-2F2+3F1F2 )]=Pi-2 (1-F)F1F2++Pi-1[(1-F)(F1+F2-2F1F2)+FF1F2]+Pi+1F(1-F1)(1-F2),i = 3,K-1;PK F (1-F 1)(1-F2)=PK-2 (1-F)F1 F2 +PK -1 [(1-F)(F1 +F2 -2F1F2)+F1F2]. Отсюда для финальных вероятностей получаемP 1=P 0 (F1+F2-F 1 F 2) ; P 2=P 0 FF1F2+(1-F)(F1+F2-F1F2)2Pi = Pi-2 ( 1-F F 1F2 +Pi-1 [( 1-F )( F1 +F2 -2F 1 F2 ) +F 1 F2 ] i =3 , K .F(1-F 1)(1-F2),Для объема буферной памяти K=2 пропускная способность определится соотношениемZ(2,F,F1,F2)=F-F3(1-F1)2(1-F2)2/A,A=F2 (1-F1)2(1-F2)2 +F(1-F1)(1-F2)(F1 +F2 -F1F2)+FF1F2 +(1-F)(F1 +F2 -F1F2)2 .Для входящих каналов связи с равными вероятностями безошибочной передачи кадров (F1=F2=F*) данное соотношение принимает вид()FF *2+FF*(1-F*)2(2-F*)+F*2(1-F)(2-F*)2Z2,F,F*,F*=F.FF * 2 +FF* (1-F*) (2-F*)+F* 2 (1-F)(2-F*) +F 2 (1-F*)Для сетевого фрагмента с одинаковой статистикой ошибок во всех звеньях передачи данных (F1=F2=F) пропускная способность упрощается до следующей зависимости:Z ( 2,F,F,F ) =F F+(1-F)(2-F)(3-2F)F+(1-F)(2-F)(3-2F)+(1-F) 4При абсолютно надежном исходящем канале связи (F=1) выражение для пропускной способности преобразуется к видуZ2 1, F 1 F 2(1-F1)(1-F2)(F1+F2-F1F2)+F1F2(1-F1)(1-F2) 2 +(1-F1)(1-F2)(F1+F2-F1F2)+F1F2100П.А. Михеев, С.П. СущенкоЕсли хотя бы один из входящих каналов абсолютно надежен (F1=1 или F2=1), то объем пропущенного потока определяется только качеством выходящего звена передачи данных:Z(2,F,1,F2)=Z(2,F,F1,1)=Z(2,F,1,1)=F.В том случае, если весь входящий трафик направляется по одному входящему каналу (например, F1=1, F2=0), получаем известную зависимость [4]:Z ( 2,F, F 1,0 ) =FF 1F (1-F 1)+ F 1(1-F ).F 2 (1-F1 2 +FF1(1-F1)+F 2 (1-F)На рис. 2 приведен набор численных зависимостей пропускной способности от достоверности передачи данных в агрегирующем канале для различных объемов буферного накопителя. Аналитические и численные исследования рассматриваемой СМО с произвольным числом входящих каналов и ограниченным объемом буферной памяти показывают, что для узла с однородными по физическому быстродействию сетевыми интерфейсами (S=1) пропускная способность фрагмента при наличии хотя бы одного абсолютно надежного входящего канала полностью определяется качеством исходящей линии связи F. В целом зависимость пропускной способности от достоверности передачи данных в выходном канале мажорируется кусочно-линейной функцией (рис. 2):0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 FРис. 2. Сравнительные кривые пропущенного потока от достоверности передачи данных в исходящем канале связи, при F1 =0,1, F2=0,6 и различных объемах буферного накопителяВ наибольшей мере функция пропускной способности (1) отстоит от мажоран-∑∑ты (2) в точке F= Fm ≤1, а при Fm ≥1 - в точке F=1. Однако с ростом емко-m=1m=11 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.10Z*(F,F1,...,FM)Z(2,F,0.1,0.6)Z(3,F,0.1,0.6)- Z(5,F,0.1,0.6) Z(20,F,0.1,0.6)III∑ FF≤F;m=1∑∑YF F>YF⎩ m=1m=1(2)О быстродействии агрегирующего канала звездообразного сетевого фрагмента 101сти буферной памяти K транзитного узла, агрегирующего входящий трафик от M каналов связи, потенциальные значения функции пропускной способности асимптотически приближаются снизу к кусочно-линейной мажоранте (2). Этот факт хорошо согласуется с представлениями о том, что пропускная способность конвейера не превышает пропускной способности его самого «узкого участка». Отметим также, что минимум функции пропускной способности при прочих равных условиях достигается для однородных по качеству входящих каналов связи(Fm=F*>0,m=1,M ). С ростом же неоднородности качества различных входящих∑ каналов (с поляризацией значений Fm) при выполнении условия Fm = constm=1пропускная способность увеличивается и при достижении, по меньшей мере, одним из входящих каналов абсолютной надежности (Fm=1), пропускная способность сетевого фрагмента независимо от размера буфера и количества входящих потоков возрастает до потенциально возможного значения F.3. Анализ быстродействия сетевого фрагмента с неоднородными скоростями каналовРассмотрим звездообразный сетевой фрагмент с двумя входящими каналами (М=2) и скоростью исходящего канала, вдвое превышающей быстродействие входящих (S=2). В рамках предложенной модели система уравнений равновесия для произвольной ограниченной емкости буферной памяти в этом случае принимает следующий вид:p0(F1+f2-f1f2)=p1f(2-F)(1-f1)(1-f2)+p2f2(1-f1)(1-f2);P 1 [F1 +F2 -F1F2 +F(2-F)(1-2F1 -2F2 +3F1F2)]=P0 (F1 +F2 -2F1F2)+ +P2 ⎡⎣2F(1-F)(1-F1)(1-F2)+F2 (F1 +F2 -2F1F2)⎤⎦+P3F2 (1-F1)(1-F2);P2 ⎡⎣F1 +F2 -F1F2 +F(2-F)(1-2F1 -2F2 +3F1F2)+F2 (F1 +F2 -3F1F2)⎤⎦ = =P0F1F2 +P1 ⎡⎣(1-F)2 (F1 +F2 -2F1F2)+F(2-F)F1F2⎤⎦+P3 [2 F(1-F )(1-F 1)(1-F 2)++F2 ( F 1 +F2 -2F1F2)⎤⎦+P4F2 (1-F1)(1-F2); Pi ⎡⎣ F 1 +F2 -F1F2 +F(2-F)(1-2F1 -2F2 +3F1F2)+F2 (F1 +F2 -3F1F2)⎤=i?_2 (1-F)2 F⎦ 1F2 + +Pi-1 ⎡⎣(1-F)2 (F1 +F2 -2F1F2)+2F(1-F)F1F2⎤⎦+Pi+1 [2F(1-F)(1-F1)(1-F2)+ +F2 (F1 +F2 -2F1F2)⎤⎦+Pi+2F2 (1-F1)(1-F2),i=3, K -2;Pk-1 ⎡⎣ F 1 +F2 -F1F2 +F(2-F)(1-2F1 -2F2 +3F1F2)+F2 (F1 +F2 -3F1F2) = =PK-3 (1-F)2 F1F2 +PK-2 ⎡⎣(1-F)2 (F1 +F2 -2F1F2)+2F(1-F)F1F2⎤⎦++PK ⎡⎣2F(1-F)(1-F1)(1-F2)+F2 (F1 +F2 -2F1F2)⎤⎦ ;Pk ⎡⎣ F(2-F)(1-F1)(1-F2)+F2 ( F 1 +F2 -2F1F2)⎤⎦=PK-2 (1-F)2 F1F2 ++PK-1 ⎡⎣(1-F)2 ( F 1 +F2 -F1F2)+2F(1-F)F1F2⎤⎦.102П.А. Михеев, С.П. СущенкоДля объема буферной памяти K=2 решение системы уравнений равновесия принимает видP0 =F2 (1-R1)(1-R2)⎡⎣(2-F)2 -(1-F)(3-F)(R 1 +R2 -R1 R 2)⎤⎦A; P 1 =F⎡⎣(2-F)(R1 +R2 -R 1 R 2)- FR 1 R 2 -2(1-F)(R 1 +R2 -R1 R 2)2⎤⎦A;P2 =⎡⎣f(2-f)R 1 R2 +(1-f)2 (R 1 +r2 -R 1 R 2)2⎤⎦ A 1 ;A 1 =F2(2-F)2 + 2F(1-F)(1-3F+F2)(R1 +R -R 1 R2) + +2F(1-F)R1R2 +(1-F)4(R 1 +R2 -R 1 R 2)2.Для пропускной способности сетевого фрагмента при K=2 из (1) получаем следующее соотношение:Z(2,F,F1 ,F2)=A{F(2-F)(F1 +F2-F1F2)+F(4-3F)F1F2 +2(1-F)(1-2F)(F1 +F2-F 1 F2)2}.ЗдесьA=F2(2-F)2+2F(1-F)(1-3F+F2)(F1+F2-F1F2)++2F(1-F)F1F2 +(1-F)4 (F1 +F2 -F1 F 2)2.Отсюда нетрудно видеть, что при F1=F2=F=1 пропущенный поток достигает максимального значения Z(2,1,1,1)=2. Для абсолютно надежного исходящего канала связи (F=1) выражение для пропускной способности определится суммой достоверностей передачи данных во входящих каналах: Z(2,1,F1,F2)=F1+F2. При отсутствии потока в одном из входящих каналов (F2=0) величина пропущенного потока составитZ ( 2,F , F 1,0 ) =FF 1F(2-F)+2F1(1-F)(1-2F)F 2 (2-F) 2 +2FF1 (1-F)(1-3F+F 2 )+F1 2 (1-F) 4Для статистически однородного сетевого фрагмента (F1=F2=F) пропускная способность фрагмента упрощается до следующего вида:6-16F+20F2 -1 1F3 +2F4Z(2,F,F,F)=2F12-40F+64F2 -56F3 +28F4 -8F5 +F6При абсолютно надежных входящих каналах (F1=F2=1) объем пропущенного потока определяется только качеством (F) и быстродействием (S=2) выходящего звена передачи данных Z(2,F,1,1)=2F. Для статистически однородных входящих каналов связи F1=F2=F* пропускная способность входящего звена передачи данных принимает видZ(2,F,F*,F*)=FF *⎡⎣ F(2-F)(2-F*)+FF* (4-3F)+2F* (1-F)(1-2F)(2-F*)2⎤⎦⎣ F2 ( 2-F ) 2 +2FF* ( 1-F )( 1-3F+F2 )( 2-F* ) +2FF*2 ( 1-F ) +F*2 ( 1-F ) 4 ( 2-F ) 2 .Численные исследования функции пропускной способности сетевого фрагмента с тремя звеньями передачи данных при различных объемах буферного накопителя показывают, что пропущенный поток имеет вид кривых, представленных на рис. 3.О быстродействии агрегирующего канала звездообразного сетевого фрагмента 1031,8 1,6 1,4 1,2 1 0,8 0,6 0,4 0,2Z(2,F,0,5,0,7) Z(3,F,0,5,0,7)- Z(5,F,0,5,0,7) Z(20,F,0,5,0,7)- /0-4;-4r-4:-4~;-4;-4;-4^-4^-4;- 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 fРис.3. Сравнительные кривые пропущенного потока от достоверности передачи данных в исходящем канале, при F1=0,5, F2=0,7 и различных размерах буферного накопителяИз данного рисунка нетрудно видеть, что пропускная способность в интервале F∈[0,(F1+F2)/2) мажорируется прямой Z*(F,F1,F2)=2F, а в интервалеF∈[(F1+F2)/1,1], не превышая значения Z*(F,F1,F2) = F1+F2, ограничивается кривой параболического вида с незначительным минимумом, расположенным примерно в середине отрезка. Численный анализ показывает, что чем ближе вероятности безошибочной передачи данных входящих каналов связи рассматриваемого фрагмента (чем ближе друг к другу значения F1 и F2), тем выше проходит мажорирующая кривая на отрезке F∈[(F1+F2)/2,1]. Наиболее глубокий минимум этойкривой наблюдается для статистически существенно неоднородных входящих каналов (например, при F1=1, F2=0).На рис. 4. приведено семейство зависимостей пропускной способности от качества исходящего канала при заданном объеме буферного накопителя транзитного узла и различных значениях Fm, m=1,2, удовлетворяющих условию F1+F2=const. Отсюда нетрудно видеть, что для различных областей изменения достоверности передачи данных в мультиплексирующем канале наибольшие значения пропускной способности достигаются при существенно различных наборах F 1 и F2 с постоянной суммой. В области F∈[0,(F1+F2)/2] доминирует кривая, соответствующая полярным значениям Fm, m=1,2, а на основной части отрезка F∈(( F 1 +F2)/2,1] - однородным значениям: F1=F2. С ростом числа входящих каналов связи имеют место сходные зависимости.Исследование сетевого звездообразного фрагмента с произвольным быстродействием магистрального канала, числом входящих линий и объемом буферного накопителя узла в ряде частных случаев показывает, что при абсолютно надежных входящих каналах (Fm =1, m=1,M) объем пропущенного потока инвариантенк числу мультиплексируемых каналов, емкости буферного накопителя и определяется скоростью передачи и качеством выходящего звена переприема данных:104П.А. Михеев, С.П. СущенкоZ(K,F,1,…,1)=SF. Очевидно, что при F=1 пропускную способность будет опреде-лять только физическое быстродействие исходящего канала S.2 1,8 1,6 1,4 1,20 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 F1 0,8 0,6 0,4 0,2Рис. 4. Сравнительные кривые пропущенного потока от достоверности передачи данных в исходящем канале, приF1+F2=1 и K=3.Для абсолютно надежного исходящего канала связи (F=1) с интегральным быстродействием S, совпадающим с числом источников М, пропущенный поток, не превышая быстродействия агрегирующего направления, определяется качеством входящих линий, инвариантен к емкости буферной памяти K≥S и задается соотношением∑ Z(K,1,F1,...,FM)=Fm.m=1Численные исследования функции пропускной способности при произвольных значениях количества входящих каналов M, быстродействия исходящего канала S, емкости буферной памяти центрального узла K≥S и достоверности передачи данных по отдельным звеньям рассматриваемого сетевого фрагмента Fm=1,m=1,M и F показывают, что данная операционная характеристика мажорируется кусочно-линейной зависимостью, аналогичной соотношению (2):При умеренных объемах буферной памяти (S≤K≤3 S) значения пропускной способности в максимальной степени отстоят от мажоранты в точке F=1∑ MFFmZ*(F,F1,...,FM)=SF,SF≤∑Fm;m=1∑∑Fm,SF>Fmm=1∑∑при выполнении ограничения Fm≤S, а при Fm≥S - в точке F=1. Для емко-m=1m=1О быстродействии агрегирующего канала звездообразного сетевого фрагмента 105сти буферной памяти, существенно превышающей быстродействие исходящегоMMканала (K>3S), указанная точка для ограничения m 1 Fm

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