网络层的设计要点：

  • 存储-转发分组交换
  • 向传输层提供服务：独立于路由器技术、路由器数量类型拓扑关系对传输层不可见、跨越多个LAN和WAN进行统一编址
  • 无连接服务的实现：数据报、数据报子网
  • 面向连接服务的实现：虚电路（VC，virtual circuit）、虚电路子网；要求建立电路、路由器建立表项、分组只含VC号而不需目标和源地址、路由失效将终止、容易实现服务质量和拥塞控制

路由算法

  • 路由：确定该使用哪一条路径
  • 转发：当一个分组到达时所采取的的动作
  • 自适应算法：会根据拓扑结构和流量的变化改变路由决策
  • 非自适应算法：不会根据当前测量或者估计的流量和拓扑结构，来调整它们的路由决策（静态路由）
  • 会话路由：虚电路子网中路由，当建立虚电路时才需要确定路由路径

优化原则

  • 最优化原则：如果路由器J在I到K的最优路径上，则J到K的最优路径也必定沿着同样的路由路径。
  • 汇集树：从所有的源到一个制定目标的最优路径的集合构成以目标节点为根的树。

最短路径路由

  • 跳数、物理距离、延迟
  • Dijkstra标记算法：两个节点间最短路径的算法，初始时所有节点的标记（从源节点沿着当前已知的最佳路径到达该节点的距离）都是暂时的，当已经发现一个标记代表了最短可能路径的时候，标记被变为永久的（以后不再改变）

扩散算发

  • 同样为静态的路由算法
  • 每一个进来的分组都被发送到除了进来的那条路线之外的每一条输出线路上。
  • 抑制扩散过程
  • 分组头包含跳计数器，初始值等于源于目标间路径长度或最坏情形下的长度（子网直径）
  • 分组头包含序列号，让路由记录已经被扩散过的分组
  • 选择性扩散：只输出到大概方向正确的线路上
  • 扩散法并不实用，但其高度健壮性可用于军事用途

距离矢量路由

  • 属于动态的路由算法
  • 每个路由器维护一张表（即一个矢量），列出已知目标的最佳距离及线路，通过与邻居交换信息不断更新
  • Bellman-Ford 路由算法、Ford-Fulkerson算法
  • 无穷计算问题：X告诉Y它有一条路径的时候，Y无法知道自己是否在这条路径上。每次更新列表，坏消息扩散一步，直至无穷大。

链路状态路由

路由器的工作分为5个部分

  • 发现邻居节点：启动时发送HELLO分组给邻居，邻居以其网络地址应答
  • 测量线路开销：发送ECHO分组，得到邻居节点的延迟
  • 创建链路状态分组：包括发送方标识、序列号、年龄、邻居及其延迟列表
  • 发布链路状态分组：扩散法
  • 序列号回转，采用32位序列号
  • 路由器崩溃，从0开始的下一分组将被作为重复分组而拒绝
  • 序列号破坏，将作为过时分组而拒绝
  • 计算新的路由路径：获得所有链路状态分组后，运行Dijkstra算法构建出到所有可能目标的最短路径

另一路由状态协议是IS-IS（intermediate system-intermediate system，中间系统对中间系统），原用于DECnet、NSFNET骨干网、CDPD、Novell Netware（使用变种NLSP来路由IPX分组），后被ISO采纳为无连接网络层协议CLNP，后被多次修改，如IP协议。

OSPF采纳了IS-IS，但IS-IS编码方法支持携带多个网络层协议的信息，二OSPF不具备这样的特性。

分级路由

路由器被划分为区域（region），区域被组织为群（cluster），群被组织为区（zone），区被组织为组（group）。路由器只知道自己所在区域的目标地址。

广播路由

  • 广播：同时将所有目标发送一个分组
  • 实现方法
  • 源机器给每一目标单独发送
  • 扩散法
  • 多目标路由：只给必要的路线发送
  • 汇集树
  • 逆向路径转发：如果通过常用发送分组的线路到达，则认为是第一份副本并转发

多播路由

  • 只给一组目标发送，而不是发送给所有目标

移动主机路由

  • 主场所：主机的永久性地址
  • 外部代理：记录当前访问该区域的移动主机
  • 本地代理：记录主场所在这个区域，当前正在访问其他区域的主机

Ad Hoc 网络中的路由

  • 每个节点包含一个主机和一个路由器，节点两两相邻，则成为Ad Hoc网络或MANET（mobile ad hoc networks，移动Ad Hoc 网络）
  • AODV（ad hoc on-demand distance vector）路由算法：类似Bellman-Ford距离矢量算法
  • 路径发现
  • 路径维护：活动邻居

