第六章 IP路由协议 主讲人: 单 位:重庆大学计算机学院 2008年3月.

Slides:



Advertisements
Similar presentations
网络管理员考证辅导 —— 真题解析 广东水利电力职业技术学院 计算机系 温海燕
Advertisements

NAT与ICMP交互.
寻址与路由技术 IP地址 ARP协议 IP地址的扩展 Internet的组播 Internet群组管理协议 自举与动态配置 端口与套接字
TCP/IP协议原理与应用.
第 4 章 网络层 本章主要内容: 4.1 网络层提供的两种服务 4.2 网际协议 IP 虚拟互连网络
计算机网络课程总结 一、计算机网络基础 计算机网络定义和功能、基本组成 OSI/RM参考模型(各层的功能,相关概念, 模型中数据传输 等)
LSF系统介绍 张焕杰 中国科学技术大学网络信息中心
第 4 章 网络层 数学科学学院 冯世斌.
第 4 章 网络层.
计算机网络教程(第 2 版) 第 7 章 网络互连 课件制作人:谢希仁.
第四章 网络层 网络层 网络层 网络层 网络层 网络层.
因特网 TCP/IP协议 IP路由技术 Internet接入技术 Internet服务.
淄博信息工程学校 ZIBOIT&ENGINEERING VOCATONAL SHCOOL 03 交换机干道技术 计算机网络技术专业.
1. 理想的路由算法 有关路由选择协议的几个基本概念 算法必须是正确的和完整的。 算法在计算上应简单。
实验八 配置动态路由-OSPF协议.
路由器繞送協定- 第三章 路由器動態繞送服務
引言 路由器的主要工作就是为经过路由器的每个 IP数据报/分组 寻找一条最佳传输路径(寻径),并将该数据有效地传送到目的站点(转发)。
第13讲 IGRP协议 主讲:史宝会.
第4章 路由原理及路由协议.
计算机网络技术 项目负责人 张嗣萍/本环节主讲教师 第5章 路由器与路由选择 (2)路由选择与数据转发 2007年度上海建桥学院教改课程
第3章 路由技术—动态路由.
网络技术之六: 路由技术 22:00.
路由协议概述 ISSUE 1.0 日期: 杭州华三通信技术有限公司 版权所有,未经授权不得使用与传播.
第4章 网络路由设计 本章要点: 4.1 路由选择算法 4.2 路由选择协议.
多播技术 郑州大学信息工程学院李向丽.
第17章 实现路由器.
项目四 组建跨地区网络 授课教师:肖颖.
计算机网络 吴功宜 编著 欢迎辞.
网络系统集成技术 网络互联技术 第六章.
TCP/IP基本原理 第五章 路由原理与协议
第 6 章 IP 遶送.
Westmont College 网络互连路由 (静态和动态路由;路由信息的传播; BGP, RIP, OSPF; 组播路由)
Kvm异步缺页中断 浙江大学计算机体系结构实验室 徐浩.
LSF系统介绍 张焕杰 中国科学技术大学网络信息中心
计算机网络原理 计算机与信息工程分院 周文峰.
基礎網路管理 第十一章 OSPF路由協定 製作:林錦財.
IPv6 地址空间.
32 bit destination IP address
锐捷网络技术培训系列课程-(中级) OSPF协议 培训组 闵 捷.
大学计算机基础 典型案例之一 构建FPT服务器.
第七章 路由器技术和路由选择协议 于银辉 教授 吉林大学 通信工程学院.
管理信息结构SMI.
矢量距离路由.
网络常用常用命令 课件制作人:谢希仁.
实用组网技术 第一章 网络基础知识.
Windows网络操作系统管理 ——Windows Server 2008 R2.
Windows网络操作系统管理 ——Windows Server 2008 R2.
第十章 IDL访问数据库 10.1 数据库与数据库访问 1、数据库 数据库中数据的组织由低到高分为四级:字段、记录、表、数据库四种。
第5讲 网络层 本讲目的: 概述: 理解网络层服务原理: 因特网的实现实例 网络层的服务 路由选择原理 分层的路由选择 IP协议
第十三章 TCP/IP 與 Internet 網路連結技術
用event class 从input的root文件中,由DmpDataBuffer::ReadObject读取数据的问题
简单介绍 用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)
第6章 IP路由 RIP----路由信息协议(Routing Information Protocol)
WPT MRC. WPT MRC 由题目引出的几个问题 1.做MRC-WPT的多了,与其他文章的区别是什么? 2.Charging Control的手段是什么? 3.Power Reigon是什么东西?
计算机网络与网页制作 Chapter 07:Dreamweaver CS5入门
宁波市高校慕课联盟课程 与 进行交互 Linux 系统管理.
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
Distance Vector vs Link State
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
数据报分片.
第4章 网络层.
谢聪.
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
GIS基本功能 数据存储 与管理 数据采集 数据处理 与编辑 空间查询 空间查询 GIS能做什么? 与分析 叠加分析 缓冲区分析 网络分析
Distance Vector vs Link State Routing Protocols
基于列存储的RDF数据管理 朱敏
3.8 局域网应用实例 某省劳动和社会保障网络中心组网实例 会议中心的无线组网实例.
实验六静态路由.
外部网关协议.
第 4 章 网络层.
Presentation transcript:

第六章 IP路由协议 主讲人: 单 位:重庆大学计算机学院 2008年3月

目录 6.1 原始Internet选路和自治系统 6.2 内部网关协议IGP 6.3 外部网关协议EGP 6.4 IGP与EGP的结合 6.5 组播协议

6.1 原始Internet选路和自治系统 6.1.1 引言 6.1.2 使用部分信息进行路由选择 6.1.1 引言 6.1.2 使用部分信息进行路由选择 6.1.3 原始Internet的结构和核心 6.1.4 距离向量路由算法 6.1.5 网关到网关GGP路由协议 6.1.6 SPF链路状态算法 6.1.7 自治系统的产生

6.1.1 引言 1、两个问题 问题1:寻径表应该包含什么内容? 拓扑:需要考虑 Internet的结构: 负载: 6.1.1 引言 1、两个问题 问题1:寻径表应该包含什么内容? 拓扑:需要考虑 Internet的结构: 负载: 问题2:寻径表内容如何获得? 需考虑两个路由器间的路由交换 多个路由器间的路由传输 二个问题的选择是根据 结构的的复杂度 互联网络规模的大小 管理策略

2、路由表的建立与维护过程 建立路由包含两个阶段: 初始化 (Initialization) 更新 (Update) 启动时,从辅存储装置读取 启动时,只提供一个空寻径表,执行一些命令来填入 启动时,从相邻路由器获得初始寻径表 更新 (Update) 静态 (static)、手动 (manually) 动态 (dynamic) 、自动 (automatic)

6.1.2 使用部分信息选择路由 主机或路由器不可能知道所有可能的目的地址或所有可能的目的网络,亦即它们只知道部分信息 (partial information) 主机的寻径表:通常只要两个路径 本地网络:直接传送 默认设路 (default route) :间接传送 (将所有的非本地报文送到预设路由器传送) 路由器的寻径表:通常有较多的路径 本地网络 (可能有好几个):直接传送 已知网络 (可能有很多): 选路 不可知网络:默认路由 (default route) 间接传送 (将所有的不知路径的报文送到预设路由器传送)

