Subject: JJ's path metric thoughts

From: Chip Elliott <[email-masked]>
Date: Tue, 22 Sep 1998 08:51:25 -0400

JJ,

As usual, I find my head vigorously nodding up and down as
I read your thoughts. Yes, brother, how true!

>
>Least-interference paths and smallest-delay paths need not be the
>smallest hop count paths. If traffic and interference patterns
>fluctuate, incremental routing delivers packets over "shorter" routes
>than a source routing, where "shortest path" does not mean smallest
>number of hops, but any or a combinatioin of delay, least
>interference, etc.....so what we may argue?.....
>

So there are (at least) two intertwined issues here: 1) a path
metric for radios is probably more than just a hop count; and 2)
the metrics along parts of paths may change faster than can be
handled via source routing.

The first part can be extremely important in practice. Let me give
a concrete example. Suppose we have a number of radios outdoors,
and one of them is on a hill or atop a building. In naive algorithms,
it will become a "neighbor" with nearly all the other routers, and
as a consequence the "best path" for much of the traffic will go
through this one radio. That means that this one radio becomes
the bottleneck for all network traffic, even if there are plenty
of other unused paths (eg via multiple hops around the hill).

The second part, I think, can only be characterized via simulations.
Certainly my intuition just goes blank when asked how paths might
fluctuate, whether local repair is better than end-to-end, etc.
I say, may CMU (or whoever) grind the numbers and then we will
be enlightened. Or perhaps endarkened.

My own belief here has been strongly influenced by Martha Steenstrup:
different types of traffic have quite widely varying needs, and
so the "metric" is really application dependent. As an obvious
example, voice packets are very delay sensitive, but much bulk
data traffic is less so. Voice could take a much higher bit error
rate, though (if the packets can be so encoded). As a less obvious
example, TCP traffic used for web browsing should perhaps follow
a different path [eg low delay] than that used for bulk data transfer.
Hence it might be better to NOT have the network create a sort of
"one size fits all" path metric, but rather reflect up salient
aspects of the path to the application level, so the application
can make a good choice. (Martha if my version of your thoughts is
straying too far from your influence, I apologize!)

>
>If we want the routing to be "efficient" under traffic and
>interference fluctuations, we cannot do routing as the Internet does
>(paths areindependent of traffic over them) and we have an
>"interesting" problem at hand, no matter which type of routing we
>choose!
>

As I'm sure JJ knows well, there is a very-hard-to-fathom feedback
loop here -- the grand feedback loop of radio routing. Sending traffic
along a given path will CHANGE the metrics *not only* for that path,
but for all paths that are within radio range of those transmissions.
It hardly matters what one uses as the basis for a metric --
channel access time, frame completion rate, decoding error rate,
etc. Each will get worse as there's more traffic within an area,
and/or as the receivers gets busier. This seems to me that hardest,
most deeply problematic part of ad hoc networks.

Even if one considers the simplest reasonable metric (hop count),
there's some reason to believe it too varies with traffic. I've heard
from our cellphone brethren that CDMA cells "breathe" with traffic;
the effective radius of a cell expands under light call loads, and
shrinks under heavy loads. Evidently this is a not-subtle effect.
We might well see similar effects in CDMA multihop networks, where
"neighbor relationships" alter dramatically under heavy traffic
loads: if there's a lot of traffic in my area, I will lose direct
connectivity to my farthest neighbors. This is a hypothesis; I don't
know of anyone who's investigated this effect.

>
>I'd like to reach some consensus on what is a MANET acceptable
>characterization of a QoS path and the associated link
>parameters.....I am working on the problem and am eager to use good
>ideas from anyone, specially from this list!
>

JJ, here I'd say the situation is HOPELESS. Even within wired
networks -- after years of debate -- there's still profound disagreement
what QOS means. Witness the diff-serv wars. My guess is that we'll
all just have a proceed on our own, without consensus. Maybe
someone will stumble on something that really works!

cheers and best wishes,

-- Chip

---

From: "M. Scott Corson" <[email-masked]>
Date: Tue, 22 Sep 1998 09:43:54 -0400 (EDT)

> I read your thoughts. Yes, brother, how true!

Yes...I also agree with much of what JJ said Friday (and you say today).

It's clear that what goes on inside these networks is far from obvious...
lots of highly-nonlinear effects to be found...I wonder when someone
from Bellcore will measure self-similarity here as well ;-)

