نمایش نتایج: از شماره 1 تا 1 , از مجموع 1

موضوع: الگوريتم هاي مسيريابي Routing algorithm

  1. #1
    عضو انجمن farzadho آواتار ها
    تاریخ عضویت
    Oct 2010
    نوشته ها
    112
    تشکر تشکر کرده 
    82
    تشکر تشکر شده 
    757
    تشکر شده در
    580 پست

    پیش فرض الگوريتم هاي مسيريابي Routing algorithm

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


    الگوريتم مسيريابي اي مناسب است که 6 ويژگي زير را داشته باشد: صحت عملکرد2، سادگي3، قابليت اطمينان4، پايداري5، عدالت6 و بهينگي7.


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


    الگوريتم کوتاه ترين مسير


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


    الگوريتم سيل آسا


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


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


    الگوريتم سيل آسا به جز چند مورد خاص، از جمله سيستم هاي توزيعي که عملکردهاي موازي در آنها نياز است، کاربرد علمي ديگري ندارد.


    الگوريتم بردار فاصله


    در اين روش، مسيرياب ها در خود جدولي (برداري) ذخيره مي کنند با عنوان بردار فاصله که در آن بهترين فاصله تا هر مسيرياب ديگر در شبکه را ذخيره مي کنند. در اين صورت، تصميم گيري بهتري هنگام مسيريابي اتخاذ مي شود. اين جدول ها با اطلاعات مسيرياب هاي همسايه به روز مي شود. هر يک از عناصر اين جدول ها يک درايه دوبخشي دارند که يکي از آنها نشانگر خط خروجي مناسب براي رسيدن به مسيرياب مورد نظر و ديگري تخمين فاصله زماني تا آن مسيرياب است.


    الگوريتم حالت لينک


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


    الگوريتم حالت لينک، ساده است و مي توان به صورت زير آن را بيان کرد:


    1. هر مسيرياب بايد همسايه هاي خود را شناسايي کرده و آدرس هاي شبکه شان را داشته باشد.


    2. ميزان هزينه و يا تاخير همسايه هاي خود را بداند.


    3. اطلاعاتي که از همسايه ها بدست آورده است را براي تمام مسيرياب هاي ديگر بفرستد.


    4. کوتاه ترين مسير براي رسيدن به ديگر مسيرياب ها را محاسبه کند.


    شناسايي همسايه ها به اين صورت انجام مي گيرد که پس از راه اندازي مسيرياب (بوت شدن) يک بسته سلام11 به تمام همسايه ها ارسال مي شود. مسيرياب هاي همسايه مشخصات خود را براي اين مسيرياب مي فرستند.


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


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


    منابع
    Andrew S. Tanenbaum, Computer Networks, 4th Edition, Prentice Hall, 2002

  2. تعداد تشکر ها ازfarzadho به دلیل پست مفید


  3. # ADS




     

اطلاعات موضوع

کاربرانی که در حال مشاهده این موضوع هستند

در حال حاضر 1 کاربر در حال مشاهده این موضوع است. (0 کاربران و 1 مهمان ها)

موضوعات مشابه

  1. الگوريتم هاي مسيريابي Routing algorithm
    توسط ColoMax در انجمن الگوریتم های روتینگ
    پاسخ ها: 0
    آخرين نوشته: October 22nd, 2015, 22:22
  2. پاسخ ها: 19
    آخرين نوشته: April 3rd, 2015, 03:30
  3. سوال بسيار مهم در مورد امنيت کلوکسو و سايتم !
    توسط Sohan Roh در انجمن کلوکسو يا ال ايکس ادمين Kloxo or LXAdmin
    پاسخ ها: 5
    آخرين نوشته: October 31st, 2013, 23:39
  4. سوال بسيار مهم در مورد Backup از سايتم در CPanel
    توسط Ariya در انجمن سی پنل CPanel
    پاسخ ها: 13
    آخرين نوشته: May 16th, 2012, 11:08
  5. پاسخ ها: 13
    آخرين نوشته: April 8th, 2012, 09:36

مجوز های ارسال و ویرایش

  • شما نمیتوانید موضوع جدیدی ارسال کنید
  • شما امکان ارسال پاسخ را ندارید
  • شما نمیتوانید فایل پیوست کنید.
  • شما نمیتوانید پست های خود را ویرایش کنید
  •