Method and system for sorting packets in a network

Details Method and system for sorting packets in a network Method and system for sorting packets in a network

2001-02-13

2004-03-30

Pham, Chi (Department: 2664)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

Reexamination Certificate

active

06714554

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to field of network communication. More specifically, the present invention is directed to a method and a system for sorting packets/cells in a switch.
BACKGROUND
The desire to integrate data, voice, image, video and other traffic over high speed digital trunks has led to the requirement for faster networks including the capability to route more information faster from one node to another node. A switch performs this routing of information. Generally, the switch consists of three logical elements: ports, a switch fabric and a scheduler.
Routing and buffering functions are two major functions performed by a switch fabric. New packets arriving at an ingress are transferred by the scheduler across the switch fabric to an egress. The ingress refers to a side of the switch which receives arriving packets (or incoming traffic). The egress refers to a side of the switch which sends the packets out from the switch.
Most of the switches today are implemented using a centralized crossbar approach.
FIG. 1
is an exemplary illustration of a centralized crossbar switch. The packets arrive at the centralized crossbar switch
100
at multiple ingress ports
105
on the ingress
102
. They are transferred across the switch fabric
110
to multiple egress ports
115
on the egress
104
and then sent out to an output link (not shown). The centralized crossbar switch
100
can transfer packets between multiple ingress port-to-egress port connections simultaneously.
A centralized scheduler controls the transfer of the packets from the ingress ports
105
to the egress ports
115
. Every packet that arrives at the ingress ports
105
has to be registered in the centralized scheduler. Each packet then waits for a decision by the centralized scheduler directing it to be transferred through the switch fabric
110
. With fixed size packets, all the transmissions through the switch fabric
110
are synchronized.
Each packet belongs to a flow, which carries data belonging to an application. A flow may have multiple packets. There may be multiple flows arriving at the ingress ports
105
at the same time. Since the packets in these multiple flows may be transferred to the same egress port, each of these packets waits for its turn in ingress buffers (not shown) in the ingress
102
.
The centralized scheduler examines the packets in the ingress buffers and chooses a set of conflict-free connections among the appropriate ingress ports
105
and egress ports
115
based upon the configuration of the switch fabric
110
. One of the egress ports
115
may receive packets from one or more ingress ports
105
. However, at any one time, the centralized scheduler ensures that each ingress port is connected to at most one egress port, and that each egress port is connected to at most one ingress port.
Each packet transferred across the switch fabric
110
by the centralized scheduler waits in egress buffers (not shown) in the egress
104
to be selected by the centralized scheduler for transmission out of the switch. The centralized scheduler places the selected packets in the appropriate egress ports
115
to have the packets transmitted out to an output link.
Each packet belongs to a flow. There may be multiple flows arriving at the ingress at the same time, and the centralized scheduler has to select a packet from one of these multiple flows. This may be time consuming since the number of incoming packets can be very large. For example, when there are 256 K flows, potentially there can be 256 K packets (one from each flow) from which to select. The centralized scheduler examines all of the incoming packets and then performs multiple comparisons in order to select a packet to send across the switch fabric
110
. The packet is selected based on several factors, such as, for example, priority level, arrival time, etc. The large number of packets could make it difficult to perform all the comparisons and to select the packet to send across the switch fabric
110
in a short time. As such, the selection process may take multiple packet times (i.e., the time it takes for the switch to process one packet). That is, it takes more time for the switch to select a packet to send across the switch fabric than it takes for the switch to move the packet to an output link. This packet selection process may be inefficient because it slows the performance of the switch.
SUMMARY OF THE INVENTION
A method and apparatus for sorting packets is disclosed. In one embodiment, a method for sorting comprises grouping flows according to a first flow rate and a second flow rate. Each flow comprises multiple packets. The flows in the first flow rate may be sorted according to an arrival time of a first packet in each flow. These flows are placed in a first FIFO (first-in-first-out) queue with a flow having an earliest first packet arrival time located at a head of the first FIFO queue. The flows in the second flow rate may be sorted according to an arrival time of a first packet in each flow. These flows are placed in a second FIFO queue with a flow having an earliest first packet arrival time located at a head of the second FIFO queue. A comparison is performed to select a packet from between the first packet of the flow at the head of the first FIFO queue with the first packet of the flow at the head of the second FIFO queue.


REFERENCES:
patent: 5764626 (1998-06-01), Vandervort
patent: 5922976 (1999-07-01), Russell et al.
patent: 5926459 (1999-07-01), Lyles et al.
patent: 5949757 (1999-09-01), Katoh et al.
patent: 5953318 (1999-09-01), Nattkemper et al.
patent: 6044091 (2000-03-01), Kim
patent: 6108305 (2000-08-01), Charny et al.
patent: 6141336 (2000-10-01), Bauchot et al.
patent: 6337851 (2002-01-01), Charny et al.
patent: 6377546 (2002-04-01), Guerin et al.
Nick McKeown, Martin Izzard Adisak Mekkittikul, William Ellersick, Mark Horowitz, “The Tiny Tera: A Packet Switch Core”, Dept. of Electrical Enginerring & Computer Science, Stanford University, Stanford, CA 94305-4070, DSP R&D Center, Corporate Research & Development, Texas Instruments, Incorp., PO Box 655474, MS446, Dallas, TX 75265.

Affiliated with

Also associated with

Rating

Method and system for sorting packets in a network does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and system for sorting packets in a network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for sorting packets in a network will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3288157