From 2d52f3013988535890981ad0dbd95a41810137e0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Anton=20Luka=20=C5=A0ijanec?= Date: Tue, 6 Aug 2024 01:35:27 +0200 Subject: =?UTF-8?q?ana1=20u=C4=8Denje=20vrsar=20lahko=20no=C4=8D?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- "\305\241ola/\304\215lanki/dht/.gitignore" | 3 + "\305\241ola/\304\215lanki/dht/dokument.lyx" | 2306 ++++++++++++++++++++++++++ 2 files changed, 2309 insertions(+) create mode 100644 "\305\241ola/\304\215lanki/dht/.gitignore" create mode 100644 "\305\241ola/\304\215lanki/dht/dokument.lyx" (limited to 'šola/članki') diff --git "a/\305\241ola/\304\215lanki/dht/.gitignore" "b/\305\241ola/\304\215lanki/dht/.gitignore" new file mode 100644 index 0000000..abd26b3 --- /dev/null +++ "b/\305\241ola/\304\215lanki/dht/.gitignore" @@ -0,0 +1,3 @@ +*.svg +*.png +*.tsv diff --git "a/\305\241ola/\304\215lanki/dht/dokument.lyx" "b/\305\241ola/\304\215lanki/dht/dokument.lyx" new file mode 100644 index 0000000..af668ed --- /dev/null +++ "b/\305\241ola/\304\215lanki/dht/dokument.lyx" @@ -0,0 +1,2306 @@ +#LyX 2.4 created this file. For more info see https://www.lyx.org/ +\lyxformat 620 +\begin_document +\begin_header +\save_transient_properties true +\origin unavailable +\textclass paper +\begin_preamble +% for subfigures/subtables +\usepackage[caption=false,font=footnotesize]{subfig} +\usepackage{textcomp} +\usepackage[ + type={CC}, + modifier={by-sa}, + version={3.0}, +]{doclicense} +\usepackage{bera}% optional: just to have a nice mono-spaced font +\usepackage{listings} +\usepackage{xcolor} +\lstset{ + extendedchars=true, + literate={č}{{\v{c}}}1 {ž}{{\v{z}}}1 {š}{{\v{s}}}1, +} + +\colorlet{punct}{red!60!black} +\definecolor{background}{HTML}{EEEEEE} +\definecolor{delim}{RGB}{20,105,176} +\colorlet{numb}{magenta!60!black} + +\lstdefinelanguage{json}{ + basicstyle=\normalfont\ttfamily, + numbers=left, + numberstyle=\scriptsize, + stepnumber=1, + numbersep=8pt, + showstringspaces=false, + breaklines=true, + frame=lines, + backgroundcolor=\color{background}, + literate= + *{0}{{{\color{numb}0}}}{1} + {1}{{{\color{numb}1}}}{1} + {2}{{{\color{numb}2}}}{1} + {3}{{{\color{numb}3}}}{1} + {4}{{{\color{numb}4}}}{1} + {5}{{{\color{numb}5}}}{1} + {6}{{{\color{numb}6}}}{1} + {7}{{{\color{numb}7}}}{1} + {8}{{{\color{numb}8}}}{1} + {9}{{{\color{numb}9}}}{1} + {:}{{{\color{punct}{:}}}}{1} + {,}{{{\color{punct}{,}}}}{1} + {\{}{{{\color{delim}{\{}}}}{1} + {\}}{{{\color{delim}{\}}}}}{1} + {[}{{{\color{delim}{[}}}}{1} + {]}{{{\color{delim}{]}}}}{1}, +} +\end_preamble +\options journal +\use_default_options false +\maintain_unincluded_children no +\language slovene +\language_package babel +\inputencoding utf8 +\fontencoding auto +\font_roman "default" "default" +\font_sans "default" "default" +\font_typewriter "default" "default" +\font_math "auto" "auto" +\font_default_family default +\use_non_tex_fonts false +\font_sc false +\font_roman_osf false +\font_sans_osf false +\font_typewriter_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 +\float_alignment class +\paperfontsize default +\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 default +\use_geometry true +\use_package amsmath 1 +\use_package amssymb 1 +\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_formatted_ref 0 +\use_minted 0 +\use_lineno 0 +\index Index +\shortcut idx +\color #008000 +\end_index +\leftmargin 0.5cm +\topmargin 0.5cm +\rightmargin 0.5cm +\bottommargin 1.25cm +\headheight 0.5cm +\headsep 0.5cm +\footskip 0.5cm +\columnsep 0.5cm +\secnumdepth 3 +\tocdepth 3 +\paragraph_separation indent +\paragraph_indentation default +\is_math_indent 0 +\math_numbering_side default +\quotes_style german +\dynamic_quotes 0 +\papercolumns 2 +\papersides 1 +\paperpagestyle default +\tablestyle default +\tracking_changes false +\output_changes false +\change_bars false +\postpone_fragile_content false +\html_math_output 0 +\html_css_as_file 0 +\html_be_strict false +\docbook_table_output 0 +\docbook_mathml_prefix 1 +\end_header + +\begin_body + +\begin_layout Title +Kaj prenašamo s protokolom BitTorrent? +\end_layout + +\begin_layout Author +Anton Luka Šijanec, + +\begin_inset CommandInset href +LatexCommand href +name "anton@sijanec.eu" +target "anton@sijanec.eu" +type "mailto:" +literal "true" + +\end_inset + + +\end_layout + +\begin_layout Institution +Fakulteta za računalništvo in informatiko Univerze v Ljubljani +\end_layout + +\begin_layout Abstract +V članku predstavimo metodo za učinkovito in za omrežje neinvazivno metodo prenašanja metapodatkov iz pomožnega omrežja Kademlia mainline DHT protokola BitTorrent za izmenjavo datotek. + Sledi pregled/analiza z opisano metodo pridobljenih metapodatkov o datotekah na voljo v omrežju BitTorrent. +\end_layout + +\begin_layout Abstract +Porazdeljene razpršilne tabele (angl. + distributed hash table) so razpršilne tabele, + ki podatke, + ponavadi so to dokumenti, + strukturirani kot vrednost in njej pripadajoči ključ, + hranijo distribuirano na več vozliščih, + na katerih se podatki shranjujejo. + V računalniških sistemih se DHT uporablja za hrambo podatkov v omrežjih P2P (angl. + peer to peer), + kjer se podatki vseh uporabnikov enakomerno porazdelijo med vozlišča in so tako decentralizirani in preprosto dostopni članom omrežja. + Ker se podatki izmenjujejo znotraj omrežja na vozliščih, + ki z izvorom in destinacijo podatkov niso povezani, + jih lahko vozlišča v velikih količinah shranjujejo za potrebe statistične analize omrežja. +\end_layout + +\begin_layout Abstract +V raziskavi preverimo praktično zmožnost pridobivanja velike količine podatkov v omrežju BitTorrent za P2P izmenjavo datotek, + nato še analiziramo pridobljene podatke. + Vsaka poizvedba po seznamu imetnikov datotek vsebuje ključ podatka v DHT in se prenese preko okoli +\begin_inset Formula $\log_{2}n$ +\end_inset + + vozlišč, + kjer je +\begin_inset Formula $n$ +\end_inset + + število vseh uporabnikov v omrežju. + Ker vsaka poizvedba obišče tako veliko število vozlišč, + lahko med poizvedbo eno drugače nepovezano vozlišče prejme veliko obstoječih ključev v omrežju, + ki jih lahko uporabi za prenos metapodatkov v omrežju BitTorrent. +\end_layout + +\begin_layout Abstract +Osredotočili smo se le na na pridobivanje metapodatkov v omrežju BitTorrent, + samih datotek, + na katere se le-ti metapodatki sklicujejo in so v omrežju na voljo, + ker jih ponujajo drugi računalniki, + pa tako vsled tehničnih (njihove ogromne skupne velikosti) kot tudi pravnih razlogov (avtorsko zaščitena in protizakonita vsebina) nismo prenašali. + Metapodatki konceptualno sicer niso shranjeni v DHT (namesto metapodatkov o datotekah so v omrežju shranjeni seznami računalnikov, + od katerih si metapodatke lahko prenesemo), + vendar odkrivanje njihovega obstoja omogoči DHT. +\end_layout + +\begin_layout Abstract +S pridobljenimi metapodatki ugotovimo, + kateri odjemalci so najpopularnejši ter kakšna je razporeditev vsebine glede na tip datotek, + ki je na voljo preko protokola BitTorrent. +\end_layout + +\begin_layout Keywords +porazdeljena razpršilna tabela, + porazdeljeni sistemi, + omrežje P2P, +\end_layout + +\begin_layout Keywords +podatkovno rudarjenje, + BitTorrent +\end_layout + +\begin_layout Section +Introduction +\end_layout + +\begin_layout Subsection +Distribucija datotek po principu P2P +\end_layout + +\begin_layout Standard +Koncept P2P (angl. + +\shape italic +peer-to-peer +\shape default +) predstavlja alternativen način distribucije identičnih datotek večim odjemalcem. + Namesto enega strežnika, + ki iste podatke odjemalcem pošlje vsakič znova, + v omrežjih P2P za distribucijo datotek vsak odjemalec podatke tako prejema kot tudi pošilja. + Odjemalec prejeto vsebino tudi sam deli drugim te vsebine željanim odjemalcem, + s čimer razbremeni ostale odjemalce. +\end_layout + +\begin_layout Standard +Odjemalec za druge izve s pomočjo centralnega strežnika ali pa drugačnega signalizacijskega protokola. + Ker se povezujejo neposredno, + medsebojno poznajo svoje internetne naslove. +\end_layout + +\begin_layout Subsection +Protokol BitTorrent +\end_layout + +\begin_layout Standard +Od 2008 +\begin_inset CommandInset citation +LatexCommand cite +key "harrison07" +literal "false" + +\end_inset + + je eden izmed popularnejših protokolov za P2P distribucijo BitTorrent, + razvit že 2001 +\begin_inset CommandInset citation +LatexCommand cite +key "cohen01" +literal "false" + +\end_inset + +. + Zaradi razširljive zasnove ga je moč dopolnjevati — + dodajati nove funkcije. + Sprva je BitTorrent temeljil na centralnih strežnikih za koordinacijo rojev, + od leta 2005 pa z uvedbo protokola DHT lahko deluje povsem neodvisno. +\begin_inset CommandInset citation +LatexCommand cite +key "jones15" +literal "false" + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset Float table +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\noindent +\align center +\begin_inset Tabular + + + + + + + +\begin_inset Text + +\begin_layout Plain Layout +Pojem +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +Angleško +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +Razlaga +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +soležnik +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +peer +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +odjemni program na računalniku, + za povezavo nanj potrebujemo IP naslov in vrata +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +roj +\begin_inset CommandInset citation +LatexCommand cite +key "dis" +literal "false" + +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +swarm +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +več soležnikov, + ki prenašajo datoteke nekega torrenta +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +torrent/ +\begin_inset Newline newline +\end_inset + +metainfo +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +torrent/ +\begin_inset Newline newline +\end_inset + +metainfo +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +datoteka z metapodatki datotek; + imena, + velikosti, + zgoščene vrednosti in drugo +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +sledilnik +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +tracker +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +koordinacijski strežnik z naslovi soležnikov v rojih +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +košček +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +piece +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +delček datoteke konstantne dolžine +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +infohash +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +infohash +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +zgoščena vrednost serializiranih podatkov pod ključem +\family typewriter +info +\family default + v torrentu, + ki unikatno opišejo ključne metapodatke o torrentu +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +objavi +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +announce +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +pošiljanje obvestila v DHT ali na sledilnik, + da se odjemalec želi priključiti nekemu roju +\end_layout + +\end_inset + + + + +\end_inset + + +\begin_inset Caption Standard + +\begin_layout Plain Layout +Slovar pojmov BitTorrenta +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +Za prenos je treba poznati metapodatke o obstoječih datotekah, + ki so shranjeni v t. + i. + obliki .torrent, + strojno berljivi z bencoding serializirani datoteki. + Vsebujejo vsaj imena in poti datotek ter njihove zgoščene vrednosti, + ime torrenta, + lastnosti prenosa in velikost koščka. +\end_layout + +\begin_layout Standard +V raziskavi ne iščemo soležnikov s sledilniki in ne prenašamo datotek, + temveč samo prenašamo in analiziramo metapodatke. +\end_layout + +\begin_layout Subsection +Protokol Kademlia mainline DHT +\end_layout + +\begin_layout Standard +V BitTorrent je za iskanje soležnikov v roju uporabljen DHT (angl. + +\shape italic +distributed hash table +\shape default +), + ki odpravi odvisnost od sledilnika. +\end_layout + +\begin_layout Standard +\begin_inset Float table +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\noindent +\align center +\begin_inset Tabular + + + + + + + +\begin_inset Text + +\begin_layout Plain Layout +Pojem +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +Angleško +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +Razlaga +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +vozlišče +\begin_inset CommandInset citation +LatexCommand cite +key "dis" +literal "false" + +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +node +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +odjemni program na računalniku +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +usmerjevalna +\begin_inset Newline newline +\end_inset + +tabela +\begin_inset CommandInset citation +LatexCommand cite +key "dis" +literal "false" + +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +routing +\begin_inset Newline newline +\end_inset + +table +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +seznam vozlišč (IP, + vrata, + ID), + ki ga hrani posamezno vozlišče +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +ID vozlišča +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +node ID +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +160-bitna ob zagonu generirana naključna vozlišču pripadajoča številka +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +merilo +\begin_inset Newline newline +\end_inset + +razdalje +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +distance +\begin_inset Newline newline +\end_inset + +metric +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +funkcija (XOR), + ki izrazi razdaljo med vozliščema kot 160-bitno številko +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +koš +\begin_inset CommandInset citation +LatexCommand cite +key "dis" +literal "false" + +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +bucket +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +element usmerjevalne tabele, + ki glede na merilo razdalje vsebuje bližnja vozlišča +\end_layout + +\end_inset + + + + +\end_inset + + +\begin_inset Caption Standard + +\begin_layout Plain Layout +Slovar pojmov Kademlie. + Slovenski prevodi niso ustaljeni. +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +Na visokem nivoju gre za abstraktno razpršilno tabelo, + shranjeno porazdeljeno na velikem omrežju vozlišč. + Podpira naslednji operaciji +\begin_inset CommandInset citation +LatexCommand cite +key "norberg08" +literal "false" + +\end_inset + +: +\end_layout + +\begin_layout Paragraph + +\family typewriter +get_peers +\end_layout + +\begin_layout Standard +Vrne seznam soležnikov (IP naslov in vrata) za torrent, + opisan z njegovim infohashom. +\end_layout + +\begin_layout Paragraph + +\family typewriter +announce +\begin_inset Note Note +status open + +\begin_layout Plain Layout +qbittorrent pravi sporoči, + v deluge in transmission nisem našel prevoda +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +V seznam soležnikov za torrent, + opisan z njegovim infohashom, + vstavi IP naslov in vrata pošiljatelja zahteve. +\end_layout + +\begin_layout Standard +V raziskavi s sodelovanjem v DHT prestrezamo obstoječe ključe v razpršilni tabeli, + z njimi pridobimo soležnike, + od katerih prenesemo metapodatke o torrentih za kasnejšo analizo. +\end_layout + +\begin_layout Standard +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset Graphics + filename /root/projects/sola-gimb-4/inf/rn/predst/dht.svg + width 100col% + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +Shematski prikaz DHT +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Section +Opis standardov +\end_layout + +\begin_layout Paragraph +Serializacija bkodiranje +\family typewriter +(bencoding) +\end_layout + +\begin_layout Standard +V BEP-0003 +\begin_inset CommandInset citation +LatexCommand cite +key "cohen08" +literal "false" + +\end_inset + + je opisan bencoding. + Z njim je serializirana večina struktur BitTorrenta in Kademlie. + Bkodiranje je podobno bolj znanemu JSONu +\begin_inset CommandInset citation +LatexCommand cite +key "pezoa2016foundations" +literal "false" + +\end_inset + + — + vsebuje štiri podatkovne tipe: + niz, + število, + seznam in slovar. +\end_layout + +\begin_layout Paragraph +Datoteka metainfo/.torrent +\end_layout + +\begin_layout Standard +Za distribucijo vsebine s protokolom BitTorrent ustvarimo .torrent datoteko, + bkodiran slovar z metapodatki, + nujnimi za prenos datotek. + Za raziskavo so pomembni metapodatki pod ključem +\family typewriter +info +\family default +: +\begin_inset CommandInset citation +LatexCommand cite +key "cohen08" +literal "false" + +\end_inset + + +\end_layout + +\begin_layout Itemize + +\family typewriter +private +\family default +: + prepoved objavljanja preko DHT, + le preko sledilnikov (ti torrenti niso zajeti v raziskavi) +\begin_inset CommandInset citation +LatexCommand cite +key "harrison08" +literal "false" + +\end_inset + + +\end_layout + +\begin_layout Itemize + +\family typewriter +name +\family default +: + ime torrenta oz. + datoteke za enodatotečne torrente +\end_layout + +\begin_layout Itemize + +\family typewriter +piece length +\family default +: + velikost koščka — + datoteke so spojene skupaj in razdeljene na enako velike koščke +\end_layout + +\begin_layout Itemize + +\family typewriter +pieces +\family default +: + niz dolžine +\begin_inset Formula $20n$ +\end_inset + + ( +\begin_inset Formula $n$ +\end_inset + + je število koščkov) s SHA-1 vrednostmi koščkov +\begin_inset CommandInset citation +LatexCommand cite +key "Eastlake2001" +literal "false" + +\end_inset + + +\end_layout + +\begin_layout Itemize + +\family typewriter +length +\family default +: + dolžina datoteke za enodatotečne torrente +\end_layout + +\begin_layout Itemize + +\family typewriter +files +\family default +: + seznam datotek v večdatotečnem torrentu — + vsaka datoteka je predstavljena kot slovar z +\family typewriter +length +\family default + in +\family typewriter +path +\family default +. +\end_layout + +\begin_layout Standard +Kdor pozna infohash, + lahko od soležnika prenese metainfo in posledično tudi pripadajoče datoteke. + Roj najde in se vanj vključi s poizvedbo v DHT, + saj je infohash ključ v tej razpršilni tabeli +\begin_inset CommandInset citation +LatexCommand cite +key "hazel08" +literal "false" + +\end_inset + +. + Infohash običajno oblikujemo v t. + i. + magnetno povezavo (magnet URI): + +\family typewriter + magnet:?dn= +\series bold +ime torrenta +\series default +&xt=urn:btih: +\series bold +infohash +\end_layout + +\begin_layout Standard +Druga različica BitTorrenta ima drugačno metainfo strukturo s podobnimi podatki. + Uporablja SHA-256 in namesto +\family typewriter +pieces +\family default + uporablja +\family typewriter +merkle hash tree +\family default + +\begin_inset CommandInset citation +LatexCommand cite +key "v2" +literal "false" + +\end_inset + + za zgoščene vrednosti datotek. +\end_layout + +\begin_layout Paragraph +Graf DHT +\end_layout + +\begin_layout Standard +DHT vzdržuje sezname soležnikov v roju vseh obstoječih torrentov. + Vozlišča komunicirajo preko UDP in so del velikega usmerjenega grafa, + vsako s +\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) povezavami — + vpisi v usmerjevalno tabelo. +\end_layout + +\begin_layout Standard +Vozlišče skrbi za urejeno usmerjevalno tabelo dosegljivih +\begin_inset Foot +status open + +\begin_layout Plain Layout +dvosmerna komunikacija zaradi NAT ni samoumevna +\end_layout + +\end_inset + + vozlišč v koših; + +\begin_inset Formula $i$ +\end_inset + +ti koš hrani do +\begin_inset Formula $K$ +\end_inset + + med +\begin_inset Formula $2^{i}$ +\end_inset + + in +\begin_inset Formula $2^{i-1}$ +\end_inset + + po merilu XOR oddaljenih vozlišč, + torej je shranjenih veliko bližnjih in malo zelo oddaljenih vozlišč. +\begin_inset CommandInset citation +LatexCommand cite +key "maymounkov2002kademlia" +literal "false" + +\end_inset + + +\end_layout + +\begin_layout Paragraph +Poizvedbe po grafu +\end_layout + +\begin_layout Standard +Sprehod po grafu med poljubnima vozliščema je torej dolg v povprečju +\begin_inset Formula $\log n$ +\end_inset + + ( +\begin_inset Formula $n$ +\end_inset + + kot prej). + Roj torrenta z infohashom +\begin_inset Formula $x$ +\end_inset + + je shranjen na vozliščih z ID blizu +\begin_inset Formula $x$ +\end_inset + +, + tedaj ima poizvedba po soležnikih/objavljanje soležnika časovno kompleksnost +\begin_inset Formula $O\left(\log n\right)$ +\end_inset + +. + Za pridobitev seznama soležnikov torrenta pošljemo bkodiran UDP paket tipa +\family typewriter +get_peers +\family default + +\begin_inset Formula $t$ +\end_inset + + +\begin_inset Foot +status open + +\begin_layout Plain Layout +odvisno od implementacije +\end_layout + +\end_inset + + vozliščem iz usmerjevalne tabele, + ki so blizu infohasha. + Pozvana vozlišča odgovorijo s seznamom do +\begin_inset Formula $K$ +\end_inset + + temu infohashu najbližjih vozlišč in seznamom soležnikov za ta torrent, + če ga imajo. + Novodobljenim vozliščem spet pošljemo poizvedbo +\family typewriter +get_peers +\family default + in postopek nadaljujemo, + dokler ne najdemo nekaj infohashu najbližjih vozlišč. + V tista pošiljamo objave in od njih še naprej prejemamo informacije o roju. +\end_layout + +\begin_layout Standard +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\align center +\begin_inset Graphics + filename Dht_example_SVG.svg + width 50col% + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +\begin_inset CommandInset label +LatexCommand label +name "fig:Usmerjevalna-tabela-za" + +\end_inset + +Usmerjevalna tabela za vozlišče 110 (koši so osenčeni) +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Section +Metode +\end_layout + +\begin_layout Standard +Vsaka poizvedba obišče +\begin_inset Formula $\log n$ +\end_inset + + vozlišč, + torej vsako vozlišče v DHT prejema ogromno ključev — + infohashov. + V raziskavi v C spišemo program travnik, + nepopolno implementacijo odjemalca BitTorrent s poudarkom na DHT. + Osredotočimo se na zajem metapodatkov iz ključev, + ki jih prejmemo s sodelovanjem v omrežju. +\end_layout + +\begin_layout Standard +Ko vozlišče, + na katerem teče travnik, + prejme paket z infohashom, + ga doda v seznam željenih torrentov. + Neprestano posodablja roje torrentov znanih infohashov in se povezuje na soležnike iz njih, + dokler mu ne uspe prenesti metapodatkov torrenta oziroma dokler ne obupa/preteče 256 sekundni TTL torrenta. + Izdeluje .torrent datoteke z najdenimi metapodatki in internetnim naslovom ter ime programske opreme soležnika, + od katerega je metapodatke prejel. + Ne objavlja se v roj, + ker ne redistribuira niti metapodatkov niti datotek. +\end_layout + +\begin_layout Standard +Da program prvič začne sodelovati z omrežjem — + da ga sosednja vozlišča vpišejo v svoje usmerjevalne tabele — + prenese metapodatke vgrajenega torrenta +\family typewriter +Big Buck Bunny +\family default +. +\end_layout + +\begin_layout Standard +Za implementacijo spišemo knjižnico za bkodiranje in bdekodiranje, + knjižnico za DHT in nekaj funkcij za prenos metapodatkov od soležnikov preko TCP. +\end_layout + +\begin_layout Standard +Za obdelavo dobljenih torrent datotek uporabimo Jupyter Notebook +\begin_inset CommandInset citation +LatexCommand cite +key "Kluyver2016jupyter" +literal "false" + +\end_inset + + in spišemo preprosto knjižnico za razčlenjevanje .torrent metainfo datotek, + ki jih generira travnik. +\end_layout + +\begin_layout Section +Rezultati +\end_layout + +\begin_layout Subsection +Zajem +\end_layout + +\begin_layout Standard +Podatke smo zajemali iz različnih lokacij in v različnih časovnih obdobjih: +\end_layout + +\begin_layout Itemize +januarja in februarja 2023: +\end_layout + +\begin_deeper +\begin_layout Itemize +16 dni: + domači optični priključek v Sloveniji (T-2): + 47863 torrentov (3084321 datotek, + 259 TiB, + 29 sekund na torrent) +\begin_inset Note Note +status open + +\begin_layout Plain Layout +travnik +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Itemize +31 dni VPS v Grčiji (grNet) +\begin_inset Note Note +status open + +\begin_layout Plain Layout +1 +\end_layout + +\end_inset + +: + +\family roman +\series medium +\shape up +\size normal +\emph off +\nospellcheck off +\bar no +\strikeout off +\xout off +\uuline off +\uwave off +\noun off +\color none +412846 +\family default +\series default +\shape default +\size default +\emph default +\nospellcheck default +\bar default +\strikeout default +\xout default +\uuline default +\uwave default +\noun default +\color inherit + torrentov (17101702 datotek, + 1881 TiB, + 6 sekund na torrent) +\begin_inset Note Note +status open + +\begin_layout Plain Layout +okeanos +\end_layout + +\end_inset + + +\begin_inset Note Note +status open + +\begin_layout Plain Layout +XX dni VPS v Grčiji (grNet) 2: + 342220 torrentov () +\begin_inset Note Note +status open + +\begin_layout Plain Layout +oliwerix +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\end_deeper +\begin_layout Itemize +5 dni junija 2024 na domačem optičnem priključku v Sloveniji (T-2): + 62110 torrentov (3725125 datotek, + 345 TiB, + 7 sekund na torrent) +\begin_inset Note Note +status open + +\begin_layout Plain Layout +2024b +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsubsection +Primer strukture torrent datoteke z metapodatki +\end_layout + +\begin_layout Standard +Spodaj je iz bencoding v JSON pretvorjena metainfo datoteka prevzetega torrenta z infohashom +\family typewriter +696802a16728636cd72617e4cd7b64e3ca314e71 +\family default +. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +lstinputlisting[language=json,firstnumber=1, + numbers=none, + breaklines=true, + basicstyle= +\backslash +tiny]{../../../../sola-gimb-4/inf/rn/predst/torrent.json} +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +Analiza +\end_layout + +\begin_layout Subsubsection +Odjemalci, + od katerih so bili prejeti torrenti +\end_layout + +\begin_layout Standard +Imenom programom odstranimo različico in jim ročno normaliziramo ime +\begin_inset Foot +status open + +\begin_layout Plain Layout +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +textmu Torrent +\end_layout + +\end_inset + + se sicer pojavi dvakrat, + enkrat ima znak mikro, + enkrat pa grško črko mu. + Unicode namreč ta dva znaka, + ki sicer izgledata identično, + hrani pod dvema različnima kodama. +\end_layout + +\end_inset + + ter prikažemo njihovo gostoto v populaciji. +\begin_inset CommandInset citation +LatexCommand cite +key "Hunter:2007" +literal "false" + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset Graphics + filename /root/projects/sola-gimb-4/inf/rn/dok/odjemalci_1_ods.png + width 100col% + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +Reprezentacija odjemalcev, + ki predstavljajo vsaj en odstotek populacije, + na logaritemski skali +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsubsection +Različice odjemalca +\family typewriter +qBittorrent +\family default + skozi čas +\end_layout + +\begin_layout Standard +Primerjava porazdelitve različic po zgornji analizi najpopularnejšega odjemalca na +\begin_inset Formula $\log_{10}$ +\end_inset + + skali pokaže višanje različic skozi čas. + +\begin_inset Note Note +status open + +\begin_layout Plain Layout +Različice smo razvrstili s pythonsko funkcijo +\family typewriter +packaging.version.Version +\family default +. +\end_layout + +\end_inset + + V obeh letih smo prejeli torrente od skupno 88 različnih inačic qBittorrenta. + V 2023 smo največ torrentov prejeli od odjemalcev različice 4.5.0, + v 2024 pa od odjemalcev različice 4.6.3. + +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset Note Note +status open + +\begin_layout Plain Layout +\begin_inset Graphics + filename /root/projects/r/šola/članki/dht/verzije2324.png + width 100col% + +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Graphics + filename /root/projects/r/šola/članki/dht/verzije2324promil.png + width 100col% + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +Primerjava distribucij različic odjemalca +\family typewriter +qBittorrent +\family default + med 2023 (plavo) in 2024 (roza), + ki predstavljajo vsaj promil populacije (delež). +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsubsection +Geolokacija IP naslovov odjemalcev +\end_layout + +\begin_layout Standard +Z uporabo podatkovne zbirke MaxMind GeoLite2 +\begin_inset CommandInset citation +LatexCommand cite +key "maxmindgeoip2" +literal "false" + +\end_inset + + IP naslovom, + od katerih smo prejeli torrente, + določimo izvirno državo. +\end_layout + +\begin_layout Standard +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset Graphics + filename countries_procent.png + width 100col% + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +Reprezentativnost držav, + iz katerih smo prenesli metainfo, + na linearni skali. + Prikazane so le države, + iz katerih izvira vsaj odstotek populacije. +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsubsection +Predstavnost ključev v prejetih slovarjih +\family typewriter +info +\end_layout + +\begin_layout Standard +Poleg standardnih obveznih nekateri torrenti vsebujejo tudi dodatne metapodatke v slovarju info. + Pogostost slednjih prikazuje spodnji grafikon. +\end_layout + +\begin_layout Standard +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset Graphics + filename /root/projects/sola-gimb-4/inf/rn/dok/vsi_ključi.png + width 100col% + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +Reprezentacija ključev v slovarju +\family typewriter +info +\family default + na logaritemski skali +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsubsection +Tipi datotek, + ki se prenašajo v torrentih +\end_layout + +\begin_layout Standard +Iz končnice datoteke izvemo tip datoteke. + Vsakemu torrentu priredimo reprezentativen tip, + tisti, + ki po velikosti prevladuje v torrentu. + Glede na število torrentov z nekim reprezentativnim tipom kvantificiramo pogostost tega datotečnega tipa za tipe, + ki zavzemajo vsaj promil populacije. +\end_layout + +\begin_layout Standard +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset Graphics + filename /root/projects/sola-gimb-4/inf/rn/dok/reprezentativni_.1_ods.png + width 100col% + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +Reprezentativni tipi torrentov, + ki predstavljajo vsaj en promil populacije, + na logaritemski skali +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +Razvidno je, + da je večina torrentov namenjena prenosu videovsebin, + zvočnih datotek in stisnjenih arhivov. +\end_layout + +\begin_layout Standard +Če bi za določilo pojavnosti tipa uporabili število datotek, + bi prevladovali tipi vsebin, + ki so ponavadi preneseni kot kopica datotek, + denimo slike (diagram v prilogi na sliki +\begin_inset CommandInset ref +LatexCommand ref +reference "fig:Pojavnost-tipa-kot" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + +), + če pa bi za določilo pojavnosti tipa uporabili velikost datotek tega tipa, + pa bi prevladovali tisti tipi, + ki zasedajo več prostora. + V tem primeru bi npr. + videovsebine zaradi svoje velikosti občutno presegale digitalne knjige (diagram v prilogi na sliki +\begin_inset CommandInset ref +LatexCommand ref +reference "fig:Pojavnost-tipa-kot-velikost" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + +). +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Subsubsection +\begin_inset CommandInset label +LatexCommand label +name "subsec:Porazdeljenost-infohashov" + +\end_inset + +Porazdeljenost infohashov +\end_layout + +\begin_layout Plain Layout +Zaradi delovanja poizvedb v DHT pričakujemo, + da je porazdelitev infohashov po celotnem sprektru števil z intervala +\begin_inset Formula $\left[0,2^{160}-1\right]$ +\end_inset + + gostejša okoli IDja vozlišča, + ki ga je med prenašanjem imelo naše iskalno vozlišče. + IDje smo izbrali naključno na vsaki merilni lokaciji in jih med meritvijo tudi nekajkrat zamenjali, + zato spodnjem grafikonu opazimo vrhove tam, + kjer so bili naši IDji med zajemom podatkov. +\end_layout + +\begin_layout Plain Layout +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +Razporeditev pridobljenih infohashov na spektru vseh infohashov +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +Diskusija +\end_layout + +\begin_layout Paragraph +Statistična kvaliteta vzorca +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +V razdelku +\begin_inset CommandInset ref +LatexCommand ref +reference "subsec:Porazdeljenost-infohashov" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + + opazimo neenakomerno porazdeljenost infohashov, + kar je posledica načina vzorčenja torrentov. + Vsa populacija ima namreč zaradi delovanja zgoščevalne funkcije SHA-1 homogeno porazdeljene infohashe. + Kljub temu trdimo, + da pridobljen vzorec torrentov dobro predstavlja celotno populacijo. + +\end_layout + +\end_inset + +Zaradi lastnosti uniformne porazdelitve zgoščevalne funkcije +\begin_inset CommandInset citation +LatexCommand cite +key "wikihashuniformity" +literal "false" + +\end_inset + + mesto infohasha na intervalu vseh možnih infohashov ni odvisno od metapodatkov. + Kot posledico načina vzorčenja z DHT pričakujemo, + da je porazdelitev infohashov prejetih torrentov po celotnem sprektru števil z intervala +\begin_inset Formula $\left[0,2^{160}-1\right]$ +\end_inset + + gostejša okoli IDja vozlišča, + ki ga je med prenašanjem imelo naše iskalno vozlišče. + IDje smo tekom raziskave izbrali naključno na vsaki merilni lokaciji in jih med meritvijo tudi nekajkrat zamenjali. + Kljub temu je vsled nepovezanosti vsebine in infohasha vzorec še vedno statistično reprezentativen. + Zajem ne more biti pristranski glede na metapodatke, + ker nikjer v procesu zajema ne obravnavamo torrentov glede na metainfo, + temveč le glede na infohash. +\end_layout + +\begin_layout Paragraph +Težava z zajemom podatkov +\end_layout + +\begin_layout Standard +Vsled majhne velikosti UDP paketov DHT glavno ozko grlo pri zajemu predstavlja število paketov, + ki jih mrežna oprema lahko posreduje v sekundi. + Domača optična povezava dopušča do okoli 2000 paketov na sekundo na naključno porazdeljene IP naslove, + odjemno mesto na VPS pa je imelo to omejitev veliko višjo, + zato smo tam v istem časovnem intervalu shranili veliko več torrent datotek. +\end_layout + +\begin_layout Paragraph +Etičnost in legitimnost rudarjenja podatkov +\end_layout + +\begin_layout Standard +Čeprav gre za izrazito osebne podatke, + se morajo uporabniki BitTorrent omrežja zavedati, + da so njihovi prenosi +\shape italic +a priori +\shape default + javni, + tudi če jih nihče aktivno ne zajema. + Nekateri BitTorrent odjemalci uporabnike ob prvem zagonu o tem obvestijo. +\end_layout + +\begin_layout Section +Priloge +\end_layout + +\begin_layout Standard +Izvorna koda programa travnik in ipynb datotek za analizo podatkov je na voljo na +\begin_inset CommandInset href +LatexCommand href +name "http://ni.šijanec.eu./sijanec/travnik" +target "http://ni.šijanec.eu./sijanec/travnik" +literal "false" + +\end_inset + +. +\end_layout + +\begin_layout Standard +Korpus zajetih metapodatkov je na voljo na +\begin_inset CommandInset href +LatexCommand href +name "rsync://b.sjanec.eu./travnik" +target "rsync://b.sijanec.eu./travnik" +type "other" +literal "false" + +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset Graphics + filename po_številu_datotek.png + width 100col% + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +\begin_inset CommandInset label +LatexCommand label +name "fig:Pojavnost-tipa-kot" + +\end_inset + +Pojavnost tipa kot število datotek +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset Float figure +placement document +alignment document +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset Graphics + filename /root/projects/sola-gimb-4/inf/rn/dok/po_velikosti_datotek.png + width 100col% + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +\begin_inset CommandInset label +LatexCommand label +name "fig:Pojavnost-tipa-kot-velikost" + +\end_inset + +Pojavnost tipa kot velikost datotek (tipi, + ki zavzamejo vsaj odstotek populacije) +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset CommandInset bibtex +LatexCommand bibtex +btprint "btPrintCited" +bibfiles "/root/projects/r/šola/citati" +options "IEEEtran" +encoding "default" + +\end_inset + + +\end_layout + +\begin_layout Section* +Viri slik +\end_layout + +\begin_layout Itemize +Slika +\begin_inset CommandInset ref +LatexCommand ref +reference "fig:Usmerjevalna-tabela-za" +plural "false" +caps "false" +noprefix "false" +nolink "false" + +\end_inset + +: + Limaner: + nespremenjena, + izvorna pod CC BY-SA +\end_layout + +\begin_layout Section* +Dovoljenje +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +doclicenseImage[imagewidth=2cm] +\end_layout + +\end_inset + + +\begin_inset Note Note +status open + +\begin_layout Plain Layout +TODO: + preštej datoteke v oliwerix, + še enkrat nariši vse grafe upoštevajoč vse torrente, + primerjaj verzije med travnik in 2024b +\end_layout + +\end_inset + + +\end_layout + +\end_body +\end_document -- cgit v1.2.3