# A Decentralized Routing Control Scheme for Data Communication Networks

Authors: Xueming Si; Xun-Lin Zhu; Xin Du; Xiangpeng Xie
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

This paper studies the decentralized routing control of data communication networks. Taking the physical constraints on the data flow and the network-induced delays into consideration, the decentralized routing control problem is reformulated as a constrained control problem, and the restriction of initial message lengths is no longer needed. By defining a general Lyapunov functional and applying a reciprocally convex combination technique to deal with the network-induced delays, less conservative and less complex designing conditions are obtained in terms of linear matrix inequalities (LMIs). A simulation example is also given to illustrate the effectiveness of the proposed designing scheme.


---

## Body

## 1. Introduction

Routing control plays an indispensable role in complex and crowded networks such as transportation networks and data communication networks [1–19]. The fundamental idea of routing control is that the most suitable route for data packets from source to destination through other nodes is to be determined such that certain objective functions are minimized.Early routing algorithms, such as those implemented in the ARPANET [2] and TYMNET [3], were designed for optimally achieving some prespecified objective, such as shortest time or shortest path from the initial node to the destination node, minimization of a cost function related to the link congestion [14], or minimization of a generic measure of link flows. However, the performance of the crowded networks with these routing algorithms will deteriorate significantly, since the channel communication capacity is usually limited and the link congestion problems may often occur in many practical networks [20]. Therefore, it is essential to take the physical constraints, such as limited channel capacity and limited energy source, into consideration in designing proper routing control scheme.It is very known that the network-induced delays (i.e., transmission delay, propagation delay, and processing delay) may induce instability, oscillation, and poor performance, and have a major impact on the routing control design. Several researchers have also attempted to address the problem of delay-constrained routing in recent years [13–19, 21–24]. Different techniques such as capacity allocation [16] and neural networks [19] are adopted to obtain the proper routing paths that minimizing or guaranteeing the boundedness of different types of network delays. However, more general index may be specified in evaluating the network performance, and many physical constraints of networks also should be taken into consideration. Under such a circumstances, the routing control problem becomes a difficult task and cannot be tackled with the above-mentioned methods. As stated in [18, 19], the fluid flow conservation principle is frequently employed in deriving the queuing dynamics, wherein each state of the subsystem (node) represents a queue corresponding to a given destination node. With the aid of linear matrix inequality (LMI) approach, the recent paper [20] provides a promising framework to revisit and reformulate the routing control problems as a constrained H∞ optimal control problem for time-delay systems; hence, a number of physical constraints can be easily imposed on the routing problem.In [20], a continuous-time system model was used to describe the dynamics of traffic networks, and the physical constraints on traffic flows and queues were transformed into a set of LMI-based conditions. Then, robust centralized as well as decentralized routing control strategies were introduced for networks with a fixed topology based on the minimisation of the worst-case queuing length, which is related to the queuing delays. Similar treatment was adopted in [25]. It is worth pointing out that the derivatives of network-induced delays were assumed to be less than 1. However, according to [26], such assumptions are false. Meanwhile, a parameter should be given a priority and the initial values of all message queue lengths are required to be 0 in the transformation of the physical constraints, which may be harsh for many practical applications and may result in some conservatism.In this paper, we study routing control of data communication networks that arise from many practical applications [19]. A discrete-time model instead of continuous-time model [20] is used to describe the communication network dynamics and the data constraints on the data flow. Furthermore, in order to facilitate the practical implementation for large-scale data communication networks, we are dedicated to design decentralized controllers instead of centralized controllers. Thus, vulnerable failures and large communication overheads in the network may be avoided. To this end, some new techniques will be adopted to tackle the extra difficulty in the related LMI manipulation and derivation, which are caused because of the decentralized controller structure. Different from the existing works, a reciprocally convex combination method is used to deal with delays, the physical constraints are successfully transformed into a set of LMIs and the restriction that initial message queue lengths should be 0 is removed, and each LMI-based condition involved in the designing of decentralized routing control is only related to an oriented link in the data communication network, which can effectively reduce both the conservatism and the complexity.Notation.
Throughout this paper, a real symmetric matrixP>0 (≥0) denotes P being a positive definite (positive semidefinite) matrix, and A>B(A≥B) means A-B>0 (≥0). I is used to denote an identity matrix with proper dimension. Matrices, if not explicitly stated, are assumed to have compatible dimensions. The symmetric terms in a symmetric matrix are denoted by *. For a real vector x∈Rn, x≽0 (≻0) denotes every component of x being nonnegative (positive). In this case, x is called nonnegative (positive). Likewise, A∈Rn×m is nonnegative or positive if every entry of A is nonnegative or positive, respectively, which is written as A≽0 or A≻0, respectively.


