پروتکل های مسیریابی

پروتکل های مسیریابی

امروزه علم کامپیوتر به حدی پیشرفت کرده که بسیاری از علوم دیگر پیشرفتشان وابسته به علم کامپیوتر می باشد.شبکه های کامپیوتری به حدی پیشرفت کرده اند که توانسته اند جهان را به یک دهکده علمی کوچک تبدیل نمایند.برای برقراری ارتباط بین این شبکه ها نیازمند به یک ستون فقرات می باشیم٬ این شبکه زیر بنایی که از تعداد زیادی مسیریاب تشکیل شده است وظیفه انتقال اطلاعات را دارد. بر روی این مسیریاب ها باید الگوریتم هایی اجرا شوند تا بتوانند بهترین مسیر را برای انتقال اطلاعات در این دهکده را انتخاب کنند.

1-5- مسیریابی

در شبکه‌های ادهاک، نودهای شبکه دانش قبلی از توپولوژی شبکه‌ای که درآن قرار دارند، ندارند به همین دلیل مجبورند برای ارتباط با سایر نودها، محل مقصد را در شبکه کشف کنند. در اینجا ایده اصلی این است که یک نود جدید به طور اختیاری حضورش را در سراسر شبکه منتشر می‌کند وبه همسایه‌هایش گوش می‌دهد. به این ترتیب نود تا حدی ازنودهای نزدیکش اطلاع بدست می‌آورد و راه رسیدن به آنها را یاد می‌گیرد به همین ترتیب که پیش رویم همه نودهای دیگر را می‌شناسد و حداقل یک راه برای رسیدن به آنها را می‌داند.

2-5- پروتکل‌های مسیریابی

پروتکل‌های مسیریابی بین هر دو نود این شبکه به دلیل اینکه هر نودی می‌تواند به طور تصادفی حرکت کند و حتی می‌تواند در زمانی از شبکه خارج شده باشد، مشکل می‌باشند. به این معنی یک مسیری که در یک زمان بهینه‌است ممکن است چند ثانیه بعد اصلا این مسیر وجود نداشته باشد. در زیر سه دسته از پروتکل‌های مسیر یابی که در این شبکه‌ها وجود دارد را معرفی می‌کنیم.

1. Table Driven Protocols: در این روش مسیریابی هرنودی اطلاعات مسیریابی را با ذخیره اطلاعات محلی سایر نودها در شبکه استفاده می‌کند و این اطلاعات سپس برای انتقال داده از طریق نودهای مختلف استفاده می‌شوند.
2. On Demand Protocols: روش ایجاب می‌کند مسیرهایی بین نودها تنها زمانی که برای مسیریابی بسته موردنیاز است تا جایی که ممکن است بروزرسانی روی مسیرهای درون شبکه ندارد به جای آن روی مسیرهایی که ایجاد شده و استفاده می‌شوند وقتی مسیری توسط یک نود منبع به مقصدی نیاز می‌شود که آن هیچ اطلاعات مسیریابی ندارد، آن فرآیند کشف مسیر را از یک نود شروع می‌کند تا به مقصد برسد. همچنین ممکن است یک نود میانی مسیری تا مقصد داشته باشد. این پروتکل‌ها زمانی موثرند که فرآیند کشف مسیر کمتر از انتقال داده تکرار شود زیرا ترافیک ایجاد شده توسط مرحله کشف مسیر در مقایسه با پهنای باند ارتباطی کمتر است.
3. Hybrid Protocols: ترکیبی از دو پروتکل بالاست. این پروتکل‌ها روش مسیریابی بردار-فاصله را برای پیدا کردن کوتاه‌ترین به کار می‌گیرند و اطلاعات مسیریابی را تنها وقتی تغییری در توپولوژی شبکه وجود دارد را گزارش می‌دهند. هر نودی در شبکه برای خودش یک zone مسیریابی دارد و رکورد اطلاعات مسیریابی در این zone ها نگهداری می‌شود. مثل ZRP (zone routing protocol ).
4. پرتکل بردار مسیر : مسیریابی حالت لینک و بردار فاصله پروتکل غالب می‌باشند. آنها از سیستم ناشناخته درونی استفاده می‌نمایند ولی بین سیستم‌های ناشناخته نمی‌باشند. این دو نوع پروتکل می‌توانند در شبکه‌های بزرگ مسیریابی شوند و به این طریق مسیریابی درون حوزه‌ای عملی خواهد شد. مسیریابی حالت لینک می‌تواند اطلاعات زیادی را وارد جدول کند، این عامل تشکیل ترافیک بزرگ می‌باشد. مسیریابی بردار برای درون حوزه‌ها استفاده می‌شود و مانند بردار راه دور است. در این جا یک گره در هر سیستم ناشناخته وجود دارد که به عنوان کل سیستم عمل خواهد کرد. این گره از نوع سخنگو است. این گره جدول مسیریابی را تولید کرده و به گره‌های همجوار می‌فرستد. در این شرایط فقط گره‌های سخنگو در هر سیستم با یکدیگر ارتباط برقرار می‌کنند. این گره می‌تواند در مسیر پیش رود و در سیستم ناشناخته فعال شود.

