[1421] in Commercialization & Privatization of the Internet
Re: Volume-sensitive charging
daemon@ATHENA.MIT.EDU (vlad@erg.sri.com)
Mon Sep 30 18:18:01 1991
To: com-priv@psi.com
Cc: vlad@erg.sri.com
Date: Mon, 30 Sep 91 13:39:24 -0700
From: vlad@erg.sri.com
SEAN@SDG.DRA.COM (Sean Donelan):
The problem isn't that bad when the packets get there. The harder
problem is what happens when the packets don't get there.
With the current Internet providers all you get for your flat rate
pipe is the right to compete. If your packets don't get through,
oh well. You pay the same rate whether or not your packets ever
reach their destination. That flat rate can be real cheap if those
packets make it, but how much is it worth if those packets don't.
...
No refunds for lost packets.
I would like to share the results of
ours on the subject of billing in lossy internets. They are rather
mathematical and maybe not very specific, but that was the idea: to keep
discussion as general as possible. I think these results could
form a foundation for more detailed discussions of billing in most lossy
internets. These results were published at INFOCOM '91. Here is a 2-page
summary in LATEX.
The reason I am sending this is that I am interested in your opinions and
suggestions. In particular, I would like to know if there are any
interesting related issues that somebody can think of.
Also, the paper contains our preliminary thoughts on the crucial subject of
accounting, i.e., counting the numbers of delivered and lost packets.
However, I think this issue remains wide open.
\documentstyle [11pt]{article}
\begin{document}
{\large\bf FAIR CHARGING POLICIES AND MINIMUM-EXPECTED-COST ROUTING
IN INTERNETS WITH PACKET LOSS}
Our paper presents a rigorous and general approach to one of the most
important (and previously unresolved) research issues in internetwork
accounting policies: the issue of fair,
efficient billing and cost recovery policies in internets and, in
particular, the highly difficult aspect
of billing and routing in internets comprised of potentially lossy
ADs, i.e., ADs that sometimes lose or drop packets.
In this paper \cite{snipe},
we propose an economics-based definition of fair pricing and
derive fair, simple, and mathematically sound charging policies that
properly handle costs and risks in lossy internetworks. We also describe
simple and efficient source-based algorithms (having both link-state and
distance-vector versions) for computing the
optimal routing tables with respect to the new charging measures.
These charging measures and algorithms have the property that,
by minimizing the individual domain's expenses, they also minimize the
global resource consumption over all possible paths and flows. All of the
above results and algorithms hold when we replace ``price'' by ``delay''.
We assume that the Internet consists of many individual ADs. Each of
these ADs is attached to some other ADs through gateways. In the basic
mathematical model, we represent the Internet by a graph $G$, each AD as a
node in $G$, and draw a link between any two nodes that are physically
attached to each other
through gateways. This model will be used throughout most of this paper
unless stated otherwise. This is not the most detailed model, because in
reality each AD, represented here as a node, is a large network in itself,
consisting of many switching nodes and hosts.
We are concerned with the billing policies for important or necessary
packets, i.e., those packets whose loss requires retransmission. We
consider the two basic retransmission policies. The first policy,
referred to as {\it route-based}, assumes that the source keeps a copy
of the packet and retransmits the packet if it gets lost.
The second, referred to
as {\it hop-based}, assumes that a copy of the packet is
kept at each intermediate AD until that AD knows that the packet has
successfully cleared the next domain. The AD will
retransmit the packet if it gets lost in the next domain.
This paper concentrates on the {\it route-based}
policy because it involves more difficult mathematical issues.
However, the corresponding results for the {\it hop-based} policy are also
presented.
We have developed
cost recovery schemes that assign fair wages to individual domains for
successful delivery of packets and fair penalties for losing packets.
These methods ensure that each domain breaks even in the long run.
The new prices (wages) reflect both the
delivery costs and the risks of losses in an economically optimal way.
In particular, we define the notion of price fairness.
We consider a packet transiting through $k$ administrative domains
$N_1, N_2, . . . , N_k$ on its
path $P$ from the source $s \in N_1$ to the destination $d \in N_k$.
Let $c_i$ denote the cost that domain $N_i$ incurs for handling this
packet, and let
$p_i$ denote the probability of a packet getting lost inside domain $N_i$.
Let $e_i$ denote
the fair tariff that domain $N_i$ should charge to the sender for
successfully transitioning a packet, and let $u_i$ denote the penalty
that domain $N_i$ should pay to the sender for losing a packet.
The fairness considerations imply that the price $e_i$ is {\it fair}
if it allows region $i$ to break even in
the long run, i.e., the expected return $Q_i$ should be equal to 0.
Fair pricing policy should be as follows:
If domain $N_i$ loses the packet, it should reimburse the client in the
amount $u_i$ equal to $E_{i-1}$.
If domain $N_i$ successfully transitions the packet, it
should be paid by the client in the
amount of \[e_i = \frac{p_i E_{i-1} \ + \ c_i}{1-p_i}.\]
Here $E_{i-1} = \Sigma_{j=1}^{i-1} e_j$ denote the total price accumulated
by a packet entering domain $N_i$.
We also present efficient algorithms
for finding the least expensive (with respect to the above prices $e_i$)
paths between different pairs of domains in lossy internets.
We derive that, given a fixed path $P$, the total price $J_P$ for
successful packet delivery from source to destination
along the path $P$ is given by:
$J_P = \frac{\sum_{i=1}^k c_i R_{i-1}}{R_k}$, where
$R_0 = 1$ and $R_i = (1-p_1) (1-p_2) (1-p_3) \cdots (1-p_{i-1})(1-p_i)$.
Based on this new price measure, one can now try to find the path that
minimizes the value of $J_P$. Because the price $J_P$ is in our case
a function of the total accumulated cost, the choice
of the future portion of the path depends on its past.
Because of this fact, the commonly used, efficient
destination-based versions of algorithms (Dijkstra, Bellman-Ford) for
computing optimal routing do not work with respect to the new measure.
The lack of a Dynamic Programming approach results in highly burdensome
algorithms with exponential time complexity.
The problem of prohibitively high algorithm complexity
can be resolved by the following idea: compute optimal routing from
a fixed source $s$ to all destinations,
rather than from all sources to a fixed destination $d$
The efficient DP algorithms are applicable to this approach because the
memoriless property holds in the backward direction, i.e., the portion of an
optimal path before some intermediate node $w$
is independent of the path after $w$.
Thus, the equally
efficient source-based versions of these algorithms do work, providing an
efficient means of computing optimal routing between different
source-destination pairs. If the network protocols are link-state, the most
efficient approach is to use
``reversed'' versions of the SPF (Dijkstra) algorithm.
If the network protocols are distance-vector, the best
approach is to use reversed versions of the
distributed Bellman-Ford algorithm.
An important aspect of the results of this paper is that, no matter
what individual billing
policies are, this paper's measures and algorithms
should still be used in order to minimize the average global resource cost of
successful packet delivery.
Namely, given a path $P$ in $G$, the expected total system
cost with retransmission until successful delivery is proved to be
equal to $\frac{\sum_{i=1}^k c_i R_{i-1}}{R_k}$, which is
exactly equal to the path cost $J_P$ derived in the previous paragraphs.
Thus, the optimal routes with respect to $J_P$ also minimize the global
resource use.
\begin{thebibliography}{10}
\bibitem{snipe}
V. Rutenburg and R. Ogier,
\newblock Fair Charging Policies and Mininmum-Expected-Cost Routing in
Internets with Packet Loss.
\newblock In {\em Proc. IEEE INFOCOM'91}, pages 279--288, Miami, FL, April
1991.
\end{thebibliography}%{10}
\end{document}
