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>