AN IMPROVED SELECTION TECHNIQUE FOR FAST PACKET ROUTING IN COMPUTER NETWORK

Authors

  • A.T. Akinwale
  • A.A. Adebayo
  • O. Folorunso
  • G.A. Adebayo

DOI:

https://doi.org/10.47839/ijc.10.3.752

Keywords:

Routing Techniques, Switch, Throughput, Treap, NoC, Queueing theory, Odd-Even and XY routing schemes.

Abstract

Contention Awareness Input Selection (CAIS) technique was recently compared with traditional input selection techniques such as First Come First Serve (FCFS) and Round Robin (RR) as a way of improving routing techniques and proved to outperform the two techniques but not widely accepted because of packet starvation problem. In this paper, Contention-Age Input Selection (CAGIS) technique was designed to correct the shortcoming of CAIS. CAIS was modified by including flattening algorithm, treap and queueing theory to improve packet access and control contention age level in the input buffer. The design involved three phases of setting up the network topology using the network objects, initiating of an event scheduler and traffic sources to start/stop transmitting packet through the event scheduler which was implemented using object-oriented tool commands language of script simulation program. The paper concluded that whilst deterministic XY routing scheme and the adaptive Odd-Even routing algorithm were used with CAGIS and CAIS to compare their performance, it was observed that CAGIS performed better under the three synthetic traffic patterns of uniform, transpose and hotspot. The results has improved significantly on contention age level of packets in the input buffer by uniformly distributing them to output ports.

References

W. Dong, B. M. Al-Hashimi and M. T. Schmitz, Improving routing efficiency for network-on-chip through contention-aware input selection, Proceedings on 11th Conference ASP-DAC, Japan, (2006).

R. R. Cessa, Design and Analysis of Reliable High Performance Packet Switches, PhD thesis, Plytechnic University, 2001.

D. Boer, D. P. Kroese and R. Y. Rubinstein, A fast cross-entropy method for estimating buffer overflows in queueing networks, Journal of Management Science, 50 (7) (2004). pp. 883-895.

V. D. Aline, Evaluation of routing algorithm on mesh based NoCs, Technical report series of GI-edition proceeding of 10th International Conference on Innovative Internet Community Services, Thailand, (2010).

C. Glass and L. Ni, The turn model for adaptive routing, Journal of the Association for Computing Machinery, 41 (5) (1994). pp. 874-902.

D. Xiang, Y. P. Zhang and J. Wu, Deadlock free adaptive routing in meshes based on cost effective deadlock schemes, International Conference on Parallel Processing, (2007).

J. Henkel, W. Wolf and S. Chakradhar, On-chip Network: A scalable communication centric embedded system desighn paradigm, VLSI Design, India, (2004). pp. 845-851.

Z. Vladimir, Adaptive routing in (Q)Noc, LNI Proceedings, (2008). http://subs.emis.de/LNI/ proceedings/proceedings165/P-165.pdf.

R. Marculescu and J. Hu, Dyad: smart routing for network-on-chip, Proceedings of the 41st annual conference on design automation, ACM, New York, (2004). pp. 260-263.

N. Kavaldjier, G. J. M. Smit and P. G. Jansen, A virtual channel router for on-chip network, IEEE International SOC Conference, USA (2004). pp. 289-293.

V. S. Iria, Design of a High Performance Buffered Crossbar Switch Fabric using Network-on-Chip, MSc. Dissertation, Department of Electrical and Computer Engineering, Delft University of Technology, (2008).

L. Mhamdi and M. Hamdi, MCBF: A high performance scheduling algorithm for buffering crossbar switches, IEEE communication letter, 7 (9) (2003). pp. 451-453.

H. C. Myong, L. Mieszko, S. S. Keun, K. Michel, W. Tina and D. Srinivas, Oblivious routing in on-chip bandwidth adaptive networks, Computer science and artificial intelligence laboratory technical report, 2009.

S. Kumar, A. Jantsch, J. P. Forsell, M. Millberg and M. Oberg, A network on chip architecture and design methodology, ISVLSI, USA (2002). pp. 117-124.

T. G. Mattson, R. V. Der Wijngaart, Programming on the intel 80-core network-on-chip terascale processor, Proceedings of the 2008 ACM/IEEE conference on supercomputing, Piscataway, USA, (2008). pp. 1-11.

G. M. Chiu, The odd-even turn model for adaptive routing, IEEE Transactions on Parallel and Distributed Systems, (11) (2000). pp. 729-738.

Downloads

Published

2011-12-20

How to Cite

Akinwale, A., Adebayo, A., Folorunso, O., & Adebayo, G. (2011). AN IMPROVED SELECTION TECHNIQUE FOR FAST PACKET ROUTING IN COMPUTER NETWORK. International Journal of Computing, 10(3), 223-234. https://doi.org/10.47839/ijc.10.3.752

Issue

2011, Volume 10, Issue 3

Section

Articles

License

International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:
•    Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
•    Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
•    Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.