Open Shortest Path First

پروتکل قدرتمند و پرطرفدار OSPF یا Open Shortest Path First، پروتکلی Link State و Open Standard

است که در RFC 2328 شرح داده شده است. این پروتکل برای پیدا کردن Neighbor (همسایه) – یا در

واقع روترهای متصل به خود – از Hello Message استفاده میکند. پیام Hello به آدرس Multicast

224.0.0.5 (AllSPFRouters) ارسال میگردد اگر در رسانه ای خاص Multicast قابل استفاده نباشد، از

Unicast استفاده میکند (در این حالت آدرس همسایه باید از قبل تنظیم شده باشد).

پس از ارتباط همسایگی، اگر در مدت زمان مشخصی پیام سلام از همسایه دریافت نشود، به قطع شدن پی میبریم. همسایه ها اطلاعات دسترسی خود به شبکه ها (لینک ها) را در اختیار هم قرار داده و Routing Database را بر اساس الگوریتم SPF یا Shortest Path First که بر اساس الگوریتم Dijkstra است ایجاد میکنند. هر روتر نسخه ای از آن Database را درون خود داشته و بر اساس آن Routing Table خود را میسازد.

مبنای الگوریتم SPF بر پایه الگوریتم ریاضی است که توسط Edsger – Wybe – Dijkstra ارائه شده که با ایجاد Topology Table به ازای یک Area کار خود را انجام می دهد. هر روتر دارای زاویه دید و Perspective خود از شبکه بوده و شبکه را بصورت درختی میبیند که خود در راس آن قرار دارد و مسیرها را بصورت گراف پردازش میکند.

به ازای هر تغییر در شبکه، LSA ارسال شده و در Area به همه ارسال میشود (LSA ،Flood میشود) و نهایتا پس از هر تغییر Topology Table دوباره از سر ساخته میشود.

مشخصات کلی OSPF :

RFC 2328
IP Protocol 89
Multicast Address
AllSPFRouters: 224.0.0.5
AllDRouters: 224.0.0.6
Classless supported – VLSM
Summarization: Auto-Summary (IANA Classful) and Manual
Administrative Distance = 110
Authentication supported
Partial updates supported

نقش Designated Router و BDR

اگر OSPF روی شبکه Multi-Access (مثل Ethernet یا FDDI) فعال شود، بخاطر تعدد در میزان ارتباطات بین همسایگان، یک روتر مامور ایجاد ارتباط با همه همسایگان خواهد شد که به آن Designated Router یا DR میگوییم (به ازای هر لینک).

DR از طریق Hello Packet شناسایی و انتخاب می شود که این انتخاب میتواند Dynamic یا بصورت Manual (از طریق تنظیمات) صورت گیرد. DR تنها در شبکه های Multi-access مورد استفاده قرار میگیرد و دلیل آن Inter-Mesh و تعدد روابط همسایگی (به میزان (n-1)n/2) است که برای جلوگیری از مشکلات حاصل از افزایش تعداد Neighbor Relationship و پیچیدگی پروتکل طرح شده است.

BDR یا Backup Designated Router، نقش Backup برای DR را ایفا میکند. هیچ عملکردی در شبکه ندارد مگر گوش دادن به ارتباط همسایگان با DR و تنها وقتی که DR در کار نباشد به DR مبدل میشود. در واقع همسایگان با DR و BDR خود را Sync کرده و Adjacency انجام میدهند و به وضعیت FULL درمیایند.

همسایگان برای ارتباط با DR و BDR از آدرس 224.0.0.6 (AllDRouters) استفاده میکنند. بعد از برقراری ارتباط بین همسایگان روترها یکی از این سه وضعیت را خواهند داشت:

· DR

· BDR

· DROTHER

انتخاب DR و BDR

بالاترین آدرس IP در هر سگمنت بعنوان DR انتخاب می شود. در صورتیکه Loopback IP روی روتر تنظیم شده باشد از آن IP بعنوان Router ID یا RID برای شرکت در انتخابات استفاده میشود و بالاترین RID (از نظر عددی) در انتخابات (Election) بعنوان BDR برگزیده می شود.

