图像处理

图像处理

第二章 数字图像基础

人类的视觉感知系统

  • 视觉是人类最高级的感知器官

  • 然而人类感知只限于电磁波谱的视觉波段,成像机器则可以覆盖几乎全部电磁波谱

  • 研究图像处理首先要了解人类的视觉感知系统

人的视觉过程

光刺激——视网膜接收——视网膜神经处理——视觉通道——大脑皮层处理(存储参考图像、信息处理、特征提取、决策、描述)并响应

图像感知和获取

传感器类型:

  • 单个传感器

    优点:精度高、成本低

    缺点:速度慢

  • 带状传感器

    优点:可获得物体截面图像、成本较低

    缺点:速度慢

  • 传感器阵列

    各类图像都是由“照射”源和形成图像的“场景”元素对光能的反射或吸收相结合而产生的。

简单的图像形成模型

当用数学方法描述图像信息时,通常着重考虑它的点的性质。例如一副图像可以被看作是空间各个坐标点的结合。它的最普通的数学表达式为:

其中,$(x,y,z)$是空间坐标,$\lambda$是波长,$t$是时间,$I$是图像强度。这样一个表达式可以代表一副活动的、彩色的、立体的图像。

当研究的是静止图像时,上式与时间$t$无关;当研究的是单色图像时,显然与波长$\lambda$无关;对于平面图像则与坐标$z$无关。因此,对于静止的、平面的、单色的图像来说其数学表达式可简化为:

人们所感受到的图像一般都是由物体反射的光组成。函数$f(x,y)$可由两个分量来表示:

  1. 入射到观察场景的光源总量$i(x,y)$

  2. 场景中物体反射光的总量$r(x,y)$

$i(x,y)$的性质取决于照射源,而$r(x,y)$取决于成像物体的特性。反射分量$r(x,y)$限制在0(全吸收)和1(全反射)之间。

$i(x,y)$的某些典型值:在晴朗的白天,太阳在地球表面产生的照度超过90000lm/m2。在有云的情况下,这个数值下降到1000lm/m2。在晴朗的夜晚,满月情况下大约为0.1lm/m2的照度。

$r(x,y)$的某些典型值:黑天鹅绒为0.01,不锈钢为0.65,白色墙为0.80

Intrinsic image decomposition 本征图像分解

图像的数字化

大多数传感器的输出是连续电影波形。为了产生一副数字图像,需要把连续的感知数据转换为数字形式。所谓的图像数字化是指将模拟图像经过离散化之后,得到用数字表示的图像。

  • 取样:

    将在空间上连续分布的图像转换成离散的取样点(即像素)集的操作。由于图像是二维分布的信息,所以取样是在x轴和y轴两个方向上进行。

    取样时注意:取样间隔的选取。取样间隔取得不合适除了画面出现马赛克之外,还会发生频率的混合现象。

  • 量化:

    将各个像素所含的明暗信息离散化后用数字来表示,称为图像的量化。一般的量化值用整数表示。充分考虑到人眼的识别能力后,目前非特殊用途的图像均为8 bit量化,即用0~255描述“黑~白”

空间和灰度级分辨率

取样值是决定一副图像空间分辨率的主要参数,空间分辨率是图像中可辨别的最新细节。

  • 在取样时,若横向的像素数(列数)为M ,纵向的像素数(行数)为N,则图像总像素数为 M * N 个像素。 一般来说,采样间隔越大,所得图像像素数越少,空间分辨率低,质量差,严重时出现马赛克效应;采样间隔越小,所得图像像素数越多,空间分辨率高,图像质量好,但数据量大。

灰度级分辨率是指在灰度级别中可分辨的最小变化,由于硬件方面的要求,灰度级数通常是2的整数幂

  • 量化等级越多,所得图像层次越丰富,灰度分辨率高,图像质量好,但数据量大

  • 量化等级越少,会出现假轮廓现象,图像质量变差,但数据量小

像素之间的邻域关系

4邻域:

  • 像素$p(x,y)$的4邻域是$(x+1,y),(x-1,y),(x,y+1),(x,y-1)$

  • 用$N_4(p)$表示像素p的4邻域

D邻域:

  • 像素$p(x,y)$的D邻域是对角上的点$(x+1,y+1),(x+1,y-1),(x-1,y+1),(x-1,y-1)$

  • 用$N_D(p)$表示像素p的D邻域

8邻域:

  • $N_8(p)=N_4(p)+N_D(p)$

图像的放大与缩小

  • 最近邻

    设i+u, j+v(i, j为正整数, u, v为大于零小于1的小数,下同)为待求像素坐标,则待求像素灰度的值 f(i+u, j+v)。

    如果(i+u, j+v)落在A区,即u<0.5, v<0.5,则将左上角像素的灰度值赋给待求像素,同理,落在B区则赋予右上角的像素灰度值,落在C区则赋予左下角像素的灰度值,落在D区则赋予右下角像素的灰度值。

    avatar

    最邻近元法计算量较小,但可能会造成插值生成的图像灰度上的不连续,在灰度变化的地方可能出现明显的锯齿状

  • 双线性插值

    简明版

彩色图像表示

光学原理解释色彩的形成:

可视光区的波长在400nm~780nm,当光谱采样限制到三个人类视觉系统敏感的红、绿、蓝光波段时,对这三个光谱带的光能量进行采样,就可以得到一副彩色图像。

彩色视觉是人眼对射入的可见光光谱的强弱及波长成分的一种感觉。

彩色模型

颜色的描述是通过建立彩色模型来实现的,不同的彩色模型对应于不同的处理目的。

各种不同的颜色模型之间可以通过数学方法转换。

CIE(国际照明委员会)在进行大量的色彩测试实验的基础上提出了一系列的颜色模型:

  • RGB模型:红、绿、蓝 三基色混合

  • HSI模型:色度(H, Hue)、饱和度(S, Saturation)、亮度(I, Intensity)

    HSI彩色模型比较适合于人用色调、饱和度、亮度描述被观察物体颜色的解释,对于开发基于彩色描述的图像处理方法是一个理性的工具。

    avatar

    • H表示色调,用 角度 表示。 反映了该颜色最接近什么样的光谱波长。 0度为红色,逆时针120度为绿色,顺时针120度为蓝色。

    • S表示饱和度,饱和度参数是色环的原点到彩色点的半径长度。在环的外围圆周是纯的或饱和的颜色,其饱和度值为1。在中心是中性(灰)色,即饱和度为0。

    • I表示光照强度或亮度,它确定了像素的整体亮度,而不管其颜色是什么。

  • YUV模型:亮度(Y)、色度(UV)

  • YCbCr模型:亮度(Y)、色度(CbCr)

CMYK色系:用于印刷行业,是一种减色系统,将从白光中滤出三种原色之后获得的颜色作为表色系的三原色CMY

C (cyan):青色/蓝绿色,从白色中滤去红色。

M (magenta):品红,从白色中滤去绿色。

Y (yellow):黄色,从白色中滤去蓝色。

彩色图像转变为灰度图像的处理称为彩色图像的灰度化处理。方法主要包括:最大值法、平均值法、加权平均值法。

  • 最大值法:将输入图像中的每个像素的R、G、B分量值的最大者赋给输出图像中对应像素的R、G、B分量的方法。用公式可表示为:

    $g_R(x,y)=g_G(x,y)=g_B(x,y)=max(f_R(x,y),f_G(x,y),f_B(x,y))$

  • 平均值法:将输入图像中的每个像素的R、G、B分量的算术平均值赋给输出图像中对应像素的R、G、B分量的方法。用公式可表示为:

    $g_R(x,y)=g_G(x,y)=g_B(x,y)=(f_R(x,y)+f_G(x,y)+f_B(x,y))/3$

  • 加权平均值法:人眼对绿光的亮度感觉仅次于白光,是三基色中最亮的,红光次之,蓝光最低。相关研究表明,当$\omega_G$=0.587、$\omega_R$=0.299、$\omega_B$=0.114时,得到的灰度化图像较合理,此时灰度化公式就变为:

    $g_R(x,y)=g_G(x,y)=g_B(x,y)=0.299\cdot f_R(x,y)+0.587\cdot f_G(x,y)+0.114\cdot f_B(x,y)$

第三章 空间域图像增强

背景知识

基本灰度变换

直方图处理

空间滤波基础

平滑空间滤波器

锐化空间滤波器

混合空间增强法

图像增强:

突出图像中的某些信息,同时削去不需要的信息。

图像在传输或处理过程中会引入噪声或使图像变得模糊,从而降低了图像质量,甚至淹没了特征,给分析带来了困难。

白噪声,使得图看上去不清晰。

https://www.zhihu.com/question/47681952

空间域处理:点处理(图像灰度变换、直方图均衡);邻域处理(线性、非线性平衡和锐化)

频域处理:高、低通滤波、同态滤波

https://blog.csdn.net/whuhan2013/article/details/53843974

空间域增强是指增强构成图像的元素,定义为:

$g(x,y)=T[f(x,y)]$

