文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 4 Basic routing theory II – Adaptive routing
侵权投诉

4 Basic routing theory II – Adaptive routing

In this section we look at adaptive routing, i.e. the path taken by a packet may not only depend on its source and destination but also on the current situation in the network. Adaptive routing has several advantages over oblivious routing: ? It is possibl

W0W1

are concentrators

4 Basic routing theory II – Adaptive routing

and

4 Basic routing theory II – Adaptive routing

Figure2:Designofasplitter.

De nition4.2An(α,β,m,δ)-splitterisabipartitegraphG=(V∪(W0∪W1),E0∪E1)inwhich(V∪W0,E0)and(V∪W1,E1)represent(α,β,m,δ)-concentrators.EdgesinE0arecalled0-edges,andedgesinE1arecalled1-edges.

Withthehelpofthesplitterswecanconstructabutter ywithmultipleedgestoeachhalf,theso-calledmultibutter y.

De nition4.3Thed-dimensionalmultibutter yMBF(d,α,β,δ)hasN=(d+1)·2dnodesanddegreeatmost4δ.Figure3showsitsrecursiveconstruction.

4 Basic routing theory II – Adaptive routing

4 Basic routing theory II – Adaptive routing

d-dim. MBF

1-dim. MBFInputsOutputs

Figure3:Recursivede nitionofamultibutter y.

Forouradaptiveroutingalgorithmforthemultibutter ynetworkweassumethateverynodecanstoreatmostonepacket.Anodethathasonepacketiscalledblocked.WiththehelpofHall’smarriagetheorem(see,e.g.[5])onecanshowthateverysplittercanbepartitionedinto2δmatchingsM1,...,M2δ,whereeachmatchingMiisasubgraphofthesplitterinwhicheverynodehasadegreeof1.Thealgorithmworksinrounds.Ineachround,everynodeofthemultibutter yworksasfollows:

fori=1to2δdo:

Everynodethathasapacketthathastotraversesomes-edgewiths∈{0,1}checkswhetherithasans-edgeinMileadingtoanon-blockednodeatthenextlowerlevel.Ifso,itsendsthepackettothatnode.

上一页第3页

你可能喜欢

热门文档

相关文档

  • Routing_basic

    4 Basic routing theory I... 8页 免费 Module 6 - Basic Routing... 暂无评价 31页 免费 1 Constraint-Based Routi... 暂无评价 15页 免费 A basic ...

  • 2.1 Basic theory...

    (II)Basic Circuit Theory 8页 2财富值 2.Basic Circuit Theory 高... 8页 免费 4 Basic routing theory I... 8页 免费 Chapter 2 signal analysi... ...

  • 我要MVC潜规则之配置Routing(4)

    我要MVC潜规则之配置Routing(4)_计算机软件及应用_IT/计算机_专业资料。Mvc3教程我要学 ASP.NET MVC 3.0(四) 我要 MVC 潜规则之配置 Routing : 概述使用...

  • ch4_data_routing

    ? Routing schemes can also divided into static or adaptive according to the...– Start by introducing some basic graph-theoretic notions. 2015-1-13 ...

  • Routing_Protocol_Basic

    Routing_Protocol_Basic_计算机硬件及网络_IT/计算机_专业资料。Routing Basic 黄永刚 CCIE 之路系列 Huang Yonggang 2011/9/9 Routing Basic 2011 年 9 月 9...

  • ...Theory with Applications to Adaptive Routing_免...

    Evolutionary Game Theory with Applications to Adaptive Routing? Simon Fischer...their routing strategies from time to time depending on the observed ...

  • NS2 routing

    NS2 routing_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 NS2 routing_IT/计算机_专业资料。NS2中添加新路由协议的一般方法【转】...

  • Adaptive Routing Using Expert Advice

    10.1093/comjnl/bxh000 Adaptive Routing Using ...Theory, Budapest University of Technology and ...information is combined to update the routing ...

  • Adaptive Routing Strategies for Modern High Perform...

    Then, we implement and evaluate basic dispersive routing mechanisms, before proposing an adaptive routing scheme that increases the effective bisection bandwidth...

  • Routing (4)

    5.1 RIPv1: Distance Vector, Classful Routing Protocol ? 5.2 Basic RIPv1 Configuration ? 5.3 Verification and Troubleshooting ? 5.4 Automatic ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email