Schedulingandqueuemanagement详解.pptVIP

Scheduling and queue management Analogous to OS scheduling and memory management…but slightly different characteristics (packets on lines, not processes on CPU) - certain simplifications (like it ain’t the halting problem:) Traditional queuing behaviour in routers Data transfer: datagrams: individual packets no recognition of flows connectionless: no signalling Forwarding: based on per-datagram, forwarding table look-ups no examination of “type” of traffic – no priority traffic Traffic patterns Questions How do we modify router scheduling behaviour to support QoS? What are the alternatives to FCFS? How do we deal with congestion? Scheduling mechanisms Assume all the previous gubbins (int or diff, and 5-tuple indexed or mark indexed) multiple queues - how to pick which queue to look at next based on flow state/history and requirements? Scheduling [1] Service request at server: e.g. packet at router inputs Service order: which service request (packet) to service first? Scheduler: decides service order (based on policy/algorithm) manages service (output) queues Router (network packet handling server): service: packet forwarding scheduled resource: output queues service requests: packets arriving on input lines Scheduling [2] Simple router schematic Input lines: no input buffering Packet classifier: policy-based classification Correct output queue: forwarding/routing tables switching fabric output buffer (queue) Scheduler: which output queue serviced next FCFS scheduling Null packet classifier Packets queued to outputs in order they arrive Do packet differentiation No notion of flows of packets Anytime a packet arrives, it is serviced as soon as possible: FCFS is a work-conserving scheduler Conservation law [1] FCFS is work-conserving: not idle if packets waiting Reduce delay of one flow, increase the delay of one or more others We can not give all flows a lower delay than they would get under FCFS Conservation law [2] Example ?n : 0.1ms/p (fixed) Flow f1: ?1 : 10p/s q