3.5 Reputation overhead analysis

In this section, we study the impact the reputation mechanism has on the network, and more precisely the overhead it engenders. We show that according to the reputation update interval and the considered value of $\tau$ mathend000#, the overhead varies significantly.

3.5.1 Routing aspects

The main aspect for message exchange is to minimize the traffic overhead, as security aspects about message routing have already been studied ([BB02], [MGLB00], [FF06]). Thus, we make the assumption that messages dropping can be prevented, as rerouting can be performed.

An important aspect is then to be assured that a message is propagated to each members of the group, in order to prevent global parameters divergences. If we suppose that the routing aspects are generally solved, the principal attack can come from the source node n_m mathend000#: it sends n mathend000# message m_i mathend000#, one for each n mathend000# subsets of the group. Thus, other nodes will we have parameters divergences about node n_m mathend000#. The best solution to prevent this problem is to use broadcast or multicast messages exchanges. By using this, we are assured that a message reaches each node of the group.

3.5.2 Traffic overhead

The traffic overhead is produced by nodes that are watching other nodes, and thus produce reputation messages. As described in section 3.3, | R| mathend000# nodes are keeping a watch on a single node. We thus have n ^. | R| mathend000# reputation messages. The overhead is formulated by overhead = nb_messages ^. size(message) = nb_messages ^. ( < sub$\_layers$$\_headers$ > + reputations$\_by$$\_message$ ^. packetsize) mathend000# where packetsize mathend000# represents the size of a single reputation message. The packetsize is thus immediately proportional to of the way we code the message: packetsize = (node_id + reputation_size + signature) mathend000# where signature = 16 mathend000# bytes, node_id = IPaddress : 16 mathend000# bytes, reputation = 10 mathend000# bits

If we consider a well distributed network, we have nb_messages = n mathend000# and reputations_per message = | R| mathend000# which optimize the overhead as we only have n mathend000# sublayers headers. With the choices made in the previous section, we have | R| = 4*$\tau$ = n mathend000# at worst (with $\tau$ mathend000# = 25%).

	< sub$\_layers$$\_headers$ > mathend000#	global overhead with $\tau$ = 25% mathend000#
OLSR:	58 bytes	n . (58 + n . 34) mathend000#
AODV:	60 bytes	n . (60 + n . 34) mathend000#

In OLSR, the timer interval for TC messages , which are sent through the whole network, as for our reputation messages, is of 5 seconds. Classical comparisons and flux statistics are based on the CBR model at 512 bytes. Using this model, increase_rate = ${\frac{{60 + n \cdot 34}}{{512 \cdot seconds_{intervals}}}}$ mathend000#

The figure 3.7 illustrates the network overhead (in percent), based on this 512 bytes per seconds model. We can see that when we have reputation intervals that are of 5 (like TC) or 10 seconds, we have an increase inferior to 30%, which is satisfying, as we suppose that 25% of the nodes are malicious (using a constant number would have engender a constant overhead of ${\frac{{\vert R\vert * 34 + 60}}{{512}}}$% mathend000#).

Figure 3.7: Network overheads

[network overhead (in %) due to reputation messages]

[Network overhead (in bytes) due to reputation messages, for 5 and 10 seconds with $\tau$ = 25% mathend000#]

3.5.2.1 Messages interval determination

We can see from the figures 3.7 that the network increase is however proportional to the reputation interval. Moreover, in section 3.3.2, we have shown than based on 25 % of malicious nodes, we have to wait for 13 iterations to get the maximal reputations. So, using a reputation interval of 10 seconds or 5 seconds does have an impact on the reputation convergence. As fives seconds are used for the TC messages, the same value can be chosen for the reputation interval (or at least k ^. 5 mathend000# seconds). By using this value, it is possible to add reputation messages in TC message, which help to decrease the traffic overhead ( increase_rate = ${\frac{{n \cdot 34}}{{512 \cdot seconds_{intervals}}}}$ mathend000#) and the number of messages in the network: by adding reputation messages in TC messages, there is no sublayers overhead.

Figure 3.8: reputation information in TC messages

[impact of $\tau$ mathend000# for a reputation intervals of 10 seconds]

[Overhead (in %) due to reputation information, 5 ,10 and 15 seconds intervals, $\tau$ = 10% mathend000#]

However, the choice of the interval update (or the value of k mathend000# or k ^. 5 mathend000# seconds) can be network-dependent: the detection mechanisms may depend on other network layers. So, by using for instance k = 2 mathend000#, detection mechanisms can be performed on TC (5 seconds intervals) and HELLO (2 seconds) messages in the OLSR protocol. Moreover, as described in the figure 3.8b, the overhead produces with a 5 seconds interval is far greater than with 10 seconds (but when k mathend000# increases, the benefit become less important)

To summarize, though our mechanism can support 25% of malicious nodes (which means it can still work and that these malicious nodes can be evicted), the produced overhead show that it is better to consider $\tau$ = 10% mathend000# as the maximal supported value (figure 3.8a). Moreover, with a reputation update interval of 10 seconds, we can first let the sublayers (namely OLSR) perform checks and thus enforce the reputation mechanism at their levels. These 10 seconds of intervals let use extend the OLSR TC messages in order to add reputation information. This does not significantly reduce the produced overhead, but it decreaes the number of broadcasted packets, which minimize the routing operations. A constant tau mathend000# value would produce better results as the overhead would be constant. However, the group would be limited by a minimal size : minimal$\_size$ = ${\frac{{tau\_constant}}{{tau\_max\_percent}}}$ mathend000# ( ${\frac{{tau}}{{n}}}$ $\leq$ tau$\_max$$\_percent$ mathend000#), where tau$\_max$$\_percent$ mathend000# is the value used to determine the system parameters.