Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1998-07-24
2002-02-26
Ngo, Ricky (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S394000, C370S428000, C709S232000
Reexamination Certificate
active
06351454
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to the field of data exchange. More specifically, this invention relates to data exchange among a plurality of agents using a plurality of data links, each data link passing through or including a crossbar.
2. Background
Those of ordinary skill in the art will realize that, in its most basic form, data exchange can represent the transfer of data of a communication from a transmitting agent to a receiving agent over a single dedicated data link. In a slightly more complicated form, data exchange can represent the transfer of data from agent A to agent B over dedicated data link
1
and the transfer of data from agent B to agent A over dedicated data link
2
. Alternatively, data exchange can represent the transfer of data from agent A to agent B over a dedicated data link at time 1 and the transfer of data from agent B to agent A over the same dedicated data link at time 2 where time 1 and time 2 are different times such that the two transmissions do not conflict with one another. In its most abstract form, data exchange can represent the transfer of data from n transmitting agents to n receiving agents over n data links where n is an positive integer. As the number of agents and data links grows, the complexity and cost of the data exchange system can become extreme.
One method for simplifying the data exchange system is to combine the data links rather than have separate links between each of the agents. This can be accomplished by connecting each of the agents only to a common point or crossbar (XBAR) which connects the agents two at a time as appropriate to complete the data link between the agents. This method benefits from a reduction in the number of data links in the data exchange system but suffers from an increase in traffic over each of the data links. Those of ordinary skill in the art will realize that each of the data links has a limited bandwidth depending on the transmission media. Eventually, each of the data links will reach this limit and will not be able to transmit any more data at any faster speeds.
Some terminology which will be used herein will now be set forth. The term “Switch Fabric” describes a plurality of Data Links interconnecting Agents through Packet Switching Crossbars (“XBARs”). The Switch Fabric can be constructed using one or more XBARs. Each “Agent” can transmit or receive data over the Switch Fabric. An Agent which is involved in a data transfer in which it is transmitting is called the “Transmitting Agent”. Likewise, an Agent which is involved in a data transfer in which it is receiving is called the “Receiving Agent”. Agents and XBARs connect to Data Links using “Data Link Ports”. An Agent has as many Data Link Ports as there are XBARs in the system. An XBAR has as many Data Link Ports as there are Agents in the system.
The data which is transferred between Agents is called a “Stream of Packets” and each of the packets will be of arbitrary size. The Stream of Packets is comprised of one or more “Flows”. A “Flow” is a group of packets that are related, i.e., they are commonly addressed. An “Order Critical Flow” is a Flow which is order sensitive, i.e., the order of this group of packets needs to be maintained when being transferred over the Switch Fabric. Such order must be maintained, for example, in voice over packet communications and video over packet communications, to name two examples.
Each Transmitting Agent keeps a queue of packets to be transmitted in a Transmit Queue (“TQ”) or transmit buffer. Each Transmitting Agent keeps queues of packets for each Data Link of the Switch Fabric. These are called Transmit Link Queues (“TLQs”). A Transmitting Agent's packets to be transmitted are removed from its TQ and assigned to its plurality of TLQs and then transmitted over the Data Link(s).
Each Receiving Agent keeps a queue of packets received from each Data Link of the Switch Fabric. These are called Receive Link Queues (“RLQs”). Each Receiving Agent keeps a queue of packets received in a Receive Queue (“RQ”) or receive buffer. A Receiving Agent's received packets are removed from its plurality of RLQs to its RQ as the received packets are received.
Packets which pass between agents across the switch fabric can be separated into two groups: those for which order must be maintained and those whose order can be modified by the switch fabric. As was previously mentioned, the former group is defined to be an Order Critical Flow while the latter is defined simply as a Flow. There are numerous reasons why an Order Critical Flow might exist in a system. One might be that the flow is comprised of packets of digitized video or audio. In this case, it is highly desirable to keep all packets of this flow in sequential order. Out of order packets would introduce distortions in what is supposed to approximate a continuous signal. This is just one example of an Order Critical Flow; there are many others. The present invention addresses the issue of maintaining packet ordering for Order Critical Flows regardless of the reason for the requirement for preservation of packet order.
SUMMARY OF THE INVENTION
A data exchange system includes at least one transmitting agent, at least one receiving agent, and a plurality of data links each having a crossbar coupling respective transmitting agents and receiving agents. A stream of data packets including at least one Order Critical Flow of data packets having a critical order to be sent from the transmitting agent to the receiving agent is divided for transmission among the plurality of data links. Multiple Order Critical Flows between the transmitting agent and the receiving agent are possible and the packets within such Order Critical Flows can be intermixed for transmission (along with packets from other Non-Order Critical Flows). The packets are transmitted over the data links so that packets from the same Order Critical Flow are transmitted over the same data link (while packets from that Order Critical Flow are in the Transmit Link Queue) and the packets are sequentially numbered, based upon the time when the first byte of the packet was received (and not the link over which the packet was received) and reassembled by the receiving agent into a stream of data packets in accordance with the numbering sequence, thus maintaining the order of all Order Critical Flows.
OBJECTS AND ADVANTAGES OF THE INVENTION
Accordingly, it is an object and advantage of the present invention to provide a method and apparatus for data exchange that exhibits improved data exchange system bandwidth.
It is another object and advantage of the present invention to provide increased Switch Fabric bandwidth by allowing the use of multiple parallel Data Links for packet transfer in circumstances where the order of some (but not all) packets is critical.
It is another object and advantage of the present invention to provide an economical high speed parallel data link.
It is another object and advantage of the present invention to take advantage of the fact that not all flows of packets sent over the data exchange system will be Order Critical Flows and thereby to maximize the useable bandwidth of the Switch Fabric by passing such Non-Order Critical Flows of packets through Parallel Data Links simultaneously with packets from Order Critical Flows queued for transmit over a selected Data Link.
It is another object and advantage of the present invention to process received packets at the Receiving Agent in the sequential order in which they were initially received in order to provide a simple method for allocating processing resources to individual Data Links while achieving the goal of maintaining the order of Order Critical Flows.
It is another object and advantage of the present invention that the use of Multiple Data Links to communicate between Transmitting Agents and Receiving Agents provides a measure of redundancy to the communications system.
These and many other objects and advantages of the present invention will become apparent to t
Crocker Daniel W.
Ng Daniel Yu Kwong
Cisco Technology Inc.
Ngo Ricky
Ritchie David B.
Thelen, Reid & Pries
LandOfFree
Apparatus and method for maintaining packet ordering over... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for maintaining packet ordering over..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for maintaining packet ordering over... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2973958