Patent Publication Number: US-8116206-B1

Title: Method and system for routing frames in a network

Description:
BACKGROUND 
     1. Technical Field 
     The present disclosure relates to networks, and more particularly, to routing frames in a storage area network. 
     2. Related Art 
     Networks typically use frames or packets (used interchangeably through out this specification) to send information (or data) between network nodes. A network node is a port for a network device (for example, a switch, host bus adapter and others). A network node that transmits a frame may be designated as a “transmitting node” and a network node that receives a frame may be designated as a “receiving node” 
     Typically, when a receiving node receives a frame, the frame is stored (or staged) in a receive buffer (or memory storage space). The receiving node makes a routing decision to send the frame to its destination based on the local conditions affecting the receive node. The receiving node is not aware of other receiving nodes that may be trying to use the same transmit resources to send a frame. If two or more receiving nodes are trying to use the same transmit node, oversubscription will occur leading to congestion and a reduction in the overall network bandwidth. 
     Therefore, there is a need for a system and method for routing frames in a network or a multi level switch. 
     SUMMARY 
     A method for routing frames is provided. The method comprises: receiving a frame at a receive port segment of a port for a switch element; generating a tag based on information included in the frame, where the tag identifies a location where the frame is stored in the receive port segment; transmitting the tag to a destination port for the frame; generating a request for the frame, where the destination port generates the request for the frame; transmitting the request for the frame to the port that received the frame, where a field in the request differentiates the request for the frame from the tag generated by the receive port segment of the port that received the frame; and transmitting the frame stored at the receive port segment, in response to the request sent by the destination port. 
     A network system is provided. The network system comprises: a first switch element including at least one port having a receive segment and a transmit segment, where the receive segment for the port receives a frame; a second switch element with at least one port having a receive segment and a transmit segment; where the port for the second switch element is a destination for the frame received by the first switch element port; where the first switch element port generates a tag based on information included in the frame, where the tag identifies a location where the frame is stored in the receive port segment; and the transmit segment of the port for the first switch element transmits the tag to the destination port at the second switch element; and wherein the second switch element port generates a request for the frame, and transmits the request for the frame to the first switch element port, where a field in the request differentiates the request for the frame from the tag generated by the first switch element port; and in response to the request, the first switch element port transmits the frame stored at the receive port segment of the first switch element. 
     A first network switch element is provided. The first network switch element comprises: at least one port having a receive segment and a transmit segment, where the receive segment for the port receives a frame; and a tag writer for the first switch element port generates a tag based on information included in the frame, the tag identifying a location where the frame is stored in the receive port segment; and the transmit segment of the port for the first switch element transmits the tag to a destination port at a second switch element; wherein the second switch element port generates a request for the frame, and transmits the request for the frame to the first switch element port, where a field in the request differentiates the request for the frame from the tag generated by the first switch element port; and in response to the request, the first switch element port transmits the frame stored at the receive port segment of the first switch element. 
     This brief summary has been provided so that the nature of the disclosure may be understood quickly. A more complete understanding of the disclosure can be obtained by reference to the following detailed description of the preferred embodiments thereof concerning the attached drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The foregoing features and other features of the present disclosure will now be described with reference to the drawings of the various embodiments. In the drawings, the same components have the same reference numerals. The illustrated embodiments are intended to illustrate, but not to limit the disclosure. The drawings include the following Figures: 
         FIG. 1A  shows an example of a network system, used according to one embodiment of the present disclosure; 
         FIG. 1B  shows an example of a Fibre Channel switch element, according to one embodiment of the present disclosure; 
         FIG. 1C  shows a block diagram of a 20-channel switch chassis, according to one embodiment of the present disclosure; 
         FIGS. 1D and 1E  shows block diagrams of a Fibre Channel switch element, according to one embodiment of the present disclosure; 
         FIG. 1F  shows a block diagram of a multi-level switch element using conventional routing techniques; 
         FIG. 2  shows a port structure used according to one embodiment of the present disclosure; 
         FIG. 3  shows an example of a tag structure used according to one embodiment of the present disclosure; 
         FIG. 4  shows a process flow diagram for generating a tag at a receive port, according to one embodiment of the present disclosure; and 
         FIG. 5  shows another process flow diagram for processing a tag received at a destination port, according to one embodiment of the present disclosure. 
     
    
    
     DETAILED DESCRIPTION 
     Definitions 
     The following definitions are provided as they are typically (but not exclusively) used in the Fibre Channel environment, implementing the various adaptive aspects of the present disclosure 
     “Fibre Channel ANSI Standard”: The standard (incorporated herein by reference in its entirety) describes the physical interface, transmission and signaling protocol of a high performance serial link for support of other high level protocols associated with IPI, SCSI, IP, ATM and others. 
     “Fabric”: The structure or organization of a group of switches, target and host devices (NL_Port, N_ports etc.). 
     “FIFO”: A first in first out buffer structure used for storing information. 
     “Port”: A general reference to N. Sub.--Port or F.Sub.--Port. 
     “Switch”: A fabric element conforming to the Fibre Channel Switch standards. 
     “Tag”: A collection of information that identifies a unique data frame. 
     To facilitate an understanding of the various embodiments, the general architecture and operation of a network system/network switch is described. The specific architecture and operation of the preferred embodiment will then be described with reference to the general architecture. 
     Storage area networking systems may use standard or proprietary protocols, or a combination of protocols for enabling communication, for example, Fibre Channel, Infiniband (“IB”), Ethernet, Fibre Channel Over Ethernet (FCoE) or any other standard. These standards are incorporated herein by reference in their entirety. The following examples are based on Fibre Channel standards; however the adaptive aspects described herein are not limited to any particular standard or protocol. 
     Fibre Channel is a set of American National Standard Institute (ANSI) standards, which provide a serial transmission protocol for storage and network protocols such as HIPPI, SCSI, IF, ATM and others. Fibre Channel provides an input/output interface to meet the requirements of both channel and network users. 
     Fibre Channel supports three different topologies: point-to-point, arbitrated loop and Fibre Channel fabric. The point-to-point topology attaches two devices directly. The arbitrated loop topology attaches devices in a loop. The Fibre Channel fabric topology attaches host systems directly to a fabric, which are then connected to multiple devices. The Fibre Channel fabric topology allows several media types to be interconnected. 
     Fibre Channel fabric devices include a node port or “N_Port” that manages fabric connections. The N_port establishes a connection to a fabric element (e.g., a switch) having a fabric port or “F_port”. Fabric devices may also support expansion ports (E_Ports) between switching elements. 
     A Fibre Channel switch is a multi-port device where each port manages a point-to-point connection between itself and its attached system. Each port can be attached to a server, peripheral, I/O (input/output) subsystem, bridge, hub, router, or even another switch. A switch receives messages from one port and routes it to another port. 
     Network System: 
       FIG. 1A  is a block diagram of a network system  100  implementing the methods and systems in accordance with the various embodiments disclosed herein. Network system  100  may be based on Fibre Channel, IB, or any other protocol. The examples below are described with respect to Fibre Channel but are applicable to Fibre Channel or any other standard. 
     System  100  includes plural devices that are interconnected. Each device includes one or more ports, classified as for example, node ports (N_Ports), fabric ports (F_Ports), and expansion ports (E_Ports) Node ports may be located in a node device, e.g. server  103 , disk array  105  and storage device  104 . Fabric ports are located in fabric devices such as switch  101  and  102 . Arbitrated loop  106  may be operationally coupled to switch  101  using arbitrated loop ports (FL_Ports). 
     The devices of  FIG. 1A  are operationally coupled via “links” or “paths”. A path may be established between two N_ports, e.g. between server  103  and storage  104 . A packet-switched path may be established using multiple links, e.g. an N_Port in server  103  may establish a path with disk array  105  through switch  102 . 
       FIG. 1B  is a block diagram of a 20-port ASIC (Application Specific integrated Circuit) Fabric switch element, used according to one embodiment.  FIG. 1B  provides the general architecture of a 20 channel switch chassis using the 20-port Fabric element. Fabric element includes ASIC  120  that supports non-blocking Fibre Channel class 2 (connectionless, acknowledged) service and class 3 (connectionless, unacknowledged) service between any ports. It is noteworthy that ASIC  120  may also be designed for class 1 (connection-oriented) service, within the scope and operation of the present embodiment as described herein. 
     The Fabric element of the present disclosure is presently implemented as a single CMOS ASIC, and for this reason the term “Fabric element” and ASIC are used interchangeably to refer to the preferred embodiments in this specification. Although  FIG. 1B  shows 20 ports, the present disclosure is not limited to any particular number of ports. 
     ASIC  120  has 20 ports numbered in  FIG. 1B  as GL 0  through GL 19 . These ports are generic to common Fibre Channel port types, for example, F_Port, FL_Port and E_Port. In other words, depending upon what it is attached to, each generic port (also referred to as GL Port) can function as any type of port. Also, the GL port may function as a special port useful in fabric element linking, as described below. 
     For illustration purposes only, all GL ports are drawn on the same side of ASIC  120  in  FIG. 1B . However, the ports may be located on both sides of ASIC  120  as shown in other Figures. This does not imply any difference in port or ASIC design. Actual physical layout of the ports will depend on the physical layout of the ASIC. 
     Each port GL 0 -GL 19  includes transmit and receive connections to switch crossbar  115 . Within each port, one connection is through receive buffer  121 , which functions to receive and temporarily hold a frame during a routing operation. The other connection is through transmit buffer  122 . 
     Switch crossbar  115  includes a number of switch crossbars for handling specific types of data and data flow control information. For illustration purposes only, switch crossbar  115  is shown as a single crossbar. Switch crossbar  115  is a connectionless crossbar (packet switch) of known conventional design, sized to connect 21×21 paths. This is to accommodate 20 GL ports plus a port for connection to a fabric controller, which may be external to ASIC  120 . 
     In one embodiment, the switch chassis described herein, the Fabric controller is a firmware-programmed microprocessor, also referred to as the input/output processor (“IOP”). As seen in  FIG. 1B , bi-directional connection to IOP  110  is routed through port  111 , which connects internally to a control bus  112 . Transmit buffer (“T”)  116 , receive buffer (“R”)  118 , control register  113  and Status register  114  (within block  113 A) connect to bus  112 . Transmit buffer  116  and receive buffer  118  connect the internal connectionless switch crossbar  115  to IOP  110  so that it can source or sink frames. 
     Control register  113  receives and holds control information from IOP  110 , so that IOP  110  can change characteristics or operating configuration of ASIC  120  by placing certain control words in register  113 . IOP  110  can read status of ASIC  120  by monitoring various codes that are placed in status register  114  by monitoring circuits (not shown). 
       FIG. 1C  shows a 20-channel switch chassis S 2  using ASIC  120  and IOP  110 . IOP  110  in  FIG. 1C  is shown as a part of a switch chassis utilizing one or more of ASIC  120 . S 2  also includes other elements, for example, a power supply (not shown). The 20 GL_Ports correspond to channels (also referred to as “C”) C 0 -C 19 . 
     Each GL_Port has a serial/deserializer (SERDES) (also referred to as “S”) designated as S 0 -S 19 . Ideally, the SERDES functions are implemented on ASIC  120  for efficiency, but may alternatively be external to each GL_Port. The SERDES converts parallel data into a serial data stream for transmission and converts received serial data into parallel data. 
     Each GL_Port may have an optical-electric converter, designated as (also referred to as “OE”) OE 0 -OE 19  connected with its SERDES through serial lines, for providing fibre optic input/output connections, as is well known in the high performance switch design. The converters connect to switch channels C 0 -C 19 . It is noteworthy that the ports can connect through copper paths or other means instead of optical-electric converters. 
       FIG. 1D  shows a block diagram of ASIC  120  with sixteen GL ports and four high speed (for example, 10 Gb) port control modules designated as XG 0 -XG 3  for four high-speed ports designated as XGP 0 -XGP 3 . GL ports (GL 0 -GL 15 ) communicate with 1 g/2 g SFP Port modules SFP 0 -SFP 15 . SFP is a small form factor pluggable optical transceiver. ASIC  120  include a control port  113 A (that includes control register  113 ) that is coupled to IOP  110  through a PCI connection  110 A. 
     FIGS.  1 E( i )/E( ii ) (jointly referred to as  FIG. 1E ) show yet another block diagram of ASIC  120  with sixteen GL and four XG port control modules. Each GL port control module has a receive port (or a receive segment) (RPORT)  132  with a receive buffer (RBUF)  132 A (similar to  121 ,  FIG. 1B ) and a transmit port (or a transmit segment)  130  with a transmit buffer (TBUF)  130 A (similar to  122 ,  FIG. 1B ). GL and XG port control modules are coupled to physical media devices (“PMD”)  134  and  135  respectively. 
     Control port module  113 A includes control buffers  113 B and  113 D for transmit and receive sides, respectively. Module  113 A also includes a PCI interface module  113 C that interfaces with IOP  110  via a PCI bus  110 A. It is noteworthy that the present disclosure is not limited the PCI bus standard, any other protocol/standard may be used to interface control port  113 A components with IOP  110 . 
     XG_Port (for example 136) includes RPORT  138 A with RBUF  138  similar to RPORT  132  and RBUF  132 A and a TBUF  137  and TPORT  137 A similar to TBUF  130 A and TPORT  130 . Protocol module  139  interfaces with SERDES to handle protocol based functionality. 
     Incoming frames are received by RPORT  132  via SERDES  131  and then transmitted using TPORT  130 . Buffers (RBUF)  132 A and (TBUF)  130 A are used to stage frames in receive and transmit paths. 
       FIG. 1F  shows an example of a Multi Level IB switch system with a plurality of Application Specific Integrated Circuits (“ASIC”) (switch elements)  141 ,  150 ,  151 ,  152 ,  153  inter-connected via plural inter-switch links (ISLs) (for example,  142 ,  143 ,  144  and  145 ). Switch elements  150 ,  151 ,  152  and  153  are shown as having four ports A, B, C and D and the ports are referred to as  150 A- 150 D (for ASIC  150 ),  151 A- 151 D (for ASIC  151 ),  152 A- 152 D (for ASIC  152 ), and  153 A- 153 D (for ASIC  153 ). Each switch element may have any number of ports and the number of ports may not be equal. 
     The Uplink of ISL  142  routes packets from ASIC  150  to ASIC  141 , while uplinks of ISL  144  and ISL  145  route packets from ASIC  152  and ASIC  153  to ASIC  141 . The Downlink of ISL  143  routes packets from ASIC  141  to ASIC  151 . 
     Typically, when a packet arrives at a port ( 150 A) of an IB switch element (for example, ASIC  150 ), the port performs a look-up using a static routing table to determine packet destination (for example, PORT  150 A to PORT  151 A). In some instances, a packet is routed to one switch element via an uplink and then routed back to another switch element via another downlink. For example, a packet may be routed via the uplink of ISL  142  to switch element  141  and then routed back via the downlink of ISL  143  to switch element  151 . 
     Static routing table based routing has disadvantages because a particular downlink may be over used (“over subscribed”) by attempting to transmit multiple packets at the same time; or may be under utilized (“or under subscribed”). For example, in  FIG. 1F , ASIC  141  receives packets from ASICs  150 ,  152  and  153  and then routes them to ASIC  151  using the downlink of ISL  143 . Since the downlink of ISL  143  is used for routing packets from the foregoing ASICs, it may result in over subscription, reducing multi Level switch and overall network throughput. 
     Also, depending on a routing path, uplink  142  may be over subscribed. For example, uplink  142  may be over subscribed when port  150 A sends packets to port  151 A; port  150 B sends packets to port  152 A; port  150 C sends packets to port  153 A and port  150 D sends packets to  154 A. 
     The adaptive embodiments described herein solve this problem by holding a frame at a receive port in the first switch element and sending a tag to a destination port. The destination port processes individual tags and sends a request for the incoming frame to the receive port. It is noteworthy that the receive port and the destination port may be on different switch elements or ASICs. 
       FIG. 2  shows a block diagram of a port structure  200 , used according to one embodiment of the present disclosure. Port structure  200  includes a receive port segment (or receive port)  214  that receives and processes received frames  201  and transmit port segment (or transmit port)  215  that transmits frames and tags via link  213 . 
     Receive port  214  receives frame in a receive buffer  202 . Depending on the protocol being used, the frame source and destination information is obtained from a frame header. For example, in a Fibre Channel system, the source identifier (S_ID) field is used to identify the frame source and a destination identifier (D_ID) is used to identify a destination. After the received frames are processed, they are stored in a frame buffer  204  where the frames wait for a request from a destination port. As soon as the frames are received and processed in receive buffer  202 , tag writer  203  creates a tag that is described below with respect to  FIG. 3 . The tag is sent to the destination port based on the destination information included in the received frame. 
     Memory  205  (shown as tag FIFO (first-in-first out)  205 ) is used to store the tags written by tag writer  203 . The tags are sent to the destination port of a received frame via crossbar  206  and transmit port  215 . 
     Transmit port  215  includes a tag FIFO  212  where received tags are staged. An arbitration module  211  receives requests for processing a tag. A tag is selected by arbitration module  211  and transmit module  208  sends the tag to its destination via transmit buffer  210 . Transmit port  215  may also include a frame buffer  207  for staging frames that are sent out to their destination. 
       FIG. 3  shows a block diagram of a tag structure  300  used by tag writer  203  to create a tag for a frame (for example,  201 ) received from another port. Tag structure  300  includes a special character  302  that differentiates the tag from a frame. An example of such a character is the “K” character. Tag structure  300  further includes an ASIC number  303  that identifies an ASIC from where the tag is generated. Port number  304  identifies the port where a frame is received and slot number  305  identifies the location of where the frame is staged (for example, a memory slot of frame buffer  204 ). Type field  306  is used to identify a tag sent by a receive port, or a request for a frame sent by a destination port. For example, a bit value of 0 may identify a tag from a receive port and a bit value of 1 may identify a request from a destination port.  307  is a reserved field. 
       FIG. 4  shows a process flow diagram for routing frames, according to one embodiment. The process starts in step S 400 . In step S 401 , a frame is received (for example, frame  201 ,  FIG. 2 ). In step S 402 , a route for the frame is determined. The route is determined by evaluating a destination or other fields in a frame header. 
     In step S 403 , a tag is created for the received frame and is sent to the destination port. An example of a tag structure is described above with respect to  FIG. 3 . Simultaneously, while the tag is being created/sent, in step S 404 , the received frame is stored at the receive port (for example, in frame buffer  204 ). 
       FIG. 5  shows a process flow diagram for processing a received tag at a destination port. The process starts in step S 500  when a transmit tag is received by the destination port. In step S 501 , the tag is stored in memory (for example, tag FIFO  212 ) at the destination port. In step S 502 , arbitration module  211  selects a tag from among a plurality of tags in tag FIFO  212 . In step S 503 , after reading the tag, the destination port sends a request to the receive port to send the received frame. 
     In step S 504 , the port that received the frame transmits the frame to the destination port. The process ends in step S 505 . 
     This method allows efficient bandwidth utilization on links between switch elements because the use of the links is scheduled by a destination port. This prevents multiple receive ports from trying to send frames to the same destination port at the same time. With only one receive port sending a frame to a given destination at any given time, the other receive ports may send frames to other destination ports, thereby increasing the overall throughput. 
     Although the present disclosure has been described with reference to specific embodiments, these embodiments are illustrative only and not limiting. Many other applications and embodiments of the present disclosure will be apparent in light of this disclosure and the following claims.