Homework #12 Solutions
cs349 -- Networks

35) n/2 log n      (that's log base 2)

36) Let's do some math!

The complexity of a Batcher network is given by a recurrence
relation:

f(n) = 2 * f(n/2) + 1/2 nlogn

In other words, an nxn Batcher network is 2 n/2 x n/2 Batcher
networks plus an interconnect that takes 1/2 nlogn pieces.

It is not generally easy to solve these things, but if you
can guess the correct functional form, then you can plug it
in and solve for the particular coefficients.

For example, we might have a wild hunch that the answer looks like:

f(n) = a * nlog2n + b * nlogn

Where a and b are the parameters we have to find and log2n is
my notation for "log squared of n".

Finally, it will be useful to realize that

log (n/2) = logn - 1             (all logs are base 2)

So,

f(n/2) = a n/2 log2 n/2 + b n/2 log n/2
       = a n/2 (log2n - 2logn + 1) + b n/2 (logn - 1)

So if the recurrence relation is true, then we need

f(n)              =     2 * f(n/2) + 1/2 nlogn

Plugging in, we get:

a nlog2n + b logn = a nlogn2n - 2 a nlogn + an
                  +               b nlogn - bn
                  +             1/2 nlogn

Notice that I have written similar terms in columns.
That's because in order for this equation to be true,
we need all the nlog2n terms to add up, and all the
logn terms to add up, and all the n terms to add up.

In other words, we need:

   a = a
   -2a + b + 1/2 = b
   a - b = 0

Solving these equations, we get a = 1/4, b = 1/4.

Checking for f(2) and f(8)

f(2) = 1/4 2 1 + 1/4 1 = 1

f(8) = 1/4 8 9 + 1/4 8 3 = 24

Both are correct.


Chapter 4

2) By measuring the offset in 8-byte chunks, we can use 13
   bits to refer to addresses up to 2^16, which is the max
   size for an IP packet.

   Also, it means that fragments fall on 8-byte boundaries.

3) At the first hop it gets broken into three packets
   that look like

        IP   TCP   data
   14	20   20    970
   14	20   20    970
   14	20   20    108

   At the second hop, each of the first two fragments gets
   refragmented like

   8	20   20    464
   8	20   20    464
   8    20   20    42

   And the third fragment gets forwarded without further
   fragmentation

   8    20   20    108

   So the total number of fragments that arrive at the destination
   is 7.