C|计算机网络|Network Layer-路由层
C|计算机网络|Network Layer-路由层
All from CSE course in IPADS SE SJTU
Background
Network(Router): IP address
负责next hop。每个路由有route table，根据路由协议（防止呈环），逐渐找到正确的地址。
Feature
- Discard Packet
IP地址是best-effort网络（尽力），因此如果无法dispatch，会丢包。
另一种是store-and-forward network（Guaranteed-delivery），这种网络追踪所有的消息并进行出错处理，以确保消息没有丢失（一般是一整条消息，而不是某个包）
后者一般在更高的层次进行处理，而IP地址只保证尽力。
- Duplicate Packet
超时重发，这导致用户必须处理多次重复的request和response，根据实际情况决定如何处理
Network Layer
Router
当包进来时，路由器根据路由表，决定包的下一个网口出口。路由表通常放在cache里，以确保查表的效率。
由于网络的多变，不能使用静态的Route Table。路由器需要计算资源进行下面这些事，从而实现适应性的路由。
- 计算最佳路径
- 链接改变时重新计算表
- 链接失败时重新计算表
- 堵塞时进行适配
可以把路由的职责分为两部分。读表称为Data-plane，根据规则决定数据如何转发。写表称为Control-plane，决定如何建立路由表，定义规则。
Data Plane - packet forwarding
API
struct packet {
bit_string source //起点
bit_string destination //终点
bit_string end_protocol //上层协议
bit_string payload //包
};
NETWORK_SEND (segment_buffer, destnation, network_protocol, end_layer_protocol){
packet instance outgoing_packet
outgoing_packet.payload ← segment_buffer
outgoing_packet.end_protocol ← end_protocol
outgoing_packet.source ← MY_NETWORK_ADDRES
outgoing_packet.destination ← destination
NETWORK_HANDLE (outgoing_packet, net_protocol)
}
NETWORK_HANDLE (packet, network_protocol){
packet instance net_packet
if net_packet.destination != MY_NETWORK_ADDRESS then
next_hop ← LOOKUP (net_packet.destination, forwarding_table)
LINK_SEND (net_packet, next_hop, link_protocol, net_protocol)
else
GIVE_TO_END_LAYER (net_packet.payload,
net_packet.end_protocol, net_packet.source)
}这里的send会调用handle，因为handle本身也存在着转发的职责，相当于handle处理了本地机器让你发出的信息、其他路由让你转发的信息、给本地机器的信息。
如果路由是终点，那么就GIVE_TO_END_LAYER，由上层进行处理（如TDP）。
否则先LOOKUP next hop（找不到就丢包），更新TTL（为0丢包）和header的checksum，再通过网口交由Link Layer进行转发。
NAT（Network Address Translation）
对于私有网络,公开的路由无法进行内网的路由，导致丢包。
如下图，Send时，NAT可以把原始的地址+端口翻译成临时的公网地址（端口to端口的映射），由路由器记住这种对应关系，Receive时再翻译回去。
缺陷
- 某些e2e协议在payload放了IP（解包后就尴尬了hhh）
- 翻译可能是瓶颈（端口数有限塞不下）
- 多个私网无法合并
- 违背了分层原则（暴露了port给network层）
INTERNET/ETHERNET MAPPING
以太网使用MAC物理地址，目前作为局域网
经典的以太网使用CSMA/CD监听信道冲突。
Hub
线上只能同时发一个包，发包前需要监听信道，确认空闲后才能发包。
ETHERNET_SEND
直接把包发到Hub上
ETHERNET_HANDLE
私播（地址单个）/组播（多个MAC组成一个组）/广播（所有设备均可接受，特定的ID）
在以太网之间可以直接进行RPC。如果要发到其他以太网（比如E），那么以太网地址应该为Router（19），再由Router通过IP网络发出去。所以跨以太网发包时，包中的MAC地址会经常发生变化。
ARP (Address Resolution Protocol)
主机发送信息时将包含目标IP地址的ARP请求广播到局域网络上的所有主机，并接收返回消息，以此确定目标的物理地址；收到返回消息后将该IP地址和物理地址存入本机ARP缓存中并保留一定时间，下次请求时直接查询ARP缓存以节约资源。
如果在同一局域网下，可以不经由路由直接通过以太网通信。 NETWORK_SEND (data, length, RPC, INTERNET, N)
NETWORK_SEND (data, length, RPC, ENET, 18)
RARP则是反过来，由MAC映射到IP。
ARP Spoofing
但是，ARP协议的前提是同一局域网下，所有的主机之间都是可信的，完全信任其他主机发出的包。如果Hacker连入以太网，伪造ARP响应，污染A和B的ARP cache，从而使得他们对A/B的包都变为给C，这样C成为了A，B间的路由，从而可以随意劫持包。（Man-in-the-Middle Attack）。
一种防御方式是：使用静态的ARP条目。
另一种防御方式则是检测行为模式，发掘可疑行为。
Control Plane - routing protocol
路由器的职责在于，建立一个routing table，寻找到目的IP的最小开销路径（通常latency）。
- 先通过Hello Protocol获得邻居路由器
- 通过广告获得其他可达的路由器
- 计算已知的最短路径
两种小范围协议
P1: Link-state
对所有路由广告自己和邻居路由的通信延迟。使用Dijkstra最短路径算法。
P2:Distance-vector
对邻居路由广告自己和认识路由的通信延迟。使用Bellman-Ford最短路径算法。
P1要求所有路由都了解整个拓扑结构，scalability是很大的难题。
P2则认为路由并不需要知道全局，只需要知道next hop（也就是传给哪个邻居）。但是由于不知道拓扑结构，错误处理很难。
P2迭代过程
X接受邻居Y的广告， 为dst:Ycost键值对。 XY为XY间的latency。Ycost，Xcost为到dst的latency。
X如果正在使用Y到达dst，那么更新Xcost为Ycost + XY。
X如果没有使用Y到达dst，那么更新Xcost为min（Xcost ， Ycost+XY），并根据路径更新到dst的next hop。
本来应该由B通信C，但是因为BC发生了一次丢包，B试图通过A通信C，形成了死循环
Advance
Path-vector Routing
广播中加入路径，防止呈环
Hierarchy of Routing
一组Router作为一个region，内部使用小范围协议，外部使用Path-vector Routing
Topological Addressing
连续的IP作为一个region，CIDR Notation（CIDR: Classless Inter Domain Routing）
例如18.0.0.0/24子网掩码，代表只关注前24位，其后的IP可以随意改变。直接把整个子网掩码放在routing table里节约空间。
BGP（Border Gateway Protocol）
现在的路由协议一般为BGP，分为多Tier，上层的Region之间寻址极快（10-15个），而下层的Region向上层支付费用。T1之间互为Peer。
Customer/provider
customer向provider支付path的费用
Peer
peer之间共享customer
上层的Region的很大一部分盈利用于购买其他的Region的通行费，最终所有Region基本能互联。
这个协议在抽象角度很简单，但是由于彼此的广告和本地的路由表没有办法验证，事实上并不安全。例如某个路由作为其他路由的中间路径的话，可以对于这些流量进行劫持、读取（一般是misconfiguration）。