Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706
Home Page
Data Communications and Networks II 4003-541-70/4005-741-70 Spring Quarter 2006
Course Page

4003-541-70/4005-741-70
Data Communications and Networks II
Module 4. Network Delay Analysis -- Lecture Notes

Prof. Alan Kaminsky -- Spring Quarter 2006
Rochester Institute of Technology -- Department of Computer Science

Questions

  • Given:
    • A network topology (graph)
    • Capacity of each link (bits/sec)
    • Route from each source to each destination
    • Traffic level (packets/sec) from each source to each destination
    • Packet size distribution (bits/packet)
       
  • Questions:
    1. How long does it take the average packet to travel from source to destination?
    2. What is the probability that a packet will be dropped due to buffer overflow?

Queuing Theory

Unbounded M/M/1 Queue

  • Exponential distribution of interarrival times, λ = mean arrival rate
     
  • Exponential distribution of service times, μ = mean service rate
     
  • One server
     
  • Traffic intensity ρ = λ / μ
     
  • Mean queue length N = ρ / (1 - ρ)
     
  • Little's Theorem; applies to any unbounded queue: Mean waiting time T = N / λ
     
  • Mean waiting time T = ρ / (λ(1 - ρ)) = 1 / (μ - λ)

Unbounded M/G/1 Queue

  • Exponential distribution of interarrival times, λ = mean arrival rate
     
  • General (any) distribution of service times
    • μ = mean service rate
    • σ = standard deviation of service rate
       
  • One server
     
  • Traffic intensity ρ = λ / μ
     
  • Mean queue length N = ρ + ρ2 (1 + σ2/μ2) / (2 (1 - ρ))
     
  • Mean waiting time T = N / λ

Unbounded M/C/1 Queue

  • Exponential distribution of interarrival times, λ = mean arrival rate
     
  • Constant service time, μ = mean service rate, σ = 0
     
  • One server
     
  • Traffic intensity ρ = λ / μ
     
  • Mean queue length N = (1 - ρ/2) ρ / (1 - ρ)
     
  • Mean waiting time T = (1 - ρ/2) / (μ - λ)

Bounded M/M/1 Queue

  • Exponential distribution of interarrival times, λ = mean arrival rate
     
  • Exponential distribution of service times, μ = mean service rate
     
  • One server
     
  • Traffic intensity ρ = λ / μ
     
  • Maximum queue length = n
     
  • If ρ != 1:
     
  • Mean queue length N = (nρn+2 - (n + 1)ρn+1 + ρ) / ((ρn+1 - 1)(ρ - 1))
     
  • Mean waiting time T = (nρn+1 - (n + 1)ρn + 1) / (μ(ρn - 1)(ρ - 1))
     
  • Dropped fraction D = ρn(ρ - 1) / (ρn+1 - 1)
     
  • If ρ = 1:
     
  • Mean queue length N = n / 2
     
  • Mean waiting time T = (n + 1) / (2μ)
     
  • Dropped fraction D = 1 / (n + 1)

Packet Delay Time Measurement In RON

  • RCMP Timestamp Request and Timestamp Reply messages (patterned after ICMP)
     
  • Package edu.rit.ron.rcmp
  • Program for generating traffic and measuring packet delay (M/C/1 queuing system)
     
  • Package edu.rit.ron.delay
  • Package edu.rit.numeric.stat
  • Demonstrations
     
  • Configuration file "a101" (unbounded queue) 
    setAddress 101
addInterface 1 localhost 5671 localhost 5672 4800 2000000000
setRoute 102 1
  • Configuration file "a102" (unbounded queue) 
    setAddress 102
addInterface 1 localhost 5672 localhost 5671 4800 2000000000
setRoute 101 1
  • Queuing system parameters
    • Link data rate = 4800 bits/sec = 600 bytes/sec
    • Packet size = 60 bytes = 12 bytes RON header + 17 bytes RCMP Timestamp Request message header + 31 bytes content
    • Constant service time distribution
    • Mean service rate = μ = (600 bytes / 1 sec) x (1 packet / 60 bytes) = 10 packets/sec
    • Exponential interarrival time distribution
    • Mean arrival rate = λ packets/sec
       
  • java edu.rit.ron.delay.Delay01 a102
     
  • java edu.rit.ron.delay.Delay01 a101 142857 31 λ 102 1000
     
  • Results (theoretical mean packet delay from an M/C/1 queuing model) 
          Measured                        Measured                 Theoretical
      Interarrival                    Packet Delay             Packet Delay
      Time (msec)                     Time (msec)              Time (msec)
lam   Mean   StdDev   StdErr     mu   Mean   StdDev   StdErr   Mean
---   ----   ------   ------   ----   ----   ------   ------   ----
1.0    984      989    31.3    10.0    132     24.5    0.775    106
2.0    492      495    15.7    10.0    140     35.5    1.12     113
3.0    328      330    10.4    10.0    150     48.2    1.52     121
4.0    246      247     7.81   10.0    165     65.1    2.06     133
5.0    197      198     6.26   10.0    185     87.9    2.78     150
6.0    164      165     5.22   10.0    229    146      4.62     175
7.0    141      141     4.46   10.0    337    271      8.57     217
8.0    123      124     3.92   10.0    617    473     15.0      300
9.0    109      110     3.48   10.0   1970   1290     40.8      550
9.5    104      104     3.29   10.0   3920   2610     82.5     1050

Discrete Event Simulation

Discrete Event Simulation of a Network

Data Communications and Networks II 4003-541-70/4005-741-70 Spring Quarter 2006
Course Page
Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706
Home Page
Copyright © 2006 Alan Kaminsky. All rights reserved. Last updated 27-Apr-2006. Please send comments to ark­@­cs.rit.edu.