## Revision d1ed66aa latex/note.tex

View differences:

latex/note.tex
1

2 1
% http://www.ams.jhu.edu/~ers/learn-latex/

3 2

4 3
\documentclass[12pt]{article}

......
13 12
\usepackage{amsmath}               % great math stuff

14 13
\usepackage{amsfonts}              % for blackboard bold, etc

15 14
\usepackage{amsthm}                % better theorem environments

16
\usepackage{listings}			   % to add code

15
\usepackage{listings}              % to add code

17 16
\lstset{language=Java}

17
\renewcommand{\lstlistingname}{Code} % change "Listing 1.1" to "Code 1.1"

18

18 19
\usepackage[utf8]{inputenc}

19 20
\usepackage{color}

20 21

......
57 58
\newcommand{\col}[1]{\left[\begin{matrix} #1 \end{matrix} \right]}

58 59
\newcommand{\comb}[2]{\binom{#1^2 + #2^2}{#1+#2}}

59 60

61
\usepackage[T1]{fontenc}

62
\AtBeginDocument{%

63
  \begingroup\lccode~=_%

64
  \lowercase{\endgroup\let~}_%

65
  \catcode_=12

66
}

60 67

61 68
\begin{document}

62 69

63
\nocite{*}

64

65 70
\title{Thesis - Note Taking}

71
\nocite{*}

66 72

67 73
\author{166071 - Pham Xuan Quynh Nguyen \\

68 74
DISI - University of Trento}

......
70 76
\maketitle

71 77

72 78
\clearpage

73
\section{Week 0}

74
    \subsection{Friday, 11/09/2015}

75
        \subsubsection{paper-adhoc.pdf}

76
            \textbf{Mesh network} A mesh network is a network topology in which each node relays data for the network. All mesh nodes cooperate in the distribution of data in the network. \footnote{https://en.wikipedia.org/wiki/Mesh\_networking}

77

78
            \textbf{Multi-Point Relays (MPR)}: nodes in Wireless ad hoc network that do the job of relaying messages between nodes. They also have the main role in routing and selecting the proper route from any source to any desired destination node. \footnote{https://en.wikipedia.org/wiki/Multipoint\_relay}

79

80
            \textbf{Optimized Link State Routing (OLSR)} an IP routing protocol optimized for \textit{mobile ad hoc networks}, which can also be used on other \textit{wireless ad hoc networks}. OLSR is a proactive \textit{link-state routing protocol}, which uses\textit{ hello and topology control (TC) messages} to discover and then disseminate link state information throughout the mobile ad hoc network. Individual nodes use this topology information to compute next hop destinations for all nodes in the network using shortest hop forwarding paths.

81

82
            \textbf{OLSRd} Optimized Link State Routing daemon - reads information about meshed networks from the txtinfo

83

84
            A \textbf{wireless ad hoc network} (WANET) is a decentralized type of wireless network.[1][2] The network is \textit{ad hoc} because it does not rely on a pre existing infrastructure, such as (i) routers in wired networks or (ii) access points in managed (infrastructure) wireless networks. Instead, each node participates in routing by forwarding data for other nodes, so the determination of which nodes forward data is made dynamically on the basis of network connectivity. In addition to the classic routing, ad hoc networks can use flooding for forwarding data.

85

86
            A \textbf{mobile ad hoc network} (MANET) is a continuously self-configuring, infrastructure-less network of mobile devices connected without wires. Ad hoc is Latin and means "for this purpose".

87

88
            cross-AP routing? abc

89

90
            \textbf{beam-width}

91

92
%%%%%%%%%%%%%%%%%%

93
% WEEK 1

94
%%%%%%%%%%%%%%%%%%

95
\section{Week 1}

96
    \subsection{Brandes 2001}

97
        \subsubsection{Counting the number of shortest paths}

98
            Explanation on k-th power of the adjacency matrix equals the number of paths from vertex \texttt{u} to vertex \texttt{v} \footnote{https://www.quora.com/What-is-an-intuitive-explanation-for-why-raising-an-adjacency-matrix-to-the-power-of-n-gives-a-new-matrix-with-the-number-of-n-paths}

99

100
            \textbf{Floyd/Warshall algorithm}

101

102
        \subsubsection{Code for shortest-path betweenness centrality}

103
            https://github.com/networkx/networkx/blob/master/networkx/algorithms/centrality/betweenness.py

104

105
            Line 116

106
            \begin{itemize}

107
            \item S

108
            \item P

109
            \item sigma

110
            \end{itemize}

111

112
            $c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\sigma(s, t)}$

113

114
%%%%%%%%%%%%%%%%%%

115
% WEEK 2

116
%%%%%%%%%%%%%%%%%%

117
\section{Week 2}

118
    \subsection{Library \texttt{networkx}}

119
        \textbf{Graph object}

120
            \begin{lstlisting}

121
            {'A': {'B': {}, 'F': {}}, 'C': {'B': {}}, 'B': {'A': {}, 'C': {}, 'E': {}}, 'E': {'B': {}, 'D': {}, 'F': {}}, 'D': {'E': {}, 'G': {}}, 'G': {'D': {}}, 'F': {'A': {}, 'E': {}}}

122
            \end{lstlisting}

123

124
        \textbf{Function} \texttt{\_single\_source\_shortest\_path\_basic} (in betweenness.py)

125

126
            Variable meanings:

127
            \begin{itemize}

128
                \item sigma[v] is the number of shortest paths passing through vertice v

129
                \item D[v] is the distance from vertice s to vertice v

130
                \item P[v] contains predecessors for node v. The predecessors satisfies the condition that if we traverse through it, the path is the shortest one.

131
            \end{itemize}

132

133
        \textbf{Function} \texttt{\_accumulate\_basic}

134
            S is an array

135
            S.pop() iteratively returns elements in array S, from the last to the top

136

137
    \subsection{Brandes 2001}

138
        I still do not understand Section 4, but I understand the pseudo-code. [21/09/2015]

139

140
    \subsection{OpenWRT}

141

142
        Download the SDK \footnote{http://wiki.openwrt.org/doc/howto/obtain.firmware.sdk}

143

144
        README.SDK:

145
        \begin{lstlisting}

146
            This is the OpenWrt SDK. It contains a stripped-down version of

147
            the buildroot. You can use it to test/develop packages without

148
            having to compile your own toolchain or any of the libraries

149
            included with OpenWrt.

150

151
            To use it, just put your buildroot-compatible package directory

152
            in the subdir 'package/' and run 'make' from this directory.

153
        \end{lstlisting}

154

155
        \subsubsection{Definition}

156
            \textbf{SDK}

157

158
            \textbf{OpenWrt Build System} = build system for the OpenWrt Linux distribution

159

160
            \textbf{OpenWrt Linux distribution}

161

162
            \textbf{Instruction set architecture} = the translator that turns the code a machine is running into instructions a processor can understand and execute. It's an important part of a processor.

163

164
            \textbf{ARM} = a simpler instruction set architecture comparing to the \texttt{x86}. It has the power efficiency. It uses \texttt{Reduced Instruction Set Computing - RISC}

165

166
            \textbf{i386} = that chips win over ARM chips on the performance. It uses \texttt{Complex Instruction Set Computing - CISC}.

167

168
            \textbf{Debian on ARM}

169

170

171
        \subsubsection{Compile OpenWRT CC toolchain to get OpenWrt SDK}

172
            Compile the \texttt{OpenWrt Chaos Calmer}. More information can be found in \href{http://wiki.openwrt.org/doc/howto/buildroot.exigence}{OpenWrt build system - Installation}.

173

174
            \href{http://wiki.openwrt.org/doc/howto/build}{This tutorial} shows how to build \texttt{OpenWrt SDK from source}

175

176
            \begin{lstlisting}

177
# Clone OpenWRT, branch Chaos Clamer

178
git clone http://git.openwrt.org/15.05/openwrt.git

179
# Make OpenWrt build system check for missing packages on your build-system using one of the following commands

180
make defconfig

181
make prereq

182
# To set the target system (e.g. Broadcom BCM47xx)

183
# Select (by pressing Y) on item "[ ] Build the OpenWrt SDK"

184
make menuconfig

185
            \end{lstlisting}

186

187
            \begin{figure}[h]

188
                \label{fig:menuconfig}

189
                \caption{menuconfig}

190
                \includegraphics[scale=0.3]{make-menuconfig}

191
            \end{figure}

192

193
            \begin{lstlisting}

194
# It will take a while to finish

195
make

196

197
# 2nd run - ERROR

198
make[3] -C package/system/opkg host-compile

199
make -r world: build failed. Please re-run make with -j1 V=s to see what's going on

200
make: *** [world] Error 1

201

202
# 3rd run - NO ERROR

203
            \end{lstlisting}

204

205
            Inside the directory \textbf{target-arm\_cortex-a9\_uClibc-0.9.33.2\_eabi} in \texttt{build\_dir}, we have \texttt{OpenWrt-SDK-bcm53xx\_gcc-4.8-linaro\_uClibc-0.9.33.2\_eabi.Linux-x86\_64}. This one is the \texttt{compiled toolchain}, or the \texttt{OpenWrt SDK, version Chaos Calmer}

206

207
    \subsubsection{Compile packages with OpenWrt SDK}

208
            Steps I performed

209

210
            \begin{itemize}

211
                \item Test building package with OpenWrt SDK BB on Linux Mint 17 (based on Ubuntu Trusty - 14)

212
                    \begin{lstlisting}

213
svn export svn://svn.openwrt.org/openwrt/packages/utils/sed package/sed

214
grep DEPENDS package/sed/Makefile

215
make package/sed/compile # GOT ERROR HERE

216

217
configure: error: in /home/quynh/Thesis/openwrt-bb/build_dir/target-mipsel_mips32_uClibc-0.9.33.2/sed-4.2.1':

218
configure: error: C compiler cannot create executables

219
See config.log' for more details.

220
make[2]: *** [/home/quynh/Thesis/openwrt-bb/build_dir/target-mipsel_mips32_uClibc-0.9.33.2/sed-4.2.1/.configured_] Error 77

221
make[2]: Leaving directory /home/quynh/Thesis/openwrt-bb/package/sed'

222
make[1]: *** [package/sed/compile] Error 2

223
make[1]: Leaving directory /home/quynh/Thesis/openwrt-bb'

224
make: *** [package/sed/compile] Error 2

225

226
# SOLUTION

227
sudo apt-get install ccache

228
                    \end{lstlisting}

229

230
                \item Test building package with Ubuntu 14 in VMWare. I got the same error as when running with Linux Mint 17

231

232
                \item Install the library \texttt{ccache} manually would solve the problem

233

234
                \item After successfully compile the package, you will find *.ipk in the folder [./bin/bcm53xx/packages/base/]. Where \texttt{bcm53xx} is the code of the target device. It can also be \texttt{ar71xx} or something else.

235
            \end{itemize}

236

237
        \subsubsection{Install QEMU}

238
            Check out \href{http://wiki.qemu.rg/Download}{Wiki} for instruction. It will took a while to install, since QEMU required several packages that are not present on my system.

239

240
            After installation, I have a bunch of binary file \texttt{quem-*} in \texttt{/usr/local/bin}

241

242
        \subsubsection{Generate OpenWrt Image with QEMU}

243
            This \href{http://wiki.openwrt.org/doc/howto/obtain.firmware}{Obtaining Firmware} page summarizes different ways to obtain \texttt{OpenWrt Firmware Image (OFI)} file. After having the OFI, then we can feed it into QEMU.

244

245
            This \href{http://wiki.openwrt.org/doc/howto/obtain.firmware.generate}{Image Generator tutorial} has instruction on how to generate Image Builder firmware.

246

247
            Since when compiling OpenWrt toolchain, I didn't modify anything in \texttt{menuconfig}, so the target system of the SDK are bcm53xx.

248

249
            The profile for bcm53xx can be found \href{https://dev.openwrt.org/browser/trunk/target/linux/bcm53xx/profiles/100-Generic.mk?rev=42143}{here}. I (randomly) pick \texttt{BCM53010}

250

251
            \begin{lstlisting}

252
cd openwrt

253
wget https://downloads.openwrt.org/chaos_calmer/15.05/bcm53xx/generic/OpenWrt-ImageBuilder-15.05-bcm53xx.Linux-x86_64.tar.bz2

254
tar -xvjf OpenWrt-ImageBuilder-15.05-bcm53xx.Linux-x86_64.tar

255
cd OpenWrt-ImageBuilder-15.05-bcm53xx.Linux-x86_64

256
mv OpenWrt-ImageBuilder-15.05-bcm53xx.Linux-x86_64 ImageBuilder-15.05-bcm53xx.Linux-x86_64

257

258
# If you want to modify 'profiles', then:

259
vim ./ImageBuilder-15.05-bcm53xx.Linux-x86_64/target/linux/bcm53xx/profiles/100-Generic.mk

260
make image PROFILE=Generic

261

262
# The image is in ./bin directory

263
# ERROR: Can't find any *.bin file

264
            \end{lstlisting}

265

266
            I then tried to generate OpenWrt Firmware Image for \texttt{ar71xx} just like the original tutorial. This time I got all the *.bin file.

267

268
        \subsubsection{Run OpenWrt Firmware Image with QEMU}

269
            \begin{lstlisting}

270
qemu-system-x86_64 -kernel openwrt-15.05-ar71xx-generic-vmlinux.elf

271
            \end{lstlisting}

272

273
    \subsection{Questions}

274
        What is \emph{buildroot-compatible package directory}?

275

276
        How big should I set for the size of the QEMU image? In \href{http://www.aurel32.net/info/debian_arm_qemu.php}{here} they set aside 10G for creating the image.

277

278
    \subsection{Technical Problems}

279
        \subsubsection{'build' folder for all output file from LaTeX with \emph{LaTeXTools}}

280
            So far I couldn't do it. I tried:

281
            \begin{itemize}

282
                \item Edit directly the simpleBuilder.py script, adding the option \texttt{"-output\_directory=./build"}. It shows error that *.log file cannot be written

283
                \item Change the \texttt{builder\_settings} \emph{Preferences -> Package Settings -> LaTeXTools -> Settings - User}

284
            \end{itemize}

285

286
            The solution now is to add extra line in \texttt{.gitignore} to not including the generated \emph{pdf} for each \emph{TeX} file.

287

288
        \subsubsection{Cannot compile package \texttt{sed}}

289
            Some line of errors from config.log

290
            \begin{lstlisting}

291
/home/quynh/Thesis/openwrt-bb/staging_dir/host/bin/

292
ccache_cc: 2: exec: ccache: not found

293
            \end{lstlisting}

294

295
            But I found the file ccache\_cc in that folder as shown below:

296
            \begin{lstlisting}

297
quynh in ~/Thesis/openwrt-bb/staging_dir/host/bin

298
\$ ls | grep ccache

299
ccache_cc

300
ccache_cxx

301
            \end{lstlisting}

302

303
            Solution: sudo apt-get install ccache

304

305

306
    \subsection{Misc}

307
        [11:10 - 11:30] I'm doing shitty things now. Removing gcc-base, and as a result most packages are being removed: chrome, mozilla, gedit,  tortoise, skype, python, libqt4, networkmanager. Now I don't have the internet connection anymore.

308

79
    \include{note_w00}

80
    \include{note_w01}

81
    \include{note_w02}

309 82
    \include{note_w03}

83
    \include{note_w04}

84
    \include{note_w05}

85
    \include{note_w06}

86
    \include{note_w07}

87
    \include{note_w08}

88
    \include{tips}

89
    \include{important_commands}

310 90

311 91
\end{document}
`

Also available in: Unified diff