# A Novel Multipath Transmission Scheme for Information-Centric Networking
## 4 Path Management
### Path Selection  
Some studies [41] have shown that only a small number of relay nodes can provide optimal relay paths for most end-to-end transmission pairs, and these nodes usually have high betweenness centrality. Therefore, we make some ICN routers with high betweenness centrality register their NA-MPSID relationship with the NRS. Betweenness centrality [42] of a node \(i\) is the sum of the fraction of all-pairs shortest paths that pass through \(i\), which is denoted as follows:  
\[BC(i)=\sum_{s,t\in V}\frac{\sigma_{st}(i)}{\sigma_{st}} \tag{1}\]  
where \(V\) is the set of nodes in topology, \(\sigma_{st}\) denotes the number of shortest paths from \(s\) to \(t\), and \(\sigma_{st}(i)\) is the number of shortest paths from \(s\) to \(t\) that go through \(i\). After obtaining the NA list of the relay nodes by querying the NRS with the MPSID, the edge router needs to select several appropriate NAs from the NA list to form the initial multipath. In [43], the authors point out that relay node selection is an NP-hard problem. Although some node selection algorithms have been proposed in the overlay network [13; 15; 16], their performance is poor in terms of robustness or scalability. The RON [13] and other similar systems require the relay nodes to probe the entire network and periodically exchange probe information, and are hence not scalable. OHSR [15] adopts a random selection strategy and thus is scalable, but it is hard to avoid poor relay nodes. PPRR [16] can maintain a top set of optional relay nodes for each destination, thus reducing the probing overhead. However, the probe overhead is still not negligible as the number of relay nodes increases. Therefore, we need a more scalable way to discover available relay paths. To reduce the overhead and avoid a poor selection, we let the edge router maintain an alternate path state table (_PST_). The _PST_ records the NAs of the relay nodes and the corresponding transmission success rate (_TSR_). The _TSR_ is obtained according to the success rate of a relay node providing data relay service in the past period of time, so it can reflect the relay node's ability to provide multipath transmission service to a certain extent. The _TSR_ can be calculated as follows:  
\[TSR_{i}=\frac{s_{i}}{s_{i}+f_{i}} \tag{2}\]  
where \(s_{i}\) and \(f_{i}\) represent the number of times that the path formed by relay node \(i\) is congested and not congested, respectively. \(s_{i}\) and \(f_{i}\) are the results of long-term historical observations. If the path formed by the selected relay node \(i\) is not congested during one transmission, the corresponding \(s_{i}\) is increased by one; that is,  
\[s_{i}=s_{i}+1 \tag{3}\]  
Conversely, if the path is congested during transmission, the corresponding \(f_{i}\) is decreased by 1; that is,  
\[f_{i}=f_{i}-1 \tag{4}\]  
In this way, the node's _TSR_ can be calculated and updated during every transmission. The larger the _TSR_ of a relay node, the higher the probability of it being selected. The rationale for this method is that a relay node that previously provided a sufficiently well-conditioned path to various destinations is likely be selected again with higher probability in the future [15]. There may be some ICN routers registering or deregistering with the MPSID on the NRS; therefore, the edge routers need to update the NA entries of the _PST_ according to the NA list of the relay nodes obtained from the NRS. In addition, if a relay node has not been selected for a long time or a new relay node is added to the _PST_, its _TSR_ will be automatically set to the default value. The _PST_ has a simple structure and its update does not require additional probe overhead, so it is scalable. The _PST_ can provide prior knowledge, and thus can reduce the difficulty and overhead of node selection. Suppose that \(P\) is the set of alternative nodes obtained from the NRS and the set of selected nodes is denoted as \(S\).