# Optimal Insurance to Minimize the Probability of Ruin: Inverse Survival
Function Formulation

Bahman Angoshtari  1365 Memorial Drive, Ungar 523, Department of Mathematics,
University of Miami, Coral Gables, FL 33146, USA. Email:
<EMAIL_ADDRESS>Virginia R. Young  530 Church Street, Department
of Mathematics, University of Michigan, Ann Arbor, MI 48109, USA. Email:
<EMAIL_ADDRESS>
###### Abstract

We find the optimal indemnity to minimize the probability of ruin when premium
is calculated according to the distortion premium principle with a
proportional risk load, and admissible indemnities are such that both the
indemnity and retention are non-decreasing functions of the underlying loss.
We reformulate the problem with the inverse survival function as the control
variable and show that deductible insurance with maximum limit is optimal. Our
main contribution is in solving this problem via the inverse survival
function.

_Keywords_ : Optimal insurance, probability of ruin, distortion premium
principle, deductible insurance, maximum limit.

_JEL Codes_ : C61, G22.

##  1 Introduction

The problem of computing optimal insurance has a long history, dating back to
optimal risk exchanges studied by Borch [3, 4] and optimal insurance design
studied by Arrow [1]. In this introduction, we describe the work in papers
related to the problem we solve, namely, minimizing the probability of ruin
when premium is calculated according to the distortion premium principle.
Throughout this introduction, $X$ denotes the insurance loss, a non-negative
random variable, $I(X)$ denotes the indemnity purchased by a buyer of
insurance, and $R(X)=X-I(X)$ denotes the loss retained by the buyer.

Gajek and Zagrodny [9] assume that $0\leq I(x)\leq x$ for all $x\geq 0$ and
assume that the insurance premium is a non-decreasing function of
$\mathbb{E}\thinspace I(X)$. Then, if the buyer of insurance wants full
protection against ruin, then deductible insurance is the cheapest, which ties
in nicely with Arrow’s Theorem on the optimality of deductible insurance.
Gajek and Zagrodny [9] also show that, if the buyer allows for ruin by
limiting the amount spent on insurance, then truncated deductible insurance is
optimal, optimal in the sense of minimizing the probability of ruin. By
truncated deductible insurance, we mean insurance of the form $I(x)=(x-d)_{+}$
when $x<m$ and $I(x)=0$ when $x\geq m$, for some $m>d$.

Kaluszka [10] computes the insurance premium via an economic principle (using
a price density), a generalized zero-utility principle, an Esscher principle,
or a mean-variance principle. Optimal insurance to minimize the probability of
ruin is truncated deductible insurance for each of these premium principles,
and he proves this result directly. He assumes that the premium is fixed so
does not find the optimal amount to spend on insurance. Kaluszka [10] also
considers optimal insurance to minimize the probability of ruin if the
insurance company invests in a risky asset during the period. He assumes that
the insurance premium is computed via the expected-value principle with a
positive safety loading; again, the amount spent on insurance is given a
priori. Truncated deductible insurance is optimal, and Kaluska also finds the
optimal amount to invest in the risky asset. Finally, Kaluszka [10] considers
a variety of other models: (1) He minimizes the variance of the insurance
company’s retained risk subject to a VaR constraint (equivalent to computing
the premium via a percentile premium). Optimal insurance is a modified
deductible policy with a maximum limit (modified DIML policy). (2) He
reconsiders Arrow’s problem with the addition of a VaR constraint. Optimal
insurance is a modified DIML policy. (3) He maximizes the expected dividend
payment when the insurance premium is computed according to the expected-value
principle. Optimal insurance is truncated full coverage. (4) He maximizes a
Kahneman-Tversky value function subject to a premium constraint based on the
expected-value principle. Optimal insurance is truncated deductible insurance.

Cai et al. [5] compute the insurance premium via the expected-value principle
with a positive safety loading $\theta>0$. The class of indemnity functions
are is the collection of non-decreasing, convex functions $I$ such that $0\leq
I(x)\leq x$. They show that proportional deductible insurance minimizes both
VaR and CTE, that is, $I^{*}(x)=c(x-d)_{+}$, which includes the proportion
$c=1$ and deductible $d=0$. Cheung [6] revisits the problem considered by Cai
et al. [5] and uses a geometric approach to solve the minimization problem,
which results in a simpler proof of the optimality of proportional deductible
insurance. Also, Chi and Tan [7] simplify and extend the work of Cai et al.
[5]. Specifically, they show that to minimize VaR of the ceding company when
insurance is computed according to the expected-value principle, (1)
proportional deductible insurance is optimal when $I(x)$ is restricted to be
increasing and convex, (2) DIML is optimal when both $I(x)$ and $R(x)=x-I(x)$
are restricted to be increasing, (3) truncated deductible insurance is optimal
when $R(x)$ is restricted to be increasing and left continuous. By contrast,
Chi and Tan [7] show that to minimize CVaR, deductible insurance is optimal
for all three cases.

Cui et al. [8] compute the insurance premium via a distorted premium principle
with distortion function not necessarily equal to 1 at 1, and they restrict
the class of indemnities such that both the indemnity and retention functions
are non-negative and non-decreasing with the underlying loss. Optimal
insurance is a layered policy with the various layers depending on how the two
distortion functions cross each other. Assa [2] extends the work of Cui et al.
[8] to consider the risk measures of both the buyer and seller of insurance.
He assumes that indemnity and retention functions are non-negative and non-
decreasing, which implies that any such indemnity function $I(x)$ is
absolutely continuous with respect to Lebesgue measure and, thus, is
differentiable almost everywhere. Hence, there exists a Lebesgue integrable
function $h$ such that $I(x)=\int_{0}^{x}h(t)\,dt$. This function $h$ is
called the marginal indemnification function (MIF), and Assa [2] uses the MIF
to obtain the optimal indemnity. Similarly, Zhuang et al. [13] use the MIF to
extend the work of Cui et al. [8] by further restricting $h$ so that
$h_{0}\leq h(x)\leq h_{1}$ for some constants $0\leq h_{0}<h_{1}\leq 1$.

Weng and Zhuang [11] minimize the probability of ruin when insurance is
computed according to a (concave) distortion premium principle with safety
loading $\theta>0$ for a given amount spent on insurance $\pi=\Pi_{g}(I(X))$.
They assume that the retention $R(x)$ lies between $0$ and $x$ (as do all of
these papers) and that $R$ is a non-decreasing function of the underlying
loss. Weng and Zhuang [11] inspired this paper because they reformulate their
minimization problem in terms of the CDF of the retained loss. We redo their
work by assuming that $I$ is also an increasing function of the underlying
loss, which is a natural requirement to prevent the moral hazard of
underreporting losses. Instead of using the CDF of $R(X)$, we use the inverse
survival function, which we find more natural. Weng and Zhuang [11] mistakenly
write that $\pi=\Pi_{g}(X)-\Pi_{g}(R(X))$, which one cannot assert for their
model because $I$ is not necessarily an increasing function of the underlying
loss. That is, as random variables, $I(X)$ and $R(X)$ are not necessarily
comonotonic, which is a requirement in order to say that
$\Pi_{g}(I(X))+\Pi_{g}(R(X))=\Pi_{g}(X)$.

In this paper, we minimize the probability of ruin when premium is calculated
according to the distortion premium principle with a proportional risk load,
and we restrict both $I(x)$ and $R(x)=x-I(x)$ to be non-decreasing, thereby
extending the work of Chi and Tan [7] who minimize VaR.111Recall that Chi and
Tan [7] compute the insurance premium via the expected-value premium
principle, which is a special case of the distortion premium principles with a
proportional risk load. The remainder of the paper is organized as follows. In
Section 2, we present the model set up and state the minimization problem with
the retention function as the control variable. Then, in Section 3, we
reformulate the problem with the inverse survival function as the control
variable and show that deductible insurance with maximum limit (DIML), or so-
called limited deductible insurance, is optimal. Finally, in Section 4, we
obtain the optimal deductible and maximum limit.

##  2 Model set up and ruin-minimization problem

Consider an individual with initial capital $w>0$ who is subject to a loss
represented by a non-negative random variable $X$ and who seeks to minimize
her probability of ruin by buying insurance.

For a random variable $Y$, let $S_{Y}$ denote the _survival function_ of $Y$,
that is,

$S_{Y}(x)=\mathbb{P}\thinspace(Y>x),\quad x\in\mathbb{R},$ (2.1)

and define the corresponding _inverse survival function_ , or _quantile
function_ , by

$S^{-1}_{Y}(p)=\inf\\{x\geq 0:S_{Y}(x)\leq p\\},\quad p\in[0,1].$ (2.2)

Note that $S^{-1}_{Y}$ is non-increasing and right-continuous, as is $S_{Y}$.

Let $M$ denote the essential supremum of $X$, which might equal $\infty$;
specifically,

$M=\inf\\{x\geq 0:S_{X}(x)=0\\}\in\mathbb{R}^{+}\cup\\{\infty\\}.$ (2.3)

We assume throughout the paper that $S_{X}$ is continuously differentiable and
strictly decreasing on $[0,M]$, and that $S_{X}(M):=\lim_{x\to
M^{-}}S_{X}(x)=0$. Note that $X$’s quantile function satisfies

$S_{X}\big{(}S_{X}^{-1}(p)\big{)}=p,\quad\text{and}\quad
S_{X}^{-1}\big{(}S_{X}(x)\big{)}=x,$ (2.4)

for all $p\in[0,S_{X}(0)]$ and $x\in[0,M]$.

######  Remark 2.1.

$X$ can have an atom at $0$, in which case, $S_{X}(0):=\lim_{x\to
0^{+}}S_{X}(x)<1$. Furthermore, $X$ can be unbounded from above, in which case
$M=\infty$. With a slight abuse of notation, the interval $[a,M]$ and the
function evaluation $f(M)$ are interpreted as $[a,\infty)$ and
$\lim_{x\to\infty}f(x)$, respectively, when $M=\infty$. ∎

The individual buys insurance to mitigate her loss $X$. We represent the
insurance contract by an _indemnity_ $I$ such that the insurer is responsible
for the amount $I(x)$ if the policyholder’s loss $X=x$. We also define the
_retention_ $R$ by $R(x)=x-I(x)$; thus, when the loss $X=x$, $R(x)$ is the
amount of loss for which the policyholder is responsible. We impose the
following conditions on the policyholder’s retention (and indemnity).

######  Definition 2.2.

A function $R:[0,M]\to[0,M]$ is an admissible retention if

  1. $(i)$

$0\leq R(x)\leq x$ for all $x\in[0,M];$

  2. $(ii)$

$R$ is non-decreasing on $[0,M];$ and,

  3. $(iii)$

$I(x)=x-R(x)$, $x\in[0,M]$, is also non-decreasing.

We denote the set of all admissible retentions by $\mathcal{A}$. ∎

Condition (i) states that neither the policyholder nor the insurer will be
responsible for more than the total loss $X$. Indeed, if $R(x)<0$ for some
$x\geq 0$, then the individual would be motivated to create or report loss
$X=x$ because she would gain $I(x)-x>0$ from the loss. No insurance company
would issue a policy that allowed a policyholder to gain from an insurable
loss. Also, if $R(x)>x$ for some $x\geq 0$, then the individual would not buy
such a policy because, in addition to suffering a loss $X=x$, the individual
would have to pay the insurance company $R(x)-x>0$.

Conditions (ii) and (iii) reduce the risk of moral hazard. Indeed, if the
retention were decreasing, then the policyholder would have an incentive to
create more loss in order to reduce her retention. Similarly, if the indemnity
were decreasing, then the policyholder would have an incentive to report a
smaller loss to the insurer. Note that a retention $R$ belongs to
$\mathcal{A}$ if and only if the indemnity $I$ also belongs to $\mathcal{A}$.

For any $R\in\mathcal{A}$, we introduce the following notation. With a slight
abuse of notation, we define $S_{R}:=S_{R(X)}$, that is, $S_{R}$ is the
survival function of $R(X)$. We also denote the quantile function of $R(X)$ by
$S^{-1}_{R}$. Similarly, we write $S_{I}$ for $S_{I(X)}$ and $S^{-1}_{I}$ for
the corresponding quantile function.

Following [8], [2], [13], and [11], we assume that the insurance premium is
given by

$\pi_{I}=(1+\theta)\int_{0}^{M}g\big{(}S_{I}(x)\big{)}\,dx,$ (2.5)

in which $\theta\geq 0$ is the _safety loading_ and $g:[0,1]\to[0,1]$ is a
strictly increasing _distortion function_ such that $g(0)=0$ and
$g(1)=1$.222We assume that $g$ is _strictly_ increasing because we want to be
able to compute its functional inverse. By Fubini’s theorem, for any
$\pi_{I}<\infty$,

$\begin{split}\frac{\pi_{I}}{1+\theta}=\int_{0}^{M}\int_{0}^{S_{I}(x)}dg(p)\,dx=\int_{0}^{S_{I}(0)}\int_{0}^{S_{I}^{-1}(p)}dx\,dg(p)=\int_{0}^{S_{X}(0)}S_{I}^{-1}(p)\,dg(p).\end{split}$
(2.6)

