考研笔记

CRC、校验和与路由算法伪代码

CRC 生成

输入：

  • dataBits：原始数据 bit 串，长度为 。
  • generator：生成多项式 bit 串，最高位和最低位为 1，长度为 。

输出：原始数据后附 bit 余数的码字。

function crcEncode(dataBits, generator):
    r = length(generator) - 1
    work = dataBits followed by r zeros
 
    for i from 0 to length(dataBits) - 1:
        if work[i] == 1:
            for j from 0 to r:
                work[i + j] = work[i + j] XOR generator[j]
 
    remainder = last r bits of work
    return dataBits followed by remainder

关键不变量：处理到位置 i 后，该位置及其左侧已经被消为 0，不再参与后续除法。

接收端验证：

function crcCheck(codeword, generator):
    work = copy(codeword)
    r = length(generator) - 1
 
    for i from 0 to length(codeword) - r - 1:
        if work[i] == 1:
            for j from 0 to r:
                work[i + j] = work[i + j] XOR generator[j]
 
    return last r bits of work are all zero

模 2 减法和加法都使用 XOR，不产生借位或进位。

16 bit Internet Checksum

输入为任意字节串。奇数字节时末尾临时补 0，按网络字节序组成 16 bit 字。

function internetChecksum(bytes):
    if length(bytes) is odd:
        append one zero byte for calculation
 
    sum = 0
    for each 16-bit word in bytes:
        sum = sum + word
        while sum > 0xFFFF:
            sum = (sum AND 0xFFFF) + (sum >> 16)
 
    return bitwiseComplement(sum) AND 0xFFFF

接收端把校验和字段也纳入相加：

function checksumValid(bytesIncludingChecksum):
    sum = onesComplementSum(bytesIncludingChecksum)
    return sum == 0xFFFF

UDP、TCP 计算前要拼接网络层伪首部；IPv4 首部校验和只覆盖 IPv4 首部，并把 Checksum 字段先置 0。

最长前缀匹配

每条路由包含：

(prefix, prefixLength, nextHop, interface, preferenceData)

基础最长前缀过程：

function longestPrefixMatch(destination, routingTable):
    best = NONE
 
    for each route in routingTable:
        mask = maskFromLength(route.prefixLength)
 
        if (destination AND mask) == route.prefix:
            if best is NONE or route.prefixLength > best.prefixLength:
                best = route
            else if route.prefixLength == best.prefixLength:
                best = selectByRoutePreference(best, route)
 
    return best

先按前缀长度选择最具体路由；只有前缀长度相同时，才比较协议优先级、度量或等价多路径规则。默认路由 /0 作为最低前缀长度候选。

Dijkstra 链路状态算法

输入：非负链路代价图 和源结点 source。

function dijkstra(graph, source):
    for each vertex v:
        dist[v] = INFINITY
        prev[v] = NONE
        confirmed[v] = false
 
    dist[source] = 0
 
    repeat |V| times:
        u = unconfirmed vertex with minimum dist[u]
        if u does not exist or dist[u] == INFINITY:
            break
 
        confirmed[u] = true
 
        for each neighbor v of u:
            if confirmed[v] == false:
                candidate = dist[u] + cost(u, v)
                if candidate < dist[v]:
                    dist[v] = candidate
                    prev[v] = u
 
    return dist, prev

关键不变量：选入 confirmed 的结点，其从源点出发的最短距离已经确定。链路代价必须非负。

恢复到目标 t 的路径：

path = empty list
u = t
while u is not NONE:
    prepend u to path
    u = prev[u]

路由器生成转发表时，需要从恢复路径中取源结点之后的第一个结点作为下一跳。

距离向量更新

结点 x 已知到每个邻居 v 的直连代价 cost[x][v]，并收到邻居通告的距离 DV[v][y]。

function recomputeDistanceVector(x):
    changed = false
 
    for each destination y:
        bestDistance = INFINITY
        bestNextHop = NONE
 
        for each neighbor v of x:
            candidate = cost[x][v] + DV[v][y]
            if candidate < bestDistance:
                bestDistance = candidate
                bestNextHop = v
 
        if bestDistance != DV[x][y] or bestNextHop != nextHop[x][y]:
            DV[x][y] = bestDistance
            nextHop[x][y] = bestNextHop
            changed = true
 
    if changed:
        send DV[x] to neighbors according to update policy

核心关系：周期更新、触发更新、水平分割、毒性逆转和最大距离可以降低环路与慢收敛影响，仍不能消除所有瞬态问题。

IPv4 分片

输入：原始数据报 datagram 和输出链路 MTU。

function fragmentIPv4(datagram, MTU):
    H = datagram.headerLengthBytes
    D = datagram.totalLength - H
 
    if datagram.totalLength <= MTU:
        return [datagram]
 
    if datagram.DF == 1:
        drop datagram
        send ICMP fragmentation-needed information   // 王道口径：ICMP 终点不可达报文
        return []
 
    maxPayload = floor((MTU - H) / 8) * 8
    fragments = empty list
    start = 0
 
    while start < D:
        payloadLength = min(maxPayload, D - start)
        fragment = copy relevant IPv4 header fields
        fragment.identification = datagram.identification
        fragment.offset = start / 8
        fragment.MF = (start + payloadLength < D)
        fragment.payload = datagram.payload[start : start + payloadLength]
        fragment.totalLength = H + payloadLength
        recompute fragment.headerChecksum
        append fragment to fragments
        start = start + payloadLength
 
    return fragments

若输入本身已是一个分片，再次分片时要把新片 Offset 加到原 Offset 对应的原数据位置，并正确继承最终 MF 语义。

二层交换机自学习与转发

function processFrame(frame, incomingPort, vlan):
    table[(vlan, frame.sourceMAC)] = (incomingPort, currentTime)
 
    if frame.destinationMAC is broadcast or multicast:
        flood to all forwarding ports in vlan except incomingPort
        return
 
    entry = table[(vlan, frame.destinationMAC)]
 
    if entry does not exist or entry is expired:
        flood to all forwarding ports in vlan except incomingPort
    else if entry.port == incomingPort:
        filter frame
    else:
        forward frame only to entry.port

交换机从源 MAC 学习入口，从目的 MAC 决定出口。学习表按 VLAN 隔离并随时间老化。

手算检查

  • CRC：生成多项式最高次数等于补 0 位数和余数长度。
  • 校验和：最高位进位必须回卷，最后再逐位取反。
  • 最长前缀：先列出全部匹配项，再选前缀最长项。
  • Dijkstra：每轮只确定一个当前最小未确定结点，再松弛其邻边。
  • 距离向量：每个候选都由“到邻居代价 + 邻居到目的距离”组成。
  • 分片：Offset 按 8 B，Total Length 要重新加首部，所有分片共用 Identification。
  • 交换机：学习源地址，查找目的地址；未知单播只在同 VLAN 泛洪。

链接

反向链接