Automatically assigned DDC number: 00436

Manually assigned DDC number: 00462

Number of references: 8

Title: Distance Routing: a New Compact Routing Technique on Series Parallel Networks

Author:

Author:

Subject: Paola Flocchini,Flaminia L. Luccio Distance Routing: a New Compact Routing Technique on Series Parallel Networks

Description: We consider the problem of routing messages on networks modeled by Series Parallel Graphs (SPGs), and we introduce a new technique, called Distance Routing (DR). We first present an algorithm that computes shortest path DR on directed SPGs, and we show how to apply to these networks the shortest path 1-Interval Routing, one of the most common compact routing techniques. We also compute and compare the complexities of these two techniques showing the strong advantage of DR especially in terms of time complexity. We then show how Distance Routing can be used to route on bidirectional SPGs, where no general shortest path 1-Interval Routing Scheme can be applied. Index Terms: Routing, Compact Routing Algorithms, Distance Routing, Networks, Series Parallel Networks. 1 Introduction In a non anonymous network (i.e., in a network where to each node it is associated a different identity) routing can be easily accomplished if each node has available a routing table. This table has n Gamma 1 e...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1998-12-22

Format: ps

Identifier: http://citeseer.ist.psu.edu/163910.html

Source: http://w3.uqah.uquebec.ca/flocchin/Papers/distance.ps.gz

Language: en

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml   version="1.0"   encoding="UTF-8"?>

