期末了神魔都没学，来复习一波

基础

P T G M K
2^30~10^9 2^20~10^6 2^10~10^3

ISP:互联网服务提供商

流程

接口：相邻的两层实体通过SAP（服务访问点）进行交互 –> 逻辑接口


第一章 概论（豪乱）

计网：网络硬件+网络协议

协议栈

OSI 7层模型
TCP/IP模型

应用层(application) 传输层(transport) 网络层(network) 链路层(link) 物理层(physical)
送什么 送给谁 送给谁 怎么送 怎么送

socket可以看作各个层的连接
送给谁：主机（ip地址标定主机）、端口（进程）

transport: process-process data transfer
network（导航）: from source to destination
link（一段一段搬运）: point-point transfer between neighboring

应用层：

  • 计网就是给应用层传输的数据提供服务
  • 对于应用层来说计网=socket

传输层（端到端）：
送给谁：标定端口

作用：

  • 附有进程端口信息（标出送到目标主机上的哪个进程）
  • 分包组包
  • 可靠传输

网络层：
送给谁：标定主机

作用：

  • 附有主机ip地址
  • 找路（原ip -> 目标ip 最优路线）

链路层（点到点）：
负责运输
从网络层运输后需贴上链路层地址
需要提供链路层地址才能运输到目标地址

路由器协议栈

  • 网络层
  • 链路层
  • 物理层

每一层都有其对应二进制序列的名称
应用层 -> message
传输层 -> Segment(TCP)/Datagram(UDP)
网络层 -> ip Datagram(ip数据报)/ip Packet(ip分组)
链路层 -> frame
物理层 -> 比特流

输入为SDU -> 层 -> 输出为PDU

上层提供SDU，下层提供PDU

主机发送数据包

带宽是R，发送的数据长为Lbit

带宽越大，从主机发送到链路上的时间越短

delay：
从PC到链路上的传输时间(transmission)为T=L/R（数据量/带宽）

传播时间(propagation)(从起点到终点)：链路长度/链路上的传播速度 -> 一般认为光速

The network core

电路交换(circuit switching)（主要由交换机实现）：先建立通信线路端到端连接，通信期间独享不可断，可理解为通电话，直到断为止 到一个输出一个
分组交换(packet switching)（主要由路由器实现）：

  • 数据被分成多个小数据包，每个分组独立路由传输，不需要建立专线
  • 存储转发机制(store and forward) -> 字节到了先存起来，等到了完整的报文一起发 不用一个字节一个字节的发
  • 可能有网络延迟会丢包

TCP是面向连接的，但是他是分组交换（两种连接说的不一样）

路由器

路由器存储空间太小：丢包
路由器存储空间太大：收发报文时间太长，无意义

路由器功能：

  • Routing（路由）:面向全局 最优路线
    路线生成后每个路由器上都会产生相应转发表
  • Forwarding（转发）（从哪个口进哪个口出）:面向局部
    根据生成的转发表进行转发

IP over everything（接收）
everything over IP（发送）

Packet queueing delay

L:单个分组的长度
a:分组到达的速率
R:带宽
La:单位时间内到达的数据量
traffic intensity = La/R
流量强度


第二章 Application Layer

port

HTTP server: 80
mail server: 25

应用层app基本框架

Client-server paradigm

客户端+服务器
多（客户端）对一（服务器）

server:

  • always-on host
  • permanent IP address

clients:

  • may be intermittently connected(时断时续)
  • may have dynamic IP address(动态IP)
  • do not communicate directly with each other
    eg. HTTP/IMAP/FTP

Peer-peer architecture

既可以充当服务器又可以充当客户端（一般用于资源共享下载），能直接与其他节点进行通信、共享资源

  • 无中心服务器
  • 数据分散在多个peer上，共享资源
  • 节点可以动态加入/离开
  • 根据节点变化自我调整

Internet transport protocol services

TCP service

可靠传输(reliable transport):
流控机制(flow control)：解决端到端 发送/接受 快/慢 （中间不管 只管起点&终点）调节快慢 速度匹配
阻塞机制(congestion control)：中间节点的协调
面向连接(connection-oriented)：需三次握手建立连接

