Esau-Williams Example Determine the CMST design of the network with link cost given below • Node A is the hub/center, all nodes have weight 1 except D which has weight 2 • The link capacity is W = 3 NodeB C D E F G A 5 6 9 10 11 15B 9 6 6 8 17C 7 9 8 12D 10 5 11E 14 9 F 8 Link Costs Iteration 1: Tradeoff (B) = Cost(B,D) – 5 = 6 – 5 = 1 Tradeoff (C) = Cost(C,D) – 6 = 7 – 6 = 1 Tradeoff (D) = Cost(D,F) – 9 = 5 – 9 = -4 Tradeoff (E) = Cost(E,B) – 10 = 6 – 10 = -4 Tradeoff (F) = Cost(F,D) – 11 = 5 – 11 = -6 Tradeoff (G) = Cost(G,F) – 15 = 8 – 15 = -7Tradeoff (G) is the lowest. Since ∑ Wi = WF + WG = 1 + 1 = 2 ≤ 3, the link (G,F) is accepted. Iteration 2: Tradeoff (B) = Cost(B,D) – 5 = 6 – 5 = 1, unchanged Tradeoff (C) = Cost(C,D) – 6 = 7 – 6 = 1, unchanged Tradeoff (D) = Cost(D,F) – 9 = 5 – 9 = -4, unchanged Tradeoff (E) = Cost(E,B) – 10 = 6 – 10 = -4, unchanged Tradeoff (F) = Cost(F,D) – 11 = 5 – 11 = -6, unchanged Tradeoff (G) = Cost(G,E) – 11 = 9 – 11 = -2 Tradeoff (F) is the lowest. Since ∑ Wi = WF + WG + WD = 1 + 1 + 2 = 4 > 3, the link (F,D) is rejected. Recompute Tradeoff (F) = Cost(F,B) – 11 = 8 – 11 = -3 Next, consider Tradeoff (D). Similarly, the link (D, F) is rejected. Recompute Tradeoff (D) = Cost(D,B) – 9 = 6 – 9 = -3, Consider Tradeoff (E). Since ∑ Wi = WE + WB = 1 + 1 = 2 ≤ 3, the link (E,B) is accepted. B A G CDF E Iteration 3: Tradeoff (B) = Cost(B,D) – 5 = 6 – 5 = 1, unchanged Tradeoff (C) = Cost(C,D) – 6 = 7 – 6 = 1, unchanged Tradeoff (D) = Cost(D,B) – 9 = 6 – 9 = -3 Tradeoff (E) = Cost(E,C) – 5 = 9 – 5 = 4 Tradeoff (F) = Cost(F,B) – 11 = 8 – 11 = -3 Tradeoff (G) = Cost(G,E) – 11 = 9 – 11 = -2, unchanged A B G CDF ETradeoff (D) is the lowest. Since ∑ Wi = WB + WE + WD = 1 + 1 + 2 = 4 > 3, the link (D,B) is rejected. Recompute Tradeoff (D) = Cost(D,C) – 9 = 7 – 9 = -2 Consider Tradeoff (F). Since ∑ Wi = WB + WE + WF + WG = 1 + 1 + 1 + 1 = 4 > 3, the link (F,B) is rejected. Recompute Tradeoff (F) = Cost(F,C) – 11 = 8 – 11 = -3 Consider Tradeoff (G). The link (G,E) is rejected for the similar reason. Recompute Tradeoff (G) = Cost(G,D) – 11 = 11 – 11 = 0 Iteration 4: Tradeoff (B) = Cost(B,D) – 5 = 6 – 5 = 1, unchanged Tradeoff (C) = Cost(C,D) – 6 = 7 – 6 = 1, unchanged Tradeoff (D) = Cost(D,C) – 9 = 7 – 9 = -2 Tradeoff (E) = Cost(E,C) – 5 = 9 – 5 = 4, unchanged Tradeoff (F) = Cost(F,C) – 11 = 8 – 11 = -3 Tradeoff (G) = Cost(G,D) – 11 = 11 – 11 = 0 Tradeoff (F) is the smallest. Since ∑ Wi = WF + WG + WC = 1 + 1 + 1 = 3 ≤ 3, the link (F,C) is accepted. BA G CDF E Iteration 5: Tradeoff (B) = Cost(B,D) – 5 = 6 – 5 = 1, Tradeoff (C) = Cost(C,D) – 6 = 7 – 6 = 1, Tradeoff (D) = Cost(D,C) – 9 = 7 – 9 = -2, Tradeoff (E) = Cost(E,C) – 5 = 9 – 5 = 4, Tradeoff (F) = Cost(F,Nj) – 6, no possible Nj left. Tradeoff (G) = Cost(G,D) – 6 = 11 – 6 = 5 Tradeoff (D) is the lowest. However, this is infeasible since it violates the link weight constraint. The algorithm terminates, and thus we add link (B,A), (C,A), and (D,A) to complete the access network.BA G CF
View Full Document