部分路由信息 路由选择一般只能使用部分路由信息 部分路由信息在某种条件下是足够的 1)路由信息是正确的 2)路由信息是一致的 3)路由信息是完备的 从整个网络拓扑来看,所有路由器的路由信息集合覆盖了整个网络

6.1.3 原始Internet的结构与核心 1. 寻径表的维护 2. 原始的 Internet 结构 早期的 Internet (以 ARPANET 为主干):手动 Internet 发展壮大后:自动 2. 原始的 Internet 结构 骨干 (backbone) 或核心 (core) 网络 小而且集中的路由器集合 (核心路由器) 具备完整的路由信息 (不使用默认路径) 特点: 一致性  不具成长性 对等 (peer networks) 或非核心 (non-core) 网络 大而且分散的路由器集合 (非核心路由器) 只具备部份路由信息 (需设置一个核心路由器为默认路肉器) 特点 可适应于本地网络改变  不一致性

3、骨干(核心)网络结构下的路由 两级结构 1)核心路由器 2)外围路由器 (2) 核心路由器 1)将LAN联接 ARPANET主干 2)不使用默认路由 (3)核心使用默认路径的问题 1) 易形成环路 2) 无效率G1 到 Gn 要经过 N个路由器)

(4) 骨干网络的路由抽象结构 核心路由器拥有完整路由信息 (不需默认路径) 外围路由器需要默认路径,该默认路径指向核心路由器

4、从核心结构到对等式主干 Internet 引入NSFNET骨干后更增加了寻径的复杂度 NSFNET经由匹兹堡的单一路由器连接到 ARPANET 骨干 当 NSFNET 成長, ARPANET 骨干和 NSFNET骨干之间出现多重连接,这两个骨干则称为对等骨干 (peer backbone)

寻径的复杂性示例 (1) 路由实例 主机 3 主机2 … 1) NB  Ri  AB(Ri=R1、R2、R3) 主机 3 主机1 2) NB  R1  AB  R2  NB  R3 AB … 主机 3 主机1 1) NB  R1  AB(最短路径) 2) NB  R2  AB 3) NB  R3  AB …

(2) 路由问题 问题1:单独路径问题 到H1 和到H2应有的不同路径,即使它们都连接到 ARPANET 骨干 问题2:路径一致性问题 两个骨干必须在所有路由器之保持路径的一致性 实现比较困难

(3)对等网络的抽象结构 1)核心结构与网络拓扑应该分离 2)核心结构可以跨多个网络:最短路径 3)核心结构不应该再划分成若干子结构、采用默认路由

5、两种结构的特点 骨干 (backbone) 或核心 (core) 网络 1) 小而且集中的路由器集合 (核心路由器) 2) 具备完整的路由信息 (不使用默认路径) 特点: 一致性  不具成长性 对等 (peer networks) 或非核心 (non-core) 网络 1)大而且分散的路由器集合 (非核心路由器) 2)只具备部分路由信息(需设置一核心路由器为默认路由器) 特点 可适应于本地网络改变  不一致性

都采用了动态路由更新策略,而不是人工维护 原因在于: 1)链路可能失败或被其他链路取代 2)网络可能过载或闲置 3)人工不能对快速的改变立刻做出反应 4)动态路由更新策略 基于距离矢量的 基于链路状态的

6.1.4 距离向量路由算法 (1)路由器保留一份所有已知的路由在表格中。 (2)启动时,在初始路由器表中包含每一个直接连接的网络 (3)表格內每一记录识别出一个目的网络,并且指出到该网络的距离 (distance),这些记录就称为距离向量 (vector) 。 通常距离的度量单位为跳 (hop) 。

(4) 各路由器周期地将路由表发送到可直接到达的网络 (5) 当来自路由器 J 的路由表报告抵达路由器 K 时,K 逐一检查每一目的地所对应的距离记录,并按一下规则更新其路由表: [较佳路由] 若 J 知道一条可以到达已在 K 表內的目的网络的更短路径; [新增路由] 若 J 给出一个原先不在 K寻径 表內的目的网落 [相同路由,但距离改变] 若 K 目前所要通往目的网络的路径是经过 J 而 J 通往该目的网络的距离改变。

示例 To Net 4 经过 J: 3 + 1 =4 原先经过 L: 8 较佳路径 修改 To Net 21 径过 J: 4 + 1 =5 新增路径  新增 To Net 42 原先经过 J: 2 距离改变  修改 J

To Net 1 To Net 24 经过 J: 2 + 1 =3 (较长) 直接:0 非较佳路径  不变 距离未变  不修改

优缺点 (1) 距离向量 (Distance-Vector) 来自周期性报文所包含的路由信息,包括(V,D),其中 V = 目的网络 (2) 为了达到路由的有效和一致性,所有路由器必须参与距离向量的交换 (3) 优点 容易实现 (4) 缺点 周期交换路由信息 增加通讯量 不适于规模大的网络 路由改变的传播缓慢 不能适应路由信息变化快的情况,算法难以稳定(收敛) 有些路由器可能会传播不正确的路由信息

6.1.5 网关到网关GGP协议 网关-网关协议GGP (Gateway-To-Gateway Protocol、GGP) (2) 作用 原始的核心路由器所使用 距离向量协议,使用了距离分方法 已经不是 TCP/IP 标准 (N, D) N = IP 网络地址 D =距离 (跳) (2) 作用 新的核心路由器告知其近邻它所能到达的网络及费用; 核心路由器更新它们的寻径表; 核心路由器向其他路由器传播新的路由信息。

(4) GGP采用的距离分解 (distance factoring) (3) 路由信息 表示法 线性表示法 (linear) 阶层式表示法 (hierarchical) – 减少信息大小 (4) GGP采用的距离分解 (distance factoring) 避免传送相同距离的数值的拷贝 序对用距离来排序,每个距离值 (抵达该网络的距离) 只出现一次,该距离的可达网络紧接在后面 其他分解协议 距离 目的站序列

可靠性与路由协议 例如:GGP 可使用正确确认 (positive ACK)或否定确认 (negative ACK) (1)多数的路由协议使用无连接传输。 GGP 直接封装在 IP报文中 目前的路由协议则通常封装在 UDP 报文中。 (2) 传送处理技术: 出错 (corruption):校验和 (Checksum) 丢失 (loss): 软状态 (Soft states) 或确认与重传机制 例如:GGP 可使用正确确认 (positive ACK)或否定确认 (negative ACK) 失序 (out-of-order):序号 (Sequence number)

6.1.6 SPF:shortest path first---链路状态算法 1、距离向量算法的缺点 不能扩大规模:分布式最短路径算法 反映缓慢 大量的信息交换:报文数目与网络数目成正比 所有的路由器必须参与 2、链路状态 (link state、link status) 最短路径优先SPF 每个参与的路由器都拥有完整的拓扑 (topology) 信息 拓扑信息就是一张图,路由器对应于节点,而边则对应路由器所连接的网络。

(1)主动测试所有邻近路由器的状态。 3、SPF过程 邻近路由器 (neighbor routers) 即两个路由器共用一条连接 也即两个路由器接到一个共同的网络 路由器周期性的传送短信息以询问邻近路由器是否活着或可达 若近邻路由器做出响应,则认为该连接开启 (up);否 则认为该连接关闭 (close)。 (2)路由器周期性向所有其他路由器传播连接状态。 利用广播或点到点 (3)路由器利用此信息更新其网络拓扑图,将各连接标记上开启或关闭状态标识。然后运用 Dijkstra 最短路径算法重新计算路径

