Home

CPSC455/555

The following types of questions are representative of those that will appear on the February 16, 2006 exam. This is not an exhaustive list, merely a representative list.
  1. Definitions: You may be asked to define technical terms; conversely, you may be given technical definitions and asked to supply the corresponding terms.
  2. Categorization of routing-problem instances: You may be given an instance (solved or unsolved) of the interdomain-routing problem and asked whether it falls into a category that was covered in class and in the assigned reading. For example, you could be given a solved instance similar to the one on slide 25 of http://www.cs.yale.edu/homes/jf/FRS.ppt and asked whether it satisfies the Gao-Rexford conditions. The answer in that case is yes. If node 1 had assigned a value to 17245d, the answer would be no: Export of provider route 7245d by 7 to its provider 1 would violate Gao-Rexford scoping constraints.

    Similarly, you could be given the following unsolved instance and asked whether it is an instance of next-hop policy routing:

    In this case, the answer is no, because node a values abd differently from the way it values abcd, even though these two routes have the same next hop.

  3. You may be asked to explain the main contributions of various papers or results that are identified by authors' names. For example, you may be asked to explain how the Feigenbaum-Papadimitriou-Sami-Shenker formulation of the LCP routing problem improves on the Nisan-Ronen formulation or why the Parkes-Shneidman formulation improves on the Feigenbaum-Papadimitriou-Sami-Shenker formulation.
  4. Complexity results and their relevance: You may be asked to state the computational complexity of one or more of the categories of interdomain routing that we studied and explain its practical relevance. The question may also ask you to define this category of instances. For example, you may be asked to define the forbidden-set routing problem (see http://www.cs.yale.edu/homes/jf/FKMS.pdf for the definition), to say what its computational complexity is (NP-hard to approximate within any factor - see Theorem 2 of http://www.cs.yale.edu/homes/jf/FKMS.pdf and think about why it applies), and to explain the practical relevance of this complexity result (forbidden-set routing policies, although they appear to be simple and natural, are not a realistic option for BGP-compatible computation of routes and VCG prices; if, as this NP-hardness result tells us, approximately optimal routing trees cannot even be found efficiently in a standard, centralized computational model, where communication complexity and incentive compatibility are not potential obstacles, then a fortiori they cannot be found efficiently in the BGP-computational model, where these potential obstacles exist).
  5. You may be asked to apply and/or generalize the results or principles covered in class. For example, you may be asked to specify a VCG mechanism for a well-known problem (see, e.g., Problem 6 in http://zoo.cs.yale.edu/classes/cs455/2002/hw1.pdf and its solution in http://zoo.cs.yale.edu/classes/cs455/2002/hw1sol.pdf).
  6. You may be given one or more interdomain-routing instances and asked to compute the results of running one or more of the algorithms we studied (e.g., the FPSS algorithm or the FRS algorithm) on these instances.