Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

Application of the generalised ballot theorem for evaluation of performance in packet buffers with non-first in first out scheduling

Application of the generalised ballot theorem for evaluation of performance in packet buffers with non-first in first out scheduling

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)
Add to cart

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Communications — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

© The Institution of Engineering and Technology
Published

Packet scheduling is a vital component to support different classes of service in all-packet networks. In classical queuing systems, the waiting-time performance of non-first in first out buffer scheduling systems could be predicted through the use of analysis. However, all-packet networks feature traffic patterns that do not conform to classical Poisson-like processes, and this greatly complicates the evaluation of their performance. Our novel approach to this problem is through a hybrid combination of analysis and simulation. The authors derive a combinatorial algorithm, using the generalised ballot theorem, which predicts waiting times for low-priority traffic. When this algorithm is combined with prior work on traffic aggregation, the authors achieve a significant reduction in the state space associated with the buffer under study. To numerically test this algorithm, the authors demonstrate its use in simulation, where state space and event count reduction is a fundamental requirement to ensure experiments complete in a timely fashion. Numerical results from these simulations show a very significant reduction in the number of events processed combined with improved state coverage. This is achieved while maintaining a highly accurate representation of packet delays compared with a conventional approach.

Inspec keywords: telecommunication congestion control; queueing theory; combinatorial mathematics; scheduling; state-space methods

Other keywords: combinatorial algorithm; queuing systems; traffic aggregation; all-packet networks; non-first in first out buffer scheduling; waiting time performance; packet delays; packet buffers; low priority traffic; state space; packet scheduling; event count reduction; traffic patterns; generalised ballot theorem

Subjects: Control applications in data transmission; Queueing systems; Queueing theory; Combinatorial mathematics; Combinatorial mathematics; Queueing theory

