音ノ木坂学院

叶え！みんなの夢――

0%

计网复习坑

发表于 更新于 Disqus：

引言

使用计算机网络

  1. 计算机网络 和 分布式系统
  2. 普适计算(Ubiquitous computing)属于Home applications

网络硬件

PAN(Personal), LAN(Local), MAN(Metropolitan), WAN(Wide)

  • PAN: Bluetooth, RFID等
  • LAN: 因为区域被限制所以速度可以很快，802.11(WiFi) AP、Switched Ethernet等
  • LAN: 静态和动态，分配时间槽(time slot)的方式不同。静态浪费大，所以多用动态
  • MAN: DQDB, cable TV, WIMAX
  • WAN = subnets + hosts
  • Subnet + hosts -> WAN -> network
  • Cable + hosts -> LAN -> network
  • Many interconnected networks -> internetworks

Broadcast networks(广播式网络) Point-to-point networks(点对点网络)

Unicasting(单播),Broadcasting(广播),Multicasting(组播)

协议层次结构

  • 协议指通信双方就如何通信的一种约定
  • 不同机器上构成响应层次的实体称为对等体
  • 层和协议的集合称为网络体系结构(network architecture)
  • 一层一个协议，称为协议栈(protocol stack)
  • 层次设计问题
    • 寻址和命名
    • 信道控制
    • 检错和纠错
    • 流量控制
    • 分解和重装
    • 复用/解复用
    • 路由
    • 拥塞(congestion)、实时、服务质量(QoS)、保密性、验证、完整性等

面向连接与无连接

  1. 面向连接
    • 可靠的报文流：顺序页面
    • 可靠的字节流：移动下载
    • 不可靠的连接：IP语音
  2. 无连接
    • 不可靠的数据报：垃圾邮件
    • 有确认的数据报：文本消息
    • 请求-应答：数据库查询

服务原语(primitive)

LISTEN, CONNECT, ACCEPT, RECEIVE, SEND, DISCONNECT

服务与协议的关系

OSI参考模型
  • 需要一个不同抽象体的地方创建一层
  • 每一层都应该执行一个明确定义的功能
  • 每一层功能的选择应该向定义国际化标准协议的目标看齐
  • 层与层边界的选择应该使跨越接口的信息流最小
  • 层数应该足够多，保证不同的功能不会被混杂在同一层中；层数也不能太多，以免体系结构变得过于庞大
  1. 物理层(Physical layer)：关注在一条信道上传输原始比特
    • 用什么电子信号
    • 传输是否可以两方向同时进行
    • 如何初始化连接
    • 连接器有多少针
  2. 数据链路层(Data link layer)：讲原始传输设施变成没有漏检传输错误的线路
    • 数据帧
    • 检错和纠错
    • 流量调节机制
    • MAC：控制共享信道
  3. 网络层(Network layer)：控制子网的运行
    • 数据包从源端到接收方
    • 拥塞控制
    • 异构网络
  4. 传输层(Transport layer)：接收上一层的数据，必要的时候分割成较小单元并传递给网络层
    • 是端到端的层
  5. 会话层(Session layer)：允许不同机器上的用户建立会话
    • 对话控制、令牌管理、同步功能等
  6. 表示层(Presentation layer)：所传递信息的语法和语义
    • 如Big endian和Little endian
  7. 应用层(Application layer)：包含各种协议
    • HTTP、telnet、FTP、DNS、DHCP、SMTP、POP等
TCP/IP参考模型
  • Application -> Transport(TCP/UDP) -> Internet(IP/ICMP) -> Link/Host-to-network(DSL,802.11…)
  • Internet layer: defines an official packet format and protocol called IP(Internet Protocol)
  • Transport layer: 允许源主机和目标主机上的对等实体进行对话
    • TCP(Transport Control Protocol, 传输控制协议): a reliable connection-oriented protocol
    • UDP(User Datagram Protocol, 用户数据报协议): an unreliable, connectionless protocol
对比
  • OSI区分了服务/接口/协议，TCP/IP没有
  • OSI现有的模型才有的协议，TCP现有的协议
  • OSI同时面向连接/无连接，TCP在网络层只支持无连接、传输层支持两种

物理层

信道的最大数据速率

尼奎斯定理：带宽B，每秒2B次采样，信号包含V个离散等级，最大数据速率 = 2B*log2V (bit/s)
香农定理：信噪比S/N时最大比特率 B*log2(1+S/N)

无线传输

带宽越宽，速率越高

  1. 跳频扩频
  2. 直接序列扩频：码分多址(CDMA)he
  3. 超宽带通信

塔越高，传得越远。但是会有多径衰落(multipath fading)和天气影响

数字调制

  • 基带传输
  • 通带传输

多路复用

  • 频分复用
  • 时分复用
  • 码分复用

数据链路层

