An Evaluation of Availability Latency in Carrier-based Vehicular ad-hoc Networks Shahram Ghandeharizadeh Dept of Computer Science Univ of Southern California Los Angeles, CA 90089, USA shahram@usc.edu Shyam Kapadia Dept of Computer Science Univ of Southern California Los Angeles, CA 90089, USA kapadia@usc.edu Bhaskar Krishnamachari Dept of Computer Science Dept of Electrical Engineering Univ of Southern California Los Angeles, CA 90089, USA bkrishna@usc.edu ABSTRACT On-demand delivery of audio and video clips in peer-to-peer vehicular ad-hoc networks is an emerging area of research. Our target environment uses data carriers, termed zebroids, where a mobile device carries a data item on behalf of a server to a client thereby minimizing its availability latency. In this study, we quantify the variation in availability latency with zebroids as a function of a rich set of parameters such as car density, storage per device, repository size, and replacement policies employed by zebroids. Using analysis and extensive simulations, we gain novel insights into the design of carrier-based systems. Significant improvements in latency can be obtained with zebroids at the cost of a minimal overhead. These improvements occur even in scenarios with lower accuracy in the predictions of the car routes. Two particularly surprising findings are: (1) a naive random replacement policy employed by the zebroids shows competitive performance, and (2) latency improvements obtained with a simplified instantiation of zebroids are found to be robust to changes in the popularity distribution of the data items. Categories and Subject Descriptors: C.2.4 [Distributed Systems]: Client/Server General Terms: Algorithms, Performance, Design, Experimentation. 1. INTRODUCTION Technological advances in areas of storage and wireless communications have now made it feasible to envision on-demand delivery of data items, for e.g., video and audio clips, in vehicular peer-topeer networks. In prior work, Ghandeharizadeh et al. [10] introduce the concept of vehicles equipped with a Car-to-Car-Peer-toPeer device, termed AutoMata, for in-vehicle entertainment. The notable features of an AutoMata include a mass storage device offering hundreds of gigabytes (GB) of storage, a fast processor, and several types of networking cards. Even with today"s 500 GB disk drives, a repository of diverse entertainment content may exceed the storage capacity of a single AutoMata. Such repositories constitute the focus of this study. To exchange data, we assume each AutoMata is configured with two types of networking cards: 1) a low-bandwidth networking card with a long radio-range in the order of miles that enables an AutoMata device to communicate with a nearby cellular or WiMax station, 2) a high-bandwidth networking card with a limited radio-range in the order of hundreds of feet. The high bandwidth connection supports data rates in the order of tens to hundreds of Megabits per second and represents the ad-hoc peer to peer network between the vehicles. This is labelled as the data plane and is employed to exchange data items between devices. The low-bandwidth connection serves as the control plane, enabling AutoMata devices to exchange meta-data with one or more centralized servers. This connection offers bandwidths in the order of tens to hundreds of Kilobits per second. The centralized servers, termed dispatchers, compute schedules of data delivery along the data plane using the provided meta-data. These schedules are transmitted to the participating vehicles using the control plane. The technical feasibility of such a two-tier architecture is presented in [7], with preliminary results to demonstrate the bandwidth of the control plane is sufficient for exchange of control information needed for realizing such an application. In a typical scenario, an AutoMata device presents a passenger with a list of data items1 , showing both the name of each data item and its availability latency. The latter, denoted as δ, is defined as the earliest time at which the client encounters a copy of its requested data item. A data item is available immediately when it resides in the local storage of the AutoMata device serving the request. Due to storage constraints, an AutoMata may not store the entire repository. In this case, availability latency is the time from when the user issues a request until when the AutoMata encounters another car containing the referenced data item. (The terms car and AutoMata are used interchangeably in this study.) The availability latency for an item is a function of the current location of the client, its destination and travel path, the mobility model of the AutoMata equipped vehicles, the number of replicas constructed for the different data items, and the placement of data item replicas across the vehicles. A method to improve the availability latency is to employ data carriers which transport a replica of the requested data item from a server car containing it to a client that requested it. These data carriers are termed ‘zebroids". Selection of zebroids is facilitated by the two-tiered architecture. The control plane enables centralized information gathering at a dispatcher present at a base-station.2 Some examples of control in1 Without loss of generality, the term data item might be either traditional media such as text or continuous media such as an audio or video clip. 2 There may be dispatchers deployed at a subset of the base-stations for fault-tolerance and robustness. Dispatchers between basestations may communicate via the wired infrastructure. 75 formation are currently active requests, travel path of the clients and their destinations, and paths of the other cars. For each client request, the dispatcher may choose a set of z carriers that collaborate to transfer a data item from a server to a client (z-relay zebroids). Here, z is the number of zebroids such that 0 ≤ z < N, where N is the total number of cars. When z = 0 there are no carriers, requiring a server to deliver the data item directly to the client. Otherwise, the chosen relay team of z zebroids hand over the data item transitively to one another to arrive at the client, thereby reducing availability latency (see Section 3.1 for details). To increase robustness, the dispatcher may employ multiple relay teams of z-carriers for every request. This may be useful in scenarios where the dispatcher has lower prediction accuracy in the information about the routes of the cars. Finally, storage constraints may require a zebroid to evict existing data items from its local storage to accommodate the client requested item. In this study, we quantify the following main factors that affect availability latency in the presence of zebroids: (i) data item repository size, (ii) car density, (iii) storage capacity per car, (iv) client trip duration, (v) replacement scheme employed by the zebroids, and (vi) accuracy of the car route predictions. For a significant subset of these factors, we address some key questions pertaining to use of zebroids both via analysis and extensive simulations. Our main findings are as follows. A naive random replacement policy employed by the zebroids shows competitive performance in terms of availability latency. With such a policy, substantial improvements in latency can be obtained with zebroids at a minimal replacement overhead. In more practical scenarios, where the dispatcher has inaccurate information about the car routes, zebroids continue to provide latency improvements. A surprising result is that changes in popularity of the data items do not impact the latency gains obtained with a simple instantiation of z-relay zebroids called one-instantaneous zebroids (see Section 3.1). This study suggests a number of interesting directions to be pursued to gain better understanding of design of carrier-based systems that improve availability latency. Related Work: Replication in mobile ad-hoc networks has been a widely studied topic [11, 12, 15]. However, none of these studies employ zebroids as data carriers to reduce the latency of the client"s requests. Several novel and important studies such as ZebraNet [13], DakNet [14], Data Mules [16], Message Ferries [20], and Seek and Focus [17] have analyzed factors impacting intermittently connected networks consisting of data carriers similar in spirit to zebroids. Factors considered by each study are dictated by their assumed environment and target application. A novel characteristic of our study is the impact on availability latency for a given database repository of items. A detailed description of related works can be obtained in [9]. The rest of this paper is organized as follows. Section 2 provides an overview of the terminology along with the factors that impact availability latency in the presence of zebroids. Section 3 describes how the zebroids may be employed. Section 4 provides details of the analysis methodology employed to capture the performance with zebroids. Section 5 describes the details of the simulation environment used for evaluation. Section 6 enlists the key questions examined in this study and answers them via analysis and simulations. Finally, Section 7 presents brief conclusions and future research directions. 2. OVERVIEW AND TERMINOLOGY Table 1 summarizes the notation of the parameters used in the paper. Below we introduce some terminology used in the paper. Assume a network of N AutoMata-equipped cars, each with storage capacity of α bytes. The total storage capacity of the system is ST =N ·α. There are T data items in the database, each with Database Parameters T Number of data items. Si Size of data item i fi Frequency of access to data item i. Replication Parameters Ri Normalized frequency of access to data item i ri Number of replicas for data item i n Characterizes a particular replication scheme. δi Average availability latency of data item i δagg Aggregate availability latency, δagg = T j=1 δj · fj AutoMata System Parameters G Number of cells in the map (2D-torus). N Number of AutoMata devices in the system. α Storage capacity per AutoMata. γ Trip duration of the client AutoMata. ST Total storage capacity of the AutoMata system, ST = N · α. Table 1: Terms and their definitions size Si. The frequency of access to data item i is denoted as fi, with T j=1 fj = 1. Let the trip duration of the client AutoMata under consideration be γ. We now define the normalized frequency of access to the data item i, denoted by Ri, as: Ri = (fi)n T j=1(fj)n ; 0 ≤ n ≤ ∞ (1) The exponent n characterizes a particular replication technique. A square-root replication scheme is realized when n = 0.5 [5]. This serves as the base-line for comparison with the case when zebroids are deployed. Ri is normalized to a value between 0 and 1. The number of replicas for data item i, denoted as ri, is: ri = min (N, max (1, Ri·N·α Si )). This captures the case when at least one copy of every data item must be present in the ad-hoc network at all times. In cases where a data item may be lost from the ad-hoc network, this equation becomes ri = min (N, max (0, Ri·N·α Si )). In this case, a request for the lost data item may need to be satisfied by fetching the item from a remote server. The availability latency for a data item i, denoted as δi, is defined as the earliest time at which a client AutoMata will find the first replica of the item accessible to it. If this condition is not satisfied, then we set δi to γ. This indicates that data item i was not available to the client during its journey. Note that since there is at least one replica in the system for every data item i, by setting γ to a large value we ensure that the client"s request for any data item i will be satisfied. However, in most practical circumstances γ may not be so large as to find every data item. We are interested in the availability latency observed across all data items. Hence, we augment the average availability latency for every data item i with its fi to obtain the following weighted availability latency (δagg) metric: δagg = T i=1 δi · fi Next, we present our solution approach describing how zebroids are selected. 3. SOLUTION APPROACH 3.1 Zebroids When a client references a data item missing from its local storage, the dispatcher identifies all cars with a copy of the data item as servers. Next, the dispatcher obtains the future routes of all cars for a finite time duration equivalent to the maximum time the client is willing to wait for its request to be serviced. Using this information, the dispatcher schedules the quickest delivery path from any of the servers to the client using any other cars as intermediate carriers. Hence, it determines the optimal set of forwarding decisions 76 that will enable the data item to be delivered to the client in the minimum amount of time. Note that the latency along the quickest delivery path that employs a relay team of z zebroids is similar to that obtained with epidemic routing [19] under the assumptions of infinite storage and no interference. A simple instantiation of z-relay zebroids occurs when z = 1 and the client"s request triggers a transfer of a copy of the requested data item from a server to a zebroid in its vicinity. Such a zebroid is termed one-instantaneous zebroid. In some cases, the dispatcher might have inaccurate information about the routes of the cars. Hence, a zebroid scheduled on the basis of this inaccurate information may not rendezvous with its target client. To minimize the likelihood of such scenarios, the dispatcher may schedule multiple zebroids. This may incur additional overhead due to redundant resource utilization to obtain the same latency improvements. The time required to transfer a data item from a server to a zebroid depends on its size and the available link bandwidth. With small data items, it is reasonable to assume that this transfer time is small, especially in the presence of the high bandwidth data plane. Large data items may be divided into smaller chunks enabling the dispatcher to schedule one or more zebroids to deliver each chunk to a client in a timely manner. This remains a future research direction. Initially, number of replicas for each data item replicas might be computed using Equation 1. This scheme computes the number of data item replicas as a function of their popularity. It is static because number of replicas in the system do not change and no replacements are performed. Hence, this is referred to as the ‘nozebroids" environment. We quantify the performance of the various replacement policies with reference to this base-line that does not employ zebroids. One may assume a cold start phase, where initially only one or few copies of every data item exist in the system. Many storage slots of the cars may be unoccupied. When the cars encounter one another they construct new replicas of some selected data items to occupy the empty slots. The selection procedure may be to choose the data items uniformly at random. New replicas are created as long as a car has a certain threshold of its storage unoccupied. Eventually, majority of the storage capacity of a car will be exhausted. 3.2 Carrier-based Replacement policies The replacement policies considered in this paper are reactive since a replacement occurs only in response to a request issued for a certain data item. When the local storage of a zebroid is completely occupied, it needs to replace one of its existing items to carry the client requested data item. For this purpose, the zebroid must select an appropriate candidate for eviction. This decision process is analogous to that encountered in operating system paging where the goal is to maximize the cache hit ratio to prevent disk access delay [18]. The carrier-based replacement policies employed in our study are Least Recently Used (LRU), Least Frequently Used (LFU) and Random (where a eviction candidate is chosen uniformly at random). We have considered local and global variants of the LRU/LFU policies which determine whether local or global knowledge of contents of the cars known at the dispatcher is used for the eviction decision at a zebroid (see [9] for more details). The replacement policies incur the following overheads. First, the complexity associated with the implementation of a policy. Second, the bandwidth used to transfer a copy of a data item from a server to the zebroid. Third, the average number of replacements incurred by the zebroids. Note that in the no-zebroids case neither overhead is incurred. The metrics considered in this study are aggregate availability latency, δagg, percentage improvement in δagg with zebroids as compared to the no-zebroids case and average number of replacements incurred per client request which is an indicator of the overhead incurred by zebroids. Note that the dispatchers with the help of the control plane may ensure that no data item is lost from the system. In other words, at least one replica of every data item is maintained in the ad-hoc network at all times. In such cases, even though a car may meet a requesting client earlier than other servers, if its local storage contains data items with only a single copy in the system, then such a car is not chosen as a zebroid. 4. ANALYSIS METHODOLOGY Here, we present the analytical evaluation methodology and some approximations as closed-form equations that capture the improvements in availability latency that can be obtained with both oneinstantaneous and z-relay zebroids. First, we present some preliminaries of our analysis methodology. • Let N be the number of cars in the network performing a 2D random walk on a √ G× √ G torus. An additional car serves as a client yielding a total of N + 1 cars. Such a mobility model has been used widely in the literature [17, 16] chiefly because it is amenable to analysis and provides a baseline against which performance of other mobility models can be compared. Moreover, this class of Markovian mobility models has been used to model the movements of vehicles [3, 21]. • We assume that all cars start from the stationary distribution and perform independent random walks. Although for sparse density scenarios, the independence assumption does hold, it is no longer valid when N approaches G. • Let the size of data item repository of interest be T. Also, data item i has ri replicas. This implies ri cars, identified as servers, have a copy of this data item when the client requests item i. All analysis results presented in this section are obtained assuming that the client is willing to wait as long as it takes for its request to be satisfied (unbounded trip duration γ = ∞). With the random walk mobility model on a 2D-torus, there is a guarantee that as long as there is at least one replica of the requested data item in the network, the client will eventually encounter this replica [2]. Extensions to the analysis that also consider finite trip durations can be obtained in [9]. Consider a scenario where no zebroids are employed. In this case, the expected availability latency for the data item is the expected meeting time of the random walk undertaken by the client with any of the random walks performed by the servers. Aldous et al. [2] show that the the meeting time of two random walks in such a setting can be modelled as an exponential distribution with the mean C = c · G · log G, where the constant c 0.17 for G ≥ 25. The meeting time, or equivalently the availability latency δi, for the client requesting data item i is the time till it encounters any of these ri replicas for the first time. This is also an exponential distribution with the following expected value (note that this formulation is valid only for sparse cases when G >> ri): δi = cGlogG ri The aggregate availability latency without employing zebroids is then this expression averaged over all data items, weighted by their frequency of access: δagg(no − zeb) = T i=1 fi · c · G · log G ri = T i=1 fi · C ri (2) 77 4.1 One-instantaneous zebroids Recall that with one-instantaneous zebroids, for a given request, a new replica is created on a car in the vicinity of the server, provided this car meets the client earlier than any of the ri servers. Moreover, this replica is spawned at the time step when the client issues the request. Let Nc i be the expected total number of nodes that are in the same cell as any of the ri servers. Then, we have Nc i = (N − ri) · (1 − (1 − 1 G )ri ) (3) In the analytical model, we assume that Nc i new replicas are created, so that the total number of replicas is increased to ri +Nc i . The availability latency is reduced since the client is more likely to meet a replica earlier. The aggregated expected availability latency in the case of one-instantaneous zebroids is then given by, δagg(zeb) = T i=1 fi · c · G · log G ri + Nc i = T i=1 fi · C ri + Nc i (4) Note that in obtaining this expression, for ease of analysis, we have assumed that the new replicas start from random locations in the torus (not necessarily from the same cell as the original ri servers). It thus treats all the Nc i carriers independently, just like the ri original servers. As we shall show below by comparison with simulations, this approximation provides an upper-bound on the improvements that can be obtained because it results in a lower expected latency at the client. It should be noted that the procedure listed above will yield a similar latency to that employed by a dispatcher employing oneinstantaneous zebroids (see Section 3.1). Since the dispatcher is aware of all future car movements it would only transfer the requested data item on a single zebroid, if it determines that the zebroid will meet the client earlier than any other server. This selected zebroid is included in the Nc i new replicas. 4.2 z-relay zebroids To calculate the expected availability latency with z-relay zebroids, we use a coloring problem analog similar to an approach used by Spyropoulos et al. [17]. Details of the procedure to obtain a closed-form expression are given in [9]. The aggregate availability latency (δagg) with z-relay zebroids is given by, δagg(zeb) = T i=1 [fi · C N + 1 · 1 N + 1 − ri · (N · log N ri − log (N + 1 − ri))] (5) 5. SIMULATION METHODOLOGY The simulation environment considered in this study comprises of vehicles such as cars that carry a fraction of the data item repository. A prediction accuracy parameter inherently provides a certain probabilistic guarantee on the confidence of the car route predictions known at the dispatcher. A value of 100% implies that the exact routes of all cars are known at all times. A 70% value for this parameter indicates that the routes predicted for the cars will match the actual ones with probability 0.7. Note that this probability is spread across the car routes for the entire trip duration. We now provide the preliminaries of the simulation study and then describe the parameter settings used in our experiments. • Similar to the analysis methodology, the map used is a 2D torus. A Markov mobility model representing a unbiased 2D random walk on the surface of the torus describes the movement of the cars across this torus. • Each grid/cell is a unique state of this Markov chain. In each time slot, every car makes a transition from a cell to any of its neighboring 8 cells. The transition is a function of the current location of the car and a probability transition matrix Q = [qij] where qij is the probability of transition from state i to state j. Only AutoMata equipped cars within the same cell may communicate with each other. • The parameters γ, δ have been discretized and expressed in terms of the number of time slots. • An AutoMata device does not maintain more than one replica of a data item. This is because additional replicas occupy storage without providing benefits. • Either one-instantaneous or z-relay zebroids may be employed per client request for latency improvement. • Unless otherwise mentioned, the prediction accuracy parameter is assumed to be 100%. This is because this study aims to quantify the effect of a large number of parameters individually on availability latency. Here, we set the size of every data item, Si, to be 1. α represents the number of storage slots per AutoMata. Each storage slot stores one data item. γ represents the duration of the client"s journey in terms of the number of time slots. Hence the possible values of availability latency are between 0 and γ. δ is defined as the number of time slots after which a client AutoMata device will encounter a replica of the data item for the first time. If a replica for the data item requested was encountered by the client in the first cell then we set δ = 0. If δ > γ then we set δ = γ indicating that no copy of the requested data item was encountered by the client during its entire journey. In all our simulations, for illustration we consider a 5 × 5 2D-torus with γ set to 10. Our experiments indicate that the trends in the results scale to maps of larger size. We simulated a skewed distribution of access to the T data items that obeys Zipf"s law with a mean of 0.27. This distribution is shown to correspond to sale of movie theater tickets in the United States [6]. We employ a replication scheme that allocates replicas for a data item as a function of the square-root of the frequency of access of that item. The square-root replication scheme is shown to have competitive latency performance over a large parameter space [8]. The data item replicas are distributed uniformly across the AutoMata devices. This serves as the base-line no-zebroids case. The square-root scheme also provides the initial replica distribution when zebroids are employed. Note that the replacements performed by the zebroids will cause changes to the data item replica distribution. Requests generated as per the Zipf distribution are issued one at a time. The client car that issues the request is chosen in a round-robin manner. After a maximum period of γ, the latency encountered by this request is recorded. In all the simulation results, each point is an average of 200,000 requests. Moreover, the 95% confidence intervals determined for the results are quite tight for the metrics of latency and replacement overhead. Hence, we only present them for the metric that captures the percentage improvement in latency with respect to the no-zebroids case. 6. RESULTS In this section, we describe our evaluation results where the following key questions are addressed. With a wide choice of replacement schemes available for a zebroid, what is their effect on availability latency? A more central question is: Do zebroids provide 78 0 20 40 60 80 100 1.5 2 2.5 3 3.5 Number of cars Aggregate availability latency (δ agg ) lru_global lfu_global lru_local lfu_local random Figure 1: Figure 1 shows the availability latency when employing one-instantaneous zebroids as a function of (N,α) values, when the total storage in the system is kept fixed, ST = 200. significant improvements in availability latency? What is the associated overhead incurred in employing these zebroids? What happens to these improvements in scenarios where a dispatcher may have imperfect information about the car routes? What inherent trade-offs exist between car density and storage per car with regards to their combined as well as individual effect on availability latency in the presence of zebroids? We present both simple analysis and detailed simulations to provide answers to these questions as well as gain insights into design of carrier-based systems. 6.1 How does a replacement scheme employed by a zebroid impact availability latency? For illustration, we present ‘scale-up" experiments where oneinstantaneous zebroids are employed (see Figure 1). By scale-up, we mean that α and N are changed proportionally to keep the total system storage, ST , constant. Here, T = 50 and ST = 200. We choose the following values of (N,α) = {(20,10), (25,8), (50,4), (100,2)}. The figure indicates that a random replacement scheme shows competitive performance. This is because of several reasons. Recall that the initial replica distribution is set as per the squareroot replication scheme. The random replacement scheme does not alter this distribution since it makes replacements blind to the popularity of a data item. However, the replacements cause dynamic data re-organization so as to better serve the currently active request. Moreover, the mobility pattern of the cars is random, hence, the locations from which the requests are issued by clients are also random and not known a priori at the dispatcher. These findings are significant because a random replacement policy can be implemented in a simple decentralized manner. The lru-global and lfu-global schemes provide a latency performance that is worse than random. This is because these policies rapidly develop a preference for the more popular data items thereby creating a larger number of replicas for them. During eviction, the more popular data items are almost never selected as a replacement candidate. Consequently, there are fewer replicas for the less popular items. Hence, the initial distribution of the data item replicas changes from square-root to that resembling linear replication. The higher number of replicas for the popular data items provide marginal additional benefits, while the lower number of replicas for the other data items hurts the latency performance of these global policies. The lfu-local and lru-local schemes have similar performance to random since they do not have enough history of local data item requests. We speculate that the performance of these local policies will approach that of their global variants for a large enough history of data item requests. On account of the competitive performance shown by a random policy, for the remainder of the paper, we present the performance of zebroids that employ a random replacement policy. 6.2 Do zebroids provide significant improvements in availability latency? We find that in many scenarios employing zebroids provides substantial improvements in availability latency. 6.2.1 Analysis We first consider the case of one-instantaneous zebroids. Figure 2.a shows the variation in δagg as a function of N for T = 10 and α = 1 with a 10 × 10 torus using Equation 4. Both the x and y axes are drawn to a log-scale. Figure 2.b show the % improvement in δagg obtained with one-instantaneous zebroids. In this case, only the x-axis is drawn to a log-scale. For illustration, we assume that the T data items are requested uniformly. Initially, when the network is sparse the analytical approximation for improvements in latency with zebroids, obtained from Equations 2 and 4, closely matches the simulation results. However, as N increases, the sparseness assumption for which the analysis is valid, namely N << G, is no longer true. Hence, the two curves rapidly diverge. The point at which the two curves move away from each other corresponds to a value of δagg ≤ 1. Moreover, as mentioned earlier, the analysis provides an upper bound on the latency improvements, as it treats the newly created replicas given by Nc i independently. However, these Nc i replicas start from the same cell as one of the server replicas ri. Finally, the analysis captures a oneshot scenario where given an initial data item replica distribution, the availability latency is computed. The new replicas created do not affect future requests from the client. On account of space limitations, here, we summarize the observations in the case when z-relay zebroids are employed. The interested reader can obtain further details in [9]. Similar observations, like the one-instantaneous zebroid case, apply since the simulation and analysis curves again start diverging when the analysis assumptions are no longer valid. However, the key observation here is that the latency improvement with z-relay zebroids is significantly better than the one-instantaneous zebroids case, especially for lower storage scenarios. This is because in sparse scenarios, the transitive hand-offs between the zebroids creates higher number of replicas for the requested data item, yielding lower availability latency. Moreover, it is also seen that the simulation validation curve for the improvements in δagg with z-relay zebroids approaches that of the one-instantaneous zebroid case for higher storage (higher N values). This is because one-instantaneous zebroids are a special case of z-relay zebroids. 6.2.2 Simulation We conduct simulations to examine the entire storage spectrum obtained by changing car density N or storage per car α to also capture scenarios where the sparseness assumptions for which the analysis is valid do not hold. We separate the effect of N and α by capturing the variation of N while keeping α constant (case 1) and vice-versa (case 2) both with z-relay and one-instantaneous zebroids. Here, we set the repository size as T = 25. Figure 3 captures case 1 mentioned above. Similar trends are observed with case 2, a complete description of those results are available in [9]. With Figure 3.b, keeping α constant, initially increasing car density has higher latency benefits because increasing N introduces more zebroids in the system. As N is further increased, ω reduces because the total storage in the system goes up. Consequently, the number of replicas per data item goes up thereby increasing the 79 number of servers. Hence, the replacement policy cannot find a zebroid as often to transport the requested data item to the client earlier than any of the servers. On the other hand, the increased number of servers benefits the no-zebroids case in bringing δagg down. The net effect results in reduction in ω for larger values of N. 10 1 10 2 10 3 10 −1 10 0 10 1 10 2 Number of cars no−zebroidsanal no−zebroids sim one−instantaneous anal one−instantaneoussim Aggregate Availability latency (δagg ) 2.a) δagg 10 1 10 2 10 3 0 10 20 30 40 50 60 70 80 90 100 Number of cars % Improvement in δagg wrt no−zebroids (ω) analytical upper−bound simulation 2.b) ω Figure 2: Figure 2 shows the latency performance with oneinstantaneous zebroids via simulations along with the analytical approximation for a 10 × 10 torus with T = 10. The trends mentioned above are similar to that obtained from the analysis. However, somewhat counter-intuitively with relatively higher system storage, z-relay zebroids provide slightly lower improvements in latency as compared to one-instantaneous zebroids. We speculate that this is due to the different data item replica distributions enforced by them. Note that replacements performed by the zebroids cause fluctuations in these replica distributions which may effect future client requests. We are currently exploring suitable choices of parameters that can capture these changing replica distributions. 6.3 What is the overhead incurred with improvements in latency with zebroids? We find that the improvements in latency with zebroids are obtained at a minimal replacement overhead (< 1 per client request). 6.3.1 Analysis With one-instantaneous zebroids, for each client request a maximum of one zebroid is employed for latency improvement. Hence, the replacement overhead per client request can amount to a maximum of one. Recall that to calculate the latency with one-instantaneous 0 50 100 150 200 250 300 350 400 0 1 2 3 4 5 6 Number of cars Aggregate availability latency (δagg ) no−zebroids one−instantaneous z−relays 3.a 0 50 100 150 200 250 300 350 400 0 10 20 30 40 50 60 Number of cars % Improvement in δagg wrt no−zebroids (ω) one−instantaneous z−relays 3.b Figure 3: Figure 3 depicts the latency performance with both one-instantaneous and z-relay zebroids as a function of the car density when α = 2 and T = 25. zebroids, Nc i new replicas are created in the same cell as the servers. Now a replacement is only incurred if one of these Nc i newly created replicas meets the client earlier than any of the ri servers. Let Xri and XNc i respectively be random variables that capture the minimum time till any of the ri and Nc i replicas meet the client. Since Xri and XNc i are assumed to be independent, by the property of exponentially distributed random variables we have, Overhead/request = 1 · P(XNc i < Xri ) + 0 · P(Xri ≤ XNc i ) (6) Overhead/request = ri C ri C + Nc i C = ri ri + Nc i (7) Recall that the number of replicas for data item i, ri, is a function of the total storage in the system i.e., ri = k·N ·α where k satisfies the constraint 1 ≤ ri ≤ N. Using this along with Equation 2, we get Overhead/request = 1 − G G + N · (1 − k · α) (8) Now if we keep the total system storage N · α constant since G and T are also constant, increasing N increases the replacement overhead. However, if N ·α is constant then increasing N causes α 80 0 20 40 60 80 100 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 Number of cars one−instantaneous zebroids Average number of replacements per request (N=20,α=10) (N=25,α=8) (N=50,α=4) (N=100,α=2) Figure 4: Figure 4 captures replacement overhead when employing one-instantaneous zebroids as a function of (N,α) values, when the total storage in the system is kept fixed, ST = 200. to go down. This implies that a higher replacement overhead is incurred for higher N and lower α values. Moreover, when ri = N, this means that every car has a replica of data item i. Hence, no zebroids are employed when this item is requested, yielding an overhead/request for this item as zero. Next, we present simulation results that validate our analysis hypothesis for the overhead associated with deployment of one-instantaneous zebroids. 6.3.2 Simulation Figure 4 shows the replacement overhead with one-instantaneous zebroids when (N,α) are varied while keeping the total system storage constant. The trends shown by the simulation are in agreement with those predicted by the analysis above. However, the total system storage can be changed either by varying car density (N) or storage per car (α). On account of similar trends, here we present the case when α is kept constant and N is varied (Figure 5). We refer the reader to [9] for the case when α is varied and N is held constant. We present an intuitive argument for the behavior of the perrequest replacement overhead curves. When the storage is extremely scarce so that only one replica per data item exists in the AutoMata network, the number of replacements performed by the zebroids is zero since any replacement will cause a data item to be lost from the system. The dispatcher ensures that no data item is lost from the system. At the other end of the spectrum, if storage becomes so abundant that α = T then the entire data item repository can be replicated on every car. The number of replacements is again zero since each request can be satisfied locally. A similar scenario occurs if N is increased to such a large value that another car with the requested data item is always available in the vicinity of the client. However, there is a storage spectrum in the middle where replacements by the scheduled zebroids result in improvements in δagg (see Figure 3). Moreover, we observe that for sparse storage scenarios, the higher improvements with z-relay zebroids are obtained at the cost of a higher replacement overhead when compared to the one-instantaneous zebroids case. This is because in the former case, each of these z zebroids selected along the lowest latency path to the client needs to perform a replacement. However, the replacement overhead is still less than 1 indicating that on an average less than one replacement per client request is needed even when z-relay zebroids are employed. 0 50 100 150 200 250 300 350 400 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Number of cars z−relays one−instantaneous Average number of replacements per request Figure 5: Figure 5 shows the replacement overhead with zebroids for the cases when N is varied keeping α = 2. 10 20 30 40 50 60 70 80 90 100 0 0.5 1 1.5 2 2.5 3 3.5 4 Prediction percentage no−zebroids (N=50) one−instantaneous (N=50) z−relays (N=50) no−zebroids (N=200) one−instantaneous (N=200) z−relays (N=200) Aggregate Availability Latency (δagg ) Figure 6: Figure 6 shows δagg for different car densities as a function of the prediction accuracy metric with α = 2 and T = 25. 6.4 What happens to the availability latency with zebroids in scenarios with inaccuracies in the car route predictions? We find that zebroids continue to provide improvements in availability latency even with lower accuracy in the car route predictions. We use a single parameter p to quantify the accuracy of the car route predictions. 6.4.1 Analysis Since p represents the probability that a car route predicted by the dispatcher matches the actual one, hence, the latency with zebroids can be approximated by, δerr agg = p · δagg(zeb) + (1 − p) · δagg(no − zeb) (9) δerr agg = p · δagg(zeb) + (1 − p) · C ri (10) Expressions for δagg(zeb) can be obtained from Equations 4 (one-instantaneous) or 5 (z-relay zebroids). 6.4.2 Simulation Figure 6 shows the variation in δagg as a function of this route prediction accuracy metric. We observe a smooth reduction in the 81 improvement in δagg as the prediction accuracy metric reduces. For zebroids that are scheduled but fail to rendezvous with the client due to the prediction error, we tag any such replacements made by the zebroids as failed. It is seen that failed replacements gradually increase as the prediction accuracy reduces. 6.5 Under what conditions are the improvements in availability latency with zebroids maximized? Surprisingly, we find that the improvements in latency obtained with one-instantaneous zebroids are independent of the input distribution of the popularity of the data items. 6.5.1 Analysis The fractional difference (labelled ω) in the latency between the no-zebroids and one-instantaneous zebroids is obtained from equations 2, 3, and 4 as ω = T i=1 fi·C ri − T i=1 fi·C ri+(N−ri)·(1−(1− 1 G )ri ) T i=1 fi·C ri (11) Here C = c·G·log G. This captures the fractional improvement in the availability latency obtained by employing one-instantaneous zebroids. Let α = 1, making the total storage in the system ST = N. Assuming the initial replica distribution is as per the squareroot replication scheme, we have, ri = √ fi·N T j=1 √ fj . Hence, we get fi = K2 ·r2 i N2 , where K = T j=1 fj. Using this, along with the approximation (1 − x)n 1 − n · x for small x, we simplify the above equation to get, ω = 1 − T i=1 ri 1+ N−ri G T i=1 ri In order to determine when the gains with one-instantaneous zebroids are maximized, we can frame an optimization problem as follows: Maximize ω, subject to T i=1 ri = ST THEOREM 1. With a square-root replication scheme, improvements obtained with one-instantaneous zebroids are independent of the input popularity distribution of the data items. (See [9] for proof) 6.5.2 Simulation We perform simulations with two different frequency distribution of data items: Uniform and Zipfian (with mean= 0.27). Similar latency improvements with one-instantaneous zebroids are obtained in both cases. This result has important implications. In cases with biased popularity toward certain data items, the aggregate improvements in latency across all data item requests still remain the same. Even in scenarios where the frequency of access to the data items changes dynamically, zebroids will continue to provide similar latency improvements. 7. CONCLUSIONS AND FUTURE RESEARCH DIRECTIONS In this study, we examined the improvements in latency that can be obtained in the presence of carriers that deliver a data item from a server to a client. We quantified the variation in availability latency as a function of a rich set of parameters such as car density, storage per car, title database size, and replacement policies employed by zebroids. Below we summarize some key future research directions we intend to pursue. To better reflect reality we would like to validate the observations obtained from this study with some real world simulation traces of vehicular movements (for example using CORSIM [1]). This will also serve as a validation for the utility of the Markov mobility model used in this study. We are currently analyzing the performance of zebroids on a real world data set comprising of an ad-hoc network of buses moving around a small neighborhood in Amherst [4]. Zebroids may also be used for delivery of data items that carry delay sensitive information with a certain expiry. Extensions to zebroids that satisfy such application requirements presents an interesting future research direction. 8. ACKNOWLEDGMENTS This research was supported in part by an Annenberg fellowship and NSF grants numbered CNS-0435505 (NeTS NOSS), CNS-0347621 (CAREER), and IIS-0307908. 9. REFERENCES [1] Federal Highway Administration. Corridor simulation. Version 5.1, http://www.ops.fhwa.dot.gov/trafficanalysistools/cors im.htm. [2] D. Aldous and J. Fill. Reversible markov chains and random walks on graphs. Under preparation. [3] A. Bar-Noy, I. Kessler, and M. Sidi. Mobile Users: To Update or Not to Update. In IEEE Infocom, 1994. [4] J. Burgess, B. Gallagher, D. Jensen, and B. Levine. MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networking. In IEEE Infocom, April 2006. [5] E. Cohen and S. Shenker. Replication Strategies in Unstructured Peer-to-Peer Networks. In SIGCOMM, 2002. [6] A. Dan, D. Dias, R. Mukherjee, D. Sitaram, and R. Tewari. Buffering and Caching in Large-Scale Video Servers. In COMPCON, 1995. [7] S. Ghandeharizadeh, S. Kapadia, and B. Krishnamachari. PAVAN: A Policy Framework for Content Availabilty in Vehicular ad-hoc Networks. In VANET, New York, NY, USA, 2004. ACM Press. [8] S. Ghandeharizadeh, S. Kapadia, and B. Krishnamachari. Comparison of Replication Strategies for Content Availability in C2P2 networks. In MDM, May 2005. [9] S. Ghandeharizadeh, S. Kapadia, and B. Krishnamachari. An Evaluation of Availability Latency in Carrier-based Vehicular ad-hoc Networks. Technical report, Department of Computer Science, University of Southern California,CENG-2006-1, 2006. [10] S. Ghandeharizadeh and B. Krishnamachari. C2p2: A peer-to-peer network for on-demand automobile information services. In Globe. IEEE, 2004. [11] T. Hara. Effective Replica Allocation in ad-hoc Networks for Improving Data Accessibility. In IEEE Infocom, 2001. [12] H. Hayashi, T. Hara, and S. Nishio. A Replica Allocation Method Adapting to Topology Changes in ad-hoc Networks. In DEXA, 2005. [13] P. Juang, H. Oki, Y. Wang, M. Martonosi, L. Peh, and D. Rubenstein. Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet. SIGARCH Comput. Archit. News, 2002. [14] A. Pentland, R. Fletcher, and A. Hasson. DakNet: Rethinking Connectivity in Developing Nations. Computer, 37(1):78-83, 2004. [15] F. Sailhan and V. Issarny. Cooperative Caching in ad-hoc Networks. In MDM, 2003. [16] R. Shah, S. Roy, S. Jain, and W. Brunette. Data mules: Modeling and analysis of a three-tier architecture for sparse sensor networks. Elsevier ad-hoc Networks Journal, 1, September 2003. [17] T. Spyropoulos, K. Psounis, and C. Raghavendra. Single-Copy Routing in Intermittently Connected Mobile Networks. In SECON, April 2004. [18] A. Tanenbaum. Modern Operating Systems, 2nd Edition, Chapter 4, Section 4.4 . Prentice Hall, 2001. [19] A. Vahdat and D. Becker. Epidemic routing for partially-connected ad-hoc networks. Technical report, Department of Computer Science, Duke University, 2000. [20] W. Zhao, M. Ammar, and E. Zegura. A message ferrying approach for data delivery in sparse mobile ad-hoc networks. In MobiHoc, pages 187-198, New York, NY, USA, 2004. ACM Press. [21] M. Zonoozi and P. Dassanayake. User Mobility Modeling and Characterization of Mobility Pattern. IEEE Journal on Selected Areas in Communications, 15:1239-1252, September 1997. 82
mobile device availability latency car density storage per device repository size replacement policy zebroid mobility latency
audio and video clip peer-to-peer vehicular ad-hoc network datum carrier termed zebroid naive random replacement policy simplified instantiation of zebroid zebroid simplified instantiation vehicular network automaton markov model