الگوریتمهای LS

از ویکی جامع پردیس دانشگاهی دانشگاه قم
پرش به: ناوبری، جستجو
مهندسی اینترنت
مقاله بعدی:الگوریتمهای DV
مقاله قبلی:روش ارسال سیل آسا یا flooding


به طور کلی در یک الگوریتم مسیریابی LS باید پنج عمل زیر توسط هر مسیریاب اجرا شوند:

1

مسیریابهای همسایه ی خود را شناسایی کرده و آدرس IP آنها را بدست آورد. این کار با ارسال یک بسته ی خاص به نام Hello Packet بر روی تمام واسطهای خروجی مسیریاب انجام میشود. مسیریابهایی که به صورت مستقیم با فرستنده ی پیام در ارتباط هستند، به آن پاسخ میدهند و پس از دریافت اطلاعات توسط فرستنده ی Hello Packet ، اطلاعات مورد نظر در یک جدول ذخیره میشوند.

2

هزینه ی مسیر تا مسیریابهای مجاور خود را اندازه گیری نماید. این کار ممکن است با روش خاصی و به صورت خودکار محاسبه شود (مثلاً با ارسال بسته های Echo و دریافت پاسخ آن و محاسبه ی زمان رفت و برگشت آن).

3

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

4

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

5

گراف شبکه را تشکیل داده و با استفاده از یک الگوریتم مناسب مسیر بهینه را بین هر دو مسیریاب در شبکه تعیین نماید. یکی از نمونه های مسیر بهینه بین دو مسیریاب کوتاهترین مسیر بین آنها است که میتوان برای یافتن آن از الگوریتم دایجسترا استفاده نمود. جدول حاصل شده پس از اجرای محاسبات تا دفتهی بعد که فرایند به روزرسانی انجام میشود در اختیار پروتکل IP قرار خواهد داشت. لازم به ذکر است که اگر یک مسیریاب اطلاعات غلطی را برای سایر مسیریابها فراهم کند، کل مسیریابی شبکه با مشکل مواجه میشود و تمام جداول مسیریابی با اطلاعات آلوده تنظیم خواهند شد. در ادامه با یک مثال استفاده از الگوریتم دایجسترا شرح داده میشود. شکل ۳ نمایش دهنده ی مراحل مختلف انجام این مثال است. در این مثال با توجه به گراف شبکه ی موجود و با توجه به هزینه ی ثبت شده برای مسیرهای بین هر جفت مسیریاب، کم هزینه ترین مسیر بین گره A (مسیریاب A) و گره D یافت میشود. لازم است که در طول اجرای مثال به ازای هر کدام از گره ها اطلاعات مشخصی شامل هزینه ی فعلی از مبدأ تا این گره، گره قبلی در مسیر حاصل شده و یک مشخصه ی خاص برای تعیین وضعیت گره (دائمی یا موقت) نگهداری میشوند. مقدار اولیه برای هزینه برابر با مقدار بینهایت است. گره قبلی در مسیر در ابتدای کار بدون مقدار است و وضعیت اولیه ی تمام گرهها در ابتدای کار به صورت موقت میباشد. مراحل مختلف اجرای مثال در ادامه ذکر میگردند.

مرحله ی 1:

وضعیت گره مبدأ که همان گره A است به صورت دائمی تغییر میکند. بدین معنی که کار این گره در فرایند یافتن کوتاهترین مسیر پایان یافته است. در شکل ۳ گره های دائمی با یک دایره ی توپر نمایش داده شده اند. در این مرحله که نشانگر (<-) به گره A اشاره میکند، هزینه از مبدأ تا گره های همسایه ی این گره (گرههای B و G که دارای وضعیت موقت هستند) محاسبه شده و به همراه گره پیشین در مسیر (گره A )، برای گره های همسایه ثبت میگردد.

مرحله ی 2:

سپس از بین تمام گره های دارای وضعیت موقت، گره با کمترین مقدار هزینه تا مبدأ (گره B ) انتخاب میشود، نشانگر به آن انتقال یافته و وضعیت آن به دائمی تغیر مییابد.

مرحله ی 3:

مقدار هزینه از گره A تا گرههای همسایه ی B که دارای وضعیت موقت هستند (گرههای C و E ) محاسبه شده و به همراه گره پیشین در مسیر (گره B ) برای آنها ثبت میشود. در این مرحله از بین تمام گرههای دارای وضعیت موقت، گره E دارای کمترین هزینه تا مبدأ است و نشانگر به آن انتقال مییابد. وضعیت گره E نیز به صورت دائمی ثبت میگردد.

مرحله ی 4:

هزینه ی گره های همسایه ی E که دارای وضعیت موقت هستند محاسبه یا اصلاح میشود و گره پیشین در مسیر برای آنها ثبت میگردد. توجه شود که با وجود اینکه مقدار هزینه تا مبدأ، قبلاً برای گره G محاسبه شده بود، به دلیل اینکه مقدار هزینه ی جدید از مقدار قبلی ثبت شده کمتر است، مقدار جدید مورد استفاده قرار میگیرد و گره قبلی در مسیر نیز برای آن اصلاح میشود و شامل گره E میگردد. از بین تمام گره های دارای وضعیت موقت، گره G دارای کمترین مقدار هزینه است و نشانگر به آنجا انتقال مییابد و وضعیت آن به صورت دائمی میگردد.

مرحله ی 5:

پس از اصلاح هزینه ی گرههای موقت همسایه ی G و ثبت گره قبلی در مسیر برای آنها، از بین تمام گره های موقت موجود در گراف، گره F به عنوان گره جاری انتخاب شده و نشانگر به آنجا انتقال مییابد. وضعیت این گره به صورت دائمی میشود.

مرحله ی ۶:

هزینه ی گره های C و H به عنوان همسایه های موقت گره F محاسبه شده و گره قبلی در مسیر برای آنها ثبت میگردد. هزینه از مبدأ تا گره H اصلاح شده و از مقدار 9 به ۸ کاهش مییابد. از بین تمام گرههای موقت موجود (گرههای C ، H و D) گره H دارای کمتری ن هزینه تا مبدأ است و نشانگر به آنجا انتقال مییابد که باعث دائمی شدن وضعیت آن میگردد.

مرحله ی 7:

هزینه ی گره های همسایه ی H که وضعیت موقت دارند (گره D ) تا مبدأ (گره A) محاسبه شده و به همراه گره قبلی در مسیر برای آن ثبت میشود. در این قسمت مشاهده میشود که از بین گره های موقت موجود در گراف (گرههای C و D)، گره C از هزینه ی کمتری برخوردار است. پس نشانگر به آنجا انتقال یافته و وضعیت آن دائمی میشود.

مرحله ی ۸:

با محاسبه ی مقدار هزینهی جدید برای گره D (تنها گره موقت موجود) مشاهده میشود که هزینه ی قبلی آن از وضعیت بهتری برخوردار است (مقدار کمتری دارد) و در نتیجه، مقدار جدید محاسبه شده برای آن ثبت نمیشود. تنها گره موقت موجود (یعنی گره D که همان مقصد است) در این مرحله به وضعیت دائمی انتقال مییابد در شرایطی که هزینه ی رسیدن به آن از گره مبدأ برابر با 10 است و گره قبلی آن در مسیر برابر با گره H است. در نهایت و برای بدست آوردن مسیر کامل، از گره D شروع کرده و گره قبلی آن پیدا میشود. این کار به صورت بازگشتی انجام میشود تا به نقطه ی شروع (گره A ) برسد. Mef4sh2.PNG