1 MURI Meeting October 1st, 2013 Analysis and Design of Complex Systems with Multivariate Heavy Tail Phenomena Ness B. Shroff Depts. ECE & CSE, The Ohio State University Collaborators Yoora Kim, Irem Koprulu, R. Srikant, and Y. Zheng
2 Three Research DirectionsDirection I Analyzing statistical metrics of Lévy mobility: first exit time, contact time, and inter-contact time Direction II Exploiting opportunities (node mobility, channel variation, predictibility) for resource allocation in wireless nets. In the first year of this MURI, I have focused on three main research directions Direction III Developing scheduling algorithms for data center/cloud computing systems
3 Progress Overview Direction I Analyzing statistical metrics of Lévy mobility: first exit time, contact time, and inter-contact time First exit time analysis for Lévy flight model (Submitted to AAP) Extension to Explore/Return model for more detailed human mobility modeling (ongoing work) Direction II Exploiting various opportunities (node mobility, channel variation, user predictibility) for resource allocation in wireless networks Optimal scheduler design for content sharing (IEEE INFOCOM’13) Design of data off-loading schemes: A coupled queueing problem with bi-variate heavy tailed on/off service time distribution Analysis of reneging probability and expected waiting time (Submitted to IEEE INFOCOM’14)
4 Progress Overview (cont’d)Direction III Developing scheduling algorithms for data center/cloud computing systems Analysis and design of MaP/Reduce type scheduling algorithms with multi-variate heavy tailed dependency for minimizing the total flow time in the system Prove that the flow time minimization problem is strongly NP-hard and does not yield a finite competitive ratio (IEEE INFOCOM’13) Developed 2-approximation probabilistic competitive ratio pre-emptive scheduler that is independent of the nature of job size distributions (IEEE INFOCOM’13) Low-latency algorithms in the large-system limit for both pre-emptive and non-pre-emptive schedulers (ongoing work) Characterization of the auto-correlation function of the number of servers (ongoing work) We are working on analyzing and deisigning for these ubiquitous Map/Reduce types of scheduling algorithms with ….
5 Collaborations/Synergistic ActivitiesR. Srikant (UIUC) Jointly supervise OSU PhD student Yousi Zheng via weekly (Thu. 11AM Eastern) Skype meetings on data center scheduling problems UIUC PhD student Siva Theja Maguluri visited OSU to collaborate on autocorrelation characterization in cloud computing. Pursuing collaboration with Anantharam Swami at ARL. Visit to OSU, kickoff, and Columbia meetings, plus phone conferences to discuss mobility modeling and coupled queuing problems Yoora Kim (Math dept., University of Ulsan) Weekly Skype meetings with OSU PhD student Irem Koprulu via weekly (Tue. 10AM Eastern) on Lévy flight analysis and explore/return model Joint investigation of data-off loading problem Anantharam Swami (ARL) and phone discussions on works on Lévy mobility and data center problems. Planned Monthly meetings to investigate Lévy mobility analysis for modeling drone behavior, and developing efficient proactive/reactive routing protocols.
6 Collaborations/Synergistic ActivitiesLang Tong (Cornell) Visits to OSU and Cornell, and meetings during kickoff/Columbia, plus phone/ discussions on problems involving cloud computing and data center systems Zhi-Li Zhang (University of Minnesota) Kickoff and Columbia meetings + phone/ conferences to discuss human mobility modeling Provided important new references on human mobility Gennady Samordinitski (Cornell) N. Shroff visited G. Samordinitski at Cornell in May 2013 to discuss issues regarding use of large deviation techniques for heavy tailed distributions and inference problems in social networks.
7 Direction I Analyzing statistical metrics of Lévy mobility: first exit time, contact time, and inter-contact time
8 What is Lévy Mobility? A class of random walks that is characterized by a heavy-tailed jump-length distribution Due to the heavy-tailed jump-length, the sample path consists of many short jumps and occasional long jumps with length |V|=S Where V is a sided jump that can take positive and negative values. (a) Brownian motion (b) Lévy mobility (c) Random waypoint
9 Why Lévy Mobility? Observed in ecology for different animal speciesTravel: Analysis of the circulation of bank notes in the US The distribution of human travelling distances decays as a power law [Brockmann et al. in Nature’06]
10 Lévy Mobility Models in the LiteratureHuman mobility [1] I. Rhee, et al. On the Lévy-walk nature of human mobility, IEEE/ACM Trans. on Netw., (Received the IEEE ComSoc William R. Bennet Prize of 2013). [2] K. Lee, et al. SLAW: Self-similar least-action human walk, IEEE/ACM Trans. on Netw., 2012 [3] D. Brockmann, L. Hufnagel, and T. Geisel, The scaling laws of human travel, Nature, (Dollar-Bill Tracking) Animal trajectories: [4] G. M. Viswanathan, et al. Lévy flight search patterns of wandering albatrosses, Nature, 1996. [5] G. Ramos-Fernandez, et al. Lévy walk patterns in the foraging movements of spider monkeys (Ateles geoffroyi), Behav. Ecol. Sociobiol., 2004. [6] D. W. Sims, et al. Scaling laws of marine predator search behaviour, Nature, 2008. [7] J. Klafter, M. F. Shlesinger, and G. Zumofen, Beyond brownian motion, Phys. Today, 1996. [8] R. N. Mantegna and H. E. Stanley, Stochastic process with ultraslow convergence to a gaussian: the truncated Lévy flight, Phys. Rev. Lett., 1994. In fact, there are lots of papers in the literature in which data is analyzed and shown to approximate some form of Levy mobility Info on the datasets of [1] - On the Levy-walk nature of human mobility Data set 226 daily GPS traces from 101 participants in five different outdoor sites (NCSU, KAIST, New York City, Disney World, and one state fair in Raleigh, NC) GPS records at every 10s with accuracy of 3 m Analysis (key observations) Similar statistical features to Levy walks moving within a confined area: Flight and pause-time distributions: heavy-tailed (Weibull, lognormal, Pareto, and truncated Pareto) MSD: supper-diffusion (up to 30 min to an hour) followed by sub-diffusion (Why transit? confined area & tendency to return home) 5 datasets based on GPS – 2 campuses, 1 urban area, 2 amusement parks (D1) North Carolina State University Campus (D2) KAIST Campus (D3) Manhattan, NYC (D4) Disney World Orlando FL (D5) State Fair, Raleigh NC
11 Lévy Mobility Models in the LiteratureForaging behavior: [9] G. M. Viswanathan, E. P. Raposo, and M. G. E. da Luz, Lévy flights and superdiffusion in the context of biological encounters and random searches, Phys. Life Rev., 2008. [10] C. T. Brown, L. S. Liebovitch, and R. Glendon, Lévy flights in Dobe Ju/'hoansi foraging patterns, Hum. Ecol., 2007. Epidemics: [11] N. Valler, B. A. Prakash, H. Tong, M. Faloutsos, and C. Faloutsos. Epidemic spread in mobile ad hoc networks: Determining the tipping point. NETWORKING, 2011.R. [12] Potharaju, E. Hoque, C. Nita-Rotaru, S. S. Venkatesh, and S. Sarkar, Closing the Pandora's Box: Defenses for Thwarting Epidemic Outbreaks in Mobile Adhoc Networks, IEEE MASS 2012….
12 Two-subclasses of Lévy MobilityLévy flight: consumed time per jump = constant for each jump Lévy walk: consumed time per jump jump-length Focus for this talk: Lévy flight Same sample path, but different elapsed time Location Time Lévy walk Z0 Z1 Lévy flight Z2 Z3 Z4 … Z0 Z1 Z3 Z2 Z4 Jump Sample trace in
13 Lévy Flight Sk : the length of the k-th jumpθk : the direction of the k-th jump Zk : location after the kth jump Lévy flight is described by jump-length model (Sk) direction model (θk) Z2 Z4 Z1 Z3 Z0 Jump We describe both these models in our next few slides
14 Jump-Length Model Sk is i.i.d. across k ( S := the generic random variable for Sk) With different values of α, mobility patterns are widely different. Smaller α induces a larger number of long jumps. α Heavier (Heavy-tail degree) Lighter S_k the jump length at time k is iid across k
15 Direction Model θk is i.i.d. across kθ := the generic random variable for θk The distribution of θ determines the dependence between the x and y coordinates along the trajectory θ is uniformly random over [0, 2π) no directional preference θ is concentrated along a direction strong directional preference Isotropic Lévy flight Lévy flight with directional drift
16 Relation to the ProjectRemember: projection of the jump onto x-axis projection of the jump onto y-axis Xk and Yk are dependent and have heavy tailed marginal distributions whose degree of dependency depends on the distribution of θ. otherwise Yk = 0 almost surely otherwise Xk = 0 almost surely Since the jump length has distribution then Bivariate heavy tailed Recall that for the Levy flight, the position of the motion after the k-th jump Z_k can be written by this equation same exponent as Sk
17 Metrics of Interest (1/2)First exit time Minimum time to escape a certain (bounded) region Distance from the center Now I will talk about the metrics of our interest. The first one is the first exit time of a node. The concept is as follows. Let’s say there is a node moving around, and let’s plot the distance from the initial position over time. As this figure shows, the first exit time is the minimum time that takes to escape a circle of a certain radius R. Radius of the circle First exit time
18 Metrics of Interest (2/2)First-meeting, contact, and inter-contact times Distance between soldiers The next metrics of our interest are defined from the movements of two nodes. As two nodes move around, the distance between them changes over time. When the distance is below a certain threshold R at a time t, then we can interpret that two nodes are in contact at that time. Based on this concept, the first meeting time is defined to be the minimum time that takes for two nodes to contact with each other. In addition, the contact time is the duration that two nodes maintain the connection. Finally, the inter-contact time is the time duration after two nodes are disconnected until they get connected. “Communication” Range contact inter-contact contact inter-contact First meeting time
19 Why are they important? For human mobility modelEstimate time until humans leave a (potentially hazardous) region Characterize the time and frequency of human contacts Analyze the total moving distance until devices carried by human reach a place for network access (e.g. WiFi area) or energy replenishment (e.g. battery charge) Mobile ad-hoc networks Critical in determining the delay and capacity of a network Important in choosing various scheduling and forwarding algorithms Inter-contact time: end-to-end delay in MANET Epidemic models Virus spread in nature: contact pattern of living organism is a major component for characterizing virus spreading time and spreading behavior. Rumor spread in human social networks: spreading time and distance are determined by social contact of humans.
20 First Exit Time Bounded region : 2-ball of radius RThe first exit time τR is defined as: where |Zk| denotes the Euclidean distance of Zk from the origin Goal: Characterize the distribution and the moments of τR for the range of values of α in (0,2) So, now let’s focus on the first exit time. 2 Heavier Heavy-tail degree (α) Lighter
21 Related Work (1/2) For one-dimensional symmetric Lévy flights[1,2] studies the distribution and mean of the first exit time from a finite interval. [3] points out that non-local boundary conditions have to be considered due to the heavy-tailed jump-lengths of a Lévy flight, and hence the analytical results in [1, 2] are incorrect. [3] provides only a numerical study, no analytical solution. An analytic solution for the distribution and the mean of the first exit time of a one-dimensional Lévy flight is known only for the diffusion limit. The distribution and the moments of the first exit time are derived in [4, 5] by solving a fractional diffusion equation. [1] M. Gitterman, Mean first passage time for anomalous diffusion, Phys. Rev. E, 2000. [2] S. V. Buldyrev et al., Properties of Lévy flights on an interval with absorbing boundaries. Physica A, 2001. [3] B. Dybiec et al., Lévy-Brownian motion on finite intervals: mean first passage time analysis. Phys. Rev. E, 2006. [4] E. Katzav et al., The spectrum of the fractional Laplacian and first-passage-time statistics. EPL 83, 2008. [5] A. Zoia et al., Fractional Laplacian in bounded domains. Phys. Rev. E, 2007.
22 Related Work (2/2) For one-sided 1-D Lévy flights[6] gives mean first exit time scaling as E[τR] = Θ(Rα) for 0 < α < 2. [7] provides a closed-form formula for the pmf of the first exit time and shows that P(τR = t) ~ exp(- ct1/(1-α)) for 0 < α < 1. For two-dimensional isotropic Lévy flights No analytic results for either the distribution or moments of the first exit time from a bounded region. [8] provides numerical results on the mean first exit time. First Exit Time analysis for isotropic Lévy flights is still unsolved and remains open For one-dimensional symmetric Lévy flights Taking the diffusion limit of a Lévy flight in such a way that both the Fourier variable for space and the Laplace variable for time approach zero results in a fractional diffusion equation. By solving a fractional diffusion equation, the distribution and the moments of the first exit time are derived in [4, 5] . For two-dimensional isotropic Lévy flights There are no analytic results for either the distribution or moments of the first exit time from a bounded region. There is a very recent study (in year 2013), which provides numerical results on the mean first exit time [6]. [6] I. Eliazar and J. Klafter, On the first passage of one-sided Lévy motions, Physica A, 2004. [7] T. Koren et al., Leapover lengths and first passage time statistics for Lévy flights, Phys. Rev. Lett [8] M. Vahabi et al., Area coverage of radial Lévy flights with periodic boundary conditions. Phys. Rev. E, 2013.
23 Distribution of First Exit TimeTheorem 1 (Distribution of the first exit time) [Submitted to AAP] For an isotropic Lévy flight, the first exit time from a ball of radius R is geometrically bounded, i.e., there exist 0 < lR ≤ uR < 1 such that , for all n = 1,2,…, where lR and uR are given as Note: S denotes the jump-length. zR= 2R for the 1-D Lévy flight zR= R for the 2-D Lévy flight Here’s a summary of our first main analytical result The complementary first exit time distribution decreases to zero geometrically fast from above and below. - The upper bound is relatively easy to obtain and relies on the fact that the jump length distribution is concave… but the lower bound relies on fairly technical lemmas and takes up most of the paper.
24 Numerical Result Simulations verify upper/lower bounds.1-dimensional Lévy Flight ( a = 0.5, R = 20) This is a numerical result for 1D levy flight. We set alpha to 0.5 and R to 20. The black line indicates simulation result and it shows exponential decay. The red and green lines indicate our upper and lower bounds in Lemma 2 respectively, and we can see that our result gives a valid bound on the simulation result. The blue line indicates the formula in reference [1], which does not match the simulation result. n Simulations verify upper/lower bounds. The formula in related work [1] does not match the simulation result.
25 Mean First Exit Time Theorem 2 (Mean first exit time) [Submitted to AAP] The mean first exit time of a Lévy flight is bounded by From the bounds, the scaling behavior of E[τR] with respect to R is given as Remarks For α = 1, we have E[τR] = Ω(R/log(R)) and E[τR] = O(R). For 1 < α < 2, we have E[τR] = Ω(R) and E[τR] = O(Rα). Future work is to fill the gap for 1≤ α < 2. We conjecture E[τR] = Θ(Rα) for 0 < α < 2. for 0 < α < 1 For a simple symmetric random walk (+1 or -1 with a constant with probability ½) the exact mean first exit time = R^2.
26 Direction Model RevisitedDistribution of θ determines dependence between X and Y Reminder X = S cos θ (movement along x-axis for a single jump) ~ Heavy-tailed Y = S sin θ (movement along y-axis for a single jump) ~ Heavy-tailed We introduce a simple directional drift model A model to exploit the full range between (A) & (B) above Parameterize the dependence between X and Y Consider a simple directional drift model where the directionality is greater in only one direction (A) tan-1(Y/X) ~ Uniform[0, 2π] (B) Since θ is a constant, we have linear relationship between X and Y (less directional, weak dependency) (more directional, strong dependency)
27 Directional Drift ModelDrift – tendency to move in a certain direction WLOG, we examine the specific direction θ =0. For any other direction, a rotation of the coordinate system makes the model apply. Drift model using the CDF of θ Drift index d (0 ≤ d ≤ 1) Parameter representing the degree of dependence between X and Y When d = 0, we have isotropic Lévy flight. When d = 1, we have one-sided Lévy flight. 1 d π
28 Parameter Set (α, d) Tail index α for jump-length SDrift index d for direction θ Solve the problem for parameter set (α, d) in (0,2)×[0,1] α Heavier (Heavy-tail degree) Lighter d Weaker (Dependence) Stronger So, as in the case of the jump length distribution, where alpha determines the degree of heaviness, the drift index determines the degree of dependence, and ideally, we’d like to solve for all values of alpha and d. Stronger Dependence (d) Weaker Parameter Set (α , d) 2 Heavier Heavy-tail degree (α) Lighter
29 Empirical Results (1/2) Heavier jump and larger directional drift results in shorter mean first exit time. As the directional drift decreases, the mean first exit time is more sensitive to the heavy-tail degree of the jump-length. As the jump-length becomes lighter, the mean first exit time is more sensitive to the directional drift. For heavier jump length distributions the first exit mode from the region is dominated by single large jumps, hence the directional model has little effect on the first exit time. As the jump length distribution gets lighter, first exit via several constructively aligned smaller jumps starts to dominate the first exit mode. A higher directional drift makes sequences of aligned steps more likely, hence first exit time is low. In the isotropic case consecutive steps in the same direction become less likely, hence first exit takes longer. One-sided Lévy flight Lighter tail Isotropic Lévy flight Heavier tail
30 Empirical Results (2/2) We increased the radius from R = 10 to R = 50, and we can observe similar results. One-sided Lévy flight Lighter tail Isotropic Lévy flight Heavier tail
31 Refined Human Mobility Model (1/2)Explore/Return mobility model [Song et al. in Nature Physics’06] Evaluated for a very large dataset (trajectories of over 3M mobile users for a 1 year period) Explore: with jump-length S and random direction q Return: return to one of the Kt previously visited locations Explore with probability Pexplore := rKt-g Explore K=5 K=4 Return Return with probability Preturn :=1-Pexplore After conversations with Zhi-Li at the meetings, and some discussions, we looked into another model for human mobility that has been published in nature. Detailed info on the two datasets used in the analysis: (D1) trajectories of 3 million mobile phone users over a one-year period. Each time a user initiated or received a phone call the tower that routed the communication was recorded for billing purposes. users' locations were recorded with the resolution that is determined by the local tower density. (a few hundred to a few kilometres). (D2) location record of 1,000 users who signed up for a location based service. users' locations were recorded every hour for a two week period. Kt := number of visited distinct points (e.g. Kt = 4) K=4 [Song. et. al] C. Song, T. Koren, P. Wang, and A.-L. Barabási, “Modeling the Scaling Properties of Human Mobility”, Nature Physics, 2010.
32 Refined Human Mobility Model (2/2)Simplified Explore/Return mobility model The probability to explore/return does not depend on the number of previously visited locations (i.e. g = 0). Hence, at each step an individual acts one of the following: either explore with probability Pexplore = ρ or return with probability Preturn = 1 − ρ Location after the nth step Note The return probability need not be uniform over Zk (k=1,2,…,n-1) i.e., one could give preference to certain locations. with probability r with probability 1- r
33 Our Analytic Results on the E/R modelTheorem 3 (Distribution of the first exit time). For an Explore/Return Lévy flight, the first exit time from a ball of radius R is geometrically bounded as Where uR and lR are given as in Theorem 1. Theorem 4 (Mean first exit time). The mean first exit time is bounded by and the scaling behavior of E[τR] with respect to R is given as for 0 < α < 1.
34 Future Work Complete our analysis on the first exit timeFill the gap between the lower and upper bounds for α in [1, 2) Analysis for Explore/Return human mobility model and direction mobility models Analysis for various direction mobility models E.g., One to multiple directional drift (vector of di’s for each direction i) Large Deviation analysis The exact decay rate of first exit time distribution for a fixed radius R (i.e., beyond bounds and scaling analysis as R goes to infinity) Other statistical metrics Contact time Relation between contact time & first exit time (preliminary results here --- still under verification)
35 Future Work (cont’d) Extensions to Lévy walkOne-dimension as well as two-dimension Challenges due to spatio-temporal dependency Time depends on size of the jump, hence dependency between space and time Work with ARL to apply results to problems of interest Levy mobility analysis for UAV and communications (3-D?) Development of new proactive Routing protocols Analyze contact patterns if data is available from Army? (talks with ARL) Distribution of the first-meeting time Distribution of the contact time Distribution of the inter-contact time
36 Progress Overview Direction I Analyzing statistical metrics of Lévy mobility: first exit time, contact time, and inter-contact time First exit time analysis for Lévy flight (Submitted to AAP) Extension to Explore/Return model for more detailed human mobility modeling (ongoing work) Direction II Exploiting various opportunities (node mobility, channel variation, user predictibility) for resource allocation in wireless networks Optimal scheduler design for content sharing (IEEE INFOCOM’13) Design of data off-loading schemes: A coupled queueing problem with bi-variate heavy tailed on/off service time distribution Analysis of reneging probability and expected delay (Submitted to IEEE INFOCOM’14)
37 Exploiting double opportunities by data off-loadingMobile data offloading Cellular networks are highly constrained (esp. in military settings) Use WiFi LANs, mmWave or direct contact opportunities for delivering data originally targeted for cellular networks (WiFi and cellular network interworking) Sketch of delayed offloading system (through WiFi only) Traffic generated by a device first seeks WiFi APs. If the device fails to meet WiFi APs until timeout expires, then cellular network takes care of the delivery. Another promising problem that exploits double opportunities is the Mobile data offloading problem. Here both mobile opportunities and channel can be exploited. on the use of aforementioned double opportunities in WiFi and cellular networks together in order to provide a solution of mobile data offloading problem (the use of WiF network technologies for delivering data originally targeted for cellular networks)
38 Reminder: Delayed Offloading SystemCoupled (upload) queuing structure at each user Server state in WiFi queue - alternating on/off process On period (in WiFi coverage) ~ heavy tailed Off period (out of WiFi coverage) ~ heavy tailed Relationship to the project: bivariate heavy-tailed on/off periods K. Lee et. al, “Mobile data offloading: How much can WiFi deliver?” IEEE/ACM Trans. on Networking, 2013. WiFi queue Traffic arrivals Served by WiFi networks Timeout expires (“Reneging event”) Cellular queue Served by 3G/4G networks out (off) in (on) out (off) in (on)
39 Preliminary Results (Kickoff)Simplifying assumptions A1. (Xn,Yn) : i.i.d. across n, but Xn and Yn could be dependent. A2. WiFi service rate (fixed): c [bits/slot] A3. Bernoulli arrival process A4. Packet size (fixed): c [bits] Performance metrics Reneging probability (that a packet leaves the WiFi queue) Average waiting time at the WiFi queue Server state in WiFi queue - alternating on/off process On period (in WiFi coverage) ~ heavy tailed Off period (outof WiFi coverage) ~ heavy tailed Goal: analyze impact of HT and dependency on network performance on on on (service rate) Generalization: A2, A3, and A4 We had some preliminary results at the kickoff under some restrictive assumptions
40 Generalized System ModelAssumptions A1. (Xn,Yn) : i.i.d. across n, but Xn and Yn could be dependent. A2. WiFi service rate (fixed): c [bits/slot] Variable service rate (General distribution) A3. Bernoulli arrival process Arrival process is renewal process. A4. Packet size (fixed): c [bits] Variable packet size (General distribution) on on on
41 Summary of Our Analytic ResultsWe obtain a formula for the queue length distribution at the WiFi queue at an arbitrary point in time Performance metric I: Reneging probability From the queue length distribution, we can obtain the formula for the reneging probability. The reneging probability determines the offloading efficiency. Performance metric II: Average waiting time in the WiFi queue Extensive numerical study Understand the impact of time-out on the performance of mobile delayed offloading system
42 Future Work Joint queue length distribution (WiFi and cellular queue)Impact of on/off WiFi channel dependency on performance Guideline for WiFi deployment strategy Exploit direct contact opportunities Further offloading gain Delay and throughput tradeoff BS could transmit to a larger group at lower throughput BS could transmit to a smaller group at a higher throughput but more delay Delay can be further controlled by predicting user needs in advance Analyze other coupled queueing systems Networks with replenishment Networks with secret communication
43 Thank You
44 Backup Slides
45 Backup: Directional Drift ModelDirectional drift - tendency to move to a certain direction Two extreme cases Isotropic Lévy flight θ ~ Uniform[0, 2π] Most weak dependence between X and Y One-sided Lévy flight θ = c (constant, i.e., deterministic) Most strong dependence between X and Y Linear relationship between X and Y Y = η X where η = tan(c) is a constant.
46 Backup: Related Work (1/2)Distribution of the first exit time τ P(τ = t) ~ exp(- ct1/(1-α)) [Koren et al.’07] 1 Parameter Set (α, d) Drift index (d) 1 2 Tail weight (α) P(τ > t) is bounded above and below by exponential functions [Shroff et al.’13]
47 Backup: Related Work (2/2)Mean first exit time E[τ] E[τ] = Θ(Rα) [Eliazar et al.’04] 1 We provide simulation study for entire (α, d). Parameter Set (α, d) Drift index (d) 2 Tail weight (α) E[τ] = Θ(Rα) [Shroff et al.’13]
48 II: Scheduling Algorithms for Data Center SystemsFacility containing a very large numbers of machines Has roots in huge computer rooms of the early ages! Process very large datasets Use MapReduce programming Model Framework for processing highly parallel jobs MapReduce Developed (popularized) by Google Nearly ubiquitous Google, IBM, Facebook, Microsoft, Yahoo, Amazon, eBay, twitter… Used in a variety of different applications Distributed Grep, distributed sort, AI, scientific computation, Large scale pdf generation, Geographical data, Image processing… IaaS: Infrastructe as a Service; PaaS: Platform as a Service; SaaS: Software as a Service Power: 1 Google: Energy consumption: 260 million watts. 2 Google: Annual energy costs > server costs. Green: 1 Use renewable energy; consider utility of renewable energy when scheduling. 2 Natural cooling: use natural wind and sea water to cool, directly related to the data center location choice. Ma-duce: Programming model for processing large datasets Popular: Google, Yahoo, … Tasks Dependency Data Locality Delay, Fairness, …
49 MapReduce Map phase Reduce phaseTakes an input job and divides into many small sub-problems (tasks) Map tasks can run in parallel on potentially different “machines” Reduce phase Combines the output of Map Occurs after the Map phase is completed Runs on parallel machines… MapReduce has two elemental processes: Map and Reduce. For the Map tasks, the inputs are divided into several small sets, and processed by different machines in parallel. The output of Map tasks is a set of pairs in
50 Relationship to Project/CollaborationNumber of Map tasks in a job could be heavy tailed (or truncated heavy tailed) Size of each reduce task could be heavy tailed (or truncated heavy tailed) Map and Reduce jobs are dependent Bivariate heavy tails and coupled queues Collaboration Weekly Skype (Thu. 11AM) meetings with R. Srikant (co-PI, UIUC) and Y. Zheng (PhD student at OSU) Developed optimal strategies for scheduling in Map-Reduce framework in the large-system limit.
51 III. Resource Allocation in Wireless NetworksWireless resources are highly stressed Need ways to off-load data from traditional cellular networks to other networks (e.g., WiFi zones, mmWave, etc.) Observed times spent in and out of WiFi zones are dependent and distributed according to heavy tailed distributions. For each user, the system can be modeled as a coupled WiFi and cellular queue, where the cellular queue serves traffic only after its time-out period has expired in the WiFi queue (reneging event) Goal: Characterize the reneging probability and waiting time in the WiFi queue Relationship to the project: bivariate heavy-tailed on/off periods
52 Key Results Derived the queue length distribution at the WiFi queue at an arbitrary point in time Performance metric I: Reneging probability From the queue length distribution, obtained an explicit formula for the reneging probability. The reneging probability determines the offloading efficiency. Performance metric II: Average waiting time in the WiFi queue Extensive numerical study Characterized the impact of time-out on the performance of mobile delayed offloading system
53 Keeping it just in case. Remove if you like.Our contribution in [9] We consider both the one-dimensional symmetric Lévy flights and the two-dimensional isotropic Lévy flights. We show that P(τR > t) is bounded above and below by exponentially decreasing functions for 0 < α < 2. From the bounds, we prove that E[τR] = Θ(Rα) for 0 < α < 1. I am keeping this slide just in case. [ [9] Y. Kim, I. Koprulu, and N. Shroff, First exit time of a Lévy flight from a bounded region, submitted, 2013.
54 Related Work (1/2) For one-dimensional symmetric Lévy flights[1,2] studies the distribution and mean of the first exit time from a finite interval. [3] points out that non-local boundary conditions have to be considered due to the heavy-tailed jump-lengths of a Lévy flight, and hence the analytical results in [1, 2] are incorrect. [3] provides only a numerical study, no analytical solution. An analytic solution for the distribution and the mean of the first exit time of a one-dimensional Lévy flight is known only for the diffusion limit. The distribution and the moments of the first exit time are derived in [4, 5] by solving a fractional diffusion equation. [1] M. Gitterman, Mean first passage time for anomalous diffusion, Phys. Rev. E, 2000. [2] S. V. Buldyrev et al., Properties of Lévy flights on an interval with absorbing boundaries. Physica A, 2001. [3] B. Dybiec et al., Lévy-Brownian motion on finite intervals: mean first passage time analysis. Phys. Rev. E, 2006. [4] E. Katzav et al., The spectrum of the fractional Laplacian and first-passage-time statistics. EPL 83, 2008. [5] A. Zoia et al., Fractional Laplacian in bounded domains. Phys. Rev. E, 2007.
55 Numerical Result 2-D n 2-dimensional Lévy Flight ( a = 0.5, R = 20)This is a numerical result for 2D levy flight. We set alpha to 0.5 and R to 20 as in the 1-D case on the previous slide. The black line indicates simulation result and it shows exponential decay. The red and green lines indicate our upper and lower bounds in Theorem 1 respectively. n