Optimizing fragment sizes in frame relay networks

[0001] 1. Field of the Invention

[0002] This invention relates to the transmission of data via frame relay networks. Particularly, it relates to fragmenting data packets to be transmitted over a frame relay network and more particularly, it relates to dynamically determining optimum fragment sizes.

[0003] 2. Description of the Related Art

[0004] When transmitting realtime and non-realtime data over the same frame relay serial interface, frame relay fragmentation is required. The frame relay implementation agreements call for fixed fragment sizes only. This convention fails to take advantage of the full bandwidth of a system.

[0005] Most layer 3 protocols such as SNA (System Network Architecture) and IP (Internet Protocol) and some layer 2 protocols such as PPP (Point-to-Point) and FR (Frame Relay) support fragmentation but they do not dynamically set the fragment sizes to maximize bandwidth utilization.

[0006] To reduce the delays in real time traffic, which generally consists of many relatively small packets, large data packets are fragmented into smaller packets, and the realtime packets are interleaved between the fragments of the data frame. This minimizes the delay in the receipt of the realtime traffic. Using dynamically determined fragment sizes when fragmenting the larger data packets reduces the amount of overhead associated with fragmentation, maximizes the amount of bandwidth used, and greatly reduces the complexity of determining the optimum fragment size.

[0007] According to the invention, data fragmentation in a frame relay network makes efficient use of bandwidth by maintaining separate queues to store realtime data and non-realtime data to be transmitted. Also, a fragment queue is implemented to hold fragments of data to be transmitted. The queues are checked in a sequence to determine first whether the realtime data queue is empty. If so, then the non-realtime data queue is checked for data to be transmitted. Existing realtime data is transmitted in successive packets when the realtime data queue is not empty. The non-realtime data is fragmented dynamically according to available transmission bandwidth.

[0014] There is an industry-wide de facto standard for fragmenting and reassembling data frames transmitted and received over circuits in a frame relay network. (FRF.12 Frame Relay Forum implementation agreement is an example.) Fragmentation is necessary when a typically low speed serial link is used to carry both realtime and non-realtime data concurrently. Examples of data types include VoFR (Voice over Frame Relay), VoIP (Voice over IP) traffic, and IP FTP (File Transfer Protocol) transactions.

[0015] To minimize delay of realtime traffic, which usually comprises many small data packets, large data packets are fragmented into smaller packets. Then the realtime packets are interleaved between the fragments of the data frame. This reduces delays in the receipt of the realtime traffic. The burden is on the frame relay layer in the receiving device to reassemble the fragmented packets and forward them to the appropriate higher layer. The current industry standard calls for using fixed data fragment sizes.

[0016] Implementing dynamic fragments is more efficient because it reduces the amount of overhead associated with fragmentation by reducing the number of fragments to be transmitted. It also optimizes the utilization of circuit bandwidth by dynamically varying the fragment sizes so as to utilize as much of the available bandwidth as possible. In addition, it greatly reduces the complexity of configuring fragment sizes for frame relay circuits.

[0017] Fragmentation is required for all circuits, i.e., end points, in a serial interface that will be used for voice and other high priority, realtime (time sensitive) data. Fragmentation is necessary to minimize the delay in queuing and transmitting voice packets and should be used for all circuits that exchange data over a link supporting voice transmission.

[0018] Fragment sizes may vary among frame relay interfaces depending on the access speed of the link, the CIR (Committed Information Rate) of the circuit, and whether a link is actually carrying voice or communicating with another router having a voice-carrying interface. Fragment sizes are not negotiated or communicated among circuits. Therefore, they may be different for two interconnected circuits. Because of the overhead associated with fragmentation, it is more efficacious to keep the size of fragments as large as possible while maintaining high quality voice communications. It is important that the round trip response time for a voice packet not exceed 250 milliseconds. Otherwise, both sides of the conversation will overlap one another. Therefore, every component in a network must minimize its portion of the delay while maximizing its efficiency.

[0019] FIG. 1 shows an environment in which the invention is useful. The components are well known in the art. FIG. 2 illustrates the position of the frame relay data link layer 11 of FIG. 1 in relation to the communications system in which it is used. In FIG. 2, a frame relay traffic shaping function 20 incorporating the invention is included as part of the circuit level priority queuing mechanism.

