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.

Meeting Name

5th International Conference on Computer Communication, Computer Communications: Increasing Benefits for Society (1980: Oct. 27-30, Atlanta, GA)


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


File Type





© 1980 International Council for Computer Communication, All rights reserved.

Publication Date

01 Oct 1980

This document is currently not available here.