Алгоритми маршрутизації в мережах, Детальна інформація
Алгоритми маршрутизації в мережах
b) Якщо N – маршрутизатор або кінцева система OSI, і більше не існує суміжних вершин {Adj(M)}, то видалимо надлишкову вершину.
c) Якщо x < dist(P,N), нічого.
d) Якщо x > dist(P,N), видалити з TENT, та додати
5) Якщо не в TENT, додати в TENT.
Крок 2: Якщо TENT пустий, зупинитися. Інакше:
1) Знайти елемент , з мінімальним x таким чином:
a)Якщо елемент <*,tentlength,*> залишився в TENT в списку для tentlength, вибрати цей елемент. Якщо в списку існує більше одного елементу, вибрати один з цих елементів для системи, що є псевдовершиною, вибрати ту, що не є псевдовершиною. Якщо більше нема елементів в списку для tentlength, збільшити tentlength і повторити Крок 2.
b)Видалити з TENT.
c) Додати в PATHS.
d) Якщо система тільки що додана в PATHS – кінцева система, то перейти в Крок 2. Інакше : перейти в Крок 1.
Позначення:
PATHS – представляє ациклічний граф найкоротших шляхів від системи S. Він представляється як набір триплетів, де N ідентифікатор системи. d(N) загальна відстань від N до S).
{Adj(N)} –набір працюючих сусідів S, що їх можна використати N. Якщо система є в PATHS, шляхи, що відповідають цьому місцю є найкоротшими.
TENT – список триплетів у вигляді, де N, d(N) та {Adj(N)} відповідають визначеним в PATHS.
TENT може бути інтуітивно представлений як місце системи в PATHS. Іншими словами, триплет в TENT говорить, що, якщо N є в PATHS, d(N) відповідає x, але N не може бути розміщене в PATHS поки не доведено, що не існує шляхів, коротших за x .
Так само в TENT значить, що якщо N є в PATHS, тоді d(N) буде дорівнювати x для маршрутів, що проходять через суміжну вершину A або через суміжну вершину B.
Запропоновано в реальній реалізації таблиці TENT проводити сортування за характеристикою d(N).
3. Висновки
Маршрутизаційні алгоритми реалізовані на різних типах мереж від локальних до глобальних. Широко розповсюдженим є демон Routed з дистриутиву університету Каліфорнії в Берклі він реалізований в протоколі RIP. Також велике значення мають реалізації алгоритму відкриття найкоротшого маршруту для подвійного середовища OSI та TCP/IP в плані знаходження маршрутів між інтер-автономними системами та маршрутизаторами TCP/IP архитектури.
Глоссарій
OSI – мережна модель, запропонована організацією по стандартизації ISO
IS – Interautonomous system – інтеравтономна система, система, що приймає участь в маршрутизації в моделі OSI
ES - End System-кінцева система, система, що не приймає участі в маршрутизації в моделі OSI
Router – маршрутизатор, об’єкт маршрутизації
Gateway – шлюз, система, що має декілька мережних інтерфейсів
RIP (Routing Information Protocol) – маршрутизаційний інформаційний протокол
c) Якщо x < dist(P,N), нічого.
d) Якщо x > dist(P,N), видалити
5) Якщо
Крок 2: Якщо TENT пустий, зупинитися. Інакше:
1) Знайти елемент , з мінімальним x таким чином:
a)Якщо елемент <*,tentlength,*> залишився в TENT в списку для tentlength, вибрати цей елемент. Якщо в списку існує більше одного елементу, вибрати один з цих елементів для системи, що є псевдовершиною, вибрати ту, що не є псевдовершиною. Якщо більше нема елементів в списку для tentlength, збільшити tentlength і повторити Крок 2.
b)Видалити з TENT.
c) Додати в PATHS.
d) Якщо система тільки що додана в PATHS – кінцева система, то перейти в Крок 2. Інакше : перейти в Крок 1.
Позначення:
PATHS – представляє ациклічний граф найкоротших шляхів від системи S. Він представляється як набір триплетів
{Adj(N)} –набір працюючих сусідів S, що їх можна використати N. Якщо система є в PATHS, шляхи, що відповідають цьому місцю є найкоротшими.
TENT – список триплетів у вигляді
TENT може бути інтуітивно представлений як місце системи в PATHS. Іншими словами, триплет
Так само
Запропоновано в реальній реалізації таблиці TENT проводити сортування за характеристикою d(N).
3. Висновки
Маршрутизаційні алгоритми реалізовані на різних типах мереж від локальних до глобальних. Широко розповсюдженим є демон Routed з дистриутиву університету Каліфорнії в Берклі він реалізований в протоколі RIP. Також велике значення мають реалізації алгоритму відкриття найкоротшого маршруту для подвійного середовища OSI та TCP/IP в плані знаходження маршрутів між інтер-автономними системами та маршрутизаторами TCP/IP архитектури.
Глоссарій
OSI – мережна модель, запропонована організацією по стандартизації ISO
IS – Interautonomous system – інтеравтономна система, система, що приймає участь в маршрутизації в моделі OSI
ES - End System-кінцева система, система, що не приймає участі в маршрутизації в моделі OSI
Router – маршрутизатор, об’єкт маршрутизації
Gateway – шлюз, система, що має декілька мережних інтерфейсів
RIP (Routing Information Protocol) – маршрутизаційний інформаційний протокол
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021