AMUSE: Empowering Users for Cost-Aware Offloading with Throughput-Delay Tradeoffs
Youngbin Im
~\IEEEmembership{Student Member
~IEEE
....lastname \thanks{...
%\boldmath \input{abstract
0_main_file.tex

%% bare_jrnl_compsoc.tex
%% V1.3
%% 2007/01/11
%% by Michael Shell
%% See:
%% http://www.michaelshell.org/
%% for current contact information.
%%
%% This is a skeleton file demonstrating the use of IEEEtran.cls
%% (requires IEEEtran.cls version 1.7 or later) with an IEEE Computer
%% Society journal paper.
%%
%% Support sites:
%% http://www.michaelshell.org/tex/ieeetran/
%% http://www.ctan.org/tex-archive/macros/latex/contrib/IEEEtran/
%% and
%% http://www.ieee.org/

%%*************************************************************************
%% Legal Notice:
%% This code is offered as-is without any warranty either expressed or
%% implied; without even the implied warranty of MERCHANTABILITY or
%% FITNESS FOR A PARTICULAR PURPOSE! 
%% User assumes all risk.
%% In no event shall IEEE or any contributor to this code be liable for
%% any damages or losses, including, but not limited to, incidental,
%% consequential, or any other damages, resulting from the use or misuse
%% of any information contained here.
%%
%% All comments are the opinions of their respective authors and are not
%% necessarily endorsed by the IEEE.
%%
%% This work is distributed under the LaTeX Project Public License (LPPL)
%% ( http://www.latex-project.org/ ) version 1.3, and may be freely used,
%% distributed and modified. A copy of the LPPL, version 1.3, is included
%% in the base LaTeX documentation of all distributions of LaTeX released
%% 2003/12/01 or later.
%% Retain all contribution notices and credits.
%% ** Modified files should be clearly indicated as such, including  **
%% ** renaming them and changing author support contact information. **
%%
%% File list of work: IEEEtran.cls, IEEEtran_HOWTO.pdf, bare_adv.tex,
%%                    bare_conf.tex, bare_jrnl.tex, bare_jrnl_compsoc.tex
%%*************************************************************************

% *** Authors should verify (and, if needed, correct) their LaTeX system  ***
% *** with the testflow diagnostic prior to trusting their LaTeX platform ***
% *** with production work. IEEE's font choices can trigger bugs that do  ***
% *** not appear when using other class files.                            ***
% The testflow support page is at:
% http://www.michaelshell.org/tex/testflow/




% Note that the a4paper option is mainly intended so that authors in
% countries using A4 can easily print to A4 and see how their papers will
% look in print - the typesetting of the document will not typically be
% affected with changes in paper size (but the bottom and side margins will).
% Use the testflow package mentioned above to verify correct handling of
% both paper sizes by the user's LaTeX system.
%
% Also note that the "draftcls" or "draftclsnofoot", not "draft", option
% should be used if it is desired that the figures are to be displayed in
% draft mode.
%
% The Computer Society usually requires 10pt for submissions.
%
\documentclass[10pt,journal,cspaper,compsoc]{IEEEtran}
%
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:
% \documentclass[12pt,journal,compsoc]{../sty/IEEEtran}

% ybim added
\usepackage[latin9]{inputenc}
%\pagestyle{headings}
\usepackage{array}
\usepackage{verbatim}
\usepackage{multirow}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{cite}% Written by Donald Arseneau
\usepackage{epstopdf}
%\usepackage[boxed,vlined,figure,algonl]{algorithm2e}
\usepackage[ruled,vlined]{algorithm2e}
%\usepackage{algpseudocode}
\graphicspath{image/}
\usepackage{color}
\usepackage[caption=false,font=footnotesize]{subfig}
\setlength\textfloatsep{0.8\baselineskip plus 3pt minus 2pt}
\usepackage{ragged2e}
\usepackage{balance}

\definecolor{comment-blue}{rgb}{0,0,1}
\definecolor{comment-red}{rgb}{1,0,0}
\definecolor{comment-black}{rgb}{0,0,0}
\newcommand{\revise}[1]{\textnormal{\color{comment-black}{#1}}\unskip}
\newcommand{\reviseAgain}[1]{\textnormal{\color{comment-black}{#1}}\unskip}



% Some very useful LaTeX packages include:
% (uncomment the ones you want to load)


% *** MISC UTILITY PACKAGES ***
%
%\usepackage{ifpdf}
% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
% compilation based on whether the output is pdf or dvi.
% usage:
% \ifpdf
%   % pdf code
% \else
%   % dvi code
% \fi
% The latest version of ifpdf.sty can be obtained from:
% http://www.ctan.org/tex-archive/macros/latex/contrib/oberdiek/
% Also, note that IEEEtran.cls V1.7 and later provides a builtin
% \ifCLASSINFOpdf conditional that works the same way.
% When switching from latex to pdflatex and vice-versa, the compiler may
% have to be run twice to clear warning/error messages.






% *** CITATION PACKAGES ***
%
\ifCLASSOPTIONcompsoc
  % IEEE Computer Society needs nocompress option
  % requires cite.sty v4.0 or later (November 2003)
  % \usepackage[nocompress]{cite}
\else
  % normal IEEE
  % \usepackage{cite}
\fi
% cite.sty was written by Donald Arseneau
% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
% \cite{} output to follow that of IEEE. Loading the cite package will
% result in citation numbers being automatically sorted and properly
% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
% \cite will automatically add leading space, if needed. Use cite.sty's
% noadjust option (cite.sty V3.8 and later) if you want to turn this off.
% cite.sty is already installed on most LaTeX systems. Be sure and use
% version 4.0 (2003-05-27) and later if using hyperref.sty. cite.sty does
% not currently provide for hyperlinked citations.
% The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/cite/
% The documentation is contained in the cite.sty file itself.
%
% Note that some packages require special options to format as the Computer
% Society requires. In particular, Computer Society  papers do not use
% compressed citation ranges as is done in typical IEEE papers
% (e.g., [1]-[4]). Instead, they list every citation separately in order
% (e.g., [1], [2], [3], [4]). To get the latter we need to load the cite
% package with the nocompress option which is supported by cite.sty v4.0
% and later. Note also the use of a CLASSOPTION conditional provided by
% IEEEtran.cls V1.7 and later.





% *** GRAPHICS RELATED PACKAGES ***
%
\ifCLASSINFOpdf
  % \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../pdf/}{../jpeg/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
  % \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.eps}
\fi
% graphicx was written by David Carlisle and Sebastian Rahtz. It is
% required if you want graphics, photos, etc. graphicx.sty is already
% installed on most LaTeX systems. The latest version and documentation can
% be obtained at: 
% http://www.ctan.org/tex-archive/macros/latex/required/graphics/
% Another good source of documentation is "Using Imported Graphics in
% LaTeX2e" by Keith Reckdahl which can be found as epslatex.ps or
% epslatex.pdf at: http://www.ctan.org/tex-archive/info/
%
% latex, and pdflatex in dvi mode, support graphics in encapsulated
% postscript (.eps) format. pdflatex in pdf mode supports graphics
% in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
% that all non-photo figures use a vector format (.eps, .pdf, .mps) and
% not a bitmapped formats (.jpeg, .png). IEEE frowns on bitmapped formats
% which can result in "jaggedy"/blurry rendering of lines and letters as
% well as large increases in file sizes.
%
% You can find documentation about the pdfTeX application at:
% http://www.tug.org/applications/pdftex





% *** MATH PACKAGES ***
%
%\usepackage[cmex10]{amsmath}
% A popular package from the American Mathematical Society that provides
% many useful and powerful commands for dealing with mathematics. If using
% it, be sure to load this package with the cmex10 option to ensure that
% only type 1 fonts will utilized at all point sizes. Without this option,
% it is possible that some math symbols, particularly those within
% footnotes, will be rendered in bitmap form which will result in a
% document that can not be IEEE Xplore compliant!
%
% Also, note that the amsmath package sets \interdisplaylinepenalty to 10000
% thus preventing page breaks from occurring within multiline equations. Use:
%\interdisplaylinepenalty=2500
% after loading amsmath to restore such page breaks as IEEEtran.cls normally
% does. amsmath.sty is already installed on most LaTeX systems. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/





% *** SPECIALIZED LIST PACKAGES ***
%
%\usepackage{algorithmic}
% algorithmic.sty was written by Peter Williams and Rogerio Brito.
% This package provides an algorithmic environment fo describing algorithms.
% You can use the algorithmic environment in-text or within a figure
% environment to provide for a floating algorithm. Do NOT use the algorithm
% floating environment provided by algorithm.sty (by the same authors) or
% algorithm2e.sty (by Christophe Fiorio) as IEEE does not use dedicated
% algorithm float types and packages that provide these will not provide
% correct IEEE style captions. The latest version and documentation of
% algorithmic.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithms/
% There is also a support site at:
% http://algorithms.berlios.de/index.html
% Also of interest may be the (relatively newer and more customizable)
% algorithmicx.sty package by Szasz Janos:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithmicx/




% *** ALIGNMENT PACKAGES ***
%
%\usepackage{array}
% Frank Mittelbach's and David Carlisle's array.sty patches and improves
% the standard LaTeX2e array and tabular environments to provide better
% appearance and additional user controls. As the default LaTeX2e table
% generation code is lacking to the point of almost being broken with
% respect to the quality of the end results, all users are strongly
% advised to use an enhanced (at the very least that provided by array.sty)
% set of table tools. array.sty is already installed on most systems. The
% latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/tools/


%\usepackage{mdwmath}
%\usepackage{mdwtab}
% Also highly recommended is Mark Wooding's extremely powerful MDW tools,
% especially mdwmath.sty and mdwtab.sty which are used to format equations
% and tables, respectively. The MDWtools set is already installed on most
% LaTeX systems. The lastest version and documentation is available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/mdwtools/


% IEEEtran contains the IEEEeqnarray family of commands that can be used to
% generate multiline equations as well as matrices, tables, etc., of high
% quality.


%\usepackage{eqparbox}
% Also of notable interest is Scott Pakin's eqparbox package for creating
% (automatically sized) equal width boxes - aka "natural width parboxes".
% Available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/eqparbox/





% *** SUBFIGURE PACKAGES ***
%\ifCLASSOPTIONcompsoc
%\usepackage[tight,normalsize,sf,SF]{subfigure}
%\else
%\usepackage[tight,footnotesize]{subfigure}
%\fi
% subfigure.sty was written by Steven Douglas Cochran. This package makes it
% easy to put subfigures in your figures. e.g., "Figure 1a and 1b". For IEEE
% work, it is a good idea to load it with the tight package option to reduce
% the amount of white space around the subfigures. Computer Society papers
% use a larger font and \sffamily font for their captions, hence the
% additional options needed under compsoc mode. subfigure.sty is already
% installed on most LaTeX systems. The latest version and documentation can
% be obtained at:
% http://www.ctan.org/tex-archive/obsolete/macros/latex/contrib/subfigure/
% subfigure.sty has been superceeded by subfig.sty.


%\ifCLASSOPTIONcompsoc
%  \usepackage[caption=false]{caption}
%  \usepackage[font=normalsize,labelfont=sf,textfont=sf]{subfig}
%\else
%  \usepackage[caption=false]{caption}
%  \usepackage[font=footnotesize]{subfig}
%\fi
% subfig.sty, also written by Steven Douglas Cochran, is the modern
% replacement for subfigure.sty. However, subfig.sty requires and
% automatically loads Axel Sommerfeldt's caption.sty which will override
% IEEEtran.cls handling of captions and this will result in nonIEEE style
% figure/table captions. To prevent this problem, be sure and preload
% caption.sty with its "caption=false" package option. This is will preserve
% IEEEtran.cls handing of captions. Version 1.3 (2005/06/28) and later 
% (recommended due to many improvements over 1.2) of subfig.sty supports
% the caption=false option directly:
%\ifCLASSOPTIONcompsoc
%  \usepackage[caption=false,font=normalsize,labelfont=sf,textfont=sf]{subfig}
%\else
%  \usepackage[caption=false,font=footnotesize]{subfig}
%\fi
%
% The latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/
% The latest version and documentation of caption.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/caption/




% *** FLOAT PACKAGES ***
%
%\usepackage{fixltx2e}
% fixltx2e, the successor to the earlier fix2col.sty, was written by
% Frank Mittelbach and David Carlisle. This package corrects a few problems
% in the LaTeX2e kernel, the most notable of which is that in current
% LaTeX2e releases, the ordering of single and double column floats is not
% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
% single column figure to be placed prior to an earlier double column
% figure. The latest version and documentation can be found at:
% http://www.ctan.org/tex-archive/macros/latex/base/



%\usepackage{stfloats}
% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
% the ability to do double column floats at the bottom of the page as well
% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
% LaTeX2e). It also provides a command:
%\fnbelowfloat
% to enable the placement of footnotes below bottom floats (the standard
% LaTeX2e kernel puts them above bottom floats). This is an invasive package
% which rewrites many portions of the LaTeX2e float routines. It may not work
% with other packages that modify the LaTeX2e float routines. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/sttools/
% Documentation is contained in the stfloats.sty comments as well as in the
% presfull.pdf file. Do not use the stfloats baselinefloat ability as IEEE
% does not allow \baselineskip to stretch. Authors submitting work to the
% IEEE should note that IEEE rarely uses double column equations and
% that authors should try to avoid such use. Do not be tempted to use the
% cuted.sty or midfloat.sty packages (also by Sigitas Tolusis) as IEEE does
% not format its papers in such ways.




%\ifCLASSOPTIONcaptionsoff
%  \usepackage[nomarkers]{endfloat}
% \let\MYoriglatexcaption\caption
% \renewcommand{\caption}[2][\relax]{\MYoriglatexcaption[#2]{#2}}
%\fi
% endfloat.sty was written by James Darrell McCauley and Jeff Goldberg.
% This package may be useful when used in conjunction with IEEEtran.cls'
% captionsoff option. Some IEEE journals/societies require that submissions
% have lists of figures/tables at the end of the paper and that
% figures/tables without any captions are placed on a page by themselves at
% the end of the document. If needed, the draftcls IEEEtran class option or
% \CLASSINPUTbaselinestretch interface can be used to increase the line
% spacing as well. Be sure and use the nomarkers option of endfloat to
% prevent endfloat from "marking" where the figures would have been placed
% in the text. The two hack lines of code above are a slight modification of
% that suggested by in the endfloat docs (section 8.3.1) to ensure that
% the full captions always appear in the list of figures/tables - even if
% the user used the short optional argument of \caption[]{}.
% IEEE papers do not typically make use of \caption[]'s optional argument,
% so this should not be an issue. A similar trick can be used to disable
% captions of packages such as subfig.sty that lack options to turn off
% the subcaptions:
% For subfig.sty:
% \let\MYorigsubfloat\subfloat
% \renewcommand{\subfloat}[2][\relax]{\MYorigsubfloat[]{#2}}
% For subfigure.sty:
% \let\MYorigsubfigure\subfigure
% \renewcommand{\subfigure}[2][\relax]{\MYorigsubfigure[]{#2}}
% However, the above trick will not work if both optional arguments of
% the \subfloat/subfig command are used. Furthermore, there needs to be a
% description of each subfigure *somewhere* and endfloat does not add
% subfigure captions to its list of figures. Thus, the best approach is to
% avoid the use of subfigure captions (many IEEE journals avoid them anyway)
% and instead reference/explain all the subfigures within the main caption.
% The latest version of endfloat.sty and its documentation can obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/endfloat/
%
% The IEEEtran \ifCLASSOPTIONcaptionsoff conditional can also be used
% later in the document, say, to conditionally put the References on a 
% page by themselves.




% *** PDF, URL AND HYPERLINK PACKAGES ***
%
%\usepackage{url}
% url.sty was written by Donald Arseneau. It provides better support for
% handling and breaking URLs. url.sty is already installed on most LaTeX
% systems. The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/misc/
% Read the url.sty source comments for usage information. Basically,
% \url{my_url_here}.





% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.
% (Unless specifically asked to do so by the journal or conference you plan
% to submit to, of course. )


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


\begin{document}
%
% paper title
% can use linebreaks \\ within to get better formatting as desired
\title{AMUSE: Empowering Users for Cost-Aware Offloading with Throughput-Delay Tradeoffs}
%
%
% author names and IEEE memberships
% note positions of commas and nonbreaking spaces ( ~ ) LaTeX will not break
% a structure at a ~ so this keeps an author's name from being broken across
% two lines.
% use \thanks{} to gain access to the first footnote area
% a separate \thanks must be used for each paragraph as LaTeX2e's \thanks
% was not built to handle multiple paragraphs
%
%
%\IEEEcompsocitemizethanks is a special \thanks that produces the bulleted
% lists the Computer Society journals use for "first footnote" author
% affiliations. Use \IEEEcompsocthanksitem which works much like \item
% for each affiliation group. When not in compsoc mode,
% \IEEEcompsocitemizethanks becomes like \thanks and
% \IEEEcompsocthanksitem becomes a line break with idention. This
% facilitates dual compilation, although admittedly the differences in the
% desired content of \author between the different types of papers makes a
% one-size-fits-all approach a daunting prospect. For instance, compsoc 
% journal papers have the author affiliations above the "Manuscript
% received ..."  text while in non-compsoc journals this is reversed. Sigh.

\author{Youngbin Im,~\IEEEmembership{Student Member,~IEEE,}
        Carlee Joe-Wong,~\IEEEmembership{Student Member,~IEEE,}\\
        Sangtae Ha,~\IEEEmembership{Senior Member,~IEEE,}
        Soumya Sen,~\IEEEmembership{Member,~IEEE,}\\
        Ted ``Taekyoung'' Kwon,~\IEEEmembership{Member,~IEEE,}
        and Mung Chiang,~\IEEEmembership{Fellow,~IEEE}
        %% <-this % stops a space
\IEEEcompsocitemizethanks{
\IEEEcompsocthanksitem Y. Im and S. Ha are with the University of Colorado, Boulder, Colorado.\protect\\
E-mails: \{youngbin.im,sangtae.ha\}@colorado.edu 
\IEEEcompsocthanksitem C. Joe-Wong and M. Chiang are with Princeton University, Princeton, New Jersey.\protect\\
E-mails: \{cjoe,chiangm\}@princeton.edu
\IEEEcompsocthanksitem S. Sen is with the Carlson School of Management, University of Minnesota, MN.\protect\\
E-mail: ssen@umn.edu
\IEEEcompsocthanksitem T. Kwon is with Seoul National University, Seoul, Korea\protect\\
(corresponding author to provide phone: +82 2 880 9105; fax: +82 2 872 2045; e-mail: tkkown@snu.ac.kr).} 
\thanks{An earlier version of this paper appeared in the IEEE INFOCOM 2013 mini-conference.}% <-this % stops a space
}

% note the % following the last \IEEEmembership and also \thanks - 
% these prevent an unwanted space from occurring between the last author name
% and the end of the author line. i.e., if you had this:
% 
% \author{....lastname \thanks{...} \thanks{...} }
%                     ^------------^------------^----Do not want these spaces!
%
% a space would be appended to the last name and could cause every name on that
% line to be shifted left slightly. This is one of those "LaTeX things". For
% instance, "\textbf{A} \textbf{B}" will typeset as "A B" not "AB". To get
% "AB" then you have to do: "\textbf{A}\textbf{B}"
% \thanks is no different in this regard, so shield the last } of each \thanks
% that ends a line with a % and do not let a space in before the next \thanks.
% Spaces after \IEEEmembership other than the last one are OK (and needed) as
% you are supposed to have spaces between the names. For what it is worth,
% this is a minor point as most people would not even notice if the said evil
% space somehow managed to creep in.



% The paper headers
\markboth{IEEE Transactions on Mobile Computing, vol. 15, no. 5, pp. 1062-1076, May 1 2016}%
{Shell \MakeLowercase{\textit{et al.}}: Bare Demo of IEEEtran.cls for Computer Society Journals}
% The only time the second header will appear is for the odd numbered pages
% after the title page when using the twoside option.
% 
% *** Note that you probably will NOT want to include the author's ***
% *** name in the headers of peer review papers.                   ***
% You can use \ifCLASSOPTIONpeerreview for conditional compilation here if
% you desire.



% The publisher's ID mark at the bottom of the page is less important with
% Computer Society journal papers as those publications place the marks
% outside of the main text columns and, therefore, unlike regular IEEE
% journals, the available text space is not reduced by their presence.
% If you want to put a publisher's ID mark on the page you can do it like
% this:
%\IEEEpubid{0000--0000/00\$00.00~\copyright~2007 IEEE}
% or like this to get the Computer Society new two part style.
%\IEEEpubid{\makebox[\columnwidth]{\hfill 0000--0000/00/\$00.00~\copyright~2007 IEEE}%
%\hspace{\columnsep}\makebox[\columnwidth]{Published by the IEEE Computer Society\hfill}}
% Remember, if you use this you must call \IEEEpubidadjcol in the second
% column for its text to clear the IEEEpubid mark (Computer Society jorunal
% papers don't need this extra clearance.)




% for Computer Society papers, we must declare the abstract and index terms
% PRIOR to the title within the \IEEEcompsoctitleabstractindextext IEEEtran
% command as these need to go into the title area created by \maketitle.
\IEEEcompsoctitleabstractindextext{%
\begin{abstract}
%\boldmath
\input{abstract}
\end{abstract}
% IEEEtran.cls defaults to using nonbold math in the Abstract.
% This preserves the distinction between vectors and scalars. However,
% if the journal you are submitting to favors bold math in the abstract,
% then you can use LaTeX's standard command \boldmath at the very start
% of the abstract to achieve this. Many IEEE journals frown on math
% in the abstract anyway. In particular, the Computer Society does
% not want either math or citations to appear in the abstract.

% Note that keywords are not normally used for peer review papers.
\begin{keywords}
Bandwidth management, mobile data, WiFi offloading
\end{keywords}}


% make the title area
\maketitle


% To allow for easy dual compilation without having to reenter the
% abstract/keywords data, the \IEEEcompsoctitleabstractindextext text will
% not be used in maketitle, but will appear (i.e., to be "transported")
% here as \IEEEdisplaynotcompsoctitleabstractindextext when compsoc mode
% is not selected <OR> if conference mode is selected - because compsoc
% conference papers position the abstract like regular (non-compsoc)
% papers do!
\IEEEdisplaynotcompsoctitleabstractindextext
% \IEEEdisplaynotcompsoctitleabstractindextext has no effect when using
% compsoc under a non-conference mode.


% For peer review papers, you can put extra information on the cover
% page as needed:
% \ifCLASSOPTIONpeerreview
% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
% \fi
%
% For peerreview papers, this IEEEtran command inserts a page break and
% creates the second title. It will be ignored for other modes.
\IEEEpeerreviewmaketitle



\input{intro_revised2}

\input{relatedWork_revised}
% \input{systemDesign}

\input{Algorithm_Revised}

%\input{bandwidthControl}

\input{implementation_revised}

%\input{DataCollection}

\input{Measurement}

\input{Evaluation_revised}

%\input{Discussion}

\input{conclusion_revised}



% if have a single appendix:
%\appendix[Proof of the Zonklar Equations]
% or
%\appendix  % for no appendix heading
% do not use \section anymore after \appendix, only \section*
% is possibly needed

% use appendices with more than one appendix
% then use \section to start each appendix
% you must declare a \section before using any
% \subsection or using \label (\appendices by itself
% starts a section numbered zero.)
%


%\appendices
%\section{Proof of the First Zonklar Equation}
%Appendix one text goes here.

% you can choose not to have a title for an appendix
% if you want by leaving the argument blank
%\section{}
%Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.Appendix two text goes here.


% use section* for acknowledgement
\ifCLASSOPTIONcompsoc
  % The Computer Society usually uses the plural form
  \section*{Acknowledgments}
\else
  % regular IEEE prefers the singular form
  \section*{Acknowledgment}
\fi
{\footnotesize
This research was supported by Basic Science Research Program through the "National Research Foundation of Korea(NRF)" funded by the Ministry of Science, ICT \& future Planning (2013R1A2A2A01016562). 
This work was in part supported by NSF grants CNS 1011962 and CNS 1456847.}

%The authors would like to thank...The authors would like to thank...The authors would like to thank...The authors would like to thank...The authors would like to thank...The authors would like to thank...The authors would like to thank...The authors would like to thank...The authors would like to thank...The authors would like to thank...The authors would like to thank...The authors would like to thank...The authors would like to thank...


% Can use something like this to put references on a page
% by themselves when using endfloat and the captionsoff option.
\ifCLASSOPTIONcaptionsoff
  \newpage
\fi



% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
% adjust value as needed - may need to be readjusted if
% the document is modified later
%\IEEEtriggeratref{8}
% The "triggered" command can be changed if desired:
%\IEEEtriggercmd{\enlargethispage{-5in}}

% references section

% can use a bibliography generated by BibTeX as a .bbl file
% BibTeX documentation can be easily obtained at:
% http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/
% The IEEEtran BibTeX style support page is at:
% http://www.michaelshell.org/tex/ieeetran/bibtex/
\bibliographystyle{IEEEtran}
\raggedright
\bibliography{0_main_file.bbl}
%\bibliography{ReferenceList}
%
% <OR> manually copy in the resultant .bbl file
% set second argument of \begin to the number of references
% (used to reserve space for the reference number labels box)
%\begin{thebibliography}{1}

%\bibitem{IEEEhowto:kopka}
%This is an example of a book reference
%H. Kopka and P.W. Daly, \emph{A Guide to {\LaTeX}}, third ed. Harlow, U.K.: Addison-Wesley, 1999.


%This is an example of a Transactions article reference
%D.S. Coming and O.G. Staadt, "Velocity-Aligned Discrete Oriented Polytopes for Dynamic Collision Detection," IEEE Trans. Visualization and Computer Graphics, vol.�14,� no.�1,� pp. 1-12,� Jan/Feb� 2008, doi:10.1109/TVCG.2007.70405.

%This is an example of a article from a conference proceeding
%H. Goto, Y. Hasegawa, and M. Tanaka, "Efficient Scheduling Focusing on the Duality of MPL Representation," Proc. IEEE Symp. Computational Intelligence in Scheduling (SCIS '07), pp. 57-64, Apr. 2007, doi:10.1109/SCIS.2007.367670.

%This is an example of a PrePrint reference
%J.M.P. Martinez, R.B. Llavori, M.J.A. Cabo, and T.B. Pedersen, "Integrating Data Warehouses with Web Data: A Survey," IEEE Trans. Knowledge and Data Eng., preprint, 21 Dec. 2007, doi:10.1109/TKDE.2007.190746.

%Again, see the IEEEtrans_HOWTO.pdf for several more bibliographical examples. Also, more style examples
%can be seen at http://www.computer.org/author/style/transref.htm
%\end{thebibliography}

% biography section
% 
% If you have an EPS/PDF photo (graphicx package needed) extra braces are
% needed around the contents of the optional argument to biography to prevent
% the LaTeX parser from getting confused when it sees the complicated
% \includegraphics command within an optional argument. (You could create
% your own custom macro containing the \includegraphics command to make things
% simpler here.)
%\begin{biography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{mshell}}]{Michael Shell}
% or if you just want to reserve a space for a photo:

%\begin{IEEEbiography}{Michael Shell}
%Biography text here.
%\end{IEEEbiography}
%
%% if you will not have a photo at all:
\justifying
\vspace{-1.2in}
\begin{biography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{./biography/ybim.jpg}}]{Youngbin Im}
	is a postdoctoral researcher in the Department of Computer Science at University of Colorado Boulder. He received his B.S. and Ph.D. degrees in computer science and engineering from Seoul National University in 2006 and 2014, respectively. During his graduate program, he was a visiting student at Princeton University. His research interest includes mobile data offloading, next-generation Internet, multi-core based content router, video rate adaptation. 
\end{biography}	
\vspace{-0.7in}
\begin{biography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{./biography/carlee.jpg}}]{Carlee Joe-Wong}
	is a Ph.D. candidate at Princeton University's Program in Applied and Computational Mathematics. Her research interests include network economics and optimal control. She received her A.B. in mathematics in 2011 and her M.A. in applied mathematics in 2013, both from Princeton University.  In 2013, she was the Director of Advanced Research at DataMi, a startup she co-founded in 2012 that commercializes new ways of charging for mobile data. She received the INFORMS ISS Design Science Award in 2014 and the Best Paper Award at IEEE INFOCOM 2012. In 2011, she received a National Defense Science and Engineering Graduate Fellowship.
\end{biography}	
\vspace{-0.7in}
\begin{biography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{./biography/sangtaeha_pic.jpg}}]{Sangtae Ha} (S'07, M'09, SM'12) is an Assistant Professor in the
	Department of Computer Science at the University of Colorado at
	Boulder. He received his Ph.D. in Computer Science from North Carolina
	State University. His research focuses on building and deploying
	practical systems. He is a co-founder and the founding CTO/VP
	Engineering of DataMi, a startup company on mobile networks, and is a
	technical consultant to a few startups. He is an IEEE Senior Member
	and serves as an Associate Editor for IEEE Internet of Things (IoT)
	Journal. He received the INFORMS ISS Design Science Award in 2014.
\end{biography}	
\vspace{-0.7in}
\begin{biography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{./biography/soumya.jpg}}]{Soumya Sen}
	received his M.S. and Ph.D. in Electrical and Systems Engineering from the University of Pennsylvania in 2008 and 2011, respectively, and was a postdoctoral researcher at the Princeton University. He is currently an Assistant Professor in the Department of Information \& Decision Sciences at the Carlson School of Management of the University of Minnesota. His research interests are in network technologies and e-commerce. He co-founded a telecom startup, DataMi, and served as the editor for the book, "Smart Data Pricing", published by John Wiley \& Sons in 2014. He won the Best Paper Award at IEEE INFOCOM 2012 and the INFORMS ISS Design Science Award 2014.
\end{biography}	
\vspace{-0.7in}
\begin{biography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{./biography/tkkwon.jpg}}]{Ted ``Taekyoung'' Kwon}
	is a professor with Department of Computer Science and Engineering, Seoul National University (SNU). 
	Before joining SNU, he was a Postdoctoral Research Associate at University of California Los Angeles and 
	City University New York. He obtained BS, MS and PhD at SNU in 1993, 1995, 2000, respectively. During his graduate program, 
	he was a visiting student at IBM T.J. Watson Research Center and at University of North Texas. He was a visiting professor 
	at Rutgers University in 2010.  His research interest lies in future Internet, indoor localizatino, network security, and wireless networks.
\end{biography}
\vspace{-0.7in}
\begin{biography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{./biography/mungchiang.jpg}}]{Mung Chiang}
	(S'00, M'03, SM'08, F'12) is the Arthur LeGrand Doty Professor of Electrical Engineering at Princeton University and the recipient of the 2013 Alan T. Waterman Award. He created the Princeton EDGE Lab in 2009 to bridge the theory-practice divide in networking by spanning from proofs to prototypes, resulting in a few technology transfers to industry, several startup companies and the 2012 IEEE Kiyo Tomiyasu Award. He serves as the inaugural Chairman of Princeton Entrepreneurship Council and the Director of Keller Center for Innovation in Engineering Education at Princeton. His Massive Open Online Courses on networking reached over 250,000 students since 2012 and the textbook received the 2013 Terman Award from American Society of Engineering Education. He was named a Guggenheim Fellow in 2014. 
\end{biography}	
\balance
%Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.
%\end{IEEEbiographynophoto}
%
%% insert where needed to balance the two columns on the last page with
%% biographies
%%\newpage
%
%\begin{IEEEbiographynophoto}{Jane Doe}
%Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.Biography text here.
%\end{IEEEbiographynophoto}

% You can push biographies down or up by placing
% a \vfill before or after them. The appropriate
% use of \vfill depends on what kind of text is
% on the last page and whether or not the columns
% are being equalized.
%\balance

%\vfill

% Can be used to pull up biographies so that the bottom of the last one
% is flush with the other column.
%\enlargethispage{-5in}
\newpage

\input{Appendix.tex}
%\balancecolumns

% that's all folks
\end{document}




abstract.tex
To cope with recent exponential increases in demand for mobile data, wireless Internet service providers (ISPs) are increasingly changing their pricing plans and deploying WiFi hotspots to offload their mobile traffic. However, these ISP-centric approaches for traffic management do not always match the interests of mobile users. Users face a complex, multi-dimensional tradeoff between cost, throughput, and delay in making their offloading decisions: while they may save money and receive a higher throughput by waiting for WiFi access, they may not wait for WiFi if they are sensitive to delay. To navigate this tradeoff, we develop AMUSE (Adaptive bandwidth Management through USer-Empowerment), a functional prototype of a practical, cost-aware WiFi offloading system that takes into account a user's throughput-delay tradeoffs and cellular budget constraint. Based on predicted future usage and WiFi availability, AMUSE decides which applications to offload to what times of the day. Since nearly all traffic flows from mobile devices are TCP flows, we introduce a new receiver-side bandwidth allocation mechanism to practically enforce the assigned rate of each TCP application. Thus, AMUSE users can optimize their bandwidth rates according to their own cost-throughput-delay tradeoff without relying on support from different apps' content servers. Through a measurement study of 20 smartphone users' traffic usage traces, we observe that though users already offload a large amount of some application types, our framework can offload a significant additional portion of users' cellular traffic.
We implement AMUSE on Windows 7 tablets and evaluate its effectiveness with 3G and WiFi usage data obtained from a trial with 37 mobile users. Our results show that AMUSE improves user utility; when compared with AMUSE, other offloading algorithms yield 14\% and 27\% lower user utilities for light and heavy users, respectively. Intelligently managing users' competing interests for cost, throughput, and delay can therefore improve their offloading decisions.
Algorithm_Revised.tex
%\documentclass[conference]{IEEEtran}
%%% INFOCOM 2013 addition:
%\makeatletter
%\def\ps@headings{%
%\def\@oddhead{\mbox{}\scriptsize\rightmark \hfil \thepage}%
%\def\@evenhead{\scriptsize\thepage \hfil \leftmark\mbox{}}%
%\def\@oddfoot{}%
%\def\@evenfoot{}}
%\makeatother
%\pagestyle{headings}
%
%% ybim added
%\usepackage[latin9]{inputenc}
%%\pagestyle{headings}
%\usepackage{array}
%\usepackage{verbatim}
%\usepackage{multirow}
%\usepackage{amsmath}
%\usepackage{amssymb}
%\usepackage{graphicx}
%\usepackage{cite}% Written by Donald Arseneau
%\usepackage{epstopdf}
%%\usepackage[boxed,vlined,figure,algonl]{algorithm2e}
%\usepackage[ruled,vlined]{algorithm2e}
%%\usepackage{algpseudocode}
%\graphicspath{./image/}
%\usepackage{color}
%
%% *** GRAPHICS RELATED PACKAGES ***
%%
%\ifCLASSINFOpdf
%  % \usepackage[pdftex]{graphicx}
%  % declare the path(s) where your graphic files are
%  % \graphicspath{{../pdf/}{../jpeg/}}
%  % and their extensions so you won't have to specify these with
%  % every instance of \includegraphics
%  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
%\else
%  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
%  % will default to the driver specified in the system graphics.cfg if no
%  % driver is specified.
%  % \usepackage[dvips]{graphicx}
%  % declare the path(s) where your graphic files are
%  % \graphicspath{{../eps/}}
%  % and their extensions so you won't have to specify these with
%  % every instance of \includegraphics
%  % \DeclareGraphicsExtensions{.eps}
%\fi
%
%\hyphenation{op-tical net-works semi-conduc-tor}
%
%
%\begin{document}

\section{Bandwidth Optimizer}\label{sec:allocation_algorithm}

In this section, we describe the individual components of AMUSE's bandwidth optimization algorithm.  Our design follows two principles: 1) AMUSE's offloading decisions will be implemented in real time on arriving sessions, and 2) AMUSE must use only the data and computational resources available on the end user's device.  Thus, we require simple, yet accurate, algorithms to compute concrete offloading decisions that can be communicated directly to the TCP Rate Controller (cf. Fig. \ref{fig:control}).  In the discussion below, we first introduce practical algorithms to predict WiFi access and application-specific usage (Sections \ref{sec:wifi} and \ref{sec:usage}).  We then incorporate these predictions into a mathematical allocation framework  in Section \ref{sec:formulation} and propose a heuristic algorithm for computing AMUSE's bandwidth allocations and offloading decisions in Section \ref{sec:online}.

To consider a user's different delay tolerances on different applications, we group a user's traffic into different application types, e.g., streaming, browsing, and downloads.  For practical implementability, we assume that only the most heavily used (e.g., top five) applications are considered, and denote these collectively as a set $J$.  We suppose that the day is divided into $n$ discrete periods of time, e.g., 24 hours, and for each period, we predict both WiFi access and application usage volumes.  % the probability that a user will have WiFi access (Section \ref{sec:wifi}), as well as the usage volume of each application type in each period, based on past usage data (Section \ref{sec:usage}).

Given these predictions, we (i.e., AMUSE) must decide which applications to offload when, subject to a maximum 3G usage budget.  By delaying sessions to future periods, users may gain WiFi access and the ability to offload; however, if WiFi is unavailable, the user must send these sessions over 3G, which has a finite bandwidth capacity that must be shared among the different applications.  AMUSE therefore computes a 3G bandwidth allocation when deciding whether to wait for WiFi.  Following the first principle above, we formulate this decision as a multiple choice knapsack problem, and propose a heuristic solution algorithm. % Section \ref{sec:implementation} demonstrates how such an allocation could occur in practice.

\subsection{Predicting WiFi Connectivity}\label{sec:wifi}

% Our WiFi prediction algorithm first calculates the probability of WiFi access over the next $n$ period (i.e., the next day), and then updates these probabilities over the course of the day.  Throughout the paper, we use $w_k$ to denote the probability of WiFi access in period $k$.

Since WiFi availability is heavily location-dependent, we predict the probabilities of WiFi access by combining user location prediction with the probabilities of WiFi access at different locations.  We define a ``location'' to be an area with WiFi coverage (e.g., a user's home).  To improve our prediction algorithm's accuracy, we consider the \emph{functional} availability of WiFi at different locations: while WiFi is always \emph{physically} available at a given location, the user may not access WiFi every time that she is there.  For instance, a user may sometimes connect to WiFi at her local Starbucks, but may walk by on weekdays without initiating a connection.  These access probabilities also depend on time: \revise{a user might stop at Starbucks in the morning but not in the evening}.  We use a training set of empirical WiFi access data to estimate these time-dependent WiFi access probabilities at each location, and modify them as we collect more access data.\footnote{One may refine these calculations by using only weekday or only weekend data, as user mobility will likely differ on weekdays and weekends.}  For a location $l$, we denote the probability of WiFi access during period $k$ as $v_k(l)$.  We use $L_k$ to denote the set of observed locations in period $k$.

Given the time- and location-specific probabilities $v_k(l)$, we then predict \emph{overall} WiFi access by incorporating predictions of users' future locations.  We define $w_k$ to be the overall WiFi probability in period $k$, \revise{i.e., the expected WiFi probability, considering the probabilities of all possible locations in period $k$ and the WiFi access probability in period $k$ for each location.}
We use a second-order Markov chain for the location prediction, which has been shown to be highly accurate \cite{song2006evaluating}.   Algorithm \ref{alg:wifi} summarizes the calculation of overall WiFi access probabilities.  We use the notation $p^{k + 2}_{l}(l_kl_{k + 1})$ to denote the probability that a user is at location $l\in L_{k + 2}$ during period $k + 2$, given his locations $l_k$ in period $k$ and $l_{k + 1}$ in period $k + 1$.  To calculate these $p^k$, we define $N^{k}(s)$ as the number of times that $s$ is observed, where $s$ is a sequence of locations that ends in period $k$; the observed location in each period $k$ is denoted by $\lambda_k$.  
\revise{We update the $p^k$ values using the empirical probabilities of a user being at different locations during period $k$}.
% We update the $p^k$ values as we collect more location data.

% Data on WiFi connectivity at different locations can be determined by a training set, e.g. one week of checking for WiFi availability every five minutes.  We denote the set of observed locations in period $k$ by $L_k$, and use a simple moving average on the observed probability of WiFi to compute the probability of WiFi access $v_k(l)$ in each period $k$ and $l\in L_k$. % A previous study has shown that this averaging method is generally accurate for predicting location \cite{song2010limits}, and indeed we observe xx\% accuracy with our empirical data in Section \ref{sec:eval_wifi}.


% [this paragraph may not be necessary] In general, we will have access only to a limited dataset of any individual's locations at different times of the day.  Thus, instead of constructing a Markov chain over the state space of all user locations, we \emph{cluster} locations based on the probability of WiFi connectivity.  The clustering occurs for each set of locations $L_k$ that a user has visited during period $k$.  We use the gap statistic to find the optimal number of clusters.  The set of clustered locations, denoted by $\overline{L}_k$, is then the state space in period $k$.

% To construct a Markov chain that predicts users' future locations, let $p^{k + 2}_{l}(l_kl_{k + 1})$ denote the probability that a user is at location $l\in L_{k + 2}$ during period $k + 2$, given that he was at location $l_k$ during period $k$ and location $l_{k + 1}$ during period $k + 1$.  % This probability is defined as the number of times the user follows this location pattern, divided by the number of times the user was at location $l_k$ during period $k$ and location $l_{k + 1}$ during period $k + 1$. We emphasize that the probabilities $p^{k + 2}_{l}(l_kl_{k + 1})$ \emph{depend on the period $k$}.
% We let $N^{k}(s)$ denote the number of times the sequence $s$ ending in period $k$ describes the user's location (e.g. $s = l_{k-1}l_{k}$), and find $p^{k + 2}_{l}(l_kl_{k + 1}) = N^{k+2}(l_kl_{k + 1}l_{k + 2})/N^{k+1}(l_kl_{k + 1})$.  If the sequence $l_kl_{k + 1}$ does not occur, then we consider only location data from period $k + 1$.  Given a user's actual locations $\lambda_k$ and $\lambda_{k + 1}$ during periods $k$ and $k + 1$, we can then update the $p^{k + 2}_l$.  Algorithm \ref{alg:wifi} summarizes this procedure.


% algpseudocode syntax alg
%\begin{figure}
%\begin{algorithmic}[1]\label{alg:wifi}
%\caption{Algorithm for computing WiFi access probabilities over the rest of the day in period $i$.}
%\If{$i = 1$}
%	\For{$k = 1\to n$}
%		\State $w_k = \sum_{l\in L_k} v_k(l)\frac{N^k(l)}{N}$, $N$ is the number of days of data.\Comment{Calculate WiFi probabilities for the next $n$ periods.}
%	\EndFor
%\EndIf
%\If{$i > 1$}
%\For{$k = 2 \to n$}
%	\ForAll{$l\in L_k$, $l_{k-1}\in L_{k-1}$, $l_{k - 2}\in L_{k - 2}$}
%		\If{$N^{k - 1}(l_{k - 2}l_{k - 1}) > 0$}
%			\State $p_l^{k}(l_{k - 2}l_{k - 1}) = \frac{N^{k}(l_{k - 2}l_{k - 1}l_{k})}{N^{k - 1}(l_{k - 2}l_{k - 1})}$
%		\Else
%			\State $p_l^{k}(l_{k - 2}l_{k - 1}) = \frac{N^{k}(l_{k - 1}l_{k})}{N^{k - 1}(l_{k - 1})}$
%		\EndIf
%	\EndFor
%	\State $w_k = \sum_{l\in L_{k}} p_l^k(\lambda_{k - 2}\lambda_{k - 1})v_k(l)$
%\EndFor
%\EndIf
%\end{algorithmic}
%\end{figure}

\subsection{Predicting Future Usage}\label{sec:usage}

At the beginning of each day, we use previous data to predict the size $s_j(k)$ of each application type $j\in J$'s usage in each period $k$.  To accommodate the dependence of session size on the amount of bandwidth allocated, our definitions of session ``size'' depend on the application: for fixed-volume application sessions such as downloads, in which the volume (MB) does not depend on the available bandwidth, we define the session size as its volume.  For fixed-time sessions such as streaming, in which the volume does depend on the bandwidth, we define the size as the time to complete.  We use $J_v$ to denote the set of fixed-volume and $J_t$ the set of fixed-time application types.  We stress that our prediction algorithms do not depend on the definition of session size; they rely only on users' consistency from day to day. % In the discussion below, we use ``usage'' to refer to the application size.
%
\begin{algorithm}[t]
\begin{scriptsize}
\DontPrintSemicolon
\If{$i = 1$}{
	\For{$k \leftarrow 1$ \KwTo $n$}{
		$w_k \leftarrow \sum_{l\in L_k} v_k(l)\frac{N^k(l)}{N}$, $N$ is the number of days of data. \tcp{Calculate WiFi probabilities for the next $n$ periods.}
	}
}
\If{$i > 1$}{
	\For{$k \leftarrow 2$ \KwTo $n$}{
		\ForAll{$l\in L_k$, $l_{k-1}\in L_{k-1}$, $l_{k - 2}\in L_{k - 2}$}{
			\If{$N^{k - 1}(l_{k - 2}l_{k - 1}) > 0$}{
				$p_l^{k}(l_{k - 2}l_{k - 1}) \leftarrow \frac{N^{k}(l_{k - 2}l_{k - 1}l)}{N^{k - 1}(l_{k - 2}l_{k - 1})}$\;
			} \Else {
				$p_l^{k}(l_{k - 2}l_{k - 1}) \leftarrow \frac{N^{k}(l_{k - 1}l)}{N^{k - 1}(l_{k - 1})}$\;
			}
		}
		$w_k \leftarrow \sum_{l\in L_{k}} p_l^k(\lambda_{k - 2}\lambda_{k - 1})v_k(l)$\;
	}
}
\caption{Computation of WiFi access probabilities over the rest of the day in period $i$.\label{alg:wifi}}
\end{scriptsize}
\end{algorithm}
%
We estimate the future usage $s_j(k)$ by taking a moving average of the observed usage sizes $\sigma_j(k)$ of application $j$ in period $k$ over some fixed number of days.\footnote{Other prediction methods (e.g., ARIMA) can be substituted for a moving average without affecting the overall structure of our system.}

In updating our usage estimates, we modify the moving-average calculation to take into account our deferral recommendations\revise{; we wish to predict the amount of future usage without the deferrals recommended by our algorithm}.  Since a user may delay application usage to another time in order to offload it to WiFi, we ``shift the usage back'' in order to evaluate and detect changes in the underlying usage pattern over the day.  We perform these adjustments if the observed usage size for application $j$ in period $i$ is much less than the predicted $s_j(i)$, i.e., the user has shifted her usage of application $j$ from period $i$.  To account for the uncertainty in our predictions, we suppose that the actual usage deferred to period $k$ from each period $i$ is proportional to the predicted usage deferred;\footnote{\revise{We assume that at the time of deferring an application, we cannot know how much traffic the user will defer. For many applications such as web browsing and social networking, it is hard to know the exact traffic amount they will use in advance, since their contents can be dynamically selected or created by the user.}} this assumption ensures that we do not calculate that more usage was deferred to period $k$ than the actual usage observed in that period. Thus, for each application $j\in J$ and period $i< k$, we adjust the observed usage $\sigma_j(i)$ and $\sigma_j(k)$ by
\begin{align*}
\sigma_j(i) &\leftarrow \sigma_j(i) + \sum_{k = i + 1}^n\frac{c_i^j(k)s_j(i)\sigma_j(k)}{s_j(k) + \sum_{l = 1}^{k-1}c_l^j(k)s_j(l)},\\
\sigma_j(k) &\leftarrow \sigma_j(k) - \sum_{i = 1}^{k - 1}\frac{c_i^j(k)s_j(i)\sigma_j(k)}{s_j(k) + \sum_{l = 1}^{k-1}c_l^j(k)s_j(l)}.
\end{align*}
Here $c_i^j(k)$ is an indicator variable taking the value 1 if application $j$ is deferred from period $i$ to period $k$ and 0 otherwise. \revise{The first expression adjusts the observed usage for application $j$ in period $i$ by adding the traffic amount deferred to later time periods, while the second expression adjusts by subtracting the traffic amounts deferred from previous times. This method is approximate, but we expect that it will be helpful for predicting the future traffic amounts from observed traffic.}   

%In accounting for the deferred sessions, we define the indicator variables $c_i^j(k,\gamma)$ to be 1 if a session of type $j$ is deferred from period $i$ to period $k$ and assigned 3G speed $\gamma$, and 0 otherwise.  The 3G speed (i.e., bandwidth allocated to this session if it is sent over 3G) is chosen from a finite subset of possibilities $\Gamma$.  We suppose that the actual usage deferred to period $k$ from each period $i$ is proportional to the predicted usage deferred.  Thus, for each application $j\in J$ and period $i< k$, we adjust the observed usage $\sigma_j(i)$ and $\sigma_j(k)$ by
%\begin{align*}
%\sigma_j(i) &\leftarrow \sigma_j(i) + \sum_{k = i + 1}^n\frac{\sum_{\gamma\in\Gamma}c_i^j(k,\gamma)s_j(i)\sigma_j(k)}{s_j(k) + \sum_{l = 1}^{k-1}\sum_{\gamma\in\Gamma}c_l^j(k,\gamma)s_j(l)},\\
%\sigma_j(k) &\leftarrow \sigma_j(k) - \sum_{i = 1}^{k - 1}\frac{\sum_{\gamma\in\Gamma}c_i^j(k,\gamma)s_j(i)\sigma_j(k)}{s_j(k) + \sum_{l = 1}^{k-1}\sum_{\gamma\in\Gamma}c_l^j(k,\gamma)s_j(l)}.
%\end{align*}
%These adjusted usage measurements can then be used in the moving average to update the predicted usage $s_j(k)$.

\subsection{User Utility Maximization}\label{sec:formulation}

In this section, we formulate the user's offloading decision problem, assuming the future WiFi probabilities $w_k$ and usage $s_j(k)$ are known.  In the discussion below, the phrase ``originally in period $i$'' indicates that the application session(s) under consideration are completed in period $i$ if they are not deferred to a future period.

\subsubsection{Utility Functions}

To mathematically formulate the user's offloading decision problem, we need a concrete measure of the user's tradeoffs between cost, throughput, and delay.  Thus, for a given application type $j$ in period $i$, we derive expressions for users' \emph{utility} of completing those application sessions over 3G and over WiFi.  This utility is determined by the per-volume price $p$ of 3G, the amount of time $t$ the session is deferred, the bandwidth speed $r$ at which the session is completed, and the size $s$ of the session.  We use $U_j(p, t, r, s)$ to denote the utility of application $j\in J$.

\reviseAgain{Though many functions could be used as the $U_j$, we note that these should be decreasing in $p$ and $t$ (price and time deferred) and increasing in $r$ (bandwdith). \revise{For fixed-volume applications, we suppose that the utility is decreasing in $s$, since a larger size indicates more time to complete the session.}
%and $s$.\footnote{\revise{The increase in $s$ will increase the data cost, which in turn results in decrease in utility. However, we can assume that, generally, the positive utility due to using data is larger than the negative utility due to data costs. Otherwise, users will not use the data at all.}} 
We use the economic principle of diminishing marginal utility to argue that as $r$ becomes larger or $t$ becomes smaller, users' marginal utility from $r$ should decrease, and the marginal utility from $t$ should increase.}  For simplicity, we take the units of $t$ to be the number of periods deferred, and do not consider sessions' timing \emph{within} the period to which they are deferred.  Since different users will have different tradeoffs between cost, quality, and delay, we suppose that the $U_j$ functions take the same form, but have different parameters that depend on the particular application and user.

The above guidelines still leave many possible utility functions.  To narrow these down, we conducted an online survey of over 100 users, primarily students, faculty and staff from U.S. universities.  For each application in Table \ref{tab:param}, we gave participants the cost to complete one application session over 3G, as well as the speed of WiFi relative to 3G.  We then asked the participants how long they would wait for WiFi access instead of immediately completing the session over 3G; for each question, we offered five options for the maximum amount of time participants were willing to wait, ranging from ``I won't wait'' to ``as long as necessary.''\footnote{The survey questions are available in \cite{tr}.}

We find that our survey data provides a good fit with the functional form
\begin{equation}
\begin{cases}
U_j(p, t, r, s) = C_j\exp\left(-\nu + r\nu - \mu t\right) - \eta prs &j\in J_t \\
U_j(p, t, r, s) = C_j\exp\left(-(s/r)\nu - \mu t\right) - \eta ps &j\in J_v,
\end{cases}
\label{eq:util}
\end{equation}
where $U_j$ denotes the parameterized utility function for application types $j$; $prs$ for $j\in J_t$ and $ps$ for $j\in J_v$ denote the cost of each session; and $C_j$, $\mu$, $\nu$, and $\eta$ are nonnegative parameters that depend on $j$.  These functions satisfy several desirable properties: for example, the constants $C_j$ allow for different user priorities for different types of sessions (e.g. a user intrinsically derives more utility from certain applications, even with zero delay or time to completion).\footnote{The $-\nu$ in the exponential for $j\in J_t$ is included for normalization: with maximum bandwidth 1 and no delay, we then have $U_j = C_j$.}  For $j\in J_v$, the $s/r$ term in the exponential represents the time to completion, while for $j\in J_t$, the bandwidth $r$ represents the quality of the streaming video. % For ease of notation, in the discussion below we denote the utility as $U_j(b,t,r,s) = U_j(p,t,r,s)$.

% We note that the exponential form in (\ref{eq:util}) is particularly convenient for file transfer-type sessions, as the time deferred is (assuming $\mu = \nu$) added to the time to completion $s/r$ in determining the session utility.  For these types of sessions, the \emph{total time to completion} is more important than the separate times deferred and time to download/upload.

Table \ref{tab:param} shows the parameter values calculated for each session type. 
To estimate these parameter values, we used the probability that a user would not wait for WiFi as the utility function value, with $b$, $t$, $r$ and $s$ measured relative to their values for WiFi.  We assume a negligible cost term for low-volume (e.g., email) sessions.  We then used nonlinear curve-fitting methods to calculate the utility function parameters, and found a small average squared-error of 0.05 for each survey question, upon comparing the actual answers with our estimates.  

We see that the $C_j$ coefficients roughly match our expectations, with email the most important and social networking (photo uploads) the least important applications. The parameter $\mu$ represents the amount of time that a user will wait to start an application, e.g., in anticipation of WiFi access or higher 3G speeds: it is largest (i.e., users are least willing to wait) for browsing and email. The importance of available
throughput is parameterized by $\nu$, and is highest for video and lowest for social networking. % Moreover, for Internet browsing, the time waited is more important than the time to complete the application session ($\mu > \nu$).
\begin{table}
\renewcommand{\arraystretch}{1.1}
\caption{Estimated parameters for the utility function (\ref{eq:util}).}
\label{tab:param}
\vspace{-0.1in}
\centering
\begin{tabular}{|r||cccc|}
\hline
& $C$ & $\mu$ & $\nu$ & $\eta$ \\ \hline
Email & $0.9848$ & $0.1527$ & $0.1527$ & assumed 0 \\
Browsing & $0.6865$ & $0.3269$ & $0.0263$ & assumed 0 \\
Video & $0.9399$ & $0.0144$ & $4.3785$ & $0.0986$ \\
Social netw. & $0.4738$ & $0.006$ & $0.006$ & $0.0986$ \\
Downloads & $0.6737$ & $0.0097$ & $0.0097$ & $0.0986$ \\ \hline
\end{tabular}
\vspace{-0.1in}
\end{table}

\subsubsection{Users' Optimization Problem}\label{sec:optProblem}

We now use the utility functions (\ref{eq:util}) to formulate the user's optimization problem.  To represent possible 3G and WiFi bandwidth speeds, we normalize the volume units so that the fixed per-second WiFi speed equals 1.  The 3G speed $\gamma$ is chosen from a finite subset of possibilities $\Gamma$\revise{; generally, all $\gamma < 1$ since 3G speeds are usually slower than WiFi, though for LTE networks we may have $\gamma > 1$}.  For each $\gamma\in \Gamma$ and period $k\geq i$, we define the indicator variables $c_i^j(k,\gamma)$ to be 1 if a session of type $j$ is deferred from period $i$ to period $k$ and assigned 3G speed $\gamma$, and 0 otherwise. \revise{Note that $\gamma$ is always chosen for each delayed period $k$; this speed $\gamma$ is then used if WiFi is not available in period $k$. If the probability of WiFi availablity is 100\%, any value of $\gamma$ can be chosen without affecting the user's expected utility from WiFi in period $k$. This utility,} for a session of type $j$ originally in period $i$, is then
\begin{equation*}
\left(\sum_{\gamma\in\Gamma}c_i^j(k,\gamma)\right)w_kU_j\left(0, k - i, 1, s_j(i)\right),
\end{equation*}
while the expected utility from 3G in period $k$ is
\begin{equation*}
\displaystyle\sum_{\gamma\in\Gamma}c_i^j(k,\gamma)(1 - w_k)U_j\left(p, k - i, \gamma, s_j(i)\right).
\end{equation*}
The user wishes to maximize the sum of these utilities over all (original) periods $i$ and application types $j$:
\begin{align}
\max_{c_i^j(k,\gamma)}\;\sum_{i = 1}^n\Bigg[&\sum_{j\in J}\Bigg(\sum_{k\geq i}\Bigg(\sum_{\gamma\in\Gamma}\Big(w_kU_j\big(0, k - i, 1, s_j(i)\big) +\nonumber \\
&(1 - w_k)U_j\big(p, k - i, \gamma, s_j(i)\big)\Big)c_i^j(k,\gamma)\Bigg)\Bigg)\Bigg] \label{eq:obj} \\
{\rm s.t.}\;\sum_{k\geq i} \sum_{\gamma\in\Gamma}& c_i^j(k,\gamma) = 1;\;c_i^j(k,\gamma) \in\left\{0,1\right\}, \label{eq:var}
\end{align}
where (\ref{eq:var}) ensures that each application $j$ in period $i$ is deferred to only one period $k$ (we may have $k = i$), with 3G speed $\gamma$.  This optimization is performed subject to two constraints: a budget constraint on expected 3G usage, and capacity constraints on the 3G bandwidth in each period.

We assume that the user specifies a maximum monthly budget $\overline{B}$ for 3G usage.  We then calculate a \emph{daily budget} $B$, taking into account both the number of days remaining in the month (denoted by $m$) and the amount of budget $B_r$ that has not yet been spent.  To allow the user some flexibility, we multiply the average usage $B_r/m$ by the factor $\exp\left(1 - m^{-1}\right)$, which equals 1 only if $m = 1$: at the end of the month, the user cannot exceed the remaining budget. The daily budget $B$ is then defined as $B_r \exp\left(1 - m^{-1}\right)/m$, and the budget constraint is
\begin{align}
p\sum_{i = 1}^n\Bigg[&\sum_{j\in J_v}\left(\sum_{k\geq i}\sum_{\gamma\in\Gamma} c_i^j(k,\gamma)(1 - w_k)s_j(i)\right) + \nonumber \\
&\sum_{j\in J_t}\left(\sum_{k\geq i}\sum_{\gamma\in\Gamma} c_i^j(k,\gamma)(1 - w_k)\gamma s_j(i)\right)\Bigg]\leq B,
\label{eq:budget}
\end{align}
The 3G bandwidth capacity constraints ensure that the sum of the bandwidth allocated to each application in a given period does not exceed the fixed maximum bandwidth, which we denote as $\beta$.  Mathematically, this constraint is
\begin{equation}
(1 - w_l)\sum_{i\leq l}\sum_{j\in J}\sum_{\gamma\in\Gamma} c_i^j(l,\gamma)\gamma\leq (1 - w_l)\beta.
\label{eq:capacity}
\end{equation}
We include a $1 - w_l$ term on each side so that if $w_l = 1$ and all sessions complete over WiFi, any 3G speed $\gamma$ may be chosen.  Putting (\ref{eq:obj}-\ref{eq:capacity}) together, we obtain the optimization problem
\begin{align}
\max_{c_i^j(k,\gamma)}\;\sum_{i = 1}^n&\Bigg[\sum_{j\in J}\Bigg(\sum_{k\geq i}\Bigg(\sum_{\gamma\in\Gamma}\Big(w_kU_j\big(0, k - i, 1, s_j(i)\big) +\nonumber \\
&(1 - w_k)U_j\big(p, k - i, \gamma, s_j(i)\big)\Big)c_i^j(k,\gamma)\Bigg)\Bigg)\Bigg] \label{eq:newobj} \\
{\rm s.t.}\;p\sum_{i = 1}^n\Bigg[&\sum_{j\in J_v}\left(\sum_{k\geq i}\sum_{\gamma\in\Gamma} c_j^i(k,\gamma)(1 - w_k)s_j(i)\right) + \nonumber \\
&\sum_{j\in J_t}\left(\sum_{k\geq i}\sum_{\gamma\in\Gamma} c_j^i(k,\gamma)(1 - w_k)\gamma s_j(i)\right)\Bigg]\leq B \label{eq:newbudget} \\
(1 - w_l&)\sum_{i\leq l}\sum_{j\in J}\sum_{\gamma\in\Gamma} c_j^i(l,\gamma)\gamma\leq (1 - w_l)\beta\,\forall\,l \label{eq:newcapacity} \\
\sum_{k\geq i} \sum_{\gamma\in\Gamma} &c_j^i(k,\gamma) = 1\,\forall\,j\in J;\;i = 1,2,\ldots,n \label{eq:newvar} \\
c_j^i(k,\gamma)&\in\left\{0,1\right\}. \nonumber
\end{align}
\revise{Note that the problem's decision variables $c_i^j(k,\gamma)$ for all time periods $i$ and applications $j$ represent the schedule for application deferrals and 3G rates to be used if the WiFi is not available at the scheduled times. Other variables such as $w_k$ and $s_j(i)$ are calculated by empirical data as explained in Sections \ref{sec:wifi} and \ref{sec:usage}.} We can view the constraints (\ref{eq:newvar}) as choosing exactly one item from a knapsack, where each $(i,j)$ pair for $i = 1,2,\ldots,n$ and $j\in J$ is associated with a knapsack consisting of items indexed by the variables $k\geq i$ and $\gamma\in\Gamma$. With this interpretation, (\ref{eq:newobj}-\ref{eq:newvar}) can be seen as a multidimensional, multiple choice knapsack problem.\reviseAgain{
In the Appendix~\ref{sec:extension}, we show that we can easily extend this formulation so that the varying WiFi capacity is considered and the user chooses which network to use depending on the utility values of WiFi and 3G.}

\subsection{Online Algorithm}\label{sec:online}

In this section, we present an online algorithm to solve the optimization problem (\ref{eq:newobj}-\ref{eq:newvar}).  At the beginning of each day, the user computes an initial solution, given estimates of the $w_k$ and $s_j(k)$.  As the $w_k$ estimates and known usage amounts are updated over the day, this solution is refined.

While various algorithms exist to compute solutions of the knapsack problem (\ref{eq:newobj}-\ref{eq:newvar}) to different degrees of accuracy, we use a Lagrange-multiplier based solution \cite{moser1997algorithm} that has relatively small computational overhead and generally returns good approximations to the optimum.\footnote{Since our estimates of WiFi access and future usage are already approximations, even an exact solution to the optimization (\ref{eq:newobj}-\ref{eq:newvar}) will be an approximation of the ``true'' optimum.}  Given a feasible solution, the algorithm improves the solution while maintaining its feasibility, allowing us to update previously computed solutions over the day.

This Lagrange multiplier algorithm starts from a solution that maximizes (\ref{eq:newobj}) without considering the constraints  (\ref{eq:newbudget}-\ref{eq:newvar}).
%This Lagrange multiplier algorithm starts from an optimal solution, neglecting constraints.  
The solution is then adjusted so that all constraints are satisfied, beginning with the ``most violated'' (i.e., the constraint with largest Lagrange multiplier).  This process repeats until no constraints are violated, and the solution can then be improved by adjusting the solution one variable at a time, so as to most increase the objective value while still not violating the constraints.\footnote{\label{footnote_constraint}If the constraints are especially tight, the Lagrange multiplier algorithm may not yield a solution.  While in practice such a situation is unlikely to occur, we can easily recover from this failure by taking as the initial allocation the worst-case scenario, in which all sessions are given the lowest possible bandwidth; we assume that this is a feasible solution. \revise{If only the bandwidth constraint is violated, we can simply scale down the 3G bandwidths assigned to different applications.}}

% We note that this algorithm can be facilitated by noting that if $w_i = 1$, then $c_i^j(0,\gamma) = 1$ for all $j\in J$, $\gamma\in\Gamma$ in period $i$, while $c_j(\gamma) = 0$ for $\gamma > 0$, $j\in J$ in period $i$.  In words, if WiFi is definitely available, the user does not complete any sessions over 3G.  We expect that this will be the case for certain hours, e.g. during the night or early morning if the user has WiFi at home.

As the user consumes data over the day, we update both the remaining daily budget $B$ and our predictions of future WiFi connectivity $\left\{w_k\right\}$.  The new optimization problem over the remainder of the day can then be solved by taking the existing solution as the initial point of our Lagrange multiplier algorithm.  This solution may well be feasible: the 3G capacity constraints do not change unless WiFi becomes definitely available in some period ($w_k\rightarrow 1$), in which case that period $k$'s capacity constraint is  removed.  Thus, if the existing solution satisfies the new budget constraint, we can skip directly to the ``solution improvement'' step, significantly reducing the computational overhead.  Algorithm \ref{alg:everything} presents this full online algorithm, along with the WiFi and app usage predictions (Sections \ref{sec:wifi} and \ref{sec:usage}).

\begin{algorithm}[t]
\begin{scriptsize}
\DontPrintSemicolon
$i \leftarrow 1$ \tcp{The current period is denoted by $i$.}
$B\leftarrow \left(B_r/m\right)\exp\left(1 - m^{-1}\right)$ \tcp{Calculate the budget for the day.}
Calculate WiFi probabilities using Algorithm \ref{alg:wifi} with $i = 1$.\;
Calculate predicted usage over all $n$ periods using a moving average.\;
Allocate bandwidth by approximately solving (\ref{eq:newobj}-\ref{eq:newvar}).\;
\For{$i\leftarrow 2$ \KwTo $n$}{
	$B\leftarrow B - S_{i - 1}$ \tcp{Remaining daily budget, given the spending $S_{i - 1}$ in period $i - 1$.}
	Update WiFi probabilities using Algorithm \ref{alg:wifi}.\;
	Update bandwidth allocations by re-solving (\ref{eq:newobj}-\ref{eq:newvar}) for the remaining $n - i + 1$ periods.\;
}
\caption{Bandwidth allocation over a day.\label{alg:everything}}
\end{scriptsize}
\end{algorithm}

% algpseudocode syntax alg
%\begin{figure}
%\begin{algorithmic}[1]\label{alg:everything}
%\caption{Algorithm for allocation bandwidth over a day.}
%\State $i \leftarrow 1$ \Comment*{The current period is denoted by $i$.}
%\State $B\leftarrow \left(B_r/m\right)\left(1 + \exp\left(-(30 - m)^{-1}\right)\right)$ \Comment{Calculate the budget for the day.}
%\State Calculate WiFi probabilities using Algorithm \ref{alg:wifi} with $i = 1$.
%\State Calculate predicted usage over all $n$ periods using a moving average of the previous 3 days.
%\State Allocate bandwidth by approximately solving (\ref{eq:newobj}-\ref{eq:newvar}).
%\For{$i = 2\to n$}
%	\State $B\leftarrow B - S_{i - 1}$ \Comment{Remaining daily budget, given the spending $S_{i - 1}$ in period $i - 1$.}
%	\State Update WiFi probabilities using Algorithm \ref{alg:wifi}.
%	\State Update bandwidth allocations by re-solving (\ref{eq:newobj}-\ref{eq:newvar}) for the remaining $n - i + 1$ periods.
%\EndFor
%\end{algorithmic}
%\end{figure}

%We first evaluate whether using the optimal solution from the previous period will yield a solution over or under budget (if it yields a solution just equal to the budget, we do not change anything).  If the solution is over budget, we must incrementally decrease spending, which can be done by a) moving more sessions to WiFi, or b) decreasing the speed of the streaming sessions.  If we are under budget, then the solution from the previous period is feasible, and we could simple leave it.  However, we can improve the objective value (\ref{eq:newobj}) by adjusting the user's spending upwards, i.e., not plan to delay some session types to WiFi.  We now give the heuristic algorithm for each case.
%\begin{itemize}
%\item
%{\bf Over-budget:} For each fixed-volume session $j$ in each period $i$, we calculate the difference between the current utility due to that session (i.e., the utility with the current $c_j(\gamma)$) and the utility if we take $c_j(0) = 1$, i.e., shift the session to WiFi.  For each streaming session, we calculate the difference between the current utility and the next-lowest utility possible (either the next-lowest speed, or the utility from shifting to WiFi).  These difference are called the \emph{utility losses} for application $j$ in period $i$, denoted as $l_j^i$.  We then start with the lowest utility loss $l_j^i$, adjust $c_j(\gamma)$ accordingly, and proceed until the constrain (\ref{eq:adjbudget}) is satisfied.
%\item
%{\bf Under budget:}  For each application type $j$ in period $i$ with $c_j(0) = 1$, we calculate the \emph{utility gain} $d_j^i$, the difference between the utility from WiFi and the next highest utility possible.  To calculate the utility from WiFi, we use the updated $w_i$ probabilities.  Starting from the highest positive $d_j^i$, we then shift sessions from WiFi to 3G, testing whether (\ref{eq:adjbudget}) is still satisfied after each shift.  If it is not, we move to the next highest $d_j^i$, etc.
%
%In shifting these sessions, we must be careful to observe the maximum bandwidth constraints (\ref{eq:bandwidth}).  Thus, a more accurate calculation of the utility gain $d_j^i$ would incorporate the utility losses from lowering the bandwidth speeds of other applications in period $i$.  Since we only consider those sessions for which $d_j^i > 0$ and $c_j(0) = 1$, calculating this utility loss for each application $j$ and period $i$ may be feasible: if we have $c_j(\gamma) \rightarrow 1$, we calculate the utility loss from lowering the bandwidth of each application $j$ with $c_j(\gamma) = 1$.  We then begin from the lowest utility loss and lower the applications' bandwidth until (\ref{eq:bandwidth}) is satisfied, then subtract the sum of these utility losses from $d_j^i$ to obtain the \emph{aggregate utility gain}.  We then start from the highest aggregate utility gain and keep shifting sessions so that (\ref{eq:adjbudget}) and (\ref{eq:bandwidth}) are satisfied.
%\end{itemize}

%  \end{document}
Appendix.tex
\appendices
\section{Extension of users' optimization problem}
\label{sec:extension}
\revise{
	Our optimization problem in Section~\ref{sec:optProblem} assumes a constant speed for WiFi and prefers WiFi to 3G as long as WiFi is available. However, we can extend it to choose the WiFi speed for each application subject to a time- and location-varying maximum WiFi bandwidth (e.g., home WiFi is generally more stable than WiFi at a coffee shop). In this case, users can choose to use either 3G or WiFi instead of automatically using WiFi when it is available. Thus, users must account for the speed, cost, delay, and traffic amount for 3G and WiFi and choose the interface that yields the highest utility.
	The user's modified optimization problem is as follows:
	\begin{align}
	\max_{c_i^j(k,\gamma,\delta)}\;&\sum_{i = 1}^n\Bigg[\sum_{j\in J}\Bigg(\sum_{k\geq i}\Bigg(\sum_{\gamma\in\Gamma}\Bigg(\sum_{\delta\in\Delta}\Big(U_j\big(0, k - i, \delta, s_j(i)\big) +\nonumber \\
	&U_j\big(p, k - i, \gamma, s_j(i)\big)\Big)c_i^j(k,\gamma,\delta)\Bigg)\Bigg)\Bigg)\Bigg] \nonumber \\
	{\rm s.t.}\;p&\sum_{i = 1}^n\Bigg[\sum_{j\in J_v}\left(\sum_{k\geq i}\sum_{\gamma\in\Gamma} c_j^i(k,\gamma,0)s_j(i)\right) + \nonumber \\
	&\sum_{j\in J_t}\left(\sum_{k\geq i}\sum_{\gamma\in\Gamma} c_j^i(k,\gamma,0)\gamma s_j(i)\right)\Bigg]\leq B \nonumber \\
	&\sum_{i\leq l}\sum_{j\in J}\sum_{\gamma\in\Gamma} c_j^i(l,\gamma,0)\gamma\leq \beta\,\forall\,l \nonumber\\
	&\sum_{i\leq l}\sum_{j\in J}\sum_{\delta\in\Delta} c_j^i(l,0,\delta)\delta\leq \alpha(l)\,\forall\,l \label{eq:WiFiCapaConstraint}\\
	&\sum_{k\geq i} \sum_{\gamma\in\Gamma} \sum_{\delta\in\Delta} c_j^i(k,\gamma,\delta) = 1\,\forall\,j\in J;\;i = 1,2,\ldots,n \nonumber \\
	&c_j^i(k,\gamma,\delta) = 0,\forall\gamma>0,\delta>0 \label{eq:oneNetSelect} \\ 
	&c_j^i(k,\gamma,\delta)\in\left\{0,1\right\}. \nonumber
	\end{align}
	We change the indicator variables $c_i^j(k,\gamma)$ to $c_i^j(k,\gamma,\delta)$ so that WiFi speed $\delta$ can be chosen.
	The WiFi speed $\delta$ is chosen from a finite subset of possibilities $\Delta$. Here, $\Delta$ and $\Gamma$ include $0$ so that we can represent the case when the WiFi and 3G are not used. We add a capacity constraint on the WiFi bandwidth in (\ref{eq:WiFiCapaConstraint}). $\alpha(l)$ is the predicted WiFi bandwidth in period $l$. We limit the rate allocation so that only one network is chosen in (\ref{eq:oneNetSelect}). 
	%Note that we removed the probability of WiFi access $w_l$ in this formulation, since it can be reflected in $\alpha(l)$: if no WiFi is available $\alpha(l)$ will be 0. 
	We expect that the WiFi bandwidth prediction algorithm can be designed by modifying the Algorithm~\ref{alg:wifi} so that $v_k(l)$ represents the product of WiFi probability and bandwidth at time $k$ and location $l$, and the expected available bandwidth at each time is updated using empirical data.	
}

\revise{	
	This formulation can be modified into a second optimization problem to be solved in each period to choose the final 3G and WiFi bandwidths for applications scheduled to that period. For all application types $j$ originated in period $i$ where $\sum_{\gamma\in\Gamma}\sum_{\delta\in\Delta}c_i^j(k,\gamma,\delta)>0$ for the current period $k$, we solve following problem:}
  
\revise{	
	\begin{align}
	\max_{c_i^j(k,\gamma,\delta)}\;&\sum_{\gamma\in\Gamma}\Bigg(\sum_{\delta\in\Delta}\Big(U_j\big(0, k - i, \delta, s_j(i)\big) +\nonumber \\
	&U_j\big(p, k - i, \gamma, s_j(i)\big)\Big)c_i^j(k,\gamma,\delta)\Bigg) \nonumber \\
	{\rm s.t.}\;p&\sum_{\gamma\in\Gamma} c_j^i(k,\gamma,0)\gamma\leq \beta\, \nonumber\\
	&\sum_{\delta\in\Delta} c_j^i(k,0,\delta)\delta\leq \alpha(k)\, \nonumber \\
	&\sum_{\gamma\in\Gamma} \sum_{\delta\in\Delta} c_j^i(k,\gamma,\delta) = 1\, \nonumber \\
	&c_j^i(k,\gamma,\delta) = 0,\forall\gamma>0,\delta>0 \nonumber \\ 
	&c_j^i(k,\gamma,\delta)\in\left\{0,1\right\}. \nonumber
	\end{align}	  
	If the bandwidth constraints are violated, we can simply scale down the bandwidths assigned to different applications so as to satisfy the constrains as we discussed in footnote~\ref{footnote_constraint}. Instead, we may delay some applications to later periods, if we use the original formulation.   
}    
\section{Top 15 applications for WiFi and cellular networks}
\label{sec:top_applications}
Tables~\ref{tab:top_wifi} and ~\ref{tab:top_cellular} show the 15 most-used applications on WiFi and cellular networks, respectively.
\begin{table*}[ht]
	\renewcommand{\arraystretch}{1.1}
	\caption{Top 15 applications in WiFi network.} \label{tab:top_wifi}
	\vspace{-0.1in}
	\centering
	\begin{tabular}{|c||c||c|c|c|c|}
		\hline Index & Package name & Upload(\%) & Download(\%) & Total(\%) & Type \tabularnewline \hline \hline 
		%Streaming Media&	8032.3& 	8848.3& 	16880.6& 	Video\tabularnewline \hline
		%android.process.media&	375.1& 	434.1& 	809.3& 	Video\tabularnewline \hline
		%com.google.android.music:main&	368.6& 	368.9& 	737.5& 	Unclassified\tabularnewline \hline
		%com.google.android.music:ui&	366.7& 	366.7& 	733.3& 	Unclassified\tabularnewline \hline
		%com.android.email&	281.8& 	344.6& 	626.4& 	Email\tabularnewline \hline
		%com.emogoth.android.phone.mimi&	305.3 &	305.3 &	610.6 &	Social Networking\tabularnewline \hline
		%com.marvel.capinstaller&	202.1 &	202.1 &	404.3 &	Downloads\tabularnewline \hline
		%com.android.browser	&141.3 &	225.9 &	367.2 &	Browsing\tabularnewline \hline
		%com.clearchannel.iheartradio.controller&	169.3 &	169.3 	& 338.6 &	Unclassified\tabularnewline \hline
		%com.facebook.katana:providers&	122.9 &	172.7 &	295.6 &	Social Networking\tabularnewline \hline
		%com.facebook.katana	&106.0 &	174.6 &	280.6 	&Social Networking\tabularnewline \hline
		%com.motorola.process.system&	5.8 	&271.9 	&277.7 &	Unclassified\tabularnewline \hline
		%com.rhythmnewmedia.android.e	&92.5 	&146.9 	&239.5 &	Unclassified\tabularnewline \hline
		%com.ninegag.android.app	&79.0 	&86.2&	165.1 &	Unclassified\tabularnewline \hline
		
		1 & Streaming Media	&	70.20 	&	66.38 	&	68.14 	&	Video	\tabularnewline \hline
		2 & android.process.media	&	3.28 	&	3.26 	&	3.27 	&	Video	\tabularnewline \hline
		3 & com.google.android.music:main	&	3.22 	&	2.77 	&	2.98 	&	Unclassified	\tabularnewline \hline
		4 & com.google.android.music:ui	&	3.20 	&	2.75 	&	2.96 	&	Unclassified	\tabularnewline \hline
		5 & com.android.email	&	2.46 	&	2.59 	&	2.53 	&	Email	\tabularnewline \hline
		6 & com.emogoth.android.phone.mimi	&	2.67 	&	2.29 	&	2.46 	&	Social networking	\tabularnewline \hline
		7 & com.marvel.capinstaller	&	1.77 	&	1.52 	&	1.63 	&	Downloads	\tabularnewline \hline
		8 & com.android.browser	&	1.23 	&	1.69 	&	1.48 	&	Browsing	\tabularnewline \hline
		9 & com.clearchannel.iheartradio.controller	&	1.48 	&	1.27 	&	1.37 	&	Unclassified	\tabularnewline \hline
		10 & com.facebook.katana:providers	&	1.07 	&	1.30 	&	1.19 	&	Social networking	\tabularnewline \hline
		11 & com.facebook.katana	&	0.93 	&	1.31 	&	1.13 	&	Social networking	\tabularnewline \hline
		12 & com.motorola.process.system	&	0.05 	&	2.04 	&	1.12 	&	Unclassified	\tabularnewline \hline
		13 & com.rhythmnewmedia.android.e	&	0.81 	&	1.10 	&	0.97 	&	Unclassified	\tabularnewline \hline
		14 & com.ninegag.android.app	&	0.69 	&	0.65 	&	0.67 	&	Unclassified	\tabularnewline \hline
		& Others	&	6.93 	&	9.10 	&	8.10 	&-		\tabularnewline \hline
		
	\end{tabular}
\end{table*}
\begin{table*}[ht]
	\renewcommand{\arraystretch}{1.1}
	\caption{Top 15 applications in cellular network.} \label{tab:top_cellular}
	\vspace{-0.1in}
	\centering
	\begin{tabular}{|c||c||c|c|c|c|}
		\hline Index & Package name & Upload(\%) & Download(\%) & Total(\%) & Type \tabularnewline \hline \hline 
		%Streaming Media&	126.5& 	2991.1& 	3117.6& 	Video\tabularnewline \hline 
		%com.android.email&	125.1& 	391.8& 	516.9& 	Email\tabularnewline \hline 
		%android.process.media&	89.5& 	418.1& 	507.6& 	Video\tabularnewline \hline 
		%com.facebook.katana&	165.7& 	271.0& 	436.7& 	Social Networking\tabularnewline \hline 
		%com.android.browser&	150.4& 	233.4& 	383.8& 	Browsing\tabularnewline \hline 
		%com.google.android.music:main&	0.8& 	369.3& 	370.2& 	Unclassified\tabularnewline \hline 
		%com.facebook.katana:providers&	139.8& 	175.8& 	315.6&	Social Networking\tabularnewline \hline 
		%com.rhythmnewmedia.android.e&	116.7& 	139.8& 	256.4& 	Unclassified\tabularnewline \hline 
		%com.pandora.android&	104.1& 	104.4& 	208.5 &	Unclassified\tabularnewline \hline 
		%com.noinnion.android.greader.reader&	98.1& 	98.1& 	196.1& 	Unclassified\tabularnewline \hline 
		%com.motorola.blur.service.main&	64.0& 	69.8& 	133.9& 	Unclassified\tabularnewline \hline 
		%com.motorola.contacts&	64.0& 	66.1& 	130.1& 	Unclassified\tabularnewline \hline 
		%com.alphonso.pulse&	48.1& 	74.7& 	122.8& 	Social Networking\tabularnewline \hline 
		%com.motorola.process.system&	7.7& 	114.9& 	122.7& 	Unclassified\tabularnewline \hline 
		%com.clearchannel.iheartradio.controller&	23.7& 	87.6& 	111.3& 	Unclassified\tabularnewline \hline 
		
		1 & Streaming Media	&	5.70 	&	42.64 	&	33.77 	&	Video	\tabularnewline \hline
		2 & com.android.email	&	5.64 	&	5.59 	&	5.60 	&	Email	\tabularnewline \hline
		3 & android.process.media	&	4.03 	&	5.96 	&	5.50 	&	Video	\tabularnewline \hline
		4 & com.facebook.katana	&	7.47 	&	3.86 	&	4.73 	&	Social networking	\tabularnewline \hline
		5 & com.android.browser	&	6.78 	&	3.33 	&	4.16 	&	Browsing	\tabularnewline \hline
		6 & com.google.android.music:main	&	0.04 	&	5.27 	&	4.01 	&	Unclassified	\tabularnewline \hline
		7 & com.facebook.katana:providers	&	6.30 	&	2.51 	&	3.42 	&	Social networking	\tabularnewline \hline
		8 & com.rhythmnewmedia.android.e	&	5.26 	&	1.99 	&	2.78 	&	Unclassified	\tabularnewline \hline
		9 & com.pandora.android	&	4.69 	&	1.49 	&	2.26 	&	Unclassified	\tabularnewline \hline
		10 & com.noinnion.android.greader.reader	&	4.42 	&	1.40 	&	2.12 	&	Unclassified	\tabularnewline \hline
		11 & com.motorola.blur.service.main	&	2.89 	&	1.00 	&	1.45 	&	Unclassified	\tabularnewline \hline
		12 & com.motorola.contacts	&	2.89 	&	0.94 	&	1.41 	&	Unclassified	\tabularnewline \hline
		13 & com.alphonso.pulse	&	2.17 	&	1.07 	&	1.33 	&	Social networking	\tabularnewline \hline
		14  & com.motorola.process.system	&	0.35 	&	1.64 	&	1.33 	&	Unclassified	\tabularnewline \hline
		15 & com.clearchannel.iheartradio.controller	&	1.07 	&	1.25 	&	1.21 	&	Unclassified	\tabularnewline \hline
		& Others	&	40.28 	&	20.08 	&	24.93 	&-		\tabularnewline \hline
		
	\end{tabular}
\end{table*}

conclusion_revised.tex
\section{Conclusion}
\label{sec:Conclusion}

In this paper, we propose AMUSE, a cost-aware WiFi offloading system that maximizes the {\it end user's} utility under her 3G budget constraints. AMUSE consists of two main components: a bandwidth optimizer and a TCP rate controller.  By predicting future usage and WiFi availability, the bandwidth optimizer chooses how long an application should wait for WiFi access, as well as a 3G data rate should WiFi not be available. These choices are optimized so as to balance the user's tradeoffs between the cost of sending an application's traffic over 3G, the higher throughput received over WiFi, and the delay inherent in waiting for WiFi. The TCP rate controller practically enforces the 3G rates chosen for each application by controlling the TCP advertisement window from the user side.  AMUSE also allows for end-user interaction by providing a user interface through which users can set their bandwidth allocation preferences and view the offloading decisions made.
Through a measurement study, we show that though a large amount of some applications' traffic is offloaded already, our offloading framework can offload a larger portion of mobile users' cellular traffic.

We prototyped AMUSE and evaluated its performance with mobile traces from 37 users. Our results show that AMUSE can improve both heavy and light data users' utility from offloading; for heavy users, two other representative WiFi offloading algorithms achieve 27\% lower utility than AMUSE on average.  Heavy users' costs were on average 18 and 36\% higher under these benchmark algorithms compared to AMUSE, a savings realized by offloading more traffic onto WiFi. Though our results are based on data from a limited number of users, we expect similar performance from a wider range of users. %We also plan to conduct field trials of AMUSE with real Windows tablets and 3G  laptop dongle users, to practically evaluate AMUSE's benefits for mobile data users.


Evaluation_revised.tex
%\documentclass[conference]{IEEEtran}
%%% INFOCOM 2013 addition:
%\makeatletter
%\def\ps@headings{%
%\def\@oddhead{\mbox{}\scriptsize\rightmark \hfil \thepage}%
%\def\@evenhead{\scriptsize\thepage \hfil \leftmark\mbox{}}%
%\def\@oddfoot{}%
%\def\@evenfoot{}}
%\makeatother
%\pagestyle{headings}
%
%% ybim added
%\usepackage[latin9]{inputenc}
%%\pagestyle{headings}
%\usepackage{array}
%\usepackage{verbatim}
%\usepackage{multirow}
%\usepackage{amsmath}
%\usepackage{amssymb}
%\usepackage{graphicx}
%\usepackage{cite}% Written by Donald Arseneau
%\usepackage{epstopdf}
%%\usepackage[boxed,vlined,figure,algonl]{algorithm2e}
%\usepackage[ruled,vlined]{algorithm2e}
%%\usepackage{algpseudocode}
%\graphicspath{./image/}
%\usepackage{color}
%\usepackage{subfigure}
%
%% *** GRAPHICS RELATED PACKAGES ***
%%
%\ifCLASSINFOpdf
%  % \usepackage[pdftex]{graphicx}
%  % declare the path(s) where your graphic files are
%  % \graphicspath{{../pdf/}{../jpeg/}}
%  % and their extensions so you won't have to specify these with
%  % every instance of \includegraphics
%  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
%\else
%  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
%  % will default to the driver specified in the system graphics.cfg if no
%  % driver is specified.
%  % \usepackage[dvips]{graphicx}
%  % declare the path(s) where your graphic files are
%  % \graphicspath{{../eps/}}
%  % and their extensions so you won't have to specify these with
%  % every instance of \includegraphics
%  % \DeclareGraphicsExtensions{.eps}
%\fi
%
%\hyphenation{op-tical net-works semi-conduc-tor}
%
%
%\begin{document}

\section{Experimental Evaluation} \label{sec:evaluation}

To evaluate the effects of AMUSE's Bandwidth Optimizer (Algorithm \ref{alg:everything} in Section \ref{sec:allocation_algorithm}) on users' offloading experience, we collected 3G and WiFi usage and mobility data from an additional 12 Android and 25 iPhone users over a period of 19 days and one week, respectively, as explained in Section \ref{sec:data_collection}.  We then simulate the performance of AMUSE's bandwidth optimizer, taking the recorded usage data as the historical usage, and compare AMUSE's performance with two other known offloading algorithms \revise{in \cite{OffloadingCoNext2010}}.  Our results show that AMUSE can both reduce users' spending and improve their utility compared with these two benchmarks.

\subsection{Experimental Data and Settings} \label{sec:empirical_data_collection}

\begin{figure*}[ht]
\vspace{-0.2in}
\centering
\subfloat[Cellular usage.]{\includegraphics[scale=0.45,bb = 30 40 360 202]{./evaluation_combined/cumulative_usage_iphone_cellular-eps-converted-to.pdf}\label{fig:cumulative_usage_iPhone_cellular}}
\subfloat[WiFi usage.]{\includegraphics[scale=0.45,bb = -30 40 320 202]{./evaluation_combined/cumulative_usage_iphone_wifi-eps-converted-to.pdf}\label{fig:cumulative_usage_iPhone_wifi}} 
\caption{Normalized cumulative usage of iPhone users.}
\end{figure*}

\begin{figure*}[ht]
\vspace{-0.2in}
\centering
\subfloat[Cellular usage.]{\includegraphics[scale=0.45,bb = 30 40 360 202]{./evaluation_combined/cumulative_usage_android_cellular-eps-converted-to.pdf}\label{fig:cumulative_usage_android_cellular}}
\subfloat[WiFi usage.]{\includegraphics[scale=0.45,bb = -30 40 320 202]{./evaluation_combined/cumulative_usage_android_wifi-eps-converted-to.pdf}\label{fig:cumulative_usage_android_wifi}} 
\caption{Normalized cumulative usage of Android users.}
\end{figure*}

%\begin{figure}
%\centering
%\includegraphics[scale=0.65,bb = 50 50 310 202]{evaluation_combined/cumulative_usage_iphone_cellular.eps}
%\caption{Normalized Cumulative Cellular Usage of iPhone Users.}
%\label{fig:screen}
%\end{figure}
%
%\begin{figure}
%\centering
%\includegraphics[scale=0.65,bb = 50 50 310 202]{evaluation_combined/cumulative_usage_iphone_wifi.eps}
%\caption{Normalized Cumulative WiFi Usage of iPhone Users.}
%\label{fig:screen}
%\end{figure}

%\begin{figure}
%\centering
%\includegraphics[scale=0.65,bb = 50 50 310 202]{evaluation_combined/cumulative_usage_android_cellular.eps}
%\caption{Normalized Cumulative Cellular Usage of Android Users.}
%\label{fig:screen}
%\end{figure}
%
%\begin{figure}
%\centering
%\includegraphics[scale=0.65,bb = 50 50 310 202]{evaluation_combined/cumulative_usage_android_wifi.eps}
%\caption{Normalized Cumulative WiFi Usage of Android Users.}
%\label{fig:screen}
%\end{figure}


Since some of our users exhibited very similar traffic patterns and some showed very limited data usage, we choose sixteen representative users' data on which to run the AMUSE simulation (eight each for iPhone and Android). 
Figures \ref{fig:cumulative_usage_iPhone_cellular} and \ref{fig:cumulative_usage_iPhone_wifi} represent the normalized cumulative usage of selected iPhone users for cellular and WiFi, respectively. 
The normalized cumulative usage of selected Android users for cellular and WiFi networks are shown in Figure \ref{fig:cumulative_usage_android_cellular} and \ref{fig:cumulative_usage_android_wifi}. 
We can observe that the chosen representative users show diverse usage patterns in both WiFi and cellular networks.
We use three days of data as each user's usage history, and run the simulation assuming hour-long periods.  The user's monthly budget for 3G data usage is chosen from a truncated normal distribution between \$20  and \$40 (2 to 4 GB at a unit price of \$10/GB).
% During the simulation experiments, we intentionally increase the traffic over 3G links, which is 4 times as much as that of the WiFi links. This setting is for us to see the performance of each offloading algorithm.
%\begin{figure}
%\centering
%\includegraphics[width = 0.2\textwidth]{image/DataWiz_main.png}
%\includegraphics[width = 0.2\textwidth]{image/DataWiz_usage.png}
%\caption{An Android App, DataWiz, for measuring network usage and connectivity.}
%\label{fig:android_app}
%\end{figure}

%\subsection{Offloading Potential}
%We first evaluate the potential of WiFi offloading by examining the amount of traffic carried over 3G and WiFi data.  Figure xxx shows the number of WiFi networks accessed per user; we see that most users access relatively few WiFI networks, indicating that they tend to follow consistent patterns from day to day.  Indeed, users are often on WiFI networks; Figure xxx shows the fraction of the time (number of 10 minute intervals) for which the user had WiFi access.  Thus, users visit relatively few locations with WiFi connectivity, but for relatively large amounts of time.  Indeed, a significant, though not overwhelming, fraction of usage takes place over WiFi, as shown in Fig. xxx.

\begin{figure}[t]
\vspace{-0.2in}
\centering
\includegraphics[scale=0.4]{./evaluation_android/wifi_prediction_accuracy-eps-converted-to.pdf}
\vspace{-0.2in}
\caption{CDF of WiFi prediction accuracy.}
\label{fig:wifi_prediction_accuracy}
\end{figure}
\begin{figure}[t]
\vspace{-0.2in}
	\centering
	\includegraphics[scale=0.4]{./wifi_stat/cdf_wifi_location_count-eps-converted-to.pdf}
	\vspace{-0.2in}
	\caption{CDF of the number of different locations per a day where WiFi network is accessed.}
	\label{fig:cdf_wifi_location_count}
\end{figure}
\begin{figure}[t]
	\centering
	\includegraphics[scale=0.4,angle=-90,bb=79 31 310 599]{./wifi_stat/wifi_access_count-eps-converted-to.pdf}
	\caption{WiFi access frequency per a day of each iPhone user.}
	\label{fig:wifi_access_count}
\end{figure}

% \subsection{Accuracy of WiFi Access Predictions}
To verify that our three-day training set of data is \revise{reasonable} to simulate AMUSE, we test the accuracy of our WiFi prediction algorithm on this dataset.  To do so, we define the prediction accuracy as follows: if the probability of WiFi access for a given user in a given future period is greater (respectively less) than 0.5 and we observe (respectively do not observe) WiFi access in that period, we classify the prediction as ``accurate.''  Otherwise, we call the prediction ``inaccurate.''  We then divide the number of accurate predictions by the total number of predictions for each user to find the prediction accuracies. \revise{As shown in Figure \ref{fig:wifi_prediction_accuracy}, we observe a 64 -- 90\% prediction accuracy for the eight iPhone users and a 67 -- 97\% accuracy for the eight Android users. %indicating that our data is sufficient for producing meaningful simulation results. 
To further inspect the prediction accuracy, we tested the algorithm on other open mobility traces. We used the data of 21 users who have enough records needed for prediction from the dataset collected in the LifeMap project~\cite{chon2011mobility}. We obtained similar accuracy as on our dataset (64 -- 95\% accuracy).}

\revise{We show the WiFi access frequency per a day of each iPhone user in Figure~\ref{fig:wifi_access_count}. Except user 1, each user has a similar WiFi access frequency for each day. 
We show the number of different locations per a day where WiFi network is accessed in Figure~\ref{fig:cdf_wifi_location_count}. We can observe that each user accesses the WiFi network within a small number of locations. These results coincides with assumptions of our location dependent WiFi prediction method.}  

% listed in Table ~\ref{tab:wifi_prediction}.

%\begin{table}[!t]
%\renewcommand{\arraystretch}{1.0}
%\centering
%\begin{tabular}{|c|c||c|c|}
%\hline User Index & Accuracy (\%) & User Index & Accuracy \tabularnewline \hline \hline
%1&68.72&5&78.02 \tabularnewline \hline
%2&89.98&6&74.28 \tabularnewline \hline
%3&81.64&7&65.10 \tabularnewline \hline
%4&89.13&8&63.89 \tabularnewline \hline
%\end{tabular}
%\caption{Accuracy of WiFi connectivity prediction for each user.} \label{tab:wifi_prediction}
%\vspace{-0.2in}
%\end{table}

\subsection{Baseline Algorithms}

We compare AMUSE's performance to two baseline algorithms: on-the-spot offloading and delayed offloading \cite{OffloadingCoNext2010}. %%oSCTP\cite{6089074},

On-the-spot offloading offloads traffic to WiFi opportunistically: users send their traffic over WiFi if they are connected to a WiFi network at that time, and switch to 3G if they move outside of the WiFi coverage area.  No sessions ever wait for WiFi, which may lead to higher spending as compared with AMUSE -- AMUSE allows delay-tolerant sessions to wait for WiFi, thus saving users money.
The delayed offloading algorithm forces all traffic to wait up to a fixed time limit for WiFi access (1 hour in our simulations). If WiFi becomes available before this time, the waiting traffic is sent over WiFi; otherwise, it is sent over 3G. While this algorithm may offload more traffic than AMUSE and thus save users money, it does not consider users' delay tolerances: even urgent sessions are forced to wait for some time.  Moreover, if WiFi is not available at the end of the fixed time limit, the sessions will complete over 3G anyway, costing users money and making them wait.  % The fixed-rate AMUSE is for evaluating the benefits of AMUSE algorithm without rate selection.


%\subsection{Example Scenario}

%\begin{figure}[t]
%\vspace{-0.1in}
%\centering
%\includegraphics[scale=0.5,bb = 40 20 300 230]{evaluation_android/traffic_demand_example.eps}
%\vspace{-0.1in}
%\caption{An example traffic demand.}
%\label{fig:traffic_demand_example}
%\end{figure}
%
%\begin{figure}[t]
%\vspace{-0.1in}
%\centering
%\includegraphics[scale=0.5,bb = 40 20 300 230]{evaluation_android/traffic_demand_example_offloaded.eps}
%\vspace{-0.1in}
%\caption{The amounts of traffic offloaded for the example traffic demand under each offloading algorithm.}
%\label{fig:traffic_demand_example_offloaded}
%\end{figure}

\begin{figure}[t]
\vspace{-0.1in}
\centering
\includegraphics[scale=0.55]{./evaluation_android/traffic_demand_example_combined.pdf}
\vspace{-0.1in}
\caption{An example traffic demand and cellular usage amount under each offloading algorithm.}
\label{fig:traffic_demand_example_combined}
\end{figure}

In Figure \ref{fig:traffic_demand_example_combined}, we show an illustrative example scenario that explains how AMUSE operates compared to other algorithms in making offloading decisions. Figure \ref{fig:traffic_demand_example_combined} illustrates the cellular traffic demand and WiFi availability of one user for 8 hours. At 1pm, the traffic demand is larger than other times, and WiFi is available at 3pm and 7pm. The amount offloaded with each offloading algorithm can be calculated from the difference in total demand and traffic for each algorithm. Since AMUSE predicts the WiFi availability and delays longer than 1 hour if the utility is increased, it offloads a considerable amount of the traffic in 1pm to 3pm. On the other hand, On-the-spot offloading offloads only the traffic at 3pm and 7pm when the WiFi is available. Delayed offloading offloads more than On-the-spot offloading by delaying the traffic of 2pm and 6pm to 3pm and 7pm, respectively. However, since it cannot predict the WiFi availability of 3pm at 1pm, it cannot delay the traffic of 1pm to 3pm, thus losing the opportunity to offload. Moreover, since it blindly delays the traffic by one hour if the WiFi is not available, the traffic of 12, 1, 4, 5pm is delayed but ultimately transmitted by 3G, decreasing users' utility. AMUSE, on the other hand, does not always prefer offloading to transmitting on 3G network. For example, AMUSE delays only some traffic at 1pm, since the expected utility of transmitting over 3G is larger than that of waiting for higher bandwidth and lower cost WiFi. % In this case, the decrease in utility by delaying traffic from 1pm to 3pm offsets the benefit of reducing the cost since the amount of the traffic demand is small. 

% \subsection{Numerical Results}

% The AMUSE delays applications to later period so that it can utilize offloading while the on-the-spot algorithm offloads only if the WiFi is available when the application starts. The AMUSE algorithm offloads more than delayed algorithm for several users, since it can defer for a longer time periods than the delayed algorithm having a deadline. On the other hand, the AMUSE algorithm offloads less than delayed algorithm for user 3 and 6, since the AMUSE does not delay the application if the budget is enough, and the utility of not delaying is better than delaying.
% We note that for all users, the delayed algorithm offloads more than the on-the-spot algorithm, since users always wait for WiFi under the former algorithm, but never wait under the latter.

\subsection{Numerical Results}

\begin{figure}[t]
\vspace{-0.3in}
\centering
\includegraphics[scale=0.45]{./evaluation_combined/utility_cdf-eps-converted-to.pdf}
\vspace{-0.1in}
\caption{CDF of relative utility function values compared to AMUSE.}
\label{fig:utilities}
%\vspace{-0.1in}
\end{figure}

Figure \ref{fig:utilities} plots the distributions of relative utility values under our benchmark algorithms compared to those under AMUSE.  For each user, both benchmark algorithms decrease the utility. This decrease is particularly dramatic for one user, whose utility values with on-the-spot and delayed offloading are only 8 and 23\%, respectively, of the utility under AMUSE.  On average, the utility of on-the-spot offloading is 19\% less than that of AMUSE, while that of delayed offloading is 22\% lower.

\begin{figure}[t]
\vspace{-0.3in}
\centering
\includegraphics[scale=0.45]{./evaluation_combined/offloaded_spent_cdf-eps-converted-to.pdf}
\vspace{-0.1in}
\caption{CDF of relative offloaded traffic amount and amount spent compared to AMUSE.}
\label{fig:offloaded_spent_cdf}
%\vspace{-0.1in}
\end{figure}

%\begin{figure}[t]
%%\vspace{-0.3in}
%\centering
%\includegraphics[scale=0.5]{evaluation_combined/utility_combined.eps}
%\vspace{-0.25in}
%\caption{Distribution of utility function values compared with AMUSE.}
%\label{fig:utilities}
%\vspace{-0.1in}
%\end{figure}
%
%\begin{figure}[t]
%\vspace{-0.1in}
%\centering
%\includegraphics[scale=0.5]{evaluation_combined/offload_combined.eps}
%\vspace{-0.25in}
%\caption{Traffic offloaded  compared to AMUSE.}
%\label{fig:offloaded}
%\vspace{-0.07in}
%\end{figure}


AMUSE yields higher utility values than on-the-spot offloading due to offloading more traffic onto WiFi: Fig. \ref{fig:offloaded_spent_cdf} shows the distributions of relative amounts of traffic offloaded under both benchmark algorithms, as compared to AMUSE.  We see that for all users, the amount of traffic offloaded is larger under AMUSE than it is under on-the-spot offloading; thus, AMUSE leverages the delay tolerance of some sessions by allowing them to wait for WiFi access.  Users then save money: Fig. \ref{fig:offloaded_spent_cdf} also compares users' amount spent under the two benchmark algorithms to that spent with AMUSE.  Users consistently spend over 20\% more with on-the-spot offloading, and on average increase their spending by 33\% compared with AMUSE. 


%\begin{figure}[t]
%%\vspace{-0.2in}
%\centering
%\includegraphics[scale=0.5]{evaluation_combined/expense_combined.eps}
%%\subfigure[Total costs of users with small usage.]
%%{
%%	\includegraphics[scale=0.50]{evaluation_new/expense1_bigfont.eps}
%%}
%%\subfigure[Total costs of users with large usage.]
%%{
%%	\includegraphics[scale=0.50]{evaluation_new/expense2_bigfont.eps}
%%}
%\vspace{-0.25in}
%\caption{Distribution of amount spent for different users.}
%\label{fig:spending}
%\vspace{-0.1in}
%\end{figure}

Compared to delayed offloading, AMUSE trades off between reducing users' spending by offloading traffic and completing some sessions immediately due to their intolerance of delay.  Figure \ref{fig:offloaded_spent_cdf} shows that delayed offloading offloads more traffic than AMUSE for 10 users: AMUSE sends some sessions over 3G without waiting for WiFi, allowing users to spend more and delay less.  
%User 6, who has a smaller delay tolerance than the other users, 
One user offloads nearly 160\% more traffic under delayed offloading relative to AMUSE. The consequent decrease in cost relative to AMUSE (nearly 80\%) is offset by less delay under AMUSE; this user in fact experiences 5\% less utility under delayed offloading than that under AMUSE.
On the other hand, delayed offloading offloads less traffic than AMUSE for 6 users: AMUSE allows delay-tolerant traffic to wait more than an hour for WiFi. We found that this additional wait for WiFi reduces these users' spending, offsetting the loss in utility from delaying the session.
% Figure \ref{fig:offloaded} compares the amount of each user's traffic that the two benchmark algorithms offload over three days, relative to that offloaded by AMUSE.  We see that for users 1 and 5, AMUSE offloads more traffic than either of the benchmarks; for the other users, AMUSE offloads more than on-the-spot but less than delayed offloading.  Thus, for most users, AMUSE allows delay-tolerant sessions to wait for WiFi access, offloading more than on-the-spot offloading.  However, AMUSE does not force delay-intolerant traffic to wait; some traffic that would have waited for WiFi under delayed offloading is instead sent immediately over 3G.

% suffers (as compared with AMUSE) due to sessions' never waiting for WiFi; thus, users spend more than they would have under AMUSE.  Indeed, Fig. \ref{fig:spending} shows the usage costs of the benchmark algorithms, compared to that of AMUSE; we see that under AMUSE, users spend less than with on-the-spot offloading, for an average savings of xx\%.  On the other hand, AMUSE does not delay sessions as strictly as delayed offloading; since urgent sessions are not forced to wait for WiFi, users' utility increases.  Some users save money as well; Fig. \ref{fig:spending} shows that AMUSE reduces the costs of all users except users 3 and 6 (who have high traffic usage).  Highly delay-tolerant applications can afford to wait more than one hour for WiFi under AMUSE, while delayed offloading cannot accommodate this flexibility.

%The utility of AMUSE is larger than fixed-rate AMUSE, because the AMUSE control the bandwidth, putting more sessions in one time slot which is limited by 3G capacity, and reducing the cost of data by controlling  the bandwidth of streaming session.


% Finally, we show the amount spent money for individual users.  Figure \ref{fig:spending}a shows the total cost of users who spent relatively small amount of money, and Figure \ref{fig:spending}b is the total cost of users who spent a large amount of money.
% We see that the variation of data cost among users are large.
%The data cost of AMUSE is smaller than on-the-spot offloading, since on-the-spot offloads can not defer the application for future offloading opportunities.
%Since the AMUSE algorithm can use more offloading opportunities than delayed offloading, the costs of AMUSE for 6 users are less than delayed offloading.
%However, since the AMUSE does not delay the applications if the budget is enough or the utility of not deferring is larger than deferring, the cost of AMUSE can be larger than delayed (2 users in the experiment).
%The data cost of delayed offloading is smaller than on-the-spot offloading for all users, since delayed offloading offloads more than on-the-spot offloading,

%We also simulated the offloading algorithms over Android traces. The utility values show a similar trend to those of iPhone users.  Figure \ref{fig:utilities_android} represents each user's utility under AMUSE and other benchmark algorithms. On average, the utility of on-the-spot offloading is 20\% less than that of AMUSE, while that of delayed offloading is 27\% lower. From Fig. \ref{fig:offloaded_android} and Fig. \ref{fig:spending_android}, we can also find that AMUSE offloads more traffic than on-the-spot offloading, and that AMUSE reduces more the total data cost of mobile users than other offloading algorithms except some light users. 

Finally, we examine AMUSE's benefits for different types of users.  We split 16 users into ``heavy'' and ``light'' usage groups (8 users for each group), and plot the amount offloaded, utility, and cost of the two benchmark algorithms relative to AMUSE in Fig. \ref{fig:total_iphone_android}.  For heavy users, both benchmark algorithms perform worse than AMUSE: users' utility and amount offloaded decrease under these algorithms, while their cost increases.  Thus, AMUSE's cost savings in offloading more traffic offset any loss in utility from waiting more for WiFi access.  On-the-spot offloading performs especially poorly compared to AMUSE, indicating that most users' delay tolerance enables them to gain utility under AMUSE by selectively delaying some sessions and sending them over WiFi. For light users, AMUSE weights the cost savings from waiting for WiFi less heavily: some sessions do wait for WiFi, as shown by the decrease in amount offloaded in on-the-spot offloading, but delay-intolerant sessions do not wait, as shown by the increase in amount offloaded in delayed offloading.  This likely arises from light users' looser budget constraint: by definition, light users spend less than heavy users on their data consumption.  They accordingly benefit less overall: compared with AMUSE, the utility of heavy users decreases by 27\% under the benchmark algorithms, while that of light users decreases by 14\%.

% two benchmark algorithms reveal different phenomena: (i) AMUSE increases the utility and amount offloaded, and decreases the cost as compared to on-the-spot offloading, and (ii) AMUSE decreases the amount offloaded, while increasing the utility and cost, compared to delayed offloading.  Since light users consume relatively little of their 3G budget, AMUSE sends some of their traffic over 3G, as compared to delayed offloading: with enough money left over, users will not wait for WiFi and instead spend money on immediate 3G usage. Indeed, AMUSE's improvement in user utility is xx\% for heavy and yy\% for light users, indicating that AMUSE is most effective for heavy users.  These users are more likely to have tight budget constraints, benefiting more from AMUSE's balancing of their cost-delay tradeoff.
% To compare the overall performance of offloading algorithms, we presented the average performance values in Figure ~\ref{fig:utilities_average}. Since the importance of the bandwidth management is different among users depending on the total data usage, we divided the users into heavy users and light users, and compared the performance between two user groups. We can find that in the case of heavy users, AMUSE shows better performance than other algorithms in all performance metrics.

% Figure \ref{fig:spendingall} shows the amount spent up to each hour of the week; we see that the amount spent increases fairly uniformly, indicating that users spend approximately the same amount in each hour.




%\begin{figure}
%\centering
%\includegraphics[width = 0.4\textwidth]{Matlab/TotalSpending_Old.eps}
%\caption{Amount spent up to each hour of the week for all users.}
%\label{fig:spendingall}
%\end{figure}

% \end{document}

%\begin{figure}[t]
%%\vspace{-0.3in}
%\centering
%\includegraphics[scale=0.60]{evaluation_android/utility_android.eps}
%\vspace{-0.25in}
%\caption{Distribution of utility function values compared with AMUSE in Android traces.}
%\label{fig:utilities_android}
%\vspace{-0.1in}
%\end{figure}
%
%\begin{figure}[t]
%\vspace{-0.1in}
%\centering
%\includegraphics[scale=0.60]{evaluation_android/offload_android.eps}
%\vspace{-0.25in}
%\caption{Traffic offloaded  compared to AMUSE in Android traces.}
%\label{fig:offloaded_android}
%\vspace{-0.07in}
%\end{figure}
%
%\begin{figure}[t]
%%\vspace{-0.2in}
%\centering
%\includegraphics[scale=0.60]{evaluation_android/expense_android.eps}
%\vspace{-0.25in}
%\caption{Distribution of amount spent for different users in Android traces.}
%\label{fig:spending_android}
%\vspace{-0.1in}
%\end{figure}

\begin{figure}[t]
\vspace{-0.1in}
\centering
\includegraphics[scale=0.45]{./evaluation_android/total_iphone_android-eps-converted-to.pdf}
\vspace{-0.25in}
\caption{Average offloaded traffic, utility, and cost of heavy and light users in all traces.}
\label{fig:total_iphone_android}
\vspace{-0.07in}
\end{figure}
implementation_revised.tex
\section{Implementation}

\label{sec:Implementation}
%AMUSE consists of three main components: (i) User Interface, (ii) Bandwidth Optimizer, and (iii) Bandwidth Controller. We implement the User Interface and Bandwidth Controller in a real system for evaluation, while the Bandwidth Optimizer is implemented in simulation code for evaluation.

We implemented an AMUSE prototype on Windows 7 tablets with the system architecture shown in Fig. \ref{fig:architecture}. 
We used the Windows Filtering Platform (WFP)~\cite{WFPCalloutDriver} to track application usage and implement a user-side TCP rate control algorithm to control each application's download rate. 
% The WFP driver allows us to modify the TCP advertisement window in outgoing ACKs.

The AMUSE prototype displays both total usage and the usage of individual applications on a daily, weekly, and monthly basis, as well as the current upload and download rates. 
We also provide user interfaces from which the user can, if he so chooses, set the download rate of each application and configure his billing starting date and data plan (e.g., 2GB per month). Figure \ref{fig:amuse_screenshot} shows screenshots of these features.

\begin{figure}[t]
\centering 
\centering \includegraphics[scale=0.215]{image/datawiz_prediction.pdf}\hspace{0.1in}
\includegraphics[scale=0.215]{image/datawiz_bwcontrol.pdf} 
\vspace{-0.1in}
\caption{Screenshots of the AMUSE prototype. Users can view their monthly usage and set bandwidth rates for individual applications.}
\label{fig:amuse_screenshot}
\vspace{-0.1in}
\end{figure}


We next describe the details of our receiver-side TCP rate control algorithm, followed by experimental data verifying its efficacy.

\subsection{Receiver-Side TCP Rate Control }
\label{sec:BWControl}

%Shaping the upload rates is trivial, since most operating systems offer a tool that throttles the rate of outgoing traffic (e.g.,\texttt{tc} command~\cite{tcsite} in UNIX). 
%However, controlling the download rates from the user side is challenging. We consider only TCP download traffic since it accounts for most of the download traffic. 

% ingress->download
% bandwidth -> capacity
% through

%With regard to the bandwidth usage of
%an application from a mobile user's perspective, we can consider four kinds of user traffic:
%TCP download, TCP upload, UDP download, and UDP upload. Controlling TCP
%upload and UDP upload traffic is trivial, since most operating systems
%offer a tool that throttles the rate of outgoing traffic (e.g., tc command~\cite{tcsite} in UNIX).
%Traffic
%control tools focus on the sets of mechanisms by which packets are queued
%for transmission/reception on a network interface. Their operations
%consist of enqueueing, policing, classifying, scheduling, shaping
%and dropping\cite{tcsite}.
%However, controlling TCP and UDP
%download traffic from a mobile user is not trivial.
%We deal with only TCP download traffic here, since it accounts for most of the download traffic.

%If we simply apply policing (and dropping)
%mechanisms to the packets in incoming TCP traffic,
%while the rate of incoming TCP traffic would converge to an intended rate after all, users would suffer from poor quality in terms of throughput and delay during this transition. 
%This is because the traffic control tools in current operating systems drop the packets exceeding the target rate without considering the internal operations of the TCP protocol. 

\revise{Algorithm~\ref{alg:everything} decides the 3G rate that will be used if WiFi is not available during the scheduled time period. In this section, we introduce a TCP rate control algorithm that applies the decided 3G rate to the receiver-side TCP connection, enforcing the result of Algorithm~\ref{alg:everything}. We devised a receiver-side TCP rate control algorithm since TCP accounts for most Internet traffic~\cite{rahmati2011mobile}, and sender-side TCP rate control can be easily implemented (e.g. using $tc$ in the Linux system).}

A TCP sender adjusts a session's rate based on its congestion window size ($cwnd$).  The ACK packets from the receiver act as a feedback to the sender on how much has been sent and how much more can be sent to the receiver. 
We use this ACK clocking to shape the incoming/downloading rates of TCP traffic, by modifying the TCP advertisement window size ($rcv\_wnd$) field in each ACK packet using the WFP driver. 
The idea behind this approach is that a TCP sender cannot send more than ${\rm min} \left(cwnd, rcv\_wnd\right)$.  While one could instead shape the TCP traffic rates by adjusting the round-trip time (RTT) of each flow (i.e., stretching each ACK packet), this latter approach increases the overall response time and renders some interactive or video TCP applications useless. Modifying the advertisement window size does not increase the RTT of each flow, making it suitable for all TCP applications.

% Therefore, we propose a practical receiver-side rate control mechanism that shapes the rate of incoming TCP traffic by dynamically adjusting $rcv\_wnd$ in the outgoing ACKs.

Unlike current traffic control tools, our proposed control mechanism does not forcibly drop incoming packets, a measure that can induce such undesirable side effects as frequent TCP timeouts. The principle behind our mechanism is as follows:
\textit{we increase the size of the advertisement window if the traffic rate recently received is smaller than the target bandwidth,
and decrease it if the traffic rate recently received is larger than the target bandwidth}.
%We use the TCP advertisement window as a tool for the TCP receiver
%to notify the TCP sender of the desirable traffic rate currently. 
With this approach, we can implement the bandwidth control
entirely at the TCP receiver. The sender is not modified, but it will react to the advertisement window from the receiver according to TCP flow control.\footnote{In order to not hurt a user's response time with short-lived TCP flows, the algorithm only runs after 5 secs, during which these short-lived flows can complete their transfers.}
%We will explain the detailed algorithm in the following, and the experiment results of proposed mechanism will be discussed
%in Section~\ref{sec:Implementation}.
\begin{algorithm}[t]
\begin{scriptsize}
\DontPrintSemicolon
Initialization:\;
$~~~target\_BW \leftarrow$ \tcp{ Desired bandwidth (bytes/sec)}
$~~~min\_adv\_win \leftarrow 512 ~(bytes)$\;
$~~~adv\_win \leftarrow min\_adv\_win$\;
$~~~last\_check\_time \leftarrow current\_time ~(sec)$\;
$~~~check\_period \leftarrow 0.2 ~(sec)$\;
$~~~bytes \leftarrow 0 ~(bytes)$\; \tcp{accumulated received bytes for current period}
$~~~\alpha \leftarrow 0.5$ \tcp{smoothing factor}
For each TCP data and ACK packet:\;
\Begin{
	\If {a data packet is received}{
		$bytes \leftarrow bytes + packet\_len$\;
		\If {$current\_time-last\_check\_time>check\_period$}{
			$interval \leftarrow current\_time - last\_check\_time$\;
			$throughput \leftarrow bytes / interval$\;
			$inc \leftarrow adv\_win * \frac{target\_BW - throughput}{target\_BW} * \alpha$\;
			$adv\_win \leftarrow adv\_win + inc$\;
			\If {$adv\_win>rcv\_buf\_size$}{
				$adv\_win \leftarrow rcv\_buf\_size$\;
			}
			\ElseIf {$adv\_win<min\_adv\_win$}{
				$adv\_win \leftarrow min\_adv\_win$\;
			}
			$last\_check\_time \leftarrow current\_time$\;
			$bytes \leftarrow 0$\;
		}
	}
	\If {an ACK packet is ready to be sent}{
		set the advertisement window of the ACK to $adv\_win$\;
	}
}
\caption{Receiver-side TCP rate control.~\label{alg:advWinControl}}
\vspace{-0.05in}
\end{scriptsize}
\end{algorithm}
%\subsection{Bandwidth Control Algorithm}
%The pseudo code of the proposed receiver-side flow control algorithm that adjust its advertisement window is
%described in Algorithm \ref{alg:advWinControl}. 

Algorithm \ref{alg:advWinControl} presents the pseudo code of our implementation.
The algorithm first initializes the $adv\_wnd$ to the default value ($min\_adv\_win$) when the connection is set up,
and periodically calculates the traffic throughput for each application in each period.\footnote{We set this value
to 200 msec. We found this value works well in various settings after comprehensive experiments.}
The throughput is obtained by dividing the received bytes ($bytes$) by the interval length ($interval$). If the throughput for a given period is smaller than the target bandwidth ($target\_BW$), we increase the advertisement window size by an amount ($inc$) proportional to the deficit throughput.
Similarly, if the throughput is larger than the target bandwidth, we decrease the size of the advertisement window
by an amount ($dec$) proportional to the surplus throughput.
Depending on the increase/decrease of the advertisement window, the TCP sender
will increase or decrease the rate of the traffic accordingly, assuming its congestion window is mostly larger than its advertisement window.
Here, we multiply the deficit/surplus bandwidth by a ratio $\alpha$, in order to reduce the
oscillation of throughput due to the drastic window size changes.
We use $\alpha = 0.5$ after experimentally determining this value's efficacy in achieving the target bandwidth in
several different environments.
We prevent the advertisement window size from moving above the maximum buffer size ($rcv\_buf\_size$) and below minimum window size ($min\_adv\_win$). 


%We set the minimum window size to 512 bytes to prevent the drastic increase
%of the window afterwards due to excessively small window value and resulting throughput decrease.
%The window scale option should be handled if needed
%when we set the advertisement window of the ACK packet.


%\subsection{User-side bandwidth control API}
%We suggest that the OS system provides an API that each application can specify the
%target bandwidth, and the application can get the statistics about the throughput.







%A user can also see the total usage (of all the applications), and set the budget for each week or month.
% It also notifies the user of the usage deferral and throttling, as well as the saved cost by offloading.

%We implement the Bandwidth Controller in Windows 7 using the Windows Filtering Platform (WFP) Callout Driver~\cite{WFPCalloutDriver}. By using the WFP Callout Driver, we first classify flows, each of which is assigned its target bandwidth usage by the bandwidth allocation algorithm.  We then use WFP Callout Driver to carry out packet modification (i.e., advertisement window size) for bandwidth control.

%We implement several callouts in WFP for inspecting and modifying the outgoing and incoming packets. We record the amount of bytes that are sent or received in each application for traffic statistics. For advertisement window adjustment, we inspect every ingress TCP data packet as described in Algorithm~\label{alg:advWinControl}. Then we write the calculated advertisement window size to each outgoing TCP ACK packet.

%\begin{figure}[t]
%\centering \includegraphics[scale=0.50]{image/basic_op.eps} \caption{Basic operation test using Iperf.}
%\label{fig:basic_bc_op}
%\end{figure}


\subsection{Experimental Efficacy}
\label{sec:BWControlEval}

To verify Algorithm \ref{alg:advWinControl} in practice, we first test our receiver-side bandwidth control algorithm by running \texttt{Iperf} over Ethernet, WiFi, and 3G networks.
We used target bandwidths of 100 Kbps, 500 Kbps, and 1 Mbps;  experimental results for the three cases are shown in Table~\ref{tab:basic_bc_op}.
While the bandwidth control algorithm achieves the target rate in each of the three different networks, we observe that the rate over the Ethernet link is much closer to the target rate than the rates over WiFi and 3G: packet loss rate and link jitter are the smallest in Ethernet. 

\begin{table}[t]
\renewcommand{\arraystretch}{1.1}
\caption{Basic rate control test using Iperf. Parentheses denote the standard deviations.} \label{tab:basic_bc_op}
\vspace{-0.1in}
\centering
\begin{tabular}{|c||c|c|c|}
\hline Target rate & 100 Kbps & 500 Kbps & 1,024 Kbps \tabularnewline \hline \hline 
Ethernet & 103.8 (0.42) & 506.2 (0.42) & 1031.2 (1.81)  \tabularnewline \hline 
WiFi & 83.14 (3.63) & 459 (6.46) & 902.4 (21.67) \tabularnewline \hline 
3G & 95.28 (1.52) & 474.7 (11.86) & 896 (47.28)
\tabularnewline \hline
\end{tabular}
\end{table}

We also test the algorithm with different applications. For this experiment, we set the target bandwidth to 300 Kbps and run two applications (HTTP and FTP). 
Our results (Table~\ref{tab:application_bc_op}) show that the rates achieved are similar to the target rate. 

\begin{table}[t]
\renewcommand{\arraystretch}{1.1}
\caption{Application rate control test using HTTP and FTP. Parentheses denote the standard deviations.} \label{tab:application_bc_op}
\vspace{-0.1in}
\centering
\begin{tabular}{|c||c|c|}
\hline Application (rate) & HTTP (300 Kbps) & FTP (300 Kbps) \tabularnewline \hline \hline 
Ethernet & 297.04 (3.54) & 291.2 (4.68)\tabularnewline \hline 
WiFi & 271.12 (10.77) & 269.28 (8.27) \tabularnewline \hline 
3G & 296.16 (3.33) & 279.2 (4.43)
\tabularnewline \hline
\end{tabular}
\vspace{-0.05in}
\end{table}

\begin{figure}[t]
\vspace{-0.2in}
\centering \includegraphics[scale=0.50]{image/advWin_throughput_variation-eps-converted-to.pdf} 
\vspace{-0.3in}
\caption{An example of throughput and advertisement window variations.}
\label{fig:advWin_throughput_variation}
\end{figure}


Finally, we show the time evolution of the advertisement window size $rcv\_wnd$ and the resulting downloading rate in
Figure \ref{fig:advWin_throughput_variation} for one FTP flow with a target bandwidth of 300 Kbps. The target bandwidth is represented by a straight green line.
%We ran the flow for a minute, and averaged the window size and the throughput for each 1 second period.
The time evolution of $rcv\_wnd$ and the rate behave as expected: if the flow rate is smaller than the target, then the window size increases, increasing the rate after a delay. The opposite behavior is seen if the flow rate is larger than the target, but eventually both the flow rate and window size stabilize.

%We observe that if the rate of a flow is smaller than the target rate, the window size increases, which in turn increases the rate after some delay.
%Similarly, if the actual rate is larger than the target rate, the window size decreases, and the actual rate is also decreased after some time.
%If the actual rate stabilizes around the target rate, the window size converges.



%\begin{figure}[t]
%\centering \includegraphics[scale=0.50]{image/application_op.eps} \caption{Application throughput test using HTTP and FTP.}
%\label{fig:application_bc_op}
%\end{figure}





%\subsubsection{Real application}
%In this section, we test our bandwidth control mechanism in real applications. We choose FTP file download, HTTP file download, and Video streaming as our test scenarios. For video streaming scenario, we use an adaptive bitrate streaming technique[]. A typical video streaming uses an %approximately fixed network bandwidth, so we cannot throttle the bandwidth under the bandwidth used. However the adaptive bitrate streaming technique selects among several bitrates, so we test the bandwidth control by choosing a target bandwidth which is larger than the minimum %bitrate.


%Now we look closely into a scenario where a timeout happens due to
%ACK spacing. As stated in Section ~\ref{sec:BWControl}, when RFC
%1323 is implemented timeouts happen scarecely since RTO timer is updated
%per every packet. So we experimented with RFC 1323 timestamp function.
%We also turned off SACK, frto.

%3g, wifi,

%fairness, co-existence, ack pacing in wireless

%rto calculation comparison with real experiment






intro_revised2.tex
%\documentclass[conference]{IEEEtran}
%%% INFOCOM 2013 addition:
%\makeatletter
%\def\ps@headings{%
%\def\@oddhead{\mbox{}\scriptsize\rightmark \hfil \thepage}%
%\def\@evenhead{\scriptsize\thepage \hfil \leftmark\mbox{}}%
%\def\@oddfoot{}%
%\def\@evenfoot{}}
%\makeatother
%\pagestyle{headings}
%
%% ybim added
%\usepackage[latin9]{inputenc}
%%\pagestyle{headings}
%\usepackage{array}
%\usepackage{verbatim}
%\usepackage{multirow}
%\usepackage{amsmath}
%\usepackage{amssymb}
%\usepackage{graphicx}
%\usepackage{cite}% Written by Donald Arseneau
%\usepackage{epstopdf}
%%\usepackage[boxed,vlined,figure,algonl]{algorithm2e}
%\usepackage[ruled,vlined]{algorithm2e}
%%\usepackage{algpseudocode}
%\graphicspath{./image/}
%\usepackage{color}
%\usepackage{subfig}
%
%% *** GRAPHICS RELATED PACKAGES ***
%%
%\ifCLASSINFOpdf
%  % \usepackage[pdftex]{graphicx}
%  % declare the path(s) where your graphic files are
%  % \graphicspath{{../pdf/}{../jpeg/}}
%  % and their extensions so you won't have to specify these with
%  % every instance of \includegraphics
%  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
%\else
%  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
%  % will default to the driver specified in the system graphics.cfg if no
%  % driver is specified.
%  % \usepackage[dvips]{graphicx}
%  % declare the path(s) where your graphic files are
%  % \graphicspath{{../eps/}}
%  % and their extensions so you won't have to specify these with
%  % every instance of \includegraphics
%  % \DeclareGraphicsExtensions{.eps}
%\fi
%
%\hyphenation{op-tical net-works semi-conduc-tor}
%
%
%\begin{document}

\section{Introduction}

\label{sec:Introduction}

%1 introduction (1.5 page)
%1.1 Managing Mobile Data Explosion
%- B/W Caps, throttling, WiFi carpeting
%1.2 Empowering Users
%- Benefits to users
%- Benefits to ISPs
%- Net Neural Solution
%1.3 Challenges & contributions
%- user budget
% * user-side allocation & control
%- allocation for apps
% usage
% availability of WiFi, 3G
%- implementation / realizing
% propose TCP control
% Control for end-user

%The growing popularity of mobile devices has recently caused a surge in data usage, driven by applications such as mobile video, cloud services, and online magazines. 
%%According to \cite{Cisco VNI}, mobile traffic is growing at 78\% annually and is expected to account for more than 54\% of IP traffic in 2015. 
%According to \cite{CiscoVNI2014}, mobile data traffic will grow at 61\% annually from 2013 to 2018, reaching 15.9 exabytes per month by 2018. 
%To cope with this unprecedented demand, many wireless Internet Service Providers (ISPs), including AT\&T and Verizon in the U.S., have adopted tiered (usage-based) pricing plans to discourage heavy usage, even discarding their existing unlimited flat-rate data plans \cite{Verizon}.  In addition to these efforts at reducing traffic, they have begun to shift some traffic to other networks, offering free WiFi hotspots and femtocells to offload their 3G traffic \cite{nycwifi,chandrasekhar2008femtocell}.  However, though beneficial for ISPs, these new data plans and offloading measures do not always match the interests of their customers \cite{SDP,sen2012incentivizing}.

Recent unprecedented increases in demand for mobile data traffic have begun to stress many mobile operators' networks: Cisco, for instance, predicts that mobile data traffic will grow at 61\% annually from 2013 to 2018, reaching 15.9 exabytes per month by 2018 \cite{CiscoVNI2014}. To cope with this surge in data usage, which is driven by applications such as mobile video, cloud services, and online magazines, many ISPs (Internet service providers) have adopted tiered pricing plans with monthly data caps to discourage heavy usage \cite{sen2012incentivizing}. To further reduce network traffic, many ISPs have also introduced supplementary networks such as WiFi hotspots or femtocells to offload their cellular traffic \cite{nycwifi,chandrasekhar2008femtocell,sen2013survey}. Such supplementary offerings introduce new challenges for users as they decide which parts of their traffic can be offloaded at what times.

\subsection{Empowering User Decisions}

Many data plans, especially in the U.S., charge large overage fees when users exceed a monthly usage cap. While offloading to WiFi reduces cellular data usage, thus saving users money on their data spending, they must also take into account WiFi's intermittent availability and higher throughput performance.  At some times, e.g., while out shopping, a user does not have immediate WiFi access and must wait for WiFi connectivity. The user then faces a choice:
\begin{itemize}
\item
\emph{Don't wait for WiFi:} The user must consume cellular data, using up some of his data cap, and may experience lower throughput than WiFi. However, she need not wait for data access, which is important for urgent applications, e.g. email.
\item
\emph{Wait for WiFi:} The user can save money and experience higher throughput, but must decide \emph{how long} to wait. Different applications can wait for different periods of time, e.g., cloud backups might be more delay tolerant than photo uploads to Facebook. Given each app's willingness to wait for some period of time, users must anticipate whether WiFi will be available at that time and decide whether the potential savings in data offloading and potential increase in throughput are worth the wait.

Waiting for WiFi also introduces the risk that apps waiting for WiFi must share the limited 3G bandwidth, should WiFi ultimately not be available. Some apps, such as videos, will require a large amount of bandwidth; their quality can suffer significantly if they must share bandwidth with other apps, e.g., cloud backups.\footnote{While our systems apply to any form of cellular data, e.g., 3G or LTE networks, we frame our discussion in terms of 3G data. LTE speeds can exceed WiFi, which makes the users' tradeoffs more complicated and AMUSE even more useful.}
\end{itemize}
% The exact structure of this tradeoff varies for different types of traffic: for , the user will not wait for WiFi. However, other applications, such as cloud backup, are more delay-tolerant and may wait.  To fully exploit the benefits of WiFi offloading, a user must balance these competing cost, throughput quality, and delay tradeoffs for different applications.

Most users will not manually balance these competing factors in making offloading decisions.  Thus, we propose a user-side, automated WiFi offloading system called AMUSE (Adaptive bandwidth Management through USer EMpowerment) that intelligently navigates these tradeoffs for the user.  AMUSE utilizes WiFi access and application usage predictions to decide how long application sessions should wait for WiFi and, in case WiFi is not available, to optimally allocate 3G bandwidth among different apps. Building such a system poses both algorithmic and implementation challenges--not only must the user's tradeoff between cost, throughput quality, and delay be quantified and balanced, but %we require a way to automatically enforce the 3G throughput rates for those application sessions that wait for WiFi access.
we require a way to automatically enforce AMUSE's waiting for WiFi and sharing of 3G bandwidth. In solving these problems, we make the following contributions:
\begin{enumerate}

\item We develop a system for cost-aware WiFi offloading that exploits a user's delay tolerances for different applications and makes offloading decisions satisfying her throughput-delay tradeoffs and 3G budget constraints.

\item To enforce AMUSE's bandwidth allocation decisions for each application, we implement a practical receiver-side rate control algorithm for TCP.\footnote{We assume that download traffic makes up most of users' usage, so that the receiver is synonymous with the user.}  The algorithm is fully contained on and driven by end-user devices, making it suitable for practical deployment as it requires no modification of the TCP server side.

\item In order to analyze current mobile offloading patterns and the potential to offload more traffic from different apps, we conduct a measurement study using application usage data collected from 20 Android smartphone users for one week.\footnote{Throughout this work, ``app usage data'' refers to the volume of data used by each application, not the time duration of application usage.} The results reveal several facts that show offloading practice and possibility of smartphone users. 

\item We surveyed 100 participants in the U.S. to evaluate users' tradeoff between the cost of 3G usage and their willingness to wait for WiFi access.  We incorporate the resulting cost-throughput-delay tradeoff estimates into our model, and evaluate AMUSE's performance using these results and 3G and WiFi usage data collected from a trial with 37 mobile users.



\end{enumerate}

AMUSE is the first WiFi offloading system to fully account for cost, delay, and throughput in offloading traffic from 3G to WiFi. Other works have considered using WiFi offloading to reduce cost within a basic delay constraint, e.g., by using predictions of WiFi connectivity to improve offloading \cite{breadcrumbs} or allocating more WiFi bandwidth to users who are expected to leave the WiFi coverage area in a short amount of time~\cite{santhapuribytestogo}. Mobility can also enhance prefetching data over WiFi \cite{siris2013performance}. Wiffler~\cite{Augmenting3G} considers a more sophisticated model of different applications' delay tolerances, but does not consider different apps' bandwidth needs or their need to share 3G bandwidth.

To fully incorporate cost, delay, and throughput, we build an end-to-end mobile offloading system. In the next section, we describe AMUSE's components and the challenges of developing this end-user system.

\subsection{Components of AMUSE}

Figure \ref{fig:overview} gives an overview of AMUSE's components and their interactions.  The system architecture comprises four main modules: the User Interface, Bandwidth Optimizer, TCP Rate Controller, and App-Level Session Tracker.  The latter two modules reside in the kernel and are accordingly shaded darker in the control flow diagram (Fig. \ref{fig:control}); these enforce the offloading decisions made by the User Interface and Bandwidth Optimizer, which reside in the user-space.  To illustrate the system's full set of interactions, the Bandwidth Optimizer is split into three components: two prediction modules for app usage and WiFi availability, and an algorithm that computes utility-maximizing offloading decisions.

\subsubsection{User Interface}

As suggested by its name, AMUSE's User Interface interacts directly with the user, displaying the offloading decisions made as well as the user's app-level usage history.  The user may also set her preferences on the user interface, e.g., the maximum budget for 3G usage and delay tolerances for different applications.

\subsubsection{Bandwidth Optimizer}

The Bandwidth Optimizer makes offloading decisions for the user, given the preferences set by the user on the User Interface.  It consists of the three medium-shaded components in Fig. \ref{fig:control}: app usage prediction, WiFi access prediction, and a utility maximization algorithm.

AMUSE uses an adaptive user mobility model to predict WiFi availability at future times (Fig. \ref{fig:control}). The app usage prediction component allows AMUSE to calculate the expected savings from offloading an application session and to allocate 3G bandwidth to all active apps at any given time, giving more bandwidth to the apps with higher bandwidth requirements. % This allocation then facilitates AMUSE's estimation of the session's throughput should WiFi not be available.

The user's offloading decisions at any given time must take into account \emph{future} offloading decisions--for instance, a myopic algorithm may delay all sessions in the morning to 12 noon, if the probability of WiFi access at that time is high.  However, should WiFi not be available then, all of the delayed sessions would have to share the limited 3G bandwidth, or else wait even longer for WiFi.  Thus, at the beginning of each day, AMUSE optimizes over the entire rest of the day, using estimates of WiFi access probabilities and the size of application sessions at different times (e.g., hours).  It then refines this initial solution over the day to reflect the observed usage and WiFi access patterns.

\subsubsection{TCP Rate Controller and Session Tracker}

Since 99.7\% of mobile traffic flows are TCP, we enforce the Bandwidth Optimizer's 3G bandwidth allocations and offloading decisions with a TCP rate controller on end-user devices \cite{rahmati2011mobile}.  To do so, the controller modifies the TCP advertisement window in outgoing acknowledgement (ACK) packets.  Unlike typical bandwidth throttling mechanisms, this rate control is completely specified by the \emph{end user} on a \emph{per-application} basis; thus, for example, file downloads may be delayed to wait for WiFi, while streaming videos may receive a higher 3G bandwidth and not be delayed.  The app-level session tracker measures the actual usage for each application as the rate controller enforces the Bandwidth Optimizer's decisions.  These usage data are then used to update AMUSE's prediction modules, as shown in the control flow diagram (Fig. \ref{fig:control}), and are displayed to the user on the User Interface.

\begin{figure}[t]
\centering
%\vspace{-0.10in}
\subfloat[System implementation architecture.]{\includegraphics[width = 0.4\textwidth]{image/Arch_Blue.pdf}\label{fig:architecture}} \\
\vspace{-0.1in}
\subfloat[Control schematic and main modules.]{\includegraphics[width = 0.4\textwidth]{image/ControlFlow_Blue.pdf}\label{fig:control}} \\\caption{Overview of AMUSE's components.}
\label{fig:overview}
\vspace{-0.12in}
\end{figure}


% Some user-side bandwidth control softwares have been developed, e.g. ~\cite{NetLimiter,SoftPerfectBM,PRTG}, but these solutions use only simple algorithms to make offloading decisions, and require much interaction and decision making on the part of users themselves.

In Section \ref{sec:RelatedWork}, we discuss prior works that propose functions related to components of the AMUSE system.  Section \ref{sec:allocation_algorithm} discusses the Bandwidth Optimizer in more detail, while Section \ref{sec:Implementation} gives an overview of the TCP Rate Controller's algorithm and implementation.
%Section \ref{sec:data_collection} gives an explanation on how we collected smartphone users' usage data in order to conduct analysis and evaluation as detailed in subsequent two sections.
In Section \ref{sec:measurement}, we observe mobile users' wireless network usage pattern from the viewpoint of WiFi offloading, and find how much and which kind of applications are currently offloaded and can be offloaded more.
In Section \ref{sec:evaluation}, we evaluate AMUSE's effectiveness in improving users' experience, utilizing 3G and WiFi data gathered from 37 mobile users.  When compared with two representative offloading algorithms (on-the-spot and delayed~\cite{OffloadingCoNext2010}), we show that AMUSE increases user utility by intelligently managing the cost-throughput-delay tradeoff for heavy and light users.  Finally, we conclude the paper in Section \ref{sec:Conclusion}.
%Typically these services provide the locations of their WiFi access points and users  need to log in the system to use the Internet []. Also, as more users have broadband access at home, the opportunity to offload the traffic to WiFI increases significantly. 

%[Need to emphasize that the receiver-side application control is better than 0/1 (enable/disable a certain connection to the time when the WiFi is available... ] 

%We propose a novel user-side bandwidth management system called AMUSE. AMUSE empowers users to utilize the data plan based on predicting WiFi availability.
%Unlike previous offloading approaches, we take into account the monetary cost in the decision of offloading. In addition, we formulate the problem of offloading decision into an optimization problem, and maximizing the users' utility becomes the objective of the problem rather than just maximizing the WiFi utilization, or considering limited number of factors such as application delay tolerance, available bandwidth. Moreover, we introduce an additional knob, the data rate for each application, in the offloading decision. This is based on the observation that several application types such as video can obtain the utility gain to a certain degree even if they consume low bandwidth. So rather than just transmiting or delaying, we can have the different data rates for each application.


%\subsection{Managing Mobile Data Explosion}

%Due to the growing popularity of mobile devices like smartphones and tablets, 
%the mobile data traffic is doubling every year. Users now expect to use the Internet 
%at any time and on any devices, and this enables cloud and streaming services 
%to become more popular. According to \cite{CiscoVNI}, the mobile devices 
%including WiFi are expected to account for 54\% of IP traffic in 2015. 

%To match price to the costs involved in upgrading the wireless infrastructure to cope with this demand, more Internet Service Providers (ISPs) are adopting usage-based data plans 
%instead of their previous unlimited data plans. 
%For example, Verizon Wireless joined the competitors AT\&T and T-Mobile on July, 2011 
%in eliminating unlimited data plans\cite{Verizon}.  
%However, their typical plans, \$10/GB, are more likely hurt price sensitive consumers 
%since downloading a 1GB high-resolution movie could be more costly than going to a theater. 
%Moreover, ISPs began slowing down the data speed even for the unlimited data plan users.
%AT\&T now throttles any 3G unlimited data plan users whose usage is within the top 5 percent of data users in their network []. 

%ISPs also explore a way to offload their costly mobile traffic to low-cost WiFi or Femtocell networks. 
%A number of wireless ISPs have deployed their WiFi and Femtocell networks to offload their mobile traffic and began providing smooth handover and high quality Internet services to users[][]. 

%\subsection{Empowering Users}

%However, adopting new data plans and ISP-centric offloading approaches do not always match the interest of mobile users. In fact users are interested in using their monthly data plans as efficiently as possible while ISPs are interested in generating more revenues without incurring more traffic on their networks.  



%While rate control can be done anywhere between two end-hosts, end-user solutions have clear advantages. First, a user knows best her bandwidth demands and priorities across different applications and it makes sense to reduce the rate of non-critical application if the current bill is getting closer to the data plan quota. Second, it sits under net neutrality radar since a user, not an ISP, decides how to assign the bandwidth across different applications. Third, it has direct incentives to users since it helps reduce Internet expenses. 



%In this paper, we are focusing on the user-side bandwidth management solution which has rarely attracted attention. 

% This paper is organized as follows. Section \ref{sec:systmArchitecture} gives an overview of the system architecture of AMUSE. Section \ref{sec:allocation_algorithm} presents an algorithm for computing a user's bandwidth allocation across different applications. Section \ref{sec:BWControl} shows how to set the rate of each application from user side. The implementation details are presented in Section \ref{sec:Implementation}. Section \ref{sec:evaluation} shows the evaluation results with 3G and WiFi usage data from 18 iPhone users in the campus. Section \ref{sec:RelatedWork} discusses related work in this area. Finally \ref{sec:Conclusion} concludes the paper.



%%- data plan change due to data explosion
%%- importance of efficient data usage increased for the users' sake
%%- to lower the cost, we can offload
%%- offload has been researched thoroughly but only on ISP-side. no approach for a user cost reduction
%%- in addtion it's hard to manage, offload by user decision because of lots of applications, application characteristics different
%%- we need a system that help users reduce cost using offload.
%%- offloading decision should consider users' cost, user experience both. unlike previous approaches
%%  In addition we should have more knob than just on/off decision, data rate for each application.
%%  (bandwidth allication.)
%%  some applications such as video can some utility even in low bandwidth consumption
%% (utility is not completely proportional to the assigned bandwidth).
%% for this we use user-side bandwidth control.
%% - benefits...
%%- So we propose a solution that accomodates all of these features.
%Due to the prevalence of mobile devices like smartphones, tablet
%PCs, the Internet traffic over wireless networks such as 3G, LTE,
%WiFi is increasing exponentially. According to \cite{CiscoVNI}, in
%2015, Wi-Fi and mobile devices are expected to account for 54 percent
%of IP traffic. At the same time, as diverse network services such
%as video streaming, cloud service evolve, the bandwidth demand for
%a service is also growing and this again leads to drastic increase
%in traffic over wireless networks. To cope with these data explosion,
%more and more ISPs are adopting usage-based data plans instead of
%their previous unlimited data plans. For example, Verizon Wireless
%joined competitors AT\&T and T-Mobile on July, 2011 in eliminating
%unlimited data plans\cite{Verizon}. However, usage-based data plans
%do not reflect the increased traffic demands of users and enhanced
%high-bandwidth services. Under a usage-based data plan which provides
%1G per \$10, the cost of downloading a high-resolution movie can be
%higher than that of going to the theater. As a result of the increase in mobile Internet traffic and the change in data
%plans, efficient bandwidth utilization of user devices is becoming
%critical. 
%
%As an effort to reduce cellular traffic of high-cost and utilize the limited cellular spectrum efficiently, offloading 3G traffic to low-cost WiFi networks has gained attention from network researchers and ISPs in recent years. A number of telecommunication companies have deployed WiFi networks to reduce the traffic burden in their cellular network and provide high quality Internet service to users[][]. However, these ISP-centric offloading approaches do not always match with the interest of mobile users. Users are interested in reducing their Internet cost and being provided with high bandwidth, while ISPs are interested in reducing the overall traffic on their overloaded network, and providing stable services. In this paper, we are focusing on the users' view which has been rarely attracting attention.
%
%For a mobile users, it is not an easy task to manage the Internet cost efficiently by taking advantage of WiFi offloading. This is because users cannot trace the traffic and assign the bandwidth for a number of applications run in wireless devices. In addition, the characteristics of applications in terms of traffic volumn, delay tolerance, session time are diverse. Even though there are bandwidth control softwares~\cite{NetLimiter}~\cite{SoftPerfectBM}~\cite{PRTG}, these software leave most of the options for managing the bandwidth in the hands of users.
%
%For effcient bandwidth utiliztion, in addition to assigning the bandwidths to applications appropriately utilizing WiFi offloading, we have to solve the problem of how to enforce the assigned bandwidths to applications.
%The bandwidth consumed by user devices can be controlled in four
%locations : user-side vs. edge gateway-side vs. ISP-side vs. content provider-side. Among
%them, user-side control has the advantage that it can use more information
%from user-side, so more powerful control is possible. For example, when a user has multiple network interface cards, this interface information can be utilized to improve the performance by utilizing each interface considering its characteristics such as bandwidth, RTT and the requirements of applications.
%Another advantage of user-side bandwidth control is higher
%controllability of users. For instance, users can decide the priorities
%of applications in bandwidth consumption. 
%%This is important since
%%users may have significantly different priorities on different applications.
%%If the same bandwidth assignment rules are applied for all users,
%%user experience will be significantly degraded. 
%In addition, while
%other approaches can draw users' resistance, as we can see in network
%neutrality controversy, user-side control has a clear and direct incentive
%to users that it can help them reduce their Internet expenses. It
%also match with the philosophy of the Internet that the functions
%should be in edges as much as possible making the intermediaries simple.
%Even if a host adopting user-side bandwidth control fails, users only
%within the same local network will be directly affected. 
%
%We propose a novel user-side bandwidth management system, named NONAME. Its goal is to utilize the limited bandwidth efficiently under fixed budgets while intelligently utilizing the WiFi offloading.
%Unlike previous offloading approaches, we take into account the monetary cost in the decision of offloading. In addition, we formulate the problem of offloading decision into an optimization problem, and maximizing the users' utility becomes the objective of the problem rather than just maximizing the WiFi utilization, or considering limited number of factors such as application delay tolerance, available bandwidth. Moreover, we introduce an additional knob, the data rate for each application, in the offloading decision. This is based on the observation that several application types such as video can obtain the utility gain to a certain degree even if they consume low bandwidth. So rather than just transmiting or delaying, we can have the different data rates for each application.
%As a user-side bandwidth control method, we introduce the TCP ACK pacing-based technique which was proposed as a gateway solution. 
%The advantage of this approach is that we can control the bandwidth by changing only TCP receiver side and the TCP sender considers that just the network status between the sender and receiver has changed when we apply bandwidth control.
%Due to its simple mechanism, this approach can be applied to various systems such as Linux, Windows, etc.
%
%%Users with a usage-based data plan have to use their bandwidth
%%efficiently in order not to receive an excessively high bill. The
%%tamed users by the high capacity of LTE and high-quality video services,
%%have to be cautious in using high-bandwidth services.
%
%Our contributions in this paper can be summarized as follows. 1) We
%suggest a novel offloading decision algorithm, which decides bandwidth or delay of applications in an optimization framework whose objective is to maximize the user's utility. The utility function includes monetary cost, delayed time, available bandwidth, service time. We also suggest WiFi connectivity prediction and future usage prediction algorithms which our offloading decision algorithm is based on. To the best of our knowledge, our algorithm is the first work in offloading decision that the monetary cost is considered and the users' utility is the objective.
%2) We suggest a user-side bandwidth control mechanism which can be implemented by changing only TCP receiver side and does not impede the internal operations of TCP protocols.
%3) Finally we show the feasibility and efficiency of proposed mechanisms in various scenarios by mathmatical analysis, simulation, and prototype experiements.
%
%This paper is organized as follows. Section \ref{sec:RelatedWork}
%introduces prior works related with bandwidth control, TCP pacing, and WiFi offloading. Section \ref{sec:systmArchitecture} explains the overall system architecture of our proposed system, NONAME.
%A new bandwidth assignment algorithm considering fixed budgets and WiFi offloading is presented in the framework of optimization problem in Section \ref{sec:User Utility Maximization}, and its online algorithm is explained in Section \ref{sec:online}.
%Section \ref{sec:BWControl} proposes a 
%user-side bandwidth control algorithm utilizing TCP ACK pacing. 
%The implementation details of our proposed algorithms are presented
%in Section \ref{sec:Implementation}. Section \ref{sec:evaluation}
%shows the evaluation results of our algorithms. After discussing several
%issues related with bandwidth control and bandwidth assignment in
%Section \ref{sec:Discussion}, we will conclude the paper in Section
%\ref{sec:Conclusion}.

\begin{comment}
\begin{enumerate}
\item Explosive demand, video, CISCO VNI, the cost of downloading a high-resolution
movie is higher than going to a theater 
\item Need for efficient bandwidth utilization

\begin{itemize}
\item User-side

\begin{itemize}
\item Limited Budget 
\item Time dependent pricing 
\item LTE (large bandwidth demand, high price) 
\end{itemize}
\item ISP-side

\begin{itemize}
\item Network congestion control 
\end{itemize}
\end{itemize}
\item User-side vs. ISP-side vs. Content provider-side control

\begin{itemize}
\item More information, more powerful (e.g. WiFi offloading) 
\item User controllability 
\end{itemize}
\item Three approaches for bandwidth control in user side

\begin{enumerate}
\item Proxy based (Split TCP) 
\item ACK pacing 
\item Receive buffer size 
\end{enumerate}
\item Internet philosophy:controllability in edges 
\item Contributions

\begin{itemize}
\item Automatic bandwidth control without user involvement 
\item Propose an efficient bandwidth control method using ACK pacing

\begin{itemize}
\item Can be applied to various systems such as linux, Windows, 
\end{itemize}
\item Propose a medium estimation mechanism 
\item Based on these, present a budget planning system that the total expense
is as close as possible to the budget while degradation of user experience
is minimized 
\item Show the accuracy and efficiency of proposed mechanisms\end{itemize}
\end{enumerate}
\end{comment}

% \end{document}
Measurement.tex
\section{Measurement} \label{sec:measurement}
We conduct a measurement study in order to analyze mobile users' network usage pattern from the viewpoint of WiFi offloading.
Specifically, in Section \ref{sec:application_types} we show that the application types considered in Table \ref{tab:param} comprise a large portion of users' cellular traffic. In  Section \ref{sec:offloading_practice}, we examine the degree to which these applications are already offloaded and their potential for more offloading.
% We also examine the potential for offloading each application to WiFi to different times of the day by investigating the temporal usage patterns of mobile users in Section \ref{sec:temporal_usage_pattern}.
%As explained in Section \ref{sec:data_collection}, we utilize 7 days' application usage traces of 20 Android smartphone users in Alaska for this study.

\subsection{Data Collection} \label{sec:data_collection}
To collect empirical traffic data for the measurement study in this section,
% Section \ref{sec:measurement} and the evaluation of AMUSE compared to other offloading algorithms in Section \ref{sec:evaluation}, 
we recruited smartphone users to participate in our trial. We recorded the data by implementing a usage monitoring app and installing it on users' phones.  Figure \ref{fig:screen} shows the screenshots of the usage monitoring app, which informed users of their overall usage over different timescales and usage at different geographical locations. % Aside from the ability to view The data is fully anonymized; for instance, longitude and latitude coordinates of a user are hashed before being sent to the servers.
%In our server we record the hashed MAC address, amount of cellular and WiFi usage at different times of the day, WiFi bssids, hashed GPS location, and Android OS version number.
% At times when the user did not have the application open, it ran as a background process in order to continue recording data.
%To minimize its impact on a user's recorded 3G or WiFi usage, the recorded data was sent to our server from participants' phones only once a day.
% by recruiting the experiment participants through large community sites, and sending e-mails to a groups of people with different occupations, gender, ages. By this diversity in users, we tried to reduce the effect of user groups' characteristics to the data usage, and WiFi/3G connectivity.

%We collected two types of data sets. %: one data set of application usage for the measurement study, and the other data set of WiFi and 3G usage and mobility for the evaluation of offloading algorithms. 
%For first data set, 
We collected application usage data from 20 Android smartphone users in Alaska for 7 days, including application package names and categories and upload and download usage amounts for each application in bytes. 
To compare AMUSE to other offloading algorithms in Section \ref{sec:evaluation}, we also collected another data set from an additional 12 Android users and 25 iPhone users in the U.S. This second dataset includes participants' 3G and WiFi usage, WiFi availability, and user locations at a ten minute granularity.\footnote{We do not collect iPhone application usage data due to iOS implementation restrictions.}

\begin{figure}
\centering
\includegraphics[height = 0.22\textwidth]{image/princeton_main_screen1.png}
\includegraphics[height = 0.22\textwidth]{image/datawiz_map.png}
\caption{Screenshots of the usage monitoring app.}
\label{fig:screen}
\end{figure}

\subsection{Application types} 
\label{sec:application_types}


%\begin{figure}[t]
%\vspace{-0.2in}
%\centering
%\includegraphics[scale=0.5]{evaluation_android/application_usage_wifi.eps}
%\vspace{-0.1in}
%\caption{Traffic usage of top 15 applications in WiFi network (The application indexes are represented in Table \ref{tab:top_wifi}).}
%\label{fig:application_usage_wifi}
%\end{figure}
%
%\begin{figure}[t]
%\vspace{-0.2in}
%\centering
%\includegraphics[scale=0.5]{evaluation_android/application_usage_cellular.eps}
%\vspace{-0.1in}
%\caption{Traffic usage of top 15 applications in cellular network (The application indexes are represented in Table \ref{tab:top_cellular}).}
%\label{fig:application_usage_cellular}
%\end{figure}

In Section \ref{sec:allocation_algorithm}, we classify user's traffic into 5 application types (i.e. Email, Browsing, Video, Social networking, Downloads). In this subsection, we verify that these application types comprise most of users' traffic by volume, indicating that AMUSE covers most cellular traffic. In Tables \ref{tab:top_wifi} and \ref{tab:top_cellular}, we list the top 15 applications for WiFi and cellular networks, respectively. 
%Figure \ref{fig:application_usage_wifi} and \ref{fig:application_usage_cellular} visually compare the usage amounts of top 15 applications for WiFi and cellular networks. 
To identify the application types, we manually searched for the package names in the Android application market and used the application descriptions there. Packages not found in the Android application market were classified using the name itself (e.g. com.android.email is classified as ``Email''). Package names that cannot be identified using these methods are designated as ``Unclassified.'' In the case of cellular network, the top five applications correspond to the application types in Table \ref{tab:param}, accounting for 54\% of the total cellular traffic. From these observations, we can conclude that our offloading mechanism can handle a large portion of mobile users' cellular traffic, demonstrating the possibility of significantly reducing the data cost.

\subsection{Offloading practice} 
\label{sec:offloading_practice}

\begin{figure}[t]
\vspace{-0.2in}
\centering
\includegraphics[scale=0.45]{./evaluation_android/category_traffic_portion2-eps-converted-to.pdf}
\vspace{-0.1in}
\caption{Traffic amounts for each category and network type.}
\label{fig:category_traffic_portion}
\end{figure}

\begin{figure}[t]
\vspace{-0.2in}
\centering
\includegraphics[scale=0.45]{./evaluation_android/wifi_cellular_ratio-eps-converted-to.pdf}
\vspace{-0.1in}
\caption{The ratio of traffic WiFi to cellular network traffic for each application type.}
\label{fig:wifi_cellular_ratio}
\end{figure}
From users' usage traces, we find that users are already offloading a large portion of their traffic, but a large amount of video and social networking cellular traffic still runs over WiFi and can be delayed for offloading.  
In Figure \ref{fig:category_traffic_portion}, we illustrate the amount of upload and download traffic for each application type in cellular and WiFi networks. As expected, the amount of WiFi traffic is much larger than that of cellular, and the amount of download traffic is larger than the upload traffic. 

As in \cite{CiscoVNI2014}, video traffic accounts for the largest portion of traffic for WiFi uploads/downloads and cellular downloads (74, 70, 49\% respectively). For these types of traffic, the order of the application types according to the traffic amount is Video, Social networking, Email, Browsing, and Downloads. In the case of cellular upload, the traffic amount is in the order of Social networking-Browsing-Email-Video-Downloads. We find that 84\% of the total upload and 66\% of the total download traffic uses WiFi.

To investigate the fraction of each application's traffic that is offloaded to WiFi networks, we calculate the ratio of WiFi to cellular upload and download traffic for all the application types, as shown in Figure \ref{fig:wifi_cellular_ratio}. If this ratio is large, it means that the users already offload their traffic to WiFi for that application type, either because that application type is delay-tolerant or because it requires WiFi's high bandwidth (e.g., video applications). 

From Figure \ref{fig:wifi_cellular_ratio}, we see that different application types show different ratios. In particular, the Video and Download types show large values for both upload and download traffic. This coincides with the small values of $\mu$ in Table \ref{tab:param} for these application types. Video requires high bandwidth and has high cost generally, incentivizing users to wait for WiFi in order to use high bandwidth. However, by comparing the ratios for Video and Downloads, we observe that users wait more for Video than for Downloads. While a significant fraction of video and downloads are offloaded, the high delay tolerance of Download apps indicates that more offloading is possible.
% The order of the size of $\mu$  values for other application types does not exactly match the order of these ratio values, since the users' intention to offload represented by $\mu$ and the user's current offloading practice represented by WiFi/cellular traffic ratio can be different. %Since users offload a lot of video and social network traffic, their utility from waiting for these application types likely does not significantly degrade with the time to wait. This is consistent with the small value of mu, which measures the decrease in utility from waiting, from our survey results.

%\subsection{Temporal usage pattern} 
%\label{sec:temporal_usage_pattern}
%
%\begin{figure}[t]
%\vspace{-0.1in}
%\centering
%\includegraphics[scale=0.65]{evaluation_android/usage_cellWifi.eps}
%\vspace{-0.1in}
%\caption{Data usage pattern of one day in cellular and WiFi networks.}
%\label{fig:traffic_pattern}
%\end{figure}

%\begin{figure}[t]
%\vspace{-0.1in}
%\centering
%\includegraphics[scale=0.65]{evaluation_android/usage_wifi.eps}
%\vspace{-0.1in}
%\caption{Data usage pattern of one day in WiFi network.}
%\label{fig:wifi_traffic_pattern}
%\end{figure}
%
%\begin{figure}[t]
%\vspace{-0.1in}
%\centering
%\includegraphics[scale=0.7]{evaluation_android/usage_cellular.eps}
%\vspace{-0.1in}
%\caption{Data usage pattern of one day in cellular network.}
%\label{fig:cellular_traffic_pattern}
%\end{figure}

\begin{figure}[t]
\vspace{-0.2in}
\centering
\includegraphics[scale=0.45]{./evaluation_android/application_usage_cdf-eps-converted-to.pdf}
\vspace{-0.1in}
\caption{CDF of the number of periods for which each user uses Email and Social networking applications.}
\label{fig:application_usage_cdf}
\end{figure}

% Figure \ref{fig:traffic_pattern} shows the traffic usage pattern during a specific day for each user. Y-axis represents user indexes, and X-axis represents the time of the day. Each dot represents that the user used data within 10 minutes' interval. Different shapes and colors of the dots represent different network types, cellular or WiFi. %, while the size of the dots represents the traffic amount used during each 10 minutes' interval in log scale. 
% Note that users 1--10 used both WiFi and cellular networks, whereas users 11--20 used only the cellular network. We can observe that many users exhibit regular usage patterns even at late night or dawn. We presume these users are using applications that check the updated contents periodically, e.g. e-mail push notification. Furthermore, when a user uses both WiFi and cellular networks, she tends to use the networks exclusively. This phenomenon coincides with the fact that typical smartphone OSes by default give higher priority to WiFi than cellular network, and use WiFi only if WiFi is available. User 5 sends data over the cellular network only in the afternoon time when the WiFi is not used at all. However, user 5 does not delay the traffic until when the WiFi is available even though the WiFi becomes available in a moment. We claim that if we can predict the WiFi availability with high accuracy and provide the users with such information, users like user 5 can delay their traffic and hence reduce data cost. 

We also see that the Email and Social networking applications have some offloading potential. % are frequently used, and other applications exhibit a sporadic traffic pattern. %, when we exclude the traffic that is conjectured to be for regular contents updates. 
Figure \ref{fig:application_usage_cdf} shows CDFs for the number of periods in which a user uses E-mail and Social networking applications. We observe that about 40\% of users use WiFi data for Email and Social networking applications 30\% of the time. Over cellular, the data usage frequency decreases, but 20\% of users spend significant amounts of time on email and social networking. This high usage frequency indicates that some Email and Social Networking traffic can be offloaded if a user does not need to wait very long for WiFi access. % We presume that this application-specific traffic pattern can be utilized in predicting the traffic demands to enhance its accuracy though we considered only users' usage history and traffic deferrals. We have found that the above observations are also applied in other days' traffic. %The final observation is that many users tend to use several applications at the same time once they use the network (e.g. user 7 in cellular network). 
%day time activity. Can we delay the always-on traffic




%The columns in both files represent the app name, app category, device phone number, UNIX timestamp, upload, and download usage in bytes (negative values should be treated as 0). The full list of apps is given in appCategory.txt.

%There should be data from 24 devices collected; these were Android smartphone users in Alaska. This data was part of our time-dependent pricing trial with a small Alaskan ISP; we installed apps on user smartphones that monitored the amount of data used at different times of the day and by application. I can send you screenshots of the app if you think they'd improve the paper write-up. The 907 area code I mentioned in (1) is the Alaska area code; all of these users should have a reliable application that reports the correct usage amounts.




relatedWork_revised.tex
\section{Related Work}

\label{sec:RelatedWork}

Recent studies of 3G and WiFi usage traces, e.g. \cite{OffloadingCoNext2010} have showed that offloading 3G traffic to WiFi can significantly benefit mobile ISPs. Other systems have demonstrated offloading's benefits for user experience \cite{breadcrumbs,siris2013performance,Augmenting3G}; other works demonstrate that WiFi offloading can benefit both ISPs and users \cite{6567156} and even generate more revenue for ISPs \cite{joe2013offering}.

Some works have focused on incentivizing users to offload traffic to WiFi. In \cite{6089074}, the authors develop a utility and cost-based formulation to decide the 3G network load that maximizes the user's benefit and apply the decided loads using a modified SCTP implementation in Linux that stripes traffic across multiple interfaces.
Win-Coupon~\cite{WinCoupon} takes a slightly different perspective and proposes a reverse-auction scheme to incentivize users to offload their traffic so as to decrease the overall network. 
 Other works, including~\cite{Ristanovic}, consider the energy consumption when making an offloading decision. We do not consider energy in this work, but can easily incorporate the battery consumption into our proposed optimization algorithm.

Several research works have analyzed the traffic of smart devices in order to understand their user behavior \cite{falaki2010diversity}, \cite{xu2011identifying}, \cite{falaki2010first},  \cite{gember2011comparative}, \cite{maier2010first}. 
In particular, \cite{falaki2010diversity} examines users' traffic diversity, relationship to application types, interactivity, and diurnal patterns, while \cite{xu2011identifying} investigates the usage patterns of smartphone apps via network-side measurements. Our work is different from these in that we specifically focus on the potential for WiFi offloading of different applications and incorporate findings on their delay tolerances.
%\subsection{bandwidth control in various sides}

%If a user wishes to limit her traffic rate, she may use the bandwidth control software (e.g., ~\cite{NetLimiter}~\cite{SoftPerfectBM}~\cite{PRTG}).
Unlike most offloading works, AMUSE also controls the 3G bandwidth for different applications. AMUSE is unique in using of receiver-side TCP advertisement windows to control application-specific 3G bandwidth from the user side.  While several commercial applications (e.g., \cite{NetLimiter,SoftPerfectBM,PRTG}) provide user-side application rate control, most require users to manually specify the desired rates.  AMUSE provides automated bandwidth rates and, by conforming to TCP interactions, avoids the TCP timeouts common to existing user-side rate control applications.  
%
%These solutions have bandwidth control mechanisms that require fine-grained control from users such as per-application type bandwidth specification by users. Meanwhile, our bandwidth control can adjust the throughput automatically depending the accumulated usage without user involvement.
%\cite{balakrishnan1999integrated} proposed a similar end-to-end integrated congestion management to ours. They suggested the Congestion Manager that performs integrated congestion management across unicast flows in an application- and transport-independent manner.
%Whereas they proposed a novel hybrid window-rate congestion control scheme and put several protocol modifications, our scheme works as an add-on on existing congestion control schemes with no change in previous protocols. Their scheme focuses on an old issue, the long-term stability of the Internet facing with multiple independent concurrent flows by Web applications, transport protocols and applications that do not adapt to congestion. On the other hand, our scheme considers recent data-explosive network environment, and focuses on the problem of reducing the users' Internet cost and maximizing the user experience.
%
%However, these solutions cannot deal with users' monetary requirements, not to mention WiFi offloading.
%
% TCP pacing
%We used the ACK pacing scheme for our bandwidth control mechanism. A large number of prior works have investigated TCP data or ACK %pacing with objects of reducing the burstiness of the traffic~\cite{Zhang91observationson}, improving the performance during %handover~\cite{1424736}, enforcing bandwidth control~\cite{TCR}\cite{10.1109/TC.2004.1261834}. ~\cite{UnderstandingTCPPacing} %and ~\cite{TCPPacingRevisited} examines the benefits and drawbacks of TCP pacing. However, no other works have investigated the %feasibility of ACK pacing as a bandwidth control mechanism in user-side. \cite{TCR} and \cite{10.1109/TC.2004.1261834} use the similar %mechanisms to ours including ACK pacing or receiver advertisment window adjustment, but since our alogrithms are run in user devices, %there is no limitation of encription and authentication such as IPsec, and we can apply per-application bandwidth by using input from users %or using values decided by our offloading decision algorithm.
%
%\subsection{Utilization of TCP receive window}
Although the TCP advertisement window is normally used by the TCP receiver to inform the TCP sender of its available buffer space, other trials \cite{1177250} have used the advertisement window as a means to control the rate of applications. However, this approach has been mainly applied to the enforcement of different application priorities, rather than direct control of the application rates.
Other solutions, such as~\cite{10.1109/TC.2004.1261834}, focus on the edge gateway, rather than the end user.

%\subsection{WiFi offloading}
%As a result of recent explosive increase in cellular traffic, offloading traffic to WiFi networks has been investigated in order to reduce the traffic that flows on cellular networks in a number of prior works
%\cite{Augmenting3G}\cite{OffloadingCoNext2010}\cite{breadcrumbs}\cite{WinCoupon}\cite{santhapuribytestogo}\cite{6089074}.
% bandwidth allocation



%1) attempt to shape inbound TCP traffic by dropping tcp packets when
%they overflow the HTB queue which will only pass them on at a certain
%rate (RATEDN) which is slightly lower than the actual capability of
%the inbound device.
% http://www.tldp.org/HOWTO/ADSL-Bandwidth-Management-HOWTO/implementation.html


%{[}ControllingWANBandwidthAndApplicationTraffic{]} implement TCP pacing
%by pacing the delivery of acknowledgements to senders. similar to
%us, but no presentation about fine bandwidth control


0_main_file.bbl
% Generated by IEEEtran.bst, version: 1.13 (2008/09/30)
\begin{thebibliography}{10}
\providecommand{\url}[1]{#1}
\csname url@samestyle\endcsname
\providecommand{\newblock}{\relax}
\providecommand{\bibinfo}[2]{#2}
\providecommand{\BIBentrySTDinterwordspacing}{\spaceskip=0pt\relax}
\providecommand{\BIBentryALTinterwordstretchfactor}{4}
\providecommand{\BIBentryALTinterwordspacing}{\spaceskip=\fontdimen2\font plus
\BIBentryALTinterwordstretchfactor\fontdimen3\font minus
  \fontdimen4\font\relax}
\providecommand{\BIBforeignlanguage}[2]{{%
\expandafter\ifx\csname l@#1\endcsname\relax
\typeout{** WARNING: IEEEtran.bst: No hyphenation pattern has been}%
\typeout{** loaded for the language `#1'. Using the pattern for}%
\typeout{** the default language instead.}%
\else
\language=\csname l@#1\endcsname
\fi
#2}}
\providecommand{\BIBdecl}{\relax}
\BIBdecl

\bibitem{CiscoVNI2014}
``Cisco visual networking index: Global mobile data traffic forecast update,
  2013 - 2018,'' Feb 2014,
  \url{http://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/white\_paper\_c11-520862.pdf}.

\bibitem{sen2012incentivizing}
S.~Sen, C.~Joe-Wong, S.~Ha, and M.~Chiang, ``Incentivizing time-shifting of
  data: {A} survey of time-dependent pricing for {I}nternet access,''
  \emph{IEEE Communications Magazine}, vol.~50, no.~11, pp. 91--99, 2012.

\bibitem{nycwifi}
T.~Ricker, ``{AT\&T making tourists even more annoying with free Times Square
  WiFi},'' Engadget, May 2010,
  \url{http://www.engadget.com/2010/05/25/atandt-making-times-square-tourists-even-more-annoying-with-free-w/}.

\bibitem{chandrasekhar2008femtocell}
V.~Chandrasekhar, J.~Andrews, and A.~Gatherer, ``{Femtocell networks: A
  survey},'' \emph{IEEE Communications Magazine}, vol.~46, no.~9, pp. 59--67,
  2008.

\bibitem{sen2013survey}
S.~Sen, C.~Joe-Wong, S.~Ha, and M.~Chiang, ``A survey of smart data pricing:
  {P}ast proposals, current plans, and future trends,'' \emph{ACM Computing
  Surveys}, vol.~46, no.~2, p.~15, 2013.

\bibitem{breadcrumbs}
A.~J. Nicholson and B.~D. Noble, ``{BreadCrumbs: Forecasting mobile
  connectivity},'' in \emph{Proceedings of ACM MobiCom}.\hskip 1em plus 0.5em
  minus 0.4em\relax ACM, 2008.

\bibitem{santhapuribytestogo}
N.~Santhapuri, J.~Manweiler, R.~Choudhury, and S.~Nelakuditi, ``{BytesToGo:
  Offloading 3G via WiFi prioritization},'' Duke University, Tech. Rep., 2011,
  http://synrg.ee.duke.edu/papers/bytes.pdf.

\bibitem{siris2013performance}
V.~A. Siris and M.~Anagnostopoulou, ``Performance and energy efficiency of
  mobile data offloading with mobility prediction and prefetching,'' in
  \emph{Proc. of WoWMoM}.\hskip 1em plus 0.5em minus 0.4em\relax IEEE, 2013,
  pp. 1--6.

\bibitem{Augmenting3G}
A.~Balasubramanian, R.~Mahajan, and A.~Venkataramani, ``{Augmenting mobile 3G
  using WiFi},'' in \emph{Proceedings of ACM Mobisys}.\hskip 1em plus 0.5em
  minus 0.4em\relax ACM, 2010, pp. 209--222.

\bibitem{rahmati2011mobile}
A.~Rahmati, C.~Shepard, A.~Nicoara, L.~Zhong, and J.~P. Singh, ``Mobile tcp
  usage characteristics and the feasibility of network migration without
  infrastructure support,'' \emph{ACM SIGMOBILE Mobile Computing and
  Communications Review}, vol.~14, no.~4, pp. 10--12, 2011.

\bibitem{OffloadingCoNext2010}
K.~Lee, I.~Rhee, J.~Lee, S.~Chong, and Y.~Yi, ``{Mobile data offloading: How
  much can WiFi deliver?}'' in \emph{Proceedings of ACM CoNEXT}.\hskip 1em plus
  0.5em minus 0.4em\relax ACM, 2010.

\bibitem{6567156}
J.~Lee, Y.~Yi, S.~Chong, and Y.~Jin, ``Economics of wifi offloading: Trading
  delay for cellular capacity,'' in \emph{INFOCOM, 2013 Proceedings IEEE},
  2013, pp. 3309--3314.

\bibitem{joe2013offering}
C.~Joe-Wong, S.~Sen, and S.~Ha, ``Offering supplementary wireless technologies:
  {A}doption behavior and offloading benefits,'' in \emph{Proc. of IEEE INFOCOM
  2013}.\hskip 1em plus 0.5em minus 0.4em\relax IEEE, 2013, pp. 1061--1069.

\bibitem{6089074}
X.~Hou, P.~Deshpande, and S.~Das, ``Moving bits from 3g to metro-scale wifi for
  vehicular network access: An integrated transport layer solution,'' in
  \emph{Network Protocols (ICNP), 2011 19th IEEE International Conference on},
  oct. 2011, pp. 353 --362.

\bibitem{WinCoupon}
X.~Zhuo, W.~Gao, G.~Cao, and Y.~Dai, ``{Win-Coupon: An incentive framework for
  3G traffic offloading},'' in \emph{Proceedings of IEEE ICNP}, Oct. 2011, pp.
  206 --215.

\bibitem{Ristanovic}
\BIBentryALTinterwordspacing
N.~Ristanovic, J.-Y. Le~Boudec, A.~Chaintreau, and V.~Erramilli, ``Energy
  efficient offloading of 3g networks,'' in \emph{Proceedings of the 2011 IEEE
  Eighth International Conference on Mobile Ad-Hoc and Sensor Systems}, ser.
  MASS '11.\hskip 1em plus 0.5em minus 0.4em\relax Washington, DC, USA: IEEE
  Computer Society, 2011, pp. 202--211. [Online]. Available:
  \url{http://dx.doi.org/10.1109/MASS.2011.27}
\BIBentrySTDinterwordspacing

\bibitem{falaki2010diversity}
H.~Falaki, R.~Mahajan, S.~Kandula, D.~Lymberopoulos, R.~Govindan, and
  D.~Estrin, ``Diversity in smartphone usage,'' in \emph{Proceedings of the 8th
  international conference on Mobile systems, applications, and
  services}.\hskip 1em plus 0.5em minus 0.4em\relax ACM, 2010, pp. 179--194.

\bibitem{xu2011identifying}
Q.~Xu, J.~Erman, A.~Gerber, Z.~Mao, J.~Pang, and S.~Venkataraman, ``Identifying
  diverse usage behaviors of smartphone apps,'' in \emph{Proceedings of the
  2011 ACM SIGCOMM conference on Internet measurement conference}.\hskip 1em
  plus 0.5em minus 0.4em\relax ACM, 2011, pp. 329--344.

\bibitem{falaki2010first}
H.~Falaki, D.~Lymberopoulos, R.~Mahajan, S.~Kandula, and D.~Estrin, ``A first
  look at traffic on smartphones,'' in \emph{Proceedings of the 10th ACM
  SIGCOMM conference on Internet measurement}.\hskip 1em plus 0.5em minus
  0.4em\relax ACM, 2010, pp. 281--287.

\bibitem{gember2011comparative}
A.~Gember, A.~Anand, and A.~Akella, ``A comparative study of handheld and
  non-handheld traffic in campus wi-fi networks,'' in \emph{Passive and Active
  Measurement}.\hskip 1em plus 0.5em minus 0.4em\relax Springer, 2011, pp.
  173--183.

\bibitem{maier2010first}
G.~Maier, F.~Schneider, and A.~Feldmann, ``A first look at mobile hand-held
  device traffic,'' in \emph{Passive and Active Measurement}.\hskip 1em plus
  0.5em minus 0.4em\relax Springer, 2010, pp. 161--170.

\bibitem{NetLimiter}
``{NetLimiter},'' \url{http://www.netlimiter.com/}.

\bibitem{SoftPerfectBM}
``{SoftPerfect Bandwidth Manager},'' \url{http://www.softperfect.com/}.

\bibitem{PRTG}
``{PRTG Network Monitor},'' \url{http://www.paessler.com/prtg/}.

\bibitem{1177250}
V.~Raisinghani, A.~Singh, and S.~Iyer, ``{Improving TCP performance over mobile
  wireless environments using cross layer feedback},'' in \emph{Proceedings of
  IEEE Conference on Personal Wireless Communications}, Dec. 2002, pp. 81 --
  85.

\bibitem{10.1109/TC.2004.1261834}
H.-Y. Wei, S.-C. Tsao, and Y.-D. Lin, ``{Assessing and improving TCP rate
  shaping over edge gateways},'' \emph{IEEE Transactions on Computers},
  vol.~53, pp. 259--275, 2004.

\bibitem{song2006evaluating}
L.~Song, D.~Kotz, R.~Jain, and X.~He, ``{Evaluating next-cell predictors with
  extensive Wi-Fi mobility data},'' \emph{IEEE Transactions on Mobile
  Computing}, vol.~5, no.~12, pp. 1633--1649, 2006.

\bibitem{tr}
Y.~Im, C.~Joe-Wong, S.~Ha, S.~Sen, T.~T. Kwon, and M.~Chiang, ``{A survey of
  cost, quality and delay tradeoffs in WiFi offloading},'' Princeton
  University, Tech. Rep., 2012,
  \url{http://www.princeton.edu/$\sim$cjoe/AMUSE\_Survey.pdf}.

\bibitem{moser1997algorithm}
M.~Moser, D.~Jokanovic, and N.~Shiratori, ``An algorithm for the
  multidimensional multiple-choice knapsack problem,'' \emph{IEICE Transactions
  on Fundamentals of Electronics, Communications and Computer Sciences},
  vol.~80, no.~3, pp. 582--589, 1997.

\bibitem{WFPCalloutDriver}
``{WFP Callout Driver},''
  \url{http://msdn.microsoft.com/en-us/library/windows/hardware/gg463267.aspx}.

\bibitem{chon2011mobility}
Y.~Chon, E.~Talipov, H.~Shin, and H.~Cha, ``Mobility prediction-based
  smartphone energy optimization for everyday location monitoring,'' in
  \emph{Proceedings of the 9th ACM conference on embedded networked sensor
  systems}.\hskip 1em plus 0.5em minus 0.4em\relax ACM, 2011, pp. 82--95.

\end{thebibliography}
