计网学习笔记

发表于 | 分类于 | 阅读量： 次

概述

计算机网络（Computer Network）复习笔记

参考书目：《计算机网络自顶向下方法（第5版）》机械工业出版社

CH1-Introduction of Networking-1

杂记：

CN负责数字通信（数字信号）

哈罗车筐前黑色是太阳能板？

宿舍-一层-一楼-学校网络中心-南京教育网（东大）-全国教育网

第一台联网计算机在UCLA

remote medicine 瓶颈在于时延

行星间联网，光速瓶颈

因特网是一个复杂系统，分解为5个子问题，谁来分解？如何分解？

课程主要讲述：

  1. 因特网如何工作？
  2. 子问题为什么这样解决？

讲解顺序：

  1. 基础：包、链路、复用、时延、丢包
  2. 低级技术：以太网，无线局域网，3g，4g
  3. IP，路由，BGP
  4. 网络互通后如何交换信息：DNS,CDN,HTTP,TCP
  5. 热点问题：数据中心、

课程任务：

  1. 实验25%（现场提问，验收，改代码，严格）
  2. 作业15%
  3. 期末考试60%

交换方式

  1. 电路交换：最基础的交换方式。点对点
    特点：
    1. 中间所有资源都预留好
    2. admission control per connection
  2. 包交换：大家都把数据分为小数据包，一股脑发到交换机，交换机再转发，自由竞争，冲突了就丢一个，一个小包失败了就再发一次。（核心思想：统计复用）
    特点：
    1. 包独立处理
    2. admission control per packet
  3. 虚链路：在包交换中模拟电路交换给vip用户优先权，以便冲突时优先满足vip用户

电路交换

电路交换：在两点之间建立通道，src和dst之间直接连接（中间类似于多刀多掷开关）

建链-传输-拆链。想象成老电影里的电话局，处长和局长通话需要接线员接线、通话、拔线。

时间分片：比如，将1ms分为1000片，1000个用户同话，用户1通话时只占用1ms的第1片，然后若干个1ms组成了通话时间。如果有人通话量大，就多分几片。

频率分片：将频率切片，比如1Mhz的一段切成100片分给不同的用户，实际上要分很多级/空间复用，不然没法满足几亿用户的分配需求，频率之间不干扰，频率由国家法律严格控制，比如联通被分在800-850Mhz。

低频波的波长长，容易绕开障碍物。所以停用2G用户，这样子那一段频率就可以用来给5G了。

1G频分，2G时分，后面的利用更高级原理。

电路交换的时序图1

为什么建链时有delay，拆链时没有delay？
因为建链时，需要预留电路，要时间，可能会失败。拆链直接拆就行。

电路交换的时序图2

传输data时，不一定是连续的，不传输的时候就浪费了。比如2G/3G时代的手机QQ，发一个消息要建链-拆链一次，电费消耗大。在传大文件或者看电影才划算。

优点：

  1. predictable performance（保证一定送到，速度也有保障）
  2. simple/fast switching (once circuit established)（建链后很简单）

缺点：

  1. complexity of circuit setup/teardown（建链和拆链很麻烦）
  2. inefficient when traffic is bursty（上述手机QQ的浪费、驿站的一匹马只运输一串荔枝，但实际上可以驼很多东西，这些空间浪费了。）
  3. circuit setup adds delay（建链需要一来一回，增加时延，聊微信会很花时延）
  4. switch fails->circuit fails（建链失败就完蛋）

相似工作原理：华为手机之所以省电，在于有1个主CPU和几个小CPU，微信等通过小CPU。天线也是自己开屏幕才会工作，所以微信可能会收到不及时。

包交换

包交换：通信时像快递一样，只要写好每个数据包发货地址和收货地址，交换机只要负责查地址，就可以发了。核心思想是统计复用。

不保证性能：如果一大堆人同时发包，只能送一个，其他丢掉。或者用一个buffer缓存一下，再发。

优点：

  1. Efficient use of network resources
  2. simpler to implement（要求交换机做的事情很少，复杂的事交给端系统完成，就很便宜）
  3. robust: can “route around trouble”（不存在链路建立失败的问题，比如一家快递倒闭了我换一家就可以了）

缺点：

  1. unpredictable performance（由于buffer容量有限，只能保证大部分快递不送丢，类比双11快递公司的爆仓）
  2. requires buffer management and congestion control（需要管理仓库和拥塞控制，管理仓库是这个快递费20，那个快递费5块，冲突就丢掉5块的。拥塞控制是双11短期取货码（被动，拥塞已经发生）、提前两三周开始双11（主动从源头控制）、南大驿站装不下就返回到上一级驿站）

统计复用 statistical multiplexing

Allowing more demands than the network can handle.

  • hoping that not all demands are required at the same time（小区接入宽带，允许10个用户100M，但只给他们分配100M，因为假定他们不会同时用网，且一家人用不了100M。）（旅馆也住不了那么多人，正常情况下不会这么多人同时去住，如果想专享线路，建个行宫吧）

  • results in unpredictability（世界杯期间突然爆满）

  • works well except for the extreme cases（爆满的情况不符合统计复用的条件）

