Xl Туполевские чтения : всероссийская (с международным участием) молодежная научная конференция. Казань, 8-10 октября 2003 г., тезисы докладов. Т. 3

Методика оптимизации распределения потоков А.Ю. ГурскиР! Научный руководитель: А.В. Пушнин, к.т.н., доцент Таганрогский государственный радиотехнический университет Предложенная методика позволяет определить максимальную пропу­ скную способность сети передачи данных между любыми двумя ее узлами. Модель сети представляется в виде графа с указанными на нем пропу­ скными способностями линий и номерами узлов. Возьмем любой поток и последовательно увеличим его до величины, предельно возможной для передачи от узла источника S к узлу полу­ чателю Т. Определим любое простое распределение потока, при котором не пре­ вышаются пропускные способности любых из линий маршрута. Определим путь, по которому может быть передан дополнительный поток, для этого используем процесс маркирования узлов, аналогичный ПОИСК)' пути через лабиринт. Начиная от узла S, перебираем по очереди каждое направление, если ОНО позволяет пропустить еще несколько единиц потока, то его можно вы­ брать как начало пути. Присвоим, новому узлу метку (N, К), где N обозначает узел, из кото­ рого может быть получен поток, идущий от S, а К - дополнительное коли­ чество передаваемых единиц потока. После рассмотрения всех возможных путей, и присваивания меток из этого узла, будем считать его определенным и к нему больше не возвраща­ емся. Затем переходим к маркированным узлам и определяем, куда может быть передан дополнительный поток и присваиваем метки. После чего данный узел можно считать определенным. Этот процесс будет продолжаться, пока не достигнем конечного узла. Для завершения процесса поиска пути, найденный путь просматрива­ ется в обратном направлении, начиная от узла Т, т.к. возможный поток мог бы на любом этапе сократиться из-за ограничения на пропускную способ­ ность линий. В результате мы получим максимальный поток S-T. Данная методика позволяет произвести оптимизацию распределения потоков, что составляет часть обшей процедуры оптимизации структуры сети. В дальнейшем эту методику можно алгоритмизировать и представить в виде программного продукта для управления маршрутизаторами. 141