Electrical computers and digital processing systems: multicomput – Computer-to-computer protocol implementing – Computer-to-computer data transfer regulating
Reexamination Certificate
1999-05-04
2002-06-04
Wiley, David (Department: 2155)
Electrical computers and digital processing systems: multicomput
Computer-to-computer protocol implementing
Computer-to-computer data transfer regulating
C709S232000
Reexamination Certificate
active
06401127
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to communications over a computer network, and more particularly to the use of timing events to detect loss of a frame.
BACKGROUND OF THE INVENTION
When a frame is transmitted over a computer network there is a possibility that it will be lost. Loss of a frame can be due to a number of factors. The factors include: failure of an intermediate link; congestion in the network; failure of a bridge or router; aborted frames in the network; cyclic redundancy check (CRC) errors; etc. In order to compensate for lost frames during transmission from a source station to a destination station, over a computer network, it is a common practice to transmit an acknowledge message (ACK message) by the destination station upon receipt of an information frame, or a sequence of frames. The ACK message usually gives the sequence number of the last correctly received frame, and may be either a separate short frame or may be “piggybacked” on an information frame traveling upstream from the destination station to the source station.
Also, an acknowledgment timer (ACK timer) is operated in the source station. The ACK timer is started when the frame is transmitted onto the network (usually at the beginning of the transmission). In the event that an ACK message is not received before the expiration of the ACK timer, then it is a common practice to have the source station either retransmit the information frame, or depending upon the protocol, transmit a poll frame to the destination station. The destination station, upon receipt of the poll frame, is required to transmit a response to the source station. The purpose of the poll frame and the response frame is for the source station to learn: whether or not the destination station is still operative on the network; if the route in a source route bridged (SRB) network is still operative; retrieving the sequence number of the last correctly received frame; etc.
A problem with operating an ACK timer in the source station is that delays in the network can cause the ACK timer to expire before the source station receives an acknowledgment frame from the destination station.
Logical Link Control Layer (LLC) reliable communication was introduced; and sequence numbers for frames along with acknowledgment (ACK) messages permit establishment of reliable communication in layer
2
of the OSI communications reference model. LLC reliable communication is referred to as “LLC type 2” reliable communication. When introduced, LLC type 2 reliable communication was established between end stations on IEEE 802.5 token ring networks, and their extension with bridges to source route bridged (SRB) networks. A fixed time timing interval for ACK messages was appropriate for uncongested small SRB networks. Later, introduction of wide area network (WAN) links in SRB networks along with development of congestion problems at bridges in SRB networks lengthened the packet travel time in the networks, and lead to time-out problems in the ACK timer.
In LLC type 2 reliable communication the source station inserts a sequence number in a field of the LLC type 2 header (in an exemplary version of the IEEE standard three (3) bits are designated for the sequence number, in another exemplary version of the IEEE standard seven (7) bits are designated for the sequence number). In some point-to-point protocols the LLC TYPE 2 function in the LLC layer can read the sequence numbers of received packets, and can request retransmission of packets which are missing. The LLC TYPE 2 fields of a frame are fully disclosed by Radia Perlman in her book
Interconnections, Bridges and Routers,
published by Addison Wesley Publishing Company, in 1992, all disclosures of which are incorporated herein by reference, particularly at pages 33-34. As explained by Perlman at page 34, LLC type 2 reliable communication makes use of four packet types: I packets; RR packets; RNR packets; and, REJ packets:
“1. I (stands for “information”) is a data packet. In this case, the CTL [control] field is 2 bytes long and includes 7 bits of sequence number for the data packets being transmitted from source S to destination D, plus 7 bits sequence number for the acknowledgment for packets being received from D by S.
2. RR (“receive ready”) is an acknowledgment. It contains a sequence number and indicates that all packets with sequence numbers lower than that have been received. It also indicates that the receiver is prepared to receive more data.
3. RNR (“receive not ready”) is an acknowledgment for previously transmitted packets (with numbers lower than the sequence number in the receive sequence number field in the RNR), just like the RR. However, it also indicates that the receiver is temporarily busy and that further packets should not be transmitted until the receiver indicates it can accept new packets, by transmitting an RR.
4. REJ (“reject”) indicates that the receiver is requesting retransmission of packets starting with the number in the receive sequence number field.”
An ACK timer in the source station is started each time transmission of a sequence of packets is begun by the source station, and the ACK timer expires after an “ACK timing interval”. The source station anticipates receiving a response frame (that is, an ACK message), for example a Receive/Ready (RR) frame, acknowledging that the destination station received the preceding sequence of frames. In the absence of receipt of an RR frame during the ACK timing interval, the ACK timer expires and the source station transmits a “poll” frame in order to seek a response from the destination station to indicate whether or not the destination station is still active on the network. Reliable communication of LLC type 2 is described by Andrew Tanenbaum in his book
Computer Networks, Second Edition,
published in 1988, all disclosures of which are incorporated herein by reference, especially at pages 253-257.
However a problem arises when the link round trip time is substantially equal to, or longer than, the ACK timing interval of the ACK timer. The ACK timer may expire before the response, for example the RR frame, is received by the source station. Factors delaying the response frame comprise: the response frame is still on its way from the destination station back to the source station; the frame transmitted by the source station has not reached the destination station because it is stuck in a queue of an intermediate router experiencing congestion; the outgoing frame is still stuck in a queue in the source station and has not been transmitted because the network connected to the source station is congested; etc.
Historically, LLC type 2 reliable communication was introduced to operate over a SRB network where the delays are small and predictable. However, further developments introduced wide area network links into SRB networks having LLC type 2 reliable communication, and so introduced long and variable packet travel times. The long and variable packet travel times give rise to premature expiration of the ACK timer in the LLC type 2 reliable communication protocol.
The premature expiration of the ACK timer causes the source station to transmit a poll frame requesting a response from the destination station. The destination station then receives the poll frame and transmits an acknowledgment response to the poll frame, for example another RR frame. Accordingly, the source station receives two (2) RR acknowledgment frames in succession from the destination station, the first from the properly received sequence of information frames and the second in response to the poll frame. Receipt of two (2) RR acknowledgment frames in succession by a source station is a violation of IEEE 802.2 protocol rules. The violation of the protocol rules causes the source station to terminate the session. Termination of the session due to an inadvertent time-out of the ACK timer is a great inconvenience for users of the network. Presently, the ACK timing interval is manually configured in order to account for low bandwidth communicatio
Karkhanis Nitin
Lei Alan
Livingston Richard
Sellentin Uwe
Cesari and McKenna LLP
Cisco Technology Inc.
Johnston A. Sidney
Wiley David
LandOfFree
Adaptive timer for LLC type 2 reliable transport 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 Adaptive timer for LLC type 2 reliable transport in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive timer for LLC type 2 reliable transport in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2941973