DOC PREVIEW
Deterministic Hybrid Systems

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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


Deterministic Hybrid Systems

Download Deterministic Hybrid Systems
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Deterministic Hybrid Systems and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Deterministic Hybrid Systems 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?