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

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

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