Dağıtık simülasyon sistemleri için yeni bir yönlendirme algoritması ve uygulaması

Abstract

ÖZET: Modelleme ve Simülasyon (M&S), DEVS, Ağ Yönetimi, Ekoloji, İnternet Dağıtık sistemler, çeşitli algoritmalar ve teknolojiler kullanarak birbirleriyle iletişim yapan birimlerden oluşur. İletişim içerisinde bulunan sistemlerin uyarlanabilirlik, ölçeklenebilirlik, güvenilirlik (sürdürülebilirlik) gibi bir takım niteliklere sahip olması gerekmektedir. Sürekli yeni servis türlerinin ve heterojen ağların bir bütün olarak dahil edilmesiyle, ağlar karmaşık bir hal almaktadır. Ağ sistemlerinin, sistemin büyüyerek daha karmaşık bir hal alması karşısında yeni ve daha gelişmiş servisleri sunması beklenmektedir. Artan karmaşıklık ve boyut nedeniyle ortaya çıkan sorunların üstesinden gelmek amacıyla geliştirilen çeşitli yöntemler bilgisayar ağlarının ihtiyaçlarına göre kullanılmaktadır. Günümüzde ağlar, hız ve işlem yapma gücündeki ihtiyaçlara cevap verebilmek için hesaplama işlevleri merkezi bir yapıdan dağıtık bir yapıya doğru kaymaktadır. Performans / maliyet oranının göz önünde tutulması zorunluluğu bu değişimi yeni işlem yapma kapasitelerinin tasarlanması üzerine daha fazla yöneltmektedir. Bu tezde, dağıtık sistemlerin karmaşıklık, ölçeklenebilirlik, vb. sorunlarının incelenmesi, tasarım alternatiflerinin araştırılması ve farklı çözüm yaklaşımlarının incelenmesi amacıyla modelleme ve simülasyon araçlarının kullanıldığı bir çalışma / uygulama gerçekleştirilmiştir. İnternetin yakın gelecekte 1 milyar düğüme erişeceği düşünülürse, ölçeklenebilirlik kavramının ağların yönetiminde, modellenmesinde ve simülasyonunda yeni boyutlar kazanacağı açıktır. Statik topoloji üreten simülatörler (COMNET, NS2, OPNET, vb.) küçük ağları çalışmak için ideal platformlarken, günümüzde üstel olarak artan ağ sistemlerini modellemede ve değişken yapılı ağ sistemlerinin performansını test etmede yetersiz kalmaktadırlar. Ayrıca, bu simülatörlerin mimarilerinin bir çoğu soyutlama ve hiyerarşiden yoksun olmaları yanında çok büyük hesaplama maliyeti oluşturmaktadırlar. Yapılan çalışmada, belirtilen kısıtlamaları / sakıncaları ortadan kaldırmaya yönelik olarak DEVS metodolojisi kullanılarak bir ağ simülatörü geliştirilmiştir. Tasarlanan ağ sisteminin modellenmesi; ağ bileşenlerinin tanımlanmasını, bu bileşenlerde çalışacak yazılım nesnelerinin, etkileşimlerinin ve bu varlıkların işlem yapan düğümlere dağıtılmalarını, ağ topolojilerinin ve iletişim protokollerinin tanımlanmasını içermektedir. Düğümler ve linkler temel ağ bileşenleri olarak tanımlandıktan sonra, DEVS birleşik model tanımı kullanılarak temel bileşenler birbirine bağlanıp birleşik ağ modelleri oluşturulmuştur. Geliştirilen ağ ortamı farklı yönlendirme algoritmalarını (en kısa yol, uzaklık vektörü, oğul zekası, vb.) modelleyebilme yeteneğine sahiptir. Geliştirilen simülatörün üstünlüklerini ve performansını göstermek amacıyla binlerce düğümden oluşan ağlar modellenmiştir. Modellenen ağlar farklı trafik yükleri altında çalıştırılarak, çalışma sırasında geliştirilen yönlendirme algoritmasının performansı incelendi. Gerçekleştirilen uygulamalardan, geliştirilen simülatörün son derece paralel, esnek ve hızlı çalıştığını, değişik teknolojileri barındıran uygulamaları geliştirebilme yeteneğine sahip olduğu gözlemlendi. Tez içerisinde yapılan çalışmalar dört grup altında özetlenebilir: i- Farklı yönlendirme algoritmalarının incelenebilmesine olanak tanıyan bir ortam oluşturulması amacıyla örnek bir ağ modelinin DEVS (Discrete Event System Specification) kullanılarak modellenmesi ve simülasyonu işlemleri gerçekleştirildi. ii- Büyük ölçekli biyolojik sistemlerde (karıncalar, halanları, termitler, vb.) kullanılan optimizasyon düzeneklerinden esinlenerek ağlarda kullanılacak kural-tabanlı yeni bir yönlendirme algoritması geliştirildi. iii- Oluşturulan ağ modeline hali hazırda kullanılmakta olan yönlendirme algoritmaları ile çalışma sırasında geliştirilen biyolojik-tabanlı yönlendirme algoritması uygulanarak, özellikle biyolojik-tabanlı yönlendirme algoritmalarının klasik yönlendirme algoritmalanyla karşılaştırılması yapıldı. iv- Geliştirilen algoritmanın büyük ölçekli ağlarda kullanılabilirliğini göstermek amacıyla, çeşitli boyutlarda ağ modelleri oluşturularak kural-tabanlı algoritmanın performansı incelendi.

