2.2. OSPF, Dual IS-IS: Алгоритм відкриття найкоротшого шляху
2.2.1.Огляд алгоритму.
Алгоритм відкриття найкоротшого шляху використовується як в IP, так і в OSI середовищі. Він має складність О(N2).
Основний алгоритм, що будує PATHS з нуля, починає додавання систем з найвигіднішими маршрутами з оглядом на PATHS (не може існувати коротшого маршруту до SELF ). Потім визначається TENT використовуючи локальні таблиці з відомостями про сусідні вершини.
Система не може бути розміщеною в PATHS до тих пір, поки не доведено, що не існує маршруту, коротшого за даний. Коли система N розміщується в PATHS, перевіряється ціна маршруту до кожної вершини M сусідньої до N через саму вершину N. Цей маршрут визначається як сума ціни маршруту до N та ціни ділянки NM. Якщо <M,*,*> розміщений в TENT та нове значення буде більшим, маршрут ігнорується.Якщо <M,*,*> розміщений в TENT та нове значення буде меншим, старий запис заміщується новим. Якщо <M,*,*> розміщений в TENT та нове значення таке ж саме як те, що вже є в TENT то набір {Adj(M)} встановлюється як поєднання старого запису (того, що міститься в TENT) та нового - {Adj(N)}. Якщо M не знаходиться в TENT, то даний маршрут додається в TENT.
Потім алгоритм знаходить триплети <N,x,{Adj(N)}> in TENT з мінімальним x.
2.2.2. Реалізація алгоритму відкриття найкоротшого шляху в DUAL IS-IS середовищі
Крок 0: Встановимо TENT та PATHS як пусті. Встановимо tentlength в 0.
(tentlength – це довжина шляху досліджуваних елементів TENT.)
1) Додамо <SELF,0,W> до PATHS, де SELF – початкова система, W –спеціальна величина, що визначає трафік до SELF що пройдений, включаючи внутрішній процес.
2) Тепер загрузимо TENT локальними даними шляхів (Кожен запис в TENT має бути визначений як маршрутизатор або кінцева система OSI, щоб дозволити правильну перевірку в Кроці 2).
Для всіх суміжних вершин Adj(N) на всіх можливих каналах:
d(N) = ціна маршруту, що проходить через (N)
Adj(N) = кількість вершин сусідніх N.
3) Якщо триплет <N,x,{Adj(M)}> в TENT, то
Якщо x = d(N), то {Adj(M)} := {Adj(M)} U {Adj(N)}.
4) Якщо N – маршрутизатор або кінцева система OSI, і більше не існує суміжних вершин {Adj(M)} то видалимо надлишкову вершину.
5) Якщо x < d(N), нічого.
6) Якщо x > d(N), видалити <N,x,{Adj(M)}> з TENT і додати триплет <N,d(N),{Adj(N)}>.
7) Якщо <N,x,{Adj(M)}> не в TENT, то додати <N,d(N),{Adj(N)}> в TENT.
8) Тепер додаються системи, для яких локальний маршрутизатор не має суміжних вершин, але вони згадані в сусідніх псевдовершинах LSP. Суміжність для таких систем визначається маршрутизатором.
9) Для всіх широковєщательних каналів в активному стані, знайти псевдовершину LSP для цього каналу. Якщо така існує, для всіх сусідів N, про які згадувається на цій вершині і не визначені в TENT, додати запис:
<N,d(N),{Adj(N)}> to TENT, where:
d(N) = ціна проміжку .
Adj(N) = кількість вершин, що стоять на шляху до заданого маршрутизатора.
10) Перейти в Крок 2.
Крок 1: Визначити нульовий PDU в LSP ситеми, щойно доданої в PATHS
1)dist(P,N) = d(P) + metric.k(P,N) для кожного сусіда N (як для кінцевої системи, так і для маршрутизатора) системи P.
2) Якщо dist(P,N) >максимальної ціни проміжку, нічого.
3) Якщо <N,d(N),{Adj(N)}> є в PATHS, нічого.
d(N) повинне бути меншим ніж dist(P,N), або N не повинне бути в PATHS. За бажанням можна зробити додаткову перевірку чи є d(N) меншим за dist(P,N).
4) Якщо триплет <N,x,{Adj(N)}> в TENT, тоді:
a) Якщо x = dist(P,N) тоді {Adj(N)}:= {Adj(N)} U {Adj(P)}.
b) Якщо N – маршрутизатор або кінцева система OSI, і більше не існує суміжних вершин {Adj(M)}, то видалимо надлишкову вершину.
c) Якщо x < dist(P,N), нічого.
d) Якщо x > dist(P,N), видалити <N,x,{Adj(N)}> з TENT, та додати <N,dist(P,N),{Adj(P)}>
5) Якщо <N,x,{Adj(N)}> не в TENT, додати <N,dist(P,N),{Adj(P)}> в TENT.
Крок 2: Якщо TENT пустий, зупинитися. Інакше:
1) Знайти елемент <P,x,{Adj(P)}>, з мінімальним x таким чином:
a)Якщо елемент <*,tentlength,*> залишився в TENT в списку для tentlength, вибрати цей елемент. Якщо в списку існує більше одного елементу, вибрати один з цих елементів для системи, що є псевдовершиною, вибрати ту, що не є псевдовершиною. Якщо більше нема елементів в списку для tentlength, збільшити tentlength і повторити Крок 2.
b)Видалити <P,tentlength,{Adj(P)}> з TENT.
c) Додати <P,d(P),{Adj(P)}> в PATHS.
d) Якщо система тільки що додана в PATHS – кінцева система, то перейти в Крок 2. Інакше : перейти в Крок 1.
Позначення:
PATHS – представляє ациклічний граф найкоротших шляхів від системи S. Він представляється як набір триплетів <N,d(N),{Adj(N)}>, де N ідентифікатор системи. d(N) загальна відстань від N до S).
{Adj(N)} –набір працюючих сусідів S, що їх можна використати N. Якщо система є в PATHS, шляхи, що відповідають цьому місцю є найкоротшими.
TENT – список триплетів у вигляді <N,d(N),{Adj(N)}>, де N, d(N) та {Adj(N)} відповідають визначеним в PATHS.
TENT може бути інтуітивно представлений як місце системи в PATHS. Іншими словами, триплет <N,x,{A}> в TENT говорить, що, якщо N є в PATHS, d(N) відповідає x, але N не може бути розміщене в PATHS поки не доведено, що не існує шляхів, коротших за x .
Так само <N,x,{A,B}> в 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) – маршрутизаційний інформаційний протокол
OSPF (Open Shortest Path First) – Маршрутизаційний протокол відкриття найкоротшого шляху
Література :
1. C.L. Hedrick. Routing Information Protocol. RFC 1058 Jun-01-1988.
2. D. Waitzman, C.Partridge, S.E. Deering. Distance Vector Multicast Routing Protocol. RFC 1075 Nov-01-1988.
3. R.W. Callon. Use of OSI IS-IS for routing in TCP/IP and dual environments.
RFC 1195 Dec-01-1990.
4. P. Almquist, F. Kastenholz. Towards Requirements for IP Routers. RFC 1716 November 1994.
5. J. Moy. , OSPF Version 2. RFC 2178 July 1997.
6. A. Ballardie. Core Based Trees (CBT) Multicast Routing Architecture. RFC 2201September 1997.
7. Bellman, R. E., "Dynamic Programming", Princeton University Press, Princeton, N.J., 1957.
8. Bertsekas, D. P., and Gallaher, R. G., "Data Networks",Prentice-Hall, Englewood Cliffs, N.J., 1987.
9. Braden, R., and Postel, J., "Requirements for Internet Gateways", USC/Information Sciences Institute, RFC-1009, June 1987.
10.Boggs, D. R., Shoch, J. F., Taft, E. A., and Metcalfe, R. M.,"Pup: An Internetwork Architecture", IEEE Transactions on Communications, April 1980.
11. Clark, D. D., "Fault Isolation and Recovery," MIT-LCS, RFC-816, July 1982.
12.Xerox Corp., "Internet Transport Protocols", Xerox System Integration Standard XSIS 028112, December 1981.
13. Ford, L.R. Jr., and Fulkerson, D.R.,"Flows in Networks", Princeton University Press, Princeton, N.J., 1962.
14. "Intermediate System to Intermediate System Intra-Domain Routeing Exchange Protocol for use in Conjunction with the Protocol for Providing the Connectionless-mode Network Service (ISO 8473)", ISO DP 10589, February 1990.
15. "Protocol for Providing the Connectionless-Mode Network Service", ISO 8473, March 1987.
16.”End System to Intermediate System Routeing Exchange Protocol for Use in Conjunction with the Protocol for Providing the Connectionless-Mode Network Service (ISO 8473)", ISO 9542, March 1988.
17.Braden,R., and Postel,J., "Requirements for Internet Gateways", RFC 1009, June 1987.
18. Moy,J., "The OSPF Specification", RFC 1131, October 1989.
19. Postel,J., "Internetwork Protocol", RFC 791, September 1981.
Postel,J., "Internet Control Message Protocol", RFC 792, September 1981.
20. GOSIP Advanced Requirements Group, "Government Open Systems
Interconnection Profile (GOSIP) Version 2.0 [Final Text]", Federal Information Processing Standard, U.S. Department of Commerce, National Institute of Standards and Technology, Gaithersburg, MD, October 1990.
21. "Standard for Local Area Networks and Metropolitan Area Networks: Overview and Architecture of Network Standards",IEEE Standard 802.1a-1990.
Додаток
#include "defs.h"
#include "pathnames.h"
#ifdef sgi
#include "math.h"
#endif
#include <signal.h>
#include <fcntl.h>
#include <sys/file.h>
pid_t mypid;
naddr myaddr; /* system address */
char myname[MAXHOSTNAMELEN+1];
int supplier; /* supply or broadcast updates */
int supplier_set;
int ipforwarding = 1; /* kernel forwarding on */
int default_gateway; /* 1=advertise default */
int background = 1;
int ridhosts; /* 1=reduce host routes */
int mhome; /* 1=want multi-homed host route */
int advertise_mhome; /* 1=must continue adverising it */
int auth_ok = 1; /* 1=ignore auth if we do not care */
struct timeval epoch; /* when started */
struct timeval clk, prev_clk;
struct timeval now; /* current idea of time */
time_t now_stale;
time_t now_expire;
time_t now_garbage;
struct timeval next_bcast; /* next general broadcast */
struct timeval no_flash = {EPOCH+SUPPLY_INTERVAL}; /* inhibit flash update */
fd_set fdbits;
int sock_max;
int rip_sock = -1; /* RIP socket */
struct interface *rip_sock_mcast; /* current multicast interface */
int rt_sock; /* routing socket */
int rt_sock_seqno;
static int get_rip_sock(naddr, int);
static void timevalsub(struct timeval *, struct timeval *, struct timeval *);
int
main(int argc,
char *argv[])
{
int n, mib[4], off;
size_t len;
char *p, *q;
struct timeval wtime, t2;
time_t dt;
fd_set ibits;
naddr p_net, p_mask;
struct interface *ifp;
struct parm parm;
char *tracename = 0;
/* Some shells are badly broken and send SIGHUP to backgrounded
* processes.
*/
signal(SIGHUP, SIG_IGN);
openlog("routed", LOG_PID | LOG_ODELAY, LOG_DAEMON);
ftrace = stdout;
gettimeofday(&clk, 0);
prev_clk = clk;
epoch = clk;
epoch.tv_sec -= EPOCH;
now.tv_sec = EPOCH;
now_stale = EPOCH - STALE_TIME;
now_expire = EPOCH - EXPIRE_TIME;
now_garbage = EPOCH - GARBAGE_TIME;
wtime.tv_sec = 0;
(void)gethostname(myname, sizeof(myname)-1);
(void)gethost(myname, &myaddr);
while ((n = getopt(argc, argv, "sqdghmAtT:F:P:")) != -1) {
switch (n) {
case 's':
supplier = 1;
supplier_set = 1;
break;
case 'q':
supplier = 0;
supplier_set = 1;
break;
case 'd':
background = 0;
break;
case 'g':
bzero(&parm, sizeof(parm));
parm.parm_d_metric = 1;
p = check_parms(&parm);
if (p != 0)
msglog("bad -g: %s", p);
else
default_gateway = 1;