Printer Friendly

An efficient and novel buffer clustering technique for minimal data loss, load balancing and effective queue management in multi core processors.


Network On-Chip (NoC) is the connection of many cores that are integrated into a single System On-Chip (SoC). A NoC contains routers, links, and network interfaces. In which the routers are used to direct the data over the links, and topology is used to describe the logical layout. The basic process of the network interface is to disconnect the computation from a network. NoC contains four important aspects they are computation, memory, communication, and I/O (Anna Adamaszek, 2011). NOC can improve design productivity by supporting modularity and reuse of complex cores.

Two basic types of routing are Static Routing and Dynamic Routing. In dynamic routing there are three kinds of routing 1. Distance vector routing 2. Link state routing 3. Hybrid routing. Also the routing process can be classified into several of two types they are 1. Unicast Routing 2. Multicast Routing. In unicast routing, the packets have a single destination, while in the case of multicast routing, the packets have multiple destinations. Between unicast and multicast routing the unicast routing is more suitable for on-chip communication, because the unicast is practical approach, since it's having end-to-end communication links between the components of the on-chip network. Based on the routing decision, unicast routing can be further classified into four classes: centralized routing, source routing, distributed routing and multiphase routing (Ankur Agarwal, 2009).

Various routing algorithms have been proposed for the Network On-Chip. Most researchers suggested that the static routing algorithms are performed well in network on-chip, and the performance is based on the static behaviour of the NOC process. Most NOC implementations used either XY routing or street sign routing algorithms (Ankur Agarwal, 2009).

Buffer management is a concept and it plays an important role in routing process in order to achieve efficiency. And it contains the two important mechanisms they are buffer manager and buffer cache. The buffer manager provides the authority to access the database and it also updates the database. And the role of buffer cache is to reducing the I/O files. Buffer management is used to enhance performance of network.

RED algorithm plays a vital role in buffer management. RED stands by Random Early Detection (or) Random Early Drop (or) Random

Early Delay. The main objective of the algorithm is to reduce the congestion within a network. It will drops the packets probabilistic based on average number of packets in the buffer, and it will use the same probabilistic for all the flows (Sonia Jain and EytanModiano).

Reordering Buffer Management: This problem can occur when the number of data arrives into a processing station and the data has to be processed. In this case the cost of processing the data is fully depending on the order of the processing (Bjerregaard, T. and S. Mahadevan, 2006).

Decision Problem: This problem can occur at the network when many packets arrive and overload occurs (Prashant Krishna, 2013).

In proposed system the Network On-chip is divided into local clusters by using partition clustering algorithm, and then threshold value can be set at each and every buffer in the cluster. If the capacity of the buffer is ten then the threshold value is set as eight in order to avoid bottleneck. The incoming packet first checks the threshold value in order to inject the packet into buffers. If the threshold value is less than the default value then the data will be transferred into the buffer, otherwise the data will get discarded. This process can be done by using RED algorithm. Within a cluster itself it will find out the alternate buffer to inject the packets so that this work will reduce the latency when compared to existing work.

The remaining part of the paper discusses on the following information: section 2 reports the literature work done relevant to buffer utilization on network on-chip, the simulation work of the proposed system is presented in section 3, section 4 is recorded with discussion on the results obtained and finally section 5 concludes the proposed work with the direction for future enhancement.

1. Literature Review:

Salem and NASRI (2011) reported on QoS metric modeling using the network on-chip (NoC) modeling in order to establish QoS metric and they focused on the network delay bound and packet losses. Their work is fully based on network calculus theory which is a mathematical model used to determine the dataflow between IP's interconnected over NoC. They have proposed QoS metric based on QoS parameter. It serves for multi-application services using calculus model.

Songpo Zhang et al (2011) described and derivate RED algorithm in order to create the new algorithm. They have mentioned a problem that when the packet arrives at the gateway its having the improper queue length of packet-marking probability. To resolve this problem they presented a new algorithm called SW-RED, it will dynamically adjust the weight and offers efficient packet-marking.