Furthermore, for any $R\in\mathcal{A}$, $R(X)$ and $I(X)=X-R(X)$ are
comonotonic because they are both non-decreasing functions of $X$. Thus, by
the comonotonic additivity property of the distorted premium principle,

$\pi_{I}=\pi_{X}-(1+\theta)\int_{0}^{S_{X}(0)}S_{R}^{-1}(p)\,dg(p),$ (2.7)

in which $\pi_{X}$, the price of insuring the total loss, is given by

$\pi_{X}=(1+\theta)\int_{0}^{S_{X}(0)}S_{X}^{-1}(p)\,dg(p),$ (2.8)

which we assume is finite.333[11] err in assuming $\pi_{I}+\pi_{R}=\pi_{X}$
because, in their paper, $I$ and $R$ are not necessarily comonotonic. Only $R$
is required to be non-decreasing with respect to $X$, so $I=X-R$ might
decrease as $X$ increases. In fact, for the optimal insurance, namely,
truncated deductible insurance, $I(x)=(x-d)_{+}\,{\bf 1}_{\\{x\leq m\\}}$,
decreases to $0$ when $x>m$. Also, if $0<m<M$ in the expression for $I$, then
$\pi_{I}+\pi_{R}\neq\pi_{X}$.

######  Remark 2.3.

Note that if $w\geq\pi_{X}$, in which $w>0$ is the individual’s initial
capital, then the policyholder can avoid ruin with probability one by choosing
the indemnity $I(x)=x$. More generally, if

$w\geq d+(1+\theta)\int_{d}^{M}g\big{(}S_{X}(x)\big{)}\,dx,$ (2.9)

for some $d\geq 0$, then the individual can avoid ruin with probability one by
purchasing deductible insurance with $I(x)=(x-d)_{+}$. The least amount of
money required for this the so-called safe level, denoted by $w_{s}$
$($subscript s for safe$)$, and is obtained by minimizing the right side of
inequality (2.9) with respect to $d\geq 0$. It is straightforward to show that
$w_{s}$ equals

$w_{s}=d_{s}+(1+\theta)\int_{d_{s}}^{M}g\big{(}S_{X}(x)\big{)}\,dx,$ (2.10)

in which $d_{s}$ is given by

$d_{s}=\begin{cases}0,&\quad\text{if }\theta\leq\theta_{s},\\\
S^{-1}_{X}\left(g^{-1}\left(\frac{1}{1+\theta}\right)\right),&\quad\text{otherwise},\end{cases}$
(2.11)

and $\theta_{s}$ is given by

$\theta_{s}=\frac{1}{g\left(S_{X}(0)\right)}-1.$ (2.12)

Henceforth, assume that $w<w_{s}$. ∎

We now formulate the optimal insurance problem from the perspective of the
policyholder, who seeks to minimize her probability of ruin. For a given
retention $R$, the net capital of the policyholder after paying the insurance
premium and experiencing the loss retained loss is $w-\pi_{I}-R(X)$. Thus, the
policyholder’s probability of ruin equals

$\mathbb{P}\thinspace\big{(}w-\pi_{I}-R(X)<0\big{)}=\mathbb{P}\thinspace\big{(}R(X)>w-\pi_{I}\big{)}=S_{R}(w-\pi_{I}).$
(2.13)

It then follows from (2.7) that the policyholder faces the following
functional optimization problem,

$\inf_{R\in\mathcal{A}}S_{R}\Big{(}w-\pi_{X}+(1+\theta)\int_{0}^{S_{X}(0)}S_{R}^{-1}(p)\,dg(p)\Big{)},$
(2.14)

for $w<w_{s}$.

######  Remark 2.4.

There is a duality between the ruin-minimization problem we consider and
minimizing value-at-risk, or $VaR_{\alpha}$, given by

$VaR_{\alpha}(R(X)+\pi_{I})=\inf\\{w\geq
0:\mathbb{P}\thinspace(R(X)+\pi_{I}>w)\leq\alpha\\}.$ (2.15)

Indeed, if the minimum probability of ruin in (2.14) equals $\alpha^{*}$ with
minimizer $R^{*}$, then $w$ is the minimum value of $VaR_{\alpha^{*}}$ with
minimizer $R^{*}$, and vice versa. Thus, we expect DIML, or limited deductible
insurance, to minimize the probability of ruin for $R\in\mathcal{A}$, as in
Theorem $3.2$ of [7]. Although our distortion premium principle is more
general than their expected-value premium principle, our result should
coincide with theirs qualitatively. ∎

##  3 Reformulating (2.14) via the retention quantile function

In problem (2.14), the retention $R$ appears indirectly through the survival
function $S_{R}$ and its right-continuous inverse $S^{-1}_{R}$. It will be
useful to reformulate (2.14) with $S_{R}^{-1}$ as the control variable. To
this end, we introduce the set of admissible retention quantile functions.

######  Definition 3.1.

A function $S_{R}^{-1}:[0,1]\to[0,M]$ is called an admissible retention
quantile function if

  1. $(i)$

$S_{R}^{-1}$ is non-increasing and right-continuous;

  2. $(ii)$

$S_{R}^{-1}\leq S_{X}^{-1};$ and,

  3. $(iii)$

$S_{I}^{-1}=S_{X}^{-1}-S_{R}^{-1}$ is also non-increasing and right-
continuous.

The set of all admissible retention quantile functions is denoted by
$\mathcal{S}^{-1}$. ∎

######  Remark 3.2.

Any admissible retention quantile function $S_{R}^{-1}\in\mathcal{S}^{-1}$
must be continuous on $[0,S_{X}(0)]$, not just right-continuous. Continuity
follows from $(iii)$ because any $($downward$)$ jump in the closed interval
would make the indemnity quantile function $S_{I}^{-1}=S_{X}^{-1}-S_{R}^{-1}$
have an upward jump. This continuity is a reason to work with quantile
functions instead of survival functions $($which potentially have jumps$)$. ∎

######  Remark 3.3.

Note that $S_{R}^{-1}$ belongs to $\mathcal{S}^{-1}$ if and only if
$S_{I}^{-1}$ belongs to $\mathcal{S}^{-1}$. ∎

Next, we establish a one-to-one correspondence between admissible retention
functions in $\mathcal{A}$ and admissible retention quantile functions in
$\mathcal{S}^{-1}$.

######  Lemma 3.4.

For any $R\in\mathcal{A}$, $S_{R}^{-1}$ given by (2.2) belongs to
$\mathcal{S}^{-1}$. Conversely, for any $S_{R}^{-1}\in\mathcal{S}^{-1}$,
define $R:[0,M]\to[0,M]$ by

$R(x):=S^{-1}_{R}\big{(}S_{X}(x)\big{)},$ (3.1)

Then, $R\in\mathcal{A}$, and $S^{-1}_{R}$ is the inverse survival function of
$R$.

###### Proof.

To show the first statement, we check that $S^{-1}_{R}$ satisfies conditions
$(i)$-$(iii)$ of Definition 3.1 for a given $R\in\mathcal{A}$. $S^{-1}_{R}$ is
non-increasing and right-continuous by its definition in (2.2). Also,
$S_{R}(x)\geq S_{X}(x)$, for all $x\in[0,M]$, since $R(X)\leq X$. Thus, by
(2.2), $S^{-1}_{R}\leq S^{-1}_{X}$ on $[0,1]$. It only remains to check
condition $(iii)$. From condition $(iii)$ in Definition 2.2, we know that
$I(x):=x-R(x)$ is non-decreasing with respect to $x$; thus, $R(X)$ and $I(X)$
are comonotonic, which implies that $S^{-1}_{I}+S^{-1}_{R}=S^{-1}_{X}$. It
follows that, if we define $S^{-1}_{I}$ by $S^{-1}_{X}-S^{-1}_{R}$, then
$S^{-1}_{I}$ equals the inverse survival function of $I=X-R$ and is, hence,
non-decreasing and right-continuous.

To show the second statement, we check that $R$ satisfies conditions
$(i)$-$(iii)$ of Definition 2.2 for a given $S_{R}^{-1}\in\mathcal{S}^{-1}$.
Note that $R$ defined by (3.1) is non-decreasing because both $S^{-1}_{R}$ and
$S_{X}$ are non-increasing. Next, because $S^{-1}_{R}\leq S^{-1}_{X}$ and
because $S^{-1}_{X}$ maps $[0,S_{X}(0)]$ continuously onto $[0,M]$, it follows
that $0\leq R(x)\leq x$, for all $0\leq x\leq M$. Also,
$R(X)=S^{-1}_{R}(S_{X}(X))\sim S^{-1}_{R}(U)$, because $S_{X}(X)\sim U$, in
which $U$ is uniformly distributed on $[0,1]$. Thus, the inverse survival
function of $R$ is given by

$\inf\left\\{x\geq 0:\mathbb{P}\thinspace\left(S^{-1}_{R}(U)>x\right)\leq
p\right\\}=S^{-1}_{R}(p).$ (3.2)

It only remains to show that $R$ satisfies condition (iii) of Definition 2.2.
To that end, define $S_{I}^{-1}(p):=S_{X}^{-1}(p)-S_{R}^{-1}(p)$, $0\leq p\leq
1$, and observe that $S_{I}^{-1}\in\mathcal{S}^{-1}$ by Remark 3.3. By the
above argument, $S^{-1}_{I}$ is the inverse survival function of $I(X)$, in
which $I$ is defined by $I(x):=S^{-1}_{I}\big{(}S_{X}(x)\big{)}$.

Finally, to show condition (iii) of Definition 2.2, it suffices to show that
$I(X)+R(X)$ has the same distribution as $X$. The latter statement can be
easily shown, since the comonotonicity of $I(X)$ and $R(X)$ implies that

$S^{-1}_{I(X)+R(X)}(p)=S^{-1}_{I}(p)+S^{-1}_{R}(p)=S^{-1}_{X}(p),\quad 0\leq
p\leq 1.\qed$

Let us illustrate the relationship between retentions and retention quantile
functions by the following example.

######  Example 3.5.

Consider the retention

$\tilde{R}(x)=\tilde{R}(x;d,m)=\begin{cases}x,&\quad 0\leq x\leq d,\\\
d,&\quad d<x\leq m,\\\ x-(m-d),&\quad x>m,\end{cases}$ (3.3)

in which $0\leq d\leq m\leq M$. Note that the corresponding indemnity,
$\tilde{I}(x)=x-\tilde{R}(x)$, is _deductible insurance with maximum limit
(DIML)_ , or limited deductible insurance, given by

$\tilde{I}(x)=\tilde{I}(x;d,m)=\begin{cases}0,&\quad 0\leq x\leq d,\\\
x-d,&\quad d<x\leq m,\\\ m-d,&\quad x>m,\end{cases}$ (3.4)

in which $d$ is the deductible, and $m$ is the maximum limit.

Let $p_{i}=S_{X}(i)$, for $i\in\\{m,d\\}$. Then, the quantile function of
$\tilde{R}(X)$ is

$\tilde{S}_{R}^{-1}(p)=\tilde{S}_{R}^{-1}(p;p_{m},p_{d})=\begin{cases}S^{-1}_{X}(p)-(m-d),&\quad
0\leq p<p_{m},\\\ d,&\quad p_{m}\leq p<p_{d},\\\ S^{-1}_{X}(p),&\quad
p_{d}\leq p\leq S_{X}(0),\end{cases}$ (3.5)

which clearly belongs to $\mathcal{S}^{-1}$.

Conversely, take arbitrary constants $0\leq p_{m}\leq p_{d}\leq S_{X}(0)$, set
$i=S_{X}^{-1}(p_{i})$, for $i\in\\{m,d\\}$, and define
$\tilde{S}_{R}^{-1}\in\mathcal{S}^{-1}$ via (3.5). A straightforward
calculation shows that the retention given by (3.1), namely,

$\tilde{R}(x):=\tilde{S}^{-1}_{R}\big{(}S_{X}(x)\big{)},\quad x\in[0,M],$

coincides with (3.3). Thus, $\tilde{R}\in\mathcal{A}$ and $\tilde{S}^{-1}_{R}$
is the inverse survival function of $\tilde{R}(X)$.∎

A direct consequence of Lemma 3.4 is that Problem (2.14) is equivalent to the
following problem

$\inf_{S_{R}^{-1}\in\mathcal{S}^{-1}}S_{R}\Big{(}w-\pi_{X}+(1+\theta)\int_{0}^{S_{X}(0)}S_{R}^{-1}(p)\,dg(p)\Big{)},$
(3.6)

in which, for each $S_{R}^{-1}\in\mathcal{S}^{-1}$, $S_{R}$ is its right-
continuous inverse given by $S_{R}(x)=\inf\\{p:S_{R}^{-1}(p)\leq x\\}$,
$x\in[0,M]$. We state this result as the following proposition, whose proof
directly follows from Lemma 3.4, so we omit it.

######  Proposition 3.6.

Problems (2.14) and (3.6) are equivalent. Specifically, if
$S^{-1,*}_{R}\in\mathcal{S}^{-1}$ optimizes problem (3.6), then an optimal
solution of (2.14) is given by

$R^{*}(x):=S^{-1,*}_{R}\big{(}S_{X}(x)\big{)},\quad x\in[0,M].$ (3.7)

