%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Draft paper for MMF TCP flows  %%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[a4paper, 11pt]{article}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage{graphicx}
\def\begdes{\begin{description} \item[] }
\def\enddes{\end{description}}
\newcommand {\eqn}[1]{\label{eq#1}}
\newcommand {\reqn}[1]{(\ref{eq#1})}
\newtheorem{proposition}{Proposition}
\newtheorem{montheo}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{claim}{Claim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{Computing optimal max-min fair resource allocation for TCP flows}
\author{{\Large Dritan Nace\footnote{Corresponding author, email: nace@utc.fr}, Nhat-Linh Doan}\\
Laboratoire Heudiasyc UMR~CNRS~6599,\\
Universit\'e de Technologie de Compi\`egne,\\ 60205 Compi\`egne Cedex, France.\\
{\Large Eric Gourdin, Bernard Liau}\\
France Telecom R\&D,\\ 38-40 rue du G\'{e}n\'{e}ral-Leclerc \\92794, Issy Moulineaux, Cedex 9,  France.}

\date{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\maketitle

\begin{abstract}
In this paper we consider the max-min fair allocation problem as applied to TCP flows in Internet. We are interested in computing the optimal max-min fair allocation vector. The proposed approach allows computing optimal routing paths, with regard to max-min fairness, in stable and known traffic conditions. It is a linear programming based approach which permits a lexicographical maximization of the allocation vector with respect to the fair share attributed to the connections competing for network resources. An optimality proof and some computational results are also presented.
\end{abstract}

%\keywords{Resource Allocation, Telecommunications Networks, TCP, Optimization, Max-min Fairness, Linear Programming.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}\label{s:i}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


In today's computer networks, routing is primarily concerned with the connectivity of the network. Usually a single metric (a weight associated with each link) such as hop-count or delay is used, and routing is then via the path which is the shortest in terms of this chosen metric. Indeed, most Internet backbone networks still use classical Internet routing protocols such as RIP ({\em Routing Internet Protocol}, OSPF ({\em Open Shortest Path First}) \textit{etc.}, which do not necessarily take into account the way that resources are shared among flows supporting TCP ({\em Transmission Control Protocol}. With today's mass commercial use of Internet services, however, it is also important for operators to allocate resources as equitably as possible among all users. Furthermore, this is quite helpful for smoothing traffic congestion since it is destinated to increase the alloted rate to connections.

Research in the resource allocation and traffic congestion area covers such aspects as scheduling, control theory, and routing, all of which aim at a fairer utilization of network resources. Among these, routing has perhaps received the least attention. We investigate this aspect and we propose an approach to compute \textit {off-line} the routing paths which allows a globally equitable sharing of resources among competing connections\footnote{In the following we use the terms \emph{flows} and \emph{connections} interchangeably.}. We assume that the only bandwidth limitations for the competing connections are due to network resources; access rates are taken to be unlimited. Even though severely limited access rates can usually be observed in today's networks as that some results (see \cite{Massoulie00}) have shown that the throughput of flows is mainly determined by their access rate, we believe that the problem will soon migrate away from network access, and towards the core of the network. Indeed, the deployment of DWDM ({\em Dense Wavelength Division Multiplexing}) networks has temporarily assured an abundance of capacity in Internet backbone networks, but the situation could be reversed in the future by the increasing number of simultaneous connections, the mass deployment of ADSL ({\em Asymmetric Digital Subscriber Line}) and the increasing demand for bandwidth. Notice that this study is concerned exclusively with TCP traffic, which represents the greater part of Internet traffic and its main contribution is a method to compute optimal max-min fair resource allocation among TCP flows in stable and known traffic conditions.

\paragraph{Background:}
 Let us also recall that the two main pillars of the Internet are the \emph{routing layer} (IP) and the \emph{transport layer} (TCP and UDP). Here is also one fundamental issue which a fair allocation of resources must address, namely the computing of routes (used in the routing layer) in accordance with a bandwidth sharing policy (transport layer), such that available resources are allotted fairly to competing connections.  An important result (see \cite{Chiu89}) concerning TCP behavior is that the AIMD ({\em Additive Increase, Multiplicative Decrease}) algorithm, (on which TCP is based), converges to an efficient and fair equilibrium point corresponding to \emph{max-min fair} allocation in a network composed of a single bottleneck link with n users sharing it. However, reality is much more complex. So we may note that the latter result (see \cite{Chiu89}) does not hold for networks with multiple bottlenecks. Furthermore, it has been observed that the rate allotted to connections is inversely proportional to the RTT value ({\em Round Trip Time}). This could be explained by the fact that the time to adjust the sending rate of sources is proportional to RTT, which implies some difficulties for long-distance networks in converging to a fair sending rate. Hence connections having long RTT are penalized compared to other connections sharing the same bottleneck links. This problem has been thoroughly investigated. So in (\cite{Kelly} it is shown that the  rate control based on AIMD (additive increase - multiplicative decrease), achieves proportional fairness. Throughout this paper we suppose that resources are distributed among TCP flows according to the max-min fair allocation (that we call simply fairness). Generally speaking, the fairness property means that no user is penalized in relation to others sharing the same bottleneck links.
 Connections are routed in the network through paths (constructed over physically interconnected links) between the source and the destination. Recall that for internal domain routing, connections are established via protocols such as RIP or OSPF which route the traffic along the shortest paths. Even today, routing is primarily concerned with network connectivity. This simplicity is one of the reasons of the success and the robustness of the Internet, but its drawback is the relatively static character of routing. Indeed, optimizing the use of network resources through dynamic routing seems difficult. So, updating routing tables constantly according to the demand for and availability of resources, is currently not feasible because of instabilities and inaccuracies in network indicators.
%
Therefore, the only way for operators to conciliate the use of resources with real time traffic is to use some estimation of traffic demand, and on this basis to determine appropriate routes. Given these conditions, it would appear that the off-line computation of paths is entirely reasonable. This problem is usually modeled as a flow problem in a capacitated network with respect to a traffic demand matrix. Generally forecasts of traffic demand (summarized in the matrix) are expressed as amounts of traffic (\textit{for e.g. Mbs/sec}) to be transported between two nodes. Here, we consider traffic demand as a number of connections to be made, and not as a fixed amount of traffic to be routed.
%

\paragraph{Related works:}
Several variants of the routing and resource allocation computing problem with fair properties have been studied in \cite{Megiddo74,Kleinberg99,Goel00,Ros,Bertsekas92,Fodor}. Some other work on general max-min fairness has been presented in \cite{PGTS,Radu}. In \cite{Megiddo74} the author has proposed an elegant method for the maximal fair multi-commodity flow problem in a single-source, multi-destination network but that cannot be extended to the multi-source multi-destination networks as it is the case here. In \cite{Kleinberg99}, it is shown that the problem of fair unsplittable routing for single-source case is NP-complete. A framework of approximation algorithms is also given. Online approximation algorithms for routing and bandwidth allocation are investigated in \cite{Goel00}. Another research direction is investigating Semi-Definite Programming to express flow problems in the telecommunications context, considering several variants of fairness \cite{Galtier01}. Some relevant work on balanced networks is presented in \cite{Georgiadis} where the authors propose an approach for lexicographically optimal balanced networks. The problem considered is allocating bandwidth between two endpoints of a backbone network so that the network be equitably loaded, and therefore it is limited to the case of single-commodity network. In \cite{Fodor}, the authors propose an heuristic for computing max-min fair routing, and more recently alternative models for computing optimal max-min fair routing has been given in (\cite{NaceISCC,Pioro,PioroMedhi,DAM,NaceINOC}). We propose here a model, (a preliminary version is given in \cite{NaceISCC}), for computing max-min fair resource allocation and at the best of our knowledge no one has studied this problem in such a way.

Other works \cite{Boulahia00,Chen98,Ma98} examine and compare performances of representative routing algorithms. In all these studies, the authors have tried to find an algorithm with fair properties and/or maximizing the overall throughput. They are all online routing algorithms: that is, for each new connection, the source computes in real-time the appropriate path according to local or collected information.

\paragraph{Contribution of this work:}
This work  aim at a fairer distribution of resources via routing, that is each connection has to be served at well as network resources will allow. Obviously, the resources assigned to a flow will depend greatly on the path through which it is routed, and on the load level of each constituent link. From the max-min fair point of view, it can be shown easily that network resource sharing is unique for a given routing. On the other hand, different routing strategies yield different levels of fairness, which justifies the interest of considering routing from a fairness point of view.
We recall that in computing optimal max-min fair resource allocation, our focus is on off-line computation, unlike some of the essentially online algorithms we have outlined above. Our problem can be formulated as optimal max-min fair flow problem in a multi-commodity network. Each flow represents here a particular connection and a traffic demand is considered as a set of simultaneous connections having the same source and destination. We restrict ourselves to the static case, i.e. the traffic connections are known in advance. So, we propose an iterative approach to compute optimal max-min fair resource allocation and the corresponding routing, which is nothing else that a particular flow problem in a capacitated network. We investigate this problem and expose some theoretical properties of the max-min fair allocation vector that permits to deduce the optimality of our approach.

 \paragraph{} The paper is organized as follows: in section 2 we give firstly an algorithm for computing the max-min fair resource allocation corresponding to a given routing. This will permit to clarify the relations between max-min fair bandwidth sharing and routing. Indeed, although this algorithm is not essential to the comprehension of this paper, it allows a better understanding of how bandwidth is shared amongst different competing flows. Next, we provide a mathematical framework and introduce an iterative algorithm for achieving global max-min fair resource allocation and  routing. In section 3, we examine the theoretical properties and also provide proof of the optimality of our approach. In section 4 we present some numerical results. In the final section we conclude and outline orientations for future work.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \section{Modeling the max-min fair resource allocation problem}\label{s:r}
In this section we investigate the problem of maximizing the minimum share offered to each connection in a network assuming max-min fair resource sharing. We give firstly an algorithm for computing the max-min fair resource allocation corresponding to a given routing. This will permit to clarify the relations between fair bandwidth sharing and routing and it will be helpful for understanding the main idea behind our approach. Next, we provide a mathematical framework and introduce an iterative algorithm for computing the optimal max-min fair resource allocation vector and the respective routing. To start with, let give some notation and definitions useful for the remainder of the paper.

\subsection {Notation and definitions}
\paragraph {Notation:}
Before describing the algorithms and presenting in detail the mathematical model for computing the fair allocation vector, let us define the following notation:\\
- A telecommunications network is represented by an undirected graph $G(N,L)$. It is made up of $N$ routers, and $L$ links. The capacity of link $k$ is denoted by $C_k$. \\
- Let $T_d$ be the expressed input traffic, measured by the number of connections of demand $d$. \\
- Let $x_{j,d}$ be the number of connections routed on path $j$ for demand $d$. Notice that the notation $k\in j$ means that link $k$ is in routing path $j$.  \\
- Let $S_k$ be the maximal bandwidth share given to connections routed through link $k$. In other words, it represents the bandwidth offered to all constrained connections using this link.\\
- Let $K$ be the set of  non-congested links.\\
- Let $L \setminus K$ be the set of congested links.\\
- Let $f_k$ be the number of connections passing through link $k$ and not intersecting any of (previously) congested links.\\
We call a link  congested, when all its capacity is shared among the connections routed through it. Conversely, we call a link non-congested when there remains some available bandwidth in the link.

\paragraph {Definitions:}
Firstly, we define the notion of max-min fairness as follows: an allocation of bandwidth to a set of connections is said to be max-min fair if it is not possible to increase the allotted rate of any connection exclusive
ly at the expense of connections whose rates are greater. Mathematically, this can be expressed as follows: \\
Let $P$ be the set of connections (paths) $p$ in $G(N,L)$ and $x_p$ its associated rate. The allocation $x_p$ is said feasible if $x \geq 0$ and all capacity constraints are satisfied. Then, the allocation vector $x$ is said max-min fair if it is feasible and for any other feasible allocation vector $y$, such that $p: y_p>x_p$ than $\exists s\in P: y_{s}<x_{s}\leq x_p$. This definition is introduced by Bertsekas in \cite{Bertsekas92} for the case of fixed single path routing. In order to distinguish from the static routing case we call the allocation vector with respect to all possible routings as optimal max-min fair.
When a set of connections has to be routed, the allocation vector is defined as the one of the allocation share {\it offered} to each connection. Obviously such a vector must contain as much coordinates as connections and its size could be quite huge. Fortunately, we don't need to explicitly enumerate all of them since the latter vector contains at most $|L|$ coordinates with different values, each of them gives the maximal share given to a single connection by network links. Indeed, assuming that access rates are unlimited, we can state that each path is constrained (or congested) in one of its links, so its rate allocation is equal to the minimum of the bandwidth offered by each link of the path. It can also be expressed as the maximal allocation offered by this particular link to connections routed through it and it can be indexed by the link (noted as $S_k$). 
 We can distinguish here two routing cases: bifurcated-routing, called splittable routing with respect to splittable flows; and single routing, called unsplittable routing with respect to unsplittable flows.

In the following we present an iterative algorithm for computing the max-min fair allocation vector that corresponds to a given routing and we then propose another algorithm that permits to compute the optimal max-min fair allocation vector among all feasible allocation vectors and deduce the corresponding routing.


\subsection {Computing the max-min-fair allocation for a given routing}

In the following we give a detailed algorithm that computes the bandwidth allocated to each flow when the network reaches the max-min fair equilibrium point. We assume that all those flows support TCP and that the access rate is unlimited. Bertsekas (see \cite{Bertsekas92}) have presented the progressive or water filling algorithm which achieves also max-min fair sharing for the given single routing case, (see also \cite{Boudec}). Finally, a similar framework algorithm for such a computation is given in (\cite{Charny}).

\begdes { \bf Algorithm MMFA, (Max-Min Fair Allocation computing in a given network with a given routing.):}\\
{\bf\small Given: The network (topology and link dimensioning), the traffic demand matrix and the routing path associated with each connection.\\}
{\bf\small Required: The (max-min fair) allocation vector.}
 \begin{itemize}
{\it Begin}
    \item [(I)] Set $K := L; i := 1;$
    \item [(II)] While $K \neq \emptyset$ and there exists some flow not yet removed, do:\\
      1. Find $k\in K$ minimizing the ${C_j/f_j}, \forall j\in K$, such that $f_j > 0$;\\
      Set $S_k := C_k/f_k; K := K \setminus {k}$;\\
      2. For each flow routed through the link $k$, set bandwidth$:= S_k$. Remove both these flows from the set of initial flows and the capacities used by these flows from the network.\\
Set $i := i+1;$\\
\it {End.}
\end{itemize}
\enddes

At the end of the algorithm, the updated value of each $C_j$, $j\in K$, represents the residual capacity of this link. All links included in $L\setminus K$ are congested, their residual capacity is null. This can be given by the following
 formula: $C_{k} =\sum_{k^{\prime}\in L\setminus K}f_{k,k^{\prime}}\ast S_{k^{\prime}}+f_{k}\ast S_{k}$ , where the $f_{k,k^{\prime}}$ gives the number of flows routed through both links $k$, $k'$ and constrained in $k'$, and $f_k$ gives the number of flows constrained in $k$.

 \subsection{Computing optimal max-min fair splittable routing}\label{mfsr}
In this section we investigate the problem of optimal max-min fair resource sharing in a network when routing is not given. With respect to the previous algorithm, one can notice that arcs are congested in a certain order. The first ones are these offering the less bandwidth to connections passing through, and so on to these offering the more, even some having capacities still not used. In the following algorithm, we state (and prove) that even when the routing is not fixed, the arcs are congested in a unique order, or more exactly by sets of arcs called $MFC$ (for Minimum Fair Cut). For each $MFC$, the algorithm computes the minimum fair share, denoted by $R$, offered to connections constrained in them. To resume, our algorithm states that arcs are congested in a unique order at some bandwidth value and it computes them iteratively: each step is intended to compute the set of newly congested arcs and the maximum bandwidth to be offered at this level while the previously congested arcs and bandwidth values have already been fixed.       

\begdes { \bf Framework of OMMFA algorithm, (Optimal Max-Min Fair Allocation computing in a given network.):\\}
{\bf\small Given: The network (topology and link dimensioning), the set of connections resumed in a traffic demand matrix.\\}
{\bf\small Required: The optimal max-min fair allocation vector and the corresponding routing paths.\\}
 \begin{itemize}
 {\it Begin}
    \item [(I)] Maximize the minimum bandwidth offered to each connection, {\it problem $P_1$.} \\
      Set $K := L; i=1;$\\
      {\it Compute $MFC_1$;}\\
      $\forall k \in MFC_1$: Set $S_k := 1/B = f_k/C_k; K := K \setminus k$;
      \item [(II)] Until $(K \neq L)$ and there exists a connection not constrained in $L \setminus K$, do: \\
{\it Compute $R$;}\\ 
{\it Compute $MFC_i$;}\\
$\forall k \in MFC_i$: Set $S_k := R; K := K \setminus k$;
$i = i+1;$
\item [(III)]For all links $k$ not congested after the final step of the algorithm, set $S_k :=+\infty$.\\
The paths obtained during the last step have the property to optimize the routing from the max-min fairness point of view.\\
{\it End}
\end{itemize}
\enddes
Where {\it Compute $R$} and {\it Compute $MFC_i$} are all procedures detailed below. Each step of the algorithm is intended to maximize the current $R$. The $R$ value is computed through an iterative procedure, (except for the first step of the algorithm). We compute the amount of residual capacity of non-congested links and we then increase $R$ according to the latter value, (procedure {\it Update $R$}). We stop iterating when this residual capacity becomes null for some non-congested links or sufficiently small, which means that the current $R$ value has reached the max-min fair share bandwidth among the connections routed through the current non-congested links. Note that we initiate the procedure with the last computed $R$ and this is not possible for the first step. We therefore provide the following two (different) mathematical formulations, the first one, (procedure {\it Solve the problem $P_1$}), and the second one for the corresponding problem $P_i$ (procedure {\it Solve the problem $P_i$}) for the computation of $R$.

Intuitively, the above algorithm states that the smallest alloted value is to be maximized before the second smallest value is maximized, and inductively, the maximization for some alloted value is carried out after those whose values are worse than the given value have been maximized. One can notice that there are great differences with the precedent algorithm or the well known progressive or water filling one which achieves max-min fair sharing for the given single routing case (\cite{Bertsekas92}). The main difference relies on the fact that for us the routing is not  fixed in the beginning and neither at the end of each step of algorithm except the last one which gives the optimal max-min fair sharing we are looking for.

\subsubsection {Formulating and solving the problem $P_1$}
Obviously, the problem $P_1$ can be modeled as a routing problem. The latter is defined as an optimization one, a multi-commodity problem aiming to guarantee fairness. The multi-commodity is represented by a given traffic matrix. This problem can be modeled by an edge-path formulation which allows more facility and flexibility when considering particular constraints such as path-length limitation constraints. Assuming that $F$ corresponds to the minimum bandwidth allotted to each flow at the equilibrium point imposed by max-min fair allocation, we have:
\begin{eqnarray}
&  Max \quad F & \nonumber \\
\label{CapF1}\forall k\in L &  F * f_k &\leq  C_k   \\
\label{TrafF1}\forall d\in D, &  \sum\limits_{j\in h(d)} x_{j,d} &= T_d  \\
\label{fkF1}\forall k\in L  & \sum\limits_{j\in h(d),d\in D,k\in j} x_{j,d} &= f_k   \\
\label{IntF1}\forall d \in D, \forall j\in h(d) & x_{j,d} & \in \mathbb{N}^{+}
\end{eqnarray}

As it can easily be seen, this formulation is not linear because of the set of constraints (\ref{CapF1}). Indeed, the variable $F$ and $f_k$ are not linearly dependent. So we replace $F$ by $1/B$, where $B$ gives the potential delay ( see for example \cite{Massoulie99}). The objective function becomes: $Min ~B $ (in place of $Max ~F$), and the set of constraints (1) will be replaced by the following set of constraints (\ref{CapB}):
\begin{eqnarray}
\label{CapB}\forall k\in L  & f_k - B * C_k &\leq  0
\end{eqnarray}

Replacing $f_k$ by the corresponding (\ref{fkF1}) we obtain the following problem $P_1$:
\begin{eqnarray}
&  Min  \quad B & \nonumber\\
\label{CapP1} \forall k\in L  & B * C_k - \sum\limits_{j\in h(d),d\in D,k\in j} x_{j,d} & \geq 0  \ \ \ (\omega_{k})\\
\label{TrafP1} \forall d\in D & \sum\limits_{j\in h(d)} x_{j,d}& = T_d  \ (\pi_d)\\
\label{PositifP1} \forall d \in D, \forall j\in h(d) & x_{j,d}
&\in \mathbb{R}^{+}
\end{eqnarray}

where $\omega_{k}$ (respectively $\pi_d$) are the dual coefficients of constraints (\ref{CapP1}) (respectively constraints (\ref{TrafP1})). Constraints (\ref{CapP1}) are capacity constraints and constraints (\ref{TrafP1}) ensure that all connections of each commodity are routed. At this stage we ensure somehow a first level load balancing. Indeed, minimizing the variable $B$, permits the maximization of the minimum share that each flow will get. It will be noticed that the set of constraints (\ref{PositifP1}) does not require an integer number of connections to be routed through a path. In reality a large number of flows can share the network resources simultaneously, and in such a dynamic environment, the most important consideration is the proportion of traffic routed by a path, not the fact that an integer number of flows are wholly routed via a path. Lastly, few words about solving the multi-commodity flow problem $P_1$. Obviously, we cannot make all candidate paths explicit, owing to their large number, so we use a set of initial paths and resolve the problem as a simple PL. However, the obtained result is not necessarily optimal. We use then a column generation method\footnote{Each column is represented here by a path.}: that is, we generate some new routing paths in the initial graph populated with dual coefficients values $\omega_k$ through a \emph{path generator}. Indeed, the reduced cost associated with each column (path $j\in h(d)$) is given by $\pi_d - \sum_{k\in j}{\omega_k$. Recall that according to the simplex algorithm, a candidate path to enter in the basis of linear programming $P_1$ must have the reduced cost $\geq 0$. Hence, we have for instance to find $j\in h(d), d\in D$ maximizing $\pi_d - \sum_{k\in j}{\omega_k$, which is nothing else that minimizing $\sum_{k\in j}{\omega_k}$. Then, we iterate resolving the modified LP program until we cannot generate any new column, that is, we cannot find any path such that $\sum_{k\in j}{\omega_k}\leq\pi_d$. Obviously, the solution obtained at this last step is an optimal one. 


\subsubsection {Formulating and solving the problem $P_i$}
We have also used an edge-path formulation for the problem $P_i$. Notice that in the following formulation (see constraints (\ref{fkk'Pi})), $f_{k,k'}$ express the number of connections passing simultaneously through links $k$ and $k'$, and constrained on link $k'$. We now have:
\setlength\arraycolsep{2pt}
\begin{eqnarray}
& Max  \quad \epsilon  & \nonumber \\
\label{CapKPi} \forall{}k\in{}K,  &  \sum\limits_{k^{\prime}\in L\backslash{}%
K} f_{k,k^{\prime}}\ast S_{k^{\prime}}+f_{k}\ast R +\epsilon &
\leq
C_{k} \ (\omega_{k})\\
\label{CapLKPi}\forall{}k\in{}L\backslash{}K,  & \sum
\limits_{k^{\prime}\in L\backslash{}K,\,k^{\prime}<k}
 f_{k,k^{\prime}}\ast S_{k^{\prime}}+f_{k}\ast
S_{k} &= C_{k} \ (\omega_{k})\\
\label{TrafPi} \forall{}d\in{}D,  &  \sum\limits_{j\in h(d)}
x_{j,d}^{{}
} & =T_{d} \ (\pi_{d})\\
\label{fKPi}\forall{}k\in{}K,  & \sum\limits_{ \substack{
j\in h(d), d\in D, k\in j,\\
s.t.\{(L\backslash K)\cap j\}=\phi }
} x_{j,d} &=f_{k}\\
\label{fLKPi}\forall{}k\in{}L{\backslash}K,  &
 \sum\limits_{ \substack{
j\in h(d), d\in D, k\in j,\\
s.t.\forall k^{\prime}\in\{(L\backslash K)\cap j\},\\
S[k]<S[k^{\prime}] }
} x_{j,d}^{{}}&=f_{k}\\
\label{fkk'Pi}\forall k\in K,  & \sum\limits_{ \substack{
j\in h(d),\ d\in D,\ k, k^{\prime}\in j,\\
s.t.\forall k"\in\{(L\backslash K)\cap j\},\\
S_{k^{\prime}}<S_{k"} } } x_{j,d}^{{}
} & =f_{k,k^{\prime}}\\
\label{PositifPi} \forall d \in D, \forall j\in h(d) & x_{j,d} &\in \mathbb{R}^{+}  \\
 \label{PositifePi}& \epsilon &\geq 0
\end{eqnarray}

As it can easily be observed from the algorithm, $S_k$ and $R$ are not considered as variables. They are fixed at each step of the algorithm via the procedure {\it Update R}. So, the current value of $R$ (step $i$) is updated at each stage (see (\ref{R})), until we get $\epsilon = 0$.

\begin{equation}
\label{R}
 R[i]= \min\limits_{k\in K} \left\{ \frac{C_{k} -
\sum\limits_{k^{\prime }\in L\backslash K} f_{k,k^{\prime }} \ast
S_{k^{\prime }} } {f_{k} } \right\}
\end{equation}

 The variables of the problem $P_i$ are $x_{j,d}, f_k$, $f{_{k,k'}$, and finally $\epsilon$. The latter represents the maximal minimum residual capacity of non-congested links in the network. The set of constraints (\ref{CapKPi}) and (\ref{CapLKPi}) are simply the capacity constraints corresponding to non-congested and congested links respectively. Constraints (\ref{TrafPi}) ensure that the connections of each commodity are totally routed. Concerning the following constraints (\ref{fKPi}), (\ref{fLKPi}) and (\ref{fkk'Pi}), they are introduced to specify the $f_k$ and $f_{k,k'}$ variables and are intended to easy the reading of the model. So, the set of constraints (\ref{fKPi}) (respectively (\ref{fLKPi})) express the number of connections passing simultaneously through non-congested (respectively congested) link $k$ and not congested in any other link of the respective path. If we replace the $f_k$ and $f_{k,k'}$ variables in (\ref{CapKPi}) and (\ref{CapLKPi}) by their corresponding in (\ref{fKPi}), (\ref{fLKPi}) and (\ref{fkk'Pi}), then the dual coefficients of constraint sets (\ref{CapKPi}) and (\ref{CapLKPi}) (respectively (\ref{TrafPi})) are given by $\omega_k$ values (respectively $\pi_d$).

The multi-commodity flow problem $P_i$ is solved in a similar way to problem $P_1$. We use a column generation method, where new columns represent candidate routing paths. The latter ones correspond to the shortest path in the sense of a two-parameter function in the initial graph valued with $\omega_k$ and $S_k$ values. Indeed, the reduced cost associated with each column (path $j\in h(d)$) is given here by $S_{k'}*\sum_{k\in j}\omega_k + \pi_d$, where $S_{k'} = Min \{S_k, k\in j\}$. A valuable path to improve the solution must have the reduced cost $\leq 0$. Hence, we have to find $j\in h(d), d\in D$ minimizing: $S_{k'} * \sum_{k\in j}\omega_k + \pi_d$ (or simply $S_{k'} * \sum_{k\in j}\omega_k$), where $\forall k\in K, S_k=R$, with $R$ the most recently computed value. Unlike the shortest path computing problem implying two additive parameters, which is known to be NP-complete, this is a polynomial problem. It can be simply implemented by computing the shortest paths $j$ (in the sense of valuations $\omega_k$) passing through each of one of links $k \in L$ and keep the one minimizing the formula $S_{k'} * \sum_{k\in j}\omega_k$.   Let us finally point out that in the general case we use the Dijkstra shortest path algorithm and we use a modified version of the Ford-Bellman algorithm with a given routing if we have to limit the length (number of links) of the routing paths. 

\subsubsection {Procedure Compute $MFC_i$}
In practice, when several links are congested (let us call the corresponding set $Q$) at the end of the $i^{th}$ step, we cannot distinguish those really congested ($MFC_i$) from others. Indeed, according to the complementary slackness property of duality theory, we have : $(\sum\limits_{k^{\prime}\in L\backslash{}K} f_{k,k^{\prime}}\ast S_{k^{\prime}}+f_{k}\ast R +\epsilon - C_{k})* \omega_{k} = 0$ and we can say that the link $k$ is congested if $\omega_k>0$. Furthermore, there is at least one value strictly positive since from the dual formulation of the problem $P_i$, we have:$\sum_{k\inK}\omega_k \geq 1$. However nothing permits to conclude the same thing when $\omega_k=0$, which makes necessary the following procedure. Thus, once the corresponding $R$ has been computed, we search for $MFC_i$ as follows:

\begdes { \bf Compute $MFC_i$}
 \begin{itemize}
    \item [(I)]Initiate $MFC_i := \emptyset$.
      $\forall k\in K$ if $\omega_k=0$ then $k \in MFC_i$;
\item [(II)] For $\forall j \in K$, if $(\sum\limits_{k^{\prime}\in L\backslash{}K} f_{k,k^{\prime}}\ast S_{k^{\prime}}+f_{k}\ast R +\epsilon - C_{k})* \omega_{k} = 0$ do: {\em /* Modify slightly the problem $P_i$. */}\\
Remove $\epsilon$ from all constraints in (\ref{CapKPi}) except the one corresponding to link $j$.\\
Solve the current problem.\\
If $\epsilon = 0$, then set $j \in MFC_i$.
\item [(III)]At the end of the procedure we get $MFC_i$ which is the minimum fair cut associated with the problem $P_i$.
\end{itemize}
\enddes

Obviously, all links included in the same $MFC_i$ offer the same max-min fair share. Thus, at each step of OMMFA algorithm, we mark all of them as congested links, and we fix the corresponding $S_k$ to $R$.


\subsubsection {Example}
Here we give an example to show how the two above algorithms work and explain the relation between routing and resource sharing.
Suppose that we have a network with 4 nodes : A, B, C, D, connected by 4 links AB, AC, BD, CD with
capacities fixed respectively at 1MB, 3MB, 1MB and 2MB. The connections to be routed are
A $\rightarrow$ B, A $\rightarrow$ C, A $\rightarrow$ D, B
$\rightarrow$ D and C $\rightarrow$ D.

Let first see how the first algorithm runs on this example when the routing is fixed (see figure 1), as shown in table 1. We can remark that at the end of the first step, connections of A $\rightarrow$ B, A $\rightarrow$ D, B $\rightarrow$ D are filled with a rate of 0.5MB/sec. Consequently, the links AB, BD become saturated. During the next step, the connections C $\rightarrow$ D is saturated with the rate of 2MB. At the final step, A $\rightarrow$C is saturated with the rate of 3MB/sec. The total throughput is 6.5 MB/sec.

The second figures gives the steps of the algorithm given in figre 2. At the end of the first step, the links AB, BD are saturated by demands A $\rightarrow$ B and B $\rightarrow$ D.  AC is also saturated by demands A $\rightarrow$ D and C $\rightarrow$ D. The current sharing rate is 1MB/sec. During the second step, AC is saturated and the rate of A $\rightarrow$ C is 2MB/sec. The total throughput is 6MB/sec.

Let us consider lastly what happens when one aims to maximize the overall throughput, see figure 3. We will obtain for A $\rightarrow$ B, A $\rightarrow$ C, B $\rightarrow$ D and C $\rightarrow$ D the respective rates of 1MB/sec, 3MB/sec, 1MB/sec and 2MB/sec. The connection A $\rightarrow$ D has not been served at all. The total throughput is 7MB/sec.
%-------------------------------------------------------------------
\begin{figure}
[h]
\begin{center}
\fbox{
\includegraphics[scale=0.3]{fix.png}%
}
\end{center}
\label{fig.fixrouting} \caption{The resulted resource sharing for a given routing (MMFA).}

\end{figure}
%--------------------------------------------------------------------
\begin{figure}
[h]
\begin{center}
\fbox{
\includegraphics[scale=0.3]{fair.png}%
}
\end{center}
\label{fig.fairrouting} \caption{The resulted resource sharing for OMMFA routing}

\end{figure}
%-------------------------------------------------------------------
\begin{figure}
[h]
\begin{center}
\fbox{
\includegraphics[scale=0.3]{max.png}%
}
\end{center}
\label{fig.maxrouting} \caption{The resulted resource sharing when maximizing the overall throughput}

\end{figure}
%-------------------------------------------------------------------
\begin{table}[htbp]
\begin{tabular}
{|c|c|c|c|c|c|c|} \hline & \multicolumn{2}{|c|}{Given Routing} &
\multicolumn{2}{|c|}{Fair Allocation} &
\multicolumn{2}{|c|}{Max Throughput}  \\
\hline Connection& Path& Flow& Path& Flow& Path&
Flow \\
\hline A $\rightarrow$ B& A-B& 0.5& A-B& 1& A-B&
1 \\
\hline A $\rightarrow$ C& A-C& 3& A-C& 2& A-C&
3 \\
\hline A $\rightarrow$ D& A-B-D& 0.5& A-C-D& 1& -&
0 \\
\hline B $\rightarrow$ D& B-D& 0.5& B-D& 1& B-D&
1 \\
\hline C $\rightarrow$ D& C-D& 2& C-D& 1& C-D&
2 \\
\hline Total&  & 6.5 &  & 6 & &
7 \\
\hline

\end{tabular}
\label{tab.Table1} \caption{Comparison of resource sharing for three routing strategies}
\end{table}
%-------------------------------------------------------------------

\section {Correctness}

\label{subsec:preuve}

The correctness of our approach and the optimality of the solution obtained by our iterative algorithm does not appear obvious, even for the continuous case (splittable routing). Indeed, different multi-flows (routings) can satisfy all constraints fixed for the problem $P_i$ at each step $i$ of the algorithm. Furthermore, several links might possibly be congested by different multi-flows. Recall also that each step of the OMMFA algorithm yields at least one of coordinates of the max-min fair allocation vector. Once computed, this value is fixed for the corresponding link, and used as a constant for the rest of calculations. So some questions naturally arise. How does this impact the upcoming $R$ value, and consequently the {\it quality} of the computed allocation vector? Which is the best link to choose and what are the consequences for the desired routing? In the following we shall try to answer these questions, and prove formally the uniqueness and the optimality of the allocation vector computed by our OMMFA algorithm.


\begin{lemma}
Each routing solution yielded by step $k$ of the OMMFA Algorithm is congested simultaneously in all links of $\sum_{i\leq k}MFC_i$.
\end{lemma}
One can easily verify that each solution obtained at the end of a given step $i$ is necessarily constrained in all links $l$ of $MCF_i$, since the corresponding constraints are tight. The tightness of such constraints (\ref{CapKPi}) is explained either by the fact that the corresponding dual variable $\omega_l \geq 0$, or either that the test associated with each $l$ gives $\epsilon = 0$. The proof can then be deduced from the fact that each solution obtained at the end of some step of the algorithm, is also a solution for all problems stated in previous steps, since it satisfies all relative constraints and it achieves necessarily $0$ for the corresponding $R$. 


\begin{montheo}
Each routing solution obtained at the end of the $k^{th}$ step of the procedure has the following property:\\
There is no other routing that allows to increase the alloted value to at least one connection constrained in one of congested links without decreasing the allocation of some connection less served.    
\end{montheo}
Obviously the above statement holds for the first step of the algorithm. Let us suppose that it also holds for the step $k$ and prove it for the next step. From the lemma 1, we can state that each solution obtained at the end of the step $k$, is also a solution for all problems $P_i, i < k$, and thus the above statement holds for all connections constrained in one of links in $\sum_{i < k, MFC_i$. Let us consider now the connections saturated in one of links in $MFC_k$, let say $l$. With respect to the formulation of the corresponding problem $P_k$, and keeping in mind that the $\epsilon = 0$ and the constraints (\ref{CapKPi}) for link $l$ is tight, the only way to increase the allocation of connections passing through the link $l$ is decreasing the allocation of the connections passing simultaneously through $l$ and some other previously congestioned arcs. The tightness of such constraints (\ref{CapKPi}) is explained either by the fact that the corresponding dual variable $\omega_p \geq 0$, or either that associated test gives $\epsilon = 0$, and thus there is no room for other connection in this arc.

An immediate corollary of the above theorem is that the allocation vector obtained at the end of the OMMFA algorithm is necessarily max-min fair.

\section{Numerical results}

Our approach for computing optimal max-min fair resource allocation was implemented in C++ with CPLEX 7.1. All tests were run on a machine with the following configuration: Sun 4000, SOLARIS 2.5, 6 UltraSparc 167Mhz processors, 256 MB of RAM.

In Table \ref{Table:net.description}, we summarize the main characteristics of four network instances that we used for our max-min fair resource allocation computations.

\begin{table}
\centering
\begin{tabular}
{|p{45pt}|p{45pt}|p{45pt}|p{50pt}|}
\hline Network& Nodes& Edges&
Demands \\
\hline
NET11&
11&
23&
55 \\
\hline
NET15&
15&
105&
105 \\
\hline
NET26&
26&
43&
264 \\
\hline
NET41&
41&
70&
319 \\
\hline
\end{tabular}
\caption{Description of test networks}
\label{Table:net.description}
\end{table}

We recall that in our model maximizing the global throughput of the network is not a goal. It is nevertheless interesting to compare the throughput of fair multi-flow with the global throughput. We therefore chose to implement a model solving the maximum multiflow problem with the same set of demands as for the fair routing. We have also considered the model where the routing is done through the shortest path in number of links, ({\it i.e., OSPF with unitary  metric for each link in the network}). Some comparisons are presented in the following graphics.

\begin{figure}
[h]
\begin{center}
\fbox{
\includegraphics[scale=0.4]{cmp15new.png}%
}
\end{center}
\label{fig.maxrouting} \caption{Comparison of resource sharing
between maximizing the overall throughput and the max-min
fairness, Net15}

\end{figure}

\begin{figure}
[h]
\begin{center}
\fbox{
\includegraphics[scale=0.4]{cmp41new.png}%
}
\end{center}
\label{fig.maxrouting} \caption{Comparison of resource sharing
between maximizing the overall throughput and the max-min
fairness, Net41}

\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Concluding remarks and future works}

\paragraph{Summary and discussion.}
In this paper we have presented an iterative algorithm for computing off-line max-min fair resource allocation and the corresponding routing paths in stable and known traffic conditions. It is a linear programming based approach that permits a lexicographical maximization of the allocation vector. We have also examined some theoretical properties and provided an optimality proof sketch of the proposed computation approach. It is worth noting that the proposed computing approach cope with a homogeneous traffic increase/decrease across all demands. Indeed, it permits to maximize the bandwidth offered to flows according to the availability of resources in the network, so that as long as traffic is subject to homogeneous changes, the model gives what the network can offer at best. Note also that access rate (assumed unlimited), constraints can easily be incorporated into our model.
%
The routing problem considered in this paper could be modeled by an arc-node formulation, but we have opted for an arc-path formulation that allows greater facility and flexibility in considering particular path constraints, such as limited length\footnote{Other QoS constraints could be considered but this could induce significant additional computation time, and usually leading to NP complete problems.}. Furthermore this formulation has the particularity of limiting the number of obtained paths (about $|D| + |L|)$, where $|D|$ gives the cardinality of the set of demands, and $|L|$ gives the number of links. In practice, we have remarked that only a certain proportion of traffic demands is multi-routed (generally two routes), and the rest is mono-routed. This result could be interesting from \textit{technological application} point of view. Indeed, a small number of routing paths could easily be materialized by MPLS ({\em Multi Protocol Label Switching}) Technology.

\paragraph{Future works.}
Obviously we intend to connect routing with the way resources are shared between competitive connections. Until now we have focused on the pure max-min fair case, which in some respects limits the scope of this approach. However, reality is much more complex and it is shown (\cite{Kelly} that the rate control based on AIMD (additive increase - multiplicative decrease), achieves proportional fairness. This could be also taken into account by our algorithm by expressing the proportional fairness notion through an approximated linear polynomial function as proposed in \cite{PioroMedhi}. One of our future research direction is considering some other variants of fairness {\textit i.e.} proportional fairness. Notice also that the proposed model is user-aware oriented, and it does not take into account global throughput considerations. Our plan, however, is to work on a multi-objective optimization function where both fairness and the global throughput are represented. Another research direction is considering the unsplittable case which is known to be NP-complete. Recall that computing unsplittable routing, as shown in \cite{Kleinberg99}, is not an easy task even for the single-source case (NP-complete). Furthermore, the theoretical results developed for the latter are not applicable. Indeed, it can easily be shown that for the unsplittable flow case, different routings can offer the same fairness for distinct links.

\begin{thebibliography}{10}

\bibitem{Benameur00}
W.~Ben-Ameur and E.~Gourdin.
\newblock Internet routing and related topology issues.
\newblock In {\em Proc. of {DRCN} 2000}, 2000.

\bibitem{Bertsekas92}
A.~Bertsekas and R.~Gallager.
\newblock {\em Data Networks}.
\newblock Prentice-Hall, Engelwood Cliffs, {N.J.}, 1992.

\bibitem{Massoulie00}
T.~Bonald and L.~Massouli\'e.
\newblock Impact of fairness on Internet performance.
\newblock In {\em Proc. of ACM SIGMETRICS 2001}, 2001.

\bibitem{Boulahia00}
S.~Boulahia-Oueslati.
\newblock {\em Qualit\'e de service et routage des flots \'elastiques dans un r\'eseau multiservice}.
\newblock PhD thesis, {ENST}, Paris, {F}rance, November 2000.

\bibitem{Charny}
A.~Charny, D. D.~Clark and R.~Jain.
\newblock Congestion control with explicit rate indication.
\newblock In {\em Proc. of IEEE International Conference on Communications}, 1995.

\bibitem{Chen98}
S.~Chen and K.~Nahrstedt.
\newblock Maxmin fair routing in connection-oriented networks.
\newblock Tech. report, Dept. Comp. Science, UIUC, {USA}, 1998.

\bibitem{Chiu89}
D.~Chiu and R.~Jain.
\newblock Analysis of the increase and decrease algorithms for congestion avoidance in computer networks.
\newblock {\em Computer Networks and ISDN Systems}, 17:1--14, 1989.

\bibitem{Fodor}
G.~Fodor, G. Malicsko, M. Pioro and T. Szymanski.
\newblock Path Optimization for Elastic Traffic under Fairness Constraints.
\newblock In {\em Proc. of {ITC} 2001}, Brazil, December 2001.

\bibitem{Galtier01}
J.~Galtier.
\newblock Semi-definite programming as a simple extension to linear programming: convex optimization with queueing, equity and other telecom functionals.
\newblock In {\em Proc. of {A}lgo{T}el 2001}. {INRIA}, 2001.

\bibitem{Georgiadis}
L.~Georgiadis, P. Georgatsos, K. Floros, S. Sartzetakis
\newblock Lexicographically Optimal Balanced Networks.
\newblock In {\em Proc. Infocom'01}, pp. 689-698, 2001.

\bibitem{Goel00}
A.~Goel, A.~Meyerson, and S.~Plotkin.
\newblock Combining fairness with throughput: Online routing with multiple objectives.
\newblock In {\em Proc. 32nd {ACM} {STOC}}, 2000.

\bibitem{Kelly}
F. P.~Kelly, A.~Maulloo, and D.~Tan.
\newblock Rate control in communication networks: shadow prices, proportional fairness and stability.
\newblock {\em Journal of the Operational Research Society}, vol. 49, pp. 237-252, 1998.

\bibitem{Kleinberg99}
J.~Kleinberg, Y.~Rabani, and E.~Tardos.
\newblock Fairness in routing and load balancing.
\newblock In {\em Proc. of the 35th Annual Symposium on Foundations of Computer Science}, 1999.

\bibitem{Ma98}
Q.~Ma.
\newblock {\em Quality-of-Service Routing in Integrated Service Networks}.
\newblock PhD thesis, Carnegie Mellon Univ., Pittsburgh, USA, Jan. 1998.

\bibitem{Massoulie99}
L.~Massouli\'e and J.W.~Roberts.
\newblock Bandwidth sharing: objectives and algorithms.
\newblock In {\em Proc. of IEEE INFOCOM'99}, 1999.

\bibitem{Megiddo74}
N.~Megiddo.
\newblock Optimal flows in networks with sources and sinks.
\newblock {\em Mathematical Programming}, 7, 1974.

\bibitem{NaceINOC}
D. Nace, N-L. Doan,
\newblock Some Results on Max-min Fair Routing", INOC 2003, Evry, 27-29 October 2003.
\newblock {\em In Proc. of {INOC} 2003, Evry, October 2003}.

\bibitem{Boudec}
J. Y.~Le Boudec
\newblock Rate adaptation, congestion control and fairness: a tutorial.
\newblock {\em http://ica1www.epfl.ch/PS\_files/LEB3132.pdf}, December 2000.

\bibitem{NaceISCC}
D.~Nace.
\newblock A linear programming based approach for computing optimal splittable fair routing.
\newblock In {\em Proc. of The Seventh IEEE Symposium on Computers and Communications 2002, ISCC'2002. pp. 468-474}, July 2002, Taormine, Italy.

\bibitem{DAM}
D.~Nace, L.N.~Doan.
\newblock A polynomial approach to the fair multi-flow problem.
\newblock {\em Rapport Interne, Heudiasyc, UTC, November 2002}.

\bibitem{Ros}
J. Ros and  W. K. Tsai,
\newblock A Theory of Maxmin Rate Allocation with Minimal Rate Guarantee.
\newblock {\em  Technical Report, http://www.eng.uci.edu/~netrol, June 2000.}

\bibitem{Pioro}
M. Pioro, P.~Nilsson, E.~Kubilinskas and G.~Fodor.
\newblock On efficient Max-min Fair Routing ALgorithms.
\newblock {\em In Proc. of {ISCC} 2003, Antalya, Turkey, July 2003}.

\bibitem{PioroMedhi}
M. Pioro and D.~Medhi,
\newblock {\em Routing, Flow and Capacity Design in Communication and Computer Networks]},
\newblock Morgan Kaufmann Publishers (to appear in March 2004).

\bibitem{Radu}
B. Radunovic, J.-Y. Le Boudec.
\newblock A Unified Framework for Max-Min and Min-Max Fairness with Applications.
\newblock {\em Technical Report IC-200248, EPFL, July 2002, http://lcawww.epfl.ch/Publications/Radunovic/TR02\_048.ps.}

\bibitem{PGTS}
A.~Tomaszewski.
\newblock A polynomial algorithm for solving a general max-min fairness problem.
\newblock {\em In the Proceedings of the second Polish-German Teletraffic Symposium, PGTS 2002, Gdansk, 2002}.

\bibitem{Teghem}
J. Teghem.
\newblock {\em Programmation Lin�aire}.
\newblock Ed. Ellipses, 1996.

\bibitem{Vojvonovic}
M.~Vojvonovic, J.-Y.~Le Boudec and C.~Boutremans.
\newblock Global Fairness of additive-increase and multiplicative-decrease with heterogeneous round trip-times.
\newblock In {\em Proc. of IEEE INFOCOM'00}, 2000.

\end{thebibliography}
\end{document}




Consequently, the computed fair paths may be assigned dynamically to the flows competing for the network resources.



+ ajouter

attention � l'utilisation de la ref. Massoulie00 (une autre reference pour le calcul de fairness pour un routage donn�).
+
les formules � deux �tages
+
Ajouter deux phrases au d�but pour presenter le problem en RO.
+
??
enlever unsplittable routing??



\begin{algorithm}
\caption{Procedure: Compute $MFCi$.}
\begin{algorithmic}
\REQUIRE We assume the routing path for each flow is known.
\ENSURE Determination of (max-min) fair allocation vector.
{\it Begin}
\STATE Set $MFCi := Q$;
\STATE For $\forall j \in Q$ do:
\STATE {\em /* Modify slightly the problem $Pi$. */}.
\STATE Remove $\epsilon$ from all constraints in (\ref{CapKPi}) except the one corresponding to link $j$.\\
\STATE  Solve the current problem.\\
\STATE If $\epsilon \geq 0$, do $MFCi:= MFCi \setminus j$.\\
\STATE At the end of the procedure we get $MFCi$ which is the minimum fair cut associated with the problem $Pi$.\\
{\it End}

\end{algorithmic}
\end{algorithm}


 \paragraph{Unsplittable fair routing.}
 We propose here a scheme that permits routing paths with fair properties to be computed for unsplittable flows, \textit{i.e.} that allocates a unique routing path to each traffic demand. Therefore, we are primarily interested in finding routing paths which permit a global load balancing with respect to users. Let us recall first that computing unsplittable routing, as shown in \cite{Kleinberg99}, is not an easy task even for the single-source case (NP-complete). In order to compute such a routing (multi-source multi-destination), we take as a starting point the OMFA algorithm presented in section \ref{s:r}.

 Obviously the unsplittable flow case is much more complex than the splittable one, and the theoretical results developed for the latter are not applicable. Indeed, it can easily be shown that for the unsplittable flow case, different routings can offer the same fairness for distinct links. In these conditions we cannot really speak of minimum fair cut (here, contrary to the splittable flow case where where more than one link can only be congested simultaneously, links may be congested non-simultaneously). With reference to the MSFR algorithm presented in section \ref{msfr}, we have been able to come up with a similar approach which can be applied to the computation of fair unsplittable routing. It is based on a classical branching scheme. Without entering into details, this approach applies branching on links providing the same maximal bandwidth (at a given step), thus generating a tree. To each pendant leaf of the tree a value (to be computed) of $R[i]$ is associated. Obviously, a breadth-first search is much better suited to a lexicographical maximization of the vector $R$. Consequently, for the computation of $R[i]$ at a given step, all the corresponding $Sk$ remain fixed for all links k associated with prior nodes in the tree. We are currently implementing this algorithm, and numerical results will shortly be available. We do not, however, consider the sub-optimality condition, but we intend to integrate it in the model in the near future.

 However, in this paper we restrict ourselves to the case of \emph{pure} max-min fair sharing resources among competing connections, which is the primary assumption of our approach for routing paths computation.


\section {Discussion}\label{Discussion}


However, multi-routing is not really satisfactory. Recall that in most Internet backbone networks routing protocols such RIP, OSPF, \textit{etc.} apply single routing: all traffic between two nodes is routed through a single path. Path lengths are defined as the sum of weights associated with the links constituting the path. In these conditions it is a question of finding the best weights allowing the best routing. In \cite{Benameur00} it is shown how such weights may be computed for a given set of routing paths satisfying certain conditions. Indeed, such conditions are essentially related to the destination-based property that most of routing protocols require. That is, all traffic having the same destination, emanating or in transit from one node, has to follow the same route to the destination node. This can be expressed by the condition of sub-optimality, forcing the existence of a unique route or sub-route between each pair of nodes in the network. Once such paths have been computed, we can find optimal weights via the method proposed in \cite{Benameur00}. Traffic will be routed through the shortest paths, which, according to these weights, are nothing other that the initial paths.

 In order to compute fair unspplittable routing (multi-source multi-destination), one can take as a starting point the OMFA algorithm presented in section \ref{s:r} and develop an approach based on a classical branching scheme. Without entering into details, this approach applies branching on links providing the same maximal bandwidth (at a given step), thus generating a tree. To each pendant leaf of the tree a value (to be computed) of $R[i]$ is associated. Obviously, a breadth-first search is much better suited to a lexicographical maximization of the vector $R$.





\bibitem{NaceISCC}
D.~Nace.
\newblock A linear programming based approach for computing optimal splittable fair routing.
\newblock In {\em Proc. of The Seventh IEEE Symposium on Computers and Communications 2002, ISCC'2002. pp. 468-474}, July 2002.
-----------------------------7d23348adc--

Load balancing by redundant decomposition and mapping
J. F. de Rondea, A. Schonevelda and P. M. A. Sloota
Future Generation Computer Systems, Volume 12, Issue 5, April 1997, Pages 391-406


Load-balancing solutions for static routing schemes in ATM networks*1
C. Casetti, R. Lo Cigno and M. Mellia
Computer Networks
Volume 34, Issue 1, July 2000, Pages 169-180


A link-state routing protocol for the provisioning of data services over ATM networks
T. Vaz�o and A. Casaca
Computer Communications
Volume 24, Issue 10, 15 May 2001, Pages 917-932


Balanced k-colorings,
Therese C. Biedl, Eowyn Imageenek, Timothy M. Chan, Erik D. DemaineE-mail, Martin L. Demaine, Rudolf Fleischer and Ming-Wei Wang.
Discrete Mathematics, Volume 254, Issues 1-3, 10 June 2002, Pages 19-32.

** Maximum Balanced Flow in a Network,
Journal of Combinatorial Theory, Series B, Volume 78, Issue 2, Pages 185-197 (March 2000)
Haggai Ilani and Michael Lomonosov

** On the complexity of the dual method for maximum balanced flows,
Discrete Applied Mathematics, Volume 50, Issue 1, Pages 77-88 (20 April 1994)
Uwe Zimmermann

Balanced linear programming problem
Ahuja, R.K.(Indian Inst of Technology)  Source: European Journal of Operational Research, 101, 1, Aug 16, 1997, p 29-38

Characterizations of max-balanced flows
Rothblum, U.G.;  Schneider, H.;  Schneider, M.H.  Source: Discrete Applied Mathematics, v 39, n 3, Nov 11, 1992, p 241

On-line load balancing and network flow
Phillips, S.(Stanford Univ);  Westbrook, J.  Source: Algorithmica (New York), 21, 3, Jul, 1998, p 245-261












\begin{lemma}
Each multi-flow yielded by step i of the OMFA Algorithm is constrained simultaneously in all links of the minimum fair cut associated with the problem $P_i$.
\end{lemma}
Let consider the set of multi-flows satisfying all constraints associated with the problem $P_i$. Obviously, each multi-flow is constrained in at least one link. Let us denote as {\it minimum fair cut} (associated with the problem $P_i$) the intersection of all those sets of congested links. This set is not empty. Indeed, let suppose by absurdity that at the end of the $i^{th}$ step $(\epsilon=0)$, there exist two multi-flows $\Phi_1$ and $\Phi_2$ satisfying all constraints relative to $P_i$, and the max-min fair share value fixed to $R[i]$. These multi-flows are such that $K_1 \subset K$ (resp. $K_2 \subset K$) represents the set of lastly congested links in $K$ for $\Phi_1$ (resp. $\Phi_2$) and $K_1 \cap K_2=\emptyset$. Let us set $\Phi = 1/2(\Phi_1+ \Phi_2)$. It is obvious that multi-flow $(\Phi)$ satisfies capacity and traffic constraints associated with the problem $P_i$. Furthermore, it is not constrained in any link in $K$ ($\epsilon$ gets a strictly positive value $\forall k \in K$), which contradicts the fact that $\Phi_1$ or $\Phi_2$ are obtained at the end of the $i^{th}$ step. It may easily be shown that this holds even for the  problem $P_1$. We have consequently proved the above lemma.

The uniqueness and the optimality of the obtained solution can be deduced as follows:

\begin{montheo}
The resource allocation vector obtained at the end of the OMFA algorithm is optimally max-min fair.
\end{montheo}

Proof: Let us denote as $R^*$ (resp. $R$) the optimal allocation vector (resp. allocation vector obtained by OMFA), and $\Phi^*$ (resp. $\Phi$) the corresponding multi-flow composed of flowing paths. Let suppose by absurdity that $\exists i$ such that $R^*[i] > R[i]$ and $\forall j < i$, we have $R^*[j] = R[j]$. It can be verified easily that the multi-flow $\Phi$ satisfies all constraints of the problem $P_1$. This proves that it is constrained in all links of the corresponding $MFC_1$. Similarly, it can be seen that the property cited above holds for all $P_j, (j<i)$. According to the Lemma, the multi-flow $\Phi^*$ is constrained in all identical links of consecutive $MFC_j$ sets as $\Phi$. Consequently, $\Phi^*$ also satisfies all constraints of the problem $P_i$, and it could not give a better bound for $R[i]$, which proves that $R^*[i] = R[i]$.



\begdes { \bf Framework of OMFA algorithm, (Optimal Max-Min Fair Allocation computing in a given network.):\\}
{\bf\small Given: The network (topology and link dimensioning), the set of connections resumed in a traffic demand matrix.\\}
{\bf\small Required: The optimal max-min fair allocation vector and the corresponding routing paths.\\}
 \begin{itemize}
 {\it Begin}
    \item [(I)] Set $K := L; i=1$\\
      \item [(II)] Until $(K \neq L)$ and there exists a connection not entirely constrained in $L \setminus K$, do: \\
{\it Compute $R$;}\\ 
{\it Compute $MFC_i$;}\\
 $\forall k \in MFC_i$: Set $S_k := R; K := K \setminus k$;
$i = i+1;$
\item [(III)]For all links $k$ not congested after the final step of the algorithm, set $S_k :=+\infty$.\\
The paths obtained during the last step have the property to optimize the routing from the max-min fairness point of view.\\
{\it End}
\end{itemize}
\enddes