Applying network calculus for performance analysis of self-similar traffic in on-chip networks

ABSTRACT

On-chip traffic of many applications exhibits self-similar characteristics. In this paper, we intend to apply network calculus to analyze the delay and backlog bounds for self-similar traffic in networks on chips. We first prove that self-similar traffic can not be constrained by any deterministic arrival curve. Then we prove that self-similar traffic can be constrained by deterministic linear arrival curves α_{r,b}(t)=rt+b (r:rate, b:burstiness) if an additional parameter, excess probability ε, is used to capture its burstiness exceeding the arrival envelope. This three-parameter model, ε-α_{r,b}(t)=rt+b(ε), enables us to apply and extend the results of network calculus to analyze the performance and buffering cost of networks delivering self-similar traffic flows. Assuming the latency-rate server model for the network elements, we give closed-form equations to compute the delay and backlog bounds for self-similar traffic traversing a series of network elements. Furthermore, we describe a performance analysis flow with self-similar traffic as input. Our experimental results using real on-chip multimedia traffic traces validate our model and approach.

REFERENCES

• 1: T. Bjerregaard and S. Mahadevan. A survey of research and practices of network-on-chip. ACM Computing Surveys, 38(1):1--51, 2006.
• 2: C.-S. Chang. Performance Guarantees in Communication Networks. Springer-Verlag, 2000.
• 3: Y. Cheng, W. Zhuang, and X. Ling. Towards an FBM model based network calculus framework with service differentiation. Mobile Networks and Applications, 12(5):335--346, December 2007.
• 4: F. Ciucu, A. Burchard, and J. Liebeherr. A network service curve approach for the stochastic analysis of networks. Proc. ACM SIGMETRICS, 2005.
• 5: R. L. Cruz. A calculus for network delay, part I: Network elements in isolation and part II: Network analysis. IEEE Transactions on Information Theory, 37(1):114--141, January 1991.
• 6: N. Fonseca, G. Mayor, and C. Neto. On the equivalent bandwidth of self-similar sources. ACM Transactions on Modeling and Computer Simulation (TOMACS), 10(2):104--124, April 2000.
• 7: Y. Jiang. A basic stochastic network calculus. Proc. ACM SIGCOMM, 2006.
• 8: J.-Y. Le Boudec and P. Thiran. Network Calculus: A Theory of Deterministic Queuing Systems for the Internet. Number 2050 in Lecture Notes in Computer Science (LNCS), Springer-Verlag, 2001.
• 9: W. E. Leland, M. S. Taqqu, W. Willinger, and D. V. Wilson. On the self-similar nature of ethernet traffic (extended edition). IEEE/ACM Transactions on Networking, 2(1):1--15, 1994.
• 10: Z. Lu. Design and analysis of on-chip communication for network-on-chip platforms. Ph.D. thesis, Royal Institute of Technology, March 2007.
• 11: S. Mao and S. S. Panwar. A survey of envelope processes and their applications in quality of service provisioning. IEEE Communications Surveys and Tutorials, 8(3):2--20, 2006.
• 12: I. Norros. On the use of fractal brownian motion in the theory of connectionless networks. IEEE J. Select. Areas Communication, 13(6):953--962, Aug. 1995.
• 13: K. Park and W. Willinger. Self-similar Network Traffic and Performance Evaluation. John Wiley and Sons, 2000.
• 14: Y. Qian, Z. Lu, and W. Dou. Analysis of worst-case delay bounds for best-effort communication in wormhole networks on chip. The 3rd ACM/IEEE International Symposium on Networks-on-Chip (NOCS'09), San Diego, CA, May 2009.
• 15: A. Scherrer, A. Fraboulet, and T. Risset. Analysis and synthesis of cycle-accurate on-chip traffic with long-range dependence. Technical report 2005-53, LIP, ENS-Lyon, December 2005.
• 16: V. Soteriou, H. Wang, and L. Peh. A statistical traffic model for on-chip interconnection networks. IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS), Sep. 2006.
• 17: D. Starobinski and M. Sidi. Stochastically bounded burstiness for communication networks. IEEE Trans. Information Theory, 46:206--212, Jan. 2000.
• 18: D. Stiliadis and A. Varma. Latency-rate servers: A general model for analysis of traffic scheduling algorithms. IEEE/ACM Transactions on Netwroking, 6(5):611--624, October 1998.
• 19: G. Varatkar and R. Marculescu. On-chip traffic modeling and synthesis for mpeg-2 video applications. IEEE Transactions of Very Large Scale Integration (VLSI) Systems, 12(1), January 2004.
• 20: Q. Yin, Y. Jiang, S. Jiang, and P. Y. Kong. Analysis on generalized stochastically bounded bursty traffic for communication networks. Proc. of the 27th IEEE Conference on Local Computer Networks (LCN'02), 2002.
• 21: SoCLib simulation environment. on-line, available at https://www.soclib.fr/.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.4 Performance Analysis and Design Aids**
          Subjects: Formal models**

General Terms:
Design, Performance

Keywords:
network calculus, network-on-chip, performance analysis, self-similar traffic