SPF的优点 (1)独立计算路由 (2)容易除错 (3)算法收敛 (4)信息量小 更适合大规模的互联网络 每个路由器使用相同的原始状态数据独立计算路 (2)容易除错 因为连接状态信息的传播是不变的,所以易于调试 (3)算法收敛 因为路由器是在本地执行路由计算,所以保证收敛 (4)信息量小 因为连接状态只带有一些关于单一路由器的直接连接信息,因此大小与 internet网络数目无关。 更适合大规模的互联网络

6.1.7 自治系统的产生 核心结构模型不能满足需要 核心结构模型不能适应大规模网络 (2) 核心结构路由的特点 1) 所有路由器都直接联在主干上 2) 所有路由器都参与路由更新 3) 核心路由器包含所有路由信息 4) 每个路由器都了解与自己相连的本地网络

核心系统存在的问题 (3) 核心结构的不足 1) 每个网点仅有一个本地网络。带来两个问题 单个网点规模问题:规模受限 网点太多的问题 :特别是核心路由器,会产生很大的选路通信量(路由更新报文所产生的通信量) 2)在互联网络中,网络和路由器属于不同管理机构拥有,选路也不完全遵循最短路径原则。需要考虑独立管理机构的影响。 3)所有路由器都参与路由信息更新是不可能的

路由规模问题(群组) 与路由相关的两个主要问题:时延、开销 时延:路由信息更新时延 开销:路由更新报文所产生的通信量 (2) 一般性结论(实验所得) 1)最多12个路由器可安全参与一个广域网路由协议 2)最多60个路由器可安全参与一个局域网路由协议 一般与网络时延、容量有关 (3) 路由规模很难确定,特别是Internet 可以通过对通信量的长期监视、利用统计方法获得一个满意的规模大小值

额外跳问题 群组是受限的 群组之外的路由器只能采用默认路由机制 把群组内的某个路由器作为默认路由器,如R1 (3) 问题:不是最佳路径、消耗较多带宽

如:R1、R2在群组内;R3不在; R3选R1作默认路由器,则: R3->R2:R3->R1->…>R2:非最佳 (4) ICMP也无法利用重定向报文通知R3,原有路由是非最佳的 (5) 解决办法:允许群组外路由器从群组路由器获得路由信息信息

隐藏网络问题 群组内存在隐藏网络:本例中的Lan4对R1是隐藏的 必须有一个路由器把Lan4通告给R1 本例选R4、经由R3向R1通告。但此方法存在问题 R3不合适,因为R3不了解Lan4

自治系统AS (1) 概念 (Autonomous System,AS) 由单一的管理机构所控制的一组网络和路由器所构成的群 组,就称为自治系统 (2) 在一个AS内,可自由选择路由协议 包括:路由发现、路由传播、路由一致性检测与保障机制 (3) 每个自治系统都有一个AS编号,其是独立的 (4) 自治系统指定一个或多个路由器,把AS内的可达网络情况 通知给另一个自治系统

6.2 内部网关协议IGP 6.2.1 AS内静态、动态路由比 6.2.2 RIP 6.2.3 HELLO 6.2.4 OSPF

6.2.1 动态路由、静态路由比较 手工模式不适合复杂的网络 增加了R5后,R2、R3之间有了冗余路径 冗余路径的切换,若采用人工方式,显然不合适 很难保证路由正确(因为要求最短路径)

内部路由器使用的协议 在AS内部,路由协议没有统一的标准 内部路由器可使用两类协议 1)内部网关协议:IGP 2)外部网关协议:EGP-BGP4.0 (3) 有多种内部网关协议 1)RIP 2)OSPF …

6.2.2 RIP 1、RIP历史 1) Xerox NS RIP,由Xerox的PARC研究中心提出的网络互连协议 2) Routed 在Uinx系统上实现,称为Routed; 利用物理网络的广播功能交换路由 不是为大型网络设计的 3) RIP因为Unix的流行而壮大,在成为标准之前已被广泛使用和接受 4) 1986成为标准 因为

RIP操作 距离-向量协议 两种工作模式:主动模式、被动模式 主动模式:发起路由通告 被动模式:接受路由通告、更新自己的路由表 路由器:工作在主动模式下 主 机:工作在被动模式下 (5) 路由通告间隔:30秒、广播路由 (6) 路由更新报文的内容:距离向量(目的网络、距离) 距离:路由跳数 (7) 基于路由跳数的最短路径不一定是最佳路径(时间) 修正办法:允许人工配置跳数(加大低速线路的跳数)

路由建立、更新实例 R1: (Net1,1,R1); 在Net2上广播(Net1,1)

RIP对故障路由器的处理 收到某路由器R的消息后,启动定时器 若R在180秒内没有进行通告新的路由,则认为该路由器失效

RIP必须处理的3类错误 路由环路问题 不能完全检测出路由环路;假定其他路由器都是可信的 (2) 路由稳定问题 (2) 路由稳定问题 路由长度必须有上限,RIP采用16作为上限。16表示不可达、或者路径无限长。 (3) 慢收敛、无限计数问题 更新报文在网络中的传播速率慢。 路由达到一致性的收敛速率慢

慢收敛实例 产生的原因: 节点没有全局拓扑 通告方式、更新方式存在不足 (a) R1 (Net 1,R1,1) R2 (Net 1,R1,2) R3 (Net 1,R2,3) 以上为正常情况 (b) 网络1与R1连接失效,对R1,则 old : (Net1,R1,1) New1: (Net1,R1,16) 若在广播New1前收到R2:(Net1,2) 则New2:(Net1,R2,3) (c)对R2: old: (Net 1,R1,2) 收到R1:(Net1,3) New:(Net1,R1,4) … 直至距离达到16 产生的原因: 节点没有全局拓扑 通告方式、更新方式存在不足

RIP慢收敛解决办法 路由器不会把路由信息回传;可解决本例中的慢收敛问题. Ri: (Net,Rj,D),则Ri不回传(Net,D)给Rj 1) 分隔范围更新 路由器不会把路由信息回传;可解决本例中的慢收敛问题. Ri: (Net,Rj,D),则Ri不回传(Net,D)给Rj 2) 抑制技术 若Rj收到Ri: (Net,16)报文,则Rj在60秒内忽略Rk:(Net,D)报文 期望在60秒内,其他路由器都收到(Net,16)报文 3) 毒性逆转技术 在若干周期内保留该路由,如R1(Net,16),并且多次通告 4) 触发更新技术 路由器在接受到不可达时就广播, 易引发广播雪崩现象 以上各种技术都不能完全解决RIP慢收敛问题

RIP报文 报文类型 1) 请求报文 2) 路由更新报文 (2) 报文的结构 1) 报头(32字节) 2) 可选部分: (网络,距离)列表 (2) 报文的结构 1) 报头(32字节) 2) 可选部分: (网络,距离)列表 RIP报文的普适性 (1)适应多种网络 (2)地址达14个字节 对IP:地址中的3-6字节 工作模式: (1)请求(报文),响应(报文) (2)定期广播响应报文

RIP路由解释和聚集 RIP v1报文中不包含子网掩码 RIP v1不适合CIDR和变长掩码环境   下一跳的作用:防止路由环路、慢收敛

RIP2 包文格式 路由标记:ROUTE TAG 用于标识路由的原始起点,可用于传播AS号 RIP 的传播 UDP port 520 (destination) 源端口原则上也是520

