Computer Networking 2--Routing

Posted on Edited on In Word count in article: 1.5k Reading time ≈ 6 mins.

What is Routing?

End Host and Router

我们先说明 End Host 和 Router 的区别。

前者是网络中一条线路的端点，他只负责接受、发送自己的信息，而不负责“传送”任务。 后者则相反，仅仅起到中介的作用。

Packets

我们之前说过，Packets 是 Internet Layer 传送的基本单元。

为了正确地在互联网中传送数据，我们显然需要指明 Source 和 Destination。 他们需要一个唯一的标识符。

这个标识符是怎么来的，姑且先不考虑。在有了这个标识符之后，我们便在 packet 的头部加上 Source Address 和 Destination Address 两个元素。

Routing States

What is Rouing State

Routing States 最简单的说，是一种策略。即当 router 接收到一个 packet 的时候，根据这些策略，便能成功地把信息传送到目的地。

其中，最重要的、也是最泛用的策略被称作转发表/Forward Table

Forwarding Table

理论上而言，我们可以建立一张表：这张表直白的告诉我们，如果我想把一个 packet 送到一个地方，我的 next hop 应该是什么。

在现实中，next hop 往往不是指一个抽象的地点，而是指物理上的一个 port

Routing vs. Forwarding

我们现在区分两个概念：routing 本身指的是填充 forwarding table 的过程，而 forwarding 指的才是转发 packet 的过程。

因此，forwarding 本身并不需要知道 forwarding table 是如何计算的，故它是一个局部的动作。

相反，routing 本身要求我们必须对于整个网络结构有一个认知，因此这是一个全局的过程。

Distance Vector Protocols

Distance Vector Protocols 的主要内容如下：

For each destination:

  • If you hear an advertisement for that destination, update the table and reset the TTL if:
    • The destination isn’t in the table.
    • The advertised cost, plus the link cost to the neighbor, is better than the best-known cost.
    • The advertisement is from the current next-hop. Includes poison advertisements.
  • Advertise to all your neighbors when the table updates, and periodically (advertisement interval).
    • But don’t advertise back to the next-hop.
    • …Or, advertise poison back to the next-hop.
    • Any cost greater than or equal to 16 is advertised as infinity.
  • If a table entry expires, make the entry poison and advertise it.

我们分条来看。

Update Rules

我们如果从毗邻的节点接收到一条 (from, to, cost, TTL) 的信息，我们进行如下的判定来决定要不要更新我们的 forwarding table:

  1. 最明显的，如果我根本没有到 to 的路径，那我肯定要加上这条
  2. 这条路径比我现在手上有的要更快，我肯定选择它更好
  3. 这条路径是从我当前的最优的 next hop 发来的，这说明 next hop 有更新，它到 to 的距离发生了变化，有可能不再是最优解。为了保证正确性，我现在先更新这条，等后面别人广播的时候自然会更新成正确答案。
  4. 或者，如果是 poison 的，也就是 “我无法到达某个目的地” 的信息，那么我收到的 Cost 就是无穷大，类似 3，我也要更新。

我们通过不停广播自己的信息来使得这个网络达到收敛态/converge

  1. 首先，我们必须定时广播信息，告诉我的邻居们我还在线，以及我到某个目的地的最小 cost 是多少
  2. 但是注意，我们不能反向告诉 next hop，否则，如果 next hop 失效（不再能够到达目的地），它会误以为通过我还能抵达目的地，造成死循环（这被称作 Split Horizon 原则）
  3. 或者，我们定时广播时，反向告诉 next hop，我不可以到达 A（即，我是从 next hop 来的，我不能把 packet 再返回给你）。这被称作 Poison Reverse，往往是比 Split Horizon 更有效的广播方式
  4. 如果我们已经有一个死循环了，我们该怎么办？方法很简单，给定一个上限，如果 cost 超过了这个上限，我们就认为他是无穷大/不可达的。

Overview

Link-state protocols in one sentence: Every router learns the full network graph, and then runs shortest-paths on the graph to populate the forwarding table.

直白地说，Link-state 协议通过让所有路由器都有全局信息，使得他们并行计算（通过 Bellman-Ford/Dijkstra 等最短路算法）出自己的next hop 但这显然引起了一个问题，如果 A 计算的最短路径和 B 计算出的路径不一致怎么办呢？

因此，我们做出以下 4 条约定：

  1. All routers have to agree on the network topology. Suppose a link failed, but only one router knows about it. Then different routers are computing paths on totally different graphs, and might produce inconsistent results.

  2. All routers are finding least-cost paths through the path. If one router preferred more expensive paths for some reason, we would get inconsistent results.

  3. All costs are positive. Negative costs could produce negative-weight cycles.

  4. All routers use the same tiebreaking rules. If we assumed shortest paths are unique, then the previous two conditions are sufficient to ensure everybody picks the same path. This condition additionally ensures that if there are multiple paths tied as the shortest, everyone chooses the same one.

Learning About Graph Topology

  1. To discover neighbors, every router sends a hello message to all of its neighbors. For example, in this network, R2 sends to both of its neighbors: “Hello, I’m R2.” Now, R1 knows that it’s connected to R2, and R3 also knows that it’s connected to R2. Similarly, R1 says hello to R2, so now R2 knows about R1. Likewise, R3 says hello to R2, so R2 also knows about R3.

    As a result, everybody now knows who their immediate neighbors are. Note that R1 does not know about R3, because R1 and R3 are not neighbors.

  1. Now that we know about our neighbors, we should announce that fact to everybody. To make a global announcement, we send the announcement to all of our neighbors. Also, if we ever receive an announcement, we should send it to all of our neighbors as well. This ensures that every message gets propagated throughout the network. This is known as flooding information across the network. If any information changes (e.g. a neighbor disappears), we should flood that information as well.
  1. avoid infinite flooding: When we see a message for the first time, send that message to all neighbors, and write down that we’ve seen that message. (We have to write down this message anyway, since we’re trying to use this information to build up the network graph.) Then, if we ever see that same message again, don’t send it a second time.