#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass scrbook
\begin_preamble
% in case somebody want to have the label "Equation"
%\renewcommand{\eqref}[1]{Equation~(\negthinspace\autoref{#1})}
% that links to image floats jumps to the beginning
% of the float and not to its caption
\usepackage[figure]{hypcap}
% the pages of the TOC is numbered roman
% and a pdf-bookmark for the TOC is added
\let\myTOC\tableofcontents
\renewcommand\tableofcontents{%
\frontmatter
\pdfbookmark[1]{\contentsname}{}
\myTOC
\mainmatter }
% makes caption labels bold
% for more info about these settings, see
% https://ctan.org/tex-archive/macros/latex/contrib/koma-script/doc/scrguien.pdf
\setkomafont{captionlabel}{\bfseries}
\setcapindent{1em}
% enables calculations
\usepackage{calc}
% fancy page header/footer settings
% for more information see section 9 of
% ftp://www.ctan.org/pub/tex-archive/macros/latex2e/contrib/fancyhdr/fancyhdr.pdf
\renewcommand{\chaptermark}[1]{\markboth{#1}{#1}}
\renewcommand{\sectionmark}[1]{\markright{\thesection\ #1}}
% increases the bottom float placement fraction
\renewcommand{\bottomfraction}{0.5}
% avoids that floats are placed above its sections
\let\mySection\section\renewcommand{\section}{\suppressfloats[t]\mySection}
% increases link area for cross-references and autoname them
% if you change the document language to e.g. French
% you must change "extrasenglish" to "extrasfrench"
% if you uncomment the following lines, you cannot use the reference version Ref+Text in LyX
%\AtBeginDocument{%
% \renewcommand{\ref}[1]{\autoref{#1}}
%}
%\def\refnamechanges{%
% \renewcommand*{\equationautorefname}[1]{}
% \renewcommand{\sectionautorefname}{sec.\negthinspace}
% \renewcommand{\subsectionautorefname}{sec.\negthinspace}
% \renewcommand{\subsubsectionautorefname}{sec.\negthinspace}
% \renewcommand{\figureautorefname}{Fig.\negthinspace}
% \renewcommand{\tableautorefname}{Tab.\negthinspace}
%}
%\@ifpackageloaded{babel}{\addto\extrasenglish{\refnamechanges}}{\refnamechanges}
\end_preamble
\options intoc,bibliography=totoc,index=totoc,BCOR10mm,captions=tableheading,titlepage
\use_default_options true
\master /usr/share/lyx/examples/thesis/thesis.lyx
\begin_modules
customHeadersFooters
\end_modules
\maintain_unincluded_children false
\language slovene
\language_package default
\inputencoding utf8
\fontencoding global
\font_roman "lmodern" "default"
\font_sans "lmss" "default"
\font_typewriter "lmtt" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures false
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command bibtex
\index_command default
\float_placement h
\paperfontsize 12
\spacing single
\use_hyperref true
\pdf_title "Your title"
\pdf_author "Your name"
\pdf_bookmarks true
\pdf_bookmarksnumbered true
\pdf_bookmarksopen true
\pdf_bookmarksopenlevel 1
\pdf_breaklinks false
\pdf_pdfborder true
\pdf_colorlinks false
\pdf_backref false
\pdf_pdfusetitle false
\pdf_quoted_options "pdfpagelayout=OneColumn, pdfnewwindow=true, pdfstartview=XYZ, plainpages=false"
\papersize a4paper
\use_geometry false
\use_package amsmath 2
\use_package amssymb 2
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 0
\use_minted 0
\branch Standalone
\selected 1
\filename_suffix 0
\color #ff0000
\end_branch
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 2
\paragraph_separation skip
\defskip medskip
\is_math_indent 1
\math_indentation default
\math_numbering_side default
\quotes_style german
\dynamic_quotes 0
\papercolumns 1
\papersides 2
\paperpagestyle fancy
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header
\begin_body
\begin_layout Left Header
\begin_inset Argument 1
status open
\begin_layout Plain Layout
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
\backslash
chaptername
\end_layout
\end_inset
\begin_inset space ~
\end_inset
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
\backslash
thechapter
\end_layout
\end_inset
\end_layout
\end_inset
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
\backslash
rightmark
\end_layout
\end_inset
\begin_inset Note Note
status collapsed
\begin_layout Plain Layout
Enable page headers and add the chapter to the header line.
\end_layout
\end_inset
\end_layout
\begin_layout Right Header
\begin_inset Argument 1
status open
\begin_layout Plain Layout
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
\backslash
leftmark
\end_layout
\end_inset
\end_layout
\end_inset
\end_layout
\begin_layout Left Footer
\begin_inset Argument 1
status open
\begin_layout Plain Layout
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
\backslash
thepage
\end_layout
\end_inset
\end_layout
\end_inset
\end_layout
\begin_layout Center Footer
\end_layout
\begin_layout Right Footer
\begin_inset Argument 1
status open
\begin_layout Plain Layout
\end_layout
\end_inset
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
\backslash
thepage
\end_layout
\end_inset
\end_layout
\begin_layout Chapter
Teoretični del
\begin_inset CommandInset label
LatexCommand label
name "chap:Teoretični-del"
\end_inset
\end_layout
\begin_layout Section
\family typewriter
bencoding
\family default
serializacija (bkodiranje)
\end_layout
\begin_layout Standard
V BEP-0003
\begin_inset CommandInset citation
LatexCommand cite
key "cohen08"
literal "false"
\end_inset
je opisan pojem bencoding serializacije, s katero je serializirana večina
paketov, ki se pošiljajo med vozlišči DHT in soležniki.
Strukturo, ki opisuje JSONu
\begin_inset CommandInset citation
LatexCommand cite
key "pezoa2016foundations"
literal "false"
\end_inset
podobno strukturirane podatke, vsebuje štiri podatkovne tipe:
\end_layout
\begin_layout Itemize
\series bold
niz
\series default
ali
\series bold
string
\series default
je serializiran tako, da ASCII številki dolžine niza sledi dvopičje in
za njim niz bajtov.
Primer:
\family typewriter
18:pozdravljen, svet!
\end_layout
\begin_layout Itemize
\series bold
število
\series default
ali
\series bold
int
\series default
je serializirano tako, da ASCII znaku
\family typewriter
i
\family default
sledi ASCII številka (lahko tudi negativna) in nato znak
\family typewriter
e
\family default
, ki označuje konec podatka.
Primer:
\family typewriter
i-1337e
\end_layout
\begin_layout Itemize
\series bold
seznam
\series default
ali
\series bold
list
\series default
je serializiran tako, da ASCII znaku
\family typewriter
l
\family default
sledi poljubno število podatkov lahko tudi različnih tipov, nato pa znak
\family typewriter
e
\family default
.
Primer:
\family typewriter
li-1337e18:pozdravljen, svet!lee
\end_layout
\begin_layout Itemize
\series bold
slovar
\series default
ali
\series bold
dict
\series default
vsebuje povezave (asociacije) med ključi in vrednosti.
Ključi so nizi, vrednosti pa so poljubni tipi.
Serializiran je podobno kot seznam, le da se začne z znakom
\family typewriter
d
\family default
.
Ključi in vrednosti so prepleteni; prvi in nato vsak drugi element predstavlja
ključe, vsakemu ključu sledeči podatek pa predstavlja vrednost pod tem
ključem.
Primer:
\family typewriter
d4:testli-1337e18:pozdravljen, svet!lee6:zzzzzzd7:podpira9:gnezdenjeee
\family default
, ki bi ga v JSONu predstavili kot
\family typewriter
{"test": [-1337, "pozdravljen, svet!", []], "zzzzzz": {"podpira": "gnezdenje"}}
\family default
.
Za hitrejše iskanje morajo biti vrednosti sortirane glede na ključ.
\end_layout
\begin_layout Section
Protokol BitTorrent
\end_layout
\begin_layout Subsection
Datoteka torrent/metainfo
\end_layout
\begin_layout Standard
Ko neke datoteke avtor želi deliti s protokolom BitTorrent, ustvari torrent
datoteko, ki je bkodiran slovar.
S to datoteko drugim omogoči prenos, zato jim jo na nedefiniran.
Glavni ključi v slovarju so
\begin_inset CommandInset citation
LatexCommand cite
key "cohen08"
literal "false"
\end_inset
:
\end_layout
\begin_layout Itemize
\family typewriter
announce
\family default
: URL sledilnika (za to nalogo brezpredmeten)
\end_layout
\begin_layout Itemize
\family typewriter
info: informacije o datotekah v torrentu
\end_layout
\begin_deeper
\begin_layout Itemize
\family typewriter
private
\family default
: za soležnike se sme spraševati le sledilnik in ne DHT
\begin_inset CommandInset citation
LatexCommand cite
key "harrison08"
literal "false"
\end_inset
\end_layout
\begin_layout Itemize
\family typewriter
name
\family default
: ime torrenta, v primeru, da torrent vsebuje le eno datoteko, pa ime datoteke
\end_layout
\begin_layout Itemize
\family typewriter
piece length
\family default
: velikost koščka.
Datoteke so razdeljene na več enako velikih koščkov, da jih je moč neodvisno
nalagati od drugih soležnikov.
Če je datotek več, so zaporedno spojene skupaj in razdeljene na koščke,
zato ena datoteka v prvi različici protokola ni vedno na mejah koščkov.
\end_layout
\begin_layout Itemize
\family typewriter
pieces
\family default
: niz dolžine
\begin_inset Formula $20n$
\end_inset
, kjer je
\begin_inset Formula $n$
\end_inset
število koščkov.
Za vsak košček je tu zapisana njegova zgoščena vrednost tipa SHA-1
\begin_inset CommandInset citation
LatexCommand cite
key "Eastlake2001"
literal "false"
\end_inset
\end_layout
\begin_layout Itemize
\family typewriter
length
\family default
: dolžina torrenta, prisotna le, če torrent vsebuje eno datoteko
\end_layout
\begin_layout Itemize
\family typewriter
files
\family default
: seznam datotek v torrentu, če je torrent večdatotečni.
Vsaka datoteka je predstavljena kot slovar:
\end_layout
\begin_deeper
\begin_layout Itemize
\family typewriter
length
\family default
: dolžina datoteke
\end_layout
\begin_layout Itemize
\family typewriter
path
\family default
: pot do datoteke kot seznam imen direktorijev in na koncu ime datoteke,
recimo
\family typewriter
[
\begin_inset Quotes gld
\end_inset
programi
\begin_inset Quotes grd
\end_inset
,
\begin_inset Quotes gld
\end_inset
travnik
\begin_inset Quotes grd
\end_inset
,
\begin_inset Quotes gld
\end_inset
src
\begin_inset Quotes grd
\end_inset
,
\begin_inset Quotes gld
\end_inset
dht.c
\begin_inset Quotes grd
\end_inset
]
\family default
predstavlja datoteko
\family typewriter
programi/travnik/src/dht.c
\end_layout
\end_deeper
\end_deeper
\begin_layout Standard
Namesto pošiljanja torrent datoteke lahko potencialnim soležnikom prenos
omogočimo tudi tako, da jih o njenem obstoju obvestimo samo z zgoščeno
vrednostjo slovarja
\family typewriter
info
\family default
(infohash).
Odjemalci s tem ključem napravijo poizvedbo po soležnikih v DHT in od njih
prenesejo slovar
\family typewriter
info
\family default
, ne pa tudi celotne datoteke, vendar slovar
\family typewriter
info vsebuje vse potrebno za prenos datotek
\family default
\begin_inset CommandInset citation
LatexCommand cite
key "hazel08"
literal "false"
\end_inset
.
Zgoščena vrednost se običajno pošilja kot magnetna povezava, torej shematski
zapis URI:
\end_layout
\begin_layout Standard
\family typewriter
magnet:?dn=
\series bold
ime torrenta
\series default
&xt=urn:btih:
\series bold
infohash
\end_layout
\begin_layout Standard
BitTorrent različica 2 ima drugačno strukturo, ki poda podobne podatke,
vendar na malce spremenjen način.
Uporablja recimo zgoščeno vrednost SHA256 in namesto ključa
\family typewriter
pieces
\family default
hrani samo eno zgoščeno vrednost, po sistemu
\family typewriter
merkle hash tree
\family default
\begin_inset CommandInset citation
LatexCommand cite
key "v2"
literal "false"
\end_inset
pa pridobi še ostale med prejemom datotek, s čimer se korenito zmanjša
velikost torrenta za velike datoteke.
\end_layout
\begin_layout Subsection
Povezava na soležnike za prevzem metapodatkov
\begin_inset CommandInset label
LatexCommand label
name "subsec:Povezava-na-soležnike"
\end_inset
\end_layout
\begin_layout Standard
Če odjemalec želi od soležnika prejeti info slovar, se nanj poveže bodisi
po
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
textmu TP
\end_layout
\end_inset
\begin_inset CommandInset citation
LatexCommand cite
key "norberg09"
literal "false"
\end_inset
bodisi po TCP
\begin_inset CommandInset citation
LatexCommand cite
key "cohen08"
literal "false"
\end_inset
.
V eksperimentalnem delu se na soležnike povezujem po TCP, saj je to bolj
preprosto.
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
textmu TP
\end_layout
\end_inset
sicer prinaša nove funkcije za bolj učinkovito rabo pasovne širine ob prenosu
datotek, vendar to za prenos slovarjev info ni kritično, saj so sami po
sebi relativno majhni.
\end_layout
\begin_layout Standard
Povezava po TCP za prevzem metapodatkov se začne z rokovanjem:
\end_layout
\begin_layout Itemize
Bajt 19, ki mu sledi niz
\family typewriter
BitTorrent protocol
\end_layout
\begin_layout Itemize
Osem rezerviranih bajtov 0, ki so na voljo za razširjanje protokola
\end_layout
\begin_layout Itemize
dvajsetbajtni infohash
\end_layout
\begin_layout Itemize
dvajsetbajtna unikatna identifikacijska številka odjemalca
\end_layout
\begin_layout Standard
Za rokovanjem sledi neskončno dolg pretok paketov.
Pred sporočilom paketa je štiribajtna neoznačena velikoendianska številka,
ki predstavlja dolžino sporočila.
Sporočila dolžine 0 so t.
i.
\shape italic
keepalive
\shape default
sporočila, ki jih prejemnik ignorira.
Paketi s sporočilom pa se začnejo z enobajtnim tipom sporočila, ki mu sledi
vsebina sporočila, vezana na ta tip.
\end_layout
\begin_layout Subsubsection
Razširitveni protokol
\end_layout
\begin_layout Standard
Prenos metapodatkov je opisan v standardu BEP-0009
\begin_inset CommandInset citation
LatexCommand cite
key "hazel08"
literal "false"
\end_inset
, vendar sam po sebi ne predstavlja številke tipa.
Za uporabo prenosa metapodatkov je najprej treba vzpostaviti razširitveni
protokol, ki odjemalcem omogoča dodajanje poljubnih protokolov v komunikacijo,
ne da bi med njimi prišlo do nekompatibilnosti.
\end_layout
\begin_layout Standard
Paketi razširitvenega protokola
\begin_inset CommandInset citation
LatexCommand cite
key "strigeus08"
literal "false"
\end_inset
imajo številko tipa 20.
Da sogovornika vesta, da lahko pošiljata razširitvene pakete, oba med rokovanje
m nastavita 19.
bit z desne v polju osmih rezerviranih bajtov.
Drugi bajt sporočila (šesti bajt celega paketa) predstavlja podtip.
Če je podtip 0, gre za razširitveno rokovanje — sogovornik pove, katere
razširitve podpira — v tem primeru bo preostanek sporočila bkodirana struktura:
\end_layout
\begin_layout Standard
\family typewriter
{
\begin_inset Quotes gld
\end_inset
m
\begin_inset Quotes grd
\end_inset
: {
\begin_inset Quotes gld
\end_inset
ut_metadata
\begin_inset Quotes grd
\end_inset
: 1},
\begin_inset Quotes gld
\end_inset
v
\begin_inset Quotes grd
\end_inset
:
\begin_inset Quotes gld
\end_inset
program odjemalca
\begin_inset Quotes grd
\end_inset
,
\begin_inset Quotes gld
\end_inset
metadata_size
\begin_inset Quotes grd
\end_inset
: 69420}
\end_layout
\begin_layout Standard
Slovar
\family typewriter
m
\family default
poda prevod z nizi poimenovanih dodatkov v številke.
Soležnik ob prejemu tega paketa ve, da lahko pakete tipa
\family typewriter
ut_metadata
\family default
pošilja sogovorniku tako, da podtip razširitvenega paketa nastavi na 1
in v preostanek sporočila vstavi telo protokola
\family typewriter
ut_metadata
\family default
.
\end_layout
\begin_layout Subsubsection
\family typewriter
P
\family default
revzem metapodatkov
\end_layout
\begin_layout Standard
Slovar metadata se konceptualno razdeli na delčke velikosti 16384 bajtov
(zadnji delček je lahko manjši), soležnik posamezen delček zahteva s paketom
\begin_inset CommandInset citation
LatexCommand cite
key "hazel08"
literal "false"
\end_inset
:
\end_layout
\begin_layout Itemize
4 bajtna dolžina sledečih polj
\end_layout
\begin_layout Itemize
bajt 20
\end_layout
\begin_layout Itemize
bajt vrednosti, kakršno je dobil v
\family typewriter
m
\family default
slovarju od soležnika pod ključem
\family typewriter
ut_metadata
\end_layout
\begin_layout Itemize
bkodiran slovar
\family typewriter
{
\begin_inset Quotes gld
\end_inset
msg_type
\begin_inset Quotes grd
\end_inset
: 0,
\begin_inset Quotes gld
\end_inset
piece
\begin_inset Quotes grd
\end_inset
: 5}
\family default
, kjer 5 predstavlja številko delčka, ki ga zahteva, tip 0 pa predstavlja
zahtevo
\end_layout
\begin_layout Standard
Sogovornik lahko bodisi odgovori z zavrnitvijo oblike
\family typewriter
{
\begin_inset Quotes gld
\end_inset
msg_type
\begin_inset Quotes grd
\end_inset
: 2,
\begin_inset Quotes gld
\end_inset
piece
\begin_inset Quotes grd
\end_inset
: 5}
\family default
, če nima vseh delčkov (za preverjanje zgoščene vrednosti slovarja info
je potrebno poznavanje vseh koščkov), bodisi odgovori s paketom
\end_layout
\begin_layout Itemize
4 bajtna dolžina sledečih polj
\end_layout
\begin_layout Itemize
bajt 20
\end_layout
\begin_layout Itemize
bajt vrednosti, kakršno je dobil v
\family typewriter
m
\family default
slovarju od soležnika pod ključem
\family typewriter
ut_metadata
\end_layout
\begin_layout Itemize
bkodiran slovar
\family typewriter
{
\begin_inset Quotes gld
\end_inset
msg_type
\begin_inset Quotes grd
\end_inset
: 1,
\begin_inset Quotes gld
\end_inset
piece
\begin_inset Quotes grd
\end_inset
: 5,
\begin_inset Quotes gld
\end_inset
total_size
\begin_inset Quotes grd
\end_inset
: 69420}
\family default
, kjer 5 predstavlja številko delčka, ki ga pošilja, tip 1 predstavlja podatke,
69420 pa je celotna dolžina slovarja info.
\end_layout
\begin_layout Itemize
bajti delčka bkodiranega slovarja info
\end_layout
\begin_layout Standard
Preden lahko odjemalec metapodatke uporabi (torej pošilja naprej ali začne
s prenosom torrenta), mora prenesti vse delčke in preveriti veljavnost
zgoščene vrednosti.
Če gre za BitTorrent različice 1, je ta zgoščena vrednost SHA-1, če pa
gre za BitTorrent različice 2, je zgoščena vrednost SHA-256
\begin_inset CommandInset citation
LatexCommand cite
key "v2"
literal "false"
\end_inset
.
\end_layout
\begin_layout Section
Protokol BitTorrent DHT
\end_layout
\begin_layout Standard
Naloga protokola DHT, standardiziranega 31.
januarja 2008 v standardu BEP-0005
\begin_inset CommandInset citation
LatexCommand cite
key "norberg08"
literal "false"
\end_inset
, je vzdrževanje seznama soležnikov v roju vseh obstoječih torrentov, ki
obstajajo in niso zasebni (več o tem v uvodu).
\end_layout
\begin_layout Standard
Komunikacija med vozlišči poteka izključno po protokolu UDP v obliki bkodiranih
slovarjev.
\end_layout
\begin_layout Subsection
Sestava grafa
\end_layout
\begin_layout Standard
Povezave med vozlišči si predstavljajmo kot velik usmerjen graf.
Vsako vozlišče ima približno
\begin_inset Formula $K\log_{2}n$
\end_inset
(konstanta
\begin_inset Formula $K=8$
\end_inset
,
\begin_inset Formula $n$
\end_inset
je število vseh vozlišč na svetu) povezav na druga vozlišča, ki jih hrani
v svoji lastni usmerjevalni tabeli, ki vsebuje IP naslov in vrata vozlišč
ter njihove IDje.
ID vozlišča si vsako vozlišče ob prvem zagonu izmisli naključno.
S tem je zagotovljena homogena porazdelitev vozlišč po spektru možnih IDjev.
\end_layout
\begin_layout Standard
Ko vozlišče izve za novo vozlišče, s katerim lahko komunicira
\begin_inset Foot
status open
\begin_layout Plain Layout
torej mu na poizvedbe odgovarja, kar zaradi obstoja NAT in požarnih zidov
ni samoumevno
\end_layout
\end_inset
, ga zapiše v svojo usmerjevalno tabelo, če je v košu, v katerega to vozlišče
spada, dovolj prostora.
Za vsako vozlišče implementacije hranijo tudi čas zadnjega odgovora na
paket.
Vozlišča, ki se nekaj minut ne oglasijo na poizvedbe, se iz tabele odstrani.
\end_layout
\begin_layout Standard
Koši so definirani kot skupki največ osmih vozlišč.
Ko program želi vstaviti novo vozlišče v usmerjevalno tabelo, preveri,
če ima koš, v katerega to vozlišče spada, prostor.
V kolikor je v košu prostor, shrani vozlišče, v nasprotnem primeru pa preveri,
če tako ID novega vozlišča kot tudi ID sebe pripadata v isti koš
\begin_inset Foot
status open
\begin_layout Plain Layout
Vozlišče sebe sicer nikoli ne shrani v usmerjevalno tabelo.
\end_layout
\end_inset
; v tem primeru ta koš razpolovi na dva dela, da lahko vanj vstavi novo
vozlišče.
Če noben izmed teh dveh pogojev ne vstavi najdenega vozlišča v usmerjevalno
tabelo, je vozlišče bodisi zavrženo bodisi vstavljeno v predpomnilnik,
da bo vstavljeno v prihodnje.
\end_layout
\begin_layout Standard
Program začne z enim košem, ki bo hranil vozlišča z identifikacijskimi številkam
i od 00...00 do ff...ff.
Razpolovitev koša v takem stanju bi iz začetnega koša izdelala dva koša
s ključi od 00...00 do 7f...ff ter od 80...00 do ff...ff.
Druga razpolovitev se lahko izvede le na enem izmed teh dveh košev, na
tistem namreč, katerega naslovno območje zavzema ID vozlišča tega programa.
Nadaljnje razpolovitve vodijo v stanje, kjer je
\begin_inset Formula $\log_{2}n$
\end_inset
košev, vsak koš pa predstavlja podmnožico vseh možnih IDjev z močjo
\begin_inset Formula $2^{160-i}$
\end_inset
, kjer je
\begin_inset Formula $i$
\end_inset
indeks koša od 1 do
\begin_inset Formula $\log_{2}n$
\end_inset
.
Ker vsak koš vsebuje le
\begin_inset Formula $K$
\end_inset
vozlišč in ker je zaradi algoritma razpolavljanja košev največ košev okoli
IDja trenutnega vozlišča, so v usmerjevalni tabeli tega vozlišča najbolj
reprezentirana vozlišča, katerih ID je podoben IDju trenutnega vozlišča.
\begin_inset CommandInset citation
LatexCommand cite
key "maymounkov2002kademlia"
literal "false"
\end_inset
\end_layout
\begin_layout Subsection
Komunikacija in izvajanje poizvedb
\end_layout
\begin_layout Standard
Da se program prvič poveže v omrežje, mora najprej najti vsaj enega člana
omrežja.
Algoritem za povezavo v omrežje ni definiran.
Implementacije ob izhodu iz programa usmerjevalno tabelo shranijo na disk,
da ob ponovnem zagonu vsaj nekaj vozlišč iz prejšnega zagona še deluje.
Če se nobeno vozlišče ne odzove, vpraša centraliziran strežnik, t.
i
\shape italic
bootstrap node
\shape default
, ki hrani podatke o veliki količini vozlišč.
\end_layout
\begin_layout Standard
Za pridobivanje seznama soležnikov odjemalec v usmerjevalni tabeli poišče
\begin_inset Formula $t$
\end_inset
infohashu najbližjih vozlišč (lahko tudi cel koš, v katerega spada infohash).
Razdaljo definiramo kot operacijo XOR med infohashom in IDjem.
Tem vozliščem pošlje paket tipa
\family typewriter
get_peers
\family default
.
Odgovor na ta paket je seznam soležnikov.
V kolikor pa kontaktirano vozlišče ne pozna soležnikov, pa vrne seznam
vozlišč iz njegove usmerjevalne tabele, ki so temu infohashu najbližje.
Program za vsak torrent hrani
\begin_inset Formula $v$
\end_inset
najbližjih vozlišč, ki jih vsake toliko časa kontaktira za nove soležnike
in bližja vozlišča.
Ob prejetju seznama vozlišč se torrent odjemalec vpiše kot soležnika in
s tem doda v roj tako, da vozlišču pošlje paket tipa
\family typewriter
announce_peer
\family default
.
\end_layout
\begin_layout Standard
Iskanje po DHT se torej obnaša kot iskanje po binarnem drevesu in ima kompleksno
st
\begin_inset Formula $O(\log n)$
\end_inset
.
\end_layout
\begin_layout Subsubsection
Sestava paketa in osnovni tipi paketov
\end_layout
\begin_layout Standard
Paketi se pošiljajo po UDP.
Celotna vsebina UDP paketa je bkodiran slovar
\begin_inset CommandInset citation
LatexCommand cite
key "norberg08"
literal "false"
\end_inset
.
Paketi se delijo na zahteve in na odgovore, da pa vozlišče prejeto zahtevo
lahko poveže s poslanim odgovorom, pa vsi paketi vsebujejo ključ
\family typewriter
t
\family default
s kratkim nizom bajtov, ki bo prepisan v odgovor.
Ključ
\family typewriter
y
\family default
v paketu predstavlja tip paketa, torej niz
\family typewriter
q
\family default
za zahtevo, niz
\family typewriter
r
\family default
za odgovor ali niz
\family typewriter
e
\family default
za poročilo o napaki, slednje vsebuje standardizirano kodo napake in tekstovno
sporočilo.
Vozlišče lahko ime programa in različico predstavi s štiribajtnim nizom
pod ključem
\family typewriter
v
\family default
.
Vsaka poizvedba ima pod ključem
\family typewriter
a/id
\family default
(odgovor pa pod ključem
\family typewriter
r/id
\family default
) zapisan ID pošiljatelja — tako je en
\family typewriter
ping
\family default
paket dovolj, da vozlišče izve za novo vozlišče in ga potencialno vstavi
v usmerjevalno tabelo.
\end_layout
\begin_layout Standard
Parametri zahteve so zapisani v slovarju pod ključem
\family typewriter
a
\family default
, parametri odziva so pod ključem
\family typewriter
r
\family default
, tip zahteve pa je kot niz naveden pod ključem
\family typewriter
q
\family default
.
Obstajajo štirje:
\end_layout
\begin_layout Paragraph
find_node
\end_layout
\begin_layout Standard
Zahteva vsebuje ključ
\family typewriter
target
\family default
, v katerem je dvajsetbajtni niz zgoščene vrednosti iskanega vozlišča.
Odgovor pod ključem
\family typewriter
nodes
\family default
vsebuje niz
\begin_inset Formula $K$
\end_inset
vozlišč iz usmerjevalne tabele, katerih ID je najbližji iskanemu.
Vozlišča si en za drugim sledijo v nizu, vsako pa je dolgo 26 znakov, 20
za ID, 4 za IP naslov in 2 za vrata.
V primeru IPv6 je seveda dolžina enega vozlišča 38, ključ pa se imenuje
\family typewriter
nodes6
\family default
.
\end_layout
\begin_layout Paragraph
get_peers
\end_layout
\begin_layout Standard
Sistem je podoben ukazu
\family typewriter
find_node
\family default
, le da je namesto parametra
\family typewriter
target
\family default
podan parameter
\family typewriter
infohash
\family default
z dvajsetbajtnim infohashom iskanega torrenta.
Odgovor na paket lahko poleg
\family typewriter
nodes
\family default
in
\family typewriter
nodes6
\family default
vsebuje tudi
\family typewriter
values
\family default
, seznam nizov, kjer vsak niz predstavlja IP naslov in vrata soležnika v
roju, ter ključ
\family typewriter
token
\family default
, pod katerim je zapisan niz, ki ga mora vozlišče, ki v seznam želi zapisati
svoj naslov, napisati pod ključem
\family typewriter
token
\family default
v paketu
\family typewriter
announce
\family default
_peer.
\end_layout
\begin_layout Paragraph
announce_peer
\end_layout
\begin_layout Standard
Vozlišče ga pošlje vozlišču, katerega ID je blizu infohasha torrenta, da
se bodo nanj z BitTorrent protokolom povezali ostali soležniki v roju in
prenašali koščke torrenta.
Parametri zahteve so
\family typewriter
port
\family default
,
\family typewriter
info_hash
\family default
in token iz prej prejetega odgovora na
\family typewriter
get_peers
\family default
.
Žeton
\family typewriter
token
\family default
poskrbi, da s ponarejanjem izvora UDP/IP paketov ne moremo v seznam vnesti
drugih računalnikov, temveč le tistega, ki je prejel odgovor na
\family typewriter
get_peers
\family default
.
Vozlišče, ki paket prejme, podatke shrani v seznam soležnikov.
\end_layout
\begin_layout Paragraph
ping
\end_layout
\begin_layout Standard
Poleg
\family typewriter
id
\family default
zahteva in odgovor nimata dodatnih parametrov.
Namenjen je preizkusu delovanja vozlišča s čim manjšo procesorsko obremenitvijo.
\end_layout
\begin_layout Standard
\begin_inset Branch Standalone
inverted 0
status open
\begin_layout Standard
\begin_inset Note Note
status open
\begin_layout Plain Layout
The contents of this branch is only output if this chapter is processed
on its own, i.
\begin_inset space \thinspace{}
\end_inset
e., not from the master.
This allows you to have a bibliography and a nomenclature if you only want
to output this chapter.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
\begin_inset CommandInset include
LatexCommand include
filename "Bibliography.lyx"
\end_inset
\end_layout
\end_inset
\end_layout
\end_body
\end_document
