The recent advances in the development of capable smart wireless devices and mobile internet services have resulted in groundbreaking levels of data traffic over cellular networks. This excessive data demand is depleting the limited spectrum resources of wireless transmissions, especially the wireless connection between the base stations and the end-users. Consequently, wireless resources are becoming scarce due to the tremendous development of throughput-hungry applications including video streaming and online gaming. Thus, more sophisticated resource management strategies are needed in order to effectively meet the growing demand.
To tackle this problem, several techniques have already been proposed such as WiFi offloading, proactive caching, and wireless multicasting. WiFi offloading is a straightforward approach that communicates some of the wireless cellulars data through WiFi networks (e.g., [1]). Different approaches to implement WiFi offloading and to improve its performance have been investigated in [2]. In the aforementioned approaches, scheduling of wireless demand is applied reactively so that data requests are initiated beforehand, and the service provider utilizes the delay tolerance from end-users to schedule them efficiently. Thus, cost reduction comes at the expense of disturbed user activity patterns as the service is postponed to off-peak times, or the next available WiFi connection. Another possible solution to address the problem is to cache popular contents on the user's site (e.g., [3]). Cache system can help reduce the total response time of users' requests. Cached data can be shared by users at the same site. It also enables reduced peak-to-average traffic ratio for the original data management system [4]. By knowing the popularity of contents, caching efficiency can be improved by pre-downloading popular contents during off-peak times and serving predictable peak-hour demands, which is referred to as proactive caching (see [5]). However, because of the limited capacity of caching storage, this technique has also its limitations.
In this work, we consider another natural alternative strategy to alleviate the growing traffic load of wireless content distribution, namely, multicasting whereby content of common interest is transmitted to multiple users at once. Although arrival requests can be served by sending a separate unicast packet to each user, this approach suffers from poor performance. The situation is especially acute in delay tolerant networks (DTNs) [6].
To illustrate the potential gains of multicasting with an example, consider a football stadium full of people watching a game and after a goal, many of them may request (at different time offsets) the related footage to watch it on their smart device, giving the opportunity to broadcast content of common interest to multiple users with small delay, since in a short period of time, there will be a lot of requests for one content. There are so many similar real world scenarios where a large group of users are interested in a certain group of content during a small time window. These are the scenarios that potentially can have great delay gains using the proposed model. Since by utilizing the multicast nature of wireless communication on the edge, instead of sending same content to multiple users separately, we can collect the requests of the content and then broadcast it using one service of that content over the wireless medium.
In particular, we focus on the distribution of data content to dynamic users over wireless channels, whereby the wireless network can simultaneously serve all the requests awaiting the same data content at the time. Our contributions, along with the organization of the paper, are as follows.
• In Section III, we present a tractable content distribution model for serving dynamically arriving demand over wireless broadcast channels. • In Section IV-A, for a database of n items with an arbitrary popularity distribution, we develop the optimal static-randomized multicasting strategy (called blind multicasting) that minimizes the aggregate average number of requests in the system. While unicast transmissions can only stabilize the system when the loading factor ρ (given by the ratio of the demand rate to the service rate) is less than 1, we show in Theorem 1 (proved in Section V-A) that under our blind multicasting, the system is always stable for all ρ ≥ 0. • Moving beyond stability for the worst-case uniform popularity distribution, in Section IV-B we expand the policies to the more efficient class of work conserving multicasting policies in order to improve the delay gains. In Theorem 2, we explicitly characterize the scaling delay gains of the First-Come-First-Serve work-conserving multicasting strategy as a function of the loading factor ρ and the database size n. The proof of Theorem 2, presented in Section V-B, may be of independent-value as it utilizes a novel approach for dealing with the nontraditional abruptly-changing (as opposed to the traditional incremental) nature of queueing dynamics under multicasting transmissions.
• In Section VI, we provide numerical simulations to validate the analytical results and compare the performance to other service strategies such as Max-Weightbased multicasting. Finally, we conclude in Section VII.
In the next section we provide a literature review of all the related works on multicast networks.
There are massive amount of works in liturature that study the multicast in wireless networks [7], [8] and [9]. Some of these works focus on the delay performance of multicasting. In [10], [11] and [12], authors study the problem of multicasting in delay tolerant networks. In multi-hop wireless network, [13] and [14] show that cross-layer cooperation of different network layers is needed to efficiently utilize network resources. In [15], by incorporating delay differentiation into cross-layer framework, authors propose a novel Cross-Layer Control algorithm (CLC-DD) that takes into account different delay requirements of flows. The main idea of the proposed algorithm is to distribute delays among flows to achieve low delays for delay-sensitive flows at the expense of increasing the delays of other flows, while simultaneously guaranteeing maximum network utility. In [16] and [17], authors use network coding for reducing transmission delay of large files in multicasts. In [18], using the network coding approach, authors analyze the delay performance in multicasting systems and show that delay can be minimized by appropriate scheduling of data packets and appropriate size of the coding buffer. In [19], authors propose an efficient framework to model the statistical delay QoS guarantees and develop a set of optimal adaptive transmission schemes to minimize the resource consumption while satisfying the diverse QoS requirements under various scenarios, including video unicast/multicast. Traditional solution on multicasting over IP-based network rely on IP multicast which suffer from poor congestion control, as well as slow and complex group membership and multicast tree management on the control plane [20]. Even though multicasting is widely acknowledged to be a promising approach in IP-based wireless networks, the complex dynamic multicast tree building and maintenance, specially for large database sizes, increases the latency and have caused most network operators to eschew its use [21] and [22]. As datacenter size continues to grow, one approach is to deploy a high bandwidth network core for datacenters using optical communication technologies [23]. In [24], authors propose HyperOptics, a low latency optical multicast architecture for datacenters which eliminates the reconfiguration delay by using optical switches.
Transitioning from IP based networks to informationcentric networks (see [25] and [26]) encourages us to rigorously investigate the multicasting gain in informationcentric networks. Such networks allow us to group requests targeting the same content and serve all of them at once, eliminating the need for dynamic multicast tree building and maintenance. To achieve this multicasting gain, some requests will not be served instantly. In other words, requests from different users for the same content do not happen at the exact same time. Users with earlier requests have to wait until the content is scheduled for service. This introduces the delay which each incoming request needs to sustain before it can be served by database.
In real world scenarios, usually, requests are correlated and this will help the multicast to potentially have great delay gains by utilizing the multicast nature of the wireless communication which is already available on the edge. Base station will collect the requests and put them in dedicated queues to be broadcasted upon the availability of the service. Delay gains in queuing theory are well known and traditional queuing dynamics, under which requests are served one by one [27], have been investigated in various works (see [28] for a survey). However, in our multicasting scenario, due to the service of all pending demands at once, previous wellknown techniques such as Lyapunov-drift [29] or fluid-limit [30] analysis techniques do not apply. We aim to reveal the stability conditions and the delay gains that multicasting can offer over its unicast counterpart using queuing dynamics. The multicasting scenario introduces new challenges which have not been studied before and to the best of our knowl-edge, this is the first work to study the delay gains of workconserving multicasting using queuing theory. In order to analyze the delay performance of work-conserving multicast in information-centric networks, we take a different novel approach based on the number of active queues. This work extends [31] to improve the bounds as well as obtain an exact asymptotic expression with numerical simulations.
We consider a wireless network comprising a content provider that serves a population of users through a wireless base station (BS) deployed at the network edge. In a continuous time fashion, the usersfoot_0 dynamically send requests targeting content from a set of n data items with certain popularity distribution offered by the content provider. The wireless BS enqueues the incoming requests in n distinct queues, one queue per data item, in order to serve them. Demand Generation: The population of users covered by the BS are assumed to generate data requests according to a Poisson process with rate λ. That is, for A tot (t), t ≥ 0 being the aggregated number of generated requests by time t, then A tot (t) is a Poisson random variable with mean λt.
The incoming requests at any point in time are split independently over the n data items based on their respective popularity. We capture the popularity of a data item k by the probability of that item k being intended by a request given a request is already generated. We denote such probability by
Thus, the aggregate request generation process {A tot (t)} t is the superposition of n independent Poisson processes A tot (t) := n k=1 A k (t), where A k (t), t ≥ 0 is the request arrival process for item k which is Poisson with rate α k λ. We consider the vector α := (α k ) n k=1 as the popularity profile of the system. Service Dynamics: The base station serves requests one at a time, i.e., a single-server system. The service time of an individual request is considered to follow an exponential distribution with mean 1/µ and the service times are assumed independent and identically distributed over time and requests. While, in practice, service times may exhibit heavily-tailed distributions due to data item length and retransmissions over the wireless medium, we adopt the exponential distribution to allow tractable characterization of the multicasting gains and contrast it with the well-known unicast results that are already derived for exponentially distributed service times.
The n queues maintained at the BS hold the requests awaiting service with queue k has all the pending requests for item k. We consider these queues to be of infinite length, hence we are not concerned with outage events due to lost requests. Instead, we care about the average delay these requests incur as our metric of interest. Since the set of items requested by users in a typical content distribution network is very large, considering that n → ∞ is a reasonable assumption.
We denote the number of requests in queue k at time t by Q k (t), k = 1, • • • , n. We define the service completion of a request from queue k as an ON-OFF process B k (t) where B k (t) = 1 if a request from queue k has completed service at time t, otherwise B k (t) = 0. We can thus define the service completion of any request from any queue as the ON-OFF process B tot (t) := 1 shows the model for our queueing system. Requests are generated at a rate of λ and based on the item being requested, each request is placed in a queue dedicated for that item. Then requests are served at the BS with a rate of µ > 0.
In this paper, we are interested in the comparative and comprehensive study of unicast (as the baseline that is widely adopted by today's wireless technologies) and multicast modes of service that are described next.
Unicast and Multicast Operation: Through unicast operation, the BS has to individually serve the requests in each queue, one request at a time. Thus, when a request is served from any queue, the length of such queue is decremented by one. Let Q U k (t) be the number of requests in queue k at time t under the unicast operation, then for dt being an infinitesimal increment in time, thenfoot_1
where [x] + = max{0, x}.
In the multicast operation, the BS relies on the broadcast nature of the wireless medium to send the requested data simultaneously to all the requesting users, consuming the same amount of resources required by a single unicast transmission. Thus, if Q M k (t) is the number of requests in Queue k under the multicast operation, then
that is, as shown in Fig. 1, the service of a single request from queue k collectively serves all of the requests in queue k yielding an empty queue after each service. This is the key difference between multicast and unicast dynamics.
Performance Metric: We use the time-average expected number of requests in the system as our performance metric to quantify the gains of multicasting. At any time t, the number of requests in the system under U nicast and M ulticast operations are Q U tot (t) and Q M tot (t), respectively, where
For any queue-length process Q k (t), we use the notation Q k to indicate its time-average expected value, that is,
Accordingly, the time-average of the expected total number of requests in the system under unicast and multicast operation is denoted by
We finally define the loading factor ρ := λ µ as a key parameter shaping the traffic intensity of the system. We then investigate the system's performance with the number of data items n in different regimes of ρ. We begin with the unicast operation as it constitutes our baseline model. From the well known results of an M/M/1 queue [32], we have
which clearly shows that the system can be stabilized by unicasting only for ρ < 1. We can also observe that Q U tot depends neither on the number of data items n, nor on the individual popularity of data items, since the service of requests is carried out on an individual request basis. In the following sections, we investigate the behavior of Q M tot and compare it to that of its unicast counterpart.
This section presents the main results of this paper and highlights the significant multicasting gains, with their detailed proofs postponed to Section V. We first show the endless stability operation furnished by simple multicasting strategies (cf. Theorem 1). Then, we explore further multicasting gains under a first-come-first-serve work-conserving operation (cf. Theorem 2). We conclude this section with a discussion of key insights from these results.
We begin by considering a simple static multicasting strategy which we label blind multicast. This strategy is suitable for scenarios whereby the individual requests are not known by the BS, and multicasting decisions are made blindly based on the statistical popularity information. As such, it is convenient in conditions when it is not feasible to receive feedback from the individual users.
Definition 1 (Blind Multicast): strategy through which the BS randomly assigns the service resources to n queues such that
for (β k ) n k=1 is a vector of non-negative weights to be determined.
We can note from the definition that the allocation of the service resources to queues is independent of the queue length, hence the naming blind. A blind multicasting strategy thus assigns the service to queue k for a fraction β k of the time irrespective of its instantaneous state.
The whole system under blind multicast can be split into n independent and parallel queues with queue k having an arrival rate of α k λ and service rate β k µ with state evolution as shown in Fig. 2. Each state represents the number of requests in the queue k. We have the following result for such multicasting.
Theorem 1 (Endless Stability of Delay-Optimizing Blind Multicast): Let Q M,B tot be the time-average expected number of all requests in the queues under blind multicasting. Then, the average delay-minimizing choice of the design parameters (β k ) k is given by
Accordingly, the time-average expected number of requests under this delay-optimal blind multicast strategy is given by
which can be written as Q M,B tot = ρ||α|| 1 2 . Note that, even in the worst-case of uniform popularities, we have Q M,B tot = ρ n under the optimal blind multicast.
More multicast gains can be reaped under smarter policies that schedule services based on the instantaneous state of the queues. In particular, we consider work-conserving policies that utilize the BS resources for some pending request(s) unless all the queues are empty. However, due to the analytical complexity under a general popularity distribution α, we study the worst case scenario of uniformly distributed popularities that serve as a fundamental lower bound on the performance of a multicasting system besides allowing tractable closed form expressions for the behavior of the average expected number of requests in the system.
Definition 2 (work-conserving Multicast):
We can note from the work-conserving operation that the allocation of the service resources to queues depends on the state of the queue. In this subsection, we consider the wellknown First-Come-First-Serve (FCFS) work-conserving policy to characterize an upper bound on the average expected number of requests in the system. FCFS operates by serving the queue that contains the oldest unserved request first. We choose the FCFS for its time-based ordering of service which enables us to analytically derive our fundamental bound on the system's performance. As such, it possesses fairness characteristics within the class of work-conserving policies. We have the following result.
Theorem 2 (Scaling Delay Gains of Work-Conserving FCFS Multicast): Let Q M,F tot be the time-average expected number of all requests for the FCFS work-conserving multicast strategy under the worst-case of uniform popularities, i.e., α k = 1/n for all k. Then, we have
where
Note that the bound on Q M,F tot is directly related to the average delay experienced by the users via Little's law.
Theorems 1 and 2 reveal the potential for content multicasting to extend the stable operation of the network significantly beyond that of unicasting. In the following remarks, we highlight some insights about those theorems.
Remark 1: Under unicast operation, when ρ ↑ 1, we see from (1) that the average number of requests grows unboundedly, i.e., Q U tot → ∞ signifying the instability of unicast as the traffic intensity becomes higher. Theorem 1, on the other hand, shows that blind multicasting guarantees a finite total average of the number of requests for any popularity distribution α and ρ ≥ 0 as can be seen in (3). Hence, blind multicasting promises endless stability operation for any distribution of content popularity and for any number of content items.
Remark 2: Uniform and degenerate distributions of popularity are, respectively, the Q M,B tot maximizing and minimizing distributions. This can be seen by optimizing (3) for the maximum and minimum values over α, where the maximum value for Q M,B tot is ρ n and the minimum value is ρ. Intuitively, uniformly distributed popularities maximize the average number of distinct data items being requested in the system irrespective of the multicasting scheduling policy. Hence, more requests on average require individual service than under any popularity distribution. The degenerate distribution, on the other hand, implies that all of the incoming traffic is targeting the same data item. Hence, multicasting operation will reap the highest gains.
Note that, using (3), we can also find the delay performance of the optimal blind multicast strategy under more common popularity distributions, such as the Zipf distribution.
A Zipf distribution α z with parameter γ is written as
Remark 3: For large number of content items n and Zipf popularity distribution with parameter γ = 2,
Proof. For γ = 2, the direct substitution of α z in (3) yields:
Which is asymptotically true as n → ∞. Remark 4: For large number of content items n and Zipf popularity distribution with parameter 0 ≤ γ < 2,
Proof. By direct substitution of Zipf distribution with parameter γ in Equation (3), we have:
On the other hand we have:
From equations ( 5) and ( 6) as n grows, we have the result.
Remark 5: Note that the result of ( 1) is obtained assuming work-conserving unicast operation. For stable operation, i.e., ρ < 1, we see that Q U tot is independent of the number of content items n irrespective of their popularity distribution. This is not the case under blind multicast operation for the same range of ρ < 1 where Q M,B tot is determined by both n and α. In fact, for large values of n, and several distributions, e.g., Zipf with γ ≤ 2, we have
tot . Thus, unicast outperforms blind multicast for ρ < 1.
Remark 6: Assume uniform distribution of popularities and ρ > 1. As n → ∞, the average expected number of requests per queue under multicast operation satisfies
That is, FCFS work-conserving multicasting attains an expected value of 1 2 ( ρ 2 -1 ρ ) requests per queue while blind multicasting attains ρ. Thus, FCFS experiences at most half the delay of blind multicasting for ρ > 1.
Remark 7: Assume uniform distribution of popularities and ρ = 1. As n → ∞, the average expected number of requests per queue under multicast operation satisfies
That is, FCFS work-conserving multicasting attains a delay that grows with √ n while blind multicasting delay grows with n. We emphasize that in the case of ρ = 1, FCFS multicasting has its most advantage compared to blind multicasting.
Remark 8: Our analysis reveals important practical insights that, while work-conserving multicast always outperforms unicast and blind-multicast: (i) unicast strategy can be sufficiently satisfactory under lightly-loaded conditions, i.e., when ρ 1; and (ii) blind-multicast strategy tends to suffer a delay performance loss within a factor of 2 under over-loaded conditions, i.e., when ρ 1. The gains of work-conserving multicasting is highest in the regime (that is explicitly characterized by our analysis in terms of ρ and n) where the loading factor is neither too small, nor too large. Table I shows a summary of the main results. For the case of loading factor ρ < 1, our simaulatins shows that unicast performs as good as multicast. In other words for the case ρ < 1 there is no need to multicast and we will just drive an upper bound on the delay of FCFS multicasting for the case ρ < 1.
V. PROOFS OF THE STABILITY AND DELAY GAIN RESULTS
In this section, we provide the full proofs of the main results discussed in the previous section. The proof of Theorem 1 (in Section V-A) is based on decomposing the system into parallel queues to optimize the delay. However, the proof of Theorem 2 (in Section V-B) requires a much more sophisticated strategy due to the coupling between the queues and their nontraditional dynamics.
We start by obtaining the expected queue-length under the blind multicast operation with a general (β k ) k choice.
Lemma 1: Let Q M,B k (t) be the number of requests in queue k under blind multicast operation, then
Proof. For a queue with input rate α k λ and service rate β k µ using the multicast operation, when a new request arrives, number of requests increases by one but when there is a service available for queue k, because of the multicast nature, after serving the total number of requests in queue k becomes 0. Markov chain for queue k is shown in Fig. 2.
The average number of requests in the system is given by: lim
Which p m is the probability of having m requests in queue k. Using the markov chain and by induction we have:
Substituting p m in Equation ( 8) and using the definition of loading factor ρ = λ µ , we have:
We thus have Q
Noting the convexity of this expression with respect to (β k ) k , we use the KKT optimality conditions to find that the choice of β k in (2) minimizes Q M,B tot subject to the constraints that β k ≥ 0, ∀k, and
√ αi in (7) completes the proof of Theorem 1.
Traditional queuing dynamics, under which requests are served one by one, have been investigated in various works (see [28] for a survey). However, in our multicasting scenario, due to the service of all pending demands at once, previous well-known techniques such as Lyapunov-drift [29] or fluid-limit [30] analysis techniques do not apply. In order to analyze and prove the results of multicasting systems, we take a different approach based on the number of active queues defined next.
Definition 3 (Active Queue): We define an active queue as a nonempty queue, i.e., a queue that has at least one request in it. Formally, queue k is active at time
Utilizing the statistics of active queues, we we characterize the behavior of the average number of requests in the system. Each proof is broken down into segments in order to facilitate the understanding. Some of the results in these proofs may be of independent-interest, especially in the case of Theorem 2.
Let N (t) be the Markov process describing the number of active queues at time t under any given work-conserving multicast strategy. The evolution of this process is shown in Fig. 3. We are interested in the limit of N (t)
where
. Proof. Global balance equations of Fig. 3 yields
Replacing λ µ with loading factor ρ gives (9). Then, setting the sum of probabilities to 1 gives the result for π 0 .
We introduce a new parameter s i (ρ, n) as:
3 Such a steady state behavior holds since N (t), t ≥ 0 follows a finite state ergodic Markov chain. which we use in deriving the moments of N (ρ, n). In the light of s i (ρ, n), we can rewrite the π 0 as π 0 = 1 1+s0(ρ,n) . We also make the following connection between s i (ρ, n) and s i-1 (ρ, n).
Lemma 3: For s i (ρ, n) defined in (10),
such that i ∈ {1, 2, ...}.
Proof. We prove this by induction.
We have n terms on the right hand side of ( 12), by induction we can show that sum of p last terms is equal to:
Since we have n total terms, putting p = n gives n ρ (nn) i-1 ρ = nδ(i -1).
Lemma 4: The first and second moments of the number of active queues, N (ρ, n), are given by:
From Lemma 3, writing s 1 (ρ, n) as a function of s 0 (ρ, n) gives Equation (13). Similarly,
Writing s 2 (ρ, n) in terms of s 0 (ρ, n) gives the result in Equation ( 14). Lemma 5: For ρ = 1, s 0 (ρ, n) asymptotically achieves
where a(n)
Rewriting and changing the variable j = n -k gives:
Now by using the fact that n-1 j=0
x j j! = e x Γ(n,x) Γ(n) , such that Γ(n, x) = ∞ x t n-1 e -t dt and Γ(n) = Γ(n, 0) [33], we can rewrite s 0 (1, n) as:
Since from [34],
, and utilizing the asymptotic behavior of Stirling's approximation, we obtain
Proof. First we show that for ρ < 1,
On the other hand we have:
From ( 18) and ( 19), and letting n → ∞, we have:
. By using the definition of f (ρ, n), we have that lim n→∞ f (ρ, n) = ρ. In order to prove the lim n→∞ f (ρ, n) = 1 for ρ > show that for any ρ > 1, s 0 (ρ, n) grows exponentially in n.
Now by the fact that n-1 j=0
For ρ > 1, we have Γ(n, n ρ ) > Γ(n, n), which implies:
and applying Stirling's inequality n! ≥ √ 2πn( n e ) n yields
Setting g(ρ) := 1 ρ + log ρ -1, since g(1) = 1 and g (ρ) > 0 for ρ > 1, s 0 (ρ, n) grows exponentially in n for ρ > 1.
After having introduced a number of crucial lemmas, we proceed to our investigation of the number of requests in the system under work-conserving multicasting. To that end, we focus on the FCFS strategy.
Let Q M,F k (t) be the number of requests in queue k at time t under FCFS work-conserving multicasting and
be the aggregate number of requests in all queues at time t. The following lemma specifies an expression for the average total number of requests in the system under FCFS multicast operation.
Lemma 7:
be the time-average expected number of aggregate requests in the system operating under FCFS multicasting and N k (t) be the number of active queues in the system when queue k just becomes active at time t, then
Proof. Since the request arrivals and services are statistically indistinguishable across the n queues, we have under steady state operation that
Let t 0 = 0 and t i be the time instant at which queue k has completed service for the i th time. So at time instants {t i } i , we will have:
for some 0 < < t i -t i-1 . Let X i be the time it takes queue k to become active for the i th time since it has been last served (emptied) at time
Let τ i denote the duration queue k must wait while being active in order to be fully serviced for the i th time. So t i = t i-1 + X i + τ i . Fig. 4 demonstrates the evolution of queue k under FCFS multicasting. Since we are interested in the average number of requests in queue k, based on Fig. 4 we claim that:
,
where A i is the area shown in figure and based on the
The first term comes from the fact that at time t i there is one arrival to queue k that makes it active and the second term is the area of the triangle knowing that the rate at which queue k receives arrival is λ n . Now we will provide a rigorous proof for the claim we just presented.
We define
, where Y j is the service time of an active queue which has an exponential distribution with mean 1 µ . We are now interested in the time-average pected of in queue k, Q
which is the number of times that queue k has received service by time T . We have:
where
]dt and {M k [i]} i is an identically distributed sequence of random variables. Then:
We note that K T → ∞ and
as T → ∞, both with probability 1. We thus have lim
For E[M k [i]], we have:
where A k (t) is the arrival process to queue k at time t. We thus obtain lim
Which N k (t) is the number of active queue in the system when queue k turns active at time t. Substituting in the previous inequality, we get
By multiplying with n and substituting λ µ with loading factor ρ, we will have the result.
Lemma 8: Let N k (t) be the number of active queues in the system, given that queue k has just become active at time t, then:
Proof. Define N c k (t) which is the number of active queues at time t given that queue k is not active, as:
where 1(x) = 1, x > 0, 0, x = 0. Let t i be the time when queue k just became active for the i th time. Therefore N k (t i ) is the number of active queues when queue k became active for the ith time. Then we can write:
For small enough δ. In other words, at time t i -δ that queue k is not still active, number of active queues is given by N c k (t i -δ). After small enough time δ when queue k just becomes active, the number of active queues is given by N k (t i ). If δ is small enough, queue k turning active is the only event ocurring in the tiny interval (t i -δ, t i ), so the number of active queues will increase exactly by one at the moment when queue k just becomes active. Since A k (t) is the request arrival process for item k which under uniform popularity distribution is a Poisson with rate λ n independent of all the arrival processes to other queues. Let δ be infinitesimally small and define the event
to show the time t that queue k just receives an arrival. Since the arrivals to queues are independently distributed, A k (t) is independent of N c k (t). In other words at any time t, whether there is a arrival to queue k or not is independent of how many active queues are in system given that queue k is not active. We thus have:
since the time that queue k have an arrival given that it was not already active is shown with t i . Under any workconserving multicast strategy, N c k (t) is a Markov process and we are interested in the steady state distribution of
As we started with general t, P (N c k (t) = k) = P ( N c k = k), which gives the distribution of N k (t i as:
Using the Markov chain for N c k (t) under any workconserving multicast, let π k = P ( N c k = k), then:
setting the sum of probabilities to 1 gives π 0 = ρ s0(ρ,n) . Then:
According to Equation ( 26) and letting t be a general time that queue k just became active, we have
Using the Equations ( 11), we expand s 2 (ρ, n) and s 1 (ρ, n) as a function of s 0 (ρ, n). Then comparing the results with Equations ( 13) and ( 14) and using the behaviour of s 0 (ρ, n) which is given at Equation ( 15) for ρ = 1 and in (17) for ρ > 1, we have the results.
Lemma 9: Let N k (t) be the number of active queues in the system, given that queue k has just become active at time t, then for ρ < 1:
Proof. First we show that π k ≤ π k ∀k ≥ 1 which π k and π k are given in Equations ( 9) and ( 27) respectively. Assuming that the inequality π k ≤ π k ∀k ≥ 1 holds, gives: removing the terms from both sides and by replacement we have:
Replacement of s0(ρ,n) 1+s0(ρ,n) =ρ which is given in Lemma 6 for ρ < 1 gives (n -k) ≤ n that is always true for all values of k ≤ n, so the assumption holds.
Then using (26) for arbitrary time t that queue k just becomes active, gives:
which hold for ∀k ≥ 1. Recall that N k (t) ≥ 1, since it at least includes queue k which just became active at time t. Taking expectation of both sides gives,
Now for ρ = 1 and ρ > 1, using the results for E[N k (t)] and E[N k (t) 2 ] given in Equations ( 22) and (23) which is a function of ρ and n from the analysis of active queues and substituting the results in Equation ( 21), we have the exact expression for the total average number of requests in the system operating under FCFS multicasting as a function of ρ and n. For ρ < 1, using the results of Lemma 9 and analysis for statistics of active queues and using the behaviour of s 0 (ρ, n) which is given in Equation ( 17) for ρ < 1, we derive the upper bound for the average number of requests in the system working under FCFS multicasting. Letting n → ∞ gives the result of Theorem 2.
The analytical results obtained in this paper are validated through numerical simulations in this section. Each of the following simulation results is an average behavior over 10 6 iterations. We first validate the main analytical results under uniform popularity distribution, and then provide more numerical results for non-uniform popularity distributions (such as the commonly used Zipf distribution). Moreover, we compare the performance of FCFS work-conserving policy to a heuristic Max-Weight work-conserving multicast policy that is expected to yield favorable delay-minimization merits. We should note that our analysis is conducted under the (c) ρ = 2.
Fig. 6: Average number of requests in the system over n for different loading factors ρ.
assumption of large database size and uniform popularity distribution. We have investigated the average number of requests in the system, proposed an upper bound for the case of ρ < 1 and derived the exact asymptotic expression for the two cases of ρ = 1 and ρ > 1. Also, since the analysis has been provided for asymptotic as n grows, we simulate the system's behavior when the number of data contents, n, is large, we set it to n = 1000, unless stated otherwise.
In Fig. 5, we provide a numerical evaluation of Q U tot and Q M,B tot under different content popularity distributions for n = 1000. For degenerate distribution of content popularity, Q M,B tot is equal to ρ which is the minimum that blind multicast can achieve for given n and ρ. On the other hand, uniform distribution of content popularity gives the maximum value of Q M,B tot which equals nρ. It is obvious from the figure that as ρ approaches 1, unicast system becomes unstable, while blind multicasting operation guarantees a finite total average number of requests upper bounded by n ρ for any popularity distribution α and ρ ≥ 0 as can be seen in Fig. 5. We can also observe from Fig. 5 that unicast outperforms blind multicast for ρ < 1 under the considered instances of Zipf distributed popularity with parameter γ ≤ 2 which is consistent with the insights of Remark 5. Notice the degenerate distribution is a Zipf distribution with parameter γ = ∞ which results in the minimum average delay, shown in Fig. 5 as the minimum blind multicast. Fig. 6 shows the average number of requests as a function of number of queues in a system with uniform distributions of content popularity under different values of loading factor ρ and scheduling policies. We can see that for different levels of the loading factor ρ, the FCFS multicast policy performs very close to the heuristic Max-Weight that serves a queue with the largest number of requests at the time of service, both of which outperform blind multicasting by a large margin. Also, we can see from Fig. 6(c) that our upperbound for the case of ρ < 1 is very accurate even for small number of queues and we expect that as n increases, our upper bound becomes tighter. For the case of ρ = 1 and ρ > 1 our analysis for the average number of active queues that we did under large database size n, is close to simulation values even though that n = 1000 is not large here. Fig. 7 shows the total average number of requests in the system for different policies under the uniform popularity distribution. As it can be seen in this figure, analytical results that we derived for FCFS in Equation ( 4) is very exact. Moreover, performance of FCFS is very close to that of Max-Weight. According to Fig. 7, for small loading factor ρ, uni-cast performance is very close to work-conserving multicast performance and it is much better than the blind multicast performance. For ρ close to 1, when the unicast becomes unstable, work-conserving multicast become substantially efficient compared to both unicast and blind multicast. For ρ 1, work-conserving multicast still outperforms blind multicast by a factor of 2 as it has been noted in Remark 6.
In this section, to illustrate the possibility of practical application of the proposed content multicasting schemes and to verify the validity of research conclusions, we aim to investigate the performance of our blind and workconserving multicast policies under non-uniform popularity distributions and compare their performance to a heuristic Max-Weight multicast policy.
To show the practicality of our analysis, we use an extensive set of real-world data, namely the data set of the BBC iPlayer [35], [36], [37], to obtain realistic video demand distributions. The BBC iPlayer is a video streaming service from BBC that provides video content for a number of BBC channels without charge. Content on the BBC iPlayer is available for up to 30 days depending on the policies. We consider the dataset covering June, 2014, which include 192,120,311 recorded access sessions, resulting in request rates λ = 74.1205 requests per second. The number of files according to the iPlayer database is larger than n = 10000. We consider multicast over 802.11 (Wi-Fi) wireless networks to stream video files. The 802.11 standard allows for multicast transmission as part of asynchronous services. According to [38], the popularity distribution of video files of the BBC iPlayer requested by the users in June 2014 can be approximated by the Zipf distributions with parameter γ = .86. Fig. 8 shows the average delay of the system for different policies in the month of June under the approximation of Zipf popularity distribution with parameter γ = 0.86. As it can be seen from the figure, the performance of FCFS is very close to Max-Weight and our analysis which we derived for FCFS in Theorem 2, under uniform popularity distribution, is also reasonable upper bound for more practical systems and under non-uniform popularity distributions like the Zipf distribution.
Fig. 9 shows the delay gain of FCFS multicast compared to blind multicast as a function of parameter of zipf distribution under different loading factors ρ. Under uniform popularity distribution with s = 0 given that ρ > 1, the gain is 2( ρ 2 ρ 2 -1 ) as it has been noted in Remark 6 which is large for ρ close to 1 and the gain decreases as ρ increases. When zipf parameter s increases, content popularity distribution will become more degenerate and blind multicasting will assign most the service to queue with largest arrival rate, resulting in same performance of FCFS multicasting. So we expect that gain will pick somewhere between and as it can be seen from figure, for loading factor ρ = 1, gain picks under Zipf distribution with parameter 1. Also, this Fig. 9: Blind/FCFS average delay ratio over Zipf parameter s and n = 1000. figure confirms that when ρ increases, the gain decreases which also agrees with the results of Remarks 6 and 7 that FCFS has the most advantage when ρ is close to 1 ans as ρ increases, the gain decreases. Note that, as we see in Fig. 7, unicast is a reasonable policy when ρ 1, but it becomes unstable for ρ ≥ 1, revealing the benefits of our proposed FCFS work-conserving policy.
In this section, we consider the transmission failures over the wireless channel as a practical issue and address the effect of multicasting error on delay gains to demonstrate that the reaped gains are still substantial even in the systems with high multicasting outage. In practical systems, it is not possible to multicast to all users at once and due to multicast error, some users may not receive the multicasting content properly. So, we need to send that content again until it is successfully received. We should note that in the presence of outage, we adjust the FCFS multicasting policy so that, if a multicast transmission fails to be received by a user, we treat that request as a new request. We call such a policy FCFS with outage. Fig. 10 shows the effect of channel failure on the delay performance of different policies for different loading factors ρ. For this figure, we assume n = 1000 and Zipf(1) popularity distribution. We can see from Fig 10(a) that, as the outage probability increases, unicast is the first policy to become unstable. Also, the proposed FCFS workconserving multicast always outperforms both unicast and blind multicast. For ρ ≥ 1, when unicast becomes unstable, Fig. 10(b) shows the effect of multicast outage probability on the average delays. As it can be seen from the figure, even in the presence of multicast error, both blind multicast and FCFS multicast with outage are stable in contrary to the unicast which is unstable for both ρ = 1 and ρ = 2. Also, the delay gains of FCFS multicast with outage compared to blind multicast is still substantial especially if ρ is close to 1. As the multicast outage probability approaches 1, the system becomes unstable independent of the multicast policy. We can conclude from this figure that under practical operational conditions with multicasting error and Zipf-like popularity distributions, the gain of FCFS work-conserving multicast is significant compared to other multicast policies like blind multicast. Recall that for large loading factors ρ ≥ 1, unicast is always unstable and is not a possible service policy.
In this work, we provided a comprehensive analysis of multicast gains for wireless content distribution networks serving a dynamic population of users that aim to access a content database with a given popularity distribution. In particular, we characterized the delay performance of two classes of multicasting strategies, namely, 'blind' multicasting whereby the pending requests are unknown to the transmitter, and 'work-conserving' multicasting whereby the pending requests are known. Our results establish that both types of multicasting yields endless stability, in that an unbounded traffic load can be supported by them by exploiting the multicast advantage of wireless communication. This is in contrast to the bounded stability of unicast mode of transmission whereby requests are fulfilled individually. Moreover, we show that work-conserving multicast based on a first-come-first-serve principle can yield further delay gains over its blind counterpart that are explicitly characterized in our analysis as a function of the traffic load and the database size. In addition to the explicit characterization of delay performance of these proposed multicast strategies, our work also revealed key insights on the conditions under which blind and work-conserving multicast solutions can yield most benefit.
Note that the number of users that generate demand is unbounded, as in the infinite-population setting of classical Aloha networks.
We note that the main results of this work will remain essentially the same if we use:Q U k (t + dt) = [Q U k (t) -B k (t) + A k (t + dt) -A k (t)] + .