• This is an open-book, open notes exam. You may also use Internet resources if you want. You can not discuss the exam with anyone, either in or outside class.
• If you have any questions about the exam, email them to me (I will check mail at least once a day). I will update the exam (to make clarifications) as needed and as questions arise, so check the copy of the exam on the www site frequently. I'll only add clarifications; I won't add or delete any questions.
• The exam is due by 5PM on Thursday November 12.
• Your solutions should be written up using a word processor (like Word or LaTex). No handwritten solutions will be accepted.
• Each answer should be no more than 2 or 3 pages long (and in many cases, you do not need nearly this maximum amount of space to answer the question).
• Please explain your answers, to give me an idea of your thinking and provide enough information to let me know that you understand the ideas behind the questions being asked. In this case, you can get partial credit even if your answer isn't right.

Good luck and have fun.

Problem 1: Voice mail.

Consider the telephone network and its SS7 signaling network. Suppose we want to implement an anycast (666) service in such a network. A telephone number with area code 666 is associated with a service and a user that calls this number is connected to a server that provides this service. More specifically, assume that a set of telephone numbers is associated with the 666 number. The 666 number is then mapped into one of these numbers, which in turn is connected to a server that can provide the service. Suppose that there are k such numbers and that each number can support exactly one caller

1. Sketch out how such a service could be implemented (it need not be the way it actually is implemented in today's telephone network), indicating the roles of the end systems (caller, callee), SSPs, SCPs, and STPs. List the steps taken from when the caller first goes off-hook to the point when the message is recorded. Explain the purpose of each signaling message used, and indicate which steps occur in the SS7 signaling network, and which steps occur in the data (telephone trunk line) network.
2. Now suppose this service is implemented in an IP network. Sketch out how such a service could be implemented, indicating the roles of the end systems (caller, callee), and any additional servers required. You need not go into lower level transport issues (e.g., how a TCP connection is established). Instead, focus on how the service is implemented at the application layer. List the steps taken from when the caller first goes off-hook to the point when the message is recorded. Explain each type and purpose of signaling message used.

Problem 2: Randomization and Indirection.

Read the paper, A. Keromytis, V. Misra, D. Rubenstein, "SOS: Secure Overlay Services," SIGCOMM 2002. You only need to read sections 1-3. What uses of randomization and indirection are used in this protocol? Pick two examples of randomization and indirection that we studied in class, and compare and contrast the use of randomization and indirection in SOS, and those taken from class. What other design principles are used by this protocol?

Problem 3: Delay bounds in a leaky-bucket controlled multiplexer

Consider a leaky bucket policer that polices the average rate r and burst size b of a packet flow.

1. Suppose that we now want to police the peak rate, p, as well. Show how the output of the leaky bucket policer in slide 4-89 of note set #5 can be fed into a second leaky bucket policer to so that the two leaky buckets in series police the average rate, peak rate, and burst size. Be sure to give the bucket size and token generation rate for the second policer.

2. Argue why the maximum delay through the multiplexer (once a packet passes through the leaky bucket) is approximately b/C. Assume that the multiplexer queue is initially empty.

Now consider a non-preemptive priority queue with two classes of input sessions, one receiving low priority, the other receiving high priority. High priority packets always always receive priority over low priority packets waiting in the queue. Packets within each class are served in FIFO order.

3. Consider the case where there is exactly one low priority session and one high priority session, each controlled by a leaky bucket with identical parameters (r,b). What is the relationship between r and C that ensures that the maximum delay through the multiplexer is finite for both the high and low priority classes of traffic? (Assume that b is finite)
4. What is the maximum delay of a high-priority packet? What is the maximum delay of a low priority packet?

Problem 4: Multibit trie prefix matching.

Consider the routing table from Homework #3:
 

routing table

	prefix	port
P1	0*	A
P2	11*	B
P3	010*	C
P4	111*	D
P5	01100*	E
P6	11001*	F
P7	011011*	G
P8	111001*	H
P9	1110011*	I
P10	110000*	J
P11	00101*	K

and the trie representation that you developed when solving the homework problem. In the following, you will consider k-ary tries and generalized tries with (possibly) different stride sizes at different levels. For these trees assume that each node must store a next hop pointer (if it is a prefix) and pointers its k children (for k-ary tries) (k + 1 memory locations per node). Suppose that you decide to encode this table in a two-level trie. How would you do this and what would the minimum number of memory locations be? This will require carefully going through the Srinivasan, Varghese paper. What is the minimum number of memory locations required for a three level representation of this table? How do these compare to the number of locations required in a binary trie, a 4-ary trie, and a 8-ary trie. Compute the number of memory accesses required to resolve the addresses 1110 0000, 0010 0000, and 1000 0100.

Problem 5: Input queue architectures.

1. Consider an N×N input-queued switch with virtual output queues (VOQs) at each input. For each i, there are an infinite number of packets in VOQ(i,i) and VOQ(i,(i + 1) mod N). Thus, input 1 has packets for outputs 1 and 2, input 2 has packets for outputs 2 and 3, ..., and input N has packets for outputs N and 1. Let M1 be the matching that connects input i to output i, and M2 the matching that connects input i to output (i + 1) mod N.
   • Consider the following scheduling algorithm: At each time slot either matching M1 or matching M2 is used with equal probability, and independently from time slot to time slot.
     • What is the maximum throughput per port?
     • Let T be the number of slots that a packet remains at the HoL before being served. Determine P(T = k), for k = 1, 2, ....
   • Consider the following iterative algorithm: At the beginning of each time slot each input requests one of the two outputs for which it has packets with equal probability. An output that receives multiple requests grants to one of the requesting inputs with equal probability. The matched input-output pairs are removed from further consideration. The unmatched inputs then issue new requests to the unmatched outputs and repeat the procedure until no more matchings are possible. Then packets are transferred from an input to the output it is matched with.
     Assuming that N = 4, what is the maximum throughput per port?
   • Suppose the distributed algorithm introduced in part second part is implemented in an N × N switch, where N is arbitrary.
     • Prove that the maximum possible throughput per port is at least 75%.
     • Find a value of N for which the throughput is strictly bigger than 75%.
   
   
2. Consider an input-queued switch with N input interfaces and N output interfaces, and VOQs at each of the inputs.
   • Recall that a maximal match is one where each input either is a part of the match, or all the outputs that it can possibly connect to are already matched to other inputs. Give an example where the maximal match is not a maximum match.
   • Notice that the maximal match you produced has at least half the number of edges of the maximum match. Can you produce a maximal match where the number of edges is strictly less than half the number of edges in a maximum size match? If not, prove the following statement: Every maximal match is at least half the size of a maximum size match.
   • Provide an efficient algorithm that produces a maximal match. What is its complexity?
   • What implications do the above results have on building VOQ switches whose switching fabrics have higher bandwidths than input and output links?