Shanghai Jiao Tong University DELAY MODELS IN DATA NETWORKS Weigiang Sun Communication Networks
Weiqiang(Sun Communica/on(Networks DELAY&MODELS&IN&DATA&NETWORKS& Shanghai(Jiao(Tong(University 1
Data networks and Queueing R R R R R R R Weigiang Sun Communication Networks
Weiqiang(Sun Communica/on(Networks Data(networks(and(Queueing R R R R R R R S 2
General Methodologies of Queueing Analysis We are given: Packet arrival behavior Packet length distribution Packet routing handling policies e We want to deduce: Packet delay -Queue length Packet loss Queueing theory can also be applied in other areas,such as in analyzing Circuit Switched Net. Weigiang Sun Communication Networks
Weiqiang(Sun Communica/on(Networks General(Methodologies(of(Queueing( Analysis • We&are&given:& – Packet(arrival(behavior( – Packet(length(distribu/on( – Packet(rou/ng(/(handling(policies( • We&want&to&deduce:& – Packet(delay( – Queue(length( – Packet(loss( • Queueing(theory(can(also(be(applied(in(other(areas,(such(as(in( analyzing(Circuit(Switched(Net. 3
In this chapter ·Poisson process ·The Little's Theorem M/M/x Queueing systems Burke's Theorem and Jackson's Theorem ·M/G/1 Reservation systems and priority queue Weigiang Sun Communication Networks 4
Weiqiang(Sun Communica/on(Networks In(this(chapter • Poisson(process( • The(LiQle’s(Theorem( • M/M/x(Queueing(systems( • Burke’s(Theorem(and(Jackson’s(Theorem( • M/G/1( • Reserva/on(systems(and(priority(queue( 4
Weigiang Sun Shanghai Jiao Tong University ARRIVAL MODEL AND THE LITTLE'S THEOREM Weigiang Sun Communication Networks 5
Weiqiang(Sun Communica/on(Networks ARRIVAL&MODEL&AND&THE&LITTLE’S& THEOREM& Weiqiang(Sun( Shanghai(Jiao(Tong(University 5
The arrival process The arrival process can normally be described by the number of arrivals in a unit time or can be described by inter-arrival time ·Poisson process the most commonly used arrival model in telecom network Named after the French Mathematician Simeon-Denis Poisson(1781-1840) Weigiang Sun Communication Networks 6
Weiqiang(Sun Communica/on(Networks The(arrival(process • The(arrival(process(can(normally(be(described(( – by(the(number(of(arrivals(in(a(unit(/me( – or(can(be(described(by(interWarrival(/me( • Poisson&process& – the(most(commonly(used(arrival(model(in(telecom( network( – Named(aXer(the(French(Mathema/cian(SimeonWDenis( Poisson((1781(–(1840) 6
Examples of Poisson process The number of page request arriving at a web server(no attack,please) The number of telephone calls arrives at an switch The number of photons hitting a photon detector,when lit by a laser The execution of trades on a stock exchange Weigiang Sun Communication Networks
Weiqiang(Sun Communica/on(Networks Examples(of(Poisson(process • The(number(of(page(request(arriving(at(a(web(server((no( aQack,(please)( • The(number(of(telephone(calls(arrives(at(an(switch( • The(number(of(photons(hibng(a(photon(detector,(when(lit(by( a(laser( • The(execu/on(of(trades(on(a(stock(exchange( • … 7
Three ways to define a Poisson process (1)In an infinitesimal time interval dt,there may occur only one arrival,and this happens with probability λdt 40444 dt Weigiang Sun Communication Networks 8
Weiqiang(Sun Communica/on(Networks Three(ways(to(define(a(Poisson(process (1)(In(an(infinitesimal(/me(interval(dt,(there(may(occur( only(one(arrival,(and(this(happens(with(probability( λdt dt 8
Three ways to define a Poisson process (2)The number of arrivals N(t)in a finite interval of length t Obeys Poisson distribution with parameter At The number of arrivals in non-overlapped intervals are independent P(N()=n)=eu() n！ 1.0 0.0 0.5 1.0 T1 T2 Poisson Poisson(入T2) 2.0 (入T1) Weigiang Sun Communication Networks 9
Weiqiang(Sun Communica/on(Networks Three(ways(to(define(a(Poisson(process (2)The(number(of(arrivals(N(t)(in(a(finite(interval(of( length(t(( – Obeys(Poisson(distribu/on(with(parameter(λt( – The(number(of(arrivals(in(nonWoverlapped(intervals(are( independent( T1( Poisson (λT1) T2( Poisson(λT2) 9
Three ways to define a Poisson process (3)The interval times are independent and obey exponential distribution with rate P(t≤t)=1-ew ↓↓↓↓出↓出↓ exp(入) ·Proof of2→3 P(tst)=1-P(>)=1-P(0arrival within t) Weigiang Sun Communication Networks 10
Weiqiang(Sun Communica/on(Networks Three(ways(to(define(a(Poisson(process (3)(The(interval(/mes(are(independent(and(obey( exponen/al(distribu/on(with(rate(λ exp(λ) • Proof(of(23 10