# An Efficient Probe-Based Routing for Content-Centric Networking
## 3 Design and Description of Our Proposal
### Routing Complexity
#### 3.3.2 Time Overhead  
Algorithms 1 and 2 demonstrate our approach of processing interest packets and data packets, respectively, which were modified from basic CCN. The following analyzes the additional time complexity caused by our modifications. Algorithm 1 has three additional parts compared to CCN, which are as follows:  
1. Check the probe in CS (see lines 7-9).
2. Add a probe (see lines 13-18).
3. Select outgoing interfaces for interest packets (see lines 19-24).  
```
OnInterval (interest) // Check PIT entries for matching interest. 0 means not found. ifPIT (interest) == 0 then
2 Create a PIT entry for interest
3 else merge interest to PIT, drop interest and break
4 endif
5 data = Create Data () // Check CS entries for matching interest. 1 means found. ifCS (interest)!=0 then
6// Check CS entries for matching probe. ifCS (interest.probe)!=0 then
7 add routerID to probe-response
8 add probe-response to data
9 add content to data
10
11 Returndata
12 endif
13// If no matching interest in CS, then continue to check CS entries for matching probe. elseifCS (interest.probe)!=0 then
14 add routerID to probe-response
15// Check ifinterest needs to add a probe. elseifinterest.probe == 0 then
16// select a probe in PIT or FIB
17 name = find an entry in PIT (max popular) or FIB (max cost)
18 add name to interest.probe
19
20 endif
21// outgoing interface = FIB (min cost)
22// Get routerID sequentially from FIB entry for each routerID in FIB:
23// Get the cost of routerID from SPT and find routerID with lowest cost
24 if SPT (routerID)!= mincost
25 mincost = SPT (routerID)
26 outgoing interface = routerID
27
28 endif
29 Forward interest
30 endif
31 endif
```  
**Algorithm 1** Processing Interest Packet  
The worst-case time complexity of checking the probe in CS is O(\(N_{CS}\)), where \(N_{CS}\) is the cache size of CS. The time complexity of the probe selection policy is O(\(N_{rt}\)), where \(N_{rt}\) is the size of the routing table. In this paper, \(N_{rt}\) denotes either the FIB or PIT size, as indicated in line 16. Line 19 is the basic CCN outgoing interface selection, with a time complexity of O(\(N_{FIB}\)), where \(N_{FIB}\) is the FIB cache size. Line 20-24 is the modified outgoing interface selection of our approach. The time complexity is O(\(N_{FIB}*N_{SPT}\)). Our approach traverses the SPT in O(\(N_{SPT}\)), where \(N_{SPT}\) is the number of entries. SPT is to record the cost and interface with the shortest path to each other router in the network so that the number of entries equals the number of routers \(N_{R}\).  
In comparison to CCN, Algorithm 2 has one additional component: updating FIB via _probe-response_ (see lines 1-6). The worst-case time complexity for checking the probe in FIB is O(\(N_{\text{FIB}}\)). For qualitative analysis, compared to the basic CCN, the additional time complexity of our approach is O(\(N_{CS}+N_{nt}+N_{\text{FIB}}*N_{SPT}\)) and O(\(N_{\text{FIB}}\)) on processing interest packets and data packets, respectively. In addition to online time complexity, there is an offline Breadth-First Search (BFS) that is used to establish SPT and has a time complexity of O(\(N_{R}+N_{E}\)), where \(N_{E}\) is the number of network edges. However, our experiments demonstrate that our approach outperforms the basic CCN in terms of the number of timeout interest packets and average response time. The details are described in Section 4.4.4.