Subject: Re: Manet flooding / broadcasting....

From: [email-masked]
Date: Mon, 7 Jan 1980 16:40:07 +0100 (CET)

Richard Ogier wrote:

> Yes, I agree that this encapsulation should be optional, and
> is done *above* the MANET network layer.  It would be done by
> an application that chooses to treat the MANET like an Ethernet.
> (Some applications may not want to treat the MANET like an Ethernet.)
> The MANET network layer should treat the limited broadcast address 
> 255.255.255.255 exactly as in RFC1812 (i.e., a packet with this address
> should not be forwarded). For example, the MANET might *include* an 
> actual Ethernet as one subnet, and 255.255.255.255 can be used by 
> a MANET router to reach all other routers connected to that Ethernet,
> or more generally to reach all neighboring routers.

We're basically digging up an old question here, however I hope it is
possible for the the WG to reach a concensus. The question is simply one
of how RFC1812 applies to a MANET.

Strictly speaking, according to RFC1812, the expectation of a limited
broadcast is for that to never be forwarded. I.e. in a MANET, a limited
broadcast should reach only the originating nodes neighbors.

However, speaking in terms of applications requirements, it seems to me
that the analogy of a manet on equal terms as an "Ethernet" may be more
appropriate, and hence a limited broadcast should reach all nodes in the
manet (but none beyond the manet). Think dhcp as a possible application in
this context: perhaps one node in the manet acts as dhcp-server, yet this
is not present in all nodes neighborhood.

Either way, I think this is basically a matter of which symbols to
associate with which semantics and mechanisms: it should definitely be
decided, but it should not influence the construction of a broadcast /
flooding protocol.

-- 

-------------------------------------------
  Thomas Heide Clausen
  Civilingeniør i Datateknik (cand.polyt)
  M.Sc in Computer Engineering

  E-Mail: [email-masked]
  WWW:    http://www.cs.auc.dk/~voop
-------------------------------------------

---

From: [email-masked]
Date: Mon, 21 Jan 2002 12:29:40 -0800

Please see my comments below.

> is not present in all nodes neighborhood.

I think we should adhere to RFC1812 if at all possible, and it is possible
simply by letting the encapsulation be optional.
Saying that an application MUST treat a MANET like an Ethernet is like saying
that an application MUST treat an ATM network like an IP subnet (using IP 
over ATM).  A MANET network does not need to be treated like an Ethernet by 
everyone, just like an ATM network need not be treated like an IP subnet.

Since Fred Baker is the editor of RFC1812, I would like to hear his opinion.

Regards,
Richard

---

From: Fred Baker <[email-masked]>
Date: Mon, 21 Jan 2002 14:27:01 -0800

>Since Fred Baker is the editor of RFC1812, I would like to hear his opinion.

I agree. It seems, as I read through the protocols, like there is use for 
something which reaches the immediate neighbors only (such as in "hello" 
functionality) and for something which will proceed some number of hops 
away, usually limited by TTL. It seems to me most consistent if one defines 
local broadcast as reaching exactly those systems whose radios (or 
whatever) can "hear" the original transmission, and no other. If you want 
to provide a particular multicast address which uses some form of RPF 
forwarding up to some distance, you should define that address separately, 
and you should specify exactly what you want the routers to do with the 
packets - repeat on all interfaces (AODV), all interfaces except the 
arrival interface (OLSR), or on an RPF tree away from the source (TBRPF). 
To my mind, those are three different algorithms, and should be specified 
separately.

As to how to specify those routes, I have to say that I (as a router 
vendor) don't particularly want to clutter my routing protocol with 
executing a route selection algorithm based on the arriving destination 
address. I would like to, instead, assume that any non-local addresses will 
simply find an address in a table which I look up using the source and 
destination addresses and perhaps the arrival interface. So I tend to think 
that (as RSVP does) the routing application should receive these multicasts 
and repeat them, rather than asking IP to do that.

---

From: Fred Baker <[email-masked]>
Date: Mon, 21 Jan 2002 15:57:37 -0800

At 02:27 PM 1/21/2002, Fred Baker wrote:
>address.

I mis-spoke. A routing protocol calculates routes; IP forwards using that 
table. I should have said that I don't want to clutter my IP implementation 
with

              if (destination_address == this) { use this route }
         else if (destination_address == that) { use that route }
         else ...
         else { do the normal route lookup to determine what to use }

when some form of standard route lookup does the job.

>I would like to, instead, assume that any non-local addresses will simply 
>find an address in a table which I look up using the source and 
>destination addresses and perhaps the arrival interface. So I tend to 
>think that (as RSVP does) the routing application should receive these 
>multicasts and repeat them, rather than asking IP to do that.

