计软杂谈学习笔记
  • 负责通过多个链路从源端向接收方传递数据包

网络层的设计问题

存储转发数据包交换

  • 主机向网络发送数据，数据包由路由器转发
  • 数据包到达路由器，并路由器的链路层完成了对其校验和的验证后，它先被存储在路由器上，然后被转发到下一个路由器上

提供给传输层的服务

面向无连接的服务（数据报网络）

  • 每个数据包都是独立处理的
  • 网络层只负责将数据包从源传送到目的地
  • 数据包使用其目标地址通过路由表进行转发
    • 数据包可以通过不同的路径到达目的地
  • 路由表会由于流量拥塞而进行更新
    • 管理路由表并做出路由选择的算法称为路由算法（routing algorithm）

面向连接的服务（虚电路网络）

  • 在发送数据报之前，应建立虚拟连接以确定数据报的传送路径
  • 数据包包含源地址和目标地址，一个流标签，一个虚电路标识符指明属于哪一条虚电路（VC号）
  • 数据包使用其内部的标识符沿虚电路转发
    • 虚电路建立过程中确定每条链路的VC号，同时在路由器转发表中增加表项
    • 连接建立后，数据报全部沿相同的路径到达目的地
  • 每台路由器的转发表包括了VC号的转换【入接口，入VC号，出接口，出VC号】
  • 路由器会为出境流量分配不同的VC号，这被称为标签交换（label switching）
    • 多协议标签交换（MPLS，MultiiProtocol Label Switching），主要被用在ISP网络
  • 一个分组沿着其路由在每条链路上不简单的保持相同的VC号的原因
    • 逐链路VC号代替统一号码减少了在分组首部中VC字段的长度
    • 通过允许沿着该虚电路路径的每条链路有不同的VC号，大大简化了虚电路的建立

虚电路与数据报网络的比较

问题数据包网络虚电路网络
电路建立不需要需要
寻址每个包包含全部的源和目标地址每个包包含简短的VC号
状态信息路由器不保留连接状态针对每个连接，每条VC都需要路由器保存其状态
路由方式每个数据包被单独路由建立VC时选择路由，所有包都遵循该路由
路由器失效的影响没影响，除了那些路由器奔溃期间丢失的包穿过故障路由器的所有VC都将中断
服务质量困难容易，如果在预先建立每条VC时有足够的资源可分配
拥塞控制困难容易，如果在预先建立每条VC时有足够的资源可分配

路由算法

路由器中的两个进程

路由（routing）

  • 发现网络路径
  • 决定使用哪条路线
  • 生成并更新路由表
  • 依赖于分布式算法

转发（forwarding）

  • 沿路径发送数据包
  • 在每个数据包到达到达的时候对它进行处理，在路由表中查找该数据包所对应的处境线路

路由算法

  • 将网络建模为节点和链接图
  • 了解网络拓扑
  • 管理路由表
  • 做出路由决策
  • 决定优化什么（例如：公平与效率）
  • 因拓扑的更改而更新路由（例如：发生故障）

优化原则

  • 最优路径的每个部分也是最优路径
  • 从所有的源到一个指定目标的最优路径的集合构成了一颗以目标节点为根的树，即汇集树（sink tree）
    • 在示例中，“最优”表示跳数最少
  • 所有路由算法的目标是为所有的路由器找到这样的汇集树，并根据汇集树来转发数据包

最短路径算法

  • Dijkstra算法在图上计算一个汇集树
    • 每条路径都被分配了一个非负的权重/距离
    • 最短路径是总权重最小的路径

泛洪算法（flooding）

  • 一种向所有网络节点发送数据包的简单方法，是一种有效的广播手段
  • 路由器将每一个入境数据包发送到除了该数据包到达的那条线路以外的每一条出境线路
  • 可以使用跳计数器来一直泛洪
  • 更好的技术是让路由器需跟踪已经泛洪过的数据包，避免第二次发送它们以阻止泛洪
  • 有非常好的鲁棒性

