Subject: Subject MANET addressing, neighborcasting etc.

From: [email-masked]
Date: Thu, 10 May 2001 13:28:22 +0200 (CEST)

Dear all,

I've been reacing the recent traffic on the list regarding MANET
addressing etc. It seems to me, that most of the discussions tend to
revolve around two "terms":

	- neighborcasting
	  (a node emitting a packet, to be received by all its
	  direct neighbors)

	- all-manet-casting
	  (a node emitting a packet to be received by all nodes in the
	  MANET)

Neighborcasting is required by MANET routing protocols for neighbor
sensing, while all-manet-casting has been mentioned in relation to various
service discovery mechanisms. The wired-network equivalences of
neighborcasting and all-manet-casting are a bit unclear at this moment - I
will address this shortly.

Several questions have arrised in this discussion of this on the list -
and on the last IETF - notably:

	- which address to associate to a "neighborcast"?
	- which address to associate to an "all-manet-cast"?
	- what is the defining boundaries of a MANET?

To take the last issue first: what are the defining boundaries of a
MANET? This is important, among other things, for the matter of defning
how far an all-manet-cast should reach - i.e. in determining which nodes
should receive a given all-manet-cast packet. This integrates very closely
with addressing-issues, which I will therefore touch briefly in the
following.

As far as I can figure, there are two ways of dealing with the boundaries
of a MANET. Either, all nodes in the MANET are required to be from within
the same IP-sequence (i.e. have the same prefix) and thus a gateway (any
node connected to both the MANET and another network) can announce routes
to just this IP-sequence. The alternative is, that there are no such
requirement (in effect that each node makes its own subnet). The later
situation is easilly dealt with within the MANET (where host routes are
being used), while disables the ability for a gateway to aggregate routes,
and hence must announce host-routes to all nodes in the network.

There are pros and cons in both cases: in the case where all nodes in the
MANET are within the same IP-sequence, route aggregation is trivial.
However if more gateways (which are connected to both the internet and
the MANET) exists and the MANET partitions such that each router is
connected only to its own partition and to the internet, there will be
special issues to deal with: the gateways being able to reach eachother
over their internet links will require "something special" (tunneling?) to
be able to provide connectivity to the entire MANET. This clearly is not a
problem if there is no assumption on the nodes being from the same
IP-sequence - but announcing host routes is often not a good idea
either...

To return to the issue of "neighborcasting" and "all-manet-casting" in the
context of the different addressing models: if the requirement that all
nodes within the MANET are of the same IP-sequence, then:

	- neighborcasting equals a traditional limited broadcast
	  (addressed by 255.255.255.255)

	- all-manet-casting equals the directed broadcast address for the
	  IP-sequence of the MANET.

This is in correspondance with RFC1812, which states that a limited
broadcast must not be forwarded - which is another way of saying that a
packet is received within the neighborhood only. It is also an unintrusive
and simple way of going about implementing things.

However, there have been valid concirns about this model. Among other
things, the limited broadcast is commonly used in service discovery
protocols with the assumption that such will reach "all nodes within the
local network". This interpretation is present in several doccuments and
protocols, but does pose problems for us in the MANET world. Therefore, an
alternative is that:

         - neighborcasting is translated into a multicast-address,
	  allocated specifically for this purpose, and used with a TTL = 1
	  only.

         - all-manet-casting equals the limited broadcast address.

