الگوريتم Kelly برای حل مسئله شبکه، بقرار زير است.
سيستم معادلات ديفرانسيلي زير را در نظر مي گيريم:
(4-13)
كه در آن، kr ضريبي ثابت و مثبت است و همچنين:
(4-14)
اگر فرض كنيم pj(y) هزينه اعمال شده توسط منبع j باشد كه بر واحد نرخ عبور كننده از اين لينك اعمال مي شود هنگامي كه كل نرخ عبور كننده از اين لينك برابر y باشد و تابعي افزايشي و مقعر از آرگومان خود است. با توجه به معادلات (4-13) و (4-14) شبكه سعي در متعادل كردن هزينه جمعي1 كاربر r يعني با مبلغ پيشنهادي كاربر يعني دارد.
در تعبيري ديگر از معادلات (4-13) و (4-14) مي توان فرض كرد كه pj(y) فيدبكي است كه از منبع j به كاربرهاي استفاده كننده از اين لينك ارسال مي گردد و كاربرها نرخ خود را بصورت يكنواخت و متناسب با افزايش داده و بصورت ضربي، نرخ را متناسب با مجموع فيدبك هاي دريافتي كاهش مي دهند.
4–3–2 الگوريتم Kelly براي حل مسئله كاربر
بررسي هاي انجام شده تا حال حاضر فرض مي كنند كه پارامترهاي انتخاب شده توسط كاربر ثابت هستند در حالي كه براي حل مسئله سيستم، كاربرها بايد قادر باشند پارامترهاي را در
مقياس هاي كوچك زماني تغيير دهند.
فرض كنيم كه كاربر r قادر به بررسي پيوسته نرخ xr(t) خود مي باشد و پارامتر را بصورت ملايم بصورتي كه نقطه بهينه و را دنبال كند، تغيير مي دهد. در [7] به كمك توابع لياپانوف مناسب نشان داده شده است كه الگوريتم تخصيص نرخ كاربر همگرا است.
در [7] نشان داده شده است كه با تبادل مداوم پارامترهاي بهينه شده مسئله كاربر و مسئله شبكه با يكديگر، نرخهاي نهائي كاربرها پاسخ مسئله SYSTEM نيز مي باشند.
4–3–3 بررسي پايداري سراسري الگوريتم ها[7]
تابع V(X) را بصورت زير تعريف می كنيم:
(4-15)
كه در آن و براي هر تابع برحسب آرگومان خود نامنفي و افزايشي و پيوسته و ناصفر است.
قضيه 4–3-1
تابع اكيداً محدب V(X) تابع لياپانوف براي سيستم (4-13) و (4-14) است و مقدار يكتاي X كه V(X) را حداكثر مي كند نقطه پايدار سيستم است كه كليه مسيرها به آن همگرا مي شوند1[7].
اثبات:
فرض هاي و شرايط pj(y) تضمين مي كنند كه V(X) بر روي اكيداً محدب است و داراي يك نقطه ماكزيمم دروني و يكتا است.
(4-16)
با صفر قرار دادن مشتق داريم:
(4-17)
(4-18)
V(X(t)) تابعي افزايشي از زمان t است مگر در X(t)=X كه ماكزيمم كننده يكتايV(X) است. پس V(X) يك تابع لياپانوف براي سيستم (4-13)-(4-14) است.
اگر تابع pj(y) را بصورت تعريف كنيم با حداكثر كردن V(X)، تا هر حد دلخواه پاسخ NETWORK(A,C;W) را تقريب مي زند.
4–3–4 سرعت همگرائي[7]
اگر X معرف برداي يكتاي حداكثر كننده V(X) باشد و قرار دهيم و فرض كنيم pj در اين نقطه مشتق پذير باشد. با خطي سازي سيستم (4-13) و (4-14) حول نقطه X يعني قراردادن براي هر r (yr(t) معرف تغييرات كوچك حول نقطه تعادل مي باشد) و جايگزيني آن در معادله (4-13)داريم[7]:
(4-19)
با نوشتن در فرم ماتريسي داريم:
(4-20)
كه در آن و و و و قرار مي دهيم:
(4-21)
كه ماتريسي متعامد است و و ماتريس مقادير ويژه ماتريس متقارن و مثبت معين سمت راست تساوی(4-21) است و بنابراين متقارن و مثبت معين است[15].
)يک ماتريس حقيقی A مثبت معين است اگروتنها اگر برای هر بردار ناصفر x داشته باشيم: (xTA x >0
آنگاه:
(4-22)
بنابراين نرخ همگرائي توسط كمترين مقدار ويژه ماتريس (4-21) معين مي شود. چنانکه مشاهده مي شود، سرعت همگرائي با ماتريس بهره K و اندازه مشتق هاي افزايش مي يابد.
اگر pj(y) افزايشي نباشد V(X) ممكن است داراي چند نقطه پايدار باشد و رفتار در اطراف نقاط تعادل توسط (4-22) معين مي شود.
4–3–5 تأخيرهاي زماني[7]
سيستم تأخيري گسسته (4-23) را در نظر مي گيريم:
(4-23)
كه در آن:
(4-24)
عددي صحيح و نامنفي بيانگرتأخيرناشي از ارسال فيدبك از لينك j به كاربر r است و تأخير ناشي از زمان لازم براي اطلاع پيدا كردن لينك j از تغيير نرخ كاربر s است. بردار X را نقطه تعادل سيستم (4-23)- (4-24) گوئيم هر گاه كه برای n =…, 0, 1, 2,… داشته باشيم xr[n]=xr.
قضيه 4–3-2
بردار X حداكثر كننده تابع اكيداً محدب V(X) نقطه يكتاي تعادل سيستم (4-23) است1[7].
اثبات:
بردار X نقطه تعادل است اگر و فقط اگر در صدق كند. اما اين دقيقاً شرايط ايستائي نتيجه شده از گرفتن مشتق جزئي (4-16) است كه تابعی اكيداً محدب با ماكزيمم يكتا است. در نتيجه، بردارX نقطة تعادل سيستم (4-23)) می باشد. g
براي مقادير بحد كافي كوچك kr ، نقطه تعادل پايدار مجانبي است چراكه اگر kr را در (4-23) با جايگزين كنيم و قرار دهيم آنگاه با مي توان با دقت كافي، پاسخ به
(4-23)-(4-24) را تقريب زد. اما براي مقادير كوچك kr همگرائي به نقطه تعادل، كند است و بهتر است پايداري محلي نقطه تعادل براي مقادير عمومي kr بررسي گردد.
قرار مي دهيم و فرض مي كنيم pj در اين نقطه داراي مشتق است. اگر قرار دهيم با خطي سازي سيستم (4-23) حول X داريم:
(4-25)
اگر تعداد كاربرهاي شبكه را با R نشان دهيم، المان rs ام ماتريس هايR×R را بصورت زير تعريف مي كنيم:
(4-26)
كه در آن تابع I[x=y] در نقطه x=y برابر با واحد و در ساير مقاديرx برابر با صفر است:
كه در آن، D حداكثر مجموع تأخيرهاي رفت و برگشتي در شبكه است.
بردارy[n] را تعريف مي كنيم و معادله (4-25) در فرم ماتريسي عبارتست از:
(4-27)
كه در آن:
نقطه تعادل X سيستم (4-23) پايدار است اگر و تنها اگر شعاع طيفي1 ماتريس L كمتر از واحد باشد. لازم به ذكراست كه طبق تعريف، شعاع طيفي يك ماتريس بزرگترين اندازه مقدار ويژه ماتريس مي باشد.
4–3–6 تطبيق كاربرها[7]
فرض كنيد كاربر r قادر به دنبال كردن نرخ xr(t) خود است و را بطور ملايم براي دنبال كردن مقدار بهينه تغيير مي دهد و داريم .
با مشتق گيري از مسئله USER داريم و بنابراين تحت شرايط تعقيب دقيق، عبارتست از:
(4-28)
حال به بررسي پايداري سيستم تغيير يافته مي پردازيم:
بنابراين، سيستم تغيير يافته پايدار است. با انجام خطي سازي حول نقطه تعادل، فرم تغييريافته (4-20) عبارتست از[7]:
كه در آن .
حال به بررسي حالت كلي تر مسئله بهينه سازي مي پردازيم كه در آن علاوه بر نرخ ها مسيرها نيز بهينه
مي شوند.
4–3–7 بهينه سازي همزمان مسير و نرخ كاربرها[7]
اگر نشان دهنده كاربری باشد که توسط زير مجموعه اي از R (کليه مسيرهای شبکه)
سرويس دهی گردد. Hrl=1 خواهد بود اگر مسير l به کاربر r متعلق باشد. درغيراينصورت Hrl=0.
براي هر lÎR ، r(l) نشان دهنده يك r است كه Hrl=1 و فرض مي كنيم اين r يكتا است.
حال اگر yl ميزان فلوي مسيرl باشد و منبع j هزينه را كه Cj(.) اكيداً محدب است، اعمال كند مسئله بهينه سازي بصورت زير است:
SYSTEM(U,H,A,C):
Maximize
Subject to:
NETWORK(H,A,C;W):
Maximize
Over:
و داريم:
(4-29)
آنگاه با روش Kelly [23] مي توان نشان داد كه بردارهاي و و كه شرط را ارضا كنند وجود دارند كه مسئله و X مسئله NETWORK(H,A,C;W) را حل مي كند و X جواب منحصر بفردي با اين ويژگي است كه برداري مثل y موجود است كه (X,y) مسئله SYSTEM را حل مي كنند[23].
حال به بررسي تعميم توابع لياپانوف مي پردازيم:
فرض كنيم pj و Cj توسط (4-29) به هم مربوطند. تعميم الگوريتم (4-13) و (4-14) عبارتست از:
(4-30)
كه درآن:
(4-31)
و قرار مي دهيم:
بنابراين سيستم ديناميكي (4-30)-(4-31) داراي ويژگي زير خواهد بود:
V(y(t)) > 0
مگر اينكه y پاسخ مسئله NETWORK(H,A,C;W) باشد.
4–3–8 بررسي مسئله ورود و خروج كاربرها در سيستم[10]
بصورت عادي انتظار مي رود كه ورود و خروج كاربرها در يك مقياس زماني بزرگتر از زمان لازم براي
همگرا شدن الگوريتم اتفاق بيفتد ولي با توجه به وجود تأخير زماني در شبكه در برخي حالات، فرض فوق برقرار نمي باشد.
در قسمت اول، هر مسير r را بعنوان بر هم نهي اثر چند كاربر كه هر كدام براي يك زمان ثابت در شبكه حضور دارند (مثلاً در حال تماشاي يك كليپ ويدئويي هستند) در نظر مي گيريم. در اين حالت همگرائي و پايداري براي سيستم ديناميكي با معرفي تابعي كه تابع هدف ضمني شبكه است صورت مي پذيرد.
در بخشي ديگر به بررسي شبكه اي با يك لينك پرداخته شده است كه دو نوع كاربر را سرويس دهي مي كند. نوع اول كاربر از نوع مطرح شده در قسمت اول مي باشد و نوع دوم كاربرها در حال انتقال يك فايل مشخص مي باشند يعني داراي اندازه وظيفة1 مشخص مي باشند. در اين حالت نشان داده شده است كه سيستم با توجه به تعداد كاربرهاي نوع اول از خود رفتار مناسب و يا نامناسب بروز مي دهد[10].
الف)كاربرهاي با دوره زماني ثابت
فرض كنيم براي مسير Rr ، كاربر r در حقيقت اثر مجموع تعداد زيادي كاربر است كه با تابع سودمندي Ur(.) وارد و خارج مي شوند. xrsub(t) و nr(t) بترتيب، نرخ تخصيص يافته و تعداد زير كاربر2 مي باشند.
سيستم زير را در نظر مي گيريم[10]:
(4-32)
(4-33)
كه در آن:
(4-34)
معادله (4-32) تغيير نرخ زير كاربرها را بررسي مي كند و (4-33) فرآيند ورود و خروج كاربرها را بررسي مي كند بدينصورت كه ورود كاربرها با نرخ ثابت و خروج آنها با نرخ صورت مي گيرد كه معرف كاربرهائي است كه زمان مشخصي در شبكه حضور دارند. حال تابع اكيداً محدب زير را در نظر مي گيريم:
(4-35)
قضيه 4–3-3
فرض كنيم . بردار يكتاي X حداكثر كننده V(X) نقطه پايدار سيستم
(4-32) است كه تمامي مسيرها به آن همگرا مي شوند[10].
اگر نقطه پايدار ما باشد كه و .
با خطي سازي با nr(t)=nr+mr(t) و داريم:
(4-36)
(4-37)
كه در آن و و و و و و اگر فرض شود L قابل قطري شدن است قرار مي دهيم: كه ماتريس مقادير ويژه L و بردارهاي ستوني بردارهاي ويژه L هستند. در اينصورت:
(4-38)
و سرعت همگرائي توسط مقادير ويژه با كمترين قسمت حقيقي ماتريس L تعيين مي گردد. همانگونه كه مشاهده مي شود اگر پارامترهاي k و و افزايش پيدا كنند سرعت همگرائي به همان نسبت افزايش مي يابد ولي در صورت وجود تأخير زماني افزايش پارامترهاي مذكور ممكن است منجر به ناپايدار شدن سيستم گردد.
ب) مخلوطي از كاربرها
در عمل، انواع مختلفي از كاربرها در سيستم حضور دارند كه در اين قسمت همانگونه كه ذكر شد به بررسي حضور همزمان كاربرهاي از دو نوع ”زمان ثابت“ و ”وظيفه ثابت“ مي پردازيم.
فرض كنيم كه يك لينك با ظرفيت واحد، حامل n1(t) كاربر با دوره ثابت و n2(t) كاربر با كار ثابت باشد. ابتدا سيستم با يك سيستم ديناميكي غير تصادفي مانند زير مدل مي گردد.
(4-39)
(4-40)
معادلات بالا بيان مي دارند كه كاربرهاي نوع اول با نرخ وارد سيستم مي شوند و براي دوره در سيستم باقي مي مانند. كاربرهاي نوع دوم با يك فايل با اندازه مدل مي شوند و با نرخ به سيستم وارد
مي شوند و پهناي باند به آنها اختصاص مي يابد ( بعلت تشريك متناسب پهناي باند بين n1(t)+n2(t) كاربر). سيستم (4-39) و(4-40) براي داراي نقطه ثابت زير است:
(4-41)
براي بررسي پايداري بايد از خطي سازي معادلات (4-39)-(4-40) استفاده كرد. با تعريف
n1(t)= n1+m1(t) و n2(t)= n2+m2(t) داريم:
(4-42)
(4-43)
كه بعلت اينكه n1>0 داراي مقادير ويژه مثبت است. بنابراين نقطه ثابت بصورت محلي پايدار است.
1-ازاين اثبات، در فصول بعد، استفاده گرديده است.