Return to search

Optimised probabilistic data structures for forwarding in information centric networking

In this thesis, a probabilistic approach to the problem of packet forwarding in information centric networks is analysed and further developed. This type of networks are based on information identifiers rather than on the traditional host addresses. The approach is compact forwarding where the Bloom filter is the key method for aggregating forwarding information that allows moving packets at line speed labelled with fiat identifiers. The Bloom filter reduces state at the nodes, simplifies multicast delivery and introduces new trade-offs in the traditional routing and forwarding design space. However) it is a lassy method which produces some potential bandwidth penalties, loops, packet storms, and security issues due to false positives. This thesis focuses on false posit ive control for the probabilistic in-packet forwarding method and proposes two approaches either to reduce false positives or to exploit them in a useful way. One approach consists of a mechanism to carefully select the number of hash functions to use to generate the Bloom filter, The mechanism on average offers the minimum false positive occurrences depending on the traffic along the links. The other approach is a variation of the Bloom filter, the optihash, that can give better performance with respect to the Bloom filter at a cost of slightly more processing. The optihash is constructed with a family of functions that allows an optimisation which can be performed according to different metrics. Two general metrics are proposed in detail and some other, appJicationspeCific, are explored for in-packet forwarding techniques in different types of networks. The time complexity/false positive trade-off is thoroughly investigated and the evaluation of the optihasb as an alternative to the Bloom filter is performed for in-packet compact forwarding.
Date January 2013
CreatorsCarrea, Laura
PublisherUniversity of Essex
Source SetsEthos UK
Detected LanguageEnglish
TypeElectronic Thesis or Dissertation

Page generated in 0.0033 seconds