Conversely, if $R^{*}\in\mathcal{A}$ solves problem (2.14), then
$S^{-1,*}_{R}$, the quantile function of $R^{*}(X)$, belongs to
$\mathcal{S}^{-1}$ and solves problem (3.6). ∎

The following theorem shows that the optimal insurance policy is a DIML
contract, as introduced in Example 3.5.

######  Theorem 3.7.

If (3.6) has an optimal solution, then there exists an optimal solution of
(2.14) that is a DIML retention function given by (3.3), for some $0\leq d\leq
m\leq M$.

###### Proof.

Let $S_{R}^{-1,*}$ be an optimal solution of (3.6), define $d^{*}$ by

$d^{*}=w-\pi_{X}+(1+\theta)\int_{0}^{S_{X}(0)}S_{R}^{-1,*}(p)\,dg(p),$ (3.8)

and set $p_{m}^{*}=S^{*}_{R}(d^{*})$, in which $S^{*}_{R}$ is the right-
continuous inverse of $S^{-1,*}_{R}$. Note that $p^{*}_{m}$ is the minimum
probability of ruin.

Consider the following auxiliary problem:

$\sup_{S_{R}^{-1}\in\mathcal{S}^{-1}}\left\\{\int_{0}^{S_{X}(0)}S_{R}^{-1}(p)\,dg(p):S_{R}^{-1}(p^{*}_{m})=d^{*}\right\\}.$
(3.9)

We first show that any optimal solution of (3.9) is also an optimal solution
of (3.6). Let $S_{R}^{-1,A}\in\mathcal{S}^{-1}$ be an optimal solution of
(3.9), and denote its right-continuous inverse by $S^{A}_{R}$. Then, because
$S^{*}_{R}(d^{*})=p^{*}_{m}$, it follows that

$\int_{0}^{S_{X}(0)}S_{R}^{-1,A}(p)\,dg(p)\geq\int_{0}^{S_{X}(0)}S_{R}^{-1,*}(p)\,dg(p).$
(3.10)

Define

$d^{A}=w-\pi_{X}+(1+\theta)\int_{0}^{S_{X}(0)}S_{R}^{-1,A}(p)\,dg(p).$ (3.11)

Inequality (3.10) implies $d^{A}\geq d^{*}$; thus, $S^{A}_{R}(d^{A})\leq
S^{A}_{R}(d^{*})=p^{*}_{m}$. Because $S^{-1,*}_{R}$ is an optimal solution of
(3.6), it follows that $S^{A}_{R}(d^{A})=p^{*}_{m}$, so $S^{-1,A}_{R}$ is also
an optimal solution for (3.6).

To finish the proof, it only remains to show that the solution of (3.9) is a
DIML retention quantile function, as given in (3.5). Figure 1 illustrates the
feasibility set of problem (3.9). In particular, (3.9) looks for a non-
increasing and continuous function $S^{-1}_{R}:[0,S_{X}(0)]\to[0,M]$ whose
graph falls into the shaded region of Figure 1 such that the integral
$\int_{0}^{S_{X}(0)}S^{-1}_{R}(p)\,dg(p)$ is maximized. Recall that an
admissible retention $S^{-1}_{R}$ is such that $S^{-1}_{X}-S^{-1}_{R}$ is non-
decreasing. It is evident that the optimal choice for $S^{-1}_{R}$ is the
upper boundary of the shaded region, which coincides with a DIML retention
quantile function (3.5). ∎

######  Remark 3.8.

From the proof of Theorem 3.7, we learn that, for the optimal DIML retention,
$\tilde{R}^{*}$, the probability
$p_{m}^{*}=S_{\tilde{R}^{*}}(d^{*})=S_{X}(m^{*})$ is the minimum probability
of ruin. ∎

Figure 1: The feasible region for problem (3.9) includes any non-increasing
and continuous function $S_{R}^{-1}$ whose graph falls into the shaded area
such that $S_{I}^{-1}=S_{X}^{-1}-S_{R}^{-1}$ is also decreasing.

##  4 Optimal DIML contract

Theorem 3.7 implies that if (3.6) has an optimal solution, then it is
sufficient to look within the class of DIML retention quantiles. Thus, our
next goal is to find the optimal DIML contract. By restricting indemnity
contracts to those given by (3.4), problem (2.14) becomes a two-dimensional
problem:

$\inf_{\begin{subarray}{c}0\leq p_{m}\leq p_{d}\leq S_{X}(0)\\\ p_{d}\geq
S_{X}(w)\end{subarray}}\tilde{S}_{R}\Big{(}w-\pi_{X}+(1+\theta)\int_{0}^{S_{X}(0)}\tilde{S}_{R}^{-1}(p;p_{m},p_{d})\,dg(p);\,p_{m},p_{d}\Big{)},$
(4.1)

in which $\tilde{S}_{R}^{-1}$ is given by (3.5), and $\tilde{S}_{R}$ is its
right-continuous inverse. Recall that $p_{i}=S_{X}(i)$ for $i\in\\{m,d\\}$.
Note that we can restrict $d$ to be such that $d\leq w$, or equivalently
$p_{d}\geq S_{X}(w)$, because buying no insurance is always better than buying
a DIML contract with $d>w$.

The following theorem provides the optimal (DIML) insurance policy.

######  Theorem 4.1.

Assume that initial wealth $w$ is less than the safe level $w_{s}$, as given
by (2.10). An optimal insurance policy to minimize the probability of ruin is
given by a DIML contract, and the optimal deductible $d^{*}$ and maximum limit
$m^{*}$ for the optimal DIML insurance policy are as follows . First, recall
that $d_{s}$ is given by

$d_{s}=\begin{cases}0,&\text{if
}\theta\leq\theta_{s}=\frac{1}{g\left(S_{X}(0)\right)}-1,\\\
S^{-1}_{X}\left(g^{-1}\left(\frac{1}{1+\theta}\right)\right),&\text{otherwise}.\end{cases}$
(4.2)

  1. (i)

If $0\leq\theta\leq\theta_{s}$, then $d^{*}=d_{s}=0$, which is independent of
initial wealth, and $m^{*}<M$ uniquely solves

$w=(1+\theta)\int_{0}^{m}g\big{(}S_{X}(t)\big{)}\,dt.$ (4.3)

  2. (ii)

If $\theta>\theta_{s}$ and $w\leq d_{s}$, then it is optimal not to buy
insurance, or equivalently, $d^{*}=m^{*}=w$.

  3. (iii)

If $\theta>\theta_{s}$ and $w>d_{s}$, then $d^{*}=d_{s}>0$, which is
independent of initial wealth, and $m^{*}<M$ uniquely solves

$w-d_{s}=(1+\theta)\int_{d_{s}}^{m}g\big{(}S_{X}(t)\big{)}\,dt.$ (4.4)

###### Proof.

See Appendix A. ∎

Theorem 4.1 can be interpreted as follows. If insurance is cheap enough,
namely, $\theta\leq\theta_{s}$, then the policyholder, regardless of the
amount of her wealth, should spend all of her initial wealth to buy a DIML
contract with a zero deductible and a maximum limit less than $M$. Thus, she
ruins if the loss exceeds the maximum limit.

However, if the insurance is expensive (that is, $\theta>\theta_{s}$), then
the optimal policy changes according to how wealthy the policyholder is. If
her wealth is less than $d_{s}>0$, then she is better off buying no insurance.
If wealth is between $d_{s}$ and $w_{s}$, it is optimal to buy a DIML policy
with non-zero deductible and a maximum limit less than $M$. That policy is
such that her initial wealth exactly covers the insurance premium with
remainder equal to the deductible. Thus, she ruins if the loss exceeds the
maximum limit.

We also have a corollary that follows readily from Theorem 4.1.

######  Corollary 4.2.

For the optimal DIML contract given in Theorem 4.1, the deductible plus the
premium equals initial wealth, that is,
$d^{*}+(1+\theta)\int_{d^{*}}^{m^{*}}g\big{(}S_{X}(t)\big{)}\,dt=w$. In other
words, the constraint in (A.4) binds. Moreover, the minimum probability of
ruin equals $S_{X}(m^{*})$. ∎

Recall that, given any optimal solution of problem (3.6), the proof of Theorem
3.7 computes a quantity $d^{*}$ in (3.8), which, in turn, becomes the
deductible for a DIML contract with the same minimum probability of ruin.
Suppose we begin with the optimal DIML contract, as given in Theorem 4.1, with
a deductible $d^{*}$ and and maximum limit $m^{*}$, then compute the
expression on the right side of (3.8). Because the expression on the right
side of (3.8) equals initial wealth minus the premium, it follows from
Corollary 4.2 that we obtain the deductible $d^{*}$ of the original DIML
policy. Corollary 4.2 also implies that the computation of $p^{*}_{m}$, the
minimum probability of ruin, in the proof of 3.7 leads to the same maximum
limit $m^{*}$ as in the original DIML policy.

##  Appendix A Proof of Theorem 4.1

We introduce the following notation. Define the auxiliary functions $\Psi$ and
$\Phi$ by

$\displaystyle\Psi(x)$
$\displaystyle=(1+\theta)\int_{x}^{M}g\big{(}S_{X}(t)\big{)}\,dt,$ (A.1) and
$\displaystyle\Phi(x)$ $\displaystyle=x+\Psi(x),$ (A.2)

for $x\in[0,M]$. Note that $\Psi$ is strictly decreasing; denote its inverse
by $\Psi^{-1}$.

######  Remark A.1.

It is easy to show that $\Psi(d)-\Psi(m)$ is the premium corresponding to a
DIML insurance with deductible $d$ and maximum level $m$; see (A.7) below.
This result is well known to those who work with the distortion premium
principle, but we include it for completeness. Also, note that
$w_{s}=\Phi(d_{s})$, in which $w_{s}$ and $d_{s}$ are given in (2.10) and
(2.11), respectively.

For ease of reference in this proof, we present the survival function
$\tilde{S}_{R}$ for the retention function of DIML insurance. $\tilde{S}_{R}$,
the right-continuous inverse of $\tilde{S}^{-1}_{R}$ in (3.5), is given by

$\tilde{S}_{R}(x)=\begin{cases}S_{X}(x),&\quad 0\leq x<d,\\\
S_{X}(x+m-d),&\quad d\leq x\leq M.\end{cases}$ (A.3)

Without loss of generality, we can assume that the optimal insurance premium
$\pi^{*}_{I}$, for the optimal indemnity and the optimal deductible $d^{*}$
satisfy

$w-\pi^{*}_{I}\geq d^{*}.$ (A.4)

Indeed, if $w-\pi^{*}_{I}<d^{*}$, then (A.3) yields that the minimum
probability of ruin equals

$S_{\tilde{R}^{*}(X)}(w-\pi^{*}_{I})=\tilde{S}^{*}_{R}(w-\pi^{*}_{I})=S_{X}(w-\pi^{*}_{I})\geq
S_{X}(w),$

in which $\tilde{R}^{*}(X)$ is the optimal DIML retention, or equivalently,
$\tilde{S}^{*}_{R}=S_{\tilde{R}^{*}(X)}$ is the optimal survival function of
the retention. But, this inequality implies that buying no insurance is also
optimal, in which case, we can set $d^{*}=m^{*}=w$ to recover (A.4). Thus,
imposing the inequality

$w-\pi_{I}\geq d$ (A.5)

will not change the optimal value of problem (4.1). Under this additional
constraint, by (A.3), the probability of ruin simplifies to

$\tilde{S}_{R}(w-\pi_{I})=S_{X}(w-\pi_{I}+m-d).$

Thus, problem (4.1) is equivalent to

$\sup_{0\leq d\leq m\leq M}\big{\\{}m-d-\pi_{I}:d+\pi_{I}\leq w\big{\\}}.$
(A.6)

We can simplify this optimization problem further. By (2.7), (2.8), and (3.5),
we obtain

$\begin{split}\frac{\pi_{I}}{1+\theta}=\frac{\pi_{X}-\pi_{R}}{1+\theta}&=\int_{0}^{S_{X}(0)}S_{X}^{-1}(p)\,dg(p)-\int_{0}^{S_{X}(0)}\tilde{S}_{R}^{-1}(p;p_{m},p_{d})\,dg(p)\\\
&=\int_{0}^{p_{m}}\big{(}m-S^{-1}_{X}(p)\big{)}\,dg(p)-\int_{0}^{p_{d}}\big{(}d-S_{X}^{-1}(p)\big{)}\,dg(p)\\\
&=\int_{p_{d}}^{p_{m}}g(p)\,dS_{X}^{-1}(p)=\int_{d}^{m}g\big{(}S_{X}(t)\big{)}\,dt.\end{split}$

Therefore,

$\pi_{I}=\Psi(d)-\Psi(m),$ (A.7)

in which $\Psi$ is given by (A.1), and (A.6) becomes

$\sup_{d,m}\left\\{\Phi(m)-\Phi(d):0\leq d\leq
m\leq\Psi^{-1}\big{(}\Phi(d)-w\big{)}\right\\},$ (A.8)

in which $\Phi$ is given by (A.2). Note that $\Phi(d)-w>0$ for all $d\in[0,M]$
because $w<w_{s}=\min_{d\in[0,M]}\Phi(d)$.

