بررسی روشهای تخصيص نرخ بهينه به کاربرهای سطح شبكه بر اساس ديدگاه جريان سيال

 

4-1 مقدمه

 

 در حالت كلي و در كليه الگوريتم هاي كنترل نرخ به دنبال روشهائي هستيم كه قادر باشند بصورت انتها-به-انتها عمل كنترل نرخ را به انجام رسانند.

سئوال اساسي مطرح شده در اينجا وجود الگوريتمهاي كنترل نرخي است كه بتوانند بدون كمك گرفتن از گره هاي شبكه به تخصيص نرخي عادلانه دست بيابند. در چنين روشهائي گره هاي انتهائي (كاربرها) فقط متكي بر فيدبك هاي ضمني دريافت شده از شبكه مي باشند (مانند گذردهي و تأخير رفت و برگشتي1) و هيچ فيدبك مستقيمي را از گره هاي شبكه دريافت نمي كنند.

دليل اصلي علاقمندي محققين به چنين روش هائي سادگي پياده سازي آنها در شبكه هاي بزرگي مانند اينترنت بدون نياز به اعمال تغييرات در سوئيچ ها و مسيرياب هاي شبكه مي باشد و فقط نياز به پاره اي تغييرات نرم افزاري در گره هاي انتهائي مي باشد.

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

شناخته شده ترين الگوريتم كنترل نرخ انتها-به-انتها در اينترنت TCP مي باشد[26]. بسياري از محققين مشاهده كرده اند كه هنگام استفاده از TCP ارتباط هائي كه داراي تأخير رفت و برگشتي زياد هستند و از گره هاي گلوگاه متعددي عبور مي كنند از كاربران ديگر نرخ كمتري را دريافت مي كنند [55],[54],[43].

براي بهبود عدالت، Floyd و Jacobson الگوريتم “constant rate adjustment” را در [56] ارائه كرده اند. با اين وجود، هنوز انتخاب پارامترهاي مناسب براي اين الگوريتم بعنوان يك مسئله باز مطرح هستند.

بنابراين اگرچه پروتكل هاي انتها-به-انتها مانند TCP داراي مزايائي از جمله قابليت گسترش پذيري و سادگي پياده سازي هستند ولي بصورت عادلانه به تخصيص نرخ نمي پردازند. Jaffe در[57] نشان داده است كه نمي توان بصورت توزيع شده به بهينه سازي توان (نسبت گذردهي به تأخير متوسط) اقدام كرد.

Chiu و Jain در [47] نشان داده اند كه در يك شبكه داراي N كاربركه از يك لينك گلوگاه عبور
 مي كنند، يك الگوريتم با افزايش خطي و كاهش حاصلضربي مي تواند به نرخ هائي عادلانه همگرا شود. اغلب نسخه هاي فعلي TCP براي كنترل ازدحام به كنترل اندازه پنجره اقدام مي كنند و نه كنترل نرخ و
مي توان با مثالهائي ساده نشان داد كه در شبكه هائي با چند لينك گلوگاه، الگوريتم نمي تواند به نرخ هائي عادلانه همگرا شود[47].

همچنين Jain و Charny با استناد به [58] لزوم كنترل بر مبناي سوئيچ را براي حصول عدالت پيشنهاد كرده اند [59],[50].

Kelly در [7]، به معرفي معيار عدالت تناسبي پرداخته است و با استفاده از الگوريتم فيدبك تجمعي به نرخهاي عادلانه دست يافته است. در الگوريتم او كاربرها نرخ خود را بصورت افزايش جمعي و كاهش حاصلضربي و بر اساس فيدبك هاي تجمعي كه از سوئيچهاي مسير دريافت مي كنند تغيير مي دهند.

Le Boudec et al. در [60],[14] به مطالعه فرم دقيق عدالت در الگوريتم هاي افزايش خطي و كاهش حاصلضربي پرداخته اند. Massoulié و Roberts نيز بر روي مسئله برقراري عدالت در تسهيم پهناي باند و عدالت حداقل تأخير بالقوه تحقيقات گسترده اي را انجام داده اند[12].

كنترل نرخ در شبكه هاي داده بطور كلي از پيچيدگي هاي خاص خود برخوردار است. در مورد شبكه اينترنت بعلت پايين بودن درجه مشاهده پذيري و كنترل پذيري اين شبكه، پيچيدگي ذكر شده افزايش خواهد يافت.

در حال حاضر، فرم اصلي كنترل نرخ در اينترنت، استفاده از كنترل هاي انتها به انتها در لايه حمل
مي باشد كه در روش TCP  ارائه شده در [26] مورد بحث قرار گرفته است. اين كنترل نرخ بر اساس مشاهداتي است كه كاربرها از حذف شدن بسته هاي خود در شبكه از وضعيت ازدحام بدست
مي آورند. اگرچه TCP كارآمدي خود را در بسياري از زمينه ها به اثبات رسانيده است در جاهائيكه بحث از ترافيكهاي بلادرنگ و پشتيباني از سرويسهاي چند مقصدي1 به ميان مي آيد، TCP از كارائي چندان مناسبي برخوردار نمي باشد و روشهاي جديدي در مقالات زير براي بهبود اين نقاط ضعف ارائه شده است[64],[63],[62],[61],[54],[47],[43],[6],[5],[4],[3] و [65].

 بطورکلی الگوريتمهای تخصيص نرخی که منجر به تخصيص بهينة نرخ به کاربرهای سطح شبکه براساس ديدگاه جريان سيال می شوند، از تئوری بهينه سازی مقيد² جهت دستيابی به نرخهای بهينه استفاده می کنند.

