Error Elimination From Bloom Filters in Computer Networks Represented by Graphs

Abstract

An undirected mathematical graph, $G = (V, E)$ where $V$ is a set of vertices and $E = V \times V$ is the set of edges, can model a computer network. By this consideration we search for solutions to real computer network problems with a theoretical approach. This approach is based on labelling each edge by a subset of a universal set, and then encoding a path as the union of the labels of its edges. We label each vertex $v \in V$ by using a subset of universal set $U$, then we present a way to encode shortest paths in the graph $G$ by using a way optimizing the data. By mathematical approach, it is provable that the labelling method we introduced eliminates the errors from the shortest paths in the graph. We aim to obtain the results in a more efficient use of network resources and to reduce network traffic. This shows how our theoretical approach works in real world network systems.

Keywords

• Computer network
• Edge labelling
• Shortest path
• Undirected graph

References

1. [1] M. X. Punithan, S. Seo, King’s graph-based neighbor-vehicle mapping framework, IEEE trans Intell Transp Syst, 14 (2013), 1313–1330.
2. [2] O. Favaron, G. H. Fricke, D. Pritikin, J. Puech, Irredundance and domination in kings graphs, Discrete Math. Elsevier, 262 (2003), 131–147 .
3. [3] E. J. Ionascu, D. Pritikin, S. E. Wright, k-Dependence and domination in kings graphs, Amer. Math. Monthly, 115 (2008), 820–836.
4. [4] R. Dantas, F. Havet, R. M. Sampaio, Minimum density of identifying codes of king grids, Discrete Math., 341 (2018), 2708–2719.
5. [5] G. C. Kayaturan, Representing Shortest Paths in Graphs Using Bloom Filters without False Positives and Applications to Routing in Computer Networks, Ph.D thesis, Univeristy of Essex, UK, 2018.
6. [6] B. H. Bloom, Space/time trade-offs in hash coding with allowable errors, Commun. ACM, 13 (1970), 422–426.
7. [7] Y. Lu, B. Prabhakar, F. Bonomi, Perfect hashing for network applications, IEEE Int. Symp. Inf. Theory - Proc., (2006), 2774–2778.
8. [8] C. E. Rothenberg, C. Macapuna, B. Alberto, M. F. Magalh˜aes, F. L. Verdi, A. Wiesmaier, In-packet Bloom filters: Design and networking applications, Comput. Netw., Elsevier, 55 (2011), 1364–1378.

9. [9] X. Yang, A. Vernitski, L. Carrea, An approximate dynamic programming approach for improving accuracy of lossy data compression by Bloom filters, Eur. J. Oper. Res. 252 (2016), 985–994.
10. [10] A. Saha, N. Sengupta, M. Ramanath, Reachability in large graphs using bloom filters, Proceedings - 2019 IEEE Trans Knowl Data Eng, ICDEW 2019, (2019), 217–224.
11. [11] M. Mitzenmacher, Compressed bloom filters, IEEE ACM Trans Netw., 10 (2002), 604–612.
12. [12] A. Broder, M. Mitzenmacher, Network applications of bloom filters: A survey, Internet Math., Taylor & Francis , 1 (2004), 485–509.
13. [13] L. Carrea, A. Vernitski, M. Reed, Optimized hash for network path encoding with minimized false positives, Comput. Netw., 58 (2014), 180–191.
14. [14] G. C. Kayaturan, A. Vernitski, A Way of eliminating errors when using Bloom filters for routing in computer networks, Comput. Electr. Eng. (CEEC), 2016 8th, (2016), 95–100.
15. [15] G. C. Kayaturan, A. Vernitski, Routing in hexagonal computer networks: How to present paths by Bloom filters without false positives, Netw., ICN2016. , (2016), 52–57.
16. [16] G. C. Kayaturan, A. Vernitski, Encoding shortest paths in triangular grids for delivery without errors, Proceedings - ICFNDS, (2017), 7.
17. [17] S. Tarkoma, C. E. Rothenberg, E. Lagerspetz, Theory and practice of bloom filters for distributed systems, IEEE Commun. Surv. Tutor., 14, (2012), 131–155.