$f(x,y)$是输入图像

$g(x,y)$是输出图像

$T$是对$f$的一种操作,定义在$(x,y)$的邻域上

邻域:中心在$(x,y)$的正方形或矩形子图像

子图像中心从一个像素向另一个像素移动

基本灰度变换模型

灰度级变换函数:s=T(r)

T是一个1*1的矩阵,因此是点处理

三种基本类型:

  • 线性的(正比或反比)
  • 对数的(对数或反对数的)
  • 幂次的(n次幂和n次方根变换)

图像反转:$s=L-1-r$

对数变换:$s=clog(1+r)$

幂次变换:$s=cr^{\gamma}$

反转变换:

适于处理增强嵌入于图像暗色区域的白色或灰色细节,特别是当黑色面积占主导地位时。

生成灰度反转图像。

对数变换:

使一窄带低灰度输入图像映射为一宽带输出值

可以用于扩展图像中的暗像素

(可以在某个区间内将输出灰度值拉伸很快,将原本黑色的区域拉伸到右图的效果。傅立叶变换图的对数变换处理)

幂次变换:

幂次曲线中的$\gamma$值决定了是否把输入窄带暗值映射到宽带输出值还是把输入窄带亮值映射到宽带输出。

应用:$\gamma$校正

用幂次变换进行对比度增强

分段线性变换:

  1. 对比拉伸:扩展图像处理时灰度级的动态范围

    起点:

    终点:

    线性函数:

    阈值函数:

    对比拉伸:

  2. 灰度切割:提高特定灰度范围的亮度

    (相当于做了一个范围内的二值化处理)

  3. 位图切割:把数字图像分解成位平面(每一个位平面可以处理成一幅二值图像,即要么是0要么是255)

    高阶位如前4位包含视觉上很重要的大多数数据

    如果用8-bit表示,则分割成8张位图

    位图切割目的是提取关键信息

直方图处理:

直方图:$h(r_k)=n_k$

其中,$r_k\in [0,L-1]$:灰度级;$n_k$:灰度级为$r_k$的像素个数

即,统计每个像素值(灰度级)在像素点出现的次数

归一化直方图:(L=256?)

$p_r(r_k)=\frac{n_k}{n},0\leq p_r\leq 1,r_k=0,1,…,L-1,\sum_{r_k=0}^{L-1}p_r(r_k)=1
$

其中 n 是像素个数,$p_r(r_k)$是原始图像灰度分布的概率密度函数

如果将$r_k$归一化到[0,1]之间,则$r_k$可以看作区间[0,1]的随机变量。

当直方图均匀分布时,图像最清晰。

直方图处理:

假设原图的灰度值变量为r,变化后新图的灰度值变量为s,希望寻找一个灰度变换函数$T: s=T(r)$,使得概率密度函数$p_r(r)$变换成希望的概率密度函数$p_s(s)$

灰度变换函数$T(r)$应该满足:

(1) $T(r)$在区间[0,1]中单调递增且单值(对一个自变量只有一个因变量的取值,多值如椭圆、圆)

(2) $\forall r\in [0,1]$,有$T(r)\in [0,1]$

直方图是近似的概率密度函数,所以用离散灰度级进行变换时很少得到完全平坦的结果。

变换后灰度级减少,即出现灰度“简并”的现象,造成了灰度级层次的丢失。

直方图均衡化的缺陷:

不能用于交互方式的图像增强应用,因为只产生唯一一个结果。

直方图规定化:

将原始图像的直方图转换为期望的直方图的形状

利用均衡化原理

  • 设 ${r_k}$ 是原图像的灰度级

  • ${z_k}$ 是符合指定直方图结果图像的灰度级

目标:找到一个灰度变换函数:$z_k=T(r_k),r\rightarrow z$

算法思路:

$p_r(r)$:原图的灰度密度函数

$p_z(z)$:希望得到的灰度密度函数

分别对$p_r(r),p_z(z)$作直方图均衡化处理,有:

$s=T(r)=\int_0^r p_r(r)dr,r\in[0,1]$

$v=G(z)=\int_0^r p_z(z)dz,z\in[0,1]$

经过变换得到的灰度s和v,

直方图均衡化是一种简单有效的图像增强技术,通过改变图像的直方图来改变图像中各像素的灰度,主要用于增强动态范围偏小的图像的对比度。原始图像由于其灰度分布可能集中在较窄的区间,造成图像不够清晰。例如,过曝光图像的灰度级集中在高亮度范围内,而曝光不足将使图像灰度级集中在低亮度范围内。采用直方图均衡化,可以把原始图像的直方图变换为均匀分布(均衡)的形式,这样就增加了像素之间灰度值差别的动态范围,从而达到增强图像整体对比度的效果。换言之,直方图均衡化的基本原理是:对在图像中像素个数多的灰度值(即对画面起主要作用的灰度值)进行展宽,而对像素个数少的灰度值(即对画面不起主要作用的灰度值)进行归并,从而增大对比度,使图像清晰,达到增强的目的。

对一幅灰度图像,其直方图反映了该图像中不同灰度级出现的统计情况。

自然语言处理复习汇总(南京大学)-转载

转载于Github

自然语言处理复习汇总(南京大学)

标签(空格分隔): 自然语言处理

参考书籍:统计自然语言处理—宗成庆

[TOC]

统计语言模型

N-Gram

N-1阶马尔可夫链我们称之为N元语言模型

$Count(w_{i-1}w_i)$由于稀疏性,值可能等于0.从而导致整个句子的概率都等于0

进行平滑处理:

线性平滑:

laplace 平滑:

Read more

编译原理

词法分析

词法分析的主要任务:

从左向右逐行扫描源程序的字符,识别出各个单词,确定单词的类型,并将识别出的单词转换成统一的机内表示——词法单元token形式。

token: <种别码,属性值>

e.g. 词法分析后得到的token序列:

输入:while(value != 100) {num++;}

输出:

  1. while < WHILE, - >
  2. ( < SLP, - >
  3. value < IDN, value >
  4. != < NE, - >
  5. 100 < CONST, 100 >
  6. ) < SRP, - >
  7. { < LP, - >
  8. num < IDN, num >
  9. ++ < INC, - >
  10. ; < SEMI, - >
  11. } < RP, - >
Read more

网络攻防

网络的漏洞和攻击在描述每一协议层的漏洞和攻击的架构时可分为4类:

  • 基于头部的漏洞和攻击:修改了协议头部,或使头部无效。
  • 基于协议的漏洞和攻击:数据包是有效的,但不能直接使用。
  • 基于验证的漏洞和攻击:修改了发送方和接收方的识别标志。
  • 基于流量的漏洞和攻击:借助流量实施攻击。

定义

  • 应用:指允许用户连接网络并执行某项任务的计算机程序。
  • 攻击者:指利用网络攻击计算机系统、网络或其他连接在互联网中的设备的个人或群体。
  • 黑客:即攻击者。
  • 主机:连接到网络上的计算机。
  • 互联网:互连众多网络设备的全球网络的集合。
  • 网络:一组互连的设备并可以相互通信。
  • 网络设备:连接到网络上的设备,泛指包括主机或计算机在内的所有设备,这些设备使网络可以运行起来。
  • 目标:黑客试图攻击的设备、主机、用户或目标。
  • 用户:利用网络执行计算机程序的个人,或一般的计算机用户。
Read more

Logging

Introduction

Log is used to record the history of database changes securely.

The transaction is the unit of execution of database operations.

In the typical embedded SQL system, transactions begin as soon as operations on the database are executed and end with an explicit COMMIT or ROLLBACK (“abort”) command.

How transactions interact with the database? There are 3 address spaces that interact in important ways:

  1. The space of disk blocks holding the database elements.
  2. The virtual or main memory address space that is managed by the buffer manager.
  3. The local address space of the transaction.

事务的定义:

  • 一个数据库操作序列
  • 一个不可分割的工作单位(atomic)
  • 恢复和并发控制的基本单位

The SQL statement COMMIT causes a transaction to complete, database modifications are now permanent in the database.

The SQL statement ROLLBACK also causes the transaction to end, but by aborting. Having no effects on the database. It caused by failures like division by 0 or a constraint violation.

ACID

ACID transactions are:

  • Atomic: Either the whole or the none of the transaction is done.
  • Consistent: Database constraints reserved. For example, a + b = 10, if a changed, b also changes.
  • Isolated: It appears to the user that only one process is executing at one time.
  • Durable: Effects of a process survive a crash.

Correctness Principle

If a transaction executes in the absence of any other transactions or system errors, and it starts with the database in a consistent state, then the database is also in a consistent state when the transaction ends.

State: a DB has state means a value for each of its elements.

Consistent state: certain state satisfies all constraints.

Another description of correctness principle:

  1. a transaction is atomic, and the complete execution of a single transaction is from one consistent state to another consistent state. That is to say, if only part of a transaction executes, then db state may not be consisitent.
  2. multiple transactions execute at the same time may lead to inconsistency unless using concurrecy control.

So, a transaction is a collection of actions that preserve consistency.

