Browse Prior Art Database

Original Publication Date: 1974-Apr-10
Included in the Prior Art Database: 2007-Mar-30
Document File: 42 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Pippenger, Nicholas: AUTHOR [+2]


Nicholas Pippenger

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 9% of the total text.

Page 1 of 42


Nicholas Pippenger

 Department of Mathematical Sciences IBM Thomas J. Watson Research Center

Yorktown Heights, New York 10598


     A probabilistic model (called the virtual state model) is presented
for uniform networks (those without concentration or expansion). This model takes account of the dependence between link occupancies due to the fact that the occupied links form a set of disjoint routes from inputs to outputs. The virtual state model is used to derive an exact expression
for the blocking probability of a uniform series-parallel network. These expressions are then used to study the complexity of such networks. It
is shown that a uniform series-parallel network carrying a load of N erlangs with akblocking probability at most E can be constructed with 6N log2 N +

O(N log 1/~)
contacts. An explicit plan for the network is given.

RC 4802 (il21350)

April 10, 1974 Communicat:ions

[This page contains 1 picture or other non-text object]

Page 2 of 42


This report has been submitted for publication elsewhere and has been issued as a Research Report for early dissemination of its contents. As a courtesy to the intended publisher, it should not be widely distributed until after the date of outside publication.

Copies may be requested from:
IBM Thomas J. Watson Research Center Post Office Box 218
Yorktown Heights, New York 10598

[This page contains 1 picture or other non-text object]

Page 3 of 42

I. Introduction

This paper deals with networks of the type used to switch traffic in

communication exchanges. Because the number of components in such net- works increases more rapidly than the traffic carried, they exhibit an intrinsic diseconomy of scale which makes their complexity a dominant factor in the cost of any sufficiently large exchange.

    We shall study the relationship among 'three factors: load (a measure of the task presented to the network), blocking probability (a measure of the effectiveness with which this task is performed, and complexity (a measure of cost). Our results w i l l be stated for a certain class of cross- bar networks (series-parallel networks without concentration or expansion), but can be translated to deal with time-division networks 121. Our treat- ment of load and blocking probability w i l l be based on a new probabilistic
;model for the behavior of networks, introduced in an attempt to overcome the shortcomings of previous models. Our measure of complexity w i l l be the number of contacts, but our results hold, a t least qualitatively, for many other complexity measures as well.

    For our purposes, a network is a directed graph. Those vertices into which no edge is directed are called inputs, those out of which no edge is directed are called outputs, and all others are called links. If the number...