draft-ietf-manet-imep-spec-00.txt   draft-ietf-manet-imep-spec-01.txt 
Internet Draft M.S. Corson Internet Draft M. S. Corson, UMD
Expiration: May 26, 1997 University of Maryland Expiration: February 7, 1999 S. Papademetriou, UMD
V. Park P. Papadopoulos, ORNL
Naval Research Laboratory V. Park, NRL
November 26, 1997 A. Qayyum, INRIA
August 7, 1999
An Internet MANET Encapsulation Protocol (IMEP) Specification An Internet MANET Encapsulation Protocol (IMEP) Specification
draft-ietf-manet-imep-spec-00.txt draft-ietf-manet-imep-spec-01.txt
Status of this Memo Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas, documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts. working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet- Drafts as reference time. It is inappropriate to use Internet- Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as ``work in progress."
To view the entire list of current Internet-Drafts, please check the To view the entire list of current Internet-Drafts, please check the
"1id-abstracts.txt" listing contained in the Internet-Drafts Shadow ``1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe), Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or
ftp.isi.edu (US West Coast). ftp.isi.edu (US West Coast).
Distribution of this memo is unlimited. Distribution of this memo is unlimited.
Abstract Abstract
This memo describes a multipurpose network-layer protocol---named the This memo describes a multipurpose network-layer protocol---named the
Internet MANET Encapsulation Protocol (IMEP)---designed to support Internet MANET Encapsulation Protocol (IMEP)---designed to support
the operation of many routing algorithms or other upper layer the operation of many routing algorithms, network control protocols
protocols intended for use in Mobile Ad hoc Networks (MANET). The or other Upper Layer Protocols (ULP) (where ``upper" denotes *any*
protocol incorporates mechanisms for supporting link status sensing, layer above IMEP) intended for use in Mobile Ad hoc Networks (MANET).
control message aggregation and encapsulation, broadcast reliability, The protocol incorporates mechanisms for supporting link status and
network-layer address resolution and provides hooks for interrouter neighbor connectivity sensing, control packet aggregation and
security authentication procedures. The IMEP also puts forth a encapsulation, one-hop neighbor broadcast (or multicast) reliability,
framework or architecture for MANET router and interface multipoint relaying, network-layer address resolution and provides
hooks for interrouter authentication procedures. Indirectly, the
IMEP also puts forth a framework for MANET router and interface
identification and addressing. identification and addressing.
The present specification is high-level and incomplete, giving only a
behavioral protocol description and proposed packet format. This
version of this draft is intended primarily to acquaint readers with
the concept of the protocol. A subsequent revision will detail the
protocol's mechanisms and data structures.
1. Introduction 1. Introduction
The primary purpose of the Internet MANET Encapsulation Protocol The primary purpose of the Internet MANET Encapsulation Protocol
(IMEP) is to improve overall network performance by reducing the (IMEP) is to improve overall network performance by reducing the
"number" of network control message broadcasts through encapsulation *number* of network control packet broadcasts through encapsulation
and aggregation of multiple MANET control messages (e.g. routing and aggregation of multiple MANET control packets (e.g. routing
protocol packets, acknowledgements, link status sensing messages, protocol packets, acknowledgements, link status sensing packets,
network-level address resolution, etc.) into larger IMEP messages. ``network-level" address resolution, etc.) into larger IMEP messages.
Usage of the IMEP is desirable because per-message, multiple access Usage of the IMEP is desirable because per-message, multiple access
delay in contention-based schemes such as CSMA/CA, IEEE 802.11, FAMA delay in contention-based schemes such as CSMA/CA, IEEE 802.11, FAMA
etc. is significant, and thus favors the use of fewer, larger etc. is significant, and thus favors the use of fewer, larger
messages. It would also be useful in reservation-based, time-slotted messages. It also may be useful in reservation-based, time-slotted
access schemes where smaller packets must be aggregated into access schemes where smaller packets must be aggregated into
appropriately-sized IP packets for transmission in a given time slot. appropriately-sized IP packets for transmission in a given time slot.
Upper layer protocols *other than routing* may make use of this Upper Layer Protocols (ULP) *other than routing* may make use of this
encapsulation functionality for the same purpose. encapsulation functionality for the same purpose.
Its secondary purpose concerns the commonality of certain Its secondary purpose concerns the commonality of certain
functionality in many network-level routing algorithms. Many functionality in many network-level control algorithms. Many
algorithms intended for use in a MANET will require common algorithms intended for use in a MANET will require common
functionality such as link status sensing, security authentication functionality such as link status sensing, security authentication
with adjacent routers, broadcast reliability of network control with adjacent routers, one-hop neighbor broadcast (or multicast)
messages, etc. This common functionality can be extracted from these reliability of control packets, etc.. This common functionality can
individual protocols and put into a unified, generic protocol useful be extracted from these individual protocols and put into a unified,
to all. MANET routing algorithms would also benefit from a common generic protocol useful to all. MANET control algorithms would also
approach to router and interface identification and addressing, and benefit from a common approach to router and interface identification
this protocol provides a framework for unifying the protocols under a and addressing, and this protocol supports a framework for unifying
common architecture. the protocols under a common architecture.
The IMEP will run at the network layer (see Figure 1), and will be an The IMEP will run at the network layer (see Figure 1), and will be an
adjunct to whichever network routing protocol is using it. Routing adjunct to whichever network protocol is using it. ULP packets will
control packets will be encapsulated in IMEP messages, which will be be encapsulated in IMEP messages, which will be further encapsulated
further encapsulated into IP packets. into IP packets.
+------+ +-----+ +-----+ +-----+ +------+ +-----+ +-----+ +-----+
|Telnet| | FTP | | TFTP| ... | ... | |Telnet| | FTP | | TFTP| ... | ... |
+------+ +-----+ +-----+ +-----+ +---------+ +------+ +-----+ +-----+ +-----+ +---------+ +-----+
| | | | | Routing | | | | | | Routing | | ULP |
+-----+ +-----+ +-----+ +---------+ +-----+ +-----+ +-----+ +---------+ +-----+
| TCP | | UDP | ... | ... | | | TCP | | UDP | ... | ... | | /
+-----+ +-----+ +-----+ +---------+ +-----+ +-----+ +-----+ +---------+
| | | | IMEP | | | | <----- | IMEP |
+----------------------------------------+ +---------+ +---------------------------------+ +---------+
| Internet Protocol & ICMP & IGMP & IMEP | | | Internet Protocol & ICMP & IGMP | |
+----------------------------------------+ +---------+ +---------------------------------+ +---------+
| | IP | | | IP |
+---------------------------+ +---------+ +---------------------------+ +---------+
| Local Network Protocol | | Local Network Protocol |
+---------------------------+ +---------------------------+
Protocol Relationships Encapsulation Protocol Relationships Encapsulation
Figure 1 Figure 1
2.0 Terminology 2.0 Terminology
This section provides definitions for the terminology used throughout This section provides definitions for the terminology used throughout
this document. Many of these definitions may be replaced by or this document. Many of these definitions may be replaced by or
merged with those of the MANET working group's terminology draft [1] merged with those of the MANET working group's terminology draft now
now under development. under development.
MANET router or router: MANET router or router:
A device---identified by a "unique Router ID" (RID)---that exe- A device---identified by a ``unique Router ID" (RID)---that exe-
cutes a MANET routing protocol and, under the direction of cutes a MANET routing protocol and, under the direction of
which, forwards IP packets. It may have multiple interfaces, which, forwards IP packets. It may have multiple interfaces,
each identified by an IP address. Associated with each inter- each identified by an IP address. Associated with each inter-
face is a physical-layer communication device. These devices face is a physical-layer communication device. These devices
may employ wireless or hardwired communications, and a router may employ wireless or hardwired communications, and a router
may simultaneously employ devices of differing technologies. may simultaneously employ devices of differing technologies.
For example, a MANET router may have four interfaces with For example, a MANET router may have four interfaces with
differing communications technologies: two hardwired (Ethernet differing communications technologies: two hardwired (Ethernet
and FDDI) and two wireless (spread spectrum and impulse radio). and FDDI) and two wireless (spread spectrum and impulse radio).
skipping to change at page 4, line 9 skipping to change at page 4, line 9
communications technology: communications technology:
The means employed by two devices to transfer information The means employed by two devices to transfer information
between them. between them.
connection: connection:
A physical-layer connection---which may be through a wired or A physical-layer connection---which may be through a wired or
wireless medium---between a device attached to an interface of wireless medium---between a device attached to an interface of
one MANET router and a device utilizing the same communications one MANET router and a device utilizing the same communications
technology attached to an interface on another MANET router. technology attached to an interface on another MANET router.
From the perspective of a given router, a connection is a
(interface, adjacency) pair.
link: link:
A "logical connection" consisting of the logical *union* of one A ``logical connection" consisting of the logical *union* of one
or more connections between two MANET routers. Thus a link may or more connections between two MANET routers--identified by a
consist of a heterogeneous combination of connections through (RID, RID) pair. Thus a link may consist of a heterogeneous com-
differing media using different communications technologies. bination of connections through differing media using different
communications technologies.
neighbor: neighbor:
From the perspective of a given MANET router, a "neighbor" is From the perspective of a given MANET router, a ``neighbor" is
any other router to which it is connected by a link. any other router to which it has a link.
adjacency: adjacency:
The name given to an "interface on a neighboring router". The name given to an ``interface on a neighboring router". From
the perspective of a given router, a connection is a (interface,
adjacency) pair.
topology: topology:
A network can be viewed abstractly as a "graph" whose "topology" A network can be viewed abstractly as a ``graph" whose ``topol-
at any point in time is defined by set of "points" connected by ogy" at any point in time is defined by set of ``points" con-
"edges". (This term comes from the branch of mathematics bear- nected by ``edges". (This term comes from the branch of
ing the same name that is concerned with those properties of mathematics bearing the same name that is concerned with those
geometric configurations (such as point sets) which are unal- properties of geometric configurations (such as point sets)
tered by elastic deformations (such as stretching) that are which are unaltered by elastic deformations (such as stretching)
homeomorphisms.) that are homeomorphisms.)
physical-layer topology: physical-layer topology:
A topology consisting of connections (the edges) through the A topology consisting of connections (the edges) through the
*same* communications medium between devices (the points) com- *same* communications medium between devices (the points) com-
municating using the *same* communications technology. Multi- municating using the *same* communications technology. Multi-
ple physical-layer topologies may exist for a given medium and ple physical-layer topologies may exist for a given medium and
communications technology if adaptive or proactive power con- communications technology if adaptive or proactive power con-
trol, or other physical-layer mechanisms are employed. trol, frequency or code division, or other physical-layer
mechanisms are employed.
network-layer topology: network-layer topology:
A topology consisting of links (the edges) between MANET routers A topology consisting of links (the edges) between MANET routers
(the points) which is used as the basis for MANET routing. Since (the points) which is used as the basis for MANET routing. Since
"links" are the logical union of physical-layer "connections", ``links" are the logical union of physical-layer ``connections",
it follows that the "network-layer topology" is the logical it follows that the ``network-layer topology" is the logical
union of the various "physical-layer topologies". union of the various ``physical-layer topologies".
IP routing fabric: IP routing fabric:
The heterogeneous mixture of communications media and technolo- The heterogeneous mixture of communications media and
gies through which IP packets are forwarded whose topology is technologies through which IP packets are forwarded whose topol-
defined by the network-layer topology. ogy is defined by the network-layer topology.
Security Context:
A security context between two routers defines the manner in
which two routers choose to mutually authentication each other,
and indicates an authentication algorithm and mode.
Mobility Security Association:
A collection of security contexts, between a pair of routers,
which may be applied to IMEP protocol messages exchanged between
them.
Security Parameter Index (SPI):
An index identifying a security context between a pair of
routers among the contexts possible in the Mobility Security
Association.
3.0 Protocol Overview 3.0 Protocol Overview
The mechanisms contained in the IMEP are: The mechanisms contained in the IMEP are:
Link/Connection Status Sensing Message Aggregation (AGGR)
Control Message Aggregation Network-layer Address Resolution (NARP)
Broadcast Reliability Link/Connection Status Sensing (LCSS)
Network-layer Address Resolution Broadcast Reliability (REL)
Security Authentication Multipoint Relaying (MPR)
3.1 Link/Connection Status Sensing Authentication (AUTH)
3.1.1 Definition of Link/Connection Status Message aggregation occurs as packets from ULPs become IMEP objects,
and IMEP packs a number of objects into larger IMEP messages for
transmission. NARP--a protocol to determine the *binding* of a RID
with each of its IP interface address--occurs implicitly in the
current specification as the router ID of a given router is put in
the header of each IMEP message. As each IMEP packet is encapsulated
in an IP packet, and its header contains the IP address of the
transmitting interface in the source field of the IP packet, the
binding can be made on reception of any IMEP packet (more on this
later). Usage of the remaining mechanisms is *optional*. The fol-
lowing dependency graph shows their relationships.
Many routing protocols require accurate knowledge of the status of AGGR---NARP
links/connections between neighboring routers. "Link status" in the |
IP routing fabric is determined from the union of the status of +------+-------+
physical-layer "connections" between interfaces. | | |
REL LCCS MPR
|
-----+----
| |
AUTH MPR
This simply means that everything uses IMEP's aggregation facility.
NARP occurs implicitly in every IMEP transmission. Usage of reliabil-
ity, LCCS, MRP and AUTH are optional. MRP traffic may be sent reli-
ably or unreliably. Authentication, if enabled, occurs reliably.
3.1 Relationship with Upper Layer Protocols
IMEP is intended to support the operation of many ULPs. ULPs that
wish to utilize IMEP must dynamically *register* with an IMEP imple-
mentation prior to using IMEP (more on registration in a moment).
3.1.1 Protocol Type Values
All ULPs which intend to utilize IMEP must have protocol type value,
and must give this value to IMEP during registration. This value is
used by a receiving IMEP implementation for purposes of demultiplex-
ing ULP objects within a received IMEP message so that they may be
passed to the appropriate ULPs. IMEP implementations receiving
objects with unknown (i.e. unregistered) protocol type values will
silently discard those objects. Several protocol types have already
been assigned well-known values (see the protocol grammar section),
but a protocol need not have a pre-assigned type value to make use of
IMEP, nor must the well-known assignments be adhered to. IMEP
currently does not specify how protocol type values are assigned or
used within a given administrative domain.
3.1.2 Protocol Handles
ULPs registering with IMEP must pass to IMEP a protocol ``handle"
which IMEP may then use to pass information back to the ULP. The
mechanism used to implement the handle is not specified (this is
implementation dependent)--it could be a pointer to a function with a
known signature, an object reference in a middleware-based implemen-
tation, etc..
3.1.3 Protocol Epitaphs
ULPs registering with IMEP must specify an ``epitaph" object. The
epitaph object specifies a signal to be broadcast reliably to all
one-hop peer ULPs if the registered ULP fails. This permits peer
ULPs (on neighboring routers) to take appropriate action in case of
peer process failure. Protocols may re-register with IMEP at any
time in order to change the epitaph object, or to remove it if
desired.
Registration with an ``epitaph" object amounts to creating and main-
taining a symbiotic relationship between IMEP and a registered ULP.
There must exist a mechanism (not specified--implementation depen-
dent) that guarantees ``mutual liveness" to each protocol so that,
should either protocol fail, the other is reliably informed within
the time of a BEACON_PERIOD (defined subsequently).
The principle purpose for epitaph-based registration is *bandwidth
conservation*. Without such a mechanism, it is not possible for peer
ULP processes--who have previously exchanged control information and
remain connected via IMEP--to be assured of mutual vitality without
exchanging keepalive packets over the communication channel.
3.1.4 IMEP Signalling Support
ULPs registering with IMEP must indicate the level of IMEP signalling
support (ISS) they wish to receive from IMEP. IMEP signalling sup-
port is only meaningful if LCSS is enabled, and consists of signals
being generated by IMEP in response to topological change events
detected by LCSS, and then passed to subscribing ULPs (those ULPs
requesting ISS). Three levels of support are possible:
0) Connection-level:
All connection-level topological change events are passed to the
subscribing ULPs. Connection-level topological change events
consist of ``connection" activation and failure (recall a con-
nection consists of an (interface, adjacency) pair). Thus, all
physical-layer topology information is passed to the ULPs, per-
mitting these ULPs to have a complete internal view of the IP
routing fabric.
1) Link-level:
All link-level topological change events are passed to the sub-
scribing ULPs. Link-level topological change events consist of
``link" activation and failure (recall a link consists of a
(RID, RID) pair). Thus, only network-layer topology information
is passed to the ULPs, permitting these ULPs to have only an
external view of the IP routing fabric.
2) Disabled:
No topological change events generated by IMEP as a result of
LCSS are passed to the ULP. This is the default mode.
3.1.5 ULP Registration
ULPs must register with IMEP *prior* to usage. ULP registration con-
sists of passing IMEP a protocol type value, a *handle* to the ULP
allowing IMEP to pass received objects to it (handle mechanism not
specified--implementation dependent), an *epitaph* object (this may
be null), and a parameter indicating the level of IMEP signaling sup-
port desired by the ULP.
3.2 Message Aggregation
MANET routing (and other) control protocols exchange control informa-
tion and other data in the form of routing control packets or
``objects". To minimize the number of channel accesses generated by
control traffic, the IMEP aggregates and encapsulates these objects
into larger IMEP ``messages". The objects are treated as ``opaque"
objects by the IMEP protocol; i.e. IMEP is not aware of the contents
of the objects, only of the protocol ``type" of the object block
(necessary for protocol demultiplexing at a receiver) and the length
of each object. These ULP object blocks are contained in yet larger
IMEP messages which are passed to the IP layer for encapsulation and
forwarding. A single IMEP message can contain a mixture of reliable
and unreliable objects. The details can be found in the IMEP message
format section.
3.3 Network-level Address Resolution
IMEP supports a framework or architecture for MANET router and inter-
face identification and addressing. IMEP operates simultaneously on
two different topological levels: the ``logical network" topology
level---which is concerned with interrouter connectivity---and the
``physical" topology level---which is concerned with interface con-
nectivity. Router IDs (RID) identify routers in the logical topol-
ogy, and IP addresses identify interfaces in the physical topology.
There may be *multiple* IP addresses associated with a given RID.
The purpose of a Network-level Address Resolution Protocol (NARP) is
to discover the mapping between RIDs and IP addresses. This is
envisioned typically only to be needed when a new connection is
discovered, as it is necessary to be able to associate an interface
(an IP address) with a router (an RID).
+----------+
| Router | RID
+----------+
| |
+--------------+ +--------------+
| Interface | | Interface | IP Address
+--------------+ +--------------+
| |
+--------------+ +--------------+
| Phys Device | | Phys Device | MAC Address
+--------------+ +--------------+
Figure 4: RIDs, IP and MAC addresses
While it is true that---as currently defined---RIDs are not
``addresses" in the strict sense, they do uniquely identify a router
for purposes of internal routing computations and somewhat resemble a
logical ``router address". Thus, the IP address-to-RID mapping is
similar in spirit to IP address-to-MAC address mapping performed by
the present ARP protocol. Each mapping simply associates an IP
address with another identifier as shown in Figure 4. As with ARP, a
``reverse" mapping is also defined as the Reverse Network-level
Address Resolution Protocol (RNARP). However, unlike RARP, a RNARP
request seeks to discover the *set* of IP addresses associated with a
given RID. The two mappings are shown in Figure 5.
ARP: IP --> MAC RARP: MAC --> IP
NARP: IP --> RID RNARP: RID --> {IP1,IP2,...,IPn}
Figure 5: ARP/RARP and NARP/RNARP
NARP is currently implemented *implicitly* through inclusion of the
RID in every IMEP message header. RNARP is not required in the
present specification, but may be specified and required in future
versions if deemed necessary.
3.4 Link/Connection Status Sensing
3.4.1 Definition of Link/Connection Status
Link/Connection Status Sensing (LCSS) is an optional mode that may be
enabled in IMEP. Many control protocols require accurate knowledge
of the status of links/connections between neighboring routers.
``Link status" in the IP routing fabric is determined from the union
of the status of physical-layer ``connections" between interfaces.
The relationship of interfaces, adjacencies, connections and links is The relationship of interfaces, adjacencies, connections and links is
depicted in Figure 2 from the perspective of router i. Router i has depicted in Figure 2 from the perspective of router i. Router i has
two interfaces f1 and f2, each of which has a physical-layer connec- two interfaces f1 and f2, each of which has a physical-layer connec-
tion with multiple interfaces attached to other routers---these tion with multiple interfaces attached to other routers---these
interfaces are referred to as adjacencies from router i's perspective interfaces are referred to as adjacencies from router i's perspective
and are numbered with c's. In this figure, there are two connections and are numbered with a's. In this figure, there are two connections
(f1,c1) and (f2,c2), the logical union of which composes the logical (f1,a1) and (f2,a2), the logical union of which composes the logical
link (i,k) between routers i and k. link (i,k) between routers i and k.
+----------+ +----------+
| Router i | | Router i |
+----------+ +----------+
+--------------+ +--------------+ +--------------+ +--------------+
| Interface f1 | | Interface f2 | | Interface f1 | | Interface f2 |
+--------------+ +--------------+ +--------------+ +--------------+
| | | |
| | | |
| | | |
| | | |
skipping to change at page 6, line 18 skipping to change at page 10, line 26
+--------------+ +--------------+ +--------------+ +--------------+
| Interface f1 | | Interface f2 | | Interface f1 | | Interface f2 |
+--------------+ +--------------+ +--------------+ +--------------+
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
+--------------+ +--------------+ +--------------+ +--------------+
| Adjacency c1 | | Adjacency c2 | | Adjacency a1 | | Adjacency a2 |
+--------------+ +--------------+ +--------------+ +--------------+
+----------+ +----------+
| Router k | | Router k |
+----------+ +----------+
Figure 2: Shown from router i's perspective, interfaces f1 and f2 are Figure 2: Shown from router i's perspective, interfaces f1 and f2 are
connected to adjacencies c1 and c2 via connections (f1,c1) and connected to adjacencies a1 and a2 via connections (f1,a1) and
(f1,c2)---the union of which forms link (i,k). (f1,a2)---the union of which forms link (i,k).
The status of an connection may be INcoming or OUTgoing (either of The status of a connection may be INcoming or OUTgoing (either of
which meaning it is unidirectional) or BIdirectional. A unidirec- which meaning it is unidirectional) or BIdirectional. A unidirec-
tional link is composed from one or more similarly-directed, uni- tional link is composed from one or more similarly-directed, uni-
directional connections. A BIdirectional link may be composed from directional connections. A BIdirectional link may be composed from
the union of one or more bidirectional connections, or two or more the union of one or more bidirectional connections, or two or more
oppositely-directed, unidirectional connections, or some combination oppositely-directed, unidirectional connections, or some combination
thereof. A link which is present (i.e. which has a non-null status, thereof. A connection or link which is present or ``active" (i.e.
and is either uni or bidirectional), is referred to as "UP". A link which has a non-null status, and is either uni or bidirectional), is
which is not present (i.e. which has a null status) is referred to as referred to as ``UP". A connection or link which is not active (i.e.
"DOWN". which has a null status) is referred to as ``DOWN".
The IMEP may be configured to run in the following "connection notif- The IMEP may be configured to run in the following ``connection
ication" modes: notification" modes:
BI-directional: BI-directional:
This mode requires that physical-layer connectivity between two This mode requires that physical-layer connectivity between an
interfaces be established in *both* IN and OUT directions before interface and an adjacency be established in *both* IN and OUT
an connection is considered *present* and the upper layer rout- directions before a connection is considered UP, and any
ing protocol is subsequently notified. registered ULPs are subsequently notified.
UNI-directional: UNI-directional:
This mode requires that physical-layer connectivity between two This mode requires that physical-layer connectivity between an
interfaces need only be established in one direction (IN or OUT) interface and an adjacency need only be established in one
before an connection is considered present and the upper layer direction (IN or OUT) before a connection is considered UP and
routing protocol is subsequently notified. the registered ULPs are subsequently notified.
As determined by the connection notification mode, the upper layer As determined by the connection notification mode, the ULP is noti-
routing protocol is notified whenever there is a change (addition, fied whenever there is a change (addition, modification, deletion) in
modification, deletion) in the status of an interface's connections. the status of an interface's connections. This notification is
This notification is implemented via a callback functions defined in implemented via a handle registered via the ULP/IMEP interface.
the MANET routing policy/IMEP interface (more on this later)
3.1.2 Link/Connection Status Sensing Packet Exchange Mechanism 3.4.2 Link/Connection Status Sensing Packet Exchange Mechanism
The IMEP uses a combination of BEACON and HELLO packets (and other The IMEP uses a combination of BEACON and ECHO packets (and other
packets to be described shortly) to ascertain connection (and equivalent packets to be described shortly) to ascertain connection
indirectly link) status. On initialization, an interface under the (and indirectly link) status. On initialization, an interface under
control of IMEP broadcasts (the format of a BEACON packet is speci- the control of IMEP broadcasts a BEACON packet to all adjacencies.
fied in section 4.0) to all adjacencies; i.e. interfaces that are (Note: The format of a BEACON packet is specified in a later section,
only one hop away such as those on the same Ethernet subnet, or those but it essentially consists of an *empty* IMEP message; i.e. an IMEP
within wireless transmission range of the broadcasting interface. message containing only the IMEP message header.). Recall that adja-
(Note: Usage of the term "broadcast" here means to transmit a *sin- cencies are interfaces that are only one hop away such as those on
gle* copy of a packet to *all* interfaces reachable over one hop. As the same Ethernet subnet, or those within wireless transmission range
is the convention with other Internet routing protocols, this is done of the broadcasting interface. (Note: Usage of the term ``broad-
using IP multicast. An IP multicast address "ALL_IMEP_ROUTERS" will cast" here means to transmit a *single* copy of a packet to *all*
be reserved, and all MANET router interfaces will be configured to interfaces reachable over one hop. As is the convention with other
listen for this address.) a BEACON packet The purpose of a BEACON Internet routing protocols, this is done using IP multicast. An IP
packet is to alert any adjacencies of the existence and identity of multicast address ``ALL_IMEP_ROUTERS" will be reserved with IANA, and
the broadcasting interface; an interface's identity is its IP all MANET router interfaces will be configured to listen for this
address. The interface must ensure that a BEACON packet (or other address.) The purpose of a BEACON packet is to alert any adjacencies
"equivalent" packet, more on this later) is transmitted at least once of the existence and identity of the broadcasting interface; an
every BEACON_PERIOD (BP) time units; i.e. no more than BP time units interface's identity is its IP address. The interface must ensure
may pass between subsequent transmissions of a BEACON (or "BEACON- that a BEACON packet (or *any* other packet, since all packets are
``BEACON-equivalent") is transmitted at least once every
BEACON_PERIOD (BP) time units; i.e. no more than BP time units may
pass between subsequent transmissions of a BEACON (or ``BEACON-
equivalent") packet. equivalent") packet.
Reception of a BEACON at an interface implies either reconfirmation Reception of a BEACON at an interface implies either reconfirmation
or creation of "IN" (read "INcoming") status of a connection at that or creation of ``IN" (read ``INcoming") status of a connection at
interface, depending on whether or not the connection already exists, that interface, depending on whether or not the connection already
respectively. Thus, BEACONs serve to tell a receiving interface that exists, respectively. Thus, BEACONs serve to tell a receiving inter-
"someone else is out there." Once present, the status remains for face that ``someone else is out there." Once present, the status
MAX_BEACON_TIME (MBT) time units, at which time it expires (i.e. remains for MAX_BEACON_TIME (MBT) time units, at which time it times
times out) if no subsequent BEACONs have been received; i.e. the link out if no subsequent BEACONs have been received; i.e. the link is
is declared DOWN and is removed from the data structures. Creation declared DOWN and is removed from the data structures. Creation or
or loss of IN status may require notification of the upper level loss of IN status may require notification of an upper level proto-
routing protocol, depending on whether or not the logical link status col, depending on its signalling support mode.
to which this connection is associated has been affected.
HELLO (or "HELLO-equivalent") packets are used to respond to BEACONs. ECHO (or ``ECHO-equivalent") packets are used to respond to BEACONs.
The purpose of a HELLO packet is to let a "BEACONing" node know that The purpose of an ECHO packet is to let a ``BEACONing" router know
someone hears its BEACON. A HELLO packet contains the identity (i.e. that someone hears its BEACON. An ECHO packet contains the identity
IP interface) of the interface broadcasting the HELLO and the iden- (i.e. IP interface address) of the interface broadcasting the ECHO
tity of the BEACONing interface to which it is responding. A HELLO and the identity of the BEACONing interface to which it is respond-
packet is generated immediately in response to a BEACON reception, ing. An ECHO packet is generated immediately in response to an ini-
and is placed in the "Awaiting Broadcast" (AB) buffer (more on the tial BEACON reception. Subsequently, as long as the interface is
functioning of this buffer later). Subsequently, as long as the considered UP (i.e. IN or BI), an ECHO packet must be generated at
interface is considered UP (i.e. IN or BI), a HELLO packet must be least once every BP time units; i.e. no more than BP time units may
generated at least once every BP time units; i.e. no more than BP pass between subsequent generations of an ECHO or ECHO-equivalent
time units may pass between subsequent generations of a HELLO packet. packet.
Reception of a HELLO at an interface implies either reconfirmation or Reception of an ECHO at an interface implies either reconfirmation or
creation of "BIdirectional" status of an connection at that inter- creation of ``BIdirectional" status of an connection at that inter-
face, depending on whether or not the connection already exists, face, depending on whether or not the connection already exists,
respectively. This is because reception of HELLO packet confirms respectively. This is because reception of ECHO packet confirms that
that someone hears this interface (i.e. that is has OUTgoing status), someone hears this interface (i.e. that is has OUTgoing status), and
and simultaneously confirms that it itself can receive them and, simultaneously confirms that it itself can receive them and, hence,
hence, also has INcoming status for that connection. also has INcoming status for that connection.
HELLO packets may be broadcast in one of two "Hello" modes: ECHO packets may be broadcast in accordance with one of two ``signal-
ling" modes, which applies to both ECHO and ACK semantics (more on
ACKs later):
Single Interface (SI): Single Interface (SI):
An interface only sends HELLOs in response to BEACONs it An interface only sends ECHOs in response to BEACONs it
receives. This is the standard mode which permits efficient receives. This is the standard mode which permits efficient
link-layer detection of IN and BI connections. It also permits link-layer detection of BI connections. This mode should be
"network-layer detection" (by a routing protocol) of BIdirec- enabled if the BI-directional connection notification mode is
tional links composed of oppositely-directed, unidirectional enabled.
links on the same or differing routers.
Multiple Interface (MI): Multiple Interface (MI):
An interface sends HELLOs in response to BEACONs it receives, An interface sends ECHOs in response to BEACONs it receives, and
and it also sends HELLOS in response to the BEACONs received by IMEP also sends Indirect ECHOs (IECHO) out *all* other inter-
*all* other interfaces attached to its router. This mode is faces. An IECHO carries the address of the interface being
necessary to permit "link-layer detection" of BIdirectional echo'ed (as does an ECHO) but, additionally, carries the address
links composed of oppositely-directed, unidirectional connec- of the interface on the echoing router that received the
tions between neighboring routers. Note that only by using this transmission being echoed. This mode is necessary to permit
Hello mode can an interface determine that it itself has "OUTgo- ``IMEP-based detection" of BIdirectional links composed of
ing" status without also having "INcoming" and, hence, BIdirec- oppositely-directed, unidirectional connections between neigh-
tional status. boring routers. Note that by using this Echo mode (i.e. via
reception of IECHOS at other interfaces), an interface can be
informed (solely via IMEP) that it has an ``OUTgoing" connection
without also having ``INcoming" status and, hence, a BIdirec-
tional link. This mode should be enabled if the UNI-directional
connection notification mode is enabled.
To make this clear, consider Figure 3. To make this clear, consider Figure 3.
+----------+ +----------+
| Router i | | Router i |
+----------+ +----------+
+--------------+ +--------------+ +--------------+ +--------------+
| Interface f1 | | Interface f2 | | Interface f1 | | Interface f2 |
+--------------+ +--------------+ +--------------+ +--------------+
| IN ^ | IN ^
skipping to change at page 9, line 24 skipping to change at page 13, line 27
| | | |
| | | |
IN V | IN V |
+--------------+ +--------------+ +--------------+ +--------------+
| Adjacency c1 | | Adjacency c2 | | Adjacency c1 | | Adjacency c2 |
+--------------+ +--------------+ +--------------+ +--------------+
+----------+ +----------+
| Router k | | Router k |
+----------+ +----------+
Figure 3: A bidirectional link consisting of two oppositely- Figure 3: A bidirectional link consisting of two oppositely-directed
directed connections. connections.
Assume that SI Hello mode is being used, and the wireless direc- Assume that SI Echo mode is being used, and the wireless directional
tional connectivity is as shown. From router i's perspective, connectivity is as shown. From router i's perspective, it can only
it can only receive over interface f2, and thus classifies con- receive over interface f2, and thus classifies connection (f2,c2) as
nection (f2,c2) as IN. It is unaware that its BEACON packets IN. It is unaware that its BEACON packets being broadcast from
being broadcast from interface f1 are being received at inter- interface f1 are being received at interface c1 on router k. How-
face c1 on router k. However, if MI mode is used, then router k ever, if MI mode is used, then router k will advertise (via IECHO
will advertise the reception of BEACON packers from f1 at c1 transmissions from c2) the reception of BEACON packets from f1 at c1
over connection (f2,c2) thereby informing router i that connec- thereby informing router i that connection (f1,c1) should be classi-
tion (f1,c1) should be classified as OUT. Of course, the fied as OUT. Of course, the reverse but same is true from router k's
reverse but same is true from router kís perspective. perspective.
The additional functionality provided by the MI mode comes at The additional functionality provided by the MI mode comes at the
the cost of broadcasting a HELLO out *every* interface instead cost of broadcasting IECHOs out one or more interfaces in addition to
of only the interface over which the corresponding BEACON was the ECHO sent over the interface over which the corresponding BEACON
received. This creates more HELLO overhead. For a given net- was received. This creates more ECHO overhead. For a given network,
work, this cost must be balanced against the frequency of this cost must be balanced against the frequency of occurrence of the
occurrence of the situation depicted in figure 3. situation depicted in figure 3.
3.2 Control Message Aggregation Additional activity at an ULP (involving communication over multiple
hops) is necessary to detect purely UNIdirectional links (i.e. links
consisting of one or more unidirectional connections) between
adjacent routers.
MANET routing protocols exchange control information in the form of 3.4.3 BEACON and ECHO ``Equivalency"
routing control messages or "objects". To minimize the number of
channel accesses generated by routing control traffic, the IMEP
aggregates and encapsulates these objects into larger "IMEP object
blocks". The objects are treated as "opaque" objects by the IMEP
protocol; i.e. IMEP is not aware of the contents of the objects, only
of the protocol "type" of the object block (necessary for protocol
demultiplexing at a receiver) and the length of each object. These
object blocks are contained in yet larger "IMEP messages" which are
passed to the IP layer for encapsulation and forwarding.
3.3 Broadcast Reliability BEACON and ECHO packets are necessary for ascertaining current con-
nection status. From the perspective of a given router, BEACONs
announce the presence of a broadcasting interface, and ECHOs simul-
taneously announce the presence of an adjacency *and* that the adja-
cency can receive from the broadcasting interface. However, it
should be clear that the same information can be gleaned from other
IMEP packets. Specifically, all transmissions signal the presence of
a broadcasting interface and are, in this sense, ``equivalent" to
BEACON packets. Similarly, ACKnowledgements both announce the pres-
ence of an adjacency and, through the process of acknowledgement,
confirm that the adjacency recently received from the broadcasting
interface. Thus, in this sense, ACKs are equivalent to ECHOs. The
equivalency is depicted in the Figure 6.
IMEP supports reliable and unreliable delivery of opaque protocol BEACON -->
objects, where reliable delivery is also guaranteed to be delivery ALL/OBJ -->
"in order" of transmission. IMEP uses a "point-to-multipoint selec- +----------+ +-------------+ +-------------+
tive repeat" algorithm to guarantee broadcast or multicast reliabil- | Router i |-| Interface f | - - - - | Adjacency c |
ity and ordered delivery. This approach eliminates unnecessary +----------+ +-------------+ +-------------+
retransmissions of the type commonly associated with "go back n" <-- ECHO or IECHOS
algorithms, and is in keeping with the greater IMEP goal of minimiz- <-- ACK or IACKS
ing the number of required channel accesses.
Figure 6: BEACON and ECHO Equivalency
Transmission or reception of a BEACON or ECHO-equivalent packet
affects the link-status sensing timers as would transmission or
reception of a BEACON or ECHO, respectively. Thus, during periods of
heavy data traffic, it is expected that BEACONs and ECHOs will rarely
be transmitted as their respective ``equivalent" packets will serve
their role in link status sensing. During periods of light or no
traffic, BEACONs or ECHOs will be transmitted as necessary to satisfy
the aforementioned timing requirements.
If MI mode is in use, the Indirect ECHOS are being sent out all
interfaces. In a corresponding fashion, Indirect ACKS (IACKS) must
be sent out all interfaces to provided reliability over BIdirection
links consisting of oppositely-direction, UNIdirectional connections.
These IACKS are also ``echo equivalent" and must indicate the address
of the interface they are IACKing, as well as the interface address
on the IACKing router which received the object being indirectly
ACKed.
3.4.4 Connection Failure Detection
Expiration of the MBT timer signals connection failure. Note that
separate timers are used to monitor IN and OUT connection status.
Thus, a connection may lose its OUT status while still retaining IN
status and vice versa. Obviously, a connection satisfying both IN
and OUT timing requirements is marked as BI.
3.5 Neighbor Broadcast Reliability
IMEP supports two broadcast delivery modes:
BROADCAST (IMPLICIT):
Delivery to the current one-hop neighbor set.
MULTICAST (EXPLICIT):
Delivery to a pre-specified subset of the one-hop neighbor set.
A ULP may specify one, some or all current neighbors.
Of course, both are delivered using one-hop scoped, multicast
addressing as is every IMEP message.
IMEP supports two reliability modes:
UNRELIABLE:
Unreliable, unsequenced delivery of either neighbor broadcast or
neighbor multicast data.
RELIABLE:
Reliable, sequenced delivery of either neighbor broadcast or
neighbor multicast data.
Thus, delivery may be implicit or explicit, and reliable or unreli-
able: all four combinations are possible. These modes are used for
delivery of opaque protocol objects, where reliable delivery-- i.e.,
broadcast or multicast --is also guaranteed to be delivery ``in
order" of transmission. (Note: This should not be confused with
transport-layer, reliable multicast across an entire multihop net-
work.)
IMEP uses a ``point-to-multipoint selective repeat" algorithm to
guarantee broadcast or multicast reliability and ordered delivery.
This approach eliminates unnecessary retransmissions of the type com-
monly associated with ``go back n" algorithms, and is in keeping with
the greater IMEP goal of minimizing the number of required channel
accesses.
To support reliability, each object block is given a SEQUENCE number, To support reliability, each object block is given a SEQUENCE number,
and is broadcast with that number and with a set of its intended and is broadcast with that number. To provide in-order delivery, a
receivers referred to as its "response list". When broadcast, a copy connection protocol is utilized to synchronize receivers with the
of the object block and its associated response list (i.e. the set of current broadcast SEQUENCE number. The connection and transmission
neighbors that are required to acknowledge this block) are stored. A protocol is designed so that an explicit receiver list does not have
retransmission timer is set to RETRANS_PERIOD (RP) time units which, to be appended to every reliable object block. Instead, an implicit
upon expiration, will cause the object to be rebroadcast to any list is used by ``coloring" all messages. If a message is received
neighbors which have not acknowledged the object (this causes the with the correct color, then the SEQUENCE number has meaning and its
retransmission timer to be set again to RP). The time the packet was objects can be forwarded up the protocol stack. If the color is
initially broadcast is also stored. If the objectís response list is incorrect, the receiver does not forward its objects up the protocol
not empty (i.e it has not been acknowledged by some adjacencies) stack. The connection protocol reliably transmits the current group
after MAX_RETRANS_TIME (MRT) time units, the connections to those color to all members of the group.
adjacencies are declared DOWN.
When broadcast, a copy of the object block with a response list (i.e.
the set of neighbors that are required to acknowledge this block) is
stored. A retransmission timer is set to RETRANS_PERIOD (RP) time
units which, upon expiration, will cause the object to be rebroadcast
to any neighbors which have not acknowledged the object (this causes
the retransmission timer to be set again to RP). The time the packet
was initially broadcast is also stored. If the object's response
list is not empty (i.e it has not been acknowledged by some adjacen-
cies) after MAX_RETRANS_TIME (MRT) time units, the connections to
those adjacencies are declared DOWN.
Acknowledgements (ACKs) are sent in response to object block recep- Acknowledgements (ACKs) are sent in response to object block recep-
tions when (i) reliable delivery is indicated and (ii) when the tions when (i) reliable delivery is indicated and (ii) when the
receiver is contained in the response list. Once a node has ACKed a receiver is contained in the response list (either implicitly or
given block, it will be removed from the block's response list so explicitly). Once a neighboring router has ACKed a given block, it
that it will not be required to ACK any future retransmissions. will be removed from the block's response list so that it will not be
required to ACK any future retransmissions.
3.4 Network-level Address Resolution 3.5.1 The Reliable Delivery Neighborhood
IMEP puts forth a framework or architecture for MANET router and Each router keeps track of the neighbors that can be reached reliably
interface identification and addressing. IMEP operates simultane- through regular Beacon-Echo exchanges. For discussion purposes, con-
ously on two different topological levels: the "logical network" sider a single router, termed a ``base-router", B and any number of
topology level---which is concerned with interrouter connectivity--- ``neighbor routers", N(i), i=1,2, ..., P, where P is the number of
and the "physical" topology level---which is concerned with interface routers that can currently hear transmissions from B. Each router
connectivity. Router IDs (RID) identify routers in the logical N(i), will respond with an ECHO packet within the time constraints of
topology, and IP addresses identify interfaces in the physical topol- the BEACON-ECHO protocol outlined previously. If B hears an ECHO
ogy. There may be *multiple* IP addresses associated with a given packet from N(i), then N(i) is a candidate member of B's reliable
RID. delivery neighborhood (RDN). For N(i) to become a member of B's
reliable delivery neighborhood (i.e., connected to B), B must broad-
cast a group COLOR with an explicit membership list. This object is
called a NEWCOLOR and must be acknowledged by every router on the
explicit membership list before B considers a reliable delivery
neighborhood to be formed.
The purpose of the Network-level Address Resolution Protocol (NARP) From N(i)'s perspective, the neighborhood rooted at B is has COLOR K.
incorporated within IMEP is to dynamically discover the mapping N(i) is a member of this neighborhood if the NEWCOLOR object expli-
between RIDs and IP addresses when necessary. This is envisioned citly contains N(i) as a member. A reliable delivery neighborhood
typically only to occur when a new connection is discovered, as it is rooted at B with COLOR K and current sequence J is specified in the
necessary to be able to associate an interface (an IP address) with a triple RDN(B,K,J). The COLOR K is updated by B every time a change to
router (an RID). its RDN is discovered (either a new router comes in range or an
existing router moves out of range or becomes hidden). Every router R
in a MANET network will have a single RDN rooted at R. R can be a
member of any number of RDN's that are not rooted at R. Every router
keeps track of its RDN and of the RDN's for which it is a member. If
a router hears a router R1 but itself is not an explicit member of
RDN(R1,K,J), then it marks the current COLOR of RDN(R1,K,J) as color-
less or as RDN(R1,0,J). The format for a NEWCOLOR object is given in
a later section.
+----------+ 3.5.2 Neighborhood definitions
| Router | RID
+----------+
| |
+--------------+ +--------------+
| Interface | | Interface | IP Address
+--------------+ +--------------+
| |
+--------------+ +--------------+
| Phys Device | | Phys Device | MAC Address
+--------------+ +--------------+
Figure 4: RIDs, IP and MAC addresses RDN(B):
Reliable delivery neighborhood rooted at MANET router B.
While it is true that---as currently defined---RIDs are not RDN(B,K):
"addresses" in the strict sense, they do uniquely identify a router Reliable delivery neighborhood rooted at MANET router B, with
for purposes of internal routing computations and somewhat resemble a COLOR K.
logical "router address". Thus, the IP address-to-RID mapping is
similar in spirit to IP address-to-MAC address mapping performed by
the present ARP protocol. Each mapping simply associates an IP
address with another identifier as shown in Figure 4. As with ARP, a
"reverse" mapping is also defined as the Reverse Network-level
Address Resolution Protocol (RNARP). The two mappings are shown in
Figure 5.
ARP: IP --> MAC RARP: MAC --> IP RDN(B,K,J):
Reliable delivery neighborhood rooted at MANET router B, with
COLOR K, and current broadcast sequence number J.
NARP: IP --> RID RNARP: RID --> IP 3.5.3 Reliable, Sequenced Delivery
Figure 5: ARP/RARP and NARP/RNARP Objects passed to IMEP from an ULP may be delivered reliably or
unreliably, and is specified by the ULP. This section addresses
reliable, sequenced delivery of ULP objects by IMEP to all members of
a RDN. Every reliable object in IMEP delivered from B to the
RDN(B,K,J) is colored with COLOR K and sequence number J. A router
N(i) is an intended receiver of the object if its notion of the COLOR
K associated with RDN(B) matches exactly the color contained in the
broadcast object. Therefore, N(i) may deliver a reliable object to
its ULP only if the object from B matches the COLOR and SEQUENCE that
N(i) has recorded for the RDN(B). If an object arrives with the
correct COLOR but the incorrect SEQUENCE number, then N(i) must
determine if the object is a duplicate or simply out of sequence. If
a duplicate, then N(i) discards the object. If out of sequence, then
N(i) retains the object until all earlier objects arrive. If an
object arrives with the incorrect COLOR, then N(i) discards the
object.
When necessary, NARP/RNARP packets are generated, aggregated with From the ULP's perspective, objects are delivered reliably and in
other network control traffic and reliably broadcast within the sequence to *only* those members of the RDN(B) that exists at the
object block of a IMEP message. However, unlike other control time when the object was received by IMEP (Note this may not be the
traffic, the NARP/RNARP objects are not opaque with respect to IMEP time when the object was sent to IMEP from the ULP's perspective, due
as they are generated and consumed by the IMEP protocol. possibly to interprocess communication delay between IMEP and the
local ULP). This is referred to as an (implicit) ``neighbor broad-
cast" object.
3.5 Security Authentication If the ULP requires a object to be delivered to a specific subset of
one-hop neighbors, then it should use ``neighbor multicast" objects
(see below). This latter delivery semantic frees ULPs from having to
decide whether or not a object is valid. Every reliable object passed
to the ULP from IMEP is guaranteed to be intended for the ULP, as
specified by the sender.
It is expected that the IMEP protocol will include hooks for security Reliability is established between *routers*, not interfaces. Thus,
authentication in a fashion similar to that already performed by OSPF the reliability semantics are the same regardless of whether BIdirec-
and other routing protocols. This will include, among others, an tion notification with SI signalling or UNIdirectional notification
authentication type field in the IMEP message header. with MI signalling is in use.
3.6 BEACON and HELLO "Equivalency" 3.5.3.1 Sequence Numbers and Associations using Broadcast Semantics
As stated earlier, BEACON and HELLO packets are necessary for ascer- The coloring of the RDN(B) corresponds to a single sender with a
taining current connection status. From the perspective of a given number of ``associated" receivers. ECHOs from a router can be viewed
router, BEACONs announce the presence of a broadcasting interface, as a association request. If an association is already established
and HELLOs simultaneously announce the presence of an adjacency and from B to N(i), then this request is vacuous. If, however, no associ-
that the adjacency can receive from the broadcasting interface. How- ation from B to N(i) exists, the ECHO then acts like a association
ever, it should be clear that the same information can be gleaned request. A NEWCOLOR object with N(i) on the list completes the asso-
from other IMEP packets. Specifically, OBJect block transmissions ciation from B to N(i) (from N(i)'s perspective) and N(i)'s ack-
(which may contain routing, NARP/RNARP and/or security objects) sig- nowledgement of the NEWCOLOR object completes the association from
nal the presence of a broadcasting interface and are, in this sense, B's perspective.
"equivalent" to BEACON packets. Similarly, ACKnowledgements both
announce the presence of an adjacency and, through the process of
acknowledgement, confirm that the adjacency recently received from
the broadcasting interface. Thus, in this sense, ACKs are equivalent
to HELLOs. The equivalency is depicted in the Figure 6.
BEACON--> The RDN(B) maintains a single sequence number that all members of
OBJ --> RDN(B) must track. NEWCOLOR objects contain not only a new group
+----------+ +-------------+ +-------------+ COLOR, but also the next expected SEQUENCE number. This allows sender
| Router i |-| Interface f | - - - - | Adjacency c | and receivers to synchronize the sequence numbers to provide in-order
+----------+ +-------------+ +-------------+ delivery.
<-- HELLO
<-- ACK
Figure 6: BEACON and HELLO Equivalency There are (subtle) consequences of these semantics.
Transmission or reception of a BEACON or HELLO equivalent packet
affects the link status sensing timers as would transmission or
reception of a BEACON or HELLO, respectively. Thus, during periods
of heavy data, it is expected that BEACONs and HELLOs will rarely be
transmitted as their respective "equivalent" packets will serve their
role in link status sensing. During periods of light or no traffic,
BEACONs or HELLOs will be transmitted as necessary to satisfy the
aforementioned timing requirements.
3.7 Connection Failure Detection 1) An RDN(B) maintains a *single* sequence number for the neigh-
borhood. Hence, every N(i) must acknowledge *every* reliable
object to ensure that all members of RDN(B) maintain the sequence
order. Of course, multiple reliable objects contained in the same
IMEP message are acknowledged simultaneously with a single ACK.
If an object is intended for a single recipient, all must ack-
nowledge (to keep sequence numbers synchronized) and information
specific to this object must further designate the intended
recipient. This is due to the fact that the current scheme is
optimized for implicit neighbor broadcast delivery, not explicit
neighbor multicast.
It should be noted here that there are two events that can signal 2) When RDN(B,K0) is updated to RDN(B,K1) (color changes from K0
connection failure: expiration of the MRT timer or expiration of the to K1), then all reliable objects must first be retired from B's
BPT timer. Thus the CONN_DEAD_TIME (CDT) value---the time at which a retry queue before the NEWCOLOR object can be transmitted.
connection, once UP (i.e. IN, OUT/BI), will be declared DOWN if its
UP status is not confirmed---is CDT = min(MBT,MRT). Note that
separate timers are used to monitor IN and OUT connection status.
Thus, a connection may lose its OUT status while still retaining IN
status and vice versa. Obviously, a connection satisfying both IN
and OUT timing requirements is marked at BI.
4.0 Protocol Message Format 3) The explicit association (via a colored neighborhood) means
that the first time a reliable object is transmitted, an explicit
recipient list can be (and is) omitted. This reduces the size of
objects and allows the receiver to determine if it should forward
the object up the protocol stack based on only the COLOR and
SEQUENCE number of the object. An additional feature of this
association is that if a single receiver fails to acknowledge an
object, an explicit recipient list may be appended to the reliable
object to indicate those routers that should re-ack the object. In
the case of delivery failure, this reduces the number of a media
accesses by requiring only those who have not acknowledged a
object to explicitly respond.
3.6 Multipoint Relaying
IMEP supports Multipoint Relaying (MR)--an optional mode or mechanism
designed to minimize the overhead of packet *flooding* throughout a
MANET by optimizing/reducing the number of duplicate retransmissions.
As control overhead expenditure is required to support MR, it is
recommended that this mode be enabled only when sufficient flooding
traffic exists so that the benefit derived from MR justifies its
cost.
Before describing MR in detail, we first give some terminology
specific to MR:
MultiPoint Relay (MPR):
A router which is selected by a one-hop neighbor to forward or
retransmit that neighbor's packets.
Multipoint Relay Selector (MPRS):
Each MPR has one or more neighbors which have selected it as a
MPR--each such neighbor is referred to as a ``Multipoint Relay
Selector". Each MPR keeps a table of RIDs identifying the
members of its MRS set so that it knows which packets to
retransmit via MR.
Source of the Multipoint Relay (SMR):
Each router which originally transmits a data packet via MR is
known as the ``Source of the Multipoint Relay" for that packet,
and is so identified in the packet.
Every router has a set of nodes one hop away N1 (its one-hop neighbor
set) and a set of nodes two hops away N2 (its two-hop neighbor set).
The objective of a router participating in MR is to select a minimal
subset M of MPRs from N1 so that their retransmissions cover N2.
Multipoint relaying proceeds as follows:
Each MR router periodically broadcasts a Multipoint Relaying Adver-
tisement (MRA) packet once every Multipoint Relaying Period (MRP)
containing its RID, the RIDs of all its one-hop neighbors in N1, and
the subset M of these neighbors it has selected as its MPRs. This is
an implicit broadcast to the current one-hop neighbor set N1 which
may occur reliably or unreliably as desired. It can easily be seen
that with each MR router transmitting the identity of its set N1,
every MR router learns its set N2.
The algorithm for selection of the set M is not prescribed. It is
required only that the set M be chosen so as to cover N2. The aim is
to select the ``minimum" number of MPRs to do so.
One possible algorithm is:
1. Start with an empty set M.
2. First select as MPRs those routers from F1 which
provide the ``only path" to reach some routers in N2.
3. While there still exist some routers in N2 that are not
covered by M:
3.1 For each router in N1, calculate the number of routers
in N2 reachable through this router which are not
yet covered by M;
3.2 Select as a MPR that router which reaches the
maximum number of uncovered routers in R2.
A ``flood termination" mechanism is also required and is implemented
simply by including a SMR field and a sequence number in every MR
object. This enables routers to maintain a list of recently-received
MR objects. MR objects are passed to the appropriate ULP the *first*
time they are recieved at a router, and are silently discarded
thereafter.
3.7 Authentication
Authentication is optional. If authentication is enabled, MANET
routers have the choice of implementing multiple authentication
options ranging from simple to complex. IMEP messages between MANET
routers are authenticated with the IMEP Authentication object, which
contains the option is use. This object immediately follows all non-
authentication objects.
4. IMEP Message Format
The following describes the message format of the proposed protocol. The following describes the message format of the proposed protocol.
An IMEP message format consists of several fixed, mandatory fields An IMEP message format consists of several fixed, mandatory fields
followed by a self-formatting byte stream. The stream is aligned followed by a self-formatting byte stream. The stream is aligned
along "byte" boundaries---not 32-bit word boundaries---to save along ``byte" boundaries---not 32-bit word boundaries---to
transmission overhead at the cost of extra processing at a router. save transmission overhead at the cost of extra processing at a
An IMEP message typically contains at least one of several optional router. An IMEP message typically contains at least one of several
blocks. A message containing no blocks is a BEACON message. optional object blocks. A message containing no objects is a BEACON
message. The following ``grammar" describes the syntax of an IMEP
message.
<IMEP message> ::= <IMEP_VERSION> <BLOCK_FLAGS> <IMEP_LENGTH> <IMEP message> : <IMEP_MSGHDR> <IMEP_OBJECTLIST>
[Ack Block]
[Hello Block]
[Object Block]
The fixed field formats are: <IMEP_MSGHDR> : <IMEP_VERSION> <COLOR> <MESSAGE_LENGTH> <RID>
<IMEP_OBJECTLIST> : <IMEP_OBJECTLIST> <IMEP_OBJECT>
| <IMEP_OBJECT>
<IMEP_OBJECT> : <OBJECT_HDR> <RELIABLE_OBJECT>
| <OBJECT_HDR> <UNRELIABLE_OBJECT>
<OBJECT_HDR> : <OBJTYPE> <SEQUENCE> <OBJECT_LENGTH>
<RELIABLE_OBJECT> : <DATA>
| <DATA> <ACK List>
<UNRELIABLE_OBJECT> : <DATA>
<DATA> : <ECHO>
| <BCAST>
| <MCAST> <DELIVERY_LIST>
| <MR>
| <ACK>
| <NEWCOLOR>
| <MRA>
| <AUTH>
<BCAST> : <PROTOCOL> <OBJLEN> <OBJDATA>
<MCAST> : <PROTOCOL> <OBJLEN> <DELIVERY_LIST_LEN>
<OBJDATA>
<MR> : <SMRRID> <MRSEQUENCE> <PROTOCOL>
<OBJLEN> <OBJDATA>
4.1 <IMEP_MSGHDR>
Every IMEP message contains header information. A message with
no objects is termed a BEACON message. Included in
every header is the <RID> of the sending IP interface.
<IMEP_MSGHDR> : <IMEP_VERSION> <COLOR> <MESSAGE_LENGTH> <RID>
31 24 23 16 15 8 7 0 31 24 23 16 15 8 7 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1 | (a) | (b) | (c) | Opt. blocks... | (a) | (b) | (c) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
(a) IMEP_VERSION (4-bit unsigned integer): 31 24 23 16 15 8 7 0
This field specifies the protocol version number, which may +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
range from 0-15. The initial protocol version number is zero. | (d) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
(b) BLOCK_FLAGS (4-bit bitmask): (a) <IMEP_VERSION> Protocol version (8 bits)
This field contains single-bit flags, each of which specifies
the presence (flag = 1) or absence (flag = 0) of a block. All
bits set equal to zero indicates that this is a BEACON packet--a
packet intended only to announce the existence of this interface
(whose IP address is contained in the IP header) to any poten-
tial adjacencies.
bit 27: Ack block flag (b) <COLOR> Group color (8 bits)
== 0 - colorless
otherwise - reliability sequence numbers are prefixed by
this color
bit 26: Hello block flag (c) <MESSAGE_LENGTH> Total message length (in bytes) of this
IMEP packet (16 bits) which lies in the following range:
bit 25: Object block flag 3 < IMEP_LENGTH <= MAX_IMEP_LENGTH <= 65535
bit 24: unused (d) <RID> Router Id associated with the sender's IP interface.
(c) IMEP_LENGTH (16-bit unsigned integer): 4.1.1 <OBJECT_HDR>
This field specifies the total length of an IMEP message
(measured in bytes) which must lie in the following range:
3 < IMEP_LENGTH <= MAX_IMEP_LENGTH <= 65535 31 24 23 16 15 8 7 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (a) | (b) | (c) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The ACK Block format is: (a) <OBJTYPE> object type (8 bits)
0 - reserved
1-127 - object does not carry reliability information,
seq# ignored
128-255 - object must be delivered reliably, in order,
according to color and seq #
<Ack Block> ::= <NUM_ACKS> <Ack List> (b) <SEQUENCE> Sequence number for this object (8 bits)
<Ack List> ::= <ACK> | (c) <OBJECT_LENGTH> Length (in bytes) of this object
<Ack List> <ACK> (16 bits). <OBJECT_LENGTH> does not include the length
of the SUBMESSAGE HEADER, but does include the length of
the explicit ack list, if any.
NUM_ACKS (8-bit unsigned integer): (<OBJECT_LENGTH> <= <MESSAGE_LENGTH> - 4)
This field indicates the length of the Ack List which may range
from 0-255. 4.1.2 <OBJTYPE>
The following object types are defined for this version of IMEP.
Unreliable Object Types:
1 - SM_ECHO : <ECHO> object
2 - SM_ACK : <ACK> object
3 - SM_UBCAST : <BCAST> object, delivered unreliably
4 - SM_UMCAST : <MCAST> object, delivered unreliably
5 - SM_UMRA : <MRA> object, delivered unreliably
6 - SM_UMR : <MR> object, delivered unreliably
7 - SM_IECHO : <IECHO> object
8 - SM_IACK : <IACK> object
[65,73] : (future) IPV6 Versions of the above
objects
Reliable Object Types:
128 - SM_NEWCOLOR : <NEWCOLOR> object
129 - SM_BCAST : <BCAST> object delivered reliably
130 - SM_MCAST : <MCAST> object delivered reliably
131 - SM_AUTH : <AUTH> object delivered reliably
132 - SM_MRA : <MRA> object, delivered reliably
133 - SM_MR : <MR> object delivered reliably
[192,197] : (future) IPV6 Versions of the above
objects
4.2 IMEP objects
This section describes the ordering of IMEP objects a MANET router
may include in an IMEP message. This following ordering MUST be fol-
lowed:
a) The fixed-length IMEP message header, followed by
b) If present, any non-authentication objects, followed by
c) The IMEP Authentication object.
The authentication in the IMEP messages MUST be checked. The receiv-
ing router MUST check for the presence of a valid IMEP Authentication
object, and perform the indicated authentication. Exactly one IMEP
Authentication object MUST be present in the IMEP message, and the
home agent MUST check the Authenticator value in the object. If no
IMEP Authentication object is found, or if more than one IMEP Authen-
tication object is found, or if the Authenticator is invalid, the
receiving router MUST discard the IMEP message and SHOULD log the
error as a security exception.
4.2.1 <ECHO>
The <ECHO> block may contain any number (subject to message length
restrictions) of Addresses
<ECHO> : <ECHO_LIST>
<ECHO_LIST> : <ECHO_LIST> <ECHO_ENTRY>
| <ECHO_ENTRY>
<ECHO_ENTRY> : <ECHO_IF>
A <ECHO_ENTRY> is a 32-bit address that contains the interface being
echo'ed.
The ACK format is:
31 24 23 16 15 8 7 0 31 24 23 16 15 8 7 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1 ...self-formatting bytestream contents | (a) | | (a) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2 | (b) Ack'ed IP Interface Address |
(a) <ECHO_IF> IPV4 of interface that is being echo'ed (4 bytes)
The number of addresses in this list are inferred from the
<OBJECT_LENGTH> field.
4.2.2 <ACK>
The ACK Block format is:
<ACK> : <Ack List>
<Ack List> : <Ack List> <Ack Entry>
| <Ack Entry>
<Ack Entry> : <ACK_IPADDR> <ACK_COLOR> <ACK_SEQUENCE>
<Ack Entry> is defined as follows: This block may contain any number
(up to total length restrictions) of acknowledgements interfaces and
sequence #'s
numAcks = <OBJECT_LENGTH>/6
ACK Block 6-byte byte block:
31 24 23 16 15 8 7 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (a) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
(a) SEQUENCE (8-bit unsigned integer): 15 8 7 0
Indicates the sequence number of the protocol object block +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
being ack'ed, which may range from 0-255. | (b) | (c) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
(b) ACKIPADDR (32-bit unsigned integer): (a) <ACK_IPADDR> IPV4 address of interface being ACKed (4 bytes)
IP interface address of the interface which originally sent (b) <ACK_COLOR> Group Color (8 bits)
the protocol object block that is being acknowledged. (c) <ACK_SEQUENCE> object sequence# (8 bits)
The Hello Block format is: 4.2.3 <IECHO>
<Hello Block> ::= <NUM_HELLOS> <Hello List> The <IECHO> block may contain any number (subject to message length
restrictions) of <IECHO_ENTRY>s.
<Hello List> ::= <HELLO> | <IECHO> : <IECHO_LIST>
<Hello List> <HELLO>
NUM_HELLOS (8-bit unsigned integer): <IECHO_LIST> : <IECHO_LIST> <IECHO_ENTRY>
This field indicates the length of the Hello List which may | <IECHO_ENTRY>
range from 0-255.
HELLO (32-bit unsigned integer): <IECHO_ENTRY> : <ECHO_IF> <RCV_IF>
This field contains the IPv4 address of the interface being A <IECHO_ENTRY> consists of two 32-bit addresses that contain the
"hello'ed". interface being echo'ed by the router and the interface which
received the BEACON-equivalent, for which this is an *indirect* echo.
The Object Block format consists of a set of fixed fields followed by 31 24 23 16 15 8 7 0
an Object List and an optional Response List: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (a) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
<Object Block> ::= <SEQUENCE> <PROTOCOL_TYPE> 31 24 23 16 15 8 7 0
<NUM_OBJECTS> <NUM_RESPONSES> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
<Object List> [ <Response List> ] | (b) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
<Object List> ::= <OBJECT> | (a) <ECHO_IF> IPV4 of interface that is being echo'ed (4 bytes)
<Object List> <OBJECT>
<OBJECT> ::= <LENGTH_FLAG> <OBJECT_LENGTH> <OBJECT_DATA> (b) <RCV_IF> IPV4 of interface of the receiving interface (4 bytes)
<Response List> ::= <RESPONSE> | The number of entries in this list are inferred from the
<Response List> <RESPONSE> <OBJECT_LENGTH> field.
The fixed fields format is: 4.2.4 <IACK>
The <IACK> Block format is:
<IACK> : <IACK_LIST>
<IACK_LIST> : <IACK_LIST> <IACK_ENTRY>
| <IACK_ENTRY>
<IACK_ENTRY> : <ACK_IPADDR> <RCV_IPADDR> <ACK_COLOR> <ACK_SEQUENCE>
<IACK_ENTRY> is defined as follows: This block may contain any number
(up to total length restrictions) of indirect acknowledgements.
numIAcks = <OBJECT_LENGTH>/10
IACK Block 10-byte byte block:
31 24 23 16 15 8 7 0 31 24 23 16 15 8 7 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1 | (a) | (b) | (c) | (d) | Object List... | (a) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
(a) SEQUENCE (8-bit unsigned integer): 31 24 23 16 15 8 7 0
A sequence counter uniquely indicating the Object Block ID +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
within a sender's transmission queue, ranging from 0-255. This | (b) |
value may rollover, but for the envisioned applications, the 8- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
bit value should be large enough so that no two Object Blocks in
the retransmission queue ever have the same SEQUENCE number.
(b) PROTOCOL_TYPE (4-bit unsigned integer): 15 8 7 0
This field indicates the protocol responsible for the opaque +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
objects in the object block--necessary for demultiplexing the | (c) | (d) |
Object Block at a receiver. The field may range from 0-15. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
value 0: reserved (a) <ACK_IPADDR> IPV4 address of interface being IACKed (4 bytes)
(b) <RCV_IPADDR> IPV4 address of receiving interface (4 bytes)
(c) <ACK_COLOR> Group Color (8 bits)
(d) <ACK_SEQUENCE> object sequence# (8 bits)
value 1: NARP/RNARP 4.2.5 <NEWCOLOR>
value 2: TORA <NEWCOLOR> : <NEW_COLOR> <NEW_SEQUENCE>
values 3-15: unassigned This contains the information about a new COLOR and SEQUENCE for a
(c) NUM_OBJECTS (7-bit unsigned integer): multicast group. The membership list is done as an explicit
This field indicates the length (i.e. number of objects) of the <ACK_LIST> and is not handled here.
Object List contained in the Object Block, which may range from
0-127.
(d) NUM_RESPONSES (5-bit unsigned integer): numMembers = (<OBJECT_LENGTH> - 2)/4
This field indicates the length (i.e. number of responses) of
the Response List contained in the Object Block, which may range
from 0-31. The value 0 indicates unreliable delivery is desired,
and that no interfaces need respond. The value 31 indicates
BROADCAST, and that ALL receiving interfaces should respond. In
both cases, the Response List is omitted.
The OBJECT format is: 15 8 7 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (a) | (b) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
(a) <NEW_COLOR> New group color (8 bits)
(b) <NEW_SEQUENCE> Next valid sequence# (8 bits)
4.2.6 <MRA>
The MRA Block format is:
<MRA> : <MRSRID> <NUM_NBRS> <NUM_MPRFLAGWORDS>
<NBR List> <MPRFLAGWORDS List>
<NBR List> : <NBR List> <NBR Entry>
| <NBR Entry>
<MPRFLAGWORDS List> : <MPRFLAGWORDS List> <MPRFLAGWORD>
| <MPRFLAGWORD>
<MRA> is defined as follows: This block contains the RID of the
advertising MRS, followed by a counter indicating the number of
neighbors and a counter indicating the number of words required to
hold the MPR flags indicating which of those neighbors are MPRs. The
MRA may contain any number (up to total length restrictions) of one-
hop neighbor RIDs, and associated flags specifying which of these
neighbors have been selected as MPRs.
31 24 23 16 15 8 7 0 31 24 23 16 15 8 7 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1 |0|OBJECT_LENGTH| OBJECT_DATA... | (a) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
31 24 23 16 15 8 7 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (b) | (c) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
or (a) <MRSRID> Router ID of advertising MRS (4 bytes)
(b) <NUM_NBRS> Number of one-hop neighbors (16 bits)
(c) <NUM_MPRFLAGWORDS> Number of 32-bit words required for
MPRFLAGS (16 bits)
NUM_MPRFLAGWORDS = (NUM_NBRS+31)/32
31 24 23 16 15 8 7 0 31 24 23 16 15 8 7 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1 |1| OBJECT_LENGTH | OBJECT_DATA... | (d) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
LENGTH_FLAG (1-bit field, bit 31 in format figures): (d) <NBR Entry> Neighbor Router ID (4 bytes)
One entry per neighbor.
0: indicates 7-bit OBJECT_LENGTH 31 24 23 16 15 8 7 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (e) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1: indicates 15-bit OBJECT_LENGTH (e) <MPRFLAGWORD> 32-bit word containing 32 1-bit MPR flags
One word required for 32 neighbors.
The i-th bit in the j-th word indicates the MPR status
of the n-th (n = j*32 + i) neighbor in the neighbor list
where 1 indicates the neighbor is a MPR, and 0 indicates
otherwise.
OBJECT_LENGTH (7 or 15-bit unsigned integer): 4.2.7 <BCAST>
May range from 0-127 or 0-32767 as required indicating the
length of the OBJECT_DATA in bytes.
OBJECT_DATA: A broadcast object block is used for delivering encapsulated data to
Opaque bytestream of data of length OBJECT_LENGTH. an upper-layer protocol (ULP). This block will be received and passed
to the appropriate ULP by all receivers. If the <BCAST> is sent
reliably, then only those routers with a matching color may forward
the message to the appropriate ULP. Each object block may be
independently- sequenced by virtue of its object header. However, all
blocks with reliability share the same group color.
NARP/RNARP Packet Format (> 10 bytes): <BCAST> : <PROTOCOL> <OBJLEN> <OBJDATA>
23 16 15 8 7 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (a) | (b) | (c) ....
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
(a) <PROTOCOL> protocol type (8 bits)
0 - reserved
1 - TORA
2 - AODV
3-255 - unassigned
(b) <OBJLEN> block length (in bytes) (16 bits)
(c) <OBJDATA> This is <OBJLEN> bytes of data encapsulated by IMEP
<BCAST> blocks are delivered reliably, and can therefore have an
explicit acknowledgement list. The <OBJLEN> in (b) can be subtracted
from the <OBJECT_LENGTH> to determine the number of explicit
addresses that should generate acknowledgments.
numExplicitAcks = (<OBJECT_LENGTH> - (<OBJLEN> + 3))/4
4.2.8 <MCAST>
A multicast (or explicit) object block is very similar to a broadcast
object in that it is also used for delivering encapsulated data to an
upper-layer protocol (ULP). The difference is that the <MCAST>
contains an *explicit* delivery list. This implies that the object
data block can be passed to the appropriate ULP only by receivers
that are members of the <DELIVERY_LIST>. If the <MCAST> is sent
reliably, then only those routers with a matching color may forward
the message to the appropriate ULP. Each object block may be
independently-sequenced by virtue of its object header. However, all
blocks with reliability share the same group color. It should be
noted that if this block is sent with reliability, then all
receivers, not just those on the <DELIVERY_LIST>, must ACKnowledge
receipt of the message.
<MCAST> : <PROTOCOL> <OBJLEN> <DELIVERY_LIST_LEN> <OBJDATA>
23 16 15 8 7 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (a) | (b) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
15 8 7 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (c) | (d) ....
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
(a) <PROTOCOL> protocol type (8 bits)
0 - reserved
1 - TORA
2 - AODV
3 - DSR
4 - ZRP
5-255 - unassigned
(b) <OBJLEN> block length (in bytes) (16 bits)
(c) <DELIVERY_LIST_LEN> - Length of the explicit delivery list
(in bytes). (16 bits)
(d) <OBJDATA> This is <OBJLEN> bytes of data encapsulated by IMEP
<MCAST> blocks may be delivered reliably, and can therefore have an
explicit acknowledgement list. The <OBJLEN> in (b) and the
<DELIVERY_LIST_LEN> in (c) can be subtracted from the from the
<OBJECT_LENGTH> to determine the number of explicit addresses that
should generate acknowledgments.
numExplicitAcks = (<OBJECT_LENGTH> - (<OBJLEN> + <DELIVERY_LIST_LEN>
+ 3))/4
4.2.9 <MR>
A multipoint relaying object block is also similar to a broadcast
object in that it is also used for delivering encapsulated data to an
upper-layer protocol (ULP). The difference is that the <MR> contains
an implicit delivery list as determined by the MR algorithm. The
object data block is only passed to the appropriate ULP the *first*
time it is received at a router--any subsequently received copies are
silently discarded. Routers maintain a list of recently-received <MR>
blocks indexed by SMR and MRSEQUENCE to determine whether a block was
previously received.
If the <MR> is sent reliably, then only those routers with a matching
color may forward the object to the appropriate ULP. Each object
block may be independently-sequenced by virtue of its object header.
However, all blocks with reliability share the same group color. It
should be noted that if this block is sent with reliability, then all
receivers, not just the MPRs, must ACKnowledge receipt of the mes-
sage.
<MR> : <SMRRID> <MRSEQUENCE> <OBJLEN> <OBJDATA>
31 24 23 16 15 8 7 0 31 24 23 16 15 8 7 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1 ...self-formatting bytestream | (a) | (b) | (c) | (d) | | (a) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2 | (e) Sender IP Interface Address |
31 24 23 16 15 8 7 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
3 | (f) Target IP Interface Address | | (b) | (c) | (d) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (g) Sender Router Identifier...
31 24 23 16 15 8 7 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...(h) Target Router Identifier... | (e)....
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Both NARP and RNARP packets share the same format which is similar (a) <SMRRID> protocol type (32 bits)
but not identical to traditional link-layer ARP/RARP packets: Router ID of Source of the Multipoint Relay packet.
(b) VERSION (4-bit unsigned integer): (b) <MRSEQUENCE> Multipoint Relay packet sequence# (8 bits)
This field specifies the version number of the NARP/RNARP
protocol. The current version maps 32-bit IPv4 addresses. A
future version would be required to map 128-bit IPv6 addresses.
0 (IPv4) (c) <PROTOCOL> protocol type (8 bits)
0 - reserved
1 - TORA
2 - AODV
3 - DSR
4 - ZRP
5-255 - unassigned
1 (IPv6) (d) <OBJLEN> block length (in bytes) (16 bits)
2-15 (unused) (e) <OBJDATA> This is <OBJLEN> bytes of data encapsulated by IMEP
(b) PROTOCOL_TYPE (8-bit unsigned integer): 4.2.10 <ACK List>, <DELIVERY_LIST>
This field specifies the network-layer routing protocol type
being mapped.
(c) PROTOCOL_LENGTH (4-bit unsigned integer): Lists are arrays of IPV4 addresses. Each entry is a 32-bit address in
This field specifies length of the protocol Router IDentifier network byte order. The length of the list is either stored as part
(RID) in bytes. of the object information (see <DELIVERY_LIST_LEN>) or inferred from
other available lengths (see <OBJECT_LENGTH> and <OBJLEN>).
(d) FRAME_TYPE (4-bit unsigned integer): 4.2.11 <AUTH> (The IMEP Authentication object)
Indicates whether packet is a NARP or RNARP, and whether it is a
request or reply.
0x00 (NARP Request) The IMEP Authentication object is used to authenticate all IMEP
objects. The types of authentication to be supported will be speci-
fied in a proposed MANET Authentication Architecture under develop-
ment.
0x01 (NARP Reply) 4.3 ULP/IMEP Interface
0x02 (RNARP Request) Other than registration, IMEP interacts with ULPs in several funda-
0x03 (RNARP Reply) mental ways. Here this interaction is specified in a format which
loosely follows the Object Management Group's (OMG) Interface Defini-
tion Language (IDL).
(e) SENDER_INTERFACE_ADDR (32-bit unsigned integer): 4.3.1 Registration
IP interface address of the sender of the NARP/RNARP message.
(f) TARGET_INTERFACE_ADDR (32-bit unsigned integer): ULPs must register with IMEP prior to use. Registration consists
IP interface address of the target of the NARP/RNARP message. of calling the following register function.
(g) SENDER_ROUTER_ADDR (length specfied in (c): typedef enum SignallingSupport { CONN, LINK, DISABLED };
Router identifier of the sender of the NARP/RNARP message.
(h) TARGET_ROUTER_ADDR (length specfied in (c): void register (in <PROTOCOL> type,
Router identifier of the target of the NARP/RNARP message. // indicates Protocol type of data object
// if not valid, an InvalidProtocolType exception
// is thrown.
in any ULPhandle,
// *implementation-dependent*
// a handle is passed to IMEP depending on the
// implementation of the ULP/IMEP system that allows
// IMEP to pass signals to the ULP.
// if not valid (and this is detectable by IMEP),
// an InvalidULPhandle exception is thrown.
in <OBJLEN> epitaphLength,
// indicates length of the epitaph object;
// if length = 0, this indicates no epitaph message and
// the OBJDATA field is ignored.
// if length > MAX_EPITAPH_LENGTH, then
// an InvalidByteLength exception is thrown
in <OBJDATA> epitaph,
// opaque epitaph data object
in SignallingSupport mode)
// indicates IMEP Signalling Support mode
// if incorrect, an InvalidSignallingSupport exception
// is thrown
raises (InvalidProtocolType,
InvalidULPhandle,
InvalidByteLength,
InvalidSignallingSupport);
5. Summary 4.3.2 Encapsulation
The preceding gives only a high-level protocol description, specify- IMEP principally aggregates and encapsulates ULP objects into longer
ing what is to be exchanged and, generally, why. Details on how the IMEP messages. From a ULP's perspective, these may be delivered
protocol is to be implemented will be given in a subsequent version reliably or unreliably, and either implicitly broadcast to the
of this draft. entire one-hop neighbor set, or explicitly multicast to a one-hop
neighbor subset. Thus, an object being given to IMEP for transmission
must come with this additional information. The following
specifies the operation ``encapsulate".
6. References typedef enum Boolean { TRUE, FALSE };
typedef enum ForwardingMode { BCAST, MCAST, MR };
[1] C. Perkins, "Mobile Ad Hoc Networking Terminology," draft-ietf- void encapsulate (in <PROTOCOL> type,
manet-term-00.txt, October 1997. // indicates Protocol type of data object
// if not valid, an InvalidProtocolType exception
// is thrown.
in <OBJLEN> length,
// indicates length of data object;
// if length > MAX_IMEP_LENGTH, then
// an InvalidByteLength exception is thrown
in <OBJDATA> data,
// data object to be transmitted
in ForwardingMode mode,
// indicates IMEP forwarding mode
// if incorrect, an InvalidForwardingMode exception
// is thrown
in <DELIVERY_LIST> list,
// List of IPv4 addresses to which object
// should be explicitly delivered via MCAST.
// If one or more addresses are incorrect,
// an InvalidInterface exception is thrown
in Boolean reliability)
// indicates whether reliable delivery is desired
raises (InvalidProtocolType,
InvalidByteLength,
InvalidForwardingMode,
InvalidInterface);
5. Security Considerations
The MANET computing environment is very different from the ordinary
computing environment. In many cases, mobile computers will be con-
nected to the network via wireless links. Such links are particu-
larly vulnerable to passive eavesdropping, active replay attacks, and
other active attacks. Among its many uses, the networking protocol
described in this document enables inter-router communication for
purposes of network control. This control function could be a
significant vulnerability if IMEP messages are not authenticated.
Authors' Addresses: Authors' Addresses:
M. Scott Corson M. Scott Corson
Institute for Systems Research Institute for Systems Research
A.V. Williams Building (115) A.V. Williams Building (115)
University of Maryland University of Maryland
College Park, MD 20742 College Park, MD 20742, USA
(301) 405-6630 (301) 405-6630
corson@isr.umd.edu corson@isr.umd.edu
S. Papademetriou
Institute for Systems Research
A.V. Williams Building (115)
University of Maryland
College Park, MD 20742, USA
(301) 405-7933
spyro@isr.umd.edu
Philip Papadopoulos
Computer Science and Mathematics Division
Oak Ridge National Laboratory
Oak Ridge, TN 37831-6367, USA
(423) 241-3972
papadopoulpm@ornl.gov
Vincent Park Vincent Park
Information Technology Division Information Technology Division
Code 5540 Code 5540
Naval Research Laboratory Naval Research Laboratory
Washington, DC 20375 Washington, DC 20375, USA
(202) 767-5098 (202) 767-5098
vpark@itd.nrl.navy.mil vpark@itd.nrl.navy.mil
Amir Qayyum
INRIA
Sophia-Antipolis, France
Amir.Qayyum@inria.fr
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/