References

    1. 1)
      • P. Heidelberger . Fast simulation of rare events in queuing and reliability models. ACM Trans. Model. Comput. Simul. , 1 , 43 - 85
    2. 2)
      • O. Gurewitz , M. Sidi , I. Cidon . The ballot theorem strikes again: packet loss process distribution. IEEE Trans. Inf. Theory , 7 , 2588 - 2595
    3. 3)
      • M. Crovella , A. Bestavos . Self similarity in world wide web traffic: evidence and possible causes. IEEE/ACM Trans. Netw. , 6 , 835 - 846
    4. 4)
      • Paxson, V., Floyd, S.: `Why we don't know how to simulate the internet', WSC, 1995, p. 1037–1044.
    5. 5)
    6. 6)
    7. 7)
      • Garret, M., Willinger, W.: `Analysis modelling and generation of self similar VBR video traffic', Proc. ACM SIGCOMM, 1994, p. 269–280.
    8. 8)
    9. 9)
      • Ma, A.H.I.: `Accelerated simulation of power-law traffic in packets networks', 2003, PhD, Queen Mary University of London.
    10. 10)
    11. 11)
      • J.A. Schormans , E. Liu , L.G. Cuthbert , J.M. Pitts . A hybrid technique for the accelerated simulation of ATM networks and network elements. ACM Trans. Model. Comput. Simul. , 2 , 182 - 205
    12. 12)
      • A. Ma , J. Schormans , L. Cuthbert . Aggregation technique for networks with power law traffic and application to accelerated simulation. IEE Proc., Commun. , 3 , 177 - 183
    13. 13)
      • L. Takacs . (1967) Combinatorial methods in the theory of stochastic process.
    14. 14)
      • S. Lu , J. Schormans . A time-stepped approach for accelerated simulation of mobile ad hoc networks. IET Commun. , 5 , 609 - 620
    15. 15)
    16. 16)
      • Villen-Altamirano, M., Villen-Altamirano, J.: `RESTART: a straight forward method for fast simulation of rare events', Winter Simulation Conf. Proc., 1994, p. 282–289.
    17. 17)
      • J.M. Pitts , J.A. Schormans . (2000) Introductions to IP and ATM design and performance.
    18. 18)
      • T. Auld , A.W. Moore . Bayesian neural networks for internet traffic classificaion. IEEE Trans. Neural Netw. , 1 , 224 - 239
    19. 19)
      • S. Floyd . Difficulties in simulating the internet. IEEE/ACM Trans. Netw. , 4 , 392 - 403
    20. 20)
      • A. Erramilli , O. Narayan , W. Willinger . Experimental queuing analysis with long-range dependence packet traffic. IEEE/ACM Trans. Netw. , 2 , 209 - 223
    21. 21)
      • Tinnakornsrisuphap, P., Makowski, A.: `Limit behaviour of ECN/RED gateways under a large number of TCP flows', Proc IEEE INFOCOM 2003, 2003.
    22. 22)
      • M. Macdougall . Computer system simulation: an introduction. ACM Comput. Surv. , 3 , 191 - 209
    23. 23)
    24. 24)
      • Schormans, J.A.: `Discrete time priority queues in telecommunication networks', 1990, PhD, Queen Mary University of London.
    25. 25)
    26. 26)
      • Shahabuddin, P.: `Fast simulation of packet loss rate in communication networks with priorities', Proceedings of the Winter Simulation Conf., 1994, p. 274–281.
    27. 27)
      • Heinanen, J., Baker, F., Weiss, W., Wroclawski, J.: `Assured forwarding PHB group', IETF RFC 2597, June 1999.
    28. 28)
      • Cisco webpage: http://www.cisco.com/en/US/products/hw/switches/ps60/products_qanda_item09186a0080116ffe.shtml#q, last visited 16 October 2007.
    29. 29)
    30. 30)
      • B. Melamed , S. Pan , Y. Wardi . HNS: A streamlined hybrid network simulator. ACM Trans. Model. Comput. Simul. , 3 , 251 - 277
    31. 31)
      • I. Cidon , R. Guerin , A. Khamisy , M. Sidi . Analysis of a correlated queue in communication systems. IEEE Trans. Inf. Theory , 2 , 456 - 465
    32. 32)
      • A.B. Deiker , M. Mandjes . Fast simulation of overflow probabilities in a queue with Gaussian input. ACM Trans. Model. Comput. Simul. , 2 , 119 - 151
    33. 33)
      • Y. Liu , F.L. Presti , V. Misra , D.F. Towsley , Y. Gu . Scaleable fluid models and simulations for large-scale IP networks. ACM Trans. Model. Comput. Simul. , 3 , 305 - 324
    34. 34)
      • Jacobson, V., Nichols, K., Poduri, K.: `An expedited forwarding PHB group', IETF RFC 2598, June 1999.
    35. 35)
    36. 36)
      • Ariffin, S.H.S., Schormans, J.A.: `Efficient acceleration simulation technique for packet switched networks: a buffer with two priority inputs', Proc. IEEE Int. Conf. Communications, 2004, 4, p. 2246–2250.
    37. 37)
      • G. Mercankosk , G.M. Nair , W.J. Soet . Combinatorial techniques for M/G/1-type queues. J. Appl. Probab. , 3 , 722 - 736
    38. 38)
      • W.E. Leland , M.S. Taqqu , W. Willinger , D.V. Wilson . On the self-similar nature of Ethernet traffic (extended version). IEEE/ACM Trans. Netw. , 1 , 1 - 15
    39. 39)
    40. 40)
    41. 41)
      • R.J. Mondragon , D.K. Arrowsmith , J.M. Pitts . Chaotic maps for traffic modelling and queueing performance analysis. Perform. Eval. , 4 , 223 - 240
    42. 42)
      • W. Willingger , M.S. Taqqu , R. Sherman , D.V. Wilson . Self Similarity through high-variability: statistical analysis of Ethernet LAN traffic at the source level. IEEE/ACM Trans. Netw. , 1 , 71 - 86
    43. 43)
      • Crovella, M.E., Lipsky, L.: `Long-lasting transient condition in simulations with heavy-tailed workloads', WSC'97, December 1997, p. 1005–1012.
    44. 44)
      • F. Baccelli , D. McDonald , J. Reynier . A mean-field model for multiple TCP connections through a buffer implementing RED. Perform. Eval. Archive , 77 - 97
    45. 45)
      • J.A. Schormans , E. Liu , L.G. Cuthbert , G. Stonely . An analytic technique for accelerating the simulation of generic network traffic. Electron. Lett. , 25 , 2168 - 2170
    46. 46)
      • Iyer, S., McKeown, N.: `Making parallel packet switched practical', IEEE INFOCOM, 2001, p. 1680–1687.
    47. 47)
      • Bonald, T., Proutiere, J., Roberts, J.W.: `Statistical performance guarantees for streaming flows using expedited forwarding', Proc. IEEE INFOCOM, 2001, 2, p. 1104–1112.
    48. 48)
      • Liu, E., Schormans, J.A., Cuthbert, L.G., Phillips, C.I., Stonely, G.: `Fast hybrid simulation with neural network prediction', World multiconference on systemics, cybernetics and informatics, 7, p. 254–258, 23-26/7/2000, computer science and engineering part 1.
    49. 49)
      • J.K. Townsend , Z. Harastzi , J.A. Freebersyser , M. Devetsikiotis . Simulation of rare events in communication networks. IEEE Commun. Mag. , 8 , 36 - 41
    50. 50)
      • Nikolaidis, I., Fujimoto, R., Cooper, C.A.: `Parallel simulation of high-speed network multiplexers', Decision and Control IEEE Conf. Proc., 1993, 3, p. 2224–2229.
    51. 51)
      • Huang, C., Devetsikiotis, M., Lambadaris, I., Kaye, A.R.: `Fast simulation for self-similar traffic in ATM networks', Proc. IEEE Int. Conf. Communications, 1995, 1, p. 438–444.
    52. 52)
      • Arrowsmith, D.K., Mondragon, R.J., Pitts, J.M., Woolf, M.: `Internet packet traffic congestion', Proc. Int. Sym. Cir. and Sys., 2003, ISCAS'03, 2003, 3, p. 746–749.
    53. 53)
      • C.S. Chang , P. Heidelberger , P. Shahabuddin . Fast simulation of packet loss rate in a shared buffer communication switch. ACM Trans. Model. Comput. Simul. , 4 , 306 - 325
    54. 54)
      • K. Park , W. Willinger . The internet as a large-scale complex system, A volume in the Santa Fe Institute Studies on the Sciences of Complexity.
    55. 55)
      • P. Humblet , A. Bhargava , M.G. Hluchi . Ballot theorems applied to the transient analysis of nD/D/1 queues. IEEE/ACM Trans. Netw. , 1 , 81 - 95
    56. 56)
    57. 57)
      • Yu, Z., McEliece, R.J.: `Buffer occupancy of statistical multiplexers with periodic interchangeable traffic in ATM networks', ISlT 1997, , Ulm, Germany.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-com.2008.0062
Loading

Related content

content/journals/10.1049/iet-com.2008.0062
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address