计算机网路四

简单确定性队列

• Simple deterministic queue model
• small packets reduce end to end delay
• statistical multiplexing

Simple deterministic queue model

假设直到t时刻位置队列里累计的字节数为A(t)

假设直到t时刻位置从队列里分发的字节数为D(t)

Q(t) = A(t) - D(t), Q(t表示t时刻内，队列里的字节数，这里假设分发速率是确定不变的；

d(t): tmie spent in the queue by a a byte arriving at time t

这其实是一种简单的FIFO/FCFS队列模型（先进先出/先来先服务）：相对公平不存在饥饿问题。

看一到简单的题目：

small packets reduce end to end delay

不要一次性直接发送一整个message，而是打包成一个个packet，分别发送，相对延迟较小一点。

statistical multiplexing

多个输入共享一个路由

排队模型特点

这里涉及的内容比较深，不做太多讨论，有兴趣可以看相关论文

通常情况下，packet到达的过程是一个复杂的随机过过程，相关理论称之为排队理论，有以下几个性质：

1. Brustness increases delay
2. Determinism minimizes delay
3. Little's Result
4. The M/M/1 Model

packet到达的分布本身并不是泊松分布，但是有些情况下，可以近似泊松分布来分析

因特网和以太网里的分包交换

优化后的队列模型

output queue cache

input queue cache

virtual

优先级队列模型

双队列模型

加权队列模型