text:
\section{Introduction}
Datacenter networks serve as infrastructure for search engines, social networks, cloud computing, etc.  Due to potentially
high traffic loads, load-balancing becomes an important solution to improve network utilization and alleviate hot spots \cite{VL2,ScalableTopology,GoogleDC,FBDC}.  A widely-used technique is equal-cost multipath (ECMP), where traffic flows are split equally according to the number of available equal-cost next-hops.  However, ECMP does not take into account actual traffic and is susceptible to asymmetric topology \cite{Niagara,CONGA,WCMP}.  Further, the deployment of ECMP is limited due to its equal-cost constraint \cite{BCube}.

Traffic load-balancing can be implemented using software-defined networking (SDN).  An SDN switch, a network device supporting layer-2 and layer-3 operations in OSI architecture, consists of a data plane and control plane \cite{SDNSwitch}.\footnote{An SDN switch should not be confused with a crossbar switch, which may reside in the data plane of an SDN switch.}   The data plane forwards packets according to given rules and operates at a fast timescale, e.g., $1$ns.  The control plane sets those rules and operates at a much slower timescale, e.g., $1$ms.  Several traffic load-balancing algorithms can be implemented through the control plane reconfiguration.

Existing traffic load-balancing methods for datacenter networks distribute traffic according to network capacity and measured traffic.  Weighted-cost multipath \cite{WCMP} distributes traffic according to path capacity.  Centralized algorithms, such as Hedera \cite{Hedera} and Niagara \cite{Niagara}, take advantage of global traffic information to split traffic at a coarse timescale.  Load-balancing with a finer timescale has been implemented in DeTail \cite{DeTail} and CONGA \cite{CONGA} using the \emph{in-network} technique, where decisions are made at switches inside a network without any central controller.  Conceptually, these approaches attempt to distribute traffic over available network resources.  However, the path-based approach in CONGA limits scalability, and the packet-by-packet dispersion in DeTail needs TCP with out-of-order resilience.  Further, these algorithms do not come with analytical optimality proofs, and it is not clear if they are \emph{throughput optimal}.

An algorithm is throughput optimal if it stably supports any feasible traffic load, so that average backlog is bounded \cite{MaxWeight}.  Specifically, a throughput-optimal algorithm utilizes the entire network capacity and can distribute traffic to any portion of the network to maintain network stability.  MaxWeight \cite{MaxWeight} is a well-known throughput-optimal algorithm and has been studied for packet radio \cite{MaxWeight}, switching \cite{McKeown:Switch}, and inter-datacenter networking \cite{Javidi:DCNet}.  It has been generalized to optimize power allocation \cite{Neely:Power}, throughput \cite{Eryilmaz:Throughput}, etc.  Practical aspects of MaxWeight such as finite buffer capacity and fairness with TCP connections have been studied in \cite{Sucha:FIFO,WirelessFiniteBuff,TCP-Backpressure}.  However, MaxWeight is not suitable for
in-network load-balancing because it prohibits the sharing of link capacity at the data plane's timescale and thus causes high queue occupancy.  This queue size has a finite average, but the size of the longer timescale makes that average unacceptably large.

\begin{figure}[!t]
  \centering
  \includegraphics[scale=1.0]{ToyProblem.pdf}\vspace{-2mm}
  \caption{MaxWeight example: Let $w_{ij}^d$ be the weight of commodity $d$ over the link from switch $i$ to switch $j$.  All weights in this figure are $\prtr{ w_{12}^1, w_{12}^2, w_{23}^1, w_{23}^2 } = \prtr{ 0, 1, 3, 1 }$.}\vspace{-4.5mm}
  \label{fig:ToyExample}
\end{figure}

\begin{figure*}[!t]
  \centering
  \includegraphics[scale=1.0]{MaxWeightTimeLine.pdf}\vspace{-2mm}
  \caption{Timeline of queue occupancy under MaxWeight: a small box represents a packet in a queue.  Switch $i$ is represented by the number $i \in \prtc{1,2,3}$ under the long line.  The short line under the number indicates that the commodity at the numbered switch is served in that particular time slot.  The occupancy pattern repeats after $t=14$, which is similar to the pattern at $t=11$.}\vspace{-4.5mm}
  \label{fig:MaxWeightTimeLine}
\end{figure*}

The MaxWeight algorithm is illustrated by the example in Fig. \ref{fig:ToyExample}.  Two traffic commodities share  three links passing through switches $1,2$ and $3$.  Time is slotted.  The slot size equals the length of the decision update
interval (the control plane's timescale).  The capacity of each link is $3$ packets per slot.  Every switch has a dedicated queue for each commodity.  In every time slot, MaxWeight calculates, for each link and commodity, a weight equal to the differential backlog between a queue and its next-hop queue.  For that slot, the entire capacity of the link is allocated to the commodity with the maximum non-negative weight, while a commodity with negative weight is ignored.  For example,
 commodity $2$ is served on the link between switches $1$ and $2$ in Fig. \ref{fig:ToyExample}, and
 commodity $1$ is served on the link between switches  $2$ and $3$.

Let the arrival rates to switch $1$ of commodities $1$ and $2$ be respectively $1$ and $2$ packets per slot.  The timeline of queue evolution is shown in Fig. \ref{fig:MaxWeightTimeLine}.  MaxWeight is effective and always transmits three packets per slot after $t=11$.  This effectiveness requires a sufficient amount of queue backlog. For example, commodity $2$ backlog at switch $1$ is always at least $5$ for times $t  \geq 11$.  This occupancy might be acceptable.  However, if the control plane is reconfigured at a slow timescale relative to the link
capacity, the queue occupancy can be very high. For example, with a $1$ms update interval, $10$Gbps link speed, and $1$kB packet size, each link can serve 1250 packets per slot (rather than just 3).  This multiplies queue backlog in the
timeline of Fig. \ref{fig:MaxWeightTimeLine} by a factor $1250/3$,  so the minimum queue backlog of commodity $2$ at switch $1$ is $5\times(1250/3)\approx 2083$ for $t \geq 11$.  Another undesirable property of MaxWeight is that
queue occupancy  scales linearly with the number hops, as shown in \cite{Scott:LIFO,ShadowQueue}.  In fact, Fig. \ref{fig:MaxWeightTimeLine} is inspired by an example in \cite{Scott:LIFO}.

In practice, the MaxWeight mechanism with a long update interval leads to i) large buffer memory, ii) packet drops, iii) high latency, and iv) burstiness (no capacity sharing during an update interval).  Issues (i)--(iii) can be alleviated partially by the techniques in \cite{Neely:SNO,Sucha:Quadratic,Longbo:Lagrange,ShadowQueue}.  However, issue (iv) resides in the decision making mechanism of MaxWeight and still persists under those techniques.  The situation is worse when issues (ii) and (iv) interact with TCP congestion control, causing slow flow rate and under utilization.  To put it into theoretical perspective, even though MaxWeight solves a network stability problem with $O(1)$ average queue size, the constant factor is too large for a practical system with a long update interval.  Note that an ideal algorithm for the example in Fig. \ref{fig:ToyExample} always serves $1$ and $2$ packets of commodities $1$ and $2$ by sharing the link capacity as shown in Fig. \ref{fig:IdealAlgorithm}.

\begin{figure}
  \centering
  \includegraphics[scale=1.0]{IdealAlgorithm.pdf}\vspace{-2mm}
  \caption{Timeline of queue occupancy under the ideal algorithm}\vspace{-4.5mm}
  \label{fig:IdealAlgorithm}
\end{figure}

In this paper, a new throughput-optimal algorithm is developed.  The algorithm shares link capacity among commodities during an update interval, resulting in low queue occupancy and low latency.  The key challenge is to design a model and an algorithm that are analyzable, provably optimal,  and practically implementable at the same time.  The algorithm imitates the weighted fair queueing (WFQ) \cite{WFQ,GPS} available in practical switches to provide fairness and low latency among TCP flows in practice.  A general intra data center network may have an exponential number of paths, and our algorithm comes with an optimality proof considering all possible paths using per-commodity queueing which grows linearly with the number of commodities.  This is also a key distinct aspect from the path-based algorithm in \cite{PathBase}.

Section \ref{sec:IdealAlgorithm} develops the throughput-optimal algorithm.
Inspired by this algorithm, Section \ref{sec:Implementation} presents an enhanced
algorithm that includes heuristics  to cope with practical aspects, including queue information dissemination, queue approximation, and packet reordering issues in TCP.  This heuristic algorithm uses local queue information and local measured traffic to hash TCP flows to next-hop switches and set weights of the weighted fair queueing.  The hash-based mechanism is chosen to reduce packet reordering, which is not possible for DeTail \cite{DeTail}.  Simulation results in Section \ref{sec:Simulations}
show that both proposed algorithms outperform MaxWeight and ECMP algorithms in ideal simulation and in more realistic simulation with OMNeT++\cite{OMNet}.

\section{System Model and Design}
\label{sec:Model}
The fast timescale of the data plane operates over slotted time $t \in  {\mathbb{Z}} _+$, where $ {\mathbb{Z}} _+ = \prtc{0, 1, 2, \dotsc }$.  The control plane configures the data plane every $T$ slots, where $T$ is a positive integer.  Thus, reconfigurations occur at times in the set $\set{T} = \prtc{0, T, 2T, \dotsc}$.

\subsection{Topology and Routing}
An intra datacenter network is the interconnection of switches and destinations (such as servers), as shown in Fig. \ref{fig:ModelTopology}.
Traffic designated for a particular destination $d$ is called \emph{commodity $d$} traffic.  Let $\set{S}$ be the set of all switches and $\set{D}$ be the set of all destinations (commodities).
A link between switches $i$ and $j$ is bi-directional with capacity $c_{ij}$ from $i$ to $j$, and capacity $c_{ji}$ in the reverse direction.
Define $c_{ij} = 0$ if  link $(i,j)$ does not exist or if $i=j$.

\begin{figure}
  \centering
  \includegraphics[scale=1.0]{ModelTopology.pdf}\vspace{-2mm}
  \caption{An example network with $\set{S} = \prtc{1, 2, \dotsc, 14}$ and $\set{D} = \prtc{1, 2, \dotsc, 8}$}\vspace{-4.0mm}
  \label{fig:ModelTopology}
\end{figure}

Each switch must decide where to send its packets next.  Define
$\set{H}_i^d \subseteq \set{S}$ as the set of next-hop switches available to commodity $d$ packets in switch $i$,
for all $i \in \set{S}$ and $d \in \set{D}$.
In practice, these sets can be obtained from manual configuration or from other routing mechanisms.  Define the set of all next-hop switches from switch $i$ as $\set{H}_i = \cup_{d \in \set{D}} \set{H}_i^d$, and the set of previous-hop switches as $\set{P}_i^d = \prtc{ j \in \set{S} : i \in \set{H}_j^d }$ for $i \in \set{S}, d \in \set{D}$.  These sets are illustrated in Fig. \ref{fig:Nexthop}.   Define $\set{D}_{ij} = \prtc{ d \in \set{D} : j \in \set{H}_i^d}$ as the set of all commodities utilizing a link from switch $i$ to switch $j$ for $i,j \in \set{S}$.  Note that this model allows arbitrary path lengths, and can be applied to existing topologies in \cite{VL2,ScalableTopology,GoogleDC,FBDC,BCube}.

\begin{figure}
  \centering
  \includegraphics[scale=1.0]{Nexthop.pdf}\vspace{-2mm}
  \caption{Example of sets of switches at switch 9.  Note that $\set{P}_9^8$ must not contain $10$ to avoid loops and imposes that $9 \notin \set{H}_{10}^8$.}\vspace{-4.5mm}
  \label{fig:Nexthop}
\end{figure}

\subsection{Traffic}
Switch $i$ receives $a_i^d(t)$ commodity-$d$ packets from external sources at time $t$ (for $i \in \set{S}, d \in \set{D}$).  The external source represents a group of servers or a link connecting to the outside of the network.  For each $i \in \set{S}$, $d \in \set{D}$, the  arrival process $\{a_i^d(t)\}_{t=0}^{\infty}$ is independent and identically distributed (i.i.d.) across time slots.  The i.i.d. assumption is useful for a simple and insightful analysis.
The resulting algorithm developed under this assumption inspires a heuristic algorithm in Section \ref{sec:Implementation} that does not require i.i.d. arrivals and works gracefully with TCP traffic.

Recall that $c_{ij}$ is the capacity of the link between switch $i$ and switch $j$, for $i, j \in \set{S}$.
Let $b_i^d$ be the capacity of the link between switch $i \in \set{S}$ and destination $d \in \set{D}$. Set $b_i^d=0$ if
switch $i$ does not have a direct link
to destination $d$.   Assume arrivals and link capacities are  always bounded by a constant $\delta>0$, so  $0\leq c_{ij} \leq \delta$,
$0\leq a_i^d(t) \leq \delta$,  $0\leq b_i^d \leq \delta$ for all $i,j\in \set{S}, d \in \set{D}, t \in  {\mathbb{Z}} _+$.

\subsection{Decision Variables}

Decision variables are defined for every link connecting switch $i$ to its next-hop switch $j$, for $i \in \set{S}, j \in \set{H}_i$.  Recall that $\set{D}_{ij}$ is a set of commodities using the link.  At configuration time $t \in \set{T}$, the control plane in switch $i$ chooses a \emph{control plane decision variable} $x_{ij}^d(t,T)$ for $d \in \set{D}_{ij}$, which represents a constant transmission rate allocated to commodity $d$ (in units of packets) for the entire $T$-slot interval.  Define $x_{ij}^d(t,T) = 0$ for $d \in \set{D} \backslash \set{D}_{ij}$.  The control plane decisions for  link $(i,j)$ are chosen to satisfy the link capacity constraint:
$$ \sum_{d \in \mathcal{D}_{ij}}  x_{ij}^d(t,T) \leq T c_{ij}. $$