eg. Web/E-mail/FTP

保证很多东西且贴端口号


UDP service

unreliable transport
面向无连接

eg. DNS

不是完全没用 贴了端口号


TCP VS UDP

HTTP

  • 不维持连接，无状态 服务器不会保存任何有关过去客户端请求的信息
  • 使用TCP，客户端向服务器发起TCP连接
  • 服务器接收来自客户端的TCP连接
  • client and server exchange HTTP messages
  • TCP connection close

maintaining user/server state

web cache(proxy server)

客户端请求一个资源，资源在cache里面直接从cache里面取,若没有，cache从原始服务器里面获取资源
通信一般不与原始服务器交互所以利用到cache

  • cache一般在本地
  • 既是客户端又是服务端

E-mail

  • the RFC(5321)
  • port 25

SMTP

HTTP: client pull
SMTP: client push

DNS（应用层协议）

去中心化、分布式
域名 -> ip

root name server

13 logic root name “server”
级别最低的域名写在左边，级别最高的域名写在右边。
域名服务基于UDP，port:53

ipv4: 32bit
ipv6: 128bit

local DNS name server

因特网服务器提供商

DNS name resolution:iterated query

告诉下一个可以查询的服务器地址，不主动帮忙查询
迭代查询

DNS name resolution:recursive query

请求的DNS服务器会帮助查到最终ip地址，一级一级向下查询
同个函数重复调用，不断嵌套，内层最先返回，最后调用的最先返回
递归查询

socket programming（不考，理解）

UDP

explicitly（显式） attaches IP destination address and port to each datagram
clientSocket.sendto(message.encode(),(serverName,serverPort))

UDP socket:

  • socket
  • destination ip address
  • destination port

用网络发信息需要：

  • 原ip
  • 原port
  • 目的ip
  • 目的port

综上，UDP socket包含原ip，原port
所以在创建UDP socket时则已经绑定了local ip & local port


TCP

TCP socket:

  • 原ip
  • 原port
  • 目的ip
  • 目的port
    通过TCP socket可以获得上述信息

第三章 Transport Layer (TCP/UDP)

process-to-process

  • multiplexing/demultiplexing
  • reliable data transfer
  • flow control
  • congestion control

Transport layer services

ip -> port -> socket -> 进程（pid）

Transport services and protocols(协议)

provide logical communication between application processes running on different hosts(传输层提供了应用进程的逻辑通信)

传输层从起点到终点

TCP才分包组包


Transport VS network layer services and protocols

transport layer: processes
network layer: hosts

transport layer relies on network layer

Multiplexing and demultiplexing

multiplexing（复用）

发送方不同的应用进程都可以使用同一个传输层协议传送数据

demultiplexing（分用）

接收方（从下往上）的传输层在剥去报文的首部后能把这些数据正确的交付到目的的应用进程

Connectionless transport: UDP

面向数据报
报文（首部、数据）是UDP处理数据的最小单位
UDP在送时需要明确目的ip和端口

UDP报文段格式

  • may be lost
  • may be 传送乱序报文
  • 直接发报文
  • 不用维持连接

Principles of reliable data transfer

可靠的数据传输：

  • 不出错
  • 不丢
  • 不乱

Reliable data transfer protocol(rdt):interfaces

数据已经正确到达，则采取rdt
可靠信息的传输需要起点和终点交互一些信息

Reliable data transfer: getting started

rdt1.0: reliable transfer over a reliable channel

理想信道：100%可靠，无比特差错、无丢包

  • 发送方：把应用层交给它的报文逐字节推到信道上
  • 接收方：按序接收，直接上交上层

rdt2.0: channel with bit errors

通道不可靠，带比特差错（可能把0变1，但是不会丢包）

改进：

  • 差错检测：采用差错控制编码进行差错检测
  • 反馈机制
    • 确认（ACK）：接收端检验ok -> 发送ACK
    • 否定确认（NAK）：检验fail -> 发送NAK，要求重传
      stop and wait: sender sends one packet, then waits for receiver response
      stop and wait协议发送方滑动窗口大小为1

rdt2.1: sender,handling garbled ACK/NAKs

