Data communications

Details Data communications Data communications

1998-07-06

2002-04-09

Vu, Huy D. (Department: 2733)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S462000

Reexamination Certificate

active

06370148

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to data communications and, more specifically, to an arbiter which finds particular, but not exclusive, application in scheduling connections within a packet data switch of the space-division type.
2. Background Description
The provision of high speed switching devices is vital to modern packet switched data communications systems, such as those based on Asynchronous Transfer Mode (ATM) technology.
Many types of switching architectures have been proposed and/or implemented in high speed switches. A general review of such architectures can be found in TOBAGI ‘Fast Packet Switch Architectures for Broadband Integrated Services Digital Networks’ Proc IEEE Vol 78, No 1, pp 133-167, (1990).
In space-division type switch architectures, multiple concurrent paths are established from a plurality of inputs to a plurality of outputs, each path only being required to operate at the same data rate as an individual input or output line. One problem with this type of switch architecture is that it is generally not possible for all the required paths from each input to each output to be set simultaneously. This has the result that if two data packets arrive simultaneously at the same input and/or destined for the same output then the passage of such data packets through the switch has to be scheduled so that one of the packets must wait in some kind of buffer or queue.
Various types of queuing and buffering arrangements have been proposed, examples of which can be found in the above mentioned article.
In one possible buffering arrangement, a set of queues are placed at the inputs to the switch and data packets are transferred from the input queues to the output ports when the required input-output connection can be established in the switch. Such so-called input-queued switches require a controller or arbiter which is capable of selecting that subset of input-output combinations which can be simultaneously connected and which maximises the utilization of the output ports.
U.S. Pat. No.-5,267,235 and U.S. Pat No. 5,500,858 describe scheduling arrangements for input-queued space-division switches which provide a match between requesters, ie the input adapters of a switch, that must arbitrate for service from one of a number of servers, ie the output adapters of a switch. Each requester presents a set of requests. Requests are presented to all servers to which access is desired. Each server selects one such request and asserts a response signal stating the request selected. Each requester then selects one incoming grant response and deasserts requests to any other servers. Several iterations are performed to try to maximise the number of requests selected. In U.S. Pat. No. 5,267,235 it is proposed that the servers select requests on a random or pseudo random basis. U.S. Pat. No. 5,500,858 proposes a rotating priority approach for selection of requests by the servers and subsequently of a grant response by the requesters.
U.S. Pat. No. 5,392,401 describes an input-queued switch in which a scheduling algorithm operating on a request matrix is used in order to select input-output pairs. The algorithm operates on each matrix row in turn and selects an input-output pair with the the rule that the same input-output pair is not selected if it was selected for that row in the last iteration. Such a structure is relatively simple to implement, but the scheduling algorithm described is not optimal.
The problem in the design of scheduling algorithms of the above type is to balance the requirement for maximum switch throughput and the need to ensure that the scheduling of the switching paths is fair in the sense that, whatever the input traffic pattern, the amount of traffic allowed to pass through any particular input-output path must receive at least a defined share of the bandwidth on the respective input or output path. This is particularly important in the presence of ATM non-reserved bandwidth (NRB) traffic which can be extremely bursty.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a packet data switch of the space division type with a scheduling arrangement which is capable of handling bursty traffic with improved fairness, whilst maintaining switch throughput.
In brief, this is achieved by the provision of an improved arbiter for arbitrating requests by a plurality of first data processing units for access to a plurality of second data processing units interconnected by a switching system of a type in which at any time each first unit can only access one second unit and each second unit can only be accessed by one first unit.
The arbiter comprises a scheduler mechanism for repeatedly selecting access requests with a defined minimum probability of selecting a request for each first unit-second unit combination. Rearrangement storage means records requests selected by the scheduler mechanism.
A rearranger is provided for repeatedly selecting a set of requests recorded in the rearrangement storage means, so that only one request per first unit and per second unit is selected, using a priority mechanism which increases the probability of selection with the length of time a request is stored in the rearrangement storage means. Finally, means are provided for communicating the grant of the selected set of requests to the switching system and for deleting the selected set of requests from the rearrangement storage means.
Thus, a two-stage mechanism has been devised in which in a first stage, a scheduler is used which is fair, but which does not necessarily remove all possible input-output contention. Any contention between the input-output combinations selected by the first scheduler is resolved in a second stage by a rearranger operating on intermediate rearrangement storage which records the requests selected by the scheduler. Since the algorithm in the scheduler is not required to resolve all contention on the input and output lines, it can maintain high throughput as well as being fair. However, it nevertheless acts to reduce contention so that the subsequent resolution in the rearranger of any remaining input or output conflicts has a relatively low impact on the switch throughput.
Whilst the above described arbiter has been developed for use in controlling switching paths in a packet data switch, the possibility is not excluded that the above measures be applied in other contexts which have a similar resource arbitration requirement.
To avoid the possibility that a request remain indefinitely in the rearrangement storage, the priority mechanism in the rearranger is such as to guarantee that each request recorded in the rearrangement storage is eventually selected. This is achieved if the priority mechanism is based at least in part on the length of time any particular request has been stored in the rearrangement storage. In one embodiment, an age indicator associated with each request is stored with the request in the first storage means and the priority mechanism in the rearranger is based at least in part on the age indicator.
In a preferred embodiment, the scheduler mechanism comprises a plurality of first schedulers, one for each first unit, for repeatedly selecting one request for access by the respective first unit with a defined minimum probability of selecting a request from that first unit to access each second unit; and a plurality of second schedulers, one for each second unit, for repeatedly selecting one of the requests for access to the respective second unit with a defined minimum probability of selecting a request from each first unit to access that second unit. Requests selected by both one of the first schedulers and one of the second schedulers are recorded in the rearrangement storage means.
Second storage means can be provided for recording the request selected by the first or second schedulers and the second or first schedulers, as the case may be, can be arranged to select requests from among those stored in the second storage means.
Preferably, the first schedulers and

Affiliated with

Also associated with

Rating

Data communications does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data communications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data communications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2932137