Once $x_{ij}^d(t,T)$ is determined, no more than $x_{ij}^d(t,T)$  commodity-$d$ packets can be
transmitted by the data plane during an interval $\prtc{t, \dotsc, t+T-1}$.  For example, the data plane can impose a token bucket mechanism.  Let $x_{ij}^d(t)$ be  \emph{data plane decision variable} that represents
the transmission rate assigned by the data plane to commodity $d$ on link $(i,j)$ for slot $t$. These are chosen to satisfy
\begin{align}
  x_{ij}^d(t,T) & = \sum_{\tau = t}^{t+T-1} x_{ij}^d(\tau) &&\hspace{-1mm}\text{for}~i\in \set{S}, j \in \set{H}_i, t \in \set{T}   \label{eq:xijdT}\\
  \sum_{d \in \set{D}_{ij}} x_{ij}^d(t) & \leq c_{ij} &&\hspace{-1mm}\text{for}~i\in \set{S}, j \in \set{H}_i, t \in  {\mathbb{Z}} _+. \label{eq:cij}
\end{align}

\subsection{Queues}

\label{sec:Queue}

Packets are queued at each switch according to their commodity.  Let  $Q_i^d(t)$ be the number of commodity-$d$
packets queued at switch $i$ on slot $t$.  The value $Q_i^d(t)$ is also called  the \emph{commodity-$d$ backlog}
and satisfies:
\begin{multline}
  \label{eq:Qid}
  Q_i^d(t+1) \leq \prts{ Q_i^d(t) - \sum_{j \in \set{H}_i^d} x_{ij}^d(t) - b_i^d }_+ +\\\sum_{j \in \set{P}_i^d} x_{ji}^d(t) + a_i^d(t) \quad\text{for}~ i \in \set{S}, d \in \set{D},
\end{multline}
where $\prts{z}_+ = \max[0,z]$.  Note that $\sum_{j \in \set{H}_i^d} x_{ij}^d(t)$ denotes  output transmission rate to next-hop switches, and $\sum_{j \in \set{P}_i^d} x_{ji}^d(t)$ denotes receiving transmission rate from previous-hop switches.
Inequality \eqref{eq:Qid} is an inequality rather than an equality because the actual amount of new endogenous arrivals
on slot $t$ may be less than $\sum_{j \in \set{P}_i^d} x_{ji}^d(t)$ if previous switches $j$ do not have enough commodity $d$
backlog to fill the assigned transmission rate $x_{ji}^d(t)$.
It can be shown that the backlog at time $t \in \set{T}$ satisfies for every $i \in \set{S}, d \in \set{D}$:
\begin{multline}
  \label{eq:QidT}
  Q_i^d(t+T) \leq \prts{ Q_i^d(t) - \sum_{j \in \set{H}_i^d} x_{ij}^d(t,T) - T b_i^d }_+ + \\\sum_{j \in \set{P}_i^d} x_{ji}^d(t,T) + \sum_{\tau=t}^{t+T-1} a_i^d(\tau).
\end{multline}

Note that, while a common queue for each commodity is not available in practical switches, it can be heuristically implemented by queues in an SDN switch in Section \ref{sec:Implementation}

\subsection{Stability and Assumption}
\begin{definition}[Queue Stability  \cite{Neely:SNO}]
  \label{def:QueueStability}
  A queue with backlog $\prtc{ Z(t) \geq 0 : t \in  {\mathbb{Z}} _+ }$ is strongly stable if
\begin{equation*}
  \limsup_{t \rightarrow \infty} \frac{1}{t} \sum_{\tau = 0}^{t - 1} \expect{ Z(\tau) } < \infty.
\end{equation*}
\end{definition}

\begin{definition}[Network Stability  \cite{Neely:SNO}]
  A network is strongly stable when every queue in the network is strongly stable.
\end{definition}

The arrival and departure rates are assumed to satisfy a standard Slater condition:
\begin{assumption}[Slater Condition]
  \label{ass:Slater}
  There exists an $\epsilon>0$ and a randomized policy $\prtc{ x_{ij}^{d\ast}(t) }_{i \in \set{S}, d \in \set{D}, j \in \set{H}_i^d}$ with
\begin{multline*}
  \expect{ \sum_{j \in \set{P}_i^d} x_{ji}^{d\ast}(t) + a_i^d(t) - \sum_{j \in \set{H}_i^d} x_{ij}^{d\ast}(t) - b_i^d } < -\epsilon \\\text{for all}~ i \in \set{S}, d \in \set{D}, t \in  {\mathbb{Z}} _+,
\end{multline*}
and the randomized policy satisfies the constraint \eqref{eq:cij}.
\end{assumption}

Note that Assumption \ref{ass:Slater} is stated in terms of only the data plane decision variables $x_{ij}^{d*}(t)$ and
the constraint \eqref{eq:cij}.  While the control plane decisions are used in the algorithm and the additional
constraint \eqref{eq:xijdT} is satisfied by the algorithm, those  are not used in the
Slater condition.

\section{Throughput-Optimal Algorithm}
\label{sec:IdealAlgorithm}
\subsection{The Algorithm}
The novel throughput-optimal algorithm runs distributively at every switch.  Let $K$ be a positive real number, and $x_{ij}^d(-T,T) = 0$ for all $i,j \in \set{S}, d \in \set{D}$.  At every reconfiguration time $t \in \set{T}$, switch $i$ executes Algorithm \ref{alg:Main} for each link connecting to a next-hop switch $j$ for $i \in \set{S}, j \in \set{H}_i$.   Recall that $x_{ij}^d(t,T) = 0$ for $d \in \set{D} \backslash \set{D}_{ij}$.  The function $\round{z}$ rounds the real-valued $z$ to its closest integer.

\begin{algorithm}
  \begin{algorithmic}
    \STATE{ \texttt{// switch $i$, link to switch $j$, time $t$ //} }\vspace{1mm}
    \STATE{ $y_{ij}^d(t) \leftarrow Q_i^d(t) - Q_j^d(t) + x_{ij}^d(t-T,T) $ for $d \in \set{D}_{ij}$ }
    \STATE{ $k_{ij}(t) \leftarrow \max\prts{ 1, \min\prts{ K, \frac{1}{Tc_{ij}} \sum_{d \in \set{D}_{ij}} \prts{ y_{ij}^d(t) }_+ } }$ }

    \IF{ $\sum_{d \in \set{D}_{ij}} \round{ \prts{ y_{ij}^d(t) }_+ / k_{ij}(t) } \leq T c_{ij}$ }
    \STATE{ $x_{ij}^d(t,T) \leftarrow \round{ \prts{ y_{ij}^d(t) }_+ / k_{ij}(t) }$ for $d \in \set{D}_{ij}$ }
    \RETURN{ $\prtc{ x_{ij}^d(t,T) }_{d \in \set{D}_{ij}}$ }
    \ELSE
      \RETURN{ result of Algorithm \ref{alg:PacketFilling} }
    \ENDIF
  \end{algorithmic}
  \caption{Throughput-optimal rate allocation}
  \label{alg:Main}
\end{algorithm}
\begin{algorithm}
  \begin{algorithmic}
    \STATE{ \texttt{// switch $i$, link to switch $j$, time $t$ //} }\vspace{1mm}

    \STATE{ $y_{ij}^d(t) \leftarrow Q_i^d(t) - Q_j^d(t) + x_{ij}^d(t-T,T) $ for $d \in \set{D}_{ij}$ }
    \STATE{ $v_{ij}^d \leftarrow 0$ for $d \in \set{D}_{ij}$ }
    \FOR{ $n = 1$ to $T c_{ij}$ }
    \STATE{ $d_n \leftarrow \argmax_{e \in \set{D}_{ij}} \prts{ y_{ij}^e(t) - v_{ij}^e k_{ij}(t) }$ }
    \STATE{ $v_{ij}^{d_n} \leftarrow v_{ij}^{d_n} + 1$ }
    \ENDFOR
    \STATE{ $x_{ij}^d(t,T) \leftarrow v_{ij}^d$ for $d \in \set{D}_{ij}$ }
    \RETURN{ $\prtc{ x_{ij}^d(t,T) }_{d \in \set{D}_{ij}}$ }
  \end{algorithmic}
  \caption{Packet-filling algorithm (unaccelerated version)}
  \label{alg:PacketFilling}
\end{algorithm}

\subsection{Intuitions}
\label{sec:Intuitions}
Algorithm \ref{alg:Main} solves problem \eqref{eq:MainProblem} with the value of $k_{ij}(t)$ that depends on local queue information and previous decisions.  This $k_{ij}(t)$ is deliberately introduced, just as a solution of problem \eqref{eq:MainProblem} imitates weighted fair queueing, which provides fairness and low latency in practice \cite{WFQ,GPS}.
\begin{align}
   {\text{Minimize}}  \quad & \sum_{d \in \set{D}_{ij}} \Bigg\{ x_{ij}^d(t, T) \prts{ Q_j^d(t) - Q_i^d(t) } + \Bigg. \notag \\ &\quad \Bigg. \frac{ k_{ij}(t) }{ 2 } \prts{ x_{ij}^d(t, T) - \frac{ x_{ij}^d(t-T, T) }{ k_{ij}(t) } }^2 \Bigg\} \label{eq:MainProblem} \\
   {\text{Subject to}}  \quad & \sum_{d \in \set{D}_{ij}} x_{ij}^d(t, T) \leq T c_{ij} \notag\\
  & x_{ij}^d(t, T) \in  {\mathbb{Z}} _+ \hspace{4.5em} \text{for all}~~ d \in \set{D}_{ij} \notag
\end{align}

In Algorithm \ref{alg:Main}, $y_{ij}^d(t)$ represents a request for transmission rate of commodity $d$.  It also indicates how well the previous rates were allocated.  Under allocation of $x_{ij}^d(t-T,T)$ increases queue backlog $Q_i^d(t)$, which tends to increase the request $y_{ij}^d(t)$.  It is easy to see that, if the queue backlogs $Q_i^d(t)$ and $Q_j^d(t)$ are about the same, then the request is about the same as its previous value.  This behavior is smoother than MaxWeight.

The requests are fulfilled in two situations.  i) When the total requests are roughly within $K T c_{ij}$, i.e., $\sum_{d \in \set{D}_{ij}} \round{ \prts{ y_{ij}^d(t) }_+ / k_{ij}(t) } \leq T c_{ij}$, the requests are fulfilled in WFQ fashion, which can be seen by considering $k_{ij}(t) = \frac{1}{T c_{ij}} \sum_{d \in \set{D}_{ij}} \prts{ y_{ij}^d(t) }_+$ and
\begin{align}
  x_{ij}^d(t, T) & = \round{ \prts{ y_{ij}^d(t) }_+ / k_{ij}(t) } \notag\\
    & = \round{ \frac{ \prts{ y_{ij}^d(t) }_+ }{ \sum_{e \in \set{D}_{ij}} \prts{ y_{ij}^e(t) }_+ } \times T c_{ij} }. \label{eq:WFQIntuition}
\end{align}
ii) The other is an extreme situation for stability analysis, which occurs when a network operates near its capacity, which may not be the case in practice due to TCP congestion control.  This case is solved by Algorithm \ref{alg:PacketFilling}\footnote{Algorithm \ref{alg:PacketFilling} can be accelerated by fulfilling multiple requests per iteration. For example, the requests in Fig. \ref{fig:PacketFilling} can be fulfilled in three iterations.}, as illustrated by Fig. \ref{fig:PacketFilling}.  It is easy to see the fairness introduced by $k_{ij}(t)$.  Without $k_{ij}(t)$, i.e., $k_{ij}(t)$ is always $1$, the allocation in Fig. \ref{fig:PacketFilling} will be $0, 0, 2, 7$ for commodities $1$ to $4$, which may cause a fairness issue with TCP flows \cite{TCP-Backpressure}.

\begin{figure}
  \centering
  \includegraphics[scale=1.0]{PacketFilling.pdf}\vspace{-2mm}
  \caption{Packet-filling Algorithm \ref{alg:PacketFilling} iteratively fulfills the requests.  An iteration number is indicated in a gray box.  In this example, $T c_{ij} = 9$ and the first iteration (the plot on the left) allocates rate to commodity 4.  The algorithm allocates $2, 0, 3, 4$ rates to commodities $1, 2, 3,4$.}\vspace{-4.5mm}
  \label{fig:PacketFilling}
\end{figure}

\subsection{Correctness of Algorithm \ref{alg:Main}}
\label{sec:solution}
This subsection shows that  Algorithm \ref{alg:Main} returns an optimal solution of problem \eqref{eq:MainProblem}.  To simplify notation in this section, the time index of variables and constants in problem \eqref{eq:MainProblem} are omitted. Let $z_{ij}^d$ denote $x_{ij}^d(t-T,T)$.

When commodity $d$ is allocated an integer service value $v_{ij}^d$, define its contribution to the cost function of problem \eqref{eq:MainProblem} as
\begin{equation*}
  \label{eq:gijd}
  g_{ij}^d( v_{ij}^d ) = v_{ij}^d \prts{ Q_j^d - Q_i^d } + \frac{ k_{ij} }{ 2 } \prts{ v_{ij}^d - \frac{ z_{ij}^d }{ k_{ij} } }^2.
\end{equation*}
The cost difference of getting another service allocation is
\begin{equation}
  \label{eq:diffgijd}
g_{ij}^d( v_{ij}^d + 1 ) - g_{ij}^d( v_{ij}^d ) = - \prts{ Q_i^d - Q_j^d + z_{ij}^d - \frac{ k_{ij} }{ 2 } - k_{ij} v_{ij}^d }.
\end{equation}
Since the cost function in problem \eqref{eq:MainProblem} is minimized, commodity $d$ only accepts a transmission allocation if $g_{ij}^d( v_{ij}^d + 1 ) \leq g_{ij}^d( v_{ij}^d )$.  The cost difference in \eqref{eq:diffgijd} is monototically increasing in $v_{ij}^d$.  Therefore, commodity $d$ receives transmission allocation at most:
\begin{align}
  x_{ij}^{d {(\text{max})} } &= \min \prtc{ v \in  {\mathbb{Z}} _+ : g_{ij}^d( v + 1 ) - g_{ij}^d( v ) > 0 } \label{eq:xijdmaxDef}\\
  & = \min \prtc{ v \in  {\mathbb{Z}} _+ : \frac{ Q_i^d - Q_j^d + z_{ij}^d }{ k_{ij} } - 0.5 < v } \notag\\
  & = \round{ \prts{ Q_i^d - Q_j^d + z_{ij}^d }_+ / k_{ij} }. \label{eq:xijdmax}
\end{align}

\begin{lemma}
  \label{lem:solution2}
  When $k_{ij} > 0$ and $\sum_{d \in \set{D}_{ij}} x_{ij}^{d {(\text{max})} } \leq T c_{ij}$, the optimal solution of problem \eqref{eq:MainProblem} is $x_{ij}^d = x_{ij}^{d {(\text{max})} }$ for $d \in \set{D}_{ij}$.
  \begin{proof}
    For any $v_{ij}^d \in \prtc{ 0, 1, \dotsc, x_{ij}^{d {(\text{max})} } }, d \in \set{D}_{ij}$, the given implies that $\sum_{d \in \set{D}_{ij}} v_{ij}^d \leq \sum_{d \in \set{D}_{ij}} x_{ij}^{d {(\text{max})} } \leq T c_{ij}$.  So, any chosen $v_{ij}^d$ in $\prtc{ 0, 1, \dotsc, x_{ij}^{d {(\text{max})} } }$ leads to a feasible solution of problem \eqref{eq:MainProblem}.  Note that the objective function of problem \eqref{eq:MainProblem} is separable, $\sum_{d \in \set{D}_{ij}} g_{ij}^d( v_{ij}^d )$, and is minimized.  The definition of $x_{ij}^{d {(\text{max})} }$ in \eqref{eq:xijdmaxDef} implies $g_{ij}^d( v ) > g_{ij}^d( x_{ij}^{d {(\text{max})} } )$ for any $v > x_{ij}^{d {(\text{max})} }$, so any $v > x_{ij}^{d {(\text{max})} }$ is not optimal.  Thus, i) if $x_{ij}^{d {(\text{max})} } = 0$, $x_{ij}^d = 0 = x_{ij}^{d {(\text{max})} }$ minimizes problem \eqref{eq:MainProblem} with respect to commodity $d$.  ii) If $x_{ij}^{d {(\text{max})} } > 0$, the definition of $x_{ij}^{d {(\text{max})} }$ in \eqref{eq:xijdmaxDef} implies $g_{ij}^d( x_{ij}^{d {(\text{max})} } ) \leq g_{ij}^d( v )$ for any $v \in \prtc{ 0, 1, \dotsc, x_{ij}^{d {(\text{max})} } - 1 }$, so $x_{ij}^d = x_{ij}^{d {(\text{max})} }$ minimizes the problem with respect to commodity $d$.
  \end{proof}
