ᚑくᄢቇℂᎿቇ⎇ⓥႎ๔
J. Fac. Sci. Tech., Seikei Univ.
Vol.46 No.2 (2009) pp.9-22

On Modeling Ubiquitous Cloud: Estimation of Traffic
Shuji KAWASAKI㧖1, Masakazu HIGUCHI㧖2, Jonah GAMBA㧖1, Hitomi MURAKAMI㧖3
ABSTRACT㧦The Ubiquitous Cloud is a concept of large-scale information service network as a social
infra-structure. It is featured by real-world context information extraction, user information profiling andself-configuration/-control of network. The objective of the research is to evaluate the network traffic
theoretically and thus give a guideline of network design. In this paper, we especially consider thosetraffic factors that are related to movement of mobile users and real-time services, and thus discuss somenecessary requirements for the network specification.
Keywords㧦context-awareness, profiling, self-reconfiguration, spatio-temporal dynamics, elephant-miceflow.
㧔Received September 24, 2009㧕䋱䋮㪠㫅㫋㫉㫆㪻㫌㪺㫋㫀㫆㫅㩷
vehiclesandITS(intelligent

transportsystem),economics and business, amenity and favor, etc. The

 The Ubiquitous Cloud (UC) is the framework of aubiquitous network concept that has been advocated since

context information of a user in the real-world is detectedof a prospective social infra-structure. The R&D of theserver called cloud, which is the brain and controller of theat any time by sensors deployed everywhere and sent to a2003 aiming at providing a theoretical and practical basis

network. The cloud then forms an appropriate service

concept is conducted in the Ubiquitous network control

information for the user according to the context orand administration (Ubila) project in Japan. The projectapplication and sends it to a nearby actuator to provide amembers are experts in the field from companies andreal-world service. We call a pair of sensor and actuator auniversities.

node.

UC is a information service network, as in Fig. 1, withTechnical elements close to user services level suppose

the following features:Autonomic extraction of various context information

context-awareness/-modeling and location- awareness.

appropriate service for a user

the first one, R&D has just begun and useful results has

These are new themes in the relevant field. Especially forfrom the real world and coordination of an

not obtained yet. In a physical or technological level, on

Keeping to provide a better service by user

theinformation profiling

other

hand,

supposeIPv6,

Heteroscedastic

multiplexing, Ad Hoc network, real-time scheduling, etc.

Self-reconfiguration of the network

For such large-scale infrastructure network UC, it is

The supposed contents of the context information include

important to assess its network traffic theoretically andthe matter of food, clothing and shelter, crime/disastergive a designing guideline. The objective of the research isprevention and rescue, medical/welfare/nursing services,

obtain the theoretical assessment. Especially we want to㧦Seikei University, Department of Information and Computer
Science, Visiting Researcher*2㧦Seikei University, Department of Information and Computer
Science, Postdoctoral Researcher*3㧦Seikei University, Department of Information and Computer
Science, professor㧔hi-murakami@st.seikei.ac.jp㧕
*1

know



㧙㧙

how much network capacity is necessary

how much spatial density of the nodes is necessary㪝㫀㪾㫌㫉㪼㩷㪈㪑㩷㪬㪹㫀㫈㫌㫀㫋㫆㫌㫊㩷㪚㫃㫆㫌㪻㩷㪠㫄㪸㪾㪼㩷
how long the response time from sensing to actuation

mobility formulation. Section 4 then considers theHere an actuation implies not only the service withfor how to formulate the traffic and what the distinction of

fundamental features that the UC should possess to seek

how quality of information is evaluatedUC from classical queueing theory. In Section 5 we briefly

physical operation but giving users requested information.

discuss network response time.

Among the context fields mentioned above, it may beconsidered that disaster rescue, medical service, care for䋲䋮㪩㪼㪺㪼㫅㫋㩷㪧㫉㫆㪾㫉㪼㫊㫊㩷㫀㫅㩷㪥㪼㫋㫎㫆㫉㫂㩷㪫㫉㪸㪽㪽㫀㪺㩷㪪㫋㫌㪻㫐㩷

they often need real-time response. In recent years, on the Since 1990s, a large number of research on the network

developed so as to utilize mobile terminals as PDA. Thus acharacteristics specific to protocols (TCP/IP, HTTP, FTP,

handicapped persons, etc. are of pubic importance andother hand, a lot of applications in these fields aretraffic has been done. Their points of view areconsideration of mobile users in UC may be a problem ofetc.), network form (WAN, LAN, etc.) and applicationhigh priority. Therefore, in this paper, we focus our(WWW, P2P, etc.). It is pointed out commonly that theattention to mobile applications that requires real-timetraffic has the following characteristics:

response to clarify problems raised in the assessment.

The organization of the paper is as follows. In section 2,

we survey known results so far and pick up concepts that

we will follow. Section 3 is the preliminary consideration
for UC traffic modeling, containing some remarks in user㧙㧙

failure of arrival process models by simple Poissonprocesses㪝㫀㪾㫌㫉㪼㩷㪉㪑㩷㪙㪸㫊㫀㪺㩷㪤㫆㫍㪼㫄㪼㫅㫋㩷㪤㫆㪻㪼㫃㩷㫆㪽㩷㪸㩷㪤㫆㪹㫀㫃㪼㩷㪬㫊㪼㫉㩷㩷

failure of traffic models by Markov processes

following point of view:elephant flowself-similarity/long-range dependence; burstiness

Moreover, in aggregation of a lot of user traffics, several

authors reports that the aggregated traffic does not presentGaussianity, according to measurements of real traffic.
Conventionally it is considered that the Gaussianity holds

