L9- IP Protocol and IP Addressing

Total Header Length = HLEN x 4 bytes = $(0014)_{16} = (20)_{10}$

Total Length = $(00A0)_{16} = (160)_{10}$

Payload = 160 - 20 = 140bytes

Efficiency = 140/160 = 7/8 = 87.5%

First byte of Class A: 0-127

First byte of Class B: 128-191

First byte of Class C: 192-223

First byte of Class D: 224-239

First byte of Class E: 240-255

a.

Class C

b.

Since Prefix of Class C = 24 bits, Suffix = 8 bits

Maximum number of hosts in this network = 2^8 - 2 = 254 hosts

Why 256-2? Because we need to exclude all 0s and all 1s.

c.

4 bits are needed to form 10 subnets (1010)

Therefore 8 bits is turned into 4 bits subnet ID and 4 bits Host ID.

The 4 bits Host ID can provide: $2^4 - 2 = 14$ hosts > 11 hosts

Since 0000 and 1111 cannot be used, the IP address of the hosts are:

1st subnet: 201.133.10.1 ~ 201.133.10.14

(^last byte 00000001 to 00001110)

Second subnet: 201.133.10.17 ~ 201.133.10.30

(^last byte 00010001 to 00011110)

3subnet: 201.133.10.33 ~ 201.133.10.46

(^last byte 00100001 to 00101110)

Fourth subnet: 201.133.10.49 ~ 201.133.10.62

(^last byte 00110001 to 00111110)

5th subnet: 201.133.10.65 ~ 201.133.10.78

(^last byte 01000001 to 01001110)

6th subnet: 201.133.10.81 ~ 201.133.10.94

(^last byte 01010001 to 01011110)

7th subnet: 201.133.10.97 ~ 201.133.10.110

(^last byte 01100001 to 01101110)

8th subnet: 201.133.10.113 ~ 201.133.10.126

(^last byte 01110001 to 01111110)

9th subnet: 201.133.10.129 ~ 201.133.10.142

(^last byte 10000001 to 10001110)

10th subnet: 201.133.10.145 ~ 201.133.10.158

(^last byte 10010001 to 10011110)

11th subnet: 201.133.10.161 ~ 201.133.10.174

(^last byte 10100001 to 10101110)

12th subnet: 201.133.10.177 ~ 201.133.10.190

(^last byte 10110001 to 10111110)

13th subnet: 201.133.10.193 ~ 201.133.10.206

(^last byte 11000001 to 11001110)

14th subnet: 201.133.10.209 ~ 201.133.10.222

(^last byte 11010001 to 11011110)

15th subnet: 201.133.10.225 ~ 201.133.10.238

(^last byte 11100001 to 11101110)

16th subnet: 201.133.10.241 ~ 201.133.10.254

(^last byte 11110001 to 11111110)

Turning The IP addresses into Binary (look at the last byte in this case):

86 -> binary -> 01010110

87 -> binary -> 01010111

88 -> binary -> 01011000

89 -> binary -> 01011001

Common bits = 8 + 8 + 4 = 20

Therefore mask = 11111111.11111111.11110000.00000000

Therefore masked address = 200.96.01010000.00000000

Aggregated Adresses = 200.96.80.0/20

Host has 1 interface.

A Router have 2 interfaces (input and output).

The End Host also have 1 interface.

1 + 1 + 2 x 3 = 8 Interfaces.

In each of the router there is a routing table.

The Source host also need a routing table because it need to determine whether the destination is in the same network.

3 + 1 = 4 Forwarding Tables

4 Tables, 8 Interface

(a)

Company X: prefix = 23, suffix = 32 - 23 = 9

Address mask of X: 11111111.11111111.11111110.00000000

Company Y: prefix = 18, suffix = 32 - 18 = 14

Address mask of Y: 11111111.11111111.11000000.00000000

For other parts of Internet: Just use the default route 0.0.0.0

Note in every routing table, there must be default entry (a default route)

Subnet Number Subnet Mask Interface

119.12.172.0 255.255.254.0 Port 1

119.12.64.0 255.255.192.0 Port 2

0.0.0.0 N/A Port 3

(b)

119.12.172.0/23 = 01110111.00001100.10101100.00000000
119.12.64.0/18 = 01110111.00001100.01000000.00000000

Only 16 bits common

Therefore mask = 11111111.11111111.00000000.00000000

Aggregated prefix = 01110111.00001100 which corresponds to 119.12.0.0/16

