图像特征

LBP特征

基本概念

LBP（Local Binary Pattern，局部二值模式）是一种用来描述图像局部纹理特征的算子；它具有旋转不变性和灰度不变性等显著的优点。

原始的LBP算子定义为在3_3的窗口内，以窗口中心像素为阈值，将相邻的8个像素的灰度值与其进行比较，若周围像素值大于中心像素值，则该像素点的位置被标记为1，否则为0。这样，3_3邻域内的8个点经比较可产生8位二进制数（通常转换为十进制数即LBP码，共256种），即得到该窗口中心像素点的LBP值，并用这个值来反映该区域的纹理信息。

用比较正式的公式来定义的话：

其中

代表3x3邻域的中心元素，它的像素值为ic，ip代表邻域内其他像素的值。s(x)是符号函数，定义如下：%!(EXTRA markdown.ResourceType=, string=, string=)

改进-圆形算子

基本的 LBP算子的最大缺陷在于它只覆盖了一个固定半径范围内的小区域，这显然不能满足不同尺寸和频率纹理的需要。为了适应不同尺度的纹理特征，并达到灰度和旋转不变性的要求，Ojala等对 LBP 算子进行了改进，将 3×3邻域扩展到任意邻域，并用圆形邻域代替了正方形邻域，改进后的 LBP 算子允许在半径为 R 的圆形邻域内有任意多个像素点。从而得到了诸如半径为R的圆形区域内含有P个采样点的LBP算子

每个采样点的值可以通过下式计算：

其中%!(EXTRA markdown.ResourceType=, string=, string=)

为邻域中心点，%!(EXTRA markdown.ResourceType=, string=, string=)

为某个采样点。通过上式可以计算任意个采样点的坐标，但是计算得到的坐标未必完全是整数，所以可以通过双线性插值来得到该采样点的像素值：

改进-旋转不变

从 LBP 的定义可以看出，LBP 算子是灰度不变的，但却不是旋转不变的。图像的旋转就会得到不同的 LBP值。

Maenpaa等人又将 LBP算子进行了扩展，提出了具有旋转不变性的 LBP 算子，即不断旋转圆形邻域得到一系列初始定义的 LBP值，取其最小值作为该邻域的 LBP 值。

图中算子下方的数字表示该算子对应的 LBP值，图中所示的 8 种 LBP模式，经过旋转不变的处理，最终得到的具有旋转不变性的 LBP值为 15。也就是说，图中的 8种 LBP 模式对应的旋转不变的 LBP模式都是 00001111。

改进-等价模式

经统计，在实际图像中，绝大多数LBP模式最多只包含两次从1到0或从0到1的跳变。故将只有0次变化和2次变化的LBP二进制模式定义为的等价模式（当某个局部二进制模式所对应的循环二进制数从0到1或从1到0最多有两次跳变时，该局部二进制模式所对应的二进制就成为一个等价模式类。如0000 0000，1111 1111，1000 0111都是等价模式类）。

等价模式有P*（P-1）+2种证明

LBP特征使用方式

对一幅图像（记录的是每个像素点的灰度值）提取其原始的LBP算子之后，得到的原始LBP特征依然是“一幅图片”（记录的是每个像素点的LBP值）。

LBP的应用中，如纹理分类、人脸分析等，一般都不将LBP图谱作为特征向量用于分类识别，而是采用LBP特征谱的统计直方图作为特征向量用于分类识别。

对LBP特征向量进行提取的步骤

1. 首先将检测窗口划分为16×16的小区域（cell）；
2. 对于每个cell中的一个像素，将相邻的8个像素的灰度值与其进行比较，若周围像素值大于中心像素值，则该像素点的位置被标记为1，否则为0。这样，3*3邻域内的8个点经比较可产生8位二进制数，即得到该窗口中心像素点的LBP值；
3. 然后计算每个cell的直方图，即每个数字（假定是十进制数LBP值）出现的频率；然后对该直方图进行归一化处理。
4. 最后将得到的每个cell的统计直方图进行连接成为一个特征向量，也就是整幅图的LBP纹理特征向量；

然后便可利用SVM或者其他机器学习算法进行分类了。

低频均值哈希

一张图片就是一个二维信号，它包含了不同频率的成分。亮度变化小的区域是低频成分，它描述大范围的信息。而亮度变化剧烈的区域（比如物体的边缘）就是高频的成分，它描述具体的细节。或者说高频可以提供图片详细的信息，而低频可以提供一个框架。

而一张大的，详细的图片有很高的频率，而小图片缺乏图像细节，所以都是低频的。所以我们平时的下采样，也就是缩小图片的过程，实际上是损失高频信息的过程。下面5张图依次是原图，放缩至6464、3232、1616、88的图。

  

均值哈希算法主要是利用图片的低频信息，其工作过程如下：