sessions of mobile users
applications

that

involves

location-awareness–disaster information, ITS, events, etc.

consideration of spatial hop processes in Ad Hocconnection

based on the assumption that a central limit theorem holds.

㧟㧚㪧㫉㪼㫃㫀㫄㫀㫅㪸㫉㫐㩷㪚㫆㫅㫊㫀㪻㪼㫉㪸㫋㫀㫆㫅㫊㪑㩷㪤㫆㪻㪼㫃㫀㫅㪾㩷㪤㫆㪹㫀㫃㪼㩷㪬㫊㪼㫉㫊

imply that we should consider rather a non-central limit Let us consider the movement model as in Fig. 2. It

dependent processes.

accessing a nearby node and finishes at a random time t =However, the aggregated traffic being non-Gaussian may

theorem, which is sometimes the case for long-range

presents that a mobile user starts a session at t=t0

As for the burstiness, Lowen and Teich discusses thetN. The user sends a context information at t = tn with rate

generation mechanism [19]. They give two such models

φn[MB/s] and receives in response a service information

called Bartlett-Lewis process and Neman-Scott process. In

real-time with rate ψn[MB/s] for n = 1, … ,N. It may bethis study, we will consider our model regarding theseconvenient to consider Φn = max(φn, ψn) sincecharacteristics as well.

The original point of our model is that it is aiming at

modeling of spatio-temporal dynamics of the network. In

the conventional traffic model based on queueing theory,user traffics accessing to finite servers are aggregated; here
the interest is in the system behaviors with respect to time

sometimes the capacity of send and receive nodes areeven though the capacities are different, one canmade the same

estimate a necessary capacity by a larger one.

For the sake of simplicity, we take a uniform

as stochastic processes. Unfortunately the behaviors withnonrandom sampling rate along time, so that tn+1 −tn =τ [s].

respect to spatial variables are not involved. Our researchThis τ may be either greater or smaller than 1, according toconsiders the spatial behaviors as well as time from theapplications. For example, in a real-time critical system㧙㧙Now, in order to study the relationship between thelike a vehicle, that involves a faster movement than a man,τ should be smaller than 1. In a system that considers

spatial density of nodes and user velocities, we may

1.

considerhuman movements, on the other hand, τ can be larger thanFor the first connection in a session, we assume that theconnection itself obeys Poisson distribution. It is theaggregated traffic that does not obey the Poisson

distribution, and we should note that the connection itself

In case that a session lasts over several nodes, we willnode at the center of the circle. We sometimes identify thethink of its flow-out of a node’s cover area El,nңDl at (tn ,position of user and the node for the sake of easy.

xn) and flow-in to another node’s cover area El’,n’ңDl’ at(tn+1 , xn+1). This l’ can be the same as l. In this respect, we

It may be considered that there are a lot of mobile users

may consider the following two ways:

like this. Let us denote the whole network region D ң R

2and let D be covered by subregions Dl: D =ыl Dl. Hereboth setting of Dl being disjoint or joint may be possible.
new sessions start with the ratio λl [person/sxm ]existing session terminate with the ratio µl [person/s

flow-in/-out ratio for each subregion Dl reflects the local

The flow-in ratio and flow-out ratio are taken

separately with the session-start within El,n andsimilarly, the session-end ratio within El,n andcharacteristics (Fig4).

flow-out ratio may be denoted as µl|El,n|/|Dl| andµ l |El,n|/|Dl|, respectively.

In considering the sptio-temporal model as above, it

may be useful to formulate the user movements based on

In the first way, the model description is simple apparently

stochastic arguments like

distribution of amount of data the users send/receiveµl|El,n|/|Dl|, respectively.

ratio within El,n and flow-in ratio may be denoted as
λl|El,n|/|Dl| and λl |El,n|/|Dl| respectively, andqueueing theory, the one may take λl < µl. This

ends of sessions in El,n. The session-start ratio in El,nsession-end within El,n. In this case, the session-start

xm2](see Fig 3). If one wants to follow the stability argument inA flow-in or flow-out are involved in the starts andis then taken as λl|El,n|/|Dl| and session-end ratio as

2

distribution of user velocities

where Vn is the velocity along the line and θn theAlso, each node has its own cover area.

in a corresponding disc which is the covered-area by thetaking a 2-dimensional time series Mn =(Vn , θn),may evaluate its N-dimensional distribution.

Fig. 2 presents that at each t = tn, user position is located

considering it is a Markov process

vertical axis; assuming Mn is a Markov process, we

process [19].



tn and evaluate their N-dimensional distribution,

angle of the moving direction and horizontal or

can be modeled as Poisson arrivals like BL process or NS

In this case, let us assume that in each Dl,taking a time series Xn representing the position at t =since the difficulty of modeling the flow-in/-out is hidden

away. But the model is the same as the one in which there

distribution of inter-user distances

are no movements between {En,l}. We thus employ thelatter.

at each instance or position.

Here it should be noted, however, that if one increases㧚 %QPIGUVKQPKPCUKPINGWUGTUGUUKQPthe random variables in the argument easily then the user Let us denote the node that a user u0 accesses at t by s(t).

movement model could be too complicated to tract

If the u0 send/receive φ [MB] and if s(tn) ≠ s(tn+1), then thetheoretically. We do not hope that but a framework thatamount of data sent/received at s(tn) and s(tn+1) are both φ/τdoes is based on theoretical analysis. In order for that it is[MB/s], as long as the session is alive, i.e. φ/τ ≥ ρ for thenecessary to construct the movement model in a clevernode’s capacity ρ [MB/s].

way. It is recognized that the description of user’s spatial
attribution is an important problem [23].