Subnet Number	Subnet Mask	Interface
119.12.172.0	255.255.254.0	Port 1
119.12.64.0	255.255.192.0	Port 2
0.0.0.0	N/A	Port 3

(a)
Prefix = 18

Mask = 11111111.11111111.11000000.00000000

Network ID = 130.85.64.0

(b)

Note 0000 and 1111 cannot be used.

Therefore first usable address:

130.85.64.1

©

Mask = 11111111.11111111.11000000.00000000

255.255.192.0

(d)

Set suffix as all 1s

130.85.01111111.11111111

Broadcast address = 130.85.127.255

There are 3 subnetworks. Each subnetworks are assigned with the same Network ID.

Since 132.5.0.0 is a Class B network, 16 bits is given.

We can use 8 bits for Network ID and 8 bits for Host ID.

Note Each subnetworks must be assigned with the same Network ID. The Router’s interface should also use the same Network ID as the subnet.

To perform checksum, simply add up all the Hex values.

4500 + 0034 + B612 + 4000 + 4006 + 6F80 + 0A00 + 008B + 5BC6 + AEE0

= 2FFFD

The result is converted to binary.

2FFFD => 10 1111 1111 1111 1101

The first 2 bits are the carry and added to the remaining 16 bits:

10 + 1111 1111 1111 1101 = 0000 0000 0000 0000

It becomes all zero. Therefore no error.

L10 - IP Routing

This is Fixed routing. We manually configure the table.

Routing Table of R2

First fill in the available destination networks.

Mask = change all non-0 bytes to 255

For 111.0.0.0, next hop is not applicable because it is directly attached to R2.

For 170.14.0.0 and 145.80.0.0, we need to forward the packet to R1 from the m1 interface of R2. So next hop ip is the m0 interface of R1.

For 192.16.7.0, we need to forward the packet to R3 from the m1 interface of R2. So next hop ip is the m1 interface of R3.

The rest of the internet is connected to the m0 interface of R2.

Destination Network Mask Next Hop (Next Router) Interface

170.14.0.0 255.255.0.0 111.25.19.20 m1

145.80.0.0 255.255.0.0 111.25.19.20 m1

111.0.0.0 255.0.0.0 - m1

192.16.7.0 255.255.255.0 111.15.17.32 m1

0.0.0.0 0.0.0.0 Default router m0

Routing Table of R3

First fill in the available destination networks.

Mask = change all non-0 bytes to 255

For 111.0.0.0 and 192.16.7.0, next hop is not applicable because it is directly attached to R3.

For 170.14.0.0 and 145.80.0.0, we need to forward the packet to R1 from the m1 interface of R3. So next hop ip is the m0 interface of R1.

For 0.0.0.0 (Rest of the internet), we need to forward the packet to R2 from m1 interface of R3. So the next hop ip is the m1 interface of R2.

Destination Network Mask Next Hop (Next Router) Interface

170.14.0.0 255.255.0.0 - m1

145.80.0.0 255.255.0.0 111.25.19.20 m1

111.0.0.0 255.0.0.0 111.25.19.20 m1

192.16.7.0 255.255.255.0 - m0

0.0.0.0 0.0.0.0 111.30.31.18 M1

Destination Network	Mask	Next Hop (Next Router)	Interface
170.14.0.0	255.255.0.0	111.25.19.20	m1
145.80.0.0	255.255.0.0	111.25.19.20	m1
111.0.0.0	255.0.0.0	-	m1
192.16.7.0	255.255.255.0	111.15.17.32	m1
0.0.0.0	0.0.0.0	Default router	m0

Destination Network	Mask	Next Hop (Next Router)	Interface
170.14.0.0	255.255.0.0	-	m1
145.80.0.0	255.255.0.0	111.25.19.20	m1
111.0.0.0	255.0.0.0	111.25.19.20	m1
192.16.7.0	255.255.255.0	-	m0
0.0.0.0	0.0.0.0	111.30.31.18	M1

Using Least Cost Tree to represent shortest paths of Node 4

Find all the shortest paths from node 4 to all other nodes.

First, Node 4 is added to the tree.

Find the weight of Node 4 (denoted as $D_4$ ) to other nodes. (i.e. the Initial case)

N $D_1$ $D_2$ $D_3$ $D_5$ $D_6$

{4} 5 1 2 3 $\infty$

Among those nodes, $D_2$ is closest to $N$ (only 1 weight).

