استفاده از الگوريتم های الهام گرفته از کلونی مورچه ها در مسيريابی شبکه های کامپيوتری

صفحه 1:
استفاده ازالگوریتمهای الهام گرفته از کلونی مورچه ها در مسیریابی شبکه های کامپیوتری AntNet :Routing in Communication Networks 

صفحه 2:
Oo Oo Oo مروری بر مسیریابی در شبکه های کامپیوتری هوش ‎(swarm Intelligence) _as>‏ مسیریاپی با الهام از کلونی مورچه ها ‎AntNet CL ®‏ ‎AntNet CO ®‏ لا شیه سازی 0 ‎AntNet‏ 8 مقایسه ۸0۷۱6۲ با روشهای معمول مسیریابی 

صفحه 3:
مروری بر مسیریابی در شبکه های کامپیوتری ‎O‏ نیازهای حاصل از رشد شبکه ها ارتباطی ذا افزايش کارآیی مدیریت توزیع شده لا معیارهای موثر در ارزیابی روشهای *مسیریابی" ‎Throughput 1#‏ ‎Average Delay of packets @‏ ‏لا ویژگی خاص مساله "مسیریابی" 1# عدم قطعیت (0ا5:000۵5) ‎(Dynamic) ob» 5‏ ‎ 

صفحه 4:
مروری بر مسیریابی در شبکه های کامپیو تری« لآ مشکل روشهای موجود (05۳۳, 8۱۳) @ " توزیع ‎(Load Balancing) jb‏ اه *مسائل یادگیری تقویتی با حالت پنهان و روشهای حل آنها و( ۰ 00۱0۳۱۷ ۸۵۱۲ 

صفحه 5:
(swarm Intelligence) ‏هوش جمعی‎ Emergent Intelligence o ‏تعاملات محلی ء محدود و ساده اعضای یک دسته و جمعيت با محيط » منتهى به یک رفتار‎ # ‏5د‎ pele eee ‏این تعاملات غالبا غریزی بوده وبدون نظارت انجام می گیرند‎ 5# نتیجه آن غالبا یک رفتار پیچیده و هوشمندانه جمعی و بطور خاص انجام بعضی بهینه ساز های پیچیده است این نوع هوشمندی هیچ نیازی به کنترل مرکزی و دید کلی ‎Stigmergy Qo‏ :لیدم لصلی‌در تعافعلت 48 ارتباط با واسطه محيط ‏لانه سازى موريانه ها ‎age eal ‎ 

