Network Graph Analysis and BGP Routing
Published:
Consider the weighted graph below with nodes A, B, C, D, E, F, G, H, I. (a) Compute the adjacency matrix and the incidence matrix of the network structure. [10 Marks] (b) Using Dijkstra's Algorithm, determine the shortest path from node H to node B. Clearly show all iterations (distance table updates). [10 Marks] (c) Briefly explain why Dijkstra's Algorithm does not work correctly with negative edge weights. [5 Marks] (d) Does the graph above exhibit Euler path and or Euler circuit? Explain your answer using vertex degrees. [5 Marks] (e) AS100 runs OSPF internally with the link costs shown in the topology above. Router A peers with AS200 and receives a BGP UPDATE for prefix 172.16.0.0/16 with AS-PATH [200, 300] and LOCAL-PREF 150. Router E peers with AS400 and receives a BGP UPDATE for the same prefix with AS-PATH [400] and LOCAL-PREF 100. Apply the BGP decision process in the correct order to identify the preferred exit router, then trace the full OSPF path from router H to that exit router using the link costs shown. [10 Marks]
This question includes visual content: The image shows a weighted undirected graph with nodes labeled A, B, C, D, E, F, G, H, and I. The nodes are arranged in a circular perimeter with node I in the center. Edges connect the nodes with various weights: (A,B)=5, (B,C)=7, (C,D)=8, (D,E)=20, (E,F)=4, (F,G)=1, (G,H)=2, (H,A)=18, (A,I)=1, (C,I)=6, (E,I)=2, (G,I)=3. There are some handwritten annotations near the edges.
Animated Video Solution
The first half plays free, the full solution is in the app.
Step by Step Written Solution
Hi baxter, let's solve this comprehensive network graph problem step by step. We'll start with part a, which asks us to compute the adjacency and incidence matrices of the given topology.
Problem Overview
- Part (a): Adjacency and Incidence Matrices
- Part (b): Dijkstra's Algorithm from $H$ to $B$
- Part (c): Why Dijkstra fails with negative weights
- Part (d): Euler Path and Circuit analysis
- Part (e): BGP Decision Process & OSPF Path routing
Let's first reconstruct the network topology on our whiteboard to clearly see all vertices, edges, and their respective weights.
An adjacency matrix represents the link costs between adjacent vertices. If two distinct vertices are connected, we write their link weight. If they are not connected, we write zero, and the diagonal is zero. Let's list the vertices in alphabetical order.
Adjacency Matrix
- Vertices ordered as: $A, B, C, D, E, F, G, H, I$
Here is the completed nine-by-nine adjacency matrix. For example, row A shows connections to B with cost five, G with cost nine, H with cost eighteen, and I with cost one.
Now let's compute the binary incidence matrix. It has nine rows representing vertices and fourteen columns representing the edges in a selected order. An entry is one if the vertex is incident to that edge, and zero otherwise.
Incidence Matrix
- Edges: $e_1(A,B), e_2(A,G), e_3(A,H), e_4(A,I), e_5(B,C), e_6(C,D), e_7(C,E), e_8(C,I), e_9(D,E), e_{10}(E,F), e_{11}(E,I), e_{12}(F,G), e_{13}(G,H), e_{14}(G,I)$
Next, let's look at Part b: using Dijkstra's Algorithm to find the shortest path from node H to node B. We will trace the distance updates step-by-step.
Part (b): Dijkstra's Algorithm from Node H
- Source: $H$
- Destination: $B$
Let's list the initial distances. At Step zero, the distance to H is zero, and all other distances are infinity.
| Step | Visited | A | B | C | D | E | F | G | H | I |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | $\{\}$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | 0 | $\infty$ |
At Step one, we visit node H. Its neighbors are A and G, with edge costs eighteen and two. We update their distances to eighteen and two.
| Step | Visited | A | B | C | D | E | F | G | H | I |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | $\{\}$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | **0** | $\infty$ |
| 1 | $\{H\}$ | $18$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | **2** | 0 | $\infty$ |
In Step two, the closest unvisited node is G, with a distance of two. Neighbors of G are A, I, and F. We calculate: A becomes two plus nine which is eleven; I becomes two plus three which is five; and F becomes two plus one which is three.
| Step | Visited | A | B | C | D | E | F | G | H | I |
|---|---|---|---|---|---|---|---|---|---|---|
| 2 | $\{H, G\}$ | $11$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | **3** | 2 | 0 | $5$ |
Now, the closest unvisited node is F, with a distance of three. We visit F and update its neighbor E: distance to E becomes three plus four, which equals seven.
| Step | Visited | A | B | C | D | E | F | G | H | I |
|---|---|---|---|---|---|---|---|---|---|---|
| 3 | $\{H, G, F\}$ | $11$ | $\infty$ | $\infty$ | $\infty$ | **7** | 3 | 2 | 0 | $5$ |
In Step four, the closest unvisited node is I, with a distance of five. Neighbors of I are A, C, and E. We update: distance to A becomes five plus one, which is six. Distance to C becomes five plus six, which is eleven. Distance to E remains seven, as seven is smaller than five plus two.
| Step | Visited | A | B | C | D | E | F | G | H | I |
|---|---|---|---|---|---|---|---|---|---|---|
| 4 | $\{H, G, F, I\}$ | **6** | $\infty$ | $11$ | $\infty$ | $7$ | 3 | 2 | 0 | 5$ |
Next, we visit node A with a distance of six. Its neighbor B is updated to six plus five, which equals eleven.
| Step | Visited | A, G, F, I, A | 6 | **11** | 11 | $\infty$ | 7 | 3 | 2 | 0 | 5 |
|---|
The rest of this solution is on Solvi
12 more steps are locked. Watch the full animated, narrated solution for free.
Snap a photo, solve any question like this.
Watch the Rest for Free
Free to download · First solutions are on us
