Home

Schedule/Notes

Readings

Assignments

TA info

Policies

Homework #3: Router Design and Algorithmics
Assigned: Monday 10/26
Due Wednesday 11/4 4:30 pm (main CS office)

1. Longest prefix matching Consider the following routing table:

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

• Construct the binary trie representing this table.
  • Given address 0111 1100, what is the next port and how many memory accesses are required?
  • Address 1111 1111? 1100 1100?
• Construct the path compressed trie representing this table and give the number of memory accesses for the previous three addresses.
• Construct a multi-ary tree with a stride of two and give the number of memorey accesses for the previous three addresses.

2. Packet classification Consider the following 2-D classifier:

routing table

	DA	SA
R1	0*	01*
R2	0*	1*
R3	1*	10*
R4	11*	0*
R5	11*	01*
R6	01*	1*
R7	*	10*

• Construct the hierarchical trie and the grid of tries for this classifier both for the case that you place the SA field at the top level of the hierarchy and the DA field at the lower level, and the case that you place the DA field at the top level and the SA field at the lower level. Using the example, (000,100), how many memory accesses are required with each data structure and what rule is resolved?

3. Output queueing. Consider an N by N switch with queues at the outputs.

• Suppose that a packet arrives to input i, i = 1,...,N at each time slot with probability p and that it is destined for output j with probability 1/N. What is the expected queue length at output j? What is the maximum value of p so that the expected queue lengths at all queues are finite?
• Suppose that a packet arrives to input i, i = 1,...,N at each time slot with probability p but that now it is destined to output j with a probability that is inveresely proportional to j. Again, what is the expected queue length at output j? What is the maximum value of p so that the expected queue lengths at all queues are finite?
• Consider now an N by N switch that handles multicast packets. A packet arrives to input i, i = 1,...,N at each time slot with probability p. Each packet generates k copies with probability 1/N, k = 1,...,N. And when k copies are made, they are destined to any set of k output queues with equal probability.
  • What is the average fanout, i.e., average number of copies made per packet?
  • Given that a packet arrives, what is the probability that it has a copy destined for output 1? What is the average arrival rate of copies to outpiut 1?
  • What is the expected queue length at output j? What is the maximum value of p so that the expected queue lengths at all queues are finite?

4. Maximum throughput of bufferless IQ switches.

• Consider an N by N IQ switch without buffers at the input. In a slot, if there is more than one packet at the inputs for a destination, only one of them is transmitted to the output, and the others are dropped. In the next slot all inputs get a new packet. As usual, assume indpendent and uniform routing. What is the maximum link utilization of such a switch?
• Consider an M by N IQ switch without buffers at the input. Packets arrive at each input according to a Bernoulli process with rate p. In other words, a packet arrivals are independent from slot to slot and a packet arrives during a slot with probability p. Let q(i) denote the probability that i inputs are active in a slot. Clearly q(i) has a binomial distribution.Assume packets are routed uuniformly (all output destinations are equally likely). Let E(i) denote the number of packets swithed in a slot when there are i active inputs. Show that E(i) = n[1-[(n-1)/n]ⁱ]. Using q(i) and E(i), find the maximum utilization, U, and the probability that a packet is not dropped, P_succ, by taking limits as M, N go to infinity while M/N is a constant.