This does preserve the usual semantics of the limited broadcast address,
which is a desireable feature, though this would require introducing
multicast features (even if a minimal way) for an unicast routing protocol
to function (they all rely on neighborcasting, which is done through
multicasting in this proposal. A question on when to terminate the limited
broadcast then must be addressed.

However this also violates RFC1812 in that now a MANET node is required
to forward limited broadcasts - and introduces the need for solving the
dangerous situations of two nodes repeatedly forwarding the same packet
between eachother. That is to say: in a MANET, limited broadcasts are
dealt with differently from in the usual IP-networks.

I can imagine that in nodes, connected both to a MANET and to another
IP-network, treating limited broadcasts differently on the two networks
could become tricky. Also, I am sceptical towards requireing modifications
to IP-stacks of existing operating systems - which would be required to
do the forwarding (and do it in a "safe" way). This would
require introducing multicast features (even if a minimal way) for an
unicast routing protocol to function.

However, I am also concirned about how many applications and other
protocols will break, due to the way a directed broadcast will work in a
MANET.

I find, intuitively, that the approach not violating RFC1812 is of
preference. However I am not cirtain how many - and which - higher level
protocols and applications would break doing this.

In any event, I believe that we should establish consensus either way.

-- 
Mange hilsner / Sincerely

-------------------------------------------
   Thomas Heide Clausen
   Civilingeniør i Datateknik (cand.polyt)
   M.Sc in Computer Engineering

   E-Mail: [email-masked]
   WWW:    http://www.cs.auc.dk/~voop
-------------------------------------------

---

From: "Fred L. Templin" <[email-masked]>
Date: Thu, 10 May 2001 17:18:06 -0700

Thomas,

Nice work summarizing the earlier discussions, as well as presenting
some additional ideas. I am enclosing some comments to your message
below.

Regards,

Fred Templin
[email-masked]

> and hence must announce host-routes to all nodes in the network.

A third and more generalized possibility is that there may be MORE THAN
one aggregated IP subnet - i.e. a collection of nodes all having the
same Classless Inter-Domain Routing (CIDR) prefix - manifested within a
single MANET. Additionally, nodes that are members of the same CIDR prefix
*need not* be clumped together in a particular geographic or topological
region of the MANET - instead, they may be randomly distributed throughout.
So, the MANET border gateways could potentially advertise one OR MORE
aggregated CIDR prefixs to external networks while the individual IP
addresses within the MANET may *appear* to be scattered about in
random fashion.

When thinking about addressing in MANETs, I find it is helpful to go back
to some old and little-used terminology which suggests that the network
layer (Layer 3) in the OSI reference model actually comprises not one,
but *three* functional sub-layers. Layer 3(a), the "Subnet Access Layer",
deals with individual nodes discovering their neighbors and (in the case
of MANETs) multi-hop paths to non-neighbor nodes. At this level, the IP
address is simply an interface identifier that uniquely identifies the
node within the MANET. (In IPv6, this might be a good application for the
"link-local" and "site-local" address forms). A perfectly good standalone
MANET could be formed even if no two nodes within the MANET shared a
common CIDR prefix, but this does you no good if you want to attach the
MANET as a stub network or transit network to the Internet. In short,
if there is *no* aggregation, there is *no* Internetworking.

In order to provide aggregation, a Layer 3(b) "Subnet Convergence Layer"
function is needed. Examples of a Layer 3(b) scheme would be LANMAR as
well as earlier works such as SRI's Network Reconstitution Protocol and
Paul Tsuchiya's work on "The Landmark Hierarchy" which both pre-date
LANMAR. NAT and DHCP would also fit into this category, as would IPv6
router discovery and Mobile IPv4 Foreign Agent discovery. In all of
these schemes, nodes discover a "good" subnet to join via some sort
of service discovery protocol. Upon discovery, nodes may optionally:

  - adopt a "care-of" address that is topologically correct for the
    MANET if they are just visiting
  - change their IPv4 address to one that is topologically correct
    for the MANET if they are staying for awhile (e.g. IPv6 address
    autoconfiguration; DHCP)
  - allow some form of NAT function at the MANET border to translate
    their non-aggregatable intra-MANET address into an aggregatable
    addresses suitable for inter-domain routing   

> IP-sequence - but announcing host routes is often not a good idea

This is where the third Layer 3 sub-layer comes in. Layer 3(c) - the
"Subnet Independent Layer" deals with inter-domain routing issues under
the assumption that subnet convergence is taking place at a lower layer.
(I truly do not see an opportunity for Internetworking if there is no
way to represent the MANET as one or more aggregatable CIDR prefixes
suitable for hierarchical routing; in particular, host routes will
probably not be carried by most IGP protocols and *certainly* not be
carried by BGP.) The idea of repairing network partitions by tunneling
across the Internet is one that came up in an earlier discussion between
Kevin Grace and myself. It works in some fashion, but does require close
coordination between the gateways. There are other possibilities as well
which may be cleaner; for example, IPv6 router renumbering.   

>           IP-sequence of the MANET.

In the generalized case, there may be many independent subnets which
have converged within a single MANET. (I can even imagine a gigantic MANET
in which hundreds or even thousands of independent subnets have converged.)
Also, as I mentioned above, there is no requirement that nodes with a
common CIDR prefix be clumped together in a common geographic or topological
region - instead, nodes with different CIDR prefixes may be randomly
interspersed throughout the MANET. In such cases, a directed broadcast
for a particular CIDR prefix may need to be forwarded by nodes with a
*different* CIDR prefix. This sounds like something that might not work
well in existing host/router OS's. Additionally, unless you know exactly
what the subnet convergence criterion are for the (possibly numerous)
subnets within the MANET, the only alternative for unambiguously reaching
all members of a particular subnet *may* be to flood the entire MANET.    
 
> local network".

Similarly, the IANA assigned numbers document for multicast addresses
requires that IPv4 multicast addresses in the range 224.0.0.0 thru
224.0.0.255 *NOT* be forwarded. These addresses are also commonly used
in service discovery protocols - also with the assumption that they
will reach "all nodes within the local network".
 
> This interpretation is present in several doccuments and

This would require modifications to existing and legacy host/router OS's;
I really don't think requiring such modifications would be a fast path
toward standardized methods for MANETs.

> In any event, I believe that we should establish consensus either way.

In earlier discussions on this topic, we presented a different approach.
The problem, as we see it, is that messages sent to the limited broadcast
address and the low-numbered multicast addresses (224.0.0.0 - .255) are
legislated as *not forwardable* beyond a single hop under RFC 1812 and the
IANA assigned numbers documents. In order to comply with existing standards
and to avoid breaking interoperability with existing implementations, we feel
that the best way to get these messages to travel further than a single hop
is to transmit them via IP-in-IP encapsulation through a well-known multicast
address that *is* forwardable - namely, a forwardable "ALL-MANET-NODES"
multicast address that is reserved with IANA within the range 224.0.1.0
through 239.255.255.255.

This approach can be implemented via software-configured tunnel interfaces
with no changes to existing host/router OS and application S/W. This approach
also allows control in terms of how many hops such encapsulated messages can
travel by setting a specific value in the IP_TTL field. But, the main point
is that service discovery applications which expect to receive service
advertisements and/or send service solicitation requests using the limited
broadcast address or one of the low-numbered multicast addresses will *still*
send and receive messages using the *same* addresses. The IP-in-IP encapsulation
will simply allow the messages to be forwarded futher than a single hop.

(NOTE: This all assumes an efficient MANET multicast routing protocol, which
falls under the jurisdiction of the MANET routing protocol designers.)

---

From: [email-masked]
Date: Thu, 17 May 2001 12:25:37 +0200 (CEST)

Fred,

On Thu, 10 May 2001, Fred L. Templin wrote:

 > some additional ideas.

Thanks ;)

 >  I am enclosing some comments to your message below.
 >

