Manuscript ID : 202005081281 Visit : 9764 Page: 19 - 30

Article Type: Original Research

A new reinforcement learning based multi-agent method for traffic shaping and buffer allocation in routers

Subject Areas : ICT

Received: 2013-06-16 Published : 2019-11-08

Keywords:

Abstract :

Normal 0 false false false EN-US X-NONE AR-SA MicrosoftInternetExplorer4 /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal" mso-tstyle-rowband-size:0 mso-tstyle-colband-size:0 mso-style-noshow:yes mso-style-priority:99 mso-style-qformat:yes mso-style-parent:"" mso-padding-alt:0cm 5.4pt 0cm 5.4pt mso-para-margin:0cm mso-para-margin-bottom:.0001pt mso-pagination:widow-orphan font-size:11.0pt font-family:"Calibri","sans-serif" mso-ascii-font-family:Calibri mso-ascii-theme-font:minor-latin mso-fareast-font-family:"Times New Roman" mso-fareast-theme-font:minor-fareast mso-hansi-font-family:Calibri mso-hansi-theme-font:minor-latin mso-bidi-font-family:Arial mso-bidi-theme-font:minor-bidi} Abstract In this paper, realizing the distributed structure of computer networks, the random behaviors in such networks, and the time limitations for control algorithms, the concepts of reinforcement learning and multi-agent systems are invoked for traffic shaping and buffer allocation between various ports of a router. In fact, a new traffic shaper based on token bucket has been developed. In this traffic shaper, instead of a static token production rate, a dynamic and intelligent rate based on the network condition is specified. This results in a reasonable utilization of bandwidth while preventing traffic overload in other part of the network. Besides, based on the stated techniques a new method for dynamic buffer allocation in the ports of a router is developed. This leads to a reduction in the total number of packet dropping in the whole network. Simulation results show the effectiveness of the proposed techniques.

References:

Full-Text:

فصلنامه علمي-پژوهشي

فنّاوري اطلاعات و ارتباطات ایران

سال اول، شماره‌هاي 1و 2، پاييز و زمستان 1387

صص: 19- 30

$E:\E Drive\logo\iicta Logo0.JPG$

يك روش چند عاملي جديد مبتني بر يادگيري تقويتي براي شكل‌دهي ترافيك و تخصيص حافظه بافر در روترها

محمد طاهري تهراني* سيد علی اکبر صفوي*1 محمد رفيع خوارزمي**

*دانشكده مهندسي برق و كامپيوتر، دانشگاه شيراز

**دانشكده مهندسي برق، دانشگاه صنعتي شيراز

چکيده¹

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

کليد واژگان‌: شبكة كامپيوتري، سيستم چند عاملي، حافظة بافر، روتر، شكل‌دهي ترافيك

1- مقدمه

امروزه با پيشرفت در شبكه‌هاي انتقال داده پرسرعت، كاربردهاي زبان واقعي1²و فعال مانند دورکنفرانس2³و يا محاسبات توزيع شده3⁴مطرح شده‌اند. با توجه به غيرهمسان بودن منابع اين كاربردها (ويدئو، صدا يا داده)، کيفيت سرويس (QoS) 4⁵موجود در شبكه‌هاي انتقال نمي‌توانند به‌طور كافي انتقال اين داده‌ها را به‌صورت پيوسته و مناسب تضمين كنند. بنابراين بايد به نوعي به سمت روشهايي رفت که نيازهاي (QoS) را به بهترين نحو ممكن برآورده كنند [1و14].

ازطرفي اكثر ابزارها و قالبهاي مديريتي كه امروزه در شبكه‌هاي كامپيوتري استفاده مي‌شود براساس روشهاي متمركز5 ⁶ بنا شده‌اند و از فنّاوريهايي كه در بستر شبكه وجود دارد و مي‌توان از آنها در راستاي مديريت شبكه استفاده كرد، چندان بهره‌اي نمي‌برند. به‌عنوان مثال، غالباً اپراتورها در سطوح مختلف سازماني، به مديريت شبكه‌ها بر اساس برنامه‌هاي ساده و غير انعطافپذير مي‌پردازند و لذا درتوسعه ابعاد شبكه، با مشکل توسعه‌پذيري6⁷سيستم خود روبرو هستند [2و3].

الگوريتم‌هاي كنترل شبكه را مي‌توان به دو دسته تقسيم كرد، يكي الگوريتم‌هاي كنترل جريان7⁸و ديگر الگوريتم‌هاي كنترل ازدحام⁹. در الگوريتم‌هاي كنترل جريان، شبكه به دنبال انجام كارهايي است كه در آن از به ‌وجود آمدن ازدحام جلوگيري شود در صورتي كه در كنترل ازدحام، شبكه به دنبال آن است كه زمان، گسترش و چگالي ازدحام به‌وجود آمده را حداقل كند. روشهاي كنترل جريان به‌نوعي پيشگيرانه¹⁰ و الگوريتم‌هاي كنترل ازدحام واكنشي¹¹ هستند[3]. به‌عنوان مثال، روش شکل‌دهي ترافيک¹² يكي از الگوريتم‌هاي كنترل ازدحام است كه در کامپيوترها و روترها مي‌تواند استفاده شود و به‌نوعي نرخ ارسال داده‌ها را بويژه در مواقعي كه نرخ توليد اين داده‌ها نامنظم و ضربه گونه¹³ است، منظم كند. اين موضوع ممكن است ناشي از اين نكته باشد كه استفاده‌كنندگان اين منابع، به‌طور سهوي يا به هر دليل ديگر، سعي در افزايش نرخ ارسال مورد توافق درهنگام برقراري ارتباط داشته باشند.

امروزه با توجه به ابعاد زياد داده‌ها و طبيعت ناهمسان آنها و محدوديت‌هاي زماني مرتبط با كارهاي كنترلي، بسياري از جنبه‌هاي كنترل شبكه‌هاي مخابراتي را مي‌توان برپايه روشهاي هوش مصنوعي بنا نهاد و با توجه به اينكه شبكه ساختاري توزيع شده دارد، روشهاي هوش مصنوعي توزيع شده (DAI)¹⁴ مي‌توانند نامزد مناسبي باشند [3و4] . يكي از زير شاخه‌هاي (DAI)، سيستم‌هاي چند عاملي ¹⁵ هستند كه با استفاده از مجموعه‌اي از واحدهاي مستقل به نام عامل، مي‌توانند رفتار يك سيستم را تحت كنترل درآورند.