给数据段和ACK/NAK都加了1-bit序号（0/1）

  • 接收方：
    • 收到段后检验通过且seq与期望相同 -> 交付上层并回ACK(seq)
    • 差错/seq重复 -> 丢弃并返回NAK/ACK（旧seq）
  • 发送方：保留最近一次已发送副本收到ACK（期望seq）才进入下一个阶段
    要保证滑动窗口里的编号没有一样的

rdt2.2

用不同编码的ACK代替NAK

  • 接收方：只回复ACK（seq）
    • 检测到问题 -> 重发ACK（seq）
  • 发送方：
    • 收到ACK（期望seq） -> 发送下一个数据段
    • 收到ACK（旧seq） -> 重传

rdt3.0

不可靠 既出错又丢包
及时性 有超时计时器
发送方：传出段后启动定时器

  • 若在计时器到期前收到正确ACK -> 关闭定时器发下一段
  • 若到期 -> 重传

效率 (L/R)/(RTT+L/R)

Go-Back-N

发送窗口>1 接收窗口=1
发送端连发多帧，若收到确认则继续发送
发送端等待超时，回退到最早未确认的帧，重发整个窗口的所有数据
累积确认

Selective Repeat

发送窗口>1 接收窗口>1
只重传出错或丢失的数据包
单个确认

kbit
sender window size + receiver window size <= 2^k

Connection-oriented transport: TCP

  • point-to-point
  • full duplex data: 全双工数据（在同一连接中数据流双向流动）
  • 可靠的、按顺序的字节流
  • 面向连接: 建立连接后发报文
  • flow controlled: 发送方的发送速度不能超过接收放的接收速度

TCP segment structure


MSS + TCPheader + IPheader <= MTU

TCP round trip time,timeout

TCP超时设置：比RTT长

  • 太短：太早超时
  • 太长：报文丢失反应太慢

TCP fast retransmit

必须保证数据按序到达

如图所示，若连着收到3个ACK=22，则可说明已经丢包，则可重传

TCP flow control

考虑的是接收方的接收能力
在每个TCP报文段中都有一个字段：
| 窗口大小(Window Size) | 16位 |
接收方汇报给发送方(Receive Window)还有多少缓存空间可以用
发送方发送的数据数量 <= Receive Window的数据

TCP connection management

三报文握手

  • 客户端->服务端 发送连接请求，初始化序号
  • 服务端->客户端 确认客户端的SYN，回应自己的SYN
  • 客户端->服务端 确认服务端SYN，建立连接

若两报文握手：

  • 可能超时
  • 报文乱序
  • 丢失重传

Closing a TCP connection

四报文挥手
全双工，每一端都要单独发送FIN和收到ACK

差错检测

检查首部和数据

port

  • 应用层应用进程将数据通过端口向下交付给传输层
  • 传输层将报文段的数据向上通过端口交付给应用层相应进程

常见端口号：

  • FTP: 21
  • TELNET: 23
  • SMTP: 25
  • DNS: 53
  • TFTP: 69
  • HTTP: 80
  • SNMP: 161

Principles of congestion control（拥塞控制）

不只接收方，要考虑整个网络
阻塞 -> 丢包 -> 重传 -> 带宽浪费

拥塞控制方法

  • 端到端拥塞控制
    • 没有网络显示反馈
    • 端系统根据延迟/丢失来判断是否拥塞
  • 网络辅助拥塞控制

TCP congestion control:AIMD

  • 慢启动
  • 拥塞控制
  • 快速重传
  • 快速恢复

丢包后直接线性增长则为 a triple duplicate ACK
丢包后慢启动则为timeout

慢启动（探测网络上限）

cwnd：发送方用于控制自己能发送多少数据的窗口
初始：cwnd = 1MSS
每收到一个ACK，cwnd指数增长
结束进入拥塞避免：

  • cwnd>=ssthresh(慢启动阀值)
  • 发生丢包

到了阈值一个一个增

拥塞避免（线性增长）

超时丢包，则回到慢启动（1MSS）
阈值变成丢包时值的1/2

快速重传

检测到同一个ACK被重复收到3次，则认为有丢包，立即重传丢失的包

