IP Networks - Q&A Part 2

L6,7 - Multicast Routing Protocols

Only consider the last 23 bits of IP as xx:xx:xx in the Mac level address.

• First convert IP address to binary, then take the last 23 bits
• Add a 0 to the head
• Change it to hex values and substitute xx:xx:xx

(i) 231.205.98.177 = 11100111.11001101.01100010.10110001 => 01:00:5E:4D:62:B1

(ii) 239.255.255.255 = 11101111.11111111.11111111.11111111 => 01:00:5E:7F:FF:FF

(iii) 224.10.130.10 = 11100000.00001010.10000010.00001010 => 01:00:5E:0A:82:0A

(iv) 224.138.130.10 = 11100000.10001010.10000010.00001010 => 01:00:5E:0A:82:0A

32 − 4 = 28 bits are available for multicast addresses. Thus, the size of the multicast address space is $N = 2^{28}$.

The probability that two groups choose the same address is P(Any) P(Same address):

$1 \times \frac{1}{N} = \frac{1}{N} = \frac{1}{2^{28}} = 3.73\times10^{-9}$

The probability that two groups choose the different address

$1 \times \frac{N-1}{N} = \frac{N-1}{N}$

The probability that 1000 groups all have different addresses is

$$\frac{N \cdot(N-1) \cdot(N-2) \Lambda(N-999)}{N^{1000}}=\left(1-\frac{1}{N}\right)\left(1-\frac{2}{N}\right) \Lambda\left(1-\frac{999}{N}\right)$$

The probability that 1000 groups interfere with each other

$$1-\frac{N \cdot(N-1) \cdot(N-2) \Lambda(N-999)}{N^{1000}}$$

IGMP format

a. Type: Query message

b. Checksum: 0xEEFF

c. Groupid: 0xE80E1508

Routing table entries: 225.4.6.7, 225.11.6.8, 226.34.12.9, 226.23.22.67, 229.12.4.89

Recieved Report : 225.4.6.7 (old), 255.32.56.8 (new), 226.34.12.9 (old)

No reply: 225.11.6.8, 226.23.22.67, 229.12.4.89

When the router receives the report about groupid 225.32.56.8 (a new membership), it should create a new entry in its group table setting the state for the group to Delaying. It should also set a timer. When the timer expires, it should send a report message to the next higher router in the spanning tree to indicate the new member of that group.

Since the groups 225.4.6.7 and 226.34.12.9 are both listed in the group table, no action needs to be taken for these groups.

Since there was no response for groups 225.11.6.8, 226.23.22.67, and 229.12.4.89, they should all be removed from the group table (have their state marked Free).

A B E F are involved in a multicast group

F is chosen as the center in a center-based multicast routing algorithm

For center F:

Total Cost For center F: 3 + 2 + 1 + 1 + 1 = 8

Repeat the question when router A, B and E is selected as the center respectively.

For center A:

Total Cost For center A: 3 + 2 + 2 + 4 = 11

For center B:

Total Cost For center B: 1 + 1 + 1 + 4 = 7

For center E:

Total Cost For center E: 1 + 2 + 3 + 1 + 1 = 8

Finding Steiner tree:

Note: Dijkstra algorithm vs Steiner Tree

• Dijkstra algorithm find the minimum cost to the source
• Steiner Tree find the minimum distance to the tree

Therefore Only when B is the center, the resulting tree is the minimum-cost Steiner tree.

• In fact we can just count the total cost to know only when B is the center, the resulting tree is the minimum cost tree.

Binary tree of routers

The cost of sending one packet to all 64 receivers via multicast is 1 + 2 + 4 + … + 64 = 126

With multicast, the packet traverses a link exactly once. There are 126 links in a binary tree of depth 5.

If the packet is unicast to all receivers, then each of the 64 receivers is sent an individual packet. Each packet must travel across five links (recall the tree depth is 6) from the source to any receiver. Hence the cost is 64*6=384.