از طرف ديگر براي اينكه سيستمهاي چند عاملي بتوانند در تقابل با محيطي كه درآن قرارگرفته‌اند، رفتار مناسب و بهينه‌اي نشان دهند، احتياج به يادگيري دارند. در واقع يكي از خصوصيات اصلي سيستمهاي هوشمند، نياز به يادگيري است و سيستمهاي چند عاملي هم از اين قانون مستثنا نيستند [5 و6]. يكي ازاين روشهاي يادگيري، ياد گيري تقويتي¹⁶ است. يادگيري تقويتي به معناي آن است كه يك عامل بتواند با سعي وخطا، در تقابل با محيطي كه در آن قرار گرفته است به يادگيري رفتار مناسب بپردازد. يادگيري تقويتي يكي از روشهاي برنامه‌ريزي عاملهاست كه در آن يك عامل بدون شناخت اوليه از محيط و با استفاده از تقابلي كه با محيط دارد و پاداشهايي كه از محيط دريافت مي‌كند، به مرور زمان، رفتار بهينه خود را مي‌آموزد. يكي از روشهايي كه اصولاً براي حل مسائل مربوط به يادگيري تقويتي وجود دارد، استفاده از روشهاي آماري وبرنامه‌ريزي پويا مانند روشهاي بلمن1¹⁷براي تخمين بهترين عمل2¹⁸ها در هرحالتي از محيط است [5-7].

در اين مقاله با ارائه راهکارهاي مبتني بر يادگيري تقويتي و مفاهيم چند عاملي، سعي مي‌شود تا در حد امکان علاوه بر استفاده بهينه از پهناي باند موجود، ترافيک و ازدحام در ديگر نقاط شبکه کاهش داده شود. در اين راستا دو قالب چند عاملي ارائه مي‌شود. يک قالب شکل دهنده ترافيک که ترافيک آمده به سمت روتر را به طور هوشمند و بر اساس وضعيت شبکه در جلو شکل دهي مي‌کند و يک قالب تخصيص دهنده حافظه که نيز بر اساس شرايط شبکه به اشتراک و اختصاص حافظه بافر به هر پورت روتر مي‌پردازد. براي عاملهاي شكل دهنده ترافيك دو حالت تعريف شده است: يکي درصد افت بسته3 ¹⁹هاي اطلاعاتي که روتر جلوي خود مي‎بيند و ديگري درصد بافر استفاده شده در پورت خروجي. عامل درهر لحظه با پسخور گرفتن از اين دو حالت به عنوان ورودي، به‌صورت هوشمند و با استفاده از الگوريتم يادگيري تقويتي عمل مناسب را به عنوان خروجي به شبکه اعمال و در مقابل يک پاداش دريافت مي‎کند. اين پاداش بر اين اساس تعريف ‎شده که شبکه با گرفتن اين عمل به چه حالت ديگري رفته است. در واقع اين پاداش ميزان مفيد بودن عمل را در راستاي نزديک کردن شبکه به يک حالت مناسب نشان مي‎دهد. طبيعي است که حالت مناسب طبق اين تعاريف، کاهش درصد افت بسته‌ها و همچنين کاهش درصد بافر استفاده شده در پورت است. به اين دليل که هرچه اين بافر خالي‎تر باشد، ميزان افت براي بسته‌هاي ورودي کاهش مي‎يابد.

علاوه بر آن که اين عاملها بر روي تمام پورتهاي خروجي يک روتر در قالب چند عاملي در نظر گرفته مي‌شود و به کمک آنها شکل دهي هوشمند ترافيک در جلوي روتر و بر اساس وضعيت شبکه انجام مي‌شود، براي هر پورت عامل ديگري هم در نظر گرفته مي‌شود تا با توجه به وضعيت شبکه در پشت روتر و در قالب يک سيستم چند عاملي ديگرکار تخصيص بافر4²⁰را براي هر پورت انجام دهد. اضافه‌کردن اين قالب باعث کاهش درصد افت بسته‌هايي مي‌شود که به سمت پورتهاي شلوغ مي‌روند. براي اين عاملهاي تخصيص دهنده حافظه نيز دو حالت تعريف مي‌شود: يكي ميزان افت بسته‌ها در ورودي هر روتر و ديگري ميزان پر يا خالي بودن بافر مربوط به هر پورت.

ساختار اين مقاله به صورت زير است: در بخش بعدي به اجمال به روشهاي شكل‌دهي ترافيك، به ويژه الگوريتم سطل نشانه‌دار، اشاره مي‌شود. پس از آن در بخش سوم به مروري درمورد يادگيري تقويتي پرداخته مي‌شود. از اين ايده در بخش چهارم براي طراحي و پياده‌سازي راهکارهاي پيشنهادي درساختار قالبهاي چند عاملي استفاده مي‌شود. در بخش پنجم به شبيه‌سازي و ارزيابي نتايج مدلهاي توسعه داده شده پرداخته مي‌شود و در نهايت در بخش آخر نتايج و پيشنهادهايي براي كارهاي آينده آورده مي‌شود.

2- شكل‌دهي ترافيك

