计算机网络&信息论

Konata Lv1
  2025-11-24 16:57:05 2025-11-24 16:57:05 创建   2025-11-24 17:05 2025-11-24 17:05 更新      

计算机网络

1. 应用层

2. 传输层

传输层职能：处理端到端的传输，保证数据传输的可靠性（类比快递调度中心 - 决定以及确保包裹最后送达具体门户， 但不确定具体的路程）
  1. Multiplexing/demultiplexing - 保证发送可以同时送出多个应用层应用传达的；保证接收方能同时接收多个应用层应用的包(packet)
    1. 实现方法： 端口号(port) - 发送时同时指明ip地址和端口号，接收时用端口号对应应用
      1. TCP socket 的识别组为
        (Source IP / Source Port Number / Dest. IP / Dest. Port Number) 说明接收方可以直接通过socket识别发送方
        UDP socket 只有 (Dest. IP / Dest. Port Number) 必选 - 说明 UDP 没有办法直接在传输层上识别发送方，需要应用层处理
  2. UDP - 一种简单的、无连接的传输层协议，定义于 RFC 768，用于在网络中传输数据时追求快速性和效率，而不强调可靠性。
    1. 简单/无连接 - 发送packet之前没有握手(handshake)阶段
    2. 不可靠 - 没有 建立连接/ACK重传/超时重传/接收顺序限制/拥堵控制/流量控制
    3. 轻量快速 - 报文头短 (8字节 - 源端口号 + 目的地端口号 + 长度 + checksum)
    4. Checksum - 把报文看作16bit 数字，求和之后按位取反就是UDP checksum（weak protection, 因为符合checksum ≠ segment未被篡改）
  3. Reliable Data Transfer - 可靠数据传输的理想模型
    1. RDT1.0 - 可信通道的传输，无丢包，无corruption
    2. RDT2.0 - 添加ACK/NAK文件，当初始信息错误时传输NAK文件, 然后sender重传；否则传输ACK文件
    3. RDT2.1 - 添加序号0/1，在其中一个包的ACK/NAK文件，或者包本身出现corruption时接收方发送NAK通知sender重传当前序号的包。否则发送ACK, sender发送下一个序号的包
    4. RDT2.2 - 去除NAK, reciever只为最后一个ACK的包发送ACK包，sender如果接收到重复ACK就等于丢包/bit error = 重传
    5. 以上RDT2.0 - RDT2.2是对bit error(也即出现错误)的对应方式，但不支持丢包(lose)
    6. RDT3.0 - 增加对丢包的支持：既在sender处增加计时器，超时则重传，接收到ACK则重新开始计时；如果收到了错误的ACK则不产生任何影响。
  4. Piplining - 通过流水线发送的方式解决RDT3.0的效率问题
    1. 如果每次发送包都要等到接收ACK在进入下一个状态，那么每次都需等待RTT(粗略理解为 路程/时间， 既propagation delay * 2) + transmission delay(数据长度/带宽, 既L/R), 那么效率是非常低下的，所以我们引入流水线机制(Pipeline)
    2. 引入Sender Utility计算公式，衡量发送方处在“正在发送”的时间在整个消息传输时间中的占比。其公式为 U = 发送数据的时间 / (RTT + L/R) 当只发送一个包时时间为L/R
    3. Pipeline - 也就是 在一个RTT+L/R内，发送第一个L/R后不等待ACK而是直接继续发送下一个包(L/R)。这样 U = (发送的包数量 * L/R) / (RTT + L/R)
    4. 下面提供2种 Pipeline 的管理机制 Go-Back-N 和 Selective Repeat
    5. Go-Back-N(GBN)
      1. 每个包标有顺序的序号
      2. 发送方确定一个序号窗口，在一个RTT+L/R内发送这个窗口
      3. 接收方发出的ACK#n代表 到n号包全部ACK，没有NAK文件。接收方只接受按序到达的包
      4. 超时事件仅针对窗口中最早未被确认的包，如果超时则重传比这个序号大于等于这个包的所有包
    6. Selective Repeat
      1. 同样每个包标有序号
      2. 发送方确定窗口，为窗口内每个包单独设立计时器。每个包可以单独被重传
      3. 如果收到的ACK(n)是当前窗口最小的文件，那么推进窗口到下一序号(n+1)
      4. 接收方buffer收到的乱序文件，正序文件传输给上一级
      5. Selective Repeat的问题：发送方认为窗口中某个序号的包还没被确认，于是重发它；接收方却认为这个序号属于新一轮的传输窗口，于是将“老包”误认为是“新包”。这是由窗口空间和序号空间的关系导致的。为防止这一现象，需要 窗口空间 ≤ 序号空间/2
  5. TCP = RDT3.0 + Pipelining + Flow control + congestion control
    1. Full duplex - 在同一连接中可以双向数据流动, 双方都可以同时发送数据和确认对方数据。
    2. Connection-oriented - 在数据交换之前先进行握手
    3. Timeout时间的计算
      1. EstimatedRTT = (1- α)* EstimatedRTT + α * SampleRTT (通过当前的RTT和过去RTT估算一个estimated RTT) 通常 α = 0.125。这是一个 指数加权移动平均（EWMA）
      2. DevRTT = (1-β) * DevRTT + β * |SampleRTT - EstimatedRTT| (DevRTT - Safety margin/偏差程度) 通常 β = 0.25。
      3. TimeoutInterval = EstimatedRTT + 4 * DevRTT
    4. TCP Reliable Data Transfer - 使用cumulative acks，但是与GBN有几点区别：
      1. 接收方缓存乱序的包
      2. 发送方只重传超时/和duplicate ACK的包
      3. 接收方在接收顺序包时会等待一段时间再发送ACK文件(delayed ACK), 由此借用cumulative ack减少ACK的数量
      4. Fast retransmit - 如果收到3个相同包的ACK, 则重传未ACK的最小的包
    5. Flow control - Sender控制传输速度和大小防止Reciever缓冲区溢出
      1. 系统设定RcvBuffer大小
      2. TCP报文中rwnd位置表明这个大小, Sender根据这个大小控制发送
    6. Connection Management - 通过握手(handshake)确立连接和连接参数
      1. 2-way handshake - 一方发送连接信息，另一方ACK
        1. 问题1：在连接被关闭以后再收到超时重传的开始连接信息会导致单方面的开始连接(无效连接)
        2. 问题2：服务器不清楚对方是否接收到ACK，如果直接开始传输数据可能会导致不被送达
      2. TCP 3-way handshake
        1. Client发送SYN flag, 请求连接，同时发送Client初始seq
        2. Server发送SYN+ACK flag + ACK=Client seq + 1, 表明收到client的SYN并请求连接，发送Server初始seq
        3. Client发送ACK flag + ACK = Server seq + 1，建立连接 (这一步可能发送数据)
      3. Close a TCP Connection - 双方都发送FIN Flag, 各自ACK对方的FIN flag之后关闭连接
    7. Congestion Control in general
      1. 表现形式(manifestations): Long Delays / Packet Loss
      2. End-to-End Congestion Control - 端从延迟和丢包中推测是否发生拥堵，并从TCP(端)中采取措施
      3. Network-assisted Congestion Control - 路由/交换机 直接告知主机出现了拥堵 或者直接告知主机网络负载情况。路由器/交换机直接参与congestion control
    8. TCP congestion control
      1. 本质是更改TCP的发送速率(效率)，也即是在Pipeline一节中提到的Sender utility(U), 在网络情况好时增大Pipeline中包的数量，在网络差时减少
      2. cwnd(congestion window) - 也就是Pipeline中包的数量
      3. 策略1：AIMD - Additive Increase, Multiplicative Decrease. 每个RTT cwnd增加1MSS, 遇到丢包则cwnd减半.
      4. 策略2：Slow Start - 每次收到ACK都将cwnd增加1, 既每个RTT cwnd都翻倍，遇到丢包减半，然后将ssthresh 设置为这个cwnd, 之后进入AIMD。
      5. Fairness - 占用多的连接下降得更多，增长速度相同 → 渐渐趋于平均
        1. 对于2连接的情况，可以假设过了SS阶段后两者差值不变，由于AIMD而都以同一速率线性增长，所以增长时差值不变，减半时差值也减半。

