Complexity Regularized Signal Processing for Networking Applications

[摘要]今天的私人和公共通信网络是数据终端、路由器和交换机的关键系统，它们为我们的经济、科学和教育系统提供了支柱。因此，用于估计性能特征和检测关键组件故障和恶意行为的信号处理方法对于确保这一重要基础设施的可靠性和鲁棒性至关重要。此外，传感器和执行器网络将很快成为我们信息系统的一部分。这些网络将为我们的环境和以信息为基础的社会提供关键的联系。用于数据分析和信号处理的分布式和分层算法将是此类网络运行的核心。本研究针对网络中这些重要的、新兴的信号处理应用。该研究融合了自适应和分布式信号处理、非参数估计和分类、网络流量测量和建模、网络流量分析和断层扫描等领域。该项目涉及网络应用中数据分析、估计和分类的理论和方法的发展。网络中出现的大多数推理问题都极具挑战性；容易收集的数据的数量和性质是非常有限的，而且估计或分类任务通常是严重病态的。由于这些混杂因素，诸如最大似然之类的常见推理方法在大规模网络问题中的效用有限。因此，用于估计和分类的复杂度正则化方法为该项目提供了核心的计算信号处理工具。这些方法缓和了拟合数据和模型复杂性（以及因此产生的可变性）之间的权衡。本文重点研究了网络分析和推理中的两个核心问题。(1)网络断层扫描：网络断层扫描包括从网络中有限数量的点上测量的流量估计性能特征和流量模式。这个问题是非常病态的，现有的方案在大规模实现中表现不佳。我们提出了新的复杂性正则化网络断层扫描方法，旨在利用网络断层扫描问题的某些自然发生的稀疏性特征。(2)多通道网络流量分析：在网络流量分析领域已经做了很多工作，但重点主要集中在信号点轨迹上。分析和理解网络中不同点的流量之间的关系对整体性能至关重要。我们建议研究和开发能够揭示重要的交通相互关系、依赖关系和多测量点的一致性的分析方法。研究探讨了：1)用于估计和检测对网络性能至关重要的条件的网络推理方法的基本局限性；2)综合灵活的网络流量时空分析方法；3)用于网络数据分析和推理的可扩展、分布式和去中心化算法；4)复杂性正则化与分布式信号处理的基本理论。

Abstract0310889Robert D. NowakWilliam Marsh Rice UToday's private and public communications networks are critical systems of data terminals, routers, and switches that provide the backbone of our economic, scientific, and education systems. Consequently, signal processing methods for estimating performance characteristics and detecting key component failures and malevolent behavior are crucial for insuring the reliability and robustness for this vital infrastructure. Moreover, networks of sensors and actuators will soon be part of our information systems. These networks will provide critical links between our environment and our information-based society. Distributed and hierarchical algorithms for data analysis and signal processing will be central to the operation of such networks.This research targets these important, emerging signal processing applications in networking. The proposed research blends the fields of adaptive and distributed signal processing, nonparametric estimation and classification, network traffic measurement and modeling, and network traffic analysis and tomography. The project involves the development of theories and methodologies for data analysis, estimation, and classification in networking applications. Most inference problems arising in networking are extremely challenging; the amount and nature of the data that is easily collected is very limited, and the estimation or classification tasks are often severely ill-posed. Common inference methodologies such as maximum likelihood are of limited utility in large-scale networking problems due to these confounding factors. Therefore, complexity regularization methods for estimation and classification provide the core computational signal processing tools in the project. These methods temper the trade-off between fitting to the data and model complexity (and hence variability).Two core problems in network analysis and inference are the focus of this proposal. (1) Network Tomography: Network tomography involves estimating performance characteristics and traffic flow patterns from measured traffic at a limited number of points in the network. This problem is very ill-posed and existing schemes do not perform well in large-scale implementations. We propose novel complexity regularized approaches to network tomography that aim to capitalize on certain, naturally occurring, sparsity characteristics of the network tomography problems. (2) Multi-channel Network Traffic Analysis: Much work has been done in the area of network traffic analysis, but the focus has been mostly on signal point traces. Analysis and understanding of the relationships between traffic flows at different points in networks is crucial to overall performance. We propose to investigate and develop analysis methods capable of revealing important traffic interrelationships, dependencies, and coincidences at multiplemeasurement points. The research investigates: 1) fundamental limits in network inference methods for estimating and detecting conditions critical to network performance; 2) integrated and flexible approaches to spatio-temporal analysis of internetwork traffic patterns; 3) scalable, distributed, and decentralized algorithms for network data analysis and inference; 4) basic theory of complexity regularization and distributed signal processing.