基于可变连接价格的TCP接入控制研究*
董永强，黄一鸣
东南大学计算机科学与工程学院，江苏南京（210096）
东南大学计算机网络和信息集成教育部重点实验室，江苏南京（210096）
E-mail: dongyq@https://www.doczj.com/doc/f514311240.html,
摘要：本文面向有连接的弹性应用，探讨了基于可变连接价格的TCP接入控制问题。将该问题描述为追求连接阻塞率最小化和活动连接时长最大化的多目标优化问题，分别考察了在连接请求确定到达和随机到达时的连接价格确定问题。提出了在阻塞率不高于某一设定值的情况下，使得单位时间内期望活动连接时长最大化的连接价格调整算法，并给出了基于Socks代理协议的价格协商和接入控制实现方法。
关键词：接入控制，网络定价，阻塞率，活动时长，Socks协议
中图分类号：TP393
1引言
传统网络的拥塞控制主要依赖于TCP协议内在的AIMD窗口自适应机制[1]。从理论上来说，TCP 不断地探测网络的可用带宽，并相应调整其数据发送窗口和发送速率，在出现丢包（TCP Reno等）或时延明显增大（TCP Vegas等）时，主动缩减其拥塞窗口的大小，以达到释放网络缓冲区、缓解网络拥塞的目的。正是由于TCP这一良好的自觉和自适应特性，与TCP兼容/友好成为其它速率控制算法的重要设计指标[2]。但近年来，基于AIMD的TCP拥塞控制却在不断受到挑战，表现在：（1）随着基于UDP的多媒体应用的普及，传统网络中以TCP为主导的流量结构在悄悄发生变化。尽管当前多数多媒体应用都已经支持多速率编码和自适应速率调整，相应地也就具有了一定的拥塞响应能力，但仍有不少应用其数据发送速率固定不变而与网络拥塞状况无关，这些应用的部署对网络的拥塞控制带来相当的影响。更有甚者，一些基于UDP的无意义恶意流量也在一定的网络范围内肆虐，严重干扰了网络的正常运行，比如通过一些简单的流量发生器工具，恶作剧者就能够轻易使网络处于局部瘫痪状态。
（2）随着开源操作系统的应用，越来越多的人们可以直接接触操作系统的内部实现，包括对TCP 传输控制协议的实现进行修改，甚至为了追求传输速率而绕开TCP内在的拥塞控制机制。经过修改的TCP协议，在和传统基于AIMD窗口调整的TCP协议争用带宽时，显然要强势得多。文献[3]通过一个简化的博弈模型，分析了如果允许用户在网络出现拥塞时自行做出适当的反应，则他们的占优（主导）均衡策略必然是继续以当前速率或者是更高的速率来发送数据，而不是选择退让，因为退让策略并不符合他们的利益，而这又必然导致拥塞加剧甚至崩溃。
（3）随着各类应用模式的层出不穷，一些新型应用如多线程下载、P2P文件共享等，虽然是基于标准的TCP协议实现，理论上来讲也不会造成网络拥塞和崩溃，但却可能导致网络资源的滥用和资源分配的公平性问题。原本可以获得较高传输性能的其它用户，不得不忍受这些披着合法外衣的贪婪用户所造成的网络性能下降。如果所有用户为使用网络而付出的成本是一样的，那么显然大流量的用户挤占
*基金资助：高等学校博士学科点专项基金（20040286001）、国家自然科学基金重大研究计划项目（90604003）
了低流量用户的利益，或者说低流量用户不情愿地补贴（subsidize）了那些贪婪的大流量用户。近几年，对P2P等应用及其流量进行控制，已经引起人们特别是运营商广泛的关注。
凡此种种，都是我们在研究网络拥塞控制和设计网络协议时所不愿看到的。我们希望，在网络协议的设计和运行中，能够引入有效的激励约束机制，在这样的机制作用下，每一用户能够自觉自愿、合理有序地使用网络资源。价格机制正是在这样的需求背景下，作为一种激励相容（incentive compatible）的方法，一种可以有效规避“公共灾难”（tragedy of the commons，[4]）的手段，引入到网络资源分配和拥塞控制问题中来的。
2基于连接价格的TCP接入控制
通常来说，TCP用户并不十分在意瞬时的传输速率，甚至能够接受非常低的传输速率，这在其效用特性上表现为连续增的效用函数，如对数形式等。但尽管如此，人们还是希望TCP数据传输能够在尽可能短的时间内完成，或者说对其期望吞吐量还是有一个基本的要求。基于这样的考虑，我们认为，要使基于TCP的应用能够向可运营的方向发展，必须对TCP的数据传输速率有一个基本的保障，又由于TCP面向连接的特性，在连接建立阶段实施面向TCP协议的接入控制就成为一种可行的方案。接入控制的原则可以有很多种，如先来先服务等，这里我们采用的方法是基于支付意愿的价格接入机制。基于价格的TCP接入控制遵循以下思想：
（1）网络接入点根据用户的普遍要求，确定每一用户的期望吞吐量，再按照网络链路容量和服务能力，确定最大可以接入的连接数。
（2）网络接入点根据某种优化原则，确定一个允许接入价格，只有当用户愿意支付的价格高于该价格时，用户连接才有可能被接入。该接入价格可以根据连接一级的拥塞状况做动态调整。
（3）用户根据自己的支付意愿决定是否发起连接，或者在其连接请求中给出其愿意支付的价格，由网络接入点来决定该连接能否接入。
（4）网络接入点在决定某一用户连接能否接入时，需要考虑以下基本因素：a) 该用户愿意支付的价格是否高于接入价格；b) 当前是否有足够的资源（剩余可用连接数）能够保证该用户连接期望的吞吐量等。
定义：
I类阻塞：若用户愿意支付的网络接入价格低于网络确定的最低接入价格，该连接请求将被拒绝，其目的是留出网络资源给愿意接受较高价格（对网络运营商来说其价值也较高）的用户连接。在接入价格对用户已知的情况下，这类阻塞通常表现为隐式阻塞，即用户主动放弃其连接请求。
II类阻塞：虽然用户愿意支付的网络接入价格高于网络确定的最低接入价格，但由于实际的网络链路资源不足（表现为接入的用户连接数已经达到网络可接纳的值），导致无法接入，其目的是避免网络拥塞和已有连接的传输性能受到影响。这类阻塞应尽量避免，其直接影响是用户满意度下降。
上述接入控制机制的要点是：网络接入点根据连接一级的拥塞状况（即资源的供需状况），制定合理的连接价格。用户在其连接请求中给出愿意接受的连接价格，只有该价格高于网络接入点确定的连接价格，连接才能被接入。网络按照接入时确定的连接价格，根据用户的实际连接时长进行计费。要说明的是：
（1）这里所说的网络接入点，可以是访问控制网关，也可以是TCP连接的对端如文件传输服务器。对前者，接入控制的资源约束主要是链路带宽等传输资源，根据用户数据的传输方向还有上行和下行之
分；对后者，接入控制的资源约束主要是服务器的处理资源，当然也包括网络带宽等通信资源。本文主要针对的是前一种情况，但有关算法和思路同样适用于后一种情况。
（2）关于网络接入价格如何确定，可以有定价法和竞价法两种方法，这里我们以定价法为主进行分析。但是在实现时，为了简化向用户传递价格的环节，借鉴了竞价法的思想，由用户在其连接请求中主动携带其支付意愿等信息。从这个意义上，接入价格类似于“智能市场”机制（smart market ）中的出清价格（cutoff price ）[5]，但两者形成的机理有所不同，并且前者是以连接为单位，后者以分组为单位。
（3）当前有一些多媒体应用，基于SIP 或RTSP 等协议完成连接和会话协商，数据传输则基于UDP 协议完成，其速率控制和服务质量由上层应用通过自适应调整其编解码方法来实现。对这类应用，原则上也可以采用类似于TCP 接入控制的定价机制来予以支持。
另外，对TCP 连接进行接入控制（具体来说是进行II 类阻塞判断时），还要考虑相继到达的TCP 连接的相关性。以Web 页面访问为例，其中大量嵌入了图片、Flash 动画及其它对象，这些对象往往通过超链指向其它服务器。对浏览器而言，为显示一个完整的页面，就需要与一个或多个服务器建立多个HTTP 连接，这些连接具有一定的相关度，如果只是允许其中的一部分连接而拒绝其它相关的连接，则总的浏览可能是无效的，至少是不完整的。从而在接入控制的过程中，要考虑TCP 连接的相关性对接入控制的影响，但本文的重点在连接价格的确定上，所以对此不做详细讨论。
3 连接价格动态调整算法
基于价格实现TCP 接入控制，需要确定一个合理的接入价格，该价格要能够体现用户的接入需求和网络的资源供给之间的关系。本节我们首先针对连接请求确定到达和随机到达两种情况，从理论上探讨最优接入价格的计算方法，然后结合实际网络中用户需求动态变化且难以准确预估的特点，提出根据资源利用率和连接阻塞率，动态调整连接价格的算法思想。
3.1 基本价格计算
假定网络的核心链路带宽为C ，每一连接的期望传输速率为R ，则在某一瞬时网络可接入的连接总数可以记作：R
C C S =)(。 设用户i 的期望连接数为i
D ，效用函数为)(i i D U ，该函数为严格凹的递增函数，则在预算约束i m 下，当i i m p D =?时，用户效用取得最大化。其中p 表示每连接单位时长的价格，i m 表示用户i 在单位时间内愿意支付的费用。
定义网络系统的优化目标为资源约束下的用户总效用最大化，有：
∑)(max i i D U s.t. ∑≤)(C S D i （1） 由于p m D i i =，R C C S =)(，可知：C
m R p i ∑?≥ 又效用函数)(i i D U 为严格凹的递增函数，从而当C m R p i
∑?=时，所有用户的总效用取得最大
化。这说明，若所有用户的预算约束已知，则网络接入点根据链路容量和单位连接的期望传输速率R ，即可设定一个合适的价格p 。在该价格下，用户的实际请求数等于网络能够提供的连接数，I 类、II 类连接阻塞率均为0，在期望的意义下，链路资源得到充分有效的利用。
3.2 连接请求随机到达时的价格计算
上面我们假定所有用户连接请求在同一时刻到达，未考虑用户请求到达的随机性，以及用户的连接时长。实际上用户的连接请求可以看作一个随机过程，假定用户请求到达的时间间隔服从参数为λ的指数分布，连接时长（服务时间）服从均值为τ的任意分布（如重尾分布），则该接入控制和服务系统可以看作是一个M/GI//m/m 排队系统，其中m 表示系统的最大接入容量)(C S ，以下假定其为一固定值，记作0S 。该排队系统的阻塞概率BP （Blocking Probability ）和期望活动连接时长ED （Expected busy connections Duration ）可以分别表示为[6]： ∑====00
000!/!)(S k k S k S S AC P BP ρρ （2）
)1(BP ED ?=ρ （3）
其中，AC （Active Connections ）表示已接入活动连接数，τλρ?=表示连接密度，即单位时间内到达排队系统并要求服务的总连接时长。
这里，排队系统的优化目标体现在两个方面：（1）连接请求阻塞率要尽可能地低（2）期望活动连接时长要尽可能地高。显然这是一个多目标优化问题，通常我们可以在阻塞概率不高于某一设定值的情况下，寻找合适的参数设置，使得单位时间内期望活动连接时长最大化，其理论上限为0S 。
另一方面，根据前面分析，用户i 单位时间内的连接需求（时长）为p
m D i i =，而我们假定每一连接的持续时长服从均值为τ的任意分布，这样单位时间内每一用户的期望连接数i EC （Expected Connections ）可以表示为τ
?=
p m EC i i 。而根据前面假设，单位时间内到达排队系统的平均连接数为λ，于是有： ∑
∑?=?=ττλp m p m i i 从而连接密度p m
i ∑=?=τλρ。这里我们假定所有用户的连接时长独立同分布，与价格变化无关，
价格变化只影响到用户是否发起连接即i EC 的多少。
这样，阻塞概率BP 和期望活动连接时长ED 均可表示为连接价格p 的函数，接入控制问题转化为
最优价格确定问题，即：在阻塞概率BP 不高于某一设定值的情况下，调整每连接单位时间的价格p ，使得单位时间内期望活动连接时长ED 最大化。注意，这里阻塞指的是上述定义中的II 类阻塞。
而根据阻塞率计算公式（2），阻塞概率为连接密度ρ的增函数，又由于ρ与p 成反比p m i ∑=ρ，
故阻塞概率为价格p 的减函数，即价格越高，阻塞率越低。这样，给定可接受的最高阻塞率0BP ，可以计算出最低的价格设置，记作：0p p ≥。在此约束条件下，求解期望活动连接时长最大化问题，可以得到满足目标要求的价格设置*p 。或者，根据可接受的最高阻塞率0BP ，计算出最高流量密度，记作：0ρρ≤。在此约束条件下求解)1(max BP ?ρ，可以得到满足目标要求的连接密度*ρ。再根据
p m
i ∑=ρ关系，计算出最优价格设置*
p 。 3.3 接入价格的动态调整
上面我们假定用户预算约束（愿付费用）确定，以资源利用率（期望活动连接时长）为优化目标，在一定的阻塞率约束下，得到理论上的优化价格设置。但是由于在实际应用中，总的用户数、每一用户的预算约束通常并不为网络所知，用户为取得更大的效用，还有可能动态调整其预算分配，总的连接需求不能够通过一个确定的公式来描述，这时就需要基于上述思想，通过启发式算法，按照一定的时间间隔来动态设置网络接入价格：
（1）根据先验知识，设置价格p 的初值，比如基于预估的用户总预算，按照上述优化方法进行设置。关于用户总预算∑i m 的估计，可以基于公式τλ?=∑p m i 进行，网络接入点统计单位时间内到达的连接请求数λ和每连接的平均持续时长τ，根据不同价格水平下λ和τ的变化做回归分析，得到∑i
m 的估计值。 （2）当网络的实际利用率或接入连接数偏低，而I 类阻塞率偏高时，可以认为之前的网络接入价格设置得偏高，超出了用户的预算接受能力，这时应适当调低价格，以接纳更多的用户连接，并鼓励用户连接需求。
（3）当网络的接入连接数接近于期望提供的连接数，但II 类阻塞率偏高时，可以认为之前的网络接入价格设置得偏低，导致需求过于旺盛，并使得部分预算接受能力比较低的用户连接请求被接入网络，而由于资源被占用，一些愿意接受价格较高的用户被拒绝在网络之外，这时应适当调高价格，抑制用户需求，使得网络能够为出价较高的用户连接服务。
3.4 价格调整对已接入连接的影响
上面我们考虑的是某一新的连接到来后，如何对其实施接入控制，但由于价格是按照一定的时间间隔动态调整的，很多连接要经历多个这样的时间调整间隔，对价格调整之后，已有的连接按照什么样的价格来进行计费，是我们必须要考虑的问题。通常有两种选择：一种是不变，即接入时什么价格就一直
按照这个价格执行，直到连接结束；另一种是变，即实际计费按照当前价格执行，最初的接入价格只适用于连接接入的那个时间段。前一种方法用户的期望支出相对固定，比较为用户所接受，但不能够体现通过价格调整网络资源分配的思想，如果某一用户在价格较低时接入网络并一直保持连接，如某些大的文件传输，则它在网络资源相对紧张时仍以低价格占用网络资源，对其它用户是不公平的，也达不到网络资源分配和拥塞控制的目的。后一种方法定价与计费比较能体现网络当前的使用状况，符合通过网络定价达到资源有效分配的思想，但价格变化过于频繁和动态，会给用户费用支出带来不确定性因素。正如文献[7]所指出的，在连接持续过程中调整价格，往往并不会使用户早一些结束会话，因为他们无法预计这种调整还要持续多长时间。
对此，我们的做法是，在用户连接请求中设置两个价格：Access Price和Keep Price，前者用于接入控制，只有该价格高于当时的连接接入价格，才能够建立起连接；后者用于连接持续过程中的价格控制，当价格低于Keep Price时，保持连接并按照动态调整的价格对连接计费，这样用户要支出的费用仍是可以预期的；而当价格高于Keep Price时，要和用户进行协商，是提高其Keep Price设置，还是断开连接，若用户无确认，可直接断开连接，这取决于用户和网络之间的约定。
4实现方案
上面我们讨论了网络接入点如何确定并动态调整连接接入价格，但是要实现基于价格的TCP接入控制，还须在端用户和网络接入点之间引入必要的价格协商和连接确认环节。本节对可选方案进行分析，并给出基于Socks代理协议的价格协商和接入控制实现方法。
4.1可选方案分析
考虑到端到端的TCP连接建立，通常并不受网络中间节点（如路由器）的控制，为实现基于价格机制的TCP接入控制，需要引入接入控制点，对TCP连接过程进行必要的控制。可采取的做法包括：（1）在网络接入点部署Socks代理，所有端系统的TCP连接都必须经过该代理实现（如通过SocksCap封装），在Socks代理上实现价格的动态调整和接入控制。关于价格如何传递，价格信息如何协商，可以在发起端到接入控制点的Socks连接建立之后，在认证环节引入一个价格协商的过程。而对由会话协议支持的多媒体应用，则可以利用SIP、RTSP等会话协议传递和协商价格信息，并根据这类连接的持续时长进行计费。
（2）Cisco的NAC（Network Admission Control）和Microsoft的NAP（Network Access Protection）等网络接入管理方案，为基于定价的接入控制提供了实现平台。NAC和NAP都属于网络访问管理的范畴，或者说是终端的检疫和隔离。它们要确保终端在接入网络之前必须经过安全配置——有防火墙、防病毒软件、及时更新过的补丁等——否则的话，这个终端就要被隔离。基于定价的接入控制可以利用上述平台提供的API得到实现。
（3）当前有些宽带网络，会在用户首次连接网络时，弹出要求登录的界面。可以利用这样的登录交互过程，通过必要的控件或Applet，在用户和网络间交换价格信息，仅当用户愿意支付的价格高于网络给出的接入价格时，用户的接入认证才算完成。而在随后的连接和数据访问过程中，如果由于接入价格提高导致I类阻塞，也可以通过弹出通知的方式告诉用户，并发起重新协商。
方案（2）和（3）分别需要结合具体的网络访问管理措施和特定运营商的登录认证机制，才能予以部署，局限性较大。而方案（1）中的Socks代理，由于具有独立于特定应用协议的特性，在实际网络中得到了广泛的应用，从而部署起来会更加方便。下面我们就结合Socks代理协议的实现过程，通过扩
充新的验证方式，给出基于价格的TCP接入控制的实现方法。
4.2基于Socks代理协议的实现方案
Socks协议是一种支持Client/Server结构的网络应用穿越防火墙的、通用的应用层网关协议，RFC1928提出的Socks5支持TCP/UDP协议，支持多种验证方式和IPv6协议[8]。Socks协议交互包括三个环节：
（1）客户端建立与Socks Server的TCP连接（一般是1080端口），并协商验证方式，完成用户认证。协议格式为：
Client ? Socks Server：
版本号（1字节）| 支持的验证方式数（1字节）| 验证方式列表（1-255字节）
客户端通过此消息，告知Socks Server它支持哪些验证方式，比如：
0x00 无验证要求
0x02 用户名/口令
0x80 — 0xFE 留作私用
0xFF 无可接受的验证方式
Socks Server ? Client：
版本号（1字节）| 服务器选定的验证方式
Socks Server通过此消息，告知客户端采用何种验证方式。
Client ? Socks Server：
0x01 | 用户名长度（1字节）| 用户名| 口令长度（1字节） | 口令
客户端按照协商好的验证方式（这里以用户名/口令方式为例），向Socks Server发出验证请求。Socks Server ? Client：
0x01 | 验证结果
Socks Serve向客户端返回验证结果，其中0x00 表示验证通过，其它表示出错。
（2）客户端与Socks Server交互连接信息，由Socks Server建立与远端服务器的连接，并维护用于数据转发的地址/端口映射关系。协议格式为：
Client ? Socks Server：
版本号（1字节）| 命令（1字节）| 保留（0x00）| 地址类型（1字节）| 目的地址（根据地址类型取不同长度）| 目的端口（2字节）
客户端向Socks Server发出命令请求，Socks Server根据该请求建立到目的服务器的连接，或是建立地址/端口映射，并向客户端返回响应，其中命令目前支持以下三种：
0x01 CONNECT 建立到目的地址/端口的TCP连接
0x02 BIND 指示Socks Server在相关端口等待服务器方的连接
0x03 UDP ASSOCIATE 建立UDP数据转发的映射关系
Socks Server ? Client：
版本号（1字节）| 响应（1字节）| 保留（0x00）| 地址类型（1字节）| 绑定地址（根据地址类型取不同长度）| 绑定端口（2字节）
Socks Server向客户端返回响应，其中0x00 表示命令成功执行，其它表示出错。
（3）完成实际的命令和数据转发。Socks代理与其它应用层代理如HTTP、FTP、RTSP代理不同，它
只是简单地转发数据包，而不关心是何种应用协议。
从Socks协议的交互过程可以看出，其用户验证环节能够为价格传递和协商提供一定支持。具体来说，可以扩展定义新的验证方式，在验证交互的过程中，要求客户端提供其愿意支付的价格等信息，Socks Server根据基于价格的接入控制策略，决定用户能否接入及验证是否成功。参考Socks5协议规范，在用户名/口令验证方式的基础上，我们定义如下验证方式：
0xF1 基于价格的接入验证
采用该验证方式，客户端需向Socks Server发出如下格式的验证请求消息：
0x01 | 用户名长度（1字节）| 用户名 | 口令长度（1字节） | 口令 | 价格长度（1字节）| 愿意支付的价格
Socks Server在收到客户端的验证消息后，按以下顺序进行用户身份验证和接入控制处理：
（1）若用户名/口令不对，则返回如下验证结果：
0x01 用户名/口令出错
（2）若用户愿意支付的价格低于网络接入价格（I类阻塞），则返回：
0x02 用户愿意支付的价格低于网络接入价格
（3）若当前网络处于拥塞状况，接入的用户连接数已经达到网络可接纳的值（II类阻塞），则返回：0x03 接入的用户连接数已经达到网络可接纳的值
（4）若上述各项检查均已通过，则返回：
0x00 验证通过，进入下一步协议交互
上述支持价格传递和协商的Socks协议交互过程，可用于实现本文提出的基于价格的TCP接入控制，其时序图描述如下：
图 1 基于Socks协议的价格协商和认证过程
5结束语
本文面向TCP连接类应用，探讨了基于价格的接入控制思想，并针对连接请求确定到达和随机到达两种情况，从理论上探讨了最优接入价格的计算方法。结合实际网络中用户需求动态变化且难以准确预估的特点，提出了根据资源利用率和连接阻塞率，动态调整连接价格的算法思想，并分析了价格调整对已接入连接的影响。在此基础上，给出了基于Socks代理协议的价格协商和接入控制实现方法。这种基于价格的接入控制思想，对有会话控制协议（如SIP、RSTP）支持的多媒体服务的接入控制具有同样的借鉴意义。
参考文献
[1] Allman M, Paxson V, Stevens W. TCP Congestion Control [S]. RFC2581, April 1999
[2] Floyd S, Fall K. Promoting the Use of End-to-End Congestion Control in the Internet [J]. IEEE/ACM
Transactions on Networking, August 1999, 7(4): 458-472
[3] Shu J, Varaiya P. Pricing network services [A]. IEEE INFOCOM’03, March 2003, 22(1): 1221-1230
[4] Schenk R. Cyber Economics [EB/OL]. https://www.doczj.com/doc/f514311240.html,/econ/TOC.html, 1998
[5] Mackie-Mason J, Murphy J, Murphy L. The Role of Responsive Pricing in the Internet [M]. L. W.
McKnight and J. P. Bailey, Eds., Cambridge, Massachusetts: MIT Press, 1997
[6] Keon N, Anandalingam G. Optimal Pricing for Multiple Services in Telecommunications Networks
Offering Quality-of-Service Guarantees [J]. IEEE/ACM Transactions on Networking, February 2003, 11(1): 66-80
[7] Shih J, Katz R, Joseph A. Pricing experiments for a computer-telephony-service usage allocation [A].
IEEE GLOBECOM’01, Nov 2001, 2450-2454
[8] Leech M, Ganis M, Lee Y, etc. SOCKS Protocol Version 5 [S]. IETF RFC1928, March 1996
Dynamic Connection-Oriented Pricing for TCP Admission Control
Dong Yongqiang, Huang Yiming
School of Computer Science and Engineering, Southeast University, Nanjing 210096, China Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of
Education, Nanjing 210096, China
Abstract: Admission control and pricing for connection-oriented elastic traffic are concerned. TCP admission control is depicted as a multi-objective optimization problem with blocked ratio minimization and active connection duration maximization as objectives. Assuming the connection request arrivals are determinate and stochastic respectively, the methods on how to price TCP connections are discussed. Then a dynamic pricing algorithm is examined which approaches the maximum of active connection duration while assuring the blocked ratio at acceptable level. Furthermore a price negotiation scheme based on Socks protocol is presented which can bring the pricing algorithm into practical networks.
Keywords: Admission control, network pricing, blocked ratio, active duration, Socks protocol
作者简介：董永强（1973-），男，博士研究生，主要研究方向为网络资源分配、拥塞控制、多媒体通信等，E-mail: dongyq@https://www.doczj.com/doc/f514311240.html,
毕业设计(论文) TCP协议中的流量控制和拥塞控制研究 院别数学与统计学院 专业名称信息与计算科学 班级学号 学生姓名 指导教师 年月日
TCP协议中的流量控制和拥塞控制研究 摘要 计算机网络技术是当今发展最迅速的计算机技术之一，而保证网络稳定可靠运行的关键是计算机网络协议。TCP协议作为网络协议中的核心协议之一，其重要性更是不言而喻，因而对于该协议的研究与完善是促进网络发展的重要手段之一。 随着互联网规模和互联网应用的快速增长，网络拥塞和数据冲突问题已引起人们密切的关注。拥塞控制与流量控制技术针对网络中的拥塞和数据冲突而成为网络领域的核心技术。其中流量控制的对象是接收端，目的是使发送端的发送速率不超过接收端的接收能力；拥塞控制的对象是网络环境，目的是使负载不超过网络的传送能力。 TCP的流量控制主要依赖于滑动窗口，通过流量约束，减少接收端出的数据流失，提高发送效率，充分利用接收端资源。 TCP的拥塞控制主要原理依赖于一个拥塞窗口(cwnd)来控制，窗口值的大小就代表能够发送出去的但还没有收到ACK的最大数据报文段，显然窗口越大那么数据发送的速度也就越快，但是也就越可能使得网络出现拥塞，如果窗口值为1，那么就简化为一个停等协议，每发送一个数据，都要等到对方的确认才能发送第二个数据包，显然数据传输效率低下。TCP拥塞控制算法就是要在这两者之间权衡，选取最的cwnd值，从而使得网络吞吐量最大化且不产生拥塞。 本文首先对TCP协议的发展做了简要的概述，然后分析了TCP协议的报文段格式和结构，TCP的数据传输过程，接着讨论了TCP的流量控制机制，最后针对TCP 的重点部分拥塞控制进行了分析，讨论了几个TCP拥塞控制算法。 关键词：TCP协议，流量控制，拥塞控制
TCP拥塞控制算法性能比较 一、NS2仿真 1.仿真实验的网络结构图 如图所示0、1、2为源节点，3为路由器，4为目的节点。源节点0、1、2为TCP代理节点，频宽为8Mbps，传递延迟时间为0.1ms，仿真时使用FTP流量。路由器的队列管理机制使用DropTail，频宽为0.8Mbps，传递延迟为100ms。在这个实验中建立3条TCP数据流，0和4、1和4、2和4。在OTCL编码中，代理节点的协议代理分别设置为TCP/Reno、TCP/Newreno、TCP/Sack1和tcp/Vegas，来模拟这四种算法。 二、模拟结果与算法分析比较 1、模拟拥塞控制四种算法的cwnd变换图：
2、TCP拥塞控制的四个阶段 这是TCP拥塞控制的核心，也体现了TCP拥塞控制的基本思想，它分为启动阶段，拥塞避免，快速重传和快速恢复阶段。 (1) 启动阶段 当连接刚建立或在发生一次超时的情况下，进入慢启动阶段。 一个新的TCP连接建立后，cwnd被初始化为1，源端只被允许发送一个报文段。当发出的报文收到接受端的ACK确认后，cwnd加1，即增加一个报文段发送。在这个阶段中，cwnd随RTT呈指数增长。 采用慢启动方法，可以防止TCP在启动一个新的连接时发送过多的数据而造成数据丢失和网络拥塞，同时，由于cwnd实际上以指数规律增长也就避免了单纯的AIMD算法造成的吞吐量增加过慢的问题。 cwnd的无限增长必将引起网络拥塞，于是引入一个状态变量：慢启动阈值ssthresh。 当cwnd
TCP拥塞控制算法比较 TCP发展到现在已经形成了TCP Tahoe、TCP Reno、TCP NewReno、SACK、Vegas等不同版本，这些算法各有利弊。 Tahoe算法是TCP的早期版本。它的核心思想是：让cwnd以指数增长方式迅速逼近可 用信道容量，然后慢慢接近均衡。它包括了3个基本的拥塞控制算法：慢启动、拥塞避免、快速重传。Tahoe的缺点体现在快速重传后转向慢启动算法，这样不能有效的利用网络带宽并且还引入较大的延时。 Reno算法是针对Tahoe算法的不足而做的改进。改进主要有两方面：一是对于收到连 续3个重复的ACK确认，算法不经过慢启动，而直接进入拥塞避免阶段；二是增加了快速重传和快速恢复机制。Reno算法以其简单、有效和鲁棒性成为TCP源算法的主流，被广泛的 采用。但它不能有效的处理多个报文分组从同一发送窗口中丢失的情况。 NewReno对Reno中快速恢复算法进行了补充，它考虑了一个发送窗口内多个报文分组 同时丢失的情况。Reno算法中，发送方收到一个不重复的应答后就退出快速恢复，而NewReno 中，只有当所有的报文分组都被应答后才退出快速恢复状态。NewReno的实现只要修改TCP 发送端的实现代码，实现简单。 SACK算法也针对一个窗口内多个报文分组丢失的情况而对Reno算法进行改进：SACK 定义了一个变量pipe来表示出现在路由器上报文分组的估计数量，接收方TCP发送SACK 分组来通知发送方的接收状况，这样源端就能准确的知道哪些报文分组被正确的传到接收端，从而避免不必要的重传，提高网络吞吐量。但SACK算法的实现需要修改TCP发送端和接收端的实现代码，增加了TCP的复杂性，因此不易大规模的应用。 Vegas与上述的算法不同，它是以RTT的变化作为拥塞信号，调节源端的发送速率。通过监测RTT的变化来改变cwnd的大小。由于Vegas采用RTT的改变来判断网络的可用带宽，能较好的预测网络带宽的使用情况，其公平性、效率都较好。但是，由于Vegas与其它算法在竞争带宽方面存在不公平现象，因此未能在因特网中普遍采用，还需要继续改进。
TCP 拥塞控制分析 摘要：随着计算机网络的飞速发展，网络用户数量急剧增加，Internet 在各个领域也发挥越来越重要的作用，但随着其流量的急剧增加，由此引发的网络拥塞已经成为制约网络发展和应用的瓶颈问题。拥塞容易造成传输延迟和吞吐量等性能指标的下降，严重影响带宽、缓存等网络资源的利用率。TCP 作为应用最广泛的传输协议，它的拥塞控制已经成为其成功的关键。本文针对这一现象对TCP 性能及拥塞控制进行研究，我们将简单探讨网络拥塞出现的原因，着重介绍TCP 拥塞控制的原理并分析四个TCP 拥塞控制算法，最后论述TCP 拥塞控制所面临的问题，根据此提出进一步的研究方向。 关键词：TCP 拥塞、拥塞控制、TCP Tahoe 、TCP Reno 、TCP SACK 、TCP Vegas 1. 拥塞产生的原因 拥塞是一种持续过载的网络状态，此时用户对网络资源（包括链路带宽，存储空间和处理器的处理能力等）的需求超过了其固有的容量。拥塞导致的直接结果就是分组丢失率增加，端到端延时加大，甚至有可能使整个系统发生崩溃。 网络产生拥塞的根本原因在于用户或端系统提供给网络的负载大于网络资源容量和处理能力，即网络提供的资源不足以满足用户的需求，这些资源包括缓存空间、链路带宽容量和中间结点的处理能力等，使其产生数据包时延增加、丢弃概率增大、上层应用系统性能显著下降等典型现象。拥塞产生的直接原因有三点： （1）存储空间不足。缓存的容量不够大，当缓存已经装满，没有空闲的空间时就只能将新到达的分组丢弃。 （2）带宽容量不足，低速链路对高速数据流的输入也会产生拥塞。任何信道带宽最大值为()N +B =S C 1log 2(N 为信道噪声平均功率，S 为信源平均功率，B 为信道带宽) [1]。 要求所有信源发送的速率R 必须小于等于信道容量C 。 （3）处理器处理能力弱，速度慢。低速链路对高速CPU 也会产生拥塞。 要避免拥塞的发生，必须对链路带宽、路由器处理速度和存储容量等问题予以考虑，尽可能使系统的各个部分相互匹配。但由于网络流量分布的不均衡性，随着用户数量和
拥塞控制（congestion control)是TCP协议的一项重要功能，TCP 的拥塞控制机制是从端到端的角度，推测网络是否发生拥塞，如果推断网络发生拥塞，则立即将数据发送速率降下来，以便缓解网络拥塞。TCP的拥塞控制采用的是窗口机制，通过调节窗口的大小实现对数据发送速率的调整。TCP的发送端维持一个称为拥塞窗口cwnd的变量，单位为字节，用于表示在未收到接收端确认的情况下，可以连续发送的数据字节数。cwnd的大小取决于网络的拥塞程度，并且动态地发生变化。拥塞窗口调整的原则是：只要网络没有出现拥塞，就可以增大拥塞窗口，以便将更多的数据发送出去，相当于提高发送速率；一旦网络出现拥塞，拥塞窗口就减小一些，减少注入网络的数据量，从而缓解网络的拥塞。 发送端判断网络发生拥塞的依据是：发送端设置一个重传计时器RTO，对于某个已发出的数据报文段，如果在RTO计时到期后，还没有收到来自接收端的确认，则认为此时网络发生了拥塞。 TCP的拥塞控制算法包括了慢启动（slow start）、拥塞避免（congestion avoidance）、快速重传（fast retransmit）和快速恢复（fast recovery）四部分。 慢启动算法作用在TCP数据传输的开始阶段，当主机开始发送数据时，因为不知道网络中的负荷情况，如果立即发送大量的数据，有可能会引起网络的拥塞。因此，TCP采用试探的方法，逐渐增大拥塞窗
口。通常在刚开始发送数据报文段时，先将拥塞窗口cwnd设置为一个TCP最大段长度MSS的值。而在每收到一个数据报文段的确认后，cwnd就增加一个MSS的数值。这样就可以逐渐增大发送端的拥塞窗口，使数据注入网络的速率比较合理。如果定义从发送端发出一个数据报文段到收到这个数据报文段的确认的时间间隔为往返时间RTT，则在慢启动阶段，每经过一个RTT，cwnd的值就加倍。 为了防止拥塞窗口增长过快而引起网络拥塞，TCP还需要设置一个慢启动阈值ssthresh，当拥塞窗口的值增加到ssthresh时，就要减缓拥塞窗口的增长速度，具体的做法是每经过一个RTT，拥塞窗口cwnd 的值加1（单位为MSS），这样就可以使cwnd按线性规律缓慢增长，这个过程称之为“加性增加”（Additive Increase）算法。通常情况下，拥塞窗口cwnd的初值被设置为1，慢启动阈值ssthresh的初值被设置为16。当拥塞避免算法执行到某个时刻，发送端在规定时间内没有收到接收端的确认，即发生了网络超时，则意味着网络发生了拥塞。此时，发送端首先将ssthresh的值变为发生超时时cwnd值的一半，同时将cwnd的值置为1，重新执行慢启动算法。这样做的好处是，当网络频繁出现拥塞时，ssthresh下降得很快，可以大大减少注入网络中的数据报文段。通常称这个过程为“乘性减小”（MultiplicativeDecrease）算法。TCP中的“加性增加”和“乘性减小”算法合起来称为AIMD算法。
TCP协议拥塞控制算法研究 摘要：自从1986年互联网出现严重的拥塞崩溃现象后，网络拥塞控制受到了广泛的关注。随着网络的不断发展，网络用户及需求急剧增加，网络拥塞也越来越严重。如何有效解决网络拥塞，成为人们急需解决的问题。TCP作为目前互联网上使用最广泛的一种传输协议，TCP拥塞控制机制对互联网的稳定运行起着重要的作用。本文阐述了TCP的拥塞控制机制以及几种TCP拥塞控制算法，并对它们进行了仿真，比较了他们各自的优缺点，并指出了进一步改进TCP拥塞控制的必要性。 关键字：互联网；TCP；拥塞控制 Abstract：Since the advent of the Internet congestion collapse in 1986, network congestion control has been widespread concern. With the continuous development of the network, network users and the demand are increasing rapidly, network congestion has become increasingly serious. How to effectively solve network congestion become an urgent problem. TCP currently used on the Internet as the most widely used transport protocol, TCP congestion control mechanisms for the stable operation of the Internet plays an important role. This paper describes the TCP congestion control mechanisms as well as several TCP congestion control algorithms, and their simulation to compare their advantages and disadvantages, and pointed out the need for further improvement of TCP congestion control. Keywords：Internet；TCP；Congestion control 1 引言 近年来以IP为基础的internet呈爆炸式增长，网络用户数量迅速增加，internet 在各个领域也发挥着越来越重要的作用，但随着其流量急剧增加，由此而引发的网络拥塞已经成为制约网络发展和应用的瓶颈问题。在计算机网络中的宽带、交换节点中的缓存和处理机等，都是网络资源。如果网络相对于负载需求表现为节点存储空间不足、链路带宽不足、处理器处理速度慢，以及系统各部分性能不匹配等等，从而导致网络上的包时延增加，丢包率上升，吞吐量下降，直接使服务质量下降。概括来说就是在某一时间段里，如果网络中的某一资源的需求量超过了该网络所能提供的网络资源的可用部分，网络的性能就能变坏。诸如网络延时
TCP拥塞控制四个主要过程（如图（a）和（b）所示）简要介绍如下： 图（a）：慢启动和拥塞避免图（b）：快速重传和快速恢复 1.慢启动阶段：早期开发的TCP应用在启动一个连接时会向网络中发送大量的数据包，这样 很容易导致路由器缓存空间耗尽，网络发生拥塞，使得TCP连接的吞吐量急剧下降。由于TCP源端无法知道网络资源当前的利用状况，因此新建立的TCP连接不能一开始就发送大量数据，而只能逐步增加每次发送的数据量，以避免上述现象的发生。具体地说，当建立新的TCP连接时，拥塞窗口（congestion window，cwnd）初始化为一个数据包大小。源端按 cwnd大小发送数据，每收到一个ACK确认，cwnd就增加一个数据包发送量，这样cwnd就将随着回路响应时间（Round Trip Time，RTT）呈指数增长，源端向网络发送的数据量将急剧增加。事实上，慢启动一点也不慢，要达到每RTT发送W个数据包所需时间仅为 RTT×logW。由于在发生拥塞时，拥塞窗口会减半或降到1，因此慢启动确保了源端的发送速率最多是链路带宽的两倍。 2.拥塞避免阶段：如果TCP源端发现超时或收到3个相同ACK副本时，即认为网络发生了拥 塞（主要因为由传输引起的数据包损坏和丢失的概率很小（<<1%））。此时就进入拥塞避免阶段。慢启动阈值（ssthresh）被设置为当前拥塞窗口大小的一半；如果超时，拥塞窗口被置1。如果cwnd>ssthresh，TCP就执行拥塞避免算法，此时，cwnd在每次收到一个ACK时只增加1/cwnd个数据包，这样，在一个RTT内，cwnd将增加1，所以在拥塞避免阶段，cwnd 不是呈指数增长，而是线性增长。 3.快速重传和快速恢复阶段：快速重传是当TCP源端收到到三个相同的ACK副本时，即认为 有数据包丢失，则源端重传丢失的数据包，而不必等待RTO超时。同时将ssthresh设置为当前cwnd值的一半，并且将cwnd减为原先的一半。快速恢复是基于“管道”模型（pipe model）的“数据包守恒”的原则（conservation of packets principle），即同一时刻在网络中传输的数据包数量是恒定的，只有当“旧”数据包离开网络后，才能发送“新”数据包进入网络。如果发送方收到一个重复的ACK，则认为已经有一个数据包离开了网络，于是将拥塞窗口加1。如果“数据包守恒”原则能够得到严格遵守，那么网络中将很少会发生拥塞；本质上，拥塞控制的目的就是找到违反该原则的地方并进行修正。 经过十多年的发展，目前TCP协议主要包含有四个版本：TCP Tahoe、TCP Reno、TCP NewReno 和TCP SACK。TCP Tahoe是早期的TCP版本，它包括了3个最基本的拥塞控制算法－“慢启动”、“拥塞避免”和“快速重传”。TCP Reno在TCP Tahoe基础上增加了“快速恢复”算法。TCP NewReno对TCP Reno中的“快速恢复”算法进行了修正，它考虑了一个发送窗口内多个数据包丢失的情况。在Reno 版中，发送端收到一个新的ACK后旧退出“快速恢复”阶段，而在NewReno版中，只有当所有的数据包都被确认后才退出“快速恢复”阶段。TCP SACK关注的也是一个窗口内多个数据包丢失的情况，它避免了之前版本的TCP重传一个窗口内所有数据包的情况，包括那些已经被接收端正确接收的数据包，而只是重传那些被丢弃的数据包。
分析TCP的拥塞控制原理 TCP是Transmission Control Protocol的缩写，即传输控制协议，它对应于OSI七层模型中的传输层，建立于网络层之上。TCP旨在给互联网提供一种可*的端到端的字节传输流。 自从1988年问世以来，TCP在研究者的努力下先后得到了许多新的发展，目前主要的模型包括四个，即TCP TAHOE，TCP RENO，TCP NEWRENO和TCP SACK。TCP TAHOE 模型是最早的TCP协议之一，它由Jacobson提出。Jacobson观察到，TCP报文段（TC P Segment）丢失有两种原因，其一是报文段损坏，其二是网络阻塞，而当时的网络主要是有线网络，不易出现报文段损坏的情况，网络阻塞为报文段丢失的主要原因。针对这种情况，TCP TAHOE对原有协议进行了性能优化，其特点是，在正常情况下，通过重传计时器是否超时和是否收到重复确认信息（dupack）这两种丢包监测机制来判断是否发生丢包，以启动拥塞控制策略；在拥塞控制的情况下，采用慢速启动（Slow Start）算法和快速重传（Fast Retransmit）算法来控制传输速率。 在试验中，我们以TCP TAHOE模型为例，对TCP的拥塞控制原理进行分析，包括两种丢包监测机制和拥塞控制中的慢速启动算法和快速重传算法。 1. TCP拥塞控制相关技术简介 1.1 慢速启动算法 在TCP TAHOE模型中，拥塞控制主要是通过调整发送端的发送速率，而这又主要是通过三个变量实现的：拥塞窗口（Congestion Window），接收端窗口（Receivers’s W indow），慢速启动阈值（Slow Start Threshold，SSTHRESH）。发送端一旦监测到数据包丢失（其原因可能是重传计时器超时，亦可能是收到重复的ACK信令），它就会开始调整发送速率。这包括，ssthresh调整为当前拥塞窗口的一半，同时拥塞窗口将降低到1个报文段。然后，随着通信过程的恢复，拥塞窗口持续增长。在拥塞窗口大小未达到ssthresh之前，它以指数速度增长；到达之后则开始线性增长。有趣的是，虽然这种算法称为慢速启动算法，但实际上一点儿也不慢，它是指数增长的。 1.2 快速重传算法 当发送端连续收到3个对应于同一个序列号的ACK信令时，就触发了其快速重传算法，即发送端不等重传计时器超时，立即向接收端发送指定的报文段。 1.3 丢包检测机制有如下两种 (1). 重复ACK信令 重复ACK有两个作用，其一，发送端可以确信该ACK序列号之前的TCP报文段都已经被接收端成功接收；其二，发送端可以据此判断出接收端接收到的TCP报文段发生了乱序的情况和接收端当前期待的TCP报文段序列号，从而触发其拥塞控制策略。
TCP拥塞控制算法性能比较 1011010409 秦树东 1、NS2仿真 仿真实验的网络结构图 如图所示0、1、2为源节点，3为路由器，4为目的节点。源节点0、1、2为TCP代理节点，频宽为8Mbps，传递延迟时间为0.1ms，仿真时使用FTP流量。路由器的队列管理机制使用DropTail，频宽为0.8Mbps，传递延迟为100ms。在这个实验中建立3条TCP数据流，0和4、1和4、2和4。在OTCL编码中，代理节点的协议代理分别设置为TCP/Reno和TCP/Vegas，来模拟这两种算法。 2、模拟结果与算法分析比较 1、模拟拥塞控制TCP Reno算法的cwnd变换图：
TCP Reno Tcl代码如下： #产生一个仿真对象 set ns [new Simulator] #开启一个trace文件，用来记录封包传送过程 set nd [open out.tr w] $ns trace-all $nd #开启3个文件用来记录3条TCP Connection的cwnd变化情况set f0 [open cwnd0.tr w] set f1 [open cwnd1.tr w] set f2 [open cwnd2.tr w] #定义一个结束程序 proc finish {} { global ns nd f0 f1 f2 $ns flush-trace #关闭文件 close $nd close $f0 close $f1 close $f2
exit 0 } #定义一个记录的程序 #每隔0.01s记录当时的cwnd proc record {tcp_} { global ns f0 f1 f2 upvar $tcp_ tcp set now [$ns now] puts $f0 "$now [$tcp(0) set cwnd_]" puts $f1 "$now [$tcp(1) set cwnd_]" puts $f2 "$now [$tcp(2) set cwnd_]" $ns at [expr $now+0.01] "record tcp" } #设置路由节点 set r0 [$ns node] #设置目的节点 set d0 [$ns node] #路由与目的节点的链路属性 $ns duplex-link $r0 $d0 0.8Mb 100ms DropTail $ns queue-limit $r0 $d0 64 for {set i 0} {$i < 3} {incr i} { #设置源节点 set s($i) [$ns node] set d($i) [$ns node] $ns duplex-link $s($i) $r0 8Mb 0.1ms DropTail #设置代理 set tcp($i) [new Agent/TCP/Reno] set tcpsink($i) [new Agent/TCPSink] $ns attach-agent $s($i) $tcp($i) $ns attach-agent $d0 $tcpsink($i) $ns connect $tcp($i) $tcpsink($i) $tcp($i) set fid_ $i
TCP拥塞控制算法 为了防止网络的拥塞现象，TCP提出了一系列的拥塞控制机制。最初由V. Jacobson在1988年的论文中提出的TCP的拥塞控制由“慢启动(Slow start)”和“拥塞避免(Congestion avoidance)”组成，后来TCP Reno版本中又针对性的加入了“快速重传(Fast retransmit)”、“快速恢复(Fast Recovery)”算法，再后来在TCP NewReno中又对“快速恢复”算法进行了改进，近些年又出现了选择性应答( selective acknowledgement,SACK)算法，还有其他方面的大大小小的改进，成为网络研究的一个热点。 TCP的拥塞控制主要原理依赖于一个拥塞窗口(cwnd)来控制，在之前我们还讨论过TCP还有一个对端通告的接收窗口(rwnd)用于流量控制。窗口值的大小就代表能够发送出去的但还没有收到ACK的最大数据报文段，显然窗口越大那么数据发送的速度也就越快，但是也有越可能使得网络出现拥塞，如果窗口值为1，那么就简化为一个停等协议，每发送一个数据，都要等到对方的确认才能发送第二个数据包，显然数据传输效率低下。TCP的拥塞控制算法就是要在这两者之间权衡，选取最好的cwnd值，从而使得网络吞吐量最大化且不产生拥塞。 由于需要考虑拥塞控制和流量控制两个方面的内容，因此TCP的真正的发送窗口=min(rwnd, cwnd)。但是rwnd是由对端确定的，网络环境对其没有影响，所以在考虑拥塞的时候我们一般不考虑rwnd的值，我们暂时只讨论如何确定cwnd值的大小。关于cwnd的单位，在TCP中是以字节来做单位的，我们假设TCP 每次传输都是按照MSS大小来发送数据的，因此你可以认为cwnd按照数据包个数来做单位也可以理解，所以有时我们说cwnd增加1也就是相当于字节数增加1个MSS大小。 慢启动：最初的TCP在连接建立成功后会向网络中发送大量的数据包，这样很容易导致网络中路由器缓存空间耗尽，从而发生拥塞。因此新建立的连接不能够一开始就大量发送数据包，而只能根据网络情况逐步增加每次发送的数据量，以避免上述现象的发生。具体来说，当新建连接时，cwnd初始化为1个最大报文段(MSS)大小，发送端开始按照拥塞窗口大小发送数据，每当有一个报文段被确认，cwnd就增加1个MSS大小。这样cwnd的值就随着网络往返时间(Round Trip Time,RTT)呈指数级增长，事实上，慢启动的速度一点也不慢，只是它的起点比较低一点而已。我们可以简单计算下： 开始 ---> cwnd = 1 经过1个RTT后 ---> cwnd = 2*1 = 2 经过2个RTT后 ---> cwnd = 2*2= 4 经过3个RTT后 ---> cwnd = 4*2 = 8 如果带宽为W，那么经过RTT*log2W时间就可以占满带宽。 拥塞避免：从慢启动可以看到，cwnd可以很快的增长上来，从而最大程度利用网络带宽资源，但是
题目：TCP拥塞控制与方法改进 摘要 如今网络已经离不开人们的生活，发展势头迅猛，网络的终端设备不仅在数量上，种类也越来越多，在此发展之下，保证大量的网络数据传输与网络性能相协调是极其重要的，经典的TCP拥塞控制机制是网络发展历史中人们想出的一种解决网络拥塞的方法，但如何适应当今网络发展的需求相信还是靠人们不断的探索来寻找合适的答案。本文致力于对经典TCP拥塞控制机制的讨论并提出相应的改进思路。 关键字：拥塞控制；慢启动；阈值；TCP拥塞窗口；数据包
一、概述 1.1TCP网络拥塞控制 TCP 是因特网中使用最广泛的一种传输协议，它是一种面向连接（连接导向）的、可靠的、基于字节流的运输层（Transport layer）通信协议，之所以应用广泛一大部分是由于它的可靠性、稳定性，它为通信的双方提供了可靠的端到端的服务，而实现这一可靠服务的便是TCP 所具有的可靠传输机制，其中包括重传、序号、确认号、定时、流量控制及拥塞控制。 当网络中存在过多的数据包时，网络的性能就会下降，这种现象称为拥塞。拥塞导致的直接后果是分组丢失率增加，端到端延迟加大，甚至有可能使整个系统发生崩溃。1986年10月,由于拥塞崩溃的发生，美国LBL到UC Berkeley的数据吞吐量从32Kbps跌落到4obps(Jacobsonv,1958)。当网络处于拥塞崩溃状态时，微小的负载增量都将使网络的有效吞吐量(Goodput)急剧下降。 图1-1吞吐量和负载的关系图 图1.1描述了网络负载和吞吐量之间的关系。当负载较小时，吞吐量的增长和负载相比基本成线性关系，延迟增长缓慢;在负载超过Knee点后，吞吐量增长缓慢,延迟增长较快;当负载超过Cliff点之后,吞吐量急剧下降，延迟急剧上升。通常将Knee点附近称为拥塞避免区间；Knee到Cliff之间是拥塞恢复区间；Cliff 之外是拥塞崩溃区间。可以看出,负载在肠ee附近时网络的使用效率最高。
NS-2实践：分析TCP的拥塞控制原理 作者：何坚(来源：赛迪网) https://www.doczj.com/doc/f514311240.html,2005年07月05日 之前我曾经给大家介绍了如何安装网络模拟器NS-2，如何安装移动IPv6快速切换协议的扩展，以及如何使用NAM和XGRAPH对试验结果进行分析（请参见《NS-2实践：在NS-2环境下模拟移动IPv6的快速切换》）。这篇文章中，我将在上篇文章的基础上，给大家详细介绍如何利用XGRAPH来分析TCP的拥塞控制原理。 TCP是Transmission Control Protocol的缩写，即传输控制协议，它对应于OSI七层模型中的传输层，建立于网络层之上。TCP旨在给互联网提供一种可靠的端到端的字节传输流。 自从1988年问世以来，TCP在研究者的努力下先后得到了许多新的发展，目前主要的模型包括四个，即TCP TAHOE，TCP RENO，TCP NEWRENO和TCP SACK。TCP TAHOE模型是最早的TCP协议之一，它由Jacobson 提出。Jacobson观察到，TCP报文段（TCP Segment）丢失有两种原因，其一是报文段损坏，其二是网络阻塞，而当时的网络主要是有线网络，不易出现报文段损坏的情况，网络阻塞为报文段丢失的主要原因。针对这种情况，TCP TAHOE对原有协议进行了性能优化，其特点是，在正常情况下，通过重传计时器是否超时和是否收到重复确认信息（dupack）这两种丢包监测机制来判断是否发生丢包，以启动拥塞控制策略；在拥塞控制的情况下，采用慢速启动（Slow Start）算法和快速重传（Fast Retransmit）算法来控制传输速率。 在试验中，我们以TCP TAHOE模型为例，对TCP的拥塞控制原理进行分析，包括两种丢包监测机制和拥塞控制中的慢速启动算法和快速重传算法。 1. TCP拥塞控制相关技术简介 1.1 慢速启动算法 在TCP TAHOE模型中，拥塞控制主要是通过调整发送端的发送速率，而这又主要是通过三个变量实现的：拥塞窗口（Congestion Window），接收端窗口（Receivers’s Window），慢速启动阈值（Slow Start Threshold，SSTHRESH）。发送端一旦监测到数据包丢失（其原因可能是重传计时器超时，亦可能是收到重复的ACK信令），它就会开始调整发送速率。这包括，ssthresh调整为当前拥塞窗口的一半，同时拥塞窗口将降低到1个报文段。然后，随着通信过程的恢复，拥塞窗口持续增长。在拥塞窗口大小未达到ssthresh之前，它以指数速度增长；到达之后则开始线性增长。有趣的是，虽然这种算法称为慢速启动算法，但实际上一点儿也不慢，它是指数增长的。 1.2 快速重传算法 当发送端连续收到3个对应于同一个序列号的ACK信令时，就触发了其快速重传算法，即发送端不等重传计时器超时，立即向接收端发送指定的报文段。 1.3 丢包检测机制有如下两种 (1). 重复ACK信令 重复ACK有两个作用，其一，发送端可以确信该ACK序列号之前的TCP报文段都已经被接收端成功接收；其二，发送端可以据此判断出接收端接收到的TCP报文段发生了乱序的情况和接收端当前期待的TCP报文段序列号，从而触发其拥塞控制策略。 (2). 超时重传 发送端发出报文段后，在规定的时间内没有能够收到接收端返回的ACK信令，从而使得发送端认为该报文段丢失，触发其拥塞控制策略。在这里面主要涉及到重传计时器（retransmission timer），它是TCP协议中最重要的计时器。根据《Computer Networks, Fourth Edition》，当报文段发出后，重传计时器立即启动，如果发送端在计时
也是总结的时候了，写完了TCP的多个经典的拥塞算法，但是由于这方面的优化算法还有很多，没办法能够一一讲完，所以下面对其他的一些比较典型的也进行一个简单的介绍：Fast TCP: Fast TCP由于后来没有对开源界做贡献了，因为作者本人自己创办了公司，把Fast TCP变成了商业产品，所以后续的学术研究就比较少了。Fast TCP是从 TCP vegas的思想发展而来，利用网络延时进行拥塞判断。之前讨论过，基于延迟的算法是对整个网络的拥塞控制有好处的，但是和当前的基于丢包的算法来说两者不公平。所以估计作者后面也做了很多的改进。 ECN：显式拥塞通知，该算法的思想是想借助路由器，因为拥塞的状况中间的路由器是最清楚的，所以让路由器在发现有拥塞现象时在连接的TCP或者IP头里面打上拥塞的标记，让终端自己去根据标记进行处理。这种思想需要中间所有的路由设备均能支持才能在整个广域网上使用起来，所以推广起来不是那么容易的事情。目前Win7、Linux均都已支持ECN 标记的处理。 UDT：UDT是一个开源的基于UDP实现的可靠传输协议，对于想知道如何去实现一个可靠的传输协议可以说值得参考。严格地来说UDT没有对TCP进行优化，不能算是一种TCP 的优化，但是在UDT里面实现的拥塞算法是和UDP或TCP没有关系的，UDT采用的是一种带宽估计的算法，在利用包对进行带宽的探测，然后由接收方把估计的带宽反馈到发送端，发送端的拥塞算法就是把拥塞窗口利用一个函数无限逼近于带宽值，这种思想对于传输的稳定性非常好，因为是一个无限逼近，所以永远不会超过带宽的值，而不是像TCP一样在平衡状态后继续一直往上增大窗口，从而在平衡状态能够维持比较久。但是缺点也显而易见，带宽的估计不是特别的精确，尤其是在小带宽环境和有丢包的环境下误差有点大，当然我们需要明白作者开发UDT的需求不是为了小带宽和丢包环境的。 很多人都会有一个初步印象就是实现一个类TCP看上去都会是一件很容易的事，不就是加上连接机制，重传机制，定时器机制，序列化机制等就可以保证TCP能够工作了，download 点开源的各种实现或者Linux内核，很快就可以改造出一个自己可用的版本出来。没错，一个可用的TCP实现确实就这样完成了，但是一个可用的版本和一个高性能版本的TCP实现那差别就远的很了。该系列的文章已经从TCP的发展进行了描述过逐步引发的一些问题，下面再列举一些问题来说明： 1. 对各种网络环境的适应能力。现在的各种网络环境都存在不一样的特征，例如有高达Gbps的网络需要超大的传输能力，家用ADSL的小带宽需要保持稳定吞吐能力，卫星网络/跨国网络有着很大的延时和一定的丢包率，3G存在异构的网络，跨运营商的网络有着很大的丢包率(主要是在中国的跨运营商之间)，等等，这些不同的网络环境对TCP算法的挑战性非常大。 2. 对不同应用的适应能力。有数据备份应用需要大量的文件传输，有对交互延时非常敏感的如RDP/Citrix/网游等应用，有一直只发送小包(发送的包长度小于MSS)的应用，也有不停的发送大包的应用，还有两边同时发送和接收数据的应用。而一旦实现的不好，就有可能对某些传输应用效果很好，但是对某种特殊的应用就很差，例如TCP的Nagle算法，ACK 回复机制，如何控制突发性，重传算法等。曾经我就碰到过很多这种问题，因为多传输了一
TCP拥塞控制机制通常可分为四个基本阶段: 慢启动、拥塞避免、快速重传和快速恢复。其中有以下几个重要的参数: 往返时延(RTT):一个TCP数据分组从发送到接收到确认ACK之间的时间间隔。 发送窗口(wnd):发送端在一个RTT内发送的数据分组的个数。 通知窗口(awnd):接收端每次能接纳的数据分组的最大个数,在链接建立的初期 由发送端和接收端协商设定。 拥塞窗口(cwnd):TCP拥塞控制中的主要参数,表示发送端下一次最多能发送的 数据分组的个数;当网络发生拥塞时,用该参数控制数据发送速率。 慢开始门限(Ssthresh):拥塞控制中慢启动阶段和拥塞避免阶段的分界点,初始值 通常设为65535bytes。 超时重传时间(RTO):数据分组在网络中传输时的有效时间,从发送端发出的数 据分组在超过该时间段后没有收到确认分组时就认为出现丢包。 快速重传阂值(tcPrexmtthxesh):触发端系统进入快速重传阶段的条件,主要用于 提高分组重传的效率,通常用发送端收到重复确认分组的个数来表示,当发送端收到的 重复确认分组的个数超过该值,发送端就进入快速重传阶段。 浙江大学硕士学位论文第2章TCP拥塞控制机制 而不必等到Rl,O超时。 TeP使用的是一种和式增长积式减小(AdditiveInereaseMultiplicative Deerease,AIMD)的基于窗口的端到端拥塞控制机制。TCP源端的发送速率由拥 塞窗口控制,如果有一个数据包丢失,发送窗口减半;否则发送窗口大小加一。 TCP的拥塞控制方式对Iniemet上尽力而为型服务有很好的适应性,是Internet 拥塞控制机制重要的组成部分。 (1)慢启动阶段 TCP源端取拥塞窗口和通告窗口的最小值作为发送窗口上限,源端按照cwnd大小发送数据,每当收到一个ACK确认,cwnd就增加一个数据包的发送量。显然,cwnd的增长随RTT呈指数级增长:cwnd每经过一个RTT时间,增加一倍。实际上,TCP的慢启动算法到达最大的可利用的窗口砰,需要的时间为RTTlogZ解7]。 (2)拥塞避免阶段 当数据通信量超过一个路由器的处理能力时,数据包就会被丢弃,网络发生 拥塞。通常源端发现超时或收到3个重复ACK确认时,就认为网络发生拥塞, 此时就要进入拥塞避免阶段。慢启动阂值被设置为当前cwnd的一半,如果超时, cwnd还要被置为1。如果此时cwnd丛Sstliresh,TCP重新进入慢启动阶段;如果 cwnd>ssthresh,TCP就执行拥塞避免算法,每收到一个ACK确认,cwnd只增 加z/ewnd,即一个RTT时间内,cwnd只增加l,这是一种和式增长(additive inerease)。 (3)快速重传和快速恢复阶段 当数据包超时时,c二d被置为1,进入慢启动阶段,这样会过分地减少发送 窗口大小,严重降低TCP连接的吞吐量。因此,当源端在收到3个重复ACK确 认后,就断定数据包己经丢失,重传数据包,将ssthresh设置为当前cwnd的一半,
TCP拥塞控制算法内核实现剖析 分类：Linux Kernel2011-12-05 17:10 内核版本：2.6.37 主要源文件：linux-2.6.37/ net/ ipv4/ Tcp_cong.c 一、RENO及拥塞控制算法基础 1.1 RENO拥塞控制算法 =========================================================== struct sock *sk 和struct tcp_sock *tp 的转换 [cpp]view plaincopy 1.在include/ linux/ Tcp.h中， 2.static inline struct tcp_sock *tcp_sk(const struct sock *sk) 3.{ 4.return (struct tcp_sock *)sk ; 5.} 6. 7.给出struct sock *sk, 8.struct tcp_sock *tp = tcp_sk(sk) ; tcp_sock结构 [cpp]view plaincopy 1.struct tcp_sock 2.{ 3. ... 4. u32 window_clamp ; /* Maximal window to advertise */ 5. u32 rcv_ssthresh ; /* Current window clamp */ 6. u32 rcv_wnd ; /* Current receiver window */ 7. ... 8./* snd_wll 记录发送窗口更新时，造成窗口更新的那个数据报的第一个序号。 9. * 它主要用于在下一次判断是否需要更新发送窗口。
TCP拥塞控制 1 引言 Internet中拥塞控制的大部分工作是由TCP完成的，目前标准TCP协议的实现都包含了一些避免和控制网络拥塞的算法。当今Internet的可靠性和稳定性与TCP拥塞控制机制密不可分，而TCP的成功也要归功于其稳固的拥塞控制机制。随着应用要求的日益丰富和技术的不断发展，要想完全依赖实现在终端系统上的策略和算法很难满足服务质量（QoS）这样复杂的要求，为了解决相应的问题，相关网络技术逐渐转向网络的中间节点即路由器上，通过增强它们的功能来实现端到端无法达到的技术，从而达到有效的拥塞控制，保持网络的良好性能。 2 产生拥塞的原因 当一个网络中出现太多报文分组的时候，网络的性能开始下降，这种情况称为拥塞。拥塞是一种持续过载的网络状态，此时用户对网络资源的需求超过了其固有的容量，这是产生拥塞的根本原因，而端到端之间却存在着直接的原因，主要有：1.存储空间相对不足。主要表现在理由器上，虽然增加存储空间有时可以缓解拥塞的产生，但有时候不但不能缓解拥塞，反而会加剧拥塞。2.带宽容量不足。低速链路对高速数据流的输入也会产生拥塞。 3.链路与CPU的处理速度不匹配，造成处理能力弱，速度慢从而引起拥塞。 3 TCP的拥塞控制机制 3.1 加法增加乘法减少（AIMD）算法 TCP作为Internet上使用最广泛的端到端传输协议，它的拥塞控制机制主要基于加法增加乘法减少(AIMD)算法，该算法定义了3个窗口变量： (1) 拥塞窗口(cwnd)：它限定了在拥塞控制中源端在一时间段里的最大数据传输量，是来自源端的流量控制。 (2) 通告窗口(awnd)：接受端与源端建立连接后，接收端通告源端它的最大可接受速率，它是来自接受端的流量控制。 (3) 有效窗口(win):即源端发送数据的实际窗口大小，定义为win=min(cwnd,awnd) AIMD的工作过程可分为两步： (1)源端每收到一个来自接受端的ACK确认,拥塞窗口按 cwnd=cwnd+MSS*(MSS/cwnd) (MSS为分组大小)增大，它所表示的实际意义是如果源端发送的分组都在最近的往返时间(RTT)内获得确认,源端就将cwnd加1，即加法增加思想。 (2)当数据传送发生超时，TCP认为路线上出现拥塞，并开始减小源端的数据发送速率。每发生一次超时，源端就会重新计算拥塞窗口的值，公式如下： cwnd=cwnd/2