JP4459620B2 - System and method for token-based PPP fragment scheduling - Google Patents

Description

【Technical field】
[0001]
The present invention generally relates to multilink packetized data transmission.
[Background]
[0002]
For example, more and more data is communicated between a plurality of computers such as a server and a user computer using an Internet protocol (IP) -based principle. One example of a protocol that can be used to carry IP-based data is the Point-to-Point Protocol (PPP) that forms IP packets. That is, IP data packets can be communicated using PPP.
[0003]
PPP can be used not only to communicate IP packets over the wired portion of the Internet, but is not limited to, for example, code division multiple access (CDMA) technology, GSM, wideband CDMA It can also be used to communicate data via a wireless transmission path to user computers using wireless communication principles such as, and other wireless technologies. Such a communication scheme is disclosed in a co-pending provisional patent application (Application No. 60 / 335,680) owned by the assignee of the present invention and incorporated herein by reference. Yes.
[0004]
Increase the bandwidth (ie, increase the amount of data per unit time that can be communicated between the transmitter and the receiver) and wait as disclosed in the above referenced patent application. To reduce time, the IP packet being transmitted can be broken into fragments. Here, this fragment is sent in parallel via a number of links established between the transmitter and the receiver. This fragment is recombined at the receiver. This fragment is brute force assigned to the link. That is, the first fragment is sent on the first link, and the second fragment is sent on the second link.
[0005]
The present invention critically observes that brute force assignment of fragments results in lost fragments. To illustrate, consider that the number of links is generally equal to the number of fragments per packet. Further, consider that the last fragment of each packet is generally smaller than the others that represent reminders. In the presence of brute force fragmentation (also called brute force scheduling), it essentially means that the last, smallest fragment of each packet is always scheduled on the same link, so It means that it will be provided while accumulating and will gradually deteriorate.
[0006]
Smaller fragments can reach the receiver first, despite having a higher sequence number than the previous fragment in the packet. Here, it is held until the remaining fragment of this packet arrives. Even if the effects of the links in use are not accumulated, it is not a problem because the system typically keeps fragments that arrive early in a limited period of time. However, as mentioned above, when using brute force scheduling with a number of links that is a multiple of the number of fragments per packet and the last fragment smaller than the other fragments, the effect in use is cumulative. To do. As a result, flushed retained fragments, further after the elapse lost, the smallest fragments, the difference in arrival time for the other fragment of a packet, Ru cormorants exceed the applied data retention time in this system. Such lost fragments to cod also regular loss of packets, the system is inaccurate in that the loss of packets by congestion.
[0007]
These critical observations were made and the following solutions were provided.
[Patent Document 1]
US Patent Application No. 60 / 335,680
DISCLOSURE OF THE INVENTION
A method for communicating data arranged in a packet includes providing a plurality of links between a transmitter and a receiver and assigning a capacity indicator, such as a token, to each link .
[0008]
Each packet is divided into a plurality of fragments. This capacity indicator (e.g. token) is used to associate the fragment with the link. In particular, each fragment is associated with the link with the highest remaining capacity, as indicated by the token at the time the fragment was scheduled. In this way, load balancing between links is achieved, reducing the possibility of premature fragment arrival at the receiver and the possibility of concomitant fragment loss.
[0009]
In a preferred and non-limiting embodiment, when a fragment is assigned to a link, the token associated with the link is reduced by an amount indicating the size of the fragment. In essence, the link token represents the current capacity recognized by the system.
[0010]
In another aspect, a transmitter that transmits packetized data in the IP protocol includes a controller. The controller receives a packet of data and segments the packet into fragments for transmission over multiple wireless links. Each fragment is scheduled for transmission by one of the wireless links based on a non-brute force assignment policy. The current policy can be referred to as a load balance policy.
[0011]
In another aspect, a system for packetized data transmission includes means for partitioning a data packet into fragments and means for scheduling fragments among a plurality of communication links based on the currently recognized capacity of the link. Including. Means are provided for transmitting packet fragments in parallel with each other over the link.
[0012]
The details of the invention, together with its construction and operation, can be best understood by referring to the drawings, wherein like reference numerals refer to like parts.
BEST MODE FOR CARRYING OUT THE INVENTION
[0013]
This application claims the priority of US Provisional Patent Application “Method And System For Aggregating Multiple Wireless Communication Channels For High Data Rate Transfers” (Application No. 60 / 335,680, filed Oct. 25, 2001) (Patent Document 1). Insist.
[0014]
First, a general communication system 10 is shown in FIG. The system includes one or more satellites that facilitate data communication between one or more mobile stations 14 (which can be performed on a moving platform) and one or more land-based gateway stations 16. 12 can be included. This system 10 can be implemented according to the well-known Globalstar system. While FIG. 1 shows that satellite communications can be used, the multilink packetized data communication principles disclosed herein are generally applicable to any multilink packetized data communication system, eg, multi-ISDN bearer channel. It will be understood that In an exemplary embodiment, this packetized data principle uses the Internet Protocol (IP) principle, and further uses, but is not limited to, the Point-to-Point Protocol (PPP) principle. .
[0015]
Returning to the description of the exemplary and non-limiting system 10 shown in FIG. 1, a soft transfer (handoff) process between satellites 12 and even between each of a plurality (eg, 16) beams transmitted by each satellite. Provides code division multiple access (CDMA) technology, which is unbroken communication via spread spectrum (SS). The presently preferred SS-CDMA technology is similar to the TIA / EIA Interim standard “Mobile Station-Base Station Compatibility Standard for Dual-Mode Wideband Spread Spectrum Cellular System” TIA / EIA / IS-95, July 1993 . On the other hand, other spread spectrum and CDMA techniques and protocols, or even time division multiple access (TDMA) systems can be applied. In addition to the CDMA portable system described in the Telecommunications Industry Association / Electronic Industries Association (TIA / EIA) standard IS-95, other usable radio systems include the AMPS & CDMA combined system described in the TIA / EIA standard IS-98. Is included. The International Mobile Telecommunications System 2000 / Universal Mobile Telecommunications System, that is, the IMT-2000 / UM standard also describes other communication systems, such as wideband CDMA (WCDMA), cdma2000 (e.g. 3x or MC standard, etc.), or what is commonly referred to as TDSCDMA. The GSM principle is also used. Satellite-based communication systems also make use of the above or similar known standards.
[0016]
As shown in FIG. 1, each mobile station 14 may include one or more controllers 18 that control a plurality of modems 20 that communicate with the satellite 12 along their respective links 22. In addition, the gateway station 16 may include one or more controllers 24 that control a plurality of modems 26 that communicate with the satellite 12 along their respective links 28.
[0017]
This mobile station 14 is capable of operating in full duplex mode, eg via an L-band RF link (uplink or return link) and an S-band RF link (downlink or forward link). It should be understood that communication is through return satellite transponders and forward satellite transponders. This return L-band RF link operates within a frequency range of 1.61 GHz to 1.625 GHz, and a bandwidth of 16.5 MHz, and is packetized digital voice signal and / or data according to a suitable spread spectrum technique. It can be modulated by the signal. This forward S-band RF link operates within a frequency range of 2.485 GHz to 2.5 GHz and a bandwidth of 16.5 MHz. This forward RF link may also be modulated with packetized digital voice and / or data signals according to spread spectrum techniques. The 16.5 MHz bandwidth of the forward link is partitioned into, for example, 16 beams with 13 sub-beams efficiently forming 208 FDM channels. Furthermore, about 128 code channels for one user assigned to each forward link code channel, pilot signals and the like are accommodated. The return link may have different bandwidths, and a given mobile station may or may not be assigned to a different channel than the channel assigned to the forward link.
[0018]
In addition, the gateway station 16 may be, for example, a fully duplexed C-band RF link (forward link (to satellite), return link (from satellite)) operating in a frequency range generally exceeding 3 GHz, preferably in the C-band. ) To communicate with the satellite 12 via. The C-band RF link carries the communication feeder link bi-directionally and carries satellite commands to the satellite and telemetry information from the satellite. The forward feeder link operates in the 5 GHz to 5.25 GHz band. On the other hand, the return feeder link operates in a band from 6.875 GHz to 7.075 GHz. As an example, thousands of full duplex communications occur through a given one of the satellites 12. Depending on the characteristics of the system 10, two or more satellites 12 each carry the same communication between a given mobile station 12 and gateway station 16. However, it should be understood that the frequencies, bandwidths, and everything described herein are representative of a particular system. Other frequencies and frequency bands can also be used without changing the principles discussed herein. As an example, the feeder link between the gateway and the satellite is a frequency band other than the C band (about 3 GHz to about 7 GHz), for example, the Ku band (about 10 GHz to about 15 GHz) or the Ka band (about 15 GHz or more). ) May be used.
[0019]
As shown in FIG. 1, a non-limiting mobile station 14 communicates using an Ethernet link, a Bluetooth-based wireless link, or a wireless transfer system based on the 802.11 (IEEE) standard protocol. It can be connected to the data network 30 via a link 32. One or more user computers 34 can be connected to the data network 30. The system also includes handheld or laptop computers with wireless or wired modems, PDAs, facsimiles, and other devices that transfer data to the user, including but not limited to gaming devices, paging devices, etc. Assumes the use of other data transfer devices. In either case, the data network 30 can be a LAN or other known network, can include a data router, and can be connected to other networks.
[0020]
Also, as shown in FIG. 1, the gateway station 16 communicates with the gateway router 36 according to principles known in the art. The gateway router 36 in turn communicates with a ground controller 38 such as a satellite operations control center and / or a ground operations control center. The ground controller 38 communicates with the network router 40. The network router 40 communicates successively with a packet data network embodied by the Internet. Therefore, the gateway station 16 communicates with the Internet, and the mobile station 14 communicates with the gateway station 16, that is, the Internet via the satellite 12 exchanging packetized data according to the logic shown below.
[0021]
Next, the current logic can be seen by referring to FIG. This logic is performed by the mobile station 14 transmitting packet data, by the gateway station 16 transmitting packet data, or by the satellite 12 transmitting packet data.
[0022]
Beginning at block 44, a number of links are established between a transmitter and a receiver, such as those incorporated in the above referenced patent application. Thereafter, each link between the transmitter and the receiver is assigned to a capacity indicator. The capacity indicator displays the amount of capacity available on the link at the indicator allocation time. The present invention envisions assigning a “token” as a capacity indicator. In general, however, any indicator is used that is proportional to or otherwise displays the amount of capacity a particular link has.
[0023]
At block 46, the packet of data received by the transmitter for transmission is divided into fragments. In one preferred and non-limiting example, all fragments except the last fragment are of a predetermined size. If required, the fragments all have different sizes, but the last fragment can be part of a predetermined size. As envisioned in a preferred embodiment, the number of fragments per packet is equal to the number of valid links. In general, a packet, particularly an IP packet, includes destination information in a header.
[0024]
In block 48, the header containing an identifier (ID) is, among other things, it and packets belonging assigned to each fragment indicates its location in the packet. Then, at block 50, a DD loop is started for each fragment. Proceeding to block 52, the fragment is transmitted on the link having the highest number of tokens. That is, the fragment is assigned to the link with the highest capacity and is transmitted here. If two or more links each have the same capacity, and that capacity is the highest of all the links, as indicated by the token, this fragment is the first of such links. Assigned first or randomly to one of the highest capacity links. Since this allocated fragment consumes some of the capacity of the link, the size of the fragment is subtracted from the token allocated to this link to reflect the capacity change at block 54. That is, at block 54, the capacity indicator of this link is reduced according to the size of the allocated fragment.
[0025]
When moving from the block 54 to the determination unit 56, it is determined here whether the last fragment has been allocated. If not, the next fragment is retrieved at block 58 and the above described process is repeated for this fragment. Otherwise, this DD loop ends with a fragment of the packet transmitted over the respective link. Block 60 is periodically refreshed with the number of tokens assigned to the link. For example, once this link resumes idle, a capacity indicator (eg, a token) is replenished to indicate the current capacity.
[0026]
At the receiver, fragments can be received randomly. If so, the receiver uses the fragment ID information to reconstruct the packet. The receiver also arranges the reconstructed packet according to a predetermined sequence rule based on the identification information. This reconstructed packet is forwarded appropriately according to the correct sequence rules.
[0027]
In a typical configuration of the invention, each of the links has a data transmission bandwidth of approximately 9.6 kilobits per second (Kbps). In a typical configuration, up to 24 satellite modem or transceiver modules 20 and 24 links operate simultaneously. This achieves a combined transmission bandwidth of about 230 (Kbps) (24 × 9.6 Kbps = 230.4 Kbps). Somewhat links are grouped together to achieve correspondingly different data transmission bandwidths.
[0028]
The fragments are processed according to a link layer protocol, such as PPP, where the transmitter appends a link layer protocol header (eg, a PPP header) to each of the packet fragments. If required, the various headers added to the fragments are compressed to reduce the size of the packet fragments and thus save data transmission bandwidth.
[0029]
For a typical CDMA-based satellite system 10 as shown in FIG. 1, the forward link uses a code channel in the FDM channel or sub-beam to distinguish users. On the other hand, on the reverse link, user-specific codes and M-ARY modulation schemes are used in the sub-beams to distinguish users. However, it should be understood that the invention need not be limited thereto. For example, the present invention is, in order to achieve a high data rate transfer, for example of a multiple such as CDMA cellular or Personal Communication Services (PCS) communication channels, the earth base is used together with the communication channel of the wireless or wired. In a typical earth-based application in the present invention, the mobile station 14 may reside in a land-based vehicle such as an automobile. It may also include a plurality of simultaneously operating CDMA portable / PCS modems or transceiver module or satellite modem alternative elements. The mobile station 14 receives data via a mobile / PCS base station including a plurality of simultaneously operating CDMA mobile / PCS modems (instead of a satellite gateway) and a plurality of simultaneously operating CDMA mobile / PCS communication channels. Replace.
[0030]
The particular system and method for scheduling token-based PPP fragments illustrated and described herein in detail can fully achieve the above-described objectives of the present invention. On the other hand, this is a preferred embodiment of the present invention, is representative of the main problems widely envisaged by the present invention, and the scope of the present invention is clear to those skilled in the art. it contains examples fully and scope of the present invention is not intended to be limited to anything other than the claims, any reference to an element in the singular is because not stated if clear If present, it should be understood that it is not intended to mean "one and only one" but rather to mean "one or more ." All structural and functional equivalents to the elements of the preferred embodiments described above that will be known or known to those skilled in the art are incorporated herein by reference. Are intended to be covered by the following claims. Further, the device or method need not necessarily address each and every problem that is required to be solved by the present invention. Because it should be included by the claims. Moreover, no element, component or method step herein is intended to be given to the public regardless of whether the element, component or method step is specifically recited in the claims. Where any claim element is explicitly stated using the “means to” phrase, or for method claims, this element may be used instead of “action”. Except where noted as “step”, 35 U.S. S. C. There is no interpretation under the provisions of Article 112, sixth paragraph.
[Brief description of the drawings]
[0031]
FIG. 1 is a block diagram of an exemplary, non-limiting communication system that can utilize the present PPP multilink principle.
FIG. 2 is a flowchart of this logic.
[Explanation of symbols]
[0032]
DESCRIPTION OF SYMBOLS 10 ... Communication system, 12 ... Satellite, 14 ... Mobile station, 16 ... Gateway station, 18 ... Controller, 20 ... Modem, 22 ... Link, 24 ... Controller, 26 ... Modem, 28 ... Link, 30 ... Data network, 32 ... Communication link 34 ... User computer 36 ... Gateway router 38 ... Ground controller 40 ... Network router

