ECE4603 Fall'00 Homework Assignment #4 Answers
Due before 5:00 p.m. Wednesday 11/8/00
--------- (You may delete all above this line) ------------------
***START_HW*** (do not delete preceding flag, or the -XXXX flags
below).
[ ]-NAME Enter your name (form: last, first middle initial)
[ ]-PRISM Enter your Prism account code (form: "gtXNNNA" where "N"
is a number, "A" is a letter, and X is either. Do not include
"@prism.gatech.edu").
[ ]-EMAIL Enter the email address ("account@server") where you
would like to receive your graded homework. If on Prism, you may leave
completely blank).
#1. Link State Routing (OSPF). Every router (A, B, ..., J) has
advertised the costs (delays) to all the other nodes. For example, node
V broadcast the following route advertisement message: "V, B:22, C:14,
G:12, W:56" (In practice, only link states that have changed since the
last broadcast are included in the message.)
Based on all the advertisement messages, the network topology and link
costs can be mapped. The letters below represent the nodes (routers) on
the network. The numbers represent costs (delay-times) on the links
between them.
(You must use a constant-width font, such as Courier, VT100, or Monaco)
> A----35----C----56----U----14----D
| | | |
45 14 12 24
| | | |
B----22----V----56----W----47----X >
| | | |
11 12 6 20
| | | |
F----13----G----21----H----45----J
A. Using Dijkstra's technique, replace the cost values with two x's "XX"
for the links that are not part of the Sink Tree for Router A. Leave the
cost values that are on links belonging to the Sink Tree for Router A.
C
> A---[35]---C---[56]---U---[14]---D
| | | |
[45] [14] [XX] [24]
| | | |
B---[XX]---V---[XX]---W---[XX]---X >
| | | |
[11] [12] [ 6] [XX]
| | | |
F---[XX]---G---[21]---H---[45]---J
#2. [ ACUDX ] What is the least-cost (least-delay) Route from A to X
(e.g., ABCDX)?
#3. [ 129 ] What is the cost of the least-cost (least-delay) Route
from A to X?
#4. [ B, A:45, V:22, F:11 | "B, A:45, V:22, F:11"]
Link-State Routing (OSPF) only reports on adjacent nodes.
What route advertisement message does node B send (same format as the
example for V in #1 above)?
#5. For Distance Vector Routing (RIP), each route sends a unicast
message to the adjacent nodes listing the routing cost to every node in
the subnet (out to the edge routers).
You are router F, connected only to B and G. The route costs in column
"Cost from " below came from the message from B to F. The costs in
column "Cost from G" came from the message from G to A. Complete the
other columns and derive the routing table for node A (last column).
The cost from F to B is 11. The cost from F to G is 13.
Note: this is not exactly the same network state as problem 1.
Destin. Cost Cost Cost from Cost from Send Packets
Node* from B from G F via B F via G to * via node
ADD 11 to col.2 ADD 13 to col. 3 SELECT LOWEST
A 45 51 - note: no answers boxes here - do not add any -
B 0 24 [ 11 ] [ 37 ] [ B ]
C 36 26 [ 47 ] [ 39 ] [ G ]
V 22 12 [ 33 ] [ 25 ] [ G ]
U 90 80 [101 ] [ 93 ] [ G ]
W 61 27 [ 72 ] [ 40 ] [ G ]
(In practice, one message at a time would arrive and be used to update
the table. For example, the message from B would cause some route costs
to change. These differences would then be sent to adjacent nodes, such
as C. There are minimum and maximum time intervals required between
advertisement messages)
#6. Answer either RIP, OSPF or BOTH to the following questions.
[ RIP ] Best for local subnets (like the Tech campus).
[ OSPF ] Best for wide-spread networks (like the MCI backbone).
[ OSPF] Requires routers only know first-hand the delay to adjacent sites
(to send the route-advertisement or link-state message).
[ OSPF ] Requires routers notify all other routers when the cost of one of
the link connected directly to it changes above a threshold amount.
[ BOTH ] Requires routers notify adjacent routers when the cost of one of
its links changes more than a threshold amount.
[ RIP ] Requires routers notify adjacent routers when the cost of one of
its routes to a distant node changes more than a threshold amount.
***END_HW*** (do not delete preceding flag) (1.0 - web)