1. 缩小尺寸：去除高频和细节的最快方法是缩小图片，将图片缩小到8x8的尺寸，总共64个像素。不要保持纵横比，只需将其变成8*8的正方形。这样就可以比较任意大小的图片，摒弃不同尺寸、比例带来的图片差异。
2. 简化色彩：将8*8的小图片转换成灰度图像。
3. 计算平均值：计算所有64个像素的灰度平均值。
4. 比较像素的灰度：将每个像素的灰度，与平均值进行比较。大于或等于平均值，记为1；小于平均值，记为0。
5. 计算hash值：将上一步的比较结果，组合在一起，就构成了一个64位的整数，这就是这张图片的指纹。组合的次序并不重要，只要保证所有图片都采用同样次序就行了。(我设置的是从左到右，从上到下用二进制保存)。

计算一个图片的hash指纹的过程就是这么简单。如果图片放大或缩小，或改变纵横比，结果值也不会改变。增加或减少亮度或对比度，或改变颜色，对hash值都不会太大的影响。最大的优点：计算速度快！这时候，比较两个图片的相似性，就是先计算这两张图片的hash指纹，也就是64位0或1值，然后计算不同位的个数(汉明距离)。如果这个值为0，则表示这两张图片非常相似，如果汉明距离小于5，则表示有些不同，但比较相近，如果汉明距离大于10则表明完全不同的图片。

pHash

pHash是低频均值哈希的增强版

一个基于pHash算法的、使用es的、从大批图片中快速检索相似图片的解决方案

理论依据为《AN IMAGE SIGNATURE FOR ANY KIND OF IMAGE》H. Chi Wong, Marshall Bern, and David Goldberg 这篇论文。

这篇论文介绍的算法有良好的普适性和鲁棒性，在处理图像文本、卡通图片、连续色调图片都有不错的效果。

图片签名计算

1. 将图片转化为256级灰度图片，简化图片的色彩属性
2. 取图片5%95%的位置，划分为9*9的网格（之所以取5%95%，是因为考虑到扫描图片、被剪辑过的图片等，边缘部分的信息可能会干扰图片的识别）。
   
3. 计算每个网格的平均灰度。计算方法为在网格内隔P个像素取一个点，取灰度均值。P的计算方法在论文内。
4. 计算每个网格和相邻网格灰度的差值。分为5个等级：暗很多，暗一点，一样，亮一点，亮很多得到一个998的数组（有的算法是划分3个等级，例如均值哈希，5个等级可以更好的区分，也可以在一定程度上避免由于四舍五入产生的误差）
5. 把数组按照某个规则打平，变为一维数组。规则不重要，只要保证每张图片都按相同的规则打平就行。

这个矩阵就是这张图片的签名。

对比两个矩阵，可以计算汉明距离，也可以计算欧氏距离.相比汉明距离，欧氏距离可以更加反映出图片的不同，而且第4步中刻意划分出5个等级，也是为了服务欧氏距离的计算。0.6的阈值是一个经验值，这个阈值在大多数情况下适用。超过0.6标识两张图片一点也不相关。

检索

如何快速从众多签名中检索出相似度高的签名，方案：将打平的图像签名切成一个一个的“词”，这些词可以重叠也可以不连续。但每张图片都要按照相同的规则切词。

例如数组 [0, 1, 2, 0, -1, -2, 0, 1]，按照k=3(每个词3个值)，N=4(切4个词)，可以切为

[0, 1, 2]

[2, 0, -1]

[-1, -2, 0]

[0, 1]

然后将这些切好的词通过矩阵乘法转化为int值，存入es中，这些“词”就是图片用于检索的签名。

当需要检索某张图片时，现将这个图片的simple_words算出，然后去es中检索，如果存在相同位置数字相同的签名，那这两张图片就有相同的可能性。

论文中推荐的切法为k=10，N=100,image-match中的切法为k=16，N=63.

存在重叠的切词有一个好处，就是接受了图片局部不相似的容错性。同时N不宜过大。因为N越大，图片至少有一个simple_word相同的可能性就越大，这样的话可能找出很多只是碰巧有一个词相同的图片，降低了搜索效率。

OSI七层模型

七层模型

• 物理层：传输二进制数据
• 数据链路层：节点-节点间。功能：组帧（增加头（发送端物理地址，接收端物理地址）、尾（差错检验）信息）、物理寻址、流量控制、差错控制、访问控制（在某时刻谁使用链路）。
• 网络层：源主机-目的主机之间单个报文。功能：逻辑寻址、路由、分组转发（内网直接转发/外网多个路由器转发）
• 传输层：源主机-目的主机之间全部报文。功能：分段与重组、SAP寻址、连接控制、流量控制、差错控制
• 会话层：对话控制、同步。
• 表示层：数据表示转换、加密解密、压缩解压缩。
• 应用层

socket编程

accept函数用于接收连接，并创建一个新的socket描述符用于处理连接。

各层的差错检验

数据链路层有校验了，为什么网络层还要校验，运输层仍需要校验？
数据链路层：对数据本身的检验
网络层：对IP Header的检验，防止头改写误修改目的地址或源地址
传输层：伪首部 + TCP Header + TCP Payload的检验。伪首部的组成【source IP】+ 【 destination IP】+ 【protocol】+ 【total length - IP length】

HTTP

长连接

