4.4 计算系统和网络

跟在物理系统的控制中的应用一样，反馈在计算系统中的应用也遵从相同的原理，但所测量的类型、控制输入的类型有所不同。在计算系统或网络中，测量（传感器）往往跟所用的资源相关，这可以包括处理器负荷、内存用量、网络带宽等类的量。控制变量（执行器）往往牵涉对程序所能获得的资源设置限制。这可以是对程序可占用的内存量、磁盘空间、可消耗的时间进行控制，也可以是开始或停止程序的执行、推迟资源的获得时间，或拒绝对服务器程序的外来请求。对网络计算系统进行过程建模是一项挑战性的工作，当没有基于基本原理的模型时，往往使用基于测量的经验模型。

4.4.1 Web服务器控制

Web服务器响应来自因特网的请求，并以网页的形式提供信息。现代Web服务器会启动多个进程来响应请求，每个进程被分配给单个请求来源，直到该来源在一段预定的时间内没有进一步的请求为止。空闲的进程成为进程池的一部分，可以用于响应新的请求。为了快速响应Web请求，保证Web服务器的计算能力不会被进程过载、内存不会被耗尽，是极其重要的。因为可能还有其他进程在服务器上运行，所以能够得到的处理能力和内存大小是不确定的，在这种不确定性的场合，反馈可以用来提供良好的性能。

图4.11展示了Web服务器的反馈控制。该服务器执行的操作包括：将到达的连接请求放入一个队列，然后为每个被接收的连接启动一个子进程来处理请求。子进程响应来自特定连接的请求，它将在忙碌与等待之间不断切换[在相继到来的请求之间保持子进程的活跃称作连接的 持久性 （persistence），这可以显著降低当单个站点请求多个信息时的延迟]。如果在足够长的时间里（由参数KeepAlive控制）没有收到请求，那么连接将被断开，子进程将进入空闲状态，可以被分配给另一个连接。能够同时服务的最大请求数目为MaxClients，其余的请求将保留在传入请求队列中。

控制服务器的这些参数代表着在性能（请求得到响应的速度有多快）与资源占用（服务器占用的处理能力及内存）间的一个折中。增大MaxClients参数可以使连接请求更快地从队列中出来，但对处理能力和内存的需求将增加。延长空闲存活时限KeepAlive则意味着单个连接可以在空闲状态下维持更长的时间，这将降低机器处理的负荷量，增加队列的长度（因而增加用户启动连接所需的时间）。要使繁忙的服务器成功运行，离不开以上参数的恰当选择，而这通常要靠反复试验。

为了更详细地建模这个系统的动态，我们以平均处理器负荷 x _cpu 和内存用量百分率 x _mem 为状态变量，建立一个离散时间模型。选择最大客户连接数 u _mc 以及空闲存活时限 u _ka 为系统的输入。假若模型在平衡点周围是线性的，那么系统动态可以写成：

式中，矩阵 A 和 B 的元素可以利用经验测量来确定，或者基于Web服务器的处理器和内存使用的具体建模来确定。文献[59,97]利用系统辨识方法，获得了线性化的动态方程的矩阵元素为：

其中的系统是围绕以下平衡点进行线性化的：

x _cpu =0.58， u _ka =11s， x _mem =0.55， u _mc =600

这个模型表现出了上面描述的那些基本特性。先看矩阵 B ，可以看到增加空闲存活时限KeepAlive（矩阵 B 的第一列）将使处理器的使用和内存的使用都降低，由于连接更为持久，服务器将把较多的时间用于等待一个连接的关闭而不是花在一个新的活跃连接上。而最大客户连接数MaxClients的增大，则将需要更大的处理能力和内存需求。请注意对处理器负荷影响最大的是空闲存活时限。矩阵 A 则告诉我们，在状态空间的平衡点附近的一个区域内，处理器及内存的使用是如何演化的。对角线元素描述了单个资源在瞬时增大或降低后是如何回到平衡点的。非对角线元素则表明在两个资源间存在耦合，一个资源的变化将引起另一个发生更大的变化。

这个模型虽然相当简单，但在后面的例子里将会看到，可以通过实时修改服务器的控制参数，来提供鲁棒性，从而抑制服务器负载不确定性的影响。类似的机制已经在其他类型的服务器中得到应用。很重要的一点是，要牢记这个模型的假定条件以及它在确定模型适用性方面的作用。特别地，由于用了平均采样时间来建立模型，因此这个模型不能精确反映高频下发生的现象。

4.4.2 拥塞控制

因特网建立的目的是提供一个巨大的、高度分散的、高效的、可扩展的通信系统。该系统由大量互联的网关组成。一条信息会被分割成多个包，在网络的不同路径上传输，这些包在接收处将被重新组合，以恢复信息。当收到包时，应答（“ack”）信息将被送回发送方。该系统的运行处于一个简单而强大并且一直在进化的分布式控制结构的控制之下。

该系统有两种称作 协议 （protocol）的控制机制：一个是用于端到端网络通信的传输控制协议（TCP），另一个是用于路由包数据以及用于从主机到网关（或从网关到网关）通信的因特网协议（IP）。当前的协议是在20世纪80年代中期发生了一些特别严重的因特网拥塞崩溃事件后发展起来的。TCP的控制机制是以从发送者到接受者、再回到发送者的回路中，收、发包的数目守恒为基础的。当不存在拥塞时，发送速率增加；当存在拥塞时，发送速率就会降到一个很低的水平。