如何评价网络性能

  • 时延delay
  • 丢包率loss
  • 吞吐量throughput（速率）

无线网络侧重于丢包率

数据中心侧重时延

时延

Consists

  • transmission delay (link，取决于带宽，$数据量/带宽$)
  • propagation delay (link，取决于路长，$长度/光速$)
  • queueing delay
    (取决于来的包，冲突就进队列，队列溢出就丢掉，由于包有编号，接收端数一数123457，丢了6号，那么通知发送方重发)(按均值和variance来衡量，由排队论设计好)（数据中心的主要时延）（平均排队时长）

    Littes’s law(1961)
    L = A * W

  • processing delay (有但可以忽略不计了，和电子工业发展有关)

链路带宽bandwidth：八车道的八（同时有几个比特在链路里跑）

BDP = Bandwidth * propagation delay

$1G=10^9$

对于小文件，$D_{prop}$占主导，对于大文件，$D_{trans}$占主导时延

普通交换机遵循store-forward模式，交换机收到包先存起来解析包头再发下一站。
端(trans,prop,queue&process)交换机()交换机()端

高频交换机（高频率股票交易）不遵循上述模式
带宽极高不用queue，收到1bit就直接发。

丢包loss

吞吐率throughput

transmission rate R bits/sec

file of size F bits
packets of size L bits

Transfer time(T) = F/R + propagation delay

木桶原理，端到端的速率取决于最细的那一段

Little laws的证明

$
\begin{equation}
\lambda\overset{def}{=}\lim\limits_{t\to \infty} \frac{N(t)}{t}, \text{the arrival rate into the system}
\end{equation}
$

$
\begin{equation}
\omega\overset{def}{=}\lim\limits_{n\to \infty} \frac{1}{n}\sum\limits_{j=1}^{n}W_j, \text{average sojourn time}
\end{equation}
$

$
\begin{equation}
l\overset{def}{=}\lim\limits_{t\to \infty} {\frac{1}{t}\int_{0}^{t}L(s)ds}, \text{average number in system}
\end{equation}
$

$
L(t):\text{the total number of customers in the system at time t.}
$

$
N(t)=max{n:t_n\leq t}
$

$
L(t)=\sum\limits_{n=1}^{\infty}{I{t_n\leq t\leq t_n^a}}=
$

$
\frac{1}{t}\sum\limits_{j:t_j^{\alpha}\leq t}{W_j} \leq \frac{1}{t}\int_{0}^{t}{L(s)ds} \leq \frac{1}{t}\sum\limits_{j:t_j < t}{W_j}
$

后者=$ \lim\limits_{t\to \infty} \frac{N(t)}{t} \frac{1}{N(t)}\sum\limits_{j=1}{N(t)}W_j $

Lemme: if $\lambda$ and $\omega$ exists and finite, then
$$ \lim\limits_{n\to \infty}{\frac{W_n}{n}=0}, \lim\limits_{n\to \infty}{\frac{W_n}{t_n}=0} $$

前者手机图片

协议

层与层之间没有耦合关系，所以更新时候方便。

OSI七层（L7应用层，L6表示层，L5会话层），TCP\IP五层

沙漏状的五层：（海淘）
应用层-CEO写的内容（确定到南大的哪个人）（千万种协议）
传输层-秘书（写美国哪个州哪个县）（TCP可靠，UDP不可靠）
网络层-全球可达（only IP，基石）
链路层-局部可达
物理层-计科不管

应用层->传输层，加header指明给对方的哪个进程
传输层->…，类似

端系统5层全要，中间的交换机只要下3层即可，负责信息的到达（联邦快递）。

传输层和网络层原本部署在 CPU 上，现在为了快速转到了网卡上。

pros:

  1. reduce complexity（分而治之）（负责分拣的就分拣，运货的就运货）
  2. improve flexibility（每一层只对上层负责，内部实现可以改）（用飞机送和用马车送）

cons:

  1. higher overheads（每一层的header，占总大小5%-8%）
  2. cross-layer information often useful（上下层可以互相偷窥对方的内容，因为只是加了header）

IP层不好改，打过了很多补丁。IPv4->IPv6的演进。就像给行驶中的高铁换轮子还不能让高铁发现。
IPv4是32bit的，所以它只能有4G个地址，不够用。

End-to-end argument
中间节点越简单越好，只负责转发就行了，复杂的事情交给终端。不然中间的设备太复杂成本高。

墙的效果：在物理层偷窥应用层，不符合要求就咔嚓

总结

  1. 分层很棒
  2. 网络层最重要，将应用和底层完全隔离开
  3. E2E arguments 激励我们 keep IP simple

第2章 链路层

术语
L3: packet
L2: frame

  • framing（将 L3 的 packet 封成 frame）
  • link access（宿舍四个人在使用同一个物理机，决定谁来用）
  • reliable delivery（应对错误和丢包丢 frame，用于无线网/基站通信，一个包发两次或者其他保护机制）
  • error detection and correction（包收到了，但内容不对，用校验码，纠错码）

