# Lightweight Path Recovery in IPv6 Internet-of-Things Systems
## 3 System Model and Problem Statement
### Problem Statement  
In the path recovery problem, a sequence consisting of the source node, the relay nodes, and the destination node for the successfully delivered packet \(k\), denoted as \(path(k)\), is supposed to be recovered. Since \(path(k)\) goes through the sink node, it can be split into two subsequences, i.e., the upstream routing path \(uppath(k)\), which comes from the source node to the sink node, and the downstream routing path \(downpath(k)\), which is from the sink node to the destination node. It is the upstream routing of all packets that ought to be recovered since it has been assumed that the upstream and downstream routing paths are mirrored and the active nodes in each collection cycle both send and receive packets. For example, as shown in Figure 4, in a certain collection cycle, while \(path(k)\) denotes the path of packet \(k\) sent from node \(N_{i}\) to node \(N_{j}\) and \(path(k^{\prime})\) denotes the path of packet \(k^{\prime}\) sent from node \(N_{j}\) to node \(N_{i}\), those two paths just form a pair of inverse order. Then, when working on path recovery at the sink node, it is only necessary to recover the path \(uppath(k)\) from node \(N_{i}\) to sink node and the path \(uppath(k^{\prime})\) from node \(N_{j}\) to sink node, respectively, to obtain \(path(k)\) and \(path(k^{\prime})\). After that, \(path(k)\) is the concatenated sequence of \(uppath(k)\) and the reverse order of \(uppath(k^{\prime})\). Our goal is to correctly recover as many paths of all packets as possible for a continuous collection period. This goal, furthermore, can be translated into recovering the uplink routing path of the packets to the side of sink node as much as possible. Figure 3: The topology of the network in a collection cycle. In each packet \(k\), some information that will be recorded by the sink node and used in our path recovery algorithm is as follows:  
* The source node \(o(k)\) and destination node \(d(k)\). These can be retrieved by the sink node based on the IPv6 address of the packet header, not requiring additional space overhead for the packet. * The parent node \(p(k)\) and grandparent node \(g(k)\). The parent node \(p(k)\) is the next hop of the source node, and the grandparent node \(g(k)\) is the next hop of \(p(k)\). To record the IDs of \(p(k)\) and \(g(k)\), an extra 4B of space is needed for a packet. The default values of \(p(k)\) and \(g(k)\) are empty. When the forwarder is the parent or grandparent node of the source node, its ID will be written into the corresponding field. * The hash value of the upstream path of packet \(k\) is denoted as \(h(k)\). It also refers to \(hash(N_{1},N_{2},...,Sink)\) where \((N_{1},N_{2},...,Sink)\) represents a series of nodes ID. We set a hash function to identify an upstream path, which requires additional 2B space for a packet. Each node forwards packet \(k\) with a small computational overhead to update the \(h(k)\), and the final \(h(k)\) received by the sink node is the hash value that records an entire upstream path. The packets with the same hash value can be considered as going through the same path. * The length of the uplink path, denoted as \(len(k)\). This can be inferred from the Hop Limit of the IPv6 header without the additional space overhead of the packet. * The timestamp \(t(k)\). This can be inferred from the packet arrival time to which the packet belongs to the collection cycle, without the additional space overhead of the packet. The performance of the path recovery algorithm can be measured by two metrics: _Accuracy_ and \(GainLossRatio\):  
* _Accuracy_. We define the _Accuracy_ of the path recovery problem as:  
\[Accuracy=\frac{Num_{correctRecovery}}{Num_{received}}, \tag{1}\]  
where \(Num_{received}\) denotes the number of all successfully communicated packets, and \(Num_{correctRecovery}\) denotes the number of all correctly recovered packets whose paths were correctly recovered. The purpose of path recovery is to improve the _Accuracy_ as much as possible.