%=======================================================================
%  COMPUTER COMMUNICATION NETWORKS, LECTURE NOTES
%=======================================================================
\def\lectureNr{{12}}   %enter number!
\def\lecture{Scheduling and Class Project Presentations} %select and enter title
\def\scribe{Ewa Musial}           %enter your name

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% --------------------------------------------------------------
% DON'T CHANGE ANYTHING UNTIL THE NEXT LINE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\def\solitude{1} %KEEP THIS WAY!!!


%
%\newcommand{\LectureDetails}[3]{
%\chapter{{#2}}
%% \chapter{Lecture {#1}: {#2}}
%\begin{flushright}
%{\large Notes taken by {#3}}
%\end{flushright}}
%
%\newcommand{\LectureDetailS}[6]{
%\chapter{{#2}}
%% \chapter{Lecture {#1}: {#2}}
%\begin{flushright}
%{{\large Notes taken by {#3} ({#4})} \\ {\large and {#5} ({#6})}}
%\end{flushright}}
%

\ifnum\solitude=1
  \documentclass[times, 10pt,letter]{article}
  \usepackage{times}
  \usepackage{setspace}
  \usepackage{alltt}
  \usepackage{fullpage,amsfonts,latexsym,graphics,amssymb}
  \usepackage{amsmath,amsthm,amstext,url}

  \title{Computer Communication Networks\thanks{\
         Lecture Notes for a course given by Stephen F. Bush
         at SUNY.} \\
         Lecture \lectureNr: \lecture}
  \author{Notes taken by \scribe}
  \date{December 2007}
%  \input{preamble}
\else
  %\LectureDetails{\lectureNr}{\lecture}{\scribe}
   \chapter{Lecture \lectureNr: \lecture}
   \begin{flushright}
   {\large Notes taken by \scribe}
   \end{flushright}
\fi


\ifnum\solitude=1

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Theorems & Definitions


\newtheorem{theorem}{Theorem}


\newtheorem{claim}[theorem]{Claim}
\newtheorem{subclaim}{Claim}[theorem]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{observation}[theorem]{Observation}


\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{construction}[theorem]{Construction}
\newtheorem{example}[theorem]{Example}
\newtheorem{algorithm1}[theorem]{Algorithm}

\newenvironment{algorithm}{\begin{algorithm1}\ \\
    \vspace{-0.2cm}}{\end{algorithm1}}

%\newcommand{\qed}{\begin{flushright}
%\rule{.1in}{.1in} \end{flushright}  }


%\newenvironment{proofsk}{\nopagebreak
%\noindent{\bf Proof Sketch:}}{ \qed \par \medskip}

\newenvironment{proofsk}{\begin{proof}[Proof Sketch:]}
{\end{proof}}


\newenvironment{smallproof}{\nopagebreak \begin{quote} %
\begin{small} \noindent{\bf Proof:}}{ \qed \par %
\end{small} \end{quote} \medskip}

\newenvironment{note}{\nopagebreak \begin{quote} %
\noindent{\bf Note:}}{%
\end{quote} \medskip}

\newenvironment{notes}{\nopagebreak \begin{quote} %
\noindent{\bf Notes:} \par%
\begin{itemize}}{%
\end{itemize}\end{quote} \medskip}

\newenvironment{summary}{\begin{quote} {\bf Summary:}}{\end{quote}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% General Macros

\newcommand{\eqdef}{\stackrel{def}{=}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\bits}{\{0,1\}}
\newcommand{\inr}{\in_{\mbox{\tiny R}}}
\newcommand{\getsr}{\gets_{\mbox{\tiny R}}}
\newcommand{\st}{\mbox{ s.t. }}
\newcommand{\etal}{{\it et al }}
\newcommand{\into}{\rightarrow}

\newcommand{\Ex}{\mathbb{E}}
\newcommand{\To}{\rightarrow}
%\newcommand{\vec}[1]{\overline{\mathbf{#1}}}
\newcommand{\e}{\epsilon}
\newcommand{\ee}{\varepsilon}
\newcommand{\ceil}[1]{{\lceil{#1}\rceil}}
\newcommand{\floor}[1]{{\lfloor{#1}\rfloor}}
\newcommand{\angles}[1]{\langle #1 \rangle}

\fi


%-------------------------------------------------------------
% YOU MAY ADD ADDITIONAL (PRIVATE) MACROS HERE,
% BUT DO START EACH WITH YOUR INITIALS.
% FOR EXAMPLE, IF YOUR NAMES ARE ARIK SHARON AND SHIMON
% PERES THEN START EACH MACRO WITH ASSP.
% EXAMPLE: \newcommand{\ASSPz2}{\Z_2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ifnum\solitude=1
\begin{document}
\maketitle
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% BEGINNING OF DOCUMENT
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\vspace{0.5cm}

\begin{summary}
This document contains the scribal version of the lecture delivered by Dr. Stephen Bush to the CSI416/516 class at University of Albany, on 2007 December 6, containing information about network scheduling, QoS, and class project presentations.
\end{summary}

\section{Scheduling}
Scheduling is committing resources according to a plan.
Scheduling determines:
\begin{itemize}
	\item Who uses the network?
\end{itemize}
\begin{itemize}
	\item Whose packets get through?
\end{itemize}
\begin{itemize}
\item How often network is used by a particular user?
\end{itemize}

\section{Fairness}
There are a fixed number of connections to share. It is important that they are shared ``fairly''.
Fairness is a very subjective matter.  The access to resources can be proportional to:

\begin{itemize}
	\item money paid by a client 
\end{itemize}
\begin{itemize}
	\item priority of events
\end{itemize}
\begin{itemize}
	\item can be equal for each client 
\end{itemize}
Fairness protects from:
\begin{itemize}
	\item starvation -- a user is waiting forever for a resource
\end{itemize}
\begin{itemize}
\item	hogging -- one user utilizes so many resources that network usage reaches unacceptable levels  
\end{itemize}  

Max-min fairness is one of the solutions to starvation and hogging.
It is necessary to consider all the connections and grant equal access to all users. If there are any resources remaining they should be shared equally among users.

If clients pay for network service, a provider might need to guarantee some level of service. Different service might have to be provided for different users. A provider needs to consider:
\begin{itemize}
	\item	increasing, decreasing bandwidth 
\end{itemize} 
\begin{itemize}
	\item acceptable delay time 
\end{itemize} 
\begin{itemize}
	\item how many of packets can be lost
\end{itemize} 
\begin{itemize}
	\item	forbidding a request to come through a channel
\end{itemize} 
At the same time calculation of fairness should not take too much time.

\section{Admission Control and Priority}
It is impossible to allow everyone to use the network at the same time. It is necessary to use priority queues to prevent overflowing and implement different levels of service. Similarly to operating systems, different queues have different priorities. The highest priority has least delay. Low-priority packets can be starved. 

There are two types of disciplines:\\
1.work conserving - server never stops working\\
2.non-work-conserving - sever can stop and delay packets until they are eligible to be sent\\

Jitter can be reduced by having buffers to preload the data.

\section{GPS -- Generalized Processor Sharing}
GPS is as fair as possible. It is ``perfect'' but cannot be implemented because it is impossible to service one bit at a time. The packets cannot be divided into individual bits. People try to derive algorithms close to GPS. 

\section{WRR -- Weighted Round Robin}
In WRR, queues have assigned weights. Large queues get more service then small ones.
This discipline might be ``unfair'' since lengths of packets vary and weights are not equal.
Having a fixed size of packets is one of the ways to solve the problem. 
In case of different packet sizes it is possible to use mean packet size to normalize weights.

\section{WFQ  -- Weighted Fair Queuing}
WFQ is a discipline that approximates GPS. 
It tries to estimate finish times as if we had used GPS.
Finish number -- corresponds to finish time, denotes the round number when a packet finishes service. 
Suppose $p$ is length of a packet, 
$R$ is it's approximate arriving time
If packet arrives at an empty queue:\\
Then finish number  $=  R + p$\\
Otherwise, if the previous packet has a finish number of $f$:\\
Then finish number  $=  f + p$\\

Packets are served in order of finish number.\\


\section{Parekh-Gallager Theorem}
Parekh-Gallager Theorem was used to develop an efficient, flexible and ``fair'' service discipline. It assumes that WFQ provides both fairness and performance guarantees. It can be generalized to networks where schedulers are WFQ variants and link service rates change over time.

\section{Presentations}

The following is the second half of the class project presentations. The class project requires original research and experimental validation of new computer network ideas.

\subsection{``Online Video Game Simulation'' by William Lotridge}

There are two types of online video games: single player and massive.
Older games used TCP protocol. Nowadays, UDP protocol is more popular. As networks gets better the chance of losing packets decreases so there is less need for a protocol as reliable as TCP. \\
Main goal of this project: test different socket types and algorithms to determine limiting factor, simulate synchronized mobility of game characters.\\

\subsection{``TCP topology and DropTail Queue Mechanism'' by Junior John}

DropTail is a simple queue management algorithm. 
The topology of the system: 5 nodes, nodes 1,2,3  duplex - links with TCP agent attached. FTP application will be also interjected into nodes 1,2,3. One of the other nodes is Gateway.\\
Objective: understanding TCP transmission and monitoring the behavior of TCP session throughput.\\

\subsection{``Active Network Tomography by using Bayesian Inference'' by Piyush Patnaik}

There is a set of known and unknown connections between nodes. Use a tomographic-type of technique to infer network connectivity and QoS.\\
Main Goal: use Bayesian Inference to estimate the best connection among unknown links. \\

\subsection{``Information Superhighway'' by Ramon Rahman}

This project explores the idea of a ``smart'' system that would allow cars to drive without drivers. A system of satellites will keep track of information. There would be a main system that would be responsible for all calculations. It would collect all data from the cars and satellites. \\
Objective:  test availability, mobility and secure data transmission. 
Since security is very important, checking how fast virus can spread through the network is a primary goal of this project. 

\subsection{``Scalability of the BitTorrent P2P Application'' by Akram Mohammed and Meghshyam More}

Main goal : understand the performance and sensitive of BitTorrent\\
BitTorrent is a method of distributing large amount of data widely.
The BitTorrent system has three main components.\\
There are two types of peers; leechers and senders,  etc...
 
\subsection{``Validation of Patterns of Temporal Behavior in Wireless Micro-Sensor Networks'' by Lance Latham}

Wireless Micro-sensor network is a network of many (potentially millions) of micro-scale sensor nodes. Nodes are self-organize into a network, using dynamic routing. This kind of network is typically multi-modal -- more than one kind of node. Nodes use radio frequencies to forward data in multiple hops.

The selected problem is: Has the network been compromised? More computation by the nodes themselves is NOT the answer. What other solutions are available?
\begin{itemize}
	\item Is it possible to validate correct operation by analyzing patterns of temporal behavior?
\end{itemize} 
\begin{itemize}
	\item I.e., can we identify necessary patterns of behavior and use those to determine whether the network is operating securely?
\end{itemize} 

Essential constraints: 
\begin{itemize}
	\item Energy! Tiny, fixed, irreplaceable supply.
\end{itemize} 
\begin{itemize}
	\item  When battery dies, node dies.
\end{itemize} 
\begin{itemize}
	\item Implies extreme energy conservation.
\end{itemize} 
\begin{itemize}
	\item Implies minimizing computation of all kinds.
\end{itemize} 
\begin{itemize}
	\item Encryption is energetically expensive.
\end{itemize} 
\begin{itemize}
	\item Sleep-and-squirt mode of operation.
\end{itemize} 

Conclusions:
\begin{itemize}
	\item The failure behavior of communication paths with the selected model adheres to a very specific sigmoid curve model, indicating that failures are cumulative, and grow rapidly after a certain point. 
\end{itemize} 
\begin{itemize}
	\item The rate of increase eventually slows and then declines, as the number of remaining opportunities for failure become less frequent by exhaustion.
\end{itemize} 
\begin{itemize}
	\item The rate of communication failure for the selected model has a normal distribution.
\end{itemize} 
\begin{itemize}
	\item The parameters of the distribution vary with communications path length. 
\end{itemize} 
\begin{itemize}
	\item It is possible, given a log of temporal behavior over some time period P, for the network, to determine whether valid communication functions have occurred. The project assumes that such a log is available from an external source, such as a separate 'master node'.
\end{itemize} 
\begin{itemize}
	\item Such periods can be assumed to occur on some regular cycle, such that data storage  is not problematic. Short cycles also give earlier warning.
\end{itemize} 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% END OF DOCUMENT
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{quote}
References: 	\itshape Wikipedia.com, whatis.com
\end{quote}
\ifnum\solitude=1
\end{document}

\fi