---

From: Joe Macker <[email-masked]>
Date: Tue, 22 Jan 2002 10:58:51 -0500

>simply by letting the encapsulation be optional.

Agreed with the desire to adhere to RFC1812..  As an aside, I think we should apply a well-known local multicast address space (224.0.0.x) for the purposes of flooding routing control data e.g, (ALL_MANET_NEIGHBORS or ALL_PROTOCOLNAME_NEIGHBORS..more specific to particular protocol).  The routing protocol floods its control data internally using these defined locally scoped multicast addresses.  This is consistent with present practice (e.g., OSPF,etc).  

Whether we define or use a generic mechanism for data flooding is another issue and I feel another address space?

---

From: [email-masked]
Date: Tue, 22 Jan 2002 09:20:27 -0800

Fred,

Thanks for your input. It looks like we are close to
reaching a consensus on this issue.

> arrival interface (OLSR), or on an RPF tree away from the source (TBRPF). 

I just want to clarify that TBRPF flooding is not tree-based.
It can be considered to be a variation of RPF (as I mentioned before), 
but to reduce message overhead it does not maintain full broadcast trees. 
Thus, the number of transmissions required to flood a packet to all nodes 
is somewhere between that of classical flooding and tree-based RPF.  
(The same is true for OLSR flooding.)

Regards,
Richard

---

From: "Philippe Jacquet" <[email-masked]>
Date: Wed, 23 Jan 2002 17:44:17 +0100

----- Original Message -----
From: "Fred Baker" <[email-masked]>
To: <[email-masked]>
Sent: Monday, January 21, 2002 11:27 PM
Subject: Re: Manet flooding / broadcasting....

> To my mind, those are three different algorithms, and should be specified
Yes, each protocol has its own way for flooding control traffic. It is clear
that the data can be flooded the same way, but in this case the flooding
would be routing protocol dependent. I know that in DSR broadcast data are
encapsulated in Route Request message. In OLSR the generic broadcast control
traffic format can be used as well.

The question is: is it possible to do with broadcast data the same way as we
did with unicast data, namely to let the IP-stack to do the forwarding alone
and to restrict the routing application to generate routing tables? If the
answer is yes, it is probably worthy to define a common framework for this
forwarding extension. If the answer is no, I agree, the broadcast forwarding
could be just an extension of the unicast routing protocol.

Philippe

---

From: Fred Baker <[email-masked]>
Date: Wed, 23 Jan 2002 17:53:42 -0800

At 08:44 AM 1/23/2002, Philippe Jacquet wrote:
>and to restrict the routing application to generate routing tables?

the problem I come up with is this. Most, perhaps all, of these broadcast 
approaches do not simply say "I received a message on {S,G}, send it to 
this set of interfaces". They say "if my router id or address is not in 
this list..." or "if the message is not in my cache of recently 
retransmitted broadcasts..." or something else.

The IP code wants to be fairly generic; if you have a manet interface and a 
wired interface, there is no reason for the wired interface to have a 
different IP forwarder than yours. If you assume it is designed with a set 
of "adjacencies" which might constitute individual IP routing or ARP 
neighbors, and one of which is "myself" (the "send" routine delivers the 
message upstairs rather than sending it somewhere else), and any given 
route therefore results in a list of zero or more adjacencies to which or 
among which the message is to be forwarded, it wants to look something like 
this (yes I left out the MTU test and all option processing):

ip_forwarding (message *datagram, ip_hdr *ip_header)
{
     if (!verify_checksum (ip_header))
         fail ();
     route = route_lookup (ip_header->ip_destination);
     if (!route)
         fail ();
     if (ip_header->destination is not a class D address)
     {
         adjacency = one_of_the_adjacencies (route->adjacencies);
         interface = adjacency->interface;
         if (interface->ttl_check)
         {       /* we don't decrement TTL when delivering upstairs */
             if (ip_header->ttl <= 1)
                 fail ();
             ip_header->ipttl--;
             ip->checksum = update_ip_checksum (ip->checksum, 0x0100);
         }
         interface->forward_message (datagram, interface,
                                     adjacency->linkheader);
     } else {
         for (adjacency = route->adjacencies; adjacency;
                   adjacency = adjacency->next)
         {
             interface = adjacency->interface;
             if (interface->ttl_check)
             {   /* we don't decrement TTL when delivering upstairs */
                 if (ip_header->ttl <= 1)
                     fail ();
                 ip_header->ipttl--;
                 ip->checksum = update_ip_checksum (ip->checksum, 0x0100);
             }
             if (adjacency->next)
             {
                 make a copy of the message for forwarding purposes;
             }
             interface->forward_message (copy of datagram,
                                         interface,
                                         adjacency->mcastlinkheader);
         }
     }
}

