Ⅰ 什么是路由啊 路由的组成 以及路由的算法
路由：路由（routing）是指分组从源到目的地时，决定端到端路径的网络范围的进程。路由工作在OSI参考模型第三层——网络层的数据包转发设备。路由器通过转发数据包来实现网络互连。虽然路由器可以支持多种协议（如TCP/IP、IPX/SPX、AppleTalk等协议），但是在我国绝大多数路由器运行TCP/IP协议。路由器通常连接两个或多个由IP子网或点到点协议标识的逻辑端口，至少拥有1个物理端口。路由器根据收到数据包中的网络层地址以及路由器内部维护的路由表决定输出端口以及下一跳地址，并且重写链路层数据包头实现转发数据包。路由器通过动态维护路由表来反映当前的网络拓扑，并通过网络上其他路由器交换路由和链路信息来维护路由表。
路由器的组成：
RAM（随机存储器）
功能：存放路由表；存放ARP告诉缓存；存放快速交换缓存；存放分组交换缓冲；存放解压后的IOS；路由器加电后，存放running配置文件；
特点：重启或者断电后，RAM中的内容丢失。
NVRAM（非易失性RAM）
功能：存储路由器的startup配置文件；存储路由器的备份。
特点：重启或者断电后内容不丢失。
FLASH（快速闪存）
功能：存放IOS和微代码。
特点：重启或者断电后内容不丢失；可存放多个IOS版本（在容量许可的前提下）；允许软件升级不需替换CPU中的芯片。
ROM(只读存储器)
功能：存放POST诊断所需的指令；存放mini-ios；存放ROM监控模式的代码。
特点：ROM中的软件升级需要更换CPU的芯片（还好这种情况比较少遇到)
CPU（中央处理器）
衡量路由器性能的重要指标，负责路由计算，路由选择等。
背板：
背板能力是一个重要参数，尤其在交换机中。
路由算法：又名选路算法，可以根据多个特性来加以区分。算法的目的是找到一条从源路由器到目的路由器的“好”路径（即具有最低费用的路径[1]）。算法设计者的特定目标影响了该路由协议的操作；具体来说存在着多种路由算法，每种算法对网络和路由器资源的影响都不同；由于路由算法使用多种度量标准（metric），从而影响到最佳路径的计算。
算法分类：主要有RIP、IGRP（IGRP为 Cisco公司的私有协议）；链路状态路由协议基于图论中非常着名的Dijkstra算法，即最短优先路径（Shortest Path First， SPF）算法，如OSPF。在距离向量路由协议中，路由器将部分或全部的路由表传递给与其相邻的路由器；而在链路状态路由协议中，路由器将链路状态信息传 递给在同一区域内的所有路由器。 根据路由器在自治系统（AS）中的位置，可将路由协议分为内部网关协议 （Interior Gateway Protocol，IGP）和外部网关协议（External Gateway Protocol，EGP，也叫域 间路由协议）。域间路由协议有两种：外部网关协议（EGP）和边界网关协议（BGP）。EGP是为一个简单的树型拓扑结构而设计的，在处理选路循环和设置 选路策略时，具有明显的缺点，已被BGP代替。
Ⅱ 路由器结构
输入端口是物理链路和输入包的进口处。端口通常由线卡提供，一块线卡一般支持4、8或16个端口，一个输入端口具有许多功能。第一个功能是进行数据链路层的封装和解封装。第二个功能是在转发表中查找输入包目的地址从而决定目的端口（称为路由查找），路由查找可以使用一般的硬件来实现，或者通过在每块线卡上嵌入一个微处理器来完成。第三，为了提供QoS（服务质量），端口要对收到的数据包进行业务分类，分成几个预定义的服务级别。第四，端口可能需要运行诸如SLIP（串行线网际协议）和PPP（点对点协议）这样的数据链路级协议或者诸如PPTP（点对点隧道协议）这样的网络级协议。一旦路由查找完成，必须用交换开关将包送到其输出端口。如果路由器是输入端加队列的，则有几个输入端共享同一个交换开关。这样输入端口的最后一项功能是参加对公共资源（如交换开关）的仲裁协议。普通路由器中该部分的功能完全由路由器的中央处理器来执行，制约了数据包的转发速率（每秒几千到几万个数据包）。高端路由器中普遍实现了分布式硬件处理，接口部分有强大的CPU处理器和大容量的高速缓存，使接口数据速率达到10Gbps，满足了高速骨干网络的传输要求。
路由器的转发机制对路由器的性能影响很大，常见的转发方式有：进程转发、快速转发、优化转发、分布式快速转发。进程转发将数据包从接口缓存拷贝到处理器的缓存中进行处理，先查看路由表再查看ARP表，重新封装数据包后将数据包拷贝到接口缓存中准备传送出去，两次查表和拷贝数据极大的占用CPU的处理时间，所以这是最慢的交换方式，只在低档路由器中使用。快速交换将两次查表的结果作了缓存，无需拷贝数据，所以CPU处理数据包的时间缩短了。优化交换在快速交换的基础上略作改进，将缓存表的数据结构作了改变，用深度为4的256叉树代替了深度为32的2叉树或哈希表（hash），CPU的查找时间进一步缩短。这两种转发方式在中高档路由器中普遍加以应用。在骨干路由器中由于路由表条目的成倍增加，路由表或ARP表的任何变化都会引起大部分路由缓冲失效，以前的交换方式都不再适用，最新的交换方式是分布式快速交换，它在每个接口处理板上构建一个镜像（mirror）路由表和MAC地址表相结合的转发表，该表是深度为4的256叉树，但每个节点的数据部分是指向另一个称为邻接表的指针，邻接表中含有路由器成帧所需要的全部信息。这种结构使得转发表完全由路由表和ARP表来同步更新，本身不再需要额外的老化进程，克服了其它交换方式需要不断对缓存表进行老化的缺陷。
交换结构最常见的有总线型、共享内存型、Cross-bar空分结构型。总线型结构最简单，所有输入和输出接口挂在一个总线上，同一时间只有两个接口通过总线交换数据。其缺点是其交换容量受限于总线的容量以及为共享总线仲裁所带来的额外开销。在调度共享数据传输通道上必须花费一定的开销，而且总线带宽的扩展受到限制，制约了交换容量的扩张，一般在中档路由器中使用这种结构。共享内存型结构中，进来的包被存贮在共享存贮器中，所交换的仅是包的指针，这提高了交换容量，但它受限于内存的访问速度和存储器的管理效率，尽管存贮器容量每18个月能够翻一番，但存贮器的存取时间每年仅降低5%，这是共享存贮器交换开关的一个固有限制。共享内存型结构在早期的中低档路由器中普遍应用。Cross-bar空分结构相当于多条并行工作的总线，具有N×N个交叉点的交叉开关可以被认为具有2N条总线。如果一个交叉是闭合，输入总线上的数据在输出总线上可用，否则不可用。对流经它的数据不断进行开关切换，可见开关速度决定了交换容量，随着各种高速器件的不断涌现，这种结构的交换容量普遍达到几十Gbps以上，成为目前高端路由器和交换机的首选交换结构。
路由计算或处理部分主要是运行动态路由协议。接收和发送路由信息，计算出路由表，为数据包的转发提供依据。各种档次的路由器的路由表条目的大小存在很大差异，从几千条到几百万条不等，因此高端路由器的路由表的构造对路由查找速度影响很大，其路由表的数据结构常采用二叉树的形式，查找与更新的速度都比较快。
输出端口在包被发送到输出链路之前对包存贮，可以实现复杂的调度算法以支持优先等级要求。与输入端口一样，输出端口同样要能支持数据链路层的封装和解封装，以及许多较高级协议。
一般而言，路由器对一个数据包的交换要经过一系列的复杂处理，主要有以下几个方面：
1）压缩和解压缩
2）加密和解密
3）用输入/输出访问列表进行报文过滤
4）输入速率限制
5）进行网络地址翻译（NAT）
6）处理影响本报文的任何策略路由
7）应用防火墙特性对包进行检查
8）处理Web页缓冲的重定向
9）物理广播处理，如帮助性地址（ip help address）
10）利用启用的QoS机制对数据包排队
11）TTL值的处理
12）处理IP头部中的任选项
13）检查数据包的完整性
Ⅲ 计算机网络-网络层-路由器的构成
路由器是一种具有多个输入端口和多个输出端口的专用计算机，其任务是转发分组。从路由器某个输入端口收到的分组，按照分组要去的目的地（即目的网络），把该分组从路由器的某个合适的输出端口转发给下一跳路由器。下一跳路由器也按照这种方法处理分组，直到该分组到达终点为止。路由器的转发分组正是网络层的主要工作。
整个的路由器结构可划分为两大部分：路由选择部分和分组转发部分。
路由选择部分也叫做控制部分，其核心构件是路由选择处理机。 路由选择处理机的任务是根据所选定的路由选择协议构造出路由表，同时经常或定期地和相邻路由器交换路由信息而不断地更新和维护路由表。 分组转发部分由三部分组成：交换结构、一组输入端口和一组输出端口（请注意：这里的端口就是硬件接口）。
交换结构(switching fabric)又称为交换组织 ，交换结构是路由器的关键构件，它的作用就是根据转发表(forwarding table)对分组进行处理，将某个输入端口进入的分组从一个合适的输出端口转发出去，交换结构本身就是一种网络，但这种网络完全包含在路由器之中，因此交换结构可看成是“在路由器中的网络”。实现这样的交换有多种方法，以下这三种方法都是将输入端口 I1收到的分组转发到输出端口O2。
图4-45(a)的示意图表示 分组通过存储器进行交换 。目的地址的查找和分组在存储器中的缓存都是在输入端口中进行的。若存储器的带宽（读或写）为每秒M个分组，那么路由器的交换速率（即分组从输入端口传送到输出端口的速率）一定小于M2。这是因为存储器对分组的读和写需要花费的时间是同一个数量级。
图4-45(b)是 通过总线进行交换 的示意图。采用这种方式时，数据报从输入端口通过共享的总线直接传送到合适的输出端口，而不需要路由选择处理机的干预。但是，由于总线是共享的，因此在同一时间只能有一个分组在总线上传送。当分组到达输入端口时若发现总线忙（因为总线正在传送另一个分组），则被阻塞而不能通过交换结构，并在输入端口排队等待。因为每一个要转发的分组都要通过这一条总线，因此路由器的转发带宽就受总线速率的限制。现代的技术已经可以将总线的带宽提高到每秒吉比特的速率，因此许多的路由器产品都采用这种通过总线的交换方式。
图4-45(c)是 通过纵横交换结构(crossbar switch fabric)进行交换 。这种交换机构常称为互连网络(interconnection network),它有2N条总线，可以使N个输入端口和N个输出端口相连接，这取决于相应的交叉结点是使水平总线和垂直总线接通还是断开。当输入端口收到一个分组时，就将它发送到与该输入端口相连的水平总线上。若通向所要转发的输出端口的垂直总线是空闲的，则在这个结点将垂直总线与水平总线接通，然后将该分组转发到这个输出端口。但若该垂直总线已被占用（有另一个分组正在转发到同一个输出端口），则后到达的分组就被阻塞，必须在输入端口排队。
在图4-42中，路由器的输入和输出端口里面都各有三个方框，用方框中的1,2和3分别代表物理层、数据链路层和网络层的处理模块。物理层进行比特的接收。数据链路层则按照链路层协议接收传送分组的核。在把航的首部和尾部去后，分组就被送入网络层的处理模块。若接收到的分组是路由器之间交换路由信总的分组（如RIP或OSPF分组等），则把这种分组送交路由器的路由选择部分中的路由选择处理机。若接收到的是数据分组，则按照分组首部中的目的地址查找转发表，根据得出的结果，分组就经过交换结构到达合适的输出端口。 一个路由器的输入端口和输出端口就做在路由器的线路接口卡上。
输入端口 中的查找和转发功能在路由器的交换功能中是最重要的。为了使交换功能分散化，往往把复制的转发表放在每一个输入端口中（如图4-42中的虚线箭头所示）。路由远择处理机负责对各转发表的副本进行更新。这些副本常称为“影子副本”(shadow ),分散化交换可以避免在路由器中的某一点上出现瓶颈。
“但在具体的实现中还是会遇到不少困难。问题就在于路由器必须以很高的速率转发分组。最理想的情况是 输入端口的处理速率能够跟上线路把分组传送到路由器的速率。这种速率称为线速 （line speed 或 wirc peed)。可以粗略地估算一下。设线路是0C-48链路，即2.5 Gbit/s。若分组长度为256字节，那么线速就应当达到每秒能够处理100万以上的分组。现在常用Mpps(百万分组每秒)为单位来说明一个路由器对收到的分组的处理速率有多高。”
当一个分组正在查找转发表时，后面又紧跟着从这个输入端口收到另一个分组。这个后到的分组就必须在队列中排队等待，因而产生了一定的时延。
输出端口 从交换结构接收分组，然后把它们发送到路由器外面的线路上。在网络层的处理模块中设有一个缓冲区，实际上它就是一个队列。当交换结构传送过来的分组的速率超过输出链路的发送速率时，来不及发送的分组就必须暂时存放在这个队列中。数据链路层处理模块把分组加上链路层的首部和尾部，交给物理层后发送到外部线路。
从以上可以看出，分组在路由器的输入端口和输出端口都可能会在队列中排队等候处理。若分组处理的速率赶不上分组进入队列的速率，则队列的存储空间最终必定减少到零，这就使后面再进入队列的分组由于没有存储空间而只能被丢弃。分组丢失就是发生在路由器中的输入或输出队列产生溢出的时候。当然，设备或线路出故障也可能使分组丢失。
“转发”和“路由选择”的区别 ：在互联网中， “转发” 就是路由器根据转发表把收到的IP数据报从路由器合适的端口转发出去。“转发”仅仅涉及到一个路由器。但 “路由选择” 则涉及到很多路由器，路由表则是许多路由器协同工作的结果。这些路由器按照复杂的路由算法，得出整个网铭的拓扑变化情况，因而能够动态地改变所选择的路由，并由此构造出整个的路由表，路由表一般仅包含从目的网络到下一跳（用P地址表示）的映射，而转发表是从路由表得出的。转发表必须包含完成转发功能所必需的信息。这就是说，在转发表的每一行必须包含从要到达的目的网路到输出端口和某些MAC地址信息（如下跳的以太网地址)的映射。将转发表和路由表用不同的数据结构实现会带来一些好处，这是因为在转发分组时，转发表的结构应当使查找过程最优化，但路由表则需要对网络拓扑变化的计算最优化。路由表总是用软件实现的，但转发表则甚至可用特殊的硬件来实现。请读者注意，在讨论路由选择的原理时， 往往不去区分转发表和路由表的区别，而可以笼统地都使用路由表这一名词。