Проблемы оптимизации сетей ЭВМ

В процессе системного проектирования ИВС удается получить набор компонентов сети: узлов коммутации, линий передач, концентраторов и мультиплексоров с известным набором характеристик; например, концентратор может обслуживать не более некоторого числа терминалов. Наивно предполагать, что на этой стадии проектирование завершено. Разработчик сети должен найти наилучший вариант расположения этих компонентов, который отвечал бы требованиям, предъявляемым сетевым трафиком; обычно им должен быть самый дешевый вариант, соответствующий определенному критерию эффективности сети (например, обеспечивающий задержку в сети, производительность или надежность). Эту вторую стадию процесса проектирования можно назвать оптимизацией сети.

Задача оптимизации настолько сложна, что пока не решена в общем виде, но известно множество подходов к решению ее подзадач. Рассмотрим наиболее типичные методы и подходы, уделяя основное внимание их разнообразию. Значительная часть теоретических положений приводится без доказательств.

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

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

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

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

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

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

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

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

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

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

В силу изложенных выше причин задачи оптимизации, встречающиеся на практике, могут сильно отличаться от задач, обычно рассматриваемых в литературе.

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

Комбинаторные методы имеют дело с конечными множествами и отношениями между ними. Типичным примером применения этих методов является выбор топологии сети. Узлы и линии связи сети образуют граф, свойства которого исследуются методами известной теории.

Сложность комбинаторных задач обусловлена их большой размерностью и огромным числом возможных вариантов, которые необходимо исследовать. Например, в сети из 30 узлов существует 435 вариантов соединения пары узлов линией связи и 2⁴³⁵ вариантов расположения линий связи, включая и множество тривиальных случаев. Изучение топологии сетей путем перебора всех возможных вариантов - совершенно бесперспективное занятие. Поэтому возникает потребность в более простых эвристических методах, являющихся, по существу, методами "проб и ошибок".

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

Какова бы ни была задача, часто наилучшими методами ее решения являются эвристические. Например, программа может генерировать топологии с улучшенными свойствами, пользуясь некоторыми "разумными" соображениями, вместо того чтобы использовать алгоритм с доказанной сходимостью к оптимуму. Такая программа может многократно "улучшать" потоки в сети без какой-либо гарантии оптимальности результата. Чтобы достаточно полно охватить возможные случаи, вводятся случайные изменения, и тогда одно из "наилучших решений" может оказаться близким к оптимуму. В эвристическом алгоритме решения задачи оптимизации случайным образом выбираются начальные точки, число которых должно быть достаточно большим. Результаты, полученные для различных начальных точек, сравниваются между собой. Наилучший из них выбирается в качестве истинного решения задачи.