第六章路由和交换
信息网络与协议 第六章 路由和交换
中国钟学我术大草 信息网倍与协议 UKIVERIT背OP SCIENC建D TECHNOLO0YO年Ca框NA 主要内容 ·概述 ·路由查找算法 ·交换结构
信息网络与协议 主要内容 • 概述 • 路由查找算法 • 交换结构
中国斜学技术大享 信息网给与协议 UKIVERIITY OF SCIENCE AND TECHNOLOOY OF CHINA Local Local 路由和交换 network network Node B 路由代表更宏观的概念，是将 分组从网络中的一个网络投递 到另一个网络的过程 Node 一需要网络中节点协作 一运行路由协议 Local 交换是指在同一个网络节点内 network 的分组传输，是指将分组从一 个端口（输入端口）转发到另 Inputo 一个端口（输出端口）的过程 一属于网络设备自己的功能 Input2 基于转发表，查找算法和交 换结构 Output1 Output3
信息网络与协议 路由和交换 • 路由代表更宏观的概念，是将 分组从网络中的一个网络投递 到另一个网络的过程 – 需要网络中节点协作 – 运行路由协议 • 交换是指在同一个网络节点内 的分组传输，是指将分组从一 个端口（输入端口）转发到另 一个端口（输出端口）的过程 – 属于网络设备自己的功能 – 基于转发表，查找算法和交 换结构
中国斜学卷术大学 信息网给与协议 IVERUITY OF SCIENC建ADT比CHNOLO0YO年LNA 路由协议、路由表和转发表 路由器之间通过路由协议交互信息执行路 由算法生成路由表 一 转发表是基于路由表生成的 一 一在路由器或者交换机上，根据转发表来决定分 组的输出端口
信息网络与协议 路由协议、路由表和转发表 • 路由器之间通过路由协议交互信息执行路 由算法生成路由表 – • 转发表是基于路由表生成的 – – 在路由器或者交换机上，根据转发表来决定分 组的输出端口
转发表 目的P地址 IP分组 输入 端口 输出 交换结构 端口 决定路由器性能： (1)路由查找算法：如何快速地决定输出端口 (2)交换结构：如何快速地交换到输出端口
信息网络与协议 IP分组 目的IP地址 交换结构 决定路由器性能： （1）路由查找算法：如何快速地决定输出端口 （2）交换结构：如何快速地交换到输出端口 转发表 输入 端口 输出 端口
中国斜学巷术大学 信息网给与协议 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路由更新有几百次，要求能够 处理每秒上千次更新 • 可扩展性 – 转发表预计每年都在增加 • 实现的灵活性 – 既能软件实现，也能硬件实现