شکل دهي ترافيک (يا شکل‌دهي بسته‌ها) فرايندي است به منظور کنترل ترافيک شبکه‌هاي کامپيوتري که طي آن واحد شکل دهنده با تأخير دادن به بسته‌ها و کنترل بر روي زمان و ميزان ارسال بسته‌ها سعي مي‌کند کارايي شبکه و همچنين پهناي باند شبکه را به طور بهينه استفاده کند و يا اهداف خاص مديريتي را در پياده‌سازي QoS تضمين نمايد. به عبارت ديگر شکل دهي ترافيک به هر عملي گفته مي‌شود که بر روي يک جريان از بسته‌ها اعمال شده و سعي مي‌کند با تحميل کردن يک زمان تأخير اضافي بر روي آن بسته‌ها، آنها را در يک پروفايل²¹ از قبل تعريف شده ترافيکي قرار دهد. شکل‌دهي ترافيک وسيله اي است براي کنترل حجم ترافيکي که در يک بازه زماني به داخل شبکه تزريق مي‌شود و يا كنترل حداكثر نرخي كه ترافيك به داخل شبكه فرستاده مي‌شود. شكل‌دهي ترافيك اصولاً در لبه‌هاي شبكه مثل روترهاي منبع²² (SR) براي كنترل ترافيك تزريقي به شبكه به كار برده مي‌شود ولي با اين حال مي‌توان آن را در منابع ترافيكي مثل خود كامپيوترها يا در داخل شبكه مثل روترهاي شبكه²³ (NR) مورد استفاده قرار داد[8،9 و10].

دو روش اصلي كه عمدتاً براي پياده‌سازي شكل‌دهي ترافيك وجود دارد الگوريتم سطل سوراخ دار(LB)²⁴ و الگوريتم سطل نشانه دار (TB)²⁵ است. الگوريتم LB يك محدوديت سخت بر روي نرخ ارسال داده‌ها مي‌گذارد و آنها را مجبور مي‌كند كه با يك نرخ ثابت ارسال شوند در حالي كه الگوريتم TB اجازه مي‌دهد ارسال داده‌ها به صورت متغير و بعضاً همراه ضربه‌هاي قابل قبول باشد و فقط بر روي ميانگين داده‌هاي ارسالي محدوديت مي‌گذارد. اين الگوريتم كه در اين تحقيق هم مورد توجه بوده است درواقع يك مكانيزم كنترلي است كه بر اساس تعداد نشانه موجود در سطل، مشخص مي‌كند چه موقع ترافيك آمده به سمت جلو ارسال شود. واحد شمارش نشانه بايت يا تعداد بسته است و اين واحد بدين معناست كه هر نشانه واحد مي‌تواند به چه تعداد بايت داده و يا بسته اطلاعاتي اجازه ارسال دهد. مقدار دقيق اين تعداد توسط مدير شبكه مشخص مي‌شود. با اين تفاسير در صورتي جريان ترافيكي اجازه ارسال خواهد يافت كه به تعداد كافي نشانه براي ارسال آن وجود داشته باشد.

3- يادگيري تقويتي

درسالهاي اخير يادگيري تقويتي به عنوان يك روش يادگيري كه در آن احتياجي به استفاده از مدل محيط نيست و مي‌توان به طور زمان واقعي از آن استفاده كرد مورد توجه قرار گرفته و بر روي آن مطالعات گسترده انجام شده است. از طرف ديگر همان طور كه قبلاً ذكر شد براي اينكه سيستمهاي چند عاملي بتوانند در تقابل با محيطي كه در آن قرار گرفته‌اند، رفتار مناسب و بهينه‌اي نشان دهند، احتياج به يادگيري دارند و از آنجا كه هر عامل اطلاعات كمي از وضعيت ديگر عاملها دارد و توجه به اين موضوع كه محيط دائماً در حال تغيير است، يادگيري تقويتي مي‌تواند به عنوان يك روش يادگيري مناسب در كنار آن استفاده شود.

يادگيري تقويتي به فرايندي گفته مي‌شود که در طي آن يک عامل مي‌آموزد چه اعمالي بايد انجام دهد تا پاداش بيشتري از محيط دريافت کند. نکته اي که در اين يادگيري قابل توجه است آن است که انجام يک عمل توسط عامل نه تنها شامل يک پاداش آني مي‌شود بلکه بر موقعيت هاي بعدي و همچنين مجموع پاداشهاي به دست آمده طي فرايند نيز تأثيرگذار است.

درشکل1 مدلي از فرايند يادگيري تقويتي ارائه شده است. در اين مدل در لحظه عامل يک عمل انجام مي‌دهد در مقابل اين عمل، محيط عامل را از حالت به حالت مي‌برد و يک پاداش لحظه اي به آن مي‌دهد. در واقع اين مقدار پاداش به نوعي عامل را در راستاي پيدا کردن سياست بهينه تقويت مي‌کند و به همين دليل است که به اين روش يادگيري تقويتي گفته مي‌شود.

شکل1: مدل ساختار يادگيري تقويتي

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

(1)

محبوبترين روش درحل مسائل يادگيري تقويتي روش تفاوت موقتي است. اين روش علاوه بر آنکه نيازي به مدل محيط يادگيري ندارد قابليت بالايي در محاسبات مرحله به مرحله افزايشي دارد. در اين روش عامل سعي مي‌کند به تقريب تابع مقدار بر اساس پاداش لحظهاي و مقدار تخمين زده شده براي حالت بعدي که در آن قرار خواهد گرفت بپردازد و در اين راستا از روش تکرار مقدار نيز کمک مي‌گيرد.

ساده‌ترين و پركاربردترين روش يادگيري تفاوت موقتي روش يادگيري Q است. اين روش تجربه بدست آمده از هر گذر حالت در محيط را استفاده كرده و مقادير مربوط به هر حالت را در يك جدول به نام جدول Q به روز مي‌كند. اين جدول براي هر زوج حالت و عمل ( و) يك مقدار Q(S,a) دارد و به ازاي هر گذر حالت از به و دريافت پاداش مقادير Q را در جدول طبق رابطه2 به روز مي‌كند:

(2)

اگر دقت شود در اين الگوريتم ،عامل موقعي که عمل را در حالت انتخاب مي‌کند و به حالت مي‌رود براي به روز کردن مقدار Q خود در آن لحظه يعني از ماکزيمم مقدار Q حالت بعدي يعني نيز استفاده مي‌کند. در اين الگوريتم اگر هر عمل در هر حالت، در بي نهايت اجراي برنامه بي نهايت بار انتخاب شود و پارامتر به خوبي تنظيم شود مقادير Q با احتمال صدر صد به Q* همگرا خواهند شد .

4- مدل سيستم ارائه شده

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

