中国斜学巷术大学 信息网给与协议 UKIVERIT背OP SCIENC建D TECHNOLO0YO年Ca框NA P路由器功能 ·数据路径功能 一根据分组目的IP地址查找转发表 一通过交换结构转发到输出端口 -输出端口调度和队列管理 ·控制面功能 一运行路由协议，构建路由表 一系统配置和管理
信息网络与协议 IP路由器功能 • 数据路径功能 – 根据分组目的IP地址查找转发表 – 通过交换结构转发到输出端口 – 输出端口调度和队列管理 • 控制面功能 – 运行路由协议，构建路由表 – 系统配置和管理
中国钟学我术大草 信息网给与协议 UKIVERIT背OP SCIENC建D TECHNOLO0YO年Ca框NA 主要内容 。概述 ·路由查找算法 ·交换结构
信息网络与协议 主要内容 • 概述 • 路由查找算法 • 交换结构
中国钟学我术大草 信息网给与协议 UKIVERIITY OF SCIENCE AND TECHNOLOOY OF CHINA 前缀最长匹配 采用CIDR后，IP地址中前缀（网络号的长度） 不固定，可能匹配到多个转发表项 Destination Address Prefix Next Hop IP Address Output Interface 24.40.32/20 192.41.177.148 2 130:86/.16… 1924117.7.181 6 208.12.16/20 192.41.177.241 4 208.12.21/24 192.41.177.196 16724.103724 1924773r 208.12.21.45 00010101 采用前缀最长匹配
信息网络与协议 前缀最长匹配 采用CIDR后，IP地址中前缀（网络号的长度） 不固定，可能匹配到多个转发表项 采用前缀最长匹配 208.12.21.45 0001 0101
中国钟学我术大草 信息网给与协议 IVERUITY OF SCIENC建ADT比CHNOLO0YO年LNA 前缀最长匹配 前缀最长匹配并不简单！ -P地址中没有携带任何前缀长度信息 一有可能需要对转发表中的所有表项都进行匹配 →效率低！ 核心路由器经常有上万甚至几十万条前缀 为此，我们需要提出更加高效的路由查找算法！
信息网络与协议 前缀最长匹配 • 前缀最长匹配并不简单！ – IP地址中没有携带任何前缀长度信息 – 有可能需要对转发表中的所有表项都进行匹配 →效率低！ 为此，我们需要提出更加高效的路由查找算法！ 核心路由器经常有上万甚至几十万条前缀
中国斜学技术大享 信息网给与协议 UKIVERIT背OP SCIENC建D TECHNOLO0YO年Ca框NA 性能度量 查找速度 决定链路带宽（10Gbps链路要求每秒转发31.25*106个分组，最小 P分组长度为40字节) ·存储（空间）需求 一存储访问速度、功耗 一基于缓存的软件算法 更新代价 在峰值时，.Internet.上每秒钟的BGP路由更新有几百次，要求能够 处理每秒上千次更新 可扩展性 一转发表预计每年都在增加 实现的灵活性 一既能软件实现，也能硬件实现
信息网络与协议 性能度量 • 查找速度 – 决定链路带宽（10Gbps链路要求每秒转发31.25*106个分组，最小 IP分组长度为40字节） • 存储（空间）需求 – 存储访问速度、功耗 – 基于缓存的软件算法 • 更新代价 – 在峰值时，Internet上每秒钟的BGP路由更新有几百次，要求能够 处理每秒上千次更新 • 可扩展性 – 转发表预计每年都在增加 • 实现的灵活性 – 既能软件实现，也能硬件实现