主要内容

  • packets(包)是如何从源地址传送到目标地址的
  • 如何选择路径
    • Routing protocol, Router
    • Routed protocol: IPv4,IPv6
    • Others
  • Outline of network layer
  • Outline of Routing algorithm
  • Learn Dijkstra algorithm
  • Distance-vector algorithm ：Rip
  • Link state routing algorithm ：OSPF
  • Multi-level routing, broadcast routing, mobile routing, adhoc routing, p2p, and et al.
第一部分
  • Main function of network layer
  • Routing algorithm
    • Static routing algorithm
      • Dijkstra
      • flooding
    • Dynamic routing algorithm
      • DV
      • LS
  • Learn Dijkstra algorithm

网络层 network layer

网络层的位置

网络层的主要作用

将数据包从源头一直传输到目的地。

Service types provided by network layer 服务类型

  • Connection oriented service 面向连接：X.25, ATM 虚电路
  • Connectionless service 无连接：IP 数据报

  • Virtual-circuit subnet 虚电路子网
    • Select a path when connection is established
      • 建立连接时选择路径
    • Each packet has a connection-number
      • 每个数据包都有一个连接号
    • Connection is removed when communication is over
      • 通信结束后连接被删除
  • Datagram subnet 数据报子网
    • Each datagram has destination-address
      • 每个数据报都有目的地址
    • Each datagram look for path independently
      • 每个数据报独立寻找路径

IPv4协议

介绍
  • 网际协议版本4
  • 一种无连接的协议，是互联网的核心
  • 也是使 用最广泛的网际协议版本，其后继版本为IPv6
基本功能

internet协议执行两个基本功能

  • 寻址(addressing)
  • 分片(fragmentation)
IPv4数据报格式

数据报分片

总结

IP地址

IP地址的分类

一些特殊的地址

子网的划分

Routing table

  • Static routing

    • Configured by administrator: ip route

  • Dynamic routing

    • Routing algorithm
      • Distance vector routing（D-V）
      • Link state routing（L-S）

  • 由管理员配置的路由表项称为静态路由

    • 适合小而稳定的网络，成本更低
    • 默认路由：目的网络地址和子网掩码均为0.0.0.0，如：

  • 可以使用Windows：route print, check routing table

  • 通过路由协议获得的路由表项称为动态路由

    • 适合大型变分网络，成本更高

Routed protocol和Routing protocol的区别

  • Routed protocol 直接连接用户的
    • example：IP、IPX
  • Routing protocol 维持路由间的表格
    • Distance vector routing
    • Link state routing
    • Hybrid routing

Routing algorithm

  • 路由算法设计必须考虑以下问题：
    • 正确性、简单性、鲁棒性、稳定性、公平性和最优性（矛盾、权衡）
    • Correctness, simplicity, robustness, stability, fairness, and optimality (contradictory、trade-off)
  • 路由算法分类
    • 静态算法（非自适应路由选择）（not self-adaptive）
    • 动态算法（自适应路由选择）（ self-adaptive ）

路由算法中的度量

  • Alias：cost，量度、代价、开销、成本
  • Common metric
    • Path length：hop (跳数)
    • reliability：error rate on line
    • delay
    • bandwidth
    • Load of router
    • Communication cost

最优化原则 Optimization principle

  • 如果路由器 J 在从路由器 I 到路由器 K 的最优路径上，那么从 J 到 K 的最优路径也落在同一条路径上
  • 从所有源到给定目的地的一组最优路由形成以目的地为根的树（称为sink tree）

Sink tree(汇集树)

  • 汇集树不一定是唯一的
  • 所有路由算法的目标都是发现并使用所有路由器的汇集树

Shortest path routing

  • 定义

    • 用于计算一个节点到其他所有节点的最短路径，主要特点是以起始点为 中心向外逐层扩展，直到扩展到终点为止

Dijkstra算法

  • compute shortest path using weight on communication-line

  • 带有最少行的路径可能不是最短路径

  • 最短的路可能不是最快的

步骤

例子