为了推导拥塞控制的整体模型，对系统三个独立的部分进行建模：单个源计算机发送包的速率，链路（路由器）中队列的动态，队列的入场控制机制。图4.12a是系统的原理框图。

目前因特网上采用的源控制机制是大家所熟知的TCP/Reno协议 ^[168] 。这个协议是这样运作的：将包发往接受者，然后等待一个来自接受者收到包之后发出的确认信号。如果经过某个限定的时间后，仍没有收到应答，就重发包。为了避免在发送下一个包之前因等待应答而浪费时间，Reno协议在由最后一个已应答包所界定的时间窗口里发送多个包。如果该窗口的长度选择得当，则在窗口开头处发送的包将在窗口结束处的包被发送之前得到应答，这样一来，计算机就可以高速地、连续流式地传输数据包。

为了确定所用窗口的大小，TCP/Reno协议采用了这样一种反馈机制，大致来讲就是：只要数据包得到确认，窗口大小就以固定的速度增大，而一旦有数据包丢失，窗口大小就减半。这个机制使得窗口大小可以动态调整，只要数据包能送达，计算机就以“贪婪的”方式运行，而一旦遇到拥塞则立即撤退。

通过描述窗口大小的动态，可以建立源计算机的行为模型。假定有 N 台源计算机，并令 w _i 为第 i 台计算机当前的窗口大小（按数据包数计算）。令 q _i 表示数据包在源计算机到接受者之间某处丢失的端到端概率。于是可以将窗口大小 w _i 的动态建模为以下的微分方程：

式中， τ _i 是数据包到达目的地且应答返回的往返时间， r _i 是从已收到数据包列表中清除数据包的速率。该动态方程右端第一项代表当收到一个数据包时窗口大小的增加，第二项则代表当丢失一个数据包时窗口大小的减小。请注意 r _i 是在 t-τ _i 时刻估算的，这考虑了收到应答所需的时间。

链路的动态受路由器队列的动态以及队列的入场控制机制的控制。假定网络中有 L 个链路，并用 l 来索引单个链路。用路由器缓冲中当前包的数目 b _l 来对队列建模，并假定路由器以 c _l 的速率（等于链路的容量）传送包。那么缓冲的动态可以写成：

式中，当链路 l 被源计算机 i 使用时取 R _li =1，否则取 R _li =0； 是一个包从源计算机 i 到达链路 l 所用的时间； s _l 是包到达链路 l 的总速率。矩阵 R ∈ℝ ^{L × N} 称作 路由矩阵 （routing matrix）。

入场控制机制决定路由器是否会接收一个特定的数据包。由于我们的模型是基于网络中的平均数量的，而不是基于单个数据包的，因此可以这样来简单建模，即假定数据包丢失的概率取决于缓冲区有多满。若令 b _{l max} 为路由器 l 可以缓冲的最大数据包个数，那么丢包概率可写成 p _l = β _l （ b _l ， b _{l max} ），其中函数 β _l 满足 β _l （0， b _{l max} ）=0和 β _l （ b _{l max} ， b _{l max} ）=1。为简单起见，现在假设 p _l = ρ _l b _l （更详细的模型请参考习题4.5）。可以用特定链路的丢包概率来确定数据包传输的端到端丢包概率：

式中， 是从链路 l 到源计算机 i 的向后延迟；“约等于”成立的条件是各个链路的丢包概率足够小。这里之所以采用向后延迟，是因为这样能考虑到应答包被源计算机收到所需的时间。

式（4.17）、式（4.18）和式（4.19）一起，共同构成了一个拥塞控制动态模型。考虑由 N 台相同的源计算机和一个链路构成的特例，有助于获得一些实质性的见解。此外还假定可以忽略向前与向后的时延，并且所有路由器都没有发生饱和或空闲，则系统的动态可以简化成以下的形式：

式中， w _i ∈ℝ（ i =1，…， N ），它们构成了一个表示数据源的窗口大小的向量； b ∈ℝ是路由器当前缓冲的大小； ρ 控制着数据包的丢失率； c 是连接路由器与计算机的链路容量。变量 τ ^p 代表路由器基于缓冲大小和链路容量来处理一个数据包所需的时间。将 τ ^p 代入以上各个方程，可以重写状态空间动态方程为

文献[167,168]提供了更复杂的模型及相应的习题和例子。

令 可以求得系统的标称运行点：

由于所有的源都具有相同的动态，因此所有的 w _i 相同，故可以证明有唯一的平衡点满足以下方程：

其中第二个方程的解有点复杂，不过很容易进行数值求解。其解答随1/（2 ρ ² N ² ）变化的函数关系如图4.12b所示。可以看出，在平衡点还有以下等式成立：

图4.13仿真了60台源计算机通过单个链路进行通信的情况，其中有20台源计算机在 t =500ms时发生了掉线，其余的源计算机则增大各自的速率（窗口大小）来填补空缺。请注意缓冲大小和窗口大小是自动调整来匹配链路容量的。

文献[236]对计算机网络问题进行了深入的介绍。文献[128]对因特网控制原理背后的思想进行了很好的介绍。文献[142]则在系统分析方面进行了较早期的研究。文献[131,117]提供了许多反馈用于计算机系统的例子。 F5145gjmQSUGp2oE4pPzz6hAOpcVKAGivZbZFiM5oUMUMm0AFl+KSZIplAPa+At5