درساختارهاي ارائه شده در اين مقاله، روترها در دو دسته اصلي روترهاي شبکه²⁶ (NR) و روترهاي منبع²⁷ (SR) طبقه‌بندي مي‌شوند. روترهاي منبع آن دسته از روترها هستند که در سمت کاربران قرار دارند و مستقيماً با آنها در ارتباط هستند و روترهاي شبکه آن دسته از روترها هستند که کاربران مستقيماً با آنها سروکار ندارند و به عنوان متصل کننده بين چند زير شبکه عمل مي‌کنند. هر SR با يک سطل نشان دار (TB) به طول بيت و نرخ توليد نشانه بيت بر ثانيه مشخص مي‌شود. در اين حالت روتر در صورتي مي‌تواند يک بسته اطلاعاتي کامل را به داخل شبکه تزريق کند که به اندازة کافي نشان براي ارسال آن وجود داشته باشد و در مقابل موقعي که تعداد نشانه‌ها بيشتر از حد TB شود، از بين مي‌روند. درصورتي که يک موج ضربهاي از بسته‌هاي اطلاعاتي به روتر برسند و تعداد بيت هاي آن بيشتر از تعداد نشانه‌هاي موجود در سطل باشد، تنها آن تعداد از بسته‌هايي که تعداد بيت آنها کمتر يا برابر نشانه‌ها باشند اجازه ارسال خواهند يافت و بقيه تا زماني که نشان براي آنها توليد شود، منتظر خواهند ماند.

روترهاي شبکه (NR) هم مسؤول توليد اطلاعات لازم در مورد وضعيت شبکه براي SR ها هستند که آنها با توجه به اين اطلاعات بتوانند پارامترهاي ذکر شده را به نحوي تنظيم کنند که احتمال حذف بسته‌ها را در يک شبکه حداقل کنند. اصولاً روشهايي که در عمل براي تنظيم اين پارامترها به ويژه نرخ توليد نشانه استفاده مي‌شود، روشهاي با نرخ ثابت هستند. به عنوان مثال از يک الگوريتم سطل سوراخ (LB) قبل از آن استفاده مي‌شود که با يک نرخ ثابت و بدون توجه به بقيه شرايط به توليد نشانه مي‌پردازد. اين نرخ ثابت معمولاً توسط مشخصه‌هاي ترافيکي و يا رزرو منابع تعيين مي‌شود.

در اين مقاله به دنبال يک مکانيزم انعطاف پذير در SR براي انتخاب پارامترهاي الگوريتم سطل نشانه‌دار بويژه پارامتر هستيم تا بتواند در هر لحظه با توجه به وضعيت شبکه در جلوي خود که در اين حالت نرخ حذف بسته‌ها در NR است و همچنين وضعيت پر يا خالي بودن بافرهاي روتر، بسته‌هاي اطلاعاتي را به سمت جلو ارسال کند. بدين منظور يک سيستم هوشمند مبتني بر يادگيري تقويتي طراحي مي‌شود که بتواند در هر حالت شبکه بهترين ممکن را که در واقع همان نرخ ارسال داده‌ها به سمت جلو است براي سطل نشان دار بياموزد. در اين طرح، عمل²⁸ مربوط به عامل يعني يک عدد بين 0 تا 100 است و با رابطه3 مقدار را مشخص مي‌کند:

(3)

که در اين رابطه با رابطه زير مشخص مي‌شود:

(4)

که به‌عنوان پهناي باند لينک ارتباطي امين پورت خروجي روتر که در واقع همان پورت مورد نظر ما است در نظر گرفته مي‌شود. به‌ عبارت ديگر عمل در هر لحظه ميزان درصد پهناي باندي را که عامل براي ارسال بسته‌هاي اطلاعاتي به سمت مقابل مي‌تواند استفاده کند، مشخص مي‌کند.

براي هرعامل شکل دهنده ترافيک، حالت شبکه با دو پارامتر مشخص مي‌شود، يکي درصد حذف بسته‌ها در مقابل SR که توسط پورت مورد نظر و يا به عبارتي امين پورت SR در لحظه ديده مي‌شود ( ) و ديگري درصد پر بودن بافر خروجي پورت مورد نظر در لحظه که به امين NR متصل است ( ).

پاداشي که اين عامل در مقابل انجام عمل در لحظه دريافت مي‌کند يعني ، مقدار مؤثر بودن عمل فوق را در راستاي بردن حالت شبکه از يک وضعيت به يک وضعيت بهتر نشان مي‌دهد. اين پاداش مقداري بين 0 تا 1 مي‌گيرد. براي محاسبه اين پاداش در هر لحظه از رابطه (5) استفاده مي‌شود:

(5)

که در آن از رابطه (6) محاسبه مي‌شود:

(6)

با درنظرگرفتن اينکه وضعيت حذف بسته‌ها در شبکه و درصد پر يا خالي بودن بافر پورت خروجي را نشان مي‌دهد و با توجه به اين مطلب که حالت ايده آل رسيدن به حالتي است که مقدار اين دو پارامتر در آن کم باشد، مي‌توان مقدار اين پاداش را توصيف کرد. به عبارت ديگر با تعريف اين پاداش سعي بر آن است که عامل به سمت حالات بهتر ترغيب شود و يا به عبارت ديگر در صفحه حالت از هر نقطه به سمت مبدأ نزديک شود. درشکل2 مدلي از سيستم ارايه شده براي هر عامل شکل دهنده ترافیک آمده است. همان طور که در اين شکل ديده مي‌شود عامل با پسخورگرفتن از محيط، پارامترهاي مورد نظر را در SR تنظيم مي‌کند.

شکل2: مدل سيستم پيشنهادي براي هر يک از عاملهاي

شکل‌دهنده ترافيک.

