# A Cognitive Anycast Routing Method for Delay-Tolerant Networks
## 3 Anycast Routing
### Anycast CSG Routing
#### 3.2.2 Optimal Anycast Bundle Forwarding  
Each unicast or anycast destination is assigned a separated CNC at any CSG gateway \(i\). The reward-shaping method used by the CSG [16] to estimate the cost \(C\) for each routing decision toward destination \(d\) (i.e., the negative reward) requires three terms:  
\[C=T_{i,j}+T_{j,d}+D_{i,d} \tag{2}\]  
where \(T_{i,j}\), is the average bundle _communication time_ over the \(i,j\) link, \(T_{j,d}\) is the communication time from gateway \(j\) to destination \(d\), and \(D_{i,d}\) is the expected _dormant time_, i.e., the total disruption time of all links along the path. The first two terms include the radiation and buffering times but not the contribution of link disruptions. It is convenient to define \(T_{i,d}=T_{i,j}+T_{j,d}\). The bundle transmission time to the neighbor \(j\) can be measured after the event either by the convergence layer or through the single-hop bundle acknowledgement that is sent by the neighbor. In either case, gateway \(i\) keeps the average observation using: \(T_{i,j}\leftarrow(1-\alpha)T_{i,j}+\alpha t_{i,j}\), where \(t_{i,j}\) is the new measurement. The single-hop bundle acknowledgements are also used by neighbor \(j\) to share its own estimation \(T_{j,d}\) with the preceding node. The process repeats along the path with \(T_{d,d}=0\). Gateway \(i\) stores the value \(T_{j,d}\) for the next calculation. As with unicast destinations, the gateway determines the dormant time introduced by link disruptions by analyzing the contact plan. The contact plan is given as a list of tuples \((t_{s},t_{e},n_{s},t_{e},f)\), where \(t_{s}\) and \(t_{e}\) are the start and end times of the contact between nodes \(n_{s}\) and \(n_{e}\) with expected channel features \(f\). The latter term is ignored in this discussion for simplicity. The contact plan is updated by replacing \(n_{e}\gets a\). The feasible paths are then calculated with respect to \(a\) (i.e., considering \(a\) as a _supernode_) using Algorithm 3 and after defining the graph from the contact plan with the procedures indicated by Algorithms 1 and 2. Algorithms 2 and 3 are identical to the one used for unicast addresses except for the last step of Algorithm 3. The time complexity of the algorithms is quadratic in the size of the contact plan. ```
1:procedurePreparePlan(\(P^{\prime},t,n_{s},a,A\))\(\triangleright\)\(P^{\prime}\): contact plan, \(t\): wall time, \(n_{s}\): source, \(a\): anycast identifier, \(A\): anycast group
2:\(P\leftarrow\) [ empty list ]
3:\(P\gets P+(n_{s},n_{s},t,\infty)\)\(\triangleright\) append source contact
4:\(P\gets P+(a,a,t,\infty)\)\(\triangleright\) and destination contact
5:for all\((n_{i},n_{j},t_{s},t_{e})\in P^{\prime}\)do
6:if\(t_{e}<t\)then
7: continue\(\triangleright\) skip this entry
8:endif
9:if\(t_{s}<t\)then
10:\(t_{s}\gets t\)
11:endif
12:if\(n_{j}\in A\)then
13:\(n_{j}\gets a\)
14:endif
15:\(P\gets P+(n_{i},n_{j},t_{s},t_{e})\)\(\triangleright\) append entry
16:endfor
17:return\(P\)
18:endprocedure
```  
**Algorithm 1** Prepare contact plan. The last step of Algorithm 3 filters the routes so that the list to be returned only includes as the next hop the optimal neighbor \(j^{*}\) (as selected by the SNN) and the learning process is done with reference to that node. Cost \(C\) is given by the lowest value \(\tau\) that is returned by Algorithm 3. The cost value is then used to adjust the weights of the SNN as defined by the learning method. Additionally, a simple extension needs to be added to the normal processing of incoming bundles. When a gateway \(k\) receives a new bundle with destination address \(d\), it needs to check for anycast group membership when \(d\) is an anycast identifier (\(a=k\)) (or \(k\in A\) with the other semantic). If so, it passes the bundle to the upper layer.