快速恢复

快速重传后触发
没有快速恢复，当快速重传后将进入慢启动（1MSS）
快速恢复 不回到1MSS，而设置为ssthresh


第四章 Network Layer：数据平面 (ip地址)

解决host-to-host的问题
只检查首部
网络层：路由器（网关）
链路层：交换机（不具备解析网络层能力）
物理层：转发器

导论

网络层：数据平面、控制平面
数据平面：

  • local
  • 转发

控制平面：

  • 逻辑
  • 路由

Network-layer services and protocols

  • 在发送主机和接收主机之间传送segment(段)
  • 网络层的协议存在每个主机和路由器

Network-layer functions

  • forwarding（local）: 分组从路由器的输入接口转发到合适的输出接口
  • routing: 决定分组从发送主机到接收主机的路径

SDN:逻辑集中的控制平面

传统网络设备自己做决策，而SDN将所有决策集中在一个远程控制器上，只让设备负责执行命令


路由器的组成

路由器结构

路由（决定数据怎么走）：选择算法/协议（RIP/OSPF/BGP），生成路由表
转发（把数据发到正确的地方）：收到数据包后查路由表，看去哪儿然后通过交换结构转发出去
路由器作用：解析ip、守护、转发
路由器：控制平面、数据平面


IP: The Internet Protocol

ip地址表示方法：点分十进制

Internet

IP Datagram format


TTL要先-1 再判断转不转发 TTL-1后为0不转发


IP分片与重组

网络层交给链路层的长度不能超过MTU
超过MTU就会分片传输，接收端再根据偏移量拼接
fragflag=1 -> 还有后续
偏移量：数据开始字节数/8（以8字节为单位）
例题

ipv4

  • ip: 32bit
  • interface
    • 路由器拥有多个接口
    • 主机有多个接口
    • 一个ip地址和一个接口相关联

Subnets(子网)

  • 子网内ip地址的高位相同
  • 无需路由器介入

物理上互联，且ip处于同一网段
路由器用来跨网络传

怎么看在同一个子网：

栗：
6个子网

IP地址分类

有类编址
A类地址：8 NATID 、 24 HostID

  • 2^8 个不同的网络id
  • 每个网络下有 2^24 个主机
    B类地址：16 NATID 、 16 HostID
    C类地址：24 NATID 、 8 HostID
    D类地址
    E类地址

特殊ip地址

NatID HostID
0 0
0 m
m 0
1 1
m 1
127.0.0.1 ~ 127.255.255.255

内网ip地址

CIDR

  • 无类
  • 域间路由
  • 需要自定义NatID

eg.200.23.16.0/23 -> 高23位为网络id 则低9位为hostid

子网掩码

写法：
eg.200.23.16.0/13
把最高23位全写为1，后面均为0
11111111111110000000000000000000 -> 255.248.0.0


DHCP协议（应用层协议）

如何获取ip地址？

  • 硬编码
  • DHCP（自动）

DHCP服务器在ISP路由器中
往下传到传输层用UDP

DHCP协议设置：

  • ip
  • 子网掩码
  • DNS服务器域名
  • 默认网关

how does network get subnet part of IP address?

大子网分小块

????????????????? 第42截？


route aggregation(路由汇聚)

小子网汇聚大

若有一子网移动到下面

假设要找200.23.18.7
根据最长匹配机制，应该进入ISPs-R-Us


network address translation(NAT)

IPv6

128bits
IPv6数据包格式：

  • 固定40字节头部
  • 传输过程中不允许分片

第五章 Network Layer：Control Plane

算法 协议
LS OSPF
DV RIP(UDP)

在一个自治系统（AS）内部网络间选择路由使用的是IGP协议(内部网关协议)

  • OSRF
  • RIP协议

在不同自治系统中选择路由使用的是EGP协议(外部网关协议)

  • BGP

路由选择算法

局部信息的全局转发

Dijkstra算法

distance vector

全局信息的局部转发
RIP协议：坏消息传的慢，好消息传的快
相邻传递
找到跳数最少的路径

路由表更新例题：

先写出B收到C发过来的信息后的路由表（未与之前对比版）：

