论拓扑推理的难度外文翻译资料

On the Hardness of Topology Inference

H.B. Acharya¹ and M.G. Gouda²

1. The University of Texas at Austin, USA acharya@cs.utexas.edu
2. The National Science Foundation, USA mgouda@nsf.gov

Abstract. Many systems require information about the topology of net-works on the Internet, for purposes like management, efficiency, testing of new protocols and so on. However, ISPs usually do not share the actual topology maps with outsiders; thus, in order to obtain the topol-ogy of a network on the Internet, a system must reconstruct it from publicly observable data. The standard method employs traceroute to obtain paths between nodes; next, a topology is generated such that the observed paths occur in the graph. However, traceroute has the prob-lem that some routers refuse to reveal their addresses, and appear as anonymous nodes in traces. Previous research on the problem of topol-ogy inference with anonymous nodes has demonstrated that it is at best NP-complete. In this paper, we improve upon this result. In our pre-vious research, we showed that in the special case where nodes may be anonymous in some traces but not in all traces (so all node identifiers are known), there exist trace sets that are generable from multiple topolo-gies. This paper extends our theory of network tracing to the general case (with strictly anonymous nodes), and shows that the problem of computing the network that generated a trace set, given the trace set, has no general solution. The weak version of the problem, which allows an algorithm to output a “small” set of networks- any one of which is the correct one- is also not solvable. Any algorithm guaranteed to output the correct topology outputs at least an exponential number of networks. Our results are surprisingly robust: they hold even when the network is known to have exactly two anonymous nodes, and every node as well as every edge in the network is guaranteed to occur in some trace. On the basis of this result, we suggest that exact reconstruction of network topology requires more powerful tools than traceroute.

1 Introduction

Knowledge of the topology of a network is important for many design decisions. For example, the architecture of an overlay network - how it allocates addresses etc.- may be significantly optimized by knowledge of the distribution and con-nectivity of the nodes on the underlay network that actually carries the traffic. Several important systems, such as P4P [9] and RMTP [7], utilize information about the topology of the underlay network for optimization as well as man-agement. Furthermore, knowledge of network topology is useful in research; for

M.K. Aguilera et al. (Eds.): ICDCN 2011, LNCS 6522, pp. 251–262, 2011.

c Springer-Verlag Berlin Heidelberg 2011

252 H.B. Acharya and M.G. Gouda

example, in evaluating the performance of new protocols. Unfortunately, ISPs do not make maps of the true network topology publicly available. Consequently, a considerable amount of research effort has been devoted to the development of systems that reconstruct the topology of networks in the Internet from publicly available data - [10], [6], and [4].

The usual mechanism for generating the topology of a network is by the use of Traceroute [3]. Traceroute is executed on a node, called the source, by specifying the address of a destination node. This execution produces a sequence of identifiers, called a trace, corresponding to the route taken by packets traveling from the source to the destination. A trace set T is generated by repeatedly executing Traceroute over a network N , varying the terminal nodes, i.e. the source and destination.

If T contains traces that identify every instance when an edge is incident on a node, it is possible to reconstruct the network exactly. However, practical trace sets do not have this property. The most common problems are incom-plete coverage, anonymity (where a node can be detected, but will not state its unique identifier, i.e. its address), and aliasing (nodes may have multiple unique identifiers). The situation is further complicated by load balancing, which may cause incorrect traces; tools such as Paris Traceroute [8] attempt to correct this problem.

In this paper, we deal with the problem of inferring the correct network topol-ogy in the presence of anonymous nodes. The problem posed by anonymous nodes in a trace is that a given anonymous node may or may not be identical to any other anonymous node. Clearly, a topology in which these nodes are dis-tinct is not identical to one in which they are merged into a single node. Thus, there may be multiple topologies for the computed network. Note that all these candidate topologies can generate the observed trace set; no algorithm can tell, given the trace set as input, which of these topologies is correct.

To solve this problem, Yao et al. [10] have suggested computing the minimal topology - the topology of the network with the smallest number of anonymous nodes (subject to some constraints - trace preservation and distance preser-vation) from which the given trace set is generable. They conclude that the problem of computing a minimal network topology from a given set of traces is NP-complete. Accordingly, most later research in the area, such as [6] and [4], has focused on heuristics for the problem.

We attack this problem from a different direction. In our earlier papers [1] and [2], we introduced a theory of network tracing, i.e. reconstruction of network topology from trace sets. In these papers, we made the problem theoretically

剩余内容已隐藏，支付完成后下载完整资料