If T starts with consistent state and executes in isolation, then T leaves with consistent state.

Three address spaces:

  1. Local address space of transaction (Memory)
  2. Buffer (Memory)
  3. Space of disk

INPUT(X): block containing X disk to buffer/memory

OUTPUT(X): block containing X buffer to disk

READ(X, t): do input(X) if necessary; read value of x in buffer to t in local address space of transaction.

WRITE(X, t): do output(X) if necessary; write t in local address space of transaction to the value of x in buffer.

Undo Logging

: indicates that transaction T has begun

: transaction T has completed successfully and will make no more changes to the database elements

: transcation T could not complete successfully

only update record:

  • transaction T has changed database element X and its former value was v

The change reflected by an update record normally occurs in memory, not disk.

  • the log record is a response to a WRITE action, not an OUTPUT action

undo log must be written to disk in the following order:

  1. The log records that indicating changed database elements.
  2. The changed database elements themselves.
  3. The COMMIT log record.

So we got 2 rules:

U1:

U2:

In order to force log records to disk:

  • The log manager needs a flush-log command that tells the buffer manager to copy to disk any log blocks that have not previously been copied to disk.
  • FLUSH LOG

When a transaction begins, a is written to the log memory; after a series of actions like INPUT or READ (or probably no actions at all), a WRITE command comes, and a is written to the log memory. After the last WRITE operation, it’s time to FLUSH LOG. After flushing log, and are written to the disk. That is to say, before flushing log, the previous logs are still in the log memory.

Then, execute OUTPUT(A), OUTPUT(B), … Only after the value of A, B, … is written to disk, a log can be written to the log memory.

Then FLUSH LOG (after execute OUTPUT B, let’s assume that B is the last one) and is written to disk.

Recovery Rules

Incomplete transactions must be undone!
Scan the undo log from the end:

  • Let S = set if transactions with in log but no or record in log

  • For each in log, in reverse order (latest to earliest) do:

    If Ti in S then WRITE(X, v), OUTPUT(X)

  • For each Ti in S do: write to log

Simple checkpointing

In a simple checkpoint,

  1. Stop accepting new transactions.

  2. Wait until all currently active transactions commit or abort and have written a COMMIT or ABORT record on the log.

  3. Flush the log to disk.

  4. Write a log record , and flush the log again.

  5. Resume accepting transactions.

Problem: must shut the system while the ckpt is being made

Nonquiescent checkpointing

Nonquiescent checkpointing

  1. Write a log record

    and flush the log.

  2. Wait until all of T1, …, TK commit or abort, but do not prohibit other transactions from starting

  3. When all of T1, …, TK have completed, write a log record and flush the log

Two cases:

  1. If we first meet an , then we know that all incomplete transactions began after the previous . Scan backwards as far as

  2. If we first meet an , then the crash occurred during the checkpoint

A general rule:

Once an has been written to disk, we can delete the log prior to the previous .

Redo Logging

Problem for undo logging: First write all its changed data to disk then commit a transaction — too many disk I/Os.

Save disk I/Os: Let changed data reside only in main memory for a while.

Redo logging requires the COMMIT record appear on disk before any changed values reach disk.

Redo logging rules

R1: Before modifying any database element X on disk, it is necessary that all log records pertaining to this modification of X, including both the update record and the record, must appear on disk.

  1. The log records indicating changed db elements.
  2. The COMMIT log record.
  3. The changed db elements themselves.

First COMMIT then OUTPUT.

To recover, using a redo log, after a system crash:

  1. Identify the committed transactions.

  2. Scan the log forward from the beginning. For each log record <T, X, v> encountered:

    a) If T is not a committed transaction, do nothing.

    b) If T is committed, write value v for database element X. (That’s because no COMMIT no values on disk)

  3. For each incomplete transaction T, write an record to the log and flush the log.

The steps to perform a nonquiescent checkpoint of redo log:

  1. Write a log record , where T1, …, Tk are all the active (uncommitted) transactions, and flush the log

  2. Write to disk all database elements that were written to buffers but not yet to disk by transactions that had already committed when the START CKPT record was written to the log

  3. Write an record to the log and flush the log

Undo/redo Logging

The update log record:

  • the former value is v, the new value is w

UR1: Before modifying any db element X on disk because of changes made by some transaction T, it is necessary that the update record appear on disk.

UR2: A record must be flushed to disk as soon as it appears in the log.

The undo/redo recovery policy is:

  1. Redo all the commited transactions in the order earliest-first.
  2. Undo all the incomplete transactions in the order latest-first.

系统故障造成数据库不一致状态的原因

未完成事务对数据库的更新已写入数据库

已提交事务对数据库的更新还留在缓冲区没来得及写入数据库

恢复方法

\1. Undo 故障发生时未完成的事务

\2. Redo 已完成的事务

系统故障的恢复由系统在重新启动时自动完成,不需要用户干预

系统故障的恢复步骤

  1. 正向扫描日志文件(即从头扫描日志文件)

重做(REDO) 队列: 在故障发生前已经提交的事务

这些事务既有BEGIN TRANSACTION记录,也有COMMIT记录

撤销 (Undo)队列:故障发生时尚未完成的事务

这些事务只有BEGIN TRANSACTION记录,无相应的COMMIT记录

  1. 对撤销(Undo)队列事务进行撤销(UNDO)处理

反向扫描日志文件,对每个UNDO事务的更新操作执行逆操作

即将日志记录中“更新前的值”写入数据库

  1. 对重做(Redo)队列事务进行重做(REDO)处理

正向扫描日志文件,对每个REDO事务重新执行登记的操作

即将日志记录中“更新后的值”写入数据库

A nonquiescent checkpoint is somewhat simpler for undo/redo logging than for other logging methods

  1. Write a record to the log, where T1, …, Tk are all the active transactions, and flush the log

  2. Write to disk all the buffers that are dirty; i.e., they contain one or more changed database elements. Unlike redo logging, we flush all dirty buffers, not just those written by committed transactions

  3. Write an record to the log and flush the log

Archiving

Maintaining a copy of the db separate from the db itself.

  • shut down the db for a while
  • make a backup copy on some storage medium
  • Store the copy in some remote secure location

Two levels of archiving:

  1. a full dump, in which the entire db is copied
  2. an incremental dump, in which only those db elements changed since the previous full or incremental dump are copied

Concurrency Control

The process of assuring that transactions preserve consistency when executing simultaneously.

The scheduler takes read/write requests from transactions and executes them in buffers or delay them.

Serial and Serializable Schedules

A schedule is serial if its actions consist of all the actions of one transaction, then all the actions of another transaction, and so on.

The correctness principle tells us that every serial schedule will preserve consistency of the db state.

A schedule is serializable if there is a serial schedule S’ such that for every initial db state, the effects of S and S’ are the same.

Conflicts: A pair of consecutive actions in a schedule such that, if their order is interchanged then the behaviour of at least one of the transactions involved can change.

数据链路层

多路访问控制(MAC)协议

两类链路:

  • 点对点链路:拨号接入的PPP,以太网交换机与主机间的点对点链路
  • 广播链路(共享介质):早期的总线以太网,HFC的上行链路,802.11无限局域网

单一共享广播信道

两个或两个以上节点同时传输:干扰,产生冲突,导致接受失败

多路访问控制协议(multiple access control protocol)

  • 采用分布式算法决定节点如何共享信道,即决策节点何时可以传输数据
  • 必须基于信道本身,通信信道共享协调信息

MAC协议分类

  1. 信道划分 (channel partitioning) MAC协议
    • 多路复用技术
    • TDMA,FDMA,CDMA,WDMA等
  2. 随机访问 (random access) MAC协议
    • 信道不划分,允许冲突
    • 采用冲突“恢复”机制
  3. 轮转 (taking turns) MAC协议
    • 节点轮流使用信道(保证节点在使用信道时不冲突,同时在使用的时候用的是信道的全部带宽)

信道划分MAC协议

TDMA: time division multiple access

  1. “周期性”接入信道
  2. 每个站点在每个周期占用固定长度的时隙(这里的长度是指分组传输时间)
  3. 未用的时隙空闲(idle)
  4. 例如,6-slot的LAN,1、3、4传输分组,2、5、6空闲

FDMA: frequency division multiple access

  1. 信道频谱划分为若干频带(frequency bands)
  2. 每个站点分配一个固定的频带
  3. 没有传输数据的频带空闲
  4. 例如,6站点LAN,1、3、4频带传输数据,2、5、6频带空闲

随机访问MAC协议

当节点要发送分组时,利用信道全部数据速率R发送分组,没有事先的节点间协调。

会发生冲突。

随机访问MAC协议需要定义:如何检测冲突、如何从冲突中恢复(通过延迟重传)

典型的随机访问MAC协议:

  • 时隙(sloted)ALOHA
  • ALOHA
  • CSMA, CSMA/CD, CSMA/CA

时隙ALOHA协议

