Unit 3. Packet Switching

数据包传输

这个单元的内容非常多。

  • 网络都建立在分组交换的基础上

    • 分组交换：每个数据包都是一个自包含的单元，携带目标

  • 部分 数学基础知识

  • 数据包延迟的三个组成部分

    • 分组 延迟

    • 传播 延迟

    • 排队 延迟

  • 数据包交换 的 工作原理

Main Topic

Packet Switching

  1. 分组交换的深远影响

  2. 分组交换的数学概念

  3. 数据包延迟的三个主要部分

    1. 分组延迟

    2. 传播延迟

    3. 排队延迟

  5. FIFO 数据包交换网络

What you learned

  • 排队延迟，端到端延迟。

    • 务必明确传播延迟和分组延迟，不要混淆

    • 端到端延迟的可变部分

  • 流媒体的 playback buffer：why and what

  • simple deterministic queue model 确定性队列模型

  • rate guarantees

  • delay guarantees

  • how packets are switched and forwarded

1. What the Internet is ?

brief history of internet and networks...

1.1. History

  1. 1000 BC 物理远程通信：携带信息较少。

    1. 烽火台

    2. 鸽子

    3. Horse Relays

  3. 0 光学通信

    1. Flag...

  5. 1800 AD 信号通信

    1. 电报通信

    2. 编码通信出现

    3. 此时萌生了 错误处理、流量控制、同步、加密 等协议

1.2. Today

  1. about 1960s 网络概念 实验 出现，完成首次通信实验

  2. about 1970s 无线电网络

  3. 1980s - 1990s 互联网协议 TCP/IP 出现，浏览器出现

2. Packet Switching - Background

分组交换

2.1. Circuit Switching

电路交换

Example: 电话

电话通过专用线路连接

电话连接到 交换中心，负责转接。

  1. 拿起电话 发起通信

  2. 告诉中心 你的目标

  3. 沿交换机 link 传播

  4. 与目标通信

  5. 通信关闭

一个电路其实是一个 端到端的物理线...

Problem

  1. Inefficient 效率低下

  2. Diverse Rate 应用通常右不同的使用频率...我们会用同一个线路来 打字和看视频..需求不一样，当前通常不用固定频率的电路来通信

  3. State Management 状态管理，建立状态...解除状态，当有成千上万的状态时，管理变得尤为困难

2.2. Packet Switching

分组交换

数据包：同时携带着 数据 + 地址 等

数据包的传输：逐跳传输，多线同用，流式进行

Packet Switches Have Buffers

Summary

  • 包是由 路由 查找地址 传输的

2.3. 为什么互联网使用包交换？

- 高效的使用昂贵的 Links

  1. 认为线路是稀缺的昂贵资源

  2. 包交换能够建设更弹性的网络，抵御外界攻击

- Resilience to failure of links & routers

为了更可靠的传输...

3. Packet Switching - End to End Delay

分组交换技术很重要，本小节讲解三种 延迟技术

3.1. Propagation Delay

传播延迟

1 bit 从 A 传向 B 所需的时间：完全却决于 length of link

t = l / c

  • t 表示传播时间

  • l 为 length of link

  • c 接近于 光速

3.2. Packetization Delay

分组延迟

数据包的 first bit 到 last bit 传输所需的时间

t = p / r

  • t 表示传播时间

  • p 为 length of packed

  • r 表示 link 的传播速度

3.3. End-to-End Delay

端到端延迟

传播延迟 + 分组延迟 = 端到端延迟

Extend

数据包有可能共享一条链路...于是产生争夺...

  • 则一些数据包必须在拥堵处 队列等待 亦 Buffer

  • 如果 Buffer 过大 会 丢弃一些数据包

  • Buffer 允许数据包等待，不至于直接丢包

  • 但是 Buffer 会增加我们的 端到端延迟

  • 此时间记作 Q(t)，取决于有多少数据包竞争 the same link

于是 End-to-End Delay 写为

  • 其中 Q(t) 为唯一的变量 variable

  • 传播延迟 fixed

  • 分包延迟 fixed

  • 实际上，我们可以用 Ping Command来测量 End-to-End Delay

  • 端到端延迟的下限：传播延迟

Example

A - S1 - S2 -S3 -S4 - B

  1. A - S1 时

    1. S1 会等待整个数据包到达后

    2. 再根据地址转发数据包 到 S2

  3. S1 - S2

    1. 同理......

  5. ...

  6. ...

  7. S4 - B

Packet Delay Variation

RTT 往返时间值

4. Packet Switching - Playback Buffer

缓存区...

4.1. Example

Youtube 不能保证实时与用户通信，所以有一个 播放缓冲区..

提前准备，防止某些数据包无法到达。

  • 缓存包的长度设计

由于现实的数据不是线性的，所以 Buffer 的一大作用就是改变现实数据，使其呈现线性状态

