ECEN4533    Final Exam    1 May 2006

1) Shown is a portion of a histogram of the application layer message size of Instant Message (IM) packet traffic.  This histogram is based on over 700,000 captured IM's.  The messages had an average size of 31.4 bytes, and standard deviation of 41.3 bytes.
[20] Do you feel the IM message size is Exponentially Distributed?  Explain.  [Answer:  Perhaps.  Except for the 1st three points, it looks somewhat exponential to the naked eye.  Additionally the plotted probabilities closely match those an exponential would be expected to generate.  For example P(X = 10) is approximately equal to Fx(10.5) - Fx(9.5) = 0.023.  P(X = 20) & P(X = 30) also closely match.  But, an exponential PDF should have identical mean and standard deviations, which this histogram does not have.  The IM message size might be approximated as exponentially distributed, but I'd also look to see if there was another closed form PDF expression that's closer.]

2) IPv6 has a "Flow Label" that contains a random number generated by a source.  Assuming that the source generates these numbers completely randomly...
[15] Compute the probability a source generates the same number twice in a row.  [953.7*10-9]
<<<<<>>>>>

3) Engineers with MegaMoron Communication's Traffic Police are evaluating two possible techniques for flagging out-of-compliance traffic on a proposed Packet over Ethernet (PoE) switch; a sliding window algorithm and Frame Relay's  Leaky Bucket algorithm.  These algorithms would operate on the input line cards that customers would connect to in order to use a PoE WAN.  Suppose, after a long idle period, five full sized Ethernet packets (1526 B) arrive on a 64 Kbps input at time t = 0, 0.250, 0.850, 1.530, and 1.72075 seconds.
[20] If a sliding window algorithm is used that keeps a continuous running tally of the amount of bytes input over the past 1 second, complete the plot over the time 0 to 2 seconds.  For example, the plotted point at t = 1.1 seconds should have a value equal to all the bits input from time t = 0.1 to t = 1.1.

[15] Suppose Frame Relay's Leaky Bucket algorithm is used instead, with Bc = 4 KB and Be = 8 KB.  Complete the plot over the period 0 to 2 seconds.

[5] Keeping in mind that a carrier PoE switch may have to monitor hundreds of input connections, from the point of view of computational complexity, which algorithm would you recommend be implemented?  Explain.  [The leaky bucket algorithm requires a counter, timer, & subtractor.  Can probably be implemented with simple logic gates.  The sliding window algorithm requires a counter, timer, cpu, & memory space to store packet arrival & departure times, & code.  It's much more complex.]

<<<<<>>>>>

4) A packet switch is passing traffic with two packet sizes.  35% of the time the packets are 855 bytes, and 65% of the time the packets are 110 bytes.  The sizes of packets arriving at the switch are statistically independent.  When the switch is running at a 60% load, there is one packet in the queue (waiting to be served) 41% of the time and two packets in the queue (waiting to be served) 59% of the time.
[10] Compute the average number of packets in the queue.  [1.59]
[10] Compute the standard deviation of the number of packets in the queue.  [0.4918]
[15] Compute the probability the switch queue size exceeds 200 bytes when the switch is running at a 60% load.  [0.7335]

<<<<<>>>>>

5) A packet switch connected to a 110 Kbps leased line trunk is fed 440 byte packets (on average).  The packet size and inter-arrival times are both known to be exponentially distributed.  If the average time in the switch is desired to be < 42 msec...
[15] Compute the maximum load ρ that can be placed on this switch.  [0.2381]
[15] Compute the carrying capacity for this system.  [0.2127]
[10] Explain to a non-engineer what "exponentially distributed inter-arrival time" means.  [If counts were made of the time between arrivals of each packet and its immediate predecessor, more of the times would be small than large.  A histogram of the times would have a decaying exponential shape, somewhat like the figure in problem 1.]
<<<<<>>>>>