Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
1998-12-18
2003-07-01
Kizou, Hassan (Department: 2662)
Multiplex communications
Data flow congestion prevention or control
C370S392000, C370S394000, C370S395300, C370S400000, C370S902000, C709S241000
Reexamination Certificate
active
06587431
ABSTRACT:
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.
Therefore, when utilizing a supertrunk to transfer data between two routers, it is important to establish a routing system that comprises both an efficient load balancing function to distribute the individual packets among the physical links and an effective sorting function to handle mis-ordered data packets. Another key consideration, is the compatibility of the protocol headers, corresponding to the data packets after having load balancing information attached, with the networks comprised within the physical links of a supertrunk. Each of the physical links of a supertrunk may be implemented with a series of connections within a series of networks with different protocols. The individual data packets traversing these physical links must have a header recognized by these different networks without modifications being required at the network level.
Hence, a general implementation of a routing system is required that supports supertrunks and, as a result, provides more efficient use of bandwidth within a series of physical links. This supertrunk routing system should not make significant changes to the overall operation of the current routing systems or networks within the physical links, but should allow individual IP packets from a single IP stream to be transferred from one router to another via different physical links.
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 increasing the efficiency of data packet communications.
According to a first aspect, the present invention provides a forwarding node capable of operation within a router that transfers digital data with a plurality of other routers within a packet routing system, the forwarding node comprising: a load balancing device that, when input with individual packets of a data stream, reads a logical output port corresponding to the data stream, assigns each of the individual packets of the data stream to a physical output port within the logical output port based upon physical link criteria, encapsulates the individual packets with a first routing header that comprises a data stream identifier, a packet sequence identifier, and a physical output port identifier, and outputs the packets to their assigned physical output ports; and a packet sorting device that, when input with encapsulated packets, re-orders the packets into the proper order with use of a sorting algorithm utilizing the packet sequence identifiers and outputs a data stream corresponding to the re-ordered packets.
According to a second aspect, the present invention provides a router capable of operation within a packet routing system that transfers digital data between a plurality of the routers, the router comprising: a route controller; a rotator space switch; at least one first forwarding node, coupled to both the route controller and the rotator space switch, comprising a load balancing device that, when input with individual packets of a data stream, reads a logical output port corresponding to the data stream, assigns each of the individual packets of the data stream to a physical output port within the logical output port based upon physical link criteria, encapsulates the individual packets with a first routing header that comprises a data stream identifier, a packet sequence identifier, and a physical output port identifier, and outputs the packets to their assigned physical output ports; at least one second forwarding node, coupled to both the route controller and the rotator space switch, that is arranged to operate as a physical output port for outputting encapsulated packets to at least one transmissio
Almulhem Abdulaziz S.
Chapman Alan S. J.
Vincent John E.
Elallam Ahmed
Kizou Hassan
Nortel Networks Limited
LandOfFree
Supertrunking for packet 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 Supertrunking for packet switching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Supertrunking for packet switching will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3093408