Browse Prior Art Database

Queued Slots Redistribution Process

IP.com Disclosure Number: IPCOM000100839D
Original Publication Date: 1990-Jun-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 4 page(s) / 159K

Publishing Venue

IBM

Related People

Feraud, J: AUTHOR [+2]

Abstract

This article relates to an algorithm allowing input character strings of constant length received from "n2" transmission sources and enqueued in "n2" queues (one queue per input source) to be redistributed among "n2" output sinks in less than a given time interval through "n" full-duplex servers. The redistribution delay is minimized, avoiding any conflict between two or more strings having the same destination.

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

Queued Slots Redistribution Process

       This article relates to an algorithm allowing input
character strings of constant length received from "n2" transmission
sources and enqueued in "n2" queues (one queue per input source) to
be redistributed among "n2" output sinks in less than a given time
interval through "n" full-duplex servers. The redistribution delay is
minimized, avoiding any conflict between two or more strings having
the same destination.

      For instance, let us assume that 4x4 input sources deliver
character slots to 4 groups of queues A, B, C, D. Group A contains 4
queues, each one corresponding, respectively, with destinations a, b,
c, d, that is, any queue contained in groups A, B, C or D. When
input sources deliver slots, the slot destination is recognized and
each character slot is enqueued in the proper sink queue. Each queue
is named according to its group and its destination, i.e., queues
"Aa, Ab, Ac, Ad, Ba, Bc, ... Dd" contain any number of slots,
provided that the slot sum in each group A, B, C, D is constant and
equal to 128 slots, for instance. The slot sums Aa + Ba + Ca +
Da, Ab + Bb + Cb Db, Ac + Bc + Cc + Dc, Ad
+ Bd + Cd + Dd are NOT RESTRICTED to be 128.

      The algorithm allows to evaluate the content of these 16 queues
in a maximum of 125 microseconds, through 4 full-duplex servers.
Group A contains 4 queues:  Aa   Ab   Ac   Ad  (Aa = for itself)
...  B   ....   4  ...   :  Ba   Bb   Bc   Bd  (Bb = for itself)
...  C   ....   4  ...   :  Ca   Cb   Cc   Cd  (Cc = for itself)
...  D   ....   4  ...   :  Da   Db   Dc   Dd  (Dd = for itself)
                    total  : 128  128  128  128

      Each of the 4 groups contains a total of 128 slots, the average
number of queued slots of 32 slots per queue, with all possible
statistical variations. If transferring one character slot requires
one "cycle", with one single server, 512 cycles would be needed to
transfer slots to their destinations. With 4 servers, a circular
permutation algorithm may be used: then the best case occurs when
each queue rigorously contains 32 slots; then 128 cycles only are
needed to complete the transfer of all queues contents. With an input
random distribution of the 128 slots among 4 queues per group, one
can expect to complete the transfer in a number of cycles that lies
between 128 and 512 cycles (128 slots in one group queue and zero in
the 3 other queues being the worst distribution case).

      The utilization of servers requires that some order be used to
scan the group queues to avoid collisions, i.e., two queues competing
for the same server.

      A conventional circular permutation algorithm proves to be very
efficient: Assuming "cycle passing" when a queue is found empty
during one cycle, the gain in time over a classical transmission was
found to go from 0% for the worst slot distribution cases (peak
distributi...