M/M/1 队列

M/M/1 队列由一个先进先出(FIFO)缓冲区构成:数据包按照 Poisson 过程随机到达,而一个处理器(称为服务器)以指定的服务速率从缓冲区中取出数据包。在本教程中,你将了解 Node Editor 以及如何使用它来创建 M/M/1 队列。你还将

  • 使用 Project Editor 收集并可视化不同类型的统计量
  • 学习如何对仿真期间收集的数据应用过滤器
  • 对仿真产生的统计数据进行数学分析

在本教程中,你将使用 Node Editor 和 Project Editor 构建一个 M/M/1 队列,收集关于该模型的统计量,运行仿真,并分析结果。

M/M/1 排队系统的性能取决于以下参数:

  • 数据包到达率
  • 数据包大小
  • 服务能力

如果平均数据包到达率与平均数据包大小的综合效应超过了服务能力,队列长度将无限增长。在本教程中,你将构建一个 M/M/1 队列模型,并确保队列在特定的到达率、数据包大小和服务能力下保持稳定。

图 1:M/M/1 Queue Model

M/M/1 队列模型

开始入门

在对任何网络建模时,你必须清楚地理解要建模的网络以及要回答的问题。在本节中,你将了解

  • M/M/1 队列系统
  • 用于对该系统建模的节点模块类型
  • 该模型可用的分布

关键概念——M/M/1 队列通常由一个 Poisson 过程来描述,该过程控制数据包到达一个无限缓冲区。当一个数据包到达缓冲区头部时,它会被服务器处理并发送到其目的地。

下图所示为 M/M/1 队列系统。

图 2:M/M/1 Queue

M/M/1 队列

λ、1/μ 和 C 分别表示平均数据包到达率、平均数据包大小(服务需求)和服务能力。

因此,队列模型需要产生、排队和服务数据包的手段,而这些都可以用 Node Editor 中提供的现有节点模块来完成。

注意: 要创建 M/M/1 队列,你需要 Node Editor 中的几个对象,包括一个 queue 和两个 processors。source module 生成数据包,sink module 用于处置 source 生成的数据包。queue 代表无限缓冲区和服务器。

processor 模块是节点模型的通用构建块。设置该模块的 process model 属性决定了特定处理器模块的行为。

图 3:Processor Module

处理器模块

source 模块(由处理器模块表示)生成数据包,并以 packets/second 表示生成数据包的创建速率。该速率由 packet interarrivals(即数据包到达队列之间的时间间隔)的 exponential 分布指定。

queue 模块可用于表示无限缓冲区,也可以表示服务器。(使用 queue 表示服务器的原因将在后面讨论。)

图 4:Queue Module

队列模块

虽然它不属于前面描述的 M/M/1 队列系统,但节点模型中将使用一个 sink 模块来处置已被服务的数据包。销毁不再需要的数据包可以释放内存,供仿真期间重复使用。

关键概念——数据包流用于连接 Node Editor 中的各个模块。

要在生成器模块、queue 模块和 sink 模块之间传输数据包,你需要使用数据包流。数据包流是数据包从一个模块移动到另一个模块的路径。

图 5:Packet Streams Move Packets Between Modules

数据包流在模块之间传输数据包

现在,构建该节点模型所需的全部要素都已介绍完毕,你可以开始构建模型了。注意,网络模型(在 Project Editor 中)将包含 M/M/1 队列节点模型的一个实例。完成建模目标不需要其他节点或网络对象,由单个“独立”节点构成的网络模型是有效的。

Node Editor

关键概念——Node Editor 用于构建节点模型,节点模型由通过数据包流和统计线连接的模块组成。

打开 Node Editor,开始创建 M/M/1 队列节点模型。

步骤 1:打开 Node Editor

  1. 选择 File > New…,然后从下拉列表中选择 Node Model。

  2. 单击 OK。

    结果: Node Editor 作为一个新窗口打开。

除了标准的四个按钮(New、Open、Save 和 Print)之外,Node Editor 还有一组用于常用操作的工具按钮:

图 6:Node Editor Tool Buttons

Node Editor 工具按钮