\end{lemma}

Lemma \ref{lem:solution2} implies that Algorithm \ref{alg:Main} solves problem \eqref{eq:MainProblem} when the first (if-)condition is met.  The other case of Algorithm \ref{alg:Main} can be shown by the following property.  When commodity $d$ is allocated $v_{ij}^d$ transmission rate, define the unfulfilled level of commodity-$d$'s request as
\begin{equation}
  \label{eq:lijd}
  l_{ij}^d( v_{ij}^d ) = Q_i^d - Q_j^d + z_{ij}^d - k_{ij} v_{ij}^d.
\end{equation}

\begin{lemma}
  \label{lem:level}
  When $k_{ij} > 0$, for any commodities $d, e \in \set{D}_{ij}$ whose allocated rates are respectively $v_{ij}^d$ and $v_{ij}^e$, the following holds:\\
  i) If $l_{ij}^d ( v_{ij}^d ) = l_{ij}^e ( v_{ij}^e )$, then
  \begin{equation*}
    g_{ij}^d( v_{ij}^d + 1 ) + g_{ij}^e( v_{ij}^e ) = g_{ij}^d( v_{ij}^d ) + g_{ij}^e( v_{ij}^e + 1 ).
  \end{equation*}
  ii) If $l_{ij}^d ( v_{ij}^d ) > l_{ij}^e ( v_{ij}^e )$, then
  \begin{equation*}
    g_{ij}^d( v_{ij}^d + 1 ) + g_{ij}^e( v_{ij}^e ) < g_{ij}^d( v_{ij}^d ) + g_{ij}^e( v_{ij}^e + 1 ).
  \end{equation*}
  \begin{proof}
    It holds from equations \eqref{eq:diffgijd} and \eqref{eq:lijd} that
    \begin{align}
      & g_{ij}^d( v_{ij}^d + 1 ) - g_{ij}^d ( v_{ij}^d ) - g_{ij}^e( v_{ij}^e + 1 ) + g_{ij}^e( v_{ij}^e ) \notag\\
      & \quad = - \prts{ l_{ij}^d( v_{ij}^d ) - \frac{ k_{ij} }{ 2 } } + \prts{ l_{ij}^e( v_{ij}^e ) - \frac{ k_{ij} }{ 2 } } \notag\\
      & \quad = - l_{ij}^d( v_{ij}^d ) + l_{ij}^e( v_{ij}^e ). \label{eq:gg}
    \end{align}
    In case (i), $l_{ij}^d ( v_{ij}^d ) = l_{ij}^e ( v_{ij}^e )$ implies that $g_{ij}^d( v_{ij}^d + 1 ) - g_{ij}^d ( v_{ij}^d ) - g_{ij}^e( v_{ij}^e + 1 ) + g_{ij}^e( v_{ij}^e ) = 0$, which proves (i).  Case (ii) can be proven similarly by substituting $- l_{ij}^d ( v_{ij}^d ) + l_{ij}^e ( v_{ij}^e ) < 0$ into equation \eqref{eq:gg} and rearranging terms.
  \end{proof}
\end{lemma}

Lemma \ref{lem:level} implies that allocating rate to the commodity with the highest unfulfilled level reduces the total objective the most.  Specifically, let $v_{ij}^d$ be the current rate allocation of commodity $d$.  For $d^\ast = \argmax_{d \in \set{D}_{ij}} l_{ij}^d(v_{ij}^d)$, Lemma \ref{lem:level} implies that
\begin{multline*}
  g_{ij}^{d^\ast}( v_{ij}^{d^\ast} + 1 ) + \sum_{d \in \set{D}_{ij}\backslash\prtc{d^\ast}} g_{ij}^d( v_{ij}^d ) \leq \\g_{ij}^{e}( v_{ij}^{e} + 1 ) + \sum_{d \in \set{D}_{ij}\backslash\prtc{e}} g_{ij}^d( v_{ij}^d ) \quad \text{for all}~ e \in \set{D}_{ij}.
\end{multline*}

The above property ensures that the iterative allocation in Algorithm \ref{alg:PacketFilling} greedily optimizes problem \eqref{eq:MainProblem} when event $\sum_{d \in \set{D}_{ij}} \round{ \prts{ y_{ij}^d(t) }_+ / k_{ij}(t) } > T c_{ij}$ occurs.  It can be proven by contradiction that commodity $d$ gets at most $x_{ij}^{d {(\text{max})} }$ rate for all $d \in \set{D}_{ij}$.  Then, the algorithm always allocates the entire transmission rate, as an implication of the event.  Therefore, Algorithm \ref{alg:PacketFilling} returns an optimal solution of problem \eqref{eq:MainProblem}.

\begin{theorem}
  Given $K > 0$, Algorithm \ref{alg:Main} solves problem \ref{eq:MainProblem} with $k_{ij}(t) \in [1, K]$, where $k_{ij}(t)$ is defined in the algorithm.
\begin{proof}
The theorem is the consequence of Lemmas \ref{lem:solution2} and \ref{lem:level} and the fact that $k_{ij}(t) \in [1, K]$.
\end{proof}
\end{theorem}

\subsection{Stability Analysis}
Problem \ref{eq:MainProblem} with $k_{ij}(t) \in [1, K]$ is shown to be a class of throughput-optimal policies.  Let $Q(t) = \prtr{ Q_i^d(t) }_{i \in \set{S}, d \in \set{D}}$ be a vector of all backlogs at time $t$.  Define $\norm{z}_1$ as the $l_1$-norm, e.g., $\norm{ Q(t) }_1 = \sum_{i \in \set{S}} \sum_{d \in \set{D}} Q_i^d(t)$.

\begin{theorem}
  When Assumption \ref{ass:Slater} holds, the network is strongly stable:
  \begin{equation*}
    \limsup_{N \rightarrow \infty} \frac{1}{NT} \sum_{n=0}^{N-1}\sum_{\tau=0}^{T-1} \expect{ \norm{Q(nT + \tau)}_1 } \leq \frac{G_1}{\epsilon} + G_2,
  \end{equation*}
  where $G_1 = \abs{\set{S}} \abs{\set{D}} \prts{ T \delta^2 \prtr{ \abs{\set{S}} + 1 } + 2 K T \delta^2 \abs{\set{S}} }$ and $G_2 = (T-1)\delta(\abs{\set{S}} + 1)/2$.
\end{theorem}

\begin{proof}
Squaring both sides of \eqref{eq:QidT}, rearranging, and bounding terms (see \cite{Neely:SNO} for example) leads to
\begin{multline*}
  \frac{1}{2} \prts{ Q_i^d(t+T)^2 - Q_i^d(t)^2 } \leq Q_i^d(t) \prts{ \sum_{\tau=t}^{t+T-1} a_i^d(\tau) - Tb_i^d }\\+Q_i^d(t) \Bigg[ \sum_{j \in \set{P}_i^d} x_{ji}^d(t,T) - \sum_{j \in \set{H}_i^d} x_{ij}^d(t,T) \Bigg] + C_i^d,
\end{multline*}
where $C_i^d = \frac{ T^2 \delta^2 \prtr{ \abs{ \set{P}_i^d } + \abs{ \set{H}_i^d } + 2 } }{2}$.  Define a $T$-slot quadratic Lyapunov drift of queue backlogs \cite{Neely:SNO} as
\begin{equation*}
  \Delta(t, T) = \frac{1}{2} \prts{ \norm{ Q(t+T) }^2 - \norm{ Q(t) }^2 },
\end{equation*}
where $\norm{z}$ is the $l_2$-norm of vector $z$, i.e., $\norm{Q(t)}^2 = \sum_{i \in \set{S}}\sum_{d \in \set{D}} Q_i^d(t)^2$. It holds that
\begin{multline}
  \label{eq:DriftBound}
  \Delta(t, T) \leq \sum_{i \in \set{S}} \sum_{d \in \set{D}} \prtc{ C_i^d + Q_i^d(t) \prts{ \sum_{\tau=t}^{t+T-1} a_i^d(\tau) - Tb_i^d } } \\ + \sum_{i \in \set{S}} \sum_{d \in \set{D}} Q_i^d(t) \Bigg[ \sum_{j \in \set{P}_i^d} x_{ji}^d(t, T) - \sum_{j \in \set{H}_i^d} x_{ij}^d(t, T) \Bigg]
\end{multline}
The second line of the above equation can be rewritten as
\begin{multline}
  \label{eq:Rearrange}
\sum_{i \in \set{S}} \sum_{d \in \set{D}} Q_i^d(t) \Bigg[ \sum_{j \in \set{P}_i^d} x_{ji}^d(t, T) - \sum_{j \in \set{H}_i^d} x_{ij}^d(t, T) \Bigg] \\= \sum_{i \in \set{S}} \sum_{j \in \set{H}_i} \sum_{d \in \set{D}_{ij}} x_{ij}^d(t, T) \prts{ Q_j^d(t) - Q_i^d(t) },
\end{multline}
using the fact that $x_{ij}^d(t, T) = 0$ for every $d \in \set{D}\backslash\set{D}_{ij}$.

  Instead of minimizing the above expression, which leads to the MaxWeight algorithm, an state-dependent proximal term
\begin{equation*}
  \frac{k_{ij}(t)}{2} \prts{ x_{ij}^d(t, T) - \frac{ x_{ij}^d(t-T,T) }{ k_{ij}(t) } }^2 \quad \text{with}
\end{equation*}
\begin{equation*}
  k_{ij}(t) = \prts{ \frac{ 1 }{T c_{ij}} \sum_{d \in \set{D}_{ij}} \prts{ Q_i^d(t) - Q_j^d(t) + x_{ij}^d(t-T, T) }_+ }_{[1,K]}
\end{equation*}
 is introduced\footnote{The $x_{ij}^d(t-T, T)$ in the proximal term can be replaced by $z_{ij}^d(t) / \alpha$ for any $0 \leq z_{ij}^d(t) < \infty$ and $0 < \alpha < \infty$ to allow more control flexibility.}, where $\prts{z}_{\prts{1,K}} = \max[1, \min[ K, z ] ]$.  This proximal term is non-negative and is upper bounded by $K T^2 \delta^2$, so it holds from \eqref{eq:DriftBound} and \eqref{eq:Rearrange} that