RIP跳数的缺陷 跳数限制太小,限制了网络跨度 任何两台计算机间只能有15台路由器 (2) 跳数测度的问题 1) 跳数不能反映网络负载的变化 网络跨度: 不是指路由器台数、也不是指路由器密度 结论:不适合非层次结构、大型自治系统 (2) 跳数测度的问题 1) 跳数不能反映网络负载的变化 2) 基于跳数的最短路径不等同于最佳路径 不能保证产生最小时延、最高容量的路由

6.2.3 Hello协议 Hello协议的特点 1) 距离向量IGP路由协议 2) 采用时延作为距离测度 3) Hello协议在NSFNET中得到使用 (2) Hello协议的功能 1) 时钟同步 2) 每个机器都能计算到目的地的最短路径

时钟同步 更新报文与更新策略 1) 更新报文(Net,Delay) 2) 更新策略:同RIP Hello 报文包含有时戳timestamp、路由信息 每个路由器维持一张时延表,该时延表包含了该路由器对相邻路由器的时钟的最佳估计值 发送路由器s发送报文时,附上其当前时戳TSs 接受路由器r收到报文时,先估计发送路由器的当前时钟值ETSn,用ETSn-TSs作为链路时延 路由器对相邻路由器进行周期轮询,以便准确时钟值。 更新报文与更新策略 1) 更新报文(Net,Delay) 2) 更新策略:同RIP

时延测度及路由震荡问题 时延测度的不足:时延不稳定;路由震荡 影响时延的最大因素:网络负载 避免震荡的启发式方法: 1) 抑制技术: 防止路由频繁切换 2) 精度技术:舍入技术 阈值技术:时延差小于某一个值时,认为没有变化 3) 平均值技术、N中取K技术 用平均值作比较 N次测量中有K次,其值小于当前路由时延,则切换 结论:启发式方法不能消除路由震荡

路由震荡实例 设有两条线路:一条卫星线路;一条串行线路9600bps 卫星线路:容量大;时延大 正常情况下:串行线路的时延《 卫星线路时延 首先选择串行线路、使得串行线路超载,时延急剧增加 在此情况下,路由转向卫星线路 此时,串行线路恢复正常,时延急剧减少 卫星线路的时延基本不会改变 再次选择串行线路,进入路由震荡

6.2.4 OSPF协议 1、OSPF的目标或成就 1) 开放Open 各种规范是公开的 任何人可以实现,无需付许可费 2) 支持TOS路由 3) 提供负载均衡:多条路径间的负载平衡 4) 支持区域划分 一个AS系统可进一步划分成区域; 各区域是自包含的:区域的拓扑结构对其它区域隐藏的

5) 支持鉴别机制 允许各个区域间采用不同的鉴别机制 确保可信任路由期间才能进行路由信息交换 6) 支持多种网络;支持特定主机路由、子网路由、特定网络路由 广播多路访问型(Broadcast MultiAccess)、 非广播多路访问型(None Broadcast MultiAccess,NBMA)、 点到点型(Point-to-Point)、 点到多点型(Point-to-MultiPoint)

7) 支持多点接入网络 * 使用更为复杂的网络拓扑图,图中的节点可以是路由器或者网络 * 每个多点接入网络可拥有一个指定网关。负责通告本网络的链路状态报文,接受和处理来自其他网络的链路状态报文 * 尽可能采用低层广播能力交付链路状态报文 8) 支持虚拟网络拓扑 例如:可为两个路由器培植一条虚拟路径,即使这两个路由器之间存在一个转发网络 9) 允许路由器间交换从其他(外部)网点得到的路由信息

OSPF拓扑实例 主干:R4、5、、10、11、12

OSPF拓扑的要求 (1) Area0:骨干;区域0 (2) 其它区域要和Area0直接连接 (3) 虚拟链路的作用 1)若骨干不连续,则不连续部分使用虚拟链路,虚拟链路属于骨干 2) 若其它区域Area0不是直接连接,也使用虚拟链路

OSPF中路由器类别 (1) 内部路由器:一个Area内 (2) 区域边界路由器 (3) 自治系统边界路由器 (4) 指定路由器DR、备份指定路由器BDR 在多路访问网络上可能存在多个路由器,为了避免路由器之间建立完全相邻关系而引起的大量开销,OSPF要求在区域中选举一个DR。每个路由器都与之建立完全相邻关系。 DR负责收集所有的链路状态信息,并发布给其他路由器。选举DR的同时也选举出一个BDR,在DR失效的时候,BDR担负起DR的职责

OSPF报文格式 头:24字节 类型Type(1字节) 鉴别类型 0 :无鉴别 1:口令鉴别 (同一区域内) 1 Hello ,用于测试可达性 数据库描述(拓扑) 3 链路状态请求 链路状态更新 链路状态确认 鉴别类型 0 :无鉴别 1:口令鉴别 (同一区域内)

Hello报文 失效定时器Dead Timer 若发送hello报文的路由器在该时间内未收到邻站的相应,则认为邻站失效;因此,邻站收到hello报文后,要尽快响应 Hello间隔:Hello报文周期 邻站IP地址: 发送者最近收到应答的邻站的IP地址 Hello报文的作用 1) OSPF周期性地发送Hello报文 2) 用于建立并测试邻站的可达 3) 利用Hello报文初始化相邻关系 优先级:用于选择后备指定路由器

OSPF 数据库描述报文 作用 OSPF通过交换该报文来初始化网络拓数据库 主动方-从方:可相互发送该报文 I bit 1--初始报文 M bit 1-- 后续报文 S bit 指定由谁置1 1 = master 0 = slave 链路类型 1 :路由器链路 2 :网络链路 3: 总结链路 4 :总结链路 (到边界路由器) 5 :外部链路 (到另一个AS) 作用 OSPF通过交换该报文来初始化网络拓数据库 主动方-从方:可相互发送该报文 主从关系是利用Hello报文的ID确认的

链路类型解释 类型1:相邻链路,链路信息只能在Area内广播 类型2:是由指定路由器DR产生的,在以太网这种广播性、多点接入的网络中,其包括该网络上连接的所有路由器的状态信息,该类信息只在该广播域内广播 类型3:是由Area边界路由器产生的,用于描述到某一区域外部的路由信息,目的地址在区域外,但在AS内.用于描述同一AS内不同Area间的链路状态. 通知本区域内的路由器通往区域外的路由信息;同时可以发送通往相同自治区不同区域的默认路由;把本区域的路由发送到骨干区域 类型4:是由ABR路由器产生的,通往ASBR路由器的链路状态 类型5:由AS边界路由器产生的,目的地址位于AS外,用于描述不同AS间的链路状态信息

链路标识符LINK ID 通告理由器 通告该链路的路由 链路序号: 发送路由器生成的序号;防丢失和失序 链路年龄: 路由器IP地址 链路建立后的时间,以秒为单位

链路状态请求报文

链路更新报文 (1)路由器周期广播链路更新报文 或作为链路状态请求报文的响应 (2)链路通告的格式如上图

6.3 外部网关协议BGP 6.3.1 EGP协议 6.3.2 BGP协议概述 6.3.3 BGP功能和报文类型 6.3.5 Internet选路仲裁系统

