读书 (20)


《计算机网络:自顶向下方法》笔记(6):无线网络和移动网络

  • 2019年7月21日
  • 读书

无线网络和移动网络

无线网络的分类根据:1. 分组是否跨越多个无线跳,2. 是否有基站这样的基础设施

  • 单跳 + 有基础设施:普通的室内 Wifi,3G,4G 网络
  • 单跳 + 无基础设施:蓝牙,具有自组织模式的 802.11
  • 多跳 + 有基础设施:无线网状网络。结点为了与某基站通信,需要通过其他无线结点做中继。
  • 多跳 + 无基础设施:移动自组织网络(MANET),车载自组织网络(VANET)。

无线链路的网络特征:信号强度递减,其他信号源干扰,多路径传播。

CDMA,码分多址,对每一个数据比特都进行编码,如 1 编码为(1,1,-1,1,1,1,-1,-1)(实际要长得多),0编码相反。编码后发送到无线链路,每个比特发送都需要 1 比特时隙时间。当无干扰时,接收方通过编码序列(1,1,-1,1,1,1,-1,-1)可以得到原数据比特。当有干扰时,CMDA 认为链路信号是叠加的,不同设备使用不同的编码,信号叠加后,如果编码是精心挑选的,接收方仍可通过编码序列恢复算法恢复特定设备的原数据比特。

WiFi,也称 IEEE 802.11 无线 LAN,从 90 年代研发的许多无线 LAN 标准和技术中胜出。现有几套相关标准:b,a,g。

  • 802.11b,2.4GHz,85MHz 频段,最大速率 11Mbps
  • 802.11a,5GHz,700Mhz 频段,最大速率 54Mbps
  • 802.11g,2.4Ghz,85MHz 频段,最大速率 54Mbps
  • 802.11n,多输出多输入(MIMO),可达几百 Mbps
  • 其他,如 802.11i,使用更安全的加密算法 AES 设计加密协议

这三个标准都是用相同的媒体访问协议 CSMA/CA,使用相同的帧格式,都具有降低传输速率以到达更远距离的能力,都允许“基础设施模式”和“自组织模式”两种模式。但物理层有重要区别。

802.11b 频段和 2.4G 电话与微波炉一样;802.11a 频率高,所以传输距离短,受多径传播影响更大。g 是 b 的速率升级版,向后兼容。

802.11b/g 定义了 11 个部分重叠的信道,仅当 2 个信道间隔 4 个信道以上时才无重叠。

802.11 要求每个 AP 周期性地发送信标帧(beacon frame),包含 AP SSID 和 MAC 地址。设备接收到信标帧后,一般选最高信号强度用于关联。

802.11 的链路层协议,CSMA/CA,带碰撞避免(CA)的载波侦听多路访问,每个站点在传输之前侦听信道,一侦听到该信道则抑制传输。因为无线设备实现碰撞检测因物理特性原因效果不好。

以太网使用碰撞检测;802.11 使用碰撞避免,并使用确认重传(ARQ)来保证较高误比特率下的效率。

802.11 帧:

帧控制 2 | 持续期 2 | 地址1 6 | 地址2 6 | 地址3 6 | 序号控制 2 | 地址 4 | 有效载荷 0~2312 | CRC 4

地址 2:传输该帧的站点的 MAC 地址

地址 1:要接收该帧的站点的 MAC 地址

地址 3:当设备和路由器中间隔着 AP 时,用于定位目的 MAC 地址

当设备移动时,会从一个 BSS 移动到另一个 BSS。如果 BSS 属于同一个子网(此时接入点 AP 是交换机),则 IP 地址不变,TCP 连接保持连接。如果不属于同一个子网(此时接入点 AP 是路由器)

802.11 还有几个特性:

  1. 速率适应:当结点离基站近时,信噪比高,使用高速率;远时信噪比低,发送失败率高,此时用低速率。速率变化的条件是一个结点连续发送两个帧而没有收到确认,则降低速率;如果连续 10 个帧收到确认,则提高速率。策略和 TCP 相似。

  2. 功率管理:结点想要休眠时,会发送帧通知接入点,接入点会缓存休眠结点的所有帧,以后再传输。结点会在信标帧发送前唤醒自己(250us 就能唤醒,而信标帧 100ms 发送一次),然后接入点会在信标帧发送的同时把缓存的帧一并发过来。结点无发送接收帧的情况下,99% 时间都在休眠。

蓝牙,802.15.1 无线个人区域网络(WPAN),2.4 GHz,时隙长度 625us,79 个信道。时隙之间以一个已知的伪随机方式变更信道,称为跳频扩展频谱(FHSS)。速度可达 4Mbps。蓝牙是自组织网络,会建立可多达 8 个设备的皮可网(piconet),其中一个被指定为主设备,其余为从设备。主设备控制皮客网,时钟以主设备为准,奇数时隙中发送,从设备收到后在下一个时隙会回复主设备。蓝牙还可以有多达 255 个寄放设备。

ZigBee,802.14.5,比蓝牙更低功耗,低速率,低成本。ZigBee 定义了 20kbps,40kbps,100kbps,250kbps 的信道速率。

蜂窝因特网,称为 GSM,1G 是模拟 FDMA 系统,专门用于语音通信,2G 是 FDM/TDM,扩展了对数据(因特网)的支持(2.5 G)。3G 4G 提高速率。

移动 IP,是指移动结点在切换不同的接入点时,通讯保持连接无需断开的解决方案。每个移动结点都有一个归属网络(home network),归属网络中执行移动管理功能的实体叫归属代理(home agent)。移动结点当前所在的网络叫外部网络(foreign network),或被访网络(visited network)。与该结点通信的实体叫通信者(correspondent)

外部代理的作用就是为移动结点创建一个转交地址(Care-Of Address,COA),COA 用于将数据报通过外部代理重新路由选择到移动结点。即封装一层转发过去。

版权所有,转载请注明出处:
https://sickworm.com/?p=1741




