Associativity-Based Routing

Rohit Khare (
Wed, 17 Jul 1996 18:05:33 -0400 (EDT)

Anyone for some instant analysis? Is this the sware key to defeating Teledesic
on the ground?

All I want is a $5 circuit that can connect to the "Net" -- mobile, radio,
autodetect, autoroute, speaks HTTP -- it would go in toasters, vaccuum cleaners,
tvsets, bikes, cars, phones, you name it... the problem is linking up
and routing 10^10 devices -- local naming will be a must.

End of ramble.



Date: Wed, 17 Jul 96 20:44 BST
From: (C. Toh)
Subject: Cambridge Ad-Hoc Routing Protocol (ABR)

Dear Fellow IETF Folks :

Recently, I was pressurised to release information about my invention
of a novel routing protocol for ad-hoc mobile networks.

I am a supporter of the Internet, the IETF, the academic and
industrial research. However, because this technology is being filed
for a patent, I will have to be aware of the amount of information
to be released to the public (basically the time it should be released).

The patent covers a broad spectrum of protection on the concept of
associativity. Hence, any unauthorised commerical exploitation of this
concept will be legally dealt with. However, any commerical organisations
willing to exploit this invention and to put themselves ahead of others
in producing ad-hoc networking products and computing platforms could
contact me via E-mail, and NOT posting to this newsgroup.
Due to my current busy schedule, I can only seriously deal with
company negotiations after 1st September.

I apologise for not being able to show up to present my talk at the IETF
Mobile Ad-hoc Networking BOF meeting in Montreal due to lack of funding
for my trip. I have informed Steve Batsell in advance about my absence.
However, I hope to present at the next BOF.

Below is a summary of my invention and more sources of references will
be made known at the end of the year.

Below is a summary of my invention filed for patent.

ABR - Cambridge Ad-Hoc Routing Protocol (C-K Toh)

17th July 1996

The ABR, ( sorry not `available bit rate' as in ATM but it stands
for Associativity-Based Routing, also known now as Cambridge Ad-Hoc
Routing Protocol) is a new, simple and bandwidth-efficient distributed
routing protocol for ad-hoc mobile networks. We have identified * new *
routing metrics for ad-hoc mobile networks.

Unlike the conventional distributed routing algorithms, this protocol
does not attempt to consistently maintain routing information in every
nodes. In an ad-hoc mobile network where mobile hosts are acting as
routers and where routes are made inconsistent by mobile hosts' movement,
we employ a new associativity-based routing scheme where a route is
selected based on nodes having associativity states that imply periods
of stability.

In this manner, the routes selected are likely to be long-lived and hence
there is no need to restart frequently, resulting in higher attainable
throughput. The association property also allows the integration of
ad-hoc routing into a BS-oriented Wireless LAN environment, providing the
fault tolerance in times of base stations (BSs) failures.

The protocol is robust, free from loops, deadlock and packet duplicates
and has scalable memory requirements. Simulation results obtained reveal
that shorter and better routes can be discovered quickly during route
re-constructions. The protocol is meant to support ad-hoc mobile
communications and networking, and has the features to support some form
of Quality of Service.

The protocol also has a scheme where enhancements in throughput can be
made in a manner that is independent of the underlying MAC layer protocols.
A data acknowledgment and retransmission scheme exists for the ABR.


C-K Toh, Ph.D. (Cambridge)
Founder, Mobile Special Interest Group;
Cambridge University Computer Laboratory, United Kingdom.