Excellent, please find my comments to your comments below. I've been
snipping rather hard to save bandwidth - hope it doesn't disturb too much.

<SNIP>

 > single MANET.

Naturally, yes.

 > Additionally, nodes that are members of the same CIDR prefix

You do mean throughout the MANET, right? - not throughout the network in
general? If it's throughout the MANET, then I agree completely on
your following statement.

 > addresses within the MANET may *appear* to be scattered about in

Makes sense, yes. In a sense, what I wrote about IP sequence could (and,
honestly, should) have been written as CIDR prefix. My bad ;(

<SNIP - interresting discussion on the first two sublayers in OSI layer 3>

 > carried by BGP.)

First, I agree: it is not likely (nor desireable) to carry host-routes
outside a very limited scope. I believe that (in part) this is also why
mobile IP is in existance (since, in a node, host-routes take priority
when deciding upon a route for a packet, mobility could easilly be
addressed functionality-wise by "just" adverticing host-routes - and not
involve mobile agents, renumbering and what not.....however maintenance of
a large number of host-routes is undesireable).

Thus, it would definitely make sense to require the nodes within a MANET
to be aggregatable.

 > The idea of repairing network partitions by tunneling
 > coordination between the gateways.

Yep - I saw the idea, but am not sure how one would go about doing so in a
"good" way. Clearly, it can be made work, though.

 > There are other possibilities as well

