## Computer Clock Synchronization

 In this work we examine synchronization of computer clocks connected via a data network and proposes a skewless algorithm to synchronize them. Unlike existing solutions, which either estimate and compensate the frequency difference (skew) among clocks or introduce offset corrections that can generate jitter and possibly even backward jumps, our solution achieves synchronization without these problems. We first analyze the convergence property of the algorithm and provide explicit necessary and sufficient conditions on the parameters to guarantee synchronization. We then study the effect of noisy measurements (jitter) and frequency drift (wander) on the offsets and synchronization frequency, and further optimize the parameter values to minimize their variance. Our study reveals a few insights, for example, we show that our algorithm can converge even in the presence of timing loops and noise, provided that there is a well-defined leader. This marks a clear contrast with current standards such as NTP and PTP, where timing loops are specifically avoided. Furthermore, timing loops can even be beneficial in our scheme as it is demonstrated that highly connected subnetworks can collectively outperform individual clients when the time source has large jitter. The results are supported by experiments running on a cluster of IBM BladeCenter servers with Linux.

Related publications:

1. E. Mallada, X. Meng, M. Hack, L. Zhang, and A. Tang, “Skewless network clock synchronization without discontinuity: Convergence and performance,” IEEE/ACM Transactions on Networking (TON), vol. 23, iss. 5, pp. 1619-1633, 2015. doi:10.1109/TNET.2014.2345692

This paper examines synchronization of computer clocks connected via a data network and proposes a skewless algorithm to synchronize them. Unlike existing solutions, which either estimate and compensate the frequency difference (skew) among clocks or introduce offset corrections that can generate jitter and possibly even backward jumps, our solution achieves synchronization without these problems. We first analyze the convergence property of the algorithm and provide explicit necessary and sufficient conditions on the parameters to guarantee synchronization. We then study the effect of noisy measurements (jitter) and frequency drift (wander) on the offsets and synchronization frequency, and further optimize the parameter values to minimize their variance. Our study reveals a few insights, for example, we show that our algorithm can converge even in the presence of timing loops and noise, provided that there is a well-defined leader. This marks a clear contrast with current standards such as NTP and PTP, where timing loops are specifically avoided. Furthermore, timing loops can even be beneficial in our scheme as it is demonstrated that highly connected subnetworks can collectively outperform individual clients when the time source has large jitter. The results are supported by experiments running on a cluster of IBM BladeCenter servers with Linux.

``````@article{mmhzt2015ton,
abstract = {This paper examines synchronization of computer clocks connected via a data network and proposes a skewless algorithm to synchronize them. Unlike existing solutions, which either estimate and compensate the frequency difference (skew) among clocks or introduce offset corrections that can generate jitter and possibly even backward jumps, our solution achieves synchronization without these problems. We first analyze the convergence property of the algorithm and provide explicit necessary and sufficient conditions on the parameters to guarantee synchronization. We then study the effect of noisy measurements (jitter) and frequency drift (wander) on the offsets and synchronization frequency, and further optimize the parameter values to minimize their variance. Our study reveals a few insights, for example, we show that our algorithm can converge even in the presence of timing loops and noise, provided that there is a well-defined leader. This marks a clear contrast with current standards such as NTP and PTP, where timing loops are specifically avoided. Furthermore, timing loops can even be beneficial in our scheme as it is demonstrated that highly connected subnetworks can collectively outperform individual clients when the time source has large jitter. The results are supported by experiments running on a cluster of IBM BladeCenter servers with Linux.},
author = {Mallada, Enrique and Meng, Xiaoqiao and Hack, Michel and Zhang, Li and Tang, Ao},
doi = {10.1109/TNET.2014.2345692},
issn = {1063-6692},
journal = {IEEE/ACM Transactions on Networking (TON)},
keywords = {Synchronization; Networking},
month = {10},
number = {5},
pages = {1619--1633},
rating = {1},
title = {Skewless network clock synchronization without discontinuity: Convergence and performance},
volume = {23},
web = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6883234},
year = {2015}
}``````