Andrea Francini (2011) mentioned twofold. In first one she mentioned due to the manner of the RED algorithm it maps the buffer occupancy levels onto packet drop probabilities and it will naturally flawed. In second one she introduced Periodic Early Detection (PED), she determined that the buffer management system with touch less arrangement survive 100% link utilization. For this purpose the PED rule requires only 2.5% memory.

Wei Shi et al (2011) reported on Hierarchical Bit-line Buffer (HiBB) for shared buffer in network on-chip in that they mentioned corresponding to traffics the HiBB can be configured. They have proposed two methods to improve the router. As well light-loaded directions and traffic situation of the total network will be determined by using congestion-aware output-port allocation system. Their second proposal is to configure the shared buffer with the help of an efficient run-time Virtual Channel (VC) regulation scheme. By which the VC's are allocated with respect to loads of network. Finally they mentioned their proposed work saves about 6.9% area and reduces 70% power consumption.

S. Umamaheswari et al (2012) reported on dynamic buffer management, the main intension of their work is to create heterogeneous router. Under various communication requirements in fault-tolerant adaptive NoC applications the buffer slots of the heterogeneous router dynamically specified in order to improve the performance. In their proposed work in order to improve the performance the buffer slots of the heterogeneous router dynamically re-allocated for different applications. The number of hotspots using EBLA (Extended Buffer Loan Algorithm) supports the process of reallocation. The oversized IP's (Internet Protocols) destroyed the regular mesh-based NoC architecture. The result of this process is mesh-based NoC with irregular manner and it wants a novel routing algorithm in case if there is any faulty links.

Heying Zhang et al (2012) reported on multi-VC dynamic shared buffers, they have proposed a novel multi-VC dynamic shared buffer called DAMQ-PF (Dynamically Allocated Multi-queue-Prefetch). This is used to minimize the area and memory requirement of shared buffer among multiple virtual channels (VC). Without delay they implemented continuous and concurrent reading and writing of the shared buffer. Finally they mentioned that the DAMQ-PF attains high buffer utilization, low write and read delay and higher throughput. On NoC based flit switch it satisfies the performance requirements in good manner.

Daniel U. Becker et al (2012) introduced an adaptive backpressure which is used to improve the usage of input buffers of the router which is dynamically managed. This is done by keep on changing the stiffness of the flow control feedback loop with respect to obtained traffic criteria. Based on the measured downstream congestion the proposed work heuristically restricts the number of credits available in each and every channel. The main objective of their work is to reduce the area of the buffer which occupied unproductively. They mentioned that the adaptive backpressure increases the network stability and also it reduces latency about 31%. And also it avoids the performance degradation.

ZHAO Jian-peng et al (2012) reported on a congestion control scheme based on improved RED (Random Early Detection) algorithm, in this they have introduced an improved RED algorithm called DFCC (Delay Feedback Congestion Control) which is based on congestion control scheme. When traffic occurs it will automatically adjust the link delay in order reduce the packet loss. And their experimental result shows that the number of packets increasing then the packet loss of DFCC system is comparatively lesser than RED algorithm.

Wen-Fong Wang and Yi-JhouShen (2012) introduced a Network On-Chip concept. The performance of the NoC increased by using congestion management method. For a particular message the congestion can be checked. In order to increase the network performance and reduce the network complexity they have proposed an idea called (ARC) Automatic Ramp Control. Finally they mentioned that their congestion control method is very effective.

Maulik K. Dadhania and K. Vinay Kumar (2012) reported on modified RED algorithm, in this paper they mentioned when overcrowd takes place at the router, web traffic and ECN (Explicit Congestion mechanism) marked packets are dropped. They proposed a solution in order to increase the response time and the number of packets it is transmitted by web traffic and it will not affect the throughput of the bottleneck links. They have also tried this solution with RED algorithm and done a test on some factors of modified RED algorithm such as performance and efficiency.

Neila MOUSSA and Rached TOURKI (2013) reported on performance analysis of network on-chip, in this paper they presented the analytical model of the on chip switch architecture. It is used to specify the physical and logical property in order to obtain the improved performance of the on chip switch architecture.