什么是长连接、短连接？
　　在HTTP/1.0中，默认使用的是短连接。也就是说，浏览器和服务器每进行一次HTTP操作，就建立一次连接，但任务结束就中断连接。如果客户端浏览器访问的某个HTML或其他类型的 Web页中包含有其他的Web资源，如JavaScript文件、图像文件、CSS文件等；当浏览器每遇到这样一个Web资源，就会建立一个HTTP会话。
但从 HTTP/1.1起，默认使用长连接，用以保持连接特性。使用长连接的HTTP协议，会在响应头有加入这行代码：
Connection:keep-alive
　　在使用长连接的情况下，当一个网页打开完成后，客户端和服务器之间用于传输HTTP数据的 TCP连接不会关闭，如果客户端再次访问这个服务器上的网页，会继续使用这一条已经建立的连接。Keep-Alive不会永久保持连接，它有一个保持时间，可以在不同的服务器软件（如Apache）中设定这个时间。实现长连接要客户端和服务端都支持长连接。
HTTP协议的长连接和短连接，实质上是TCP协议的长连接和短连接。

websocket

websocket
websocket 2

对称加密、非对称加密

对称加密：指的就是加、解密使用的同是一串密钥，所以被称做对称加密。对称加密只有一个密钥作为私钥。 常见的对称加密算法：DES、3DES、AES、Blowfish、IDEA、RC5、RC6等。
对称加密相比非对称加密算法来说，加解密的效率要高得多、加密速度快。但是缺陷在于对于密钥的管理和分发上比较困难，不是非常安全，密钥管理负担很重。

非对称加密：指的是加、解密使用不同的密钥，一把作为公开的公钥，另一把作为私钥。公钥加密的信息，只有私钥才能解密。反之，私钥加密的信息，只有公钥才能解密。 如RSA。
安全性更高，公钥是公开的，密钥是自己保存的，不需要将私钥给别人。缺点：加密和解密花费时间长、速度慢，只适合对少量数据进行加密。

HTTPS

RSA握手

1. 客户端向服务器发送Client Hello,告诉服务器，我支持的协议版本，加密套件等信息。
2. 服务器收到响应，选择双方都支持的协议，套件，向客户端发送Server Hello。同时服务器也将自己的证书发送到客户端(Certificate)。
3. 客户端自己生产预主密钥，通过公钥加密预主秘钥，将加密后的预主秘钥发送给服务器 (Client Exchange)。
4. 服务器用自己的私钥解密加密的预主密钥。

DH握手

1. 客户端向服务器发送Client Hello,告诉服务器，我支持的协议版本，加密套件等信息。
2. a. 服务端收到响应，选择双方都支持的协议，套件，向客户端发送Server Hello。同时服务器也将自己的证书发送到客户端(Certificate)。
   b. 服务器利用私钥将客户端随机数，服务器随机数，服务器DH参数签名，生成服务器签名。
3. 服务端向客户端发送服务器DH参数以及服务器签名(Server Key Exchange)。
4. 客户端向服务端发送客户端DH参数(Client Key Exchange)。

TCP

SRTT

RTT：一个包来回时间
SRTT（指数加权移动平均RTT）：根据最新测量的值和之前计算出的值，获取最新的预估RTT时间。α典型值=0.125
SRTT=（1-α）*SRTT+α*SampleRTT

RTO

超时时间设置

• 方法1：
  RTO = min [ UBOUND,  max [ LBOUND,   (β * SRTT) ]  ]
  • UBOUND是最大的timeout时间，上限值
  • LBOUND是最小的timeout时间，下限值
  • β 值一般在1.3到2.0之间。
• 方法2：
  DevRTT:平滑RTT和真实的差距（加权移动平均）
  DevRTT = (1-β)DevRTT + β(|RTT-SRTT|)
  RTO= µ * SRTT + ∂ *DevRTT
  在Linux下，α = 0.125，β = 0.25， μ = 1，∂ = 4

收包策略

收到乱序包时，接收端会缓存包，并且发送一个序号为未收到的包的ACK信息。

快速重传

连续收到三次同一个ACK序列号，即使没到超时时间也对该包进行重传

流量控制

接收方返回的tcp头包含Revwindow，用于通知发送方自己的缓存区大小，确保发送方不会发从超过缓存区大小的数据量。

三次握手

1. 第一次握手：建立连接时，客户端A发送SYN包（SYN=j）到服务器B，并进入SYN_SEND状态，等待服务器B确认。
2. 第二次握手：服务器B收到SYN包，必须确认客户A的SYN（ACK=j+1），同时自己也发送一个SYN包（SYN=k），即SYN+ACK包，此时服务器B进入SYN_RECV状态。
3. 第三次握手：客户端A收到服务器B的SYN＋ACK包，向服务器B发送确认包ACK（ACK=k+1），此包发送完毕，客户端A和服务器B进入ESTABLISHED状态，完成三次握手。

