|CS-534: Packet Switch Architecture
|Department of Computer Science
© copyright: University of Crete, Greece
|[Lecture: 6.2 Per-flow queueing and credit flow control]||[printer version - PDF]|
(a) If flow 1 is the only flow going out through output 1, what is the delay from the moment the first byte of flow 1 arrives at S, to the moment the last byte of flow 1 departs from S? Assume that the enqueueing and dequeueing delay of S is negligible.
(b) Now assume that output 1 carries 8 active flows: flow 1 as before, plus flows 2 through 8 which arrive on inputs 2 through 8, respectively. Flows 2 through 8 were idle until the moment the first byte of flow 1 arrived, but then, unfortunately, they all became suddenly active, carrying traffic at their peak arrival rate, which is 100 Mbps for each of them. Assume that the buffer of output 1 is large enough so that it does not overlow during the time that it takes for all packets of flow 1 to arrive. How many bytes of packets belonging to flows 2 through 8 will be queued in output queue 1 between the first and the last byte of flow 1's message? (Assume, for simplicity, that the bytes of individual flows arrive uniformly spread in time, i.e. ignore their clustering in packets of varying sizes). How long will it take for all these bytes to depart through output 1? Subsequently, what is now the delay for the message of flow 1? How does it compare to the delay in (a)?
(c) Now assume that output 1 uses per-flow queueing , i.e. it has (more than) 8 separate (logical) queues, one for each of flows 1 through 8, and that it performs round-robin scheduling among its non-empty queues. For simplicity, assume that all 8 flows carry packets of the same size, and that this common packet size is 1500 Bytes. How long does it take for one packet to depart through output 1? Call this a "packet time". In the worst case, a packet of flow 1 that arrives into an empty flow-1 queue will have to wait for 7 packet times before it receives service, because it happened to arrive just after the round-robin pointer passed over its queue and found it empty. What is this worst-case queueing delay for a flow-1 packet, assuming it was the head packet in its queue? Every how often does a new packet of flow 1 arrive through input 1? Given your last two answers what do you conclude: when each flow-1 packet arrives, does it find an empty or a non-empty flow-1 queue? Based on the above findings, what is now the delay for the message of flow 1? How does it compare to the delays in (a) and (b)?
|Up to the Home Page of CS-534
University of Crete, Greece.
Last updated: 20 May 2011, by M. Katevenis.