ECE4603 Fall'00 Homework Assignment #4 (v.1.0)
Due before 5:00 p.m. Wednesday 11/8/00
Instructions. Copy this document from the Web Page, or save it from
your email program, as a "text" file. Edit it in a word processor to
add the answers into the square brackets after each question. Save it
as a "text" file, and email it back to me:
(john.copeland@ece.gatech.edu).
Email the completed document as the body of a message (not as an
attached document) with the Subject exactly as "HW-4";. Please send
questions or comments in a separate message, with a different Subject
(e.g., "Question on HW-4").
I will not accept paper returns. If you can not complete the assignment on
time, tell me why and turn it in as soon as possible for partial credit.
Remember, home work grades count as 10% of the final grade.
Your return will be graded by a computer program that looks for your
answers between square brackets. Please do not add or delete square
brackets (or the ***???*** flags). The format and units of answers
should be those indicated in the problem (e.g., a letter, a group of
letters, or a number). Each question counts equally. Each answer within
a question counts equally, but the value depends on the number of
answers within the question.
See Tips on
Submitting HW for more information.
--------- (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] [12] [24]
| | | |
B---[22]---V---[56]---W---[47]---X ->
| | | |
[11] [12] [ 6] [20]
| | | |
F---[13]---G---[21]---H---[45]---J
#2. [ ] What is the least-cost (least-delay) Route from A to X
(e.g., ABCDX)?
#3. [ ] What is the cost of the least-cost (least-delay) Route
from A to X?
#4. [ ] {Link-State 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 B" 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).
Destin. Cost Cost Cost from Cost from Send Packets
Node* from B from G F via B F via C to * via node
A 45 51
B 0 24 [ ] [ ] [ ]
C 36 26 [ ] [ ] [ ]
V 22 12 [ ] [ ] [ ]
U 90 80 [ ] [ ] [ ]
W 61 27 [ ] [ ] [ ]
(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.
[ ] Best for local subnets (like the Tech campus).
[ ] Best for wide-spread networks (like the MCI backbone).
[ ] Requires routers only know first-hand the delay to adjacent sites
(to send the route-advertisement or link-state message).
[ ] Requires routers notify all other routers when the cost of one of
the link connected directly to it changes above a threshold amount.
[ ] Requires routers notify adjacent routers when the cost of one of
its links changes more than a threshold amount.
[ ] 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)