《计算机网络:自顶向下方法》笔记(5):链路层

  • 2019年7月6日
  • 读书

链路层

链路层协议的任何设备称为结点(node)

沿着通信路径连接相邻结点的通信信道称为链路(link)

链路层协议功能:

  • 成帧(framing)。把数据报(segment)封装成帧。

  • 链路接入。媒体访问控制(Medium Access Control,MAC)用于协调多个结点共享单个广播链路时候的帧传输。

  • 可靠交付。通过确认和重传保证无差错移动每个网络层的数据报。对于差错率低的链路,如光线,同轴电缆等,则不提供可靠交付,由上层保证可靠交付。

  • 差错检测和纠正。(通过校验和)

链路层使用更复杂的 CRC 差错检测是因为其使用了专门的硬件实现。

有两种网络链路:点对点(point-to-point link)链路和广播链路(boardcast link)。

点对点链路使用点对点协议(point-to-point protocol, PPP)和高级数据链路控制协议(high-level data link control, HDLC)。

广播链路涉及协调多个发送和接收结点对一个共享广播信道的访问,也就是多路访问问题(multiple access problem)。对应的协议叫多路访问协议(multiple access protocol)。

多路访问协议可分为三大类:信道划分协议(channel partitioning protocol),随机接入协议(random access protocol),轮流协议(taking-turns protocol)。

信道划分协议:
时分多路复用(Time Devision Multiple,TDM)将时间平均分为多个片,每个信道一个片。优点是公平,简单,缺点是只有一个分组时速度仍然是 R/N,造成资源浪费。
频分多路复用(Frequency Devision Multiple,FDM),把频率分片,优缺点和 TDM 一样。
码分多址(Code Division Mupltiple Access,CDMA),不同节点分配不同的精心选择的编码,使得不同结点可以同时传输。

随机接入协议:
节点总是以全速 R 进行发送,当发生碰撞时,结点会反复等待一个随机时延然后重发,直到无碰撞通过为止。

轮流协议:
轮询协议(polling protocol),其中一个结点指定为主结点,主节点以循环方式轮询(poll)每个结点。优点避免碰撞和随机时延,缺点引入了轮询时延。
令牌传递协议(token-passing protocol)。一个称为令牌(token)的小点的特殊帧在结点之前以某种固定次序进行交换。当结点需要发送帧时,才会持有该令牌,否则会立刻传递给下一个。优点是效率高,缺点是不能兼容单点故障。

—- 20190713 —-

MAC 地址与硬件设备绑定,不会发生变化。

主机和路由器接口除了 IP 地址还有 MAC 地址的原因是:

  • 局域网是为任意网络层协议涉及的,不仅用于 IP 和因特网。

  • IP 是变化的,则 IP 地址必须存在 RAM,且在上电时初始化

  • 保持各层独立。

ARP(地址解析协议,Address Resolution Protocol),IP 转 MAC 地址的转换协议。每台主机或路由器在其内存中具有一个 ARP 表(ARP table),这张表包含 IP 地址到 MAC 地址的映射关系。因为涉及 IP,所以这是一个网络层协议。

如果表中没有对应 IP 地址的记录,则发送一个 ARP 分组(ARP packet)来查询。ARP packet 的目标地址是 MAC 广播地址 FF-FF-FF-FF-FF-FF。子网的所有其他适配器都会收到。如果查询的 IP 地址和自己的 IP 地址匹配,则回复一个相应 ARP packet。

网络层跨网传输时,数据报会首先发送到路由器对应的 MAC 地址,再由路由器转发出去。

以太网是目前为止最流行的有线局域网技术,其他技术还有 FDDI 和 ATM。

以太网一开始在 70 年代是通过同轴电缆总线来互相连接,到了 90 年代后期进化为集线器,使用星行拓扑结构;21 世纪早期进化为交换机(switch)。交换机是“无碰撞的”,是储存转发分组的交换机。

以太网帧结构:

前同步码(8) | 目的地址(6) | 源地址(6) | 类型(2) | 数据(46~1500) | CRC(4)

前同步码用于唤醒适配器,并与发送方时钟同步,是固定的值。前 7 字节 10101010,最后 1 字节 10101011。类型字段用于记录网络层协议。

以太坊是无连接的。

交换机两个功能:过滤(filtering)决定是否要转发这个帧,转发(forwarding)决定帧应该被导向到哪个接口。过滤和转发通过交换机表(switch table)完成。

交换机表内容包含:mac 地址,输出接口,表项建立的时间

当一个帧到达交换机,交换机会查找该帧的目的地址对应的表项。这可能有三种情况:

  1. 没有对应项,此时向所有接口转发(即广播)该帧,后续处理属于自学习功能。

  2. 有表项,但输出接口和收到的接口一致。此时丢弃。

  3. 有表项,且接口不一致。此时转发。

自学习:交换机表一开始可能是空的,但经过一定时间后,交换机可以自行建立出一个可行的交换机表。

交换机可以消除碰撞,兼容不同链路,并且使安全性管理功能称为可能。

交换机和路由器比较:交换机即插即用,性能好,但是是扁平的,单局域网的,不能阻止广播风暴;路由器是分层次的,允许以丰富的拓扑结构构建因特网,但速度慢一些。

虚拟局域网(Virtual Local Network,VLAN)可以提供交换机局域网没有的,流量隔离,不同局域网共享一个交换机,管理用户的功能。

版权所有,转载请注明出处:
https://sickworm.com/?p=1735




《计算机网络:自顶向下方法》笔记(4):网络层

  • 2019年6月23日
  • 读书

网络层

网络层的功能是:分组从一台发送主机移动到另一台接收主机。细分为两个子功能:转发(forwarding)和路由选择(routing)。涉及的协议是:IP,NAT,ICMP。

转发:分组从一个输入链路到达路由器的时候,将其移动到一条合适的输出链路。

路由选择:从发送主机到接收主机的端到端的路由器选择。

每个路由器都有一张转发表,转发表指示一个分组应该移动到哪条输出链路。