پروتکل‌های روش اول مسیریابی

1. DSDV: این پروتکل بر مبنای الگوریتم کلاسیک Bellman-Ford بنا شده‌است. در این حالت هر گره لیستی از تمام مقصدها و نیز تعداد پرش‌ها تا هر مقصد را تهیه می‌کند. هر مدخل لیست با یک عدد شماره گذاری شده‌است. برای کم کردن حجم ترافیک ناشی از بروز رسانی مسیرها در شبکه از incremental -packets استفاده می‌شود. تنها مزیت این پروتکل اجتناب از به وجود آمدن حلقه‌های مسیریابی در شبکه‌های شامل مسیریاب‌های متحرک است. بدین ترتیب اطلاعات مسیرها همواره بدون توجه به این که آیا گره در حال حاضر نیاز به استفاده از مسیر دارد یا نه فراهم هستند.
2. معایب: پروتکل DSDV نیازمند پارامترهایی از قبیل بازه زمانی بروزرسانی اطلاعات و تعداد بروزرسانی‌های مورد نیاز می‌باشد.
3. WRP: این پروتکل بر مبنای الگوریتم path-finding بنا شده با این استثنا که مشکل شمارش تا بینهایت این الگوریتم را برطرف کرده‌است. در این پروتکل هر گره، چهار جدول تهیه می‌کند: جدول فاصله، جدول مسیر یابی، جدول هزینه لینک و جدولی در مورد پیام‌هایی که باید دوباره ارسال شوند. تغییرات ایجاد شده در لینک‌ها از طریق ارسال و دریافت پیام میان گره‌های همسایه اطلاع داده می‌شوند.
4. CSGR: در این نوع پروتکل گره‌ها به دسته‌ها تقسیم بندی می‌شوند. هر گروه یک سر گروه دارد که می‌تواند گروهی از میزبان‌ها را کنترل و مدیریت کند. از جمله قابلیت‌هایی که عمل دسته بندی فراهم می‌کند می‌توان به اختصاص پهنای باند و دسترسی به کانال اشاره کرد. این پروتکل از DSDV به عنوان پروتکل مسیریابی زیر بنایی خود استفاده می‌کند. نیز در این نوع هر گره دو جدول یکی جدول مسیریابی و دیگری جدول مریوط به عضویت در گره‌های مختلف را فراهم می‌کند.
5. معایب: گره‌ای که سر واقع شده سربار محاسباتی زیادی نسبت به بقیه دارد و به دلیل اینکه بیشتر اطلاعات از طریق این سرگروه‌ها برآورده می‌شوند در صورتی که یکی از گره‌های سرگروه دچار مشکل شود کل و یا بخشی از شبکه آسیب می‌بیند.
6. STAR: این پروتکل نیاز به بروز رسانی متداوم مسیرها نداشته و هیچ تلاشی برای یافتن مسیر بهینه بین گره‌ها نمی‌کند.

پروتکل‌های روش دوم مسیریابی

