On the Generation of Explicit Routing Tables
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.
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.
5th International Conference on Computer Communication, Computer Communications: Increasing Benefits for Society (1980: Oct. 27-30, Atlanta, GA)
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
Article - Conference proceedings
© 1980 International Council for Computer Communication, All rights reserved.
01 Oct 1980