传输方式：

  • point to point（海底光缆，电话线，以太网-墙上的网口）
  • broadcast（无线局域网，不安全= =，几个人会同时讲话）

广播 broadcast

广播方式中，物理媒介是共享的，如何决定谁说话？

  • channel partitioning: 切片，一人一片，类似电路交换，分频率，效率不高
  • taking turns: 轮流上
  • random access: 每个人想发就发，协议决定谁发（不避免 collision，而是解决 collision）（分布式）

random access protocol(MAC)
do: detect and recover from collisions

所谓 protocol:

  • pattern（先说一句hello）
  • senmatic（然后开始交流）

broadcast Ethernet（老）

CD: collision detection

老的是 broadcast 方式，新的是网口直连交换机。

CSMA(carrier sense multiple access)
发之前监听一下，媒体空着我就说话，没空着我就等等再说
问题在于，有传播时延、还是有冲突没法消灭

CSMA/CD
limits:

  • 包的最小值
  • 传输距离最大值

原因：propagation delay

以太网最短帧限定 64bytes

Q: 冲突后 AB 都停止发送，何时重新开始？
AQ: 随机一段时间再发，随机多久？
A: binary exponential back-off（在小区间里取随机数，发，失败了就在更大区间里取随机数，重复，直到不拥塞）

CSMA/CD 效率
$ Efficiency \approx \frac{d_{trans}}{d_{trans}+5d_{prop}} $

switched Ethernet（新）

点到点，交换机判断 A 和 C 通信，那么 A 的消息就不往 B 和 D 发了。

Ethernet

以太网协议除了帧格式没变，其他基本都变了，API 为帧格式。

PPT图示以太网帧结构

  • preamble: 8 bytes 前导码，7用于时钟同步，1用于表示帧开始
  • address: 6 bytes，dst+source
  • type: 2 bytes，表明高层协议
  • data payload: max 1500, min 64 bytes
  • CRC: 4 bytes for error dectection

Q: 如何决定帧在传输时，从何开始从何结束？
A1: 开头说明帧多长（弊端，可能会在传输中出错）
A2: 开头结尾加哨兵，比如0111110表示开头，01111111表示结尾（弊端，哨兵出现在 frame contents 中，提前结束）（解决方法：发送端向 frame contents 中加0，由网卡自动完成，接收端去0，使得哨兵不会出现在 contents 中）

MAC address（48 bit，二层地址，局部有效，身份证）
IP address（标识你在网络空间里的位置，邮政编码）

路由 routing

routing with broadcast ethernet

Q: 如何在广播以太网里路由？
A: 即插即用，都接在一根铜缆上

Q: 同一楼层用一根线，不同楼层
A: 用网桥 bridges，连接不同 LAN

broadcast storm 问题：假如不同 LANS 间有环路，信号永生，信号循环加强，gg

解决思路：无环路的连通图是树，给网络图找生成树，保留节点，去掉链路。

spanning tree protocol

nice properties:

  • zero configuration（即插即用，自动配置）
  • self healing（坏了一台，可以迅速重新构建拓扑）

routing with switched ethernet

要求：即插即用

问题：依然存在广播数据包，交换机之间会有环
flooding 洪泛

spaning tree 算法

思想：

  1. pick a root（选一个 MAC 地址最小的作为 root，约定俗成）
  2. 计算其他节点到 root 的最短路，只保留最短路上的链路，多个最短路就选一条（比如选 MAC addr 最小的，约定俗成）

算法内容：
[UST]见PPT

1次洪泛可以确定所有主机 MAC 地址、root 地址？
A 不知道 B 在哪时，就把 dst 设为全 f，总能传播到，路上的交换机也知道 A 在哪了，这样 B 再回个包就能顺利到 A

交换机干的事：

  1. 看看 A 来的包以前来过没，没来过就加入 switch table
  2. 表里的项如果过了生存期还没有被使用，就删掉表项（原因：容量有限、A 可能会离开这片有线网）
  3. 收到单播数据包，当发现目标节点不认识时，就 forwarding

以太网 pros and cons

pros

  1. 即插即用
  2. 自愈
  3. 便宜

cons

  1. 带宽浪费（spanning tree 把很多枝砍掉了）
  2. 重建 spanning tree 时的延迟（新插入节点的 id 是0，那么它会是新 root）
  3. 对付移动中的设备比较慢（云平台，虚拟机快速移动）
  4. 可预测性差（A 找 B 不知道找多久，但问题不大，因为很快）

即插即用咋实现的

Q: 一台主机来时，只有 MAC 地址，怎么知道 IP 地址，邮政编码？
A: ARP, DHCP protocol

功能：

  • discovery of local end-host
    • for communication between hosts on the same LAN
  • bootstrap communication with remote hosts
    what is my
    • IP addr
    • local DNS server
    • first hop router

DHCP

a host uses DHCP to discover

  • IP addr
  • netmask
  • IP addr for its local DNS name server （没有DNS也能通信，直接输入 IP 地址就行，DNS 坏了表现为 www.baidu.com 上不去，但QQ（内置了对方IP地址）可以用）
  • IP addr for its fist-hop “default” router(s)

