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

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

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

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

 

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

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

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

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

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

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

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

اصل بهينگي

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

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

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

مسير يابي كوتاه ترين مسير

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

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

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

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

الگوريتم‌هاي متعددي براي محاسبه كوتاهترين مسيربين در گره گراف شناسايي شده‌اند يكي از اين الگوريتمهاي به ديكسترا ۱۹۹۵ نسبت داده مي‌شود. هر گره داراي برچسب هايي در پرانتز است كه فاصله آن تا گره منبع، از طريق بهترين مسير شناخته شده نيست لذا تمام گره‌ها داراي بر چسب بي نهايت هستند .با ادامه اجراي الگوريتم وپيدا شدن مسيرها، امكان دارد برچسب‌ها تغيير كنند تا مسيرهاي بهتري منعكس نمايند. برچسب ممكن است موقتي يا دائمي باشد. در آغاز ، تمام برچسب‌ها موقتي‌اند وقتي مشخص شد كه برچسبي كوتاهترين مسير بين منبع به آن گروه تمام برچسب‌ها مو قتي اندوقتي مشخص شد كه برچسبي كوتاهترين مسير بين منبع به آن گره را نمايش مي‌دهد، دائمي مي‌شود و از آن پس تغيير نمي‌كند.

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

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

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

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

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

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

الگوريتم غرق كردن

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

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

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

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

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

 

 

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

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

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

الگوريتم مسير يابي بردار فاصله به اسامي ديگر نيز خوانده مي‌شود. ازجمله الگوريتم مسير يابي بلمن –فورد و الگوريتم و الگوريتم فورد – فوركرسون كه نامگذاري آنها را نام مخترعين آنها بلمن ۱۹۷۵- فورد و فوكرسون، ۱۹۶۲ اقتباس شده است. اين الگوريتم مسير يابي ARPANET اوليه بود و تحت نام RIP در اينترنت مورد استفاده قرارگرفت.

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

 

 

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

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

اين فرآيند بازسازي در شكل ۵ آمده است بخش الف زير شبكه‌اي را نشان مي‌دهد چهار ستون اول بخش (ب) بردارهايي تاخيري را كه از همسايه هايي مسيريابJ آمده‌اند نشان مي‌دهد تاخير از A به B برابر با ۱۲ ميلي ثانيه و از A به C برابر با ۲۵ ميلي ثانيه و از A به D برابر ۴۰ ميلي ثانيه و غيره است فرض كنيد تاخيرهايي J به همسايه هايش A,H,I,A به ترتيب عبارتست از ۸و۱۰و۱۲و۶ ميلي ثانيه .

 

 

چگونگي محاسبه مسير جديد از J به G را در نظر بگيريد J مي‌داند كه مي‌تواند با ۸ ميلي ثانيه تاخير به A برسد و A با ۱۸ ميلي ثانيه به G مي‌رسد لذا J مي‌داندكه اگر بخواهد از طريق A به G برسد ۲۶ ميلي ثانيه طول مي‌كشد. به طور مشابه به تاخير رسيدن به J را در جدول ،۱۸ ميلي ثانيه ثبت مي‌كند و آن، از طريق H است محاسبه مشابهي براي تمام مقصدها صورت ميگيرد به طوري كه جدول مسير يابي جديد را به صورت آخرين به صورت اخرين ستون شكل در مي‌آيد.

 

 

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

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

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

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

اكنون وضعيت شكل ۶ (ب) را در نظر مي‌گيريم در اين شكل تمام خطوط و مسيرياب‌ها در آغاز فعال‌اند وفاصله مسير ياب‌هاي Aتا, E,D,C,B به ترتيب عبارتند از ۱و۲٫۳و۴ ناگهان A از كار مي‌افتد يا خط بين A, B قطع مي‌شود از ديد B فرقي نمي‌كند كه كداميك اتفاق افتاده است.

در مبادله اولين بسته، B چيزي از A نمي‌شنود خوشبختانه C مي‌گويد نگران نباشيد من مسيري به طول ۲ به A دارم لذا B مي‌داندكه مسير C از طريق خود B مي‌داند كه C ممكن است ده خط خروجي داشته باشد .كه هر كدام داراي مسيرهاي مستقلي به A هستند كه طول آنها ۲ است در نتيجه B فكر مي‌كند كه مي‌تواند از طريق C به A برسد با مسيرهاي به طول ۳ در مبادله اول E,D وارده‌هاي خود را براي A را بازسازي ميكنند.

در مبادله دوم C در مي‌يابدكه هريك از همسايه هايش ادعا ميكنند كه طول مسير انها را به A برابر با ۳ است يكي از آنها به طور تصادفي انتخاب مي‌كندو فاصله جديد به A را برابر با ۴ منظور مي‌كند سطر سوم از شكل ۶ الف مبادله‌هاي بعدي نتايج بقيه شكل ۶ الف را توليد ميكنند.

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

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

مسير يابي فاصله تا سال ۱۹۷۹ در ARPANET مورد استفاده قرار گرفت و از ان پس جاي خود را به مسير يابي حالت پيوند داد. و مشكل عمده موجب مرگ آن شد. يكي از اين كه مقياس تاخير، طول صف بود و هنگام انتخاب مسيرياب‌ها پهناي باند را در نظر نمي‌گرفت در آغاز تمام خطها ۵۶KBPS بودند لذا پهناي باند موضوع مهمي نبود اما وقتي بعضي از خطوط به ۲۳۵KBPS وبعضي ديگر به MBPS 55/1 تغيير يافتند عدم توجه به پهناي باند را به عنوان مقياس در نظر گرفت اما مشكل دوم نيز وجود داشت، يعني الگوريتم براي همگرا شدن به زمان زيادي نياز دارد . بي نهايت گرايي به اين دلايل الگوريتم ديگري به نام مسيريابي حالت پيوند جاي ان را گرفت اكنون شكلهاي گوناگوني از مسير يابي حالت پيوند مورد استفاده قرار ميگيرد.

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

