پرتکل های مسیریابی و درجه مشارکت نودها در مسیریابی
امروزه تمایل به استفاده از شبکه های بی سیم روز به روز در حال افزایش است ، چون هر شخصی، هر جایی و در هر زمانی می تواند از آنها استفاده نماید . در سالهای اخیر رشد شگرفی در فروش کامپیوترهای laptop و کامپیوترهای قابل حمل بوجود آمده است . این کامپیوترهای کوچک،به چندین گیگا بایت حافظه روی دیسک ، نمایش رنگی با کیفیت بالا و کارتهای شبکه بی سیم مجهز هستند . علاوه بر این ، این کامپیوترهای کوچک می توانند چندین ساعت فقط با نیروی باتری کار کنند و کاربران آزادند براحتی آنها را به هر طرف که می خواهند منتقل نمایند . زمانی که کاربران شروع به استفاده از کامپیوترهای متحرک نمودند ، به اشتراک گذاشتن اطلاعات بین کامپیوترها یک نیاز طبیعی را بوجود آورد . از جمله کاربردهای به اشتراک گذاری اطلاعات در مکانهایی نظیر سالن کنفرانس ،کلاس درس ، ترمینالهای فرودگاه و همچنین در محیط های نظامی است .
دوروش برای ارتباط بی سیم بین کامپیوترهای متحرک وجود دارد .
1- استفاده از یک زیر ساخت ثابت که توسط یک Acces point خارج شد آنگاه در محدوده رادیویی Wireless Access point ها فراهم می آید . که در این گونه شبکه ها ، نودهای متحرک از طریق Access Point ها با یکدیگر ارتباط برقرار می کنند و هنگامیکه یک نود از محدوده رادیویی Access Pointدیگری قرار می گیرد . مشکل اصلی در اینجا هنگامی است که یک اتصال باید از یک Access Point به Access Point دیگری تحویل داده شود ، بدون آنکه تاخیر قابل توجهی به وجود آید ویا بسته ای گم شود .
2- شکل دادن یک شبکه بی سیم Adhoc در بین کاربرانی است که می خواهند با هم ارتباط داشته باشند . این گونه شبکه ها زیر ساخت ثابتی ندارند و کنترل کننده و مرکزی نیز برای آنها وجود ندارد .
شبکه های بی سیم Adhoc از مجموعه ای از نودهای متحرک تشکیل شده اند که این نودها قادرند به طور آزادانه و مداوم مکانشان را در شبکه تغییر دهند . نودهای موجود در شبکه Adhoc همزمان به عنوان client و مسیریاب عمل می کنند و با توجه به عدم وجود ساختار ثابت در این گونه شبکهها ، نودها مسئولیت مسیریابی را برای بسته هایی که می خواهند در شبکه ارسال شوند بر عهده دارند و در انجام این امر با یکدیگر همکاری می کنند .
هدف ما نیز در اینجا بررسی و مطالعه بر روی خصوصیات و ویژگی های این تکنیکهای مسیر یابی است . لازم بذکر است پروتکل های مسیریابی متفاوتی برای استفاده در شبکه های Adhoc پیشنهاد شده اند که پس از مطالعه اجمالی برروی نحوه عملکرد هر یک از آنها ، قادر خواهیم بود آنها را بر طبق خصوصیاتشان قسمت بندی نمائیم .
چرا نیاز به طراحی پروتکلهای مسیر یابی جدیدی برای شبکه های Adhoc وجود دارد ؟
در شبکه های سیم دار تغییرات در توپولوژی شبکه بندرت اتفاق می افتد . بیشتر host ها و نودهای دیگر در یک جای مشخصی در شبکه قرار دارند ویک شکستگی در لینک زمانی اتفاق میافتد که یک قطع فیزیکی نظیر fail شدن host و یا خسارت فیزیکی کامل اتفاق بیفتد . برای این نوع شبکه های سیم دار با ساختار ثابت یک الگوریتم مسیریابی کلاسیک به خوبی کار می کند.
برای اینکه اطلاعات جداول مسیریابی بروز باشند ،مسیریابها به صورت دوره ای اطلاعاتشان را با یکدیگر مبادله می کنند و در حالتی که یک failure ی در لینکی اتفاق بیفتد مسیرها باید مجدداً محاسبه شوند ودر شبکه منتشر گردند. این پروسه یک مدت زمانی طول می کشد که چنین چیزی در شبکه های سیم دار طبیعی است و آشکار است که چنین روشی در شبکه های Adhoc کار نخواهد کرد . در این شبکه ها از آنجایی که نودها مرتباً در حال حرکت هستند ، تغییراتی که در لینکها به وجود می آید نیز بسیار مداوم خواهد بود . به عنوان مثال زمانی را در نظر بگیرید که 2 تا نود در حالی با هم ارتباط برقرار کرده اند که مدام از همدیگر فاصله می گیرند . تا زمانی که هردوی آنها در محدوده ارتباطی همدیگر باشند این ارتباط می تواند حفظ گردد. ولی هنگامیکه فاصله بین نودها بیشتر شود دیگر این ارتباط نیز میسر نخواهد بود . حال تصور کنید که تعداد زیادی از نودها مطابق این سناریو رفتار نمایند ، در این حالت لینکهای زیادی شکل خواهند گرفت ومسیرهای جدیدی به سمت مقصدها محاسبه خواهد شد و در مقابل لینکهای بسیاری نیز شکسته خواهند شد و مسیرهای بسیاری نیز از بین خواهند رفت .
از دیگر مواردی که می توان به عنوان دلایل نیاز به طراحی پروتکلهای مسیریابی جدید برای شبکههای Adhoc به آنها اشاره کرد عبارتند از :
- پروتکلهای مسیریابی شبکه های سیم دار بار محاسباتی بسیار زیادی را به صورت مصرف زیاد حافظه و همچنین مصرف زیاد انرژی بر روی هر کامپیوتر قرار می دهند .
- پروتکلهای مسیریابی مورد استفاده در شبکه های سیم دار از مشکلات به وجود آوردن حلقههای کوتاه مدت وبلند مدت رنج می برند .
- متدهایی که برای حل مشکلات ناشی از بوجود آوردن حلقه ها در پروتکلهای مسیریابی سنتی استفاده می شوند در شبکه های Adhoc عملی نیستند .
این تفاوتها بین شبکه های سیم دار و بی سیم به راحتی آشکار می کند که یک پروتکل مسیریابی برای شبکه های Adhoc باید یکسری از مشکلات اضافه تری را حل نماید که این مشکلات در شبکه های سیم دار وجود نداشته است .
در زیر لیستی از مواردی را که یک پروتکل مسیریابی باید آنها را مدنظر قرار دهد ذکر گردیده که بعضی از این خصوصیات مهمتر از خصوصیات دیگر هستند .
به طور کلی اهداف طراحی پروتکلهای مسیریابی این است که پروتکلی ساخته شود که :
1- وقتی که توپولوژی شبکه گسترش می یابد این پروتکل نیز بتواند همچنان مسیریابی را انجام دهد .
2- زمانی که تغییراتی در توپولوژی شبکه به وجود می آید این پروتکل سریعاً قادر به پاسخگویی باشد .
3- مسیرهایی را فراهم کند که بدون حلقه باشد .
4- تاخیر را به حداقل رساند (باانتخاب مسیرهای کوتاه )
5- برای اجتناب از تراکم چندین مسیر را از مبدأ به مقصد فراهم نماید .
پروتکل طراحی شده برای مسیریابی در یک شبکه Adhoc باید خصوصیات زیررا دارا باشد .
1- اجرای غیر مرکزی داشته باشد ، به این معنی که نباید به یک نود مرکزی وابسته باشد .
2- استفاده از پهنای باند را کار اگرداند (overhead مسیریابی را می نیمم کند )
3- هم از لینکهای یکطرفه و هم از لینکهای دو طرفه استفاده کند .
تقسیم بندی پروتکلهای مسیریابی در شبکه های Adhoc
چندین معیار متفاوت برای طراحی و کلاس بندی پروتکلهای مسیر یابی در شبکه های Adhoc وجود دارد . به عنوان مثال اینکه چه اطلاعات مسیریابی مبادله می شوند ؟ چه زمانی و چگونه این اطلاعات مبادله میشوند ؟ چه زمانی و چگونه مسیرها محاسبه می شوند .
که ما در این بخش در مورد هر یک از این معیارها مطالبی را بیان خواهیم کرد .
- مسیریابی Link State در مقابل مسیریابی DisTance Vector
همانند شبکه های سیم دار عرف ، LSR و DVR مکانیزم های زیرین برای مسیریابی در شبکههای Adhoc بی سیم می باشند . در LSR اطلاعات مسیریابی به شکل بسته های Link State
(Link State Packets) مبادله می شوند . LSP یک نود شامل اطلاعات لینکهای همسایگانش است . هرنود زمانی که تغییری را در لینکی شناسایی کند LSP هایش را فوراً در کل شبکه جاری می کند . نودهای دیگر بر اساس اطلاعاتی که از LSP های دریافتی شان بدست می آورند ، توپولوژی کل شبکه را ترسیم می کنند و برای ساختن مسیرهای لازم از یک الگوریتم کوتاهترین مسیر نظیردایجکسترا استفاده می کنند .
لازم به ذکر است تعدادی از هزینه های لینکها از دید یک نود می توانند غیر صحیح باشند واین بدلیل تاخیر زیاد انتشار و قسمت بندی بودن شبکه است . این دیدهای ناسازگار از توپولوژی شبکه می تواند مارا به سمت تشکیل مسیرهایی دارای حلقه سوق دهد . اگرچه این حلقه ها عمرشان کوتاه است وبعد از گذشت مدت زمانی (مدت زمانی که طول می کشد تا یک Message قطر شبکه را بپیماید ) ناپدید می شوند . مشکلی که در LSR وجود دارد overhead بالای مسیریابی است که بدلیل حرکت سریع نودها در شبکه و در نتیجه تغییرات سریع در توپولوژی شبکه اتفاق می افتد .
در مکانیزم DVR ، هر نود یک بردار فاصله که شامل شناسه مقصد ، آدرس hop بعدی ، کوتاهترین مسیر. می باشد را برای هر مقصدی نگهداری می کند . هر نود بصورت دوره ای بردارهای فاصله را با همسایگانش مبادله می کند . هنگامیکه نودی بردارهای فاصله را از همسایگانش دریافت می کند ، مسیرهای جدید را محاسبه می کند و بردار فاصله اش را نیز Update می کند و یک مسیر کاملی را از مبدأ تا مقصد شکل می دهد . مشکلی که در مکانیزم DVR وجود دارد همگرایی کند آن وتمایلش به تولید مسیرهای دارای حلقه است .
Event – driven Update در مقابل Periodical Update
برای تضمین اینکه اطلاعات مربوط به موقعیت لینکها و توپولوژی شبکه بروز باشد ، اطلاعات مسیریابی باید در شبکه منتشر شوند . براساس اینکه چه زمانی اطلاعات مسیریابی منتشر خواهند شد قادر خواهیم بود که پروتکلهای مسیریابی را به 2 دسته تقسیم بندی نمائیم . دسته اول پروتکلهایی هستند که به صورت دوره ای اطلاعات مسیریابی را منتشر می کنند و دسته دوم مربوط به پروتکلهایی است که در زمان وقوع تغییری در توپولوژی شبکه اطلاعات مسیریابی را انتشار میدهند .
پروتکلهای Periodical Update ، اطلاعات مسیریابی را بصورت دوره ای پخش می کنند . این پروتکلها ،پروتکلهای ساده ای هستند و پایداری شبکه ها را حفظ می کنند و مهم تر از همه این است که به نودهای جدید امکان می دهند که اطلاعات مربوط به توپولوژی و موقعیت لینکها را درشبکه بدست آورند. اگرچه ،در صورتی که مدت زمان بین این بروز رسانی های دوره ای طولانی باشد آنگاه این پروتکلها نمی توانند اطلاعات بروز ر انگه دارند . از طرف دیگر ، در صورتی که این مدت زمان کوتاه باشد ، تعداد بسیار زیادی از بسته های مسیریابی منتشر خواهند شد که در نتیجه پهنای باند زیادی را از یک شبکه بی سیم مصرف خواهد کرد .
در یک پروتکل بروز رسانی Event – Driven ، هنگامیکه یک حادثه ای اتفاق می افتد ، ( نظیر اینکه یک لینک fail می شود و یا اینکه یک لینک جدیدی بوجود می آید )، یک بسته مسیریابی جهت بروزرسانی نمودن اطلاعات مسیریابی موجود در نودهای دیگر ، broadkact می شود . مشکل زمانی بوجود خواهد آمد که توپولوژی شبکه بسیار سریع تغییر کند ، که در آن هنگام تعداد زیادی از بسته های بروز رسانی تولید و در شبکه پخش خواهند شد که این موجب مصرف مقدار زیادی از پهنای باند ونیز تولید نوسانات بسیاری در مسیرها می گردد .
مکانیزم های بروز رسانی دوره ای و بروز رسانی Event Driven می توانند با یکدیگر استفاده شوند و یک مکانیزمی به نام مکانیزم بروز رسانی ترکیبی (Hybrid Update ) را به وجود آورند .
- ساختارهای مسطح (Flat ) در مقابل ساختارهای سلسله مراتبی (Hierarchical)
دریک ساختار مسطح همه نودها در شبکه در یک سطح قرار دارند و دارای عملکرد مسیریابی مشابهی می باشند ، مسیریابی مسطح برای استفاده در شبکه های کوچک ، ساده وکارا است .
در مسیریابی سلسله مراتبی نودها به صورت دینامیک در شبکه به قسمتهایی که clustor نامیده میشوند سازماندهی می گردند ، سپس مجدداً این clustor هادر کنار یکدیگر تجمع می کنند وSuperclustor ها را می سازند وبه همین ترتیب ادامه می یابد .
سازماندهی یک شبکه به clustor به نگهداری توپولوژی یک شبکه نسبتاً پایدار کمک می کند .
در شبکه هایی که عضویت در آنها و همچنین تغییرات در توپولوژی بسیار داینامیک باشد استفاده از cluster ها کارایی چندانی نخواهد داشت .
- محاسبات غیر متمرکز(Decentralizad) در مقابل محاسبات توزیع شده (Distributed)
براساس اینکه چگونه و در کجا یک مسیر محاسبه می شود 2 بخش برای پروتکلهای مسیریابی به وجود می آید . محاسبات Decentralized و محاسبات توزیع شده .
در یک پروتکلی که بر اساس محاسبات Decentralized باشد ، هرنود در شبکه از اطلاعات کاملی راجع به توپولوژی شبکه نگهداری می کند بطوریکه هر زمان که مایل باشد بتواند خودش یک مسیری را به سمت مقصد مورد نظر محاسبه کند . برخلاف آن ، در پروتکلی که بر اساس محاسبات توزیع شده باشد هر نود در شبکه فقط قسمتی از اطلاعات مربوط به توپولوژی شبکه را نگهداری می کند . هنگامیکه یک مسیری نیاز به محاسبه داشته باشد ، تعداد زیادی از نودها با هم همکاری می کنند تا آن مسیررا محاسبه کنند .
- Source Routing درمقابل hop- by-hop Routing
بعضی از پروتکلهای مسیریابی کل مسیر را در header مربوط به بسته های اطلاعاتی قرار می دهند بنابراین نودهای میانی فقط این بسته ها را بر طبق مسیری که در header شان وجود دارد forward میکنند . به چنین مسیریابی ، مسیریابی از مبدأ یا Source Routing گفته می شود . مزیت این گونه مسیریابی ها در این است که نودهای میانی نیازی ندارند که اطلاعات مسیریابی بروز شده را نگهداری کنند چون خود بسته ها شامل تمام تصمیمات مسیریابی می باشند . بزرگترین مشکل این مسیریابی، زمانی است که شبکه بزرگ باشد ومسیرها طولانی باشند در این حالت قرار دادن کل مسیر در header هر بسته مقدار زیادی از پهنای باند را مصرف خواهد کرد . لازم بذکر است که مسیریابی Source Route ، امکان تولید چندین مسیر را به سمت یک مقصد خاص فراهم می کند . در مسیریابی hop- by- hop ، هنگامیکه یک نود بسته ای را برای یک مقصدی دریافت می کند ، بر طبق آن مقصد بسته را به hop بعدی forward خواهد کرد . مشکل این است که همه نودها نیاز دارند که اطلاعات مسیریابی را نگهداری کنند وبنابراین این امکان وجود دارد که مسیرهای دارای حلقه شکل بگیرند .
-مسیرهای منفرد در مقابل مسیرهای چندگانه
بعضی از پروتکلهای مسیریابی یک مسیر منفرد را از مبدأ به مقصد پیدا می کنند که این گونه پروتکلها معمولاً عملکرد ساده ای دارند . پروتکلهای مسیریابی دیگری نیز هستند که چندین مسیر را به سمت یک مقصد معین پیدا می کنند که مزیت آن قابلیت اطمینان بالاتر و همچنین بهبودی راحتتر در هنگام وقوع failure می باشد . علاوه بر این ، نود مبدأ می تواند بهترین مسیر را از میان مسیرهای در دسترس انتخاب نماید .
مسیریابی ProActive در مقابل مسیریابی ReAvtive
بسته به اینکه چه زمانی مسیرها محاسبه می شوند ، پروتکلهای مسیریابی می توانند به 2 بخش تقسیم شوند . مسیریابی ProActive و مسیریابی ReActive .
مسیریابی ProActive ، مسیریابی Precomputed و یا Table-Driven نیز نامیده می شود . دراین متد ، مسیرها از قبل به سمت تمام مقصدها محاسبه می شوند . برای محاسبه مسیرها ، نودها نیاز دارند که تمام ویا قسمتی از اطلاعات را در مورد موقعیت های لینکها و توپولوژی شبکه نگهداری کنند و برای اینکه این اطلاعات را بروز رسانی نمایند ، احتیاج دارند که بصورت دوره ای ویا در زمانی که موقعیت لینکی یا توپولوژی شبکه ای تغییر کرد اطلاعاتشان را منتشر نموده و براساس اطلاعات بدست آمده جداولشان را نیز Update نمایند . مزیت مسیریابی ProActive این است که زمانی که یک مبدأ نیازمند ارسال بسته ای به مقصدی باشد ، مسیر مورد نظر در دسترس است و هیچ اتلاف زمانی صورت نمی پذیرد . عیبی که برای این گونه مسیریابی ها مطرح می باشد این است که بعضی از مسیرهای تولید شده ممکن است هیچ گاه استفاده نشوند و همچنین اینکه در هنگامیکه تغییرات در توپولوژی شبکه سریع باشد ، انتشار اطلاعات مسیریابی ممکن است مقدار زیادی از پهنای باند را مصرف نماید .
مسیریابی ReActive ، مسیریابی On-Demand نیز نامیده می شود . دراین متد ، مسیر به سمت یک مقصد وجود ندارد و فقط هنگامیکه آن مسیر مورد نیاز باشد اقدامات لازم جهت محاسبه آن صورت می پذیرد . ایده اصلی این نوع مسیریابی به صورت زیر است :
هنگامیکه یک مبدأ نیاز دارد که بسته ای را به سمت یک مقصدی بفرستد ، ابتدا یک یا چند مسیر را به سمت آن مقصد شناسایی می کند که به این پروسه ، پروسه کشف مسیر و (Route Discovery) گفته می شود . بعد از اینکه آن مسیر یا مسیرها بدست آمدند ، مبدأ بسته مورد نظر را از طریق یکی از آنها ارسال می کند . در طول انتقال بسته ها ، ممکن است که بدلیل حرکت مداوم نودها در شبکه ، مسیرها شکسته شوند .
مسیر های شکسته شده نیازمند بازسازی هستند . پروسه شناسایی شکست مسیرها و بازسازی آنها نگهداری مسیر و (Route maintenance) نام دارد .
مزیت اصلی مسیریابی On-Demand صرفه جویی در پهنای باند است زیرا از انتشار اطلاعات مسیریابی به صورت دوره ای و یا جاری نمودن این اطلاعات هنگامیکه تغییری در موقعیت لینکی اتفاق می افتد جلوگیری می کند.
مشکل اصلی این نوع مسیریابی تاخیر زمانی زیادی است که در ابتدا برای انجام عمل کشف مسیر باید انجام بگیرد .
لازم بذکر است که استراتژی دیگری نیز برای مسیریابی در شبکه های Adhoc وجود دارد و این استراتژی ترکیبی از مسیریابی هایProActive و ReActive می باشد و اصطلاحاً به آن Hybrid می گویند . در این گونه پروتکلها یک شبکه به تعدادی ناحیه تقسیم می شود که از مسیریابی ProActive در داخل این نواحی و از مسیریابی ReActive برای مسیریابی در بین نواحی مذکور استفاده می شود . این روش برای شبکه های بزرگی که تقسیم بندی نواحی در آنها انجام می گیرد بسیار مناسب و کارا است . به غیر از مکانیزم های فوق ، مکانیزم مسیریابی دیگری نیز وجود دارد که Flooding نامیده می شود . در Flooding ، هیچ مسیری محاسبه و یا کشف نمی شود . یک بسته به تمام نودها در شبکه فرستاده می شود و انتظار داریم که حداقل یک کپی از بسته به مقصد مورد نظر برسد . ناحیه بندی می تواند برای محدودتر کردن سربارکاری در مکانیزم Floding استفاده شود .
این متد ساده ترین متد مسیریابی است زیرا نیاز به هیچ دانشی در مورد توپولوژی شبکه ندارد و عموماً برای ارسال بسته های کنترلی (اطلاعات مسیریابی ) استفاده می شود ، نه برای ارسال بسته های اطلاعاتی .
هدف ما در این جا مطالعه برروی 2 دسته پروتکلهای Table- Driven و On-Demand می باشد . دراین راستا به بررسی خصوصیات و ویژگی های چند نمونه از پروتکلهای مسیریابی می پردازیم و آنها را بر اساس عملکردشان در دسته های ذکر شده فوق قرار می دهیم .