距离矢量算法（distance vector routing）

  • 距离矢量是一种分布式路由算法
    • 最短路径计算在节点之间分割
    • 又被称为Bellman-ford（Ford-Fulkerson）算法
    • 是最初ARPANET使用的路由算法
    • 使用于RIP协议、IGRP协议…
  • 算法：“tell neighbors where I can go, and how far”
    • 通常是以延迟作为距离度量
    • 每个节点都知道到其邻居的距离
    • 每个节点定期向所有邻居播发最小已知距离的向量
    • 每个节点使用接收到的向量更新自己的向量
  • 无穷计算问题
    • 失败（路由器停机或链路断裂）会导致DV在寻找无法到达的节点的路径时“计数到无穷大”
  • 链接状态路由是距离矢量算法的替代（由于无穷计算问题）
    • 更多的计算但更简单的动态
    • 广泛应用于互联网（OSPF、IS-IS）
  • 算法： “tell all which neighbors I have”
    • 每个节点在 LSP（链路状态包）中泛洪有关其邻居的信息
    • 所有节点学习完整的网络图
    • 每个节点运行 Dijkstra 算法来计算每个目的地的路径
  • LSPs
    • 节点的 LSP（链路状态包）包含发送方的标识符、序号（Seq）、年龄（Age）、邻居列表和到达它们的链路权重
    • 链路权重可以选择成本与链路带宽成反比，也可以选择链路的延迟
    • 可以选择周期性的创建数据包，也可以选择发生重要事件时才创建数据包
  • 可靠泛洪
    • 序号和年龄用于可靠泛洪
    • 序号
      • 序号随着每一个新数据包发出而逐一递增
      • 新的数据包会被转发到除了入境线路之外的所有其他线路上
      • 重复数据包会被丢弃
      • 数据包的序号小于当前看到过的来自该源路由器的最大序列号，则该数据包已过时，被丢弃
    • 年龄
      • 年龄每秒钟减1
      • 当年龄被减到0时，该信息被丢弃

层次路由（hierarchical routing）

  • 层次路由减少了路由计算的工作量，但可能会导致比平面路由稍长的路径

广播路由（broadcast routing）

  • 广播向所有节点发送数据包
    • 多目标路由（multidestination routing）
    • 逆向路径转发（reverse path forwarding，RPF）
      • 判断数据包到来的线路是否是通常用来给广播源发送分组的线路。 如果是，路由器将该分组转发到除到来的那条线路之外的所有其他线路
      • 否则，此分组被当作一个可能的重复分组被丢弃
      • 通常汇集树被用作来判断是否是最佳线路

组播路由（multicast routing）

  • 给组发送消息被称为组播
  • 不同的组播有不同的生成树
  • 距离矢量组播路由协议（DVMRP）
  • 基于核心树（core-based trees，CBT）
    • 使用单棵生成树进行组播
    • 生成树是从核心（core）节点到组成员的汇集树
    • 发送者把数据包发送给核心，当数据包到达核心后，它再被沿着树往下转发
    • 在把数据包发送给核心的过程中，数据包同时沿着树转发到其他分支，即组播并非从核心开始

选播路由（anycast routing）

  • 向一个最近的组成员发送数据包被称为选播
  • 距离矢量和链路状态路由算法可以用来生成选播路由

移动主机路由

  • 可以通过家乡代理（home agent）访问移动主机

拥塞控制算法

网络性能

  • 网络的性能可以用延迟、吞吐量和丢包来衡量
    • 延迟：传输延迟、传播延迟、处理延迟和排队延迟。
    • 网络中任一点的吞吐量：每秒通过该点的比特数，即该点的数据传输速率
    • 丢包：传输过程中丢失的数据包数
  • 拥塞控制是一种提高网络性能的机制

拥塞控制的途径

  • 增加资源或减少负载
  • 不同时间尺度上拥塞控制的途径（从慢到快）
    • 网络供给（增加资源）
    • 流量感知路由
    • 准入控制
    • 流量调节
    • 负载脱落

流量感知路由（traffic-aware routing）

  • 根据流量的变化选择路由，而不仅仅是拓扑结构的变化
  • 最直接的方式是将链路权重设置为一个链路带宽、传输延迟、测量负载或平均排队延迟的函数
  • 但要注意避免振荡（忽略负载，只考虑带宽和传输延迟）

准入控制（admission control）

  • 除非网络可以携带额外的流量而不会变得拥塞，否则不再建立新的虚电路
  • 可以和流量感知路由相结合

流量调节（traffic throttling）

  • 拥塞的路由器（内部排队延迟）向发送方发送反馈信息以降低流量
  • 显式拥塞通知（ECN）
    • 标记数据包，接收方在发送应答包时告知发送方
  • 逐跳后压
    • 让抑制包在沿途的每一跳都发挥作用
    • 拥塞点上的拥塞现象能很快得到缓解
    • 代价是上游路径需要消耗更大的缓冲空间

负载丢弃（load shedding）

  • 当路由器来不及处理数据包，直接将它们丢弃

服务质量（QoS）

应用需求

  • 带宽、延迟、抖动和丢失绝对了一个流要求的服务质量