Chandni M Patel (2013) reported on URED (Upper Threshold RED). The core part of this paper is to get over from the disadvantages of the RED algorithm. So that he introduced a new algorithm named URED. By made some changes in the existing algorithm he created a new algorithm. The new technique is efficient than the previous algorithm and also it works opposite to DDoS (Distributed Denial of Service) attack. He has done a simulation in NS 2.35 simulator environment. And his simulation results showed that the URED algorithm provide better performance than RED and also adaptive RED, as well he done a comparison between these two algorithms. The comparison metrics are total average throughput, total packet drops and average packet drops.

Salem and Nasri (2011) presented a new NoC QoS metrics modeling which is based on QoS parameters. In the NoC nodes he quantifies the buffer requirements and packet switching technique by done analysis on End-to-End delays and packet loss. Their work is fully focused on flit losses which is occur because of buffer congestion for a network loading. By which they determine the optimal buffer size for switch design, this based on the wormhole routing method.

Farid Daneshgar and Majid Taghipoor (2014) reported that they proposed a novel algorithm named DAMQSV and DAMQS. These mechanisms are used in system on-chip applications and it requires an interconnection network. These algorithms are used to optimize the buffer management in an effective manner with good performance when there is larger network load and it occupies only lesser amount of buffer space. They have done simulation on Modalism environment to test the performance of these algorithms. During the simulation process they considered many factors such as different traffic mode, network size, virtual channel number, buffer size per virtual/physical channel and routing protocols. They concluded that these algorithms are efficient especially DAMQSV is more efficient.

K. Malathi and S. Vivek Pandian (2014) reported that they mentioned the solution to overcome the design complexity in network. They introduced a buffer less router in order to avoid the design complexity. And also they discussed the impact of power reduction.

V. Parthasarathy and V. Rajamani (2008) they introduced a new techniques called as flow discard and early flow discard. These techniques are used to analysis the performance of routing and switching in optical IP networks. By using these techniques they achieved the lower loss rate which is about 24.95% and in optical packet routing which is 71.17%.

V. Parthasarathy et al (2009) presented a new scheme for contention resolution in bulk flow TCP routing in optical IP network. Also they had done a simulation work. They studied about packet loss rate and flow loss rate for both fixed size and variable size flows. And they achieved the flow loss rate about 0.038 for variable size flow and flow loss rate about 0.043 for fixed size flows intended for 200 packets transmission.

2. Experiment:

This session includes the experimental part of above mentioned work.

The above mentioned snap shot indicates the cluster formation of network on-chip in 16 numbers of processors with buffers. Each cluster having its own source to transfer the data into buffers. In that threshold value can set at each and every buffer in the local cluster. Threshold value is 75% of buffer capacity in order to avoid bottleneck. The connection between the clusters are virtual not physical, but the connection within the cluster is physical.

The incoming packet from the source first checks the threshold value of the corresponding buffer. If the buffer having the empty space in it the data will be transmit into the processor of the corresponding buffer, or else the packet will be transferred into the buffer of the another processor in the same cluster itself.

Here the data is enter into buffer, because in this case the buffer having the empty space in it. After sometimes it will transmit into the processor for the particular process. So that here the buffer space is utilized in higher level and also efficient too. Within the cluster itself it will find out the buffer space so that it will take only lesser amount of time.

This snap shot indicates the successful transformation of packet into the processor. In this case the data is transferred into the processor.

The above mentioned snap shot indicates the process which takes place in another cluster in the network on-chip. In this case the incoming packet from the source first enter into the buffer, here the data checks the threshold value of the buffer. Here the threshold value exceeds its level so that the data is transferred into another buffer in the same cluster. Here also the data checks the threshold value of the buffer.

In this buffer also the threshold value exceeds its level. Finally the data get dropped due to the insufficient space in the buffer of the corresponding processor. But, the packet drop will occur only at certain cases not frequently. The packet drop will not affect the performance of the buffer.

3. Result and Analysis:

The proposed work will reduce the time taken to find out the empty space in the buffer as well it will reduces the network traffic. Data loss also will be low in this proposed work. The following graph will show the comparison between existing and proposed system in terms of data loss, buffer utilization, throughput and latency.

This graph indicates the data loss between shared queues and cluster method. When compared to shared queues that are conventional method data loss is low in cluster based method. Because in conventional method the data have to search for the empty buffer on the whole network. So, it traverse the long distance on the network during this travelling it may loss many data compared to cluster based method.

