Paper Info
Title
Robustness of the destination tag based routing algorithm for the control of unique path networks (abstract only)
Abstract
There is a considerable literature on the analysis of average bandwidth of unique path networks such as the Baseline network, Omega network etc. These methods proceed by analysing the average bandwidth of complete cross-bar networks under standard assumptions such as “independence”, and “uniformity” of the destination tags across the various memory modules. Since the destination tag based routing algorithms in a sense preserve the above properties across the various stages of the unique path networks, the analysis of the complete cross- bar could be readily carried over to these networks. All these methods are essentially probabilistic in nature [1]. Once the input to the network is given, since the routing algorithm is deterministic in nature, we present a deterministic analysis of the behavior of these networks under random inputs using the destination tag based routing algorithms.A unique path network built out of cross bar switches with two inputs and two outputs has k stages with each stage containing N/2 switches, where N = 2**k. Of the total Nk bits in the input, only Nk/2 bits are used to control the network. The rest of the Nk/2 bits are called the “don't-care” bits. These don't-care bits do not take part in the control of the network. Infact, by fixing the control bits, we can fix the settings of the switches in all the stages. Now one can change the don't-care bits to generate a variety of random inputs. To analyze the possibility of random inputs through the network, we introduce a new possibility condition. Let = { 0,1,2,3,……,N-1 }. Let f be a function mappings to . Let kj = {x:ƒ(x)=j Clearly 0≤ kj ≤N and kj = N Define Iƒ = |{j|kj = &Ogr;}| called the index of the function f. If Iƒ = N, then f is a permutation. We say the function f is passable if there exists a setting of the switches of the network such that exactly one input terminal from each kj is connected to the output terminal j. This new definition is clearly a generalization of now well known possibility condition for the permutations. Using the properties of the destination tag based routing algorithms, the properties of a number of sub-classes of the random inputs under the generalized possibility conditions are analysed.Our method does not require detailed assumptions as in [1] such as the independence and uniformity etc. While the methods given in [1] are not applicable to the rearrangeable networks, our method is easily extendable to rearrangeable networks as well.
Year
DOI
Venue
1987
10.1145/322917.323120
ACM Conference on Computer Science
Keywords
Field
DocType
omega network etc.,t-care bit,average bandwidth,baseline network,destination tag,unique path network,n define,rearrangeable network,random input,complete cross-bar network,ada,frame,object oriented design,artificial intelligence,inference engine
Object-oriented design,Existential quantification,Computer science,Permutation,Theoretical computer science,Robustness (computer science),Bandwidth (signal processing),Inference engine,Omega network,Probabilistic logic,Distributed computing
Conference
ISBN
Citations 
PageRank 
0-89791-218-7
0
0.34
References 
Authors
3
1
Name
Order
Citations
PageRank
Abdulraouf Y. Al-Hallaq100.68