Python代写 | CSE 434, SLN 11223 — Computer Networks

这个作业是用Python实现socket的通信
ARIZONA STATE UNIVERSITY
CSE 434, SLN 11223 — Computer Networks — Spring 2020
Instructor: Dr. Violet R. Syrotiuk
Socket Programming Project
Available Sunday 02/02/2020; group formation by Sunday, 02/09/2020
Milestone due Sunday 02/16/2020; full project due Sunday 03/01/2020
The purpose of this project is to implement your own application program in which processes communicate using
sockets to first build a distributed hash table (DHT) and then process queries using it.
• You may write your code in C/C++, in Java, or in Python; no other programming languages are permitted.
Each of these languages has a socket programming library that you must use for communication among
processes. Sample client and server programs that use sockets written in C will be provided as supplementary
materials. They will be discussed and demonstrated in class on Tuesday, 02/04/2020.
• This project may be completed individually or in a group of size at most two people. Whatever your choice,
you must join a SocketGroup under People on Canvas before Sunday, 02/09/2020. Each group must restrict
its use of port numbers as described in §2 to prevent application programs from interfering with each other.
• You must use a version control system as you develop your solution to this project, e.g., GitHub or similar.
Your code repository must be private to prevent anyone from plagiarizing your work. It is expected that you
will commit changes to your repository on a regular basis.
The rest of this project description is organized as follows. Following an overview of the DHT application and its
architecture in §1, the requirements of the DHT’s client-server protocol, and its peer-to-peer protocol are provided in
§1.1 and §1.2, respectively. Finally, §3 describes the requirements for the milestone and full project deadlines.
1 DHT: A Distributed Hash Table with Ring Overlay
As the name suggests, in a distributed hash table (DHT), the contents of a hash table are distributed across a number
of nodes in a network rather than storing the entire table at a single node. In this project, a ring overlay will be
imposed on the nodes implementing the DHT meaning that these nodes will be logically organized in a cycle. If you
are interested, you can see the more complex overlay topologies used in real DHT implementations such Chord [3],
Kademlia [2], and Tapestry [4].
DHT Server
Node 1
Leader
Node 0
Node 2
Local DHT
Local DHT
Local DHT
Logical ring
Query to DHT
State information
Message interaction with server
Figure 1: Architecture of the DHT application.
1
The architecture of the DHT application is illustrated in Figure 1. It shows the DHT server maintaining state
information about the system. Three users are organized in a logical ring. Together they implement the DHT with
each storing a subset of the records of the DHT locally. Two users are shown querying the DHT (the responses are not
shown). All peers interact with the server to establish the DHT, and to query it. Any request to query the DHT while
it is under construction or modification is denied. In general, DHTs support peers joining and leaving the overlay
structure. In this project, we will only implement nodes leaving the ring.
This socket programming project involves the design and implementation of two programs:
1. The first program implements an “always-on” server of a client-server protocol to support management of the
nodes implementing the DHT, among other functionality. Similar to the sample server code, your server should
read one integer command line parameter giving the port number at which the server listens. The messages to
be supported by the server are described in §1.1.
2. The second program implements the client-side of the client-server protocol, as well as the peer-to-peer protocol
to construct the DHT, and to query it. Similar to the sample client code, your process should read two command
line parameters, the first being a string representing the IPv4 address of the server in dotted decimal, and the
second being an integer port number at which the server is listening. The messages to be supported by peers
interacting with the server, and with other peers are described in §1.2.
1.1 The DHT Client-Server Protocol
Recall that a protocol defines the format and the order of messages exchanged between two or more communicating
entities, as well as the actions taken on the transmission and/or receipt of a message or other event [1]. This section
and the next describe all but the message format which you are to design; see §1.3.
The server process is started at an hIPv4-addressi and hporti. Once started it runs in an infinite loop,
listening to the given port for messages incoming from a client process. As users send messages, the server maintains
state about the DHT application. Users that register with the server may be in one of 3 states:
1. Free, a user able to participate in any capacity,
2. Leader, a user that leads the construction of the DHT, and
3. InDHT, a user that is one of the members of the DHT.
Users transition between states as commands are processed.
Commands are read from stdin at a client (no fancy UI is expected!). A client processes a command by constructing
a message to be sent to the server or to another peer over a UDP socket. Messages to the server always come
in pairs; i.e., after sending a message to the server, the client waits for a response before issuing its next command.
Messages sent among peers are described in §1.2.
The server must support messages corresponding to the following commands from a client:
1. register huser-namei hIPv4-addressi hporti, where user-name is an alphabetic string of length
at most 15 characters. This command registers a user with the server. All users must be registered prior to issuing
other any other commands to the server.
On receipt of a command to register, the server stores the name, IPv4 address, and one or more ports associated
with that user in a state information base. In addition the state of the user is set to Free.
If the parameters are unique, the server responds to the client with a return code of SUCCESS. Specifically, each
huser-namei may only be registered once. The hIPv4-addressi of a user need not be unique, i.e., one or more
processes may run on the same end host. However, the port(s) used for communication by each process must be
unique; see §1.1.1 for suggestions on implementation.
The server takes no action and responds to the client with a return code of FAILURE indicating failure register
the user due to a duplicate registration, or some other problem.
2. setup-dht hni huser-namei, where n ≥ 2 . This command initiates the construction of a DHT of size
n, with user-name as its leader. In this project, only one DHT may exist at any time (though in principle this
need not be the case).
2
This command results in a return code of FAILURE if:
• The user-name is not registered.
• n is not at least two.
• There are not at least n users registered with the server.
• A DHT has already been setup.
Otherwise, the server sets the state of user-name to Leader, and selects at random n−1 Free users from
those registered updating each one’s state to InDHT. The server returns a return code of SUCCESS and a list of
n users that together will construct the DHT. The n users are given by 3-tuples consisting of the user-name,
IPv4-address, and port, with the 3-tuple of the leader given first (the other tuples can be given in any
order). Receipt of SUCCESS at the leader involves several additional steps to accomplish the setup of the DHT,
as described in §1.2.1.
After responding with SUCCESS to a setup-dht, the server waits for dht-complete, returning FAILURE
to all incoming messages.
3. dht-complete huser-namei. Receipt of a dht-complete indicates that the leader has completed all
the steps required to setup the DHT. If the user-name is not the leader of the DHT then this command returns
FAILURE Otherwise, the server responds to the leader with SUCCESS. The server may now process any other
command except setup-dht (because we assume at most one DHT in the system).
4. query-dht huser-namei. This command is used to initiate a query of the DHT. It returns FAILURE if the
DHT setup has not been completed, the user is not registered, or the user is registered but is not Free. Otherwise,
the server chooses at random one of the n users maintaining the DHT and returns a 3-tuple corresponding
to its user-name, IPv4-address, and port to the user wishing to initiate a query the DHT. The return
code is also set to SUCCESS. Receipt of SUCCESS at the client involves several additional steps to process the
query, as described in §1.2.2.
5. leave-dht huser-namei. In general, a DHT is maintained by a set of processes that is dynamic. In this
project, we only support a process leaving the DHT. The leave-dht initiates the process of user-name
leaving the DHT. This command returns FAILURE if the user is not one maintaining the DHT, or the DHT does
not exist. Otherwise, the server responds to the user with SUCCESS and stores the user-name making the
request. The server waits for dht-rebuilt, returning FAILURE to all other incoming messages. Receipt of
SUCCESS at the client involves several steps to rebuild the DHT, as described in §1.2.3.
6. dht-rebuilt huser-namei hnew-leaderi, where new-leader is the user name of the leader of the
rebuilt DHT. Receipt of dht-rebuilt indicates that all the steps of removing user-name from maintaining
the DHT have been completed. If the user-name is not the same as that initiating the leave-dht then
return FAILURE. Otherwise, the server responds to the user with SUCCESS and sets the state of user-name
to Free. Rebuilding the DHT may have required the assignment of a new leader. If the Leader of the DHT is
not the user new-leader, then the state of the old leader is set to InDHT and the state of user new-leader
is set to Leader. The server may now process any other command (except setup-dht).
7. deregister huser-namei. This command removes the state of a Free user from the state information
base, allowing it to terminate. This command returns FAILURE if the user is a node maintaining the DHT.
Otherwise, the user’s state information is removed, and the server responds to the user with SUCCESS. The user
process then exits the application, i.e., it terminates.
8. teardown-dht huser-namei, where user-name is the leader of the DHT. This command initiates the
deletion of the DHT. This command returns FAILURE if the user is not the leader of the DHT. Otherwise, the
server responds to the leader with SUCCESS. Receipt of SUCCESS at the client involves several steps to delete
the DHT, as described in §1.2.4. The server waits for teardown-complete, returning FAILURE to all other
incoming messages.
3
9. teardown-complete huser-namei, where user-name is the leader of the DHT. This command indicates
that the DHT has been deleted. The server returns FAILURE if the user is not the leader of the DHT.
Otherwise, the server changes the state of each user involved in maintaining the DHT to Free. The server
responds to the former leader with SUCCESS.
1.1.1 Implementation Suggestions
Conceptually, a peer communicates with the server, it may ultimately query a peer in the DHT, and if it participates in
maintaining the DHT it sends messages to its right neighbour and receiving from its left neighbour. You may choose
to set up a separate socket for each such communication. In this case, you must use a different port for each socket, so
you should register multiple ports with the server for each user. Rather than registering a 3-tuple, you may decide to
register two additional ports, e.g.,
register huser-namei hIPv4-addressi hportf rom−lef ti hportto−righti hportqueryi
If you set up multiple sockets, you may consider using a different thread for handling each one. Alternatively a
single thread may loop, checking each socket one at a time to see if a message has arrived for the process to handle.
If you use a single thread, you must be aware that by default the function recvfrom() is blocking. This means that
when a process issues a recvfrom() that cannot be completed immediately (because there is no packet), the process
is put to sleep waiting for a packet to arrive at the socket. Therefore, a call to recvfrom() will return immediately
only if a packet is available on the socket. This may not be what you want.
You can change recvfrom() to be non-blocking, i.e., it will return immediately even if there is no packet. This
can be done by setting the flags argument of recvfrom() or by using the function fcntl(). See the man pages
for recvfrom() and fcntl() for details; be sure to pay attention to the return codes.
1.2 The DHT Peer-to-Peer (P2P) Protocol
A peer-to-peer (P2P) process can be a client of the server and also interact with other P2P nodes. Several commands
sent to the server involve several additional steps with peer processes on receipt of SUCCESS. Specifically, each
of setup-dht, query-dht, leave-dht, and teardown-dht involve additional steps, as described in the
following sections.
1.2.1 Creation of the DHT
The creation of a DHT is initiated by a setup-dht command sent by the leader process, to be maintained by n
processes in total. On receipt of SUCCESS, n 3-tuples are also included as Table 1 shows. The first 3-tuple is the user
name, IPv4 address, and port number of the process that sent the setup-dht command. This process serves as the
leader of the DHT, assigning itself an identifier of zero.
If you choose to use multiple sockets for communication (see §1.1.1) then rather than a 3-tuple, you may return a
5-tuple and associate the port numbers with different sockets.
Table 1: The n 3-tuples returned in a successful setup-dht command.
user0 IP-addr0 port0
user1 IP-addr1 port1
user2 IP-addr2 port2
.
.
.
.
.
.
.
.
.
usern−1 IP-addrn−1 portn−1
The leader then follows these steps to setup the DHT:
1. Assign identifiers and neighbours. First, a logical ring among the n processes must be set up. The processes
will be assigned identifiers 0, 1, . . . , n−1 because these will be used by the hash function to determine in which
local DHT to store a record. The leader has identifier 0. For i = 1, . . . , n − 1:
4
(a) The leader sends a command set-id to useri at IP-addri
, porti
. It also sends identifier i, the ring
size n, and the two 3-tuples (i − 1) mod n and (i + 1) mod n from Table 1.
(b) On receipt of a set-id, useri sets its identifier to i and the ring size to n. It stores the 3-tuple of
user(i−1) mod n to use as the address of its left neighbour. It stores the 3-tuple of user(i+1) mod n to use
as the address of its right neighbour.
Messages will always travel around the logical ring in one direction, received from the left neighbour and
forwarded to the right neighbour. After the end of this step, each of the processes has a unique identifier and
knows the address of its left and right neighbours.
2. Construct the local DHTs. Now, the leader populates the DHT. The dataset consists of a set of 241 records
in a CSV file named StatsCountry.csv. Each record consists of 9 fields related to countries of the world:
Country Code, Short Name, Table Name, Long Name, 2-alpha Code, Currency Unit, Region, WB-2 Code, and
Latest Population Census. The first line of the file consists of the column headers and is not part of the data.
For ` = 2, . . . , 241, the leader:
(a) The leader reads line ` from the dataset into a record; you will need to define the record structure.
(b) The leader computes the hash function using the Long Name as the key in two steps: First, as the sum of
the ASCII value of each character in the Long Name field of record `, modulo the local hash table size of
353 and, secondly, modulo the logical ring size n.
pos =


len(LongName
X
)
k=1
ASCII(LongN ame[k])

 mod 353
id = pos mod n
The second modulus yields a value id that is the identifer, 0 ≤ id ≤ n − 1, of the node in the logical ring
that must store the record (each record is stored in exactly one node in the DHT). The first modulus gives
the position in the local hash table of node id on the logical ring at which to store the record.
For example, sum of the ASCII values of the characters in the Long Name of the country Aruba is: (65 +
114 + 117 + 98 + 97) = 491. Taking this sum modulo the local hash table size 353 gives, 491 mod 353 =
138, the position to store the record in the local hash table. But the local hash table is determined by the
second modulus, i.e., modulo the ring size.
(c) If the hash function returns an id equal to the identifier of node i, 0 ≤ i ≤ n − 1, then node i stores the
record in its local hash table. For the example, if the logical ring has size n = 3, 138 mod 3 = 0 yields a
node identifier of 0. Hence the leader stores the record for Aruba in its local hash table at position 138.
If the id does not equal the identifier of node i, then node i sends a store command to its right neighbour,
along with the record. The record will be forwarded along the ring from the leader to node whose identifier
equals id, where it will be stored in the local hash table. In a correct implementation, a store command
never returns to the leader.
Do not have the leader send the store command directly to the node id. In DHTs the topology of the
DHT, here a ring, must be traversed.
On completion of this step, all of the records of the country statistics dataset will have been distributed across
the nodes that are working together to maintain the DHT.
3. The leader now sends a message for the dht-complete command to the server.
1.2.2 Querying the DHT
A query of the DHT is initiated by a query-dht command sent by a process with a user name u. Recall that the
server may return the 3-tuple of any the one of the processes involved in maintaining the DHT, i.e., the query process
can start at any node in the logical ring. On receipt of SUCCESS of the query-dht the process follows these steps:
5
1. The message returned to u from the server includes where to initiate the query. Therefore u sends a query
‘‘Long Name’’ to IPv4-address at port from the 3-tuple. The user receiving the query computes
the hash function of Long Name.
2. If the id equals the user’s identifier on the ring, it examines position pos in its local DHT to see if it holds the
record. If so, it returns SUCCESS, includes the entire record associated with Long Name to u; otherwise it
returns FAILURE.
3. If the id does not equal the user’s identifier on the ring, then the query message is forwarded to its right
neighbour for processing. The query message will be forwarded along the ring until the node whose identifier
matches id is encountered. When found, it examines position pos in its local DHT and responds as described in
step 2.
4. On receipt of a SUCCESS, the process issuing the query outputs the fields of the record, while on receipt of a
FAILURE it outputs that the record associated with Long Name is not found in the DHT.
Do not compute the identifier of the node to handle the query directly. The topology of the DHT, here a ring,
must be traversed to answer the query.
1.2.3 Leaving the DHT
As mentioned earlier, DHTs are maintained by a dynamic set of processes so existing implementations of DHTs allow
new nodes to join the maintenance of a DHT or leave the DHT. In this project, we only implement the latter, when a
leave-dht command is issued to the server by user u with identifier i. Naturally, this requires the DHT to be rebuilt
with n − 1 nodes. To accomplish this requires the following steps:
1. User u retains the 3-tuple of its right neighbour.
2. User u initiates a teardown of the DHT (see step 1 in §1.2.4). When the teardown propagates back to u, it
deletes its own local DHT.
3. A renumbering of identifiers is now initiated by u. A reset-id command is sent to its right neighbour setting
its identifier to zero, and the ring size to n − 1 (but not resetting the neighbours). The reset-id propagates
around the ring, with each node sending to its right neighbour, incrementing the node identifier when it forwards
the message. When a reset-id is received by u, it knows the identifiers of the nodes in the ring have been
renumbered, with its right neighbour becoming the leader of the new smaller ring of size n − 1.
4. User u now must reset one neighbour of each of its own left and right neighbours to remove itself from the logical
ring. This involves resetting the left neighbour of u’s right neighbour to u’s left neighbour, and resetting the right
neighbour of u’s left neighbour to u’s right neighbour. New commands reset-left and reset-right
should be introduced to accomplish the removal of u from the logical ring.
5. User u sends a command rebuild-dht to its right neighbour, i.e., the new leader of the smaller ring. Upon
receipt of the rebuild-dht, the new leader follows the steps in step 2 of §1.2.1 to construct the local DHTs
in the new ring of size n − 1.
6. The user u now sends a message for the dht-rebuilt command to the server with the new-leader specified
as its right neighbour.
1.2.4 Deletion of the DHT
The command tearddown-dht deletes the DHT. This is accomplished by the following steps:
1. The leader send a teardown command to its right neighbour. After each node deletes its local DHT, its
identifier, and its neighbour information, it forwards the teardown message to what was its right neighbour.
Hence the teardown propagates around the ring, deleting the DHT back to the leader.
2. On receipt of the teardown at the leader, it follow suits, and then sends a message for the teardown-complete
command to the server.
Be sure to make the implementation of teardown generic so that it can be used as part of the processing for the
leave-dht command; see step 2 of §1.2.3.
6
1.3 Defining Message Exchanges and Message Format
The previous sections §1.1 and §1.2 have described the order of many message exchanges, as well as the actions taken
on the transmission and/or receipt of a message. As part of this project, you will ultimately have to define these steps for
the set-id and store commands that are part of the setup-dht command, the query command that is part of
the query-dht command, the reset-id, reset-left, reset-right, and rebuild-dht commands that
are part of the leave-dht command, and the teardown command that is part of the teardown-dht command.
In addition, you will need to define the format of all messages used in client-server and in peer-to-peer communication.
This is often achieved by defining a structure with all the fields required by the command. For example, you
could define the name of the command as an integer field and interpret it accordingly. Alternatively, you may prefer
to define the command as a string. Indeed, any choice is fine so long as you are able to extract from a message and
interpret them.
You may want to define an upper bound on the size a local DHT as 353 (a prime number), and reasonable upper
bounds on the total number of registered users that your application supports, among others. It may also useful to
define meaningful return codes to differentiate SUCCESS and FAILURE.
2 Port Numbers
Both TCP and UDP use 16-bit integer port numbers to differentiate between processes. Both TCP and UDP define a
group of well known ports to identify well-known services. For example, every TCP/IP implementation that supports
FTP assigns well-known port of 21 (decimal) to the FTP server.
Clients on the other hand, use ephemeral, or short-lived, ports. These port numbers are normally assigned to the
client. Clients normally do not care about the value of the ephemeral port; the client just needs to be certain that the
ephemeral port is unique on the client host.
RFC 1700 contains the list of port number assignments from the Internet Assigned Numbers Authority (IANA).
The port numbers are divided into three ranges:
• Well-known ports: 0 through 1023. These port numbers are controlled and assigned by IANA. When possible
the same port is assigned to a given server for both TCP and UDP. For example, port 80 is assigned for a Web
server for both protocols, though all implementations currently use only TCP.
• Registered ports: 1024 through 49151. The upper limit of 49151 for these ports is new; RFC 1700 lists the
upper range as 65535. These port numbers are not controlled by the IANA. As with well-known ports, the same
port is assigned to a given service for both TCP and UDP.
• Dynamic or private ports: 49152 through 65535. The IANA dictates nothing about these ports. These are the
ephemeral ports.
In this project, each group G ≥ 1 is assigned a set of 500 unique port numbers to use in the following range. If
G mod 2 = 0, i.e., your group is even, then use the range:
G
2
× 1000
+ 1000,

G
2
× 1000
+ 1499
If G mod 2 = 1, i.e., your group is odd, then use the range:
G
2

× 1000
+ 500,
G
2

× 1000
+ 999
That is, group 1 has range [1500, 1999], group 2 has range [2000, 2499], group 3 has range [2500, 2999], group 4 has
range [3000, 3499], and so on.
Do not use port numbers outside your assigned range, as otherwise you may send messages to another group’s
server or peer process by accident and it is unlikely it will be able to interpret it correctly, causing spurious crashes.
7
3 Submission Requirements for the Milestone and Full Project Deadlines
All submissions are due before 11:59pm on the deadline date.
1. The milestone is due on Sunday, 02/16/2020. See §3.1 for requirements.
2. The full project is due on Sunday, 03/01/2020. See §3.2 for requirements.
It is your responsibility to submit your project well before the time deadline!!! Late projects are not accepted.
Do not expect the clock on your machine to be synchronized with the one on Canvas!
An unlimited number of submissions are allowed. The last submission will be graded.
3.1 Submission Requirements for the Milestone
For the milestone deadline, you are to implement the following commands to the server: register, setup-dht,
dht-complete, and query-dht. This also involves implementation of commands that may be issued among
peers that are associated with these commands; see §1.2.1 and §1.2.2.
Submit electronically before 11:59pm of Sunday, 02/16/2020 a zip file named Groupx.zip where x is your
group number. Do not use any other archiving program except zip.
Your zip file must contain:
1. Design document in PDF format. 50% Describe the design of your DHT application program. Include
a description your message format for each command implemented. Include a time-space diagram for each
command implemented to illustrate the order of messages exchanged between two or more communicating
entities, as well as the actions taken on the transmission and/or receipt of a message or other event. In addition,
describe your choice of data structures and algorithms used, and other design decisions such as the number of
sockets you chose to use.
2. Code and documentation. 50% Submit all well-documented source code implementing the milestone of your
DHT application. In addition, you must provide user documentation that describes how to compile and run your
program. For the milestone the code will be reviewed and the grader will attempt to run it.
You must provide output that traces the messages transmitted and received at the client/server/peer to
help understand the commands processed.
The milestone is worth 30% of the total project grade.
3.2 Submission Requirements for the Full Project
For the full project deadline, you are to implement the all commands to the server listed in §1.1. This also involves
implementation of all commands issued between peers that are associated with these commands as described in §1.2.
Submit electronically before 11:59pm of Sunday, 03/01/2020 a zip file named Groupx.zip where x is your
group number. Do not use any other archiving program except zip.
Your zip file must contain:
1. Design document in PDF format. 30% Describe the design of your DHT application program. Include
a description your message format for each command implemented. Include a time-space diagram for each
command implemented to illustrate the order of messages exchanged between two or more communicating
entities, as well as the actions taken on the transmission and/or receipt of a message or other event. In addition,
describe your choice of data structures and algorithms used.
2. Code, demo, and documentation. 70% Submit all well-documented source code implementing the milestone
of your DHT application. In addition, you must provide user documentation that describes how to compile and
run your program.
8
This will be evaluated by you demonstrating the functionality of your application to grader involving at least 4
different machines. You should strongly consider using the racks in BYENG 217 for this purpose. In addition,
you must provide user documentation that describes how to compile and run your program.
You must provide output that traces the messages transmitted and received at the client/server/peer to
help understand the commands processed.
References
[1] James Kurose and Keith Ross. Computer Networking, A Top-Down Approach. Pearson, 7th edition, 2017.
[2] Petar Maymounkov and David Mazieres. Kademlia: A peer-to-peer information system based on the XOR metric. `
In International Workshop on Peer-to-Peer Systems (IPTPS’02), LNCS Volume 2429, pages 53–62, 2002.
[3] Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, and Hari
Balakrishnan. Chord: A scalable peer-to-peer lookup protocol for Internet applications. IEEE/ACM Transactions
on Networking (TON), 11(1):17–32, 2003.
[4] Ben Y. Zhao, Ling Huang, Jeremy Stribling, Sean C. Rhea, Anthony D. Joseph, and John D. Kubiatowicz.
Tapestry: A resilient global-scale overlay for service deployment. IEEE Journal on Selected Areas in Communications
(JSAC), 22(1):41–53, 2004.
9