Browse Prior Art Database

Communication Line Configurator Algorithm Using Computational Pruning

IP.com Disclosure Number: IPCOM000101756D
Original Publication Date: 1990-Aug-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 3 page(s) / 123K

Publishing Venue

IBM

Related People

Leung, YM: AUTHOR [+2]

Abstract

Disclosed is an algorithm for solving a multiple-constraint configuration problem without exhaustive node search. It was developed for configuration of communication lines, but could be applied to any configuration task with analogous constraints.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Communication Line Configurator Algorithm Using Computational Pruning

       Disclosed is an algorithm for solving a
multiple-constraint configuration problem without exhaustive node
search.  It was developed for configuration of communication lines,
but could be applied to any configuration task with analogous
constraints.

      Communication lines in this application attach to ports on I/O
Adapter cards (IOAs), which, in turn, are driven by I/O Processor
cards (IOPs).  Each IOP may drive one or more IOAs, and each IOA
contains several ports for the attachment of lines.  The total number
of lines driven by an IOP group is limited by the aggregate data
capacity of the IOP, the number of IOAs it can support, and the port
addresses available.  Certain lines or combinations of lines cause a
reduction in the total aggregate data capacity of the IOP.  Certain
type IOAs are compatible only with a restricted set of lines.

      The primary task of the algorithm is to find a configuration of
lines that requires the least amount of supporting IOP and IOA
hardware.  Certain lower priority preferences may also be
implemented. This task can be represented by a decision tree, in
which each level corresponds to the placement of a single
communications line, and each branch at that level corresponds to an
IOP which is a possible place for the line.  The number of nodes at
any level n is bounded by np**(n1), where np is the number of IOPs in
the system.  With large systems, exhaustive node search becomes
impractical.

      The process is illustrated in the figure.  It begins by
calculating the minimum number of IOAs and IOPs required based on the
total number, protocols and data rates of the lines.  Those lines
which cause a degradation of an IOP's aggregate data capacity are
also taken into account.  The minimum number of IOPs thus calculated
are made available immediately for the assignment of lines.

      After initialization, the algorithm begins to assign lines to
IOPs one by one, generally assigning the most difficult to place
lines first.  At each level, it considers all possible branches
(placements for the line), and performs a pruning calculation with
respect to each.  To support pruning, the program maintains various
counters, which record the total remaining unused data capacity of
the IOPs, unused line addresses, unused IOA capacity, and unused
physical ports of each type.  It also records the total data
capacity, line addresses, etc., required to service the lines not yet
placed. Whenever a line is assigned to an IOP, that placement reduces
the total remaining capacity of the IOPs, as well as...