假定:

  • 所有帧大小相同
  • 时间被划分为等长的时隙(每个时隙可以传输1个帧)
  • 节点只能在时隙开始时刻发送帧
  • 节点间时钟同步
  • 如果2个及以上的节点在同一时隙发送帧,则检测到冲突

运行:

  • 当节点有新的帧时,在下一个时隙(slot)发送
  • 如果无冲突:该节点可以在下一个时隙继续发送新的帧
  • 如果冲突,该节点在下一个时隙以概率p重传该帧,直至成功

优点:

  • 单个节点活动时,可以连续以信道全部速率传输数据
  • 高度分散化:只需同步时隙
  • 简单

缺点:

  • 冲突,浪费时隙
  • 时钟同步
  • 空闲时隙
  • 节点也许能以远小于分组传输的时间检测到冲突

非时隙ALOHA

更加简单,无需同步

当有新的帧生成时,立即发送

因此比时隙ALOHA协议更差。

CSMA协议

载波监听多路访问协议CSMA(carrier sense multiple access)

发送帧之前,监听信道(载波):

  • 信道空闲:发送完整帧
  • 信道忙:推迟发送

    • 1-坚持CSMA
    • 非坚持CSMA
    • P-坚持CSMA
  • 冲突可能仍然发生:存在信号传播延迟

CSMA/CD协议

CSMA/CD: CSMA with Collision Detection

  • 短时间内可以检测到冲突
  • 冲突后传输中止,减少信道浪费

冲突检测:

  • 有线局域网易于实现:测量信号强度,比较发射信号与接收信号
  • 无线局域网很难实现:接收信号强度淹没在本地发射信号强度下

网络带宽:R bps

数据帧最小长度:$L_min$ (bits)

信号传播速度:V(m/s)

“边发边听,不发不听”

主机A、B之间的距离是$d_{max}$,A向B发送数据帧,快到达B时,B又向A发送了一个数据帧,两者在靠近B的地方相遇,于是发生了冲突。A发送的数据帧到达B时,B检测到了冲突,但此时B发送的数据帧还未到达A,因此A还没有检测出冲突。最后,两者都检测到冲突时,用了$2d_{max}/V$的时间。

满足:$L/R >= 2d_{max}/V$

那么:

$L_{min}/R >= 2d_{max}/V$

$L_{min}/R = RTT_{max}$

$t_{prop}$趋近于0或$t_{trans}$趋近于∞时,效率趋近于1.

远优于ALOHA,并且简单、分散。

ARP协议

MAC地址

32位IP地址:

  • 接口的网络层地址
  • 用于标识网络层(第3层)分组,支持分组转发

MAC地址(或称LAN地址,物理地址,以太网地址)

  • 作用:用于局域网内标识一个帧从哪个接口发出,到达哪个物理相连的其他接口
  • 48位MAC地址(用于大部分LANs),固化在网卡的ROM中,有时也可以软件设置
  • 将48bits分为6个字节,16进制表示,e.g.: 1A-2F-BB-76-09-AD

局域网中的每块网卡都有一个唯一的MAC地址。

MAC地址由IEEE统一管理与分配。

网卡生产商购买MAC地址空间(前24比特),后24比特生产商依次分配。

类比:

  • MAC地址:身份证号
  • IP地址:邮政地址
  • MAC地址是“平面”地址,可”携带“,可以从一个LAN移到另一个LAN
  • IP地址是层次地址,不可“携带”,IP地址依赖于节点连接到哪个子网

ARP:地址解析协议

在同一个LAN内,如何在已知目的接口的IP地址前提下确定其MAC地址?

ARP表:LAN中每个IP节点(主机、路由器)维护一个表

  • 存储某些LAN节点的IP/MAC地址映射关系。如:
  • 存活时间TTL(time to live):经过这个时间后,该映射关系会被遗弃(典型时间是20min)

ARP协议:同一局域网内

  • A想要向同一局域网中的B发送数据报,但B的MAC地址不在A的ARP表中
  • A广播ARP查询分组,其中包含B的IP地址。LAN中所有节点都会接收到ARP查询。
  • B也接收到了,IP地址匹配成功,B向A应答B的MAC地址。利用单播帧向A发送应答。
  • A在自己的ARP表中缓存B的IP-MAC地址对,直至超时。超时后,再次刷新。
  • ARP是“即插即用”协议,节点自主创建ARP表,无需干预。

约束与触发器

完整性约束

删除/更新具有引用关系的表时,有以下操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
-- 被引用的行禁止删除
on delete restrict

-- 级联,被引用行删除时,引用行也一起删除;即子表里的行跟着父表里相应的行一起删除
on delete cascade

-- 被引用行删除时,引用行不做什么处理
no action

-- 被引用行禁止更新
on update restrict

-- 被引用行更新时,引用行自动更新
on update cascade


create table so_items(
item_id int not null,
so_id int references so_headers(id) on delete restrict,
product_id int,
net_price numeric,
primary key(item_id,so_id)
);

create table so_items(
item_id int not null,
so_id int references so_headers(id) on delete cascade,
product_id int,
net_price numeric,
primary key(item_id,so_id)
);

外键约束的几种方法:

方法1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
create table so_headers(
id serial primary key,
customer_id int,
ship_to varchar(255)
);

-- 在创建表时,作为外键的列后面直接依赖父表列
create table so_items(
item_id int not null,
so_id int references so_headers(id),
product_id int,
net_price numeric,
primary key(item_id,so_id)
);

方法2:

1
2
3
4
5
6
7
8
9
10
-- 创建表时,在末尾指定外键约束
create table so_items(
item_id int not null,
so_id int,
product_id int,
net_price numeric,
primary key(item_id,so_id),
foreign key(so_id) references so_headers(id)
);
-- 【注】:如果没有指定外键别名,则默认的外键别名为:"表名_列名_fkey"

方法3:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
-- 创建表时,在末尾指定外键约束,并且指定外键别名;so_id_fkey
create table so_items(
item_id int not null,
so_id int,
product_id int,
net_price numeric,
primary key(item_id,so_id),
constraint so_id_fkey foreign key(so_id) references so_headers(id)
);


-- 多个主键建立外键约束
create table child_table(
c1 int primady key,
c2 int,
c3 int,
primary key(c2,c3) references 父表(p1,p2)
);

方法4:

1
2
3
4
5
6
-- 修改表添加外键约束
alter table 表名 add constraint 外键别名 foreign key(列名) references 父表(列名);


-- 删除外键约束
alter table 表名 drop constraint 外键别名;

DEFERRABLE

推迟约束

触发器

触发器(trigger)是用户定义在关系表上的由事件驱动调用函数的机制。

触发器比CHECK更灵活,可以实施各种复杂的检查和操作,具有更精细和更强大的数据保护能力。

在创建触发器之前,必须首先创建触发器函数,触发器函数的语法格式是:

1
2
3
4
5
6
CREATE FUNCTION function_name() RETURNS TRIGGER AS $$
DECLARE 变量声明;
BEGIN
函数执行代码
END;
$$ LANGUAGE plpgsql;

触发器中有两对前是函数头部。触发器函数定义的头部RETURNS后面只能是TRIGGER,并且触发器函数不能带任何参数。

两对$$之间是函数体。包括DECLARE部分的变量声明以及BEGIN和END之间的函数执行代码。DECLARE部分是可选的。

由于PG允许使用各种语言比如PL/pgSQL,C,Python来编写函数,所以第二对$$之后是对函数编写语言的说明。这里是PL/pgSQL。

触发器函数创建后,使用CREATE TRIGGER命令创建触发器。

1
2
3
4
5
CREATE TRIGGER name {BEFORE|AFTER} {event [OR...]}
ON TABLE YYY
[FOR [EACH] {ROW|STATEMENT}]
[WHEN {condition}]
EXECUTE PROCEDURE function_name();

{event [OR…]}中,{}里面是一个或多个用OR分隔的事件列表。这里的事件包括数据库的数据修改操作,比如INSERT、DELETE或UPDATE等命令。

BEFORE|AFTER的意思是触发器可以分为BEFORE和AFTER触发器,分别在操作完成前和操作完成后执行触发器函数。

ON TABLE后面给出触发器所在表的表名。

触发器可以按行或按语句触发,也就是行级触发器和语句级触发器。

行级:[FOR [EACH] {ROW|STATEMENT}]

语句级:[FOR [EACH] {STATEMENT}]

行级触发器的触发器函数为触发语句影响的每一行执行一次。

语句级触发器的触发器函数为每条触发语句执行一次。

假设表examiner有10000行,定义了如下的UPDATE触发器:

1
UPDATE examiner SET erage = erage + 1;

如果是语句级触发器,则执行完该语句后,触发动作只发生1次;如果是行级触发器,则执行10000次。

触发器必须返回一个NULL或者一个元组类型的变量。

语句级触发器应返回NULL。

行级after触发器的值总是被忽略,可以返回null。

行级before触发器的返回值不同,对触发器操作的影响也不同。

如果返回NULL则忽略该触发器的行级操作,其后的触发器也不会执行。

如果返回非NULL,则返回的行将成为被插入或更新的行。

