Source: http://www.google.com/patents/US20020159446?dq=5,832,511
Timestamp: 2017-09-20 09:35:29
Document Index: 581494018

Matched Legal Cases: ['Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60']

Patent US20020159446 - Method and system for interswitch load balancing in a communications network - Google Patents
An interconnect fabric module (“IFM”) with high-speed switching capabilities. An interconnect fabric module can be dynamically configured to interconnect its communications ports so that data can be transmitted through the interconnected ports. Multiple interconnect fabric modules can be connected...http://www.google.com/patents/US20020159446?utm_source=gb-gplus-sharePatent US20020159446 - Method and system for interswitch load balancing in a communications network
Publication number US20020159446 A1
Application number US 10/039,404
Also published as US6993023, US6996058, US7042877, US7068666, US7068667, US7164656, US20020159389, US20020159437, US20020159451, US20020159452, US20020159453, US20020159456, US20020159458, US20020159468, US20020161887, US20020161923, US20020167902, US20020181395, US20020184529, US20020188754, US20030189927, US20030202535, US20030202536, US20030204618, US20040004966
Publication number 039404, 10039404, US 2002/0159446 A1, US 2002/159446 A1, US 20020159446 A1, US 20020159446A1, US 2002159446 A1, US 2002159446A1, US-A1-20020159446, US-A1-2002159446, US2002/0159446A1, US2002/159446A1, US20020159446 A1, US20020159446A1, US2002159446 A1, US2002159446A1
Patent Citations (71), Referenced by (11), Classifications (31), Legal Events (4)
Method and system for interswitch load balancing in a communications network
US 20020159446 A1
receiving data that designates that the first port is to be the destination port for the received data; and
when the first port is currently unavailable, selecting the second port as the destination port for the received data based on the provided designation that the first port and the second port are equivalent.
5. The method of claim 1 wherein a port can be equivalent to multiple other ports.
6. The method of claim 5 wherein the multiple ports have associated priorities and the second port is selected as the destination port when it has a priority that is higher than another of the multiple ports that are available.
7. The method of claim 1 wherein the received data designates the first port to be the destination port based on a mapping of a virtual address of the received data to the first port.
8. The method of claim I wherein the provided designations is provided by a source external to the switch.
9. The method of claim 1 wherein the provided designation is dynamically updated by a source external to the switch.
10. The method of claim 1 wherein the switch is part of an interconnect fabric.
11. The method of claim 1 wherein the switch is Fibre Channel compatible.
12. The method of claim 1 wherein the switch is InfiniBand compatible.
13. The method of claim 1 wherein the data is a Fibre Channel frame.
a designation that a first port and second port are equivalent;
a component that receives a communication that designates that the first port is to be the destination port for the received communication; and
a component that selects the second port as the destination port for the received communication based on the designation when the first port is currently unavailable.
15. The routing device of claim 14 wherein the designation is a table with an entry for source ports of the routing device.
16. The routing device of claim 15 wherein an entry for the first port designates that the second port is equivalent to the first port.
17. The routing device of claim 15 wherein an entry for the second port designates that the first port is equivalent to the second port.
18. The routing device of claim 14 wherein a port can be equivalent to multiple other ports.
19. The routing device of claim 18 wherein the multiple ports have associated priorities and the second port is selected as the destination port when it has a priority that is higher than another of the multiple ports that are available.
20. The routing device of claim 18 wherein the component that selects the second port selects the second port from one of the multiple other ports that is available.
21. The routing device of claim 14 wherein the received communication designates the first port to be the destination port based on a mapping of a virtual address of the received communication to the first port.
22. The routing device of claim 14 wherein the designation is provided by a source external to the routing device.
23. The routing device of claim 14 wherein the designation is dynamically updated by a source external to the routing device.
24. The routing device of claim 14 wherein the routing device is part of an interconnect fabric.
25. The routing device of claim 14 wherein the routing device is Fibre Channel compatible.
26. The routing device of claim 14 wherein the routing device is InfiniBand compatible.
means for designating that a first port and second port are equivalent;
means for receiving a communication that designates that the first port is to be the destination port for the received communication; and
means for selecting the second port as the destination port for the received communication based on the designation that the first port and the second port are equivalent when the first port is currently unavailable.
28. The routing device of claim 27 wherein the means for designating is a mapping for source ports of the routing device.
29. The routing device of claim 28 wherein a mapping for the first port designates that the second port is equivalent to the first port.
30. The routing device of claim 28 wherein a mapping for the second port designates that the first port is equivalent to the second port.
31. The routing device of claim 27 wherein a port can be equivalent to multiple other ports.
32. The routing device of claim 31 wherein the multiple ports have associated priorities and the second port is selected as the destination port when it has a priority that is higher than another of the multiple ports that are available.
33. The routing device of claim 31 wherein the means for selecting the second port selects the second port from one of the multiple other ports that is available.
34. The routing device of claim 27 wherein the received communication designates the first port to be the destination port based on a mapping of a virtual address of the received communication to the first port.
35. The routing device of claim 27 wherein the means for designating is provided a designation by a source external to the routing device.
36. The routing device of claim 27 wherein means for designating receives a dynamic update from a source external to the routing device.
37. The routing device of claim 27 wherein the routing device is part of an interconnect fabric.
38. The routing device of claim 27 wherein the routing device is Fibre Channel compatible.
39. The routing device of claim 27 wherein the routing device is InfiniBand compatible.
This application claims the benefit of U.S. Provisional Application No. 60/287,069 entitled “METHOD FOR IMPLEMENTING A CLUSTER NETWORK FOR HIGH PERFORMANCE AND HIGH AVAILABILITY USING A FIBRE CHANNEL SWITCH FABRIC,” filed Apr. 27, 2001; U.S. Provisional Application No. 60/287,120 entitled “MULTI-PROTOCOL NETWORK FOR ENTERPRISE DATA CENTERS,” filed Apr. 27, 2001; U.S. Provisional Application No. 60/286,918 entitled “UNIFIED ENTERPRISE NETWORK SWITCH (UNEX) PRODUCT SPECIFICATION,” filed Apr. 27, 2001; U.S. Provisional Application No. 60/286,922 entitled “QUALITY OF SERVICE EXAMPLE,” filed Apr. 27, 2001; U.S. Provisional Application No. 60/287,081 entitled “COMMUNICATIONS MODEL,” filed Apr. 27, 2001; U.S. Provisional Application No. 60/287,075 entitled “UNIFORM ENTERPRISE NETWORK SYSTEM,” filed Apr. 27, 2001; U.S. Provisional Application No. 60/314,088 entitled “INTERCONNECT FABRIC MODULE,” filed Aug. 21, 2001; U.S. Provisional Application No. 60/314,287 entitled “INTEGRATED ANALYSIS OF INCOMING DATA TRANSMISSIONS,” filed Aug. 22, 2001; U.S. Provisional Application No. 60/314,158 entitled “USING VIRTUAL IDENTIFIERS TO ROUTE TRANSMITTED DATA THROUGH A NETWORK,” filed Aug. 21, 2001, and is related to U.S. Patent Application No. ______ entitled “METHOD AND SYSTEM FOR VIRTUAL ADDRESSING IN A COMMUNICATIONS NETWORK,” (Attorney Docket No. 030048019US1); U.S. Patent Application No. ______ entitled “METHOD AND SYSTEM FOR LABEL TABLE CACHING IN A ROUTING DEVICE,” (Attorney Docket No. 030048024US); U.S. Patent Application No. ______ entitled “METHOD AND SYSTEM FOR MULTIFRAME BUFFERING IN A ROUTING DEVICE,” (Attorney Docket No. 030048025US); U.S. Patent Application No. ______ entitled “METHOD AND SYSTEM FOR DOMAIN ADDRESSING IN A COMMUNICATIONS NETWORK,” (Attorney Docket No. 030048026US); U.S. Patent Application No. ______ entitled “METHOD AND SYSTEM FOR INTERSWITCH LOAD BALANCING IN A COMMUNICATIONS NETWORK,” (Attorney Docket No. 030048027US); U.S. Patent Application No. ______ entitled “METHOD AND SYSTEM FOR INTERSWITCH DEADLOCK AVOIDANCE IN A COMMUNICATIONS NETWORK,” (Attorney Docket No. 030048028US); U.S. Patent Application No. ______ entitled “METHOD AND SYSTEM FOR CONNECTION PREEMPTION IN A COMMUNICATIONS NETWORK,” (Attorney Docket No. 030048029US); U.S. Patent Application No. ______ entitled “METHOD AND SYSTEM FOR MULTICASTING IN A ROUTING DEVICE,” (Attorney Docket No. 030048030US); U.S. Patent Application No. ______ entitled “METHOD AND SYSTEM FOR NETWORK CONFIGURATION DISCOVERY IN A NETWORK MANAGER,” (Attorney Docket No. 030048032US); U.S. Patent Application No. ______ entitled “METHOD AND SYSTEM FOR PATH BUILDING IN A COMMUNICATIONS NETWORK,” (Attorney Docket No. 030048033US); U.S. Patent Application No. ______ entitled “METHOD AND SYSTEM FOR RESERVED ADDRESSING IN A COMMUNICATIONS NETWORK,” (Attorney Docket No. 030048035US); U.S. Patent Application No. ______ entitled “METHOD AND SYSTEM FOR RECONFIGURING A PATH IN A COMMUNICATIONS NETWORK,” (Attorney Docket No. 030048036US1); U.S. Patent Application No. ______ entitled “METHOD AND SYSTEM FOR ADMINISTRATIVE PORTS IN A ROUTING DEVICE,” (Attorney Docket No. 030048037US); U.S. Patent Application No. ______ entitled “PARALLEL ANALYSIS OF INCOMING DATA TRANSMISSIONS,” (Attorney Docket No. 030048038US); U.S. Patent Application No. ______ entitled “INTEGRATED ANALYSIS OF INCOMING DATA TRANSMISSIONS,” (Attorney Docket No. 030048039US); U.S. Patent Application No. ______ entitled “USING VIRTUAL IDENTIFIERS TO ROUTE TRANSMITTED DATA THROUGH A NETWORK,” (Attorney Docket No. 030048040US); U.S. Patent Application No. ______ entitled “USING VIRTUAL IDENTIFIERS TO PROCESS RECEIVED DATA ROUTED THROUGH A NETWORK,” (Attorney Docket No. 030048041US); U.S. Patent Application No. ______ entitled “METHOD AND SYSTEM FOR PERFORMING SECURITY VIA VIRTUAL ADDRESSING IN A COMMUNICATIONS NETWORK,” (Attorney Docket No. 030048042US); and U.S. Patent Application No. ______ entitled “METHOD AND SYSTEM FOR PERFORMING SECURITY VIA DE-REGISTRATION IN A COMMUNICATIONS NETWORK” (Attorney Docket No. 030048043US), which are all hereby incorporated by reference in their entirety.
[0007]FIG. 1 is a block diagram illustrating components of the interconnect fabric module (“IFM”) in one embodiment.
[0008]FIG. 2 is a block diagram illustrating components of a switch protocol controller in one embodiment.
[0009]FIG. 3 is a block diagram illustrating the contents of a label table in one embodiment.
[0010]FIG. 4 is a block diagram illustrating the format of a frame in one embodiment.
[0011]FIG. 5 is a diagram illustrating logic of an arbitrator of a switch protocol controller in one embodiment.
[0012]FIG. 6 is a block diagram illustrating the transmit controller in one embodiment.
[0013]FIG. 7 is a block diagram illustrating the interconnection of interconnect fabric modules forming an interconnect fabric that connects various nodes.
[0014]FIG. 8 is a block diagram illustrating the mapping of a destination identifier to a port map.
[0015]FIG. 9 is a block diagram illustrating switch protocol controller caching in one embodiment.
[0016]FIG. 10 is a block diagram illustrating multiframe buffering.
[0017]FIG. 11 is a diagram illustrating the logic of the buffer arbitrator in one embodiment.
[0018]FIG. 12 is a block diagram illustrating an interconnect fabric configuration with multiple direct links between interconnect fabric modules.
[0019]FIG. 13 is a block diagram illustrating the use of equivalent ports.
[0020]FIG. 14 is a diagram illustrating the logic of the equivalent port service in one embodiment.
[0021]FIG. 15 is a block diagram illustrating a component for identifying upper layer protocol ports.
[0022]FIG. 16 is a block diagram illustrating an interswitch deadlock.
[0023]FIG. 17 is a diagram illustrating the logic of deadlock avoidance algorithm in one embodiment.
[0024]FIG. 18 illustrates the preempting of a connection.
[0025]FIG. 19 is a diagram illustrating the logic of processing a preemption signal in one embodiment.
[0026]FIG. 20 is a diagram illustrating the logic of distributed class 3 multicasting in one embodiment.
An interconnect fabric module (“IFM”) with high-speed switching capabilities is provided. In one embodiment, an interconnect fabric module can be dynamically configured to interconnect its communications ports so that data can be transmitted through the interconnected ports. Multiple interconnect fabric modules can be connected to form an interconnect fabric through which nodes (e.g., computer systems) can be interconnected. In one embodiment, data is transmitted through the interconnect fabric as frames such as those defined by the Fibre Channel standard. Fibre Channel is defined in ANSI T11 FC-PH, FC-PH-2, FC-PH-3, FC-PI, and FC-FS industry standard documents which are hereby incorporated by reference. One skilled in the art will appreciate however, that the described techniques can be used with communications standards other than Fibre Channel. In particular, the described techniques can be used with the InfiniBand standard, which is described in the InfiniBand Architecture Specification, Vols. 1-2, Release 1.0, Oct. 24, 2000, which is hereby incorporated by reference. As will be described below in more detail, the interconnect fabric module allows the creation of an interconnect fabric that is especially well suited for interconnecting devices utilizing multiple information types such as might be required by the devices of an enterprise data network (“EDN”).
[0042]FIG. 1 is a block diagram illustrating components of the interconnect fabric module (“IFM”) in one embodiment. The interconnect fabric module 100 includes 32 switch protocol controllers (“SPC”) 101, a crosspoint switch 102, a switch control unit (“SCU”) 103, a field programmable gate array (“FPGA”) monitor 104, an arbitration bus 105, and an IFM identifier 106. The interconnect fabric module has 32 bi-directional communication ports. A switch protocol controller controls each communications port. Each switch protocol controller is responsible for decoding the header information of a frame, arbitrating access to destination ports and configuring the crosspoint switch, and transmitting the received frame through the crosspoint connections to one or more communication ports. The switch control unit receives requests for crosspoint connections from the switch protocol controllers, configures the crosspoint switch accordingly, and directs the switch protocol controllers to transmit their frames through the crosspoint connections. The crosspoint switch provides full crossbar functionality in that each port of the interconnect fabric module can be simultaneously connected to any number of ports. In one embodiment, the crosspoint switch has 34 inputs and 34 outputs, numbered 0-33. The field programmable gate array monitor connects to an interconnect fabric module manager (not shown), which is a single board computer that may provide an interface for configuring the interconnect fabric module and may provide an interface to upper layer protocol services such as a name server or alias server.
[0043]FIG. 2 is a block diagram illustrating components of a switch protocol controller in one embodiment. The switch protocol controller 200 includes a receive controller 201, a decoder 202, a header processor 203, a frame buffer 204, a transmit controller 205, and an arbitrator 206. The receive controller is connected to the input (i.e., receive side) of a port and may perform a serial-to-parallel conversion of the received frame. The decoder provides the header information of the received frame to the header processor and stores the frame in the frame buffer. The header processor includes a processor 207, a label table 208, and an equivalent port table 209. The label table contains port maps that indicate to which ports a frame should be routed (“switch destination port”) based on the port through which the frame is received (i.e., “switch source port”) and the destination identifier of the frame. The processor retrieves the port map from the label table for the received frame and provides the port map to the arbitrator. The equivalent port table indicates groups of ports that are equivalent in the sense that a frame can be sent through any port of an equivalent group to reach the identified destination. If one port in an equivalent port group is currently in use, then a switch protocol controller can equivalently route the frame to any available port in the equivalent port group. The arbitrators of the switch protocol controllers coordinate access to the switch control unit so that a switch protocol controller can request the switch control unit to configure the crosspoint switch in accordance with the port map. As described below in detail, the arbitrators and the switch control unit are connected to an arbitration bus. The arbitrator is also connected to the output (i.e., transmit side) of the port for transmitting control frames. The transmit controller transmits frames stored in the frame buffer to the crosspoint switch when the switch control unit indicates that the crosspoint switch has been configured appropriately.
[0044]FIG. 3 is a block diagram illustrating the contents of a label table in one embodiment. The entries of the label table are port maps that are indexed by a virtual address. In one embodiment, the destination identifier includes a domain address and a virtual address, which are described below in detail. A virtual address is virtual in the sense that it is not a physical address of a node (or interconnect fabric module). Rather, a virtual address is mapped to a series of output ports of one or more interconnect fabric modules as specified by their label tables that define a route from the source device to the destination device. A port map has one bit for each of the 32 ports of the interconnect fabric module. A bit value of 1 indicates that frames directed to the indexing virtual address should be routed to the corresponding port. For example, the first entry in the label table contains a bit value of 1 in the column corresponding to port 2 and contains a bit value of 0 in all the other columns corresponding to ports 0, 1, and 3-31. When a frame is directed to the virtual address of 0, the corresponding entry in the label table indicates that the frame should be routed to only port 2. The second entry in the label table indicates that frames directed to the virtual address of 1 are to be routed to ports 2-31, but not to ports 0 and 1. In one embodiment, the label table of each switch protocol controller contains 8K entries. One skilled in the art will appreciate that the size of the label table can be adjusted to meet overall performance goals of the interconnect fabric module. Because each switch protocol controller has its own label table, a frame received via port 2 with a virtual address of 5 would be routed in accordance with the port map in the sixth entry of the label table for port 2.
[0045]FIG. 4 is a block diagram illustrating the format of a frame in one embodiment. The illustrated frame is in Fibre Channel format. One skilled in the art will appreciate that other formats can be used such as the InfiniBand format. A frame contains a start-of-frame portion, a header portion, a data portion, and an end-of-frame portion. The header portion includes a 24-bit destination identifier field, a 24-bit source address field, an 8-bit control field, an 8-bit type field, and an 8-bit priority field. The data portion is variable length and contains up to 2112 bytes. The destination and source identifiers include a domain address and a virtual address. The destination identifier identifies a path from a source device (e.g., node or switch) to one or more devices to which a frame is to be sent. The source identifier identifies a path from the destination device to the source device. The control field indicates whether the frame is a control frame or a data frame. A control frame may include response frames (e.g., an acknowledge frame), fabric control frames, flow control management frames, and link control frames. The flow control management and link control frames are standard Fibre Channel defined frames. The type field indicates the type of data in the data field. A data frame contains payload data that is to be sent from one node to another node using the interconnect fabric. The class of a frame specifies whether a frame is to be sent with or without a connection (e.g., Fibre Channel class 1 a connection with acknowledgment). The class field may indicate a class, a priority value, and a preemption flag. Start-of-connection and end-of-connection frames delimit a connection. A connection is a bi-directional, physical connection from a source node through the interconnect fabric to destination node. When the interconnect fabric receives a start-of-connection frame, the interconnect fabric modules cooperate to establish a physical connection between the source and destination nodes. The physical connection is maintained until an end-of-connection frame is sent via the connection or until a frame that has a priority higher than the connection and that designates to preempt conflicting connections (i.e., its preemptive flag is set) is received by an interconnect fabric module that needs to use one of its port that is dedicated to the existing connection.
[0046]FIG. 5 is a diagram illustrating logic of an arbitrator of a switch protocol controller in one embodiment. The arbitrator communicates with the switch control unit via the arbitration bus. The arbitration bus follows the IEEE 896 Futurebus+ arbitration protocol. The arbitration bus is a wired-or bus in which multiple arbitrators can drive their information onto the bus simultaneously. Based on the information that is being driven on the arbitration bus, each arbitrator determines whether it is the arbitrator with the highest priority that is currently driving the bus. When an arbitrator decides that it does not have the highest priority, it stops driving its information onto the bus. Ultimately, the arbitrator with the highest priority will remain driving the bus. At that point the switch control unit retrieves the information from the arbitration bus, which includes the port map for the destination identifier, the switch source port number, and the class. The switch control unit then configures the crosspoint switch to crosspoint connect the input of the switch source port to the output of each switch destination port identified by the port map. The switch control unit then notifies the arbitrator with the highest priority that the crosspoint switch has been configured. In one embodiment, the arbitration bus includes 32 port status lines to indicate whether the corresponding port is currently in use. The switch control unit sets and clears the status lines as it configures the crosspoint switch. If the port status lines indicate that the crosspoint switch cannot be configured in accordance with the port map (e.g., a port indicated in the port map is in use), then the arbitrator, in general, does not participate in arbitrations until all the switch destination ports indicated by the port map become available. In block 501, the arbitrator raises an arbitration signal on the arbitration bus. If the arbitration signal is already raised, then the arbitrator waits until the arbitration signal is lowered before raising the signal. It is possible that two arbitrators can raise the arbitration signal simultaneously. If so, the arbitrator with the highest priority frame is given control of the arbitration bus. In block 502, the arbitrator drives a competition number comprising the 7-bit priority of the frame and the 5-bit port number of its port onto the arbitration bus. In decision block 503, if the arbitrator does not have the highest priority, then it stops driving the competition number and other data onto the arbitration bus in block 504 and then continues to block 501 so it can eventually raise the arbitration signal and try again. If the arbitrator has the highest priority and all the other arbitrators have stopped driving the arbitration bus, then the arbitrator continues at block 505. In block 505, the arbitrator drives the port map, its 5-bit port number, and class onto the arbitration bus. In block 506, the controller stops driving any data on the arbitration bus, and then lowers the arbitration signal. In block 507, the arbitrator receives confirmation from the switch control unit when the crosspoint switch has been appropriately configured. In block 508, the arbitrator signals the transmit controller to transmit the frame to the crosspoint switch and then completes. At that point, other arbitrators detect that the arbitration signal has been lowered and can then arbitrate access to the switch control unit.
[0047]FIG. 6 is a block diagram illustrating the transmit controller in one embodiment. The transmit controller 600 includes a frame generator 601, a multiplexor 602, and an encoder 603. The transmit controller when directed by the arbitrator either generates and transmits a control frame or transmits the frame currently stored in a frame buffer. The encoder forwards the frame to the crosspoint switch for transmission through the switch destination ports.
[0048]FIG. 7 is a block diagram illustrating the interconnection of interconnect fabric modules forming an interconnect fabric that connects various nodes. In this example, the interconnect fabric modules 701, 702, 703, and 704 form a fully connected interconnect fabric. An interconnect fabric is fully connected when each interconnect fabric module is directly connected to each other interconnect fabric module. For example, interconnect fabric module 701 is directly connected to interconnect fabric module 702 via link 762, to interconnect fabric module 703 via link 763, and to interconnect fabric module 704 via link 764. Each interconnect fabric module is also directly connected to various nodes. For example, interconnect fabric module 701 is directly connected to nodes 710. The ports of a interconnect fabric module that are directly connected and other interconnect fabric modules are referred to as expansion ports (“E-ports”), and the ports of an interconnect fabric module that are connected to nodes are referred to as fabric ports (“F-ports”). FIG. 7 illustrates that a connection has been established between node 711 and node 746. Node 711 is directly connected to port 0 of interconnect fabric module 701. Port 0 of interconnect fabric module 701 is connected to port 30 via the crosspoint connection 771. Port 30 of interconnect fabric module 701 is directly connected to port 29 of interconnect fabric module 704 via link 764. Port 29 of interconnect fabric module 704 is connected to port 16 via the crosspoint connection 774. Port 16 of interconnect fabric module 704 is directly connected to node 746. While the connection is maintained, all frames sent from node 711 through port 0 of interconnect fabric module 701 are transmitted through the connection to node 746 via port 16 of interconnect fabric module 704. When a frame is transmitted using a connectionless protocol, the crosspoint switches of the interconnect fabric modules are dynamically configured to route the packet from the source node to the destination node. That is, once an interconnect fabric module transmits a frame from its switch source port through its switch destination port, those ports are available to be reconnected to other ports. Thus, with a connectionless protocol each frame will result in an arbitration at each interconnect fabric module in the path from the source node to the destination node.
[0049]FIG. 8 is a block diagram illustrating the mapping of a destination identifier to a port map. Each interconnect fabric module has a interconnect fabric module identifier 801. In one embodiment, the interconnect fabric identifier contains a domain address that has been assigned to the interconnect fabric module. When a frame is processed by a switch protocol controller, the switch protocol controller determines whether the domain address of the destination identifier matches the domain address assigned to the interconnect fabric module. If so, then the switch protocol controller uses the virtual address label table to retrieve the port map. (The label table is sub-divided into a virtual address label table and a domain address label table.) If the domain addresses do not match, then the switch protocol controller uses a domain address label table to retrieve the port map. The domain address of a frame specifies those interconnect fabric modules that are configured to route the frame and the domain address label table is used to route frames to interconnect fabric modules that are configured to route the frame.
[0053]FIG. 10 is a block diagram illustrating multiframe buffering. A switch protocol controller 1000 includes a receive controller 1001, a multiframe buffer 1002, and a buffer arbitrator 1003. The receive controller receives frames via the input of its port and stores the frame in the next available buffer of the multiframe buffer. In one embodiment, the receive controller may store all the frames of a connection in the same buffer. Alternatively, the received controller may store frames of a connection in different buffers and the buffer arbitrator ensures that frames of an established connection are given the highest priority. The buffer arbitrator is enabled when the switch protocol controller is ready to process the next frame. FIG. 11 is a diagram illustrating the logic of the buffer arbitrator in one embodiment. In decision block 1101, if the switch protocol controller is currently in a connection, then the buffer arbitrator selects the buffer associated with the connection and completes. If, however, the switch protocol controller is not currently in a connection, then the buffer arbitrator calculates a priority score for each frame stored in the multiframe buffer. The buffer arbitrator uses a buffer arbitration algorithm to calculate the priority score. In block 1104, the buffer arbitrator selects the buffer containing the frame with the highest priority score to be processed next and completes.
[0056]FIG. 13 is a block diagram illustrating the use of equivalent ports. Equivalent port service 1303 inputs a port map that may be generated using virtual address 1301 and virtual address label table 1302. Alternatively, the port map may be generated using a domain address and a domain address label table. The equivalent port service also inputs equivalent port table 1304. The equivalent port table contains an entry for each port of the interconnect fabric module. Each entry, referred to as an equivalent port map, contains a bit for each port of the interconnect fabric module. In this example, the entry for port 0 has its bits for port 1 and port 2 set to indicate that port 0, port 1, and port 2 are equivalent. The entry for port 1 has its bits for port 0 and port 2 set to indicate that port 0, port 1, and port 2 are equivalent. The equivalent port service also inputs the port status lines, which indicates the current status of each of the ports of the interconnect fabric module. When the equivalent port service receives a port map it determines whether the designated ports are available based on the port status. If a designated port is not available, the equivalent port service retrieves the equivalent port map for that designated port. The equivalent port service then determines whether any of the equivalent ports are available. If an equivalent port is available, then the equivalent port service changes the port map to designate an available equivalent port. If no equivalent ports are available, then the equivalent port service leaves the port map unchanged. In one embodiment, an equivalent port map may have a priority associated with each port. The equivalent port service may select equivalent ports based on their associated priority. The priorities may be useful, for example, when ports are equivalent, but the cost of routing a frame through the ports are different. For example, port 3 of interconnect fabric module 1201 may be equivalent to port 0, port 1, and port 2, but the cost of routing a frame through port 3 may be higher because the frame would travel through interconnect fabric module 1204 on its way to interconnect fabric module 1202.
[0057]FIG. 14 is a diagram illustrating the logic of the equivalent port service in one embodiment. The equivalent port service receives an input port map and processes each designated port of the input port map. The service may initialize the output port map so that no ports are designated. In block 1401, the service selects of the next designated port of the input port map. In decision block 1402, if all the designated ports have already been selected, then the service completes, else the service continues at block 1403. In decision block 1403, if the selected port is available, then the service designates the selected port in the output port map and proceeds to select the next designated port of the input port map. In block 1405, the service retrieves the equivalent port map for the selected port from the equivalent port table. In block 1406, the service selects the next designated port of the selected equivalent port map. In decision block 1407, if all designated ports of the equivalent port map have already been selected, then the service continues at block 1408, else the service continues at block 1409. In block 1408, the service designates the selected port in the output port map because no equivalent ports are available and completes. The service may repeat this process as ports become available. In decision block 1409, if the selected port of the equivalent port map is available, then the service continues at block 1410, else the service loops to block 1406 to select the next designated port of the equivalent port map. In block 1410, the service designates the selected port of the equivalent port map in the output port map and then loops to select the next designated port of the input port map.
[0059]FIG. 15 is a block diagram illustrating a component for identifying upper layer protocol ports. This component may be part of the header processor of the switch protocol controller. An administrative port comparator 1503 inputs the virtual address of the destination identifier 1501 of a frame and a reserved address table 1502. The reserved address table has entry for each reserved address and contains the value of the reserved address and may contain a flag indicating whether to route a frame designating the reserved address to upper layer protocol port 32 or upper layer protocol port 33. When signaled, the comparator determines whether any of the reserved addresses match the virtual address of the frame. If so, the comparator enables the port 32 or port 33 flags. When enabled, the arbitrator automatically designates the signaled upper layer protocol port during arbitration. The crosspoint switch 1506 may be connected to the interconnect fabric module manager 1507 via upper layer protocol port 32 and upper layer protocol port 33. In this way, the upper layer protocol frames are routed to the interconnect fabric module manager as indicated for further processing.
[0063]FIG. 17 is a diagram illustrating the logic of deadlock avoidance algorithm in one embodiment. The deadlock avoidance algorithm may process each frame that is received by a switch protocol controller. In decision block 1701, if a start-of-connection frame is received, then processing continues at block 1702, else there is no conflict. In decision block 1702, if the port is currently in a connection, then there is a conflict and the processing continues at block 1703, else there is no conflict. In decision block 1703, if the frame that established the connection for this port has a higher priority than the conflicting frame just received, then this port wins the conflict and discards the conflicting frame, else the processing continues at block 1704. In decision block 1704, if the priorities are equal, the processing continues at block 1705 to check the tiebreaker, else this switch protocol controller loses the conflict and continues at block 1706. In decision block 1705, if the domain address of this interconnect fabric module is greater than the domain address of the interconnect fabric module that sent the conflicting frame, then this port wins the conflict, else this port loses the conflict and continues at block 1706. In block 1706, when this port loses conflict, it removes the partial connection that has been established through it by sending a remove connection frame through its input to notify the originating node and the other interconnect fabric modules through which the connection was partially built.
[0065]FIG. 19 is a diagram illustrating the logic of processing a preemption signal in one embodiment. This processing is performed when a switch protocol controller detects a preemption signal on the arbitration bus. In decision block 1901, if this port is currently in a connection, then the switch protocol controller may need to participate in the arbitration. In decision block 1902, if this port is the conflicting port (i.e., established the connection), then this port participates in the arbitration and continues processing at block 1903. In block 1903, the switch protocol controller for this port participates in the arbitration. In decision block 1904, if the switch protocol controller of this port loses the arbitration, then it continues at block 1905 to disconnect the connection, else it leaves the connection established. In block 1905, the switch protocol controller sends a disconnect frame in the direction of its input and output. In block 1906, the switch protocol controller indicates to the switch control unit to remove the crosspoint connection for this port.
[0067]FIG. 20 is a diagram illustrating the logic of distributed class 3 multicasting in one embodiment. This logic is performed when a class 3 frame with multicasting is received at a switch protocol controller. In block 2001, the switch protocol controller identifies the multicast ports that are currently available. The multicast ports may be the set of ports indicated by the port map to which a virtual address maps. In block 2002, if any of the multicast ports are available, then the switch protocol controller participates in arbitration. In decision block 2003, if the switch protocol controller wins the arbitration, then it continues at block 2004, else it continues at block 2001 to again participate in an arbitration. In block 2004, the switch protocol controller sends the frame and updates the port map stored in a temporary buffer to reflect those ports through which the frame has been sent. In decision block 2005, if the multicast is complete (i.e., the frame has been transmitted through each multicast port), then processing completes, else processing continues to participate in an arbitration to send the frame as additional ports become available.
International Classification H04L12/28, G06F15/173, G06F15/16, H04J3/16, G06F11/30, H04J1/16, H04L12/56, H04L12/50
Cooperative Classification H04L67/322, H04L67/1029, H04L67/1031, H04L69/08, H04L67/1008, H04L67/1002, H04L69/22, H04L67/1014, H04L49/357, H04L63/0245, H04L49/101, H04L63/0236, H04L49/552
European Classification H04L29/08N9A1E, H04L29/06E, H04L29/08N9A1B, H04L49/55A, H04L29/08N9A9, H04L49/35H2, H04L29/08N9A7, H04L29/08N31Q, H04L29/08N9A
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:FOSTER, MICHAEL S.;DORSETT, MICHAEL A.;REEL/FRAME:012472/0001