Method and apparatus for distributed topology function in serial attached small computer system interface (SAS)
View Patent ↗The present invention is directed at a method and apparatus for determining a distributed Serial Attached Small computer system interface (SAS) topology in a storage network system. Once a SAS storage network element, such as a SAS Expander, receives notification that a downstream SAS topology has changed, the SAS Expander queries all downstream SAS Expanders to update its route table.
1. In a Serial Attached Small Computer System Interface (SAS) domain including a set of SAS storage network elements, a method of configuring an Expander route table of a SAS Expander in a distributed manner comprising:
receiving notification of a trigger event by an initiator at SAS Expander closest to the initiator;
determining a set of paths originating from said SAS Expander based on an origin of topology change;
determining a list of Expanders to query based on said set of paths;
said list of Expanders to query including a first encountered self-configuring or last-in-path Expander and intermediate non self-configuring SAS Expanders for each path;
wherein determining comprises calling a self-configuring process;
determining a set of route table information from a set of SAS Expanders in said list of Expanders to query;
updating route tables of the intermediate non self-configuring (NSCFG) SAS Expanders in a distributed manner;
wherein said updating comprises calling a non-self-configuring process; and
configuring said Expander route table based on said set of route table information;
wherein the determining, updating and configuring are performed in an iterative sequence originating from the initiator.
2. The method of claim 1 wherein each of said paths begins at said SAS Expander and terminates at said origin of topology change.
3. The method of claim 1 wherein said path is empty when said origin of topology change is upstream from said SAS Expander.
4. The method of claim 1 wherein said list of Expanders to query is an ordered list.
5. The method of claim 1 wherein said set of Expanders are downstream from said SAS Expander.
6. The method of claim 1 further comprising, occurring before said step of determining a set of paths: receiving a signal indicating a topology change to said SAS domain.
7. The method of claim 6 wherein said step of receiving comprises:
receiving notification that a SAS storage network element has completed a link initialization sequence with said SAS Expander, or a link has dropped out of an operational state.
8. The method of claim 6 wherein said step of receiving comprises:
receiving a broadcast change primitive, a broadcast frame or a SMP Zoned Broadcast message indicating a change to one of said SAS storage network elements.
9. The method of claim 8 wherein said one of said SAS storage network elements is downstream from said SAS Expander.
10. The method of claim 6 further comprising, occurring after said step of receiving said signal:
determining said origin of said topology change by determining a trigger PHY.
11. The method of claim 1 further comprising: generating a signal for an upstream SAS storage network element indicating a change to its downstream topology.
12. The method of claim 1 wherein said step of determining comprises: querying each self-configuring SAS Expander in said list of Expanders to query to retrieve its route table; querying each SAS Expander in said list of Expanders to query to retrieve its direct routing table; and querying each SAS Expander in said list of Expanders to retrieve local PHY status information and identification of directly attached devices.
13. The method of claim 1 further comprising: providing said configured Expander route table to an upstream SAS Expander.
14. The method of claim 13 wherein said step of providing is performed after said Expander route table is completely configured.
15. The method of claim 1 wherein said step of updating is performed in a breadth-first or depth-first traversal order.
16. The method of claim 1 wherein said self-configuring process comprises: retrieving a list of PHYs associated with an Expander being queried; retrieving all routing information from the Expander being queried a route table of each of said PHYs in said list of PHYs; and storing said routing information as said set of route table information in the SAS expander.
17. The method of claim 1 wherein said self-configuring process comprises: selecting one PHY per port of said Expander being queried; determining all routing information corresponding to a route table of each of said one PHY per port; and storing said routing information as said set of route table information.
18. The method of claim 1 wherein said non self-configuring process comprises: determining a list of SAS storage network elements directly attached to said Expander being queried; and configuring routes of a parent SAS Expander to said Expander being queried based on said SAS storage network elements directly attached to said Expander being queried.
19. The method of claim 18 wherein said step of determining a list of SAS storage network elements comprises:
retrieving a direct routing table from said Expander being queried; and
retrieving a route table from said Expander being queried when said Expander being queried is a self-configuring Expander.
20. The method of claim 1 further comprising, occurring before said step of determining a set of route table information: determining if a SAS Expander being queried is a self-configuring or non-self-configuring SAS Expander.
21. In a Serial Attached Small Computer System Interface (SAS) domain including a set of SAS Expanders, a method of configuring an Expander route table of a subject SAS Expander in a distributed manner comprising the steps of:
a) receiving an indication of a topology change due to a trigger event by an initiator to said SAS domain downstream from said subject SAS Expander, the subject SAS Expander being closest to the initiator;
b) determining a set of paths originating from said SAS Expander based on an origin of topology change;
c) determining a list of Expanders to query based on said set of paths; said list of Expanders to query including a first encountered self-configuring or last-in-path Expander and intermediate non self-configuring SAS Expanders for each path;
wherein determining comprises calling a self-configuring process;
d) determining a set of route table information from a set of SAS Expanders in a list of Expanders to query;
e) updating route tables of intermediate non self-configuring (NSCFG) SAS Expanders;
wherein said updating comprises calling a non-self-configuring process;
f) configuring a route table of said subject SAS Expander, in the distributed manner, based on information retrieved from a predetermined set of downstream SAS Expanders;
g) transmitting a signal to an upstream SAS Expander, upon completion of said route table configuration, indicating a topology change to said SAS domain downstream from said upstream SAS Expander;
h) activating said upstream SAS Expander as said subject SAS Expander; and
repeating these steps a) to h) for each upstream SAS Expander until a root SAS Expander is encountered.
22. The method of claim 21 further comprising:
providing said configured route table in response to a request from an upstream SAS Expander.
23. The method of claim 21 wherein said step of transmitting further comprises:
propagating said topology change indication to all PHYs in said subject SAS Expander except a PHYs belonging to the trigger port if said indication is received from an upstream SAS Expander; and
propagating said topology change indication to all PHYs in said subject SAS Expander after completing said step of configuring said route table if said indication is received from a downstream SAS Expander.
24. The method of claim 21 wherein said step of receiving comprises:
receiving notification that a SAS Expander has completed a link initialization sequence with said subject SAS Expander, or a link has dropped out of operational state.
25. The method of claim 21 wherein said step of receiving comprises:
receiving a broadcast change primitive, a broadcast frame or a SMP Zoned Broadcast message indicating a change to one of said SAS Expanders.
26. The method of claim 25 further comprising:
ignoring said broadcast change primitive, broadcast frame or Broadcast message if said primitive, frame or message is received from an upstream SAS Expander.
27. A non-transitory computer readable medium containing computer instructions which, when executed, perform, in a Serial Attached Small Computer System Interface (SAS) domain including a set of SAS storage network elements, a method of configuring an Expander route table of a SAS Expander in a distributed manner, comprising:
instructions for receiving notification of a trigger event by an initiator at SAS Expander closest to the initiator;
instructions for determining a set of paths originating from said SAS Expander based on an origin of topology change;
instructions for determining a list of Expanders to query based on said set of paths;
said list of Expanders to query including a first encountered self-configuring or last-in-path Expander and intermediate non self-configuring SAS Expanders for each path;
wherein determining comprises calling a self-configuring process;
instructions for determining a set of route table information from a list of Expanders to query;
instructions for updating route tables of the intermediate non self-configuring (NSCFG) SAS Expanders in the distributed manner;
wherein said updating comprises calling a non-self-configuring process; and
instructions for configuring said Expander route table based on said set of route table information;
wherein the instructions for determining, updating and configuring are performed in an iterative sequence originating from the initiator.
28. Apparatus for determining a distributed Serial Attached Small computer system interface (SAS) topology for a SAS Expander comprising:
at least one PHY, each PHY including a transmitter for requesting route table information from a list of Expanders to query downstream from said SAS Expander; and
a receiver for receiving route table information as a result of said requests and for receiving a topology change request from a trigger event by an initiator; and
a processor for:
determining a set of paths originating from said SAS Expander based on an origin of topology change;
determining a list of Expanders to query based on said set of paths;
said list of Expanders to query including a first encountered self-configuring or last-in-path Expander and intermediate non-self-configuring SAS Expanders for each path;
wherein determining comprises calling a self-configuring process;
determining a set of route table information from a set of SAS Expanders in a list of Expanders to query;
updating route tables of the intermediate non self-configuring (NSCFG) SAS Expanders in the distributed manner;
wherein said updating comprises calling a non-self-configuring process; and
configuring said Expander route table based on said set of route table information £ wherein the determining, updating and configuring are performed in an iterative sequence originating from the initiator.
29. The apparatus of claim 28 wherein said transmitter also includes means to transmit a signal to an upstream SAS Expander indicating a change in downstream topology after said Expander route table has been completely configured.
30. The apparatus of claim 28 wherein each of said receivers is capable of receiving a signal indicating an origin of topology change.
31. The apparatus of claim 30 further comprising a means to determine which of said at least one PHY receives said signal.
32. The apparatus of claim 28 wherein said list of Expanders to query comprises self-configuring Expanders.
33. The apparatus of claim 28 wherein said list of Expanders to query comprises non self configuring Expanders.