Capturing router congestion and delay

ABSTRACT

Using a unique monitoring experiment, we capture all packets crossing a (lightly utilized) operational access router from a Tier-1 provider, and use them to provide a detailed examination of router congestion and packet delays. The complete capture enables not just statistics as seen from outside the router, but also an accurate physical router model to be identified. This enables a comprehensive examination of congestion and delay from three points of view: the understanding of origins, measurement, and reporting. Our study defines new methodologies and metrics. In particular, the traffic reporting enables a rich description of the diversity of microcongestion behavior, without model assumptions, and at achievable computational cost.

REFERENCES

• 1: K. Papagiannaki, S. Moon, C. Fraleigh, P. Thiran, F. Tobagi, and C. Diot, "Analysis of measured single-hop delay from an operational backbone network," in Proc. IEEE INFOCOM, New York, Jun. 2002, pp. 535-544.
• 2: Waikato Applied Network Dynamics. [Online]. Available: http://www. wand.cs.waikato.ac.nz/wand/wits/
• 3: N. Hohn , D. Veitch , K. Papagiannaki , C. Diot, Bridging router performance and queuing theory, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 4: K. Papagiannaki, D. Veitch, and N. Hohn, "Origins of microcongestion in an access router," in Proc. Passive and Active Measurement Workshop (PAM2004), Juan-Les-Pins, France, Apr. 19-20, 2004, Lecture Notes in Computer Science (LNCS), pp. 126-136, Springer.
• 5: Nick McKeown, The iSLIP scheduling algorithm for input-queued switches, IEEE/ACM Transactions on Networking (TON), v.7 n.2, p.188-201, April 1999 [doi>10.1109/90.769767]
• 6: W. Simpson, PPP in HDLC-like Framing, RFC Editor, 1994
• 7: Endace Measurement Systems. [Online]. Available: http://www.endace.com/
• 8: S. Donnelly, "High precision timing in passive measurements of data networks," Ph.D. dissertation, Univ. of Waikato, Hamilton, New Zealand, 2002.
• 9: C. Fraleigh, S. Moon, B. Lyles, C. Cotton, M. Khan, D. Moll, R. Rockell, T. Seely, and C. Diot, "Packet-level traffic measurements from the Sprint IP backbone," IEEE Network, vol. 17, no. 6, pp. 6-16, Nov.-Dec. 2003.
• 10: S. Keshav and S. Rosen, "Issues and trends in router design," IEEE Commun. Mag., vol. 36, no. 5, pp. 144-151, May 1998.
• 11: N. Hohn, D. Veitch, and P. Abry, "Cluster processes, a natural language for network traffic," IEEE Trans. Signal Processing, vol. 51, Special Issue on Signal Processing in Networking, no. 8, pp. 2229-2244, Aug. 2003.
• 12: Konstantina Papagiannaki , Rene Cruz , Christophe Diot, Network performance monitoring at small time scales, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948244]
• 13: R. Addie, P. Mannersalo, and I. Norros, "Performance formulae for queues with Gaussian input," in Proc. 16th Int. Teletraffic Congr., Edinburgh, Scotland, U.K., Jun. 1999, pp. 1169-1178.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Measurement techniques

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development

General Terms:
Design, Measurement, Performance

Keywords:
busy period, congestion, delay, modelling, router, utilization