1Stochastic Hybrid Systems:Applications to Communication NetworksJoão P. HespanhaCenter for Control Engineeringand ComputationUniversity of Californiaat Santa Barbararesearch supported by NSFDeterministic Hybrid Systemsguardconditionsreset-mapscontinuousdynamicsq(t) ∈ Q={1,2,…} ≡ discrete statex(t) ∈ Rn≡ continuous stateright-continuousby conventionwe assume here a deterministic system so the invariant sets would be the exact complements of the guards2Stochastic Hybrid Systemsreset-mapscontinuousdynamicsNA(t) ∈ N ≡ transition counter, which is incremented by one each time the Ath reset-map ϕA(x) is “activated”number of transitionson (t1, t2]equal to integral of transition intensityλA(x) on (t1, t2]right-continuousby conventiontransition intensities(instantaneous rates at which transitions occur)Stochastic Hybrid Systemsreset-mapscontinuousdynamicsSpecial case: When all λAare constant, transitions are controlled by a continuous-time Markov process q = 1q = 2q = 3specifies q(independently of x)transition intensities(instantaneous rates at which transitions occur)3Formal model—SummaryState space:q(t) ∈ Q={1,2,…} ≡ discrete statex(t) ∈ Rn≡ continuous stateContinuous dynamics:Reset-maps (one per transition intensity):Transition intensities:# of transitionsResults:1. [existence] Under appropriate regularity (Lipschitz) assumptions, there exists a measure “consistent” with the desired SHS behavior2. [simulation] The procedure used to construct the measure is constructive and allows for efficient generation of Monte Carlo sample paths3. [Markov] The pair ( q(t), x(t) ) ∈ Q× Rnis a (Piecewise-deterministic) Markov Process (in the sense of M. Davis, 1983)Example I: TCP congestion controlserver clientnetworkpackets droppedwith probability pdroptransmitsdata packetsreceivesdata packetscongestion control ≡ selection of the rate r at which the server transmits packetsfeedback mechanism ≡ packets are dropped by the network to indicate congestionr4Example I: TCP congestion controlserver clientnetworktransmitsdata packetsreceivesdata packetsTCP (Reno) congestion control: packet sending rate given bycongestion window (internal state of controller)round-trip-time (from server to client and back)• initially w is set to 1• until first packet is dropped, w increases exponentially fast(slow-start)• after first packet is dropped, w increases linearly (congestion-avoidance)• each time a drop occurs, w is divided by 2 (multiplicative decrease)packets droppedwith probability pdropcongestion control ≡ selection of the rate r at which the server transmits packetsfeedback mechanism ≡ packets are dropped by the network to indicate congestionrExample I: TCP congestion controlper-packetdrop prob.pckts sentper sec×pckts droppedper sec=# of packetsalready sentTCP (Reno) congestion control: packet sending rate given bycongestion window (internal state of controller)round-trip-time (from server to client and back)• initially w is set to 1• until first packet is dropped, w increases exponentially fast(slow-start)• after first packet is dropped, w increases linearly (congestion-avoidance)• each time a drop occurs, w is divided by 2 (multiplicative decrease)5Analysis—Lie DerivativeGiven function ψ : Rn× [0,∞) → Rderivativealong solutionto ODELfψLie derivative of ψOne can view Lfas an operatorspace of scalar functions onRn× [0,∞)space of scalar functions onRn× [0,∞)→ψ(x, t)6Lfψ(x, t)Lfcompletely defines the system dynamicsAnalysis—Generator of the SHScontinuous dynamicsreset-mapstransition intensitiesGiven function ψ : Q × Rn× [0,∞) → Rgenerator for the SHSwhereLfψLie derivative of ψreset instantaneousvariationintensityL completely defines the SHS dynamicsdisclaimer: see paper for technical assumptionsDynkin’sformula(in differential form)6Example I: TCP congestion controlslow-startcongestionavoidanceThis TCP model is always-onExample II: On-off TCP model• Between transfers, server remains off for an exponentially distributed time with mean τoff• Transfer-size is a random variable with cumulative distribution F(s)determines duration of on-periods7Using the SHS generator…Mixture of exponential distribution for transfer-sizes:M exp. distr. with mean{ k1, k2, …, kM}M probabilities{ p1, p2, …, pM}transfer-sizes are extracted from an exponential distribution with mean kiw.p. pican approximate well distributions found in the literature …µq,n≡ expected value of rnwhen SHS is in mode qprobability of being in off modeslow-start with file-size from ith exponential distributioncong.-avoidance with file-size from ith exponential distributionµq,n≡ expected value of rnwhen SHS is in mode qUsing the SHS generator…Mixture of exponential distribution for transfer-sizes:M probabilities{ p1, p2, …, pM}transfer-sizes are extracted from an exponential distribution with mean kiw.p. pican approximate well distributions found in the literature …off modeslow-start with file-size from ith exponential distributioncong.-avoidance with file-size from ith exponential distributioninfinite system of ODEsBut:distributions are well approximated by log-Normal so one can truncate the infinite system of ODEs(keeping only first 2 moments)M exp. distr. with mean{ k1, k2, …, kM}8Case I10-310-210-100.010.020.030.040.050.060.070.080.09pdropProbabilityany active modeslow-startcongestion-avoidance10-310-210-10123456pRate Meantotalslow-startcongestion-avoidancesmall "mice" transfersmid-size "elephant" transfers10-310-210-10102030405060708090pdropRate Standard Deviationtotalslow-startcongestion-avoidancesmall "mice" transfersmid-size "elephant" transfersMonte-Carlo& theoreticalsteady-state values(vs. drop probability)Transfer-size approximating the distribution of file sizes in the UNIX file systemp1= 88.87% k1= 3.5KB (“mice” files)p2= 11.13% k2= 246KB (“elephant” files, but not heavy tail)Case IITransfer-size distribution at an ISP’s www proxy [Arlitt et al.] p1= 98% k1= 6KB (“mice” files)p2= 1.7% k2= 400KB (“elephant” files)p3= .02% k3= 10MB (“mammoth” files)10-310-210-100.511.522.5pdropRate Meantotalslow-startcongestion-avoidancesmall "mice" transfersmid-size "elephant" transfersmid-size "mammoth" transfers10-310-210-10102030405060708090pdropRate Standard Deviationtotalslow-startcongestion-avoidancesmall "mice" transfersmid-size "elephant" transfersmid-size "mammoth" transfersSteady-state valuesvs.drop
or
We will never post anything without your permission.
Don't have an account? Sign up