Multiplex communications – Fault recovery – Bypass an inoperative switch or inoperative element of a...
Reexamination Certificate
1999-11-04
2003-08-19
Chin, Wellington (Department: 2664)
Multiplex communications
Fault recovery
Bypass an inoperative switch or inoperative element of a...
C370S216000
Reexamination Certificate
active
06608813
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to the field of packet data networks, and, more particularly, to the application of inverse multiplexing in packet switching systems.
2. Description of the Related Art
Inverse multiplexing has long been known as a technique to implement a single high-capacity logical communication channel by using several lower-capacity communication channels, where distribution and aggregation of the traffic flow to and from individual communication links is transparent to the applications. A variety of such inverse multiplexing schemes for packet data networks were proposed and implemented such as incremental bandwidth on demand (BONDING), Multilink Point-to-Point protocol (Multilink PPP), Packet Striping and Inverse multiplexing for ATM (IMA), for example. The aforementioned techniques primarily are related to different operating environments, have different objectives, and can be classified in respect to splitting granularity, synchronous vs. asynchronous use of resources, and methods of differential delay compensation. However, aggregation of communication bandwidth through splitting, recombination, and sequencing is a feature that they have in common. Other common features include: operating on the point-to-point link and sensitivity to packet loss. The former means that the underlying lower capacity channels are in fact point-to-point links which do not contain contention points associated with switching nodes and, therefore, can be characterized by predictable delay and low delay variation. Furthermore, the splitting and recombination scheme may rely on the exclusive use of those links for the inverse multiplexing purposes. The latter implies that loss of just a single packet within the boundaries of the inverse multiplexed logical channel may cause loss of synchronization and lead to the necessity for some number of successfully delivered packets to be discarded as well. Discarding of the successfully delivered packets, in turn, is associated with the need to retransmit the packets later, causes reduction of throughput, and is a contributing factor of network congestion.
In recent years, it has become obvious that point-to-point inverse multiplexing does not address all the needs of modern packet data networks. While the market demands switches that are capable of terminating trunks of ever increasing bandwidth, the issue of scaling the port capacity becomes critical. Inverse multiplexing can potentially provide an economical way to interface the new higher-rate trunks with existing switches (or switching networks) that have ports operating at a lower rate.
However, the principles of inverse multiplexing applicable in the point-to-point environment can not be directly translated into the switching systems. First, in this case, splitting has to distinguish between multiple components of the incoming packet flow which are destined to distinct output ports of the switching system and carry different Quality of Service (QoS) requirements. Second, the presence of buffers within the boundaries of the logical link make the differential delays unpredictable and highly variable, as well as is associated with inherent probability of packet loss.
An improved inverse multiplexing scheme called switched connection inverse multiplexing, which presents a significant qualitative advancement over conventional point-to-point inverse multiplexing, has been proposed recently. This new switched connection inverse multiplexing scheme applies to any packet data network, operates on individual established network connections or flows, and allows inverse multiplexed packets of the selected network connections over network segments which contain switching nodes. The scheme is generally directed to a packet switching system including a plurality of input controllers and a plurality of output controllers attached to a core switching network. Each input controller and each output controller terminates a communication link that can carry a plurality of network connections (NCs). Each NC is received at a unique input controller and is routed through the core switching network to a unique output controller. The core switching network provides a plurality of switching paths between each input controller and each output controller such that the bandwidth of each individual switching path is smaller than the data rate of the communication links terminated by a controller, but the aggregate bandwidth of all the switching paths provided between a given pair of input and output controllers is approximately equal to the data rate of the terminated communication links.
The packet switching system processes NC requests for switched connections between the incoming communication links and the outgoing communication links. Non-multiplexed NCs are established through the core switching network in which the entire bandwidth of the NC is carried by a single switching path. Inverse multiplexed NCs are established through the core switching network in which the bandwidth of the NC is partitioned among a plurality of switching paths using weight values to determine the fraction of bandwidth to be allocated to each switching path, each portion of the NC traffic taking a separate switching path being referred to as a subconnection.
Every packet of an inverse multiplexed NC is assigned an inverse multiplexing tag, which contains a sequence number consistent within the subconnection, i.e., it reflects the number of packets belonging to every given inverse multiplexed NC transmitted over the same switching path, and a next path pointer, i.e., the identification of the switching path on which the following packet of the same inverse multiplexed NC will be transmitted. To enhance robustness of the scheme, the inverse multiplexing tag may optionally contain one or more i-th previous next path pointers, i=1, . . . , n, the i-th previous next path pointer meaning the value of the next path pointer that has been carried by the i-th preceding packet belonging to the same subconnection.
The switched connection inverse multiplexing scheme successfully translates the resource aggregation principles from point-to-point link bandwidths to switch port capacities in a switching system. However, the issue of confronting packet loss remains critical. To eliminate preventable packet losses within the inverse multiplexed switching path and to transfer them to the input controller before the actual splitting point, the switched connection inverse multiplexing scheme employs ubiquitous back pressure applied through all stages of the core switching network from the output controller to the input controller. Still not all types of packet losses can be excluded by this method. If the back pressure to the input controller can not be applied or is ineffective at the specific location within the core switching network where loss can occur, or if packet losses are associated with random uncontrollable factors, such as the electrical glitches, packet memory faults, or interface errors, the packet re-sequencing engine may lose synchronization and be unable to restore the original order of the inverse multiplexed NC packets. In particular, if the number of packets from the same subconnection of the given inverse multiplexed NC which have been lost in a row exceeds n, i.e., the number of previous next path pointers contained in the inverse multiplexing tag, then restoring the packet order of the given inverse multiplexed NC becomes impossible.
Therefore, there is a need for improved methods and devices which address these and other shortcomings of the prior art.
SUMMARY OF THE INVENTION
The present invention generally is directed to a packet switching system which provides a fault tolerant extension of the switched connection inverse multiplexing scheme. In a preferred embodiment, the packet switching system incorporates a core switching network including a plurality of input and output ports and a plurality of switching paths between the input and output ports. Prefe
Chiussi Fabio M.
Khotimsky Denis A.
Krishnan Santosh
Agere Systems Inc
Chin Wellington
Fox Jamal A.
LandOfFree
Method and apparatus for achieving fault tolerance in packet... 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 achieving fault tolerance in packet..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for achieving fault tolerance in packet... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3102499