بخشی از مقاله
الگوریتم مسیر یابی
(خلاصه)
اين مقاله به توصيف الگوريتم مسير يابي Q براي مسير يابي packet در ماجول تقويت كننده آموزش دهنده كه در هر گروه از يك شبكه جابجا كننده قرار داده شده است مي پردازيم. تنها ارتباطهاي محلي براي هر گيرنده بكار مي رود تا آمار آنها را در مرحله تصميم هاي جهتيابي دقيق نگاه دارد كه منجر به كاهش زمان ارسال مي گردد. در آزمايشهاي ساده كه حاوي 36 گره است و شبكه بصورت بي قاعده اي متصل گرديده است. جهتيابي Q برتري حضور را نسبت به الگوريتم غير قابل تطابق مبتني بر محاسبات كوتاهترين مسير ها به اثبات مي رساند و قادر خواهد بود تا به ميزان كافي جهتيابي انجام دهد حتي زماني كه ويژگيهاي بسيار مهم شبيه سازي همانند load كردن شبكه اجازه مي يابند تا بطور پويا تغيير پيدا كنند. اين مقاله در برگيرنده بحثي در مورد حالت حد ووسط بين كشف ميان برها و سياستهاي با ثبات نگه داشتن مي باشد.
معرفي INTROSUCTION
حيطه تقويت دانش بنحو چشمگيري در طي چند سال اخير رشد كردهاست البته به استثناء ماتريس [8,2] كه كاربردهاي موفقيت آميزي كمتري در مقايسه با كارهاي عملي و بزرگ دشته است. اين مقابله نشان مي دهد كه كار عملي جهتيابي Pachat ها درون يك ارتباط شيبكه اي يك كاربرد طبيعي براي الگوريتم تقويت كننده دانش مي باشد.
الگوريتم جهتيابي Q تا، متناسب با برخي الگوريتمهاي جهتيابي packet توزيع شده [6,7] ياد مي دهد كه سياست جهتيابي كه در آن توزان ها تعداد پرشهاي يك pachet را به حداقل مي رسانند با احتمال انسداد مسيرهاي شلوغ بدست خواهد آمد. اين امر به كمك آزمايش روشهاي جهتيابي گوناگونم و جمع آوري آمار درباره تصميمهايي كه زمان ارسال را به حداقل مي رساند ميسر خواهد شد. يادگيري مستمر و پيوسته خواهد بود، تنها از اطلاعات محلي استفاده مي كند و بصورت بي قاعده بسيار قوي و يكپارچه عمل مي كند و الگوهاي ارتباط شبكه دائما در حال تغيير load شدن است.
آزمايشات در اين مقاله به كمك شبيه ساز گسسته رويداد صورت گرفته است تا حول انتقال packet ها را در درون يك شبكه محلي بدست دهد و در بخش [5] توضيح كامل در اين مورد داده شده است.
جهتيابي براي تقويت عملكرد يادگيري Routiny As A Reinforcement l earniy task
سياست جهتيابي يك packet پاسخگويي اين پرسش مي باشد كه : به كدام گروه مجاور مي بايستي گره فعلي packet هاي خود را ارسال كند در مقايسه با مقصد نهايي اش آزاد دريافت دارد؟ از آنجائيكه عملكرد اين روش به كمك كل زمان بدست آمده جهت ارسال يك packet اندازه گيري مي شود، هيچ سيگنال آموزش دهنده اي براي برآورد كردن مستيم يا بهبود دادن سياست تا زمانيكه يك packet نهايتا به مقصد خود مي رسد وجود ندارد. با اينهمه، با استفاده از تقويت يادگيري،روش مي بايستي سريعتر بروز شود و تنها از اطلاعات محلي استفاده كرد. فرض كنيد Q(x)(d,y) زماني باشد كه يك گروه x تخمين زده مي شود كه يك packet را به گره d به كمك گروه همسايه x يعني y تحويل دهد، كه در برگيرنده هر زماني است كه p مي بايستي در صفx صرف كند. در زمان ارسال p به y، x فورا برآورده y را براي زمان باقيمانده جهت ارسال بر مي گرداند در نتيجه:
اگر packet مقدار q واحد زمان در صف x صرف كند و s واحد زماني در انتقال بين گروه هاي y,x در نتجه x مي تواند برآورده خود را طبق رابطه زير بازبيني كند:
جايئكه پارامتر نرخ يادگيري است (معمولا در آزمايشس ما Q.5 در نظر گرفته مي شود.)
اگلوريتم منبع مي تواند در حكم نسخه اي از الگوريتم كوتاهترين مسير Bellman – Ford در نر گرفته شود كه (1) نمايش دهنده گامهاي مسير آن بصورت غير همزمان و online مي باشد و (2) طول مسير را صرفا به كمك تعداد پرسشها بلكه به كمك زمان ارسال كل اندازه گيري مي كند.
ما الگوريتم خود را مسير يابي Q نامگذاري مي كنيم تابع Q را((Qx(d,y) به كمك يك جدول بزرگ ارائه مي كنيم. ما همچنين بصورت تقريبي Qx را با يك شبكه خنثي مشخص كنيم كه به دانش آموز اجاز مي دهد تا انواع مختلفي از پارامتر هاي سيستم شامل اندازه صف محلي و زمان روز به تخمين مسافت آن تبديل و يكي كند. با اينهمه نتيجه هاي اين آزمايشات نا تمام ماند.
نتايج (Results)
ما الگوريتم مسير يابي Q را بر روي انواع توپولوژيهاي شبكه شامل مكعب 7 وجهي، شبكه تلفن 116 گره اي LATA و جدول 6*6 بي قاعده آزمايش كرده ايم. از آنجائيكه بار شبكه متفاوت است، ميزان متوسط زمان ارسال packet ها را در يك سيستم پس از فراگيري كه بر مبناي مسير يابي و روش آن بوده است اندازه گيري نمودم. و اين زمان ها را با آنهائيكه طرح مسير يابي ثابت بر مبناي كوتاهترين مسير مقايسه كرديم. نتايج بدين صورت بود كه در تمامي موارد، مسير يابي Q قادر خواهد بود تا سطح بالاتري از بار شبكه را نسبت به حاتي كه مي توانست مسير كوتاهتر را بپيمايد بحالت تعليق درآمده اين بخش نتايج كامل بر شبكه چهار گوش تصوير شده در شكل 1 را ارائه كند. تحت شرايط بار كم شبكه، نسبتا سريع تشخيص مي دهد كه packet ها را در طول كوتاهتري مسيرها به سوي مقصد شان مسير يابي كند. منحني عملكرد در برابر زمان كه در سمت چپ شكل 2 نمايش داده شده است اين موضوع را عنوان مي كند كه الگوريتم مسير يابي Q،
پس از دوره ابتدايي بي كفايتي زماني كه در حال شناخت توپولوژي شبكه است. همانند مسيرياب كوتاهترين مسير عمل مي كند كه تحت بار كم بهترين انتخاب خواهد بود. زمانيكه بار شبكه افزايش مي يابد، طرح كلي مسير يابي كوتاهترين مسير باي بهترين انتخاب بودن متوقف مي شود: اين روش سطوح در حال افزايش ترافيك را در نظر نمي گيرد و بزودي شبكه را با packet ها لبريز مي كند. در سمت راست شكل 2 نمايش دهنده جدول عملكرد بر زمان براي دو سطح مسير يابي در شرايط بار سنگين شبكه مي باشد. زمانيكه كوتاهترين مسير قادر به تحمل كردن بار packet نيست مسير يابي Q يك روش كار آمد مسير يابي را فرا مي گيرد. دليل آموختن موفقيت الگوريتم در دياگرام هاي خلاصه روش شكل 3 آشكار مي گردد اين دياگرامهاي براي هر يك از روشهاي ارائه شده نشان مي دهد چه مقدار از مسير نقطه به نقطه 35*36 از هر گره عبور مي كند . در سمت چپ شكل 3، كه سياست كوتاهترين مسير را خلاصه مي كند، در گره در مركز شبكه (كه 570 و 573 نامگذاري شده اند) در بسياري از كوتاهترين مسير ها قرار دارند و از اينرو زمانيكه بار شبكه زياد است مسدود شده اند. بر خلاف اينحالت دياگرام سمت راست مسير يابي Q را نشان مي دهد كه در شرايط بار زياد شبكه روشي را بزگريده است كه طي آن در مسيري طولاني تر از مسير مورد نياز و با وجود ترافيك (در قسمت بالاي شبكه) مسير يابي
را انجام مي دهد بگونه اي كه از انسداد در مركز شبكه پرهيز شود. نتيجه اوليه در شكل 4 بدست مي آيد، كه عملكرد هاي روش كوتاهترين مسير را با روش آموخته شده مسير يابي Q در مقياسهاي مختلف بار شبكه را با يكديگر مقايسه مي كند. هر نقطه نشاندهنده ميانه حد وسط زمان ارسال هر packet پس از اينكه مسير شناخته شده باشد، زمانيكه بار شبكه كم باشد الگوريتم مسير يابي Q تقريبا هماند الگوريتم كوتاهترين مسير عمل مي كند. ولي در زمان بار زياد روش كوتاهترين مسير منجر به تعداد زيادي از انسداد هاي شبكه اي مي گردد در حاليكه الگوريتم يادگيري به مسير يابي خود با موفقيت ادامه مي دهد
(شبكه هاي دائما در حال تغيير)Dynamically changing Netwosks
ايكي از مزاياي الگوريتم يادگيري نسبت به مسيريابي استاتيك، پتانسيل بكارگيري جهت تغييرات در پارامترهاي بسيار حياتي سيستم در زمان كار شبكه است ما الگوريتم مسير يابي را آزمايش كرديم، همچنين در شبكه هايي كه توپولوژي، الگوهاي ترافيك و ميزان بار بصورت ديناميك تغيير مي كردند:
توپولوژي
بصورت دستي ارتباطات را از شبكه در زمان شبيه سازي قطع كرديم. به لحاظ كيفي، مسير يابي Q بسرعت به چنين تغييراتي واكنش نشان داد و قادر به مسير يابي ترافيك بخوبي بود.
الگوهاي ترافيك:
ما شبيه سازي را جهت به حالت نوسان در آوردن و بين دو حالت مختلف الگوهاي درخواست در شبكه بي قاعده بطور دوره اي ايجاد كرديم: اولي در تمامي ترافي بين نيمه بالايي و پائيني شبكه هدايت شده بود و دومي در تمام زمان ترافيك بين نيمه راست و چپ حركت كرده بود. دوباره، پس از تنها يك دوره كوتاه نه چندان كار آمد مسير يابي هر زمان كه الگوي تقاضا جابجا مي شد، الگوريتم مسير يابي Q با موفقيت بكار بسته مي شد
سطح بار
زمان كه تمام سطح ترافيك در زمان شبيه سازي زياد مي شد، مسير يابي Q بسرعت سياست را پذيرفته تا مسير يابي packet در تنگناي جديد انجام دهد. با اينهمه زمانيكه ترافيك شبكه دوباره پائين آورده شد، بكارگيري كندتر صورت گرفت وهرگز در كوتاهترين مسير بهينه متمركز نمي شود. اين اثر در بخش بعد مورد بحث قرار مي گيرد
اكتشاف) Exploration
با تشابه به بدست آمده بين بروز كردن معادله مسيبر يابي Q و بازگشت كوتاهترين مسير Bellman- Ford، شگفت آور اين است كه هيج تفاوتي بين عملكرد و مسيريابي Q و كوتاهترين مسير كه در بار كم مسير يابي مي كند وجود ندارد كه اينحالت در شكل شماره 4 قابل مشاهده است.
با اينهمه، در نگاهي عميقتر به الگوريتم آشكار مي گردد كه مسير يابي Q نمي تواند بخوبي سياست راتنظيم كند تا كه ميان برها را پيدا نمايد. از آنجائيكه فقط بهترين برآورد مجاوز آن بروز مي شود. به طور مثال، اگر يك گره زمان ارسال را براي يك مسير بهينه خيلي دست بالا فرض كند، سپس آن مسير بهينه فرعي خواهد يافت كه زمان ارسال در طي مسير آن كمتر از برآورد بسيار زياد زمان ارسال مسير بهينه باشد. اين اشكال شناسايي Q در جامعه تقويت يادگيري بصورت گسترده اي مورد توجه قرار گرفت. و چندين روش اكتشافات جهت فائق آمدن بر آن پيشنهاد گرديد . يكي از معمول ترين آنها اين است كه الگوريتمي داشته باشيم با عملياتي كه در آن مقداري عمليات Random در طي زمان يادگيري اوليه صورت مي گيرد. ولي اين دستاورد در نقص زمينه مسير يابي توزيع شده است
1- شبكه دائما در حال تغييرات، از اينرو دوره اوليه اكتشاف هرگز به پايان نمي رسد و بطور قابل توجهي
2- ترافيك تصادفي اثر فوق العاده منفي برانسداد شبكه دارد. Packet ارسال شده در مسير و نمي بهينه تمايل دارند تا از تاخيرها صفي ايجاد نمايند كه packet هايي كه از اين صفها مي گذرند سرعتشان كاسته شده كه موجب افزوده شدن تاخير در صفها مي گردد بدليل اينكه كه گره ها تصميمات خود را بر اساس اطلاعات صرفا محلي مي گيرد، اين انسداد افزايش يافته عينا مسائلي را كه فراگيران سعي در حل آنها دارند تغيير مي دهند.
به جاي ارسال نمونه packet ها در يك مسير تصادفي، گره اي كه از تغيير الگوي كامل مسير يابي Q بهره مي برد درخواست اطلاعات خود را به گره هاي مجاور در هر زماني كه نياز به تصميم گيري داشته باشد مي فرستند. هر گره مجاور يك عدد ارسال مي كند كه از كانالي مجزا طوري استفاده مي كند كه انسداد را در مدل ما گسترش ندهد بدين گونه كه گره جاري برآوري از كل زمان رسيدن به مقصد انجام مي دهد. اين برآوردها جهت تنظيم مقادير (Qx (d,y) براي هر y مجاور صورت مي گيرد. زمانيكه ميان برها ظاهر مي گردند. و يا اگر عدم كفايت در سايستها موجود باشد اين اطلاعات سرعت در شبكه پخش مي شود و روش مورد نظر بصور مناسب آنرا تنظيم مي كند.