صفحه 6:
(wi) (Swarm Intelligence) ‏هوش جمعی‎ لا مزايابى كه هوش جمعى از آن بهره مى برند (scalability); i, i 0 خطا يذيرى(ع0167366غ غاناة2) ل[ عدم وجود كنترل متم ركز اتطبيق يذيرى عاملها سرعت انتقال تغییر تعاملات توزیع شده موجودات (modularity) «5 24, <3 خود کار بودن سیستم : کار کرد موازی 

صفحه 7:
(als!) (Swarm Intelligence) ‏هوش جمعی‎ لا كاربردها ‎Ad-hoc wireless network 1#‏ ‎Robotic ®‏ ‎Optimization »‏ ‎Routing @‏ 

صفحه 8:
مسيريابى با الهام از کلونی مورچه ها لآ ترشح اسيد فرميك در مسير حركت لآ دنبال كردن مسيرهاى با اسيد فرميك بيشتر aw Ol 

صفحه 9:
با الهام از کلونی مورچه ها (ک ۲ 6۳0۱ ۸۳۲-88560 در شبکه های‌تلفن Agent-Based Routing System (ARS) O ‏كاريرد بهينه از متابع شبكه‎ & Dorigo & Caro, + 2+ 4L\AntNet routing O AntNet CL ®@ AntNetcCO ® 

صفحه 10:
AntNet CL Forward Ant and Backward Ant 0 لا ویرایش (۱.۰): ارائه شده در سال ۱۹۹۷ توسط ۵0۲6 = در جدول مسیریاب به ازای هر مقصد ممکن (هر نود شبکه) یک ردیف وجود دارد. ‎Hf‏ لیستی از اطلاعات ۲۱ مسافرت آخر به ازای هر مقصد نگهداری می شود لآ میانگین و واریانس در یک پنجره بطول ۷۷ محاسبه می شود ‏واریانس زمان مسافرت | میانگین زمان مسافرت 1 2 ‎ ‎ ‎dest\neighbor | ni [2 ] 3 ‎ ‎ ‎2 or 96 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 11:
AntNet CL ‎Oo‏ هر ‎clio router‏ ¥ صف مى باشد ‎High priority queue !#‏ لا 206 03»10۷3۲0اها در آنقرار می‌گیرند » عبء‌یاو ۱۱۵۲۴۵۱ ۳ 206 ۴0۳۷۵۲۵ هاو بسته های‌داده در آنقرار می‌گیرند ‎ 

صفحه 12:
(a) ANtNet CL واریانس زمان ‎ 8::8)0(‏ ميانكين زمان مام | 4ه | 3ه | 2ه | 1ه | ‎dest\neighbor‏ ‏۳ ‎os [ox | oo fos 2 3‏ 1 2 ‏بل رط‎ j=1...N JEN, لا هر 201 داراي یک پشته است لا دو دسته بسته های 20۴ داریم 8 206 ۴۵۳۷۷۵۳۵ از مبدا بسه سمتعقصد حر کنف یکسند و لطافاتهسیر را در پسشته جح ‎Backward ant‏ از مقصد به سمسهبا باز ميكردد و جدايل! 101056 هارا بسروز می‌کسند ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 13:
(ast) ANtNet CL 2 به روز کردن جدول در 1.0 ۸۵۳۵6 ‎P,+(- r).d- Py)‏ بط ۶ ۶ ز آل عل 9 زر( -) -رط رط 1 گعز 1ج - ۳ ‎ae oe‏ ‎Xo‏ + و > وام 2+1 ‎ 

صفحه 14:
(au) ANtNet CL 1 به روز کردن جدول در 2.0 ۸۵۳۲۱6۲ (يظ -21 +یبط یبط P,- P,- rP ne N,n#f __ Jacobson/Karels nd 74 ٠ \ \ \ \ 4 ink تسام sup اسر \ تک (هلا -وسية) 7+ هار سر ل ماخ ‎Ty sus‏ 2 2 2 2_ 2 2-1 /)1- ( ye[0.7508] == 2 Gea) 7 ‏ص‎ 

صفحه 15:
(ast) ANtNet CL لا ۸06 ها بر لساس‌حجم داده ایسالب» مقاصد مختلفف رستاده می‌شوند ‎Oo‏ << 2 = P,=— 4 = 2 1+0) - 10 = 2 n=l لآ بروز كردن جدول در صورت از بين رفتن م1 | 2 بال حل رذ عو ۷ جر 

صفحه 16:
AntNet CO ‎Oo‏ زمان ‎queuing‏ مربوط به 201 ۲0۳۷۷3۲0 را محاسبه کرده ولی آنها راهم در عناعنا9 0۲0۲16۷ ‎high‏ = گذارد ‎a‏ ‎ ‏سرعت انتشار تاثير تغييرات افزايش مى يابد ‎ 

صفحه 17:
سازی لا تولید ترافیک ‎Session based "*‏ ا حجم ترافيك هر 5655/00 بر اساس پارامترهای ورودی تنظیم می شود لا متوسط و واریانس 1# تاد ‎Session‏ ‎Session Life Time 1#‏ ‎Throughput 1#‏ لا طول بسته ثابت و قابل تنظیم 

صفحه 18:
مقایسه با روشهای موجود Property | LS DV | Ants Space O(nrl) + Ofrh) | Ofrh) | O(rh) Time O(rnlogn) O(Id) | O(tdh) # of msgs | O(rl) O(ld) | O(/dh) Size of msg | O(e) Oth) | 0) A: number of hosts r: number of routers n: rth i: number of point-to-point links d: diameter of the network e: average number of link per router 

صفحه 19:
‎gt‏ بدست امه ‎Throughput «5 L621)! Oo‏ ‎L353 42 Delay ‏افزايش‎ Oo ‏لا‎ ‎ ‏رفتار بسيار خوب در ‎ ‎ ‎ ‎TIME [es] ‎ ‎ ‎ 

