On Optimal Packet Routing in Deterministic DTNs

Giovanni Neglia (1) , Xiaolan Zhang (2) , Jim Kurose (3) , Don Towsley (3) , Haixiang Wang (2)

1 MAESTRO - Models for the performance analysis and the control of networks
2 Computer & Information Sciences Department, Fordham University
3 Department of Computer Science [Amherst]

In this paper, we investigate the problem of determining the routing that minimizes the maximum/average delivery time or the maximum/average delivery delay for a set of packets in a deterministic Delay Tolerant Network, i.e. in a network for which all the nodes' transmission opportunities are known in advance. While the general problem with multiple sources and multiple destinations is NP-hard, we present a polynomial time algorithm that can efficiently compute the optimal routing in the case of a single destination or of a single packet that needs to be routed to multiple destinations.

Mots clés: delay tolerant networks; routing

Domaines: Réseaux et télécommunications [cs.NI]

Giovanni Neglia, Xiaolan Zhang, Jim Kurose, Don Towsley, Haixiang Wang. On Optimal Packet Routing in Deterministic DTNs. IEEE VTC - 77th Vehicular Technology Conference, Jun 2013, Dresden, Germany. pp.1-5, ⟨10.1109/VTCSpring.2013.6692662⟩. ⟨hal-00923328⟩