Note: The exam will be closed book, closed notes.

1. What are the three most important things that routers do?
   • compute routes
   • forward packets
   • security/congestion control/QOS
2. List three issues arising in the design of a router
   • design cost
   • manufacturing cost
   • deployment cost
3. Why is the maximum size of an Ethernet frame 1518 bytes? Would there be any advantage to a larger frame size?
   • Memory used to be very very expensive. Larger packets would be more efficient (less overhead in the header, less processing at destination).
4. Why is there a 10$\times$ range in the price of Fast Ethernet switches?
   • MAC cache size, buffer memory, redundancy, quality of management software
5. What are the primary differences between core routers and enterprise routers?
   • core need reliability and speed; enterprise needs lots of ports for cheap, security, QOS
6. Describe an architecture for computing longest prefix matching using 16 MBit DRAMs
   • talk about table expansion, exceptions \& the digital logic needed to process them, update mechanisms
7. How would you use balanced BSTs to perform longest prefix matching?
   • Can't use directly (since we're not doing exact matches). One idea might be to keep a number of BSTs, one for each distinct length, then add markers a la the binary search on hashes we saw.
8. How does the performance of bus-based fabrics scale with the number of attached cards?
   • electrical delay increases to the square of the number of cards - length increases linearly, so resistance and capacitance both grow linearly. then there's linear growth in the traffic itself, so availablity drop off.
9. What is the primary advantage of a crossbar over a ring?
   • handles multiple transfers concurrently
10. Show greedy routing on an N node array with no more than one packet for any destination completes in N steps
    • need to talk about interference and critical packets
11. Show that the greedy algorithm routes permutations in order root(N) on an N node butterfly
    • use bound on number of paths sharing an edge, add up geometric series