IP Library › Granted Patent US 12,216,926
Granted Patent B2
US 12,216,926 · App. 18/224,409 · Granted Feb 4, 2025

Intelligent path selection and load balancing

Inventors: Zhengyu Yang (San Diego, CA); Nithya Ramakrishnan (San Diego, CA); Allen Russell Andrews (El Cajon, CA); Sudheendra Grama Sampath (San Diego, CA); T. David Evans (San Diego, CA); Clay Mayers (San Diego, CA)
Assignee: Samsung Electronics Co., Ltd.
G06F3/0635G06F3/0604G06F3/0611G06F3/0659G06F3/0673G06F13/1668G06F13/4027
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,216,926
App. No.
18/224,409
Granted
Feb 4, 2025
Kind
B2
Abstract

A method for dispatching input-output in a system. The system may include a centralized processing circuit, a plurality of persistent storage targets, a first input-output processor, and a second input-output processor. The method may include determining whether the first input-output processor is connected to a first target of the plurality of persistent storage targets; determining whether the second input-output processor is connected to the first target; and in response to determining that both the first input-output processor is connected to the first target, and the second input-output processor is connected to the first target, dispatching a first plurality of input-output requests, each to either the first input-output processor or the second input-output processor, the dispatching being in proportion to a service rate of the first input-output processor to the first target and a service rate of the second input-output processor to the first target, respectively.

Claims (62)

1. A method comprising:

determining a first service rate of a first processor to a first persistent storage device;

determining a second service rate of the first processor to the first persistent storage device based on a service rate of a second processor to the first persistent storage device;

comparing the first service rate with the second service rate; and

transmitting a request to at least one of the first processor or the second processor based on the comparing.

2. The method of claim 1 , wherein the second service rate is calculated based on a parameter associated with an operation of the second processor to access the first persistent storage device.

3. The method of claim 1 , wherein the second service rate includes a portion of the first service rate that is used by the second processor to access the first persistent storage device.

4. The method of claim 3 , wherein the request is transmitted to the at least one of the first processor or the second processor according to the portion.

5. The method of claim 1 , wherein the service rate of the second processor is calculated based on at least a third service rate of the second processor, and a fourth service rate for routing the request from the second processor to the first persistent storage device through a bridge.

6. The method of claim 1 , wherein:

the request comprises a first request and a second request;

the first service rate is determined for a configuration in which both the first and second requests are transmitted to the first processor;

the second service rate is determined for a configuration in which one of the first and second requests is transmitted to the first processor, and the other one of the first and second requests is transmitted to the second processor; and

the first and second requests are transmitted to the first processor in response to determining that the first service rate is greater than the second service rate.

7. The method of claim 1 , wherein:

the request comprises a first request and a second request;

the first service rate is determined for a configuration in which both the first and second requests are transmitted to the first processor;

the second service rate is determined for a configuration in which one of the first and second requests is transmitted to the first processor, and the other one of the first and second requests is transmitted to the second processor; and

the one of the first and second requests is transmitted to the first processor and the other one of the first and second requests is transmitted to the second processor in response to determining that the first service rate is less than the second service rate.

8. A system comprising:

a first persistent storage device;

a first processor connected to the first persistent storage device;

a second processor connected to the first persistent storage device through a bridge; and

a processing circuit configured to:

determine a first service rate of the first processor to the first persistent storage device;

determine a second service rate of the first processor to the first persistent storage device based on a service rate of the second processor to the first persistent storage device;

compare the first service rate with the second service rate; and

transmit a request to at least one of the first processor or the second processor based on the comparing.

9. The system of claim 8 , wherein the second service rate is calculated based on a parameter associated with an operation of the second processor to access the first persistent storage device.

10. The system of claim 8 , wherein the second service rate includes a portion of the first service rate that is used by the second processor to access the first persistent storage device.

11. The system of claim 10 , wherein the request is transmitted to the at least one of the first processor or the second processor according to the portion.

12. The system of claim 8 , wherein the service rate of the second processor is calculated based on at least a third service rate of the second processor, and a fourth service rate for routing the request from the second processor to the first persistent storage device through the bridge.

13. The system of claim 8 , wherein:

the request comprises a first request and a second request;

the first service rate is determined for a configuration in which both the first and second requests are transmitted to the first processor;

the second service rate is determined for a configuration in which one of the first and second requests is transmitted to the first processor, and the other one of the first and second requests is transmitted to the second processor; and

the first and second requests are transmitted to the first processor in response to determining that the first service rate is greater than the second service rate.