对等网络中的节点查询

  • 节点标识符：IP地址的160位散列值
  • 键：记录名字的160位散列值，该记录的索引关联信息保存在对应标识符的节点上
  • successor(i)返回从i开始第一个实际节点的标识符
  • 指取表：加快了搜索目标节点IP的过程

拥塞控制算法

通用原则

  • 监视系统，检测何时何地发送了拥塞
  • 将该信息传递到能够采取行动的地方
  • 调整系统运行

拥塞预防策略

  • 传输层：重传、乱序缓存、确认、流控制、确认超时
  • 网络层：子网内部的虚电路与数据报、分组排队和服务、分组丢弃、路由算法、分组生存期管理
  • 数据链路层：重传、乱序缓存、确认、流控制

虚电路子网中的拥塞控制

  • 准入控制

数据报子网中的拥塞控制

每条线路关联一个变量 u新 = a u旧 + (1-a)f，a表示了路由器忘记历史有多快

  • 警告位：位于分组头，分组到达目标端后，传输实体将警告位复制到下一确认分组，源主机因此削减流量
  • 抑制分组：路由器直接给源主机送回一个抑制分组 （choke packet）
  • 逐跳（hop-by-hop）抑制分组：影响沿途的每一跳，收到抑制分组的路由立即减慢该方向的分组（要求分配更多的缓冲区）

负载丢弃

  • 随机的早期检测：RED（random early detection，随机的早期检测）算法，在恶化之前开始丢弃分组

抖动控制

每一跳都记录期望传输时间，到达晚了就尽快转发，否则多停留一段时间

服务质量

好的服务质量所使用的技术

  • 过度提供资源
  • 缓冲能力：接收方在递交数据前缓存起来
  • 流量整形：在服务器段进行平滑处理；服务等级协定（承运商与顾客）、流量监管（对业务流进行监视）
  • 漏桶算法：Turner（1986），常数服务时间的单服务器排队系统
  • 令牌桶：每隔一段时间产生令牌，每送出去一个分组，计数器减一，到零时不再发送分组。令牌足够时以最大速度输出，此后为令牌产生速度
  • 资源预留：带宽、缓冲区空间、CPU周期
  • 准入控制
  • 比例路由：分散流量到多条路径
  • 分组调度：流之间公平排队、加权的公平排队

综合服务

  • 基于流的算法或综合服务（RFC2205~2210）：流式多媒体的体系结构
  • 资源预留协议（resource reservation protocol，RSVP）

区分服务

  • 基于类别的服务质量（相对于基于流的服务质量）
  • 快速型转发：另外的通道
  • 确保行转发：确保不会丢弃分组

标签交换和MPLS

  • MPLS（multiprotocol label switching，多协议标签交换）：RFC 3031，在数据链路层之上添加MPLS头
  • MPLS与VC（虚电路）区别
  • MPLS 将多个发往同一目标的分组组合起来（虚电路做不到）
  • 建立转发表
  • 虚电路：在建立连接时发送setup packet到网络中建立转发表
  • MPLS：
  • 数据驱动：分组到来时，联系下一跳生成这一分组流（FEC，forwarding equivalence class，转发等价类）的标签；使用有色绳索来避免环
  • 控制驱动：路由启动时，检查哪些路由路径中自己是最终目标，然后为该路径建立FEC（forwarding equivalence class，转发等价类）并分配标签，将标签传递给邻居，传给所有的路由器

网络互联

  • 多协议路由器
  • 面向连接的网络互联：级联虚电路
  • 无连接的网络互联：数据报模型
  • 隧道技术：将IP分组插入WAN网络层分组净荷域中发送
  • 互联网路由：内部网关协议、外部网关协议、自治系统（AS，autonomous system）
  • 分段：每个网络会限制分组的最大长度

Internet上的网络层

原则

  • 保证它能够工作
  • 尽可能使它简单
  • 作出明确的选择
  • 尽可能做到模块化
  • 期望具备异构性
  • 避免使用固定不变的选择和参数
  • 寻找一个好的设计，它不必是最完美的
  • 对于发送操作一定要严格，而对于接收操作要有一定的容忍度
  • 要考虑伸缩性
  • 要考虑性能和代价

IP协议

  • IPV4头：版本、IHL、服务类型、总长度、标识、DF、MF、分段偏移、生命期、协议、头部校验和、源地址、目的地址、选项

