State-space Analysis of the Interval Merging Binary Tree
Acta Polytechnica Hungarica · 2019
In the course of transmission through networks a particular packet, like a Storm tuple or a performance/fault management (PM/FM) report in XML format of an Operation Support System (OSS) application, data loss/out of order arrival/duplication phenomena may cause the packet not to arrive at the destination, arrive exactly once or to arrive in several copies.These anomalies have to be handled both on the lower and higher level network or application layers to an extent depending on the later usage.The efficiency of handling depends on the applied data structures.To detect packet loss and duplication, a special, tree-like data structure was proposed earlier, the Interval Merging Binary Tree (IMBT).We analyzed IMBT from several perspectives and we compared its performance with other well-known tree variants, under various circumstances.However, in contrast to a completely balanced binary search tree, it is impossible to associate to the newly developed data structure a one dimensional function, dependent on the number of input keys, to determine for instance the average cost of an operation.Nevertheless, for further development, it is essential in case of any data structure, to determine the actual boundaries of its applicability.In this contribution we explore the state space of IMBT in order to be able to classify the data structure regarding the input pattern during the later performance analysis.We used in the modeling Fibonacci sequences, bipartite multi-graphs and combination tables.