استفاده ازالگوريتمهای الهام گرفته از کلونی مورچه ها در مسيريابی شبکه های کامپيوتری ‏AntNet :Routing in Communication ‏Networks فهرست مطالب مروری بر مسيريابی در شبکه های کامپيوتری هوش جمعی ()swarm Intelligence مسيريابی با الهام از کلونی مورچه ها ‏AntNet CL  ‏AntNet CO  شبيه سازی مقايسه AntNetبا روشهای معمول مسيريابی ‏AntNet CO مروری بر مسيريابی در شبکه های کامپيوتری نيازهای حاصل از رشد شبکه های ارتباطی افزايش کارآيی مديريت توزيع شده معيارهای موثر در ارزيابی روشهای “مسيريابی” ‏Throughput  ‏Average Delay of packets  ويژگی خاص مساله “مسيريابی” عدم قطعيت ()Stochastic پويايی ()Dynamic مروری بر مسيريابی در شبکه های کامپيوتری (ادامه) مشکل روشهای موجود ()RIP ,OSPF توزيع بار ()Load Balancing نوسانات ترافيک()Traffic Oscillation •مسائل يادگيری تقويتی با حالت پنهان و روشهای حل آنها •Q-Learning •Ant Colony Systems هوش جمعی ‏ ()swarm Intelligence ‏Emergent Intelligence تعامالت محلی ،محدود و ساده اعضای يک دسته و جمعيت با محيط ،منتهی به يک رفتار جمعی هوشمندانه می شود اين تعامالت غالبا غريزی بوده وبدون نظارت انجام می گيرند نتيجه آن غالبا يک رفتار پيچيده و هوشمندانه جمعی و بطور خاص انجام بعضی بهينه سازی های پيچيده است اين نوع هوشمندی هيچ نيازی به کنترل مرکزی و ديد کلی نسبت به سيستم ندارد ‏ : Stigmergyايده اصلی در تعامالت ‏ النه سازی موريانه ها ترشح اسيد فرميک توسط مورچه ها ‏ ‏ ارتباط با واسطه محيط هوش جمعی (( )swarm Intelligenceادامه) مزايايي که هوش جمعی از آن بهره می برند مقياس پذيری()scalability تعامالت توزيع شده موجودات خطا پذيری()Fault tolerance عدم وجود کنترل متمرکز قابليت تطبيق پذيری عاملها سرعت انتقال تغيير تفکيک پذيری ()modularity خودکار بودن سيستم :نياز به نظارت انسان نيست کارکرد موازی )) (ادامهswarm Intelligence( هوش جمعی کاربردها Ad-hoc wireless network Robotic Optimization Routing     مسيريابی با الهام از کلونی مورچه ها ترشح اسيد فرميک در مسير حرکت دنبال کردن مسيرهای با اسيد فرميک بيشتر تبخير )(کاربرد مسيريابی با الهام از کلونی مورچه ها در شبکه های تلفنAnt-Based Control  Agent-Based Routing System (ARS)  کاربرد بهينه از منابع شبکه  AntNet CL  AntNet CO  Dorigo & Caro ارائه شده توسطAntNet routing  AntNet CL ‏Forward Ant and Backward Ant  ويرايش ( :)1.0ارائه شده در سال 1997توسط Dorigo در جدول مسيرياب به ازای هر مقصد ممکن (هر نود شبکه) يک رديف وجود دارد. ليستی از اطالعات nمسافرت آخر به ازای هر مقصد نگهداری می شود ميانگين و واريانس در يک پنجره بطول Wمحاسبه می شود واريانس زمان مسافرت ميانگين زمان مسافرت ‏n4 ‏n3 ‏n2 ‏n1 ‏dest\neighbor 3 12 0.3 0.4 0.15 0.15 1 4 14 0.2 0.1 0.6 0.1 2 2 13 0.1 0.1 0.4 0.4 3 AntNet CL صف می باشد2 دارایrouter هر High priority queue  ها در آن قرار می گيرندbackward ant  Normal queue  ها و بسته های داده در آن قرار می گيرندForward ant  AntNet CL (ادامه) واريانس زمان )trip(σ ميانگين زمان trip )(μ ‏n4 ‏n3 ‏n2 ‏n1 ‏dest\neighbor 3 12 0.3 0.4 0.15 0.15 1 4 14 0.2 0.1 0.6 0.1 2 2 13 0.1 0.1 0.4 0.4 3 ‏Pji 1; j 1,...,N ‏ ‏i N ‏k ‏ هر antدارای يک پشته است دو دسته بسته های antداريم Forward ant از مبدا به سمت مقصد حرکت می کند و اطالعات مسير را در پشته خود ذخيره می کند. Backward ant از مقصد به سمت مبدا باز میگردد و جداول routerها را بروز می کند )(ادامه Pdf  Pdf  (1 r' ).(1 Pdf ) AntNet 1.0 به روز کردن جدول در Pdj  Pdj  (1 r' )Pdj ; j  Nk , j  f T r'   c  n1  c 1 if n n  xn1 n 1 T 1 c AntNet CL )(ادامه AntNet CL AntNet 2.0 به روز کردن جدول در Pfd  Pfd  r(1 Pfd ) Pnd  Pnd  rPnd n Nk , n  f Jacobson/Karels   Isup  Iinf  Wbest  r c1   c2   T   (Isup  Iinf )  (T  Iinf )  Isup   z* ( / w) z 1/ (1  )   [0.75,0.8]  d   d   (Tk d   d )  d2   d2   ((ok d   d )2   d2 ) AntNet CL (ادامه) Ant ها بر اساس حجم داده ارسالی به مقاصد مختلف فرستاده می شوند خاص آحتمال رفتن به يک مسير ‏q ‏Pnd  Ln ‏Ln 1 Nk n ‏  ‏Pnd )1  ( Nk  1 ‏qn ‏ ‏n ' ‏1 بروز کردن جدول در صورت از بين رفتن linkkj ‏Pdj ‏Pdi Pdi  ‏ i  j i, j  Nk ‏nk  1 AntNet CO زمان queuingمربوط به forward antرا محاسبه کرده ولی آنها را هم در high priority queueمی گذارد سرعت انتشار تاثير تغييرات افزايش می يابد شبيه سازی توليد ترافيک ‏Session based  حجم ترافيک هر Sessionبر اساس پارامترهای ورودی تنظيم می شود متوسط و واريانس تعداد Session ‏Session Life Time  ‏Throughput  طول بسته ثابت و قابل تنظيم مقايسه با روشهای موجود h: number of hosts r: number of routers n: r+h l: number of point-to-point links d: diameter of the network per router e: average number of link نتايج بدست آمده افزايش قابل توجه افزايش Delayدر ترافيک سبک رفتار بسيار خوب در صورت بروز شکست در سيستم ‏Throughput