E6998-02 Homework 5

Out: 21 November 2002


Due: 10 December 2002 at 3am EDT. You have three weeks. Start tonight, ask questions if you have problems.


The purpose of this homework is to test your understanding of Interdomain routing. You answers should be short and concise; don't write a dissertation!

Part I: Review of BGP
Answer these questions very briefly (0-2 lines). Their main purpose is to help you review the material.
  1. What is an Autonomous System (in the context of Interdomain Routing)?
  2. List three reasons why EGP was abandoned in favor of BGP.
  3. We say that BGP is a Path-Vector protocol. What does that mean? How does it differ from a Distance-Vector protocol? How does it differ from a Link-State protocol?
  4. List all BGP message types (names and RFC or I-D in which they are specified).
  5. List all BGP Path Attributes (names and RFC or I-D in which they are specified).
  6. What does the BGP KEEPALIVE message do? Although it is used in all situations, is it always necessary?
  7. v
  8. Why is the ORIGIN attribute needed? What would break (or work less well) if ORIGIN could be omitted?
  9. Why is the AS_PATH attribute needed? What would break (or work less well) if AS_PATH could be omitted?
  10. Why is the NEXT_HOP attribute needed? Under what circumstances could it be omitted without anything breaking?
  11. What are the differences between I-BGP and E-BGP?
  12. What are the similarities between I-BGP and E-BGP?
  13. In an AS that is running I-BGP, is OSPF still needed?
  14. What is a multihomed network?
  15. Can an AS be at the same time a transit network and a non-transit network? Explain.

Part II: Understanding BGP Route Selection
Consider the following network:

  • AS1, AS2, and AS3 are ISPs, peering with each other at the links between routers J-K, N-A, and D-G.
  • AS6 is a customer of AS1 and AS3. Two more customer networks are shown.
  • All routers are shown. All links between routers are shown. All networks are running OSPF as their IGP, and all link costs are equal.
  • All providers are running I-BGP.
  • The prefix for AS6 is 12.2.0.0/16. The prefix for AS65432 is 135.207.16.0/20. The prefix for the nameless customer containing router S and host d is 192.20.225.0/24.
  • AS1, AS2, and AS3 number their routers out of 1.0.0.0/8, 2.0.0.0/8, and 3.0.0.0/8, respectively. The loopback address of each router has the ascii value of the letter given in the figure as its last octet. For example, router G is 3.0.0.71.
  1. What path (list of routers they go through) does traffic from host c to host d follow?
  2. What path does traffic from host d to host c follow?
  3. Suppose that AS6 announces its entire prefix out of both X and Y, and that it receives full BGP tables from its providers. What is the path from a to b? From a to c? From a to d? From c to a? From d to a?
  4. Now suppose that AS6 announces the lower half of its address space (12.2.0.0/17) from the X-E link, and the upper half from the Y-C link. Let a's IP address be 12.2.33.65, and b's IP address be 12.2.192.66. What is the path from a to b? From a to c? From a to d? From c to a? From d to a?
  5. What is undesirable about the flow of traffic in the previous question? Give two different ways to fix it.
  6. How would AS6 tell the world that it prefers receiving traffic for the upper half of its address space only via the C-Y link, unless of course it is broken? List just the obvious way. For extra credit, define some communities, and make sure that traffic to the upper half only flows through the C-Y link.

Submit the homework via email to ji+hw5@cs.columbia.edu. Do not send anything other than plain ascii text of a .pdf file. Do not send to any other address, or your submission will be ignored. Any submissions received after the deadline will be ignored. After means even a second after 3am. If in doubt, submit early; if there are duplicate submissions, the latest one (that's still before the deadline) will be the only one that I shall read.


$Id: $