6.3.1 EGP (Exterior Gateway Protocol) R1 在 AS1 中收集有关的路由信息,并用BGP协议将其传送给路由器 R2; 同理,R2 也收集AS2 的路由信息,并报告给 R1 (1) EGP的作用:在两个自治系统间传送寻径信息的协议 (2) BGP-4:Border Gateway Protocol Version 4 1)当一对自治系统同一交换寻径信息时,双方需标示为 BGP 路由器。 2)这两个路由器可称为: 边界网关 (border gateway) 边界路由器 (border router) BGP对等路由器 (peer)

6.3.2 BGP的特点 (1) BGP 不是纯距离向量,也不是纯链路状态,而是路径向量 (2) BGP 的特点 1) 自治系统间 (Inter-AS) 通信:AS 到 AS 2) 协调多个 BGP路由器 (BGP Speakers) 若一自治系统有多个路由器,每个路由器都与自治系统的外部通信,其可以保证所有路由器传送一致的信息。 3) 传播可达信息(Reachability) AS 通告目的地可以直接或间接可达,并向其他自治系统学习这类信息。 4)下一跳信息 (next-hop) :为目的站提供下一跳信息 5) 策略支持: 管理员可选择路由通告策略。一般协议通告的是本地路由表的信息;而BGP可以区分两类路由信息,一是AS内可达的路由信息;一类是可通告给其他AS的路由信息

BGP特点 6) 可靠传输:使用TCP协议 路径信息:BGP通告从源到目的站的路 径上的一系列自治系统 8) 增量更新 9) 支持CIDR 8) 增量更新 9) 支持CIDR 10) 路由聚集: 11) 鉴 别:允许接收方对报文进行鉴别 (验证发送者的身份)

内部BGP---IBGP 当 BGP neighbors 属于同一个 AS 时不需要直接连接 AS 65500 AS 65000 IBGP Neighbors AS 65000 AS 65500 Neighbors B C 当 BGP neighbors 属于同一个 AS 时不需要直接连接

外部 BGP——EBGP 当BGP neighbors 属于不同的AS 必须直接连接 AS 65500 AS 65000 EBGP Neighbors IBGP Neighbors C B 当BGP neighbors 属于不同的AS 必须直接连接

路径向量 AS间使用距离向量是不现实的 很多例子说明最短路径并不一定是最优路由 例如:最短路径可能穿过的是一个昂贵的商业服务网、或者是一个不安全的学术机构网 (2) 若采用链路状态技术,就带来一个问题:是否有必要向整个Internet广播链路状态信息 链路状态技术一般要求:路由器数在200左右 1994年,AS号就有700多 目前,骨干AS号达7000个左右

路径向量的作用 通告的路径信息形式: 源AS、中间AS…、目的AS (2) 作用: 1)接收者可以检查路径是否存在回路 2) 接收方可以使用路由信息实现策略约束 接收方可以检查验证路由中的不可靠AS 3) 利用路径向量了解所有源站,从而还可以区分信息是一个自治系统内的,还是来自其他自治系统。

AS路径举例 一条路由穿过的一系列自治系统 如:在路由器B中,到192.168.1.0的path是 AS 65500、AS 64500 192.168.3.0 AS 65000 192.168.2.0 AS 64500 192.168.1.0 A B C 一条路由穿过的一系列自治系统 如:在路由器B中,到192.168.1.0的path是 AS 65500、AS 64500

下一跳举例 路由器A通过EBGP向路由器B通告网络172.16.0.0的 next hop是10.10.10.3 AS 64500 172.20.0.0 172.16.0.0 AS 65000 10.10.10.1 10.10.10.3 172.20.10.1 172.20.10.2 B A C 路由器A通过EBGP向路由器B通告网络172.16.0.0的 next hop是10.10.10.3 路由器B通过IBGP向路由器C通告网络172.16.0.0 同时将10.10.10.3 作为next-hop地址

下一跳 172.16.0.0 10.10.10.3 10.10.10.1 10.10.10.2 172.30.0.0 B C A AS 65000 AS 64500 172.20.0.0 EBGP 在多连通路径的网络中,路由器B将通过EBGP向路由器A通告网络172.30.0.0 next hop是10.10.10.2, 而不是10.10.10.1 这样就可以避免没有必要的 hop

CIDR和路由聚集 AS 64500 192.168.1.0/24 AS 65500 192.168.0.0/16 AS 65000 AS 65250 192.168.2.0/24 D B C A 192.168.1.0/24 =>192.168.0.0/16 192.168.2.0/24

6.3.3 BGP功能与报文类型 BGP 对等路由器执行三个基本功能 1)对等路由器探测与鉴别 2)传送肯定或否定的可达路由信息(重点) 在对等路由器间建立TCP连接并执行报文交换,确保双方都能进行通信。 2)传送肯定或否定的可达路由信息(重点) 发送方可通告一个或多个可达目的地 (并告知下一跳 地址) ,或通告一些先前可达而现在已不可达的目 的地。 3)持续的验证 确保对等路由器的功能正常。

四种报文类型 1)建立一个 TCP连接 宣告 AS编号与其他操作参数 2)握手协商 (Negotiation Handshake) OPEN 报文 宣告 AS编号与其他操作参数 KEEPALIVE报文 3)传送路由信息 UPDATE 报文 4)错误通告 NOTIFICATION 报文 R1 R2 建立连接 OPEN KEEKALIVE UPDATE ……

BGP报文首部 MARKER(标记、16字节 双方同意用该值作为报文的开始部分 作为同步和鉴别使用 (2)LENGTH (报文长度) 报文总长度,字节单位 最小值 = 19 最大值 = 4096 (3)TYPE (类型) 4类

Marker的作用 在初始报文中,标记都为1 若对等路由器同意使用验证机制,则标记可包含验证信息。 同步 (Synchronization) 1) 数据流传输 (例如 TCP)并未指定信息的边界。 2) 为确保发送端与接收端同步,BGP 在每个报文开头使用 双方公认的序列。 而接收端处理报文前需对该值进行确认

BGP Open报文 1) 两个 BGP对等路由器建立一TCP连接后,双方开始传送Open报文,打开BGP连接,通告其AS编号,并建立其操作参数 2) 接收端收到Open 报文后,若愿意建立BGP连接,则应答一 KeepAlive报文,作为对 OPEN 的肯定确认。 3) 若接收端拒绝建立BGP连接,则应答一 NOTIFICATION报文

各字段的含义 版本:4 自治系统编号:发送方的AS编号 保留时间:接收方等待发送方的最长时间. 1) 用于接收方的定时器设置。 1) 用于接收方的定时器设置。 2) 若接收方超时,则认为发送方不可用, 停止从发送方学习和转发路由 3) 缺省保留时间为3秒 (4) BGP标识:唯一能标识发送方的IP地址

BGP UPDATE报文 (1) 每个 UPDATE 报文分为两部分: 1) 第一部分:以前通告过,但现在要撤销的目的地 2) 第二部分:要通告的新的目的地 (2) Withdrawn Len (撤销长度):撤销目的地字段的长度 (字节) Withdrawn Destinations (撤销目的地)

Update报文的作用 BGP对等路由器建立 TCP连接、发送OPEN报文,使用 UPDATE报文 通告 (advertise)新的可达目的地 撤销(withdraw)先前的可达目的地 (3) 路由器只在路径改变时,才发送Update报文。

