Efficient Update of Shortest Path Algorithms for Network Routing

Bin Xiao; Qingfeng ZhuGe; Edwin H.M. Sha

Efficient Update of Shortest Path Algorithms for Network Routing

Bin Xiao, Qingfeng ZhuGe, Edwin H.M. Sha

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

Abstract

In this paper, we present a new efficient update of shortest path algorithms for network routing, which make use of the information of the previously computed SPT. Besides efficiency, our algorithm maintain the most routing stability by making minimum changes to the topology of an existing SPT. In order to get the new SPT in the basic algorithm, we introduce a weight-change graph G^∗according to original graph G. Because of the nonnegative edge in G^∗, we can extend our idea about dynamic update of shortest path tree to a graph with negative edges. To the authors' knowledge, our algorithms are the most efficient algorithms known in the literature.

Original language	English
Title of host publication	14th International Conference on Parallel and Distributed Computing Systems 2001, PDCS 2001
Editors	Edwin Sha
Publisher	International Society for Computers and Their Applications (ISCA)
Pages	315-320
Number of pages	6
ISBN (Electronic)	9781618395740
Publication status	Published - 2001
Externally published	Yes
Event	14th International Conference on Parallel and Distributed Computing Systems, PDCS 2001 - Richardson, United States Duration: 8 Aug 2001 → 10 Aug 2001

Publication series

Name	14th International Conference on Parallel and Distributed Computing Systems 2001, PDCS 2001

Conference

Conference	14th International Conference on Parallel and Distributed Computing Systems, PDCS 2001
Country/Territory	United States
City	Richardson
Period	8/08/01 → 10/08/01

Keywords

OSPF
Routing
shortest path tree

ASJC Scopus subject areas

Computer Networks and Communications
Hardware and Architecture
Software

Cite this

Xiao, B., ZhuGe, Q., & Sha, E. H. M. (2001). Efficient Update of Shortest Path Algorithms for Network Routing. In E. Sha (Ed.), 14th International Conference on Parallel and Distributed Computing Systems 2001, PDCS 2001 (pp. 315-320). (14th International Conference on Parallel and Distributed Computing Systems 2001, PDCS 2001). International Society for Computers and Their Applications (ISCA).

Xiao, Bin ; ZhuGe, Qingfeng ; Sha, Edwin H.M. / Efficient Update of Shortest Path Algorithms for Network Routing. 14th International Conference on Parallel and Distributed Computing Systems 2001, PDCS 2001. editor / Edwin Sha. International Society for Computers and Their Applications (ISCA), 2001. pp. 315-320 (14th International Conference on Parallel and Distributed Computing Systems 2001, PDCS 2001).

@inproceedings{c303ef9b055a49b7bc7e3492fc37e1ac,

title = "Efficient Update of Shortest Path Algorithms for Network Routing",

abstract = "In this paper, we present a new efficient update of shortest path algorithms for network routing, which make use of the information of the previously computed SPT. Besides efficiency, our algorithm maintain the most routing stability by making minimum changes to the topology of an existing SPT. In order to get the new SPT in the basic algorithm, we introduce a weight-change graph G∗according to original graph G. Because of the nonnegative edge in G∗, we can extend our idea about dynamic update of shortest path tree to a graph with negative edges. To the authors' knowledge, our algorithms are the most efficient algorithms known in the literature.",

keywords = "OSPF, Routing, shortest path tree",

author = "Bin Xiao and Qingfeng ZhuGe and Sha, {Edwin H.M.}",

note = "Publisher Copyright: {\textcopyright} (2001) by the International Society for Computers and Their Applications All rights reserved.; 14th International Conference on Parallel and Distributed Computing Systems, PDCS 2001 ; Conference date: 08-08-2001 Through 10-08-2001",

year = "2001",

language = "English",

series = "14th International Conference on Parallel and Distributed Computing Systems 2001, PDCS 2001",

publisher = "International Society for Computers and Their Applications (ISCA)",

pages = "315--320",

editor = "Edwin Sha",

booktitle = "14th International Conference on Parallel and Distributed Computing Systems 2001, PDCS 2001",

address = "United States",

}

Xiao, B, ZhuGe, Q & Sha, EHM 2001, Efficient Update of Shortest Path Algorithms for Network Routing. in E Sha (ed.), 14th International Conference on Parallel and Distributed Computing Systems 2001, PDCS 2001. 14th International Conference on Parallel and Distributed Computing Systems 2001, PDCS 2001, International Society for Computers and Their Applications (ISCA), pp. 315-320, 14th International Conference on Parallel and Distributed Computing Systems, PDCS 2001, Richardson, United States, 8/08/01.

Efficient Update of Shortest Path Algorithms for Network Routing. / Xiao, Bin; ZhuGe, Qingfeng; Sha, Edwin H.M.
14th International Conference on Parallel and Distributed Computing Systems 2001, PDCS 2001. ed. / Edwin Sha. International Society for Computers and Their Applications (ISCA), 2001. p. 315-320 (14th International Conference on Parallel and Distributed Computing Systems 2001, PDCS 2001).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Efficient Update of Shortest Path Algorithms for Network Routing

AU - Xiao, Bin

AU - ZhuGe, Qingfeng

AU - Sha, Edwin H.M.

PY - 2001

Y1 - 2001

N2 - In this paper, we present a new efficient update of shortest path algorithms for network routing, which make use of the information of the previously computed SPT. Besides efficiency, our algorithm maintain the most routing stability by making minimum changes to the topology of an existing SPT. In order to get the new SPT in the basic algorithm, we introduce a weight-change graph G∗according to original graph G. Because of the nonnegative edge in G∗, we can extend our idea about dynamic update of shortest path tree to a graph with negative edges. To the authors' knowledge, our algorithms are the most efficient algorithms known in the literature.

AB - In this paper, we present a new efficient update of shortest path algorithms for network routing, which make use of the information of the previously computed SPT. Besides efficiency, our algorithm maintain the most routing stability by making minimum changes to the topology of an existing SPT. In order to get the new SPT in the basic algorithm, we introduce a weight-change graph G∗according to original graph G. Because of the nonnegative edge in G∗, we can extend our idea about dynamic update of shortest path tree to a graph with negative edges. To the authors' knowledge, our algorithms are the most efficient algorithms known in the literature.

KW - OSPF

KW - Routing

KW - shortest path tree

UR - http://www.scopus.com/inward/record.url?scp=85133128758&partnerID=8YFLogxK

M3 - Conference article published in proceeding or book

AN - SCOPUS:85133128758

T3 - 14th International Conference on Parallel and Distributed Computing Systems 2001, PDCS 2001

SP - 315

EP - 320

BT - 14th International Conference on Parallel and Distributed Computing Systems 2001, PDCS 2001

A2 - Sha, Edwin

PB - International Society for Computers and Their Applications (ISCA)

T2 - 14th International Conference on Parallel and Distributed Computing Systems, PDCS 2001

Y2 - 8 August 2001 through 10 August 2001

ER -

Xiao B, ZhuGe Q, Sha EHM. Efficient Update of Shortest Path Algorithms for Network Routing. In Sha E, editor, 14th International Conference on Parallel and Distributed Computing Systems 2001, PDCS 2001. International Society for Computers and Their Applications (ISCA). 2001. p. 315-320. (14th International Conference on Parallel and Distributed Computing Systems 2001, PDCS 2001).

Efficient Update of Shortest Path Algorithms for Network Routing

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this