## 2. Problem Formulation

Consider a data communication network,𝒢=(𝒩,ℒ), consisting of a directed graph with a set 𝒩 of N nodes and a set ℒ of L-oriented links. Each message has a destination node d∈𝒩, and all destination nodes form a set 𝒩d. Each node i∈𝒩 receives messages from the upstream nodes within the network. Messages are absorbed as soon as they arrive at their destination nodes. Messages arriving to a node other than their final destination are put into a queue (or buffer) and eventually are sent out to a downstream node. It is assumed that the network is “connected,” that is, each node of the network must be reachable from each other node. In the worst case, where all the nodes are source as well as destination, at each node i∈𝒩 there will be n-1 queues in which messages are stored for all destinations, 1,2,…,i-1,i+1,…,N. We also assume that the rate of messages that are sent from one node to another is updated (synchronously throughout the communication network) by control variables at discrete instants kT(k=0,1,2,…), where T is a positive scalar.Similar to [19], the data communication network dynamics can be expressed as
(1)qid(k+1)=qid(k)+∑j≠dj∈𝒫(i)‍fjid(k-τji(k))-∑j∈𝒮(i)‍fijd(k),i∈𝒩,d∈𝒩di,
where qid(k): message queue length at node i destined to node d at instant kT;𝒫(i): set of upstream neighbors of node i; 𝒮(i): set of downstream neighbors of node i; fijd(k): traffic flow routed from node i to node j destined to node d at instant kT; 𝒩di: subset of 𝒩d, that is, 𝒩di=𝒩d∖{i}; τij(k): time-varying delay in transmitting, propagating, and processing of messages (including identifying the destination, inserting in the queue, and routing computation) with destination d routed from node i to node j, which satisfies
(2)0≤τij(k)≤τij,∀(i,j)∈ℒ,
where τij are constants.Due to the physical significance offijd and the constraints on the data flow through each link and the message queue buffer size at each node, the following conditions should be satisfied:
(3)fijd(k)≥0,i∈𝒩,j∈𝒮(i),d∈𝒩di,(4)0≤∑d∈𝒩di‍qid(k)≤qi,i∈𝒩,(5)∑d∈𝒩di‍fijd(k)≤cij,i∈𝒩,j∈𝒮(i),
where positive scalars qi and cij represent the maximal length of the message queue length at node i and the maximal capacity of oriented link (i,j) (it is also called “edge”), respectively.Define(6)xi(k)=vec{qid(k)},ui(k)=vec{fijd(k)},(i∈𝒩,j∈𝒮(i),d∈𝒩di),
then (1) can be rewritten as
(7)xi(k+1)=xi(k)+Biui(k)+∑j∈𝒫(i)‍Bdjiuj(k-τji(k)),
where xi(k)∈RNdi and ui(k)∈RmiNdi are vectors; mi,Nd, and Ndi represent the numbers of nodes contained in 𝒮(i),𝒩d, and 𝒩di, respectively; Bi and Bdji are constant matrices. Obviously, the entries of Bi are equal to 0 or -1, and the ones of Bdji are equal to 0 or 1, which reflect the network connectivity of node i in graph 𝒢 [20].In this paper, a decentralized routing control scheme(8)ui(k)=Kixi(k),i∈𝒩,
is proposed to stabilize the origin system (1), where state feedback controllers Ki(i∈𝒩) are to be designed. Such a constrained control problem can be found by solving a set of linear matrix inequalities (LMIs). Different from the one given in [20], the obtained routing control scheme is at edge-level; that is, each inequality is only dependent on an edge (i,j) in ℒ. This implies that the dimension of each inequality is low, so the computational complexity is reduced effectively. In addition, since some constraints are discarded, the conservatism of the obtained LMI-based conditions is also reduced.Through this paper, Jensen's integral inequality [27] and a reciprocally convex combination technique [28] will be used, so it is listed as the following lemmas.Lemma 1 (see [27]).
For any positive symmetric constant matrixM∈Rn×n, scalars r1,r2 satisfying r1<r2, a vector function ω:[r1,r2]→Rn such that the integrations concerned are well defined, then
(9)(∫r1r2‍ω(s)ds)TM(∫r1r2‍ω(s)ds)≤(r2-r1)∫r1r2‍ωT(s)Mω(s)ds.Lemma 2 (see [29]).
For given positive semidefinite matricesZ1 and Z2, if there exists a matrix T such that
(10)[Z1T*Z2]≥0,
then the following inequality for any α(0<α<1) holds
(11)[1αZ10*11-αZ2]≥[Z1T*Z2].


## 3. Main Results

### 3.1. Stability Analysis

Now, we give a new stability criterion for the origin of system (7) with (2) as follows.Theorem 3.
For given scalarsτij>0 and Ki(i∈𝒩,j∈𝒮(i)), the origin of system (7) with (2) is globally asymptotically stable if there exist matrices Pij=PijT>0, Qij=QijT≥0, Rij=RijT≥0, Zij=ZijT>0, and Uij=UijT>0  (∀i∈𝒩,j∈𝒮(i)) with appropriate dimensions, such that
(12)[ZijTij*Zij]≥0,(13)[ΦijΘij*-Uij]<0,
where i=1,2,…,n and j∈𝒮(i), and
(14)Φij=[Φij111τij(Zij-Tij)1τijTijΦij14*Φij221τij(Zij-Tij)0**-Rij-1τijZij0***Φij44],Φij11=τijQij+Rij-1τijZij-1mi(Mi1BiKi+KiTBiTMi1T-Mi1(∑l∈𝒫(i)‍Uli)Mi1T),Φij14=Pij+1mi(Mi1-KiTBiTMi2T+Mi1(∑l∈𝒫(i)‍Uli)Mi2T),Φij22=-Qij-1τij(2Zij-Tij-TijT),Φij44=Pij+τijZij+1mi(Mi2+Mi2T+Mi2(∑l∈𝒫(i)‍Uli)Mi2T),Θij=[0BdijKi00]T.Proof.
The proof is provided in the Appendix.Remark 4.
In Theorem3, a sufficient condition of globally asymptotical stability for the origin of system (7) with (2) is given in terms of LMIs. Different from the one in [20], positive definite matrices Pij,Qij,Rij, and Zij correspond to the oriented link (i,j), so the Lyapunov functional (A.1) is more general. Meanwhile, each inequality in (13) is also related to an oriented link (i,j) in ℒ, so its dimension is lower. Combined with using a reciprocally convex technique [28], the computational complexity and the conservatism are reduced.


### 3.2. A Decentralized Routing Control Scheme

#### 3.2.1. Controller Design without the Physical Constraints

From (13), one can find that Mi2+Mi2T(i=1,2,…,n) are negative definite, this implies that Mi2 are nonsingular. Set
(15)Mi1=ɛiMi2,Mi2¯=Mi2-1,P¯ij=Mi2¯PijMi2¯T,Q¯ij=Mi2¯QijMi2¯T,R¯ij=Mi2¯RijMi2¯T,Z¯ij=Mi2¯ZijMi2¯T,T¯ij=Mi2¯TijMi2¯T,Fi=KiMi2¯T,
pre- and postmultiplying the left side of inequality (13) by diag{M¯i2,M¯i2,M¯i2,M¯i2,I} and its transpose, and from the Schur complement, we get the following.Theorem 5.
For given scalarsτij>0 and ɛi(i∈𝒩,j∈𝒮(i)), the origin of system (7) with (2) is globally asymptotically stable if there exist matrices P¯ij=P¯ijT>0, Q¯ij=Q¯ijT≥0, R¯ij=R¯ijT≥0, and Z¯ij=Z¯ijT>0, Fi and M¯i2(foralli∈𝒩,j∈𝒮(i)) with appropriate dimensions, such that
(16)[Z¯ijT¯ij*Z¯ij]≥0,(17)[ΩijΓij*-Uij]<0,
where i∈𝒩 and j∈𝒮(i), and
(18)Ωij=[Ωij111τij(Z¯ij-T¯ij)1τijT¯ijΩij14*Ωij221τij(Z¯ij-T¯ij)0**-R¯ij-1τijZ¯ij0***Ωij44],Γij=[0BdijFi00]T,Ωij11=τijQ¯ij+R¯ij-1τijZ¯ijΩij11=-1miɛi(BiFi+FiTBiT-ɛi∑l∈𝒫(i)‍Uli),Ωij14=P¯ij+1mi(M¯i2T-FiTBiT+∑l∈𝒫(i)‍Uli),Ωij22=-Q¯ij-1τij(2Z¯ij-T¯ij-T¯ijT),Ωij44=P¯ij+τijZ¯ij+1mi(M¯i2T+M¯i2+∑l∈𝒫(i)‍Uli).
The gains Ki(i∈𝒩) of the subsystem controllers in (8) are given by
(19)Ki=FiM¯i2-T.


#### 3.2.2. LMI-Based Conditions for the Physical Constraints

