• صفحه اصلی
  • بهبود مسیریابی جهت کنترل ازدحام در شبکه¬هاب مبتنی بر نرم¬افزار با استفاده از کنترلرهای توزیع¬شده

اشتراک گذاری

آدرس مقاله


کد مقاله : 202007188338 بازدید : 15998 صفحه: 49 - 72

20.1001.1.27170414.1398.11.39.3.9

نوع مقاله: پژوهشی

بهبود مسیریابی جهت کنترل ازدحام در شبکه¬هاب مبتنی بر نرم¬افزار با استفاده از کنترلرهای توزیع¬شده

محورهای موضوعی : عمومى

سعید بختیاری 1 , اردشیر آذرنژاد 2 *

1 - دانشگاه علوم انتظامی امین، تهران
2 - فناوری اطلاعات دانشگاه آزاد اسلامی واحد تهران مرکزی

تاریخ دریافت : 1398/04/13 تاریخ پذیرش : 1398/04/13 تاریخ انتشار : 1399/04/15

کلید واژه: شبکه¬های مبتنی بر نرم¬افزار, کنترلرهای توزیع¬شده, قراردادن کنترلرها, خوشه¬بندی, کنترل ازدحام, Software Defined Networking, Distributed Controllers, Controller Placement, Clustering, Congestion Control,

چکیده مقاله :

شبکه های مبتنی بر نرم افزار (SDN) برای استفاده در تعیین مسیریابی ترافیک شبکه قابل انعطاف هستند، زیرا سطح داده ای و سطح کنترلی را از یکدیگر تفکیک می کنند. یکی از چالش های بزرگی که پیش روی شبکه‌های مبتنی بر نرم‌افزار قرار گرفته است، انتخاب مکان هایی مناسب برای قرار دادن و توزیع کنترلرها (کنترل کننده ها) است؛ به گونه‌ای که بتوان تأخیر بین کنترلرها و سوئیچ ها را در شبکه‌های گسترده کاهش داد. در همین راستا اغلب روش‌های ارائه شده بر روی کاهش تأخیر متمرکز بوده‌اند. ولی تأخیر تنها یکی از عواملی است که در کارائی شبکه و کاهش هزینه ی کلی بین کنترلرها و سوئیچ‌های مرتبط با آن‌ها نقش دارد. این مقاله به بررسی عوامل بیشتری برای کاهش هزینه بین کنترلر ها و سوئیچ ها نظیر ترافیک لینک های ارتباطی می پردازد. به همین منظور یک الگوریتم مبتنی برخوشه بندی برای بخش بندی شبکه ارائه می شود. با بهره گیری از این الگوریتم می‌توان تضمین کرد که هر بخش از شبکه می‌تواند حداکثر هزینه (شامل تأخیر و ترافیک موجود روی لینک ها) را در بین کنترلر و سوئیچ های مربوط به آن کاهش دهد. در این مقاله، با بکارگیری از Topology Zoo، شبیه‌سازی‌های گسترده‌ای تحت توپولوژی های واقعی شبکه انجام شده است. نتایج شبیه سازی ها نشان می دهد در شرایطی که احتمال ازدحام در شبکه بالا می رود، الگوریتم پیشنهادی با شناسایی لینک های گلوگاه در مسیرهای ارتباطی هر گره با سایر گره ها، توانسته به خوبی ازدحام را در شبکه کنترل نماید. لذا، با در نظر گرفتن دو معیار تأخیر و میزان مشغول بودن لینک ها، فرآیند قرارگیری و توزیع کنترلر ها را در عمل خوشه-بندی با دقت بالاتری انجام می دهد. با این کار، میانگین حداکثر هزینه ی انتها به انتها بین هر کنترلر و سوئیچ های مربوط به آن به ترتیب در توپولوژی های Chinanet کشور چین، Uunet کشور آمریکا، DFN کشور آلمان، و Rediris کشور اسپانیا به اندازه ی 4694/41، 2853/29، 3805/21 و 4829/46 درصد کاهش یافته است.

چکیده انگلیسی:

Software defined networks (SDNs) are flexible for use in determining network traffic routing because they separate data plane and control plane. One of the major challenges facing SDNs is choosing the right locations to place and distribute controllers; in such a way that the delay between controllers and switches in wide area networks can be reduced. In this regard, most of the proposed methods have focused on reducing latency. But latency is just one factor in network efficiency and overall cost reduction between controllers and related switches. This article examines more factors to reduce the cost between controllers and switches, such as communication link traffic. In this regard, a cluster-based algorithm is provided for network segmentation. Using this algorithm, it can be ensured that each part of the network can reduce the maximum cost (including delays and traffic on links) between the controller and its related switches. In this paper, using Topology Zoo, extensive simulations have been performed under real network topologies. The results of the simulations show that when the probability of congestion in the network increases, the proposed algorithm has been able to control the congestion in the network by identifying the bottleneck links in the communication paths of each node with other nodes. Therefore, considering the two criteria of delay and the degree of busyness of the links, the process of placing and distributing the controllers in the clustering operation has been done with higher accuracy. By doing so, the maximum end-to-end cost between each controller and its related switches, in the topologies Chinanet of China, Uunet of the United States, DFN of Germany, and Rediris of Spain, is decreased 41.2694%, 29.2853%, 21.3805% and 46.2829% respectively.

منابع و مأخذ:

1.N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, et al., "OpenFlow: enabling innovation in campus networks," ACM SIGCOMM Computer Communication Review, vol. 38, pp. 69-74, 2008.
2.W. Miao, G. Min, Y. Wu, H. Wang, and J. Hu, "Performance modelling and analysis of software-defined networking under bursty multimedia traffic," ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM), vol. 12, p. 77, 2016.
3.H. Huang, H. Yin, G. Min, H. Jiang, J. Zhang, and Y. Wu, "Data-driven information plane in software-defined networking," IEEE Communications Magazine, vol. 55, pp. 218-224, 2017.
4.D. Levin, M. Canini, S. Schmid, F. Schaffert, and A. Feldmann, "Panopticon: Reaping the Benefits of Incremental {SDN} Deployment in Enterprise Networks," in 2014 {USENIX} Annual Technical Conference ({USENIX}{ATC} 14), 2014, pp. 333-345.
5.N. Feamster, J. Rexford, and E. Zegura, "The road to SDN: an intellectual history of programmable networks," ACM SIGCOMM Computer Communication Review, vol. 44, pp. 87-98, 2014.
6.OpenFlow Switch Specification Version 1.5.1. Available: https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/openflow/openflow-switch-v1.5.1.pdf
7.B. A. A. Nunes, M. Mendonca, X.-N. Nguyen, K. Obraczka, and T. Turletti, "A survey of software-defined networking: Past, present, and future of programmable networks," IEEE Communications Surveys & Tutorials, vol. 16, pp. 1617-1634, 2014.
8.A. Ominike Akpovi, A. Adebayo, and F. Osisanwo, "Introduction to Software Defined Networks (SDN)," 2016.
9.W. Stallings, "Software-defined networks and openflow," The internet protocol Journal, vol. 16, pp. 2-14, 2013.
10.G. Wang, Y. Zhao, J. Huang, and W. Wang, "The controller placement problem in software defined networking: A survey," IEEE Network, vol. 31, pp. 21-27, 2017.
11.B. Heller, R. Sherwood, and N. McKeown, "The controller placement problem," in Proceedings of the first workshop on Hot topics in software defined networks, 2012, pp. 7-12.
12.G. Yao, J. Bi, Y. Li, and L. Guo, "On the capacitated controller placement problem in software defined networks," IEEE Communications Letters, vol. 18, pp. 1339-1342, 2014.
13.S. Khuller and Y. J. Sussmann, "The capacitated k-center problem," SIAM Journal on Discrete Mathematics, vol. 13, pp. 403-418, 2000.
14.Y. Hu, T. Luo, W. Wang, and C. Deng, "On the load balanced controller placement problem in Software defined networks," in 2016 2nd IEEE International Conference on Computer and Communications (ICCC), 2016, pp. 2430-2434.
15.L. Han, Z. Li, W. Liu, K. Dai, and W. Qu, "Minimum control latency of SDN controller placement," in 2016 IEEE Trustcom/BigDataSE/ISPA, 2016, pp. 2175-2180.
16.Y. Zhang, N. Beheshti, and M. Tatipamula, "On resilience of split-architecture networks," in 2011 IEEE Global Telecommunications Conference-GLOBECOM 2011, 2011, pp. 1-6.
17.Y.-N. Hu, W.-D. Wang, X.-Y. Gong, X.-R. Que, and S.-D. Cheng, "On the placement of controllers in software-defined networks," The Journal of China Universities of Posts and Telecommunications, vol. 19, pp. 92-171, 2012.
18.L. F. Müller, R. R. Oliveira, M. C. Luizelli, L. P. Gaspary, and M. P. Barcellos, "Survivor: An enhanced controller placement strategy for improving SDN survivability," in 2014 IEEE Global Communications Conference, 2014, pp. 1909-1915.
19.Y. Jimenez, C. Cervelló-Pastor, and A. J. García, "On the controller placement for designing a distributed SDN control layer," in 2014 IFIP Networking Conference, 2014, pp. 1-9.
20.Y. Hu, W. Wang, X. Gong, X. Que, and S. Cheng, "On reliability-optimized controller placement for software-defined networks," China Communications, vol. 11, pp. 38-54, 2014.
21.M. Tanha, D. Sajjadi, and J. Pan, "Enduring node failures through resilient controller placement for software defined networks," in 2016 IEEE Global Communications Conference (GLOBECOM), 2016, pp. 1-7.
22.A. Sallahi and M. St-Hilaire, "Optimal model for the controller placement problem in software defined networks," IEEE communications letters, vol. 19, pp. 30-33, 2015.
23.H. K. Rath, V. Revoori, S. M. Nadaf, and A. Simha, "Optimal controller placement in Software Defined Networks (SDN) using a non-zero-sum game," in Proceeding of IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks 2014, 2014, pp. 1-6.
24.A. Ruiz-Rivera, K.-W. Chin, and S. Soh, "GreCo: An energy aware controller association algorithm for software defined networks," IEEE communications letters, vol. 19, pp. 541-544, 2015.
25.M. T. I. ul Huque, G. Jourjon, and V. Gramoli, "Revisiting the controller placement problem," in 2015 IEEE 40th Conference on Local Computer Networks (LCN), 2015, pp. 450-453.
26.A. Sallahi and M. St-Hilaire, "Expansion model for the controller placement problem in software defined networks," IEEE Communications Letters, vol. 21, pp. 274-277, 2017.
27.D. Hock, M. Hartmann, S. Gebert, M. Jarschel, T. Zinner, and P. Tran-Gia, "Pareto-optimal resilient controller placement in SDN-based core networks," in Proceedings of the 2013 25th International Teletraffic Congress (ITC), 2013, pp. 1-9.
28.S. Lange, S. Gebert, T. Zinner, P. Tran-Gia, D. Hock, M. Jarschel, et al., "Heuristic approaches to the controller placement problem in large scale SDN networks," IEEE Transactions on Network and Service Management, vol. 12, pp. 4-17, 2015.
29.D. Tuncer, M. Charalambides, S. Clayman, and G. Pavlou, "Adaptive resource management and control in software defined networks," IEEE Transactions on Network and Service Management, vol. 12, pp. 18-33, 2015.
30.J. Liao, H. Sun, J. Wang, Q. Qi, K. Li, and T. Li, "Density cluster based approach for controller placement problem in large-scale software defined networkings," Computer Networks, vol. 112, pp. 24-35, 2017.
31.B. Zhang, X. Wang, L. Ma, and M. Huang, "Optimal controller placement problem in Internet-oriented software defined network," in 2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC), 2016, pp. 481-488.
32.G. Wang, Y. Zhao, J. Huang, and Y. Wu, "An effective approach to controller placement in software defined wide area networks," IEEE Transactions on Network and Service Management, vol. 15, pp. 344-355, 2017.
33.M. F. Bari, A. R. Roy, S. R. Chowdhury, Q. Zhang, M. F. Zhani, R. Ahmed, et al., "Dynamic Controller Provisioning in Software Defined Networks," in CNSM, 2013, pp. 18-25.
34.Y. Hu, T. Luo, N. C. Beaulieu, and C. Deng, "The energy-aware controller placement problem in software defined networks," IEEE Communications Letters, vol. 21, pp. 741-744, 2017.
35.G. Ishigaki and N. Shinomiya, "Controller placement algorithm to alleviate burdens on communication nodes," in 2016 International Conference on Computing, Networking and Communications (ICNC), 2016, pp. 1-5.
36.SDN-Enabled Programmatic Control of the Network. Available: http://www.brocade.com/en/backend-content/ pdf-page.html?/content/dam/common/documents/content-types/solution-brief/brocade-mlx-service-provider-sb.pdf
37.Corsa’s DP2100 SDN switching and routing platform. Available: http://www.corsa.com/products/dp2100/
38.R. Daniels and D. Whittaker. (2015). Benchmarking the SDN Switch. Available: https://www.opennetworking.org/ images/stories/sdn-solution-showcase/germany2015/Spirent%20-%20Benchmarking%20the%20SDN%20Switch.pdf
39.C. Veness, "Calculate distance and bearing between two Latitude/Longitude points using Haversine formula in JavaScript," Movable Type Scripts, 2011.
40.G. Wang, Y. Zhao, J. Huang, and R. M. Winter, "On the data aggregation point
placement in smart meter networks," in 2017 26th International Conference on Computer Communication and Networks (ICCCN), 2017, pp. 1-6. 41.S. Skiena, "Dijkstra’s algorithm," in Implementing discrete mathematics: combinatorics and graph theory with mathematica, ed: Addison-Wesley Reading, MA, 1990, pp. 225-227.
42.S. Knight, H. X. Nguyen, N. Falkner, R. Bowden, and M. Roughan, "The internet topology zoo," IEEE Journal on Selected Areas in Communications, vol. 29, pp. 1765-1775, 2011.
43.(2019, 02/05/2019). The Internet Topology Zoo. Available: http://www.topology-zoo.org/
متن کامل:


 

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

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