What you're asking for is some form if "if it's going to go out on this 
interface, can we first ask if we think that it should?", and I think 
you're asking for something fairly specific to the address proposed. That 
could be achieved with an API pointer in the interface table that is used 
only in the multicast case:

         if (interface->forwarding_test) {
             if (*(interface->forwarding_test(ip_header, interface)))
                 continue;
         }

placed just before the TTL game in the multicast case. The problem you will 
get into is making it generic to the wired world, which has no such 
problem, and defining one forwarding test for any kind of interface.

Personally, I'd be just as happy to let the routing application handle this 
rather than add to the IP code path.

---

From: Fred Baker <[email-masked]>
Date: Thu, 24 Jan 2002 10:14:17 -0800

More in response to your note from yesterday. As a way of analyzing the 
issues, I'm thinking about the behavior of OSPF in the same case, to ask 
myself what particularly would be different. Guess what; there are quite a 
few differences, and the various manet protocols are obviously optimized in 
various ways to reduce the chitchat from what OSPF would go through.

However, OSPF resolves this re-broadcasting issue quite simply. It floods 
an LSA that it receives if and only if the LSA was not already in its link 
state database, and otherwise ignores it.

It seems that moving the function to the application simplifies it based on 
the application databases, while trying to put it into IP itself makes it 
fairly complex.

BTW, putting it into the application makes the IP TTL unavailable. That 
argues towards an application level TTL for "widening ring" searches.

---

From: "Philippe Jacquet" <[email-masked]>
Date: Fri, 25 Jan 2002 14:27:36 +0100

----- Original Message -----
From: "Fred Baker" <[email-masked]>
To: "Philippe Jacquet" <[email-masked]>
Cc: <[email-masked]>
Sent: Thursday, January 24, 2002 7:14 PM
Subject: Re: Manet flooding / broadcasting....

> state database, and otherwise ignores it.
I agree. OSPF uses the LSA sequence number for this. By the way  the
flooding of OSPF is fairly heavy since it requires ack from neighbors.

> argues towards an application level TTL for "widening ring" searches.

Do you mean that the routing application should decrement TTL and this would
be against the use of some kind of encapsulation/tunneling by routing?

Philippe

---

From: Fred Baker <[email-masked]>
Date: Fri, 25 Jan 2002 08:15:41 -0800

>flooding of OSPF is fairly heavy since it requires ack from neighbors.

true, but I will argue that this is only half the story. OSPF will only use 
broadcast on an interface that supports a designated router. Hence, it not 
only acknowledges on a point to point basis, it forwards the information 
(in a manet, where a designated router election is problematic) on a point 
to point basis.

I bring up OSPF because it is a protocol that is known to work, and has a 
fair bit of mechanism. Anything that is the same is the same, and anything 
that is different is up for review. The review is likely to be favorable; 
the important point is the underlying reason for the difference.

>be against the use of some kind of encapsulation/tunneling by routing?

I mean that if the application wants a TTL (such as in an AODV 
hello-equivalent-RREP or a widening RREQ search, which are both limited by 
TTL), it should put the TTL in the application layer information. The IP 
TTL is not necessarily available to it, and requires changes to IP to make 
use of.

I'm pointing out a layer or API violation in some protocols. The IP header 
is available to upper layers across some interfaces (kernel interfaces, 
usually) but not across socket interfaces. Let's say, for example, that you 
wanted to put such a protocol into my router; the IP header would not 
necessarily be available to the routing protocol, because the routing 
protocol is an application that rides on the IP layer.

---

From: [email-masked]
Date: Fri, 25 Jan 2002 11:23:30 -0800

> (in a manet, where a designated router election is problematic) on a point 

I would say this is much less than half the story, since there
are other factors that make TBRPF and OLSR more efficient than OSPF
in MANETs:

  - OSPF uses classical flooding to disseminate LSA's,
    (except on interfaces that support designated routers),
    whereas TBRPF and OLSR use more efficient mechanisms (based on 
    parents and MPRs) for propagating topology information.  
    (Actually, one could say that these efficient mechanisms are 
    analogous to designated routers, which as you say are problematic
    for MANETs.)

  - OSPF is a full-topology protocol, i.e., every node within a given 
    area is provided with the entire topology of the area, whereas
    TBRPF and OLSR provide each node with only a small part
    of the topology, sufficient to compute shortest paths.
    
  - In OSPF, each HELLO contains the ID of every neighbor, whereas
    TBRPF uses much smaller differential HELLOs, which report only 
    *changes* in neighbor states.

