Skip to content

作业四

211275022田昊东

R4

Link State Distance Vector
类型 完整性、全局性 迭代式、分布式、异步
节点信息 每个节点都有整个网络拓扑的全部信息 每个节点只有直接相邻的点的信息,以及从邻居发送的dv中的信息
消息复杂度 O(ne) 取决于迭代次数
时间 O(n2) 较慢
鲁棒性 节点故障可能会导致错误的直接链路成本广播，但错误范围受到限制。 错误节点可能会交换错误的路径成本，错误可能会通过网络传播。

R6

  • 没有必要：
  • 因特网在设计时考虑到了AS内部管理自治的问题
  • 不同AS只要保证使用相同的EGP算法即可，而对于其内部路由选择算法IGP不同AS可以选择不同的算法，也可以进行调整

R10

  • 子网：
  • 指在同一个物理网络上的一组主机的集合，它们使用相同的IP地址前缀。即具有相同的网络号，而主机号不同的设备的集合。
  • 前缀：
  • 用于表示一个IP地址段，通常用于路由协议中，以描述路由表中一个网络的地址范围。
  • BGP路由：
  • 是EGP协议中的一种，用于实现AS之间的路由选择，把不同AS连接起来，实现在不同自治系统之间传递路由信息。

P3

No T L(y) Path L(z) Path L(v) Path L(w) Path L(u) Path L(t) Path
1 {x} 6 x-y 8 x-z 3 x-v 6 x-w \ \ \ \
2 {x,v} 6 x-y 8 x-z 3 x-v 6 x-w 6 x-v-u 7 x-v-t
3 {x,y,v} 6 x-y 8 x-z 6 x-w 6 x-v-u 7 x-v-t
4 {x,y,v,w} 8 x-z 6 x-w 6 x-v-u 7 x-v-t
5 {x,y,v,w,u} 8 x-z 6 x-v-u 7 x-v-t
6 {x,y,v,w,u,t} 8 x-z 7 x-v-t
7 {x,y,v,w,u,t,z} 6 x-y 8 x-z 3 x-v 6 x-w 6 x-v-u 7 x-v-t

P5

h Lh(v) Path Lh(x) Path Lh(u) Path Lh(y) Path
1 6 z-v 2 z-x \ \ \ \
2 5 z-x-v 7 z-v-u 5 z-x-y
3 5 z-x-v 2 z-x 6 z-x-v-u 5 z-x-y

  • h=1

  • z v x u y
    z 0 6 2 \ \
    v \ \ \ \ \
    x \ \ \ \ \

  • h=2

  • z v x u y
    z 0 5 2 7 5
    v 6 0 3 1 \
    x 2 3 0 \ 3

  • h=3

  • z v x u y
    z 0 5 2 6 5
    v 5 0 3 1 3
    x 2 3 0 4 3
Destination Next-Hop Distance
v x 5
x x 2
u x 6
y x 5

P7

  • a.

  • 距离 路径
    w 2 x-w
    y 4 x-w-y
    u 7 x-w-u

  • b.

  • 也就使得从x到u的最短路径不再是x-w-u

  • c(x,w)+5>5+6
  • c(x,y)+6<2+5

  • 即：

    • c(x,w)>6
    • c(x,y)<1

  • c.

  • 也就是保持从x到u的最短路径是x-w-u

  • 即：
    • c(x,w)<=6
    • c(x,y)>=1

P11

image-20230414211705192

  • a.
  • w：
    • 最短路径：5;w-y-x
    • 告诉y:inf（毒性逆转）
    • 告诉z:5
  • y：
    • 最短路径：4;y-x
    • 告诉w:4
    • 告诉z:4
  • z：
    • 最短路径：6;z-w-y-x
    • 告诉w:inf（毒性逆转）
    • 告诉y:6
  • b.
  • 当c(x,y)变成60时，y-x的最短距离发生了变化
    • Dy(x)=min(60,Dy(z)+Dz(x),Dy(w)+Dw(x))=9
  • y会进行广告，关于Dy(x)路径变为y-z...且长度为9，告诉z为inf，告诉w为9
    • Dw(x)=min(Dw(z)+Dz(x),Dw(y)+Dy(x))=10
  • w会进行广告，关于Dw(x)变为10，告诉y为inf，告诉z为9
    • Dz(x)=min(50,Dz(y)+Dy(x),Dz(w)+Dw(x))=11
  • z会进行广告，关于Dw(x)变为10，告诉y为1，告诉w为inf
    • Dy(x)=min(60,Dy(z)+Dz(x),Dy(w)+Dw(x))=14
  • 按照逆时针的顺序如此重复执行,每经过三次迭代到x的距离会增加4（1+1+3）
    • 14+5*7=49，经过4+3*7=25
    • 27：Dz(x)=50，选择路径z-x不经过其他节点
    • 28：Dy(x)=min(60,Dy(z)+Dz(x),Dy(w)+Dw(x))=53
    • 29：Dw(x)=min(Dw(z)+Dz(x),Dw(y)+Dy(x))=51
    • 30：Dy(x)=min(60,Dy(z)+Dz(x),Dy(w)+Dw(x))=52
    • 31：不再发生变化，算法终止
  • 因此存在无穷计数问题，因为yzw连成了一个环，而毒性逆转只会告诉在路径中直接相连的路径inf，因此在三个节点的情况下节点会轮流受到信息，错误的更新到x的最短路径；需要经过31次迭代才能到达稳定状态。
  • c.
  • 令c(y,z)较大，迫使y选择y-x的路径而不是错误的通过z
  • 6+c(y,z)>=50即c(y,z)>=44即可

P12

  • 是通过检查路由广告的aspath属性来实现的
  • 如果一个路由器在路径列表中看到了自己所在的AS，那么就说明路径中存在环路，应该丢弃

P14

  • a.
  • eBGP
  • b.
  • iBGP
  • c.
  • eBGP
  • d.
  • iBGP