statespace براي محاسبه پارامترهاي ذکر شده در بالا، که همان درصد پربودن بافر خروجي پورت مورد نظر است به سادگي در داخل SR قابل محاسبه است. اما در مورد محاسبه دو مسأله مطرح مي‌شود. يکي اينکه چگونه مقدار اين پارامتر اندازه‌گيري شود و ثانياً اينکه چگونه مقدار اندازه‌گيري شده را به محل استفاده از آن يعني SR منتقل کنيم. براي رفع اين مسائل از مکانيزم ECN استفاده شده است که مي‌تواند به طور سريع و راحت، عمليات سيگنالينگ لازم براي انتقال اطلاعات لازم به SR را انجام دهد. اين مکانيزم بجاي آنکه بسته‌هاي اطلاعاتي را متناسب با ازدحام به‌وجود آمده حذف کند، آنها را با احتمالي متناسب با ازدحام در شبکه علامت گذاري مي‌کند. به طور ايده آل، امکان اينکه اطلاعات لازم را از NR ، يعني جايي که اين علامت گذاري انجام مي‌شود، به سمت SR ، يعني جايي که اين اطلاعات قرار است استفاده شود، به صورت پسخور مستقيم ارسال کنيم، وجود ندارد. به همين دليل بسته ACK²⁹ مربوط به پروتکل TCP مي‌تواند در اين زمينه کمک مناسبي کند. اگر گيرنده‌هاي TCP يک بسته اطلاعاتي را با علامت دريافت کنند، مي‌توانند اين علامت را از سرايندهاي IP اين بسته ( اين علامت در دو بيت قرار دارد که در IPv4 در فيلد TOS و در IPv6 در فيلد TC وجود دارد) کپي و در داخل سرايند TCP بسته ACK ارسالي به سمت فرستنده قرار دهند و به اين طريق، وضعيت ازدحام و حذف بسته‌ها را به SR برسانند. به دليل آنکه اين اطلاعات پسخور شده تنها در دو بيت قرار دارند، در ترافيک شبکه نقش زيادي ندارند[12و13].

SR پس از دريافت بسته‌هاي ACK و شمردن اينکه چه تعداد از آنها حاوي اطلاعات علامت گذاري شده هستند، در پايان هر چرخه شبکه به محاسبه طبق رابطه7 مي‌پردازد:

(7)

با داشتن اين دو پارامتر و تزريق آن به يک آشکار ساز حالت دو بعدي، در هر لحظه مي‌توان حالت فعلي شبکه را مشخص کرد. آشکار ساز حالت حاصل گسسته سازي³⁰ صفحه حالت³¹ است که اين گسسته سازي کاملاً به نظر طراح و شرايط سيستم بستگي دارد. در اين مقاله آشکار ساز حالت انتخاب شده

شکل3: آشکار ساز حالت ارائه شده براي عاملهاي

شکل دهنده ترافيک

مطابق شکل3 است که در آن محور افقي و محور عمودي را نشان مي‌دهد. در اين شکل تعداد کل حالات در نظر گرفته شده 20 عدد است که توسط خطوط شعاعي و قطري درکل صفحه حالت تقسيم بندي شده اند. انتخاب اين تعداد حالت و طرح گسسته سازي صفحه حالت بر اساس تجارب و اهداف مورد نظر انجام شده است. بديهي است هر چه تعداد اين حالات بيشتر شود، دقت بالاترمي‌رود ولي حجم محاسبات لازم افزايش مي‌يابد.

براي قالب چند عاملي تخصيص حافظه بافر نيز SR با يك حافظه بافر با حجم M بيت مشخص مي‌شود كه بين پورتهاي روتر به طور مساوي تقسيم مي‌شود و هر عامل مي‌تواند در اختيار بگيرد. راهكار استفاده شده در اين قسمت بر اين مبناست كه هرعامل تخصيص دهنده حافظه در هر پورت مي‌تواند مقداري از حافظه بافر در اختيار خود را در صورت احتياج نداشتن در اختيار عاملهاي تخصيص دهنده ديگري كه به آن نياز دارد بگذارد. ميزان حافظه‌اي كه هر عامل مي‌تواند با ديگران به اشتراك بگذارد كاملاً به نظر طراح بستگي دارد. در اين مقاله فرض برآن است كه هر عامل مي‌تواند نيمي از حافظه در اختيار خود را در اختيار ديگران گذارد. به عبارت ديگر هر عامل در ابتدا مي‌تواند نيمي از آنچه را مي‌تواند به طور ايستا دراختيار بگيرد، را استفاده کند و نيم ديگر را در5 مرحله 10درصدي استفاده کند و يا به ديگران قرض دهد. براي پياده‌سازي اين روش توسط عاملها، عمل هر عامل يعني يک عدد بين 0 تا 8 در نظر گرفته شده است. يعني اين که عامل احتياجي به حافظه بيش از آنچه در ابتدا دراختيار قرار گرفته است ندارد. يعني اين که ده درصد از بقيه حافظه خود را در اختيار مي‌گيرد و به همين ترتيب يعني اين که عامل3 واحد10 درصدي از بقيه پورتها قرض مي‌گيرد .طراحي اين عملها و همچنين نحوه اشتراک گذاشتن کاملاً به نظر طراح بستگي دارد. در اين طرح به دليل آنکه هر عامل بتواند در يک شرايط پايدار کار کند و همچنين اين فرض که معمولاً به طور ميانگين يک بار ترافيکي در شبکه وجود دارد تحت هر شرايطي 50 % از حافظه بافر هر پورت در اختيار آن قرار گرفته است. از طرف ديگر براي آنکه به دليل بافر شدن زياد بارهاي ترافيکي سنگين به Time Out شدن و ارسال مجدد در فنّاوري TCP/IP منجر نشود، نهايت حافظه اي که هر عامل توانسته قرض بگيرد به سه واحد10 درصدي يعني محدود شده است.

همانطور که قبلاً نيز ذکر شد، حالتهاي در نظر گرفته شده براي عاملهاي تخصيص دهنده دو پارامتر UBS³² و SR-DP است. UBS همانند قبل همان درصد پربودن بافر خروجي پورت مورد نظر و به عبارتي امين پورت در لحظه است که بهامين NR متصل است و با نمايش داده مي‌شود و SR-DP احتمال حذف بسته‌ها در ورودي پورتهاي SR و يا بهعبارتيامين پورت SR در لحظه است که با نمايش داده مي‌شود و در داخل SR قابل محاسبه است.

با داشتن اين دو پارامتر و تزريق آن به آشکار ساز حالت مشابه قسمت قبل مي‌توان درهر لحظه حالت فعلي شبکه را مشخص کرد. اين آشکار ساز شبيه آشکار ساز استفاده شده براي عاملهاي شکل دهنده ترافيک است با اين تفاوت که در آن محور افقي از و يا به عبارتي NR-DP به و يا به همان SR-DP تغيير يافته است.

محاسبه پاداش داده شده به هر عامل که در مقابل انجام عمل درلحظه دريافت مي‌کند، يعني نيز شبيه عاملهاي شکل دهنده ترافيک طبق روابط 8 و 9 محاسبه مي‌شود و عددي بين 0 و 1 است.

(8)

(9)

باز همچنان که در محاسبه اين پاداشها ديده مي‌شود، هدف ترغيب عاملها به سمت حالاتي بوده است که نرخ حذف بسته‌ها را در ورودي SR تا حد امکان کاهش دهند و در مقابل يک تخصيص بهينه و مفيد بين عاملها انجام دهند.

5- شبيه‌سازي

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

شکل4: روند نمای ترتیب انجام مراحل راهکارهای پیشنهادی.

5-1- قالب چند عاملي مبتني بر يادگيري تقويتي براي شکل‌دهي ترافيک بدون قالب تخصيص دهنده حافظه

در اين مدل فقط از قالب شکل دهنده ترافيک استفاده شده است. در اين قالب عاملهاي شکل دهنده ترافيک بر روي چهار پورت يک روتر قرار مي‌گيرند و مستقل از يکديگر باتوجه به شرايط شبکه به ارسال داده‌ها به سمت جلو مي‌پردازند. در اين مدل هر عامل در هر پورت تنها يک مقدار مشخص از حافظه بافر روتر را مي‌تواند به طور ثابت براي اين پورت در نظر بگيرد و در نتيجه احتياجي به قالب چند عاملي تخصيص دهنده حافظه در عقب روتر نيست. به عبارت ديگربافر موجود به طور ايستا و مساوي بين چهار پورت تقسيم مي‌شود.

5-1-1- نتايج شبيه‌سازي

در اين قسمت به شبيه‌سازي و ارزيابي مدل ارائه شده در محيط شبيه ساز توسعه داده شده مي‌پردازيم. شرايط شبيه‌سازي مطابق شکل4 است که در آن چهار عامل شکل دهنده ترافيک بر روي چهار پورت SR قرار گرفته اند. براي اينکه مدل توسعه داده شده در شرايط پويا و نزديک به واقعيت آزمايش شود و قابليتهاي آنها به ويژه در فرايند ارسال و شکل دهي داده‌ها بهتر ديده شود، فلوهاي ورودي مختلفي به آنها اعمال مي‌شود.

فلوهای ورودی که در این شبیه‌سازی‌ها در نظر گرفته شده به نحوی بوده است که بتواند کارایی قالبهای چند عاملی را در مقابل دینامیک های مختلف اعمالی مشخص کند. نتايج شبيه‌سازي براي پورت اول اين SkR در قسمتهاي اول تا ششم شکل6 آورده شده است.

شکل5: ساختار شبکه در نظر گرفته شده براي شبيه‌سازي راهکارهاي پيشنهادي.

همچنان که درقسمت اول اين شکل ديده مي‌شود فلو ورودي به اين پورت به صورت درصدي از پهناي باند ورودي به SR که در اين آزمايش 10Mb در نظر گرفته شده نشان داده مي‌شود. اين فلو تا چرخه حدود 20 در حدود 80 درصد پهناي باند ورودي و پس از آن تا چرخه حدود 60 در حدود 20 درصد پهناي باند ورودي و پس از آن در دو مرحله باز افزايش داشته است. به تبع آن مي‌توان نرخ ارسال عامل شکل دهنده ترافيک را به سمت NR درقسمت دوم شکل6 و دو پارامتر تصميم گيرنده اين عامل يعني درصد پر و خالي بودن بافر مربوط به هر پورت (UBS)³⁴ وميزان حذف بسته‌ها درNR (NR- DP)³⁵ را به ترتيب درقسمتهاي سوم و چهارم مشاهده كرد. نرخ حذف بسته‌ها در ورودي SR (SR-DP)³⁶ که به عنوان يکي از پارامترهاي عامل تخصيص دهنده حافظه در قسمتهاي بعدي از آن استفاده مي‌شود در قسمت پنجم و عمل تخصيص حافظه در قسمت ششم اين شکل نمايش داده شده است که در اين قسمت به دليل ثابت بودن حافظه بافر براي هر پورت در کل مسير فرايند، عامل در همه شرايط 100 درصد بافرخود را در اختيار داشته است. در اين شکل ديده مي‌شود که با اعمال اين فلو به ورودي پورت، عامل بدون در نظر گرفتن شرايط شبکه در پشت روتر و حذف بسته‌ها که در ورودي آن در حال اتفاق است (SR-DP) و همچنين مستقل از بقيه عاملها، ترافيک آمده را به نحوي به سمت NR ارسال کرده است که حذف بسته‌ها در مقابل خود يعني NR-DP را و همچنين ميزان استفاده از بافر خود يعني UBS را پايين نگه دارد. در اين شکل ديده مي‌شود که در کل مسير، به جز چرخه‌هاي اوليه، NR-DP صفر بوده ولي UBS بالا بوده است که اين به دليل ثابت بودن بافر پورت و زياد بودن نسبي حجم ترافيک ورودي بوده است.

شکل6: نتايج شبيه‌سازي عاملهای شکل دهنده ترافيک بدون تخصيص حافظه براي پورت اول روتر.

5-2- قالب چند عاملي مبتني بر يادگيري تقويتي براي شکل‌دهي ترافيک در کنار قالب چندعاملي تخصيص دهنده حافظه مبتني بر قوانين خبره

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

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

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

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

