Routing arbiter for data network switching

Details Routing arbiter for data network switching Routing arbiter for data network switching

1999-05-27

2004-08-03

Vo, Tim (Department: 2733)

Electrical computers and digital data processing systems: input/

Access arbitrating

C710S316000, C710S317000, C709S245000

Reexamination Certificate

active

06772256

ABSTRACT:

BACKGROUND OF THE INVENTION
An apparatus commonly known to persons skilled in the art of data communications as a data network switch, is used to interface between a plurality of network segments. The apparatus works in a way that allows a plurality of simultaneous independent data transactions on different network segments, one transaction on each segment, while concurrently enabling a plurality of data transmissions between segments whenever such transmissions are requested. A central routing controller receives routing requests from the plurality of segments and attempts to connect the requesting segment to the requested destination segment when the request is routable. A request is considered routable when both the requesting source segment and the requested destination segment are idle, which means neither is engaged in data communications with any other segment at the time of the route change. In the prior art, the requesting segments send their routing requests to a queue, which lines-up the requests and attempts to establish the requested route if both the requesting source and the requested destination are idle. In case a routing request of the first request in line is not readily available this request and all other subsequent requests in the queue must wait until the requested route becomes available. This case is called a Head of Line Blocked route case and is the most undesirable case as it delays all subsequent routing requests in the queue. The present invention describes a routing arbiter which optimizes the process of routing of available routes and minimizes Head of Line routing blockage.
The routing arbiter described herein maintains a list of all pending route requests and receives information of all idle sources and destinations. Whenever a request for routing exists when both the destination and the source are simultaneously idle, the arbiter grants permission to execute that request, where the criteria for such grant is not the order of the requests within the queue but rather a set of programmable priority parameters. The uniqueness of this invention is in the way it processes the pending requests. It does not do it on an individual basis, handling one request at a time, but instead processes all the pending requests simultaneously.
SUMMARY OF THE INVENTION
This invention describes a device intended to solve “Head of Line Blocking” problems associated with routing queues in computer data network switches. Such queues typically store all pending routing requests, and processes them in the order of their arrival. If the request at the head of the queue can not be processed and the requested routing cannot be granted because of a busy requested source or destination at the time of process, all other pending request cannot be processed until the head of the queue is cleared. All pending requests are processed simultaneously, thus there is no “Head of Line” in the queue. Instead the decision and the selection of the request to be granted at the time of processing is based on a programmable priority scheme. Further, all pending requests are compared simultaneously with all idle sources and destinations. A request is considered routable if both the requesting source and requested destination in that particular request match with an idle source and an idle destination. If more than one request is routable at the time of the processing, the routable request with the highest priority is granted. This priority scheme equates to a virtual prioritized queue. Several virtual queues can exist side by side. Priorities can be applied within each virtual queue and also between the queues. If desirable, more than one request may be granted in any single processing period. The process of examination of all the pending routing requests repeats itself in a cyclic fashion, once per each clock cycle.


REFERENCES:
patent: 4754451 (1988-06-01), Eng et al.
patent: 4866701 (1989-09-01), Giacopelli et al.
patent: 4899334 (1990-02-01), Shimizu
patent: 5179552 (1993-01-01), Chao
patent: 5179558 (1993-01-01), Thacker et al.
patent: 5724352 (1998-03-01), Clooman et al.
patent: 5761440 (1998-06-01), De Marco et al.

Affiliated with

Also associated with

Rating

Routing arbiter for data network switching does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Routing arbiter for data network switching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Routing arbiter for data network switching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3279089