通信网理论基础A4纸整理.docx

基本概念
1、RED:提前随机丢弃(Random Early Detection);拥塞控制
是一种主动队列管理算法。Random:指按照一定的概率丢弃;Early:发生在队列已满之前;detection:只是为分组标记,更倾向于被丢弃。通过监控路由器输出端口队列的平均长度来探测拥塞,一旦发现拥塞逼近,即平均队列长度超过一个阈值,就以一定的概率丢包或者在分组上作标记来通知相应的连接来减小发送速率,使他们在队列溢出导致丢包之前减小拥塞窗口,降低发送数据速度,从而缓解网络拥塞,也就是说在缓冲区满之前就按照一定的比例(即丢弃概率)随机地将缓冲区的数据丢弃或标记。
随机早期检测(RED,Random Early Detection)算法将队列的平均队长作为决定拥塞避免机制是否应被处罚的随机函数的参数,增加了在队列长度变得太大之前平滑瞬时拥塞的可能性,可以过滤掉短期队长的变化,减少了同时使多个流受分组丢弃影响的可能性,使得因特网数据突发本质或短暂拥塞不会平均使队长有明显变化。
概率与长度问题计算:(1)若平均队列长度小于最小门限,则把新到达的分组放入队列进行排队(p=0);(2)若平均队列长度超过最大门限,则把新到达的分组丢弃(分组丢弃概率p=1);(3)若平均队列长度在最小门限和最大门限之间,则按照某一概率p(0-1)将新到达的分组丢弃。RED不是等到已经发生网络拥塞后才把所有在队列尾部的分组全部丢弃,而是在检测到网络拥塞的早期征兆时(即路由器的平均队列长度超过一定的门限值时),就以概率p随机丢弃个别的分组,让拥塞控制只在个别的TCP连接上进行,因而避免发生全局性的拥塞控制。平均队列长度()(count代表新到达的分组有多少个已经进入队列)。
AQM:主动队列管理(Active queue management),主动而非相应性的分组丢弃,提早通知发送方降低速率。包含有RED,SRED,FRED等。另一种拥塞控制:Drop tail:尾部丢弃(被动),队列达到最大长度,通过丢包来指示拥塞,告知发送方调整发送速率。
2、GBN ARQ:返回N自动请求重发(Go back N automatic repeat reQuest);差错控制
发送方在没有收到对方应答的情况下,可以持续的发送多个帧(窗口大小),假如发现已发送的第N帧中有错误发生,那么回退到第N帧及其之后所有的帧全部再重新发送,窗口越大重传帧数越多,而上述过程可以自动完成,不需要上层干预。最大窗口值:-1(i为比特数)
ARQ其他类型:停等式(stop-and-wait)ARQ(在开始下一帧传送之前,必须确保当前帧已被正确接收),选择性重传(selective repeat)ARQ(发送端不用等待接收端的应答,持续发送多帧,假如发现已发送的帧中有错误,只重新发送那个发生错误的帧)。
BEB:二进制指数退避(binary exponential backoff):流量控制
依据通信环境的变化,自适应调整冲突窗口时间值,提供了一个处理重负荷的方法。具体是指:一旦检测到冲突,为降低再冲突的概率,需要等待一个随机时间,然后再使用CSMA方法试图传输。为了保证这种退避维持稳定,采用了二进制指数退避算法的技术。遇到重复的冲突时,站点将重复传输,但在每一次冲突之后,通信窗口的时间t随n翻倍,从而减小发生冲突的概率,这是一种自适应算法。尝试传输的重复失败导致更长的退避时间,这将有助于负荷的平滑。
具体实现:具体的退避算法如下:(1)确定基本退避时间,它就是争用期(以太网的端到端往返时间,);(2)从离散的整数集合(k为重传次数) 中随机取出一个数,记为r。重传应推后的时间就是r倍的争用期。;(3)当重传16次仍不能成功时(这表明同时打算发送数据的站太多,以致连续发生冲突),则丢弃该帧,并向高层报告。‚PPT:(1)准备就绪时,在(0,w-1)一致性随机选择延后发送;(2)起始时,,最大不超过;(3)冲突发生后,w倍增;(4)如遇信道忙,w冻结。所谓截断就是有一个上限,不能无限制的加倍。
4、LPM:最长前缀匹配(longest prefix match);路由表查找
最长前缀匹配是指在IP协议中路由器用于在路由表中进行选择的一个算法。Prefix:前缀,即IP地址中的前缀部分,对用于网络号。在使用CIDR时,由于采用了网络前缀这种记法,IP地址由网络前缀和主机号这两个部分组成,这时,路由表中的每个项目由“网络前缀”和“下一跳地址”组成。但是在查找路由表时可能会得到不止一个匹配结果。应当从匹配结果中选择具有最长网络前缀的路由。这是因为网络前缀越长,其地址块就越小,因而路由就越具体。在CIDR中,路由表中的每个表项都指定了一个网络,可能存在多行路