We need the following result regarding monotonicity of $\Psi$ and $\Phi$. Its
proof is immediate; thus, we omit it.

######  Lemma A.2.

For $x\in(0,M)$,

$\Psi^{\prime}(x)=-(1+\theta)g\big{(}S_{X}(x)\big{)},\quad\text{and}\quad\Phi^{\prime}(x)=1-(1+\theta)g\big{(}S_{X}(x)\big{)}.$
(A.9)

In particular, $\Psi$ is strictly decreasing on $[0,M]$, and $\Phi$ is
strictly decreasing $($respectively, strictly increasing$)$ on $[0,d_{s})$
$($respectively, $(d_{s},M])$, in which $d_{s}$ is given by (2.11).

For a fixed $d\in[0,M]$, Lemma A.2 implies that

$\begin{split}&\sup_{m}\left\\{\Phi(m):d\leq
m\leq\Psi^{-1}\big{(}\Phi(d)-w\big{)}\right\\}\\\
&=\max\left\\{\Phi(d),\,\Phi\left(\Psi^{-1}\left(\Phi(d)-w\right)\right)\right\\}.\end{split}$
(A.10)

In other words, the best maximum limit $m$, given a fixed deductible
$d\in[0,M]$, is either $m=d$ or

$m=\Psi^{-1}\big{(}\Phi(d)-w\big{)},$ (A.11)

in which the former choice means buying no insurance.

By substituting (A.10) into (A.8), and by noting that

$\Phi\Big{(}\Psi^{-1}\big{(}\Phi(w)-w\big{)}\Big{)}-\Phi(w)=0,$

we obtain the following single-variable optimization problem:

$\sup_{0\leq d\leq
w}\left\\{\Phi\Big{(}\Psi^{-1}\big{(}\Phi(d)-w\big{)}\Big{)}-\Phi(d)\right\\}.$
(A.12)

Let $d^{*}$ be the optimal deductible for problem (A.12). We have the
following dichotomy:

  1. (a)

If $\Phi\left(\Psi^{-1}\big{(}\Phi(d^{*})-w\big{)}\right)-\Phi(d^{*})>0$,
then, by (A.11), the maximum limit $m^{*}$ is given by

$m^{*}=\Psi^{-1}\big{(}\Phi(d^{*})-w\big{)}.$ (A.13)

  2. (b)

If $\Phi\left(\Psi^{-1}\big{(}\Phi(d^{*})-w\big{)}\right)-\Phi(d^{*})=0$,
then, we can choose $d^{*}=m^{*}=w$, and buying no insurance is the best
choice for the policyholder.

It only remains to solve (A.12). From (A.9), we obtain

$\frac{d}{dd}\left[\Phi\Big{(}\Psi^{-1}\big{(}\Phi(d)-w\big{)}\Big{)}-\Phi(d)\right]=-\frac{\Phi^{\prime}(d)}{(1+\theta)g\left(S_{X}\left(\Phi^{-1}\left(\Phi(d)-w\right)\right)\right)}\propto-\Phi^{\prime}(d).$

Lemma A.2, then, yields that the objective function of (A.12) is strictly
increasing on $[0,d_{s})$ and strictly decreasing on $(d_{s},w]$, with $d_{s}$
given by (2.11). It follows that $d_{s}$ is the optimal deductible if
$d_{s}<w$. Recall that we impose the condition that $d+\pi_{I}\leq w$; in
particular, $d<w$ if the individual buys insurance.

We identify the following cases:

  1. (i)

$0\leq\theta\leq\theta_{s}$: By (2.11), $d^{*}=d_{s}=0$, and case (a) above
applies. By (A.13),

$m^{*}=\Psi^{-1}\big{(}\Phi(0)-w\big{)}=\Psi^{-1}\big{(}\pi_{X}-w\big{)},$

or equivalently, $m^{*}$ uniquely solves (4.3). $m^{*}<M$ because
$w<w_{s}=\Phi(0)=\pi_{X}$.

  2. (ii)

$\theta>\theta_{s}$ and $w\leq d_{s}$: It follows that the objective function
of (A.12) is strictly increasing on $[0,w)$. Thus, case (b) above holds, and
it is optimal for the individual not to buy insurance.

  3. (iii)

$\theta>\theta_{s}$ and $w>d_{s}$: By (2.11), $d^{*}=d_{s}>0$, and by (A.13),

$m^{*}=\Psi^{-1}\big{(}\Phi(d_{s})-w\big{)},$

or equivalently, $m^{*}$ uniquely solves (4.4). $m^{*}<M$ because
$w<w_{s}=\Phi(d_{s})$, which implies that
$w-d_{s}<(1+\theta)\int_{d_{s}}^{M}g\big{(}S_{X}(t)\big{)}\,dt$.

## References

  * [1] Arrow, Kenneth J. (1963). Uncertainty and the welfare economics of medical care. The American Economic Review, 53(5): 941-973.
  * [2] Assa, Hirbod (2015). On optimal reinsurance policy with distortion risk measures and premiums. Insurance: Mathematics and Economics, 61: 70-75.
  * [3] Borch, K., (1960). An attempt to determine the optimum amount of stop loss reinsurance. In: Transactions of the 16th International Congress of Actuaries, 597-610.
  * [4] Borch, K. (1960). The safety loading of reinsurance premiums. Scandinavian Actuarial Journal, 1960(3-4): 163-184.
  * [5] Cai, Jun, Ken Seng Tan, Chengguo Weng, and Yi Zhang (2008). Optimal reinsurance under VaR and CTE risk measures. Insurance: Mathematics and Economics, 43(1): 185-196.
  * [6] Cheung, Ka Chun (2010). Optimal reinsurance revisited - a geometric approach. ASTIN Bulletin, 40(1): 221-239.
  * [7] Chi, Yichun and Ken Sang Tan (2011). Optimal reinsurance under VaR and CVaR risk measures: a simplified approach. ASTIN Bulletin, 41(2): 487-509.
  * [8] Cui, Wei, Jingping Yang, and Lan Wu (2013). Optimal reinsurance minimizing the distortion risk measure under general reinsurance premium principles. Insurance: Mathematics and Economics, 53: 74-85.
  * [9] Gajek, Lesław and Dariusz Zagrodny (2004). Reinsurance arrangements maximizing insurer’s survival probability. Journal of Risk and Insurance, 71(3): 421-435.
  * [10] Kaluszka, Marek (2005). Truncated stop loss as optimal reinsurance agreement in one-period models. ASTIN Bulletin, 35(2): 337-349.
  * [11] Weng, Chengguo and Sheng Chao Zhuang (2017). CDF formulation for solving an optimal reinsurance problem. Scandinavian Actuarial Journal, 2017(5): 395-418.
  * [12] Zheng, Yanting, Wei Cui, and Jingping Yang (2015). Optimal reinsurance under distortion risk measures and expected value premium principle for reinsurer. Journal of Systems Science Complex, 28: 122-143.
  * [13] Zhuang, Sheng Chao, Chengguo Weng, Ken Sang Tan, and Hirbod Assa (2016). Marginal Indemnification Function formulation for optimal reinsurance. Insurance: Mathematics and Economics, 67: 65-76.


#  Fair End to End Window Based Congestion Control in Time Varying Data
Communication Networks

Suchi Kumari  Department of Computer Science and Engineering,
National Institute of Technology,
Delhi, India
email<EMAIL_ADDRESS>Anurag Singh  Department of Computer Science
and Engineering,
National Institute of Technology,
Delhi, India
email: Corresponding author<EMAIL_ADDRESS>
###### Abstract

Communication networks are time-varying and hence, fair sharing of network
resources among the users in such dynamic environment is a challenging task.
In this context, a time-varying network model is designed and shortest user’s
route is found. In the designed network model, an end to end window-based
congestion control scheme is developed with the help of internal nodes or
router and the end user can get implicit feedback (RTT and throughput). This
scheme is considered as fair if the allocation of resources among users
minimizes overall congestion or backlog in the networks. Window update
approach is based on multi-class fluid model and is updated dynamically by
considering delays (communication, propagation and queuing) and the backlog of
packets in the user’s routes. Convergence and stability of the window size are
obtained using a Lyapunov function. A comparative study with other window-
based methods is also provided.

###### keywords:

Time varying communication networks, congestion control, fairness, window,
delay

##  1 Introduction

Real life systems such as communication, social, biological can be described
with the help of complex networks [1, 2]. It is a challenging task to design a
time-varying communication network (TVCN) with the ability to respond to the
randomly changing traffic. Hence, the study of the traffic dynamics and fair
sharing of resources on communication networks has received a great wave of
interest for the researchers in past few years. The allocation of resources
among the users in an unbiased manner is one of the challenging tasks in
today’s scenario. For assigning resources in an unbiased or fair manner, some
researchers use various rate vector allocation schemes [3, 4] to gain maximum
utility while others select fair end to end window-based congestion control
scheme [5, 4]. In this paper, we are interested to design a TVCN model
considering network growth, redistribution of traffic from heavily loaded
nodes and removal of some fraction of links to reduce maintenance cost. A
window-based congestion control scheme may be applied on the proposed TVCN
model and user’s current window size may be updated by considering
delays(communication, propagation and queuing delays).

Communication networks are evolving and the concept of evolving networks with
preferential linking during the addition of new nodes is introduced by
Barabasi-Albert ([6]). The distribution of degrees of nodes in these networks
follow the power law and is termed as scale free nature of the networks. Many
time-varying graph (TVG) models are proposed [7, 8]. A series of static graphs
(i.e., the snapshots) is used to represent the network at a given time instant
[9]. Wehmuth et al. [7] proposed a new unifying model for representing finite
discrete TVGs. A framework is designed to obtain degree distribution of
evolving network with the consideration of deletion of nodes and a continuum
formulation is also provided by [10]. A preferential attachment model for
network growth is proposed where a new node has partial information about the
network [11]. A new node has access to a fraction of nodes and a new
connection is formed with the known set of nodes with a probability
proportional to the degree of the node. A framework to represent mobile
networks dynamically in a Spatio-temporal fashion is designed and algebraic
structural representation is also provided by [12]. Chen et al. [13]
investigated controllability of a formation control systems in a directed
graph where a node represents agent and link describes information flow
between nodes in the system. They studied strong and weak connected components
in a time-varying graph and provided some estimations on a number of nodes of
strongly connected components.

Communication networks are extremely changeable and modeling its rate control
behavior helps us in getting optimal utilization of the system. Kelly [3]
provided a mathematical model of the Internet where rate allocation problem is
considered as an assignment of optimal rate to each user for maximizing
individual user’s utility as well as the system utility. La et al. [4]
extended Kelly’s work by introducing a suitable pricing scheme. Resources may
be of multiple types and users request different portion of the resources so
trade-off arises between fair resource allocation and system efficiency [14].
Anirudh et al. [15] have used an automated protocol design tool which
approximates the best possible congestion control scheme without the prior
information about the structure of the network.

Some Congestion control algorithms in the elementary transmission control
protocol (TCP) based models such as TCP Reno [16], Tahoe [17] and TCP Vegas
[18] have performed remarkably well. As current Internet scaled up by more
than six times in size, speed and load in past few years. Hence, due to
increased bandwidth delay, the model will eventually become a performance
bottleneck. A new congestion control scheme, called FAST is developed by
proposing an equation based algorithm to avoid packet level oscillation, using
queuing delay as a measure of congestion and stable and weighed proportionally
fair flow is obtained [19]. Proportional fairness is achieved by their
$(p,1)$-proportionally fair algorithm and max-min fairness is achieved as a
limiting case of $(p,\alpha)$ proportionally fairness. Mo et al. [5] and La et
al. [20] proposed a window based algorithm, in which window sizes are adjusted
more intelligently such that transmission rate and the backlog of packets
should be controlled. TCP/AQM [21] based optimization technique performs well
under commonly defined constraints but it is hard to simulate in the current
complex networks. Low et al. [22] proposed a framework to cop up with buffer-
bloat in multiple bottleneck links. The stability of the Controlled Delay
(CoDel) is also analyzed and system stability and performance are improved by
designing a self-tuning CoDel. In delay tolerant network (DTN), there is no
guarantee of an end to end connection between source and destination hence, it
is a challenging task to perform some functions like routing and congestion
control. Aloizio et al. [23] performed classification on existing DTN and
provided a state of the art in DTN congestion control mechanisms. Giovanna et
al. [24] considered multi-path routing with joint congestion control and user
throughput is maximized, and, overall network cost is minimized.