1. SSR: این پروتکل مسیرها را بر مبنای قدرت و توان سیگنال‌ها بین گره‌ها انتخاب می‌کند. بنابراین مسیرهایی که انتخاب می‌شوند نسبتا قوی تر هستند. می‌توان این پروتکل را به دو بخش DRP و SRP تقسیم کرد. DRP مسئول تهیه و نگهداری جدول مسیریابی و جدول مربوط به توان سیگنال‌ها می‌باشد.SRP نیز بسته‌های رسیده را بررسی می‌کند تا در صورتی که آدرس گره مربوط به خود را داشته باشد آن را به لایه‌های بالاتر بفرستد.
2. DSR: در این نوع، گره‌های موبایل بایستی حافظه‌هایی موقت برای مسیرهایی که از وجود آنها مطلع هستند فراهم کنند. دو فاز اصلی برای این پروتکل در نظر گرفته شده‌است:کشف مسیر و بروز رسانی مسیر. فاز کشف مسیر از route request/reply packet ها و فاز بروز رسانی مسیر از تصدیق‌ها و اشتباهای لینکی استفاده می‌کند.
3. TORA: بر اساس الگوریتم مسیریابی توزیع شده بنا شده و برای شبکه‌های موبایل بسیار پویا طراحی شده‌است. این الگوریتم برای هر جفت از گره‌ها چندین مسیر تعیین می‌کند و نیازمند کلاک سنکرون می‌باشد. سه عمل اصلی این پروتکل عبارتند از: ایجاد مسیر. بروز رسانی مسیر و از بین بردن مسیر.
4. AODV: بر مبنای الگوریتم DSDV بنا شده با این تفاوت که به دلیل مسیریابی تنها در زمان نیاز میزان انتشار را کاهش می‌دهد. الگوریتم کشف مسیر تنها زمانی آغاز به کار می‌کند که مسیری بین دو گره وجود نداشته باشد.
5. RDMAR: این نوع از پروتکل فاصلۀ بین دو گره را از طریق حلقه‌های رادیویی و الگوریتم‌های فاصله یابی محاسبه می‌کند. این پروتکل محدوده جستجوی مسیر را مقدار مشخص و محدودی تایین می‌کند تا بدین وسیله از ترافیک ناشی از سیل آسا در شبکه کاسته باشد. تقسیم بندی های مختلفی در مورد پروتوکل های مسیر یابی شبکه های Mobile ad hoc وجود دارد که از این میان می توان به ۲ نوع زیر اشاره کرد:

تقسیم بندی اول :

1. Pro active (Table driven)
2. Reactive (On demand)
3. Hybrid (Table driven & On demand)

هر کدام از این انواع خود شامل پروتوکل هایی هستند که در جدول زیر به چند مورد اشاره شده است:

تقسیم بندی دوم:

1. Flat routing protocols
2. Hierarchal routing approaches
3. GPS Augmented geographical routing approaches

در اینجا به توضیحاتی در مورد پروتوکل های تقسیم بندی اول می پردازیم:

: Table driven pro active در پروتوکلهای از این نوعnode ها مدام در حال جستجوی اطلاعات مسیر یابی جدید درون شبکه هستند به صورتی که حتی با تغییر مکان node ها در صورت نیاز به راحتی می توان مسیر مناسبی را یافته و برای ارسال و دریافت اطلاعات بین هر دو node ی استفاده کرد. به عبارت بهتر می توان گفت که در این شبکه ها مسیر ها از قبل موجود هستند.و به محض آنکه node ی اقدام به ارسال داده به node دیگری کند قادر خواهد بود مسیر موجود را از روی اطلاعات از قبل جمع آوری شده شناسایی کرده و مورد استفاده قرار دهد و لذا تاخیری در این مورد متوجه node نیست.

DSDV   : این پروتوکل بر مبنای الگوریتم کلاسیک Bellman-Ford بنا شده است.در این حالت هر node لیستی از تمام مقصد هاو نیز تعداد hop ها تا هر مقصد را تهیه می کند.هر مدخل لیست با یک عدد شماره گزاری شده است. برای کم کردن حجم ترافیک ناشی از به روز رسانی مسیر ها در شبکه از incremental packets  استفاده می شود.تنها مزیت این پروتوکل اجتناب از به وجود آمدن حلقه های مسیر یابی در شبکه های شامل مسیر یاب های متحرک است.بدین ترتیب اطلاعات مسیر ها همواره بدون توجه به این که آیا node در حال حاضر نیاز به استفاده از مسیر دارد یا نه فراهم هستند.

معایب : پروتوکل DSDV نیازمند پارامترهایی از قبیل بازه ی زمانی به روز رسانی اطلاعات و تعداد به روز رسانی های مورد نیاز می باشد.