سال یازدهم، شماره­های 39و40، بهار و تابستان 1398

 صص: 49-72

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

 

 

بهبود مسیریابی جهت کنترل ازدحام در شبکه­هاب مبتنی بر نرم­افزار با استفاده از کنترلرهای توزیع­شده

 

* سعید بختیاری             **اردشیر آذرنژاد            

* استادیار دانشگاه علوم انتظامی امین، تهران

**کارشناسی­ارشد فناوری اطلاعات دانشگاه آزاد اسلامی واحد تهران مرکزی

تاریخ دریافت: 13/04/ 1398 تاریخ پذیرش: 24/03/1399

چکیده

شبکه­های مبتنی بر نرم­افزار (SDN) برای استفاده در تعیین مسیریابی ترافیک شبکه قابل انعطاف هستند، زیرا سطح داده­ای و سطح کنترلی را از یکدیگر تفکیک می­کنند. یکی از چالش­های بزرگی که پیش روی شبکه‌های مبتنی بر نرم‌افزار قرار گرفته است، انتخاب مکان­هایی مناسب برای قرار­دادن و توزیع کنترلرها (کنترل­کننده­ها) است؛ به گونه‌ای که بتوان تأخیر بین کنترلرها و سوئیچ­ها را در شبکه‌های گسترده کاهش داد. در همین راستا اغلب روش‌های ارائه شده بر روی کاهش تأخیر متمرکز بوده‌اند. ولی تأخیر تنها یکی از عواملی است که در کارائی شبکه و کاهش هزینه­ی کلی بین کنترلرها و سوئیچ‌های مرتبط با آن‌ها نقش دارد. این مقاله به بررسی عوامل بیشتری برای کاهش هزینه بین کنترلر­ها و سوئیچ­ها نظیر ترافیک لینک­های ارتباطی می­پردازد. به همین منظور یک الگوریتم مبتنی برخوشه­بندی برای بخش­بندی شبکه ارائه می­شود. با بهره گیری از این الگوریتم می‌توان تضمین کرد که هر بخش از شبکه می‌تواند حداکثر هزینه (شامل تأخیر و ترافیک موجود روی لینک­ها) را در بین کنترلر و سوئیچ­های مربوط به آن کاهش دهد. در این مقاله، با بکارگیری از Topology Zoo، شبیه‌سازی‌های گسترده‌ای تحت توپولوژی­های واقعی شبکه انجام شده است. نتایج شبیه­سازی­ها نشان می­دهد در شرایطی که احتمال ازدحام در شبکه بالا می­رود، الگوریتم پیشنهادی با شناسایی
لینک­های گلوگاه در مسیرهای ارتباطی هر گره با سایر گره­ها، توانسته به خوبی ازدحام را در شبکه کنترل نماید. لذا، با در نظر گرفتن دو معیار تأخیر و میزان مشغول بودن لینک­ها، فرآیند قرارگیری و توزیع کنترلر­ها را در عمل خوشه­بندی با دقت بالاتری انجام می­دهد. با این کار، میانگین حداکثر هزینه­ی انتها به انتها بین هر کنترلر و سوئیچ­های مربوط به آن به ترتیب در توپولوژی­های Chinanet کشور چین، Uunet کشور آمریکا، DFN کشور آلمان، و Rediris کشور اسپانیا به اندازه­ی 4694/41، 2853/29، 3805/21 و 4829/46 درصد کاهش یافته است.

 

واژه­های كليدي: شبکه­های مبتنی بر نرم­افزار، کنترلرهای توزیع­شده، قراردادن کنترلرها، خوشه­بندی، کنترل ازدحام.

 

نویسنده عهده­دار مکاتبات : سعید بختیاری  saeid.bakhtiarii@chmail.ir

 

 

1- مقدمه

افزایش فناوری‌های رایانشی جدید اعم از کلان داده‌ها1، اینترنت اشیاء2، و رایانش ابری3 باعث شده تا تغییرات قابل ملاحظه‌ای در روش ذخیره‌سازی، گردآوری و انتقال اطلاعات و داده‌ها صورت گیرد. در کنار این روندهای رایانشی جدید، چالش‌های جدیدی اعم از مدیریت و ارتقای شبکه، استفاده‌ی بهینه از منابع، انتقال سریع داده‌ها نیز پدید آمده است. به منظور غلبه بر این چالش ها، از شبکه­های مبتنی بر نرم­افزار (SDN)4 به عنوان یک الگوی مطلوب برای شبکه‌های نسل آینده استفاده می‌شود. شبکه­های نرم‌افزار محور در مقایسه با شبکه‌های متعارف از اصل تفکیک سطح کنترلی5 و سطح داده‌ای6 بهره می‌برد. این بدین معنا است که سطح کنترلی در این شبکه‌ها به وسیله‌ی یک مجموعه از کنترلرهای7 اختصاصی شکل گرفته و هر کدام از آن‌ها می‌توانند یک یا چند سوئیچ که وظیفه‌ی هدایت بسته‌های داده‌ای به سمت جلو را بر عهده دارند را مدیریت نمایند. در نتیجه توابع کنترلی و مدیریتی در این شبکه‌ها به گونه‌ای طراحی می‌شوند که خدمات شبکه و برنامه­های کاربردی، از زیرساختار زیرین آن مجزا باشند.

در شبکه­های نرم‌افزار محور، کنترلرِ مبتنی بر نرم‌افزار نقش یک واسط هوشمند شبکه را بازی می‌کند و سوئیچ‌های شبکه نیز نقش دستگاه‌های ساده‌ای برای هدایت و فوروارد بسته‌های داده‌ای به سمت جلو را بر عهده دارند که البته می‌توان این فرآیند فوروارد را از طریق واسط‌های بازی مانند OpenFlow برنامه نویسی کرد [1]. در صورتی که یک بسته وارد یک سوئیچ شده ولی جدول جریان در این سوئیچ هیچ تطابقی با الگوی این بسته نداشته باشد، سوئیچ اقدام به ایجاد یک بسته‌ی درخواست نموده و آن را برای کنترلر مربوطه ارسال می‌کند. کنترلر پس از دریافت این درخواست اقدام به ارسال یک سیاست فوروارد جدید نموده و بر همین اساس سوئیچ اقدام به بروز رسانی جدول جریان خود می‌کند. پس از آن، بسته‌ی داده‌ای بر مبنای جدول جریان که بروز شده است تحویل داده می‌شود.

همان‌طور که در این مدل تشریح شده است، همه‌ی توابع موجود در SDN از طریق مبادله‌ی مکرر پیام ها در بین کنترلر ها و سوئیچ­ها صورت می‌گیرد. بنابراین، موقعیت کنترلرها نقش قابل ملاحظه‌ای در مبادله‌ی پیام داشته و از این رو بر روی کارائی SDN تأثیر می‌گذارد. مسأله‌ی تعیین موقعیت‌هایی مناسب برای قرار دادن و توزیع کنترلرها را مسأله‌ی گمارش کنترلرها8 می­گویند. در این مسأله به دنبال آن هستیم که چطور می‌توان کنترلرها را در یک شبکه‌ی مبتنی بر نرم­افزار قرار داده و سوئیچ‌های مربوطه را به گونه‌ای به این کنترلرها تخصیص داد تا به هدف مد نظر برسیم. گمارش کنترلرها اهمیت بسیاری در شبکه‌های گسترده9 دارد که دلیل آن را می‌توان ناشی از توپولوژی نامتعارف و تأخیر بالا در انتشار بسته‌های داده‌ای دانست.