We see there is a significant savings using multicast in this case.
(The links between users and routers are excluded in the calculation as our main concern is the cost of the core networks)

Cost of m0 : 3+4 = 7

Cost of m1: 6

Cost of m2: 3+2 = 5

The packet that has arrived through m2 should be forwarded because if R3 wants to send a packet to the source, S, in the reverse path, it will send it through the interface m2.

In OSPF: R is the root of the unitcast communication.

In MOSPF : S is the root of multicast communication.

Build up the shortest path tree, we get:

Extra (Multicast Routing)

(i) Assume Router C contains the source (158.132.28.3) of a multicast application and routers B, D, E, F, and G contain the members of the multicast group (224.2.3.4). Determine the broadcasting tree for the source using reverse path forwarding (RPF). Indicate the links over which packets will be forwarded, and the links over which packets will not be forwarded.

(ii) Assume reverse path multicasting (RPM) is used to prune the broadcasting tree. Determine the resultant tree. Show the routing table entry for this multicast group at router D and G.

Routing table entry for this multicast group at router D:

Source Address	Multicast Group	Input interface	Output interface list
158.132.28.3	224.2.3.4	b	c,f

Routing table entry for this multicast group at router G:

Source Address	Multicast Group	Input interface	Output interface list
158.132.28.3	224.2.3.4	a	c

(iii) Assume now router B contains the source and router C has members joining the group. MOSPF is used to construct the shortest path tree from B. Determine the shortest path sub-tree at D and F. Show the routing table entry for this multicast group at router D and F.

Shortest Path Tree:

the shortest path sub-tree at D

routing table entry for this multicast group at router D:

Source Address	Multicast Group	Input interface	Output interface list
158.132.28.3	224.2.3.4	c	b,f

the shortest path sub-tree at F

routing table entry for this multicast group at router F:

Source Address	Multicast Group	Input interface	Output interface list
158.132.28.3	224.2.3.4	a	N.A.

(iv) Assume new members join in Router A, using the algorithm shown in Figure Q1(b), construct the minimum cost tree for the members of the group. You may start the algorithm with Router F and show your steps in detail.

L8 - IPv6 and Mobile IP

Yes, because the entire IPv6 datagram (including header fields) is encapsulated in an IPv4 datagram

Only skip 0 ahead

a. ::F53:6382:AB00:67DB:BB27:7332

b. ::4D:ABCD

c. ::AF36:7328:0:87AA:0398

d. 2819:AF::35:CB2:B271

(a) 0000:0000:0000:0000:0000:0000:0000:2222

(b) 1111:0000:0000:0000:0000:0000:0000:0000

© 000B:000A:00CC:0000:0000:0000:1234 :000A

The Protocol field tells the destination host which protocol handler to give the IP packet to. Intermediate routers do not need this information, so it is not needed in the main header. Actually, it is there, but disguised. The “Next header” field of the last (extension) header is used for this purpose.

The “Next header” field is used to specify the type of information that follows the current header. For example, if the datagram includes an extension header, the “Next header” field specifies the type of the extension header. If no extension header exists, the “Next header” field specifies the type of data being carried in the payload.

Conceptually, there are no changes. Technically, the IP addresses requested are now bigger, so bigger fields are needed.

The checksum is eliminated in IPv6 because it is provided by upper-layer protocols; it is therefore not needed at this level.

Two mobiles could certainly have the same care-of-address in the same visited network. Indeed, if the care-of-address is the address of the foreign agent, then this address would be the same. Once the foreign agent decapsulates the tunneled datagram and determines the address of the mobile, then separate addresses would need to be used to send the datagrams separately to their different destinations (mobiles) within the visited network.

Because datagrams must be first forward to the home agent, and from there to the mobile, the delays will generally be longer than via direct routing. Note that it is possible, however, that the direct delay from the correspondent to the mobile (i.e., if the datagram is not routed through the home agent) could actually be smaller than the sum of the delay from the correspondent to the home agent and from there to the mobile. It would depend on the delays on these various path segments. Note that indirect routing also adds a home agent processing (e.g., encapsulation) delay.

