路由机制（共8篇）
路由机制 篇1
摘要：随着计算机技术的告高速发展, 因特网规模的不断增大, 各种各样的网络服务也越来越多。如视频点播、语音群聊等多媒体实时业务的出现。以及文本页面的浏览, 附件数据包的下载等各种不同业务的涌现使得现在网络的负载压力也越来越大。尤其是针对一些实时性业务, 对网络传输时延、延时抖动等特性都要求较高。这样更加导致网络负载压力的增大, 同时也使得实时业务的服务质量难以得到保证。这就对路由器中的队列调度机制有着很高的要求。本文主要介绍一下传统的路由队列调度机制, 以及针对一些特定服务模型如区分服务所提出的队列调度机制的改进进行介绍。
关键词：视频点播,实时业务,队列调度,区分服务
1 常见路由器队列调度机制
(1) 先进先出队列FIFO调度算法
(2) 优先级队列PQ调度算法
(3) 加权公平队列WFQ调度算法
(4) 差值加权轮训队列DWRR调度算法
2 队列调度算法的性能指标
队列调度算法性能的好坏主要涉及到时延性能、公平性、复杂性这三个方面。
时延性能:队列调度算法应为不同的业务流提供端到端的时延保证, 而且只与此业务流的某些参数 (如带宽需求等) 有关, 而与其他的业务流无关。Stiliadis和Varma首先提出了一种分析网络中不同队列调度算法带来的端到端时延的模型;时延速率调度器 (LRS:Latency2Rate Server) 。Francini随后又提出了另一种分析端到端时延的模型:速率分隔 (RST:Rate2Spaced2Timestamp Scheduler) , 此模型的限制条件比LRS要少且在定长分组环境下应用时更加有效。
公平性:可用的链路带宽必须以公平的方式分配给共享此链路的各业务流:此外队列调度算法必须能够隔离不同的业务流, 让不同的流只享用自己可以享用的带宽, 这样即使存在恶意或高突发性业务, 它也不致影响到其他的正常业务流。关于算法公平的定义有:服务公平指数 (SFI:Service Fairness Index) 和最坏公平指数 (WFI:Worst2case Fairness Index) 两种。
复杂性和可扩展性:调度算法实现起来应该比较简单.在高速网络中, 传输一个分组的时间很小, 所以调度算法必须在短时间里完成对分组的调度, 这就要求调度算法尽量简单, 易于实现。另外当业务流数量增加和链路速率变化范围较大时, 调度算法仍应有效工作;这要求调度算法应该具有良好的可扩展性。
3 现有队列调度算法性能比较
3.1 基于轮询的调度算法
传统的轮循 (RR:Round Robin) 算法对不同队列 (业务流) 进行无区别的循环调度服务.这样, 如果不同的队列具有不同的分组长度, 则分组长度大的队列可能会比分组长度小的队列接受更多的服务, 使队列之间产生不公平的现象;而且, 这种算法不能对业务提供时延保证.后来为了改进RR算法, 出现了一些改进型的算法。如加权轮询 (WRR Weighted Round Robin) , 差额轮询 (DRR Deficit Round Robin) , 紧急轮询 (URR Urgencybased Round Robin) 。
3.2 加权公平队列WFQ调度算法
WFQ调度机制是由Demers等人提出, 又由Parekh等人实现基于报文的PGPS (packet by packet generalized processor sharing) 的排队算法。
WFQ调度机制主要分为基于流的WFQ和基于类的WFQ (CBWFQ) 2种。它们的主要区别在于:前者的队列数在理论上没有限制, 但队列数目太多会增大调度的复杂度, 而后者最多为64个队列。WFQ算法能到达很好的公平性和时延保证, 但是系统其系统需时间函数计算复杂度为O (N) (N为总的队列数) , 且具有较大的WFI, 使得输出的突发度增加。它虽然很好的解决了RR机制的不公平性, 但是包含了GPS调度机制的局限性, 它调度的结果会带来带宽保证和时延保证的耦合性 (即低带宽保证总以为着不严格的时延保证) , 这个特性使得WFQ不适合调度某些类型的业务, 这类业务的特点是带宽需求不大, 但是有着极严格的时延要求, 如语音等实时业务。
3.3 基于时延的调度算法
基于轮询和WFQ的调度算法可以看成是基于速率的调度算法, 这种算法通常为每个队列提供一定的速率保证来达到提供时延保证的目的。而基于时延的调度算法则是以 (为各队列) 直接提供时延保证为目的, 这类算法的代表是最早期限优先 (EDF, Earliest Deadline First) 。
4 基于区分服务的调度算法
区分业务 (Diffserv Differentiated Service) 体系结构正成为解决因特网上服务质量的一种有效的办法, 能支持Diff Serv技术的一个子网被称为Diff Serv域, 它由一些边缘路由器和域内路由器组成, 边缘路由器执行较为复杂的业务流分类、业务量调节及队列管理和调度的功能, 而域内路由器则执行较为简单的队列管理和调度的功能。之前介绍的队列调度都没有边缘交换节点和域内交换节点。都是基于每个业务流的调度算法, 他们需要交换节点维护每个业务流的一些状态信息, 尽管这样可以达到很好的调度性能, 但同时带来了不易扩展和不强壮的缺点。
基于这种考虑, Stocia提出了两种新的调度算法:CSFQ (Core Stateless Fair Queueing) 和CJVC (Core Jitter Virtual Clock) , 其核心在于对交换节点进行了“边界交换节点”和“域内交换节点”的区分, 从而不需要每个交换节点都维护所有业务流的状态信息。
5 结论
队列调度算法的目的都是以可实现的复杂性为代价来提供更好的服务质量:公平性和时延性能。除了先入先出、优先级和传统轮循调度外, 先进的队列调度算法都是把分组放到不同的队列里, 然后再为其计算一个时签, 根据时签的大小来对分组进行调度.对于PFQ算法, 其出发点在于为每个队列提供带宽保证 (从而时延得到一定的保证) , 所以在其时签的计算中只用到了速率参数和分组长度参数;而基于时延的调度算法, 则以提供时延保证为主要目的, 所以在其时签的计算中, 只引入了队列的时延参数。本文首先介绍了几种传统的队列调度机制的算法如FIFO、PQ、WFQ和DWRR这四种传统的调度算法。然后接下来对队列调度算法的性能指标及几种队列调度算法的优缺点进行了阐述和比较。最后在这些算法的基础上, 根据现有的区分服务模型的提出了新的调度机制, 并对其进行了改进。总之, 未来的队列调度机制一定要适合网络带宽的高速化和业务多样化的发展趋势。首先要保证高的分组调度速度, 同时在时延特性和公平性方面有较好的保证。
路由机制 篇2
阅读提示：静态路由是指由网络管理员手工配置的路由信息，动态路由是指路由器能够自动地建立自己的路由表，并且能够根据实际实际情况的变化适时地进行调整，
静态路由
静态路由是指由网络管理员手工配置的路由信息，
当网络的拓扑结构或链路的状态发生变化时，网络管理员需要手工去修改路由表中相关的静态路由信息。静态路由信息在缺省情况下是私有的，不会传递给其他的路由器。当然，网管员也可以通过对路由器进行设置使之成为共享的。静态路由一般适用于比较简单的网络环境，在这样的环境中，网络管理员易于清楚地了解网络的拓扑结构，便于设置正确的路由信息。
动态路由
动态路由是指路由器能够自动地建立自己的路由表，并且能够根据实际实际情况的变化适时地进行调整。
路由机制 篇3
随着网络应用日益深入到人们的生活之中,网络冗余备份机制显得越发重要。作为IPv4的替代协议, IPv6网络必须提供可靠的网络冗余机制保证业务的可靠传输。多路由器备份是一个日益重要的网络冗余备份机制。 在多路由器备份场景中,在同一链路上的两个或多个路由器提供网络的冗余备份功能。本文中将分析研究IPv6邻居发现协议以及默认路由优先级协议,并利用路由器发现机制,邻居不可达检测机制以及默认路由器优先级实现网络冗余机制。
2 邻居发现协议
邻居发现协议是IPv6协议的一个基本组成部分。它主要利用ICMPv6协议, 增加了新的ICMPv6报文类型以解决几个问题。路由器发现:主机如何定位链路上的路由器;前缀发现:主机如何发现同一链路上有哪些前缀;参数发现:节点学习链路MTU等参数,地址自动配置;地址解析:获取邻居的链路层地址,下一跳判定; 邻居不可达检测:判定邻居可达状态,重复地址检测;重定向:路由器告知主机更好的第一跳节点。
IPv6主机利用邻居发现协议中的路由器发现过程来发现链路上的路由器网关。路由器发现过程定义并使用了路由器公告 (ICMPv6类型133) 和路由器请求 (ICMPv6类型133)两种ICMPv6消息。
路由器随机的发出非请求路由器公告报文到链路范围内所有节点组播地址(FF02::1)如图1所示。此时链路范围内的所有主机都可以接收到该路由器公告报文。
IPv6主机也可以通过发送路由器请求报文到链路范围内所有路由器组播地址(FF02::2)主动请求路由器发送路由器公告报文。当路由器收到主机的路由器请求报文时将立即发送路由器公告报文作为回应。 如图2所示。
当收到路由器公告报文后,IPv6主机将根据路由器公告报文的内容自动配置默认路由列表。IPv6主机将使用默认路由器列表来选择默认路由器转发报文。
3 默认路由优先级
如图3所示, 在同一个链路上存在多个路由器,其中与路由器1相比,路由器2可以提供更好的路由转发性能。理论上IPv6主机应该优先选择路由器2作为默认路由器。但是根据RFC4861定义的路由器发现协议, 当一个链路上存在多个路由器时,IPv6主机从默认路由器列表中循环选择默认路由器。此时路由器1可能被主机选为默认路由器。实际上这样的选择不是最优化的。
RFC4191在路由器公告报文的基础上,使用了路由器公告报文中的保留位, 增加了Prf (Default Router Preference)字段,用来定义路由器优先级:
01 High
00 Medium (default)
11 Low
10 Reserved - MUST NOT be sent
IPv6主机可以根据路由器公告报文中的路由器优先级来选择高优先级的路由器作为默认路由器。如图4所示,主机1和主机2选择了具有更高优先级的路由器2作为默认路由器。
此时如果路由器2发生故障,主机1和2将选择备份的路由器1作为默认路由转发数据报文。
4 默认路由器不可达检测
优选的默认路由器可能因为很多原因失效不能提供服务,例如硬件故障,链路故障等等。IPv6主机必须检测到优选默认路由器故障从而选择备份的默认路由器。在IPv6中, 主机使用邻居不可达检测机制来发现优选默认路由器故障。邻居不可达检测过程定义并使用了邻居公告(ICMPv6类型136)和邻居请求(ICMPv6类型135)两种ICMPv6消息。
当IPv6主机收到邻居路由器公告报文后,IPv6主机将为邻居路由器创建新的邻居列表, 其邻居状态都变为REACHABLE。经过一定时间,邻居状态由REACHABLE变为STALE状态。当主机需要发送数据给一个状态为STALE的邻居时,发送主机把邻居状态改为DELAY,并启动定时器。若定时器超时后,邻居状态仍为DELAY,则把邻居状态改为PROBE。若定时器超时前收到邻居可达确认,则邻居状态变为REACHABLE。在PROBE状态, 主机每隔一定时间重发一次单播的邻居请求, 直到收到邻居的可达性确认。当发送了若干个邻居请求后,依然没有收到邻居的回应,则中止发送,删除邻居条目,此时认为邻居不可达,如图5所示。
5 实现网络备份机制
图6给出了一个利用路由器优先级,路由器发现过程以及邻居不可达检测过程实现的路由器备份过程。
(1)路由器1和路由器2发送路由器公告。
(2)根据路由器优先级 ,主机创建路由默认路由器列表,选择高优先级的路由器作为主路由器,低优先级路由器作为备份路由器。
(3)正常情况下IPv6报文经路由器2转发。
(4)主路由器2发生故障。
(5)主机通过邻居不可达检测机制检测到主路由器2不可达。
(6)选择备份路由器1作为主默认路由器。
(7)新的IPv6报文经路由器1转发。
6 结束语
当使用IPv6承载网络业务时, 网络的冗余备份机制变得越来越普遍,越来越重要。本文通过在IPv6网络中应用路由器发现机制, 路由器优先级以及邻居不可达检测机制实现了IPv6网络的路由器冗余备份机制,为IPv6网络业务的传输提供了可靠保证,并提高了网络自愈能力。同时我们也应该注意到当IPv6网络用于语音, 数据等实时业务传输时, 业务要求可靠不间断传输。本文提供的IPv6网络路由器备份机制的有效性依赖于邻居故障发现以及备份路由器切换的有效性及快速性。根据邻居发现协议,邻居不可达检测通常需要几秒,十几秒的时间,对于传送实时业务的通信网络,这样的故障切换时间太长。如何缩短故障切换时间是我们下一步的研究方向。
摘要：随着互联网技术的爆炸性发展,网络应用日益深入到人们的生活之中。网络冗余备份机制显得越发重要。作为IPv4的替代协议,IPv6网络必须提供可靠的网络冗余机制保证业务的可靠传输。多路由器备份是一个日益重要的网络冗余备份机制。在多路由器备份场景中,在同一链路上的两个或多个路由器提供网络的冗余备份功能。本文中将分析研究IPv6邻居发现协议以及默认路由优先级协议,并利用路由器发现机制,邻居不可达检测机制以及默认路由器优先级实现网络冗余机制。
路由机制 篇4
无线传感网络节点多用于比较恶劣的环境,如战场或各种地下作业,因此对节能和数据可靠传输的要求较高,同时由于节点分布不均匀,多为垂直和水平分布,传统的路由协议如AODV(Ad Hoc On-Demand Distance Vector Routing),Gear,Leach等缺乏灵活性,且对节点定位要求较高[1]。而先应式路由协议OLSR(Optimized Link State Routing)引入了MPR选择机制,使得其有效减少路由开销和保证节点传输的可靠性。
OLSR是一种先验式路由协议,已经被IETF MANET工作组正式公布为自组网路由协议的RFC标准。OLSR通过获得的拓扑信息,利用Dijkstra算法进行路由计算,选择到达目的节点的最短路径。
虽然OLSR协议具有很多优点,但研究结果表明,当节点分布稀疏时,使用OLSR协议获得的数据吞吐量大幅度下降,同时延迟也增大[2]。因此本文将对OLSR协议进行改进,使其在稀疏节点环境中也能取得较好的性能。
1 OLSR路由协议的改进
本文提出的结合功率进行补偿机制的改进OLSR协议,在节点密集处采用传统OLSR协议,在节点稀疏处自动切换到改进后的OLSR协议。
1.1 OLSR路由算法的缺陷
(1)不适应稀疏节点
OLSR协议默认节点信号传播半径足够大,保证源与目的节点之间存在通信链路使得网络整体连通。但在节点稀疏或移动分布式无线网络拓扑结构中,网络拓扑频繁改变,无法确保网络的连通性及节点间始终存在通信路径。
(2)链路结构不均衡
OLSR协议只有被选为MPR的节点才产生并转发TC(Topology Control)消息,默认情况下的TC只包含了MPR(MultiPoint Relays)选择者的地址信息[3]。在每个时刻,网络节点的拓扑集里仅仅存在MPR链路信息,而对其他的对称链路或者单向链路不会反映到网络拓扑集中。OLSR协议实验可以得到10个节点情况下网络拓扑图如图1所示,完整的拓扑图如图2所示。
由图1可以看出,节点3,7,8,9均未被任何节点选为MPR,它们没有TC消息可以发送,同时节点8只有一条链路可以被广播。
节点8到目的节点只有一条可用链路,因此需要为这些MPR节点集中节点数为1的节点选择一个备用的转发节点,当MPR节点出现故障时,能够及时代替MPR节点转发。
1.2 稀疏OLSR路由补偿节点选择算法
改进协议针对只有一条链路被感知的节点,在Hello消息中增加一个标志位,标志该节点MPR集中节点数量。
协议开始后,按照传统OLSR协议进行MPR选举,MPR集合中的节点选出后,各个MPR节点检查收到的节点Hello消息中的标志位,当标志位为1时,在网络性能下降到一定程度时就可以采用补偿算法选取相应的补偿节点,增大补偿节点发射功率,使它的通信范围覆盖MPR集合中惟一节点所覆盖的范围,这样就解除了该惟一节点的不可靠性,以保证整个网络的连通性。补偿节点选择流程如图3所示。
由图3可得到补偿算法如下:
为了节约能量,补偿节点最大发射功率的工作时间为一个查找周期,当发现MPR集合中的集合节点不需要补偿节点时就恢复之前的发射功率。
2 自主切换机制
在路由建立阶段,当通过各个节点的Hello消息使整个网络的MPR节点集确定后,MPR子集内部各个节点利用式(1)求出平均阈值Savr:
undefined
式中:Sall代表整个网络的节点数和;Smpr代表MPR集合节点个数。MPR节点集合内的各个子节点计算自己负责转发的节点数Hello_Count。当Hello_Count低于平均阈值Savr时,便利用式(2)开始预测本轮信号强度:
undefined
式中:Snew-measure表示新测得的信号强度;Sold表示上一次预测的信号强度;Snew表示预测的下一段时间的信号强度;∂是权重,取值范围是[0,1],∂越小,预测信号强度受该时刻信号强度的影响越大[4]。
当预测的下次信号强度低于预先规定的一定强度时,可以确定此处为稀疏节点分布区且信号强度较低,则该MPR集合中节点分组内实行改进后的OLSR协议,否则继续使用OLSR协议。
OLSR协议和改进OLSR协议的自主切换机制流程如图4所示。
3 功率控制算法依据
补偿机制中,需要增大节点的发射功率,当源节点向目的节点发送分组时,发送功率Pt与接收功率Pr的关系[5]如下:
undefined
式中:λ为载波波长;d为源节点和目的节点间的距离;Gt为发射机天线增益;Gr为接收机天线增益。设接收功率的门限为Prt,当信号的功率不小于Prt时才能被正确接收,可推出式(4)和式(5):
undefined
由式(4)可知,当传输距离增大1倍,发射功率成幂级数增加,才能被正确接收。
4 实验结果
本文实验环境是在Linux操作平台下移植了TinyOS操作系统,利用CC2430控制芯片进行编程,并在ns2.34环境下进行仿真实验。
4.1 仿真实验环境
仿真的网络范围为500 m×1 000 m,节点数量为20和100个,传输范围为250 m,物理信道的带宽为2 Mb/s,MAC层使用802.11a协议。建立12个CBR业务连接,分组长度为512 B,仿真时间为200 s,发包率为4个/s,节点的速度分别为0 m/s,1 m/s,5 m/s,10 m/s,20 m/s,25 m/s,30 m/s。
4.2 性能指标
协议改进主要针对网络的可靠传输,因此仿真实验的性能指标有节点投递率和网络传输平均延时[7]。由于改进后的协议运用了自主切换机制,必然会增大部分能量的开销,因此,需要对剩余能量也进行仿真实验[6]。
(1) 投递率
OLSR协议适用于节点密集型的网络,从图5可以看出,两个协议在100个节点的网络整体比20个节点的稀疏网络的投递率高。在节点固定或者移动较小的情况下,性能已经很好,则改进后的协议性能并未得到良好的体现。当节点移动速度超过10 m/s后,网络性能明显下降,这时运用自主切换机制,网络的投递率得到显著改善。速度越大,OLSR协议性能下降越快,而改进的OLSR协议性能下降得到控制。
(2) 平均时延
在节点固定或者移动速度较低的情况下,改进的OLSR协议并未表现出特别的优势,这是由于监测网络的性能耗费一定的时延,之前采用自主切换提高的时延并不明显。
端到端时延统计如图6所示。由图可看出,当节点移动速度超过15 m/s后,改进的OLSR协议能够在网络剩余能量很低或部分MPR节点失效的情况下,使数据通过补偿节点得到及时的转发,因而它的网络传播时延相比OLSR协议有明显降低。
(3) 剩余能量
对100个节点进行仿真,速度固定为5 m/s,假定节点初始能量在[20,60]间随机分配。仿真时间为400 s,x轴表示剩余能量,y轴表示处于该能量的节点数,如图7所示。
在400 s处,使用传统路由协议在剩余能量60 J处有3个,而改进的协议在此处为1个。但是在剩余能量为10 J的节点中,传统OLSR有15个,而改进的OLSR只有11个,两个协议的大多数节点都集中在[20,50]的能量区。由此可见,使用改进的OLSR协议并没有造成过多的能量耗费,同时有效地平衡了能量的均衡使用,从而延长了部分节点的寿命。
5 结 论
本文分析了OLSR协议不适合节点分布稀疏的网络拓扑结构情况,通过加入特定节点补偿机制和自主切换机制对其进行改进,并对改进后的OLSR协议进行了仿真。实验结果表明,改进后的协议能够取得更高的投递率,提高了网络传输的可靠性。在节点移动速度较大时,在降低时延方面效果显著。同时也有利地均衡了各个节点的能量,从而延长整个网络的寿命。
选取出的补偿节点进行合适的功率放大后,增大了节点的传输覆盖范围,必然会对周围的节点传输信号有所影响,本文假定是在忽略功率增大的幅度对周围节点信号强度影响的情况下进行的研究,下一步对增加这种补偿和切换机制后的网络与节点信号强度之间的关系和影响进行研究,找到一种均衡的度量关系,使改进的协议性能可以得到最好的发挥。
摘要：针对物联网无线传感器监测系统,研究了适合稀疏分布传感器节点下的无线路由OLSR协议,并对传统OLSR路由协议进行改进。在网络高可靠性要求和节点分布不均的情况下,引入了功率补偿机制和自主切换机制,并对改进后的协议通过NS2进行了仿真实验。实验结果表明,该协议在可靠性和时延方面均有所提高,达到了提高稀疏节点无线路由网络系统性能的目的。
关键词：OLSR协议,稀疏路由,补偿点,功率补偿,自主切换机制
参考文献
[1]SUN Yan-jing,LIU Xue.Wireless multi-hop ad hoc net-works based on OLSR for underground coal mine[C]//Wireless Communications and Signal Processing.Suzhou:IEEE,2010:1-4.
[2]WISITPONGPHAN N,FAN Bai,MUDALIGE P,et al.Routing in sparse vehicular ad hoc wireless networks[J].Selected Areas in Communications,2007,25(8):1538-1556.
[3]DE RANGO Floriano,FOTINO Marco,MARANO S,et al.Energy efficient OLSR routing protocol for mobilead-hoc networks[C]//Military Communications Confer-ence.San Diego,CA:IEEE,2008:1-7.
[4]严雯,郭伟,刘军.一种基于信号强度的OLSR路由协议改进算法[J].电讯技术,2008,48(5):40-45.
[5]谭学治,王则鸣,李鹏.基于OLSR的Ad Hoc网络功率意识路由协议[J].通信技术学报,2008,41(11):103-105.
[6]TADDIA C,GIOVANARDI A,MAZZINI G,et al.Ener-gy efficiency in OLSR protocol[C]//Sensor and Ad HocCommunications and Networks.Reston,VA:IEEE,2006:792-796.
[7]CHENG Shun-feng.A wireless sensor system for prognos-tics and health management[J].Sensors Journal,2010,10(4):856-862.
[8]LI Zhi-yuan,HU Jin-hong.Simulation and analysis of opti-mized OLSR[C]//Multimedia Information Networking andSecurity.Nanjing,Jiangsu:IEEE,2010:97-100.
[9]王笃亭.基于DSP的FFT算法在无功补偿控制器上的应用[J].现代电子技术,2010,33(12):194-196.
路由机制 篇5
(1) IP协议概述。
网际协议或互联网协议 (Internet Protocol, IP) 是用于报文交换网络的一种面向数据的协议, 是网络层通信的标准协议, 它负责提供基本的数据封包传送功能, 让每一块数据包都能够到达目的主机, 但不检查是否被正确接收。与IP协议配套使用的还有四个协议:地址解析协议ARP、逆地址解析协议RARP、网际控制报文协议ICMP、网际组管理协议IGMP。
(2) 虚拟互连网络中IP数据报的传输。
如一个互联网中的源主机要把一个IP数据报发送给目的主机。根据分组交换的存储转发的概念, 源主机先要查找自己的路由表, 看目的主机是否就在本网络上。如果是, 则不需要经过任何路由器而是直接交付, 任务就完成了。如果不是, 则必须把IP数据报发送给某个路由器A。A在查找了自己的路由表后, 知道应当把数据报转发给路由器B进行间接交付。这样一直转发下去, 最后由路由器C知道自己是和目的主机连接在同一个网络上, 不需要再使用别的路由器转发了, 于是就把数据报直接交付给目的主机。而各个网络之间可以是异构的。
(3) IP地址。
IP地址是为每个网络连接 (网卡) 分配一个在全世界范围内惟一的标识。报文头中的源IP地址、宿IP地址分别表示源主机、目的主机的IP逻辑地址。
IP地址长度为32比特, 由网络号、主机号组成, 常用的IP地址有A类、B类、C类地址, 路由器就根据IP地址进行寻址。
现在的国际互联网普遍的采用了IP协议。而现在正在网络中运行的IP协议是IPv4;IPv6 为IPv4的后续的一个版本。互联网现在正慢慢的耗尽IP地址, 而IPv6的出现解决了这个问题, 与IPv4的32位的地址相比较而言, IPv6拥有128位的地址空间可以提供比前者多很多的地址。
(4) IP层转发分组。
在TCP/IP系统中, 选路是指在网络中选择一条用于传送IP数据包路径的过程。路由器是承担选路任务的网络设备。用于决策选路的信息称为IP选路信息。路由器使用IP选路信息, 对所传输的IP数据包进行IP转发。
由于Internet是由许多不同的物理网络连接而成的, 加入Internet的计算机在与其他入网计算机通信时, 发送信息的源计算机可能与接收信息的目的计算机在同一个物理网络中;也可能不在同一个物理网络 (如以太网) 中。IP数据包在从源计算机发送到网络上后, 根据上述两种不同情况, 被传递到目的计算机时也有两种方式:直接交付和间接交付。
①直接交付:
IP数据包被直接交付时不需要经过路由器。因为在运行TCP/IP协议的以太网中, 入网的计算机TCP/IP协议族的ARP协议软件, 会帮助查询到本物理网络中其他计算机的MAC地址, 使IP数据包可以直接从源计算机传递到目的计算机。
②间接交付:
当送出IP数据包的源计算机与接收数据包的目的计算机不在同一个物理网络时, 就需要借助跨接不同物理网络的路由器实现间接交付。特别是当源计算机与目的计算机被多个物理网络隔开, 且它们之间可能有多条信息传输路径时, IP数据包的间接交付不但需要借助多台路由器, 还有一个选择最佳路径的问题。
2 路由选择协议
2.1 路由原理
当IP子网中的一台主机发送IP分组给同一IP子网的另一台主机时, 它将直接把IP分组送到网络上, 对方就能收到。而要送给不同IP于网上的主机时, 它要选择一个能到达目的子网上的路由器, 把IP分组送给该路由器, 由路由器负责把IP分组送到目的地。
路由动作包括两项基本内容:寻径和转发。寻径即判定到达目的地的最佳路径, 由路由选择算法来实现。路由选择算法将收集到的不同信息填入路由表中, 根据路由表可将目的网络与下一站 (nexthop) 的关系告诉路由器。路由器间互通信息进行路由更新, 更新维护路由表使之正确反映网络的拓扑变化, 并由路由器根据量度来决定最佳路径。这就是路由选择协议 (routing protocol) , 例如路由信息协议 (RIP) 、开放式最短路径优先协议 (OSPF) 和边界网关协议 (BGP) 等。
转发即沿寻径好的最佳路径传送信息分组。路由器首先在路由表中查找, 判明是否知道如何将分组发送到下一个站点, 如果路由器不知道如何发送分组, 通常将该分组丢弃;否则就根据路由表的相应表项将分组发送到下一个站点, 如果目的网络直接与路由器相连, 路由器就把分组直接送到相应的端口上。这就是路由转发协议 (routed protocol) 。
2.2 路由协议
典型的路由选择协议有静态路由选择策略与动态路由选择策略。静态路由选择的特点是简单和开销小, 但不能及时适应网络状态的变化。对于很简单的小网络, 完全可以采用静态路由选择, 用人工配置每一条路由。动态路由选择的特点是能较好地适应网络状态的变化, 但实现起来较为复杂, 开销也比较大, 因此, 动态路由选择适用于较复杂的大网络。
根据是否在一个自治域内部使用, 动态路由协议分为内部网关协议 (IGP) 和外部网关协议 (EGP) 。自治域内部采用的路由选择协议称为内部网关协议, 常用的有RIP、OSPF;外部网关协议主要用于多个自治域之间的路由选择, 常用的是BGP和BGP-4。
(1) RIP协议。
RIP协议最初是为Xerox网络系统的Xerox parc通用协议而设计的, 是Internet中常用的路由协议。RIP采用距离向量算法, 所以也称为距离向量协议。路由器收集所有可到达目的地的不同路径, 并且保存有关到达每个目的地的最少站点数的路径信息, 除到达目的地的最佳路径外, 任何其它信息均予以丢弃。同时路由器也把所收集的路由信息用RIP协议通知相邻的其它路由器。这样, 正确的路由信息逐渐扩散到了全网。
RIP使用非常广泛, 它简单、可靠, 便于配置。但是RIP只适用于小型的同构网络。而且RIP每隔30s一次的路由信息广播也是造成网络的广播风暴的重要原因之一。此外, 它还有慢收敛的问题, 即好消息传播快, 坏消息传播慢。
(2) OSPF协议。
20世纪80年代中期, RIP已不能适应大规模异构网络的互连, OSPF随之产生。它是网间工程任务组织 (1ETF) 的内部网关协议工作组为IP网络而开发的一种路由协议。
OSPF是一种基于链路状态的路由协议, 需要每个路由器向其同一管理域的所有其它路由器发送链路状态广播信息。在OSPF的链路状态广播中包括所有接口信息、所有的量度和其它一些变量。利用OSPF的路由器首先必须收集有关的链路状态信息, 并根据一定的算法计算出到每个节点的最短路径。
(3) BGP协议。
BGP是为TCP/IP互联网设计的外部网关协议, 用于多个自治域之间。它既不是基于纯粹的链路状态算法, 也不是基于纯粹的距离向量算法。它的主要功能是与其它自治域的BGP交换网络可达信息。各个自治域可以运行不同的内部网关协议。BGP更新信息包括网络号/自治域路径的成对信息。自治域路径包括到达某个特定网络须经过的自治域串, 这些更新信息通过TCP传送出去, 以保证传输的可靠性。
2.3 新一代路由器
由于多媒体等应用在网络中的发展, 以及ATM、快速以太网等新技术的不断采用, 网络的带宽与速率飞速提高, 传统的路由器已不能满足人们对路由器的性能要求。
新一代路由器使用转发缓存来简化分组的转发操作。在快速转发过程中, 只需对一组具有相同目的地址和源地址的分组的前几个分组进行传统的路由转发处理, 并把成功转发的分组的目的地址、源地址和下一网关地址放入转发缓存中。当其后的分组要进行转发时, 应先查看转发缓存, 如果该分组的目的地址和源地址与转发缓存中的匹配, 则直接根据转发缓存中的下一网关地址进行转发, 而无须经过传统的复杂操作, 大大减轻了路由器的负担, 达到了提高路由器吞吐量的目标。
参考文献
[1]谢希仁.计算机网络 (第5版) [M].北京:电子工业出版社, 2008.
路由机制 篇6
如图1(a)所示,是4X4 mesh型拓扑结构的NOC,主要由通信节点和资源节点组成。每个IP核为一个资源节点,通过网络接口与一个通信节点(switch)互联,资源节点之间通过发送和接收数据包的方式进行通信。数据包由一个个数据微片构成。每个数据包从源节点到目的节点的通信链路有很多条,数据包通过每条链路所需要的时间各不相同。特定的路由技术不仅为数据包的传送选好路径,还决定了switch的工作状态。图1(b)所示为switch的结构图,它是由n+1条输入沟道(input channel,IC)和n+1条输出沟道(output channel,OC)通过交叉开关(crossbar)连接而成。Switch中需要植入一定的路由算法,才能使数据包在网络中传输。而这个路由算法由两大部分组成:输出选择和输入选择。一个数据包从某个IC流入,可以从多个OC中流出。例如,从IC_0中流入的数据包p0可以从输出沟道OC_0,OC_1等等中流出。这时,输出选择就决定了数据包具体选择哪一条OC输出。同样的,可能有多个输入沟道IC请求通过某一条输出沟道OC进行数据包输出。例如,IC_0中数据包p0和IC_1中数据包p1同时请求从OC_0中输出。这时,输入选择就需要选出具体是哪一条输入沟道IC获得选通权。
先前的很多工作[4,5]都是研究输出选择对路由效率的影响。该文提出一种新的基于阻塞程度的输入选择机制(block-level input selection,BLIS)。该机制可以使链路通信变的流畅,提高通信效率。实验研究表明,与传统的先到先得(first come first served,FCFS)输入选择机制相比,该机制不论是与自适应性输出选择还是与确定性输出选择结合使用,都大大降低了传输延迟。
1 基于阻塞程度的输入选择机制
先前已有先到先得(FCFS)[4]输入选择机制应用于NOC中,FCFS的输出沟道给了请求最早的输入沟道,因此所有输入沟道的优先级都是等同的,然而这种输入选择并没有考虑实际网络通信情况。本节提出一种不同阻塞程度下灵活选择输入沟道的输入选择机制。
1.1 输入选择机制
为了说明输入选择和输出选择对路由效率的影响,现在考虑如图2所示的一组通信节点网络,为了简单起见,IP核没有画出。
通信节点Switch颜色的灰暗程度表示其中等待的数据包数量。随着颜色的加深,switch中等待的数据包数量逐渐增多。白色的switch中等待的数据包数量最少,灰色有比白色要多,黑色的switch如节点(2,2),表示其中等待的数据包数量最多。为了证明输出选择对路由效率的影响,现在考虑数据包p0从节点(3,0)起始,传送到节点(0,2),现有多条路径可以选择,例如path1,path2。传输延迟较少的路径需要避开阻塞区域(如图中灰色和黑色的switch区域),所以path1与path2相比,延时较少,路径较优。这就证明了输出选择对路由效率的影响,一条合适的路径可以减少链路时延。现在考虑输入选择的影响,节点(3,2)处的数据包p1和节点(4,3)处的数据包p2同时想通过节点(3,3)。在这种情况下,较好的选择是让p1通过节点(3,3),因为节点(3,2)处比节点(4,3)处等待的数据包要多,网络阻塞程度要高。这样的选择将会降低阻塞更严重区域中等待的数据包数量,降低网络阻塞,进而提高NOC的性能。由此,该文提出一种基于阻塞程度输入选择机制(block-level input selection,BLIS)。
BLIS的基本思想是赋予输入沟道不同的优先权来选通输出沟道,而输入沟道的优先级是在通信过程中基于上流switch阻塞程度动态授予的。精确的来说就是通信节点中每个输出沟道根据当前switch中输入沟道的输出请求次数,得到一个BL(block level)值,然后把得到的BL值(即为输出请求次数)传送给下路相邻switch对应的IC,再根据所得BL的值来断定下路相邻switch中对应IC的优先级别。当某个通信节点中,同时有多个IC请求同一个OC输出时,BL最大的IC优先级最高,优先被选通。
图3作出了含有BLIS的switch结构图,可以看出该switch除了含有用来传输数据的连接线,还额外包括用来传送相邻switch BL的连接线。该switch共有n+1条IC和n+1条OC,每个IC中还有一个缓存(buffer),那些即将到来的数据包微片在还没送到某个OC之前,就暂时存放在buffer中。输出选择(OS)模块根据数据包的头微片,决定整条报文从哪个OC中输出。OS模块将输出请求发送到对应的OC。一旦某个OC空闲,OC中的BLIS模块就会检查所有的输出请求并发送一条选择信号给MUX模块,MUX模块再将获得许可的输入数据输出。如果只有一条输出请求,那么那条数据可以直接传送。如果有多条请求,则需考虑此刻具体哪个请求可以被选通。这个选择机制接下来做详细介绍。
2.2 BLIS算法伪代码
BLIS根据输入沟道BL的大小作出选择,输入沟道BL的取自上流相邻switch输出沟道的BL。上流switch输出沟道的BL是特定时刻收到输入沟道传送请求的次数。
图4为该输入机制算法的VHDL伪代码,它包括了两个并行的进程。当req_0...n变化时,进程observe_BL被激发,它根据当前第i个输出沟道收到的请求次数,将BL值赋予out_BL_i。接着BL值被传送到下流相邻switch中对应的第i个输入沟道并用于输入选择。例如,考虑图3所示的switch,IC_0和IC_1同时请求OC_0,则out_BL_0的值就是2,下流相邻的switch的in_BL_0的值也是2。为了避免高复杂性和硬件消耗,BL值传送到下一个相邻的switch中就截止,不会继续向更远的switch传送。例如先前的例子,IC_0的in_BL_0的值为3,IC_1的in_BL_1值为4,IC_0和IC_1同时请求OC_0,OC_0中out_BL_0值不是3+4而是2。当有输出请求且输出沟道空闲时,select_input进程被激发。它比较所有的输出请求及对应的输入沟道BL的值,选择BL值最大的作为输出。
对于那些与IP核相连的输入沟道,它们没有上流switch传送BL给它们。这些输入沟道的BL值默认设置为0,因此,网络中所有正在传送的数据包优先级都高于IP核中正在等待注入网络的数据包。
2 实验结果
该文设计了一系列实验来评估BLIS的性能,并与传统的FCFS输入选择做了对比。两种输入选择分别与确定性路由输出(XY路由[6])和自适应性路由输出(OE路由[7])结合使用,并用VHDL实现了四种路由模型:XY+FCFS,XY+BLIS,OE+FCFS,OE+BLIS,四种模型都在6X6 mesh NOC上做了仿真。由先前的工作[4,9]可知,路由算法的性能的主要是通过传输延迟来评估的。在给定的注入率(在一个周期内注入网络的数据包数)下,我们测量每个数据包的平均传输延迟。一个数据包的传输延迟时间是指从源节点数据包的第一个微片产生开始到最后个微片送进目的节点后所持续的时间。所有的仿真都是基于50,000个数据包求平均的。考虑到网络的稳定性,在头5000个周期内传输延迟不作计算。假定,数据包的固定长度是5个微片,输入沟道的buffer深度也是5个微片。将该文的路由算法应用到三种不同的通信模式上:普通(uniform)模式,对调(transpose)模式,热点(hot spot)模式[7]。在普通模式下,每个IP核随机的发送数据包去另一个IP核。在对调模式下,节点(i,j)IP核发送数据包去节点(5-i,5-j)IP核。在热点模式下,节点(3,3)IP核被设为热点,它比在普通模式下收到的数据包数量要高出10%。
图5显示了在普通模式下四种路由算法的性能。X轴代表的是每个节点的注入率,Y轴是数据包平均延迟。由图可得,在低注入率下(<0.038包/周期),四种路由算法的性能几乎相同。随着注入率的增大,由于网络变的阻塞,包传输延迟急剧上升。比较OE+FCFS和OE+BLIS特性曲线可得,在OE输出选择下,BLIS性能优于FCFS。同样的比较XY+FCFS和XY+BLIS特性曲线可知,在XY输出选择下,BLIS性能更优。在[4,7]中曾经说明XY路由算法比OE路由算法性能要优,这是因为在普通模式下,XY算法综合了全局和长远的负载信息,从而使网络的负载分配变的平稳。而OE算法基于的是局部短期的负载情况,只是对当前的数据包特性敏感,对于长久的通信缺乏平稳性。
图6显示了在对调模式下四种算法的性能。由图可知,在结合使用XY算法下,FCFS算法和BLIS算法性能几乎相同。在结合OE算法,FCFS算法的性能稍稍优于BLIS算法的性能。这是因为在对调通信模式下,很少出现多个输入同时请求一个输出的情况,从而输入选择对整个路由算法的性能影响很小。图7是在热点模式下四种算法的性能体现。不论是结合XY输出选择还是OE输出选择,同样可以得出BLIS算法的性能要优于FCFS算法的性能。此外,尽管在FCFS输入选择下,OE算法比XY算法性能要差。但在BLIS输入选择下,OE算法的性能却比较接近XY算法的性能。
以上实验均证明了输入选择的重要性。该文设计的BLIS输入选择很大程度上提高了NOC的路由效率。
3 结论
该文证明了输入选择对于路由效率的影响,并设计了一种基于阻塞程度的输入选择算法(BLIS)。BLIS是根据上流switch的阻塞情况,赋予那些比较繁忙的输入沟道更高的优先权来输出。在高负载情况下,促使阻塞区域得以继续通信,减少了网络的阻塞。与输出选择机制结合使用,该文设计了四种路由方案。实验证明除了在对调模式下,BLIS输入选择与传统的FCFS输入选择性能相近外,其余模式下,BLIS性能均优于FCFS。在一些模式下,BLIS还能使复杂度低硬件需求少的XY路由算法在性能上接近甚至超过高复杂度硬件需求高的算法。
参考文献
[1]Benini L,De Micheli G.Networks on chips:A new SoC paradigm[J].Computer,2002,(35):70-78.
[2]Henkel J,Wolf W,Chakradhar S.On-chip networks:A scalable,communication-centric embedded system design paradigm[J].VLSI De sign,2004(1):845-85.
[3]Dally W J,Towles B.Route packets,not wires:On-chip interconnection networks[J].DAC,2001:684-689.
[4]Hu J,Marculescu R.DyAD Smart routing for networks-on-chip[J].DAC,2004:260-263.
[5]Nilsson E,Millberg M,Oberg J,et al.Load distribution with the proximity congestion awareness in a network on chip[C].DATE,2003(1):126-7.
[6]Ni L M,McKinley P K.A survey of wormhole routing techniques in direct networks[J].Computer,1993(26):62-76.
路由机制 篇7
关键词：可靠性,安全性,DoS攻击
(一) 引言
在信息时代, 随着计算机的广泛应用和网络技术的快速发展, 网络中用户隐私安全问题已经成为互联网应用中迫切需要解决的问题。因此互联网环境下匿名通讯技术的研究正逐渐成为新的热点问题。在这些研究中, 匿名系统的评价指标主要集中在系统的安全性上, 即匿名有效性。然而, 目前的研究开始将衡量匿名系统的指标转向可用性和可靠性上, 因为事实上这些“次要”的特征也是很重要的:在某些情况下若系统是不可靠, 或者是不可用的, 将导致用户的通信处在一个不安全的状态下。
可靠性与安全紧密相关, 且难以观测和分析, 在难以对整个系统的安全造成威胁的状态下, 攻击者可通过有选择地降低系统的可靠性来代替大规模的拒绝服务攻击, 导致系统处于弱安全状态下。通过研究, 在通信无法被控制的情况下, 选择性DoS攻击比针对整个系统的攻击更容易实施, 也更有效。在可靠性很弱的情况下, 许多用户将会尝试再次通信, 这也就给实施攻击提供了更多的机会。
通过对重路由机制的匿名通信技术中低时延系统 (Tor) 和高时延系统 (如Mixminion邮件转发器) 分别实施攻击的成功程度的分析发现:在这些系统中, 随着共谋节点的增多, 处在选择性拒绝服务攻击下的系统更易受到攻击, 尤其是受传统的MIX架构的安全性的限制, 在攻击者实施DoS攻击下, 一个有着大部分共谋节点的匿名系统中匿名性在很大程度上会遭到破坏。
(二) Tor
Tor网络是一个被广泛应用的低时延的匿名通信网络, 自从2003年开始部署以来得到了快速的发展, 到2007年8月已经发展到1000个节点组成, 支持成百上千个用户。它的基本思想是:发送主机先与一系列Tor节点建立连接, 最后到达目的主机。通信通道以压缩的方式构建并分层加密, 因而每个节点只知道前一跳和下一跳路由。然而, 通信的低时延特性给通道中的第一跳和最后一跳节点提供了共谋的机会, 它们通过匹配转发的数据包的时间段很容易发现他们转发的是否同一数据流。
假设节点是随机选取的, 表示被攻击者控制的节点所占的比例, 那么表示任一个通信通道被控制的概率。
设Tor系统中路径的长度为l (l=3) , 若其中任何一个节点失效则通信失败。f表示路径上某个节点可靠的概率, 则此路径的可靠性为:R=fl。
Tor系统的提出者考虑到了选择性DoS攻击模式, 但并没有分析其影响。下面我们分析选择性DoS攻击对Tor的影响。假设共谋节点在他们无法控制整条路径的情况下实施DoS攻击, 这种攻击很容易实施:如果攻击者是路径中的第一个或最后一个转发节点, 这条路径将会很快被发现, 然后将它分别与那些路径上的第一个或最后一个是共谋节点的路径比较。如果匹配, 此条路径将被控制, 否则攻击者通过拒绝在路径上转发信息来废除此路径。若共谋节点位于路径的中间部分, 攻击者同样也会废除此路径, 除非他的前驱和后继节点被串通。
在这种攻击下, 路径中只有第一个和最后一个节点被控制, 或者路径仅由可靠的节点构成, 则此路径是可靠的。
其中RDoS表示在选择性DoS攻击下, Tor系统的可靠性。
图1表示当f=0.9时, Tor系统在选择性DoS攻击下的可靠性, 从图中可知, 可靠性随着被攻击者控制的节点数的增加而降低, 当t=0.6时达到最低, 随后又开始增加。这是因为从那点开始, (1-t) 2开始占主导, 即共谋节点开始较少地实施DoS攻击, 因为他们已控制了更多的节点。
当然, 我们希望共谋节点比例小于50%, 对于攻击者来说控制800个节点中的400个似乎很困难。然而, Tor网络中的节点是由自愿加入的, 且节点只需通过最小限度的认证即可, 所以某些组织以不同的身份来充当Tor系统中的多个节点不是不可能的, 它将控制大部分节点, 况且, 攻击者可以夸大自己的带宽来获得较高的有效的t值。
(三) Mix网络
下面我们讨论选择性DoS攻击对基于MIX网络的高时延系统 (如MixMaster, MixMinion系统) 的影响。
MIX的设想最早由David Chaum在1981年提出。Mix-Net系统由多个相互独立的Mix节点组成, 用户在这些Mix中随机选择构成发送路径, 然后用路径上所有MIX节点的公钥来分层加密消息并通过这些节点依次转发, 直到最终的接收者。每个MIX节点用自己的私钥解密后, 通过延时与重排序再将消息发送给指定的下一个MIX节点, 从而达到通信关系的匿名。Mixmaster, Mixminion系统是在Mix-Net上进一步发展起来的高时延系统, 它相对于低延时系统 (如Tor) 更能抵御计时攻击, 只有当攻击者控制了转发路径中的每个节点时, 消息的匿名性才会遭到破坏。
Mixmaster, Mixminion系统中提供了一种保证可靠性的策略:在完全独立的不同的路径上多次发送同一消息, 使得不同路径上的信息的无联系性减少了潜在的流量分析的可能性。以下的分析都是基于这种策略, 其中参数如下:
l:转发路径的长度 (假设发送同一消息的所有路径的长度相同)
w:转发同一消息的路径数 (不包括重复的)
t:Mix节点是诚实的概率
f:诚实的节点是可靠的概率
1. 常规分析
在被动攻击下, 我们分析Mix网络的安全性和可靠性。
(1) 安全性
只有当路径上的所有节点被控制, 此消息的匿名性才会遭到破坏, 所以MIX网络的安全性为:
Mix网络相对于低时延系统安全性更高, 因为随着l的增长其安全性呈指数级别的增长。例如, 当l=5时, 即使50%的节点共谋, 也只能获取3%的信息。当l的值越大时, 即使共谋节点的数量很大, 用户的信息也能保证安全。
(2) 可靠性
假设攻击者只是简单地转发所有的通信。
为了转发消息, 至少有一条完整的路径包含没有不可靠的Mix节点, 其概率为:
则MIX网络的可靠性为:
2. 选择性DoS攻击
与Tor相似, 攻击者通过实施选择性DoS攻击策略来最大化破坏消息的机会。攻击者通过利用共谋节点的密钥来解密消息从而判断在整个路径中是否存在诚实的节点, 在不被接收者发觉的情况下, 不能被追踪的消息要么抛弃要么以一种巧妙的方式被修改。因而, 发送者不得不发送更多的消息复件来加大此消息到达的几率, 这也增加了被敌人捕获的机会。
假设攻击者将抛弃所有他不能控制的通信, 因而消息被转发的条件是: (1) 路径中所有的节点都是共谋节点; (2) 路径中所有的节点是诚实和可靠的。
其中r为消息在某条路径上被转发的概率。
则在选择性DoS攻击下, MIX网络的可靠性为:
DoS策略并不会影响网络的安全性, 其结果同 (1) 。那么这种策略有什么优势呢?为了达到同级别的可靠性, 发送者必须多次发送消息复件, 这也给攻击者提供了更多捕获信息的机会。需要发送多少消息复件呢?
在DoS攻击下为了获得在被动攻击下同样的可靠性, 需要发送的消息复件的数量为:
其中wpas表示在被动攻击下发送的消息复件数。图2表示当l=5, f=0.90时, 为了获得95%的可靠性, t与w之间的关系, 参数l和f的选择是参照Mixminion系统。从图2中可知, 在DoS策略下, 需要的消息复件数w变得很大, 在t=0.5时达到最大值。
(四) 结论
通过研究表明, 在匿名通信系统中, 系统的可用性及匿名性都与可靠性密切相关。攻击者通过实施选择性DoS攻击在很大程度上能减小系统的匿名性, 而先前的研究中很少有提到这样的假设。
从研究中可以发现, 包含较少的诚实节点的路径容易受到DoS攻击, 因而如何通过检测恶意的不可靠的节点, 或确保路径上的大部分节点都是诚实的来预防拒绝服务攻击是我们今后研究的方向。
参考文献
[1]R.Dingledine and N.Mathewson.Anonymity loves company:Usability and the network effect.In R.Anderson, editor, Fifth Workshop on the Economics of Information Security (WEIS) , Cambridge, UK, June2006.
[2]P.Golle and A.Juels.Parallel mixing.In ACM Conference on Computer and Communications Security, pages220–226, Washington, DC, Oct.2005.ACM Press.
[3]G.Danezis, R.Dingledine, and N.Mathewson.Mixminion:Design of a Type III Anonymous Remailer Protocol.In Bellovin and Wagner[2], pages2-15.
[4]R.Dingledine, N.Mathewson, and P.F.Syverson.Tor:The Second-Generation Onion Router.In The13th USENIX Security Symposium, pages303–320, San Diego, CA, August2004.USENIX Association.
路由机制 篇8
关键词：Ad hoc网络,VCG机制,YWCR路由策略
0 引 言
Ad hoc是一种新型的网络构架技术。运用此技术的移动Ad hoc网络(Mobile Ad hoc NETwork,MANET)与传统的无线网络有很大不同,它通过移动节点间的相互协作来保证网络连接和数据传递。节点使用电池或其他易损耗的能源作为能量提供源,最大程度地节省能源是一项重要的系统设计指标。
本文首先对传统无线网络中的路由机制VCG进行了简单的分析,指出VCG机制运用在Ad hoc网络时所面临的路由欺骗。在此基础上,提出了一种加密安全路由策略—YWCR,该策略既保证了数据包转发的效率,又有效地防止了路由欺骗。并在文章的最后通过模拟试验进行了验证。
1 VCG机制中的欺骗路由
1.1 VCG机制简介
传统的无线网络中常常采用VCG[1]机制进行路由选择。在此机制中,网络中的每个节点拥有一张独立的票据,网络建立之初,管理节点根据各个节点声明的票值建立网络的路由表,从而选择最优的路径进行路由。
这个协议的关键是[2]:路由的效率取决于各个节点声明票值的真实性。真实性越高,路由表的正确性越高,路由的效率越高。而任意票值的不正确都会影响到网络路由的质量。
为了描述VCG机制,我们定义如下:
定义1 假设某个Ad hoc网络由有限个节点N组成:N={0,1,…,n};每个节点i在接收到数据包时,可以作出两种合理的选择:
a1:拒绝转发数据包,从而自身能源消耗为0,获得的回报值为0。
a2:转发数据包,消耗自身能源的同时获得相应的回报值。
定义2 定义节点i将数据包传递到节点j所得到的回报值为pij=cij/R(0<R<1)。其中cij为数据包传递时所消耗的能量,R为一固定值,由管理节点给出。
综合两个定义,我们可以得出两个结论:
(1) 节点i转发数据包得到的回报值大于消耗的能量值。促使了Ad hoc网络中数据的传递。
(2) 节点i转发数据包所消耗的能量越大,得到的回报值越大。从而促使各个节点选择a2,保证了网络路由的公平性[3]。
在本文中,我们选择Ci={ci0,ci1,…,cij,…,cin}作为节点i在VCG机制中节点的票值[4]。而具体回报值,在实际的移动Ad hoc网络中,往往会有多种体现形式[5]。
1.2 欺骗路由行为
在Ad hoc网络中,转发数据包所消耗的能量cij由发送节点i和接收节点j所共同决定。我们给出定义3。
定义3 定义节点i将数据包传递到节点j后所消耗的能量cij=pemit/Tj。其中pemit为节点i转发数据包时所使用的能量,Tj为节点j得到数据包后向i返回的确认信息的能量。
通过定义2和定义3可以最终得到:
pij=pemit/TjR (1)
可见pij由Pemit和Tj共同决定,而pemit和Tj分属于两个不同节点,这为恶意节点进行欺骗路由提供了可能。
我们用图1描述如下:
如图1,节点i以pemit=5发出数据包,节点j实际应当返回Tj=5。令R=0.5,图中路线上标出的数字表示各个节点数据包传递时所消耗的能量值。而在实际过程中,节点i接收到Tj后,为了得到较高的回报值,私自将cij的计算定义为:cij=pemit/Tj*6。此时作为节点j有以下两种选择:
(1) 如果返回真实值Tj=5,则cij=5/5*6=6。pi=6/0.5=12。
(2) 节点采用欺骗手段,Tj=15,则cij=5/15*6=2,pi=2/0.5=4。
如果节点j采用选择(1),会采用路线二进行数据传递,cji为0,pji为0;如果选择(2),将采用路线一进行数据包传递,pji不为0。即如果节点i进行了欺骗,将促使节点j同时选择欺骗获得利益。最终导致整个网络的瘫痪。
为了解决上述问题,本文以下部分提出了YWCR策略,用于解决Ad hoc网络中VCG机制面临的欺骗问题。
2 YWCR策略
在网络建立之初,我们选择网络中的某个节点d作为网络的管理节点。然后,任选源节点s以由小到大的能量E0,E1,…,El,…,En发送包含节点s特征数据rs的数据包到目的节点d。
数据包路由经过某个中途节点i时,节点i将特征数据ri加入其中。当数据包到达管理节点d后,节点d根据到达的数据包进行分析,直接确定pij值。在公式(1)中,由于pemit的值已经确定,此时Tj值相应被确定下来。由此,YWCR策略成功地杜绝了节点的欺骗。
在策略实现中,需要解决的问题主要有以下两个:
问题1:如何保证在路由过程中各节点的特征数据不被篡改,为节点d进行正确的分析提供保障?
我们让节点i和节点d之间分享密钥Kid,当从节点s发出的数据包经过节点i时,节点i将收到的消息用密钥Kid进行加密,并将消息验证码(MAC)放在消息的末尾。
在消息最终到达管理节点d后,d根据密钥Kid对消息进行解密,由于Kid只由节点i和管理节点d分享,任何其他节点的篡改,都将导致解密后的消息与消息验证码不符,从而可以迅速找出恶意节点,为管理节点d进行分析提供保障。
问题2:管理节点d如何根据收到的数据包来分析确定pij?
如图2,我们用节点相互连接虚线段上的数字表示数据包能够成功传递时所需要的最小能量。我们可以假设Eix<Eij。当节点i按照能量由小到大的顺序发出数据包时,可以分成三个阶段:
(1) 当能量很小时,数据包没有任何途径能够到达节点j,节点d所收到的数据包中不包含rj。
(2) 当能量Eij>El>Eix时,数据包可以到达节点j,节点d所收到的数据包包含了ri和rj,但是ri和rj不相邻,之间存在rx,…,ry。
(3) 当El>=Eij时,数据包从节点i直接到达节点j,节点d所收到的数据包中包含了相邻的ri和rj。
我们选择El=Eij作为pij,过程结束后,节点d收集到数组P={pij;i,j∈{1,…,n}}。
在数组P的基础上,管理节点建立整个网络路由表。在此后的路由过程中,采用Dijkstra's算法,选择最优路径,从而可以最大程度地减少了整个网络在路由过程中所消耗的能量。
3 模拟试验
我们通过模拟试验来验证YWCR策略的效果和性能,使用的模拟实验环境是NS-2模拟器;仿真环境:节点个数:30;节点所处空间:2000×2000m2;传输能量:14dBm;模拟时间:300s;Mac层协议:802.11协议。我们认为整个过程中存在着恶意节点的随机欺骗干扰。
在这里我们主要验证协议的两点:
(1) 对于整个网络而言,考虑协议的有效性:网络的管理节点是否为数据包的路由选择了最佳的路由路径,从而可以在最大程度上节省整个系统的能源消耗。
(2) 对于单个节点而言,考虑协议的公平性:消耗能源较多的节点同时也应当得到较多的回报值,有效地避免恶意节点的欺骗行为。
首先,我们总结数据如图3,表示了模拟网络中各节点所处位置和整个过程中自身所消耗能量的大小关系。
每个节点由一个圆圈表示,圆圈的半径代表了节点在数据包转发过程中所消耗的能量多少。可以看出,离区域中心越近并且连接的节点越多,在路由过程中所起到的作用越大,消耗的能源相应也越多。由此表明网络选择了最佳的路径进行数据转发,在最大程度上节省整个系统的能源消耗,体现了协议的有效性。
然后,我们任选其中的六个节点进行比较,如图4中反映了网络中六个节点在每个50秒内获得回报的情况,结合图3进行分析,可以看出消耗较多能量的节点相应地获得了较多的回报,而消耗能量较少的节点相应获得了较少的回报,从而证明了YWCR策略的公平性。
4 结 语
论文根据Ad hoc移动网络独有的特征,在VCG机制的基础上,通过对网络中恶意节点的路由欺骗进行分析,提出了基于密钥加密和消息验证码(MAC)的YWCR策略。该策略通过对发送数据中添加加密信息的方法,在网络建立之初为移动Ad hoc网络建立路由表,从而可以在保证网络数据包传输效率的前提下,杜绝恶意节点的欺骗行为。
我们的试验中,在网络建立之初建立了整个网络的路由表。并没有考虑到由于Ad hoc网络的移动性,而产生的网络拓扑结构的变化。在实际的Ad hoc网络应用当中,我们还需要选择适当的时间来重复网络建立之处对路由表进行重构工作,从而保证在任意时间都能得到较高的路由效率。
参考文献
[1] Zhong S,Chen J,Yang Y R.Sprite,a simple,cheat-proof,credit-based system for mobile ad-hoc networks.In Proceedings of IEEE INFOCOM,San Francisco,CA,Apr.2003.
[2]Anderegg L,Eidenbenz S.Ad hoc-VCG:a truthful andcost-ef-cient rou-ting protocol for mobile Ad hoc networkswith selfish agents.In Proceed-ings of the Ninth International Conference on Mobile Computing and Networking(Mobicom),San Diego,CA,Sept.2003.
[3]Cagalj M,Ganeriwal S,Aad I,Hubaux J P.On selfish behavior in cs-ma/ca networks.In Proceedings of IEEE INFOCOM,Miami,Florida,USA,March2005.
[4]Wang W,Li X Y,Wang Y.Truthful multicast in sel-sh wireless net-works.In Proceedings of the Tenth International Conference on Mobile Computing and Networking(Mobicom),Philadelphia,PA,Sept.2004.