• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Exact and heuristic algorithms for solving the generalized minimum filter placement problem.
【24h】

Exact and heuristic algorithms for solving the generalized minimum filter placement problem.

机译：用于解决广义最小滤波器放置问题的精确和启发式算法。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We consider a problem of placing route-based filters in a communication network to limit the number of forged address attacks to a prescribed level. Nodes in the network communicate by exchanging packets along arcs, and the originating node embeds the origin and destination addresses within each packet that it sends. In the absence of a validation mechanism, one erode care send packets to another node using a forged origin address to launch an attack against that node. Route-based filters can be established at various nodes on the communication network to protect against these attacks. A route-based filter examines each packet arriving at a node, and determines whether or not the origin address could be legitimate; based on the arc on which the packet arrives, the routing information, and possibly the destination. The problem we consider seeks to find a minimum cardinality subset of nodes to filter so that the prescribed level of security is achieved.; The primary contributions of this dissertation are as follows. We formulate and discuss the modeling of this filter placement problem as a mixed-integer program. We then show the sensitivity of the optimal number of deployed filters as the required level of security changes; and demonstrate that current vertex cover-based heuristics are ineffective for problems with relaxed security levels. We identify a set of special network topologies on which the filter placement problem is solvable in polynomial time, focusing our attention on the development of a dynamic programming algorithm for solving this problem on tree networks. These results can then in turn be used to derive valid inequalities for a mixed-integer programming model of the filter placement problem. Finally, we present heuristic algorithms based on the insights gained front our overall study for solving the problem, and evaluate their performance against the optimal solution provided by our mixed-integer programming model.
机译：我们考虑了在通信网络中放置基于路由的筛选器，以将伪造的地址攻击的数量限制到规定级别的问题。网络中的节点通过沿弧线交换数据包进行通信，并且原始节点将源地址和目标地址嵌入到它发送的每个数据包中。在没有验证机制的情况下，一个被腐蚀的人使用伪造的原始地址将数据包发送到另一个节点，以对该节点发起攻击。可以在通信网络的各个节点上建立基于路由的筛选器，以防止这些攻击。基于路由的过滤器检查到达节点的每个数据包，并确定源地址是否合法；基于数据包到达的弧，路由信息以及可能的目的地。我们认为的问题是寻求找到要过滤的最小基数子集，以便达到规定的安全级别。本文的主要贡献如下。我们以混合整数程序的形式制定和讨论此过滤器放置问题的建模。然后，我们将说明随着所需安全级别的变化，最佳数量的已部署过滤器的敏感性。并证明当前基于顶点覆盖的启发式方法对于安全级别放宽的问题无效。我们确定了一组特殊的网络拓扑，可以在多项式时间内解决滤波器的放置问题，并将我们的注意力集中在开发用于在树状网络上解决该问题的动态规划算法。然后，这些结果又可以用于得出滤波器放置问题的混合整数编程模型的有效不等式。最后，我们基于启发式算法提出了启发式算法，这些见解是我们为解决问题而进行的整体研究之前得出的，并根据混合整数编程模型提供的最佳解决方案评估了它们的性能。

著录项

  • 作者

    Mofya, Enock Chisonge.;

  • 作者单位

    The University of Arizona.;

  • 授予单位 The University of Arizona.;
  • 学科 Engineering Industrial.; Operations Research.
  • 学位 Ph.D.
  • 年度 2005
  • 页码 111 p.
  • 总页数 111
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 一般工业技术;运筹学;
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号