Introduction to Computer Networks

Mock Midterm Paper 1

Q1.3

10 packets are continuously sent over a 1 Mbps link. Each packet is of 1,000 bits long and RTT is 10 ms. What is the throughput of the link (i.e. on average, how many bits transmitted per second)?

A. 511.856 bps

B. 511.856 Kbps

C. 500 bps

D. 500 Kbps

E. 666.667 Kbps

Answer

E

We only consider one way transmission for this question.

Throughput =

Total bitsTime period

Transmission delay =

1000ร—10106 = 10ms

Propagation delay = RTT / 2 = 5ms

Throughput =

1000ร—10(10+5)ร—10โˆ’3 = 666.667 Kbps

Q1.5

Which of the following statement about IP datagram is FALSE?

A. Routing protocols determine the routes that datagrams take between sources and destinations.

B. TTL field of IP header prevents a datagram from circulating in the network forever.

C. When a big datagram is fragmented into a series of smaller fragments, transport layer header will be replicated in each fragment.

D. On the Internet, datagrams from the same source may take different routes towards the destination.

E. MTU of the link-layer protocol places a limit on the length of a datagram.

Answer

C

Q1.10

A device (D) is used to connect a sender (S) and a receiver (R). Transmission rates of the links between sender and the device and between the device and receiver are

r1 and
r2
(r1>r2)
respectively. Ignore other types of delay, what is the end-to-end delay to send a packet of length
L
?

A.

Lr1r2r1+r2, if this device is a store-and-forward packet switch.

B.

L2r1+L2r2, if this device is a store-and-forward packet switch.

C.

L(r1+r2)r1r2, if this device acts on individual bits and repeats every bit to receiver once receives it from sender.

D.

Lr1+1r2, if this device acts on individual bits and repeats every bit to receiver once receives it from sender.

E.

1r1+Lr2, if this device acts on individual bits and repeats every bit to receiver once receives it from sender.

Answer

E

Mock Midterm Paper 2

Q7

A file is transferred over an existing TCP connection (i.e., 3-way handshake is already done). The connection is still open after transmission. The first and last TCP segments have the sequence numbers 12345 and 2345 respectively. The last TCP segment carries 1000 bytes of data. What could be the size of the file transferred?

A. 10,000 bytes

B. 4,294,957,296 bytes

C. 4,294,966,296 bytes

D. 4,294,958,296 bytes

E. None of the above

Answer

D

Similar to Midterm Practice 2 Q15, but use approximation.

Q9

The distance from a sender to a receiver is 10,000 km and the propagation speed is 2*10^8 m/s. Go-back-N protocol is used and window size is set to 10. Each packet is 2,000 bits long and the size of packet header is negligible. Assume that no packet is lost or corrupted during transmission. Ignore transmission, queueing and processing delays. How long does it take to send 1 million bits from the sender to the receiver?

A. 5 s

B. 50 s

C. 2.5 s

D. 0.005 s

E. None of the above

Answer

A

Propagation delay =

10000ร—1032ร—108 = 50ms

Sender can send maximum of

2000ร—10 bits and need to wait for ACK

So, each time the delay = packet delay + ACK delay = 100ms

Each time is 20,000 bits, so 1,000,000 bits will be 50 times.

Total time = 50 * 100ms = 5s

Q10

Consider a sender and a receiver communicating using Selective Repeat protocol. Senderโ€™s window size is 5. Sender just receives an ACK packet with sequence number 23. This ACK number falls within the senderโ€™ window. Which of the following could possibly be the sequence number for the next packet transmitted by the sender?

A. 17

B. 18

C. 28

D. 30

E. None of the above

Answer

C

Midterm Practice 1

Q16

A Go-Back-N sender just receives an ACK packet with ACK number 14. This ACK number falls within sender window which has the window size 6. Every data packet embeds a k-bit sequence number field (k is a constant unknown to you).

Which of the following definitely CANNOT be the sequence number of the next packet transmitted by the sender?

A. 4

B. 9

C. 15

D. 19

E. 20

Answer

B

C,D,E are possible.

In the question, the ACK number can be 14, this means the minimum for k is 4.

If k = 4, largest seq number will be

24โˆ’1 = 15. Then the window can be [14,15,0,1,2,3].

When sender receives ACK 14, the window can become [15,0,1,2,3,4]. So 4 is possible.

Q17

Consider sending a packet over a path from node

0, through nodes
1,2,โ€ฆ
, till node
K+1
. The links, from node
i
to node
i+1
, for
i=0,1,โ€ฆ,K
each has the same link transmission rate
C
(in bits/s) and propagation delay
p
(in seconds). The packet has
h
header bits and
L
data bits.

