In-Network Hashing

Updated wiki can be viewed at the following site: ​https://bitbucket.org/romoore/gnrs/wiki/Home

Architecture

Consists of the following components: GNRS service (with GNRS servers and LNRS servers), GNRS client, GNRS Agent

Service Interface

• Insert
• Update
• Query

Protocol

Message Formats

• Insert Message
• Insert Acknowledgement
• Query Message
• Query Response

refer to file ./common/messages.h for detail.

Implementation Status

1. two level of NRS: LNRS, GNRS, corresponds to LNRS_daemon and GNRS_daemon. The client sends GNRS insert/lookup message to its LNRS server and then LNRS server will forward the message to GNRS (for insert message, the LNRS server will insert the local part of the GUID mapping into its database and then forwards it to GNRS; for lookup message, LNRS server will first lookup in its local database, reply back if hit or forward to GNRS if not found). The client needs to know its LNRS server from a configuration file. (LNRS listens on port 5000, GNRS listens on port 5001).

2. locator is made up of two parts: network address: local host GUID. Network address part is stored at GNRS and works as the inter-domain routing locator, while the local host GUID is stored at LNRS and works as the intra-domain routing locator. ':' is used as the delimiter and LNRS server would replace it with '\0' and then forward the insert message to GNRS server.

3. each GUID mapping could have multiple NAs with TTL and weight attached. So the format of a GUID mapping looks like this: GUID: NA1, expiring timestamp weight; NA2, expiring timestamp weight;... (here, though the time field in insert/lookup message is TTL, the time field at the server is expiring timestamp. The server needs to do the translation. The advantage of such timing scheme is that it's not required that the whole system has the same clock.)

4. now the daemon uses a configation file (servers.lst) to know which servers are working as GNSR server. The servers.lst works as faked BGP table now. And for the hash function, it will return an index given GUID (supposed the index is i), then the ith server IP in the servers.lst will be chosen as the GNRS server for that GUID.

5. there are two sets of hashing functions that are implemented: the first hashing function directly returns with a server node IP address from the GUID. the other hashing function works in a consistent way with the GNRS paper: return an IP address hashed from GUID, then check the prefix table to get the corresponding AS number, and finally use another map function to map the AS number to a server node IP. ( now MD5 is used, need to change to SHA1 later).

6. a client gbench used for generating insert/lookup message and receiving responses. there are two sets of client stack: in folder client/, a serial client is implemented; in folder client-new/, a parallel client is implemented. For serial client, the client sends out a request, then waits for the response; after it receives the response, it sends out the next request. Parallel client separates sending from receiving.

7. deal with IP hole: rehashing.

8. longestPrefixMatching algorithm: based on radixIPlookup from click elements.

9. Berkley DB as a thread-safe in-memory database. mySQL is used for persistence.

10. computation flag in the message header: calculate the GNRS server which holds a certain mapping needs lots of computation. add a flag in the message header so only calculating once for the destination server.

Running experiments

1. LNRS server:
   

./lnrsd <config file> [<server_self_addr>] [servers_list_file]

2. GNRS server:
   

./gnrsd <config file> [<server_self_addr>] [servers_list_file]

3. client:
   

gnrs-client: used for testing
gbench: used for generating insert/lookup message and receiving responses (evaluation purpose).
./gbench <config_file> <request_file> ( optional: <client_address>, <server_address>, <client_port>

4. client-new:
   

gbench: used for generating insert/lookup message and receiving responses (evaluation purpose).
./gbench <config_file> <request_file> ( optional: <client_address>, <server_address>, <client_port>

5. the most updated working image for gnrs: feixiong-gnrs-17.ndz

pay attention to modify corresponding config file(config file for server and config file for client) and servers_list_file when running experiments.

evaluation script

1. evaluation scripts are under the folder /gnrsd/eval/:
   

gnrs_test_52_sb8.rb: script based on omf-5.2
gnrs_test_53_sb8.rb: script based on omf-5.3
run these ruby script at the console. e.g. omf-5.3 exec ./gnrs_test_53_sb8.rb

2. scripts under the folder /gnrsd/scripts/:
   

fetch_data.sh: fetch data from each node to console
some tools are in svn repository at the path gnrsd/src/tools/ which can be used for further data analysis.

evaluation result

1. orbit grid testing with 30 server + 1 client:
   

new node: Intel core i7, 2.96 GHz, 8G memory
old nodes: CentaurHaulsVIA, 512M memory

node1-1:
lookup: 112.223 us
mutex: 6.09186 us
lookup_handler: 51.6849 us
sendout: 16.1736 us

node1-5:
lookup: 628.75 us
mutex: 52.4 us
lookup_handler: 306.4 us
sendout: 86.8 us

client: lookup: 1374.28 us

2. round trip time testing on sb9:
   

udp transfer round-trip time: 135.411 us (using lmbench, 200 bytes message)

3. throughput testing using serial client:

sb8, Intel(R) Core(TM) i7 cpu, 8G memory One node for client side, one node for server

4. throughput testing using parallel client:
   

tools for collecting cpu info: iostat -c 1; mpstat -P ALL 1

TODO Items

1. GUID mapping caching

2. evaluation: a delay module for emulating real Internet; a topology file, a prefix file and a data trace which can represent the real Internet

3. no routing scheme, need to integrate with MF click forwarding engine or using existing BGP routing implementation like quagga.

4. change commandline params to be able to pass in 'argname=value' style. instead of what it is now which is forcing user to enter what are eseentially tuning parameters that are used for evaluation purposes