Now, we translate the physical constraints (3)–(5) into LMI-based conditions.(1)Nonnegativity Constraint on Data Traffic Flow. From (1), it is easy to see that the nonnegativity of xi(k) and fijd(k) can be guaranteed if I+BiKi and Ki are nonnegative for all i∈𝒩,j∈𝒮(i), and d∈𝒩di.Note that the negative definiteness ofM¯i2+M¯i2T, and from (17), the nonnegativity of I+BiKi and Ki can be guaranteed if M¯i2 are diagonal for all i∈𝒩 and
(20)M¯i2+BiFi⪯0,Fi⪯0.
(2)Upper Bound on the Buffer Size. Note that
(21)∑d∈𝒩di‍qid(k)=Hixi(k),
where
(22)Hi=[1⋯1︸Ndi].
So, the constraint (4) can be represented as
(23)0≤Hixi(k)≤qi.FromΩij<0, it follows that  Ωij44<0. So, there exist a small enough λ>0 such that
(24)P¯ij+1mi(M¯i2T+M¯i2+λI)<0.
Since
(25)-1λM¯i2M¯i2T≤M¯i2T+M¯i2+λI,
and P¯ij=M¯i2PijM¯i2T, inequality (24) implies
(26)∑j∈𝒮(i)‍Pij<1λI.
If (16) and (17) in Theorem 5 are feasible, under the assumption xi(τ)=0for all τ∈{-1,-2,…,-τij}, from
(27)xiT(k)(∑j∈𝒮(i)‍Pij)xi(k)≤∑i=1N‍xiT(k)(∑j∈𝒮(i)‍Pij)xi(k)≤V(k),V(0)≤1λ∑i=1N‍xiT(0)xi(0)≤1λ∑i=1N‍xiT(0)HiTHixi(0)≤1λ∑i=1N‍qi2,
we get
(28)xiT(k)(∑j∈𝒮(i)‍Pij)xi(k)≤1λ∑i=1N‍qi2,
where V(k) is defined in (A.1).Thus, (23) can be guaranteed if
(29)1miqi2HiTHi≤λ∑i=1Nqi2Pij,∀j∈𝒮(i).
From the Schur complement, the above inequality is equivalent to
(30)[-P¯ijM¯i2HiT*-miqi2∑i=1Nqi2λ]<0.
So, from the above analysis, it is known that (23) can be guaranteed if (24) and (30) hold for any (i,j)∈ℒ.(3)Capacity Constraints on Links. For j∈𝒮(i), it is known that there exists a nonnegative integer ij such that the numbers of ij nodes contained in 𝒮(i) are less than j and the ones of mi-ij-1 nodes contained in 𝒮(i) are greater than j. Thus, We get
(31)∑d∈𝒩di‍fijd(k)=Gijui(k),∀(i,j)∈ℒ,
where
(32)Gij=[0⋯0︸ij×Ndi1⋯1︸Ndi0⋯0︸(mi-ij-1)×Ndi].
so the constraint (5) can be represented as
(33)0≤Gijui(k)≤cij.Similarly, constraint (33) can be satisfied if (24) and
(34)[-P¯ijFiTGijT*-cij2∑i=1Nqi2λ]<0.Therefore, considering the physical constraints (3)–(5), a decentralized routing control scheme can be get as follows.Theorem 6.
For given scalarsτij>0 and ɛi(i∈𝒩,j∈𝒮(i)), the origin of system (7) with (2) is globally asymptotically stable if there exist a scalar λ>0, matrices P¯ij=P¯ijT>0, Q¯ij=Q¯ijT≥0, R¯ij=R¯ijT≥0, and Z¯ij=Z¯ijT>0, Fi and diagonal matrices M¯i2(foralli∈𝒩,j∈𝒮(i)) with appropriate dimensions, such that (16), (17), (20), (24), (30), and (34) hold.Correspondingly, the gainsKi of the subsystem controllers in (8) are given by (19).Remark 7.
In [20, 25], a scalar λ was needed to be selected before and the restriction V(0)=0 in transforming the physical constraints into LMI-based conditions. Contrastively, λ involved in inequalities (30) and (34) is a variable and it can be found by solving these LMIs. More importantly, the restriction V(0)=0 is not needed here.Remark 8.
Different from [20, 25], positive definite matrix P¯ in Theorem 6 is not required to be diagonal, which discards the constraint on P.


## 3.1. Stability Analysis