过程如下：
一个 DHCP 服务器把 IP addr，DNS addr 都弄好
用户先用全 f 进行广播，所有的 DHCP 服务器（一个就能工作，多个为了鲁棒）回一个 offer
用户选择一个，发一个 request， DHCP 服务器回一个 ACK
然后就能用了

DHCP uses “soft state”（软状态就好比普通内存，得不停的刷它，不然比特会翻转，所以得一直耗电，硬状态好比固态硬盘，即使不给他电，比特也不会翻转）
一个用户比如12小时不继续申请，DHCP server 就收回 IP addr，适用于咖啡馆这类客户用会就走了
如果用户在到期前“续租”，配置不会改变，应用不会断（网上银行之类，换个 IP addr 就直接断开），如果过期后续租，IP addr 可能就改了

如果用户挂了，租约到期时 DHCP 回收回
如果 DHCP 挂了，租约到期前用户正常使用，到期后用户企图续租，但没人鸟他，该 IP addr 就没法用了
如果用户和 DHCP 之间的链路挂了，用户到期前正常，到期后找别的 DHCP 服务器

ARP, DNS

假设我的 IP addr 为 1.2.3.53
掩码 netmask 是 1.2.3.0/24
DNS IP addr 为 1.2.3.156

  1. 在网页浏览器输入 www.sina.com
  2. 浏览器一看，就去问 DNS，由于在以太网内，就要知道 DNS 的 MAC addr
  3. 怎么知道呢，在以太网内广播一次，就知道哪个 MAC addr 拥有 1.2.3.156 这个 IP addr（即使要通信10000次也只要广播一次就知道 MAC addr 了）
  4. 利用每个主机都有一张 ARP table，记录最近和本主机通信过的 <IP addr, MAC addr>

本地通信：
直接丢局域网就解决了（类似同一个宿舍传递毛巾）

远程通信：
丢到网关里，然后事情丢给网关（类似快递丢给快递员，怎么送我就不关心了）

远程通信的四大关键要素：
IP addr
netmask
DNS IP addr
Gateway IP addr

ARP 负责 链路层和网络层映射
DNS 负责 应用层和网络层映射

DNS 是一级级的，有南大级别的，教育网级别的，中国级别的…

无线网络 WLAN

wireless != mobility

handoff: mobile changes base station providing connection into wired network（从南校门走到北校门，手机用的基站已经换了一个了）
5G 目标就是解决高铁高速移动中迅速切换基站

基站：
可以理解为连接无线和有线的，解决最后一公里问题。
部署在位置比较好的地方，铁塔公司把基站后连接有线连入因特网核心

无线链路：
按照目标来划分，目标有：通信距离

无线网络通信的两种方式

  1. infrastructure mode（一台通信车，其他人通过通信车进行通讯，通信车被炸了就没法通信了）
  2. ad-hoc mode（每个人都是一个节点，能和其他人进行通信，挂了一个其他人不影响）

single hop: 宿舍两个人手机通信，实际上 A-AP-B
multiple hop: MANET, VANET（车联网用的到，企图把道路上的一片区域的车组成小网络，防止碰撞）

无线连接的特征：

  1. decreased signal strength: 信号衰减
    自由路径损失公式
    free space path loss(FSPL)
    $ FSPL = (\frac{4\pi df}{c})^2 $
    d = distance
    $\lamda$ = wave length(c/f)
    f = frequency
    c = speed of light

TODO:
第5周周四的课补

第3章 网络层

IP Layer

IP 包：IP header + 四层的 payload

IP 层只关心 header，类比快递员只关心快递盒子上贴了什么快递单

IP header 作为下两者的 interface：

  1. source and destination（发件人和收货人）
  2. source and network（发件人和收货地址）

IP 协议设计时要完成的目标

  1. 解析包
  2. 传送包
  3. 处理第三层遇到的问题：
    1. routing 的死循环（类似二层交换机的死循环）
    2. 出错误
    3. 包太大
  4. 协议可扩展
  5. 信息传递优先级（类似顺丰隔日达、今日达，只看你给钱多）

IPv4

目标1 parse packet

  • IP version number（4 bit），packet length（16 bit）

目标2 carry packet to Destination

  • destination packet addr（32 bit）

目标3 handle problem

  1. preventing loops（TLL）
    为什么不用二层的 spanning tree？

    1. 太大了不好剪
    2. 局域网里链路很便宜，广域网太贵了，一条光纤不能扔那不用

    解决：
    在包里加了 Time-to-Live（TTL）field（8 bit），每被发一次，TTL 就减一点，减到0就丢掉这个包
    负责丢的路由器告诉 source 没发成

  2. corruption
    checksum（16 bit），每发一次都计算一次 checksum，保证刚才一跳中包头未发生改变

  3. fragmentation
    frag（32 bit）

  4. evolution
    version number（4 bit）+ special handling

    special handling：

    • type of service（8 bit）

IP header 结构

PPT完整图！

fragmentaion

每个 link 有一个最大传输单元，从一段大链路到另一段小链路时需要切片加头。