Update报文中目的地的表示 ---压缩的掩码地址表示法 (1)长度:掩码中1的个数(从坐到右连续) (2)地址:掩码覆盖的IP地址 长度 =0 :缺省路由 长度[01~08]:地址1个字节 长度[9~16]:地址2个字节 长度 [17~24]:地址3个字节 长度〉24 :地址4个字节

BGP路径属性 (1) 额外信息是包含在 UPDATE报文的路径属性字段中 (2) 路径信息的作用 (3) 路径信息的构成 1)到目的地的下一跳地址 2)到目的地的路径上的各个AS编号 3)路径信息由其他自治系统学习而得或由发送端的自治系统学习而得。 (2) 路径信息的作用 1)接收端可以检查是否存在回路 (routing loop)。 2)接收端可据此实现策略限制 (policy constrains)。 3)接收端知道报文的源站,可決定接受或拒绝所接收的报文。 (3) 路径信息的构成 (type, length, value) (类型,长度,值)

BGP的报文通告的约束 从接收方的角度来看BGP BGP不仅要提提供可达目的站信息;还要提供从接收方来看的正确信息。 忽略:自治系统内部的路由器可以到达给定的目的站;而禁止外界到达该目的站 最佳路由:从外界来看是最佳的。

举例: R2执行 BGP R2 必须通告到 Net 1、到 Net 4 的可可达性 到 经 ------- ---- Net 1 R1 到 经 ------- ---- Net 1 R1 Net 2 R2 Net 3 R3 Net 4 R3

BGP KeepAlive报文 定期交换KeepAlive报文 (2) 19字节大小 KeepAlive报文只有标准的BGP报头,其大小为19字节(最小 BGP报文长度) 。 (3) 高效 BGP 将连接性测试与路由通告功能分开,让 BGP 可以常常传送小的报文以保持通信连接,而可达性改变时才传送较大的更新报文。

KeepAlive报文 (4) KeepAlive定时器的设置 1)=Hold_Time/3 2)Hold_Time=0;不使用KeepAlive报文 3)大于1秒

BGP Notification 报文 (1) 用于控制或用在发生错误的时候 (2) 错误是不可避免的 一旦发现错误,BGP 发Notification报文,然后关闭TCP连接 (3) Err Code :6大类 Err Subcode:约20小类 Data :与错误相关的数据(路径)

6.3.4 BGP的局限 BGP 对距离值不传递也不做任何解释 (distance metrics),即使距离值是有用的 因此,BGP 不能传送或比较两个路由器间的代价 (cost),除非两个路由器在同一个自治系统内。 (2) 从技术角度看,EGP (BGP) 是可达性协议,而不是路由协议,因为它不知道经过的中间自治系统的代价。

BGP的主要限制 (1) 往返路径可能不对称 1) 虽然 BGP 可通告到一给定网络的多条路径,但不同时使用多条路径。自治系统间只使用一条路径 2) 即使源系统使用多条路径发送信息给目的站,外部的自治系统也只会使用一条返回路径。 3) 因此,往返路径可能是不对称的 (asymmetric) 这种现象难以监督和消除。 (2) 不支持任意自治系统间的路由负载分担 如两个AS间连接了多个路由器,BGP允许自治系统以网络为单位的负载分担;但不支持一般的负载分担(如根据实际负载的分担)

6.3.5 全局不一致性解决办法 --- Internet路由仲裁系统 需要建立一个新机制保证全局一致性,该机制称为路由仲裁系统 (2) 该机制的主要思想 1)全局性的路由可达信息库 2)更新该库的报文来自经过验证的路由器;不是所有路由器通告的路径都起作用 3)Internet还使用NAP机制 --- NAP有一台路由服务器RS,上面运行包含全局路由可达性的数据库,并运行BGP; --- 若干ISP使用靠近NAT的BGP路由器与NAT相连; --- 各边界路由器和NAT交换信息。

(3) 不适合用于最佳路由 (4) 无法保持路由的全局一致性 1)BGP 单独运作不适合作为最佳的路由方法 2)管理员必须手动配置每个网络由外部路由器通告(或外部路由器通告哪些网络) (4) 无法保持路由的全局一致性 1)为实现合理的路由,所有网络中的自治系统需使用一致方法通告可达性 2)BGP 单独运作不保证全局一致性

6.4 IGP与EGP的组合问题 在一个AS内,一个路由器可能既是IGP、是BGP 能否把IGP和EGP集合成一个整体? 答案:很难 原因:信任问题, 引起不信任的根源在于:不同AS具有不同的管理机构,而各管理机构由于利益问题,是很难相互信任的 在AS内部,各路由器相互信任 不同AS间,各路由器互不信任

对BGP的改进 传统的BGP互不信任、不是一个有效的路由协议 存在可以相互信任的AS 如一个大学的各个系;若每个系都对应一个AS,则这些AS是相互信任的 (3) 相互信任的AS可以交换距离,从而使得相互信任的不同AS之间可以进行有效的路由选择 例如: 相互信任的AS构成组 (1) 在一个AS内,距离值<128 (2) 在一个组内,距离值在128,191范围内 (3) 不同组间,距离值在192,254范围内

gated 能理解不同的路由协议 IGP、BGP 能接受RIP报文,并修改本地路由表 能像BGP那样,通告本AS的可达路由 (2) 遵从策略约束

6.5 组播和IGMP协议 6.5.1 多点交付 6.5.2 组播(Ethernet组播、IP组播) 6.5.3 IGMP 6.5.1 多点交付 6.5.2 组播(Ethernet组播、IP组播) 6.5.3 IGMP 6.5.4 常规路由与组播路由的差异 6.5.5 RBF和TRBF等基本组播协议 6.5.6 组播隧道技术 6.5.7 其他组播协议 6.5.8 可靠组播协议与ACK爆炸

6.5.1 多点交付 多点(传输)交付: 发送者把一个分组传递给多个接受者 多点交付的形式: 广播模式 基于单播模式的多点交付 组播模式

多点交付实例 ---(Ethernet广播实现) 网络 实例 完成方式 总线 Ethernet 一个报文分组 点到点 交换机 通过软件,拷贝分组到多个端口 广播地址 Ethrnet: 全1 定向IP广播: <netid, 全1> 有限IP广播: <all 1s> (本地网络) 不足: (1) 消耗网络带宽 (2) 消耗所有设备的计算资源 (3) 没有针对性

6.5.2 组播Multicasting 组播 要进行通信,必须选择一个特定的组播地址,只有在该组播地址中的组成员才能接收数据 (2) 特点 具有很强的针对性 单播、广播从概念上可以看成是特殊的组播

以太网组播 Ethernet地址(用点16进制表示)(MAC帧) 目的地址: 最高位:0;单播地址 最高位:1;组播地址; FF.FF.FF.FF.FF.FF:全1,广播地址 一半的Ethernet地址是组播地址 Mac帧中:源站的首位永远为0 (2) 网络接口卡接收3类帧(需要对卡进行配置) 单播帧 组播帧 广播帧

IP组播的特点 组播地址:D类地址 成员是动态的: 一个成员可以加入多个组;可以随时退出、加入组 IP组的数目很大 组可以跨越多个物理网络 尽最大努力交付机制:组报文可能丢失等 任意主机都可以向组发送数据

IP组播地址 两大类: (1) 永久性组播地址:用于组播协议 组播地址范围: (1) 224.0.0.0~239.255.255.255 (2) 临时组播地址 组播地址范围: (1) 224.0.0.0~239.255.255.255 (2) 224.0.0.0:保留 (3) 224.0.0.1~224.0.0.255:禁用,用于组播路由、组维护