Now, we give a new stability criterion for the origin of system (7) with (2) as follows.Theorem 3.
For given scalarsτij>0 and Ki(i∈𝒩,j∈𝒮(i)), the origin of system (7) with (2) is globally asymptotically stable if there exist matrices Pij=PijT>0, Qij=QijT≥0, Rij=RijT≥0, Zij=ZijT>0, and Uij=UijT>0  (∀i∈𝒩,j∈𝒮(i)) with appropriate dimensions, such that
(12)[ZijTij*Zij]≥0,(13)[ΦijΘij*-Uij]<0,
where i=1,2,…,n and j∈𝒮(i), and
(14)Φij=[Φij111τij(Zij-Tij)1τijTijΦij14*Φij221τij(Zij-Tij)0**-Rij-1τijZij0***Φij44],Φij11=τijQij+Rij-1τijZij-1mi(Mi1BiKi+KiTBiTMi1T-Mi1(∑l∈𝒫(i)‍Uli)Mi1T),Φij14=Pij+1mi(Mi1-KiTBiTMi2T+Mi1(∑l∈𝒫(i)‍Uli)Mi2T),Φij22=-Qij-1τij(2Zij-Tij-TijT),Φij44=Pij+τijZij+1mi(Mi2+Mi2T+Mi2(∑l∈𝒫(i)‍Uli)Mi2T),Θij=[0BdijKi00]T.Proof.
The proof is provided in the Appendix.Remark 4.
In Theorem3, a sufficient condition of globally asymptotical stability for the origin of system (7) with (2) is given in terms of LMIs. Different from the one in [20], positive definite matrices Pij,Qij,Rij, and Zij correspond to the oriented link (i,j), so the Lyapunov functional (A.1) is more general. Meanwhile, each inequality in (13) is also related to an oriented link (i,j) in ℒ, so its dimension is lower. Combined with using a reciprocally convex technique [28], the computational complexity and the conservatism are reduced.


## 3.2. A Decentralized Routing Control Scheme

### 3.2.1. Controller Design without the Physical Constraints

From (13), one can find that Mi2+Mi2T(i=1,2,…,n) are negative definite, this implies that Mi2 are nonsingular. Set
(15)Mi1=ɛiMi2,Mi2¯=Mi2-1,P¯ij=Mi2¯PijMi2¯T,Q¯ij=Mi2¯QijMi2¯T,R¯ij=Mi2¯RijMi2¯T,Z¯ij=Mi2¯ZijMi2¯T,T¯ij=Mi2¯TijMi2¯T,Fi=KiMi2¯T,
pre- and postmultiplying the left side of inequality (13) by diag{M¯i2,M¯i2,M¯i2,M¯i2,I} and its transpose, and from the Schur complement, we get the following.Theorem 5.
For given scalarsτij>0 and ɛi(i∈𝒩,j∈𝒮(i)), the origin of system (7) with (2) is globally asymptotically stable if there exist matrices P¯ij=P¯ijT>0, Q¯ij=Q¯ijT≥0, R¯ij=R¯ijT≥0, and Z¯ij=Z¯ijT>0, Fi and M¯i2(foralli∈𝒩,j∈𝒮(i)) with appropriate dimensions, such that
(16)[Z¯ijT¯ij*Z¯ij]≥0,(17)[ΩijΓij*-Uij]<0,
where i∈𝒩 and j∈𝒮(i), and
(18)Ωij=[Ωij111τij(Z¯ij-T¯ij)1τijT¯ijΩij14*Ωij221τij(Z¯ij-T¯ij)0**-R¯ij-1τijZ¯ij0***Ωij44],Γij=[0BdijFi00]T,Ωij11=τijQ¯ij+R¯ij-1τijZ¯ijΩij11=-1miɛi(BiFi+FiTBiT-ɛi∑l∈𝒫(i)‍Uli),Ωij14=P¯ij+1mi(M¯i2T-FiTBiT+∑l∈𝒫(i)‍Uli),Ωij22=-Q¯ij-1τij(2Z¯ij-T¯ij-T¯ijT),Ωij44=P¯ij+τijZ¯ij+1mi(M¯i2T+M¯i2+∑l∈𝒫(i)‍Uli).
The gains Ki(i∈𝒩) of the subsystem controllers in (8) are given by
(19)Ki=FiM¯i2-T.


### 3.2.2. LMI-Based Conditions for the Physical Constraints