提供给网络层的服务

  1. 无确认无连接：不确认帧。错误率低（如以太网）、实时通信（语音传输）
  2. 有确认无连接：每一帧都需要单独确认。信道差（如WiFi）
  3. 有确认有链接：每一帧都编号、确保每一帧都收到且每一帧都被接受一次。长距离切不可靠（如卫星信道或长途电话）

成帧

  1. 字节计数法（不用）
  2. 字节填充的标识字节法：数据中的标志字节需要转义、转义字符也需要转义（PPP）
  3. 比特填充的标志比特法：
  4. 物理层编码违禁法

纠错码

  1. Hamming code
    • m个消息位和r个校验位，(m+r+1)<=2^r (求r用)
    • 计算出m+r后填入r，把所有1的位置改写成二进制。对这些位置求异或，结果直接填入r的位置
    • 检测d个错误需要d+1海明距离的海明码；改正d个错误需要2d+1
    • 只能纠错1位
  2. 奇偶校验
  3. 校验和
  4. CRC
    • G是r+1为，则在M后加上r个0
    • 不借位减法，做完余数加上4个0，跟在M后面

Utilization of Stop-and-Wait

T_prop = Distance / Speed-of-Signal (注意是两倍距离)
T_frame = Frame-Size / Bit-Rate
Utilization = T_frame / (2*T_prop + T_frame)
α = T_prop / T_frame

改进：Utilization of window
Utilization = N * T_frame / (2*T_prop + T_frame)

Go-Back-N ARQ

在阻塞之前发送w个帧
带宽-延迟乘积：BD
w = 2*BD+1
链路利用率<= w/(1+2*BD)

PPP

有空再回来看

介质访问控制子层

静态

  1. TDM：时分复用
  2. FDM：频分多路复用

ALOHA

  1. 纯ALOHA：信道使用率很低
  2. slot-ALOHA：一个时间槽一帧，转换成脉冲输出

CSMA（载波侦听多路访问协议）

  1. CSMA：监听信道，如非空闲则监听直到空闲开始发送
  2. 非坚持CSMA：监听信道，如果非空闲则停止监听，随机等待一段时间后重复上述算法。利用率更高，但是延迟也更高。
  3. 带冲突检测的CSMA（CSMA/CD）：以太网，可以看做slot-ALOHA，时间槽2τ（τ是最远两个站之间传播时间）
  4. 带冲突避免的CSMA（CSMA/CA）：无线局域网，早期后退避免冲突、利用确认推断是否发生冲突。是分布式协调功能（DCF）

MACA（冲突避免多路访问）

核心思想：使用一个短帧通知附近的站，放置在接下来的大传输中冲突

  1. RTS：30字节，包括发送数据帧的长度。其他收到RTS的站在确保CTS收到之前要沉默。
  2. CTS：也包含数据帧长度。其他收到CTS的站在确保数据传输完成前要沉默。
  3. 仍会有冲突，比如两个站同时发送RTS。此时没有收到CTS的说明传输失败，等一段时间再试

以太网

802.3: T/L<=0x600=1536

网桥（交换机）

工作在数据链路层
Bridge里不能有环路，所以要形成Tree

  1. 向后学习算法
    • 目的端口==来源端口：立即丢弃该帧
    • 不同：转发到目标端口
    • 未知情况：泛洪算法，向除来源端口外所有端口转发该帧
    • 向后：可以通过“来源端口=目的端口”判断
  2. 生成树算法
    • 先基于MAC地址选择根，标识符最低的为根
    • 构造从根到每个网桥的最短路径树
    • 并不是所有连接（甚至桥）都必须出现在树中，因为需要关闭一些端口防止出现环路

联网设备

  • 应用层：应用网关
  • 传输层：传输网关
  • 网络层：路由器
  • 数据链路层：网桥、交换机
  • 物理层：中继器、集线器

网络层

网络层的设计问题

  1. 存储转发分组交换
  2. 为传输层提供的服务
  3. 面向连接服务的实现
  4. 虚电路或数据报子网的比较

路由算法

  1. 最短路径路由：Dijkstra
  2. 泛洪算法：需要给包头加一个生命长度，一般是到目的的距离，最坏是网络的直径
  3. 距离向量路由：每个路由器维护一张表，表中列出当前已知的到每个目标的最佳距离，以及所用的链路。邻居之间交换信息更新。（RIP）
    • 计算方法：收敛
  4. 链路状态路由：（OSPF）
    1. 发现它的邻居节点，并了解其网络地址
    2. 设置到每个邻居节点的距离或成本度量值
    3. 构造一个包含所有刚刚获知的链路信息包
    4. 将这个包发送给所有其他的路由器，并接受来自所有其它路由器的信息包
    5. 计算出到每个其它路由器的最短路径（Dijkstra）
  5. 分层路由：region -> cluster -> zone -> group …

网络互联

回头再说

IP

回头再说

传输层

  • 帧：数据链路层
  • 包：网络层
  • 段：传输层

Berkeley Socket

其实没啥

应用层

网络安全