Subject: MANET Addressing Architecture

From: "M. Scott Corson" <[email-masked]>
Date: Wed, 2 Sep 1998 09:49:53 -0400 (EDT)

Folks,

Thanks again to everyone who attended the last meeting.  It was productive
and many new ideas were put forth.  It's great to see so many people getting
involved and starting to build stuff. Towards the end of the meeting,
I began a discussion on MANET node identification and addressing.
I'm not sure if I was able to get my point across as
the discussion had to be curtailed.  I'd like to take up where the
discussion left off at the meeting.

Simply put, my thoughts concern the addressing architectures implicitly
supported by some proposed routing approaches being put forth within the 
working group.  My concern is that some of these approaches either depart
from the classic IP addressing architecture, or are short-term and limited
in their scope, considering only a narrowly-defined application space 
for MANETs.  My comments here are meant to be constructive, as I think
all the proposed protocols would benefit in the long term from adopting
the more general addressing architecture described herein.
I think the working group effort would benefit from adopting a
common approach to issues such as addressing, security,
eventual interoperability with the fixed network, etc. while developing
routing technology for MANETs.  Here are some thoughts regarding node
addressing and identification.

A MANET node can loosely be thought of as a mobile entity in a MANET to 
which information is transmitted and received.  Its composition and 
means of identification are the issue here.  For this discussion, I will 
define a MANET "node" as an abstract entity consisting of a MANET "router" 
and set of affiliated mobile "hosts".  

                             MANET node
                  ********************************
                  *    +------+                  *
                  *    | host |--+               *
                  *    +------+  |               *
                  *              |               *
                  *    +------+  |   +--------+  *
                  *    | host |--+---| router |  *
                  *    +------+  |   +--------+  *
                  *              |               *
                  *    +------+  |               *
                  *    | host |--+               *
                  *    +------+                  *
                  ********************************

A MANET router is an entity which, among other things, runs a MANET routing 
algorithm.  A mobile host is simply an IP-addressible host/entity in the 
traditional sense.

In the sequel, it will become apparent that I think the ability to distinguish 
between routers and hosts is a crucial element of any viable, long-term MANET 
addressing architecture even though, in some special cases, 
a physical device may act as both router and host.  

There are three types of identifiers to consider:

1) Interface Identifiers

Interfaces are present on both hosts and routers.  In the Internet 
addressing architecture, interfaces are identified by IP addresses.  

2) Host Identifiers

Under current practice, a host's network-level identity may change
It is often synonomous with one of the host's interface addresses on one 
of its home networks (for multihomed hosts).  This is a so-called *permanent* 
identifier.  However, it can also be an IP address of one of its interfaces
dynamically obtained by some other means--a *temporary* identifier.

3) Router Identifiers

Router identification, apart from the IP addresses of its interfaces, 
is unspecified and generally depends on the routing policy in use.

There are three basic approaches to MANET router identification and
addressing currently being considered within the working group:

A) Single IP address (as put forth in AODV, etc.)

                       +--------+
                       |        |
                       |        |
                       |        |----+
                       | router | IP |
                       |        |----+
                       |        |
                       |        |
                       +--------+

This approach identifies a MANET node with a single IP address.  In keeping 
with the Internet addressing architecture, this implies that the MANET node 
has a single interface with this identity.  We can also infer that this is its
*wireless* interface as this is a wireless router.  

This approach naturally supports an implementation where a host
acts as a router, but this approach leaves open several issues:

* How does one support sets or subnets of hosts attached to a MANET router?

* How does one support use of multiple wireless technologies simultaneously?

B) Single IP address with interface indexes (as put forth by DSR)

                       +--------+-------+
                       |        | index |
                       |        |-------+
                       |        |-------+
                       | router | index |
                       |  (IP)  |-------+
                       |        |-------+
                       |        | index |
                       +--------+-------+

This approach identifies a MANET router with a single IP address, and 
identifies each of the router's interfaces with a single-byte interface index.  
The usage of interface indexes was added to enable simultaneous support for 
multiple wireless technologies, with the IP address essential acting
as a router identifier.

A difficulty with this approach is that it departs from the Internet addressing 
architecture.  It is not IP in the classical sense where interfaces are
identified by IP addresses.  It is a psuedo-IP, psuedo link-level approach.  
The ramifications of this design choice are unclear, but the use of a 
non-standard addressing architecture will likely complicate interoperability
and may limit the utility of protocols developed using this approach.

C) Router identifier and IP interface addresses (as put forth by IMEP, etc.)

                       +--------+----+
                       |        | IP |
                       |        |----+
                       |        |----+
                       | router | IP |
                       | (RID)  |----+
                       |        |----+
                       |        | IP |
                       +--------+----+