目的网络 距离 下一跳路由
N2 5 C
N3 9 C
N6 5 C
N8 4 C
N9 6 C

更新版：

目的网络 距离 下一跳路由
N1(没有的直接加入) 7 A
N2（下一跳一样，更新） 5 C
N3 9 C
N6 5 C
N8（距离一样则下一跳不变） 4 E
N9（均不一样选最短） 4 F

毒性逆转机制：

intra-ISP routing: OSPF

通过通告知道所有链路信息，所有路由器都广播
每个路由器都需要构建出全图
只在初始和更新时更新
选择代价最小的

routing among ISPs: BGP

基于TCP,不是看最短

第六章 The link Layer and LANs（point-to-point）

概论

从一个节点通过链路将（帧中的）数据包发送到相邻的物理节点
在相邻节点间（一个子网内）进行可靠的转发

  • framing(成帧), link access
    • 将数据报封装在帧中，加帧头帧尾
    • 帧头使用MAC物理地址来标示源和目的
  • reliable delivery between adjacent nodes

  • flow control
  • error detection
  • error correction
  • half-duplex and full-duplex

差错检测和纠正

计算循环冗余码

多点访问协议

  • 点对点
  • 广播

MAC协议

  • channel partitioning(信道划分)
    • TDMA
    • CDMA
    • FDMA
  • random access(随机访问)
    • Slotted ALOHA
    • Pure ALOHA
    • CSMA
    • CSMA/CD
  • taking turns(依次轮流)
    • polling（轮询） token passing
    • token ring

点对点协议（PPP）

LANs

addressing, ARP

LAN(MAC/物理/以太网)地址：

  • 48bit
  • 使帧从一个网卡传到与其物理连接的另一个网卡（在同一个物理网络中）
  • 任意两个网卡MAC地址不同
  • 一个网卡可以有多个ip地址

局域网链路传输必须提供MAC地址
局域网内部通信不需要ip地址 需要MAC地址

ARP协议：
找ip地址对应的MAC地址

  • 广播提问：问ip地址对应的MAC地址，这条消息会被发到局域网的所有机器
  • 目标设备回应：有一台和你找的ip一样的电脑回应自己的MAC地址（只回应给A，不再广播）
  • 存入ARP缓存

TTL时间是指地址映射失效的时间
典型是20min

跨网段发送数据报：

  • A通过DNS知道B的ip地址
  • A知道第一跳路由器R的ip地址 -> 路由表会告诉A
  • A 查自己的 ARP 表，看看 111.111.111.110 对应哪个 MAC 地址
  • 找到 MAC：E6-E9-00-17-BB-4B，就用这个地址发数据
  • R收到A发来多点而数据包（目标ip为B）
  • R 会根据自己的路由表判断：“B 是我直接连接的另一侧 LAN 中的主机”，然后查自己的 ARP 表，找出 B 的 MAC 地址（49-BD-D2-C7-56-2A），再把数据转发过去

广播域（ARP）只能在局域网内部传播
交换机隔离冲突域不隔离广播域，路由器隔离广播域

Ethernet

  • 无连接
  • 不可靠

以太网的两个标准:

  • DIX Ethernet V2
  • IEEE 802.3

switches

  • 存储转发frame
  • 透明：向直接连接的一样
  • 即插即用，自学习

多路同时传输
A与A’发和B与B’发可以同时且不冲突

题目

chapter2

HTTP

  1. Suppose within your Web browser you use http://ip/url.html to obtain a Web page. Further suppose that the Web page associated with the link contains exactly one object, consisting of a small amount of HTML text. Let RTT0 denote the RTT between the local host and the server containing the object. Assuming zero transmission time of the object, how much time elapses from when the client clicks on the link until the client receives the object（）

客户端获取网页发送建立连接的请求到服务器，服务器响应 –> 1个RTT0
请求文件 –> 1个RTT0

  1. two object / Non-persistent HTTP / no parallel TCP connnections
    初始HTTP –> 2个RTT0
    一个object –> 2个RTT0

  2. eight object / Non-persistent HTTP with the browser configured for 5 parallel connections
    初始http –> 2个RTT0
    5个object –> 2个RTT0
    8-5=3 –> 2个RTT0

  3. eight object / client clicks on the link until the client receives / using persistent HTTP connection with pipelining
    初始http –> 2个RTT0
    带流水线，复用TCP –> 1个RTT0

  4. eight object /persistent HTTP / without pipelining
    初始http –> 2个RTT0
    –> 8个RTT0