If the correspondent is mobile, then any datagrams destined to the correspondent would have to pass through the correspondent’s home agent. The foreign agent in the network being visited would also need to be involved, since it is this foreign agent that notifies the correspondent’s home agent of the location of the correspondent. Datagrams received by the correspondent’s home agent would need to be encapsulated/tunneled between the correspondent’s home agent and foreign agent.

Doesn’t care if they are in the same network, still will forwarded by home agent.

Extra (IPv6 and Mobile IP)

Path:

A Home to B Home Agent

B Home Agent to B Foreign Agent

B Foreign Agent to B home

L9 - TCP

a. 000000

None of the control bits are set. The segment is part of a data transmission without piggybacked acknowledgment.

b. 000001

The FIN bit is set. This is a FIN segment request to terminate the connection.

c. 010001

The ACK and the FIN bits are set. This is a FIN + ACK in response to a received FIN segment.

d. 000100

The RST bit is set. This a request for resetting.

e. 000010

The SYN bit is set. This is a SYN segment. The client wishes to establish a connection with the server.

f. 010010

The ACK and the SYN bits are set. This is a SYN + ACK segment is sent in response to a SYN segment.

a. Source port (16 bits = 2 bytes)

0532 in HEX

b. Destination port (16 bits = 2 bytes)

0017 in HEX

c. Sequence number (32 bits = 4 bytes)

00000001 in HEX

d. Acknowledgement number (32 bits = 4 bytes)

00000000 in HEX

e. HLEN (4 bits = half byte)

Note Header length = HLEN x 4, therefore

5 x 4 = 20 bytes

f. The control field is 002 in hex. This indicates a SYN segment used for connection establishment.

g. The window size field is 07FF in hex and 2047 in decimal. The window is 2047 bytes.

Message	ACK	Total Length	Sequence Number	ACK Number
1	1(Given)	50+20(Given)	220(Given)	689 (Given)
2	1	0+20	688	270
3	0	300+20	270	689
4	1	0+20	688	570
5	0	150+20	689	570
6	1	0+20	569	839

a. Identify the intervals of time when TCP slow start is operating.

TCP slowstart is operating in the intervals [1,6] and [23,26]

b. Identify the intervals of time when TCP congestion avoidance is operating.

TCP congestion avoidance is operating in the intervals [6,16] and [17,22]

c. After the 16th transmission round, is segment loss detected by a tripple duplicate ACK or by a timeout?

After the 16th transmission round, packet loss is recognized by a triple duplicate ACK. If there was a timeout, the congestion window size would have dropped to 1.

d. After the 22nd transmission round, is segment loss detected by a tripple duplicate ACK or by a timeout?

After the 22nd transmission round, segment loss is detected due to timeout, and hence the congestion window size is set to 1.

e. What is the initial value of ssthresh at the first transmission round?

The threshold is initially 32, since it is at this window size that slow start stops and congestion avoidance begins.

f. What is the value of ssthresh at the 18th transmission round?

The threshold is set to half the value of the congestion window when packet loss is detected. When loss is detected during transmission round 16, the congestion windows size is 42. Therefore ssthresh = 42/2 = 21, Hence the threshold is 21 during 18th transmission round.

g. What is the value of ssthresh at the 24th transmission round?

The threshold is set to half the value of the congestion window when packet loss is detected. When loss is detected during transmission round 22, the congestion windows size is 26. Therefore ssthresh = 26/2 = 13, Hence the threshold is 13 during the 24th transmission round.

h. During what transmission round is the 70th segment sent?

During the 1st transmission round, packet 1 is sent; packet 2-3 are sent in the 2nd transmission round; packets 4-7 are sent in the 3rd transmission round; packets 8-15 are sent in the 4th transmission round; packets15-31 are sent in the 5th transmission round; packets 32-63 are sent in the 6th transmission round; packets 64 – 96 are sent in the 7th transmission round. Thus packet 70 is sent in the 7th transmission round.