Given that we don't really understand all of what going on inside...

Regarding performance issues, I'd like to find consensus on 
*external* measures of fitness, i.e. external to the little 
black box we are testing called a network...for starters...
If we are interested in supporting good old, connectionless best effort
service,  how about?

1) Avg. data packet throughput

2) Avg. data packet delay (perhaps variance too)

3) Avg. route acquisition delay (variance too)

These are independent of any given routing algorithm.  From an
external perspectve, one doesn't really care *how* a network 
accomplishes its task--simply *what* are the final effects on data traffic.

Internal measures (e.g. control bits transmitted, how many hops a packet took) 
can be examined to gain an understanding of a protocol's behavior, 
to understand how efficiently it does the job--in essence, 
*why* the effects observed in the data performance are present,
but this matters little to users of the network layer.

Another external measure could be

4) Percent unordered data delivery (in a session)

as this might affect services preferring ordered delivery.

Others???

-Scott

---

From: Jose Garcia-Luna <[email-masked]>
Date: Tue, 22 Sep 1998 14:28:59 -0700

> handled via source routing.

^`'^`'^`' <-- vigorous nodding .....:)

> The first part can be extremely important in practice.

^`'^`'^`' <-- more vigorous nodding .....:)

> The second part, I think, can only be characterized via simulations....

YES!  if we want a predictive measure of the complete behavior
of the routing protocol. 

However, a comparative model could be derived for basic aspects of the
time response of the protocol. Any routing protocol has local actions
(e.g., deciding what percentage of traffic for a destination to send
through a neighbor) and coordinated actions (e.g., computing QoS
paths). A crude way to predict the behavior of a protocol is based on
its response to an impluse or step function. LIke any control system,
given a change in traffic load (e.g., a new ucsc grad starts web
srufing....again!) or capacity in the network (e.g., due to a resource
failure) the protocol will try to adapt to deliver pkts "efficiently"
(e.g., min-delay paths). Because it takes time for routers to
communicate with neighbors and for info to propagate across the net,
the adjustment of the protocol will take some time. If the protocol is
too conservative, the response is underdamped and we end up wasting
bandwidth; if the protocol is too agressive (or has no clue, like OSPF
:-> and uses a single path for a destination) the response is
underdamped and we end up with much higher delays.  The necessary and
sufficient conditions for min-delay routing were given by Gallager
[Trans on Comm, Jan 77] the problem is that the theory applies to
static nets only....to make a long story short, we need to manage the
delays by smoothly shifting load from congested neighbors to uncoseted
neighbors.  Assuming a single step input (e.g., a node fails, a new
flow starts) we can look at how the network responds (delay in pkt
delivery). What to watch for: the size of the peak in the underdamped
response and the time it takes for the net to reach
equilibrium.....why? drastic changes in mobility and traffic load
amount to a whole bunch of impluses and step functions on top of other
smooth variations. A protocol that is too underdamped (e.g., it
requires data to traverse the whole network) in responding will lead
to longer delays in practice...I have done simulation work, but would
love to see some analysis on this!

> I'd say the situation is HOPELESS. 

I feel your pain :-).....I'll proceed with delay measures appropriate
for wireless with added constraints....

Cheers,

JJ

---

From: Rajesh Talpade <[email-masked]>
Date: Tue, 22 Sep 1998 18:12:56 -0400 (EDT)

> as this might affect services preferring ordered delivery.

Extrapolating 4 a bit, how about percent data pkts lost, or percent
connectivity between nodes is lost. This would reflect how
efficient and robust the protocol is. Efficient 'coz excessive b/w 
usage for signaling by the protocol may result in data pkt loss. A 
robust protocol would recover quickly from path failures, resulting in 
a lower percent of loss of connectivity.

Rajesh.

-- 
Rajesh R. Talpade    [email-masked]   973 829-{4261, 5888(fax)}
Research Scientist, Bellcore, 445, South St, Morristown, NJ-07960

---

From: Ken Carlberg <[email-masked]>
Date: Tue, 22 Sep 1998 18:33:36 -0400

> ....to make a long story short, we need to manage the
> neighbors.

i'm sympathetic, but i'm also a bit weary about the notion of "shifting
load", smoothly or otherwise, without any built-in incentive or dampening
affect to prevent oscilation.  

