автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Анализ структуры и характеристик многокаскадных коммутационных сетей баньянного типа

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ВЫСШЕМУ ОБРАЗОВАНИЮ РОСС15ИСКИИ УНИВЕРСИТЕТ ДРУЖБЫ НАРОДОВ

На правах рукописи

КУКОВ Олег Витальевич

УДК 681.3.016

АНАЛИЗ СТРУКТУРЫ И ХАРАКТЕРИСТИК ШЮГОКАСКАДЩХ КОММУТАЦИОННЫХ СЕТЕЙ БАНЬЯННОГО ТИПА

( 05.13.17 - теоретические основы информатики )

Автореферат

дасоэртацил на соискание ученой степени кандидата физико-математических наук

Москва - 1994

Работа выполнена на кафедре теории вероятностей и математической статистики Российского университета дружбы народов

Научный руководитель -Действительный член Академии естественных наук Российской Фодерации, доктор технических наук, профессор, Г.П.Башарвн

Официальные оппоненты: доктор физико-математических наук, доцент Г.И.Фалин кандидат физико-математических наук В.А.Ефймушкин

Ведущая организация -Институт проблем передачи информацзш Российской Академии наук

Защита диссертации состоится " У.. " __________1994 г.

в 15 час. 00 мин. на заседании, диссертационного совета К 053.22.28 в Российском университете дружбы народов.

Адрес: 117198, Москва, ул.Ордаоникидзе, 3, факультет физико-математических и естественных наук, ауд.

С диссертацией моино ознакомиться в научной библиотека Российского университета дружбы народов .по адресу: 117188, Москва, ул. Миклухо-Маклая, д.6

*

Автореферат разослан * 22 " Ко.р^и?___1994 г.

Ученый секретарь

диссертационного совета . С.С.Спесивов

кандидат физико-математических наук, доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

"Актуальность работы. Появление и развитие суперЭВМ с параллельными распределенными вычислениями потребовало научится снижать расходы времени и ресурсов на связь между процессорными элементами. Архитектура соответствующей сети связи может . оказаться эффективной для одних приложений и неэффективной для других. Поэтому возникла и с развитием конкретных сфер приложений стала играть все более важную • роль теория многокаскадных коммутационных сетей (МКС = MIN), помогающая их проектировать с учетом структуры, быстродействия, пропускной способности, возможных задержек, надежности и стоимости,

С -другой стороны, развитие современных сетей связи, распространение пакетной коммутации и появление цифровых сетей с интеграцией служб (I1GITG = ISDH) привело к переходу от классических, телефонных :яюгокпскадных шлмутациснных схем к многокаскадным сетям тех т ютов, что к с суперЭВМ. Это, кромо прямого переноса ряда фундаментальна мнтемптм юпких результатов ео-х годов, одехало развито д углублотте различшх аспектов теории мнопжпскадтах сотой: о коь-лутачдей пакетов весьма актуальным кок о тобретлческой, так и с грактичеегсой точек зрения.

Наконец, в последнее. вртл в дополнение к существующим • системам связи наметилась тенденция объединения разноскоростнкх слунб, таких как передача данных, речи, видеосигналов и др. в одинуп широкополостную ЦСИО (Ш-ЦСКС = B-I3DN), в качестве коммутационной . среда которой предлагается использовать Оаньящша многокаскадные сети. Эта новейшая сфера приложений обеспечивает актуальность теш, выбранной для исследования, и в '.. будущем. #

Современные научные результаты по анализу внутренней структуры й вероятностно-временных характеристик МКС .восходят к - классическим работам, связанным с изучением многокаскадных коммутаторов в аналоговых телефонных сетях такими учеными как А.Д.Харкевич, Л.А.Бассалыго, Г.П.Башарин, В.И.Нейман, М.А.Шнепс

- г -

и др. в СССР, У.Е.Вепез, С.A.Clos, C.Y.Lee, A.lotse, K.Takagl и др. В дальнейшем различные аспекты теории МКС (как чистая теория, так и в связи с приложением в суперЭВМ) получили свое развитие в работах. Г.Т.Артамонова, Г.П.Веселовского, Л.Л.Дудко, Е.А.Метлицкого, В.Д.Тюрина и др.; D.P.Agrawal, D.DeGroot, Т.-Y.Feng, R.W.Hockney, G.J.LipovsKl, M.Malek» J.H.Patel, H.J.Siegel и др. Среди многих направлений по улучшению характеристик производительности сетей выделим появившиеся в последние годы работы, изучающие применение буферов в МКС с блокировками. Наибольший вклад в ¿то направление вйесли D.H.Dias, M.N.Huber, J.S.Turner, T.H»Tîieimer, Y.-C.Yeriq и др.

