CS 356 (Lam), Fall 2017

Homework 1 (Due at beginning of class on Sept. 14, 2017, Thurs.)

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 (small packets),
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.