3. 网络层

网络层职能：决定去哪里（路由选择/Routing）+ 怎么去（转发分组/Forwarding），确保每个数据包从源头走到终点(类比邮政网络)

根据这个职能，我们也可以将网络层在逻辑上划分为2个部分，分别是Data Plane对应围观上的如何Forwarding(根据路由表操作)和Control Plane对应宏观上如何Routing(如何建立路由表)

转发分组/Forwarding

  1. Router - 转发包和维护路由表。路由器由input port / switching fabric / output port 按顺序构成
    1. Input port ![[Pasted image 20250715103832.png|300]]
      lookup/fowarding @ input port = decentralized fowarding = 根据报文头的值查路由表然后送至对应的output端口。Decentralized fowarding又分为以下两种
      1. Destination-Based Forwarding - 根据目标IP地址转发
      2. Generalized Forwarding - 根据报文头中的任意字段转发
    2. 对于Destination-Based Forwarding，算法使用的是Longest prefix matching既匹配最长前缀
    3. Switching fabric - 将input link发送的包传输到output link. 他的衡量指标是传输速率
    4. Switching fabric - 共有3种类型memory(内存)，bus(总线), interconnection network(交叉网络?)
      1. Memory - 包通过系统共享内存传输，速率取决于内存带宽，通常是几十Mb/s - 几十MB/s
      2. Bus - 包通过共享总线传输，速率取决于总线带宽，通常是几 Gb/s
      3. Interconnection network - 输入/输出端口通过多条并行通道互连。速度为N * 线速，可扩展到Tb/s级别 ![[Pasted image 20250715120135.png|200]]
    5. Queuing - 处理速度<包到达的速度
      1. Head of Line Blocking - 排位较前的包阻塞排位较后但是可以传输(对应端口空闲)的包 或者 两个端口都需要向同一个output端口传输数据 必须有一个等待，也视为一种HOL
  2. IP protocal - 实现主机之间的数据包传输与寻址。它是 无连接（connectionless） 和 不可靠（unreliable） 的协议
    1. IP fragmentation - 当一个 IP 数据报太大，无法通过某个网络链路的 最大传输单元（MTU） 时，将其分割成多个更小的数据报段，每个段都可以独立传输，再由接收方主机进行重组还原出原始数据。IPv4在每个经过的路由器上都可以进行fragmentation；IPv6不允许中间路由器分片
      1. Subnet - 不经过路由器即可互联的设备集合(连接到同一个interface)
    2. Addressing - Classless InterDomain Routing (CIDR)，划分形式: IP地址/前缀长度，其中前缀长度相当于子网掩码
    3. 如何获取IP地址
      1. 一个网络如何获取自己的IP地址？
        • 通过供应商的ISP获取 (ICANN - ISP - Network)
      2. 网络内部的设备如何获取自己的IP地址？
        • DHCP
    4. DHCP - 在加入网络时从服务器动态获取IP地址，地址仅在设备连接时保存，设备退出网络后地址可以复用。适用于网络内部的设备获取自己的IP地址。以下是具体过程:
      1. 客户端发送DHCP discover，查找网络中的DHCP服务器(optional)
      2. DHCP服务器回复DHCP offer (optional)
      3. 客户端发送IP地址请求DHCP request
      4. DHCP服务器发送IP地址DHCP ACK
    5. DHCP还可以告知：1.下一级路由器的IP 2. DNS服务器的名称和IP 3.子网掩码
    6. NAT: network address translation - 将子网IP翻译成公网IP, 每个子网只对应一个公网IP
      1. 优点：
        1. 子网设备不能直接被公网访问，安全性提高
        2. 节省IPv4地址
        3. 内部地址灵活管理，网络重构或设备更换时不影响外部通信配置
      2. 缺点：
        1. 打破端到端的通信模型
        2. 增加配置复杂性
        3. 不是真正的安全机制，依赖 NAT 可能导致误判
    7. IPv6 - 128bit 地址 / datagram 中没有checksum, fragmentation 和 option
      1. 因为还有不支持IPv6的路由器，所以使用Tunneling, 将IPv6作为payload放在IPv4的包中
  3. Generalized Forwarding/SDN (OpenFLow) - SDN下发一张flow table给路由器和交换机，这张表可以匹配文件头中的任意一个字段来进行操作
    1. 这张表包含如下的字段
      1. Match - 需要在报文头中匹配的字段和值
      2. Actions - 匹配成功后执行的动作(drop, forward, modify, matched packet or send matched packet to controller)
      3. Priority - 这条规则的优先级
      4. Counters - 流量统计信息（比如匹配次数、字节数）
    2. 抽象化 - match + action

