High performance path allocation system and method with fairness insurance mechanism for a fiber optic switch

• US 5,528,584 A
• Filed: 10/27/1994
• Issued: 06/18/1996
• Est. Priority Date: 10/27/1994
• Status: Expired due to Term

• Current Assignee: Brocade Communications Systems, Inc. (Broadcom, Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Book, David, Stoevhase, Bent, Purohit, Robin, Sullivan, Gregory T., Grant, Robert H.
• Primary Examiner(s): MARCELO, MELVIN C
• Application Number:
  US08/330,273
• Time in Patent Office: 600 Days
• Field of Search: 370/54, 370/58.1, 370/58.2, 370/58.3, 370/60, 370/60.1, 370/61, 370/94.1, 370/94.2, 359/117
• US Class Current: 370/254
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/357 Fibre channel switches

Abstract

A fiber optic switch interconnects fiber optic channels so that a fiber optic network can be implemented. Channel modules provide ports (p1-pi) for connection of the fiber optic channels. Each channel module has a receive memory for temporarily storing incoming data frames from the fiber optic channels associated therewith. A switch module having a data distribution network interconnects each of the channel modules and permits ultimate connection of a source channel to a destination channel. A path allocation system, which controls the switch module, allocates the data paths between the channels. The path allocation system has a scheduler which maintains a destination queue (Q_p1 -Q_pi) for each of the channels, a sentry which determines when a new data frame is ready to be routed, and an arbitrator which arbitrates port availability and which grants transfer requests proposed by the scheduler. Significantly, the arbitrator is equipped with fairness insurance mechanisms for insuring that transfer requests are always timely and efficiently serviced.

Claims

1. A path allocation system for high performance data transfer through a fiber optic switch which selectively interconnects fiber optic channels, comprising:

a plurality of ports for connection to said channels;

a memory means associated with said ports, said memory means for storing an incoming new data frame from a source port;

a distribution network configured to interconnect said ports;

a sentry in communication with said memory means, said sentry configured to determine when said new data frame has been received by said memory means;

a scheduler which maintains a destination queue corresponding with each of said ports, said scheduler configured to receive path data pertaining to said new data frame from said sentry after said sentry determines receipt of said new data frame, said path data including a source port indicator which identifies a source port and which identifies a memory address identifying a location of said frame in said memory means, and a destination port indicator which identifies a destination port, and said scheduler configured to place said path data within a destination queue corresponding with said destination port and to retrieve said path data from said destination queue;

an arbitrator configured to control said distribution network and in communication with said scheduler and said ports, said arbitrator configured to determine when said ports are busy servicing other frame transfer requests and when said ports are available for accommodating frame transfer requests, and said arbitrator configured to deny and grant said transfer requests based upon availability; and

a source fairness insurance means associated with said source port, said source fairness insurance means for defining an order for future access to said source port as a source for data, said order including at least one destination port corresponding to a denied transfer request.

2. The system of claim 1, wherein said order is specified by said source fairness insurance means to include said destination port pertaining to said transfer request when said source port is busy and when no other transfer requests directed to said source port preceded said transfer request after said busy condition.

3. The system of claim 1, wherein said source fairness insurance means is a next-in-line source indicator which identifies only a single source port to define said order.

4. The system of claim 1, wherein said arbitrator further comprises a class determination means for determining whether said transfer request is directed to establishing a packet transfer and a reserved path transfer and wherein when said reserved path transfer is established, said arbitrator determines the availability of said destination port to both receive and transmit data and the availability of said source port to transmit data.

5. The system of claim 1, wherein said new data frame establishes a reserved data path in said distribution network for a circuit switching data transfer.

6. The system of claim 1, further comprising a destination fairness insurance means associated with said destination port, said destination fairness insurance means for defining another order for future access to said destination port as a destination for data, said another order including at least one source port corresponding to another denied transfer request directed to said destination port.

7. The system of claim 1, further comprising a destination fairness insurance means associated with said source port, said destination fairness insurance means for storing another order for future access to said source port as a destination for data, said another order including at least one source port corresponding to another denied transfer request directed to said source port.

8. The system of claim 1, further comprising another source fairness insurance means associated with said destination port, said another source fairness insurance means for defining another order for future access to said destination port as a source for data, said another order including at least one destination port corresponding to a denied transfer request.

9. The system of claim 3, wherein said next-in-line source indicator is configured so that after being assigned said single source port, said next-in-line source indicator does not identify subsequent source ports corresponding with subsequent frame transfer requests directed to said source port.

10. The system of claim 3, wherein said scheduler is configured to service said destination queues in a predetermined queue service order.

11. The system of claim 6, wherein said destination fairness insurance means is a next-in-line destination indicator which stores only a single source port indicator to define said another order.

12. The system of claim 7, wherein said destination fairness insurance means is a next-in-line destination indicator which stores only a single source port indicator to define said another order.

13. The system of claim 8, wherein said another source fairness insurance means is a next-in-line source indicator which stores only a single destination port indicator to define said another order.

14. The system of claim 10, wherein said predetermined queue service order is sequential.

15. A path allocation system for high performance data transfer through a fiber optic switch which selectively interconnects fiber optic channels, comprising:

a plurality of ports for connection to said channels;

a memory means associated with said ports, said memory means for storing an incoming new data frame from a source port;

a distribution network configured to interconnect said ports;

a sentry in communication with said memory means, said sentry configured to determine when said new data frame has been received by said memory means;

a scheduler which maintains a destination queue corresponding with each of said ports, said scheduler configured to receive path data pertaining to said new data frame from said sentry after said sentry determines receipt of said new data frame, said path data including a source port indicator which identifies a source port and which identifies a memory address identifying a location of said frame in said memory means, and a destination port indicator which identifies a destination port, and said scheduler configured to place said path data within a destination queue corresponding with said destination port and to retrieve said path data from said destination queue;

an arbitrator configured to control said distribution network and in communication with said scheduler and said ports, said arbitrator configured to determine when said ports are busy servicing other frame transfer requests and when said ports are available for accommodating frame transfer requests, and said arbitrator configured to deny and grant said transfer requests based upon availability; and

a destination fairness insurance means associated with said destination port, said destination fairness insurance means for storing an order for future access to said destination port as a destination for data, said order including at least one source port indicator corresponding to a denied transfer request.

16. The system of claim 15, wherein said destination fairness insurance means is a next-in-line source indicator which identifies only a single source port to define said order and, after being assigned said single source port, does not identify subsequent source ports corresponding with subsequent frame transfer requests directed to said source port, and wherein said scheduler is configured to service said destination queues in a predetermined queue service order.

17. A method for insuring efficient and reliable transfer of data through a fiber optic switch for selectively interconnecting fiber optic channels which are connected to the switch via respective ports, comprising the steps of:

receiving data at said switch from a source port, said data to be switched to a destination port;

determining when said destination port is available to receive said data and when said destination port is busy receiving other data;

when said source and destination ports are available, transferring said data from said source port to said destination port;

when either of said source and destination ports is busy, denying transfer of said data from said source port to said destination port;

defining an order for future access to said source port as a source for data, said order including a designation of at least one destination port corresponding to at least one denied transfer request;

defining another order for future access to said source port as a destination for data, said another order including a designation of at least one destination port corresponding to at least one other denied transfer request; and

after said source port terminates said busy condition, permitting a denied transfer request by acquiring a destination port designation based upon said order.

18. The method of claim 17, wherein said order includes only a single destination port.

19. The method of claim 17, further comprising the step of maintaining a corresponding destination queue for each of said ports directed to queuing transfers through said switch from source ports to destination ports.

20. The method of claim 17, further comprising the steps of:

determining whether said transfer request is directed to establishing a packet transfer;

determining whether said transfer request is directed to establishing a reserved path transfer; and

when said transfer request is directed to establishing said reserved path transfer, further determining the availability of said destination port to transmit data.

21. The method of claim 17, further comprising the step of defining another order for future access to said destination port as a source for data, said another order including a designation of at least one destination port corresponding to at least one other denied transfer request.

22. The method of claim 18, wherein said single destination port corresponds to a next transfer request immediately following a granted request which resulted in said busy condition.

23. The method of claim 19, wherein said destination queues are serviced in a predetermined queue service order.

24. The method of claim 23, wherein said predetermined queue service order is sequential.

25. A method for insuring efficient and reliable transfer of data through a fiber optic switch for selectively interconnecting fiber optic channels which are connected to the switch via respective ports, comprising the steps of:

receiving data at said switch from a source port, said data to be switched to a destination port;

determining when said destination port is available to receive said data and when said destination port is busy receiving other data;

determining when said source port is available to transmit said data and when said source port is busy transmitting other data;

when said source and destination ports are available, transferring said data from said source port to said destination port;

when either of said source and destination ports is busy, denying transfer of said data from said source port to said destination port;

defining an order for future access to said destination port as a destination for data, said order including a designation of at least one source port corresponding to at least one denied transfer request; and

permitting a denied transfer request by acquiring a stored source port designation based upon said order.

26. A method for insuring efficient and reliable transfer of data through a fiber optic switch for selectively interconnecting fiber optic channels which are connected to the switch via respective ports, comprising the steps of:

receiving data at said switch from a source port, said data to be switched to a destination port;

determining when said destination port is available to receive said data and when said destination port is busy receiving other data;

when said source and destination ports are available, transferring said data from said source port to said destination port;

when either of said source and destination ports is busy, denying transfer of said data from said source port to said destination port;

defining an order for future access to said source port as a source for data, said order including a designation of at least one destination port corresponding to at least one denied transfer request; and

after said source port terminates said busy condition, permitting a denied transfer request by acquiring a destination port designation based upon said order; and

defining another order for future access to said destination port as a destination for data, said another order including a designation of at least one source port corresponding to at least one other denied transfer request.