㧙㧙㪝㫀㪾㫌㫉㪼㩷㪊䋺㩷 㪘㫉㪼㪸㩷㪻㫀㫍㫀㫊㫀㫆㫅㩷㪸㪺㪺㫆㫉㪻㫀㫅㪾㩷㫋㫆㩷㪺㫆㫍㪼㫉㪸㪾㪼㩷㫆㪽㩷㪺㪼㫃㫃㫌㫃㪸㫉㩷㪹㪸㫊㪼㩷㫊㫋㪸㫋㫀㫆㫅㫊㩷㫆㫉㩷㫊㫋㪸㫋㫀㫊㫋㫀㪺㪸㫃㩷㪺㪿㪸㫉㪸㪺㫋㪼㫉㫀㫊㫋㫀㪺㫊㩷
Next, if s(tn) = s(tn+1), the amount of data sent/received㧚 %QPIGUVKQPKP5GXGTCN7UGTU

[MB]. This can be generalized as follows. We assume that

For this, it is immediately understood that the following

during the two time slots, i.e. [tn, tn+2) is min(2τρ , φ)

 A node may be used by several users simultaneously.

the positions of nodes and users are the same, for the sakerequirements should be satisfied. Let us suppose that auser u0 sends a context information of size φ [MB] from aof simplicity. Let the radius of cover area of a node be ζ[m]. If the u0 get out of the area at n = N* th step and get

node at t = t0 and let another user u = u1 sends the same

into another area, then the N* is given by2  N
N * = min  N τ ∑ vn cos θ n   n=0+ τ ∑ vn sin θ n  ≥ ς 2 .

 n =0
2Ndata at t = t1 from the same node, moving the same

direction as u0. Let the distance of the users be r [m] andvelocities are the same with v [m/s]. Thenrt1 = t0 + .
v(1)

If the capacity of the node is ρ [MB/s], then the timenecessary to send or receive the data is φ/ρ [s]. Hence, if

In this case, for k1, k2 with 0 ≤ k1 < k2 ≤ N*, a requirement

r ϕ
≥ ,
v ρ

may be such that the maximum of amount of data does notexceed the node’s capacity in some sense. A primitive
form of it may be

k2
1
max
ϕi ≤ C ;∑0≤k1 <k2 ≤ N * ( k − k )τi = k12
1


1P  max *Φ i ≤ C  ≥ 1 − δ∑ 0≤k1<k2 ≤ N (k 2−k1 )τ i=k1

(5)

the congestion at the node does not occur. From this itself,

one might take the capacity satisfying ρ ≥ vφ/r. Actually v,(2)r, φ are, however, random variables and we may consider
requirements such asR ΦP  ≥  ≥ 1 − δ ,V ρ 

Or, a probabilistic form may be as
k2

(4)

(3)

(6)

where R, V and Φ are random variables corresponding to r,
v and φ respectively. For some applications or positions

for certain prescribed small δ, 0 < δ < 1. Here N* and Φiare random variables.

these random variables may be set constants.

㧙㧙㪝㫀㪾㫌㫉㪼㩷㪋䋺㩷 㪝㫃㫆㫎㪄㫀㫅㪆㪄㫆㫌㫋㩷㫆㪽㩷㫊㪼㫊㫊㫀㫆㫅㫊㩷arrival for each connection, exponential service time, c

For example, instead of Φ itself, the upper bound Φ* may
be used, so that random variables in (6) are only R and V .

service stations and no waiting rooms. It is a lossy system

El,n simultaneously, it is sufficient for the connection not tobeing served in each station then the new customer cannot

r ϕ + L + ϕν
min i ≥ 0,
1≤i ≤ν v
ρi(7)

stations as capacity of the node. Thus the capacity of thei.e. ρ ≥ Σνi=0 φi /[min1≤i≤νri /vi]; In a slightly more general

the same rate s [MB/s], so that ξ = c/s users can connect tothe capacity b [MB]. Then the requirement, stated in theusers are connecting sessions in El,n is given by [12,In a more general case where users u1, … , uν appear in an

since a customer arriving when c customers are alreadyenter the system.

overflow is that

In our model, we can think of the number c of service

node is c [MB/s] and each user send data to the node with

the node simultaneously. Then, the probability Pν that νargument the node may have a buffer, which we assume
probabilistic form, is expressed as

[

]


R
∑i=1 Φ i − b  ≥ 1 − δ .
P  min i ≥ 1≤i≤ν Vi

ρ


ν

Section 3.7]

ρv
P0 , ν ∈ N 0 ,ν!

(9)λl | El ,n | / | Dl | λl=
µl | El ,n | / | Dl | µl

(10)

Pν =

(8)
with

If we consider in each El,n only those sessions that start

within it and assumes the amount of data sent by each user

ρ=is the same, then we can apply directly an argument ofqueueing theory to evaluate the loss probability at the node.
The argument, called M/M/c/c system, assumes Poisson

㧙㧙

and

 ξ ρν 
P0 = ∑  ,ν =0 ν ! 
−1

(11)

㧚 #-PQYP4GUWNVKP,CEMUQP̉U0GVYQTMU In this subsection, we survey briefly the known result,respectively. Also, the loss probability that a new user

called Jackson’s theorem, and indicate differences frombyappropriate starting point for us and we have to seek for an

our problem. Then the Jackson’s theorem will be antrying to connect when there are ξ users already is given

Pξ =

∑

ρ ξ / ξ!

ξρ ν /ν !
ν =0.

extension beyond it.

(12)

The setting of Jackson’s theorem is as follows [12]. We

consider a network of nodes, each of which is a service