表 1:Node Editor 工具按钮名称

按钮 名称 按钮 名称
1 Create Processor 6 Create Point-to-point Receiver
2 Create Queue 7 Create Point-to-point Transmitter
3 Create Packet Stream 8 Create Bus Receiver
4 Create Statistic Wire 9 Create Bus Transmitter
5 Create Logical Tx/Rx Association 10 Create External System Module

在本教程中你将用到其中的许多按钮。如果你启用了 Wireless 功能,还会看到用于创建无线电接收器、发射器和天线的额外按钮:

图 7:Node Editor Tool Buttons (with Wireless Functionality)

启用 Wireless 功能时的 Node Editor 工具按钮

创建 M/M/1 队列的第一步是定义随机生成数据包的源模块。为此,你可以使用处理器模块。

步骤 2:定义源模型

  1. 单击 Create Processor 工具按钮

    Create Processor 工具按钮

  2. 在工作区中你希望放置该模块的位置单击。

    结果: 一个处理器出现在 Node Editor 工作区中。

  3. 右键单击以结束该操作。

Node Editor 中的模块与 Project Editor 中的网络对象一样具有属性。要指定处理器的生成速率、生成分布、平均数据包大小和数据包大小分布,你必须在处理器模块中设置这些属性。

步骤 3:指定处理器的生成速率、生成分布、平均数据包大小和数据包大小分布

  1. 右键单击处理器模块,然后选择 Edit Attributes。

  2. 将 name 属性改为 src(表示 source):在 Value 列中左键单击,输入 src,然后按 Return。

  3. 将 process model 属性改为 simple_source。你可能需要滚动才能看到该模型。

    结果: 生成器属性出现在属性列表中。

  4. 在 Packet Interarrival Time 属性的 Value 列中左键单击,打开“Packet Interarrival Time” Specification 对话框。

  5. 从 Distribution name 弹出菜单中选择 exponential。这将使生成数据包的到达间隔时间呈指数分布,即 Poisson 过程。

  6. 确认 Mean outcome 设置为 1.0,然后单击 OK。这将数据包的平均到达间隔时间设为 1 秒。

  7. 修改 Packet Size 属性,使 Distribution name 为 exponential,Mean outcome 为 9000。

  8. 单击 OK 关闭规格对话框。这将使生成数据包的大小呈指数分布,平均大小为每包 9000 比特。

  9. 单击 OK 关闭 Attributes 对话框。

关键概念——Packet Interarrival Time 属性指定数据包的到达间隔时间及其分布。Packet Size 属性指定数据包的大小及其分布。

PDF 是 probability density function(概率密度函数)的缩写。PDF 决定随机数的分布。exponential PDF(如为 Packet Interarrival Time 和 Packet Size 属性所设置的分布)的可能取值范围介于零和无穷大之间,更多的取值聚集在指定均值附近或其下方。

在 M/M/1 模型中使用指数 PDF,与最初为服务时间和数据包到达概率指定的 Poisson 过程是一致的。

M/M/1 模型的数据包生成部分已经完成,在仿真期间它将按照所分配的指数 PDF 值生成数据包。

下一步是创建一个 queue 模块,用来模拟 M/M/1 队列中的无限缓冲区和服务器,如下所示。

步骤 4:创建 queue 模块

  1. 单击 Create Queue 工具按钮。

    Create Queue 工具按钮

  2. 在工作区中把 queue 模块放置在生成器模块的右侧,然后右键单击以结束该操作。

  3. 右键单击 queue 模块并选择 Edit Attributes,打开其属性。

  4. 将 name 属性改为 queue。

  5. 将 process model 属性改为 acb_fifo(其背后的原因将在本步骤之后讨论)。

    图 8:Changing the Module Attributes

    修改模块属性

  6. 确认 service_rate 属性设置为 9600。

  7. 单击 OK 关闭 Attributes 对话框。

关键概念——queue 模块的 process model 属性设置该 queue 的底层过程模型,它定义了 queue 模块的行为。