The delay

D of a packet from node
0
to node
K+1
is defined to be the duration from when the last bit of the packet leaves node
0
to when the last bit of the packet arrives at node
K+1
. Suppose the delay also includes a processing time of
q
seconds in each of the nodes
1,2,โ€ฆ,K
. The processing time includes the waiting time in the queue.

Which of the following formula correctly gives the delay

D of a packet travelled from node
0
to node
K+1
?

A.

D=p+K[L+hC+p+q]

B.

D=(K+1)[L+hC+p+q]

C.

D=p+K[L+hC]+(K+1)q

D.

D=(K+1)p+K[L+hC]+q

E. None of the above

Answer

A

Processing delay for nodes

1,2,โ‹ฏ,K=Kq

Propagation delay for link

0,1,โ‹ฏ,K=(K+1)p

Notes: link 0 means link connecting node 0 and node 1

Transmission delay for nodes

1,2,โ‹ฏ,K=K(h+LC)

Notes: transmission delay for node 0 is not included, because of how delay is defined in the question.

D=Kq+(K+1)p+K(h+LC)=p+K(L+hC+p+q)

Q20

Two hosts A and B are separated by a router R in between. The bandwidth of the links between A and R and between R and B are 1 Kbps and 2 Kbps respectively. Ignore all other kind of delays. Suppose A sends 8*10^4 bits to B as a series of consecutive packets of 1,000 bits each, when (in seconds) will B receive all the data?







G



A

A



R

R



A->R

1 Kbps



B

B



R->B

2 Kbps



A. 40

B. 80

C. 80.5

D. 161

E. None of the above

Answer

C

We can visualised as follows

seq # reach R at reach B at
1 t = 1 t = 1.5
2 t = 2 t = 2.5
3 t = 3 t = 3.5
โ€ฆ โ€ฆ โ€ฆ
80 t = 80 t = 80.5

Midterm Practice 2

Q15

A huge file is transferred over an existing TCP connection (i.e., 3-way handshake is already done). The connection is still open after transmission. The first and last TCP segments have the sequence numbers 12,345 and 2,105 respectively. MSS is 1,024 bytes and TCP sends as much data as possible in a segment.

How many TCP segments are used to transfer the file (i.e. carries file data), assuming the communication channel is perfectly reliable?

(Hint: TCP sequence number will wrap up and restart from 0 after reaching the biggest sequence number)

Answer

Note: Remember sequence number is the "byte number" of the first byte of data in a segment. Doesn't include TCP header length.

Packets before wrap around:

  • Suppose
    12345+1024(x)=232โˆ’1
  • Then
    x=4,194,291.943โŸน4,194,291
    packets before wrap around.

Packet with wrap around sequence number

  • Sequence number of that packet =
    12345+1024(4,194,291)=4,294,966,329
  • Packet:
    [4,294,966,329:232โˆ’1โž967 bytes:0:56โŸ57 bytes]

Packets after wrap around:

  • First packet:
    [57:1080]
  • Second packet:
    [1081:2104]
  • Third packet:
    [2105:3128]

Total packets =

4,194,291+1+3=4,194,295

Q16

Consider a sender and a receiver communicating using Selective Repeat protocol. Every packet embeds a 3-bit sequence number field. Sender just sends a packet with sequence number 6. Sender window size is 3.

Which of the following CANNOT possibly be the sequence number of the next packet transmitted by sender?

A. 0

B. 2

C. 4

D. 5

E. 6

Answer

B

Q17

Two hosts A and B are connected by a router R as shown in the following diagram.







G



A

A



R

R



A->R

link 1



B

B



R->B

link 2



For link 1, link transmission rate is 1 Kbps and propagation delay is 100 milliseconds. For link 2, link transmission rate is 250 bps and propagation delay is 150 milliseconds. Suppose Host A sends 2000 packets to Host B continuously and each packet is 500 bits long. Host A starts sending the 1st packet at time

t = 0.

When (in seconds) will host B receive the

kth packet (1
โ‰ค
k
โ‰ค
2000)?

A. 0.75 + 2

k

B. 2.75

k

C. 0.6 + 2

k

D. 0.6 + 2.15

k

E. None of the above

Answer

0.75 + 2k

Q18

Suppose two hosts are connected by a direct link of 1 Mbps. A stop-and-wait protocol is used to transfer 10 packets from the sending host to the receiving host. Each packet is 1000 bytes long. RTT is 24 milliseconds. No packet is lost or corrupted during transmission and ACK packets are of negligible size.

