خلاصه)
این مقاله به توصیف الگوریتم مسیر یابی Q برای مسیر یابی packet در ماجول تقویت کننده آموزش دهنده که در هر گروه از یک شبکه جابجا کننده قرار داده شده است می پردازیم. تنها ارتباطهای محلی برای هر گیرنده بکار می رود تا آمار آنها را در مرحله تصمیم های جهتیابی دقیق نگاه دارد که منجر به کاهش زمان ارسال می گردد. در آزمایشهای ساده که حاوی 36 گره است و شبکه بصورت بی قاعده ای متصل گردیده است. جهتیابی Q برتری حضور را نسبت به الگوریتم غیر قابل تطابق مبتنی بر محاسبات کوتاهترین مسیر ها به اثبات می رساند و قادر خواهد بود تا به میزان کافی جهتیابی انجام دهد حتی زمانی که ویژگیهای بسیار مهم شبیه سازی همانند load کردن شبکه اجازه می یابند تا بطور پویا تغییر پیدا کنند. این مقاله در برگیرنده بحثی در مورد حالت حد ووسط بین کشف میان برها و سیاستهای با ثبات نگه داشتن می باشد.
معرفی INTROSUCTION
حیطه تقویت دانش بنحو چشمگیری در طی چند سال اخیر رشد کردهاست البته به استثناء ماتریس [8,2] که کاربردهای موفقیت آمیزی کمتری در مقایسه با کارهای عملی و بزرگ دشته است. این مقابله نشان می دهد که کار عملی جهتیابی Pachat ها درون یک ارتباط شیبکه ای یک کاربرد طبیعی برای الگوریتم تقویت کننده دانش می باشد.
الگوریتم جهتیابی Q تا، متناسب با برخی الگوریتمهای جهتیابی packet توزیع شده [6,7] یاد می دهد که سیاست جهتیابی که در آن توزان ها تعداد پرشهای یک pachet را به حداقل می رسانند با احتمال انسداد مسیرهای شلوغ بدست خواهد آمد. این امر به کمک آزمایش روشهای جهتیابی گوناگونم و جمع آوری آمار درباره تصمیمهایی که زمان ارسال را به حداقل می رساند میسر خواهد شد. یادگیری مستمر و پیوسته خواهد بود، تنها از اطلاعات محلی استفاده می کند و بصورت بی قاعده بسیار قوی و یکپارچه عمل می کند و الگوهای ارتباط شبکه دائما در حال تغییر load شدن است.
آزمایشات در این مقاله به کمک شبیه ساز گسسته رویداد صورت گرفته است تا حول انتقال packet ها را در درون یک شبکه محلی بدست دهد و در بخش [5] توضیح کامل در این مورد داده شده است.
جهتیابی برای تقویت عملکرد یادگیری Routiny As A Reinforcement learniy 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 بسرعت به چنین تغییراتی واکنش نشان داد و قادر به مسیر یابی ترافیک بخوبی بود.