These expressions are called Erlang’s B formula.

facility and each with storage room for queues. Customers

Here it is important to recognize that we are implicitly

assuming the number of users try to start a connection

enter the system at various points, queue for service anda more realistic model, we have to take into account that

other nodes to receive there additional service.

upon departure from one of the nodes proceed to one of

newly within a time slot of length τ is one. For the sake of

The network consists of N nodes where the i-th node

several users may start connection within a time slot.

consists of mi exponential servers each with parameter µi.

㧠㧚㪫㫆㫎㪸㫉㪻㫊㩷㫋㪿㪼㩷㪤㫆㪻㪼㫃㫀㫅㪾㩷㪸㫅㪻㩷㪜㫊㫋㫀㫄㪸㫋㫀㫆㫅㩷㫆㪽㩷㪬㪚㩷

Further, the i-th node receives arrivals from outside theIn this section, we consider special features of the UC

then it is just an M/M/m system. Upon leaving the i-th

system in the form of a Poisson process at rate γi. If N = 1,

traffic model distinct from classical queuing theory. Suchnode a customer proceeds to the j-th node with probabilityspatio-temporal birth-death processes or its variants

probability that the customer departs from the network ismultiple

In order to indicate the arrival from outside and theri,j. After completing service in the i-th node thefeatures may includerather than temporal birth-death processes
occurrence[1][2],

corresponding

given by 1 –ΣNj=1 ri,j.

tomulti-user connection, in a temporal point process

departure to outside of the network, we designate states 0

rather than single occurrence

and N + 1. Thus, r0,i is the probability that next externallyand not for the number of connecting users.

ri,N+1 is the probability that a customer leaving i-th nodeof the temporal point processes. Especially, thenext arrival require no service and leave immediately upon

points, they approximate to self-similar and LRD

node i be µki when the there are ki customers at the node.

the traffic process is for the amount of user traffic,

generated arrival will enter the network at node i, while

induction of clusters [1][2] by each user in each point

departs from the network. r0,N+1 is the probability that theclusters are such that, aggregated over the users andarrival. In addition, let the exponential serveice rate attraffic process. In this sense, the distribution over

Below, we will calculate the total average arrival rate ofuser traffic sizes, that represents well the traffic

customers to a given node. Let λi be the total averagecomponents from mice to elephants, may be involvedarrival rate to i-th node. Then,in the traffic modeling.

λi = γ i + ∑ λi r j ,i ,N

description of user mobility by a spatio-temporal

j =1

Markov process. By the spatial Markovian property,
we may think of the Gibbs process [1], which is such(13)

for i = 1, … , N. Let k = (k1, … , kN) be number ofthat given the position of a user in certain boundary

customers in each of the nodes. Thus k is the state of theof the past.

customers in the network. Let Pk(t) be the time-dependent

region of Dls, his movement afterward is independent

network. Then, S(k) =ΣNi=1ki denotes the total number ofstate probabilities,

Since our motivation has become clear as above, it is

helpful to see a known result that may be a basis to ourPk (t ) = P(state vector at time t is k ).

problem, which we do in the following subsection.

㧙㧙

(14)

As in the usual formulation method of queues, we canwithwrite the differential equation governing the state
probability asN
dPk (t )= − γ ( S (k )) + ∑ µ ki (1 − rii ) Pk (t )
dt
i =1



+ ∑ γ ( S (k ) − 1)r0,i Pk ( i − ) (t )+ ∑ µ ki +1ri , N +1 Pk ( i + ) (t )N

∑ f (k ).

k:S ( k )= K

(20)㧚 㪛㪼㫇㪸㫉㫋㫌㫉㪼㩷 㪽㫉㫆㫄㩷 㫋㪿㪼㩷 㪽㫆㫉㫄㫌㫃㪸㫋㫀㫆㫅㩷 㪹㪸㫊㪼㪻㩷 㫆㫅㩷 㪡㪸㪺㫂㫊㫆㫅㵭㫊㩷

N

i =1

H (K ) =㪥㪼㫋㫎㫆㫉㫂 Though the Jackson’s theorem stated above applies insome parts of our setting, it does not in several other points.

(15)

The applicable point is the network topology. The
differences are in the following points:

i =1+ ∑ µ ki +1rj ,i Pk (i , j ) (t ),Ni , j =1i≠ j

The Jackson’s network considers the increase or

decrease of number of customers (network data size)
only by 1 at a time, while we would like the increaseor decrease by general integers. This may call for thewhere k(i−) equals k except for its i-th component with thei-th component is ki − 1 and k(i+) equals k except for its

i-th component with the i-th component is ki + 1. Also, k(i,j) = k except that its i-th and j-th components are ki − 1

multiple occurrence [1][2] in Poisson arrivals.

The Jackson’s network do not consider the spatial

dynamics of state probability but only temporal,

while we would like to consider the data size flow inand kj + 1, respectively. Here the first term of the righthand side is the probability component corresponding to

the case that the state S(k) is unchanged due to thecomplete balance of arrival from and departure to outside.

a spatio-temporal point dynamics.

We would like to model certain cluster processes
cause by the Poisson arrival as well, in order todescribe the self-similarity or LRD.

The second term corresponds to the case that state gets

Below we consider a traffic model of UC that takes into

increased from S(k) − 1 to S(k), by external arrivals. The

account the first three features of the above, to seek for thethird term corresponds to the case that state gets decreased

formulation of traffic model.

from S(k)+1 to S(k), by departure to outside. The fourthterm is the case corresponding to the case that the state

For the l-th region, let the aggregated user traffic process

S(k) is unchanged due to just internal emigration-

