（物理电子学专业论文）路由器中路由转发机制的fpga实现.pdf

论文摘要 论文摘要 路由器是网络互连中的重要组成部分， 而路由技术则是路由器的基础和 核心。路由器的电路结构是否合理、软件设计是否高效直接影响到路由器的 工作，进而影响到整个网络的效率和可靠性。正因为这样路由器中的路山转 发机制也成为世界各大公司竞相研究的热点, c i s c o , l u c e n t 和华为等公司都 投入了大j _ 的人力物力去努力完善和发展自己的路由技术。 基于对路由器内部结构和1作原理的理解，以及对 v h d l硬件描述语言 的熟练掌握，我把 “路由器中路由转发机制的 f p g a实现” 选定为我的毕业 论文题目 ， 在该课题中我将使用v h d l语言和自 顶向 下的硬件设计方法来实现 路由转发模块的设计、模拟和仿真。 关 键词:路由器路由转发机制i p 数据报内部数据包 a b s t r a c t n o w a d a y s , r o u t e r s p l a y a n i m p o r t a n t r o l e i n n e t w o r k i n g , w h i l e , t h e r o u t i n g t e c h n o l e d g e f o r m s t h e c o r e o f r o u t e r s . t h e h a r d w a r e d e s i g n i n g a n d t h e s o f t w a r e p r o g r a m m i n g o f r o u t e r e x e r t d i r e c t i n f l u e n c e o n t h e p r o p e r w o r k i n g o f r o u t e r s , a n d f u r t h e r , o n t h e e f f i c i e n c y a n d r e l i a b i l i t y o f t h e w h o l e n e t w o r k t h e r e f o r e , t h e f o r w a r d i n g t e c h n o l e d g e o f r o u t e r s b e c o m e s t h e f o c u s i n t h e r e s e a r c h e s c a r r i e d o n b y m a n y l e a d i n g c o r p r a t i o n s a r o u n d t h e w o r l d . a s w e c a n s e e , c i s c o , l u c e n t a n d h u a w e i a l l p u t h u g e a m o u n t o f m a n p o w e r a n d m a t i e r i a l r e s o u r c e s i n p e r f e c t i n g a n d d e v e l o p i n g t h e i r o w n r o u t i n g t e c h n o l e d g e b a s e d o n t h e d e e p u n d e r s t a n d i n g o f t h e i n t e r n a l s t r u c t u r e a n d w o r k i n g p r i n c i p l e s o f r o u t e r s a n d g o o d m a s t e r y o f v h d l l a n g u a g e , t h e a u t h o r t i t l e s t h e t h e s i s a s t h e r e a l i z a t i o n o f f o r w a r d i n g f u n c t i o n i n r o u t e r b y f p g a . i n t h i s p r o j e c t , t h e a u t h o r a t t e m p t s t o d e s i g n , s i m u l a t e a n d e m u l a t e t h e f o r w a r d i n g m o u l d o f r o u t e r s b y u s i n g v h d l l a n g u a g e a n d t o p - d o w n d e s i g n i n g m e t h o d . k e y w o r d s : r o u t e r , t h e f o r w a r d i n g f u n c t i o n , i p p a c k e t , i n t e r n a l p a c k e t 路由器中路由转发机制的f p g a实现 第一章绪 论 第一章 绪 论 1 . 1 t c p / i p 概述 1 . 1 . 1网络的分层 很多不同的厂家生产各种类型的计算机，它们运行完全不同的操作系 统，但 t c p / 工 p协议族允许它们互相进行通信。网络协议通常按不同层次进 行划分，每一 层分别负责不同的通信功能。t c p / i p是一组不同层次上的多个 协议的组合。t c p / i p 通常被认为是一个四层协议系统( 如图卜1 ) . 应用层 运输层 网络层 链路层 t e l n e t , p t p 和 e - m a i l 等 t c p 和 u d p i l l , 1 c m p 和 i g m p 设备驱动程序及接1- 1 _ 图1 - 1 t c p / i p 协议族的四个层次 1 ) 链路层，有时也称作数据链路层或网络接口 层，通常包括操作系统中 的设备驱动程序和计算机中的网络接口卡。它们一起处理与电缆( 或其他任 何传输媒介) 的物理接口细节。 2 ) 网络层，有时也称作互联网层，处理分组在网络中的活动，例如分组 的选路。在t c p / i p 协议族中，网络层协议包括 i p 协议( 网际协议) 、i g m p 协 议( i n t e r n e t 互联网控制报文协议) ，以 及工 g m p ( i n t e r n e t 组管理协议) 。 3 ) 运输层主 要为两台主机上的应用程序提供端到端的通信。 在 t c p / i p 协议族中， 有两个互不相同的传输协议:t c p ( 传输控制协议) 和 u d p ( 用户数 据报协议) 。t c p 为两台主机提供高可靠性的数据通信。它所做的工作包括把 应用程序交给它的数据分成合适的小块交给下面的网络层，确认接收到的分 组，设置发送最后确认分组的超时时钟等。由于运输层提供了高可靠性的端 到端的通信，因此应用层可以忽略所有这些细节。而另一方面，u d p则为应 用层提供一种非常简单的服务，它只是把称作数据报的分组从一台主机发送 到另台_ 机，但并不保证该数据报能到达另一 端。任何必需的可靠性必须 由应用层来提供。这两种运输层协议分别在不同的应用程序中有不同的用 途。 4 ) 应用层负责处理特定的应用程序细节。 当 应用科学试验有 t c p 传送数据时，数据被送入协议栈中， 然后逐个通 过每一层直到被当作一串比 特流送入网络。 其中每一层收到的数据都要增加 一 些首部 信息( 有时 还要 增加 尾部 信息) ，该 过程如图 所示。 t c p 传给1 p 的数 据单i g 称作t c l, 报文段或简称为ic p 段 t c p s e g m e n t ) . i p 传给网络接1: 1 层 的数据中 儿 称作 i i i 数 据报 ( 1 1, s e g m e n t ) . 通过以 太网 传输的比 特流称作帧 路由 撰中 路由 转发机制的f p g a实现 第一章 绪 论 ( f了 a m e 川户数据 a p p i , m a ls i川户数州 t c p首部应用数据 t c p 段 i p首部 t c p首部应用数据 p 数据报 以 太网 首部 i i p 首部】 t c p 首部 应用数据以太网尾部 以太网帧 图1 - 2数据进入协议栈时的封装过程 1 . 1 . 2互联网的地址 互联网上的每个主机必须有- 址) 。i p 地址长3 2 b i t . i n t e r n e t 2 , 3 等。i p 地址具有一定的结构， 个唯一的 工 n t e r n e t地址 ( 也称作 印 地 地址并不采用平面形式的地址空间，如1 , 五类不同的互联网地址格式如图所示。 a 类 0 1 7 位 网 络 号 。 类 1 1 0 1 14 位 网 络 号 2 4 位土机号 1 6 位主机号 2 1 位网络号8 位土机号 2 8 位多播组号 类类 七d e 类 2 7 位 留待后用) 图1 - 3 五 类互联网地址 这联 这些 3 2位的地址通常写成四个十进制数，其中每个整数一个字节。 利 表示方法称作 “ 点分十进制表示法 ( d o t t e d d e c i m a l n o t a t i o n ) . 1 路由器中 路由 转发机制的f p g a实现 第一章 绪 论 网士 的侮个接曰 必须有 一 个唯 其中每个接口都一个 l p 地址。 一 的 i p 地址，多接口主机具有多个 1 p 地址， l p地址中还有一个子网掩码的概念，这个掩码是一个 3 2 b i t的值，其 中值为 1 的比特留给网络号和子网号，为0 的留给主机号。 给定 工 p地址和子网掩码后，主机就可以确定 l p 本了网 卜 的主机: ( 2 ) 本网络中其他子网中的主机; 数据报的目的是:( 1 ) ( 3 ) 其他网络上的主机。 如果知道木机的 i p 地址，那么就能知道它是否为八 类、6 类或c 类地址 从 i i ， 地址的高位， 1 以得知) ，也就知道网络 号 和子网号之ih j 的分界线。i n 根据 f - 网掩码就可以知道子网号与主机号之间的分界线。 一般的 子网 掩码中i 的个数一般为8 的 倍数， 如1 6 个、 2 4 个等， 而 本 文中将要介绍的子网掩码是任意位的，为了区别和传统子网掩码概念的不 同，本文中将使用 “ t p 地址前缀”op a d d r e s s p r e f i x ) o 1 . 1 . 3 i p 数据报的格式 路由器是工作在网络层，即i p 层上的，它处理的对象是 l p 数据报，下 面就简单地介绍一下 l p 数据报的格式: 1 5 1 6 4 vi.w t* 4 位6 部长 度 8 位服务类i(l) ( t os) 1 6 位总长 度 字竹 数) 1 6 位标识 3 1ti.u;- 13位片偏移 8 位生存时间 ( t t l) 8 位协议1 6 位首部检验和 3 2 d i .源 i p 地址 ( s a) 3 2 位卜 的l p地址 ( da) 选项 如果有) 数据 图1 - 4 i p 数据报格式 及首部中的各字段 路由器中 路由 转发机制的f p g a实现 第一章绪 论 先来看一 卜 图 1 - 4中 i p 数据报的首部，最高位在左边，记为o b i t ，最 低位在右边，记为3 1 b i t o 4 个字节的3 2 6 i t 值以下面的次序传输: 首 先是0 - 7 b i t ， 其次是8 - 1 5 b i t , 然后 1 6 - 2 3 b i t , 最后是2 4 - 3 1 b i t 。 这种传输次 序称作b i g c n d i a n 字 犷 j 了 。 山j 几 t c p / i p首 部i i i 所有的二 进制整数在网络中 传输时都要求以 这种次序因 此它又称作网络字节序。以其他形式存储二进制整数的机器，如 l i t t l e l: n d i a 。 格式，则必须在传输数据之前 把首部转换成网络字节序。 目前的协议版本号是4 ，因此 i p 有时也称作i p v 4 o 首部长度指的是首部占3 2 b i t字的数目，包括任何选项。由于它是一个 4 b i t 字段，因此首部最长为6 q 字节。普通i p 数据报 ( 没有任何选项)该字 段的值是 5 0 服务类型( t o s ) 字段包括一个3 6 i t 的优先权字段( 现在己被忽略) ， 4 6 i t 的t o s 子字段和 i b i t 未用位但必须置o o 4 6 i t 的t o s 分别代表:最小延时、 最大吞吐量、最高可靠性和最小费用。4 b i t中只能置其中的 l b i t 。如果所 有4 h i i 均为。 ， 那么就意味着是 般服务。 总长度字段是指整个 i p数据报的长度，以字节为单位。利用首部长度 字段和总长度就可以知道 i p数据报中数据内容的起始位置和长度。由于该 字段长1 6 6 i t ，所以i p 数据报最长可达6 5 5 3 5 字节。当 数据报被分片时，该 字段的值也随着变化。 标识字段唯一地标识主机发送的每一份数据报。 通常每发送一份报文它 的值就会加t o t t l ( t i m e - t o - l i v e ) 生存时间 字段设置了 数据报可以 经过的最多 路由 器 数。它指定了数据报的生存时间。 t t l 的初始值由源主机设置 ( 通常为3 2 或 6 4 ) ，一旦经过一个处理它的路由器，它的值就减 t o当该字段的值为0 时， 数据报就被丢弃，并发送 i c m p 报文通知源主机。 协议字段可以用来识别是哪个协议向i p 传送数据。 首部检验和字段是根据 i p首部计算的检验和码。它不对首部后面的数 据进行计算。 最后一个字段是任选项，是数据报中的一个可变长的可选信息。目 前， 这些任选项定义如下:安全处理限制、记录路径、时间戳、宽松的源站选路、 严格的源站选路。这些选项很少使用，并非所有的主机和路由器都支持这些 选项。选项字段一直都是以3 2 b i t 作为界限，在必要的时候插入值为0 的填 充字节。这样就保证了 i p首部始终是 3 2 b i t的倍数 ( 这是首部长度字节段 所要求的) 。 1 . 2 i p 路由 选择原理 从概念上说，i p路由选排是简单的，特别对于主机来说。如果目的主 机与源主机直接相连 ( 如点 对点链路) 或都在一个共享网 络上 ( 以 太网或令 牌环网) ， 那么 i p 数据报就直接送到目 的主 机上。 否则，主 机把数据报发往 一 默认的路由 器上，由路由 器来转发该数据报。大多数的主机都是采用这种 简单机制。 路由器中路由转发机制的f p g a实现 第一章 绪 论 尸 层 既 可 以 配 置 主 机 的 功 能 ， 也 可 以 配 置 成 路 由 器 的 功 能 。 当 今 的 大 多数多用户系统，包括几乎所有的 u n i x系统，al s 口 j 以r t 直hxy 广 f* 田3 s o 我们可以为它指定卞机和路由器都可以使用的简单路由算法。本质土的区别 在于主机从不把数据报转发到另一个接口，而路由器则要转发数据报。内含 路由器功能的主机应该从不转发数据报，除非它被设置成那样。 在 本地 般的体制中，i p可以从 t c p , u d p , 成的数p : 报)井进行发送，或名 从 i c m p , i g m p接收数据报 ( 即在 个网络接1 1 1 ) 收数据报 ( 1 1141 发 的数据报)j j .进行发送。i ii 层在内存中有 一 个路由表。当收到 一 份数那报井 进行发送时，它都要对该表搜索一 次。当数据报来自 某个网络接n时，i p 首 先检查日的 i i i 地址是否为本机的 i i i 地址之或者 i p厂 一 播地址。如果确实 是这样，数1 fi 1, 报就被送到由 i ii首部协议字段所指定的协议模块进行处理。 如果数据报的目 的地址不是这些，那么:( i )如果 i ii层被设置为路由器的 功能， 就对数据报进行转发( 也就是说， 像下面对待发出的数据报一样处理) : 否则 ( 2 )数据报被丢弃。 路由表中的每一项都包含下面这些信息: 目的i p 地址。它既可以是一个完整的主机地址，也可以是一个网络 地址，由该表目 中的标志字段来指定 ( 如下所述) 。主机地址有一个 非0 的主机号，以指定某一个特定的主机，而网络地址中的主机号 为0 ，以指定网络中的所有主 机 ( 如以太网、令牌环网) 。 下一 站 ( 或下一跳) 路由 器 ( n e x t - h o p - r o u t e r )的i ii 地址， 或者 有直接连接的网络i p 地址。下一站路由器是指一个在直接相连网络 上的路由器，通过它可以转发数据报。下一站路由器不是最终目的 地，但是它可以把传送给它的数据报转发到最终目的。 标志。其中一个标志指明目 的i p 地址是网 络地址还是主机地址，另 一 个标志指明下一站路由器是否为真正的下一站路由器，还是一个 直接相连的接口。 为数据报的传输指定一个网络接口。 i p路由 选择是逐跳地 ( h o p - b y - h o p )进行的。从这个路由 表信息可以 看出，i p 并不知道到达任何目 的的完整路径 ( 当 然，除了 那些与主机直接相 连的目的) 。所有的 工 p路由 选择只为数据报传输提供下一站路由器的 i p地 址。它假定下一站路由器比发送数据报的主机更接近目的，而且下一站路由 器与该主机是直接相连的。 印路山选择主要完成以下这些功能: ( i ) 搜索路由 表，寻找能与目 的 i p地址完全匹配的 表目( 网络号和主机 号都要匹配) 。如果找到，则把报文发送给该表目 指定的下一站路由器或直 接连接的网络接口 ( 取决于标志字段的值) 。 ( 2 ) 搜索路由表，寻找能与目 的网络号相匹配的表目。如果找到，则把报 文发送给该表目 指定的下一站路由器或直接连接的网络接口 ( 取决于标志字 段的值) 。日的网络 卜 的所有 1 - 机都可以通过这个表日来处置。例如，一个 以太网 卜 的所有七 f ) l 都是通过这种表日 进行;1 径的。 ( 3 ) 搜索路由表，寻找标为 “ 默认 ( d e f a u l t ) ”的表目。如果找到，则把 报文发送给该表目 指定的下一站路由器。 如果上面这些步骤都没有成功，那么该 数据报就不以被传送。如果不能 传送的数据报来自 本机，那么一般会向生成数据报的应用程序返回一个 “ 主 m r h 器中路i l i 转发机制的f p g a实现 第 一 章绪 论 # 1 l 不可达”或 “ 网络不可达”的错误。 完整主机地址匹配在网络号 匹配之前 执行。只有当它们都失败后刁选择 默认路由。默认路由，以及下一站路由器发送的 i c m p间接报文 ( 如果我们 为数据报选择了 错误的默认路由) 。是i p 路由 选择机制中功能强大的特性。 为 一 个网络指定一 个路由器，而不必为每个主机指定一个路由器，这是 i ll 路l l i 选择机制的另 个基本特性。这样做可以极大地缩小路由表的规模， 比9 1 1 i n t c r n e t 几 的路ii i 器只有儿千 个表【 i ，i( ii 不会是超过 1 0 0 万个表日。 1 .3 可编程逻辑器件和现代e d a 技术简介 2 0 世纪9 0 年代上半叶，由 于个人电 脑、 无绳电 话和高 速数据传输设备 的发展需求，电子工业经历了巨大的飞跃。为了赢得商业上的竞争，生产商 的产品迫切需要追求高功能、优品质、低成本、微功耗和微小封装尺寸。为 此，生产商必须采用少量的 i c器件和面积尽可能小的 p c b板来研制高集成 化的复杂系统。亚微米半导体工艺、p c b表面安装技术的发展支持了产品集 成化程度的进步。但是，在给定 e d a工具的条件下，随着产品上市时间周期 的加速， 设计复杂程度的提高， 影响生产商开发的瓶颈问题就是其设 计能力， 这个问题实际上孕育着对现代设计方法和现代测试方法的普遍需求。因此， 高密度逻辑器件和v h d l( 超高速集成电路硬件描述语言)成为解决这些问题 的关键所在。 1 . 3 . 1 可编程逻辑器件 可编程逻辑器件经历了从 的发展过程，在结构、工艺、 改进和提高。 p l a , p a l , g a l , e p l d到 c p l d , f p g a 、功能、速度和灵活性方面都有很大的 在生产工艺方面，可编程逻辑集成电路的线宽从 1 9 9 0 年的 i p m发展到 1 9 9 7 年的0 . 3 5 u m ，甚至已经达到深亚微米级，在一块硅片上最多可以集成 2 0 万个逻辑门。 与此同时， 器件速度指标也在飞速提高， 到1 9 9 6 年为止， f p g a 的门 延时已 小于 3 n s , c p l d器件的系统z作速度已达 1 8 0 m h z ( l a t t i c e的 i s p l i s 2 0 3 2 ) ， 如图 所示。 延 迟( n s ) 标准门i 巨 路延时 睽h il w f “. ” . 2 1 . 5 1 0 . 8 0 . 6 0 . 3 5 图1 - 5 可编程逻辑电路的线宽与延迟 设计线宽( pm ) 路山器中路由转发机制的f p g a实现 第一章绪 论 c m o s 工艺在速度上超过双极型工艺，成为可编程逻辑集成主要的工艺 手段， 在便携计算机和移动电话等产品上使用的低电压 ( 3 . 3 v ) 器件的市场 份 额 擎 黔 赢fho 和 测 试 技 术 方 面 ， 除 传 统 的 熔 、 ( fuse ) 、 紫 夕 卜线 工 艺 ( u v e p r o m )外，出现性能更佳的反熔丝 ( a n t i f u s e )和电擦写 ( e e p r o m ) i 艺， i 3 ? p r o m 有充个取代u v e p r o m 的趋势. f p c a 器个 卜 的现场可编程技术和c p l d 器件的在系统i if 编程技术使i 1) 编程器件在使用 i 几 更为力 一 便，边界扫描测试技 术大大加强了芯片、电路板和系统的可测试性。 可 编程逻辑器件技术未来发展的动力仍来自 于实际应用的要求和芯片制 造商之间的竞争。可以断定，可编程逻辑器件在结构、密度、功能速度和灵 活性方面将得到进一步发展，各制造商受商业利益驱使会继续推出一些新的 技术来提高器件的性能以提高竞争力。在最近几年内，可编程逻辑器件技术 的发展热点可能体现在以下两个方面: 1 )从互连延时入手解决系统速度问题。过去，由于门延时较大，所以 系统的速度主要取决于门延时然而随着技术的发展，门延时已从过去的几百 n s 降低到不足2 n s ， 由于硅片几何尺寸的限制， 继续减少门延时越来越困难。 与 此同时，和门延时相比互连延时却越来越大，成了系统延迟时间的关键因 素。 2 )可再配置技术。在系统可 编程技术和现场可编程技术都能够对器件 功能重新配置，可以 称为初级的可再配置技术。随着技术的发展，缩短配置 时间，会出现能够在极短时间内重新配置的器件，这会使硬件的概念发生革 命性改变，即系统硬件的功能不再固定，而是像软件一样可以灵活地加载配 置。可再配置技术是继续提高计算机运算速度最有潜力的技术之一， 对于复 杂的数学运算，例如d s p等，硬件的处理速度大大高于软件，用可再配置的 硬件代替软件能够显著地提高计算机的速度。 1 . 3 . 2现代 e d a 技术 在e d a 技术出现以前，人们ft .采用传统的硬件电路设计方法来设s 系 统的硬件，即自 下至上的方法 ( b o t t o m u p ) . 这种方法设计电路的主要步骤是: 1 )根据系统对硬件的要求，详细编制技术规格书，并画出系统控制流 图; 2 )根据技术规格书和系统控制流图，对系统的功能进行细化，合理地 划分功能模块，并画出系统的功能框图; 3 )进行各功能模块的细化和电路设计; 4 )各功能模块电路设计、调试; 5 )各功能模块的连调，即系统调试。 这种b o t t o m u p的 设计方法有一个致命的 缺点: 在系统硬件设计的 后期 进行仿真和调试， 仿真和调试通常只能在后期完成系统硬件设计以后才能进 行。 因为进行仿真和调试的仪器一般为系统仿真器、 轮回分析仪和示波器等， 因此只有在硬件系统己经构成以后刁 能使用。系统设计时存在的问题只有在 后期才 一 能较容易发现，这样，传统的硬件设计方法对系统设计人员有较高的 要求，一旦考虑不周，系统设计存在较大缺陷，那么就有可能要重新设计系 路由器中 路由 转发机制的f p g a实 现 第一章绪 论 统 ， 货 亨 纂 蕊 星 塑 裔 赣 押 架 袂 ed、 的 设 计 方 法 、t op down 。 应 运 而 生 ， 它 从 系统总体要求出发，自 上而下地逐步将设计内容细化，最后完成系统硬件的 整体设计。 设计说明 5 v h d l行为模i 4 0. 模拟 vhdl-r tl 模拟 综合 测试向41生成 模拟 设计规范级 图形 v h d l i 具 lj 行为级 . - - - - - - -一 ， . 吮 响 . - - - - - 一 n 形v h d l 1 .,r 寄存器传输级 网表级 图1 - 6 t o p d o w n 的设计流程 8 路由器中 路由 转发机制的p p g a实现 第三章 系统级设计 第二章系统级设计 2 . 1 路由器系统结构 路山器提供 i p的路山和转发服务，一个路由器一 般由一个主控制器各 多个智能接口组成 ( 如图所示) 。 图2 - 1 路由器系统结构 路由 器控制器 ( r o u t e r c o n t r o l l e r )是整个路由 器的控制中心，它提供 操作、管理和维护 ( o a 2 ) i p 数 据 报被 送 入 ( 缓 存管 理 器) b u f f e r m a n a g e r 中 存起来; 3 )内部数据包被送入路山 转发器中; 4 ) 路由 转发器对内部数据包进行过滤和 i p路由 选择后，把内部数据 包送入缓存，再送到交换接口; 5 ) i p 数据报被再次 送入 缓存; 6 )对内部数据包进行排序处理; 7 )交换接口 将i p数据报送到相应的出口。 路由器中路由 转发机制的f p g a实现 第二章 缓存管理模块设计 第三章 缓存管理模块设计 在智能路由器接口中，缓存管理模块用于暂时贮存 工 p数据报，管理存 贮空间，并目 . 决定哪数据报将被丢弃。 缓存管理器山两大部分组成:存贮器和管理器 据报被分割成固定大小的块 ( l i n k l i s t ) ，通常为 下面是缓存管理器的结构: b u f f e r m a n a e e r m o d u l e 。在缓存中存贮的 t p数 :p a c k e t d a t a :p o i n t e r d a t a 图3 - 1缓存管理器的结构 路由 器巾路巾 转发 机制的f p g a实现 第章 缓存管理模块设计 3 . 1缓存管理器 ( l l m ) 缓存管理器是用来管理缓存的高速硬件设备，它对缓存中数据 ( l i n k ! i s t ) 的指针进行操作，管理空余缓存，并且进行一些丢弃处理。 缓存管理器的主要功能: . 缓存的分配 缓存， ， 的存4i il ii 11 被分判成许1, w rl 定人小的片，缓存竹t 9 ! j i x 5 1. 缓存中还没有被使用的片的地址，它所使用的指针 一 般是 2 0位的， 也就是说它的最大寻址范围是 1 m . . 缓存的封装 缓存管理器为网 络接口( l i r i c ) 和交换器 ( s w i t c h i n t e r f a c e ) 分配存贮空间，这些空间用来存贮从接口 接收到的 i p 数据报。 缓存管理器保存着指向存贮器中所存贮的 i p 数据报的指针，当一 个工 p 数据报比较大，一 个存贮片存不下时， 就需要用几个存贮片 来存一个数据报，这些存贮片由 缓存管理器连接在一起组成一个存 贮链。 . 空余缓存的管理 当 一块存贮空间被置上释放标记 后，缓存管理器将释放该存贮片。 . 听从c p u 的命令分配和释放缓存 c p u 可以直接为 i p 数据报分配缓存，也可以 从 l l m中把某个 i p数 据报删除，c p u 通过总线和缓存管理器进行联系。 . 垃圾的收集 缓存管理器记录着每一个存贮片最后一次被使用的时间。当 一 个存 贮片很久没有被使用，但它又不在空余缓存的列表中时，就会被视 为垃圾，并且被释放列入空余列表。c p u会对缓存进行定期的巡视， 检测出垃圾并对它们进行处理。导致垃圾产生的原因主要是 i p数 据报的奇偶较验错误。 垃圾的检测可以采用以下算法:在缓存管理器中为每一个存贮片设 一个变量，该变量在经过段比较长的时间后会自 动加 i , , l 该存 贮片被访问时相应的变量清 0 。如果一个存贮片的相应变量值大 于 3 时，该存贮片就可以被视为垃圾并且被清除。 . i p 数据报的丢弃 缓存管理器检测相应的控制位，来决定是否将一个 i p数据报丢弃 或是 将它传送到c p u . . 缓存的计数和 i p 数据报的多发 . 对内部数据包的处理 缓存管理器接收从数据流控制单元发过来的内部数据包，4且 对它 们进行如下处理: 缓存管理器决定一个内部数据包是否应该被送往 c p u ，如果是的话， 就把该内部数据包送往相应的f i f o ，并且给出正确的片选信号。 缓存管理器把一 个内部数据包发送到正确的网络接口( l i r i c )或 交换器。内 部数据包有它专用的总线和 f i f o ，当 f 工 f o已 满时，缓 存管理器就会丢弃内 部数据包和相应的工 p 数据报。 如果是个多播的 i p数据报，缓存管理器会检测相应的内部数据 路由 器中 路由 转发机制的f p g a实现 第三章 缓存管理模块设计 包中的标志字段，它标明该 i p数据报被读取了多少次，缓存管理 器每读一次i p 数据报，相应的标志字段就要加 t o 缓存管理器要支持的指令: b u f f e r m a n a g e m e n t c o m m a n d s r e g # u n i c a s t b u ff e r s = u n i c a s t b u ff e r s - p a c k e t s i z e ; e l s e i f m u lt i c a s t p a c k e t t h e n mc a s t b u ff e r c o u n t e r = m c a s t b u ff e r c o u n t e r - p a c k e t s i z e ; e n d i f ; 程序清单3 一 卫 路由器中 路由 转发机制的f p g a实现 第三章 缓存管理模块设计 i f u n i c a s t p a c k e t t h e n i f ( d r o p f r o m t a i l f o r t h i s l i r i c ) t h e n i f ( b u ff e r c o u n t e r l i r i c l i r i c - t h r e s h o l d ) t h e n d r o p p a c k e t ; e n d i f ; el s e b u f f e r c o u n t e r l i r i c + = p a c k e t r e c o r d s i z e ; u n i c a s t b u ff e r s + = p a c k e t r e c o r d s i z e ; en d i f ; e l s e i f m u l t i c a s t p a c k e t t h e n i f mc a s t b u ff e r c o u n t e r mc a s t t h r e s h o l d t h e n mc a s t b u ff e r c o u n t e r - = p a c k e t s i z e ; d r o p i n t e rn a l p a c k e t ; el s e m c a s t b u ff e r c o u n t e r + = p a c k e t r e c o r d s i z e ; f o r w a r d p a c k e t b a s e d o n l o c a l b i t m a p t o l i r i c s ; e a c h h a l f o f t h t b i t m a p c o r r e s p o n d s t o o n e l i r i c ; u p d a t e r e f e r e n c e c o u n t o f c o r r e s p o n d i n g p a c k e t ; e n d i f ; e n d i f ; r u n b u ff e r c o n t r o l a l g o r i t h m; 程序清单 3 - 2 还有一个附加算法来决定 l 工 r 工 c是否应当丢弃一个 i p数据报，这样做 的目的是为了同时实现缓存的动态分配和静态分配。 b u ff e r s iz e c o n tr o l t o t a l b u f f e r s = mc a s t b u ff e r c o u n t e r + u n i c a s t b u ff e r s ; o v e r fl o w = ma x b u ff e r s - t o t a l b u ff e r s ; wh i l e d y n a m i c a l l o c a t i o n a n d o v e r fl o w s e l e c t l i r i c s u c h t h a t b u f f e r c o u n t e r l i r i c ma x b u f t l i r i c ; s e n d d e l e t e s i g n a l t o t h a t l i r i c ; e n d w h i l e ; i f ( s t a t i c a l l o c a t i o n ) t h e n wh i l e ( b u ff e r c o u n t e r l i r i c ma x b u 红 l i r i c k e e p d e l e t e s i g n a l a s s e r t e d f o r t h i s l i r i c ; e n d w h i l e ; e n d i f ; 程序清单3 - 3 缓存管理器的状态由c p u 总线来控制， c p u 通过总线来对缓存管理器进 行初始化和差错控制。 路山脚卜 路山 转发机制的f p g a实现 第rl 缓存管理模块设计 3 . 2 缓存存贮器 ( b m ) 缓存存贮器中存放的是i p 数据报和内部数据包，它由缓存控制器控制， 存入 i p 数据报的内存的地址被存在内 部数据包中 c p u 通过总线控制 b m的状态，并且读写 b m ,c p u 还对 b m进行初始化和 差错控制。 路由 器中路由 转发机制的f p g a实现 第四章路由 转发 模块的设计 第四章 路由转发模块的设计 路由转发模块是一个路由器的核心，它主要实现以下功能: . 对收到的i p 数据报进行过滤处理 . 为收到的i p 数据报进行i p路由的查找 . 对收到的i p 数据报和即将发出的i p 数据报进行流量控制 下面是 路由 转发模块 ( f o r w a r d i n g p i p e l i n e ) 的结构示意图: f i l t e r t a b l e ram f i l t e r e n g i n e r o u t i n g t a b l e s ram i p l o o k u p f l o w t a b l e s r am i n g r e s s f l o w i d e n t i f i e r f l o w t a b l e s ram e g r e s s f l o w i d e n t i f i e r . . 图4 - i 路由转发模块的结构 路由器中 路由 转发 机制的f p g a实现 第四章 路由 转发模块的设6 1 图中的 i n t e r n a l p a c k e t m u x是一个多路选择器，所有的内部数据包 ( i n t e rn a l p a c k e t )都要经过它才能进入路由 转发模块。 一 个路由转发模块由三个部分组成，它连在一 起就像一条流水线，因 此我们把路由转发模块称作路由转发流水线 ( f o r o a r d i n g p i p e l i n e ) o 如图， t 个内部数据包多路选择器的输入有 3个来源，它们分别是 l i r i c , c p u ，以 及i ii l o o k u p 的 输出个i p 数据报到达l i r i c后， 自 的报头信息被提出来生成内部数据包，经过 i n t e r n a l p a c k e t m u x送到 f o r w a r d i n g p i p e l i n e ， 如果 该 数 据报 是单 播的， 就从f o r w a r d i n g p i p e l i n e 输 出到s w i t c h i n t e r f a c e , 如果是多播的， 就将其待播次数减i 再经i n t e r n a l p a c k e t m u x 送回f o r w a r d i n g p i p e l i n e ， 直至其次数减为0 . i n t e rn a l p a c k e t m u x 的 另个数据来源是 c p u，它传送的是一些特殊的内部数据包，这里就不再 i 羊 细讨论了。 4 . 1 内部数据包多路选择器 一个内 部数据包多路选择器 ( i n t e r n a l p a c k e t mu x )的电路结构如下: s e l l) s e l l d i n t) d i n l d i n t 图4 - 2内部数据包多路选择器的电路结构 图中d i n t) , d i n t , d in 2 分别是3 个数据输入， 它们都是3 2 位的数据线， d o u t 是数据输出，它也是3 2 位的数据线，s e 1 0 和s e l l 是两根选择线，它决 定d i n t) , d i a l 和d i n 2 v ,， 的哪一个将被输出。 s e l ls e 1 0d o 以 00d i n t) 01d i n t 10d i n 2 it 高阻态 图4 - 3选择线和数据输出的关系 下面是对该电路的v h d l描述: 路由器中路由 转发机制的f p g a实 现 第四章 路由 转发模块的设计 l i b r a r y i e e e ; u s e i e e e .s t 之l o g i c _ 1 1 6 4 .a l l ; e n t i t y p a c k e t m u x i s p o r t ( d i n 0 , d i a l , d i n 2 : i n s t d _ l o g i c _ v e c t o r ( 3 1 d o w n t o 0 ) ; c l k : i n s t d _ l o g i c ; d o u t : o u t s t d _ l o g i c _ v e c t o r ( 3 1 d o w n t o 0 ) ) ; e n d p a c k e 仁 m a x ; a r c h i t e c t u r e p a c k e t es m u x es a r c o f p a c k e t 一 m u x i s s i g n a l s e l : i n t e g e r r a n g e 0 t o 3 ; b e g i n p r o c e s s ( s e 1 0 , s e l l , d i n 0 , d i n l , d i n 2 , c l k ) b e g i n i f ( c l k e v e n t a n d c l k = 1 ) t h e n s e l d o u t d o u t d o u t d o u t 0 ) ; e n d c a s e ; e n d i f , e n d p r o c e s s ; e n d p a c k e 仁 m u x _ a r c ; 程序清单4 - 1 内 部数据包多路选择器 4