2. E. Mallada, X. Meng, M. Hack, L. Zhang, and A. Tang, “Skewless network clock synchronization,” in 21st IEEE International Conference on Network Protocols (ICNP), 2013, pp. 1-10. doi:10.1109/ICNP.2013.6733612

This paper examines synchronization of computer clocks connected via a data network and proposes a skewless algorithm to synchronize them. Unlike existing solutions, which either estimate and compensate the frequency difference (skew) among clocks or introduce offset corrections that can generate jitter and possibly even backward jumps, our algorithm achieves synchronization without these problems. We first analyze the convergence property of the algorithm and provide necessary and sufficient conditions on the parameters to guarantee synchronization. We then implement our solution on a cluster of IBM BladeCenter servers running Linux and study its performance. In particular, both analytically and experimentally, we show that our algorithm can converge in the presence of timing loops. This marks a clear contrast with current standards such as NTP and PTP, where timing loops are specifically avoided. Furthermore, timing loops can even be beneficial in our scheme. For example, it is demonstrated that highly connected subnetworks can collectively outperform individual clients when the time source has large jitter. It is also experimentally demonstrated that our algorithm outperforms other well-established software-based solutions such as the NTPv4 and IBM Coordinated Cluster Time (IBM CCT).

``````@inproceedings{mmhzt2013icnp,
abstract = {This paper examines synchronization of computer clocks connected via a data network and proposes a skewless algorithm to synchronize them. Unlike existing solutions, which either estimate and compensate the frequency difference (skew) among clocks or introduce offset corrections that can generate jitter and possibly even backward jumps, our algorithm achieves synchronization without these problems. We first analyze the convergence property of the algorithm and provide necessary and sufficient conditions on the parameters to guarantee synchronization. We then implement our solution on a cluster of IBM BladeCenter servers running Linux and study its performance. In particular, both analytically and experimentally, we show that our algorithm can converge in the presence of timing loops. This marks a clear contrast with current standards such as NTP and PTP, where timing loops are specifically avoided. Furthermore, timing loops can even be beneficial in our scheme. For example, it is demonstrated that highly connected subnetworks can collectively outperform individual clients when the time source has large jitter. It is also experimentally demonstrated that our algorithm outperforms other well-established software-based solutions such as the NTPv4 and IBM Coordinated Cluster Time (IBM CCT).},
author = {Mallada, Enrique and Meng, Xiaoqiao and Hack, Michel and Zhang, Li and Tang, Ao},
booktitle = {21st IEEE International Conference on Network Protocols (ICNP)},
doi = {10.1109/ICNP.2013.6733612},
keywords = {Networking; Synchronization},
month = {10},
pages = {1--10},
title = {Skewless network clock synchronization},
web = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6733612},
year = {2013}
}``````

## Dynamics-aware Optimal Power Flow

 The development of open electricity markets has led to a decoupling between the market clearing procedure that defines the power dispatch and the security analysis that enforces predefined stability margins. This gap results in market inefficiencies introduced by corrections to the market solution to accommodate stability requirements. In this work, we present an optimal power flow formulation that aims to close this gap. First, we show that the pseudospectral abscissa can be used as a unifying stability measure to characterize both poorly damped oscillations and voltage stability margins. This leads to two novel optimization problems that can find operation points which minimize oscillations or maximize voltage stability margins and make apparent the implicit tradeoff between these two stability requirements. Finally, we combine these optimization problems to generate a dynamics-aware optimal power flow formulation that provides voltage as well as small signal stability guarantees.

Related publications:

1. E. Mallada and A. Tang, “Dynamics-aware optimal power flow,” in 52nd IEEE Conference on Decision and Control (CDC), 2013. doi:10.1109/CDC.2013.6760118

