用流队列fluid queue建模可解码包数量的分布

最近看DTN论文,发现一些文章是用流队列理论建模可解码包数量的分布(distribution of the number of decodable packets)。

1. Fluid Queue

摘抄维基百科如下[1]

In queueing theory, a discipline within the mathematical theory of probability, a fluid queue (fluid model,[1] fluid flow model[2] or stochastic fluid model[3]) is a mathematical model used to describe the fluid level in a reservoir subject to randomly determined periods of filling and emptying.

The model was first introduced by Pat Moran in 1954 where a discrete-time model was considered. The model has been used to approximate discrete models, model the spread of wildfires,[4] in ruin theory[5] and to model high speed data networks.[6] The model applies the leaky bucket algorithm to a stochastic source. Fluid queues allow arrivals to be continuous rather than discrete, as in models like the M/M/1 and M/G/1 queues.

Fluid queues have been used to model the performance of a network switch,[10] a router,[11] the IEEE 802.11 protocol,[12] Asynchronous Transfer Mode (the intended technology for B-ISDN),[13][14] peer-to-peer file sharing,[15] optical burst switching,[16] and has applications in civil engineering when designing dams.[17] The process is closely connected to quasi-birth–death processes, for which efficient solution methods are known.[18][19]

2. 模型描述

摘抄维基百科如下[1]

A fluid queue can be viewed as a large tank, typically assumed to be of infinite capacity, connected to a series of pipes that pour fluid in to the tank and a series of pumps which remove fluid from the tank. An operator controls the pipes and pumps controlling the rate at which fluid pours in to the buffer and the rate at which fluid leaves.

When the operator puts the system in to state i we write ri for the net fluid arrival rate in this state (input less output). When the buffer contains fluid, if we write X(t) for the fluid level at time t,[20]

\frac{\mathrm{d}X(t)}{\mathrm{d}t} = \begin{cases} r_i & \text{ if } X(t)>0 \\ \max(r_i,0) & \text{ if } X(t)=0.\end{cases}

The operator is a continuous time Markov chain and is usually called the environment process, background process[21] or driving process.[6] As the process X represents the level of fluid in the buffer it can only take non-negative values.

The model is a particular type of piecewise deterministic Markov process and can also be viewed as a Markov reward model with boundary conditions.

3. 与网络编码

网络中使用线性网络编码,目的节点需要收到一定数目的数据包方能解码。而目的节点接收数据包可以视为流队列(只有注入,没有留出),这样就可以用流队列来建模可解码包数目的分布。

但具体怎么构造模型呢?欢迎推荐资料,也欢迎交流:sparkandshine@163.com

参考资料:
[1]Wikipedia: Fluid queue

Leave a Reply

Your email address will not be published. Required fields are marked *