A fuzzy evolutionary algorithm for topology design of campus networks

Abstract

The topology design of campus networks is a hard constrained combinatorial optimization problem It consists of deciding the number type and location of the active network elements (nodes) and the links This choice is dictated by physical and technological constraints and must optimize several objectives Important objectives are monetary cost network delay hop count between communicating pairs and reliability Furthermore due to the nondeterministic nature of network traffic and other design parameters the objective criteria are imprecise Fuzzy Logic provides a suitable mathematical framework in such a situation In this paper we present a Simulated Evolution algorithm for the design of campus network topology To intensify the search we have also incorporated Tabu Searchbased characteristics in the allocation phase of the SE algorithm The proposed fuzzy SE algorithm is compared with the Simulated Annealing heuristic Comparison is also made with EsauWilliams (EW) algorithm a well known constructive algorithm for the category of problems addressed in this work Results show that on all test cases the Simulated Evolution algorithm exhibits a more intelligent search of the solution subspace and was able to find better solutions than Simulated Annealing and EsauWilliams algorithm

إن التصم م الطبولوجي لشبكات المجمعات تطلب حلولا تقر ب ة ضمن إطار من المتطلبات الصعبة، ح ث شتمل التصم م على تحد د عدد العناصر الفعالة ونوعها وموقعها وخطوط وصلها ضمن الحدود الف ز ائ ة والتقن ة، مما وجب إ جاد نقاط تقارب ب ن العد د من المتطلبات المتعارضة، وأھم ھذه المتطلبات التكلفة المال ة، وزمن النقل في الشبكة، وعدد القفزات ب ن نقاط الاتصال، وموثوق ة الشبكة إضافة إلى ذلك فإن ھذه المتطلبات غ ر محددة بشكل دق ق بسبب صعوبة التنبؤ بحركة الب انات داخل الشبكة وفي مثل ھذه الحالات وفر المنطق المبھم إطارا ر اض ا مناسبا لحل المشكلة وسوف نقدم في ھذا البحث خوارزم ة للتصم م الطبولوجي لشبكات المجمعات عتمد على خوارزم التطور المحاكي ولتفع ل عمل ة البحث في مرحلة التوز ع قمنا باستخدام خواص للبحث مستقاة وقد قمنا بمقارنة الخوارزم المقترح مع كلتا الخوارزم ت ن Tabu Search من خوارزم وقد أظھرت النتائج في كل الحالات التي تم اختبارھا Esau–Williams و Simulated Annealing تفوق خوارزم ة التطور المحاكي على الخوارزم ت ن الأُخر ن وسوف نقدم في ھذا البحث خوارزم ة للتصم م الطبولوجي لشبكات المجمعات عتمد على خوارزم التطور المحاكي ولتفع ل عمل ة البحث في مرحلة التوز ع قمنا باستخدام خواص للبحث مستقاة وقد قمنا بمقارنة الخوارزم المقترح مع كلتا الخوارزم ت ن Tabu Search من خوارزم وقد أظھرت النتائج في كل الحالات التي تم اختبارھاEsau–Williams و Simulated Annealing تفوق خوارزم ة التطور المحاكي على الخوارزم ت ن الأخر ن