Outch ;) Then I hope you also envision some hirachy within the MANET: as
it is now (at least in what I have seen), routes within a MANET are
maintained as host-routes. If thousands of independant subnets (each, I
assume, with more than one node) converge to a single network, this may
raise difficulties?

 > *different* CIDR prefix.

In the case you describe, definitely yes...

 > This sounds like something that might not work well in existing
 > host/router OS's.
 > Additionally, unless you know exactly

 > toward standardized methods for MANETs.

I agree, that it would probably not be a viable path for short-term (or
even long-term) deployment of MANET protocols.

 > falls under the jurisdiction of the MANET routing protocol designers.)

In general, I agree that the perfect solution would be to maintain
compliance with RFC1812 and at the same time not break any existing
applications. I would like to add, though, that in my mind, the perfect
solution also should not introduce significant complexity to the the
routing protocols or should introduce a significant overhead.

I have a general problem with the requirement that an efficient MANET
multicasting protocol be in existance - essentially for a unicast routing
protocol to function. I know that this is not what you are saying in the
above. However if the usually expected semantics of the non-forwardable
IP-addresses is to be preserved through tunneling and multicasting, then
some other mechanism is required to be in place for the
"neighborcasting". If I recall correctly, you proposed that a
non-relayable multicast-address be set asside for this purpose? If so,
then that non-relayable address should be treated differently from the
other non-relayable addresses, which are being tunneled to the entire
subnet - or am I missing something? Also, this would introduce some
requirements of (at least some) multicasting capabilities of all nodes.

I do not mean to sound "negative" in the above - I'm just trying to
clarify the concequences of the different approaches at this problem.

---

From: "Fred L. Templin" <[email-masked]>
Date: Thu, 17 May 2001 17:54:36 -0700

Thomas,

I've cut out alot of stuff for the sake of brevity in order to

> your following statement.

Yes - throughout the MANET. The MANET partitioning issue makes life
difficult enough the way it is without inferring a random distribution
throughout the network in general.

> assume, with more than one node) converge to a single network, this may

The problem of achieving greater levels of aggregation for such a
jumbo MANET would be no more or less difficult than the same situation
that administrators of large corporate networks, ISPs, etc. face in the
existing global Internet infrastructure. Administrators of such large
and complex sites are under constant pressure to reduce the number of
aggregated prefixes they announce over their BGP peering sessions to
other autonomous systems. Strategies for dealing with this in IPv4 are
becoming increasingly difficult as the available IPv4 address space
dwindles and becomes fragmented. But, the strategies would be no
different for a jumbo MANET than they would for a large and complex
site in the existing wired infrastructure.

In IPv6, the aggregation issue is essentially non-existent since even
the finest-grain prefix allocation unit (/48) allows the assignment of
up to 64K individual SLA-based subnets out of a single aggregated prefix.

> above.

I suppose one could optionally use an INeffiecient MANET multicasting
protocol (like simple flooding), but I don't think it would be well
received! :^} If we want to make multicasts and/or broadcasts go more
than a single hop, however, there must be SOME kind of protocol in
effect to avoid loops and the resultant broadcast/multicast "storms"
that would ensue. 

> However if the usually expected semantics of the non-forwardable

I may not have articulated this very clearly in earlier messages, but
I am not suggesting tunneling *all* of the non-forwardable broadcast
and multicast addresses through the forwardable "All-MANET-Nodes"
multicast address. Instead, I am suggesting selective tunneling of
ONLY those non-forwardable addresses we would like to travel more than
a single hop. Again, this is something that can be set up through S/W
configuration options only. So, if you wanted to treat one of the
low-numbered multicast addresses as an "All-MANET-Neighbors" address
for what you are calling "neighborcasting" then you would simply
avoid a tunnel configuration that matches this address. Perhaps MANET
should also reserve a specific non-forwardable "All-MANET-Neighbors"
multicast address with IANA to go along with the forwardable
"All-MANET-Nodes" multicast address we have already suggested.
(Actually, I think we suggested such an All-MANET-Neighbors address
in the TBRPF draft.)

