Conges'on(Control(Reading:(Sec'ons(6.1‐6.4(COS(461:(Computer(Networks(Spring(2009((MW(1:30‐2:50(in(CS(105)(Mike(Freedman(Teaching(Assistants:(WyaM(Lloyd(and(Jeff(Terrace(hMp://www.cs.princeton.edu/courses/archive/spring09/cos461/(1Course(Announcements(• Second(programming(assignment(is(posted(– Web(proxy(server(– Due(Sunday(March(8(at(11:59pm(– More(challenging(than(the(first(assignment(• Good(to(get(started(on(the(next(assignment(– To(go(to(office(hours(early(if(you(encounter(problems(2Goals(of(Today’s(Lecture(• Conges'on(in(IP(networks(– Unavoidable(due(to(best‐effort(service(model(– IP(philosophy:(decentralized(control(at(end(hosts(• Conges'on(control(by(the(TCP(senders(– Infers(conges'on(is(occurring((e.g.,(from(packet(losses)(– Slows(down(to(alleviate(conges'on,(for(the(greater(good(• TCP(conges'on‐control(algorithm(– Addi've‐increase,(mul'plica've‐decrease(– Slow(start(and(slow‐start(restart(• Ac've(Queue(Management((AQM)(– Random(Early(Detec'on((RED)(– Explicit(Conges'on(No'fica'on((ECN)(3No(Problem(Under(Circuit(Switching(• Source(establishes(connec'on(to(des'na'on(– Nodes(reserve(resources(for(the(connec'on(– Circuit(rejected(if(the(resources(aren’t(available(– Cannot(have(more(than(the(network(can(handle(4IP(Best‐Effort(Design(Philosophy(• Best‐effort(delivery(– Let(everybody(send(– Network(tries(to(deliver(what(it(can(– …(and(just(drop(the(rest(5 source destination IP networkConges'on(is(Unavoidable(• Two(packets(arrive(at(the(same('me(– The(node(can(only(transmit(one(– …(and(either(buffer(or(drop(the(other(• If(many(packets(arrive(in(short(period(of('me(– The(node(cannot(keep(up(with(the(arriving(traffic(– …(and(the(buffer(may(eventually(overflow(6The(Problem(of(Conges'on(• What(is(conges'on?(– Load(is(higher(than(capacity(• What(do(IP(routers(do?(– Drop(the(excess(packets(• Why(is(this(bad?(– Wasted(bandwidth(for(retransmissions(7 Load Goodput “congestion! collapse”!Increase in load that results in a decrease in useful work done.Ways(to(Deal(With(Conges'on(• Ignore(the(problem(– Many(dropped((and(retransmiMed)(packets(– Can(cause(conges'on(collapse(• Reserva'ons,(like(in(circuit(switching(– Pre‐arrange(bandwidth(alloca'ons(– Requires(nego'a'on(before(sending(packets(• Pricing(– Don’t(drop(packets(for(the(high‐bidders(– Requires(a(payment(model(• Dynamic(adjustment((TCP)(– Every(sender(infers(the(level(of(conges'on(– Each(adapts(its(sending(rate(“for(the(greater(good”(8Many(Important(Ques'ons(• How(does(the(sender(know(there(is(conges'on?(– Explicit(feedback(from(the(network?(– Inference(based(on(network(performance?(• How(should(the(sender(adapt?(– Explicit(sending(rate(computed(by(the(network?(– End(host(coordinates(with(other(hosts?(– End(host(thinks(globally(but(acts(locally?(• What(is(the(performance(objec've?(– Maximizing(goodput,(even(if(some(users(suffer(more?(– Fairness?(((Whatever(the(heck(that(means!)(• How(fast(should(new(TCP(senders(send?(9Inferring(From(Implicit(Feedback(• What(does(the(end(host(see?(• What(can(the(end(host(change?(10 ?Where(Conges'on(Happens:(Links(• Simple(resource(alloca'on:(FIFO(queue(&(drop‐tail(• Access(to(the(bandwidth:(first‐in(first‐out(queue(– Packets(transmiMed(in(the(order(they(arrive(• Access(to(the(buffer(space:(drop‐tail(queuing(– If(the(queue(is(full,(drop(the(incoming(packet(11How(it(Looks(to(the(End(Host(• Packet(delay(– Packet(experiences(high(delay(• Packet(loss(– Packet(gets(dropped(along(the(way(• How(does(TCP(sender(learn(this?(– Delay(• Round‐trip('me(es'mate(– Loss(• Timeout((• Duplicate(acknowledgments(12What(Can(the(End(Host(Do?(• Upon(detec'ng(conges'on((well,(packet(loss)(– Decrease(the(sending(rate(– End(host(does(its(part(to(alleviate(the(conges'on(• But,(what(if(condi'ons(change?(– Suppose(there(is(more(bandwidth(available(– Would(be(a(shame(to(stay(at(a(low(sending(rate(• Upon(not(detec'ng(conges'on(– Increase(the(sending(rate,(a(liMle(at(a('me(– And(see(if(the(packets(are(successfully(delivered(13TCP(Conges'on(Window(• Each(TCP(sender(maintains(a(conges'on(window(– Maximum(number(of(bytes(to(have(in(transit(– I.e.,(number(of(bytes(s'll(awai'ng(acknowledgments(• Adap'ng(the(conges'on(window(– Decrease(upon(losing(a(packet:(backing(off(– Increase(upon(success:(op'mis'cally(exploring(– Always(struggling(to(find(the(right(transfer(rate(• Both(good(and(bad(– Pro:(avoids(having(explicit(feedback(from(network(– Con:(under‐shoo'ng(and(over‐shoo'ng(the(rate(14Addi've(Increase,(Mul'plica've(Decrease(((AIMD)(• How(much(to(increase(and(decrease?(– Increase(linearly,(decrease(mul'plica'vely(– A(necessary(condi'on(for(stability(of(TCP(– Consequences(of(over‐sized(window(are(much(worse(than(having(an(under‐sized(window(• Over‐sized(window:(packets(dropped(and(retransmiMed(• Under‐sized(window:(somewhat(lower(throughput(• Mul'plica've(decrease(– On(loss(of(packet,(divide(conges'on(window(in(half(• Addi've(increase(– On(success(for(last(window(of(data,(increase(linearly(15Leads(to(the(TCP(“Sawtooth”(16 t Window halved LossPrac'cal(Details(• Conges'on(window(– Represented(in(bytes,(not(in(packets((Why?)(– Packets(have(MSS((Maximum(Segment(Size)(bytes(• Increasing(the(conges'on(window(– Increase(by(MSS(on(success(for(last(window(of(data(• Decreasing(the(conges'on(window(– Never(drop(conges'on(window(below(1(MSS(17Receiver(Window(vs.(Conges'on(Window(• Flow(control(– Keep(a(fast(sender(from(overwhelming(a(slow(receiver(• Conges'on(control(– Keep(a(set(of(senders(from(overloading(the(network(• Different(concepts,(but(similar(mechanisms(– TCP(flow(control:(receiver(window(– TCP(conges'on(control:(conges'on(window(– TCP(window:(min({(conges'on(window,(receiver(window(}(18How(Should(a(New(Flow(Start(19 t Window But, could take a long time to get started! Need to start with a small CWND to avoid overloading the
View Full Document