پروتکل مسیریابی حالت پیوند
پروتکل های مسیریابی حالت پیوند یکی از دو کلاس اصلی پروتکل های مسیریابی است که در بسته سوئیچینگ شبکه برای ارتباطات رایانه ای مورد استفاده قرار می گیرد ، دسته دیگر پروتکل های مسیریابی بردار-فاصله هستند . نمونه هایی از پروتکل های مسیریابی حالت پیوند شامل OSPF یا ابتدا انتخاب کردن کوتاهترین مسیر (به انگلیسی: Open Shortest Path First) و سامانه حدواسط به سامانه حدواسط یا IS-IS (به انگلیسی: Intermediate Sysytem to Intermediate System) است.
پروتکل حالت پیوند توسط هر گره سوئیچینگ در شبکه انجام می شود (یعنی گره هایی که برای ارسال بسته ها آماده شده‌اند ؛ در اینترنت به اینها روتر گفته می شود). مفهوم اساسی مسیریابی حالت پیوند این است که هر گره نقشه ای از اتصال به شبکه را به صورت گراف ایجاد می کند و نشان می دهد کدام گره ها به گره های دیگر متصل است. سپس هر گره به طور مستقل بهترین مسیر منطقی بعدی را از آن به هر مقصد احتمالی در شبکه محاسبه می کند. سپس هر مجموعه از بهترین مسیرها جدول مسیریابی هر گره را تشکیل می دهند.
این در تضاد با پروتکل های مسیریابی بردار-فاصله است ، که با به اشتراک گذاشتن هر گره در جدول مسیریابی خود با همسایگان خود کار می کنند ، در یک پروتکل حالت پیوند ، تنها اطلاعاتی که بین گره ها منتقل می شود مربوط به اتصال است . الگوریتم های حالت پیوند گاهی اوقات به صورت غیررسمی به عنوان هر روتر توصیف می شوند ، "در مورد همسایگان خود به جهان می گویند."
تاریخچه[ویرایش]
اعتقاد بر این است که اولین شبکه مسیریابی انطباقی رایانه است که از مسیریابی حالت پیوندی به عنوان قلب خود استفاده می کند ، در طی سالهای 77-1976 توسط تیمی از رادار Plessey به رهبری Bernard J Harris طراحی و اجرا شد. این پروژه برای "Wavell" - یک سیستم کنترل و کنترل رایانه ای برای ارتش انگلیس- بود.[نیازمند منبع]
اولین مفهوم مسیریابی حالت پیوند در سال 1979 توسط جان م. مک کوئیلان (به انگلیسی: John M. McQuillan ) (سپس در بولت ، برانک و نیومن ) به عنوان مکانیزمی منتشر شد که با تغییر شرایط شبکه مسیرها را سریعتر محاسبه می کند و بنابراین منجر به پایداری مسیریابی می شود. [۱] [۲]
کارهای بعدی در بی‌بی‌ان تکنالوجیز (BBN Technologies) نشان داد که چگونه می توان از تکنیک حالت پیوند در یک سیستم سلسله مراتبی استفاده کرد (به عنوان مثال ، یکی از شبکه ها به مناطقی تقسیم شده است) به طوری که هر گره سوئیچینگ نیازی به نقشه کل شبکه ندارد ، فقط به منطقه (s) که در آن گنجانده شده است.[نیازمند منبع]
این تکنیک بعداً برای استفاده در پروتکل های مسیریابی معاصر حالت پیوند IS-IS و OSPF سازگار شد. ادبیات سیسکو به پروتکل مسیریابی دروازه داخلی (EIGRP) به عنوان یک پروتکل "ترکیبی" اشاره دارد ،[نیازمند منبع] علی‌رغم این واقعیت که جداول مسیریابی را به جای نقشه های توپولوژی توزیع می کند. با این حال ، این جداول مسیریابی را با OSPF همزمان می کند و فقط در صورت بروز تغییرات توپولوژی ، به روزرسانی های خاص را ارسال می کند.
در سال 2004 ، رادیا پرلمن (به انگلیسی:Radia Perlman) پیشنهاد کرد که از مسیریابی حالت پیوند برای انتقال قاب لایه 2 با دستگاههایی به نام پل های مسیریاب (به انگلیسی:routing bridges) یا Rbridges استفاده شود. گروه ویژه مهندسی اینترنت اتصال شفاف پروتکل پیوندهای زیادی (TRILL) را برای تحقق این امر استاندارد کرده است. [۳]
اخیراً ، این روش سلسله مراتبی با استفاده از پروتکل مسیریابی بهینه سازی پیوند (OLSR) در شبکه های بی سیم مش استفاده شد. در مواردی که اتصال می تواند کیفیت متفاوتی داشته باشد ، می توان از کیفیت اتصال برای انتخاب اتصالات بهتر استفاده کرد. این مورد در برخی از پروتکل های مسیریابی که از انتقال فرکانس رادیویی استفاده می کنند ، استفاده می شود.
در سال 2012 ، IEEE استاندارد سازی استفاده از IS-IS را برای کنترل انتقال اترنت با IEEE 802.1aq کوتاهترین مسیر پل زدن (SPB) را به پایان رساند و تصویب کرد.
توزیع نقشه ها[ویرایش]
این توصیف فقط ساده ترین تنظیمات را در بر می گیرد. به عنوان مثال ، یکی بدون منطقه ، به طوری که همه گره ها نقشه ای از کل شبکه داشته باشند. مورد سلسله مراتبی تا حدودی پیچیده تر است; مشخصات مختلف پروتکل را مشاهده کنید.
همانطور که قبلاً ذکر شد ، اولین مرحله اصلی در الگوریتم حالت پیوند دادن نقشه ای از شبکه به هر گره است. این کار با چندین مرحله فرعی انجام می شود.
تعیین همسایگان هر گره[ویرایش]
ابتدا ، هر گره باید از طریق پیوندهای کاملاً فعال ، به پورت های دیگری که متصل است را مشخص کند . این کار را با استفاده از پروتکل قابلیت دسترسی انجام می دهد که به صورت دوره ای و جداگانه با هر یک از همسایگانی که به طور مستقیم متصل می شوند اجرا می شود.
توزیع اطلاعات برای نقشه[ویرایش]
سپس ، هر گره به صورت دوره ای (و در صورت تغییر اتصال) یک پیام کوتاه ، تبلیغات حالت پیوند را ارسال می کند ، که:
- گره تولید کننده آن را شناسایی می کند.
- تمام گره های دیگر (روتر یا شبکه) را که مستقیماً به آنها متصل است شناسایی می کند.
- شامل "شماره توالی" است ، که هر زمان گره منبع نسخه جدیدی از پیام را ایجاد می کند ، افزایش می یابد .
این پیام به همه گره های شبکه ارسال می شود. به عنوان یک پیش درآمد ضروری ، هر گره در شبکه ، برای هر یک از همسایگان خود ، شماره توالی آخرین پیام حالت پیوند را که از آن گره دریافت کرده است ، به خاطر می آورد. هنگامی که یک تبلیغ حالت پیوند در یک گره دریافت می شود ، گره به دنباله ای که برای منبع آن پیام حالت پیوند ذخیره کرده است نگاه می کند: اگر این پیام جدیدتر باشد (یعنی شماره دنباله بیشتری داشته باشد) ، ذخیره می شود ، شماره توالی به روز می شود و یک نسخه نیز به نوبه خود برای هر یک از همسایگان آن گره ارسال می شود. این روش به سرعت یک نسخه از آخرین نسخه تبلیغات حالت پیوند هر گره به هر گره در شبکه را دریافت می کند.
شبکه هایی که الگوریتم های حالت پیوند را اجرا می کنند نیز می توانند به سلسله مراتبی تقسیم شوند که دامنه تغییرات مسیر را محدود می کند. این ویژگی ها به این معنی است که الگوریتم های حالت مقیاس بهتری را به شبکه های بزرگتر پیوند می دهند.
ایجاد نقشه[ویرایش]
سرانجام ، با در دست داشتن مجموعه کاملی از تبلیغات حالت پیوند (یکی از هر گره در شبکه) ، هر گره نمودار نقشه شبکه را تولید می کند. این الگوریتم در مجموعه تبلیغات حالت پیوند تکرار می شود. برای هر یک ، پیوندهایی را روی نقشه شبکه ایجاد می کند ، از گره ارسال کننده آن پیام ، به همه گره هایی که پیام نشان می دهد همسایه گره ارسال کننده هستند.
به نظر نمی‌رسد هیچ پیوندی به درستی گزارش شده باشد مگر اینکه دو انتها با هم توافق داشته باشند. به عنوان مثال ، اگر یک گره گزارش کند که به گره دیگری متصل است ، اما گره دیگر گزارش ندهد که به گره اول متصل است ، مشکلی پیش می آید و پیوند روی نقشه موجود نیست.
نکاتی درمورد این مرحله[ویرایش]
پیام پیوند حالت که اطلاعات مربوط به همسایگان را ارائه می دهد مجدداً محاسبه می شود ، و سپس در سراسر شبکه جاری می شود ، هر زمان که در اتصال بین گره و همسایگان آن تغییر ایجاد شود. به عنوان مثال ، هنگامی که پیوند از کار می افتد. هرگونه تغییر توسط پروتکل قابلیت دسترسی که هر گره با همسایگان خود اجرا می کند ، شناسایی می شود.
محاسبه جدول مسیریابی[ویرایش]
همانطور که در ابتدا ذکر شد ، دومین مرحله اصلی در الگوریتم حالت پیوند ، تولید جداول مسیریابی ، با بازرسی از نقشه ها است. این کار دوباره با چندین مرحله انجام می شود.
محاسبه کوتاهترین مسیرها[ویرایش]
هر گره به طور مستقل یک الگوریتم را روی نقشه اجرا می کند تا کوتاهترین مسیر از خودش به هر گره دیگر در شبکه را تعیین کند. به طور کلی برخی از انواع الگوریتم دایجسترا (Dijkstra) استفاده می شود. این بر اساس یک هزینه پیوند در هر مسیر است که شامل پهنای باند موجود است.
یک گره دو ساختار داده را حفظ می کند: یک درخت حاوی گره های "انجام شده" و یک لیست از نامزدها است . الگوریتم با خالی بودن هر دو ساختار شروع می شود. سپس گره را به گره اول اضافه می کند. نوع الگوریتم حریص پس از تکرار موارد زیر را انجام می دهد:
- همه گره های همسایه که مستقیماً به گره متصل هستند ، فقط به درخت اضافه می شوند (به استثنای گره هایی که از قبل یا در درخت یا در لیست نامزدها وجود دارند). بقیه به لیست دوم (نامزد) اضافه می شوند.
- هر گره در لیست نامزد با هر یک از گره های موجود در درخت مقایسه می شود. گره کاندیدایی که به نزدیکترین گره موجود در درخت نزدیک است ، خود به درون درخت منتقل شده و به گره همسایه مناسب متصل می شود. وقتی گره ای از لیست نامزدها به درون درخت منتقل می شود ، از لیست نامزد حذف می شود و در تکرارهای بعدی الگوریتم در نظر گرفته نمی‌شود.
دو مرحله بالا تا زمانی که گره هایی در لیست نامزدها باقی مانده باشد ، تکرار می شوند. (وقتی هیچ موردی وجود نداشته باشد ، همه گره های شبکه به درخت اضافه می شوند. ) این رویه با درختی که شامل تمام گره های شبکه است ، با گره ای که الگوریتم روی آن به عنوان ریشه درخت در حال اجرا است ، پایان می یابد. کوتاهترین مسیر از آن گره به هر گره دیگر با لیستی از گره هایی که برای عبور از ریشه درخت ، به گره مورد نظر در درخت عبور می کند ، نشان داده می شود..!
پر کردن جدول مسیریابی[ویرایش]
با داشتن کوتاهترین مسیرها ، مرحله بعدی پر کردن جدول مسیریابی است. برای هر گره مورد نظر ، بهترین مسیر برای آن مقصد گره ای است که اولین مرحله از گره ریشه است ، پایین شاخه در درخت کوتاه ترین مسیر که به گره مقصد مورد نظر منتهی می شود. برای ایجاد جدول مسیریابی ، فقط لازم است که درخت را بپیمایید ، هویت گره در سر هر شاخه را به یاد داشته باشید، و ورودی جدول مسیریابی برای هر گره ای که با آن هویت روبرو می شود پر کردنید.
بهینه سازی الگوریتم[ویرایش]
الگوریتم توضیح داده شده در بالا برای کمک به سهولت درک به ساده ترین شکل ممکن ساخته شده است. در عمل ، تعدادی بهینه سازی وجود دارد که استفاده می شود.
محاسبه مجدد جزئی[ویرایش]
هر زمان که تغییری در نقشه اتصال اتفاق می افتد ، لازم است درخت کوتاهترین مسیر را دوباره محاسبه کنید و سپس جدول مسیریابی را دوباره ایجاد کنید. کار توسط BBN Technologies[نیازمند منبع] کشف کرد که چگونه فقط آن قسمت از درخت را که می توانست تحت تأثیر تغییر داده شده در نقشه قرار گیرد دوباره محاسبه کند . همچنین ، جدول مسیریابی معمولاً با محاسبه درخت کوتاه ترین مسیر ، به جای اینکه آن را به یک عمل جداگانه محاسبه کند ، پر می شود.
کاهش توپولوژی[ویرایش]
در بعضی موارد کاهش تعداد گره هایی که پیام های LSA را تولید می کنند منطقی است. به عنوان مثال ، گره ای که فقط یک اتصال به نمودار شبکه دارد ، نیازی به ارسال پیام های LSA ندارد ، زیرا اطلاعات موجودیت آن می تواند از قبل در پیام LSA همسایه خود باشد. به همین دلیل می توان از یک استراتژی کاهش توپولوژی استفاده کرد که در آن فقط زیرمجموعه ای از گره های شبکه پیام های LSA را تولید می کنند. دو روش به طور گسترده ای مورد مطالعه برای کاهش توپولوژی عبارتند از:
- رله های MultiPoint که در پایه پروتکل OLSR قرار دارند اما برای OSPF نیز پیشنهاد شده‌اند [۴]
- مجموعه های مسلط متصل که دوباره برای OSPF پیشنهاد شده‌اند [۵]
Fisheye State Routing[ویرایش]
با استفاده از LSA ، FSR با مقادیر مختلف TTL ارسال می شود تا انتشار آنها را محدود کرده و هزینه های اضافی ناشی از پیام های کنترل را محدود کند. درپروتکل مسیریابی حالت پیوند Hazy Sighted نیز از همین مفهوم استفاده شده است.
حالت های شکست[ویرایش]
اگر همه گره ها دقیقاً از یک نقشه کار نکنند ، حلقه های مسیریابی می توانند تشکیل شوند. اینها موقعیت هایی است که در ساده ترین شکل ، دو گره همسایه فکر می کنند دیگری بهترین مسیر برای رسیدن به یک مقصد مشخص است. هر بسته ای که به آن مقصد می رسد و به هر گره می رسد بین این دو حلقه قرار می گیرد ، از این رو نام آن است. حلقه های مسیریابی شامل بیش از دو گره نیز امکان پذیر است.
این می تواند از آنجا رخ دهد که هر گره درخت کوتاه ترین مسیر و جدول مسیریابی خود را محاسبه می کند بدون اینکه به هیچ وجه با گره های دیگر تعامل داشته باشد. اگر دو گره با نقشه های مختلف شروع شوند ، می توان سناریوهایی ایجاد کرد که در آنها حلقه های مسیریابی ایجاد شوند. در شرایط خاص ، حلقه های دیفرانسیل ممکن است در یک محیط چند ابر فعال شوند. گره های دسترسی متغیر در سراسر پروتکل رابط همچنین ممکن است مشکل گره دسترسی همزمان را دور بزنند. [۶]
پروتکل مسیریابی حالت پیوند بهینه برای شبکه های موقت تلفن همراه[ویرایش]
پروتکل مسیریابی حالت پیوند بهینه (OLSR) یک پروتکل مسیریابی حالت پیوند است که برای شبکه های موقت تلفن همراه بهینه شده است (که می تواند در سایر شبکه های بی سیم موقت نیز استفاده شود). [۷] OLSR فعال است ، از پیام های Hello و Topology Control (TC) برای کشف و انتشار اطلاعات وضعیت پیوند به شبکه موقت تلفن همراه استفاده می کند . با استفاده از پیام های Hello ، هر گره اطلاعات همسایه 2-هاپ را کشف می کند و مجموعه ای از رله های چند نقطه (MPR) را انتخاب می کند. MPR ها OLSR را از سایر پروتکل های مسیریابی حالت پیوند منحصر به فرد می کنند. گره های فردی از اطلاعات توپولوژی برای محاسبه مسیرهای بعدی هاپ با توجه به همه گره های شبکه با استفاده از کوتاهترین مسیرهای انتقال هاپ استفاده می کنند.
منابع[ویرایش]
- ↑ John M. McQuillan, Isaac Richer and Eric C. Rosen, ARPANet Routing Algorithm Improvements, BBN Report No. 3803, Cambridge, April 1978
- ↑ John M. McQuillan, Isaac Richer and Eric C. Rosen, The New Routing Algorithm for the ARPANet, IEEE Trans. on Comm., 28(5), pp. 711–719, 1980
- ↑ Transparent Interconnection of Lots of Links (TRILL) Use of IS-IS, RFC 7176
- ↑ rfc:5449
- ↑ rfc:5614
- ↑ Wójcik, R (2016). "A survey on methods to provide interdomain multipath transmissions". Computer Networks. 108.
- ↑ RFC 3626
- جاش سیگر و آتول خانا ، کاهش سربار مسیریابی در DDN در حال رشد ، MILCOMM '86 ، IEEE ، 1986
- رادیا پرلمن "Rbridges: مسیریابی شفاف" بایگانی‌شده در ۲۶ ژوئیه ۲۰۱۱ توسط Wayback Machine ، Infocom 2004.
برای مطالعه بیشتر[ویرایش]
- بخش "حالت پیوند در مقابل بردار فاصله" بایگانی‌شده در ۱۴ دسامبر ۲۰۱۰ توسط Wayback Machine در فصل "مبانی مسیریابی" در سیسکو "کتابچه راهنمای فناوری کار در اینترنت"