This approach identifies a MANET router with a Router IDentifier (RID), 
and identifies each of its interfaces with an IP address. This is nothing 
really new, being essentially the same approach used in OSPF today.
The approach can support sets or aggregated subnets of attached hosts 
(hanging off its wired interfaces) and simultaneous usage of multiple 
wireless technologies (through its wireless interfaces).

Architecturally, having only one IP address per node, approaches A and B 
seem tailored to supporting a mobile host that acts as a router.
Approach C is intended to support a mobile router platform to which one or 
more host-like devices may be permanently or temporarily affiliated, 
and has the flexibility to support efficient subnet-based route advertisement 
for hosts hanging off wired interfaces.

It is the view here that supporting multiple hosts per router and multiple 
wireless technologies should form the *general* case, with other cases 
being *special* cases of this general architecture, which is shown below.

                                                      \|/
          +------+----+               +--------+----+  |
          | host | IP |----+          |        | IP |---
          +------+----+    |          |        |----+    \|/
          +------+----+    |     +----|        |----+     |
          | host | IP |----+-----| IP | router | IP |------
          +------+----+    |     +----| (RID)  |----+       \|/
          +------+----+    |          |        |----+        |
          | host | IP |----+          |        | IP |---------
          +------+----+               +--------+----+

Note that this architecture says nothing about *how* IP addresses are assigned 
to interfaces (on hosts or routers), or *what* the RID is and *how* it is 
assigned.  This is a separable problem, although one which is related to 
routing.  

Policies and protocols for IP and RID assignment and management will 
likely be developed (perhaps in a separate working group), or on an
as-needed basis within a given administrative domain.  These policies
should reflect the nature of a given MANET domain, just as a routing policy
should reflect the nature of a domain.  It is the view here that
policies should be dynamic (varying from domain to domain), but core 
elements such as the addressing architecture must be uniform across
the MANET space for interoperability within the space and with the
fixed network.  Otherwise, how do elements of the fixed network easily
interoperate with stub MANETs if each has a separate addressing architecture?

Analysis of some Special Cases:

1) A mobile host may be coincident with a MANET router (i.e. the *same* device)
with only a single wireless interface. 

                       +--------+
                       |        |
                       |        |       \|/
                       | host/  |----+   |
                       | router | IP |---|
                       | (RID)  |----+
                       |        |
                       |        |
                       +--------+

In this case, the host inherits the identity of the router's IP address.
Here, the RID appears to be unnecessary, as both the RID and IP address
identify the same device.  However, it is necessary if this node is
to interoperate with other devices which are using multiple wireless
technologies.  The RID is the key to enabling simultaneous usage of 
multiple technologies---usage which happens to be the technical 
justification for wireless multihop routing at the IP layer.
Here, the (RID,IP) pair must be advertised by a routing algorithm.
Advertisement of the RID is the runtime communication cost (in my view a
negligible one) of a multi-technology addressing architecture.

2) A mobile host may be coincident with a MANET router (i.e. the *same* device)
with multiple wireless interfaces. 

                       +--------+
                       |        |
                       |        |       \|/
                       | host/  |-----+   |
                       | router | IP1 |---|
                       | (RID)  |-----+       \|/
                       |        |-----+        |
                       |        | IP2 |--------|
                       +--------+-----+

In this case, the host is multihomed, and inherits the identities
of the router's IP addresses.  Here, the RID is clearly necessary, as it 
permits routing through a multi-technology multihop wireless fabric.  
Here, the tuple (RID,IP1,IP2) needs advertisement for full routing 
capability.

In summary, the essence of the MANET effort is to begin building 
Internet routing technology for a mobile infrastructure. It is difficult
to predict the future, and it may become feasible to readily build non-trivial 
MANETs.  It is the view here that the MANET working group should architect
its approach now to allow for this possibility.  One cannot predict the way 
networks of mobile platforms (car, planes, trains, robots, humans, etc.) 
will want to be interconnected in the future.  In many of these cases, there 
will be multiple mobile hosts (i.e. IP-addressable entities) affiliated with 
each mobile router.  

* Their identities need to be *separate* from that of the router for 
  addressability, flexibility and the ability to change affiliation.

* Also, future multihop wireless networks will need to simultaneously support
  *multiple* wireless technologies.  This is the technical argument for
  developing IP-level multihop wireless networking technology (the other being
  an economic argument regarding the reusability of networking technology as 
  link and physical layer technologies evolve.)  

* Eventually, these networks will need to *interoperate* with the fixed 
  network.  Such interoperability would be greatly facilitated by a *common*
  addressing architecture throughout the MANET space, regardless of the
  policies (such as routing and address assignment) in use in a given domain. 

Current military networks already have all these requirements. In the past, 
military applications have oftentimes been leading indicators of commercial 
applications and technologies (e.g. consider the fixed Internet itself).

