Westmont College 网络互连路由 (静态和动态路由;路由信息的传播; BGP, RIP, OSPF; 组播路由) CS 140 Part XIV 网络互连路由 (静态和动态路由;路由信息的传播; BGP, RIP, OSPF; 组播路由) Chapter 25

术语 转发、传递（ Forwarding） 路由（Routing） 指数据报传输 由主机或路由器执行 使用路由表 专指路由信息的传播 Westmont College CS 140 术语 转发、传递（ Forwarding） 指数据报传输 由主机或路由器执行 使用路由表 路由（Routing） 专指路由信息的传播 由路由器执行 插入/修改路由表中的值 2018/9/20 Chapter 25

两大类别的IP路由 Static routing：静态路由 Automatic routing：动态路由 系统启动时初始化路由表 除非检测到错误，否则路由不变 Automatic routing：动态路由 仍然是系统启动时初始化路由表 路由软件学习并更新路由表 可能持续改变 2018/9/20

静态路由 大多数的internet主机采用这种形式的路由 典型的路由表只有两项： 直接连接的网络 → direct delivery 否则，Default → 默认路由 2018/9/20

静态路由图示 2018/9/20

动态路由 IP 路由器使用 需要特殊软件 使用该软件与其他路由器交换路由信息 交互时使用路由传播协议（route propagation protocol） 更新本地路由表 2018/9/20

路由传播图示 Each router advertises destinations that lie beyond it 每个路由器都将自己能到达的目标通知其他路由器 2018/9/20

路由交换的要点 Each router runs routing software that learns about destinations other routers can reach, and informs other routers about destinations that it can reach. The routing software uses incoming information to update the local routing table continuously. 在每台路由器上都运行着路由软件，路由软件可以知道其他路由器能够达到的目标，并且将自己能到达的目标通知其他路由器。路由器使用收集到的信息不断更新本地路由表。 2018/9/20

自治系统概念（Autonomous System） 动机：在internet上，如果所有路由器都试图交换路由信息，会怎样？ 为了限制路由通信量，internet使用两级路由层次，将internet上的路由器和网络分为组，组内所有路由器互换信息，然后每组中至少一台路由器汇总这些信息，再把这些信息传递给其他组。 问题： 组的规模多大？ 一个组内的路由器使用什么协议？ 如何表示路由信息？ 组间路由器使用什么协议？ 答案：没有答案 2018/9/20

自治系统概念（Autonomous System） AS：在一个管理权威控制下的，一个网络和路由器的连通集合 灵活、软性定义 例如: a single corporation 由于没有哪个路由协议能扩张到整个internet，因此只能采取这种分组的方法，每个组是一个AS,每个 AS 可自行选择路由协议. 2018/9/20

Inernet路由协议分类 两类 内部网关协议：Interior Gateway Protocols (IGPs) 自治系统内部路由器之间交换信息使用的协议 目标在IGP内部 外部网关协议：Exterior Gateway Protocols (EGPs) 在自治组之间使用 目标跨越Internet 2018/9/20

IGP / EGP 图示 在自治系统内部，IGP软件使用路由度量选择到达每个目标的最优 2018/9/20

路由和数据流量 Each ISP is an autonomous system that uses an Exterior Gateway Protocol to advertise its customers’ networks to other ISPs. After an ISP advertises destination D, datagrams destined for D can begin to arrive 每个ISP都有一个自治系统用EGP将其客户网络通告其他ISP.只有这样，数据才可以到达这些客户。 2018/9/20

特殊的路由协议 边界网关协议：Border Gateway Protocol (BGP) 路由信息协议：Routing Information Protocol (RIP) 开放最短路径优先协议：Open Shortest Path First Protocol (OSPF) 2018/9/20

边界网关协议 Border Gateway Protocol (BGP) 提供自治系统级的路由信息 (EGP) 管理员可通告配置来限制BGP向外部发布的路由 使用 TCP通信，提供可靠传输 给出自治系统到其它每个目的的路径 是目前的internet所使用的 EGP，所有ISP都参与路由信息的交换，所以从任意一台计算机到任意目标的数据报均会被正确路由和转发 Current version is four (BGP-4) 2018/9/20

路由信息协议 The Routing Information Protocol (RIP) 一种内部网关协议 (IGP) 按跳数计量距离，源和目标之间的每个网络计为一跳，直接连接计为一跳。 使用UDP进行消息传输 使用广播或多播传送 采用距离向量算法(Distance vector algorithm) 支持默认路由传播，方便安装 实现： Unix program routed 2018/9/20

距离向量：Distance Vector 路由器之间周期性的、双向交换信息 交换时，路由器发送 接收方 List of pairs：big! 每个 pair 给出 (destination, distance) 接收方 将收到的list同自己的路由表比较 如果有更好的路由即修改 2018/9/20

RIP Packet Format 2018/9/20

开放最短路径优先协议 The Open Shortest Path First Protocol (OSPF) RIP不适合大型组织对路由协议的需求。 一种内部网关路由协议 (IGP) 提供 CIDR 和 subnet 地址格式支持 提供认证的消息交换，安全性增强 允许路由器引入其它手段获得的路由 采用链路状态算法：SPF 支持多路存取网络 (e.g., Ethernet) 2018/9/20

Dijkstra’s SPF Algorithm 以自己为源节点 向外移动 在每一步 寻找满足如下条件的节点u 未计算过 与源节点距离最近 计算 U与每个neighbor v的距离 如果距离更短，建立一条通过U到v的路径 2018/9/20

OSPF 区域和效率 OSPF允许层次路由，为了获得层次，允许管理员把一个AS中的路由器和网络划分为子网，这种子网称为区域（AREA）. 配置每台路由器使之知道区域的边界。 当OSPF允许时，给定area内的路由器定期交换链路状态消息 允许area之间的通信，通信前先要汇总自己area的信息 将广播限制在区域中，降低了overhead ，更适合处理大型互连网络 2018/9/20

Internet中的链路状态：Link-Status 路由器对应图中节点 网络对应边 邻近连接的一对路由器周期性地： 测试彼此之间的连通性 把该 link-status 广播到整个 area 每个路由器利用收到的 link-status messages 来重新计算最短路径 2018/9/20

OSPF 图 (a) 由路由器连接的7个网络组成的互连网 (b) 对应的 OSPF 图 每个路由器对应图中的一个节点 2018/9/20

OSPF 要点 Because it allows a manager to partition the routers and networks in an autonomous system into multiple areas, OSPF can scale to handle a much larger number of routers than other IGPs 因为OSPF允许管理员将自治系统中的路由器和网络划分为多个区域，所以OSPF可以比其它IGP更适合处理含有大量路由器的互连网络。 2018/9/20

Summary 主机一般采用静态路由 路由器使用动态路由 Internet 划分为自治系统 路由协议分为两种： Interior Gateway Protocols (IGPs) provide routing within an autonomous system Exterior Gateway Protocols (EGPs) provide routing among autonomous systems 2018/9/20

Summary (continued) Border Gateway Protocol (BGP) is current EGP used in Internet Interior Gateway Protocols include: Routing Information Protocol (RIP) Open Shortest Path First protocol (OSPF) 2018/9/20