Proof of Theorem 1
	v When a packet arrives in a time slot it must choose a memory not chosen by 1. The N – 1 other packets that arrive at that timeslot. 2. The N other packets that depart at that timeslot. 3. The N - 1 other packets that can depart at the same time as this packet departs (in future). v Proof: Ø By the pigeon-hole principle, 3N –1  memories that can perform at most one memory operation per time slot are sufficient for the router to be work-conserving
				10