Синтез структуры сети. Изучение математической модели и метода синтеза звездообразной структуры ЛВС

МИНИСТЕРСТВО  НАУКИ И ОБРАЗОВАНИЯ  РЕСПУБЛИКИ КАЗАХСТАН

НАЦИОНАЛЬНЫЙ  ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ  им. К.И.САТПАЕВА

Институт  Информационных Технологий

Кафедра «Вычислительная техника» 
 
 
 

Лабораторная  работа  №1

дисциплина: Компьютерные сети.

Тема: Синтез структуры сети. Изучение математической модели и метода синтеза звездообразной структуры ЛВС.

 
 
 
 
 

Проверил:

Турым А. Ш.

Выполнила:

Ходжаева  Ж.

гр. СИБ – 08 – 1р  
 
 
 
 
 

Алматы 2011 г.

  Математическая модель  звездообразной структуры  ЛВС 

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

¦ = (x,y,z) = ∑     ∑  C_jt y_jt + ∑        ∑    C_ijx_ij +∑      ∑     C°_jk Z°_jk®min

                                 ^{iÎM°   tÎR                     iÎM/M°   jÎM°                  jÎM°    kÎMk}

(2.10)

при ограничениях (2.1) – (2.3) и  

 å     Z°_jk = 1  (j¹k, M°_kÎM°),                     (2.11)

  ^{jÎM°     kÎM°k}                                                        

Z°_jk = 1, если j – я АС прикреплена к к – й КС;

           0- в противном случае                                                     (2.12) 

å V_l    å     å   Z°_jk £ (å    l_i) / m                             (2.13)

  ^{lÎL             jÎM°       kÎM°k                        kÎM/M}

где M°_kÌM° -  подмножество пунктов, где возможны размещения  КС ; V_l – пропускная способность l – го типа КС ; L – множество вариантов построения КС ; С_jk – приведенные затраты на передачу информации в единицу времени из j-й АС через к – й КС.

Ограничение (2.11) означает, что на заданном множестве возможных пунктов размещения M°_k может быть организована только одна КС, связанная со всеми АС. Ограничение (2.13) учитывает требования к пропусным способностям КС и линии связи.

При этом пропускные способности линии связи считаются такими, что они полностью обеспечивают максимальную загрузку КС.

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

(å  l_i) / m , где m – число АС, подключенных к магистрали (или

   ^iÎM

кольцу). 
 

                    

                           Метод построения звездообразной ЛВС

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

  Решение  этой задачи можно свести к задаче поиска медианы полного взвешенного графа G с матрицей весов ||C_ij|| (i,jÎM⁰), где каждой вершине приписывается вес w_j³L для всех jÎM⁰. Медианой графа G называется вершина, для которой сумма кратчайших расстояний от нее до остальных вершин графа является минимальной. Для каждой вершины определим два числа, которые называются передаточными числами:

  n₁(x_i)=åw_j d(x_i,x_j) и n₂(x_i)=åw_j d(x_j,x_i),

                 ^{jÎM                              jÎM}

где d(x_i,x_j)- кратчайшее расстояние от вершины x_i до вершины x_j, в данном случае d(x_i,x_j)= C_ij. Числа n₁(x_i) и n₂(x_i) соответственно называются внешними и внутренними передаточными числами вершины x_i. Вершина x¢, для которой

 n₁(x¢)=min{n₁(x_i)}       (2.48)

                                                          ^iÎM

называется  внешней медианой графа G, а вершина x² для которой

             n₂(x²)=min{n₂(x_i)} (2.49) -  внутренней медианой его. Если 

                          ^iÎM

граф  G имеет симметричную матрицу весов, т.е. по одним и тем же каналам связи осуществляется как передача, так и прием данных (например, как в ЛВС), то n₁(x¢)=n₂(x²). Таким образом, в качестве пункта размещения КС можно взять вершину x^1,2, которая является внешне-внутренней медианой графа. Выбор варианта построения КС будем производить таким образом, чтобы затраты на ее создание были минимальными и выполнялось условие

   (ål_i /m_o)£w_j           (iÎM^o, rÎR),                 (2.50)

      ^iÎM

     где w_j(r)- пропускная способность r-го варианта КС, расположенного в j-м пункте.

Шаг 1. Упорядочить затраты  на создание вариантов  построения КС по возрастанию:   C₁<C₂<…<C_r<…<C_n.  

Шаг 2. Посмотреть варианты построения КС в порядке  возрастания затрат на их создание до тех  пор, пока не будет  выполняться условие (2.50).

Шаг 3. Если условие (2.50) выполняется, то за j-й КС закрепляется

r-е ТС с производительностью W_j(r). Если условие (2.50) не выполняется, то j=j+1 и перейти к шагу 1.

Шаг 4. Если j£m, то перейти к шагу 5. Иначе j=j+1 и перейти к шагу 1.

Шаг 5. Вычислить  внешние (или внутренние) передаточные числа n₁(x_i) (или n₂(x_i)).

Шаг 6. Определить внешне-внутреннюю медиану графа  с помощью выражений (2.48) и (2.49). Конец  алгоритма.