Consider the following forwarding table. Hint: Ch$4$ Forwarding table and longest prefix matching.

$\backslash$table$[[$Destination address range,,$\backslash$table$[[$Link$],[$interface$]],],[10000001,00000010,00000000,00000000,0],[$through$,,,,],[10000001,00000010,00000011,11111111,],[10000001,00000010,000000000,00000000,1],[$through$,,,,],[10000001,00000010,00000001,11111111,],[10000001,00000010,00000100,00000000,2],[$through$,,,,],[10000001,00000010,00000111,11111111,],[$Otherwise$,,,,3]]$

a$.(9$ pt$.)$ Rewrite the forwarding table using the wildcard notation $($See the slide for "Longest prefix matching"$).$

$\backslash$table$[[$Destination address range,$\backslash$table$[[$Link$],[$interface$]]]]$

$\backslash$table$[[,0],[,1],[,2],[$Otherwise$,3]]$

b$.(9$ pt$.)$ Rewrite the forwarding table using the CIDR notation $("$a$.$b$.$c$.$d$/$x$").$

$\backslash$table$[[$Destination address range,$\backslash$table$[[$Link$],[$interface$]]],[,0],[,1],[,2],[$Otherwise$,3]]$

c$.(12$ pt$.,3$ pt$.$ each$)$ For each of the following IP address, convert it to binary and determine the outgoing link interface. Justify your answer.

i$.129\mathrm{.}2\mathrm{.}1\mathrm{.}5$

ii$.129\mathrm{.}2\mathrm{.}3\mathrm{.}5$

iii. $129\mathrm{.}2\mathrm{.}5\mathrm{.}5$

iv$.129\mathrm{.}2.8\mathrm{.}5$

Problem $2.$ Network Address Allocation $(20$ pt$.)$

Consider a router that interconnects four subnets: S$1,$ S$2,$ S$3,$ and S$4.$ Suppose all of the interfaces in each of these four subnets are required to have the prefix $199\mathrm{.}100\mathrm{.}8\mathrm{.}0/21.$ You want to divide this address block into four equal$-$sized contiguous address blocks, and give one of these address blocks to each subnet connected to the router. Provide network addresses $($of the form a$.$b$.$c$.$d$/$x$)$ that satisfy this requirement.

Problem $3.$ Link State Routing $(30$ pt$.)$

Consider the following network.

With the indicated link costs, use Dijkstra's shortest$-$path algorithm to compute the shortest path from $"w"$ to all network nodes. Show how the algorithm works by computing the table below. Note: If there exists any tie in each step, choose the leftmost column first.

$\backslash$table$[[$Step$,N^{\text{'}},\backslash$table$[[D(s),],[p(s)$