Эффективные алгоритмы и программные средства реализации линейных диофантовых моделей сетей ЭВМ

Сложность сетей ЭВМ постоянно возрастает за счет введения новых протоколов, роста числа приложений и их требований к качеству обслуживания. Этот рост приводит к усложнению прикладных технических задач управления сетевыми системами, что, в свою очередь, требует развития соответствующих методов математического моделирования. В моделях сетей ЭВМ необходимо учитывать дискретность как самих сетей (напр., топология и характеристики линии связи), так и возможных управляющих воздействий на них (напр., переключение маршрута или кратное увеличение пропускной способности линии связи), а также большую размерность (число ЭВМ порядка 102−106), см., напр., [32,53,72].

Традиционно решение многих задач управления сетями основано на графовых моделях и их обобщениях (напр., гиперграфы), реализация которых использует базовые алгоритмы на графах (напр., поиск простых контуров, кратчайших путей, оптимальных потоков) и методы целочисленного линейного программирования (ЦЛП) [12,10,13,74]. На практике этот подход может приводить к затруднениям [60,93,82,87].

Так, кратчайшие пути могут порождать перегрузку линий связи, линейность целевой функции не всегда адекватна на практике, оптимизационные задачи дают только одно решение, поиск альтернативных решений и различные обобщения графовых моделей требуют многократного использования базовых алгоритмов. В ряде случаев этих затруднений можно избежать применяя модели на основе систем однородных неотрицательных линейных диофантовых уравнений (одНЛДУ) и базисов Гильберта (линейные диофантовы модели). [17,19,64,56,80].

Системой одНЛДУ называется система, коэффициенты которой — целые числа, а неизвестные — неотрицательные целые. Конечный и единственный базис Гильберта однородной системы НЛДУ (системы одНЛДУ) представляет собой множество всех ее неразложимых решений за исключением нулевого. Традиционно системы НЛДУ исследовались в теории чисел [5] и комбинаторном анализе [70]. Концепция базиса Гильберта появляется в исследованиях ученых D. Hilbert, P. Gordan, J. G. van der Corput, E. B. Elliot и P. A. MacMahon (см. исторические справки в [36,85,39,50]). Термин «базис Гильберта» дан F. Giles и W. Pulleyblank [57] в ходе развития теории вполне двойственной целочисленности и целочисленных полиэдров [10,36,37]. Сложность задачи решения таких систем исследуется в работах В. Н. Шевченко [37], Н. К. Косовского [20], A. Schriever [36], L. Pottier [79], М. Henk [59], L. Juban [50], J.-F. Romeuf [83] и др.

Базис Гильберта используется в самых разнообразных приложениях. Так, при автоматизации дедуктивных построений задача ассоциативно-коммутативной унификации сводится к решению системы одНЛДУ, где базис Гильберта определяет минимальный полный набор унификаторов [88, 52,41,90]. В целочисленном программировании этот базис используется при построении универсального тестового множества для семейства целочисленных задач [36,39]. В задачах управления памятью и распараллеливания программ доступ к данным (кэш-память, массивы) описывается системой НЛДУ, решения которой определяют повторные обращения [80,56].

Базис Гильберта представляется удобным инструментом для описания дискретных свойств сетей ЭВМ. Известно, что базис системы одНЛ-ДУ, построенной по матрице инцидентности графа сети, определяет простые контуры в графе. Они используются при решении задач обеспечения надежности и устойчивости сети к сбоям [67,87]. При идентификации структуры нагрузки канала передачи данных базис Гильберта определяет главные источники нагрузки [17]. В самоорганизующихся и одноранговых сетях этот базис описывает маршруты с заданными свойствами [19,64].

Таким образом, актуальной является проблема развития методов моделирования сетей ЭВМ на основе систем одНЛДУ pi их базисов Гильберта. В диссертационной работе эта проблема рассматривается на примере актуальной прикладной технической задачи — восстановления соединений в сети ЭВМ. Ее актуальность вызвана ростом числа чувствительных к задержкам приложений (напр., потоковый звук и видео). Существующие методы восстановления (напр., IP reroute [95,87]) не обеспечивают гарантированного времени восстановления. Кроме поиска возможных маршрутов, необходимо выполнять отбор маршрутов-кандидатов на основе дополнительных критериев. Например, некоторые маршруты могут не подходить из-за загруженности линий связи.