如果是行级触发器,可以在触发器函数中使用NEW和OLD引用UPDATE/INSERT事件之后的新值和UPDATE/DELETE事件之前的旧值。

插入examinee表的考号长度必须为10位:

创建触发器函数:

1
2
3
4
5
6
7
8
9
10
CREATE FUNCTION examineeid() RETURNS TRIGGER AS $examineeid$
BEGIN
IF(CHAR_LENGTH(new.eeid)<>10) THEN
RAISE EXCEPTION '格式错误';
RETURN NULL;
ELSE
RETURN NEW;
END IF;
END
$examinee$ LANGUAGE plpgsql;

NEW代表INSERT或UPDATE操作产生的新的数据行

创建触发器:

1
2
CREATE TRIGGER examineeid_insert BEFORE INSERT ON examinee
FOR EACH ROW EXECUTE PROCEDURE examineeid();

三种:

1.DEFERRABLE INITIALLY DEFERRED

2.DEFERRABLE INITIALLY IMMEDIATE

3.NOT DEFERRABLE

1
Copy"subject_iddddd" INTEGER REFERENCES "Subjects" ("id") DEFERRABLE INITIALLY IMMEDIATE

注1:IMMEDIATE 会在每一个语句执行后进行约束检查,DEFERRED 则只会在事务结束时才检查约束。(DEFERRED 只是推迟检查而不是不检查)

注2:此设置仅影响 UNIQUE,PRIMARY KEY,REFERENCES (外键)和 EXCLUDE 约束

1
SET CONSTRAINTS { ALL | name [, ...] } { DEFERRED | IMMEDIATE }

注1:NOT DEFERRABLE 来说,SET CONSTRAINTS 不生效。

注2:SET CONSTRAINTS ALL 更改所有 DEFERRABLE 约束。

网络层

网络层服务

从发送主机向接收主机传送数据段

发送主机:将数据段封装到数据报中。

接收主机:向传输层交付数据段。

每个主机和路由器都运行网络层协议。

路由器检验所有穿越它的IP数据报的头部域。

网络层核心功能

转发与路由

转发(forwarding):将分组从路由器的输入端口转移到合适的输出端口。

每个路由器维护一张转发表,转发表确定本路由器如何转发分组。

转发表的内容:地址-输出链路,如0100-3, 0101-2, 0111-2, 1001-1.

取出收到的数据报的地址信息,然后查转发表得到输出链路。

路由(routing):确定分组从源到目的经过的路径。

如何得到路由信息?

网络层设备都会运行一些路由协议,或路由算法(routing algorithms),根据路由算法确定通过网络的端到端路径。

连接的建立

数据分组传输之前两端主机需要首先建立虚拟/逻辑连接,网络设备(如路由器)参与连接的建立。

网络层连接与传输层连接的对比:

  • 网络层连接:两个主机之间的连接,并且在路径上的每个网络层设备都要参与建立连接。
  • 传输层连接:两个应用进程之间的连接(端到端的连接,对中间网络设备透明)。

网络层为发送端(主机)到接收端(主机)的数据报传送”通道(channel)”提供怎样的服务模型(service model)?

不同的网络架构(Network Architecture)提供的服务模型是不一样的。例如Internet提供的是best effort服务模型,不保障Bandwidth, Loss, Order或Timing,通过数据是否丢失来判断拥塞(congestion)。ATM的服务模型有CBR,VBR,ABR,UBR。

网络层服务模型

  • 无连接服务(connection-less service):
    • 不事先为系列分组的传输确定传输路径
    • 每个分组独立确定传输路径
    • 不同分组可能传输路径不同
    • 数据报网络(datagram network)
  • 连接服务(connection service):
    • 首先为系列分组的传输确定从源到目的经过的路径(建立连接)
    • 然后沿该路径(连接)传输系列分组
    • 系列分组传输路径相同
    • 分组传输顺序可以保证
    • 传输结束后拆除连接
    • 虚电路网络(virtual-circuit network)

虚电路网络和数据报网络

虚电路网络

数据报网络和虚电路网络是典型的两类分组交换网络

数据报网络提供网络层无连接服务。

虚电路网络提供网络层连接服务。

类似于传输层的无连接服务(UDP)和面向连接服务(TCP),但是网络层服务:

  1. 是主机到主机的服务
  2. 网络核心实现(传输层是端到端实现)

虚电路:一条从源主机到目的主机,类似于电路的路径(逻辑连接)。

  • 分组交换
  • 每个分组的传输利用链路的全部带宽
  • 源到目的路径经过的网络层设备共同完成虚电路功能

  • 通信过程:呼叫建立(call setup)——数据传输——拆除呼叫

  • 每个分组携带虚电路标识(VCID),而不是目的主机地址
  • 虚电路经过的每个网络设备(如路由器),都要维护每条经过它的虚电路的连接状态
  • 链路、网络设备资源(如带宽、缓存等)可以面向VC进行预分配
    • 预分配资源 = 可预期服务性能
    • 如ATM的电路仿真(CBR)

每条虚电路包括:

  1. 从源主机到目的主机到一条路径

  2. 虚电路号(VCID),沿路每段链路一个编号

    链路带宽越大,允许建立的虚电路的数量就越大。

    同一条虚电路在每一段链路上的VCID可能是不一样的。

  3. 沿路每个网络层设备(如路由器),利用转发表记录经过的每条虚电路。

沿某条虚电路传输的分组,携带对应虚电路的VCID,而不是目的地址。

同一条VC,在每段链路上的VCID通常不同:

  • 路由器转发分组时依据转发表改写/替换虚电路号

虚电路信令协议(signaling protocols)

用于VC的建立、维护与拆除:路径选择

应用于虚电路网络:如ATM、帧中继(frame-relay)网络等

目前的Internet不采用。

初识呼叫——呼叫到达——接受呼叫——呼叫建立——数据流开始——接收数据

通信结束后,也通过虚电路信令协议进行呼叫的拆除。

数据报网络

网络层无连接

每个分组携带目的地址

路由器根据分组的目的地址转发分组:

  • 基于路由协议/算法构建转发表
  • 检索转发表
  • 每个分组独立选路
  • 每个分组走的路径可能不一样,因为如果在传输过程中路由器更新了转发表,那么后面的分组就会走新的路径

数据报中含有目的主机的IP地址。但是IP地址是32位的二进制数,一共有2^32种不同情况,严重降低了传输效率。解决方法是:转发表中的目的地址不是一个明确的地址,而是一个地址范围。这样就将许多具有共同列表地址的转发表进行了聚合。

目的地址范围的匹配采用最长前缀匹配优先(在检索转发表时,优先选择与分组目的地址匹配前缀最长的入口[entry])。

Internet(数据报网络)

  • 计算机之间的数据交换:”弹性”服务,没有严格时间需求。
  • 链路类型众多:特点、性能各异,统一服务困难。
  • “智能”端系统:可以自适应、性能控制、差错恢复
  • 简化网络,复杂”边缘”

ATM(VC网络)

  • 电话网络演化而来
  • 核心业务是实时对话:严格的时间、可靠性需求,需要有保障的服务。
  • “哑”端系统(非智能):电话机、传真机
  • 简化”边缘”,复杂网络

IPv4协议

Internet网络层

主要功能就是路由和转发。

主机、路由器网络层主要功能:

  • 路由协议:路径选择,如RIP,OSPF,BGP
  • 转发表(路由表)
  • IP协议:寻址规约(conventions),数据报(分组)格式,分组处理规约
  • ICMP协议(互联网控制报文协议):差错报告,路由器”信令协议”
  • 实现IP协议,通常也要实现ICMP协议。后者可以看做是前者的一个伴随协议。

IP数据报(分组)格式

IP数据报格式:首部 + 数据(e.g. TCP, UDP段)

数据报长度是32位,即从0到31位。

首部(固定部分5行、可变部分1行)

数据(1行)

首部分为固定部分和可变部分。

固定部分:

版本号(4位,0~3),首部长度,服务类型(TOS),总长度

标识,标识位,片偏移

生存时间(TTL),协议,首部检验和

源IP地址

目的IP地址

可变部分:

选项字段(长度可变),填充

  1. 版本号:4位,如果是IPv4就是4,如果是IPv6就是6。

  2. 首部长度:4位。是IP分组的首部长度。

    • 以4字节为单位(1行32比特,刚好4字节)
    • IP固定部分首部长度为5*4=20字节
    • 最典型的,例如是IPv4协议,那么版本号是0100(4d),首部长度0101(5d)。
  3. 服务类型(TOS):8位,指示期望获得哪种类型的服务。
    • 1998年这个字段改名为区分服务
    • 只有在网络提供区分服务(DiffServ)时使用
    • 一般情况下不使用,通常IP分组的该字段(第2字节)的值为00H
  4. 总长度:16位,是IP分组的总字节数(首部+数据)
    • 最大IP分组的总长度:65535B
    • 最小的IP分组首部:20B(可变部分为0)
    • IP分组可以封装的最大数据:65535-20=65515B
    • 当然在实际中不会达到最大数据,因为一定会将它切分的。
  5. 生存时间(TTL):8位,是IP分组在网络中可以通过的路由器数(或跳步数)
    • 路由器转发一次分组,TTL减一
    • 如果TTL=0,则路由器丢弃该IP分组
  6. 协议:8位,指示IP分组封装的是哪个协议的数据包
    • 实现复用/分解
    • 6为TCP,表示封装的是TCP段;17为UDP,表示封装的是UDP数据报
  7. 首部校验和:16位,实现对IP分组首部的差错检测
    • 计算校验和时,该字段置为全0
    • 采用反码算数运算求和,和的反码作为首部校验和字段
    • 逐跳计算、逐跳检验
  8. 源IP地址、目的IP地址字段各占32位