For equilibrium of t→∞, the differential equation can bebe X(l)(t), t ≥ 0. By pn(l)(t), we denote P(X(l)(t) = n) forn ∈ N0 .

1
f (k ) F ( S (k )),Gformulate the pn(l)(t). Before that, however, we should

immigration.

solved for limt→∞ Pk(t) = pk to be

pk =
where

F ( K ) = ∏ γ ( S (k )),K −1

S ( k ) =0

ei
i =1 ji =1 µ ji

f (k ) = ∏∏K −1 kiandFirst, we would like to describe a differential equation to(16)

remark that it will be a better approach to take the state

space of the amount of user traffic X(l)(t) rather than the(17)

number of connected users as is traditional in classicalqueueing theory.

The reason for this, besides that basically we would(18)

 ∞ F ( K ) H ( K ) if the sum converges
G = ∑K =0
∞otherwise,
(19)

㧙㧙

㪝㫀㪾㫌㫉㪼㩷㪌㪑㩷㪬㫊㪼㫉㩷㫋㫉㪸㪽㪽㫀㪺㫊㩷㪸㪾㪾㫉㪼㪾㪸㫋㫀㫆㫅㩷㪸㫋㩷㫋㩷㪔㩷㫋㪇㩷㫆㫍㪼㫉㩷㫍㪸㫉㫀㫆㫌㫊㩷㫍㪸㫃㫌㪼㫊㩷㫆㪽㩷㱢㩷like to estimate the amount of the traffic at a time instant tof φ stated above nor by considering the number ofconnected users as the vertical axis. Presence of the eachor as t → ∞, is as follows.

traffic size class along time axis is depicted in Figure 5.

Therefore, we will consider the differential equation of pn(l)Consider the distribution of amount of user traffics φ ≥ 0[MB/s]. Then each of the traffics runs over horizontal time(t), not of number of users but the amount of aggregateduser traffic. Now let λν and µν , ν =∈ N 0 be input andaxis, as an on-off source [13][26], with φ the vertical axis.

Thus φ may be considered to take nonnegative integer

output rate, respectively. Then, along with the birth-death

It may as well be written with φ real-valued for the sakemultiple occurrence of points [1], we may write

values.

state transition in classical queueing theory but withpn( l ) (t + h) = pn (t )1 − ∑ λν(l ) + µν(l ) h  ν ∈N

(of theoretical formulation. In such cases, one may wants todivide the vertical axis with a finite number of partition sothat the one can apply a traditional birth-death processes in+ ∑ pn(l−)ν (t + h)λν( l ) h)nqueueing theory in every partitioned classes, with input

and output rates depending on the classes. This is awkward,

ν =1+ ∑ pn(l+)ν (t + h) µν( l ) h + o(h),however, since the distribution of user traffics consists ofν ∈N 0“so many mice and rare elephants” [15][25]. Here the micemean those users that cause small amount of traffics, while

where

the elephants those that cause extraordinarily large amountof traffics. The distribution of the user traffic thus varyover φ. This may be written well neither by the partitions

㧙㧙

(21)

λν( l ) = ςν( l ) + ∑ην( i ,l ) ,i ≠lµν( l ) = γ ν( l ) + ∑ην( l ,i ) , N (t )Gν (t , x) = P ∑ Wν ,k Iν ,k ≤ x 
 k =1∗k= ∑ pν ,k (t ) Fν ,k ( x).

(22)

i ≠l

k∈N 0

with ζν(l) and γν(l) the birth and death rates in the l-thregion,

while ην(i,l) and ην(l,i) the “immigration” rate from i-th to l-th

Asymptotically as t → ∞, this can be calculated further

region and “emigration” rate from l-th to i-th region,

using a tool of renewal equations [8].

respectively. Here the “immigration” and “emigration” arefor the amount of user traffic and not for the number of㧚 㪘㩷㪩㪼㫄㪸㫉㫂㩷㫆㫅㩷㪧㫆㫀㫊㫊㫆㫅㩷㪘㫉㫉㫀㫍㪸㫃㫊㩷㪸㫅㪻㩷㪬㫅㫀㪽㫆㫉㫄㩷 㩷connected users.

㪛㫀㫊㫋㫉㫀㪹㫌㫋㫀㫆㫅㩷㫆㫅㩷㪲㪇㪃㩷㫋㪴

Then (21) yields(

dPn (t )= − pn (t ) ∑ λν(l ) + µν( l )
dt
ν ∈N
+∑ p
n

ν =1

(27)

(l )
n −ν

)

(t + h)λ + ∑ p(l )ν In Fig. 5, let us first fix a single data class. For this dataν ∈N 0class, let each duration of connection be Yk [sec], k = 1, 2,… and Wk [sec] be time instants of beginning of the

(l )
n +ν

duration. These Yk and Wk are of course random variables.

(t + h) µ .
(l )νDenote the amount of data at time t of the class by Φ(t)(23)

represents where the value of Wk falls in the interval [0, t]

and a uniformly distributed random variable thatby Uk. Then, according to [24, Section V.4], theSolving the equation explicitly may be difficult. Certain

another way of characterizing the solution pn(t) will be

distribution of Φ(t) is given bydesired.

Pr (Φ(t ) = k ) =On the other hand, we can write the distribution of

aggregated on-off process as follows. Let Iν,k be the k-th

occurrence of the busy period of process for φ = ν and Xν
the random sum of Iν,k by random upper bound Nν (t ) ∈ N 0 .
Thus we may writeX ν (t ) = ∑ Wν ,k Iν ,k ,Nν ( t )
k =1

(24)

