Transport Layer

While it does not describe a transport protocol per se, Chapter 4 describes methods to transparently render TCP usable in a wireless mesh network. It contains a paper by Steluta Gheorghiu, Alberto Lopez Toledo and Pablo Rodriguez: Multipath TCP with Network Coding for Wireless Mesh Networks published in Proceedings of IEEE ICC 2010 - Wireless and Mobile Networking Symposium (ICC10 WNS). The authors propose two network coding-based protocols interposed between the transport and the network layer which improve the performance of TCP ows in a wireless mesh network. Evaluations via simulations of the proposed methods and comparison with proposed techniques show that signicant gains are to be obtained by coupling TCP with either of the two proposed underlying network coding protocols. The work presented in this chapter allows legacy applications relying on TCP to run in such wireless mesh networks without changes to higher layers of the networking stack. Chapters 5 and 6 propose distributed ow control protocol designs for streaming applications. In such applications a source node wishes to convey information at a xed rate to a set of receiver nodes. While there may exist many rate allocations enabling this goal, the proposed protocols aim at nding a rate allocation minimizing a certain network cost function. Chapter 5 presents the paper of Amin Jafarian, Sang Hyun Lee, Sriram Vishwanath and Christina Fragouli: Distributed Rate Allocation for Network-Coded Systems shown in the IEEE International Workshop on Wireless Network Coding (WiNC 2009). The authors consider a specic bipartite topology motivated by a real world wireless network setting. For such a topology two Belief Propagation techniques are used to compute the optimal rate allocation minimizing a linear cost function in a distributed fashion. The two proposed algorithms are evaluated via simulation. Chapter 6 is an extended version of the paper of Dan-Cristian Tomozei and Laurent Massouli : Flow e Control for Cost-Efcient Peer-to-Peer Streaming published in the Proceedings of IEEE INFOCOM 2010, San Diego, March 2010. This work analyzes a streaming session in a xed-topology peer-to-peer network for which the source wishes to transmit data (at a xed rate) to all the other nodes in the network while minimizing a global generic network cost function. A particular cost function considered is network congestion. The authors propose a simple local rate adaptation rule and analyze its properties. By considering a uid scaling, it is shown that when network coding is used, the system does not deviate from the optimal rate allocation. Furthermore, for a particular class of network cost functions (i.e. separable functions) it is shown that the size of the backlogs remains bounded. Evaluations support a stronger conjecture, namely convergence to the optimum. The scheme can used either directly as a transport protocol, or it can be implemented above the transport layer.

A diagram of the destination is depicted in Fig. 2.5. The demodulation (Dem.) at the destination is a symbolby-symbol, soft-input soft-output, maximum a posteriori detector whose aim is to calculate from the channel output yD,l,m the LLR L(tl,m ) about the timing tl,m. Although it would be possible to calculate LLRs about the code-bits cS,l and cR,l1 as well, we do not calculate them at this point. Initially, the destination assumes that the the relay has decoded successfully. Then, the possible inputs to the demodulator are noisy versions of the entries in the alphabet SD = (hSD SS ) (hRD SR ) whereas hSD SS represents the multiplication of each element in SS with hSD. The elements in hSD SS correspond to tl,m = 1 (source transmitted the m-th symbol of the l-th block), the elements in hRD SR correspond to tl,m = 0 (relay transmitted the m-th symbol of the l-th blocks). The demodulator has to exploit the knowledge about the probability p(tl,m = 1) = MS /M as a priori knowledge. Fig. 2.6 depicts the probability density function p( {yD,l,m }) of the real part of yD,l,m for SS = SR = {1, 1}, 2 = 0.02, MS = 6000, MR = 4000, hSD = 1 and hRD = 23.52/2. The demodulation uses the alphabet SD = {hRD , hSD , hSD , hRD } with the labels depicted in Fig. 2.6.

p( {yD,l,m })

tl,m = 1 tl,m = 1 cS,l,m = 0 cS,l,m = 1 tl,m = 0 tl,m = 0 cR,l1,m = 0 cR,l1,m = 1

hSD 0 {yD,l,m }

Figure 2.6: Probability density function of the real part of yD,l,m for an example.

Punct.

fCW (dT,l )
Figure 2.7: Constant-Weight Encoder with weight MS and fCW (dT,l ) = [11(MS MR )

dT,l ].

The LLRs L(tl ) = [L(tl,1 ) L(tl,2 ). L(tl,M )] are channel decoded by the MS -weight decoder to obtain the hard estimate cT,l1 and the soft estimate L(cT,l1 ) of the code-bits cT,l1. We will explain the MS -weight decoder in Section 2.4. The hard estimate cT,l1 is reencoded with the MS -weight encoder in order to obtain the timing l of the current block. This allows the timing functionality R-Timing to split yD,l into the symbols t ySD,l received from the source and the symbols yRD,l received from the relay. If the m-th element of l is a 1 , t the timing functionality adds the m-th element of yD,l to ySD,l. If the m-th element of l is a 0 , the timing t functionality adds the m-th element of yD,l to yRD,l. The values in ySD,l are demodulated to LLRs L(cS,l ) about cS,l assuming the alphabet SS. The values in yRD,l are demodulated to LLRs L(cR,l1 ) about cR,l1 assuming the alphabet SR. The calculation of L(cS,l ) and L(cR,l1 ) after the decision l on the timing is advantageous t compared to the calculation in the initial demodulation with SD in the simulations in Section 2.5. The LLRs L(cS,l ) are stored and used for the next block. The LLRs L(cS,l1 ) (obtained during the previous block) about cS,l1 , the LLRs L(cR,l1 ) about cR,l1 and the LLRs L(cT,l1 ) about cT,l1 are fed into a turbo decoder to obtain the estimate ul1 about ul1. If the CRC indicates that ul1 is wrong, the destination tries to decode with the previously described procedure under the assumption that the relay has decoded wrongly, i.e. SD = (hSD SS ) (0). If the timing is initialized, the destination knows the timing and demodulates the transmission of source and relay separately. It is crucial for the system performance that the estimate l of the timing is correct at the destination, because t only one bit error in l can disturb the bit allocation to and the position within L(cS,l ) and L(cR,l1 ). In t further work it could be investigated, if differential encoding of cS,l and cR,l could help to decrease the error propagation due to errors in l. t

2.4 Design of Constant-Weight Code
Fig. 2.7 depicts the constant-weight encoder used in the system. Our constant-weight code requires that NT MR MS is fullled. The block of NT code-bits cT,l is turbo encoded and punctured. The puncturing outputs the block of MR bits dT,l. Then, the timing tl+1 for the block l + 1 is calculated to tl+1 =

L(tl+1 )

L(dT,l ) Turbo gCW () Dec.