为什么需要三次握手：
1.如果两次，那么B无法确定B的信息A是否能收到，B的初始序列号无法达成一致。
2.如果两次，A的连接请求信息超时时，会重发连接请求。这时候B直接建立了连接，没有向A确认是否还需要这个连接，导致维护了客户端以为失败了的连接。
　　如果四次，那么就造成了浪费，因为在三次结束之后，就已经可以保证A可以给B发信息，A可以收到B的信息； B可以给A发信息，B可以收到A的信息。

四次挥手

过程

1. 客户端A发送一个FIN，用来关闭客户A到服务器B的数据传送。
2. 服务器B收到这个FIN，它发回一个ACK，确认序号为收到的序号加1。和SYN一样，一个FIN将占用一个序号。
3. 服务器B关闭与客户端A的连接，发送一个FIN给客户端A。
4. 客户端A发回ACK报文确认，并将确认序号设置为收到序号加1。

TIME_WAIT

TIME_WAIT的产生条件：主动关闭方在发送四次挥手的最后一个ACK会变为TIME_WAIT状态，保留次状态的时间为两个MSL（linux里一个MSL为30s，是不可配置的）。主动关闭的Socket端会进入TIME_WAIT状态，并且持续2MSL时间长度，MSL就是maximum segment lifetime(最大分节生命期），这是一个IP数据包能在互联网上生存的最长时间，超过这个时间将在网络中消失。MSL在RFC 1122上建议是2分钟，而源自berkeley的TCP实现传统上使用30秒，因而，TIME_WAIT状态一般维持在1-4分钟。

TIME_WAIT两个MSL的作用：

• 可靠安全的关闭TCP连接。比如网络拥塞，主动方最后一个ACK被动方没收到，这时被动方会对FIN开启TCP重传，发送多个FIN包，在这时尚未关闭的TIME_WAIT就会把这些尾巴问题处理掉，不至于对新连接及其它服务产生影响。
• 允许老的重复分节在网络中消逝。TCP分节可能由于路由器异常而“迷途”，在迷途期间，TCP发送端可能因确认超时而重发这个分节，迷途的分节在路由器修复后也会被送到最终目的地，这个 原来的迷途分节就称为lost duplicate。在关闭一个TCP连接后，马上又重新建立起一个相同的IP地址和端口之间的TCP连接，后一个连接被称为前一个连接的化身 （incarnation)，那么有可能出现这种情况，前一个连接的迷途重复分组在前一个连接终止后出现，从而被误解成从属于新的化身。为了避免这个情 况，TCP不允许处于TIME_WAIT状态的连接启动一个新的化身，因为TIME_WAIT状态持续2MSL，就可以保证当成功建立一个TCP连接的时 候，来自连接先前化身的重复分组已经在网络中消逝。

TIME_WAIT占用的资源：少量内存（查资料大概4K）和一个fd。

TIME_WAIT关闭的危害：

• 网络情况不好时，如果主动方无TIME_WAIT等待，关闭前个连接后，主动方与被动方又建立起新的TCP连接，这时被动方重传或延时过来的FIN包过来后会直接影响新的TCP连接；
• 同样网络情况不好并且无TIME_WAIT等待，关闭连接后无新连接，当接收到被动方重传或延迟的FIN包后，会给被动方回一个RST包，可能会影响被动方其它的服务连接。

TCP: time wait bucket table overflow产生原因及影响：原因是超过了linux系统tw数量的阀值。危害是超过阀值后﹐系统会把多余的time-wait socket 删除掉，并且显示警告信息，如果是NAT网络环境又存在大量访问，会产生各种连接不稳定断开的情况。

为什么需要四次分手：
TCP是双向的，只有等到Server端所有的报文都发送完了，才能发送FIN报文，因此不能和ACK报文一起发送。故需要四步握手。

拥塞控制

拥塞控制