i. Assuming a packet loss is detected after the 26th round by the receipt of a tripple duplicate ACK, what will be the values of the congestion-window size (Cwnd) and of ssthresh?

The congestion window and threshold will be set to half the current value of the congestion window (8) when the loss occurred. Thus the new values of the threshold and window size (cwnd) will both become 4.

The congestion window increases by one for each packet received (i.e., doubles every RTT) until the packet loss occurs. Note that the packet loss occurs after 12 segments, not 12 round- trip times. After the 12th segment, the sender will get duplicate ACKs and reset ssthresh and cwnd to half the current congestion window, i.e. 4. Then the cwnd value will increase linearly (congestion avoidance phase).

• Before reaching threshold, each time increase $2^m$ where m = 0…N
• If Loss happen, cwnd = cwnd/2
• After reaching threshold, each time only increase 1. (Congestion Avoidance)

Each Timeout, RTO = 2RTO

Timeout also for Segment 4 and 5,

Therefore the RTO will goes from 24 => 48 => 96

(i) Assume that the window size (W) is fixed at 2. How long does client A take to receive the whole file from the server after sending a request?

$$\text{No. of Segment} = \frac{\text{Files Size}}{\text{Segment Size}} = \frac{350K}{20K} = 18$$

$R = \text{Data Rate} = 10Mbps$

$S = \text{Segment Size} = 20K$

$W = \text{Window Size} = 2$

$$\text{Number of transmission round for sending the file} = \frac{\text{No. of Segment}}{W} = \frac{18}{2} = 9$$

$$\text{Transmission time for sending the whole window} = \frac{WS}{R} = \frac{2\times 20K}{10M} = 32\text{ms}$$

$\rm{RTT} = 20$ms

Two cases to consider:

• $\frac{WS}{R} \geq \rm{RTT} + \frac{S}{R}$
  • ACK for first segment in window returns before window’s worth of data sent
• $\frac{WS}{R} < \rm{RTT} + \frac{S}{R}$
  • wait for ACK after sending window’s worth of data sent

As RTT=20ms, the time required for the first acknowledgements go back to the server:

$$\rm{RTT} + \frac{S}{R} = \frac{20K}{10M} +\rm{RTT} =36ms$$

Since $\frac{WS}{R} < \rm{RTT} + \frac{S}{R}$, (32ms < 36ms):

Therefore, the server has to stall in each round of transmission. The stall time of the server in each transmission round is 36ms – 32 ms = 4ms

The latency =

$$2\rm{RTT} + \text{Extra Waiting time} + \frac{Files Size}{R}$$

$$= 2\times 20 + (9-1) \times (36-32) + \frac{350K}{10M} = 40 + 32 + 280 = 352\text{ms}$$

(ii) Assume that the window size (W) is adjusted according to the congestion control procedures of TCP-Reno. How long does client A take to receive the whole file from the server after sending a request? Given that the initial slow-start threshold is 32.

$$\text{No. of Segment} = \frac{\text{Files Size}}{\text{Segment Size}} = \frac{350K}{20K} = 18$$

$R = \text{Data Rate} = 10Mbps$

$S = \text{Segment Size} = 20K$

$W = \text{Window Size} = 2$

$$\text{Number of transmission round for sending the file} = \frac{\text{No. of Segment}}{W} = \frac{18}{2} = 9$$

$$\text{Transmission time for sending the whole window} = \frac{WS}{R} = \frac{2\times 20K}{10M} = 32\text{ms}$$

$\rm{RTT} = 20$ms

Two cases to consider:

• $\frac{WS}{R} \geq \rm{RTT} + \frac{S}{R}$
  • ACK for first segment in window returns before window’s worth of data sent
• $\frac{WS}{R} < \rm{RTT} + \frac{S}{R}$
  • wait for ACK after sending window’s worth of data sent

