
                      Computer Science 825
                         Quiz B           Name _______________________

1. Suppose the Bellman-Ford routing algorithm is being used and station
   B receives the following routing updates from neighbors A, C and E
   Suppose BA delay = 3, BC delay = 6 and BE delay = 5.
   Complete the routing table for B.,

      A  C  E      Cost VIA
   A  0  6  9          |
   ------------   ----------
   B  5 11  2          |
   ------------   ----------
   C  3  0  9          |
   ------------   ----------
   D  8  5  2          |
   ------------   ----------
   E  6  8  0          |
   ------------   ----------
   F 11  2  7          |
   ------------   ----------

3. Suppose a new virtual circuit is to be set up and that it goes
   from the host at switch D to the host at switch E following the
   route D -> F -> B -> A -> E.  Update the VC assignment tables.






















4. Order the following broadcast algorithms according to the number
   of packet transmissions needed to complete a broadcast (1 = least
   transmissions; 3 = most).

   ______ a. Reverse Path Forwarding

   ______ b. Spanning tree.

   ______ c. Flooding



5. Suppose network addresses are 24 binary digits and all network
   addresses are in use.

   a. How many entries must a flat routing table have. (A flat
      routing table has an entry for each node in the network).



   b. Suppose a hierarchichal addressing/routing scheme is used
      in which the 24 bits are partitioned as a 6 digit region
      code followed by a 8 digit locality code followed by a 10 digit
      local address.  How many routing table entries are now
      required?



6. In another network that uses SPF suppose station A constructs the
   following cost matrix

       A   B   C   D   E

   A   0   2   -   3   4

   B   2   0   6   -   9

   C   -   6   0   7   2

   D   3   -   7   0   4

   E   4   9   2   4   0


   Draw the routing tree from node C to all destinations.
   Label the ARCs of the graph in the order in which they
   are made permanent in the SPF algorithm.


7. Let N = number of nodes in a network and M = the average number
   of links / node.

   a. The size of a routing info packet in Bellman-Ford is of order

      1. M      2. N      3. N ^ 2       4. N ^ M

   b. The size of each routing update packet transmitted in an SPF net is
      of order

      1. M      2. N      3. N ^ 2       4. N ^ M


   c. In terms of computational complexity the SPF algorithm as performed
      by a single node is of order.

       1. M    2. N     3. N ^ 2    4. M ^ 2    5. N ^ M


   d. The minimum number of routing packets transmissions at each complete
      exchange in SPF within the entire network is of order:

       1. M    2. N     3. N ^ 2    4. M ^ 2    5. N * M





