Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRobust Distributed Routing in Dynamical Flow Networks - Part II: Strong Resilience, Equilibrium Selection and Cascaded Failures
141
0
0.0
(
0
)
Added by
Ketan Savla
Publication date
2011
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Strong resilience properties of dynamical flow networks are analyzed for distributed routing policies. The latter are characterized by the property that the way the inflow at a non-destination node gets split among its outgoing links is allowed to depend only on local information about the current particle densities on the outgoing links. The strong resilience of the network is defined as the infimum sum of link-wise flow capacity reductions under which the network cannot maintain the asymptotic total inflow to the destination node to be equal to the inflow at the origin. A class of distributed routing policies that are locally responsive to local information is shown to yield the maximum possible strong resilience under such local information constraints for an acyclic dynamical flow network with a single origin-destination pair. The maximal strong resilience achievable is shown to be equal to the minimum node residual capacity of the network. The latter depends on the limit flow of the unperturbed network and is defined as the minimum, among all the non-destination nodes, of the sum, over all the links outgoing from the node, of the differences between the maximum flow capacity and the limit flow of the unperturbed network. We propose a simple convex optimization problem to solve for equilibrium limit flows of the unperturbed network that minimize average delay subject to strong resilience guarantees, and discuss the use of tolls to induce such an equilibrium limit flow in transportation networks. Finally, we present illustrative simulations to discuss the connection between cascaded failures and the resilience properties of the network.
rate research
Read More
Robustness of distributed routing policies is studied for dynamical flow networks, with respect to adversarial disturbances that reduce the link flow capacities. A dynamical flow network is modeled as a system of ordinary differential equations derived from mass conservation laws on a directed acyclic graph with a single origin-destination pair and a constant inflow at the origin. Routing policies regulate the way the inflow at a non-destination node gets split among its outgoing links as a function of the current particle density, while the outflow of a link is modeled to depend on the current particle density on that link through a flow function. The dynamical flow network is called partially transferring if the total inflow at the destination node is asymptotically bounded away from zero, and its weak resilience is measured as the minimum sum of the link-wise magnitude of all disturbances that make it not partially transferring. The weak resilience of a dynamical flow network with arbitrary routing policy is shown to be upper-bounded by the networks min-cut capacity, independently of the initial flow conditions. Moreover, a class of distributed routing policies that rely exclusively on local information on the particle densities, and are locally responsive to that, is shown to yield such maximal weak resilience. These results imply that locality constraints on the information available to the routing policies do not cause loss of weak resilience. Some fundamental properties of dynamical flow networks driven by locally responsive distributed policies are analyzed in detail, including global convergence to a unique limit flow.
Robustness of routing policies for networks is a central problem which is gaining increased attention with a growing awareness to safeguard critical infrastructure networks against natural and man-induced disruptions. Routing under limited information and the possibility of cascades through the network adds serious challenges to this problem. This abstract considers the framework of dynamical networks introduced in our earlier work [1,2], where the network is modeled by a system of ordinary differential equations derived from mass conservation laws on directed acyclic graphs with a single origin-destination pair and a constant inflow at the origin. The rate of change of the particle density on each link of the network equals the difference between the inflow and the outflow on that link. The latter is modeled to depend on the current particle density on that link through a flow function. The novel modeling element in this paper is that every link is assumed to have finite capacity for particle density and that the flow function is modeled to be strictly increasing as density increases from zero up to the maximum density capacity, and is discontinuous at the maximum density capacity, with the flow function value being zero at that point. This feature, in particular, allows for the possibility of spill-backs in our model. In this paper, we present our results on resilience of such networks under distributed routing, towards perturbations that reduce link-wise flow functions.
We propose a dynamical model for cascading failures in single-commodity network flows. In the proposed model, the network state consists of flows and activation status of the links. Network dynamics is determined by a, possibly state-dependent and adversarial, disturbance process that reduces flow capacity on the links, and routing policies at the nodes that have access to the network state, but are oblivious to the presence of disturbance. Under the proposed dynamics, a link becomes irreversibly inactive either due to overload condition on itself or on all of its immediate downstream links. The coupling between link activation and flow dynamics implies that links to become inactive successively are not necessarily adjacent to each other, and hence the pattern of cascading failure under our model is qualitatively different than standard cascade models. The magnitude of a disturbance process is defined as the sum of cumulative capacity reductions across time and links of the network, and the margin of resilience of the network is defined as the infimum over the magnitude of all disturbance processes under which the links at the origin node become inactive. We propose an algorithm to compute an upper bound on the margin of resilience for the setting where the routing policy only has access to information about the local state of the network. For the limiting case when the routing policies update their action as fast as network dynamics, we identify sufficient conditions on network parameters under which the upper bound is tight under an appropriate routing policy. Our analysis relies on making connections between network parameters and monotonicity in network state evolution under proposed dynamics.
The paper investigates the throughput behavior of single-commodity dynamical flow networks governed by monotone distributed routing policies. The networks are modeled as systems of ODEs based on mass conversation laws on directed graphs with limited flow capacities on the links and constant external inflows at certain origin nodes. Under monotonicity assumptions on the routing policies, it is proven that a globally asymptotically stable equilibrium exists so that the network achieves maximal throughput, provided that no cut capacity constraint is violated by the external inflows. On the contrary, should such a constraint be violated, the network overload behavior is characterized. In particular, it is established that there exists a cut with respect to which the flow densities on every link grow linearly over time (resp. reach their respective limits simultaneously) in the case where the buffer capacities are infinite (resp. finite). The results employ an $l_1$-contraction principle for monotone dynamical systems.
In Part I cite{Zhao13TSPasync1}, we introduced a fairly general model for asynchronous events over adaptive networks including random topologies, random link failures, random data arrival times, and agents turning on and off randomly. We performed a stability analysis and established the notable fact that the network is still able to converge in the mean-square-error sense to the desired solution. Once stable behavior is guaranteed, it becomes important to evaluate how fast the iterates converge and how close they get to the optimal solution. This is a demanding task due to the various asynchronous events and due to the fact that agents influence each other. In this Part II, we carry out a detailed analysis of the mean-square-error performance of asynchronous strategies for solving distributed optimization and adaptation problems over networks. We derive analytical expressions for the mean-square convergence rate and the steady-state mean-square-deviation. The expressions reveal how the various parameters of the asynchronous behavior influence network performance. In the process, we establish the interesting conclusion that even under the influence of asynchronous events, all agents in the adaptive network can still reach an $O( u^{1 + gamma_o})$ near-agreement with some $gamma_o > 0$ while approaching the desired solution within $O( u)$ accuracy, where $ u$ is proportional to the small step-size parameter for adaptation.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