پس از انتخاب BDR در صورتیکه DR در شبکه نباشد، BDR به DR مبدل شده و روتر دیگری بعنوانBDR انتخاب میشود (همان مراحل بالا تکرار میشوند) و از آن پس، DR در Hello Packet به همسایه ها معرفی میگردد.

برای انتخاب بصورت Manual از اولویت (Priority) استفاده میکنیم. اولویت هر روتر بصورت پیش فرض "یک" است. (Default Priority=1) اولویت یک روتر از صفر تا 255 قابل تنظیم است که اگر صفر باشد هیچ وقت آن روتر نمی تواند نقش DR را بعهده گیرد. اولویت در Interface یک روتر تنظیم میشود. هر روتری که اولویت بالاتری دارد DR و اولویت بعدی BDR میشود. در صورت برابری اولویت، بالاترین RID انتخاب می گردد.

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

DR و BDR مامور ایجاد Adjacency با همسایگان هستند. هدف از وجود DR، دریافت LSA و پخش LSA بین همسایگان ها درون شبکه Multi-access است.

OSPF در چند Area

یکی از تفاوت های بارز این پروتکل با پروتکل های Distance Vector اختصاص و تفکیک ناحیه ها توسط Area است. در واقع Topology Database هر ناحیه منحصر به خود بوده و بار CPU و Memory روتر ها را کمتر میشود و هر autonomous به تعدادی ناحیه تبدیل میشود.

مشکلات OSPF در یک Area:

· الگوریتم SPF مکررا اجرا میشود از آنجا که هر تغییر موجب این امر میشود، هر چه Area بزرگتر باشد تغییرات بیشتر شده در نتیجه محاسبه مجدد الگوریتم به کررات صورت میگیرد.

· هر چه شبکه بزرگتر باشد Routing Table بزرگتر خواهد بود، حافظه بیشتری اشغال میکند و Lookup کندتر میشود.

· اندازه و سایز Topological Database بزرگتر شده و مدیریت آن سختر میشود. هر 30 دقیقه نیز باید بصورت کامل بین روتر ها ردوبدل شود.

با در نظر گرفتن مشکلات فوق CPU روتر ها بیشتر مشغول شده، حافظه کاهش میابد و نهایتا منجر به کند شدن شبکه میگردد. راه حل تفکیک شبکه به Area های مختلف است.

نقش روتر در Area

· Internal Router (روتر داخلی): تمام Interface های این روتر درون یک ناحیه است و درنتیجه از تمام Subnet های ناحیه خود مطلع است و در topology database خود تنها اطلاعات Area خود را داراست.

· Backbone Router: در طراحی OSPF تمام Area ها توسط ناحیه Backbone به هم متصل میشوند. روتری که در این ناحیه است Backbone Router بوده خود میتواند یک Internal، ABR و یا ASBR باشد.

· ABR: مسئول ارتباط دو یا چند Area است. Topology database این روتر شامل تمام نواحی است که به آن متصل است و LSA ها را بین Area ها ردوبدل میکند. (Area Border Router)

· ASBR: برای ارتباط با دنیای بیرون از OSPF (اینترنت یا یک Routing Protocol دیگر یا …) باید از OSPF خارج شویم. هر روتری که پروتکلی و یا Route خارجی را به OSPF معرفی کند (در واقع Redistribute کند)، ASBR خوانده میشود. (Autonomous Boundary Router)

انواع LSA

در OSPF از انواع مختلفی از LSA (Link State Advertisement) برخورداریم:

· Router Link (Type 1): هر روتر توسط این LSA وضعیت Link های خود را به Area خود اطلاع میدهد که شامل لینک و Cost آن میباشد.

· Network Link (Type 2): این LSA توسط DR در سطح Area پخش میشود و لیست تمام روترهایی است که برایشان DR است بعلاوه لینکهایشان.