Целью данной диссертационной работы является развитие методов анализа топологической структуры KMC, изучение вопросов эквивалентности сетей с помощью графового подхода, построение аналитических и имитационных моделей буферизованных МКС, работающих при неоднородной • нагрузке. Эти модели позволяют получить ответ на многие вопросы, возникающие при проектирован}»: МКС разных типов.

Методы исследований.. В работе в основном использованы ' методы теории вероятностей, теории массового обслуживания И дискретной математики - теории графов и перестановок.

Научная новизна и результаты, выносимые на защиту, состоят в следующем:

- в развитие графового подхода к изучении многокаскадных сетей предложена графовая модель МКС общего вида и баньянных сетей в частном случае с использованием специально определенной группы перестановок; на основе модели проведена классификация и описано управление в дельта-сетях;

- с помощью определенной графовой модели рассмотрен вопрос эквивалентности МКС и доказано взаимно-однозначное соответствие между эквивалентностью двух сетей и изоморфизмом соотвествующих графов;

- изучен, вопрос построения аналитической модели МКС в случае неоднородной по выходам нагрузки; проведен анализ

Оаньяшшх сетей при неоднородой нагрузке с а) распре долешша буферными накопителями (БН) на входах каждого коммутатора сети и 6) поднодостугошмй БН внутри коммутаторов о помоцью разработанного аналитического подхода и в сравнении с результатами работа имитационной модели.

Прпктичоскап...!loiniqcTb..paOqju. Результаты диссертации могут бить полезны при проектировании конкретных коммутационных. схем длл оценки производительности и . задержек, с номовдо шшлитичоского и имитационного моделирования. Кром^ того, построенные графовые модели дают возможность использовать в дальштжих исследованиях rp&Ionuft подход для изучении Соло о широких классов эквивалентны* сотой и получения различиях, вероятноспю-ьрпмзншх характеристик МКС, важных при их проектировании и оксплуатацпи.

Pgajmaauhfl результатов рзОотн, Иссл-здовштз многокаскадшх коммутационных сетей в овота заявлешви: a-jae целей проводилось в радсах НИР "Разработки матемзтичоских кэтодов и апгорпиюв аиолт мультипроцессор»«. мгчислитссыкгг. .т:стем, ¿окольных ц 1ппч)грильипх кн'Горме;деонно-вычислите.п'. ;<чх сетей" (гопудпр-етиошпИ* P'<! iiorpnimoiHffltt исмер 01.5.10.033110), вторил г. поднялась и соотиотствш* с , нланаш ЛИ СССр,

ооиовнн'» ревультьтц, излоквняыо и

дассзртсщш, докладываюсь на:

4-м кзидународном еакинарэ по теории тедотр^дка и компьютерному моделированию '(МСТТКН-4, ('оокве,- 1092 г.);

9-й Полорусокой сишо-семинарг, "Митсмлгачеокие методц неслодавания систем и сетей массового обслуживания" (Минск, -1993 г.); .

Региональной мекгашпродном сэш:иаро по талеурефику "Digital Ooœnuhlcation network mariassent" w-uaiopsypr1,- 1993 г.);

10-ft Белорусской школэ-сеюшаре "Анализ и применение* систем и сетей массового, ссслузя'лзнэд" (Минск, - 1994 ?.)

4-м Росоийско-аэмецком семинаре по интвгральннм сетям и управления потоками инфоршлцт (Москва-, - 1?94 г.)

научных семинарах Российского университета дружбы народов (1991 -1994 гг.)

По теме диссертации опубликовано 5 работ.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы из наименований. Диссертация содержит страниц текста, 2-4

рисунков, ......2...... таблиц.

СОДЕРЖАНИЕ РАБОТЫ

Во ..введении., обосновывается актуальность темы диссертации, проводится обзор публикаций по отой теме, формулируется цоль исследований, кратко изложили содержание и основные результаты диссертации по главам, охарактеризованы их научная новизна и практическая цошюсть.

В первой главо изучаются вопросы построения графовой модели МКС и вытекающие из нее вопросы классификации. и описания управления.

В §1.1 даются основные определания и проводится общая классификация МКС. С помощью понятия статической перестановки