Some evolving network models only consider the addition of nodes [6], although
some works consider deletion of nodes during/beyond the evolution of the
networks [25, 26, 10]. There are only a few networks such as citation, movie
actor collaboration and science collaboration networks which can be described
without removal of links. But other real-world networks, e.g., like the
Internet, communication networks, WWW, transportation networks have the
varying composition of links due to appearance or disappearance of
connections. A link may disappear due to break down and sometimes removed
forcibly to balance the traffic loads in the communication networks. Few
heavily loaded nodes get the opportunity to rewire (remove a connection from a
node and attach with another node) their links. In this context, the proposed
work considers designing of a TVCN model, minimization of network congestion
and a fair sharing of resources among the users according to their willingness
to pay. A TVCN is designed where nodes, as well as links, are getting added
into the networks while restructuring is performed in the existing networks
through rewiring and removal of the links. Addition and rewiring of links are
based on preferential attachment while removal of links is based on anti-
preferential attachment [27]. Probability $\Pi_{i}$ that a node $i$ will be
selected through preferential attachment is proportional to its in-degree and
is given by, $\frac{k_{i}}{\sum_{j\in N}k_{j}}$ where, $k_{i}$ is in-degree
and the probability $\Pi^{\prime}_{i}$ of selecting node $i$ with anti-
preferential attachment is given by,
$\frac{1}{|N|-1}\left(1-\frac{k_{i}}{\sum_{j\in N}k_{j}}\right)$. Rewiring of
links is done to redistribute the traffic loads, while few links increase the
maintenance cost so these links may be chosen for removal from the network.
After designing the network, users select their routes for data communication
with their destination nodes. Optimality of the routes is checked by using the
proposed window-based congestion control scheme at different time intervals.

In the window based algorithm, a fair end to end congestion control scheme is
developed with the help of internal node or router. Each user calculates
congestion at the resources appearing in its route without using any explicit
signal from the network router. It is hard to get prior information of
network’s feedback as networks are evolving over time. In this paper,
congestion control formulation is considered as fair allocation which is a
natural extension of the models proposed by Mo et al. [5] and La et al. [20]
and a comparative study of these models are also provided. Mo et al. [5]
updated window size by considering propagation delay, queuing delay and using
the difference between the actual and the target backlog. La et al. [20]
updated window size such that it converges to the unique stable point, where
the resulting rates solve the system utility, $SYSTEM(U,A,C)$. As networks
keep changing with time and evolving in nature so it is required to consider
dynamic parameters in the window updating rules. The propagation delay is a
function of the distance between two nodes and remains constant throughout the
life of the networks. Hence, in place of propagation delays, we have
considered transmission delay of the resources. The transmission delay is the
amount of time required for the node to push out the packet and it is
dependent on the transmission rate of the connecting link and the length of
the packet. Once user’s connection is established, packets are transferred to
the receiver and number of packets is decreased at any resource with some
rates. Hence, the transmission delay also decreases accordingly.

In this paper, Section 2 describes fairness and gives background information
about the classical models. Section 3 states the proposed work in two parts:
(i)the time varying communication network model and (ii) fair end to end
congestion control scheme. Section 4 presents simulation results, and in
Section 5, conclusions and future research plan are discussed.

##  2 Fairness and Classical Models

Network structure keeps on changing with time hence, nodes as well as links
will change accordingly. Let the network consist of $N$ nodes, $E$ links
(resources) and $T$ is life time of the network. A set of $R$ users are
willing to access and send data to the desired location through the networks
using the resources. A link $e_{mn}$ establishes a connection between node $m$
and node $n$ and can send maximum $C_{e_{mn}}$ units of data through it, where
capacity of a link $C_{e_{mn}}$ is dependent on the degrees $k_{m}$ and
$k_{n}$ of nodes $m$ and $n$. Each user $r$ is assigned a route $r\in R$ in
the duration of time $t_{(i-1)}\in T$ to $t_{i}\in T$. At the end of
$t_{i}^{th}$ time, a zero-one matrix $A$ of the size $(R\times E)_{t_{i}}$ is
defined where, $A_{r,e_{ab},t_{i}}=1$, if link $e_{ab}$ is a part of route
$r_{i}$ in the duration of time $t_{(i-1)}$ to $t_{i}$, otherwise zero.

###  2.1 Fairness

Fairness is defined as how the bottleneck resources are shared among users in
communication networks. There are various types of fairness measures.

  * 1.

Max-min fairness: A feasible flow vector is defined as max-min fair if any
rate vector $x_{i}$ cannot be increased without decreasing some $x_{j}$ where,
$x_{j}\leq x_{i}$. The max-min fairness is defined in terms of transmission
rates of source nodes sending data to destination nodes [28]. We need
transmission schedules of the packets along with the global state and timing
information of all the nodes in the network hence, its use is avoided in
dynamic communication networks.

  * 2.

Proportional fairness: A rate vector $x^{*}$ is called proportionally fair if
it is feasible. For any other feasible vector $x$, the aggregate of the
proportional change is negative.

$\sum_{i}\frac{x_{i}-x_{i}^{*}}{x_{i}^{*}}\leq 0$

  * 3.

$(p,\alpha)-$ Proportional fairness: There is a trade-off between fairness and
resource utility maximization. Max-min fairness approach gives more priority
on fairness. But, in real life scenario, we want to maximize overall network
utility. Therefore, we need to generalize max-min fairness and proportional
fairness. $(p,\alpha)-$ defines both the fairness approach; proportional and
max-min. If $\alpha=1$, then it converges to proportional fairness otherwise
it will behave as max-min fairness.

As we want to get optimal window size according to the willingness of pay
$p_{r}$ for each user, $r$ so $(p,1)$ proportional fairness approach may be
used. The vector $p$ in $(p,1)$ is proportionally fair and dependent on
utility function $U_{r}(x_{r}(t_{i}))$

###  2.2 Fair End to End Window Based Model

Window based model proposed by Mo et al. [5] and La et al. [20], is based on
the fluid model of the network and is dependent on window size, rate and queue
size. The model can be represented by,

$\displaystyle A^{T}x-c\leq 0,$ (1) $\displaystyle Q(A^{T}x-c)=0,$ (2)
$\displaystyle X(Ad_{Q}+d_{prop})=w,$ (3) $\displaystyle x\geq 0,q\geq 0.$

Where, $x=(1,...,R)^{T}$, $c=(1,...,E)^{T}$, $d_{Q}=(1,...,E)^{T}$,
$d_{prop}=(1,...,R)^{T}$ and $X=diag(x)$. $d_{prop}$ is propagation delay,
$d_{Q}$ is queuing delay and $(Ad_{Q}+d_{prop})$ is total delay. Eq. (1) shows
capacity constraint. The constraint in Eq. (2) states that there may be
backlogged data at any resource if total data rate is equal to its capacity.
Window size of a connection is sum of the number of packets in transmission
and the packets buffered in the queue (Eq. (3)). Rate vector, $x$ and queue
size, $q$ should be positive.

Mo et al. [5] considered $(p,1)$ proportionally fair algorithm where $p$ is
the vector of target queue size of the connections. Let
$((Ad_{Q})^{i}+d_{prop}^{i}),d_{prop}^{i},w_{i}(t)$ and $x_{i}(t)$ denote the
total delay, propagation delay, current window size and data rate of user $i$,
respectively. They update user’s window size based on the following system of
differential equations,

$\displaystyle\frac{dw(t)}{dt}=-\alpha\frac{d_{prop}^{i}}{((Ad_{Q})^{i}+d_{prop}^{i})}\frac{s_{i}(t)}{w_{i}(t)},$
(4) $\displaystyle s_{i}=w_{i}-x_{i}d_{prop}^{i}-p_{i}.$

Where, $s_{i}$ is the difference between actual and targeted backlog of user
$i$.

La et al. introduced dynamicity in the above formulation, where $p_{i}$ is
dependent on $SYSTEM(U(t_{i}),A(t_{i}))$ and $d_{Q}$ is updating dynamically
with time [20],

$\displaystyle\frac{dw(t)}{dt}=-\alpha\frac{d_{prop}^{i}+U^{\prime}_{i}(x_{i}(t))+x_{i}(t)U^{\prime\prime}_{i}(x_{i}(t))}{((Ad_{Q})^{i}(t)+d_{prop}^{i})}\frac{s_{i}}{w_{i}}.$
(5)

As $U_{i}(x_{i}(t))$ is an increasing concave function. Hence, the term
$U^{\prime}_{i}(x_{i}(t))+x_{i}(t)U^{\prime\prime}_{i}(x_{i}(t))$ in Eq. (5)
will always be positive and depend on the rate and user’s utility and is added
into the propagation delay. It shows that user’s window size update equation
depends on user’s utility function.

##  3 Proposed Work

We want to find the node which is endorsed by the maximum number of nodes.
Hence, the probability of linking of a newly appeared node with nodes with a
maximum degree will be greater. The network is shared among users and each
user wants to maximize its system utility and minimize congestion in the
network by choosing an optimal window size. Therefore, the formulation of a
congestion control scheme for a dynamic network is also provided.

###  3.1 Time Varying Communication Network Model

A time-varying communication network model is proposed where, at each time
instant, $t_{i}\in T$, a new node $i$ is added to the network (expansion) and
a number $M(\leq n_{0})$ is selected for network expansion, rewiring, and
removal, where $n_{0}$ is initial number of nodes present as the seed network.
Links are divided into three categories: newly added, rewired and removed
links. Distribution of the links are done using the given set of rules [29].
Notations:

  1. (a.)

$\beta=$ Fraction of the evolving (appear from the new node and
appear/disappear in the existing network) links at any time instant. It
informs about the establishment of new connections from the new nodes at time
$t=n$ , $0<\beta<1$.

  2. (b.)

$\gamma=$ Fraction of the links, rewired in the existing network,
$0.5<\gamma\leq 1$.

Using the above notations, following set of rules are formed,

  1. (i)

Total number of new out-flowing links from the new appeared node, $i\mbox{
}(=t)$ with the nodes in the existing network at $(t-1)$ based on the
preferential attachment is given by,

$f_{add}(t)=\beta M$

  2. (ii)

Few links are rewired in the existing network, $\gamma$ fraction of the
available $M$ links is chosen for rewiring,

$f_{rewire}(t)=\gamma(M-f_{add}(t))=\gamma(1-\beta)M$

  3. (iii)

Final fraction of the remaining segment of $M$ are used for deleting the most
infrequently used links.

$f_{delete}(t)=M-f_{add}(t)-f_{rewire}(t)=(1-\gamma)(1-\beta)M$

###  3.2 Proposed Fair End to End Window Based Model

A TVCN is designed by using the proposed model. An end to end connection is
established between user’s source and destination. There exist multiple paths
from user’s source to destination nodes but among all those connections, the
shortest route(s) is (are) chosen for data communication. Initially, user $i$
wants to send $w_{i}$ number of packets but an actual number of packets in
user’s route are the sum of packets in transit (on the route) and the total
number of packets waiting in the queue. At each time instant, few packets are
forwarded towards their destination node hence, each user updates its current
window size. Users’ preferences are implicitly reflected in the window size
updating rule. An end to end window-based congestion control formulation is
required to get a fair rate vector. Max-min fairness is not suitable for time-
varying networks and it is more focused on fairness rather than the system
utility maximization. In real-world networks, we are interested to maximize
the system utility. Hence, $(p,\alpha)$ proportionally fair allocation for
rate vector of each user is considered. Here, the value of $\alpha$ may be any
positive number.

Delays play an important role in finding congestion in the network as
congestion is directly proportional to the delays. There are various types of
delays in communication networks: transmission delay, propagation delay,
queuing delay etc. A snapshot of all the delays are shown in Figure 1. The
transmission delay is defined by the amount of time required for the node to
push out the packet. If the length of each packet is $\mathtt{L}$ bits, and
the transmission rate of the link from first node to second node is $r_{tran}$
bits/sec, then transmission delay $(d_{trans})$ is denoted by,
$d_{trans}=\frac{\mathtt{L}}{r_{tran}}$ and it depends upon transmission rate
$(r_{tran})$ of the link and length, $L$. The propagation delay $(d_{prop})$
is the time to propagate a bit from one node to other. If the distance between
two nodes is $\delta$ and the propagation rate is $r_{prop}$, then the
propagation delay is $d_{prop}=\frac{\delta}{r_{prop}}$. It is a function of
the distance between the two nodes, but does not share the dependency on $L$
and $r_{tran}$ of the link. Queuing delay $(d_{Q})$ depends on number of
packets waiting in a queue. Total delay $D^{i}$ for the user $i$ is the sum of
propagation delay $d_{prop}^{i}$, transmission delay $d_{trans}^{i}$ and
queuing delay $d_{Q}^{i}$ for that user.

Figure 1:  Network Delays

It is hard to know for end users about the fair share of the network resources
among the users. The fair share not only depends on the users but also the
network structure. Each user does not aware of the behavior of other users.
Hence, it is important to introduce a formulation where the user can achieve
fairness without considering the behavior of other users. Let,
$w_{i}(t),x_{i}(t),d_{trans}^{i}(t)$ and $p_{i}(t)$ represent the window size,
data sending rate, transmission delay and willingness to pay of user $i$,
respectively at time $t$. The actual backlog at user $i$ may be defined as,

$s_{i}(t)=w_{i}(t)-x_{i}(t)d_{trans}^{i}(t)-p_{i}(t),\mbox{ for }i\in R.$

Where, second term on the right-hand side of the equation provides the total
number of packets transmitted through the route of user $i$ in one round.
$w_{i}(t)$ is the total number of packets in the route of user $i$. $p_{i}(t)$
is willingness to pay for user $i$ at time $t$. A time varying cost is chosen
by the user $i$ for the queue size of resources which appears in the route of
that user at time $t$. User $i$ is able to change its willingness to pay
$p_{i}(t)$ according to its rate $x_{i}(t)$ as,

