مقایسه پروتکل های مسیریابی DSR و AODV
مقایسه کارایی پروتکل های مسیریابی در شبکه MANET
پروتکل های مسیریابی یکی از پارامترهای مؤثر در توانایی MANET در انتقال مالتی مدیا از منبع به مقصد، است. شبکه های MANET – Mobile Ad-hoc Network از تعدادی گره بی سیم تشکیل می شود که می توانند بدون نیاز به یک زیرساخت موجود، هر زمان و هر جا به صورت داینامیک فعالیت کنند. در شبکه، برای اینکه مسیر از مبدأ به مقصد کشف شود، هر گره به عنوان یک روتر عمل میکند. امروزه نیاز به انتقال ترافیک مالتی مدیا روی شبکه های MANET در حال افزایش می باشد. همچنین تعداد فاکتورهایی هم که در حفظ ارتباط بلادرنگ با وجود توپولوژی داینامیک در MANET، مطرح هستند نیز افزایش می یابد. هدف اصلی ما در این گزارش، مقایسه کارآیی دو پروتکل مسیریابی AODV و DSR در شرایط تحرک بالای شبکه تحت چگالی های شبکه مختلف می باشد. این پروتکل ها هر دو reactive هستند. هرچند این دو پروتکل رفتار on-Deman یکسانی را از خود نشان می دهند، ولی تفاوت های موجود در مکانیزم داخلی این دو پروتکل منجر به تفاوت های چشمگیری در کارآیی می شود. نتایج تحقیقات نشان می دهد که با افزایش تعداد گره های متحرک در شبکه، AODV از لحاظ تأخیر انتها به انتها، میزان توان عملیاتی و بار شبکه، رفتار بهتری نسبت به DSR از خود نشان می دهد.
۱. مقدمه
در شبکه های MANET هر گره می تواند به صورت مستقل و بدون نیاز به مشخص کردن جهت مشخصی حرکت کرده و به طور مکرر مسیرها را تغییر دهد. توپولوژی MANET را میتوان به شدت داینامیک در نظر گرفت و به همین دلیل ارسال دیتا میان گره ها ممکن است به صورت مکرر دچار وقفه گردد. برپایی مجدد کانکشن جدید از منبع به مقصد جهت ارسال دیتا نیاز به کشف یا همان discovery شدن تمام مسیرهای در دسترس در شبکه های ادهاک می باشد. در این شبکه ها، هر گره موبایل، علاوه بر اینکه نقش هاست را دارد، به عنوان روتر نیز عمل می کند تا قادر به فوروارد پکت های دیتا به گره های دیگر از طریق لینک های وایرلس مستقیم یا چند-گامه (multi-hop) باشد. این یعنی لینک میان گره های موبایل می تواند در طول زمان به صورت مکرر تغییر پیدا کند و گره های جدید می توانند به شبکه ملحق شوند یا گره های موجود از شبکه خارج شوند.
در شرایط حاکم بر شبکه های MANET یک پروتکل مسیریابی خوب، می تواند کمترین بار محاسباتی را روی گره موبایل و همچنین کمترین سربار ترافیک را روی شبکه داشته باشد. برای کشف مسیر بین دو گره، هر پروتکل از استراتژی مسیریابی مخصوص خودش استفاده می کند. هر کدام از پروتکل ها در شرایط مختلف شبکه از جمله چگالی گره ها در ناحه خاص، سرعت و جهت حرک گره ها، کارآیی متفاوتی خواهند داشت.
در این مقاله، می خواهیم ببینیم وقتی دیتای مالتی مدیا در شبکه های موبال multi-hope در حال انتقال است، کدام پروتکل مسیریابی می تواند بهترین کارآیی را داشته باشد. پارامترهایی که برای این بررسی استفاده می شود عبارتند از:
- تأخیر انتها به انتها (End to End Delay)
- بار شبکه (Network Load)
- توان عملیاتی (Throughput)
۲. بررسی عملکرد پروتکل مسیریابی AODV
AODV – Ad-hoc On Deman Distance Vector محبوب ترین پروتکل مسیریابی reactive است که برای شبکه های ادهاک موبایل و سایر سایر شبکه های بی سیم طراحی شده است. این پروتکل قادر به یافتن مسیر بین گره ها بوده و توانایی انجام هر دو نوع مسیریابی unicast و multicast را دارد.
در AODV برای هر مقصد ممکن در شبکه، مسیر مشخص ایجاد و نگهداری نمی شود، بلکه وقتی که گره منبع پکتی برای ارسال داشته باشد، مسیرها بر اساس نیاز موجود برپاسازی می شوند (مفهوم ویژگی on-Demond). البته برای مسیرهایی که اخیراً استفاده شده اند، اطلاعات مسیریابی در جدول مسیریابی نگهداری می شود. بنابراین زمانی که یک پیام درخواست مسیر جدید می رسد، در شبکه flooding یا ارسال سیل آسا صورت نمی گیرد چراکه هر گره می تواند فقط به مقصدهای موجود در جدول مسیریابی اش، پکت ارسال کند.
برای جلوگیری از به وجود آمدن مسئله حلقه که ممکن است در فرآیند مسیریابی رخ دهد، AODV در هر مقصد برای شناسایی اطلاعات مربوط به مسیریابی کنونی، از یک Sequence Number استفاده می کند که این Sequence Number توسط کلیه پکت های مسیریابی حمل می شود تا به مقصد برسد.
۲-۱- کشف مسیر در AODV
فرآیند کشف مسیر یا route discovery وقتی شروع می شود که یک گره منبع، درخواست ارتباط با گره دیگری از شبکه داشته باشد. در این شرایط، گره ابتدا در جدول مسیریابی خود، دنبال مسیر جدید می گردد. چنانچه مسیری پیدا شود، ارتباط بلافاصله آغاز می شود ولی اگر مسیری برای ارسال پکت از منبع به مقصد پیدا نشود، گره منبع با پخش یک پکت RREQ – Route Request به همسایگانش فرآیند کشف مسیر را آغاز می کند. هر کدام از گره های همسایه چنانچه مسیری به مقصد داشته باشند، با پیام کنترلی RREP – Route Reply که از طریق مسیر عکس منتشر می شود، پاسخ می دهند و در غیر اینصورت گره همسایه نیز پیام RREQ را پخش می کند. در شکل زیر پخش پیام های RREQ و RREP در شبکه نشان داده شده است:
فرایند کشف مسیر در AODV
فرآیند کشف مسیر باید یک جایی تمام شود و نمی تواند تا بی نهایت ادامه داشته باشد. برای کنترل پخش پکت RREQ در شبکه، گره منبع از تکنیک Expanding Ring Search استفاده می کند. این جستجو با ثبت شدن محدودیت های RREQ داخل فیلد TTL – Time to Live کنترل می شود. TTL یکی از فیلدهای سرآیند IP در پکت های RREQ می باشد. در این تکنیک، هر RREQ حامل یک مقدار TTL است. مقدار TTL، تعداد hop هایی که پکت RREQ باید فوروارد شود را تعیین میکند. در اولین ارسال، مقدار TTL هنگام ارسال مجدد set می شود. ارسال مجدد زمانی صورت می گیرد که هیچ پاسخی دریافت نشود. پکتی که پخش RREQ را شروع کرده منتظر ارسال می ماند.
در AODV دو شمارنده مختلف در هر گره وجود دارد:
- Broadcast ID
- Sequence Number
شمارنده Broadcast ID درصورتی افزایش می یابد که گره دریافت کننده، مسیر مقصدی برای یک پکت RREP داشته باشد. این گره، یا یک پیام unicast را به گره منبع ارسال می کند یا پس از افزایش تعداد hop، مجدداً RREQ را به همسایگان خودش پخش می کند. این فرآیند در شکل۱ به تصویر کشیده شده است.
درضمن، گره پاسخ دهنده، یک مسیر عکس (reverse route) حاوی آدرس گره منبع، تعداد hop ها تا منبع و آدرس hop های بعدی را به جدول مسیریابی اش اضافی می کنید.
پارامترهای پکت RREQ
- Source Address
- Request ID
- Sequence Number
- Destination Address
- Destination Sequence Number
- Hop Count
پارامترهای پکت RREP
- Source Address
- Destination Address
- Destination Sequence Number
- Hop Count
- Life Time
علاوه براین، از Host-ID و Broadcast-ID هم استفاده شده تا درخواست ها منحصر بفرد شوند و از پخش تکراری یک درخواست اجتناب شود. هر Host نیز یک رکورد برای همسایه هایش نگهداری می کند تا وقایع را گزارش دهند.
۲-۲- نگهداری مسیر در AODV
مسیر برقرار شده بین منبع و مقصد، تا زمانیکه مورد نیاز منبع باشد، نگهداری خواهد شد. طی یک نشست فعال، اگر گره منبع حرکت کند، می تواند مجدداً یک فرآیند “کشف مسیر” دیگر آغاز کند تا مسیر جدیدی به گره مقصد تأسیس شود. ممکن است برخی از گره های میانی یا گره مقصد نیز حرکت داشته باشد. وقتی حرکتی صورت می گیرد، همسایگان گره حرکت کرده، متوجه شکست لینک (Link Failure) شده و پکت RERR – Route Error را به گره های منبع متأثر از این مشکل، ارسال می کنند. گره های میانی با دریافت RERR و درج مقدار بی نهایت به عنوان فاصله از مقصد، جدول مسیریابی خود را به روز می کنند. زمانیکه گره منبع، پیام RERR دریافت می کند، اگر هنوز به آن مسیر نیاز داشته باشد، می تواند مجدداً یک کشف مسیر انجام دهد.
اطلاعات همسایگی نیز با پخش دوره ای Hello Packet کسب می شود. برای نگهداری یک مسیر، دو روش وجود دارد که می توان از آنها استفاده نمود:
- Hellow Message درلایه Net
- ACK Message در لایه Mac
۲-۳- فلوچارت AODV
۳- بررسی عملکرد پروتکل مسیریابی DSR
DSR – Dynamic Sourse Routing یک پروتکل مسیریابی reactive است که مسیر مناسب را زمانی تعیین می کند که نیاز به فوروارد شدن پکتی باشد. این پروتکل از لحاظ اینکه مسیر را بر حسب نیاز برقرار می کند (on-demand بودن) مشابه AODV است. تفاوت این دو پروتکل این است که DSR به جای وابستگی به جدول مسیریابی در هر گره میانی، از Source Routing استفاده می کند. DSR به شبکه این امکان را می دهد که بدون نیاز به ادمین شبکه یا زیرساخت موجود، خودپیکربندی و خودسازماندهی را انجام دهند. هر گره متحرک در شبکه ادهاک متحرک MANET با پروتکل DSR، نیاز به نگهداری یک Route Cache جهت کش کردن مسیرهای منبع در آن میباشد. برای تحویل موفق پکت های دیتا از گره منبع به مقصد، گره منبع ابتدا Route Cache خود را بررسی می کند تا ببیند مقصد در آن قرار دارد یا خیر. در این شرایط، اگر مسیری پیدا شود، گره منبع از آن مسیر برای انتشار پکت های دیتا استفاده می کند و در غیر اینصورت، فرآیندی را برای پیدا کردن مسیر جدید، آغاز می کند. در شبکه ادهاک وایرلس، DSR به دو مکانیزم اصلی برای کشف و نگهداری مسیر، وابسته است.
۳-۱- کشف مسیر در DSR
DSR زمانی که گره منبع قصد ارسال یک پکت به گره مقصد را دارد، از دو نوع پیام RREQ و RREP برای انجام کشف مسیر استفاده میکند. به اینصورت که گره منبع ابتدا rout cache خود را بررسی می کند تا مشخص شود آیا اطلاعات مسیریابی مرتبط با آن مقصد وجود دارد یا خیر.
اگر اطلاعات مسیریابی یافت نشود، گره منبع با پخش یک پکت RREQ به تمام گره های همسایه واقع در محدوده انتقالش، یک پروسه کشف مسیر را آغاز میکند تا یک مسیر به صورت داینامیک کشف شود. گره های همسایه نیز ID خودشان را در پکت RREQ اضافی کرده و پکت را پخش می کنند. به اینصورت پکت Broadcast یا به گره مقصد می رسد یا به گره میانی که حاوی مسیری به گره مقصد باشد. در هر گره یک route cache نگهداری می شود و گره ها همواره قبل از پخش پکت RREQ، ابتدا cache خود را بررسی می کنند. با نگهداری route cache سربار حاصل از کشف مسیر، کاهش پیدا می کند.
اگر در cache گره مسیری قابل دسترس باشد، به جای پخش پکت RREQ، یک پکت RREP ارسال خواهد شد. اولین پکتی که به گره مقصد می رسد، اطلاعات کامل مربوط به مسیر را در خود دارد. در پروتکل DSR مسیر به دست آمده، کوتاه ترین مسیر در نظر گرفته شده است. پکت RREP که به گره منبع ارسال می شود، اطلاعات مسیر تا مقصد را در بر دارد. گره منبع باید این مسیر را در cache خود ذخیره کند.
زمانی که مسیری بین منبع و مقصد شکسته می شود، از پیام RREP برای اطلاع به گره منبع استفاده می شود تا گره منبع هر مسیری که از این لینک استفاده می کرده را از cache خود پاک کند و اگر هنوز نیاز به مسیری داشته باشد، مکانیزم کشف مسیر جدیدی را آغاز کند.
DSR به شیوه بهینه ای از Source Path و Path Catching استفاده می کند و برای پیدا کردن حلقه های مسیریابی، نیازی به مکانیزم خاصی ندارد.
۳-۲- نگهداری مسیر در DSR
DSR در مکانیزم نگهداری مسیر از دو نوع پکت RERR و ACK استفاده می کند. صحه گذاری بر وجود یک مسیر در DSR بر مبنای پکت ACK ای صورت می گیرد که از گره های همسایه دریافت می شود و بیانگر تحویل داده شدن پکت به hop بعدی می باشد. پکت ACK حاوی یک Passive Acknowledgement است.
علاوه بر این، زمانیکه یک گره، موفق به دریافت Ack نمی شود، یک پکت RERR تولید می شود و چنانچه مسیر پشتیبانی (Redundant Route) در دسترس نباشد، پکت RERR به منبع ارسال می شود تا دوباره فاز کشف مسیر را آغاز کند. زمانیکه گره ای پکت RERR دریافت می کند، کلیه رکوردهای مسیریابی که از این لینک شکسته استفاده کرده باشند را از Route Cache پاک می کند.
به علاوه، DSR برای کاهش سربار، از برپایی Flow State در گره های میانی پشتیبانی می کند. Flow State قابلیت فورواردینگ hop به hop با “مسیرهای مبتنی بر منبع” یکسان با مسیرهای تأمین شده توسط “مسیر منبع” اصلی، را میسر می سازد.
۳-۳- فلوچارت DSR
منبع: علوم نوین امیرکبیر
دوره آموزشی مرتبط با این موضوع
درباره مجید شبیری
کارشناس ارشد فناوری اطلاعات از دانشگاه صنعتی امیرکبیر. مدیر و مؤسس "علوم نوین امیرکبیر"، متخصص برنامه نویسی، شبکه، لینوکس و امنیت. از سال 84 همزمان با شروع تحصیلات دانشگاهی، وارد حوزه تخصصی مهندسی نرم افزار شدم و اکنون مشغول تحقیق، توسعه و آموزش در حوزه بلاک چین هستم و معتقدم بلاکچین به زودی فضای کسب و کارها را منقلب خواهد کرد.
نوشته های بیشتر از مجید شبیری
دیدگاهتان را بنویسید