Q: 何时重组？
A: 接收端重组比较好，不要让中间路由器做重组的事，否则

  1. 影响效率
  2. 且包可以走很多条路，只有接收端这个唯一终点。
  3. 还能再被切更小

体现了 E2E principle（中间节点傻，只干转发的事，终端智能）

切片重组需要

  1. 知道是谁的分片
  2. 是第几片分片
  3. 还能继续切小

fragmentation fields:

  1. identifier
  2. flags
  3. offset

IPv6 小览

  1. 解决 IPv4 地址只有 32 bit IP 地址，地址不够的问题。进化到 128 bit 的地址，足以给太阳系内每一颗沙子分地址
  2. 简化 IPv4 里不必要的东西（

IPv6 哲学

  1. don’t deal with problems: leave to ends（网络要做的只是传得快、不丢包）
    • 删去 fragmentation 和 checksum
    • 保留 ttl
  2. simplify handling
    • use next header
    • 删去 header length
  3. provide general flow label for packet
    • not tied to semantics(语义)
    • 高灵活性

总结

  1. 网络层可分为数据平面和控制平面
    • 数据平面负责转发
    • 控制平面负责指挥

IP router

IP router 的架构大大小小都差不多，差别就是吞吐量

如何评价 router？

  • Router capacity = N * R
  • N = number of external router “ports”（有几个口）
  • R = speed(“line rate”) of a port（一个口有多快）

router 分类：

  1. core
  2. edge（两种，一种和别的运营商交互，另一种和自家用户交互）
  3. small business（家庭用）

router 结构：

router结构ppt

入线卡 input linecards

任务：

  • 接受发过来的数据包
  • 更新 IP 包头
    • TTL-1, checksum, options and fragment(ipv4)
    • TTL-1(ipv6)
  • 查本地的 forwarding table 去找 dest IP addr 的出端口

挑战：speed
100B packets @ 40Gbps -> new packet every 20 nano secs

IP 包最小长度 64 bit，路由器能力评价标准 是能处理最小的包是多小，因为这决定了速度

查 forwarding table

  • 1个端口对应一块地址，而不是1个 IP addr

如何找端口呢？找端口主要是根据 IP addr 的网络号进行找

  1. 软件方法：用树的结构，根据网络号一级级往下分
  2. 硬件方法：?

出线卡 output linecards

任务：

  • 分类：map packets to flows
  • 决定何时、丢哪个包
  • 传输哪个包（优先级）

调度策略：

  1. fair
  2. weighted

入卡和出卡的连接

  1. 共享一块内存（低端货
  2. 总线（低端货
  3. 系统内部网络，做到入口和出口间传输不互相干扰（有点像数电的可编程阵列？

总结

  1. IP router 是因特网骨干
  2. 速度和公平

routing 算法

goal:

  1. find a path
  2. make the state contained in forwarding tables meets our goal

评价路由算法：

  1. 有效正确，即收敛
  2. 收敛地越快越好

local state vs. global view of state

单看一个路由器，无法判断它正确与否。要判断正确（即是否能正确转发到目的地），得看全局。

路由正确性的充要条件

  1. 没有死路（即不会出现一个路由器在接到包后，不知道这个数据包该往哪发）
    （case 1, case 2, …, default。default 来保证没有 dead ends)
  2. 没有环路

least-cost path routing（收敛的越快越好）

dijkstra 算法

routing 协议（自治域内部）

基于 dijkstra 算法

  • link-state routing
  • distance-vector routing

dijkstra 算法要知道全局的拓扑

工程做起来有两种方法：

  1. 一个独立的 machine 计算完，再分发给各个节点
  2. 将全网拓扑广播给所以路由器，每个路由器都算一下，结果是一样的

Internet 使用2

每个节点都知道和自己直接相邻的路的 cost
每个节点都会把自己的状态广播给其他所有路由器，周期性地。
还有就是 cost 改变时也会广播。

洪泛过后大家重新计算 least-cost path

点数为 N, 边数为 E
复杂度 N*E

何时洪泛？

洪泛不需要 routing 规则，直接发到广播端口的。所以在这里只能用洪泛不能用路由，因为路由还没建立呢。

  1. 拓扑改变了（节点挂了，下线了）
  2. cost 改变了
  3. 周期性的，告诉别人你还活着

收敛时延 convergence delay

时延太长会导致一台 router 还活在旧的状态理解里，搞不好会出环路

收敛过程中可能发生

  1. looping packets
  2. 包进死胡同丢了
  3. 由于发的过程中 path 可能改变，先发的数据后到了，而后发的数据先到了

复杂度

  1. O(NE) messages 洪泛
  2. O(N^2) computation time | dijkstra算法时间
  3. O(network diameter) 收敛时延，主要是传播时延
  4. O(N) entries in forwarding table

OSPF: open shortest path first

IS-IS: intermediate system to intermediate system

讲到现在的所有协议都是 AS 内部的协议

distance-vector 协议

router 不需要把自己的信息洪泛给全网，只要告诉邻居节点他对世界的看法就行了，这有益于分布式