· Network Summary Link (Type 3): توسط ABR ایجاد شده و شامل مسیر ها و آدرس هایی است که از طریق ABR در خارج از ناحیه قابل دسترس است.

· AS External ASBR Summary Link (Type 4): از ABR به ASBR ارسال میشود و حاوی Metric است. درواقع همان Network Summary است با این تفاوت که گیرنده ASBR است.

· External Link (Type 5): توسط ASBR به تمام autonomous ارسال میگردد و مسیر به شبکه خارجی را عنوان میکند. از این طریق Default Route ها نیز برای AS اعلام میگردند.

· NSSA External (Type 7): یک ASBR در ناحیه NSSA این LSA را منتشر میکند از آنجا که تنها در داخل ناحیه خود این LSA اعلام میشود، توسط ABR بعنوان Type 5 به بقیه اعلام میگردد.

Type Code	Description
1	Router LSA
2	Network LSA
3	Network Summary LSA
4	ASBR Summary LSA
5	AS External LSA
6	Group Membership LSA
7	NSSA External LSA
8	External Attributes LSA
9	Opaque LSA (link-local scope)
10	Opaque LSA (area-local scope)
11	Opaque LSA (AS scope)

 

انواع Area

1. Stub Area: این ناحیه به اطلاعات External LSA (type 5) نیازی ندارد زیرا به هر حال برای خروج از ناحیه دست به دامان ABR خود میشود. پس مسیر همیشه بدین گونه است و از طریق یک روتر خارج میشود. نکته و هدف از استفاده از این Area، Performance است. از آنجا که LSA 5 را قبول نمیکند پس LSA 4 نیز در این ناحیه بی معنی است و توسط ABR، Filter می شود. هدف صرفه جوئی در Resource ها و Memory است. که البته Stub area محدودیت های خود را نیز دارد:

· هیچ ASBR ی در ناحیه نمی توان داشت. (و مسلما هیچ Redistribution و External Route)

· Virtual Link در این Area مجاز نیست (نه در ناحیه و نه بصورت Transit)

· می توان چند ABR در این ناحیه داشت اما از آنجا که بهترین مسیر به ASBR را نمیتوان در این ناحیه فهمید، تفاوتی در انتخاب ABR برای رسیدن به ASBR وجود ندارد.

· تمام روتر ها (در Hello Message) بیت E خود را صفر ست میکنند (علامت Stub) و با روتری با E Flag برابر با یک، ارتباطی برقرار نمی کنند.

2. Totally Stubby Area: اگر فیلتر کردن LSA 5 موجب بهبود کارایی روتر میشود، در این نوع از ناحیه حتی LSA 3 نیز Block میشود. این نوع Area توسط Cisco ارائه شده تا تنها با تزریق یک Default Route توسط ABR روتر ها تمام بسته هایی که مقصدشان داخل ناحیه نیست را به ABR بفرستند.

3. Not So Stubby Area: یک ناحیه Stub است که بنا به دلایلی اقدام به Redistribution میکند. (مثلا ارتباط با ISP) LSA 7 در داخل ناحیه منتشر میکند. برای اعلام به نواحی دیگر به ABR میرسد. توسط ABR، اگر P bit آن LSA صفر باشد، Block میشود و اگر P Bit آن یک باشد به صورت مبدل شده به LSA 5 به بیرون از ناحیه اعلام میگردد.

4. Backbone Area: این ناحیه بنام Area 0 مطرح میگردد و تمام نواحی از طریق این ناحیه به هم متصل میگردند. تمام LSA ها در این ناحیه مجازند غیر از نوع 7.

5. Standard Ordinary Area: این Area به Backbone وصل است و Stub نیست.

نواحی و LSA مجاز

Area Type	1&2	3&4	5	7
Backbone (area 0)	Yes	Yes	Yes	No
Non-backbone, non-stub	Yes	Yes	Yes	No
Stub	Yes	Yes	No	No
Totally stubby	Yes	No*	No	No
Not-so-stubby	Yes	Yes	No	Yes
*به جز یک Route که در واقع همان Default Route شبکه است.