控制我们 queue 模块行为的底层过程模型 acb_fifo 同时模拟了 M/M/1 队列中的无限缓冲区和服务器。如果你想查看该过程模型,可以双击 queue 模块,Process Editor 将打开并显示 queue 的底层过程。不过,本课不会探讨用于定义 acb_fifo 的过程。Basic Processes 教程将介绍 Process Editor。

底层过程模型的名称 acb_fifo 反映了它的主要特征:“a”表示它是活动的(即它充当自己的服务器),“c”表示它能够将多个传入的数据包流汇聚到其单一的内部排队资源,“b”表示服务时间是数据包比特数的函数,“fifo”表示服务排序规则。

关于为节点模块指定过程模型还有一点需要注意:过程模型的属性会出现在模块的属性列表中。因此,你设置的 service_rate 属性值也会设置到底层的 acb_fifo 过程模型中。

为了正确的内存管理,数据包在不再需要时应当被销毁。完成这项任务可以使用 sink 模块。

步骤 5:在数据包不再需要时将其销毁

  1. 单击 Create Processor Module 工具按钮,并在 queue 模块的右侧放置一个处理器模块,如下图所示。

    图 9:Placing the Sink Module

    放置 sink 模块

  2. 右键单击该处理器,打开其 Attributes 对话框。

  3. 将 name 属性改为 sink。

  4. 注意 process model 属性的默认值就是 sink。

    图 10:“sink” is the Default Value

    默认值“sink”

  5. 单击 OK 关闭 Attributes 对话框。

现在,用于模拟 M/M/1 队列的全部模块都已放置在工作区并正确配置,必须用数据包流将它们连接起来,以便数据包能够在模块之间传输。

步骤 6:用数据包流连接模块

  1. 单击 Create Packet Stream 工具按钮。

    Create Packet Stream 工具按钮

  2. 先单击 src 图标,再单击 queue 图标,将 src 模块连接到 queue 模块。

    图 11:Connecting src to queue

    将 src 连接到 queue

  3. 先单击 queue 图标,再单击 sink 图标,将 queue 模块与 sink 模块连接。记住要通过右键单击结束 Create Packet Stream 操作。

    图 12:Connecting queue to sink

    将 queue 连接到 sink

  4. 将节点类型设置为仅 fixed(不包括 mobile 或 satellite):

    • 4.1 选择 Interfaces > Node Interfaces。

    • 4.2 在 Node types 表中,将 mobile 和 satellite 类型的 Supported 值改为 no。

      图 13:Supporting the Fixed Node Type

      仅支持 fixed 节点类型

    • 4.3 单击 OK 关闭 Node Interfaces 对话框。

你已经完成了节点模型的创建,可以开始创建网络模型。首先应当保存你的工作,如下一步骤所述。

步骤 7:保存你的工作

  1. 选择 File > Save。将该节点命名为 <initials>_mm1 并 Save 到你的 op_models 目录。
  2. 关闭 Node Editor。

创建网络

关键概念——M/M/1 队列的网络模型可以在 Project Editor 中构建为单个节点对象。

底层节点模型已经构建完成,现在你可以在 Project Editor 中创建网络模型。通常创建网络模型时,你会创建一个子网(或使用 Startup Wizard 设置场景)并在子网内放置节点。但由于 M/M/1 模型只需要一个不进行通信的节点,节点的位置无关紧要。因此你可以把它放在顶层(全局)子网中。本主题重点关注

  • 创建自定义对象调色板
  • 指定网络模型

首先,为本课设置一个新的项目和场景:

步骤 8:设置新的项目和场景

  1. 关闭所有已打开的项目。
  2. 创建一个新项目和一个新场景。将新项目命名为 <initials>_mm1net,将场景命名为 mm1。单击 OK。
  3. 在 Startup Wizard 中单击 Quit。(无需任何特殊定制。)

构建该网络模型的第一步是创建一个新的模型列表。然后你可以指定该列表,定制调色板,使其只显示你需要的网络对象。