B-F 算法

看 ppt 上的具体示例

节点 x 知道它到所有邻居的距离 d_i ，然后他的邻居 i 到目标的距离 dis_i 是已知的，所以只要遍历邻居，取 d_i + dis_i 之和的最小值即可。

节点发生改变时告诉它的邻居，然后向外更新 vector

B-F 算法有的问题

看 ppt 具体例子

  1. 形成 routing loops，要互相丢包很久才能恢复到正确状态，期间没有包能被发送

解决办法 poinsoned reverse 毒药逆转

若 z 经过 y 到达 x，那么 z 会告诉 y 自己到 x 的距离是 正无穷，这样 y 就不会考虑通过 z 到达 x。
否则 z 会告诉 y 它到 x 的真实距离。

x-y cost < y-z cost

这样子假如 x-y 挂了，y 发现自己到 x 是无路可走的，y-x 更新为正无穷。这个消息传到 z，z-x 被启用，这个消息再正确的传给 y，y 就可以通过 z 到达 x 啦。

看 ppt 具体例子

解决办法 path routing

不单单广播距离，还广播向量，这样邻居就知道它之前是怎么走的了。（不考）

LS 和 DV 不同点

信息告知：
LS: O(NE) 因为是全网洪泛
DV: O(E) 只要告诉邻居就行

收敛速度：
LS: 比较快
DV: 可能出现 loop，然后要一段时间才能恢复，即使用了毒药逆转

鲁棒性：（假定所有节点都是善意的）（节点挂了尽快恢复，且不出错就是鲁棒）
LS:

  • 可能广播错误的 link cost，然后影响其他节点
  • 每个节点自己算自己的

DV:

  • 可能传播错误的 path cost
  • 每个节点算自己的，但别人还依赖你的计算结果，所以错误会蔓延

LS 和 DV 相似点

目的都是找最短路

用于同一个 AS 域内，都是友军

下节课讲 AS 之间的 routing

routing 协议 （自治域之间）

IXP: 不提供服务，只负责交换 ISP 和 ISP 之间的信息，这样两个 ISP 之间就不用特地建立物理线了。（运营商间的交换机）

域间路由的挑战：

  1. 全球寻址
  2. 管理
    • 自治管理，策略，隐私（可以不告诉对方自己的内部路由细节）

scaling

路由器必须全球可达

一个操作就是把一个范围内的 IP 一个 entry。而不是一个 IP 一个 entry。

管理

涉及商业竞争：

  1. 我不走我竞争者的网
  2. 我不让竞争者走我的网

域间路由算法

丢弃 Link-state

  1. 没隐私，因为要广播自己的世界看法
  2. 得商量 cost 咋定义

distance-vector

  1. 需要改进，叫 BGP
  2. 需要去环路
  3. 需要加入 policy

IPv4 设计（为了scaling）

一段 host 地址一般全0，全1，01不能用（留给网关）

一开始分为 ABCD 四类地址，愚蠢的设计

CIDR: 无类别的

比如一个公司 50 台主机，2^5 < 50 < 2^6，移动就给你 32 - 6 = 26 位前缀，IP 范围就是 128.23.9/26。掩码 26 个 1，6 个 0

大运营商层层分 IP，比如分给南大一段，南大再给下面的机子分配，运营商联系南大的时候，不需要知道南大下面的具体细节，只要知道是发往南大就行，剩下来的事情交给南大的路由器。

这就是聚合。

AS 之间的关系

AS A 可以是 B 的客户（付钱）

可以是 B 的提供商（付钱）

可以是 B 的对端，有双向合作的那种（互相不收钱，交换起来数据比不能过 1:3 或 3:1，在这个范围内不收钱，超了就收钱了）

为什么会有 peer？

本来因特网是树，只有上下级关系，但因为钱，同级别的可以不经过上层传，而是直接传

routing follows the money 图片

B 没有义务帮 A 和 C 省钱，所以 D 走到 E 不能通过 A-B-C 路

域间路由的第一要义不是最短路！是省钱！题目分析是要看 经过的路上的 AS 是不是得到了利益，没得到就不能过这个 AS。

以及，不会先向下走再向上走。因为下层没有义务帮上层的 AS 传数据，不赚钱。

BGP 协议

先选一条 ASes 路，这条路反映了 物理链路通达 且 有商业关系。

两个 AS 的边防局互相交流就是 “讲 BGP 语言”

类似 DV，一个 AS 广播它到某一个 IP 域的 cost

BGP 和 DV 的区别

  1. 不一定选最短路（钱）
  2. path-vector 广播到某个 IP 网络的 path，而不只是距离，这样就可以避免环路了，还可以自己选择路径
  3. 广播策略可选，比如可以不广播
  4. aggregate route，目的地址都在一起，可以合并以减少路由表

路怎么选

  • 为了赚钱，路由的路选哪好？customer > peer > provider
  • 最大化 performance，最短 AS path 长度
  • 最小化带宽，热土豆策略

Gao-Rexford：
路由不往下走？
AS policy graph 应当是有向无环图

边防局 border routers