DNS

  1. 记录类型
  • 基础类：A（IPv4）、AAAA（IPv6）、CNAME（别名）、NS（域名服务器）、SOA（起始授权）、PTR（反向解析）；
  • 功能类：MX（邮件）、TXT（文本信息，如SPF防垃圾邮件）、SRV（服务定位，如即时通讯服务器）等。
  1. 先查询hosts文件，找不到才查DNS服务器
  2. 在缺省情况下DNS服务器采用递归查询

RDT协议

sending side: rdt_send() -> udt_send()
receiving side: rdt_rcv() -> deliver_data

拥塞控制

  1. TCP congestion avoidance -> 线性
  2. 丢包后直接线性增长 –> a triple duplicate ACK
  3. 丢包后慢启动 –> timeout
  4. initial value of slow-start threshold at first transmission round(第一轮慢启动阀值初始值)

CRC

补零个数 = 生成多项式位数-1
CRC 为 待发送信息补零/多项式 的余数
余数个数取补零的个数
最后发送的信息 = 待发送 + 余数
若余数为0则没有误码

SDN

核心组件：控制器
第一阶段商用的重点：数据中心

数据报分片

数据部分长度不包括首部

标识字段 = 原始标识字段
DF标志位：0表示可分片 1表示不可分片
MF标志位：看后面还有没有分片
分片偏移字段 = 该分片前面所有分片长度的总和/8

UDP报文首部8bits
TCP报文首部20bits

码分多址通信

所给码片与收到码片正交
eg. (-1 1 0) (1 0 0) –> (-1*1 + 1*0 + 0*0)/3
结果为1 -> 发1
结果为-1 -> 发0
结果为0 -> 未发

地址聚合

转换成二进制 找最长前缀匹配

ARP

ARP查询包直接封装在链路层广播帧中

checksum

相加 -> 若溢出循环加最高位 -> 全部取反

ip数据报

ip数据报总长度 = ip头部长度（20） + TCP头部长度（20） + 应用数据长度

路由器

N个路由器有N+1个链路

protocol

传输层：

  • UDP -> 17字段 4fields
  • TCP -> 6字段 10fields 序列号由第一个数据字节的编号决定

网络层：

  • ICMP
  • IGMP

邮件：

  • SMTP（TCP）(push)：邮件从发件人的邮件客户端传输到发件人的邮件服务器 & 邮件服务器之间的邮件传输
  • POP3（TCP）(pull)：邮件服务器将邮件下载到用户的本地计算机

交换技术

  • circuit switched(电路交换) 独占
    • 电话
    • 能支持的最大用户数 = 链路总带宽/单个用户的宽带需求
  • packet switched
    • 互联网

MAC

  • 十六进制
  • 6组

子网

子网掩码转为二进制 1 -> 网络位 0 -> 主机位
总地址数 = 2^主机数
有效主机地址数量 = 总地址数 - 2
广播地址为当前子网的最后一个地址

eg. 255.255.255.128
11111111.11111111.11111111.10000000
/25 -> 2^7 = 128个地址

port

  • SMTP:25
  • POP3:110

frame

核心功能：

  • synchronization bytes(同步字节)
  • address
  • frame identifier

子网划分

划分x个块，从前面网络位加2^n=x位
新网络位 = 原网络位+x
每一个网络地址分块的子网间隔有2^(32-新网络位)
在网络ip的基础上加间隔即可

路由表

  • 没有加入
  • 下一跳一样则更新
  • 距离一样则下一跳不变

传播

比特数 = 传播时延 * 数据率

多路访问协议

  • 信道划分协议(Channel Partitioning Protocol)
  • 随机访问协议(Random Access Protocol)
  • 轮流协议(Taking-Turns Protocol)

CSMA/CD 最长帧长

帧的传输时间必须>=最长传播时延的2倍