There are other differences (such as the fact that TBRPF does not require 
sequence numbers for topology updates), but I think but these are the main 
advantages over OSPF.

Regards,
Richard

---

From: Laurent Viennot <[email-masked]>
Date: Tue, 29 Jan 2002 11:49:46 +0100

Dear Richard,

I agree that OLSR is an optimized adaptation of OSPF. But I don't follow

 >     *changes* in neighbor states.

As I understand your draft, all neighbors are advertised regularly in
every periodic topology update message (every
PER_UPDATE_INTERVAL). Indeed I had a hard time for figuring that out
from your pseudo-code.

No matter whether you advertise the full list of neighbors in HELLOs
or in TOPOLOGY UPDATES, the overhead is there. What is the right
period for advertising this list is a tuning issue. 

laurent

---

From: [email-masked]
Date: Tue, 29 Jan 2002 11:58:29 -0800

Laurent,

> period for advertising this list is a tuning issue. 

The main tuning issue regarding HELLOs (whether you are talking
about TBRPF, OLSR, or OSPF) is that if HELLOs are sent more
frequently, then the detection of link failures/breakages can be
done more quickly.  Thus it would be good to send HELLOs more
frequently (e.g., every 0.5 sec) if nodes are moving fast.

Since HELLOs are differential in TBRPF, this can be done with a
relatively small increase in overhead.  However, in OSPF and OLSR,
since each HELLO contains all neighbor IDs, this would increase
overhead a lot if each node has a large number of neighbors.

In TBRPF, each node reports links to all neighbors in periodic
topology updates, which are sent less frequently than HELLOs,
just as periodic TC messages are sent less frequently than
HELLOs in OLSR.  For example, in a network with very fast moving
nodes, HELLOs might be sent every 0.5 second while periodic topology
updates are sent every 5 seconds.  Therefore, TBRPF saves a lot of
overhead by reporting links to neighbors less frequently.
(In OLSR, each node needs to advertise its neighbor set more
frequently because this information is needed to select MPRs.)

Another advantage of reporting links to neighbors in topology updates 
instead of HELLOs is that (unlike OLSR) neighbor sensing performs ONLY 
neighbor sensing.  Thus, in TBRPF, neighbor sensing is completely modular 
and separate from topology discovery. In OLSR, each node reports its links 
to all neighbors (and also its MPRs) in HELLOs.  Note that OSPF also
uses HELLOs only for neighbor sensing (even though the HELLOs are
not differential). I really think this is a better approach.

A related issue is that TBRPF also uses differential topology updates
(unlike OLSR) so that a link failure (e.g., detected through link-layer
notification) can be quickly reported with minimal overhead to all 
nodes that are affected by the failure.

I noticed that OLSR allows triggered TC messages to be sent in response 
to link-layer notification.  Since these are full (not differential)
TC messages, I would expect that this will create a lot of additional
control traffic if link-layer notification is used in highly mobile 
networks with a large number of streams.  However, the simulation
study posted a few days (comparing OLSR to AODV) does not use link-layer 
notification (resulting in a packet delivery fraction that is often 
less than 50%), and the ns-2 code for OLSR available from the INRIA 
site does not provide link-layer notification (as does the available 
AODV code and the available TBRPF code at www.erg.sri.com/projects/tbrpf).

I think it is important to conduct simulations that use link-layer 
notification for the following reasons:

  1. It is the only way to achieve a packet delivery fraction close
     to 100% without end-to-end retransmission (which is not acceptable
     for real-time traffic such as voice).

  2. Link-layer notification is usually available on commercially 
     available 802.11 cards (e.g., Cisco Aironet).

Regards,
Richard

---

From: Vikram Kanodia <[email-masked]>
Date: Tue, 29 Jan 2002 15:48:11 -0600 (CST)

Hi,

I had a couple of questions about multirate support of IEEE 802.11. I
will be gratefuil if someone can provide pointers etc...

(*) I know that the PHY preamble and headers are all sent at a basic rate
(1Mbps?). Is the RTS/CTS exchange also done at the basic rate ?

(*)....if not then how do other overhearing nodes latch onto the
RTS/CTS.. ?

Thanks,
-Vikram

-- 

Department of ECE, Rice University | 713 348 3786 (O)| 713 664 5650(H)
WWW: http://www.ece.rice.edu/~kanodia

---

From: Joe Macker <[email-masked]>
Date: Tue, 29 Jan 2002 20:15:19 -0500

Richard/All:

I ran some example OLSR performance curves vs. AODV to check against findings recently presented at the Salt Lake IETF.  I used the same scenarios and cmu tools and was most interested initially in the static topology results since my early OLSR results were very different from those presented.

I posted one OLSR /AODV example output at http://protean.itd.nrl.navy.mil/manet/olsrstatic.pdf
I also used fixed scales to plot since I believe autoscaling plots can overexaggerate the difference s in performance between protocols

In the 100 node case, Ogier's results have OLSR never obtaining more than 65% packet delivery or so.  My results show it achieving close to 100% packet delivery for the lower loading case and retaining reasonable performance as loading increases (it even beat the AODV model with link layer notification in this static example)...yes mobility is more interesting and OLSR degrades, but I am here trying to independently reproduce snapshots of the experiments you presented.

Richard, I feel some of protocol points being raised are valid but I did want to present some results I obtained from running some trials that don't seem to match up with IETF presented results.  I will try and produce some additional mobility curves and post them as well, my initial mobility results for OLSR (Aalborg) also look much better than you presented at the last meeting...(I know I mentioned alot about potential porting problems with jitter, event handlers,etc in the linux based source code you were working with)...not sure any of the differences could be caused by configuration or implementation issues but there must be some differences.

In addition, we have almost completed some other work that is independently developing an OLSR ns2 implementation with optional link layer notification and faster localized MPR state repairing.  This work was being done prior to recent discussions, but I thought I'd mention it since people are discussing it.

-joe

---

From: Ferenc Kubinszky <[email-masked]>
Date: Wed, 30 Jan 2002 09:37:04 +0100

Hello,

> (*)....if not then how do other overhearing nodes latch onto the