$p_{i}(t)=x_{i}(t)U^{\prime}_{i}(x_{i}(t)),\mbox{ for }i\in R.$ (6)

Where, $U^{\prime}_{i}(x_{i}(t))$ is the first derivative of the utility
function and is used to check whether the utility function is increasing or
decreasing. Suppose a resource is heavily loaded with packets then the charge
per unit flow through that resource will be high and user has to pay more. If
user pays more then it may get high data sending rate, $x_{i}(t)$. Hence, rate
allocation is proportional to $p_{i}(t)$ and is considered as $(p,1)$\-
proportionally fair. The expression $x_{i}(t)d_{trans}^{i}(t)-p_{i}(t)$ states
the sum of the packets of user $i$ which can send through the route and the
total number of packets of user $i$ which may store in the queue at the
destination node. Therefore, the expression,
$w_{i}(t)-x_{i}(t)d_{trans}^{i}(t)-p_{i}(t)$ will provide the total number of
backlogged packets in the route of user $i$. The choice for selecting the
window size, $w_{i}(t)$ of user $i$ which makes $s_{i}(t)\approx 0$ is
considered as $(p_{i},1)$-proportionally fair. User $i$ needs to send
$w_{i}(t)$ packets while total delay is $D^{i}(t))$ hence, total time taken is
$w_{i}(t)D^{i}(t)$. But, total time to transmit backlogged packets, $s_{i}(t)$
in one round is $s_{i}(t)d_{trans}^{i}(t)$. Therefore, the fraction of packets
that may be sent in one round is
$\frac{d_{trans}^{i}(t)s_{i}(t)}{D^{i}(t)w_{i}(t)}$. The rate equation that is
used by the user to update its window size is,

$\frac{dw_{i}(t)}{dt}=-\kappa f_{i}(d,t)f_{i}(w,t).$ (7)

Where,

$f_{i}(d,t)=\frac{d_{trans}^{i}(t)}{D^{i}(t)},$

here, $\kappa$ is a scaling parameter, $\kappa>0$. Queuing delay,
$d_{Q}^{i}(t)=\sum_{i:j\in R_{i}}\left(\frac{\sum_{z:j\in
R_{z}}x_{z}(t)}{C_{j}}\right)$ depends on number of packets in the queue and
the route of user $i$. If the incoming rate of the packet is $\lambda_{j}(t)$
bits at node $j$, and the transmission rate of the user $i$ is $min_{1\leq
k\leq|R_{i}|}C_{j}$ bits/sec, then transmission delay $(d_{trans})$ is denoted
by $d_{trans}^{i}(t)=\frac{\sum_{j\in
R_{i}}\lambda_{j}(t)}{min_{1\leq<k\leq|R_{i}|}C_{j}}$ and function
$f_{i}(w,t)$ is defined as,

$f_{i}(w,t)=\frac{w_{i}(t)-x_{i}(t)d_{trans}^{i}(t)-x_{i}(t)U^{\prime}_{i}(x_{i}(t))}{w_{i}(t)}.$

If resource (link) $j$ appears in the route of large number of users then the
number of packets at that resource will increase rapidly which makes the node
congested. Hence, transmission delay and queuing delay will increase
accordingly.

To check the stability of the the differential Eq. (7), a Lyapunov function
$V(w)=\frac{1}{2}\sum_{i}{f_{i}(w)^{2}}$ (a function of $w$) is defined. As
Lyapunov function directly or indirectly depends only on one control input
i.e, window size hence, quadratic form of the function $f_{i}(w)$ may provide
the solution. The following theorem depends on Eq. (7) and states that
$w_{i}(t)$ converges to the unique stable point, where the optimal window
size, $w_{i}^{*}$ and optimal rate, $x_{i}^{*}$ solves the aggregate system
utility $\sum_{i\in R}U_{i}(x_{i})$.

######  Theorem 3.1.

Let $V(w)=\frac{1}{2}\sum_{i}{f_{i}(w)^{2}}$
$V(w)$ is a Lyapunov function for the system of differential Eq. (7). The
unique value minimizing $V(w)$ is stable point of this system where all
trajectories converge.

Proof:
A Lyapunov function is a convex function and hence, the stable value of window
size $w(t)$ may lie either on boundary or within interior region. $w(t)$ is an
interior point if for any small value of $\epsilon>0$, $w(t+\epsilon)$ must
lie in the same region as $w(t)$ otherwise, $w(t)$ is considered as boundary
point. Now consider both the cases.
Case 1: Interior point

$\displaystyle\frac{dV(w(t))}{dt}={}$
$\displaystyle\frac{1}{2}\sum_{j}\frac{dV}{dw_{j}}\frac{dw_{j}(t)}{dt}$ (8)
$\displaystyle={}$
$\displaystyle\frac{1}{2}\sum_{j}\sum_{i}\frac{d(f_{i}(w))^{2}}{dw_{j}}\dot{w_{j}}$
$\displaystyle={}$
$\displaystyle-k\sum_{j}\sum_{i}f_{i}(w)\frac{df_{i}}{w_{j}}\dot{w_{j}}$
$\displaystyle={}$ $\displaystyle-kf(w)^{T}J_{f}\dot{w}.$

Where,
$J_{f}=\frac{df}{dw}=(d_{trans}+U^{\prime})D^{-2}A(A^{T}XD^{-1}A)^{-1}A^{T}D^{-1}$
(Jacobian of function $f$ with respect to $w$ and proof is given in Appendix
A). $\dot{w}=f(d)f(w)=d_{trans}D^{-1}f(w)$. By using all these values, Eq. (8)
can be written as,

$\displaystyle\frac{dV(w(t))}{dt}={}$ $\displaystyle-
kf(w)^{T}\left((d_{trans}+U^{\prime})D^{-2}A(A^{T}XD^{-1}A)^{-1}A^{T}D^{-1}\right)\left(d_{trans}D^{-1}f(w)\right)$
(9) $\displaystyle={}$ $\displaystyle-
kf(w)^{T}\left[(d_{trans}+U^{\prime})D^{-2}A(A^{T}XD^{-1}A)^{-1}A^{T}D^{-1}\right]\left(d_{trans}D^{-1}f(w)\right)$
$\displaystyle={}$ $\displaystyle-
kf(w)^{T}\left[(d_{trans}+U^{\prime})D^{-2}AA^{-1}DX^{-1}(A^{T})^{-1}A^{T}D^{-1}\right]\left(d_{trans}D^{-1}f(w)\right)$
$\displaystyle={}$ $\displaystyle-
kf(w)^{T}\left[(d_{trans}+U^{\prime})D^{-2}X^{-1}d_{trans}D^{-1}\right]f(w)$
$\displaystyle={}$ $\displaystyle-kf(w)^{T}Qf(w).$

Here, $Q=\left[(d_{trans}+U^{\prime})D^{-2}X^{-1}d_{trans}D^{-1}\right]$,
$d_{trans}=diag(d_{trans}^{i}(t))$,
$U^{\prime}=diag(U^{\prime}_{i}(x_{i}(t)))$, $D=diag(D_{i}(t))$ and
$X=diag(x_{i}(t))$.

The inverse of a rectangular matrix cannot be calculated. Hence, first we need
to convert matrix $A$ into a square matrix by adding some vectors from a basis
for $\mathbb{R}^{RE}$. The matrix, $Q$ in the bracket of Eq. (9) is positive
definite (the proof is provided in Appendix B). The overall value of Eq. (9)
is negative and hence, $V(w(t))$ is strictly decreasing in $t$ on interior
points.

Case 2: Boundary point
Jacobian matrix $J_{x}$ can be defined only for the interior points but it may
be extended to boundary points in the form of feasible direction $\bar{d}$. A
vector $\bar{d}\in\mathbb{R}^{n},\bar{d}\neq 0$, is called a feasible
direction at time $t$ if there exist $\epsilon_{0}>0$ such that $t$ and
$t+\epsilon d$ belong to same bottleneck set for all
$\epsilon\in[0,\epsilon_{0}]$.

## Results and Analysis

The simulation is set by constructing the time varying network according to
the TVCN model proposed in Section 3.1. The proposed TVCN model is an example
of real world networks, hence, degree distribution must follow power law
distribution, $P(k)\sim k^{-\alpha}$, where $2<\alpha\leq 3$. The parameters
are set to be seed node $n_{0}=5$, number, $M=5$, fraction of newly added
links $\beta$ in the range $(0,1)$, fraction of rewired links $\gamma$ is in
the range $(0.5,1)$, with network size ranging from $N=s\times 10^{2}$ to
$N=3.5\times 10^{3}$. Any node may be in the user’s $(S,D)$ sets or
participate in routing also. Data forwarding capacity of a node $n$, $C_{n}$
is defined by the degree $k_{n}$ of the node $n$. Capacity of a link
$C_{e_{mn}}$ is obtained by multiplying the degrees $k_{m}$ and $k_{n}$ of end
nodes $m$ and $n$, respectively. At each time stamp, degree of the nodes will
be different, hence capacity of the nodes as well as links change accordingly.
We demonstrate the convergence of users’ parameters ($w(t),(f(w))^{2}$) with
utility function, $U_{i}(x_{i}(t))=a_{i}log(x_{i}(t)+b_{i})$, $a_{i}>0$ and
$0\leq b_{i}\leq 1$, through simulations and study the behavior of $w^{*}$ for
time varying network. We study the behavior of all the window update (La’s ans
Mo’s) approaches on the networks designed by the time varying communication
network model and compare with the proposed approach.

While the connection is established between user’s source and destination
pairs, initial value number of packets in window, $w(0)$ is calculated by
summing up the packets which are in transit as well as in queue on the
resources which appear in user’s route. Window size is adjusted with time and
finally it converges to unique stable point $w^{*}$. Simulation is run for
$15000$ iteration and convergence of window size for four users are mentioned
in Table 1. The value of scaling parameter, $k$, may be any positive number.
Here, in the paper it is fixed as $0.1$ and each user’s data sending amount is
fixed as $10Mb$. $w(0)$ of User $1-4$ are evaluated as $25.1012\mbox{
}Mb,15.2063\mbox{ }Mb,20.4796\mbox{ }Mb$ and $35.6423\mbox{ }Mb$,
respectively. These values are taken as input for all approaches (the
proposed, La’s [20] and Mo’s [5]). In the proposed method, the value of
$w_{i}(t)$ depends on the delays ($d_{prop}^{i}$, $d_{Q}^{i}(t)$ and
$d_{trans}^{i}(t)$), $s_{i}(t)$, willingness to pay $p_{i}(t)$ and previous
window size $w_{i}(t-1)$ for user $i$. $w_{i}(t)$ will decrease exponentially
with time and the value of $w_{i}(t)$ makes $s_{i}(t)\approx 0$, is termed as
optimal window size $w_{i}^{*}$ of the user $i$. As the window updates the
equations for all the approaches are different hence, convergence rate will be
different with difference in the value of $w_{i}^{*}$. Mo’s approach gives the
value of $w^{*}$ for all the users; User $1-4$ as $3.2378\mbox{
}Mb,15.2946\mbox{ }Mb,5.2962\mbox{ }Mb$ and $9.9753\mbox{ }Mb$, respectively.
La’s approach gives the value of $w^{*}$ of all users; User $1-4$ as
$1.3471\mbox{ }Mb,7.7192\mbox{ }Mb,2.0598\mbox{ }Mb$ and $2.0986\mbox{ }Mb$,
respectively. By using the proposed approach, User $1-4$ get $w^{*}$ values as
$1.3568\mbox{ }Mb,7.8302\mbox{ }Mb,2.0746\mbox{ }Mb$ and $2.1107\mbox{ }Mb$,
respectively. Window update equation keeps changing dynamically with the
varying value of transmission delay, $d_{trans}(t)$ unlike, propagation delay,
$d_{prop}$ in La’s and Mo’s, which was static. The proposed approach provides
a unique stable value of window size, $w^{*}$ as in La’s approach and is quite
approximate to the value obtained through static (La’s) approach. Mo’s
approach uses both propagation and queuing delays as static and it assumes
less number of packets in queue irrespective of large number of incoming
packets in the network hence, provides higher value of $w^{*}$. The proposed
method provides dynamicity in the previous approaches by updating the window
size based on transmission delay and gets stable value of window size,
$w^{*}$.

Table 1: Comparative study of the convergence of values of window size, $w$
obtained through proposed, Mo’s and La’s approaches, when network size
$N=2500$.

