بخشی از مقاله
چکیده:
تخصیص منابع از مهمترین مسائل در شبکههای توزیعشده میباشد که هم از نقطه نظر تئوری و مدلسازی در این زمینه تحقیقات بسیاری انجام شده و مورد توجه بوده است و هم به دلیل گسترش و اهمیت شبکههای کامپیوتری، جنبههای کاربردی بسیاری دارد. بویژه تخصیص منابع در شبکههای بیسیم با کارایی بالا، با توجه به طبیعت پویای این شبکهها مسالهای مورد توجه است و برای این کار نیاز به تشخیص و مدیریت مناسب تداخلها است. این مساله زمانی که تعداد فرستندگان و گیرندگان افزایش مییابد، و مکانهای قرارگیری آنها نیز تصادفی باشد اهمیت بیشتری پیدا میکند. مد نظر ما الگوریتمهای توزیع شدهای است که بدون نیاز به ردو بدل کردن اطلاعات زیاد، جواب بهینهای برای تخصیص منابع شبکه به درخواستهای کاربران بدست آورد. در این مقاله ابتدا به مبحث تئوری تخصیص منابع پرداخته شده و پس از آن نگاه کاربردیتر آن در شبکههای کامپیوتری موردتوجه قرار می گیرد.
واژگان کلیدی: تخصیص منابع، شبکه بیسیم، الگوریتم توزیع شده.
-1 مقدمه
تخصیص منابع1 از مهم ترین مسائل شبکههای توزیعشده2 است و در طی سالیان محتلف، موردتوجه محققان قرار گرفته است. با توجه به قدمت بیشتر شبکههای سیمی3 نسبت به شبکههای بی سیم، و پویایی کمتر آنها، الگوریتمهای تخصیص منابع نیز در این دسته از شبکهها ساده تر هستند. ولی در شبکههای بی سیم با پیچیدگیهای بیشتری روبرو هستیم و نیاز به الگوریتمهای جدیدی داریم. مد نظر ما الگوریتمهای توزیع شده ای است که بدون نیاز به ردو بدل کردن اطلاعات زیاد، جواب بهینه ای برای تخصیص منابع شبکه - که مهم ترین آنها پهنای باند است - به درخواستهای کاربران بدست آورد. در این میان از نظریه بازیها و روشهای قیمت گذاری4 برای طراحی الگوریتمهای مناسب استفاده میشود.
اغلب این الگوریتمها با تکرار به تعداد کافی به جواب بهینه هم گرا میشوند.در ادامهی مقاله در بخش 2 از دیدگاه نظری به موضوع تخصیص منابع در شبکههای توزیع شده پرداخته می شود و مفهوم آن بیان می شود. پس از آن الگوریتم توزیع شده تخصیص منابع بر پایه قیمت TCP در بخش 3 شرح داده میشود. دربخش 4 توضیحی برای تخصیص منابع برای شبکههای بی سیم و Ad Hoc بیان خواهد شد و نهایتا در بخش 5 جمع بندی مقاله آورده می شود.-2 تخصیص منابع در شبکههای توزیع شده از دیدگاه نظری مساله انحصار متقابل5 حالت خاصی از مساله تخصیص منابع است. به بیان دیگر تخصیص منابع حالت کلی تر انحصار متقابل است که درآن به جای یک منبع امکان دارد چند منبع وجود داشته باشد.
حالات خاصی از مساله نیز وجود دارند. به عنوان نمونه، یک کاربر میتواند به جای درخواست یک منبع خاص ، درخواست منبعی از یک نوع را داشته باشد. مثلا کاربری درخواست پرینتر میدهد و اینکه دقیقا کدام پرینتر در اختیار او قرار داده شود، اهمیتی ندارد. در حالت دیگر ممکن است این اجازه وجود داشته باشد که چند کاربر به طور همزمان به یک منبع دسترسی داشته باشند. به عنوان مثال امکان چند عمل خواندن6 از پایگاه داده7 به طور همزمان8 وجود دارد.برای بیان رسمی مساله تخصیص منابع دو روش کلی وجود دارد. در روش اول منابع مورد نیاز هر کاربر به طور صریح ذکر میشود و در راه حل نباید دو کاربر که درخواستهای آنها اشتراک دارد، همزمان در حال استفاده باشند.
در شیوه دوم بیان مساله، ترکیبهایی از کاربرانی که نباید همزمان فعال باشند داده میشود و منابع درخواستی به طور صریح بیان نمیشوند. واضح است که با داشتن صورت مساله به بیان اول میتوان آن را به صورت دوم نیز بیان کرد. تعریف مساله تخصیص منابع دارای سه قسمت خوش فرم بودن9، شامل بودن10 و پیشرفت11 است.مساله کلاسیکی که معمولا در رابطه با تخصیص منابع موردبررسی قرار میگیرد ناهار فیلسوفان12 است. N فیلسوف دور میزی نشستهاند و بین هر دو فیلسوف یک چنگال قرار دارد. فیلسوفان اغلب در حال فکر کردن هستند - ناحیه - R13 و هرگاه گرسنه شوند - ناحیه - T 14 دو چنگال دو طرف خود را برداشته و شروع به غذا خوردن میکنند. - ناحیه بحرانی - C15 و پس از سیر شدن چنگالها را دو باره روی میز قرار میدهند - ناحیه - E16 برای حالت متقارن این مساله مشابه مساله انتخاب رهبر17 الگوریتمی وجود ندارد ولی با شماره گذاری فیلسوفان راه حلهایی با مدت انتظار محدود وجود دارد.
-3 الگوریتم توزیع شده تخصیص منابع بر پایه قیمت TCP
اینترنت را میتوان به عنوان بزرگترین سیستم توزیع شده در حال استفاده، در دنیای امروز به شمار آورد. اهمیت و نقش اینترنت در دنیای امروز بر کسی پوشیده نیست و از آن جا که پروتکلهای مورد استفاده در آن بر پایه الگوریتمهای توزیعشده[1] است، اهمیت مطالعه و گسترش و بهبود این الگوریتمها را نشان میدهد. از جمله مهم ترین مسائل در انواع شبکههای کامپیوتری مبحث تخصیص منابع است.مهم ترین پروتکل اینترنت ،TCP ، بر پایه یک الگوریتم استاندارد توزیع منابع بر پایه قیمت18 است. پیش فرض اولیه برای طراحی این الگوریتم، ترافیک ارتجاعی19 بوده است. منظور از ترافیک ارتجاعی، ترافیکی است که در طول زمان، حد ثابتی برای آن وجود ندارد و قابل تغییر است. برای ترافیکهای ارتجاعی میتوان توابع کارایی پیوسته20 و مقعر21 تعریف کرد و با استفاده از آن مسائل بهینه سازی22