What is the throughput (in Kbps) of the transmission?

A. 40

B. 250

C. 770

D. 870

E. 1000

Answer

B

Similar to Mock Midterm Paper 1 Q1.3, but here stop-and-wait protocol is used, so we need to consider full RTT.

Mock Final Paper 2

Q1.5

A Web server supports both HTTP/1.0 and HTTP/1.1. So far 100 clients have downloaded a web page from the server, which contains 1 HTML file and 2 images. Half of the clients run HTTP/1.0 and the other half run HTTP/1.1.

How many sockets has the Web server ever created?

A. 201

B. 200

C. 100

D. 101

E. None of the above

Answer

A

HTTP/1.0: 50 * 3 = 150

HTTP/1.1: 50

Also, HTTP runs on TCP, TCP server has a listening socket and is always present.

Total = 201

Q1.6

Which of the following statement is FALSE?

A. When a router receives an IP datagram with destination address 255.255.255.255, it must broadcast this IP datagram on all the interfaces except the interface this datagram is received.

B. One of the benefits of segmenting a big chunk of data into smaller packets for transmission in the Internet is to lower end-to-end delay.

C. MSS specifies the maximum size of a TCP segment, exclusive of the size of TCP header.

D. Hosts in the same subnet communicate with each other without intervening a router.

E. The maximum size of an IP datagram that can be transmitted over a link is restricted by the link MTU.

Answer

A

255.255.255.255 is a limited broadcast address used to reach all devices on the same local network.

Routers do not forward limited broadcast packets to other interfaces.

Q1.8

Knowing that you have taken CS2105, a friend comes to you for help with his laptop. He says that he cannot access the Web page hosted at www.example.com. Using the tools you have learned in CS2105, you run the following commands on his laptop to troubleshoot what could be the reason.

Which of the following is NOT the correct use of the corresponding tool?

A. You run telnet to check if www.example.com is listening on port 80.

B. You run traceroute to check if there is a route from the laptop to www.example.com.

C. You run dig to check if his DNS server is able to resolve the IP address of host name www.example.com.

D. You run ping to check if you can establish a TCP connection to www.example.com.

E. You run curl to check if www.example.com is responding to a HTTP request correctly.

Answer

D

ping uses ICMP

Q1.9

A Go-back-N sender just receives an ACK packet with sequence number

t. Before this ACK is received, sender's window is
[k,k+Nโˆ’1]
where
N
is the window size. Suppose
k>N
, packets may be lost or corrupted but will not be reordered. What is the smallest possible value of
t
?

A.

kโˆ’1

B.

k

C.

kโˆ’N+1

D.

kโˆ’N

E. None of the above

Answer

A

sender send packet with seq k, the packet is corrupted, so receiver send ack k - 1

Q4

Two hosts A and B are connected via a router. The link rate is 1 Mbps and propagation delay is 40 ms per link. The maximum size of a packet is 1 Kb and packet header is 80 bits. Suppose sender sends as much data as possible in a packet, packets are sent continuously and no packet is corrupted or lost during transmission.

How long (in milliseconds) does it take to send a 400 Kb file from A to B (from when the first bit of the first packet leaves A to when last bit of the last packet arrives at B)?

Answer

515.8ms (I got 515.6ms, dk what when wrong :/)

The file will be split in 434 packets with 1000 bits and 1 packets with 800 bits

Transmission delay for each first 434 packets =

10001ร—106 = 1ms

Transmission delay for last packet =

8001ร—106 = 0.8ms

We can visualise in table:

packet # arrives at router arrives at B
1 1 + 40 = 41ms 41 + 1 + 40 = 82ms
2 1(wait for packet #1) + 1 + 40 = 42ms 42 + 1 + 40 = 83ms
3 2(wait for packet #2) + 1 + 40 = 43ms 43 + 1 + 40 = 84ms
โ€ฆ โ€ฆ โ€ฆ
434 433 + 1 + 40 = 474ms 474 + 1 + 40 = 515ms
435 434 + 0.8 + 40 = 474.8ms 474.8 + 0.8 + 40 = 515.6ms

Notes: Subsequent packet will be pushed onto the link before previous packets reach router.

Correct Answer

Sample solution given:

Number of packets =

โŒˆ400ร—1031000โˆ’80โŒ‰=435

Total number of bits send =

435ร—80+400000=434800

Length of first 434 packets: 1000 Length of last packet: 800

End-to-end delay =

1000103+40+434800103+40 = 515.8ms

Mock Final Paper 3

Q3

Two hosts A and B are

2000 km apart and are connected directly using a link with propagation delay of
800
bit times and propagation speed of
2.5ร—108
m/s. A is sending a sequence of packets, each is
100
bytes in size, to B.

a) How long does it take for B to receive a packet?

b) A is using a sliding window protocol to communicate with B. What is the minimum window size A should use for the link to be fully utilized?

Answer

a) 16ms

Total delay = propagation delay + transmission delay

Propagation delay =

distancepropagation speed=2000ร—1032.5ร—108=8ms

Transmission delay =

packet sizebandwidth (transmission rate)

We are not given bandwidth or transmission rate, but are given link with propagation delay of

800 bit times.

800 bit times refers to the time it takes to transmit 800 bits on the link.

propagation delay of

800 bit times means the propagation delay is the same as the time it takes to transmit 800 bits on the link. So, bandwidth =
8008ร—10โˆ’3=100000 bit per second

So, transmission delay =

100ร—8100000=8ms

Total delay =

16ms

b) 3

It takes 8ms to push 1 packet onto the link, and another 8ms to propagate to B. During the 8ms of propagating, A can send another packet. It takes 16ms for the ACK from B to reach A, so during this 16ms, A can also send packets.

Total free time = 8ms + 16ms = 24ms.

1 seconds can send 100k bits. So, 24ms can send 2400 bits = 300 bytes = 3 packets.

Q6

The diagram below shows a small network with five entities: hosts A and B are connected to a router R through a switch S. Host C connects to R directly. There is no other host, switch, or router in the network.

image

a) What is the maximum number of entries that could be in the switching table of S?

b) What is the maximum number of entries that could be in the ARP table of A?

c) What is the maximum number of entries that could be in the ARP table of C?

d) How many IP addresses are used in this network?

Answer

a) 3 {A,B,C}

b) 2 {R,B}

c) 1 {R}

d) 5 {A,B,C,R have 2 for 2 subnet}

Q7

A node

x is part of a network running distance vector routing protocol.
x
has three entries in its routing table:

Destination Cost Next Hop
w
4
w
y
ฮฑ
z
x
ฮฒ
w

ฮฑ and
ฮฒ
are two unknown values (unknown to you, but known to
x
). Assume that the distance vector routing protocol has converged and the minimum cost from
x
to every other node has been found. We denote
c(x,y)
as the link cost between
x
and
y
, and
dx(y)
as the cost of the minimum cost path from
x
to
y
. The link cost is a positive integer.

We know that

c(x,w) is 4, and
c(x,z)
is 10.

a) What is the minimum possible value for

ฮฑ?

b) What is the value for

dw(z)?

Answer

a) 11

b) 6

We can visualise

w,x,y,z as follows







%0



x

x



w

w



x->w

4



z

z



x->z

10



w->z




y

y



z->y




Then

ฮฑ=c(x,z)+c(z,y)=10+c(z,y), so the minimum value of
ฮฑ
will be 11.

Notice that when the destination is

z, the router choose to go through
w
, this means
dx(z)=c(x,w)+c(w,z)โ‰คc(x,z)
.

But at the same time, when the destination is

y, router choose to go through
z
instead of
w
first. So,
dx(y)=c(x,z)+c(z,y)โ‰คc(x,w)+c(w,z)+c(z,y)โŸนc(x,z)โ‰คc(x,w)+c(w,z)
.

Combining, both conditions,

c(x,z) must be equal to
c(x,w)+c(w,z)
. So
dw(z)=c(w,z)=6
.

AY1516 S2 Final

Q1.9

Host A and B are connected by a NAT-enabled router R as shown in the following diagram. Suppose A sends a packet to host B and B replies with a packet. What is the destination IP address and MAC address in the packet replied by B?

image

A. Dest IP address: 102.33.17.1; dest MAC address: E6-E9-00-17-BB-4B

B. Dest IP address: 102.33.17.1; dest MAC address: CC-49-DE-D0-AB-7D

C. Dest IP address: 192.168.2.3; dest MAC address: E6-E9-00-17-BB-4B

D. Dest IP address: 192.168.2.3; dest MAC address: CC-49-DE-D0-AB-7D

E. Dest IP address: 192.168.2.1; dest MAC address: CC-49-DE-D0-AB-7D

Answer

B

Since this is through a NAT-enabled router, Router R translates A's private IP address (192.168.2.3) into its public IP (102.33.17.1) when forwarding the packet to B. Therefore:

Source IP seen by B: 102.33.17.1 (Router R's public IP).
Destination IP seen by B: 102.33.17.17 (Host B's IP).