TCP/IP复习
coconutnut
 2023-01-08 16:57:24    

每一年前3题套路基本是一样的，重点：

  1. IP地址&路由（问请求的souce/dest、配置network box为NAT/proxy/VLAN switch后的变化）
  2. BGP（E-BGP和I-BGP，OSPF）
  3. 拥塞控制3种分配流量的方法

第四题每年有些变化，大部分有IPv6-IPv4 interworking、IP multicast相关内容

五层体系结构

  • application：HTTP、DNS
  • transport：TCP、IP
  • network：IP
  • link
    • MAC：ARP
  • physical

缩写和概念

  • DNS
    • A/AAAA record：前者用于将域名映射到IPv4地址，后者IPv6
      • 如果有一个网站不知道用v4还是v6，可以用DNS，根据收到的record类型分辨
  • TCP
    • MSS：Maximum Segment Size，指每个数据报所能携带的最大数据量
    • ECN：Explicit Congestion Notification，在数据包中添加特殊的标记，表示数据包可能会在传输过程中丢失，源端收到后，降低发送速率，从而减轻网络拥塞
  • IP
    • address prefix delegation through DHCPv6：在 IPv6 网络中，地址分配由 DHCPv6 服务器完成。当一个客户端连接到网络时，它会发送一个 Solicit 消息给 DHCPv6 服务器，请求获取一个地址前缀。如果 DHCPv6 服务器认为该请求是合法的，它会向该客户端发送一个 Advertise 消息，提供一个地址前缀。客户端收到的地址前缀可以用于分配其他地址。
  • ARP：根据IP地址查询MAC地址
    • Proxy ARP：主机A和B位于不同局域网（通常需要通过路由进行通信），可以用Proxy ARP设置路由器作为代理，接收ARP请求并返回虚拟的MAC地址
  • 路由
    • IGP：Interior Gateway Protocol，AS内使用
      • RIP：Routing Information Protocol，基于距离向量
      • OSPF：用Dijkstra计算最短路径
    • EGP：Exterior Gateway Protocol，AS间使用
      • BGP：Border Gateway Protocol
    • 距离向量路由算法
      • route poisoning：当一个路由器发现某条路径不可用时，向相邻路由器发送带有较大距离的路由信息，表示该路径不可用
  • Stub network：指一种特殊类型的路由器，它只有一条出边（或者说只连向一个直接的邻居）。在这样的网络中，所有的数据包都会通过默认网关转发，而不是进行多跳转发

套路

第一题：IP、路由

subnet mask

  • 不能太长：保证同一LAN内前缀相同

  • 不能太短：避免不同LAN内前缀相同

    • 不同LAN前缀相同的问题：The hosts will think that other hosts are on the same LAN, and will try using ARP to get their MAC addresses. To solve this, one solution is to use proxy ARP in all routers X1, X2, X3, X4 .

  • 不同LAN中，长度可以不同

ping request/ARP

  • ping的过程

    1. 查询本地路由表，看ping的是内网还是外网地址

    2. 如果是内网地址

      1. 查询ARP缓存，如果有，直接返回ICMP reply

      2. 如果缓存没有，用ARP协议在LAN内广播，要求拥有指定IP地址的主机回复自己的MAC地址

        • ARP的可见范围是LAN内

        • 如果收到，加入ARP缓存，返回ICMP reply

    3. 如果是外网地址

      1. ARP请求的IP目的地址是路由器的IP地址

      2. 路由器转发请求到外网

        • 路由器可能再次用ARP协议，查找目标主机的MAC地址

  • 注意network boxs的配置，是bridge还是router

    • 只有过router才减少TTL/HC，bridge不减（易错：host和router相连的一段没注意，直接填了64）
    • 如果是bridge
      • 注意内网有没有环，如果有，要先用spanning tree algorithm，禁用部分链接
      • 内网可以经过多个bridge，直接发给目标MAC地址（易错：把bridge看成router，填了bridge的MAC）