某些计算机网络中还有第三种功能,连接建立(connection setup)。因为某些网络体系结构中(包括 ATM,帧中继的体系结构)属于虚电路网络。和因特网的数据报网络不一样,虚电路网络提供恒定速率和连接功能。

转发表的修改是通过路有选择算法进行修改的,这通常每 1 到 5 分钟左右更新一次转发表。

虚电路的概念来源于电话界,呼叫简历和每次呼叫的状态都要在网络中的路由器位置。这显然要复杂的多。复杂的原因是端系统设备(电话)是“哑巴”,他们本身不负责维持过于复杂的状态。而在因特网中,连接状态是由端设备(电脑)维持的,电脑会维护网络层之上的运输层 TCP 的连接。

当路由某个输出端口的分组转移速度赶不上其他输入端口的速度之和时,未处理的分组会放入缓存。当缓存满的时候,就会被路由器丢弃,出现丢包。

IPv4 数据格式:

版本 4bits
首部长度 4 bits
服务类型(TOS) 8bits  // 第七章
数据报长度(16 bits)
标识 16bits
标志 3bits
片偏移 13bits // 这三个与 IP 分片有关
寿命(TTL) 8bits  // 每经过一个路由会减 1
上层协议 8bits // 最终到达目的地才有用,指示了该报文应该交给哪个传输层协议。协议号绑定网络层和运输层,就像运输层的端口号绑定运输层和应用层
首部校验和 16bits
源地址 32bits
目的地址 32bits
选项(可选)
数据 n bits

版权所有,转载请注明出处:
https://sickworm.com/?p=1728




《计算机网络:自顶向下方法》笔记(3):运输层

  • 2019年6月15日
  • 读书

运输层

运输层协议为运行在不同主机上的应用进程之间提供了逻辑通信(logic communication)功能。运输层分组成为报文段(segment)。

TCP 为应用程序提供了几种附加服务。可靠数据传输(reliable data transfer),拥塞控制(congesion control)。

多路复用与多路分解

接收运输层报文段中并交付到正确的套接字的工作称为多路分解(demultiplexing)。

将各个套接字的数据封装并传递到网络层成为多路复用(multiplexing)。

UDP

UDP 是无连接的,他在 IP 层上只增加了多路复用与多路分解(即端口号 port);和差错检测(即校验和 checksum)。

UDP 适合应用的特征:无需连接建立,无连接状态,希望保文尽量精简,不希望过分延迟,且能容忍一些数据丢失。

UDP 校验公式是:每16位为一组相加,溢出回卷,最后结果的反码即是校验和。接收方同样计算出结果与反码相加结果应为 16 位全 1。

UDP 提供差错检测是因为底层链路不一定每一条链路都提供了差错检测,以及内存复制也可能出现差错。

—————— 20190615 ————————

TCP

TCP 是面向连接的(connection-oriented),提供的是全双工服务(full-duplex service),点对点(point-to-point)

TCP 报文包含:32 bits 序号(sequence number,seq),32 bits 确认号(acknowledgment number,ack),16 bits 接收窗口(receive windows),4 bits 首部长度(header length,以 32 bits 为单位),可选变长选项(options),6 bits 标记位(flag)。若 options 为空,则 TCP 头部长度为 20 字节。

累计确认:TCP 只会确认流中第一个丢失字节为止的字节。如 TCP 接收到 0~535 和 900~1000 的报文段,则 TCP 仍在等待 536 的报文段,A 给 B 的下一个报文段的 ack 将包含 536。

报文段的序号就是该报文段数据字段首字节的序号。

seq 即自己的当前报文的首字节序号,ack 即期望的对方的 seq。

TCP 超时时间基于 RTT 的一种计算方法可以是:

// 估算 RTT
EstimatedRTT = 0.875 EstimatedRTT + 0.125 Sample RTT。
// 偏差 RTT
DevRTT = 0.75 DevRTT + 0.25 |SampleRTT - EstimatedRTT|
// TCP 超时时间
TimeoutInterval = EstimatedRTT + 4 DevRTT

而没收到 RTT 时 TimeoutInterval 建议值为 1 秒,超时翻倍。

当接收端发现数据流出现空间隔(可能是中间报文超市或重新排序造成的),此时可以立即发送一个冗余 ACK(duplicate ACK)。如果发送方收到 3 个冗余 ACK,它把这个当作一种指示,即这个被确认 3 次的保文已经丢失。此时 TCP 就执行快速重传(fast restransmit)。

发送方发送 1, 2…N 的报文到接收方,且除 n(n<N)之外的所有报文都接收成功。此时 TCP n 报文超时,TCP 只会重传 n 这个报文段。GBN 风格的重传机制则会重传 n, n+1 … N 的报文段。

对 TCP 提出的一种修改意见是所谓的选择确认(selective actknowledgment)。它允许 TCP 接收方有选择地确认失序报文段,而不是累计地确认最后一个正确接收的有序报文段。此时 TCP 就更像 SR 协议。

TCP 通过让发送方维护一个发送窗口(receive window)来实现流量控制服务(flow-control service),接收方会在回复报文里携带 rwnd 变量,表示当前接收窗口(receive window)的剩余空间。

当接收方缓存空间已满,但接收方没有数据要返回的时候,是不会发送报文给发送方的。此时发送方无法得知 rwnd 变量的情况。TCP 规范要求:接收方接收窗口为 0 时,发送方持续发送 1 字节报文段,直到被接收方确认,返回非 0 rwnd。

握手过程中 SYN = 1,完成握手后 SYN = 0。三次握手的第三阶段已经可以携带数据给 server 了。

  • 第一阶段:SYN = 1,seq = 随机数 client_isn

  • 第二阶段(返回):SYN = 1,seq = 随机数 server_isn,ack = client_isn + 1

  • 第三阶段:SYN = 0,seq = client_isn + 1,ack = server_isn + 1