(-ТТп и определения основной алгебры перестановок проводится клэсификация т.н. дельта-сетей, т.о. сетей, обладающих свойствами единственности пути от кавдого ее входа к кавдому выходу' (свойство баньянности) и свойством самомаршрутизации пакетов. Приводится эквивалентная десятичная запись основного ниооро перестановок, позволяющая в дальнейшем корректно описывать маршрутизацию в МКС с точют зрения графового подхода, т.к. десятичная нумерация вершин графа наиболее естественна.

В §1.2 рассматривается организация управления в

дельта-сетях. Строится взаимнооднозначная функция В4(д:{,у), где

о;1 - номер входа в I-каскад коммутационных элементов ЧКЭ), у -номер адресата (выходного порта сети), позволяющая полностью

описать алгоритм управления маршрутом пакета в дельта-сети на основе следующих данных: х - номера входного порта сети, у, 13

1=ТТп>, {0£(1/>, 1=Т7п>.

В §1.3 проводится построение графовых моделей МКС общего вида и, в частном случае, дельта-сетей. Даются типичные для графов определения полнодоступной и баньянной сетей в терминах достижимости и вытекающие из определений некоторые свойства таких сетей. Приводится классификационные' определения однородной, регулярной, прямоугольной, двоичной и дельта-сети в графовых терминах.

Ей второй главе рассматриваемся вопрос эквивалентности дельта-сетей с помощью представленного гра-^ового подхода.

В §2.1 дается постановка задачи и определение конфликта в дельта-сети в термшгах перестановки. А именно, допустим, что на всех входных портах сети имеются г.ччети, ка.едый из которых, ь свою очередь, снабжен своим, ,н;;м от других, тегом

назначения. Тогда такую ситуацг.в мы представляем с помощьи перестановки

&Го 1 2 ... н-1 1 ' п Ц/0 У, Уг ...

где N - размер дельта-сети, (£,у{) - паро, соотвтствующиг пакету, поступившему на входной порт I и имеющего тег назначения у(, <=0,Ы-1, у,€£0,1,...,Н-1}; ЧЩ. На графе поре (1,у{)

будет соотгзтствовать путь Ь И т.к. исследуемый класс мко являотся классом сетей с блокировками, то в могут существовать такие пары вида (4, у {), что мевду*соответствующими путями могут возникать конфликты.

Определение. ■ Первсттовха называется реализуемой в

дельта-сети, если при прохождении пакетов в соответствии с нею не возникает ни одного внутреннего конфликта-, или д-реализуемой,

- б -

если для передачи всех пакетов Сез конфликтов требуется по крайней мере д проходов,

Далее приводится две задачи, известные из" литературы,

возникающие при задании для данной МКС перестановки

1. Определить, является ли перестановка реализуемой}

2. Если не реализуема (д>1), то минимизировать число проходов q, требуемых для ее реализации.

Для порвой задачи с помощью определенных в главе 1 статических поростановок и динамических функций приводится алгоритм

проворки реализуемости перестановки тс®.

В §2.2 вопрос о конфликтах в дельта-сетях рассматривается с точки зрения функциональных возможностей сетей, что приводит к постановке вопроса об юс эквивалентности в этом смысле. Если рассматривать сети с точки зрения реализации конкретной перестановки тс, то возникающая задача минимизации числа проходов, необходимых для реализации тс, будет эквивалентна задаче минимальной раскраске соответствущего конфликтного графа. Если же рассмотреть все множество перестановок в' совокупности, то исходя из реализуемости тех или иных подмножеств перестановок разными сетями мы можем говорить об отношении эквивалентности на всем множестве МКС рассматриваемого класса. Т.о., по определению, две сети Б и функционально эквивалентны, если они реализуют одинаковое множество перестановок.

В упомянутом параграфе . задача функциональной эквивалентности переносится в термины графовой модели, определенной в работе выше. Попутно доказывается вспомогательное утвервдение: две сети О и в: функционально эквивалентны тогда и только тогда, когда множества их блокируемых путей совпадают. Дается определение блокируемых путей в терминах операций над вершинами соответствующих графов.

В начале §2.3 представлен обзор основных работ по анализу эквивалентных свойств МКС. Показано, что для изучения вопроса

- т -

эквивалентности достаточно обратиться к разработанному вопросу об изоморфизме графов. Основным результатом параграфа является следующая

Теорема. Две баньянные прямоугольные регулярные сети функциональна эквивалентны тогда и только тогда, когда графы этих сетей изоморфны.

В частном случае, для основных дельта-сетей, использующих в Качества статических перестановок а4 перестановки • из

определенной в главе 1 алгебры перестановок, получено следствие о да функциональной эквивалентности. .

а) • б)

Гйо.1

' решаются задачи, связанные о ; анализом вороятностно- временных харатгтарист:« дэльта-еэтей.

В <}ЗЛ приводится обзор извеотних методов улучшния производительности МКО па очэт онинения эффекта внутренних блокировок. В частности, рассматривается аналитический' подход к изучению влияния на качественные характеристики сети от размещения в каадом- ее КЭ распределенных (рис.1 а) или полнодоступных (рио.16) буферных накопителей*(БН).

*

- в -

В большинстве опубликованных по данной теме работ принималось, что пакеты, поступающие в сеть, распределяются по выходным портам равномерно. Такое допущение значительно упрощает задачу и позволяет, в частности, значительно сократить число состояний аналитической модели. Однако равномерный трафик не всегда отражает реальную ситуацию в моделируемых сетях и даже элементарная неоднородность в том смысле, что в сети существует лишь один более загруженный выход (hot spot), в корне меняет ситуацию й применение к такой МКС однородной модели приводит к оптимистической оценке пропускной способности сети.

В §3.2 приводится .все вида матрицы 6=(9{J), I,J=0,N-1, ОlJ=P(naKQT, поступивший на входной порт i, имеет тег назначения

Я, позволяющие сколько-нибудь сократить число состояний ft" моделирующей ЦМ для МКС в самом общем случав. Здесь k - число состояний отдельного КЗ.

В следующих параграфах описываются две аналитические модели МКС с БН в каждом коммутаторе. В §3.3 приводится анализ сети с распределенными БН, а в §3.4 - с полнодоступными БН. Несмотря на аналогичность построения этих разделов, показано, что, вообще говоря,' метод анализа, примененный к распределенным БН не применим к полнодоступным БН, что привело к необходимости подробного разбора обеих моделей.

В §3.3 изучена следующая математическую модель:

Рассмотрена дельта-сеть, у которой на каждом входящем направлении имеется распределенный БН на m пакетов. Тогда главная цель появления буферов - уменьшение вероятностей потерь из-за наличия внутренних блокировок - достигается следующим образом: если два пакета (иЛи более, если размер КЗ а5&) из разных БН конкурируют за один и тот же выход КЭ, то среди конфликтующих пакетов равновероятно выбирается один и направляется для передачи на следующий каскад, а остальные остаются на своих местах для последующего повторения этого алгоритма. Сеть синхронна, ее такт х - время прохождения пакетом

одного каскада.'Здесь где:

т,- время распространения сигнальной информации с последнего каскада до первого, после чего каждому пакету известно, может ли он двигаться дальше;

т£- время передачи пакета в накопитель КЗ следующего каскада, причем сначала осуществляется передача из последнего каскада во внешнюю среду, затем из предпоследнего в последний и т.д.

Рис.2

Пусть исследуемая сеть задается набором

а, т, {34,£=Т7п>; X, (в^J),i,J=T7S>.

Здесь М»И - размерность сети; а«а - размерность КЗ; п=1о£аЫ -

число каскадов КЭ; СБ > набор статических перестановок, ?=1~7п;

т - размерность БН, Принималось, что с вероятпотью X,

00^1 за такт на любой входной порт независимо один от другого поступает пакет, т.е. общее число пакетов, поступающих за такт на все входные порты имеет биноминальное распределение с

параметрами N и к. Пакет может бить потерян, если БН соответствующего входного порта бил полол. Кагдай пакет,

принятый на входной порт 1, о вероятностей ^Г 0^=1,

• Д^о

адресуется на выгодной порт

Далее рассмотрены одновременно два случая ~ обдай случай неоднородной нагрузки для сети N=8 и случай "вццеяешюго. выхода" для сети любой размерности.. Кроме того, для простоты 0=2| ц

- имеем в первом случае омега-сеть (рис.й), , 1=Т7и7а.

Обозначим вероятность адресации пшсета ца верхний выход

коммутатора I каскада Р. ( Ш)-КЭ )? . - на даний

выход того ке КЭ.

Пусть теперь -накопитель оодэркя? } пагштов ?!

начале такта ^ (*

' /=о . ' •

пакет готов- к передаче в йЬнакошггель из (г.-1 )-

каскада};

*ми)=р{пакат в йЬнакопитело способен дв^атьса дальше са

г-такт | в М-накопителе есть пакзт}.

В частности, для случая "выделанного выхода" доказано

Утверждение. Вероятности' . состояния буферных .накопителей дельта-сети в случае неоднородной нагруьки ткйа "выделенный выход" в двух последующих тактах описываются следующей онстэшй уравнений:

Рьг и' ь[ркг(0.:г )+ры с1.,г)гм.и)]чы а ):

+Рь* * < *)$

рм )=[рк1 и )+Рге1 ом )гЛ1 и «)+