Therefore Node 2 is added to the tree.

After Node 2 is added to the tree, We update the shortest path. (1st Iteration)

With Node 2 in the tree, we can now connect to Node 1 with closer path (1+3=4).

N $D_1$ $D_2$ $D_3$ $D_5$ $D_6$

{2,4} 4 2 3 $\infty$

Since $D_3$ is closest to $N$ (only 2 weight),

Therefore Node 3 is added to the tree.

After Node 3 is added to the tree, We update the shortest path. (2nd Iteration)

With Node 3 in the tree, we can now connect to Node 6 with a path (2+1=3).

N $D_1$ $D_2$ $D_3$ $D_5$ $D_6$

{2,3,4} 4 3 3

Since $D_5$ is closest to $N$ (only 3 weight),

Therefore Node 5 is added to the tree.

After Node 5 is added to the tree, We update the shortest path. (3rd Iteration)

N $D_1$ $D_2$ $D_3$ $D_5$ $D_6$

{2,3,4,5} 4 3

Since $D_6$ is closest to $N$ (only 3 weight),

Therefore Node 6 is added to the tree.

After Node 6 is added to the tree, We update the shortest path. (4th Iteration)

N $D_1$ $D_2$ $D_3$ $D_5$ $D_6$

{2,3,4,5,6} 4

Then the remaining $D_1$ is added to the tree.

We update the shortest path. (5th Iteration)

Now we have a tree diagram and show all the costs.

N $D_1$ $D_2$ $D_3$ $D_5$ $D_6$

{1,2,3,4,5,6} 4 1 2 3 3

From the graph, we can create a routing table of Node 4.

Dest Next Hop Cost

1 2 4

2 2(Direct Link) 1

3 3(Direct Link) 2

5 5(Direct Link) 3

6 3 3

A quicker way to write the solution:

N	$D_1$	$D_2$	$D_3$	$D_5$	$D_6$
{4}	5	1	2	3	$\infty$

N	$D_1$	$D_2$	$D_3$	$D_5$	$D_6$
{2,4}	4		2	3	$\infty$

N	$D_1$	$D_2$	$D_3$	$D_5$	$D_6$
{2,3,4}	4			3	3

N	$D_1$	$D_2$	$D_3$	$D_5$	$D_6$
{2,3,4,5}	4				3

N	$D_1$	$D_2$	$D_3$	$D_5$	$D_6$
{1,2,3,4,5,6}	4	1	2	3	3

Dest	Next Hop	Cost
1	2	4
2	2(Direct Link)	1
3	3(Direct Link)	2
5	5(Direct Link)	3
6	3	3

Distance Vector Routing

When a node is booted, it can only get the neighbors node information to create a initial distance vector. (For example, A can only get info of B and D.)

In Iteration, each node will send their info to neighbor nodes and update the neighbor nodes’ distance vector. (For example, B updates C,D and A by telling them B’s info.)

Distance Vector Routing

In this question, Hop count (i.e. number of hops) is used as Cost measure. In this case, the Cost is simply 1.

Info from Router D:

Destination Hop count

Net2 4+1 = 5

Net3 8+1 = 9

Net5 6+1 = 7

Net7 3+1 = 4

Net9 5+1 = 6

B[] = min(B[], info from Router D)

If the entry has a cost smaller than the existing entry in the routing table, then you will update the entry.

Net1 is not in the info from Router D, therefore need not to update.

Net2’s info is 5, which is > 3 (original entry). Suppose we need not to update. However, the original next hop is also D. That means the info from Router D is 100% true and therefore it would be updated.

Net3’s info is 9, the Router B does not have Net3’s info, therefore the entry is added.

Net5’s info is 7, which is > 5 (original entry), therefore need not to update.

Net7’s info is 4, which is < 6 (original entry), therefore the table is updated and the new next hop is D.

Net9’s info is 6, which is > 5 (original entry), therefore need not to update.

Destination Hop count Next hop

Net1 8 A

Net2 5 D

Net3 9 D

Net5 5 C

Net7 4 D

Net9 5 C

Destination	Hop count
Net2	4+1 = 5
Net3	8+1 = 9
Net5	6+1 = 7
Net7	3+1 = 4
Net9	5+1 = 6

Destination	Hop count	Next hop
Net1	8	A
Net2	5	D
Net3	9	D
Net5	5	C
Net7	4	D
Net9	5	C

Path Vector Routing