networking project

1

CPS 470/570: Computer Networks Project #1 due 11:55 pm, 2/13/2017 (100 pts)

No late submission will be accepted

Receive 5 bonus points if turn in the complete work without errors at least one day before deadline

Receive an F for this course if any academic dishonesty occurs

1. Purpose This homework builds an understanding of the Application Layer, Winsock programming,

and multithreaded programming.

2. Description Using Winsock and Visual Studio .NET 2013, your goal is to create a Gnutella crawler that

discovers all currently present peers in the system. Your program will first contact a seed web-

server to acquire a set of initial ultrapeers, traverse the entire Gnutella network in the BFS order,

and then record the identities of found ultrapeers and their children (i.e., leaf nodes) in some text

file. Using this information, you will then analyze the collected data to answer several questions

about geographic and domain diversity of peers as well as popularity of individual user agents

(i.e., client software).

Requirements for the implementation:

1. Must be able to connect to a GWebCache (specified at the command prompt using a URL

string host[:port][/path] where parts in [] are optional) and download a list of

active seed ultrapeers. Make sure to check that the status code of the response is 200 OK

and the protocol type in the first line of the response is indeed HTTP.

2. Must be able to use BFS to crawl the entire Gnutella network of ultrapeers starting from the seed list (each ultrapeer must be contacted no more than once, leaf nodes must not be

contacted at all). Make sure to check that the response begins with the correct string

compliant with the protocol (i.e., GNUTELLA/version statusCode statusText).

3. During the crawl, the program must record all found ultrapeers and their leaves into a set and then write it on disk at the end of the crawl (this set needs to contain unique elements

only).

4. The final version must support operation with N threads and crawls up to M contacted ul- trapeers, where both N and M are specified by the user in the command prompt (e.g.,

crawler.exe gwc1c.olden.ch.3557.nyud.net:8080/gwc/ 200 300000). For sim-

plicity, count each ultrapeer pulled from the BFS queue as “contacted.”

Requirements for the report:

1. Explain the structure of your code and what the crawler does. Document the various sta- tistics of your crawl – the total number of ultrapeers found, how many of them were re-

sponsive (accepted a connection), how many leaves were found, how long it took to per-

form the crawl, the average rate of crawling responsive ultrapeers per second.

2. Experiment with 10-5000 threads and document performance improvement arising from using multiple threads (e.g., using such metrics as the delay needed to crawl a certain

number of ultrapeers or the average number of peers found per second).

2

3. Perform reverse DNS lookups on all obtained IP addresses and build a distribution of the number of users per domain (e.g., the domain of host.network.cox.com is cox.com;

that of network.amazon.co.uk is amazon.co.uk). The distribution should be sorted

from the most popular to the least popular domain. Discuss how many domains you ob-

served, list several top domains, and show the number of users in each. If there are many

domains, you can assign sequence numbers in the plot instead of using their full names.

See Figure 1(a) for an example.

4. Map all users to their countries (e.g., domain blah.fr belongs to France) and build a dis- tribution of how many users from each country are represented in your crawl. See

http://www.iana.org/cctld/cctld-whois.htm for a list of all valid country codes. Sort the

countries by the number of found peers. See Figure 1(b) for an example. Note: you can

treat 3-letter and 4-letter domains (e.g., .com, .net, .edu, .biz, .info) as country codes.

5. Plot the distribution of user-agents used by the contacted ultrapeers using a pie-chart. You should treat different versions of the same agent (e.g., LimeWire 5.22 and 5.21) as

different agents. Figure 1(c) serves as a general guideline.

0

20000

40000

60000

80000

100000

120000

140000

fr de be us pl ru

country code

u s e rs

f o

u n

d

BearShare

LimeWire

Morph

Gnucleous

Figure 1. Sample homework graphs.

Delivery schedule:

1. The first part is due on1/24/17, Tuesday: your code must be able to connect to Gnutella cache webservers specified in the command line, download the initial seed, parse it, and

print the entire seed list on the screen.

2. The second part is due on 2/7/17, Tuesday: your code must be able to crawl the network using N (as least 50) threads. You must have all proper data structures in place (i.e., the

BFS queue, the set of all found peers, and the set of visited ultrapeers) and be able to

write the results into a file. Print all debugging information on screen: where you are

sending connection requests, entire response headers, what you have parsed from the re-

sponse and action taken for each returned peer.

3. The third part is due on 2/13/17, 11:55PM, Monday: do DNS lookups and write the re- port.

3. Details The current Gnutella network has a two-tier structure briefly explained in class. Ultrapeers

are long-lived (i.e., reliable) nodes that form a communication network (i.e., graph) among them-