Time Proposed Mo La User1 User2 User3 User4 User1 User2 User3 User4 User1
User2 User3 User4 $0$ $25.1012$ $15.2063$ $20.4796$ $35.6423$ $25.1012$
$15.2063$ $20.4796$ $35.6423$ $25.1012$ $15.2063$ $20.4796$ $35.6423$ $1000$
$11.3987$ $13.0505$ $10.7814$ $22.7718$ $7.8069$ $15.2946$ $8.8397$ $24.1478$
$4.6878$ $10.5919$ $4.0879$ $14.3736$ $2000$ $2.9560$ $11.3053$ $4.7454$
$11.8962$ $3.2514$ $15.2946$ $5.4114$ $14.9804$ $1.3500$ $8.5821$ $2.0806$
$2.8991$ $3000$ $1.4584$ $10.1034$ $2.6813$ $5.6193$ $3.2379$ $15.2946$
$5.2987$ $11.0237$ $1.3471$ $7.9628$ $2.0600$ $2.1177$ $4000$ $1.3622$
$9.2974$ $2.1964$ $3.1047$ $3.2378$ $15.2946$ $5.2964$ $10.1366$ $1.3471$
$7.7866$ $2.0598$ $2.0992$ $5000$ $1.3571$ $8.7681$ $2.0983$ $2.3619$ $3.2378$
$15.2946$ $5.2963$ $9.9978$ $1.3471$ $7.7377$ $2.0598$ $2.0986$ $6000$
$1.3568$ $8.4257$ $2.0791$ $2.1720$ $3.2378$ $15.2946$ $5.2962$ $9.9784$
$1.3471$ $7.7243$ $2.0598$ $2.0986$ $7000$ $1.3568$ $8.2067$ $2.0754$ $2.1255$
$3.2378$ $15.2946$ $5.2962$ $9.9757$ $1.3471$ $7.7206$ $2.0598$ $2.0986$
$8000$ $1.3568$ $8.0674$ $2.0747$ $2.1143$ $3.2378$ $15.2946$ $5.2962$
$9.9753$ $1.3471$ $7.7196$ $2.0598$ $2.0986$ $9000$ $1.3568$ $7.9794$ $2.0746$
$2.1116$ $3.2378$ $15.2946$ $5.2962$ $9.9753$ $1.3471$ $7.7193$ $2.0598$
$2.0986$ $10000$ $1.3568$ $7.9239$ $2.0746$ $2.1109$ $3.2378$ $15.2946$
$5.2962$ $9.9753$ $1.3471$ $7.7192$ $2.0598$ $2.0986$ $11000$ $1.3568$
$7.8890$ $2.0746$ $2.1108$ $3.2378$ $15.2946$ $5.2962$ $9.9753$ $1.3471$
$7.7192$ $2.0598$ $2.0986$ $12000$ $1.3568$ $7.8446$ $2.0746$ $2.1107$
$3.2378$ $15.2946$ $5.2962$ $9.9753$ $1.3471$ $7.7192$ $2.0598$ $2.0986$
$13000$ $1.3568$ $7.8302$ $2.0746$ $2.1107$ $3.2378$ $15.2946$ $5.2962$
$9.9753$ $1.3471$ $7.7192$ $2.0598$ $2.0986$ $14000$ $1.3568$ $7.8302$
$2.0746$ $2.1107$ $3.2378$ $15.2946$ $5.2962$ $9.9753$ $1.3471$ $7.7192$
$2.0598$ $2.0986$ $15000$ $1.3568$ $7.8302$ $2.0746$ $2.1107$ $3.2378$
$15.2946$ $5.2962$ $9.9753$ $1.3471$ $7.7192$ $2.0598$ $2.0986$

In the communication networks, multiple paths are available for sending
packets for each user, between the desired source and destination. Among all
the available paths, users select the shortest path to reach the destination
with a maximum flow rate of individual links for data communication. The data
sending rate $x$ is reduced as multiple users want to share the common
resources. With the varying size of the network $N$ (from $N=5\times 10^{2}$
to $N=3.5\times 10^{3}$), shortest route of the user will also change. Routes
of the users may be same or vary at different time instants. It depends on the
availability of the resources.

User’s window size depends on two parameters; total number of packets in
transit and queue. Using window update theorem (Eq. (2)), $w^{*}$ of each user
is shown in Table 2. The size of the network, $N$ is varying but the number of
users is kept same as in initial network. Here, initial size of the network is
considered as $N=5\times 10^{2}$ and it ranges up to $N=3.5\times 10^{3}$
where, $\Delta N=5\times 10^{2}$ (Table 2). The size of the network increases
but $w(t)$ decreases to a stable point $w^{*}$. User’s window size depends on
the demand of particular resources appearing in the shortest route. If demand
is high then window size and data sending rate will be less. When $N$ is
changing then, user’s route, data flow rate $x$ through the path and $w^{*}$
will also change accordingly. Optimal window size, $w^{*}$ for users are
independently changing and in some cases $w^{*}$ obtained through proposed
approach is higher/lower than La’s. But, Mo’s approach uses more static
approach and analyze less congestion in the network.

Table 2: Comparative study of the values of optimal window size $w^{*}$
obtained through proposed, La’s and Mo’s approaches, for different values of
network size $N$.

Users Network Size $(N)$ Approaches $500$ $1000$ $1500$ $2000$ $2500$ $3000$
$3500$ Proposed $5.0157$ $9.0963$ $4.1568$ $5.4256$ $1.3568$ $8.7011$ $6.4785$
User 1 La’s $4.9549$ $4.9549$ $4.1032$ $5.2499$ $1.3472$ $8.5732$ $6.0885$
Mo’s $12.5436$ $14.0656$ $16.0440$ $9.4742$ $3.2378$ $27.9147$ $4.8265$
Proposed $2.2173$ $0.6899$ $2.6955$ $1.9178$ $7.8302$ $3.0075$ $0.9175$ User 2
La’s $2.1135$ $2.1135$ $2.6547$ $1.7302$ $7.7192$ $2.9698$ $0.9153$ Mo’s
$8.5779$ $5.2688$ $5.4462$ $1.1634$ $15.2946$ $12.0407$ $4.3771$ Proposed
$5.9961$ $2.7512$ $4.9292$ $7.8832$ $2.0746$ $1.8750$ $2.1889$ User 3 La’s
$5.9337$ $5.9337$ $4.8319$ $7.7533$ $2.0598$ $1.8367$ $1.2650$ Mo’s $12.0888$
$1.9225$ $11.3823$ $11.4005$ $5.2962$ $3.3067$ $8.2767$ Proposed $0.8467$
$1.7196$ $5.0519$ $1.0817$ $2.1107$ $1.3798$ $1.2145$ User 4 La’s $0.8455$
$0.8455$ $5.0073$ $1.0773$ $2.0986$ $1.3743$ $1.2112$ Mo’s $7.0850$ $13.6237$
$12.8835$ $6.8177$ $9.9753$ $6.3977$ $8.1358$

A comparative study of optimal window size, $w^{*}$ of three users; User1,
User2 and User3 are shown by using red, black and cyan lines with different
markers (Figure 2). La’s and proposed approaches give approximate values of
$w^{*}$ while Mo’s approach considers more static approach and gives higher
value of $w^{*}$ for each user.

Figure 2:  Comparative study of the values of $w^{*}$ obtained through
proposed, La’s and Mo’s approaches, for the network size $N=\\{5\times
10^{2}$, $1\times 10^{3}$ … , $3.5\times 10^{3}\\}$.

The window size vector $w(t)$ is said to be $(p,1)$ proportionally fair rate
vector $x$ if $s_{i}(t)\approx 0$ for all $i$ and the unique value minimizing
$V(w)$ is stable point of this system. Figure 3 shows convergence of
$V(w)=\frac{f_{i}(w)^{2}}{2}$ for $4$ users when size of the network
$N=3\times 10^{4}$. Initially, the difference between actual and targeted
backlog, $s_{i}$ for user $i$ is high hence, $V(w)$ is also high. But it
decreases independently and exponentially with time and finally, it becomes
approximately zero, like $s_{i}$.

Figure 3: convergence of user’s $\frac{f_{i}(w)^{2}}{2}$ value, when
$N=3\times 10^{4}$.

In window update equation (Eq. (5)), La added dynamic terms
($U^{\prime}_{i}(x_{i}(t))+x_{i}(t)U^{\prime\prime}_{i}(x_{i}(t))$) to the
propagation delay $(d_{prop})$ which will always be positive and depends on
the dynamic rate and corresponding user’s utility function. We have divided
La’s approach into two parts: (i) with the consideration of dynamic terms and
(ii) without the consideration of dynamic terms (LaWD approach). It is found
that both the approaches converge to the same value of stable window size,
$w^{*}$. But, the computation complexity in the convergence of window size is
different for both the approaches and is shown in Table 3. The configuration
of the system is given as Intel $R$ Xeon (R) CPU E5-$2620$ v2 @ $2.10$ GHz
$2.10$ GHz with memory size $8.00$ GB. The average value of the computation
complexity for different values of the network size, $N$ is calculated to
check the speed up of the proposed approach with other approaches. Total
computation time for obtaining $w^{*}$ depends upon the network topology and
the total number of congested resources. Different network structures with the
same number of nodes and resources (links) take a different amount of time to
get optimal window size. The simulation is run for $10$ times and finally, an
average value is considered as computation time. The proposed approach is
approximately $23,33$ and $24$ times faster than the Mo’s, La’s and La without
Dynamic terms (LaWD) approaches, respectively.

Table 3: Comparative study of the computation complexity (in Seconds) analysis
to obtain $w^{*}$ through proposed, Mo’s, La’s and LaWD’s approaches, for
different size of network $N$.

Network size $(N)$ Proposed Mo La LaWD time taken (in seconds) for optimal
window size $(w^{*})$ $500$ $281.4865$ $1.2660\times 10^{3}$ $2.9717\times
10^{3}$ $2.5891\times 10^{3}$ $1000$ $279.2723$ $7.4122\times 10^{3}$
$2.9577\times 10^{3}$ $2.7117\times 10^{3}$ $1500$ $484.9320$ $6.7600\times
10^{3}$ $1.3749\times 10^{4}$ $1.3954\times 10^{4}$ $2000$ $744.9612$
$2.2145\times 10^{4}$ $3.6035\times 10^{4}$ $1.2091\times 10^{4}$ $2500$
$461.6515$ $1.2812\times 10^{4}$ $1.8069\times 10^{4}$ $1.5984\times 10^{4}$
$3000$ $243.9001$ $1.3780\times 10^{4}$ $9.3088\times 10^{3}$ $8.4913\times
10^{3}$ $3500$ $550.8467$ $6.9841\times 10^{3}$ $1.6396\times 10^{4}$
$1.6720\times 10^{4}$

## Conclusion and Future Directions

A framework is designed to represent time-varying communication networks
(TVCN). We have shown the existence of window based fair end to end congestion
control scheme using a multi-class fluid based model. $(p,1)$ proportionally
fairness is used to formulate an optimization problem. According to the
willingness for pay, $(p_{i})$ of each user, an optimal window size is
allocated such that congestion is minimized as well as system utility is
maximized. The window-based update algorithm is proposed by considering
dynamic delay especially, transmission delay $d_{trans}(t)$. It is observed
that we are still getting a stable value of window size $w^{*}$ which is
approximately same as the result obtained through La’s approach [20]. While,
Mo’s approach [5] considers static delay hence, overestimates the value of
optimal window size, $W^{*}$. Convergence of the proposed window-based
congestion control scheme is proved by using a Lyapunov function, $V(w)$. For
the same network topology, the converged window size, $w^{*}$ is obtained in
the least amount of time through the proposed scheme. The network is time-
varying therefore, User’s optimal window size, $w^{*}$ is evaluated for the
varying sizes of networks and we may get a different value of $w^{*}$ due to
change in route of each user.

In future work, the proposed study will be extended to provide good QoS
(Quality of Service) by considering error rates, robustness, data transmission
within budget etc. The concept of multi-path routing can be used for data
transmission of each user.

