$Id: rap.txt,v 1.11 2004/03/02 21:35:22 luca Exp $ Robos Ad-Hoc Protocol Packet Format - RAP With contributions from: Luca de Alfaro , Eric Decker ================================================================ COMMON FORMAT 0 1 2 3 4 5 +--------+--------+--------+--------+--------+--------+-- ... | len | ptype | dst | src | nonce | sr_ptr | +--------+--------+--------+--------+--------+--------+-- ... 1 1 1 1 1 1 6 7 ...-+--------+--------+--------+-- ... --+--------------------+ ... | rlen | source route ... | type-specific part | ... +--------+--------+--------+-- ... --+--------------------+ 1 rlen bytes len : packet length ptype: broadcast/routed id, packet type dst: destination address src: source address nonce: the pair source/nonce is unique when used (broadcasts), and non-zero sr_ptr: route index. For broadcast packets, this is the next free element, as the route is lengthened. For routed packets, it is the inded of the intended hop recipient. rlen: route length source route: list of hops this packet should traverse All addresses should be different from #ff, that is, 255, which is reserved for broadcast. ptype: 1 RR Route Request (route discovery) 2 RP Route Reply (route discovery) 3 RC Route Confirm (route discovery) 4 AK Network ACK (route ack) 5 DT Data Not all fields are used in all contexts. For instance, the nonce is used only for RR and RP packets (i.e., when it is necessary to broadcast). These fields are followed by a type-specific part, which depends on the packet type. The broadcast packets are RR and RP. The routed packets are RC, AK, and DT. ================================================================ BROADCAST PACKETS Route Request: ptype = RR The Route Request packet is used to request a route be found from SRC to DST. The originating node will construct an RR packet with a source route that only contains itself, a unique non-zero nonce and send the packet. Each node receiving the packet will 1st check to see if this src/nonce pair has been seen and if so discards the packet (storm completion). Otherwise, the node will add itself to the end of the source route, and the packet will be re-broadcast. Type specific part: none ================ Route Reply: ptype = RP The Route Reply packet is used to establish a reverse route in response to a Route Request. A responding node will construct an RP packet based on a received RR packet. It will copy the forward route of the RR packet into the forward route, it will generate a reverse route containing only itself, and it will generate a new nonzero nonce. As for RR packets, the forward route initially contains only the originator of the RR packet. The destination of the RP packet is the source of the RR packet. Each intermediate node will first check the src/nonce pair, and discard the packet if the src/nonce pair has already been seen. If the src/nonce pair is new, the node adds itself to the end of the forward route, and re-broadcasts the packet. Type specific part: +--------+--------+--------+-- ... --+ | rlen | rev route ... | rev route +--------+--------+--------+-- ... --+ rev route: new route constructed by propagation of the RP packet. ================ Route Confirm: ptype = RC The Route Confirm packet is used by a destination node to respond to a Route Request without flooding. The packet is created essentially by keeping in the same order the forward and reverse route of an RP packet. Type specific part: +--------+--------+--------+-- ... --+ | rlen | ack route ... | +--------+--------+--------+-- ... --+ ack route: route being ackowledged. ================ Data Packets: ptype = DT Type specific part: +--------+------+-------+ | dtype | dlen | data | +--------+------+-------+ dtype: the upper layer protocol that the data is in. I propose not to use this for the moment. dlen: length of data part of the packet. data: upper layer data ================ Acknowledge packets: ptype = AK The ACKN packet allows a receiving node to tell the source that it was heard. When the sourcing node hears this packet it also knows that its route is still valid. Type specific part: none. ================================================================ Examples Node 3 is trying to communicate with node 8 and doesn't have a route. (in the following tables, N indicates the source node, and is not part of the protocol. The packet length is also omitted, as the author finds it too tiresome to compute). Note how sr_ptr starts counting from 1: the element pointed to by sr_ptr is the next hop, which in this case is not in the list, as it is unknown. N ptype dst src nonce sr_ptr rlen srcroute 3 RR 8 3 23 1 1 3 nodes 1, 25, and 22 receive the RR and propagate N ptype dst src nonce sr_ptr rlen srcroute 1 RR 8 3 23 2 2 3-1 25 RR 8 3 23 2 2 3-25 22 RR 8 3 23 2 2 3-22 now nodes 3, 1, 25, and 22 all receive these packets too, see that the src/nonce of 3/23 has already been seen and drop the storm packets. Similar conditions in this example will be ignored. Node 4 sees the transmission from 1, 25, and 22 but gets the packet from 1 first. N ptype dst src nonce sr_ptr rlen srcroute 4 RR 8 3 23 3 3 3-1-4 Node 7 gets it next. N ptype dst src nonce sr_ptr rlen srcroute 7 RR 8 3 23 4 4 3-1-4-7 Finally 8 gets it. It adds itself to the source route, and responds with an RP packet. ======== Using RP, here is node 3's reply. rev_len is the length of the reverse route, and rev_route is the reverse route. Note that a new nonce is used. We assume that the reverse route that will be discovered is 8,7,6,2,1,3. Note that sr_ptr is always 0, as it is meaningless. N ptype dst src nonce sr_ptr rlen srcroute rev_len rev_rote 8 RP 3 8 55 0 5 3-1-4-7-8 1 8 7 RP 3 8 55 0 5 3-1-4-7-8 2 8-7 6 RP 3 8 55 0 5 3-1-4-7-8 3 8-7-6 2 RP 3 8 55 0 5 3-1-4-7-8 4 8-7-6-2 1 RP 3 8 55 0 5 3-1-4-7-8 5 8-7-6-2-1 When 3 receives the packet, the final reverse route is 8-7-6-2-1-3. ======== At this point, node 3 knows that to get to 8, it can use 3-1-4-7-8. However, node 8 does not know how to get to 3. Hence, node 3 uses a RC packet to send the route 8-7-6-2-1-3 to 8. This is a routed packet, since node 3 knows the route to 8. We use ? to denote arbitrary content. N ptype dst src nonce sr_ptr rlen srcroute rev_len rev_route 3 RC 8 3 ? 1 5 3-1-4-7-8 6 8-7-6-2-1-3 1 RC 8 3 ? 2 5 3-1-4-7-8 6 8-7-6-2-1-3 4 RC 8 3 ? 3 5 3-1-4-7-8 6 8-7-6-2-1-3 7 RC 8 3 ? 4 5 3-1-4-7-8 6 8-7-6-2-1-3 At this point, 8 can put in the cache that the route to 3 is 8-7-6-2-1-3. ======== At this point, the communication is established. We can send data: from 3 to 8: N ptype dst src nonce sr_ptr rlen srcroute dtype dlen data 3 DT 8 3 ? 1 5 3-1-4-7-8 ? 4 3-4-6-2 1 DT 8 3 ? 2 5 3-1-4-7-8 ? 4 3-4-6-2 4 DT 8 3 ? 3 5 3-1-4-7-8 ? 4 3-4-6-2 7 DT 8 3 ? 4 5 3-1-4-7-8 ? 4 3-4-6-2 ======== And 8 is kind enough to respond with an AK: N ptype dst src nonce sr_ptr rlen srcroute 8 AK 3 8 ? 1 6 8-7-6-2-1-3 7 AK 3 8 ? 2 6 8-7-6-2-1-3 6 AK 3 8 ? 3 6 8-7-6-2-1-3 2 AK 3 8 ? 4 6 8-7-6-2-1-3 1 AK 3 8 ? 5 6 8-7-6-2-1-3 And finally 3 gets it. Wonderful! # $Log: rap.txt,v $ # Revision 1.11 2004/03/02 21:35:22 luca # fixed typo in RR reception description - thanks Preetha # # Revision 1.10 2004/03/02 21:20:34 luca # fixed sr_ptr in RP packets, and reserved ff for broadcast # # Revision 1.9 2004/03/02 21:02:00 luca # changed format of RP packets # # Revision 1.7 2004/03/02 08:05:47 luca # Made sure the nonce must be non-zero. # # Revision 1.6 2004/03/01 11:26:07 luca # Some minor changes. # # Revision 1.5 2004/03/01 07:15:58 luca # Now sr_ptr starts counting from 0, so the element pointed to it can be # retrieved simply by doing data[sr_ptr]. # # Revision 1.4 2004/03/01 06:22:38 luca # Added list of contributors # # Revision 1.3 2004/03/01 06:21:01 luca # *** empty log message *** # # Revision 1.2 2004/03/01 06:20:04 luca # - Changed the name of ACKP packet to AK # # - Changed names of other fields, to hopefully improve readability. # # - Added a dlen field to keep track of the length of the data part. # # - Changed the use of the reverse list for RP packets: with the current # definition, the forward list is the route list that always gets # longer. # # - Likewise, put in the right order the routes in RC packets. # # - Fixed how sr_ptr works; there were bugs here. # # - Re-did the examples. # # - Overhauled the reorganization of the text. # # Basically, this is a whole new version. #