Cross-point switch with deadlock prevention

Details Cross-point switch with deadlock prevention Cross-point switch with deadlock prevention

2002-08-02

2003-12-30

Vanderpuye, Kenneth (Department: 2663)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S428000, C370S429000

Reexamination Certificate

active

06671275

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a digital data switch, and more particularly, to a digital data switch with mechanisms for prevention of deadlock.
2. Related Art
A network switch is a device that provides a switching function (i.e., determines a physical path) in a data communications network. Switching involves transferring information, such as digital data packets or frames, among entities of the network. Typically, a switch is a computer having a plurality of circuit cards coupled to a backplane. In the switching art, the circuit cards are typically called “blades.” The blades are interconnected by a “switch fabric” or “switching fabric,” which is a switchable interconnection between blades. The switch fabric can be located on a backplane, a blade, more than one blade, a separate unit from the blades, or on any combination thereof. Each blade includes a number of physical ports that couple the switch to other network entities over various types of media, such as coaxial cable, twisted-pair wire, optical fibers, or a wireless connection, using a communication protocol such as Ethernet, FDDI (Fiber Distributed Data Interface), or token ring. A network entity includes any device that transmits and/or receives data packets over such media.
The switching function provided by the switch typically includes receiving data at a source port from a network entity and transferring the data to a destination port. The source and destination ports may be located on the same or different blades. In the case of “local” switching, the source and destination ports are on the same blade. Otherwise, the source and destination ports are on different blades and switching requires that the data be transferred through the switch fabric from the source blade to the destination blade. In some cases, the data may be provided to a plurality of destination ports of the switch. This is known as a multicast data transfer.
Switches operate by examining the header information that accompanies data in the data frame. In some communications protocols, the header information is structured in accordance with the International Standards Organization (ISO) 7-layer OSI (open-systems interconnection) model. In the OSI model, switches generally route data frames based on the lower level protocols such as Layer 2. In contrast, routers generally route based on the higher level protocols such as Layer 3 and by determining the physical path of a data frame based on table look-ups or other configured forwarding or management routines to determine the physical path (i.e., route).
Ethernet is a widely used lower-layer network protocol that uses broadcast technology. The Ethernet frame has six fields. These fields include a preamble, a destination address, source address, type, data and a frame check sequence. In the case of an Ethernet frame, a digital switch will determine the physical path of the frame based on the source and destination addresses.
A problem of deadlock (also known as lock up, or hang up, or deadly embrace) exists in virtually all modern digital switches. Typical digital switches include multiple ports, each one of which can transmit data to any one of the other ports. Each port has a FIFO, sometimes multiple FIFOs. The switching fabric also typically contains multiple FIFOs, and is responsible for managing and arbitrating data transfer between the various ports. A condition that may occur, particularly during heavy utilization of multiple ports of the same switching fabric, is that as the FIFOs fill up with outgoing data, each port is simultaneously waiting for another port to be allowed to transmit data to that port through the digital switch. For example, port A is waiting for port B, port B is waiting for port C, port C is waiting for port D, and port D is waiting for port A (in a 4 port example). This situation, which is most likely to occur during heavy traffic conditions, is referred to as a deadlock, a “deadly embrace,” or a “lockup.”
Accordingly, a need exists for a digital switch with a mechanism that ensures that a lockup will not occur, regardless of the size of the packet or amount of data traffic through the digital switch.
SUMMARY OF THE INVENTION
The present invention is directed to a digital data switch with deadlock prevention that substantially obviates one or more of the problems and disadvantages of the related art.
There is provided a network switch including a switching fabric that routes data traffic between the plurality of cross points. Each cross-point has a plurality of ports. An arbitrator arbitrates the data traffic based on a cut-through request for packets above a predetermined size, and based on a store and forward request for packets below the predetermined size.
In another aspect there is provided a network switch including a switching fabric with a plurality of cross points, the switching fabric switching data between a plurality of ports belonging to the plurality of cross points. A cycle-based arbitrator arbitrates traffic within each cross point. A packet-based arbitrator arbitrates traffic between the cross points in response to a store and forward request for packets smaller than the predetermined size and in response to a cut-through request for packets larger than a predetermined size.
In another aspect there is provided a switch including a plurality of cross points connected by a switching fabric, each cross point connected to a plurality of ports. A round-robin arbitrator arbitrates traffic between ports belonging to the same cross point. A packet-switch arbitrator arbitrates traffic between ports belonging to different cross points based on a store-and-forward request for packets smaller than the predetermined size and based on a cut-through request for packets larger than a predetermined size.
In another aspect there is provided a switch including a switching fabric connecting a plurality of ports. A plurality of FIFOs in the switching fabric temporarily store data traffic from the ports. A multi-level arbitrator arbitrates the data traffic between the ports using two levels of arbitration. A first level arbitration is used by the multi-level arbitrator for FIFOs with at least some data. A second level arbitration is used by the multi-level arbitrator for FIFOs with at least one packet.
In another aspect there is provided a method of switching data traffic including the steps of receiving a packet, determining size and destination of the packet, arbitrating packet transmission based on the size of the packet. Packet is arbitrated in a cut-through manner within a cross point of a digital switch, and in a store and forward manner between different cross points of the digital switch.
In another aspect there is provided a method of switching data traffic including the steps of receiving packets from a plurality of sources, determining size and destination of the packets, arbitrating packet transmission of packets larger than a predetermined size in response to a cut-through request, and arbitrating packet transmission of packets smaller than a predetermined size in response to a store-and-forward request.
Additional features and advantages of the invention will be set forth in the description that follows, and in part will be apparent from the description, or may be learned by practice of the invention. The advantages of the invention will be realized and attained by the structure particularly pointed out in the written description and claims hereof as well as the appended drawings.
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are intended to provide further explanation of the invention as claimed.


REFERENCES:
patent: 4876681 (1989-10-01), Hagiwara et al.
patent: 5307345 (1994-04-01), Lozowick et al.
patent: 5663959 (1997-09-01), Nakagawa
patent: 6035414 (2000-03-01), Okazawa et al.
patent: 6125417 (2000-09-01), Bailis et al.
patent: 6144668 (2000-11-01), Bass et al.
Copy of International Search Report for Appl

Affiliated with

Also associated with

Rating

Cross-point switch with deadlock prevention does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Cross-point switch with deadlock prevention, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cross-point switch with deadlock prevention will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3121049