Mahdı ABBASI, Mılad RAFIEE, Mohammad R. KHOSRAVI

8452

Investigating the efficiency of multithreading application programming interfaces for parallel packet classification in wireless sensor networks

This paper investigates the most appropriate application programming interface API that best accelerates the flow-based applications on the wireless sensor networks WSNs . Each WSN include many sensor nodes which have limited resources. These sensor nodes are connected together using base stations. The base stations are commonly network systems with conventional processors which are responsible for handling a large amount of communicated data in flows of network packets. For this purpose, classification of the communicated packets is considered the primary process in such systems. With the advent of high-performance multicore processors, developers in the network industry have considered these processors as a striking choice for implementing a wide range of flow-based wireless sensor networking applications. The main challenge in this field is choosing and exploiting an API which best allows multithreading; i.e. one which maximally hides the latency of performing complex operations by threads and increases the overall efficiency of the cores. This paper assesses the efficiency of Thread, Open Multiprocessing, and Threading Building Blocks TBB libraries in multithread implementation of set-pruning and grid-of-tries packet classification algorithms on dual-core and quad-core processors. In all cases, the speed and throughput of all parallel versions of the classification algorithms are much more than the corresponding serial versions. Moreover, for parallel classification of a sufficiently large number of packets by both classification algorithms, TBB library results in higher throughput and performance than the other libraries due to its automatic scheduling and internal task stealing mechanism.
Keywords:

Packet Classification, Multi-threading, Thread, Open Multiprocessing Threading Building Blocks, wireless sensor network, efficiency,

PDF

