| Internet-Draft | STURP | June 2023 |
| Lou, et al. | Expires 1 January 2024 | [Page] |
This memo describes an approach to updating topologies in typical MANET-like environments, relying on what is termed 'sloppy updates' in the remainder of this document. Key to the approach is that updates are only initiated if existing communication relations may be effect by non-synchronized topology information, otherwise using the topology information as it exists. This 'sloppy' nature of the approach reduces the needed updates and the associated communication for them, thus increases efficiency as well as performance from a user perspective. As such, STURP does not provide a complete routing protocol solution but is intended to extend existing routing protocols with this improved efficiency mechanism instead.¶
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶
This Internet-Draft will expire on 1 January 2024.¶
Copyright (c) 2023 IETF Trust and the persons identified as the document authors. All rights reserved.¶
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 Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License.¶
The penetration of smart devices like smart phones, pads, smart watches, cameras, speakers and TVs, etc. has led to the increasing proliferation of mobile ad-hoc networks and communications, as shown in Figure 1. A key characteristic of those environments is the minimization or entire absence of dedicated network infrastructure involved in such networks. For instance, a smart watch can pair with a smart phone via bluetooth to exchange contacts and takes over phone calls. It can further talk to a speaker connected to the home WiFi network via the smart phone. When the smart phone is absent, a tablet may take over the role to bridge the link between the smart watch and the speaker. Common to those scenarios is the need for a self organized network, with a dynamic topology comprised of the currently participating devices in that network.¶
Looking more closely at those environments, we can recognize that devices may join or leave the network depending on the application, location, and their own status. In the presence of such dynamicity, proactive network formation is desired to enable any to any as well as instant device communication, while ensuring the Quality of Experience (QoE) of any such communication.¶
As a key aspect in a routing and communication protocol for such environments, it is required that all devices in the network are able to create and periodically refresh the network topology information, including node addresses and link information. For instance, the Ad hoc On-Demand Distance Vector (AODV) routing protocol defined in [RFC3561] enables dynamic, self-starting, multi-hop routing between network nodes to establish and maintain ad hoc networks. However, it is a reactive routing protocol, creating a relatively higher end-to-end delay due to route discovery ([SHARMA16], [SHANKAR16]), which impacts the QoE of the communication. The Optimized Link State Routing (OLSR) protocol defined in [RFC3626] and further optimized by [RFC7181], was developed as a proactive protocol for mobile ad-hoc networks to exchange and update the network topology periodically. It reduces the end-to-end latency and improves the QoE. Although a set of Multi-Point Relays (MPR) is selected by each node to reflect control traffic efficiently, thus avoiding flooding the overall network, the frequent periodic refreshing leads to higher power consumption, which is not desirable for battery enabled devices. RPL [RFC6550] (Routing Protocol for Low-Power and Lossy Networks) targets wireless networks with low power consumption, with the main target being many-to-one communication over IEEE 802.15.4, and thus possibly not providing the desired QoE in different use cases. Its routing based on a proactive distance vector approach. The Babel routing protocol, also based on a distance vector approach, has been designed to be robust and efficient on both wireless mesh networks and wired networks [RFC8966], and has been chosen by the Homenet WG as mandatory to implement. It includes various mechanisms to avoid loops, which however may lead to slow topology updates (still, preserving connectivity), which may hinder QoE. Babel does focus on energy efficiency for realizing its topology update.¶
Having identified the topology and service updates in such dynamic environment as a key contributing factor to the overall QoE, this memo introduces a mechanism we term 'sloppy topology updates for ad-hoc routing protocols' (STURP) for improving on topology updates. This is achieved through a proactive mechanism that limits updates for topology changes, e.g., through nodes joining or leaving, only to those cases where ongoing communication relations would be affected. As a consequence, full topology updates are postponed to regular intervals instead, while ongoing communication may continue, using partially correct topology information only. Through this, our approach strikes a balance between reducing the power consumption (and memory footprint) while keeping the QoE thanks to the proactiveness of its mechanism.¶
It is important to note that STURP does constitute a routing protocol per se, but merely addresses the crucial component for providing topology update. As such, we target the integration of STURP with existing routing protocols, improving thus the efficacy of those existing protocols.¶
In the remainder of this document, we first provide an overview of the protocol in Section 4, followed by the protocol interactions in Section 5, discussing the integration with existing routing protocols in Section 7.¶
+----------+
| WIFI AP0 |
+----------+
/ \
/ --PLC-- \
+----------+ +----------+
| WiFi AP1 | | WiFi AP2 |
+----------+ +----------+
/ \ / \
/ WiFi \ / WiFi \
+-----+ +-------+ +----+ +----+
| Pad | | Phone | | TV | | PC |
+-----+ +-------+ +----+ +----+
/ \ |
/ BLE \ | BLE
+---------+ +-----+ +---------+
| Watch A | | Pod | | Speaker |
+---------+ +-----+ +---------+
This memo uses the terms defined in the MANET Neighborhood Discovery Protocol (NHDP) [RFC6130], the Generalized MANET Packet/Message Format [RFC5444], the TLVs specified in [RFC5497], the Optimized Link State Routing protocol (OLSR) [RFC3626], and the Optimized Link State Routing protocol Version 2 (OLSRv2) [RFC7181]. This document assumes that the reader is familiar with the aforementioned MANET protocols and algorithms.¶
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] and [RFC8174] when, and only when, they appear in all capitals, as shown here.¶
The CLSR protocol operates as table driven, distance vector, proactive routing protocol exchanging topology information regularly with neighbors for mobile ad-hoc networks (MANETs). It works in a completely distributed manner without any centralized control entity. Every node in the network stores the overall network topology information in local table(s) in order to route packets hop-by-hop. Routes are immediately available when needed.¶
Network nodes periodically send Hello Messages, as shown in Figure 5, to their 1-hop neighbors to establish/maintain the neighbor relationship. After receiving the address and link information from a neighbor, the node will update its Neighbor Information Table (NIT). Each node furthermore maintains a sequence number for each neighbor to track historical progress of communication with the respective neighbors.¶
Furthermore, the hello message is used to check whether the topology information is synchronized between several neighbors or not. For this, a 'topology hash' is transmitted, calculated over ALL NITs available at a node. Consequently, receiving the same hash value from a neighbor indicates that the receiving node's topology information is in sync with this sending neighbor, while the usage of a single hash value reduces the size of the message and communication power consumption since no full topology information is sent in the hello message. As another advantage of the compact size of hello messages in our STURP (due to the avoidance of exchanging full topology information), they may be carried in the payload of link layer broadcast messages (e.g. BLE, Zigbee, WIFI) as an optimization, further improving the energy efficiency of the system.¶
Key to the 'sloppy updates' mentioned in the introduction, a 'Sync Radius' is introduced to reflect which part of the network is fully synchronized with respect to topology information. A sync radius value N indicates that all nodes within N hops from the current node share the same topology information; the calculation of the sync radius is described in more detail in section Section 5.2. As a consequence, a packet can be routed to any node within this 'radius'. With this, the sync radius value provides an easy and efficient manner to determine whether there is a need to perform a network topology refresh before launching an application/service.¶
In other words, if existing service/application communication happens within the sync radius, it is concluded that the service is not affected and thus no flooding of the network is required. Instead, the neighbor nodes merely update their own NITs, topology information and topology hash values, while the overall topology refreshing is triggered either in the next freshing cycle, or by a launch of new applications/services.¶
The protocol functionality specifies the behavior of a node participating in the network and running CLSR as a routing protocol. It covers neighbor acquisition, topology refreshing and route calculation.¶
When a node receives a hello message, it records the IP address of the neighbor into its NIT, as shown in Table 1. The NIT of a node contains the neighbor router IDs, the addresses of 1-hop neighbors, the type and cost of the link. The Table 1 provides an example illustrating that node A has 2 neighbors, B and C. The link between node A and B is bluetooth, while the link between A and C is WiFi. The cost of the link is defined based on the bandwidth capacity. For instance the cost of WiFi will be lower than the cost of bluetooth, as WiFi could provide bigger bandwidth than bluetooth.¶
| Neighbor Router ID | Neighbor Address | Link Type | Cost |
|---|---|---|---|
| B | Address B | BLE | X |
| C | Address C | WiFi | X |
Via neighbor detection, each node obtains the information of a list of 1-hop neighbors which it can communicate directly, stored in the NIT of this node.¶
Besides the NIT, each node contains a Topology Information Database (TIDB). After the exchange of the hello message, a node checks whether there is any update in the NIT table. Any change in the "Neighbor Address" column indicates a change in the local neighborhood. If it detects a new node joining, it will further exchange with the new node the created/updated NIT in order to synchronize the TIDB. The synchronization of the TIDBs between 2 neighbors will be done by exchanging the Topology Synchronization Message (TSM). The format of TSM is depicted in section Section 6.2. Once the synchronization is done, the node will update the Topology Hash Value (THV) accordingly. If it detects a node depart, it will only update the topology hash without exchanging the TSM.¶
The workflow of the neighbor detection and topology exchange is shown in the Figure 2¶
Node A Node B |----+ |----+ | | 1. node startup | | 1. node startup |<---+ |<---+ | 2. Hello Message | |-------------------------------------->| | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | Addr A| Hash(0)| Sync R.(0) | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |<--------------------------------------| | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | Addr B| Hash(0)| Sync R.(0) | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | 3. Create NIT A | 3. Create NIT B | +-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+ | |N. addr| Link | Cost | | |N. addr| Link | Cost | | +-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+ | |Addr B | BLE | XXX | | |Addr A | BLE | XXX | | +-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+ | | | 4. Create TIDB A | 4. Create TIDB B | +-+-+ | +-+-+ | | A | | | B | | +-+-+ | +-+-+ | | | 5. Topology Sync Message | |<------------------------------------->| | | | 6. Update TIDB A | 6. Update TIDB B | +-+-+ | +-+-+ | | A | | | A | | +-+-+ | +-+-+ | | B | | | B | | +-+-+ | +-+-+ | | | 7. Hello Message | |-------------------------------------->| | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | Addr A| Hash(X)| Sync R.(0) | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |<--------------------------------------| | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | Addr B| Hash(X)| Sync R.(0) | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | 8. Update Sync Radius | 8. Update Sync R. | Sync R. = 1 | Sync R. = 1 | |
step 1, node A and B start up. step 2, node A and B exchange hello messages. As there is no topology and sync radius information, both values are set to zero. step 3, upon receiving the hello message from each other, node A and B create their NITs. step 4, based on the newly created neighbor information tables, node A and B create their TIDBs. At this stage, the topology information database only contains their own addresses. step 5, node A and B exchange topology sync message... step 6, upon receiving the topology sync message from each other, node A and B updated their TIDBs. Now both TIDBs are identical, leading to the same THV. step 7, node A and B exchange hello messages with the same topology hash value Hash(X) in the next period. Since the hash values are identical, both update their sync radius to 1.¶
The periodical exchange of the hello message updates the NIT and TIDB between 1-hop neighbors. A node 2-hops away gets informed of the topology change via the THV it received. However, it may not trigger the overall network topology synchronization as long as it doesn't impact on existing applications and services. Compared with neighbor detection, the network topology synchronization is performed periodically as well, but in much slower sync cycles. When it get triggered, the nodes broadcast hello messages to exchange their THVs. The ones receive different THVs (comparing with their own) will send unicast topology sync messages (request) to all neighbors with different THV values, which respond back with their own TIDB in the form of TSM, as shown in Figure 3.¶
All nodes update their TIDBs and calculate new THVs based on received TSM messages. Hello messages will be then broadcasted with updated THVs. If the THV alters, the node continues sending unicast TSM (request) to all neighbors with different THV values until all THVs stay the same.¶
+----------------------------------+
| Start Topology Refreshing |
+----------------------------------+
|
V
+--------------------------+
| Broadcast Hello Message |
| to all neighbors |<------------------+
+--------------------------+ |
| |
V |
+-------------------------+ +--------------------------+
/ \ No | Unicast TSM to neighbors |
| THV(received) == THV(own) | --> | with different THVs |
\ / +--------------------------+
+-------------------------+
| Yes
V
+------------+
| END |
+------------+
Then hello messages will be sent out to compute the sync radius value, as shown in Figure 4 depends on the THV. Assuming node A has K neighbors (N1, N2,..., Nk), the THV is Hash(A) and the sync radius is R(A).¶
+-----------------+
| R(A) = 0 |
+-----------------+
|
V
+------------------+
| Exchange TIDB&THV|
| with neighbors |<---------------+
+------------------+ |
| |
V |
+-------------------+ No +----------+
/ for i = (1, 2...K) \ -----> | R(A) = 0 |
\ Hash(A) = Hash(Ni)? / +----------+
+-------------------+
| Yes
V
+----------------------------------------+
| R(A) = min[R(N1), R(N2),...,R(Nk)] + 1 |
+----------------------------------------+
|
V
+------------+
| END |
+------------+
From Figure 4, one can see that the calculation of the sync radius value can be accomplished by exchanging TIDB&THV only with neighbors without involving >2 hops communication.¶
The network topology synchronization can be triggered by application launch as well. A node can launch an application as long as it meets the following 2 conditions: - Its THV equals the THV from one of the neighbors - Its sync radius value is larger or equal to the number of hops between the source and the destination Otherwise, TSMs will be flooded to synchronize the network topology.¶
Each node maintains a routing table which allows it to route data, destined for the other nodes in the network. The routing table is based on the information contained in the TIDB. If the TIDB is updated, the routing table is recalculated to update the route information about each destination in the network. The route entries are recorded in the routing table in the following format:¶
1. Dest_addr, Next_addr, Link
2. Dest_addr, Next_addr, Link
3. ,, ,, ,,
¶
Each entry in the table consists of Dest_addr, Next_addr and Link. Such entry specifies that for a specific application routing towards the Dest_addr, the enxt hop is Next_addr that is reachable through the media "Link". Entries are recorded in the routing table for each destination in the network for which a route is known. All the destinations, for which a route is broken or only partially known, are not recorded in the table.¶
A node periodically exchanges the hello message with its neighbors to create/maintain the NIT. The format of the hello message is as follows:¶
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | Router Id | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Topology Hash | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | Sync Radius | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version | Type | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | Router ID | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Nonce | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | No. of Records | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Record 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ....... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Record N | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The format of the Record is as follows:¶
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length |No.of Neighbors| Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | Node ID | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbors | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Extension | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Cost | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
TBD. # IANA Considerations¶
TBD.¶