RFC: request for comments 制定于每年三次的 ietf 会议

eBGP, iBGP, IGP

eBGP: 边防局交流

iBGP: 边防局和内部人员交流（学习外交部文件，交给内部人员学习）

IGP: 内部人员交流

BGP 中的基本信息

Open: 验明身份

notification：报故障

update：

keep alive：

attributes

  1. AS path 矢量（每个 AS 都有独立编号）

  2. local preference（对内消息，有多条出去的路的情况下，告诉内部人员走哪比较好，机密）

  3. MED: multi-exit discriminator（对于每个 IP 的前缀，指定走哪里，南京的联通和移动通话没必要走到北京再走回来）

  4. IGP cost（hot-potato）

可达问题

不一定

安全问题（想断就断，不想断就让他连着）

收敛问题

很可能收敛不了

传输层

传输层是端到端的

存在的意义：比如 NJU x 楼 x 宿舍 -> PKU y 楼 y 宿舍，网络层就编址到这里，NJUer 对 PKUer 发文件、发 QQ 经过不同的端口？
NJUer 需要复用物理地址，PKUer 需要解复用

IP 层保证全球可达（但不是一定到达），包会 崩溃、延迟、丢包、乱序、重复包（电子设备出错、对抗前面的问题）
传输层需要提供手段解决上述问题（这些问题不交由网络层解决的原因是：不是所有业务都需要稳得一批，低价看视频就不用）

传输层要告诉 网络层 传多块（速度），比如传输层知道某个路由器拥堵了，那就发慢点让它能处理

Ports

区分是哪个应用在发包

端口号自动分配，NJU 某机子一个端口，PKU 某机子一个端口，返回 1024~65536 ?

UDP 与 TCP 区别：
UDP

  • 不保证传达到
  • 不面向连接，丢出去就完事了，野蛮人的交流方式

TCP

  • 保证送达，发不到的会重发等等
  • 面向连接，要握手，文明人的交流方式

UDP

一直没怎么更新过，简陋但简单

包头就

  • src port（这都可以不给，意思就是不需要你回复我）（每个主机一个 16 bit 的 port号）
  • dst port
  • length
  • checksum（可以置为0，意思就是别检查我了，对不对和你没关系）

TCP 简介

精致，啥都干了

处理机制

一系列对抗机制 Mechanisms，来处理 bad events

  • checksum
  • ACK（没收到）
  • NACK（没收到
  • Sequence number
  • Retransmission
  • timeout
  • forward error correction

检错、纠错

checksum

告诉发送端发生了啥

ACK/NACK

PPT 图

如果 ACK/NACK 包出错，那么也再发一遍 ACK/NACK（对于发送端来说，它只感受到刚发的没发好）

如果 A->B P1(yes), B->A ACK(no), A 重发 B P1，如果不编号，那么 B 不知道收到的是第几个包
所以要用 sequence number

处理丢包

PPT 图

用 Timeout，如果过了时间没收到回复，那就重新发

会有伪丢包现象，只是传的慢了，确实可达了，但 timeout 超了

具体算法

stop and wait

@sender

  1. send, then wait
  2. if(ack) i++; repeat;
  3. if(nack/timeout) repeat;

弊端：不高效，因为 send 1 个 data 时间少，等待时间 RTT 太长！

效率 = data/RTT

在广域网情况下，带宽利用率会很低！
但如果很短的线直连，利用率还是挺高的

sliding window

PPT 图

窗里 记录应当在传输，而还未确认的那些包

一次发一批，发送端和接收端维护相同长度的滑动窗

效率 = min{n*data/RTT, link bandwidth}

n 太大的情况下（一次传的超过带宽），包会堆积，然后丢包

接收端收到了一个包就滑动一格，然后顺便发出 ack，然后发送端收到 ack 后也滑动一格。

如何确认
  1. cumulative ack

每次收到连续的 包 时更新 ack 的编号，再发

如果中间有一个没收到，那么后面的包都不发 ack 了

  1. selective ack

每次收到都更新 ack 编号，发（导致 ack 数量很多，这是消耗）

这样可以直接定位丢了哪个

如何重传
  1. Go-back-N（逻辑简单，多用硬件实现，超级计算机常用）

发送端按序发送（12345），接收端按序接受（12 45），其中 3 在路上丢了，则接收端没收到 3，就把 45 都丢了，然后无作为，发送端的 timeout 到了没收到 3 的 ack，察觉到 3 丢了，则发送端把 345.. 都重传

要求错误率极低，这样效率才不会很差（1% 的错误率就 gg 了）

  1. selective repeat

发送端按序发送（12345），接收端按序接受（12 45），其中 3 在路上丢了，则接收端没收到 3，就把 45 都 buffer 存住先不提交给应用层，回 45 的 ack，接收端的 timeout 到了没收到 3 的 ack，察觉到 3 丢了，重传 3，接收端收到 3 之后再将 3 和 buffered 45 拼起来，再提交给应用层。

适用广域网（TCP 用的就是这个）

TCP 详细

TCP 头部

PPT 图