论拓扑推理的难度

H.B. Acharya¹ and M.G. Gouda²

The University of Texas at Austin, USA acharya@cs.utexas.edu

The National Science Foundation, USA mgouda@nsf.gov

^{摘要：许多系统需要有关互联网上网络工作拓扑的信息，例如管理、效率、新协议测试等。然而，ISP通常不与外界共享实际的拓扑图；因此，为了在互联网上获得网络拓扑图，系统必须从公开的可观测数据中重建网络拓扑图。标准方法使用traceroute来获取节点之间的路径；接下来，生成拓扑，以便观察到的路径出现在图中。然而，traceroute有一个问题，一些路由器拒绝透露它们的地址，并在跟踪中显示为匿名节点。以往对匿名节点拓扑推理问题的研究表明，它充其量是NP完全的。本文对这一结果进行了改进。在我们以往的研究中，我们发现，在某些记录道中节点可能是匿名的，而不是在所有记录道中（因此所有节点标识符都是已知的），存在可从多个拓扑图中生成的跟踪集。本文将我们的网络跟踪理论推广到一般情况下（严格匿名节点），并表明在给定跟踪集的情况下，计算生成跟踪集的网络的问题没有一般的解决方案。这个问题的弱版本，允许一个算法输出一组“小”的网络——其中任何一个都是正确的网络——也是无法解决的。任何保证输出正确拓扑的算法至少输出一个指数数量的网络。我们的结果是惊人的健壮：即使已知网络只有两个匿名节点，并且网络中的每个节点和每个边缘都保证在某些跟踪中发生，它们仍然有效。在此基础上，提出了网络拓扑的精确重构需要比traceroute更强大的工具。}

1. 引言

了解网络的拓扑结构对于许多设计决策都很重要。例如，覆盖网络的结构——它如何分配地址等——可能会通过了解底层网络上实际承载传输的节点的分布和连通性而得到显著优化。一些重要的系统，如p4p[9]和rmtp[7]利用了有关底层网络拓扑的信息。为优化和管理铺设网络。此外，网络拓扑知识在研究中很有用；因为例如，在评估新协议的性能时。不幸的是，ISP不公开真实网络拓扑的地图。因此，大量的研究成果致力于开发利用公共数据重建互联网网络拓扑结构的系统－[10]、[6]和[4]。

生成网络拓扑的常见机制是使用traceroute[3]。traceroute通过指定目标节点的地址在名为source的节点上执行。这个执行产生一个称为跟踪的标识符序列，与从源到目的地的数据包所采取的路由相对应。跟踪集t是通过在网络n上重复执行traceroute，改变终端节点（即源节点和目标节点）而生成的。

如果T包含在节点上发生边缘事件时标识每个实例的跟踪，则可以准确地重建网络。但是，实际的跟踪集不具有此属性。最常见的问题是不完全覆盖、匿名（可以检测到一个节点，但不会说明其唯一标识符，即其地址）和别名（节点可能有多个唯一标识符）。负载平衡可能导致不正确的跟踪，这种情况进一步复杂化；Paris Traceroute[8]等工具试图纠正此问题。

本文讨论了在存在匿名节点的情况下，正确推断网络拓扑结构的问题。跟踪中匿名节点造成的问题是，给定的匿名节点可能与任何其他匿名节点相同，也可能不相同。显然，这些节点不连续的拓扑结构与它们合并到单个节点的拓扑结构不同。因此，计算网络可能有多个拓扑。请注意，所有这些候选拓扑都可以生成观察到的跟踪集；如果将跟踪集作为输入，则没有任何算法可以分辨出哪些拓扑是正确的。

为了解决这个问题，Yao等人[10]建议计算最小拓扑-具有最小数量匿名节点的网络拓扑（受某些限制-跟踪保留和距离预留），给定跟踪集可从中生成。他们得出的结论是，从给定的跟踪集计算最小网络拓扑的问题是NP完全的。因此，该领域的大多数后期研究，如[6]和[4]，都将重点放在问题的启发式方法上。

我们从不同的方向来解决这个问题。在我们之前的论文[1]和[2]中，我们介绍了网络跟踪理论，即从跟踪集重构网络拓扑。在这些论文中，我们通过假设没有节点是严格匿名的，从理论上解决了这个问题。在这个理论中，节点可以是不规则的，这意味着它在某些跟踪中是匿名的，但是必须存在至少一个非匿名跟踪。这种简化假设在实践中显然不成立；事实上，匿名节点几乎总是一致匿名的，而不是不规则的。（在实际情况下，匿名节点cor对不响应ping的路由器作出响应；不规则节点是由于负载过大而丢弃ping的路由器。