应用带宽延迟抖动丢失
电子邮件低低低中等
文件共享高低低中等
浏览网页中等中等低中等
远程登录低中等中等中等
音频点播低低高低
视频点播高低高低
电话低高高低
视频电话高高高低
  • 网络可以支持不同类别的QoS
  • ATM网络支持：
网络类型应用
恒定比特率电话
实时可变比特率压缩的视频会议
非实时可变比特率点播电影
可用比特率文件传输

流量整形（traffic shaping）

  • 指调节进入网络的数据流的平均速率和突发性所采用的技术
  • 当一个流在建立时，用户和网络就该流的流量模式达成一致的协议

漏桶/令牌桶

  • 漏桶/令牌桶限制了平均速率（R）和短期突发流量（B）
  • 对于漏桶，无论流入漏桶的水的速率有多大，只要，漏桶中还有水，水流出桶的速率是一个恒定速率R
  • 对于令牌桶，水龙头速率为R，水桶容量为B。为了发送一个数据包，必须能从桶中掏出水或令牌

包调度（packet scheduling）

  • 在同一个流的数据包之间以及在竞争流之间分配路由器资源的算法称为包调度算法
  • 潜在资源
    • 带宽
    • 缓冲区
    • CPU周期
  • 先进先出算法（FIFO）在队列满时通常丢弃新到的数据包（尾丢包），可能造成饥饿
  • 公平队列算法（fair queueing），线路空闲时循环扫描各个流的队列，从下一个队列中取出第一个数据包发送
  • 加权公平队列（WFQ），数据包接数据包改为字节接字节的循环方式，为流设置权重W
  • Fi = max(Ai , Fi-1) +Li/W（每个流单独计算）

准入控制（admission control）

  • 准入控制采用流规范，并决定网络是否能够承载该规范

综合服务（integrated services）

  • 为每个流设计QoS；处理组播通信
  • RSVP（资源预留协议）：
    • 接收方将请求发送回发送方
    • 沿途的每个路由器都保留资源
    • 路由器为同一个流合并多个请求
    • 已设置整个路径，或未进行预留

区分服务（differentiated services）

  • 加速转发，将服务类型分为常规的和加速的
  • 确保转发，将服务类型分为12种

网络互联

何以连接网络

  • 网络互联基于共有网络层-IP

隧道

  • 通过中间的网络连接两个网络
    • 数据包被封装在中间

数据包分段

  • 由于许多原因，网络具有不同的数据包大小限制
    • 通过分段和重组发送的大数据包
    • 透明分段，包在每个网络内分段/重组
    • 非透明分段，包只在目的地重组
  • 路径MTU发现避免了网络分段
  • 路由器将MTU（最大传输单元）返回到源并丢弃大数据包

Internet的网络层

IPV4

  • IPV4报头包含20字节定长部分和一个可选的变长部分
    • 版本：4位，记录数据包属于协议哪个版本
    • IHL：4位，记录头部长度（以4字节长度为单位），最小值为5，最大值为15
    • 区分服务：8位，前6位标记数据包的服务类别，后2位携带显示拥塞通知信息
    • 总长度：16位，记录数据报总长度
    • 标识：16位，用于标识数据报，同一个数据包的所有段包含同样的的标识符
    • DF：1位，代表不分段标志位，1代表不分段
    • MF：1位，代表更多的段标志位，0代表最后一段
    • 分段偏移量：13位，指明了该段在当前数据报中的位置（以8字节长度为单位），除了数据报的最后一个段外，其他所有段的长度必须是8字节的倍数
    • 生存期（TTL）：8位，用于限制数据包生存期的计数器，递减到0时数据包被丢弃，并向源主机发回报警包
    • 协议：8位，记录上层协议，ICMP01，IGMP02，TCP06，UDP17，OSPF89
    • 校验和：16位
    • 源地址：32位，源IP地址
    • 目标地址：32位，目标IP地址

IP地址

  • IPv4地址是一个32位地址，它唯一且地定义了设备到Internet的连接。
  • IPv4的地址空间是2^32

前缀

  • 地址以称为前缀的块分配
  • 前缀由网络部分确定
  • 书写格式：地址/长度，如18.0.31.0/24

分类和特殊寻址

  • 分类寻址中IP地址被分为5个类别
    • A类，1.0.0.0-127.255.255.255/8
    • B类，128.0.0.0-191.255.255.255/16
    • C类，192.0.0.0-223.255.255.255/24
    • D类，224.0.0.0-239.255.255.255（组播地址）
    • E类，240.0.0.0-255.255.255.255（保留地址）
  • 特殊IP地址
    • 0.0.0.0 主机
    • 00…00|主机 本地网络主机
    • 255.255.255.255 本地网络广播
    • 网络|11…11 远程网络广播
    • 127|任何内容 回环

