S/UNI®-ATLAS-3200 Telecom Standard Product Data Sheet
Preliminary
Figure 13 Construction of Primary and Secondary Keys
(L +L
P
)
2
-1
A
0
Primary Search Table
Secondary
Search
Tabl e
Ingress
VC
Ingress
VC
Tabl e
Entry
Tabl e
Entry
Ingress
VC
Ingress
VC
Ingress
VC
Ingress
VC
Ingress
VC
Ingress
VC
Ingress
VC
Tabl e
Entry
Tabl e
Entry
Tabl e
Entry
Tabl e
Entry
Tabl e
Entry
Tabl e
Entry
Tabl e
Entry
Ingress
VC
Tabl e
Entry
Ingress
VC
Tabl e
Entry
The following gives the immutable coding rules for the search data structures. The coding
supports numerous possible algorithms, but the S/UNI-ATLAS-3200 software driver presents an
algorithm that is optimized for most applications.
Primary Search Table
The Primary Search Table contains an array of pointers (the Primary Search Pointers) that point to
the roots of binary trees. The table is directly indexed by the contents of the Primary Search Key,
as defined above. For any given received cell, the Search Table entry pointed to by the Primary
Search Key contains the Primary Search Pointer which points to the root of the Secondary Search
binary tree for that cell.
The entire Primary Search Table must be initialized to all zeros. A table value of zero represents a
null pointer; therefore, the initial state means no provisioned connections are defined. If a
connection is added which results in a new binary search tree (i.e. it is the only connection
associated with a particular Primary Search Key), the appropriate Primary Search Pointer must
point to the newly created binary search tree root. If the last connection with a particular Primary
Search Key is removed, the associated Primary Search Pointer must be set to all zeros.
Secondary Search Table
The Secondary Search Table consists of a set of binary search trees. Each tree’s root is
pointed to by a Primary Search Pointer. Each node in the tree is represented by a 42-bit
data structure. The fields of the Secondary Search Table are described below.
Table 6 Secondary Search Table Fields
Name
Selector
Description
The Selector field is a 6 bit field which is the index of the Secondary
Search Key bit upon which the branching decision of the binary
search is based. An index of zero represents the LSB. If the
selected bit is a logic 1, the Left Leaf and Left Branch fields are
subsequently used. Likewise, if the selected bit is a logic 0, the Right
Leaf and Right Branch are subsequently used. Typically, the
Selector value decreases monotonically with the depth of the tree, but
Proprietary and Confidential to PMC-Sierra, Inc., and for its Customers’ Internal Use
Document ID: PMC-1990553, Issue 4
78
PMC [ PMC-SIERRA, INC ]
