Cтраница 3
Моделирование показало, что для сбалансированной со стабильными потоками сети А ( рис. 5.7) случайная маршрутизация дает хорошие результаты и, наоборот, при резких колебаниях потока алгоритм случайной маршрутизации существенно хуже эвристических алгоритмов. [31]
Из матрицы HOPS ( i, j) с учетом значения D определяется достижимость из данного узла i - ro узла-адресата, а из матрицы COST ( i, /) - выходящий канал, соответствующий минимальному элементу в t - м векторе матрицы. Алгоритм маршрутизации может поддерживать альтернатив ные пути. В этом случае в таблицах повторяются строи с одним и тем же узлом-адресатом. Если цена всех кана лов одинакова, то выбирается путь с наименьшим переприемов. [32]
Опыт показал, что централизованные алгоритмы более эффективны в глобальном смысле, выбор маршрутов в каждом узле последовательно основывается на состоянии всей сети. Алгоритмы распределенной маршрутизации эффективны в основном в локальных участках; решения, принимаемые в отдельных узлах, часто оказываются несогласованными, возникает зацикливание пакетов. С другой стороны, эти алгоритмы быстро реагируют на изменение потоков данных и ресурсов в локальных участках сети. [33]
Алгоритм дельта-маршрутизации обладает преимуществом перед другими алгоритмами, когда в сети происходят скачкообразные изменения шумового потока. При этом централизованный алгоритм маршрутизации в сети виртуальных каналов ( ЦМВ) дает наихудшие результаты в случае сети Б, так как выбор маршрутов не корректируется продолжительное время, определяемое длительностью сеанса связи. [34]
Сети с КП имеют разветвленную иерархическую структуру, что осложняет решение задачи управления сообщениями. Алгоритмы управления включают в свой состав алгоритмы маршрутизации и организации нагрузки. При реализации датаграммного режима задача выбора пути или задача маршрутизации является более сложной, чем в сети с виртуальными соединениями. В этом случае устройства управления должны определять оптимальный путь для каждого пакета. В центре КП необходимо иметь таблицу маршрутизации, содержащую информацию о всех направлениях, по которым можно передать датаграмму. Очевидно, что в сетях большой размерности такие таблицы могут быть весьма громоздкими и трудно обрабатываемыми, что может привести к росту задержек. [35]
Маршрутизация в Internet организована по иерархическому принципу. Имеются уровни ЛВС и корпоративных сетей; маршрутных доменов, в каждом из которых используются единые протоколы и алгоритмы маршрутизации; административных доменов, каждый из которых соответствует некоторой ассоциации и имеет единое управляющее начало. [36]
Не менее важным представляется задача проектирования верхнего уровня сети, включающего в свой состав коммутационные центры и называемого в [55] базовой сетью. Среди основных задач здесь также следует назвать определение топологии базовой сети, распределение пропускных способностей, определение процедур управления потоками и алгоритмов маршрутизации. [37]
Эффективность алгоритма в первую очередь определяется такими характеристиками, как пропускная способность ТС, время передачи информации в сети связи, устойчивость алгоритма к изменениям условий работы сети, простота реализации алгоритма, объем требуемой алгоритмом служебной информации и т.п. Сложность задачи заключается в том, что при оптимизации алгоритма маршрутизации необходимо учесть большое число сложных зависимостей характеристик ТС и параметров исследуемого алгоритма. Поэтому разработка алгоритмов маршрутизации остается задачей актуальной и вызывает интерес многих исследователей. [38]
Эффективность алгоритма в первую очередь определяется такими характеристиками, как пропускная способность ТС, время передачи информации в сети связи, устойчивость алгоритма к изменениям условий работы сети, простота реализации алгоритма, объем требуемой алгоритмом служебной информации и т.п. Сложность задачи заключается в том, что при оптимизации алгоритма маршрутизации необходимо учесть большое число сложных зависимостей характеристик ТС и параметров исследуемого алгоритма. Поэтому разработка алгоритмов маршрутизации остается задачей актуальной и вызывает интерес многих исследователей. [39]
Теоретически идеальным является алгоритм динамической маршрутизации, основанный на глобальной информации о состоянии сети. Однако возрастание скорости адаптации алгоритма связано с увеличением загруженности каналов передачей служебной информации. Поэтому на практике используют квазистатические и статические алгоритмы маршрутизации. [40]
Эти алгоритмы должны выбирать наиболее эффективные маршруты передачи данных, минимизировать время доставки данных адресатам. Проводить адекватное аналитическое исследование алгоритмов маршрутизации очень трудно. [41]
Одним из важных вопросов, возникающих при исследовании алгоритмов адаптивной маршрутизации, является вопрос, связанный с устойчивостью алгоритма, определяемой как способность алгоритма не реагировать на те изменения в сети, реакция на которые может привести к резкому снижению эффективности сети. Существующие алгоритмы квазистатической маршрутизации в основном исследованы для ТС с коммутацией пакетов. Это объясняется тем, что задачу оптимизации алгоритма квазистатической маршрутизации в ТС с коммутацией пакетов при вполне допустимых упрощающих предположениях можно разбить на более простые частные задачи, и можно получить некоторые аналитические результаты относительно сходимости исследуемых алгоритмов. Сложнее данная задача решается для сетей с коммутацией каналов. В ряде работ ( например, в [5]) для сетей с коммутацией каналов предлагаются решения, аналогичные тем, что предложены для ТС с коммутацией пакетов, основанные на предположении о независимости разных направлений связи. [42]
Мизина по созданию СОД АСУ В С в 70 - х годах выполнялись одновременно с созданием в США экспериментальной оборонной сети ARPANet, предшественницы нынешней глобальной сети Интернет. Первые четыре узла в сети ARPANet были связаны к началу 1970 г., а название Интернет было предложено В. Интересно отметить, что первоначально принятые разработчиками ARPANet методы и алгоритм маршрутизации потоков пакетов данных приводили при определенных условиях к отказу передачи. [43]
Поскольку в каждом узле сети должны быть идентичные базы данных маршрутизации, процедура распространения в сети корректирующей информации о задержках должна гарантировать получение этой информации всеми узлами и приводить при этом к малым накладным расходам. Для этого в узле формируется корректирующий пакет, который содержит данные о задержках на всех выходящих каналах, где произошли соответствующие изменения. Корректирующий пакет размножается и рассылается по всем выходящим каналам данного узла всем соседним узлам. Пакеты не содержат адреса и их распространение не зависит от алгоритма маршрутизации. В узле при получении корректирующего пакета проверяется: если такой пакет уже был получен ранее, то он уничтожается, в противном случае пакет передается далее по всем выходящим каналам, включая тот, по которому он поступил. Таким образом, узел, передавший корректирующий пакет, в течение некоторого тайм-аута ожидает от соседних узлов пакет-эхо, который играет роль квитанции. Если пакет-эхо не получен, узел повторно передает корректирующий пакет. Для того чтобы исключить случай, когда потерян лакет-эхо, корректирующий пакет при повторной передаче маркируется единицей в специальном разряде с целью вызвать пакет-эхо, даже если корректирующий пакет был ранее получен. [44]
За последние годы накоплен большой опыт моделирования сетей ЭВМ и соответствующих методов управления. Поэтому в книге на конкретных примерах отражены принципы построения таких моделей и обсуждены качественные и количественные результаты моделирования. Эти результаты нередко позволяют обоснованно выбрать протоколы и их управляющие параметры в зависимости от конкретного применения и аппаратного обеспечения сети ЭВМ. Это в первую очередь относится к методам управления каналами ( линейным протоколам), методам распределения буферов и алгоритмам маршрутизации. К сожалению, большое количество возможных структур сетей, типов каналов связи и ЭВМ и различные требования конкретных применений не позволяют в небольшой книге дать четкие инженерные рекомендации для всех случаев. [45]