PM8621 PMC-Sierra, Inc., PM8621 Datasheet - Page 160

• Manufacturer Part Number: PM8621
• Description: NSE-8G Standard Product Data Sheet Preliminary
• Manufacturer: PMC-Sierra, Inc.

12.13.3 Bi-partite graphs
Proprietary and Confidential to PMC-Sierra, Inc., and for its Customers’ Internal Use
Document ID: PMC-2010850, Issue 1
Consider a request to route an octet from ingress port i to egress port j, where i and j range from
0 to 3, over four ports corresponding to the four SBS devices. To make this connection, we must
find a timeslot in the NSE-8G which can accept an octet from the ingress SBS and send an octet
to the egress SBS. If the NSE-8G has these two slots free in the same timeslot, then the SBSs
must also have the corresponding slot free. The actual routing of the sample is accomplished in
several steps. The octet is:
1. mapped to the free timeslot by the ingress SBS port,
2. picked up by the NSE-8G in that timeslot on the port from the ingress SBS and mapped to the
3. picked up by the egress SBS in the expected timeslot.
It may not be possible to find a free time which connects the ingress SBS to the egress SBS, even
though both SBS devices have unused capacity into the NSE-8G core (the ingress SBS may have
a free timeslot at time i and the egress SBS may have a free timeslot at time j, but i ~= j). Such
cases require a more complex algorithm which is capable of disconnecting and reconnecting other
connections to make space for the new i to j connection. (Disconnection and reconnection of
other connections is done hitlessly by NSE/SBS fabrics.) This more sophisticated algorithm is
described in the remainder of this section.
A general solution to the connection problem is a schedule where each connection is assigned to
one of the 9720 timeslots in each time stage such that no two connections conflict. This solution
then maps to physical switch settings for the SBS and NSE-8G devices. The following definitions
allow us to represent the problem as an abstract graph problem:
1. Draw a graph where each input and output port is represented as a node.
2. Partition the graph so that all of the input ports are in one partition and all the output ports
3. Draw an edge from an input node to an output node if there is a connection from the
This results in a bipartite graph where each node has a maximum degree of 9720 (the total
number of possible connections from/to a port). A subset of this problem (6 nodes, 2 timeslots) is
illustrated in Figure 29. We want to assign the edges (connections) to timeslots such that no
coincident edges are assigned to the same timeslot. Notice that a solution to the problem consists
of a permutation (or partial permutation) mapping of input nodes onto output nodes for each of
the timeslots. These permutation mappings correspond to one set of switch settings for the NSE-
8G devices.
port which leads to the egress SBS,
are in the other.
corresponding input port to the corresponding output port.
NSE-8G™ Standard Product Data Sheet
Preliminary
159