۱-همسايه هايش را تشخيص داده و آدرس شكبه‌ها آنها را بداند.

۲-تاخير با هزينه تا همسايه هايش را اندازه گيري كند.

۳- ايجاد بسته‌اي كه اطلاعات به دست آمده از همسايه‌ها را نگهداري كند.

۴-اين بسته‌ها را به تمام مسيرياب‌ها ارسال نمايد.

۵-كوتاهترين مسير به هر مسير ديگر را محاسبه كند.

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

كسب اطلاعاتي راجع به همسايه‌ها

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

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

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

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

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

 

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

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

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

وقتي اطلاعات مورد نياز براي مبادله جمع آوري شد قدم بعدي هر مسيرياب اين است كه بسته‌اي حاوي تمام داده‌ها ايجاد كند. در ابتداي هر بسته،هويت فرستنده قرار مي‌گيرد، سپس شماره ترتيب و سن قرار دارد و تعدادي از همسايه‌ها به دنبال آن قرار مي‌گيرند راجع به سن قرار دارد در ادامه توضيح داده خواهد شد. براي هر همسايه ، تاخير در خطوط نشان داده شده‌اند بسته حالت ۱بوندمتناظر با هر شش مسيريابدر شكل ۹ (ب) آمده است.

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

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

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

ابتدا، الگوريتم توزيع اوليه رامورد بحث قرار مي‌دهيم. سپس اصلاحاتي را انجام دهيم ايده اصلي ، استفاده از الگوريتم غرق كردن براي توزيع بسته‌هاي حالت پيوند است براي كترل غرق كردن هر بسته حاوي شماره ترتيبي است كه با ارسال هر بسته، يك واحد افزايش مي‌يابد.وقتي بسته حالت پيوند ديگري دريافت مي‌شود ،با ليستي از بسته‌ها كه تاكنون ديده شده‌اند مقايسه مي‌شود اگر بسته‌اي دريافت شود. به هر خطي به جز خطي كه از ان آمده است، توزيع مي‌گردد.و اگر تكراري باشد،صرف نظر مي‌شوداگر بسته‌اي دريافت شود كه شماره ترتيب آن كوچك تر از بالاترين شماره‌اي باشد كه تاكنون مشاهده شده است به دليل كهنه بودن رد مي‌شود. زير مسيريابداده‌ها جديدي دارد.اين الگوريتم داراي مشكلات خاصي است اما اين مشكلات قابل كنترل‌اند يكي اين كه اگر شماره‌ها تمام شدند، بسته هايي بعدي از اول شماره گذاري شوند راه حل اين مشكل، استفاده از شماره ترتيب ۳۲ بيتي ۳۲ بيتي است اگر در هر دقيقه يك بسته حالت پيوند ايجاد شود.۱۳۷سال طول مي‌كشد تا چرخش صورت مي‌گيرد. لذا از اين حالت مي‌توان صرف نظر كرد.

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

سوم اينكه اگر شماره ترتيب خراب شود و ۵۴۰،۶۵ به جاي ۴(خطاي يك بيتي ) دريافت شود ، بسته‌هاي ۵ تا ۵۴۰،۶۵ به علت كهنگي رد مي‌شوند زيرا فرض مي‌شود كه شماره ترتيب بايد ۵۴۰،۶۵ باشد.

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

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

ساختمان داده‌اي كه مسيريابB براي زير شبكه شكل ۱۳-۵ الف استفاده مي‌كند در شكل ۱۰ آمده است هر سطر ، متناظر با بسته حالت پيوندي است كه از راهع رسيد و هنوز به طور كامل پردازش نشده است. جايي كه بسته از انجا ارسال شد و شماره ترتيب وسن ، داده‌هاي ان درجدول ذخيره مي‌شود به علاوه نشانگرهاي ارسالي و اعلام وصول براي هر سه خط B وجود دارند به ترتيب به F,C,A معناي نشانگرهاي ارسالي اين است كه بسته بايد به خط تعيين شده ارسال گرددو معناي نشانگرهاي اعلام وصول اين است كه بايد در آنجااعلام وصول شوند.

در شكل ۱۰ بسته حالت پيوند مستقيما از A رسيده است. لذا همانطور كه با بيت‌هاي نشانگر نشان داده شده است بايد به C, F ارسال شود. و به A اعلام وصول گردد. به طور مشابه بسته‌اي از F بايد به A و C ارسال شود و به F اعلام وصول گردد.

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

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

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

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

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

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

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

مسير يابي حالت پيوند در شبكه‌هاي واقعي به طور گسترده به كار رفته است ، لذا مثال هايي در رابطه با آن ارائه شده اند، قرار داد 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 وجود ندارد اين امتياز در محيطهاي قرارداد چندگانه بزرگ ،ارزشمند است.

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

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

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

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