\begin{align}
  \Delta(t, T)
  & \leq \sum_{i \in \set{S}} \sum_{d \in \set{D}} \prtc{ C_i^d + Q_i^d(t) \prts{ \sum_{\tau=t}^{t+T-1} a_i^d(\tau) - Tb_i^d } } \notag\\
  & \quad + \sum_{i \in \set{S}} \sum_{j \in \set{H}_i} \sum_{d \in \set{D}_{ij}} \Bigg\{ x_{ij}^d(t, T) \prts{ Q_j^d(t) - Q_i^d(t) } \notag\\
  & \quad + \frac{k_{ij}(t)}{2} \prts{ x_{ij}^d(t, T) - \frac{ x_{ij}^d(t-T,T) }{ k_{ij}(t) } }^2 \Bigg\}.   \label{eq:DriftMin}
\end{align}
Minimizing the right-hand-side of \eqref{eq:DriftMin} with respect to $\prtc{x_{ij}^d(t,T)}_{d \in \set{D}_{ij}}$ leads to problem \eqref{eq:MainProblem}.  Applying the result from Algorithm \ref{alg:Main}, which solves the minimization at reconfiguration time $t \in \set{T}$, yields the bound for any other $\prtc{ \hat{x}_{ij}^d(t, T) }_{d \in \set{D}_{ij}}$ satisfying constraints in problem \eqref{eq:MainProblem}:
\begin{align*}
  \Delta(t, T)
  & \leq \sum_{i \in \set{S}} \sum_{d \in \set{D}} \prtc{ C_i^d + Q_i^d(t) \prts{ \sum_{\tau=t}^{t+T-1} a_i^d(\tau) - Tb_i^d } } \\
  & \quad + \sum_{i \in \set{S}} \sum_{j \in \set{H}_i} \sum_{d \in \set{D}_{ij}} \Bigg\{ \hat{x}_{ij}^d(t, T) \prts{ Q_j^d(t) - Q_i^d(t) } \\
  & \quad + \frac{k_{ij}(t)}{2} \prts{ \hat{x}_{ij}^d(t, T) - \frac{ x_{ij}^d(t-T, T) }{ k_{ij}(t) } }^2 \Bigg\}
\end{align*}
Since the proximal term is bounded and policy $\prtc{ x_{ij}^{d\ast}(t, T) = \prtc{ x_{ij}^{d\ast}(\tau) }_{\tau = t }^{t+T-1} }_{d \in \set{D}_{ij}}$, constructed from the randomized policy in Assumption \ref{ass:Slater}, is one of those $\prtc{ \hat{x}_{ij}^d(t, T) }_{d \in \set{D}_{ij}}$, it follows that
\begin{align*}
  \Delta(t, T)
  & \leq \sum_{i \in \set{S}} \sum_{d \in \set{D}} \prtc{ C_i^d + Q_i^d(t) \prts{ \sum_{\tau=t}^{t+T-1} a_i^d(\tau) - Tb_i^d } } \\
  & \hspace{-3em}+ \sum_{i \in \set{S}} \sum_{j \in \set{H}_i} \sum_{d \in \set{D}_{ij}} \Bigg\{ x_{ij}^{d\ast}(t, T) \prts{ Q_j^d(t) - Q_i^d(t) } + K T^2 \delta^2 \Bigg\}
\end{align*}
Applying identity \eqref{eq:Rearrange}, taking expectation, and using the independent property of the randomized policy gives
\begin{multline*}
  \expect{ \Delta(t, T) } \leq \sum_{i \in \set{S}} \sum_{d \in \set{D}} \Bigg\{ D_i^d + \expect{ Q_i^d(t) } \times \\
  \sum_{\tau = t}^{t+T-1} \expect{ \sum_{j \in \set{P}_i^d} x_{ji}^{d\ast}(\tau) + a_i^d(\tau) - \sum_{j \in \set{H}_i^d} x_{ij}^{d\ast}(\tau) - b_i^d } \Bigg\},
\end{multline*}
where $D_i^d = C_i^d + K T^2 \delta^2\prtr{ \abs{\set{P}_i^d} + \abs{\set{H}_i^d} }$.  Assumption \ref{ass:Slater} implies for all $t \in \set{T}$ that
\begin{equation}
  \label{eq:DriftNeg}
  \frac{1}{2T} \expect{ \norm{ Q(t+T) }^2 - \norm{ Q(t) }^2 } \leq G_1 - \epsilon \sum_{i \in \set{S}} \sum_{d \in \set{D}} \expect{ Q_i^d(t) },
\end{equation}
where $G_1$ is defined in the theorem.

Queue dynamic \eqref{eq:Qid} and the upper bound $\delta$ imply that $Q_i^d(t + \tau) \leq Q_i^d( t ) + \tau \delta ( \abs{ \set{S} } + 1 )$ for any $\tau \in  {\mathbb{Z}} _+$ and $i \in \set{S}, d \in \set{D}$.  Summing for $\tau \in \prtc{0, 1, \dotsc, T-1}$ gives $\sum_{\tau = 0}^{T-1} Q_i^d(t+\tau) \leq T Q_i^d(t) + T (T - 1) \delta ( \abs{\set{S}} + 1 )/2$ and
\begin{equation*}
  Q_i^d(t) \geq \frac{1}{T} \sum_{\tau=0}^{T-1} Q_i^d(t+\tau) - G_2 \quad \text{for}~ t \in  {\mathbb{Z}} _+,
\end{equation*}
where $G_2$ is defined in the theorem.  Substituting the above into inequality \eqref{eq:DriftNeg} yields:
\begin{multline*}
  \label{eq:DriftNeg}
  \frac{1}{2T} \expect{ \norm{ Q(t+T) }^2 - \norm{ Q(t) }^2 } \leq G_1 + \epsilon G_2  \\ - \frac{\epsilon}{T} \sum_{\tau=0}^{T-1} \expect{ \norm{ Q(t+\tau) }_1 }  \quad\text{for}~ t \in \set{T}.
\end{multline*}
Telescope summation for $t \in \prtc{0, T, \dotsc, (N-1)T}$ gives:
\begin{multline*}

  \frac{1}{2T} \expect{ \norm{ Q(NT) }^2 - \norm{ Q(0) }^2 } \leq G_1 N + \epsilon G_2 N \\- \frac{\epsilon}{T} \sum_{n=0}^{N-1} \sum_{\tau=0}^{T-1} \expect{ \norm{ Q(nT+\tau) }_1 }.
\end{multline*}
Rearranging terms and taking supremum limit as $N \rightarrow \infty$ proves the theorem.
\end{proof}

\section{System Realization}
\label{sec:Implementation}

The previous section provides an ideal allocation of decision variables.  This section develops a heuristic improvement
that is easier to implement for practical switches.

\subsection{Approximation of Common Queues}
\label{sec:QueueApprox}
An SDN switch has output queues at each of its ports\cite{DeTail,DiffMax,OpenFlow}.  Those queues can be assigned to each commodity.  Let $Q_{ij}^d(t)$ denote the backlog of a queue for commodity $d$ at the port of switch $i$ connecting to switch $j$ at time $t$.  The queue backlog $Q_i^d(t)$ in Section \ref{sec:Queue} can be approximated by $\tilde{Q}_i^d(t) = \sum_{j \in \set{H}_i^d} Q_{ij}^d(t)$, for $i \in \set{S}, d \in \set{D}$.  It can be shown that this approximation becomes exact when the port's queues have never been emptied.  Note that OpenFlow \cite{OpenFlow} allows $2^{32}$ unique queues per port, but availability of those queues may depend on a switch.  This work encourages next generation switches to have a high number of available queues.

\subsection{Additional Packet Headers}
Three fields are appended into the IP header as IP options: \texttt{CommodityId}, \texttt{QueueInfo}, and \texttt{HashField}.  The \texttt{CommodityId} identifies the commodity of \texttt{QueueInfo} which stores the rounded value of exponential moving average of approximated queue backlog, $\tilde{Q}_j^d(t)$.  A packet from switch $j$ to switch $i$ carries queue information of a commodity, which is circularly selected from commodities in $\set{D}_{ij}$\footnote{This round-robin technique is inspired by CONGA \cite{CONGA}.  The concept can also be applied to VXLAN \cite{VXLAN}.}.  The \texttt{HashField} is used for traffic splitting and is explained in Section \ref{sec:Hashing}.

Once a packet with the additional headers from switch $j$ arrives to switch $i$, the contained queue information is extracted and stored in a local memory, which is denoted by $M_{ij}^d(t)$. This is the most recent queue information for commodity $d$ on link $(i,j)$ up to time $t$, where $d$ is the value in  \texttt{CommodityId}.  The header processing can be implemented by P4 \cite{P4}, NetFPGA \cite{NetFPGA}, or a custom ASIC.

\subsection{Weighted Fair Queueing}
Each port of switch $i$ connecting to switch $j \in \set{H}_i$ is configured with weighted fair queueing.  Let $r_{ij}^d(t, T)$ denote the measured number of commodity-$d$ packets transmitted from switch $i$ to switch $j$ during the interval $[t, t+T)$.  At every configuration time $t \in \set{T}$, the weight $w_{ij}^d(t)$ for the interval $[t,t+T)$ is
\begin{equation*}
  w_{ij}^d(t) = \max\prts{ 1, \tilde{Q}_i^d(t) - M_{ij}^d(t) + r_{ij}^d(t-T,T)/\alpha }, d \in \set{D}_{ij}

\end{equation*}
and $w_{ij}^d(t) = 0$ for $d \in \set{D}\backslash\set{D}_{ij}$.  Parameter $\alpha > 0$ is added to scale the magnitude of actual traffic to match a finite queue capacity.  From these weights, $w_{ij}^d(t)/\sum_{e \in \set{D}} w_{ij}^e(t)$ fraction of link capacity is given to commodity $d$, which corresponds to the intuition in equation \eqref{eq:WFQIntuition}.  Note that actual traffic  $r_{ij}^d(t-T,T)$ is used instead of $x_{ij}^d(t-T,T)$, because it is a better approximation under TCP traffic.

\subsection{Traffic Splitting by Hashing}
\label{sec:Hashing}
A sending rate of a TCP connection is reduced when out-of-order packets are received at a destination.  Hashing a packet to a next-hop switch based on \texttt{HashField} is implemented to reduce packet reordering.  The \texttt{HashField} is generated once for the entire packet life.  Packets from the same TCP connection have the same \texttt{HashField}, so they are hashed to the same path.  Reordering does not occur if a hash rule at each switch is the same for the entire TCP connection.  The hash rule is calculated as follows.  For each commodity $d \in \set{D}$, define $\prtc{ s_{ij}^d(t) }_{j \in \set{H}_i^d}$ as a solution of
\begin{align}
   {\text{Maximize}}  &\quad \min_{j \in \set{H}_i^d} \prtc{ Q_{ij}^d(t) - r_{ij}^d(t-T,T) + s_{ij}^d(t) } \label{eq:MaxMin}\\
     {\text{Subject to}}  &\quad \sum_{j \in \set{H}_i^d} s_{ij}^d(t) = \sum_{j \in \set{H}_i^d} r_{ij}^d(t-T,T) \notag\\
      & \quad s_{ij}^d(t) \in  {\mathbb{Z}} _+ \quad \text{for all}~ j \in \set{H}_i^d. \notag
