COMP3331/9331辅导、Computer Networks讲解、Java，C++，Python程序语言辅导 辅导留学生 Statistics
- 首页 >> Python编程 COMP3331/9331 Computer Networks and Applications
Assignment for Term 1, 2019
Individual Assignment
Version 1.1
Due: 26th April 2019
Updates to the assignment, including any corrections and clarifications, will be posted
on the course website (https://moodle.telt.unsw.edu.au/course/view.php?id=37585).
Please make sure that you check the course website regularly for updates. You can
post questions in the assignment forum.
1. Change Log
1. Version 1.0 released on Feb 18, 2018.
2. Goal and learning objectives
For this assignment, you will be asked to implement a part of the peer-to-peer (P2P)
protocol Circular DHT which is described in Section 2.6 of the text Computer
Networking (6th ed) and would be discussed in the lecture. A primary requirement for
a P2P application is that the peers form a connected network at all time. A complication
that a P2P network must be able to deal with is that peers can join and leave the
network at any time. For example, if a peer leaves the network suddenly (because it
has crashed), then the remaining peers must try to keep a connected network without
this peer. It is therefore necessary to design P2P networks so that they can deal with
these complications. One such method has been described in Section 2.6 of the text,
under the heading of Peer Churn for circular DHT. You will also learn how to implement
reliable data transmission over UDP.
2.1. Learning Objectives
On completing this assignment, you will gain sufficient expertise in the following
skills:
1. Understanding of routing mechanism and connectivity maintenance in peerto-peer
systems, and Circular DHT in particular.
2. Socket programming for both UDP and TCP transport protocols.
3. Protocol and message design for applications.
4. Basic understanding of creating a reliable connection.
3. BackgroundThe following is extracted from the Peer Churn section of the text:
“In P2P systems, a peer can come or go without warning. Thus, when designing a
DHT, we also must be concerned about maintaining the DHT overlay in the presence
of such peer churn. To get a big-picture understanding of how this could be
accomplished, let’s once again consider the DHT in Figure 2.27(a) [Reproduced here
as Figure 1]. To handle peer churn, we will now require each peer to track (that is,
know the IP address of) its first and second successor; for example, peer 4 now tracks
both peer 5 and peer 8. We also require each peer to periodically verify that its two
successors are alive (for example, by periodically sending ping messages to them and
asking for responses). Let’s now consider how DHT is maintained when a peer
abruptly leaves. For example, suppose peer 5 in Figure 2.27(a)[Figure 1 in this
assignment spec] abruptly leaves. In this case, the two peers preceding the departed
peer (4 and 3) learn that 5 has departed, since it no longer responds to ping messages.
Peers 4 and 3 thus need to update their successor state information. Let’s consider
how peer 4 updates its state:
1. Peer 4 replaces its first successor (peer 5) with its second successor (peer 8).
2. Peer 4 then asks its new first successor (peer 8) for the identifier and IP
addresses of its immediate successor (peer 10). Peer 4 then makes peer 10 its
second successor.
Having briefly addressed what has to be done when a peer leaves, let’s now consider
what happens when a peer wants to join the DHT. Let’s say a peer with identifier 13
wants to join the DHT, and at the time of joining, it only knows about peer 1’s existence
in the DHT. Peer 13 would first send peer 1 a message, saying ”what will be peer 13’s
predecessor and successor?” This message gets forwarded through the DHT until it
reaches peer 12, who realises it will be peer 13’s predecessor and its current
successor, peer 15, will become its successor. Next, peer 12 sends this predecessor
and successor information to peer 13. Peer 13 can now join the DHT by making peer
15 its successor and by notifying peer 12 that it should be its immediate successor to
peer 13.
Figure 1. DHT configuration.
4. Assignment description
For this assignment, you are asked to write a Java, C, or Python program which can
handle query/response and peer churn (leaving only) for circular DHT as described in
Section 3. However, there are a few important points that you need to note:1. You will be running each peer in an xterm on one machine. Therefore, tracking
a peer no longer means knowing the IP address but in your case, it means
knowing the port numbers (we will further elaborate on this point later).
2. You will not be able to use built in ping in OS to determine whether the two
successors of a peer are still alive. You will need to implement your own ping
mechanism.
Please make sure that your P2P program is working in the CSE laboratory as we
will test (and mark) your assignment using CSE machines.
If your program does not work on CSE machine, you will get ‘0’ mark for
assignment as we cannot accept running the code on your own machine.
In the following description, we will continue to use the example in Figure 1, but a very
important point that you need to note is that: you should not make any assumption
regarding the number of peers and their identities in your program. The number of
peers and their identities to be used for the evaluation can change from student to
student. You should therefore make sure that you test that your program can deal with
the general situation. You can assume that there would be no more than 10 peers and
the peer identities is within the range of 0-255.
There are a number of mandatory requirements:
1. You must name your program cdht.c, cdht.java, or cdht.py.
2. This program uses 5 input arguments. The first three input arguments are all
integers in the range of [0,255]. The fourth input is an integer value. And the
final input is a value in the range of [0,1]. They are used to initialise the network
as discussed in section 4.1 (initialization step).
3. For python programs, please indicate the version of python you used clearly in
the first lines of your report.
4. For c programs, please include makefile with your submission and explain the
process for making the file in your report. You must also show this on your
demo.
4.1. Assignment specification
In this section, we will discuss the steps that you must take to implement this
assignment. Make sure your program covers all these steps to get full mark. The
marking guideline is discussed in section 7.
Step 1: Initialization
The main aim of this step is to initialize the DHT. For the example in Figure 1, which
has 8 peers, 8 xterms will be open to initialise 8 peers. This step will be performed by
using a set-up script, of which the following is an example:This script opens up 8 xterms and starts a peer in each xterm. The -e option asks the
xterm to execute the command specified after the switch (For meaning of the other
xterm options, please use man xterm).
In order to understand what the input arguments represent, let us look at the first line
more closely. The executable part of this line is “java cdht 1 3 4 400 0.1”.
The first input argument, i.e., 1” is the identity of the peer to be initialised. The second
and third arguments, i.e., 3 and 4, are the identities of the two successive peers. The
forth argument is Maximum Segment Size (MSS) used to determine the size of the
data that must be transferred in each segment (discussed more in Step 3). MSS in
this example is set to 400. The last argument is the drop probability which must be
between 0-1 (discussed more in Step 3). You will find that the above file initialises the
configuration of the circular DHT given in Figure 1. The above configuration file is
available from the assignment website. There are also C and Python versions.
Given the above set-up script, each peer will know its identity and the identities of its
two successors. There are a few assumptions that you can safely assume:
1. We will ask you to work with at most 10 peers.
2. The minimum number of peers is 4.
3. The identity of a peer is always in the range of [0,255].
4. The set-up script that we give you will always correctly describe a circular
DHT.
You can always create more set-up scripts for testing. Although for the demo (see
Section 5) you will run your code with the above configuration, but we will also test
your code with another configuration that we have to ensure that you did not hardcode
anything in the program. You would not know that configuration, but the configuration
will follow the above rules. Thus, make sure you test your code with different
configurations.
Step 2: Ping successors
After initialisation, each peer will start pinging its two successors to see whether they
are alive. The ping mechanism should define two types of messages: 1) ping request,
and 2) ping response. The ping messages should use UDP protocol. You can assume
that a peer whose identity is i will listen to the UDP port 50000 + i for ping messages.
For example, peers 4 and 12 will listen on UDP ports 50004 and 50012 respectively
for ping request messages. Each peer should output a line to the terminal when a ping
request message is received from any of its two predecessors. For example, peer 10
is expected to receive ping request messages from peers 5 and 8; when peer 10
receives a ping request message from peer 5, it should output the following line to the
terminal:A ping request message was received from Peer 5.
Similarly, if peer 10 receives a ping request message from peer 8, it should output the
following line to the terminal:
A ping request message was received from Peer 8.
The numbers ”5” and ”8” are correct for this example, your program is of course
expected to print the correct identities for the situation.
NOTE: Printing ping messages to the terminal is highly important as the evaluator will
mark you according to the outputs. So, if no output is printed, the evaluator will assume
that the ping was unsuccessful. Even if you implement the ping correctly but there is
no output, you will get 10% of the mark for that part (see Section 7).
Since the title of each xterm displays the identity of each peer, you should be able to
keep track of each peer. When a peer receives a ping request message from another
peer, it should send a ping response message to the sending peer so that the sending
peer knows that the receiving peer is alive. When a peer receives a ping response
from another peer, it should display on the terminal. For example, if peer 10 is still
alive, peer 5 is expected to receive a ping response message from peer 10, and peer
5 should display:
A ping response message was received from Peer 10.
It is important to note that the messages displayed in the terminal should differentiate
between ping request and ping response messages.
You will need to decide on how often you send the ping messages. You should not
send them very often, otherwise you may overwhelm the computer. Please don’t make
the evaluator waiting for more than 3 minutes before it shows the output. Otherwise it
will be assumed that the program does not work.
Step 3: Requesting a file
An application of DHT is distributed file storage. In this step, you will be using the P2P
network that you have created to request for files. To request a file with filename X
from peer Y, the requester will type “request X” to the xterm of peer Y. Thus, your
program must be able to receive string inputs. Before describing what will be
evaluated, we first specify the rules for filenames, hashing, file location and messages:
Filename: You can assume all the filenames in this P2P system are four digit
numbers. Some examples of valid filename are 0000, 0159, 1890, etc.
Filenames such as a912 and 32134 are invalid because the former contains a
non-numeral character and the latter does not consist of exactly 4 numerals.
Hash function: All the peers in the network use the same hash function. Note
that you need to implement a simple hash function, so you do not need to use
conventional hash functions. The hash function will be applied to the filename.
Given the filename format defined earlier, each filename is an integer in the
range [0, 9999]. To compute the hash of a file, you must compute the remainder
of the filename integer when it is divided by 256. This gives you a hash value
as an integer in [0,255]. For example, for the file with filename 2012, its integer equivalent is 2012 and the remainder when 2012 is divided by 256 is 220; thus,
the hash of the file 2012 is 220.
? File location: The location where a file is stored in a P2P network depends on
the hash of the file as well as the peers that are currently in the network. The
rule is, for a file whose hash is n (where n is an integer in [0, 255]), the file will
be stored in the peer that is the closest successor of n. We will use the P2P
network in figure 1 to illustrate this rule. If the hash values of three different files
are 6, 10 and 210, then they will be stored, respectively, in peers 8, 10 and 1.
Request and response messages: If a peer wants to request for a file, the peer
(which we will call the requesting peer) will send a file request message to its
successor. The file request message will be passed round the P2P network
until it reaches the peer that has the file (which we will call the responding peer).
The responding peer will send a response message directly to the requesting
peer. We require both these messages, i.e., file request and response, to be
sent over TCP. You can assume that a peer whose identity is i will listen to the
TCP port 50000 + i for these messages.
Transfer the file: The responding peer has to transfer a file to the requesting
peer over UDP connection. Unlike ping packets, the file has to be sent directly
to the requesting peer. Recall that UDP is not reliable. You need to make the
connection reliable by implementing a simple protocol with stop-and-wait
behaviour. Recall that in stop-and-wait, the sender sends a data packet to the
receiver, and waits until it receives an acknowledgement, or a timeout happens.
In case an ACK is received, the sender sends the next part of data, and if a
timeout occurs, the sender re-transmits the data. Note that, this will be a very
simple reliable connection which only deals with packet lost. The responding
peer forms packet with MSS bytes of data. Then, it has to add the sequence
number, acknowledge number, and MSS, and encapsulate all as a packet. This
packet will then be transmitted to the requesting peer. The responding peer will
start a timer for the packet which essentially is needed for timeout operation.
Once the requesting peer received the data packet, it will generate a
corresponding acknowledgement and send back to the responding peer. On
receipt of the acknowledgement packet, the responding peer will transfer the
next MSS bytes of data. If the data packet gets lost, the requesting peer will not
transfer the acknowledgement (as no data is received) and thus the timeout will
happen in the responding peer. Recall that the responding peer maintains a
timer for each data packet it sends. The timeout-interval is set to 1 seconds in
this assignment. If the responding peer does not receive an acknowledgement
for the sent packet within timeout-interval, it considers the packet to be lost, and
thus have to re-transmit the packet.
The responding and requesting peers must maintains a log file named
responding_log.txt and requesting_log.txt where they record the information
about each segment they send and receive. The format of the log file shall be
as follow:
Assignment for Term 1, 2019
Individual Assignment
Version 1.1
Due: 26th April 2019
Updates to the assignment, including any corrections and clarifications, will be posted
on the course website (https://moodle.telt.unsw.edu.au/course/view.php?id=37585).
Please make sure that you check the course website regularly for updates. You can
post questions in the assignment forum.
1. Change Log
1. Version 1.0 released on Feb 18, 2018.
2. Goal and learning objectives
For this assignment, you will be asked to implement a part of the peer-to-peer (P2P)
protocol Circular DHT which is described in Section 2.6 of the text Computer
Networking (6th ed) and would be discussed in the lecture. A primary requirement for
a P2P application is that the peers form a connected network at all time. A complication
that a P2P network must be able to deal with is that peers can join and leave the
network at any time. For example, if a peer leaves the network suddenly (because it
has crashed), then the remaining peers must try to keep a connected network without
this peer. It is therefore necessary to design P2P networks so that they can deal with
these complications. One such method has been described in Section 2.6 of the text,
under the heading of Peer Churn for circular DHT. You will also learn how to implement
reliable data transmission over UDP.
2.1. Learning Objectives
On completing this assignment, you will gain sufficient expertise in the following
skills:
1. Understanding of routing mechanism and connectivity maintenance in peerto-peer
systems, and Circular DHT in particular.
2. Socket programming for both UDP and TCP transport protocols.
3. Protocol and message design for applications.
4. Basic understanding of creating a reliable connection.
3. BackgroundThe following is extracted from the Peer Churn section of the text:
“In P2P systems, a peer can come or go without warning. Thus, when designing a
DHT, we also must be concerned about maintaining the DHT overlay in the presence
of such peer churn. To get a big-picture understanding of how this could be
accomplished, let’s once again consider the DHT in Figure 2.27(a) [Reproduced here
as Figure 1]. To handle peer churn, we will now require each peer to track (that is,
know the IP address of) its first and second successor; for example, peer 4 now tracks
both peer 5 and peer 8. We also require each peer to periodically verify that its two
successors are alive (for example, by periodically sending ping messages to them and
asking for responses). Let’s now consider how DHT is maintained when a peer
abruptly leaves. For example, suppose peer 5 in Figure 2.27(a)[Figure 1 in this
assignment spec] abruptly leaves. In this case, the two peers preceding the departed
peer (4 and 3) learn that 5 has departed, since it no longer responds to ping messages.
Peers 4 and 3 thus need to update their successor state information. Let’s consider
how peer 4 updates its state:
1. Peer 4 replaces its first successor (peer 5) with its second successor (peer 8).
2. Peer 4 then asks its new first successor (peer 8) for the identifier and IP
addresses of its immediate successor (peer 10). Peer 4 then makes peer 10 its
second successor.
Having briefly addressed what has to be done when a peer leaves, let’s now consider
what happens when a peer wants to join the DHT. Let’s say a peer with identifier 13
wants to join the DHT, and at the time of joining, it only knows about peer 1’s existence
in the DHT. Peer 13 would first send peer 1 a message, saying ”what will be peer 13’s
predecessor and successor?” This message gets forwarded through the DHT until it
reaches peer 12, who realises it will be peer 13’s predecessor and its current
successor, peer 15, will become its successor. Next, peer 12 sends this predecessor
and successor information to peer 13. Peer 13 can now join the DHT by making peer
15 its successor and by notifying peer 12 that it should be its immediate successor to
peer 13.
Figure 1. DHT configuration.
4. Assignment description
For this assignment, you are asked to write a Java, C, or Python program which can
handle query/response and peer churn (leaving only) for circular DHT as described in
Section 3. However, there are a few important points that you need to note:1. You will be running each peer in an xterm on one machine. Therefore, tracking
a peer no longer means knowing the IP address but in your case, it means
knowing the port numbers (we will further elaborate on this point later).
2. You will not be able to use built in ping in OS to determine whether the two
successors of a peer are still alive. You will need to implement your own ping
mechanism.
Please make sure that your P2P program is working in the CSE laboratory as we
will test (and mark) your assignment using CSE machines.
If your program does not work on CSE machine, you will get ‘0’ mark for
assignment as we cannot accept running the code on your own machine.
In the following description, we will continue to use the example in Figure 1, but a very
important point that you need to note is that: you should not make any assumption
regarding the number of peers and their identities in your program. The number of
peers and their identities to be used for the evaluation can change from student to
student. You should therefore make sure that you test that your program can deal with
the general situation. You can assume that there would be no more than 10 peers and
the peer identities is within the range of 0-255.
There are a number of mandatory requirements:
1. You must name your program cdht.c, cdht.java, or cdht.py.
2. This program uses 5 input arguments. The first three input arguments are all
integers in the range of [0,255]. The fourth input is an integer value. And the
final input is a value in the range of [0,1]. They are used to initialise the network
as discussed in section 4.1 (initialization step).
3. For python programs, please indicate the version of python you used clearly in
the first lines of your report.
4. For c programs, please include makefile with your submission and explain the
process for making the file in your report. You must also show this on your
demo.
4.1. Assignment specification
In this section, we will discuss the steps that you must take to implement this
assignment. Make sure your program covers all these steps to get full mark. The
marking guideline is discussed in section 7.
Step 1: Initialization
The main aim of this step is to initialize the DHT. For the example in Figure 1, which
has 8 peers, 8 xterms will be open to initialise 8 peers. This step will be performed by
using a set-up script, of which the following is an example:This script opens up 8 xterms and starts a peer in each xterm. The -e option asks the
xterm to execute the command specified after the switch (For meaning of the other
xterm options, please use man xterm).
In order to understand what the input arguments represent, let us look at the first line
more closely. The executable part of this line is “java cdht 1 3 4 400 0.1”.
The first input argument, i.e., 1” is the identity of the peer to be initialised. The second
and third arguments, i.e., 3 and 4, are the identities of the two successive peers. The
forth argument is Maximum Segment Size (MSS) used to determine the size of the
data that must be transferred in each segment (discussed more in Step 3). MSS in
this example is set to 400. The last argument is the drop probability which must be
between 0-1 (discussed more in Step 3). You will find that the above file initialises the
configuration of the circular DHT given in Figure 1. The above configuration file is
available from the assignment website. There are also C and Python versions.
Given the above set-up script, each peer will know its identity and the identities of its
two successors. There are a few assumptions that you can safely assume:
1. We will ask you to work with at most 10 peers.
2. The minimum number of peers is 4.
3. The identity of a peer is always in the range of [0,255].
4. The set-up script that we give you will always correctly describe a circular
DHT.
You can always create more set-up scripts for testing. Although for the demo (see
Section 5) you will run your code with the above configuration, but we will also test
your code with another configuration that we have to ensure that you did not hardcode
anything in the program. You would not know that configuration, but the configuration
will follow the above rules. Thus, make sure you test your code with different
configurations.
Step 2: Ping successors
After initialisation, each peer will start pinging its two successors to see whether they
are alive. The ping mechanism should define two types of messages: 1) ping request,
and 2) ping response. The ping messages should use UDP protocol. You can assume
that a peer whose identity is i will listen to the UDP port 50000 + i for ping messages.
For example, peers 4 and 12 will listen on UDP ports 50004 and 50012 respectively
for ping request messages. Each peer should output a line to the terminal when a ping
request message is received from any of its two predecessors. For example, peer 10
is expected to receive ping request messages from peers 5 and 8; when peer 10
receives a ping request message from peer 5, it should output the following line to the
terminal:A ping request message was received from Peer 5.
Similarly, if peer 10 receives a ping request message from peer 8, it should output the
following line to the terminal:
A ping request message was received from Peer 8.
The numbers ”5” and ”8” are correct for this example, your program is of course
expected to print the correct identities for the situation.
NOTE: Printing ping messages to the terminal is highly important as the evaluator will
mark you according to the outputs. So, if no output is printed, the evaluator will assume
that the ping was unsuccessful. Even if you implement the ping correctly but there is
no output, you will get 10% of the mark for that part (see Section 7).
Since the title of each xterm displays the identity of each peer, you should be able to
keep track of each peer. When a peer receives a ping request message from another
peer, it should send a ping response message to the sending peer so that the sending
peer knows that the receiving peer is alive. When a peer receives a ping response
from another peer, it should display on the terminal. For example, if peer 10 is still
alive, peer 5 is expected to receive a ping response message from peer 10, and peer
5 should display:
A ping response message was received from Peer 10.
It is important to note that the messages displayed in the terminal should differentiate
between ping request and ping response messages.
You will need to decide on how often you send the ping messages. You should not
send them very often, otherwise you may overwhelm the computer. Please don’t make
the evaluator waiting for more than 3 minutes before it shows the output. Otherwise it
will be assumed that the program does not work.
Step 3: Requesting a file
An application of DHT is distributed file storage. In this step, you will be using the P2P
network that you have created to request for files. To request a file with filename X
from peer Y, the requester will type “request X” to the xterm of peer Y. Thus, your
program must be able to receive string inputs. Before describing what will be
evaluated, we first specify the rules for filenames, hashing, file location and messages:
Filename: You can assume all the filenames in this P2P system are four digit
numbers. Some examples of valid filename are 0000, 0159, 1890, etc.
Filenames such as a912 and 32134 are invalid because the former contains a
non-numeral character and the latter does not consist of exactly 4 numerals.
Hash function: All the peers in the network use the same hash function. Note
that you need to implement a simple hash function, so you do not need to use
conventional hash functions. The hash function will be applied to the filename.
Given the filename format defined earlier, each filename is an integer in the
range [0, 9999]. To compute the hash of a file, you must compute the remainder
of the filename integer when it is divided by 256. This gives you a hash value
as an integer in [0,255]. For example, for the file with filename 2012, its integer equivalent is 2012 and the remainder when 2012 is divided by 256 is 220; thus,
the hash of the file 2012 is 220.
? File location: The location where a file is stored in a P2P network depends on
the hash of the file as well as the peers that are currently in the network. The
rule is, for a file whose hash is n (where n is an integer in [0, 255]), the file will
be stored in the peer that is the closest successor of n. We will use the P2P
network in figure 1 to illustrate this rule. If the hash values of three different files
are 6, 10 and 210, then they will be stored, respectively, in peers 8, 10 and 1.
Request and response messages: If a peer wants to request for a file, the peer
(which we will call the requesting peer) will send a file request message to its
successor. The file request message will be passed round the P2P network
until it reaches the peer that has the file (which we will call the responding peer).
The responding peer will send a response message directly to the requesting
peer. We require both these messages, i.e., file request and response, to be
sent over TCP. You can assume that a peer whose identity is i will listen to the
TCP port 50000 + i for these messages.
Transfer the file: The responding peer has to transfer a file to the requesting
peer over UDP connection. Unlike ping packets, the file has to be sent directly
to the requesting peer. Recall that UDP is not reliable. You need to make the
connection reliable by implementing a simple protocol with stop-and-wait
behaviour. Recall that in stop-and-wait, the sender sends a data packet to the
receiver, and waits until it receives an acknowledgement, or a timeout happens.
In case an ACK is received, the sender sends the next part of data, and if a
timeout occurs, the sender re-transmits the data. Note that, this will be a very
simple reliable connection which only deals with packet lost. The responding
peer forms packet with MSS bytes of data. Then, it has to add the sequence
number, acknowledge number, and MSS, and encapsulate all as a packet. This
packet will then be transmitted to the requesting peer. The responding peer will
start a timer for the packet which essentially is needed for timeout operation.
Once the requesting peer received the data packet, it will generate a
corresponding acknowledgement and send back to the responding peer. On
receipt of the acknowledgement packet, the responding peer will transfer the
next MSS bytes of data. If the data packet gets lost, the requesting peer will not
transfer the acknowledgement (as no data is received) and thus the timeout will
happen in the responding peer. Recall that the responding peer maintains a
timer for each data packet it sends. The timeout-interval is set to 1 seconds in
this assignment. If the responding peer does not receive an acknowledgement
for the sent packet within timeout-interval, it considers the packet to be lost, and
thus have to re-transmit the packet.
The responding and requesting peers must maintains a log file named
responding_log.txt and requesting_log.txt where they record the information
about each segment they send and receive. The format of the log file shall be
as follow: