计算机网络:自顶向下方法-第8版-Chapter5-Problems

文章目录

P1
P2
P3
P4
P5
P6
P7
- a
- b
- c
P8
P9
P10
P11
- a
- b
- c
P12
P13
P14
- a
- b
- c
- d
P15
- a
- b
- c
P16
P17
P18
P19
P20
P21
P22

P1

观察图5-3，列举从y到u不包含任何环路的路径。

随便写个搜索路径算法

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
const int INF = 0x3f3f3f3f;
std::vector<int> edges[N];
bool vis[N];
int fa[N];
void printPath(int u) {
    if (fa[u] == 0) {
        printf("%c", u);
        return;
    } 
    printPath(fa[u]);
    printf(" -> ");
    printf("%c", u);
}
int path;
void dfs(int u, int dest) {
    if (u == dest) {
        printf("path %d: ", ++path);
        printPath(dest);
        printf("\n");
        return;
    }
    for (auto v : edges[u]) {
        if (!vis[v]) {
            vis[v] = true;
            fa[v] = u;
            dfs(v, dest);
            vis[v] = false;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    edges['x'].push_back('u');
    edges['x'].push_back('v');
    edges['x'].push_back('w');
    edges['x'].push_back('y');


    edges['u'].push_back('v');
    edges['u'].push_back('x');
    edges['u'].push_back('w');

    edges['v'].push_back('u');
    edges['v'].push_back('x');
    edges['v'].push_back('w');


    edges['w'].push_back('u');
    edges['w'].push_back('x');
    edges['w'].push_back('v');
    edges['w'].push_back('z');
    edges['w'].push_back('y');
    
    edges['z'].push_back('w');
    edges['z'].push_back('y');


    edges['y'].push_back('x');
    edges['y'].push_back('w');
    edges['y'].push_back('z');
    vis['y'] = true;
    dfs('y', 'u');
    return 0;
}

输入起点和终点, 计算得一共15条简单路径

path 1: y -> x -> u
path 2: y -> x -> v -> u
path 3: y -> x -> v -> w -> u
path 4: y -> x -> w -> u
path 5: y -> x -> w -> v -> u
path 6: y -> w -> u
path 7: y -> w -> x -> u
path 8: y -> w -> x -> v -> u
path 9: y -> w -> v -> u
path 10: y -> w -> v -> x -> u
path 11: y -> z -> w -> u
path 12: y -> z -> w -> x -> u
path 13: y -> z -> w -> x -> v -> u
path 14: y -> z -> w -> v -> u
path 15: y -> z -> w -> v -> x -> u

P2

重复习题P1，列举从 x 到 z, z 到 u 以及 z 到 w 的不包含任何环路的路径。

x到z

path 1: x -> u -> v -> w -> z
path 2: x -> u -> v -> w -> y -> z
path 3: x -> u -> w -> z
path 4: x -> u -> w -> y -> z
path 5: x -> v -> u -> w -> z
path 6: x -> v -> u -> w -> y -> z
path 7: x -> v -> w -> z
path 8: x -> v -> w -> y -> z
path 9: x -> w -> z
path 10: x -> w -> y -> z
path 11: x -> y -> w -> z
path 12: x -> y -> z

z到u

path 1: z -> w -> u
path 2: z -> w -> x -> u
path 3: z -> w -> x -> v -> u
path 4: z -> w -> v -> u
path 5: z -> w -> v -> x -> u
path 6: z -> w -> y -> x -> u
path 7: z -> w -> y -> x -> v -> u
path 8: z -> y -> x -> u
path 9: z -> y -> x -> v -> u
path 10: z -> y -> x -> v -> w -> u
path 11: z -> y -> x -> w -> u
path 12: z -> y -> x -> w -> v -> u
path 13: z -> y -> w -> u
path 14: z -> y -> w -> x -> u
path 15: z -> y -> w -> x -> v -> u
path 16: z -> y -> w -> v -> u
path 17: z -> y -> w -> v -> x -> u

z到w

path 1: z -> w
path 2: z -> y -> x -> u -> v -> w
path 3: z -> y -> x -> u -> w
path 4: z -> y -> x -> v -> u -> w
path 5: z -> y -> x -> v -> w
path 6: z -> y -> x -> w
path 7: z -> y -> w

P3

考虑下面的网络。对于标明的链路开销，用 Dijkstra 的最短路算法计算出从x到所有网络节点的最短路径。通过计算一个类似于表5-1的表，说明该算法是如何工作的。

表5-1

模拟Dijkstra即可, 每次从未确定最短路的点集中取出离x最近的点, 然后利用该点更新起点到该店的未确定的邻居点的距离

step	N’(最短路以确定的点集)	D(z), p(z)	D(y), p(y)	D(v), p(v)	D(w), p(w)	D(u), p(u)	D(t), p(t)
0	x	8, x	6, x	3, x ✔	6, x	∞	∞
1	x, v	8, x	6, x ✔		6, x	6, v	7, v
2	x, v, y	8, x			6, x ✔	6, v	7, v
3	x, v, y w	8, x				6, v ✔	7, v
4	x, v, y, w, u	8, x					7, v ✔
5	x, v, y w, u, t	8, x✔
6	x, v, y w, u, t, z

P4

考虑习题P3中所示的网络。使用Dijkstra算法和一个类似于表5-1的表来说明你做的工作:
a. 计算出从t到所有网络节点的最短路径。
b. 计算出从u到所有网络节点的最短路径。
c. 计算出从v到所有网络节点的最短路径。
d. 计算出从w到所有网络节点的最短路径。
e. 计算出从y到所有网络节点的最短路径。
f. 计算出从z到所有网络节点的最短路径。

太麻烦了, 直接用代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
const int INF = 0x3f3f3f3f;
bool distOver[N];
int n, m, k, dist[N], fa[N];
typedef pair<int, int> PII;
vector<PII> edges[N];
int arr[10] = {0, 'x', 'y', 'z', 'u', 'v', 'w', 't'};
void printDist(int u) {
    char ans[20] = "1234567";
    int len = 0;
    for (int i = 1; i <= 7; i++) {
        int v = arr[i]; 
        if (distOver[v]) {
            ans[len++] = v;
        } 
    }
    printf("distOver=[");
    for (int i = 0; i < 7; i++) {
        if (ans[i] > '9') {
            printf("%c", ans[i]);
        }
    }
    printf("] ");
    for (int i = len; i < 7; i++) {
        printf(" ");
    }
    for (int i = 1; i <= 7; i++) {
        int v = arr[i];
        if (true) {
            if (dist[v] < INF) {
                if (fa[v] == 0) {
                    printf("%d, %c| ", dist[v], v);
                } else {
                    printf("%d, %c| ", dist[v], fa[v]);
                }
            } else {
                printf("INF | ");
            }
        }
    }

    printf("\n");
}
void djikstra(int s) {
    for (int i = 1; i <= 19; i++) {
        printf(" ", arr[i]);
    }
    printf("\n");
    for (int i = 1; i <= 7; i++) {
        printf(" %c  | ", arr[i]);
    }
    printf("\n");
    memset(dist, 0x3f, sizeof(dist));
    memset(distOver, false, sizeof(distOver));
    priority_queue<PII, vector<PII>, greater<PII>> q;
    dist[s] = 0;
    q.push(make_pair(dist[s], s));
    while(!q.empty()) {
        int u = q.top().second; q.pop();
        if(distOver[u]) continue;
        distOver[u] = true;
        printDist(s);
        // 利用结点x更新
        for(auto y : edges[u]) {
            int v = y.first, w = y.second;
            if(dist[u] + w < dist[v]) {
                fa[v] = u;
                dist[v] = dist[u] + w;
                q.push(make_pair(dist[v], v));
            }
        }
    }
} 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    edges['x'].push_back({'z', 8});
    edges['x'].push_back({'y', 6});
    edges['x'].push_back({'v', 3});
    edges['x'].push_back({'w', 6});

    edges['z'].push_back({'x', 8});
    edges['z'].push_back({'y', 12});

    edges['y'].push_back({'z', 12});
    edges['y'].push_back({'x', 6});
    edges['y'].push_back({'v', 8});
    edges['y'].push_back({'t', 7});

    edges['v'].push_back({'y', 8});
    edges['v'].push_back({'x', 3});
    edges['v'].push_back({'w', 4});
    edges['v'].push_back({'u', 3});
    edges['v'].push_back({'t', 4});

    edges['t'].push_back({'y', 7});
    edges['t'].push_back({'v', 4});
    edges['t'].push_back({'u', 2});

    edges['u'].push_back({'t', 2});
    edges['u'].push_back({'v', 3});
    edges['u'].push_back({'w', 3});

    edges['w'].push_back({'u', 3});
    edges['w'].push_back({'v', 4});
    edges['w'].push_back({'x', 6});
    djikstra('t');
    return 0;
}

t为源点

                    x  |  y  |  z  |  u  |  v  |  w  |  t  | 
distOver=[t]       INF | INF | INF | INF | INF | INF | 0, t| 
distOver=[ut]      INF | 7, t| INF | 2, t| 4, t| INF | 0, t| 
distOver=[uvt]     INF | 7, t| INF | 2, t| 4, t| 5, u| 0, t| 
distOver=[uvwt]    7, v| 7, t| INF | 2, t| 4, t| 5, u| 0, t| 
distOver=[xuvwt]   7, v| 7, t| INF | 2, t| 4, t| 5, u| 0, t| 
distOver=[xyuvwt]  7, v| 7, t| 15, x| 2, t| 4, t| 5, u| 0, t| 
distOver=[xyzuvwt] 7, v| 7, t| 15, x| 2, t| 4, t| 5, u| 0, t|

u为源点

                    x  |  y  |  z  |  u  |  v  |  w  |  t  | 
distOver=[u]       INF | INF | INF | 0, u| INF | INF | INF | 
distOver=[ut]      INF | INF | INF | 0, u| 3, u| 3, u| 2, u| 
distOver=[uvt]     INF | 9, t| INF | 0, u| 3, u| 3, u| 2, u| 
distOver=[uvwt]    6, v| 9, t| INF | 0, u| 3, u| 3, u| 2, u| 
distOver=[xuvwt]   6, v| 9, t| INF | 0, u| 3, u| 3, u| 2, u| 
distOver=[xyuvwt]  6, v| 9, t| 14, x| 0, u| 3, u| 3, u| 2, u| 
distOver=[xyzuvwt] 6, v| 9, t| 14, x| 0, u| 3, u| 3, u| 2, u|

v为源点

                    x  |  y  |  z  |  u  |  v  |  w  |  t  | 
distOver=[v]       INF | INF | INF | INF | 0, v| INF | INF | 
distOver=[uv]      3, v| 8, v| INF | 3, v| 0, v| 4, v| 4, v| 
distOver=[xuv]     3, v| 8, v| INF | 3, v| 0, v| 4, v| 4, v| 
distOver=[xuvt]    3, v| 8, v| 11, x| 3, v| 0, v| 4, v| 4, v| 
distOver=[xuvwt]   3, v| 8, v| 11, x| 3, v| 0, v| 4, v| 4, v| 
distOver=[xyuvwt]  3, v| 8, v| 11, x| 3, v| 0, v| 4, v| 4, v| 
distOver=[xyzuvwt] 3, v| 8, v| 11, x| 3, v| 0, v| 4, v| 4, v|

w为源点

                    x  |  y  |  z  |  u  |  v  |  w  |  t  | 
distOver=[w]       INF | INF | INF | INF | INF | 0, w| INF | 
distOver=[uw]      6, w| INF | INF | 3, w| 4, w| 0, w| INF | 
distOver=[uvw]     6, w| INF | INF | 3, w| 4, w| 0, w| 5, u| 
distOver=[uvwt]    6, w| 12, v| INF | 3, w| 4, w| 0, w| 5, u| 
distOver=[xuvwt]   6, w| 12, v| INF | 3, w| 4, w| 0, w| 5, u| 
distOver=[xyuvwt]  6, w| 12, v| 14, x| 3, w| 4, w| 0, w| 5, u| 
distOver=[xyzuvwt] 6, w| 12, v| 14, x| 3, w| 4, w| 0, w| 5, u|

y为源点

                    x  |  y  |  z  |  u  |  v  |  w  |  t  | 
distOver=[y]       INF | 0, y| INF | INF | INF | INF | INF | 
distOver=[xy]      6, y| 0, y| 12, y| INF | 8, y| INF | 7, y| 
distOver=[xyt]     6, y| 0, y| 12, y| INF | 8, y| 12, x| 7, y| 
distOver=[xyvt]    6, y| 0, y| 12, y| 9, t| 8, y| 12, x| 7, y| 
distOver=[xyuvt]   6, y| 0, y| 12, y| 9, t| 8, y| 12, x| 7, y| 
distOver=[xyuvwt]  6, y| 0, y| 12, y| 9, t| 8, y| 12, x| 7, y| 
distOver=[xyzuvwt] 6, y| 0, y| 12, y| 9, t| 8, y| 12, x| 7, y|

z为源点

                    x  |  y  |  z  |  u  |  v  |  w  |  t  | 
distOver=[z]       INF | INF | 0, z| INF | INF | INF | INF | 
distOver=[xz]      8, z| 12, z| 0, z| INF | INF | INF | INF | 
distOver=[xzv]     8, z| 12, z| 0, z| INF | 11, x| 14, x| INF | 
distOver=[xyzv]    8, z| 12, z| 0, z| 14, v| 11, x| 14, x| 15, v| 
distOver=[xyzuv]   8, z| 12, z| 0, z| 14, v| 11, x| 14, x| 15, v| 
distOver=[xyzuvw]  8, z| 12, z| 0, z| 14, v| 11, x| 14, x| 15, v| 
distOver=[xyzuvwt] 8, z| 12, z| 0, z| 14, v| 11, x| 14, x| 15, v|

P5

考虑下图所示的网络，假设每个节点初始时知道到它的每个邻居的开销。考虑距离向量算法，请给出节点z处的距离表表项。

因为只考虑z的距离表, 所以同时考虑v, x的距离表

t0时刻, z只有到x, v的信息

from	to u	to v	to x	to y	to z
v	INF	INF	INF	INF	INF
x	INF	INF	INF	INF	INF
z	INF	6	2	INF	0

t1时刻, v, x的距离表与z的交换, 即更新了下表的1, 2行

然后z根据新的路由向量更新自己的路由表

以下即根据更新后的v, x距离向量表更新z的距离向量表

z到u的距离可以由v的向量更新

d[z][u] = min{d[z][u], d[z][v] + d[v][u]} = min{INF, 6 + 1} = 7

z到v的距离可以由x的向量更新

d[z][v] = min{d[z][u], d[z][x] + d[x][v]} = min{6, 2 + 3} = 5

z到y的距离可以由x的向量更新

d[z][y] = min{d[z][y], d[z][x] + d[x][y]} = min{INF, 2 + 3} = 5

from	to u	to v	to x	to y	to z
v	1	0	3	INF	6
x	INF	3	0	3	2
z	7	5	2	5	0

t2时刻, 当v, x的距离向量因为和它们的相邻结点发送交换后

v到y的距离通过u的向量得到更新为3, 到z的距离通过x的向量更新为5

x到u的距离通过v的向量更新为4

以下根据更新后的v, x距离向量表更新z的距离向量表

z通过x或v都可以更新到u的最小距离为6

d[z][u] = min{d[z][u], d[z][x] + d[x][u], d[z][v] + d[v][u]} = min{7, 6, 6} = 6

from	to u	to v	to x	to y	to z
v	1	0	3	3	5
x	4	3	0	3	2
z	7 -> 6	5	2	5	0

此后再无距离向量的更新

P6

考虑一个一般性拓扑（即不是以上所显示的特定网络）和一个同步版本的距离向量算法。假设每次迭代时，一个节点与其邻居交换其距离向量并接收它们的距离向量。假定算法开始时，每个节点只知道到其直接邻居的开销，在该分布式算法收敛前所需的最大迭代次数是多少?评估你的答案。

这个问题的措辞有点含糊。我们的意思是，“算法第一次运行时的迭代次数”（也就是说，假设节点最初拥有的唯一信息是其最近邻居的成本）。我们假设该算法同步运行（即，在一个步骤中，所有节点同时计算其距离表，然后交换表）。在每次迭代中，节点与其邻居交换距离表。因此，如果您是节点 A，而您的邻居是 B，则 B 的所有邻居（都距您一跳或两跳）将在一次迭代后知道到您的一跳或两跳的最短成本路径（即，在 B 告诉他们你的成本）。

设 d 为网络的"直径"——网络中任意两个节点之间没有环路的最长路径的长度。使用上述推理，在 d-1 次迭代之后，所有节点将知道到所有其他节点的 d 或更少跳数的最短路径成本。由于任何具有大于 d 跳的路径都会有环路（因此比删除环路的路径具有更大的成本），因此该算法将在最多 d-1 次迭代中收敛。

旁白：如果 DV 算法是由于链路成本变化而运行的，则收敛之前所需的迭代次数没有先验限制，除非还指定了链路成本的限制。

这里的直径大小可能是根据点数算的, 所以距离最远的两个点之间有d-1条边, 所以它们拥有彼此的距离向量会在d-1轮接待以后, 当一个点拥有了里它最远的点的距离向量, 则肯定也拥有了其它所有点的距离向量

P7

考虑下图所示的网络段。x只有两个相连邻居w与y。w有一条通向目的地u(没有显示）的最低开销路径，其值为5, y有一条通向目的地u的最低开销路径，其值为6。从u与y到u(以及w与y之间）的完整路径未显示出来。网络中所有链路开销皆为正整数值。

a. 给出x对目的地w、y和u的距离向量。

b. 给出对于c(x，w)或c(x，y)的链路开销的变化，使得执行了距离向量算法后，x 将通知其邻居有一条通向u的新最低开销路径。

c. 给出对c(x,w)或c(x,y)的链路开销的变化，使得执行了距离向量算法后, x 将不通知其邻居有一条通向x的新最低开销路径。

a

x可以通过w到y, 距离为4

x可以通过w到u, 距离为7

d[x][w] = 2
d[x][y] = 4
d[x][u] = 7

b

首先考虑如果 c(x,y) 改变会发生什么。

d[x][u] = min{d[x][u], c[x][y] + 6} = min{7, c[x][y] + 6}

如果 c(x,y) 变得更大或更小（只要 c(x,y) >=1），从 x 到 u 的最小成本路径的成本仍然至少为 7。因此 c(x, y)不会导致 x 通知其邻居任何变化。

如果 $\delta<1$ ，则最小成本路径现在经过 y 并且具有成本 $\delta+6$ (6为y到u的成本)。

考虑 c(x,w) 是否变化。

d[x][u] = min{c[x][w] + 5, c[x][y] + 6} = min{c[x][w] + 5, 11}

如果 $\epsilon \le 6$ ，则到 u 的最小成本路径继续通过w，其成本变为 $5+\epsilon$ , x 将通知它的邻居这个新的成本。

如果 $\delta > 6$ ，则最小成本路径现在经过 y 并且成本为 11; x 将再次通知其邻居这个新成本。

c

只要c(x, y)变化后仍大于等于1, 则x不会通知其邻居到u的新的最小成本路径

无论c(x, w)怎么变, 都会通知其邻居新的最小成本路径发送变化

P8

考虑如图5-6中所示3个节点的拓扑。

不使用显示在图5-6中的开销值，链路开销值现在是c(x, y)=3, c(y, z)=6，c(z, x)=4。

在距离向量表初始化后和在同步版本的距离向量算法每次迭代后，计算它的距离向量表（如我们以前对图5-6讨论时所做的那样)。

初始结点x的路由选择表

From	cost to x	cost to y	cost to z
x	0	3	4
y	INF	INF	INF
z	INF	INF	INF

初始结点y的路由选择表

From	cost to x	cost to y	cost to z
x	INF	INF	INF
y	3	0	6
z	INF	INF	INF

初始结点z的路由选择表

From	cost to x	cost to y	cost to z
x	INF	INF	INF
y	INF	INF	INF
z	4	6	0

迭代(与相邻结点交换DV)1次后, 结点x的路由选择表

对x结点来说, 即y行和z行被填充, 然后用于更新x行, 发现无法更新

From	cost to x	cost to y	cost to z
x	0	3	4
y	3	0	6
z	4	6	0

迭代1次后, 结点y的路由选择表, 也拥有了x, z的DV, 然后用他们更新y的DV, 也无法更新

From	cost to x	cost to y	cost to z
x	0	3	4
y	3	0	6
z	4	6	0

迭代1次后, 结点z的路由选择表, 也拥有了x, y的DV, 然后用他们更新z的DV, 也无法更新

From	cost to x	cost to y	cost to z
x	0	3	4
y	3	0	6
z	4	6	0

结束

P9

考虑距离向量路由选择中的无穷计数问题。如果我们减小一条链路的开销，将会出现无穷计数问题吗? 为什么? 如果我们将没有链路的两个节点连接起来,会出现什么情况?

在这里插入图片描述

不会引起无穷计数问题，这是因为减少链路成本不会导致环路（由该链路的两个节点之间的下一跳关系引起）。

例如书上的例子, c(x,y)变为1后, z到x的最短路径经过y且距离为2, 而y与x的距离肯定会小于z到x的距离, 所以算法会静止下来

用边连接两个节点相当于将边权重从无限大减小到有限权重。

P10

讨论图5-6中的距离向量算法，距离向量D(x)中的每个值不是递增的并且最终将在有限步中稳定下来。

在每一步中，节点距离向量的每次更新都基于Bellman-Ford方程，即仅减少其距离向量中的这些值。价值没有增加。如果不更新，则不会发送任何消息。因此，D(x) 是不增加的。由于这些成本是有限的，因此最终距离向量将以有限步长稳定。

P11

考虑图5-7。假定有另一台路由器w，与路由器y和z连接。所有链路的开销给定如下: c(x, y)= 4, c(x, z)=50, c(y, w) = 1, c(z, w)=1, c(y, z)= 3。假设在距离向量路由选择算法中使用了毒性逆转。

a. 当距离向量路由选择稳定时，路由器 w、y 和 z 告知彼此到 x 的距离。它们告诉彼此什么样的距离值?

b. 现在假设x和y之间的链路开销增加到60。如果使用了毒性逆转，将会存在无穷计数问题吗?为什么?如果存在无穷计数问题，距离向量路由选择需要多少次迭代才能再次到达稳定状态?评估你的答案。

c.如果c(y, x）从4变化到60，怎样修改c(y, z)才能不存在无穷计数问题?

在这里插入图片描述

毒性逆转思想: 如果u到v的最短路径上, u的下一跳结点为x, 则u将通知x, u无法到达v, 即 $D_u(v) = \infin$

a

对于路由器z

由于z到x的最短路径经过w, 所以z向w通告, D[z][x] = INF

虽然z到x的最短路径经过y, 但是y并不是路径上第一个结点, 所以z向y通告, D[z][x] = 6

对于路由器w

由于w到x的最短路径经过y, 所以w向y通告 D[w][x] = INF

由于w到x的最短路径不经过z, 所以w向z通告 D[w][x] = 5

对于路由器y

由于y到x的最短路不经过w,z, 所以y向w, z通告D[y][x] = 4

b

仍然会存在无穷计数,

假设在t0时刻通知发送后后, 链路状态发送改变

t1时刻y更新自己的DV, 因为z向y通告过D[z][x] = 6, 所以会经过z到达x, 更新自己的D[y][x] = c[y][z] + D[z][x] = 3 + 6 = 9, 显然这是不正确的, z到x的最短路会经过y, 然后根据毒性逆转,y向z通告D[y][x] = INF, 然后y向w, z通告更新后的DV

t2时刻, w接收到y的向量, 此时w到x的最短路径会经过y, 根据毒性逆转所以w向y通知D[w][x] = INF, w向z正常通知D[w][x] = c[w][y] + D[y][x] = 1 + 9 = 10, 由于z接收到y的DV后, 没有成功的更新z的DV, 所以不再通知

t3时刻z接收到w的DV, 更新自己的DV, D[z][x] = c[z][w] + d[w][x] = 1 + 10 = 11, 根据毒性逆转, z向w通告D[z][x] = INF, 向y诚实的通告D[z][x] = 11

t4时刻, y接收到z的DV, 向y通告D[z][x] = 11, 则y更新自己到x的距离为D[y][x] = c[x][z] + D[z][x] = 3 + 11 = 14, 由于毒性逆转, y向w通告D[y][x] = 14, 向z通告D[y][x] = INF

time	t0	t1	t2	t3	t4
Z	`->w, D[z][x] = INF ->y, D[z][x] = 6`		no change	`->w, D[z][x] = INF ->y, D[z][x] = 11`
W	`->y, D[w][x] = INF ->z, D[w][x] = 5`		`->y, D[w][x] = INF ->z, D[w][x] = 10`		no change
Y	`->w, D[y][x] = 4 ->z, D[y][x] = 4`	`->w, D[y][x] = 9 ->z, D[y][x] = INF`			`->w, D[y][x] = 14 ->z, D[y][x] = INF`

我们看到 w、y、z 在计算路由器 x 的成本时形成了一个循环: z的最短路经过w, w的最短路经过y, y的最短路经过z。

…

在 t27，z经过w到x的距离从t0的6变为t27的51, 此时z 通过与 x 的直接链接检测到它到 x 的最小成本是 50。所以向w, y诚实通告到x的最短距离D[z][x] = 50

t28时刻, w, y根据z到x的最新距离更新它们到x的距离, 此时w仍会通过y到达x, 代价是49 + 1 = 50, 根据毒性逆转w向y通知D[w][x] = INF, 向z通知D[w][x] = 50, y根据D[z][x] = 50, 更新D[y][x] = c[y][z] + D[z][x] = 3 + 50 = 53

在 t29，w 通过 z 得知其对 x 的最小成本是 51。

在 t30，y 将 x 的最小成本更新为 52(通过 w)。

最后，在t31时刻，没有更新，路由稳定下来。

time	t27	t28	t29	t30	t31
Z	`->w, D[z][x] = 50 ->y, D[z][x] = 50`				`D[z][x] = c[z][x] = 50`
W		`->y, D[w][x] = INF ->z, D[w][x] = 50`	`->y, D[w][x] = 51 ->z, D[w][x] = INF`		`D[w][x] = c[w][z] + D[z][x] = 51`
Y		`->w, D[y][x] = 53 ->z, D[y][x] = INF`		`->w, D[y][x] = INF ->z, D[y][x] = 52`	`D[y][x] = c[y][w] + D[w][x] = 1 + 51 = 52`

c

删除掉(y, z)边

P12

描述在 BGP 中是如何检测路径中的环路的。

由于 BGP 路由中包含AS-PATH属性, 所以如果 BGP 对等体收到一条在 AS 路径中包含其自己的 AS 编号的路由，则使用该路由将导致环路。

P13

BGP路由器将总是选择具有最短AS路径长度的无环路由吗?评估你的答案。

所选路径不一定是最短的 AS 路径。回想一下，在路线选择过程中需要考虑很多问题。由于经济原因，很可能较长的无环路路径优于较短的无环路路径。例如，AS 可能更愿意将流量发送到一个邻居，而不是发送到 AS 距离较短的另一邻居。

P14

考虑下图所示的网络。

假定AS3和AS2正在运行OSPF作为其AS内部路由选择协议。假定AS1和AS4正在运行RIP作为其AS内部路由选择协议。假定AS间路由选择协议使用的是eBGP 和 iBGP。假定最初在AS2和AS4之间不存在物理链路。
a.路由器3c从哪个路由选择协议学习到了前缀x?
b.路由器3a从哪个路由选择协议学习到了前缀x?
c.路由器1c从哪个路由选择协议学习到了前缀x?
d.路由器1d从哪个路由选择协议学习到了前缀x?

a

3c是与AS4相连的网关路由器, 所以通过eBGP学到了前缀x

b

3a不与x所在的AS4的网关路由器相邻, 所以通过3c通过iBGP学习前缀x

c

3a通过eBGP传送x的可达性信息给1c

d

1c通过iBGP传送x的可达性信息给1d

P15

参考习题P14，一旦路由器 $1 d$ 知道了 $x$ 的情况，它将一个表项 $(x, I)$ 放入它的转发表中。
a.对这个表项而言, $I$ 将等于 $I_1$ 还是 $I_2$ ?用一句话解释其原因。
b.现在假定在AS2和AS4之间有一条物理链路，显示为图中的虚线。假定路由器1d知道经AS2以及经 AS3能够访问到x。 $I$ 将设置为 $I_1$ 还是 $I_2$ ?用一句话解释其原因。
c.现在假定有另一个AS，称为AS5，其位于路径AS2和AS4之间（没有显示在图中)。假定路由器1d知道经AS2、AS5、AS4以及经过AS3、AS4能够访问到x。 $I$ 将设置为 $I_1$ 还是 $I_2$ ?用一句话解释其原因。

a

$I_1$

因为该接口开始从 1d 到网关路由器 1c 的最低成本路径, 经过2跳路由, 如果从 $I_2$ 到1c则需要3跳

b

$I_2$

两条路由具有相同的 AS-PATH 长度，但 $I_2$ 开始具有最近的 NEXT-HOP 路由器的路径, 从 $I_2$ 出到2a这个NEXT-HOP只需要2跳, 而从 $I_1$ 出到3a这个NEXT-HOP都需要3跳

c

$I_1$

$I 1$ 开始具有最短 AS-PATH 的路径: AS3, AS4, x, 而从 $I_2$ 开始的路径为AS2, AS5, AS4, x

P16

考虑下面的网络。

ISPB为地区 ISPA提供国家级主干服务。ISPC为地区ISPD抛供国家级主干服务。每个ISP由一个AS组成。B和C使用 BGP,在两个地方互相对等。

考虑从A到D的流量。B愿意将流量交给C传给西海岸（使得C将承担承载跨越整个国家的流量的开销)，而C愿意经其东海岸与B对等的站点得到这些流量（使得B将承载跨越整个国家的流量)。C可能会使用什么样的 BGP机制、使得B将通过东海岸对等点传递A到D的流量?要回答这个问题,你需要钻研BGP规范。

