导图社区 计算机网络：自顶向下方法
- 244
- 12
- 2
- 举报
计算机网络：自顶向下方法
这是一篇关于网络层—计算机网络：自顶向下方法的思维导图，涉及到的内容有网络概述、数据平面、控制平面等。
编辑于2021-09-02 23:23:03- 网络层
- 相似推荐
- 大纲
网络层
网络层概述
转发和路由选择：数据平面和控制平面
核心功能
转发：将分组从路由器输入端口转移到合适的输出端口（数据平面唯一功能）
分组可能被阻挡
冗余分组可能被发向多条链路
硬件实现，时间尺度短
在路由器内实现
路由选择：通过转发表和算法啊确定分组从源到目的的路径（控制平面）
软件实现
在端到端的网络中实现
路由器的关键元素：转发表
路由器检查数据报的首部，检索转发表，确定数据报向哪个端口转发
<目的地址范围x，该目的地址对应的输出链路接口I>
主机到主机的通信服务
控制平面：传统的方法
转发表的初始信息配置方法
路由选择算法决定了插入该转发表的内容
假象情况：所有转发表人为配置
控制平面：SDN方法
远程控制器计算并分发转发表给各个路由器使用
网络服务模型
网络服务模型的服务：尽力而为服务
确保交付
具有时延上界的确保交付
有序分组交付
确保最小带宽：只要主机发送数据的速率在某特定值一下，则所有分组都会被交付
安全性
其他服务模型
恒定比特率CBR ATM网络服务
使网络连接看起来就像是在发送端和接受端之间有一条专用的、固定带宽的传输链路
ATM信元流以如下方式承载跨越网络：一个信元的端到端时延、信元端到端时延中的可变性（即时延抖动）及丢失或推迟交付的心愿比率都保持在特定值以下。但第一次建立CBR连接时，发送主机和ATM网络认可这些值
可用比特率ABR ATM网络服务
比尽力而为服务稍好
可以保证最小传输速率MCR
可以为发送方提供反馈信息，以便调整速率
无连接服务
不事先为系列分组的传输确定路径
每个分组独立确定传输路径
不同分组可能传输路径不同
数据报网络
因为无连接，每个分组需要携带目的地址
不需要建立虚电路，故而无需维护其状态信息
路由器根据分组的目的地址进行转发
基于路由器协议或者算法建立转发表
检索转发表：采用最长前缀优先匹配，因为ip地址众多，所以是范围检索
因为转发表的更新，所以不同分组的路径可能不一样，即独立选路
Internet网络：尽力而为服务
连接服务
虚电路（Virtual-Circuits）网络
具体实现和组成
①源→目的的路径
②VCID，沿路每段链路一个编号，即，路径上链路的编号，相同VCID的沿同一条虚电路
不保持VCID相同的原因
逐路代替减少分组首部VC字段的长度
大大简化了虚电路的建立，同一条链路上成为不同虚电路的路径时，可以用不同的VCID
③沿路每个网络层设备（路由器），利用转发表记录经过的每条虚电路，并改写下一段路程的VCID
虚电路信令协议
通信过程（逻辑连接）：虚电路建立→数据传输→虚电路拆除
一般过程
首先为系列分组的传输确定从源到目的经过的路径（建立连接）
网络层决定其路径，为链路分配VCID，还可预留资源
沿该路径传输系列分组
系列分组传输路径相同
传输结束后拆除连接
特点
每个分组携带虚电路标识VCID，而不是目的主机地址
VC路径上的每个路由器都要维护其连接的状态信息，连接拆除后，路由器更新转发表，并表明该虚电路已不存在
可以预分配网络资源
分组交换，每个分组利用全部带宽
ATM网络采用
网络层和运输层的面向连接和无连接服务的区别
网络层是主机到主机，运输层是应用进程到应用进程
网络层只能存在面向连接和非链接之中的一个
运输层面向连接是实现在端系统上的，二网络层的面向连接服务除在端系统外，还由路由器实现
路由器对运输层的连接建立完全不知情，而对于虚电路网络层，路径上的路由器都参与建立连接，且每台路由器都完全知道经过他的所有虚电路
区别
Internet
Internet弹性服务，没有严格时间需求
链路类型众多，特点性能各异，统一服务困难
智能端系统：可以自适应、性能控制、差错回复
简化网络，复杂边缘
ATM
电话网络演化而来
核心业务：实时对话
严格时间、可靠性要求
需要有保障的服务
非智能
简化边缘，复杂网络
数据平面（转发）
路由器工作原理
路由器体系结构组成
输入端口
功能
在路由器中执行人物理链路的物理层功能
与位于链路远端的数据链路层交互执行数据链路层的功能
执行查找功能：查询转发表决定输出端口
此端口指的是物理输入和输出接口
交换结构（核心部位）
功能
将输入端口连接到输出端口
网络路由器中的网络
输出端口
功能
存储从交换结构接收的数据，并执行必要的数据链路层和物理层功能在输出链路上传输该数据
链路双向，则输入端口和输出端口出现在同一线路卡上
硬件构成
路由选择处理器
功能
执行控制平面功能
传统路由器：执行路由选择协议，维护路由选择表与连接，并为该路由计算转发表
SDN路由器中：负责与远程控制器通信，接收它的转发表项，并在该路由器输入端口安装该表项
执行网络管理功能
路由器处理的信息
基于目的地转发：R查找最终目的地，决定通向它的输出端口
通用转发：基于其他许多因素决定输出端口，如源的信息，链路的速率等
输入端口处理和基于目的地转发
线路端接→数据链路处理（协议、拆封）→查找，转发，排队→交换结构
三态内容可寻址存储器TCAM进行查找
其他动作（出查找外）
出现物理层和链路层处理
检查分组的版本号、检验、寿命字段
必须更新用于网络管理器的计时器
处理规模的方法：使用IP的前缀匹配，并用最长前缀匹配机制
交换（=转发）
经内存交换
原理：处理器内存将数据从输入端口复制，再在转发表中寻找合适的输出端口，再把数据复制过去
经过共享总线链路一次只能执行一个读/写，故而吞吐量＜读写的速率/2
在路由选择处理器的直接控制下完成
经总线交换
原理：一根共享总线直接将分组送至输出端口
给分组一个路由器内部标签：首部，总线将此分组转发至所有端口，但只有与首部匹配的端口才将其保存，在撤去首部后再发出
一次只能传输一个分组
不需要路由选择处理器的干预
经互联网网络交换
原理：N个输入端口和N个输出端口，组成纵横式线路，类似于围棋棋盘，再转发时由交换结构控制器决定每个节点的开启与关闭，关闭即相连，从而确定线路
非阻塞式的：同时最多可以交换N个分组，但同一条线路最多交换一个
输出端口处理
原理：与输出端口相反，交换结构→排队→数据链路处理（协议，封装）→线路端接
何处出现排队
取决于流量负载、交换结构的相对速率和线路速率
输入排队
原因：交换结构不能快得式所有分组无时延地传输
例子
纵横式结构中，两个不同输入端口中的分组欲进入同一个输出端，若发送其中一个，则另外一个必须等待，且紧随其后的欲进入其他输出的分组也必须等待
上种情况即为：线路前部HOL阻塞
输出排队
原因：假设交换结构传输速率为输出端口传输速率的N倍，且分组前往同一个输出端口，则会造成N个分组排队，最终没有缓存，则需要主动队列管理AQM（分组丢弃与标记策略等都包含于其中），随机早期检测RED即为其中一种
曾经：缓存数量B=RRT*c（链路速率）
现在：B=RRT*c/√n，当有n个TCP流通过链路时
分组调度
功能：确定选择排队中的哪个分组用来传输
方法
先进先出FIFO（也称先来先服务FCFS）
优先权排队
分组被分类到队列的优先权类中，同类按FIFO输出，不同类等优先权高的传输完再传输
非抢占式优先权排队：一旦分组开始传输，就不能打断
循环和加权公平排队
先分配优先权，然后先传输优先权最高的类的首个分组，再发次高的首个分组，发完优先权最低的首个分组后，再发送最高的第二个分组，一次类推
网际协议：IPv4、寻址、IPv6及其他
IPv4数据报格式
版本号：路由器可以知道如何解释剩余数据报部分
首部长度：以32bit为一个计数单位，无选项时为5
TOS：区别不同类型的数据报，如明确拥塞通告ECN
总长度：数据报的总长度，字节为单位
标识：16位，表示哪个数据报分组，再加总长度可以确定分组，在源主机中生成，或者通过计数器，每产生一个分组就+1，分片后，可以识别同一个分组的分片
标志位：3位
保留
DF=1，禁止分片；0，允许分片
MF=1，非最后一片；0，最后一片
片偏移量：13位
一个IP分组分片封装原IP分组有效载荷 的相对偏移量
以8字节为单位，即数据长度需被8整除
生存时间TTL：确保数据报不会在网络中无线循环，每过一台路由器时都会-1，=0时，该数据报被丢弃
协议：仅当数据报到达终点才用，类似于端口号，告诉我们数据部分交给运输层的哪种协议，如，6为TCP，17为UDP
首部检验和：检测首部 比特错误，即以两字节为一组，全部相加，进位加到后面，最后取反码
IPv4数据报分片：与第二行的标志位有关
最大传输单元MTU，链路层数据帧可封装的数据上限，不同链路的链路层协议可能不一样，则MTU可能不一样
MTU不一样时需要分片，在端网络层重组
分片过程：原IP长度L，MTU为M
分片最大可封装数据d=
需要总片数
每片片偏移字段取值
每片总长度
每片的MF标志位：只有i=n时，才为0
IPv4编址
概述
IP是告诉IP分组从哪来，到哪去
接口
主机/路由器与物理链路的连接
一个IP地址与一个接口相关联
实现网络层功能
路由器通常由多个接口
主机一般只有一个或者两个
IP地址（静态配置）
用32bit编号（点分十进制）标识主机/路由器的接口，二者相互关联
分配地址
有类编址IP子网
IP地址具有相同网络号的设备接口
不跨越路由器，可以彼此物理联通的接口
网络号+主机号
A类：网络号8位，第一位为0，0.0.0.0-127.255.255.255
B类：网络号16位，前两位为10，128.0.0.0-191.255.255.255
C类：网络号24位，前三位110，192.0.0.0-223.255.255.255
D类：前四位1110，224.0.0.0-239.255.255.255，用作主机组播
E类：前四位1111，240.0.0.0-255.255.255.255，作为保留
特殊IP地址：掐头去尾
缺省路由：在路由表中未能查到的地址，则取目的IP为0.0.0.0，子网掩码为0.0.0.0
服务器是一种特殊的网络，经路由器查找时应该取其子网掩码为255.255.255.255
子网掩码
子网的编码形式：a.b.c.d/x，/x有时称为子网掩码
被接口隔离的都叫子网，包括两路由器接口直接相连的链路
子网地址划分为：网络号，子网号SubID，主机号
前二者取1，后者全取0
目的IP地址与子网掩码按位与 运算，提取子网地址
子网地址+子网掩码→准确确定子网大小
默认网关：即子网连接的路由器的端口号
因特网地址分配策略：无类别域间路由选择CIDR
用于处理相同子网造成的问题
形式：a.b.c.d/x
x位最高比特为其网络地址，为网络前缀prefix
路由聚合（地址聚合、路由摘要）：使用单个网络前缀通告多个网络的能力
作用
提高IPv4地址空间分配效率
提高路由效率，通过路由聚合将多个子网聚合为一个较大的子网
获取一块地址
由因特网名字和编号分配机构ICANN管理分配
获取主机地址：动态主机配置协议DHCP（即插即用协议，零配置协议）
功能
C从DHCP服务器（应用层，使用UDP）获取
IP地址
子网掩码
默认网关地址
DNS服务器名称与IP地址
即插即用
允许地址重用
支持再用地址续租
支持移动用户加入网络
C/S协议
配置步骤（皆以广播形式通信）
1、DHCP S发现：利用DHCP发现报文，基于UDP，源端口68，目的端口67，此IP数据报的源IP为0.0.0.0，目的IP为255.255.255.255
2、DHCP服务器提供：收到发现报文时，用DHCP提供报文，响应客户端，广播
发现报文的组成
发现报文的事务ID
向客户推荐的IP地址
网络掩码
IP地址租用期
广播发送的原因：子网中可能由几台DHCP服务器，该客户可以选择优越位置
3、DHCP请求：C选择一个S，并发送DHCP请求报文，回显配置的参数
4、DHCP ACK：S用DHCP ACK报文响应，正式所要求的参数
注：全是广播形式发送报文
ICMP：因特网控制报文协议
功能：被主机和路由器用来彼此沟通网络层的信息
差错报告
网络探询
ICMP的体系结构应该位于IP之上，因为其报文是作为IP有效承载的，当IP数据报中的协议字段指向的是ICMP，就分解出该数据报的有效载荷给ICMP
两类ICMP报文
差错报告报文
①目的不可达：报文在传输到目的主机或者之前，不能成功进入网络、主机、端口、协议，则被丢弃
②源抑制：拥塞时，即路由器缓存已满，发送源抑制报文给源主机，让他降低发送速度
③超时/超期：TTL超时，当TTL=0时，被丢弃，并向源主机发送此报文
④参数问题：发现报文头部参数出现问题，可丢弃，发送此报文
⑤重定向：路由器认为不能转发到目的地址，则丢弃，并发送此报文让源主机换一个路由器转发
其中的第一个IP数据报首部以及有效载荷的前8个字节来自于引起ICMP报文产生的IP数据报，带上它是为便于发送方能确定引发该差错的数据报
网络探询报文
回声请求和回声应答：探测网络是否可达，例ping
时间戳请求与应答报文
例外情况
对ICMP差错报告报文不再发送ICMP差错报告报文
除第一个IP数据报外均不再发送ICMP差错报告报文
对多播IP均不发送ICMP差错报告报文
对特殊地址，如0.0.0.0的数据报均不发送ICMP差错报告报文
应用举例：traceroute原理
网络地址转换NAT
动机
只需/只能从ISP申请一个IP地址→造成IPv4资源耗尽
本地网络设备IP地址的变更无需告知外界
变更ISP时，无需修改内部网络设备IP地址
内部网络对外面不可见，不可直接寻址
一般用于专用网络PN，或着具有专用地址的地域（指其地址仅对该网络中的设备有意义的网络）
承载NAT的路由器由ISP的DHCP提供IP，其下的子网的地址都由路由器运行的DHCP服务器分配
实现
1、替换：利用（NAT转换表 IP地址，新端口号）替换每个外出IP数据报的（源IP地址，源端口号）
2、记录：将二者的替换信息存储到NAT转换表中
3、替换：根据NAT转换表，替换进入内网IP数据报的端点地址
16bit端口号字段，可同时支持60000多并行连接
争议
路由器应该只处理第三层功能
违背端到端通信原则，因为它修改了应用层的socket，即运输层报文段中的源端口字段
地址短缺问题应该由IPv6解决
NAT穿透：客户想访问内部的服务器
方案一：静态配置NAT，将特定端口的连接请求转发给服务器，即替换的端点地址不变
方案二：利用UPnP（通用即插即用）互联网网关设备协议自动配置
措施
学习到NAT公共IP地址
在NAT转换表中，增删端口映射
UPnP是一种允许主机发现并配置邻近NAT的协议
使用UPnP，在主机上运行的应用程序能为某些请求的公共端口号请求一个NAT映射，该映射位于（专用IP，专用端口）和（公用IP，公共端口）之间。若NAT接收请求并产生映射，则来自外部的结点就可以发起到（公用IP，公共端口）的TCP连接
UPnP让应用程序知道（公用IP，公共端口），因此该应用程序能向外部世界通告他
方案三：中继：外客户端↔中继服务器↔NAT内部客户
IPv6
动机
32位的IPv4地址空间已经分配殆尽了
改进首部格式，强化协议
快速处理/转发数据报
支持QoS
IPv6数据报格式
优点
校验和移除，以减少每跳处理时间
允许选项，但是在数据字段
不再使用掩码
扩大了地址容量
简化高效的40字节首部
流标签
重点：快速处理IP分组
新数据报格式
版本
（图中并非优先级，而是）流量类型：与TOS类似
流标签：给特殊流的分组加上标签，这些特殊流时发送方要求进行特殊处理的流，如一种非默认服务质量或者需要实时服务的流，可以根据此标签给出优先权
有效载荷长度：无符号整数，给出40字节首部后的字节数
下一个首部：标识交给运输层的哪个协议，值与IPv4的协议字段值相同
跳限制：即TTL生存时间的用法
首部定长40字节
移除内容
分片/重组：IPv6不允许分片与重组，若数据报太大，直接丢弃，并返回“分组太大”的ICMP报文，让源主机减小长度。此举大大加快了网络的IP转发速度
首部检验和：因为运输层和数据链路层执行检验操作，设计者大抵觉得它多余，故而去掉
选项：被放进载荷中了，即由“下一个分组”中指向的位置
新IP格式
地址改用128个比特每16个比特用"："隔开
压缩形式：全0的分组用：：表示，但只能有一个
IPv4嵌入形式0：0：0：0：0：FFFF：13.1.35.1或：：FFFF：13.1.35.1
用在URL时需要加"[]"
新版ICMP
附加报文类型
多播组管理功能
基本地址类型
单播：一对一
多播：一对多（一组网络）
任意播：一对一组之一（最近一个）
从IPv4到IPv6的迁移
进入IPv4网络前的IPv6中封装IPv4的报文首部，在离开后的IPv6中去除
建隧道：将一段相同协议的集合称为隧道
IPv6安全性：IPSec
运输模式（面向连接）
IPSec加密报文段，加上安全性字段，并且在一个普通的IP中封装
服务
密码技术约定
IP数据报有效载荷的加密
数据完整性
初始鉴别
通用转发和SDN
概述
通用转发：每台分组交换机包含一张匹配加动作表，此表由远程控制器计算、安装和更新
OpenFlow标准
是匹配加动作转发抽象、控制器以及更一般的SDN革命等概念的先驱
匹配加动作转发表在OpenFlow中称为流表
首部字段值的集合：入分组与其匹配，不同则丢弃
计数器集合（分组与流表项匹配时更新）：包括已匹配的分组数量，以及前次更新时间
匹配时，所采取的动作集合：转发到特定输出端、丢弃、复制并发送、重写所选
TCP之上，端口6653
匹配
允许来自链路层，网络层，运输层的协议首部选择的字段进行匹配
有通配符
并非所有字段可以匹配
动作
转发
丢弃
修改字段：分组首部字段
匹配加动作操作中的OpenFlow例子
一、简单转发
二、负载均衡
三、充当防火墙
控制平面（路由）
概述
转发表（基于目的地转发）和流表（通用转发）的计算、维护和安装
每路由器控制
逻辑集中式控制：如前述的远程控制器
该控制器经一种定义良好的协议与每台路由器中的控制代理CA进行交互，以配置和管理该路由器的转发表
CA
一般具有最少的功能，用于与控制器通信，按控制器命令行事
不能直接相互交互，也不能主动参与参与计算转发表
在每个路由器上
路由选择算法
概述
目的：寻找最低开销路径（最短路径）
若有相同开销的不同路径，则取源与目的地之间最少链路数量的路径
图G（N，E）：N个节点和E条边的集合，边无方向，（x，y）就表示一条边
分类
静动态
静态路由选择算法
手工配置
路由更新慢
优先级高
需要人工修复
动态路由选择算法
路由更新快
定时更新
及时响应链路费用或网络拓扑变化
全局与分散
集中式路由选择算法
所有路由器掌握完整网络拓扑和链路费用信息
链路状态LS路由算法
分散式路由选择算法
路由器只掌握物理相连的邻居以及链路费用
邻居间信息交换、运算的迭代过程
距离向量DV路由算法
敏感与迟钝
负载敏感算法
链路开销动态变化以反映底层网络拥塞状态
若拥塞链路与高开销相联系，则此算法趋于避开此链路
负载迟钝算法（RIP、OSPF、BGP）
链路开销不明确反应其链路拥塞情况
链路状态（LS）路由选择算法
Dijkstra算法p
所有节点（路由器）掌握网络拓扑和链路费用：每个路由器向网络中其他所有路由器进行链路状态广播（分组包含其链路的标识与开销）
计算从一个结点到达所有其他结点的最短路径，获得该结点的转发表
符号
C（x，y）：x→y的费用，若不直接相连则为∞
D（v）：从源→v的费用
p（v）：沿源到v的当前路径，v的前序结点
N‵：节点子集，如果从源→v的最低开销路径已知，则v在N'中
迭代
例子
p
p
最差情况下算法复杂性O（n²）
存在震荡的可能性：链路费用是该链路承载的通信量，来往非对称，即，未传输方向的链路费用为0，着就造成更新后数据会往此方向，即与原方向相反的方向流动，此时，原方向的链路费用变为0，又造成更新后回流，如此往复，是为震荡
解决方案
强制链路开销不依赖所承载的流量（不太现实）
确保并非所有的路由器运行LS算法
距离向量（DV）路由选择算法
特点
分布式：每个节点都从与其直接相连的邻居收取信息，并发送计算结果
邻居在其DV更新后发生改变再通告他们
迭代：上述过程一直持续到邻居间无更多消息交换
引发每次局部迭代的因素
局部链路费用改变
来自邻居的DV更新
异步：它不要求所有的节点相互之间步伐一致地操作
可以在任意时刻出现节点计算和更新的产生/接收
使用Bellman——Frod方程（动态规划）
，其中dx（y）=从x到y最短路径的费用（距离），v是x的邻居
结点x
Dx（y）：从结点x到结点y的最小费用估计，小写d为实际费用
x维护距离向量（DV）：
已知到达每个邻居的的费用c（x，y）
维护其所有邻居的距离向量：
核心思想
节点真正需要知道的是下一跳路由器
每个节点不定时地将其自身的DV估计发送给其邻居
当x接收到邻居的新的DV估计时，即依据B-F更新其自身的距离向量估计
Dx（y）将最终收敛于实际的最小的费用dx（y）
算法
一、初始化：对每个N中的y，使Dx（y）=c（x，y），对选的每个邻居w，有Dx={Dx（y）：y∈N}
二、循环
1、等待：直到收到新DV，或者检测到链路开销改变
2、对每个y∈N，，其中v即为所需的下一跳有：
三、如果Dx（y）因为某个y改变，则发送DV给所有邻居：
距离向量算法：链路开销改变与链路故障
费用变化时动作
t0：y检测到链路费用发生变化，更新DV，通告其邻居。未变化的则不发送信息，等待接收，且计算时，依旧用原来的数据
路由环路黑洞：即由于原来下，链路开销未改变的节点会依旧保持，故而计算时可能比现实的小，从而数据在两个节点来回发送，直到转发表改变
可以设置跳步数来阻止无限循环
t1：z收到y的DV更新，更新其距离向量表，计算到达x的最新最小费用，更新其DV，并发送给邻居
t2：y收到z的DV更新，更新其距离向量表，重新计算y的DV，未发生改变，不再向z发送DV
好消息传播快
坏消息传播慢，因为他是一步步根据原来的最小值 增加改变的
无穷计数问题：由于开销突然变得很大，则要迭代很多次才能平稳
距离向量算法：增加毒性逆转
思想：如果结点z到达目的x的最小费用路径是通过邻居y的，则通告y到达该目的x的距离为无穷大
LS与DV路由选择算法的比较
交谈方式
DV：每个节点仅和与它直接相连的邻居交谈，它为其他邻居提供了从他自己到网络中所有其他节点（它知道的）的最低开销估计
LS：需要全局信息，每个节点通过广播与其他所有节点通信，但仅告诉他们与它直接相连链路的开销
报文复杂性
LS：需要每个节点知道网络中每条链路的开销，要求发送O（|N||E|）个报文
DV：在每次迭代中，相邻节点交换报文。链路开销改变时，DV仅当新链路开销导致与该链路相连节点的最低开销路径发生变化时，才传播已改变的链路开销
收敛速度
LS：O（|N|^2）
DV：较慢，且可能遇到路由选择环路和无限计数问题
健壮性：一台路由器发生故障，对整个系统的影响
LS：路由器向其连接 的链路广播不正确的开销，一个节点也可损坏或者丢弃此广播报文，一个节点仅计算自己的转发表，其他节点类似。故而路由计算在一定程度上是分离的，有一定健壮性
DV：一个节点可以向任意或者所有目的节点 通告不正确的最低开销路径，他的一个不正确的节点计算会扩散到整个网络
因特网路由选择协议
基础：层次路由
原因
规模：因为网络规模过大，路由表无法计算与存储，故而需要分层
管理自治：每个网络自主控制其内的网络
解决办法
聚合路由器为一个区域：自治系统AS
相同AS内的路由器运行相同的路由协议算法：自治系统内部路由选择协议IGP
不同AS内运行不同的AS内部协议
网关路由器：位于AS边缘，通过链路与其他AS网关路由器相连
AS知晓哪些网络可以通过哪些AS到达，并将此等信息传播给AS内部路由器
因特网AS内部的路由选择
路由信息协议RIP
使用距离向量路由算法
RIP响应报文（RIP通告）
哟条路经的最大费用不大于15，即跳步数最大15，即网络直径不大于15跳
每隔30s，邻居间交换一次DV，成为通告
通过UDP协议，520端口传输通告，相当于应用层协议
即它通过UDP来实现网络层的路由选择功能
每次通告包含：该AS内最多25个目的子网的列表，以及发送方到其中每个子网的距离
每个路由器维护一张称为路由选择表 的RIP表，包括
该路由器的DV
该路由器的转发表
得到新通告，立即与旧路由选择表合并
若是180s未收到来自邻居的通告→邻居/链路失效
经过该邻居的路由不可用，重新计算路由，修改路由选择表
向邻居发送新的通告
邻居再一次向外发送通告（如果转发表改变）
链路失效信息能否快速传播到全网：可能发生无穷计数问题
毒性逆转技术用于防止乒乓（往复来回）环路
路由表由进程管理实现，报文通过UDP数据报发送
开放最短路径优先OSPF
性质
开放：公众可用
核心
使用洪范链路状态信息的链路状态协议
采用LS路由算法
每个路由器构造完整的网络（AS）拓扑图
利用Dijkstra算法计算路由
设置OSPF链路权值
管理员配置链路费用的计算方法，如将所有链路的开销设为1，等，但不强制使用此策略
LS分组扩散（通告）
OSPF通告中每个入口对应一个邻居
OSPF通告在整个AS范围内泛洪，即广播路由选择信息
OSPF报文封装在IP数据报中，对其上层协议的值为89
路由器周期性地（至少30分钟一次）广播链路状态，提高健壮性
优点
安全：能鉴别OSPF路由器间的信息交换（如链路状态更新），利用MD5加密进行鉴别OSPF报文是否被伪造，故而所有OSPF报文可以被认证
允许多条相同费用的路径（RIP只能选一条，但是多了选择）
对单播和多播路由选择的综合支持
对于每条链路，可以针对不同ToS设置多个不同的费用度量
集成单播路由和多播路由：二者利用相同的网络拓扑数据
支持在单个路由选择域内的层次结构：按层次构造AS
OSPF支持对大规模AS分层
两级分层：局部区和主干区
AS边界路由器：连接其他AS
主干路由器：在主干区内运行OSPF算法，为其他区域之间的流量提供路由算法
区域边界路由器（在主干区域内）：汇总到达所在区网络的距离，通告给其他区边界路由器
每个区域可运行自己的OSPF链路状态路由选择算法
链路状态通告只限于区内
每个路由器掌握所在区的详细拓扑
只知道去往其他区网络的最短路径
ISP（AS）之间的路由选择：边界网关协议BGP
概述：事实上的标准域间路由协议，将Internet粘合的关键
eBGP（外部BGP会话）：从邻居AS获取子网可达性信息（即AS之间）
iBGP（内部BGP）：向所有AS内部路由器传播子网可达性信息（AS内部）
BGP的作用：为每个AS提供了一种手段
从邻居AS获得前缀的可达性信息，
向本AS内的所有路由器传播这些可达性信息
基于可达性信息与策略，确定到其他网络的最好路径
分组路由到CIDR化的IP前缀，而不是特定的地址，其路由表为（x，l），x为前缀，l是该路由器的接口之一
通告BGP路由信息
BGP会话：两个BGP对等peer路由器交换BGP报文
通告去往不同目的的前缀的路径（路径向量协议）例：a.b.c.d/x
报文交换基于半永久的TCP连接，端口为179
在两个不同AS之间有一条半永久的BGP TCP连接
BGP中，每个AS有一个全局唯一的自治系统号ASN（桩AS无ASN，用于承载源/目的地址为流量）
BGP报文含义
OPEN：与peer建立TCP连接，并认证发送方
UPDATE：通告新路径，或撤销原路径
KEEPALIVE：在无UPDATE时，保持连接，也用于对OPEN请求的确认
NOTIFICATION：报告先前报文的差错，也用于关闭连接
会话时，路由器会通告一个前缀，前缀包含一些BGP属性
带有属性的前缀叫做一条路由
承诺可以将数据报转发给该子网
在通告中会聚合网络前缀
当路由器获得的前缀可达时，在其转发表中增加关于该前缀的入口
确定最好的路由
带有属性的前缀=路由
AS-PATH
当一个前缀传送到一个AS时，该AS将他的ASN增加到此属性中
包含前缀通告所经过的AS序列：头→尾，其中头时源AS的下一个AS
可用来检测和防止循环通告，如一台路由器在此路径列表中看见了它所在的AS，将拒绝该通告
NEXT-HOP
是AS-PATH起始的的路由器接口的IP地址，即上述头的一个接口
偏好测度的属性
前缀如何插入位于其实AS的BGP的属性
BGP路由写法：NEXT-HOP：AS-PATH；x
一台网关路由器接收到路由通告时，它使用输入策略决定是否接收或过滤该路由，是否设置某种属性
热土豆路由选择：选择最小费用路径的费用最小的网关
1、从AS间协议知道经过多个网关可达子网
2、使用来自AS内部协议的路由选择信息，决定到每个网关的最低费用路径的费用
3、热土豆路由选择，选择具有最小的最低费用的网关
4、从转发表确定通向最低费用网关的接口I，将（x，I）项添加到转发表中
直接发送给最近的其他AS网关，只考虑减小自己AS的开销，而忽略了其他AS的开销
路由器选择算法：对相同前缀存在多条路由，则顺序调用右侧方法
①路由器被指派一个本地偏好值作为属性，最高者被选择
②余下路由中，具有最短AS-PATH的路由被选中
若只剩此规则，则运行DV路由选择算法决定，距离测度为AS跳的数目
③余下路由中，选择最靠近（指的是费用最低的）NEXT-HOP路由器的路由
④余下路由通过BGP标识符选择路由
路由器选择策略
网关路由器收到路由通告后，利用其输入策略决策接受/拒绝该路由，是否设置某种属性
基于策略路由
分类
提供商网络
客户网络
桩网络：只与一个其他AS相连，通告没有通向其他AS目的的路径
双宿网络：连接两个其他AS
任何穿越ISP主干网的流量必须时其中源或者目的或者两者位于该ISP的某个客户网络中
p
准则
本地偏好值属性：策略决策
最短AS-PATH
最近NEXT-HOP路由器：热土豆路由器
附加准则
拼装在一起：在因特网中呈现
路由表的表项有前缀+对应输出端口组成
策略
inter-AS：主导作用，期望能管理控制流量如何被路由，谁路由经过其网络
intra-AS：单一管理，无需策略决策
规模
层次路由节省路由表大小，减少路由更新流量
过大可以通过OSPF的分层功能减小
适应大规模互联网
性能
inter-AS：策略主导，不怎么关注性能
intra-AS：侧重性能
广播和多播路由选择
广播路由选择算法
N次单播
发送节点向每个目的地分别分发分组的副本
①源节点产生N份副本
②N次单播选择向N个目的地传输N个副本
隐含假设：广播的接收方及其地址均为发送方所知
缺点
效率低
解决办法：仅第一跳发送单个副本，之后的都复制节点所需副本
不好得到上述隐含假设中的信息
解决：需要其他协议
广播生成和更新单播路由的情况下，基于单播路由选择基础设施来取得广播不明智
洪泛技术
无控制洪泛
原理：每个接收广播分组的结点都复制此分组发送给其邻居
缺点
如果链路图有圈导致两个广播分组无休止地循环
广播风暴：每个结点复制多余他们自身的分组，最终生成大量分组，使得网络无用
受控洪泛
序号控制洪泛
原理：每个分组加上源结点地址和一个广播序号，每个结点维护收到的、复制的和转发的分组的源结点地址和广播序号列表。当一个结点收到此分组时，先检查列表中是否有此分组，若有，则丢弃；若无，则复制转发
Cnutella协议用此方法，但在应用层实现报文的复制与转发
反向路径转发RPF
结点只转发在它到源的最短路径上的结点转发的分组，其他则丢弃
不能避免冗余广播分组的传输
生成树广播
原理：树中的源结点欲发送分组，则通过树中的邻居分发
一个节点不必知道政客树，只需知道树中的邻居即可
生成树的方法
基于中心的方法
首先定义中心节点（汇合点、核）
结点向中心节点单播加入树报文，此报文使用单播路由选择朝中心出发，直到到达树的结点或者核心
实践中的广播算法
Gnutella（应用层进程）
通过应用级的广播，建立TCP连接
它使用某种形式的序号控制洪泛：16bit标识符+16bit有效载荷描述符，以检测一个接收到的广播以前是否收到、复制、转发过
也以TTL字段限制转发的跳数
范围受限的洪泛
OSPF和IS-IS应用一种序号控制洪泛来广播链路状态通告LSA
用32bit序号，和一个16比特年龄字段标识LSA,用于检测冗余
年龄是增加的，区别新旧报文
多播路由选择算法
特点
多播分组仅被交给网络结点的一个子集
由于多播的接收方过多，不适宜原来的目的地址编址，而是采用间接地址 编址
D类多播地址：表示一组接收方的单一标识
多播组：一个与D类地址相关联的接收方小组被
1、因特网管理协议IGMP
IGMP运行在一台主机与其直接相连的路由器之间
IGMP提供手段，让主机上的应用程序加入一个特定的多播组
多播路由算法：协调遍及因特网内的多播路由器，以便多播数据能路由到想去的目的地
IGMP报文
IGMP承载在IP数据包中，IP协议号为2
有三种报文类型
membership_query报文：路由器向所有与主机相连的接口发送此报文，以确定该接口上主机已加入的所有多播集合。
membership_report报文：回应上述报文。当一个应用程序首次加入一个多播组时，主机主动产生此报文
leave_group报文：可选
当无主机想用一个具有给定地址的该报文时，该路由器就推断没有主机在这个多播组了
软状态协议
状态未被显式地更新，则通过超时事件被删除
2、多播路由选择算法
目标：发现树的链路
方法
使用一棵组共享树的多播路由选择
实现：即树的建立过程，见上
关键：选择树的核心
构建单一的，共享的路由选择树，以路由所有发送方的分组
使用一棵基于源的树的多播路由选择
多播组中每个源利用RPF原则构建一棵多播路由选择树
由于RPF转发时会向不是树成员的结点转发数据报，故而需要剪枝
剪枝：一台接收到多播分组的多播路由器，如无加入该组的相连主机，则它可以向其上游路由器发送一个剪枝报文；如果一个路由器的所有下游路由器都发送了剪枝报文，则它也向上发送一个剪枝报文
3、在因特网中的多播路由选择
距离向量多播路由选择协议DVMRP
实现了具有RPF和剪枝算法的基于源的树
协议无关的多播PIM路由选择协议
稠密模式
多播组成员位置分布稠密，即，该区大多数路由器都参与多播路由选择中
是一种洪泛和剪枝反向路径转发技术
稀疏模式
组成员极为分散
在源特定多播SSM中，仅允许单已发送方向多播树中发送流量，大大简化了树的构造和维护
SDN（软件定义网络）控制平面
概述
SDN控制器和SDN网络控制应用程序
OpenFLow协议
数据平面和控制平面交互的例子
SDN的过去和未来
网络管理和SNMP
概述
网络管理框架
简单网络管理协议