Adversarial Queueing Model for Continuous Network Dynamics

In this paper we initiate the generalization of the Adversarial Queueing Theory (aqt) model to capture the dynamics of continuous scenarios in which the usually assumed synchronicity of the evolution is not required anymore. We propose an asynchronous model, named continuous aqt (caqt), in which packets can have arbitrary lengths, and the network links may have different speeds (or bandwidths) and propagation delays. With respect to the standard aqt model, these new features turn out to be significant for the stability of packet scheduling policies that take them into account, but not so much for the stability of networks. From the network point of view, we show that networks with directed acyclic topologies are universally stable, i.e., stable independently of the scheduling policies and traffic patterns used in it. Interestingly enough, this even holds for traffic patterns that make links to be fully loaded. Finally, it turns out that the set of universally stable networks remains the same as in the aqt model and, therefore, the property of universal stability of networks is decidable in polynomial time. Concerning packet scheduling policies, we show that the well-known lis, sis, ftgand nfsscheduling policies remain universally stable in the caqt model. We introduce other scheduling policies that, although being universally stable in the aqt model, they are unstable under the caqt model. This work was partially supported by eu IST-2004-15964 (aeolus), by the Spanish Ministry of Education and Science under cicyt tin2005-09198 (asce) and cicyt tin2005-25859-E, by the Regional Government of Madrid under contract No. 07T/0022/2003, and by the Universidad Rey Juan Carlos under project No. PPR-2004-42. Also partially supported by the Universidad de Chile (Mecesup fellowship and Anillo en Redes). A preliminary version of this work was presented in the 30th International Symposium on Mathematical Foundations of Computer Science (mfcs), Gdansk, Poland, LNCS, vol. 3618, pp. 144–155, Springer.     

Performance and stability bounds for dynamic networks

In this work, we study the impact of dynamically changing link capacities on the delay bounds of LIS (Longest-In-System) and SIS (Shortest-In-System) protocols on specific networks (that can be modelled as Directed Acyclic Graphs (DAGs)) and stability bounds of greedy contention–resolution protocols running on arbitrary networks under the Adversarial Queueing Theory. Especially, we consider the model of dynamic capacities  , where each link capacity may take on integer values from [1,C]$[1,C]$ with C>1$C>1$, under a (w,ρ)$(w,\rho )$-adversary. We show that the packet delay on DAGs for LIS is upper bounded by O(iwρC)$O(\mathit{iw}\rho C)$ and lower bounded by Ω(iwρC)$\Omega (\mathit{iw}\rho C)$ where i   is the level of a node in a DAG (the length of the longest path leading to node v$v$ when nodes are ordered by the topological order induced by the graph). In a similar way, we show that the performance of SIS on DAGs is lower bounded by Ω(iwρC)$\Omega (\mathit{iw}\rho C)$, while the existence of a polynomial upper bound for packet delay on DAGs when SIS is used for contention–resolution remains an open problem. We prove that every queueing network running a greedy contention–resolution protocol is stable for a rate not exceeding a particular stability threshold, depending on C and the length of the longest path in the network.     

Stability bounds in networks with dynamic link capacities

We address the problem of stability in networks where the link capacities can change dynamically. We show that every network running a greedy scheduling policy is universally stable at any injection rate r<1/(Cd), where d is the largest number of links crossed by any packet and C is the maximum link capacity. We also show that system-wide time priority scheduling policies are universally stable at any injection rate r<1/(C(d−1)).     

Fault-tolerant adaptive routing under an unconstrained set of node and link failures for many-core systems-on-chip

An online fault tolerant routing algorithm for 2D mesh Networks-on-Chip is presented in this work. It combines an adaptive routing algorithm with neighbor fault-awareness and a new traffic-balancing metric. To be able to cope with runtime permanent and temporary failures that may result in message corruption, message loss or deadlocks, the routing algorithm is enhanced with packet retransmission and a new message recovery scheme.     

Intrinsic robustness of global asymptotic stability

Equivalence is shown for discrete time systems between global asymptotic stability and the so-called integral Input-to-State Stability. The latter is a notion of robust stability with respect to exogenous disturbances which informally translates into the statement “no matter what is the initial condition, if the energy of the inputs is small, then the state must eventually be small”.     

An analysis of stability with time-delay of link level power control in optical networks