Comments?

-Scott

*******************************************************************************

M. Scott Corson                                 Institute for Systems Research
[email-masked]                              A.V. Williams Bldg. (115)
Phone: 301-405-6630 (Rm. 2205 AVW)              University of Maryland     
Fax:   301-314-8586                             College Park, MD  20742

*******************************************************************************

---

From: "Fred L. Templin" <[email-masked]>
Date: Wed, 02 Sep 1998 10:57:37 -0700

Scott,

I was in attendance at the MANET WG meetings and was disappointed that
time did not permit this discussion to continue, so I really appreciate
your taking it back up again here. I'll insert a few comments/questions

> and set of affiliated mobile "hosts".  

I think you need to define "affiliated" mobile hosts a bit more firmly.
If by "affiliated", you mean that the hosts are somehow "tethered" to
their corresponding router (either via hardwired links or wireless links
which can somehow never be broken) then I can see the distinction of
hosts vs routers. But, if the affiliated hosts are free to move; possibly
losing touch with their router and coming into contact with other hosts
and routers, then I think the concept breaks down. In this case, you would
want such mobile hosts to behave like routers as well, in the sense that
IMEP defines a router. That is, you would want the mobile host to participate 
in the BEACON/ECHO process to discover it's single-hop and
multi-hopped neighbors as it moves.  

> interoperate with stub MANETs if each has a separate addressing architecture?

Without trying to debate between the AODV vs. DSR vs. IMEP approaches,
I think the RID assignment can be done rather easily. Why not just pick
one of the router's interface identifiers (IP addresses), designate it as
the "primary address" for this router, and set the RID to that address?
Even if the router moves and it's interface identifiers change, I think
you are still OK to just set the RID once and for all. In a way, it would
be like the Mobile IP concept of a "home address".

>From what I've seen in the GloMo, SUO, and Tactical Internet scenarios,
I believe this will actually be the more general case for mobile hosts.
That is, the mobile host will have a single radio with no pre-configured
notion of the network topology, and so it will need to adhere to some
channel access protocol (like 802.11) and also go about discovering it's
network neighborhood through some means such as IMEP. It should also
participate in multi-hop packet forwarding (notice I didn't say "routing")
in cases where it can serve as the go-between for other hosts, and so it
begins to look like a single interface router in the spirit of IMEP.  
 
> with multiple wireless interfaces. 

Again from the GloMo, SUO, Tactical Internet experiences, I believe
this configuration will be common, but not as widespread as the 
single-interface case. It should also be considered that the interfaces
may be a heterogeneous mix of both wired and wireless devices. Then,
within the subset of wireless interfaces, this sort of configuration
should behave like a multiple-interface router in the IMEP sense, and
within the superset of all interfaces it should behave as a traditional
router in the classical Internet sense.

That's all I have for now; again, I appreciate your taking the time to
initiate this thread of discussion,

Fred
[email-masked]

---

From: "M. Scott Corson" <[email-masked]>
Date: Wed, 2 Sep 1998 15:18:19 -0400 (EDT)

> multi-hopped neighbors as it moves.  

Fred,

This is an interesting point of discussion.  I'm trying to distinguish
between what is a mobile host, and what is a MANET router, 
and *why* it is useful to distinguish between the two.  

I understand your point above, but having every mobile host with a 
permanent identifier treated as a router has *nasty* scaling implications 
for the routing protocols.  I think it is better to allow the mobile hosts 
to affiliate with a MANET router (identified by a RID, where the RID becomes 
the hosts *location* in the MANET), and utilize some additional efficient 
location management mechanism to track the host/RID mapping as it
evolves in time.  This way, the routing algorithm only has to track
the mobility of the routers currently forming the multihop wireless topology.
The location management functionality can be used to discover host
location (its current RID affiliation) as necessary...their are several
ways one can imagine doing this.  A protocol (something like IGMP) can 
be developed to permit automated host affiliation with a router.

There are several basic cases I can think of:

1) Hosts may be permanently attached to a MANET router; 

2) Hosts may be temporarily attached, receiving an address via some dynamic
   address assignment policy/protocol;

3) Hosts may be temporarily attached, bringing with them a permanent
   identifier;

4) Hosts are mobile routers.

Cases 1 and 2 can permit very efficient routing without requiring any external
location management functionality.  Case 3 requires the functionality I 
described.  Case 4 (which you suggest) is also easily done within the 
architecture IMEP puts forth, but has scaling limitations and so should
be used only to the extent possible in a large-scale network.

What is desireable for node identifiers is that they be 
``constant for the time required for a given application".
This way...transport, security and other higher layer associations
can remain in place.

To me, the RID is essentially a *location* in a MANET space, to which one
or more host devices may be temporarily or permanently associated.