Yes, they are. (or maybe at 2 Mbps, I can't remember exactly)
But as I know the some manufacturers sometimes break the standard, use
short preambles, and higher RTS/CTS bitrates to reduce the overhead,
which is really high in the basic case. 
In that case older cards can't communicate, because they can't decode
the CCK "modulation".
Carrier detection still works in this case.

With RTS/CTS mechanism the measured throughput between two nodes
communicating at 11Mbps is smaller by 20% than without RTS/CTS (1500byte
MTU).
Is there any simulation or measurement results that proove the necessity
of RTS/CTS ?

Best regards,
Ferenc

---

From: "Philippe Jacquet" <[email-masked]>
Date: Wed, 30 Jan 2002 11:41:57 +0100

----- Original Message -----
From: <[email-masked]>
To: <[email-masked]>
Cc: <[email-masked]>
Sent: Tuesday, January 29, 2002 8:58 PM
Subject: Re: Manet flooding / broadcasting....

> overhead a lot if each node has a large number of neighbors.
Richard, again, OLSR HELLOs can be partial, you only need to refresh all
neighbors within a certain period, and you can increase the hello rate for
fast moving node. I think Laurent mentioned this to you before. However
don't forget that even the overhead of an empty HELLO can be non negligible.
In IEEE 802.11 the MAC-PHY overhead is around 192 usec (with option to 92
usec) which at 11 Mbps corresponds to approximately 60 IPv4 addresses.

Philippe

---

From: Yang Xiao <[email-masked]>
Date: Wed, 30 Jan 2002 08:33:57 -0800 (PST)

According to the standerd, the control frame data rate may be different
from the data frame rate, and the control frame rate is one among the
basic rate set. For example, in 802.11a, the basic rate set is {6, 12,
24} Mbps. One example of settings is to let the control rate for IEEE
802.11a be 24Mbps if the data rate 24Mbps, 6Mbps if the data rate
<12Mbps, otherwise, is 12Mbps. 

RTS and CTS are control frames, and they are used as RTS-CTS-DATA-ACK.

RTS/TCS is an option of IEEE 802.11 to reduce overhead. However, in a
infrastructure with Ethernet presented as the distributed systemt (DS),
the packet size normally 1500Bytes. In an ad hoc network, the packet
size can be expected larger. 

Regards,

Yang

> Is there any simulation or measurement results that proove the

__________________________________________________
Do You Yahoo!?
Great stuff seeking new owners in Yahoo! Auctions! 
http://auctions.yahoo.com

---

From: Laurent Viennot <[email-masked]>
Date: Wed, 30 Jan 2002 19:10:37 +0100

Dear Richard,

As mentioned by Philippe the overhead of sending a packet is quite
high and makes differential updates significantly less attractive.

But let me try to summarize the advantages of partial HELLOs as used
in OLSR. Notice for example that partial HELLOs allow to make
differential updates since you can advertise a new neighbor at any
time (and also the loss of a neighbor thanks to the LOST_LINK status).
Indeed, partial HELLOs is a very flexible way of advertising
neighbors.

Let me recall the basic principles of partial HELLOs :
- the rule is: any neighbor must be advertised at least once in every
   HELLO_INTERVAL period of time
- the list of neighbors can be advertised in any number of HELLO
   messages during that period of time
- this allows to avoid fragmentation of HELLO messages if their size
   is higher than maximum size of MAC packets (fragmentation should be
   avoided because the loss of one packet will prevent from reading
   other packets)

Link breakage detection is a sensitive part of a MANet and there are
two main ways of doing that in OLSR :
- either you can get link layer notification, and if a node gets a
   link failure notification it immediately sends a HELLO message
   with LOST_LINK status and a correcting TC message if necessary,
- either you can't and then you rely on link hysteresis.
   
Neighbor sensing with link hysteresis is a much more advanced way of
testing links than counting the number of received HELLOs during a
certain period of time. With link hysteresis, the quality of a link is
estimated. If the quality is higher than HYST_THRESHOLD_HIGH, the link
becomes valid. When the quality becomes lower than HYST_THRESHOLD_LOW,
the link is then considered pending and is advertised as lost. Setting
HYST_THRESHOLD_HIGH strictly higher than HYST_THRESHOLD_LOW allows to
cope with dangling links.

If power level is available from the link layer, it can be used for
estimating the link quality and anticipating link breakage. 

When no information is available from the link layer, link hysteresis
uses the reception and loss of control messages for estimating the
link quality. Each time a control message is received, the link
quality is increased and each time a control message is lost, the link
quality is decreased.  The sequence numbers of control messages allow
to detect loss of messages. 

The loss of any control message is a valuable information for
detecting link breakage and link hysteresis allows to do that.

In conclusion, I would say that partial HELLOs together with link
hysteresis is a better alternative than differential HELLOs.

laurent

---

From: [email-masked]
Date: Wed, 30 Jan 2002 12:04:31 -0800

Joe,

> Richard/All:
> 
> I ran some example OLSR performance curves vs. AODV to check against findings recently presented at the Salt Lake IETF.  I used the s
ame scenarios and cmu tools and was most interested initially in the static topology results since my early OLSR results were very diff
erent from those presented.
> In the 100 node case, Ogier's results have OLSR never obtaining more than 65% packet delivery or so.  My results show it achieving cl
ose to 100% packet delivery for the lower loading case and retaining reasonable performance as loading increases (it even beat the AODV
 model with link layer notification in this static example)...yes mobility is more interesting and OLSR degrades, but I am here trying 
to independently reproduce snapshots of the experiments you presented.
> 
> Richard, I feel some of protocol points being raised are valid but I did want to present some results I obtained from running some tr
ials that don't seem to match up with IETF presented results.  I will try and produce some additional mobility curves and post them as 
well, my initial mobility results for OLSR (Aalborg) also look much better than you presented at the last meeting...(I know I mentioned
 alot about potential porting problems with jitter, event handlers,etc in the linux based source code you were working with)...not sure
 any of the differences could be caused by configuration or implementation issues but there must be some differences.

Yes, there must be some differences, since the two versions of the code were written by 
different people.  I will make some effort to determine the reason for the different results, 
but I am also re-running the experiments using the ns-2 code available from the INRIA site.  
Is the Aalborg code exactly the same as the ns-2 code available from the INRIA site?  
Are you using the WaveLAN 802.11 model with 2 Mbps bandwidth?

Richard

> In addition, we have almost completed some other work that is independently developing an OLSR ns2 implementation with optional link 
layer notification and faster localized MPR state repairing.  This work was being done prior to recent discussions, but I thought I'd m
ention it since people are discussing it.

---

From: [email-masked]
Date: Wed, 30 Jan 2002 13:08:24 -0800

Joe,

> Richard/All:
> 
> I ran some example OLSR performance curves vs. AODV to check against findings recently presented at the Sa
lt Lake IETF.  I used the same scenarios and cmu tools and was most interested initially in the static topol
ogy results since my early OLSR results were very different from those presented.
> In the 100 node case, Ogier's results have OLSR never obtaining more than 65% packet delivery or so.  My r
esults show it achieving close to 100% packet delivery for the lower loading case and retaining reasonable p
erformance as loading increases (it even beat the AODV model with link layer notification in this static exa
mple)...yes mobility is more interesting and OLSR degrades, but I am here trying to independently reproduce 
snapshots of the experiments you presented.

We did not run simulations for the static case with 40 sources (which is what you are using)
but we did run 20 m/s with 40 sources, and in this case TBRPF also performed significantly
better than AODV.  These results can be found at the TBRPF site: 
http://www.erg.sri.com/projects/tbrpf/
However, I should note that AODV did not use local repair (but both AODV
and TBRPF used link-layer notification). 

I am thinking of using three different sets of assumptions in simulation experiments:

1. With link-layer notification, buffering of data packets at intermediate nodes allowed
   (In this case, AODV would use local repair.)
2. With link-layer notification, buffering of data packets at intermediate nodes NOT allowed
   (In this case, AODV would not use local repair since this requires buffering at intermediate nodes.)
3. No link-layer notification, buffering of data packets at intermediate nodes NOT allowed.

Any comments?

Richard

---

From: Joe Macker <[email-masked]>
Date: Wed, 30 Jan 2002 15:35:30 -0500

>Is the Aalborg code exactly the same as the ns-2 code available from the INRIA site?  

I don't know that. Perhaps one of the developer's and releasing agents could chime in.

>Are you using the WaveLAN 802.11 model with 2 Mbps bandwidth?

Yes

---

From: [email-masked]
Date: Wed, 30 Jan 2002 16:00:05 -0800

> fast moving node. I think Laurent mentioned this to you before.

Philippe,

Yes, I know that HELLOs can be partial and that each neighbor must be 
included in at least one HELLO every HELLO interval, but unless there 
are too many neighbor IDs to fit into one packet, normally OLSR uses one 
full HELLO per HELLO interval.  (Just check the source code.)

But this does not affect my argument.  What I am saying is that OLSR 
must include each neighbor in a HELLO every HELLO_INTERVAL, whereas 
TBRPF includes each neighbor only in periodic topology updates, which are 
less frequent (e.g., 10 times less frequent if the HELLO_INTERVAL is 0.5 s 
and the update period is 5 s).

It is the HELLO_INTERVAL that determines how quickly a failed link is 
detected, e.g., if no HELLO is received within 3 * HELLO_INTERVAL, then 
the neighbor is declared to be lost.

I also know that OLSR can use differential HELLOs,
since it has recently added the LOST_LINK status (which TBRPF has
had since version 01).  *But this does not change the requirement that 
in OLSR each neighbor ID must be included in at least one HELLO every 
HELLO_INTERVAL.*  You can increase HELLO_INTERVAL, but then it
would take longer to detect a lost neighbor.  OLSR could be *modified* 
so that each neighbor ID is reported less frequently than HELLO_INTERVAL
(as in TBRPF), but I am not sure how this would affect MPR computation.

> However don't forget that even the overhead of an empty HELLO can be non 
> negligible.  In IEEE 802.11 the MAC-PHY overhead is around 192 usec (with 
> option to 92 usec) which at 11 Mbps corresponds to approximately 60 IPv4 
> addresses.

Yes, this is a good point.  With the 92 usec option, this becomes about 30 
IPv4 addresses (or router IDs).  So if a node has 30 neighbors, then a full 
HELLO is about twice as big as an empty HELLO.  I think that's significant.

There are lots of differences between TBRPF and OLSR that can affect
performance, and we have already discussed many of these.
But it is difficult to predict how these differences affect performance.
That's what simulations are for.

Regards,
Richard

---

From: Laurent Viennot <[email-masked]>
Date: Thu, 31 Jan 2002 11:09:59 +0100

Dear Richard,

Please take a look at previous mail about partial HELLOs in OLSR. I
have to correct some points you mention here about OLSR that are wrong.

laurent

 > full HELLO per HELLO interval.  (Just check the source code.)

In the released code yes but the draft allows to do differently.

 > the neighbor is declared to be lost.

No, with link hysteresis, you can detect the loss of packet also through
missing sequence numbers.

 > had since version 01).  *But this does not change the requirement that 

