شبکه‌های کامپیوتری/مسیریابی

مقدمه

مسیریابی روند دریافت بسته های اطلاعاتی از مکانی که بسته ها باید به آن ارسال شود تعریف میشود. در واقع مسیریابی اجرا الگوریتم های مختلفی است که وظیفه آنها پیدا کردن کوتاه ترین مسیر بین دو نقطه می باشد.

آدرس دهی IP برپایه مفهوم شبکه و هاست است. در واقع هاست به هر عضوی در شبکه گفته میشود که توانایی ارسال و دریافت بسته های IP را داشته باشد که شامل دستگاه هایی از قبیل ایستگاه کاری و یا روتر می باشد. مسیریابی عملیات انتقال داده از یک هاست به یک هاست دیگر میباشد. تفاوت مهم مسیریابی با برقراری پل (bridging) این است که پل در لایه 2 "لایه لینک" از مدل OSI است اما مسیریابی در لایه 3 "لایه شبکه" میباشد. مسیریابی بهینه ترین مسیر را در شبکه تشخیص میدهد.

الگوریتم های مسیریابی

الگوریتم مسیریابی در حافظه روتر ذخیره میشود . این الگوریتم فاکتور مهمی برای عملکرد مناسب عملیات مسیریابی است. هدف این الگوریتم مسیریابی انتخاب مسیر انتقال داده است. روتر از الگوریتم مسیریابی برای انتخاب مسیری که بهترین شرایط انتقال داده از مبدا به مقصد را دارد، استفاده میکند. الگوریتم مسیریابی مورد استفاده روتر را نمی توان به صورت مستقیم تغییر دارد اما به طور غیر مستقیم میتوان با انتخاب پروتکل مسیریابی، الگوریتم مورد استفاده روتر را تغییر دهیم. به عنوان مثال پروتکل اطلاعات مسیریابی ((Routing Information Protocol (RIP) ممکن است از یک نوع الگوریتم برای انتقال داده و در مقابل پروتکل ابتدا کوتاه‌ترین مسیر را انتخاب کردن ((Open Shortest Path First (OSPF) از الگوریتم دیگری استفاده کند. در نتیجه الگوریتم مسیریابی مستقیما نمی تواند تغییر کند و تنها راه تغییر آن تغییر پروتکل مسیریابی است. در مجموع دو نوع اصلی از پروتکل های مسیریابی وجود دارد که عبارت اند از :

• فاصله راس ها (Distance Vector)
• وضعیت اتصال (link-state)
  

الگوریتم های مسیریابی و پروتکل های مسیریابی

یکی از وظایف پروتکل مسیریابی ارائه اطلاعات موردنیاز الگوریتم مسیریابی برای محاسبه تصمیماتش است. نحوه فراهم کردن و نوع اطلاعاتی که پروتکل مسیریابی به الگوریتم مسیریابی میدهد باعث ایجاد تفاوت بین پروتکل های مسیریابی می شود. اطلاعات فراهم شده برای الگوریتم می تواند در هر پروتکلی متفاوت باشد. پروتکل مسیریابی اطلاعاتی درمورد شبکه و روتر های متصل در شبکه جمع آوری میکند و سپس در نقشه مسیر (Routing Table) ، که در حافظه روتر وجود دارد، این اطلاعات را ذخیره میکند. الگوریتم مسیریابی درحال اجرا از اطلاعات این جدول برای محاسبه بهترین مسیر از یک روتر به روتر دیگر استفاده می کند. الگوریتم ها با استفاده از ازفرمول خود مسیرها را محاسبه می کنند. نتیجه این محاسبه برای تخمین مکانی که اطلاعات ارسال خواهد شد، استفاده می شود. برای مثال، جدول زیر یک جدول مسیریابی برای یک شبکه را نشان می دهد. به وسیله مجموعه ای از بروزرسانی ها هر روتر به روترهای دیگر خواهد گفت که چه اطلاعاتی را ذخیره دارد. نهایتا یک جدول مسیریابی داخلی مانند شکل زیر ساخته خواهد شد.

مسیر روتر	متریک
روتر A به B	٢
روتر B به C	٣
روتر C به A	٦
روتر C به D	٥

به عنوان نمونه بهترین مسیر به هر مقصدی در این الگوریتم مسیریابی مسیری است که کمترین مقدار متریک را داشته باشد. متریک یک عدد است که به عنوان یک استاندار اندازه گیری برای لینک های یک شبکه استفاده میشود. در واقع هر متریک به یک لینک اختصاص دارد که به معنی هزینه استفاده از پهنای باند (Bandwidth) آن مسیر است.

##وقتی که روتر A نماینده یک packet bound از روتر C است،

جدول مسیریابی دو مسیر ممکن به مقصد انتخابی را نشان میدهد. انتخاب اول فرستادن بسته از روتر A به روتر C به طور مستقیم است و گزینه دوم ارسال بسته از روتر A به روتر B و سپس از آن به روتر C است. الگوریتم مسیریابی برای تشخیص بهترین مسیر و انتخاب آن استفاده میشود. بعضی از پروتکل های مسیریابی ممکن است یک متریک را برای الگوریتم مسیریابی فراهم کنند، درحالی که پروتکل های دیگر ممکن است بیشتر از 10 متریک فراهم کنند. از طرف دیگر ممکن است دو پروتکل متفاوت یک متریک مشابه را برای یک الگوریتم همسان ارسال کنند، اما ممکن است منبع یک متریک در پروتکل های مختلف تفاوت داشته باشد. همچنین یک پروتکل مسیریابی ممکن است برای الگوریتم مسیریابی تنها یک معیار اراده دهد، اما این معیار میتواند معنی متفاوتی در الگوریتم دیگر داشته باشد. در الگوریتم مثال زده شده بهترین مسیر، مسیری است که کمترین هزینه متریک را دارد، بنابراین توسط اضافه کردن عدد متریک مرتبط با هر پیوند، میبینیم که مسیری از A به B و سپس به C که مقدار مجموع معیار آن عدد 5 است انتخاب میشود در حالی که مقدار متریک لینک مستقیم به روتر C عدد 6 است. بنابراین الگوریتم مسیر A-B-C را انتخاب و اطلاعات را توسط آن ارسال میکند.

الگوریتم فاصله راس ها (Distance Vector Algorithms)

الگوریتم فاصله راس ها از متریک به عنوان هزینه مسیر برای مشخص کردن بهترین مسیر (مسیری با کمترین هزینه) به مقصد استفاده می کند. زمانی که روتر از الگوریتم فاصله راس ها استفاده میکند ، هزینه ها توسط هر روتر جمع آوری می شود. این هزینه ها میتواند به صورت واحدهای قرار دادی باشند و یا به صورت پویا و در حال تغییر جمع آوری شود مانند مقدار تاخیر در ارسال اطلاعات از طریق یک مسیر به یک روتر دیگر. تمام هزینه ها در جدول مسیریابی روتر قرار می گیرند و سپس توسط الگوریتم مسیریابی جستجو شده تا بهترین مسیر برای هر نوع استفاده از شبکه را محاسبه کنند.

اگر چه منابع زیادی وجود دارد که فرمول های ریاضی پیچیده ای از الگوریتم های بردار فاصله و نحوه تصمیم گیری آنها نمایش میدهند، اما مفهوم اساسی آن که با اضافه کردن متریک هر مسیر اختیاری در یک شبکه، شما حداقل یک بهترین مسیر را خواهید یافت، در تمامی فرکول ها یکسان است. نمایه آن به شکل زیر است:

$M(i,k)=min[M(i,t)+M(t,k)]$

این فرمول بیان می دارد که بهترین مسیر بین دو شبکه (M (i، k را می توان با پیدا کردن کمترین (min) مقدار مسیرها  بین تمام نقاط شبکه پیدا کرد. توجه داشته باشید که i به معنای مبدا و k به معنای مقصد است. بیایید دوباره در اطلاعات مسیریابی در جدول بالا نگاه کنیم. این اطلاعات را به فرمول اضافه می کنیم. می بینیم که مسیر A از B به C هنوز بهترین مسیر است:

$5(A,C)=min[2(A,B)+3(B,C)]$

در حالی که فرمول مسیر مستقیم A به C به این شکل است:

$6(A,C)=min[6(A,C)]$

این مثال نشان می دهد که چگونه الگوریتم های بردار فاصله از اطلاعات منتقل شده به آنها برای مسیریابی استفاده می کنند. از تفاوت های عمده بین الگوریتم های بردار فاصله و پروتکل های حالت پیوند این است که وقتی پروتکل های مسیریابی بردار فاصله که داده های یکدیگر را به روز می کنند، این داده ها ممکن است تمام و یا بخشی از جدول مسیریابی (بسته به نوع بروز رسانی) از یک روتر به دیگری فرستاده می شود. با استفاده از این فرآیند، هر روتر اطلاعات موجود در جدول خود را به  روترهای دیگر نمایش می دهد، به این ترتیب هر روتر یک نمای  کامل تر از محیط شبکه را بدست می آورد و آنها را قادر می سازد تا تصمیمات مسیریابی بهتر را اتخاذ کنند. نمونه هایی ازپروتکل هایی که ازالگوریتم های بردار فاصله استفاده میکنند RIP و BGP است. دیگر پروتکل های محبوب مانند OSPF نمونه هایی از پروتکل هایی هستند که از الگوریتم مسیریابی حالت پیوند استفاده می کنند. الگوریتم های Bellman-Ford و Ford-Fulkerson جزو الگوریتم های بردار فاصله  شناخته می شوند. در این الگوریتم ها، هر روتر یک جدول مسیریابی دارد که بهترین مسیر را برای هر مقصد نشان می دهد. یک جدول گراف و جدول مسیریابی برای روتر J در زیر نشان داده شده است.

Destination	Weight	Line
A	8	A
B	20	A
C	20	I
D	20	H
E	17	I
F	30	I
G	18	H
H	12	H
I	10	I
J	0	N/A
K	6	K
L	15	K

جدول نشان می دهد که اگر روتر J  بخواهد بسته ها را به روتر D بفرستد، ابتدا باید آن را به روتر H ارسال کند. هنگامی که بسته ها به روتر H می رسند، روتر کنونی جدول خود را بررسی می کند و تصمیم می گیرد که بسته ها را به D ارسال کند. در الگوریتم های بردار فاصله، هر روتر باید مراحل زیر را دنبال کند:

1. وزن لینک هایی که به طور مستقیم به آن متصل شده است را شمارش می کند و اطلاعات را در جدول خود ذخیره می کند.

2. در یک دوره زمانی خاص، روتر جدول خود را به روترهای همسایه خود (نه همه روترها) ارسال می کند و جدول مسیریابی هر یک از همسایگانش را دریافت می کند.

3. براساس اطلاعاتی که روتر از جداول مسیریابی همسایگان خود دریافت می کند، خود را به روز می کند.

بیایید یک نمونه دیگر (شکل زیر را نشان بدهیم) را در نظر بگیریم.

هزینه هر پیوند 1 تنظیم شده است. بنابراین، مسیری با کمترین هزینه، تنها مسیری است که هزینه آن کمترین باشد . جدول زیر نشان دهنده دانش هر گره از فاصله به تمام گره های دیگر است:

Information stored at node	Distance to reach node
	A	B	C	D	E	F	G
A	0	1	1	$\infty$	1	1	$\infty$
B	1	0	1	$\infty$	$\infty$	$\infty$	$\infty$
C	1	1	0	1	$\infty$	$\infty$	$\infty$
D	$\infty$	$\infty$	1	0	$\infty$	$\infty$	1
E	1	$\infty$	$\infty$	$\infty$	0	$\infty$	$\infty$
F	1	$\infty$	$\infty$	$\infty$	$\infty$	0	1
G	$\infty$	$\infty$	$\infty$	1	$\infty$	1	0

در ابتدا، هر گره هزینه 1 را به گره هایی که مستقیما به آن متصل هستند و مقدار بی نهایت به تمامی گره های دیگر می دهد. در زیر جدول مسیریابی اولیه در گره A نشان داده شده است:

Destination	Cost	Next Hop
B	1	B
C	1	C
D	$\infty$	-
E	1	E
F	1	F
G	$\infty$	-

در مرحله بعد، هر گره یک پیام را به گره های متصل  ارسال می کند. این پیام حاوی لیستی از فاصله هر گره تا  گره های دیگر است. به عنوان مثال، گره F به گره A می گوید که می تواند با هزینه 1 به  گره G برسد. گره A همچنین می داند که با هزینه ی 1  می تواند به F  برسد، بنابراین این هزینه را به هزینۀ رسیدن به G با استفاده از F می افزاید. از آنجائیکه 2  کمتر از هزینه فعلی (بی نهایت ) است، بنابراین گره A می گوید که می تواند از طریق F به G با هزینه 2 برسد. گره A از گره C می آموزد که گره B را می توان از گره C با هزینه ی 1 رد کرد، بنابراین نتیجه می شود که هزینه رسیدن به B از طریق گره C هزینه 2 در بردارد. از آنجا که این هزینه ، بهینه تر ازهزینه فعلی رسیدن به B  که در حال حاضر 1 است نمی باشد، اطلاعات جدید نادیده گرفته می شود. جدول نهایی در گره A ، در زیر نشان داده شده است:

Destination	Cost	Next Hop
B	1	B
C	1	C
D	2	C
E	1	E
F	1	F
G	2	F

فرایند دریافت اطلاعات مسیر یابی سازگار به تمام گره ها همگام سازی نامیده می شود. مجموعه نهایی هزینه ها از هر گره به تمام گره های دیگر در جدول زیر نشان داده شده است:

Information stored at node	Distance to reach node
	A	B	C	D	E	F	G
A	0	1	1	2	1	1	2
B	1	0	1	2	2	2	3
C	1	1	0	1	2	2	2
D	2	2	1	0	3	2	1
E	1	2	2	3	0	2	3
F	1	2	2	2	2	0	1
G	2	3	2	1	3	1	0

یکی از مشکلات الگوریتم های بردار فاصله، "شمارش تا بی نهایت" (count to infinity) نامیده می شود. بگذارید این مشکل را با یک مثال بررسی کنیم:

یک شبکه را با یک گراف در زیر نشان دهید. تنها یک اتصال بین D و سایر قسمت های شبکه وجود دارد.

	A	B	C	D
A	0	1	2	3
B	1	0	1	2
C	2	1	0	1
D	3	2	1	0

در حال حاضر لینک C به D  دچار تصادم است زیرا برای ارسال  بسته با آدرس D باید از لینک  CD استفاده شود ، اما اگر گره D در حال ارسال اطلاعات باشد، هزینه ∞ = [C] [D]  میشود،بنابراین گره C باید بردار فاصله خود را مجددا محاسبه و مسیری را انتخاب کند . به همین ترتیب گره D باید بردارهای خود را بروزرسانی کند. پس از به روزرسانی بردارهای خود در C و D، ما داریم :

	A	B	C	D
A	0	1	2	3
B	1	0	1	2
C	2	1	0	3
D	$\infty$	$\infty$	$\infty$	0

گره C گره B را به عنوان بهترین مسیر به گره D با هزینه 3 میشناسد، زمانی که گره C بردارهای خود را به گره B ارسال میکند، گره B می فهمد که انتخاب قبلی خود برای ارسال اطلاعات به گره D از طریق گره C هزینه بیشتری دربر دارد بنابراین گره B باید بردارهای خود را دوباره محاسبه کند.

	A	B	C	D
A	0	1	2	3
B	1	0	1	4
C	2	1	0	3
D	$\infty$	$\infty$	$\infty$	0

با توجه به سطر گره B می توان نتیجه گرفت که مسیریابی به گره D می تواند از طریق گره A یاگره  C با هزینه مساوی انجام شود بنابراین گره B بردار خودرا به روزرسانی و ارسال می کند. هر دو گره A وC بردار به روز شده گره B  را دریافت می کنند و متوجه میشوند که مسیرترجیحی خود به گره D در حال حاضر دارای هزینه بالایی است، بنابراین بردارهای  خود را مجددا محاسبه میکنند.

	A	B	C	D
A	0	1	2	5
B	1	0	1	4
C	2	1	0	5
D	$\infty$	$\infty$	$\infty$	0

سپس گره A و C بردارهای خود را ارسال می کنند وگره B باید بردار خود را با توجه به بردارهای دریافتی دوباره به روزرسانی کند، و سپس اطلاعات خودرا برای آنها می فرستند که در اینجا با یک حلقه مواجح میشویم.

	A	B	C	D
A	0	1	2	7
B	1	0	1	6
C	2	1	0	7
D	$\infty$	$\infty$	$\infty$	0

توجه داشته باشید که همچین برداری در واقعیت به ندرت پیش می آید:

$d[x][D]=\infty \quad for\quad x=A\quad or\quad x=B\quad or\quad x=C$

این حلقه تا زمانی که تمام گره ها متوجه شوند وزن لینک به گره D بی نهایت است ادامه پیدا میکند. به این ترتیب، کارشناسان می گویند که الگوریتم های بردار فاصله یک نرخ همگرایی آهسته دارند. در نتیجه، الگوریتم بردار فاصله الگوریتم کاملی (در حلقه گیر میکند و جواب درستی  نمی دهد) نیست. یکی از راه حل های این مشکل این است که روترها اطلاعات را فقط برای همسایگان ارسال کنند که لینک منحصر به فردی به مقصد نداشته باشند. به عنوان مثال، در این مورد، گره B نباید به گره C اطلاعات مربوط به گره D را ارسال کند، زیرا گره C تنها راه برای رسیدن به گره D است.

الگوریتم های حالت لینک (Link-State Algorithms)

الگوریتم های بردار فاصله و الگوریتم های حالت لینک هر دو مسیری را با کمترین هزینه انتخاب  می کنند. با این حال، پروتکل های حالت لینک به صورت محلی تر کارها را انجام می دهند. اگرچه روتری که یک الگوریتم بردار فاصله را برای مسیریابی استفاده می کند،برای هر بسته داده شده هزینه مسیر را از مبدا تا مقصد محاسبه می کند. اما پروتکل حالت اتصال ، هزینه لینک های متصل و ضروری را محاسبه میکند. بدین معنی که در آن الگوریتم بردار فاصله، کمترین متریک بین گره A و گره C را محاسبه می کند، اما یک پروتکل حالت اتصال، آن را به عنوان دو مسیر متمایز از A به B و B به C محاسبه می کند. این فرآیند برای محیط های بزرگ بسیار کارآمد است. الگوریتم های حالت لینک روتر ها را قادر می سازد که روی لینک ها و اینترفیس های خود تمرکز کنند. هر روتر در یک شبکه  اطلاعات خود را فقط از روترها و شبکه هایی که به طور مستقیم به آن متصل است بدست می آورد. درواقع درمحیط های بزرگتر، روتر از قدرت پردازشی کمتری برای محاسبه مسیرهای پیچیده استفاده خواهد کرد. روتر نیاز دارد به شناختن واسطی مستقیم که می خواهد اطلاعات را به سرعت از طریق آن ارسال کند(واسط در اینجا به معنی مسیری است که شرایط ارسال اطلاعات به مقصد را مهیا میکند به طور مثال یک واسط می تواند شامل مسیری از یک یا روتر ها باشد). روتر بعدی در خط روند را تکرار می کند تا اطلاعات به مقصد خود برسد. مزیت دیگری برای چنین فرآیندهای مسیریابی محلی این است که پروتکل ها می توانند جداول مسیریابی کوچکتری را حفظ کنند. از آنجا که یک پروتکل حالت پیوند تنها اطلاعات مسیریابی را برای واسط های مستقیم آن حفظ می کند، جدول مسیریابی حاوی اطلاعات بسیار کمتری نسبت به پروتکل بردار فاصله است که ممکن است اطلاعات روی چند روتر وجود داشته باشد. پروتکل های حالت لینک مانند پروتکل های بردار فاصله، برای به اشتراک گذاشتن اطلاعات با یکدیگر نیاز به بروزرسانی دارند. این به روز رسانی  به نام (Link State Advertisements)  و به صورت خلاصه  (LSAs) شناخته می شود و هنگامی که وضعیت لینک های روتر تغییر می کند، این فرآیند اجرا می شود. هنگامی که یک لینک خاص در دسترس نیست (وضعیت تغییر می کند)، روتر از طریق شبکه به تمام روتر هایی که با آنها ارتباط مستقیم دارد اعلام می دارد و این روتر ها اطلاعات خود را بروز رسانی می کند.

در الگوریتم های حالت لینک ها، هر روتر باید این مراحل را دنبال کند:

1. شناسایی روترهایی که از لحاظ فیزیکی به آنها متصل شده اند و آدرس های IP خود را دریافت می کنند؛ هنگامی که یک روتر شروع به کار می کند، ابتدا یک بسته راه انداز (به طور مثال "Hello") را از طریق شبکه ارسال می کند. هر روتر که این بسته را دریافت می کند با یک پیام که حاوی آدرس IP خود است پیام را پاسخ میدهد.
2. روترها زمان تأخیر (یا هر پارامتر مهم دیگر شبکه، مانند ترافیک متوسط) را برای روترهای همسایه اندازه گیری می کنند. برای انجام این کار، روترها بسته های اکو را بر روی شبکه ارسال می کنند. هر روتر که این بسته ها را دریافت میکند با یک بسته اکو پاسخ می دهد. با نصف کردن زمان ارسال و دریافت، روترها می توانند زمان تأخیر را محاسبه کنند. زمان تاخیر شامل زمان انتقال و پردازش( زمانی که بسته ها برای رسیدن به مقصد و زمان گیرنده برای پردازش و پاسخ نیاز دارد) می باشد.
3. اطلاعات مربوط به یک روتر برای روترهای دیگر شبکه ارسال میشود واطلاعات  سایرروترها نیزدریافت میشود. در این مرحله همه روترها دانش خود را به اشتراک می گذارند و اطلاعات خود را به یکدیگر می فرستند. به این ترتیب، هر روتر می تواند ساختار و وضعیت شبکه را بداند.
4. روترها از یک الگوریتم مناسب برای شناسایی بهترین مسیر بین دو گره شبکه استفاده می کنند. در این مرحله، روترها بهترین مسیر را به هر گره انتخاب می کنند. آنها این کار را با استفاده از یک الگوریتم انجام می دهند، مانند الگوریتم کوتاه ترین مسیر دایجسترا. در این الگوریتم، یک روتر، بر اساس اطلاعاتی که از دیگر روترها جمع آوری شده، یک نمودار از شبکه را ایجاد می کند. این نمودار محل روترها و لینک های متصل به روتر های دیگر در شبکه را  نشان می دهد. هر لینک با یک عدد برچسب گذاری شده واین عدد به عنوان وزن و یا هزینه مسیر شناخته میشود. این شماره  تابعی از زمان تاخیر، متوسط ترافیک و گاهی اوقات به سادگی تعداد ایستگاه های بین گره ها است. به عنوان مثال، اگر دو لینک بین یک گره و یک مقصد وجود دارد، مسیریاب مسیری  با کمترین وزن انتخاب می کند.

الگوریتم دایجسترا

الگوریتم Dijkstra از طریق مراحل زیر انجام می شود:

1. روتر گراف یک شبکه را ایجاد و سپس گره های منبع و مقصد را مشخص می کند. روتر طبق گراف ذکر شده را به صورت ماتریسی (ماتریس مجاورت) تبدیل می کند. در ماتریس مجاورت، مختصات، نشان دهنده وزن است. برای مثال مختصات درایه [i، j] نشان دهنده وزن پیوند (هزینه پیوند) بین گره های Ri و Rj است. اگر ارتباط مستقیم بین Ri و Rj وجود نداشته باشد، این وزن به عنوان "بی نهایت" شناخته می شود.
2. روتر پس از آن یک رکورد وضعیت برای هر گره در شبکه ایجاد می کند. رکورد شامل زمینه های زیر است:
   • فیلد گره قبلی (گره جد) را نشان می دهد.
   • فیلد مجموع وزنها (هزینه) را از مبدا تا آن گره نشان می دهد.
   • فیلد حالت که وضعیت گره را نشان می دهد هر گره یک حالت وضعیت دارد: "دائمی" یا "پیش فرض".
3. در مرحله بعد، روتر پارامترهای وضعیت (برای تمام گره ها) را اولویت می دهد و فیلد حالت و وزن آنها را به ترتیب "پیش فرض" و"بی نهایت" تنظیم می کند.
4. در طی این مرحله، روتر یک T-node را تنظیم می کند. برای مثال، اگر R1 جد t-node باشد، روتر فیلد حالت این گره را به "دائمی" تغییر می دهد. هنگامی که فیلد حالت یک گره به "دائمی" دیگر تغییر نمی کند.
5. روتر رکورد وضعیت را برای تمام گره های پیشنهادی که به طور مستقیم به گره منبع متصل هستند، به روز می کند.
6. روتر تمام گره های متصل را جستجو میکند و گره ای را انتخاب می کند که وزن آن تا گره R1 کمتر است. این گره سپس مقصد T-node است.
7. اگر T-node جدید R2 نبود (مقصد مورد نظر)، روتر به مرحله 5 باز می گردد.
8. اگر این گره R2 باشد، روتر گره قبلی خود را از رکوردهای وضعیت استخراج می کند و این کار را تا زمانی که به R1 برسدادامه میدهد. این لیست بهترین مسیر را از R1 تا R2 نشان می دهد.

مثالی از الگوریتم دایجسترا:

بیایید بهترین مسیر را بین روترهای A و E پیدا کنیم. شش مسیر ممکن بین آنها وجود دارد (ABE، ACE، ABDE، ACDE، ABDCE، ACDBE)، و واضح است که ABDE بهترین مسیر است زیرا وزن آن کمترین است. اما همیشه به این آسانی نیست، و برخی از موارد پیچیده وجود دارد که در آن ما باید از الگوریتم ها برای یافتن بهترین مسیر استفاده کنیم.

1. گره A  به عنوان گره ریشه انتخاب شده است بنابراین فیلد حالت آن دائمی است.

2. در این مرحله، وضعیت گره هایی که به طور مستقیم به گره A متصل هستند(گره B و C) بررسی می شود. بنابراین گره B که هزینه مسیر آن از گره A کمتر از گره C است انتخاب میشود و فیلد حالت آن به دایمی تغییر میکند.

3. در این مرحله مانند مرحله قبل گره های متصل به گره B بررسی میشوند که در نتیجه گره D که هزینه کمتری دارد انتخاب میشود.

4. از آنجا که گره D به طور مستقیم به گره E متصل و هزینه این مسیر از مسیر DC کمتر است بنابراین گره E انتخاب میشود.

حالا ما باید مسیر را بررسی و صحت آن را تعیین کنیم. مجموع هزینه های مسیر ABDE $1+2+1=4$ است، بنابراین میتوان فهمید که این مسیر بهترین است زیرا هیچ مسیر دیگری با هزینه کمتر نمی توان یافت. این الگوریتم به خوبی کار می کند، اما این عملیات در مقیاس بزرگ بسیار پیچیده است و زمان زیادی را برای پردازش مصرف می کند. این مسئله باعث کاهش بهره وری سیستم میشود. مورد مهم دیگر این است که اگر یک روتر به روترهای دیگر اطلاعات اشتباه داده ارسال کند، همه تصمیمات مسیریابی اشتباه شده که باعث کاهش بهره وری شبکه میشود.

مثال بعدی نشان می دهد که چگونه بهترین مسیرها را در میان تمام گره ها در یک شبکه پیدا کنید. مثال از الگوریتم Dijkstra Shortest Path استفاده می کند. شبکه زیر را در نظر بگیرید:

در این مثال از الگوریتم دایجسترا  استفاده می کنیم تا مسیرهایی که گره A میتواند برای انتقال اطلاعات به هر یک از گره های دیگر استفاده کند را  پیدا می کنیم.  نحوه اجرا این فرآیند در جدول زیر نشان داده شده است:

		B	C	D	E	F	G	H	I
Step 1	A	2-A	3-A	5-A	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
Step 2	AB		3-A	5-A	7-B	9-B	$\infty$	$\infty$	$\infty$
Step 3	ABC			4-C	4-C	9-B	$\infty$	$\infty$	$\infty$
Step 4	ABCD				4-C	9-B	$\infty$	11-D	$\infty$
Step 5	ABCDE					8-E	12-E	7-E	$\infty$
Step 6	ABCDEH					8-E	12-E		11-H
Step 7	ABCDEHF						10-F		11-H
Step 8	ABCDEHFG								11-H
Step 9	ABCDEHFGI

با توجه به جدول و بروزرسانی های انجام شده ، شبکه ایجاد شده از کوتاه ترین مسیر بین گره های ما به شکل زیر است :