> the "primary address" for this router, and set the RID to that address?

Sure...this is one possible policy for a flat network.

> begins to look like a single interface router in the spirit of IMEP.  

In the near term, this may be the more common case, but it is a special
case of the more general architecture.

I'm concerned long term about the type of architecture that would be 
required to build a mobile infrastructure.  Protocols implemented 
atop the general architecture will have flexibility and long-term viability.

> single-interface case. 

Probably...but I regard all of that work as very near term.

Remember the original cellphones...big analog bricks...now we have
dual and triple mode phones being developed, and technology is coming
to permit radios to be reprogrammable on-the-fly, and multi-functional.
Cool stuff.

It's really hard to predict what wireless comms will be like in 30 years.

> It should also be considered that the interfaces

Yes...this is included in the general architecture.

> router in the classical Internet sense.

Sure.

> initiate this thread of discussion,

Thanks for the feedback.

-Scott

---

From: "Fred L. Templin" <[email-masked]>
Date: Wed, 02 Sep 1998 13:05:12 -0700

Scott,

I'll need some time to consider your reply in more depth. But, one point

> be developed to permit automated host affiliation with a router.

I appreciate your concerns regarding scalability, since it seemed from
my first read of IMEP that control messages could possibly grow as large
as N**2 (neglecting message aggregation), where N is the number of nodes
participating in the routing exchanges. But with the above model, it seems
that simple hosts would not be eligible to participate in the multi-hop 
functionality. The example I have in mind is, supposing hosts A, B, and C
somehow get separated from their MANET and thus no longer have an RID
affiliation. Suppose also that A<->B is a bidirectional link and B<->C
is a bidirectional link, but no link exists between A<->C. Now, if A
wishes to start a session with C it can't - even though B seems ideally 
situated to enable the session via multi-hop packet forwarding. Am I
right about this?

So, perhaps what is needed is a dynamic means for simple hosts to become
routers when the MANET is router-scarce and for routers to revert back to
being simple hosts when the MANET is router-rich?

Thanks,

Fred
[email-masked]

---

From: "M. Scott Corson" <[email-masked]>
Date: Wed, 2 Sep 1998 16:28:18 -0400 (EDT)

> situated to enable the session via multi-hop packet forwarding. Am I

Using my terminology, if A, B and C are solely mobile hosts and they leave 
a router, they are out of luck.

> being simple hosts when the MANET is router-rich?

Yes.  I think this is essentially where this discussion is headed...rather
interesting actually.

A host-like device can become a MANET router *when necessary* 
(when it is alone), but when it affiliates with another MANET router, 
it suppresses its router behavior and reverts to being a simple host.  
This could be part of the IGMP-like affiliation protocol where it is
decided which becomes a host, and which continues being a router.

Kind of cool....this could supported by the general addressing architecture.

-Scott

---

From: "Stephen A. Witt" <[email-masked]>
Date: Thu, 3 Sep 1998 09:36:27 -0700 (PDT)

> a router, they are out of luck.

Isn't this the job of the datalink (layer 2) protocol?  Does it make sense
for B to "forward" datagrams (meaning a network layer action) back out the
same network interface that they were received on?  Perhaps this view is
too "classical".  

Steve Witt
Raytheon Systems Company

---

From: "M. Scott Corson" <[email-masked]>
Date: Thu, 3 Sep 1998 12:56:25 -0400 (EDT)

> same network interface that they were received on?  Perhaps this view is

Steve,

I don't follow you here.  By my comment, I mean that A, B and C are incapable
of forwarding (since they are not routers) so A and C are out of luck if
they wish to communicate.  As far as we are concerned here, there is no
layer 2 multihop forwarding...if there were, A and C would appear only a
``single hop" apart from the perspective of IP, but that's another approach.

At the IP layer, if A, B and C are routers and B has a single wireless
interface, it makes perfect sense for B to forward the packet out the
interface on which it was received (assuming a broadcast medium).

-Scott

---

From: "Fred L. Templin" <[email-masked]>
Date: Thu, 03 Sep 1998 12:15:50 -0700

Stephen,

> same network interface that they were received on?  Perhaps this view is

Just to add to what Scott has already said, my perception is that 
"multi-hopping" in the wireless world refers to packet forwarding at
the datalink level. This is why I tried to carefully distinguish it
from classical network-level (IP) routing. Even if nodes A, B, and C
all had the same network prefix in their IP address, you could still
perform datalink-level multi-hopping in the scenario I presented. I
think the key concept here is that a wireless MANET (or "subnet") will
have a constantly-changing and rarely fully-connected datalink-level 
connectivity graph, and so multi-hopping may sometimes be necessary to
reach all members of the MANET...

Regards,

Fred
[email-masked]