步骤 9:构建模型列表

  1. 单击 Open Object Palette 工具按钮。

    Open Object Palette 工具按钮

  2. 单击对话框左上角的按钮,切换到图标视图。

    图标视图按钮

  3. 单击对象调色板中的 Configure Palette… 按钮。

    结果: 这会打开一系列选项,允许你定制调色板。

  4. 如果 Model list 单选按钮尚未选中,单击选中它。

    图 14:Selecting “Model list”

    选择“Model list”

  5. 单击 Configure Palette 对话框中的 Clear 按钮。这将从调色板中移除除子网以外的所有模型,子网始终存在。

  6. 单击 Node Models 按钮,打开可用节点模型列表。

  7. 在表中滚动,直到找到 <initials>_mm1 节点模型。在 <initials>_mm1 旁边的 Status 列中单击,将其从 not included 改为 included。

    图 15:Including the Custom Node Model

    包含自定义节点模型

  8. 单击 OK 关闭该表。

    结果: 调色板现在包含新包含的节点模型的图标,并且默认还有一个子网图标。

  9. 在 Configure Palette 对话框中单击 OK 以保存调色板配置。在提示处输入名称 <initials>_mm1_palette 并单击 Save。

    结果: Configure Palette 对话框关闭。调色板现在包含了你在 Node Editor 中创建的节点模型。

    图 16:Custom Model included in Object Palette

    对象调色板中包含的自定义模型

    注意: 只有启用了 Wireless 功能时,你才会看到 mobile 和 satellite 子网。

现在你已经配置好自定义调色板,可以创建网络模型了。

步骤 10:创建网络模型

  1. 将 <initials>_mm1 节点模型从对象调色板拖放到工作区。记住要通过右键单击结束该操作。

  2. 关闭对象调色板。

  3. 右键单击该节点对象,从 Object 弹出菜单中选择 Set Name。

  4. 输入 m1 作为名称并单击 OK。

    图 17:Naming the Node

    为节点命名

    节点创建完成后,你需要设置仿真期间要收集的统计量。首先保存你的网络模型:

  5. 选择 File > Save,将模型保存到你的 op_models 目录。

收集结果

对于 M/M/1 队列,需要收集的统计量包括

  • 数据包在无限缓冲区中被延迟的平均时间(queue delay)
  • 队列中数据包的平均数量(queue size,以包计)

这两个统计量对于回答我们针对该网络模型的两个主要问题是必需的:

  • 数据包在队列中等待的平均时间是否超过了可接受的上限?在本教程中,可接受的上限是 20 秒。
  • 队列长度是否单调增长,还是在某个时刻趋于平稳?如果队列长度没有趋于平稳,这可能表明系统(在本例中尤其是服务器)已过载。

步骤 11:定义要收集的统计量

  1. 右键单击该节点对象,从 Object 弹出菜单中选择 Choose Individual DES Statistics。

    结果: Choose Results: top.m1 对话框打开。

    图 18:Choose Results: top.m1 (Initial State)

    Choose Results: top.m1(初始状态)

  2. 展开以下层次结构:

    Module Statistics > queue.subqueue [0] > queue

    第一个“queue”指命名的模块,第二个指模块类型。

  3. 选择 queue size (packets) 和 queuing delay (sec) 统计量。

    图 19:Selected Statistics

    选中的统计量

  4. 单击 OK 关闭 Choose Results 对话框。

现在你已经创建了用于在仿真期间收集统计量的探针,需要运行仿真。

步骤 12:运行仿真

  1. 在 Project Editor 中,单击 Configure/Run Discrete Event Simulation (DES) 工具按钮。

    Configure/Run DES 工具按钮

    结果: Configure/Run DES 对话框打开。

  2. 将仿真 Duration 设置为 7 小时。

  3. 将 Seed 设置为 195。

  4. 单击 Run 关闭 Configure/Run DES 对话框并执行仿真。

根据你机器的速度,仿真应该在几秒内成功完成。当 Simulation Progress 对话框显示仿真已完成时,你会看到一组接下来要执行的典型操作。(如果遇到问题,请参阅"教程疑难解答"。)

图 20:Next Steps

Next Steps

查看结果

第一个值得关注的统计量是平均排队延迟,它显示仿真期间数据包在队列中经历的延迟。下一步骤描述如何查看平均排队延迟。