C 迫使 B 将 B 的所有流量移交给东海岸的 D 的一种方法是，C 仅通过与 C 的东海岸对等点向 D 通告其路由

P17

在图5-13中，考虑到达桩网络W、X和Y的路径信息。

基于W与X处的可用信息，它们分别看到的网络拓扑是什么?评估你的答案。

Y所见的拓扑视图如下图所示。

在上述解决方案中，X 不知道 AC 链路，因为 X 没有收到包含 AC 链路的到 w 或 y 的通告路由（即，X 在到 a 的路径上没有收到包含 AS A 和 AS C 的通告）目的地。

P18

考虑图5-13。

B将不会基于BGP路由选择，经过X以Y为目的地转发流量。但是有某些极为流行的应用程序，其数据分组先朝向X，然后再流向Y。指出一种这样的应用程序，描述数据分组是如何经这条未由BGP路由选择所给定的路径传输的。

BitTorrent 文件共享和 Skype P2P 应用程序。

考虑一个 BitTorrent 文件共享网络，其中对等点 1、2 和 3 分别位于桩网络 W、X 和 Y 中。由于BitTorrent文件共享的机制，peer 2很有可能从peer 1获取数据块，然后将这些数据块转发给3。这相当于B转发最终目的地为桩网络Y的数据。

P19

在图5-13中，假定有另一个桩网络V，它为ISP A的客户。

假设B和C具有对等关系，并且A是B和C的客户。假设A希望让发向W的流量仅来自B，并且发向V的流量来自B或C。A如何向B和C通告其路由?C收到什么样的AS路由?

A 应向 B 通告两条路由：AS 路径 A-W 和 A-V。

A 应该只向 C 通告一条路线，A-V。

C 接收 AS 路径：B-A-W、B-A-V、A-V。

P20

假定AS X和Z不直接连接，但与AS Y连接。进一步假定X与Y具有对等协定, Y与Z具有对等协定。最后，假定Z要传送所有Y的流量但不传送X的流量。BCP 允许Z实现这种策略吗?

由于 Z 想要传送 Y 的流量，因此 Z 将向 Y 发送路由通告。这样，当 Y 具有发往可通过 Z 到达的 IP 的数据报时，Y 将可以选择通过 Z 发送该数据报。但是，如果 Z 通告到 Y 的路由，Y 可以将这些路由重新通告到 X。因此，在这种情况下，Z 无法阻止从 X 到 Z 的流量

P21

考虑在管理实体和被管设备之间发生通信的两种方式: 请求响应方式和陷阱方式。从以下方面考虑这两种方式的优缺点:

开销
当异常事件出现时通告的时间
对于管理实体和设备之间丢失报文的健壮性。

由于多种原因，请求响应模式通常会具有更多的开销（以交换的消息数量来衡量）。首先，管理器收到的每条信息都需要两个消息：轮询和响应。陷阱仅向发送者生成一条消息。如果管理器确实只想在条件发生时收到通知，则轮询会产生更多开销，因为许多轮询消息可能表明等待的条件尚未发生。仅当条件发生时，陷阱才会生成消息。

当事件发生时，陷阱方式也会立即通知管理员。通过轮询，管理器需要在事件发生和管理器发现（通过其轮询消息）事件已发生之间等待半个轮询周期（平均）。

如果陷阱报文丢失，受管设备将不会再发送副本。如果轮询报文或其响应丢失，管理器就会知道消息丢失（因为回复永远不会到达）。因此，如果需要，管理实体可以再次轮询。

P22

在5.7节中我们看到，用不可靠的UDP数据报传输SNMP报文是更可取的方式。请考虑SNMP 设计者选择UDP而不是 TCP作为SNMP运输协议的理由。

通常，最需要网络管理的时间是在压力时期，此时网络可能严重拥塞并且数据包丢失。当 SNMP 在 TCP 上运行时，TCP 的拥塞控制将导致 SNMP 在网络管理器需要发送 SNMP 报文时精确地退避并停止发送报文。