14. The system of claim 8 , wherein:

the request comprises a first request and a second request;

the first service rate is determined for a configuration in which both the first and second requests are transmitted to the first processor;

the second service rate is determined for a configuration in which one of the first and second requests is transmitted to the first processor, and the other one of the first and second requests is transmitted to the second processor; and

the one of the first and second requests is transmitted to the first processor and the other one of the first and second requests is transmitted to the second processor in response to determining that the first service rate is less than the second service rate.

15. A system comprising:

a processor; and

memory comprising instructions that, when executed by the processor, cause the processor to:

determine a first service rate of a first processor to a first persistent storage device;

determine a second service rate of the first processor to the first persistent storage device based on a service rate of a second processor to the first persistent storage device;

compare the first service rate with the second service rate; and

transmit a request to at least one of the first processor or the second processor based on the comparing.

16. The system of claim 15 , wherein the second service rate is calculated based on a parameter associated with an operation of the second processor to access the first persistent storage device.

17. The system of claim 15 , wherein the second service rate includes a portion of the first service rate that is used by the second processor to access the first persistent storage device.

18. The system of claim 17 , wherein the request is transmitted to the at least one of the first processor or the second processor according to the portion.

19. The system of claim 15 , wherein:

the request comprises a first request and a second request;

the first service rate is determined for a configuration in which both the first and second requests are transmitted to the first processor;

the second service rate is determined for a configuration in which one of the first and second requests is transmitted to the first processor, and the other one of the first and second requests is transmitted to the second processor; and

the first and second requests are transmitted to the first processor in response to determining that the first service rate is greater than the second service rate.

20. The system of claim 15 , wherein:

the request comprises a first request and a second request;

the first service rate is determined for a configuration in which both the first and second requests are transmitted to the first processor;

the second service rate is determined for a configuration in which one of the first and second requests is transmitted to the first processor, and the other one of the first and second requests is transmitted to the second processor; and

the one of the first and second requests is transmitted to the first processor and the other one of the first and second requests is transmitted to the second processor in response to determining that the first service rate is less than the second service rate.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Aug 24, 2023
From: YANG, ZHENGYU; RAMAKRISHNAN, NITHYA; ANDREWS, ALLEN RUSSELL; SAMPATH, SUDHEENDRA GRAMA; EVANS, T. DAVID; MAYERS, CLAY
To: SAMSUNG ELECTRONICS CO., LTD.
Reel/Frame 064690/0357 →
Continuity (4)
Continuation 17461809 · Aug 30, 2021
Continuation 16459166 · Jul 1, 2019
Provisional Application 62832616 · Apr 11, 2019
Related Publication 20230359377A1 · Nov 9, 2023
References Cited (103)
US 5592672A · Grewal et al. · 1997 [cited by applicant]
US 6438138B1 · Kamiya · 2002 [cited by applicant]
US 6683875B1 · Byham et al. · 2004 [cited by applicant]
US 6986139B1 · Kubo · 2006 [cited by applicant]
US 7159216B2 · McDonald · 2007 [cited by applicant]
US 7289498B2 · Yu et al. · 2007 [cited by applicant]
US 7448044B1 · Rust et al. · 2008 [cited by applicant]
US 8031729B2 · Elzur · 2011 [cited by applicant]
US 8589941B2 · Cardona et al. · 2013 [cited by applicant]
US 8638664B2 · Shankar et al. · 2014 [cited by applicant]
US 8640128B2 · Cardona et al. · 2014 [cited by applicant]
US 9021138B2 · Dabagh et al. · 2015 [cited by applicant]
US 9152448B2 · Wang et al. · 2015 [cited by applicant]
US 9262095B2 · Sugimoto · 2016 [cited by examiner]
US 9459904B2 · Mehta et al. · 2016 [cited by applicant]
US 9571426B2 · Agarwal et al. · 2017 [cited by applicant]
US 9785356B2 · Huang · 2017 [cited by applicant]
US 9800523B2 · Guan et al. · 2017 [cited by applicant]
US 9804780B2 · Oe et al. · 2017 [cited by applicant]
US 9979678B2 · Huang et al. · 2018 [cited by applicant]
US 10069903B2 · Sorenson, III et al. · 2018 [cited by applicant]
US 10089144B1 · Nagpal et al. · 2018 [cited by applicant]
US 10127177B2 · Tamir et al. · 2018 [cited by applicant]
US 10142231B2 · Vasudevan · 2018 [cited by applicant]
US 10637817B2 · Kuo et al. · 2020 [cited by applicant]
US 10671302B1 · Aggarwal et al. · 2020 [cited by applicant]
US 10757180B2 · Hodges et al. · 2020 [cited by applicant]
US 10860218B2 · Graham et al. · 2020 [cited by applicant]
US 20020124104A1 · Rappaport et al. · 2002 [cited by applicant]
US 20030076849A1 · Morgan et al. · 2003 [cited by applicant]
US 20050138170A1 · Cherkasova et al. · 2005 [cited by applicant]
US 20060064497A1 · Bejerano et al. · 2006 [cited by applicant]
US 20060161924A1 · Di Gregorio · 2006 [cited by applicant]
US 20080216087A1 · Dillenberger et al. · 2008 [cited by applicant]
US 20080298240A1 · Lee et al. · 2008 [cited by applicant]
US 20090161684A1 · Voruganti et al. · 2009 [cited by applicant]
US 20100157964A1 · Yoon · 2010 [cited by applicant]
US 20110044338A1 · Stahl et al. · 2011 [cited by applicant]
US 20110142064A1 · Dubal et al. · 2011 [cited by applicant]
US 20110153935A1 · Li · 2011 [cited by applicant]
US 20110191011A1 · McBride et al. · 2011 [cited by applicant]
US 20120072627A1 · Droux et al. · 2012 [cited by applicant]
US 20120079495A1 · Conti et al. · 2012 [cited by applicant]
US 20140274011A1 · Jain et al. · 2014 [cited by applicant]
US 20140325524A1 · Zangaro et al. · 2014 [cited by applicant]
US 20140337540A1 · Johnson et al. · 2014 [cited by applicant]
US 20150233983A1 · Siebel et al. · 2015 [cited by applicant]
US 20160269240A1 · Balakrishnan et al. · 2016 [cited by applicant]
US 20160301610A1 · Amit et al. · 2016 [cited by applicant]
US 20170031610A1 · Regester · 2017 [cited by examiner]
US 20170083252A1 · Singh et al. · 2017 [cited by applicant]
US 20170168715A1 · Eshwarappa et al. · 2017 [cited by applicant]
US 20170315840A1 · Yu et al. · 2017 [cited by applicant]
US 20180131718A1 · Chien · 2018 [cited by applicant]
US 20180191867A1 · Siebel et al. · 2018 [cited by applicant]
US 20180285021A1 · Akaike et al. · 2018 [cited by applicant]
US 20180349026A1 · Richter et al. · 2018 [cited by applicant]
US 20180349300A1 · Bubb et al. · 2018 [cited by applicant]
US 20180359318A1 · Rogers et al. · 2018 [cited by applicant]
US 20190042326A1 · Chilikin et al. · 2019 [cited by applicant]
US 20190042331A1 · McDonnell et al. · 2019 [cited by applicant]
US 20190042388A1 · Wang et al. · 2019 [cited by applicant]
US 20190095491A1 · Bhattacharjee et al. · 2019 [cited by applicant]
US 20190163764A1 · Ioannou et al. · 2019 [cited by applicant]
US 20190182316A1 · Hodges et al. · 2019 [cited by applicant]
US 20190196969A1 · Yang et al. · 2019 [cited by applicant]
US 20190354406A1 · Ganguli et al. · 2019 [cited by applicant]
US 20200162385A1 · Thiagarajan et al. · 2020 [cited by applicant]
US 20200195550A1 · Cao · 2020 [cited by examiner]
CN 103955422A · 2014 [cited by applicant]
CN 106254272A · 2016 [cited by applicant]
CN 107741878A · 2018 [cited by applicant]
CN 109074269A · 2018 [cited by applicant]
JP 2005508545A · 2005 [cited by applicant]
JP 2013250905A · 2013 [cited by applicant]
JP 6289631 · 2018 [cited by applicant]
KR 100748187B1 · 2007 [cited by applicant]
KR 1020140096511A · 2014 [cited by applicant]
WO WO2014050125A1 · 2014 [cited by applicant]
Korean Office Action for KR Appl 10-2019-0159870 dated Oct. 16, 2023, 55 pages. [cited by applicant]
SNIA.ORG, https://composter.com.ua/documents/SNIASSSIPCle101WhitePaper1.12013.pdf, “PCle SSD 101”, Jan. 1, 2013, pp. 1-32. [cited by applicant]
Mohammad Hedayati, et al., “Multi-Queue Fair Queuing”, Department of Computer Science, University of Rochester Google Inc Technical Report #1005, Oct. 1, 2018, pp. 1-13, https://pdfs.semanticscholar.org/abd0/a302926f662… [cited by applicant]
Ann Klimovic, et al., “ReFlex: Remote Flash ˜ Local Flash”, ASPLOS '17, Apr. 8-12, 2017, Xi'an, China Jul. 12, 2017, pp. 1-15, http://web.stanford.edu/group/mast/cgibin/drupal/system/files/reflex_asplos17.pdf. [cited by applicant]
John Kim, et al. “How Ethernet RDMA Protocols iWARP and ROCE Support NVMe over Fabrics”, https://www.snia.org/forums/nsf/knowledge/webcasts, Jan. 26, 2016, pp. 1-34. [cited by applicant]
Wenyu Gao, Jianxin Wang, Jianer Chen and Songqiao Chen, “PFED: a prediction-based fair active queue management algorithm,” 2005 International Conference on Parallel Processing (ICPP'05), Oslo, Norway, 2005, pp. 485-491,… [cited by applicant]
Allen B. Downey, “Using Queue Time Predictions for Processor Allocation”, EECS Department University of California, Berkeley, Technical Report No. UCB/CSD-97-929 (Year: 1997). [cited by applicant]
Guan, L. , Awan, 1.U. , Phillips, L. , Grigg, A. , Dargie, W. (2009). “Performance analysis of a threshold-based discrete-time queue using maximum entropy”. Simulation Modelling Practice and Theory. 17, 558-568 (Year: 2… [cited by applicant]
Hu, Q., Sun, Y. & Han, J. An efficient scheduling algorithm for input-queued switches. J. of Electron.(China) 24, 251-256 (2007). https://doi.org/10.1007/s11767-006-0111-8 (Year: 2007). [cited by applicant]
Yuan Sun, Qingsheng Hu, Jiangtao Han and Zhigong Wang, “A self-adaptive threshold based scheduling algorithm for input-queued switches,” 2006 Workshop on High Performance Switching and Routing, Poznan, 2006, pp. 4 pp.-,… [cited by applicant]
A. K. Choudhury and E. L. Hahne, “Dynamic queue length thresholds for shared-memory packet switches,” in IEEE/ACM Transactions on Networking, vol. 6, No. 2, pp. 130-140, Apr. 1998, doi: 10.1109/90.664262. (Year: 1998). [cited by applicant]
H. Li and T. Yang, “Queues with a variable number of servers,” European Journal of Operational Research, vol. 124, No. 3, pp. 615-628, 2000. (Year: 2000). [cited by applicant]
H. Xiao and G. Zhang, “The queuing theory application in bank service optimization,” 2010 International Conference on Logistics Systems and Intelligent Management (ICLSIM), Harbin, 2010, pp. 1097-1100, doi: 10.1109/ICLS… [cited by applicant]
U.S. Office Action dated Jul. 28, 2020, issued in U.S. Appl. No. 16/536,928, 26 pages. [cited by applicant]
Office Action issued in U.S. Application No. 16/706, 161 by the USPTO, dated Sep. 3, 2020, 9 pages. [cited by applicant]
U.S. Final Office Action dated Nov. 13, 2020, issued in U.S. Appl. No. 16/536,928 (27 pages). [cited by applicant]
U.S. Advisory Action dated Feb. 8, 2021, issued in U.S. Appl. No. 16/536,928 (6 pages). [cited by applicant]
J.S. Chase, D.C. Anderson, P.N. Thakar, A.M. Vahdat, R.P. Doyle, Managing energy and server resources in hosting centers, in: Proceedings of the 18th ACM Symposium on Operating Systems Principles, ACM, New York, NY, USA… [cited by applicant]
M. Mazzucco, D. Dyachuk and M. Dikaiakos, “Profit-Aware Server Allocation for Green Internet Services,” 2010 IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, M… [cited by applicant]
U.S. Final Office Action dated Feb. 18, 2021, issued in U.S. Appl. No. 16/706,161 (10 pages). [cited by applicant]
U.S. Office Action dated Mar. 2, 2021, issued in U.S. Appl. No. 16/536,928, (30 pages). [cited by applicant]
Chinese Notice Of Allowance dated Jun. 13, 2022, issued in corresponding Chinese Patent Application No. 202010095602.5 (5 pages). [cited by applicant]
Korean Notice of Allowance dated Jan. 29, 2024, issued in corresponding Korean Patent Application No. 10-2019-0159870 (8 pages). [cited by applicant]
Korean Office Action dated Aug. 22, 2024, issued in corresponding Korean Patent Application No. 10-2024-0057170 (7 pages). [cited by applicant]