We study the effects of time-delay on the stability of optical networks. A link level power control scheme adjusts the OSNR value of the signals toward channel OSNR optimization. We utilize the OSNR model from [Pavel, L. (2006). A noncooperative game approach to OSNR optimization in optical networks. IEEE Transactions on Automatic Control, 51(5), 848-852] along with its game-theoretic based control algorithm. Time-delay is incorporated into the closed loop system, for the general network case where every link has a unique time-delay. We derive sufficient conditions for stability under arbitrary time-delays and network configurations. The results are verified via extensive simulations.     

The advanced-step NMPC controller: Optimality, stability and robustness

Widespread application of dynamic optimization with fast optimization solvers leads to increased consideration of first-principles models for nonlinear model predictive control (NMPC). However, significant barriers to this optimization-based control strategy are feedback delays and consequent loss of performance and stability due to on-line computation. To overcome these barriers, recently proposed NMPC controllers based on nonlinear programming (NLP) sensitivity have reduced on-line computational costs and can lead to significantly improved performance. In this study, we extend this concept through a simple reformulation of the NMPC problem and propose the advanced-step NMPC controller. The main result of this extension is that the proposed controller enjoys the same nominal stability properties of the conventional NMPC controller without computational delay. In addition, we establish further robustness properties in a straightforward manner through input-to-state stability concepts. A case study example is presented to demonstrate the concepts.     

具有失效节点和链路的E-2DＭesh网络可靠性研究*

对E-2DMesh网络中节点和链路失效模式进行了研究,构造了一种多级事件状态分解法,对网络状态空间进行分解。基于该方法和组合模型原理研究了在给定节点和链路失效概率均为0.10%以下时,对多达上千个节点的E-2DMesh网络仍可达超过0911 9的可靠度。该方法能够应用于研究其他层次结构的网络与其他网络通信问题,也很适合近似计算。     

Fast reroute from single link and single node failures for IP multicast

The rise in multicast implementations has seen with it an increased support for fast failure recovery from link and node failures. Most recovery mechanisms augment additional services to existing protocols causing excessive overhead, and these modifications are predominantly protocol-specific. In this paper, we develop a multicast failure recovery mechanism that constructs protocol independent fast reroute paths to recover from single link and single node failures. We observe that single link failure recovery in multicast networks is similar to recovering unicast traffic, and we use existing unicast recovery mechanisms for multicast traffic. We construct multicast protection trees that provide instantaneous failure recovery from single node failures. For a given node x, the multicast protection tree spans all its neighbors and does not include itself. Thus, when the node fails, the neighbors of the node are connected through the multicast protection tree instead of node x, and forward the traffic over the multicast protection tree for the duration of failure recovery. The multicast protection trees are constructed a priori, without the knowledge of the multicast traffic in the network. Based on simulations on three realistic network topologies, we observe that the multicast protection trees increase the routing table size only by 38% on average and the path length between any source–destination pair by 13% on average.     

Analysis of the local robustness of stability for flows

In this paper the problem of measuring the robustness of stability for a perturbed continuous-time nonlinear system at a singular fixed point is studied. Various stability radii are introduced and their values for the nonlinear system and its linearization are compared. It is shown that they generically coincide. This result may also be used to show generic continuity of linear real stability radii. Some examples are presented showing that it is sometimes necessary to consider the nonlinear system directly, and not simply to rely on the information provided by the linearization.     

Sensitivity results in open, closed and mixed product form queueing networks

General formulas are proposed to quantify the effects of changing the model parameters in the so-called BCMP network [F. Baskett et al., J. ACM 22 (2) (April 1975) 248–260]. These formulas relate the derivative of the expectation of any function of both the state and the paramaters of the network with respect to any model parameter (i.e., arrival rate, mean service demand, service rate, visit ratio, traffic intensity) to known functions of the state variables. Applications of our results to sensitivity analysis and optimization problems are given.     

Complete stability robustness of third-order LTI multiple time-delay systems

A unique procedure is presented in this paper, for a complete stability robustness of the third-order LTI multiple time-delay systems (LTI-MTDS). The uniqueness of the treatment is simply due to the fact that there is no comparable methodology, presently, in the literature. The end result of this procedure is an exhaustive and precise determination of the stable regions in the domain of time delays. The backbone of the method is a novel framework called “the cluster treatment of characteristic roots, (CTCR)”. CTCR is constructed over two fundamental propositions. The first proposition claims the existence of a bounded number of so-called “kernel curves”, where the only imaginary characteristic roots occur. The second proposition is on an interesting directional invariance property of the crossing tendencies of these imaginary roots. For simplicity of conveyance and without loss of generality, the number of time delays is taken as two in this document. The new methodology is expandable to higher-order dynamics with more time delays than two, as the authors intend to demonstrate in future publications.     

