Content-Type: text/plain; charset=us-ascii
A dense and filling dish of bits. Munchkin routing will be a hard, hard
problme to solve. Hope we can get to gigabit radios sooner than later,
because routing load is O(mobility of physical devices) and can only be
made negligible by dividing by high bandwidths.
Remember: how long do you have to transfer data from an F-16 to an M1
Abrams with even a 3 mile radio?
Content-Type: text/plain; charset=us-ascii; name="milcom_panel.html"
Content-Disposition: inline; filename="milcom_panel.html"
This article will appear in ACM Mobile Computing and Communications
Review (MC2R), vol.2, no.1, January 1998
Milcom'97 Panel on "Ad-Hoc Networks"
Ad-hoc networks are self-organizing network architectures that are rapidly
deployable and that adapt to the propagation conditions and to the traffic
and mobility patterns of the networks nodes. The most distinguishing
characteristic of ad-hoc networks is the lack of fixed infrastructure. Other
characteristics include a distributed peer-to-peer mode of operation,
multi-hop routing, and relatively frequent changes in nodal constellation.
Precursors of the ad-hoc networking technology were the DARPA Packet Radio
Networks and the Survivable Adaptive Networks (SURAN) programs in the 1970s
and 1980s. Although, military tactical communication is still considered as
the primary application for ad-hoc networks, commercial interest in this
type of networks continues to grow. Applications such as rescue missions in
times of natural disasters, law enforcement operation, commercial and
educational use, and sensor networks are just few possible commercial
examples. It is, however, not clear whether the technology developed for
military applications is directly transferable to the commercial market.
A panel on "Ad-Hoc Networks" was held at the IEEE MILCOM conference, which
took place this year in Monterey, California, November 2-5. The theme of the
conference was Integrating Military and Commercial Communications for the
Next Century. Thus the topic of ad-hoc networks was especially well suited
for the conference. The panelists were:
* J.J. Garcia-Luna-Aceves, UC Santa Cruz
* Zygmunt J. Haas, Cornell University
* David B. Johnson, Carnegie Mellon University
* Joseph P. Macker, Naval Research Laboratory
* Charles E. Perkins, Sun Microsystems,
* Robert Ruth, DARPA ITO
* Paul F. Sass, U.S. Army CECOM
* Jay W. Strater, MITRE Corporation
* John Zavgren, BBN
The panel moderator was Zygmunt J. Haas. After introductions, each of the
panelists delivered a 10-minutes position presentation.
In his talk, Zygmunt J. Haas outlined a number of ad-hoc network design
* flat vs. hierarchical architecture,
* proactive vs. reactive routing protocols,
* the geographical scope of dissemination of information on topological
* the frequency and the stimulai at which the network topological
information should be exchanged.
In a hierarchical architecture, nodes are grouped in clusters, with one of
the nodes assuming the function of a cluster head. Cluster heads create a
second-tier network that operates at much higher transmission power. Routing
between nodes in different clusters is always performed through the cluster
heads. In contrast, in a flat architecture there are no clusters - "all
nodes are created equal." Neighbor nodes can communicate directly, without
restriction, to traverse any specific nodes (i.e., cluster heads).
Zygmunt claimed that the flat-routed networks are much more applicable to
the military communication environment, since the routing is more optimal
(close-by nodes do not have to go through the hierarchy), they provide
improved security (Low Probability of Detection / Low Probability of
Intercept) as the transmission is limited to adjacent nodes only, and the
network tends to better balance the load among multiple paths, thus reducing
the traffic bottlenecks that occur at the cluster nodes in the hierarchical
approach. He also introduced the term Reconfigurable Wireless Networks
(RWN), which are a subgroup of an ad-hoc network architecture, characterized
by large range of nodal mobility, large network span, and large number of
network nodes. Finally, a brief comparison was made between the proactive
(such as OSPF) and reactive (such as flooding) routing protocols. Both of
these approaches are not effective in the RWN environment, the first
introducing too much overhead traffic and the second suffering from too much
delay. A reference was made to a hybrid scheme - the Zone Routing Protocol
J.J. Garcia-Luna-Aceves addressed the lack of seamless extension of the
Internet to support "unplug-and-play" operation, unrestricted by the
existing infrastructure. In particular, the currently used protocols, such
as OSPF and BGP, do not provide a satisfactory solution to ad-hoc
networking. There is no support for Quality-of-Service (QoS) in routing and
multicasting, and the protocols assume fairly static configurations.
Furthermore, existing protocols do not take into account battery life.
J.J. predicted in his talk that the future solutions will involve IP.
However, some modifications are required, especially to reduce the IP
overhead and to support some QoS measures. The characteristics of future
ad-hoc networks will be influenced by cheap processing and storage and by
relatively expensive transmission. The protocol stack will be integrated;
i.e., the physical layer will affect the higher layer protocols. Multiple
channels will be used based on open etiquettes for cooperation among the
network nodes. MAC protocols will incorporate some form of time scheduling
to provide delay guarantees to higher layers. Future routing protocols will
use link-state information to accommodate QoS, but will not be based on
flooding. Future multicasting protocols for ad-hoc nets will be based on
more flexible routing structures than the multicast routing trees used in
the Internet. Finally, reliable multicast solutions for ad-hoc networks will
be different than those being developed for the Internet.
David B. Johnson discussed the use of ad-hoc networks for applications where
no infrastructure is available, such as remote areas, unplanned meetings, or
emergency relief operation. Furthermore, sometimes users may not want to use
the existing infrastructure even when it is available, such as when it takes
too long to register or the service or when the use of the service is too
expensive. David pointed out that the existing traditional routing protocols
are insufficient for ad-hoc routing, since the amount of update traffic may
waste a large portion of the wireless bandwidth, especially for protocols
that use periodic updates and when the network topology changes too fast.
Current limits to ad-hoc networking include the problems of resource
consumption forwarding packets for others, etiquette, and lack of services.
The possible commercial applications of ad-hoc networking include
mission-oriented networking, community-based networking, and arbitrary
groups of strangers.
David described the CMU Dynamic Source Routing protocol, which is based on
on-demand route discovery and route maintenance. The features of the
protocol include absence of periodic exchanges of messages and no reaction
to movements by nodes whose communications are not affected by the movement.
The protocol is being implemented on FreeBSD 2.2.2 in an environment of IBM
infrared wireless LAN cards. The current maximum size of the network is
about 10 machines, limited by the amount of hardware and physical space
available for the prototype. A commercial application that is being
considered is to support ad-hoc connectivity at a large mining or
construction site. Caterpillar is cooperating with CMU on a project in this
Joseph Macker's presentation started with description of the work done at
the Naval Research Laboratory in mobile routing. The work include the
pioneering work on Linked Cluster Routing (Baker et al), the more recent
work on the Temporally-Ordered Routing Algorithm (TORA) protocol, and
involvement in the IETF IP-based Ad-hoc Mobile Network Working Group
(MANet). He then outlined the desirable properties of a well-suited routing
protocol: executes distributedly, provides loop-free routes, supplies
multiple routes, establishes routes quickly, and minimizes algorithmic
reaction/communication overhead. The TORA protocol was introduced and
simulation results displayed in terms of the reduced bandwidth utilization
for the protocol's control traffic and the mean packet delay.
Joseph then discussed mobile routing for the Internet protocol suite,
indicating that wireless networking poses technical challenges at the link
and the physical layer, in addition to the effect on performance of the
upper layers. Related IETF work was described. This work extends the current
standardized protocols, as those were not intended for use in a mobile
environment. IEFT Mobile Ad-hoc Networking (MANet) was chartered. MANet
addresses improved, peer-to-peer mobile routing technology in a
heterogeneous wireless fabric. Some issues include performance evaluation
criteria and infrastructure integration. In particular, performance criteria
could include data throughput and delay and efficiency and robustness, under
different network context, such as size, connectivity, rate of change, and
capacity. As concluding remarks, Joseph suggested that there is a need for
increased support for standardized routing solutions for mobile networking,
that the future holds some interesting possibilities, such as use of
heterogeneous wireless "fabrics" and inexpensive wireless routing nodes, and
that some initial concepts are ready for technology transition.
The next position talk was given by Charlie Perkins, who discussed routing
considerations for ad-hoc networking. He advocated the use of Distance
Vector algorithms for routing, since they use less memory, constrain the
updates to local operations, are simple to program, and can be made loop
free. Routing protocols have to be based on demand-driven route
establishment procedures. They have to be scalable for large node
populations in memory and search time, in the overhead for maintenance, and
in the overhead on data traffic.
Charlie described the Ad-Hoc On-Demand Distance Vector (AODV) routing
protocol, which uses destination sequence numbers for route updates.
Destination sequence numbers ensure loop-freeness and eliminate the well
known "counting to infinity" problem of Bellman-Ford algorithms. In AODV, a
route is cached by intermediate nodes for some time since its last use. A
limited-range broadcast message is used for neighbor discovery. Upon
discovery of a link failure, a notification is issued to the users of the
link. The protocol involves little overhead for data traffic and enables
future aggregation of computations. Open questions for future consideration
include the location of network services (e.g., DNS, certificates, agent
directory for service location) and whether functions should be independent
of location and hostname.
Robert Ruth described the DARPA GloMo (Global Mobile Information Systems)
project. The goal of the project is to make the mobile environment a
first-class citizen in the Defense Information Infrastructure by providing
user friendly connectivity and access to services for wireless mobile users.
The defense wireless environment is characterized by lack of pre-deployed
infrastructure, by significant changes in the connectivity and link quality
due to weather, terrain, foliage, or EMI, and by mobile operations. The
focus of the GloMo program is in the areas of: mobile applications support,
end-to-end networking, wireless networking, and wireless node design. Hard
issues in mobile ad-hoc networking include: set up and settling time,
dynamic reconfiguration, overhead vs. throughput, reliable multicast, QoS,
variation in network density, highly asymmetric communications, and
heterogeneous networking. Network security and survivability is especially a
hard and important issue that deserve more attention.
Robert briefly described a number of GloMo projects, concentrating on the
new ideas in each of them. GloMo initiatives include: self organizing/self
healing networks; both flat and hierarchical multihop routing algorithms;
ATM over wireless; Georouting; Satellite communications networks;
heterogeneous networking with IP overlays; end-to-end network enhancements;
and security & survivability for ad-hoc networks. GloMo technologies are
applicable to Wide-Area Information Systems, Information Systems for
Dismounted Forces, and Information System for Rapid Deployment of Forces.
Robert stressed two points in his presentation. The first was that much can
be gained by designing the radio/wireless node and networking algorithms to
work together. The second was that one protocol may not be optimum for all
situations. Instead, we may need to move to a multi-mode networking stack
that addresses: stealth, low power, low data rate, voice and low data rate,
multi-media, and antijam.
The next speaker was Paul Sass, who presented the Army perspective on ad-hoc
wireless networks, based on four layers, from the bottom up: the so-called
"Plasma Net," the Terrestrial Transport, the High Altitude/Endurance UAV,
and the Satellite Transport. He described a "canonical brigade," which
includes 1000 tactical platforms (tanks, APCs, helicopters, etc), with one
or more tactical radios per platform, each with hemispherical coverage, and
with platform-to-platform direct line of sight range of less than 16 km. The
deployment area of the brigade is 3 km wide by 5 km deep in offensive
posture and 15 km wide by 10 km deep in defensive posture. While platoon
platforms are relatively close, brigade platforms may be widely separated.
Communication today is currently supported by SINCGARS, the Army's VHF
combat net radio designed primarily for digitized voice. He described
near-term plans to experiment with the NTDR, an IP-based packet radio, to
support increasing needs for IP datagram service in the Tactical Internet.
Paul pointed out that although commercial protocols must be the starting
point for military R&D, the commercial network attributes differ from the
military networks. The military environment requires high survivability,
lack of fixed infrastructure, fast response time to failures, reliable
communications, and support for real-time traffic. Multicast and
"eavesdropping" are also important attributes for military networks. Thus,
the commercial cellular wireless model does not represent the tactical
world. At the brigade level and below, tactical networks are multi-hop.
There are a lot of small networks (i.e., 20 nodes per network) and the
number of networks is much larger than the number of nodes per network.
Since both hosts and routers are mobile, IP addressing must be dynamically
managed. Effective dynamic routing schemes are needed at the subnet layer.
Open questions include how connectivity information could be shared with IP
routers? How can mobility be managed without IP address changes? Can
on-demand routing replace the Distributed Spanning Tree (e.g., SINCGARS) or
Link State (e.g., NTDR) routing? How data and voice should be handled? Can a
single routing scheme handle connectionless and connection-oriented traffic?
Jay Strater's presentation started with outlining design challenges for
future tactical radio systems. The challenges include support for mixed
traffic, increase in network capacity, support of unrestricted mobility, and
simplification of configuration and management procedures. Jay then
addressed the topic of the network architecture considerations: routing
architecture, cluster management, address/mobility management,
interface/protocol stack, and security. In particular, the routing
architecture could be either shared or separate band (which is related to
the previously-mentioned flat-routed vs. hierarchically-routed networks).
Cluster management includes issues related to cluster formation and its
maintenance and connectivity within the cluster. Address/mobility management
can be performed with distributed or with centralized management algorithms
and can be implemented through address servers or forwarding agents.
On the physical layer, Jay discussed the issues of frequency bands, the
choice of spread spectrum technique (direct sequence and frequency hopping),
and modulation and coding schemes. On the link layer, reference was made to
the MACA and the PRMA schemes. Finally, on the network layer, the routing
schemes and router resource reservation topics were addressed. In
particular, a distinction was made between the topology-driven and the
on-demand routing protocols.
The last, but not least, talk was given by John Zavgren, which described the
Near-Term Digital Radio (NTDR) mobility management protocols and procedures.
NTDR is based on layered architecture: Media Layer, Internet Layer, and
Internet Layer. The Intranet layer is based on two-level hierarchical
architecture (with clusters and cluster heads), while the Internet layer is
based on peer NTDR communication. The routing in the Intranet is based on
forwarding tables for the backbone network (the network that interconnects
cluster heads) and on augmenting the forwarding tables with cluster members
information. The clustering is implemented through the following concepts:
neighbor discovery, backbone formation, and affiliation of nodes with
cluster heads. The cluster beacon format was presented and the affiliation
protocol was described. The routing protocol is based on the Shortest Path
First (SPF) link-state algorithm, with the link-state information aged over
John presented the BBN modeling strategy, which included scenario of 50-node
testbed simulated by OPNET Modeler. (OPNET is a trademark of MIL3, Inc.) In
particular, the shared modeling scenario, based on ITT and BBN models, was
described. Although OSPF has a large overhead due to the HELLO protocol and
due to its flooding operation, modifications were made to reduce this
overhead. For example, it was claimed that for 500-node NTDR network, the
OSPF HELLO protocol and the link-state flooding would consume in excess of
1.4 Mbps each. The Radio OSPF was defined that includes such features as
elimination of OSPF HELLO protocol and elimination of designated-router
The above presentations were followed by about an hour and a half of
questions and comments from the audience to the panel members. Examples of
topics discussed were:
* At what level should the mobility be handled?
* The applicability of wireless ATM in the context of ad-hoc networks?
* Can a flat-routed architecture be used for the Army applications and
how can a flat-routed architecture accommodate UAV/satellite relays?
* Use of the ad-hoc networking technology in commercial applications?
* How Quality of Service can be supported in ad-hoc networks? The
following issues were identified by the panel members as central
problems in design and implementation of ad-hoc networks:
* Commercial awareness of ad-hoc mobility
* Interoperable APIs that clearly identify information passed between
* Dynamics of the battlefield
* Agreement on what constitutes QoS
* Physical and MAC standards for ad-hoc networks
* Security, and
* Scalability of routing protocols
In summary, this was one of the most successful panels at the conference
with large audience participation. Comments of the attendees were extremely
positive and indicate significant interest in the ad-hoc networking
technology, both for the military and commercial markets.