Проста маршрутизація

Проста маршрутизація, у свою чергу, поділяється на випадкову й лавинну. При випадковіймаршрутизації пакет передається з вузла у випадково обраному напрямку, крім напрямку, яким він надійшов до вузла. Теоретично доведено, що пакет через певний проміжок часу досягне адресата. Метод характеризується значним часом доставки пакетів і неефективним використанням мережі. Незважаючи на це, різноманітні модифікації випадкової маршрутизації застосовуються у мережах з низькою інтенсивністю потоків для забезпечення сталої роботи мережі під час виходу з ладу окремих її компонентів. Можна запропонувати низку заходів щодо збільшення ефективності такого методу маршрутизації, наприклад, при повторному проходженні пакета через вузол змінювати напрямок його подальшої передачі.

В основі лавинноїмаршрутизації лежить ефект розмноження пакетів, за якого вузол, отримавши пакет, генерує ідентичні пакети і передає їх у всіх напрямках, крім того, яким надійшов пакет (рис. 8.2).

Рис. 8.2. Лавинна маршрутизація, де:

ti – напрямок передачі пакета в момент ti ;

х – знищення пакета на вході вузла комутації

Копії пакета лавиноподібно поширюються мережею. Перевагою методу є забезпечення мінімальної затримки передачі пакетів, оскільки використовуються всі шляхи через мережу, в тому числі й найкоротший, яким і прийде перший пакет. Для розглянутого випадку це шлях через вершини А₁ Þ А₃ Þ А₅ Þ А₉. Водночас, якщо кількість зв’язків між вузлами є великою, сильно проявляється ефект розмноження пакетів. Так на момент часу t₃ в аналізованому фрагменті мережі наявні дев’ять копій пакета, що позначається на пропускній здатності мережі. Вплив ефекту розмноження пакетів можна зменшити додаванням певних засобів обліку проходження пакетів через вузли комутації. Наприклад, кожен вузол може розпізнавати повторне отримання копії раніше пакета і вилучати її. Таким чином, копії пакетів поступово видаляються з мережі. На момент часу t₄ залишаються тільки дві копії пакетів, які, у свою чергу, знищуються на вході дев’ятого вузла. Цей процес називається «виродженням» пакетів і дає можливість істотно підвищити пропускну здатність мережі передачі даних.

Подальшим розвитком простої маршрутизації слід вважати маршрутизацію з попереднього досвіду, при якій забезпечується коригування попередньо вибраних випадкових маршрутів. З цією метою у пакети додаються лічильники пройдених вузлів, відповідно до вмісту яких формується адреса наступного вузла на шляху проходження пакета до одержувача. Отже, на початковому етапі маршрутизації шлях проходження пакетів може визначатися випадково або способом лавинного заповнення пакетів, а потім, під час проходження наступних пакетів, шлях їх коригується. Після проходження першого пакета певним маршрутом у кожному вузлі комутації зберігається інформація про адресу відправника, одержувача, попереднього вузла і кількість пройдених вузлів. У разі надходження пакета з такими самими значеннями адрес відправника і одержувача, але з меншим значенням лічильника пройдених вузлів, здійснюється коригування маршруту у вузлах комутації. Припустимо, що для ділянки мережі (рис. 8.3) спочатку був сформований шлях А₀ÞА₁ÞА₂ÞА₃ÞА₄ÞА_к, якому відповідають такі значення маршрутів у вузлах: А₂={А_к, А_0, А₁, А₃, 2}; А₃={А_к, А₀, А₂, А₄, 3} і А₄={А_к, А₀, А₃, А_к, 4}, де на першому місці стоїть адреса одержувача, на другому — адреса відправника, на третьому — адреса попереднього вузла, на четвертому — адреса наступного вузла і на п'ятому — кількість попередніх вузлів.

Рис. 8.3. Маршрутизація з попереднього досвіду, де:

– першочерговий маршрут;

– маршрут після корекції

За появи у вузлі А₄ пакета, що прийшов з вузла А₂, значення лічильника пройдених вузлів якого дорівнює трьом, здійснюється коригування маршруту у вузлах А₂ і А₄ на значення: А₂={А_к, А₀, А₁, А₄, 2} і А₄={А_к ,А₀, А₂, А₅, 3}. Унаслідок цього формується новий, коротший шлях: А₀ÞА₁ÞА₂ÞА₄ÞА_к, відповідно до якого пакети, що рухаються у напрямку А_к, відразу направлятимуться з вузла А₂ у вузол А₄.Отже, можна говорити про елементи адаптації, проте цей процес проходить повільно і не завжди є ефективним.