缓存有可能会处于空状态也有可能会处于满状态，这些都应当考虑

5. Packet Switching - Queue Models

讨论多种不同的队列模型

  1. Simple model of a router queue

  2. Small packets reduce end to end delay

  3. Statistical multiplexing gain

5.1. Simple Model of a Router Queue

路由器的队列模型

由当前时刻 t 第一个离开的 数据 D(t)

和当前时刻 t 最后一个进入的 数据 A(t)

之间的数据组成队列，其中队列占用量 Q(t) = A(t) - D(t)

  • leave rate R, means the router forwording rate...

  • enter rate X depends on the rate of data transport

当前假设是 FIFO System...

Example

队列的 A 和 D 可能会出现空闲时段...

如果假设出数据的发送速率的话，可以计算出队列的平均占用量

Example

from kimi

Simple Deterministic Queue Model

想象你去银行排队办业务，队伍里的人一个接一个地被叫号办理业务。这个过程就是一个“队列模型”。而“简单确定性队列模型”是一种很简单的排队方式，它假设所有事情都很规律、很确定，没有随机性。

关键点

• 简单（Simple）：

这个模型很直接，没有复杂的规则。比如，人（或者数据包）按照到达的顺序排队，先到的先服务（FIFO，First-In-First-Out）。

不考虑突发情况，比如突然很多人一起涌进来。

• 确定性（Deterministic）：

一切都是确定的，没有随机性。比如，每个人办理业务的时间是固定的，不会因为心情不好或者业务复杂而变长或变短。

数据包到达的时间间隔也是固定的，不会突然延迟或者提前。

• 队列（Queue）：

就像银行排队一样，数据包也会在一个“队列”里等待处理。队列的长度会随着数据包的到达和离开而变化。

数学表达

简单确定性队列模型可以用几个公式来描述：

• A(t)：到时间 t 为止，到达队列的包裹数量。

• D(t)：到时间 t 为止，从队列里处理完的包裹数量。

• Q(t)：时间 t 时，队列里等待的包裹数量。

它们之间的关系是：

Q(t)=A(t)-D(t)（队列里的包裹=到达的包裹-已处理的包裹）

简单确定性队列模型是一种很基础的排队模型，它假设一切都是规律的、确定的，没有随机性。虽然它很理想化，但在很多场景下可以用来初步分析和优化排队系统。

5.2. Small Packets Reduce End to End Delay

为什么不 send the entire message in one packet ?

  • 端到端延迟会增加

  • link 的利用率

如果 分成 多个 packet，可以减少端到端延迟，还能显著增加信道的效率

5.3. Statistical Multiplexing Gain

统计复用效益

共享带宽：

统计复用增益是指通过根据多个数据流的瞬时流量需求共享带宽，而不是为每个数据流分配固定带宽，从而实现的链路利用率提升。这种方法允许更高效地利用可用带宽，因为它能够适应不同的数据速率，并减少浪费的容量。

出现在分组交换中，多个源主机向同一段链路发送分组，此时用统计多路复用，每个源主机得到的带宽取决于每个源主机的发送量，发的越多，得到的带宽越大，发送一样多的数据则平分该链路的带宽。

queue 的输入 rate 和 输出 rate 相同会造成输出丢包现象。

因为输入的多个信道合在一起实际上有 n*rate 的数据 进入，而输出只会以 1*rate 速度输出

5.4. Example

讲解一个计算 Queue Occupancy 的例子。

总的来说就是计算队列输入 和 输出之间的差值在一段时间内的平均数。

  1. 普通的固定速率收发，接收和排除速率 2:1

  2. 如果数据不固定时间发送（1s一列），队列占用率实际上会增加

6. Packet Switching - Useful Queue Properties

queue process actually an random process.

随机过程的数据收发队列。实际上是一个时间序列。

下面介绍一些特性

6.1. Burstiness Increases Delay

突发性会增加延迟

6.2. Determinism Minimizes Delay

确定性会减少延迟

随即到达的等待时间比规律到达等待时间 要长

6.3. Little's Result

任何一个 queue system 都会有特殊情况，lost or dropped。

但只要有一个 λ 就可以根据 公式计算总的队列平均占用时间。

6.4. The Poisson Process

泊松过程是一个到达过程

利用泊松公式给出了 k arrivals in interval of t seconds...

Why Poisson？

因为它能够描述很多独立随机事件，适用 Computer Network

Be Warned

  1. network traffic is very bursty

  2. 数据包的到达实际上不是严格 poisson 分布的

  3. 但是模型很好模拟了新数据的到达

M/M/1 Queue

固定收发速率，但是过程随机。

根据收发速率 λ 和 μ 的不同，有不同的系统过程，趋于稳定 或 不稳定

extension：连续事件的马尔可夫链

7. Packet Switching - How a Packet Switch Works (1)

分组交换机是如何工作的

  1. look like

  2. do?

