# Lightweight Path Recovery in IPv6 Internet-of-Things Systems
## 4 Design of LiPa  
### Solution Overview  
Our proposed algorithm consists of two parts, i.e., path information encoding during packet delivery and path recovery of the received information at the server-side.  
During packet delivery, the information required for path recovery is passed along the uplink path from the source node to the sink node. The information needed in packet \(k\) is as follows: the source node \(o(k)\) and the destination node \(d(k)\), which can be looked up by the sink node based on the IP address in the IPv6 header; the length of the uplink path \(len(k)\); the timestamp \(t(k)\), which can be directly inferred from the IPv6 header; and three additional data--the parent node \(p(k)\) and grandparent node \(g(k)\) combined with the hash of the uplink path \(h(k)\).  
For the parent node, \(p(k)\), it will take 2 bytes of the packet space to store the ID of the parent node. We specify that when a forwarder finds \(p(k)\) empty in a packet, the forwarder is the parent node and will write its ID into \(p(k)\). For the grandparent node \(g(k)\), the space of 2 bytes of the packet is occupied to store the ID of the grandparent node. Analogously, when \(p(k)\) is not empty and \(g(k)\) is empty, the forwarder is the grandparent node and needs to write its ID to \(g(k)\). Note that once \(p(k)\) or \(g(k)\) are filled in, their value will not be changed. In addition, if the parent node or grandparent node is already a sink node, the corresponding value will be all zeros. For the upstream path \(h(k)\), 2 bytes of overhead is used to store the hash value of the route, which is continuously updated during the transmission. Starting from the source node, for each node of such an upstream route, they update the hash value by the following functions [12]:  
\[h_{i}(k)=h_{i-1}(k)\oplus f_{ID}(i) \tag{5}\]  
based on their ID value, where  
\[f_{ID}(i)=(ID\times\alpha<<\lceil log_{2}ID\rceil)\ mod\ 2^{m}, \tag{6}\]  
\[h_{1}(k)=f_{ID}(1). \tag{7}\]We set \(m=16\), i.e., the number of bits occupied by this hash is 16, and the space size is 2 bytes. Note that LiPa is used to extract the full path information by measurements of the packet traces. It works independently from the routing protocols. The 6 bytes overhead, i.e., the \(p(k)\), \(g(k)\), and \(h(k)\) fields, are directly appended to the packet to participate in the transmission, rather than an additional packet being routed through to recover the path.  
For server-side information processing, the above packet information is used for uplink path recovery within the sliding observation window to recover the point-to-point routing path through the mirroring feature. Specifically, the required information mentioned above is recorded when the packet arrives at the sink node through the uplink; then, the packet is forwarded following the downlink to the destination node. We set a sliding window of the following size:  
\[\tau=[\frac{1}{Ratio_{active}}], \tag{8}\]  
where \(Ratio_{active}\) is the proportion of active nodes in the network. At time \(t\), the sink node will recover all packets' paths in the period \([t-\tau,t]\). For path recovery within this sliding window, the possible correlations in different paths are explored, starting from the short one-hop and two-hop paths based on the information of the parent and grandparent nodes and then iteratively solving for more unknown paths. To ensure whether the recovered paths are correct, the hash value of the uplink is needed.  
During the running of system, the operation of LiPa is divided into two operation parts. (1) For sensor nodes, the information encoded during packet delivery is updated by every forwarder, and their IDs are attached to headers when they work as the first-hop or second-hop forwarder of a packet. (2) For the sink node which collects packets from all sensor nodes, the received packet information can be merged to perform the recovery algorithm in the style of online (real-time) or offline.