شكل ۱۱ يك مثال كمي از مسيريابي در سلسله مراتب دو سطحي با پنج ناحيه را نشان مي‌دهد. جدول مسيريابي كامل مربوط به مسيرياب۱A داراي ۱۷ وارده است(َ(شكل ۱۱)(ب) وقتي مسيريابي‌هاي محلي،وارده‌هاي ،وجود دارد،اما ناحيه‌هاي ديگر در يك مسير باب جمع شده‌اند لذا كل ترافيك ناحيه ۲ از طريق خط ۱B-2A منتقل مي‌شود اما بقيه ترافيك از راه دور ،از طريق خط ۱C-3B منتقل خواهد شد مسير يابي‌ها در هر ناحيه،صرفه جويي در فضاي جدول بيشتر مي‌شود.

با اين صرف جويي ،بايد تاواني را پس داد و آن، افزايش طول مسير است به عنوان بهترين مسير از ۱A به SC از طريق ناحيه ۲ است ،اما در مسير يابي سلسله مراتبي ،۵ از طريق ناحيه ۳ منتقل مي‌شود زيرا اين كار براي اغلب مقصدها در ناحيه پنج بهتر است .

 

وقتي شبكه منفردي بسيار بزرگ مي‌شود اين سوال مطرح است: سلسله مراتب چند سطح بايد داشته باشد؟ بعنوان مثال زير شبكه‌اي با ۷۲۰ مسيرياب را در نظر بگيريد. اگر سلسله مراتبي وجود نداشته باشد، هر مسيرياب به ۷۲ وارده جدول نياز دارد اگر زير شبكه به ۲۴ ناحيه ۳۰ مسيريابي تقسيم شود هر مسيرياب نيازمند ۳۰ وارده محلي و ۲۳ وارده راه دور است كه مجموع آن ۵۳ وارده است. اگر سلسله مراتب سه سطحي انتخاب شود، با هشت دسته كه هر كدام حاوي ۹ ناحيه از مسيرياب‌ها باشند هر مسيرياب براي مسيريابي محلي به ۱۰ وارده نياز دارد و براي مسيريابي به ساير نواحي در دسته خود به ۸ وارده نياز دارد و براي خوشه‌هاي راه دور به ۷ وراده نياز دارد كه در مجموع برابر با ۲۵ است. كامون و كلينراك (۱۹۷۹) كشف كردند كه بهترين تعداد سطوح در زير شبكه‌اي با N ln است كه به ازا هر مسيرياب به N ln وارده نياز دارد. آنها همچنين نشان دادند كه افزايش ميانگين طول مسير در اثر مسيريابي سلسله مراتبي اندك است و اغلب قابل قبول خواهد بود.

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

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

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

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

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

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

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

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

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

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

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

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

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

براي مسيريابي چند پخشي، هر مسيرياب، درخت پوشايي را ايجاد مي‌كند كه تمام مسيريابهاي موجود در زير شبكه را در بر گيرد. بعنوان مثال در شكل ۱۳ (الف) زير شبكه‌اي با دو گروه ۱ و ۲ وجود دارد. بعضي از مسيريابها به ميزبانهايي دست يافتند كه متعلق به يك يا هر دو گروه است (همانطور كه در شكل آمده است). درخت پوشاي مربوط به مسيرياب سمت چپ، در شكل ۱۳ (ب) آمده است.

وقتي فرايندي بسته چند پخشي را به گروهي مي‌فرستد، اولين مسيرياب، درخت پوشاي خود را بررسي كرده آن را هرس مي‌كند. براي اين كار تمام خطوطي را كه به ميزبانهايي مي‌روند كه عضو اين گروه نيستند حذف مي‌كند. در مثال مورد نظر ما شكل ۱۳ (ج) درخت پوشاي هرس شده مربوط به گروه ۱ را نشان مي‌دهد. شكل ۱۳ (د) درخت پوشاي هرس شده مربوط به گروه ۲ را نشان مي‌دهد. بسته‌هاي چند بخضي فقط از طريق درخت پوشاي مناسبي ارسال مي‌گردند.

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

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

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

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

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

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

مدل مياني كه طراحان از آن استفاده مي‌كنند در شكل ۱۴ آمده است در اينجا يك شبكه گسترده وجود دارد كه حاوي مسيريابها و ميزبانها است. شبكه‌هاي محلي و شهري و سلول‌هاي بي سيم به اين شبكه گسترده متصل‌اند.

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

 

فرض مي‌شود تمام ميزبانها موقعيت داخلي ثابتي داشته باشند كه هرگز تغيير نكند. ميزبانها آدرس داخلي ثابتي نيز دارند كه محل آنها را مشخص مي‌كنداين حالت را با شماره تلفن ۵۵۵۱۲۱۲-۲۱۲-۱ مقايسه كنيد كه نشان دهنده ايالات متحده (كد كشور۱) و جزيره مان هاتان (۲۱۲) است. هدف مسيريابي در سيستمي با ميزبانهاي سيار، عبارت است از: ارسال بسته‌ها به ميزباهاي سيار به كمك آدرسهاي داخلي آنها، و خواندن بسته‌ها توسط ميزبانها در هر جايي كه هستند.

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

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

  1. هر نمايندگي خارجي به طور تناوبي بسته‌اي را پخش مي‌كن تا وجود و آدرس خود را اعلام كند. ميزبان سيار تازه وارد ممكن است منتظر يكي از اين پيامها باشد اما اگر در مدت معدين چنين پيامي نرسد، ميزبان سيار مي‌تواند بسته‌اي را پخش كند و بگويد آيا هيچ نمايندگاي خارجي وجود دارد؟
  2. ميزبان سيار، با نمايندگي خارجي ثبت مي‌شود براي اين كار آدرس داخلي خود آدرس لايه پيونده داده فعلي، و اطلاعات سري ديگر را ارائه مي‌كند.
  3. نمايندگي خارجي با نمايندگي داخلي ميزبان سيار تماس برقرار مي‌كند و مي‌گويد يكي از ميزبانهاي شما در اين جاست، پيامي از نمايندگي خارجي به نمايندگي داخلي، حاوي آدرس شبكه نمايندگي خارجي است. همچنين حاوي اطلاعات سري است تا نماينگي داخلي را متقاعد كند كه ميزبان سيار واقعا وجود دارد.
  4. نمايندگي داخلي اطلاعات سري را كه حاوي مهر زمان است، بررسي مي‌كند تا ثابت كند در چند ثانيه قبل توليد شده است. اگر راضي باشد، به نمايندگي خارجي مي‌گويد كه پيشروي نمايد.
  5. وقتي نمايندگي خارجي اعلام وصولي را از نمايندگي داخلي دريافت مي‌كند يك وارده در جدول خود ايجاد مي‌نمايد و اطلاع مي‌دهد كه ميزبان سيار ثبت شده است.

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

وقتي بسته‌اي به ميزبان ارسال مي‌گردد به شبكه محلي داخلي كاربر هدايت مي‌شود زيرا چيزي است كه آدرس، انجام آن را مي‌طلبد، مانند آنچه كه در مرحله ۱ از شكل ۱۵ نشان داده شده است اينجا فرسنتند در شهر شمال غربي سيتل مي‌خواهد بسته‌اي را از طريق ايالات متحده در نيويورك به يك ميزبان بفرستد. بسته‌هاي ارسال شده به ميزبان سيار در LAN داخلي خود در نيويورك، توسط نمايندگي داخلي متوقف مي‌شود. سپس نمايندگي داخل، محل جديد (موقتي) ميزبان سيار را جست و جو مي‌كند و آدرس نمايندگي خارجي را مي‌يابد كه ميزبان سيار را جست وجو مي‌كند و آدرس نمايندگي خارجي را مي‌يابد كه ميزبان سيار را اداره مي‌كند.

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

دوم اينكه نمايندگي داخلي به فرستنده مي‌گويد از اين پس بسته‌ها را با قراردادن آنها در فيلد بار مفيد بسته‌هايي كه صريحاً به نمايندگي خارجي آدرس دهي مي‌شوند، به ميزبان سيار ارسال نمايد (به جاي اينكه آنها را به آدرس داخل كاربر سيال ارسال كند (مرحله ۳) اكنون بسته‌هاي بعدي مي‌توانند مستقيما از طريق نمايندگي خارجي (مرحله ۴) به ميزبان هدايت شوند (با ناديده گرفتن موقعيت داخلي).

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

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

مسيريابي در شبكه‌هاي موقتي

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

  1. وسايل نقليه نظامي در ميدان جنگ كه هيچ ساختماني وجود ندارد
  2. ناوگان كشتي‌ها در دريا
  3. كاركنان اضطراري در هنگام وقوع زلزله كه ساختمانها را خراب كرده است
  4. گردهمايي افرادي با كامپيوترهاي كيفي در منطقه‌اي كه فاقد۱۱ است.

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

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

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

كشف مسير

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

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

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

شمارنده جهش شماره ترتيب مقصد شماره ترتيب منبع آدرس مقصد شناسه تقاضا آدرس منبع

 

 

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

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

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

  1. جفت (شناسه تقاضا و آدرس منبع) در يك جدول سابقه محلي جست و جو مي شود تا مشخص شود آيا اين درخواست قبلا ديده و پردازش شد يا خير. اگر تكراري باشد، ناديده گرفته مي شود و پردازش متوقف مي گردد اگر تكراري نباشد اين جفت در جدول سابقه قرار مي گيرد و پردازش ادامه مي يابد.
  2. گيرنده مقصد را در جدول مسير خود جست و جو مي كند اگر مسير تازه اي به مقصد شناخته شود. بسته ROUTE REPLY به منبع ارسال مي شود تا به آن بگويد چگونه به مقصد برسد. معناي مسير تازه اين است كه شماره ترتيب مقصد كه در جدول مسيريابي ذخيره شده است بزرگتر يا مساوي شماره ترتيب مقصد موجود در بسته ROUTE REQUEST است. اگر كمتر باشد مسير ذخيره شده قديمي تر از مسير قبلي است كه منبع براي مقصد داشته است در نتيجه مرحله ۳ اجرا مي شود.
  3. چون گيرنده مسير تازه اي به مقصد نمي رساند به فيلد شمارنده جهش يك واحد اضافه مي كند و بسته ROUTE REQUEST را پخش مي كند داده ها را نيز از بسته استخراج و آن را بعنوان وارده جديد در جدول مسير معكوس خود ذخيره مي كند اين اطلاعات براي ساختن مسير معكوس به كار مي روند لذا پاسخ مي تواند بعدا به منبع برسد. فلشها در شكل ۱۶ براي ساخت مسر معكوس به كار مي روند براي وارده مربوط به مسير معكوس جديدي كه ساخته شد، تايمري شروع به كار مي كند وقتي تايمر از كار افتاد وارده حذف مي شود.

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

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

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

  1. هيچ مسيري به I شناخته نشده باشد
  2. شماره ترتيب مربوط به I در بسته ROUTE REPLY بزرگتر از مقدار موجود در جدول مسيريابي است
  3. شماره‌هاي ترتيب برابرند ولي مسير جديد كوتاه تر است

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

لذا فرايند كشف مسير به اين صورت اصلاح مي‌شود. براي يافتن مقصد، فرستنده يك بسته ROUTE REPLY را مي‌فرستد كه طول عمر آن ۱ است. اگر در مدت زمان معقولي پاسخ دريافت نشود، بسته ROUTE REPLY ديگري ارسال مي‌شود. اين بار طول عمر برابر با ۲ خواهد بود. دفعات بعد طول عمر برابر با ۳ و ۴ و ۵ و غيره خواهد شد به اين ترتيب جست و جو به طور محلي انجام مي‌شودو به طور فزاينده فراگيرتر مي‌شود.

نگهداري مسير

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

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

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

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

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

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

جست و جوي گره در شبكه‌هاي نظير به نظير

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

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

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

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

الگوريتم‌هاي متعددي براي حل اين مسئله ارائه شدند. الگوريتم كورد (دابك و همكاران، ۲۰۰۱) را بررسي مي‌كنيم. سيستم كورد از چندين كاربر تشكيل شده است كه هركدام داراي چندين ركورد ذخيره شده هستند و آمادگي دارند كه قطعاتي از ايندكس را براي استفاده ديگران ذخيره كنند. هر گره كاربر، داراي يك آدرس IP است كه مي‌تواند با استفاده از تابع درهم سازي، hash به يك عدد m بيتي درهم سازي شود. كورد از SHA-1 براي تابع hash استفاده كرد. SHA-1 در رمز نگاري استفاده مي‌شود كه در فصل ۸ بحث مي‌شود. در حال حاضر مي‌گوييم تابعي است كه يك رشته بيتي طول متغير را به عنوان آرگومان مي‌گيرد و يك عدد تصادفي ۱۶۰ بيتي را توليد مي‌كند. لذا مي‌توانيم هر آدرس IP را به عدد ۱۶۰ بيتي تبديل كنيم كه نامش شناسه گره است.

از نظر مفهومي، كل ۲ شناسه گره به ترتيب صعودي در يك دايره بزرگ چيده شدند. بعضي از آن‌ها متناظر با گره‌هاي كاربران هستند، ولي اغلب آن‌ها اين طور نيستند. در شكل ۲۴-۵ (الف) دايره شناسه گره را براي ؟؟؟ داديم (فعلاً كمان‌هاي وسط را حذف كرديم). در اين مثال،گره هايي با شناسه ۲۰،۱۵،۱۲،۷،۴،۱ ،۲۷

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

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

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

اگر بعداً كاربري بخواهد name را جست و جو كند، آن را درهم سازي مي‌كند تا كليد را به دست آورد و سپس با استفاده از successor(key) آدرس IP گره‌اي را مي‌يابد كه دوتايي‌هاي ايندكس آن را ذخيره كرده است. مرحله اول ساده است ولي مرحله دوم ساده نيست. براي اين كه بتوان آدرس IP گره متناظر با كليد خاصي را پيدا كرد، هر گره بايد ساختمان داده هايي را به منظور سرپرستي ذخيره كند. يكي از اين‌ها آدرس IP گره جانشين آن در دايره شناسه گره است. به عنوان مثال، در شكل ۲۴-۵، گره جانشين ۴، و گره ۱۲ گره جانشين ۷ است.

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

به عنوان اولين بهينه سازي، هر گره مي‌توانست آدرس‌هاي IP گره‌هاي جانشين و پيشين را نگهداري كند و در نتيجه تقاضاها هم در جهت عقربه‌هاي ساعت و هم در جهت خلاف عقربه‌هاي ساعت (بسته به اين كه كدام مسير كوتاه تر است) ارسال شوند. به عنوان مثال، گره ۷ در شكل ۲۴-۵ مي‌توانست براي يافتن شناسه گره ۱۰ در جهت عقربه‌هاي ساعت و براي يافتن شناسه گره ۳ در خلاف جهت عقربه‌هاي ساعت حركت كند.

حتي حركت در دو جهت نيز با جست و جوي خطي در سيستم نظير به نظير كارآمد نيست، زيرا ميانگين گره‌هاي مورد نياز در هر جست و جو، است. براي افزايش سرعت جست و جو، هر گروه جدولي به نام جدول انگشت دارد. جدول انگشت m وارده دارد كه انديس آن از ۰ تا m-1 است و هر كدام به يك گره واقعي اشاره مي‌كنند. هر وارده داراي دو فيلد است: start و آدرس IP مربوط به successor(start) . اين جدول‌ها در شكل ۲۴-۵ (ب) آمده اند. مقادير فيلدهاي مربوط به وارده i در گره k به صورت زير محاسبه مي‌شود،

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

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

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

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

به عنوان اولين مثال، جست و جوي key=3 را در گره ۱ در نظر مي‌گيريم. چ.ن گره ۱ مي‌داند گره ۳ بين آن و جانشين آن يعني ۴ قرار دارد، گره مطلوب ۴ است و جست وجو خاتمه مي‌يابد و آدرس IP گره ۴ برگردانده مي‌شود. به عنوان دومين مثال، جست و جوي key=14 را در گره ۱ در نظر مي‌گيريم. چون ۱۴ بين ۱ و۴ نيست، از جدول انگشت استفاده مي‌شود. نزديك ترين گره پيشين ۱۴، گره ۹ است. لذا تقاضا به سمت آدرس IP وارده ۹، يعني گره ۱۲ پيش مي‌رود. گره ۱۲ مي‌بيند كه ۱۴ بين آن جانشين آن، يعني ۱۵ قرار دارد و در نتيجه آدرس IP گره ۱۵ برگردانده مي‌شود.

به عنوان سومين مثال، جست وجوي key=16 را در گره ۱ در نظر بگيريد. تقاضا به گره ۱۲ ارسال ميشود. ولي گره ۱۲ پاسخ را نمي‌داند. نزديك ترين گره قبل از ۱۶ جست و جو مي‌كند و ۱۴ را مي‌يابد كه آدرس IP گره ۱۵ را ارائه مي‌كند. سپس تقاضا به اين جا ارسال مي‌شود. گره ۱۵ مي‌بيند كه ۱۶ بين آن و جانشين يعني ۲۰ قرار دارد و در نتيجه آدرس IP گره ۲۰ را برمي گرداند و در مسيرش به گره ۱ برمي گردد.

چون گره‌ها در هر زمان اضافه و كم مي‌شوند الگوريتم كورد مي‌باست اين عمليات را اداره كند. فرض مي‌كنيم وقتي سيستم شروع به كاركرد به اندازه كافي كوچك بود و گره‌ها مي‌توانستد مستقيما اطلاعات را مبادله كنند و اولين دايره و جدولهاي انگشت را بسازند. از اين پس نياز به روبه خودكار است وقتي گره جديدي مثل r مي‌خواهد اضافه شود، بايد با يك گره موجود تماس بگيرد و از او بخواهد آدرس IP مربوط به successor(r) را برايش جست و جو كند. سپس گره جديد از successor(r) مي‌خواهد گره پيشين آن را بيابد. سپس گره جديد از هر دو مي‌خواهد r را بين آنها در دايره اضافه كند. بعنوان مثال اگر گره ۲۴ در شكل ۲۰ بخواهد اضافه شود از هر گره‌اي مي‌خواهد successor(24) را بيابد كه گره ۲۷ است. پس از گره ۲۷ گره پيشين آن را مي‌پرسد كه ۲۰ است. سپس حضورش را به هر دو اعلان مي‌كند. ۲۰ از ۲۴ به عنوان جانشين خود و ۲۷ از ۲۴ به عنوان پيشين خود استفاده مي‌كند. علاوه بر اين گره ۲۷ اين كليدها را در بازه ۲۴-۲۱ تحويل مي‌دهد كه اكنون متعلق به ۲۴ هستند. اكنون ۲۴ اضافه شده است.

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

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

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

الگوريتم كنترل ازدحام

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

 

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

 

 

 

اگر حافظه كافي براي ذخيره آنها وجود نداشته باشد، بسته‌ها از بين مي‌روند افزودن حافظه ممكن است كمك كند، اما ناگل (۱۹۸۷) دريافت كه اگر مسيرياب‌ها حافظه‌هاي زيادي داشته باشند، ازدحام بيشتر مي‌شود، زيرا در اين صورت بسته‌ها با رسيدن به مقصد را افزايش مي‌دهند.

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

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

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

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

از طرف ديگر شبكه ذخيره و ارسالي با خطوط ۱Mbps و ۱۰۰۰ كامپيوتر بزرگ را در نظر بگيريد نيمي از آنها سعي مي‌كنند فايلهايي را با سرعت ۱۰۰kbps به نيمي ديگر بفرستند. در اينجا مشكل اين نيست كه فرستنده سريع گيرنده كند را تحت فشار قراتر مي‌دهد بلكه كنترل ترافليك از توان شبكه بيشتر است.

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

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

اصول كلي كنترل ازدحام

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

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

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

  1. نظارت بر سيستم جهت تشخيص زمان و مكان وقوع ازدحام.
  2. انتقال اين اطلاعات به جايي كه فعاليت بايد انجام گيرد.
  3. تنظيم عمل سيستم براي برطرف كردن مشكل

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

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

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

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

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

الگوريتم‌هاي كنترل ازدحام متعددي شناخته شده اند. براي سازماندهي معقول آنها، يانگ وردي ۱۹۹۵ الگوريتم ‌هاي كنترل شده ازدحام را طبقه بندي كردند . انها ابتدا الگوريتم‌ها ر براساس حلقه بسته يا حلقه باز تقسيم بندي نمودند، سپس الگوريتمهاي حلقه باز ر براساس اين كه درمنبع عمل مي‌كنند يا در مقصد تقسيم بندي ، الگوريتمهاي حلقه بسته نيزبه دو دسته تقسيم شدند. با خوردي صريح و باز خوردي ضمني در الگوريتمهاي ضمني، منبع با مشاهدات محلي ،مثل زمان مورد نياز براي برگشت اعلام وصول ، به وجود ازدحام پي مي‌برد.

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

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

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

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

 

مطالعه روشهاي كنترل ازدحام را با نگاهي به سيستم‌هاي حلقه باز شروع مي‌كنيم. اين سيستم‌ها طوري طراحي شدند كه از بروز ازدحام جلوگيري كنند. براي اين منظور از سياست‌هاي مختلفي استفاده مي‌شود. در شكل ۲۱ سياست‌هاي مختلفي از لايه‌هاي پيونده داده ها، شبكه و انتقال را مشاهده مي‌كنيم كه بر ازدحام موثرند (جين ، ۱۹۹۰).

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

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

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

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

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

كنترل ازدحام در زيرشبكه‌هاي مدار مجازي

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

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

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

شكل۲

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

اين نوع رزرو سازي يا مي‌تواند هميشه بعنوان يك عمليات استاندارد انجام شود و يا در صورت وجود ازدحام انجام گيرد. اگر‌اي كار به طور هميشگي انجام شود منابع را به هدر مي‌دهد. اگر شش مدار مجاز كه مي‌تواند از ۱۰ Mpbs استفاده كند. همگي از يك خط ۶Mpbs فيزيكي عبور كنند، بايد خط را به عنوان خط پر علامت گذاري كرد. ولي احتمال اينكه هر شش مدار مجازي همزمان عمل انتقال را انجام دهند كم است. در نتيجه هزينه كنترل ازدحام پهناي باند مصرف نشده است.

 

 

كنترل ازدحام در زيرشبكه‌هاي داده گرام

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

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

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

بيت اخطار

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

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

بسته‌هاي چوك

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

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

ميزبانها مي‌توانند با تنظيم پارامترهاي خود مثل اندازه پنجره، ترافيك را كاهش دهند، اولين بسته چوك موجب مي‌شود تا سرعت به اندازه ۵۰% سرعت قبلي كاهش يابد و بسته چوك بعدي موجب ۲۵% كاهش مي‌شود و غيره. افزايشها به تدريج انجام مي‌شود تا از وقوع سريع ازدحام جلوگيري به عمل آيد.

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

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

بسته‌هاي چوك مسير به مسير

در سرعتهاي زياد و مسافتهاي طولاني، ارسال بسته چوك به ميزبانهاي منبع كارايي خوبي ندارد، زيرا واكنش كند است. بعنوان مثال ميزباني را در سان‌فرانسيسكو (مسيرياب A در شكل ۲۳) در نظر بگيريد ك ترافيكي را به ميزباني در نيويورك (مسيرياب D در شكل ۲۳) با سرعت ۱۵۵ Mpbs مي‌فرستد. اگر بافر ميزبان نيويورك شروع به پر شدن كند، ۳۰ ميلي ثانيه طول مي‌كشد تا بسته چوك به سان فرانسسيكو برسد و به آن بگويد كه كندتر عمل كند. انتشار بسته چوك در شكل ۲۳- الف به صورت مراحل دوم، سوم، چهارم نشان داده شده است. در آن ۳۰ ميلي ثانيه‌ها، ۶/۴ مگابيت ديگر ارسال خواهند شد. حتي اگر ميزبان در سانفرانسيسكو كاملا از كار افتد، ۶/۴ مگابيت موجود در مجرا، به انتقال ادامه مي‌دهد تا تمام شود. فقط در نمودار هفتم در شكل ۲۳- الف مسيرياب نيويورك جريان كندتري را مشاهده مي‌كند.

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

حاصل كار الگوي مسير به مسير اين است كه فورا در نقطه ازدحام تسكين ايجاد مي‌شود و هزينه اش اين است كه فضاي بافر بيشتري بايد اختصاص داده شود در اين روش ازدحام، بدون آسيب ديدن بسته اي، از بين مي‌رود. اين ايده با تفضيل بيشتر و نتايج شبيه سازي در (ميشرا و كاناكيا، ۱۹۹۲) تشريح شده است.

تخليه بار

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

مسيريابي كه در بسته‌هاي زيادي غرق شده است بسته‌ها را به طور تصادفي انتخاب و حذف مي‌كند. اما بهتر از اين مي‌تواند كار كند. بسته هايي كه بايد حذف شوند به برنامه كاربرديي كه در آن اجرا مي‌شوند، بستگي دارد. براي انتقال فايل بسته قديمي ارزشمندتر از بسته جديد است، زيرا حذف بسته ۶ و نگهداري بسته از بين ۱۰ بسته شكافي در گيرنده به و جود مي‌آورد و موجب مي‌شود بسته‌هاي ۶ تا ۱۰ دوباره ارسال شوند. اين در صورتي است كه گيرنده معمولا بسته‌هاي خارج از ترتيب را به دور بريزد. در فايل ۱۲ بسته‌اي حذف بسته ۶ ممكن است منجر به ارسال مجدد ۷ تا ۱۲ شود، در حالي كه حذف ۱۰ ممكن است نياز به ارسال دوباره ۱۰ تا ۱۲ باشد. بر عكس براي چند رسانه‌اي بسته جديد مهمتر از بسته قديمي است. سياست قبلي (قديمي بهتر از جديد است) معمولا شراب نام دارد و سياست بعدي (جديد بهتر از قديم است) معمولا شير نام دارد.

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

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

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

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

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

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

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

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

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

كنترل لرزش

براي كاربردهايي مثل صوت و ويديو، تا زماني كه زمان انتقال ثابت است مهم نيست كه بسته‌اي پس از ۲۰ ميلي ثانيه برسد يا ۳۰ ميلي ثانيه نوسان در زمانهاي رسيدن بسته، لرزش نام دارد. لرزش زياد مثلا وقتي كه بسته‌اي ۲۰ ميلي ثانيه بعد و بسته ديگر ۳۰ثانيه بعد برسد از كيفيت صوت و فيلم مي‌كاهد. لرزش در شلك ۲۵ نشان داده شده است برعكس اگر ۹۹% از بسته‌ها با تاخيري در بازه ۵/۲۴ تا ۵/۲۵ ميلي ثانيه برسند، مي‌تواند قابل قبول باشد. بازه انتخابي بايد امكان پذير باشد. بايد زمان انتقال سرعت نور و كمترين تاخير از طريق مسيرياب در نظر گرفته شود و بعضي از تاخيرهاي اجتناب ناپذير و ناچيز را ناديده گرفت.

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

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

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

كيفيت خدمات

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

‌مسير يابي منبع ديناميك (۱)

    پروتكل 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 است اين نسخه پروتوكل ، نسخه ۴ را انتقال داده ميكندو ipv6 جانشين ipv4 در نظر گرفته مي شود در اينترنت تدريجا آدرسها را تمام مي كند و ipv6 ، منبع ۱۲۸-bit و عنوان مقصدها رادارد ، بيشتر ازعناوين آدرس ipv4 يا منبع ۳۲-bit عناوين فراهم ميكند. نسخه ۵براي يك جريان پروتوكل هاي آزمايشي تعيين كرده شده اند ديگر شماره نسخه معمولا براي پروتكل هاي آزمايشي تعيين كرده شده اند اما بطور وسيعي استفاده نشده اند. 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 را جابجاد مي كند. متعاقبا اضافه كردن لبه ها بايستي به اندازه دياگرام موجود طراحي مي شوند. شكل ۵۴-۵ : يافتن يك راه درميان يك مسير پرپيچ و خم

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

كاربرد حداقل فاصله 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:

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

مسير يابي Guntella

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

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

جستجو كردن در شبكه براي يك منبع تا حدي كاربرد يك 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 وجود دارد و همچنين به طور نسبي پيچيدگي كم دارد.

فوايد:

  • داده هاي عمومي در كل سيستم تكرار مي شود.
  • داده ها به طور بي نام و مستعارانه و به طور آزاد پخش كرده ميشود، اصول و عقايد كلي را در سيستم در هدف دارد.
  • الگوريتم مسيريابي به وفق دادن و بهبودي سودمند به طور اضافه طراحي كرده شد.

مضرات:

  • مردم به بخشيدن و اهداء بخشي از hard-drive شان به سيستم مخصوصاً دو دل و مردد هستند زماني كه آن مي توانست در انداختن اطلاعات استفاده شود. آنها پسند و موافقت نمي كنند.
  • شبكه به سادگي قابل جستجو نيست، كاربر نياز به شناخت كليد پيدا كردن يك فايل دارد.
  • شبكه كند و آهسته است. همانطور كه داده ها بايد در بين تمام گره ها (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 است.

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

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

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

تست تركيبي از ۲۰ وظيفه است كه شامل سفرهايي بين اثرات متقابل در منطقه palo Alto مي باشد. در جبران كردن براي فقدان تاثير بر يكديگر، ما ۴ مسير براي هر وظيفه در عوض آن دو توليد كرديم. از زماني كه ما هيچ فرصتي در ساخت مدل هاي كاربر نداشتيم، ما به ترتيب بردارهاي weight اكتشافي را با يك weight واحد براي يك صفت و صفر براي استراحت، ايجاد مسيرهاي بهينه براي زمان، فاصله، تعداد پيچش ها را به كار مي برديم. ما ۴ مسير ار برچسب دار به طور تصادفي بين A,D روي يك نقشه palo Alto طرح ريزي كرديم. شكل ۵ مثالي از يكي ار برنامه ها را نشان مي دهد و خودش ۴ مسير را انتخاب مي كند.

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

شكل ۶: ميزان تبادلات براي ۳ صفت راجع به مسافت، محاسبه از تمام داده ها براي هر موضوع است. ارزشهاي مثبت بالا براي يك مسافتي اشاره مي كند كه كوتاهترين مسافت است و كم اهميت تر از كاهش است كه نسبت داده مي شود، ارزشهاي نزديك صفر اشاره مي كند كه فاصله كوتاهتر مهم تر است و ارزش هاي منفي بالا اشاره مي كند كه مسافت طولاني تر قابل ترجيح تر است.

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

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

Startkey word يكي از ۱- net –مسير A به يك شبكه

۲- 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 با ۵ متريك مختلف با هر مسير مربوط مي باشد.

تاخير كردن Dekay

پهناي باند Bandwidth

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

MTV

Load

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

K4)}+قابليت اعتماد K3)}*{(k6/تاخيركردن *)(۲۵۶-Load)+( K2)* پهناي باند( K1) +*پهناي باند( {

جايي كه ثابت هاي مختلف(k1 تا k5 ) مي توانند بوسيله كاربر در ايجاد حركات مختلف set كرده شوند اگر k set به صفر است در term استفاده كرده نمي شود كسري براي k1, و۳ k به ۱ set مي شود و به صفر استراحت مي كند.

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

تاخير كردن +پهناي باند

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

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

Rip(2)

Biocrwler

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

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

۳- در شكبه كامپيوتري ،rip نماينده براي پروتوكل اطلاعات مسير يابي ip,ipx و يا idp است.

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

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

در امور سياسي انگلستان ،rip نماينده فعاليت ۲۰۰۰ نيروهاي تحقيقي تنظيم مباحثه اي حكومت انگلستان است ،كه قوانين وقواعدي براي ارتباطات قطع شده روي تمام شكبه هاي ارتباط از دور و پستي جدا مي كند. كه شامل دسترسي به ارتباط در اينترنت است .

  • يك توزيع linux ، استرداد و باز بافت ممكن است.

۷-roleplayiny در امكانات نامحدود،سيستم rpg يك كامپيوتر

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

Sri بين المللي يكي از موسسات تحققي بزرگترين قرار داد دنيا است. آن مثل موسسه تحقيقي استانفود درسال ۱۹۴۶ بوسيله منافع يكي شده با دانشگاه استانفود تاسيس گرديده شد.بعداً آن كاملا مستقل شد ومثل يك سازمان بدون سود تحت قوانين ايالات متحده و كاليفرنيا تاسيس گرديده است.

در سال ۱۹۷۲ دكتر hal pauthoff يك محقق در sri ، يك سري پروتكل هاي مطالعه مكانيك هاي كوآنتوم را در فرآيندهاي life به كاربرد اين در برنامه ramote viewing مباحثه اي در حال حاضر نتيجه اي مي دهد كه به طور گزارشي قطع گرديده و غير محرمانه و تنزل مرتبه پيدا كرد. DouglasC.Engelbart مشهورترين سازنده mouse كامپيوتري است و همانند يك pioneer اثر متقال كامپيوتر – انسان به طور قابل بحثي برجسته ترين دانش آموخته sri است. محققان بين المللي sri در جهان اول پيشرفت كردند و فقط تمام كامپيوترهاي ديجيتال مغناطيسي ، براساس بسط وتوسعه هايي به حافظه مغناطيسي قرار گرفت.

در سال ۱۹۷۷ موسسه تحقيق استانفورد مثل sri بين المللي ، مشهور شد وبه طور رسمي از دانشگاه استانفورد جدا گرديداين يك واكنش وپاسخ وديرتر از موقع به دانشجويان معترض ضد جنگ بود كساني كه باور داشتند سرمايه كار darpa sri ضرورتا در قسمت استانفورد درتركيب نظامي – صنعتي ساخته مي شد.

در طي اين كار، sri بيش از ۰۰۰/۱۰ حق و جواز ثبت شده انحصاري براي استفاده ازاختراعي در مهندسي و تكنولوژي رااعطا كرده است. 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 بوسيله خروجي ها و ورودي يك بسته در شبكه تهيه سرويس .


 

تذكر : مطالبي كه شامل پرداخت هزينه مي باشند لينك دانلود پس از پرداخت موفق قابل نمايش و به ايميل شما ارسال مي شود ، در صورت نبود ايميل در بخش دريافتي ها به بخش اسپم ايميل خود مراجعه نماييد.