4551
правка
Алгоритмы прямой маршрутизации: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритмы прямой маршрутизации (посмотреть исходный код)
Версия от 23:39, 28 ноября 2013
, 28 ноября 2013→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == срочная маршрутизация; безбуферная коммутация пакетов; беск…») |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
На эффективность коммуникационных сетей серьезно влияет перекрытие, или конфликт пакетов, которое случается, когда два или несколько пакетов одновременно оказываются в одном и том же узле сети (маршрутизатора), и все эти пакеты пытаются покинуть узел по одному и тому же исходящему каналу. Поскольку пропускная способность каналов ограничена, конфликтующие пакеты вынуждены ждать в буферах, пока конфликты не будут разрешены. Конфликты вызывают задержки в доставке пакетов и снижают эффективность работы сети. | На эффективность коммуникационных сетей серьезно влияет перекрытие, или [[конфликт пакетов]], которое случается, когда два или несколько пакетов одновременно оказываются в одном и том же узле сети (маршрутизатора), и все эти пакеты пытаются покинуть узел по одному и тому же исходящему каналу. Поскольку пропускная способность каналов ограничена, конфликтующие пакеты вынуждены ждать в буферах, пока конфликты не будут разрешены. Конфликты вызывают задержки в доставке пакетов и снижают эффективность работы сети. | ||
Прямая маршрутизация представляет собой метод доставки пакетов, позволяющий избежать конфликтов пакетов в сети. После того, как пакет вброшен в сеть, он следует своим путем по направлению к месту назначения, не конфликтуя с другими пакетами и, вследствие этого, не испытывая задержек из-за ожидания в буферах, пока не достигнет узла-адресата. Задержка может произойти только в узле-источнике, пока пакет ожидает вброса в сеть. | [[прямая маршрутизация|Прямая маршрутизация]] представляет собой метод доставки пакетов, позволяющий избежать конфликтов пакетов в сети. После того, как пакет вброшен в сеть, он следует своим путем по направлению к месту назначения, не конфликтуя с другими пакетами и, вследствие этого, не испытывая задержек из-за ожидания в буферах, пока не достигнет узла-адресата. Задержка может произойти только в узле-источнике, пока пакет ожидает вброса в сеть. | ||
В формулировке задачи прямой маршрутизации сеть моделируется графом, в котором все узлы синхронизированы с одним общим датчиком времени. Каналы сети являются двунаправленными, и в каждый момент времени каждый канал могут пересекать только два пакета – по одному в каждом направлении. Время маршрутизации для заданного набора пакетов определяется как промежуток между вбросом первого пакета и доставкой последнего. | В формулировке задачи прямой маршрутизации сеть моделируется графом, в котором все узлы синхронизированы с одним общим датчиком времени. Каналы сети являются двунаправленными, и в каждый момент времени каждый канал могут пересекать только два пакета – по одному в каждом направлении. [[время маршрутизации|Время маршрутизации]] для заданного набора пакетов определяется как промежуток между вбросом первого пакета и доставкой последнего. | ||
Рассмотрим набор из N пакетов, в котором у каждого пакета имеется свой узел-источник и свой узел-адресат. Цель [[задача прямой маршрутизации|задачи прямой маршрутизации]] состоит в первую очередь в нахождении набора путей по сети для пакетов, а затем в нахождении подходящего времени вброса пакетов в сеть, так что вброшенные в нужный момент пакеты смогут проследовать до места назначения без конфликтов. [[задача прямого планирования|Задача прямого планирования]] представляет собой вариацию задачи прямой маршрутизации, в которой пути пакетов заданы априори, и нужно только вычислить подходящее время для вброса пакетов в сеть. | |||
Цель любого алгоритма (как прямой маршрутизации, так и прямого планирования) заключается в достижении минимального времени маршрутизации для пакетов. Обычно прямые алгоритмы являются оффлайновыми, т.е. пути и план вброса рассчитываются заблаговременно, до момента собственно вброса, поскольку для расчетов требуется наличие информации обо всех пакетах, чтобы гарантировать отсутствие конфликтов между ними. | Цель любого алгоритма (как прямой маршрутизации, так и прямого планирования) заключается в достижении минимального времени маршрутизации для пакетов. Обычно прямые алгоритмы являются оффлайновыми, т.е. пути и план вброса рассчитываются заблаговременно, до момента собственно вброса, поскольку для расчетов требуется наличие информации обо всех пакетах, чтобы гарантировать отсутствие конфликтов между ними. | ||