断开过程需要 4 次握手,因为发起方收到回复时,被动方可能还有数据要继续发。被动方发完后会发送属于它的断开,此时发起方收到后,再次回复,此时双方才真正断开。

TCP 丢包事件定义为:超时或收到接收方 3 个冗余 ACK

TCP 使用确认(ACK)来触发增大它的拥塞窗口长度,确认的快就增大得快

慢启动:在 TCP 慢启动状态下,cwnd 初始值是 1 个 MSS。 MSS 是初始窗口大小的参考值,是控制拥塞的字段。如果 MSS 初始值为 500 字节,RTT 200ms,则速率大约为 20kbps(1s 发 2500 bytes,即 20k bits)。当报文段被确认后, cwnd 会翻倍,即 2 个 MSS,4 个 MSS 地增长。报文段出现丢失的时候,进入拥塞避免(丢包)或快速恢复(3 个 冗余 ACK)状态。

拥塞避免:cwnd 降低为原来的一半。每次确认增加 1 个 MSS,丢包时状态切换和慢启动一致。

快速恢复:cwnd 降低为原来的一半 + 3 个 MSS。每次确认增加 1 个 MSS,丢包时状态切换和慢启动一致。

某些协议如 DCCP,SCTP 和 TFRC 明确地提供了超过 TCP 和 UDP 的强化能力,但多年来已经郑敏 TCP 和 UDP 是“足够好”的,未来“更好”的协议是否会取代 TCP 和 UDP,这将取决于技术,社会和商业考虑的复杂组合。

版权所有,转载请注明出处:
https://sickworm.com/?p=1722




《计算机网络:自顶向下方法》笔记(2):应用层

2.应用层

套接字是应用程序进程和运输层协议之间的接口。

运输层协议特性:可靠数据传输,吞吐量,时延,安全性

运输层提供了 TCP 和 UDP 两种运输服务。TCP 是面向连接的,并提供了可靠的数据传输服务。UDP 不是面向连接的,切不提供可靠数据传输服务。

往返时间 RTT(Round-Trip Time),表示一个短分组从客户到服务器再反悔到客户所花费的时间。RTT 包括分组传播时延,排队时延和处理时延。

HTTP

HTTP 基于 TCP,无需关心数据丢失的问题。HTTP 是个无状态协议,并不会保存关于客户的任何信息。(基于 HTTP 可以实现有状态协议,如 Cookie)。HTTP 请求响应时间大概是 2 个 RTT 加服务器传输 HTML 文件的时间,包含 TCP 三次握手和最后返回数据。HTTP 可使用持续连接模式(keep-alive),这样多次 HTTP 请求可以节省 3 次握手的时间。

HTTP GET 请求报文:

GET /somedir/page.html HTTP/1.1     // 1 请求行,request line
Host: www.someschool.edu            // 2~4 首部行,header line。Host 知名对象所在主机,用于 Web 代理高速缓存
Connection: close                   // 不使用持续连接(使用则为 keep-alive)
User-agent: Mozilla/5.0             // 浏览器类型
Accept-language: fr                 // 语言
// 再附加一个回车换行符(CR LF)结束

HTTP GET 响应报文:

HTTP/1.1 200 OK                     // 1 状态行,status line
Connection: close                   // 2~6 首部行,header line
Date: Tue, 09 Aug 2011 15:44:04 GMT // 服务器产生并发送改响应报文的日期和时间
Server: Apache/2.2.3 (CentOS)       // 服务器类型
Last-Modified: Tue, 09 Aug 2011 15:11:03 GMT // 被发送对象创建或最后修改的时期和时间,用于对象缓存
Content-Length: 6821                // 被发送对象中的字节数
Conent-Type: text/html              // 被发送对象类型
// 再附加一个回车换行符(CR LF)结束 header line
(data data data data data ...)      // 实体体,entity body
// 再附加一个回车换行符结束

条件 GET 方法即在 header line 加入 “If-Modified-Since”,来充分利用本机缓存。如果服务器没有更新该对象,则返回 304 Not Modified,且 entity body 为空;若更新对象则返回正常 200 OK,并带有 entity body。

——- 2019.06.01 ——–

FTP

FTP 使用了两个并行的 TCP 连接来传输文件,一个是控制连接(constrol connnection),一个是数据连接(data connection)。

FTP 协议使用一个独立的控制连接,所以也称 FTP 的控制信息是带外(out-of-band)传送的。HTTP 请求/回复和文件是在同一个 TCP 连接中的,所以 HTTP 是带内(in-band)发送控制信息的。

FTP 控制连接是一直保持的,文件传输每次都建立一个新连接。FTP 会保留用户的状态(state),包括账户,当前目录。状态大大限制了 FTP 的同事维持的会话总数。

FTP 和 HTTP 一样都是可读的。

SMTP

SMTP 是电子邮件使用的服务器间传输协议之一,基于 TCP。HTTP 主要是拉协议(pull protocol),即数据请求方发起链接。SMTP 基本上是推协议(push protocol),即数据发送方发起链接。

SMTP 要求每个报文使用 7 比特 ASCII 码格式。

POP3 / IMAP

POP3(Post Office Protocol——Version 3),IMAP(Internet Mail Access Protocol)协议用于从邮件服务器上取回邮件。

POP3 认证(authorization)后,提供 list,retr,dele,quit 四种命令,完成拉取邮件列表,读取,删除,关闭链接等功能。POP3 的客户端通过这几条命令的组合,可以实现“下载并删除”和“下载并保留”两种模式。

IMAP 比 POP3 复杂,但提供了文件目录功能,可以把邮件分类;也允许只获取部分邮件,如只获取邮件头。

DNS

DNS 是一种主机名到 IP 地址转换的目录服务,是应用层协议。

DNS 还提供了主机别名(host aliasing),邮件服务器别名(mail server aliasing),负载分配(load distribution)功能。

  • 主机别名(host aliasing):提供一个比原主机名(又称规范主机名,canonical hostname)更好记的别名

  • 邮件服务器别名(mail server aliasing):功能同主机别名

  • 负载分配(load distribution):IP 地址集合与同一个规范主机名相联系。

