![[UW ]](../gif/HuskyW.gif)
CSE
588 lecture
May 15, 1997
Steve Corbató
corbato@cac.washington.edu
Networks and Distributed Computing, Computing & Communications
University of Washington
E = S ; R = all other nodes ; O = direct connects to S
while( valid paths in O ){
P = shortest path in O
remove P from O
V = last node in P
if( V is a member of R ){
move V from R to E
use V's links to generate new paths
insert new paths into O and sort
}
}
R <- unreachable
+----------------+
| AS1 |
+----------------+
MED=5 | | MED=10
+----------------+
| AS2 |
+----------------+
Internet
124.0/16 / \ 124.0.1/24
/ \
ISP1 ISP2
\ /
124.0.1/24 \ / 124.0.1/24
Customer
NSP
+--AS2 ISP
/ | AS4
/ | |?
AS1----AS3----Customer
NSP ISP
From/To | R&E | Elsewhere |
-------------+-----------+------------+
R&E | OK | OK |
-------------+-----------+------------+
Elsewhere | OK | X |
-------------+-----------+------------+
From/To | VCI | Fed nets | Elsewhere |
-------------+-----------+------------+------------+
VCI | OK | OK | X |
-------------+-----------+------------+------------+
Fed nets | OK | X | X |
-------------+-----------+------------+------------+
Elsewhere | X | X | X |
-------------+-----------+------------+------------+