به منظور حل مسأله‌ی گمارش کنترلرها در شبکه‌های نرم‌افزار محور، معیارهای مختلفی ارائه شده است. در بین این معیارها، تأخیر در بین کنترلر و شبکه نقش بسیار مهمی را بازی می‌کند چرا که تأثیر قابل ملاحظه‌ای بر روی کارائی کلی SDN دارد [2] [3]. برای مثال در صورتی که یک بسته‌ی داده‌ای هیچ تطابقی با الگوهای تعریف شده در جدول جریان یک سوئیچ نداشته باشد، نیاز است تا این سوئیچ برای یک بازه‌ی زمانی منتظر مانده تا جدول‌های جریان را قبل از پردازش این بسته‌ی داده‌ای دریافت نماید. بدیهی است که یک زمان انتظار طولانی می‌تواند افت کلی بازدهی SDN را به همراه داشته باشد، یعنی برنامه­های کاربردی10 که نسبت به زمان حساس هستند با کندی روبرو شده و وظایفی که باید به صورت بلادرنگ صورت گیرند، به هیچ وجه انجام نخواهند شد. به طور معمول، لینک­های ارتباطی که پهنای باند محدودی دارند و ترافیک بالای شبکه باعث شده تا شبکه دچار ازدحام شده و تأخیر بالایی پیش روی شبکه قرار گیرد. با توجه به ویژگی انحصاری که در SDN وجود دارد، تأخیر ناشی از ازدحام بین کنترلرها و سوئیچ­ها در شبکه‌های SDN بسیار محدود خواهد بود. چرا که سطح کنترلی از سطح داده‌ای جدا بوده و از این رو پیام‌های کنترلی که بین کنترلرها و سوئیچ­ها مبادله می‌شود از طریق یک کانال اختصاصی (مد برون باند) منتقل می‌شود [4] [5]. علاوه بر این، پیام‌های کنترلی، شامل یک سری جریان داده‌ای سبک وزن در مقایسه با بارهای داده‌ای موجود در سطح داده‌ای می‌باشند [6]. در کنار معیار تأخیر، باید بار موجود و درصد مشغول بودن
لینک­های ارتباطی را هم در نظر بگیریم تا از به وجود آمدن نقاط گلوگاه در شبکه و در نتیجه به وجود آمدن ازدحام جلوگیری به عمل آوریم.

در این مقاله به بررسی هزینه انتها به انتها (شامل تأخیر انتها به انتها و درصد مشغول بودن لینک­ها) در بین کنترلرها و سوئیچ­ها می‌پردازیم و به دنبال راهکاری برای کاهش هزینه و کنترل ازدحام در شبکه‌های گسترده خواهیم بود. هر کدام از این ها را به صورت مجزا مورد بحث قرار می‌دهیم. در ابتدا باید یک شبکه را به چندین زیر شبکه تقسیم بندی کرده تا بتوان هزینه انتها به انتها در بین کنترلرها و سوئیچ­ها را کاهش داد. با در نظر گرفتن اهمیت تأخیر و هم­چنین بار موجود روی لینک­های ارتباطی، روش پیشنهادی در این مقاله ارائه شده است. باید حتماً در نظر داشته باشیم که تأخیر انتها به انتها تنها یکی از مؤلفه‌های تأثیر گذار بر روی کارائی شبکه می‌باشد. علاوه بر تأخیر عواملی هم­چون بار موجود روی لینک­های ارتباطی بین کنترلر­ها و سوئیچ­های مربوط به آن­ها نیز در کارائی کلی شبکه تاثیرگذار می­باشد.

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

2- شبکه­های مبتنی بر نرم­افزار

SDN یک معماری جدید برای شبکه­های کامپیوتری است که طی آن کنترل اطلاعات از خود اطلاعات و انتقال اطلاعات، مجزا می­شود. روترها و سوئیچ­های کنونی شبکه­ها هرچقدر که پیشرفته و قدرتمند باشند عملیات انتقال و کنترل اطلاعات را با هم انجام می­دهند. در معماری SDN کنترل اطلاعات از سخت­افزار سوئیچ و روتر مجزا شده و به یک لایه بالاتر رفته و توسط نرم­افزار انجام می­شود.

با مجزا شدن سطح کنترلی از سطح داده­ای در سخت­افزارها، شرکت­ها می­توانند نرم­افزارها و ابزارهای زیادی برای کنترل اطلاعات نوشته و در نتیجه سرعت، انعطاف­پذیری11،
مقیاس­پذیری12، دسترس­پذیری13، و قابلیت اعتماد14 شبکه را بیشتر کنند. شرکت­های مختلف می­توانند برای سخت افزارهایی با برندهای مختلف رابط­های برنامه‌نویسی كاربردی15 (API) بنویسند که قابلیت ها و امکانات بیشتری برای شبکه به همراه دارند و مدیریت شبکه را متمرکز و یکپارچه می­کنند و همچنین امنیت شبکه بالاتر می رود زیرا کاربران با نوشتن نرم­افزارهایی می­توانند مدیریت و مانیتورینگ بهتر و بیشتری روی اطلاعات داشته باشند و بر اساس نیازهای شبکه و تهدیداتی که متوجه شبکه آنها است، فایروال ها و سیستم های کشف فیلترینگ را برنامه ریزی و سیاستگذاری کنند. مزیت دیگر، پیکربندی مجدد شبکه و سخت­افزار بدون نیاز به شرکت سازنده آن سخت­افزار است. در شبکه­های کنونی کاربران محدود به استفاده از فناوری و معماری ارائه شده توسط شرکت­های سازنده سخت افزار هستند و نمی­توانند خودشان دست به توسعه شبکه بزنند. برنامه­نویسی رابط شبکه در SDN توسط خود کاربر صورت می­گیرد و مطابق با نیازهای او می­تواند بومی­سازی شود. استاندارد SDN به گونه اي طراحي شده است که فرآيند ارسال اطلاعات در شبکه ها را آسان تر و انعطاف پذيري شبکه­ها را تحت فضاي برنامه­ريزي شده هوشمند بيشتر مي­کند.

به منظور بهبود مسیریابی در شبکه­های مبتنی بر نرم­افزار با استفاده از کنترلرهای توزیع شده، ابتدا برخی از مفاهیم مربوط به آن را بیان می­نماییم و سپس به بررسی پژوهش­های اخیر صورت پذیرفته در این حوزه می­پردازیم.

مفهوم کنترلر در شبکه­های مبتنی بر نرم­افزار: شبکه‌هاي مبتنی بر نرم­افزار سعي دارد هوشمندي شبکه‌ها را بيشتر کرده و با انتقال بخش کنترل داده‌ها از سوئیچ و روتر سخت‌افزاري به لايه‌هاي نرم‌افزاريِ مجازي شبکه و بهره‌گيري از يک واحد نرم‌افزاري متمرکز، قابليت‌هايي مانند برنامه‌ريزي، مقياس‌پذيري، انعطاف‌پذيري، خودکارسازي، هوشمندي و توسعه نرم‌افزاري شبکه توسط سازمان‌ها را فراهم کند [7]. این واحد متمرکز، کنترلر یا همان کنترل­کننده نام دارد و باید حتماً تأکید کنیم که منظور از متمرکز بودن به معنی منطقاً متمرکز می­باشد، به این معنی که کنترلر­ها را می­توانیم به صورت فیزیکی و آن هم توزیع­شده، در سطح شبکه قرار دهیم.

معماری شبکه­های مبتنی بر نرم­افزار: مدیریت و کنترل شبکه‌های بزرگ همیشه دردسرهای مخصوص به خود را دارد. یکی از آسان‌ترین روش‌های پیشگیری از بروز مشکلات و پیچیدگی‌های مدیریت شبکه‌های بزرگ استفاده از محصولات یک تولید­کننده در تمامی قسمت‌های شبکه مورد نظر است. اتکا به یک تولیدکننده، علاوه بر تحمیل هزینه‌های بیشتر (به خاطر محدودیت‌های مربوط به لایسنس، حق نام، و…) می‌تواند خلاقیت را از سازمان‌ها و شرکت‌ها دور کند.

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

اما تجهیزاتی كه برای SDN  و استفاده از OpenFlow  تولید می‌شوند، از منطق معماری افقی پیروی می‌كنند. در این معماری، دیگر از دستگاه‌هایی یكپارچه خبری نیست و تولیدكننده امكان استفاده از سیستم‌عامل و نرم‌افزار دلخواه مشتری را روی سخت‌افزار تولید شده فراهم می‌كند تا بتوان به‌طور سفارشی از سخت‌افزار بهره جست. در واقع از دیدگاه شبكه می‌توان گفت، قابلیت مدیریت دلخواه چند Control Plane  مختلف و استفاده از نرم‌افزارهای كاربردی مجزا روی این تجهیزات فراهم می‌‌شود. در SDN، داده‌ها و اطلاعات کنترلی تجهیزات شبکه مانند سوئیچ ها و روترها، توسط یك API جدا می‌شوند. در شکل 1 مقایسه­ای از معماری عمودی تجهیزات فعلی شبکه در مقابل معماری افقی تجهیزات شبکه SDN نمایش داده شده است.

 

[1]  Big Data

[2]  Internet of Things (IoT)

[3]  Cloud Computing

[4]  Software Defined Networking (SDN)

[5]  Control Plane

[6]  Data Plane

[7]  Controller

[8]  Controller Placement Problem (CPP)

[9]  Wide Area Networks (WAN)

[10]  Application

[11]  Flexibility

[12]  Scalability

[13]  Availability

[14]  Reliability

[15]  Application Programming Interface

 

 

img0 

img0 

معماری افقی

معماری عمودی

شکل 1- معماری عمودی تجهیزات فعلی شبکه در مقابل معماری افقی تجهیزات شبکه­ SDN [8]

 

دامنه‌های موجود در شبکه­های مبتنی بر نرم­افزار: در یك شبكه بزرگ، استقرار یك کنترلر واحد برای مدیریت تمام دستگاه‌های شبكه کار مناسبی نیست. یك سناریو محتمل‌تر این است كه مدیر شبكه، شبكه را همانطور كه در شكل 2 نشان داده شده است، به تعدادی دامنه SDN كه همپوشانی ندارند تقسیم ‌كند.

 

 