: WRP این پروتوکل بر مبنای الگوریتم path-finding بنا شده با این استثنا که مشکل count-to-infinity این الگوریتم را برطرف کرده است. در این پروتوکل هر node , ۴ جدول تهیه می کند:

1. جدول فاصله
2. جدول مسیر یابی
3. جدول link-cost
4. جدولی در مورد پیامهایی که باید دوباره ارسال شوند.

تغییرات ایجاد شده در لینکها از طریق ارسال و دریافت پیام میان node های همسایه اطلاع داده می شوند.

: CSGR در این نوع پروتوکل node ها به دسته ها یا cluster هایی تقسیم بندی می شوند. هر گروه یک cluster head دارد که می تواند گروهی از host ها را کنترل و مدیریت کند.از جمله قابلیت هایی که عمل  clustering  فراهم می کند می توان به اختصاص پهنای باندو channel access اشاره کرد.این پروتوکل از DSDV  به عنوان پروتوکل مسیریابیی زیر بنایی خود استفاده می کند . نیز در این نوع هر node دو جدول یکی جدول مسیریابیی و دیگری جدول مریوط به عضویت در node های مختلف را فراهم می کند.

معایب : node ی که head واقع شده سربار محاسباتی زیادی نسبت به بقیه داردو به دلیل اینکه بیشتر اطلاعات از طریق این head ها برآورده می شونددر صورتی که یکی از node های head دچار مشکل شود کل و یا بخشی از شبکه آسیب می بیند.

: STAR این پروتوکل نیاز به به روز رسانی متداوم مسیر ها نداشته و هیچ تلاشی برای یافتن مسیر بهینه بین node ها نمی کند.

:On demand Reactiveدر این نوع پروتوکل مسیر ها تنها زمانی کشف می شوند که مبدا اقدام به برقراری ارتباط با node دیگری کند.زمانی که یک node بخواهد با node دیگری ارتباط برقرار کند بایستی فرایند کشف مسیر ( Route Discovery Process ) را در شبکه فراخوانی کند.در این حالت قبل از بر قرار شدن ارتباط , تاخیر قابل توجهی مشاهده می شود.

: SSR این پروتوکل مسیرها را بر مبنای قدرت و توان سیگنالها بین node ها انتخاب می کند. بنابراین مسیرهایی که انتخاب می شوندد نسبتا قوی تر هستند . می توان این پروتوکل را به ۲ بخش DRP) Dynamic Routing Protocol)  و SRP ( Static Routing Protocol) تقسیم کرد .

DRP: مسئول تهیه و نگهداری جدول مسیریابی و جدول مربوط به توان سیگنال ها می باشد.

SRP: نیز packet های رسیده را بررسی می کند تا در صورتی که آدرس node مربوط به خود را داشته باشد آن را به لایه های بالاتر بفرستد و در غیر این صورت به شبکه.

: DSR در این نوع node های موبایل بایستی cache هایی برای مسیر هایی که از وجود آنها مطلع هستند فراهم کنند.دو فاز اصلی برای این پروتوکل در نظر گرفته شده است کشف مسیر و به روز رسانی مسیر. فاز کشف مسیر از route request/reply packet ها و فاز به روز رسانی مسیر از acknowledgement ها و error های لینکی استفاده می کند.

: TORA بر اساس الگوریتم مسیر یابی توزیع شده بنا شده و برای شبکه های mobile بسیار پویا طراحی شده است.این الگوریتم برای هر جفت از node ها چندین مسیر تعیین می کند و نیازمند clock سنکرون می باشد. ۳ عمل اصلی این پروتوکل عبارتند از :ایجاد مسیر. به روز رسانی مسیر و از بین بردن مسیر.

: AODV بر مبنای الگوریتم DSDV بنا شده با این تفاوت که به دلیل مسیریابی تنها در زمان نیاز میزان Broad casting را کاهش می دهد.الگوریتم کشف مسیر تنها زمانی آغاز به کار می کند که مسیری بین ۲ node وجود نداشته باشد .

: RDMAR این نوع از پروتوکل فاصله ی بین ۲ node را از طریق حلقه های رادیویی و الگوریتم های فاصله یابی محاسبه می کند. این پروتوکل محدوده ی جستجوی مسیر را مقدار مشخص و محدودی تایین می کند تا بدین وسیله از ترافیک ناشی از flooding در شبکه کاسته باشد.