Fred
[email-masked]

---

From: Richard <[email-masked]>
Date: Thu, 31 May 2001 04:59:20 -0700

Thomas,

I would like to add a few thoughts to Fred's response regarding 
our proposed approach for dealing with limited broadcasts and 
non-forwardable multicasts using IP-in-IP encapsulation/tunneling 
(see below).  

(Lines preceded by ">>" were writen by Fred Templin.)

 >> falls under the jurisdiction of the MANET routing protocol designers.)

(Lines preceded by ">" were written by Thomas Clausen.)

> solution also should not introduce significant complexity to the 

The method we propose does involve some overhead in the form of an
additional IP header that is attached to a packet that already has 
an IP header.  I address this issue below.  (I don't think the proposed 
method adds significant complexity.)

> requirements of (at least some) multicasting capabilities of all nodes.

As noted in my message of April 8, the idea of using IP-in-IP 
encapsulation came from IP over ATM (which encapsulates IP packets 
into ATM cells), or more generally, IP over NBMA.  The idea is that 
the MANET emulates (i.e., appears to be) one or more conventional 
broadcast subnet(s) to a higher layer IP internetwork. 
Thus, we have IP over MANET, where the MANET is also IP-based. 
Therefore, unlike IP over ATM (or NBMA), encapsulation is not required 
for IP over MANET for unicast and for most multicast addresses,
as long as the internetwork and the MANET both use IPv4 (or both use IPv6).  
Thus, referring to your concern about overhead, I think we should 
consider ourselves lucky that encapsulation is required *only* 
for limited broadcasts (255.255.255.255) and non-forwardable multicasts
(224.0.0.x) (e.g., All_OSPF_Routers).

Regarding your question of how to decide which non-forwardable addresses 
are tunneled/encapsulated, Fred suggested one approach in his last 
message, and I would like to describe another (perhaps complementary) 
approach which is motivated by the above discussion of IP over MANET. 

In this approach, *all* non-forwardable addresses are treated the same 
by all MANET routers (they are not forwarded, in compliance with RFC1812). 
Encapsulation is used only when an internetwork router (not a MANET 
router) wants to send limited broadcasts and non-forwardable multicasts 
over the MANET (which is viewed as one or more conventional subnets).  
A MANET gateway would perform this encapsulation, which would give 
the packet a forwardable multicast address.

As Fred noted, this approach would not necessarily require the existence 
of an efficient MANET multicast protocol, but would require at least 
a reasonable MANET broadcast protocol which could be used to reach 
all nodes in the MANET.  Given the broadcast nature of MANETs, 
I think we can assume the existence of such a protocol.

I would like to add some thoughts on subnet-directed (i.e., 
prefix-directed) broadcasts in MANETs.  (Some of these thoughts 
resulted from a discussion I had with Fred.)  As Fred mentioned, 
a MANET can contain multiple subnets (where a subnet is defined 
as all the nodes in the MANET with a common prefix). The nodes 
in the MANET with a given prefix need not be contiguous, i.e., 
some of them may be reachable only if intermediate nodes are used that 
do not have the given prefix.  Therefore, it is not clear to me whether 
a prefix-directed broadcast should reach all nodes in the MANET having 
the prefix, or just the nodes that are reachable (from the gateway) 
using only intermediate nodes that have the same prefix.  Moreover, 
if the former is the case, then the gateway could either (efficiently) 
multicast such packets to only the nodes having the given prefix, 
or could broadcast such packets to *all* nodes in the MANET. 
In summary, there are three possibile rules:

  1. Broadcast (e.g., flood) to all nodes in the subnet that are 
     reachable using only intermediate nodes that have the subnet prefix. 
  2. Multicast to all nodes in the MANET having the given prefix
     (including "drifters").
  3. Broadcast (e.g., flood) to all nodes in the MANET.

The third rule would be very inefficient if the MANET consists
of a large number of subnets, so I think one of the first two 
rules would be better.

Richard

----------
Richard Ogier
Sr. Research Engineer
SRI International
[email-masked]

---

From: "Fred L. Templin" <[email-masked]>
Date: Thu, 17 May 2001 17:54:36 -0700

Thomas,

Fred
[email-masked]