\section{Background Issues}

Why do we feel we need to replace ARP with an authenticated link
layer addressing system?  The reasons include lack
of security, problems inherent in the IP subnet architecture, and
our desire to more closely integrate ICMP router discovery packets
with mobility in general and Mobile-IP in particular.  

From a
security point of view, IP address spoofing at the link layer is
too easy.  Steve Bellovin pointed out in his classic security paper
on TCP/IP \cite{Bellovin} that ARP spoofing is dangerous.  One
system A can pretend to be another system B by responding to ARP
broadcast queries for B with a binding of (B's ip address,  A's
mac address).  A system may overwrite another system's ARP cache
entry with a gratuitous ARP.  This function is sometimes necessary
due to a controller board change.  Thus ARP spoofing may even be
viewed as a feature.  However ARP overwrites are not good from a security
point of view, especially when coupled with higher level protocols
that only authenticate a host in terms of its IP address.

There is probably no reason the
ARP protocol cannot be extended to include authentication, even
though on the surface the protocol does not support an extension mechanism.  
However we chose instead to place authenticated MAC addresses into
the ICMP data payload in ICMP router discovery packets.  Mobile-IP
uses such packets and has already extended them in order
to announce the existence of agents.  We feel our ICMP router discovery
extensions (MAC and otherwise) integrate with Mobile-IP.

There is an important problem that is often coupled with ARP,
but is not really ARP's fault.  That problem is: how are IP subnets
to be interpreted at a link where ad hoc networks may occur?

By definition, mobile systems based on Mobile-IP bring with them
the semantic that any given link-layer may have more than one
IP subnet resident.  The notion of "one wire, one IP subnet" has been
under stress for awhile partially due to network exhaustion in 
IP version 4.  Any wired segment may have to tolerate greater than one
class C subnet, since such a subnet is limited at a maximum to 254 hosts 
(less if further divided by subnet masks).  Mobile-IP makes a necessity
out of the notion of many subnets on one segment since a Mobile-IP node
retains its IP address as it moves from one subnet point of attachment
to another.  A subnet with a {\it Foreign Agent} (a FA is a Mobile-IP 
entity that allows the mobile nodes access to the network) present 
may potentially have many mobile nodes present, each with a IP 
net address different from all the other Mobile systems 
including that of the interface at the Foreign Agent itself.

In terms of TCP/IP routing, subnetting has a number of functions.  We might
distinguish a "high-level" function of routing aggregation; i.e.,
it is common knowledge at this point that unicast IP routing is based
on the exchange of a two-tuple consisting of (IP address, net mask). 
\footnote {Actually we wish this was true, but it will not be until
RIP v1 is replaced by RIP v2 or OSPF everywhere.}
Core IP routers
are under stress from too many routes in routing tables and routing
aggregation is a grim and important necessity.  On the other hand,
subnetting has a low-level function that typically manifests itself
in the routing implementation of a particular operating system.  
A subnet mask is AND'ed with a IP destination address to determine
if the destination is either on the link or not on the link.  
An algorithm that has been used in very simple TCP/IP implementations
might be stated as follows:
\footnote{See \cite{Comer} for an example.}
\begin{tabbing}
123\=456\=789\kill
\>	if dest IP address AND subnet mask indicate same subnet \\
\>\>		assume same link and ARP for the destination  \\
\>	else  \\
\>\>		send to default router \\
\>\>  		(use ARP to talk to router) \\
\end{tabbing}

The router itself must share a subnet/subnet mask association with
the leaf node.  As a  consequence, if a link has greater than
one subnet resident on it,  a node on IP subnet A cannot directly send
packets to a node of subnet B, even though they share a physical connection.
The router must have one IP address on both subnets and packets must be
sent twice on the same wire.  
Mobile nodes with different subnets and a shared radio link
cannot talk directly to each other even if one is laid on top of the
other.  They would need a router to communicate, of course.
This is truly absurd for mobile systems.  
We feel that the notion of IP subnets as a link-layer routing basis
for mobile systems is not useful.  Current end-system routing algorithms
may not exactly be as stupid as the above algorithm, but the 
subnetting semantic will probably exist \footnote{ To be fair,
it should be noted that the above algorithm only uses ARP
for direct delivery on a interface that speaks MAC addresses.  
We cannot blame the ARP protocol itself as it doesn't care about 
subnetting.  Historically it came first, and nothing prevents it
from being employed in a subnet-free way.}.
The current 4.4 BSD routing algorithm employs a mechanism that 
is not as brutal as the above algorithm, but has the same result.  
A {\it clone} or {\it direct} route \cite{Stevens} is installed 
for every interface (link) and attempts to talk to same subnet nodes 
result in a magic cloned link-layer route (LLINFO) that is automatically installed and used.  The end result is the same.  