DNS 服务器大致分为三种:根 DNS 服务器,顶级域(Top-Level Domain,LTD,com,org 等就是顶级域名) DNS 服务器和权威 DNS 服务器。

根 DNS 服务器:标号 A 到 M,每个根服务器都是一个集群,2011 年秋季一共有 247 个 根服务器。

还有一类 DNS 是本地 DNS 服务器,每个 ISP 都有一台本地 DNS 服务器(也叫默认名字服务器)。主要为了更高的性能。

迭代查询:请求主机会先访问根 DNS 服务器,得到顶级域 DNS 服务器 IP 地址,再访问顶级域 DNS 服务器得到权威 DNS 服务器 IP 地址,最后从权威 DNS 服务器获取查询的域名对应的 IP 地址。

递归查询:请求主机会先访问根 DNS 服务器,根 DNS 服务器询问顶级域 DNS 服务器,顶级域 DNS 服务器询问权威 DNS 服务器,权威 DNS 服务器返回查询的域名对应的 IP 地址,再沿路返回。

实践中,一般从请求主机到本地 DNS 服务器是递归的,其余是迭代的。

DNS 缓存用于改善时延性能并减少 DNS 报文数量。一般由本地 DNS 服务器做缓存。

DNS 记录和报文

DNS 服务器存储了资源记录(Resource Record,RR)来提供主机名到 IP 地址的映射。格式为:(Name,Value,Type,TTL),TTL 为记录的缓存的生存时间。

  • TYPE = A 时,NAME 为主机名,VALUE 为 IP 地址
  • TYPE = NS 时,NAME 为域,VALUE 为权威 DNS 服务器主机名,用于指向该域应该向哪个 DNS 服务器查询
  • TYPE = CNAME 时,NAME 为别名,VALUE 为规范主机名
  • TYPE = MX 时,NAME 为邮件服务器别名,VALUE 为规范主机名

DNS 只有查询和回答两种报文。

DNS 报文格式:

id[2]   // 用于标识该查询
flag[2] // 包含:查询 or 回答;希望递归;支持递归;等
questionCount[2] // 问题数
responseCount[2] // 回答 RR 数
authorityCount[2] //权威 RR 数
additionalCount[2] // 附加 RR 数

questionRR[questionLen * questionCount] // 查询的名字和类型字段
responseRR[rrLen * responseCount] // 对查询的响应中的 RR
authorityRR[rrLen * authorityCount] // 权威服务器记录
additionalRR[rrLen * additionalCount] // 附加信息

questionLen = len(NAME) + len(TYPE)
rrLen = len(NAME) + len(TYPE) + len(VALUE)

以前 DNS 服务器中的内容都是静态配置的,直到最近才添加了一个新的 UPDATE 选项,允许通过 DNS 报文对数据库中的内容进行动态添加或者删除。

P2P

BitTorrent 协议是一个非常流行的 P2P 文件共享协议。BitTorrent 设有追踪服务器(tracker),当一个对等方想要加入 P2P 网络时,则向追踪服务器注册自己,并周期性地通知追踪服务器自己仍在网络中。

当一个对等方 Alice 加入 P2P 网络时,追踪器会随机从对等方集合选择一个子集的 IP 地址(如 50 个)返回。Alice 将自行连接这些 IP 地址。连接上后 Alice 会从连接上的对等方中获取文件的块列表,并根据一定策略从各个对等方中同步过来完整的文件内容。

P2P 网络的数据库实现可以是分布式散列表(Distributed Hash Table,DHT),BitTorrent 正是使用了 Kademlia DHT 来产生一个分布式跟踪器。这个数据库会存储一系列的键值对,其中 key 为文件名,value 为存储了该文件的对等方 IP 地址。当新的对等方请求下载某个文件时,数据库可以返回持有该文件对等方 IP 地址子集以供下载。

简单粗暴的办法可以是每个对等方都维护一个完整的 DHT 数据库。但这对存储和同步的压力会很大。一种精确有效的办法是:为每个对等方分配一个 [0, 2^n – 1] 之间的标识符,对每一个文件都进行 hash,hash 的取值范围也是 [0, 2^n – 1]。然后该文件选择临近的标识符对应的对等方来存储。

那么当我们知道一个文件的 hash 值,需要找到最近的对等方时,应该如何寻找呢?遍历显然是不可取的。其中一个解决方案是 DHT 网络将所有节点组织成一个环形网络,一个对等方只和自己的直接后继和直接前任联系。然后增加一些捷径路径,来大大降低请求需要的报文数量。而捷径的数量选择需要严格的数学论证。目前研究可知,捷径数量和报文数量(与经过的对等方成正比)数量均为 O(log N)。

当某个对等方突然离开时,以该对等方为第 N 后继的节点,会用第 N + 1 个后继代替第 N 后继,然后用新的第 N 后继(旧的第 N + 1 后继)的直接后继作为第 N + 1 个后继。

版权所有,转载请注明出处:
https://sickworm.com/?p=1717




《计算机网络:自顶向下方法》笔记(1):计算机网络和因特网

1. 计算机网络和因特网

网络传输基于协议运行。一个协议定义了在两个或多个通信尸体之间交换的保温格式和次序,以及报文发送/或接收一条报文或其他事件锁所采取的动作。

因特网是一个特定的计算机网络,也是目前最大的计算机网络。

客户端经过一个接入 ISP(Internet Service Providers,网络服务提供商) 与因特网相连。接入 ISP 的接入技术包括 DSL,电缆,FTTH,Wifi,蜂窝等。接入 ISP 不必是电信运营商,也可以是公司,学校这样的单位。

现在的 ISP 网络结构是:客户端接入到低层 ISP,低层 ISP 接入到高层 ISP,较高层 ISP 彼此互联。

分组交换网的时延种类包括,节点处理时延,排队时延,传输时延,传播时延。传输时延与发送速率(带宽)有关,传播时延与物理链路(材料特性)和节点间距离有关。