IP分片

网络链路存在MTU(最大传输单元)——链路层数据可封装数据的上限。不同链路的MTU不同。

大IP分组向较小MTU链路转发时,可以被”分片”(fragmented)。

IP分片到达目的主机后进行”重组”(reassembled)。

路由器对IP分组只分片不重组。

如果此路由器不让分片,那么就把这个IP分组丢掉,一般地会再发一个ICMP的分组(具体是怎样再查查,这里只是粗略记录)。

IP首部中的总长度、标识、标识位和片偏移用来标识分片以及确定分片的相对顺序。

标识字段:16位,用于标识一个IP分组

  • IP协议利用一个计数器,每产生一个IP分组,计数器就加一,利用此时计数器的值和其他一些信息唯一标识该IP分组

标识位:3位

IP编址

接口:主机/路由器与物理链路的连接

  • 实现网络层功能
  • 路由器通常有多个接口
  • 主机通常只有一个或两个接口(有线的以太网接口,无限的802.11接口)

IP地址:32比特(IPv4)编号用于标识主机、路由器的接口

一般用点分十进制的方式表示。

11011111 00000001 00000001 00000001 = 233.1.1.1

一个IP地址唯一标识一个接口。

IP地址与每个接口关联。

IP子网(subnets)

IP地址:

  • 网络号(NetID) - 高位比特
  • 主机号(HostID) - 低位比特

NetID HostID

233.1.1 .1

相同的网络号构成IP子网。

IP子网:

  • IP地址具有相同网络号的设备接口
  • 不跨越路由器(第三及以上层网络设备)可以彼此物理联通的接口

“有类”编址:

A类地址,50%:NetID(8位) + HostID(24位)

0.0.0.0 ~ 127.255.255.255

B类地址,25%:NetID(16位) + HostID(16位)

128.0.0.1 ~ 191.255.255.255

C类地址,12.5%:NetID(24位) + HostID(8位)

192.0.0.0 ~ 223.255.255.255

D类地址,6.25%:32位,1110

224.0.0.0~239.255.255.255

E类地址,6.25%:32位,1111

240.0.0.0~255.255.255.255

IP子网划分与子网掩码

子网划分:

IP地址——网络号(NetID) + 子网号(SubID) + 主机号(HostID)

就是将刚才的主机号划分为了:子网号(SubID) + 主机号(HostID)。即 子网号是原主机号的部分比特。

子网划分定义:Internet组织机构定义了五种IP地址,有A、B、C三类地址。A类网络有126个,每个A类网络可能有16777214台主机,它们处于同一广播域。而在同一广播域中有这么多节点是不可能的,网络会因为广播通信而饱和,结果造成16777214个地址大部分没有分配出去。可以把基于每类的IP网络进一步分成更小的网络,每个子网由路由器界定并分配一个新的子网网络地址,子网地址是借用基于每类的网络地址的主机部分创建的。划分子网后,通过使用掩码,把子网隐藏起来,使得从外部看网络没有变化,这就是子网掩码。

比如,当一组IP地址指定给一个公司时,公司可能将该网络“分割成”小的网络,每个部门一个。这样,技术部门和管理部门都可以有属于它们的小网络。通过划分子网,我们可以按照我们的需要将网络分割成小网络。这样也有助于降低流量和隐藏网络的复杂性。

子网掩码:

形如IP地址:32位,点分十进制形式

取值:NetID, SubID位全取1,HostID全取0

例如:

A网的默认子网掩码为:255.0.0.0

B网的默认子网掩码为:255.255.0.0

C网的默认子网掩码为:255.255.255.0

借用3比特划分子网的B网的子网掩码为:255.255.224.0 (224就是11100000)

子网地址+子网掩码 —— 准确确定子网大小

将IP分组的目的IP地址与子网掩码按位与运算,提取子网地址。

CIDR与路由聚集

无类域间路由(CIDR: Classless InterDomain Routing)

  • 消除传统的A、B、C类地址界限:将NetID和SubID合在一起变成Network Prefix(Prefix),即统称为网络前缀,并且可以任意长度

  • 融合子网地址与子网掩码,方便子网划分

    无类地址格式:a.b.c.d/x,其中x为前缀长度

11001000 00010111 00010000 00000000

前面是前缀(长为8+8+7=23),后面是主机号HostID。

写成CIDR地址形式就是200.23.16.0/23。

优势

  • 提高IPv4地址空间分配效率
  • 提高路由效率
    • 将多个子网聚合为一个较大的子网
    • 构成超网
    • 路由聚合(route aggregation)

DHCP协议

如何获得IP地址?

  • “硬编码”:静态配置

  • 动态主机配置协议 - DHCP:Dynamic Host Configuration Protocol

    从服务器动态获取:IP地址、子网掩码、默认网关地址、DNS服务器名称与IP地址

    “即插即用”

    允许地址重用

    支持在用地址续租

    支持移动用户加入网络

动态主机配置协议DHCP

  1. 主机广播”DHCP discover”(发现报文)等待是否有DHCP服务器响应
  2. DHCP服务器利用”DHCP offer”(提供报文)进行响应,告诉客户端自己可以提供的一个IP地址
  3. 主机请求IP地址:客户端向服务器发送”DHCP request”(请求报文)表示愿意接受这个IP地址同时请求服务器将它真正分配给自己
  4. DHCP服务器分配IP地址:服务器向客户端发送”DHCP ack”(确认报文)表示确认分配

DHCP协议在应用层实现:

  • 请求报文封装到UDP数据报中
  • IP广播
  • 链路层广播(例如,以太网广播)

DCHP服务器内建于服务器中。

DHCP服务器构造ACK报文,包括分配给客户的IP地址、子网掩码、默认网关、DNS服务器地址。

NAT网络地址转换

本地网络内通信的IP数据报的源与目的IP地址均在子网10.0.0/24(显然这是一个私有地址,比如说是家庭网络)内。

所有离开本地网络去往Internet的数据报的源IP地址需要替换为相同的NAT IP地址(例如138.76.29.7)以及不同的端口号。

动机:

  • 只需从ISP申请一个IP地址,因此面临IPv4地址耗尽
  • 本地网络设备IP地址的变更,无需通告外界网络
  • 变更ISP时,无需修改内部网络设备IP地址
  • 内部网络设备对外界网络不可见,即不可直接寻址

实现:

  • 替换:利用(NAT IP地址,新端口号)替换每个外出IP数据报的(源IP地址,源端口号)
  • 记录:将每对(NAT IP地址,新端口号)与(源IP地址,源端口号)的替换信息存储到NAT转换表中
  • 根据NAT转换表,用(源IP地址,源端口号)替换每个进入内网IP数据报的(目的IP地址,目的端口号)

NAT转换表包含:WAN端地址、LAN端地址。

NAT穿透问题:外部设备期望连接内网地址的服务器

方法1: 静态配置NAT(转换表),将特定端口的连接请求转发给服务器。

方法2: 利用UPnP(Universal Plug and Play)互联网网关设备协议(IGD-Internet Gateway Device)自动配置:学习到NAT公共IP地址,在NAT转换表中增删端口映射。

方法3: 中继(如Skype)

互联网控制报文协议ICMP

Internet Control Message Protocol支持主机或路由器

差错或异常报告

网络探询

两类ICMP报文:

差错报文

IPv6

最初动机:32位IPv4地址空间已分配殆尽

其他动机:改进首部格式:快速处理/转发数据报,支持QoS

IPv6数据报格式:

  • 固定长度的40字节基本首部
  • 不允许分片

虽然首部没有可选项、是固定长度,但是有可选的扩展首部。

IPv6数据报格式:

基本首部,扩展首部1,扩展首部2,…,扩展首部N,数据部分(例如TCP段)

路由算法

路由算法(协议)确定最佳路径,转发表确定在本路由器如何转发分组。

路由算法分类

静态路由&动态路由

静态路由:

  • 手工配置
  • 路由更新慢
  • 优先级高

动态路由:

  • 路由更新快
    • 定期更新
    • 及时响应链路费用或网络拓扑结构变化
  • 由路由算法计算出来的

全局信息&分散信息

全局信息:

  • 所有路由器掌握完整的网络拓扑和链路费用信息。
  • 链路状态(LS)路由算法