with the amount load Wν,k for k-th occurrence for each ν.
Then, X(t) = Σν Xν(t) represents the amount of aggregatedtraffic. Assuming independence of Xν(t) over ν, we have( pλt ) k − pλt
e ,
k!

(28)

for k = 0, 1,… , with

p = Pr (U k + Yk ≥ t )1 t
Pr (Yk ≥ t − u ) dut ∫01 t
= ∫ [1 − G (t − u )] dut 0
1 t[1 − G (u )] du,t ∫0=

where G(u) = Pr(Yk ≤ u).


P ( X (t ) ≤ x) = P ∑ X ν (t ) ≤ x  = G1 ∗ G2 ∗ L ,νsimultaneously and aggregate them to obtain the(25)

i = 1,… ,N. Let Hi(t, x) =Pr(Φi(t) = k). If we assume theNext, let us consider data classes Φi(t), i =1, 2, …

evaluation of P(ΣiΦi(t) = k). Accordingly, we take pi, λi forwhere Gν is the distribution function of Xν(t): Gν(t, x) =independence of Φi(t), i = 1,… ,N, thenP  ∑ Φ i (t ) = k  = (H1 (t ,⋅) ∗ L ∗ H K (t ,⋅) )(k ) i
( p1λ1t ) k1 − p1λ1t( p λ t ) k N − p N λN t
,
e
e
= ∑
×K× N NkN !
k1!
k1 +L+ k N = k

P(Xν(t) ≤ x). Let {pν,k(t)} = P(Nν(t) = k),Σk pν,k(t) = 1 andFν*k(x) the k-th convolution of the distribution Fν(x) that t

is in some Iν,k:Fν ( x) = P t ∈ ∑ Iν ,k .
 k∈N0 (26)

where the last sum is taken over all possible combinationsof (k1, … , kN) such that k1 + · · · + kN = k.

Then, we have㧙㧙Here recall that Φi(t) = riMi(t) with ri and Mi the constant

MAC, it is necessary to define the packet length and the

In order to relate the amount of data Σi Φi(t) withassumed to be a random process and queueing theory isnature of arrival statistics. Packet arrival is normallydata size of the class random number of connections at t.

used to define the network. We note that, in multi-hop

distribution of data classes from the elephant flow to mice

networks, it may be necessary to separate the end-to-end

flow, what kind of formulation is to be considered?

delay into processing delay, propagation delay and MAC
delay [36]. The processing delay accounts for processing

For example, two different data classes Φi1(t) and Φi2(t)of the packets in the transmit and receive circuits, thecan be the same by ri1Mi1(t) = ri2Mi2(t), even though one

propagation delay is function of distance between nodes,

corresponds to elephant flow and the other mice. We

while the MAC delay is affected by the accessibility of theshould make the formulation such that the difference of themedium and interference from neighboring transmissions.

data classes are distinctly described.

Also, we may consider, for example, a weighted versionof the above argument in which the sum is taken over all㧚 㪮㪿㪸㫋㩷㫀㫊㩷㫋㪿㪼㩷㫀㫄㫇㫆㫉㫋㪸㫅㪺㪼㩷㫆㪽㩷㫅㪼㫋㫎㫆㫉㫂㩷㫉㪼㫊㫇㫆㫅㫊㪼㩷㫋㫀㫄㪼㪖㩷

instead of k1 +· · ·+kN = k.

network response time. Basically the network response䋵䋮㪥㪼㫋㫎㫆㫉㫂㩷㪩㪼㫊㫇㫆㫅㫊㪼㩷㪫㫀㫄㪼㩷㪸㫅㪻㩷㪠㫋㫊㩷㪤㪼㪸㫊㫌㫉㪼㫄㪼㫅㫋㩷

network. The shorter the response time, the better the

The answer can vary according to one’s perception of(M1(t), … ,MN(t)) such that r1M1(t)+· · ·+rNMN(t) = k,time gives a measure of the quality of service (QoS) of the
network performance. Network response time also affects㧚 㪮㪿㪸㫋㩷㫀㫊㩷㫅㪼㫋㫎㫆㫉㫂㩷㫉㪼㫊㫇㫆㫅㫊㪼㩷㫋㫀㫄㪼㪖㩷the power-saving ability of network terminals such as

networks. It is generally defined as the time between

ubiquitous environments where mobile terminals operate

mobile phones, PDA’s etc. This can be very important in

The network response time has its origin in computeron limited power supplies. The longer the network

message generation at the sending station and its reception

response time, the greater the power consumption of theat the destination station. Since the networks response time

devices. In fact, this power-saving ability extends tois affected by buffering inside the network, great care has

mobile base stations as well. Therefore, it is desirable toto be taken when it used to evaluate local area network

obtain the best network response time in order to improve(LAN) technology. One example of this is when one

the QoS and minimize power consumption.

considers the situation in which the buffers fill up due tocongestion. In this case the network response time

becomes a function of buffer length and is not affected by
the underlying LAN technology.

㧚 㪮㪿㪸㫋㩷㪽㪸㪺㫋㫆㫉㫊㩷㪺㫆㫅㫋㫉㫀㪹㫌㫋㪼㩷㫋㫆㩷㫋㪿㪼㩷㪹㪼㫊㫋㩷㫉㪼㫊㫇㫆㫅㫊㪼㩷㫋㫀㫄㪼㪖㩷measured by packet delay which depends on MAC delay.

In practice, the network response time is normallya good measure of network performance. The higher the

The MAC delay of a station in a LAN is defined as thethroughput, the better the network performance. However,increase the network throughput may have adverse effects

In network analysis, throughput is normally considered as

on packet delay. There is generally a tradeoff between

