a) Modify the distance-vector-routing pseudo-code such that each pair of neighboring nodes (p, q) has a cost for the directed edge (p, q) and a cost for the directed edge (q, p). Furthermore, have each node remember the cost vector received by its neighbor, and take advantage of this new information that it maintains.
b) Add split-horizon with poisoned-reverse to your pseudo-code in a) above.
Code: declarations:
node p
inp
G : set {g | g is a neighbor of p}
up : array [G] of boolean, {is my neighbor up? or dead?}
var
rtb : array [NID] of G, {routing table}
cost : array [NID] of integer, {cost to reach each node}
d : NID, {temporary variable}
c : array [NID] of integer {temporary variable}
param
g: element of G {g can be any neighbor}
Code: actions (data):
begin
event: receive data(d) from g
resp:
if d = p then skip {arrived}
else if d ¹ p Ù cost[d] < ¥ then
send data(d) to node rtb[d]
else if d ¹ p Ù cost[d] = ¥ then skip {non reachable}
end if
Code: send distance vector action, and detect down neighbors action:
event: true {at anytime, send cost to all neighbors}
resp:
if up[g] then send update(cost) to node g
end if
event: ~up[g] {has the neighbor died?}
resp:
for every d do
if rtb[d] = g then cost[d] = ¥
end if
end for
Code: receive distance vector:
event: receive update(c) from g then
resp: {compare costs to all destinations}
for every d do {for every destination, compare c[] and cost[]}
if d = p then cost[p] := 0
end if
if d ¹ p Ù (rtb[d] = g Ú c[d] + 1 < cost[d])
then {change routing table to point to g for dest. d}
rtb[d] := g;
cost[d] := c[d]+1 {I assume link cost of 1 for simplicity}
end if
end for
end {code}