This graph indicates the buffer utilization between conventional method and cluster based method. The cluster based method utilizing the more buffer space when compared to conventional based method because in this case it will uses the utmost buffer space until it attain the threshold value. As well it's having one of the added advantages that it avoids the problem of bottleneck occurrence.

This graph is about throughput between conventional method and cluster based method. Throughput is higher in cluster based method because of the clustering technique. It will find out the buffer space within the cluster itself so within short span of time it will find the buffer space as well it transfers the large amount of data.

This graph is about latency between conventional method and cluster based method. Latency is low in cluster based method because within a local cluster itself it will find out the empty buffer space so, comparatively latency is low in cluster based method. In case of conventional method the data searches for the empty space on the whole network so it will take large amount of time to find out the empty buffer space.

4. Conclusion:

In order to efficiently utilize the buffer space in the multicore processor, the proposed work uses the clustering methodology and partitions the buffers into clusters. The threshold value assigned to each buffer in the cluster allows determining the availability of the buffer for packet transmission. The RED algorithm implemented in this paper ensures the avoidance of collision during the data transmission. Thus, the proposed work optimizes the buffer utilization and achieves reduced throughput and power consumption compared to the existing shared queue technique in the multicore processor.


Article history:

Received 6 March 2015

Accepted 25 April 2015

Published 29 May 2015

Corresponding Author: Anusha, V., M.E Student, vel tech multi tech Dr. Rangarajan Dr. Sakunthala Engineering College, Avadi, Tamilnadu, India.



Anh T. Tran and Bevan M. Bass, 2014. "Achieving High-Performance On-Chip Networks With Shared-Buffer Routers". IEEE Transactions On Very Large Scale Integration (VLSI) Systems, 22(6).

Ankur Agarwal, Cyril Iskander and Ravi Shankar, 2009. "Journal of Engineering, Computing and Architecture". ISSN 1934-7197, 3(1).

Sonia Jain and Eytan Modiano, "Buffer Management Schemes For Enhanced TCP Performance Over Satellite Links". Laboratory for Information and Decision Systems Massachusetts Institute of Technology Cambridge, MA 02139.

Prashant Krishna, 2013. "A Study on Dynamic and Static Clustering Based Routing Schemes for Wireless Sensor Networks". International Journal of Modern Engineering Research (IJMER), 3(2): pp 1100-1104 ISSN: 2249-6645.

Leah Epstein and Rob van Stee, "Buffers Management problems".

Bjerregaard, T. and S. Mahadevan, 2006. "A Survey of Research and Practices of Network-on-Chip".ACM Computing Surveys, 38, Article 1.

Anna Adamaszek, Artur Czumaj and Matthias Englert Harald Racke, 2011. "Almost Tight Bounds for Reordering Buffer Management". STOC'11, June 6-8, 2011, San Jose, California, USA. Copyright ACM 978-1-4503-0691-1/11/06.

Salem and NASRI, 2011. "Network on Chip: a New Approach of QoS Metric Modeling Based on Calculus Theory". International Journal of Computer Networks & Communications (IJCNC), 3(5).

Songpo Zhang, Jiming Sa, Jian Liu and Shaoyun Wu, 2011. "An Improved RED Algorithm with Sinusoidal Packet-marking Probability and Dynamic Weight". 978-1-4244-8039-5/11/$26.00 [C]2011 IEEE.

Andrea Francine, 2011. "Beyond RED: Periodic Early Detection for On-Chip Buffer Memories in Network Elements". IEEE 12th International Conference on High Performance Switching and Routing.

Wei Shi, Weixia Xu, Hongguang Ren, Qiang Dou, Zhiying Wang, Li Shen and Cong Liu, 2011. "A Novel Shared-buffer Router for Network-on-chip Based on Hierarchical Bit-line Buffer", 978-1-4577 1954-7/11/$26.00 [C]2011 IEEE.

Umamaheswari, S. N. Nancy and J. Rajapaul Perinbam, 2012. "Dynamic Buffer Management to Improve the Performance of Fault Tolerance Adaptive Network-On-Chip Applications", ICRTIT.