Given that the initial slow-start threshold is 32.

According to slow start, the congestion window will increase as 1, 2, 4, 8, 16 …

To send a total of 18 segment, we need 5 transmission rounds (1+2+4+8+3 = 18)

The time required for the first acknowledgements go back to the server =

$$\rm{RTT} + \frac{S}{R} = \frac{20K}{10M} +\rm{RTT} =36ms$$

In the 1st round, the transmission time for sending the whole window (W=1)

$$\frac{WS}{R} = \frac{S}{R} = \frac{20K}{10M} = 16\rm{ms}$$

Since $\frac{WS}{R} < \rm{RTT} + \frac{S}{R}$, (16ms < 36ms): the server has to stall

In the 2nd round, the transmission time for sending the whole window (W=2)

$$\frac{WS}{R} = \frac{2S}{R} = \frac{2\times20K}{10M} = 32\rm{ms}$$

Since $\frac{WS}{R} < \rm{RTT} + \frac{S}{R}$, (32ms < 36ms): the server has to stall

In the 3rd round, the transmission time for sending the whole window (W=4)

$$\frac{WS}{R} = \frac{2S}{R} = \frac{4\times20K}{10M} = 64\rm{ms}$$

Since $\frac{WS}{R} > \rm{RTT} + \frac{S}{R}$, (64ms > 36ms): the server needs not to stall

After the 3rd round, the 4th round and 5th round also needs not to stall.

No. of transmission round that the server has to wait = 2

The latency =

$$2\rm{RTT} + \text{Extra Waiting time} + \frac{Files Size}{R}$$

$$= 2\times 20 + (36-16) + (36-32) + \frac{350K}{10M} = 40 + 20 + 4 + 280 = 344\rm{ms}$$

Extra (TCP)

Given $\alpha = 0.15$ , $\beta = 0.2$

Given $\rm{RTT}_S = 70$ ms, $\rm{RTT}_D = 10$ ms just before the first of these six samples

Given The $\rm{RTT}_M$ for the 6 segments are 68ms, 42ms, 65ms, 80ms, 38ms, 75ms

$\mathrm{RTT}_{\mathrm{S}}=(1-\alpha) \times \mathrm{RTT}_{\mathrm{S}}+\alpha \times \mathrm{RTT}_{\mathrm{M}} = 0.85 \times \mathrm{RTT}_{\mathrm{S}} + 0.15 \times \mathrm{RTT}_{\mathrm{M}}$

$\rm{RTT}_D=(1-\beta) \times \rm{RTT}_D+\boldsymbol{\beta} \times \left|\rm{RTT}_S-\rm{RTT}_M\right| = 0.8\times \rm{RTT}_D + 0.2\times|\rm{RTT}_S - \rm{RTT}_M|$

$\rm{RTO} = \rm{RTT_s} + 4\rm{RTT_D}$

Segment	$\rm{RTT}_M$	$\rm{RTT}_S$	$\rm{RTT}_D$	$\rm{RTO}$
1st	68	69.7	8.34	103.06
2nd	42	65.54	11.38	111.07
3rd	65	65.46	9.20	102.25
4th	80	67.64	9.83	106.96
5th	38	63.20	12.90	114.81
6th	75	64.97	12.33	114.28

Therefore RTO = 114.28ms

(i) Sketch how the value of sending window changes as a function of time (in units of RTT) during the whole connection time.

Given:

Initial Slow-start threshold is 8

Buffer has a storage space of 150 K bytes

Segment size = 15 K bytes

Therefore buffer can hold $\frac{150K}{15K} = 10$ Segments

Cwnd will go from 1,2,4,8 each RTT

The sending window must be =< 10

After reaching threshold (8 in this case), enter Congestion Avoidance state. cwnd+1 after each RTT.

(ii) Determine how long client A takes to receive the whole file from the server after sending a request.

Given:

900K bytes stored in a web server

Segment size = 15 K bytes

