ZIPjava基于蚁群算法路由选择可视化动态模拟.zip 1.25MB

weixin_44259230

资源文件列表:

java基于蚁群算法路由选择可视化动态模拟.zip 大约有14个文件
  1. readme.pdf 52.77KB
  2. 论文+程序/A new class of QoS routing strategies based on network graph reduction.pdf 275.4KB
  3. 论文+程序/java程序/
  4. 论文+程序/java程序/ant.java 18.72KB
  5. 论文+程序/java程序/Antcolony.java 14.5KB
  6. 论文+程序/java程序/Configer.java 4.88KB
  7. 论文+程序/java程序/MapPad.java 13.35KB
  8. 论文+程序/java程序/Maps.java 184.04KB
  9. 论文+程序/java程序/Pheromone.java 1.74KB
  10. 论文+程序/java程序/SetInd.java 6.94KB
  11. 论文+程序/毕业设计任务书.doc 33.5KB
  12. 论文+程序/翻译.doc 8.03MB
  13. 论文+程序/开题报告.doc 38.5KB
  14. 论文+程序/论文.doc 1.46MB

资源介绍:

这是“java 基于蚁群算法路由选择可视化动态模拟”，仅供学习参考，请勿商用。
<link href="/image.php?url=https://csdnimg.cn/release/download_crawler_static/css/base.min.css" rel="stylesheet"/><link href="/image.php?url=https://csdnimg.cn/release/download_crawler_static/css/fancy.min.css" rel="stylesheet"/><link href="/image.php?url=https://csdnimg.cn/release/download_crawler_static/89628520/raw.css" rel="stylesheet"/><div id="sidebar" style="display: none"><div id="outline"></div></div><div class="pf w0 h0" data-page-no="1" id="pf1"><div class="pc pc1 w0 h0"><img alt="" class="bi x0 y0 w1 h1" src="/image.php?url=https://csdnimg.cn/release/download_crawler_static/89628520/bg1.jpg"/><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0">A<span class="_ _0"> </span>new<span class="_ _0"> </span>class<span class="_ _0"> </span>of<span class="_ _0"> </span>QoS<span class="_ _0"> </span>routing<span class="_ _0"> </span>strategies<span class="_ _0"> </span>based<span class="_ _0"> </span>on<span class="_ _0"> </span>network</div><div class="t m0 x2 h2 y2 ff1 fs0 fc0 sc0 ls0 ws0">graph<span class="_ _0"> </span>reduction</div><div class="t m1 x3 h3 y3 ff2 fs1 fc0 sc0 ls0 ws0">q</div><div class="t m2 x4 h4 y4 ff1 fs2 fc0 sc0 ls0 ws0">C.<span class="_ _1"> </span>Casetti</div><div class="t m3 x5 h5 y5 ff1 fs3 fc0 sc0 ls0 ws0">a</div><div class="t m2 x6 h4 y4 ff1 fs2 fc0 sc0 ls0 ws0">,<span class="_ _1"> </span>R.<span class="_ _1"> </span>Lo<span class="_ _1"> </span>Cigno</div><div class="t m3 x7 h5 y5 ff1 fs3 fc0 sc0 ls0 ws0">a</div><div class="t m2 x8 h4 y4 ff1 fs2 fc0 sc0 ls0 ws0">,<span class="_ _1"> </span>M.<span class="_ _1"> </span>Mellia</div><div class="t m3 x9 h5 y5 ff1 fs3 fc0 sc0 ls0 ws0">a</div><div class="t m2 xa h4 y4 ff1 fs2 fc0 sc0 ls0 ws0">,<span class="_ _1"> </span>M.<span class="_ _1"> </span>Munaf</div><div class="t m2 xb h6 y6 ff3 fs2 fc0 sc0 ls0 ws0"></div><div class="t m2 xb h4 y4 ff1 fs2 fc0 sc0 ls0 ws0">o<span class="_ _2"></span>o</div><div class="t m3 xc h5 y5 ff1 fs3 fc0 sc0 ls0 ws0">a,</div><div class="t m3 xd h5 y7 ff1 fs3 fc0 sc0 ls0 ws0">*</div><div class="t m2 xe h4 y4 ff1 fs2 fc0 sc0 ls1 ws0">,Z<span class="_ _3"></span>.Z<span class="_ _3"></span>s</div><div class="t m2 xf h6 y6 ff3 fs2 fc0 sc0 ls0 ws0"></div><div class="t m2 xf h4 y4 ff1 fs2 fc0 sc0 ls0 ws0">o<span class="_ _2"></span>oka</div><div class="t m3 x10 h5 y5 ff1 fs3 fc0 sc0 ls0 ws0">b</div><div class="t m4 x11 h7 y8 ff1 fs4 fc0 sc0 ls0 ws0">a</div><div class="t m0 x12 h8 y9 ff4 fs5 fc0 sc0 ls0 ws0">Dipartimento<span class="_ _4"> </span>di<span class="_ _4"> </span>Elettronica,<span class="_ _4"> </span>Politecnico<span class="_ _4"> </span>di<span class="_ _4"> </span>Torino,<span class="_ _4"> </span>Corso<span class="_ _4"> </span>Duca<span class="_ _4"> </span>degli<span class="_ _4"> </span>Abruzzi<span class="_ _4"> </span>24,<span class="_ _4"> </span>I-10129<span class="_ _4"> </span>Torino,<span class="_ _4"> </span>Italy</div><div class="t m4 x13 h7 ya ff1 fs4 fc0 sc0 ls0 ws0">b</div><div class="t m0 x14 h8 yb ff4 fs5 fc0 sc0 ls0 ws1">Department<span class="_ _4"> </span>of<span class="_ _4"> </span>Telecommunications,<span class="_ _4"> </span>Budapest<span class="_ _4"> </span>University<span class="_ _4"> </span>of<span class="_ _4"> </span>Technology<span class="_ _4"> </span>and<span class="_ _4"> </span>Economic<span class="_ _5"></span>s,<span class="_ _4"> </span>Magyar<span class="_ _4"> </span>tud</div><div class="t m0 x15 h9 yc ff3 fs5 fc0 sc0 ls0 ws0"></div><div class="t m0 x15 h8 yb ff5 fs5 fc0 sc0 ls0 ws0">o<span class="_ _6"></span>o<span class="ff4">sok<span class="_ _4"> </span>k</span></div><div class="t m0 x16 h9 yc ff3 fs5 fc0 sc0 ls0 ws0">€</div><div class="t m0 x16 h8 yb ff5 fs5 fc0 sc0 ls0 ws0">o<span class="_ _6"></span>o<span class="ff4">r</span></div><div class="t m0 x17 h9 yc ff3 fs5 fc0 sc0 ls0 ws0"></div><div class="t m0 x17 h8 yb ff5 fs5 fc0 sc0 ls0 ws0">u<span class="_ _6"></span>u<span class="ff4">tja<span class="_ _4"> </span>2,</span></div><div class="t m0 x18 h8 yd ff4 fs5 fc0 sc0 ls0 ws0">1117<span class="_ _4"> </span>Budapest,<span class="_ _4"> </span>Hungary</div><div class="t m0 x19 ha ye ff1 fs5 fc0 sc0 ls0 ws0">Received<span class="_ _4"> </span>15<span class="_ _4"> </span>October<span class="_ _4"> </span>2002;<span class="_ _4"> </span>received<span class="_ _4"> </span>in<span class="_ _4"> </span>revised<span class="_ _4"> </span>form<span class="_ _4"> </span>16<span class="_ _4"> </span>October<span class="_ _4"> </span>2002;<span class="_ _4"> </span>accepted<span class="_ _4"> </span>24<span class="_ _4"> </span>October<span class="_ _4"> </span>2002</div><div class="t m0 x1a ha yf ff1 fs5 fc0 sc0 ls0 ws0">Responsible<span class="_ _4"> </span>Editor:<span class="_ _4"> </span>I.F.<span class="_ _4"> </span>Akyildiz</div><div class="t m0 x1b hb y10 ff6 fs6 fc0 sc0 ls0 ws0">Abstract</div><div class="t m0 x1c hc y11 ff1 fs6 fc0 sc0 ls0 ws0">This<span class="_ _7"> </span>paper<span class="_ _7"> </span>discusses<span class="_ _7"> </span>a<span class="_ _7"> </span>new<span class="_ _7"> </span>approach<span class="_ _7"> </span>to<span class="_ _7"> </span>QoS<span class="_ _7"> </span>routing,<span class="_ _7"> </span>introducing<span class="_ _7"> </span>the<span class="_ _7"> </span>notion<span class="_ _7"> </span>of<span class="_ _7"> </span>algorithm<span class="_ _7"> </span>resilience<span class="_ _7"> </span>(i.e.,<span class="_ _7"> </span>its<span class="_ _7"> </span>ca-</div><div class="t m0 x1b hc y12 ff1 fs6 fc0 sc0 ls0 ws0">pability<span class="_ _8"> </span>to<span class="_ _8"> </span>adapt<span class="_ _8"> </span>to<span class="_ _8"> </span>network<span class="_ _4"> </span>and<span class="_ _8"> </span>load<span class="_ _8"> </span>modifications)<span class="_ _8"> </span>as<span class="_ _8"> </span>performance<span class="_ _8"> </span>index<span class="_ _8"> </span>of<span class="_ _8"> </span>the<span class="_ _8"> </span>algorithm<span class="_ _8"> </span>itself.</div><div class="t m0 x1c hc y13 ff1 fs6 fc0 sc0 ls0 ws0">The<span class="_ _9"> </span>new<span class="_ _9"> </span>approach<span class="_ _9"> </span>can<span class="_ _9"> </span>be<span class="_ _9"> </span>summarized<span class="_ _9"> </span>as<span class="_ _9"> </span>Network<span class="_ _9"> </span>Graph<span class="_ _9"> </span>Reduction,<span class="_ _9"> </span>i.e.,<span class="_ _9"> </span>a<span class="_ _9"> </span>modification<span class="_ _9"> </span>of<span class="_ _9"> </span>the<span class="_ _9"> </span>graph<span class="_ _9"> </span>describing<span class="_ _9"> </span>the</div><div class="t m0 x1b hc y14 ff1 fs6 fc0 sc0 ls0 ws0">network<span class="_ _9"> </span>before<span class="_ _9"> </span>the<span class="_ _9"> </span>routing<span class="_ _9"> </span>path<span class="_ _a"> </span>is<span class="_ _9"> </span>computed,<span class="_ _a"> </span>in<span class="_ _9"> </span>order<span class="_ _9"> </span>to<span class="_ _9"> </span>exclude<span class="_ _9"> </span>from<span class="_ _9"> </span>the<span class="_ _a"> </span>path<span class="_ _9"> </span>selection<span class="_ _9"> </span>over-congested<span class="_ _9"> </span>portions<span class="_ _9"> </span>of<span class="_ _a"> </span>the</div><div class="t m0 x1b hc y15 ff1 fs6 fc0 sc0 ls0 ws0">network.<span class="_ _7"> </span>This<span class="_ _7"> </span>solution<span class="_ _8"> </span>leads<span class="_ _7"> </span>to<span class="_ _7"> </span>a<span class="_ _7"> </span>class<span class="_ _8"> </span>of<span class="_ _7"> </span>two-step<span class="_ _7"> </span>routing<span class="_ _7"> </span>algorithms,<span class="_ _b"> </span>where<span class="_ _b"> </span>both<span class="_ _7"> </span>steps<span class="_ _b"> </span>are<span class="_ _7"> </span>simple,<span class="_ _b"> </span>hence<span class="_ _7"> </span>allowing</div><div class="t m0 x1b hc y16 ff1 fs6 fc0 sc0 ls0 ws0">efficient<span class="_ _8"> </span>implementation.</div><div class="t m0 x1c hc y17 ff1 fs6 fc0 sc0 ls0 ws0">Simulation<span class="_ _8"> </span>experiments,<span class="_ _8"> </span>run<span class="_ _b"> </span>on<span class="_ _8"> </span>randomly-generated<span class="_ _8"> </span>topologies<span class="_ _b"> </span>and<span class="_ _8"> </span>traffic<span class="_ _8"> </span>patterns,<span class="_ _b"> </span>show<span class="_ _8"> </span>that<span class="_ _8"> </span>these<span class="_ _b"> </span>routing<span class="_ _8"> </span>algo-</div><div class="t m0 x1b hc y18 ff1 fs6 fc0 sc0 ls0 ws0">rithms<span class="_ _8"> </span>perform<span class="_ _4"> </span>consistently<span class="_ _8"> </span>better<span class="_ _8"> </span>than<span class="_ _4"> </span>both<span class="_ _8"> </span>the<span class="_ _8"> </span>standard<span class="_ _4"> </span>Minimum<span class="_ _8"> </span>Hop<span class="_ _4"> </span>algorithm<span class="_ _8"> </span>and<span class="_ _8"> </span>those<span class="_ _4"> </span>QoS-based<span class="_ _8"> </span>algorithms</div><div class="t m0 x1b hc y19 ff1 fs6 fc0 sc0 ls0 ws0">based<span class="_ _8"> </span>on<span class="_ _8"> </span>the<span class="_ _8"> </span>same<span class="_ _8"> </span>metrics<span class="_ _4"> </span>but<span class="_ _8"> </span>not<span class="_ _8"> </span>using<span class="_ _8"> </span>the<span class="_ _8"> </span>notion<span class="_ _8"> </span>of<span class="_ _8"> </span>Network<span class="_ _8"> </span>Graph<span class="_ _8"> </span>Reduction.</div><div class="t m0 x1b hc y1a ff7 fs6 fc0 sc0 ls0 ws0"><span class="_ _1"> </span><span class="ff1">2002<span class="_ _8"> </span>Elsevier<span class="_ _8"> </span>Science<span class="_ _8"> </span>B.V.<span class="_ _8"> </span>All<span class="_ _8"> </span>rights<span class="_ _8"> </span>reserved.</span></div><div class="t m0 x1b ha y1b ff4 fs5 fc0 sc0 ls0 ws0">Keywords:<span class="_ _4"> </span><span class="ff1">QoS<span class="_ _4"> </span>routing;<span class="_ _4"> </span>Routing<span class="_ _4"> </span>algorithms;<span class="_ _9"> </span>MPLS</span></div><div class="t m0 x1b hd y1c ff6 fs7 fc0 sc0 ls0 ws0">1.<span class="_ _b"> </span>Introduction</div><div class="t m0 x1c he y1d ff1 fs7 fc0 sc0 ls0 ws0">Dynamic,<span class="_"> </span>QoS-based<span class="_ _1"> </span>rou<span class="_ _c"></span>ting<span class="_ _d"> </span>received<span class="_"> </span>consid-</div><div class="t m0 x1b he y1e ff1 fs7 fc0 sc0 ls0 ws0">erable<span class="_ _e"> </span>attention<span class="_ _e"> </span>in<span class="_ _e"> </span>recent<span class="_ _e"> </span>years<span class="_ _e"> </span>[1–7],<span class="_ _e"> </span>especially</div><div class="t m0 x1b he y1f ff1 fs7 fc0 sc0 ls0 ws0">considering<span class="_ _f"> </span>the<span class="_ _f"> </span>difficulty<span class="_ _f"> </span>in<span class="_ _f"> </span>predicting<span class="_ _f"> </span>Internet</div><div class="t m0 x1d he y1c ff1 fs7 fc0 sc0 ls0 ws0">traffic<span class="_ _4"> </span>patterns<span class="_ _4"> </span>and<span class="_ _4"> </span>the<span class="_ _4"> </span>consequent<span class="_ _4"> </span>impos<span class="_ _c"></span>sibility<span class="_ _4"> </span>to</div><div class="t m0 x1d he y20 ff1 fs7 fc0 sc0 ls0 ws0">properly<span class="_ _b"> </span>plan<span class="_ _b"> </span>and<span class="_ _b"> </span>dimens<span class="_ _c"></span>ion<span class="_ _b"> </span>the<span class="_ _b"> </span>netwo<span class="_ _c"></span>rk.</div><div class="t m0 x1e he y1d ff1 fs7 fc0 sc0 ls0 ws0">The<span class="_ _4"> </span>core<span class="_ _4"> </span>of<span class="_ _4"> </span>any<span class="_ _4"> </span>QoS-based<span class="_ _8"> </span>routing<span class="_ _9"> </span>algori<span class="_ _c"></span>thm<span class="_ _4"> </span>is</div><div class="t m0 x1d he y1e ff1 fs7 fc0 sc0 ls0 ws0">a<span class="_"> </span>network-status-dep<span class="_ _c"></span>endent<span class="_ _e"> </span><span class="ff4">cost<span class="_"> </span>function<span class="_ _e"> </span></span>that<span class="_ _e"> </span>is</div><div class="t m0 x1d he y1f ff1 fs7 fc0 sc0 ls0 ws0">used<span class="_"> </span>to<span class="_ _d"> </span>find<span class="_"> </span>the<span class="_ _d"> </span>optimal<span class="_"> </span>(or<span class="_ _d"> </span>at<span class="_ _d"> </span>least<span class="_"> </span>a<span class="_ _d"> </span>suitable)</div><div class="t m0 x1d he y21 ff1 fs7 fc0 sc0 ls0 ws0">route<span class="_ _7"> </span>across<span class="_ _10"> </span>the<span class="_ _7"> </span>network<span class="_ _10"> </span>by<span class="_ _7"> </span>solving<span class="_ _10"> </span>an<span class="_ _7"> </span>optimiza-</div><div class="t m0 x1d he y22 ff1 fs7 fc0 sc0 ls0 ws0">tion<span class="_ _1"> </span>pro<span class="_ _c"></span>blem.<span class="_ _d"> </span>In<span class="_ _1"> </span>parti<span class="_ _c"></span>cular,<span class="_ _d"> </span>given<span class="_ _1"> </span>the<span class="_"> </span>best-effort</div><div class="t m0 x1d he y23 ff1 fs7 fc0 sc0 ls0 ws0">nature<span class="_ _1"> </span>of<span class="_ _1"> </span>the<span class="_ _1"> </span>current<span class="_ _1"> </span>Intern<span class="_ _c"></span>et<span class="_ _1"> </span>where<span class="_ _1"> </span>elastic<span class="_ _1"> </span>data</div><div class="t m0 x1d he y24 ff1 fs7 fc0 sc0 ls0 ws0">flows<span class="_ _4"> </span>are<span class="_ _4"> </span>in<span class="_ _4"> </span>the<span class="_ _4"> </span>majorit<span class="_ _c"></span>y,<span class="_ _4"> </span>the<span class="_ _4"> </span>most<span class="_ _8"> </span>commonly<span class="_ _4"> </span>used</div><div class="t m0 x1d he y25 ff1 fs7 fc0 sc0 ls0 ws0">metric<span class="_ _8"> </span>aims<span class="_ _8"> </span>at<span class="_ _8"> </span>the<span class="_ _8"> </span>maximization<span class="_ _8"> </span>of<span class="_ _8"> </span>either<span class="_ _8"> </span>network</div><div class="t m0 x1d he y26 ff1 fs7 fc0 sc0 ls0 ws0">utilization<span class="_ _1"> </span>or<span class="_ _1"> </span>user<span class="_ _1"> </span>throughpu<span class="_ _c"></span>t.<span class="_ _1"> </span>Several<span class="_ _1"> </span>proposals</div><div class="t m0 x1d he y27 ff1 fs7 fc0 sc0 ls0 ws0">introduced<span class="_ _1"> </span>cost<span class="_ _1"> </span>functions,<span class="_ _10"> </span>algorithm<span class="_ _c"></span>s<span class="_ _1"> </span>and<span class="_ _10"> </span>pro<span class="_ _c"></span>to-</div><div class="t m0 x1d he y28 ff1 fs7 fc0 sc0 ls0 ws0">cols<span class="_"> </span>that<span class="_"> </span>give<span class="_ _d"> </span>them<span class="_"> </span>advantages<span class="_"> </span>over<span class="_"> </span>traditional,</div><div class="t m4 x1f hf y29 ff2 fs4 fc0 sc0 ls0 ws0">q</div><div class="t m0 x20 ha y2a ff1 fs5 fc0 sc0 ls0 ws0">This<span class="_ _a"> </span>work<span class="_ _a"> </span>was<span class="_ _9"> </span>supported<span class="_ _a"> </span>in<span class="_ _a"> </span>part<span class="_ _a"> </span>by<span class="_ _9"> </span>the<span class="_ _a"> </span>Italian<span class="_ _a"> </span>Ministry<span class="_ _a"> </span>for</div><div class="t m0 x1b ha y2b ff1 fs5 fc0 sc0 ls0 ws0">University<span class="_"> </span>and<span class="_"> </span>Scientific<span class="_"> </span>Resear<span class="_ _5"></span>ch<span class="_"> </span>through<span class="_"> </span>the<span class="_"> </span>PLANET-IP</div><div class="t m0 x1b ha y2c ff1 fs5 fc0 sc0 ls0 ws0">Project.<span class="_ _8"> </span>A<span class="_ _b"> </span>preliminary<span class="_ _8"> </span>version<span class="_ _8"> </span>of<span class="_ _b"> </span>this<span class="_ _b"> </span>paper<span class="_ _8"> </span>was<span class="_ _b"> </span>presented<span class="_ _8"> </span>at</div><div class="t m0 x1b ha y2d ff1 fs5 fc0 sc0 ls0 ws0">IEEE<span class="_ _4"> </span>Infocom<span class="_ _4"> </span>2002<span class="_ _4"> </span>in<span class="_ _4"> </span>New<span class="_ _4"> </span>York.</div><div class="t m4 x21 h7 y2e ff1 fs4 fc0 sc0 ls0 ws0">*</div><div class="t m0 x20 ha y2f ff1 fs5 fc0 sc0 ls0 ws0">Corresponding<span class="_ _9"> </span>author.</div><div class="t m0 x1c ha y30 ff4 fs5 fc0 sc0 ls0 ws0">E-mail<span class="_ _4"> </span>address:<span class="_ _4"> </span><span class="ff1 fc1">munafo@polito.it<span class="_ _4"> </span><span class="fc0">(M.<span class="_ _4"> </span>Munaf</span></span></div><div class="t m0 x22 h9 y31 ff3 fs5 fc0 sc0 ls0 ws0"></div><div class="t m0 x22 ha y30 ff1 fs5 fc0 sc0 ls0 ws0">o<span class="_ _3"></span>o).</div><div class="t m0 x1b ha y32 ff1 fs5 fc0 sc0 ls0 ws0">1389-1286/02/$<span class="_ _9"> </span>-<span class="_ _8"> </span>see<span class="_ _9"> </span>front<span class="_ _4"> </span>matter<span class="_"> </span><span class="ff7"><span class="_ _10"> </span></span>2002<span class="_ _4"> </span>Elsevier<span class="_ _4"> </span>Science<span class="_ _4"> </span>B.V.<span class="_ _4"> </span>All<span class="_ _4"> </span>rights<span class="_ _4"> </span>reserved.</div><div class="t m0 x1b ha y33 ff1 fs5 fc0 sc0 ls0 ws2">PII:<span class="_ _4"> </span>S<span class="_ _11"> </span>1<span class="_ _11"> </span>3<span class="_ _11"></span>8<span class="_ _11"></span>9<span class="_ _11"></span>-<span class="_ _11"></span>1<span class="_ _12"></span>2<span class="_ _12"> </span>8<span class="_ _11"> </span>6<span class="_ _11"> </span>(<span class="_ _11"> </span>0<span class="_ _11"> </span>2<span class="_ _11"> </span>)<span class="_ _11"> </span>0<span class="_ _11"> </span>0<span class="_ _12"></span>4<span class="_ _11"> </span>1<span class="_ _11"> </span>4<span class="_ _11"> </span>-<span class="_ _11"> </span>0</div><div class="t m0 x23 ha y34 ff1 fs5 fc0 sc0 ls0 ws3">Computer<span class="_ _4"> </span>Networks<span class="_ _4"> </span>41<span class="_ _4"> </span>(2003)<span class="_ _9"> </span>475–487</div><div class="t m0 x24 ha y35 ff1 fs5 fc0 sc0 ls0 ws0">www.elsevier.com/locate/comnet</div><a class="l"><div class="d m5"></div></a></div><div class="pi" data-data='{"ctm":[1.764706,0.000000,0.000000,1.764706,0.000000,0.000000]}'></div></div><div id="pf2" class="pf w0 h0" data-page-no="2"><div class="pc pc2 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="/image.php?url=https://csdnimg.cn/release/download_crawler_static/89628520/bg2.jpg"><div class="t m0 x25 he y36 ff1 fs7 fc0 sc0 ls0 ws0">topology-based<span class="_ _10"> </span>algori<span class="_ _c"></span>thms<span class="_ _10"> </span>such<span class="_ _10"> </span>as<span class="_ _10"> </span>the<span class="_ _1"> </span>Minimum</div><div class="t m0 x25 he y37 ff1 fs7 fc0 sc0 ls0 ws0">Hop<span class="_ _1"> </span>(MH)</div><div class="t m6 x12 h10 y38 ff1 fs8 fc0 sc0 ls0 ws0">1</div><div class="t m0 x26 he y39 ff1 fs7 fc0 sc0 ls0 ws0">presently<span class="_ _1"> </span>used<span class="_"> </span>in<span class="_ _1"> </span>TCP/IP<span class="_ _1"> </span>networks</div><div class="t m0 x25 he y3a ff1 fs7 fc0 sc0 ls0 ws0">[8,9].<span class="_ _4"> </span>For<span class="_ _8"> </span>example<span class="_ _8"> </span>in<span class="_ _4"> </span>[1],<span class="_ _8"> </span>the<span class="_ _4"> </span>authors<span class="_ _8"> </span>introduce<span class="_ _4"> </span>the</div><div class="t m0 x25 he y3b ff1 fs7 fc0 sc0 ls0 ws0">bottleneck<span class="_ _7"> </span>bandwidth<span class="_ _7"> </span>as<span class="_ _b"> </span>a<span class="_ _7"> </span>metric<span class="_ _7"> </span>and<span class="_ _7"> </span>then<span class="_ _7"> </span>de&#64257;ne</div><div class="t m0 x25 he y3c ff1 fs7 fc0 sc0 ls0 ws0">the<span class="_"> </span>maximization<span class="_"> </span>of<span class="_ _1"> </span>user<span class="_"> </span>throughput<span class="_"> </span>as<span class="_"> </span>optimi-</div><div class="t m0 x25 he y3d ff1 fs7 fc0 sc0 ls0 ws0">zation<span class="_ _7"> </span>target.<span class="_ _7"> </span>Similarly,<span class="_ _7"> </span>in<span class="_ _10"> </span>[2,3]<span class="_ _b"> </span>the<span class="_ _10"> </span>authors<span class="_ _b"> </span>study</div><div class="t m0 x25 he y3e ff1 fs7 fc0 sc0 ls0 ws0">how<span class="_ _9"> </span>to<span class="_ _4"> </span>improve<span class="_ _9"> </span>the<span class="_ _4"> </span>throughput<span class="_ _4"> </span>of<span class="_ _9"> </span>high-ba<span class="_ _c"></span>ndwidth</div><div class="t m0 x25 he y3f ff1 fs7 fc0 sc0 ls0 ws0">tra&#64259;c,<span class="_"> </span>such<span class="_ _d"> </span>as<span class="_"> </span>large<span class="_ _d"> </span>&#64257;le<span class="_"> </span>transfers,<span class="_ _d"> </span>in<span class="_"> </span>a<span class="_ _d"> </span>network</div><div class="t m0 x25 he y40 ff1 fs7 fc0 sc0 ls0 ws0">where<span class="_ _10"> </span>resources<span class="_ _1"> </span>are<span class="_ _10"> </span>fairly<span class="_ _1"> </span>shared<span class="_ _10"> </span>among<span class="_ _1"> </span>connec-</div><div class="t m0 x25 he y41 ff1 fs7 fc0 sc0 ls0 ws0">tions.<span class="_ _9"> </span>Their<span class="_ _4"> </span>&#64257;ndings,<span class="_ _4"> </span>obtained<span class="_ _9"> </span>by<span class="_ _4"> </span>simulation,<span class="_ _4"> </span>show</div><div class="t m0 x25 he y42 ff1 fs7 fc0 sc0 ls0 ws0">that,<span class="_ _13"> </span>at<span class="_ _13"> </span>high<span class="_ _13"> </span>loads,<span class="_ _13"> </span>a<span class="_ _13"> </span>MH<span class="_ _13"> </span>routing<span class="_ _13"> </span>algorithm</div><div class="t m0 x25 he y43 ff1 fs7 fc0 sc0 ls0 ws0">maximizes<span class="_ _13"> </span>network<span class="_ _13"> </span>and<span class="_ _f"> </span>user<span class="_ _13"> </span>performance;<span class="_ _13"> </span>for</div><div class="t m0 x25 he y44 ff1 fs7 fc0 sc0 ls0 ws0">low-congested<span class="_ _7"> </span>networks,<span class="_ _b"> </span>inst<span class="_ _c"></span>ead,<span class="_ _b"> </span>they<span class="_ _7"> </span>propose<span class="_ _7"> </span>an</div><div class="t m0 x25 he y45 ff1 fs7 fc0 sc0 ls0 ws0">algorithm,<span class="_ _14"> </span>named<span class="_ _14"> </span>Minimum<span class="_ _14"> </span>Distance<span class="_ _14"> </span>(MD)</div><div class="t m0 x25 he y46 ff1 fs7 fc0 sc0 ls0 ws0">routing,<span class="_ _4"> </span>which<span class="_ _4"> </span>o&#64256;ers<span class="_ _4"> </span>better<span class="_ _4"> </span>performance<span class="_ _c"></span>.<span class="_ _4"> </span>However</div><div class="t m0 x25 he y47 ff1 fs7 fc0 sc0 ls0 ws0">they<span class="_ _f"> </span>are<span class="_ _13"> </span>unable<span class="_ _f"> </span>to<span class="_ _f"> </span>provide<span class="_ _f"> </span>an<span class="_ _13"> </span>algorithm<span class="_ _f"> </span>that</div><div class="t m0 x25 he y48 ff1 fs7 fc0 sc0 ls0 ws0">merges<span class="_ _0"> </span>the<span class="_ _15"> </span>two<span class="_ _0"> </span>behaviors.<span class="_ _15"> </span>Researchers<span class="_ _15"> </span>focused</div><div class="t m0 x25 he y49 ff1 fs7 fc0 sc0 ls0 ws0">their<span class="_ _8"> </span>attention<span class="_ _8"> </span>upon<span class="_ _4"> </span>other<span class="_ _8"> </span>aspects<span class="_ _8"> </span>of<span class="_ _8"> </span>QoS<span class="_ _8"> </span>routing,</div><div class="t m0 x25 he y4a ff1 fs7 fc0 sc0 ls0 ws0">namely<span class="_ _e"> </span>protocol<span class="_ _0"> </span>overhead<span class="_ _e"> </span>[5,7],<span class="_ _e"> </span>impl<span class="_ _c"></span>ementation</div><div class="t m0 x25 he y4b ff1 fs7 fc0 sc0 ls0 ws0">issues<span class="_ _b"> </span>[4,6],<span class="_ _b"> </span>impac<span class="_ _c"></span>t<span class="_ _b"> </span>of<span class="_ _b"> </span>update<span class="_ _b"> </span>policies<span class="_ _7"> </span>[5].</div><div class="t m0 x27 he y4c ff1 fs7 fc0 sc0 ls0 ws0">A<span class="_"> </span>major<span class="_ _1"> </span>drawb<span class="_ _c"></span>ack,<span class="_"> </span>however,<span class="_ _d"> </span>a&#64256;ects<span class="_"> </span>all<span class="_ _1"> </span>QoS-</div><div class="t m0 x25 he y4d ff1 fs7 fc0 sc0 ls0 ws0">based<span class="_ _8"> </span>routing<span class="_ _8"> </span>algorithms.<span class="_ _8"> </span>The<span class="_ _4"> </span>co<span class="_ _c"></span>st<span class="_ _8"> </span>function<span class="_ _8"> </span>at<span class="_ _4"> </span>the</div><div class="t m0 x25 he y4e ff1 fs7 fc0 sc0 ls0 ws0">core<span class="_ _8"> </span>of<span class="_ _8"> </span>the<span class="_ _b"> </span>algorithms<span class="_ _b"> </span>tries<span class="_ _8"> </span>to<span class="_ _b"> </span>&#64257;nd<span class="_ _8"> </span>por<span class="_ _c"></span>tions<span class="_ _8"> </span>of<span class="_ _b"> </span>the</div><div class="t m0 x25 he y4f ff1 fs7 fc0 sc0 ls0 ws0">network<span class="_ _e"> </span>where<span class="_ _0"> </span>resources<span class="_ _e"> </span>are<span class="_ _0"> </span>under-utilized<span class="_ _e"> </span>and</div><div class="t m0 x25 he y50 ff1 fs7 fc0 sc0 ls0 ws0">exploits<span class="_"> </span>them<span class="_"> </span>to<span class="_ _d"> </span>the<span class="_"> </span>bene&#64257;t<span class="_ _d"> </span>of<span class="_"> </span>connections<span class="_"> </span>that</div><div class="t m0 x25 he y51 ff1 fs7 fc0 sc0 ls0 ws0">would<span class="_ _7"> </span>otherw<span class="_ _c"></span>ise<span class="_ _7"> </span>cross<span class="_ _10"> </span>a<span class="_ _7"> </span>congested<span class="_ _10"> </span>portion<span class="_ _10"> </span>of<span class="_ _7"> </span>the</div><div class="t m0 x25 he y52 ff1 fs7 fc0 sc0 ls0 ws0">network.<span class="_ _8"> </span>In<span class="_ _4"> </span>doing<span class="_ _8"> </span>so,<span class="_ _4"> </span>as<span class="_ _8"> </span>shown<span class="_ _4"> </span>in<span class="_ _8"> </span>[11]<span class="_ _8"> </span>for<span class="_ _4"> </span>the<span class="_ _8"> </span>case</div><div class="t m0 x25 he y53 ff1 fs7 fc0 sc0 ls0 ws0">of<span class="_ _8"> </span>simple<span class="_ _b"> </span>alternate<span class="_ _b"> </span>routing,<span class="_ _b"> </span>the<span class="_ _b"> </span>algorithm<span class="_ _b"> </span>ends<span class="_ _8"> </span>up</div><div class="t m0 x25 he y54 ff1 fs7 fc0 sc0 ls0 ws0">consuming<span class="_ _8"> </span>more<span class="_ _4"> </span>resources<span class="_ _8"> </span>than<span class="_ _4"> </span>MH<span class="_ _8"> </span>routing<span class="_ _8"> </span>does,</div><div class="t m0 x25 he y55 ff1 fs7 fc0 sc0 ls0 ws0">hence,<span class="_ _0"> </span>in<span class="_ _0"> </span>case<span class="_ _15"> </span>of<span class="_ _0"> </span>heavy<span class="_ _0"> </span>congestion,<span class="_ _15"> </span>QoS-based</div><div class="t m0 x25 he y56 ff1 fs7 fc0 sc0 ls0 ws0">routing<span class="_ _13"> </span>wastes<span class="_ _16"> </span>resources<span class="_ _13"> </span>and<span class="_ _16"> </span>performs<span class="_ _13"> </span>poorly</div><div class="t m0 x25 he y57 ff1 fs7 fc0 sc0 ls0 ws0">compared<span class="_ _1"> </span>with<span class="_ _1"> </span>MH.<span class="_ _d"> </span>A<span class="_ _1"> </span>formal<span class="_ _1"> </span>proof<span class="_ _1"> </span>of<span class="_ _1"> </span>this<span class="_ _d"> </span>ob-</div><div class="t m0 x25 he y58 ff1 fs7 fc0 sc0 ls0 ws0">servation<span class="_ _1"> </span>can<span class="_ _1"> </span>be<span class="_ _1"> </span>found<span class="_ _1"> </span>in<span class="_ _1"> </span>[10].<span class="_ _1"> </span>The<span class="_ _1"> </span>extension<span class="_ _1"> </span>of</div><div class="t m0 x25 he y59 ff1 fs7 fc0 sc0 ls0 ws0">this<span class="_ _7"> </span>property<span class="_ _10"> </span>to<span class="_ _7"> </span>TCP/IP<span class="_ _10"> </span>networks<span class="_ _7"> </span>is<span class="_ _7"> </span>not<span class="_ _10"> </span>straight-</div><div class="t m0 x25 he y5a ff1 fs7 fc0 sc0 ls0 ws0">forward,<span class="_ _8"> </span>since<span class="_ _b"> </span>&#64258;ows<span class="_ _b"> </span>often<span class="_ _b"> </span>exhibit<span class="_ _b"> </span>a<span class="_ _8"> </span>greedy,<span class="_ _b"> </span>elastic</div><div class="t m0 x25 he y5b ff1 fs7 fc0 sc0 ls0 ws0">behavior,<span class="_ _10"> </span>using<span class="_ _10"> </span>up<span class="_ _10"> </span>the<span class="_ _10"> </span>a<span class="_ _c"></span>vailable<span class="_ _10"> </span>bandwidth.<span class="_ _10"> </span>M<span class="_ _c"></span>H</div><div class="t m0 x25 he y5c ff1 fs7 fc0 sc0 ls0 ws0">routing<span class="_ _e"> </span>ha<span class="_ _c"></span>s<span class="_ _e"> </span>be<span class="_ _c"></span>en<span class="_ _e"> </span>already<span class="_ _0"> </span>conjectured<span class="_ _0"> </span>to<span class="_ _e"> </span>be<span class="_ _0"> </span>as-</div><div class="t m0 x25 he y5d ff1 fs7 fc0 sc0 ls0 ws0">ymptotically<span class="_ _10"> </span>optimal<span class="_ _10"> </span>as<span class="_ _10"> </span>the<span class="_ _10"> </span>load<span class="_ _1"> </span><span class="ff8">q<span class="_ _7"> </span></span>o&#64256;e<span class="_ _c"></span>red<span class="_ _10"> </span>to<span class="_ _10"> </span>the</div><div class="t m0 x25 he y5e ff1 fs7 fc0 sc0 ls0 ws0">network<span class="_"> </span>tends<span class="_ _e"> </span>to<span class="_ _e"> </span>in&#64257;nity,<span class="_ _e"> </span>and<span class="_ _e"> </span>many<span class="_"> </span>sim<span class="_ _c"></span>ulation</div><div class="t m0 x25 he y5f ff1 fs7 fc0 sc0 ls0 ws0">results<span class="_ _8"> </span>con&#64257;<span class="_ _c"></span>rm<span class="_ _8"> </span>this<span class="_ _b"> </span>intuition<span class="_ _b"> </span>[2,3,13,16].<span class="_ _b"> </span>We<span class="_ _b"> </span>stress</div><div class="t m0 x25 he y60 ff1 fs7 fc0 sc0 ls0 ws0">at<span class="_ _10"> </span>this<span class="_ _1"> </span>point<span class="_ _1"> </span>that<span class="_ _1"> </span>the<span class="_ _10"> </span>poor<span class="_ _1"> </span>performance<span class="_ _1"> </span>of<span class="_ _1"> </span>QoS-</div><div class="t m0 x25 he y61 ff1 fs7 fc0 sc0 ls0 ws0">based<span class="_ _b"> </span>routing<span class="_ _b"> </span>at<span class="_ _7"> </span>high<span class="_ _b"> </span>loads<span class="_ _7"> </span>is<span class="_ _b"> </span>not<span class="_ _b"> </span>due<span class="_ _b"> </span>to<span class="_ _7"> </span>the<span class="_ _b"> </span>sub-</div><div class="t m0 x25 he y62 ff1 fs7 fc0 sc0 ls0 ws0">optimality<span class="_ _8"> </span>of<span class="_ _8"> </span>the<span class="_ _8"> </span>used<span class="_ _b"> </span>algorithms,<span class="_ _8"> </span>but<span class="_ _8"> </span>is<span class="_ _b"> </span>rooted<span class="_ _8"> </span>in</div><div class="t m0 x25 he y63 ff1 fs7 fc0 sc0 ls0 ws0">the<span class="_ _d"> </span>locality<span class="_ _d"> </span>of<span class="_ _d"> </span>the<span class="_ _d"> </span>routing<span class="_ _d"> </span>decision.<span class="_ _d"> </span>Whenever<span class="_ _d"> </span>a</div><div class="t m0 x28 he y64 ff1 fs7 fc0 sc0 ls0 ws0">call<span class="_ _4"> </span>is<span class="_ _4"> </span>routed,<span class="_ _4"> </span>the<span class="_ _4"> </span>given<span class="_ _4"> </span>cost<span class="_ _8"> </span>function<span class="_ _4"> </span>is<span class="_ _4"> </span>minimized/</div><div class="t m0 x28 he y65 ff1 fs7 fc0 sc0 ls0 ws0">maximized<span class="_"> </span>for<span class="_ _1"> </span>the<span class="_"> </span>current<span class="_ _d"> </span>state<span class="_ _d"> </span>of<span class="_ _d"> </span>the<span class="_"> </span>network,</div><div class="t m0 x28 he y66 ff1 fs7 fc0 sc0 ls0 ws0">necessarily<span class="_"> </span>disregarding<span class="_"> </span>the<span class="_"> </span>future<span class="_"> </span>network<span class="_"> </span>evo-</div><div class="t m0 x28 he y67 ff1 fs7 fc0 sc0 ls0 ws0">lution.<span class="_ _15"> </span>Under<span class="_ _15"> </span>heavy<span class="_ _15"> </span>load,<span class="_ _f"> </span>the<span class="_ _15"> </span>overall<span class="_ _15"> </span>network</div><div class="t m0 x28 he y68 ff1 fs7 fc0 sc0 ls0 ws0">bene&#64257;t<span class="_ _8"> </span>does<span class="_ _8"> </span>not<span class="_ _8"> </span>co<span class="_ _c"></span>incide<span class="_ _8"> </span>with<span class="_ _8"> </span>the<span class="_ _8"> </span>cost<span class="_ _8"> </span>fun<span class="_ _c"></span>ction<span class="_ _8"> </span>of</div><div class="t m0 x28 he y69 ff1 fs7 fc0 sc0 ls0 ws0">a<span class="_ _d"> </span>single<span class="_"> </span>call,<span class="_ _1"> </span>hen<span class="_ _c"></span>ce<span class="_ _d"> </span>the<span class="_"> </span>minimization<span class="_ _d"> </span>of<span class="_ _d"> </span>the<span class="_ _d"> </span>one</div><div class="t m0 x28 he y6a ff1 fs7 fc0 sc0 ls0 ws0">does<span class="_ _b"> </span>not<span class="_ _b"> </span>lead<span class="_ _b"> </span>to<span class="_ _7"> </span>the<span class="_ _b"> </span>maximization<span class="_ _7"> </span>of<span class="_ _b"> </span>the<span class="_ _b"> </span>other.</div><div class="t m0 x9 he y6b ff1 fs7 fc0 sc0 ls0 ws0">In<span class="_ _7"> </span>the<span class="_ _10"> </span>light<span class="_ _10"> </span>of<span class="_ _7"> </span>the<span class="_ _10"> </span>above<span class="_ _7"> </span>discussion,<span class="_ _10"> </span>the<span class="_ _10"> </span>draw-</div><div class="t m0 x28 he y6c ff1 fs7 fc0 sc0 ls0 ws0">back<span class="_ _f"> </span>of<span class="_ _13"> </span>QoS<span class="_ _15"> </span>routin<span class="_ _c"></span>g<span class="_ _f"> </span>in<span class="_ _13"> </span>the<span class="_ _15"> </span>Internet<span class="_ _13"> </span>is<span class="_ _f"> </span>clear:</div><div class="t m0 x28 he y6d ff1 fs7 fc0 sc0 ls0 ws0">whatever<span class="_ _0"> </span>is<span class="_ _0"> </span>gained<span class="_ _0"> </span>at<span class="_ _0"> </span>low<span class="_ _0"> </span>or<span class="_ _0"> </span>medium<span class="_ _0"> </span>network</div><div class="t m0 x28 he y6e ff1 fs7 fc0 sc0 ls0 ws0">loads,<span class="_ _8"> </span>it<span class="_ _4"> </span>is<span class="_ _8"> </span>paid<span class="_ _4"> </span>for<span class="_ _8"> </span>at<span class="_ _4"> </span>high<span class="_ _8"> </span>network<span class="_ _8"> </span>loads.<span class="_ _4"> </span>What<span class="_ _8"> </span>is</div><div class="t m0 x28 he y6f ff1 fs7 fc0 sc0 ls0 ws0">needed<span class="_"> </span>to<span class="_ _d"> </span>solve<span class="_ _d"> </span>this<span class="_"> </span>problem<span class="_ _d"> </span>is<span class="_"> </span>a<span class="_ _1"> </span>resilient<span class="_"> </span>algo-</div><div class="t m0 x28 he y70 ff1 fs7 fc0 sc0 ls0 ws0">rithm<span class="_ _d"> </span>that<span class="_ _d"> </span>allows<span class="_"> </span>the<span class="_ _1"> </span>migration<span class="_"> </span>of<span class="_ _1"> </span>a<span class="_"> </span>QoS-based</div><div class="t m0 x28 he y71 ff1 fs7 fc0 sc0 ls0 ws0">routing<span class="_ _4"> </span>algorithm<span class="_ _4"> </span>to<span class="_ _4"> </span>MH<span class="_ _4"> </span>routing<span class="_ _4"> </span>as<span class="_ _9"> </span><span class="ff8">q<span class="_ _4"> </span></span>grow<span class="_ _c"></span>s<span class="_ _4"> </span>large.</div><div class="t m0 x28 he y72 ff1 fs7 fc0 sc0 ls0 ws0">The<span class="_ _4"> </span>problem<span class="_ _4"> </span>is<span class="_ _4"> </span>that<span class="_ _9"> </span><span class="ff8">q<span class="_ _4"> </span></span>is<span class="_ _4"> </span>typically<span class="_ _4"> </span>not<span class="_ _4"> </span>known<span class="_ _4"> </span>to<span class="_ _4"> </span>the</div><div class="t m0 x28 he y73 ff1 fs7 fc0 sc0 ls0 ws0">routing<span class="_"> </span>algorithm,<span class="_ _e"> </span>not<span class="_"> </span>even<span class="_ _e"> </span>in<span class="_"> </span>the<span class="_"> </span>case<span class="_ _e"> </span>of<span class="_"> </span>cen-</div><div class="t m0 x28 he y74 ff1 fs7 fc0 sc0 ls0 ws0">tralized<span class="_ _b"> </span>routing<span class="_ _b"> </span>a<span class="_ _c"></span>lgorithms.</div><div class="t m0 x9 he y75 ff1 fs7 fc0 sc0 ls0 ws0">The<span class="_ _7"> </span>contribution<span class="_ _7"> </span>of<span class="_ _7"> </span>this<span class="_ _10"> </span>paper<span class="_ _b"> </span>lies<span class="_ _7"> </span>in<span class="_ _10"> </span>the<span class="_ _b"> </span>iden-</div><div class="t m0 x28 he y76 ff1 fs7 fc0 sc0 ls0 ws0">ti&#64257;cation<span class="_ _8"> </span>an<span class="_ _c"></span>d<span class="_ _8"> </span>de&#64257;nition<span class="_ _b"> </span>of<span class="_ _b"> </span>a<span class="_ _8"> </span>class<span class="_ _b"> </span>of<span class="_ _8"> </span>routin<span class="_ _c"></span>g<span class="_ _8"> </span>algo-</div><div class="t m0 x28 he y77 ff1 fs7 fc0 sc0 ls0 ws0">rithms,<span class="_ _4"> </span>named<span class="_ _9"> </span>Netwo<span class="_ _c"></span>rk<span class="_ _4"> </span>Graph<span class="_ _4"> </span>Reduction<span class="_ _9"> </span>(NG<span class="_ _c"></span>R),</div><div class="t m0 x28 he y78 ff1 fs7 fc0 sc0 ls0 ws0">whose<span class="_ _13"> </span>performance<span class="_ _f"> </span>en<span class="_ _c"></span>compasses<span class="_ _13"> </span>that<span class="_ _f"> </span>of<span class="_ _13"> </span>QoS-</div><div class="t m0 x28 he y79 ff1 fs7 fc0 sc0 ls0 ws0">based<span class="_ _15"> </span>routing<span class="_ _15"> </span>algorithms<span class="_ _f"> </span>at<span class="_ _15"> </span>light<span class="_ _15"> </span>and<span class="_ _15"> </span>medium</div><div class="t m0 x28 he y7a ff1 fs7 fc0 sc0 ls0 ws0">loads,<span class="_ _10"> </span>and<span class="_ _10"> </span>the<span class="_ _10"> </span>optimality<span class="_ _10"> </span>of<span class="_ _10"> </span>MH<span class="_ _10"> </span>routi<span class="_ _c"></span>ng<span class="_ _10"> </span>at<span class="_ _10"> </span>high</div><div class="t m0 x28 he y7b ff1 fs7 fc0 sc0 ls0 ws0">loads.<span class="_ _b"> </span>The<span class="_ _b"> </span>goal<span class="_ _8"> </span>is<span class="_ _b"> </span>obtaine<span class="_ _c"></span>d<span class="_ _8"> </span>by<span class="_ _b"> </span>red<span class="_ _c"></span>ucing<span class="_ _8"> </span>the<span class="_ _b"> </span>graph</div><div class="t m0 x28 he y7c ff1 fs7 fc0 sc0 ls0 ws0">that<span class="_ _8"> </span>describes<span class="_ _8"> </span>the<span class="_ _8"> </span>network<span class="_ _4"> </span>top<span class="_ _c"></span>ology,<span class="_ _8"> </span>and<span class="_ _8"> </span>applying</div><div class="t m0 x28 he y7d ff1 fs7 fc0 sc0 ls0 ws0">a<span class="_ _8"> </span>suitable<span class="_ _4"> </span>metric<span class="_ _8"> </span>to<span class="_ _8"> </span>the<span class="_ _4"> </span>red<span class="_ _c"></span>uced<span class="_ _4"> </span>graph<span class="_ _c"></span>.<span class="_ _8"> </span>Results<span class="_ _4"> </span>are</div><div class="t m0 x28 he y7e ff1 fs7 fc0 sc0 ls0 ws0">reported<span class="_ _a"> </span>showing<span class="_ _9"> </span>both<span class="_ _a"> </span>the<span class="_ _a"> </span>elem<span class="_ _c"></span>entary<span class="_ _a"> </span>propert<span class="_ _c"></span>ies<span class="_ _a"> </span>of</div><div class="t m0 x28 he y7f ff1 fs7 fc0 sc0 ls0 ws0">the<span class="_ _10"> </span>algorithm,<span class="_ _10"> </span>and<span class="_ _7"> </span>its<span class="_ _10"> </span>behavior<span class="_ _10"> </span>in<span class="_ _7"> </span>randomly<span class="_ _10"> </span>gen-</div><div class="t m0 x28 he y80 ff1 fs7 fc0 sc0 ls0 ws0">erated<span class="_ _0"> </span>topologies,<span class="_ _0"> </span>both<span class="_ _e"> </span>with<span class="_ _0"> </span>uniform<span class="_ _0"> </span>and<span class="_ _0"> </span>non-</div><div class="t m0 x28 he y81 ff1 fs7 fc0 sc0 ls0 ws0">uniform,<span class="_ _8"> </span>time-varying<span class="_ _8"> </span>tra&#64259;c.</div><div class="t m0 x9 he y82 ff1 fs7 fc0 sc0 ls0 ws0">The<span class="_ _1"> </span>rest<span class="_ _1"> </span>of<span class="_ _1"> </span>the<span class="_ _1"> </span>paper<span class="_ _1"> </span>is<span class="_ _1"> </span>organized<span class="_ _1"> </span>as<span class="_ _1"> </span>follows.</div><div class="t m0 x28 he y83 ff1 fs7 fc0 sc0 ls0 ws0">Section<span class="_ _e"> </span>2<span class="_ _0"> </span>provides<span class="_ _e"> </span>a<span class="_ _0"> </span>general<span class="_ _e"> </span>description<span class="_ _0"> </span>of<span class="_ _e"> </span>the</div><div class="t m0 x28 he y84 ff1 fs7 fc0 sc0 ls0 ws0">NGR<span class="_ _0"> </span>algorithm,<span class="_ _e"> </span>along<span class="_ _0"> </span>with<span class="_ _0"> </span>implementation<span class="_ _0"> </span>is-</div><div class="t m0 x28 he y85 ff1 fs7 fc0 sc0 ls0 ws0">sues.<span class="_"> </span>Section<span class="_"> </span>3<span class="_"> </span>presents<span class="_"> </span>the<span class="_"> </span>netwo<span class="_ _c"></span>rk<span class="_"> </span>and<span class="_"> </span>tra&#64259;c</div><div class="t m0 x28 he y86 ff1 fs7 fc0 sc0 ls0 ws0">models<span class="_ _4"> </span>us<span class="_ _c"></span>ed<span class="_ _4"> </span>in<span class="_ _8"> </span>the<span class="_ _4"> </span>simulation<span class="_ _8"> </span>presented<span class="_ _4"> </span>in<span class="_ _4"> </span>Secti<span class="_ _c"></span>on</div><div class="t m0 x28 he y87 ff1 fs7 fc0 sc0 ls0 ws0">4,<span class="_ _9"> </span>in<span class="_ _4"> </span>which<span class="_ _9"> </span>the<span class="_ _9"> </span>perfor<span class="_ _c"></span>mance<span class="_ _9"> </span>of<span class="_ _4"> </span>the<span class="_ _9"> </span>NGR<span class="_ _9"> </span>algorithm</div><div class="t m0 x28 he y88 ff1 fs7 fc0 sc0 ls0 ws0">is<span class="_ _7"> </span>compared<span class="_ _7"> </span>to<span class="_ _7"> </span>the<span class="_ _7"> </span>one<span class="_ _10"> </span>of<span class="_ _b"> </span>classic<span class="_ _10"> </span>QoS<span class="_ _b"> </span>routin<span class="_ _c"></span>g<span class="_ _7"> </span>al-</div><div class="t m0 x28 he y89 ff1 fs7 fc0 sc0 ls0 ws0">gorithms,<span class="_ _4"> </span>both<span class="_ _4"> </span>in<span class="_ _4"> </span>simple<span class="_ _4"> </span>network<span class="_ _4"> </span>scenarios,<span class="_ _4"> </span>and<span class="_ _4"> </span>in</div><div class="t m0 x28 he y8a ff1 fs7 fc0 sc0 ls0 ws0">more<span class="_ _1"> </span>complex<span class="_ _1"> </span>ones.<span class="_ _10"> </span>Finall<span class="_ _c"></span>y,<span class="_ _1"> </span>conclusions<span class="_ _1"> </span>and<span class="_ _10"> </span>fu-</div><div class="t m0 x28 he y8b ff1 fs7 fc0 sc0 ls0 ws0">ture<span class="_ _b"> </span>work<span class="_ _b"> </span>are<span class="_ _b"> </span>discus<span class="_ _c"></span>sed<span class="_ _b"> </span>in<span class="_ _b"> </span>Section<span class="_ _7"> </span>5.</div><div class="t m0 x28 hd y8c ff6 fs7 fc0 sc0 ls0 ws0">2.<span class="_ _b"> </span>NGR<span class="_ _b"> </span>routing<span class="_ _7"> </span>algorithms</div><div class="t m0 x9 he y8d ff1 fs7 fc0 sc0 ls0 ws0">Routing<span class="_ _1"> </span>can<span class="_ _d"> </span>be<span class="_ _1"> </span>form<span class="_ _c"></span>alized<span class="_ _1"> </span>as<span class="_ _d"> </span>the<span class="_ _1"> </span>problem<span class="_ _d"> </span>of</div><div class="t m0 x28 he y8e ff1 fs7 fc0 sc0 ls0 ws0">&#64257;nding<span class="_ _15"> </span>a<span class="_ _15"> </span>suitable<span class="_ _15"> </span>set<span class="_ _15"> </span>of<span class="_ _15"> </span>edges<span class="_ _f"> </span>connecting<span class="_ _15"> </span>two</div><div class="t m0 x28 he y8f ff1 fs7 fc0 sc0 ls0 ws0">nodes<span class="_ _10"> </span>in<span class="_ _1"> </span>a<span class="_ _10"> </span>direct<span class="_ _c"></span>ed<span class="_ _10"> </span>graph.<span class="_ _1"> </span>QoS<span class="_ _10"> </span>routing<span class="_ _1"> </span>relies<span class="_ _10"> </span>on</div><div class="t m0 x28 he y90 ff1 fs7 fc0 sc0 ls0 ws0">the<span class="_ _1"> </span>de&#64257;nition<span class="_ _1"> </span>of<span class="_ _1"> </span>a<span class="_ _10"> </span>suitable<span class="_ _1"> </span>edge<span class="_ _1"> </span>metric<span class="_ _1"> </span><span class="ff5">w</span>,<span class="_ _1"> </span>which</div><div class="t m4 x20 h7 y91 ff1 fs4 fc0 sc0 ls0 ws0">1</div><div class="t m0 x29 ha y2f ff1 fs5 fc0 sc0 ls0 ws0">In<span class="_ _a"> </span>this<span class="_ _a"> </span>paper<span class="_ _a"> </span>we<span class="_ _a"> </span>refer<span class="_ _a"> </span>to<span class="_ _a"> </span>the<span class="_ _a"> </span>MH<span class="_ _a"> </span>algorithm<span class="_ _a"> </span>as<span class="_ _17"> </span>a<span class="_ _a"> </span>special<span class="_ _17"> </span>case</div><div class="t m0 x25 ha y30 ff1 fs5 fc0 sc0 ls0 ws0">of<span class="_ _4"> </span>the<span class="_ _4"> </span>Shortest<span class="_ _4"> </span>Path,<span class="_ _4"> </span>in<span class="_ _4"> </span>which<span class="_ _4"> </span>all<span class="_ _4"> </span>links<span class="_ _4"> </span>have<span class="_ _4"> </span>unitary<span class="_ _4"> </span>costs.</div><div class="t m0 x25 ha y92 ff1 fs5 fc0 sc0 ls0 ws0">476<span class="_ _18"> </span><span class="ff4">C.<span class="_ _4"> </span>Casetti<span class="_ _4"> </span>et<span class="_ _4"> </span>al.<span class="_ _4"> </span>/<span class="_ _4"> </span>Computer<span class="_ _4"> </span>Networks<span class="_ _4"> </span>41<span class="_ _4"> </span>(2003)<span class="_ _4"> </span>475&#8211;487</span></div></div><div class="pi" data-data='{"ctm":[1.764706,0.000000,0.000000,1.764706,0.000000,0.000000]}'></div></div><div id="pf3" class="pf w0 h0" data-page-no="3"><div class="pc pc3 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="/image.php?url=https://csdnimg.cn/release/download_crawler_static/89628520/bg3.jpg"><div class="t m0 x1b he y36 ff1 fs7 fc0 sc0 ls0 ws0">depends<span class="_ _e"> </span>on<span class="_ _0"> </span>the<span class="_ _e"> </span>networks<span class="_ _e"> </span>statu<span class="_ _c"></span>s,<span class="_ _e"> </span>and<span class="_ _0"> </span>of<span class="_ _e"> </span>a<span class="_ _e"> </span>cost</div><div class="t m0 x1b h11 y37 ff1 fs7 fc0 sc0 ls0 ws0">function<span class="_ _e"> </span><span class="ff5">c<span class="ff9">&#240;&#58882;&#222;<span class="_ _c"></span></span></span>,<span class="_ _e"> </span>which<span class="_ _0"> </span>should<span class="_ _e"> </span>be<span class="_ _e"> </span>minimiz<span class="_ _c"></span>ed/maxi-</div><div class="t m0 x1b he y93 ff1 fs7 fc0 sc0 ls0 ws0">mized,<span class="_ _10"> </span>yielding<span class="_ _10"> </span>the<span class="_ _10"> </span>optimal<span class="_ _1"> </span>route<span class="_ _10"> </span>selection<span class="_ _10"> </span>under</div><div class="t m0 x1b he y94 ff1 fs7 fc0 sc0 ls0 ws0">speci&#64257;c<span class="_"> </span>network<span class="_"> </span>conditions.<span class="_"> </span>As<span class="_"> </span>discussed<span class="_"> </span>in<span class="_"> </span>the</div><div class="t m0 x1b he y95 ff1 fs7 fc0 sc0 ls0 ws0">Introduction,<span class="_ _10"> </span>however,<span class="_ _10"> </span>all<span class="_ _10"> </span>metrics<span class="_ _10"> </span>and<span class="_ _10"> </span>cost<span class="_ _10"> </span>func-</div><div class="t m0 x1b he y96 ff1 fs7 fc0 sc0 ls0 ws0">tions<span class="_ _7"> </span>that<span class="_ _7"> </span>try<span class="_ _7"> </span>to<span class="_ _7"> </span>maximize<span class="_ _7"> </span>network<span class="_ _10"> </span>utilization<span class="_ _7"> </span>or/</div><div class="t m0 x1b he y97 ff1 fs7 fc0 sc0 ls0 ws0">and<span class="_ _1"> </span>user<span class="_ _1"> </span>throughput<span class="_ _1"> </span>su&#64256;er<span class="_ _10"> </span>from<span class="_ _1"> </span>the<span class="_ _1"> </span>same<span class="_ _1"> </span>draw-</div><div class="t m0 x1b h11 y98 ff1 fs7 fc0 sc0 ls0 ws0">back:<span class="_ _8"> </span>as<span class="_ _8"> </span>the<span class="_ _8"> </span>network<span class="_ _8"> </span>load<span class="_ _8"> </span>increases<span class="_ _8"> </span>(<span class="ff8">q<span class="_ _4"> </span><span class="ff9 ls2">!1<span class="_ _19"></span><span class="ff1 ls0">)<span class="_ _8"> </span>their</span></span></span></div><div class="t m0 x1b he y99 ff1 fs7 fc0 sc0 ls0 ws0">performance<span class="_"> </span>dro<span class="_ _c"></span>ps<span class="_"> </span>below<span class="_ _e"> </span>that<span class="_"> </span>of<span class="_"> </span>a<span class="_ _e"> </span>simple<span class="_"> </span>MH</div><div class="t m0 x1b he y9a ff1 fs7 fc0 sc0 ls0 ws0">algorithm.<span class="_ _b"> </span>Finding<span class="_ _7"> </span>metrics<span class="_ _b"> </span>that<span class="_ _b"> </span>let<span class="_ _7"> </span>the<span class="_ _b"> </span>path<span class="_ _b"> </span>selec<span class="_ _c"></span>-</div><div class="t m0 x1b he y9b ff1 fs7 fc0 sc0 ls0 ws0">tion<span class="_ _0"> </span>process<span class="_ _0"> </span>converge<span class="_ _0"> </span>to<span class="_ _0"> </span>MH<span class="_ _0"> </span>routing<span class="_ _0"> </span>as<span class="_ _e"> </span><span class="ff8">q<span class="_ _0"> </span></span>in-</div><div class="t m0 x1b he y9c ff1 fs7 fc0 sc0 ls0 ws0">creases<span class="_ _7"> </span>seems<span class="_ _7"> </span>to<span class="_ _7"> </span>be<span class="_ _7"> </span>a<span class="_ _7"> </span>hard<span class="_ _7"> </span>problem.<span class="_ _7"> </span>As<span class="_ _7"> </span>shown<span class="_ _7"> </span>in</div><div class="t m0 x1b he y9d ff1 fs7 fc0 sc0 ls0 ws0">[16]<span class="_ _d"> </span>the<span class="_ _1"> </span>elastic<span class="_"> </span>nature<span class="_ _1"> </span>of<span class="_"> </span>the<span class="_ _1"> </span>Internet<span class="_ _d"> </span>tra&#64259;c<span class="_ _d"> </span>just</div><div class="t m0 x1b he y9e ff1 fs7 fc0 sc0 ls0 ws0">worsens<span class="_ _d"> </span>the<span class="_ _d"> </span>problem.<span class="_ _d"> </span>The<span class="_ _d"> </span>di&#64259;culty<span class="_ _d"> </span>of<span class="_ _d"> </span>&#64257;nding<span class="_ _d"> </span>a</div><div class="t m0 x1b he y9f ff1 fs7 fc0 sc0 ls0 ws0">suitable<span class="_ _4"> </span>metr<span class="_ _c"></span>ic<span class="_ _4"> </span>lies<span class="_ _8"> </span>in<span class="_ _4"> </span>the<span class="_ _8"> </span>fact<span class="_ _4"> </span>that<span class="_ _8"> </span>the<span class="_ _4"> </span>goal<span class="_ _8"> </span>of<span class="_ _4"> </span>such</div><div class="t m0 x1b he ya0 ff1 fs7 fc0 sc0 ls0 ws0">a<span class="_"> </span>metric<span class="_ _0"> </span>should<span class="_"> </span>change<span class="_ _e"> </span>with<span class="_ _e"> </span>the<span class="_ _e"> </span>ne<span class="_ _c"></span>twork<span class="_ _e"> </span>load,</div><div class="t m0 x1b he ya1 ff1 fs7 fc0 sc0 ls0 ws0">making<span class="_ _7"> </span>the<span class="_ _10"> </span>problem<span class="_ _7"> </span>not<span class="_ _7"> </span>e<span class="_ _c"></span>asily<span class="_ _7"> </span>tackled<span class="_ _10"> </span>by<span class="_ _7"> </span>a<span class="_ _7"> </span>stan-</div><div class="t m0 x1b he ya2 ff1 fs7 fc0 sc0 ls0 ws0">dard<span class="_ _b"> </span>minimization<span class="_ _7"> </span>approach.</div><div class="t m0 x1c he ya3 ff1 fs7 fc0 sc0 ls0 ws0">Indeed,<span class="_ _e"> </span>we<span class="_ _0"> </span>can<span class="_"> </span>look<span class="_ _0"> </span>at<span class="_"> </span>the<span class="_ _0"> </span>routing<span class="_ _e"> </span>problem</div><div class="t m0 x1b he ya4 ff1 fs7 fc0 sc0 ls0 ws0">from<span class="_ _e"> </span>a<span class="_"> </span>sligh<span class="_ _c"></span>tly<span class="_"> </span>mod<span class="_ _c"></span>i&#64257;ed<span class="_"> </span>perspect<span class="_ _c"></span>ive.<span class="_ _e"> </span>Instead<span class="_ _e"> </span>of</div><div class="t m0 x1b he ya5 ff1 fs7 fc0 sc0 ls0 ws0">trying<span class="_"> </span>to<span class="_ _d"> </span>&#64257;nd<span class="_ _d"> </span>adaptive<span class="_"> </span>metrics,<span class="_"> </span>the<span class="_ _d"> </span>same<span class="_"> </span>metric</div><div class="t m0 x1b he ya6 ff1 fs7 fc0 sc0 ls0 ws0">that<span class="_ _10"> </span>works<span class="_ _1"> </span>well<span class="_ _10"> </span>for<span class="_ _10"> </span>light<span class="_ _1"> </span>loads<span class="_ _10"> </span>can<span class="_ _10"> </span>be<span class="_ _1"> </span>applied<span class="_ _10"> </span>at</div><div class="t m0 x1b he ya7 ff1 fs7 fc0 sc0 ls0 ws0">high<span class="_ _10"> </span>loads<span class="_ _1"> </span>to<span class="_ _10"> </span>a<span class="_ _1"> </span><span class="ff4">reduced<span class="_ _10"> </span>graph<span class="_ _1"> </span></span>that<span class="_ _10"> </span>only<span class="_ _1"> </span>contains</div><div class="t m0 x1b he ya8 ff1 fs7 fc0 sc0 ls0 ws0">uncongested<span class="_ _8"> </span>links,<span class="_ _4"> </span>i.e.,<span class="_ _8"> </span>links<span class="_ _8"> </span>whose<span class="_ _4"> </span>load<span class="_ _8"> </span>is<span class="_ _4"> </span>under<span class="_ _8"> </span>a</div><div class="t m0 x1b he ya9 ff1 fs7 fc0 sc0 ls0 ws0">given<span class="_ _b"> </span>threshold.<span class="_ _b"> </span>Since<span class="_ _7"> </span>the<span class="_ _b"> </span>reduced<span class="_ _b"> </span>graph<span class="_ _7"> </span>may<span class="_ _b"> </span>not</div><div class="t m0 x1b he yaa ff1 fs7 fc0 sc0 ls0 ws0">be<span class="_ _4"> </span>connected,<span class="_ _4"> </span>i.e.,<span class="_ _4"> </span>no<span class="_ _4"> </span>path<span class="_ _4"> </span>may<span class="_ _8"> </span>exist<span class="_ _9"> </span>from<span class="_ _8"> </span>a<span class="_ _9"> </span>source</div><div class="t m0 x1b he yab ff1 fs7 fc0 sc0 ls0 ws0">to<span class="_"> </span>a<span class="_"> </span>destination,<span class="_"> </span>the<span class="_"> </span>minimum-hop<span class="_"> </span>path<span class="_"> </span>should</div><div class="t m0 x1b he yac ff1 fs7 fc0 sc0 ls0 ws0">always<span class="_ _0"> </span>be<span class="_ _15"> </span>included<span class="_ _15"> </span>as<span class="_ _15"> </span>possible<span class="_ _15"> </span>solution<span class="_ _0"> </span>of<span class="_ _15"> </span>the</div><div class="t m0 x1b he yad ff1 fs7 fc0 sc0 ls0 ws0">routing<span class="_ _13"> </span>problem.<span class="_ _13"> </span>Thus,<span class="_ _f"> </span>as<span class="_ _13"> </span>the<span class="_ _13"> </span>o&#64256;ered<span class="_ _f"> </span>load<span class="_ _13"> </span><span class="ff8">q</span></div><div class="t m0 x1b he yae ff1 fs7 fc0 sc0 ls0 ws0">grows,<span class="_ _d"> </span>all<span class="_ _1"> </span>links<span class="_ _d"> </span>become<span class="_ _d"> </span>congested<span class="_ _d"> </span>and<span class="_ _1"> </span>the<span class="_ _d"> </span>algo-</div><div class="t m0 x1b he yaf ff1 fs7 fc0 sc0 ls0 ws0">rithm<span class="_ _b"> </span>necessarily<span class="_ _7"> </span>chooses<span class="_ _7"> </span>the<span class="_ _b"> </span>minimum-<span class="_ _c"></span>hop<span class="_ _b"> </span>path.</div><div class="t m0 x1b he yb0 ff1 fs7 fc0 sc0 ls0 ws0">While<span class="_ _7"> </span>the<span class="_ _b"> </span>direct<span class="_ _7"> </span>measure<span class="_ _7"> </span>(or<span class="_ _7"> </span>evaluation)<span class="_ _7"> </span>of<span class="_ _b"> </span><span class="ff8">q<span class="_ _7"> </span></span>is<span class="_ _7"> </span>a</div><div class="t m0 x1b he yb1 ff1 fs7 fc0 sc0 ls0 ws0">complex<span class="_ _4"> </span>task,<span class="_ _4"> </span>the<span class="_ _9"> </span>identi<span class="_ _c"></span>&#64257;cation<span class="_ _4"> </span>of<span class="_ _4"> </span>single<span class="_ _9"> </span>c<span class="_ _c"></span>ongested</div><div class="t m0 x1b he yb2 ff1 fs7 fc0 sc0 ls0 ws0">links<span class="_ _b"> </span>is<span class="_ _7"> </span>extremely<span class="_ _7"> </span>easy,<span class="_ _b"> </span>so<span class="_ _7"> </span>that,<span class="_ _7"> </span>overall,<span class="_ _b"> </span>the<span class="_ _7"> </span>meth-</div><div class="t m0 x1b he yb3 ff1 fs7 fc0 sc0 ls0 ws0">odology<span class="_ _8"> </span>is<span class="_ _8"> </span>simple<span class="_ _8"> </span>and<span class="_ _8"> </span>its<span class="_ _8"> </span>implementation<span class="_ _8"> </span>straight-</div><div class="t m0 x1b he yb4 ff1 fs7 fc0 sc0 ls0 ws0">forward.</div><div class="t m0 x1c he yb5 ff1 fs7 fc0 sc0 ls0 ws0">This<span class="_ _9"> </span>key<span class="_ _4"> </span>idea<span class="_ _9"> </span>leads<span class="_ _4"> </span>to<span class="_ _4"> </span>the<span class="_ _9"> </span>de&#64257;nition<span class="_ _4"> </span>of<span class="_ _9"> </span>the<span class="_ _4"> </span>NGR</div><div class="t m0 x1b he yb6 ff1 fs7 fc0 sc0 ls0 ws0">strategy<span class="_ _8"> </span>which<span class="_ _b"> </span>can<span class="_ _8"> </span>be<span class="_ _8"> </span>applied<span class="_ _b"> </span>to<span class="_ _8"> </span>any<span class="_ _8"> </span>existing<span class="_ _b"> </span>QoS</div><div class="t m0 x1b he yb7 ff1 fs7 fc0 sc0 ls0 ws0">routing<span class="_ _b"> </span>algorithms<span class="_ _c"></span>.</div><div class="t m0 x1b h12 yb8 ff4 fs7 fc0 sc0 ls0 ws0">2.1.<span class="_ _b"> </span>Formal<span class="_ _b"> </span>descri<span class="_ _c"></span>ption</div><div class="t m0 x1c he yb9 ff1 fs7 fc0 sc0 ls0 ws0">For<span class="_ _15"> </span>the<span class="_ _f"> </span>purpose<span class="_ _f"> </span>of<span class="_ _f"> </span>providing<span class="_ _f"> </span>a<span class="_ _15"> </span>formal<span class="_ _f"> </span>de-</div><div class="t m0 x1b he yba ff1 fs7 fc0 sc0 ls0 ws0">scription<span class="_ _7"> </span>of<span class="_ _10"> </span>the<span class="_ _7"> </span>class<span class="_ _10"> </span>of<span class="_ _7"> </span>NGR<span class="_ _10"> </span>algorithms<span class="_ _7"> </span>in<span class="_ _10"> </span>their</div><div class="t m0 x1b he ybb ff1 fs7 fc0 sc0 ls0 ws0">most<span class="_ _9"> </span>general<span class="_ _4"> </span>form,<span class="_ _4"> </span>we<span class="_ _4"> </span>use<span class="_ _9"> </span>a<span class="_ _4"> </span>standard<span class="_ _4"> </span>graph<span class="_ _9"> </span>theory</div><div class="t m0 x1b he ybc ff1 fs7 fc0 sc0 ls0 ws0">formalism.<span class="_ _b"> </span>Thus,<span class="_ _8"> </span>we<span class="_ _b"> </span>refer<span class="_ _b"> </span>to<span class="_ _b"> </span>a<span class="_ _b"> </span>generic<span class="_ _b"> </span>network<span class="_ _8"> </span>as</div><div class="t m0 x1b h11 ybd ff1 fs7 fc0 sc0 ls0 ws0">a<span class="_ _4"> </span>directed<span class="_ _8"> </span>graph<span class="_ _4"> </span><span class="ffa">G<span class="_ _4"> </span><span class="ff9 ls3">&#188;&#240;<span class="_ _19"></span><span class="ffa ls0">V<span class="ffb">;<span class="_ _17"> </span></span>E<span class="ff9">&#222;<span class="ff1">,<span class="_ _4"> </span>where<span class="_ _4"> </span></span></span>V<span class="_ _8"> </span><span class="ff1">is<span class="_ _4"> </span>the<span class="_ _4"> </span>set<span class="_ _4"> </span>of</span></span></span></span></div><div class="t m0 x1b he ybe ff1 fs7 fc0 sc0 ls0 ws0">vertices<span class="_ _1"> </span>(nodes,<span class="_ _1"> </span>in<span class="_ _1"> </span>our<span class="_ _1"> </span>case),<span class="_ _1"> </span>and<span class="_ _1"> </span><span class="ffa">E<span class="_ _d"> </span></span>is<span class="_ _1"> </span>the<span class="_ _1"> </span>set<span class="_ _1"> </span>of</div><div class="t m0 x1d he ybf ff1 fs7 fc0 sc0 ls0 ws0">edges<span class="_ _1a"> </span>(links).</div><div class="t m6 x2a h10 yc0 ff1 fs8 fc0 sc0 ls0 ws0">2</div><div class="t m0 x2b h11 y36 ff1 fs7 fc0 sc0 ls0 ws0">A<span class="_ _1a"> </span>path<span class="_ _1a"> </span><span class="ff8">p<span class="ff9">&#240;<span class="ff5">v</span></span></span></div><div class="t m0 x2c h13 yc1 ff5 fs9 fc0 sc0 ls0 ws0">s</div><div class="t m0 x2d h14 y36 ffb fs7 fc0 sc0 ls0 ws0">;<span class="_ _17"> </span><span class="ff5">v</span></div><div class="t m0 x2e h13 yc1 ff5 fs9 fc0 sc0 ls0 ws0">d</div><div class="t m0 x2f h11 y36 ff9 fs7 fc0 sc0 ls0 ws0">&#222;<span class="_ _1a"> </span><span class="ff1">of<span class="_ _1a"> </span>length</span></div><div class="t m0 x1d h11 y37 ff5 fs7 fc0 sc0 ls0 ws0">n<span class="_ _4"> </span><span class="ff9 ls4">&#188;j<span class="_ _19"></span>j<span class="_ _1b"></span><span class="ff8 ls0">p<span class="ff9">&#240;<span class="ff5">v</span></span></span></span></div><div class="t m0 x30 h13 yc2 ff5 fs9 fc0 sc0 ls0 ws0">s</div><div class="t m0 x31 h14 y39 ffb fs7 fc0 sc0 ls0 ws0">;<span class="_ _17"> </span><span class="ff5">v</span></div><div class="t m0 x32 h13 yc2 ff5 fs9 fc0 sc0 ls0 ws0">d</div><div class="t m0 x33 h11 y39 ff9 fs7 fc0 sc0 ls0 ws0">&#222;jj<span class="_ _9"> </span><span class="ff1">is<span class="_ _9"> </span>de&#64257;ned<span class="_ _4"> </span>as<span class="_ _9"> </span>a<span class="_ _9"> </span>sequence<span class="_ _9"> </span>of<span class="_ _4"> </span><span class="ff5">n<span class="_ _9"> </span></span>distinct</span></div><div class="t m0 x1d he y3a ff1 fs7 fc0 sc0 ls0 ws0">edges<span class="_ _8"> </span><span class="ff5">e</span></div><div class="t m0 x34 h13 yc3 ff5 fs9 fc0 sc0 ls0 ws0">i</div><div class="t m0 x35 he yc4 ff1 fs7 fc0 sc0 ls0 ws0">joining<span class="_ _8"> </span><span class="ff5">v</span></div><div class="t m0 x36 h13 yc3 ff5 fs9 fc0 sc0 ls0 ws0">s</div><div class="t m0 x37 he yc4 ff1 fs7 fc0 sc0 ls0 ws0">and<span class="_ _4"> </span><span class="ff5">v</span></div><div class="t m0 x38 h13 yc3 ff5 fs9 fc0 sc0 ls0 ws0">d</div><div class="t m0 x24 he yc4 ff1 fs7 fc0 sc0 ls0 ws0">,<span class="_ _4"> </span>where<span class="_ _8"> </span><span class="ff5">v</span></div><div class="t m0 x2d h13 yc3 ff5 fs9 fc0 sc0 ls0 ws0">s</div><div class="t m0 x39 h14 yc4 ffb fs7 fc0 sc0 ls0 ws0">;<span class="_ _17"> </span><span class="ff5">v</span></div><div class="t m0 x3a h13 yc3 ff5 fs9 fc0 sc0 ls0 ws0">d</div><div class="t m0 x3b h11 yc4 ff9 fs7 fc0 sc0 ls0 ws0">2<span class="_ _4"> </span><span class="ffa">V<span class="ff1">,<span class="_ _8"> </span><span class="ff5">e</span></span></span></div><div class="t m0 x3c h13 yc3 ff5 fs9 fc0 sc0 ls0 ws0">i</div><div class="t m0 x3d h11 yc4 ff9 fs7 fc0 sc0 ls0 ws0">2<span class="_ _4"> </span><span class="ffa">E<span class="ff1">,</span></span></div><div class="t m0 x1d h11 yc5 ff8 fs7 fc0 sc0 ls0 ws0">p<span class="ff9">&#240;<span class="ff5">v</span></span></div><div class="t m0 x3e h13 yc6 ff5 fs9 fc0 sc0 ls0 ws0">s</div><div class="t m0 x9 h14 yc7 ffb fs7 fc0 sc0 ls0 ws0">;<span class="_ _17"> </span><span class="ff5">v</span></div><div class="t m0 x3f h13 yc6 ff5 fs9 fc0 sc0 ls0 ws0">d</div><div class="t m0 x40 h11 yc7 ff9 fs7 fc0 sc0 ls5 ws0">&#222;&#188;f<span class="_ _1b"></span><span class="ff5 ls0">e</span></div><div class="t m0 x41 h15 yc6 ff1 fs9 fc0 sc0 ls0 ws0">1</div><div class="t m0 x42 h14 yc7 ffb fs7 fc0 sc0 ls0 ws0">;<span class="_ _17"> </span><span class="ff5">e</span></div><div class="t m0 x43 h15 yc6 ff1 fs9 fc0 sc0 ls0 ws0">2</div><div class="t m0 x36 h14 yc7 ffb fs7 fc0 sc0 ls0 ws0">;<span class="_ _17"> </span><span class="ff3 ls6">...</span>;<span class="_ _17"> </span><span class="ff5">e</span></div><div class="t m0 x44 h13 yc6 ff5 fs9 fc0 sc0 ls0 ws0">n</div><div class="t m0 x45 h11 yc7 ff9 fs7 fc0 sc0 ls0 ws0">g<span class="ff1">.</span></div><div class="t m0 x1e he yc8 ff1 fs7 fc0 sc0 ls0 ws0">A<span class="_ _10"> </span>set<span class="_ _1"> </span><span class="ffa">P</span></div><div class="t m0 x46 h16 yc9 ffa fs9 fc0 sc0 ls0 ws0">G</div><div class="t m0 x47 he yca ff1 fs7 fc0 sc0 ls0 ws0">is<span class="_ _10"> </span>de&#64257;ned<span class="_ _1"> </span>as<span class="_ _10"> </span>the<span class="_ _10"> </span>set<span class="_ _1"> </span>of<span class="_ _10"> </span>all<span class="_ _1"> </span>paths<span class="_ _10"> </span>ex-</div><div class="t m0 x1d he ycb ff1 fs7 fc0 sc0 ls0 ws0">isting<span class="_ _7"> </span>between<span class="_ _10"> </span>any<span class="_ _b"> </span>tw<span class="_ _c"></span>o<span class="_ _7"> </span>distinct<span class="_ _10"> </span>vertices<span class="_ _7"> </span>of<span class="_ _7"> </span><span class="ffa">G</span>,<span class="_ _7"> </span>i.e.<span class="_ _c"></span>,</div><div class="t m0 x1d h17 ycc ffa fs7 fc0 sc0 ls0 ws0">P</div><div class="t m0 x48 h16 ycd ffa fs9 fc0 sc0 ls0 ws0">G</div><div class="t m0 x49 h11 yce ff9 fs7 fc0 sc0 ls4 ws0">&#188;f<span class="_ _1b"></span><span class="ff8 ls0">p<span class="ff9">&#240;<span class="ff5">v</span></span></span></div><div class="t m0 x4a h13 ycd ff5 fs9 fc0 sc0 ls0 ws0">s</div><div class="t m0 x4b h14 yce ffb fs7 fc0 sc0 ls0 ws0">;<span class="_ _17"> </span><span class="ff5">v</span></div><div class="t m0 x47 h13 ycd ff5 fs9 fc0 sc0 ls0 ws0">d</div><div class="t m0 x4c h11 yce ff9 fs7 fc0 sc0 ls0 ws0">&#222;j<span class="ff5">v</span></div><div class="t m0 x36 h13 ycd ff5 fs9 fc0 sc0 ls0 ws0">s</div><div class="t m0 x4d h14 yce ffb fs7 fc0 sc0 ls0 ws0">;<span class="_ _17"> </span><span class="ff5">v</span></div><div class="t m0 x4e h13 ycd ff5 fs9 fc0 sc0 ls0 ws0">d</div><div class="t m0 x4f h11 yce ff9 fs7 fc0 sc0 ls0 ws0">2<span class="_ _4"> </span><span class="ffa">V<span class="ffb">;<span class="_ _17"> </span><span class="ff5">v</span></span></span></div><div class="t m0 x50 h13 ycd ff5 fs9 fc0 sc0 ls0 ws0">s</div><div class="t m0 x51 h11 yce ff9 fs7 fc0 sc0 ls0 ws0">6&#188;<span class="_ _4"> </span><span class="ff5">v</span></div><div class="t m0 x52 h13 ycd ff5 fs9 fc0 sc0 ls0 ws0">d</div><div class="t m0 x2d h11 yce ff9 fs7 fc0 sc0 ls0 ws0">g<span class="ff1">.<span class="_ _13"> </span>Each<span class="_ _f"> </span>link<span class="_ _13"> </span>is</span></div><div class="t m0 x1d he ycf ff1 fs7 fc0 sc0 ls0 ws0">assigned<span class="_ _1"> </span>a<span class="_"> </span>weight<span class="_ _1"> </span><span class="ff5">w<span class="_ _d"> </span></span>using<span class="_ _d"> </span>any<span class="_ _1"> </span>metric<span class="_"> </span>that<span class="_ _1"> </span>com-</div><div class="t m0 x1d he yd0 ff1 fs7 fc0 sc0 ls0 ws0">bines<span class="_ _10"> </span>topological,<span class="_ _10"> </span>physical<span class="_ _10"> </span>or<span class="_ _10"> </span>tra&#64259;c-related<span class="_ _10"> </span>ch<span class="_ _c"></span>ar-</div><div class="t m0 x1d h11 yd1 ff1 fs7 fc0 sc0 ls0 ws0">acteristics<span class="_ _9"> </span>of<span class="_ _4"> </span>that<span class="_ _9"> </span>link.<span class="_ _9"> </span>To<span class="_ _4"> </span>each<span class="_ _9"> </span>path<span class="_ _9"> </span><span class="ff8">p<span class="_ _9"> </span></span>a<span class="_ _4"> </span>cost<span class="_ _9"> </span><span class="ff5">c<span class="ff9">&#240;<span class="ff8">p</span>&#222;<span class="_ _9"> </span></span></span>is</div><div class="t m0 x1d he yd2 ff1 fs7 fc0 sc0 ls0 ws0">assigned<span class="_ _8"> </span>using<span class="_ _b"> </span>a<span class="_ _b"> </span>combination<span class="_ _b"> </span>of<span class="_ _8"> </span>the<span class="_ _b"> </span>weights<span class="_ _b"> </span>of<span class="_ _8"> </span>its</div><div class="t m0 x1d h11 yd3 ff1 fs7 fc0 sc0 ls0 ws0">links.<span class="_ _4"> </span>Following<span class="_ _4"> </span>this,<span class="_ _4"> </span>an<span class="_ _4"> </span>order<span class="_ _8"> </span>relation<span class="_ _9"> </span><span class="ff9">&#58892;<span class="_ _8"> </span></span>in<span class="_ _9"> </span>the<span class="_ _4"> </span>set</div><div class="t m0 x1d h17 yd4 ffa fs7 fc0 sc0 ls0 ws0">P</div><div class="t m0 x48 h16 yd5 ffa fs9 fc0 sc0 ls0 ws0">G</div><div class="t m0 x49 he yd6 ff1 fs7 fc0 sc0 ls0 ws0">is<span class="_ _9"> </span>established<span class="_ _4"> </span>among<span class="_ _4"> </span>paths,<span class="_ _4"> </span>and<span class="_ _9"> </span>we<span class="_ _4"> </span>will<span class="_ _9"> </span>refer<span class="_ _4"> </span>to</div><div class="t m0 x1d he yd7 ff1 fs7 fc0 sc0 ls0 ws0">a<span class="_ _b"> </span>path<span class="_ _b"> </span><span class="ff8">p</span></div><div class="t m0 x53 h13 yd8 ff5 fs9 fc0 sc0 ls0 ws0">i</div><div class="t m0 x54 he yd9 ff1 fs7 fc0 sc0 ls0 ws0">as<span class="_ _b"> </span>&#8216;&#8216;lighter<span class="_ _b"> </span>than&#8217;&#8217;<span class="_ _b"> </span><span class="ff8">p</span></div><div class="t m0 x51 h13 yd8 ff5 fs9 fc0 sc0 ls0 ws0">j</div><div class="t m0 x55 he yd9 ff1 fs7 fc0 sc0 ls0 ws0">if<span class="_ _b"> </span><span class="ff8">p</span></div><div class="t m0 x56 h13 yd8 ff5 fs9 fc0 sc0 ls0 ws0">i</div><div class="t m0 xf h11 yd9 ff9 fs7 fc0 sc0 ls0 ws0">&#58892;<span class="_ _4"> </span><span class="ff8">p</span></div><div class="t m0 x57 h13 yd8 ff5 fs9 fc0 sc0 ls0 ws0">j</div><div class="t m0 x58 he yd9 ff1 fs7 fc0 sc0 ls0 ws0">holds.</div><div class="t m0 x1e he yda ff1 fs7 fc0 sc0 ls0 ws0">The<span class="_ _1"> </span>NGR<span class="_ _1"> </span>algorithm<span class="_ _d"> </span>operates<span class="_ _1"> </span>two<span class="_ _1"> </span>subsequent</div><div class="t m0 x1d he ydb ff1 fs7 fc0 sc0 ls0 ws0">alterations<span class="_ _10"> </span>upon<span class="_ _10"> </span>the<span class="_ _7"> </span>path<span class="_ _10"> </span>set<span class="_ _10"> </span><span class="ffa">P</span></div><div class="t m0 x59 h16 ydc ffa fs9 fc0 sc0 ls0 ws0">G</div><div class="t m0 x2d he ydd ff1 fs7 fc0 sc0 ls0 ws0">,<span class="_ _10"> </span>and<span class="_ _7"> </span>applies<span class="_ _10"> </span>se-</div><div class="t m0 x1d he yde ff1 fs7 fc0 sc0 ls0 ws0">lection<span class="_ _b"> </span>criteria<span class="_ _b"> </span>on<span class="_ _7"> </span>the<span class="_ _b"> </span>resulting<span class="_ _b"> </span>subset:</div><div class="t m0 x1d he ydf ff7 fs7 fc0 sc0 ls0 ws0">&#8226;<span class="_ _e"> </span><span class="ff4">Step<span class="_ _e"> </span>1:<span class="_ _e"> </span><span class="ff1">the<span class="_"> </span>&#64257;rst<span class="_ _e"> </span>alterati<span class="_ _c"></span>on<span class="_ _e"> </span>transforms<span class="_ _e"> </span>the<span class="_ _e"> </span>di-</span></span></div><div class="t m0 x5a he ye0 ff1 fs7 fc0 sc0 ls0 ws0">rected<span class="_ _4"> </span>graph<span class="_ _8"> </span><span class="ffa">G<span class="_ _4"> </span></span>into<span class="_ _4"> </span><span class="ffa">G</span></div><div class="t m0 x45 h18 ye1 ff9 fs9 fc0 sc0 ls0 ws0">0</div><div class="t m0 xd h11 ye2 ff9 fs7 fc0 sc0 ls7 ws0">&#188;&#240;<span class="_ _1b"></span><span class="ffa ls0">V<span class="ffb">;<span class="_ _17"> </span></span>E</span></div><div class="t m0 x2d h18 ye1 ff9 fs9 fc0 sc0 ls0 ws0">0</div><div class="t m0 x56 h11 ye2 ff9 fs7 fc0 sc0 ls0 ws0">&#222;<span class="ff1">,<span class="_ _4"> </span><span class="ffa">E</span></span></div><div class="t m0 x5b h18 ye1 ff9 fs9 fc0 sc0 ls0 ws0">0</div><div class="t m0 x57 h11 ye2 ff9 fs7 fc0 sc0 ls0 ws0">&#58894;<span class="_ _4"> </span><span class="ffa">E<span class="ff1">,<span class="_ _8"> </span>select-</span></span></div><div class="t m0 x5a he ye3 ff1 fs7 fc0 sc0 ls0 ws0">ing<span class="_ _0"> </span>only<span class="_ _e"> </span>those<span class="_ _0"> </span>links<span class="_ _0"> </span>whose<span class="_ _0"> </span>weight<span class="_ _0"> </span>satis&#64257;es<span class="_ _e"> </span>a</div><div class="t m0 x5a he ye4 ff4 fs7 fc0 sc0 ls0 ws0">Cut-o&#64256;<span class="_ _4"> </span>criteri<span class="_ _c"></span>on<span class="_ _4"> </span><span class="ffa">C<span class="_ _4"> </span><span class="ff1">(e.g.,<span class="_ _8"> </span>if<span class="_ _4"> </span><span class="ff5">w<span class="_ _4"> </span></span>represented<span class="_ _8"> </span>the<span class="_ _4"> </span>link</span></span></div><div class="t m0 x5a he ye5 ff1 fs7 fc0 sc0 ls0 ws0">capacity,<span class="_ _16"> </span>&#8216;&#8216;slower&#8217;&#8217;<span class="_ _16"> </span>links<span class="_ _13"> </span>could<span class="_ _16"> </span>be<span class="_ _16"> </span>discarded</div><div class="t m0 x5a h14 ye6 ff1 fs7 fc0 sc0 ls0 ws0">from<span class="_ _7"> </span>path<span class="_ _7"> </span>selection<span class="_ _7"> </span>if<span class="_ _7"> </span><span class="ff5">w<span class="_ _8"> </span><span class="ffb">&lt;<span class="_ _4"> </span></span>w</span></div><div class="t m0 x5c h13 ye7 ff5 fs9 fc0 sc0 ls0 ws0">M</div><div class="t m0 x2c he ye8 ff1 fs7 fc0 sc0 ls0 ws0">,<span class="_ _7"> </span>where<span class="_ _7"> </span><span class="ff5">w</span></div><div class="t m0 x5d h13 ye7 ff5 fs9 fc0 sc0 ls0 ws0">M</div><div class="t m0 x3c he ye8 ff1 fs7 fc0 sc0 ls0 ws0">is<span class="_ _7"> </span>the</div><div class="t m0 x5a he ye9 ff1 fs7 fc0 sc0 ls0 ws0">smallest<span class="_ _e"> </span>accep<span class="_ _c"></span>table<span class="_ _e"> </span>capacity);<span class="_ _0"> </span>as<span class="_ _e"> </span>a<span class="_ _e"> </span>result,<span class="_ _0"> </span>the</div><div class="t m0 x5a he yea ff1 fs7 fc0 sc0 ls0 ws0">path<span class="_ _d"> </span>set<span class="_ _d"> </span><span class="ffa">P</span></div><div class="t m0 x5e h16 yeb ffa fs9 fc0 sc0 ls0 ws0">G</div><div class="t m0 x5f he yec ff1 fs7 fc0 sc0 ls0 ws0">is<span class="_ _d"> </span>reduced<span class="_ _d"> </span>to<span class="_ _d"> </span><span class="ffa">P</span></div><div class="t m0 x59 h16 yed ffa fs9 fc0 sc0 ls0 ws0">G</div><div class="t m0 x2d h19 yee ff9 fsa fc0 sc0 ls0 ws0">0</div><div class="t m0 xf he yec ff1 fs7 fc0 sc0 ls0 ws0">after<span class="_ _d"> </span>removing</div><div class="t m0 x5a he yef ff1 fs7 fc0 sc0 ls0 ws0">those<span class="_ _b"> </span>paths<span class="_ _b"> </span>containing<span class="_ _7"> </span>cut-o&#64256;<span class="_ _b"> </span>links;</div><div class="t m0 x1d he yf0 ff7 fs7 fc0 sc0 ls0 ws0">&#8226;<span class="_ _e"> </span><span class="ff4">Step<span class="_ _1"> </span>2:<span class="_ _1"> </span><span class="ff1">let<span class="_ _1"> </span><span class="ffa">P</span></span></span></div><div class="t m0 x5f h15 yf1 ff1 fs9 fc0 sc0 ls8 ws0">mh</div><div class="t m0 x60 he yf2 ff1 fs7 fc0 sc0 ls0 ws0">be<span class="_ _1"> </span>the<span class="_ _1"> </span>set<span class="_ _10"> </span>includi<span class="_ _c"></span>ng<span class="_ _1"> </span>one<span class="_ _1"> </span>mini-</div><div class="t m0 x5a he yf3 ff1 fs7 fc0 sc0 ls0 ws0">mum-hop<span class="_ _7"> </span>path<span class="_ _10"> </span>from<span class="_ _7"> </span>each<span class="_ _7"> </span>source<span class="_ _10"> </span>to<span class="_ _b"> </span>each<span class="_ _10"> </span>desti-</div><div class="t m0 x5a he yf4 ff1 fs7 fc0 sc0 ls0 ws0">nation.<span class="_"> </span>In<span class="_ _e"> </span>case<span class="_"> </span>more<span class="_ _e"> </span>than<span class="_"> </span>one<span class="_ _e"> </span>minimum-hop</div><div class="t m0 x5a he yf5 ff1 fs7 fc0 sc0 ls0 ws0">path<span class="_ _4"> </span>exist<span class="_ _4"> </span>from<span class="_ _4"> </span>the<span class="_ _4"> </span>same<span class="_ _4"> </span>source<span class="_ _4"> </span>to<span class="_ _4"> </span>the<span class="_ _4"> </span>same<span class="_ _4"> </span>des-</div><div class="t m0 x5a he yf6 ff1 fs7 fc0 sc0 ls0 ws0">tination,<span class="_ _4"> </span>one<span class="_ _9"> </span>at<span class="_ _9"> </span>random<span class="_ _4"> </span>is<span class="_ _9"> </span>selec<span class="_ _c"></span>ted.</div><div class="t m6 x5b h10 yf7 ff1 fs8 fc0 sc0 ls0 ws0">3</div><div class="t m0 x61 he yf8 ff1 fs7 fc0 sc0 ls0 ws0">The<span class="_ _9"> </span>second</div><div class="t m0 x5a he yf9 ff1 fs7 fc0 sc0 ls0 ws0">alteration<span class="_ _16"> </span>transforms<span class="_ _13"> </span>the<span class="_ _16"> </span>path<span class="_ _13"> </span>set<span class="_ _16"> </span><span class="ffa">P</span></div><div class="t m0 x62 h16 yfa ffa fs9 fc0 sc0 ls0 ws0">G</div><div class="t m0 x63 h19 yfb ff9 fsa fc0 sc0 ls0 ws0">0</div><div class="t m0 x64 he yfc ff1 fs7 fc0 sc0 ls0 ws0">into</div><div class="t m0 x5a h17 yfd ffa fs7 fc0 sc0 ls0 ws0">P</div><div class="t m0 x65 h18 yfe ff9 fs9 fc0 sc0 ls0 ws0">0</div><div class="t m0 x65 h16 yff ffa fs9 fc0 sc0 ls0 ws0">G</div><div class="t m0 x66 h19 y100 ff9 fsa fc0 sc0 ls0 ws0">0</div><div class="t m0 x67 h11 y101 ff9 fs7 fc0 sc0 ls0 ws0">&#188;<span class="_ _4"> </span><span class="ffa">P</span></div><div class="t m0 x68 h16 y102 ffa fs9 fc0 sc0 ls0 ws0">G</div><div class="t m0 x69 h19 y103 ff9 fsa fc0 sc0 ls0 ws0">0</div><div class="t m0 x41 h11 y101 ff9 fs7 fc0 sc0 ls0 ws0">[<span class="_ _a"> </span><span class="ffa">P</span></div><div class="t m0 x36 h15 y104 ff1 fs9 fc0 sc0 ls8 ws0">mh</div><div class="t m0 x60 he y101 ff1 fs7 fc0 sc0 ls0 ws0">;<span class="_ _1"> </span>the<span class="_ _1"> </span>new<span class="_ _d"> </span>subset<span class="_ _1"> </span>is<span class="_ _1"> </span>built<span class="_ _d"> </span>from</div><div class="t m0 x5a he y105 ff1 fs7 fc0 sc0 ls0 ws0">(i)<span class="_ _b"> </span>the<span class="_ _b"> </span>paths<span class="_ _b"> </span>belongi<span class="_ _c"></span>ng<span class="_ _b"> </span>to<span class="_ _b"> </span><span class="ffa">P</span></div><div class="t m0 x6a h16 y106 ffa fs9 fc0 sc0 ls0 ws0">G</div><div class="t m0 x6b h19 y107 ff9 fsa fc0 sc0 ls0 ws0">0</div><div class="t m0 x6c he y108 ff1 fs7 fc0 sc0 ls0 ws0">and<span class="_ _b"> </span>(ii)<span class="_ _b"> </span>the<span class="_ _b"> </span>mini<span class="_ _c"></span>-</div><div class="t m0 x5a he y109 ff1 fs7 fc0 sc0 ls0 ws0">mum-hop<span class="_ _10"> </span>paths<span class="_ _1"> </span>between<span class="_ _10"> </span>an<span class="_ _c"></span>y<span class="_ _10"> </span>two<span class="_ _1"> </span>nodes<span class="_ _10"> </span>in<span class="_ _10"> </span><span class="ffa">V</span>,</div><div class="t m0 x5a he y10a ff4 fs7 fc0 sc0 ls0 ws0">even<span class="_ _8"> </span>if<span class="_ _8"> </span>their<span class="_ _b"> </span>links<span class="_ _8"> </span>were<span class="_ _b"> </span>discarded<span class="_ _8"> </span>in<span class="_ _b"> </span>the<span class="_ _8"> </span>&#64257;rst<span class="_ _8"> </span>step<span class="_ _c"></span><span class="ff1">.</span></div><div class="t m0 x1e he y10b ff1 fs7 fc0 sc0 ls0 ws0">Finally,<span class="_ _1"> </span>the<span class="_ _1"> </span>decision<span class="_ _1"> </span>on<span class="_ _1"> </span>how<span class="_ _1"> </span>to<span class="_ _1"> </span>route<span class="_ _1"> </span>packets</div><div class="t m0 x1d he y10c ff1 fs7 fc0 sc0 ls0 ws0">between<span class="_ _8"> </span>a<span class="_ _4"> </span>source<span class="_ _8"> </span>and<span class="_ _8"> </span>a<span class="_ _4"> </span>desti<span class="_ _c"></span>nation<span class="_ _8"> </span>is<span class="_ _4"> </span>made<span class="_ _8"> </span>by<span class="_ _8"> </span>ap-</div><div class="t m0 x1d h11 y10d ff1 fs7 fc0 sc0 ls0 ws0">plying<span class="_ _a"> </span>the<span class="_ _a"> </span>order<span class="_ _a"> </span>relat<span class="_ _c"></span>ion<span class="_ _a"> </span><span class="ff9">&#58892;<span class="_ _a"> </span></span>to<span class="_ _a"> </span>the<span class="_ _a"> </span>path<span class="_ _9"> </span>subset<span class="_ _a"> </span>of<span class="_ _a"> </span><span class="ffa">P</span></div><div class="t m0 x6d h18 y10e ff9 fs9 fc0 sc0 ls0 ws0">0</div><div class="t m0 x6d h16 y10f ffa fs9 fc0 sc0 ls0 ws0">G</div><div class="t m0 x6e h19 y110 ff9 fsa fc0 sc0 ls0 ws0">0</div><div class="t m0 x1d he y111 ff1 fs7 fc0 sc0 ls0 ws0">joining<span class="_ _17"> </span>source<span class="_ _17"> </span>and<span class="_ _17"> </span>de<span class="_ _c"></span>stination,<span class="_ _17"> </span>and<span class="_ _a"> </span>picking<span class="_ _17"> </span>the<span class="_ _17"> </span>path</div><div class="t m4 x6f h7 y112 ff1 fs4 fc0 sc0 ls0 ws0">2</div><div class="t m0 x70 ha y113 ff1 fs5 fc0 sc0 ls0 ws0">In<span class="_ _4"> </span>this<span class="_ _4"> </span>paper<span class="_ _9"> </span>we<span class="_ _8"> </span>interchan<span class="_ _5"></span>geably<span class="_ _4"> </span>use<span class="_ _4"> </span>the<span class="_ _4"> </span>terms<span class="_ _4"> </span><span class="ffc">&#212;</span>edges<span class="ffc">&#213;<span class="_ _9"> </span></span>and</div><div class="t m0 x1d ha y114 ffc fs5 fc0 sc0 ls0 ws0">&#212;<span class="ff1">links</span>&#213;<span class="_ _4"> </span><span class="ff1">and<span class="_ _4"> </span>the<span class="_ _4"> </span>terms<span class="_ _4"> </span></span>&#212;<span class="ff1">vertices</span>&#213;<span class="_ _4"> </span><span class="ff1">and<span class="_ _4"> </span></span>&#212;<span class="ff1">nodes</span>&#213;<span class="ff1">.</span></div><div class="t m4 x6f h7 y91 ff1 fs4 fc0 sc0 ls0 ws0">3</div><div class="t m0 x70 ha y2f ff1 fs5 fc0 sc0 ls0 ws0">It<span class="_ _b"> </span>is<span class="_ _b"> </span>possible<span class="_ _b"> </span>to<span class="_ _b"> </span>optimize<span class="_ _b"> </span>the<span class="_ _7"> </span><span class="ffa">P</span></div><div class="t m0 x71 h1a y115 ff1 fsb fc0 sc0 ls9 ws0">mh</div><div class="t m0 x72 ha y2f ff1 fs5 fc0 sc0 ls0 ws0">set,<span class="_ _b"> </span>for<span class="_ _b"> </span>example<span class="_ _b"> </span>using</div><div class="t m0 x1d ha y30 ff1 fs5 fc0 sc0 ls0 ws0">load-balancing<span class="_ _9"> </span>criteria.</div><div class="t m0 x73 ha y92 ff4 fs5 fc0 sc0 ls0 ws0">C.<span class="_ _4"> </span>Casetti<span class="_ _4"> </span>et<span class="_ _4"> </span>al.<span class="_ _4"> </span>/<span class="_ _4"> </span>Computer<span class="_ _4"> </span>Networks<span class="_ _4"> </span>41<span class="_ _4"> </span>(2003)<span class="_ _4"> </span>475&#8211;487<span class="_ _18"> </span><span class="ff1">477</span></div></div><div class="pi" data-data='{"ctm":[1.764706,0.000000,0.000000,1.764706,0.000000,0.000000]}'></div></div><div id="pf4" class="pf w0 h0" data-page-no="4"><div class="pc pc4 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="/image.php?url=https://csdnimg.cn/release/download_crawler_static/89628520/bg4.jpg"><div class="t m0 x25 he y36 ff1 fs7 fc0 sc0 ls0 ws0">that<span class="_ _17"> </span>turns<span class="_ _a"> </span>out<span class="_ _a"> </span>to<span class="_ _17"> </span>be<span class="_ _a"> </span>the<span class="_ _a"> </span><span class="ff4">lightest<span class="_ _17"> </span></span>acco<span class="_ _c"></span>rding<span class="_ _17"> </span>to<span class="_ _a"> </span>the<span class="_ _a"> </span>cost</div><div class="t m0 x25 he y37 ff1 fs7 fc0 sc0 ls0 ws0">metric<span class="_ _4"> </span>de&#64257;ned<span class="_ _8"> </span>by<span class="_ _4"> </span>the<span class="_ _4"> </span>QoS<span class="_ _4"> </span>routing<span class="_ _8"> </span>algorithm.</div><div class="t m0 x25 h12 y94 ff4 fs7 fc0 sc0 ls0 ws0">2.2.<span class="_ _b"> </span>NGR-MD<span class="_ _b"> </span>and<span class="_ _b"> </span>NG<span class="_ _c"></span>R-WS<span class="_ _b"> </span>algorithms</div><div class="t m0 x27 he y96 ff1 fs7 fc0 sc0 ls0 ws0">In<span class="_ _8"> </span>a<span class="_ _4"> </span>broad<span class="_ _8"> </span>sense<span class="_ _8"> </span>the<span class="_ _8"> </span>NGR<span class="_ _8"> </span>methodology<span class="_ _8"> </span>can<span class="_ _8"> </span>be</div><div class="t m0 x25 he y97 ff1 fs7 fc0 sc0 ls0 ws0">coupled<span class="_ _b"> </span>with<span class="_ _7"> </span>any<span class="_ _b"> </span>metric<span class="_ _7"> </span>and<span class="_ _b"> </span>cost<span class="_ _7"> </span>function.<span class="_ _7"> </span>In<span class="_ _b"> </span>or-</div><div class="t m0 x25 he y98 ff1 fs7 fc0 sc0 ls0 ws0">der<span class="_ _7"> </span>to<span class="_ _10"> </span>exemplify<span class="_ _10"> </span>this<span class="_ _7"> </span>property,<span class="_ _10"> </span>we<span class="_ _7"> </span>co<span class="_ _c"></span>nsidered<span class="_ _10"> </span>the</div><div class="t m0 x25 he y99 ff1 fs7 fc0 sc0 ls0 ws0">application<span class="_ _8"> </span>of<span class="_ _4"> </span>this<span class="_ _4"> </span>methodo<span class="_ _c"></span>logy<span class="_ _4"> </span>to<span class="_ _8"> </span>two<span class="_ _4"> </span>algorithms</div><div class="t m0 x25 he y9a ff1 fs7 fc0 sc0 ls0 ws0">already<span class="_ _15"> </span>proposed<span class="_ _15"> </span>in<span class="_ _f"> </span>the<span class="_ _15"> </span>literature,<span class="_ _15"> </span>whi<span class="_ _c"></span>ch<span class="_ _15"> </span>were</div><div class="t m0 x25 he y9b ff1 fs7 fc0 sc0 ls0 ws0">shown<span class="_ _b"> </span>to<span class="_ _b"> </span>o&#64256;er<span class="_ _b"> </span>good<span class="_ _7"> </span>performance<span class="_ _b"> </span>[1,2]:</div><div class="t m0 x74 he y116 ff4 fs7 fc0 sc0 ls0 ws0">Widest-shortest<span class="_ _8"> </span>(WS):<span class="_ _8"> </span><span class="ff1">for<span class="_ _8"> </span>each<span class="_ _8"> </span>source&#8211;destina-</span></div><div class="t m0 x74 he y117 ff1 fs7 fc0 sc0 ls0 ws0">tion<span class="_ _4"> </span>pair,<span class="_ _8"> </span>the<span class="_ _4"> </span>algorithm<span class="_ _8"> </span>determines<span class="_ _4"> </span>all<span class="_ _8"> </span>the<span class="_ _4"> </span>paths</div><div class="t m0 x74 he y118 ff1 fs7 fc0 sc0 ls0 ws0">with<span class="_ _8"> </span>the<span class="_ _8"> </span>minimum-<span class="_ _c"></span>hop<span class="_ _8"> </span>count;<span class="_ _8"> </span>if<span class="_ _8"> </span>more<span class="_ _b"> </span>than<span class="_ _8"> </span>one</div><div class="t m0 x74 he y119 ff1 fs7 fc0 sc0 ls0 ws0">such<span class="_ _4"> </span>path<span class="_ _4"> </span>exist,<span class="_ _8"> </span>it<span class="_ _9"> </span>br<span class="_ _c"></span>eaks<span class="_ _4"> </span>the<span class="_ _4"> </span>tie<span class="_ _8"> </span>by<span class="_ _4"> </span>choosing<span class="_ _4"> </span>the</div><div class="t m0 x74 he y11a ff1 fs7 fc0 sc0 ls0 ws0">one<span class="_ _b"> </span>with<span class="_ _b"> </span>the<span class="_ _b"> </span>large<span class="_ _c"></span>st<span class="_ _b"> </span>available<span class="_ _b"> </span>bandwi<span class="_ _c"></span>dth<span class="_ _b"> </span>[1];</div><div class="t m0 x74 he y11b ff4 fs7 fc0 sc0 ls0 ws0">Minimum<span class="_ _7"> </span>distance<span class="_ _b"> </span>(M<span class="_ _c"></span>D):<span class="_ _b"> </span><span class="ff1">for<span class="_ _7"> </span>each<span class="_ _7"> </span>source&#8211;des-</span></div><div class="t m0 x74 he y11c ff1 fs7 fc0 sc0 ls0 ws0">tination<span class="_"> </span>pair,<span class="_"> </span>the<span class="_"> </span>path<span class="_"> </span>is<span class="_"> </span>chosen<span class="_"> </span>which<span class="_"> </span>mini-</div><div class="t m0 x74 he y11d ff1 fs7 fc0 sc0 ls0 ws0">mizes<span class="_"> </span>the<span class="_ _1"> </span>sum<span class="_"> </span>on<span class="_ _d"> </span>each<span class="_"> </span>link<span class="_ _d"> </span>of<span class="_ _d"> </span>the<span class="_"> </span>inverse<span class="_ _1"> </span>of</div><div class="t m0 x74 he y11e ff1 fs7 fc0 sc0 ls0 ws0">the<span class="_ _b"> </span>equal<span class="_ _b"> </span>bandwidth<span class="_ _b"> </span>sh<span class="_ _c"></span>are<span class="_ _b"> </span>[2].</div><div class="t m0 x27 he ya6 ff1 fs7 fc0 sc0 ls0 ws0">To<span class="_ _0"> </span>help<span class="_ _15"> </span>the<span class="_ _15"> </span>reader,<span class="_ _0"> </span>we<span class="_ _15"> </span>report<span class="_ _15"> </span>a<span class="_ _0"> </span>simple<span class="_ _15"> </span>de-</div><div class="t m0 x25 he ya7 ff1 fs7 fc0 sc0 ls0 ws0">scription<span class="_ _b"> </span>of<span class="_ _7"> </span>the<span class="_ _b"> </span>above<span class="_ _7"> </span>algorithms,<span class="_ _b"> </span>us<span class="_ _c"></span>ing<span class="_ _b"> </span>the<span class="_ _7"> </span>nota-</div><div class="t m0 x25 he ya8 ff1 fs7 fc0 sc0 ls0 ws0">tion<span class="_ _b"> </span>introduced<span class="_ _b"> </span>in<span class="_ _b"> </span>this<span class="_ _7"> </span>paper.</div><div class="t m0 x25 he yaa ff7 fs7 fc0 sc0 ls0 ws0">&#8226;<span class="_ _e"> </span><span class="ff4">WS<span class="_ _4"> </span>path<span class="_ _4"> </span>weight<span class="_ _4"> </span>computation:<span class="_ _8"> </span><span class="ff1">a<span class="_ _9"> </span>weight<span class="_ _4"> </span><span class="ff5">w</span></span></span></div><div class="t m0 x18 h13 yeb ff5 fs9 fc0 sc0 ls0 ws0">l</div><div class="t m0 x75 he yec ff1 fs7 fc0 sc0 ls0 ws0">associ-</div><div class="t m0 x76 he yef ff1 fs7 fc0 sc0 ls0 ws0">ated<span class="_ _b"> </span>to<span class="_ _b"> </span>a<span class="_ _b"> </span>generi<span class="_ _c"></span>c<span class="_ _b"> </span>link<span class="_ _b"> </span><span class="ff5">l<span class="_ _b"> </span></span>is<span class="_ _b"> </span>computed<span class="_ _7"> </span>as</div><div class="t m0 x77 h1b y11f ff5 fs7 fc0 sc0 ls0 ws0">w</div><div class="t m0 x78 h13 y120 ff5 fs9 fc0 sc0 ls0 ws0">l</div><div class="t m0 x79 h11 y121 ff9 fs7 fc0 sc0 ls0 ws0">&#188;<span class="_ _4"> </span><span class="ff5">b</span></div><div class="t m0 x7a h13 y120 ff5 fs9 fc0 sc0 ls0 ws0">l</div><div class="t m0 x7b h11 y121 ffb fs7 fc0 sc0 ls0 ws0">;<span class="_ _1c"> </span><span class="ff9">&#240;<span class="ff1">1</span>&#222;</span></div><div class="t m0 x77 he y122 ff1 fs7 fc0 sc0 ls0 ws0">where<span class="_ _10"> </span><span class="ff5">b</span></div><div class="t m0 x7c h13 y123 ff5 fs9 fc0 sc0 ls0 ws0">l</div><div class="t m0 x7d he y124 ff1 fs7 fc0 sc0 ls0 ws0">is<span class="_ _10"> </span>an<span class="_ _1"> </span>estimate<span class="_ _1"> </span>of<span class="_ _10"> </span>the<span class="_ _10"> </span>cu<span class="_ _c"></span>rrently<span class="_ _10"> </span>avail<span class="_ _c"></span>-</div><div class="t m0 x77 he y125 ff1 fs7 fc0 sc0 ls0 ws0">able<span class="_ _b"> </span>bandwidth<span class="_ _b"> </span>on<span class="_ _7"> </span>link<span class="_ _b"> </span><span class="ff5">l</span>;</div><div class="t m0 x27 he y126 ff1 fs7 fc0 sc0 ls0 ws0">The<span class="_ _10"> </span>set<span class="_ _10"> </span>of<span class="_ _1"> </span>paths<span class="_ _10"> </span>among<span class="_ _10"> </span>which<span class="_ _1"> </span>the<span class="_ _10"> </span>path<span class="_ _10"> </span><span class="ffa">P</span></div><div class="t m0 x7e h16 y127 ffa fs9 fc0 sc0 ls0 ws0">G</div><div class="t m0 x7f he y128 ff1 fs7 fc0 sc0 ls0 ws0">is</div><div class="t m0 x25 he y129 ff1 fs7 fc0 sc0 ls0 ws0">chosen<span class="_ _9"> </span>is<span class="_ _9"> </span>restricted<span class="_ _9"> </span>to<span class="_ _9"> </span>the<span class="_ _4"> </span>minimum-hop<span class="_ _9"> </span>paths,<span class="_ _9"> </span>i.e.,</div><div class="t m0 x25 h17 y12a ffa fs7 fc0 sc0 ls0 ws0">P</div><div class="t m0 x20 h16 y12b ffa fs9 fc0 sc0 ls0 ws0">G</div><div class="t m0 x1 h11 y12c ff9 fs7 fc0 sc0 ls4 ws0">&#188;f<span class="_ _1b"></span>f<span class="_ _19"></span><span class="ff8 ls0">p</span></div><div class="t m0 x80 h13 y12b ff5 fs9 fc0 sc0 ls0 ws0">i</div><div class="t m0 x81 h11 y12c ff9 fs7 fc0 sc0 ls0 ws0">&#240;<span class="ff5">v</span></div><div class="t m0 x82 h13 y12b ff5 fs9 fc0 sc0 ls0 ws0">s</div><div class="t m0 x83 h14 y12c ffb fs7 fc0 sc0 ls0 ws0">;<span class="_ _17"> </span><span class="ff5">v</span></div><div class="t m0 x84 h13 y12b ff5 fs9 fc0 sc0 ls0 ws0">d</div><div class="t m0 x85 h11 y12c ff9 fs7 fc0 sc0 ls0 ws0">&#222;j<span class="_ _b"> </span>jj<span class="ff8">p</span></div><div class="t m0 x5 h13 y12b ff5 fs9 fc0 sc0 ls0 ws0">i</div><div class="t m0 x86 h11 y12c ff9 fs7 fc0 sc0 ls0 ws0">&#240;<span class="ff5">v</span></div><div class="t m0 x87 h13 y12b ff5 fs9 fc0 sc0 ls0 ws0">s</div><div class="t m0 x88 h14 y12c ffb fs7 fc0 sc0 ls0 ws0">;<span class="_ _17"> </span><span class="ff5">v</span></div><div class="t m0 x89 h13 y12b ff5 fs9 fc0 sc0 ls0 ws0">d</div><div class="t m0 x8a h11 y12c ff9 fs7 fc0 sc0 ls0 ws0">&#222;jj<span class="_ _17"> </span><span class="ffd">6<span class="_ _17"> </span></span>jj<span class="ff8">p</span></div><div class="t m0 x8b h13 y12b ff5 fs9 fc0 sc0 ls0 ws0">j</div><div class="t m0 x8c h11 y12c ff9 fs7 fc0 sc0 ls0 ws0">&#240;<span class="ff5">v</span></div><div class="t m0 x8d h13 y12b ff5 fs9 fc0 sc0 ls0 ws0">s</div><div class="t m0 x8e h14 y12c ffb fs7 fc0 sc0 ls0 ws0">;<span class="_ _17"> </span><span class="ff5">v</span></div><div class="t m0 x8f h13 y12b ff5 fs9 fc0 sc0 ls0 ws0">d</div><div class="t m0 x90 h11 y12c ff9 fs7 fc0 sc0 ls0 ws0">&#222;jj<span class="_ _b"> </span>8<span class="ff5">j<span class="_"> </span></span>g</div><div class="t m0 x14 h11 y12d ff9 fs7 fc0 sc0 ls0 ws0">8<span class="ff5">v</span></div><div class="t m0 x7a h13 y12e ff5 fs9 fc0 sc0 ls0 ws0">s</div><div class="t m0 x7b h14 y12f ffb fs7 fc0 sc0 ls0 ws0">;<span class="_ _17"> </span><span class="ff5">v</span></div><div class="t m0 x82 h13 y12e ff5 fs9 fc0 sc0 ls0 ws0">d</div><div class="t m0 x91 h11 y12f ff9 fs7 fc0 sc0 ls0 ws0">g<span class="ffb">:<span class="_ _1d"> </span></span>&#240;<span class="ff1">2</span>&#222;</div><div class="t m0 x25 h11 y130 ff1 fs7 fc0 sc0 ls0 ws0">Then,<span class="_ _9"> </span>the<span class="_ _4"> </span>cost<span class="_ _4"> </span><span class="ff5">c<span class="ff9">&#240;<span class="ff8">p</span></span></span></div><div class="t m0 x92 h13 y131 ff5 fs9 fc0 sc0 ls0 ws0">i</div><div class="t m0 x93 h11 y132 ff9 fs7 fc0 sc0 ls0 ws0">&#222;<span class="_ _9"> </span><span class="ff1">of<span class="_ _4"> </span>path<span class="_ _9"> </span><span class="ff8">p</span></span></div><div class="t m0 x73 h13 y131 ff5 fs9 fc0 sc0 ls0 ws0">i</div><div class="t m0 x94 he y132 ff1 fs7 fc0 sc0 ls0 ws0">is<span class="_ _9"> </span>de&#64257;ned<span class="_ _4"> </span>as<span class="_ _4"> </span>follows:</div><div class="t m0 x25 h11 y133 ff5 fs7 fc0 sc0 ls0 ws0">c<span class="ff9">&#240;<span class="ff8">p</span></span></div><div class="t m0 x95 h13 y134 ff5 fs9 fc0 sc0 ls0 ws0">i</div><div class="t m0 x96 h11 y135 ff9 fs7 fc0 sc0 lsa ws0">&#222;&#188;<span class="ff1 ls0">min</span></div><div class="t m0 x97 h18 y136 ff5 fs9 fc0 sc0 ls0 ws0">l<span class="ff9">2<span class="ff8">p</span></span></div><div class="t m0 x98 h1c y137 ff5 fsa fc0 sc0 ls0 ws0">i</div><div class="t m0 x12 h11 y135 ff9 fs7 fc0 sc0 ls0 ws0">f<span class="ff5">w</span></div><div class="t m0 x99 h13 y134 ff5 fs9 fc0 sc0 ls0 ws0">l</div><div class="t m0 x9a h11 y135 ff9 fs7 fc0 sc0 ls0 ws0">g<span class="ff3">;<span class="_ _1e"> </span></span>&#240;<span class="ff1">3</span>&#222;</div><div class="t m0 x25 he y138 ff1 fs7 fc0 sc0 ls0 ws0">and<span class="_"> </span>the<span class="_ _d"> </span>ordering<span class="_"> </span>relation<span class="_"> </span>is<span class="_ _d"> </span>such<span class="_ _d"> </span>that<span class="_"> </span><span class="ff8">p</span></div><div class="t m0 x18 h13 y139 ff5 fs9 fc0 sc0 ls0 ws0">i</div><div class="t m0 x9b h11 y13a ff9 fs7 fc0 sc0 ls0 ws0">&#58892;<span class="_ _4"> </span><span class="ff8">p</span></div><div class="t m0 x9c h13 y139 ff5 fs9 fc0 sc0 ls0 ws0">j</div><div class="t m0 x7f he y13a ff1 fs7 fc0 sc0 ls0 ws0">if</div><div class="t m0 x25 h11 y13b ff5 fs7 fc0 sc0 ls0 ws0">c<span class="ff9">&#240;<span class="ff8">p</span></span></div><div class="t m0 x95 h13 y13c ff5 fs9 fc0 sc0 ls0 ws0">i</div><div class="t m0 x96 h11 y13d ff9 fs7 fc0 sc0 ls0 ws0">&#222;<span class="_ _4"> </span><span class="ffb">&gt;<span class="_ _8"> </span><span class="ff5">c</span></span>&#240;<span class="ff8">p</span></div><div class="t m0 x7c h13 y13c ff5 fs9 fc0 sc0 ls0 ws0">j</div><div class="t m0 x9d h11 y13d ff9 fs7 fc0 sc0 ls0 ws0">&#222;<span class="_ _7"> </span><span class="ff1">(i.e.,<span class="_ _10"> </span><span class="ff8">p</span></span></div><div class="t m0 x9e h13 y13c ff5 fs9 fc0 sc0 ls0 ws0">i</div><div class="t m0 x86 he y13d ff1 fs7 fc0 sc0 ls0 ws0">is<span class="_ _7"> </span>lighter<span class="_ _10"> </span>than<span class="_ _10"> </span><span class="ff8">p</span></div><div class="t m0 x8e h13 y13c ff5 fs9 fc0 sc0 ls0 ws0">j</div><div class="t m0 x9f he y13d ff1 fs7 fc0 sc0 ls0 ws0">if<span class="_ _7"> </span>its<span class="_ _10"> </span>avail-</div><div class="t m0 x25 he y13e ff1 fs7 fc0 sc0 ls0 ws0">able<span class="_ _b"> </span>bandwidth<span class="_ _b"> </span>is<span class="_ _7"> </span>larger<span class="_ _b"> </span>than<span class="_ _b"> </span><span class="ff8">p</span></div><div class="t m0 xa0 h13 y13f ff5 fs9 fc0 sc0 ls0 ws0">j</div><div class="t m0 xa1 he y140 ffc fs7 fc0 sc0 ls0 ws0">&#213;<span class="ff1">s).</span></div><div class="t m0 x25 he y141 ff7 fs7 fc0 sc0 ls0 ws0">&#8226;<span class="_ _e"> </span><span class="ff4">MD<span class="_ _b"> </span>p<span class="_ _c"></span>ath<span class="_ _b"> </span>weight<span class="_ _b"> </span>compu<span class="_ _c"></span>tation:<span class="_ _b"> </span><span class="ff1">a<span class="_ _b"> </span>weig<span class="_ _c"></span>ht<span class="_ _b"> </span><span class="ff5">w</span></span></span></div><div class="t m0 xa2 h13 y142 ff5 fs9 fc0 sc0 ls0 ws0">l</div><div class="t m0 xa3 he y143 ff1 fs7 fc0 sc0 ls0 ws0">asso-</div><div class="t m0 x76 he y144 ff1 fs7 fc0 sc0 ls0 ws0">ciated<span class="_ _b"> </span>to<span class="_ _b"> </span>a<span class="_ _b"> </span>generi<span class="_ _c"></span>c<span class="_ _b"> </span>link<span class="_ _b"> </span><span class="ff5">l<span class="_ _b"> </span></span>is<span class="_ _b"> </span>co<span class="_ _c"></span>mputed<span class="_ _b"> </span>as</div><div class="t m0 x77 h1b y145 ff5 fs7 fc0 sc0 ls0 ws0">w</div><div class="t m0 x78 h13 y146 ff5 fs9 fc0 sc0 ls0 ws0">l</div><div class="t m0 x79 h11 y147 ff9 fs7 fc0 sc0 ls0 ws0">&#188;</div><div class="t m0 x97 h1b y148 ff5 fs7 fc0 sc0 ls0 ws0">n</div><div class="t m0 x7a h13 y149 ff5 fs9 fc0 sc0 ls0 ws0">l</div><div class="t m0 x98 h11 y148 ff9 fs7 fc0 sc0 ls0 ws0">&#254;<span class="_ _9"> </span><span class="ff1">1</span></div><div class="t m0 x7b h1b y14a ff5 fs7 fc0 sc0 ls0 ws0">C</div><div class="t m0 x9d h13 y14b ff5 fs9 fc0 sc0 ls0 ws0">l</div><div class="t m0 xa4 h11 y147 ffb fs7 fc0 sc0 ls0 ws0">;<span class="_ _1f"> </span><span class="ff9">&#240;<span class="ff1">4</span>&#222;</span></div><div class="t m0 x9 he y14c ff1 fs7 fc0 sc0 ls0 ws0">where<span class="_ _10"> </span><span class="ff5">C</span></div><div class="t m0 x33 h13 y14d ff5 fs9 fc0 sc0 ls0 ws0">l</div><div class="t m0 x42 he y14e ff1 fs7 fc0 sc0 ls0 ws0">is<span class="_ _7"> </span>the<span class="_ _10"> </span>link<span class="_ _10"> </span>capacity<span class="_ _7"> </span>and<span class="_ _10"> </span><span class="ff5">n</span></div><div class="t m0 xa5 h13 y14d ff5 fs9 fc0 sc0 ls0 ws0">l</div><div class="t m0 xa6 he y14e ff1 fs7 fc0 sc0 ls0 ws0">is<span class="_ _7"> </span>an<span class="_ _10"> </span>esti-</div><div class="t m0 x9 he y14f ff1 fs7 fc0 sc0 ls0 ws0">mate<span class="_ _d"> </span>of<span class="_ _d"> </span>the<span class="_ _d"> </span>number<span class="_"> </span>of<span class="_ _1"> </span>active<span class="_"> </span>&#64258;ows<span class="_ _1"> </span>currently</div><div class="t m0 x9 he y150 ff1 fs7 fc0 sc0 ls0 ws0">routed<span class="_ _b"> </span>over<span class="_ _b"> </span>link<span class="_ _7"> </span><span class="ff5">l</span>.</div><div class="t m0 x9 h11 y151 ff1 fs7 fc0 sc0 ls0 ws0">The<span class="_ _b"> </span>cost<span class="_ _7"> </span><span class="ff5">c<span class="ff9">&#240;<span class="ff8">p</span></span></span></div><div class="t m0 xa7 h13 y152 ff5 fs9 fc0 sc0 ls0 ws0">i</div><div class="t m0 xa8 h11 y153 ff9 fs7 fc0 sc0 ls0 ws0">&#222;<span class="_ _b"> </span><span class="ff1">of<span class="_ _b"> </span>pa<span class="_ _c"></span>th<span class="_ _b"> </span><span class="ff8">p</span></span></div><div class="t m0 xa9 h13 y152 ff5 fs9 fc0 sc0 ls0 ws0">i</div><div class="t m0 xaa he y153 ff1 fs7 fc0 sc0 ls0 ws0">is<span class="_ _b"> </span>then<span class="_ _7"> </span>de&#64257;ned<span class="_ _b"> </span>as<span class="_ _7"> </span>fol-</div><div class="t m0 x28 he y154 ff1 fs7 fc0 sc0 ls0 ws0">lows:</div><div class="t m0 x28 h11 y155 ff5 fs7 fc0 sc0 ls0 ws0">c<span class="ff9">&#240;<span class="ff8">p</span></span></div><div class="t m0 xab h13 y156 ff5 fs9 fc0 sc0 ls0 ws0">i</div><div class="t m0 xac h11 y157 ff9 fs7 fc0 sc0 lsb ws0">&#222;&#188;</div><div class="t m0 xad h1d y158 ffe fs7 fc0 sc0 ls0 ws0">X</div><div class="t m0 xae h18 y159 ff5 fs9 fc0 sc0 ls0 ws0">l<span class="ff9">2<span class="ff8">p</span></span></div><div class="t m0 x32 h1c y15a ff5 fsa fc0 sc0 ls0 ws0">i</div><div class="t m0 xaf h1b y157 ff5 fs7 fc0 sc0 ls0 ws0">w</div><div class="t m0 x4c h13 y156 ff5 fs9 fc0 sc0 ls0 ws0">l</div><div class="t m0 xb0 h11 y157 ff3 fs7 fc0 sc0 ls0 ws0">;<span class="_ _20"> </span><span class="ff9">&#240;<span class="ff1">5</span>&#222;</span></div><div class="t m0 x28 he y15b ff1 fs7 fc0 sc0 ls0 ws0">and<span class="_"> </span>the<span class="_ _d"> </span>ordering<span class="_"> </span>relation<span class="_"> </span>is<span class="_ _d"> </span>such<span class="_"> </span>that<span class="_ _d"> </span><span class="ff8">p</span></div><div class="t m0 xb1 h13 y15c ff5 fs9 fc0 sc0 ls0 ws0">i</div><div class="t m0 xb2 h11 y15d ff9 fs7 fc0 sc0 ls0 ws0">&#58892;<span class="_ _4"> </span><span class="ff8">p</span></div><div class="t m0 xb3 h13 y15c ff5 fs9 fc0 sc0 ls0 ws0">j</div><div class="t m0 xb4 he y15d ff1 fs7 fc0 sc0 ls0 ws0">if</div><div class="t m0 x28 h11 y15e ff5 fs7 fc0 sc0 ls0 ws0">c<span class="ff9">&#240;<span class="ff8">p</span></span></div><div class="t m0 xab h13 y15f ff5 fs9 fc0 sc0 ls0 ws0">i</div><div class="t m0 xac h11 y160 ff9 fs7 fc0 sc0 ls0 ws0">&#222;<span class="_ _4"> </span><span class="ffb">&lt;<span class="_ _8"> </span><span class="ff5">c</span></span>&#240;<span class="ff8">p</span></div><div class="t m0 xb5 h13 y15f ff5 fs9 fc0 sc0 ls0 ws0">j</div><div class="t m0 xb6 h11 y160 ff9 fs7 fc0 sc0 ls0 ws0">&#222;<span class="ff1">.</span></div><div class="t m0 x9 he y161 ff1 fs7 fc0 sc0 ls0 ws0">To<span class="_ _10"> </span>implement<span class="_ _10"> </span>the<span class="_ _10"> </span>NGR<span class="_ _1"> </span>algorithms,<span class="_ _10"> </span>we<span class="_ _10"> </span>de&#64257;ne</div><div class="t m0 x28 he y162 ff1 fs7 fc0 sc0 ls0 ws0">the<span class="_ _b"> </span>following:</div><div class="t m0 x28 he y163 ff4 fs7 fc0 sc0 ls0 ws0">Cut-o&#64256;<span class="_ _7"> </span>criterio<span class="_ _c"></span>n<span class="_ _7"> </span><span class="ffa">C<span class="_ _8"> </span><span class="ff3">:<span class="_ _7"> </span><span class="ff1">a<span class="_ _7"> </span>link<span class="_ _10"> </span>is<span class="_ _7"> </span>discar<span class="_ _c"></span>ded<span class="_ _7"> </span>if<span class="_ _10"> </span>its<span class="_ _7"> </span>utili-</span></span></span></div><div class="t m0 x28 he y164 ff1 fs7 fc0 sc0 ls0 ws0">zation<span class="_ _17"> </span>is<span class="_ _17"> </span>found<span class="_ _17"> </span>to<span class="_ _17"> </span>be<span class="_ _a"> </span>above<span class="_ _17"> </span>a<span class="_ _17"> </span>given<span class="_ _17"> </span>threshold<span class="_ _a"> </span><span class="ff5">W</span></div><div class="t m0 x64 h13 y165 ff5 fs9 fc0 sc0 ls0 ws0">t</div><div class="t m0 xb7 he y166 ff1 fs7 fc0 sc0 ls0 ws0">,<span class="_ _17"> </span>i.e.,</div><div class="t m0 x28 h1b y167 ff5 fs7 fc0 sc0 ls0 ws0">b</div><div class="t m0 x5a h13 y168 ff5 fs9 fc0 sc0 ls0 ws0">l</div><div class="t m0 xb8 h14 y169 ffb fs7 fc0 sc0 ls0 ws0">=<span class="ff5">c</span></div><div class="t m0 xa h13 y168 ff5 fs9 fc0 sc0 ls0 ws0">l</div><div class="t m0 x67 h14 y169 ffb fs7 fc0 sc0 ls0 ws0">&gt;<span class="_ _4"> </span><span class="ff5">W</span></div><div class="t m0 x4a h13 y168 ff5 fs9 fc0 sc0 ls0 ws0">t</div><div class="t m0 x4b h11 y169 ffb fs7 fc0 sc0 ls0 ws0">:<span class="_ _1c"> </span><span class="ff9">&#240;<span class="ff1">6</span>&#222;</span></div><div class="t m0 x9 he y16a ff1 fs7 fc0 sc0 ls0 ws0">Combining<span class="_ _8"> </span>NGR<span class="_ _b"> </span>and<span class="_ _8"> </span><span class="ffa">C<span class="_ _8"> </span></span>with<span class="_ _b"> </span>either<span class="_ _8"> </span>the<span class="_ _8"> </span>MD<span class="_ _b"> </span>or</div><div class="t m0 x28 he y16b ff1 fs7 fc0 sc0 ls0 ws0">WS<span class="_ _8"> </span>QoS<span class="_ _8"> </span>algorithm<span class="_ _c"></span>s<span class="_ _8"> </span>we<span class="_ _8"> </span>obtain<span class="_ _b"> </span>the<span class="_ _8"> </span>NGR-MD<span class="_ _b"> </span>and</div><div class="t m0 x28 he y16c ff1 fs7 fc0 sc0 ls0 ws0">NGR-WS<span class="_ _b"> </span>algorithms<span class="_ _c"></span>.</div><div class="t m0 x9 he y16d ff1 fs7 fc0 sc0 ls0 ws0">In<span class="_ _8"> </span>the<span class="_ _8"> </span>rest<span class="_ _b"> </span>of<span class="_ _8"> </span>the<span class="_ _b"> </span>paper,<span class="_ _8"> </span>we<span class="_ _8"> </span>assum<span class="_ _c"></span>e<span class="_ _8"> </span><span class="ff5">W</span></div><div class="t m0 xa6 h13 y16e ff5 fs9 fc0 sc0 ls0 ws0">t</div><div class="t m0 xb9 h11 y16f ff9 fs7 fc0 sc0 ls0 ws0">&#188;<span class="_ _4"> </span><span class="ff1">1,<span class="_ _b"> </span>i.e.,</span></div><div class="t m0 x28 he y170 ff1 fs7 fc0 sc0 ls0 ws0">if<span class="_ _9"> </span>a<span class="_ _4"> </span>link<span class="_ _9"> </span>shows<span class="_ _4"> </span>a<span class="_ _9"> </span>100%<span class="_ _9"> </span>utilizat<span class="_ _c"></span>ion,<span class="_ _9"> </span>it<span class="_ _4"> </span>is<span class="_ _9"> </span>discarded<span class="_ _4"> </span>by</div><div class="t m0 x28 he y171 ff1 fs7 fc0 sc0 ls0 ws0">the<span class="_ _b"> </span>Cut-o&#64256;<span class="_ _b"> </span>criteri<span class="_ _c"></span>on.</div><div class="t m0 x28 h12 y172 ff4 fs7 fc0 sc0 ls0 ws0">2.3.<span class="_ _b"> </span>Implementation<span class="_ _7"> </span>issues</div><div class="t m0 x9 he y173 ff1 fs7 fc0 sc0 ls0 ws0">After<span class="_ _8"> </span>de&#64257;<span class="_ _c"></span>ning<span class="_ _8"> </span>the<span class="_ _b"> </span>algorithms,<span class="_ _b"> </span>we<span class="_ _b"> </span>are<span class="_ _b"> </span>interested</div><div class="t m0 x28 he y174 ff1 fs7 fc0 sc0 ls0 ws0">in<span class="_ _10"> </span>the<span class="_ _10"> </span>viability<span class="_ _10"> </span>of<span class="_ _10"> </span>a<span class="_ _10"> </span><span class="ff4">consistent<span class="_ _10"> </span></span>hop-by-hop<span class="_ _1"> </span>imple-</div><div class="t m0 x28 he y175 ff1 fs7 fc0 sc0 ls0 ws0">mentation,<span class="_ _b"> </span>in<span class="_ _b"> </span>which<span class="_ _7"> </span>routing<span class="_ _b"> </span>decisions<span class="_ _7"> </span>taken<span class="_ _b"> </span>at<span class="_ _b"> </span>an</div><div class="t m0 x28 he y176 ff1 fs7 fc0 sc0 ls0 ws0">upstream<span class="_ _7"> </span>node<span class="_ _7"> </span>are<span class="_ _7"> </span>not<span class="_ _7"> </span>liable<span class="_ _7"> </span>to<span class="_ _7"> </span>be<span class="_ _7"> </span>superseded<span class="_ _10"> </span>by</div><div class="t m0 x28 he y177 ff1 fs7 fc0 sc0 ls0 ws0">downstream<span class="_ _0"> </span>nodes<span class="_ _0"> </span>&#64257;nding<span class="_ _0"> </span>a<span class="_ _0"> </span>locally-optim<span class="_ _c"></span>al<span class="_ _0"> </span>al-</div><div class="t m0 x28 he y178 ff1 fs7 fc0 sc0 ls0 ws0">ternative<span class="_ _1"> </span>to<span class="_ _1"> </span>the<span class="_ _1"> </span>path<span class="_ _1"> </span>chosen<span class="_ _d"> </span>earlier<span class="_ _1"> </span>by<span class="_ _1"> </span>upstream</div><div class="t m0 x28 he y179 ff1 fs7 fc0 sc0 ls0 ws0">nodes.<span class="_ _1"> </span>As<span class="_ _1"> </span>formally<span class="_ _1"> </span>proved<span class="_ _10"> </span>in<span class="_ _1"> </span>[12],<span class="_ _1"> </span>the<span class="_ _1"> </span>WS<span class="_ _1"> </span>algo-</div><div class="t m0 x28 he y17a ff1 fs7 fc0 sc0 ls0 ws0">rithm<span class="_ _1"> </span>does<span class="_ _10"> </span>not<span class="_ _1"> </span>belong<span class="_ _10"> </span>to<span class="_ _1"> </span>the<span class="_ _1"> </span>class<span class="_ _10"> </span>of<span class="_ _1"> </span>algorithms</div><div class="t m0 x28 he y17b ff1 fs7 fc0 sc0 ls0 ws0">that<span class="_"> </span>allow<span class="_"> </span>a<span class="_ _d"> </span>consistent<span class="_"> </span>hop-by-hop<span class="_"> </span>implementa-</div><div class="t m0 x28 he y17c ff1 fs7 fc0 sc0 ls0 ws0">tion,<span class="_ _8"> </span>while<span class="_ _8"> </span>the<span class="_ _4"> </span>MD<span class="_ _8"> </span>algorithm<span class="_ _8"> </span>can<span class="_ _8"> </span>be<span class="_ _8"> </span>implemented</div><div class="t m0 x28 he y17d ff1 fs7 fc0 sc0 ls0 ws0">in<span class="_ _10"> </span>a<span class="_ _1"> </span>hop-by-hop<span class="_ _1"> </span>fashion<span class="_ _10"> </span>while<span class="_ _1"> </span>preserving<span class="_ _1"> </span>consis-</div><div class="t m0 x28 he y17e ff1 fs7 fc0 sc0 ls0 ws0">tency.<span class="_ _16"> </span>If<span class="_ _13"> </span>we<span class="_ _16"> </span>combine<span class="_ _16"> </span>the<span class="_ _13"> </span>NGR<span class="_ _16"> </span>methodology</div><div class="t m0 x28 he y17f ff1 fs7 fc0 sc0 ls0 ws0">described<span class="_ _8"> </span>above<span class="_ _8"> </span>with<span class="_ _8"> </span>those<span class="_ _8"> </span>algorithms,<span class="_ _8"> </span>is<span class="_ _8"> </span>the<span class="_ _8"> </span>hop-</div><div class="t m0 x28 he y180 ff1 fs7 fc0 sc0 ls0 ws0">by-hop<span class="_"> </span>implementation<span class="_"> </span>property<span class="_"> </span>preserved?<span class="_"> </span>Un-</div><div class="t m0 x28 he y181 ff1 fs7 fc0 sc0 ls0 ws0">fortunately,<span class="_ _1"> </span>the<span class="_ _10"> </span>answ<span class="_ _c"></span>er<span class="_ _1"> </span>is<span class="_ _10"> </span>negative.<span class="_ _1"> </span>The<span class="_ _1"> </span>proof<span class="_ _10"> </span>in</div><div class="t m0 x28 he y182 ff1 fs7 fc0 sc0 ls0 ws0">case<span class="_ _7"> </span>of<span class="_ _7"> </span>the<span class="_ _b"> </span>NGR<span class="_ _c"></span>-MD<span class="_ _7"> </span>metric<span class="_ _7"> </span>is<span class="_ _b"> </span>by<span class="_ _7"> </span>co<span class="_ _c"></span>unter-exam-</div><div class="t m0 x28 he y183 ff1 fs7 fc0 sc0 ls0 ws0">ple,<span class="_"> </span>while<span class="_"> </span>NGR-WS<span class="_"> </span>cannot<span class="_"> </span>be<span class="_ _d"> </span>considered<span class="_"> </span>since</div><div class="t m0 x28 he y184 ff1 fs7 fc0 sc0 ls0 ws0">the<span class="_ _10"> </span>WS<span class="_ _10"> </span>criterion<span class="_ _10"> </span>itself<span class="_ _10"> </span>is<span class="_ _7"> </span>not<span class="_ _10"> </span>implementable<span class="_ _10"> </span>hop-</div><div class="t m0 x28 he y185 ff1 fs7 fc0 sc0 ls0 ws0">by-hop.<span class="_ _4"> </span>Consi<span class="_ _c"></span>der<span class="_ _4"> </span>the<span class="_ _8"> </span>simple<span class="_ _4"> </span>directed<span class="_ _4"> </span>graph<span class="_ _8"> </span>in<span class="_ _4"> </span>Fig.</div><div class="t m0 x28 he y186 ff1 fs7 fc0 sc0 ls0 ws0">1,<span class="_ _8"> </span>consisting<span class="_ _8"> </span>of<span class="_ _4"> </span>&#64257;ve<span class="_ _8"> </span>links,<span class="_ _8"> </span><span class="ff5">a</span>,<span class="_ _8"> </span><span class="ff5">b</span>,<span class="_ _4"> </span><span class="ff5">c</span>,<span class="_ _8"> </span><span class="ff5">d<span class="_ _12"></span></span>,<span class="_ _8"> </span><span class="ff5">z</span>,<span class="_ _4"> </span>each<span class="_ _8"> </span>labeled</div><div class="t m0 x28 he y187 ff1 fs7 fc0 sc0 ls0 ws0">with<span class="_ _b"> </span>its<span class="_ _7"> </span>own<span class="_ _b"> </span>weight,<span class="_ _7"> </span>i.e.,<span class="_ _7"> </span><span class="ff5">w</span></div><div class="t m0 xa9 h13 y188 ff5 fs9 fc0 sc0 ls0 ws0">a</div><div class="t m0 xba h11 y189 ff9 fs7 fc0 sc0 ls0 ws0">&#188;<span class="_ _4"> </span><span class="ff1">10,<span class="_ _7"> </span><span class="ff5">w</span></span></div><div class="t m0 x5b h13 y188 ff5 fs9 fc0 sc0 ls0 ws0">b</div><div class="t m0 x61 h11 y189 ff9 fs7 fc0 sc0 ls0 ws0">&#188;<span class="_ _4"> </span><span class="ff1">5,<span class="_ _7"> </span><span class="ff5">w</span></span></div><div class="t m0 xbb h13 y188 ff5 fs9 fc0 sc0 ls0 ws0">c</div><div class="t m0 xbc h11 y189 ff9 fs7 fc0 sc0 ls0 ws0">&#188;<span class="_ _4"> </span><span class="ff1">2,</span></div><div class="t m0 x28 h1b y18a ff5 fs7 fc0 sc0 ls0 ws0">w</div><div class="t m0 x1e h13 y18b ff5 fs9 fc0 sc0 ls0 ws0">d</div><div class="t m0 x65 h11 y18c ff9 fs7 fc0 sc0 ls0 ws0">&#188;<span class="_ _4"> </span><span class="ff1">2<span class="_ _8"> </span>and<span class="_ _4"> </span><span class="ff5">w</span></span></div><div class="t m0 xbd h13 y18b ff5 fs9 fc0 sc0 ls0 ws0">z</div><div class="t m0 x5f h11 y18c ff9 fs7 fc0 sc0 ls0 ws0">&#188;<span class="_ _4"> </span><span class="ff1">2.<span class="_ _8"> </span>Let<span class="_ _4"> </span>us<span class="_ _8"> </span>consider<span class="_ _8"> </span>the<span class="_ _4"> </span>problem<span class="_ _8"> </span>of</span></div><div class="t m0 x25 ha y18d ff1 fs5 fc0 sc0 ls0 ws0">478<span class="_ _18"> </span><span class="ff4">C.<span class="_ _4"> </span>Casetti<span class="_ _4"> </span>et<span class="_ _4"> </span>al.<span class="_ _4"> </span>/<span class="_ _4"> </span>Computer<span class="_ _4"> </span>Networks<span class="_ _4"> </span>41<span class="_ _4"> </span>(2003)<span class="_ _4"> </span>475&#8211;487</span></div></div><div class="pi" data-data='{"ctm":[1.764706,0.000000,0.000000,1.764706,0.000000,0.000000]}'></div></div>
100+评论
captcha
    相关资源
    类型标题大小时间
    ZIPJAVA局域网飞鸽传书软件设计与实现.zip304.34KB8月前
    ZIPJAVA局域网监听软件的设计与开发.zip3.05MB8月前
    ZIP基于JAVA的足球社区管理系统（Vue.js+SpringBoot+MySQL）36.6MB8月前
    ZIP基于JAVA的社区物资互助平台（Vue.js+SpringBoot+MySQL）35.03MB8月前
    ZIP个人网站主页模板zip13.88MB8月前
    ZIP图像增强补丁3.00 请尽量使用官方无修改的游戏版本 反作弊是非法virus36.63KB8月前
    ZIPparsec-vdd-0.45475.08KB8月前
    ZIPParsec-vdd-cli323.81KB8月前