因特网协议栈:

  • 应用层(如 HTTP)分组:message(报文)
  • 传输层(如 TCP)分组:segment(报文段)
  • 网络层(IP)分组:datagram(数据报)
  • 链路层(如 WiFi,以太网)分组:帧(frame)
  • 物理层:与具体传输媒体有关

OSI 参考模型:比 TCP/IP 在应用层和传输层之间增加了,表示层(represent)和会话层(session)。TCP/IP 协议决定让这两层交给应用开发者处理。

版权所有,转载请注明出处:
https://sickworm.com/?p=1715




《敏捷软件开发:原则、模式与实践》笔记(4)

  • 2019年3月25日
  • 读书

第 10 章 Liskov 替换原则(LSP)

一个模型,如果孤立的来看,并不具有真正意义上的有效性。模型的有效性只能通过它的客户程序来体现。能解决问题的模型才是好模型

IS-A 的关系是就行为方式而言的。Rectangle 可以单独设置长宽,Square 不可以,他们的行为是不一致的。(但如果边长只能在创建时设置,那其余部分的行为是可以一致的。所以还是要看如何使用。)

可以通过编写单元测试的方法指定契约(约定,如 Rectangle 设置完 width 之后 height 不变)。

Line(线) 和 LineSegment(线段) 的 LSP 问题:Line 有两个点 p1,p2,还有一个 isOn 虚函数,返回该点是否在线上。LineSegment 继承于 Line,也有 isOn 函数。但 LineSegment 的 isOn 的行为与 Line 不一致,导致 LineSegment 作为 Line 时导致函数结果异常。解决办法是:抽取 Line 和 LineSegment 的公共部分,作为 LineObject,Line 和 LineSegment 分别继承它。

第 11 章 依赖倒置原则(DIP)

高层不应该依赖于低层,二者都应该依赖于抽象。
抽象不应该依赖于细节,细节应该依赖于抽象。

依赖倒置原则的核心就是要我们面向接口编程。

Don’t call us,we’ll call you.

第 12 章 接口隔离原则(ISP)

ISP 用来处理胖接口所具有的的缺点。胖接口可以分解成多组方法。每一组方法都服务于一组不同的客户程序。

不应该强迫客户依赖于它们不用的方法。如果强迫客户程序依赖于那些它们不适用的方法,那么这些客户程序就面临着由于这些未使用的方法的改变所带来的的变更。

版权所有,转载请注明出处:
https://sickworm.com/?p=1691




《敏捷软件开发:原则、模式与实践》笔记(3)

  • 2019年3月17日
  • 读书

第二部分 敏捷设计

敏捷团队不会花费许多时间去预测未来的需求和需要,也不会试图在今天就构建一些基础结构去支撑那些他们认为明天才会需要的特性。

第 7 章 什么是敏捷设计

软件系统的源代码是它的主要设计文档,用来秒回源代码的图示只是设计的附属物而不是设计本身。

设计的臭味:

  • 僵化性(Rigidity):很难对系统改动,一个改动需要其他部分一起改动。
  • 脆弱性(Frgility):系统的改动会导致其他概念无关的地方出现问题。
  • 牢固性(Immobility):很难解开系统,抽取出重用组件。
  • 粘滞性(Viscosity):做正确的事情比做错误的事情更难。(实现或变更一个需求时,生硬的方法很简单,保持系统设计的方法很难;或开发环境迟钝低效时,开发人员会倾向于做不会导致大规模重编译的改动,即使那些改动不再保持设计)
  • 不必要的复杂性(Needless Complexity):设计中包含不具有任何直接好处的基础结构。
  • 不必要的重复(Needless Repetition):设计中包含重复结构,而该重复结构本应使用单一抽象进行统一。
  • 晦涩性(Opacity):很难阅读,理解。没有很好的表现出意图。

设计的退化是因为需求没有设计遇见的方式进行变化。改动很急迫,且改动人员对原始设计并不熟悉。

在要实现新需求时,团队抓住这次机会去改进设计,以便设计对于将来的同类变化具有弹性,而不是设法去给设计打补丁。

在不知道某个需求是否会变化的时候,现在就添加额外的保护没有任何现实意义。如果需要这种保护时,应能非常容易的添加。

不能接受代码腐化。

第 8 章 单一职责原则(SRP)

就一个类而言,应该仅有一个引起它变化的原因。如果一个雷承担的职责过多,一个职责的变化可能会削弱或职责和抑制这个类完成其他职责的能力,从而导致脆弱的设计。当变化发生时,设计会遭受到意想不到的破坏。

职责:变化的原因(a reason for change)。

仅当变化实际发生时考虑 SRP 或任何其他原则才具有意义,如果没有征兆就考虑是不明智的。

第 9 章 开放-封闭原则(OCP)

OCP 对于扩展是开放的,对于更改是封闭的。

一般而言,无论模块是多么的“封闭”,都会存在一些无法对之封闭的变化。没有对于所有的情况都贴切的模型。

遵循 OCP 的代价是昂贵的,创建正确的抽象是要花费开发时间和经理的,同时也增加了复杂性。开发人员有能力处理的抽象的数量也是有限的。OCP 的应用应限定在可能会发生的变化上。所以我们应该进行适当的调查,提出正确的问题,并且使用我们的经验和一般常识。最终,我们会一直等到变化发生时才采取行动。

通常,我们更愿意一直等到确实需要哪些抽象时再把他放置进去。

使用数据驱动的方式获取封闭性。

版权所有,转载请注明出处:
https://sickworm.com/?p=1687




《敏捷软件开发:原则、模式与实践》笔记(2)

  • 2019年3月10日
  • 读书

第六章 一次编程实践

原文保龄球规则:(文末)

https://www.twblogs.net/a/5b957acb2b717750bda47bd5/zh-cn/

原文需求:

记录一届保龄球联赛的所有比赛,确定团队等级,确定每次周赛优胜者和失败者,每场比赛成绩