Heying Zhang, Kefei Wang, Yi Dai, Lu Liu, 2012. "A Multi-VC Dynamically Shared Buffer with Prefetch for Network on Chip". IEEE Seventh International Conference on Networking, Architecture, and Storage, 978-0-7695-4722-0/12 $26.00 [C] 2012 IEEE DOI 10.1109/NAS.2012.39.

Daniel U. Becker, Nan Jiang, George Michelogiannakis and William J. Dally, 2012. "Adaptive Backpressure: Efficient Buffer Management for On-Chip Networks". Department of Electrical Engineering, Stanford University, Stanford, CA, USA, 978-1-4673-3052-7/12/$31.00 [C]IEEE.

ZHAO Jian-peng, GUO Shi-ze, ZHENG Kangfeng, ZHAO Shuang, 20121. "A congestion control scheme based on improved RED algorithm in Internet topology simulation". International Conference on Computer Science and Service System, 978-0-7695-4719-0/12 $26.00 [C] 2012 IEEE DOI 10.1109/CSSS.2012.77.

Wen-Fong Wang and Yi Jhou Shen, 2012. "A Congestion-Relief Method for Wormhole-routed 2D Mesh Networks". 978-1-4673-2588-2/12/$31.00 [C]IEEE.

Maulik K. Dadhania and K. Vinay Kumar, 2012. "Modified RED Algorithm to Improve The Performance of Web Traffic". 2012 Third International Conference on Advanced Computing & Communication Technologies, 978-0-7695-49415/12 $26.00 [C] IEEE DOI 10.1109/ACCT.2013.45.

Neila MOUSSA and Rached TOURKI, 2013. "Analytical Performance Analysis of Mesh Network on- Chip based on network calculus".978-1-46735549-0/13/$31.00 [C]2013 IEEE.

Chandni M. Patel, 2013. "URED: Upper Threshold RED an Efficient Congestion Control Algorithm".th ICCCNT, Tiruchengode, India.

Salem and Nasri, 2011. "New Approach of QoS Metric Modeling on Network on Chip". Int J. Communications, Network and System Sciences, 4: 351-355.

Fadir Daneshgar and Majid Taghipoor, 2014. "Increase the efficiency of Network on Chip using buffer sharing mechanism". IJCSI International Journal of Computer Science Issues, 11(1): 2.

Malathi, K. and S. ViVek Pandian, 2014. "An Effective Test Data Delivery and Collection Method in NoC on Unicast Based Multicast Method". International Journal of Advance Research in Computer Science and Management Studies, 2(1).

Parthasarathy, V. and V. Rajamani, 2008. "Simulation of Performance Analysis of Bulk Flow Routing for TCP in Optical Network", Optical Communication, 29: 98-106.

Parthasarthy, V., P. Anandkumar and V. Rajamani, 2009. "Performance analysis for Contention Resolution in Bulk Flow TCP Routing to Optical IP Networks through simulation", INFOCOMP J. of computer science, 8(2): 95-102.

(1) Anusha, V., (2) V. Parthasarathy, (3) Bellamkonda Prithvi, (4) Aarthi Priya Bellamkonda

(1) M.E Student, vel tech multi tech Dr. Rangarajan Dr. Sakunthala Engineering College, Avadi, Tamilnadu, India. (2) Professor, vel tech multi tech Dr. Rangarajan Dr. Sakunthala Engineering College, Avadi, Tamilnadu, India. (3) B.E. Student, vel tech multi tech Dr. Rangarajan Dr. Sakunthala Engineering College, Avadi, Tamilnadu, India. (4) B.Tech Student, Holy Mary Institute of Technology, Bogaram, Hyderabad.
COPYRIGHT 2015 American-Eurasian Network for Scientific Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Anusha V.; Parthasarathy, V.; Prithvi, Bellamkonda; Bellamkonda, Aarthi Priya
Publication:Advances in Natural and Applied Sciences
Article Type:Report
Date:Jun 15, 2015
Previous Article:Unsupervised segmentation based classification of microcalcification using SVM.
Next Article:Simulation analysis of hybrid asymmetric SVPWM for DTC based induction motor drive using soft computing technique.

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters