CoLin's BLOG
0%

计算机网络——第5章习题

发表于 分类于 ，
本文字数： 3.2k 阅读时长 ≈ 3 分钟

课后习题和问题

5.2

  1. 集中式路由选择算法用完整的、全局性的网络知识计算出从源到目的地之间的最低开销路径，该算法以所有结点之间的连通性以及所有链路的开销为输入。这要求该算法在真正开始计算之前要以某种方式获取这些信息。具有全局状态信息的算法常被称为链路状态算法（LS）。分散式路由选择算法中路由器以迭代、分布式的方式计算出最低开销路径。没有节点拥有关于所有网络链路开销的完整信息。每个节点仅有与其直接相连链路的开销知识即可开始工作。距离向量算法（DV）属于分散式路由选择算法。OSPF协议属于集中式路由选择算法，BGP协议属于分散式路由选择算法。
  2. 这两种算法一个是集中式的，另一种是分布式的。
  3. 无穷计数问题与DV算法中“坏消息传得慢”这一特性有关。当一条链路的代价增加时，该链路两端的某一个路由器检测到代价增加，开始重新计算其到其他路由器的代价最小路由，但这个计算过程需要使用该路由器之前计算得到的到其他路由器的代价最小路由，而随着这一条链路的代价增加，这些最小路由很可能不再是最小的路由，因此每一次更新只能够将最短路由增加1，从而导致无穷计数问题的产生。无穷计数问题会导致代价增加这个“坏消息”的处理时间大大增加，严重影响到整个网络的性能。
  4. 没有必要，不同的AS的内部路由器互相不关联，因此无论当前AS使用什么内部路由选择算法，其对外部的路由器都是透明不可见的。

5.2~5.3

  1. 考虑到了以下3点因素：（P263）
    策略。有些AS可能不希望其他AS的流量经过自身，也可能希望经过，但这种策略问题在AS内部选择路由算法中并不重要，强行设计则会增加系统的冗余度。
    规模。在一个AS之内，通常网络的规模不会太大，如果一个AS内的网络规模超出了该AS内部路由选择算法的承载能力，完全可以将这个AS分割为多个AS，并通过AS间路由选择协议进行管理。这使得AS内部路由选择算法没有必要考虑当网络规模特别大时产生的诸多问题。
    性能。在AS之间基本没有与路由相关的开销概念，而在AS内部，一切的路由选择都需要将性能放在至关重要的位置，因此AS间路由选择算法与AS内路由选择算法对于性能的要求不同。
  2. 错误，OSPF属于集中式路由选择算法，其自身发送的链路状态信息需要被这个网络中的所有路由器知悉，因此该信息将会在网络中不断传递，直到被所有路由器接收确认为止。
  3. 一个区域指的是AS中的一组路由器，一个区域内可以实现自己的OSPF算法，不同区域之间通过边界路由器实现互相通信。引入区域的概念主要是用于构建大型网络，简化路由器中的路由表，并提升路由选择算法的效率。
  4. 子网是一个更大的网络中的一部分，一定隶属于某个网络，其不包含路由器，其边界是由路由器和主机接口所定义的。前缀表示的是一个子网或一个子网的集合，是CIDR化的网络部分。CIDR即无类别域间路由选择，是因特网的地址分配策略。BGP路由指的是前缀及其属性。属性包含有AS-PATH、NEXT-HOP等。当路由器通过BGP连接通告前缀时，在前缀中会包括一些BGP属性。
  5. NEXT-HOP是AS-PATH起始的路由器接口的IP地址，是BGP要前往的下一个AS中的第一个路由器地址，作用是配置路由表的下一条为NEXT-HOP指向的地址。AS-PATH记录了到目的地的一系列地址前缀，作用有检测环路、多路选择。
  6. 如果一个一级ISP不得在另两个ISP（A和B）之间运输中转流量，而该ISP与另外两个ISP有对等传输协议，该ISP只需要不将通过A的路由通知给B，不将通过B的路由通知给A，那么该ISP在A和B看来就是透明的。
  7. 错误。有时为了特殊需求，BGP路由器可以选择不将自己的表示添加到已经接受的路径之中，此时该BGP将不会作为中转路由器工作。

5.6

  1. ICMP报文有：ping报文（回显报文）、traceroute（目标端口不可达报文、TTL过期报文）、用于拥塞控制的源抑制报文。
  2. TTL过期报文和目标端口不可达报文。解释：Traceroute用ICMP报文实现，源主机的数据报中携带了一个具有不可达UDP端口号的UDP报文段，第1个数据报的TTL为1，第2个为2，等等。当TTL为0时，接收到该数据报的路由器应该向源主机发送一个ICMP警告报文给源主机。如果有数据报到达了目的主机，那么该目的主机将向源发送一个端口不可达的ICMP报文，以标志路由探测完毕。

习题

  1. y→x→u，y→w→x→u，y→w→v→u，y→w→v→x→u，y→z→w→v→x→u，y→z→w→v→u，y→z→w→x→u等。
  2. 略
节点 x y v w t u
z 8.z 12.z
zx 8.z 12.z 11.x 14.x
zxv 8.z 12.z 11.x 14.x 15.v 14.v
zxvyw 8.z 12.z 11.x 14.x 15.v 14.v
zxvywu 8.z 12.z 11.x 14.x 15.v 14.v
zxvywut 8.z 12.z 11.x 14.x 15.v 14.v
  1. 略
  2. DV算法流程：

z表

x y z u v
x ∞ ∞ ∞ ∞ ∞
z 2 ∞ 0 ∞ 6
v ∞ ∞ ∞ ∞ ∞
x y z u v
x 0 3 2 ∞ 3
z 2 5 0 7 5
v 3 ∞ 6 1 0
x y z u v
x 0 3 2 4 3
z 2 5 0 7 5
v 3 3 6 1 0
x y z u v
x 0 3 2 4 3
z 2 5 0 7 5
v 3 3 6 1 0
  1. 最大迭代次数为这个网络中最长无环路径的长度，迭代到这个值时网络中所有的路径都能够被遍历到。
  2. a. Dx(w)=2，Dx(y)=4，Dx(u)=7。
    b. 若让x通知邻居有一条通往u的新的最低开销路径，则可以将c(x,w)的值增大，只要让c(x,w)+c(w,u)>=c(x,y)+c(y,u)，即c(x,w)>6即可。或者让c(x,y)的值变为1。
    c. 只能让c(x,w)的值增加到7或以上才可以。

初始向量表：
x：

x y z
x 0 3 4
y ∞ ∞ ∞
z ∞ ∞ ∞

y：

x y z
x ∞ ∞ ∞
y 3 0 6
z ∞ ∞ ∞

z：

x y z
x ∞ ∞ ∞
y ∞ ∞ ∞
z 4 6 0

第一次迭代后：
x：

x y z
x 0 3 4
y 3 0 6
z 4 6 0

y：

x y z
x 0 3 4
y 3 0 6
z 4 6 0

z：

x y z
x 0 3 4
y 3 0 6
z 4 6 0
  1. 不会。将没有链路的两个节点连接，相当于距离从无穷大降到了有限值。
  2. 每一次更新，至少有一个距离向量的某维度的值减小。(假如没有任何距离向量发生改变，更新就停止。)
    由于这些值都是整数、不可能增加、也不可能小于0、所以减小的次数必然是有限的，所以更新也必然是有限的。
  3. a. 考虑增加了毒性逆转。y将通知w和z其到x的最短距离为4。z将通知w，其到x的距离为无穷大，因为z此时到x的最短路径是通过w的。另外z通知y其到x的距离为6（因为z只保存了其下一跳，因此并不知道它到x最短路径经过y，因此不发送无穷大）。w通知z其到x的距离为5，通知y其到x的距离为无穷大。
    b. 不能。问题出在z上，因为z和x的最短路径经过了y，z却告知y的Dz(x)=6（这是毒性逆转作用不到的地方），y就会把Dy(x)更新成9（实际上并不是）,然后陷入了无穷计数。
    c. 设置为无穷大即可。
  4. BGP是ISP之间的路由选择，如果在寻路时发现了自己所在ISP的路由器，则说明产生了环路。
  5. 不是。路由器将偏向于本地偏好值。
  6. a. 路由器3c从eBGP中学习到了前缀x，因为其与AS4直接相连。
    b. 路由器3a从iBGP学习到前缀x，其需要通过iBGP与3c通信。
    c. 路由器1c从eBGP学习到前缀x。
    d. 路由器1d从iBGP学习到。
  7. a. I1，距离1c更近。
    b. I2，根据热土豆路由选择算法其距离2a更近。
    c. I1，这样AS-PATH更短。
  8. 考虑到B将流量传给C的西海岸路由器，因此为了减少西海岸路由器的负担，C可以只告诉D它的东海岸路由器。
  9. 因为B不希望C通过它自身转发分组，因此B和C的这条链路对于w是不可见的。同理x为了不想通过自身转发C和B之间的分组，不会告诉B自己与C连接，因此C和w的这条链路对于w也不可见。同理，为了不让x经过自己转发到w的流量，C到A的链路对于x不可见，且C到B的链路对于x不可见。
  10. BitTorrent
  11. A会向B通告其有到w的路由，不会向c通告，A会向B和C通告有到v的路由。
  12. 不允许。
  13. 略
  14. 略