2014.5.17---网络流量×××与带宽控制技术

1.流量×××：缓冲区和令牌桶。当报文的发送速度过快时，首先在缓冲区进行缓存，在令牌桶的控制下再均匀地发送这些被缓冲的报文。

2.带宽控制是一种限制流量输出速率的措施，带宽控制的作用是控制某个数据源（主机或某类应用）的发送速率，当这类报文的发送速率超过预定指标时，将其丢弃。

3.流量×××与带宽控制的主要区别在于，流量×××对流量监管中需要丢弃的报文进行缓存，通常是将他们放入缓冲区或队列内。当令牌桶有足够的令牌时，再均匀地向外发送这些被缓存的报文。流量×××与带宽控制的另以区别是，×××可能会怎加延迟，而带宽控制几乎不引入额外的延迟，但会增加额外的丢包率。

4.就现有Internet体系结构而言，拥塞的发生是其固有的属性。因为在事先没有任何商量和请求许可机制的资源共享网络中，几个IP分组同时到达路由器，并期望经过同一个输出端口转发的可能性是存在的，显然，不是所有的分组都可以接受处理，必须有一个服务顺序，中间节点上的缓存为等候服务的分组提供了一定的保护，然而，如果次状况具有一定的持续性，当缓存空间被耗尽时，路由器只有丢弃分组。表面上增大缓存空间可以防止由于拥塞引起的分组丢弃，但随着缓存的增加，端到端的时延也相应增大，这是因为分组的持续时间有限，超时分组同样需要重传，因此，过大的缓存空间有可能妨碍拥塞的恢复，有效分组白白浪费了网络的可利用带宽。

5.拥塞导致的直接结果是分组丢失率提高，端到端的时延加大，甚至有可能使整个系统发生崩溃。负载与吞吐量之间的关系：一般有三个阶段，分别是拥塞避免，拥塞恢复，拥塞崩溃。拥塞避免结束时的负载称为膝点，拥塞恢复结束时的负载称为崖点。崖点之前负载和吞吐量都是线性的关系，之后就不是了，而是更加陡峭的曲线。

6.如何解决拥塞问题：1增加网络资源2降低用户需求：降低用户需求主要有三种方式，拒绝服务，降低服务质量和调度。

7.常见的拥塞控制机制：链路容量规划和网络设计、连接接纳控制、基于负载的动态路由、内容动态压缩，端-端反馈、链路-链路反馈、缓存

8.当前广泛部署的网络流量控制系统主要由四个部分：流量分类，队列管理，分组调度，流量×××。

   流量分类：按照不同的优先级或控制策略，将数据包注入到不同队列。当前的流量分类技术主要分为基于端口、会话、内容的识别方式。其经典算法包括Lakshman等提出的BV（BitVector）算法，Baboescu等提出的ABV（Aggregated Bit Vector）算法，以及Li Ji等提出的改进型ABV算法，AFBV算法。

   队列管理通过控制队列的平均深度来避免拥塞发生。对于主动队列管理，常用的算法有：RED（Random Early Detection），WRED和ECN（Explicit Congestion Notification）算法。RED算法便于实现，被大多数路由器采用。

   分组调度控制不同类型的分组对链路带宽的利用，使不同的数据流得到不同等级的服务。相关算法有基于静态优先级的PQ（Priority Queuing）算法，FQ（Fair Queuing）算法、WFQ（Weight Fair Queuing）算法、针对轮询的WRR（Weighted Roud  Robin）算法以及DWRR（Deficit Weighted Round Robin）算法等。

   流量×××使经过网络瓶颈的数据包平缓的注入主干网，减少数据包在边缘网关排队等待的时间，从而减少边缘网关缓存的大小和数据包丢失率。流量×××主要采用两种基本方法：漏桶算法和令牌桶算法，另外，Amit Aggarwal等提出的TCP Pacing、Karandikar等提出的TCR算法，以及Wei Huanyuan等提出的改进型TCR算法PostACK，都能实现网络流量的×××。

9.