img0 

شکل 2-تقسیم­بندی شبکه SDN به دامنه­های مختلف [9]

 

وجود چندین دامنه نیازمند ایجاد کنترلرهای تكی برای برقراری ارتباط با یكدیگر از طریق یك پروتكل استاندارد برای تبادل اطلاعات مسیریابی می­باشد. برای این منظور IETF اخیراً بر روی توسعه و گسترش پروتكلی به نام 1SDNi كار می‌كند.

3- کارهای مرتبط

در این بخش به بررسی تحقیقاتی که بر روی مسأله‌ی گمارش کنترلرها صورت گرفته است می‌پردازیم. تحقیقات موجود را می‌توان بر حسب اهداف زیر به چهار بخش تقسیم کرد [10]: کاهش تأخیر شبکه در بین کنترلرها و سوئیچ­ها، افزایش قابلیت اطمینان و اعتماد، کاهش هزینه‌ی توسعه و مصرف انرژی و روش چند هدفی.

کاهش تأخیر شبکه در بین کنترلرها و سوئیچ­ها: آقای هِلر و همکارانش [11] به مطالعه‌ی مسأله‌ی گمارش کنترلرها در SDN پرداختند و خاطر نشان کردند که تأخیر در انتشار (تأخیر میانگین و تأخیر در بدترین حالت)، ملاحظه‌ی اصلی آن‌ها در این مطالعه می‌باشد. این مسأله به صورت یک مسأله‌ی سهولت در مکان­یابی شبیه­سازی شده است و از الگوریتم K-center نیز برای حل این مسأله استفاده شده است. آقای یائو و همکارانش [12] نیز هر دوی تأخیر در انتظار و ظرفیت کنترلر را در نظر گرفتند. بنابراین فرآیند گمارش را می‌توان به عنوان یک مسأله‌ی K-center در نظر گرفت [13]. نتایج شبیه‌سازی‌های آن‌ها نشان می‌دهد که راهکار پیشنهادی آن‌ها می‌تواند تعداد کنترلرها و بار کنترلرهای درگیر را کاهش دهد. در [14] به ایجاد یک توازن در بین تأخیر در انتشار و بار ترافیکی پرداخته شده است. نتایج شبیه­سازی نشان می‌دهد که بار موجود در سطح کنترلی را می‌توان با افزایش جزئی تأخیر متوازن­سازی کرد. در [15] به بررسی مسأله‌ی گمارش کنترلرها و آن هم از یک دید متفاوت پرداخته شده است. بر مبنای این دیدگاه، بجای کمینه­سازی مستقیم تأخیر بین کنترلرها و سوئیچ ها، هدف این است که تعداد سوئیچ‌های کنترلی را در یک بازه‌ی زمانی که با تأخیر روبرو هستیم افزایش دهیم.

افزایش قابلیت اطمینان و تاب­آوری: آقای ژانگ و همکارانش [16] به ارائه‌ی یک الگوریتم مبتنی بر برش کمینه2 پرداخته‌اند تا بتوانند احتمال قطعی ارتباط در بین کنترلر و سوئیچ را به حداقل سطح ممکن برسانند. آقای هیو و همکارانش [17] نیز به مطالعه‌ی مسأله‌ی گمارش کنترلر برای تضمین قابلیت اطمینان پرداخته‌اند و یک الگوریتم حریصانه را برای گمارش کارآمد و رسیدن به قابلیت اطمینان ارائه نموده‌اند. در [18] هدفی که دنبال شده است این بوده که ارتباط بین دستگاه‌های هدایت­کننده‌ی بسته‌های داده‌ای و کنترلرها به بالاترین سطح ممکن برسد. در این مطالعه خاطر نشان شده است که تنوع در مسیرها می‌تواند بقای شبکه را در شرایط بروز اشکال و خرابی افزایش دهد. تحقیقات مشابهی نیز صورت گرفته که می‌توان به [19] اشاره کرد. شبیه­سازی­هایی نیز در [20] و با هدف افزایش قابلیت اطمینان SDN ارائه شده است. در این مطالعه به گمارش مناسب کنترلرها پرداخته شده است. جدای از تحقیقاتی که به بهبود تاب­آوری اتصالات شبکه پرداخته‌اند، در [21] روشی ارائه شده است که می‌تواند اشکالات کنترلر در شبکه‌های گسترده‌ی SDN را تحمل نماید.

کاهش هزینه‌ی توسعه و مصرف انرژی: پژوهشگران تحقیق [22] به توسعه‌ی مدلی بهینه پرداخته‌اند و مصرف کلی انرژی را بر اساس شبیه‌سازی‌هایشان کاهش داده‌اند. چالش اصلی در این مدل، پیچیدگی بالای آن می‌باشد چرا که بعضی از محاسبات را نمی‌توان در کمتر از 30 ساعت انجام داد. آن­ها در این کار شرایط قرارگیری را برای بسط دادن یک شبکه مبتنی بر نرم­افزار با کمترین هزینه مورد بررسی قرار دادند. بدین صورت که با داشتن طراحی یک شبکه موجود و تعدادی سوئیچ جدید که باید به شبکه قبلی اضافه شوند، مدل بررسی می­کند که شبکه چگونه مجدداً سازماندهی شود تا هزینه بروزرسانی کمینه شود. از آنجایی که مسأله بسط دادن، کلی شده مسأله برنامه­ریزی است، این مدل می­تواند برای برنامه­ریزی یک شبکه از ابتدا نیز مورد استفاده قرار بگیرد. آن­ها برای حل این مسأله از یک راه­حل برنامه­ریزی خطی استفاده کردند. در [23] راهکاری ارائه شده است که می‌تواند به صورت پویا به اضافه و یا حذف کنترلرها و آن هم بر اساس تغییر بارها بپردازد. یکی از روش­ها برای به حداقل رساندن مصرف انرژی، روش GreCo می‌باشد که در [24] ارائه شده است. در این روش، لینک­های غیر ضروری خاموش شده و در عین حال حفظ ارتباط در بین سوئیچ­ها و کنترلرها تضمین می‌شود. با توجه به شبیه­سازی­ها، با روش GreCo می‌توان تا 55 درصد مصرف انرژی را در طی ساعات شلوغی و اوج کاهش داد. روش دیگری در [25] ارائه شده که در آن در ابتدا تعداد کنترلرها مشخص شده و سپس کنترلرهای ضروری فعال می‌شوند تا به این شکل در مصرف انرژی صرفه­جویی شود. یک مدل دیگر در [26] برای به حداقل رساندن هزینه‌ی بروز رسانی توسعه یافته است و آن هم در زمانی که سوئیچ‌های جدید به شبکه اضافه می‌شوند. با توجه به اینکه این روش در شبکه‌های مبتنی بر نرم­افزار محدود نمی­باشد، می‌توان از آن برای ایجاد یک شبکه‌ی جدید و یا بروز رسانی شبکه‌های موجود استفاده نمود.

روش چند هدفی: در [27]، مباحثی در خصوص مسأله‌ی گمارش کنترلرها و آن هم با تمرکز بر تاب­آوری و اشکال در شبکه‌های هسته‌ای مبتنی بر نرم­افزار ارائه شده است. یک مجموعه­ی ابزاری با نام POCO ارائه شده که این امکان را به اپراتورهای شبکه داده تا گمارش را به صورت شبه بهینه انجام دهند. یافته‌های آن‌ها نشان می‌دهد که در اغلب توپولوژی­ها، بیش از 20 درصد از همه‌ی گره‌ها باید از نوع کنترلر بوده تا ارتباط پیوسته‌ی همه‌ی گره‌ها با یکی از کنترلرها و آن هم در سناریوهای خرابی تضمین شود. این مجموعه ابزار در [28] به صورت توسعه­یافته تر ارائه شده است به گونه‌ای که در آن از یک روش ابتکاری با دقت کمتر استفاده شده ولی زمان محاسباتی کمتری برای غلبه بر ماهیت پویای شبکه‌های بزرگ مقیاس دارد. ایجاد توازن در بین زمان و میزان صحت نیز به صورت کامل از طریق توپولوژی‌های مختلفی بررسی شده است.  پژوهشگران در [29] به ارائه‌ی یک چارچوب کنترل و مدیریت مبتنی بر نرم­افزار و آن هم برای شبکه‌هایی با ستون فقرات ثابت پرداخته‌اند. الگوریتم‌هایی برای تخصیص مدیران و کنترلرها در یک لایه‌ی کنترلی ارائه شده که هدف آن رسیدن به یک توازن بار و مصرف انرژی می‌باشد. در [30]، یک روش گمارش کنترلر و مبتنی بر چگالی ارائه شده است که مسأله‌ی گمارش کنترلر بر حسب تأخیر، تحمل­پذیری در برابر اشکال و تعداد کنترلرها، ارائه شده است. ارزیابی‌های کارائی نشان می‌دهد که این روش می‌تواند به کارائی مطلوبی دست پیدا کرده و سرعت اجرا را نیز در عین حال کاهش می‌دهد. آن­ها برای حل مسأله قرارگیری کنترلر­ها به چگالی گره­ها در توپولوژی شبکه توجه کردند. بدین صورت که در ابتدا بر اساس چگالی گره­ها، شبکه را به تعدادی خوشه­ی مجزا تقسیم می­کنند و به دلیل آنکه گره­های درون هر خوشه اتصال قوی با دیگر گره­های درون خوشه خود دارند و اتصال آن­ها با گره­های دیگر خوشه­ها ضعیف است، در هر خوشه یک کنترل­کننده قرار می­گیرد. ژانگ و همکاران در [31] به تدوین مسأله‌ی گمارش کنترلرها بر روی یک مدل چند هدفی پرداخته‌اند که هدف آن افزایش قابلیت اطمینان در بین کنترلرها و سوئیچ­ها می‌باشد. نتایج شبیه­سازی­ها نشان می‌دهد که روش پیشنهادی می‌تواند کارائی شبکه را بهبود داده و به توان مطلوبی در بین این اهداف دست پیدا کند.

با توجه به بررسی­ها، بسیاری از روش‌هایی که در بالا مطرح شد تنها تأخیر در انتشار بسته در بین کنترلرها و سوئیچ­ها را در نظر می‌گیرد تا بتواند تأخیر را به حداقل سطح ممکن برساند. البته تأخیر در انتشار تنها یکی از عوامل تأثیرگذار بر روی تأخیر سراسری می‌باشد. از جمله عوامل دیگر می‌توان به تأخیر در صف­بندی کنترلرها اشاره کرد. بنابراین نیاز به تحقیقات گسترده‌ای برای لحاظ کردن همه‌ی مؤلفه‌ها می‌باشد. در مقاله­ی [32] که به عنوان مقاله­ی پایه در این پژوهش مورد استفاده قرار گرفته است، همه‌ی تأخیرهای ممکن در بین کنترلرها و سوئیچ­ها را در نظر گرفته و راهکاری را برای کاهش تأخیرها ارائه نموده‌ است. علاوه بر مقالات و مطالعاتی که در بالا به آن­ها اشاره شد، می­توان به موارد زیر نیز در حوزه موضوع پژوهش اشاره کرد:

یک کار دیگر در خصوص قرارگیری کنترلر­ها توسط بَری و همکارانش انجام شده است [33]. آنها دو الگوریتم مکاشفه­ای برای تأمین کنترلر به صورت پویا پیشنهاد دادند. اهداف آن­ها شامل کمینه کردن زمان تنظیم جریان، ترافیک کنترلی و تخصیص مجدد سوئیچ به کنترلر می­باشد.

هم­چنین به تازگی تحقیقی توسط هیو و همکارانش انجام شده است که به مسأله قرارگیری کنترلرها از دیدگاه ذخیره انرژی نگاه می­کند [34]. آن­ها برای کار خود، مسأله قرارگیری ذخیره­کننده انرژی را توسط یک مسأله خطی عدد صحیح دودویی3 مدل کردند. در این مدل، مصرف انرژی شبکه­هایی که برای ترافیک کنترلی استفاده می­شوند، تحت محدودیت­های تأخیر مسیرهای کنترلی و بار کنترلر­ها کمینه می­شوند. هم­چنین آن­ها با توجه به پیچیدگی مدل خطی عدد صحیح، یک الگوریتم مکاشفه­ای ژنتیک نیز برای پیدا کردن
راه­حل­های زیر­بهینه ارائه دادند.

یک کار متفاوت دیگر نیز توسط ایشیگاکی و همکارانش انجام شده است [35]. آن­ها در کار خود، راه­حلی برای مسأله­ی قرارگیری کنترلر­ها ارائه داده­اند که قرارگیری را با توجه به بار روی گره­های ارتباطی انجام می­دهد. باید در نظر گرفت که پیام­های کنترلی بین یک کنترلر و یک سوئیچ که در بخش داده رد­و­بدل می­شوند، توسط دیگر سوئیچ­ها به کنترلر
می­رسند. معمولاً الگوریتم­های مسیریابی برای چنین
انتقال­هایی بر اساس کوتاه­ترین مسیر عمل می­کنند که باعث می­شود دائماً برخی گره­های خاص به عنوان نقاط بازپخش انتخاب شوند. به عبارت دیگر بسیاری از کوتاه­ترین مسیر­ها بین سوئیچ­ها و کنترلر ممکن است شامل گره­های مشابه باشند. بدین صورت بار زیادی بر روی این گره­ها به وجود می­آید که ممکن است باعث خرابی در این نقاط شود. به همین دلیل در این مقاله قرارگیری با توجه به حداکثر بار بر روی این گره­ها انجام شده است.

تمام موارد فوق تنها بخشی از مطالعات و پژوهش­هایی بود که در خصوص گمارش و قرارگیری کنترلر­ها و توزیع آن­ها در شبکه­های مبتنی بر نرم­افزار صورت گرفته است.

4-روش پیشنهادی

در این بخش با توجه به بررسی­های صورت گرفته در حوزه­ی موضوع پژوهش و هم­چنین با در­نظر گرفتن معایب مقاله پایه [32]، روش پیشنهادی خود را که 4ECNPA نامگذاری کرده­ایم، ارائه خواهیم کرد و به تشریح آن خواهیم ­پرداخت. عیب عمده الگوریتم به کار رفته در مقاله پایه در این است که در عمل خوشه­بندی کنترلرها، تنها معیار تأخیر را در نظر می­گیرد و توجهی به بار موجود روی لینک­ها ندارد که این موضوع باعث به وجود آمدن ازدحام در لینک­ها و ایجاد لینک­های گلوگاه5 می­شود. ولی در روش پیشنهادی، علاوه بر تأخیر بین کنترلر­ها و سوئیچ­ها، بار موجود روی لینک­ها نیز در نظر گرفته شده و به تبع آن با دقت بالاتری عمل خوشه­بندی را ادامه می­دهیم. تأخیر و هم­چنین بار موجود روی لینک­ها در بین کنترلرها و سوئیچ‌های مربوط به آن‌ها را می‌توان یک ضرورت برای SDN در نظر گرفت چرا که همه‌ی توابع در یک شبکه‌ی مبتنی بر SDN می‌توانند به وسیله‌ی مبادله‌ی مکرر پیام ها در بین کنترلرها و سوئیچ­ها صورت گیرد. در این بخش به بررسی مؤلفه‌های ممکن مربوط به تأخیر در بین کنترلرها و سوئیچ­ها می‌پردازیم و در بخش بعد به تدوین مسأله‌ی گمارش کنترلر­ها خواهیم پرداخت.

در یک شبکه‌ی مبتنی بر نرم­افزار با تعداد مشخصی از گره‌ها و لینک­ها، فرض کنید که  بیانگر سوئیچ‌های موجود در شبکه باشد و  نیز بیانگر کنترلرها باشد. فرض بر آن است که تعداد گام­های6 حرکتی مربوط به سوئیچ  تا کنترلر  به صورت  نمایش داده می‌شود. در شکل 3، تأخیر انتها به انتها را در شرایطی مشاهده می‌کنید که انتقال یک بسته از سوئیچ  به سمت کنترلر  صورت می‌گیرد.

[1]  Interfacing SDN Domain Controllers

[2]  Min-cut algorithm

[3]  Binary Integer Program (BIP)

[4]  Enhanced Cluster-based Network Partitioning Algorithm

[5]  Bottleneck

[6]  Hop

 

 

img0 

شکل 3: تأخیر انتها به انتها در انتقال بسته در SDN [32]

 

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

در نظر داشته باشید که سه مؤلفه از تأخیر انتها به انتها، وزن یکسانی در شبکه‌های مختلف ندارند. برای مثال در یک شبکه‌ محلی1 (LAN) که پهنای باند کم سرعتی داشته و محدوده‌ی انتقال نیز محدود می‌باشد، تأخیر در انتقال بسته‌های داده‌ای ، غالب بوده در حالی که تأخیر در انتشار  را می‌توان نادیده گرفت. در مقابل، در یک شبکه‌ای که مجهز به سوئیچ‌های 10 یا 100 گیگابیت بر ثانیه می‌باشد [36] [37] و فاصله‌ی صدها مایلی دارد، تأخیر در انتقال بسته را می‌توان نادیده گرفت در حالی که تأخیر در انتشار بسته‌های داده‌ای یک تأخیر مهم می‌باشد. تأخیر در پردازش سوئیچ  نیز به وسیله‌ی کارائی سوئیچ­ها مشخص می‌شود. سوئیچ‌هایی با کارائی بالا و سوئیچ‌هایی با سرعت سیمی را همراه با تأخیر پایین و نوسان در شبکه‌های ستون فقرات مشاهده می‌کنیم. اخیراً دستاوردهای مهمی بر روی سوئیچ‌های SDN صورت گرفته است. برای مثال همان‌طور که در [38] مطرح شده است، Corsa DP2100 [37] می‌تواند به توان عملیاتی 100 گیگابیت بر ثانیه دست پیدا کند و این بدین معنا است که تأخیر در پردازش سوئیچ  را می‌توان در صورتی که از این نوع سوئیچ­ها در یک شبکه‌ی ستون فقرات مبتنی بر نرم­افزار استفاده شود،
چشم­پوشی کرد.

در ادامه به تدوین مسأله‌ی تقسیم­بندی شبکه در SDN می‌پردازیم. برای یک شبکه‌ی مبتنی بر نرم­افزار با تعداد مشخصی از گره‌ها و لینک ها، توپولوژی فیزیکی شبکه را به صورت یک گراف  نمایش می‌دهیم که در آن، V بیانگر یک مجموعه از گره‌ها بوده و هر دوی سوئیچ­ها و کنترلرها را در بر دارد. این بر مبنای این فرضیه بوده که کنترلرها در مکان‌هایی قرار دارند که سوئیچ­ها نیز در آن مکان قرار دارند به گونه‌ای که کنترلرها و سوئیچ­ها را می‌توان به هم متصل نمود [11] [12] [28].

E بیانگر مجموعه‌ای از لینک­های فیزیکی در بین این گره‌ها می‌باشد. فرض بر آن است که تعداد زیرگراف­ها به صورت K مشخص می‌شود و بیانگر تعداد زیرشبکه‌های موجود در شبکه باشد. در زمانی که SDN در نظر گرفته می‌شود، پارتیشن شبکه را می‌توان به صورت  تعریف کرد:

(1)

 

معادله‌ی 2 بکار گرفته شده تا نمایش داده شود که کل زیرشبکه‌ها باید همه‌ی اِلمان­ها را پوشش دهند: گره‌ها و لینک­ها. در معادله‌ی 3،  به معنای یک مجموعه‌ی خالی بوده به این معنا که یک گره یا لینک تنها می‌تواند به یک زیرشبکه تخصیص داده شود و معادله‌ی 4 نیز مبین این بوده که المان‌های موجود در یک زیرشبکه داری تشابه یکسانی می‌باشند. در معادله‌ی 5 نشان داده شده است که ِالمان‌هایی که به زیرشبکه‌های مختلف تخصیص داده می‌شوند، دارای کمترین تشابه با یکدیگر هستند. منظور ما از تشابه، همان هزینه (تأخیر و بار) می‌باشد. به طور خاص، انتظار می‌رود که شبکه به گونه‌ای تقسیم شود که گره‌های موجود در یک خوشه دارای هزینه کمتری باشند. معادله‌ی 6 نشان می‌دهد که همه‌ی رئوس موجود در زیرشبکه‌ها به وسیله‌ی لینک به هم متصل می‌باشند. معادلاتی که در بالا به آن­ها اشاره شد، همگی در مقاله پایه مورد استفاده قرار گرفته­اند. حال هدفی که در این مقاله دنبال می‌کنیم این است که کنترلرها را در یک شبکه‌ی گسترده‌ی مبتنی بر نرم­افزار به گونه­ای قرار دهیم تا بتوان حداکثر هزینه بین کنترلرها و سوئیچ­ها را به حداقل سطح ممکن رساند. در روش پیشنهادی اگر  را میزان مشغول بودن لینک i ام در نظر بگیریم، میزان مشغول بودن مسیر بین سوئیچ  و کنترلر  از رابطه­ی 7 محاسبه می­شود:

                (7)