7.1. Generic Packet Switch

每次数据交换后需要改变下一跳地址，更新校验和并进入 Queue。

7.2. Ethernet Switch

以太网交换机

如果没有找到对应端口的地址，实际上会进行广播，然后进行学习...

7.3. Internet Router

  1. 处理的是 IP 地址，会检查目的地址是否属于路由器。

  2. 检查 IP 版本

  3. 减少 TTL，更新 header 和校验和

  4. 确定 TTL 是否为 0

  5. 如果是单播，转发给下一个。如果是多播，转发多个端口。

  6. 找到 Ethernet DA 对应的下一跳设备

7.4. Basic Operations: Lookup Address

Ethernet

和以太地址匹配，决定下一个 Action

如果没有匹配成功，会进行广播

IP

进行所谓的最长前缀匹配，而不是一个精准的 match

找不到的话不会进行广播，而是使用默认的端口

Longest Prefix Match

Example:

65.0.0.0/8 匹配 前 8 位为 65 的所有地址

所以65.14.24.120 会与之匹配

最常使用的技术实际上是

  1. Binary Tree

最长前缀匹配算法，也叫字典树其实

利用这个数据结构进行存储，可以有效决定地址匹配哪个条目

也可以使用

  1. Ternary Content Addressable Memory (TCAM)

Binary value + MASK

Generic

可以匹配任何地址的方法。通用 Ethernet 和 IP。

8. Packet Switching - How a Packet Switch Works (2)

数据如何被正确传输到正确端口并出站。

硬件结构需要支撑网络的软件功能：数据收发速度...

8.1. Input Queued Packet Switch

输入队列交换机

头部阻塞

Head Bolcking

虚拟输出队列

Virtual Output Queues

使用多个信道进行输出队列的分配

8.2. Properties of OQ Switches

  1. 工作保存：是指交换机在处理数据包时，不会浪费任何可用的资源（如带宽或处理能力）。只要还有数据包需要处理，交换机就会持续工作，直到所有数据包都被处理完毕。

  2. 吞吐量最大化：是指单位时间内交换机能够成功处理的数据量。OQ Switches 通过优化数据包的调度和处理方式，能够实现最大化的吞吐量，即使在高负载情况下也能保持高效运行。

  3. 延迟最小化：是指数据包从进入交换机到离开交换机所需的时间。OQ Switches 通过优化数据包的排队和调度策略，能够显著减少数据包的等待时间，从而实现最小化的延迟。

保持一定的 Load 让系统保持最高效率（最少 delay）

交通路口的例子，左转的车辆进入阻塞缓存区，直到直行车辆走完后才能走

9. Packet Switching - Strict Priorities and Guaranteed Flow Rates

回顾一下分组输出。总的来说有两个机制要点：先进先出 + 缓冲队列

  • Strict Priorities

  • Guaranteed Flow Rates

9.1. FIFO is a free for all

先进先出对于不均等数据流来说是一个 bad behavior...

数据从 A 会进行 data 的分组发送，如果 packets 被分到两个速度差异过大的组，那么实际上会造成输出端的拥堵？

所以这里需要设计一个 优先输出队列

9.2. Strict Priorities

IP: ToS Type of Server

在这个系统中，输出会一直服务 High Priorities...直到其空，再区服务 Low Priorities

但是 low 在这时候有可能会 killed...所以这样的情况一般适用于 high 较少时

9.3. Weighted Priorities

High 的权重是 Low 的两倍时...这时候 H 的输出速度也是 Low 的两倍，这样两边都可以涉及。

当然权重可以自己设定，管道数量也可以自己设定。 - 这样的时候使用遍历的策略，“round”可以很好使得输出的序列按照想法输出。

数据包其实会被分为比特进行发送，比特后有一个 EOP 标记 End of Packet...在输出的地方会再进行重新组合。

9.4. A practical way to do it

每个数据包具有自己的开始时间和结束时间。

根据开始和结束时间，引入一个调度器，可以服务于数据序列之间的调度

Weight Fair Queue...

10. Packet Switching - Guaranteed Delay

10.1. Intuition

根据端到端延迟公式：

前两项为网络固定因素，而最后一项无法控制。

下面假设我们已经知道：

  • 队列的缓冲区大小 Buffer Size

10.2. One Queue

队列的时间演变模型。

仍然记得如何判断延迟的大小：A(t) - D(t)

所以我们如果想要让队列能够不溢出缓冲区，要控制好输入的速度

10.3. Constraining Traffic

(σ, ρ) constrained arrivals and minimum service rate

leaky-bucket regulator

  • σ（sigma）：表示数据流的最大突发量，即在短时间内允许的最大数据量。

  • ρ（rho）：表示数据流的平均速率，即单位时间内允许通过的最大数据量。

PreviousUnit 2. TransportNextUnit 4. Control Congestion

Last updated