[0020] To support both realtime and non-realtime traffic over the same link, the invention utilizes three queues: one for realtime data, one for non-realtime data, and a fragment queue. These queues are always checked in the following order at each opportunity to transmit data: first, the realtime data queue; second, the fragment queue; and third, the non-realtime data queue. If data to be transmitted is found in the queue when it is checked, it is serviced without checking the contents of the other queues. If the queue is empty, the next queue is checked.

[0021] FIG. 3 illustrates a situation in which only non-realtime data is being transmitted. Frames are removed from the non-realtime queue 32 one at a time. The optimum fragment size is determined based on the amount of bandwidth available in the current burst window and the resulting data is sent as represented by a packet 35. Remaining data is placed on the fragment queue 33. When the next opening to send data arises, data is taken from the fragment queue 33. The optimum fragment size is again calculated and this is transmitted as packet 37. The sizes of packets 35 and 37 depend on the burst interval and the burst size.

[0022] In FIG. 4, the situation in which both realtime and non-realtime data are being transmitted is shown. Realtime data is taken from the realtime queue 31 and transmitted as packets 45 to 46. When the realtime queue 31 is empty, a frame is taken from the non-realtime queue. The optimum fragment size is determined based on the amount of bandwidth available in the current burst window and a fragment 47 is transmitted. Remaining data is placed on the fragment queue 33.

[0023] When the next opening to send data arises, data is taken from the realtime queue 31 and sent as packets 48 to 49. Data is then taken from the fragment queue 33, the optimum queue size is again calculated, and send as a packet 40.

[0024] At The fragment size is determined at each transmission occasion to maximize the use of the available bandwidth. The packets 45 to 46 together with the fragment 47 comprise a burst such as the burst interval of the packet 35 in FIG. 3. Similarly, the packets 48 to 49 together with the fragment 40 are analogous to the burst interval of the fragment 37 of FIG. 3.

[0025] The burst size and the burst interval are important when multiplexing voice and data over the same circuit to reduce the delay of the voice packets. The burst interval, Tc, is calculated as Bc/CIR, i.e., the committed burst interval divided by CIR. This determines the duration of the burst. The burst size is the number of bits the circuit is configured to send during the burst interval Tc and is calculated as Bc+Be (the committed burst plus the excess burst). Typical values for a circuit on a T1 link with a CIR of 64 Kbs (kilobits per second) might be a Bc of 64 Kb, and a Be of 0 results in a Tc of 1 second. Such a circuit will burst up to 64 Kb during a one-second period. If there is data queued for the circuit, then the 64 Kb will be sent at the beginning of the interval. The frame relay device must then wait for the next Tc, i.e., the next second, before it can send more data. This works well for file transfers and also for voice only since a voice adapter will send data to the frame relay link at a steady and predictable rate, eliminating the burst. When the circuit is handling a combination of voice and data traffic, the voice traffic could be queued for up to one second waiting for the next Tc interval. This exceeds the 250 milliseconds allowable maximum.

[0026] In the case of combined voice and data traffic, the fragment size should be adjusted as should the CIR and burst size to accommodate the combination of voice and data. The parameters include access rate of the link, the maximum number of expected calls to be carried concurrently, and the vocoder's (voice adapter) sampling and compression rate. A 60-millisecond delay in the voice traffic at the frame relay link has been found to be acceptable for voice communication. Thus, the burst interval, Tc, should be set to 60 milliseconds. With a CIR of 64 Kbps, setting Bc to 3840 bits results in a Tc interval of 60 milliseconds. Thus, the circuit can send 480 bytes (3840 bits) per each 60 millisecond burst interval. This provides a transmission rate of 8 KBps (kilobytes per second or 64 Kbps).

[0027] For example, if there are four voice calls to be carried concurrently and each call will generate one 25 byte frame every 15 milliseconds, then in a 60-millisecond interval, the voice ports will be transmitting 400 bytes per interval, i.e., 25 bytes×4 frames×4 calls per interval. This leaves 80 bytes per Tc interval to send data traffic. Therefore, the fragment size should be set to 74 bytes, viz., 80 bytes less 6 bytes of overhead.

