Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-12-18
2003-06-03
Nguyen, Steven (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395400, C709S241000
Reexamination Certificate
active
06574230
ABSTRACT:
RELATED APPLICATIONS
U.S. patent applications entitled “Supertrunking for Packet Switching” and “Flow-Level Demultiplexing within Routers” both by Almulhem et al, both filed on the same day as the present application, and both assigned to the assignee of the present application, disclose and claim subject matter related to that of the present invention and are herein incorporated by reference.
FIELD OF THE INVENTION
This invention relates generally to data routing systems and more specifically to data packet routing systems over multiple physical links.
BACKGROUND OF THE INVENTION
The following paragraphs give definitions of terms used throughout this document.
Physical link: a single point-to-point (PPP) serial transmission link between two nodes in the network (such as between two routers or between a router and a host machine). The implementation of a serial link may take various forms such as an optical fibre or a wavelength segment on an optical fibre, among other options.
Physical input/output port: the input/output port of the router that supports one physical link.
Logical link: a point-to-point traffic path between two routers that is composed of multiple physical links and appears from a routing point of view to be one link.
Logical input/output port: the collection of physical input/output ports that support the physical links of a logical link.
Supertrunk: the aggregation of physical links into larger, logical links.
Transmission Control Protocol (TCP): a library of routines that applications can use when they need reliable network communications with another computer. TCP is responsible for verifying the correct delivery of data from client to server. It adds support to detect errors or lost data and to trigger reconstruction until the data is correctly and completely received.
Internet Protocol (IP): a library of routines that TCP calls on, but which is also available to applications that do not use TCP. IP is responsible for transporting packets of data from node to node. It forwards each packet based on a four-byte destination address (the IP address).
There has been an incredible increase in demand for bandwidth within communication routing systems over the past few years. This increase is particularly pronounced when considering the increase in data networking information transferred within these systems directly associated with the expanding popularity of the Internet. Soon the traffic rates needed between router pairs will be higher than the serial link transmission technology available. Currently, the highest transmission rate is 9.6 Gb/s, (on a single wavelength) but 2.4 Gb/s is much more commonly available. Purchasers of routers are already demanding 2.4 Gb/s links and it is expected that within a short time, some routes will require multiple physical links.
There are other reasons why multi-link routes are attractive. In situations where routers are clustered in close physical proximity, the use of multiple links might allow the interconnect to be multiple low cost links rather than single high cost connections. Another reason is that the application of the multi-link approach might also be a fast way to provide higher rate ports on existing routers. Yet another reason is that the use of multiple links allows more granularity of growth than the large steps in the transmission network and so may allow savings in bandwidth costs. Finally, another reason is that multiple links can allow for redundancy to cover link failure without requiring the spare link to cover the whole bandwidth of the route.
When using multiple links between two routers, it is a requirement that the total bandwidth be used efficiently. That is to say, the traffic offered must be spread over all available links, hereinafter referred to as load balancing. It would not be acceptable to have one link under utilized while traffic is queued on another. This suggests that packets from any source can be delivered over any link to any destination. In fact, because of the bursting nature of the traffic, allocating links statically to particular sources or destinations would result in inefficient use of the total available bandwidth.
When traffic streams are spread over multiple links, successive packets from a particular flow (for example, a TCP connection between two IP hosts) can travel over different lengths and may arrive at the destination out of order. The variability of delay can be caused by different path lengths or different congestion levels on the paths, as well as the normal indeterminacy introduced by queuing and scheduling. The TCP can accommodate some mis-ordering of packets, but there is a problem if too much mis-ordering occurs on a connection where the transmitter is using the fast retransmission protocol.
To combat this mis-ordering of packets, a sorting function that places, the packets in the proper order is utilized within routers implemented with a supertrunking capability. In cases that multiple data streams are routed to a single router via the same supertrunk, incoming packets from different data streams may be mixed with incoming packets of a plurality of other data streams. In such cases, each incoming data stream is sorted independently and assigned a memory location for the buffering of the packets.
A key problem that occurs within a router that receives packets from a plurality of data streams simultaneously over a single supertrunk is the scheduling of the packets corresponding to the different data streams for service after being sorted. Only a limited number of packets can be serviced at a time. Hence, a decision procedure is required to select which of the sorted data streams to service a packet from during each servicing period. To maintain the efficiency gained by supertrunking data packets, this scheduling procedure must be sufficiently effective so as to not significantly diminish the advantages gained through use of supertrunks. To maintain efficiency, such a procedure should allow data streams with considerable numbers of incoming packets to be serviced frequently while still allowing data streams with few incoming packets to get a minimum level of service.
SUMMARY OF THE INVENTION
It is an object of the present invention to overcome the disadvantages of the prior art and, in particular, to provide an apparatus and method for efficiently scheduling the service of packets within data packet communication systems.
According to a first broad aspect, the present invention provides a scheduling apparatus capable of being coupled to a plurality of memory buffers, each memory buffer capable of inputting data packet units and outputting data packets corresponding to a single data stream, the scheduling apparatus scheduling the outputting of the data packets from the memory buffers with use of scheduling logic; and wherein the scheduling logic operates, if a first data packet unit from a first data stream is input to a first memory buffer, to determine whether a first outputting parameter corresponding to a front packet within the first memory buffer is met and to output the front packet from the first memory buffer if the first outputting parameter is met.
In a preferable embodiment, the present invention provides a scheduling apparatus according to the first aspect, wherein the scheduling logic further operates to maintain a counter corresponding to each memory buffer, to select a round-robin (RR) memory buffer during each inputting of a data packet packet, each memory buffer cyclically being selected as the RR memory buffer, and incrementing the counter of the RR memory buffer if an incrementing parameter is met; wherein the scheduling logic further operates, if the first outputting parameter is met, to reset the counter of the first memory buffer; and wherein the scheduling logic further operates, if the first outputting parameter is not met, to determine whether any memory buffers are starving by checking if any counters exceed a predetermined maximum value; if a starving memory buffer is found, to determine whether a starvation outputting parameter, corr
Almulhem Abdulaziz S.
Depelteau Gary M.
Vincent John E.
Nguyen Steven
Nortel Networks Limited
LandOfFree
Scheduling technique for delayed queue service does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scheduling technique for delayed queue service, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheduling technique for delayed queue service will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3136917