经典路由算法
一、先验式路由协议(DSDV)
先验式路由协议是一种基于表格的路由协议。在这种协议中，每个节点维护一张或多张表格，这些表格包含到达网络中其它所有节点的路由信息。当检测到网络拓扑结构发生变化时，节点在网络中发送路由更新信息。收到更新信息的节点更新自己的表格，以维护一致的、及时的、准确的路由信息。
不同的先验式路由协议的区别在于拓扑更新信息在网络中传输的方式和需要存储的表的类型。先验式路由协议不断的检测网络拓扑和链路质量的变化，根据变化更新路由表，所以路由表可以准确地反映网络的拓扑结构。源节点一旦需要发送报文，可以立即得到到达目的节点的路由。
（DSDV、OLSR路由协议等很多普通的因特网路由协议）它们查找路由是不依赖于路径上的节点是否要发包，而是每个节点维护一张包含到达其它节点的路由信息的路由表。节点间通过周期性的交换路由信息来不断更新自身的路由表，以便能够及时的反映网络拓扑结构和变化，以维护一致的、及时的、准确的路由信息。
DSDV:目的节点序列距离矢量协议（待补充）
可以解决路由成环问题，每一个节点维持一个到其它节点的路由表，表的内容为路由的“下一跳”节点。
1）给每条路径增加了一个序列号码
2）每个目的节点会定期广播一个单调递增的偶数序列号号码
3）当一个节点发现它到某个目的节点的路径断开时，它把到这个节点的距离
设为无穷大。并且将这条路径的序列号加1（此时为奇数），然后向网络中
广播这个更新包。当这条路径修复时，它又将序列号加1然后广播出去。
换另一种方式来说，每个节点都保持着一张路由表，路由表中的每一项记录了
它到目的节点的距离和序列号，也就是（s，d）。我们假设有一目的节点为D，
当以下任何一情况发生时，都会发送更新：
1）D定期将自己的序列号加2并广播出去，即（S，0）
2）如果节点X要通过Y到达节点D，当X和Y之间的连接断开后，X将到D的路径的序列号加1，同时将路径值设为∞，然后将信息发送给邻居。
参考资料：https://www.doczj.com/doc/7f6940947.html,/candycat1992/article/details/8100146CSDN博客DSDV协议
DSDV创新之处是为每一条路由设置一个序列号，序列号大的路由为优选路由，序列号相同时，跳数少的路由为优选路由。正常情况下，节点广播的序列号是单调递增的偶数，当节点B发现到节点D的路由(路由序列号为s)中断后，节点B 就广播一个路由信息，告知该路由的序列号变为s+l，并把跳数设置为无穷大，这样，任何一个通过B发送信息的节点A的路由表中就包括一个无穷大的距离，这一过程直到A收到一个到达D的有效路由(路由序列号为s+1-1)为止。
在此方案中，网络内所有的移动终端都建立一个路由表，包括所有的目的节点到达各个目标节点的跳跃次数(或标识距离矢量的路径矩阵)。每个路由记录都有一个由目标节点设定的序列号。序列号使移动终端可以区分当前有效路由路径和已过时的路由路径。路由表周期性地做全网更新以维护全网的通信有效性。通常，为了减少由于路由表更新而产生的大量路由信息传递，减少网络路由开销，可以采用两种路由更新方式。
1）第一种是全清除方式：
即通过多个网络协议数据单元将路由更新信息在全网中传输。如果网络内终端出现移动，则产生的新路由分组信息不定期的传达至网络内所有终端。
2）第二种是部分更新方式：
或称为增量更新方式，即在最后一次全清除传输后，只传递那些涉及变化了的路
由信息进行传输，这些信息通常被放置在一个标准的NPDU里，从而减少路由信息的传递量。在增量更新方式中移动终端可以增加另外一个附加的表来存储路由更新信息。
新路由信息的广播信息包含目标节点的地址，到每个目标节点的跳数、接收信息的序列号，以及独有的广播序列号。新路由信息适用最新的序列号。如果两次更新具有相同的序列号，则具有较小的距离矢量阵的路由具有优先权。因为它代表路径最短(或跳数最少)。在通常情况下，从源节点到目的节点可能存在多条路径，在最佳路由路径的确定过程中，移动终端跟踪不同路由路径的时间，最佳路由路径就是时间最短的路径。在找到最佳路径之前，该时间呈收敛性涨落。一旦路径确定，这些信息就存放到每一个终端的路由表中，直到节点收到新的路由信息。
二、反应式路由协议(AODV)
反应式路由选择协议是一种当需要一条从源节点到目的节点的路径进行数据发送时才查找路由的路由选择方式。
节点并不保存整个网络的及时准确的路由信息。当源节点要向目的节点发送报文时，源节点在网络中发起路由查找过程，找到相应的路由后，才开始发送报文。为了提高效率，节点可以将找到的路由保存在缓存中供后续发送使用。反应式路由协议按需路由的特点可以较好地适应节点移动较为频繁的无线网络环境，节点发生移动后，只需要更新需要发送数据的相关路径的路由信息即可。AODV: adhoc on-demand distance vetor routing 无线自组网按需平面距离矢量路由协议
当一个节点需要给网络中的其他节点传送信
息时，如果没有到达目标节点的路由，则必须先以
多播的形式发出路由请求消息RREQ (route request
packet)。RREQ报文中记录着发起节点和目标节点
的网络层地址。
邻近节点收到RREQ，首先判断目标节点是否
为自己。如果是，则向发起节点发送路由应答消息
RREP (route reply packet)；如果不是，则首先在路
由表中查找是否有到达目标节点的路由，如果有，
则向源节点单播RREP，否则继续转发RREQ进行
查找。直至发现目的节点。
在网络资源充分的情况下，AODV协议可以通过定期广播hello报文来维护路由，一旦发现某一个链路断开，节点就发送ERROR报文通知那些因链路断开而不可达的节点删除相应的记录或者对已存在的路由进行修复。
在AODV中，整个网络都是静止的除非有连接建立的需求。这就是说一个网络节点要建立连接时才广播一个连接建立的请求。其他的AODV节点转发这个请求消息，并记录源节点，和回到源节点的临时路由。当接收连接请求的节点
知道到达目的节点的路由时，就把这个路由信息按照先前记录的回到源节点的临时路由发回源节点。于是源节点就开始使用这个经由其他节点并且有最短跳数的路由。当链路断掉，路由错误就被回送给源节点，于是源节点就重新发起路由查找的过程。
参考资料：https://https://www.doczj.com/doc/7f6940947.html,/item/AODV/7811971?fr=aladdin百度百科AODV
三、基于位置的路由协议(GPSR)
GPSR路由协议：greedy perimeter stateless routing
GPSR路由算法是使用地理位置信息实现路由（非辅助作用）的一种算法，它使用贪婪算法来建立路由。当节点S需要向节点D转发数据分组的时候，它首先在自己的所有邻居节点中选择一个距节点D最近的节点作为数据分组的下一跳，然后将数据传送给它。该过程一直重复，直到数据分组到达目的节点D 或某个最佳主机。
贪心算法：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
一般步骤是：
1.建立数学模型来描述问题；
2.把求解的问题分成若干个子问题；
3.对每一子问题求解，得到子问题的局部最优解；
4.把子问题的局部最优解合成原来问题的一个解。
参考资料：https://www.doczj.com/doc/7f6940947.html,/qq_32400847/article/details/51336300从零开始学贪心算法
空洞问题：
产生或收到数据的节点向以欧氏距离计算出的最靠近目的节点的邻节点并向其转发数据,但由于数据可能会到达没有比现节点更接近目的点的区域(称为空洞),导致数据无法传输。
解决方法：当出现这种情况时,空洞周围的节点能够探测到,并利用右手法则沿空洞周围传输来解决此问题。
优点：
1)该协议避免了在节点中建立、维护、存储路由表,只依赖直接邻节点进行路由
选择,几乎是一个无状态的协议;
2)且使用接近于最短欧氏距离的路由,数据传输时延小;并能保证只要网络连通
性不被破坏,一定能够发现可达路由。
缺陷：需要GPS定位系统或其他定位方法协助计算节点位置信息。
参考资料：https://www.doczj.com/doc/7f6940947.html,/showcontent_38756.htm无线网状网络的路由协议分析
路由算法是路由协议必须高效地提供其功能，尽量减少软件和应用的开销。 路由器使用路由算法来找到到达目的地的最佳路由。 关于路由器如何收集网络的结构信息以及对之进行分析来确定最佳路由，有两种主要的路由算法：总体式路由算法和分散式路由算法。采用分散式路由算法时，每个路由器只有与它直接相连的路由器的信息——而没有网络中的每个路由器的信息。这些算法也被称为DV（距离向量）算法。采用总体式路由算法时，每个路由器都拥有网络中所有其他路由器的全部信息以及网络的流量状态。这些算法也被称为LS（链路状态）算法。 收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。路由更新信息遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。 路由算法的核心是路由选择算法，设计路由算法时要考虑的技术要素有： 1、选择最短路由还是最佳路由； 2、通信子网是采用虚电路操作方式还是采用数据报的操作方式； 3、采用分布式路由算法还是采用集中式路由算法； 4、考虑关于网络拓扑、流量和延迟等网络信息的来源； 5、确定采用静态路由还是动态路由。 各路由算法的区别点包括：静态与动态、单路径与多路径、平坦与分层、主机智能与路由器智能、域内与域间、链接状态与距离向量。 链接状态算法（也叫做短路径优先算法）把路由信息散布到网络的每个节点，不过每个路由器只发送路由表中描述其自己链接状态的部分。 距离向量算法（也叫做 Bellman-Ford算法）中每个路由器发送路由表的全部或部分，但只发给其邻居。 也就是说，链接状态算法到处发送较少的更新信息，而距离向量算法只向相邻的路由器发送较多的更新信息。 metric是路由算法用以确定到达目的地的最佳路径的计量标准，如路径长度。
路由算法及分类 路由算法及分类： 1、非自适应算法，静态路由算法 不能根据网络流量和拓扑结构的变化更新路由表，使用静态路由表，也称为固定式路由选择算法。 特点：简单，开销少；灵活性差。 2、自适应算法，动态路由算法 可根据网络流量和拓扑结构的变化更新路由表。 特点：开销大；健壮性和灵活性好。 3、最优化原则（optimality principle） 如果路由器J 在路由器I 到K 的最优路由上，那么从J 到K 的最优路由会落在同一路由上。 4、汇集树（sink tree） 从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树，称为汇集树； 路由算法的目的是找出并使用汇集树。 几种典型的路由选择算法： 1、最短路径路由算法（Shortest Path Routing） 1）基本思想 构建子网的拓扑图，图中的每个结点代表一个路由器，每条弧代表一条通信线路。为了选择两个路由器间的路由，算法在图中找出最短路径。
2）测量路径长度的方法 结点数量 地理距离 传输延迟 距离、信道带宽等参数的加权函数 3）Dijkstra算法 每个结点用从源结点沿已知最佳路径到本结点的距离来标注，标注分为临时性标注和永久性标注； 初始时，所有结点都为临时性标注，标注为无穷大； 将源结点标注为0，且为永久性标注，并令其为工作结点； 检查与工作结点相邻的临时性结点，若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注，则用新计算得到的和重新标注该结点； 在整个图中查找具有最小值的临时性标注结点，将其变为永久性结点，并成为下一轮检查的工作结点； 重复第四、五步，直到目的结点成为工作结点； 2、洪泛及选择洪泛算法 1）洪泛算法（Flooding） 属于静态路由算法 a)基本思想 把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。
路由器原理及常用的路由协议、路由算法 近十年来，随着计算机网络规模的不断扩大，大型互联网络（如Internet）的迅猛发展，路由技术在网络技术中已逐渐成为关键部分，路由器也随之成为最重要的网络设备。用户的需求推动着路由技术的发展和路由器的普及，人们已经不满足于仅在本地网络上共享信息，而希望最大限度地利用全球各个地区、各种类型的网络资源。而在目前的情况下，任何一个有一定规模的计算机网络（如企业网、校园网、智能大厦等），无论采用的是快速以大网技术、FDDI技术，还是ATM技术，都离不开路由器，否则就无法正常运作和管理。 1 网络互连 把自己的网络同其它的网络互连起来，从网络中获取更多的信息和向网络发布自己的消息，是网络互连的最主要的动力。网络的互连有多种方式，其中使用最多的是网桥互连和路由器互连。 1.1 网桥互连的网络 网桥工作在OSI模型中的第二层，即链路层。完成数据帧（frame）的转发，主要目的是在连接的网络间提供透明的通信。网桥的转发是依据数据帧中的源地址和目的地址来判断一个帧是否应转发和转发到哪个端口。帧中的地址称为“MAC”地址或“硬件”地址，一般就是网卡所带的地址。 网桥的作用是把两个或多个网络互连起来，提供透明的通信。网络上的设备看不到网桥的存在，设备之间的通信就如同在一个网上一样方便。由于网桥是在数据帧上进行转发的，因此只能连接相同或相似的网络（相
同或相似结构的数据帧），如以太网之间、以太网与令牌环（token ring）之间的互连，对于不同类型的网络（数据帧结构不同），如以太网与X.25之间，网桥就无能为力了。 网桥扩大了网络的规模，提高了网络的性能，给网络应用带来了方便，在以前的网络中，网桥的应用较为广泛。但网桥互连也带来了不少问题：一个是广播风暴，网桥不阻挡网络中广播消息，当网络的规模较大时（几个网桥，多个以太网段），有可能引起广播风暴（broadcasting storm），导致整个网络全被广播信息充满，直至完全瘫痪。第二个问题是，当与外部网络互连时，网桥会把内部和外部网络合二为一，成为一个网，双方都自动向对方完全开放自己的网络资源。这种互连方式在与外部网络互连时显然是难以接受的。问题的主要根源是网桥只是最大限度地把网络沟通，而不管传送的信息是什么。 1.2 路由器互连网络 路由器互连与网络的协议有关，我们讨论限于TCP／IP网络的情况。 路由器工作在OSI模型中的第三层，即网络层。路由器利用网络层定义的“逻辑”上的网络地址（即IP地址）来区别不同的网络，实现网络的互连和隔离，保持各个网络的独立性。路由器不转发广播消息，而把广播消息限制在各自的网络内部。发送到其他网络的数据茵先被送到路由器，再由路由器转发出去。 IP路由器只转发IP分组，把其余的部分挡在网内（包括广播），从而保持各个网络具有相对的独立性，这样可以组成具有许多网络（子网）互连的大型的网络。由于是在网络层的互连，路由器可方便地连接不同类型的网络，只要网络层运行的是IP协议，通过路由器就可互连起来。 网络中的设备用它们的网络地址（TCP／IP网络中为IP地址）互相通信。IP地址是与硬件地址无关的“逻辑”地址。路由器只根据IP地址来转发数据。IP地址的结构有两部分，一部分定义网络号，另一部分定义网
对路由算法的讨论 电气学院自动化1313 金莉萍131001260305 摘要：路由算法是提高路由协议功能，尽量减少路由时所带来开销的算法。路由算法在路由协议中起着至关重要的作用，采用何种算法往往决定了最终寻径结果。本文就对各路由算法在不同模型下，综合对比它们路径选择的差异以展开研究讨论。 关键词：路由算法差异不同模式研究讨论 随着科学技术的飞速发展，不仅传统业务流量大大增加，而且出现了许多新业务，如语音、数据和多媒体应用等对网络传输质量的要求差别很大，关于IP网络相关问题变得日益尖锐，特别是宽带业务，对网络性能加转发速度、流量控制以及网络的可扩展性等提出了较高的要求、随着主干网链路传输速度的不断提高，IP网络中节点上的包转发成了网络的瓶颈，在不断地需求下，人们提出了新的高效的路由算法，这种算法是通过提高网络的调节和控制功能使流量分布更加合理，以达到尽可能减少网络阻塞、最小的网络代价、分布的网络负载等目标。路由算法，又名选路算法，可以根据多个特性来加以区分。实现路由算法的软件必须运行在物理资源有限的计算机上时高效尤其重要。路由算法必须健壮，即在出现不正常或不可预见事件的情况下必须仍能正常处理，例如硬件故障、高负载和不正确的实现。因为路由器位于网络的连接点，当它们失效时会产生重大的问题。最好的路由算法通常是那些经过了时间考验，证实在各种网络条件下都很稳定的算法。 就我看来，一个理想的路由算法应该在计算上应简单。路由选择的计算不应使网络通信量增加太多的额外开销。 算法应具有稳定性。在网络通信量和网络拓扑结构相对稳定的情况下，路由算法应收敛于一个可以接受的解，而不应使得出的路由不停的变化。 算法必须是正确的和完整的。这里，“正确”的含义是指沿着各路由表所指引的路由，分组一定能够最终到达目的网络和目的主机。 算法应能适应通信量和网络拓扑的变化，这就是说要有自适应性。当网络中的通信量发生变化时，算法能自适应的改变路由以均衡个链路的负载。等某个或某些节点、链路发生故障不能工作，或者修理好了再投入运行时，算法也能及时的改变路由。有时称这种自适应性为“稳健性”。 算法应是最佳的。路由选择算法应当能够找出最好的路由，使得分组平均延时最小而网络的吞吐量最大。我们希望得到“最佳”的算法，但这并不是最重要的。对于某些网络，网络的可靠性有时要比最小的分组平均延时或最大吞吐量更加重要。因此，所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。 一个实际的路由选择算法，应尽可能接近于理想算法。在不同的应用条件下对以上提出的六个方面也可有不同的侧重。 所以，路由是个非常复杂的问题，因为它是网络中的所有结点共同协调工作的结果。 路由算法应是公平的。路由选择算法应对所有用户（除了少数优先级高的用户）都是平等的。例如，若仅仅使某一对用户的端到端时延为最小，但却不考虑其他的广大用户，这就明显的不符合公平性的要求。 路由算法的核心是路由选择算法，常见的路由选择算法有最短路径法、扩散法、基于流量的路由选择、距离向量路由选择、链路状态路由选择、分级路由选择、移动主机的路由选择、组播路由选择、广播路由选择。 这种算法是个非常复杂的问题，因为它是网络中的所有节点共同协调工作的结果。其次，路由选择的环境往往是不断变化的，而这种变化有时无法事先知道，例如，网络中出现了某些故障。此外，当网络发生拥塞时，就特别需要有能缓解这种拥塞的路由选择策略，但恰好在这种条件下，很难从网络中的各结点获得所需的路由选择信息。
无线传感器网络中AODVjr路由算法改进* 摘要：目前无线传感器网络主要采用zigbee协议，而zigbee 协议中aodvjr路由算法查找路由时容易引起广播风暴。根据aodvjr 算法中路由请求命令帧结构和路由应答命令帧结构的特点，研究出一种改进的aodvjr路由算法。改进算法中通过命令帧结构中的命令选项保留字，取保留字第0位控制命令帧传输的方向性，该位为1表示向该节点的子节点方向传输，该位为0表示目的地不在该节点的子节点范围内。利用omnet++4.1进行的仿真实验结果表明，改进的aodvjr路由算法能有效减少通信量，降低跳数，节约网络的整体能量，同时提高了网络的传输效率。 关键词： zigbee； aodvjr；广播风暴； omnet 中图分类号：tp393 文献标志码：a 文章编号：1006-8228（2013）01-09-03 improvement of aodvjr routing algorithm in wireless sensor network zou guoxia， tang jianqing （guilin university of aerospace technology， guilin，guangxi 541004， china） abstract： at present， zigbee protocol is mainly applied in wireless sensor network. however， it is easier to arouse a broadcast storm when using the aodvjr routing algorithm.
经典路由算法 一、先验式路由协议(DSDV) 先验式路由协议是一种基于表格的路由协议。在这种协议中，每个节点维护一张或多张表格，这些表格包含到达网络中其它所有节点的路由信息。当检测到网络拓扑结构发生变化时，节点在网络中发送路由更新信息。收到更新信息的节点更新自己的表格，以维护一致的、及时的、准确的路由信息。 不同的先验式路由协议的区别在于拓扑更新信息在网络中传输的方式和需要存储的表的类型。先验式路由协议不断的检测网络拓扑和链路质量的变化，根据变化更新路由表，所以路由表可以准确地反映网络的拓扑结构。源节点一旦需要发送报文，可以立即得到到达目的节点的路由。 （DSDV、OLSR路由协议等很多普通的因特网路由协议）它们查找路由是不依赖于路径上的节点是否要发包，而是每个节点维护一张包含到达其它节点的路由信息的路由表。节点间通过周期性的交换路由信息来不断更新自身的路由表，以便能够及时的反映网络拓扑结构和变化，以维护一致的、及时的、准确的路由信息。
DSDV:目的节点序列距离矢量协议（待补充） 可以解决路由成环问题，每一个节点维持一个到其它节点的路由表，表的内容为路由的“下一跳”节点。 1）给每条路径增加了一个序列号码 2）每个目的节点会定期广播一个单调递增的偶数序列号号码 3）当一个节点发现它到某个目的节点的路径断开时，它把到这个节点的距离 设为无穷大。并且将这条路径的序列号加1（此时为奇数），然后向网络中 广播这个更新包。当这条路径修复时，它又将序列号加1然后广播出去。 换另一种方式来说，每个节点都保持着一张路由表，路由表中的每一项记录了 它到目的节点的距离和序列号，也就是（s，d）。我们假设有一目的节点为D， 当以下任何一情况发生时，都会发送更新： 1）D定期将自己的序列号加2并广播出去，即（S，0） 2）如果节点X要通过Y到达节点D，当X和Y之间的连接断开后，X将到D的路径的序列号加1，同时将路径值设为∞，然后将信息发送给邻居。 参考资料：https://www.doczj.com/doc/7f6940947.html,/candycat1992/article/details/8100146CSDN博客DSDV协议 DSDV创新之处是为每一条路由设置一个序列号，序列号大的路由为优选路由，序列号相同时，跳数少的路由为优选路由。正常情况下，节点广播的序列号是单调递增的偶数，当节点B发现到节点D的路由(路由序列号为s)中断后，节点B 就广播一个路由信息，告知该路由的序列号变为s+l，并把跳数设置为无穷大，这样，任何一个通过B发送信息的节点A的路由表中就包括一个无穷大的距离，这一过程直到A收到一个到达D的有效路由(路由序列号为s+1-1)为止。 在此方案中，网络内所有的移动终端都建立一个路由表，包括所有的目的节点到达各个目标节点的跳跃次数(或标识距离矢量的路径矩阵)。每个路由记录都有一个由目标节点设定的序列号。序列号使移动终端可以区分当前有效路由路径和已过时的路由路径。路由表周期性地做全网更新以维护全网的通信有效性。通常，为了减少由于路由表更新而产生的大量路由信息传递，减少网络路由开销，可以采用两种路由更新方式。 1）第一种是全清除方式： 即通过多个网络协议数据单元将路由更新信息在全网中传输。如果网络内终端出现移动，则产生的新路由分组信息不定期的传达至网络内所有终端。 2）第二种是部分更新方式： 或称为增量更新方式，即在最后一次全清除传输后，只传递那些涉及变化了的路
车载网络综述及相关路由算法分析 Overview of V ANET and analysis of relevant routing algorithm 软网1301 王建帮 201192181 软网1301 张凯源 1车载网络综述 1.1相关概念 随着相关技术的发展，越来越多的无线设备开始被应用在汽车上，如远程钥匙、PDAs、 智能手机等，车载网络(英文术语为Vehicular Ad hoc Network，即VANET)的概念因而被 提出。在Vehicular ad hoc networks(VANETS):status, results, and challenges一文中，作者从 以下四个方面对VANET作出了较为全面的阐述： 1)Intelligent transportation systems (ITSs) VANET中节点可分为vehicles和Roadside Units(RSUs), 它们各自都有接收，存储，转发数据 以及路由的功能。两者区别在于，vehicles代表着移动的车辆，其位置是不断变化的，而 RSUs则是固定在路边的节点。 Fig. 1 Inter-vehicle communication
Fig. 2 Vehicle-to-roadside communication Fig. 3 Routing-based communication 由于实际应用的需要，在ITSs中存在三种可能的通信结构（communication configure-tion）:inter-vehicle, vehicle-to-roadside, and routing-based communication。这三者的实现都依赖于有关周围环境的精确且即时的信息，而要获取这样的信息，则需要精确的定位系统（如Bluetooth, Ultra-wide Band, ZigBee等）以及智能的通信协议（如GPS, DGPS）来提供支持。 2)Inter-vehicle communication The inter-vehicle communication configuration (Fig. 1) uses multi-hop multicast/broadcast to transmit traffic related in- formation over multiple hops to a group of receivers. 3)Vehicle-to-roadside communication The vehicle-to-roadside communication configuration (Fig. 2) represents a single hop broadcast where the road- side unit sends a broadcast message to all equipped vehicles in the vicinity. 4)Routing-based communication
第２６卷第６期 ２００８年６月 河南科学ＨＥＮＡＮＳＣＩＥＮＣＥＶｏｌ．２６Ｎｏ．６Ｊｕｎ．２００８ 收稿日期：２００８－０１－０７ 基金项目：郑州市技术研究与开发项目（０７４ＳＣＣＧ３８１１１） 作者简介：曹 敏（１９７０－），男，山东曹县人，工程师，硕士，主要从事网络技术研究苏玉（１９６８－），女，河南郑州人，副教授，主要从事网络技术及数据库方向研究． 文章编号：１００４－３９１８（２００８）０６－０６９１－０４关于几种路由算法的比较 曹敏，苏玉 （中州大学信息工程学院，郑州４５００４４） 摘要：通过几种路由算法在静态和动态的不同模型下的仿真实现，综合对比它们在不同模式下路径选择的差异， 从中选出目前解决网络瓶颈的较理想的流量控制算法． 关键词：实现；路由算法；比较 中图分类号：ＴＮ９１５．０１文献标识码：Ａ 近年来Ｉｎｔｅｒｎｅｔ不断速度发展，不仅传统业务流量大大增加，而且出现了许多新业务（如语音、数据和多媒体应用等）对网络传输质量的要求差别很大，如果ＩＳＰ依旧基于传统路由器发展大规模的ＩＰ网络，相关问题（如路由器转发部件的软件操作，构造高速路由器组件的开销，传统路由寻径机制在传输时难以预计的网络性能，网络无法提供针对特定业务的ＱｏＳ等）将变得日益尖锐［１］．特别是宽带业务，对网络性能加转发速度、流量控制以及网络的可扩展性等提出了较高的要求、随着主干网链路传输速度的不断提高，ＩＰ网络中节点上的包转发成了网络的瓶颈［２］．除了开发使用高速ＡＳＩＣ的路由器或采用新的转发模型，人们还提出了新的高效算法，如最小干涉路由算法、流量工程的约束路由算法等．这些算法都是通过提高网络的调节和控制功能使流量分布更加合理，以达到尽可能减少网络阻塞、最小的网络代价（ｃｏｓｔ）、分布的网络负载等目标［３］． 通过模拟仿真研究几种路由的算法在路径选择上的差异，从中比较它们的不同状态下的优缺点，评估出目前较为理想流量控制算法．这几种算法包括最小干涉路由算法（ＭｉｎｉｍｕｍＩｎｔｅｒｆｅｒｅｎｃｅＲｏｕｔｉｎｇＡｌｇｏｒｉｔｈｍ，ＭＩＲＡ）、最宽最短路径算法（Ｗｉｄｅｓｔ－ＳｈｏｒｔｅｓｔＰａｔｈ，ＷＳＰ）、最小临界Ｋ最短路由算法（ＬｅａｓｔＣｒｉｔｉｃａｌＫＳｈｏｒｔｅｓｔＲｏｕｔｉｎｇＡｌｇｏｒｉｔｈｍ，ＬＣＫＳ）和流量工程的的约束路由算法（ＴｒａｆｆｉｃＥｎｇｉｎｅｅｒｉｎｇＢａｎｄｗｉｄｔｈＣｏｎｓｔｒａｉｎｅｄＲｏｕｔｉｎｇＡｌｇｏｒｉｔｈｍ，ＴＥ－Ｂ）． 需要说明的是：文中选路时考虑的ＱｏＳ约束条件仅为带宽要求，这是由于其他ＱｏＳ要求（如时延、丢包率等），可以转化为等效带宽的形式． １几种路由算法 １．１最小干扰路由算法 算法是基于控制的约束路由算法寻址请求根据“最少的干扰”概念，以便网络能接受更多新的请求［３］．首先，为了满足所需带宽要求，要检查在每个网络上链路残余的带宽．可利用的带宽比所需的带宽小的链路将被剔出，所有能满足所需带宽的链接将作为候选链路被保留在一个链路集中．接着，优化网络的链路，这种路径选择算法的宗旨是在源和目的节点选择受其它链路流量干扰影响最少链路．通过将链路关键度映射为链路权重，然后用Ｄｉｊｋｓｔｒａ算法实现干扰的最小化．１．２最宽最短路径算法 这是最短的路径算法一种改进算法［４］．首先它检查可利用的带宽确定是否能满足新的寻址请求，还有当有一个以上最短路径存在在源和目的节点之间时，根据链接花费，算法会选择可利用带宽最大的链路，而不是像传统最短路径算法任意选择其中的一个． １．３最小关键链路ｋ最短路由算法 这是对最宽最短路径算法的一种改进算法［５］．这种算法不仅能发现ＳＤ之间具有相同花费的多个最短
什么是算法？ 简而言之，任何定义明确的计算步骤都可称为算法，接受一个或一组值为输入，输出一个或一组值。（来源：homas H. Cormen，Chales E. Leiserson《算法导论第3版》） 可以这样理解，算法是用来解决特定问题的一系列步骤（不仅计算机需要算法，我们在日常生活中也在使用算法）。算法必须具备如下3个重要特性： ［1］有穷性。执行有限步骤后，算法必须中止。 ［2］确切性。算法的每个步骤都必须确切定义。 ［3］可行性。特定算法须可以在特定的时间内解决特定问题， 其实，算法虽然广泛应用在计算机领域，但却完全源自数学。实际上，最早的数学算法可追溯到公元前1600年-Babylonians有关求因式分解和平方根的算法。 那么又是哪10个计算机算法造就了我们今天的生活呢？请看下面的表单，排名不分先后： 1. 归并排序（MERGE SORT），快速排序（QUICK SORT）和堆积排序（HEAP SORT） 哪个排序算法效率最高？这要看情况。这也就是我把这3种算法放在一起讲的原因，可能你更常用其中一种，不过它们各有千秋。 归并排序算法，是目前为止最重要的算法之一，是分治法的一个典型应用，由数学家John von Neumann于1945年发明。 快速排序算法，结合了集合划分算法和分治算法，不是很稳定，但在处理随机列阵（AM-based arrays）时效率相当高。 堆积排序，采用优先伫列机制，减少排序时的搜索时间，同样不是很稳定。 与早期的排序算法相比（如冒泡算法），这些算法将排序算法提上了一个大台阶。也多亏了这些算法，才有今天的数据发掘，人工智能，链接分析，以及大部分网页计算工具。 2. 傅立叶变换和快速傅立叶变换 这两种算法简单，但却相当强大，整个数字世界都离不开它们，其功能是实现时间域函数与频率域函数之间的相互转化。能看到这篇文章，也是托这些算法的福。 因特网，WIFI，智能机，座机，电脑，路由器，卫星等几乎所有与计算机相关的设备都或多或少与它们有关。不会这两种算法，你根本不可能拿到电子，计算机或者通信工程学位。（USA） 3.代克思托演算法（Dijkstra‘s algorithm）
一、路由器简介 (1).基本概念 路由器是工作在网络层上，可以连接不同类型的网络，能够选择数据传送路径并对数据进行转发的网络设备。路由器工作的目的就是选择最佳路径，把数据传递到目的地。 (2).路由表 路由器在接收到数据时，要对其传输路径进行选择。为了实现这一目标，路由器需要维护一个称为“路由表”的数据结构。概括来讲，路由表就是包含若干条目、供路由器选路时查询数据包传输路径的表项。 (3).选路策略和选路机制 一般来说，路由器要实现数据转发的功能，至少需要完成两方面的工作： a)根据数据包的目的地址和网络的拓扑结构选择一条最佳路径，把对应不同目的地址的最 佳路径存放在路由表中（找最佳路径的过程就相当于更新路由表的过程）； b)搜索路由表，决定向哪个接口转发数据，并执行相应的操作。 在上面的两方面工作中，前者是选路策略（Routing policy, 也称为路由选择策略）问题，而后者是选路机制（Routing mechanism, 也称为路由选择机制）问题。 选路策略的实质就是如何确定数据传送的最佳路径，它是通过建立并维护路由表开实现的。选路策略的不同，从本质上讲就是建立和维护路由表的方式不同；选路机制实际上就是如何查找路由表，并根据查表的结果把数据转发出去。 (4).自治系统和路由域 由于Internet规模太大，分布范围太广，所以所有路由器的路由表中对应每一个目的网络都有一个条目是不可能的，同样，也不可能采用一个全局的路由算法或协议。因此，Internet 将整个网络划分为若干个相对自治的局部系统，即自治系统（Autonomous System, AS）。自治系统可以定义为同一机构下管理的路由器和网络的集合。 世界各地的自治系统都通过自己的边界路由器连接到Internet的核心网上。一般来说，一个自治系统可以配置一个或多个边界路由器，自治系统内部的路由器或者网络通过边界路由器与其他自治系统或者Internet核心网进行通信。
路由算法介绍 网络层的作用：1、路由选择 2、网络互连 3、拥塞控制 4、为上层提供服务 网络层的主要功能是将分组从源机器路由到目标机器。完成路由选择的路由算法是网络层设计的最主要内容。 路由算法：它负责确定一个进来的分组应该被传送到哪一条输出线路上。 如果是数据报子网，将在每一个分组到达时作此决定 如果是虚电路子网，是在虚电路建立时决定，该连接上所有分组都将沿此线路传输 路由算法设计必须考虑的问题：正确性简单性健壮性稳定性公平性最优性路由算法的原则：按照某种指标(传输延迟,所经过的站点数目等)找到一条从源节点到目标节点的较好路径。 静态算法：不会根据当前测量或者估计的流量和拓扑结构，来调整它们的路由决策，所有的路由选择是预先在离线情况下计算好的，在网络启动的时候被下载到路由器中。 1、最短路径路由：
如图所示，图中的每个节点代表一台路由器，每条弧代表一条通信线路，线路上的数字是它的开销。现在我们想找到从A到D的最短路径。过程： （1）节点A标记为永久节点，依次检查每一个与A相邻的节点，并检查它们与A之间的距离。 （2）如果新的标记距离小于该节点原来的标记，说明找到了一条更短路径，该节点需要重新标记，作为暂时性标记 （3）检查整个图中所有有暂时性标记的节点，使其中具有最小标记的那个节点成为永久节点，并且作为下一个工作节点。 （4）重复上述过程，直到没有新的永久节点为止。 如下图所示 2、扩散法：每一个进来的分组将被发送到除了它进来的那条线路之外的每一条输出线路上。 产生的问题：会产生大量的重复分组。
解决办法： 在数据包头设一个计数器初值，每经过一个节点自动减1，计数值 为0 时，丢弃该数据包 在每个节点上建立登记表，则数据包再次经过时丢弃 缺点：重复数据包多，浪费带宽 优点：可靠性高，可用于并发数据库更新。极好的健壮性，可用于军事应用。常作为衡量标准，评价其它路由算法 现代计算机网络通常使用动态的路由算法（自适应算法），而不是上面介绍的静态路由算法，因为静态路由算法不会考虑到网络的当前负载情况。 自适应算法：随拓扑结构和流量的变化改变它们的路由决策，又称为动态路由算法。 1、 距离矢量路由：每个路由器维护一张表（即一个矢量），表中列出了当前抑制的到每个目标的最佳距离，以及所使用的线路。通过邻居之间互相交换信息，路由器不断更新它们内部的表。 举例： B A E F D C 2 3 7 6 1 8 5 4 延迟信息B
2020年计算机四级网络工程师复习要点：路由选择算法的分类 在INTERNET中，路由器采用表驱动的路由选择算法。路由表存储了可能的目地地址与如何到达目的地址的信息。 报考路由选择算法也称为自适应路由选择算法，其特点是能较好地适应网络状态的变化，但实现起来较为复杂，开销也比较大。路由表可以分为静态路由表和报考路由表： 1、静态路由表：是由人工方式建立的，网络管理人员将每一个目的地址的路径输入到路由表中。网络结构发生变化时，路由表无法自动地更新。 2、报考路由表：大型互联网网络通常采用报考路由表。在网络系统运行时，系统将自动运行报考路由选择协议，建立路由表。 一个自治系统重要的特点就是它有权决定在本系统内应采用何种路由选择协议。自治系统内部的路由选择称为域内路由选择，自治系统之间的路由选择称为域间路由选择。作为一个自治系统，其核心是路由寻址的“自治”。 INTERNET将路由选择协议分为两大类：内部网关协议IGP和外部网关协议EGP。 内部网关协议是在一个自治系统内部使用的路由选择协议，这与INTERNET 中其他自治系统选用什么路由选择协议无关。目前内部网关协议主要有：路由信息协议RIP和开放短路径优先协议OSPF。外部网关协议主要是边界网关协议BGP，路由选择算法和路由选择协议在概念上是不同的。网络上的主机、路由器通过路由选择算法去形成路由表，以确定发送分组的传输路径。而路由选择协议是路由器用来完成路由表建立和路由信息更新的通信协议。 路由信息协议是内部网关协议中使用广泛的一种协议，它是一种分布式、基于距离向量的路由选择协议，其特点是协议简单。路由信息协议是用于TCP/IP 系统和其他网络环境的距离矢量路由选择协议。路由信息协议RIP适用于相对较小的自治系统，它们的直径“跳数”一般小于15.因为每一个自治系统里的路由器都要与同一系统里的其他路由器交换路由表信息，当内部路由器的数目增加时，网络的RIP信息交换量会大幅度地增加。 短路径优先协议OSPF的主要特点： 1、使用分布式链路状态协议，而RIP使用距离向量协议。 2、OSPF协议要求路由器发送的信息是本路由器与哪些路由器相邻，以及链路状态的度量。链路状态度量主要是指费用、距离、延时、带宽等。
Z i g B e e路由算法分析
摘要基于IEEE802.15.4标准的ZigBee网络是一种具有强大组网能力的新型无线个域网，其中的路由算法是研发工作的重点。本文介绍了IEEE802.15.4标准及ZigBee规范的协议模型，重点研究了ZigBee协议网络层的路由算法，分析了Tree路由及Z-AODV路由算法，在此基础上提出了ZigBee网格型网络中基于数据特性的路由选择机制，该机制在网络性能和低功耗方面有明显的优势，并且可以平衡节点能量，最后简单介绍了ZigBee节点的硬件实现。 关键词 ZigBee协议；网络；IEEE802.15.4；路由算法；Tree路由；Z-AODV路由 1 概述 ZigBee技术是由英国Invensys公司、日本三菱电气公司、美国摩托罗拉公司以及荷兰飞利浦等公司在2002年10月共同提出设计研究开发的具有低成本、体积小、能量消耗小和传输速率低的无线通信技术。 2000年12月，IEEE 802 无线个域网（WPAN，Wireless Personal Area Network）小组成立，致力于WPAN无线传输协议的建立。2003年12月，IEEE正式发布了该技术物理层和MAC层所采用的标准协议，即IEEE 802.15.4协议标准，作为ZigBee技术的网络层和媒体接入层的标准协议。2004年12月，ZigBee联盟在IEEE 802.15.4 定义的物理层（PHY）和媒体接入层（MAC）的基础上定义了网络层和应用层，正式发布了基于IEEE 802.15.4的ZigBee标准协议。 2 网络层的研究
ZigBee技术的体系结构主要由物理层（PHY）、媒体接入层（MAC）、网络/安全层以及应用框架层组成，各层之间的分布如图1所示。 图1 ZigBee技术协议组成 PHY层的特征是启动和关闭无线收发器、能量检测、链路质量、信道选择、清除信道评估（CCA）以及通过物理媒体对数据包进行发送和接收。MAC层可以实现信标管理、信道接入、时隙管理、发送确认帧、发送连接及断开连接请求，还为应用合适的安全机制提供一些方法。它包含具有时间同步信标的可选超帧结构，采用免碰撞的载波侦听多址访问（CSMA-CA）。安全层主要实现密钥管理、存取等功能。网络层主要用于ZigBee的LR-WPAN网的组网连接、数据管理等。应用框架层主要负责向用户提供简单的应用软件接口（API），包括应用子层支持APS（Application Sub-layer Support）、ZigBee设备对象ZDO （ZigBee Device Object）等，实现应用层对设备的管理，为ZigBee技术的实际应用提供一些应用框架模型等，以便对ZigBee技术的开发应用。 网络层的定义包括网络拓扑、网络建立、网络维护、路由及路由的维护。 2.1 ZigBee的网络拓扑结构 ZigBee定义了三种拓扑结构：星型拓扑结构（Star），主要为一个节点与多个节点的简单通信设计；树型拓扑结构（Tree），使用分等级的树型路
Ad Hoc 中的常用路由算法分析 孙晓艳,李建东,张光辉,田红涛 (西安电子科技大学信息科学研究所 陕西西安 710071) 摘 要:在传统的移动无线In ternet 接入方式中,通常是以宽带有线接入网为支撑,无线用户只通过一跳(不需要在无线网中多次转接)就可以接入固定网络。在很多应用场合,如个人区域网、家域网、军事应用、抢险救灾等,无线网络没有固定的基础设施作支撑,移动用户的信息需要通过移动用户之间的多次中转才能到达目的用户,这种网络通常称为分布式或无中心式(A d hoc )网络。本文首先介绍了A d Hoc 网络,然后介绍了目前运用于A d Hoc 网络中的几种路由算法,并指出其优缺点。 关键词:A d Hoc ;D SDV ;CGSR ;W R P ;D SR ;AODV ;TORA 中图分类号:T P 30116 文献标识码:B 文章编号:1004373X (2003)1301804 Ana lysis of the Severa l Routi ng A lgor ith m s i n Ad Hoc SUN X iaoyan ,L I J iandong ,ZHAN G Guanghu i ,T I AN Hongtao (Institute of Info r m ati on Science ,X idian U niversity ,X i ′an ,710071,Ch ina ) Abstract :In traditi onal access m ethods to In ternet in mob ile and w ireless environm en t ,u ser can access to fixed netw o rk by one hop (w ithou t m u lti relay )based on w ideband access netw o rk 1In som e app licati on s ,such as personal local netw o rk ,hom e local netw o rk ,m ilitary app licati on ,em ergency rescue patien t care operati on s ,m essages from sou rce u sers can on ly arrive at destinati on term inals by m u lti relay (m u lti hop )among several mob ile u sers becau se w ireless netw o rk is infrastructu ral ,w h ich is so called distribu ted o r A d Hoc netw o rk 1Fo llow ing in troducti on to A d Hoc netw o rk concep ts ,rou ting algo rithm s u sually u tilized in A d Hoc 1 Keywords :A d Hoc ;D SDV ;CGSR ;W R P ;D SR ;AODV ;TORA 收稿日期:20030424 1 引 言 在通信基础设施很少或没有通信基础设施的地方,在现存的基础设施很昂贵或不方便使用的地方,例如学生使用笔记本电脑进行交互式的讲座时,商家在会议当中共享信息时,战士在战场上需要依靠信息获得地形状况[1,2]时,以及当洪水或地震后的紧急灾难援救人员共同协作时,如何来进行通信联系呢?这时就需要用A d Hoc 的思想来实现通信。A d Hoc 网络是在没有任何现存网络基础设施或是集中管理的情况下动态形成的暂时网络。由于无线节点的发射功率和无线网络接口传输范围的限制,多跳网络可能需要有一个节点或多个节点来和网络中的其他节点交换数据,而且网络中的移动节点动态的在他们之间建立路由以形成动态变化的网络。A d Hoc 网络的这个思想也称为无基础设施的网络[3]。所以由于A d Hoc 的存在,无线移动用户可能(在某种情况下)仍然可以通过一个A d Hoc 网络来交换信息。 在这种网络中,每一个移动节点不仅作为主机而且还作为路由器来为网络中的其他不 能直接通信的节点转发分组信息。通常,在A d Hoc 网络中需要考虑的移动性有:源节点的移动性(当源节点移动时必须把这种变化通知路由上游的节点)、目的节点的移动性(当目的节点移动时必须通知路由下游节点这种变化)和中转节点的移动性(对于路由中的这种变化,采用不同协议处理的方式也不同)。由于A d Hoc 网络中的节点并不是物理上相互连接,因此通信节点就必须寻找到网络的连接。通信节点寻找网络连接是通过发现来实现的。一个新节点可以通过检测其他节点发出的信标来和这个节点相连接,然后这个新加入的节点就通知主节点这条新的连接,这个信息就会在网络中得到进一步的广播(到协议所认为必要的范围内)。现在,当源节点试图建立到这个新加入节点的链路时,查询过程就可以通过广播消息的节点来进行。每一个A d Hoc 网络路由协议的节点都允许通过网络中的其他节点发现路由。随着通信技术的发展,人们对网络更大的移动性要求和军队对于传感器网络的 8 1
之前看到过许多与子网掩码的算法，今天在书上找到了一种简单的算法例如一个C类IP 由－－－>该网络的地址掩码为255.255.255.224（其主机位数为：32－27＝52的5 次方32个主机地址） 可以知道应该网络最多有255－224＋1＝32个网络地址可以使用，但全0,全1情况我们一般保留。 有一种简单算法可以得出该网络地址段内的最小地址与最大地址 算法简单实现如下 1、找出地址掩码中的0和1的交界处，也即192.199.170.82的第四字节"010010（十进制82）"－－－>取其前3位"010" 注： 【这里的主机位有5位（32-27=5）；82=26+24+21故取第四 字节的后五位】 2、将其后5位置0－－－>"01000(十进制64)"－－－>192.199.170. 643、将其后5位置1－－－>"0111(十进制95)"－－－>192.199.170.95因此该网络地址段内最大的IP为192.199.170.95，最小IP为 192.199.170.64,从这里得到的该网络段内 可以供使用的地址数95－64＋1＝32与上述255－224＋1＝32是一致的。 子网掩码常用算法： 一、利用子网数来计算 在求子网掩码之前必须先搞清楚要划分的子网数目，以及每个子网内的所需主机数目。
1)将子网数目转化为二进制来表示 2)取得该二进制的位数，为N 3)取得该IP地址的类子网掩码，将其主机地址部分的的前N位置1即得出该IP地址划分子网的子网掩码。 如欲将B类IP地址168.195.0.0划分成27个子网： 1)27=11011 2)该二进制为五位数，N = 5 3)将B类地址的子网掩码255.255.0.0的主机地址前5位置1，得到 255.255.248.0，即为划分成27个子网的B类IP地址168.195.0.0的子网掩码。 二、利用主机数来计算 1)将主机数目转化为二进制来表示 2)如果主机数小于或等于254（注意去掉保留的两个IP地址），则取得该主机的二进制位数，为N，这里肯定N<8。如果大于254，则N>8，这就是说主机地址将占据不止8位。 3)使用255.255.255.255来将该类IP地址的主机地址位数全部置1，然后从后向前的将N位全部置为0，即为子网掩码值。 如欲将B(c)类IP地址168.195.0.0划分成若干子网，每个子网内有主机700台 (17)： 1) 700=101100 2)该二进制为十位数，N = 10 (1001)
路由器原理及常用的路由协议、路由算法 [点击数：148 更新时间：2006年05月18日] 近十年来，随着计算机网络规模的不断扩大，大型互联网络（如Internet）的迅猛发展，路由技术在网络技术中已逐渐成为关键部分，路由器也随之成为最重要的网络设备。用户的需求推动着路由技术的发展和路由器的普及，人们已经不满足于仅在本地网络上共享信息，而希望最大限度地利用全球各个地区、各种类型的网络资源。而在目前的情况下，任何一个有一定规模的计算机网络（如企业网、校园网、智能大厦等），无论采用的是快速以大网技术、FDDI技术，还是ATM技术，都离不开路由器，否则就无法正常运作和管理。 1 网络互连 把自己的网络同其它的网络互连起来，从网络中获取更多的信息和向网络发布自己的消息，是网络互连的最主要的动力。网络的互连有多种方式，其中使用最多的是网桥互连和路由器互连。 1.1 网桥互连的网络
网桥工作在OSI模型中的第二层，即链路层。完成数据帧（fra me）的转发，主要目的是在连接的网络间提供透明的通信。网桥的转发是依据数据帧中的源地址和目的地址来判断一个帧是否应转发和转发到哪个端口。帧中的地址称为“MAC”地址或“硬件”地址，一般就是网卡所带的地址。 网桥的作用是把两个或多个网络互连起来，提供透明的通信。网络上的设备看不到网桥的存在，设备之间的通信就如同在一个网上一样方便。由于网桥是在数据帧上进行转发的，因此只能连接相同或相似的网络（相同或相似结构的数据帧），如以太网之间、以太网与令牌环（token ring）之间的互连，对于不同类型的网络（数据帧结构不同），如以太网与X.25之间，网桥就无能为力了。 网桥扩大了网络的规模，提高了网络的性能，给网络应用带来了方便，在以前的网络中，网桥的应用较为广泛。但网桥互连也带来了不少问题：一个是广播风暴，网桥不阻挡网络中广播消息，当网络的规模较大时（几个网桥，多个以太网段），有可能引起广播风暴（broadcasting storm），导致整个网络全被广播信息充满，直至完全瘫痪。第二个问题是，当与外部网络互连时，网桥会把内部和外部网络合二为一，成为一个网，双方都自动向对方完全开放自己的网络资源。这种互连方式在与