路由选择/Routing

  1. 路由算法分类 - global/decentralized, static/dynamic
    1. global/decentralized - 表示路由算法掌握的数据限制
    2. static/dynamic - 表示路由表更新的快慢
    3. global + dynamic = 每个路由器都知道全网拓扑，并能根据变化快速更新 = Link State（链路状态）算法（如 OSPF）
    4. decentralized + dynamic = 路由器只知道邻居，但能动态根据变化调整 = Distance Vector（距离向量）算法（如 RIP）
  2. Autonomous Systems(AS) - 路由器的聚合形成AS, AS聚合形成互联网。路由可以分为AS内部(intra-AS)，AS间(inter-AS)两种。从一个AS连接到另一个AS的路由器称为gateway router. Routing table由intra-AS routing 和 inter-AS routing 两套算法共同确定。
  3. Intra-AS Routing Algorithms - RIP / EIGRP / OSPF
    1. OSPF: Open Shortest Path First
      1. Router通过IP协议向AS内部全部Router广播OSPF link-state
      2. 可以获得link cost矩阵
      3. Router有整个AS的地图，通过Dijkstra algorithm计算最短路
      4. 所有OSPF信息都经过验证
    2. Hierachical OSPF - 在OSPF的基础上将一块AS划分为数个Area和一个Backbone. Area之内Router互相flood link state. Area border Router 将Area内部的连接信息告知Backbone. Backbone区域内部再单独进行OSPF。只有Backbone中的Boundary router连接到其他区域，其余部分都不连接到其他AS
  4. Inter-AS Routing - BGP(Border Gateway Protocol)
    1. BGP session - 是半永久TCP session(长期连接，只在人工干预或者不可抗力下断开)。两个处在不同IP前缀(prefix)的路由器通过这个session交换path信息
      1. Path信息包含三个部分：
        1. Prefix - 目的地的网络前缀
        2. AS-PATH - 经过的AS(或者说)
        3. NEXT-HOP - 到达目的的路径上距离当前最近的路由器(非同一AS内)
      2. 每个路由器不知道完整的路径，只知道到达当前路由器经过的路径和下一跳路由器的地址
      3. Policy-based routing - 路由器根据既定好的policy来选择是否接收当前被传播到的路径
      4. 除此之外的选择方案有最短AS列表/最近NextHop
  5. 为什么要区分Intra-AS / Inter-AS ?
    1. 每个AS的管理员对于Routing有不同的规则
    2. Hierarchical routing可以减小routing table的大小
    3. Policy VS. Performance - 关注点不同
  6. Software defined networking (SDN)
    1. Motivation
      1. 网络管理更简单
      2. 自定义(可编程)路由更方便
    2. 具体实施 - 将互联网分为3个层级 - Data Plane Switches / SDN controller (network OS) / Network-control apps 后两者合在一起是Control Plane
      1. Data Plane Switches - 负责根据上一级下发的flow table做简单的转发。保持跟上一级的联系，API for table-based switch control（OpenFlow）
      2. SDN controller (network OS) - 一个承上启下的分布式系统，用于保存网络状态(包括拓扑信息，带宽和链路状态)
      3. Network-control apps - 负责策划网络，包括：路由计算，访问管理，负载均衡等。可以由第三方机构提供。比如OSPF的Dijkstra算法应该跑在这一层

