Premium
A probabilistic model for the analysis of the routing process for circuits
Author(s) -
Agrawal P.,
Breuer M. A.
Publication year - 1980
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230100203
Subject(s) - routing (electronic design automation) , probabilistic logic , bounded function , path (computing) , computation , algorithm , mathematics , mathematical optimization , class (philosophy) , expected value , point (geometry) , computer science , probability density function , ideal (ethics) , process (computing) , topology (electrical circuits) , combinatorics , statistics , mathematical analysis , artificial intelligence , geometry , computer network , philosophy , epistemology , programming language , operating system
A probabilistic model is developed for studying the problem of routing printed circuits. The model, which uses the density of blockages on the carrier as a parameter, is based on the path‐searching mechanism of Lee's algorithm. Lee's algorithm is used in our analysis because it belongs to a class of pathfinding procedures which guarantee finding a path between two given points if one exists. It is shown that the routing probability, RM ( d ), is bounded above by PM ( d ), where PM ( d ) is the probability of existence of an arbitrary path of ideal Manhattan distance d from a given source point. Analytical computation shows that PM ( d ) is practically one until a density of about 35%. After this it sharply reduces, reaching a negligible value at a density of 43% for all but very small values of d . Some experiments related to the verification of the model are described. These experimental results show good agreement with the theoretically derived probabilities.