No, LOST_LINK status is mentioned since version 02 of the OLSR draft
and was included in HIPERLAN type 1 standard, so it is an old idea.

---

From: [email-masked]
Date: Thu, 31 Jan 2002 13:07:25 +0100 (CET)

> At 12:04 PM 1/30/2002 -0800, [email-masked] wrote:

<SNIP>
 
> I don't know that. Perhaps one of the developer's and releasing agents

The ns2-code, currently available from the INRIA www-site, is equivalent
with what Joe refers to as the Aalborg code.

--

---

From: [email-masked]
Date: Thu, 31 Jan 2002 13:14:01 +0100 (CET)

> full HELLO per HELLO interval.  (Just check the source code.)

Richard,

Please keep seperate implementation choises from protocol specifications. 

In the current implementation, it may be chosen to use full HELLO's. It
is also chosen not to use link-layer notifications. However, as is
mentioned elsewhere on the list (by Laurent), another possible choise
would be to include link-layer notifications and trigger partial HELLO's
as a result hereof.

While not provided by the implementation you are using, it cirtainly is
permitted by the protocol specification.

--

---

From: [email-masked]
Date: Thu, 31 Jan 2002 04:51:44 -0800

Laurent,

> have to correct some points you mention here about OLSR that are wrong.

See below.  

