table,routing,bittorrent,dht,kademlia , Implementing find node on torrent kademlia routing table


Implementing find node on torrent kademlia routing table

Question:

Tag: table,routing,bittorrent,dht,kademlia

I, already, reviewed a number of documents on this topic but there is something not exactly clear. For example bit torrent document (http://www.bittorrent.org/beps/bep_0005.html) states

The routing table is subdivided into "buckets" that each cover a portion of the space. An empty table has one bucket with an ID space range of min=0, max=2^160. When a node with ID "N" is inserted into the table, it is placed within the bucket that has min <= N < max. An empty table has only one bucket so any node must fit within it. Each bucket can only hold K nodes, currently eight, before becoming "full." When a bucket is full of known good nodes, no more nodes may be added unless our own node ID falls within the range of the bucket. In that case, the bucket is replaced by two new buckets each with half the range of the old bucket and the nodes from the old bucket are distributed among the two new ones. For a new table with only one bucket, the full bucket is always split into two new buckets covering the ranges 0..2^159 and 2^159..2^160.

It is somewhat different from other documents regarding kademlia routing table where buckets are arranged in accordance to the bit prefix of the node id but there is another confusing thing. When we reply to the "find node" request we have to find 8 closest nodes to the requested one using XOR operation. I saw some implementations just going through each item in the routing table executing XOR operation and thus finding 8 closest items. It seems to me too CPU wasting.

Everything is already in buckets. Even if we use the suggested by the bit torrent document system we can quicker find the bucket which could potentially contain the requested node id simply enumerating buckets and checking the minimum and maximum numbers on it. Then potentially that bucket should contain the closes nodes but they are value closest nodes not the XOR closest nodes (as I understand) which is somewhat different but somewhat similar.

I ran a simple test using numbers from 0 to 99 where I wanted to find 8 XOR closest numbers and they where in the proximity of the sought number but not right near it. Now, thinking about our buckets I guess it possible that all node ids in the bucket are the closest for a minor exception. So, for example if we take this bucket, take one from the left and one from the right and search for the XOR closest node ids we'll find what we are looking for and there is no point to go through ALL nodes in the routing table.

Am I right or am I missing something?


Answer:

It is somewhat different from other documents regarding kademlia routing table where buckets are arranged in accordance to the bit prefix of the node id but there is another confusing thing.

The bittorrent specification describes a routing table implementation that only approximates the one described in the kademlia paper. It is easier to implement but has some shortcomings.

So, for example if we take this bucket, take one from the left and one from the right and search for the XOR closest node ids we'll find what we are looking for and there is no point to go through ALL nodes in the routing table.

In both - the full, tree-like routing table implementation and the simplified BEP5-variant - each bucket can be thought of as having a CIDR-like prefix (see this SO answer) consisting of prefix bits that the bucket covers and a mask bit count.

In the BEP5-variant each bucket's prefix is simply derived from the array index and your node's own ID. In the tree-like table buckets have to track their prefix due to bucket split/merge operations.

Using those prefixes you can find the bucket that covers the target key.

The thing is that buckets don't have to be full, and if you want to send, let's say 20 nodes in a response a single bucket will not suffice. So you have to traverse the routing table (either sorted based on your own node ID or by the natural distance) in two directions at once because you're looking at distances relative to the target node. Since the XOR distance metric folds in the order at each bit-carry you basically have to bounce backwards and forwards.

Here's my implementation[I could probably do without sorting] for finding the N closest nodes to a specific target key from a tree-like routing table.

I figure that many people simply iterate over the whole routing table because for regular nodes it will only contain a few dozen buckets at most and a DHT node does not see much traffic, so it only has to execute this operation a few times per second and if you implement this in a dense, cache-friendly datastructure then the lion's share might actually be the memory traffic and not the CPU instructions doing a few XORs and comparisons.


Related:


Awk Script to process data from a trace file


table,awk,rows,trace
I have a table (.tr file) with different rows (events). **Event** **Time** **PacketLength** PacketId sent 1 100 1 dropped 2 100 1 sent 3 100 2 sent 4.5 100 3 dropped 5 100 2 sent 6 100 4 sent 7 100 5 sent 8 100 6 sent 10 100 7...

for-loop add columns using SQL in MS Access


sql,ms-access,table,for-loop,iteration
I am trying to add n columns to a table, like in this example of code where n = 10: Sub toto() Dim db As Database, i As Integer Set db = CurrentDb() For i = 1 To i = 10 db.Execute " ALTER TABLE time_series " _ & "ADD...

Rails routing link to specific show


ruby-on-rails-4,routing
This question seems a little basic, but considering I have 'pages#show' with a show page with url 'history'. How could I add this specific show page to a link: = link_to 'History', pages_path(@?????) PD1: I would prefer avoid using :id since I tend to seed a lot of data, and...

$StateProvider Remove Child View Nesting


angularjs,routing,angular-ui-router,angularjs-ui-router
I am new to angular ui routing . I am creating a sample application and want to display parent and child view separately . I mean when parent item gets selected child view will be displayed and parent view would be hidden . If I add ui-view to parent view...

How to show mysql multi row / mysql_fetch_array results in a table?


php,mysql,arrays,table,while-loop
I am trying to show mysql_fetch_array() results in a table. I want to show guests name,their country and their agreed time who are traveling on a same date. Following code works fine. The code fetches the row values and prints it. $select_guests = mysql_query('SELECT name FROM van_sharing WHERE date =...

Select Mongoose Model Based on Express Route


express,routing,mongoose
I think this might be a basic question, but looking for the best approach. I'm building an express app that should route to one of four different Mongoose models depending on the route. Something like this: app.get('/:trial', function(req, res){ var trial = req.params.trial; trial.find(function(err, records) { if (err) res.send(err); res.json(records);...

filtering firstname and lastname using datatable.js


javascript,jquery,table,datatable,filtering
I have created a application with dataTable for filtering firstname and lastname, I am having a firstname and lastname text-field through which I would filter firstname and lastname. The filtering is working but the issue is that firstname and lastname filtering is doing from both the textfield, Actually I need...

How to parse table of numbers in C++


c++,parsing,table,numbers
I need to parse a table of numbers formatted as ascii text. There are 36 space delimited signed integers per line of text and about 3000 lines in the file. The input file is generated by me in Matlab so I could modify the format. On the other hand, I...

Retaining original table formatting after a 'pagebreak'


excel,excel-vba,table,formatting,page-break
So here's the finished product, a statement of accounts with a working statement table, and an ageing analysis: Everything works great. It basically populates itself row by row with data from another table. Here is the sample code: j = 21 'First row on the statement of accounts workbook For...

Why doesn't table resize work here? jsfiddle url inserted


jquery,html,table,jquery-ui-resizable
How can I make my table resizable like a textarea element and not individual rows/columns? I seem to be fundamentally missing something simple. https://jsfiddle.net/o0Ldf0us/ <table id="example"> <thead> <tr> <th>Heading1</th> <th>Heading2</th> <th>Heading3</th> </tr> </thead> <tbody> <tr> <td>Data1.1</td> <td>Data1.2</td> <td>Data1.3</td> </tr> <tr> <td>Data2.1</td> <td>Data2.2</td>...

Table goes max height when screen is resized


javascript,html,css,ajax,table
I have a table that is generated with a min-height of 300px and a max-heigh of 650px which is perfect. The only problem is when i resize the window the table will stretch all the way down until all its values are shown. Its supposed to have a scroll bar...

PL/SQL: Join between two tables error [on hold]


sql,table,join,plsql
I have got a task in which I have to display information from two different tables using a cursor. I tried doing it with an example we did before, but it doesn't seem to work! Below mentioned are the two tables that I have to take records from and display...

Codeigniter Select JSON, Insert JSON


json,codeigniter,select,insert,routing
I have very simple users database: user_id, user_name, user_email My model this: class Users extends CI_Model { private $table; private $table_fields; private $table_fields_join; function __construct() { parent::__construct(); $this->table = 'users'; $this->table_fields = array( $this->table.'.user_id', $this->table.'.user_name', $this->table.'.user_email' ); $this->table_fields_join = array(); } function select(){ $this->db->select(implode(', ', array_merge($this->table_fields, $this->table_fields_join)));...

Taking cell values in a table


javascript,jquery,html,table
I want to take some of the cell values in a table . How to take All at a strech. Can i assign a class name to those cells and take the values for each of them

c - Parallelising a function


c,multithreading,table,rainbowtable
I'm trying to implement parallelism to this function I want it to take as many threads as possible, and write the results to a file. The results need to be written in the file in the incrementing order so the first result needs to be written first the second second...

Open page url in modal on a page (Facebook Photo URLs)


javascript,jquery,angularjs,routing,angularjs-routing
P.S. I am using html5Mode to remove '#' in routing in below scenario Removing the hashtag from AngularJS urls (# symbol) Consider I have two main pages.One is photos where thumbnails are provided and whose url is /someSlug/photos. Other is the url of a single photo '/someSlug/photos/somePhotoId' which shows a...

How to deal with extra “/” in phpleague route?


php,web-services,routing
I am setting endpoints for my web application like this: $router = new League\Route\RouteCollection; function user_action (Request $request, Response $response) { // some logic . . . return $response; } $router->addRoute('GET', '/user', 'user_action'); /user endpoint works well. However when I use /user/ (extra slash in the end) I get a...

How to Click All Inputs with the Same Class on Page Load


javascript,jquery,table,input,click
I have a table with multiple rows (hundreds) on my web page. Each table row has an input with the class name of act_inv. I am trying to get JavaScript/JQuery to click each input with the class name of act_inv. Is this possible? And if so, how may I do...

HTML Table with 2 (two) rows set beside a 4 (four) row set


html,table
How would I achieve this table layout?

Break table in two lines


css,table
How to break the table td in two lines using media-querie? jsfiddle @media only screen and (max-width : 768px) { .table > tbody > tr > td { width: 100%; max-width: 100%; } } ...

Displaying table columns below of each other for small displays (responsive layout)


html,css,table,responsive-design
I have a table with two columns: ------------- | A | B | ------------- I the browser width is too small for this layout, it should switch to this layout: ------------- | A | ------------- | B | ------------- I got this to work with fixed column width and "float:left":...

Multiple Json response to html Table format


php,mysql,json,table,response
I want to fetch data from different servers Database and i need to shown in one Centralised server. So i have written a SELECT query in different locations and i am trying to fetch in one Centralised Server. I am getting a JSON Array response. But i tried displaying it...

Joining tables and LEFT JOIN as new Columns in tsql


sql,sql-server,tsql,table,row
In this sample I have two tables containing data for my Customer and Products that a office supply shop has. which is seen below: The Above tables primarily functions to supply the required data for the third table which is the Orders table Using the orders table, I can get...

Show and hide column in a table using drop down


javascript,jquery,html,table,drop-down-menu
I have a table, which looks exactly like this one: https://www.datatables.net/examples/api/show_hide.html I now want to replace the headers (the th things) with a drop down. I want to hide and show columns thanks to those drop downs (they can click and show what they want). I was also wandering if...

Php Mysql: Retrieving 2 usernames via 2 user id


php,mysql,table,join
Hi all i have one problem that i cant solve. I am doing pair generator for tournament. I have two tables. The first table contains the usernames and userids. The second table contains match_id, round, user1_id, user2_id Table 1 user_id username 21 John 22 Peter 23 Ana 24 Dan Table...

Refreshing SQL view after adding a default constraint to one of its tables


sql,table,view,refresh
How exactly can I refresh the view after adding a default constraint to one of the tables that makes up the view? I tried to use the sp_refreshview stored procedure but that didn't actually update the view. Here is the code I wrote to update one of columns with a...

Restrict laravel to open url that is not in route


php,laravel,routing,laravel-5,laravel-5.1
I am Learning laravel now. Today I came across a problem that surprised me. I open this link in my browser: http://localhost/laravel/project/ch/resources/views/pages/blog.blade.php And I expect error 404. but it opens contains of this file. So, How to restrict laravel to do this. I want laravel to open only url mentioned...

For each `pop` get frequencies of the elements of `id`


r,table,data.table
Consider this data: m = data.frame(pop=c(1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4), id=c(0,1,1,1,1,1,0,2,1,1,1,2,1,2,2,2)) > m pop id 1 1 0 2 1 1 3 1 1 4 1 1 5 2 1 6 2 1 7 2 0 8 2 2 9 2 1 10 3 1 11 3 1 12 3 2 13 3 1...

How to get a mysql query to use a specific index?


mysql,database,table,indexing
SELECT * FROM orders WITH (INDEX(idx)); When i fired above query i got the error mysql #1064 - You have an error in your SQL syntax I have created index as below create index idx on orders(date,status); Can anybody tell me the correct syntax?...

Table with AngularJS using different jsons


javascript,angularjs,table
I am new with AngularJS and I've created a table to show information from two different JSONs. To do that, I "mixed" them to get one. My code: test.html <!doctype html> <html ng-app="App"> <head> <script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/angularjs/1.2.0-rc.2/angular.min.js"></script> <script type="text/javascript" src="script.js"></script> </head> <body ng-controller="myCtrl" ng-init="init()"> <table border=1> <thead> <tr>...

How do I print a list of strings into a table in python? [on hold]


python,string,list,table,printing
This is the list tableData = [['apples', 'oranges', 'cherries', 'banana'], ['Alice', 'Bob', 'Carol', 'David'], ['dogs', 'cats', 'moose', 'goose']] This is how I want it to look like apples Alice dogs oranges Bob cats cherries Carol moose banana David goose ...

Event on dynamically created checkbox asp.net


c#,jquery,asp.net,table,checkbox
I started to programming with asp.net, I have a table with some checkboxses. The problem is, I can't create static tables, because this action is linked with some parameters. Anyway.. When I click on the First checkbox I want to invert the other checkboxes in this table. How can i...

Formatting long-form survey data in R


r,table,formatting,reshape,long-form
We asked 3 people two or three yes-no questions. Let me denote these 3 people by 101,102,103 the questions by "A", "B","C" and the responses by 0, 1. The result is q<-data.frame(response=c(0,0,1,0,0,1,1), qstn=c("A","B","A","B","A","B","C"), person=c(101,101,102,102,103,103,103)) We need to convert this table to the following format person|qustionA|questionB|questionC 101 | 0 | 0...

How to reduce table border thickness?


table,border,thickness
I am drawing one table with border=1 but it looks quite prominent as i am enclosing one image inside it so i want to make it thinner for better look and feel. <table border=1 cellpadding=50 cellspacing=0><tr><td></td></tr></table> How can i reduce border thickness? ...

Route parameter with slash “/” in URL


asp.net-web-api,routing,asp.net-web-api2,asp.net-web-api-routing,attributerouting
I know you can apply a wildcard in the route attribute to allow / such as date input for example: [Route("orders/{*orderdate}")] The problem with wildcard is only applicable to the last paramter in URI. How do I solve the issue if want to have the following URI: [Route("orders/{orderdate}/customers")] ? EDIT:...

Angular $routeProvider and Controller As Syntax


angularjs,routing,angularjs-scope,angularjs-routing,ngroute
Can anyone tell me if it is valid to use $routeProvider with Controller as syntax? I am having issues accessing <h1>{{kickController.foo}}</h1> from the controller where this.foo resides. angular.module('ucp.kick', ['ngRoute']).config(function($routeProvider, APP_BASE_URL) { return $routeProvider.when(APP_BASE_URL + 'kicks', { reloadOnSearch: false, navitem: true, name: 'Kicks', templateUrl: 'kick/partials/kick.html', controller: 'kick as KickController' }); });...

fill an html table by column instead of row?


html,css,table
'<table> <tr> <th>' .$varProduct[$x][0]. '</th>'. //this is a title '<th>' .$varProduct[$x][2] . $varProduct[$x][11] . ' </th> // this is a price </tr> </table>' this code makes a table that fills out like this Title Price Title Price Title Price but I want to fill it Title Title Title Price Price...

Excel- update table with another table based on cell value


excel,table,copy,cell
after searching, I understand I can copy data into a table one at a time using VLOOKUP. However, is it possible to replace an entire table with another if a cell contains a certain value? for example, I have a table1. I want to replace table1 with table2 if cell...

No action was found on the controller that matches the request


c#,asp.net,ajax,asp.net-mvc,routing
Sorry for the lame question. I've already read all similar questions and still can't resolve my issue. I'm getting 'No action was found on the controller that matches the request' error when calling from ajax: $.ajax({ url: '/api/ToyEdit/Post/', dataType: "json", type: "POST", contentType: 'application/json; charset=utf-8', data: JSON.stringify({toyId: 1, toy: 'asd'}),...

Change resources path


ruby-on-rails,ruby,routing
I'm using Rails 4 I have a routes.rb file that looks like: resources :books However, I'd like the urls in the application to end up looking like /b/101 instead of /books/101. I realize I could go through and rename each resource path individually, but is there not a way to...

SWT - show multiple table items


java,table,swt,tableviewer
Could anybody help me? I have a table in SWT and simply I want to show some table items but the table only shows one item and the others with vertical scroll. I want to show everything, without scrolling. I tried with the option SWT_NO_SCROLL but is not working. I...

WebApi Routing not working for Post


routing,asp.net-web-api2,asp.net-web-api-routing
My WebApiConfig has following routes // Web API routes config.MapHttpAttributeRoutes(); config.Routes.MapHttpRoute( name: "DefaultApi", routeTemplate: "api/{controller}/{id}", defaults: new { controller = "Employee", action = "Get", id = RouteParameter.Optional } ); The Post WebApi method has got following Signatures [HttpPost] public IHttpActionResult Post(Employee emp) { ..... } When i try to call...

How can I render this irregular table with ng-repeat?


html,angularjs,table,angularjs-ng-repeat,ng-repeat
Here I have a json data as below: [ {"teacher":"Tom","student":[{"name":"stuA","project":"projectA"},{"name":"stuB","project":"projectB"}]}, {"teacher":"Jerry","student":[{"name":"stuC","project":"projectC"},{"name":"stuD","project":"projectD"},{"name":"stuE","project":"projectE"}]}, {"teacher":"Lee","student":[{"name":"stuF","project":"projectF"}]} ] And now I wanna render it into an irregular table like the picture: So how can I make it possible by using ng-repeat?It's really a confusing problem. here is the html code that makes the table...

How do I display my mysql table column headers in my php/html output?


php,html,mysql,table,data
2 Questions... Scenario: I would like to query my database table via a form and then display the results that occur(if there are results) and my current situation is that it does work but it clears the form completely and leaves my to an empty page with just the results...

Form inside javascript not working


javascript,forms,table
I am using javascript to show a sort of menu box with clickable links but I changed my mind and want to use links as forms now. <script type="text/javascript"> $('.mouseon-examples div').data('powertipjq', $( [ '<table class="tabulkajazyku"><form id="myformen" action="member" method="POST"><input type="hidden" name="jazyk" value="en"><tr><td><a class="odkaz_cerveny odkaz_cerveny_block" href="#" id="mylinken"><img src="/images/flag_en.jpg" class="vlajky"><div...

MySQL 4 Table Join


mysql,table,join
I've been trying to get the proper data for this 4-table join for awhile and I can't seem to pin it down. I'm trying to grab a list of ids from songs based on who I am following in follows, and show the song id if my followers are the...

Symfony/Twig how to render a Route set by anotation?


php,symfony2,routing,twig,url-routing
Let's say I have this code in a controller: <?php namespace Foo\BarBundle\Controller; use Symfony\Bundle\FrameworkBundle\Controller\Controller; use Sensio\Bundle\FrameworkExtraBundle\Configuration as Mvc; /** * @Mvc\Route("/foo/bar") */ class TestController extends Controller /** * @Mvc\Route("/test/{id}", requirements={"id" = "[0-9]{1,6}"}) * @Mvc\Template * * @return view */ public function testAction($id) { return array('test' => $id); } } How...

How to insert data into sql server database when the primary key column already set default identity(1, 1)


c#,table,insert
I'm trying to insert two data columns into my SQL Server database but I get an error at the code line -> cmd.ExecuteNonQuery(); Cannot insert the value NULL into column OrderID, table RestaurantApp.dbo.Junc_Order; column does not allow nulls. INSERT fails. The OrderID column is actually the primary key in my...

I need help displaying an Xml file with php in table form


php,xml,table,attributes
So all-knowing community, once more I seek your help. I have been working on something for the past few days and it is starting to drive me insane. I need to grab the contents of an xml file and display it in a table. Since it has various levels I...

Convert table HTML to JSON


javascript,html,json,table
I have this: <table> <tr> <th>Name:</th> <td>Carlos</td> </tr> <tr> <th>Age:</th> <td>22</td> </tr> </table> And I need a json format. {"Name":"Carlos","Age": 22} I've tried with https://github.com/lightswitch05/table-to-json but it doesn't work for the headings in every row :( EDIT: http://jsfiddle.net/Crw2C/773/...