Tranmission rate = 10 Mbps

RTT between server and client = 30ms

Number of segments to send = $\frac{900 \text{K bytes}}{15 \text{K bytes}} = 60$ segments to send

60 = 1 + 2 + 4 + 8 + 9 + 10 + 10 + 10 + 6

Total 9 tranmission rounds needed to send.

Time need for First ACK: $\text{number of hops} \times \frac{S}{R} + \rm{RTT} = 3 \times \frac{15K \times 8}{10M} + 30$

$= 36\text{ms} + 30\text{ms} = 66\text{ms}$

1st round, W = 1, therefore $\frac{WS}{R} = \frac{S}{R} = \frac{15K \times 8}{10M} = 12\text{ms}$

Since 12ms < 66ms, server has to wait for ACK (wait for 66ms - 12ms = 54ms)

2nd round, W = 2, therefore $\frac{WS}{R} = \frac{2S}{R} = 2\times \frac{15K \times 8}{10M} = 24\text{ms}$

Since 24ms < 66ms, server has to wait for ACK (wait for 66ms - 24ms =42ms)

3rd round, W = 4, therefore $\frac{WS}{R} = \frac{4S}{R} = 4\times \frac{15K \times 8}{10M} = 48\text{ms}$

Since 48ms < 66ms, server has to wait for ACK (wait for 66ms - 48ms =18ms)

4th round, W = 8, therefore $\frac{WS}{R} = \frac{8S}{R} = 8\times \frac{15K \times 8}{10M} = 96\text{ms}$

Since 96ms >= 66ms, server need not to wait for ACK

No. of tranmission round that the server has to wait= 3

Total latency:

$2RTT + (3-1)\frac{S}{R} + 54 + 42 + 18 + \frac{900K \times 8}{10Mbps}$

$= 2\times 30\text{ms} + 2\times 12\text{ms} + 54\text{ms} + 42\text{ms} + 18\text{ms} + 720\text{ms} = 918\text{ms}$

L10 - Application Layers

The following shows the commands and responses. The file mode in this case needs to be C (compressed).

The following shows the set of commands and responses. Note that there is no data transfer connection in this; we have only a control connection. We need to give the name of the file to be renamed (/usr/users/report/file1) and then the new name (/usr/top/letters/file1).

• RNFR first identify name
• RNTO write the file to new directory

If the identifier of a key and a node is the same, the node is responsible for the key. In other words, the node is the successor of the key, but not the predecessor of it. In this case, N5 is the successor of k5, but the predecessor of k5 is the node before N5 in the ring.

Size of the identifier space = 16

$\log_2(16) = 4$

The rows in the table for node N6 show the successors of target keys $(6 + 2^{m-1})$ for $m = 1$ to $4$:

m	Target Key	Successor
1	6+1 = 7	N8
2	6+2 = 8	N8
3	6+4 = 10	N12
4	6+8 = 14	N3

$m = 4$ , therefore Size of the identifier space = 16

Peers: N3, N8, N11, N13

Keys: k5, k9, k14

Key	Successor
k5	N8
k9	N11
k14	N3

Finger table of N3: (Pre: N13)

m	Target Key	Successor
1	3+1 = 4	N8
2	3+2 = 5	N8
3	3+4 = 7	N8
4	3+8 = 11	N11

Finger table of N8: (Pre: N3)

m	Target Key	Successor
1	8+1 = 9	N11
2	8+2 = 10	N11
3	8+4 = 12	N13
4	8+8 = 16 (0)	N3

Finger table of N11: (Pre: N8)

m	Target Key	Successor
1	11+1 = 12	N13
2	11+2 = 13	N13
3	11+4 = 15	N3
4	11+8 = 19 (3)	N3

Finger table of N13: (Pre: N11)

m	Target Key	Successor
1	13+1 = 14	N3
2	13+2 = 15	N3
3	13+4 = 17 (1)	N3
4	13+8 = 21 (5)	N8

Therefore: