در شبكه هائي مانند اينترنت كه اكثريت ترافيك هاي موجود در آن را ترافيك الاستيك تشكيل مي دهد راضي بودن كاربرها از نرخ هاي تخصيص يافته، بستگي به معيار عدالت بكاررفته در امر تخصيص نرخ خواهد داشت.
هدف اصلي در واقع استفاده از تمامي پهناي باند موجود و تخصيص عادلانه آن به كاربرهاي مختلف
مي باشد. از بين شناخته شده ترين معيارها براي برقراري عدالت در تخصيص نرخ مي توان به معيار عدالت حداكثر- حداقل اشاره نمود[16].
در اين معيار، نرخ ها تا حدي كه محدوديتهاي مربوط به ظرفيت لينكها اجازه مي دهند به هم نزديك
مي شوند. يك مجموعه نرخ تخصيص داده شده داراي عدالت حداكثر- حداقل است اگر نتوان هيچ نرخي را بدون كاهش دادن نرخ ديگري كه كمتر يا مساوي با آن است افزايش داد.
Kelly معيار ديگري را مطرح كرده است كه در اثر حداكثر كردن يك تابع هدف در سرتاسر شبكه حاصل مي شود[7] و با اين فرض كه تابع سودمندي كاربرها بفرم لگاريتمي(log xr) است به تخصيص نرخي دست مي يابد كه آن را داراي عدالتي بنام ” عدالت تناسبي “ مي داند.
معيار ديگري كه براي عدالت در نظر گرفته مي شود با فرض در نظر گرفتن تابع سودمندي بفرم (-1/xr) براي كاربرها تعريف مي شود و منجر به تخصيص پهناي باندي مي شود كه مجموع معكوس نرخ كليه كاربرها را حداقل مي كند( xr نشان دهنده نرخ کاربرr است )[42].
تعبير ديگر اين معيار چنان كه خواهيم ديد، حداقل كردن مجموع كليه تأخير هاي بالقوه كاربرها
مي باشد. هر سه معيار عدالت ذكر شده را مي توان بصورت وزن دهي شده در نظر گرفت كه در واقع معرف وضع كردن تعرفه هاي متفاوت براي كاربرهاي متفاوت است.
اگر چه در اكثر موارد از معيار عدالت حداكثر- حداقل بهره گرفته مي شود و اغلب پروتكل هاي كنترل نرخ شبكه بطور تقريبي منجر به برقراري اين معيار مي شوند ولي مشخص شده است كه اصل پرهيز از ازدحام افزايش جمع شونده و كاهش حاصلضربي استفاده شده در TCP-Vegas [47] تمايل به برقراري عدالت تناسبي دارد[7]. معيار عدالت حداكثر- حداقل را مي توان با محاسبات صريح نرخ در سرويس ABR شبكه ATM بدست آورد [49],[48].
الگوريتم هاي تقسيم پهناي باند عملي بايد طبيعت بسته اي بودن ترافيك و تأثير حاصله از آن بر روي
نرخ ها را مورد توجه قرار دهند ولي در بحث فعلي فرض ما بر اين است كه ترافيك بصورت جريان مايع
مي باشد. حال به بررسي رياضي مفاهيم عدالت ذكر شده مي پردازيم.
3-4-1 مدل شبكه
فرض مي كنيم شبكه مورد نظر داراي L لينك باشد كه هر لينك داراي ظرفيت مثبت مي باشد. تعدادي از كاربرها براي دستيابي به اين لينك ها با هم رقابت مي كنند و اگر مجموعه لينك ها و كاربرها را بترتيب با J و Â نمايش دهيم، مي توانيم به هر كاربرrÎÂ يك مجموعه از لينكهاي متعلق به J را نسبت دهيم. lÎRr خواهد بود اگر لينك l در مسير ترافيک كاربر r (که با Rr نمايش می دهيم) قرار داشته باشد.
فرض مي كنيم مجموعه كاربرها و مسير ترافيک آنها مشخص و ثابت می باشند. اگر نرخ xr ³ 0 به كاربر r تخصيص پيدا كند، براي كليه لينك ها بايد محدوديت ظرفيتي زير برقرار باشد:
(3-1)J
همچنانكه قبلاً نيز اشاره شد فرض مي كنيم نرخ كاربرها بصورت جريان مايع باشد و تأثير ماهيت
بسته اي ترافيك را قابل اغماض فرض مي كنيم.
براي بيان معيارهاي عدالت مختلف، شبكه شكل (3-6) را در نظر مي گيريم.
شكل3-6: شبكه شامل L لينك و L+1 كاربر[12]
شبكه از L لينك با ظرفيت واحد تشكيل شده است كه ترافيک n0 كاربر در طول مسير خود تمامي L لينك را طي مي كنند و ترافيک nl كاربر فقط از لينك l عبور مي كنند براي 1 £ l £ L. مجموعه كاربراني كه از مسير طولاني عبور مي كنند را با R0 و مجموعه كاربراني كه از لينك l استفاده مي كنند را با Rl نمايش مي دهيم.
يكي از اهدافي كه ممكن است در تخصيص پهناي باند مورد توجه واقع شود انتخاب نرخ هاي xl به نحوي است كه مجموع نرخ كلي شبكه يا بعبارتي ديگر xr å را حد اكثر كنند ولي يك عيب عمده اين روش تخصيص پهناي باند اين است كه در اين روش ممكن است براي برآورده كردن هدف فوق مجبور به صفر كردن نرخ برخي از كاربرها شويم.
در حالت خاصي كه ni=1, “i ، اگر در شبكه خطي شكل (3-6) يك مسير انتها به انتها و يك مسير براي هر لينك داشته باشيم، در صورت تخصيص نرخ x0 به كاربري كه به صورت انتها به انتها در شبكه قرار دارد و با توجه به تقارن موجود ناگزير به تخصيص نرخ xr=1-x0 به مابقي كاربرها خواهيم بود و مجموع نرخها برابر با L-(L-1)x0 خواهد بود. اين نرخ كل در صورتي بيشينه مي شود كه داشته باشيم x0=0 .
3-4-2 معيار عدالت حداكثر-حداقل
اين معيار عدالت يكي از متداول ترين معيار هاي برقراري عدالت در تخصيص نرخ در شبكه هاي داده
مي باشد و نخستين بار توسط Bertsekas و Gallager مطرح شده است. [16] محققين بسياري الگوريتم هائي را ارائه كرده اند كه منجر به برقراري اين معيار مي شوند[51],[50]. هدف كلي از اين معيار حداكثر كردن حداقل {xr} در صورت وجود ظرفيت هاي محدود براي لينك هاي شبكه مي باشد. بعبارت ديگر، نرخ هاي تخصيص يافته {xr} بايد بنحوي باشند كه هر گونه افزايش در xr در ناحيه مقبول منجر به كاهش در نرخي مثل xs كه xs £ xr گردد. بنابراين حداقل يك لينك lÎr وجود خواهد داشت كه:
(3-2)
مشخص شده است كه در صورت محدود بودن تعداد منابع و كاربرها فقط يك تخصيص داراي اين نوع عدالت موجود خواهد بود و مي توان بطريق زير به آن رسيد[12].
با شروع از زمان صفر و تخصيص نرخ اوليه صفر براي تمامي كاربرها نرخ كليه كاربرها را بصورت خطي و هماهنگ افزايش مي دهيم و هرگاه به محدوديت ظرفيتي براي لينكي خاص رسيديم، تخصيص نرخ به كاربران عبور كننده از آن لينك پايان مي يابد و اين كار تا پايان تخصيص نرخ به بقيه كاربرها ادامه پيدا
مي كند. لازم به توضيح است كه در چنانکه در فصل دوم اشاره کرديم، در معيار حداكثر-حداقل كه سعي در حداكثر كردن حداقل سهم كاربر ناراضي دارد مطابق شکل (3-7) رعايت اصول زير الزامي است:
- منابع به ترتيب ميزان درخواستهاي صعودي تخصيص مي يابند.
- هيچ كاربري بيش از درخواست خود منبع در اختيارش قرار نمي گيرد.
- در يك لينك مشترك كاربراني كه به تقاضاي خود نرسيده اند مقدار سهم مساوي از منبع دريافت مي كنند.
- در يك لينك مشترك سهم كاربران ناراضي كمتر از سهم كاربران راضي نمي باشد.
شكل3-7: مفهوم عدالت Max-min
تخصيص نرخ حداكثر- حداقل براي شبكه شكل (3-6) بقرار زير است[12]:
| (3-3)
|
در حالت خاصي كه ni=1, “i ، به تمامي كاربرها نرخ 1/2 تخصيص مي يابد و مجموع نرخها برابر با (L+1)/2 خواهد بود كه مقدار قابل توجهي از مقدار حداكثر L كمتر است.
در حالت كلي، يك تخصيص نرخ داراي عدالت نياز به اطلاعات سرتاسري از شبكه دارد[52] و اغلب الگوريتم هائي كه توسط محققين براي حصول اين معيار ارائه شده است نياز به تبادل پاره اي اطلاعات بين كاربرها و شبكه دارند. Hahne يك روش round-robin را ارائه كرده است كه در صورت اجراي آن توسط تمامي لينك ها مي توان به معيارعدالت حداكثر- حداقل دست پيدا نمود [53] .
3-4-3 معيار عدالت تناسبي
يك مجموعه نرخ{xr} را داراي عدالت تناسبي مي گوئيم اگر آنها تحت محدوديت مربوط به ظرفيت
(3-1) تابع هدف å log xr را حداكثر كنند[23]. در حالتي كه تعدادي محدود از منابع و لينكها را در اختيار داريم بعلت فشرده1 بودن ناحيه تقيد (3-1) و اكيداً محدب2 بودن توابع لگاريتم، بردار تخصيص نرخ داراي عدالت تناسبي به كاربرها منحصر بفرد است و بصورت زير مشخص مي گردد.
مجموع تغييرات تناسبي نرخ هاي داراي عدالت تناسبي نسبت به نقطه بهينه هر تخصيص نرخ مقبول ديگر منفي است. بعبارتي ديگر:
(3-4)
حال اگر شكل (3-6) را در نظر بگيريم، از محدب بودن تابع لگاريتم نتيجه مي شود كه تمامي كاربراني كه در مجموعه Ri قرار دارند يك نرخ مشابه را دريافت خواهند كرد كه اگر اين نرخ را براي 0 £ i £ L
با xi نمايش دهيم، لزوماً خواهيم داشت:
(3-5)
براي هر تخصيص نرخ كه مجموع فوق كمتر از واحد باشد مي توان با افزودن نرخ ها به حد ظرفيت هر لينك رسيد و تابع هدف كلي را افزايش داد. بنابراين براي تعيين نرخ هاي بهينه بايد x0 را بنحوي پيدا كرد كه عبارت زير را حد اكثر كند:
(3-6)
با گرفتن مشتق داريم:
(3-7)
كه از آنجا بدست مي آيد:
(3-8)
در حالت خاصي كه ni =1 ,”i ، به نرخ هاي x0=1/(L+1), xi=L/(L+1) for i¹0 دست خواهيم يافت كه باعث مي شود مجموع نرخها برابر با L-(L-1)/(L+1) گردد.
3-4–4 معيار عدالت حداقل تأخير بالقوه
در حالتي كه مثلاً مشغول به ارسال پاره اي از اسناد در شبكه هستيم يك معيار بالقوه (و نه دقيق) براي بيان كردن تأخير ارسال هر سند، معكوس ميزان نرخي است كه براي ارسال آن سند مورد استفاده قرار مي گيرد.
در اين معيار عدالت ما به دنبال يك مجموعه از نرخ ها مي باشيم كه بتوانند تأخير بالقوه كل يا å1¤xr را حداقل كنند. شكل (3-6) را در نظر مي گيريم. در[12] نشان داده شده است كه براي مسير هاي موجود در مجموعه Ri، نرخ ها به قرار زير هستند:
(3-9)
در حالت خاصي كه ni =1 “i ، داريم: و . بنابراين مجموع نرخها عبارت خواهد بود از: .
3-4–5 تخصيص پهناي باند وزن دهي شده
در هر سه معيار قبلي، امكان قرار دادن يك ضريب وزن wr در رابطه با هر مسير r وجود خواهد داشت بقسمي كه افزايش در اين ضريب موجب افزايش نرخ تخصيص يافته به كاربر r خواهد شد.
بعنوان مثال، معيار عدالت حداكثر- حداقل را در نظر می گيريم. دراين معيار براي هر r حداقل يك لينك lÎRr موجود است بقسمي كه:
(3-10)
همانند حالت قبل، براي رسيدن به اين معيار، نرخ ها را با شروع از صفر بطور خطي افزايش مي دهيم با اين تفاوت كه شيب افزايش نرخ هر كاربرr متناسب با وزن wr مي باشد. در حالتي كه فقط يك لينك گلوگاه داريم، تخصيص نرخ ها بنحوي خواهد بود كه داشته باشيم:
xr/wr = constant
نسخه وزن دهي شده معيار عدالت تناسبي [12] بدينصورت است كه نرخ هاي xr بنحوي تنظيم مي شوند كه å wr.log xr را حداكثر كنند. براي هر تخصيص مقبول ديگر مجموع تغييرات نرخ وزن دهي شده نسبت به تخصيص بهينه نرخ {xr} منفي است.
بعبارت ديگر:
(3-11)
در حالتي كه يك لينك موجود باشد، نرخ هاي بهينه وزن دهي شده بنحوي هستند كه xr / wr=c.t.e. بطورمشابه در معيار عدالت حداقل تأخير بالقوه وزن دهي شده، نرخ هاي بهينه بگونه اي هستند كه مجموع
wr / xr å را حداكثر مي كنند.
Mo و Walrand يك معيار كلي را براي عدالت تعريف كرده اند و آن را معيار عدالت تناسبي (W,a) نامگذاری کرده اند[13]. آنها همچنين نشان داده اند كه هر سه معيار قبلي را مي توان بعنوان حالت هاي خاص اين معيار بيان كرد.
3-4–6 معيار عدالت تناسبي(W,a)
اگر W=(w1,…, wN) و a اعدادي مثبت باشند بردار نرخX* را داراي عدالت تناسبي (W,a)
مي دانيم اگر اين بردار مقبول باشد( يعنی در شرط (3-1) صدق کند) و براي هر بردار مقبول ديگر X :
(3-12)
حال مسئله زير را در نظر مي گيريم:
Max: (†)
Subject to: J
Over: X³0
لازم به توضيح است كه منظور از عبارت X ³0 ، نامنفي بودن تك تك مولفه هاي بردار X است.
قضيه 3-4– 1
تابع ¦a را بصورت زير تعريف مي كنيم:
آنگاه بردار نرخ X* مسئله (†) را با ¦=¦a حل مي كند اگر و تنها اگر X* داراي عدالت تناسبي (W,a) باشد[13] .
مثال 1:
در يك حالت خاص اگر قرار دهيم W=(1,…,1) و a=1 آنگاه به معيار عدالت تناسبي دست خواهيم يافت.
مثال 2:
اگر قرار دهيم W=(1,…,1) و a=2 آنگاه به معيار عدالت حداقل تأخير بالقوه دست خواهيم يافت.
قضيه 3-4– 2
اگر h(X) براي X ³ 0 تابعي مشتق پذير و افزايشي و محدب و منفي باشد پاسخ مسئله (†) با
= -(-h(X))a ¦a در صورتي كه a®¥ بسمت عدالت حداكثر- حداقل ميل مي كند [13].
1-Compact 2-Strictly concave