idnits 2.17.1 draft-ietf-manet-imep-spec-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-03-29) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. ** The document is more than 15 pages and seems to lack a Table of Contents. == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** There are 7 instances of too long lines in the document, the longest one being 4 characters in excess of 72. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 1067: '.... This following ordering MUST be fol-...' RFC 2119 keyword, line 1076: '...he IMEP messages MUST be checked. The...' RFC 2119 keyword, line 1077: '... ing router MUST check for the prese...' RFC 2119 keyword, line 1079: '...ntication object MUST be present in th...' RFC 2119 keyword, line 1080: '... home agent MUST check the Authentic...' (1 more instance...) Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 438 has weird spacing: '...nnected to a...' == Line 577 has weird spacing: '... of two oppos...' == Line 938 has weird spacing: '...several fixed...' == Line 939 has weird spacing: '...ollowed by a...' == Line 940 has weird spacing: '... 32-bit word ...' == (35 more instances...) -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (August 7, 1999) is 9001 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? '65' on line 1050 looks like a reference -- Missing reference section? '73' on line 1050 looks like a reference -- Missing reference section? '192' on line 1061 looks like a reference -- Missing reference section? '197' on line 1061 looks like a reference Summary: 10 errors (**), 0 flaws (~~), 7 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Draft M. S. Corson, UMD 3 Expiration: February 7, 1999 S. Papademetriou, UMD 4 P. Papadopoulos, ORNL 5 V. Park, NRL 6 A. Qayyum, INRIA 8 August 7, 1999 10 An Internet MANET Encapsulation Protocol (IMEP) Specification 11 draft-ietf-manet-imep-spec-01.txt 13 Status of this Memo 15 This document is an Internet-Draft. Internet-Drafts are working 16 documents of the Internet Engineering Task Force (IETF), its areas, 17 and its working groups. Note that other groups may also distribute 18 working documents as Internet-Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six months 21 and may be updated, replaced, or obsoleted by other documents at any 22 time. It is inappropriate to use Internet-Drafts as reference 23 material or to cite them other than as ``work in progress." 25 To view the entire list of current Internet-Drafts, please check the 26 ``1id-abstracts.txt" listing contained in the Internet-Drafts Shadow 27 Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe), 28 munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or 29 ftp.isi.edu (US West Coast). 31 Distribution of this memo is unlimited. 33 Abstract 35 This memo describes a multipurpose network-layer protocol---named the 36 Internet MANET Encapsulation Protocol (IMEP)---designed to support 37 the operation of many routing algorithms, network control protocols 38 or other Upper Layer Protocols (ULP) (where ``upper" denotes *any* 39 layer above IMEP) intended for use in Mobile Ad hoc Networks (MANET). 40 The protocol incorporates mechanisms for supporting link status and 41 neighbor connectivity sensing, control packet aggregation and 42 encapsulation, one-hop neighbor broadcast (or multicast) reliability, 43 multipoint relaying, network-layer address resolution and provides 44 hooks for interrouter authentication procedures. Indirectly, the 45 IMEP also puts forth a framework for MANET router and interface 46 identification and addressing. 48 1. Introduction 49 The primary purpose of the Internet MANET Encapsulation Protocol 50 (IMEP) is to improve overall network performance by reducing the 51 *number* of network control packet broadcasts through encapsulation 52 and aggregation of multiple MANET control packets (e.g. routing 53 protocol packets, acknowledgements, link status sensing packets, 54 ``network-level" address resolution, etc.) into larger IMEP messages. 55 Usage of the IMEP is desirable because per-message, multiple access 56 delay in contention-based schemes such as CSMA/CA, IEEE 802.11, FAMA 57 etc. is significant, and thus favors the use of fewer, larger 58 messages. It also may be useful in reservation-based, time-slotted 59 access schemes where smaller packets must be aggregated into 60 appropriately-sized IP packets for transmission in a given time slot. 61 Upper Layer Protocols (ULP) *other than routing* may make use of this 62 encapsulation functionality for the same purpose. 64 Its secondary purpose concerns the commonality of certain 65 functionality in many network-level control algorithms. Many 66 algorithms intended for use in a MANET will require common 67 functionality such as link status sensing, security authentication 68 with adjacent routers, one-hop neighbor broadcast (or multicast) 69 reliability of control packets, etc.. This common functionality can 70 be extracted from these individual protocols and put into a unified, 71 generic protocol useful to all. MANET control algorithms would also 72 benefit from a common approach to router and interface identification 73 and addressing, and this protocol supports a framework for unifying 74 the protocols under a common architecture. 76 The IMEP will run at the network layer (see Figure 1), and will be an 77 adjunct to whichever network protocol is using it. ULP packets will 78 be encapsulated in IMEP messages, which will be further encapsulated 79 into IP packets. 81 +------+ +-----+ +-----+ +-----+ 82 |Telnet| | FTP | | TFTP| ... | ... | 83 +------+ +-----+ +-----+ +-----+ +---------+ +-----+ 84 | | | | | Routing | | ULP | 85 +-----+ +-----+ +-----+ +---------+ +-----+ 86 | TCP | | UDP | ... | ... | | / 87 +-----+ +-----+ +-----+ +---------+ 88 | | | <----- | IMEP | 89 +---------------------------------+ +---------+ 90 | Internet Protocol & ICMP & IGMP | | 91 +---------------------------------+ +---------+ 92 | | IP | 93 +---------------------------+ +---------+ 94 | Local Network Protocol | 95 +---------------------------+ 97 Protocol Relationships Encapsulation 99 Figure 1 101 2.0 Terminology 103 This section provides definitions for the terminology used throughout 104 this document. Many of these definitions may be replaced by or 105 merged with those of the MANET working group's terminology draft now 106 under development. 108 MANET router or router: 109 A device---identified by a ``unique Router ID" (RID)---that exe- 110 cutes a MANET routing protocol and, under the direction of 111 which, forwards IP packets. It may have multiple interfaces, 112 each identified by an IP address. Associated with each inter- 113 face is a physical-layer communication device. These devices 114 may employ wireless or hardwired communications, and a router 115 may simultaneously employ devices of differing technologies. 116 For example, a MANET router may have four interfaces with 117 differing communications technologies: two hardwired (Ethernet 118 and FDDI) and two wireless (spread spectrum and impulse radio). 120 medium: 121 A communication channel such as free space, cable or fiber 122 through which connections are established. 124 communications technology: 125 The means employed by two devices to transfer information 126 between them. 128 connection: 130 A physical-layer connection---which may be through a wired or 131 wireless medium---between a device attached to an interface of 132 one MANET router and a device utilizing the same communications 133 technology attached to an interface on another MANET router. 135 link: 136 A ``logical connection" consisting of the logical *union* of one 137 or more connections between two MANET routers--identified by a 138 (RID, RID) pair. Thus a link may consist of a heterogeneous com- 139 bination of connections through differing media using different 140 communications technologies. 142 neighbor: 143 From the perspective of a given MANET router, a ``neighbor" is 144 any other router to which it has a link. 146 adjacency: 147 The name given to an ``interface on a neighboring router". From 148 the perspective of a given router, a connection is a (interface, 149 adjacency) pair. 151 topology: 152 A network can be viewed abstractly as a ``graph" whose ``topol- 153 ogy" at any point in time is defined by set of ``points" con- 154 nected by ``edges". (This term comes from the branch of 155 mathematics bearing the same name that is concerned with those 156 properties of geometric configurations (such as point sets) 157 which are unaltered by elastic deformations (such as stretching) 158 that are homeomorphisms.) 160 physical-layer topology: 161 A topology consisting of connections (the edges) through the 162 *same* communications medium between devices (the points) com- 163 municating using the *same* communications technology. Multi- 164 ple physical-layer topologies may exist for a given medium and 165 communications technology if adaptive or proactive power con- 166 trol, frequency or code division, or other physical-layer 167 mechanisms are employed. 169 network-layer topology: 170 A topology consisting of links (the edges) between MANET routers 171 (the points) which is used as the basis for MANET routing. Since 172 ``links" are the logical union of physical-layer ``connections", 173 it follows that the ``network-layer topology" is the logical 174 union of the various ``physical-layer topologies". 176 IP routing fabric: 177 The heterogeneous mixture of communications media and 178 technologies through which IP packets are forwarded whose topol- 179 ogy is defined by the network-layer topology. 181 Security Context: 182 A security context between two routers defines the manner in 183 which two routers choose to mutually authentication each other, 184 and indicates an authentication algorithm and mode. 186 Mobility Security Association: 187 A collection of security contexts, between a pair of routers, 188 which may be applied to IMEP protocol messages exchanged between 189 them. 191 Security Parameter Index (SPI): 192 An index identifying a security context between a pair of 193 routers among the contexts possible in the Mobility Security 194 Association. 196 3.0 Protocol Overview 198 The mechanisms contained in the IMEP are: 200 Message Aggregation (AGGR) 202 Network-layer Address Resolution (NARP) 204 Link/Connection Status Sensing (LCSS) 206 Broadcast Reliability (REL) 208 Multipoint Relaying (MPR) 210 Authentication (AUTH) 212 Message aggregation occurs as packets from ULPs become IMEP objects, 213 and IMEP packs a number of objects into larger IMEP messages for 214 transmission. NARP--a protocol to determine the *binding* of a RID 215 with each of its IP interface address--occurs implicitly in the 216 current specification as the router ID of a given router is put in 217 the header of each IMEP message. As each IMEP packet is encapsulated 218 in an IP packet, and its header contains the IP address of the 219 transmitting interface in the source field of the IP packet, the 220 binding can be made on reception of any IMEP packet (more on this 221 later). Usage of the remaining mechanisms is *optional*. The fol- 222 lowing dependency graph shows their relationships. 224 AGGR---NARP 225 | 226 +------+-------+ 227 | | | 228 REL LCCS MPR 229 | 230 -----+---- 231 | | 232 AUTH MPR 234 This simply means that everything uses IMEP's aggregation facility. 235 NARP occurs implicitly in every IMEP transmission. Usage of reliabil- 236 ity, LCCS, MRP and AUTH are optional. MRP traffic may be sent reli- 237 ably or unreliably. Authentication, if enabled, occurs reliably. 239 3.1 Relationship with Upper Layer Protocols 241 IMEP is intended to support the operation of many ULPs. ULPs that 242 wish to utilize IMEP must dynamically *register* with an IMEP imple- 243 mentation prior to using IMEP (more on registration in a moment). 245 3.1.1 Protocol Type Values 247 All ULPs which intend to utilize IMEP must have protocol type value, 248 and must give this value to IMEP during registration. This value is 249 used by a receiving IMEP implementation for purposes of demultiplex- 250 ing ULP objects within a received IMEP message so that they may be 251 passed to the appropriate ULPs. IMEP implementations receiving 252 objects with unknown (i.e. unregistered) protocol type values will 253 silently discard those objects. Several protocol types have already 254 been assigned well-known values (see the protocol grammar section), 255 but a protocol need not have a pre-assigned type value to make use of 256 IMEP, nor must the well-known assignments be adhered to. IMEP 257 currently does not specify how protocol type values are assigned or 258 used within a given administrative domain. 260 3.1.2 Protocol Handles 262 ULPs registering with IMEP must pass to IMEP a protocol ``handle" 263 which IMEP may then use to pass information back to the ULP. The 264 mechanism used to implement the handle is not specified (this is 265 implementation dependent)--it could be a pointer to a function with a 266 known signature, an object reference in a middleware-based implemen- 267 tation, etc.. 269 3.1.3 Protocol Epitaphs 270 ULPs registering with IMEP must specify an ``epitaph" object. The 271 epitaph object specifies a signal to be broadcast reliably to all 272 one-hop peer ULPs if the registered ULP fails. This permits peer 273 ULPs (on neighboring routers) to take appropriate action in case of 274 peer process failure. Protocols may re-register with IMEP at any 275 time in order to change the epitaph object, or to remove it if 276 desired. 278 Registration with an ``epitaph" object amounts to creating and main- 279 taining a symbiotic relationship between IMEP and a registered ULP. 280 There must exist a mechanism (not specified--implementation depen- 281 dent) that guarantees ``mutual liveness" to each protocol so that, 282 should either protocol fail, the other is reliably informed within 283 the time of a BEACON_PERIOD (defined subsequently). 285 The principle purpose for epitaph-based registration is *bandwidth 286 conservation*. Without such a mechanism, it is not possible for peer 287 ULP processes--who have previously exchanged control information and 288 remain connected via IMEP--to be assured of mutual vitality without 289 exchanging keepalive packets over the communication channel. 291 3.1.4 IMEP Signalling Support 293 ULPs registering with IMEP must indicate the level of IMEP signalling 294 support (ISS) they wish to receive from IMEP. IMEP signalling sup- 295 port is only meaningful if LCSS is enabled, and consists of signals 296 being generated by IMEP in response to topological change events 297 detected by LCSS, and then passed to subscribing ULPs (those ULPs 298 requesting ISS). Three levels of support are possible: 300 0) Connection-level: 301 All connection-level topological change events are passed to the 302 subscribing ULPs. Connection-level topological change events 303 consist of ``connection" activation and failure (recall a con- 304 nection consists of an (interface, adjacency) pair). Thus, all 305 physical-layer topology information is passed to the ULPs, per- 306 mitting these ULPs to have a complete internal view of the IP 307 routing fabric. 309 1) Link-level: 310 All link-level topological change events are passed to the sub- 311 scribing ULPs. Link-level topological change events consist of 312 ``link" activation and failure (recall a link consists of a 313 (RID, RID) pair). Thus, only network-layer topology information 314 is passed to the ULPs, permitting these ULPs to have only an 315 external view of the IP routing fabric. 317 2) Disabled: 318 No topological change events generated by IMEP as a result of 319 LCSS are passed to the ULP. This is the default mode. 321 3.1.5 ULP Registration 323 ULPs must register with IMEP *prior* to usage. ULP registration con- 324 sists of passing IMEP a protocol type value, a *handle* to the ULP 325 allowing IMEP to pass received objects to it (handle mechanism not 326 specified--implementation dependent), an *epitaph* object (this may 327 be null), and a parameter indicating the level of IMEP signaling sup- 328 port desired by the ULP. 330 3.2 Message Aggregation 332 MANET routing (and other) control protocols exchange control informa- 333 tion and other data in the form of routing control packets or 334 ``objects". To minimize the number of channel accesses generated by 335 control traffic, the IMEP aggregates and encapsulates these objects 336 into larger IMEP ``messages". The objects are treated as ``opaque" 337 objects by the IMEP protocol; i.e. IMEP is not aware of the contents 338 of the objects, only of the protocol ``type" of the object block 339 (necessary for protocol demultiplexing at a receiver) and the length 340 of each object. These ULP object blocks are contained in yet larger 341 IMEP messages which are passed to the IP layer for encapsulation and 342 forwarding. A single IMEP message can contain a mixture of reliable 343 and unreliable objects. The details can be found in the IMEP message 344 format section. 346 3.3 Network-level Address Resolution 348 IMEP supports a framework or architecture for MANET router and inter- 349 face identification and addressing. IMEP operates simultaneously on 350 two different topological levels: the ``logical network" topology 351 level---which is concerned with interrouter connectivity---and the 352 ``physical" topology level---which is concerned with interface con- 353 nectivity. Router IDs (RID) identify routers in the logical topol- 354 ogy, and IP addresses identify interfaces in the physical topology. 355 There may be *multiple* IP addresses associated with a given RID. 357 The purpose of a Network-level Address Resolution Protocol (NARP) is 358 to discover the mapping between RIDs and IP addresses. This is 359 envisioned typically only to be needed when a new connection is 360 discovered, as it is necessary to be able to associate an interface 361 (an IP address) with a router (an RID). 363 +----------+ 364 | Router | RID 365 +----------+ 366 | | 367 +--------------+ +--------------+ 368 | Interface | | Interface | IP Address 369 +--------------+ +--------------+ 370 | | 371 +--------------+ +--------------+ 372 | Phys Device | | Phys Device | MAC Address 373 +--------------+ +--------------+ 375 Figure 4: RIDs, IP and MAC addresses 377 While it is true that---as currently defined---RIDs are not 378 ``addresses" in the strict sense, they do uniquely identify a router 379 for purposes of internal routing computations and somewhat resemble a 380 logical ``router address". Thus, the IP address-to-RID mapping is 381 similar in spirit to IP address-to-MAC address mapping performed by 382 the present ARP protocol. Each mapping simply associates an IP 383 address with another identifier as shown in Figure 4. As with ARP, a 384 ``reverse" mapping is also defined as the Reverse Network-level 385 Address Resolution Protocol (RNARP). However, unlike RARP, a RNARP 386 request seeks to discover the *set* of IP addresses associated with a 387 given RID. The two mappings are shown in Figure 5. 389 ARP: IP --> MAC RARP: MAC --> IP 391 NARP: IP --> RID RNARP: RID --> {IP1,IP2,...,IPn} 393 Figure 5: ARP/RARP and NARP/RNARP 395 NARP is currently implemented *implicitly* through inclusion of the 396 RID in every IMEP message header. RNARP is not required in the 397 present specification, but may be specified and required in future 398 versions if deemed necessary. 400 3.4 Link/Connection Status Sensing 402 3.4.1 Definition of Link/Connection Status 404 Link/Connection Status Sensing (LCSS) is an optional mode that may be 405 enabled in IMEP. Many control protocols require accurate knowledge 406 of the status of links/connections between neighboring routers. 407 ``Link status" in the IP routing fabric is determined from the union 408 of the status of physical-layer ``connections" between interfaces. 410 The relationship of interfaces, adjacencies, connections and links is 411 depicted in Figure 2 from the perspective of router i. Router i has 412 two interfaces f1 and f2, each of which has a physical-layer connec- 413 tion with multiple interfaces attached to other routers---these 414 interfaces are referred to as adjacencies from router i's perspective 415 and are numbered with a's. In this figure, there are two connections 416 (f1,a1) and (f2,a2), the logical union of which composes the logical 417 link (i,k) between routers i and k. 418 +----------+ 419 | Router i | 420 +----------+ 421 +--------------+ +--------------+ 422 | Interface f1 | | Interface f2 | 423 +--------------+ +--------------+ 424 | | 425 | | 426 | | 427 | | 428 | | 429 | | 430 +--------------+ +--------------+ 431 | Adjacency a1 | | Adjacency a2 | 432 +--------------+ +--------------+ 433 +----------+ 434 | Router k | 435 +----------+ 437 Figure 2: Shown from router i's perspective, interfaces f1 and f2 are 438 connected to adjacencies a1 and a2 via connections (f1,a1) and 439 (f1,a2)---the union of which forms link (i,k). 441 The status of a connection may be INcoming or OUTgoing (either of 442 which meaning it is unidirectional) or BIdirectional. A unidirec- 443 tional link is composed from one or more similarly-directed, uni- 444 directional connections. A BIdirectional link may be composed from 445 the union of one or more bidirectional connections, or two or more 446 oppositely-directed, unidirectional connections, or some combination 447 thereof. A connection or link which is present or ``active" (i.e. 448 which has a non-null status, and is either uni or bidirectional), is 449 referred to as ``UP". A connection or link which is not active (i.e. 450 which has a null status) is referred to as ``DOWN". 452 The IMEP may be configured to run in the following ``connection 453 notification" modes: 455 BI-directional: 456 This mode requires that physical-layer connectivity between an 457 interface and an adjacency be established in *both* IN and OUT 458 directions before a connection is considered UP, and any 459 registered ULPs are subsequently notified. 461 UNI-directional: 462 This mode requires that physical-layer connectivity between an 463 interface and an adjacency need only be established in one 464 direction (IN or OUT) before a connection is considered UP and 465 the registered ULPs are subsequently notified. 467 As determined by the connection notification mode, the ULP is noti- 468 fied whenever there is a change (addition, modification, deletion) in 469 the status of an interface's connections. This notification is 470 implemented via a handle registered via the ULP/IMEP interface. 472 3.4.2 Link/Connection Status Sensing Packet Exchange Mechanism 474 The IMEP uses a combination of BEACON and ECHO packets (and other 475 equivalent packets to be described shortly) to ascertain connection 476 (and indirectly link) status. On initialization, an interface under 477 the control of IMEP broadcasts a BEACON packet to all adjacencies. 478 (Note: The format of a BEACON packet is specified in a later section, 479 but it essentially consists of an *empty* IMEP message; i.e. an IMEP 480 message containing only the IMEP message header.). Recall that adja- 481 cencies are interfaces that are only one hop away such as those on 482 the same Ethernet subnet, or those within wireless transmission range 483 of the broadcasting interface. (Note: Usage of the term ``broad- 484 cast" here means to transmit a *single* copy of a packet to *all* 485 interfaces reachable over one hop. As is the convention with other 486 Internet routing protocols, this is done using IP multicast. An IP 487 multicast address ``ALL_IMEP_ROUTERS" will be reserved with IANA, and 488 all MANET router interfaces will be configured to listen for this 489 address.) The purpose of a BEACON packet is to alert any adjacencies 490 of the existence and identity of the broadcasting interface; an 491 interface's identity is its IP address. The interface must ensure 492 that a BEACON packet (or *any* other packet, since all packets are 493 ``BEACON-equivalent") is transmitted at least once every 494 BEACON_PERIOD (BP) time units; i.e. no more than BP time units may 495 pass between subsequent transmissions of a BEACON (or ``BEACON- 496 equivalent") packet. 498 Reception of a BEACON at an interface implies either reconfirmation 499 or creation of ``IN" (read ``INcoming") status of a connection at 500 that interface, depending on whether or not the connection already 501 exists, respectively. Thus, BEACONs serve to tell a receiving inter- 502 face that ``someone else is out there." Once present, the status 503 remains for MAX_BEACON_TIME (MBT) time units, at which time it times 504 out if no subsequent BEACONs have been received; i.e. the link is 505 declared DOWN and is removed from the data structures. Creation or 506 loss of IN status may require notification of an upper level proto- 507 col, depending on its signalling support mode. 509 ECHO (or ``ECHO-equivalent") packets are used to respond to BEACONs. 510 The purpose of an ECHO packet is to let a ``BEACONing" router know 511 that someone hears its BEACON. An ECHO packet contains the identity 512 (i.e. IP interface address) of the interface broadcasting the ECHO 513 and the identity of the BEACONing interface to which it is respond- 514 ing. An ECHO packet is generated immediately in response to an ini- 515 tial BEACON reception. Subsequently, as long as the interface is 516 considered UP (i.e. IN or BI), an ECHO packet must be generated at 517 least once every BP time units; i.e. no more than BP time units may 518 pass between subsequent generations of an ECHO or ECHO-equivalent 519 packet. 521 Reception of an ECHO at an interface implies either reconfirmation or 522 creation of ``BIdirectional" status of an connection at that inter- 523 face, depending on whether or not the connection already exists, 524 respectively. This is because reception of ECHO packet confirms that 525 someone hears this interface (i.e. that is has OUTgoing status), and 526 simultaneously confirms that it itself can receive them and, hence, 527 also has INcoming status for that connection. 529 ECHO packets may be broadcast in accordance with one of two ``signal- 530 ling" modes, which applies to both ECHO and ACK semantics (more on 531 ACKs later): 533 Single Interface (SI): 534 An interface only sends ECHOs in response to BEACONs it 535 receives. This is the standard mode which permits efficient 536 link-layer detection of BI connections. This mode should be 537 enabled if the BI-directional connection notification mode is 538 enabled. 540 Multiple Interface (MI): 541 An interface sends ECHOs in response to BEACONs it receives, and 542 IMEP also sends Indirect ECHOs (IECHO) out *all* other inter- 543 faces. An IECHO carries the address of the interface being 544 echo'ed (as does an ECHO) but, additionally, carries the address 545 of the interface on the echoing router that received the 546 transmission being echoed. This mode is necessary to permit 547 ``IMEP-based detection" of BIdirectional links composed of 548 oppositely-directed, unidirectional connections between neigh- 549 boring routers. Note that by using this Echo mode (i.e. via 550 reception of IECHOS at other interfaces), an interface can be 551 informed (solely via IMEP) that it has an ``OUTgoing" connection 552 without also having ``INcoming" status and, hence, a BIdirec- 553 tional link. This mode should be enabled if the UNI-directional 554 connection notification mode is enabled. 556 To make this clear, consider Figure 3. 558 +----------+ 559 | Router i | 560 +----------+ 561 +--------------+ +--------------+ 562 | Interface f1 | | Interface f2 | 563 +--------------+ +--------------+ 564 | IN ^ 565 | | 566 | | 567 | | 568 | | 569 IN V | 570 +--------------+ +--------------+ 571 | Adjacency c1 | | Adjacency c2 | 572 +--------------+ +--------------+ 573 +----------+ 574 | Router k | 575 +----------+ 577 Figure 3: A bidirectional link consisting of two oppositely-directed 578 connections. 580 Assume that SI Echo mode is being used, and the wireless directional 581 connectivity is as shown. From router i's perspective, it can only 582 receive over interface f2, and thus classifies connection (f2,c2) as 583 IN. It is unaware that its BEACON packets being broadcast from 584 interface f1 are being received at interface c1 on router k. How- 585 ever, if MI mode is used, then router k will advertise (via IECHO 586 transmissions from c2) the reception of BEACON packets from f1 at c1 587 thereby informing router i that connection (f1,c1) should be classi- 588 fied as OUT. Of course, the reverse but same is true from router k's 589 perspective. 591 The additional functionality provided by the MI mode comes at the 592 cost of broadcasting IECHOs out one or more interfaces in addition to 593 the ECHO sent over the interface over which the corresponding BEACON 594 was received. This creates more ECHO overhead. For a given network, 595 this cost must be balanced against the frequency of occurrence of the 596 situation depicted in figure 3. 598 Additional activity at an ULP (involving communication over multiple 599 hops) is necessary to detect purely UNIdirectional links (i.e. links 600 consisting of one or more unidirectional connections) between 601 adjacent routers. 603 3.4.3 BEACON and ECHO ``Equivalency" 605 BEACON and ECHO packets are necessary for ascertaining current con- 606 nection status. From the perspective of a given router, BEACONs 607 announce the presence of a broadcasting interface, and ECHOs simul- 608 taneously announce the presence of an adjacency *and* that the adja- 609 cency can receive from the broadcasting interface. However, it 610 should be clear that the same information can be gleaned from other 611 IMEP packets. Specifically, all transmissions signal the presence of 612 a broadcasting interface and are, in this sense, ``equivalent" to 613 BEACON packets. Similarly, ACKnowledgements both announce the pres- 614 ence of an adjacency and, through the process of acknowledgement, 615 confirm that the adjacency recently received from the broadcasting 616 interface. Thus, in this sense, ACKs are equivalent to ECHOs. The 617 equivalency is depicted in the Figure 6. 619 BEACON --> 620 ALL/OBJ --> 621 +----------+ +-------------+ +-------------+ 622 | Router i |-| Interface f | - - - - | Adjacency c | 623 +----------+ +-------------+ +-------------+ 624 <-- ECHO or IECHOS 625 <-- ACK or IACKS 627 Figure 6: BEACON and ECHO Equivalency 628 Transmission or reception of a BEACON or ECHO-equivalent packet 629 affects the link-status sensing timers as would transmission or 630 reception of a BEACON or ECHO, respectively. Thus, during periods of 631 heavy data traffic, it is expected that BEACONs and ECHOs will rarely 632 be transmitted as their respective ``equivalent" packets will serve 633 their role in link status sensing. During periods of light or no 634 traffic, BEACONs or ECHOs will be transmitted as necessary to satisfy 635 the aforementioned timing requirements. 637 If MI mode is in use, the Indirect ECHOS are being sent out all 638 interfaces. In a corresponding fashion, Indirect ACKS (IACKS) must 639 be sent out all interfaces to provided reliability over BIdirection 640 links consisting of oppositely-direction, UNIdirectional connections. 641 These IACKS are also ``echo equivalent" and must indicate the address 642 of the interface they are IACKing, as well as the interface address 643 on the IACKing router which received the object being indirectly 644 ACKed. 646 3.4.4 Connection Failure Detection 648 Expiration of the MBT timer signals connection failure. Note that 649 separate timers are used to monitor IN and OUT connection status. 650 Thus, a connection may lose its OUT status while still retaining IN 651 status and vice versa. Obviously, a connection satisfying both IN 652 and OUT timing requirements is marked as BI. 654 3.5 Neighbor Broadcast Reliability 656 IMEP supports two broadcast delivery modes: 658 BROADCAST (IMPLICIT): 659 Delivery to the current one-hop neighbor set. 661 MULTICAST (EXPLICIT): 662 Delivery to a pre-specified subset of the one-hop neighbor set. 663 A ULP may specify one, some or all current neighbors. 665 Of course, both are delivered using one-hop scoped, multicast 666 addressing as is every IMEP message. 668 IMEP supports two reliability modes: 670 UNRELIABLE: 671 Unreliable, unsequenced delivery of either neighbor broadcast or 672 neighbor multicast data. 674 RELIABLE: 675 Reliable, sequenced delivery of either neighbor broadcast or 676 neighbor multicast data. 678 Thus, delivery may be implicit or explicit, and reliable or unreli- 679 able: all four combinations are possible. These modes are used for 680 delivery of opaque protocol objects, where reliable delivery-- i.e., 681 broadcast or multicast --is also guaranteed to be delivery ``in 682 order" of transmission. (Note: This should not be confused with 683 transport-layer, reliable multicast across an entire multihop net- 684 work.) 686 IMEP uses a ``point-to-multipoint selective repeat" algorithm to 687 guarantee broadcast or multicast reliability and ordered delivery. 688 This approach eliminates unnecessary retransmissions of the type com- 689 monly associated with ``go back n" algorithms, and is in keeping with 690 the greater IMEP goal of minimizing the number of required channel 691 accesses. 693 To support reliability, each object block is given a SEQUENCE number, 694 and is broadcast with that number. To provide in-order delivery, a 695 connection protocol is utilized to synchronize receivers with the 696 current broadcast SEQUENCE number. The connection and transmission 697 protocol is designed so that an explicit receiver list does not have 698 to be appended to every reliable object block. Instead, an implicit 699 list is used by ``coloring" all messages. If a message is received 700 with the correct color, then the SEQUENCE number has meaning and its 701 objects can be forwarded up the protocol stack. If the color is 702 incorrect, the receiver does not forward its objects up the protocol 703 stack. The connection protocol reliably transmits the current group 704 color to all members of the group. 706 When broadcast, a copy of the object block with a response list (i.e. 707 the set of neighbors that are required to acknowledge this block) is 708 stored. A retransmission timer is set to RETRANS_PERIOD (RP) time 709 units which, upon expiration, will cause the object to be rebroadcast 710 to any neighbors which have not acknowledged the object (this causes 711 the retransmission timer to be set again to RP). The time the packet 712 was initially broadcast is also stored. If the object's response 713 list is not empty (i.e it has not been acknowledged by some adjacen- 714 cies) after MAX_RETRANS_TIME (MRT) time units, the connections to 715 those adjacencies are declared DOWN. 717 Acknowledgements (ACKs) are sent in response to object block recep- 718 tions when (i) reliable delivery is indicated and (ii) when the 719 receiver is contained in the response list (either implicitly or 720 explicitly). Once a neighboring router has ACKed a given block, it 721 will be removed from the block's response list so that it will not be 722 required to ACK any future retransmissions. 724 3.5.1 The Reliable Delivery Neighborhood 726 Each router keeps track of the neighbors that can be reached reliably 727 through regular Beacon-Echo exchanges. For discussion purposes, con- 728 sider a single router, termed a ``base-router", B and any number of 729 ``neighbor routers", N(i), i=1,2, ..., P, where P is the number of 730 routers that can currently hear transmissions from B. Each router 731 N(i), will respond with an ECHO packet within the time constraints of 732 the BEACON-ECHO protocol outlined previously. If B hears an ECHO 733 packet from N(i), then N(i) is a candidate member of B's reliable 734 delivery neighborhood (RDN). For N(i) to become a member of B's 735 reliable delivery neighborhood (i.e., connected to B), B must broad- 736 cast a group COLOR with an explicit membership list. This object is 737 called a NEWCOLOR and must be acknowledged by every router on the 738 explicit membership list before B considers a reliable delivery 739 neighborhood to be formed. 741 From N(i)'s perspective, the neighborhood rooted at B is has COLOR K. 742 N(i) is a member of this neighborhood if the NEWCOLOR object expli- 743 citly contains N(i) as a member. A reliable delivery neighborhood 744 rooted at B with COLOR K and current sequence J is specified in the 745 triple RDN(B,K,J). The COLOR K is updated by B every time a change to 746 its RDN is discovered (either a new router comes in range or an 747 existing router moves out of range or becomes hidden). Every router R 748 in a MANET network will have a single RDN rooted at R. R can be a 749 member of any number of RDN's that are not rooted at R. Every router 750 keeps track of its RDN and of the RDN's for which it is a member. If 751 a router hears a router R1 but itself is not an explicit member of 752 RDN(R1,K,J), then it marks the current COLOR of RDN(R1,K,J) as color- 753 less or as RDN(R1,0,J). The format for a NEWCOLOR object is given in 754 a later section. 756 3.5.2 Neighborhood definitions 758 RDN(B): 759 Reliable delivery neighborhood rooted at MANET router B. 761 RDN(B,K): 762 Reliable delivery neighborhood rooted at MANET router B, with 763 COLOR K. 765 RDN(B,K,J): 766 Reliable delivery neighborhood rooted at MANET router B, with 767 COLOR K, and current broadcast sequence number J. 769 3.5.3 Reliable, Sequenced Delivery 771 Objects passed to IMEP from an ULP may be delivered reliably or 772 unreliably, and is specified by the ULP. This section addresses 773 reliable, sequenced delivery of ULP objects by IMEP to all members of 774 a RDN. Every reliable object in IMEP delivered from B to the 775 RDN(B,K,J) is colored with COLOR K and sequence number J. A router 776 N(i) is an intended receiver of the object if its notion of the COLOR 777 K associated with RDN(B) matches exactly the color contained in the 778 broadcast object. Therefore, N(i) may deliver a reliable object to 779 its ULP only if the object from B matches the COLOR and SEQUENCE that 780 N(i) has recorded for the RDN(B). If an object arrives with the 781 correct COLOR but the incorrect SEQUENCE number, then N(i) must 782 determine if the object is a duplicate or simply out of sequence. If 783 a duplicate, then N(i) discards the object. If out of sequence, then 784 N(i) retains the object until all earlier objects arrive. If an 785 object arrives with the incorrect COLOR, then N(i) discards the 786 object. 788 From the ULP's perspective, objects are delivered reliably and in 789 sequence to *only* those members of the RDN(B) that exists at the 790 time when the object was received by IMEP (Note this may not be the 791 time when the object was sent to IMEP from the ULP's perspective, due 792 possibly to interprocess communication delay between IMEP and the 793 local ULP). This is referred to as an (implicit) ``neighbor broad- 794 cast" object. 796 If the ULP requires a object to be delivered to a specific subset of 797 one-hop neighbors, then it should use ``neighbor multicast" objects 798 (see below). This latter delivery semantic frees ULPs from having to 799 decide whether or not a object is valid. Every reliable object passed 800 to the ULP from IMEP is guaranteed to be intended for the ULP, as 801 specified by the sender. 803 Reliability is established between *routers*, not interfaces. Thus, 804 the reliability semantics are the same regardless of whether BIdirec- 805 tion notification with SI signalling or UNIdirectional notification 806 with MI signalling is in use. 808 3.5.3.1 Sequence Numbers and Associations using Broadcast Semantics 810 The coloring of the RDN(B) corresponds to a single sender with a 811 number of ``associated" receivers. ECHOs from a router can be viewed 812 as a association request. If an association is already established 813 from B to N(i), then this request is vacuous. If, however, no associ- 814 ation from B to N(i) exists, the ECHO then acts like a association 815 request. A NEWCOLOR object with N(i) on the list completes the asso- 816 ciation from B to N(i) (from N(i)'s perspective) and N(i)'s ack- 817 nowledgement of the NEWCOLOR object completes the association from 818 B's perspective. 820 The RDN(B) maintains a single sequence number that all members of 821 RDN(B) must track. NEWCOLOR objects contain not only a new group 822 COLOR, but also the next expected SEQUENCE number. This allows sender 823 and receivers to synchronize the sequence numbers to provide in-order 824 delivery. 826 There are (subtle) consequences of these semantics. 828 1) An RDN(B) maintains a *single* sequence number for the neigh- 829 borhood. Hence, every N(i) must acknowledge *every* reliable 830 object to ensure that all members of RDN(B) maintain the sequence 831 order. Of course, multiple reliable objects contained in the same 832 IMEP message are acknowledged simultaneously with a single ACK. 833 If an object is intended for a single recipient, all must ack- 834 nowledge (to keep sequence numbers synchronized) and information 835 specific to this object must further designate the intended 836 recipient. This is due to the fact that the current scheme is 837 optimized for implicit neighbor broadcast delivery, not explicit 838 neighbor multicast. 840 2) When RDN(B,K0) is updated to RDN(B,K1) (color changes from K0 841 to K1), then all reliable objects must first be retired from B's 842 retry queue before the NEWCOLOR object can be transmitted. 844 3) The explicit association (via a colored neighborhood) means 845 that the first time a reliable object is transmitted, an explicit 846 recipient list can be (and is) omitted. This reduces the size of 847 objects and allows the receiver to determine if it should forward 848 the object up the protocol stack based on only the COLOR and 849 SEQUENCE number of the object. An additional feature of this 850 association is that if a single receiver fails to acknowledge an 851 object, an explicit recipient list may be appended to the reliable 852 object to indicate those routers that should re-ack the object. In 853 the case of delivery failure, this reduces the number of a media 854 accesses by requiring only those who have not acknowledged a 855 object to explicitly respond. 857 3.6 Multipoint Relaying 859 IMEP supports Multipoint Relaying (MR)--an optional mode or mechanism 860 designed to minimize the overhead of packet *flooding* throughout a 861 MANET by optimizing/reducing the number of duplicate retransmissions. 862 As control overhead expenditure is required to support MR, it is 863 recommended that this mode be enabled only when sufficient flooding 864 traffic exists so that the benefit derived from MR justifies its 865 cost. 867 Before describing MR in detail, we first give some terminology 868 specific to MR: 870 MultiPoint Relay (MPR): 871 A router which is selected by a one-hop neighbor to forward or 872 retransmit that neighbor's packets. 874 Multipoint Relay Selector (MPRS): 875 Each MPR has one or more neighbors which have selected it as a 876 MPR--each such neighbor is referred to as a ``Multipoint Relay 877 Selector". Each MPR keeps a table of RIDs identifying the 878 members of its MRS set so that it knows which packets to 879 retransmit via MR. 881 Source of the Multipoint Relay (SMR): 882 Each router which originally transmits a data packet via MR is 883 known as the ``Source of the Multipoint Relay" for that packet, 884 and is so identified in the packet. 886 Every router has a set of nodes one hop away N1 (its one-hop neighbor 887 set) and a set of nodes two hops away N2 (its two-hop neighbor set). 888 The objective of a router participating in MR is to select a minimal 889 subset M of MPRs from N1 so that their retransmissions cover N2. 891 Multipoint relaying proceeds as follows: 893 Each MR router periodically broadcasts a Multipoint Relaying Adver- 894 tisement (MRA) packet once every Multipoint Relaying Period (MRP) 895 containing its RID, the RIDs of all its one-hop neighbors in N1, and 896 the subset M of these neighbors it has selected as its MPRs. This is 897 an implicit broadcast to the current one-hop neighbor set N1 which 898 may occur reliably or unreliably as desired. It can easily be seen 899 that with each MR router transmitting the identity of its set N1, 900 every MR router learns its set N2. 902 The algorithm for selection of the set M is not prescribed. It is 903 required only that the set M be chosen so as to cover N2. The aim is 904 to select the ``minimum" number of MPRs to do so. 906 One possible algorithm is: 908 1. Start with an empty set M. 909 2. First select as MPRs those routers from F1 which 910 provide the ``only path" to reach some routers in N2. 911 3. While there still exist some routers in N2 that are not 912 covered by M: 913 3.1 For each router in N1, calculate the number of routers 914 in N2 reachable through this router which are not 915 yet covered by M; 916 3.2 Select as a MPR that router which reaches the 917 maximum number of uncovered routers in R2. 919 A ``flood termination" mechanism is also required and is implemented 920 simply by including a SMR field and a sequence number in every MR 921 object. This enables routers to maintain a list of recently-received 922 MR objects. MR objects are passed to the appropriate ULP the *first* 923 time they are recieved at a router, and are silently discarded 924 thereafter. 926 3.7 Authentication 928 Authentication is optional. If authentication is enabled, MANET 929 routers have the choice of implementing multiple authentication 930 options ranging from simple to complex. IMEP messages between MANET 931 routers are authenticated with the IMEP Authentication object, which 932 contains the option is use. This object immediately follows all non- 933 authentication objects. 935 4. IMEP Message Format 937 The following describes the message format of the proposed protocol. 938 An IMEP message format consists of several fixed, mandatory fields 939 followed by a self-formatting byte stream. The stream is aligned 940 along ``byte" boundaries---not 32-bit word boundaries---to 941 save transmission overhead at the cost of extra processing at a 942 router. An IMEP message typically contains at least one of several 943 optional object blocks. A message containing no objects is a BEACON 944 message. The following ``grammar" describes the syntax of an IMEP 945 message. 947 : 949 : 951 : 952 | 954 : 955 | 957 : 959 : 960 | 962 : 964 : 965 | 966 | 967 | 968 | 969 | 970 | 971 | 973 : 975 : 976 978 : 979 981 4.1 983 Every IMEP message contains header information. A message with 984 no objects is termed a BEACON message. Included in 985 every header is the of the sending IP interface. 987 : 989 31 24 23 16 15 8 7 0 990 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 991 | (a) | (b) | (c) | 992 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 994 31 24 23 16 15 8 7 0 995 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 996 | (d) | 997 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 999 (a) Protocol version (8 bits) 1001 (b) Group color (8 bits) 1002 == 0 - colorless 1003 otherwise - reliability sequence numbers are prefixed by 1004 this color 1006 (c) Total message length (in bytes) of this 1007 IMEP packet (16 bits) which lies in the following range: 1009 3 < IMEP_LENGTH <= MAX_IMEP_LENGTH <= 65535 1011 (d) Router Id associated with the sender's IP interface. 1013 4.1.1 1015 31 24 23 16 15 8 7 0 1016 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1017 | (a) | (b) | (c) | 1018 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1020 (a) object type (8 bits) 1021 0 - reserved 1022 1-127 - object does not carry reliability information, 1023 seq# ignored 1024 128-255 - object must be delivered reliably, in order, 1025 according to color and seq # 1027 (b) Sequence number for this object (8 bits) 1029 (c) Length (in bytes) of this object 1030 (16 bits). does not include the length 1031 of the SUBMESSAGE HEADER, but does include the length of 1032 the explicit ack list, if any. 1034 ( <= - 4) 1036 4.1.2 1038 The following object types are defined for this version of IMEP. 1040 Unreliable Object Types: 1042 1 - SM_ECHO : object 1043 2 - SM_ACK : object 1044 3 - SM_UBCAST : object, delivered unreliably 1045 4 - SM_UMCAST : object, delivered unreliably 1046 5 - SM_UMRA : object, delivered unreliably 1047 6 - SM_UMR : object, delivered unreliably 1048 7 - SM_IECHO : object 1049 8 - SM_IACK : object 1050 [65,73] : (future) IPV6 Versions of the above 1051 objects 1053 Reliable Object Types: 1055 128 - SM_NEWCOLOR : object 1056 129 - SM_BCAST : object delivered reliably 1057 130 - SM_MCAST : object delivered reliably 1058 131 - SM_AUTH : object delivered reliably 1059 132 - SM_MRA : object, delivered reliably 1060 133 - SM_MR : object delivered reliably 1061 [192,197] : (future) IPV6 Versions of the above 1062 objects 1064 4.2 IMEP objects 1066 This section describes the ordering of IMEP objects a MANET router 1067 may include in an IMEP message. This following ordering MUST be fol- 1068 lowed: 1070 a) The fixed-length IMEP message header, followed by 1072 b) If present, any non-authentication objects, followed by 1074 c) The IMEP Authentication object. 1076 The authentication in the IMEP messages MUST be checked. The receiv- 1077 ing router MUST check for the presence of a valid IMEP Authentication 1078 object, and perform the indicated authentication. Exactly one IMEP 1079 Authentication object MUST be present in the IMEP message, and the 1080 home agent MUST check the Authenticator value in the object. If no 1081 IMEP Authentication object is found, or if more than one IMEP Authen- 1082 tication object is found, or if the Authenticator is invalid, the 1083 receiving router MUST discard the IMEP message and SHOULD log the 1084 error as a security exception. 1086 4.2.1 1088 The block may contain any number (subject to message length 1089 restrictions) of Addresses 1091 : 1093 : 1094 | 1096 : 1098 A is a 32-bit address that contains the interface being 1099 echo'ed. 1101 31 24 23 16 15 8 7 0 1102 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1103 | (a) | 1104 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1106 (a) IPV4 of interface that is being echo'ed (4 bytes) 1108 The number of addresses in this list are inferred from the 1109 field. 1111 4.2.2 1113 The ACK Block format is: 1115 : 1117 : 1118 | 1120 : 1122 is defined as follows: This block may contain any number 1123 (up to total length restrictions) of acknowledgements interfaces and 1124 sequence #'s 1126 numAcks = /6 1128 ACK Block 6-byte byte block: 1130 31 24 23 16 15 8 7 0 1131 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1132 | (a) | 1133 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1135 15 8 7 0 1136 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1137 | (b) | (c) | 1138 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1140 (a) IPV4 address of interface being ACKed (4 bytes) 1141 (b) Group Color (8 bits) 1142 (c) object sequence# (8 bits) 1144 4.2.3 1146 The block may contain any number (subject to message length 1147 restrictions) of s. 1149 : 1151 : 1152 | 1154 : 1156 A consists of two 32-bit addresses that contain the 1157 interface being echo'ed by the router and the interface which 1158 received the BEACON-equivalent, for which this is an *indirect* echo. 1160 31 24 23 16 15 8 7 0 1161 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1162 | (a) | 1163 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1165 31 24 23 16 15 8 7 0 1166 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1167 | (b) | 1168 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1170 (a) IPV4 of interface that is being echo'ed (4 bytes) 1172 (b) IPV4 of interface of the receiving interface (4 bytes) 1174 The number of entries in this list are inferred from the 1175 field. 1177 4.2.4 1179 The Block format is: 1181 : 1183 : 1184 | 1186 : 1188 is defined as follows: This block may contain any number 1189 (up to total length restrictions) of indirect acknowledgements. 1191 numIAcks = /10 1193 IACK Block 10-byte byte block: 1195 31 24 23 16 15 8 7 0 1196 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1197 | (a) | 1198 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1200 31 24 23 16 15 8 7 0 1201 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1202 | (b) | 1203 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1205 15 8 7 0 1206 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1207 | (c) | (d) | 1208 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1210 (a) IPV4 address of interface being IACKed (4 bytes) 1211 (b) IPV4 address of receiving interface (4 bytes) 1212 (c) Group Color (8 bits) 1213 (d) object sequence# (8 bits) 1215 4.2.5 1217 : 1219 This contains the information about a new COLOR and SEQUENCE for a 1220 multicast group. The membership list is done as an explicit 1221 and is not handled here. 1223 numMembers = ( - 2)/4 1225 15 8 7 0 1226 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1227 | (a) | (b) | 1228 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1230 (a) New group color (8 bits) 1232 (b) Next valid sequence# (8 bits) 1234 4.2.6 1236 The MRA Block format is: 1238 : 1239 1241 : 1242 | 1244 : 1245 | 1247 is defined as follows: This block contains the RID of the 1248 advertising MRS, followed by a counter indicating the number of 1249 neighbors and a counter indicating the number of words required to 1250 hold the MPR flags indicating which of those neighbors are MPRs. The 1251 MRA may contain any number (up to total length restrictions) of one- 1252 hop neighbor RIDs, and associated flags specifying which of these 1253 neighbors have been selected as MPRs. 1255 31 24 23 16 15 8 7 0 1256 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1257 | (a) | 1258 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1259 31 24 23 16 15 8 7 0 1260 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1261 | (b) | (c) | 1262 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1264 (a) Router ID of advertising MRS (4 bytes) 1265 (b) Number of one-hop neighbors (16 bits) 1266 (c) Number of 32-bit words required for 1267 MPRFLAGS (16 bits) 1269 NUM_MPRFLAGWORDS = (NUM_NBRS+31)/32 1271 31 24 23 16 15 8 7 0 1272 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1273 | (d) | 1274 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1276 (d) Neighbor Router ID (4 bytes) 1277 One entry per neighbor. 1279 31 24 23 16 15 8 7 0 1280 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1281 | (e) | 1282 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1284 (e) 32-bit word containing 32 1-bit MPR flags 1285 One word required for 32 neighbors. 1286 The i-th bit in the j-th word indicates the MPR status 1287 of the n-th (n = j*32 + i) neighbor in the neighbor list 1288 where 1 indicates the neighbor is a MPR, and 0 indicates 1289 otherwise. 1291 4.2.7 1293 A broadcast object block is used for delivering encapsulated data to 1294 an upper-layer protocol (ULP). This block will be received and passed 1295 to the appropriate ULP by all receivers. If the is sent 1296 reliably, then only those routers with a matching color may forward 1297 the message to the appropriate ULP. Each object block may be 1298 independently- sequenced by virtue of its object header. However, all 1299 blocks with reliability share the same group color. 1301 : 1303 23 16 15 8 7 0 1304 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1305 | (a) | (b) | (c) .... 1306 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1308 (a) protocol type (8 bits) 1309 0 - reserved 1310 1 - TORA 1311 2 - AODV 1312 3-255 - unassigned 1314 (b) block length (in bytes) (16 bits) 1316 (c) This is bytes of data encapsulated by IMEP 1318 blocks are delivered reliably, and can therefore have an 1319 explicit acknowledgement list. The in (b) can be subtracted 1320 from the to determine the number of explicit 1321 addresses that should generate acknowledgments. 1323 numExplicitAcks = ( - ( + 3))/4 1325 4.2.8 1327 A multicast (or explicit) object block is very similar to a broadcast 1328 object in that it is also used for delivering encapsulated data to an 1329 upper-layer protocol (ULP). The difference is that the 1330 contains an *explicit* delivery list. This implies that the object 1331 data block can be passed to the appropriate ULP only by receivers 1332 that are members of the . If the is sent 1333 reliably, then only those routers with a matching color may forward 1334 the message to the appropriate ULP. Each object block may be 1335 independently-sequenced by virtue of its object header. However, all 1336 blocks with reliability share the same group color. It should be 1337 noted that if this block is sent with reliability, then all 1338 receivers, not just those on the , must ACKnowledge 1339 receipt of the message. 1341 : 1343 23 16 15 8 7 0 1344 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1345 | (a) | (b) | 1346 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1348 15 8 7 0 1349 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1350 | (c) | (d) .... 1351 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1353 (a) protocol type (8 bits) 1354 0 - reserved 1355 1 - TORA 1356 2 - AODV 1357 3 - DSR 1358 4 - ZRP 1359 5-255 - unassigned 1361 (b) block length (in bytes) (16 bits) 1363 (c) - Length of the explicit delivery list 1364 (in bytes). (16 bits) 1366 (d) This is bytes of data encapsulated by IMEP 1368 blocks may be delivered reliably, and can therefore have an 1369 explicit acknowledgement list. The in (b) and the 1370 in (c) can be subtracted from the from the 1371 to determine the number of explicit addresses that 1372 should generate acknowledgments. 1374 numExplicitAcks = ( - ( + 1375 + 3))/4 1377 4.2.9 1379 A multipoint relaying object block is also similar to a broadcast 1380 object in that it is also used for delivering encapsulated data to an 1381 upper-layer protocol (ULP). The difference is that the contains 1382 an implicit delivery list as determined by the MR algorithm. The 1383 object data block is only passed to the appropriate ULP the *first* 1384 time it is received at a router--any subsequently received copies are 1385 silently discarded. Routers maintain a list of recently-received 1386 blocks indexed by SMR and MRSEQUENCE to determine whether a block was 1387 previously received. 1389 If the is sent reliably, then only those routers with a matching 1390 color may forward the object to the appropriate ULP. Each object 1391 block may be independently-sequenced by virtue of its object header. 1392 However, all blocks with reliability share the same group color. It 1393 should be noted that if this block is sent with reliability, then all 1394 receivers, not just the MPRs, must ACKnowledge receipt of the mes- 1395 sage. 1397 : 1399 31 24 23 16 15 8 7 0 1400 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1401 | (a) | 1402 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1404 31 24 23 16 15 8 7 0 1405 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1406 | (b) | (c) | (d) | 1407 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1409 31 24 23 16 15 8 7 0 1410 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1411 | (e).... 1412 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1414 (a) protocol type (32 bits) 1415 Router ID of Source of the Multipoint Relay packet. 1417 (b) Multipoint Relay packet sequence# (8 bits) 1419 (c) protocol type (8 bits) 1420 0 - reserved 1421 1 - TORA 1422 2 - AODV 1423 3 - DSR 1424 4 - ZRP 1425 5-255 - unassigned 1427 (d) block length (in bytes) (16 bits) 1429 (e) This is bytes of data encapsulated by IMEP 1431 4.2.10 , 1433 Lists are arrays of IPV4 addresses. Each entry is a 32-bit address in 1434 network byte order. The length of the list is either stored as part 1435 of the object information (see ) or inferred from 1436 other available lengths (see and ). 1438 4.2.11 (The IMEP Authentication object) 1440 The IMEP Authentication object is used to authenticate all IMEP 1441 objects. The types of authentication to be supported will be speci- 1442 fied in a proposed MANET Authentication Architecture under develop- 1443 ment. 1445 4.3 ULP/IMEP Interface 1447 Other than registration, IMEP interacts with ULPs in several funda- 1448 mental ways. Here this interaction is specified in a format which 1449 loosely follows the Object Management Group's (OMG) Interface Defini- 1450 tion Language (IDL). 1452 4.3.1 Registration 1454 ULPs must register with IMEP prior to use. Registration consists 1455 of calling the following register function. 1457 typedef enum SignallingSupport { CONN, LINK, DISABLED }; 1459 void register (in type, 1460 // indicates Protocol type of data object 1461 // if not valid, an InvalidProtocolType exception 1462 // is thrown. 1463 in any ULPhandle, 1464 // *implementation-dependent* 1465 // a handle is passed to IMEP depending on the 1466 // implementation of the ULP/IMEP system that allows 1467 // IMEP to pass signals to the ULP. 1468 // if not valid (and this is detectable by IMEP), 1469 // an InvalidULPhandle exception is thrown. 1470 in epitaphLength, 1471 // indicates length of the epitaph object; 1472 // if length = 0, this indicates no epitaph message and 1473 // the OBJDATA field is ignored. 1474 // if length > MAX_EPITAPH_LENGTH, then 1475 // an InvalidByteLength exception is thrown 1476 in epitaph, 1477 // opaque epitaph data object 1478 in SignallingSupport mode) 1479 // indicates IMEP Signalling Support mode 1480 // if incorrect, an InvalidSignallingSupport exception 1481 // is thrown 1482 raises (InvalidProtocolType, 1483 InvalidULPhandle, 1484 InvalidByteLength, 1485 InvalidSignallingSupport); 1487 4.3.2 Encapsulation 1489 IMEP principally aggregates and encapsulates ULP objects into longer 1490 IMEP messages. From a ULP's perspective, these may be delivered 1491 reliably or unreliably, and either implicitly broadcast to the 1492 entire one-hop neighbor set, or explicitly multicast to a one-hop 1493 neighbor subset. Thus, an object being given to IMEP for transmission 1494 must come with this additional information. The following 1495 specifies the operation ``encapsulate". 1497 typedef enum Boolean { TRUE, FALSE }; 1498 typedef enum ForwardingMode { BCAST, MCAST, MR }; 1500 void encapsulate (in type, 1501 // indicates Protocol type of data object 1502 // if not valid, an InvalidProtocolType exception 1503 // is thrown. 1504 in length, 1505 // indicates length of data object; 1506 // if length > MAX_IMEP_LENGTH, then 1507 // an InvalidByteLength exception is thrown 1508 in data, 1509 // data object to be transmitted 1510 in ForwardingMode mode, 1511 // indicates IMEP forwarding mode 1512 // if incorrect, an InvalidForwardingMode exception 1513 // is thrown 1514 in list, 1515 // List of IPv4 addresses to which object 1516 // should be explicitly delivered via MCAST. 1517 // If one or more addresses are incorrect, 1518 // an InvalidInterface exception is thrown 1519 in Boolean reliability) 1520 // indicates whether reliable delivery is desired 1521 raises (InvalidProtocolType, 1522 InvalidByteLength, 1523 InvalidForwardingMode, 1524 InvalidInterface); 1526 5. Security Considerations 1528 The MANET computing environment is very different from the ordinary 1529 computing environment. In many cases, mobile computers will be con- 1530 nected to the network via wireless links. Such links are particu- 1531 larly vulnerable to passive eavesdropping, active replay attacks, and 1532 other active attacks. Among its many uses, the networking protocol 1533 described in this document enables inter-router communication for 1534 purposes of network control. This control function could be a 1535 significant vulnerability if IMEP messages are not authenticated. 1537 Authors' Addresses: 1539 M. Scott Corson 1540 Institute for Systems Research 1541 A.V. Williams Building (115) 1542 University of Maryland 1543 College Park, MD 20742, USA 1544 (301) 405-6630 1545 corson@isr.umd.edu 1547 S. Papademetriou 1548 Institute for Systems Research 1549 A.V. Williams Building (115) 1550 University of Maryland 1551 College Park, MD 20742, USA 1552 (301) 405-7933 1553 spyro@isr.umd.edu 1555 Philip Papadopoulos 1556 Computer Science and Mathematics Division 1557 Oak Ridge National Laboratory 1558 Oak Ridge, TN 37831-6367, USA 1559 (423) 241-3972 1560 papadopoulpm@ornl.gov 1562 Vincent Park 1563 Information Technology Division 1564 Code 5540 1565 Naval Research Laboratory 1566 Washington, DC 20375, USA 1567 (202) 767-5098 1568 vpark@itd.nrl.navy.mil 1570 Amir Qayyum 1571 INRIA 1572 Sophia-Antipolis, France 1573 Amir.Qayyum@inria.fr