Now, we translate the physical constraints (3)–(5) into LMI-based conditions.(1)Nonnegativity Constraint on Data Traffic Flow. From (1), it is easy to see that the nonnegativity of xi(k) and fijd(k) can be guaranteed if I+BiKi and Ki are nonnegative for all i∈𝒩,j∈𝒮(i), and d∈𝒩di.Note that the negative definiteness ofM¯i2+M¯i2T, and from (17), the nonnegativity of I+BiKi and Ki can be guaranteed if M¯i2 are diagonal for all i∈𝒩 and
(20)M¯i2+BiFi⪯0,Fi⪯0.
(2)Upper Bound on the Buffer Size. Note that
(21)∑d∈𝒩di‍qid(k)=Hixi(k),
where
(22)Hi=[1⋯1︸Ndi].
So, the constraint (4) can be represented as
(23)0≤Hixi(k)≤qi.FromΩij<0, it follows that  Ωij44<0. So, there exist a small enough λ>0 such that
(24)P¯ij+1mi(M¯i2T+M¯i2+λI)<0.
Since
(25)-1λM¯i2M¯i2T≤M¯i2T+M¯i2+λI,
and P¯ij=M¯i2PijM¯i2T, inequality (24) implies
(26)∑j∈𝒮(i)‍Pij<1λI.
If (16) and (17) in Theorem 5 are feasible, under the assumption xi(τ)=0for all τ∈{-1,-2,…,-τij}, from
(27)xiT(k)(∑j∈𝒮(i)‍Pij)xi(k)≤∑i=1N‍xiT(k)(∑j∈𝒮(i)‍Pij)xi(k)≤V(k),V(0)≤1λ∑i=1N‍xiT(0)xi(0)≤1λ∑i=1N‍xiT(0)HiTHixi(0)≤1λ∑i=1N‍qi2,
we get
(28)xiT(k)(∑j∈𝒮(i)‍Pij)xi(k)≤1λ∑i=1N‍qi2,
where V(k) is defined in (A.1).Thus, (23) can be guaranteed if
(29)1miqi2HiTHi≤λ∑i=1Nqi2Pij,∀j∈𝒮(i).
From the Schur complement, the above inequality is equivalent to
(30)[-P¯ijM¯i2HiT*-miqi2∑i=1Nqi2λ]<0.
So, from the above analysis, it is known that (23) can be guaranteed if (24) and (30) hold for any (i,j)∈ℒ.(3)Capacity Constraints on Links. For j∈𝒮(i), it is known that there exists a nonnegative integer ij such that the numbers of ij nodes contained in 𝒮(i) are less than j and the ones of mi-ij-1 nodes contained in 𝒮(i) are greater than j. Thus, We get
(31)∑d∈𝒩di‍fijd(k)=Gijui(k),∀(i,j)∈ℒ,
where
(32)Gij=[0⋯0︸ij×Ndi1⋯1︸Ndi0⋯0︸(mi-ij-1)×Ndi].
so the constraint (5) can be represented as
(33)0≤Gijui(k)≤cij.Similarly, constraint (33) can be satisfied if (24) and
(34)[-P¯ijFiTGijT*-cij2∑i=1Nqi2λ]<0.Therefore, considering the physical constraints (3)–(5), a decentralized routing control scheme can be get as follows.Theorem 6.
For given scalarsτij>0 and ɛi(i∈𝒩,j∈𝒮(i)), the origin of system (7) with (2) is globally asymptotically stable if there exist a scalar λ>0, matrices P¯ij=P¯ijT>0, Q¯ij=Q¯ijT≥0, R¯ij=R¯ijT≥0, and Z¯ij=Z¯ijT>0, Fi and diagonal matrices M¯i2(foralli∈𝒩,j∈𝒮(i)) with appropriate dimensions, such that (16), (17), (20), (24), (30), and (34) hold.Correspondingly, the gainsKi of the subsystem controllers in (8) are given by (19).Remark 7.
In [20, 25], a scalar λ was needed to be selected before and the restriction V(0)=0 in transforming the physical constraints into LMI-based conditions. Contrastively, λ involved in inequalities (30) and (34) is a variable and it can be found by solving these LMIs. More importantly, the restriction V(0)=0 is not needed here.Remark 8.
Different from [20, 25], positive definite matrix P¯ in Theorem 6 is not required to be diagonal, which discards the constraint on P.


## 3.2.1. Controller Design without the Physical Constraints