Flooding

  • Every incoming packet is sent out on every outgoing line except the one it arrived on
    • 不计算路径，有路就走

  • problem：duplicate packets，such as 3，6

  • 解决：

    • 在packet-header中加一个计数器，通过节点时减1，计数器为零时丢包
    • 每个节点建立一个寄存器表，数据包再次到达节点时被丢弃
    • 选择性地Flooding

  • 缺点：重复数据包有两个，浪费带宽

  • 优点：可靠性高，路径短，军事上使用频繁

Dynamic Routing algorithm

  • Distance vector routing algorithm
    • For example: RIP
  • Link state routing algorithm
    • For example: OSPF
  • Hybrid routing 混合路由
    • For example: IGRP

动态的实现

  • 如果路由器需要通信，他们必须说相同的语言，即相同的路由协议
  • 一个新的路由器必须主动介绍自己（问好）
  • 定期发送 hello 数据包以了解其他人的健康状况（保持活动状态）

Distance Vector Routing 距离矢量路由

  • 距离矢量路由选择：
    • 通过让每个路由器维护一个表（即矢量）来操作
    • 给出到每个目的地的最佳已知距离以及使用哪条线路到达那里。
  • D-V 算法是动态的和分布式的。 常用于小型网络，RIP是D-V的典型例子
  • RIP：路由信息协议，路由选择信息协议，1988，RFC1058
Working principle of DV -- DV算法的工作原则
  • 每个路由器使用两个向量 $D_i $和 \(S_i\)
    • $D_i $表示从一个节点到所有其他节点的距离
    • \(S_i\) 表示下一个节点（跳）
  • 在邻居路由器之间交换路径信息
  • 每个节点根据路径信息更新自己的路由表

更新表
  • 交换向量后
    • 更新距离
    • 更新下一个节点

练习

D-V算法的特点
  • 优势
    • 算法很简单
  • 坏处
    • 交换的信息太大
    • 路径信息传播缓慢，路径信息可能不同
    • 收敛速度慢，导致无穷计数问题。
    • 不适合大网络
Main features of RIP
  • RIP 是一种 D-V 路由协议
  • RIP 使用 hop（跳数）作为度量(metric)
  • 当metric大于15时，认为目的地不可达
  • 默认发送周期为 30 秒
Disadvantage of RIP
  • 当目标网络的度量大于 15（如此小）时无法到达
  • RIP的度量是hop，一路都是router的编号，不太合理
  • 实际中，常数到无穷大，收敛缓慢
The problems induced by DV
  • Representation
    • routing loop（路由环路）
    • Count to infinite（计数到无穷问题）
    • slow Convergence （收敛慢的问题）
  • Cause
    • Trust wrong routing information
Main problem of DV

It reacts rapidly to good news, but leisurely to bad news(好消息跑得快，坏消息传得慢)

  • 距离矢量路由一直在 ARPANET 中使用，直到 1979 年它被链路状态路由取代。
  • 链路状态路由的变体现在被广泛使用。
  • 链路状态路由背后的思想由五个部分组成：
    • 发现它的邻居并了解他们的网络地址。
    • 测量每个邻居的延迟或成本。
    • 构造一个分组，分组中包含刚收到的所有信息
    • 将此分组发送给其他的路由器
    • 计算到所有其他路由器的最短路径。

Learning about the Neighbors

  • 当路由器启动时，它会在每条点对点线路上发送一个特殊的 HELLO 数据包。
  • 期望另一端的路由器发回一个回复，告诉它是谁（使用全局唯一名称）。
  • 当两个或多个路由器通过 LAN 连接时，LAN 可以建模为一个节点。

