取最大值。使用 Power函数有一定的局限性。它主要基于M/M/1队列的网络,并假设 队列的长度为无穷;另外, Power的计算一般在单资源、单用户的情况下使用。 膝 崖点 负载 图104网络负载的 Power函数值 3、资源分配的公平性 在多用户存在的情况下,需要考虑资源分配的公平性。公平性的主要评价方法包括 Max-Min公平性(Max- Min fairness)、公平性指数( Fairness Index)和比例公平性 ( Proportional Fairness)等。 Max-Min公平性被非正式地定义为:每个用户的吞吐量至少和共享相同瓶颈的其它 用户的吞吐量相同。该公平性是一种理想的状况,它是一个广泛使用的评价标准,但是 不能给出具体的公平程度。 公平性指数提供了一个计算公式,可以计算公平的程度,定义为 F(x)=22 用公平性指数计算得到的结果在0和1之间,并且结果不受衡量单位的影响。它的 个性质是:如果在n个用户中只有k个用户平均共享资源,而另外n-k个用户没有任 何资源,函数的结果为 些研究者认为,如果考虑用户的“效用函数”( Utility Function),在一些情况下 使用Max-Min公平性来评价公平程度并不是最理想的。通过使用对数效用函数,Kel!y 引入了比例公平性的概念,其定义为:向量X满足比例公平性,如果对于其它任何向量 Y都满足 ∑ Vi-x
355 取最大值。使用 Power 函数有一定的局限性。它主要基于 M / M /1队列的网络，并假设 队列的长度为无穷；另外，Power 的计算一般在单资源、单用户的情况下使用。 图 10.4 网络负载的 Power 函数值 3、资源分配的公平性 在多用户存在的情况下，需要考虑资源分配的公平性。公平性的主要评价方法包括 Max-Min 公平性（Max-Min Fairness）、公平性指数（Fairness Index）和比例公平性 （Proportional Fairness）等。 Max-Min 公平性被非正式地定义为：每个用户的吞吐量至少和共享相同瓶颈的其它 用户的吞吐量相同。该公平性是一种理想的状况，它是一个广泛使用的评价标准，但是 不能给出具体的公平程度。 公平性指数提供了一个计算公式，可以计算公平的程度，定义为： 2 2 i i n x x F x 用公平性指数计算得到的结果在 0 和 1 之间，并且结果不受衡量单位的影响。它的 一个性质是：如果在n个用户中只有k 个用户平均共享资源，而另外n k 个用户没有任 何资源，函数的结果为 n k 。 一些研究者认为，如果考虑用户的“效用函数”（Utility Function），在一些情况下 使用 Max-Min 公平性来评价公平程度并不是最理想的。通过使用对数效用函数，Kelly 引入了比例公平性的概念，其定义为：向量 X 满足比例公平性，如果对于其它任何向量 Y 都满足： i I i i i x y x 0
由于“公平性”是针对资源分配而言,所以在评价前首先要确定“资源”的含义。 目前大多数研究在评价公平性时都使用吞吐量来衡量用户得到的资源,这是从用户角度 进行考虑的,并不完全适合网络中资源的状况。网络中的资源主要包括链路带宽、网关 的缓冲和网关的处理能力,在考察公平性时应当将这些资源的分配情况综合起来考虑。 102TCP拥塞控制机制研究 10.21互联网的网络模型 拥塞现象的发生和互联网的设计机制有着密切的联系。在互联网中使用的网络模型 可以用以下几点来抽象。 ①分组交换网络 和电路交换( Circuit-Switched)相比,分组交换( Packet-Switched)的本质是网络 资源共享。共享方式提高了网络资源的利用效率,但是也带来了一些问题。在共享方式 下,如何保证用户的服务质量成为一个很棘手的问题;在分组交换的网络中有可能出现 分组的“乱序”现象,对“乱序”分组的处理增加了端系统的复杂性 在分组交换网络中,理论上可以通过路由的调整来“绕过”某个拥塞的网络节点, 负载均衡”就属于这类解决方案。但是在网络中大量的节点周围不存在多条路由,从 而不能完全使用这种方法来解决拥塞问题。另外,如果通过调整路由来解决拥塞问题, 可能会导致路由的不稳定或者振荡,对网络全局的稳定性造成巨大挑战。 ②无连接网络 互联网使用无连接( Connectionless)的模型,两个节点之间在发送数据之前不需要 建立连接。无连接简化了网络的设计,在网络的中间节点不需要保存和连接有关的状态 信息。但是无连接模型也有一定的问题。首先,在无连接模型中难以引入“准入控制” ( Admission control)算法,这样在用户需求大于网络资源的情况下难以保证服务的质 量;其次,在无连接模型中对数据发送源的追踪能力很差,这给网络的安全性带来了很 大的隐患;另外,无连接也是网络中“乱序”分组出现的一个主要原因。 ③尽力而为的服务模型 在互联网中使用的模型为尽力而为(Best- Effort),即互联网不对数据传输的服务质 量提供保证。这个选择和早期网络中的应用有关。网络上传统的主要应用包括FTP、 Telnet和SMTP等,这些应用对网络性能(如时延、分组丢失等)的变化不敏感,Best- Effort 的服务模型可以满足这些应用的需要。而且由于它们在底层都基于包含拥塞控制算法的
356 由于“公平性”是针对资源分配而言，所以在评价前首先要确定“资源”的含义。 目前大多数研究在评价公平性时都使用吞吐量来衡量用户得到的资源，这是从用户角度 进行考虑的，并不完全适合网络中资源的状况。网络中的资源主要包括链路带宽、网关 的缓冲和网关的处理能力，在考察公平性时应当将这些资源的分配情况综合起来考虑。 10.2 TCP 拥塞控制机制研究 10.2.1 互联网的网络模型 拥塞现象的发生和互联网的设计机制有着密切的联系。在互联网中使用的网络模型 可以用以下几点来抽象。 ① 分组交换网络 和电路交换（Circuit-Switched）相比，分组交换（Packet-Switched）的本质是网络 资源共享。共享方式提高了网络资源的利用效率，但是也带来了一些问题。在共享方式 下，如何保证用户的服务质量成为一个很棘手的问题；在分组交换的网络中有可能出现 分组的“乱序”现象，对“乱序”分组的处理增加了端系统的复杂性。 在分组交换网络中，理论上可以通过路由的调整来“绕过”某个拥塞的网络节点， “负载均衡”就属于这类解决方案。但是在网络中大量的节点周围不存在多条路由，从 而不能完全使用这种方法来解决拥塞问题。另外，如果通过调整路由来解决拥塞问题， 可能会导致路由的不稳定或者振荡，对网络全局的稳定性造成巨大挑战。 ② 无连接网络 互联网使用无连接（Connectionless）的模型，两个节点之间在发送数据之前不需要 建立连接。无连接简化了网络的设计，在网络的中间节点不需要保存和连接有关的状态 信息。但是无连接模型也有一定的问题。首先，在无连接模型中难以引入“准入控制” （Admission Control）算法，这样在用户需求大于网络资源的情况下难以保证服务的质 量；其次，在无连接模型中对数据发送源的追踪能力很差，这给网络的安全性带来了很 大的隐患；另外，无连接也是网络中“乱序”分组出现的一个主要原因。 ③ 尽力而为的服务模型 在互联网中使用的模型为尽力而为（Best-Effort），即互联网不对数据传输的服务质 量提供保证。这个选择和早期网络中的应用有关。网络上传统的主要应用包括 FTP、 Telnet 和 SMTP 等，这些应用对网络性能（如时延、分组丢失等）的变化不敏感，Best-Effort 的服务模型可以满足这些应用的需要。而且由于它们在底层都基于包含拥塞控制算法的
TCP协议,因此可以在一定程度上适应网络环境的变化。但是随着多媒体等应用在网络 中的引入, Best-Effort模型已经不能满足许多新的网络应用的要求。例如,很多应用的 性能对于时延的变化比较敏感,而且它们在网络发生拥塞时不能降低发送速率。 10.22线性拥塞控制机制 假设网络中有n个用户共享有限的资源,如图10.5所示。网络系统的拥塞状态由系 统中数据包的数量决定。假设时间可以分割成长度相同的时间片( Time Slot),用户在 每个时间片开始时根据前一个时间片收到的网络反馈来设定本时间片的负载水平。如果 在某个时间片t,第i个用户的负载为x(),那么瓶颈资源上的总负载则为∑x(),此 时的系统状态可以用n维向量x(t)={x1(,x2(),x2(t)}表示。 用户1 xE 用户2 用户n 图105网络资源控制机制示意图 由于网络处于或者接近膝点,所有用户的资源需求都是可以得到保证的(这一情况 在崖点并不成立)。因此,x,()表示第i个用户的资源需求,同时也是系统分配给它的 资源数。在每个时间片,网络系统根据负载情况向所有用户发送二进制反馈信号y(t)。 当y()为0时,用户会增加资源需求;反之,当yt)为1时,用户会降低资源需求。 所有用户与网络系统进行交互,改变(增加或者减少)各自的资源需求,假设改变 量为u1(t),则有下面的状态等式( State Equation) x(t+1)=xr、()+u1(t) 其中改变量u1()表示第i个用户的控制量,它是关于本用户历史需求和系统反馈的 函数,即 u1(t)=f(x,(,y;(t) 因此状态等式可以重新写为 x(t+1)=x,()+f(x、(),y,(t)
357 TCP 协议，因此可以在一定程度上适应网络环境的变化。但是随着多媒体等应用在网络 中的引入，Best-Effort 模型已经不能满足许多新的网络应用的要求。例如，很多应用的 性能对于时延的变化比较敏感，而且它们在网络发生拥塞时不能降低发送速率。 10.2.2 线性拥塞控制机制 假设网络中有n个用户共享有限的资源，如图 10.5 所示。网络系统的拥塞状态由系 统中数据包的数量决定。假设时间可以分割成长度相同的时间片（Time Slot），用户在 每个时间片开始时根据前一个时间片收到的网络反馈来设定本时间片的负载水平。如果 在某个时间片t ，第i 个用户的负载为 x t i ，那么瓶颈资源上的总负载则为 x t i ，此 时的系统状态可以用n维向量 x t x1 t, x2 t,.., x3 t表示。 1 x xi Xgoal? x2 xn 图 10.5 网络资源控制机制示意图 由于网络处于或者接近膝点，所有用户的资源需求都是可以得到保证的（这一情况 在崖点并不成立）。因此， x t i 表示第i 个用户的资源需求，同时也是系统分配给它的 资源数。在每个时间片，网络系统根据负载情况向所有用户发送二进制反馈信号 yt。 当 y t 为 0 时，用户会增加资源需求；反之，当 yt为 1 时，用户会降低资源需求。 所有用户与网络系统进行交互，改变（增加或者减少）各自的资源需求，假设改变 量为u t i ，则有下面的状态等式（State Equation）： x t x t u t i 1 i i 其中改变量u t i 表示第i 个用户的控制量，它是关于本用户历史需求和系统反馈的 函数，即 u t f x t , y t i i i 因此状态等式可以重新写为： x t x t f x t , y t i 1 i i i
需要注意的是,每个用户并不知道其它用户的资源需求,因此,当j≠时,1()不 是关于x()的函数。 通常情况下,控制函数∫可以是任意线性或者非线性函数,此处只关注线性控制函 数,则状态等式可以归约为 ;(t+) Ja,+b r, ()if y(0)=0=Increase ap+bpx, (t) if y(o)=1=Decrease 其中a1、aD、b、bb为常数 通过为上述4个参数设定不同的数值,将得到不同的拥塞控制机制 ①“乘性增加,加性减小”( Multiplicative Increase Additive Decrease,MIAD)控 制机制。当a1=0、b1>1、aD<0、b=1时,状态等式可表示为 ∫bx,()ify(t)= +x,(o) if y(t) ②“加性增加,加性减小”( Additive Increase additive decrease,AIAD)控制机制。 当a1>0、b1=1、aD<0、b=1时,状态等式可表示为 x(t+)= )ify()=0→ ap+x,(o)if y()=1=Decrease ③“乘性增加,乘性减小”( Multiplicative Increase Multiplicative Decrease,MMD) 控制机制。当a1=0、b>1、aD=0、0<b<1时,状态等式可表示为 x,(+0)=b, x, (t)if y()=0=Increase lbox, ()if y(t)=1=Decrease ④“加性增加,乘性减小”( Additive Increase Multiplicative Decrease,AIMD)控 制机制。当a1>0、b=1、aD=0、0<b<1时,状态等式可表示为 (t+1) a,+x, if y(t)=0=Increase ()ify(t)=1→ Decrease 102.3线性拥塞控制机制评价 在1022节中通过设置不同参数值可以得到一组控制机制的集合,为了确定哪些控 制机制是可行的,需要观察系统状态在n维向量空间中的变迁轨迹。为了便于描述,考 虑系统中只有两个用户的情况,此时n维向量空间可以简化为二维空间 如图106所示,两个用户的资源分配{x1(t,x2(}可以用二维空间中的点(x,x2
358 需要注意的是，每个用户并不知道其它用户的资源需求，因此，当 j i 时，u t i 不 是关于 x t j 的函数。 通常情况下，控制函数 f 可以是任意线性或者非线性函数，此处只关注线性控制函 数，则状态等式可以归约为： if 1 Decrease if 0 Increase 1 D D I I a b x t y t a b x t y t x t i i i 其中 I a 、 D a 、 I b 、 D b 为常数。 通过为上述 4 个参数设定不同的数值，将得到不同的拥塞控制机制。 ① “乘性增加，加性减小”（Multiplicative lncrease Additive Decrease，MIAD）控 制机制。当 0 aI 、 1 bI 、 0 aD 、 1 bD 时，状态等式可表示为： if 1 Decrease if 0 Increase 1 D I a x t y t b x t y t x t i i i ② “加性增加，加性减小”（Additive Increase Additive Decrease，AIAD）控制机制。 当 0 aI 、 1 bI 、 0 aD 、 1 bD 时，状态等式可表示为： if 1 Decrease if 0 Increase 1 D I a x t y t a x t y t x t i i i ③ “乘性增加，乘性减小”（Multiplicative Increase Multiplieative Decrease，MIMD） 控制机制。当 0 aI 、 1 bI 、 0 aD 、0 1 bD 时，状态等式可表示为： if 1 Decrease if 0 Increase 1 D I b x t y t b x t y t x t i i i ④ “加性增加，乘性减小”（Additive Increase Multiplicative Decrease，AIMD）控 制机制。当 0 aI 、 1 bI 、 0 aD 、0 1 bD 时，状态等式可表示为： if 1 Decrease if 0 Increase 1 D I b x t y t a x t y t x t i i i 10.2.3 线性拥塞控制机制评价 在 10.2.2 节中通过设置不同参数值可以得到一组控制机制的集合，为了确定哪些控 制机制是可行的，需要观察系统状态在n维向量空间中的变迁轨迹。为了便于描述，考 虑系统中只有两个用户的情况，此时n维向量空间可以简化为二维空间。 如图 10.6 所示，两个用户的资源分配x1 t, x2 t可以用二维空间中的点（ 1 x ， 2 x ）