Assignment 2: CMPT 371


1) Consider a host running a IPv4 resolver and a local DNS server. Do not consider IPv6 AAAA
records. Assume the domain names given in A, B and C are hosts (not DNS servers). Assume
that only the following domains are delegated by the DNS server for the node above them.

ca. com. gov. halloween.ca. digital.com. sealife.gov. photos.digital.com.
fish.sealife.gov

Assume all other domains are not delegated.
Both the host and the server have recently been rebooted. The server has made three queries
since it was rebooted. The queries were for the A records for each of the following hosts. The
hosts (not running DNS servers) are listed in the order the queries are made.

A. scarey.costumes.halloween.ca
B. cameras.photos.digital.com.
C. perch.fish.sealife.gov.

Answers should all be in the form of DNS records for example
 NS record for each DNS server for domain fresh.fruit.gov.
 A record for each DNS server for domain favorit.color.ca.
 AAAA record for fish.shark.seafood.com.

a) [4 points] What DNS records would you expect to find in the cache of the local DNS
server after the queries to resolve the address for scarey.costumes.halloween.ca. had
been completed?
b) [3 points] Consider each of the following hosts. For each host answer the following two
questions.
 Which DNS server would be authoritative for each of the following hosts?
 Why is that DNS server you chose authoritative for the host?
I. Salmon.fish.sealife.gov.
II. slr.digital.cameras.edu.
III. childrens.costumes.halloween.ca.
c) [6 points] Assume trout.fish.sealife.gov has been delegated to by fish.sealife.gov. After
the three queries above for hosts A, B, C, an additional query for host
rainbow.trout.fish.sealife.gov. is made.
I. [2 points] What is the first DNS server queried? Why?
II. [2 points] What DNS record is the query requesting, in the query to the DNS
server in I.?
III. [2 points] What is returned by DNS query in II.?
d) [7 points] Assume that queries A, B, and C have been completed. Next queries X and Y
will occur.
Query X is apple.pear.sealife.gov.
Query Y is phones.cameras.digital.com.
For each of these two domains you will state:
 Which DNS server would be contacted first
 The number of iterative queries needed to obtain an answer to the query
 The item queried for
 The response expected from the query.


2) [15 points] Consider bit torrent as an example of a peer to peer application.













The host labeled X is has just joined the illustrated bit torrent. As indicated below the host it
is the newest host in the torrent. Answer the following questions. Each answer should be no
longer than three sentences.
a) How does host X obtain an initial list of potential peers?
b) What is the purpose of the tracker?
c) How does a potential peer from X’s list become a neighboring peer?
d) What does it mean to unchoke a peer?
e) What does it mean for a peer to be optimistically unchoked?


X
NEWEST HOST
IN TORRENT
tracker:

3) [45 points] You will write two Python (compatible with v3.7) socket programs to implement
a slightly modified version of the protocol (rdt3.0) from your text (that we will/have discussed
in class. These two processes will exchange simple packets that are used to implement the
protocol. Please note that the form of the packets has been changed from the example in
your textbook. This means that the arguments of the makepkt function in the figures must
be changed to a list of the variables in the fields of the packets described below. The
arguments of makepkt should be in the order Field1, Field2, Field3, Field4
Your program should run correctly on the windows workstation environment in the CSIL. If
they do not you will receive 0 for this program.

The contents of the simple packets you send between your sender (client) and receiver
(server) sockets will include 3 values.
 Field 1:
o Packet contents for a packet is a 32 bit random integer (data). (generated with a
random number generator)
o Packet contents for an ACK packets is 0
 Field 2: Sequence Number either 1 or 0 (integer)
o For a Packet it is a sequence number for the packet
o For an ACK it is the sequence number of the ACK
 Field 3: Is this an ACK? Boolean
True if the packet is an ACK, False if the packet is not an ACK
THERE SHOULD BE NO NACKs used in this problem.


RECEIVER

Waiting for
F0 from
below
Waiting for
F1 from
below
Received F0 or
Corrupted packet
Resend ACK0
Received F0
Extract data
Send data to app
Make ACK 0
Send ACK0
Received F1
Extract data
Send data to app
Make ACK 1
Send ACK1
Received F1 or
Corrupted packet
Resend ACK1



In your sender program you will
 Use one instance of a pseudo random number generator Random( ) to produce
uniformly distributed random floating point numbers in the range [0.0, 6.0). These pseudo
random numbers will be used to simulate random arrival time of packets in seconds.
When a packet is sent, the send is followed immediately by a call to this random number
generator. The pseudo random number returned will be interpreted as the delay in
seconds before the next packet will be generated. This delay occurs after the process
enters either “wait for call 0 from above” or “wait for call 1 from above”. It is the time
between entering one of these states and building the next packet (waiting for enough
data for a packet).
 Use a second instance of a pseudo random number generator Random() to generate
random number that will be used to determine if an ACK that has just arrived has been
corrupted. This instance of the pseudo random number generator random should
generate uniformly distributed pseudo random numbers between [0.0 and 1.0). If the
number generated is less that the input value of the probability that an ACK packet has
been be corrupted, then the ACK packet that has just arrived will be considered to be
corrupted.
 Use a third instance of a pseudo random number generator Random() to generate a
random integer in the range [25,100]. This number will the data you place in your packet
before you send it
SENDER
Received ACK1 or
Corrupted ACK
From initial state
IDLE 1
Waiting for
data from
application
Received ACK 0
Stop timer:
Make and Transmit
segment: F0
start timeout timer
Make and Transmit
segment: F1
start timeout timer
Receive ACK 1
Stop Timer:
WAIT
Waiting for
ACK 0
Timeout expired
Retransmit segment
Reset timeout timer
WAIT
Waiting for
ACK 1
Timeout Expired
Retransmit segment
Reset Timer
Received data from
above for
Segment F1
Received
Data from above
for segment F0
Received ACK 0 or
Corrupted ACK
IDLE 0
Waiting for
data from
application
 Read the values of the following quantities used in your program at the start of your
program. You will not read any quantities not in this list into your program. You will read
the specified quantities in the order they are specified below.
o The seed for the instance of the random number generator used for timing arrival
of data from the application
o The seed for the instance of the random number generator used for determining
if ACKs have been corrupted.
o The seed for the instance of the random number generator for generating the data
in the packet
o The number of packets to send
o The probability that an ACK has been corrupted. Between [0 and 1)
o The round trip travel time (to be used for the duration of the timeout timer that
expires if an ACK is not received)

 Print three messages immediately before a packet is sent.
o You must print the messages exactly as given (character by character), with the
sole exception of items in bold which will contain actual data values.
o First message: one of the four following messages should be printed
 A packet with sequence number 0 is about to be sent
 A packet with sequence number 1 is about to be sent
 A packet with sequence number 0 is about to be resent
 A packet with sequence number 1 is about to be resent
o Second message should be printed
 Packet to send contains: data = 123 seq = 0 isack=False
o Third message: one of the two following messages should be printed.
 Starting timeout timer for ACK0
 Starting timeout timer for ACK1

 Print the following messages immediately after an uncorrupted ACK packet is received.
o An ACK will be received. Print the message for the packet received followed by the
third message.
o You must print the messages exactly as given below, with the sole exception of
items in bold which will contain actual data values.
o First message: one of the two following messages should be printed.
 An ACK0 packet has just been received
 An ACK1 packet has just been received
o Second message should be printed
 Packet received contains: data = 0 seq = 1 isack= True
o Third message: one of the two following messages should be printed.
 Stopping timeout timer for ACK0
 Stopping timeout timer for ACK1



 Print the following messages immediately after a corrupted packet is received.
o You must print each message exactly as given below.
 A Corrupted ACK packet has just been received

 Print the following messages if a timer expires.
HINT:There are two reasons the timer may expire.
For a lost packet/ack the best way to handle this timeout is using the timeout
associated with the socket recv().
For a corrupted ack or an incorrect sequence number something will be received
before the timeout. You will need to check what is received, if it is a corrupted
ack or incorrect ack you will need to monitor the time until the timeout timer
expires then send your next packet.
You must print the message exactly as given below.
o One of the two following messages should be printed.
 ACK0 timeout timer expired
 ACK1 timeout timer expired

 Print the following messages immediately before the sender moves to another state
or returns to the same state.
o Only the appropriate one of the following messages should be printed for each
transition.
o These messages must be printed exactly as given below.
 The sender is moving to state WAIT FOR CALL 0 FROM ABOVE
 The sender is moving to state WAIT FOR CALL 1 FROM ABOVE
 The sender is moving back to state WAIT FOR CALL 0 FROM ABOVE
 The sender is moving back to state WAIT FOR CALL 1 FROM ABOVE
 The sender is moving to state WAIT FOR ACK0
 The sender is moving to state WAIT FOR ACK1
 The sender is moving back to state WAIT FOR ACK0
 The sender is moving back to state WAIT FOR ACK1




In your receiver program you will
 Use an instance of a pseudo random number generator random() to generate uniformly
distributed pseudo random numbers between [0.0 and 1.0). These pseudo random
numbers will be used to determine if a packet that has just arrived has been corrupted.
If the pseudo random number generated is less that the input value of the probability that
the packet has been be corrupted, then the packet that has just arrived will be considered
to be corrupted.



 Read the values of the following quantities used in your program at the start of your
program. You will not read any quantities not in this list into your program. You will read
the specified quantities in the order they are specified below.
o The seed for the random number generator used for determining if packets have
been corrupted.
o The probability that a packet has been corrupted

 Print the following messages immediately before an ACK is sent.
o One of the first two messages should be sent followed by the third message.
o You must print the messages exactly as given, with the sole exception of items in
bold which will contain actual data values.
 An ACK0 is about to be sent
 An ACK1 is about to be sent
 Packet to send contains: data = 29 seq = 0 isack = True

 Print the following messages immediately after an uncorrupted packet is received.
o One of the first four messages should be sent followed by the fifth message,
including the actual contents of the packet just received
o You must print the messages exactly as given, with the sole exception of items in
bold which will contain actual data values.
 A packet with sequence number 0 has been received
 A packet with sequence number 1 has been received
 A duplicate packet with sequence number 0 has been received
 A duplicate packet with sequence number 1 has been received
 Packet received contains: data 333 seq = 0 isack = False

 Print the following message immediately after a corrupted packet is received.
You must print the message exactly as given.
 A Corrupted packet has just been received

 Print the following messages Immediately before the sender moves to another state or
returns to the same state
o the appropriate one of the following messages should be printed
 The receiver is moving back to state WAIT FOR 0 FROM BELOW
 The receiver is moving back to state WAIT FOR 1 FROM BELOW
 The receiver is moving to state WAIT FOR 0 FROM BELOW
 The receiver is moving to state WAIT FOR 1 FROM BELOW


4) [20 points] Consider two hosts, host A and host B, connected by a point to point link.
 Messages cannot be lost as they travel through the point to point link.
 Messages can be corrupted as they travel through the point to point link.
 NACKs cannot be corrupted as they travel through the point to point link.
 NACKs cannot be lost as they travel through the point to point link
 Host A will deliver a message to host B. In response host B will deliver a message to host A. In
response Host A will deliver a message to host B, and so on.
 Each message contains a sequence number (either 0 or 1)
 When an uncorrupted message is received by host A host A will leave state “wait receive from B”.
Then host A will
o Extract and deliver the information in the packet to the application
o change the sequence number to 0.
o Set the 5 second timer
o Move into state “wait send to B”
 When an uncorrupted message is received by host B host B will leave state “wait receive from A”.
Then host B will
o change the sequence number to 1.
o Extract and deliver the information in the packet to the application
o Set the 5 second timer
o Move into state “wait send to A”
 When a corrupted message is received A NACK is sent.
 When a NACK is received the last packet sent is retransmitted. The sequence number of the
packet being retransmitted is not changed.
 Assume that after the data has been extracted from a packet the host must wait for 5 seconds
before building and sending the next message.
 The data needed to build the packets is always available when it is needed. This is an assumption
to simplify the problem. Do not worry if this assumption does not seem realistic

Draw a state machine for host A and another state machine for host B.
Use the following events and actions in your state diagrams.
 Receive packet (corrupt)
 Receive packet (not corrupt, sequence number)
 Build packet (sequence number)
 Send packet (Sequence number)
 Extract/Deliver packet data (sequence number)
 Set 5 second timer( )
 5 second timer expired()
 Send NACK (sequence number)
 Receive NACK (sequence number)
 Change sequence number(sequence number)


Use the following states in your state diagrams.
 Wait: receive from A
 Wait: send to A
 Wait: receive from B
 Wait: send to B
















































































































































































































































































































































































学霸联盟