diff options
| -rw-r--r-- | Makefile | 5 | ||||
| -rw-r--r-- | assignments/2/README.md | 114 |
2 files changed, 64 insertions, 55 deletions
@@ -58,7 +58,7 @@ pdf2: $(STUDENT_ID)-assignment-2.pdf pdf3: $(STUDENT_ID)-assignment-3.pdf a1: pdf1 tar1 -a2: pdf2 tar2 +a2: graph pdf2 tar2 a3: pdf3 tar3 tar1: $(STUDENT_ID)-assignment-1.tar.gz @@ -70,5 +70,8 @@ tar2: $(STUDENT_ID)-assignment-2.tar.gz tar3: $(STUDENT_ID)-assignment-3.tar.gz @true +graph: + dot -Tpng assignments/2/graph.dot -o assignments/2/graph.png + clean: rm -f $(PDFS) $(TARS) diff --git a/assignments/2/README.md b/assignments/2/README.md index cf014cc..105ad47 100644 --- a/assignments/2/README.md +++ b/assignments/2/README.md @@ -238,8 +238,8 @@ which is better known as Dijkstra's shortest path algorithm. | Step | N' | D(v),P(v) | D(w),P(w) | D(x),P(x) | D(y),P(y) | D(z),P(z) | |------|--------|-----------|-----------|-----------|-----------|-----------| -| 0 | u | 2,u | 5,u | 1,u | ∞ | ∞ | -| 1 | ux | 2,u | 4,x | | 2,x | ∞ | +| 0 | u | 2,u | 5,u | 1,u | - | - | +| 1 | ux | 2,u | 4,x | | 2,x | - | | 2 | uxy | 2,u | 3,y | | | 4,y | | 3 | uxyv | | 3,y | | | 4,y | | 4 | uxyvw | | | | | 4,y | @@ -256,33 +256,41 @@ which is better known as Dijkstra's shortest path algorithm. > b) Consider the network shown in the following diagram. With the indicated link costs, use Dijkstra's shortest path algorithm to compute the shortest path from x to all other network nodes. Show how the algorithm works by computing a table like the one above. -```plaintext - z - |\ - 3 | 11 - | \ - t----y - /|\ | - 5 / | \5 | 1 - / |9 \ | - x u---- v - \ |1 / |6 - 2 \ | / | - \| / | - w-----s - 3 5 - - (z)-(t) - | | - (y)--+ - - |------------------------------------ - | | | - | | | - (t) (u) (v) (w) (x) (y) (z) - +```dot +strict graph { + s -- t [label=1] + s -- v [label=5] + t -- s [label=1] + t -- u [label=9] + t -- v [label=6] + t -- y [label=5] + t -- z [label=3] + u -- t [label=9] + u -- v [label=1] + u -- w [label=1] + u -- x [label=2] + u -- y [label=1] + v -- s [label=5] + v -- t [label=6] + v -- u [label=1] + v -- w [label=3] + w -- u [label=1] + w -- v [label=3] + w -- x [label=3] + x -- u [label=2] + x -- w [label=3] + x -- y [label=5] + y -- t [label=5] + y -- u [label=1] + y -- x [label=5] + y -- z [label=11] + z -- t [label=3] + z -- y [label=11] +} ``` + + ```ruby { s: [[:t,1], [:v,5]] @@ -296,21 +304,16 @@ which is better known as Dijkstra's shortest path algorithm. } ``` -| Step | N' | D(u), P(u) | D(w), P(w) | D(y), P(y) | -| ---- | -- | --- | --- | --- | -| 0 | x | 2,x | 3,x | 5,x | -| 1 | xu | | 1,x | 1,x - - -From source x (using the link costs in the figure), the algorithm proceeds as follows: - - Step 0: N' = {x}; D(u)=1 via x; D(y)=1 via x; D(w)=3 via x; D(v)=inf; D(z)=inf - - Step 1: add y; N' = {x,y}; relax y->w and y->z: D(w)=2 via y; D(z)=3 via y; D(u)=1 via x; D(v)=inf - - Step 2: add u; N' = {x,y,u}; relax u->v (cost 2): D(v)=3 via u; others unchanged - - Step 3: add w; N' = {x,y,u,w}; no better paths found - - Step 4: add v; N' = {x,y,u,w,v}; no better paths found - - Step 5: add z; done - Shortest-path costs from x: to u = 1 (x->u); to y = 1 (x->y); to w = 2 (x->y->w); to v = 3 (x->u->v); to z = 3 (x->y->z). - +| Step | N' | D(s),P(s) | D(t),P(t) | D(u),P(u) | D(v),P(v) | D(w),P(w) | D(y),P(y) | D(z),P(z) | +| ---- | -- | --------- | --------- | --------- | --------- | --------- | --------- | --------- | +| 0 | x | - | - | 2,x | - | 3,x | 5,x | - | +| 1 | xu | - | 11,u | | 3,u | 3,x | 3,u | - | +| 2 | xuw | - | 11,u | | 3,u | | 3,u | - | +| 3 | xuwv | 8,v | 9,v | | | | 3,u | - | +| 4 | xuwvy | 8,v | 8,y | | | | | 14,y | +| 5 | xuwvys | | 8,y | | | | | 14,y | +| 6 | xuwvyst | | | | | | | 11,t | +| 7 | xuwvystz | | | | | | | | ## 2.3 CIDR Routing (20%) @@ -327,18 +330,21 @@ From source x (using the link costs in the figure), the algorithm proceeds as fo > c) 192.53.40.6 > d) 192.53.56.7 -Answer: -- CIDR routers use longest-prefix match: among all entries that match the destination, choose the one with the longest mask; if none match, use the default route. -- Entry coverage: - - 135.46.56.0/22 covers 135.46.56.0 to 135.46.59.255 -> Interface 0 - - 135.46.60.0/22 covers 135.46.60.0 to 135.46.63.255 -> Interface 1 - - 192.53.40.0/23 covers 192.53.40.0 to 192.53.41.255 -> Router 2 - - Default -> Router 3 -- Per address: - - a) 135.46.61.10 -> matches 135.46.60.0/22 -> forward to Interface 1. - - b) 135.46.53.16 -> no /22 match -> forward using Default -> Router 3. - - c) 192.53.40.6 -> matches 192.53.40.0/23 -> forward to Router 2. - - d) 192.53.56.7 -> no /23 match -> forward using Default -> Router 3. +CIDR routers use the longest prefix match. Among all entries that match +the destination it will choose the one with the longest mask. If none +match, then is uses the default route. + +| CIDR | start | end | Route | +| ---- | ----- | --- | --------- | +| 135.46.56.0/22 | 135.46.56.0 | 135.46.59.255 | Interface 0 | +| 135.46.60.0/22 | 135.46.60.0 | 135.46.63.255 | Interface 1 | +| 192.53.40.0/23 | 192.53.40.0 | 192.53.41.255 | Router 2 | +| Default | | | Router 3 | + +a. 135.46.61.10 -> matches 135.46.60.0/22 -> forward to Interface 1. +b. 135.46.53.16 -> no /22 match -> forward using Default -> Router 3. +c. 192.53.40.6 -> matches 192.53.40.0/23 -> forward to Router 2. +d. 192.53.56.7 -> no /23 match -> forward using Default -> Router 3. ## 2.4 TCP Congestion Control (20%) |