# My Smartphone tattles: Considering Popularity of Messages in Opportunistic Data Dissemination
## 5 Keetchi Forwarding Protocol
### Keetchi Algorithm  
The Keetchi algorithm consists of a number of software modules that operate in a node, interacting with each other to optimally disseminate data in a network. Figure 3 shows the flow diagram of these modules and their interactions. The Keetchi algorithm is triggered by four stimuli that activate five different software modules through the use of three message types. The modules perform the following activities. **Cache Data:** Similar to any other OppNets forwarding protocol, Keetchi uses a _store-carry-and-forward_ mechanism to disseminate data and stores all data in a cache. Every data item in Keetchi consists of the payload itself and an additional integer representing the current estimate of the popularity of that data item at this node, referred to as the _goodness value_ of the data item. The goodness value has a range between 0 and 100, and all the data items are held in the cache sorted by descending order of this value. **Update Goodness Value:** Every data item in Keetchi that is disseminated and stored in caches carry the goodness value. When a data item (from an application or the network interface) or a user feedback (from an application) is received by Keetchi, the goodness value is updated using simple Q-Learning. The update of the goodness value is shown in Equation (1):  
\[GV_{new}=\gamma\cdot GV_{old}+(1-\gamma)\cdot GV_{r} \tag{1}\]  
Figure 2: Development of popularity of a joke over time. While the joke is very popular in Hamburg, it is less popular in Bremen and not popular globally. where \(GV_{new}\), \(GV_{old}\) and \(GV_{r}\) are the new, previous and received goodness values, respectively. The received goodness value plays the role of a reward in a Q-Learning setting and the new and old values are the new and old Q-values. The \(\gamma\) is a constant referred to as the learning constant, where higher values result in slower learning. The goodness values are the estimates of the popularity for each data item. **Determine Change Significance:** As any other forwarding protocol, Keetchi needs information from lower protocol layers to know which nodes are in a given node's neighbourhood. If all of these nodes are new neighbours, then it is worth sending them more popular items first. If they are all known, then we have already sent them the popular items and we have time to send them also less popular ones. We adopt a _fuzzified_ technique to determine whether the neighbourhood changed significantly (see Figure 4). If the change per cent is in the _fuzzy area_, the old value is kept (significant/not significant). This is important to avoid sudden fluctuations of the value, because it triggers the data sending mechanism. **Determine Data to Send:** The selection of data item to send is random and the random distribution is controlled by the significance of change. In general, if the change is significant, Keetchi will select a  
Figure 4: Fuzzified mechanism to determine the significance of change of a node’s neighbourhood. Figure 3: Flow diagram of KEETCHI consisting of a number of software modules, triggers and interactions: **(a,b)** external stimuli ; and **(c,d)** internal stimuli. These stimuli trigger the operation of KEETCHI. data item which has a higher goodness value and a data item with a lower goodness value in the case of an insignificant change. The used distribution is a Gauss-like heavy tail distribution with a moving peak, whose form is controlled by the parameter focus weight factor. The larger is this factor, the steeper is the distribution. Whenever the change is significant, the peak of the distribution is set to the highest goodness value (see Figure 5). With continuous successive insignificant changes in the neighbourhood, the peak of this distribution is moved downwards, in the direction of lower goodness values. If the distribution peak reaches the bottom of the cache, Keetchi stops sending data altogether.