（checksum 算的时候先把 checksum 设定一个初始值，再算完 checksum 写回去。）

头里的 sequence number 不是包的编号，是 byte offset，做字节定位用的

TCP 段

基于字节流，但不是一字节一字节发，也不是一个大东西发，而是分成段再发

分段条件；

  1. 比如传一个大文件，一个段装不下，那么分成段
  2. 段没满但时间到了，也发的情况，比如敲命令

段的大小：

  • 不超过最大传输单元大小 (缩写 MTU)（以太网 1500 byte）
  • IP 包头不带选项是 20 字节，TCP 包头 20 字节，那么最大不超过 1460

TCP sequence number、acknowledgement

seqno 是我正在发送的数据位于数据流的哪个位置

sender: seqno = X, length = B
recv: ack = X + B

sender: seqno = X + B, length = B
recv: ack = X + 2B

…

如果丢包了

比如一个包 100B，期望 seqno 如下
100, 200, 300, 400, 500, 600

假如第五个丢了，即第 500~599 字节丢了，ack 为 200,300,400,500(seqno 600),500(seqno 700)…

快速重传：不用等 timeout 耗尽，改为：看PPT，我课上没听到

timeout 怎么设定

采样得到 sampleRTT

estimateRTT = (1-a) * old_estimateRTT + a * sampleRTT

TCP 建立过程

进行三次握手

ISN 不是从 0 开始编号的

*** 2019-5-20 断线重连

TCP 缺陷

  1. misled by non-congetion losses

  2. fills up queues leading to high delays

  3. short flows comlete before discovering availale capacity

  4. AIMD impractical for high speed links

  5. saw tooth discovery too choppy for some apps

  6. unfair under heterogeneous RTTs

  7. tight couplin with reliablity mechanisms

  8. end host can cheat

7 cheating

8 Implications

P2P 传输早期被禁止，开多个 tcp 连接，带宽占满

TCP 缺陷解决

借助路由器

  1. 发现拥塞
  2. 调整达到公平

公平针对欺骗

数据包都塞入流中，轮转

ECN

多用于数据中心

终极解决，给钱

大企业解决办法

自己接管拥塞控制，方法是 UDP+应用层 Quic，这样快速

应用层

NAT

翘课

DNS

翘课

HTTP

最早出现在欧洲核子中心

HTTP/1.1 明文表示，便于调试，消耗空间

HTTP/2 二进制表示，省空间

Web 组成部分

客户端-用户

URL 全球资源标识

资源格式 HTML

URL

protocol://host-name[:port]/directory-path/resource

方法

GET, HEAD

POST, PUT, DELETE

cookies

为无状态的 HTTP 加上状态，这个状态不放在服务器端，放在客户端

复习课

ICMP

TTL 防止包永生

traceroute 对动态路由不管用，即每次 traceroute 的结果可能不一样，因为中间路由器可能会针对负载改走别的路

ip协议类型

1 ip

6 tcp

7 udp

导论

包交换-电路交换

统计复用

如何刻画一条链路的特征

带宽，点到点

OSI 模型和 TCP-IP 模型

OSI 七层，TCP-IP 五层

考一个设备是第几层的

时延由那几个部分组成

包是怎么封装/解封的

给定链路层 MTU，给头部大小，问应用层数据该有多大

中间路由器会不会分片

链路层

TDMA/FDMA/CDMA

Aloha/Slotted-Aloha 什么时候用哪个

发数据的成功概率

以太网

CSMA/CD 是怎么做的，重点看

Wireless

CSMA/CA or Distributed Coordination<-这个没讲过，自己看一下

问为什么不直接用 CD 而要用 CA

特征
Hidden terminal

Multi-path

信号衰减

有线网无线网区别

交换机和网桥有什么区别

地址的 self learning（交换机）

spanning tree（交换机）防止环路

网络层

IP header

dijkstra and bf

域间，域内 routing

RIP/OSPF/BGP，用的什么算法

哪些是用于域间，哪些域内

subnet，netmask，gateway

是什么，为什么gateway

如果没配置会有什么后果

CIDR 是什么

ARP 是干什么的

谁是 1.1.1.1？告诉我它的 mac

DHCP 是干什么的

传输层

UDP 和 TCP 区别

UDP TCP header里有什么

TCP 三次握手，分手

为什么要三次握手

分手有几种，友好的，不友好的

TCP 的细节，可靠性和流控

流控和拥塞控制的区别

TCP 拥塞控制

sliding window

AIMD

RTT

ICMP

有什么黑科技功能

NAT

有两种类别，运行于不同层？

静态绑定动态绑定

一个子网怎么划分？网关怎么配？dns怎么设，防火墙怎么设，要不要设NAT

应用层

HTTP

有多少种，取数据的方式有什么不同 1.0 2.0，中间建立几个连接

DNS

是主机在发 query 还是别的实体在发 query

安全

对称密钥

公私密钥

RSA 实例

信任第三方 CA

为什么需要可信第三方

DH key exchange

不需要第三方，为什么也能安全交换

IPSec

什么时候用，有几种协议模式，有几种运行模式

SSH

什么时候用