基于排队论的路由选择策略研究

朱小流，廖晓谈

（南京熊猫汉达科技有限公司，江苏 南京 210000）

0 引言

随着通信行业的蓬勃发展，新的技术层出不穷。低时延、高效率是通信质量的一个重要指标，而通信过程中信息的传输离不开路由的选择，如何优化路由器的选路模型，减少信息传输的时间，降低时延是一个十分重要的课题。本文针对某区域设置局域网的实际问题，分别设计了不同的路由器方案，通过将信息在各个路由器节点处的逗留时间进行求和，得到了总的信息传输时间。将平均的信息传输时间进行比较，得到了时延最低的路由器选择方案。最后，通过蒙特卡洛仿真验证了理论分析的正确性。

1 系统模型

在实际通信过程中，同一个网段的终端设备都会连接同一个路由器，该路由器为网关路由器。不同网段的终端设备在通信的过程中，发端发出的信息需要经过自身网段的网关路由器后，再经过路由选择到达收端的网关路由器，最终再传给收端。本文通过建立三种传输模型，分析比较三种网络模型下信息的平均传输时间，寻找信息传输时间最短的方案，使得系统的延迟降低，为系统的路由选择提供参考。

1.1 方案1 系统模型

如图1所示，信息在经过网关路由器后，以概率P中间路由1、P中间路由2传到两个路由器，在这里，我们假设信息等概传输到两个中间路由器。信息传输速率为λ，则到达后面的两个路由器时，信息速率减半为λ/2，最终到达收端网关路由器速率为λ。发端网关、中间路由和收端网关的服务速率为μ1、μ2、μ3。假设三种路由器的服务员数量为c1、c2、c3。

图1 方案1传输网络

1.2 方案2 系统模型

如图2所示，信息在经过网关路由器后，经过一个中间路由，中间路由器的服务员数为方案 1两个中间路由器服务员数之和。最终信息在汇总到收端的网关路由器。发端网关、中间路由和收端网关的服务速率为μ1、μ2、μ3。服务员数量分别为c1、c2=c21+c22、c3。

图2 方案2传输网络

1.3 方案3 系统模型

如图3所示，信息在经过网关路由器后，不经过中间路由的传递，直接将信息发送给接收端的网关路由器。此方案也加大了发端路由器的负荷，使得信息处理速率降低，假设速率为μ1、μ3。服务员数量分别为c=c1+c2、c3。

图3 方案3传输网络

2 平均信息传输时间

在得到M/M/c 排队模型的平均逗留时间的基础上，计算各个方案的信息传输时间，即信息在每个节点的平均逗留时间之和。

2.1 方案1 传输时间

方案1可看作三个独立的M/M/c 排队模型，具体的参数设置在系统模型中已经给出，在此不再赘述。因此，信息传输时间为：

2.2 方案2 传输时间

方案 2在方案 1的基础上将中间路由合并，减少路由器数量，增多单个路由器中服务员数量，得到信息传输时间为：

2.3 方案3 传输时间

在方案2的基础上，进一步减少路由器数量，由发端的网关路由器同时实现收集信息和选路的作用，信息传输速率为：

3 仿真结果与分析

本节通过matlab 对通信过程进行仿真，分析比较不同方案下的传输性能。为了避免系统崩溃，输入速率和服务速率需要满足如无特殊说明，系统参数设置如下：λ=120、μ1=60、μ2=80、μ3=80，服务员数量分别为：c1=5、c21=1、c22=1、c3=2，时间单位为s。

图4 信息传输时间随输入速率变化图

如图4所示，仿真点与理论曲线基本重合，验证了理论分析的正确性。随着信息速率的提高，系统节点的阻塞概率C（c，a）提高，使得信息在单个节点的逗留时间增大，增大了信息的平均传输时间，这与实际情况相符，在信息量较大的情况下，网络的延迟会提高。同时，从图4可以发现，在本文设定的系统参数下，方案3的信息传输时间最短，方案1的传输时间最长，说明方案3的路由选择方案最好。

如图5所示，仿真点与理论曲线基本重合，验证了理论分析的正确性。由于方案3的性能最优，在此我们单独对方案3进行研究。在方案3中，由于发端的网关路由同时实现接收集信息和选路功能，使得路由器的负荷增大，使得方案3中的发端网关路由器的信息处理速率低于系统预设。通过仿真分析可以发现，当方案3中发端网关路由器信息服务速率低于25时，传输时间长于方案2，当信息服务速率低于21时，传输时间长于方案1。说明当路由器负荷过大，使得方案3的发端网关路由器信息服务速率降低时，方案 3可能并不是最佳选择。

图5 信息传输时间随服务速率变化图

4 结束语

本文基于排队论理论知识，建立了三种信息传输过程中的路由选择模型，研究得到了信息传输时间随信息输入速率的变化图和最优方案下信息传输时间随路由器服务速率的变化图。研究表明，当网关路由器结合中间路由器后，如能保持较高的服务速率，信息的传输时间最低，系统的延迟最小。

但应注意在实际中，通常情况下不会采用只有两个网关路由的通信方式。这是因为采用此方案时，若一个终端想要和其他终端通信，需要单独建立一条链路，然而物联网时代的终端数目庞大，不论是在经济性还是可行性的考虑下都不是一个好的选择。然而，在小型局域网中，当终端的数目较少，不同网段的终端较少时，可以每个网关路由器直接建立通路，此方案以其高效性可以展现出巨大的优势。