Маршрутизация: различия между версиями

Маршрутизация является одной из самых широко используемыъ техник в современных компьютерных сетях. Под маршрутизацией понимается выбор путей в сети, по которым следует отправлять данные. Спрос обычно возникает случайным образом в некоторых узлах сети, и алгоритмы маршрутизации должны быть способны отправить данные по месту их назначения. Данные пересылаются через промежуточные узлы при помощи соединительных звеньев, учитывая топологию сети. Пользователь ждет от сети гарантии наличия необходимой прлопускной способности в процессе передачи данных, что означает, что сеть ведет себя так, словно ее узлы напрямую соединены физическим каналом связи. Подобный сервис носит название постоянного виртуального соединения (permanent virtual circuit, PVC). Для моделирования реальных ситуаций будем предполагать, что спрос возникает в режиме онлайн, задается точкой-источником и точкой-получателем и включает требования к пропускной способности.

Существуют два фундаментальных подхода к разработке алгоритмов маршрутизации. Первый подход заключается в адаптивной маршрутизации (adaptive routing), учитывающей фактическую загрузку узлов или каналов связи. Второй подход заключается в маршрутизации в отсутствие информации (oblivious routing), без использования каких-либо данных о текущем состоянии сети. Далее будет рассматриваться только второй подход.