Subject: CBRP new draft and simulation code(ns)

From: "mingliang jiang" <[email-masked]>
Date: Mon, 05 Jul 1999 10:02:31 -0700

Hello,

A copy of our much revised CBRP draft is now available
at http://cram.comp.nus.edu.sg:8080/cram/cbrp
Our appologies for missing the submission deadline,
and we will submit after the Oslo meeting.

CBRP has been simulated in ns2 with CMU's wireless
extension. The simulation code is available on the CBRP 
webpage for download.

The new CBRP draft features "route shortening" and
"local repair", which further improves CBRP's performance.
A rough performance comparison between CBRP and DSR
is also made available as part of a ppt presentation
on the webpage.

An abstract of the ID is attached below.

Cluster Based Routing Protocol (CBRP) is a routing protocol designed
for use in mobile ad hoc networks.  The protocol divides the nodes of
the ad hoc network into a number of overlapping or disjoint 2-hop-
diameter clusters in a distributed manner.  A cluster head is elected
for each cluster to maintain cluster membership information. Inter-
cluster routes are discovered dynamically using the cluster
membership information kept at each cluster head.  By clustering
nodes into groups, the protocol efficiently minimizes the flooding
traffic during route discovery and speeds up this process as well.
Furthermore, the protocol takes into consideration the existence of
uni-directional links and uses these links for both intra-cluster and
inter-cluster routing.

This updated draft has a more detailed description of the cluster
formation and routing process. In addition, it describes 2 major new
features that have been added to the protocol: route shortening and
local repair.  Both features make use of the 2-hop-topology
information maintained by each node through the broadcasting of HELLO
messages.  The route shortening mechanism dynamically shortens the
source route of the data packet being forwarded and informs the
source about the better route.  Local route repair mechanism patches a broken
source route automatically and avoids route rediscovery by the source.

Regards,
Mingliang & Jinyang

Join 18 million Eudora users by signing up for a free Eudora Web-Mail account at http://www.eudoramail.com

---

From: Dave Johnson <[email-masked]>
Date: Mon, 05 Jul 1999 15:05:32 -0400

>is also made available as part of a ppt presentation

Mingliang,

I agree that CBRP has some interesting features, but in looking at
the performance evaluation you mentioned in your message, I see two
problems right away:

 - Your comparison with other routing protocols (including DSR)
   neglects to mention the rate at which you exchange the HELLO
   messages, and it seems from your graphs that you don't count
   these in your "overhead" figure.  Your revised draft also does
   not say what the appropriate "HELLO_INTERVAL" value should be.
   DSR, on the other hand, uses *no* messages like this of any kind,
   so it is not fair to DSR and to the other protocols to ignore
   such HELLO messages (or any other periodic messages of any kind)
   in your calculation of overhead.  If you included these
   additional overhead packets in your evaluation, the overhead
   of CBRP would go up significantly.

 - You mention in the powerpoint slides that simulations have shown
   that RIP, OSPF, and DSDV fail to converge in highly dynamic
   environments.  At least the DSDV results you mention here must
   be our results from MobiCom'98, and there, the reason DSDV
   failed to converge was due to the use of the periodic 
   messages from each node.  For mobility beyond some average
   rate, such periodic messages cannot be sent frequently enough
   and thus routing tables get out of date and packets cannot be
   routed correctly.  DSDV tries to solve this with triggered 
   updates, as it seems does CBRP too, but we found for DSDV at
   least, that it still wasn't sufficient for keeping the routing
   tables up to date.  It seems that CBRP, with its periodic HELLO
   messages needed to maintain the clusters, would suffer from
   exactly the same problem, in at least some environments.
   Have you studied this problem?

					Dave

---

From: Jiang Ming Liang <[email-masked]>
Date: Tue, 6 Jul 1999 14:44:10 +0800 (SST)

Hi Dave,

  Thanks for the comments!

>    of CBRP would go up significantly.

  Oops, there should have been a section in the draft about the
constants and suggested values. ( I've now added in that section.)
Actually it is also clear in the simulation code the HELLO_INTEVAL
values we have used for CBRP. We have tried both values of 1.5 seconds
and 2 seconds.  The simulation results shown in the slides use 1.5 s
as HELLO_INTEVAL.
  HELLO messages are counted towards the routing
overhead. That's why you see CBRP's routing overhead is more than DSR's
when network size is small. But as network size grows, the reactive
routing protocol's routing message overhead becomes the dominant one and
that's when CBRP (who has smaller amount of routing messages) catches up. 

>    be our results from MobiCom'98, and there, the reason DSDV

Yeah, we use your implementation of DSDV.

>    Have you studied this problem?
 
   I think there is a big difference between the periodic messages of DSDV
(which propage thru out the net) and CBRP(which are local).
   Firstly of all, CBRP does not use periodic HELLO messages
to keep routing table up-to-date. (They are mainly used for cluster
formation and keeping the NEIGHBOR TABLE up-to-date)The actual routing is
still based on source routing (and hence the route discovery stuff..) 
The "triggered" HELLO in CBRP is for faster cluster formation and is
different from the "triggered" update in DSDV.
   Secondly, CBRP does NOT need an accurate, consistent, and up-to-date
view of the group of clusters in order to do the routing. Furthermore,
such a consistent view in a dynamic network has been proven impossible.
As you can see from our simulation code, our route discovery tolerates
such inconsistencies to an extend.

Thanks a lot for your comments and making Monarch's ns ext code available
to the MANET community.

Regards,
Mingliang