الگوریتمهای مسیریابی

مقدمه الگوریتمهای مسیریابی

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

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

-

الگوریتمهای مسیر یابی

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

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

پایداری نیز برای الگوریتم مسیر یابی هدف مهمی است. الگوریتم‌های مسیر یابی وجود دارند که هرگز وجود دارندکه هرگز به حالت پایداری نمی‌رسند.مدت زمان اجرای آن بی تاثیر است عدالت وبهینگی مممکن است ساده به نظر می‌رسند یقیینا  کسی با آن مخالف نیست. اماهمان طور که روشن است اهداف متناقضی دارند به عنوان مثال از این تناقض ، شکل 1 را بینید. فرض کنید ترافیک کافی بین A و ش، بین B,B وبین C, C  وجود دارد تا پیوندهای افقی را اشباع نماید برای بیشینه کردن کل جریان ترافیک  X, X باید کاملا از بین برود. متاسفانه از نظر X وX عادلانه نیست بدیهی است که توافقی  بین کارایی کلی و عدالت اتصال‌های منفرد لازم است.

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

الگوریتم‌های مسیر یابی  به می‌توانند به دو دسته تقسیم شوند غیر وفقی و وفقی  الگوریتم‌های غیر وفقی تصمیات مسیر یابی خود را بر اندازه گیری یا تخمین  توپولوژی و ترافیک فعلی بنا نمی‌نهند بلکه برای انتخاب مسری جهت رسیدن از I  به J برای تمام I  را به تمام J از قبل  محاسبه می‌شود در حالت OFF-LINE و هنگام راه اندازی شبکه به مسیر یاب‌ها بار می‌شود این روند گاهی مسیر یابی ایستا نام دارد.

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

اصل بهینگی

قبل از پرداختن به الگوریتم  توجه به مهم است که صرف نظر از توپولوژی شبکه  وتر افیکی ، می‌توان حکمی کلی راجع به مسیرهای بهینه ارائه کرد این حکم را به عنوان اصل بهینگی  شناخته می‌شود. این اصل بیا می‌کند که اگر مسیریابJ از مسیریاب I به مسیریابK در مسیریاب بهینه‌ای شناخته می‌کند آنگاه مسر بهینه‌ای از J و K نیز در مسیر مشابهی  قرار می‌گیرد. برای مشاهده این موضوع ، بخشی  از مسیر I به J  را به بنامید و بقیه را نامگذاری کنید اگر مسیری بهتر از وجود داشت می‌توانست با الحاق  شود تا مسیری از I به K  بهبود بخشد، و حکم ما را می‌گوید ?  بهینه است نقض کند.

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

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

مسیر یابی کوتاه ترین مسیر

مطالعه الگوریتمهای  مسیر یابی را با تکنیکی که به طور گسترده به شکل‌های مختلفی به کار می‌رود شروع می‌کنیم، زیرا الگوریتم ساده‌ای است ودرک آن آسان است. ایده ، ساختن گرافی از زیر شبکه است ، به طوری که ، هر گره گراف نشان دهنده مسیریاب است و هریال نشان دهنده خط ارتباطی است ( که اغلب پیوند نام دارد.) برای انتخاب  مسیری بین دو مسیریابمعین ، الگوریتم ، کوتاهترین مسیر بین آنها را درگراف می‌یابد.

در مورد کوتاهترین مسیر توضیحاتی باید ارائه شود . یک راه اندازه گیری طول مسیر ، تعداد جهش است با این معیار ، طول مسیرهای ABC,ABE در شکل 3 یکسان است.و معیار دیگر معیار دیگر فاصله جغرافیایی به کیلومتراست ، در این حالت بدیهی است که ABC خیلی طولانی تر از ABE است با فرض این که شکل با مقیاس رسم شده است.

علاوه بر جهش‌ها و فاصله فیزیکی معیارهای دیگری نیز قابل  استفاده‌اند به عنوان مثال هریال می‌تواند به میانگین تاخیر صف بندی و انتقال برای بعضی از بسته‌های آزمایشی  برچسب گذاری شود. با این برچسب گذاری، کوتاهترین مسیر به جای مسیری به جای مسیری که با کمترین یال یا فاصله  سریع تر مسیر است.

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

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

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

اکنون از B شروع می‌کنیم و تمام گره هایی همجوار آن را مورد بررسی قرار می‌دهیم. اگر مجموع برچسب در B و فاصله B تا گره‌ای که باید در نظر گرفته شود کمتر از برچسب موجود در ان گره باشد کوتاهترین مسیر پیدا شده ، این گره مجددا برچسب گذاری می‌شود.

پس از این تمام کره‌ها همجوار گره کاری بررسی شدند و گره‌های موقتی تغییر کردند ، کل گراف مورد جست وجو قرار می‌گیرد تا گره‌ای موقتی با کمترین مقدار برچسب گذاری می‌شود

برای پی بردن به عملکرد الگوریتم شکل 3 ج را ببیند  در این شکل، E دائمی است فرض کنید مسیر AXYZA کوتاهتر از ABE باشد دو امکان وجود دارد: یا گره Z به عنوان گره دائمی منظور شده است یا نشده است اگر دائمی باشد E تاکنون بررسی شده است در سیکلی بعد از ان که Z دائمی شد. لذا AXYZE از دید ما خارج  نبوده است و نمی‌تواند  مسیر کوتاهتری باشد

اکنون حالتی را در نظر بگیرید که هنوز بر چسب Z موقتی باشد.برچسب موجود در Z بزرگتر یا مساوری برچسب در E است که در این حالت XYZE نسبت به ABC مسیر کوتاهتری نیست، یا کمتر از E است که در این حالت Z وE تاکنون بررسی مورد جستجو قرار می‌گیرد.

این الگوریتم در شکل 4 آمده است متغیرهایی عمومی N و DIST گراف را توصیف می‌کنند و قبل از فراخوانی SHORTEST PATH مقدار می‌گیرند . تنها بین برنامه والگوریتمی که تشریح شد این است که کوتاهترین مانند کوتاهترین مسیر از Sبه T محاسبه شده است .چون کوتاهترین مسیر از T به S در گراف  بدون جهت است مهم نیست که از کدام طرف شروع کنیم مکر اینکه کوتاهترین مسیر متعددی  وجود داشته باشد که در آن حالت جست و جستجوی معکوس مسیر دیگری را انتخاب می‌نماید. دلیل جستجوی معکوس این است که هرگره با گره قبلی خود (به جای گره بعدی) برچسب گذاری می‌شود. هنگام کپی کردن مسیر نهایی در متغیر خروجی PATH مسیر، معکوس می‌شود با معکوس کردن جستجو این دو اثر خنثی می‌شود. پاسخ به ترتیب درستی تولید می‌گردد.

الگوریتم غرق کردن

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

تکنیک دیگر برای محدود کردن الگوریتم غرق کردن این است که بسته هایی که تاکنون ارسال شده‌اند مشخص باشند، تا مجددا ارسال نگردند یک روش انجام این کار این است که مسیریابمنبع ، در بسته هایی که از میزبانهایش دریافت می‌کند شماره ترتیبی را قرار دهد در این صورت هر مسیریاببه ازای هر مسیریابمنبع به لیستی نیاز دارد تا مشخث کند کدام شماره ترتیب هایی که تاکنون از منبع ارسال شدند دریافت گردیدند. اگر بسته ورودی در آن لیست موجود باشد: ارسال نشده است.

برای جلوگیری از رشد بی رویه لیست، هر لیست باید دارای شمارنده‌ای به نام K باشد،معنایش این است که تمام شماره ترتیب‌ها از 1 تا K مشاهده شده‌اند وقتی بسته‌ای دریافت می‌شود، به راحتی می‌توان تشخیص داد که این آیا تکراری است یا خیر اگر تکراری باشد، از آن صرف نظر می‌گردد. علاوه بر این ،به لیست کامل کمتر ازK نیازی نیست،زیرا K آن را خلاصه می‌کند.

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

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

مسیر یابی بردار فاصله

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

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

الگوریتم مسیر یابی  بردار فاصله به اسامی دیگر نیز خوانده می‌شود. ازجمله الگوریتم مسیر یابی بلمن –فورد و الگوریتم و الگوریتم فورد – فورکرسون که نامگذاری آنها را نام مخترعین آنها بلمن 1975- فورد و فوکرسون، 1962 اقتباس شده است. این الگوریتم مسیر یابی ARPANET اولیه بود و تحت نام RIP در اینترنت مورد استفاده قرارگرفت.

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

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

به عنوان  مثال ، فرض کنید تاخیر به عنوان مقیاس به کار می‌رود و مسیریاب، تاخیر  به هر همسایه خودش را می‌داند . هر مسیریابدر هر T میلی ثانیه لیستی  از تاخیرهای تخمینی خود را به هر مقصد را ارسال می‌کند ولیست مشابهی از هر همسایه خود دریافت می‌کند فرض کنید  یکی از این جدول‌ها از همسایه‌ها X می‌رسد، به طوری که X زمان رسیدن به مسیریاب I باشد که X آن را تخمین  زده است اگر مسیریاببداند تاخیر تا X برابر با M میلی ثانیه باشد، می‌داند که اگر بخواهد  از طریق X به مسیریابI برسدX+M میلی ثانیه  طول می‌کشد. با انجام این محاسبات  برای هر همسایه‌های مسیریابمی‌تواند بهترین تخمین را تشخیص دهد و می‌تواند از این تخمین و خط متناظر در جدول مسیر یابی جدید استفاده نماید توجه داشته باشیدو که جدول مسیر یابی قبلی، در محاسبه  به کار نمی‌آید.

این فرآیند  بازسازی در شکل 5 آمده است بخش الف زیر شبکه‌ای را نشان می‌دهد چهار ستون اول بخش (ب) بردارهایی تاخیری  را که از همسایه هایی مسیریابJ آمده‌اند نشان می‌دهد تاخیر از A به B برابر با 12 میلی ثانیه و از A به C برابر با 25 میلی ثانیه و از A به D برابر 40 میلی ثانیه و غیره  است فرض کنید تاخیرهایی J به همسایه هایش A,H,I,A به ترتیب عبارتست از 8و10و12و6 میلی ثانیه .

چگونگی محاسبه مسیر جدید از J به G را در نظر بگیرید J می‌داند که می‌تواند با 8 میلی ثانیه تاخیر به A برسد و A با 18 میلی ثانیه به G می‌رسد لذا J می‌داندکه اگر بخواهد از طریق A به  G برسد 26 میلی ثانیه طول می‌کشد. به طور مشابه به تاخیر رسیدن به J را در جدول ،18 میلی ثانیه ثبت می‌کند و آن، از طریق H است محاسبه مشابهی برای تمام مقصدها صورت میگیرد به طوری که جدول مسیر یابی  جدید را به صورت آخرین به صورت اخرین ستون شکل در می‌آید.

مسئله بی نهایت گرایی

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

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

 وقتی A را به کار می‌افتد . سایر مسیر یاب‌ها از طریق مبادله بردار ، آگاه مس شوند برای سهولت فرض کنیم زنگ بزرگی وجود دارد که برای شروع همزمان مبادله بردار در تمام مسیر یاب‌ها به صدا در می‌آید در زمان مبادله نخست B می‌فهمد که همسایه چپ آن تا A آن را تاخیری ندارد صفراست سپس B در جدول مسیر یابی خود ثبت می‌کند که A تا همسایه چپ ، یک جهش فاصله دارد سایر مسیر یاب‌ها فکر می‌کنند  که A هنوز از کار افتاده است در این لحظه وارده هایی جدول مسیر یابی A در سطر  دوم شکل 6 برابر است الف لذا جدول مسیر یابی را بازسازی  می‌کند تا مسیری به طول 2 را نشان دهد اما D و E تاکنون خبرهای جدید را نشنیده اندن بدیهی است که خبرهای جدید با سرعت یک جهش درهر مبادله بخش می‌شود در زیرشبکه‌های که طولانی ترین مسیر که ان به طول N جهش است. در N مبادله هرکسی از خطوط از خطوط و مسیریاب هایی که تازه فعال شده‌اند باخبر می‌شود.

اکنون وضعیت شکل 6 (ب) را در نظر می‌گیریم در این شکل تمام خطوط و مسیریاب‌ها در آغاز فعال‌اند وفاصله  مسیر یاب‌های Aتا, E,D,C,B به ترتیب عبارتند از 1و2.3و4 ناگهان A  از کار می‌افتد یا خط بین A, B قطع می‌شود از دید B فرقی نمی‌کند که کدامیک اتفاق افتاده است.

در مبادله اولین بسته، B  چیزی از A نمی‌شنود خوشبختانه C می‌گوید نگران نباشید من مسیری به طول 2 به A دارم لذا B می‌داندکه مسیر C از طریق خود B می‌داند که C ممکن است ده خط خروجی داشته باشد .که هر کدام دارای مسیرهای مستقلی به A هستند که طول آنها 2 است در نتیجه B فکر می‌کند که می‌تواند از طریق C به A برسد با مسیرهای به طول 3 در مبادله اول E,D وارده‌های خود را برای A را بازسازی میکنند.

در مبادله دوم C در می‌یابدکه هریک از همسایه هایش ادعا میکنند که طول مسیر انها را به A برابر با 3 است یکی از آنها به طور تصادفی انتخاب می‌کندو فاصله جدید به A را برابر با 4 منظور می‌کند سطر سوم از شکل 6 الف مبادله‌های بعدی نتایج بقیه شکل 6 الف را تولید میکنند.

از این شکل پیدا است که چرا خبرهای بد کندی ارسال می‌شوند : هیچ مسیر یابی مقداری بیش از کمترین مقدار تمام همسایه هایش را ندارد گاهی تمام مسیر یاب‌ها بی نهایت بار کار می‌کنند.به همین دلیل ، عاقلانه است که بی نهایت را برابر با طولانی ترین مسیر به علاوه 1 قرار داد اگر مقیاس تاخیر زمان باشدو حد بالایی تعریف شده‌ای وجود ندارد لذا برای با طولانی ترین مسیر با تاخیر طولانی مثل مسیر از کار افتاده رفتار نشود وجود نداردلذا برای اینکه با مسیری با تاخیر طولانی، مثل مسیر از کار افتاده نشود ،نیاز به حد بالایی است لذا این مسئله بی نهایت گرایی نام دارد تلاش زیادی برای حل آن انجام شد ، ولی هیچ کدام موفق نبوده اند. مسئله مهم این است که وقتی X به Y می‌گوید مسیری در اختیار دارد،Y نمی‌تواند بفهمد که آیا خودش در آن مسیر قراردارد یا خیر .

مسیر یابی حالت پیوند