The development of open electricity markets has led to a decoupling between the market clearing procedure that defines the power dispatch and the security analysis that enforces predefined stability margins. This gap results in market inefficiencies introduced by corrections to the market solution to accommodate stability requirements. In this paper we present an optimal power flow formulation that aims to close this gap. First, we show that the pseudospectral abscissa can be used as a unifying stability measure to characterize both poorly damped oscillations and voltage stability margins. This leads to two novel optimization problems that can find operation points which minimize oscillations or maximize voltage stability margins, and make apparent the implicit tradeoff between these two stability requirements. Finally, we combine these optimization problems to generate a dynamics-aware optimal power flow formulation that provides voltage as well as small signal stability guarantees.

``````@inproceedings{mt2013cdc,
abstract = {The development of open electricity markets has led to a decoupling between the market clearing procedure that defines the power dispatch and the security analysis that enforces predefined stability margins. This gap results in market inefficiencies introduced by corrections to the market solution to accommodate stability requirements. In this paper we present an optimal power flow formulation that aims to close this gap. First, we show that the pseudospectral abscissa can be used as a unifying stability measure to characterize both poorly damped oscillations and voltage stability margins. This leads to two novel optimization problems that can find operation points which minimize oscillations or maximize voltage stability margins, and make apparent the implicit tradeoff between these two stability requirements. Finally, we combine these optimization problems to generate a dynamics-aware optimal power flow formulation that provides voltage as well as small signal stability guarantees.},
author = {Mallada, Enrique and Tang, Ao},
booktitle = {52nd IEEE Conference on Decision and Control (CDC)},
doi = {10.1109/CDC.2013.6760118},
keywords = {Power Networks; Optimization},
month = {12},
title = {Dynamics-aware optimal power flow},
web = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6760118},
year = {2013}
}``````

2. E. Mallada and A. Tang, “Improving damping of power networks: Power scheduling and impedance adaptation,” in 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC), 2011, pp. 7729-7734. doi:10.1109/CDC.2011.6161287

This paper studies the effect of power scheduling and line impedances on the damping of a power network. We relate the damping of a network with the algebraic connectivity of a state dependent Laplacian. Via implicit function theorem, we further characterize its dependence on network parameters. This allows us to derive several updating directions that can locally improve the damping. The analysis also provides some interesting insight. For example, improving connectivity, by adding lines for instance, may not be beneficial in terms of damping.

``````@inproceedings{mt2011cdcb,
abstract = {This paper studies the effect of power scheduling and line impedances on the damping of a power network. We relate the damping of a network with the algebraic connectivity of a state dependent Laplacian. Via implicit function theorem, we further characterize its dependence on network parameters. This allows us to derive several updating directions that can locally improve the damping. The analysis also provides some interesting insight. For example, improving connectivity, by adding lines for instance, may not be beneficial in terms of damping.},
author = {Mallada, Enrique and Tang, Ao},
booktitle = {50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC)},
doi = {10.1109/CDC.2011.6161287},
keywords = {Power Networks; Optimization},
month = {12},
pages = {7729--7734},
title = {Improving damping of power networks: Power scheduling and impedance adaptation},
web = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6161287},
year = {2011}
}``````

## Sparse Recovery on Graphs

 Sparse recovery can recover sparse signals from a set of underdetermined linear measurements. Motivated by the need to monitor large-scale networks from a limited number of measurements, this work addresses the problem of recovering sparse signals in the presence of network topological constraints. Unlike conventional sparse recovery where a measurement can contain any subset of the unknown variables, we use a graph to characterize the topological constraints and allow an additive measurement over nodes (unknown variables) only if they induce a connected subgraph. We provide explicit measurement constructions for several special graphs, and the number of measurements by our construction is less than that needed by existing random constructions. Moreover, our construction for a line network is provably optimal in the sense that it requires the minimum number of measurements. A measurement construction algorithm for general graphs is also proposed and evaluated. For any given graph $G$ with $n$ nodes, we derive bounds of the minimum number of measurements needed to recover any k-sparse vector over $G(M_{k,n}^G)$. Using the Erdos-Renyi random graph as an example, we characterize the dependence of $M_{k,n}^G$ on the graph structure. Our study suggests that $M_{k,n}^G$ may serve as a graph connectivity metric.

Related publications:

1. M. Wang, W. Xu, E. Mallada, and A. Tang, “Sparse recovery with graph constraints,” IEEE Transactions on Information Theory, vol. 61, iss. 2, pp. 1028-1044, 2015. doi:10.1109/TIT.2014.2376955

Sparse recovery can recover sparse signals from a set of underdetermined linear measurements. Motivated by the need to monitor the key characteristics of large-scale networks from a limited number of measurements, this paper addresses the problem of recovering sparse signals in the presence of network topological constraints. Unlike conventional sparse recovery where a measurement can contain any subset of the unknown variables, we use a graph to characterize the topological constraints and allow an additive measurement over nodes (unknown variables) only if they induce a connected subgraph. We provide explicit measurement constructions for several special graphs, and the number of measurements by our construction is less than that needed by existing random constructions. Moreover, our construction for a line network is provably optimal in the sense that it requires the minimum number of measurements. A measurement construction algorithm for general graphs is also proposed and evaluated. For any given graph G with n nodes, we derive bounds of the minimum number of measurements needed to recover any k-sparse vector over G (Mk,nG). Using the Erdös-Rényi random graph as an example, we characterize the dependence of Mk,nG on the graph structure. This paper suggests that Mk,nG may serve as a graph connectivity metric.

``````@article{wxmt2015tit,
abstract = {Sparse recovery can recover sparse signals from a set of underdetermined linear measurements. Motivated by the need to monitor the key characteristics of large-scale networks from a limited number of measurements, this paper addresses the problem of recovering sparse signals in the presence of network topological constraints. Unlike conventional sparse recovery where a measurement can contain any subset of the unknown variables, we use a graph to characterize the topological constraints and allow an additive measurement over nodes (unknown variables) only if they induce a connected subgraph. We provide explicit measurement constructions for several special graphs, and the number of measurements by our construction is less than that needed by existing random constructions. Moreover, our construction for a line network is provably optimal in the sense that it requires the minimum number of measurements. A measurement construction algorithm for general graphs is also proposed and evaluated. For any given graph G with n nodes, we derive bounds of the minimum number of measurements needed to recover any k-sparse vector over G (Mk,nG). Using the Erdös-Rényi random graph as an example, we characterize the dependence of Mk,nG on the graph structure. This paper suggests that Mk,nG may serve as a graph connectivity metric.},
author = {Wang, M. and Xu, W. and Mallada, Enrique and Tang, A.},
doi = {10.1109/TIT.2014.2376955},
journal = {IEEE Transactions on Information Theory},
keywords = {Sparse Recovery},
month = {02},
number = {2},
pages = {1028-1044},
title = {Sparse recovery with graph constraints},
volume = {61},
year = {2015}
}``````

2. M. Wang, W. Xu, E. Mallada, and A. Tang, “Sparse recovery with graph constraints: Fundamental limits and measurement construction,” in Proceedings of IEEE Infocom, 2012, pp. 1871-1879. doi:10.1109/INFCOM.2012.6195562

This paper addresses the problem of sparse recovery with graph constraints in the sense that we can take additive measurements over nodes only if they induce a connected subgraph. We provide explicit measurement constructions for several special graphs. A general measurement construction algorithm is also proposed and evaluated. For any given graph G with n nodes, we derive order optimal upper bounds of the minimum number of measurements needed to recover any k-sparse vector over \$G (M_k,n^G)\$. Our study suggests that \$M_k,n^G\$ may serve as a graph connectivity metric.

``````@inproceedings{wxmt2012infocom,
abstract = {This paper addresses the problem of sparse recovery with graph constraints in the sense that we can take additive measurements over nodes only if they induce a connected subgraph. We provide explicit measurement constructions for several special graphs. A general measurement construction algorithm is also proposed and evaluated. For any given graph G with n nodes, we derive order optimal upper bounds of the minimum number of measurements needed to recover any k-sparse vector over \$G (M_k,n^G)\$. Our study suggests that \$M_k,n^G\$ may serve as a graph connectivity metric.},
author = {Wang, Meng and Xu, Weiyu and Mallada, Enrique and Tang, Ao},
booktitle = {Proceedings of IEEE Infocom},
doi = {10.1109/INFCOM.2012.6195562},
keywords = {Sparse Recovery},
month = {03},
pages = {1871--1879},
title = {Sparse recovery with graph constraints: Fundamental limits and measurement construction},
web = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6195562},
year = {2012}
}``````