步骤 13:查看平均排队延迟

  1. 选中 Close window when choosing 'Next Step' 复选框。

  2. 在 Simulation Progress 对话框的 Next Steps 选项卡页上单击 Results Browser 图标。

    Results Browser 图标

    结果: Results Browser 打开。

  3. 确认“Results for:”下拉菜单中选择了 Current Scenario。

    图 21:Output Vector from Current Scenario Selected

    选择来自当前场景的输出向量

  4. 在结果(下方)树中展开以下层次结构:

    Object Statistics > m1 > queue > subqueue [0] > queue

    展开的结果树层次结构

  5. 选择 queuing delay (sec) 统计量。

    结果: 统计量名称旁边的框中出现一个勾选标记,并显示原始数据的预览。

  6. 从过滤器下拉列表(在 Presentation 区域中)选择 average。

    图 22:Selecting the “average” Filter

    选择“average”过滤器

  7. 单击 Show 按钮。

    结果: 平均排队延迟的图应如下图所示:

    图 23:Average Queuing Delay

    平均排队延迟

仿真早期的剧烈变化反映了平均值对相对较少的样本数量的敏感性。在仿真接近结束时,平均值趋于稳定。

验证仿真结果的准确性非常重要。注意本次仿真的平均排队延迟约为 15 秒。下图展示了可用于确定准确性的几个计算。

图 24:Queuing Delay Calculations

排队延迟计算

另一个值得关注的统计量是时间平均队列长度。对仿真期间收集的 queue size 统计量应用时间平均过滤器即可查看该统计量。

步骤 14:查看时间平均队列长度

  1. 将平均排队延迟的图移开,但不要关闭它。

  2. 在 Results Browser 中,单击复选框取消选择 queuing delay (sec) 统计量。

  3. 选择 queue size (packets) 统计量。

  4. 从过滤器下拉列表中选择 time_average。

    图 25:Selecting the queue size (packets) Statistic

    选择 queue size (packets) 统计量

  5. 单击 Show 按钮。时间平均队列长度的图如下图所示:

    图 26:Time-averaged Queue Size

    时间平均队列长度

时间平均队列长度的值可以与由公式 ρ / (1-ρ) 得到的期望值进行比较,其中 ρ = λ / (μC)。该公式得出 15.0,与仿真产生的结果一致。

你可能已经注意到,平均排队延迟和时间平均队列长度的图非常相似。事实上,对于该模型,由于仿真期间发生了大量分散良好的队列插入和移除操作,两个统计量最终值之间的差异可以忽略不计。

本课的最后一张图是队列长度与时间平均队列长度绘制在同一张图上的曲线:

步骤 15:查看瞬时队列长度与时间平均队列长度

  1. 关闭 Results Browser,但保持各个图打开。

  2. 右键单击时间平均队列长度的图,然后从弹出菜单中选择 Add Statistic。

    结果: 出现一个新的 Results Browser。

  3. 在 Results Browser 中,展开 Object Statistics 树,选择 Object Statistics > m1 > queue > subqueue [0] > queue > queue size (packets) 统计量。

  4. 单击 Add 按钮。

    结果: queue size (packets) 统计量的曲线被添加到已有的时间平均队列长度图中(如下图所示)。

    图 27:Queue Size, Time-averaged and Instantaneous

    队列长度:时间平均与瞬时

该图现在显示两条曲线。queue size 曲线显示仿真过程中队列中数据包的数量瞬时值。time-averaged queue size 曲线描绘队列中数据包数量随时间的平均值。

从这张图可以看出,时间平均值没有超过 20 秒的可接受上限,队列也没有单调增长(它似乎在 5 小时左右趋于平稳)。因此,这是一个稳定的系统。

你现在已经完成了 M/M/1 队列教程。你应该对节点模型如何融入整个建模体系、以及如何用它们创建复杂的网络模型有了很好的理解。你也应该已经熟悉了 Node Editor。

下一个教程 Basic Processes 关注过程模型在网络建模中的使用。如果你想继续学习该教程,请先保存尚未保存的所有工作,然后关闭所有打开的编辑器窗口。返回 Contents 窗格中的教程列表,选择 Basic Processes。