分散信息:

  • 路由器只掌握物理相连的邻居以及链路费用。
  • 距离向量(DV)路由算法

链路状态路由算法

Dijkstra算法

  • c(x, y): 结点x到结点y的链路费用;如果x和y不直接相连,则为∞。

  • D(v): 从源到目的v的当前路径费用值。

  • p(v): 沿从源到v的当前路径,v的前序结点集合。
  • N’: 已经找到最小费用路径的结点集合。
1
2
3
4
5
6
7
8
9
10
11
12
13
初始化:
N'= {u}
for 所有结点v
if v nextTo u
D(v) = c(u, v)
else
D(v) = ∞

循环:
找出不在N'中的结点w,使得D(w)最小
将w加入N'
更新w的所有不在N'中的邻居v的D(v): D(v) = min{c(v, w)+D(w), D(v)}
until 所有结点都在N'中

但是存在振荡现象。

距离向量路由算法

Bellman-Ford方程(动态规划)

  • Dx(y) := 从x到y最短路径的费用(距离)
  • Dx(y) = min{c(x, v) + Dv(y)}

异步迭代:

  • 引发每次局部迭代的因素:
    • 局部链路费用改变
    • 来自邻居的DV更新

分布式:

  • 每个结点只当DV变化时才通告给邻居

无穷计数问题

层次路由

将任意规模网络抽象为一个图计算路由——过于理想化。

标识所有路由器

“扁平”网络

网络规模巨大时,交换量会占用所有网络带宽。

聚合路由器为一个区域:自治系统AS

Internet路由

AS内部路由:

  • Internet采用层次路由
  • AS内部路由协议也称为内部网络协议IGP(interior gateway protocol)
  • 最常见的AS内部路由协议:
    • 路由信息协议:RIP(Routing Information Protocol)
    • 开放最短路径优先:OSPF(Open Shortest Path First)
    • 内部网关路由协议:IGRP(Interior Gateway Routing Protocol)
      • Cisco私有协议

RIP

早于1982年随BSD- UNIX操作系统发布

跳数指从源端口到达目的端口所经过的路由个数,每经过一个路由器,跳数加1 。数据包经过一台路由器就是一跳,经过的路由器数量,就是它的跳数。

距离向量路由算法:

  • 距离度量:跳步数(max = 15hops),每条链路1个跳步
  • 每隔30秒,邻居之间交换一次DV,成为通告(advertisement)
  • 每次通告:最多25个目的子网(IP地址形式)

LINK

OSPF(Open Shortest Path First)协议:

  • 开放:公众可用
  • 采用链路状态路由算法

Don’t let anyone rush yourself with their timelines.

传输层

传输层服务的基本理论和基本机制:

  • 多路复用/分用
  • 可靠数据传输机制
  • 流量控制机制
  • 拥塞控制机制

Internet的传输层协议

  • UDP: 无连接传输服务
  • TCP: 面向连接的传输服务
  • TCP拥塞控制

主机上运行着五层Internet协议栈,有应用层、传输层、网络层、数据链路层和物理层;路由器上只有三层协议栈,即网络层及以上的是没有的。

传输层协议为运行在不同host上的进程提供了一种逻辑通信机制

逻辑通信机制,就是指进程之间仿佛是直接连接的,不需要关心有多远的物理距离、经过了多少个路由器、使用的是什么物理媒介。

端系统运行传输层协议:

  • 发送方:将应用递交的消息分成一个或多个的segment,并向下传给网络层。
  • 接收方:将接收到的segment组装成消息,并向上交给应用层。

传输层可以为应用提供多种协议:

  • Internet上的TCP
  • Internet上的UDP

比较

  • 网络层:提供主机之间的逻辑通信机制

  • 传输层:提供应用进程之间的逻辑通信机制

    — 位于网络层之上(IP),依赖于网络层服务,对网络层进行(可能的)增强

Internet传输层协议

可靠、按序的交付服务(TCP)

  • 拥塞控制
  • 流量控制
  • 连接建立

不可靠的交付服务(UDP)

  • 基于”尽力而为 (best-effort) “的网络层,没有做(可靠性方面的)扩展

两种服务均不提供:延迟、带宽

多路复用和多路分用

为什么要多路复用/分用?

  • 如果某层的一个协议对应直接上层的多个协议/实体,则需要复用/分用。

socket是应用层和传输层之间的”门”。

接收端进行多路分用:传输层依据头部信息将收到的segment交给正确的socket,即不同的进程。

发送端进行多路复用:从多个socket接收数据,为每块数据封装上头部信息,生成segment,交给网络层。

分用——如何工作?

主机接收到 IP 数据报(datagram)

  • 每个数据报携带源 IP 地址、目的 IP 地址
  • 每个数据报携带一个传输层的段(segment)
  • 每个段携带源端口号和目的端口号

TCP/UDP 段格式:

|——————- 32 bits ——————-|

| 源端口号 | 目的端口号 |

| 其他头部信息 |

| 应用数据 (message) |

主机收到segment后,传输层协议提取IP地址和端口号信息,将segment导向相应的socket。(网络层是不关心端口号信息的)TCP会做更多的处理。

无连接分用

UDP的socket用二元组标识(目的IP地址,目的端口号)

主机收到UDP段后:

  • 检查段中的目的端口号
  • 将UDP段导向绑定在该端口号的socket

来自不同源IP地址和/或源端口号的IP数据包被导向同一个socket。

面向连接分用

TCP的socket用四元组标识:

  • 源IP地址
  • 源端口号
  • 目的IP地址
  • 目的端口号

接收端利用所有的4个值将segment导向合适的socket。

服务器可能同时支持多个TCP socket。每个socket用自己的四元组标识。

web服务器为每个客户端开不同的socket。

也就是说,例如host B中的进程1向host A发起TCP连接,SP(source port)是9157,DP是80;进程2也发起TCP连接,SP是5775,DP是80;两个进程的S-IP和D-IP相同,都是B和A。但是socket不同,服务器为每个客户端开不同的socket。进程1对应socket1,进程2对应socket2。服务器上的这两个socket的SP相同,都是80,S-IP和D-IP也分别相同,但是DP不同,分别是5775和9157.

UDP

User Datagram Protocol [ RFC 768 ]

基于Internet IP协议:

  • 复用/分用
  • 简单的错误校验(因为路由器在存储转发的过程中也可能会出错)

UDP提供的是”Best effort”服务,所以会丢失、非按序到达。

每个UDP段的处理独立于其他段。

UDP为什么存在?

  • 无需建立连接(减少延迟,因此DNS使用的是UDP)
  • 实现简单:无需维护连接状态
  • 头部开销少(UDP头部8个字节,而TCP是20个字节)
  • 没有拥塞控制:应用可以更好地控制发送时间和速率(TCP有拥塞控制,会根据实际情况自动调整发送时间和速率)

常用于流媒体应用:容忍丢失、速率敏感

UDP还用于:DNS,SNMP

在UDP上是可以实现可靠数据传输的——在应用层增加可靠性机制、应用特定的错误恢复机制(即在应用层实现,因此对应用层开发人员来说难度较大)

UDP segment format:

[32bits]

| sp | dp |

| length | checksum |

| Application data (message)|

length是UDP段的长度(包含头部),checksum是校验和(实现错误校验功能)。

UDP checksum

目的:检测UDP段在传输过程中是否发生错误(如位翻转)。

发生错误是因为传输是端到端的,可能经历了多种物理媒介、多个路由器等等,中途很有可能发生错误。

发送方

  • 将段的内容视为16-bit整数
  • 校验和计算:计算所有整数的和,进位单独取出来与剩下的16位相加,将得到的值按位求反,得到校验和
  • 发送方将校验和放入校验和字段

接收方

  • 计算所收到的校验和
  • 将其与校验和字段进行对比,若不相等则检测出错误,若相等则没有检测出错误,但仍然可能有错误

可靠数据传输原理

可靠——不错、不丢、不乱

可靠数据传输协议:

  • 可靠数据传输对应用层、传输层、链路层都很重要
  • 网络top-10问题
  • 信道的不可靠特性决定了可靠数据传输协议 (rdt) 的复杂性

可靠数据传输协议基本结构:接口

rdt_send(): 被上层应用调用,将数据交给rdt (reliable data transfer protocol) 以发送给对方。即发送方向上地响应这样一个rdt_send的调用。

udt_send(): 被rdt调用,在不可靠信道(unreliable channel)上向接收方传输数据。(所谓的不可靠信道,实际上就是我们所说的网络层的IP协议)

rdt_rcv(): 当数据包到达接收方信道时被调用。这一调用就会触发接收方的rdt协议对数据包进行处理。

deliver_data(): 被rdt调用,向上层应用交付数据。

可以看出,rdt_send()和deliver_send()是单向的。这是因为应用层只需要发数据和收数据,不关心数据是怎么处理和传输的。剩下的所有工作都由下面的层完成。

可靠数据传输协议

渐进的设计可靠数据传输协议的发送方和接收方,只考虑单向数据传输,但控制信息双向流动。利用有限状态机(Finite State Machine, FSM)刻画传输协议。