___

  • [1] Belfkih A, Duvallet C, Sadeg B. A survey on wireless sensor network databases. Wireless Networks 2019; 25(8): 4921-4946.
  • [2] Menon VG, Pathrose PJ, Priya J. Ensuring reliable communication in disaster recovery operations with reliable routing technique. Mobile Information Systems 2016; 1: 1-10.
  • [3] Prathap PJ. Comparative analysis of opportunistic routing protocols for underwater acoustic sensor networks. In: International Conference on Emerging Technological Trends (ICETT); Kollam, India; 2016. pp. 1-5.
  • [4] Borges LM, Velez FJ, Lebres AS. Survey on the characterization and classification of wireless sensor network applications. IEEE Communications Surveys & Tutorials 2014; 16(4): 1860-1890.
  • [5] Vukobratovic D, Stankovic L, Stankovic V. Performance analysis of node cooperation with network coding in wireless sensor networks. In: 4th IFIP International Conference on New Technologies, Mobility and Security; Paris, France; 2011. pp. 1-4.
  • [6] Stankovic L, Stankovic V. Cooperative network-coding system for wireless sensor networks. IET communications 2012; 6(3): 344-352.
  • [7] Kumar S, Chaurasiya VK. A strategy for elimination of data redundancy in internet of things (IoT) based wireless sensor network (wsn). IEEE Systems Journal 2018; 13(2): 1650-1657.
  • [8] Wan S, Gu Z, Ni Q. Cognitive computing and wireless communications on the edge for healthcare service robots. Computer Communications 2019; 149(1): 99-106.
  • [9] Wan S, Zhao Y, Wang T, Gu Z, Abbasi QH, Choo KKR. Multi-dimensional data indexing and range query processing via Voronoi diagram for internet of things. Future Generation Computer Systems 2019; 91(1): 382-391.
  • [10] Salma B, Youssef B, Abderrahim H. Software Defined Networking Based for Improved Wireless Sensor Network. In: Ezziyyani M (editors). International Conference on Artificial Intelligence and Symbolic Computation. Cham, Switzerland: Springer, 2019, pp. 246-258.
  • [11] Wee J, Choi JG, Pak W. Wildcard fields-based partitioning for fast and scalable packet classification in vehicle-toeverything. Sensors 2019; 19(11): 2563.
  • [12] Attar H, Alhihi M, Zhao B, Stankovic L. Network Coding Hard and Soft Decision Behavior over the Physical Payer Using PUMTC. In: International Conference on Advances in Computing and Communication Engineering (ICACCE); Paris, France; 2018, pp. 471-474.
  • [13] Prathap PJ. Opportunistic routing with virtual coordinates to handle communication voids in mobile ad hoc networks. In: Thampi S, Bandyopadhyay S, Krishnan S, Li KC, Mosin S, Ma M (editors). Advances in Signal Processing and Intelligent Recognition Systems. Cham: Springer, 2016, pp. 323-334.
  • [14] Rabileh AA, Bakar KAA, Mohamed RR, Mohamad MA. Enhanced buffer management policy and packet prioritization for wireless sensor network. International Journal on Advanced Science, Engineering and Information Technology 2018; 8(4): 1770-1776.
  • [15] Chithaluru P, Prakash R, Srivastava S. WSN Structure Based on SDN. In: Dumka A (editors). Innovations in Software-Defined Networking and Network Functions Virtualization. India: IGI Global, 2018, pp. 240-253.
  • [16] Rao VS, Dakshayini M. SDN Based Energy Efficient Mechanism for Constrained Networks. Procedia computer science 2018; 143(1): 341-348.
  • [17] Wan S, Li X, Xue Y, Lin W, Xu X. Efficient computation offloading for Internet of Vehicles in edge computingassisted 5G networks. The Journal of Supercomputing; 2019; 1-30.
  • [18] Inoue T, Mano T, Mizutani K, Minato Si, Akashi O. Fast packet classification algorithm for network-wide forwarding behaviors. Computer Communications 2018; 116(1): 101-117.
  • [19] Abbasi M, Tahouri R, Rafiee M. Enhancing the performance of the aggregated bit vector algorithm in network packet classification using GPU. PeerJ Computer Science 2019; 5(1): e185.
  • [20] Taylor DE. Survey and taxonomy of packet classification techniques. ACM Computing Surveys (CSUR) 2005; 37(3): 238-275.
  • [21] Rafiee M, Abbasi M. Pruned Kd-tree: a memory-efficient algorithm for multi-field packet classification. SN Applied Sciences 2019; 1(12): 1537.
  • [22] Nayyar A, Mahapatra B. Effective Classification and Handling of Incoming Data Packets in Mobile Ad Hoc Networks (MANETs) Using Random Forest Ensemble Technique (RF/ET). In: Sharma N, Chakrabarti A, Balas V (editors). Data Management, Analytics and Innovation. Singapore: Springer, 2020, 1016(1): pp. 431-444.
  • [23] Gao Z, Xuan HZ, Zhang H, Wan S, Choo KKR. Adaptive fusion and category-level dictionary learning model for multi-view human action recognition. IEEE Internet of Things Journal 2019; 6(6): 9280-9293.
  • [24] Rajkamal R, Ranjan PV. Packet classification for network processors in wsn traffic using ann. In: 6th IEEE International Conference on Industrial Informatics; Daejeon, South Korea; 2008, pp. 707-710.
  • [25] Xianyang F. Design and implementation of QoS routing protocol for wireless sensor network. In: Fourth International Conference on Digital Manufacturing & Automation; Qingdao, China; 2013, pp. 428-431.
  • [26] Letswamotse BB, Malekian R, Chen CY, Modieginyane KM. Software defined wireless sensor networks (SDWSN): a review on efficient resources, applications and technologies. Journal of Internet Technology 2018; 19(5): 1303-1313.
  • [27] Farhan L, Kharel R, Kaiwartya O, Hammoudeh M, Adebisi B. Towards green computing for Internet of things: Energy oriented path and message scheduling approach. Sustainable Cities and Society 2018; 38(1): 195-204.
  • [28] Modieginyane KM, Letswamotse BB, Malekian R, Abu-Mahfouz AM. Software defined wireless sensor networks application opportunities for efficient network management: A survey. Computers & Electrical Engineering 2018; 66(1): 274-287.
  • [29] Kim CG, Kim JG, Lee DH. Optimizing image processing on multi-core CPUs with Intel parallel programming technologies. Multimedia tools and applications 2014; 68(2): 237-251.
  • [30] Reinders J. Intel threading building blocks: Outfitting C++ for multi-core processor parallelism. O’Reilly Media Inc, 2007.
  • [31] Zhou S, Qu YR, Prasanna VK. Multi-core implementation of decomposition-based packet classification algorithms. In: Malyshkin V (editors). International Conference on Parallel Computing Technologies. Berlin: Springer, 2013, pp. 105-119.
  • [32] Wu X, Taylor V. Performance modeling of hybrid MPI/OpenMP scientific applications on large-scale multicore supercomputers. Journal of Computer and System Sciences 2013; 79(8): 1256-1268.
  • [33] Memeti S, Pllana S. PAPA: A parallel programming assistant powered by IBM Watson cognitive computing technology. Journal of computational science 2018; 26(1): 275-284.
  • [34] Abbasi M, Rafiee M, A calibrated asymptotic framework for analyzing packet classification algorithms on GPUs. The Journal of Supercomputing 2019; 6574-6611.
  • [35] Rafiee M, Abbasi M, Nassiri M, An Efficient Method for Parallel Implementation of H-Trie Packet Classification Algorithm on GPU. Tabriz Journal of Electrical Engineering 2016; 46(3): 181-196.
  • [36] Lim H, Lee S, Swartzlander Jr. A new hierarchical packet classification algorithm. Computer Networks 2012; 56(13): 3010-3022.
  • [37] Batty M, Memarian K, Owens S, Sarkar S, Sewell P. Clarifying and compiling C/C++ concurrency: from C++ 11 to POWER. ACM SIGPLAN Notices 2012; 47(1): 509-520.
  • [38] Stroustrup B. A Tour of C++. Addison-Wesley Professional, 2013.
  • [39] Wolf F, Psaroudakis I, May N, Ailamaki A, Sattler KU. Extending database task schedulers for multi-threaded application code. In: Proceedings of the 27th International Conference on Scientific and Statistical Database Management: ACM; La Jolla, California; 2015, pp. 1-12.
  • [40] Kim W, Voss M. Multicore desktop programming with intel threading building blocks. IEEE software 2010; 28(1): 23-31.
  • [41] Pong F, Tzeng NF. HaRP: rapid packet classification via hashing round-down prefixes. IEEE Transactions on Parallel & Distributed Systems 2010; 22(7): 1105-1119.
  • [42] Qu YR, Zhang HH, Zhou S, Prasanna VK. Optimizing many-field packet classification on FPGA, multi-core general purpose processor, and GPU. In: Architectures for Networking and Communications Systems (ANCS): ACM/IEEE Symposium; Oakland, CA, USA; 2015, pp. 87-98.
  • [43] Taylor DE, Turner JS. Classbench: A packet classification benchmark. IEEE/ACM Transactions on Networking (ton) 2007; 15(3): 499-511.
  • [44] Varvello M, Laufer R, Zhang F, Lakshman T. Multilayer packet classification with graphics processing units. IEEE/ACM Transactions on Networking 2016; 24(5): 2728-2741.
  • [45] Deng Y, Jiao X, Mu S, Kang K, Zhu Y. NPGPU: Network Processing on Graphics Processing Units. In: Zhou Q. (editors). Theoretical and Mathematical Foundations of Computer Science. Singapore: Springer, 2011, pp. 313-321.
  • [46] Kang K, Deng YS. Scalable packet classification via GPU metaprogramming. In: Design, Automation & Test in Europe Conference & Exhibition (DATE); Grenoble, France; 2011, pp. 1-4.
  • [47] Zhou S, Singapura SG, Prasanna VK. High-Performance Packet Classification on GPU. In: High Performance Extreme Computing Conference (HPEC); Waltham, MA, USA; 2014, pp. 1-6.
  • [48] Zheng J, Zhang D, Li Y, Li G. Accelerate Packet Classification Using GPU: A Case Study on HiCuts. In: Park J, Stojmenovic I, Jeong H, Yi G (editors). Computer Science and its Applications. Berlin: Springer, 2015, pp. 231-238.
  • [49] Abbasi M, Fazel SV, Rafiee M. MBitCuts: optimal bit-level cutting in geometric space packet classification. The Journal of Supercomputing 2019; 1-24.
  • [50] Khezrian N, Abbasi M, Comparison of the performance of skip lists and splay trees in classification of internet packets. PeerJ Computer Science 2019; 5(1): e204.
Turkish Journal of Electrical Engineering and Computer Science-Cover
  • ISSN: 1300-0632
  • Yayın Aralığı: Yılda 6 Sayı
  • Yayıncı: TÜBİTAK
Arşiv
Sayıdaki Diğer Makaleler

Rıdvan UMAZ

Musab T S AL-KALTAKCHI, Raıd Rafı Omar AL-NIMA, Mohammed A M ABDULLAH

Hilmi Kayhan YILMAZ, Serkan TOPALOĞLU

Maryam JAMEHSHOURANI, Afsaneh FATEMI, Mohammadalı NEMATBAKHSH

Seyedmohsen DEHGHAN, Mehmet KAYA

Jıngfang WANG, Xulıang YAO, Qı GUAN, Changjı DENG, Shıyan YANG

Mehmet Alp ILGAZ, Andrej LAVRIC, Temıtope ODEDEYI, Izzat DARWAZEH, Bostjan BATAGELJ

Jıanpeng BIAN, Jıaxıng HAO, Shuaı ZHAO, Weıjıng HUA, Shıchuang GAO

Mohsın ABBAS, Sajıd SALEEM, Fazlı SUBHAN, Abdul BAIS

İlhan İLHAN