IP地址

  • 分类的编制方案（classful addressing）
  • A类：0+网络+主机；1.0.0.0~127.255.255.255
  • B类：10+网络+主机；128.0.0.0~191.255.255.255
  • C类：110+网络+主机；192.0.0.0~223.255.255.255
  • D类：1110+多播地址；224.0.0.0~239.255.255.255
  • E类：11110+保留将来使用；240.0.0.0~247.255.255.255
  • 网络号管理：ICANN（internet corporation for assigned names and numbers）
  • 点分十进制标记法
  • 子网：通过子网掩码分别路由
  • CIDR-Classless InterDomain Routing（无类别域间路由）：RFC 1519，将剩余的IP地址以可变大小块的方式进行分配，而不管它们所属的类别；聚集表项（用二进制地址与掩码标识一组IP地址）
  • NAT-网络地址转换
  • 为每个公司分配一个IP地址用于传输Internet流量；公司内部用每台计算机唯一的IP地址常用来传输内部流量。
  • 三段保留的IP地址范围如下，包含这些地址的分组不应出现在Internet上
  • 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
  • 操作方式：IP分组大多携带UDP或TCP净荷，从中提出目标端口和源端口进行一次转换，以TCP为例
  • 请求建立TCP连接时，替换TCP的源地址与源端口，替换IP与TCP头部校验和，建立源地址与源端口的表项（共65535个）
  • IP分组到达时，取出TCP的目标端口，查找对应的内部IP表项，替换目标端口与目标地址，替换IP与TCP头部校验和，转发给内部主机

Internet 控制协议

  • Internet 控制消息协议（ICMP，internet control message protocol）：报告Internet有关事件
  • ARP-地址解析协议（address resolution protocol）
  • 要发送分组的主机首先发送一个广播分组到以太网络，询问IP对应的以太网地址，只有拥有该IP的主机以其以太网地址应答
  • 优化：1.缓存结果；2.机器启动时广播地址映射，请求查询自己的IP，检测有无冲突（应答）
  • RARP（reverse address resolution protocol，反向地址解析协议）：机器启动时询问自己IP，RARP服务器送回它的IP。因受限的广播（全1的目标地址）不会被路由转发，每个网络都需要一个RARP服务器。
  • BOOTP：RFC951、1048、1084，机器启动时使用UDP分组来询问自己IP。新加入的主机要系统管理员为它分配IP地址并加入BOOTP配置文件。
  • DHCP（dynamic host configuration protocol，动态主机配置协议）：RFC 2131、2132，允许手工分配IP，也允许自动分配。也通过广播发送请求，每一网络有一DHCP中继代理（relay agent），主机先广播DHCP DISCOVER分组，DHCP中继代理单播给DHCP服务器，进而获得IP地址。租用：主机需在租用期到达之前申请续租，否则将释放其IP。

OSPF-内部网关路由协议

  • OSPF（open shortest path first）将每个AS划分为编号的区域（area），每个AS有一骨干网络（backbone area），编号为0.
  • OSPF区分4种路由器：
  • 内部路由器：完全在一个区域内部
  • 区域边界路由器：连接两个或多个区域
  • 骨干路由器：位于骨干区域上
  • AS边界路由器：与其他AS中的路由器进行通信
  • 邻接的：OSPF要求每个LAN中选举出一台指派路由器（designated router），该路由器与该LAN上所有其他路由器都是邻接的

BGP-外部网关路由协议

  • BGP（border gateway protocol）将网络分为三种：末端网络（与BGP图只有一个连接）、多连接网络（一般可用来传输中转流量）、穿越网络（愿意处理第三方分组，不过有限制条件）
  • BGP路由间通过TCP连接通信

Internet 多播

  • IP通过D类地址来支持多播，要通过特殊的多播路由器
  • IP支持两种组地址
  • 永久地址
  • 224.0.0.1 一个LAN上的所有系统
  • 224.0.0.2 一个LAN上的所有路由器
  • 224.0.0.5 一个LAN上的所有OSPF路由器
  • 224.0.0.6 一个LAN上的所有指派路由器
  • 临时组：进程要求主机加入或离开某个组，主机记录它的进程属于哪个组
  • 查询和应答分组使用IGMP（internet group management protocol）协议

移动IP

  • 可通过主动ARP（gratuitous ARP）更新路由器的映射缓存
  • 外部代理通过定时发送广告分组（advertisement）来通知新进入的主机

IPv6

  • IPv6为IEEE Network发表的SIPP（simple internet protocol plus，增强的简单Internet协议）
  • IPv6头部：版本、流量类别、流标签、净荷长度、下一个头、跳数限制、源地址、目标地址
  • 扩展头部：为兼容IPv4，跟在固定头部的后面（可以有多个）
  • 16字节固定长度编址

本文采用 知识共享署名 4.0 国际许可协议（CC-BY 4.0）进行许可，转载注明来源即可： https://harttle.land/2014/04/17/computer-network-network-layer.html。如有疏漏、谬误、侵权请通过评论或 邮件 指出。