1 files changed, 1359 insertions, 0 deletions
diff --git a/inf/rn/dok/lyx/teoretični.lyx b/inf/rn/dok/lyx/teoretični.lyx
new file mode 100644
index 0000000..2db1b48
--- /dev/null
+++ b/inf/rn/dok/lyx/teoretični.lyx
@@ -0,0 +1,1359 @@
+#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 (citiraj) 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 (citiraj) 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 (citiraj) š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 (citiraj BEP):
+\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 (citiraj BEP 27)
+\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 (citiraj
+ SHA-1)
+\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
+ (citiraj metadata transfer BEP 9).
+ 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
+ (citiraj) 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
+
+ (citiraj 
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+textmu TP
+\end_layout
+
+\end_inset
+
+) bodisi po TCP.
+ 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, 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 (citiraj BEP 10) 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
+ (citiraj BEP 9):
+\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 (citiraj BEP
+ bittorrent v2).
+\end_layout
+
+\begin_layout Section
+Protokol BitTorrent DHT
+\end_layout
+
+\begin_layout Standard
+Naloga protokola DHT, standardiziranega 31.
+ januarja 2008 v standardu BEP-0005, 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.
+\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 (citiraj BEP 5).
+ 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