From: Pravin Bhat (pravinb@u.washington.edu)
Date: Mon Nov 22 2004 - 05:29:37 PST
Paper summary: The paper defines a new routing protocol, GPRS, designed to scale
efficiently over mobile networks with large diameters. The performance of GPRS is
compared to current state of art in wireless routing, DSR, across various metrics.
Paper strengths:
GPRS requires routers to maintain only a local view of the network. This
results in several desirable features in the protocol:
- minimal state per router
- low routing protocol related traffic in the network
- Quick convergence to stable routes in the face of mobile routers and
frequent failures.
Moreover these features hold regardless of the network diameter.
The authors provide an extensive comparison of GPRS and DSR where
GPRS is shown to outperform DSR across various efficiency and scalability
metrics like - routing protocol overhead, state per router, packet delivery success
rate, and path inflation
The authors point to a possible error in the performance results reported in the
DSR paper as their simulation analysis of DSR using the original code base failed to
corroborate the expected results.
Limitations and room for improvement:
One of the key technologies that GPRS relies on is IP to geographic-location
mapping. In fact if this technology existed geographic distance based routing
protocols might have been deployed a long time ago as the idea is pretty obvious
and often used in real-world routing. However the fact remains that location
mapping is an unsolved problem due to several reasons:
- ISPs/ASs are unwilling to provide such a mapping exposing their internal structure
- Majority of the machines on the internet do not have location detection
technology built in - no GPS receivers, no indoor location system, etc
- GPS receivers do not work in regions with no direct line of sight to the sky -
i.e. indoors, tunnels, etc
On the other hand if a packet were to be stamped with a wrong destination/router
location due to imprecise lookup technology:
- GPRS could misroute and eventually drop all packets sent to the given destination
- The planar graph calculations could fail as certain edge distances would be miscalculated
GPRS assumes that the routers are roughly dispersed over a plane. On the other
hand GPRS is targeted for low-memory/high-mobility ad hoc networks and sensors
networks. However a huge class of ad-hoc/sensor networks tend to be setup
in a multistory buildings where this assumption fails to hold.
Its also not clear if minimum distance is best routing metric in a datagram
network. This cost metric can only approximate the optimal routing policy if
every router in the wireless network had the same bandwidth and latency. In real
world networks GPRS would fail to maximize the network utilization through
load-balancing. Also GPRS' greedy routing scheme results in the shortest path
routing only when the network is densely populated which may not always be true
for mobile networks.
To maximize efficiency the end-hosts would have to co-operate with the GPRS
routing protocol by executing a location lookup of the destination-IP during
connection setup. This location would then be used to mark the destination
location of each packet sent to the destination-IP. This requires a change in
all end-host TCP/IP stack implementations which would be a major hurdle in the
efficient deployment of GPRS.
On the other hand this lookup and increase in TCP/IP-packet header size would
be incurred by all non-wireless connections/packets since there is no
way to tell whether or not a packet being sent out will be routed through a
wireless network.
Certain mobile networks might see minimal change in topology over time however
their planar graph calculations might have to be continually updated due to small
displacements in the network routers. An example of such a network would be
a room full of sensors/robots/ad-hoc network hosts that are constantly
moving around inside the room. For such networks GPRS would have a much
higher routing protocol overhead over its competitors like DSR.
Relevance:
With the formulation of GPRS the authors have taken us a step closer towards a
scalable solution for low-memory, ad-hoc, mobile, wireless networks which are increasingly
becoming popular by the day.
Future work:
- Efficient and reliable location lookup
- Making GPRS resilient to errors in destination location
- Incorporating link-capacity and delay into the cost metric
- Incremental/efficient calculations of the planar graph to accommodate
constantly moving routers
This archive was generated by hypermail 2.1.6 : Mon Nov 22 2004 - 05:29:38 PST