Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-11-30
2004-09-07
Vu, Huy D. (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S389000, C370S400000, C370S401000, C370S535000, C370S536000, C370S537000, C370S542000
Reexamination Certificate
active
06788686
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to the field of communications and switching systems and in particular, to a method of packet resequencing where multiple limited-bandwidth paths are available for data transmission between a source and a destination.
BACKGROUND OF THE INVENTION
Networks provide a convenient and powerful conduit for exchanging or transferring information, e.g., data, voice, text, and video, among different communication devices connected to the network(s) such as host computers, computer terminals, multimedia workstations, fax machines, printers, servers, telephones, videophones and the like. A network typically comprises switching nodes connected to each other and to the communication devices by one or more communication links. Each link may be characterized by various configuration and operation parameters, or metrics, among which the link capacity and available bandwidth are two important ones. Information carried by the network may be in any form, but is often formatted into packets of either fixed or variable length.
When information is to be exchanged between two communication devices, a path is established within the network between the nodes (called a source node and a destination node) with which the information exchanging devices are associated. Each individual path, which is a concatenation of a number of communication links and switching devices, preserves the order of the transmitted packets and can carry only as much traffic as its link or device of the lowest capacity or available bandwidth. Such a link is often called a bottleneck link. If more than a single path can be established between the source and destination, then traffic can be split between the different paths, with the overall capacity increasing up to the sum of the bottleneck bandwidths of the available paths. However, if the traffic stream between the source and destination belongs to a single logical entity, then splitting it requires additional measures to maintain the integrity of that stream. In particular, the packet order at the destination has to be maintained the same as the original packet order at the source. The logical entity carrying multiple packets between the same pair of nodes over an extended period of time and requiring that the order of the packets be continuously maintained is referred to as a flow.
The concepts of traffic splitting and bandwidth aggregation are well known in data networking. Reincarnated as bandwidth on demand, inverse multiplexing, dynamic routing, or striping, they employ a common idea of using several lower capacity channels to implement a single logical high-capacity channel in a transparent manner. While various existing techniques and implementations differ from each other in many aspects, such as the operating environment, the splitting granularity, the applicable protocol stack layer, the loss/delay characterization of the medium, synchronous vs. asynchronous use of resources, etc., they all face the similar design challenges such as load balancing, differential delay compensation, and maintaining integrity of the data flow.
Partitioning an incoming data flow into segments of certain granularity, forwarding them along multiple paths to ensure fair load distribution and balancing between the paths, and re-assembly of the data flow at the destination are essential for achieving the goal of bandwidth aggregation. This may present less of a problem, if the lower bandwidth channels have equal capacity and are used exclusively by the demultiplexed traffic. However, if the capacity available to different individual channels is not equal or varies in time, the load balancing becomes non-trivial. Differential delay (sometimes referred to as skew) results from the fact that individual channels, which generally follow different paths, may have different propagation and processing delays. Therefore, a re-assembly engine at the receiving end has to be able to buffer each channel's data to allow for correct reconstruction of the aggregate flow. Maintaining flow integrity includes both the restoration of the original order of the data segments under normal operating conditions and maintaining the consistent order in the presence of losses and failures.
The present invention addresses the issue of packet re-ordering after splitting in a communication and switching environment which is characterized by large bandwidth-delay product value, uneven variable in time capacities of the individual paths, large variable delays, and non-zero probabilities of packet loss. It is demonstrated that under described conditions, existing techniques, based primarily on marking the order of the packets in the original flow, may not be adequate. Consequently, a new packet re-ordering method is described which satisfies the above operating requirements.
SUMMARY OF THE INVENTION
The invention presents a method to restore the original order of the packets in an end-to-end data flow after the flow has been multiplexed over a set of communication or switching paths whose available bandwidth varies significantly over time. It is observed that the prior art techniques which are based on sequentially numbering the packets in the flow and restoring the packet order with the use of the packet sequence numbers can lead to ambiguity, when the re-assembly engine a the destination node is presented with more than one packet carrying the same sequence number. This situation can occur even if no packet has been lost in transmission.
Unlike the prior art techniques, the present invention conveys the relative order of available paths, rather than the order of the transmitted packets. It guarantees that the re-assembly engine never enters the ambiguous state, provided no packet loss has occurred. Furthermore, it provides a fault-tolerant framework to ensure the preservation of the original order under specified severity of the packet losses.
To provide the basis for conveying the relative path ordering, the method of the present invention considers all possible path pairs. For each such path pair it enumerates the packet block transmissions, i.e., the sequences of packets transmitted on a selected path of the given path pair which are not interleaved by the packets transmitted on the other path of the same pair. Packet block enumeration for each path pair is performed independently and does not take into account any packets transmitted on the other paths. A packet transmitted on a given path carries a set of packet block identifications for each path pair the given path belongs to. Increasing the range of the packet block enumeration, the robustness of the method can be adjusted to an arbitrary level of packet loss tolerance.
REFERENCES:
patent: 4703475 (1987-10-01), Dretzka et al.
patent: 5127000 (1992-06-01), Henrion
patent: 5251210 (1993-10-01), Mann et al.
patent: 6226687 (2001-05-01), Harriman et al.
patent: 6246684 (2001-06-01), Chapman et al.
F. M. Chiussi et al, “Advanced Frame Recovery In Switched Connection Inverse Multiplexing for ATM”,Proceedings of 2ndIEEE International Conference on ATM, ICATM '99, Jun. 1999, pp 404-412.
E. Desmet et al, “Performance Analysis of a Resequencing Unit in a Multipath Self-Routing Switch Fabric”,ITC 14, Antibes Juan-les-Ins, France, Jun. 6-10, 1994, pp 611-621.
S. K. Biswas et al, “Connection Splitting: An Efficient Way of Reducing Call Blocking in ATM”,IEEE Global Telecommunications Conference, IEEE GLOBECOM 1998 Conference Record, Sydney Nov. 8-12, 1998, pp 2412-2418.
F. M. Chiussi et al, “Generalized Inverse Multiplexing of Switched ATM Connections”,IEEE Global Telecommunications Conference, IEEE GLOBCOM 1998, Conference Record, Sydney, Nov. 8-12, 1998, pp 3134-3140.
J. Duncanson, “Inverse Multiplexing”,IEEE Communications, vol. Apr. 1994, pp. 34-41.
H. Adiseshu et al, “A Reliable and Scalable Striping Protocol”,ACM SIGCOM '96 Conference, pp. 131-142.
P. H. Fredette, “The Past, Present, and Future of Inverse Multiplexing”,IEEE Communications, vol. 32, Apr. 1994, pp 42-46.
ATM Forum, “Inverse Multiplexing
Khotimsky Denis Andreyevich
Krishnan Santosh
Lucent Technologies - Inc.
Volper Thomas E.
Vu Huy D.
LandOfFree
Method of maintaining packet order in multipath transmission... 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 of maintaining packet order in multipath transmission..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of maintaining packet order in multipath transmission... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3186203