显然，通常情况下，节点是匿名的，而不是不规则的。）但是，它使我们能够为网络中的节点数量清楚（等于唯一标识符的数量）的情况开发理论。

本文发展了严格匿名节点网络的网络跟踪理论。我们最初的假设是，由于不规则节点是“部分”匿名的，因此[1]中的硬结果应该适用于不规则节点。令我们惊讶的是，事实并非如此；在定理3中，我们证明了具有一个匿名节点的网络完全由其跟踪集指定，而具有一个不规则节点的网络则不是[1]。因此，我们构建了一个完整的新的证据，证明网络跟踪存在严格的匿名性，如第3节所示。我们表明，即使在最小拓扑是正确的假设下，匿名节点的网络跟踪问题实际上比NP完全问题困难得多，不仅是难以解决的，而且是无法解决的。即使我们弱化了问题并允许算法返回“少量”拓扑（其中一个是正确的），问题仍然无法解决：保证返回正确拓扑的算法返回的拓扑数量至少是节点总数的指数（匿名和非匿名）。

一个非常令人惊讶的事实是，如果不规则节点的数量限制在两个，这个结果甚至成立。我们演示了如何构造一个跟踪集，该跟踪集可以从具有两个匿名节点的指数数量的网络中生成，但不能从具有一个或更少匿名节点的任何网络中生成。（有趣的是，我们的结果是在一个网络模型下得到的，该模型有多个强有力的假设——稳定和对称的路由、无别名和完全覆盖。我们为模型选择这样友好的条件的原因是为了证明，使用先进的网络跟踪技术（如Paris Traceroute）检测工件路径和推断丢失的链接并不能使问题变得更容易[5]。感谢Stefan Schmid博士的观察。）

我们想澄清一下我们的说法，即仅给定跟踪集，识别从中生成跟踪集的网络的问题是无法解决的。我们的证明并不涉及到一个已知的不可解问题的简化，例如停顿问题。相反，我们证明有许多最小的网络——其中的一个指数数量——可以生成一个给定的跟踪集；因此，仅给出跟踪集，就不可能确定地声明一个特定的拓扑（甚至是一个小拓扑集的一个成员）代表跟踪集实际上来自的网络。生成。

Yao等人提供的NP完整性的早期证明（通过减少图着色）。用于构造最小拓扑，而不是用于生成跟踪集的最小拓扑。找到指数型解集的一个单成员是NP完全的。因此，即使假设真正的网络在匿名节点数量上是最小的，试图重建它也比以前想象的困难得多。

在下一节中，我们正式定义了网络、跟踪和跟踪集等术语，以便能够发展我们对问题的数学处理。

2、最小网络跟踪

在本节中，我们将介绍本文中使用的术语的正式定义。我们还解释了我们的网络模型和假设的基础推理。最后，我们对所研究的问题作了正式的说明。

2.1 术语定义

网络n是节点具有唯一标识符的连接图。但是，一个节点可以或不可以用它的唯一标识符来标记。如果一个节点被标记为其唯一标识符，那么它是非匿名的；否则，它是匿名的。另外，非匿名节点可以是终端节点，也可以是非终端节点。（以下使用这些术语。）跟踪是节点标识符的序列。在满足以下四个条件的情况下，可以从网络生成跟踪t：1.t表示n中的简单路径

2.t中的第一个和最后一个标识符是n中终端节点的唯一标识符。

3.如果n中的非匿名节点“a”出现在t中，则显示为“a”。

4.如果n中的匿名节点“”出现在t中，则显示为“i”。i是t中唯一的整数，用于区分匿名节点。

在满足以下条件的情况下，可以从网络生成跟踪集T：

1.t中的每一个微量元素都是从n可属的。

2.对于N中的每对终端节点x、y，t在x和y之间至少有一条记录道。

3.n中的每个边在t中至少出现一个记录道。

4.n中的每个节点在t中至少出现一个记录道。

5.t是一致的：对于每两个不同的节点x和y，在t中的每个记录道x和y之间必须出现完全相同的节点，其中x和y都出现。

我们现在讨论为什么假设上述条件。

第一个条件显然是必要的。第三和第四个条件也很明显是必要的，因为我们对节点匿名性问题很感兴趣，而不是覆盖不完全。然而，第二和第五个条件是不平凡的，我们将它们解释如下。