## References

  * [1] M. Newman, A.-L. Barabasi, D. J. Watts, The structure and dynamics of networks, Princeton University Press, 2011.
  * [2] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D.-U. Hwang, Complex networks: Structure and dynamics, Physics reports 424 (4) (2006) 175–308.
  * [3] F. P. Kelly, Mathematical modelling of the internet, Mathematics unlimited-2001 and beyond (2001) 685–702.
  * [4] R. J. La, V. Anantharam, Utility-based rate control in the internet for elastic traffic, IEEE/ACM Transactions on Networking (TON) 10 (2) (2002) 272–286.
  * [5] J. Mo, J. Walrand, Fair end-to-end window-based congestion control, IEEE/ACM Transactions on Networking (ToN) 8 (5) (2000) 556–567.
  * [6] A.-L. Barabási, R. Albert, H. Jeong, Mean-field theory for scale-free random networks, Physica A: Statistical Mechanics and its Applications 272 (1) (1999) 173–187.
  * [7] K. Wehmuth, A. Ziviani, E. Fleury, A unifying model for representing time-varying graphs, in: Data Science and Advanced Analytics (DSAA), 2015. 36678 2015. IEEE International Conference on, IEEE, 2015, pp. 1–10.
  * [8] A. Casteigts, P. Flocchini, W. Quattrociocchi, N. Santoro, Time-varying graphs and dynamic networks, International Journal of Parallel, Emergent and Distributed Systems 27 (5) (2012) 387–408.
  * [9] B. B. Xuan, A. Ferreira, A. Jarry, Evolving graphs and least cost journeys in dynamic networks, in: WiOpt’03: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, 2003, pp. 10–pages.
  * [10] J. Saldaña, Continuum formalism for modeling growing networks with deletion of nodes, Physical Review E 75 (2) (2007) 027102.
  * [11] T. Carletti, F. Gargiulo, R. Lambiotte, Preferential attachment with partial information, The European Physical Journal B 88 (1) (2015) 18.
  * [12] S. Kumari, A. Singh, P. Ranjan, Towards a framework for rate control on dynamic communication networks, in: Proceedings of the International Conference on Internet of things and Cloud Computing, ACM, 2016, p. 12.
  * [13] X. Chen, M.-A. Belabbas, T. Başar, Controllability of formations over directed time-varying graphs, IEEE Transactions on Control of Network Systems 4 (3) (2017) 407–416.
  * [14] C. Joe-Wong, S. Sen, T. Lan, M. Chiang, Multiresource allocation: Fairness-efficiency tradeoffs in a unifying framework, IEEE/ACM Transactions on Networking (TON) 21 (6) (2013) 1785–1798.
  * [15] A. Sivaraman, K. Winstein, P. Thaker, H. Balakrishnan, An experimental study of the learnability of congestion control, in: ACM SIGCOMM Computer Communication Review, Vol. 44, ACM, 2014, pp. 479–490.
  * [16] J. Padhye, V. Firoiu, D. F. Towsley, J. F. Kurose, Modeling tcp reno performance: a simple model and its empirical validation, IEEE/ACM Transactions on Networking (ToN) 8 (2) (2000) 133–145.
  * [17] J. Mo, R. J. La, V. Anantharam, J. Walrand, Analysis and comparison of tcp reno and vegas, in: INFOCOM’99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, Vol. 3, IEEE, 1999, pp. 1556–1563.
  * [18] L. S. Brakmo, L. L. Peterson, Tcp vegas: End to end congestion avoidance on a global internet, IEEE Journal on selected Areas in communications 13 (8) (1995) 1465–1480.
  * [19] C. Jin, D. Wei, S. H. Low, J. Bunn, H. D. Choe, J. C. Doylle, H. Newman, S. Ravot, S. Singh, F. Paganini, et al., Fast tcp: From theory to experiments, IEEE network 19 (1) (2005) 4–11.
  * [20] R. J. La, V. Anantharam, Utility-based rate control in the internet for elastic traffic, IEEE/ACM Transactions On Networking 10 (2) (2002) 272–286.
  * [21] S. H. Low, A duality model of tcp and queue management algorithms, IEEE/ACM Transactions On Networking 11 (4) (2003) 525–536.
  * [22] J. Ye, K.-C. Leung, V. O. Li, S. H. Low, Combating bufferbloat in multi-bottleneck networks: Equilibrium, stability, and algorithms, Tech. rep., Technical Report TR-2018-001, Dept. of EEE, HKU (2018).
  * [23] A. P. Silva, S. Burleigh, C. M. Hirata, K. Obraczka, A survey on congestion control for delay and disruption tolerant networks, Ad Hoc Networks 25 (2015) 480–494.
  * [24] G. Carofiglio, M. Gallo, L. Muscariello, Optimal multipath congestion control and request forwarding in information-centric networks: Protocol design and experimentation, Computer Networks 110 (2016) 104–117.
  * [25] Q. Chen, D. Shi, The modeling of scale-free networks, Physica A: Statistical Mechanics and its Applications 335 (1) (2004) 240–248.
  * [26] F. Chung, L. Lu, T. G. Dewey, D. J. Galas, Duplication models for biological networks, Journal of computational biology 10 (5) (2003) 677–687.
  * [27] S. KUMARI, A. SINGH, Time-varying network modeling and its optimal routing strategy, Advances in Complex Systems 20 (2017) 1850006.
  * [28] D. Nace, M. Pióro, Max-min fairness and its applications to routing and load-balancing in communication networks: a tutorial, IEEE Communications Surveys & Tutorials 10 (4).
  * [29] S. Kumari, A. Singh, Modeling of data communication networks using dynamic complex networks and its performance studies, Complex Networks & Their Applications V (2017) 29.

## Appendix A

A Lyapunov function $V(w)$ can be used to find an output error and/or size of
a state, deviation from true parameter, energy difference from desired
equilibrium point or it may be the combination of the above. Lyapunov function
is decreasing with time (continuous or discrete) hence, we need to choose some
suitable control equation such that $\frac{dV(w(t))}{dt}\leq 0$ and it should
be minimum.

######  Theorem 3.2.

Let $V(w)=\frac{1}{2}\sum_{i}f_{i}(w)^{2}$
$V(w)$ is a Lyapunov function for the system of differential Eq. (7). The
unique value minimizing $V(w)$ is stable point of this system where all
trajectories converge.

Define

$\displaystyle J_{x}=\left[\frac{\partial x_{i}}{\partial w_{j}},\mbox{
}i,j\in\mathcal{N}\right],$ $\displaystyle J_{q}=\left[\frac{\partial
q_{i}}{\partial w_{j}},\mbox{ }i\in\mathcal{L},j\in\mathcal{N}\right]$

$J_{x}$ and $J_{q}$ are considered as changes in rate and queue size with
respect to the window size $w$. All congested links are considered to solve
the Lyapunov function $V(w)$ and these congested links are collectively stored
in a set $B$. A sub-matrix $A_{B}$ of matrix $A$ is formed by considering only
congested links.

######  Lemma 3.3.

The Jacobian $J_{x}$ of $x(w)$ with respect to $w$ is given by following
expression on the interior point:

$J_{x}=D^{-1}\left(I-XA_{B}(A_{B}^{T}XD^{-1}A_{B})^{-1}A_{B}^{T}D^{-1}\right)$
(10)

Proof:

$\displaystyle
D=diag\left[(d_{P})_{i}+Ad_{trans}^{i}(t)+A(d_{Q}^{t})_{i}\right]$
$\displaystyle X=diag(x_{i},\mbox{ }i\in\mathcal{N})$

To calculate $J_{x}$, only congested links are considered and hence, the
equation will be

$\displaystyle
x_{i}\left[(A_{B}{d_{Q}}_{B})_{i}+(A_{B}{d_{T}}_{B})_{i}+(d_{P})_{i}\right]=w_{i},\mbox{
}i\in B$ (11) $\displaystyle A^{T}x=C$ (12)

Now, taking partial derivative of Eq. (16) with respect to $w_{j}$ and
avoiding subscript $B$ for calculation

$\displaystyle\frac{\partial(x_{i}\left[(Ad_{Q})_{i}+(Ad_{trans})_{i}+(d_{prop})_{i}\right]}{\partial
w_{j}}=\frac{\partial w_{i}}{w_{j}}$ $\displaystyle\frac{\partial
x_{i}}{\partial
w_{j}}\left[(Ad_{Q})_{i}+(Ad_{trans})_{i}+(d_{prop})_{i}\right]+x_{i}\left[A_{i}\frac{\partial(d_{Q})_{i}}{\partial
w_{j}}\right]=\delta_{ij}$
$\displaystyle(D)_{i}(J_{x})_{ij}+x_{i}A_{i}(J_{q})_{ij}=\delta_{ij}$

Now this can be written in matrix form as

$DJ_{x}+XAJ_{q}=I$ (13)

Multiplying both side by $A^{T}D^{-1}$

$A^{T}J_{x}+\left(A^{T}D^{-1}XA\right)J_{q}=A^{T}D^{-1}$ (14)

From Eq. (12) $A^{T}J_{x}=0$, hence

$J_{q}=\left(A^{T}D^{-1}XA\right)^{-1}A^{T}D^{-1}$ (15)

Now, putting Eq. (15) into Eq. (13), we get

$\displaystyle DJ_{x}+XA\left(A^{T}D^{-1}XA\right)^{-1}A^{T}D^{-1}=I$
$\displaystyle
J_{x}=D^{-1}\left(I-XA\left(A^{T}D^{-1}XA\right)^{-1}A^{T}D^{-1}\right)$

######  Lemma 3.4.

The Jacobian $J_{f}$ of $f(w)$ with respect to $w$ is given by following
expression on the interior point:

$J_{f}=(d_{trans}+U^{\prime})D^{-2}A(A^{T}XD^{-1}A)^{-1}A^{T}D^{-1}$ (16)

Proof:

$\displaystyle J_{f}={}$ $\displaystyle\frac{\partial f}{\partial
w}=\frac{\partial\left(1-\frac{x_{i}d_{trans}^{i}}{w_{i}}-\frac{x_{i}U^{\prime}_{i}(x_{i}))}{w_{i}}\right)}{\partial
w_{j}}$ (17) $\displaystyle={}$
$\displaystyle-(J_{x})_{ij}d_{trans}^{i}w_{i}^{-1}+x_{i}d_{trans}^{i}w_{i}^{-2}-(J_{x})_{ij}U^{\prime}_{i}(x_{i})w_{i}^{-1}+x_{i}U^{\prime}_{i}(x_{i})w_{i}^{-2}.$

Now, the above equation can be written in matrix form as,

$\displaystyle J_{f}={}$ $\displaystyle
Xd_{trans}W^{-2}+XU^{\prime}W^{-2}-\left(d_{trans}W^{-1}+W^{-1}U^{\prime}\right)J_{x}$
(18) $\displaystyle={}$ $\displaystyle
Xd_{trans}W^{-2}+XU^{\prime}W^{-2}-\left(d_{trans}W^{-1}+W^{-1}U^{\prime}\right)\left(D^{-1}-D^{-1}XA\left(A^{T}D^{-1}XA\right)^{-1}A^{T}D^{-1}\right)$
$\displaystyle={}$ $\displaystyle
Xd_{trans}W^{-2}+XU^{\prime}W^{-2}-d_{trans}W^{-1}D^{-1}-W^{-1}U^{\prime}D^{-1}+\left(d_{trans}+U^{\prime}\right)W^{-1}D^{-1}XA\left(A^{T}D^{-1}XA\right)^{-1}A^{T}D^{-1}$

Where, $X=WD^{-1}$. Hence, the starting four terms of Eq. (18) will be
canceled out and it can be rewritten as,

$\displaystyle J_{f}={}$
$\displaystyle\left(d_{trans}+U^{\prime}\right)W^{-1}D^{-1}XA\left(A^{T}D^{-1}XA\right)^{-1}A^{T}D^{-1}$
(19) $\displaystyle={}$
$\displaystyle\left(d_{trans}+U^{\prime}\right)D^{-2}A\left(A^{T}D^{-1}XA\right)^{-1}A^{T}D^{-1}$

## Appendix B

Proof for checking whether the matrix, $Q$ is positive definite

Figure 4: Example network

A numerical example of a simple network is given to check the matrix, $Q$ (in
the bracket of Eq. (9)) is positive definite. There are three users who share
the network. The capacities and the propagation delays of the resources are
indicated next to the links. The source, destination, transmission delay,
total delay, data rate, $U^{\prime}$ and user’s route are provided in the
Table 4.

Table 4: User’s data. User | Source | Destination | Route | $d_{trans}^{i}$ | $U^{\prime}_{i}(x_{i})$ | $x_{i}$ | $D$
---|---|---|---|---|---|---|---
User1 | $3$ | $6$ | $3-1-6$ | $9.2593$ | $0.6329$ | $1.0800$ | $42.0744$
User2 | $1$ | $4$ | $1-4$ | $4.6296$ | $0.3759$ | $2.1600$ | $14.6398$
User3 | $6$ | $2$ | $6-5-4-2$ | $9.2593$ | $0.6329$ | $1.0800$ | $43.1729$

By putting all these values, we get the matrix, $Q$ as,

$\begin{bmatrix}0.0011&0&0\\\ 0&0.0034&0\\\ 0&0&0.0011.\end{bmatrix}$

The eigen values of the above matrix are positive with values $(0.0011,0.0034$
and $0.0011)$ hence, the matrix, $Q$ is positive definite.

Table 5: List of Symbols

Symbols Meaning $\Pi$ Probability that a node $i$ will be selected through
preferential attachment $\Pi^{\prime}$ Probability that a node $i$ will be
selected through anti-preferential attachment $N$ Set of nodes $E$ Set of
links $T$ Life span of the networks $x^{\star}$ Optimal data rate $C_{e_{mn}}$
Capacity of a link $e_{mn}$ and $e_{mn}\in E$ $A_{i,j,t_{i}}=1$ If nodes $i$
and $j$ are connected at time $t_{i}$ then the value of the matrix $A$ will be
$1$ otherwise $0$ $x_{r}(t_{i})$ Data flow rate of user $r$ at time $t_{i}$
$U_{r,t_{i}}(x_{r}(t_{i}))$ System utility of user $r$ with rate
$x_{r}(t_{i})$. $\psi_{e_{mn}}(t_{i})$ total data flow through a link $e_{mn}$
at time $t_{i}$ $\mathcal{P}_{r}(t_{i})$ willingness to pay of User $r$ at
time $t_{i}$ $SYSTEM(U(t_{i}),A(t_{i}))$ Aggregate System Utility $d_{prop}$
propagation delay $d_{Q}$ queuing delay $d_{trans}$ transmission delay $D$
total delay $w_{i}(t)$ window size of user $i$ at time $t$ $x_{i}(t)$ data
flow rate of user $i$ at time $t$ $s_{i}$ actual backlog of packets at user
$i$ $n_{0}$ Initial number of nodes in the seed networks. $M(\leq n_{0})$ A
number is selected for network expansion, rewiring and removal of links.
$\sigma(S\rightarrow D)$ Shortest path between $S$ to $D$. $V(w)$ Lyapunov
function