Measuring Line Cost 设置到每个邻居的成本度量

  • 为了确定线路的成本，路由器发送一个特殊的 ECHO 数据包，并且要求对方立即发回。

  • 通过测量往返时间，发送路由器可以获得对延迟的合理估计。

    • 为了获得更好的结果，可以多次进行测试，并使用平均值。

  • 为了将负载考虑在内，往返计时器必须在 ECHO 数据包排队时启动。

  • 要忽略负载，应在 ECHO 数据包到达队列前端时启动计时器。

  • 测量延迟时是否应考虑负载？

    • 论证可以通过两种方式进行。

  • 链路状态包被构造为发送到其他路由器。 数据包中包含的信息是：
    • ID of the sender
    • sequence number
    • age
    • list of neighbors
    • delay to each neighbor
  • 什么时候建立？
    • 状态数据包可能会定期构建，或者在某些重要事件发生时构建，例如线路或邻居断开或再次恢复。

  1. A subnet. (b) The link state packets for this subnet.
  • 基本算法：
    • 每个状态数据包都包含一个序列号，该序列号随着每个新数据包的发送而递增。
    • 路由器会跟踪它们看到的所有（源路由器、序列）对。
    • 当一个新的链路状态数据包进来时，它会根据已经看到的数据包列表进行检查。
      • 如果它是新的，它将在除到达的那条线路之外的所有线路上转发（即，flooding）。
      • 如果它是重复的，则将其丢弃--discarded
      • 如果一个序列号低于迄今为止看到的最高序列号的数据包到达，则它被视为已过时而被拒绝。

  • 基本算法的问题：
    • 序列号可能会环绕，导致混淆。
      • 解决方案：使用 32 位序列号。 每秒一个数据包，需要 137 年才能环绕。
    • 如果路由器崩溃，它将失去对自己序列号的跟踪。 如果它再次从序列号 0 开始，新的数据包将被其他路由器拒绝为过时/重复。
    • 如果序列号被破坏并且接收到 65,540 而不是 4（1 位错误），则数据包 5 -- 65540 将被拒绝为已过时。

00000000000000100 10000000000000100

  • 路由器崩溃和序列号损坏的解决方案是将age（例如，60）与来自任何路由器的每个状态数据包相关联，并每秒递减一次年龄。

  • 当年龄达到zero时，来自该路由器的信息将被丢弃。

  • 通常每 10 秒就会有一个新数据包出现，因此路由器信息仅在路由器关闭时才会超时（或连续丢失 6 个数据包，这种情况不太可能发生）。

  • 对基本算法的一些改进使其更加健壮。

    • 当一个状态包进入路由器进行flooding时，它首先被放置在一个保持区（保留区）中等待一小会。
    • 如果来自同一源的另一个状态数据包在传输之前进入，则比较它们的序列号。
      • 如果它们相等，则丢弃重复项。
      • 如果它们不同，则较旧的将被丢弃。
    • 为了防止线路上的错误，所有状态数据包都被确认。
    • 当一条线路空闲时，保持区被循环扫描以选择要发送的数据包或确认。

Computing the New Routes

  • 一组完整的链路状态数据包允许路由器构建整个子网的图。
  • 我们现在可以使用 Dijkstra 算法来计算路由器之间的最短路径。
  • 我们可以在路由器中安装这些信息来引导数据包。 （设置路由表）

Characteristics of L-S routing algorithm

  • 好处
    • 每个路由器的一致性好
    • 收敛性好
    • 适合大网络
  • 缺点
    • 每个路由器需要更大的存储空间
    • 计算工作量很大

OSPF

  • 先开最短路径
  • 用图代替真实网络
    • 每个路由器都是一个节点
    • 计量成本（公制）
    • 可能有几张图
  • 计算最短路径

BGP（border gateway protocol）（边界网关协议）

  • 不同的协议 - AS 之间需要 BGP（边界网关协议），因为内部网关协议和外部网关协议的目标不同。
  • BGP 的定义在 RFCs 1771 到 1774 中。

  • 外部网关协议路由器的典型策略涉及政治、安全或经济方面的考虑。
  • 鉴于 BGP 对传输流量的特殊兴趣，网络被分为三类之一。
    • 存根网络 stub networks
    • 多连接网络 multiconnected networks
    • 过境网络 transit networks

  • BGP 路由器对通过建立 TCP 连接相互通信。
  • BGP 从根本上说是一种距离矢量协议，但与大多数其他协议（如 RIP）截然不同。
    • BGP 路由器会跟踪准确的路径。