Keywords: Modeling & Simulation, DEVS, Network Management, Ecology, Internet Network systems must communicate with one another using a variety of algorithms and technologies. Many systems supporting interconnectivity are required to exhibit essential traits such as adaptability, scalability, and reliability (survivability). At the same time, these networked systems are expected to offer new and more sophisticated services in the face of increasing system heterogeneity. Consequently, to cope with the management of such networks in the presence of ever increasing complexity, various decentralized and centralized approaches are being used to address the needs of private and public organizations. In this thesis, in order to examine some problems of distributed systems such as complexity and scalab resolution levels, a modeling and simulati methodologies and tools are used. Scalabil lity, search for design alternatives and propose various on study is performed in which modeling and simulation ty issue has become very crucial concept for modeling and simulation of the Internet. Simulators generating static topology such as COMNET, NS2, and OPNET are ideal platforms for studying small networks, but incapable of modeling and testing large-scale and dynamic structure networks. Furthermore, due to lack of hierarchy and abstraction in their structure, it is difficult to create and manage large model families. In this study, a network simulator is developed to bring solutions to above problems by using DEVS modeling and simulation methodology. To develop and study dynamic and adaptive swarm-based routing protocols of biological, we have devised a DEVS (Discrete Event System Specification) network model. The nodes and links are characterized as the elementary network components. These models and networks are implemented in the DEVSJAVA modeling and simulation environment which is an implementation of the DEVS framework. The developed network environment is capable of representing behavior of different routing algorithms (e.g. shortest-path, distance vector and other swarm algorithms). For the purpose of modeling of a distributed networked system, we define a network in terms of its components (e.g. nodes and links) and their hierarchical structure. The network is then modeled as DEVS atomic and coupled models. To do this we closely examine biological aspects of honeybee colony and their mappings into DEVS models. For example, the routing policy of the network which is embedded in every node is similar to a honeybee having its own capability to search for food and communicate with other honeybees. Using the DEVS hierarchical model composition concept, we develop simulation models of networks with varying topologies and scales. For example, we will use clusters to study its impact on reducing communication and increasing performance. The explicit and hidden behaviors of these networks are observed under various experimental configurations - e.g., nodes and links are assigned different capacities. In this thesis, performed operations can be summarized into four steps: i- Modeling and simulation of distributed systems together with nodes and links components using DEVS. ii- Developing a rule-based swarm intelligence routing algorithm by inspiring from honeybee scout- recruit system. iii- Modeling a state-of-the-art routing algorithm in order to depict advantages of developed algorithm. iv- Creating large-scale networks models having from tens to several thousands of components and observing the behavior of developed algorithm. Xlll