Decentralized approaches for admission, routing and flow problems

Online control of large dynamic networks is challenging because little data are in general available about the environment, because decentralized strategies have to be employed, which rely on the knowledge of local data only, and because faults can occur. In this regard, three problems are addressed in this thesis. The first problem concerns the scheduling of some requests of a limited resource occurring at different times, from a supplier with limited capacity. The goal is that of minimizing the average waiting time for these requests. The problem is formulated as an optimal control one, in which the control is the supply strategy, specified by some constraints, and the state variables are associated with the waiting times of the demands. The exact optimal problem requires mixed-integer linear programming; some relaxed versions are also formulated and, in particular, one of these is based on linear programming and efficiently provides some lower bound. Some online heuristics are analyzed, both centralized and decentralized, for which, in general, no a-posteriori optimality of the solution is obtained. The second problem is an agent-based minimum path one. Some tokens (agents) are injected in the network, in some source nodes, and must travel in the network to find an exit, a sink. A simple decentralized policy is proposed. This policy allows or denies the transitions of the tokens along the arcs on the basis of a simple local threshold mechanism. In particular, a transition occurs through a directed arc if the amount of tokens present in the origin node minus the amount tokens present in the end node exceeds the arc cost. Despite the very simple local mechanism, in the long run, all the injected tokens leave the network by the closest sink through the shortest path, although some tokens are, unavoidably, lost during the initial transient exploring phase. This issue can be avoided by enhancing the policy allowing the generation of some virtual tokens. Some constraints to the maximum number of transitions can also be imposed to all tokens. In fact, this is equivalent to applying the policy proposed for the unconstrained case to the so-called expanded network. The third problem considers flow networks with buffers in the nodes containing an amount of a continuous resource at a given level (state), which is transferred between nodes by controlled flows along the arcs. A decentralized control is formulated to meet a given flow demand, stabilize the system and asymptotically minimize the p-norm of the flow. This control is specified at the arc level and depends only on the value of p and on the difference of the states of the two arc's endnodes. After an initial transient, the unique optimal desired flow is obtained when 1 < p < ∞. When p = 1 sparsity of the solution tends to emerge, while when p = ∞ fairness is promoted; however, no optimality or uniqueness of solution is achieved in these two cases: suboptimal solutions can be obtained by applying the control with p → 1 and p → ∞, respectively. Enhancements can be applied to support uncontrollable flows governed by unknown dynamics depending on the buffer levels and buffer level control to a desired set-point. In this case, a decentralized proportional-integral control is adopted.