مسیر یابی فاصله تا سال 1979 در ARPANET مورد استفاده قرار گرفت و از ان پس جای  خود را به مسیر یابی حالت پیوند داد. و مشکل عمده موجب مرگ آن شد. یکی از این که مقیاس تاخیر، طول صف بود و هنگام انتخاب مسیریاب‌ها پهنای باند را در نظر نمی‌گرفت در آغاز تمام خطها 56KBPS بودند لذا پهنای باند موضوع مهمی نبود اما وقتی بعضی از خطوط به 235KBPS وبعضی دیگر به MBPS 55/1 تغییر یافتند عدم توجه به پهنای باند را به عنوان مقیاس در نظر گرفت اما مشکل  دوم نیز وجود داشت، یعنی الگوریتم برای همگرا شدن به زمان زیادی نیاز دارد . بی نهایت گرایی به این دلایل الگوریتم دیگری به نام مسیریابی حالت پیوند جای ان را گرفت اکنون شکلهای گوناگونی از مسیر یابی حالت پیوند مورد استفاده قرار میگیرد.

ایده مسیر یابی حالت پیوند ساده است ودر پنج بخش بیان می‌شود هر مسیریابباید:

1-همسایه هایش را تشخیص داده و آدرس شکبه‌ها آنها را بداند.

2-تاخیر با هزینه تا همسایه هایش را اندازه گیری کند.

3- ایجاد بسته‌ای که اطلاعات به دست آمده از همسایه‌ها را نگهداری کند.

4-این بسته‌ها را به تمام مسیریاب‌ها ارسال نماید.

5-کوتاهترین مسیر به هر مسیر دیگر را محاسبه کند.

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

کسب اطلاعاتی راجع به همسایه‌ها

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

وقتی دو یا چند مسیریاببا شبکه‌های محلی را به هم متصل باشند. وضعیت کمی پیچیده تر است. شکل 7 الف شبکه محلی را با سه مسیریابA,C,F نشان می‌دهد که مستقیما به آن متصل‌اند هرکدام از این مسیریاب‌ها به یک یا چند مسیریاب دیگر متصل شده‌اند .

یک روش مدل سازی شبکه محلی این است که به عنوان یک گروه در نظر گرفته شود شکل( 7 ب )در اینجا گره جدید و مصنوعی  به نام N را معرفی می‌کردیم . که F,C,A به آن متصل ‌اند امکان  رفتن از A به C در شبکه محلی ، با مسیر ANC مشخص شده است.

اندازه گیری هزینه خط

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

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

هر دو روش بحث هایی را می‌طلبد معنای به حساب آوردن تاخیرهای مربوط به ترافیک ، این است که وقتی مسیریاب دو خط با پهنای باند مساوی را در پیش روا داشته باشد، به طوری که یکی از آنها  همواره تحت بار سنگین قراردارد و دیگری این این طور نباشد مسیر مربوط به خط فاقد بار را به عنوان مسیر کوتاهتر در نظر می‌گیرد. این روش کارایی بهتری دارد متاسفانه با در نظر گرفتن بار در محاسبات تاخیر مخالفت هایی صورت گرفت زیر شبکه شکل 8 را در نظر بگیرید که به دو بخش شرقی و غربی تقسیم  شده است و توسط دو خط CF-, EI به هم متصل  شده‌اند فرض کنید بیشترین ترافیک بین شرق  غرب از خط ترافیک شرقی – غربی از طریق EI منتقل می‌شودو بار ان افزون می‌گردد. در نتیجه در بازسازی بعدی، CF کوتاهترین مسیر خواهد بود. لذا امکان دارد جدول‌های مسیر یابی شدیدا تغییر می‌کنندو منجر به مسیر یابی غیر عادی و بسیاری از مشکلات  دیگر شوند. اگر از بار صرف نظر شودو فقط پنهای باند منظور گردد، این مشکل نمی‌آید از طرف دیگر بار می‌تواند در هر دو خط پخش شود. اما این راه حل ، بهترین مسیر را مورد استفاده قرار نمی‌دهد با این وجود برای اجتناب از برخورد در انتخاب بهترین  مسیر، معقول است که بار در چندین خط توزیع شود.

ساخت  بسته‌های حالت پیوند

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

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

توزیع بسته‌های حالت پیوند.

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

ابتدا، الگوریتم توزیع اولیه رامورد بحث قرار می‌دهیم. سپس  اصلاحاتی را انجام دهیم ایده اصلی ، استفاده از الگوریتم غرق کردن برای توزیع بسته‌های حالت پیوند است برای کترل غرق کردن هر بسته حاوی شماره ترتیبی است که با ارسال هر بسته، یک واحد افزایش می‌یابد.وقتی بسته حالت پیوند دیگری دریافت می‌شود ،با لیستی از بسته‌ها که تاکنون دیده  شده‌اند مقایسه  می‌شود اگر بسته‌ای دریافت شود. به هر خطی به جز خطی که از ان آمده است، توزیع می‌گردد.و اگر تکراری باشد،صرف نظر می‌شوداگر بسته‌ای دریافت شود که شماره ترتیب آن کوچک تر از بالاترین شماره‌ای باشد که تاکنون مشاهده شده است به دلیل کهنه بودن رد می‌شود. زیر مسیریابداده‌ها جدیدی دارد.این الگوریتم دارای مشکلات خاصی است اما این مشکلات قابل کنترل‌اند یکی این که اگر شماره‌ها تمام شدند، بسته هایی بعدی از اول شماره گذاری شوند راه حل این مشکل، استفاده از شماره ترتیب 32 بیتی 32 بیتی است اگر در هر دقیقه یک بسته  حالت پیوند ایجاد شود.137سال  طول می‌کشد تا چرخش صورت می‌گیرد. لذا از این حالت می‌توان صرف نظر کرد.

دوم اینکه اگر مسیریاباز کار افتد و شماره ترتیب خود را از دست می‌دهد. اگر مجدداً از صفر شروع کند، بسته بعدی به عنوان بسته تکراری رد خواهد شد.

سوم اینکه  اگر شماره ترتیب خراب شود و 540،65 به جای 4(خطای یک بیتی ) دریافت شود ، بسته‌های 5 تا 540،65 به علت کهنگی رد می‌شوند زیرا فرض می‌شود که شماره ترتیب باید 540،65 باشد.

راه حل این مشکلات این است که سن هر بسته بعد از شماره ترتیب قرار داده می‌شود و هر ثانیه یک واحد از آن کسر گردد . وقتی که سن به صفر رسید. از اطلاعات حاصل از آن مسیریاب صرف نظر می‌شود. فرض کنید در هر 10دقیقه  بسته جدیدی می‌رسد. لذا مهلت اطلاعات مسیریاب وقتی تمام می‌شود که مسیریاب غیر فعال شود یاشش بسته متوالی از بین رفته باشد، البته این حالت رویداید نامحتملی است هرمسیریاب در فرآیند غرق کردن اولیه، از فیلد سن یک واحد می‌کاهد لذا اطمینان  حاصل می‌شود که هیچ بسته‌ای نمی‌تواند از بین برود و یا مدت زمان زیادی  زنده بماند (بسته‌ای که سن آن به صفر باشد. نادیده گرفته می‌شود.)

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

ساختمان داده‌ای که مسیریابB برای زیر شبکه شکل 13-5 الف استفاده می‌کند در شکل 10 آمده است هر سطر ، متناظر با بسته حالت پیوندی است که از راهع رسید و هنوز به طور کامل پردازش نشده است. جایی که بسته از انجا ارسال شد و شماره ترتیب وسن ، داده‌های ان درجدول ذخیره می‌شود به علاوه نشانگرهای ارسالی و اعلام وصول برای هر سه خط B وجود دارند به ترتیب به  F,C,A معنای نشانگرهای ارسالی این است که بسته باید به خط تعیین شده ارسال گرددو معنای نشانگرهای اعلام وصول این است که باید در آنجااعلام وصول شوند.

در شکل 10 بسته حالت پیوند مستقیما از A رسیده است. لذا همانطور که با بیت‌های نشانگر نشان داده شده است باید به  C, F ارسال شود. و به A اعلام  وصول گردد. به طور مشابه بسته‌ای از F باید به A و C ارسال شود و به F اعلام وصول گردد.

اما، وضعیت در بسته سوم  که از E می‌آید. این بسته دوباره می‌آید یک بار از طریق EAB و یک بار از طریق EFB در نتیجه فقط باید به C ارسال گردد، اما باید به A و F اعلام  وصول شود (همانطور که با بیت‌ها مشخص شده است.)

 اگر بسته‌ها اولیه هنوز دربافر باشد و بسته تکراری  دریافت شود،بیتها باید تغییر کنندو به عنوان مثال اگر قبل از این که وارده چهارم موجود در جدول ارسال شود. یک کپی از حالت c برسد این شش بیت به 100011 تغییر می‌کند تا نشان دهد که بسته باید به f اعلام وصول شود ، ولی نباید به آنجا ارسال گردد.

محاسبه مسیرهای جدید

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

اکنون الگوریتم دیکسترا را می‌توان اجرا کرد تا کوتاه ترین مسیر به همه مقصدها را بیاید نتایج این الگوریتم می‌توانددر جدول مسیر یابی قرار گیرد و عمل عادی از سر گرفته شود.

برای زیر شبکه‌ای با n مسیریاب که هرکدام k همسایه داشته باشد حافظه لازم را برای ذخیره داده ورودی متناسب با kn است این موضوع در شبکه‌های بزرگ  می‌تواند مشکل زا باشد زمان محاسبه نیز ممکن است زیاد باشد با این وجود مسیر یابی حالت پیوند  در بسیاری از حالتهای عملی به خوبی کار می‌کند.

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

مسیر یابی  حالت پیوند در شبکه‌های واقعی به طور گسترده به کار رفته است ، لذا مثال هایی در رابطه با آن ارائه شده اند، قرار داد ospf به طور فزاینده‌ای در زیر شبکه‌ای به کار گرفته می‌شود، از الگوریتم‌های حالت پیوند استفاده می‌کند ospf که به طور فزاینده‌ای در زیر شکبه به کار گرفته می‌شود ، از الگوریتم حالت پیوند استفاده می‌کند.

قرارداد حالت پیوند مهم دیگر is-is( سیستم میانی - سیستم میانی) نام دارد که برای شبکه dec طراحی شد وبعداً iso آنرا پذیرفت تا در قرارد داد لایه شبکه  بی اتصال خود یعنی  clnp به کار گیرد از آن پس ، اصلاح شد تا به سایر قرار دادها به خصوص ip خدمات ارائه کند is-is در بسیاری از ستونهای فقرات اینترنت به کار گرفته شد از جمله در ستون فقرات nsfnat قدیمی و در بعضی از سیسمتهای سلولی دیجیتال مانند cdpd نیز به کاررفت شبکه novel از شکل تغییر یافته‌ای از nlsp)is-is برای مسیر یابی بسته‌های ipx استفاده می‌کند .

اساسا is-is تصویری از توپولوژی مسیریاب  را توزیع می‌کند که از آن کوتاهترین مسیرها محاسبه می‌شوند هر مسیر یاب، در اطلاعات حالت پیوند خود، اعلام می‌درد که به کدام آدرسهای لایه شبکه مستقیما دسترسی دارداین آدرس ها، می‌توانند : از متد خود ایستایی مربوط به بازسازی‌های حالت پیوند غرق کردن ،مفهوم مسیریاب تعیین شده در شبکه مستقیماًدسترسی دارد این آدرس‌ها می‌توانند ip-ipx-apple talk یا بسیاری از آدرس‌های لایه شبکه  را پشتیبانی کند.

ospf بسیاری از ابداعاتی را که is-is طراحی کرده پذیرفت ospe چند سال بعد از iS-IS طراحی شد این ابداعات عبارتند از متدخود ایستایی مربوط به بازسازی‌های حالت پیوند غرق کردن،مفهموم مسیریابتعیین شده در شبکه محلی ،و متد محاسبه وپشتیبانی تقسیم مسیر و مقیاس‌های چندگانه ، درنتیجه  تفاوت  اندکی بین IS-IS و oSPF وجود دارد. مهمترین اختلاف این است که IS-IS طوری رمز گذاری شده است که می‌توان به طور همزمان اطلاعاتی راجع به قراردادهایی که لایه شبکه چندگانه  را انتقال داد، این ویژگی در OSPF وجود ندارد این امتیاز در محیطهای قرارداد چندگانه بزرگ ،ارزشمند است.

مسیریابی سلسله مراتبی   

با بزرگ شدن اندازه شبکه، جدول‌های مسیر یابی  مسیریابنیز به تناسب آن رشد می‌کنند. با بزرگ شدن اندازه جدول‌های ، نه تنها حافظه مصرف شده بیشتر می‌گردد ، بلکه زمان لازم برای جست وجو درجدول بیشتر می‌شود. و برای گزارش وضعیت آنها به پنهای باند بیشتری نیاز است . ممکن است شبکه‌های به حدی رشد که دیگر امکان نداشته باشد.که هر مسیر باب برای هر مسیریاب دیگر دارای یک وارده باشد ، لذا مسیر یابی به صورت سلسله مراتبی انجام می‌شود. مانند شبکه تلفن.)

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

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

