Optimal Link Deployment for Minimizing Average Path Length in Chain Networks

Abstract : This study considers chain-topology networks, which has certain inherent limitations, and presents an optimization model that augments the network by the addition of a new link, with the objective of minimizing Average Path Length (APL).We built up a mathematical model for APL, and formulated our problem as Integer Programming. Then, we solved the problem experimentally by brute-force, trying all possible topologies, and found the optimal solutions that minimize APL for certain network sizes up to 1000 nodes. Later on, we derived analytical solution of the problem by applying Linear Regression method on the experimental results obtained.We showed that APL on a chain-topology network is decreased by the proposed optimization model, at a gradually increasing rate from 24.81 % to asymptotic value of 41.4 % as network grows. Additionally, we found that normalized length of the optimal solutions decreases logarithmically from 100 % to 58.6048 % as network size gets larger.
Type de document :
Communication dans un congrès
Lefteris Mamatas; Panagiotis Papadimitriou; Ibrahim Matta; Yevgeni Koucheryavy. 14th International Conference on Wired/Wireless Internet Communication (WWIC), May 2016, Thessaloniki, Greece. Lecture Notes in Computer Science, LNCS-9674, pp.348-359, 2016, Wired/Wireless Internet Communications. 〈10.1007/978-3-319-33936-8_27〉
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01434864
Contributeur : Hal Ifip <>
Soumis le : vendredi 13 janvier 2017 - 14:34:46
Dernière modification le : vendredi 13 janvier 2017 - 14:45:31
Document(s) archivé(s) le : vendredi 14 avril 2017 - 19:54:31

Fichier

 Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Zeki Bilgin, Murat Gunestas, Omer Demir, Sahin Buyrukbilen. Optimal Link Deployment for Minimizing Average Path Length in Chain Networks. Lefteris Mamatas; Panagiotis Papadimitriou; Ibrahim Matta; Yevgeni Koucheryavy. 14th International Conference on Wired/Wireless Internet Communication (WWIC), May 2016, Thessaloniki, Greece. Lecture Notes in Computer Science, LNCS-9674, pp.348-359, 2016, Wired/Wireless Internet Communications. 〈10.1007/978-3-319-33936-8_27〉. 〈hal-01434864〉

Partager

Métriques

Consultations de la notice

54