ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ  ГОСУДАРСТВЕННОЕ  ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ ВЫСШЕГО  ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ 
 

КАМСКАЯ ГОСУДАРСТВЕННАЯ 

ИНЖЕНЕРНО-ЭКОНОМИЧЕСКАЯ АКАДЕМИЯ 
 
 

Кафедра «ПИУ» 
 
 
 
 
 
 
 

КОНТРОЛЬНАЯ РАБОТА 

на  тему «Основные подходы к выбору структуры информационно-вычислительной сети и оптимизации ее параметров». 

Вариант № 2, 6. 
 
 
 
 
 
 
 

                                                Выполнил: студент гр. 4367-с

                                                Богатова Н.П. 

                                                Проверил: доцент

                                                Зубков Е.В. 
 
 
 
 
 

Набережные  Челны

2010 г.

 

Содержание 
 

 

Задание.

 
       

1. Для заданного  варианта (табл.1) построить обобщенный критерий оптимальности прокладки вычислительной сети.
2. Методом Форда найти оптимальное решение по прокладке вычислительной сети.
3. Рассчитать все возможные значения маршрутов прокладки вычислительной сети, определить наилучший и сравнить с результатом, полученным по методу Форда.

 

Теоретическая часть

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

      Каждой  вершине может приписываться  некоторый набор чисел:

• пропускная  способность  узла, 
• стоимость узла и т.п. 

      Каждое  ребро может иметь вес в  виде набора чисел: 

• длины линии,
• пропускной способности,
• стоимости и т.п.

      Для записи структуры сети и количественных оценок ее элементов используют матрицы (таблицы):

• Матрица связности (смежности);
• Матрица длин ребер (каналов связи);
• Матрица пропускных способностей  (емкостей) ребер (максимальное число бит в секунду, которое может быть пропущено по ребру);
• Матрица стоимости (стоимость ребра между пунктами).

      Используется два подхода к выбору критериев оптимизации:

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

      2. На  основе  исходного  множества  параметров  строится обобщенный критерий, наиболее полно характеризующий систему, при этом задача обычно сводится к нахождению безусловного экстремума.

      При первом подходе обычно используют такие  критерии, как: средняя задержка в  сети, стоимость сети и т.д. При втором подходе используют различные комбинации перечисленных параметров (например, произведение стоимости и средней задержки в сети).

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

      Простейший  пример оптимизации отдельного критерия ВС, представляет собой решение сетевой  транспортной задачи методом Форда. 
 
 
 
 
 
 
 
 
 
 
 

 

Решение  контрольной работы.

    Таблица 1.

Примечание. В  таблице 1: 1к – 1 000 бит/с; 1М – 1 000 000 бит/с.

      Транспортная  сеть может быть представлена в виде графа (рис.1), дуги которого – транспортные магистрали, а узлы – пункты отправления и назначения. Графически транспортная сеть изображается в виде совокупности n пунктов P₁,P₂,...,P_n, причем некоторые упорядоченные пары (P_i,P_j) пунктов назначения соединены дугами заданной длины r(P_i,P_j)=l_ij. Некоторые или все дуги могут быть ориентированы, т.е. по ним возможно движение только в одном направлении, указанном стрелками.

                                       

            

                                  
 
 
 

Рис. 1

      На  рисунке построена ориентированная транспортная сеть, содержащая шесть пунктов P₁,P₂,...,P₆, которые связаны между собой восьмью транспортными путями.

     Необходимо  определить кратчайший маршрут из пункта P₁ в P₆. Определение кратчайшего маршрута состоит в указании последовательности прохождения маршрута через промежуточные пункты и суммарной длины маршрута. Для решения данного типа задач применяют Метод Форда. 

     Этап 1. Составление исходной таблицы расстояний.

    Таблица 2.

      P_{i –} пункты отправления;

      P_j   - пункты назначения;

     Кратчайший  маршрут из пункта P₁ в P₆ :

        

     Этап 2. Определение значений параметров l и заполнение данной таблицы с учетом рассчитанных коэффициентов l_i и l_j, i, j=1..n.

l₁ = 0;

l₂ = min(l₁+l_1,2) = min(0+1,9) = 1,9;

l₃ = min(l₁+l_1,3) = min(0+16) = 16;

l₄ = min(l₂+l_2,4; l₃+l_3,4) = min(1,9+0,21; 16+1,7) = min(2,11; 17,7) = 2,11;

l₅ = min(l₂+l_2,5; l₃+l_3,5) = min(1,9+3,2; 16+50) = min(5,1; 66) =5,1;

l₆ = min(l₄+l_4,6; l₅+l_5,6) = min(2,11+20; 5,1+3) = min(22,11; 8,1) = 8,1; 

Таблица 3.

 

      Этап 3. Определение длины кратчайших путей. Знаком «+» будем отмечать неравенство удовлетворяющее (2), а знаком «–» – неравенство удовлетворяющее (3).

      Определение длины кратчайших путей.

      Возможны  два случая определения длины  кратчайших путей из пунктов P_i в пункты P_j, i=1,2,...,n; j=1,2,...,n.

      В первом случае, если выполняются неравенство:

      l_j – l_i £ l_ij; l_ij¹0; j=1,2,...,n; j=1,2,...,n,          (2)

то значения параметров l₁,...,l_n удовлетворяют условиям оптимальности. Каждое значение l_j есть не что иное, как кратчайшее расстояние от пункта P_i до пункта P_j, j=2,3,...,n.