Задача восстановления соединений особенно актуальна для технологии многопротокольной коммутации с использованием меток (Multiprotocol label switching, MPLS) [84,73], позволяющей значительно уменьшать время выбора направления пересылки пакета и выполнять рационализацию (инжиниринг [30,8,72]) трафика. Технология MPLS имеет общий механизм восстановления, включающий поиск маршрута [86]. В [60] предложен алгоритм Short Leap Shared Protection (SLSP) для поиска маршрута восстановления. Используемая в алгоритме SLSP-модель основана на поиске простых циклов в графе сети по которому отбираются маршруты-кандидаты, а затем выбор оптимального маршрута решается задачей ЦЛП. Трудоемкость последней зависит от числа выбранных простых циклов [71,36].

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

В диссертационной работе предлагается иерархия линейных диофантовых моделей сети MPLS в виде систем одАНЛДУ для замены SLSP-модели. Предложенные модели используют базис Гильберта для описания кандидатов на маршрут восстановления, а для их отбора предлагается использовать содержательный нелинейный критерий — кумулятивную характеристику маршрута, которая более адекватно учитывает наличие неэффективных линий связи в маршруте.

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

Линейные диофантовы модели представляют интерес пе только для модификации алгоритма SLSP, но могут быть использованы pi при решении других задач, связанных с сетями MPLS. Так, в вычислительных экспериментах с сетью MPLS необходимо определять входную нагрузку. Для каждого входного маршрутизатора указываются сценарии поступления пакетов в сеть, что отражается на загрузке линии связи. В этом случае предложенная иерархия моделей может быть использована для поиска основного маршрута соединения с учетом оптимального распределения нагрузки по всей сети.

Применение предлагаемых моделей возможно при условии наличия эффективных алгоритмов нахождения базиса Гильберта (НБГ) и их протестированных реализаций. Однако в этой области существует серьезный пробел. В настоящее время предложен ряд алгоритмов НБГ для случая произвольных одНЛДУ и их систем на основе различных математических методов: верхние границы компонент базисных решений [62,79,59]- элементарные преобразования матриц [66]- покомпонентное построение решений, начиная с пулевого [45,46]- преобразования производящих функций (метод Elliott — MacMahon) [70,49,77,40]- нахождение базисных решений с минимальным носителем и последующим построением оставшихся базисных решений как рациональных положительных комбинаций [48,91,65]- нахождение базиса Гребнера идеала в кольце полиномов [79,78].

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

Задача НБГ является вычислительно трудоемкой, поскольку число базисных решений в худшем случае экспоненциально зависит от размерности системы и абсолютных величин ее коэффициентов [36,50]. В этом случае эффективным можно считать псевдополиномиальный алгоритм, сложность которого ограничена полиномиально не только в зависимости от числа уравнений и неизвестных, но и от числа базисных решений [42,17].

Такое положение определяет актуальность исследований частных классов систем одНЛДУ для построения специализированных эффективных алгоритмов НБГ. Например, в случае системы одНЛДУ из двух уравнений, время нахождения базиса Гильберта полиномиально по числу неизвестных и максимальному значению коэффициентов [83].

М. Filgueiras и A. Tomas показали, как систему НЛДУ можно ассоциировать с контекстно-свободной (КС) грамматикой (сокращенно — система АНЛДУ) [54]. Авторы [4], а затем Д. Ж. Корзун в [15,17] развили этот результат, предложив метод построения системы АНЛДУ по произвольной КС-грамматике и по двум цепочкам. При равенстве цепочек строится однородная система АНЛДУ (система одАНЛДУ). В диссертации используется только алгебраическое определение этих систем [15,17].

Известно, что метод последовательного исключения для систем линейных уравнений справедлив, когда и коэффициенты системы и неизвестные рассматриваются, как элементы одного множества, например произвольного поля (варианты метода Гаусса [28,3]) или кольца целых чисел Z (метод Эрмита [13]). В то же время неизвестны аналоги этого метода, когда коэффициенты являются элементами множества Z, а неизвестные — элементами множества неотрицательных целых чисел Z+.

Таким образом, актуальной является задача построения эффективного алгоритма НБГ системы одАНЛДУ на основе метода последовательного исключения уравнений и неизвестных.

Автором предлагается и обосновывается алгоритм — аналог метода исключения, позволяющий решать как задачу НБГ, так и задачу генерации систем одАНЛДУ с известным базисом Гильберта (НБГ системы). Последние включают тестовые, эталонные и модельные системы одАНЛДУ, структурно соотвествующие реальным сетям MPLS (М-системы). Для практического применения алгоритма необходимы тестирование и экспериментальная оценка эффективности его реализации, в том числе по сравнению с реализациями других алгоритмов.

Таким образом, актуальной является задача программной реализации алгоритмов НБГ и разработки программных средств для их тестирования, экспериментального и сравнительного анализа, оценки эффективности предлагаемых моделей на М-системах и представления результатов исследований в Web-пространстве.

