English
Robust Network Tomography: k-identifiability and Monitor Assignment
文件大小：
210k
资源说明：### Robust Network Tomography: k-Identifiability and Monitor Assignment
#### 概述
网络拓扑识别(Network Tomography)作为一种有效的技术手段，在网络管理、路由选择、资源分配以及性能诊断等多个方面发挥着至关重要的作用。它通过在边缘节点进行端到端测量来推断网络内部的状态。然而，在实际应用中，网络元素的不可靠性（如链路故障）对网络状态的准确识别提出了挑战。因此，本研究提出了一种新的概念——k-可识别性(k-identifiability)，并在存在k个链路故障的情况下探讨了确保网络状态可识别性的拓扑条件。
#### 研究背景与动机
随着全球网络基础设施的快速发展，互联网变得越来越复杂。管理如此庞大的网络面临着巨大挑战，而准确及时地了解网络内部状态对于各种网络操作至关重要。然而，由于测量开销和技术限制，直接测量每个网络元素的性能往往是不可行的。因此，网络拓ology识别成为了一种理想的选择，通过在网络边缘放置监测器来进行端到端测量，从而推断网络内部状态。
#### k-可识别性的定义及意义
- **k-可识别性**：在存在最多k个链路故障的情况下，能够准确推断出网络内部状态的能力。
- **意义**：考虑到现实世界中网络可能会遭受链路故障的影响，k-可识别性为确保网络状态在不完美环境下仍能被准确识别提供了理论基础。
#### 拓扑条件分析
为了确保网络状态在存在k个链路故障的情况下仍可识别，本文提出了一系列充分必要条件。这些条件主要关注于如何构建网络结构，使得即使部分链路出现故障，网络内部状态仍然可以被准确推断。
- **测量路径与循环**：利用测量路径和循环来构建线性系统模型，该模型将已知的路径指标与未知的链路指标之间的关系建模为加性关系。
- **拓扑条件**：具体条件包括但不限于链路的冗余度、测量路径的选择等。这些条件确保了即使在网络存在多个故障点时，网络状态仍然可以被唯一确定。
#### 算法设计
基于以上理论基础，本研究还提出两种高效多项式时间算法来解决以下两个问题：
1. **链接可识别性分析**：给定一个具有指定监测器的网络，哪些链路是k-可识别的？
- 通过分析网络结构和链路故障的可能性，算法可以确定哪些链路即使在网络出现故障的情况下也能够被准确识别。
2. **监测器最佳位置选择**：给定一个网络和κ个监测器，监测器应该放置在哪里才能使k-可识别的链路数量最大化？
- 这一问题的核心在于优化监测器的位置以提高网络的整体可识别性。算法考虑了网络拓扑、链路故障概率等因素，以找到最佳的监测器部署方案。
#### 实验验证
通过对真实ISP网络拓扑结构的模拟实验，验证了所提出的算法的有效性。实验结果表明，即使在网络面临链路故障的情况下，采用上述算法也能显著提高网络状态的识别准确性。
#### 结论
本文针对网络拓ology识别中的关键问题——k-可识别性进行了深入研究，并提出了一系列确保网络状态在存在链路故障的情况下仍可识别的拓扑条件和算法。这不仅为网络管理提供了一套有效的理论框架，也为未来网络的设计和维护提供了重要的指导。通过这些研究成果的应用，有望进一步提升网络的可靠性和效率。
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