+рк1ш,г)гЬ1а), Й=ТТп, г=Т7л. где qп(t)=Л. - входная нагрузка на любой вход сети;

Чм <' ». I(0'* > 0 "<«»¿-1.. ,, (о.« )р„:,,, ("о,t)e0k_]¡) .

й=гТп, 1=0; .

' (Рь, ,.,<«.*>+рь* ,,; (я.г)ты, _ г < * (Ры (о.г )+|ры «э,»> (1 )] (?*♦). и Г*'■г. г+»<"•'' ■К*,, г+< <*:>) • 1=тт^.;

гп1(4)=рп1(О>1)+рг11(ОЛ)(1+е^0у. , .

где

еО I (.0 гк и-1 ) I о 2ь-1 и-1 )

I 1/2, г>1, '

и нумерация соответствует сети веерной структуры для .исходной сети.

В §3.3 рассмотрена дельта-сеть с полнодоступныш ВН. Используя тот т подход, что и в предыдущем параграфе, получены следующие результаты. В обозначениях

рЬ1(г;и)=РШ-накопитель содоргит { пакетов в начале такта г},

(1;"Ь)=1, причем здесь и далее А=1 .п,

1=0

г=ГГЕ, ¿=о7т, ш,

(^и,)=Р1г?Х-накопитель ' содержт Зг пакетов на начало *

текущего такта | в начале предыдущего такта 1-1+ было

.^пакетов), ,^=07111,