From (13), one can find that Mi2+Mi2T(i=1,2,…,n) are negative definite, this implies that Mi2 are nonsingular. Set
(15)Mi1=ɛiMi2,Mi2¯=Mi2-1,P¯ij=Mi2¯PijMi2¯T,Q¯ij=Mi2¯QijMi2¯T,R¯ij=Mi2¯RijMi2¯T,Z¯ij=Mi2¯ZijMi2¯T,T¯ij=Mi2¯TijMi2¯T,Fi=KiMi2¯T,
pre- and postmultiplying the left side of inequality (13) by diag{M¯i2,M¯i2,M¯i2,M¯i2,I} and its transpose, and from the Schur complement, we get the following.Theorem 5.
For given scalarsτij>0 and ɛi(i∈𝒩,j∈𝒮(i)), the origin of system (7) with (2) is globally asymptotically stable if there exist matrices P¯ij=P¯ijT>0, Q¯ij=Q¯ijT≥0, R¯ij=R¯ijT≥0, and Z¯ij=Z¯ijT>0, Fi and M¯i2(foralli∈𝒩,j∈𝒮(i)) with appropriate dimensions, such that
(16)[Z¯ijT¯ij*Z¯ij]≥0,(17)[ΩijΓij*-Uij]<0,
where i∈𝒩 and j∈𝒮(i), and
(18)Ωij=[Ωij111τij(Z¯ij-T¯ij)1τijT¯ijΩij14*Ωij221τij(Z¯ij-T¯ij)0**-R¯ij-1τijZ¯ij0***Ωij44],Γij=[0BdijFi00]T,Ωij11=τijQ¯ij+R¯ij-1τijZ¯ijΩij11=-1miɛi(BiFi+FiTBiT-ɛi∑l∈𝒫(i)‍Uli),Ωij14=P¯ij+1mi(M¯i2T-FiTBiT+∑l∈𝒫(i)‍Uli),Ωij22=-Q¯ij-1τij(2Z¯ij-T¯ij-T¯ijT),Ωij44=P¯ij+τijZ¯ij+1mi(M¯i2T+M¯i2+∑l∈𝒫(i)‍Uli).
The gains Ki(i∈𝒩) of the subsystem controllers in (8) are given by
(19)Ki=FiM¯i2-T.


## 3.2.2. LMI-Based Conditions for the Physical Constraints

Now, we translate the physical constraints (3)–(5) into LMI-based conditions.(1)Nonnegativity Constraint on Data Traffic Flow. From (1), it is easy to see that the nonnegativity of xi(k) and fijd(k) can be guaranteed if I+BiKi and Ki are nonnegative for all i∈𝒩,j∈𝒮(i), and d∈𝒩di.Note that the negative definiteness ofM¯i2+M¯i2T, and from (17), the nonnegativity of I+BiKi and Ki can be guaranteed if M¯i2 are diagonal for all i∈𝒩 and
(20)M¯i2+BiFi⪯0,Fi⪯0.
(2)Upper Bound on the Buffer Size. Note that
(21)∑d∈𝒩di‍qid(k)=Hixi(k),
where
(22)Hi=[1⋯1︸Ndi].
So, the constraint (4) can be represented as
(23)0≤Hixi(k)≤qi.FromΩij<0, it follows that  Ωij44<0. So, there exist a small enough λ>0 such that
(24)P¯ij+1mi(M¯i2T+M¯i2+λI)<0.
Since
(25)-1λM¯i2M¯i2T≤M¯i2T+M¯i2+λI,
and P¯ij=M¯i2PijM¯i2T, inequality (24) implies
(26)∑j∈𝒮(i)‍Pij<1λI.
If (16) and (17) in Theorem 5 are feasible, under the assumption xi(τ)=0for all τ∈{-1,-2,…,-τij}, from
(27)xiT(k)(∑j∈𝒮(i)‍Pij)xi(k)≤∑i=1N‍xiT(k)(∑j∈𝒮(i)‍Pij)xi(k)≤V(k),V(0)≤1λ∑i=1N‍xiT(0)xi(0)≤1λ∑i=1N‍xiT(0)HiTHixi(0)≤1λ∑i=1N‍qi2,
we get
(28)xiT(k)(∑j∈𝒮(i)‍Pij)xi(k)≤1λ∑i=1N‍qi2,
where V(k) is defined in (A.1).Thus, (23) can be guaranteed if
(29)1miqi2HiTHi≤λ∑i=1Nqi2Pij,∀j∈𝒮(i).
From the Schur complement, the above inequality is equivalent to
(30)[-P¯ijM¯i2HiT*-miqi2∑i=1Nqi2λ]<0.
So, from the above analysis, it is known that (23) can be guaranteed if (24) and (30) hold for any (i,j)∈ℒ.(3)Capacity Constraints on Links. For j∈𝒮(i), it is known that there exists a nonnegative integer ij such that the numbers of ij nodes contained in 𝒮(i) are less than j and the ones of mi-ij-1 nodes contained in 𝒮(i) are greater than j. Thus, We get
(31)∑d∈𝒩di‍fijd(k)=Gijui(k),∀(i,j)∈ℒ,
where
(32)Gij=[0⋯0︸ij×Ndi1⋯1︸Ndi0⋯0︸(mi-ij-1)×Ndi].
so the constraint (5) can be represented as
(33)0≤Gijui(k)≤cij.Similarly, constraint (33) can be satisfied if (24) and
(34)[-P¯ijFiTGijT*-cij2∑i=1Nqi2λ]<0.Therefore, considering the physical constraints (3)–(5), a decentralized routing control scheme can be get as follows.Theorem 6.
For given scalarsτij>0 and ɛi(i∈𝒩,j∈𝒮(i)), the origin of system (7) with (2) is globally asymptotically stable if there exist a scalar λ>0, matrices P¯ij=P¯ijT>0, Q¯ij=Q¯ijT≥0, R¯ij=R¯ijT≥0, and Z¯ij=Z¯ijT>0, Fi and diagonal matrices M¯i2(foralli∈𝒩,j∈𝒮(i)) with appropriate dimensions, such that (16), (17), (20), (24), (30), and (34) hold.Correspondingly, the gainsKi of the subsystem controllers in (8) are given by (19).Remark 7.
In [20, 25], a scalar λ was needed to be selected before and the restriction V(0)=0 in transforming the physical constraints into LMI-based conditions. Contrastively, λ involved in inequalities (30) and (34) is a variable and it can be found by solving these LMIs. More importantly, the restriction V(0)=0 is not needed here.Remark 8.
Different from [20, 25], positive definite matrix P¯ in Theorem 6 is not required to be diagonal, which discards the constraint on P.


