Evaluation of Hash Functions for Multipoint Sampling in IP Networks

Diploma Thesis from the year 2008 in the subject Computer Science - Applied, grade: 1, Technical University of Berlin, language: English, abstract: Network Measurements play an essential role in operating and developing today'sInternet. A variety of measurement applications demand for multipointnetwork measurements, e.g. service providers need to validate their delay guaranteesfrom Service Level Agreements and network engineers have incentives totrack where packets are changed, reordered, lost or delayed. Multipoint measurementscreate an immense amount of measurement data which demands for highresource measurement infrastructure. Data selection techniques, like samplingand filtering, provide efficient solutions for reducing resource consumption whilestill maintaining sufficient information about the metrics of interest. But not allselection techniques are suitable for multipoint measurements; only deterministic filtering allows a synchronized selection of packets at multiple observation points.Nevertheless a fillter bases its selection decision on the packet content and henceis suspect to bias, i.e the selected subset is not representative for the whole population.Hash-based selection is a filtering method that tries to emulate randomselection in order to obtain a representative sample for accurate estimations oftraffic characteristics.The subject of the thesis is to assess which hash function and which packet contentshould be used for hash-based selection to obtain a seemingly random andunbiased selection of packets. This thesis empirically analyzes 25 hash functionsand different packet content combinations on their suitability for hash-basedselection. Experiments are based on a collection of 7 real traffic groups fromdifferent networks.