• 典型流量×××与带宽控制方法：TCP流量管理：1）TCP滑窗机制2)TCP窗口管理3)TCP重传机制4）TCP自同步机制
• 队列管理技术：排队论，把分组流经网络传输节点的过程用顾客-服务器模型来描述。这里的队列管理指对网络传输节点中队列缓冲资源的管理和分配，即缓冲管理。
• 分组调度技术是实现网络流量控制的核心机制之一，使网络资源管理的重要的内容，通过控制不同类型的分组对链路带宽的利用，使不同的数据流得到不同等级的服务，分组调度的基本过程是根据一定的系统信息作出判断，控制各个队列占用来南路带宽的频率，进而影响贷款分配、时延和时延抖动等。分类器根据分组的上下文和粒度确认它所在的队列，分组进入相应队列排队等候，直至调度器将其选择发送。  1）带宽分配  2）时延控制 3）相对优先级控制 。三种常用的分组调度算法：1）基于静态优先级的算法2）基于轮询的算法3）基于链路共享算法

• 流量×××技术：流量×××主要采用两种基本算法：漏桶和令牌桶算法

10.linux网络过滤技术与连接分析

linux分为三层：最下面是硬件层（包括CPU 、内存、磁盘、键盘、显示器、网卡），中间是内核层（是有层次的）

最上面是用户层，用户层包括函数库和用户程序。

11.Netfilter是linux内核中的一个包过滤框架，默认情况下，这个框架实现了包过滤、状态监测、网络地址转换和包标记等多种功能。本书讲的很详细。

12.linux连接跟踪式就是跟踪并且记录网络流的连接状态。linux系统为每一个经过内核网络协议栈的数据包生成一个新的连接记录项（connection entry）。此后，所有属于此连接的数据包都被唯一的分配给这个连接，并标识连接的状态。连接跟踪是防火墙模块的状态监测的基础，同时也是地址转换中实现SNAT和DNAT的前提。大部分的流量控制技术和方法，大多是基于linux流量跟踪的。

    状态检测技术是近几年才应用的新技术。传统的包过滤防火墙只是通过监测IP包头的相关信息来决定数据流通过还是拒绝；而状态监测技术采用的是一种基于连接的状态监测机制。将所有属于同一连接的包当作整体来的数据流来看待，构成连接状态表，通过规则表和状态表的配合，对表中的各个连接状态因素加以识别。动态链接状态表内的信息可以很灵活，可以是以前的通信信息，也可以是相关应用程序的信息。具有很强的灵活性和安全性。

   状态监测和应用代理是防火墙市场内普遍采用的主流技术，两种技术趋于融合。

13.无分类队列规定有先进先出（First In  FIRST Out,FIFO）、随机早起检测（Random Early Detect，RED）、随机公平队列（Stochastic Fairness Queueing,SFQ）、令牌桶过滤器（Token Bucker Filter,TBF）。目前基于分类的队列规定有基于分类的队列（Class-Bassed Queuing,CBQ），分层令牌桶队列（Hierarchical Token Bucket，HTB），基于优先级的队列规定（PRIO）。

14.目前Internet上应用广泛的内部网关协议总是选择链路权值总和最小的路径，但也因此导致网络上的流量分布不均衡，浪费了网络资源。而在自治系统（Autonomy System，AS）区域边缘的负载不平衡，边缘网络与主干网络连接时流量负载的不平衡性，也成为了网络拥塞的瓶颈。因此，多链路环境下的流量负载平衡和流量控制具有重要的现实意义。

15.流量工程的主要目的是怎就爱运行网络的效率，提高其可靠性，同时优化网络资源的使用和流量性能。目前，IETF的因特网流量工程工作组（TEWG）负责流量工程领域的标准化工作。随着互联网服务提供商（Internet Service Provider，ISP）网络规模的日益扩大和流量的激增，以及ISP之间的网络服务方面的激烈竞争，流量工程的优化设计变得越来越重要。此外，多链路网络流量调度也是实现网络结构可扩展性、可靠性的重要问题。

    如何在多个节点的多链路之间合理地调配流量是目前流量负载平衡研究的热点问题。

    widjaja等首次提出了流量工程的概念，但只是简单地从避免拥塞的角度出发，从高拥塞的节点搬移到流量到无拥塞的节点。仿真表明，在整个网络负荷很小的时候能够很好的工作，随着网络符合的增加，收敛性变得很差[1]。[2][3]给出了MPLS网络的动态区分模型和分析结果，但是对Internet的流量特征过于理想化和模型化，其数学结果很难应用与实际，仿真的假设条件也过于简单。