we can probably constrain the shifting so that certain apps, like email,
never get shifted unless there is loss of connectivity.  but that only
(potentially) reduces the problem space. we still need a threshold or
incentive to prevent dramatic shifts that can lead to bursts, which could
lead to sunami's :-)

so while i'm in agreement with chip/martha's view of having a more
application-based influence on what the network does, this may not be
enough -- i'm assuming we don't have something like rsvp/GS providing
the net with hard delay/load boundaries to rely on.  so perhaps this means 
keeping some history (maybe like EWMA) at the edges of the net to make a 
more intelligent decision as to when to shift. just a thought.

-ken

---

From: Jose Garcia-Luna <[email-masked]>
Date: Tue, 22 Sep 1998 15:46:56 -0700

> affect to prevent oscilation.  

Glad to hear that you appreciate the complexity of the problem...With
some luck, I hope I can convince this group in the not so distant
future that this can be done in a very practical way in a dynamic
network, and without oscilations.

> incentive to prevent dramatic shifts that can lead to bursts, which could

Since I see a way out of oscillations, I don't agree with you on
establishing constraints on how to forward flows based on
applications....

> more intelligent decision as to when to shift. just a thought.

Well, to me applications are a necessary evil to show how great
routing protocols work :-)....the application has a contract with the
little people (lower layers) and should not care about what the little
people do as long as the contract clauses are met....I am assuming
that we don't have RSVP too.....I am interested in hearing how we can
write the contract between applications and network (i.e., how do we
specify and quantify the QoS requested).

JJ

---

From: Joe Macker <[email-masked]>
Date: Tue, 22 Sep 1998 19:47:01 -0400

At 02:28 PM 9/22/98 -0700, Jose Garcia-Luna wrote:
>static nets only....to make a long story short, we need to manage JJ:

Yes, there really is good foundational theoretical background for static
networks.  Expanding more analytical knowledge in the mobile net domain is
quite a worthy quest! In short, I feel the present pain also ;-) and am
interested in hearing more details on properly damped "load shifting"
approaches that achieve good utilization within mobile networks.  Sounds
like you are in progress on an approach.

The "impulse response" analogy is an interesting one and has been used to
good effect in dynamic congestion estimation and adaptation also. Hmm...I
digress.  until there is more...

Cheers,
-Joe

---

From: Jose Garcia-Luna <[email-masked]>
Date: Tue, 22 Sep 1998 18:17:29 -0700

> If we are interested in supporting good old, connectionless best effort

I submit that providing 1 to 4 in your list is good for datagrams but
is also good for any type of e-t-e service. Let's not forget that the
service to be provided by the network does not dictate how traffic
flows inside the network, e.g., I should be able to provide the
equivalent of a telephone call across a network even if it does not do
circuit switching.

I like 1 to 3....Just to clarify, throughput means new good packets
received at the network end (we are not including retransmissions of
same  packets). Delay variance is important too!

I think (3) [route acquisition delay (variance too)] plays a role in
resilient transmissions (pkts that have to arrive withina time window)
and a role in the ave delay.

Why is (4) important? ordered delivery can be done e-t-e within a
wireless net....of course, we need something at the transport level if
we need e-t-e in order delivery across nets.  TCP assumes FIFO
delivery of packets, but that does not mean that all transport
protocols should.

Now, how do we quantify the requested values of 1 to 3? Does this mean
I will try to choose next hops or do source routing over paths that
for example, have no more than 1msec ave delay, no more than 5% delay
variance, and no less than 100kbps?

I will think about "others"....

JJ

---

From: "M. Scott Corson" <[email-masked]>
Date: Tue, 22 Sep 1998 21:29:41 -0400 (EDT)

> underdamped and we end up with much higher delays.  The necessary and
  ^^^^^
JJ, do you mean to say...

  too conservative = underdamped
  too aggressive   = overdamped

or is every non-ideal response considered underdamped in your model?

Nevertheless, it sounds cool.  I sometimes think of Gallager's classic
paper when I sit idle on the Beltway (as I did today coming home, 
wishing for an alternate route...;-)

-Scott

*******************************************************************************

M. Scott Corson                                 Institute for Systems Research
[email-masked]                              A.V. Williams Bldg. (115)
Phone: 301-405-6630 (Rm. 2205 AVW)              University of Maryland     
Fax:   301-314-8586                             College Park, MD  20742

*******************************************************************************