روند تخصيص حافظه بين اين عاملها همانند مدل توسعه داده شده در قسمتهاي قبلي است و فرض مي‌شود هر عامل در ابتدا نيمي از آنچه مي‌تواند به طور ايستا و ثابت (منظور از ايستا آن است که مانند قسمت قبل از همان ابتدا حافظه موجود بين آنها به طور مساوي تقسيم شود) در اختيار داشته باشد را دراختيار مي‌گيرد و نيم ديگر را در 5 مرحله مي‌تواند با بقيه عاملها (پورتها) به اشتراک بگذارد. به عبارت ديگر هر عامل مي‌تواند درهر مرحله 10% از حافظه خود را در اختيار ديگران بگذارد و يا در صورت نياز خود علاوه بر 50 % اوليه، آن را در اختيار بگيرد. دراين مدل فرض مي‌شود که هر عامل در صورت نياز به حافظه قرض داده شده خود در هر لحظه مي‌تواند آن را از ديگر عاملها پس بگيرد.

5-2-1- نتايج شبيه‌سازي

دراين قسمت فرض مي‌شود مدل ارائه شده، در داخل يک SR و مطابق شکل5 شبيه‌سازي مي‌شود. شرايط شبيه‌سازي دقيقاً مطابق با قسمت قبل درنظرگرفته مي‌شود تا در هر مرحله مزايا و معايب مدلهاي پيشنهادي به خوبي مشخص شود.

SR در نظر گرفته شده داراي چهار پورت خروجي است که دو قالب چند عاملي هر کدام با چهار عامل در داخل آن قرارمي‌گيرد. يکي از اين قالبها براي شکل دهي هوشمند ترافيک در چهار پورت به صورت مستقل و يکي از اين قالبها براي به اشتراک گذاشتن و اختصاص حافظه به هر پورت.

همانطور که در شکل7 براي پورت اول اين SR ديده مي‌شود، براي اين که اين عاملها بتوانند درشرايط نزديک به

شکل7: نتايج شبيه‌سازي عاملهای شکل دهنده ترافيک درکنارعاملهای تخصيص دهنده حافظه خبره براي پورت اول روتر.

واقعيت آزمون شوند و قابليتهاي آنها به ويژه در فرايند اشتراک گذاري حافظه بهتر ديده شود، و ازطرف ديگر بين قسمتهاي مختلف مقايسه صورت گيرد، فلوهاي ورودي مطابق با قسمت قبل به آنها اعمال مي‌شود. اگر به اين نتايج دقت شود و با نتايج قسمت قبل درشكل6 مقايسه شود اثر اضافه شدن قالب تخصيص دهنده حافظه در اين مدل در مقايسه با مدل قبلي که حافظه عامل ثابت بود و هيچ گونه تعاملي بين عاملها در به اشتراک گذاشتن حافظه وجود نداشت بهتر ديده مي‌شود. اگر دقت شود اضافه شدن اين قالب در کنار قالب شکل دهنده ترافيک و پويا شدن عمل تخصيص حافظه، نه تنها باعث شده نرخ حذف بسته‌ها در ورودي SR کاهش يابد، بلکه باعث شده نرخ ارسال عاملهاي شکل دهنده ترافيک به سمت NR نيز افزايش يابد در حالي که نرخ حذف در NR همچنان پايين است. اين موضوع نشانگر آن است که اين دو قالب با وجودي که مستقل از يکديگر هستند با يکديگردر تعاملند. به عبارت ديگر، موقعي که فلوورودي به اين پورت SR افزايش داشته است، عاملهاي تخصيص دهنده حافظه سعي کرده اند حافظه بافر بيشتري در اختيار آن قرار دهند و اين باعث شده تا عامل شکل دهنده ترافيک، UBS کمتري داشته باشد و به حالتي در نقشه آشکار ساز حالت خود برود که باعث افزايش نرخ ارسال آن شود.

5-3- قالب چند عاملي مبتني بر يادگيري تقويتي براي شکل دهي ترافيک درکنار قالب چند عاملي تخصيص دهنده حافظه مبتني بر يادگيري تقويتي

در اين مدل نيز مانند مدل قبلي از دو قالب چند عاملي که هر کدام داراي چهار عامل هستند استفاده مي‌شود. اين دو قالب در يک SR با چهارپورت خروجي قرار گرفته و به شکل دهي هوشمند ترافيک و همچنين تخصيص حافظه بين پورتها مي‌پردازند.

تفاوتي که در اين مدل با مدل قبلي وجود دارد، استفاده از يادگيري تقويتي براي آموزش عاملها در قالب تخصيص دهنده حافظه است. در مدل قبلي، فقط قالب شکل دهنده ترافيک از اين روش براي ارسال داده‌ها به سمت جلو استفاده مي‌کرد و قالب تخصيص دهنده حافظه فقط بر اساس شرايط شبکه که نرخ افت بسته در SR و همچنين UBS در نظرگرفته شده بود و استفاده از يک سري قوانين تجربي به تخصيص و اشتراک حافظه بين پورتها مي‌پرداخت. در اين مدل، اين عاملها با استفاده از اين پارامترها براي هر پورت و روش يادگيري تقويتي مي آموزند که چگونه اين عمل را به طور پويا و هوشمند انجام دهند. نحوه طراحي ساختار يادگيري تقويتي براي اين عاملها شبيه عاملهاي شکل دهنده ترافيک است با اين تفاوت که براي حالتهاي در نظر گرفته شده براي آن به جاي استفاده از NR- DP ، ازSR-DP استفاده مي‌شود که مانند UBS در داخل SR محاسبه مي‌شود.

5-3-1- نتايج شبيه‌سازي

در اين قسمت به ارزيابي مدل چند عاملي ارائه شده در قسمت قبلي پرداخت مي‌شود. سناريو و شرايط شبيه‌سازي دقيقاً مطابق با شرايط و سناريوي شبيه‌سازي مدلهاي قبلي است تا بتوان درمجموع بين مدلهاي ارائه شده مقايسه صورت گيرد و مزايا و معايب آنها مشخص گردد. دو قالب چند عاملي مبتني بر يادگيري تقويتي، هر کدام با چهار عامل، در يک SR با چهار پورت مطابق با شکل5 قرار مي‌گيرند. در يک قالب عاملها با همکاري يکديگر ترافيک آمده به سمت هر پورت را مطابق با وضعيت شبکه به سمت جلو شکل دهي مي‌کنند تا در حدامکان، از پهناي باند جلو استفاده بهينه شود تا حدي که نرخ حذف بسته‌ها در NR پايين باشد. در قالب ديگر عاملها با در نظر گرفتن وضعيت يکديگر در ميزان ترافيک آمده به سمت آنها و همچنين ميزان استفاده فعلي خود از حافظه بافر موجود، به تخصيص حافظه واشتراک آن بين يکديگر مي‌پردازند. فلو ورودي اعمالي به SR و براي هر پورت دقيقاً مطابق با فلو اعمالي در شبيه‌سازي مدلهاي قبلي است و به گونه اي بوده است تا ديناميک استفاده از پهناي باند و همچنين تخصيص حافظه به خوبي نمايانگر شود.

