Predictive routing for mobile networks

Abstract

Bilgisayar ağlarında yönlendirme çok önemli bir problemdir. Yanlış yönlendirme kararları daha fazla tıkanıklığa yol açacak ve yüksek tıkanıklık daha fazla gecikmeye ve paket kaybına neden olacaktır. Bilgisayar ağları giderek daha karmaşık hale gelmekte ve ağlar giderek daha kalabalıklaşmaktadır. Yönlendirme problemi için algoritmalar onlarca yıl önce tasarlanmıştır. Bu nedenle, yeni yönlendirme algoritmalarının tasarlanması gerekmektedir. Bu tezde, yönlendirme problemi için derin takviyeli öğrenme tabanlı bir algoritma önerilmiştir. Öğrenen ajan yeteneği ile daha akıllı yönlendirme kararları alınabilir. Tezin amacı, teslim edilen paket sayısı açısından Dijkstra en kısa yol algoritması tabanlı yönlendirmeyi aşmak ve daha düşük ortalama gecikmeye sahip olmaktır. Önerilen yönlendirme algoritması Derin Çift QAğına dayanmaktadır. Sonuçları test etmek için Simply adlı Python kütüphanesi ile bir mobil ağ simülasyon ortamı yazılmıştır. Test sonuçlarından önce, en iyi sinir ağı mimarisini bulmak için farklı türde araştırmalar yapılmıştır. En iyi sinir ağı mimarisi bulunduktan sonra, test aşamasından önce farklı türde ödül fonksiyonları denenmiştir. Tüm testlerden sonra, iki farklı ödül fonksiyonuna ve aynı mimariye sahip önerilen yöntemler Dijkstra en kısa yol tabanlı yönlendirme algoritmasına karşı test edilmiştir. Test ortamı, cihazların hareket etmediği ve cihazın her zaman adımında bir paket ürettiği 10 cihaz, 10 yönlendirici ve 10 baz istasyonundan oluşan mobil ağ topolojisidir. 95 GB, 45 GB ve 22 GB her bir test kurulumundaki yönlendiriciler için tampon boyutlarıdır. Önerilen yöntemlerin avantajları sonuçlarda gösterilmiştir. Dijkstra tabanlı yönlendirme her testte yakın sonuçlar göstermiştir, ancak önerilen yöntemler kendi aralarında bile ödül fonksiyonu tasarımları nedeniyle kuruluma bağlı olarak performans açısından farklılık göstermektedir. Önerilen yöntemler, daha büyük ağlarda kullanılmak üzere genişletilebilecek umut verici sonuçlar vermiştir. Çalışmanın bir sonraki adımı hareketli cihazların olduğu ağ ve algoritmanın gerçek hayattaki ağ kurulumunda gösterilmesi olacaktır.Routing in computer networks is a crucial problem. Wrong routing decisions will lead to more congestion and high congestion will cause more delays and packet loss. Computer networks are getting more complex, and networks are getting more crowded. The algorithms for the routing problem were designed decades ago. So, the design of new routing algorithms is needed. In this thesis, a deep reinforcement learning based algorithm is proposed for the routing problem. With the ability of learning agent, more intelligent routing decisions can be made. The aim of the thesis is to surpass Dijkstra shortest path algorithm-based routing in terms of number of packets delivered and have lower average delay. The proposed routing algorithm is based on Deep Double Q-Network (DDQN). To test the proposed method, a mobile network simulation environment with Python library called Simply is written. Before the tests, different types of research have been conducted to find the best neural network architecture. After finding the best neural network architecture, different types of reward functions have been tried before the test phase. After all the tests, proposed methods with two different reward functions and same architecture have been tested against Dijkstra shortest path-based routing algorithm. The test environment is mobile network topology which has 10 hosts where hosts are not moving and each host generates a packet in each timestep, 10 routers and 10 base stations. 95 GB, 45 GB and 22 GB are buffer sizes for the routers in each test setup. The advantages of proposed methods are shown in the results. Dijkstra based routing showed close results in each test but even between the proposed methods differ in terms of performance depending on the setup because of their reward function design. The proposed methods have given promising results that can be extended for usage in bigger networks. The next step of the work will be network with moving hosts and demonstration of the algorithm in the real-life network setup.