selves for routing requests and aggregating information about the files shared by their children.

Ultrapeers usually maintain up to 30 neighbors and up to 30 children. Leaves on the other hand

only attach to 1-2 ultrapeers and do not allow search requests originating from other nodes to

0

10000

20000

30000

40000

50000

60000

70000

80000

90000

100000

1 2 3 4 5

domain sequence number

u s

e rs

f o

u n

d

coxcable.com 90000

verizon.net 87000

sbc.com 46700

att.com 22000

udayton.edu 1800

3

pass through them. For more information, see http://en.wikipedia.org/wiki/Gnutella or section

2.6 of the textbook.

Gnutella peers communicate with each other using standardized handshake messages de-

scribed in http://rfc-gnutella.sourceforge.net/src/rfc-0_6-draft.html. A summary of relevant sec-

tions of the protocol are provided below.

3.1. Seed File

For BFS search, your program must initially know at least one ultrapeer that is currently alive

in the system. This information can be downloaded from certain web caches that record the ad-

dresses of well-know users. These caches, called GWebCaches, collect identities of certain

Gnutella ultrapeers and make them available to external clients through a web interface.

To collect bootstrap information, send an HTTP request (you can do this manually using any

browser) to a GWebCache such as http://gwebcaches.pongwar.com/gnutella.html. This page

contains URLs of GWebCaches such as

gwcrab.sarcastro.com:8001/

grant1026.dyndns.ws/skulls0.2.8/skulls.php

gwc1c.olden.ch.3557.nyud.net:8080/gwc/

where, for example, the first URL decodes as following: gwcrab.sarcastro.com is the

hostname, 8001 is the port number on which the server is listening, and / is the directory. To re-

trieve lists of ultrapeers from GWebCaches, you must append a special string to the server's URL

that specifies the name of your client and the required action. Examples:

gwcrab.sarcastro.com:8001/?client=udayton0.1&hostfile=1

grant1026.dyndns.ws/skulls0.2.8/skulls.php?client=udayton0.1&hostfile=1

gwc1c.olden.ch.3557.nyud.net:8080/gwc/?client=udayton0.1&hostfile=1

where client=udayton0.1 specifies the name of your P2P client (in this example uday-

ton0.1 is being used) and hostfile=1 requests that a list of online peers be provided in the re-

sponse. Replies from web caches are composed of tuples IP:port separated by line breaks \r\n:

86.17.112.42:23694\r\n

67.180.41.229:6346\r\n

where 86.17.112.42 is the IP address and 23694 is the decimal port number of the first peer.

To communicate with a GWebCache node, you first need to resolve its hostname to an IP

address and then initiate a TCP connection on the corresponding port (if no port is provided, the

default HTTP port is 80). After establishing a connection, you need to send a GET request for

the directory in question. For gwcrab.sarcastro.com:

GET /?client=udayton0.1&hostfile=1 HTTP/1.0\n

Host: gwcrab.sarcastro.com\n \n

and wait for a reply. Standard HTTP response headers will follow from the server:

HTTP/1.1 200 OK\n

4

Connection: close\n

Date: Thu, 1 Sep 2006 12:00:15\n

Server: Apache/1.3.0\n

Content-type: text/html\n

Content-length: 456\n

\n

86.17.112.42:23694\n

67.180.41.229:6346\n

See section 2.2.3 of the textbook for a detailed description of HTTP messages.

Notes: 1) new line character \n is sometimes accompanied by carriage return \r as in \r\n,

which depends on the server you contact; 2) some GWebCaches rate limit requests and will not

respond if contacted too frequently. For more details about bootstrapping in Gnutella, see

http://www.pam2004.org/papers/247.pdf.

3.2. Neighbor Lists

The latest Gnutella protocol provides a convenient interface for crawling. Each alive peer

must accept crawl requests and reply with a list of its neighbors' IDs. After a connection to a

Gnutella user is established, you can send a crawl request to the peer using a standard Gnutella

handshake:

GNUTELLA CONNECT/0.6\r\n

User-Agent: UDAYTON_CS_CRAWLER/1.0\r\n

X-Ultrapeer: False\r\n

Crawler: 0.1\r\n\r\n

Here, GNUTELLA CONNECT/0.6 is the Gnutella connection request specifying protocol version

0.6, User-Agent: UDAYTON_CS_CRAWLER/1.0 is the name of your client (can be an arbitrary

string in place of UDAYTON_CS_CRAWLER/1.0), X-Ultrapeer: False indicates that your client

wants to be viewed as a leaf node, and Crawler: 0.1 marks this message as a crawl request of

version 0.1.