چنانکه قبلاً اشاره کرديم، اگر بردار نرخ کاربرهای سطح شبکه را با X=(x₁, x₂, …, x_R) نمايش دهيم، هدف الگوريتمهای تخصيص نرخ بهينه، تخصيص بهينه المانهای بردار X براساس محدوديت ظرفيت لينکهای شبکه می باشد.

اين الگوريتمها در ابتدا توسط دکتر گلستانی در MIT مورد معرفی قرار گرفته اند[17]. سپس محققينی مانند Kelly  با تقسيم مسئله بهينه سازی به دو زير مسئله به تخصيص نرخ بهينه دست يافته اند[7].

Kelly براي اثبات پايداري اينگونه الگوريتمها از اين مسئله كه تابع هدف ضمني شبكه، يك تابع لياپانوف براي سيستم ديناميكي تعريف شده با الگوريتم كنترل نرخ است، استفاده کرده است.

مقالات مهمي از Bolot & Shankar [66] و Fendick [9] و Bonomi [67] موجود است كه پايداري شبكه را در حضور منبع گلوگاه بررسي كرده اند و در آنها از پر شدن بافر موجود در منبع براي اعلام ازدحام به كاربرها استفاده مي شود و بحث اين مقالات در مورد WAN ها مي باشد كه تأخير انتشار در آنها در مقايسه با تأخير صف بندي زياد است.

در اين بخش و بطور کلی در اکثر موارد رسالة حاضر، ما فقط به بررسي نرخ متوسط كاربرها مي پردازيم و به طول صف ها توجه نمي كنيم و بر اساس ديدگاه جريان سيال عمل خواهيم كرد. اين ديدگاه اگرچه از روشهائي كه به بررسي رفتار صف هاي موجود در شبكه مي پردازند آسانتر است ولي از نظر اينكه مي تواند به بررسي چندين گلوگاه بپردازد كاملتر از روشهاي ذكر شده مي باشد.

هر گونه بحثي در ارتباط با عملكرد روشهاي كنترل نرخ بايد به بررسي مسئله عدالت تخصيص نرخ نيز بپردازد چرا كه امكان دارد يك روش خاص، گذردهي شبكه را حداكثر كند ولي از دسترسي برخي كاربرها به شبكه جلوگيري كند. Kelly به توصيف مدلي از ترافيك الاستيك مي پردازد كه در آن كاربر به انتخاب

هزينه بر واحد زماني كه مايل به پرداخت آن است مي پردازد و پس از آن، نرخ كاربر، توسط شبكه، بر طبق معيار عدالت تناسبي كه به نرخ بر واحد هزينه اعمال مي گردد، تعيين مي شود[7].

نشان داده شده است كه در صورتي كه انتخاب هزينه كاربرها و نرخ تخصيص داده شده توسط شبكه در تعادل باشند به تخصيص نرخ بهينه دست پيدا خواهيم كرد.

در ادامه، دربخش (4-2) به معرفی الگوريتم تخصيص نرخ معرفی شده توسط دکتر گلستانی می پردازيم و سپس در بخش (4-3) به معرفی روش Kelly  که در اين رساله بيشتر مورد توجه واقع شده است خواهيم پرداخت.

4–2  طرح مسئله كنترل نرخ بصورت يك مسئله بهينه سازي عمومي[17]

يك شبكه داده را در نظر مي گيريم و فرض مي كنيم از L لينك و R كاربر تشكيل شده است. نرخ متوسط كاربر r را با x_r و فلوي متوسط عبور كننده از لينك  را (بر حسب بيت بر ثانيه) با  نمايش
 مي دهيم. بردار نرخ كاربرها و فلوي لينك ها را بترتيب با   و  نمايش مي دهيم. مجموعه لينکها يا منابع را با J و مجموعه مسيرهاي ممكن را با Â نمايش مي دهيم.

با مدلسازي الگوريتم تخصيص نرخ با يك مسئله بهينه سازي سرتاسري مي توان به نرخ هاي بهينه كه بر اساس معيار عدالت مشخص، تنظيم شده اند دست پيدا كرد. در ابتدا براي هر كاربر يك تابع هزينه نارضايتي كه تابعي از نرخ او مي باشد مطابق شكل (4-1) تنظيم مي گردد.

شکل 4-1: تابع هزينه نارضايتي کاربر r [17]

با كاهش پيدا كردن x_r هزينه مربوط به نارضايتي كاربر افزايش پيدا مي كند. بطور مشابه، براي هر لينك شبكه، يك تابع هزينه به فرم  مطابق با شكل (4-2) تعريف مي گردد.

شکل 4-2: تابع هزينه لينک [17]

اين تابع هزينه تابعي افزايشي از فلوي  عبور كننده از لينك مي باشد. هنگامي كه اين فلو به ظرفيت لينك نزديك مي شود،  طول متوسط صف تشكيل شده براي پيغام هائي كه قصد عبور از لينك را دارند و در نتيجه خطر ايجاد ازدحام افزايش پيدا مي كند. توابع هزينه مربوط به لينك و كاربر مي توانند فرم هاي مختلفي داشته باشند كه در قسمتهاي بعد راجع به اين مطلب بحث خواهيم كرد. فعلاً فقط فرض مي كنيم اين توابع مقعر بوده و دو بار مشتق پذير هستند و مشتق دوم نامنفي دارند. همچنين فرض مي كنيم e_r(x_r) و  بترتيب توابعي كاهشي و افزايشي از آرگومان خود هستند.

 آن بخشي از ترافيك كاربر r است كه از لينك عبور مي كند. در حالت مسيريابي تك مسيري  براي تمامي لينك هاي واقع در مسير ترافيک كاربر r برابر با 1 و براي لينك هائي كه در مسير ترافيک كاربر r  قرار ندارند برابر صفر است. از تعريف فوق بر مي آيد كه:

 (4-1)                                

عبارت فوق بيان مي دارد كه فلوي هر لينك عبارتست از مجموع نرخ كاربرهائي كه از آن لينك عبور مي كنند.

بايد توجه داشت كه پارامترهاي كه در ارتباط با الگوريتم مسير يابي مي باشند در حقيقت خود در يك مقياس زماني بسيار بزرگتر از تغيير دادن نرخ کاربرها در الگوريتم كنترل نرخ، تغيير می کنند و فرض مي كنيم در حين اعمال الگوريتم كنترل نرخ، ثابت هستند.

فرض مي كنيم x_r^d نرخ متوسط ارسال مطلوب براي كاربر r باشد. نرخ متوسط x_r تخصيص يافته به كاربر r بايد در رابطه زير صدق كند:

 (4-2)                                                             

مسئله كنترل نرخ را مي توان با عبارات رياضي بصورت پاسخ مسئله بهينه سازي زير بيان كرد:

 (4-3)                                             

Subject to:

به منظور بيان كردن شرايط بهينگي براي اين مسئله، به معرفي دو تابع جديد مي پردازيم. ابتدا تابع نمو پاداش1  براي كاربر r را بصورت زير تعريف مي كنيم:

 (4-4)                                         

h_r(x_r) در واقع عبارتست از نمو كاهش در هزينه كاربر r براي واحد افزايش در نرخ تخصيص يافته x_r . از آنجائيكه e_r(x_r) طبق تعريف تابعي مقعر و كاهشي است، h_r(x_r) تابعي مثبت و كاهشي خواهد بود. تابع بعدي در واقع اندازه ازدحام كاربر r  را بعنوان  نمو هزينه ازدحام شبكه در اثر واحد افزايش نرخ كاربر r معرفي مي كند:

 (4-5)                           

بعنوان تابعي از  معرفي شده است تا نمايانگر بستگي آن به فلوي لينك هاي شبكه باشد. از آنجائيكه بر طبق فرض، توابع هزينه لينك توابعي افزايشي با مشتق مثبت هستند، اندازه ازدحام يك كاربر همواره كميتي مثبت است.

 (4-6)                                                       

كه در آن، R_r نشانگر مسير ترافيک كاربر r است. مشاهده مي كنيم كه در اين حالت اندازه ازدحام هر كاربر برابر است با مجموع نمو هزينه لينك هاي مسير.

با اعمال تئوري Kuhn-Tucker  به مسئله بهينه سازي (4-3) به شرايط بهينگي بيان شده در قضيه زير دست مي يابيم[15]:

 قضيه4-2-1

فرض كنيد  و  داراي مشتقات اول و دومي هستند كه در روابط  و  صدق مي كنند. در زير شرايط لازم و كافي براي اينكه بردار نرخ كاربران  مسئله (4-3) را با محدوديتهای آن حداقل كند، آورده شده اند:

 (4-7)              

كه در آن  بردار فلوي لينكها در ارتباط با بردار مي باشد چنانكه در رابطه (4-1) مشخص گرديده است.

تفسير شرايط بهينگي فوق از اين قرار است كه در نقطه بهينه تا زمانيكه محدوديت (4-2) براي كاربرr فعال نيست، تابع نمو پاداش كاربر بايد با هزينه نمو ازدحام يا اندازه ازدحام كاربر برابر باشد. اگر x_r^*=0 يا  (x_r^*=x_r^d) باشد يعني اگرx_r^* ديگر نتواند كاهش (افزايش) بيابد، آنگاه تابع نمو پاداش كاربر
 مي تواند كوچكتر (بزرگتر) از اندازه ازدحام كاربر باشد.

1-Round-trip time (RTT)

1-Multicast                                                                                                              2-Constrainted Optimization                                                                                                                                                     

1- Incremental reward function