路由算法及分类 路由算法及分类： 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)基本思想 把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。
路由表 在内核中存在路由表 fib_table_hash 和路由缓存表 rt_hash_table。路由缓存表主要是为了加速路由的查找，每次路由查询都会先查找路由缓存，再查找路由表。这和 cache 是一个道理， 缓存存储最近使用过的路由项，容量小，查找快速；路由表存储所有路由项，容量大，查找慢。 首先，应该先了解路由表的意义，下面是 route 命令查看到的路由表： Destination Netmask Gateway Flags Interface Metric 169.254.0.0255.255.0.0*U eth01 192.168.123.0255.255.255.0*U eth01 default0.0.0.0192.168.123.254UG eth01 一条路由其实就是告知主机要到达一个目的地址，下一跳应该走哪里。比如发往 192.168.22.3 报文通过查路由表，会得到下一跳为 192.168.123.254，再将其发送出去。在路由 表项中，还有一个很重要的属性-scope，它代表了到目的网络的距离。 路由 scope 可取值：RT_SCOPE_UNIVERSE, RT_SCOPE_LINK, RT_SCOPE_HOST 在报文的转发过程中，显然是每次转发都要使到达目的网络的距离要越来越小或不变，否则根本到达不了目的网络。上面提到的 scope 很好的实现这个功能，在查找路由表中，表项的scope 一定是更小或相等的 scope(比如 RT_SCOPE_LINK，则表项 scope 只能为 RT_SCOPE_LINK 或RT_SCOPE_HOST)。 路由缓存 路由缓存用于加速路由的查找，当收到报文或发送报文时，首先会查询路由缓存，在内核中被组织成 hash 表，就是 rt_hash_table。 static struct rt_hash_bucket*rt_hash_table __read_mostly;[net\ipv4\route.c] 通过 ip_route_input()进行查询，首先是缓存操作时，通过[src_ip, dst_ip, iif,rt_genid]计算出 hash 值 hash=rt_hash(daddr,saddr,iif,rt_genid(net)); 此时 rt_hash_table[hash].chain 就是要操作的缓存表项的链表，比如遍历该链表for(rth=rt_hash_table[hash].chain;rth;rth=rth->u.dst.rt_next) 因此，在缓存中查找一个表项，首先计算出 hash 值，取出这组表项，然后遍历链表，找出指定的表项，这里需要完全匹配[src_ip, dst_ip, iif, tos, mark, net]，实际上 struct rtable 中有专门的属性用于缓存的查找键值– struct flowi。 /*Cache lookup keys*/ struct flowi fl; 当找到表项后会更新表项的最后访问时间，并取出 dst dst_use(&rth->u.dst,jiffies); skb_dst_set(skb,&rth->u.dst); 路由缓存的创建 inet_init()->ip_init()->ip_rt_init() rt_hash_table=(struct rt_hash_bucket*) alloc_large_system_hash("IP route cache", sizeof(struct rt_hash_bucket), rhash_entries, (totalram_pages>=128*1024)?
青岛农业大学理学与信息科学学院 计算机网络综合实习报告 题目 专业 学号 姓名 指导教师 日期
目录 一、课程设计任务和目的 (1) 二、设计要求 (1) 三、设计内容 (1) 3.1顺序查找路由表的工作原理 (1) 3.2课程设计程序运行结果与分析 (2) 四、改进和建议 (5) 五、总结 (5) 六、主要参考文献 (5) 附录： (6)
一、课程设计任务和目的 1.了解路由器更新的原理。 2.了解表示路由器的结构。 3.掌握路由器转发分组的算法。 二、设计要求 编写计算机程序，用（目的网络，掩码，下一跳）的结构表示路由表，以一个目的地址作为输入，顺序查找路由表，找出正确的下一跳，并输出。 三、设计内容 3.1顺序查找路由表的工作原理 使用子网划分后，路由表必须包含：目的地址，子网掩码，下一跳地址。路由器分组转发的算法如下： （1）从收到的数据包的首部提取目的IP地址D； （2）对路由器直接相连的网络逐个进行检查：用个网络的掩码和D逐位相“与”，看结果是否和相应的网络地址匹配。若匹配，则把分组直接交付，转发任务结束，否则就是间接交付执行（3）。 （3）若路由表中有目的地址为D特定主机路由，则把数据报传送给路由表中所指明的下一跳路由器否则执行（4）。 （4）对路由表的每一行，用其中的子网掩码和D逐位相“与”，其结果为N。若N 与该行的目的网络相匹配，则把数据报送给该行指明的下一跳路由器；否则执行（5）。 （5）若路由表中有一个默认路由，则把数据报传送给路由表中所指明的默认路由器；否则执行（6）。 （6）报告转发分组出错，没有查找到路由。 简单来说，就是当来一个数据报时，抓
计算机网络实习报告 设计题目编程查路由表 学生专业班级 学生姓名（学号） 指导教师 完成时间 2010年5月26日 实习（设计）地点信息楼139机房 2010 年5月26日
计算机网络与通信实习 一、编写计算机程序用（目的网络掩码下一跳）的结构表示路由表，以一个目的地址作为输入，顺序查找路由表，找出正确的下一跳，并输出。 二、原理概述 当IP子网中的一台主机发送IP分组给同一IP子网的另一台主机时，它将直接把IP分组送到网络上，对方就能收到。而要送给不同IP于网上的主机时，它要选择一个能到达目的子网上的路由器，把IP分组送给该路由器，由路由器负责把IP分组送到目的地。如果没有找到这样的路由器，主机就把IP分组送给一个称为“缺省网关（default gateway）”的路由器上。“缺省网关”是每台主机上的一个配置参数，它是接在同一个网络上的某个路由器端口的IP地址。 路由器转发IP分组时，只根据IP分组目的IP地址的网络号部分，选择合适的端口，把IP分组送出去。同主机一样，路由器也要判定端口所接的是否是目的子网，如果是，就直接把分组通过端口送到网络上，否则，也要选择下一个路由器来传送分组。路由器也有它的缺省网关，用来传送不知道往哪儿送的IP分组。这样，通过路由器把知道如何传送的IP分组正确转发出去，不知道的IP分组送给“缺省网关”路由器，这样一级级地传送，IP分组最终将送到目的地，送不到目的地的IP分组则被网络丢弃了。 三、设计方案 1、从收到的数据报的首部提取目的IP地址D 2、先判断是否为直接交付 3、若路由表中有目的地址为D的特定主机路由，则把数据报传送给路由表中所指明的下一 跳路由表 4、对路由表中的每一行，用其中的子网掩码和D逐位相“与”，其结果为N 5、若路由表中有一个默认路由，则把数据报传送给路由表中所指明的默认路由器；否则执 行6 6、报告转发分组出错 四、程序编写 #include #include
1、查看路由表信息的命令为ZXR10#show ip route，显示实例如下： ZXR10#show ip route IPv4 Routing Table: Dest Mask Gw Interface Owner pri metric 10.26.32.0 255.255.255.0 10.26.245.5 fei_1/1 bgp 200 0 10.26.33.253 255.255.255.255 10.26.245.5 fei_1/1 ospf 110 14 10.26.33.254 255.255.255.255 10.26.245.5 fei_1/1 ospf 110 13 10.26.36.0 255.255.255.248 10.26.36.2 gei_5/2.1 direct 0 0 10.26.36.2 255.255.255.255 10.26.36.2 gei_5/2.1 address 0 0 10.26.36.24 255.255.255.248 10.26.36.26 gei_5/2.4 direct 0 0 10.26.245.4 55.255.255.252 10.26.245.6 fei_1/1 direct 0 0 10.26.245.6 255.255.255.255 10.26.245.6 fei_1/1 address 0 0 路由表中通常包含以下信息： ● Dest：目的逻辑网络或子网地址。 ● Mask：目的逻辑网络或子网的掩码。 ● Gw：与之相邻的路由器的端口地址，即该路由的下一跳IP地址。 ● Interface：学习到该路由条目的接口，也是数据包离开路由器去往目的地将经过的接口。 ● Owner：路由来源，表示该路由信息是怎样学习到的。 ● Pri：路由的管理距离，即优先级，决定了来自不同路由来源的路由信息的优先权。 ● Metric：度量值，表示每条可能路由的代价，度量值最小的路由就是最佳路由。Metric 只有当同一种动态路由协议，发现多条到达同一目的网段路由的时候，才有比较性。不同路由协议的Metric不具有可比性。 例如，实例中加粗显示的一行是路由表中的一条路由信息，其中：
计算机网络实习报告 论文题目距离向量算法更新路由表 学生专业班级通信07级2班 学生姓名（学号） 指导教师 完成时间 2010年05月22日 实习（设计）地点信息楼139（112）机房 2010 年 05 月 22 日
距离向量算法更新路由表 一．实验目的 1．认识并掌握路由器结构组成及路由建立与更新的原理 2．理解、掌握和利用距离向量算法的应用。 3. 能够用距离向量算法建立一个路由表并根据相邻路由器发来的数据进行更新。 5．所实现的路由器模拟Internet上的IP路由器，它能确定网络的最短路由，并在其上传输分组 二．原理概述 距离向量路由算法被距离向量协议作为一个算法，它告诉在网络中每个节点的最远和最近距离。在距离表中的这个信息是根据临近接点信息的改变而时时更新的。表中数据的量和在网络中的所有的接点是等同的。每个数据包括传送数据包到每个在网上的目的地的路径和距离/或时间在那个路径上来传输。 这个表中的列代表直接和它相连的“邻居”路由器相连，行代表在网络中的所有目的地。在距离向量路由算法中，相邻路由器之间周期性（一般为3分钟）地相互交换各自的路由表。当网络拓扑结构发生变化时，路由器之间也将及时地相互通知有关变更信息。它是一种动态路由选择算法。每个路由器都定期与其相邻的所有路由器交换路由表，据此更新它们自己的路由表。 所有路由器只与其相邻路由器交换信息，在发来为RIP报文情况下更新其路由表的具体步骤为： 1.对地址为X的相邻路由器发来的RIP报文，先修改报文中的所有项目，把“下跳”字段中地址均改为X，把所有“距离”字段的值加1.每一个项目都有三项数据，即：到目的网络N，距离是d，下一条路由器是X 2.对修改后的RIP报文中每个项目，进行以下步骤： 若原来路由表中没有目的网络N，则把该项目添加到路由表中。 否则若吓一跳地址是X，把收到的项目替还原路由表中的项目 否则若收到的项目中的距离d小于路由表中的距离，则进行更新。 否则什么也不做。 3．若三分钟还没有收到相邻路由器的更新路由表，则把此相邻路由器记为不可达的路由器，即把距离置为16.（本实验将其定义为6） 4.返回。 三．设计方案 路由表的建立和更新 假设建立七个路由器，其中三个A，B和C。路由器A的两个网络接口E0和S0 分别连接在 10.1.0.0和10.2.0.0网段上；路由器B的两个网络接口S0和S1 分别连接在 10.2.0.0和10.3.0.0网段上；路由器C的两个网络接口S0和E0 分别连接在 10.3.0.0和10.4.0.0网段上； 如上面各路由表的前两行所示，通过路由表的网络接口到与之直接相连的网 络的网络连接，其向量距离设置为0。这即是最初的路由表。
滁州学院 课程设计报告 课程名称：计算机网络 设计题目：路由表查找过程模拟 院部：计算机及信息工程学院 专业：网络工程（无线传感器网络方向） 组别：第二组 起止日期:2012年12月29日~2012年12月30日 指导教师:张老师
计算机及信息工程学院二○一二年制
课程设计任务书
目录 1引言 (1) 2需求分析 (2) 2.1设计题目 (2) 2.2设计目的 (2) 2.3设计主要内容及要求 (2) 2.3.1 设计内容 (2) 2.3.2设计要求 (2) 2.3.3使用环境及语言 (3) 3概要设计 (3) 3.1基本功能描述 (3) 3.1.1路由表的结构 (3) 3.1.2路由表的作用 (4) 3.1.3路由表中路由的来源 (4) 3.2IP路由选择 (4) 3.2.1通过RIP（路由信息协议）来实现路由选择 (4) 3.2.2通过OSPF（开放最短路径优先）来实现路由选择 (6) 3.2.3 Dijkstra算法 (7) 4详细设计 (8) 4.1各模块的伪码算法 (8) 4.1.1RIP (8) 4.1.2 OSPF (12) 5调试及结果说明 (15) 5.1RIP的调试结果 (15) 5.2OSPF的调试结果 (16) 6.课程设计总结及体会 (19) 参考文献 (19) 致谢 (20) 附录 (21)
1引言 随着计算机信息技术的发展，大规模的互联网逐渐流行起来，也为路由器的发展提供了良好的基础和平台。作为不同网络之间互相连接的枢纽，路由器系统构成了基于TCP/IP 的国际互联网络Internet 的主体脉络。然而如何准确的发送并接受信息，则需要通过路由表的准确查找，路由表存储着指向特定网络地址的路径（在有些情况下，还记录有路径的路由度量值）。通过路由表查找过程的设计及模拟可以更好的体现路由的选择，帮助我们准确的理解路由的选择过程。 2需求分析 2.1设计题目 路由器查表过程模拟 2.2设计目的 该程序主要是用来模拟路由器中路由查找的过程。当主机向目的网络发送一个数据包时，对每一个IP包，当发送到一个网络拓扑中的时候，可以分别使用RIP或OSPF协议，来决定数据包通过互联网络的路径。通过模拟算法的实现，我们可以模拟一个简单的路由查找过程，进而找出最优路径，实现路由的查找。 2.3设计主要内容及要求 2.3.1 设计内容 1．rip：距离向量路由协议，距离向量路由协议的特征是它在进行路由更新时，会发送路由表的全部或一部分给邻居路由器（这台邻居路由器也必须运行rip协议），当路由信息通过这种方式扩散到整个自治系统时，每个路由器会根据Dijkstra算法计算出到达每个网段的最优路径，rip选择到达某个网络的最优路径根据跳数。数据包经过一个路由器就是一跳。 2． ospf：路由器的路由选择是基于链路状态，通过Dijkastra算法建立起来最短路径树，用该树跟踪系统中的每个目标的最短路径。最后再通过计算域间路由、自治系统外部路由确定完整的路由表。及此同时，OSPF动态监视网络状态，一旦发生变化则迅速扩散达到对网络拓扑的快速聚合，从而确定出新的网络路由表。因此，需要把自治系统划分为多个域，每个域内部维持本域一张唯一的拓扑结构图，且各域根据自己的拓扑图各自计算路由，域边界路由器把各个域的内部路由总结后在域间扩散。这样，当网络中的某条链路状态发生变化
CCNA考点精析---IP路由表分析 当frame到达路由器的接口后，路由器检查frame中的目标地址字段，如果目标地址为路由器接口的地址或者广播地址的时候，路由器把packet从frame中剥离出来，传递给network layer，然后packet中的目标地址将被检查，接下来还要检查protocol字段，最后再发送给合适的进程，如果packet是可路由的，路由器会查找自己路由表中寻找相应 的路由条目，路由条目至少包含两个要素： 1、目标地址，这个地址是路由器必须能够到达的地址； 2、到达目标地址的指针，这个指针也就是我们平时在路由表中看到的Via.或者是平 时听说的next-hop（下一跳） 路由器根据packet中的目标地址字段，在路由表中执行查询，查询的精确程度按如下顺序 递减： 1、主机地址 2、子网地址 3、汇总网络号 4、主类网络号 5、超网号（super net） 6、默认路由 如果在执行完所有的表查询后，还没有找到匹配的条目，则丢弃packet，并回送一个（Destinnation Unreachable）ICMP不可达的报文给发送方在CISCO路由器上要查看路由表，可以使用特权命令：show ip route R1#sh ip route Codes: C - connected, S - static, I - IGRP, R - RIP, M - mobile, B - BGP D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area N1 - OSPF NSSA external type 1, N2 - OSPF NSSA external type 2 E1 - OSPF external type 1, E2 - OSPF external type 2, E - EGP i - IS-IS, su - IS-IS summary, L1 - IS-IS level-1, L2 - IS-IS level-2 ia - IS-IS inter area, * - candidate default, U - per-user static route o - ODR, P - periodic downloaded static route Gateway of last resort is not set C 192.168.123.0/24 is directly connected, FastEthernet0/0 1.0.0.0/24 is subnetted, 3 subnets C 1.1.1.0 is directly connected, Loopback0 C 1.1.2.0 is directly connected, Loopback1 C 1.1.3.0 is directly connected, Loopback2 C 192.168.14.0/24 is directly connected, Serial1/2
路由表的主要参数 1) 路由表提供了到达不同目标网络的表项，所以转发分组中的目标地址会通过 掩码运算得到分组目标地址所在的目标网络号，使用这个运算出来的网络号在路由表中查找表中目标网络和分组目标网络匹配的表项。所以路由表中包括两项：子网掩码和目标网络(使用CIDR记法只有一项)。 2) 路由表为路由器转发分组提供了路径选择的依据，由于网络层提供了面向非 连接的服务，所以路由表不会存在从分组源地址到分组目的地址的完整路径信息。路由表仅仅提供了经由本路由器接口(Interface 可以是逻辑子接口)和到达目标网络要经过的下一个路由器接口逻辑地址的信息(下一跳，Next Hop)。所以路由表中还包括两项：接口和下一跳地址。 3) 路由表中会出现到达同一个目标网络，但是经过不同的下一跳地址，这种多 路径选择是由计算机网络设计初衷决定的，也是选择分组交换通信的必然结果。条条大路通罗马的思路在路由表中最直接的体现就是到达同一个目标网络可以经过不同路径，但是经过每条路径的开销(Cost)是不一样的，在路由表中把这种开销称为度量值(Metric)，度量值低的路径会被优先选择。度量值可能是一个单一参数的概念(如日常生活中从一个出发地到另外一个目的地经过的收费站数量，收费站数量少的作为优先的出行方式)；度量值也可能是多个参数综合权衡的结果(如日常生活中从一个出发地到另外一个目的地选择的交通工具、距离的远近、交通安全性、费用情况及时间消耗等多个参数，来综合评估出一个度量值，再按照度量值低的选择合适的出行方式)。 所以路由表中还包括一项：度量值。 4) 路由表中的表项可以通过三种方式进行添加：直接连接、静态添加和动态添 加。直接连接代表着路由器端口所配IP地址所在的目标网络；静态添加是由网络管理人员手动添加的路由表项；动态添加是指使用动态路由选择协议(如RIP协议、OSPF协议)自动学习到的路由表项。所以路由表中还包括一项：表项类型。
第22卷第10期 计算机应用与软件 Vol.22, No.10 2005年10月 Computer Applications and Software Oct. 2005 IPv6的快速路由查找算法研究 王 燕 (浙江警官职业学院 浙江 杭州 310018） 摘 要 TCAM 被广泛用于执行快速路由查找，不管前缀的数量和长度，它能在极短时间内解决最佳前缀问题。与基于软件解 决方法相比较，TCAM 能提供持续吞吐量和简单系统体系，这对IPv6路由查找来说是很有吸引力的。然而，它也有一些缺点，例如入口数量有限，价格昂贵和能源消耗。因此，本文提出一种有效、能减少所需TCAM 的算法，该算法通过增加微DRAM 来消除98%的TCAM 入口。实验证明，该算法效果良好，可以大大提高IPv6路由查找性能。 关键词 IPv6 路由查找 TCAM RAPID ROUTING LOOKUP ALGORITHM RESEARCH ON IPv6 Wang Yan (Department of Information Technology and Management, Zhejiang Police Vocation Academy, Hangzhou Zhejiang 310018, China) Abstract Ternary content-addressable memory has been widely used to perform fast routing lookups. It is able to accomplish the best matching prefix problem in (1)O time without considering the number of prefixes and its lengths. As compared to the software-based solutions, the Ternary content-addressable memory can offer sustained throughput and simple system architecture. It is attractive for IPv6 routing lookup. However, it also comes with several shortcomings, such as the limited number of entries, expansive cost and power consumption. Accordingly, an efficient algorithm is proposed in the paper to reduce the required size of Ternary content-addressable memory. The proposed scheme, which has a good effect, can eliminate 98 percentages of Ternary content-addressable memory entries by adding tiny DRAM. Keywords IPv6 Routing Lookup TCAM 1 引 言 由于国际互联网和电子商务的飞速发展、网络接入需求呈 指数级增长、国际互联网正面临着IPv4地址损耗问题，所以网络管理员必须越来越多地依赖NAT(网络地址转换)技术来配置网络。但这会使网络管理变得更加复杂，还会中断网络首尾相连的规则。一些应用程序越过NAT 设备就不能运行，例如IPsec 。而且网络主机不再是计算机，而是一个全新的需要大量IP 地址的信息设备范围。 所有这些事实是发展IPv6主要驱动力量，因为IPv6拥有大量地址空间。例如，目前IPv6的推荐地址分配策略是分配一个48位前缀给国际互联网每个站点，不管它是国内，小办公室，还是大企业站点。48位前缀允许每个站点中65,000子网，每个子网能容纳实质上无数台主机。IPv6也带来了这样一些好处：无国家限制的自动配置，更有效的移动管理和完整的IPsec 。 高速路由设计的主要障碍是相对较慢的IP 查找算法。为了将数据包转发到目的地址，一台路由器必须执行转发决定，输入数据包下一跳地址取决于路由协议收集到的信息。随着1993年CIDR [1]的发展，(路由前缀，前缀长度)确定了IP 路由，这里前缀长度在1位到32位之间变化。对一台有大量路由表入口的骨干路由器来说，可变前缀长度进行的BMP(最佳匹配前缀)搜索可能会花很长时间，国际互联网主机的指数级增长也给路由系统增加更大的压力。数据包转发速度很难跟上日益增长的通信量需求，地址查找操作更是当今路由器转发性能的主要瓶颈。 TCAM 是执行快速IP 查找的流行硬件设备，与基于软件解决方法相比较，TCAM 能提供持续吞吐量和简单系统体系结构，因此对IPv6路由查找来说是很有吸引力的。然而，它也有一些缺点，例如入口数量有限，价格昂贵和能源消耗。更有甚者，用同样的IPv4入口处理IPv6的128位地址需要4倍的TCAM 。本文提出了一种有效算法，该算法通过增加微DRAM 来消除98%TCAM 入口。 2 已有算法 近年来，在创建路由表方面已有大量的研究，包括硬件和软件解决方法。在[2]中，Degermark et al.使用一个类似Trie 树结构，其主要观点是量化前缀长度到几个级别：16位、24位和32位，然后将路由表中每个前缀扩充到下一个更高级别。该方法能将一个有40,000入口的路由表压缩成大小只有150~160K ，用硬件实现一个路由查找需要访问存储器的最小和最大次数分别为2和9。在[3]中，Gupta et al.提出了基于巨型DRAM 的快速路由查找方案，该方案采用最多2次存储器访问实现33MB 转发路由表的路由查找。通过增加一张中间长度路由表，使转
如何读懂路由表-实例大解析 及双网卡设置方案 当前的路由： destination 目的网段 mask 子网掩码 interface 到达该目的地的本路由器的出口ip gateway 下一跳路由器入口的ip，路由器通过interface和gateway定义一调到下一个路由器的链路，通常情况下，interface和gateway是同一网段的metric 跳数，该条路由记录的质量，一般情况下，如果有多条到达相同目的地的路由记录，路由器会采用metric值小的那条路由 第一条缺省路由：意思就是说，当一个数据包的目的网段不在你的路由记录中，那么，你的路由器该把那个数据包发送到哪里！缺省路由的网关是由你的连接上的default gateway决定的该路由记录的意思是：当我接收到一个数据包的目的网段不在我的路由记录中，我会将该数据包通过192.168.123.88这个接口发送到192.168.123.254这个地址，这个地址是下一
个路由器的一个接口，这样这个数据包就可以交付给下一个路由器处理，与我无关。该路由记录的线路质量 1 第二条 缺省路由： 该路由记录的意思是：当我接收到一个数据包的目的网段不在我的路由记录中，我会将该数据包通过192.168.123.68这个接口发送到192.168.123.254这个地址，这个地址是下一个路由器的一个接口，这样这个数据包就可以交付给下一个路由器处理，与我无关。该路由记录的线路质量1 第三条 本地环路：127.0.0.0这个网段内所有地址都指向自己机器，如果收到这样一个数据，应该发向哪里该路由记录的线路质量 1 第四条 直联网段的路由记录：当路由器收到发往直联网段的数据包时该如何处理，这种情况，路由记录的interface和gateway是同一个。 当我接收到一个数据包的目的网段是192.168.123.0时，我会将该数据包通过192.168.123.68这个接口直接发送出去，因为这个端口直接连接着192.168.123.0这个网段，该路由记录的线路质量1 第五条 直联网段的路由记录 当我接收到一个数据包的目的网段是192.168.123.0时，我会将该数据包通过192.168.123.88这个接口直接发送出去，因为这个端口直接连接着192.168.123.0这个网段，该路由记录的线路质量1 第六条 本地主机路由：当路由器收到发送给自己的数据包时将如何处理 当我接收到一个数据包的目的网段是192.168.123.68时，我会将该数据
递归路由 在添加静态路由的时候，next_hop一般是和本地路由器直连的邻居路由器的接口IP地址。当然我们完全可以写成到达目的地的路径上的任一路由器的接口IP地址。 A-B-C-D-E-F六台路由器串联，在A上正常情况下我们这样添加路由： Ip route F f-mask B 当然也可以这样添加：ip route F f-mask E ，要到达F的下一跳是E。但是在本地路由表中还得有到达E的路由条目：ip route E e-mask D，到达E 的下一跳是D；在本地路由表中还得有到达D的路由条目：ip route D d-mask C，到达D的下一跳是C；在本地路由表中还得有到达C的路由条目：ip rotue C c-mask B，到达C的下一跳是B；在本地路由表中有到达B的直连路由。 这就是一个标准的递归路由。当中间网络有多条路径到达目的时，可以采用递归路由的方式分段管理。 递归路由在实际的网络环境中用的相对较少！ ping命令的关键点 检查网络的通断情况，我们一般使用ping命令来检查。 1：可以ping通目的地址，但ping不通中间某个路由器的接口。 这种现象是典型的可以通过，但无法到达的问题。原因在哪里呢？请大家思考！ 2：连接在路由器上的PC可以telnet到目的地址，但在路由器上却无法ping 通目的地址。 Ping是一个双向的过程，数据包发送到目的地址，目的地址再发送响应包到源地址。这是ping的最基本，最简单的要求。
在路由器上直接ping目的地址，并没有给出源IP地址。一般情况下源地址就是数据包离开路由器的接口的IP地址。 可以ping通目的地址，说明数据包离开路由器的接口的网络对于目的地址是可达的，在路由器上也有到达目的地址的路由。Ping不通中间某个路由器的接口，只能说明没有路由！！凡是ping不通的情况，首先应该查看是否存在路由！！ 要明确路由是否存在，请一定使用show ip route命令来查看。 要明确源到目的是否畅通，请一定在使用ping的时候携带源地址。 Ping命令携带源地址有两种方式（不同版本有所差异）： 1：ping destination_ip source_ip 2：输入ping命令然后回车，根据提示，输入目的ip地址和源IP地址。 第二种我们一般称为扩展ping。
路由表 在内核中存在路由表fib_table_hash和路由缓存表rt_hash_table。路由缓存表主要是为了加速路由的查找，每次路由查询都会先查找路由缓存，再查找路由表。这和cache是一个道理，缓存存储最近使用过的路由项，容量小，查找快速；路由表存储所有路由项，容量大，查找慢。首先，应该先了解路由表的意义，下面是route命令查看到的路由表： Destination Netmask Gateway Flags Interface Metric 169.254.0.0255.255.0.0*U eth01 192.168.123.0255.255.255.0*U eth01 default0.0.0.0192.168.123.254UG eth01一条路由其实就是告知主机要到达一个目的地址，下一跳应该走哪里。比如发往 192.168.22.3报文通过查路由表，会得到下一跳为192.168.123.254，再将其发送出去。在路由表项中，还有一个很重要的属性-scope，它代表了到目的网络的距离。 路由scope可取值：RT_SCOPE_UNIVERSE, RT_SCOPE_LINK, RT_SCOPE_HOST 在报文的转发过程中，显然是每次转发都要使到达目的网络的距离要越来越小或不变，否则根本到达不了目的网络。上面提到的scope很好的实现这个功能，在查找路由表中，表项的scope一定是更小或相等的scope(比如RT_SCOPE_LINK，则表项scope只能为RT_SCOPE_LINK或RT_SCOPE_HOST)。 路由缓存 路由缓存用于加速路由的查找，当收到报文或发送报文时，首先会查询路由缓存，在内核中被组织成hash表，就是rt_hash_table。 static struct rt_hash_bucket *rt_hash_table __read_mostly; [net\ipv4\route.c] 通过ip_route_input()进行查询，首先是缓存操作时，通过[src_ip, dst_ip, iif,rt_genid]计算出hash 值 hash = rt_hash(daddr, saddr, iif, rt_genid(net)); 此时rt_hash_table[hash].chain就是要操作的缓存表项的链表，比如遍历该链表for (rth = rt_hash_table[hash].chain; rth; rth = rth->u.dst.rt_next) 因此，在缓存中查找一个表项，首先计算出hash值，取出这组表项，然后遍历链表，找出指定的表项，这里需要完全匹配[src_ip, dst_ip, iif, tos, mark, net]，实际上struct rtable中有专门的属性用于缓存的查找键值– struct flowi。 /* Cache lookup keys */ struct flowi fl; 当找到表项后会更新表项的最后访问时间，并取出dst dst_use(&rth->u.dst, jiffies); skb_dst_set(skb, &rth->u.dst); 路由缓存的创建 inet_init() -> ip_init() -> ip_rt_init() rt_hash_table = (struct rt_hash_bucket *) alloc_large_system_hash("IP route cache", sizeof(struct rt_hash_bucket), rhash_entries, (totalram_pages >= 128 * 1024) ? 15 : 17,
学习目标 （一）了解路由器的相关概念和基本知识 一、子网寻径及路由 标准的路由表表目是一个二维组（目的网络地址，下一站地址），其中不携带子网信息，不能满足子网寻径。引入子网编址以后，路由表的每一表目中加入子网掩码，于是路由表表目变为三维组：子网掩码、目的网络地址、下一站地址。 表1 路由表结构及使用 二、路由算法、路由协议、寻径 路由器依据路由表来为报文寻径，路由表由路由协议建立和维护。路由协议的设计则是依据某种路由算法。 1.什么是路由
路由器提供了将异构网互联的机制，实现将一个数据包从一个网络发送到另一个网络。路由就是指导IP数据包发送的路径信息。 2.通过路由表进行选路 图2 查看路由表 路由器转发数据包的关键是路由表。每个路由器中都保存着一张
路由表，表中每条路由项都指明数据包到某子网或某主机应通过路由器的哪个物理端口发送，然后就可到达该路径的下一个路由器，或者不再经过别的路由器而传送到直接相连的网络中的目的主机。 路由表中包含了下列关键项： 目的地址（Destination）：用来标识IP包的目的地址或目的网络。 网络掩码（Mask）、输出接口（Interface）、下一跳IP地址（Nexthop）。 3.路由表中路由的来源 在路由表中有一个Protocol字段，指明了路由的来源，即路由是如何生成的。路由的来源主要有3 种： （1）链路层协议发现的路由（Direct） 它的特点是开销小，配置简单，无需人工维护，只能发现本接口所属网段拓扑的路由。 （2）手工配置的静态路由（Static） 静态路由是一种特殊的路由，它由管理员手工配置而成。通过静态路由的配置可建立一个互通的网络，但这种配置问题在于：当一个网络故障发生后，静态路由不会自动修正，必须有管理员的介入。静态路由无开销，配置简单，适合简单拓扑结构的网络。 3）动态路由协议发现的路由（RIP、OSPF等） 当网络拓扑结构十分复杂时，手工配置静态路由工作量大而且容
路由器中的硬件IP路由表查找技术 Internet的迅速发展给我们的生活带来了巨大的变化。随之而来的是网络流量的迅速增长。网络流量的增长对于Internet上的路由器来说是一个很大的挑战，特别是核心路由器。它需要高速有效的包调度.转发和路由策略。本文针对路由器的路由查找，提出了一种高效的.便于用硬件实现的技术。 1. 路由器的体系结构 图1给出了一般路由器的逻辑体系结构。它主要由下面几部分组成：路由引擎、转发引擎、路由表、网络适配器和相关的逻辑电路等。转发引擎负责把从一个网络适配器来的数据包转发到另一个网络适配器出去。IP协议，包括对路由表的查找，构成了转发引擎中最主要的部分。由于每个通过路由器并需要其转发的数据包都要对路由表进行查找，所以路由表的查找效率如何往往决定了整个路由器的性能。路由引擎则包括了高层协议，特别是路由协议，它负责对路由表的更新。由于路由引擎不涉及通过路由器的数据通路，故它可用通用的CPU代替。 2．硬件路由表的数据结构设计 一般路由器中路由表的每一项至少有这样的信息：目标地址、网络隐码、下一跳地址。如果对每一个IP地址都要一个表项，那么需要占用很大的2323*4字节的存储器，而且其中必定有很多的表项没有被使用，这就会造成极大的资源浪费。 为了用硬件实现路由表的查找，查找算法需要满足如下的条件： 1）实时的实现路由表的查找； 2）有效的实现路由表的插入和删除； 3）提供有效的最长前缀匹配； 4）具有良好的可扩展性； 5）支持广播和组播； 6）有效的对Memory进行利用； 7）硬件上容易实现，并具有良好的性能。 我们考虑，如果在对路由表的查找中，把子网隐码和IP地址结合起来，对IP地址进行相应的分段，并把它们相连。这样在路由表的表项中，只有IP地址的一部分及其相应的隐码部分，可以实现良好的可扩展性，只要对Memory进行有效的管理，可以灵活的动态的实现对路由的插入和删除。鉴于此，我们设计该表的结构（如下面的表一所示）：
课程设计报告 课程名称：局域网技术 设计题目：路由表查找过程模拟 系别：计算机与信息工程学院 专业：网络工程 组别：第一组 起止日期: 2012年6月11日~ 2012年6月24日指导教师: 计算机科学与技术系二○一二年制
课程设计任务书 目录 1 引言 (1)
2需求分析 (1) 2.1设计目的 (1) 2.2设计主要内容及要求 (1) 2.2.1 设计内容 (1) 2.2.2设计要求 (2) 2.2.3 使用环境及语言 (2) 3概要设计 (2) 3.1基本功能描述 (2) 3.1.1路由表的结构 (2) 3.1.2路由表的作用 (2) 3.1.3路由表中路由的来源 (3) 3.2IP路由选择 (3) 3.2.1通过RIP(路由信息协议)来实现路由选择 (3) 3.2.2通过OSPF(开放最短路径优先)来实现路由选择 (5) 3.2.3 Dijkstra算法 (5) ⒋详细设计 (6) 4.1各模块的伪码算法 (6) 4.1.1 RIP (6) 4.1.2 ospf (10) 5调试与结果说明 (13) 5.1.RIP的调试结果 (13) 5.2.OSPF调试结果 (14) ⒍课程设计总结与体会 (17) 致谢 (17) 参考文献 (18) 附录 (18)
课程设计的主要内容 1 引言 随着计算机信息技术的发展，大规模的互联网逐渐流行起来，也为路由器的发展提供了良好的基础和平台。作为不同网络之间互相连接的枢纽，路由器系统构成了基于TCP/IP 的国际互联网络Internet 的主体脉络。然而如何准确的发送并接受信息，则需要通过路由表的准确查找，路由表存储着指向特定网络地址的路径（在有些情况下，还记录有路径的路由度量值）。通过路由表查找过程的设计与模拟可以更好的体现路由的选择，帮助我们准确的理解路由的选择过程。 2需求分析 2.1设计目的 该程序主要是用来模拟路由器中路由查找的过程。当主机向目的网络发送一个数据包时，对每一个IP包，当发送到一个网络拓扑中的时候，可以分别使用RIP或OSPF协议，来决定数据包通过互联网络的路径。通过模拟算法的实现，我们可以模拟一个简单的路由查找过程，进而找出最优路径，实现路由的查找 2.2设计主要内容及要求 2.2.1 设计内容 1．rip：距离向量路由协议，距离向量路由协议的特征是它在进行路由更新时，会发送路由表的全部或一部分给邻居路由器（这台邻居路由器也必须运行rip协议），当路由信息通过这种方式扩散到整个自治系统时，每个路由器会根据Dijkstra算法计算出到达每个网段的最优路径，rip选择到达某个网络的最优路径根据跳数。数据包经过一个路由器就是一跳。 2．ospf：路由器的路由选择是基于链路状态，通过Dijkastra算法建立起来最短路径树，用该树跟踪系统中的每个目标的最短路径。最后再通过计算域间路由、自治系统外部路由确定完整的路由表。与此同时，OSPF动态监视网络状态，一旦发生变化则迅速扩散达到对网络拓扑的快速聚合，从而确定出新的网络路由表。因此，需要把自治系统划分为多个域，每个域内部维持本域一张唯一的拓扑结构图，且各域根据自己的拓扑图各自计算路由，域边界路由器把各个域的内部路由总结后在域间扩散。这样，当网络中的某条链路状态发生变化时，此链路所在的域中的每个路由器重新计算本域路由表，而其它域中路由器只需修改其路由表中的相应条目而无须重新计算整个路由表，节省了计算路由表的时间。