• 初始：
  cwnd(拥塞窗口）=1个最大报文段大小（MSS）
• 慢启动：
  每当有一个报文段被确认，cwnd就增加1个MSS大小。这样，cwnd的值就随着网络往返时间(Round Trip Time,RTT)呈指数级增长。
• 拥塞避免：
  ssthresh(慢启动门限），linux3.0后默认初始值为10* MSS
  当cwnd超过ssthresh，当窗口中所有的报文段都被确认时，cwnd的大小加1，cwnd的值就随着RTT开始线性增加，这样就可以避免增长过快导致网络拥塞，慢慢的增加调整到网络的最佳值。
• 两种情况：
  • 报文超时。出现报文超时意味着拥塞已经相当严重，此时会进行三个动作：
    1. 把ssthresh降低为cwnd值的一半
    2. 把cwnd重新设置为1
    3. 重新进入慢启动过程。
  • 收到三个相同的ACK。此时进行快速重传：
    1. 把ssthresh设置为cwnd的一半
    2. 把cwnd再设置为ssthresh的值(具体实现有些为ssthresh+3)
    3. 重新进入拥塞避免阶段。
• 快速恢复
  “快速恢复”算法是在上述的“快速重传”算法后添加的，当收到3个重复ACK时，TCP最后进入的不是拥塞避免阶段，而是快速恢复阶段。快速重传和快速恢复算法一般同时使用。快速恢复的思想是“数据包守恒”原则，即同一个时刻在网络中的数据包数量是恒定的，只有当“老”数据包离开了网络后，才能向网络中发送一个“新”的数据包，如果发送方收到一个重复的ACK，那么根据TCP的ACK机制就表明有一个数据包离开了网络，于是cwnd加1。如果能够严格按照该原则那么网络中很少会发生拥塞，事实上拥塞控制的目的也就在修正违反该原则的地方。
  具体来说快速恢复的主要步骤是：
  1. 当收到3个重复ACK时，把ssthresh设置为cwnd的一半，把cwnd设置为ssthresh的值加3，然后重传丢失的报文段，加3的原因是因为收到3个重复的ACK，表明有3个“老”的数据包离开了网络。
  2. 再收到重复的ACK时，拥塞窗口增加1。
  3. 当收到新的数据包的ACK时，把cwnd设置为第一步中的ssthresh的值。原因是因为该ACK确认了新的数据，说明从重复ACK时的数据都已收到，该恢复过程已经结束，可以回到恢复之前的状态了，也即再次进入拥塞避免状态。

公平性

tcp乘性减少加性增加的特性，决定相同拥塞控制策略的多个tcp最终都会在公平线上震荡。

tcp的公平性是有限制的，相同策略的tcp之间是公平的，不公平的情况有：

• tcp和udp之间
• 一台机器有多个tcp，则不同机器之间是不公平的

网络层

IP分片与重组

IP分片与重组
IP头中，标识和片偏移字段就是标识的IP数据报文的分片。原因是不同的网络中MTU（最大传输单元）可能不一样。

IP地址分类

1．A类IP地址
　　一个A类IP地址由1字节的网络地址和3字节主机地址组成，网络地址的最高位必须是“0”， 地址范围1.0.0.1-126.255.255.254（二进制表示为：00000001 00000000 00000000 00000001 - 01111110 11111111 11111111 11111110）。可用的A类网络有126个，每个网络能容纳1677214个主机。
2．B类IP地址
　　一个B类IP地址由2个字节的网络地址和2个字节的主机地址组成，网络地址的最高位必须是“10”，地址范围128.1.0.1-191.255.255.254（二进制表示为：10000000 00000001 00000000 00000001 - 10111111 11111111 11111111 11111110）。可用的B类网络有16384个，每个网络能容纳65534主机 。
3．C类IP地址
　　一个C类IP地址由3字节的网络地址和1字节的主机地址组成，网络地址的最高位必须是“110”。范围192.0.1.1-223.255.255.254（二进制表示为: 11000000 00000000 00000001 00000001 - 11011111 11111111 11111110 11111110）。C类网络可达2097152个，每个网络能容纳254个主机。
4．D类地址用于多点广播（Multicast）。
　　D类IP地址第一个字节以“1110”开始，它是一个专门保留的地址。它并不指向特定的网络，目前这一类地址被用在多点广播（Multicast）中。多点广播地址用来一次寻址一组计算机，它标识共享同一协议的一组计算机。
　　地址范围224.0.0.1-239.255.255.254
5．E类IP地址
　　以“1111”开始，为将来使用保留。
　　E类地址保留，仅作实验和开发用。

特殊IP地址

• 169.254.x.x　　如果你的主机使用了DHCP功能自动获得一个IP地址，那么当你的DHCP服务器发生故障，或响应时间太长而超出了一个系统规定的时间，Wingdows系统会为你分配这样一个地址。如果你发现你的主机IP地址是一个诸如此类的地址，很不幸，十有八九是你的网络不能正常运行了。
• 10.x.x.x、172.16。x。x～172.31。x。x、192.168。x。x　　私有地址，这些地址被大量用于企业内部网络中。一些宽带路由器，也往往使用192.168.1.1作为缺省地址。私有网络由于不与外部互连，因而可能使用随意的IP地址。保留这样的地址供其使用是为了避免以后接入公网时引起地址混乱。使用私有地址的私有网络在接入Internet时，要使用地址翻译(NAT)，将私有地址翻译成公用合法地址。在Internet上，这类地址是不能出现的。

路由聚合(超网）

路由聚合
超网(supernetting)是与子网类似的概念–IP地址根据子网掩码被分为独立的网络地址和主机地址。但是，与子网把大网络分成若干小网络相反，它是把一些小网络组合成一个大网络–超网。
作用：

• 超网的功能是将多个连续的C类的网络地址聚合起来映射到一个物理网络上。这样，这个物理网络就可以使用这个聚合起来的C类地址的共同地址前缀作为其网络号。超网创建用来解决路由列表超出现有软件和管理人力的问题以及提供B类网络地址空间耗尽的解决办法。超网允许一个路由列表入口表示一个网络集合，就如一个区域代码表示一个区域的电话号码的集合一样。
• 超网（路由聚合）技术是为了解决路由表的内容冗余问题，使用路由聚合能够缩小路由表的规模，减少路由表的内存。

为避免路由黑洞，路由匹配遵循最长前缀匹配原则。

DHCP动态主机配置协议

DHCP

1. 客户端：利用广播封包发送搜索DHCP服务器的封包：
   若客户端网络设定使用DHCP协议取得IP (在Windows内为『自动取得IP』)，则当客户端开机或者是重新启动网络卡时，客户端主机会发送出搜寻DHCP服务器的UDP封包给所有物理网段内的计算机。此封包的目标IP会是255.255.255.255，所以一般主机接收到这个封包后会直接予以丢弃，但若局域网络内有DHCP服务器时，则会开始进行后续行为。

2. 服务器端：提供客户端网络相关的租约以供选择：
   DHCP服务器在接收到这个客户端的要求后，会针对这个客户端的硬件地址(MAC)与本身的设定数据来进行下列工作：

   • 到服务器的登录文件中寻找该用户之前是否曾经用过某个IP ，若有且该IP 目前无人使用，则提供此IP 给客户端；
   • 若配置文件针对该MAC 提供额外的固定IP (static IP) 时，则提供该固定IP 给客户端；
   • 若不符合上述两个条件，则随机取用目前没有被使用的IP 参数给客户端，并记录下来。

   总之，服务器端会针对客户端的要求提供一组网络参数租约给客户端选择，由于此时客户端尚未有IP ，因此服务器端响应的封包信息中， 主要是针对客户端的MAC 来给予回应。此时服务器端会保留这个租约然后开始等待客户端的回应。

3. 客户端：决定选择的DHCP服务器提供的网络参数租约并回报服务器：
   由于局域网络内可能并非仅有一部DHCP服务器，但客户端仅能接受一组网络参数的租约。因此客户端必需要选择是否要认可该服务器提供的相关网络参数的租约。当决定好使用此服务器的网络参数租约后，客户端便开始使用这组网络参数来设定自己的网络环境。此外，客户端也会发送一个广播封包给所有物理网段内的主机，告知已经接受该服务器的租约。此时若有第二台以上的DHCP服务器，则这些没有被接受的服务器会收回该IP租约。至于被接受的DHCP服务器会继续进行底下的动作。

4. 服务器端：记录该次租约行为并回报客户端已确认的响应封包信息：当服务器端收到客户端的确认选择后，服务器会回传确认的响应封包，并且告知客户端这个网络参数租约的期限，并且开始租约计时喔！那么该次租约何时会到期而被解约(真可怕的字眼) ？你可以这样想：

   • 客户端脱机：不论是关闭网络接口(ifdown)、重新启动(reboot)、关机(shutdown)等行为，皆算是脱机状态，这个时候Server端就会将该IP回收，并放到Server自己的备用区中，等待未来的使用；
   • 客户端租约到期：前面提到DHCP server端发放的IP有使用的期限，客户端使用这个IP到达期限规定的时间，而且没有重新提出DHCP的申请时，就需要将IP缴回去！这个时候就会造成断线。但用户也可以再向DHCP服务器要求再次分配IP啰。

NAT网络地址转化

NAT
哈工大计网慕课NAT内容
功能：
NAT不仅能解决了lP地址不足的问题，而且还能够有效地避免来自网络外部的攻击，隐藏并保护网络内部的计算机。把内网的私有地址，转化成外网的公有地址。使得内部网络上的（被设置为私有IP地址的）主机可以访问Internet。

1. 宽带分享：这是 NAT 主机的最大功能。
2. 安全防护：NAT 之内的 PC 联机到 Internet 上面时，他所显示的 IP 是 NAT 主机的公共 IP，所以 Client 端的 PC 当然就具有一定程度的安全了，外界在进行 portscan（端口扫描） 的时候，就侦测不到源Client 端的 PC 。

NAT局限性

1. NAT违反了IP地址结构模型的设计原则。IP地址结构模型的基础是每个IP地址均标识了一个网络的连接。Internet的软件设计就是建立在这个前提之上，而NAT使得有很多主机可能在使用相同的地址，如10.0.0.1。
2. NAT使得IP协议从面向无连接变成面向连接。NAT必须维护专用IP地址与公用IP地址以及端口号的映射关系。在TCP/IP协议体系中，如果一个路由器出现故障，不会影响到TCP协议的执行。因为只要几秒收不到应答，发送进程就会进入超时重传处理。而当存在NAT时，最初设计的TCP/IP协议过程将发生变化，Internet可能变得非常脆弱。
3. NAT违反了基本的网络分层结构模型的设计原则。因为在传统的网络分层结构模型中，第N层是不能修改第N+1层的报头内容的。NAT破坏了这种各层独立的原则。
4. 有些应用是将IP地址插入到正文的内容中，例如标准的FTP协议与IP　Phone协议H.323。如果NAT与这一类协议一起工作，那么NAT协议一定要做适当地修正。同时，网络的传输层也可能使用TCP与UDP协议之外的其他协议，那么NAT协议必须知道并且做相应的修改。由于NAT的存在，使得P2P应用实现出现困难，因为P2P的文件共享与语音共享都是建立在IP协议的基础上的。
5. NAT同时存在对高层协议和安全性的影响问题。RFC对NAT存在的问题进行了讨论。NAT的反对者认为这种临时性的缓解IP地址短缺的方案推迟了Ipv6迁移的进程，而并没有解决深层次的问题，他们认为是不可取的。

NAT转换规则

• TCP/UDP：内网IP+端口号 <—> NAT公网IP+端口号
• ICMP：内网IP+sequenceId <—> NAT公网IP+sequenceId

ICMP互联网控制报文协议

ICMP协议的功能主要有：

1. 确认IP包是否成功到达目标地址
2. 通知在发送过程中IP包被丢弃的原因

常见报文：

• 相应请求
  我们用的ping操作中就包括了相应请求（类型字段值为8）和应答（类型字段值为0）ICMP报文。
  过程：
  一台主机向一个节点发送一个类型字段值为8的ICMP报文，如果途中没有异常（如果没有被路由丢弃，目标不回应ICMP或者传输失败），则目标返回类型字段值为0的ICMP报文，说明这台主机存在。
• 目标不可达，源抑制和超时报文
  这三种报文的格式是一样的。
  1. 目标不可到达报文（类型值为3）在路由器或者主机不能传递数据时使用。
     例如：我们要连接对方一个不存在的系统端口（端口号小于1024）时，将返回类型字段值3、代码字段值为3的ICMP报文。
     常见的不可到达类型还有网络不可到达（代码字段值为0）、主机不可达到（代码字段值为1）、协议不可到达（代码字段值为2）等等。
  2. 源抑制报文（类型字段值为4，代码字段值为0）则充当一个控制流量的角色，通知主机减少数据报流量。由于ICMP没有回复传输的报文，所以只要停止该报文，主机就会逐渐恢复传输速率。
  3. 无连接方式网络的问题就是数据报会丢失，或者长时间在网络游荡而找不到目标，或者拥塞导致主机在规定的时间内无法重组数据报分段，这时就要触发ICMP超时报文的产生。
     超时报文（类型字段值为11）的代码域有两种取值：代码字段值为0表示传输超时，代码字段值为1表示分段重组超时。
• 时间戳请求
  时间戳请求报文（类型值字段13）和时间戳应答报文（类型值字段14）用于测试两台主机之间数据报来回一次的传输时间。
  传输时，主机填充原始时间戳，接受方收到请求后填充接受时间戳后以类型值字段14的报文格式返回，发送方计算这个时间差。
  (有些系统不响应这种报文)

记录路由

找出ip数据包在网络中经过的路由

ipv6

ipv4区别：

1. 移除校验和，减少每跳处理时间
2. 选项，从基本首部移除，用“下一个首部”字段扩展选项
3. ICMPv6。增加了一些报文类型，支持多播组管理

隧道：
在ipv6网络穿越ipv4网络时，会将ipv6数据包封装到ipv4数据包中

路由算法

哈工大计网慕课-路由算法
算法将路由结构抽象为图，边的权重为数据传输代价

全局信息 vs 分散信息

有的路由算法需要所有路由器掌握完整的网络拓扑和链路费用信息，也就是对网络的全局有一个了解
最有代表性的就是链路状态(LS)路由算法。有的路由算法只需要路由器只掌握物理相连的邻居以及链路费用。通过邻居间信息交换、运算的迭代过程来更新路由信息。
最有代表性的就是距离向量(DV)路由算法。

链路状态路由算法（LS）

首先将网络抽象，然后利用图算法中的最短路径算法，Dijkstra 算法。
所有结点(路由器)掌握网络拓扑和链路费用

• 通过“链路状态广播”
• 所有结点拥有相同信息
  利用Dijkstra 算法计算从一个结点(“源” )到达所有其他结点的最短路径。从而可以获得该节点的转发表。

算法复杂性: n个结点

• 每次迭代: 需要检测所有不在集合N’中的结点w
• n(n+1)/2次比较: O(n2)
• 更高效的实现: O(nlogn)

算法可能存在震荡现象：
当链路状态更新的太快并且不断变化的时候，假设我们发出一个分组，结果还没到目的地，路由表就更新了，然后这个数据报就一直在路由间切换，最后由于ttl到0，直接丢弃。这就是震荡现象。

距离向量(Distance Vector)路由算法

使用动态规划的思路。

Dx(y)：x与y的最小距离
c(x,v)：x与相邻节点v的距离

迭代过程：

毒性逆转：
如果一个结点(e.g. Z)到达某目的(e.g.X)的最小费用路径是通过某个邻居(e.g.Y)，则通告给该邻居结点到达该目的的距离为无穷大。解决无穷计数问题。

层次路由

层次路由

将路由器聚合成一个自治系统AS(autonomous systems)

1. 同一AS内的路由器运行相同的路由协议自治系统内部路由协议(“intra-AS” routing protocol)
2. 不同AS内的路由器可以运行不同的AS内部路由协议
   路由器的转发表由AS内部路由算法与AS间路由算法共同配置：
3. AS内部路由算法设置AS内部目的网络路由入口(entries)
4. AS内部路由算法与AS间路由算法共同设置AS外部目的网络路由入口
   网关路由器(gateway router)位于AS边缘，通过链路连接其他AS的网关路由器

假设AS1内某路由器收到一个目的地址在AS1之外的数据报，为确定路由器应该将该数据报转发给哪个网关路由器：

1. AS1必须学习到哪些目的网络可以通过AS2到达，哪些可以通过AS3到达。
2. AS间路由算法将这些网络可达性信息传播给AS1内部路由器。
3. 路由器利用AS内部路由信息，确定其到达网关路由器的最小费用路径接口，在转发表中增加入口
4. 如果通过AS3和AS2均可到达，为了配置转发表，路由器必须确定应该将去往子网的数据报转发给哪个网关，这个任务也是由AS间路由协议完成的。在实践中经常使用的一种方法是热土豆路由选择(hotpotatorouting)，将分组发送给最近的网关路由器。
   

Intenet层次路由

Intenet路由
全球各国as自治系统总数排名、全球自治系统总数排名

路由信息协议：RIP（Routing Information Protocol）

是一种距离向量协议， 费用实际上是从源路由器到目的子网的跳步数(max = 15 hops)，跳是沿着从源路由器到目的子网（包括目的子网）的最短路径所经过的子网数量
每隔30秒，邻居之间交换一次DV，成为RIP通告(RIP advertisement)-RIP响应报文，其中包含了一个该AS内的最多25个目的子网的列表(IP地址形式)，以及发送方到其中每个子网的距离。
路由器也可通过使用RIP请求报文，请求其邻居到指定目的地的费用。
每台路由器维护一张称为路由选择表的RIP表，包括该路由器的距离向量和该路由器的转发表。
如果180秒没有收到通告→邻居/链路失效，经过该邻居/链路的路由不可用，重新计算路由并向邻居发送新的通告，邻居再依次向外发送通告（如果转发表改变）
链路失效信息要快速传播到全网，可能发生无穷计数问题，因此使用了毒性逆转技术，且定义16 hpps = 无穷距离
RIP路由表是利用一个称作routed (daemon)的应用层进程进行管理， 维护路由选择信息并与相邻路由器中的routed进程交换报文，通告报文周期性地通过UDP数据报发送。路由器在UDP上使用端口520相互发送RIP请求与响应报文。封装在标准IP数据报中的UDP报文段在路由器之间传输。

开放式最短路径优先协议OSPF（Open Shortest Path First）

开放指路由选择协议规范是公众可用的。
OSPF的核心就是一个使用洪泛（向整个AS内广播，而不仅仅是邻居）链路状态信息的链路状态协议和一个Dijksua最低费用路径算法。使用OSPF，一台路由器构建了一幅关于整个自治系统的完整拓扑图（网络AS拓扑图）。
各条链路费用是由网络管理员配置的。
路由器在本地运行Dijkstra的最短路径算法，以确定一个以自身为根结点的到所有子网的最短路径树。
每当一条链路的状态发生变化时（如费用的变化或连接／中断状态的变化），路由器就会广播链路状态信息。
即使链路状态未发生变化，它也要周期性地（至少每隔30分钟一次）广播链路状态。
OSPF通告包含在OSPF报文中，该OSPF报文直接封装到IP数据报中。因此OSPF协议必须自已实现诸如可靠报文传输、链路状态广播等功能。OSPF协议还要检查链路正在运行（通过向相连的邻居发送HELLO报文），并允许OSPF路由器获得相邻路由器的网络范围链路状态的数据库。

OSPF的优点：

1. 安全(security)：所有OSPF报文可以被认证(预防恶意入侵)
2. 允许使用多条相同费用的路径 (RIP只能选一条)，数据多的时候可以负载到多条路径
3. 对于每条链路，可以针对不同的TOS设置多个不同的费用度量。例如，卫星链路可以针对“尽力”(best effort) ToS设置低费用、针对实时ToS设置“高”费用
4. 对单播与多播路由选择的综合支持：多播OSPF(MOSPF)提供对OSPF 的简单扩展，以便提供多播路由选择。它使用现有的OSPF链路数据库，并为现有的OSPF 链路状态广播机制增加了一种新型的链路状态通告。
5. 支持对大规模AS分层

OSPF的分层：
一个OSPF自治系统可以配置成多个区域。每个区域都运行自己的OSPF链路状态路由选择算法，链路状态通告只限于区域内部。
每个路由器掌握所在区的详细拓扑，只知道去往其他区网络的“方向” (最短路径)

如图：局部分层为骨干区域、局部区域。

边界网关协议BGP (Border Gateway Protocol)

BGP为每个AS提供了一种手段:
（1）eBGP: 从邻居AS获取子网可达性信息.
（2）iBGP: 向所有AS内部路由器传播子网可达性信息.
（3）基于可达性信息与策略，确定到达其他网络的“好”路径.
（4）容许子网向Internet其余部分通告它的存在

当一台路由器通过BGP会话通告一个前缀时，它在前缀中包括一些BGP 属性，前缀+属性= “路由”
两个重要属性:
AS-PATH(AS路径)包含前缀通告所经过的AS序列
NEXT-HOP(下一跳)开始一个AS-PATH的路由器接口，指向下一跳AS。可能从当前AS到下一跳AS存在多条链路，NEXT-HOP指明了走哪一条。