初步分析数据结构:

  1. 计分数据
record {
    uint32 id primary auto_increase,
    uint8 round0_0,
    uint8 round0_1,
    uint8 round1_0,
    uint8 round1_1,
    ...
    uint8 round9_0,
    uint8 round9_1,
    uint8 round10_0,
    uint8 round10_1,
    uint8 round10_2,
}

不存储最终该轮得分,该轮得分由函数提供计算,防止冗余数据和出现数据冲突。

  1. 团队数据
team {
    uint32 id primary auto_increase,
    string name,
    string religin,
    uint32 level
}
  1. 比赛数据
match {
    uint32 id primary auto_increase,
    uint64 time,
    uint32 team_a,
    uint32 team_b,
    uint32 record_a_id,
    uint32 record_b_id,
    uint32 winner_id,
}

winner_id 稍微考虑了一下 2 队比赛和多队比赛的可能性(不熟悉规则),以及后期搜索数据的效率。所以不使用 bool 类型。

通过比赛 id 可以构建比赛的三角形淘汰图。

疑问:是否需要计算中的轮数的分值?为了用户体验,默认需要。

初步分析代码:

public class Score {
    public static final int ROUNDS = 10;
    public static final int FULL_HITS = 10;
    public static final int TEN_ROUNDS_THROWS = 20;
    public static final int TOTAL_THROWS = TEN_ROUNDS_THROWS + 1;

    // 10 轮计分
    private int[] scores = new int[ROUNDS];
    // 如果是全中轮,则第二轮直接赋值 0,将特殊情况普通化。第十轮可能扔 3 次,所以一共 21 次。
    private int[] throws = new int[TOTAL_THROWS];

    public void currentRound = 0;
    public void currentThrowIndex = 0;
    // 用于友好标记不再变化的分数
    public void determinedScoreRound = -1;

    public void throw(int hits) {
        if (!isPlaying()) {
            throw new IllegalStateException("it is ended");
        }

        if (hits < 0 || hits > FULL_HITS) {
            throw new IllegalStateException("illegal throws score");
        }

        boolean isRoundEnd = updateThrowsAndRounds();
        if (isRoundEnd) {
            updateScores();
        }
    }

    private boolean updateThrowsAndRounds() {
        throws[currentThrowIndex++] = throws;
        if (throws == FULL_HITS) {
            if (isAllFullHits() || isAllOneShot()) {
                if (currentThrowIndex == TOTAL_THROWS) {
                    currentRound++;
                    return true;
                }
            } else {
                throws[currentThrowIndex++] = 0;
                currentRound++;
                return true;
            }
        }
        return false;
    }

    private void updateScores() {
        if (isOneShot(beforeLastRound)) {
            final int calculateShots = 2;
        }

        while (int i = determinedScoreRound + 1; i < currentRound; i++) {
            if (updateScore(i)) {
                determinedScoreRound = i;
            }
        }
    }

    /**
     * @return boolean is the score determined
     **/
    private boolean updateScore(int round) {
        int score = throws[round * 2] + throws[round * 2 + 1];
        if (round == 0) {
            scores[round] = score;
            return true;
        }

        int lastRound = round - 1;
        score += scores[lastRound];
        boolean lastRoundDetermined = determinedScoreRound >= lastRound;

        int calculateShots = 0;
        boolean needDeteminedRound = round;
        if (isOneShot(round)) {
            int calculateShots = 2;
            needDeteminedRound = round + 2;
        } else if (isFullHits(round) {
            int calculateShots = 1;
            needDeteminedRound = round + 1;
        }

        int nextRound = round + 1;
        while (calculateShots > 0 && nextRound < currentRound) {
            score += throws[nextRound * 2];
            calculateShots--;

            if (isOneShot(nextRound)) {
                nextRound++;
                continue;
            }

            score += throws[nextRound * 2 + 1];
            calculateShots--;
            nextRound++;
        }

        scores[round] = score;
        return lastRoundDetermined && calculateShots = 0;
    }

    public void isPlaying() {
        return currentRound < ROUNDS;
    }

    public void getRounds() {
        return currentRound + 1;
    }

    private boolean isOneShot(round) {
        return throws[round * 2] == FULL_HITS;
    }

    private boolean isFullHits(round) {
        return throws[round * 2] + throws[round * 2 + 1] == FULL_HITS;
    }

    // 10 轮补中
    private boolean isAllFullHits() {
        if (currentThrowIndex < TEN_ROUNDS_THROWS) {
            return false;
        }
        for (int i = 0; i < currentRound; i++) {
            if (!isFullHits(i)) {
                return false;
            }
        }
        return true;
    }

    // 10 轮全中
    private boolean isAllOneShot() {
        if (currentThrowIndex < TEN_ROUNDS_THROWS - 1) {
            return false;
        }
        for (int i = 0; i < currentRound; i++) {
            if (!isOneShot(i)) {
                return false;
            }
        }
        return true;
    }
}

阅读原文

做出思考后开始看文章。

首先发现文章一开始提出了 Frame 和 Throw 的概念,而我的代码跳跃性的直接用 int 和 int[] 作为表示。尽管文中也讨论了是否需要这两个对象,但我觉得确实对象化确实是应对复杂软件的良好解决办法。

到了文章中部,他们也用到了 21 和 currentThrow,currentFrame 这两几概念,但很快被质疑了,因为他们不易理解。而不易理解意味着难读懂,更意味着程序容易出错。

同样文中的 scoreForFrame 和我的 updateScore 功能相似。但他们一开始就想到这样设计,因为他们是测试驱动的,或者说是使用用例驱动的。而我是在编写的最后发现原有办法(每次 throw 更新几个 round 的值)难以编写才想出来的。

文中没有 scores 数组,取值由函数代替。这符合尽量简单的原则,依照他们的思路,确实也不需要这个。我现在觉得我这个 scores 数组也非常累赘。

文中先考虑一般情况,再考虑特殊情况,这也是正确的。我在实现一般情况的时候总是会想特殊情况,并将其兼容,这样不利于一个正常流程的实现。

文中的程序性能较差,因为每次获取分数都要从 0 算起,但也减少了很多没必要的变量,例如我的 determinedScoreRound。再说,这程序需要考虑性能吗?

文中代码再持续不断的被重构。每次增加新功能和修改代码,都会重新跑一次测试用例。这非常舒服。

文中目前貌似没有处理全中和补中要投多一次的情况?测试用例只覆盖了分数,没有轮数。

不太赞同为了独立 handleSecondThrow 把好几个局部变量变成全局变量。不过后面的重构也优化了一些,也许先移出去简化结构也是一种好的办法。但 ball 这个临时状态变量还是存在。

ball 也被移到一个计算分数的类 Scorer 去了。

文中最后否定了 Frame 和 Throw 这两个类,增加了 Scorer 类。文中倡导从 Game 开始设计,即自上而下设计。

文中通过限制轮数最大为 11 来处理多投一次的情况,超过 11 轮还是等于 11 轮。是否允许多投 1 或 2 次取决于输入(裁判)。

文中提到,大意:增加各种类来提高软件通用性不等于易于维护(需求变更),易于理解才时易于维护的。

版权所有,转载请注明出处:
https://sickworm.com/?p=1683




《敏捷软件开发:原则、模式与实践》笔记

