A STRATEGY OF DESIGNING ROUTING ALGORITHMS BASED ON IDEAL ROUTINGS

K. Shinjo, S. Shimogawa, J. Yamada and K. Oida
Additional contact information
K. Shinjo: ATR Adaptive Communications Research Laboratories, Seika-cho, Soraku-gun, Kyoto 619-02, Japan
S. Shimogawa: ATR Adaptive Communications Research Laboratories, Seika-cho, Soraku-gun, Kyoto 619-02, Japan
J. Yamada: ATR Adaptive Communications Research Laboratories, Seika-cho, Soraku-gun, Kyoto 619-02, Japan
K. Oida: ATR Adaptive Communications Research Laboratories, Seika-cho, Soraku-gun, Kyoto 619-02, Japan

International Journal of Modern Physics C (IJMPC), 1999, vol. 10, issue 01, 63-94

Abstract: This paper proposes a strategy of designing routing algorithms for connectionless packet-switched networks. This strategy consists of three design elements as follows: [A] the notion of ideal routings is introduced to provide the upper performance limits attained by improving routing algorithm and it serves as a standard to measure the performance of other algorithms; [B] a method of constructing simple algorithms is presented under implementation conditions from ideal routings; [C] a method is described to enhance the performance limits of [A]. By using these elements, simple algorithms with a maximum degree of performance attainment are realized. By "degree of performance attainment", we mean that we can see how much room is left for the improvement of algorithms. We develop [A] and [B] with the performance measures of throughput and average packet delay and the M/M/1 queuing network. We decide ideal static routings and their performance limits from [A]. We obtain a new simple algorithm from [B] based on the notion of the ideal routings in implementation conditions. The designed algorithm improves the throughput and the average delay, which are comparable to those from ideal static routings. This improvement is contrasted to the adaptive and distributed OSPF (Open Shortest Path First), a standard Internet routing protocol.

Keywords: Control algorithms; Routing algorithms; Connectionless networks; Ideal routings (search for similar items in EconPapers)
Date: 1999
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S012918319900005X
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijmpcx:v:10:y:1999:i:01:n:s012918319900005x

Ordering information: This journal article can be ordered from

DOI: 10.1142/S012918319900005X

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().