There is a further problem inherent in the use of certain kinds of
link-layer hardware that needs to be addressed in link-layer communication
between all mobile nodes.  This problem is tied to the notion
that a shared subnet means you can assume reachability between
two nodes.  One might distinguish two kinds of hardware; e.g.,
wired broadcast-based media like ethernet, and 
media like WaveLAN(tm), a 2 megabit spread-spectrum radio LAN
technology.  We could state that ethernet has an attribute called:
{\it shared address reachability}. Radio (and infrared) devices
that are highly likely to be used with mobile nodes do not have that
attribute.  In their case, we have to say: 
{\it "shared addresses do not mean reachability"}.

In a trivial sense, a mobile node cannot
assume that a cousin with a shared IP subnet must be resident simply
because of the shared subnet.  The cousin might be away on some other
subnet, or unreachable in a closet somewhere.

But there is a more serious flaw lurking in the shared reachability
notion.  Assume there are four systems, A (MN), B(FA), C(MN), and D(router) 
\begin{figure} [h]
\begin{center}
\mbox{\psfig{figure=/circles.ps}}
\caption{4 Radio Nodes, A can hear B, but not C, etc.}
\end{center}
\end{figure}
arranged from left to right.  (Please see Figure 1).
Assume that each has a radio cell that is roughly circular and that A and B's
cells overlap, but the cells for A and C do not overlap.  B in turn can
hear C (and A), but cannot hear D.  D can only hear C.
Assume that A, B, C, and D all share a common IP
subnet and that A and C are mobile nodes, B is a Mobile-IP Foreign
Agent, and D is an agent (or router).

If A tries to talk to C, with current routing implementations,
it will ARP for it, without success.  If C moved to a Foreign Agent
far away, A might still ARP for it.  To add insult to injury, the 
ICMP redirection mechanism could possibly rear its (in this case, ugly) 
head.  Assume
that A is using B as its FA, which enables it to talk to some other
host X.  B and D might be on the same interior ethernet subnet.
Hence B might "know" due to IP routing assumptions, that D is a
better router "on the same link" in the case of a given destination
X.  It might then send a redirect to A to tell it that it should
use D to get to X.  With many current kernel routing implementations,
A would simply accept that routing redirect and no longer be able
to talk to X.  Given the above two problems,
we assert that the assumption of shared address reachability
due to a shared subnet address is not valid on
multicast-based "lan" radio links.  It makes sense on ethernet.
It makes less sense on radio links and other similar link technologies.
			
From a survivability point of view,  mobile nodes from different IP subnets
should be able to talk directly to each other without
needing a router.  They should be able to flush MAC address state
in other systems easily (their MAC addresses might change if a PCMCIA
card changes) and they should ignore such things as ICMP
redirects.  There should certainly be no argument that an ad hoc
network is not useful or needed.  Our proposed protocol deals with
link-layer reachability and addresses a fair number of the problems
mentioned above 
\footnote {ICMP redirects are not addressed.  They might be ignored on a per interface basis.}.

It is one form of an ad hoc routing
protocol, but it is not multi-hop and only applies to same link
reachability.  Other research is being done in higher level ad hoc
routing.  For example, Charles Perkins at IBM \cite{PerkinsADHOC} has
proposed a vector-distance protocol that would allow participating Mobile
Nodes to route each others packets.  Dave Johnson \cite{JohnsonADHOC}
has proposed a multi-hop protocol based on source-routing.  
It is possible that we may need a number of ad hoc protocols based on different
attributes including link technology and the type of motion
expected.  Certainly high-speed movement (F16s), might have to 
fallback on flooding.  A set of mobile systems that are moved 
from one building to another,  where they
will sit for days after deployment, could use a simple vector-distance based
technique where convergence takes a bit of time.  If scare bandwidth is
a concern, systems could take advantage of "on-demand" end system 
source-routing.  

Our simple authenticated beaconing proposal works for a number 
of ad hoc laptops sitting in a big open space using a technology like WaveLAN.  
One might also argue that it is not incompatible
with a multi-hop ad hoc protocol.  Our proposal informs systems about
direct reachability and it might be subsumed by or run alongside a
higher-level routing protocol in the same way that ES-IS \cite{Perlman}
is subsumed by IS-IS (ISO's routing protocol similar to OSPF \cite{Huitema}).