协议:(逐步贴近真实情况)

Rdt 1.0: 可靠信道上的可靠数据传输

假设底层信道完全可靠:不会发生位错误,不会丢弃分组

发送方和接收方的FSM独立(因为这是一个可靠信道!发送方和接收方之间就不需要什么交互,全部交给协议处理就行了)

Rdt 2.0: 产生位错误的信道

假设分组不会丢失,只是产生了位错误。

首先,接收方需要知道分组是否出错。如果错了,就要想办法恢复/重传。

检测出错已解决——底层信道可能翻转分组中的位(bit):利用校验和检测位错误

如何从错误中恢复?这就需要引入新的控制消息来标识——

  • 确认机制(Acknowledgements, ACK):接收方显示地告知发送方分组已正确接收。
  • NAK:接收方显示地告知发送方分组有错误。
  • 发送方收到NAK后,重传分组。

基于这种重传机制的rdt协议称为ARQ(Automatic Repeat Request)协议。

Rdt 2.0中引入的新机制:

  • 差错检测
  • 接收方反馈控制消息:ACK/NAK
  • 重传

但是有一个致命缺陷:如果ACK/NAK的传输出错怎么办?这里使用的是停-等协议,即stop and wait — sender sends one packet, then waits for receiver response.

what happens if ACK/NAK corrupted?

  • sender doesn’t know what happened at receiver!

  • can’t just retransmit: possible duplicate

Handling duplicates:

  • sender retransmits current pkt if ACK/NAK corrupted

  • sender adds sequence number to each pkt

  • receiver discards (doesn’t deliver up) duplicate pkt

Rdt 2.1 发送方应对ACK/NAK破坏

增加了两个序列号0和1。

对于发送方,有等待上层调用的状态和等待ACK/NAK的状态这两种,因此总状态是翻倍了的,即两个0两个1。(等待上层调用序列号0分组的状态,等待序列号0的ACK/NAK的状态,等待上层调用序列号1分组的状态,等待序列号1的ACK/NAK的状态)翻倍是因为必须记住当前分组的序列号。

Rdt 2.2: 无NAK消息协议

接收方通过ACK告知最后一个被正确接收的分组,在ACK中显示地加入被确认分组的序列号。

发送方接收到重复ACK后,重发当前分组。

停等操作使得Rdt 3.0的性能很差。

流水线协议

允许发送方在收到ACK之前连续发送多个分组。这就需要更大的序列号范围,发送方和接收方需要更大的存储空间以缓存分组

滑动窗口协议 Sliding-window protocol

窗口:允许使用的序列号范围

窗口尺寸为N,表示最多有N个等待确认的消息。

滑动窗口:随着协议的运行,窗口在序列号空间内向前滑动

滑动窗口协议:GBN,SR

GBN协议 (Go-Back-N)

分组头部包含k-bit序列号

采用累积确认的机制

ACK(n): 确认到序列号n(包含n)的分组均已被正确接收。

超时timeout(n)事件:重传序列号大于等于n,还未收到ACK的所有分组。

ACK机制:发送拥有最高序列号的、已被正确接收的分组的ACK

  • 可能产生重复的ACK
  • 只需要记住唯一的expectedseqnum

乱序到达的分组:

  • 直接丢弃——接收方不缓存
  • 重新确认序列号最大的、按序到达的分组

SR (Selective Repeat)

接收方对每个分组单独进行确认

  • 设置缓存机制,缓存乱序到达的分组

发送方只重传那些没收到ACK的分组

  • 为每个分组设置定时器

发送方窗口

  • N个连续的序列号
  • 限制已发送且未确认的分组

序列号空间大小与窗口尺寸满足的关系:$N_S+N_R\leq2^k$.

TCP

  • 点对点:一个发送方,一个接收方

  • 可靠的、按序的字节流

  • 流水线机制:TCP拥塞控制和流量控制机制设置窗口尺寸

  • 发送方/接收方缓存

  • 全双工 (full-duplex):统一连接中能够传输双向数据流

  • 面向连接:

    通信双方在发送数据之前必须建立连接

    连接状态只在连接的两端中维护,在沿途节点中并不维护状态

    TCP连接包括:两台主机上的缓存、连接状态变量、socket等

  • 流量控制机制

序列号

  • 序列号指的是segment中第一个字节的编号,而不是segment的编号,通常从500开始
  • 建立TCP连接时,双方随即选择序列号

ACKs

  • 希望接收到的下一个字节的序列号
  • 累积确认:该序列号之前的所有字节均已被正确接收到

接收方如何处理乱序到达的segment?

  • TCP规范中没有规定,由TCP的实现者做出决策

TCP可靠数据传输

  • TCP在IP层提供的不可靠服务基础上实现可靠数据传输服务

  • 流水线机制

  • 累积确认

  • TCP使用单一重传定时器

  • 触发重传的事件:超时,收到重复ACK
  • 渐进式:暂不考虑重复ACK,暂不考虑流量控制,暂不考虑拥塞控制

RTT和超时

如何设置定时器的超时时间?

  • 大于RTT——但是RTT是变化的
  • 过短:不必要的重传
  • 过长:对段丢失时间反应慢

如何估计RTT?

  • SampleRTT:测量从段发出去到收到ACK的时间

  • 忽略重传

  • SampleRTT变化,就测量多个取平均值

  • 指数加权移动平均:

    EstimatedRTT=(1-alpha)*EstimatedRTT+alpha*SampleRTT

    典型值:0.125

TCP发送方要处理的事件

从应用层收到数据:

  • 创建segment
  • 序列号是segment第一个字节的编号
  • 开启计时器
  • 设置超时时间TimeoutInterval

超时:

  • 重传引起超时的segment
  • 重启定时器

收到ACK:

如果确认此前未确认的segment

  • 更新SendBase
  • 如果窗口中还有未被确认的分组,重新启动定时器

快速重传机制

TCP实现中,如果发生超时,超时时间间隔将重新设置,即将超时时间间隔加倍,导致其很大,因此重发丢失的分组之前要等待很长时间。

通过重复ACK检测分组丢失

如果sender收到对同一数据的3个ACK,则假定该数据之后的段已经丢失,sender重传该分组。

快速重传:在定时器超时之前即进行重传

TCP流量控制

接收方为TCP连接分配buffer。

流量控制 (flow control):发送方不会传输的太多、太快以至于淹没接收方(buffer溢出)。

TCP连接管理

TCP sender和receiver在传输数据前需要建立连接

client是连接发起者,server等待客户连接请求。

Three way handshake

  1. client host sends TCP SYN segment to server

    specifies initial seq

    no data

  2. server host receives SYN, replies with SYNACK segment

    server allocates buffers

    specifies server initial seq

  3. client receives SYNACK, replies with ACK segment, which may contain data

TCP关闭——4次挥手

client向server发送FIN

server收到FIN,回复ACK,关闭连接,发送FIN

client收到FIN,回复ACK

  • 进入等待状态,timeout了会重复发送ACK

server收到ACK,连接关闭

拥塞控制原理

拥塞(congestion)

表现:

  • 分组丢失(路由器缓存溢出)
  • 分组延迟过大(在路由器缓存中排队)

拥塞控制的方法

端到端的拥塞控制:

  • 网络层不需要显式地提供支持
  • 端系统通过观察loss, delay等网络行为判断是否发生拥塞
  • TCP采取这种方法

网络辅助的拥塞控制:

  • 路由器向发送方显示地反馈网络拥塞信息
  • 简单的拥塞只是说

TCP快速重传为什么3次ACK

TCP为什么3次握手

TCP MSS

Java复习

文件IO操作

感觉自己没救了😭

路径分隔符:

static String pathSeparator

static char pathSeparatorChar

文件名称分隔符:

static String separator

static char separatorChar

操作路径:"Code"+File.separator+"Java"+File.separator+"Homework"

String类型和char类型作用完全相同,因为在源码里是这样的:

public static final String pathSeparator=""+pathSeparatorChar;

路径是不区分大小写的。Unix中文件名称分隔符是/,Windows是\,但是这是转义字符,所以写的时候要写成\\.

File类

构造方法

File(String pathname) 通过将给定路径名字符串转换为抽象路径名来创建一个新File实例。路径结尾可以是文件也可以是文件夹。可以是相对路径或绝对路径。路径可以存在也可以不存在。这是因为创建File对象,只是把字符串路径封装成File对象,不考虑路径的真假情况。

File(String parent, String child)

获取功能的方法

  • public String getAbsolutePath() 返回此File的绝对路径
  • public String getPath() 将此File转换为路径名字符串(就是把结果放到这个File对象中返回)
  • public String getName() 返回此File表示的文件或目录的名称
  • public long length() 返回由此File表示的文件的长度,以字节为单位。不能是文件夹。若文件不存在,则返回0.

判断功能的方法

  • public boolean exists() 此File表示的文件或目录是否实际存在
  • public boolean isDirectory() 此File表示的是否为目录
  • public boolean isFile() 此File表示的是否是文件
You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.