永久性组播地址的作用 (1) 224.0.0.1 参与组播的所有主机、路由器 (2) 224.0.0.2 参与组播的所有路由器 (1) 224.0.0.1 参与组播的所有主机、路由器 (2) 224.0.0.2 参与组播的所有路由器 (3)用于组播控制,组播协议 (4) 限于同一本地网络

IP组播路由机制 不同于单播地址 组播地址只能是目的地址;不能用作源地址中 因此,凡是涉及源、路径的地方都不能有该类地址 不会生成与组播报文相关的ICMP差错报文 原因:组播报文出现差错的概率大 出现差错,也没法处理

IP组播与Ethernet组播 IP组播的低23bit=>Ethernet低23位比特 IP组播地址有28位 原因何在:MAC地址的前三个字节是固定的 (3) 多重映射问题 由IP软件处理

组播交付 在单个物理网络内 直接交付,主机把组播数据报封装在帧中,由底层协议支持的硬件组播完成 主机-〉组播路由器-〉目的组播路由器 (2) 不在同一物理网络内 主机-〉组播路由器-〉目的组播路由器 (3) 主机如何发送组播分组 同在同一物理网络中的组播一样,由硬件组播完成 在该网络中的组播路由器会接收该组播分组,并转发 主机无需配置相应的路由

组播作用域 组播地址:无作用域 组的作用域:加入组播地址的组成员的范围 组播报文的作用域:组播报文经过的网络集合 限制作用域的因素: 1)地址因素 图7.2中的最后两类地址 2) 报文寿命TTL 0:本机测试;1:本地网络

组播在主机上的实现 1) 目的:使主机能处理组播 2) 组播报文发送:比较简单 允许应用程序使用组播地址 3)组播接收 处理有两个含义:发送组播报文、接收组播报文 2) 组播报文发送:比较简单 允许应用程序使用组播地址 使硬件支持组播(不支持使用广播) 3)组播接收 允许应用程序加入、退出组 产生主机交付问题:多个应用程序加入一个组,底层 需要拷贝多个备份给高层 主机需要把组成员状态通知组播路由器

R1 R2 Lan1 H1 H2 H3 Lan2 H4 (1) 如果本地网络中没有应用程序加入组 则R1就不应该进行在该网络上进行组播通信 (2) R1需要把本地网络上的群组成员信息通告给其他路由器R2 (3) 主机加入群组,必须指定网络。例如: 假如H1加入了群组G=(H1,H2),则H1只须在Lan1上进行组播,若H1没有指定网络,则H1需要在Lan1和Lan2上组播,显然在Lan2上的组播是多余的 (4) 路由器也如此,需要知道网络

6.5.3 IGMP:Internet群组管理协议 主要作用: 完成本地网络主机加入群组(本地组播路由器)的管理;不涉及不同组播路由器间的路由信息交换 (2) 所有需要使用组播的主机必须使IGMP (3) IGMP是IP的一部分,IGMP报文是用IP传输的 (4) IGMP分为连个阶段 1)加入阶段:主机加入群组 2)维护阶段:轮训策略;适应群组的动态性

IGMP的实现 主机与本地组播路由器 (2) 组播路由选择 组播路由器:对某个本地网络,组播路由器不需要知道本地网络中有哪些属于某个群组;只需要知道某个群组是否有成员 主机:为每个群组建立一张群组、应用程序表 (2) 组播路由选择

IGMP报文格式 保留时间

加入群组 退出群组 对主机: 若应用程序退出群组;则相应计数器减1; 当为0时,则发退出群组报告报文 (1) 应用程序加入群组,加入前必须知道群组地址,IGMP不提供群组地址查询功能 (2) 若主机中的应用程序Pi是首次加入某群组G;其过程如下: 1)启动定时器(定时器时间在0~10之间随机选择) 2)定时器时间内,若收到该群组的查询报文;重置定时期 定时器时间内,若收到其他主机的包含该群组的响应报文,则自动属于该群组;不发群组成员报告报文,并取消定时器 若定时器到,则组播群组成员报告报文 (3) Pj不是首次加入群组G,则相应速其计数器加1 退出群组 若应用程序退出群组;则相应计数器减1; 当为0时,则发退出群组报告报文

组播路由器群组成员查询机制 轮询机制:轮询周期125s 查询报文:不是针对特定群组的;针对所有群组 需要时可以针对单个特定群组 (3) 主机使用成员报告报文响应,并用组播模式 响应时间:收到查询报文后,等待一个随机时间相应(该时间最大值为10s) 主机抑制那些不再需要发出的查询响应

6.5.4 组播路由与常规路由的差异 传统路由:拓扑或负载变化才会发生路有改变 传播组播路由信息,还没有形成单一的协议标准 6.5.4 组播路由与常规路由的差异 传播组播路由信息,还没有形成单一的协议标准 组播路由与传统路由有很大差异 1) 动态路由 传统路由:拓扑或负载变化才会发生路有改变 组播路由:应用程序加入、退出组也会引发路由变化 2) 组播路由需要检查多个目的地址 3) 组播可由网络上的任一主机发起,包括非组播成员主机

动态选路实例 在上图中 群组· O:A、B、C; 群组× :D、E、F 对群组· 1)网络2中无该群组成员,故不应向网络2转发组播报文 3)当F或G加入群组时,就需要向网络2转发组播报文

多目的地址检查 对群组× (1) E向群组发组播报文 R把E的报文转发到网络2 (2) F向群组发组播报文 R把F的报文转发到网络1 (3) A向群组发组播报文 R把A的报文转发到网络1、网络2

6.5.5 基本组播路由RBF RBF:反向路径转发; (1) 最短路径; (2) 避免环路 RPF (Reverse Path Forwarding) If (源地址在路由表中)(源地址作为目的地址) if (Fromport = Toport) (FromPort:组播报文来的端口、ToPort到源地址的端口) 向路由器的其他端口转发 else 丢弃

RBF的不足 向所有端口转发会浪费网络带宽 原因: 每个端口都连结一个网络 但是,组成员并不是在每个网络中都有 解决办法:截尾反向路径转发TRBF

TRBF的基本思想 常规路由表:实现RBF (2) 算法思想 需要两张路由表 组播可达网络群组表:避免无效转发 (2) 算法思想 TRPF (Truncated Reverse Path Forwarding) If (源地址在路由表中)(源地址作为目的地址) if (Fromport = Toport) (FromPort:组播报文来的端口、ToPort到源地址的端口) while(待转发端口P包含群组)向该端口P转发 else 丢弃

TRBF的后果 (1) 额外副本问题 原因:B到源A有两条各不相同的最短路径 A sends one datagram B receives two datagrams 原因:B到源A有两条各不相同的最短路径

(2)交付取决于源站 传输路径 交付细节

组播树 什么是组播树 从源站与所有组播成员之间所构成的路径树 (2) 组播树的简化 1)源站=〉源站网络 (2) 组播树的简化 1)源站=〉源站网络 同一群组、同一网络的源站其组播树是相同的 2)组播成员=〉组播路由器 (3) 组播路由表 (组播群组,源站;转发端口列表)或 (组播群组,源站;下一跳组播路由器列表) (4) 组播路由表的大小:正比于:网络数*组播群组数

组播树实例 X R2 R1 R3 R4 R5 R6 net 1 net 2 net 3 (leaf router) (root)