هزینه را به صورت معادله­ی 8 نمایش می‌دهیم که شامل تأخیر انتها به انتها و درصد بار موجود یا همان میزان مشغول بودن لینک­ گلوگاه در مسیر بین کنترلر تا سوئیچ می­باشد:

                        (8)

 بنابراین تابع هدف2 را به صورت رابطه 9 بیان می‌کنیم:

        (9)

4-1- تشریح نحوه تقسیم­بندی شبکه به k زیرشبکه با استفاده از الگوریتم پیشنهادی

در این بخش به ارائه‌ی یک الگوریتم بخش­بندی شبکه بر مبنای خوشه­بندی می‌پردازیم و چگونگی بخش­بندی یک شبکه به زیرشبکه‌ها را با هدف کاهش ماکزیمم هزینه­ی انتها به انتها ارائه می‌دهیم. مسأله‌ی بخش­بندی شبکه مشابه با مسأله‌ی خوشه­بندی می‌باشد و راهکارهای آن را می‌توان از الگوریتم‌های خوشه­بندی الهام گرفت. البته الگوریتم‌های استاندارد خوشه­بندی، مانند K-means و K-center را نمی‌توان به صورت مستقیم برای بخش­بندی یک شبکه به زیرشبکه‌ها بکار گرفت که دلیل آن را می‌توان ناشی از موارد زیر دانست: اول اینکه انتخاب تصادفی مراکز اولیه نمی‌تواند این تضمین را بدهد که هر پارتیشن می‌تواند هزینه حداکثری در بین مرکز و گره‌های مربوط به آن را در زیرشبکه‌ها کاهش دهد. دوم اینکه فاصله‌ی اقلیدسی را نمی‌توان برای محاسبه‌ی فاصله‌ی بین دو گره جغرافیایی بکار گرفت. به منظور غلبه بر این معایب، از الگوریتم پیشنهادی برای حل مسأله‌ی بخش­بندی شبکه استفاده می‌کنیم. در الگوریتم پیشنهادی، به محاسبه‌ی هزینه بین هر دو گره پرداخته می‌شود. مسیری با کوتاه‌ترین فاصله در الگوریتم پیشنهادی بکار گرفته شده تا تأخیر انتها به انتها محاسبه شود. به طور خاص، در یک توپولوژی شبکه با لینک­ها و گره‌های مختلف، ماتریس مجاورت این توپولوژی در ابتدا محاسبه می‌شود. مختصات این گره‌ها را از روی نقشه‌ی گوگل به دست آوردیم و فاصله‌ی این لینک­ها را نیز با استفاده از فرمول "haversine" محاسبه کردیم [39] [40]. هم­چنین کوتاه‌ترین مسیر بین هر دو گره را با استفاده از الگوریتم دایجسترا محاسبه خواهیم کرد [41]. مراحل الگوریتم پیشنهادی در زیر مشاهده می­شود:

 

[1]  Local Area Network (LAN)

[2]  Objective Function

 

(2)

 

(3)

 

(4)

 

(5)

 

(6)

 is a connected region                     

 

 

شبه­کد مربوط به محاسبه فاصله بین هر دو گره از دو سر یک لینک در شبکه WAN با استفاده از فرمول Haversine که در بالا به آن اشاره شد، به صورت زیر می­باشد:

 

الگوریتم پیشنهادی برای خوشه­بندی و توزیع کنترلرها

ورودی­ها:

1-       توپولوژی شبکه که به صورت  نمایش داده می­شود و از داخل یک فایل XML وارد برنامه می­شود که در آن V نشان­دهنده­ی گره­ها و E نشان­دهنده­ی یال­ها یا همان لینک­های ارتباطی می­باشد.

2-       تعداد زیر شبکه‌ها.

شروع

گام اول: محاسبه‌ی تأخیر انتها به انتها بین هر دو گره دلخواه. .

گام دوم: محاسبه‌ی میزان مشغول بودن لینک گلوگاه در مسیر بین هر دو گره دلخواه. .

گام سوم: محاسبه‌ی اولین مرکز شبکه. گره­ای که دارای کمترین هزینه (تأخیر و بار) نسبت به سایر گره‌ها باشد به عنوان اولین مرکز انتخاب می‌شود.

گام چهارم: پیدا کردن مرکز بعدی شبکه. گره‌ای که دارای بیشترین هزینه (تأخیر و بار) نسبت به مراکز قبلی می‌باشد، به عنوان مرکز بعدی انتخاب می‌شود.

گام پنجم: توزیع بردار  بر روی یکی از خوشه‌ها و آن هم با استفاده از رابطه‌ی زیر:

 

گام ششم: بروز رسانی مراکز  به گونه‌ای که جمع هزینه­ی مربوط به همه‌ی گره‌ها در خوشه  نسبت به مرکز  به حداقل سطح ممکن برسد.

 

 

گام هفتم: مراحل 4، 5 و 6 را تکرار می‌کنیم تا اینکه شبکه به  زیر شبکه تقسیم شود.

پایان

خروجی­ها:

1-       مراکز  خوشه.

2-       تخصیص سوئیچ­ها به هر یک از خوشه­ها.

شبه­کد محاسبه فاصله بین هر دو گره با فرمول Haversine

1)Begin

2)Function dist = CalcDistance(node1,node2)

3)        lat1 = node1(1);

4)        lng1 = node1(2);

5)        lat2 = node2(1);

6)        lng2 = node2(2);

7)        earthRadius = 3958.75; % In Miles(6370.99056 In Kilometers)

8)        dLat = toRadians(lat2 - lat1);

9)        dLng = toRadians(lng2 - lng1);

10)        a = sin(dLat / 2) * sin(dLat / 2) +

11)        cos(toRadians(lat1)) * cos(toRadians(lat2)) *

12)        sin(dLng / 2) * sin(dLng / 2);

13)        c = 2 * atan2(sqrt(a), sqrt(1 - a));

14)        dist = earthRadius * c;

15)        meterConversion = 1/0.000621371192;

16)        dist=dist * meterConversion;

17)        Function r=toRadians(d)

18)            r=d/180*pi;

19)        End function

20)End function

21)End

 

شبه­کد مربوط به محاسبه تأخیر انتها به انتها بین هر دو گره از دو سر یک لینک در شبکه WAN با توجه به معادله­ی 1 که در بالا به آن اشاره شد، به صورت زیر می­باشد:

 

شبه­کد محاسبه تأخیر انتها به انتها با معادله­ی 1

1)Begin

2)Function [Delay] = CalcLatency(Distance) % Distance is in Meters

3)    SpeedOfLight=299792458; % Meters Per Second

4)    WANFiberSpeed=(SpeedOfLight*65)/100; % Meters Per Second

5)    Delay=(Distance/WANFiberSpeed)*1000; % Delay in Millisecond

6)End function

7)End

 

شبه­کد مربوط به محاسبه میزان مشغول بودن لینک گلوگاه در مسیر بین هر دو گره دلخواه در شبکه با توجه به معادله­ی 7 که در بالا به آن اشاره شد، به صورت زیر می­باشد:

 

شبه­کد محاسبه میزان مشغول بودن لینک گلوگاه با معادله­ی 7

1)Begin

% Find the bottleneck link load

2)For each node with indices i,j in Topology

3)tmp=[];

4)  For k=FindLinks(path,links)

5)    tmp=[tmp;loads(loads(:,1)==k,:)];

6) End for

7)tmp=tmp(tmp(:,2)==max(tmp(:,2)),2);

8)AllNodesBottleNeckLinkLoad(i,j)=tmp(1);

9)AllNodesBottleNeckLinkLoad(j,i)=tmp(1);

10)End for

11)End

 

بطور خلاصه، اولین مرحله در الگوریتم پیشنهادی به این صورت است که می‌تواند مرکز واقعی شبکه (محور) را به راحتی پیدا کند. به طور خاص، الگوریتم پیشنهادی اقدام به محاسبه‌ی هزینه مربوط به هر گره نسبت به سایر گره‌ها نموده و گره ای را که دارای کمترین هزینه تا سایر گره­ها می‌باشد را به عنوان محور انتخاب می‌کند. در گام بعد، الگوریتم پیشنهادی اقدام به پیدا کردن مرکز دوم شبکه می‌کند. این مرکز دوم، به عنوان گره ای انتخاب می‌شود که بیشترین هزینه را دارد. در گام بعد، الگوریتم پیشنهادی نقش محور  و مرکز دوم  را به عنوان دو مرکز اولیه انتخاب کرده و گره‌های مربوطه را به این مراکز تخصیص می‌دهد. به طور خاص به ازای هر گره­ی ، هزینه آن نسبت به مراکز محاسبه شده تا دو مقدار  به دست آید. این دو مقدار با هم مقایسه شده و گره به مرکزی تخصیص داده می‌شود که به آن هزینه­ی کمتری دارد. برای مثال در صورتی که  باشد، گره ی  به  تخصیص داده می‌شود. زمانی که گره به یک مرکز دیگر تخصیص داده شد، محور این خوشه بر مبنای حداقل هزینه­ای که در گام سوم مشخص شده است محاسبه می‌شود. این فرآیند تا زمانی ادامه پیدا می‌کند که شبکه به  زیرشبکه تقسیم شود. قابل ذکر است که بر خلاف الگوریتم‌های متعارف خوشه­بندی، که به صورت تصادفی اقدام به انتخاب یک باره‌ی همه  مرکز نموده و سپس همه‌ی آن‌ها را در طی تکرارهایی بهینه می‌سازند، الگوریتم پیشنهادی در ابتدا اقدام به تقسیم کل شبکه به تعدادی زیرشبکه نموده تا به  زیرشبکه دست پیدا کند. در طول هر بخش، می‌توان هزینه را در بین مراکز و گره‌های مربوط به آن‌ها کاهش داده و از این رو هزینه حداکثری در سطح قابل ملاحظه‌ای در مقایسه با الگوریتم‌های متعارف خوشه­بندی مانندK-center و K-means کاهش پیدا می‌کند.

5- ارزیابی روش پیشنهادی

در این بخش به ارزیابی روش پیشنهادی می‌پردازیم و آن را با راهکارهای موجود و آن هم تحت توپولوژی‌های واقعی که از پروژه‌ی Topology Zoo1 به دست آمده است [42] مقایسه می­نماییم. الگوریتم‌ پیشنهادی در نرم‌افزار متلب به عنوان یک محیط رایانش عددی قوی پیاده سازی شده است. این نرم‌افزار به صورت گسترده در حوزه‌ی تحقیقات گمارش کنترلر SDN بکار گرفته می‌شود. شبیه­سازی­ها شامل گام‌های زیر می‌باشد:

گام اول: در اولین مرحله با استفاده از تابعی با نام ImportGraphML دیتاست­های مربوطه را که در قالب فایل­های XML می­باشند و شامل اطلاعاتی مانند موقعیت­ جغرافیایی2 گره­های شبکه، مشخصات لینک­ها، توپولوژی شبکه، و ... می­باشند، وارد برنامه می­کنیم. موقعیت­ جغرافیایی گره­های شبکه شامل مشخصات طول جغرافیایی3 و عرض جغرافیایی4 می­باشد که در جدولی به نام latlong ذخیره می­شوند. اطلاعات مربوط به لینک­ها در جدول links و اطلاعات مربوط به توپولوژی شبکه در جدول topology ذخیره می­شود. تمامی عملیات مربوط به گام اول با اجرای تابع main انجام می­شود.

گام دوم: فاصله‌ی بین هر دو گره از دو سر یک لینک با استفاده از فرمول Haversine که در تابع CalcDistance پیاده­سازی شده است، محاسبه می­شود.

گام سوم: کوتاه‌ترین مسیر بین هر دو گره دلخواه در شبکه با استفاده از الگوریتم Dijkstra که یکی از معروف­ترین و محبوب­ترین الگوریتم­های مسیریابی می­باشد، محاسبه می‌شود. این گام توسط تابع Dijkstra انجام شده و نتایج در جدول AllNodesDistances ذخیره می­شود. در شکل 4 نمونه­ای از مسیریابی بین هر دو گره دلخواه از شبکه با استفاده از الگوریتم Dijkstra نمایش داده شده است. لازم به ذکر است که هم در روش پیشنهادی و هم در روش به کار رفته در مقاله پایه، از همین الگوریتم مسیریابی استفاده شده است.

[1]   پروژه Topology Zoo شامل صدها توپولوژی شبکه بوده که توسط سرویس­دهندگان شبکه تدارک دیده شده است.

[2]  Geographical Location

[3]  Longitude

[4]  Latitude

 

img0 

گره مبدأ: 41

گره مقصد: 5

کوتاه­ترین مسیر: 41 39 20 21 23 9 8 5

فاصله: 3778412 متر

 

شکل 4- نمونه­ای از مسیریابی بین گره­های شبکه­ی Uunet با استفاده از الگوریتم Dijkstra

 

گام چهارم: در این مرحله با توجه به نتایج به دست­آمده از مرحله قبل و با استفاده از تابع CalcLatency تاخیر انتها به انتها بین هر دو گره دلخواه محاسبه می­شود. توجه به این نکته حائز اهمیت است که با توجه به این که گره­های ما در سطح شبکه WAN توزیع شده­اند و لینک­های مورد استفاده فیبر نوری می­باشد و با در نظر گرفتن این که سرعت انتقال سیگنال در فناوری فیبر نوری 65 درصد سرعت نور است، محاسبات لازم در تابع CalcLatency انجام شده است. هم­چنین نتایج به دست آمده از این مرحله در جدول AllNodesLatencies ذخیره شده است.

گام پنجم: اطلاعات مربوط به بار موجود روی هر لینک و در­صد مشغول بودن آن توسط یک کنترلر مرکزی در جدولی به نام loads ذخیره می­شود. در این مرحله با استفاده از تابعی به نام FindLinks ، لینک گلوگاه بین هر دو گره دلخواه به دست آمده و میزان مشغول بودن آن در جدولی به نام AllNodesBottleNeckLinkLoad ذخیره می­شود. با شناسایی لینک­های گلوگاه توانسته­ایم ازدحام را در شبکه کنترل کنیم و با دقت بالاتری کنترلر­ها را توزیع کنیم و عمل خوشه­بندی را انجام دهیم. لازم به توضیح است که برای پیاده­سازی این مرحله، درصد مشغول بودن هر لینک را به صورت یک عدد تصادفی بین 0 تا 100 در نظر گرفته­ایم که نشان­دهنده وضعیت شبکه در آن لحظه مشخص می­باشد.

گام ششم: با توجه به تابع هدفی که در بخش قبل معرفی کردیم، هزینه مربوط بین هر دو گره دلخواه محاسبه شده و در جدولی به نام AllNodesCosts ذخیره می­شود.

گام هفتم: نتایج حاصل از اجرای الگوریتم پیشنهادی با الگوریتم K-means و CNPA مقایسه شده و نشان
می­دهیم که الگوریتم پیشنهادی بهتر عمل کرده است.

5-1- نتایج پیاده­سازی

در این قسمت نتایج حاصل از پیاده­سازی را با اجرای 100 مرتبه از هر سه الگوریتم، در چند نمونه از توپولوژی­های مربوط به پروژه Topology Zoo با هم مقایسه می­کنیم. ضمناً با توجه به این که در مقاله پایه، توپولوژی Chinanet مربوط به کشور چین مورد بررسی قرار گرفته است و هم­چنین جهت نشان دادن هر چه بهتر عملکرد الگوریتم پیشنهادی در توپولوژی­های پیچیده­تر و متفاوت­تر در سایر کشور­های پیشرفته جهان مانند آمریکا، آلمان، و... به انتخاب دیتاست­های مربوطه پرداخته و نتایج به دست آمده را ارزیابی می­کنیم.

5-1-1- ارزیابی نتایج به دست آمده در توپولوژی Uunet مربوط به کشور آمریکا

در شکل 5 نمایی از توپولوژی واقعی شبکه­ی Uunet را در مقابل توپولوژی پیاده­سازی شده آن در نرم­افزار متلب مشاهده می­کنیم:

 

img0 

img0 

توپولوژی پیاده­سازی شده

توپولوژی واقعی [43]

شکل 5- توپولوژی واقعی شبکه­ی Uunet در مقابل توپولوژی پیاده­سازی شده آن

 

 

در ادامه، نتایج مربوط به اجرای هر یک از الگوریتم های CNPA و ECNPA را نمایش می­دهیم. مراحل انتخاب سرخوشه­ها در الگوریتم CNPA تا رسیدن به تعداد زیر­شبکه دلخواه در شکل 6 نمایش داده شده است:

img0 

مرحله اول: 25

img0 

مرحله دوم: 25 43

img0 

مرحله سوم: 21 42 32

img0 

مرحله چهارم: 21 42 31 15

img0 

مرحله پنجم: 21 42 31 15 0

img0 

مرحله ششم: 21 42 31 15 0 46

شکل 6- اجرای الگوریتم CNPA روی شبکه Uunet به ازای k=6

 

حداکثر هزینه به دست آمده در تمام خوشه­ها،­ بین سرخوشه 21 (که معرف کنترلر­ می­باشد) تا گره 33 متعلق به آن (که معرف سوئیچ­ می­باشد) با اجرای الگوریتم CNPA در توپولوژی Uunet برابر با 9945/6 می­باشد.

مـراحـل انتـخاب سـرخوشـه­ها در الـگـوریتـم پیشـنهادی (ECNPA) تا رسیدن به تعداد زیر­شبکه دلخواه در شکل 7 نمایش داده شده است:

img0 

مرحله اول: 25

img0 

مرحله دوم: 25 31

img0 

مرحله سوم: 9 31 41

img0 

مرحله چهارم: 9 31 41 15

img0 

مرحله پنجم: 9 31 41 15 0

img0 

مرحله ششم: 9 31 41 15 0 25

شکل 7: اجرای الگوریتم پیشنهادی روی شبکه Uunet به ازای k=6

 

حداکثر هزینه به دست آمده در تمام خوشه­ها،­ بین سرخوشه 31 (که معرف کنترلر­ می­باشد) تا گره 46 متعلق به آن (که معرف سوئیچ­ می­باشد) با اجرای الگوریتم پیشنهادی در توپولوژی Uunet برابر با 2852/4 می­باشد. 

در نمودار 1، نتایج به دست آمده در 100 بار اجرای هر سه الگوریتم، نشان می­دهد که در توپولوژی Uunet، میانگین حداکثر هزینه بین هر کنترلر و سوئیچ­های مربوط به آن، در الگوریتم پیشنهادی مقدار کمتری می­باشد. هم­چنین نتایج شبیه­سازی­ها در توپولوژی Uunet نیز به وضوح نشان می­دهد که اگرچه میزان تأخیر انتها به انتها در الگوریتم پیشنهادی ممکن است در بعضی از مواقع در مقایسه با الگوریتم CNPA کمی بیشتر باشد ولی در شرایطی که احتمال ازدحام در شبکه بالا می­رود، الگوریتم پیشنهادی با شناسایی لینک­های گلوگاه در مسیرهای ارتباطی هر گره با سایر گره­ها، توانسته به خوبی ازدحام را در شبکه کنترل نماید و با در نظر گرفتن دو معیار تأخیر و میزان مشغول بودن لینک­ها، فرایند قرارگیری و توزیع کنترل­ها را در عمل خوشه­بندی با دقت بالاتری انجام دهد و کارایی شبکه را افزایش دهد.

در نمودار 2 نیز یک مقایسه­ی کلی از هر سه الگوریتم زمانی که شبکه را به زیرشبکه­های مختلفی تقسیم­بندی می­کنیم، ارائه شده است. نتایج به دست آمده نشان می­دهد که با افزایش تعداد زیر­شبکه­ها در توپولوژی Uunet، میانگین هزینه­ی انتها به انتها کاهش می­یابد و الگوریتم پیشنهادی در کاهش میانگین هزینه­ی انتها به انتها، نسبت به دو الگوریتم دیگر، بهتر عمل کرده است.

 

img0 

نمودار 1- مقایسه نتایج الگوریتم پیشنهادی با الگوریتم K-means و CNPA در شبکه Uunet به ازای k=6

 

img0 

نمودار 2- مقایسه­ی کلی هر سه الگوریتم به ازای تعداد زیر­شبکه­های مختلف در توپولوژی Uunet

 

6- نتیجه‌گیری

