1. Michela Lorandi and Leonardo Lucio Custode and Giovanni Iacca. 2021. Genetic Improvement of Routing Protocols for Delay Tolerant Networks. arXiv:2103.07428 [cs.NI] https://arxiv.org/abs/2103.07428 To appear on ACM Transactions on Evolutionary Learning and Optimization. ------------ 2. Michela Lorandi, Via Sommarive, 9 - 38123 Pov:q o (TN) , michela.lorandi@studenti.unitn.it, Tel. +39 346 66800681 Leonardo Lucio Custode, Via Sommarive, 9 - 38123 Povo (TN), leonardo.custode@unitn.it, Tel. +39 388 1767536 Giovanni Iacca, Via Sommarive, 9 - 38123 Povo (TN), giovanni.iacca@unitn.it, Tel. +39 389 8088796 ------------ 3. Corresponding author: Giovanni Iacca, giovanni.iacca@unitn.it ------------ 4. Routing plays a fundamental role in network applications, but it is especially challenging in Delay Tolerant Networks (DTNs). These are a kind of mobile ad hoc networks made of e.g. (possibly, unmanned) vehicles and humans where, despite a lack of continuous connectivity, data must be transmitted while the network conditions change due to the nodes' mobility. In these contexts, routing is NP-hard and is usually solved by heuristic "store and forward" replication-based approaches, where multiple copies of the same message are moved and stored across nodes in the hope that at least one will reach its destination. Still, the existing routing protocols produce relatively low delivery probabilities. Here, we genetically improve two routing protocols widely adopted in DTNs, namely Epidemic and PRoPHET, in the attempt to optimize their delivery probability. First, we dissect them into their fundamental components, i.e., functionalities such as checking if a node can transfer data, or sending messages to all connections. Then, we apply Genetic Improvement (GI) to manipulate these components as terminal nodes of evolving trees. We apply this methodology, in silico, to six test cases of urban networks made of hundreds of nodes, and find that GI produces consistent gains in delivery probability in four cases. We then verify if this improvement entails a worsening of other relevant network metrics, such as latency and buffer time. Finally, we compare the logics of the best evolved protocols with those of the baseline protocols, and we discuss the generalizability of the results across test cases. ------------ 5. List of claimed criteria: A, B, D, E, F, G ------------ 6. Justification of the claims: A) Several patents address the methods and protocols used for communication in delay tolerant networks, e.g. US8787257B2, KR101534526B1, CN102664805B, CN101478805B, CN102006237A, KR101294366B1. This means that the protocols obtained by using our results may be patentable. B) The protocols obtained are statistically equal to or better than the original protocols (Epidemic, PRoPHET) and improvements of the PRoPHET protocol (PRoPHETv2, Efficient Evict Policy for PRoPHET, PRoPHET+). These methods represent the state-of-the-art in the area of routing in delay tolerant networks. D) The new protocols obtained are publishable as new scientific results independently of the fact that they have been mechanically obtained. In fact, they could be published e.g. in computer networking venues, regardless the fact that they were obtained by means evolutionary search, to advance the state-of-the-art in the area of routing in delay tolerant networks. E, F) The obtained protocols are, in most cases, statistically better than the state-of-the-art solutions (i.e., PRoPHET and its variants PRoPHETv2, Efficient Evict Policy for PRoPHET, PRoPHET+). G) The obtained protocols do not solve the problem of the routing in delay tolerant networks (it is an NP-hard problem), but it improves the performance over existing methods. ------------ 7. Michela Lorandi and Leonardo Lucio Custode and Giovanni Iacca. 2021. Genetic Improvement of Routing Protocols for Delay Tolerant Networks. arXiv:2103.07428 [cs.NI] https://arxiv.org/abs/2103.07428. To appear on ACM Transactions on Evolutionary Learning and Optimization. ------------ 8. Any prize money, if any, is to be divided in the following percentages: - Michela Lorandi: 50% - Leonardo Lucio Custode: 25% - Giovanni Iacca: 25% ------------ 9. We expect that our results would be recognized as of extreme impact, especially in the computer networking field. In fact, our results show that mechanically created solutions (in just a few computing hours) were able to obtain better performance than what humans were able to achieve in a decade (note that PRoPHETv2, the best variant of PRoPHET to date, is from 2011). Moreover, the proposed Genetic Improvement methodology may be applicable (and will be applied, in our future works) to other protocols and protocol layers. As such, we believe that our work can be considered "the best" as it can potentially attract the interest of the computer network community towards Evolutionary Computation. ------------ 10. The evolutionary computation technique used in our work are: GP (genetic programming) and GI (genetic improvement). ------------ 11. The paper has been unconditionally accepted for publication on ACM Transactions on Evolutionary Learning and Optimization. See the attached decision letter from the Editors-in-Chief, Juergen Branke and Darrell Whitley.