子网

  • 在内部将一个网络块分成几个部分供多个内部网络使用，但对外部仍然像单个网络一样

IP地址聚合

  • 聚合将多个IP前缀合并为一个较大的前缀，以减少路由表的大小

最长前缀匹配

  • 数据包被转发到具有最长匹配前缀或最小地址块的条目
    • 使转发复杂化，但增加了灵活性

NAT

  • NAT（网络地址转换）盒将一个外部IP地址映射到多个内部IP地址
    • 使用TCP/UDP端口区分连接
    • 违反分层原则；在家庭等中非常常见
  • 私有地址：
    • 10.0.0.0-10.255.255.255/8
    • 172.16.0.0-172.31.255.255/12
    • 192.168.0.0-192.168.255.255/16

IPV6

  • IPv6的地址空间包含21282^{128}个地址。这个地址空间是IPv4地址的2962^{96}倍
  • IPv6报头40字节，并且更简单
    • 版本：4位
    • 区分服务：8位，用于区分数据包的服务类别，与IPV4相同
    • 流标签：20位，为源端和接收方提供了一种建立伪连接的方式
    • 有效载荷长度：16位
    • 下一个头：8位，指明当前头之后还有哪种扩展头。如果当前头是最后一个头，则该字段指定了该数据包的上层协议（TCP/UDP）
    • 跳数限制：8位，同IPV4
    • 源地址：16字节
    • 目标地址：16字节
  • 三种过渡策略：
    • 双栈
    • 隧道
    • 头部翻译

Internet控制协议

ICMP（Internet控制消息协议）

  • 处理错误和控制消息
  • 每一种消息被封装在IP包中
  • 如果路由器不能传递或转发数据包，它会向源发送一条ICMP“主机不可访问”消息
  • 若路由器接收到本应发送至另一路由器的数据包，则向发送方发送ICMP“重定向”消息；发送方修改其路由表
  • ICMP“路由器发现”消息允许主机了解其网络中的路由器，并初始化和更新其路由表
  • ICMP回送请求和回复有助于诊断并用于“ping”

ARP（地址解析协议）

  • ARP允许节点从IP地址中查找目标以太网地址

RARP（反向地址转换协议）

  • RARP允许局域网的物理机器从网关服务器的 ARP 表或者缓存上请求其 IP 地址
  • RARP request也是广播，没有目标地址；RARP reply也是有目标地址，也是单播

DHCP（动态主机配置协议）

  • DHCP是一个应用层程序，使用客户机-服务器范例，实际上在网络层帮助TCP/IP
  • 客户机登录服务器时就可以自动获得服务器分配的IP地址和子网掩码
    • DHCP DISCOVER，客户端寻找DHCP服务器位置时所使用的报文
    • DHCP OFFER，告知用户本服务器可以为其提供IP地址
    • DHCP REQUEST，向该服务器发送一个广播的Request请求报文通告选择的服务器。希望获得所分配的IP地址
    • DHCP ACK，发送ACK应答报文，通知用户可以使用分配的IP地址

MPLS（多协议标签交换）

  • 一种在开放的通信网上利用标签引导数据高速、高效传输的新技术
  • MPLS介于IP网络层和链路层协议之间，有时被称为2.5层协议
  • MPLS沿着已建立的路径发送数据包
  • 在进入MPLS网络（如ISP）时根据IP地址添加标签，在离开时删除
    • 转发仅在MPLS网络内使用标签

OSPF/开放式最短路径优先（内部网关路由协议/IGP）

  • OSPF（Open Shortest Path First开放式最短路径优先）计算单个网络（如ISP）的路由
    • 将网络建模为加权边图
  • OSPF将一个大型网络（自治系统）划分为连接到主干区域的区域
    • 有助于扩大规模

BGP/边界网关协议（外部网关路由协议/EGP）

  • BGP（边界网关协议）计算互连自治网络中的路由
    • 关键作用是尊重网络的路由政策约束

Internet组播

  • 组具有保留的IP地址范围（D类）
  • 通过协议（如PIM）计算的路由：
    • 密集模式使用带剪枝的RPF(逆向路径转发树)
    • 稀疏模式使用核心树(CBT)
  • IP组播除了在单个网络中（如数据中心、有线电视网络）外，没有得到广泛应用
backtop