بخشی از مقاله
چکیده
به منظور محدود ساختن نرخ گمشدن بسته که به علت افزایش نمایی ترافیک شبکه ایجاد میشود، تکنیکهای مدیریت پویای صف مطرح شدهاند. به کمک این مکانیزمها ، وقوع تراکم کنترل شده و از کاهش کارایی شبکه جلوگیری میشود. در این مقاله بر روی سه الگوریتم مدیریت پویای صف RED ، REM و SFQ تمرکز کردیم و با بررسی معیارهای کارایی ( گذردهی، طول صف ، گمشدن بسته و تاخیر انتها به انتها ) بر روی شبکه سیمی مورد نظر خود این سه الگوریتم را با نرمافزار NS-2 پیادهسازی کردیم. در نهایت با مقایسه این الگوریتمها نشان دادیم که در ساختار شبکه فرض شده الگوریتم REM از نظر کارایی از الگوریتم SFQ بهتر است و بعد از این دو الگوریتم ، RED قرار میگیرد.
واژه های کلیدی مدیریت پویای صف ، RED ، REM ، SFQ ، گذردهی ، تاخیر ، نرخ گمشدن ، طول صف
-1 مقدمه
یکی از مکانیزمهای مهم تامین کیفیت سرویس1 و جلوگیری از وقوع ازدحام در شبکههای IP استفاده از مکانیزمهای مدیریت پویای صف و زمانبندی در مسیریابهای IP میباشد. الگوریتمهای زمانبندی صف میزان پهنای باند تخصیص یافته به هر کلاس سرویس را در درگاه خروجی مدیریت میکنند. الگوریتمهای مدیریت حافظه صف تعداد بستههای موجود در صف را با مشخص نمودن اینکه کدامین بسته چه زمان باید دورریخته شود، کنترل میکنند. SFQ2 یک کلاس از الگوریتمهای زمانبندی صف است. این الگوریتم برای تقسیم صف به تعداد زیادی از صفهای FIFO3 به صورت مجزا به کار میرود .[1] افزایش تعداد صفها به میزان زیاد، کمک میکند که در تقسیم پهنای باند عدالت4 بیشتری بدست آید. الگوریتم RED5 ازدحام اولیه را با ارسال سیگنال ازدحام به میزبانهای فرستنده آشکار میسازد و به آنها اجازه میدهد تا نرخ ارسال خود را قبل از سرریز بافر و دور ریختن بستهها کاهش دهند. به همین منظور الگوریتم RED یک متوسط وزن دار را از طول صف نگهداری میکند که به عنوان یک مکانیزم آشکارسازی ازدحام به کار میرود.[2] برای افزایش کارایی RED باید این ضمانت را ایجاد کند که اخطار ازدحام در نرخی انتقال داده شود که
1 Quality of service 2 Stochastic fair queuing 3 First in first out 4 fairness 5 Random early detection
منابع ارسال دهنده داده را تحت فشار قرار دهد؛ بدون آنکه بر بهرهوری لینک اثری گذاشته شود. همچنین RED باید تضمین سازد که فضای بافر برای تشکیل صف کافی است تا بتواند بار اعمالی بیشتر از ظرفیت لینک ( از زمانی که ازدحام تشخیص داده میشود تا زمانی که در پاسخ به ازدحام منابع نرخ ارسال خود را کاهش میدهند واز اینرو بار اعمالی بر لینک کاهش مییابد) را تحمل کند. FRED6 برای بدست آوردن عدالت در تقسیم پهنایباند استفاده از مکانیزمهای RED را پیشنهاد میکند. FRED بر اساس اشغال لحظهای صف توسط یک جریان مشخص عمل میکند و با پذیرفتن جریانهایی از اتصالات با پهنای باند کم از جریانهای شکننده7 محافظت میکند. از اینرو بسیاری از نقص-های الگوریتم RED را برطرف میکند ضمن آنکه تصمیمهای متفاوتی را برای دور ریختن بستهها به هنگام ازدحام برای جریانهای فعال در اتصالاتی که دارای کاربردهایی با پهنایباند متفاوت هستند میگیرد.[3] هنگامیکه یک جریان مقدار قابل توجهی از فضای بافر را اشغال می-کند، شناسایی میشود و به یک فضای کوچکتر محدود میشود. در الگوریتمهای مدیریت صف متفاوت، شدت ازدحام با استفاده از طول صف مشخص میشود. این مشکل ذاتی توسط الگوریتم BLUE حل شده است.[4] این الگوریتم هم در دور انداختن بسته و هم در نیاز به فضای بافر بهتر از RED عمل میکند. اگر بافر سرریز شود؛ BLUE به صورت بازگشتی بستهها را دور میریزد، احتمال دور ریختن را افزایش میدهد بنابراین نرخی را که اعلان ازدحام به منابع فرستاده میشود،
6 Flow random early drop 7 Fragile flows
2365
بالا میبرد، ایده اصلی این الگوریتم اجرای مدیریت صف مستقیما بر اساس نرخ ازدستدادن بسته و بهرهوری اتصال است REM8 .[4] یک مکانیزم مدیریت پویای صف است، که هدف از این مکانیزم بدست آوردن بهرهوری بالا ، تاخیر کم ، نرخ گم شدن ناچیز میباشد .[5] درحالی که اندازهگیری ازدحام تقاضای اضافی برای پهنای باند را نشان میدهد و باید تعداد کاربران را دنبال کند، طول صف و نرخ ارسال بستهها مستقل از تعداد کاربران پیرامون هدف مشخص شده خواهد بود. اولین ایدهی این الگوریتم این است که توسط آن نرخ ارسال کاربر با ظرفیت شبکه تطبیق یابد. بدون آنکه به تعداد کاربران توجهی شود. دومین ایده این الگوریتم این است که مجموع price های لینک (اندازهگیریهای ازدحام) را نگهداری میکند. احتمال دور ریختن یا علامت زدن کلی به صورت مجموع ارزشهای اتصالات موجود در مسیر ارسال بستههای کاربر محاسبه میشود.[5]
در این مقاله از نرمافزار NS-2 برای تحلیـل مقایسـه سـه الگـوریتم RED ، REM و SFQ اســتفاده کــردیم. ســاختار NS-2 و معیارهــای ارزیابی کارایی در بخش 2 شرح داده شده اسـت. در بخـش 3 در مـورد پیکربندی و پارامترهای استفاده شده در شبیهسازی توضـیح داده ایـم. همچنین در این بخش در مورد پیادهسازی و تحلیل نتایج مشاهده شده در شبیهسازی بحث کردهایم و در بخش 4 نتیجه گرفته شـده را بیـان کردیم.
-2 معیارهای ارزیابی کارایی
در شی Queue از زنجیره کلاس NS-2 الگوریتمهای مدیریت پویای صف مانند RED ، REM ، RIO ، FRED و سایرکلاسهای زمانبندی صف قرار گرفتهاند. هر الگوریتم مدیریت صف که اضافه میشود در این زنجیره قرار میگیرد. و از این رو قابلیت پیادهسازی در NS-2 را پیدا میکند
هنگامیکه NS اجرا میشود، اثر هر رویداد در فایل trace ذخیره میشود. همانطور که در شکل 1 نشان داده میشود این نتیجه در 12 ستون ذخیره میشود. توضیح هر ستون به همراه ذکر یک مثال در شکل 1 نشان داده شده است.
-2-1 گم شدن بسته9
یک علت دور ریختن بستهها در یک شبکه میتواند سرریز10 صف به علت ازدحام باشد. مقدار گم شدن بستهها در طول حالت پایا مشخصهی
8 Random exponential marking 9 Packet lost 10 overflow
مهم دیگری از شماتیک کنترل ازدحام است. حساسیت به گم شدن تنها یک بسته و گم شدن مکرر یک بسته یا الگوهایی از گم شدن بسته در بین زنجیرههای طولانی تنها به کاربرد وابسته است. این مشخصه به صورتهای متفاوتی مشخص میشود شامل؛ نرخ گم شدن11، الگوهای گم شدن12 ، احتمال گم شدن شرطی13 و از دست رفتن زمانهای خالی.[6] 14
دراین مقاله فرض میکنیم که گم شدن بسته به علت دور انداختن بستهها در نتیجهی ازدحام صورت گرفته است. وبنا به سایر دلایل مثل خرابی لینک یا خطا (که بیشتر در لینکهای بیسیم اتفاق میافتد )، بستهای گم نمیشود.
شکل:1 ساختار فایل trace
-2-2 گذردهی15
گذردهی معیار اصلی اندازهگیری کارایی است وکاربرد وسیعتری دارد. این معیار میزان دادهای را نشان میدهد که تا هر لحظه از زمان گیرنده از فرستنده دریافت میکند. که در هر لحظه از زمان با نسبت مجموع داده دریافتی توسط گیرنده به لحظهی مشخص شده بدست میآید. گذردهی فاکتور بسیار مهمی است که تاثیر مستقیم بر کارایی شبکه میگذارد.
-2-3 تاخیرانتها به انتها16
11 Loss rate 12 Loss patterns 13 Conditional loss probability 14 Loss free seconds 15 Throughput 16 End to end delay
2366
تاخیر مدت زمانی است که یک بسته برای حرکت از یک نقطه(مبدا ثابت یا به هنگام ورود به شبکه) به نقطهی دیگر(مقصد ثابت یا هنگام خروج از شبکه) میگذراند. هرچه میزان تاخیر بیشتر باشد برای پروتکلهای لایهی انتقال نگهداشتن پهنای باند بالا دشوارتر است.
این مشخصه میتواند در راههای متفاوتی شامل تاخیر متوسط17، واریانس تاخیر)18لغزش(19 و محدوده تاخیر20 بیان شود. در این مقاله تاخیر انتها به انتها را بررسی میکنیم.