time between the instant at which a packet comes to thepacket delay and throughput [32]-[34]. Strategies forhead of the station transmission queue and the end of thethroughput improvement such as packet aggregation [35],packet transmission. For this reason, the MAC delay is[37] have a tendency to an increase packet delay, reducing

considered the best measure for network response

the suitability of the network for media services. In this[27]-[29]. In this paper, we will use packet delay ascase, some counter-measures such as increasing media

measure of network response time because it becomes

capacity can be taken although this may lead increased

easier to understand the theoretical concepts. The packet

power consumption.

delay is defined as the time taken by a packet to reach its

The packet delay at MAC level is affected bydestination node after it is generated [30]. The packet
delay is a statistical quantity that depends on the packet

transmission power. Experimental results have shown that

performance of standard protocols such as IEEE 802.11

gives lower packet delay, while under low load a higher

for high traffic load in the network, a lower power levelsize and network topology. In order to assess the㧙㧙power gives lower delay [36].

formulation of the optimal design for a given requirement

packet delay. A number of algorithms have been proposed

enjoys central limit theorem or not.

and whether the limit for large number of aggregation

The network model and routing algorithm also affect the

Towards the UC traffic model formulation, we canto optimize packet delay while maintaining highthroughput. Examples include Minimum Expected Delayconsider several point of view in order to make the model(DRAs) [39].

point of view may be those listed in the beginning ofdistinct from classical queueing theory. Examples of such

Algorithm [38] and Distributed Routing Algorithms

Section 4. Some of the points are complicated version of㧚 㪟㫆㫎㩷㫋㫆㩷㫄㪼㪸㫊㫌㫉㪼㩷㫆㫉㩷㪺㪸㫃㪺㫌㫃㪸㫋㪼㩷㫀㫋㪖㩷

basic and classical concepts. Among them, formulation

multihop wireless network can be written as [30]interdisciplinary interests: the connection of SS and LRD

along the last two points may have challenging

For a random access MAC model the packet delay in a

ρi
D ( n) =,λ (1 − ρˆ )property with spatio-temporal process, and statistical(29)

mechanics. We would like to explore the formulation
along these directions more.

Finally, it will be necessary to perform a verification ofwhere ρi is the utilization factor of a given node i, λ isarrival rate and ρ is the average utilization of all nodes.

the model through a simulation. For this, one may consider

Rayleigh fading channel the average packet delay can be

auto-maton. As the cell auto-maton is sometimes used for

simulating

Assuming packet collision under the Markovian Model forLc,
λe ffπ 1

spatio-temporal

dynamics

bycell

a microscopic behavior simulation to obtain a macroscopic

found as follows [40]:

Dav =

the

description of the model, we would like to have an(30)

equation, like partial differential equation, that describes
the spatio-temporal dynamics.

where λeff is the effective arrival rate, π1 is the probability

that the received power exceed the threshold value and Lc

㪘㪺㫂㫅㫆㫎㫃㪼㪻㪾㪼㫄㪼㫅㫋㫊㩷processing rate. Other expressions for the measurement of

A part of this work was supported by MEXT

is a constant that depends on queue length and packet

Grant-in-Aid

packet delay (packet arrival rate) can be found in [31].

Infrastructures.

for

Building

Strategic

Research㧢㧚㪚㫆㫅㪺㫃㫌㪻㫀㫅㪾㩷㪩㪼㫄㪸㫉㫂㫊㪩㪼㪽㪼㫉㪼㫅㪺㪼㫊㩷In traffic modeling of UC, we have extracted several

problems in spatio-temporal modeling of mobile users and[1] D. R. COX AND V. ISHAM, Point Processes,

receiving service information. We take into account some[2] D. J. DALEY AND D. VERE-JONES, An Introduction

While the conventional queueing theoretic models are[3] M. K. DENKO, Mobility Prediction Schemes inwould like to construct a spatio-temporal model for UC,

Wireless Networks, ed. T. A. Wysocki et al., Springer,

real-time requirement of sending context information andChapman & Hall, 1980.

characteristics pointed out by several authors after 1990s.

to the Theory of Point Processes, Springer, 1998.

mainly interested in temporal behavior of the system, we

Wireless Ad Hoc Networks, in Advanced Wired andand thus to give a guideline of network design.

2005.

The mobile user model in this paper will be a basic[4] M. FRANCESCHETTI AND R. MEESTER, Random

concept of the spatio-temporal model. The behavior could

Networks for Communication, Cambridge Univ. Press,

be somewhat complicated, but it is due to the2007.

spatio-temporal dimension. We are to consider several[5] G. B. FOLLAND, Introduction to Partial Differential

connected to the self-similarity of the aggregated traffic,[6] R. A. Holley and D. W. Stroock, Nearest neighbortheoretical problems such as how the movement model is

Equations, Princeton Univ. Press, 1995.

㧙㧙Telecommunications and Informatics, 88-94, 2009.

birth and death processes on the real line, Acta[22] S. Rugova and A. Maraj, Traffic Load and Cost

Mathematica, 140, 103-154, 1978.

[7] T. M. Liggett, The stochastic evolution of infinite

Analysis

systems of interacting particles, Lecture Notes inforDifferent

IPTV

Architectures,

Proceedings of the 8th WSEAS International

Mathematics, 598, 187-248, 1977.

Conference on Telecommunications and Informatics,
163-168, 2009.

[8] S. KARLIN, A First Course in Stochastic Processes,
Academic Press, 1975.

[9] S. Kawasaki, M. Higuchi, K. Hirano and H. murakami,
A Study on Traffic Modeling in Ubiquitous Cloud,Proceedings of the 8th WSEAS International[23] Y. Takahashi, Application of Queueing Theory to
Mobile Communication Systems (in Japanese), Trans.
Japan OR Society, 45, 11-20, 2001.