request经过NAT/proxy/VLAN switch的变化

  • NAT：建立{内网IP和端口，外网IP和端口}的对应

    • 内网向外发请求时，正常用自己的地址，像没有NAT一样
    • 外网向内发请求时，用NAT翻译后的地址，像内网的主机不存在一样
      • 外网的C想ping内网的A，直接ping翻译后的地址即可
    • TCP，丢包，source负责重发，NAT不负责

  • application layer gateway, acting as web proxy

    • host向server发请求时，发给proxy，像server不存在一样
    • server像host发请求时，发给proxy，像host不存在一样
    • proxy转发host的请求时，不同的host用不同的端口

  • VLAN switch：将原本相连的网络分成不同的VLAN，通信必须经过路由器

    • 如果2个VLAN链接到同一个路由，可以：configure the Y1 interface of the router with two different IP addresses, each belonging to a different VLAN

  • 题目中有ping request和HTTP两种，地址变化都一样

    • HTTP的protocol是TCP
    • HTTP over QUIC则protocol是UDP

🌰 A/B都用端口4567通过HTTP从服务器S下载文件，经过X

  1. 当X是NAT

    • A/B到X段观察（内网）

      • A/B发送的包（仿佛没有X，直接发给S一样）

        IP source IP dest protocol source port dest port
        A/B S TCP 4567 80

      • S发送的包（仿佛没有经过X，直接发给A/B一样）

        IP source IP dest protocol source port dest port
        S A/B TCP 80 4567

      • X到S段观察（外网，NAT转换后）

        • A/B发送的包

          IP source IP dest protocol source port dest port
          X S TCP 23456/23457 80

        • S发送的包（先发给X，用X的IP，和不同的端口号）

          IP source IP dest protocol source port dest port
          S X TCP 80 23456/23457

​ 实际上就是在NAT处做了一个地址映射，将A,4567换成X,23456，将B:4567换成X,23457

​ 从A/B的视角，没有X，以为是直接和S通信

​ 从S的视角，没有A/B

  1. 当X是application layer gateway, acting as web proxy

    • A/B到X段观察

      • A/B发送的包

        IP source IP dest protocol source port dest port
        A/B X的内网IP TCP 4678 8080

    • X到S段观察

      • A/B发送的包

        IP source IP dest protocol source port dest port
        X的外网IP S TCP 8923/8924 80

​ 从A/B的视角，没有S（以为X就是S）

​ X收到A/B的请求后，从不同端口转发给S

​ 从S的视角，没有A/B

路由表配置

路由器的routing table需要的几列：

Destination Network Interface Gateway
10.1/16 Xw VLAN A onlink
10.2/16 Xw VLAN B onlink
9/8 Xe onlink

  • Interface是该路由器的网络接口

    • 通常以eth0、eth1、eth2等命名，表示网卡的编号

  • 如果需要其它路由器转发，gateway填其它路由器的IP

第二题：BGP/OSPF

注意：BGP next hop是AS外部的地址，不一定直接连接，而OSPF next hop是相邻的地址

注意：题目给定的OSPF cost是一个常数，还是cost to BGP next hop加一个常数

Adj-RIB-in/out

当运行BGP的路由器收到更新时，会更新这两个表

Adj-RIB-in的列：

Destination network AS path Next hop
from C1 66.66/16 C E F 30.20.0.3 best
from C1 66.66.0/17 C E F 30.20.0.3 best

Adj-RIB-out包含best的几行

*如果上面的路由B1转发给另一个路由B2，next hop不变，仍是AS外的地址

*out只转发通过E-BGP得到的路径（不转发I-GBP得到的）

BGP

BGP如何选择最优路线的Decision process，几项常用的（详见Exam booklet）：

  1. Shortest AS-PATH
  2. E-BGP>I-BGP
  3. Shortest path to NEXT-HOP, according to IGP
  4. Lowest BGP identifier

Q：假设一个AS中只有部分路由器运行BGP，它们不re-distribute BGP into the interior routing protocol，如何让其他路由器也能知道外部的路径？

A：方法一：By configuring default gateway on all other routers. Drawback: Can not cope with link-failures. 方法二：By running BGP on all routers. Drawback: Expensive

Distance vector routing

🌰 关于更新

假设有连接A-B-net1-C-net2，原本cost都是1

原本A的路由表中有：

Destination network Next hop Distance
net1 IP of B 2
net2 IP of B 3

此时B告诉A：B到直接相连的net1的cost变成了6，A的路由表变成：

Destination network Next hop Distance
net1 IP of B 7
net2 IP of B 3

