Homework #7 Solutions
cs349 -- Networks

Questions 33, 36, 37, 41 from Chapter 2

33) Why is it important for protocols configured on top
    of Ethernet to have a length field in their header?

Because there is a minimum frame size, small messages have
to be padded, meaning that the end of the frame is not
necessarily the end of the message.

BTW, how does Ethernet know where the end of the frame is?

36) Suppose the rt prop delay for Ethernet is 46.4 us.
This yields a minimum packet size of 512 bits.

a) What happens when the signalling rate goes to 100 Mbps
   (from 10 Mbps)?

   Now it's 4640 bits for the prop delay and 48 bits of
   jam, for a total of 4688 bits

b) What are the drawbacks of so large a minimum packet size?

   Lots of wasted time tranmitting padding bits, and added
   latency for small messages.

c) How might the specs be rewritten to reduce the minimum packet size?

   If the maximum length of the network is smaller, then the
   max prop time is smaller and the frames could be smaller.


37) A and B have collided once, and A won, so A has sent a packet
    and B has suffered one collision.

    After A's first packet, A and B collide again:

a) What are the chances that A wins this faceoff, too?

   A is choosing from 0, 1
   B is choosing from 0, 1, 2, 3

   There are 8 possible outcomes.
   There are 5 ways for A to win immediately.
   There is only 1 way for B to win.
   There are two ways they might tie.

   So A's probability is  5/8 + p * 2/8

   Where p is the chance that A will eventually win the ties.

   We know that p is at least 1/2, so A's chances are at least 6/8.

b) Assuming that A wins, and that after A sends a frame, A and
   B collide again, what are A's chances?

   A is choosing from 0, 1
   B is choosing from 0, 1, 2, 3, 4, 5, 6, 7

   There are 16 outcomes.
   Again, 2 ties.
   Again, 1 way for B to win.
   That leaves 13 ways for A to win.

   Now A's chances are better than 14/16 = 0.875

c) Give a lower bound for the chance that A wins all remaining
   faceoffs.

   The chance of winning the next one is 1 - 1/16 = 0.9375
                    Then the next one is 1 - 1/32 = 0.969
                    Then the next one is 1 - 1/64 = 0.984
                      and so on...

   The product of that series is (very) approximately 0.88

d) What happens to frame B1?

   Hosed.


41) Suppose Ethernet addresses are chosen at random.

a) What is the chance that two hosts out of 1024 will
   have the same address?

                  1 + 2 + ... + (n-1)
   roughly   1 -  -------------------
                          m

   where n is the number of hosts (1024) and m is the total
   number of addresses (2^48 =~ 2 * 10^14)

   the sum from 1 to n of i is n/2 (n-1) = 523,766

   p = 1.9 * 10-9    (very unlikely)

b) What is the chance that that will happen if we try 2^20 times?

   Easier to ask what is the chance of failing 2^20 times in
   a row.

   Chance of failing once is 1-p = 0.9999999981

   Raise that to the power of 2^20, you get 0.9981

   Which means that the chance of picking two with the same
   address is still only 0.00195 (not too bad, but it depends
   on what the consequences are).

c) What is the prob that any two of 2^30 have the same address.

   Unfortunately, the approximation fails for such large n.

   So I wrote a java program to compute it:

public class Compute {

    public static void main (String[] args) {
	int n = 1024;
	double m = Math.pow (2.0, 48.0);
	double prod = 1.0;
	    
	for (int i=0; i<n-1; i++) {
	    System.out.println (1.0 - i/m);
	    
	    prod *= 1.0 - (double) i / m;
	}
	System.out.println (prod);
    }
}

This program confirms that the answer to part (a) is

   0.9999999981428083   (very good chance of no pairs)

Then with n = 2^30:

   6.47582E-319  (vanishingly small chance of no pairs)