در این پژوهش به بررسی روش‌های جدیدی برای کاهش هزینه­ی انتها به انتها (شامل تأخیر انتها به انتها و درصد مشغول بودن لینک­ها) بین کنترلرها و سوئیچ‌های مرتبط با آن‌ها پرداختیم. در ابتدا تأخیر انتها به انتها در بین کنترلرها و سوئیچ­ها را بررسی و به صورت کیفی تدوین نمودیم. در مرحله بعد به شناسایی لینک­های گلوگاه که عامل ایجاد ازدحام هستند، پرداختیم و یک الگوریتم مبتنی بر خوشه­بندی را برای بخش­بندی شبکه ارائه دادیم تا یک شبکه را به چندین زیرشبکه تقسیم کنیم تا بتوان هزینه انتها به انتها را کاهش داد. به منظور ارزیابی کارائی الگوریتم پیشنهادی، شبیه‌سازی‌های زیادی را تحت توپولوژی‌های واقعی در پروژه‌ی Topology Zoo شامل توپولوژی Chinanet کشور چین، توپولوژی Uunet کشور آمریکا، توپولوژی DFN کشور آلمان، و توپولوژی Rediris کشور اسپانیا انجام دادیم. نتایج شبیه­سازی­ها نشان می‌دهد که الگوریتم پیشنهادی می‌تواند میانگین هزینه انتها به انتها در بین کنترلرها و سوئیچ‌های مربوطه را نسبت به الگوریتم­هایی مانند K-means کاهش دهد. مراکز اولیه‌ی الگوریتم K-means به

 

 

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

در انتها لازم به ذکر است که در راستای استفاده از کنترلر­های توزیع­شده و قرار دادن آن­ها در شبکه­های مبتنی بر نرم­افزار می­توان از الگوریتم­های ابتکاری و فرا ابتکاری مانند الگوریتم ازدحام ذرات، الگوریتم ژنتیک، الگوریتم کلونی زنبور عسل، الگوریتم تکامل تفاضلی، و ... نیز جهت انجام دقیق­تر و بهتر عمل خوشه­بندی و توزیع کنترلر­ها استفاده کرد.

 

 

 

منابع

1.N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, et al., "OpenFlow: enabling innovation in campus networks," ACM SIGCOMM Computer Communication Review, vol. 38, pp. 69-74, 2008.

2.W. Miao, G. Min, Y. Wu, H. Wang, and J. Hu, "Performance modelling and analysis of software-defined networking under bursty multimedia traffic," ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM), vol. 12, p. 77, 2016.

3.H. Huang, H. Yin, G. Min, H. Jiang, J. Zhang, and Y. Wu, "Data-driven information plane in software-defined networking," IEEE Communications Magazine, vol. 55, pp. 218-224, 2017.

4.D. Levin, M. Canini, S. Schmid, F. Schaffert, and A. Feldmann, "Panopticon: Reaping the Benefits of Incremental {SDN} Deployment in Enterprise Networks," in 2014 {USENIX} Annual Technical Conference ({USENIX}{ATC} 14), 2014, pp. 333-345.

5.N. Feamster, J. Rexford, and E. Zegura, "The road to SDN: an intellectual history of programmable networks," ACM SIGCOMM Computer Communication Review, vol. 44, pp. 87-98, 2014.

6.OpenFlow Switch Specification Version 1.5.1. Available: https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/openflow/openflow-switch-v1.5.1.pdf

7.B. A. A. Nunes, M. Mendonca, X.-N. Nguyen, K. Obraczka, and T. Turletti, "A survey of software-defined networking: Past, present, and future of programmable networks," IEEE Communications Surveys & Tutorials, vol. 16, pp. 1617-1634, 2014.

8.A. Ominike Akpovi, A. Adebayo, and F. Osisanwo, "Introduction to Software Defined Networks (SDN)," 2016.

9.W. Stallings, "Software-defined networks and openflow," The internet protocol Journal, vol. 16, pp. 2-14, 2013.

10.G. Wang, Y. Zhao, J. Huang, and W. Wang, "The controller placement problem in software defined networking: A survey," IEEE Network, vol. 31, pp. 21-27, 2017.

11.B. Heller, R. Sherwood, and N. McKeown, "The controller placement problem," in Proceedings of the first workshop on Hot topics in software defined networks, 2012, pp. 7-12.

12.G. Yao, J. Bi, Y. Li, and L. Guo, "On the capacitated controller placement problem in software defined networks," IEEE Communications Letters, vol. 18, pp. 1339-1342, 2014.

13.S. Khuller and Y. J. Sussmann, "The capacitated k-center problem," SIAM Journal on Discrete Mathematics, vol. 13, pp. 403-418, 2000.

14.Y. Hu, T. Luo, W. Wang, and C. Deng, "On the load balanced controller placement problem in Software defined networks," in 2016 2nd IEEE International Conference on Computer and Communications (ICCC), 2016, pp. 2430-2434.

15.L. Han, Z. Li, W. Liu, K. Dai, and W. Qu, "Minimum control latency of SDN controller placement," in 2016 IEEE Trustcom/BigDataSE/ISPA, 2016, pp. 2175-2180.

16.Y. Zhang, N. Beheshti, and M. Tatipamula, "On resilience of split-architecture networks," in 2011 IEEE Global Telecommunications Conference-GLOBECOM 2011, 2011, pp. 1-6.

17.Y.-N. Hu, W.-D. Wang, X.-Y. Gong, X.-R. Que, and S.-D. Cheng, "On the placement of controllers in software-defined networks," The Journal of China Universities of Posts and Telecommunications, vol. 19, pp. 92-171, 2012.

18.L. F. Müller, R. R. Oliveira, M. C. Luizelli, L. P. Gaspary, and M. P. Barcellos, "Survivor: An enhanced controller placement strategy for improving SDN survivability," in 2014 IEEE Global Communications Conference, 2014, pp. 1909-1915.

19.Y. Jimenez, C. Cervelló-Pastor, and A. J. García, "On the controller placement for designing a distributed SDN control layer," in 2014 IFIP Networking Conference, 2014, pp. 1-9.

20.Y. Hu, W. Wang, X. Gong, X. Que, and S. Cheng, "On reliability-optimized controller placement for software-defined networks," China Communications, vol. 11, pp. 38-54, 2014.

21.M. Tanha, D. Sajjadi, and J. Pan, "Enduring node failures through resilient controller placement for software defined networks," in 2016 IEEE Global Communications Conference (GLOBECOM), 2016, pp. 1-7.

22.A. Sallahi and M. St-Hilaire, "Optimal model for the controller placement problem in software defined networks," IEEE communications letters, vol. 19, pp. 30-33, 2015.

23.H. K. Rath, V. Revoori, S. M. Nadaf, and A. Simha, "Optimal controller placement in Software Defined Networks (SDN) using a non-zero-sum game," in Proceeding of IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks 2014, 2014, pp. 1-6.

24.A. Ruiz-Rivera, K.-W. Chin, and S. Soh, "GreCo: An energy aware controller association algorithm for software defined networks," IEEE communications letters, vol. 19, pp. 541-544, 2015.

25.M. T. I. ul Huque, G. Jourjon, and V. Gramoli, "Revisiting the controller placement problem," in 2015 IEEE 40th Conference on Local Computer Networks (LCN), 2015, pp. 450-453.

26.A. Sallahi and M. St-Hilaire, "Expansion model for the controller placement problem in software defined networks," IEEE Communications Letters, vol. 21, pp. 274-277, 2017.

27.D. Hock, M. Hartmann, S. Gebert, M. Jarschel, T. Zinner, and P. Tran-Gia, "Pareto-optimal resilient controller placement in SDN-based core networks," in Proceedings of the 2013 25th International Teletraffic Congress (ITC), 2013, pp. 1-9.

28.S. Lange, S. Gebert, T. Zinner, P. Tran-Gia, D. Hock, M. Jarschel, et al., "Heuristic approaches to the controller placement problem in large scale SDN networks," IEEE Transactions on Network and Service Management, vol. 12, pp. 4-17, 2015.

29.D. Tuncer, M. Charalambides, S. Clayman, and G. Pavlou, "Adaptive resource management and control in software defined networks," IEEE Transactions on Network and Service Management, vol. 12, pp. 18-33, 2015.

30.J. Liao, H. Sun, J. Wang, Q. Qi, K. Li, and T. Li, "Density cluster based approach for controller placement problem in large-scale software defined networkings," Computer Networks, vol. 112, pp. 24-35, 2017.

31.B. Zhang, X. Wang, L. Ma, and M. Huang, "Optimal controller placement problem in Internet-oriented software defined network," in 2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC), 2016, pp. 481-488.

32.G. Wang, Y. Zhao, J. Huang, and Y. Wu, "An effective approach to controller placement in software defined wide area networks," IEEE Transactions on Network and Service Management, vol. 15, pp. 344-355, 2017.

33.M. F. Bari, A. R. Roy, S. R. Chowdhury, Q. Zhang, M. F. Zhani, R. Ahmed, et al., "Dynamic Controller Provisioning in Software Defined Networks," in CNSM, 2013, pp. 18-25.

34.Y. Hu, T. Luo, N. C. Beaulieu, and C. Deng, "The energy-aware controller placement problem in software defined networks," IEEE Communications Letters, vol. 21, pp. 741-744, 2017.

35.G. Ishigaki and N. Shinomiya, "Controller placement algorithm to alleviate burdens on communication nodes," in 2016 International Conference on Computing, Networking and Communications (ICNC), 2016, pp. 1-5.

36.SDN-Enabled Programmatic Control of the Network. Available: http://www.brocade.com/en/backend-content/

pdf-page.html?/content/dam/common/documents/content-types/solution-brief/brocade-mlx-service-provider-sb.pdf

37.Corsa’s DP2100 SDN switching and routing platform. Available: http://www.corsa.com/products/dp2100/

38.R. Daniels and D. Whittaker. (2015). Benchmarking the SDN Switch. Available: https://www.opennetworking.org/

images/stories/sdn-solution-showcase/germany2015/Spirent%20-%20Benchmarking%20the%20SDN%20Switch.pdf

39.C. Veness, "Calculate distance and bearing between two Latitude/Longitude points using Haversine formula in JavaScript," Movable Type Scripts, 2011.

40.G. Wang, Y. Zhao, J. Huang, and R. M. Winter, "On the data aggregation point

 

 

 

 

placement in smart meter networks," in 2017 26th International Conference on Computer Communication and Networks (ICCCN), 2017, pp. 1-6.

41.S. Skiena, "Dijkstra’s algorithm," in Implementing discrete mathematics: combinatorics and graph theory with mathematica, ed: Addison-Wesley Reading, MA, 1990, pp. 225-227.

42.S. Knight, H. X. Nguyen, N. Falkner, R. Bowden, and M. Roughan, "The internet topology zoo," IEEE Journal on Selected Areas in Communications, vol. 29, pp. 1765-1775, 2011.

43.(2019, 02/05/2019). The Internet Topology Zoo. Available: http://www.topology-zoo.org/

 

 

51

 


مقالات مرتبط

حقوق این وب‌سایت متعلق به سامانه مدیریت نشریات رایمگ است.
حق نشر © 1403-1396

صفحه اصلی| عضویت/ ورود| درباره رایمگ| تماس با ما|
[English] [العربية] [en] [ar]