  • 2019年3月2日
  • 读书

第一章:敏捷实践

敏捷开发要点节选:

  • 结对编程
  • 集体代码所有权:所有人可以在任何时候改进所有代码
  • 隐喻:团队提出一个程序工作原理的公共景象

如果把程序员团队当做是组件(component),那么就无法对他们进行管理。人不是“插入即兼容的编程装置”。如果想要项目取得成功,就必须构建具有合作精神的,自组织的(self-organizing)的团队。

一个大而笨重的过程会产生它本来企图去解决的问题。它降低了团队的开发效率,使得进度延期,预算超支。它降低了团队的相应能力,使得团队经常创建错误的产品。

代码是唯一没有二义性的信息源。

计划会遭受形态(shape)上的改变,而不仅仅是日期上的改变。所以预先制定好的详细的计划图是不适用的。正确做法是:为下两周做详细计划,为下三个月做粗略的计划,再以后做极为粗糙的计划。

跑得过快会导致团队经理好景,出现短期行为一直与崩溃。敏捷团队会测量他们自己的速度。他们不允许自己过于疲惫。他们不会借用明天的经理赖在今天多完成一点工作。他们工作在一个可以使在整个项目开发期间保持最高质量标准的速度上。

敏捷团队会不断地对团队的组织方式,规则,规范,关系等进行调整。敏捷团队知道团队所处的环境在不断地变化,并且知道为了保持团队的敏捷性,就必须随环境一起变化。

第二章:极限(eXtreme Programming)编程概述

在离真正实现需求还很早时就去补货该需求的特定细节,很可能会导致做无用功以及对需求不成熟的关注。在XP中,我们和客户反复讨论,以获取对需求细节的理解,但是不去捕获那些细节。

测试驱动的开发方法:编写所有产品代码的目的都是为了使失败的单元测试能够通过。

简单的设计:XP 团队使他们的设计尽可能地简单,具有表现力(expressive)。这意味着 XP 团队的工作可能不会从基础结构开始,他们可能并不先去选择使用数据库或者中间件。团队最开始的工作是以尽可能最简单的方式实现第一批用户素材。

因为添加特性和处理错误导致代码结构逐渐退化,XP 团队通过经常性的代码重构来扭转这种退化。重构是持续进行的,是每个一个小时或者半个小时就要去做的事情。通过重构,我们可以持续低保持尽可能干净,简单并且具有表现力的代码。

第三章:计划

所有大的用户素材(user stories)都应该被分解为小的素材,过小的素材应该和其他过小素材合并。

“用户能够安全的进行存款,取款,转账活动。”可以被分解为:

  • 用户可以登录
  • 用户可以退出
  • 用户可以向其账户存款
  • 用户可以从其账户取款
  • 用户可以从其账户向其他账户转账

团队的开发速度在实现数个素材后可以估算出来,确定素材和开发速度后就可以估算开发时间。

客户挑选在某个发布中他们想要实现的素材,并大致确定这些素材的实现顺序。

分配的任务应该是 4~16 小时内实现的一些功能,多个任务组成一个素材。

迭代进行到一半的时候,此时半数素材应该被完成,如果没有完成,团队会设法重新法分配任务和职责。如果不能重新分派,则由客户决定从迭代中去掉一个任务或素材,或指出哪些最低优先级别的任务和素材。

如果完成了 90% 任务,但却没有完成素材,这是没有意义的。

迭代结束后,应该给客户演示当前可运行的程序,让客户评价并以新的用户素材进行反馈。

第四章:测试

测试驱动开发使你的代码都是对测试友好的。

测试可以作为一种无价的文档形式,如果想知道如何调用一个函数或者创建一个对象,会有一个测试战士给你看。

在实现钱,现在测试中陈述你的意图,使你的意图尽可能地简单,已读,你相信这种简单和清除会给程序指出一个好的结构。

MockObject 用于配合目标类的功能测试,相对比真实实现类好更好控制一些。

单元测试是白盒测试,验收测试是黑盒测试。

在项目迭代的初期,会受到用手工的方式进行验收测试的诱惑。但是,这样做使得在迭代的初期就丧失了由自动化验收测试的需要带来的对系统进行解耦合的促进力。

测试套件运行起来越简单,就会越频繁地运行它们。运行的越多,就会越快地发现和那些测试的任何背离。

第五章:重构

每一个软件都具有三项职责:

  • 运行起来所完成的功能
  • 应对变化,开发者有责任保证这种改变应该尽可能简单
  • 和阅读它的人沟通

代码应能够清晰的表述各个子流程的意义,最常用的方法是将其封装为一个函数。

版权所有,转载请注明出处:
https://sickworm.com/?p=1678