Transcript ppt
Providing Guaranteed Services without Per Flow Management • Today’s Internet offers best-effort delivery service and IP routers are stateless (except coarse-grained routing state) ==> scalable and robust • Solutions for better services - stateless, e.g. RED for congestion control, Diffserv for QoS - stateful (per flow management), e.g. FQ, Intserv • Stateful solutions provide more powerful and flexible services, but require per flow state, classification, buffers and scheduling • Goal: want to emulate stateful services (per flow bandwidth and delay guarantees) at the cost of stateless solutions (only edge routers perform per flow management) Dynamic Packet State (DPS) • • • • Ingress router computes and inserts per flow state in packet’s header Core router processes packet based on its state and node’s state Core router updates both packet and node’s state Egress router removes state from packet’s header Reference Stateful Network • Want to emulate a network where - each router implements Jitter-VC discipline on data path - each router performs per flow admission control on control path • On data path, use DPS to approximate Jitter-VC with Core-JitterVC, where core routers do not maintain per flow state Jitter Virtual Clock • • • • • Delay-jitter rate-controller + VC scheduler Assign each packet eligible time and deadline Keep packet in rate-controller until it becomes eligible Schedule packets in increasing order of their deadlines A network of Jitter-VC servers can provide the same guaranteed service as a network of WFQ servers • Intuition: eligible time and deadline of a packet in a flow with reservation r <==> start and finish time of transmitting the packet in an ideal network in which flow has dedicated links of capacity r • Eligible time = max of * arrival time + ahead time = (departure time at previous router + prop delay) + (deadline at previous router - departure time) = deadline at previous router + prop delay * deadline of previous packet (this is the per flow state!) • Deadline = eligible time + (packet length / flow reserved rate) Core-Jitter VC • Goal: eliminate per flow state at core routers - eliminate dependence on previous packet deadline • Solution: introduce a slack variable s, such that at each core router packet deadline at previous router + prop delay + s >= deadline of previous packet for every packet • Then eligible time = packet deadline at previous router + prop delay + s • s is inserted in packet’s header by ingress router, depends on - lengths of previous and current packets - slack of previous packet - number of hops (known at admission control time) • Each packet carries its slack, flow reserved rate, and ahead time at previous router • No per flow classification and no per flow scheduling state No per Flow Admission Control • Goal: light-weight signaling protocol that does not require core routers to maintain per flow state (the reserved rate of the flow) • A router admits a reservation r, if r <= C - R • Solution: maintain aggregate reservation R • Problem: requires per flow state to handle partial reservation failures and message loss (to maintain consistency) • Solution: Estimate aggregate reservation Re • Account for approximations and compute upper bound Rb, Rb>= R • Admit a reservation if r <= C - Rb Estimate Aggregate Reservation • If all flows were sending at their reserved rates, computing Re is trivial; just measure traffic throughput • Problem: what if flows do not send at their reserved rates? • Solution: Associate with each packet a virtual length - virtual length = r * (time now - transmit time of previous packet) • Use virtual lengths instead of actual lengths to compute Re • Ingress router inserts virtual length in packet’s header • Core router uses virtual lengths to compute Re on each output link • Re can underestimate R, because it ignores jitter and packet inter-departure times, and reservations accepted or terminated in the middle of an estimation interval Computing Upper Bound • Rb = (sum of virtual lengths / estimation interval)/(1-f) + Rn where f = (max inter-departure time + max jitter) / estimation interval Rn = new reservations made during estimation interval • The estimation algorithm is robust in presence of control message loss and duplication - their effect is “forgotten” after one time interval • If no packet of a flow departs during a predefined interval (i.e., maximum inter-departure time), ingress router generates a dummy packet Implementation • Where to insert the state? • Possible solutions: - between link layer and network layer headers - as an IP option - find room in IP header (e.g. TOS byte and fragment offset)