EE555, Homework #2, Due Feb 26 (for on-campus students) Feb 27 (for DEN students ONLY) 1. Consider a queuing system which caters to three different classes of Packets whose arrival processes are all Poisson. Priority 1 (Highest) packets has an average arriving rate of 0.25 Packets/sec and requires a deterministic service time of 1 sec. Priority 2 Packets have an average arriving rate of 0.05 Packets/sec and requires a deterministic service time of 5 sec. Priority 3 (Lowest) Packets have an average arriving rate of 0.02 packets/sec and requires a deterministic service time of 20sec. Find the average time spent waiting in the queue by a packet of each of the three classes for the following scheduling policies: a. Non-preemptive Priority policy (we derived this in class) b. Preemptive-Resume policy (you need to derive the equations yourself) Keep in mind the average residual time for those Packets in service is = E(S2)/2E(S) where S is the Service time. 2. The following schedule for a given flow lists for each second the number of packets sent between that time and the following second. The flow must stay within the bounds of a Token Bucket filter. What bucket depth does the flow need for the following token generating rates? a) 2 tokens/sec, b) 4 tokens/sec Time (Second) Packets sent 0 5 1 5 2 1 3 0 4 6 5 13. Suppose a router has accepted flows with the following Tspec, described in terms of Token Bucket filter, with token rate r tokens/sec and bucket depth b tokens. All flows are in the same directions and the router can forward one packet every 0.1 seconds. a) What is the maximum delay a packet may face? b) What is the minimum number of packets from the third flow that the router would send over 2 seconds assuming the flow sent packets at the maximum rate uniformly? r b 1 10 2 4 4 1 4. Consider a router handling fixed length packets using a token bucket burst control mechanism. Packets that arrive when there is no token available are marked. One token is added to the bucket at the end of each slot and the bucket depth is 5. The arrival process is defined by: Pk = Pr {k arrivals per slot}. For the case of P0 = 0.2, P1 = 0.4, P2 = 0.4. Assume that the system starts with a non-empty token bucket. a) Draw the complete Markov chain for the number of tokens available at the beginning of a slot. b) Solve the Markov chain and find the average number of marked packets/slot5. Consider the following stream of packets (all of length 3) to be served by a router from a (very large) shared buffer. Construct a Table (like the one we studied in class) with Departure Time; Mean Waiting Time, Mean Total Time for each group separately and also overall for the following Queuing disciplines. If departures occur at same time as arrivals, assume departures occur first. a) FCFS b) Non-Preemptive, Priority Queue (Group 2 has the higher priority) c) WFQ with group 2 getting twice the service rate as group 1 Packet Arrival Time P1.1 1 P2.1 2 P1.2 3 P1.3 4 P2.2 6 P1.4 8 P2.3 9 P2.4
View Full Document