Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1998-06-09
2002-04-16
Chin, Wellington (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S231000
Reexamination Certificate
active
06373818
ABSTRACT:
FIELD OF INVENTION
The present invention relates to high speed data networking and, more particularly, to the adaptation of legacy window-based Data Link Control (DLC) protocols to modern Rate Based link accesses such as Adaptive Committed Information Rate over Frame Relay Network.
BACKGROUND ART
The present invention makes references to the following standards:
ANSI T1.617, T1.618 and T1.606 (addendum); and
ITU-T Q933 and Q922, 802.2
The present application is also based on another patent application whose title is “Method for adapting committed information rate over frame relay switched network” by Esteve et al. filed on the same date.
The terminology that is used throughout the description is as follows:
FR: Frame Relay: A High speed switched network, with statistical multiplexing.
FH: Frame Handler concerns the function of FR layer
2
that handles frames switching in the network.
TE: Terminating Equipment is a gateway from FR, it handles upper layer
2
and layer
3
functions.
AD: Access Device, a FRAD usually converts LAN traffic into FR traffic and so forth.
TDM: Time Division Multiplexing, it is used for splitting bandwidth in timely slots.
ISDN: Integrated Services Digital Network, it is another high speed network, with TDM.
TA: Terminal Adapter, it is used to convert leased/dial line into a channel (FR, ISDN).
Bc: Committed Burst size, it represents the number of bytes that can be sent in a burst according to CIR.
Be: Excess Burst size, it represents the additional bytes of Bc that may or may not be carried by the network.
Tc: Period over which Bc is sent its value is generally computed according to the formula CIR=Bc/Tc.
CIR: Committed Information Rate which represents a bit rate that is subscribed from a carrier.
V_CIR: Variable CIR which is the classical recommendation according to the standard organizations as mentioned above.
A_CIR: Adaptive CIR is the environment in which the present invention is implemented.
ARB: Adaptive Rate Base represents the ability to perform flow control by adapting a transmission rate.
PVC: Permanent virtual channel is a leased end to end path through the FR network.
DLC: Data Link Control, associated with OSI layer
2
, provides link access functions for upper layers. 802.2 DLC is also referred as a LLC (logical link control) as it is mostly used to access logical links or virtual channels.
DLCI: Data Link Control Identifier which identifies a PVC over a given hop.
ECN: Explicit Congestion Notification where a bit is piggy-backed in FR Q922 header to notify of a congestion (which happens generally in the FH function). The ECN uses the pair FECN/BECN of congestion management.
FECN: Forward ECN which is generally set by FH function in a frame that passes through a congested node and sends a signal to the receiving or destination FRTE, advising it to slow down the receipt of information.
BECN: Backward ECN. Flows on the way back from which the congestion was experienced to the source FRTE of the traffic in order to pace it down.
Bottleneck: The node or the line in the network that limits the throughput over a PVC. Both the bottleneck location and its throughput are subject to change overtime.
LAN: Local Area Network, it interconnects station within a single plant (campus). Tendency is to go from the old shared media model to a switched model for higher throughput.
WAN: Wide Area Network. Everything from the most common modem in a PC to Serial Optical Network, it interconnects stations and LANs over long distance serial links.
Most telecommunication protocols use window based mechanisms for doing their flow control (for instance with protocols SNA, TCP). Transporting Windows over High Speed lines requires huge window sizes and control becomes very poor.
Without an Adaptive Rate Based or A_CIR, when a node any where in the network cannot obtain the expected throughput owing to the FRTE having a fixed CIR, a logical bottleneck forms.
Thus, its throughput (TH) limits the FRTE traffic. The minimum size of the window (in bytes) at the FRTE that is required to keep the bottleneck busy is Wmin=TH*TAT, wherein TAT stands for the Turn Around Time of the network which is caused by propagation, store_and_forward effect and encoding delay.
For instance, it takes a window of 100*2 Kbytes frames to keep a 100 Mbps link busy over 1000 miles.
Most of that window will end up being queued in the bottleneck. At high speed, the bottleneck latency and memory requirements become unacceptable. In consequence, the window size decreases, which in turn causes a poor utilization of the link. This case of implementation according to the prior art is shown in FIG.
3
.
This leads to two consequences: firstly, the window based protocols are not efficiently transported over high speed lines unless heavy multiplexing takes place, and secondly, modern protocols rather use ARB mechanisms.
When window_based protocols are transported by a Frame Relay network, an Adaptive Committed Information Rate (A_CIR) can be used as an ARB so that the network logical bottlenecks move to the Terminating Equipment (TE). Provided that, the CIR queue in the TE is now the place were the huge unwanted queuing takes place. This is shown in FIG.
4
.
The problem this invention addresses is determining how to keep the network busy while protecting CIR queues in the Terminating Equipment, in the case of high speed FR lines with adaptive CIR.
REFERENCES:
patent: 5130986 (1992-07-01), Doshi et al.
patent: 5592627 (1997-01-01), Burt et al.
patent: 5764625 (1998-06-01), Bournas
patent: 5995486 (1999-11-01), Iliadis
patent: 0454364 (1991-10-01), None
Perros et al., Semaphore Queues: Modeling Multilayered Window Flow Control Mechanisms, IEEE, pp. 309-317, 1990.*
Suk et al, Performance Comparison of Two Window Flow Control Schemes with Admission Delay, ieee, pp. 892-896, 1990.*
Gong et al., Study Of A Two-Level Flow Control Scheme and Buffering Strategies, IEEE, pp. 1224-1233, 1994.*
“Congestion Control Strategies for Mixed X.25/Frame Relay Networks” by A.J. Vernon, T. Jawor, S. Rabie, D. Whiting & H. Badran XP000438768, Jan. 5, 1994, Bell-Northern Research, Ontario Canada.
“A Taxonomy for Congestion Control Algorithms in Packet Switching Networks” by C. Yang and A. Reddy XP000526590, 8302 IEEE Network, Jul./Aug. 1995 #4, New York US, pp 34-45.
“An Effective Mean Rate Policing Scheme: Moving Ceiling Scheme” by J. Park et al, XP000622956, Globecom'95, IEEE, Nov. 14-16, 1995, vol. 2, pp 71-75.
Brassier Rene
Esteve Denis
Marce Jean-Pierre
Thubert Pascal
Chin Wellington
Duong Frank
Frisone John B.
LandOfFree
Method and apparatus for adapting window based data link to... 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 adapting window based data link to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for adapting window based data link to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2865917