Claims (20)

A method for communicating data arranged in a packet,
Providing multiple links between the transmitter and the receiver;
Assigning each link at least one token which is a capacity indicator;
Partitioning each packet into a number of fragments equal to the number of the plurality of links;
Using said token, each of the plurality of fragments, such that said plurality of fragments can be transmitted in parallel via a plurality of links, the links having the highest capacity available indicated by the token Repeating the association for the number of the plurality of fragments . The method of claim 1, wherein
Subtracting an amount indicating the size of the fragment from the number of tokens assigned to the link if the fragment is assigned to the link. The method of claim 1, wherein
The method further comprising assigning at least one identifier to each fragment to enable reassembly of the packet. The method of claim 1, wherein
Reconstructing the fragment at the receiver based on at least one identifier assigned to each fragment to reconstruct the packet. The method of claim 1, wherein
Transmitting the fragment in parallel over the link. The method of claim 1, wherein
The method in which the packet is encapsulated in PPP. A transmitter for transmitting packetized data using an IP protocol,
A controller for receiving the packet and dividing the packet into fragments;
The number of fragments is equal to the number of multiple radio links, and each fragment is the plurality of fragments based on an allocation policy according to link capacity so that the multiple fragments can be transmitted in parallel over the wireless link. Scheduled to be transmitted on one of the radio links,
The controller, for each fragment, repeats associating the fragment with the link having the highest capacity indicated by a token that is a capacity indicator, by the number of the plurality of fragments . The transmitter of claim 7, wherein
The controller is a transmitter mounted on a mobile station. The transmitter of claim 7, wherein
The controller is a transmitter installed in a gateway station. The transmitter of claim 7, wherein
The controller is a transmitter mounted on a satellite. The transmitter of claim 7, wherein
The controller is a transmitter that assigns a token indicating the capacity of each link to the link. The transmitter of claim 11, wherein
The controller, if the fragment is allocated to a link, subtracts an amount indicating the size of the fragment from the number of allocated tokens. A system for transmitting packetized data,
Means for partitioning the packet into a number of fragments equal to the number of communication links;
Means for scheduling the plurality of fragments between the plurality of communication links such that the plurality of fragments can be transmitted in parallel via the plurality of communication links based on a current capacity of the communication link; And
The scheduling means repeats, for each fragment, associating the fragment with the link having the highest capacity indicated by the capacity indicator token by the number of the plurality of fragments . The system of claim 13, wherein
The means for scheduling is realized by at least one controller;
The controller is a system that allocates a token indicating the capacity of each link to the link. The system of claim 14, wherein
The controller, when the fragment is assigned to the link, subtracts an amount indicating the size of the fragment from the number of tokens assigned to the link. The system of claim 13, wherein
The controller is a system implemented in a mobile station. The system of claim 13, wherein
The controller is a system implemented in a gateway station. The system of claim 13, wherein
The controller is a system implemented in a satellite. The system of claim 13, wherein
The system further comprising means for transmitting the plurality of fragments in parallel with each other over the link. The transmitter of claim 7, wherein
The controller is a transmitter for transmitting the plurality of fragments in parallel via the link.

Images