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.
- 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?
- After the second round of table exchanges, what are the routing tables at nodes A and E?
- What are the final routing tables at nodes A and E?
- 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?
- 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.
- 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?
- For a general network with n nodes, estimate how many table-update messages a node will send in the wired and wireless case.
- List the sequence of steps involved in sending a packet from the network layer in node A to the network layer in node D.
- 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.
- Will this result in a functioning network layer with a useful routing table at each node?
- List at least 5 problems that may arise with this naive implementation.
- For each problem item you listed above, briefly propose a way to address it.