[24] H. M. TAYLOR AND S. KARLIN, An Introduction

Conference on Telecommunications and Informatics,

to Stochastic Modeling, 3rd ed., Academic Press,

187-193, 2009.

1998.

[10] F. P. KELLY, Reversibility and Stochastic Networks,[25] W. Willinger and V. Paxon, Where Mathematics Meets

JOhn Wiley & Sons, 1979.

the Internet, Notices of the AMS, 961-970, 1998.

[11] J. F. C. KINGMAN, Poisson Processes, Oxford Univ.

[26] W. Whitt, Stochastic Process Limits, Springer, 2002.

[27] M. Conti, Body, personal, and local ad hoc wirelessPress, 1993.

networks, The Handbook of Ad Hoc Wireless[12] L. KLEINROCK, Queueing Systems, vol.I: Theory,

Networks, Editors: Mohammad Ilyas and Richard C.

John Wiley & Sons, 1975.

Dorf p.1-5 – 1-22, 2003.

[13] M. MANDJES, Large Deviations for Gaussian[28] M. Conti, E. Gregori, and L. Lenzini, Metropolitan

Queues: Modeling Communication Networks, Wiley,

Area Networks, Springer Limited Series on Telecom

2007.

Networks and Computer Systems, Nov. 1997.

[14] T. MORI, M. UCHIDA AND S. GOTO, Flow[29] M. Conti and S. Giordano, special issue on “Mobile

Analysis of Internet Traffic: World Wide Web versus

Ad Hoc Networking,” Clustering Computing Journal,

Peer-to-Peer, VOL.36, NO.11, Syst. Comp. Japan,

5(2), April 2002.

70-81, 2005.

[15] T. Mori, R. Kawahara, S. Naito and S. Goto, On the[30] N. Bisnik and A. Abouzeid, Queuing Network Models

and Elephants, Proc. IEEE/IPSJ Symp. Appl. Internet

Networks, IWCMC’06, July 3-6, 2006, Vancouver,for Delay Analysis of Multihop Wireless Ad HocCharacteristics of Internet Traffic Variability: Spikes

British Columbia, Canada.

(SAINT2004), 99-106, Tokyo, 2004.

[16] S. V. LOWEN, M. C. TEICH, Fractal-Based Point[31] F. Gebali, Analysis of computer and Communication[17] H. Murakami, The Role of a Mobile Terminal in the[32] H. del Rio and D. Sarkar, Logarithmic expected[18] H. Murakami, R&D of Total Network System Aiming

networks, Wirel. Commun. Mob. Comput., vol.4, p.

Networks, Springer, 2008, p.464.

Processes, Wiley, 2005.

Ubiquitous Network, IEEE GLOBECOM 2005.

packet delivery delay in mobile ad hoc wirelessat Realization of Ubiquitous Network Society – From

281–287, 2004.

the Results of Ubila Project –, 13th Kyushu[33] M. J. Neely, and E. Modiano, “Capacity and Delay

International Techno-Fair, 2008.

Tradeoffs for Ad-Hoc Mobile Networks,” IEEE Trans.

[19] J. E. MOYAL, The General Theory of Stochastic

Inform. Theory, vol. 51, no. 6, p.1917–1936, 2005.

Population Processes, Acta Math., pp.1-31, 1962.

[34] N. Bansal, and Z. Liu, Capacity, Delay and Mobility[20] B. D. Ripley and F. P. Kelly, Markov Point Processes,

in Wireless Ad-Hoc Networks, IEEE INFOCOM,

Journal of the London Mathematical Society, s2-15,

2003.

188-192, 1977.

[35] A. Jain, M. Gruteser, M. Neufeld, and D. Grunwald,[21] S. M. Torabi and M. A. Samadian, Covering ofBenefits of Packet Aggregation in Ad-Hoc WirelessProblem in Wireless Sensor Networks, Proceedings of
the

8th

WSEAS

International

Conference

Network, PhD Thesis, Dept of Computer Science,on

University of Colorado, 2003.

㧙㧙[36] V. Kawadia, P.R. Kumar, Principles and protocols for

power control in wireless ad hoc networks, IEEE
Selected Areas in Communications: Special Issue on

Wireless Ad Hoc Networks, vol. 23, Issue 1, p.76–88,
2005.

[37] J. Broch, D. A. Maltz, D. B. J. Y. Hu, and J. Jetcheva,

A Performance Comparison of Multi-HopWireless Ad
Hoc Network Routing Protocols, Proceedings of the

Fourth Annual ACM/IEEE International Conference
on Mobile Computing and Networking (MobiCom98), October 25.30, Dallas, Texas, USA, 1998.

[38] R. G. Ogier and V. Rutenburg, “Minimum-expected-delay alternate routing,” Proceedings of the eleventh
annual joint conference of the IEEE computer andcommunications societies on One world throughcommunications (Vol. 2), Florence, Italy, 617 - 625,
1992.

[39] A. R. Mohd Shariff and M. E. Woodward, “A Delay
Constrained Minimum Hop Distributed Routing
Algorithm

using

Adaptive

Path

Prediction,”

JOURNAL OF NETWORKS, VOL. 2, NO. 3,
p.46–57, JUNE 2007.

[40] P.P. Pham, S. Perreau, A. Jayasuriya, “New crossLayer design approach to ad hoc networks underRayleigh fading,” IEEE Journal on Selected Areas inCommunications, Volume: 23, Issue: 1, p.28–39,
2005.

㧙㧙