The stability robustness determination of state space models with real unstructured perturbations

This paper considers the robust stability of a linear time-invariant state space model subject to real parameter perturbations. The problem is to find the distance of a given stable matrix from the set of unstable matrices. A new method, based on the properties of the Kronecker sum and two other composite matrices, is developed to study this problem; this new method makes it possible to distinguish real perturbations from complex ones. Although a procedure to find the exact value of the distance is still not available, some explicit lower bounds on the distance are obtained. The bounds are applicable only for the case of real plant perturbations, and are easy to compute numerically; if the matrix is large in size, an iterative procedure is given to compute the bounds. Various examples including a 46th-order spacecraft system are given to illustrate the results obtained. The examples show that the new bounds obtained can have an arbitrary degree of improvement over previously reported ones. This work has been supported by the Natural Sciences and Engineering Research Council of Canada under Grant No. A4396.     

Multiple link failures survivability of optical networks with traffic grooming capability

This paper investigates the problem of survivable traffic grooming (STG) in shared mesh optical networks and proposes different frameworks for improving the survivability of low speed demands against multiple near simultaneous failures. Spare capacity reprovisioning has recently been considered for improving the overall network restorability in the event of dual failures; here, after the recovery form the first failure, some connections in the network may become unprotected and exposed to new failures. Capacity reprovisioning then allocates protection resources to unprotected and vulnerable connections so that the network can withstand a future failure. In this paper, we propose two different reprovisioning schemes (lightpath level reprovisioning, LLR, and connection level reprovisioning, CLR); they differ in the granularity at which protection resources are reprovisioned. Further, each of these schemes is suitable for a different survivable grooming policy. While LLR provides collective reprovisioning of connections at the lightpath level, CLR reprovisions spare bandwidth for lower speed connections instead. We use simulation methods to study the performance of these schemes under two grooming policies (PAL and PAC), and we show that while CLR reprovisions substantially many more connections than LLR (i.e., potentially more management overhead) CLR yields a much better network robustness to simultaneous failures due to its superior flexibility in using network resources.     

Lea-TN: leader election algorithm considering node and link failures in a torus network

The Journal of Supercomputing - Torus network topology offers many advantages such as higher speed, lower latency, better fairness, and lower energy consumption. For these kinds of benefits,...     

Design of fuzzy controllers for uncertain nonlinear systems using stability and robustness analyses

This paper analyzes the stability and robustness of uncertain nonlinear systems and shows that the analysis results provide an efficient technique for the design of fuzzy controllers. Based on a fuzzy plant model describing an uncertain nonlinear plant, this design involves the derivation of a stability criterion and a robust area in the uncertain parameter space in terms of some measures of the closed-loop control system matrices. An application example on balancing an inverted pendulum is given to illustrate the simple design methodology, the stability and the robustness of the feedback system incorporated with the proposed fuzzy controller.     

Unequal error protection under bitrate constraint for video streaming over internet

This article describes a simple packet-level FEC system suitable for unequal error protection of layered video streams, that we called TAPIOCA (in French, Transport Audiovisuel avec Protection Inégale des Objets et Contrôle d’Admission). It is designed in a way that the FEC overhead induced by redundant packets is perfectly controlled by the sender. In order to achieve that, TAPIOCA calculates on-the-fly the optimal erasure code to be used, video data unit by video data unit, under a given bitrate constraint. In addition, and contrary to the well-known PET (Priority Encoding Transmission) system, the video data units of each layer are encoded separately. This is especially useful when all layers are not output from the video coder at the same time. Simulation results for MPEG-4 video streaming show that the proposed FEC system can be very efficient even if packet losses are due to network congestion. Moreover, comparison with PET system shows that TAPIOCA exhibits better performance, considering criteria including the decodable frame rate, protection system efficiency and computational cost.     

Attraction, stability and robustness for stochastic functional differential equations with infinite delay

This paper establishes the stochastic LaSalle theorem to locate limit sets for stochastic functional differential equations with infinite delay, from which some criteria on attraction, boundedness, stability and robustness are obtained. To illustrate the applications of our results clearly, this paper considers a scalar stochastic integro-differential equation with infinite delay as an example.