ZingLix Blog

凡心所向,素履以往

IP 地址格式

子网与 CIDR

IP 地址的表示 IPv4 的地址有 32 位长,一般以 8 位一组换成十进制,中间以点分割。 点分四组 二进制 0.0.0.0 00000000 00000000 00000000 00000000 1.2.3.4 00000001 000000...

UDP 特点及报文结构

在运输层中,最为重要的两个协议就是 TCP 和 UDP。相对于 TCP 巨细无遗的处理了各种情况,UDP 只提供了最小的功能,几乎就是在直接使用 IP 协议。UDP 面向报文,只负责将报文传输给对方,不做任何拆分或拼接处理。 特点 UDP 的整体思想就是以牺牲功能(可靠性)为代价,换来更高的效率。 没有差错纠正。UDP 仅提供差错检测功能,以最小化额外消耗。 不可靠。UDP ...

TCP 拥塞控制

TCP 协议实现可靠传输的核心在于确认重传,而重传意味着消耗更多的资源。然而在一个拥塞到快崩溃的网络中,十分容易发生丢包,而这又会触发重传,从而使得网络条件更加糟糕,为此 TCP 设计了拥塞控制算法。 概述 为了能够控制发送速度,TCP 中有一个 拥塞窗口 变量(congestion window, cwnd),配合滑动窗口中的接收窗口 rwnd,所以网络中发送速度为两者间的较小值。cw...

TCP 流量控制与滑动窗口

一般来说,对于接收方数据抵达时接收方可能忙于其他事情并不能立即处理数据,所以会设置一个接受缓存,并使得收到的数据正确有序。由于缓存有一定大小,这时发送方发送太快就会使得很多数据因缓存满了而丢弃,导致不必要的重传,这时就需要称为 滑动窗口 的流量控制措施。 TCP 协议是一个全双工协议,所以双方都既是发送方又是接收方,下面两个窗口虽然是针对特定一方,但实则双方都会维护两个窗口。 发送窗口 ...

TCP 可靠数据传输的实现

超时与重传

TCP 的数据传输 TCP 建立于 IP 协议之上,而 IP 协议是一个尽力而为的协议,所以可靠性由 TCP 自己实现。TCP 将数据看成一个无结构的、有序的字节流,头部有序列号和确认号两个字段用于实现数据的可靠传输。 TCP 将报文段看成字节流,每个字节都有对应的编号,序列号记录的就是 报文段中字节流第一个字节的编号,而不是报文段的序号。例如传输一个大型的文件,MSS(最大报文段长度)...

TCP 概述及报文结构

TCP 数据报封装于 IP 数据报中,在 IP 的不可靠尽力而为的服务上创建了 可靠数据传输服务。 TCP 有自己的 连接管理机制,基于 确认重传 实现了数据传输的可靠性。在此基础上加上了 流量控制 保证接收方成功接收和 拥塞控制 避免网络阻塞,这些构成了 TCP 协议的核心。 流量控制和拥塞控制都涉及到了窗口这一概念,都是为了降低传输的速度,但处理的是不同的场景。 流量...

TCP 连接管理

三次握手和四次挥手

TCP 连接分为三个部分:启动、数据传输和退出。 连接建立 建立一条 TCP 连接需要完成以下三步: 客户端将一个特殊的 TCP 报文封装在一个 IP 数据报中发送给服务器端,其中不包含任何应用层数据但 SYN 置为 1 以表明想要建立一条连接。同时会发送客户端的初始序号 client_isn 以及选项(如果有的话)。 服务器收到后,如果同意建立连接的话会返回一个 SYNAC...

Logistic 回归、梯度下降及向量化

深度学习学习笔记 - Week 1 & 2

神经网络概述 神经网络的目标与一个普通的函数相同,即给定输入,期望得到一个处理后的结果,只不过有些时候输入输出间的关系十分复杂,而神经网络可以通过学习的方式得到输入输出之间的关系。 上图即为一个神经网络,分为输入层、隐藏层和输出层,其中隐藏层就是神经网络的关键所在。其中每个圆圈代表一个“神经元”,而箭头则代表这些数据影响着所指的神经元,并一层层最终影响结果。 Logistic 回归...

最大流问题

Maxflow Problem

例如传递一批货物,有不同的路径可以走,但是每条路上有传递货物数量的上限,那么在整个网络中如何能同时传递最多的货物,这样的问题称为 最大流问题 。 一、定义 流网络 流网络是一个有向图,且具有以下性质: 每条边都有一个 非负 的容量值 \(c(u,v)\) 如果存在一条边(u, v),那么 不存在 反向的边(v, u) 图中有两个特殊节点,源结点(source)和 汇点(...

单源最短路径算法

Single-source Shortest Paths

一、问题描述 在图算法中,从某点开始,计算到其他点最短的路径是十分常见的问题,而这一问题有许多变种,本文着重于从某点开始到图中所有其他点的最短路径,称为 单源最短路径问题(Single-source Shortest Paths)。 二、特殊情况 负权重的边 在单源最短路径中,负权重的边并非不允许存在,但要求是不存在从源结点可以到达权重为负的环路。因为如果存在可以抵达的权重为负的环路...