文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 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

Adaptiveroutingbasedonlocalinformation:Here,nopathsystemoredgecostsareknown.Eachnodeonlyuseslocalinformation(suchasthepacketscurrentlyresidingatanode)fromitselfanditsdirectneighborswhendecidingwhichpackettotransmitalonganedge.Thisiscertainlythehardestofthethreecases,becausenoglobalguidancesuchaspathsystemsoredgecostsisavailable.

Wewillpresentanalgorithmforeachofthesecases.

4.1Adaptiveroutingbasedonpathsystems

Supposewewanttousethed-dimensionalbutter ynetworkasanindirectcommunicationnetworkwiththenodesatlayerdbeingtheinputsandthenodesinlayer0beingtheoutputs.Then√weknowfromtheBorodin-Hopcroftlowerboundthatapermutationcanbeconstructedsothat ()pathsgothroughasinglenode.Onewaytoimprovethisistoallowmorethanoneedgegoingtoeachhalfofthebutter y(seeFigure1).Thenasystemofmanyoptionalpathscanbeestablishedforeachsource-destinationpair.Onemaythenaskwhetherthiswouldsuf cetogetthecongestiondowntoalevelsimilartoValiant’s√trick.However,onecanshowthatusingδedgesinsteadofonecanstillcreateacongestionof (2d/log2δ).Thequestioniswhetheradaptivestrategieswoulddobetterinthissituation,andwewilldemonstratethatundercertaincircumstancestheydo.Forthisweneedsomede nitions.

Inputs

4 Basic routing theory II – Adaptive routing

4 Basic routing theory II – Adaptive routing

Outputs

4 Basic routing theory II – Adaptive routing

(a)(b)Figure1:(a)showsastandardbutter ynetworkand(b)showsavariantofitinwhicheverynodehasseveraledgestoeachhalf.

De nition4.1AbipartitegraphG=(V∪W,E)iscalledan(α,β,m,δ)-concentratorif

1.|V|=mand|W|=m/2,

2.thenodesinVhavedegreeatmostδandthenodesinWhavedegreeatmost2δ,and

3.forallU V,|U|≤α|V|:|Γ(U)|≥β|U|(recallthede nitionofΓinSection1.1).

Notethatα·β≤1/2,becauseotherwiseproperty(1)wouldbeviolated.Interestingly,thereareconstructionswhereforasmallenoughconstantαonecangetveryclosetothisinequality[8,6].Concentratorsallowtoconstructso-calledsplitters(seealsoFigure2).

上一页第2页

你可能喜欢

热门文档

相关文档

  • 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