Выбор маршрута

Случайные путевые процедуры есть определенные пра­вила, по которым выбор следующего узла, который будет посещен, производится в соответствии с некоторым веро­ятностным распределением по множеству соседних узлов). В этой главе мы соединим группу узлов друг с другом и применим случайную путевую процедуру к результиру­ющей сети. В результате этого исследования возникают два интересных вывода: во-первых, мы обнаруживаем, что для частного класса случайных путевых процедур мы мо­жем определить ожидаемое число шагов, которое сообщение должно проделать до прибытия к своему адресату. Во-вто­рых, мы выводим выражение математического ожидания времени, проводимого сообщений в сети. Для анализа мы используем пашу модель с включением предположения о независимости.

Разумно спросить, почему интересны именно случай­ные путевые процедуры. Их основное преимущество со­стоит и том, что они просты как в принципе, так и в реали­зации в практических системах. Другое достоинство за­ключается в том, что системы, работающие со случайной путевой процедурой, относительно нечувствительны к изменениям структуры сети, т. е. при выпадении каналов путевая процедура продолжает функционировать без су­щественного ухудшения характеристик. Кроме того, так кап при случайной процедуре но используется информация о направлениях, то нет необходимости на всех узлах знать об изменениях структуры сети. Этот факт становится все более важным в военной или меняющейся обстановке, ког­да изменения сети происходят постоянно. Если было бы необходимо передавать по сети информацию об изменениях на всех узлах, то сеть легко могла бы переполниться толь-ко информацией о направлениях и, таким образом, не оста­валось бы канальной емкости для потоков сообщений. Кроме того, можно добавить, что случайная путевая про­цедура является одной из немногих процедур, для кото­рых возможно получить осмысленные математические результаты. Таким образом, они могут служить в качестве меры качества характеристик других путевых процедур.

Ясно, что существует ряд недостатков, присущих случайпой путевой процедуре. Главная трудность состоит в том, что процедура не иснользует определенной доступ­ной информации. В частности, при известной топологии се­ти и адресации сообщений определенные пути должны иметь преимущество перед другими; случайная путевая процедура не требует и не использует эту информацию. В результате сообщения должны следовать но случайным путям. Когда, наконец, сообщению повезет настолько, что оно будет передано своему адресату, оно выпадает из сети. В 1962 году Р. Проссер 1401 предложил приближен­ный анализ случайной путевом процедуры в коммуникаци­онной сети, в котором он показал, что эта процедура паи-' более неэффективна в смысле задержки сообщений, но предельпо устойчива (т. е. она относительно не затрагива­ется небольшими изменениями структуры сети.)

Общий результат применения случайного определе­ния пути состоит в увеличении внутренних потоков, которые требуется передавать по сети; соответственно внеш­ние потоки, которые могут быть введены в сеть, значитель­но уменьшаются. Кроме того, растет время, которое сооб­щение проводит в сети; это ухудшает качество обслужива­нии потребителя системы.