Each field ends with a Windows-style line break \r\n and the whole message ends with an

empty line (i.e., double break \r\n\r\n). After sending a crawl request, your code needs to wait

for a reply from the crawled peer and then parse this response to find new peers.

3.3. Parsing Replies

Replies to Gnutella crawl requests are similar to requests you transmit:

GNUTELLA/0.6 200 OK\r\n

User-Agent: BearShare 5.2.1.2\r\n

Peers: 66.171.38.246:6346,70.61.68.76:6346\r\n

Leaves: 128.108.111.162:3559,128.108.111.148:2679\r\n

X-Try-Ultrapeers:72.199.169.34:6346,71.160.45.142:6346\r\n\r\n

In the first line, the peer replies with its Gnutella protocol version number and status code,

where 200 means OK, 503 means busy, and 593 means OK to be crawled. Each line of the re-

5

maining reply is in the form of field_name: field_value\r\n. Field User-Agent: specifies

the name and version of the client software (which is BearShare 5.2.1.2 in this case). Field

Peers: provides a list of neighboring ultrapeers, which are separated by commas (the same sepa-

rator applies to fields Leaves and X-Try-Ultrapeers). Field Leaves: contains a list of children

attached to this peer, which may be an empty set if the crawled peer is a leaf, and field X-Try-

Ultrapeers: is an optional field that contains additional ultrapeers that may be contacted (in-

clude these in your crawl).

Note that usually there is a space after the colon, but this is not always the case (e.g., in the

above example, X-Try-Ultrapeers: is not followed by a space). To accommodate multiple

spaces and other random formats, it is recommended that you skip all spaces and possibly tabs

following the colon. Also note that field names may be capitalized or occur in a different order

from the one shown above. Similarly, the reply message may contain fields unrelated to your

crawl, which you should simply ignore. To illustrate these points, additional examples follow

below. The first one is from a LimeWire ultrapeer:

GNUTELLA/0.6 593 Hi\r\n

User-Agent: LimeWire/4.9.23 (Pro)\r\n

X-Ultrapeer: true\r\n

Peers: 68.52.201.178:9812,69.244.250.162:6346\r\n

Leaves: 216.218.168.49:6346,128.108.151.7:6346\r\n

Here is a response from a LimeWire leaf:

GNUTELLA/0.6 593 Hi\r\n

User-Agent: LimeWire/4.9.7\r\n

X-Ultrapeer: false\r\n

Peers: 128.108.151.7:6346\r\n

Leaves:\r\n

It is also possible to receive the following reply with timestamps appended to each X-Try-

Hub ultrapeer:

GNUTELLA/0.6 503 Crawling a Leaf\r\n

User-Agent: morph500 5.2.2.1015 (GnucDNA 1.1.1.4)\r\n

Remote-IP: 128.194.135.83\r\n

X-Try-Ultrapeers: 24.124.51.119:3047\r\n

X-Try-Hubs: 81.248.122.225:20805 2006-08-24T13:33Z,81.242.228.37:5835

2006-08-24T13:33Z\r\n

Note that you should parse all responses (including the busy code) and use the returned list of

Peers and X-Try-Ultrapeers. If you intend to parse X-Try-Hubs: or other user-agent specific

fields, document the details of this step in your report.

3.4. Performance Issues

You may soon find that some peers are dead or behind firewalls, in which case your connec-

tion will fail after a lengthy timeout. To speed up the crawl, this homework requires that you use

multiple threads to work on the BFS queue. Each thread will pull one IP:port pair from the queue

and attempt to crawl the corresponding peer. After obtaining its neighbors and children, the

6

thread will have to check uniqueness of the found ultrapeers and then insert those that are unique

(i.e., not seen before) back in the BFS queue. You will thus need to use mutexes to synchronize

on updating shared data structures. The isidore.udayton.edu contains a sample file that uses two

threads and inter-thread synchronization during access to a shared array. Here is an example of

creating and using mutexes/semaphores:

#include <windows.h>

HANDLE mutex, semaphore;

// create a mutex not initially owned by anyone

mutex = CreateMutex (NULL, false, NULL);

// create a semaphore counting to 5 (allowing up to 5 concurrent events)

semaphore = CreateSemaphore (NULL, 0, 5, NULL);

// lock mutex

WaitForSingleObject (mutex, INFINITE);

<critical section>

// release mutex

ReleaseMutex (mutex);

// lock semaphore

WaitForSingleObject(semaphore, INFINITE);

<critical section>

// release semaphore by 1

ReleaseSemaphore (semaphore, 1, NULL); // release 1 thread

In addition, to avoid slowing down the user-interaction response time of your computer, you

