Постановка задачи. Цель: Выбрать оптимальную топологию базовой сети передачи данных

Сетевое обеспечение КИС

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

Цель: Выбрать оптимальную топологию базовой сети передачи данных

Для создания крупномасштабных КИС вычислительные комплексы объединяются с помощью средств передачи данных в вычислительную сеть. Сеть передачи данных состоит из линий связи и узлов связи.

Узел связи - совокупность средств коммуникации и передачи данных в одном пункте.

Узел связи принимает данные, поступающие по каналам связи, и передает данные в канал, ведущий к абонентам.

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

Тип топологии определяет основные параметры сети:

• производительность;
• надежность;
• время доставки сообщения;
• цена обработки данных.

Топологию сети удобно описывать в виде графа.

Графом называется совокупность множества вершин V и дуг U.

Если сопоставить каждой дуге и вершине число (вес) из некоторого множества W, то в результате получим взвешенный граф.

Две вершины называются смежными, если они соединяются одной дугой.

Граф называется полным, если между любыми двумя вершинами существует дуга.

В лабораторной работе рассматривается следующая задача:

Имеется множество узлов сети X от 1 до n, и известен объём информации a_xy, передаваемой между узлами x, y Î X. Пусть t - пропускная способность одного канала связи.

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

где - число единичных каналов между узлами k и l;

- стоимость аренды одного канала между узлами k и l.

При этом должны выполняться следующие условия:

• для передачи информации между узлами x и y используется один путь;
• путь передачи потока a_xy выбирается независимо от выбора путей передачи остальных потоков;

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

Для решения поставленной задачи можно использовать алгоритм последовательного определения путей для каждой пары узлов.

Дата добавления: 2014-11-06