همانطور که در شکل8 براي يک پورت اين SR ديده مي‌شود، در اين حالت فرايند تخصيص حافظه پايدار و منظم بوده و از طرف ديگر، عاملهاي شکل دهنده ترافيک با پايين نگاه داشتن نرخ حذف بسته‌ها در NR بهتر توانسته اند از پهناي باند مقابل استفاده کنند.

شکل8: نتايج شبيه‌سازي عاملهای شکل دهنده ترافيک درکنارعاملهای تخصيص دهنده حافظه مبتني بر يادگيري تقويتي براي پورت اول روتر.

در اين شکل ديده مي‌شود که نرخ حذف بسته‌ها در ورودي SR نيز به صفر کاهش يافته است. اگر يک مقايسه متناظر بين اين نتايج و نتايج به دست آمده در مدل قبلي در شكل7 که در آن فرايند تخصيص حافظه بر اساس قوانين تجربي انجام مي‌شد صورت گيرد مشخص است که در مدل اخير علاوه بر بهبود وضعيت حذف بسته‌ها در SR و همچنين پايين تر بودن درصد UBS ، ترافيک شکل داده شده از SR به NR و يا به عبارتي ميزان استفاده از پهناي باند مقابل بيشتر شده است. در ضمن آنکه عاملها با در نظر گرفتن شرايط پروتکلهاي TCP/IP , علاوه برآن که منظم تر و پايدارتر به تخصيص حافظه پرداخته‌اند، از قرض گرفتن بيش ازحد مجاز حافظه پرهيز کردهاند.

6- نتايج

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

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

سپاسگزاری

بخشی از هزينه‌های تحقیقاتی این پروژه با حمايت مالی مرکز تحقیقات مخابرات ایران تأمين شده است که از اين حمايت قدردانی مي‌شود.

مراجع

[1] Park E., H. Choi, "Adaptive Token Bucket Algorithm for fair Bandwidth Allocation in Diffserve Networks". School of Electrical Engineering and computer science, Seoul National University, Seoul, Korea, 2002.

[2] Radhakrishnan S., S.V. Raghavan, K.Agrawala, "Flexible Traffic Shaper for High Speed Networks Design and comparative study with leaky Bucket", Computer Networks and ISDN systems 28, 453-469, 1996.

[3] Davison R.G., J.J.Hardwick, , ''Applying the agent paradigm to network management., BT Technology Journal., Vol 16.,No3.,125-136, 1998.

[4] Harle D., P.vila, ''A Multi Agent Approach to dynamic virtual path management in ATM networks'', Communication Division, Department of Electronics & Electrical Engineering, university of strathclyde, UK,2004.

[5] Kaebling L.P., M.L. Littman, A.W. Moore, "Reinforcement Learning: A Survey". Journal of Artificial Intelligence Research, 4: 237-285, 1996.

[6] Babuska R., L. Busoniu, ''Reinforcement Learning for MultiAgent systems", Delft Center for Systems and control,2004.

[7] Watkins C., ''Q-Learning. Machine Learning",8: 279-292, 1992.

[8] Chen T.M., S. Liu,"ATM Switching Systems", Artech House Publishers, 1995.

[9] Tanenbaum A.S, "Computer Networks" ,Prentice Hall ,2004.

[10] Cisco TechNotes, "Comparing Traffic policing and Traffic Shaping for Bandwidth Limiting”, Document ID: 19645

[11] Sutton R., A.G Barto, "Reinforcement learning: An Introduction", MIT Press, Cambridge, MA, USA, 1996.

[12] Ramakrishnan K., S. Floyd, "A Proposal to add Explicit congestion notification (ECN) to IP. "RFC 2481, 1999.

[13] Shames I., N. Najmaei, M. Zamani, A.A. Safavi, ''Application of Reinforcement learning in Development of a new Adaptive Intelligent Traffic Shaper'', ICMLA'06 , Orlando, Florida, December, 2006.

[14] Tumer K., Agogino A., "Agent Reward shaping for Alleviating Traffic Congestion" AAMAS'06 Hokkaido, Japan, May, 2006.

[15] Buffet O.,A. Dutech,F. Charpillet, ''Shaping Multi- Agent Systems with Gradient reinforcement Learning'',AAMASJ0'7, 2007.

[1] 1. نویسنده عهدهدار مکاتبات (safavi@shirazu.ac.ir)

[2] 1.Real Time

[3] 2.Teleconference

[4] 3.Distributed Computation

[5] 4.Quality of Service

[6] 5.Centralized

[7] 6.Scalability

[8] 7.Flow Control

[9] .Congestion Control

[10] .Preventive

[11] .Reactive

[12] .Traffic Shaping

[13] .Burst

[14] .Distributed Artificial Intelligence

[15] .Multi Agent

[16] .Reinforcement Learning

[17] 1.Bellman Methods

[18] 2.Action

[19] 3.Packet Drop

[20] 4.Buffer Allocation

[21] .Profile

[22] .Source Routers

[23] .Network Routers

[24] .Leaky Bucket

[25] .Token Bucket

[26] .Network Router

[27] .Source Router

[28] .Action

[29] .Acknowledgement Packet

[30] .Discretization

[31] .State Plain

[32] .Used Buffer Size

[33] 1.Expert

[34] .Used Buffer Size

[35] .NR-Drop

[36] .SR-Drop

Share To

Article Url

A new reinforcement learning based multi-agent method for traffic shaping and buffer allocation in routers

Rimag

Links

Related Centers

Technical Support

Official pages