Encoding Vertices in Rectangular Grid Graphs with Eliminating Errors

Abstract

An undirected graph G = (V,E) where V is a set of vertices and E =V ×V is the set of pair of adjacent edges or in other words it is the set of edges. In theory, a graph can be a model of a message delivery in a network. We assume that the computer network has a particular shape which we call as a rectangular grid and there is a computer on each vertex in the graph. Each vertex v∈V is labelled by a subset of universal set U that models the header of a message sent between two distinct computers in G. We present a way to encode routes in the graph G by encoding all distinct vertices u,v ∈V in the routes. We aim that these codes prevent errors denoted by false positives, therefore, results in a more efficient use of network resources.

Keywords

• Computer Network
• False Positive
• Rectangular grid
• Undirected Graph

References

1. [1] B. H. Bloom, “Space/time trade-offs in hash coding with allowable errors,” Communications of the ACM, vol. 13, no. 7, 1970, pp. 422–426.
2. [2]Y. Lu, B. Prabhakar, and F. Bonomi, “Perfect hashing for network applications,” in Information Theory, 2006 IEEE International Symposium on. IEEE, 2006, pp. 2774–2778.
3. [3] C. E. Rothenberg, C. A. B. Macapuna, M. F. Magalhaes, F. L. Verdi, ˜ and A. Wiesmaier, “In-packet bloom filters: Design and networking applications,” Computer Networks, vol. 55, no. 6, 2011, pp. 1364–1378.
4. [4] L. Carrea, A. Vernitski, and M. Reed, “Yes-no bloom filter: A way of representing sets with fewer false positives for in-packet path encoding,” Arxiv eprint arXiv:1603.01060v1, 2016.
5. [5] X. Yang, A. Vernitski, and L. Carrea, “An approximate dynamic programming approach for improving accuracy of lossy data compression by bloom filters,” Europen Jornal of Operational Research, Elsevier, vol. 252, no.3, 2016 ,pp. 985-994
6. [6] A. Broder and M. Mitzenmacher, “Network applications of bloom filters: A survey,” Internet mathematics, vol. 1, no. 4, 2004, pp. 485–509.
7. [7]Vernitski A. Reed M. Carrea, L. Optimized hash for network path encoding with minimized false positives. Computer networks, 58:180–191, 2014.
8. [8]Gokce C. Kayaturan and Alexei Vernitski. “A way of eliminating errors when using bloom filters for routing in computer networks”. In Networks, ICN 2016. The Fifteenth International Conference on, pages 52–57. IARIA, 2016.

9. [9] X. Li, L. Peng, and C. Zhang, “Application of bloom filter in grid information service,” in Multimedia Information Networking and Security (MINES), 2010 International Conference on. IEEE, 2010, pp. 866–870.
10. [10] K. Czajkowski, S. Fitzgerald, I. Foster, and C. Kesselman, “Grid information services for distributed resource sharing,” in High Performance Distributed Computing, 2001. Proceedings. 10th IEEE International Symposium on. IEEE, 2001, pp. 181–194.
11. [11] Li Fan, Pei Cao, Jussara Almeida, and Andrei Z Broder. Summary cache: a scalable wide-area web cache sharing protocol. IEEE/ACM Transactions on Networking (TON), 8(3):281–293, 2000.
12. [12] Michael Mitzenmacher. Compressed bloom filters. IEEE/ACM Transactions on Networking (TON), 10(5):604–612, 2002.