<references_metadata>

      <rec   ID="/534167.html"   Type="article"   CiteSeer_Book="Computer   Networks   and   ISDN   Systems"   CiteSeer_Volume="26"   Title="Prefix   routing   schemes   in   dynamic   networks,">

            <identifier   Org="ISBN:0521403766"   Paper_ID="/534167.html"   Extracted="0521403766"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.2"   />

            <identifier   Org="ISBN:0521794838"   Paper_ID="/534167.html"   Extracted="0521794838"   DDC="005.2/76"   Normalized_DDC="005276"   Normalized_Weight="0.2"   />

            <identifier   Org="ISBN:0769501435"   Paper_ID="/534167.html"   Extracted="0769501435"   />

            <identifier   Org="ISBN:0818656026"   Paper_ID="/534167.html"   Extracted="0818656026"   />

            <identifier   Org="ISBN:0818680628"   Paper_ID="/534167.html"   Extracted="0818680628"   />

            <identifier   Org="ISBN:0849331536"   Paper_ID="/534167.html"   Extracted="0849331536"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.2"   />

            <identifier   Org="ISBN:0886292530"   Paper_ID="/534167.html"   Extracted="0886292530"   DDC="811/.52"   Normalized_DDC="81152"   Normalized_Weight="0.2"   />

            <identifier   Org="ISBN:3540578994"   Paper_ID="/534167.html"   Extracted="3540578994"   DDC="004/.01/5115"   Normalized_DDC="004015115"   Normalized_Weight="0.2"   />

            <identifier   Org="ISBN:3540602461"   Paper_ID="/534167.html"   Extracted="3540602461"   />

            <identifier   Org="ISBN:9031314889"   Paper_ID="/534167.html"   Extracted="9031314889"   />

      </rec>

      <rec   ID="/115278.html"   Type="article"   CiteSeer_Book="ALCOM   Algorithms   Review   Newsletter   of   the   ESPRIT   II   Basic   Research   Actions   Program   Project   no   3075   ALCOM"   CiteSeer_Volume="2"   Title="Linear   Interval   Routing,">

            <identifier   Org="ISBN:0122007514"   Paper_ID="/115278.html"   Extracted="0122007514"   DDC="004.6/5"   Normalized_DDC="00465"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0471719978"   Paper_ID="/115278.html"   Extracted="0471719978"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0521794838"   Paper_ID="/115278.html"   Extracted="0521794838"   DDC="005.2/76"   Normalized_DDC="005276"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0769501435"   Paper_ID="/115278.html"   Extracted="0769501435"   />

            <identifier   Org="ISBN:0818673990"   Paper_ID="/115278.html"   Extracted="0818673990"   />

            <identifier   Org="ISBN:088629312X"   Paper_ID="/115278.html"   Extracted="088629312X"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0897918002"   Paper_ID="/115278.html"   Extracted="0897918002"   DDC="004.36"   Normalized_DDC="00436"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:1584885645"   Paper_ID="/115278.html"   Extracted="1584885645"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540578994"   Paper_ID="/115278.html"   Extracted="3540578994"   DDC="004/.01/5115"   Normalized_DDC="004015115"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540584307"   Paper_ID="/115278.html"   Extracted="3540584307"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540602461"   Paper_ID="/115278.html"   Extracted="3540602461"   />

            <identifier   Org="ISBN:3540602747"   Paper_ID="/115278.html"   Extracted="3540602747"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540606181"   Paper_ID="/115278.html"   Extracted="3540606181"   />

            <identifier   Org="ISBN:3540609229"   Paper_ID="/115278.html"   Extracted="3540609229"   DDC="004/.01/511"   Normalized_DDC="00401511"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540617698"   Paper_ID="/115278.html"   Extracted="3540617698"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540626166"   Paper_ID="/115278.html"   Extracted="3540626166"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540635750"   Paper_ID="/115278.html"   Extracted="3540635750"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540652604"   Paper_ID="/115278.html"   Extracted="3540652604"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07142857142857142"   />

      </rec>

      <rec   ID="/46278.html"   Type="inproceedings"   CiteSeer_Book="Symposium   on   Principles   of   Distributed   Computing"   CiteSeer_Volume=""   Title="A   Characterization   of   Networks   Supporting   Linear   Interval   Routing,">

            <identifier   Org="ISBN:0769501435"   Paper_ID="/46278.html"   Extracted="0769501435"   />

            <identifier   Org="ISBN:0818673990"   Paper_ID="/46278.html"   Extracted="0818673990"   />

            <identifier   Org="ISBN:088629312X"   Paper_ID="/46278.html"   Extracted="088629312X"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="1.0"   />

      </rec>

      <rec   ID="/107378.html"   Type="inproceedings"   CiteSeer_Book="Parallel   Processing   CONPAR94      VAPPVI"   CiteSeer_Volume=""   Title="Optimal   Interval   Routing,">

            <identifier   Org="ISBN:038794883X"   Paper_ID="/107378.html"   Extracted="038794883X"   DDC="511.3"   Normalized_DDC="5113"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0471719978"   Paper_ID="/107378.html"   Extracted="0471719978"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0769501435"   Paper_ID="/107378.html"   Extracted="0769501435"   />

            <identifier   Org="ISBN:0886292530"   Paper_ID="/107378.html"   Extracted="0886292530"   DDC="811/.52"   Normalized_DDC="81152"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:088629312X"   Paper_ID="/107378.html"   Extracted="088629312X"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0897917103"   Paper_ID="/107378.html"   Extracted="0897917103"   DDC="004.36"   Normalized_DDC="00436"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0897917170"   Paper_ID="/107378.html"   Extracted="0897917170"   DDC="004.22"   Normalized_DDC="00422"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0897918002"   Paper_ID="/107378.html"   Extracted="0897918002"   DDC="004.36"   Normalized_DDC="00436"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0897918096"   Paper_ID="/107378.html"   Extracted="0897918096"   DDC="004.35"   Normalized_DDC="00435"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:3540584307"   Paper_ID="/107378.html"   Extracted="3540584307"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:3540602461"   Paper_ID="/107378.html"   Extracted="3540602461"   />

            <identifier   Org="ISBN:3540617698"   Paper_ID="/107378.html"   Extracted="3540617698"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:3540634371"   Paper_ID="/107378.html"   Extracted="3540634371"   DDC="004.0151"   Normalized_DDC="0040151"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:3540645055"   Paper_ID="/107378.html"   Extracted="3540645055"   DDC="004.6/2"   Normalized_DDC="00462"   Normalized_Weight="0.08333333333333333"   />

      </rec>

      <rec   ID="/19221.html"   Type="article"   CiteSeer_Book="Algorithmica"   CiteSeer_Volume="21"   Title="Interval   Routing   Schemes,">

            <identifier   Org="ISBN:0521794838"   Paper_ID="/19221.html"   Extracted="0521794838"   DDC="005.2/76"   Normalized_DDC="005276"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0521876346"   Paper_ID="/19221.html"   Extracted="0521876346"   DDC="004.36"   Normalized_DDC="00436"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:0769501435"   Paper_ID="/19221.html"   Extracted="0769501435"   />

            <identifier   Org="ISBN:0886292530"   Paper_ID="/19221.html"   Extracted="0886292530"   DDC="811/.52"   Normalized_DDC="81152"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:088629312X"   Paper_ID="/19221.html"   Extracted="088629312X"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:1581131836"   Paper_ID="/19221.html"   Extracted="1581131836"   />

            <identifier   Org="ISBN:3540309357"   Paper_ID="/19221.html"   Extracted="3540309357"   DDC="004.015118"   Normalized_DDC="004015118"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540578994"   Paper_ID="/19221.html"   Extracted="3540578994"   DDC="004/.01/5115"   Normalized_DDC="004015115"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540584307"   Paper_ID="/19221.html"   Extracted="3540584307"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540590420"   Paper_ID="/19221.html"   Extracted="3540590420"   DDC="004/.01/511"   Normalized_DDC="00401511"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540602461"   Paper_ID="/19221.html"   Extracted="3540602461"   />

            <identifier   Org="ISBN:3540602747"   Paper_ID="/19221.html"   Extracted="3540602747"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540606181"   Paper_ID="/19221.html"   Extracted="3540606181"   />

            <identifier   Org="ISBN:3540617698"   Paper_ID="/19221.html"   Extracted="3540617698"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540626166"   Paper_ID="/19221.html"   Extracted="3540626166"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540650660"   Paper_ID="/19221.html"   Extracted="3540650660"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540652604"   Paper_ID="/19221.html"   Extracted="3540652604"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:354074990X"   Paper_ID="/19221.html"   Extracted="354074990X"   DDC="681/.2"   Normalized_DDC="6812"   Normalized_Weight="0.07142857142857142"   />

      </rec>

      <rec   ID="/11069.html"   Type="techreport"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="Worst   Case   Bounds   for   Shortest   Path   Interval   Routing,">

            <identifier   Org="ISBN:088629312X"   Paper_ID="/11069.html"   Extracted="088629312X"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.14285714285714285"   />

            <identifier   Org="ISBN:0897917103"   Paper_ID="/11069.html"   Extracted="0897917103"   DDC="004.36"   Normalized_DDC="00436"   Normalized_Weight="0.14285714285714285"   />

            <identifier   Org="ISBN:0897918002"   Paper_ID="/11069.html"   Extracted="0897918002"   />

            <identifier   Org="ISBN:0897918096"   Paper_ID="/11069.html"   Extracted="0897918096"   DDC="004.35"   Normalized_DDC="00435"   Normalized_Weight="0.14285714285714285"   />

            <identifier   Org="ISBN:0898714648"   Paper_ID="/11069.html"   Extracted="0898714648"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.14285714285714285"   />

            <identifier   Org="ISBN:1581131836"   Paper_ID="/11069.html"   Extracted="1581131836"   />

            <identifier   Org="ISBN:3540602461"   Paper_ID="/11069.html"   Extracted="3540602461"   />

            <identifier   Org="ISBN:3540609229"   Paper_ID="/11069.html"   Extracted="3540609229"   DDC="004/.01/511"   Normalized_DDC="00401511"   Normalized_Weight="0.14285714285714285"   />

            <identifier   Org="ISBN:3540634371"   Paper_ID="/11069.html"   Extracted="3540634371"   DDC="004.0151"   Normalized_DDC="0040151"   Normalized_Weight="0.14285714285714285"   />

            <identifier   Org="ISBN:3540652604"   Paper_ID="/11069.html"   Extracted="3540652604"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.14285714285714285"   />

      </rec>

      <rec   ID="/52232.html"   Type="misc"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="Boolean   routing   in   chordal   rings,"   />

      <rec   ID="/171712.html"   Type="article"   CiteSeer_Book="J   Algorithms"   CiteSeer_Volume="26"   Title="Interval   Routing   on   k   -Trees,">

            <identifier   Org="ISBN:0769501435"   Paper_ID="/171712.html"   Extracted="0769501435"   />

            <identifier   Org="ISBN:0818682272"   Paper_ID="/171712.html"   Extracted="0818682272"   />

            <identifier   Org="ISBN:088629312X"   Paper_ID="/171712.html"   Extracted="088629312X"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="1.0"   />

      </rec>

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="Distance   Routing:   a   New   Compact   Routing   Technique   on   Series   Parallel   Networks"   />

</references_metadata>

www.000webhost.com