Main / CoursesESHw2

SFSU Engr 844 - Spring 2013 - Homework 2

Prof. Seapahn Megerian

For the questions below, consider the network with nodes A, B, C, D, E, and the given bi-directional communication link costs:

  • A-B: 1
  • A-E: 4
  • B-C: 1
  • B-E: 2
  • C-D: 4
  • D-E: 1

Assume that initially, all nodes know about themselves, their immediate (1-hop) neighbors, the cost of communicating with each neighbor and that they are going to do Bellman-Ford (distance-vector) routing.

  1. After the first round of table exchanges (i.e. each node sends its current table to all its neighbors and receives a table from each neighbor), what are the routing tables at nodes A and E?
  2. After the second round of table exchanges, what are the routing tables at nodes A and E?
  3. What are the final routing tables at nodes A and E?
  4. Assuming the network will never have more than 255 nodes, and that link costs are also in the range 0-255, how many bits do you need to store the routing table in each node?
  5. Assuming this is a wired network, how many table-update messages are sent by each node until the route computation in this specific network converges? Note that in a wired network, each node has to send a separate update to each neighbor.
  6. Assuming, this is a wireless network where a node only needs to send its table just once and all its neighbors hear it, how many total table-update messages are sent by each node?
  7. For a general network with n nodes, estimate how many table-update messages a node will send in the wired and wireless case.
  8. List the sequence of steps involved in sending a packet from the network layer in node A to the network layer in node D.
  9. Consider a naive implementation of an embedded wireless network system such as the one above that has each node send one table-update as soon as it powers up and any time it receives a table-update.
    1. Will this result in a functioning network layer with a useful routing table at each node?
    2. List at least 5 problems that may arise with this naive implementation.
    3. For each problem item you listed above, briefly propose a way to address it.