Automatically assigned DDC number: 00465
Manually assigned DDC number: 004652
Number of references: 4
Title: A Distributed Algorithm for Delay-Constrained Unicast Routing
Author:
Author:
Author:
Subject: H. F. Salama,D. S. Reeves,Y. Viniotis A Distributed Algorithm for Delay-Constrained Unicast Routing
Description: We define the problem of unicast routing subject to delay constraints in point-to-point connection-oriented networks as a delay-constrained least-cost path problem. This problem is NP-complete, and therefore we propose a simple, efficient, distributed heuristic solution: the delay-constrained unicast routing (DCUR) algorithm. DCUR requires limited information about the network state to be kept at each node. This information is stored in a cost vector and a delay vector which resemble the distance vectors of some existing routing protocols. We prove the correctness of DCUR by showing that it is always capable of constructing a loop-free delay-constrained path within finite time, if such a path exists. The number of computations DCUR performs at each node participating in the path construction process is fixed, irrespective of the size of the network. The message complexity of DCUR is O(jV j 3 ) messages in the worst case, where jV j is the number of nodes in the network. However, simu...
Contributor: The Pennsylvania State University CiteSeer Archives
Publisher: unknown
Date: 1996-07-30
Pubyear: 1997
Format: ps
Identifier: http://citeseer.ist.psu.edu/149843.html
Source: ftp://ftp.eos.ncsu.edu/pub/ccsp/papers/ppr9626.PS
Language: en
Relation:
Relation:
Relation:
Relation:
Rights: unrestricted
<?xml version="1.0" encoding="UTF-8"?>
<references_metadata>
<rec ID="/608098.html" Type="techreport" CiteSeer_Book="" CiteSeer_Volume="" Title="Routing Information Protocol,">
<identifier Org="ISBN:0123740134" Paper_ID="/608098.html" Extracted="0123740134" DDC="004.6/5" Normalized_DDC="00465" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:0131876716" Paper_ID="/608098.html" Extracted="0131876716" DDC="004.6" Normalized_DDC="0046" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:0470110090" Paper_ID="/608098.html" Extracted="0470110090" DDC="004.65" Normalized_DDC="00465" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:0470848561" Paper_ID="/608098.html" Extracted="0470848561" DDC="004.6" Normalized_DDC="0046" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:0471215929" Paper_ID="/608098.html" Extracted="0471215929" DDC="004.6/2" Normalized_DDC="00462" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:0596002750" Paper_ID="/608098.html" Extracted="0596002750" DDC="004.6/2" Normalized_DDC="00462" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:0596002971" Paper_ID="/608098.html" Extracted="0596002971" DDC="004.62" Normalized_DDC="00462" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:0672325659" Paper_ID="/608098.html" Extracted="0672325659" DDC="005.7/1376" Normalized_DDC="00571376" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:0789728702" Paper_ID="/608098.html" Extracted="0789728702" DDC="005.4469" Normalized_DDC="0054469" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:1578203023" Paper_ID="/608098.html" Extracted="1578203023" DDC="004.6" Normalized_DDC="0046" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:1578700418" Paper_ID="/608098.html" Extracted="1578700418" DDC="004.6/2" Normalized_DDC="00462" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:1578700698" Paper_ID="/608098.html" Extracted="1578700698" DDC="004.6/5" Normalized_DDC="00465" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:157870071X" Paper_ID="/608098.html" Extracted="157870071X" DDC="005.7/1376" Normalized_DDC="00571376" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:1587050242" Paper_ID="/608098.html" Extracted="1587050242" DDC="004.6" Normalized_DDC="0046" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:159327047X" Paper_ID="/608098.html" Extracted="159327047X" DDC="004.6/2" Normalized_DDC="00462" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:1931836019" Paper_ID="/608098.html" Extracted="1931836019" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:1931836639" Paper_ID="/608098.html" Extracted="1931836639" />
<identifier Org="ISBN:1931836906" Paper_ID="/608098.html" Extracted="1931836906" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540678638" Paper_ID="/608098.html" Extracted="3540678638" DDC="004/.01/5113" Normalized_DDC="004015113" Normalized_Weight="0.05555555555555555" />
</rec>
<rec ID="/160643.html" Type="article" CiteSeer_Book="Computer Networks and ISDN Systems" CiteSeer_Volume="24" Title="Single Path Routing with Delay Considerations,">
<identifier Org="ISBN:0890066574" Paper_ID="/160643.html" Extracted="0890066574" DDC="621.382/7" Normalized_DDC="6213827" Normalized_Weight="0.5" />
<identifier Org="ISBN:3540747664" Paper_ID="/160643.html" Extracted="3540747664" DDC="004.6" Normalized_DDC="0046" Normalized_Weight="0.5" />
</rec>
<rec ID="/4773.html" Type="misc" CiteSeer_Book="" CiteSeer_Volume="" Title="An Evaluation of Routing and Admission Control Algorithms for Multimedia Traffic in Packet-switched Networks,">
<identifier Org="ISBN:0818678143" Paper_ID="/4773.html" Extracted="0818678143" />
<identifier Org="ISBN:0818680164" Paper_ID="/4773.html" Extracted="0818680164" />
</rec>
<rec ID="/113943.html" Type="article" CiteSeer_Book="IEEE Journal of Selected Areas in Communications" CiteSeer_Volume="13" Title="Competitive Routing of Virtual Circuits in {ATM} Networks,">
<identifier Org="ISBN:0387986804" Paper_ID="/113943.html" Extracted="0387986804" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:0412809702" Paper_ID="/113943.html" Extracted="0412809702" DDC="004.66" Normalized_DDC="00466" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:0780357973" Paper_ID="/113943.html" Extracted="0780357973" />
<identifier Org="ISBN:0780374002" Paper_ID="/113943.html" Extracted="0780374002" />
<identifier Org="ISBN:0780378024" Paper_ID="/113943.html" Extracted="0780378024" />
<identifier Org="ISBN:0780389387" Paper_ID="/113943.html" Extracted="0780389387" />
<identifier Org="ISBN:0780394143" Paper_ID="/113943.html" Extracted="0780394143" />
<identifier Org="ISBN:0818678534" Paper_ID="/113943.html" Extracted="0818678534" />
<identifier Org="ISBN:0849323576" Paper_ID="/113943.html" Extracted="0849323576" DDC="004.2/4" Normalized_DDC="00424" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:0849326494" Paper_ID="/113943.html" Extracted="0849326494" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:0897918886" Paper_ID="/113943.html" Extracted="0897918886" />
<identifier Org="ISBN:0897919963" Paper_ID="/113943.html" Extracted="0897919963" />
<identifier Org="ISBN:1581138520" Paper_ID="/113943.html" Extracted="1581138520" />
<identifier Org="ISBN:3540253386" Paper_ID="/113943.html" Extracted="3540253386" DDC="004.6" Normalized_DDC="0046" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540404562" Paper_ID="/113943.html" Extracted="3540404562" DDC="004.67/8" Normalized_DDC="004678" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540437096" Paper_ID="/113943.html" Extracted="3540437096" DDC="004.6" Normalized_DDC="0046" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540438645" Paper_ID="/113943.html" Extracted="3540438645" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540655786" Paper_ID="/113943.html" Extracted="3540655786" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1111111111111111" />
</rec>
<rec ID="SELF" Type="SELF" CiteSeer_Book="SELF" CiteSeer_Volume="SELF" Title="A Distributed Algorithm for Delay-Constrained Unicast Routing">
<identifier Org="ISBN:078036452X" Paper_ID="SELF" Extracted="078036452X" />
<identifier Org="ISBN:0780365364" Paper_ID="SELF" Extracted="0780365364" DDC="006.7" Normalized_DDC="0067" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:0780370783" Paper_ID="SELF" Extracted="0780370783" />
<identifier Org="ISBN:0780370988" Paper_ID="SELF" Extracted="0780370988" />
<identifier Org="ISBN:0780372069" Paper_ID="SELF" Extracted="0780372069" />
<identifier Org="ISBN:0780378024" Paper_ID="SELF" Extracted="0780378024" />
<identifier Org="ISBN:0780385217" Paper_ID="SELF" Extracted="0780385217" />
<identifier Org="ISBN:0780385330" Paper_ID="SELF" Extracted="0780385330" />
<identifier Org="ISBN:0780387945" Paper_ID="SELF" Extracted="0780387945" />
<identifier Org="ISBN:0818677821" Paper_ID="SELF" Extracted="0818677821" />
<identifier Org="ISBN:1402076169" Paper_ID="SELF" Extracted="1402076169" DDC="005.8" Normalized_DDC="0058" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:3540240756" Paper_ID="SELF" Extracted="3540240756" DDC="004.6/78" Normalized_DDC="004678" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:3540438661" Paper_ID="SELF" Extracted="3540438661" DDC="511.8" Normalized_DDC="5118" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:354067506X" Paper_ID="SELF" Extracted="354067506X" DDC="621.382/1" Normalized_DDC="6213821" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:3540723927" Paper_ID="SELF" Extracted="3540723927" />
<identifier Org="ISBN:3540747834" Paper_ID="SELF" Extracted="3540747834" DDC="004.6/5" Normalized_DDC="00465" Normalized_Weight="0.14285714285714285" />
<identifier Org="ISBN:7800908275" Paper_ID="SELF" Extracted="7800908275" DDC="621.382" Normalized_DDC="621382" Normalized_Weight="0.14285714285714285" />
</rec>
</references_metadata>