> missing sequence numbers.

Right (that's why I wrote "e.g."). 
But this has no effect on my main point, which
is that differential HELLOs can save bandwidth.

>  > HELLO_INTERVAL.*  

You are right that OLSR *mentioned* the LOST_LINK status before,
but it did not actually use it in HELLOs.

Richard

---

From: Laurent Viennot <[email-masked]>
Date: Thu, 31 Jan 2002 15:40:14 +0100

Dear Richard,

I still disagree.

 > is that differential HELLOs can save bandwidth.

I don't think that sending almost empty packets is a gain of bandwidth. If
you want to say I am alive, any control packet is good for that and
will carry more valuable information. Link hysteresis allows to consider
any control packet as a << I am alive >> packet. 

 > but it did not actually use it in HELLOs.

It was used in the implementation released for draft 03 (even if this
implementation is very basic and do not take advantage of all OLSR
features), it is just a matter of maturation of the draft.

I think our misunderstanding comes from different views of neighbor
sensing. There are many features in neighbor sensing :
- 1 - detecting new neighbors
- 2 - checking bi-directionality of links
- 3 - detecting link breakage
- 4 - advertising list of neighbors

 From your point of view 1,2,3 is done through Hello messages and 4
through Topology updates.

 From the OLSR point of view 1,2,4 is done through Hello messages,
and 3 is done through link hysteresis which uses all control messages
and possibly link layer notifications.

Wether 4 is part of the neighbor sensing or not  can be debated, but
it is not very interesting. In OSPF, it is included in both Hello
messages and Topology updates. When optimizing bandwidth utilization
it is logical to advertise the list only once. The reason for putting
4 in the neighbor sensing in OLSR is that neighbor sensing can be seen as a
lower layer that provides also an optimized flooding mechanism.

Your point is doing 1 and 3 at a higher rate than 4. Partial HELLOs
and link hysteresis allow to do that more efficiently than
differential HELLOs because they are more flexible. You can advertise
a new neighbor at any time with partial HELLOs, so doing 1 at a higher
rate is no problem. As mentioned Thomas, if you send an additional
HELLO message then you would probably glue a part of your neighbor
list with it to send more information in the packet and save some
bandwidth with regards to packet overhead.

Doing 3 at a higher rate is implementation dependent and OLSR link
hysteresis mechanism is very flexible about that: you can use link
layer notification of link breakage, or link layer notification of
power level or loss of control messages. For example, if you split
your list of neighbors in 10 HELLO messages, you will be able to
discover link breakage 10 times quicker than with only 1 HELLO message
(at the cost of more overhead).

It is logical to send more control data when mobility increases.
Partial HELLOs allow to react smoothly.

laurent

---

From: [email-masked]
Date: Thu, 31 Jan 2002 11:24:55 -0800

> with what Joe refers to as the Aalborg code.

I think I found a bug in that code regarding packet size.  (I don't know whether the 
same bug is in Joe's code or in the code used for simulations that others have done.)
When running simulations with that code, I noticed in the trace file that every
OLSR packet has length 20 bytes, including the 20-byte IP header (i.e., ns-2 
considers each OLSR message to have zero length not including the IP header).

So I looked in the file ns-olsragent.cc and noticed the line

    ch->size() = IP_HDR_LEN;

in the sendPacket() function, which explained the bug. I changed the line to

    ch->size() = IP_HDR_LEN + p->datalen();

which seemed to fix the bug.  Am I missing something?

Richard

---

From: Joe Macker <[email-masked]>
Date: Thu, 31 Jan 2002 19:21:16 -0500

>which seemed to fix the bug.  Am I missing something?

Richard:
Good catch, I also believe this a bug.  I checked prototype olsrv4 ns2 code we developed here and it does not have this bug (it was independently developed from the INRIA code).

I will add your fix and doublecheck my previous snapshot scenarios with both pieces of code.  The initial points are still looking similar from running our code, although this is a third piece of code (its going to take awhile to get the full curves again)..

---

From: [email-masked]
Date: Thu, 31 Jan 2002 11:24:55 -0800

ch->size() = IP_HDR_LEN;

Richard