3. W. Xu, E. Mallada, and A. Tang, “Compressive sensing over graphs,” in Proceeding of IEEE Infocom, 2011, pp. 2087-2095. doi:10.1109/INFCOM.2011.5935018

In this paper, motivated by network inference and tomography applications, we study the problem of compressive sensing for sparse signal vectors over graphs. In particular, we are interested in recovering sparse vectors representing the properties of the edges from a graph. Unlike existing compressive sensing results, the collective additive measurements we are allowed to take must follow connected paths over the underlying graph. For a sufficiently connected graph with n nodes, it is shown that, using O(k log(n)) path measurements, we are able to recover any k-sparse link vector (with no more than k nonzero elements), even though the measurements have to follow the graph path constraints. We mainly show that the computationally efficient ℓ1 minimization can provide theoretical guarantees for inferring such k-sparse vectors with O(k log(n)) path measurements from the graph.

``````@inproceedings{xmt2011infocom,
abstract = {In this paper, motivated by network inference and tomography applications, we study the problem of compressive sensing for sparse signal vectors over graphs. In particular, we are interested in recovering sparse vectors representing the properties of the edges from a graph. Unlike existing compressive sensing results, the collective additive measurements we are allowed to take must follow connected paths over the underlying graph. For a sufficiently connected graph with n nodes, it is shown that, using O(k log(n)) path measurements, we are able to recover any k-sparse link vector (with no more than k nonzero elements), even though the measurements have to follow the graph path constraints. We mainly show that the computationally efficient ℓ1 minimization can provide theoretical guarantees for inferring such k-sparse vectors with O(k log(n)) path measurements from the graph.},
author = {Xu, Weiyu and Mallada, Enrique and Tang, Ao},
booktitle = {Proceeding of IEEE Infocom},
doi = {10.1109/INFCOM.2011.5935018},
keywords = {Sparse Recovery},
month = {03},
organization = {IEEE},
pages = {2087--2095},
title = {Compressive sensing over graphs},
year = {2011}
}``````

## Congestion Control and Multi-path Routing

 This work considers a TCP/IP-style network with flow control at end-systems based on congestion feedback and routing decisions at network nodes on a per destination basis. The main generalization with respect to standard IP is to allow routers to split their traffic in a controlled way between the outgoing links. We formulate global optimization criteria, combining those used in the congestion control and traffic engineering, and propose decentralized controllers at sources and routers to reach these optimal points, based on congestion price feedback. We first consider adapting the traffic splits at routers to follow the negative price gradient; we prove this is globally stabilizing when combined with primal congestion control, but can exhibit oscillations in the case of dual congestion control. We then propose an alternative anticipatory control of routing, proving its stability for the case of dual congestion control. We present a concrete implementation of such algorithms, based on queueing delay as congestion price. We use TCP-FAST for congestion control, and develop a multipath variant of the distance vector routing protocol RIP. We demonstrate through ns2-simulations the collective behavior of the system, in particular, that it reaches the desired equilibrium points.

Related publications:

1. F. Paganini and E. Mallada, “A unified approach to congestion control and node-based multipath routing,” IEEE/ACM Transactions on Networking (TON), vol. 17, iss. 5, pp. 1413-1426, 2009. doi:10.1109/TNET.2008.2011902