考虑参考MPLS标签协议加快在现有网络中转发速率的设计，将其应用的color中。使得域间的流量能够自适应的Load-Balancing。

    三个文献:[1]Elwalid A,Jin C,Low S,et al. A Framework for Internet Traffic Engineering. http://www.itef.org/proceedings/51/I-D/draft-ietf-tewg-framework=05.txt

                  [2]Dinan E,awduche D,Jabbari B. Analytical framework for dynamic traffic partitioning in MPLS network. IEEE INternation Conference on Conmmunications,New Orieans,2000

                  [3]Dinan E,awduche D,Jabbari B. Optimal traffic partitioning in MPLS. Networking 2000,Paris,2000

    优化流量分配的核心就是任务调度，将多个任务请求比较均衡地分布到控制节点进行调度，有控制节点决定路由路径，可使各个控制节点有效利用，从而提高系统的吞吐能力，保证整个系统的实时高效。优化问题本质上是在每个控制节点上从多个选择域中得到渐进次优解，理论上没有最优解的算法[4]。

                 [4]Gerasoulis A,Yang T. On the granularity and clustering of directed acyclic task graphs. IEEE Transcation on Parallel and Distributed System,1990,4（6）：686-701

16.目前Internet上最广泛的内部网关协议是OSPF，采用最短路径优先算法（SPF）选路，因此产生网络流量分布不平衡，使得网络上有些链路因为过负荷产生拥塞现象，而另外一些链路则处于闲置状态。网络流量优化体系的主要目的是优化网络资源利用率，提高网络行性能，能够提供有保证的网络负载质量，路由优化算法是实现流量工程目标的重要策略之一。

17.恰当调整网络中链路的权值可以对网络路由进行控制，达到流量工程目标。这种方式保持了IP网络的无连接特性，以及由此带来的简单性和良好的可扩展性，Cisco公司建议将链路权值设置成C的i次方分之一（C的i次方为链路容量），这种方式没有利用网络内的流量分布信息，因此不能有效地利用网络资源。Khanna等早起研究者提出将链路权值与当前链路上的负载状态对应起来以避免拥塞，这种方法会带来频繁的路由改变，导致网络不稳定。Fortz建立了以平衡网络流量分配为目标的链路权值全局优化模型，并提出一种启发式算法求解改NP完全问题（关于NP完全问题见算法导论第5页）的优化问题，Wang等研究发现，求解路由优化问题的对偶问题，可以得到一组链路权值，给出了建立符合负载均衡原则的启发式方法，使得通过SPF算法得到的路由与求解线性规划问题的最优路由一致，Lee对多约束条件下的负载均衡问题I进行了数学描述和分析。很多算法的基本你思路都是先对原数学模型中的流限制条件进行松弛、求解，在此基础上再依据实际的流限制条件，进行路由调整。但是，要在等价最短路径中任意分配流量，这在实际网络中是难以实现的。

18.国内之前的相关研究思想，薛希俊等基于路径的量度提出带宽和跳数的流量工程动态路由选择。未涉及自治系统边界链路的负载问题[1]。向建军等采用董涛任务分配表为核心的多任务负载分配方式，此方法独特，并可以较精确地求解负载均衡问题，但尚未在重载条件下进行工程验证，在上述的研究工作中，知识注重了网络负载均衡，忽略了对路径传输时延的控制[2]。郭国强等将IP流量规划与区分服务相结合，在分析区分服务对流量需求的基础上，设计了区分服务与流量规划相结合的功能框架，提出了适合流量规划要求的队列调度方法以及流量分割和映射的原理和方法。但回避了实际流量工程中的大规模流量和IP包重组问题[3]。【可以考虑在Color中也引入同样的体系，即将服务标识SID与流量规划相结合】

               [1]薛希俊，孙雨耕，刘振肖. 基于带宽和跳数的流量工程动态路由选择算法研究.电子学报，2002,30(2):274-278

               [2]向建军，白欣，左继章. 一种用于实时集群的多任务负载均衡算法. 计算机工程，2003，29（12）:36-38

               [3]郭国强，张尧学，王晓春. 一种区分服务域内的IP流量规划方法. 软件学报，2002,13（3）:365-371

19.提供了两种模型：多逻辑链路间共享令牌调度流量负载模型（通过在多链路间动态调度令牌，此模型使链路的流量趋于稳定分布，到达流量负载均衡的目的。算法伪代码需要结合数学模型同时使用）和多链路时延反馈共享令牌流量拥塞控制算法（前者的改进，有效减少数据链路访问时延，而且链路流量的平滑性，带宽利用率等都比其他传统调度算法要好，适合高性能贷款介入链路流量控制的应用）。