\end{align}
This problem can be solved in polynomial time.  Let $s_{ij}^d(t) = 0$ for all $j \in \set{H}_i^d$.  Iteratively, $s_{ij}^d(t)$ is increased for a group of indices in $\Argmin_{j \in \set{H}_i^d} \prts{ Q_{ij}^d(t) - r_{ij}^d(t-T,T) + s_{ij}^d(t) }$ until the equality constraint is met\footnote{The process can be accelerated by increasing multiple values of $s_{ij}^d(t)$'s per iteration.}.  This process keeps increasing the $\min_{j \in \set{H}_i^d} \prtc{ Q_{ij}^d(t) - r_{ij}^d(t-T,T) + s_{ij}^d(t) }$.  The intuition of problem \eqref{eq:MaxMin} is that it attempts to equalize the backlog levels at all ports at end of the interval $[t,t+T)$ by using $r_{ij}^d(t-T,T)$ as an estimate of actual transmission $r_{ij}^d(t,T)$.  The attempt tries to make the approximation in Section \ref{sec:QueueApprox} exact.  The splitting ratio of the port connecting to switch $j$ is $f_{ij}^d(t) = s_{ij}^d(t) / \sum_{k \in \set{H}_i^d} s_{ik}^d(t)$ for $j \in \set{H}_i^d$.

\section{Simulations}
\label{sec:Simulations}

\subsection{Ideal Simulation}
Algorithm \ref{alg:Main} is simulated according to the system model in Section \ref{sec:Model}.  A switch uses a token bucket mechanism to ensure that transmission rate per interval satisfy constraint \eqref{eq:xijdT} after $x_{ij}^d(t, T)$ is determined.

\begin{figure}
  \centering
  \includegraphics[scale=1.0]{IdealLineNet.pdf}\vspace{-2mm}
  \caption{Line Network with $\set{S}=\prtc{1,2,3,4}, \set{D}=\prtc{1,2}$ and $\set{H}_1^d = \prtc{ 2 }, \set{H}_2^d = \prtc{ 3 }, \set{H}_3^d = \prtc{ 4 }$ for $d \in \set{D}$}\vspace{-4.5mm}
  \label{fig:IdealLineNet}
\end{figure}

A line network in Fig. \ref{fig:IdealLineNet} is simulated with the interval length $T = 100$ and the constant $K = 10$.   The network is simulated for $10^5$ slots.  The average backlogs shown in Table \ref{tlb:IdealLineNet} are calculated after Algorithm \ref{alg:Main} and MaxWeight converge.  The link-capacity sharing of Algorithm \ref{alg:Main} leads to small queue backlogs.  For scaling comparison, when $T = 1000$, the average backlogs of commodity 1 at switch 1 are respectively $23.94$ and $16005.63$ under Algorithm \ref{alg:Main} and MaxWeight.  In this simulation, the maximum value of $k_{ij}(t)$ for all $i \in \set{S}, j \in \set{H}_i, t \in \prtc{0, \dotsc, 10^5}$ is $1.732 < K$.

\begin{table}
  \caption{Average backlogs under Algorithm \ref{alg:Main} and MaxWeight}
  \label{tlb:IdealLineNet}
  \begin{tabular}{ c | r | r | r | r |}\cline{2-5}
    & \multicolumn{2}{ c | }{Commodity 1} & \multicolumn{2}{ c |}{Commodity 2} \\\cline{2-5}
    & Algorithm \ref{alg:Main} & MaxWeight & Algorithm \ref{alg:Main} & MaxWeight  \\\hline
    \multicolumn{1}{| c |}{Switch-1} & $14.88$ & $2598.19$ & $6.25$ & $213.45$ \\
    \multicolumn{1}{| c |}{Switch-2} &  $8.17$ & $1699.99$ & $2.35$ & $195.12$ \\
    \multicolumn{1}{| c |}{Switch-3} &  $7.52$ &  $700.01$ & $2.16$ & $199.51$ \\
    \multicolumn{1}{| c |}{Switch-4} &  $7.12$ &    $7.00$ & $2.00$ &   $2.00$ \\\hline
  \end{tabular}\vspace{-2.5mm}
\end{table}

A network in Fig. \ref{fig:IntraDC} is simulated with $T=100$ and $K=10$.  After $10^5$ slots, the average backlogs per queue (from all $124$ queues) are $34.23$ and $555.95$ under Algorithm \ref{alg:Main} and MaxWeight.  An event $k_{ij}(t) = K$ occurs $93.41\%$ of the times due to that the network operates near its capacity boundary.  Reducing the arrivals by $12\%$ ($24\%$) yields $20.68\%$ ($5.49\%$) of the times that $k_{ij}(t) = K$.  This suggests that Algorithm \ref{alg:PacketFilling} is rarely invoked, i.e., $k_{ij}(t) < K$, when a network does not operate near its capacity boundary.  In practice, TCP flows with congestion control are different from the i.i.d. arrivals, so Algorithm \ref{alg:PacketFilling} is not included in the heuristic algorithm.

\begin{figure}
  \centering
  \includegraphics[scale=1.0]{IntraDC.pdf}\vspace{-2mm}
  \caption{Intra datacenter network with $\set{S}=\prtc{1,2,\dotsc,14}, \set{D}=\prtc{1,2,\dotsc,9}$.  Each next-hop set $\set{H}_i^d$ contains next-hop switches with the shortest distance to commodity $d$, e.g., $\set{H}_1^8 = \prtc{9,10}, \set{H}_9^8 = \prtc{13,14}, \set{H}_{13}^8 = \prtc{11,12}, \set{H}_{11}^{8} = \prtc{8}, \set{H}_1^9 = \prtc{9,10} = \set{H}_1^e$ for $e \in \prtc{2,3,4}$.  Arrivals are $\expect{a_i^d(t)} = 2$ and $\expect{a_i^9(t)} = 1$ for $d,i \in \prtc{1,\dotsc,8}$; otherwise 0.  Departure rate is $b_i^d = 20$ if commodity $d$ connects to switch $i$; otherwise $0$.}\vspace{-4.5mm}
  \label{fig:IntraDC}
\end{figure}

\subsection{Network Simulator}
The heuristic in-network load-balancing algorithm in Section \ref{sec:Implementation} is simulated by OMNeT++ \cite{OMNet}.  All simulations share the following setting.  Capacity of each commodity queue at a switch port is $200$ packets.  For ECMP setting, a shared queue at a switch port has buffer capacity of $200\times\abs{\set{D}}$ packets, where $\set{D}$ is a set of commodities in a considered network.  Configuration interval is $T = 1$ms, and the scaling parameter is $\alpha = 5$.  The NewReno TCP from INET Framework \cite{INET} is adjusted for $10$Gbps and $40$Gbps link speeds.  Every TCP flow is randomly established during $[0s, 0.5s]$ and starts during $[1s, 1.01s]$.  Each flow transmits $1$MB of data.  Flow completion time (FCT) is measured as the performance metrics, which are also used in \cite{CONGA,DeTail}.  FCT is the duration of time to complete a flow, i.e., the time to send $1$MB of data.

A network without commodity 9 in Fig. \ref{fig:IntraDC} is simulated.  The speeds of level-1 links and level-2 links are respectively $10$Gbps and $40$Gbps.  $64$ flows are generated from a commodity to one another, and the total number of flows in the network is $3584$.  The FCTs under the heuristic algorithm and ECMP are shown in Fig. \ref{fig:IntraSymFCT}, and their variances are $5.8 \times 10^{-4}$ and $19.5 \times 10^{-4}$.  Unsurprisingly, they are comparable, since the topology is optimized for ECMP.  The FCTs under the heuristic algorithm has less variation, as the distribution of flows are more balance.  Note that the tail of FCTs is critical for interactive services \cite{DeTail}.

\begin{figure}
  \centering
  \includegraphics[scale=0.26]{HierarchicalSym.pdf}\vspace{-2mm}
  \caption{The FCTs from the network in Fig. \ref{fig:IntraDC} without commodity $9$}\vspace{-2mm}
  \label{fig:IntraSymFCT}
\end{figure}

A follow-up scenario is simulated when the link between switches $12$ and $14$ in Fig. \ref{fig:IntraDC} fails.  The FCTs of all flows are shown Fig. \ref{fig:IntraAsymFCT}.  The heuristic algorithm balances the flows better than ECMP.  Switches $9$ and $10$ hash more flows to switch $13$ than switch $14$, while ECMP hashes flows equally.

\begin{figure}
  \centering
  \includegraphics[scale=0.26]{HierarchicalAsym.pdf}\vspace{-2mm}
  \caption{The FCTs of all flows in the network in Fig. \ref{fig:IntraDC} where commodity $9$ is omitted and the link between switches $12$ and $14$ fails }\vspace{-4.5mm}
  \label{fig:IntraAsymFCT}
\end{figure}

A network in Fig. \ref{fig:Priority} illustrates the adaptiveness of the heuristic algorithm when some link capacity is taken away by priority flows.  The FCTs of all flows are shown in Fig. \ref{fig:PriorityFCT}.  The FCTs under the heuristic algorithm is more balance compared to the FCTs under ECMP, as switches $1$ and $2$ hash more flows to switch $4$ instead of equally hashing in ECMP case.  Note that if the priority flows begin shortly after $1.01$s, the same result is observed.

\begin{figure}
  \centering
  \includegraphics[scale=1.0]{SimulationTopology.pdf}\vspace{-2mm}
  \caption{A network with a priority flow in each direction and $600$ normal flows between commodities $1$ and $2$}
  \label{fig:Priority}
\end{figure}

A similar trend can be observed from scenarios with short flows ($10$KB of data per flow) when $T = 0.1$ms and $\alpha = 1$.

\begin{figure}
  \centering
  \includegraphics[scale=0.26]{Priority.pdf}\vspace{-2mm}
  \caption{The FCTs of normal flows between commodities $1$ and $2$ in Fig. \ref{fig:Priority}}\vspace{-4.5mm}
  \label{fig:PriorityFCT}
\end{figure}

\section{Conclusion}
\label{sec:Conclusion}
This paper showed that practical load-balancing in datacenter networks can be tackled by the concept of throughput optimality.
Our first algorithm is a novel variation of the MaxWeight concept that treats control plane and data plane timescales (useful for software defined networking),
allows link capacity sharing during a control plane interval, incorporates weighted fair queueing aspects,
and comes with a proof of throughput optimality.  Next, this algorithm was modified to include heuristic
improvements that allow easy operation with practical switch capabilities and works gracefully with TCP flows.
Ideal and OMNeT++ simulations show promising potential against existing MaxWeight and ECMP.

\bibliographystyle{IEEEtran}

redpajama_set_name: RedPajamaArXiv


text:
Q: Double click in selected item in treeview win32 api I want to send message about mouse double click to selected item in treeview in other application with winapi.

*

*How get the handle of selected item in treeview in other application?
p.s. In spy++ i get handle only for treeview.
Thank you!

A: This is best handled using UI Automation, which exposes access to UI elements, like TreeView controls and TreeView items, using COM interfaces:

*

*create an instance of the CUIAutomation COM object via CoCreateInstance() and get its IUIAutomation interface.

*call its ElementFromHandle() method to retrieve an IUIAutomationElement interface for the TreeView window.

*call its FindFirst() method to find the first selected item and get its IUIAutomationElement interface.

*call its GetCurrentPattern() method to get an IUnknown interface for the Invoke control pattern.

*query it for the IUIAutomationInvokePattern interface, and then call its Invoke() method
But, if you want to stick with just window messages, you can do the following:

*

*get the selected item using the TVM_GETNEXTITEM message, specifying TVGN_CARET for the wParam.

*get the rectangle of the item's text within the TreeView's client area using the TVM_GETITEMRECT message, specifying TRUE for its wParam.
However, this requires manually marshaling a RECT across process boundaries, as the RECT must exist in the same process that owns the TreeView.

*

*use GetWindowThreadProcessId() to get the ID of the process that owns the TreeView

*use OpenProcess() to get a HANDLE to the process ID, requesting PROCESS_VM_OPERATION and PROCESS_VM_READ access

*use VirtualAllocEx() to allocate a RECT in the process

*pass that allocated pointer in the lParam of TVM_GETITEMRECT

*use ReadProcessMemory() to read the RECT data

*free the memory with VirtualFreeEx()

*close the process handle with CloseHandle().

*send a WM_LBUTTONDBLCLK message to the TreeView window, specifying X,Y coordinates that are within the item text's rectangle.

A: I Know this is old, but I tried many ways to make it work in VB.net. I need to create 2 different structures for RECT because it was returning wrong values for the RECT position with Long parameters.
Here is the example, you can easily convert to C#
 Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
    Dim SelNodeRectangle As RECT = GetTreeViewSelectedNodeRECT(TreeViewPtr)
End Sub

Private Const TV_FIRST As Integer = &H1100
Private Const TVGN_CARET As Integer = &H9
Private Const TVM_GETNEXTITEM As Integer = (TV_FIRST + 10)
Private Const TVM_GETITEMRECT As Integer = (TV_FIRST + 4)

Private Const PROCESS_VM_OPERATION As Integer = &H8
Private Const PROCESS_VM_READ As Integer = &H10
Private Const PROCESS_VM_WRITE = (&H20)

Private Const PAGE_READWRITE As Long = &H4
Private Const MEM_COMMIT As Long = &H1000&
Private Const MEM_RELEASE As Long = &H8000&

Private Structure RECTPointer
    Public Left As IntPtr
End Structure

Private Structure RECT
    Public Left As Integer
    Public Top As Integer
    Public Right As Integer
    Public Bottom As Integer
End Structure

<Flags>
Public Enum AllocationType
    Commit = &H1000
    Reserve = &H2000
    Decommit = &H4000
    Release = &H8000
    Reset = &H80000
    Physical = &H400000
    TopDown = &H100000
    WriteWatch = &H200000
    LargePages = &H20000000
End Enum

Private Declare Function SendMessageA Lib "user32" (ByVal hWnd As IntPtr, ByVal Msg As Integer, ByVal wParam As Integer, ByVal lParam As Long) As IntPtr

Private Declare Function WriteProcessMemory Lib "kernel32" (ByVal hProcess As IntPtr, ByVal lpBaseAddress As IntPtr, ByRef buffer As RECTPointer, ByVal dwSize As Integer, ByVal lpNumberOfBytesWritten As IntPtr) As Boolean

Private Declare Function GetWindowThreadProcessId Lib "user32" (ByVal hwnd As IntPtr, ByRef lpdwProcessID As Integer) As Integer

Private Declare Function OpenProcess Lib "kernel32" (ByVal dwDesiredAccess As Integer, ByVal bInheritHandle As Boolean, ByVal dwProcessId As UInteger) As IntPtr

Private Declare Function VirtualAllocEx Lib "kernel32" (ByVal hProcess As IntPtr, ByVal lpAddress As IntPtr, ByVal dwSize As UInteger, ByVal flAllocationType As UInteger, ByVal flProtect As UInteger) As IntPtr

Private Declare Function ReadProcessMemory Lib "kernel32" (ByVal hProcess As Integer, ByVal lpBaseAddress As Long, ByVal lpBuffer As Long, ByVal nSize As Integer, ByRef lpNumberOfBytesWritten As Integer) As Integer

Private Declare Function VirtualFreeEx Lib "kernel32" (ByVal hProcess As IntPtr,
                  ByVal lpAddress As IntPtr,
                  ByVal dwSize As Integer,
                  ByVal dwFreeType As AllocationType) As Boolean

Private Declare Function CloseHandle Lib "kernel32" (ByVal hObject As IntPtr) As <Runtime.InteropServices.MarshalAs(Runtime.InteropServices.UnmanagedType.Bool)> Boolean

Private Function GetTreeViewSelectedNodeRECT(TreeViewPTR As IntPtr) As RECT

    Const dwBufferSize As Integer = 1024
    Dim dwProcessID As Integer
    Dim processHandle As IntPtr = IntPtr.Zero
    Dim remotePointerBuffer As IntPtr = IntPtr.Zero
    Dim localPointerBuffer As IntPtr = IntPtr.Zero
    Dim threadId As IntPtr = IntPtr.Zero

    localPointerBuffer = Runtime.InteropServices.Marshal.AllocHGlobal(dwBufferSize)

    threadId = GetWindowThreadProcessId(TreeViewPTR, dwProcessID)

    processHandle = OpenProcess(PROCESS_VM_OPERATION + PROCESS_VM_WRITE + PROCESS_VM_READ, False, dwProcessID)

    remotePointerBuffer = VirtualAllocEx(processHandle, IntPtr.Zero, dwBufferSize, MEM_COMMIT, PAGE_READWRITE)

    Dim bSuccess As Boolean
    Dim tvItem As New RECTPointer()

    Dim SelectedNodePTR As IntPtr = SendMessageA(TreeViewPTR, TVM_GETNEXTITEM, TVGN_CARET, 0)
    tvItem.Left = SelectedNodePTR

    bSuccess = WriteProcessMemory(processHandle, remotePointerBuffer, tvItem, Runtime.InteropServices.Marshal.SizeOf(GetType(RECTPointer)), IntPtr.Zero)
    If Not bSuccess Then
        Throw New SystemException("Fail writing to process memory!")
    End If

    SendMessageA(TreeViewPTR, TVM_GETITEMRECT, 0, remotePointerBuffer)

    bSuccess = ReadProcessMemory(processHandle, remotePointerBuffer, localPointerBuffer, dwBufferSize, IntPtr.Zero)

    If Not bSuccess Then
        Throw New SystemException("Fail reading from process memory!")
    End If

    Dim returnRECT As RECT = Runtime.InteropServices.Marshal.PtrToStructure(localPointerBuffer, GetType(RECT))

    If localPointerBuffer <> IntPtr.Zero Then
        Runtime.InteropServices.Marshal.FreeHGlobal(localPointerBuffer)
    End If
    If remotePointerBuffer <> IntPtr.Zero Then
        VirtualFreeEx(processHandle, remotePointerBuffer, 0, MEM_RELEASE)
    End If
    If processHandle <> IntPtr.Zero Then
        CloseHandle(processHandle)
    End If

    Return returnRECT
End Function

redpajama_set_name: RedPajamaStackExchange


text:
Questlove defends Rich Homie Quan's Biggie verse flub: "I blame us"
Hear him out; he has a point.
On Monday, VH1 aired its Hip Hop Honors special, and during Lil Kim's performance, she invited Rich Homie Quan to the stage to take the reins on the Notorious B.I.G.'s verse on "Get Money." But he ended up flubbing the lyrics so badly, his mistake turned into a meme and he felt the need to issue an apology.
But Questlove is playing devil's advocate and defending Quan, arguing that it's not Quan's fault he forgot the lyrics, but ours — well, "hip hop heads" — for not paying it forward and passing down the music of their prime to following generations. In the Instagram post, he also made note of America's "disposable" outlook on art and the way we mass consume entertainment.
A post shared by Questlove Froman, (@questlove) on Jul 11, 2016 at 11:43pm PDT
So, go on and make a playlist for someone in your life.

redpajama_set_name: RedPajamaCommonCrawl


text:
The Daily Dispatch: December 23, 1863., [Electronic resource]
The Averill raiders — a probability of their capture. The enemy in the Valley . Confederate States Congress. From General Lee 's army . From East Tennessee . Honor to a Virginian. A Boy Run over by Mrs. Lincoln 's carriage. article 8 How Lincoln 's message "Took" in New York. General Meade on his late movement. A New material in warfare. Rumored fight in North Carolina . Tried for murder. The retrograde movement. Great Yankee breach of promise Case. Lincoln 's pay. Movements of John Morgan . Self to the last. The last words of a good Woman. A Senator from Arkansas . House breaking Stolen Goods. Stealing a watch. Hustings Court . Paroled Yankee prisoners. The hiring season Going at large. The cow Case. Fined. The hospitals The river, The cage. From New Orleans. The Siege of Charleston . From East Tennessee . From the Rapidan . Runaway. 50 dollars reward. Two hundred dollars reward Piedmont Railroad , Superintendent's office, Danville , Dec. 15th, 1863. Confederates abroad. Public hiring of Negroes. For Sale. For Sale
Richmond Times Dispatch, December 1863
The Averill raiders — a probability of their capture.
The enemy in the Valley .
Confederate States Congress.
From General Lee 's army .
From East Tennessee .
Honor to a Virginian.
A Boy Run over by Mrs. Lincoln 's carriage.
How Lincoln 's message "Took" in New York.
General Meade on his late movement.
A New material in warfare.
Rumored fight in North Carolina .
Tried for murder.
The retrograde movement.
Great Yankee breach of promise Case.
Lincoln 's pay.
Movements of John Morgan .
Self to the last.
The last words of a good Woman.
A Senator from Arkansas .
Stolen Goods.
Stealing a watch.
Paroled Yankee prisoners.
The hiring season
Going at large.
The cow Case.
Fined.
The hospitals
The river,
The cage.
From New Orleans.
The Siege of Charleston .
From the Rapidan .
50 dollars reward.
Two hundred dollars reward
Piedmont Railroad , Superintendent's office, Danville , Dec. 15th, 1863.
Confederates abroad.
Public hiring of Negroes.
From General Lee's army.
[special Correspondence of the Richmond Dispatch.]
Army of Northern Virginia,
Dec. 21st, 1863.
It cannot be any longer a matter of concealment, I suppose, that Major General Early has been assigned to the command of the Valley Department of Virginia, with his headquarters at Staunton. In his absence the command of Gen. E.'s division will devolve upon Senior Brigadier Harry H. Hayes, of the Louisiana brigade. Gen. Early is peculiarly fitted for this position, and will doubtless discharge the duties of his new place with credit to himself and acceptability to the country.
Lt.-Col. Curley, Chief Quartermaster of this army, is now absent on a sixty days furlough. Col. C. is a most excellent and efficient officer, and has been constant, in season and our of season, in the discharge of the duties of his position. In his temporary absence Major Harmon, of Gen. Ewell's corps, is Acting Chief Quartermaster of the army, and Capt. A. M. Garber, of Staunton, assistant to Major Harmon, Chief Quartermaster of Ewell's corps, is now Acting Chief Quartermaster of that corps.
Congress, I am told, will, in all probability, at its present session, create the office of Provost Marshal General for this army. If such be its action, I trust I shall be pardoned for speaking favorably of Major Bridgford, of Richmond, who has been acting in that capacity for the last ten months. He will be a candidate for the post, and is recommended by Gens. Ewell, A. P. Hill, Rodes, Early, and other leading Generals and officers of the army.
The Chaplains of this army held a meeting at Orange C. H on Friday. Most interesting reports were made, which show a high state of religious feeling throughout the army. To that sainted hero, the immortal Jackson, is due much, if not all, of the present system by which the Chaplains in our army are enabled to do so much good. And, by the way, let me say, that my firm conviction is, that the great success of this army is due to the religious element which reaches every corner of it; whilst, on the other hand, I am very much disposed to fear, from what I have been told by officers who have served in the Army of Tennessee, that the lack of success of that army is due in a large measure to the want of religious influence upon the troops.
Dennis Driscoll, of Marmaduke Johnson's battery, from Richmond, Va., was executed at noon Friday by shooting, for the crime of desertion.--His wife came up and took charge of his body and took it to Richmond for interment. Another sad warning to those who leave their country and standard without permission. The time was when Gen. Lee was disposed to look leniently on this kind of conduct. That time has now passed, however, and I believe that every sentence will be rigidly carried into execution.
An amusing incident occurred yesterday at the Provost Marshal's office. Four Quakers were brought in as conscripts from Loudoun. They were ordered to fall in the ranks, in order to be marched to the command to which they were to be assigned. They refused, saying "We will not fall in, but will follow whither soever thou leadest."--A few persuasive arguments, however, in the shape of thrusts with bayonets, changed their opinions, and they fell in and marched off to camp.
There is a comparative full in all military operations, and but little likelihood of any active operations very shortly. X.
The Daily Dispatch: December 23, 1863. Richmond Dispatch. 2 pages. by Cowardin & Hammersley. Richmond. December 23, 1863. microfilm. Ann Arbor, Mi : Proquest. 1 microfilm reel ; 35 mm.
Orange Court House (Virginia, United States) (1)
Loudoun (Virginia, United States) (1)
Ewell (3)
Early (3)
Harmon (2)
Rodes (1)
Marmaduke Johnson (1)
A. P. Hill (1)
Harry H. Hayes (1)
A. M. Garber (1)
Dennis Driscoll (1)
Curley (1)
Bridgford (1)
December 21st, 1863 AD (1)
The Daily Dispatch: December 23, 1863., [Electronic resource] (this document)


1/20/18- Post Maria- The parking area and old trail to the Poza and Golondrinas area was washed away…it is currently a pond. Park on the road sides and now there is a trail on the north (beachside) of the road that goes past the ruined house to the beach Poza Mujeres. I assume you can carefully climb the rocks by the wall to get up to the path to Golondrinas…we did not try it.
The town of Manatí is about 45 minutes west of San Juan, and it boasts a number of beautiful beaches. Playa la Cueva de las Golondrinas and Poza del Mujeres are two beach areas in Manatí that are very close to each other, and that each have small and beautiful beaches. They require a little bit of walking (a couple of minutes) to get to, but you should do both the same day as they are both worth the effort.
These beach areas are located on the property of the Reserva Natural de Hacienda La Esperanza. They allow the public to use the paths to the beaches, but ask that we all keep it clean. They have a barrier up to keep vehicles out, so just walk around that and follow the path straight and to the right(closer to fence).
The path goes through a marshy area. Parts of it can be a little muddy, and sometimes under a couple inches of water. You will quickly get to a Y that has two possible paths. At the Y, walk to left for Playa la Cueva de las Golondrinas and to the right for Poza del Mujeres.
Both beaches have huge rock outcroppings that protect the cove beach from the rough Atlantic Ocean. You may be tempted to climb on the rocks. We do not recommend that. The rocks are sharp and there is the possibility of waves crashing over the rocks when the seas are rough. There are memorial markers up on the rocks for people who made bad choices and were not careful.
To get to this beach and "cave", you will be walking on a narrow path through bushes, so you may get a few scratches along the way. The path is hot and in the sun, but it is only a 5-10 minute walk. After you see a beach on your right, you will get to a Y in the path, stay to the right on the Y, and follow the path straight to Playa la Cueva de las Golondrinas .
Golondrinas is a small beach with a cove that is somewhat protected. There can be waves or currents at this beach, most likely in the winter. The feature here is the rock formation that is a "cave" (really more of an overhang), where goldondrinas (which is a bird like the barn swallow) use for nesting.
We explored this area, and checked out the beach. As a bonus, we found a couple nice pieces of sea glass.
If it is calm enough to enter the cave area, you can get a good look at the birds going in and out. I hear that there are some petroglyphs in this cave, though we did not see any. If you do venture into the cave, note that there are lots of little urchins, so wear water shoes!
The beach is nice, sand is soft, there are trees for shade, and the cave makes a nice barrier from the rough ocean. It's a nice place to spend some time. Be forewarned — I have heard that some people use this beach as a nudist beach … though that was not our experience either time we have been here.
You will notice other paths out from this beach or back at the Y's in the paths. These paths lead around the Nature Reserve, to other beaches and even the river. It's a neat place to explore, as long as you can find your way back to your car!
From Golondrinas, walk back to the original Y, and this time go to the right (which will be to your left if you're on the path coming from Golondrinas). In just a few yards you will get to the top of some steps and a concrete wall. You need to climb down the rock on the right to get to the Poza del Mujeres. This is a small strip of sand that separates a calmer pool (on the left) from the open ocean on the other side. A rock formation keeps the waves from crashing in, but be aware that there are sometimes strong currents. Sand is soft, but it is all open, there is no shade.
A few years ago, when we were inquiring about beaches in the area, we were told that this area can be sketchy — robberies and smash-n-grabs of cars. It appeared safe on our recent visits. So use your best judgement and take nothing of value with you to beach. Sometimes, there is an older guy there (with a machete) there that keeps an eye on the cars. Give him $1 or $2 "tip" … it's worth that much for some peace of mind.
There are no facilities at these beaches, so bring what you need for the day (water, sunscreen etc). And remember to take your trash out with you when you are finished.
Mar Chiquita is another beautiful beach that is very nearby. You could stop there also and visit three great beaches in one day.
From the San Juan area, take Route 22 west to exit 46, then take Route 686 north to Route 685. Take Route 685 west until a curve to the left … at that curve, make a sharp right, and then a quick left onto Road 6684. Follow that to the end, and park at the end of the street.
The pool is close to the cove. Standing looking at the cove, the mini pool will be to your left just a few steps to the water, protected by a wall from the ocean and currenrs. Careful, there are sea urchins.Also be careful because the car robberies (car battery) isn't an Urban Legend. It has happened and I was a frequent visitor.
I don't know exactly, but some of the rocks formations have pooled areas. I think it all depends on the tides if the rock formations will fill with water. If I were looking, I would walk west on the rocks from Mar Chiquita, or east from Punta Boquilla....looking really close on Google Maps, I can see some possible spots.
I keep seeing pictures on Instagram from a natural pool (it looks deep enough to swim/float in) that is somewhere between Poza Mujeres and Mar Chiquita. Most pictures appear to be locals. Any idea where this may be or how to get there?


We paddled this stretch of water in March 2018. The going was easy and the landscape beautiful, with peppermint trees overhanging the water and rock outcrops at intervals. We drove in to the waterfall car park on the rough 4WD track (an adventure on its own), entering from Pile Rd/Lennard Rd and kayaked up river to Honeymoon Pool, then returned with the slow current. There are quite a few fallen trees that need to be ported over/around but they were not difficult at that time. Definitely recommended if you like leisurely paddling and good scenery.


text:
Locals gear up for High School Finals Rodeo
Jake Newby
jnewby@daily-times.com
FARMINGTON — Four high school students from the Four Corners area will make their way to Gillette, Wyo., next week to compete in the 68th annual National High School Finals Rodeo.
Bloomfield's Levi Whitley, Aztec's Olivia Morehouse, Ignacio, Colo.'s Lauren Kelsey and Durango, Colo.'s Tyllor Ledford all qualified for the event, which runs from Sunday, July 17 through Saturday, July 23.
Students from 41 different states, as well as Canada and Australia, will make up the field of approximately 1,500 qualifying contestants.
For Kelsey, 17, and Morehouse, 15, it's not their first rodeo.
Kelsey, who will graduate from Keystone Online School in December, qualified in the reined cow horse division. The Ignacio resident is a natural, having qualified for the NHSFR twice since she picked up the sport just two years ago.
Riding a different horse than she rode in the event last year, Kelsey said she's feeling more confident and determined this time around.
"Last year, I went for the experience. I went on a horse I knew I wasn't probably going to make short go on," Kelsey said. "This year I'm going to place and win."
After cracking the top 50 in reined cow horse last year, Kelsey, and her horse, Centerfold, are aiming for a top-10 finish in 2016.
Morehouse will only be a sophomore when she begins classes at Dora Online High School this fall. But the former Piedra Vista student is far from a newcomer in barrel racing, which she's been doing for six years. She said she fell in love with the sport at age 8.
"I love the speed and the grittiness of it," she said. "It's just really intense and a good adrenaline rush."
Morehouse said her horse, Tink, has a lot of heart. The two made it to the National Junior High Finals Rodeo for barrels last year, so chemistry is on their side.
During the NJHFR, Morehouse ranked 17th in barrels after an excellent opening round, but she hit a barrel in the second round and fell out of contention. She said she thinks the work she's put in over the past year will pay off this week.
"I've spent some time with my trainers in Arizona fixing all the little things," Morehouse said. "I'm going in there expecting to not hit a barrel this time. Just go fast and ride how I ride."
Bloomfield's Whitley, 17, has overcome a pair of serious injuries to make his first NHSFR appearance.
In May 2015, the soon-to-be senior bull rider broke his hip during a high school rodeo when his bull bucked him off and stepped on him.
The timing of the injury couldn't have been worse for Whitley, who said he's been riding sheep since before he knew how to walk. The broken hip sidelined Whitley for two months, which forced him out of the state finals and disqualified him from a possible NHSFR berth.
Whitley didn't miss a beat when he returned for the 2015 fall season, where he won the bull riding event in Santa Rosa, his first rodeo back from injury.
But before this year's spring season, when his bull bucked him off during practice, Whitley landed awkwardly on his left arm and broke it, setting him back another two months. He said the second major injury wasn't as poorly timed.
"I made the last (rodeo) of the spring season, and then I made state finals," Whitley said. "So I got lucky I guess — I made it back in time to qualify."
Whitley said he's not about to squander his long-awaited opportunity to compete in the NHSFR.
"I better go over there and ride some bulls, I'll say that," he said. "I want to do well, for sure. It's good experience, and I'd like to go to college for rodeo, so I'm sure that would help out a lot if I did good out there."
Jake Newby covers sports for The Daily Times. He can be reached at 505-564-4577.


text:
The bizarre abduction of Patty Hearst
On February 4 1974, 19-year-old newspaper heiress Patricia Hearst was abducted from the apartment she shared with her fiancée in Berkeley, California.
Stephen Weed, Hearst's fiance, was beaten unconscious by the two abductors. Soon, a ransom demand came from the Symbionese Liberation Army (SLA), a radical activist group led by Donald DeFreeze.. But a few short months later, Patty Hearst appeared to be on their side.
On March 5, 1973, Donald DeFreeze escaped from prison. Radical penal activists and future SLA members Russell Little and William Wolfe took DeFreeze to Patricia Soltysik's house.The SLA was led by DeFreeze, who, after a prison acquaintance named Wheeler left, was the only African American in the group. By the time the group became active, most of the members of the tiny group were women, some of whom have, like Soltysik and her roommate Nancy Ling Perry, been described as in lesbian relationships. The members included William and Emily Harris and…
Previous Eric Clapton — Layla (Unplugged) (Live at Bray Studios, England, 16/01/1992) Next Clown Factor: Trying to Explain Our Idiotic and Self-Destructive Wind & Solar Obsession


Marble and granite can be considered as two of the most popular natural stones that people tend to use when they build new homes or work on home remodeling work. However, it has been identified that most of the people get confused when they are trying to select an option in between marble and granite.
Are granite and marble the same thing?
As the first thing, let's understand if a marble is the same as granite. Marble is not the same as granite. It is true that both of them are natural stones. However, you will be able to discover a variety of differences in between them.
Geologists use the term marble in order to refer to a metamorphosed limestone. When limestones deposited on the earth is being subjected to high pressure and temperature, marble is formed. In fact, the pressure and temperature can create changes in the overall texture of the rock. That's why you can find marble with enhanced beauty.
With that in mind, let's check what granite is. Granite can simply be defined as a granular igneous rock. It has got a phaneritic texture. The crystallization of magma, which takes place along with time, under the surface of the earth is responsible for creating granite.
What's better marble or granite?
To understand what's better, it is important for you to pay more attention to longevity and hardness. Granite can be considered as the stronger and harder natural stone out of these two options. In fact, granite has earned a reputation as one of the strongest natural stones available out there in the world. Granite is resistant to heat. Therefore, it has got the ability to withstand the heat that will get, while you prepare food. Due to this reason, you can think about getting granite tops to your kitchen without keeping any doubts in mind.
You should also keep in mind that marble is vulnerable towards the fading of color. In other words, a marble countertop will look dull after a short period of time. You will not be able to get back the shine of such a dull marble countertop. This can also be considered as an irreversible process. Therefore, you will have to face a lot of hassle in the long run.
What is more reactive to acids?
Both granite and marble come along with porous structures. However, marble has got some unique metamorphic attributes. Therefore, it is more porous when compared to granite. Due to this reason, marble tops can easily get stained from the liquid spills. In addition, fruits and other acidic content can create discoloration of your marble countertops.
When you compare the two options, you will notice that granite is more vulnerable towards the stains. However, an effective sealant should be kept on the surface to minimize the extent of the damage.
When you get a marble or a granite countertop, you tend to pay more attention towards the appearance as well. The appearance of marble and granite is different from each other. The color variation that you can find in granite would look freckling throughout. That's because it has got meddled stones. However, marble comes along with cream or grey colored veins, which run throughout. The impurities that you can find in marble, such as iron oxide, are responsible for creating these veins on the surface.
What are the applications of granite and marble?
Due to the durability factor, marble is widely being used for kitchen hallways and countertops. You will also be able to get granite to the high traffic areas that are located around your home. However, marble is recommended for the areas where there is less traffic, such as your bathroom. You will be able to get a unique bright look, which is really good on the areas that you use less frequently.
Both granite and marble tops are being installed by professional service providers. There is no significant variation in the cost that they charge for the installation. However, you should also keep in mind that high-end granite is way cheaper when compared to counterpart marble. The actual price you have to spend depends on the complexity of the job, quality of the stone and the style of the tiles.
You have to use a sealant on top of granite or a marble top in order to prevent etching and staining. However, you will need to apply the sealant on marble on a regular basis. In fact, professionals recommend you to go ahead with it at least two times in a year. But when it comes to granite, you have to worry about maintenance only for one time in two years.
Is granite and marble the same thing?marble and granitemarble vs graniteUnderstanding the difference between marble and graniteWhat is more reactive to acids?What's better marble or granite?


Everyone loves saving money and no one wants to give their hard earned money to anyone that is why promo codes and discounts are the biggest draws to online shopping. But it happens most of the time that either you do not land on the right website that can give you coupons and offers or the deals give has already expired. You keep on searching the right online deals on Google but you hardly find what you have looking for whole day. Secondly if you are a shopaholic you hardly care for saving as you are only bothered about the quality but not the price sometimes. I am not shopaholic, I am just helping the economy. This is the only excuse given by every shopping addict. But if you really want to help economy why not save some extra money for yourself as you are the part of this economy too. At yoursearch.in we have already done tie up with shopping biggies like Snapdeal, Flipkart, Amazon, Paytm, Myntra, Pizza Hut, Dominos, Shopclues, Freecharge, MakeMyTrip, eBay, Infibeam, Jabong, Zomato and many more. So can easily get all the latest and best deals and promo codes for your online shopping. Life is not perfect but your outfit can be! You were surfing internet and came across that shimmery black dress but you budget is not at all supporting you and you have just finished with your online shopping for the month now this is the time when these online coupons and offerswill come for your savior. Whether you are looking for massive saving or you do not want to miss any super saver deal online or you are a frequent online shopper you can avail Codes for online shopping for every kind of shopping. Surprise your beloved with some amazing gifts and yet keep your pocket happy. If you are planning to steal the hearts from your entirely different party look but you are running away from your dream dress just because of the price. Then you just do not have to sacrifice your will because of the fear of those dreary online bills. Everything is just sorted for you at yoursearch.in! Check out new deals and promo code for online shopping at yoursearch.in! Avail Up To huge Discount on Domestic Hotel Bookings for Various Bank Cards. Avail Flat 40% OFF + Additional 25% OFF on all Food Orders. Promo codes on footwear, clothing and accessories. Get best discounts on gadgets, electronic products, computer accessories, and various Smart phones. Get heavy discount on web hosting, Get cash back on Ola, avail heavy discounts on Bus tickets and many more. Enjoy the benefits and get more now! It is not about how much you make, It is about how much you save.


Thinly slice the lemons and toss them with sugar in a bowl. Transfer the lemon sugar mixture to a glass jar, seal it and let sit for 3 days on the counter. Roll the jar whenever you think of it.
After 3 days, add the lemon/sugar mixture to a sauce pan and bring to a simmer to dissolve the sugar. Strain the solids out using a cheesecloth.
Add strained syrup to a clean pint bottle or jar. You can top off with clean water, but this may thin the syrup out too much. You want a nice bitter bite to go along with the sweetness. If you want a thicker, stronger syrup, skip the water.
Fortify with rum to preserve (if you think necessary). Store in the fridge.
Makes about 1 pint of syrup.
If you have normal lemons and want to remove the wax, soak them in a solution of 1 quart of water and 1 oz of white vinegar for one minute. Then rinse with cold water and scrub dry with a paper towel.
Be sure to sanitize the implements you will be using. I have had better luck using the vinegar solution on normal lemons - this might be "sanitizing" the fruit.
If you leave a bunch of juice on your counter/cutting board as a result of the slicing, you can make up for this by squeezing 1/3 of a lemon in the lemon sugar mixture.


text:
Q: SQL code to get a certain activity a rank of 1? select whse,
    user_id,
    shift,
    tran_nbr,
    to_char(sched_start_date, 'HH24:MI:SS') as STRTUP,
    to_char(sched_start_date, 'MM/DD/YYYY') as DATE1,
    act_name,
    dept_code,
    num
from (
    select whse,
        user_id,
        shift,
        tran_nbr,
        sched_start_date,
        to_char(sched_start_date, 'MM/DD/YYYY'),
        actl_time,
        act_name,
        dept_Code,
        dense_RANK() over (
            partition by to_char(sched_start_date, 'MM/DD/YYYY'),
            user_id order by user_id,
                sched_start_date asc
            ) num
    from my_hdr
    ) X
where to_char(sched_start_date, 'MM/DD/YYYY HH24:MM:SS') between '02/09/2017 04:00:00' and '02/09/2017 10:00:00'
    and actl_time > '0'
    and ACT_NAME = 'JFSTRTUP'
order by whse,
    user_id,
    to_char(sched_start_date, 'HH24:MI:SS')

I am trying to return whenever JFSTRTUP is found to give it the rank (num) of '1'. Right now I get some JFSTRTUP where num <> 1
SQL Output:
WHSE USER_ID Shift  TRAN NBR    STRTUP      DATE1       ACT_NAME    DEPT_CODE  NUM
008   AMANY   1B    900197641   05:28:00    02/09/2017  JFSTRTUP    ORDERFILL   1
008   BTORR   1C    900197629   05:58:00    02/09/2017  JFSTRTUP    ORDERFILL   3
008   CROM    1B    900197644   05:29:00    02/09/2017  JFSTRTUP    ORDERFILL   1

I would like to have that second row return a 1 instead of 3.

A: Add this line before your ORDER BY clause, after the filter for JFSTRTUP:
AND num = 1

Note: You don't need to use user_id in the dense_rank order by clause - you are partitioning by user_id, so the rank will never take user_id into account. There is never a reason to use a value in both the partition by and order by clause of window functions.


Your website (the linking website) may not contain adult, racist or offensive material.
Your website (the linking website) may not infringe on copyright or trademark protections.
Copy and paste the code below to place our link on your site.
View our Links and Resources pages.


text:
Instrument-building Firms (1)
Open Section Music and Media (5)
Early Music Media (3)
Film, Television, and Video Game Music (1)
Organology (5)
Keyboard Instruments (3)
Instrument Maker (5)
Sound Artist (1)
Organology x
Music and Media x
Instrument Maker x
Dadson, Phil
Laurence Libin
(b Napier, New Zealand, May 14, 1946). Intermedia artist whose transdisciplinary practice includes video/sound work and installations, experimental instruments, graphic scores, and improvisation. He studied at Elam School of Fine Arts, Auckland (DipFA Hons, 1971) and the University of West Sydney, Nepean (MA Hons, 2000). Since the early 1970s his sound-based artworks have involved newly invented instruments. A member of the original Scratch Orchestra in London (1968–9), Dadson founded Scratch Orchestra (NZ) in 1970 and later From Scratch (1974–2004). A key part of From Scratch's development was instrument invention, from using found objects to making unique, custom-designed devices. Tunings evolved from randomly pitched sounds to 12-note and microtonal tunings, and just intonation. Central to this development were tuned percussion stations composed of rack-supported, four-tiered assemblies of PVC pipes, tuned-tongue bamboos and bells (in which parallel slots cut in the materials produce a vibrating tongue matching the resonant frequency of the open or closed tubes), and roto-tom drums, combined with special methods of playing. These percussion stations, along with other novel struck and spun acoustic instruments, produced the characteristic From Scratch sound. More recent instruments include the Zitherum (long-stringed instruments that are drummed and bowed), the metal-pronged Nundrum, the stroked RodBaschet, the gong tree, Foley-trays, the Water Cooler Drumkit, water bells, the Gloop-spring-string-drum family, the Sprong family, and other fanciful types....
Duo-Art
Gernsback [Gernsbacher], Hugo
Hugh Davies
(b Luxembourg, Aug 16, 1884; d New York, Aug 19, 1967). American writer, publisher, and inventor. In 1904 he emigrated to America, where in 1908 he founded the first of a series of radio magazines (including Radio-Craft) which he wrote for and edited. He later turned to science fiction magazines (from ...
Givelet, (Joseph) Armand
(M.Y. de P. )
(b Rheims, France, 1899; d La Varenne St-Hilaire, St-Maur-des-Fossés, France, Nov 9, 1963). French engineer and physicist. He was one of the pioneers of electronic instruments and especially of the electronic organ in the 1920s and early 1930s; some of his instruments were constructed in collaboration with the organ builder Edouard Eloi Coupleux. In 1917 or 1918, while working in the radio laboratory at the Eiffel Tower in Paris (at the same time as Maurice Martenot and Joseph Béthenod), Givelet first conceived the idea of electronic instruments based on the pitches that could be produced and varied by placing one's hand near or on certain components in a radio receiver. His idea for a dial-operated instrument (similar to the later Dynaphone and Ondium Péchadre) was not followed up until the mid-1920s, when he returned to studying the possibilities of electronic instruments.
Givelet's first completed electronic instrument, the monophonic keyboard ...
McMillen, Keith
Anne Beetem Acker
(b Bermuda, July 10, 1957). American audio engineer, musician, and owner of Keith McMillen Instruments, based in Berkeley, California. He received his BS in acoustics from the University of Illinois, where he also studied classical guitar and composition. In 1979 he founded Zeta Music, which designed and sold electric and electronic violins and basses. In 1992 he organized a research laboratory for Gibson Guitars. He developed a computerized composition, notation, and performance system, and also helped devise ZIPI, a MIDI-like music control language. At the Center for New Music and Audio Technologies at the University of California, Berkeley, he researched audio networking, synthesizers, and string instruments. In 1996 he became director of engineering for the audio processing and distributed music networks division of Harmon Kardon. In 1999 he founded Octiv, Inc., an Internet audio signal processing company, which produced the 'Volume Logic' plug-in for iTunes that allows digital audio remastering to improve the sound produced by computers and MP3 players....


You are currently converting cryptocurrency REQ to fiat currency KWD.
Calculator is operating with latest rate 1 REQ = 0.00663575 KWD.
Calculator is operating with latest rate 1 USD = 0.304417 KWD.
Refresh browser window to get the latest REQ/KWD rate.


text:
U2Songs.com
Adam Clayton Solo Listing
This is a listing of all of the tracks in the database which feature Adam Clayton working on a track outside of U2. It includes listings for studio songs, remixes and live recordings.
Adam Clayton Solo Songs
"Anarchy in the USA" (Studio Version) - Tito Larriva and the Million Dollar Hotel Band (featuring Adam & Larry) (03:37)
> The Million Dollar Hotel Soundtrack Album - Various Artists
> Million Dollar Hotel Promotional Release - Various Artists
"Born Again Savage" (Studio Version) - Little Steven (With Adam Clayton) (04:38)
> Born Again Savage Album - Little Steven
> Salvation Promotional Release - Little Steven
> RockNRoll Rebel – The Early Work Collection - Little Steven
"The Bucks of Oranmore" (Studio Version) - The Hughes' Band (03:24)
> Bringing it All Back Home Compilation Album - Various Artists
"Camouflage of Righteousness" (Edit) - Little Steven (featuring Adam Clayton) (04:36)
> Camouflage of Righteousness (Edit) Digital Single - Little Steven
"Camouflage of Righteousness" (Short Edit) - Little Steven (featuring Adam Clayton) (01:19)
> Born Again Savage (D.A.M. Promo) Promotional Release - Little Steven
"Camouflage of Righteousness" (Studio Version) - Little Steven (With Adam Clayton) (05:02)
"Do They Know It's Christmas?" (12-Inch Mix) - Band Aid (with Bono and Adam Clayton) (06:18)
> Do They Know it's Christmas? Single - Band Aid
> Band Aid Special / Rock "Now" 12 Hits ! Compilation Album - Various Artists
"Do They Know It's Christmas?" (Flexitone Version) - Band Aid (with Bono and Adam) (03:46)
> Do They Know it's Christmas: The Story of the Official Band Aid Video Video - Various Artists
"Do They Know it's Christmas?" (Single Version - Edit) - Band Aid (with Bono and Adam) (03:47)
> Do They Know it's Christmas? Single - Band Aid 20
> If I Was: The Very Best of Midge Ure and Ultravox Compilation Album - Ure, Midge
"Do They Know it's Christmas?" (Single Version) - Band Aid (with Bono and Adam) (03:54)
> Live Aid Video Release - Various Artists
> The Greatest Xmas Songs Compilation Album - Various Artists
"Don't Forget About Me" (Alternative Studio Version) - Nanci Griffith (Featuring Adam Clayton and Larry Mullen) (03:00)
> Flyer Promotional Release - Griffith, Nanci
"Don't Forget About Me" (Studio Version) - Nanci Griffith (with Larry and Adam) (02:59)
> Flyer Album - Griffith, Nanci
"Face of God" (Short Edit) - Little Steven (featuring Adam Clayton) (01:43)
"Face of God" (Studio Version) - Little Steven (With Adam Clayton) (07:38)
"Feed the World" (Studio Version) - Band Aid (with Bono and Adam Clayton) (04:18)
"Flesheater" (Studio Version) - Little Steven (with Adam Clayton) (06:08)
"GoldenEye" (Club Edit) - Tina Turner (04:26)
> GoldenEye Single - Turner, Tina
> GoldenEye Promotional Release - Turner, Tina
"Guns, Drugs, and Gasoline" (Short Edit) - Little Steven (featuring Adam Clayton) (01:25)
"Guns, Drugs, and Gasoline" (Studio Version) - Little Steven (With Adam Clayton) (04:59)
"Jolie Louise" (Studio Version) - Daniel Lanois (featuring Adam Clayton and Larry Mullen) (02:42)
> Acadie Album - Lanois, Daniel
> Jolie Louise Single - Lanois, Daniel
> Northern Exposure Soundtrack Album - Various Artists
"Larry O'gaff's Set" (Studio Version) - Sharon Shannon with Donal Lunny and Adam Clayton (03:12)
> The Winkles Tapes 1989 Album - Shannon, Sharon
"Lust for Englightenment" (Studio Version) - Little Steven (With Adam Clayton) (08:38)
"The Marguerita Suite" (Studio Version) - Sharon Shannon (featuring Adam Clayton) (05:53)
> Sharon Shannon Album - Shannon, Sharon
> Spellbound Compilation Album - Shannon, Sharon
> The Heart of Ireland Compilation Album - Various Artists
"Mission: Impossible Theme (Mission Accomplished)" (Cut the Red Not the Blue) - Adam Clayton and Larry Mullen (04:35)
> Theme from Mission: Impossible Single - Clayton, Adam and Larry Mullen
> Theme from Mission: Impossible Promotional Release - Clayton, Adam and Larry Mullen
"Mission: Impossible Theme (Mission Accomplished)" (Dave Clarke Remix) - Adam Clayton and Larry Mullen (04:31)
"Mission: Impossible Theme (Mission Accomplished)" (Studio Version) - Adam Clayton and Larry Mullen (03:05)
> Mission: Impossible Soundtrack Album - Various Artists
"On Grafton Street" (Alternative Studio Version) - Nanci Griffith (featuring Adam Clayton and Larry Mullen) (03:57)
"On Grafton Street" (Studio Version) - Nanci Griffith (featuring Larry Mullen and Adam Clayton) (04:02)
> On Grafton Street Promotional Release - Griffith, Nanci
> Merry Little Christmas Promotional Release - Various
"One" (Live from Washington, Jan. 20, 1993) - Automatic Baby (Michael Stipe, Mike Mills, Adam Clayton & Larry Mullen) (04:21)
> Amazing Grace Compilation Album - Various Artists
> 99X Live X Volume 2 - One Life Compilation Album - Various Artists
> Just Passin' Thru Compilation Album - Various Artists
> Childline Compilation Album - Various Artists
> KZON Collectibles Volume 4 Album - Various Artists
"Organize" (Studio Version) - Little Steven (featuring Adam Clayton) (02:13)
"Saint Francis" (Studio Version) - Little Steven (featuring Adam Clayton) (08:19)
"Salvation" (Short Edit) - Little Steven (featuring Adam Clayton) (01:27)
"Salvation" (Studio Version) - Little Steven (featuring Adam Clayton) (05:10)
"Still Water" (Radio Version) - Daniel Lanois (featuring Adam Clayton and Larry Mullen) (04:24)
> Still Water Promotional Release - Lanois, Daniel
"Still Water" (Studio Version) - Daniel Lanois (featuring Adam Clayton and Larry Mullen) (04:29)
> The Maker Single - Lanois, Daniel
"Theme from Mission: Impossible" (Guru Mix) - Larry Mullen and Adam Clayton (03:26)
"Theme from Mission: Impossible" (Junior's Hard Dub I) - Larry Mullen and Adam Clayton (07:46)
"Theme from Mission: Impossible" (Junior's Hard Dub 2) - Larry Mullen and Adam Clayton (07:25)
"Theme from Mission: Impossible" (Junior's Hard Mix Edit) - Larry Mullen and Adam Clayton (04:13)
"Theme from Mission: Impossible" (Junior's Hard Mix) - Larry Mullen and Adam Clayton (08:53)
"Theme from Mission: Impossible" (Junior's Tribal Beats) - Larry Mullen and Adam Clayton (03:17)
"Theme from Mission: Impossible" (Studio Version) - Larry Mullen and Adam Clayton (03:28)
"These Days in an Open Book" (Studio Version) - Nanci Griffith (featuring Adam Clayton and Larry Mullen) (03:33)
> These Days in an Open Book Promotional Release - Griffith, Nanci
"Tomorrow" (Common Ground Version) - Bono and Adam Clayton (04:36)
> October Remastered Album (2008 Master) - U2
> Common Ground Compilation Album - Various Artists
> 1977 - 1984 / 1980 - 1983 Album Collection - U2
> Common Ground Sampler Promotional Release - Various Artists
"Tongues of Angels" (Studio Version) - Little Steven (featuring Adam Clayton) (08:19)
"Two Shots of Happy, One Shot of Sad" (Studio Version - Nancy Sinatra) - Nancy Sinatra (featuring Larry Mullen and Adam Clayton) (04:25)
> Nancy Sinatra Album - Sinatra, Nancy
> Burnin' Down the Spark Single - Sinatra, Nancy
Explore U2 Studio Songs:
Songs Categories:
Songs Covered by U2
Songs Covered (Solo)
Instrumental Songs
The Edge Solo Songs
Larry Mullen Solo Songs
Explore U2 Studio Songs
Recent Updated Lyrics
Where Is the Love? / One (Live from New York, Oct. 30, 2009)
Sgt. Pepper's Lonely Hearts Club Band (Live from London, Jul. 2, 2005)
Sgt. Pepper's Lonely Hearts Club Band (Live from London, Jul. 2, 2005 - Live 8 Video)
Springhill Mining Disaster (Live from Dublin, Mar. 16, 1987)
Springhill Mining Disaster (Live from East Rutherford NJ, May 15, 1987)
U2 News
U2 Discography
U2 Lyrics
U2 Shows
U2 History
U2 Videos
U2 Demos
About U2Songs
U2Songs Forum
Site © 1995-2022 U2 Songs. Site formerly known as U2Wanderer.org. All rights reserved. All images are copyright their respective designers. This website is an informational resource for private use only and is not affiliated with U2, their management company, their record label or any related bodies. The information presented within these pages is accurate to the best of our knowledge but is based upon information provided by other fans, research into individual items and several books, and U2 Songs takes no responsibility for any problems resulting from use of the material as presented within. The discography, news and video entries are copyright U2Songs and should not be reused in any form without permission, all images in the discography are scanned / generated by U2Songs from original sources and also should not be used without permission. Lyrics are transcribed as heard and are presented here under a provisional license by Universal Music, granted in 2005. Page rendered in: 1.6809 seconds