
STANDARD PRODUCT
PM7323 RCMP-200
DATASHEET
PMC-960543
ISSUE 2
ROUTING CONTROL, MONITORING, & POLICING
200 MBPS
Proprietary and Confidential to PMC-Sierra, Inc.
and for its Customer’s Internal Use.
165
Note:
The algorithm presented below has the following features which optimize it for
VC identification:
1. Only those bits in the Secondary Search Key required to make an unique
identification are examined. This minimizes the average search time.
2. The number of nodes in the Secondary Search Table is bounded by the
number of VC Table entries. Therefore, the depth of memory required for the
Secondary Search Table is equal to that required for the VC Table.
3. Nodes can be added or deleted on the fly without corrupting a binary search
in progress.
A C-language example of the algorithm will be made available.
12.4.1 Overview
The VC search algorithm maps the cell's PHY identifier, VCI, VPI and selected
portions of appended bytes to a 16-bit VC Table address. Effectively, it performs
the operation of a Content Addressable Memory (CAM). The data structure
created to support the VC identification is designed around maximizing the
efficiency of the process.
It is the Select field in the Secondary Search Table which makes the search
efficient, because it allows each branching decision to be made based on only
the first bit in which two branches differ. That is, as two values are compared,
starting with the MSB (most significant bit) and moving to the LSB (least
significant bit), the two can be fully discriminated based on the first bit in which
they differ. No other bits after that bit, regardless of how much they differ, need
to be considered. Because not all bits are not examined in the binary search, the
search is concluded with a confirmation step which compares the Secondary
Search Key against the VPI/VCI of the candidate VC Table.
The following sub-sections describe the search table initialization, connection
addition and connection removal processes. Refer to the VC Identification sub-
section of the Functional Description section for definitions of the Primary and
Secondary Search Keys, for an overview of the search process and for a
definition of the data structures.