The paper considers a TCP/IP-style network with flow control at end-systems based on congestion feedback and routing decisions at network nodes on a per-destination basis. The main generalization with respect to standard IP is to allow routers to split their traffic in a controlled way between the outgoing links. We formulate global optimization criteria, combining those used in the congestion control and traffic engineering, and propose decentralized controllers at sources and routers to reach these optimal points, based on congestion price feedback. We first consider adapting the traffic splits at routers to follow the negative price gradient; we prove this is globally stabilizing when combined with primal congestion control, but can exhibit oscillations in the case of dual congestion control. We then propose an alternative anticipatory control of routing, proving its stability for the case of dual congestion control. We present a concrete implementation of such algorithms, based on queueing delay as congestion price. We use TCP-FAST for congestion control and develop a multipath variant of the distance vector routing protocol RIP. We demonstrate through ns2-simulations the collective behavior of the system, in particular that it reaches the desired equilibrium points.

``````@article{pm2009ton,
abstract = {The paper considers a TCP/IP-style network with flow control at end-systems based on congestion feedback and routing decisions at network nodes on a per-destination basis. The main generalization with respect to standard IP is to allow routers to split their traffic in a controlled way between the outgoing links. We formulate global optimization criteria, combining those used in the congestion control and traffic engineering, and propose decentralized controllers at sources and routers to reach these optimal points, based on congestion price feedback. We first consider adapting the traffic splits at routers to follow the negative price gradient; we prove this is globally stabilizing when combined with primal congestion control, but can exhibit oscillations in the case of dual congestion control. We then propose an alternative anticipatory control of routing, proving its stability for the case of dual congestion control. We present a concrete implementation of such algorithms, based on queueing delay as congestion price. We use TCP-FAST for congestion control and develop a multipath variant of the distance vector routing protocol RIP. We demonstrate through ns2-simulations the collective behavior of the system, in particular that it reaches the desired equilibrium points.},
author = {Paganini, Fernando and Mallada, Enrique},
doi = {10.1109/TNET.2008.2011902},
journal = {IEEE/ACM Transactions on Networking (TON)},
keywords = {Networking},
month = {10},
number = {5},
pages = {1413--1426},
publisher = {IEEE},
title = {A unified approach to congestion control and node-based multipath routing},
volume = {17},
web = {http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5200323},
year = {2009}
}``````

2. E. Mallada and F. Paganini, “Stability of node-based multipath routing and dual congestion control,” in 47th IEEE Conference on Decision and Control (CDC), 2008, pp. 1398-1403. doi:10.1109/CDC.2008.4739209

This paper considers a network flow control problem where routing and input rates are controlled in a decentralized way across a network, to optimize a global welfare objective. We build on our recent work which combines “dual” congestion control for the traffic sources, with multipath routing at the router nodes, controlling the traffic split among outgoing links based on downstream congestion prices. The challenge is to obtain stabilization of the optimum point; in fact, controlling the split fractions following the price gradient has the correct equilibrium, but can lead to oscillatory instabilities. This suggests the use of derivative action to damp such oscillations. We study two alternatives in this regard; either anticipatory control of routing splits, which yields local stability in an arbitrary network topology, or anticipatory price generation, which yields a global result for the case of a network of parallel links. Proofs are based on a Lyapunov argument. Results are illustrated through simulations.

``````@inproceedings{mp2008cdc,
abstract = {This paper considers a network flow control problem where routing and input rates are controlled in a decentralized way across a network, to optimize a global welfare objective. We build on our recent work which combines ``dual'' congestion control for the traffic sources, with multipath routing at the router nodes, controlling the traffic split among outgoing links based on downstream congestion prices. The challenge is to obtain stabilization of the optimum point; in fact, controlling the split fractions following the price gradient has the correct equilibrium, but can lead to oscillatory instabilities. This suggests the use of derivative action to damp such oscillations. We study two alternatives in this regard; either anticipatory control of routing splits, which yields local stability in an arbitrary network topology, or anticipatory price generation, which yields a global result for the case of a network of parallel links. Proofs are based on a Lyapunov argument. Results are illustrated through simulations.},
author = {Mallada, Enrique and Paganini, Fernando},
booktitle = {47th IEEE Conference on Decision and Control (CDC)},
doi = {10.1109/CDC.2008.4739209},
keywords = {Networking},
month = {12},
pages = {1398--1403},
title = {Stability of node-based multipath routing and dual congestion control},