由于routing protocol还没有converge，其它暂时不变

OSPF

在某一节点，对某一目的地，BGP会根据Decision process选出最优路径，但OSPF可能会算出多条equal-cost的路径

如果有大量packet发到该目的地，一般选择每条路径的可能性相同

Q：当有多条equal-cost最短路径时，会有什么负面影响？

A：所有用Dijkstra算法计算出的最短路径都会出现在路由表中。The router then does per-flow load balancing to ensure that packets of the same flow (e.g. same TCP connection) are sent to the same next hop. This is done to improve TCP performance by avoiding reordering of packets at the destination. It is typically achieved using hash functions on flow identifiers (source and destination IP’s and port numbers).

🌰 关于获得路径的过程

假设有3个area：

  • Area 1：A，B1
  • Area 2：B1，B2
  • Area 3：B2，C

C如何获得到A的路径？

过程：

  1. B1在area 1内用Dijkstra计算到A的最短路径，然后inject the route into area 2
  2. B2在area 2内用Dijkstra计算到A的最短路径，然后inject the route into area 3
  3. C在area 3内用Dijkstra计算到A的最短路径

第三题：拥塞控制

max-min fairness

计算方法：water-filling

  1. mark all sources as non frozen
  2. Do
    • increase the rate of all non frozen sources to the largest possible common value
    • mark sources that use a saturated link as frozen
  3. Until all sources are frozen

propotional fairness

计算方法
$$
J(x) = \sum_i{ logx_i }
$$

判断分配是否propotional fair：如果改变分配，变化率符合↓，则符合propotional fairness
$$
\sum_i\frac{\Delta x_i}{x_i}\le0
$$

TCP with ECN

rate和RTT成反比

TCP Cubic：less sensitive to RTT than Reno

TCP Loss - Throughput Formula

$$
𝜃 = \frac{MSS*1.22}{RTT\sqrt{q}}
$$

其中𝜃是throughput，a fraction q of packets is lost，MSS和RTT题目会给

一般是前一问已经算出𝜃，问q

注意单位，s和bit，1 MB=10^6 bit

第四题：IPv4和IPv6

6to4

IPv6保留地址块2002::/16

IPv4保留地址块192.88.99/24（6to4 relay routers）

🌰 3.3.3.3->2002:0303:0303::，default gateway 192.88.99.1->2002:c058:6301::

NAT64

收到IPv6包后，转发给只支持IPv4的主机，步骤：

  1. 检查NAT64转换表，看是否已经为该IPv6地址分配了IPv4地址
  2. 如果没有，分配地址，将该地址添加到表中，并使用该地址转发IPv4包给目标主机

*不能用NAT64设备自己的IPv4地址

IP multicast

当receiver想加入一个multicast group，它需要发送MLD(Multicast Listener Discovery)消息。其它receiver和server不需要任何操作。

（还看到一种答案是start a program that listens to the multicast group）

multicast MAC 地址：

  • IPv4：01-00-5e-XX-XX-XX（后23bit）
  • IPv6：33-33-XX-XX-XX-XX（后32bit）
    • 🌰 ff35::6:7 -> 33-33-00-06-00-07

分片

IPv4：主机/路由器都可以对数据报进行分片

IPv6：只有主机可以对数据报进行分片

但是，路由器不会重新组装数据报。这意味着，如果数据报在网络中被分片，则接收方必须自己重新组装数据报。

补充

一些错题的知识点

Protocol type

in IP header: TCP/UDP

in Ethernet header: IPv4/IPv6/ARP

6to4

A的IPv4地址：3.3.3.3，则：

A的6to4 IPv6地址：2002:0303:0303:abcd:EUI_A

A的6to4 default gateway’s IPv6地址：2002:c058:6301::（IPv4默认网关192.88.99/24）

BGP

R1-B1-B4 R1-B2-B3都跑BGP

R1 peers with all BGP routers inside AS B

B4、B3的路线直接I-BGP发给R1，而不是通过B1、B2（不转发I-BGP学到的路径），所以在R1的表里，路径是来自BGP peer B4、B3的

ARP

The first ARP packet is broadcast and is sent to all bridges along the tree（MAC dest ff-ff-ff-ff-ff-ff）

The ARP reply is unicast from dest to source