P1

y-x-u
y-x-v-u
y-x-w-u
y-x-w-v-u
y-w-u
y-w-v-u
y-w-x-u
y-w-v-x-u
y-w-x-v-u
y-z-w-u
y-z-w-v-u
y-z-w-x-u
y-z-w-v-x-u
y-z-w-x-v-u

P2

x to z:
x-y-z
x-y-w-z
x-w-z
x-w-y-z
x-v-w-z
x-v-w-y-z
x-u-w-z
x-u-w-y-z
x-u-v-w-z
x-u-v-w-y-z

z to u:
z-w-u
z-w-v-u
z-w-x-u
z-w-v-x-u
z-w-x-v-u
z-w-y-x-u
z-w-y-x-v-u
z-y-x-u
z-y-x-v-u
z-y-x-w-u
z-y-x-w-y-u
z-y-x-v-w-u
z-y-w-v-u
z-y-w-x-u
z-y-w-v-x-u
z-y-w-x-v-u

z to w:
z-w
z-y-w
z-y-x-w
z-y-x-v-w
z-y-x-u-w
z-y-x-u-v-w
z-y-x-v-u-w

P3

步骤	$N^{\prime }$	$D(t),p(t)$	$D(u),p(u)$	$D(v),p(v)$	$D(w),p(w)$	$D(y),p(y)$	$D(z),p(z)$
0	$x$	114514	114514	$3,x$	$6,x$	$6,x$	$8,x$
1	$xv$	$7,v$	$6,v$	-	$6,x$	$6,x$	$8,x$
2	$xvu$	$7,v$	-	-	$6,x$	$6,x$	$8,x$
3	$xvuw$	$7,v$	-	-	-	$6,x$	$8,x$
4	$xvuwy$	$7,v$	-	-	-	-	$8,x$
5	$xvuwyt$	-	-	-	-	-	$8,x$
6	$xvuwytz$	-	-	-	-	-	-

P4

a)

步骤	$N^{\prime }$	$D(u),p(u)$	$D(v),p(v)$	$D(w),p(w)$	$D(x),p(x)$	$D(y),p(y)$	$D(z),p(z)$
0	$t$	$2,t$	$4,t$	$114514$	$114514$	$7,t$	$114514$
1	$tu$	-	$4,t$	$5,u$	$114514$	$7,t$	$114514$
2	$tuv$	-	-	$5,u$	$7,v$	$7,t$	$114514$
3	$tuvw$	-	-	-	$7,v$	$7,t$	$114514$
4	$tuvwx$	-	-	-	-	$7,t$	$15,x$
5	$tuvwxy$	-	-	-	-	-	$15,x$
6	$tuvwxyz$	-	-	-	-	-	-

b)

步骤	$N^{\prime }$	$D(t),p(t)$	$D(v),p(v)$	$D(w),p(w)$	$D(x),p(x)$	$D(y),p(y)$	$D(z),p(z)$
0	$u$	$2,u$	$3,u$	$3,u$	$114514$	$114514$	$114514$
1	$ut$	-	$3,u$	$3,u$	$114514$	$9,t$	$114514$
2	$utv$	-	-	$3,u$	$6,v$	$9,t$	$114514$
3	$utvw$	-	-	-	$6,v$	$9,t$	$114514$
4	$utvwx$	-	-	-	-	$9,t$	$14,x$
5	$utvwxy$	-	-	-	-	-	$14,x$
6	$utvwxyz$	-	-	-	-	-	-

c)

步骤	$N^{\prime }$	$D(t),p(t)$	$D(u),p(u)$	$D(w),p(w)$	$D(x),p(x)$	$D(y),p(y)$	$D(z),p(z)$
0	$v$	$4,v$	$3,v$	$4,v$	$3,v$	$8,v$	$114514$
1	$vu$	$4,v$	-	$4,v$	$3,v$	$8,v$	$114514$
2	$vux$	$4,v$	-	$4,v$	-	$8,v$	$11,x$
3	$vuxt$	-	-	$4,v$	-	$8,v$	$11,x$
4	$vuxtw$	-	-	-	-	$8,v$	$11,x$
5	$vuxtwy$	-	-	-	-	-	$11,x$
6	$vuxtwyz$	-	-	-	-	-	-

d)

步骤	$N^{\prime }$	$D(t),p(t)$	$D(u),p(u)$	$D(v),p(v)$	$D(x),p(x)$	$D(y),p(y)$	$D(z),p(z)$
0	$w$	$114514$	$3,w$	$4,w$	$6,w$	$114514$	$114514$
1	$wu$	$5,u$	-	$4,w$	$6,w$	$114514$	$114514$
2	$wuv$	$5,u$	-	-	$6,w$	$12,v$	$114514$
3	$wuvt$	-	-	-	$6,w$	$12,v$	$114514$
4	$wuvtx$	-	-	-	-	$12,v$	$14,x$
5	$wuvtxy$	-	-	-	-	-	$14,x$
6	$wuvtxyz$	-	-	-	-	-	-

e)

步骤	$N^{\prime }$	$D(t),p(t)$	$D(u),p(u)$	$D(v),p(v)$	$D(w),p(w)$	$D(x),p(x)$	$D(z),p(z)$
0	$y$	$7,y$	$114514$	$8,y$	$114514$	$6,y$	$12,y$
1	$yx$	$7,y$	$114514$	$8,y$	$12,x$	-	$12,y$
2	$yxt$	-	$9,t$	$8,y$	$12,x$	-	$12,y$
3	$yxtv$	-	$9,t$	-	$12,x$	-	$12,y$
4	$yxtvu$	-	-	-	$12,x$	-	$12,y$
5	$yxtvuw$	-	-	-	-	-	$12,y$
6	$yxtvuwz$	-	-	-	-	-	-

f)

步骤	$N^{\prime }$	$D(t),p(t)$	$D(u),p(u)$	$D(v),p(v)$	$D(w),p(w)$	$D(x),p(x)$	$D(y),p(y)$
0	$z$	$114514$	$114514$	$114514$	$114514$	$8,z$	$12,z$
1	$zx$	$114514$	$114514$	$11,x$	$14,x$	-	$12,z$
2	$zxv$	$15,v$	$14,v$	-	$14,x$	-	$12,z$
3	$zxvy$	$15,v$	$14,v$	-	$14,x$	-	-
4	$zxvyu$	$15,v$	-	-	$14,x$	-	-
5	$zxvyuw$	$15,v$	-	-	-	-	-
6	$zxvyuwt$	-	-	-	-	-	-

P5

从\到	u	v	x	y	z
x	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
v	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
z	$\infty$	6	2	$\infty$	0

从\到	u	v	x	y	z
x	$\infty$	3	0	3	2
v	1	0	3	$\infty$	6
z	7	5	2	5	0

从\到	u	v	x	y	z
x	4	3	0	3	2
v	1	0	3	3	5
z	6	5	2	5	0

从\到	u	v	x	y	z
x	4	3	0	3	2
v	1	0	3	3	5
z	6	5	2	5	0

P6

首先我们需要知道图中两节点之间的最长（指hop数最多）无环路径，假如是d个hop，那么最大迭代次数就是d。

P7

a) $D_x(w)=2,D_x(y)=4,D_x(u)=7$
b) 对于c(x,w)，c(x,w)>6
对于c(x,y),c(x,y)=1
c) c(x,y)变为任意值，都不能改变最低开销路径

P8

x’s tables

from\to	x	y	z
x	0	3	4
y	$\infty$	$\infty$	$\infty$
z	$\infty$	$\infty$	$\infty$

from\to	x	y	z
x	0	3	4
y	3	0	6
z	4	6	0

y’s tables

from\to	x	y	z
x	$\infty$	$\infty$	$\infty$
y	3	0	6
z	$\infty$	$\infty$	$\infty$

from\to	x	y	z
x	0	3	4
y	3	0	6
z	4	6	0

z’s tables

from\to	x	y	z
x	$\infty$	$\infty$	$\infty$
y	$\infty$	$\infty$	$\infty$
z	4	6	0

from\to	x	y	z
x	0	3	4
y	3	0	6
z	4	6	0

P9

不会；将没有链路的节点连接起来，相当于将开销从无穷降到了有限值，也不会出现无穷计数问题。

P10

拒绝讨论

P11

a) 中文版完全把意思翻译错了。。。按照英文版来
w inform y,$D_w(x)=\infty$;
w inform z,$D_w(x)=5$;
y inform w,$D_y(x)=4$;
y inform z,$D_y(x)=4$;
z inform w,$D_z(x)=\infty$;
z inform y,$D_z(x)=6$;
b) 会存在无穷计数问题，注意，这里涉及三个节点，毒性逆转无法解决。需要31次迭代。
c) let c(y,z)=$\infty$

P12

🐎

P13

否，BGP将优先考虑本地偏好值。

P14

a) eBGP
b) iBGP
c) eBGP
d) iBGP

P15

a) $I_1$ 因为这样距离1c最近。
b) $I_2$ 根据热土豆路由选择，这样距离next hop 2a最近。
c) $I_1$ 这样AS-PATH最短。

P16

只告诉D自己临近东海岸的路由器，不告诉它自己临近西海岸的路由器。

P17

x

w

P18

BitTorrent

P19

A向B通报A-W,A-V两条路径
A向C通报A-V一条路径
C收到的AS路由：B-A-W,B-A-V,A-V

P20

不允许（无慈悲

P21

开销：陷阱方式节省开销
异常及时通知：陷阱方式响应更快
健壮性：请求-响应方式更健壮

P22

TCP的拥塞管理可能会导致SMTP报文不能及时交付。