1)=Р1в Ь1-накопитель поступило ] пакетов , в момент времени'$ | в начале предыдущего такта г-1+ было I пакетов), т1п(2,т-1), гьг(1~Лг)=Р(из кг -накопителя ушло. / пакетов в в момент времени 1-0 | в начале предыдущего такта г-1 + Сало ( пакетов)( 04/4и1п(2,П, пакет готов к передаче в йг-КЭ из (&-1 )-каекада)= РСнакоторцй данный (,^.-1 )-КЭ имеет пакет для передачи в ¿1-1(3);

Ь^йРСКЭ кз (&-И ¡-каскада предоставит возмокюсть принять пакет 'из -накопителя, причем ее,ее а тот КЗ находится в верхней подсети для '^-каскаде, то а=0, а если в нижней - то э=1II й=ш1п{2,т-1)| имеем Утаерззддние 3,4,Ь Вероятности состояний для каждого из п(п+1)/2 Накопителей дельта-сотп . V в двух соседних 'тактах , описываются ододуюдеП системой уравненийI

щ ■ ,

^ Н^ЦП-МРыЦ^-Н), •'г*5*®'

Здесь

пииЦО,.* -)

Вероятности | связшздэ с поступлзнк&м

-тэ -

пакетов в й!-йакопйтель, определяются равенствами где

т

)=0

если М-КЗ расположен в верхней подсети для (й-1)-касквда,

если в нижней}

*0 Чц**" '

Утверздение 3.4,3» Вероятности, связанные о уходом-пакетов из Л1-нвкот!Твля, определяются равенствами

I

Здесь

х*0

' 1* '