should set all your threads to the lowest priority:

SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_LOWEST);

3.5. BFS Termination Issues

The BFS queue is a shared object that is written to by many threads and read from my many

threads as well. This is the classical producer-consumer problem in synchronization. The solu-

tion is outlined below using a combination of C++ and pseudo code. It uses a counting sema-

phore semaQ that is incremented each time an item is placed in the queue and locked before an

access to the queue is attempted. After the access is granted, all threads synchronize on a BFS

mutex before they modify the queue. Termination is signaled when the queue becomes empty

and no other thread is working:

HANDLE arr[] = {eventQuit, semaQ};

if (WaitForMultipleObjects (2, arr, false, INFINITE) == WAIT_OBJECT_0+1){

BFSmutex.lock();

active_threads ++; peer = Q.extract();

BFSmutex.unlock();

// crawl peer ... large delay here

BFSmutex.lock();

for (each new peer){

Q.insert(peer); visited.insert(peer);

ReleaseSemaphore(semaQ);

}

7

active_threads--;

if (Q.size() == 0 && active_threads == 0)

SetEvent (eventQuit);

BFSmutex.unlock();

}

else // quit event has been signaled

return;

3.6. Socket Issues

By default, Windows XP SP2 does not allow more than 5000 open sockets. If you experience

a problem with opening new sockets (i.e., calls to socket() fail), you can increase this limit using

the registry. There is a link on the course webpage to the documentation from Microsoft. Note:

this issue does not arise in Windows 2003 Server.

Another feature of Windows XP SP2 is that it limits the number of outbound connections to

10/second. There is a fix that modifies tcpip.sys to allow more connections per second (the link

is also provided on the course website). To achieve good performance, you will need to raise this

limit to about 500/second or more depending on how fast your code runs. Note: this issue does

not arise in Windows 2003 Server.

Reading from sockets is accomplished using this general algorithm:

char buf [512];

string s = ""; // empty initial string

do {

// wait to see if the socket has any data (see MSDN for description)

// set the timeout to 30 seconds

if (select (sock, ..., timeout) > 0) {

// leave one byte for NULL termination and get the data

bytes = recv(s, buf, 511, 0);

if (bytes == 0) // connection closed, all data received

break;

if (bytes == SOCKET_ERROR) {

closesocket(sock);

continue to the next peer;

}

buf[bytes] = 0; // NULL terminate buffer

s += buf; // append to the string

}

} while (true);

Finally, you may experience deadlocks inside recv() when the peer would not provide any

data and would not close the connection in response to your request. To avoid this possibility,

always use select() before attempting to read from a socket. See MSDN or a winsock tutorial on

the usage of this function.

8

3.7. Thread Issues

Starting too many threads may be difficult in 32-bit operating systems due to the large space

needed in the kernel to handle thread control data. It is recommended that you use a system with

at least 2 GB of RAM and a 64-bit operating system.

Here are several suggestions that will overcome problems with running out of thread memory

in the kernel (which usually manifests itself in calls to bad_alloc() with out-of-memory errors in

Debug mode). First, reduce the reserve stack size in the project using Visual Studio .NET 2005:

Project Properties->Linker->System->Stack Reserve Size = 65536

Second, use Windows Task Manager to see the number of threads actually running and make

your code report any errors returned from CreateThread to the user. To see the thread count per

process, use View->Select Columns in Task Manager.

3.8. Helpful Commands

For debugging purposes, use telnet <host> <port> to establish a TCP connection and test

HTTP or Gnutella commands manually. For example: telnet www.google.com 80

opens an HTTP connection to www.google.com on port 80. You can use a similar technique

to connect to Gnutella peers if their IP address and port number are known. To see what you are

typing on the screen, set the local echo to true by pressing Ctrl-] and typing set localecho fol-

lowed by two ENTER keys.

For information about your network configuration, use ipconfig at the command prompt (to

see the DNS servers, use ipconfig /all). To manually perform DNS lookups, use nslookup

host or nslookup IP at the command prompt.

3.9. Visual Studio STL

Learn how to use sets and queues in STL using MSDN. For example, you can use sets as an

easy way of storing unique elements and verifying whether additional elements belong to a set

(e.g., based on the observation that new elements increase set size, while duplicates do not):

#include <set>

using namespace std;

// Create an empty set s0 of key type integer

set <int> s0;

s0.insert(10); // set size 1

s0.insert(20); // set size 2

s0.insert(30); // set size 3

s0.insert(10); // set size 3, contains (10, 20, 30)

STL queues are similar:

9

#include <queue>

using namespace std;

queue<int> q;

q.push(10);

q.push(20);

q.push(30);

while (!q.empty())

{

int x = q.front();

printf("x = %d\n", x);

q.pop();

}

While the above examples store only elements of type int, your specific application will re-

quire elements that are classes of type Peer:

#pragma pack(push) // save current struct packing

#pragma pack(1) // align to 1-byte boundary

class Peer{

public:

DWORD IP; // 4-byte unsigned int defined in <windows.h>

unsigned short port;

};

#pragma pack(pop) // restore old packing

queue<Peer> q;

// inet_addr converts strings to 4-byte IP representations

Peer x = {inet_addr("128.194.135.100"), 2001},

y = {inet_addr("128.194.5.20"), 4089};

q.push(x);

q.push(y);

A similar approach applies to the set; however, you will need to define a comparison function

for class Peer so that STL can detect insertion of duplicate elements:

#pragma pack(push) // save current struct packing

#pragma pack(1) // align to 1-byte boundary

class Peer{

public:

DWORD IP; // 4-byte unsigned int defined in <windows.h>

unsigned short port;

// comparison operator for testing uniqueness

bool operator ()(Peer x, Peer y) {

return memcmp(&x, &y, sizeof(Peer))<0;

}

};

#pragma pack(pop) // restore old packing

set<Peer, Peer> s;

Peer x = {100, 200}, y = {200, 200}, *z = new Peer;

z->IP = 200; z->port = 200;

s.insert (x);

s.insert (y);

10

s.insert (*z);

s.insert (x); // set contains two elements (x,y)

delete z;

Repacking to 1 byte is mandatory for this code to work. Note: you cannot add STL structures

to the above class Peer since memcmp only works with scalar object types (you can write your

own comparison function, however).

3.10. DNS Lookup Issues

During the final phase of converting IPs into hostnames (by using standard getnamein-

fo() or gethostbyname() Winsock calls – getnameinfo is recommended), you may

generate a huge amount of traffic to your local DNS server (the default DNS server at my com-

puter is ns3.udayton.edu) and potentially crash it. This may lead to suspicion that you are per-

forming malicious activity and purposely trying to compromise network security. To find out

your local DNS server, go to the command prompt and type nslookup without any arguments.

To avoid complications, you should reset the DNS server of your own computer using one of

the following methods. You need administrator privileges to switch the DNS server.

Method 1 (the only choice for students who live on campus): go into Network Connec- tions->Local Area Connection (Properties)->Internet Protocol (TCP/IP) (Prop-

erties) and modify the field called “Preferred DNS server.” If you are using DHCP, move the

radio button from “Obtain DNS server address automatically” to “Use the following DNS server

addresses.” Set Preferred DNS server to 131.238.252.51. The UD helpdesk authorizes students in

CPS 470/570 to use this DNS server. Run the lookups slowly (space them out over a 2-day period).

The instructions of setting DNS servers for Windows Vista are slightly different. Check this

website https://www.opendns.com/start/device/windows-vista, or search Google to find out.

Method 2 (recommended for students who live off campus): you can install a free trial ver-

sion of Simple DNS Plus (http://www.simpledns.com). After you install the DNS server locally

at your computer and reset (see above) the DNS server to 127.0.0.1, getnameinfo will send

all lookup requests to your local server.

Method 3 (not recommended for students who live off campus, but a working method): you

can use the DNS servers at OpenDNS (http://www.opendns.com/) and set Preferred DNS server

to 208.67.222.222. In this case, you do not need to install any DNS server at your computer, but run the lookups slowly (space them out over a 2-day period).

Note: Do not run your code at CPS labs when you convert IPs into hostnames (Part 3).

To verify that DNS is working as intended, run nslookup at the command prompt.

3.11. Wireshark

Wireshark (http://www.wireshark.org/) is a software package that allows you to intercept all

packets sent and received by your computer. Wireshark allows you to diagnose implementation

problems encountered in this and other homework.

3.12. Debug vs. Release Mode

When using a large number of threads, always run your code in Release mode as it runs 50

times faster in STL functions and occupies 50% less memory. For scalar classes inserted into

11

STL sets, you can roughly estimate 60 bytes per entry in Debug mode and 30 bytes in Release

mode. If you insert other STL objects (such as strings) into a set, then count a minimum of 90

bytes per entry plus the length of the string in Debug mode and 55 bytes in Release mode.

Furthermore, to avoid swapping to disk and showing unacceptably low performance in your

report, check that the total memory usage in Task Manager is well below your physical RAM

size. You can notice that something is wrong when increasing the number of threads beyond

some threshold (such as 2500) leads to significantly lower performance.

__MACOSX/project 1/._as1-crawler.pdf