شکل 11 یک مثال کمی از مسیریابی در سلسله  مراتب دو سطحی با پنج ناحیه را نشان می‌دهد. جدول مسیریابی کامل مربوط به مسیریاب1A دارای 17 وارده است(َ(شکل 11)(ب) وقتی مسیریابی‌های محلی،وارده‌های ،وجود دارد،اما ناحیه‌های دیگر در یک مسیر باب جمع شده‌اند لذا کل ترافیک ناحیه 2 از طریق خط 1B-2A منتقل می‌شود اما بقیه ترافیک از راه دور ،از طریق خط 1C-3B   منتقل خواهد شد مسیر یابی‌ها در هر ناحیه،صرفه جویی در فضای جدول بیشتر می‌شود.

با این صرف جویی ،باید تاوانی را پس داد و آن، افزایش  طول مسیر است به عنوان بهترین مسیر از 1A به SC از طریق ناحیه 2 است ،اما در مسیر یابی سلسله مراتبی ،5 از طریق ناحیه 3 منتقل می‌شود زیرا این کار برای اغلب مقصدها در ناحیه پنج بهتر است .

وقتی شبکه منفردی بسیار بزرگ می‌شود این سوال مطرح است: سلسله مراتب چند سطح باید داشته باشد؟ بعنوان مثال زیر شبکه‌ای با 720 مسیریاب را در نظر بگیرید. اگر سلسله مراتبی وجود نداشته باشد، هر مسیریاب به 72 وارده جدول نیاز دارد اگر زیر شبکه به 24 ناحیه 30 مسیریابی تقسیم شود هر مسیریاب نیازمند 30 وارده محلی و 23 وارده راه دور است که مجموع آن 53 وارده است. اگر سلسله مراتب سه سطحی انتخاب شود، با هشت دسته که هر کدام حاوی 9 ناحیه از مسیریاب‌ها باشند هر مسیریاب برای مسیریابی محلی به 10 وارده نیاز دارد و برای مسیریابی به سایر نواحی در دسته خود به 8 وارده نیاز دارد و برای خوشه‌های راه دور به 7 وراده نیاز دارد که در مجموع برابر با 25 است. کامون و کلینراک (1979) کشف کردند که بهترین تعداد سطوح در زیر شبکه‌ای با N ln است که به ازا هر مسیریاب به N  ln وارده نیاز دارد. آنها همچنین نشان دادند که افزایش میانگین طول مسیر در اثر مسیریابی سلسله مراتبی اندک است و اغلب قابل قبول خواهد بود.

مسیریابی پخشی

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

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

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

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

چهارمین الگوریتم پخشی، برای مسیریاب آغازگر پخش، از درخت بایگانی استفاده می‌کندة یا از هر درخت پوشای مناسب استفاده می‌نماید. درخت پوشا زیر مجموعه‌ای از زیرشبکه است که تمام مسیریابها را در بر می‌گیرد و فاقد حلقه است. اگر هر مسیریاب بداند کدامیک از خطوط متعلق به درخت پوشا است، می‌تواند بسته دریافتی را بر روی تمام خطوط درخت پوشا به جز خطی که بسته از آن رسیده است کپی نماید این روش از پهنای باند به خوبی استفاده می‌کند؛ و کمترین تعداد بسته‌های مورد نیاز برای انجام این کار را تولید می‌نماید. این روش از پهنای باند به خوبی استفاده می‌کند و کمترین تعداد بسته‌های خمورد نیاز برای انجام کار را تولید می‌نماید. تنها مشکل این است که هر مسیریاب باید اطلاعاتی راجع به درخت پوشا داشته باشد. گاهی این اطلاعات وجود دارند (مثلا، در مسیریابی حالت پیوند)، اما گاهی نیز وجود ندارد (مثلا در مسیریابی بردار فاصله).

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

نمونه‌ای از الگوریتم پیشروی مسیر معکوس در شکل 12 آمده است. قسمت (الف) زیرشبکه را نشان میدهد، قسمت (ب) درخت بایگانی مربوط به مسیریاب I آن زیر شبکه را نشان می‌دهد و قسمت (ج) چگونگی عملکرد الگوریتم مسیر معکوس را نشان می‌هد در جهش اول U بسته هایی را به N , H , H , F می‌فرستد (که در سطر دوم درخت نشان داده شده است). هر کدام از این بسته‌ها از مسیر بهینه به I دریافت می‌شونهد (با فرض اینکه مسیر بهینه در درخت بایگانی باشد) و دور حرف آن دایره‌ای کشیده شده است. در جهش دوم هشت بسته تولید می‌شوند؛ هر مسیریابی که در جهش اول بسته‌ای را دریافت کرد، دو بسته تولید می‌کند. ضمن تولید تمام این هشت بسته به مسیریاب‌های ملاقات نشده قبلی می‌رسند که پنج بسته از آنها در امتداد خط بهینه به مقصد می‌رسد. از شش بسته‌ای که در جهتش سوم تولید می‌شود فقط سه تا از مسیر بهینه می‌رسند (در K , E , C) و بقیه تکراری‌اند. پس از پنج جهش و 24 بسته، پخش خاتمه می‌یابد در حالی که اگر درخت بایگانی دنبال می‌شد چهار جهش و 14 بسته لازم بود.

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

مسیریابی چند پخشی

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

ارسال پیام به چنین گروهی چند پخشی نام دارد و الگوریتم مسیریابی آن، مسیریابی چند پخشی نامیده می‌شود. در این بخش یکی از روشهای مسیریابی چند پخشی را بررسی می‌کنیم.

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

برای مسیریابی چند پخشی، هر مسیریاب، درخت پوشایی را ایجاد می‌کند که تمام مسیریابهای موجود در زیر شبکه را در بر گیرد. بعنوان مثال در شکل 13 (الف) زیر شبکه‌ای با دو گروه 1 و 2 وجود دارد. بعضی از مسیریابها به میزبانهایی دست یافتند که متعلق به یک یا هر دو گروه است (همانطور که در شکل آمده است). درخت پوشای مربوط به مسیریاب سمت چپ، در شکل 13 (ب) آمده است.

وقتی فرایندی بسته چند پخشی را به گروهی می‌فرستد، اولین مسیریاب، درخت پوشای خود را بررسی کرده آن را هرس می‌کند. برای این کار تمام خطوطی را که به میزبانهایی می‌روند که عضو این گروه نیستند حذف می‌کند. در مثال مورد نظر ما شکل 13 (ج) درخت پوشای هرس شده مربوط به گروه 1 را نشان می‌دهد. شکل 13 (د) درخت پوشای هرس شده مربوط به گروه 2 را نشان می‌دهد. بسته‌های چند بخضی فقط از طریق درخت پوشای مناسبی ارسال می‌گردند.

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

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

یکی از عیب‌های این الگوریتم این است که در شبکه‌های بزرگ به خوبی کار نمی‌کند فرض کنید شبکه‌ای دارای n گروه است و هر گروه به طور متوسط دارای m عضو است. برای هر گروه m درخت هرس شده پوشا باید ذخیره گردد و در نتیجه تعداد کل درختها mn است. وقتی گروه‌ها بزرگ باشند حافظه زیادی برای ذخیره همه درختها لازم است.

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

مسیریابی برای میزبانهای سیار

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

مدل میانی که طراحان از آن استفاده می‌کنند در شکل 14 آمده است در اینجا یک شبکه گسترده وجود دارد که حاوی مسیریابها و میزبانها است. شبکه‌های محلی و شهری و سلول‌های بی سیم به این شبکه گسترده  متصل‌اند.

میزبان‌هایی که حرکت نمی‌کنند (ثابت اند) از طریق سیم‌های مسی یا فیبر نوری به شبکه وصل می‌شوند. بر عکس دو نوع میزبان دیگر وجود دارند. میزبانهای مهاجر میزبانهای ثابتی‌اند که گاهی از یک سایت ثابت به سایت ثابت دیگر منتقل می‌شوند اما فقط وقتی از شبکه استفاده می‌کنند که به طور فیزیکی به آن وصل باشند. میزبانهای متحرک کسانی هستند که در حال حرکت نیز به شبکه متصل اند. این دو نوع میزبان را میزبانهای سیار می‌نامند.

فرض می‌شود تمام میزبانها موقعیت داخلی ثابتی داشته باشند که هرگز تغییر نکند. میزبانها آدرس داخلی ثابتی نیز دارند که محل آنها را مشخص می‌کنداین حالت را با شماره تلفن [phone] مقایسه کنید که نشان دهنده ایالات متحده (کد کشور1) و جزیره مان هاتان (212) است. هدف مسیریابی در سیستمی با میزبانهای سیار، عبارت است از: ارسال بسته‌ها به میزباهای سیار به کمک آدرسهای داخلی آنها، و خواندن بسته‌ها توسط میزبانها در هر جایی که هستند.

در مدل شکل 14 جهان ( از نظر جغرافیایی) به واحدهای کوچکی تقسیم شده است. این واحدها را ناحیه می‌نامیم به طوری که هر ناحیه یک شبکه محلی یا سلول بی سیم است هر ناحیه دارای یک یا چند نمایندگی خارجی است است که فرایندهایی هستند که تمام میزبانهای سیار ناحیه را نگهداری می‌کند بعلاوه هر ناحیه دارای نمایندگی داخلی است. این نمایندگی میزبانهایی را که خانه شان در این ناحیه قرار دارد ولی فعلا با ناحیه دیگری در حال ملاقات‌اند نگهداری می‌کند.

وقتی میزبان جدیدی وارد ناحیه‌ای شود، چه از طریق اتصال به آن (مثل وصل شدن به شبکه محلی)، یا سرگردان بودن در سلول، کامپیوترش باید خودش را با نمایندگی خارجی ثبت نماید. روند ثبت به صورت زیر انجام می‌شود:

1.                   هر نمایندگی خارجی به طور تناوبی بسته‌ای را پخش می‌کن تا وجود و آدرس خود را اعلام کند. میزبان سیار تازه وارد ممکن است منتظر یکی از این پیامها باشد اما اگر در مدت معدین چنین پیامی نرسد، میزبان سیار می‌تواند بسته‌ای را پخش کند و بگوید آیا هیچ نمایندگای خارجی وجود دارد؟

2.                   میزبان سیار، با نمایندگی خارجی ثبت می‌شود برای این کار آدرس داخلی خود آدرس لایه پیونده داده فعلی، و اطلاعات سری دیگر را ارائه می‌کند.

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

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

5.                   وقتی نمایندگی خارجی اعلام وصولی را از نمایندگی داخلی دریافت می‌کند یک وارده در جدول خود ایجاد می‌نماید و اطلاع می‌دهد که میزبان سیار ثبت شده است.

ایده آل ان است که وقتی کاربری ناحیه را ترک می‌کند، باید اطلاع دهد تا از ثبت خارج شود، اما اغلب کاربران به طور غیر منتظره، کامپیوترهای خودشان را خاموش می‌کنند.

وقتی بسته‌ای به میزبان ارسال می‌گردد به شبکه محلی داخلی کاربر هدایت می‌شود زیرا چیزی است که آدرس، انجام آن را می‌طلبد، مانند آنچه که در مرحله 1 از شکل 15 نشان داده شده است اینجا فرسنتند در شهر شمال غربی سیتل می‌خواهد بسته‌ای را از طریق ایالات متحده در نیویورک به یک میزبان بفرستد. بسته‌های ارسال شده به میزبان سیار در LAN داخلی خود در نیویورک، توسط نمایندگی داخلی متوقف می‌شود. سپس نمایندگی داخل، محل جدید (موقتی) میزبان سیار را جست و جو می‌کند و آدرس نمایندگی خارجی را می‌یابد که میزبان سیار را جست وجو می‌کند و آدرس نمایندگی خارجی را می‌یابد که میزبان سیار را اداره می‌کند.

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

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

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

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

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

تا کنون با چگونگی مسیریابی در حالتی که میزبانها سیار و مسیریابها ثابت باشند آشنا شدید حالت دیگر این است که خود مسیریابها سیار باشند. بعضی از این موارد عبارت‌اند از:

1.      وسایل نقلیه نظامی در میدان جنگ که هیچ ساختمانی وجود ندارد

2.      ناوگان کشتی‌ها در دریا

3.      کارکنان اضطراری در هنگام وقوع زلزله که ساختمانها را خراب کرده است

4.      گردهمایی افرادی با کامپیوترهای کیفی در منطقه‌ای که فاقد802.11 است.

در همه این موارد و موارد مشابه، هر گروه متشکل از یک مسیریاب و یک میزبان است که معمولا در یک کامپیوتر قرار دارند. شبکه هایی از گره‌ها که در نزدیک یکدیگر قرار می‌گیرند. شبکه‌های موقتی یا MANET (شبکه‌های موردی همراه) نام دارند. آنها را به طور مختصر شرح می‌دهیم.

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

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

کشف مسیر

شبکه موقتی را در هر لحظه می‌توان به وسیله گرافی از گره‌ها (مسیریاب ها+ میزبانها) توصیف کرد. دو گره در صورتی متصل به هم هستند که بتوانند مستقیما با استفاده از رادیوهای خود با یکدیگر ارتباط برقرار کنند (در این صورت در گراف یالی بین آنها وجود دارد). چون ممکن است یکی از آنها خیلی قوی تر از دیگری باشد ممکن است A به B متصل باشد اما B به A متصل نباشد. اما برای سهولت فرض می‌کنیم تمام اتصالها متقارن هستند. توجه داشته باشید که اگر دو گره در رادیوی یکدیگر باشند به معنای این نیست که به هم متصل هستند.

برای توصیف این الگوریتم شبکه موقتی شکل 16 را در نظر بگیرید که در آن فرایندی در گره A می‌خواهد بسته‌ای را به گره I بفرستد. الگوریتم AODV در هر گره دارای جدولی است که کلید آن مقصد است و اطلاعاتی راجع به آن مقصد ارائه می‌کند از جمله کدام همسایه باید بسته را بفرستد تا به مقصد برسدو فرض کنید، A در جدول خود جست و جو می‌کند و وارده‌ای را برای I نمی‌یابد. اکنون باید مسیری را به I را کشف کند. چون این الگوریتم در صورت نیاز مسیرها را کشف می‌کند، الگوریتم تقاضا نام دارد.

برای یافتنI گره A بسته ROUTE REQUEST خاصی را می‌سازد و آن را پخش می‌کند. این بسته به B و D می‌رسد (شکل 15- الف). علت این که D , B در گراف به A وصل هستند این است که A می‌تواند با آنها ارتباط برقرار کند. به عنوان مثال از F به A یالی وجود ندارد زیرا نمی‌تواند سیگنال رادیویی A را دریافت کند. لذا F به A وصل نیست.

شمارنده جهش

شماره ترتیب مقصد

شماره ترتیب منبع

آدرس مقصد

شناسه تقاضا

آدرس منبع

فرمت بسته ROUTE REQUEST در شکل 19 آمده است. این فرمت حاوی آدرسهای منبع و مقصد (معمولا آدرس IP آنها) است که مشخص می کند چه کسی برای چه کسی جست و جو می کند. شناسه تقاضا یک شمارنده محلی است و توسط هر گره ای نگهداری می شود و هر وقت ROUTE REQUEST پخش می شود یک واحد به آن اضافه می شود فیلدهای آدرس منبع و شناسه تقاضا، یک بسته ROUTE REQUEST منحصر به فرد را مشخص می کنند که به گره‌ها اجازه می‌دهند بسته‌های تکراری را حذف کنند.

هر گره علاوه بر شمارنده شناسه تقاضا شمارنده دنباله ای دارد که هر وقت ROUTE REQUEST فرستاده شد (یا پاسخی به ROUTE REQUEST داده شد) یک واحد به آن اضافه می شود. تقریبا مثل ساعت عمل می کند و برای تخشیص مسیر جدید از مسیر قدیم به کار می رود. فیلد چهارم در شکل 19 شماره ترتیب A است و فیلد پنجم جدیدترین مقدار شماره ترتیب I است که A آن را دیده است. فیلد شمارنده جهش مشخص می کند که بسته تا کنون چند جهش انجام داد. مقدار اولیه آن صفر است.

وقتی بسته ROUTE REQUEST به گره ای می رسد به صورت زیر پردازش می شود:

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

2. گیرنده مقصد را در جدول مسیر خود جست و جو می کند اگر مسیر تازه ای به مقصد شناخته شود. بسته ROUTE REPLY به منبع ارسال می شود تا به آن بگوید چگونه به مقصد برسد. معنای مسیر تازه این است که شماره ترتیب مقصد که در جدول مسیریابی ذخیره شده است بزرگتر یا مساوی شماره ترتیب مقصد موجود در بسته ROUTE REQUEST است. اگر کمتر باشد مسیر ذخیره شده قدیمی تر از مسیر قبلی است که منبع برای مقصد داشته است در نتیجه مرحله 3 اجرا می شود.

3. چون گیرنده مسیر تازه ای به مقصد نمی رساند به فیلد شمارنده جهش یک واحد اضافه می کند و بسته ROUTE REQUEST را پخش می کند داده ها را نیز از بسته استخراج و آن را بعنوان وارده جدید در جدول مسیر معکوس خود ذخیره می کند این اطلاعات برای ساختن مسیر معکوس به کار می روند لذا پاسخ می تواند بعدا به منبع برسد. فلشها در شکل 16 برای ساخت مسر معکوس به کار می روند برای وارده مربوط به مسیر معکوس جدیدی که ساخته شد، تایمری شروع به کار می کند وقتی تایمر از کار افتاد وارده حذف می شود.

D , B نمی دانند I در کجا قرار دارد، لذا هر کدام از آنها وارده ای را برای مسیر معکوس ایجاد می کنند که به A اشاره می کند  (مثل فلش های 16) بسته را در حالی پخش می کنند که فیلد شماره جهش آن 1 است. پخش حاصل از B به D , C  می رسد. C وارده ای را در جدول مسیر معکوس خود ایجاد می کند و آن را پخش می کند در حالی که D آن را بعنوان پخش تکراری رد می کند. به طور مشابه پخش حاصل از D توسط B رد می شود. پخش D توسط G , F پذیرفته و ذخیره می شود. (شکل 16 ج) پس از اینکه I , H , E پخش را دریافت کردند، ROUTE REQUEST به مقصدی می رسد که می داند I در کجا قرار دارد (یعنی خود I) شکل (16 د) را ببینید توجه کنید که گرچه پخش‌ها در سه مرحله گسسته نشان دادیم. پخش‌های حاصل از گره‌های مختلف هماهنگ نیستند.

در پاسخ به تقاضای ورودی I یک بسته ROUTE REPLY را می‌سازد (شکل 18) آدرس منبع، آدرس مقصد،  شمارنده جهش از تقاضای ورودی کپی می‌شوند، اما شماره ترتیب مقصد از شمارنده اش به حافظه منتقل می‌شود. فیلد شمارنده جهش برابر با صفر می‌شود. فیلد طول عمر مشخص می‌کند که مسیر چه مدت معتبر است. این بسته یک بسته تک پخشی به گره‌ای است که بسته ROUTE REPLY از آن آمده است که در اینجا G است. سپس مسیر معکوس را به D طی می‌کند و به A می‌رسد. در هر گره شمارنده جهش یک واحد اضافه می‌شود لذا گره می‌تواند تشخیص دهد که چقدر از مقصد I فاصله دارد.

در هر گره میانی در مسیر معکوس بسته بررسی می‌شود اگر یک یا چند شرط زیر برقرار شود آن گره به عنوان مسیری به I در جدول مسیریابی محلی ذخیره می‌شود:

1.      هیچ مسیری به I شناخته نشده باشد

2.      شماره ترتیب مربوط به I در بسته ROUTE REPLY بزرگتر از مقدار موجود در جدول مسیریابی است

3.      شماره‌های ترتیب برابرند ولی مسیر جدید کوتاه تر است

بدین ترتیب تمام گره‌های موجود در مسر معکوس مسیری به I به طور رایگان یاد می‌گیرند. گره هایی که بسته ROUTE REPLY را گرفتند ولی در مسیر معکوس نبودند (H , F , E , C ,B در مثال ما)، با انقضای مدت تایمر مربوط، وارده‌ها را از جدول مسیر معکوس حذف می‌کنند.

لذا فرایند کشف مسیر به این صورت اصلاح می‌شود. برای یافتن مقصد، فرستنده یک بسته ROUTE REPLY را می‌فرستد که طول عمر آن 1 است. اگر در مدت زمان معقولی پاسخ دریافت نشود، بسته ROUTE REPLY دیگری ارسال می‌شود. این بار طول عمر برابر با 2 خواهد بود. دفعات بعد طول عمر برابر با 3 و 4 و 5 و غیره خواهد شد به این ترتیب جست و جو به طور محلی انجام می‌شودو به طور فزاینده فراگیرتر می‌شود.

نگهداری مسیر

چون گره‌ها می‌توانند جا به جا شوند یا خاموش شوند توپولوژی خود به خود تغییر می‌کند. بعنوان مثال در شکل 16 اگر G خاموش شود، A متوجه نمی‌شود که برای رسیدن به I استفاده می‌کرد. (ADGI) معتبر نیست. الگوریتم باید این موضوع را اداره کند. هر گره به طور تناوبی پیام Hello می‌فرستدد. انتظار می‌رود هر یک از همسایه هایش به آن پاسخ دهند. اگر هیچ پاسخی دریافت نشود، پخش کننده متوجه می‌شود که همسایه‌ها از برد آن خارج شدند و دیگر به آن  متصل نیستند به طور مشابه، اگر سعی کند بسته‌ای به همسایه‌ای بفرستد که پاسخ نمی‌دهد یاد می‌گیرد که این همسایه دیگر وجود ندارد.

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

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

بعنوان مثالی از نگهداری مسیر، مثال قبلی خود رادر نظر می‌گیریم اما فرض می‌کنیم G خاموش می‌شود. توپولوژی تغییر یافته در شکل 19-ب آمده است وقتی D می‌فهمد که G ناپدید شد، به جدول مسیریابی خود نگاه می‌کند و می‌بیند که G در مسیرهایی به I , G, E استفاده شده است. اجتماع همسایه‌های فعال مربوط به این مقصدها مجموعه {A,B}  است. به عبارت دیگر، A و B در بعضی از مسیرهای خود به G وابسته‌اند ولذا باید به آنها اطلاع داده شود که این مسیرها دیگر معتبر نیستند. D با ارسال بسته هایی این خبر را به آنها می‌دهد که باعث می‌شود آنها جدول‌های مسیریابی خودشان را نوسازی کنند. علاوه بر این، D وارده‌های مربوط به E ، G و I را از جدول مسیریابی خود حذف می‌کند.

تفاوت عمده بین الگوریتم AODV و بِلْمَن- فورد این است که در AODV گره‌ها به طور تناوبی پخش هایی را که حاوی جدول‌های مسیریابی آنها باشد، انجام نمی‌دهند. این تفاوت منجر به صرفه جویی در پهنای باند و مصرف باطری می‌شود.

ADOV قادر است مسیریابی پخشی و چندپخشی را انجام دهد. مسیریابی در شبکه‌های موردی، موضوع پژوهش است.

جست و جوی گره در شبکه‌های نظیر به نظیر

یک پدیده نسبتاً جدید، شبکه نظیر به نظیر است که در آن تعداد زیادی از افراد منابع مشترکی استفاده می‌کنند. معمولاً این افراد اتصال دائمی سیمی با اینترنت دارند. اولین کاربرد گسترده فناوری نظیر به نظیر جرم گروهی بود: 50 میلیون کاربر Napster آوازهایی با حق کپی رایت را بودن مجوز مالکین کپی رایت مبادله کردند و دادگاه با وجود اختلاف نظرهای زیاد، Napster را متوقف کرد. با این وجود، فناوری نظیر به نظیر، کاربردهای جالب و قانونی دارد. مشکلاتی مثل مسیریابی دارد، ولی این مشکلات با آن چه که تاکنون مطالعه کردیم متفاوت هستند. با این وجود، مروری سریع به آن‌ها خواهیم داشت.

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

فرض می‌کنیم هر کاربر یک یا چند قلم داده مثل آواز، عکس، برنامه، فایل و غیره دارد و کاربران دیگر می‌خواهند از آن‌ها استفاده کنند. هر قلم دارای نام اسکی است. کاربر فقط رشته اسکی را می‌شناسد و می‌خواهد بداند آیا کسانی آن‌ها را کپی کردند یا خیر. چنانچه کپی کرده باشند، آدرس IP آنها را بداند.

به عنوان مثال، یک بانک اطلاعاتی توزیعی تبارشناسی را در نظر بگیرید. هر تبارشناس چند رکورد on-line برای اجداد و خویشاوندان دارد که ممکن است شامل عکس، صوت یا برش‌های ویدیوی فرد باشد. چند نفر ممکن است یک جّد پدری داشته باشند، لذا رکوردهای مربوط به یک جد ممکن است در چندین گره وجود داشته باشد. نام رکورد، نام فرد به شکل کانونی است. در نقطه‌ای از این بانک اطلاعاتی، تبارشناس می‌بیند که جد پدری او در آرشیو قرار دارد و جد پدری تو ساعت جیبی طلایی خود را برای نوه اش به ارث گذاشت. اکنون تبارشناس نام نوه را می‌داند و می‌خواهد بداند که آیا تبارشناس دیگری رکوردی برای  آن دارد یا خیر. بدون وجود بانک اطلاعاتی متمرکز چگونه می‌توان این موضوع را تشخیص داد؟

الگوریتم‌های متعددی برای حل این مسئله ارائه شدند. الگوریتم کورد (دابک و همکاران، 2001) را بررسی می‌کنیم. سیستم کورد از چندین کاربر تشکیل شده است که هرکدام دارای چندین رکورد ذخیره شده هستند و آمادگی دارند که قطعاتی از ایندکس را برای استفاده دیگران ذخیره کنند. هر گره کاربر، دارای یک آدرس IP است که می‌تواند با استفاده از تابع درهم سازی، hash به یک عدد m بیتی درهم سازی شود. کورد از SHA-1 برای تابع hash استفاده کرد. SHA-1 در رمز نگاری استفاده می‌شود که در فصل 8 بحث می‌شود. در حال حاضر می‌گوییم تابعی است که یک رشته بیتی طول متغیر را به عنوان آرگومان می‌گیرد و یک عدد تصادفی 160 بیتی را تولید می‌کند. لذا می‌توانیم هر آدرس IP را به عدد 160 بیتی تبدیل کنیم که نامش شناسه گره است.

از نظر مفهومی، کل  2 شناسه گره به ترتیب صعودی در یک دایره بزرگ چیده شدند. بعضی از آن‌ها متناظر با گره‌های کاربران هستند، ولی اغلب آن‌ها این طور نیستند. در شکل 24-5 (الف) دایره شناسه گره را برای ؟؟؟ دادیم (فعلاً کمان‌های وسط را حذف کردیم). در این مثال،گره هایی با شناسه 20،15،12،7،4،1 ،27

متناظر با گره‌های واقعی‌اند و سایه دار شده اند. بقیه وجود ندارند.

تابع successor (k) را به عنوان شناسه اولین گره واقعی بعد از k در جهت عقربه ساعت در دایره تعریف می‌کنیم. به عنوان مثال، successor(6)=7 ، successor(8)=12 و successor(22)=27 است.

اسامی رکوردها ( اسامی آواز، اسامی اجداد و غیره) توسط تابع hash درهم سازی شدند تا یک عدد 160 بیتی به نام کلید تولید شود. لذا برای تبدیل name (نام اسکی رکورد) به کلید، از عبارت key=hash(name) استفاده می‌کنیم. اگر شخصی، رکورد تبارشناشی برای name داشته باشد و بخواهد آن را برای دیگران مهیا کند، ابتدا یک دوتایی متشکل از (آدرس IP وname ) می‌سازد و سپس از successor(hash(name)) می‌خواهد این دوتایی را ذخیره کند. اگر برای این نام، چندین رکورد (در گره‌های مختلف) وجود داشته باشند، دوتایی آن‌ها در گره یکسانی ذخیره می‌شود. به این ترتیب، ایندکس به طور تصادفی در گره‌ها توزیع می‌شود. برای تحمل عیب می‌توان از p تابع درهم سازی مختلف استفاده کرد تا هر دوتایی را که در p گره ذخیره کند. اما این موضوع را در این جا بررسی نمی‌کنیم.

اگر بعداً کاربری بخواهد name را جست و جو  کند، آن را درهم سازی می‌کند تا کلید را به دست آورد و سپس با استفاده از successor(key) آدرس IP گره‌ای را می‌یابد که دوتایی‌های ایندکس آن را ذخیره کرده است. مرحله اول ساده است ولی مرحله دوم ساده نیست. برای این که بتوان آدرس IP گره متناظر با کلید خاصی را پیدا کرد، هر گره باید ساختمان داده هایی را به منظور سرپرستی ذخیره کند. یکی از این‌ها آدرس IP گره جانشین آن در دایره شناسه گره است. به عنوان مثال، در شکل 24-5، گره جانشین 4، و گره 12 گره جانشین 7 است.

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

به عنوان اولین بهینه سازی، هر گره می‌توانست آدرس‌های IP گره‌های جانشین و پیشین  را نگهداری کند و در نتیجه تقاضاها هم در جهت عقربه‌های ساعت و هم در جهت خلاف عقربه‌های ساعت (بسته به این که کدام مسیر کوتاه تر است) ارسال شوند. به عنوان مثال، گره 7 در شکل 24-5 می‌توانست برای یافتن شناسه گره 10 در جهت عقربه‌های ساعت و برای یافتن شناسه گره 3 در خلاف جهت عقربه‌های ساعت حرکت کند.

حتی حرکت در دو جهت نیز با جست و جوی خطی در سیستم نظیر به نظیر کارآمد نیست، زیرا میانگین گره‌های مورد نیاز در هر جست و جو،  است. برای افزایش سرعت جست و جو، هر گروه جدولی به نام جدول انگشت دارد. جدول انگشت m وارده دارد که اندیس آن از 0 تا m-1 است و هر کدام به یک گره واقعی اشاره می‌کنند. هر وارده دارای دو فیلد است: start و آدرس IP مربوط به successor(start) . این جدول‌ها در شکل 24-5 (ب) آمده اند. مقادیر فیلدهای مربوط به وارده i  در گره k به صورت زیر محاسبه می‌شود،

( به پیمانه( start=k+

آدرس IP مربوط به successor(start[i])

توجه کنید که هر گره، آدرس‌های IP تعداد نسبتاً کمی از گره‌ها را ذخیره می‌کند و اغلب این‌ها نیز از نظر شناسه گره به هم نزدیک هستند.

با استفاده از جدول انگشت، جست و جوی key در گره k به این صورت انجام می‌شود. اگر key بین k و successor(k) باشد، آنگاه گره successor(k) حاوی اطاعاتی راجع به key خواهد بود و جست و جو خاتمه می‌یابد. وگرنه، جدول انگشت جست و جو می‌شود تا وارده‌ای را پیدا کند که فیلد start آن نزدیک ترین جانشین key است. سپس تقاضا مستقیماً به آدرس IP در آن وارده جدول انگشت ارسال می‌شود تا از آن بخواهد که جست و جو را ادامه دهد. چون نزدیک تر به key ولی کمتر از آن است، مزیتش این است که قادر پاسخی را با تعداد اندکی از تقاضاهای دیگر ارائه کند. در واقع، چون هر جست و جو، فاصله تا مقصد را نصف می‌کند، می‌توان نشان داد میانگین جست و جو  است.

به عنوان اولین مثال، جست و جوی key=3 را در گره 1 در نظر می‌گیریم. چ.ن گره 1 می‌داند گره 3 بین آن و جانشین آن یعنی 4 قرار دارد، گره مطلوب 4 است و جست وجو خاتمه می‌یابد و آدرس IP  گره 4 برگردانده می‌شود. به عنوان دومین مثال، جست و جوی key=14 را در گره 1 در نظر می‌گیریم. چون 14 بین 1 و4 نیست، از جدول انگشت استفاده می‌شود. نزدیک ترین گره پیشین 14، گره 9 است. لذا تقاضا به سمت آدرس IP وارده 9، یعنی گره 12 پیش می‌رود. گره 12 می‌بیند که 14 بین آن جانشین آن، یعنی 15 قرار دارد و در نتیجه آدرس IP گره 15 برگردانده می‌شود.

به عنوان سومین مثال، جست وجوی key=16  را در گره 1 در نظر بگیرید. تقاضا به گره 12 ارسال میشود. ولی گره 12 پاسخ را نمی‌داند. نزدیک ترین گره قبل از 16 جست و جو می‌کند و 14 را می‌یابد که آدرس IP  گره 15 را ارائه می‌کند. سپس تقاضا به این جا ارسال می‌شود. گره 15 می‌بیند که 16 بین آن و جانشین یعنی 20 قرار دارد و در نتیجه آدرس IP گره 20 را برمی گرداند و در مسیرش به گره 1 برمی گردد.

چون گره‌ها در هر زمان اضافه و کم می‌شوند الگوریتم کورد می‌باست این عملیات را اداره کند. فرض می‌کنیم وقتی سیستم شروع به کارکرد به اندازه کافی کوچک بود و گره‌ها می‌توانستد مستقیما اطلاعات را مبادله کنند و اولین دایره و جدولهای انگشت را بسازند. از این پس نیاز به روبه خودکار است وقتی گره جدیدی مثل r می‌خواهد اضافه شود، باید با یک گره موجود تماس بگیرد و از او بخواهد آدرس IP مربوط به successor(r) را برایش جست و جو کند. سپس گره جدید از successor(r) می‌خواهد گره پیشین آن را بیابد. سپس گره جدید از هر دو می‌خواهد r را بین آنها در دایره اضافه کند. بعنوان مثال اگر گره 24 در شکل 20 بخواهد اضافه شود از هر گره‌ای می‌خواهد successor(24) را بیابد که گره 27 است. پس از گره 27 گره پیشین آن را می‌پرسد که 20 است. سپس حضورش را به هر دو اعلان می‌کند. 20 از 24 به عنوان جانشین خود و 27 از 24 به عنوان پیشین خود استفاده می‌کند. علاوه بر این گره 27 این کلیدها را در بازه 24-21 تحویل می‌دهد که اکنون متعلق به 24 هستند. اکنون 24 اضافه شده است.

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

اگر گره‌ای به خوبی دایره را ترک کند، کلیدهایش را به جانشین خود تحویل می‌دهد و خروج خود را به گره پیشین خود خبر می‌دهدو گره پیشین می‌تواد به گره جانشین گره خارج شده وصل شود. وقتی گره‌ای خراب می‌شود مشکل پیش می‌آید. زیرا، گره پیشین آن دیگر جانشین معتبری ندارد. برای حل این مسئله هر گره نه تنها جانشین مستقیم خود را نگه می‌دارد، بلکه تعداد s جانشین معتبری ندارد. برای حل اینکه مسئله هر گره نه تنها جانشین مستقیم خود را نگه می‌دارد، بلکه تعداد s جانشین مستقیم خود را نگه می‌دارد تا در صورتی که s-1 گره متوالی با شکست مواجه شود، بتواند به گره جانشین مناسبی وصل شود.

کورد خواست سیستم فایل توزیعی و سایر کاربردها را ایجاد کند و تحقیق در این زمینه ادامه دارد.

الگوریتم کنترل ازدحام

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

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

اگر حافظه کافی برای ذخیره آنها وجود نداشته باشد، بسته‌ها از بین می‌روند افزودن حافظه ممکن است کمک کند، اما ناگل (1987) دریافت که اگر مسیریاب‌ها حافظه‌های زیادی داشته باشند، ازدحام بیشتر می‌شود، زیرا در این صورت بسته‌ها با رسیدن به مقصد را افزایش می‌دهند.

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

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

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

برای پی بردن به تفاوت بین این دو مفهوم شبکه فیبر نوری با ظرفیت 1000 گیگابیت در ثانیه را در نظر بگیرید که در آن سوپرکامپیوتری سعی می‌کند فایلی را با سرعت Gbps 1 به کامپیوتر شخصی ارسال نماید. اگر هیچ ازدحامی وجود نداشته باشد (خود شبکه مشکلی نداشته باشد) نیاز به کنترل جریان است تا سوپر کامپیوتر را گاه‌گاهی متوقف کند تا کامپیوتر شخصی دچار مشکل نشود.

از طرف دیگر شبکه ذخیره و ارسالی با خطوط 1Mbps و 1000 کامپیوتر بزرگ را در نظر بگیرید نیمی از آنها سعی می‌کنند فایلهایی را با سرعت 100kbps به نیمی دیگر بفرستند. در اینجا مشکل این نیست که فرستنده سریع گیرنده کند را تحت فشار قراتر می‌دهد بلکه کنترل ترافلیک از توان شبکه بیشتر است.

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

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

اصول کلی کنترل ازدحام

بسیاری از مشکلات در سیستم پیچیده، مثل شبکه‌های کامپیوتری را می‌توا از دید نظیه کنترل نگریست در این روش راه حلها به دو دسته تقسیم می‌شوند: حلقه باز و حلقه بسته، راه حلهای حلقه باز سعی می‌کنند مشکلات را با طراحی خوب حل کنند، یعنی مطمئن می‌شوند که مشکلی بروز نخواهد کرد. وقتی سیستم راه اندازی شد و شروع به کار کرد، کامل (بی عیب) است.

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

بر عکس، راه حلهای حلقه بسته بر مفهوم  حلقه باز خوردی استوارند. وقتی این روش برای کنترل ازدحام به کار می‌رود دارای سه بخش است:

1.      نظارت بر سیستم جهت تشخیص زمان و مکان وقوع ازدحام.

2.      انتقال این اطلاعات به جایی که فعالیت باید انجام گیرد.

3.      تنظیم عمل سیستم برای برطرف کردن مشکل

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

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

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

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

در تمام الگوهای باز خوردی ، اگرمیزبان‌ها اطلاعتی راجع به ازدحام داشته باشند می‌توانند اعمالی انجام دهندکه از ازدحام را کاهش دهند برای صحت انجام کار ، مقیاس زمان باید دقیقا تنظیم گردد. اگر در هر زمان دو بسته در یک ردیف برسند ، مسیریاب می‌گوید STOP ، و هر وقت مسیریاب به مدت  بیکار باشد، می‌گوید GO ، . سیستم به شدت نوسان می‌کند و همگرا نمی‌شود. از طرف دیگر ، اگر قبل از انجام هر کاری 30 دقیقه منتظر بماند.عکس العمل راهکار کنترل ازدحام آنقدر کند است که عملا به کار نمی‌آید. برای عملکرد خوب، تا حدی به تعدیل نیازمندیم ، اما به دست آوردن ثابت زمانی ، مسئله کوچکی نیست.

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

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

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

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

سیاست‌های جلوگیری از ازدحام

مطالعه روشهای کنترل ازدحام را با نگاهی به سیستم‌های حلقه باز شروع می‌کنیم.  این سیستم‌ها طوری طراحی شدند که از بروز ازدحام جلوگیری کنند. برای این منظور از سیاست‌های مختلفی استفاده می‌شود. در شکل 21 سیاست‌های مختلفی از لایه‌های پیونده داده ها، شبکه و انتقال را مشاهده می‌کنیم که بر ازدحام موثرند (جین ، 1990).

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

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

در لایه شبکه، انتخاب بین مدارهای مجازی و داده گرام‌ها بر ازدحام تاثیر دارد. زیرا بسیاری از الگوریتم‌های کنترل ازدحام مربوط می‌شود که: آیا مسیریاب‌ها به ازای هر خط ورودی یک صف دارند، آیا به ازای هر خط خروجی یک صف دارند، یا هر دو حالت را دارند. به ترتیب پردازش بسته‌ها (مثل نوبتی یا اولویت) نیز مربوط می‌شود. در سیاست دور انداختن بسته‌ها، مشخص می‌شود که اگر حافظه کافی وجود نداشته باشد، چه بسته هایی باید دور انداخته شوند. سیاست خوب می‌تواند از ازدحام بکاهد و سیاست بد می‌تواند بر ازدحام بیفزاید.

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

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

کنترل ازدحام در زیرشبکه‌های مدار مجازی

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

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

روش دیگر این است که مدارهای مجازی جدیدی بتوانند فعال شوند، اما در جاهایی باید برقرار شوند که ازدحام موجود را رفع کنند. بعنوان مثال زیرشبکه شکل 22 (الف) را در نظر بگیرید، در آن دو مسیریاب دچار ازدحام شده اند. فرض کنید میزبان متصل به مسیریاب A می‌خواهد با میبان متصل به مسیریاب B اتصالی برقرار کند. این اتصال از طریق یکی از مسیریاب‌های دچار ازدحام عبور می‌کند. برای پرهیز از این وضعیت می‌توان زیر شبکه را مانند شکل 22 (ب) رسم کرد. در این شکل مسیرهای دچار ازدحام و کلیه خطوط آنها حذف شده اند. خط نقطه چین مسیری را برای مداری نشان می‌دهد که از مسیریاب‌های دچار ازدحام  نمی‌گذرد.

شکل2

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

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

کنترل ازدحام در زیرشبکه‌های داده گرام

اکنون روشهایی را بررسی می‌کنیم که می‌توانند در زیرشبکه‌های داده گرام و مدار مجازی به کار روند. هر مسریاب می‌تواند بهره وری خطوط خروجی خود و سایر منابع را کنترل کند. بعنوان مثال می‌تواند متغیری مثل u را به هر خط اختصاص دهد که مقدارش بین 0/0 و 0/1 است و بهره وری فعلی خط را نشان می‌دهد برای برآورد دقیقی از u نمونه‌ای از بهره وری لحظه‌ای خط، f (0 یا 1)، را می‌توان به طور تناوبی ایجاد کرد و u به صورت زیر محاسبه گردد:

که در آن، a سرعتی است که مسیریاب وضعیت فعلی خود را از یاد می‌برد.

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

بیت اخطار

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

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

بسته‌های چوک

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

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

میزبانها می‌توانند با تنظیم پارامترهای خود مثل اندازه پنجره، ترافیک را کاهش دهند، اولین بسته چوک موجب می‌شود تا سرعت به اندازه 50% سرعت قبلی کاهش یابد و بسته چوک بعدی موجب 25% کاهش می‌شود و غیره. افزایشها به تدریج انجام می‌شود تا از وقوع سریع ازدحام جلوگیری به عمل آید.

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

شکل دیگر، استفاده از طول صف یا بهره وری بافر به جای بهره وری خط، مانند سیگنال رها کننده است. البته، وزن دهی توای مشابه آنچه که با u به کار می‌رفت، می‌تواند با این مقیاس نیز به کار گرفته شود.

بسته‌های چوک مسیر به مسیر

در سرعتهای زیاد و مسافتهای طولانی، ارسال بسته چوک به میزبانهای منبع کارایی خوبی ندارد، زیرا واکنش کند است. بعنوان مثال میزبانی را در سان‌فرانسیسکو (مسیریاب A در شکل 23) در نظر بگیرید ک ترافیکی را به میزبانی در نیویورک (مسیریاب D در شکل 23) با سرعت 155 Mpbs می‌فرستد. اگر بافر میزبان نیویورک شروع به پر شدن کند، 30 میلی ثانیه طول می‌کشد تا بسته چوک به سان فرانسسیکو برسد و به آن بگوید که کندتر عمل کند. انتشار بسته چوک در شکل 23- الف به صورت مراحل دوم، سوم، چهارم نشان داده شده است. در آن 30 میلی ثانیه‌ها، 6/4 مگابیت دیگر ارسال خواهند شد. حتی اگر میزبان در سانفرانسیسکو کاملا از کار افتد، 6/4 مگابیت موجود در مجرا، به انتقال ادامه می‌دهد تا تمام شود. فقط در نمودار هفتم در شکل 23- الف مسیریاب نیویورک جریان کندتری را مشاهده می‌کند.

روش دیگر این است که بسته چوک بر هر مسیر انتقالی که از آن عبور می‌کند، موثر باشد (مانند شکل 32-ب ) در اینجا به محض اینکه بسته چوک به F می‌رسد، F باید میزان جریان به D را کاهش دهد برای انجام این کار F باید فضای بافر بیشتری را به جریان اختصاص دهد. زیرا منبع با شدت تمام در حال ارسال است اما مانند درمان دردسر در آگهی تجارتی تلویزیون، D را تسکین می‌دهد. در مرحله بعدی بسته چوک به E است ولی F را فوراً تسکین می‌دهد. سرانجام بسته چوک به A می‌رسد و جریان به تدریج کاهش می‌یابد.

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

تخلیه بار

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

مسیریابی که در بسته‌های زیادی غرق شده است بسته‌ها را به طور تصادفی انتخاب و حذف می‌کند. اما بهتر از این می‌تواند کار کند. بسته هایی که باید حذف شوند به برنامه کاربردیی که در آن اجرا می‌شوند، بستگی دارد. برای انتقال فایل بسته قدیمی ارزشمندتر از بسته جدید است، زیرا حذف بسته 6 و نگهداری بسته  از بین 10 بسته شکافی در گیرنده به و جود می‌آورد و موجب می‌شود بسته‌های 6 تا 10 دوباره ارسال شوند. این در صورتی است که گیرنده معمولا بسته‌های خارج از ترتیب را به دور بریزد. در فایل 12 بسته‌ای حذف بسته 6 ممکن است منجر به ارسال مجدد 7 تا 12 شود، در حالی که حذف 10 ممکن است نیاز به ارسال دوباره 10 تا 12 باشد. بر عکس برای چند رسانه‌ای بسته جدید مهمتر از بسته قدیمی است. سیاست قبلی (قدیمی بهتر از جدید است) معمولا شراب نام دارد و سیاست بعدی (جدید بهتر از قدیم است) معمولا شیر نام دارد.

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

برای پیاده سازی سیاست حذف هوشمند، کاربردها باید رده 4 اولویت بسته‌های خود را تعیین کنند تا میزان اهمیت آنها را نشان دهند. در این صورت مسیریابها برای حذف بسته‌ها ابتدا آنها را از رده پایین‌تر حذف می‌کنند و سپس به رده‌های بعدی می‌روند. البته مگر در حالتی که انگیزه‌های خاصی وجود داشته باشد که بسته‌ها را غیر از EVER DISCARD , VERY IMPORTANT-NEVER تعیین کند، که هیچکس این کار را انجام نمی‌دهد.

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

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

تشخیص زودرس تصادفی

بدیهی است که اگر به محض کشف ازدحام به درمان آن بپردازیم، بهتر این است که اجازه دهیم اوضاع بدتر شود و سپس به آن بپردازیم این مشاهده منجر به این ایده می‌شود که قبل از پر شدن کل بافر، بسته‌ها از بین بروند. الگویتم معروف برای انجام این کار RED (تشخیص زودرس تصادفی) نام دارد. در بعضی از قراردادهای انتقال (از جمله TCP)، پاسخ به بسته مفقود شده این است که منبع کندتر شود. منطق این عمل این است که TCP برای شبکه‌های سیمی طراحی شد و شبکه‌های سیمی قابل اعتماداند. لذا بسته‌ها اغلب به علت پر شدن بافر از بین می‌روند تا در اثر خطاهای انتقال، این حقیقت می‌تواند به کاهش ازدحام کمک کند.

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

چون مسیریاب نمی‌تواند بگوید کدام بسته بیشترین مشکل را ایجاد کرد، انتخاب تصادفی بسته‌ای از آن صف، مناسب به نظر می‌رسد.

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

کنترل لرزش

برای کاربردهایی مثل صوت و ویدیو، تا زمانی که زمان انتقال ثابت است مهم نیست که بسته‌ای پس از 20 میلی ثانیه برسد یا 30 میلی ثانیه نوسان در زمانهای رسیدن بسته، لرزش نام دارد. لرزش زیاد مثلا وقتی که بسته‌ای 20 میلی ثانیه بعد و بسته دیگر 30ثانیه بعد برسد از کیفیت صوت و فیلم می‌کاهد. لرزش در شلک 25 نشان داده شده است برعکس اگر 99% از بسته‌ها با تاخیری در بازه 5/24 تا 5/25 میلی ثانیه برسند، می‌تواند قابل قبول باشد. بازه انتخابی باید امکان پذیر باشد. باید زمان انتقال سرعت نور و کمترین تاخیر از طریق مسیریاب در نظر گرفته شود و بعضی از تاخیرهای اجتناب ناپذیر و ناچیز را نادیده گرفت.

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

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

در بعضی از کاربردها مثل ویدیوی درخواستی می‌توا لرزش را حذف کرد برای این کار باید بسته‌ها در سمت گیرنده بافر شوند و داده‌ها برای نمایش در زمان بی درنگ از بافر برداشته شوند نه از شبکه اما برای کاربردهای دیگر به خصوص در کابردهایی که نیاز به تعامل بی درنگ بین افراد است مثل تلفن اینترنت و کنفرانس ویدیویی تاخیر ناشی از بافر کردن قابل قبول نیست. کنترل ازدحام موضوع تحقیق است.

کیفیت خدمات

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

‌مسیر یابی منبع دینامیک (1)

            پروتکل DSR یک منبع  مسیریاب  روی پروتکل درخواستی است دو فاز اصلی برای پروتکل وجود دارد : کشف مسیر ونگهداری مسیر کلیدمتفاوتی بین DSR و دیگر پروتکل ها در اطلاعات مسیر یابی وجود دارد که در PACH HADER  شامل می شود نظر به اینکه اطلاعات مسیر یابی  شامل PACH HADER  می شود پس NODE گرهها میانجی برای نگهداری اطلاعات  مسیر یابی بی نیاز نیست  یک گره میانجی ممکن است تمایل به ضبط اطلاعات مسیریابی  در جداول خودش داشته باشد که به اصلاح  کردن اجرا می پردازند اما ان اجباری نیست دیگر ترکیب DSR وجود دارر که لینک های نامتقارن را حمایت می کنند همانند یک پاسخ مسیر که می تواند به درونیک بسته درخواستی مسیر بر پشت سوار شود. DSR برای شکبه های کوچک و متوسط متناسب است مانند OVERHEAD خود که می تواند تمام راههای پایین به صفر رسیده رسیده را قیاس کند OVERHEAD بطور معنی داری برای شبکه هایی با دیامترهای بزرگتر HOP افزایش خواهد یافت مثل اطلاعات مسیریابی  بیشتر که شامل packet header ها خواهند شد.

مسیر یابی دینامیک و عملکرد موازنه در شکبه های ارتباط از راه دور

مشکل مسیر یابی

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

یافتن انبوهی ازکوتاهترین راهها

بوسیله استفاده مورچه های نشان دار pheromome  مجموعا کوتاهترین  راه پیدا می شود الگوریتمهای جدید مانند یک توسعه به الگوریتمهای مسیر clossicd پیشرفته شده است آنها به ایده هایی بردار مسیر یابی مقصد درون خطی غیر هنرمان با وضع مسیر یابی  لینگ انطباق ملحق می شوند تخمین هایی وضعیت جریان ترافیک و ارزشهای لینک بوسیله ارسال نمایندگان مسیریابی در شبکه اندازه گیری شده که با بسته های اطلاعاتی منظم ترکیب گشته و track ارزش های قیمت های مواجه شده در طی سفرشان نگهداری می شوند.

جداول مسیریابی بنابراین به طور منظم جدید وبروز  می شوند که اطلاعات بدون برخی کنترل های مرکزی ، دانش توپولوژی شبکه کامل نمی شود . دو الگوریتم جدید در اینجا پیشنهاد کرده می شود. اول اینکه براساس roud trip نمایندگان مسیر قرارداده می شود که جداول مسیر یابی  بوسیله رد گم کردن مسیر شان بعدازجستجوی مقصد جدید به روز می شود جدید به روز می شود. دوم اینکه روی نمایندگان تکیه میشود که جداول مسیریابی را به طور مستقیم همچون آنها نسب به هدفشان جنبش دارند، جدید و به روزی می شوند ویک برنامه عملی موثر به سروکار داشتن با تماسهای نامتقارن ،پیشنهاد کرده می شود.

مسیر یابی نیاز به مسیر یابی :

یک شبکه یک مجموعه به هم پیوسته از node (گرهها) است (با یک سیتم  وسیع شبکه با عناوین منحصر به فرد باشد آنجا هیچ نیازی برای یک تماس مستقیم بین دو node وجود ندارد برخی node های داده شده یک تماس مستقیم  به یک یا تعداد بیشتری node خواهند داشت اگر یک node  به یک بسته addressed به طور مستقیم به یک node  تماس رسیده به سادگی به آن در نرم افزار driver لینک اختصاصی ، عبور خواهد کرد. اگر یک node  یک بسته addressed به یک node  برسد که از آن هیچ تماس مستقیمی ندارد وباید مشکل مسیر یابی تعیین نشده را حل کند که node  ان را می فرستد.

Forward در جستجوی الگوریتم

همچنین مشهور به الگوریتن Digktra;s  Forward در جستجوی الگوریتم می تواند بنابراین بطور غیر رسمی توضیح داده شود.

(N.i) c ، حداقل قیمت مسیر از I به n است

(N.i) 1  قیمت  لینک  از I به n است برای هر node است برای هر (گره )(

 برای سایر node   ها مجموع n, است برای هر l ما دوباره تکرار می شود.

پیداکردن  یک node  گره w که هنوز بوسیله الگوریتن ملاحظه نشده است ، مانند (w,i) c حداقل برای تمام node  های ملاحظه نشده است.

برای هر node (گره) متفاوت با I وw انجام می شود. اگر (n وi)  باشد پس (nو w) c= (n,w) = c(inو node ها گرهw به مجموع nodeهای رسیدگی نشده اضافه می گردد . تاکنون همه node های ملاحظه رسیدگی شده است.

الگوریتمهای مسیر یابی درکاربرد

در forword جستجوی الگوریتم ، عملکرد تمرکز یافته مناسب تری ادعا کرده می شود در back ward جستجوی الگوریتم ها می توانست فقط ارزش منطقه  یا نیم منطقه اطلاعاتی پیروی شده را که بلافاصله را از node  های  مجاور است را اداره کند.

ارزش پارامتر کاربردی در مسیر یابی الگوریتم ها ممکن است یک پارامترهای جهانی گوناگونی را بازتاب کند که شامل مخابرات واقعی تاخیری و فضای میانگیر مورد نیاز بوسیله لینگ drivel می باشد همچنین  آن ممکن است در فرمول محاسبه ارزش کاربر ملین شده استفاده گردد و.در برخی شبکه های کاربردی در ارزش (قیمت) یک لینگ یک کارکرد دینامیکی میزان و ماهیت ترافیک بر روی شبکه وجود داردوبنابراین ان مطلوب در دوبار حساب کردن جداول مسیریابی  در فواصل مناسب است .و ترافیک داده ها در گردآوری بالا در داده های مورد نیاز برای جدول محاسبه مجدد و انتقال نتایج به nodeها (گره ها ) که می توانند به تراکم بیشتر منتج می شود وارد گردید آن بایستی  همچنین شود که هر دو جدول مسیر یابی الگوریتم یک پیچیدگی را دارند.

پروتوکل اینترنت :

در پروتوکل اینترنت ip)) یک پروتکل جهت دار داده بوسیله منبع و مقصد hot ها برای مکاتبه داده ای عبوری یک packet –switched inerntwork به کار برده می شود.

داده اه دریک ip intrenrtwork در قالبهای ارجاعی مثل بسته ها یا داتا گرام ها در دوره های بطور اساسی در ip مترداف هستند فرستاده می شوند بویژه  درIP هیچ SETUP نیاز نمی شود. قبل از اینکه یک HOST  مترداف هستند فرستاده می شوند بویژه در تلاش برای فرستادن بسته ها به یک HOST  کنند آن قبلا کنند آن قبلا ابلاغ شده است. در پروتوکل اینترنت IP یک سرویس داتاگرام تا مطئمن ایجاد شد (همچنین بهترین تلاش نامیده شد) آن تقریبا گارانتی در اطراف جعبه ایجاد می کند بسته ممکن است  آسیب دیده برسد آن ممکن نادست و در هم برهم گردد مقایسه شد با دیگر بسته های ارسالی در هر دو HOST مشابه آن ممکن است دو نسخه ای المثنی گرددویا کاملا رها شده وبیفتد اگر یک کاربرد نیاز به اعتبار داشته باشد ، آن توسط دیگر وسایل  اماده گردیده می شود.

packet switches  یا مسیر یابهای internetwork ، داتاگرام های forward IP از میان لایه شبکه های بهم متصل شدندو در فقدان تحویل برخی گارانتی ها ، طرحی از packet switches در نظر گرفته می شود. که بسیار ساده تر ساخته شده است.( توضیح اینکه اگر شبکه سقوط ،نگارش دوباره یا در غیر اینصورت بسیاری از بسته ها آسیب ببیند در اجرا دیده شده بوسیله کاربر، سست خواهند شد . بنابراین اغلب عناصرشبکه به سختی تلاش می کنند این چیزها – از این پس در دوره بهترین تلاش انجام نشود.)

ip عنصر متعارف و معمول در اینترنت عمومی امروزه ،پیدا شد.پروتوکل رایج  وعمومی ترین لایه شبکه در استفاده امروزه ipv4 است این نسخه پروتوکل ، نسخه 4 را انتقال داده میکندو ipv6  جانشین ipv4  در نظر گرفته می شود در اینترنت تدریجا آدرسها را تمام می کند و ipv6 ، منبع 128-bit و عنوان مقصدها رادارد ، بیشتر ازعناوین آدرس ipv4  یا منبع 32-bit عناوین فراهم میکند. نسخه 5برای یک جریان پروتوکل های آزمایشی تعیین کرده شده اند دیگر شماره نسخه معمولا برای پروتکل های آزمایشی تعیین کرده شده اند اما بطور وسیعی استفاده نشده اند. IPaddressing و مسیر یابی  : شاید بیشترین نمودهای مجموعه IP مسیر یابی  و  آدرس های هستد addrerring به اینکه  چگونه انتهای hot  ها به صورت IPaddresses تعیین  می گردد و اینکه چگونه  و اینکه چگونه زیر شبکه های addresses تقسیم  کرده شوند و به یکدیگر طبقه بندی می کردند تخصص داده می شوند مسیر یابی ip بوسیله تمام host ها انجام گردیده می شود اما بطور مهمترین بوسیله  مسیر یابل interetwork که به طور نمونه هم در مدخل درونی پروتوکل ها IGPS  , و هم در مدخل خروجی پروتکل ها EGPS  به کار می روند که کمک به ساختن تصمیمات Forwarding  داتاگرام IP از میان شبکه های اتصالی IP می کنند

IPV6 وسیستم نام گذاری حوزه domain name

IPV6 addressed در سیستم  نام گذاری حوزه  بوسیله گزارشات AAAA برای مراجعات Forwarding نشان داده می شوند بوسیله مقایسه با گزارشات A برای IPV4 مراجعات معکوس تحت ip6.arpa و گزارشات DNAME را داشته اند.

آن در RFC2874 آزمایشی و منابع خودش را تعیین کرده شد.

ماادامیکه طرح AAAA یک نتیجه و تعمیم ساده IPV4 DNS است، طرح A6 یک معاینه کامل DNS به عمومی ترشدن است و از اینرو پیچیده تر است.

مسیر یابی الگوریتم

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

مسیریابی ساختمانی : در بخش مسیر یابی لبه ساختمانی شرح داده می شود.

مسیر یابی  قائم : در بخش مسیر یابی لبه قائم شرح داده می شود.

اختیارات مسیر یابی : راه انتخاب  شدن لبه ها: اگر این اختیار به فعالیت  پرداخته شود فقط لبه های انتخاب شده برای مسیر یابی مورد ملاحظه و رسیدگی قرار خواهند گرفت

نمونه ای مسیر یابی ساختمانی

نمونه ای از مسیریابی قائم

حداقل فاصله این حداقل فاصله مجاز دربین node (گره ها ) ولبه ها را مشخص می کند.

کاربرد خمیدگی های موجود: این اختیار ، خواه خمیدگی های موجود را که بایستی مثل یک راه حل ابتدایی برای مسیر یابی جدید به کار برده می شود را، مشخص می کند.

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

در مقیاس حداقل فاصله دوبار تعیین خواهندشد.

مسیر یابی لبه قائم : مسیریاب لبه قائم یک طرح بندی الگوریتمی گردان ونیرومندی ، برای مسیر یابی که دیاگرام لبه های کاربردی عمودی و افقی قطعات خطی است . وضعیت های دیاگرام گره ها یا برخی دیگر از لبه های روی هم افتاده بریده نخواهند شد.

امکانات عرضه شده بوسیله مسیریاب آن را ی طرح بندی کامل  برای ثاثیر بر یکدیگر یا توسعه جایی ایجادمی کنند. برخی لبه های بایستی  دوباره طراحی می شوند. بعداز اینکه کار برخی گره ها node را جابجاد می کند. متعاقبا اضافه کردن لبه ها بایستی به اندازه دیاگرام موجود طراحی می شوند. شکل 54-5 : یافتن یک راه درمیان یک مسیر پرپیچ  و خم

اختیارات مسیر یابی: مسیریاب لبه قائم یک مجموعه اختیارات را فراهم می کندکه در رفتار مسیر یاب موثر می گردد . این بخش تشکیل چند شکل اختیارات موجود را روشن می کند.

کاربرد حداقل فاصله custom بر گرهها Node اگر پس از یک cutom value برای  حداقل فاصله بین قطعه لبه و گوشه گره استفاده خواهد شد. وگرنه ازجهت دیگر این فاصله به طور اتوماتیک از حداقل بین دو قطعه لبه drive خواهد شد. نظر به اینکه این اختیار می تواند زمان محاسبه را افزایش بدهد ، آن بوسیله غفلت و کوتاهی از کار افتاده می شود.

حداقل فاصله custom به گره ها : فاصله بین قطعه لبه گوشه تعیین می شود. لبه مسیر یاب اکیداً وسخت به ارزش مجموعه set value می پیوندد. توضیح می دهد که این ارزش به طور نرمال به طور اتوماتیک drive کرده می شود جز اینکه (کاربرد حداقل فاصله custom به گره ها مجموعه set است.

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

فضای arrive  شده در مقابل جستجوی مرکز drive شده: نسبت به دو استرانژهای سنگین تعریفی ، تعیین می شود ،زمانیکه  به دنبال یک راه لبه ای می گردند ،

مسیریاب لبه تا حد امکان به setvalue می چسبد. اما در فاصله گذاری ارزش به طور انتخاب کاهش می یابد : فقط برای یک پروسه لبه به طور شایع در زمانیکه انجا فاصله بسیار کمی دریک راه vakue درست وصحیح است وجود دارد

فضای drive شده درمقابل جستجوی مرکز drive شده : نسبت به دو استرانژی سنگین تعریفی ، تعیین می شود. زمانیکه به دنبال یک راه لبه ای می گردند یعنی مرکز drive شده و فضای driveشده سنگین  و حجیم هستند و به نسبت با یک value ما بین صفر ویک ،صفر اظهار داشته می شود values به صفر، صفر راههای پایه را راهنمایی می کند که بیشتر از فضای موجود پخش کرده می شوند values به یک صفر تاکید واهمیت بیشتری به راههای نزدیک در bary center لبه داده شده ،می دهند.

حداقل منطقه عبور: اگر مجموعه set نباشد، تعداد مناطق عبوری مشاهده نشده در یک بخش گره می تواند زیاد افزایش یابد. از زمانیکه این اختیار یک اثر مثبت روی دیاگرام با قابلیت خواندن را دارد. ان بوسیله کوتاهی و غفلت توانا گردیده شد.

بها عبور : یک جریحه برای محل های عبور لبه تعیین می گردد. اساسا یک نرخ جریحه به معنی آن است که یک لبه پرتر بیشتر مسیر n زمان را نسبت به عبور یک را لبه که قبلها که مسیریابی شده ، تغییر می یابد. در مقابل به حداقل منطقه عبور  بهینه سازی به طور سراسری روی یک راه لبه داخلی کار می کند value های خوب برای یک مجازات عبور از حدود یک صفر به سه، صفر قرار می گیرند با کوتاهی کردن این value به صفر ، صفر set کرده می شود. که آنجا هیچ مجازات و جریحه ای  وجود ندارد.

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

فواید و مقرارت مسیریاب – لیبنک شده : فایده اصلی و اولیه مسیریاب معین شده این است که ان به سیرعلت عکس العمل نشان می دهد ودریک مقدار کردان دار زمان به اتصال تغییر می کند همچنین بسته های معین لینگ شده به بالای شبکه فرستاده کرده می شوند ، کوچکتر از بسته های کاربردی در مسیریاب  بردار – مقصد هستند مسیر یاب بردار مقصد نیاز به یک جدول مسیریاب  گره های درست و بی عیب دارند که انتقال داده می شوند. مادامیکه در مسیریاب معین لینک شده فقط اطلاعات درباره گره بلافاصله به همجوارها انتقال داده می شوند.

بنابراین این بسته ها به حدی کوچک هستند که آنها در منابع شبکه به درجه مهمی استفاده نمی شوند. ضرر اصلی و عمده مسیریاب ملین لینگ شده این است که نیاز به ذخیره سازی بیشتری نسبت به مسیر یاب بردار – فاصله در روان بودن و حرکت دارند

مسیر یاب peer to peer

 معرفی سیستم peer to  (p2p) می تواند به چند شکل موثر واقع شود E-mail ، ایستگاه تقویت تمرکز یابی شده یابه طور استانیکی عددی می گردند و بنابراین بدون مشکل است .

دیگر دسته  شبکه های p2p شبکه پوششی هست و شبکه های پوششی یک توپولوژی واقعی روی راس لینگ های فیزیکی وطبیعی شبکه می سازد.

گره ها لازم شده وبه این شکبه به طور دینامیکی متصل می شوند و متوسط UPTIME گره های اختصاصی  به طور نسبی پایین است و توپولوژی یک نسخه یک شبکه  ممکن است در تمام مدت تغییر می کند به محض اینکه یکی از مسیرها تاسیس کرده شود در انجا هیچ گارانتی در طول در زمان وجود ندارد که ان معتبرو به ثوت خود باقی خواهد ماند.

مسیر یاب در این شبکه ها وجود دارد بنابراین بسیار مشکل ساز است و مرکز توجه گزارشات ما خواهد شد. برخی از طراحان مسائل تما الگوریتمهای مسیر یاب P2P:

1-                  SCALBILITY

2-                  پیچیدگی

3-                  گمنامی هستند

4-                  SCALBILIT یک حد چگونگی عملکردهای سیستم های است زمانی که شماری از گره ها ویاشماری از پیغام ها روی ترقی و پیشرفت های شبکه است . پیچیدگی مراحل ترتیب گامهای  گامهای مورد نیاز برای یک بسته از یک host به دیگری در بدترین حالت scenario سو می کند ، است .وگمنامی anonymity نیاز بیشترین شبکه های p2p است اگر چه یک شکبه به طراحی شدن به anonymity  را فراهم می کنند و سپس این یک مشکل است که بایستی  در سطح مسیر یابی حل کرده شود ما به مثالهای کم الگوریتمهای مسیریاب را از هرکدام از این مناظر اشاره خواهیم کرد.

مسیر یابی Guntella

Guntella قابل بحث در اولین مسیر اصلی  شبکه پوششی که از کاربرد گسترده ای بهرمند می شود.

عقیده قبلی ساده بود. در اتصال یک مشتری به شبکه ، می بایستی  آدرس  حداقل یک گره موجود روی شبکه را شناسایی کرده باشد. بیشتر یک بیشتری یک اتصال  به این گره node داشت آن می توانست بعد از پراکنده کردن یک صدای غر مانند آدرسهای دیگر گره ها node را بیاید ایده اصلی این است که هرگره node یک اتصال به یک شماره از دیگر گره ها node  را به طور نرمال تقریبا 5تا برقرار می کند.

جستجو کردن در شبکه برای یک منبع  تا حدی کاربرد یک time-to- live counter را کنترل نمایند. این نوع مسیر یاب ساده ترین نوع ممکن برای یک شبکه  پوششی است به هر حال آن نیز خودش بدون مشکلات نیست.

مسیر یاب طرح Gnutemlla یا طیغان کننده ، خیلی خوب برای شبکه  کوچک و متوسط کار می کند. ان نشان داده است که ارزش جستجو روی یک شبکه طرح Gnutemlla به طور superlinear مانند شماری از گره های node زیاد شده ، افزایش  می یابد. زمانی که اشباع گره node اشباع گره nodeرخ می تواند جزجز و ناقص بشود Gnutemlla ، بنابراین در صورتی که یک حل ساده راه به خوبی مطابق مقیاس قرار نمی دهد. جستجو شبکه Gnutemlla  را به طور کلی آمیختگی و پیچیدگی تعریفی است همانطور که هر جستجو درباره فواصل n8d تفسیر خواهد شد در باره اینکه n time to live است و d در شماره ای از همتای های هر node گره است. flooding در بیشترین حل بهینه برای مسیر یابی آشکار بدهی نیست و ان مدتی نبود قبل از دیگر الگوریتمهای  پدیدار مسیر یاب p2p که موثرند بودند.

ما درباره تعداد از این ها به انضمام مسیریاب معنایی و جدوال پخش hash را باعث و مطرح خواهیم کرد.

یک شکبه که بطور ویژه  طراحی کرده شد به طور مستعارانه در ذهن طراحی کرده شد . مانظری درنتایج  اتخاذ خواهیم کرد که anonymity بی نامی بر حسب sclablity و پیچیدگی ارائه می گردد فایده اصلی chord ها در گارانتی است که شما یک پاسخ درون زمان hog(n)  به دست خواهید آورد. همچنین یک فایده مهم در فقدان افزونه بالایی است. هر دو اینها به آن یک لبه وسیع روی برخی الگوریتمهای foolding می دهند اما درکل معلوم است که الگوریتمهای  DHT منابع داده ها یشان را دریک راه تشکیل شده اندوخته می کند آنها همیشه  الگوریتمهای flooding را در این منطقه شکست خواهند داد CHORD به خوبی مطابق مقیاس قرار داده می شود. معین است که جستجو دسته LOG وجود دارد و همچنین به طور نسبی پیچیدگی  کم دارد.

فواید:

1-    داده های عمومی در کل سیستم تکرار می شود.

2-    داده ها به طور بی نام و مستعارانه و به طور آزاد پخش کرده میشود، اصول و عقاید کلی را در سیستم در هدف دارد.

3-    الگوریتم مسیریابی به وفق دادن و بهبودی سودمند به طور اضافه طراحی کرده شد.

مضرات:

1-       مردم به بخشیدن و اهداء بخشی از hard-drive شان به سیستم مخصوصاً دو دل و مردد هستند زمانی که آن می توانست در انداختن اطلاعات استفاده شود. آنها پسند و موافقت نمی کنند.

2-       شبکه به سادگی قابل جستجو نیست، کاربر نیاز به شناخت کلید پیدا کردن یک فایل دارد.

3-       شبکه کند و آهسته است. همانطور که داده ها باید در بین تمام گره ها (node) سریع و فوراً عبور کند. جستجوهای می توانند بطور جزجز کند و آهسته شوند زیرا آنها از multicasting استفاده نمی کنند.

رده بندی یک به یک الگوریتم های مسیریابی

تصمیمات مسیریابی: عملکرد معیار برای مسیریابی مکان و زمان عملکرد معین شده مسیریاب است.

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

مسیریابی منبع: گره های منبع به طور از بیش تعیین شده راه های مسیریابی را قبل از تزریق بسته ها به درون شبکه کامل می کنند، بطوریکه مسیریاب ها فقط header ها می خوانند ( و معمولاً subfield های مناسب و اختصاصی را جدا کرده یا مشخص می کنند) . و از اینرو مجموعه (set) به طور مکانیکی راه خودش را برمی گزیند. اگر میزان خروج یک مسیریاب k است. سپس header  بسته پیروی از یک راه طویل d کرده که حداقل نیازمند bit های d log k را برای رمزی کردن شماره های کارکرد کانال است. این برنامه در ماشین IBM SP-2 استفاده کرده می شود.

در شبکه ها اساس روی تولیدات    Cartesianاندازه اطلاعات مسیریابی header که می تواند بوسیله استفاده مسیریابی  street-sign (علامت خیابان) کاهش یابد.

کوتاهی و نقصان کارکرد کانال اندازه و جهت یکسان شبیه نیروی معروف شده کانال است، جز اینکه header صریحاً با شماره معلوم کارکرد جدید کانال به یک آدرس پیوسته گردیده که با آدرس های مسیریابی رایج جور می باشد.

مسیریابی پیوندی (هیبرید) چند فازی: گره منبع فقط آدرس های چند گره واسطه و میانه را از پیش محاسبه می کند و راههای دقیق بین آنها، در یک روش توزیع شده بوسیله مسیریاب ها تعیین گردیده می شود. این عملکرد برای مثال در ماشین NCUBE-2 انجام شد.

آن فرض می کند که مسیریاب ها بطور متوالی آدرس های گره واسطه و میانه را جدا می کنند.

مسیر یابی تمرکز یافته: در عملکرد مسیریابی بوسیله یک کنترل کننده تمرکز یافته تعیین کرده می شود. این به طور نمونه در ماشین های SIMD استفاده شده است.

اجرا الگوریتم مسیریابی: تصمیمات مسیریابی باید سریع باشند. در حالت مسیریابی توزیع شده، یک اجرا HW مطلوب است. آنجا دو معبر اصلی وجود دارد.

ماشین محدود-معین: الگوریتم SW یا HW اجرا و تکمیل چند رباط مکانیکی محدود- معین.

جدول مراجعه: منبع گره ها و یا مسیریاب ها، جداول مسیریابی را حفظ می کنند.

تعدادی از مدخل ها O(N) است. در جائیکه N ،# گره ها در شبکه است. جداول مسیریابی گره منبع شامل تمام راههای تشخیصی می باشند، با در نظر گرفتن اینکه در حالت مسیریابی توزیع شده در جداول مراجعه فقط می گویند که کارکرد کانال یا کانال ها مربوط به هر مقصد می شود.

کاهش یافتن اندازه جدول خطی، مسیریابی وقفه ای نامیده شده که می تواند کاربرد داشته باشد. جداول مسیریابی می توانند استاتیک یا به طور دینامیکی باقی بمانند. یک مثال که یک سیستم با جداول مراجعه ای به طور دینامیکی جدید و به روز می گردد. Myrinet است. که اجازه محاسبات مجدد اتوماتیک جداول مسیریابی را هنگامی که شبکه اتصالی داخلی تغییر می کند را دارد. برای مثال به واسطه حذف یک گره را می توان گفت.

Adaptivity تصمیمات مسیریابی می تواند نه فقط اساسی روی آدرس ها، بلکه همچنین روی دیگر اطلاعات باشد.

الگوریتم های مسیریابی قطعی: همیشه راه مسیریابی واحد یکسان برای جفت منبع معین و آدرس های مقصد، به طور نمونه یک shortest را تولید می کنند. زمانی که مسیریابی منبع به کار برده می شود، گره منبع برگشت عملکرد مسیریابی فرضی یک راه منحصر به فرد را بدون نظر به اطلاعات درباره عبور و مرور اجرا می کند. برای مسیریابی توزیع شده مسیریاب ها تصمیم های منحصر به فرد را در هر گره واسطه ومیانه ایجاد می کنند. مسیریابی  قطعی در بیشترین ماشین های موازی موجود به طور تجارتی به کار برده می شود.

این ساده، سریع و بسیار عملی تحت اتخاذ یکسان عبور و مرور است. در ماشین های مشبک- پایه ای آن مسیریابی اندازه- ترتیب است. (XY,XYZ,e-cube) . آن شناسایی گردیده می شود به بی تکلیفی دچار وقفه شدن- آزاد بودن در شبکه و در اجرا انجام HW . آسان است. عبور و مرور ناهمسان نیاز به چند درجه adaptivity دارد.

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

الگوریتم های مسیریابی انطباقی: اطلاعات  درباره عبور و مرور شبکه و یا وضعیت کانال به اجتناب از مناطق انبوه شده یا معیوب به کار برده می شود. مسیریابی انطباقی گره- منبع فقط زمانی مفید است که در وضعیت عبور و مرور خیلی سریع تغییر ایجاد نکند، وگرنه در گره منبع ممکن است اطلاعات منسوخ داشته و یک وضعیت سراسری گزاف به monitor است.

عملکرد مسیریابی: که یک مجموعه کانال های کارکردی ممکن، تحویل داده می شود.

عملکرد انتخاب کارکردی: که یکی از کانال های کارکردی آزاد در میان وضعیت اطلاعات منطقه کاربردی انتخاب می شود. (اگر این چنین موجود باشد.)

تست در الگوریتم انطباقی: در تست الگوریتم انطباقی مجزا از دیگر وظیفه راهنمای مسیر منطبق است.

تست ترکیبی از 20 وظیفه است که شامل سفرهایی بین اثرات متقابل در منطقه palo Alto می باشد. در جبران کردن برای فقدان تاثیر بر یکدیگر، ما 4 مسیر برای هر وظیفه در عوض آن دو تولید کردیم. از زمانی که ما هیچ فرصتی در ساخت مدل های کاربر نداشتیم، ما به ترتیب بردارهای weight اکتشافی را با یک weight   واحد برای یک صفت و صفر برای استراحت، ایجاد مسیرهای بهینه برای زمان، فاصله، تعداد پیچش ها را به کار می بردیم. ما 4 مسیر ار برچسب دار به طور تصادفی بین A,D روی یک نقشه palo Alto  طرح ریزی کردیم. شکل 5 مثالی از یکی ار برنامه ها را نشان می دهد و خودش 4 مسیر را انتخاب می کند.

شکل5: برنامه ساده برای موضوعات در نقطه آغاز در بسته در بالا سمت چپ است و نقطه انتهایی در بسته پایین سمت راست می باشد. A  مسیری با کمترین پیچش ها می باشد. B سریعترین مسیر است. C مسیری با کمترین تقاطع ها است و D کوتاهترین مسیر است.

شکل 6: میزان تبادلات برای 3 صفت راجع به مسافت، محاسبه از تمام داده ها برای هر موضوع است. ارزشهای مثبت بالا برای یک مسافتی اشاره می کند که کوتاهترین مسافت است و کم اهمیت تر از کاهش است که نسبت داده می شود، ارزشهای نزدیک صفر اشاره می کند که فاصله کوتاهتر مهم تر است و ارزش های منفی بالا اشاره می کند که مسافت طولانی تر قابل ترجیح تر است.

مسیریابی دینامیک: مسیر برای به روز شدن و جدید شدن RIP روی شبکه پذیرفته خواهد شد و آنها را در ساختن یک جدول مسیریابی به کار می برند.

RIP یک انتخاب مسیریابی خوب برای شبکه های خیلی بزرگ نیست اما آسان در اجرا کردن است و برای شبکه های کوچک به خوبی کار می کند در /etc ورودی های فایل، مسیرهای استاتیک مجاز به اضافه کردن به daemon مسیریابی را که به صورت دستی هستند را فراهم کنند. Format فایل به شرح زیر است:

Startkey word یکی از 1- net –مسیر A به یک شبکه

2- host – مسیر A به یک host است.

آدرس مقصد مکان بسته را می گویند. اگر مقصد .،.،.،. است. پس آن در مسیر قصور default است.

ورودی در مدخل خارجی که در جستجوی مقصد می باشد، با gwaddress مشخصی در IP address ورودی    تعریف می شود.

متریک یک نیاز keyword است و ارزش متریک در ارزش به مقصد است.

ارزش فعال/ منفعل اشاره می کند اعم از اینکه یک مسیریاب به روز کردن updates  مسیریابی را انجام می دهد.

مسیریابی adaptive از Biocrawler

مسیریابی adaptive قابلیت یک سیستم را شرح می دهد در میان اینکه مسیرها بوسیله مقصدشان مشخص کرده می شوند.

دگرگونی در مسیر که وظایف مسیر را در سوتالیرسیستم درواکنش به تغییر  در وضعیت های است انطباق بر آن شد که به مانند برخی مسیرها امکان باقی ماندن معتبر را در پاسخ به تغییر مجاز کند استفاده مردمی یک سیستم حمل و نقل می تواند مسیر یابی adaptive را  آشکار کند برای مثال اگر یک ایستگاه خط آهن بسته کرده شود مردم می توانند از یک قطار در یک ایستگاه متفاوت پایین امده  روش دیگری را به کار ببرند. همانند یک اتوبوس که به مقصدش می رسد . term به طور عادی در داده های شبکه های شرح دادن قابلیت یک شبکه در آسیب دیدن مسیر دور تا دور به کار برده می شود. مثل فقدان یک گره node با یک اتصال بین گره ها به شرطی که انتخاب های راه دیگر موجود باشند آنجا چندین پروتکل به رسیدن این ها به کار گرفته می شوند.

RIP

OSPE

IS-IS

 IGRP/EIGRP

IGRP/EIGRP

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

متریک های متعدد

EIGRP با 5 متریک مختلف با هر مسیر مربوط می باشد.

تاخیر کردن Dekay

پهنای باند Bandwidth

اعتبار و قابلیت اعتماد Reliablity

MTV

Load

برای هدف های مسیرهای مقایسه ای اینها در فرمول weigted به ایجاد متریک واحد به یکدیگر می پیوندند.

K4)}+قابلیت اعتماد K3)}*{(k6/تاخیرکردن *)(256-Load)+( K2)* پهنای باند( K1) +*پهنای باند( {

جایی که ثابت های مختلف(k1 تا k5 ) می توانند بوسیله کاربر در ایجاد حرکات مختلف set کرده شوند اگر k set به صفر است در term استفاده کرده نمی شود کسری برای k1,  و3 k به 1 set می شود و به صفر استراحت می کند.

بطور موثر کاهش در فرمول بالا است.

تاخیر کردن +پهنای باند

سیستم میانه به سیستم میانه is-is یک پروتوکل کاربردی بوسیله تمهیدات شکبه مسیریاب در تعیین کردن بهتر

خلاصه طبقه ای برای طرح پروتوکل شبکه کامپیوتری و ارتباطات ، توسعه بخشی از سیستمهای باز بهم پیوسته آغاز ی وجود دارد. ان همچنین اسلوب 7لایه osi نیز نامیده می شود .

Rip(2)

Biocrwler

 Rip که از اختصار ریا ترکیب حروف اول یکسری کلمات است ، چند معنی مختلف  دارد: آن می تواند نماینده آسایش در صلح rest باشد یک اصلاحی  که اغلب روی سنگ قبرها نمایان است. در بیان بطور اصلی از اصلاح لاتین نماز میت در آرامش reguiecat in peace و در نسخه انگلیسی یک مثال تشکیلات back است . (اگر چه دو عبارت چیز یکسانی است.)

2- در bbsing وrip نماینده پروتوکل تصورمتحرک یا ripscip است. یک روش فرستادن شبیه سازی گرافیکی برروییک bbs

3- در شکبه کامپیوتری ،rip نماینده برای پروتوکل اطلاعات مسیر یابی ip,ipx و یا idp است.

4- در صنعت pre-press ، rip نماینده برای raster image processor است.

5- در تولید فایل های mp3 وriping به فرآیند برگرداندن خواندن انالوگ cd  به فایل های mp3 دیجیتال رجوع می گردد.

در امور سیاسی انگلستان ،rip نماینده فعالیت 2000 نیروهای تحقیقی تنظیم  مباحثه ای حکومت انگلستان است ،که قوانین وقواعدی برای ارتباطات قطع شده روی تمام شکبه های ارتباط از دور و پستی جدا می کند. که شامل دسترسی به ارتباط در اینترنت است .

5-                                                                 یک توزیع linux ، استرداد و باز بافت ممکن است.

7-roleplayiny در امکانات نامحدود،سیستم rpg یک کامپیوتر

Sri بین المللی : از biocrawler

Sri بین المللی یکی از موسسات تحققی بزرگترین قرار داد دنیا است. آن مثل موسسه تحقیقی استانفود درسال 1946 بوسیله منافع یکی شده با دانشگاه استانفود تاسیس گردیده شد.بعداً آن کاملا مستقل شد ومثل یک سازمان بدون سود تحت قوانین  ایالات متحده و کالیفرنیا تاسیس گردیده است.

در سال 1972 دکتر hal pauthoff یک محقق در sri ، یک سری پروتکل های مطالعه مکانیک های کوآنتوم را در فرآیندهای life به کاربرد این در برنامه ramote viewing مباحثه ای در حال حاضر نتیجه ای می دهد که به طور گزارشی قطع گردیده و غیر محرمانه و تنزل مرتبه پیدا کرد. DouglasC.Engelbart مشهورترین سازنده mouse کامپیوتری  است و همانند یک pioneer اثر متقال کامپیوتر  - انسان به طور قابل بحثی برجسته ترین دانش آموخته sri است. محققان بین المللی sri در جهان اول پیشرفت کردند و فقط تمام کامپیوترهای دیجیتال مغناطیسی ، براساس بسط وتوسعه هایی به حافظه مغناطیسی قرار گرفت.

در سال 1977 موسسه تحقیق استانفورد مثل sri بین المللی ، مشهور شد وبه طور رسمی از دانشگاه استانفورد جدا گردیداین یک واکنش وپاسخ ودیرتر از موقع به دانشجویان معترض ضد جنگ بود کسانی که باور داشتند سرمایه کار darpa sri  ضرورتا در قسمت استانفورد درترکیب نظامی – صنعتی ساخته می شد.

در طی  این کار، sri بیش از 000/10 حق و جواز ثبت شده انحصاری برای استفاده ازاختراعی در مهندسی و تکنولوژی  رااعطا کرده است. sri بین المللی تحقیق و توسعه در چند ناحیه ، انتقال داده ورهبری می کند، هردو به طور مستقل وبرای اجاره وفروش برروی تحقیق مستقل ،گزارش می دهند.curtis carlos.ph.D رئیس CEO SRI بین المللی است.

پروتوکل داتا گرام کاربر UDF یکی از پروتکل های هسته در درخواست پروتوکل اینترنت است استفاده UDP یکی از پروتوکل های هسته در ، درخواست پروتوکل اینترنت است . استفاده UDP  ، برنامه های روی کامپیوتر  شکبه را می تواند پیامهای  کوتاه مشهور مثل داتا گرام به یکدیگر را ارسال نماید. UDP  دراعتبار و گارانتی های  سفارشی  که tcp انجام می دهد فراهم نمی گردد، UDP  دراعتبار و گارانتی های سفارشی که tcp انجام می دهد، فراهم نمی گردد. داتا گرام ها ممکن است خارج از سفارش وارد شوند یا بدون توجه از دست بروند به هر حال، نتیجه می شود. که UDP  سریعتر و موثرند برای اهداف سبکه یا زمان – حساس است.

کاربردهای شبکه های معمولی و عادی که UDP استفاده میکنند  شامل سیستم Domain Name کاربردهای جریان رسانه ها ، voie ovep و مسابقات Online می شوند.

مسیر یابی معنایی : مسیر یابی معنایی یک روش مسیر یابی است. که بیشتر از توپولوژی  شبکه روی ماهیت تحقیق وپرسش متمرکز یک روش معنایی روی مسیر یابی  سنتی  را اصلاح می گردد بوسیله گره های priorisng که به طور ابتدایی در اطلاعات تهیه شده درباره انواع درباره انواع حجم ارجاع شده بوسیله تحقیق و پرسش  ، معتبر شده اند.

در توانایی جستجو برای اطلاعات روی یک  شبکه p2p به طور معنایی  در داده های نیاز به تشریح معنایی در ارتباط با آن دارند،یک حل معمولی در ارتباط با آن دارند، یک حل عمومی ، کاربرد rdfmeta-data(1) برای این هدف است داده های اسناد ضمیمه شده با rdf یک وب معنایی وسیع را تهیه می کنند که می توانست دریک مدل p2p پی ریزی  شود. یک شبکه طرح شده – اساسی p2p مثل این به طور بزرگی از مسیر یابی معنایی سود می برد مسیر یابی معنایی اساسا از دیگر تکنیک های مسیر یابی متفاوت است زیرا گره های موثر در آینده بواسطه اطمینان  دیگر گرهها در توانایی شان به پاسخ دادن به طور صحیح به یک پرسش  معین صرفنظر از وضعیت  نشان در شبکه انتخاب کرده می شوند.

آنجا چندین پروژه مختلف با یک نظر آزمایشی در قدرت مسیر یابی  معنایی آغاز گردیده است نمونه ها tempidh sibersli et wolpre, Nejdigrid(2) و wranik,stab   به طور قابل بحثی جالب ترین اینها و سیستم Remmindin است که یک الگوریتم  مسیریابی  بی معنایی پیشرفته  با مقصد شبکه های اجتماعی تقلیدی یکی می شود. به علاوه این تعداد تکنیک های پیشرفته  برای فیلترینگ همکاری یافته به طور مساوی به ranking نظیر و همتای  درون یک شبکه مسیر یابی  شده به طور معنایی قابل اجرا وعملی هستند.

Vpn چیست؟

یک شبکه اختصاصی مجازی یا vpn یک شکبه تکمیلی  کاربردی در یک بخش  سازمانی شبکه اما برای تهیه کردن نگهبانی وپوشیدگی یک شبکه خطی استجاری اختصاصی است.

مثالهای قدیمی تر frame relay و ATM می باشند اخیرا به رجوع بیشتری به تونل های ipsee بالا در اینترنت با شاید pptp با شماره گیری l2tp اتصال vpn از میان یک internetwork بخش شده رسیده است.

برای اهدفمان در این مقاله ،vpns ، شبکه های ip خواهد شد که هسته wan یک شکبه یکی شده ه تهیه کننده سرویس ، outsorce کرده است در IPVPN اتصال در میان یک شبکه IP بخش شده متعلق به تهیه کننده سرویس ، آماده گردیده می شود.

ان در BGP-MPLS اساس VPNS ثابت و معلوم خواهد شد. ما درباره خواهد شد ما درباره قدرت کافی تهیه کردن اتصال ایمن وبی خطر (وترکیب نسبتا ساده) برای هر دو in tranets extranets گفتگو خواهیم کرد.

اصلاحات واژه شناسی

Vpn: اینترنت   اتصالی داخلی با سایت یکی شود.

Extranet: vpn اتصالی سایت یاسایت های یکی شده به شرکای کاری خارجی یا کارپردازان اینترنت vpn: Extranet باز پسین ناامن و نامحفوظ است

مسیر یاب customer edge (ce) یک مسیر یاب دریک سایت   مشتری که به تهیه کنندگان سرویس متصل می شود. ( از طریق یک  یاتعداد بیشتری مسیریاب provierp.e edge

مسیر یاب هسته تهیه کننده: یک مسیریاب  در اتصال داخلی شبکه تهیه کننده سرویس به مسیر یاب pe ، اما عموما  خودش یک مسیریاب pe نیست.

مسیریاب های دخول وخروج pe : مسیریاب های pe  بوسیله  خروجی ها و ورودی یک بسته در شبکه تهیه سرویس .