L(cT,l HE cT,l

S +M Figure 2.8: Constant-Weight Decoder with gCW (t) = tMS MR +1 tMS +1 R. M MS
fCW (dT,l ) = [11(MS MR ) dT,l dT,l ] whereas dT,l denotes the bit-inverted version of dT,l. The output tl+1 of the constant-weight encoder has always the Hamming-weight MS. This ensures that the source transmits MS symbols per block. The constant-weight ensuring function fCW () is motivated by previous work in [11]. The rate of the constant-weight code is RCW = NT /(MS + MR ). Our code can be interpreted as a serial concatenation of a turbo code with a pulse-position modulation [12, 13]. Fig. 2.8 depicts the constant-weight decoder used in the previously described system. First, the LLRs L(tl+1 ) about tl+1 are transformed to LLRs L(dT,l ) = gCW (L(tl+1 )) about dT,l whereas the function gCW is dened as gCW (t) = tMS MR +1 tMS +MR. The notation tj denotes a vector of length (j i + 1) with all elements of i MS +1 MS the vector t with indices from i to j. The substraction in gCW () corresponds to the inverse repetition in fCW () and allows to increase the accuracy of L(dT,l ). Then, a turbo decoder outputs the hard estimate (HE) cT,l and the soft estimate L(cT,l ) of the code-bits cT,l.

2.5 Simulation Results

We use a Monte-Carlo simulation to measure the bit error rate (BER) and packet error rate (PER) at the destination for the following parameters: K = 5000, MS = 6000, MR = 4000, LS = LR = 1, SS = SR = {1, 1}, NT = 1333. The rate of the constant-weight code is given by RCW = NT /(MS + MR ) = 2/15. Fig. 2.9 depicts the error rates of the proposed system (Relay with timing) dependent on the signal-to-noise ratio (SNR) SD = |hSD |2 / 2 on the source-destination link. The relay is assumed on half-distance between source and destination and the path-loss exponent is assumed to be 3.52 [14]. Therefore, the coefcients hSR and hRD are given by hSR = hRD = hSD 23.52/2. The turbo codes in the encoder and in the MS -weight encoder are chosen to be the UMTS turbo code [15] and 16 CRC bits are used. All turbo decoders perform 15 iterations. The puncturing is done similar as in the UMTS standard [15]. However, we choose the puncturing such that the subsets cS,l , cR,l and cT,l are disjoint and such that cS,l contains all systematic bits. Fig. 2.9 depicts the performance of two reference systems. The rst reference system is a distributed turbo code without information transfer through timing (Relay without timing). The timing of the relay-transmit phases is always xed to tl = tI. The destination knows the timing a priori and demodulates the transmission of source and relay separately. This reference system does not transfer code-bits with the help of timing (NT = 0) and loses more than 2.2 dB compared to the proposed system with timing at a PER of 102. The other parameters are the same as in the proposed system. The second reference system is a point-to-point communication without relay (No Relay). The source is allowed to use all channel uses (MS = 10000 BPSK symbols). The turbo code is the same as in the proposed system. This system loses more than 5.6 dB compared to the proposed system with timing at a PER of 102. The comparison is fair, because the three systems work with the same spectral efciency and transmit MS + MR = 10000 BPSK symbols for each packet with K = 5000 information bits. For a very low SD , the BER of the proposed system is 1/2 due to timing errors at the destination and the resulting error propagation. In order to benchmark the turbo coding scheme, we depict in Fig. 2.9 the information-theoretic SNR-limits for a reliable communication with rate K/(MS + MR ) = 1/2. The limits for the two relay systems can be obtained from the expression for the achievable decode-and-forward rate given in [6, Eq. (12)] and in [8, Eq.

Chapter 3

NCRAWL - An Intersession Network Coding Architecture
Intersession Network Coding (NC) enables the local processing and mixing of independent information ows. It is possible to combine ows belonging to different sessions at different wireless routers [1618] in order to increase the available capacity. Intersession network coding is envisioned to provide signicant performance benets in wireless networks, due to reduction of transmissions, fairness improvement, efcient content distribution with direct implications on end-to-end peering, and robustness to network topology variations [18, 19]. However, all these advantages are evident only when: (a) routers (which perform the encoding operations) are able to quickly identify efcient coding opportunities that increase the network coding gain; (b) packet decoders are able to correctly decipher the encoded packets and acknowledge the decoded packets that they receive in diverse channel conditions; and (c) the overheads imposed due to the inclusion of additional packet headers [18] as well as packet processing operations [20] are kept minimal. Note also that while NC can increase the router throughput in random-access networks [21], prior studies have shown that network coding should be tightly combined with link-level scheduling, in order to yield signicant performance benets [17, 22]. All these factors should be taken into account when designing and developing practical network coding algorithms and systems. NCRAWL is a congurable OSI layer 2 protocol that abstracts the common low-level packet processing operations which are related to network coding, and exports a scheduler plugin that can be used to implement network coding link-level scheduling algorithms.
3.1 Rationale behind the NCRAWL design
Although intersession NC can theoretically offer unprecedented wireless router capacity benets [16,17], effecting these benets in real systems is by no means an easy task. In the rst approach towards practical NC [18], the authors were able to show throughput benets at low rates but also discovered a series of complexity issues arising in such implementations. Following implementations such as [2325], focused on the complexity of the problem. Nevertheless, despite the simplicity of the idea, no experimental implementation exists to-date that delivers the expected throughput gains in practical multi-rate wireless deployments using high channel rates. The reason for this is a series of architectural design considerations that introduce important computational overhead which in turn overloads the routers CPU and cause performance degradation. More specically, a common, overhead intensive design decision has to do with the process of correctly and timely identifying the key holders (i.e., the neighbors that have successfully overheard recent packets-keys,

Diamond topology

For the diamond topology, we use two-ray ground for the propagation model and we vary the loss probability per link and the number of relays doing the forward. In Fig. 4.3 and Fig. 4.4 we plot the average throughput in kbps on the y-axis with the probability of having a successful transmission on each link, psuccess , on the x-axis. When using plain multi-path with UDP, the throughput is the same independent of the number of paths that are used (see Fig. 4.3(a)). This is due to the fact that trafc is basically split equally among the paths and losses or packets arriving out-of-order at destination do not inuence the throughput at the sender. Unfortunately, this is not the case for TCP. As you can see from Fig. 4.4(a), there are small differences in throughput when multiple paths are used, but overall the performance is signicantly affected by the losses in the network.

N1 N2 N3 N0 N4 N5 N6

(a) diamond topology with 6 overlapping paths (b) the Roofnet topology, consisting of 92 nodes deployed over an area of approximately 3 km2
Figure 4.2: Topologies used for simulations - diamond topology (left) and the Roofnet topology (right) For overhearing we observe similar results for both UDP ( Fig. 4.3(b)) and TCP ( Fig. 4.4(b)), that is, as psuccess decreases, using more relays improves the total throughput. When the losses are low, multiple paths achieve a lower throughput than single path, because intermediate relays forward all the packets that they receive, thus bandwidth is wasted with duplicates. Moreover, the maximum throughput that TCP gets is lower than that obtained with UDP, because packets arrive at destination out-of-order and for TCP, this will result in duplicate acks and unnecessary retransmissions. In the case of credit assignment and reassignment, notice from Fig. 4.3(c) that for UDP multiple paths yield a clear improvement over single path. This is due to the fact that no more duplicates arrive at the receiver and also some of the losses are recovered when credits are reassigned. As an example, two paths is up to 67% better than one path. For TCP though, credit reassignment has a negative effect ( Fig. 4.4(c)), and even if more packets arrive at destination, they are out-of-order and do not help at all. With hop-by-hop retransmissions we obtain the best results for both UDP and TCP because all the losses are recovered with high probability 1 (1 psuccess )nretx , where nretx is the number of retransmissions and is equal to 5. For UDP ( Fig. 4.3(d)), the higher the number of paths, the better, although the benet is not proportional to the number of paths. For example, the throughput obtained with two paths improves over that with one path by up to 44%. For TCP ( Fig. 4.4(d)), using two paths achieves an improvement of up to 40% over single path. If more paths are used, then the interference between nodes increases and the throughput decreases.

4: 5: 6: 7:

remove P0 from output bufferf add id(P0 ) in ph list add in P0 s header qf k and (skl , tkl ) for each upstream neighbor, Nl send P0
Load balancing and congestion control
When multiple paths are used in parallel, one important decision is how much of the trafc needs to be sent through each path. Consider the example in Fig. 4.1. If each node A, B and C would generate a linear combination every time it receives a packet from source, it would result in an explosion of the rate, with the destination receiving several packets that are not innovative. Also, when multiple paths are used, the likelihood of ows traversing the same set of links increases, so one must use a mechanism to ensure fairness among those ows. To address these issues, we use a hybrid credit-based scheme to balance the trafc among the different paths. The idea is to associate a credit with each packet that is sent in the network. This credit is further assigned to one of the downstream neighbors, that is chosen according to the criterium described next. The idea of credits is not new, and several other proposals have used it previously. With MORE [40] and MC2 [43], credits are computed by source, transfered to downstream nodes and consumed at destination. In our case, we use a hybrid credit scheme, as follows. First, credits are generated at source and transfered to the forwarders, as the schemes mentioned above do. Second, credits can be generated by intermediate nodes as well, which differentiates our approach from the existing ones. This second part enables each node to compute locally and distributedly the rate that it needs to send to recover the losses. In order to select a forwarder for a packet, we use backpressure [38]. The idea behind the backpressure is that a node is allowed to send packets to his neighbor as long as the neighbor is less congested. The level of congestion is given by the size of the queue, i.e. the more packets are queueing at a node, the more congested the node is. Our algorithm works as follows. Each node Nk keeps the following information for each of the ows that it forwards: an output queue, output bufferi , i = 1 : nf , where nf is the number of ows that node Nk forwards; the queue sizes of its next hops for each ow, qij , i = 1 : nf , j = 1 : nh , where nh is the number of next hops that Nk has for ow i. Whenever the node has the opportunity to transmit a packet in the wireless medium, it rst selects the ow for which to forward a packet, as the one for which it queues the highest number of packets (see Algorithm 2). After the ow is selected, Nk chooses the forwarder to be the node from the list of his neighbors for ow f the one with shortest output queue, as long as the backpressure condition holds. Next, Nk removes the rst packet from the output bufferf and it adds the packet id in ph , the list of packets sent to Nh. It adds in the header of the packet the size of its own queue, qf k for backpressure computation and for each of its upstream neighbors Nl , the id of the last received packet, skl , and the total number of received packets, tkl , for loss estimation. Finally, Nk sends the packet.

Algorithm 4 Coding at relays for MPTCP. This algorithm is used by a relay Nk when it receives a linear combination of ow f from neighbor Nl. m represents the number of packets from the coding bufferf. Coefcients ci are randomly chosen from a nite eld.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:
receive coded packet LCr of ow f skl = id(LCr ); tkl tkl + 1 if LCr is innovative then store LCr in the coding bufferf if receive credit associated to LCr then generate LCj = m ci LCi i=1 store LCj in output bufferf end if else drop LCr end if
Algorithm 5 On-the-y decoding for MPTCP. Destination Nd decodes native packets as soon as it receives independent linear combinations.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17:
receive coded packet LCk of ow f from neighbor Nl sdl = id(LCk ); tdl tdl + 1 if LCk is innovative then store LCk in the coding bufferf if a packet can be decoded then deliver the decoded packet to the TCP layer else if feedback algorithm is enabled then send an ack to the sender end if end if if current generation is decoded then send a packet with ag generation decoded end if else drop packet LCk end if
Algorithm 6 Generation decoded for MPTCP. This algorithm is used by a node when it receives a control packet with ag generation decoded for ow f. m represents the number of packets from the coding bufferf and n is the size of the generation. Coefcients ci are randomly chosen from a nite eld.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
receive a control packet with ag generation decoded for ow f ush coding bufferf and output bufferf if size(pending bufferf ) > 0 then counter 0 while size(pending bufferf ) > 0 || counter < n do remove the rst packet Pl from the pending bufferf add Pl to the coding bufferf generate LCk = m ci Pi i=1 store LCk in output bufferf counter counter + 1 end while end if
when it receives a credit. Note that a linear combination of already coded packets is also a linear combination of the original packets. MPTCP Receiver. When destination Nd receives a linear combination of ow f , it updates the id of the last received packet and the total number of received packets for the sender. Next, it stores the coded packet only if it is linear independent with all the packets received previously. Since we use triangular matrix coding, then the destination decodes a native packet, if possible, and passes it up to the TCP layer (see Algorithm 5). If no native packet can be decoded and the feedback mechanism for TCP is enabled, then destination acknowledges the reception of the current packet to the source. When all the packets from the current generation are decoded, the destination sends a control packet with a generation decoded ag. Whenever a node receives this control packet, it ushes both its coding bufferf and output bufferf. If the node is the source of the ow f , then it starts to process the packets stored in the pending bufferf , if any, and to send linear combinations for the next generation ( Algorithm 6). CoMP Algorithm 7 Online coding at source for CoMP. If a data packet arrives, the source stores it and generates a linear combination. m represents the size of the coding bufferf. The coefcients ci are randomly chosen from GF (216 ). If it receives a TCP ACK, the source removes the oldest packet from the coding bufferf.

1: 2: 3: 4: 5: 6: 7: 8: 9:
receive packet Pk of ow f if Pk is DATA packet then store packet in the coding bufferf generate LCk = m ci Pi i=1 store LCk in the output bufferf else Pk is TCP ACK remove P0 from coding bufferf end if
The CoMP protocol is based on the online coding approach presented in Section 4.3.1. For each ow f , every node keeps a coding bufferf and an output bufferf. The coding bufferf contains packets that the node uses to generate linear combinations. The source stores here native, uncoded packets, while the other nodes
store linear combinations. The output bufferf contains coded packets that will be sent in the network. Packets are removed from the output bufferf whenever the node has the possibility to transmit a packet. In this case, a node rst runs Algorithm 2 to select a ow f and a forwarder Nh. After that, the node removes the rst packet from the output bufferf , it updates the statistics for node Nh and it sends the packet. Algorithm 8 Online coding at relays for CoMP. The relay Nk receives a packet of ow f from neighbor Nl. m represents the size of the coding bufferf. The coefcients ci are chosen from GF (216 ) at random.
CoMP Sender. When a native packet of ow f is produced, the source stores it in the coding bufferf. Note that source performs online coding, which means that it generates a new linear combination every time it receives a new packet. To generate a coded packet, the source mixes all the packets from the coding bufferf and stores the resulting linear combination in the output bufferf (see Algorithm 7). When the source receives a TCP ACK for ow f , it removes the oldest packet from the coding bufferf , thus sliding the coding window. Algorithm 9 Online decoding at destination for CoMP. The destination Nd receives a linear combination.
receive coded packet LCk of ow f from neighbor Nl sdl = id(LCk ); tdl tdl + 1 if LCk is innovative then store LCk in the coding bufferf if a packet can be decoded then deliver the decoded packet to the TCP layer else send an ack to the sender end if else drop packet LCk end if
CoMP Relays. When receiving a coded packet from ow f , an intermediate node Nk rst updates the state for the upstream neighbor Nl that sent it. The updated information is the id of the last received packet skl , and the total number of received packets, tkl. Next, if the coded packet is innovative, Nk stores it in the coding bufferf , otherwise Nk drops it (see Algorithm 8). A relay generates and forwards a linear combination when it receives a credit. Note that a linear combination of coded packets is also a linear combination of the original packets. CoMP Receiver. When destination Nd receives a linear combination of ow f , it updates the id of the last received packet and the total number of received packets for the sender. Next, it stores the coded packet only if it is linear independent with all the packets received previously. Since the source is coding online, then the

(l) (l)

of the message MVa Ui (x), this message takes such form as (5.1). Moreover, the message mUi Va (x) is calculated by taking the product of probability density of XUi transferred from other constraint nodes in the sense of a prior knowledge. These update rules form Algorithm I. Although Algorithm I basically uses the probability densities as its messages, the algorithm can be simplied by a further assumption that the message distribution be Gaussian-like with a (minor) change in the objective function to:

x2 i. U

(5.14)
Then, the corresponding unconstrained optimization problem is given as

n {xUk }

x2 k U

(5.15)

Note that the local potential term for XUi is a Gaussian function, and the constraint function basically involves a series of convolution operations followed by the calculation of Gaussian integral. Therefore, we can approximate messages transferred along the network to be Gaussian functions. Since, as mentioned in the previous section, the mean and the variance are sufcient statistics of Gaussian probability density under the approximation, the same procedure as Algorithm I can be performed by transferring only two parameters. Hence, Algorithm II is given as such.

5.6 Complexity analysis

Here, we discuss the complexity of the proposed algorithms. Let L denote the number of points for the FFT operation to perform a convolution operation of two message distributions. For Algorithm I, a single edge processing at the constraint node update for a degree-dc constraint node involves dc 2 convolutions and one integration, which are computationally equivalent to dc 1 FFTs and dc 3 products of message distributions. Since there are mdc edges connected to constraint nodes, the complexity for constraint node updates is O(md2 L log L). Likewise, the complexity for variable node updates of degree dv is O(nd2 L). Therefore, the v c overall complexity of Algorithm I is O(nd2 L log L). v For Algorithm II, the constraint node updates are simple because all operations can be replaced by addition operations. Since one integration and 2(dc 2) additions are required for a single edge processing, the number of addition required for constraint node updates is O(mdc (dc + L)). If we use a lookup table for Q(x; , 2 ), the number of additions reduces to O(md2 ). Since variable node updates involve direct calculation of the rst c and second moment of message distributions, the overall number of multiplications and additions are O(nd2 L) v and O(ndv L), respectively. Therefore, the overall complexity of Algorithm II is O(nd2 L). v

5.7 Conclusion

In this work, we presented two distributed algorithms for the rate allocation problem over a coded multicast network. We provided simulation results which illustrates the convergence rate and correctness of these algorithms.

6.3 Explicit and Implicit Primal-Dual
Consider a peer-to-peer network described by a graph G = ({s} V, L) with an achievable capacity region |L| C R+ (i.e. only rate allocations c C are feasible). The source s wishes to convey information (a stream of bytes) at a rate to the set of receivers V. We dene cij as the rate at which information is transferred along edge (i, j) L. Also consider an increasing strictly convex differentiable function (c) describing the global
cost incurred from transferring information on edges at rates given by c R+. We wish to minimize cost while still achieving a transfer rate of at each of the receivers in V. More formally, denote by Ts = {{s} S : S V} the set of non-trivial cuts containing the source node and by c(S, S) for S Ts the transmission rate through cut S, namely i,j:i|S j cij. The notation i|S j signies i S, j S and (i, j) L (i.e. cut S separates node i from node j or, equivalently, link (i, j) crosses cut S) and will be used frequently in the remainder of the paper. We state the following optimization problem which describes our goal: minimize (c) over c subject to c(S, S) , (6.1) S Ts. (6.2)
The cut constraint (6.2) is clearly necessary. It is also sufcient when network coding is allowed, in view of the founding result in network coding, identifying feasible multicast rates with the min-min-cut [62]. In the present context where all nodes are receivers, the feasible broadcast rate is again given by the min-min-cut condition, as follows from Edmonds theorem [63]. We suppose the capacity constraints are included in the cost function. Thus, a further condition the cost function must satisfy is (c) = + for c C. Denote the marginal cost of a link by p (c) = c (c). We will / also refer to this marginal cost as the price of link. For example take a network with R physical links and L overlay links. The underlay routing can be expressed as a routing matrix H {0, 1}RL , for which Hr = if overlay link uses physical link r, otherwise.
Denote by r (c) = Cr Hr , c the spare capacity on link r. A possible choice of cost function is network congestion, i.e. setting link prices equal to the observed packet delay. Such prices can be modeled as p (c) =

r:Hr =1

1. r (c)
Furthermore, ISPs wishing to avoid overloading sensitive links can dene physical link weights wr which increase additively the price of an overlay link: pISP (c) =

1 r (c)

The corresponding global cost function writes as:

ISP (c) =

wr Hr , c

r (c). Cr

Let us now characterize the optimum rates minimizing some generic. For problem (6.16.2) the Lagrangian is: L(c, ) = (c) + S c(S, S) , (6.4)
where the {S }STs are Lagrange multipliers associated with the cut constraints (6.2). Taking the partial derivative with respect to cij for some (i, j) L, we obtain that the optimum values (c , ) satisfy pij (c ) =

S:i|S j

Motivated by the previous remarks, we propose Implicit-Primal-Dual (IPD), a distributed rate control algorithm, for which we use a continuous rate adaptation method, the Implicit-Primal rule (as opposed to the Explicit-Primal (6.8)): + (6.11) cij (t) = [X+ij (t) pij (c(t))]cij (t) , for all (i, j) L. Here is a gain factor and is a conversion factor (it can be considered as price per useful packet). Further intuition behind this rule is as follows: the more a node i has to offer to its neighbor j, the more it will increase the rate cij ; at the same time, the higher the price of the link, the lower the rate cij will become. As we previously stressed, the Implicit-Dual equations describe the backlog size evolution and follow implicitly from the packet transfer strategy. In the next Sections we consider a classic packet forwarding network implementing the Random Useful (RU) scheme and a coded packet network implementing Random Linear Coding (RLC). We use a uid scaling of the system to deduce the governing Implicit Dual rule for both cases. We nd that IPD deviates from the optimum operation point under RU due to redundant transmissions over congested links. We show that RLC solves this problem and that the global optimum is a stationary point for IPD in this setting.

6.4 A First Approach

Consider the case in which the source generates a sequence of packets it wishes to deliver to the receivers in V at rate. We use the notations Pi , ZS , X+ij introduced in the previous Section 6.3. Nodes are assumed to have the knowledge of which packets are present at their one-hop neighbors. Consider the following transmission strategy: For each link (i, j) L, with rate cij (t) node i picks a packet uniformly at random from the set Pi (t) \ Pj (t) of packets useful for j and sends it along the link. Such a transmission occurs if and only if X+ij (t) = |Pi (t) \ Pj (t)| > 0. This strategy is called the Random Useful strategy. In [65] the authors prove that Random Useful (RU) is rate-optimal for a xed rate allocation c0. That is, when using RU if the value of the min-min-cut of the edge-capacitated graph (G, c0 ) with source node s is greater than , then rate is attained at each receiver. Starting from this rate optimal strategy, we wish to characterize the behavior of the proposed IPD rate control scheme (6.11). We model the system as follows: We assume for simplicity that packets are generated at the source at instants of a Poisson process of rate. We also assume that packet transfers on links L are triggered at instants of Poisson processes of time-varying rates c (t). The process pair ((c (t)) L , (ZS (t))STs ) is jointly Markovian with a continuous and a discrete component. Packet generation at the source increments Z{s} (at rate ). Along any edge (i, j) L there are X+ij packets available for transfer from node i to node j. From (6.10) it follows that for every packet selected for transfer along edge (i, j) (according to the RU strategy) there exists a unique set S Ts with i|S j, such that the selected packet belongs to the backlog at S. Such a packet transfer will decrement the corresponding ZS and increment ZSj simultaneously, and will occur with probability XZS. +ij Moreover, since the process dictating transfers is Poisson with rate cij , the simultaneous updates for ZS and ZSj will be performed at rate cij XZS , provided that X+ij > 0. +ij In what follows we describe the behavior of the system at a uid time scale. Based on this scaling, we show on an example that IPD is suboptimal. We analyze the reason for which IPD deviates from the optimum point and we propose a coding-based approach.

Table 6.1: Relative Mean Error an execution instance for each of the cases, for a time span of 20, 000 time units. We notice that in this setting, when ruling out the Idealized Coding case, the best performance is obtained by performing coding over F28. The generation size parameter has the anticipated impact on performance: the higher the generation size, the closer we are to the optimum. It is surprising that IPD in a Random Useful setting, while proven suboptimal in Section 6.4, gives similar performance to IPD in a Generation Coding setting for F28 and outperforms it when the eld size is equal to 2. Indeed, while for F28 virtually all transfers are linearly independent combinations, for F2 the number of transfered linearly dependent combinations becomes non-negligible. In Figure 6.5 we plot

1.5 Rate

1 Time

1.8 x 10

Figure 6.5: Wasted rate on the 3 physical links by transferring linear dependent combinations when a eld of size 2 is used the wasted bandwidth on each of the 3 physical links for a generation size of 150 packets for a coding eld

6.7 Conclusion

In this paper we proposed a fully distributed cost-efcient rate control scheme for live streaming peer-to-peer systems. We formulated our goal as an optimization problem having a convex cost function. Using the backlog sizes as approximations for the dual variables we introduced Implicit-Primal-Dual, our rate control scheme. We managed to show the advantage of using Network Coding over a classic Random Useful approach. Namely, while the two have the same feasible capacity region in the considered setting, we proved that for Random Linear Coding IPD has a xed point at the global optimum while this does not hold in the Random Useful setting. Our numerical evaluations showed that IPD still performs reasonably well for Random Useful packet networks.

Chapter 7

Conclusion
Investigating network coding benets in wireless and peer-to-peer networks has revealed the need for novel protocols. In this document we gave an overview of the status of the design of such protocols within the N-Crave project. We presented protocols showing substantial improvement over state-of-the-art techniques at various layers of the networking stack. The encouraging ndings motivate additional exploration of network coding protocols. Further steps to be taken in the next stage of the project involve physical deployment and evaluation of protocols in more practical settings. Each of the presented works gives several directions for future extensions which will be examined. Several questions have been raised in the previous document D2.1 and are yet to be fully addressed. Is inter-session coding relevant in wired networks? Can intra- and inter-session coding bring cumulative gains when used together? Answers to such questions have proven hard to nd. The impact of performing non-linear coding on rate remains unknown to this day.

Bibliography

[1] A. Stefanov and E. Erkip. Cooperative Coding for Wireless Networks. IEEE Trans. on Communications, 52(9):14701476, Sep. 2004. [2] T. E. Hunter and A. Nosratinia. Diversity through Coded Cooperation. IEEE Trans. on Wireless Communications, 5(2):283289, Feb. 2006. [3] B. Zhao and M. C. Valenti. Distributed Turbo Coded Diversity for the Relay Channel. Electronic Letters, 39:786787, May 2003. [4] M. R. Souryal and B. R. Vojcic. Cooperative Turbo Coding with Time-Varying Rayleigh Fading Channels. In IEEE International Conf. on Communications (ICC), pages 356360, June 2004. [5] Z. Zhang and T. Duman. Capacity Approaching Turbo Coding for Half Duplex Relaying. In International Symposium on Information Theory (ISIT), pages 18881892, Adelaide, Australia, Sept. 2005. [6] G. Kramer. Models and Theory for Relay Channels with Receive Constraints. In Allerton Conf. on Communication, Control, and Computing, Sept. 2004. [7] G. Kramer. Communication Strategies and Coding for Relaying. Wireless Communications, Vol. 143 of the IMA Volumens in Mathematics and its Applications:163175, 2007. [8] S. Vijayakumaran, T. F. Wong, and T. M. Lok. Capacity of the Degraded Half-Duplex Relay Channel, August 2007. http://arxiv.org/abs/cs/07082270. [9] T. Lutz, C. Hausl, and R. Koetter. Coding Strategies for Noise-Free Relay Cascades with Half-Duplex Constraint. In International Symposium on Information Theory (ISIT), Toronto, Canada, July 2008. [10] V. Anantharam and S. Verd. Bits Through Queues. IEEE Trans. on Inform. Theory, 42(1):418, Jan. u 1996. [11] D. E. Knuth. Efcient Balanced Codes. IEEE Trans. on Inform. Theory, 32(1):5153, 1986. [12] K. Kiasaleh. Turbo-Coded Optical PPM Communication Systems. IEEE Journal of Lightwave Technology, 16(1):1826, 1998. [13] J. Hamkins and M. Srinivasan. Turbo Codes for APD-Detected PPM. In Allerton Conf. on Communication, Control, and Computing, Sept. 1998. [14] H. Holma and A. Toskala. WCDMA for UMTS. Wiley, Inc., 2001. [15] European Telecommunications Standards Institute (ETSI); Universal Mobile Telecommunications System (UMTS); Multiplexing and Channel Coding (FDD). 3GPP TS 25.212 V3.4.0, Oct. 2000. 73

BIBLIOGRAPHY

[16] R. Ahlswede, Ning Cai, S.-Y.R. Li, and R.W. Yeung. Network information ow. Information Theory, IEEE Transactions on, 46(4):12041216, 2000. [17] P. Chaporkar and A. Proutiere. Adaptive Network Coding and Scheduling for Maximizing Throughput in Wireless Networks. In ACM MOBICOM, 2007. [18] S. Katti, H. Rahul, W. Hu, D. Katabi, M. M dard, and J. Crowcroft. XORs in The Air: Practical Wireless e Network Coding. In ACM SIGCOMM, 2006. [19] C. Fragouli, D. Katabi, A. Markopoulou, M. M dard, and H. Rahul. Wireless network coding: Opportue nities & Challenges. In IEEE Military Communications Conference 2007, October 2007. [20] Kim, J., et al. A Memory Copy Reduction Scheme for Networked Multimedia Service in Linux Kernel. In EurAsia-ICT, LNCS 2510, 2002. [21] ANSI/IEEE 802.11-Standard. 1999 edition. [22] B. Scheuermann, W. Hu, and J. Crowcroft. Near-Optimal Co-ordinated Coding in Wireless Multihop Networks. In ACM CONEXT, 2007. [23] Eric Rozner, Anand Padmanabha Iyer, Yogita Mehta, Lili Qiu, and Mansoor Jafry. ER: Efcient Retransmission Scheme for Wireless LANs. In ACM CONEXT, 2007. [24] S. Rayanchu, S. Sen, J. Wu, S. Banerjee, and S. Sengupta. Loss-Aware Network Coding for Unicast Wireless Sessions: Design, Implementation, and Performance Evaluation. In ACM SIGMETRICS, 2008. [25] S. Chachulski, M. Jennings, S. Katti, and Dina Katabi. Trading Structure for Randomness in Wireless Opportunistic Routing. In ACM SIGCOMM, 2007. [26] Raychaudhuri, D., et al. Overview of the ORBIT Radio Grid Testbed for Evaluation of Next-Generation Wireless Network Protocols. In IEEE WCNC, 2005. [27] D. S. J. De Couto, D. Aguayo, J. Bicket, and R. Morris. A High Throughput Path Metric for MultiHop Wireless Routing. In ACM MOBICOM, 2003. [28] Click Modular Router. http://read.cs.ucla.edu/click/. [29] Roofnet. http://pdos.csail.mit.edu/roofnet/doku.php. [30] SDBM hash function. http://www.partow.net/hashfunctions. [31] R. Draves, J. Padhye, and B.Zill. Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks. In ACM MOBICOM, 2004. [32] Ian F. Akyildiz, Xudong Wang, and Weilin Wang. Wireless mesh networks: a survey. Computer Networks, 47(4):445487, March 2005. [33] H. Balakrishnan, V.N. Padmanabhan, S. Seshan, and R.H. Katz. A comparison of mechanisms for improving TCP performance over wireless links. Networking, IEEE/ACM Transactions on, 5(6):756769, 1997. [34] Youngseok Lee, Ilkyu Park, and Yanghee Choi. Improving TCP performance in multipath packet forwarding networks. JOURNAL OF COMMUNICATIONS AND NETWORKS, 4:148157, 2002.

Pitkin County Department Equipment 10 Year Plan

Yrs Life

BOCC & COMMUNITY RELATIONS
RECORDING SONY DVD CAMERA TOTAL BOCC

4,000 4,000

19,932 19,932

19,932 4,000 23,932

TV TOTAL COMMUNITY RELATIONS

1,000 1,000

G:\budget\2010\original\R&R\Dept'l Replacement\ 2010 BOCC & Com Rel dept equip 6-30-09.xls
CLERK & RECORDER AND ELECTIONS
(1) COMPUTER / PLAT SCAN 2006 Recording/Imaging Sys (3) COMPUTERS Recording/Imaging Sys (3) FUJITSU PRINTERS 2007 Recording/Imaging Sys (2) COMPUTERS Recording/Imaging Sys (3) FUJITSU SCANNERS 2007 Recording/Imaging Sys (8) DYMO LABEL PRINTERS 2007 Recording/Imaging Sys HP LASERJET 8000N 1999 Recording/Imaging Sys READER/PRINTER (MINOLTA MS 6000) /03 READER/PRINTER MINOLTA /05 microfilm copier XEROX 8525 LARGE DOCUMENT SCANNER-PR Recording/Imaging (State s ONCORE RECORDING SYSTEM 2007 Recording/Imaging Sys (5) ONCORE RECORDING SERVERS Recording/Imaging Sys RECORDER/TRANSCRIB SONY (BM-88) /94 Jeanette/BOCC equipmt TASCOM CO-RW402 CD RECORDER /2008 Jeanette/BOCC equipmt SONY SOUND SYSTEM /97 Jeanette/BOCC equipmt PLAT CABINETS

2,000 4,000 900

2,000 4,000

2,4,000 2,700

2,700 1,000 2,700

2,700 1,000

1,000 7,800 8,400
26,000 25,2,700 3,300 3,300 3,300 3,300 3,500 3,2,700 103,100 25,000
TOTAL CLERK & RECORDER

40,400

31,000

16,500

17,700

136,800

67 VOTING BOOTHS '77 $ 17,OS Tabulators '02 ($6500 ea) $78,DRE machines '06 (3800ea) $41,800 replace 2016 LASER PRINTER HP55i GEMS COMPUTER STATION/SERVER 14 E-POLLBOOKS TOTAL ELECTIONS
Voting Equipment Voting Equipment Voting Equipment Voting Equipment Voting Equipment Voting Equipment

yrs 10 yrs 4 -

24,000 78,000 41,800 4,000 12,000 16,800 24,000 16,800 82,000 12,000 16,800 16,800 41,800 4,000 12,000 4,000 12,000 16,800 16,800
G:\budget\2010\original\R&R\Dept'l Replacement\ 2010 Clerk Elections dept equip 7-15-09.xls

SHERIFF

SANYO LCD TV 37" - LCR SMARTBOARD INTERACTIVE DISPLAY - LCR NITE VISION GOGGLES PATROL PHOTOGRAPHIC EQUIPMENT TRAFFIC RADARS (20) RADAR TRAILER-(SMALL WHITE) RADAR TRAILER-(LARGE ORANGE) EVIDENCE LOCKERS BALLISTIC VESTS - OFFICERS (15) BALLISTIC VESTS - TACTICAL (20) VARDA ALARM SYSTEM TASERS (24) IN 2000 @450, NOW 800 RIFLES (24) GPS UNITS (22) AVALANCHE BEACONS & PROBES AUTO DEFIB. LP 12 - 2003 AUTO DEFIB. BATTERIES AUTO DEFIB. LP 1000 (12) AUTO DEFIB. LP 500 (12)
5,000 6,000 7,600 7,600 12,000 2,000 4,000 25,000 3,200 1,1,500 12,000 1,200 30,000 7,600 8,000 7,600 7,600 8,000 7,600 7,600 12,000 4,000 4,000 4,000 4,000 4,000 4,000 3,1,500 1,200

5,000 8,000 7,600

7,600 8,000
4,000 25,000 3,200 1,200 600

3,200 1,200 600

3,1,500

3,1,500 1,200 15,000

3,200 1,12,000 1,200 15,000

3,1,500 1,200 20,000

1,200 1,200 10,000 20,000 DELETE LINE AFTER 2010

1,200 10,000

1,200 15,000
TOTAL PATROL EQUIPMENT PATROL ROOM MICROWAVE PATROL REFRIGERATOR TOTAL OFFICE FURNITURE/EQUIP. TOTAL SHERIFF 10 7

17,800

48,700

58,000

39,100

45,800

41,100

44,1,000

35,300

30,800

46,100

40,800

1,500 46,300
F.A.T.S FIREARMS MACHINE (PITCO 29%) TOTAL FIREARMS PROGRAM FIREARMS PARTICIPATION REVENUE @ 59% PITCO SHARE
11,080 11,080 6,537 4,543 -
G:\budget\2010\original\R&R\Dept'l Replacement\ 2010 Sheriff dept equip 7-22-09.xls

DETENTION

APPLIANCES DISHWASHER (1) WASHER/DRYER STACK(1) REFRIGERATOR Large (2) REFRIGERATOR Small (2) MICROWAVE (3) A/V EQUIPMENT: TV Large (2) Med (6) Small (2) VCR / DVD Players (3) PHOTOGRAPHIC EQUIPMENT: POLAROID MUG CAMERA GYM EQUIPMENT: EXERCISE BIKES (3) WEIGHT MACHINE WEIGHTS & SYSTEM TREADMILL SECURITY CHAIR FURNITURE: OPERATOR CHAIRS/92/0 DESK SERIES 9000 (1) OAK BEDFRAMES (18) MOLDEN CHAIRS (2) SLED BED SIDECHAIRS (6) SLED BASE ARMS (2) 96X42X36 BOAT TABLE 32" INMATE DESKS (21) OAK BKCASE 2 SHELVES (6) OAK BENCHES 60X35 TABLES (2) 42"ROUND TABLE (1) 96X42X36 TABLE (1) GREEN LOUNGE CHAIRS (3) MADISON LOUNGE CHRS (10) THORNET SIDECHAIRS (12) THORNET ARMCHAIRS (4) TARA SIDECHAIRS (30) TARA ARMCHAIR (12) DESKS

1,350 1,350

1,350 1,500 300

1,1,1,500

1,500 1,700 1,200 2,1,300 2,400 3,600 1,600 1,600 1,300 2,400 1,200 2,000 1,000 750

TOTAL PITKIN COUNTY JAIL

13,750
G:\budget\2010\original\R&R\Dept'l Replacement\ 2010 Detention dept equip 7-22-09.xls

FLEET MANAGEMENT

HOTSY CAR WASH BUILDING EQUIPME MOBILE HOTSY SHOP TOOLS TIRE BALANCER SHOP TOOLS TIRE MACHINE - big SHOP TOOLS TIRE MACHINE - small SHOP TOOLS ALIGNMENT MACHINE SHOP TOOLS METAL LATHE SHOP TOOLS BRAKE LATHE SHOP TOOLS BANDSAW SHOP TOOLS SMALL VEHICLE HOIST (2) BUILDING EQUIPME BIG VEHICLE LIFT BUILDING EQUIPME SHOP PARTS WASHER SHOP TOOLS STICK WELDER SHOP TOOLS MIG WELDER - Big SHOP TOOLS MIG WELDER - Little SHOP TOOLS TIG WELDER SHOP TOOLS PLASMA SHOP TOOLS PERONA SHOP TOOLS AC UNIT SHOP TOOLS TRANSMISSION UNIT SHOP TOOLS COOLANT UNIT SHOP TOOLS POWER STEERING UNIT SHOP TOOLS INSHOP WELDING EXHAUST ELIMINATOR SHOP TOOLS SANDBLASTER SHOP TOOLS AIR COMPRESSOR BUILDING EQUIPME MILL SHOP TOOLS SNAP ON MASTER TECH - Small vehicle diagnost SHOP TOOLS SNAP ON DIOGNOSTIC - Lab Scope SHOP TOOLS FUEL TANKS EMMA INSPECTION AND SPCC PLAN FUEL TANKS LANDFILL INSPECTION AND SPCC PLAN FUEL TANKS SHOP INSPECTION AND SPCC PLAN FUEL TANKS AIRPORT INSPECTION AND SPCC PLAN TOTAL FLEET MANAGEMENT

10,500

4,000 10,000 15,000 4,000 15,000 11,000 11,000 6,000 4,000 15,000 10,000 15,000
9,500 12,000 6,000 3,500 7,500 5,000 6,000 5,000 2,000 2,000 4,000 12,000 2,500 7,000 3,000 3,000 3,000 3,000 3,000 43,000 22,000 34,500 7,000 3,000 3,000 3,000 3,000 3,000 19,000 24,000 31,000 31,500 38,000 3,000 3,000 35,500 24,000 7,500 3,500 7,500 3,500 3,000 3,000 3,000 2,000 4,000 8,000 6,000

G:\budget\2010\original\R&R\Dept'l Replacement\ 2010 Fleet dept equip 7-27-09.xls
HEALTH & HUMAN SERVICES ADMIN
Lobby chairs ( 6) Lobby couches (2) lobby loveseat (1) lobby coffee tables (2) lobby end tables (3) refrigerator--staff kitchen refrigerator--former daycare space refrigerator--community health lab oven/range--staff kitchen oven/range--former daycare space dishwasher--staff kitchen dishwasher--former daycare space microwave--staff kitchen folding chairs (60) folding chairs (25) folding chairs (15) chair caddies (2) chair caddie (1) fold 'n roll tables (10) fold 'n roll tables (2) standard 8 ft. tables (2) square wooden tables (3) large wooden table TV/VCR overhead projector projector screens (2) outdoor storage shed LCD projector tent for Saturday market

TOTAL HHS ADMIN

4,500 5,850 900
900 actual $738.700 actual $398.2,200 6,100 1,actual $291.5,500 2,000 actual $489.25 1,300 1,22,550 1,000 5,900
1992 unknown 2009 unknown 2008 known--before 19

2008 2009

250 20,850 2,100
G:\budget\2010\original\R&R\Dept'l Replacement\ 2010 Human Services dept equip f8-10-09.xls
Pitkin County Department Equipment 10 Year Plan SENIOR SERVICES
DISHWASHER TABLE SOILED 1989 DISHWASHER TABLE CLEAN 1989 (12) ZINC RACKS @ $200 ea 1989-91 HOT/COLD SERVING UNIT 2001 KITCHEN HOOD 1989 KITCHEN SLICER 1989 WALK-IN FREEZER - TOTAL REPLACEMENT 1989 WALK-IN FREEZER COMPRESSOR 2000 WALK-IN FREEZER COILS 2008 WALK-IN REFRIGERATOR - TOTAL REPLACE 1989 WALK-IN REFRIGERATOR COMPRESSOR 2007 WALK-IN REFRIGERATOR COILS 2008 REFRIGERATOR (DISPLAY CASE) 1989 VULCAN RANGE 2005 ICE MAKER 2008 ICE DISPENSER 2008 COMMERICAL MICROWAVE OVEN-AMANA 1997 UPRIGHT DISHWASHER QUART MIXER - HOBART 2004 STAINLESS STEEL KITCHEN WORK TABLE 2006 TRAY STATION WITH WATER DISPENSER 2008 SHELVING ABOVE FOOD SERVICE AREAS 2008 (3) OUTDOOR DINING sets @ $900 ea 1989 (2) OUTDOOR BISTRO sets @ $375 ea 1989 (5) OUTDOOR UMBRELLAS @ $300 ea 2008 (13) WOOD BLINDS HUNTER DGLAS @ $200 ea 2001 (6) FILE CABINETS @ $300 ea 1989 FILE CABINET 2001 (2) FILE CABINETS @ $300 ea 2008 (2) WORK STATIONS @ $3000 ea 1989 WORKSTATION 2001 CABINET/WARDROBE 2001 CHAIR TELEPHONE TABLE 2001 PILLOWS/BENCHCOVER 2001 BEVERAGE CENTER COUNTERTOP 2008 ACOUSTICS $16,REUPHOLSTER (70) DINING CHAIRS 2001 REFINISH WOOD DINING CHAIRS 2007 REUPHOLSTER L/R FURN (2 sofa, 2 chair, 2 ott) 2001 GARBAGE DISPOSAL-(24) FOLDING CHAIRS-BLK PADDED @ $50 ea 1989 (5) FOLDING CARD TABLES @ $125 ea 1989 (2) UNIFRAME TABLES @ $1300 ea 1989 PUBLIC ADDRESS/SOUND SYSTEM 2008 TELEVISION, DVD, CART 2008 (76) STACKING CHAIRS-replace @ $800 ea 1989 (10) 36x36 DINING TABLES @ $520 ea 2001 (6) 30x60 DINING TABLES @ $670 ea 2001 CLOVER PARLOUR TABLE 1989 PINE WASH STAND 1989 WOOD BENCH W/BACK (CHURCH PEW) 1989 MENNONITE BENCH 1990 TABLE W/DROP LEAVES 1989 PIANO (2) KIMBALL SOFAS replace@$2500 ea 2001 (2) KIMBALL CHAIRS replace@ $1000 ea 2001 (2) KIMBALL OTTOMANS replace@ $500 ea 2001 KITCHEN FLOOR MATS 2008 (2) FOLDING OFFICE TABLES 18X48 @$135 ea 2007/08 RECEPTION DESK/WORKSTATION 2007 TOTAL SENIORS

10(11) (11) 20

2,300 1,500
[bumped] 5,500 2,500 2,500 2,500
2,400 2,500 1,500 2,500 6,000
5,000 1,200 1,200 4,000 5,000 2,4,5,4,800

2,285 2,600

2,1,500 1,800 1,215
6,000 2,1,5,500 2,000 3,000 2,250 [bumped] [bumped] [bumped] 1,2,600 5,000 2,000 60,800 5,200 4,650 [bumped] [bumped] [bumped] 5,000 2,000 1,19,550 7,000 2,000 9,485 87,900 750

12,835

28,495

14,100

10,900
G:\budget\2010\original\R&R\Dept'l Replacement\ 2010 Seniors dept equip 7-15-09.xls
Pitkin County Department Equipment 10 Year Plan AIRPORT CAPITAL REPLACEMENT AIRPORT (MAIN TERMINAL) CARPET REPLACEMENT ENTRY MATS HVAC REPAIR OVERHEAD DOORS PAINT EXTERIOR SIDING ROOF MAINTENANCE REPAIR TERMINAL SEATING WINDOW FILMING TERMINAL AUDIO/PA SYSTEM BASIC WORK EQUIPMENT LAWN MOWERS TOTAL MAIN TERMINAL 5 years 15,375 23,946 5,years 7 years 7 years 65,000 65,000 2,122 15,000 12,000 25,000 5,125 40,000 12,500 2,500 2,500 2,500 2,500 2,500 2,500 15,000 25,000 5,253 15,000 12,000 30,000 5,384 15,000 30,000 5,519 100,000 15,000 12,000 30,000 5,657 15,000 35,000 5,798 15,000 12,000 35,000 5,943 15,000 40,000 6,092 65,000 150,000 2,500 15,000 12,000 40,000 6,244 45,000 2,500 2,500 15,000 40,000 6,400 100,YEARS 2010 BUDGET 2011 PRJECTD 2012 PRJECTD 2013 PRJECTD 2014 PRJECTD 2015 PRJECTD 2016 PRJECTD 2017 PRJECTD 2018 PRJECTD 2019 PRJECTD

7,183,479

2,000 2,000

3,000 3,000

111,625

51,753

66,884

155,019

67,157

61,298

76,443

281,592

123,744

166,900

AIRPORT OPERATIONS CENTER WATER SOFTENER CARPET REPLACEMENT OVERHEAD DOOR REPLACEMENT PAINT EXTERIOR PAINT INTERIOR ICE REMOVER STORAGE TANK AFFORDABLE HOUSING UNITS APPLIANCE REPLACEMENT FLOORING REPLACEMENT INTERIOR PAINTING 7 years 5,years 4 years 10 years 20,000 15,000 5,000 20,000 50,000 5,000 20,000 15,000 25,000 35,000 5,000 20,000 60,000 15,000

5,000 20,000

5 years 3 years

5,0 6,000 5,000 5,000

6,000 7,000 5,000

7,000 5,000 5,000

TOTAL AIRPORT OPERATION CENTER

20,000

30,000

76,000

10,000

73,000

70,000

52,000

25,000
OTHER AIRPORT DEPARTMENTS GATE REPLACEMENT 5 years 0 188,479 50,000 50,000 181,625 50,000 50,000 131,142,165,019 30,000 30,000 117,134,96,443 30,000 30,000 381,175,191,900
TOTAL OTHER AIRPORT DEPARTMENTS

AIRPORT GRAND TOTAL

G:\budget\2010\original\R&R\Dept'l Replacement\ 2010 Airport Facility Capital Plan 7-8-09.xlsx
Pitkin County, Library Department Equipment 10 Year Plan

LIBRARY

Marmot terminals (replacement) Barcode Readers Receipt Printers Microfilm reader/printers Reel-to-reels CD/cassette players Amplifiers Turntables Reel-to-reel (control) Tape duplicator (control) Cassette player (control) Overhead projectors Portable overhead projectors Slide projectors Laser Printers VCR Television ADA-Reading machine Opaque projector Video projector Portable record player XEROX COPIER 5328 /94 LASER PRINTERS - Color TYPEWRITERS SERVER HUB POWER SUPPLY Azuradic - Disc Cleaner AMPLIFIER(CONTROL) WORK GROUP PRINTER FAX MACHINE BOOK DETECTION SYSTEM MICROWAVE LOUD SPEAKER SYSTEM TURNTABLE (CONTROL) OUTDOOR BOOK RETURN OFFICE CHAIRS COLOR COPIER REFINISH FURNITURE DVD PLAYERS TELEPHONE SYSTEM TOTAL LIBRARY

16,800 2,200

16,800 1,000

61,600

16,800 2,200 1,000

16,800

24,000 1,950 3,600 1,800 1,560 1,1,2,2,600 1,1,300 300
1,14,235 2,000 2,400 4,100 2,500 1,800 2,400 1,1,250 12,600 9,000 8,40,000 63,035 34,675 119,720 59,060 28,850 23,000 65,450 4,500 600. 34,290. 18,320 9,000 8,000 2,500 14,235 2,000 2,000 2,000 4,400 18,000. 2,500 2,500 1,400 2,500 2,500 1,800 2,400 1,500 2,000

2,400 1,000 10,700

G:\budget\2010\original\R&R\Dept'l Replacement\ 2010 Library Replacement 9-7-09.xls
Pitkin County Department Equipment 10 Year Plan LANDFILL, RESOURCE RECOVERY & COMPOSTING MULTI-YEAR CAPITAL REPLACEMENT & IMPROVEMENT

CAPITAL REPLACEMENT

LANDFILL: 416.68.92664. Truck scale/PC/software Gate/Fence replacement Asphalt/maint. Groundwater Equipment-Sampling Groundwater Equipment-QED Haz Mat building Permitting Modular Office Building Replacement Subtotal RESOURCE RECOVER416.68.92665. MRf-Conveyor Belts MRF-Bearings, gear boxes, motors 3-30 yard Roll-off containers 3-30 yard Roll-off containers 3-30 yard Roll-off containers 3-30 yard Roll-off containers 3-30 yard Roll-off containers Pitkin Iron Buildings Air Compressor Power Welder Baler conveyor and frame Horizontal Baler - Excel 2R9 Replacement Subtotal RR/COMPOSTING Compost pad prep Replacement Subtotal 416.68.92661

year 2008

life 8 25
COST 43,000 10,000 120,000 2,500 3,500 10,000 100,000 289,000
2010 150,000 10,000 100,000
10,000 50,000 2,500 3,500 10,000 40,000 2,500 3,500

2,500 3,500

260,000

40,000

50,000

2003 2003

5,754 7,284 10,000 15,000

5,754 7,284

5,754 12,000
15,000 15,000 150,000 1,500 3,630 56,000 256,000 490,168 150,000 3,500 3,630 3,630 3,630 3,500 3,630

15,000

150,000

31,538

24,884

50,000 50,000

CAPITAL REPLACEMENT SUMMARY: Landfill Resource Recovery Composting SWC TOTAL

6,000 3,9,630

260,000 15,275,000

0 150,150,000

0 3,3,630

0 31,31,538

6,0 6,000

10,000 3,13,630

40,000 15,55,000

50,0 50,000

10,000 24,34,884
G:\budget\2010\original\R&R\Dept'l Replacement\ 2010 RR replacement_CH 7-16-09.xls
Pitkin County Department Equipment 10 Year Plan ROAD CAPITAL PLAN
Road Name BRUSH CREEK RD MAROON CREEK RD SMITH WY OWL CREEK RD RED MTN RD AABC 400 AABC 500 AABC 200 AABC 300 AABC 100 SAGE WY FRONT WY MCLAIN FLATS RD GERBAZ WY SNOWMASS CREEK RD (to Capitol LOWER RIVER RD CASTLE CREEK RD UPPER RIVER RD AIRPORT RD E AIRPORT RD AIRPORT RD W AIRPORT RD SOPRIS CREEK RD WILLOUGHBY WY SNOWMASS CREEK RD CAPITOL CREEK RD WOODY CREEK RD WOODY CREEK RD EMMA RD WATSON DIVIDE RD WATSON DIVIDE RD MTN LAUREL DR E LUPINE DR MTN LAUREL CT W LUPINE DR W SOPRIS CREEK RD W SOPRIS CREEK RD MAROON CREEK RD REDSTONE BLVD REDSTONE BLVD PRINCE CREEK RD HUNTER CREEK TOLL RD E SOPRIS CREEK RD CASTLE CREEK RD CASTLE CREEK RD CASTLE CREEK RD MAGNIFICO RD GLEN EAGLES DRIVE E SOPRIS CREEK RD HORSESHOE DRIVE Traffic Volume Length (ft) 7,653.90 2,398.61 2,144.20 19,853.00 6,137.64 1,347.70 1,056.84 1,459.83 1,352.63 1,095.57 1,555.46 706.52 23,335.52 2,602.24 9,314.28 25,990.88 22,742.64 8,277.29 122.99 2,171.28 1,207.68 2,882.31 5,986.52 5,532.94 27,377.39 17,848.24 18,899.25 6,049.06 6,527.94 2,429.83 328.52 4,599.15 1,573.71 498.89 1,174.29 7,224.67 6,468.93 42,035.82 5,529.19 3,460.04 7,643.07 1,483.17 7,196.10 21,521.84 11,239.79 9,774.15 1,178.62 2,688.67 6,266.21 2,939.63 Length (mi) 1.45 0.45 0.41 3.76 1.16 7.23 0.26 0.20 0.28 0.26 0.21 0.29 0.13 4.42 0.49 1.76 8.30 4.92 4.31 1.57 0.02 0.41 0.23 0.55 1.13 1.05 5.19 3.38 3.58 1.15 27.48 1.24 0.46 0.06 0.87 0.30 0.09 0.22 1.37 1.23 7.96 1.05 0.66 1.45 0.28 17.23 1.36 4.08 2.13 1.85 0.22 0.51 1.19 0.56 OCI 96.95 87.53 64.04 95.74 100.00 24.61 49.00 61.46 63.16 73.78 100.00 100.00 67.99 84.38 91.71 83.93 74.91 68.38 86.88 62.48 84.55 90.97 67.23 68.68 89.90 79.12 68.21 89.54 69.85 87.24 89.35 68.76 82.24 76.74 94.38 88.22 93.04 96.51 85.46 91.41 92.36 89.54 83.64 82.75 86.15 52.99 58.49 69.85 86.54 69.53.20 479.2019

357 265

Traffic Volume 56
Road Name JACK GREDIG LN FRYING PAN RD FRYING PAN RD APPLE DR CHERRY LN PLUM ST Upper CAPITOL CREEK RD CONUNDRUM CREEK RD THOMPSON CREEK RD THOMPSON CREEK RD SMUGGLER MTN RD COOPER CREEK RD COAL CREEK RD South 7th Street Service Center Road Pearl Pass Road Maintenance + Misc Planning Budget
planning capital replacement / reconstruction 4" 2" Slurry Chip
Length (ft) 3,499.15 37,554.28 24,307.95 2,087.75 364.01 374.03 7,592.94 1,255.14 4,274.02 12,565.96 160.18 965.02 6,951.66
Length (mi) 0.66 7.11 4.60 0.40 0.07 0.07 1.44 0.24 0.81 2.38 0.03 0.18 1.32 0.00
OCI 90.16 68.74 73.04 78.65 73.05 76.33 68.18 90.64 53.34 29.27 83.35 39.66 86.18

175 175

325.0 1460.9 400,000 1,920,000 459,100 125.0 747.0 400,000 859,100 112,100 130.0 340.0 424,000 536,100 196,100 135.2 420.2 449,440 645,540 225,340 140.6 420.6 476,406 701,746 281,138 146.2 421.2 504,991 786,129 364,897 152.1 282.1 535,290 900,187 618,105 158.2 614.2 567,408 1,185,513 571,348 164.5 429.5 601,452 1,172,800 743,309 171.1 171.1 637,539 1,380,848 1,209,777 177.9 177.9 675,792 1,885,569 1,707,655
Yearly Budget Total Budget Carry Over

1520000

Turn to gravel Add gravel
TRANSLATOR CAPITAL REPLACEMENT GENERAL

YRS LIFE

SUNLIGHT (TV and FM) 00753
Denver TV Stations Satellite Donor Project Tower Structural Studies HVAC DTV Conversion Site Short Falls & Corrections Repair Roof Grassroots TV Buildout Replace Roof with Pitched Standing Seam Sheet Metal 1,000 1,000 8,000 30,000 20,000 15,000
LOWER RED MOUNTAIN (TV) 00761
Generator Replacement Tower Structural Studies HVAC DTV Conversion Site Short Falls & Corrections 20,000 20,000 3,000 1,000
UPPER RED MOUNTAIN (FM) 00754
Tower Structural Studies Repair Self-Support Tower (Rebuild Foundations, New Concrete) HVAC Road Repair DTV Conversion Generator Replacement 20,000 3,000 11,000 75,000 32,000
CROWN MOUNTAIN (TV and FM) 00757
Site Short Falls Denver TV Stations Satellite Donor Project DTV Conversion Alarm & Security System 500 20,000 67,000 30,000
WILLIAMS PEAK (TV and FM) 00755
Denver TV Stations Satellite Donor Project Site Shortfall Corrections (See Pericle Survey Report) HVAC DTV Conversion Generator Replacement FM Transoator Replacement 20,000

75,000 15,000 8,000

G:\budget\2010\original\R&R\Dept'l Replacement\ 2010 Translator 10 year plan 8-24-09.xls
TRANSLATOR CAPITAL REPLACEMENT ELEPHANT MOUNTAIN (TV and FM) 00752
Denver TV Stations Satellite Donor Project Tower Structural Studies HVAC DTV Conversion Generator Replacement FM Transoator Replacement

2011 20,000

13,000 1,000 20,000 5,000 8,000
THOMASVILLE (TV & FM) 00756
Denver TV Stations Satellite Donor Project Site Shortfall Corrections (See Pericle Survey Report) Tower Structural Studies HVAC DTV Conversion FM Transoator Replacement Generator Replacement 20,000 20,000 75,000 8,000 30,000 40,000
JACK RABBIT RIDGE (FM) 00751
Site Shortfall Corrections Roof Repair (New membrane and roll asphalt roofing) 300

LOGES PEAK (Inactive)

RED HILL (Inactive)
Redevelop Red Hill as Cell Site & Public Safety (Public Safety Equipment Costs Not Included) (Note: Can be done sooner if there is cellular operator interest) TOTAL TRANSLATOR

400,800

152,000

99,000

121,000

37,000