## 4. Numerical Example

Consider a data communication network shown in Figure1 [20, 30]. The capacity of each link is also indicated in the figure, the unit of which is kbit/sec. All the nodes are assumed to be sources as well as destinations. From Figure 1, it follows that there are 6 queues (the states of the system) and 8 output flows for these queues (the input signals). The queue dynamic of the communication network can be described as follows
(35)x1(k+1)=x1(k)+B1u1(k)+Bd31u3(k-τ31(k)),x2(k+1)=x2(k)+B2u2(k)+Bd12u1(k-τ12(k))x2(k+1)=+Bd32u3(k-τ32(k)),x3(k+1)=x3(k)+B3u3(k)+Bd23u2(k-τ23(k)),
where
(36)x1(k)=[q12(k)q13(k)],x2(k)=[q21(k)q23(k)],x3(k)=[q31(k)q32(k)],u1(k)=[f122(k)f123(k)],u2(k)=[f231(k)f233(k)],u3(k)=[f311(k)f312(k)f321(k)f322(k)],B1=B2=[-100-1],Bd31=[01000000],Bd12=[0001],Bd32=[00100000],B3=[-10-100-10-1],Bd23=[1000].Figure 1
Topology of a communication network.Assume that the maximal buffer sizes,qi(i∈𝒩), are given by q1=10, q2=15, and q3=20. For the case of τij=5 for all (i,j)∈ℒ, by Theorem 6 with ɛi=4, one can get
(37)K1=[0.20350.00010.00010.1971],K2=[0.1934000.2037],K3=[0.2219000.17430.1388000.1736].Now, we provide a simulation.Suppose that the initial states ofxi(k) are given by x1(0)=[6,3]T, x2(0)=[5,8]T and x3(0)=[9,9]T. With the obtained controller gains in (37), the state responses of the system are depicted in Figures 2, 3, and 4, which shows that the system is asymptotically stable. Figures 5, 6, 7, and 8 show the data flows between nodes in the communication network. From Figures 5–8, one can see that the physical constraints are satisfied although initial state x(0) is not equal to 0. So, the proposed decentralized routing control scheme is effective.Figure 2
State response ofx1(k).Figure 3
State response ofx2(k).Figure 4
State response ofx3(k).Figure 5
Data flow from node 1 to node 2.Figure 6
Data flow from node 2 to node 3.Figure 7
Data flow from node 3 to node 1.Figure 8
Data flow from node 3 to node 2.


## 5. Conclusion

In this paper, the routing control problem of data communication networks has been investigated. By considering both the network-induced delays and the physical constraints, a decentralized routing control scheme is proposed, which can be realized by solving a set of LMIs. Since a method is used to relax the transformation conditions of the physical constraints, and a reciprocally convex combination technique is employed to dealing with the network-induced delays, a less complex and less conservative designing result is obtained. A simulation example is given to illustrate the effectiveness of the presented designing scheme.



---

*Source: 648267-2013-04-09.xml*