Проектирование реляционных баз данных. Ковалев А.В - 27 стр.

ляется полученный таким образом поток максимальным или нет, следует просмотреть все дру-
гие возможные пути, ведущие от vs к vt. Для этого необходимо возвратиться в vs и повторить
описанные выше действия, но идти следует по еще не отмеченным вершинам.
       В результате выполнения указанного алгоритма возможны два варианта:
       • насыщенный путь снова приводит от vs к vt, т.е. удается найти ненасыщенные пути, и,
значит, можно увеличить потоки на их дугах;
       • в процессе поиска пути обнаруживается вершина, у которой все смежные вершины
уже отмечены, и, следовательно, новых путей, ведущих к vt, больше нет. Это указывает на то,
что в ходе выполнения алгоритма был найден максимальный поток.
       Такая тесная связь между потоком в сети и ее связностью приводит к результату, извест-
ному как теорема Уитни. Эта теорема утверждает, что в графе со связностью n любую пару уз-
лов s и t можно соединить, по крайней, мере n различными цепями, не имеющими общих узлов,
кроме s и t. Существует целый ряд подобных теорем, связывающих размеры сечений с числом
независимых цепей.

      2.4.2. Выбор пропускных способностей

        Увеличение пропускных способностей уменьшает среднюю задержку в сети, но увеличи-
вает стоимость, и это является основной особенностью задачи оптимизации. Для каждой линии
имеется зависимость между ее стоимостью (зависящей также от длины) и пропускной спо-
собностью С. Для каждого канала i имеем поток λi; Ci- пропускная способность этого канала, а
diCi - его стоимость. Предположим также, что задержка в сети зависит только от полного пото-
ка в каналах. Величины λi и di считаются заданными, а Ci необходимо найти.
        Определение средней задержки T требует анализа сложной системы массового обслужи-
вания. Для получения простой формулы для T делается ряд предположений. Во-первых, все
очереди связываются с линиями, выходящими из узла. С каждой i-й линией сопоставляется
средняя задержка на этой линии. Пусть γ - общий трафик в сети. Тогда среднее число пакетов,
находящихся в сети, есть γT (T - средняя задержка пакета). С другой стороны, число пакетов в
каждой очереди из тех же соображений есть λiTi, откуда γT= ∑λiTi.
        Поскольку время обслуживания пропорционально длине пакета, необходимо ввести еще
один параметр m, характеризующий среднюю длину пакета. В очередь на передачу поступают
как пакеты, пришедшие из других линий, так и вновь поступившие в сеть. Эти потоки пакетов
вышли из разных очередей, и поэтому интервалы между поступлениями отдельных пакетов
распределены по весьма сложному закону. Если очереди представить с помощью СМО М/М/1
(что оправдывается на практике) и учесть формулу для средней задержки в этой системе
Ti=1/(µCi-λi), то для средней задержки во всей сети, которую необходимо минимизировать, по-
лучаем:
                                        T=∑(λi/γ)[1/(µCi-λi )].
        В этом выражении не учтены время обработки пакета в узле и задержки при распростра-
нении сигнала по линии связи, а также наличие пакетов подтверждения и другой служебной
информации, передаваемой по сети.
        Поиск минимума времени T и соответствующих ему значений Ci осуществляется с по-
мощью метода неопределенных множителей Лагранжа. Распределение пропускных способно-
стей каналов, получающихся из уравнений, оказывается равным
                                           Ci=λi/µ+k diλi .
        Первое слагаемое есть минимальная пропускная способность, а второе пропорционально
квадратному корню из величины потока.
        Итак, для задач оптимального распределения пропускных способностей удалось полу-
чить точное аналитическое решение, хотя и после введения большого числа упрощающих
предположений.
                                                29