О, 1чг=0 А (з>1 V /=2, . Х*1 Л >1,

л /«=0, (=Т7й; ^^^ л

л>17ЯГ л ¿»о, • ЬйХ^Х,. *-ТП=га/-1. да.

где

т-г

н=о н=о

т-а 1

ы _

т-г 1

К=о Кво

»

ь'г-1, г-Т^п. в-о,1.

На примере последней модели приведем формулы для раочет?} основных вероятностно- временных характеристик ЦВЮ. Определи;.» ■ пропускную способность (ПО) выходного коммутатора. п1 последнего каскада сети как величину, равную среднему числу пакетов, проходящих за такт черев этот КЭ|

г, 2 ■

' t=0J=0 ■ ,

Тогда ПО конкретного выходного порта а Щ-КЭ будет иметь вид , ' а суммарная ПС оэти будет равна , ■; .

; Т= у5 Тп1 2и<1"г), ^

ГД9 Ц(Х)

{О, ХФ, 1, Х>0.

Среднюю в а держу в &1-КЭ определим кок отношение средне^ . длины очереди в &1-накопитела. К орадаёму числу поступала в него пакетов (формула Литтла)!

1

(жо 1=о.»=о

Тогда средняя задержка в й-квскаде будет равна

г*о

а средняя задержка всей сети

Нак известно, аналитические метода моделирования, несмотря на достоинства - сравнительная простота расчетов и сравнительно малые затраты машинного времени - позволяют в лучшем случав получить лишь средние значения нужных характеристик в стационарном режиме, функционирования и приводят,' как упомянуто выше, к существеному упрощению моделей. При шитации можно .снять Многие ограничения И, кроме того, охватить и более' сложные алгоритмы функционирования. .

В §3.5 представлена имитационная модель буферизованной дельта-сети, параметры и допущения которой включают в себя множество параметров МКС, рассмотренных при аналитическом анализе. Формулируются предположения^ положенные в основу имитационной модели.

Все основные численные результата, вытекающие из параграфов 3.3 - 3.5 приводятся в §3.6.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

1. В диссертационной работе рассмотрены аспекты анализа МКС баньянного типа, связанные о их топологическими, функционально-зквивалентшйи свойствами и . вопросами улучшения производительности дельта-сетей;

2. Построена графовая модель многокаскадных сетей и проведена с ее помощью классификация МКС;

3. С графовой точки зрения изучен вопрос об эквивалентности различных сетей;

4. Портроода аналитические модели дельта-сетей о распределенными и ролшдостушшми буферными накопителями прк неоднородной нагрузке. Проведен чнолевдшй, с также ш.гатециошшй анализ таких свте£,

Основные разультаед. диссертация отра;©1щ » слэдумща опубликованных работах?

1. Baaharln G.F., Zhukov 0,v. Functionally equivalent of multistage interconnection networks In temp or gyapii theory// 4 Меэд. семинар no теории толатрафшса я Компьютерному модвлпрорй-шда (ЫСТШ1-4): Об. трудор.- М.гШШ PAII, 193,1.- 0,0-14.

г. Baaharln G.P., Khukoy 0,V. Analysts of Mul «buffered delta networks under nonuniforrn traffic paterns// Froceo»tlngn of Regional International. Toletralflc Deminar "Digital <?опдавд1 cation not work racmagisnt". - ШЦ1Б, Bt^eteraburs,- 16-20 Jur.o 1993,- P.172-176.

3, Baaapiai Г,П,, Жуков Q.p, . ,0 графовой мадоля « эквивалентности бойыадах сотой// Автоэдтика и т0лэмах£да:г,сь~ 1993,- /3(0,- 0,168-177,

4. Бащарин Г,ПМ Цуков О,В, faosot ярощ'СШЦ' способное!'« буферизованной, дольта-сота при нэраш^омбряо^ нагрузке// Автоматика И толакэхщрша,- 1934,- Й10.~ 0,175-103.

6. Baaharln С.р., fchukoy 0,V, QueueJng snalyalo ci buffered delta networlm untjer nonuniform tralflo// Proceeding oi 4 -Russian-German So,ulnar o| inteTrutisd IJeteorJzs 1ШД Flow Control ПГР Of RAS, Hoscow. 1994,-f,43-63, ' .

Abstract. Zhukov Oleg Vitalievich. Analysis of structure and performance of banyan multistage interconnection networks.

Banyan ilultiataga Interconnection Networks (MIN) have received much attention in recent years because of their' hardware efficiency and their key rolé in parallel processing ' Systems and also in packet switching nodes of ISDN systems. But these networks do not realize all permutations. This has led to reseârch in network equivalence relations, some classes of équivalence and basic properties of these networks * Then the first part of thia dissertation is founded on graph theory and some properties of permutations. It was shown that two networks are functionally equivalent If and only-if they have isomorphism between graphs. Any class of equivalence was proposed.

in the second part of the dissertation a method for evaluating the throughput of multibuffered delta networks with input and shared buffeting wider nonuniform traffic patterns with allowance for topology otruotura of M was presented. Analytical and simulative methods were discussed, .

I7.IIv94r. ftfoeM Iir, jû Tapi. 100. 3atfi 494 Test; Opjciomsnwae, 3