Flow optimization in Delay Tolerant Networks using dual decomposition

We study flow optimization in Delay Tolerant Networks (DTNs), which we model using Capacity Region Evolving Graphs (CREGs). CREGs consist of different instances (called replicas) of the network graph in cascade; each replica is associated with a distinct time period (called epoch) and its own Capacity Region. Although CREGs can model any DTN, they are particularly well suited for the study of wireless ones. We define a single-commodity utility maximization problem in a CREG of T replicas that contains as special cases various interesting flow maximization problems. Using dual decomposition, we cast the maximization as a dual problem that can be solved iteratively and where in each iteration a set of T problems, T times smaller than the original, are solved, potentially (if multiple processors are available) in parallel. In addition, we propose two suboptimal utility maximization heuristics that operate on an epoch-by-epoch basis and we discuss a multi-commodity extension to the problem.