CS 356 (Lam), Fall 2013

Homework 1 (Due at beginning of class on Sept. 18, 2013, Wed.)


Problem 1 

Consider N users who share a communication link.  Suppose each 
user transmits a fraction p of the time, i.e., at any time 
instant, each user is transmitting with probability p.

The probability that at any time instant, n users are
transmitting is given by the Binomial distribution:

Prob{number of users transmitting = n} = C(N,n)pn(1-p)(N-n)
where C(N,n) = N!/[n!(N-n)!]
i. What is the probability of more than 12 users transmitting at the same time? (5 pts)
ii. What is the probability of less than 5 users transmitting at the same time? (5 pts)
iii. Suppose p = 0.1 and N = 35. Calculate the numerical values of the probabilities in parts i. and ii. (10 pts) (You might need to write a small program to do this.) Problem 2 Consider a path from node 0, through nodes 1, 2, ...,K, to node K+1. The channels, from node i to node i+1, for i = 0, 1, ..., K, have the same capacity and propagation delay: C channel capacity in bits/second p propagation delay in seconds Consider packets, each of which has h header bits and L information bits. The delay of a packet from node 0 to node K+1 is defined to be the duration from when the last bit of the packet leaves node 0 to when the last bit of the packet arrives at node K+1. Suppose the delay also includes a processing time of q seconds in each of nodes 1, 2, ..., K. The processing time includes waiting time in queue. Part I. (10 pts) Draw a picture to show that the delay D of a packet from node 0 to node K+1 is given by the following formula: D = p + K [ (L+h)/C + p + q ] Now, suppose that each packet is segmented into n cells, each of which has L/n information bits and h header bits. Each cell still requires a processing time of q seconds in an intermediate node. Suppose that the n cells of a packet are transmitted from one node to the next with no gap between consecutive cells, i.e., transmission of the last bit of a cell is immediately followed by transmission of the first bit of the next cell. (A node has multiple processors and can process the output of one cell and the input of another cell concurrently.) Segmenting packets into cells has the advantage of pipelining, namely: as soon as a cell is completely received by node i, node i can process and transmit the cell to node i+1 without waiting for the rest of the packet. This observation is to be illustrated by the following analysis. Part II. (10 pts) Draw a picture to show that the delay of a packet that has been segmented into cells is given by the following formula: D(n) = p + K [ (L/n + h)/C + p + q ] where D(n) is defined to be from when the last bit of the packet's last cell leaves node 0 until the last bit of the last cell arrives at node K+1. Part III. (10 pts) For p = q = 0.001 second L = 10,000 bits C = 1,000,000 bits/second h = 100 bits Perform the following computations: 1. Calculate delay for K = 10, n = 1 2. Calculate delay for K = 10, n = 20 3. Calculate delay for K = 4, n = 1 4. Calculate delay for K = 4, n = 20 Part IV. (10 pts) Plot the following: 1. For K = 10, plot delay as a function of n, for n = 1, 2, 3, ..., 40. 2. For n = 20, plot delay as a function of K, for K = 1, 2, 3, ..., 20.