组播设计是:路由维护通信量和组播数据传输之间进行折衷 组播路由的本质 传播成员信息 原因:组播路由器必须了解群组成员信息,才能进行路由并且避免不必要的通信量 (2) 群组成员关系必须经过互联网络传播 组播群组与源(主机、路由器) 相隔很远;若不能通过互联网络传播群组关系,则源无法进行组播 成员关系变化快,通常组播路由表无法跟上这个变化 组播设计是:路由维护通信量和组播数据传输之间进行折衷

RPM RPM是TRPF的扩展 两阶段方法:广播和修剪 1)广播:RBF 2)修剪:路由器相互交换无群组成员的路径情况;路由器在转发时,如发现某条路径上已没有群组成员;就不在进行转发 (3) 信息交换方法: 自低向上(从加入或退出群组的主机、组播路由器开始) 若组播路由器是叶路由器且群组中无成员,则向其组播树中的父节点通告;以此类推,直至根节点 (4) 数据驱动 组播路由器在收到群组成员关系的数据报文后,才向其他路由器转发;其次,路由器在收到允续剪除的信息后,才停止转发。 (5) 接枝请求: 被修剪掉的组播路由器,若其又含有成员,可以使用该请求恢复原有路径

DVMPR (1) 矢量距离组播协议 (2) RIP协议的扩展 (3) 组播路由器间交换 (4) 定义了IGMP的一种扩展形式 (群组,源网络) 信息和代价(费用) 为每个(群组,源网络)建立组播转发树 (4) 定义了IGMP的一种扩展形式 IGMP用于成对的组播路由器间的通信; 扩展部分:允许携带包括费用的路由信息 (5) 数据驱动模式

mrouted 程序 是DVMPR在unix系统上的一个实现 不使用标准路由表,需要使用unix组播内核的特殊组播路由表 功能 1)路由传播:传播(群组,源网络)信息 2)组播隧道技术: 两个组播路由器间,若存在非组播路由器,则两个路由器无法交换组播路由信息; 利用隧道技术可以解决上述问题

6.5.6 组播隧道技术

MBONE 由含有组播路由器的网点系统所构成 组播路由器可以直接连接; 组播路由器可以通过不支持组播的网络连接(隧道技术)、虚拟网络 不同隧道之间的费用问题

6.5.7 其他组播协议 (1) DVMPR的缺陷: 规模受限 不能快速反映群组成员关系的变化 不适合Internet (2) 其他协议 6.5.7 其他组播协议 (1) DVMPR的缺陷: 规模受限 不能快速反映群组成员关系的变化 不适合Internet (2) 其他协议 1)核心基干树CBT 2)协议无关组播PIM 3) OSPF组播扩展

CBT(Core Base Tree) CBT与DVMPR的差别 (2) 核心组播路由器 CBT:需求驱动;DVMPR:数据驱动 需求驱动:收到肯定信息后才转发 数据驱动:收到了否定信息才停止转发 CBT:所有源站尽可能共享同一转发树 (2) 核心组播路由器 1)互联网被划分成区段 region 2)区段内,有一个路由器被指定为核心路由器 3)其他路由器 静态配置:知道核心路由器的地址 动态发现:动态发现核心路由器

主机加入群组G,本地组播路由器L如何通告 数据驱动模式: 本地组播路由器L向Ri通告,其中Ri向L传递过组播报文 需求驱动模式: 需求驱动无法使用上述办法。原因在于: 需求驱动使用肯定信息模式,由于L没有向其他组播路由器通告过(G,L),故其他路由器没有(G、L)的信息,故其他路由器不会向L转发有关G的组播报文 解决办法:核心组播路由器办法

CBT共享树的形成 核心路由器了解区段内的所有群组成员信息 区段内的所有组播路由器根据这些信息形成共享树 形成共享树的基本过程 1)主机加入群组G后,本地组播路由器L发CBT加入请求,使用常规的单播模式发给核心 到核心路径上的每个中间组播路由器检查该请求, 如果该路由器R已经在CBT树中,则记录和传递群组成员信息给它的上一层节点(父节点),同时返回ACK应答 3)在应答从R到L的路径上,各路由器改变其组播路由配置表,允许转发群组G的组播报文

(4) CBT的维护 1)每个路由器周期发送CBT 回应请求给其父节点

源站组播转发树SPT和共享树的区别 (1)源树,也称最短路径树(SPT) (2)共享树ST 以发送者为树根,到每一个接收者的最短路径构成一棵转发树。 可以用二元组(s, g)标示一棵源树。 从发送者到接收者的路径最优,但需要维护较多状态信息。 (2)共享树ST 以某个路由器为根(RP或Core)到所有接收者的树。 可以用(*,g)标示一棵共享树。 一棵树被多个发送者共享,维护较少的状态信息,但转发路径未必最优。树根的位置很重要。

协议无关组播PIM 包含两个协议PIM-DM、PIM-SM 协议无关的含义: 与单播协议共存,利用单播路由表的信息形成组播路由的转发树 (2) PIM-DM (Dense Mode) 1) 用于低时延网络 (LAN) 2) 确保交付,而不是降低开销 3) 使用了类似DVMPR的广播-修剪技术 (3) PIM-SM (Sparse Mode) 1) 用于高时延网络 (WAN) 2) 是CBT的扩展 3) 采用需求驱动策略 4) 使用了汇聚点路由器RP(与和新路由器相似)

PIM-SM与CBT的差异 在PIM-SM中,每个路由器维护着一个RP集合,每次只选一个 (2) 若当前RP不可达,则从候选RP中再选一个,构建组播转发树

共享树到最短路径树的切换 汇聚点:R7 共享树: 1)X-R7:X-R2-R5-R7 2)Y-R7:Y-R3-R4-R6-R7 若X-Y: 1) 共享树: X-R2-R5-R7-R6-R4-R3-Y 2)最佳路径:X-R1-R3-Y PIM-SM允许路由器选择最短路径 改变方法(基本思想): 若目的路由器发现源来的组播报文的路径超过了某个阈值,则目的路由器和源之间建立最短路径。 改变路径也会带来其他问题

MOSPF (1) 是OSPF的扩展 由于每个路由器都有一个拓扑结构的副本,因此,可利用该拓扑结构建立组播转发树 (2) 需求驱动模式 (2) 需求驱动模式 (3) 区域间的组播协议 1) 在一个域中,指定ABR作为MABR 作用:负责把本域中的群组成员关系传播给其他域 2) 具体实现:把信息传给主干,主干不在传给各区域,即非均衡传输 3) 指定一个ABR作为组播报文接收器,该接收器称为组播通配接收器

6.5.8 可靠组播与ACK爆炸 (1) 可靠组播的含义 1)正确:报文有序、无丢失、无重复、无差错 2)有效 (2) 实现策略:应答 (3) 可靠组播面临的 问题 1) 多个发送者:如何保证按序? 2) 重复不可避免,如何消除重复? 3) 如何保证时延的稳定?如音频、视频应用 4) ACK爆炸问题 发送者要处理所有接收者的应答ACK

ACK爆炸问题的解决办法 确认点:指定的路由器,负责处理源站确认 不由源站来进行处理,而是由确认点进行 否定应答NACK模式 多次发送N 要求:缓存组播报文、重传 否定应答NACK模式 多次发送N 发送N个副本 (4) 使用纠错码 利用纠错码恢复错误的组播报文