Hybrid (Pro-active / Reactive): این مورد با ترکیب دو روش قبلی سعی در کاهش معایب کرده و از ویژگی های خوب هر دو مورد بهره می برد. این پروتوکل جدید ترین کلاس پروتوکل ها در این راستا می باشد. معروفترین پروتوکل از این نوع می توان به ZRP( Zone Routing protocol)  اشاره کرد.این پروتوکل از ویژگی های نوع Pro active برای مسیریابی node های نزدیک به هم و از ویژگی های نوع Reactive برای مسیر یابی node های دورتر استفاده می کند.

: ZRPنوعی از clustering است با این تفاوت که در این پروتوکل هر Node خود head بوده و به عنوان عضوی از بقیه ی cluster ها می باشد. به دلیل hybrid بودن کارایی بهتری دارد.

شاید بتوان شبکه های ad hoc را آسب پذیر ترین شبکه ها از لحاظ امنیتی و ضعیفترین در مقابل حملات نفوذگران دانست. به همین دلیل برخورد با این مسئله و رفع مشکلات مربوطه از مهمترین دغدغه های شخصی است که اقدام به را ه اندازی چنین شبکه ای می کند.از جمله مواردی که منجر به نا امن شدن این شبکه ها شده است می توان به موارد زیر اشاره کرد:

ـ کانال رادیویی از نوع broad cast به اشتراک گزارده شده.

1. محیط عملیاتی نا امن
2. نبود شناسایی (authentication) متمرکز.
3. دسترسی محدود به منابع
4. مشکلات و آسیت پزیری های فیزیکی.

زمانی که در مورد امنیت شبکه بحث می شود معمولا به عناوین چندی توجه می شود:

: Availability بدین معنی که شبکه در تمام زمان ها حتی در مواردی که دچار حمله شده بتواند به عمل خود ادامه بدهد.

: Confidentiality اطمینان از اینکه اطلاعات مشخص و معینی در اختیار کاربران خاصی قرار نگیرد.

: Authentication توانایی یک node در شناسایی و تشخیص node ی که با وی در ارتباط است.

: Integrity تضمین اینکه یک پیام پس از منتشر شدن تخریب نشده و از بین نمی رود.

: Non-repudiation فرستنده ی پیام نتواند ارسال خود را انکار کنند.

یک شبکه ی ad hoc به دلیل نداشتن ساختار ثابت و مشخص و نیز ارتباطات پویا بین node ها نیازمند ملاحظات امنیتی بیشتری نسبت به انواع دیگر شبکه است.

همان طور که قبلا نیز بیا ن شد در این شبکه ها هر node ی هم مسیر یاب است و هم end – system . بدین ترتیب node ها از هم متمایز نیستند و به این دلیل نیاز به یک پروتوکل مسیر بایی امن حس می شود. که در این راستا معمولا پروتکل های multi hop بث کار گرفته می شوند.

3-5- معنای حمل

این طرح‌ها بسته به معنای خود متفاوت هستند.

• حمل Unicast برای یک پیام به حالت ویژه
• بخش عامل حمل پیام به تمام گره‌های شبکه
• حمل multicast برای یک گروه گره که در دریافت پیام نقش دارند.
• حمل anycast برای ارسال به هر گروه و به خصوص نزدیکترین منبع. Unicast حالت غالب حمل پیام است و این جا بر آلگوریتم unicastتاکید داریم.

4-5- توزیع توپولوژی

شبکه‌های کوچک دارای جداول دستی هستند. شبکه‌های بزرگ توپولوژی پیچیده دارند. و به سرعت تغییر می‌کنند. به این طریق ساختار جداول غیرقابل طراحی خواهد شد. بیشتر این شبکه‌های تلفنی کلیدی (pstn) از این جداول استفاده می‌کنند و نقایص در مسیر این سیستم شناخته و رفع خواهند شد. مسیر یابی دینامیکی تلاشی برای حل مسئله و تشکیل ساختار خودکار جداول است. این براساس اطلاعات پروتکل مسیریابی عملی است. به این طریق شبکه‌ها از هر نقص ایمن خواهند شد. این دینامیک در اینترنت نقش فعال دارد. طراحی پروتکل‌ها به یک تماس ماهرانه نیاز دارد. نباید فرض کرد که شبکه سازی به نقطه اتوماسیون کامل رسیده‌است.