In this programming assignment, you will practice peer-to-peer network programing. Based on the experiences of socket and multi-thread programming youve learnt from the previous assignment; you will implement a simplified Gnutella-like P2P system. By the end of it, you should understand the concepts and programming constructs necessary to implement a P2P protocol and/or application program. This assignment does not require final coding. But you need to record the whole design process. Eventually, you need to describe your design of the system with (1) flowchart diagram, and (2) pseudocode (assume use object-oriented programming such as Java or C++). Deliverables You should hand in a report which presents your design, including (1) description of your design, (2) program flowchart diagram which can illustrates your design effectively, (3) challenges you solved, lessons you learnt, or anything else you want to express, and (4) pseudocode that implement the design. Total Marks: 100 --------------------------------------------------------------------------- 1. Review of P2P Networks P2P Introduction As we have learned in class, Peer-to-peer (P2P) networks/applications organize and manage resources at the edges of the Internet in a decentralized manner, with little or no interaction with centralized servers. The resources may be storage or content (e.g. file sharing applications), processor cycles (e.g. the SETI framework or other programs which use your computer to perform part of some large, distributed task when it is idle), or human presence (e.g. instant messaging). The 'edges' of the Internet are machines such as the average home PC which has just a single line (dial-up, DSL, cable, etc.) to connect it to the vast Internet 'cloud.' In a traditional client/server setup, your home PC acts as a client and sends requests to machines-- servers- - somewhere inside the cloud of the Internet to get things done: e.g., browsing the web or getting email. In a P2P paradigm, on the other hand, your home PC (for example) may connect, through the Internet, directly to tens or hundreds of other home PCs (or other machines at the 'edge') in order to share information and data. Because such resources at the edge of the Internet tend to be ephemeral (they may connect and disconnect many times repeatedly in a day), P2P protocols have to operate in an "environment of unstable connectivity and unpredictable IP addresses" P2P vs. Client/Server Unlike a server/client architecture where you develop applications in two asymmetrical pieces -- the server, which provides services and is assumed to be reliably available at a known Internet address, and the client which connects to the server in order to request information -- P2P applications seem a bit trickier to develop. In a P2P system, all machines (nodes) are running the same program (this is somewhat of a generalization: some systems are organized so groups of P2P nodes are running similar but different programs). Some of the issues that need to be handled in such a situation include: Connectivity: how to find and connect other P2P nodes that are running in the network (unlike traditional servers, they don't have a fixed, known IP address) Instability: nodes may always be joining and leaving the network (unlike servers-- web, email, etc., which we usually depend on to "be there") Message routing: how messages should be routed to get from one node to another (where the two nodes may not directly know about each other) Searching (somewhat related to routing): how to find desired information from the nodes connected to the network Gnutella P2P System. In this project, we are going to implement a simplified Gnutella system. Therefore, you should get familiar with the Gnutella system first. Gnutella falls into the class of pure P2P; peers in the network are joined by point-to-point connections to a set of neighboring peers to form an unstructured overlay. These point-to-point connections in Gnutella are maintained using predefined messages described by the Gnutella protocol (table 1). Type Description Contained information Ping Used to actively discover hosts on the network. A peer receiving a Ping descriptor is expected to respond with one or more Pong descriptors. None Pong The response to a Ping. Includes the address of a connected Gnutella peer and information regarding the amount of data it is making available to the network. IP address and port number of the responding peer; number and total kB of files shared Query The primary mechanism for searching the distributed network. A peer receiving a Query descriptor will respond with a QueryHit if a match is found against its local data set. Minimum network bandwidth of responding peer; search criteria QueryHit The response to a Query. This descriptor provides the recipient with enough information to acquire the data matching the corresponding Query. IP address, port number, and network bandwidth of responding peer; number of results and result set Push A mechanism that allows a firewalled peer to contribute file-based data to the network Peer identifier; index of requested file; IP address and port to send file to Table 1: The message types in the Gnutella protocol Note: Table 1 is the actual Gnutella protocol message. In this assignment, you only need to implement a simplified version and part of the functionalities. In particular, you will need to implement a modified Ping, Pong, Query, and QueryHit, you dont need to implement Push. 2. Implementation You are required to implement a Gnutella-like P2P search application. Users can use your application to join a P2P system and search resources in the system. In this assignment, the resources are simply represented by keywords. Therefore, each peer is in charge of a few keywords. A user can search keywords, a peer who has the keyword will respond with a QueryHit. You should implement the network formation (using ping and Pong), resource search (query and query hit). Before diving into the details of actual code, you should understand what we are trying to implement at a high-level. The figure below illustrates how conversations happen between peers in a network. Each application running on a peer that provides an interface to the user (you and I), and is simultaneously running a "main loop" that listens for incoming connections/requests from other peers. User Interface Main Loop Request Handle Ping Query Pong QHit User Interface Main Loop Request Handle Ping Query Pong QHit Peer1 Peer2 1. User clicks search 3. Peer2 calls the Query request handler 4. Query request search the query locally and forward the request to neighbor peers 6. Peer1 calls the QHit request handler In the figure, a scenario is diagrammed where the user on Peer 1 clicks a button, for example, a "Search" button, in the GUI interface. The interface somehow decides to send a "Query" message to another peer, in this case, Peer 2. The main loop of Peer 2 detects the incoming request (step 3) and handle the actual data of the request based on its type (step 3). In step 4, the "Query request handle of Peer 2 calls an appropriate function/method to handle the request, in this case check its local resource, and forward the query request to its neighbors if TTL >0. After processing the query, peer2 may need to send or forward a "QueryHit" message back to Peer 1. Again, Peer1's main loop, listening for request and starts its separate handler to process this request/message, and the process continues... In order to join the Gnutella P2P network a peer has to contact a known member of the network and request to establish a Gnutella protocol connection to the remote peer. Once connected to the network, new peers learn about other nodes through the protocol message they receive from the network. Initial discovery of known peers in the network is not part of the protocol definition, (though some out-ofnetwork means such as downloading a predefined list of known peers from a server are popular methods). Once a Gnutella peer obtains an address for at least one known peer in the Gnutella network to try to initiate a TCP/IP connection, and next a Gnutella protocol connection request string is sent over the connection to the remote peer to establish the Gnutella connection. In your implementation, each peer has a file of known peer list. They can get known peer information from reading that file. These known peers have exactly the same functionality as other peers, but you can assume they are already in the network. In Gnutella system, A peer joining the network shares an area in its local storage by creating a list of files that are contained in the share space and evaluates queries it receives from the network against the inverted list. In this assignment, you dont need to share files. Instead, each peer only maintains a word list, and it evaluates queries it receives from the network against the word list. Gnutella uses TCP as its underlying transport protocol but it is abstracted by an application level protocol which describes how peers communicate. Each message in the network always has a message type (Ping, Pong, Query, and QueryHit). Each message is assigned unique identifier so that a peer that has already seen a message before can ignore it (helps to avoid looping in the network). Messages also have a TTL (Time-To-Live) value and a hops count value which keeps track of the times the message has been forwarded. Messages received by a peer are forward to other peers that are connected to it, in this way message are flooded in the network to ensure it reaches it intended destination. Each peer has a Max Number of Neighbors parameter, to limit the number of neighbors a peer can have. Periodically, a peer sends Ping to its direct neighbors to maintain a UpToDate neighbor list. To control the scope of flooding of Gnutella messages, the TTL value is set specifying the number of times the message should be forwarded before it can be discarded. When a peer receives a ping message from a new peer in the network, it replies back with a pong message and decrements the TTL value of the message. The ping message is forwarded to other neighboring nodes which reply with a pong and decrement the TLL value. Once the TTL value of the message is zero, the message is dropped from the network. Distributed discovery of resources in the Gnutella P2P network works in much the same way as sending ping/pong message in the network; the initial query is generated by a peer and sent to neighbor peers directly connected to it, these neighbor peers evaluate and then forward the query to other neighbor peers. Peers that receive the query message evaluate it against its own data store and if they have resources that match the query respond back with a QueryHit message through the reverse path the query comes in. Please refer to the lecture notes for more information about Gnutella systems. About Flowchart and Pseudocode Flowchart: It is a type of diagram that represents a workflow or process. A flowchart can also be defined as a diagrammatic representation of an algorithm, a step-by-step approach to solving a task (Wikipedia). A flowchart can be great tool for both writing programs and explaining the program to others. Pseudo code: Its simply an implementation of an algorithm in the form of annotations and informative text written in plain English. It has no syntax like any of the programming language and thus cant be compiled or interpreted by the computer. You can google more on Flowchart and pseudocode for more instructions and tutorials. We will be flexible on flowchart representation and syntax of pseudo coding, but they should express the right logic of the program and it is easy to understand.