Transcript An Improved Kademlia Protocol In a VoIP System

An Improved Kademlia Protocol
In a VoIP System
Xiao Wu，Cuiyun Fu and Huiyou Chang
Department of Computer Science, Zhongshan University,
Guangzhou, China
resource：2007 IFIP International Conference on Network
and Parallel Computing – Workshops
reporter：69721019 蔡進合 69721059 賴彥彰
Outline





Introduction
Kademlia
Improved protocol based by Kademlia
 Improved Route table
 Improved Route protocol
Backup channel
Conclusion
Outline





Introduction
Kademlia
Improved protocol based by Kademlia
 Improved Route table
 Improved Route protocol
Backup channel
Conclusion
Introduction

Standard Kademlia is designed for file sharing
systems and searching is expected to stop when
both the desirable peer and k closest peers return.
Introduction

When applying to real-time system such as VoIP,
standard Kademlia should make some
modification.

We proposed an improved kademlia protocol to
adapt to VoIP systems meeting the need of realtime audio service and establishing a conversation
in short delay.
Outline





Introduction
Kademlia
Improved protocol based by Kademlia
 Improved Route table
 Improved Route protocol
Backup channel
Conclusion
Kademlia

A peer-to-peer distributed hash table protocol in
P2P network.

ID：a unique 160-bits identifier that calculated by
SHA-1 algorithm
 properties：
(1) different inputs bring different values;
(2) distributed in the overlay topology
uniformly
Kademlia

<key, value> pairs are stored on nodes
 key ： 160-bit identifier
 value ： such as file name in file sharing
system and phone number in VoIP system.

distance：
d(x,y) = x ⊕ y
where x and y are two peers’ node ID
Kademlia

routing table：a binary tree whose leaves are kbuckets keeping a list of at most k nodes with
some common prefix of their node IDs in terms of
<IP Address, UDP port, NODE_ID> triples.

The prefix is the k-bucket’s position in the
routing table.
Kademlia
Kademlia

Remote Procedure Control(RPC)：
 PING
 FIND_NODE
 STORE
 FIND_VALUE

Peers will republish their <key, value> pairs to
keep them alive periodically；otherwise,
<key,value> pairs would expire and be deleted.
Outline





Introduction
Kademlia
Improved protocol based by Kademlia
 Improved Route table
 Improved Route protocol
Backup channel
Conclusion
Improved protocol based by Kademlia

When making phone calls, callers use routing
algorithm FIND_CALLEEID to search callees’ IP
addresses and UDP ports in the absence of server.
Besides, system has a backup channel.

When entering the network,the newcomer must
have a contact to an already participating node and
then it performs a node lookup for its own ID.
Outline





Introduction
Kademlia
Improved protocol based by Kademlia
 Improved Route table
 Improved Route protocol
Backup channel
Conclusion
Improved Route table

A binary tree similar to Kademlia.

Each leaf contains a cache-bucket as well as a kbucket, cache-bucket is used as a backup buffer of
the k-bucket.
Improved Route table

Quaternion <Node ID, IP address, Port, State>.
 Node ID ： generated by performing SHA-1
operation on client’s phone number
Lookup algorithm
Building the routing table

At the first beginning, the routing table is
composed of a single TNode, with only one
k-bucket and one cache-bucket.

When more than k nodes are being inserted,
the TNode will be split into two and each
child will be allocated a k-bucket and a
cache-bucket respectively.
Building the routing table


Those “near” the local node ID will be put in the
right child’s k-bucket or cachebucket ; in contrast,
those far from the local node ID will be moved to
the other child’s.
Nodes whose node IDs share common prefix of
local node ID are put in the right child’s.
Improved Route table


The routing table should try its best to stores
nodes near the local node ID and drop some nodes
far away to avoid routing table turgid expansion.
A target TNode is ”splitable”：
RULE1： It is a Local TNode;
RULE2 ：The right subtree of the minimum
subtree, containing the Local TNode and the
target TNode, contains less than k nodes.
Splitting TNode algorithm
A compression mechanism
Compacity
1 if This is an TNode that both left
and right child TNode is a leave
TNode and the binary tree is not
splitable.
2 Then Order all nodes in child
buckets by time first seen
3 move nodes from child TNodes to
parent and prefer old nodes,
when bucket is full put
remaining nodes in replacement
cache.
4 Order all nodes in child
replacement caches by time last
seen and prefer most recently
seen nodes
endif
Outline





Introduction
Kademlia
Improved protocol based by Kademlia
 Improved Route table
 Improved Route protocol
Backup channel
Conclusion
Improved Route protocol

Caller sends FIND_CALLEEID, with callee ID as
its parameter, to find the IP address in accordance
with the ID. Receiver returns k closest peers to
some given callee ID.

If Caller gets a response containing the callee ID,
lookup finishes or else continues to find closer
peers to callee.

The searching process terminates when caller has
queried and gotten responses from the k closest
peers it has seen and informs the caller that search
fails.
Improved Route protocol

Avoiding no refreshing in a certain distance, every
k-bucket without lookup in an hour would refresh
themselves by doing a callee lookup for a random
ID in the bucket’s range.
Outline





Introduction
Kademlia
Improved protocol based by Kademlia
 Improved Route table
 Improved Route protocol
Backup channel
Conclusion
Backup channel

In our model, backup channels build up a list
which stores n closest peers in IP network in the
form of <IP distance, IP address, port, timestamp,
next>.
Backup channel

We assume that the quaternion would become
untrusty once it stays longer that average talk time
and would be offline at any moment. Such
quaternion should be dropped so that the list could
be effective to the greatest extent thereafter.
Backup channel

When getting the IP address of the callee, caller
establishes a conversation with the callee and
caller no longer refreshes its backup channels. It
sends heartbeat packets to those peers in the list to
ensure every peer could connect to both caller and
callee. If peer fails to response, caller supposes the
peer is offline and deletes the quaternion from the
list.
Backup channel
Backup channel

The backup channels will stop refreshing when ID
searching is over. Thereby the failure probability
of backup list is increasing together with the
increase of the talk time. When backup channel is
really needed, little useful channel could be
offered by the list.
Backup channel


When there are less than β quaternions, caller will
require all of the remaining peers in the list for
more backup channels.Those peers will return γ
closest peers it knows from their own backup
channels. βand γis a system-wide parameter.
Returning peers would update the current backup
channels. In this rate, local peer would get more
information to set up a robust backup channel.
Outline





Introduction
Kademlia
Improved protocol based by Kademlia
 Improved Route table
 Improved Route protocol
Backup channel
Conclusion
Conclusion

In the improved Kademlia protocol we change the
original FIND_NODE in Kademlia to
FIND_CALLEEID, which terminates once the
caller gets the information about callee so that it
could set up a session as soon as possible.

Backup channel for circuit switching shortens the
delay when the connection between caller and
callee is broken.