4. 数据链路层

数据链路层职能：决定数据在两个直连设备间的传输方式，同时保证数据可靠、有序地传输。数据链路层在网卡(NIC)中实现，是硬件，软件，固件的结合。
  1. 数据链路层提供的服务:
    1. Framing
      1. 将packet封装成datagram，提供文件头，文件尾
      2. 为处在同一传输通道协调谁什么时候可以发送数据
      3. 确定物理地址(MAC)
    2. 相邻节点(路由器)的可靠传输
    3. Flow control
    4. Error detection
    5. Error correction
  2. Why we need both link-level & End to end reliability?
    1. Errors Can Still Occur Beyond One Hop
    2. Link-layer retransmissions don’t detect end-to-end failures
    3. Different networks, different reliability
    4. Local retransmissions are more efficient
    5. Some protocols don’t need end-to-end reliability
  3. Error detecion
    1. Parity Checking
      1. 一维Parity - 对行求和
      2. 二维Parity - 每行和每列都计算checksum bit
    2. Cyclic Redundancy Check (CRC) - 被广泛使用，如以太网，802.11 WiFi
      1. 首先确定 CRC bit 长度 n，然后根据长度确定 pattern (除数) G（n+1位）
      2. 在原二进制数据最后加上 n 位的 0
      3. 使用G与原数据用除法的方式按位异或，除法过程中遇到0开头则跳到下一个1开头的位置
      4. 除法完成后在新加入的 n 位上留下余数，这就是CRC的输出
      5. 在校验时将 n 位余数添加到数据最后端，然后用G在进行一次除法，如果余数=0则校验成功
  4. Multiple access protocols
    1. 理想MAC协议的特征
    2. Channel Partitioning
    1. TDMA - Time Divisioning Multiple Access
    1. 将channel中的节点划分成n个时间slot，每个设备在自己的slot中发送，没有消息发送则保持channel空闲
    2. FDMA - Frequency Divisioning Multiple Access
    1. 将channel中的设备划分成不同的频段，每个节点分配一个频段
    3. Random Access - 当节点需要发送消息时则直接使用整个带宽发送，如果两个或多个节点需要发送消息则发生collision。RA算法需要解决 1.如何检测collision 2.如何从collision中恢复
    1. Slotted ALOHA
    1. 假设:时间被划分成等长slot，所有node的datagram大小一致，可开始发送的时间点一致，如果部分节点检测到collision则所有节点都设为collision状态。
    2. 节点收到datagram直接在下一个slot中发送。如果发生collision，节点在接下来的每个slot以p的概率发送datagram直到成功
    3. 优点：1. 单个节点在发送时可以享受完整带宽 2.实施简单 3.各个节点可以独立地运行发送逻辑，没有中心控制节点
    2. CSMA - Carrier Sense Multiple Access
    1. 如果channel空闲 - 传输整个frame。 如果channel忙碌，等待
    2. CSMA/CD - CSMA with collision detection
    1. - 发送过程中继续监听信道. 如果监听到自身发送的信号与信道上的不一致 → 发生了碰撞
    2. 发送 Jam Signal
    3. 使用指数退避算法（Binary Exponential Backoff） 等待随机时间后重新发送。时间 T = K * 512bit，其中 K 在 [1, 2^m-1] 中任意选取，m为collision计次
    4. “Take Turns”
    1. Polling - master node “invites” other nodes to transmit in turn
    2. Token Passing - control token passed from one node to next sequentially.
  5. LAN
    1. MAC - 物理地址：48bit 地址，一般烧录在网卡储存中。作用是在同一子网内将一个frame从一个interface送到另一个物理上连接的interface
    2. ARP - address resolution protocol - 根据ARP table将IP地址翻译成MAC地址，table中的条目有存在时限TTL
    3. Ethernet - wired LAN technology
      1. Bus - All nodes in same collision domain(Apply CSMA/CD)
      2. Switched - 中央有一个数据链路层的交换机
      3. Ethernet frame结构 - Preamble(同步时钟频率) + Destination MAC address + Higher Layer Protocal +CRC
      4. Ethernet特点
        1. Connectionless - 不需要建立连接
        2. unreliable - 接收方不向发送方发送ACK或者NAK
        3. 使用CSMA/CD
    4. Ethernet Switch - store, selectively forward Ethernet frames using MAC address and CSMA/CD
      1. Transparent - unaware to users
      2. Self-learning - No need to configure
      3. 连接都使用以太网协议，所以不能同时从两个节点经由交换机发送向同一个节点，会导致collision
      4. 当Switch遇到未识别的MAC地址时会自动向局域网广播需要发送的信息，收到回复后加入Switch table (Self-Learning)
  6. 无线连接和WLAN
    1. 与有线网络的异同：
      1. 无线传输
        1. 信号强度随距离衰减
        2. 可能收到其他基站/信号的干扰
        3. 物理反射可能造成信号多次到达
      2. 移动性 - 设备位置不固定(可能更换接入点)
    2. 无限传输的三个组成部分
      1. 主机 - 运行应用，位置可能移动
      2. 基站 - 大部分是接入传统的有线网络，负责在区域内接收和发送包
      3. 传输介质 -
    3. IEEE 802.11
      1. 无线传输中很难执行Collision detection
        1. 发送方信号远强于接收端信号，所以发送时不能同时接收，既不能发送到一半然后在检测到collision时停止发送(CSMA/CD)
        2. 两个发送者可能互相听不到对方的信号
        3. 如果发生碰撞，信号会严重干扰，接收端往往无法检测和恢复出原始信号，既无法执行数据链路层的error correction
      2. 所以改用CSMA/CA - CSMA/Collision Avoidance 在发送前感知collision
        1. 发送前sense channel, 如果空闲，等待DIFS然后发送
        2. 如果channel忙碌，那么设置一个随机时间的timer，在channel空闲以后开始倒计时，倒计时结束后直接发送数据包
        3. 接收方，接收到数据包以后等待SIFS，然后发送ACK，表示接收到数据
      3. RTS - CTS Collision Avoidance模型
        1. 用于解决 Hidden terminal 和 Exposed terminal 问题。
        2. Hidden Terminal - A,C都可以检测到B，而A,C 互相不能检查到对方。都给B发送信息时会造成 B 处 collision
        3. Exposed terminal - 一个终端会假设他周围的终端的发信息回影响到自身的信息发送
        4. 发送方法先给基站发送Request to Send（RTS）请求发送文件
        5. 基站收到某个RTS后，对所有节点广播一个Clearing to Sending(CTS)
        6. 所有节点收到CTS之后，暂停发送行为。这是channel空闲
        7. 发送方发送数据
  • 标题: 计算机网络&信息论
  • 作者: Konata
  • 创建于 : 2025-11-24 16:57:05
  • 更新于 : 2025-11-24 17:00:05
  • 链接: http://blog.suzumiyaharuhi.net/2025/11/24/计算机网络&信息论/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
计算机网络&信息论
  1. 计算机网络
    1. 1. 应用层
    2. 2. 传输层
    3. 3. 网络层
      1. 转发分组/Forwarding
      2. 路由选择/Routing
    4. 4. 数据链路层