Эти задачи решаются с помощью разработанного автором комплекса программ. Тестирование позволяет проверить корректность реализации алгоритма на наборе тестовых систем [35]. При этом необходимы разработка и реализация ПО измерения эффективности и автоматической генерации и проверки тестов.

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

Цель исследования формулируется следующим образом.

1. Развитие метода последовательного исключения для частного класса — систем одАНЛДУ, коэффициенты которых принадлежат Z, а неизвестные — Z+. Разработка, обоснование, реализация, тестирование и экспериментальное исследование алгоритмов НБГ и генерации этих систем.

2. Разработка, обоснование и реализация линейных диофантовых моделей сетей MPLS для использования в алгоритме SLSP, а также проверка эффективности алгоритмов НБГ на сгенерированных М-системах.

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

Научная новизна работы отражена в следующих положениях.

Для решения задачи восстановления соединений в сетях MPLS впервые предложено использовать линейные диофантовы модели па основе систем одАНЛДУ и базисов Гильберта.

Впервые предложены и обоснованы преобразования систем одАНЛДУ к трапециевидной форме и обратной подстановки базиса Гильберта для случая, когда коэффициенты системы принадлежат Z, а неизвестные.

Разработан, обоснован и протестирован новый алгоритм НБГ произвольной системы одАНЛДУ, имеющий лучшие теоретические и экспериментальные оценки по сравнению с известными алгоритмами.

Разработаны и обоснованы пять алгоритмов генерации частных классов ИБГ систем одАНЛДУ. Ранее задача построения тестовых примеров решалась с помощью полученных вручную малых наборов систем или непосредственной (без построения базиса Гильберта) генерацией.

Объектами исследования в работе являются сети MPLS, системы одАНЛДУ и базисы Гильберта, а предметом исследования — линейные ди-офантовы модели сетей ЭВМ, алгоритмы НБГ и генерации систем одАНЛДУ, сложность алгоритмов, программные реализации алгоритмов и средства их экспериментального исследования.

Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка использованной литературы (98 наименований), пяти приложений, имеет объем 136 машинописных страниц и 34 страницы приложений, содержит 25 рисунков и 12 таблиц.

Выводы.

В главе 4 представлен разработанный комплекс программ и описаны результаты проведенных с его помощью экспериментальных исследований программных реализаций алгоритмов НБГ и генерации ИБГ систем одАНЛДУ. Результаты позволяют сделать положительный вывод о практической применимости разработанных автором алгоритмов для реализации линейных диофантовых моделей сетей ЭВМ.

Разработанная автором ПС alganalyser автономно тестирует программные реализации и измеряет потребление ресурсов. Автором реализованы алгоритм НБГ TransSol и алгоритмы генерации GaussGen, JordanGen,.

ExtGaussGen и SymGen. Полученный комплекс программ может быть использован для широкого круга прикладных задач, связанных с решением систем одНЛДУ.

Автором выполнено экспериментальное исследование из трех частей: I) тестирование алгоритма решения SyntacticII) сравнение алгоритмов решения SlopesSys и SyntacticIII) сравнение алгоритмов решения TransSol и Syntactic при использовании в линейных диофантовых моделях сети MPLS. Получен вывод о практической применимости алгоритмов решения Syntactic и TransSol для систем одАНЛДУ, размерности которых соответствуют размерностям реальных сетей MPLS: общее время в пределах десятков секунд для m, q ~ 103. Показано, что алгоритм TransSol превосходит алгоритм Syntactic для такого класса систем одАНЛДУ: потребление памяти и общее время меньше на 10−35% и до двух раз, соответственно.

Заключение

.

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

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

Проведен анализ алгоритмов НБГ систем одНЛДУ, показавший необходимость разработки эффективных алгоритмов численного решения этой задачи для использования в линейных диофантовых моделях. Для систем одАНЛДУ разработаны и обоснованы преобразования к трапециевидной форме и подстановки базиса Гильберта, являющиеся развитием общего метода исключения неизвестных и уравнений для случая, когда коэффициенты системы принадлежат Z, а неизвестные — Z+.

На базе этих преобразований предложен и обоснован псевдополиномиальный алгоритм НБГ произвольной системы одАНЛДУ. Определен подкласс систем одАНЛДУ, для которого сложность алгоритма TransSol не зависит от размеров промежуточных систем. Также разработаны и обоснованы алгоритмы генерации ИБГ систем.

Разработанные алгоритмы реализованы в виде комплекса программ, обеспечивающих тестирование и экспериментальное исследование алгоритма НБГ, в том числе, для М-систем. Комплекс также обеспечивает доступ к алгоритмам из web пространства.

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