---

From: Jose Garcia-Luna <[email-masked]>
Date: Tue, 22 Sep 1998 18:47:13 -0700

Scott:

I guess I was thinking that a routing policy is too aggresive when it
reassigns large chunks of traffic at once, so single-path routing
protocol is as aggresive as you can get, because it switches all
traffic to a destination from one path to another and ends up
ping-ponging.

In terms of control, I guess we want a routing policy with a damping
factor slightly less than 1, which means a tiny overshoot but quick
response.

JJ

---

From: "Miguel Sanchez" <[email-masked]>
Date: Wed, 23 Sep 1998 10:26:35 -0000

> specify and quantify the QoS requested).

Ok, one idea may be to establish a contract clause depending on port
numbers. User could configure a node with differents needs
(Throughput/Delay/stability of route) by asigning the proper value to the
port number it uses. In this way there is no need to path any application
but you could benefit of several QoS suited for each application.

Miguel Sanchez

---

From: Ken Carlberg <[email-masked]>
Date: Wed, 23 Sep 1998 12:49:56 -0400

> we need e-t-e in order delivery across nets.  

my undertanding is that there are 'measures' of ordered delivery. i think
it was fred baker on the diff-serv list that mentioned that TCP can 
really crumble when the degree of unordered packets for a flow reaches a 
certain threshold.  hence, it would be desirable to reduce, within reason, 
the degree by which packets are delivered out of order -- or at least not
promote it any more than what would normally be generated by the network.

> TCP assumes FIFO

tcp may flourish with fifo, but with diciplines like CBQ, i don't
think it can assume this model as being homogenous any more.

but do i think that (4) should be included as a direct responsibility 
of the network?  no, i'd prefer to keep things simple and try and map
or force fit requirements/impact to what should be expected from the 
network.

-ken

---

From: Jose Garcia-Luna <[email-masked]>
Date: Wed, 23 Sep 1998 17:44:58 -0700

Ken:

TCP does crumble with unordered delivery (folks at Metricom have
experience with that)....However, depending on the retransmission
strategy inside the wireless net, out-of-order delivery *will* happen
even with single-path routing (ask Metricom), because nodes move and
links and nodes fail....TCP's limited design has to be fixed, even if
we assume single-path routing in an ad-hoc network.

Since single-path routing does not help TCP taht much anyway, we
should do the most survivable and efficient routing we can, and we
should provide e-t-e services on top of that (with patches to TCP at
the e-t-e net layer or TCP extensions).

JJ

---

From: Zygmunt Haas <[email-masked]>
Date: Fri, 25 Sep 1998 08:20:07 -0400 (EDT)

Hi Everyone:

Two references to M. Pursley's papers are:

M.B. Pursley, "Investigation of least resistance routing in SINGARS packet
radio network," Proc of the 1996 Tactical COmmunications Conference, Fort
Wayne, IN, April 30-May 2, 1996

M.B. Pursley, "Routing in frequency-hop packet radio networks with
partial jamming," IEEE Trans. on Comm., vol.41, no.7, July 1993

Zygmunt Haas.
==-=-==-=-=-=-
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
Prof. Zygmunt J. Haas             tel: +1-607-255-3454
Wireless Networks Laboratory
323 Frank Rhodes Hall             fax: +1-607-255-9072
School of Electrical Engineering
Cornell University                e-mail: [email-masked]
Ithaca, N.Y. 14853
U.S.A                             http://www.ee.cornell.edu/~haas/wnl.html
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-

On Thu, 24 Sep 1998, M. Scott Corson wrote:

> On Thu, 24 Sep 1998, Joe Macker wrote:
>
> > There was a related downloadable presentation referenced at the site
> > http://www.isr.umd.edu/Courses/Workshops/MANET/program.html
> > which is the DARPA/ARO Workshop on MANET site from March 1997.
> > When I try to download its not found. Scott? it this around somewhere.
>
> Actually...all that is there is a .ps file of the LRR paper I
> think...never got the slides from Mike.
>
> > >
> > >LRR is like the SURAN routing protocol (Bellman-Ford) but the metric
> > >used is different and based on interference. I like the metric, but do
> > >not support the use of distributed Bellman-Ford as the underlying
> > >routin algorithm.
> >
> > Vigorous nodding..
> >
>
> Poor Bellman-Ford...;-(...it really is a good idea--in principle.