[0028] If the maximum number of calls changes or the subscribed CIR is different from 64 Kbps, the values of Bc and the fragment size will be different. In the example, if the maximum number of voice calls changes from four to two for the circuit, the Tc interval will remain at 60 milliseconds so that Bc remains 3840 bits. The fragment size, however, will change because a larger fragment size is possible and can be sent in the same Tc interval with the voice packets. In this example, the fragment size would be set to 274 bytes (480−(25×4×2)−6).

[0029] The example shows that dynamic fragment sizes provide better implementation of the frame relay circuits because the overhead and number of fragments to be transmitted are reduced. If no voice calls are active, a steady stream of data traffic is being transmitted. With dynamic fragment sizing, the bandwidth utilized for overhead would be about seven bytes per Tc interval, one fragment header plus one HDLC boundary flag per transmission opportunity. With a fixed fragment size of 80 bytes, the overhead would amount to 42 bytes per Tc interval, one fragment header plus on HDLC boundary flag for six transmission opportunities. This would waste 6% of the bandwidth based on worst case of one or more active voice calls.

[0030] In the example with only one voice call active, a dynamic fragment size would use all the available bandwidth because the fragment size needed to fill each Tc exactly is calculated. Using a fixed fragment size of 80 bytes, 60 bytes per Tc interval would be wasted since the last full fragment would not fit in the current Tc interval. That is, 480 bytes per interval less 100 bytes of voice data leaves 380 bytes, which at 80 bytes per fragment, requires 4¾ fragments. Since partial fragments can not be transmitted, the amount of wasted bandwidth is 60 bytes (three-fourths of 80). In the example, this is 6% of the available bandwidth being wasted.

[0031] The fundamental consideration in optimizing link usage is to find the largest possible Tc interval to permit the largest possible fragment size consistent with good voice quality.

[0032] In the following description, references are made to the flowchart of FIG. 5 depicting the sequence of operations executable by a computer program. The symbols used are standard flowchart symbols recommended by the American National Standards Institute and the International Standards Organization. In the explanation, an operation may be described as being performed by a particular block in the flowchart. This is to be interpreted as meaning that the operations referred to are performed by programming and executing a sequence of instructions that produces the result said to be performed by the described block. The actual instructions used depend on the particular system used to implement the invention. Different processors have different instruction sets, but persons of ordinary skill in the art are familiar with the instruction sets with which they work and can implement the operations set forth in the blocks of the flowchart.

[0033] FIG. 5 is a flowchart of the procedure according to the invention. The procedure is entered at a terminal symbol 51. Next, by a process block 52, a transmit operate signal is initiated.

[0034] By a process block 53, the priority queuing mechanism is checked for the next packet to be transmitted. The process block 53 returns a packet from the highest priority non-empty queue. The queues are always searched in the order of realtime queue first, fragment queue next, and non-realtime queue last.

[0035] A decision block 54 determines whether a returned packet can be sent without being fragmented by comparing the packet size to the current bandwidth available in the current burst window. If the current burst window is able to handle the entire packet, the fragmentation header is added as though the packet came from the fragment queue. It is then transmitted by process block 57.

[0036] A decision block 55 determines whether the returned packet can be fragmented. Packets from the realtime queue can not be fragmented. If the frame is from the realtime queue, it is placed back on the realtime queue and processing is deferred until the beginning of the next burst window in a process block 58.

[0037] If the packet can be fragmented, the fragment size is determined by a process block 56 as the working burst size less the size of the overhead and the fragment data is moved to the transmit buffer. The remaining packet data is transferred to the fragment queue. Then the procedure continues at the process block 57.

[0038] If the packet cannot be fragmented, then a process block 58 determines when the next burst interval, Tc, begins. A delay timer is set to initiate the transmit operation at the start of the next interval.

[0039] The goal of fragmentation is to prevent queuing small realtime packets for even a short period of time. Bandwidth will be wasted if the fragment sizes are not optimal. The fragment size may vary because of the changing nature of the realtime traffic. For example, if VoFR data is being multiplexed with non-realtime data, the fragment size will vary for a given circuit depending on the number of active calls. If no calls are active, the entire burst interval can be devoted to data fragments. As the number of calls varies, the fragment size will be the number of bytes per Tc interval less the number of bytes needed for each active call.

[0040] While the invention has been particularly shown and described with reference to a preferred embodiment thereof, it will be understood by those skilled in the art that various changes and modifications in form and details may be made therein without departing from the spirit and scope of the invention according to the following claims.