On the Generation of Explicit Routing Tables
Abstract
Explicit routing offers some good features for packet-switching. This paper considers three table-driven explicit routing algorithms depending on the information carried in the packet header and how the packet is steered at the intermediate nodes. These are the origin-dependent algorithm, the origin-independent non-swap algorithm and the origin-independent swap algorithm. This paper assumed that the routes to be defined in the routing tables are given and for each of the above routing algorithms, describes algorithms for generating the corresponding routing tables. In discussing the origin-independent swap algorithm, we show that the explicit route number assignment problem is NP-complete and discuss a number of heuristic approaches to its solution. All the algorithms described have been coded in PL/1 and run successfully.
Recommended Citation
K. Maruyama and G. Markowsky, "On the Generation of Explicit Routing Tables," Proceedings of the 5th International Conference on Computer Communication, Computer Communications: Increasing Benefits for Society (1980, Atlanta, GA), pp. 90 - 95, International Council for Computer Communication, Oct 1980.
Meeting Name
5th International Conference on Computer Communication, Computer Communications: Increasing Benefits for Society (1980: Oct. 27-30, Atlanta, GA)
Department(s)
Computer Science
Keywords and Phrases
Explicit Routing Algorithms; Heuristic Approaches to Solution of Mathematical Problems; Origin Dependent Algorithms; Origin Independent Non-swap Algorithm; Origin-independent Swap Algorithms; Packet Switched Communication Networks; Routing Tables; Computers
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 1980 International Council for Computer Communication, All rights reserved.
Publication Date
01 Oct 1980
