Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1997-12-24
2001-06-12
Nguyen, Chau (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S363000, C370S412000
Reexamination Certificate
active
06246684
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of data communications networks. More specifically, it pertains to devices and methods for re-ordering data traffic units at a destination node.
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 fiber a wavelength segment on an optical fiber among others.
Physical output port: the 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 parallel physical links and appears from a routing point of view to be one link.
Logical output port: the collection of physical output ports that support the physical links of a logical link.
Data traffic unit: a portion of the original traffic stream. This may be a complete packet such as an IP data packet, a part of a packet, a collection of packets or an arbitrary number of bytes from the total stream.
Supertrunks: refers to the aggregation of physical links into larger, logical links.
Transmission Control Protocol (TCP): It is 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 number).
The traffic on the Internet is growing very fast and 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 need 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 stops 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. This is called 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 misordering of packets, but there is a problem if too much misordering occurs on a connection where the transmitter is using the fast retransmission protocol. Typically, if a packet stream of A, B, C, D gets misordered such that the destination sees A, C, D, B, then the sender may assume that B was lost when it sees the third acknowledgement for A and will retransmit B. Occasional unnecessary retransmissions are not a problem, but a systematic misordering of packets for very many connections would result in a large drop in the throughput of the network, hence misuse of bandwidth.
Other existing or future applications, or transport protocols may also suffer from packet misordering but the TCP example is the most visible at present.
One of the current solutions to the problems outlined above is to provide multiple routers or additional ports on routers. However, this solution has a serious impact on the efficiency of routing methods used to build routing tables. In fact, more routes to a destination is a less desirable solution than one bigger route.
A load balancing technique, which does not cause packet miss-ordering, has been discussed and is called “Stream Based Load Balancing”. In general, the methods rely on choosing a particular link for a traffic stream and using only that link for all its traffic A traffic stream is usually identified by the IP header (source address or source and destination address) and a hash function is used as a quick way to record and retrieve the link designated for traffic with a particular header.
Such methods can distribute traffic streams among links, but there is no prior knowledge of the rate or duration of the stream and, therefore, loads can be distributed quite unfairly. In some cases, a source address can be that of a proxy server which acts on behalf of many host machines and, in other cases, a destination address might be that of a large server which is accessed constantly by a number of source addresses.
Thus, there is a need in the industry to provide a method and a system capable of effecting low cost data traffic unit re-ordering in a network.
OBJECTIVES AND SUMMARY OF THE INVENTION
An object of the present invention is to provide a novel method and apparatus to effect re-ordering of data traffic units transmitted in a network.
As embodied and broadly described herein, the invention provides an apparatus for manipulating data traffic units transmitted in a network to reduce a level of miss-ordering of the data traffic units, said apparatus including:
an input for receiving a stream of data traffic units in a potentially miss-ordered condition;
a re-ordering queue storage medium for receiving the data traffic units, said re-ordering queue storage medium providing means for:
a) altering an order of the data traffic units on a basis of a first recognizable characteristic of each data traffic unit for reducing a level of miss-ordering of the data traffic units;
b) controlling a residence time of each data traffic unit in said reordering queue storage medium;
an output for releasing data traffic units from said re-ordering queue storage medium.
In a most preferred embodiment, the apparatus according to the present invention can be implemented on a router. Such router comprises a plurality of interfaces supporting a number of individual physical links. The router also includes a processor and a memory that contains a program element executed by the processor for regulating the operation of the router. A data bus interconnects the interfaces with the processor and the memory to provide a medium over which data and control signals can be exchanged. The novel feature of the router resides in its ability to re-order data traffic units that have been placed in an out of order condition at some earlier point in the transmission. This miss-ordering may result from individual data traffic units that were originally part
Chapman Alan Stanley John
Kung Hsiang-Tsung
Nguyen Chau
Nguyen Phuongchau Ba
Nortel Networks Limited
LandOfFree
Method and apparatus for re-ordering data packets in a... 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 apparatus for re-ordering data packets in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for re-ordering data packets in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2532143