不一致或非对称路由等条件可能是真的，也可能不是真的。此外，还可以使用源路由和公共跟踪路由页面等工具来确保跟踪集包含每对可能终端之间的跟踪。由于我们的主要结果是否定的，我们通过假设最坏的情况来证明它们的鲁棒性：我们发展了假设推理算法的最佳可能条件的理论，并证明了结果仍然有效。

在我们之前的工作[1]和[2]中，我们使用另一个强条件开发了我们的理论：没有节点是匿名的。对于一个可从网络工作生成的跟踪集，我们要求网络中每个节点的唯一标识符至少出现在一个跟踪中。但是，在进一步的研究中，我们了解到网络中的路由器似乎是匿名的，因为它们被配置为从不发送ICMP响应，或者使用traceroute数据包的目标地址而不是它们的实际地址[10]。因此，如果一个节点在单个跟踪中是匿名的，那么在跟踪集中的所有跟踪中它通常都是匿名的。这一事实将我们早期对网络跟踪的研究减少到了理论上的实践中，因为很明显它的假设是不能满足的。因此，在本文中，我们放弃了这一条件，更新了网络跟踪理论，将匿名节点的网络包含进来。

严格匿名节点的引入导致了我们理论中的一个复杂问题：我们不再拥有所有唯一的标识符，并且不能确定网络中节点的总数。因此，我们将采用与Yao等人相同的方法。在[10]中，尝试用尽可能少的匿名节点重建拓扑。因此，我们采用了一个新的定义：

可生成跟踪集t的最小网络n是具有以下属性的网络：

1.t可从n属。

2.t不能从节点数少于n的网络n中生成。

请注意，如果存在多个可生成跟踪集t的最小网络，那么它们都具有相同数量的节点。此外，由于所有这些网络都包含T中看到的每个非匿名节点，因此跟踪集T可生成的所有最小网络也具有相同数量的匿名节点。

2.2最小网络跟踪问题

我们现在可以对本文研究的问题给出一个形式化的定义。最小的网络跟踪问题可以这样描述：“设计一个

一种算法，将一个可从网络生成的跟踪集t作为输入，并产生一个网络n，使t可从n生成，对于任何网络n=n，至少满足下列条件之一：

1.t不可由n产生。

2.n的匿名节点比n多。”

弱最小网络跟踪问题可以表述为：“设计一种算法，将一个可从网络生成的跟踪集T作为输入，并生成一个最小网络的小集S=n1，hellip;，nk，这样t就可以从该集的每个网络生成，并且对于任何网络N/S，至少满足以下条件之一：LDS：

1.t不可由n产生。

2.n的匿名节点比s的任何成员都多。”

最小网络跟踪问题显然是弱最小网络跟踪问题的一个特例，在这种情况下，我们只考虑单个集很小。

在第3节中，我们证明了弱极小网络跟踪问题在存在匿名节点的情况下是不可解决的，即使我们只考虑指数大小的集合“不小”；当然，这意味着极小网络跟踪问题也是不可解决的。

1. 最小网络跟踪的硬度

在本节中，我们首先构造一个只有一个跟踪的非常简单的跟踪集，

T_0,0 = {(a, ₁, b₁)}

当然，他对于于图一中的网络。

图1 t0.0的最小拓扑

我们现在定义两个操作来扩展这个网络，op1和op2。在op1中，我们引入了一个新的非匿名节点和一个新的匿名节点；op1引入的非匿名节点是B节点。在op2中，我们引入一个非匿名节点，但可能引入或不引入一个匿名节点；如果我们只考虑最小网络，那么在op2中，我们只引入非匿名节点。

为了执行op1，我们引入了一个新的b节点（比如b i），通过一个新的匿名节点i连接到a。现在我们将解释如何确保i是一个新的匿名节点。

注意，我们对一致路由的假设确保了跟踪中没有循环。因此，我们可以确保我是一个“新的”匿名节点（而不是“旧的”，即以前看到的匿名节点），通过显示它发生在每个旧匿名节点的跟踪上。为了实现这一点，我们将从BI到每个预先存在的B节点BJ添加跟踪。这些痕迹的形式是（bi、ii、a、jj、bj）。然后，我们使用一致的路由来显示i=i i和j=j j，以及（如我们预期的那样）

我们表示通过应用op1 k产生的跟踪集，例如，在将op1应用到t0,0之后，我们t0.0乘以tk，0。获取跟踪集T1,0:

T₁ = {(a, ₁, b₁), (a, ₂, b₂), (b₁, ₃

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[19645]，资料为PDF文档或Word文档，PDF文档可免费转换为Word