ST-CS120: Computer Network

OSI Model

• https://www.forcepoint.com/zh-hans/cyber-edu/osi-model

Performance

• Metrics (性能与指标)
  • Bandwidth (Throughput)
    • Unit: bps, kbps, Mbps, Gbps, where b stands for bits
  • Latency
    • RTT: Round-Trip Time: calc the time of send and recieve. Local because of the avoidance of time shift between devices.
    • 计算往返的时间，也就是本地从发出到收到的时间差。对应的，单程 (One-way Latency) = T2 - T1 or T3 -T2
    • Latency = Transmit Delay + Propagation Delay + Queueing Delay
      • Transmit Delay = TransferSize/Bandwidth
      • Propagation Delay = Distance/SpeedofSignal
• Effective Bandwidth (throyghput) = TransferSize/Latency
• tools: iperf, ping (https://networktools.he.net/)(https://ping.sx)

L1: Physical Layer

网线一类的东西

• 介质
• 需要调制与解调（以通过物理介质传输）

Upper bound of throughout

Shannon-Hartley Theorem

The theoretical throughput upper bound:

Transmission Method

Baseband Transmission (Line Coding)

• 无载波
• 串行

Passband Modulation

• 载波
• 并行
• $A\cdot \sin (2\pi ft+\varphi )$
  • Amplitude
  • Frequency
  • Phase

Frequency Shift Keying (FSK)

Phase Shift Keying (PSK)

Frequencty shift passing

• 高频部分解码归零
• 低频部分保留

Amplitude shift passing

• $A\cos (2\pi ft)\cos (2\pi ft)=\frac{1}{2}A(cos(2\pi ft)+1)$
• 乘以载波解码
• 信号不稳定时效果较差

Quadrature Amplitude Modulation

• ASK + PSK
• 传输更多的信息 (4 symbols) 总结: Baseband * coherence wave = Passband

纠错与恢复

analog goes wrong

• Bit error rate (BER) = error bits/transmitted bits
• High rate <-> Low reliability

2D Parity Check

是不是有偶数个 0

• overhead
  $\frac{1}{8}$
• 1,2,3 bit wrong OK to recover
• 4 bit may ERROR

Check sum

• TCP/IP header
• sum all, check sum
• 作为补码加起来
• 快但低能

CRC Performance

多项式 https://users.ece.cmu.edu/~koopman/crc/

汉明码

多路复用

• 分时复用
• 分频复用 Frequency-division multiplexing (FDM)
• 分码复用
• 传输介质无法承载我们的传输

Rate Selection

ACK

🐱：喵
😺：喵
🐱：喵喵
😺：喵喵

Stop and Wait

http://www2.rad.com/networks/2004/sliding_window

规定时间内收不到就等,效率不高（利用 buffer 解决）

https://en.wikipedia.org/wiki/Bandwidth-delay_product

https://github.com/shadowsocks/shadowsocks/wiki/Optimizing-Shadowsocks

NACK (Negative ACK)

接收方定时把所有未收到的包序号通过反馈报文通知到发送方进行重传。

Sliding Window

• 不对等的传输
• Send buffer size: Delay
  $\cdot$ Bandwidth
• Receive buffer size: Flow control
• 拥塞控制: 控制 buffer 大小

并行

Random Access

Transmit and Pray

Slotted ALOHA

• For each slot, the probability of successful transmission is
  $\mathrm{Np}(1-\mathrm{p}{)}^{\wedge }(\mathrm{N}-1)$
• $\mathrm{p}$ is the probability of transmission. It is determined by the number of nodes
  $N$ in the network, when
  $N$ is large,
  $p$ should be small.
• The optimal p can be calculated by derivation
  • $f(p)=Np(1-p{)}^{\wedge }(N-1)$
  • $f^{\prime }(p)=N(1-p{)}^{\wedge }(N-1)-Np(N-1)(1-p{)}^{\wedge }(N-2)$
  • Thus the optimal
    $\mathrm{p}$ is
    $1/\mathrm{N}$
• So when
  $p=1/N$, the probability of successful transmission is
  $(1-1/N{)}^{\wedge }(N-1)$, when
  $N$ is large, it is close to
  $1/e$. Thus the utilization of the channel is about
  $30\mathrm{\%}$
• Efficiency: 1/e

L2: 链路层，介质访问子层

Main function

• 连接协议 (e.g. Hola)

Ethernet

ip addr show

WIFI and Cecullar

https://blog.csdn.net/qq_27847237/article/details/104098817

• 半双工
• 不对称

RTS/CTS

通过监听其它 client 之间的通讯来推测 server 与它的连接情况

• RTS/CTS does not solve hidden terminal and exposed terminal completely
• Designing Wireless MAC is non-trivial
• overhead too large

IEEE 802.11 MAC

WIFI 包经过再打包走 Ethernet

• 3-Addr: A -> AP -> C
• 4-Addr: A -> B -> C -> D (mesh)

See https://github.com/SpacehuhnTech/esp8266_deauther for a security issue for WIFI

Switch

learning Bridge

• Switching method

  • Datagram / Connectionless
    • 转发表：记录下来这条链路上的所有主机和对应走哪个端口
    • No Guarantee for
      • Success delivery
      • Performance
      • Delay, Throughput
      • Packet Order
    • 打电话给 ISP
    • 
  • Vitual Circuit/Connection
    • Procedure
      • 预留资源 (入口与 index)
      • 当链路上的所有 switch 都有足够的资源，destination 会发回一个 ack， 然后链路就建立起来了
  • Source Routing
    • 带路由信息

• Learning Switch

  • 知道 A 从哪来 (port 1)
  • 广播 (X 收到包)
  • 其它节点也知道 A 在哪了
  • 同一个冲突域内 drop

• Cycle:

  • 成因: 错误的网络管理、冗余
  • 结果: Storm
    • 占用网络资源
    • 重复包

• Distributed Spanning Tree Algorithm

  • Each switch is a vertex
  • Each connection is an edge
  • 最小生成树
  • 计算 hof, speed, rtt 将形成环路的节点断掉

L3: 网络层

Internet Protocal

多协议之间的网络通信

• Addressing Scalability
• Network Heterogeneity

IP Addressing

IP Forward

• Each router maintains a forwarding table
  • if IP.network == Connected network
    • forward to the host (How? ARP: IP->MAC)
  • if IP.network != Connected network
    • forward to some router

IP jisuanqi

ipjisuanqi.com

IP Packet

Dynamic Host Configuration Protocol (DHCP)

分配 IP 地址并记录

Address Resolution Protocol (ARP)

• ARP table: each IP node (host, router) on LAN has table IP/MAC address mappings for some LAN nodes
  • < IP address; MAC address; TTL>
  • 200.155.11.3; 58-23-D7-FA-20-B0 200.155.11.5;
  • 1A-2F-BB-76-09-AD 200.155.11.2;
  • 0C-C4-11-6F-E3-98

Fragmentation and Reassembly

包会分割成 MTU 的大小传输，之后再重组 (There is Offset-bits in IP packet)

Routing

The basic problem of routing is to find the lowest-cost path between any two nodes

RIP

• Bellman-Ford Equation
• $d_{A\to C}=min\{A\to B+B\to C\}$ foreach
  $B$ in
  $A\to C$ 松弛操作
• 每个节点不断的估计和其它节点的最短距离，并不断收敛
  • distance to neighbour is known
  • and its neighbour can tell (not specific) the distance to destination y
  • 当一个节点收到新的值的时候，通知周围节点更新
• 优点：收敛块
• 缺点：缺少弹性
  • 断连无法更新或者更新出错或者很慢
  • 数字会一直变大
• 优化
  • 限制最大跳数
  • 限制每次更新的数目

Dijastra

OSPF

BGP

bgp.he.net

• iBGP: peers
• eBGP: transits

IPV6

NAT

随机端口映射到主机

Mobile

L4: 传输层

UDP

TCP

TCP Congestion in Network

Additive Increase/Multiplicative Decrease (AIMD)

• Additive Increase
  • Increment = 1/cwnd
  • cwnd += Increment
• Multiplicative Decrease
  • cwnd = cwnd /2