Dynamic allocation of satellite capacity
through packet reservation
Dr. Lawrence G. RobertsDepartment of Defense
If one projects the growth of computer communication networks like the ARPANET1,2,3,4 to a worldwide situation, satellite communication is attractive for intercommunicating between the widespread geographic areas. For this variable demand, multi-station, data traffic situation, satellites are uniquely qualified in that they are theoretically capable of statistically averaging the load in total at the satellite rather than requiring each station or station-pair to average the traffic independently. However, very little research has been done on techniques which permit direct multi-station demand access to a satellite for data traffic. For voice traffic statistics, COMSAT Laboratories has developed highly efficient techniques; the SPADE5 system currently installed in the Atlantic permitting the pooled use of 64KB PCM voice channels on a demand basis, and the MAT-16 TDMA (Time Division Multiple-Access) experimental system. Both systems permit flexible demand assignment of the satellite capacity, but on a circuit-switched basis designed to interconnect a full duplex 64KB channel between two stations for minutes rather than deliver small blocks of data here and there. This work forms the technical base for advanced digital satellite communication, and provides a very effective means for moving large quantities of data between two points. However, for short interactive data traffic between many stations, new allocation techniques are desirable.
In order to evaluate the performance of any new technique for dynamic assignment of satellite capacity and compare it with other techniques, a complete model of the data traffic must be postulated. Given the model, each technique can be analyzed and its performance computed for any traffic load or distribution. Although it is difficult to fully represent the complete variation in traffic rates normal in data traffic, the following model describes the basic nature of data traffic which might arrive at each satellite station from a local packet network.
There are Poisson arrivals of both single packets (1270 bits including the header) and multi-packet blocks (8 packets) at each station. The overall Poisson arrival rate for both is L with a fraction F of single packets and the remainder multi-packets. For simplicity, the arrival rates at all stations are stationary and equal. This is not completely representative of normal data traffic but for the assignment techniques of interest, non-stationary and unequal arrival rates will produce nearly identical performance to the stationary case. Techniques which subdivide the satellite capacity in a preassigned manner would be seriously hurt by non-stationary traffic rates but the poor performance of these systems will be demonstrated, at least in part, by their inability to handle Poisson packet arrivals effectively. The average station traffic in packets per second is:
The destination of this traffic is equally divided between all of the other stations.
For a truly reliable data communications network, each packet or block should be acknowledged as having been correctly received. Positive error control using acknowledgments and retransmissions is very important for data traffic. Thus, acknowledgment traffic must be added to the station traffic. To achieve rapid recovery from errors there must be one small packet (144 bits) sent for each packet or block sent. This traffic is administrative overhead and will not be counted when computing the channel utilization.
The analytic results presented later in the paper are all for equal arrival rates for single packets and multi-packets (F = .5). Other values of F have been examined as well as eases where the input traffic contains small (144 bit) data packets as well. The detailed effect of these variations is not sufficiently pronounced to consider here, however. For comparing techniques the equal arrival distribution is quite representative.
ARPANET experience indicates that the data traffic one can expect is proportional to the total dollar value of computer services being bought or sold through the network. The total traffic generated by one dollar of computer activity is about 315 packets, half going each way.3 Thus, $200K/year of computer activity within a region produces 2KB of traffic, of which 1KB is leaving the region. Within the next few years it is probable that the computer services exchanged internationally will be between 350K/country and $2M/country which suggests that the traffic levels, T, to consider are from .25KB to 10KB. For domestic satellite usage the dollar flow would be far greater than this if the regions are ones like the east and west coast. However, if small stations become economically attractive, the individual user complexes or computer sites will have traffic levels well within this range. Therefore, several of the analytic results presented are for a station traffic of T = 1KB. This corresponds to one packet or multi-packet arriving every 4.5 seconds, on the average. It is extremely important to note the infrequency of this, considering that the block must be delivered within less than a second. Even at 10KB, with arrivals every .45 seconds, each arrival must be treated independently, not waiting for a queue to build up if rapid response is to be maintained. Only after the individual traffic exceeds 50KB is there significant smoothing and uniformity to the station's traffic flow. Thus, it is quite important to devise techniques which do not depend on this smoothing at each station if stations with under $1OM of remote computer activity are to be served economically.
CHANNELIZED SATELLITE TRANSMISSION TECHNIQUES
The most common technique in use today is for each pair of stations which have traffic to lease a small full duplex data channel directly. If this technique were used for a large net of N stations, it would require N (N-1) half duplex channels, each large enough to provide the desired delay response. The total satellite bandwidth required is the sum of the N(N-1) individual requirements plus 2KHz* per channel (minimum) for guardbands. However, since the channels are dedicated, variable packet sizes can be handled and the small acknowledgments fit in efficiently.
FDM-Store and forward star
Since it is clearly very costly for full interconnection, store and forward is an obvious alternative. With short, leased ground lines, the ARPANET very effectively uses this technique, but since each hop adds at least .27 sec due to the propagation delay, it is important to minimize the number of hops. Thus a star design is probably as good an example of this technique as any. The total number of channels for a star is N-1. The delay is the two hop total plus any switch delay (herein presumed zero and of infinite capacity).
Since all stations could theoretically hear all the transmissions, a store and forward process is really unnecessary if each packet has an address and its destination can receive it. Further, the guardbands required for FDM can be eliminated if Time Division Multiple Access techniques are used. Instead, an 80 bit start up synchronization leader is required. This increases the small acknowledgment packets to 225 bits and the normal packets to 1350 bits, a 7.6 percent overhead. For this type of data traffic a strict alternation of time slot ownership between the stations was evaluated. All slots are the same size, 1350 bits, except for small acknowledgment packets which are packed in at the necessary intervals. Thus, each station has one Nth of the channel capacity and can use it freely to send to any station. Each station must examine all packets for those addressed to itself. To adapt to unequal or non-stationary traffic levels, there are many techniques6 for slowly varying the channel split.
Instead of preassigning time slots to stations and often having them be unused, in the ALOHA system they are all freely utilized by any station with traffic. When there are many stations this reduces the delay caused in waiting for your own slot, but introduces a channel utilization limit of 36 percent to insure that conflicts are not too frequent. When conflicts do occur the sum check clearly indicates it and both stations retransmit. A very complete treatment of this technique is presented in the papers by Abramson7 and Kleinrock and Lam.8 For the comparison curves presented here, an approximation to the precise delay calculation was used and the possibilities of improved performance due to excess capacity were ignored. Thus, the ALOHA results are slightly conservative.
In order to further improve the efficiency of data traffic distribution via satellite, the following reservation system is proposed. As with TDMA and ALOHA the satellite channel is divided into time slots of 1350 bits each. However, after every M slots one slot is subdivided into V small slots. The small slots are for reservations and acknowledgments, to be used on a contention basis with the ALOHA technique. The remaining M large slots are for RESERVED data packets. When a data packet or multi-packet block arrives at a station it transmits a reservation in a randomly selected one of the V small slots in the next ALOHA group. The reservation is a request for from one to eight RESERVED slots. Upon seeing such a reservation each station adds the number of slots requested to a count, J, the number of slots currently reserved. The originating station has now blocked out a sequence of RESERVED slots to transmit his packets in. Thus, there is one common queue for all stations and by broadcasting reservations they can claim space on the queue. It is not necessary for any station but the originating station to remember which space belongs to whom, since the only requirement is that no one else uses the slots.
Referring to Figure 1, a reservation for three slots is transmitted at t=0 so as to fall in an ALOHA slot at t=5. If a conflict occurs, the originating station will determine the sum check is bad at t=10 and retransmit the reservation. However, if it is received correctly at t=10 and assuming the current queue length is thirteen, the station computes that it can use the slots at t=21, 22 and 24. It does this by transmitting at t=16, 17 and 19. By t=30 the entire block of three packets has been delivered to their destination. If no other reservations have been received by t=19 the queue goes to zero at this point and the channel reverts to a pure ALOHA state until the next valid reservation is received.
To maintain coordination between all the stations, it is necessary and sufficient that each reservation which is received correctly by any station is received correctly by all the stations. This can be assured even if the channel error rate is high by properly encoding the reservation. The simplest strategy is to use the standard packet sum check hardware, and send three independently sumchecked copies of the reservation data. A reservation requires 24 bits of information and with the sum check is 48 bits. Three of these together with the 80 bit sync sequence made a 224 bit packet. Given this size for the small slot and 1350 bits for the large slot, we can pack six reservations in the large slot space; therefore, V=6. If the channel error rate is 10-5and there are 1000 stations, the probability that one or more of the stations will have errors in all three sections is approximately 1000 (48X10-5)3 or 10-7. With a 1.5MB channel this is one error every three days, a very tolerable rate considering the only impact is to delay some data momentarily. If the reservation were not triplicated, however, the probability of an error is .48, sufficient to totally confuse all the stations.
There are two states, ALOHA and RESERVED. On start up and every time thereafter when the reservation queue goes to zero, the channel is in the ALOHA state. In this state, all slots small and the ALOHA mode of transmission is used. Reservations, acknowledgments and even small data packets can be sent using the 224 bit slots. However, the first successful reservation causes the RESERVED state to begin. Let us define Z to be the channel rate in large
slots per second and R to be the number of large slots per round trip (R .27Z). Then, considering time as viewed from the satellite, the data packets associated with the first reservation should be transmitted so as to start R+1 large slots after the reservation. To avoid confusion, M is kept constant for the entirety of each RESERVED state but it is allowed to change each time the state is entered. The initial reservation which starts the state contains a suggested new value for M. This value is used until the state terminates. The determination of M will be considered later.
Figure 1. RESERVATION SYSTEM CHANNEL DIVISION 50KB channel) R = 10 slots per round trip), M = 5, V = 6
The traffic of small packets (reservations, acknowledgments) is twice the overall arrival rate (NL) since every data block requires a reservation and an acknowledgment. If we assume that the arrival rate of these small packets is independent of the state (a good approximation since they are fully independent at both low and high traffic levels where the average duration of one of the states is short compared to R), then:
Small Slot Channel Utilization in ALOHA State: S1 = 2NL/ZV(2)
Small Slot Channel Utilization in RESERVED State: S
2= 2NL(M + 1)/ZV(3)
The channel utilization for large slots must be computed as if the channel were always in the RESERVED state since the ALOHA state is a result of the non-utilization of the reserved slots, not the cause. Thus:
Large Slot Channel Utilization: S3 = BNL(M + 1)/MZ
Where, average block size: B=F+8(1-F)
ALOHA State: S1=AG01e-g1
RESERVED State: S2=AG2e-G2
These relations must be solved for G by iteration since S is the known quantity. The correction constant, A, depends on the retransmission randomization technique and R, but is always between .8 and 1.0. As a result of these relations the maximum useful ALOHA throughput is S=A/c. An empirically derived approximation* to A used for this analysis was (K = retransmission randomization period in slots):
Small packet delay
The average fraction of time the system is in the RESERVED state is equal to the large slot channel utilization, S3, since that is the fraction of time the reserved packets are being sent. Thus, if we compute the delay for the small packets in both states a weighted average can be taken, using S3, to obtain the average delay.
Now, the overall average small packet delay can be determined: Overall Small Packet Delay:
Overall Small Packet Delay: D2=D1(1-S3)+D2S3(5)
Large packet and block delay
For the reserved packets, the delay has three components; the reservation delay (D8), the central queueing delay and the transmission-propagation delay of the packet or block. For a block of B packets where the general load is the defined traffic distribution the delay is:
Missing scan !!!!!!!!
Where: Y = 7.2 packets (second moment of block size/avg. block size)
and: B = 4.5 packets (average block size)
Determination of M
An optimal value for M can now be determined numerically for any given channel and traffic load. However, this value is not very critical at low channel loading factors. It is only when the channel is operating near peak capacity that M affects the delay more than a few percent. Since M cannot be changed rapidly it is desirable to set M to the value which optimizes the channel capacity and thereby minimizes the delay at peak load. For peak capacity, both the small and large slot portions of the channel in the RESERVED state should be fully loaded. This occurs when = A/c and S8 = 1. Doing this and solving equations (3) and (4) for the arrival rate, L, gives us:
If this peak capacity value for M is always used the delay is within 10 percent of optimal and the system is quite stable. As can be seen, the only traffic parameter M depends on is B, the average block size. M can be adjusted by the stations if the channel is monitored and the fractions of each type of packet sent are measured. From these fractions it is easy to determine M. Figure 2: Average Block Delay
Now it is possible to determine the delay given the traffic distribution (F,B), number of stations (N), and input arrival rate (L). One common way to examine performance is by plotting delay versus the channel utilization for a fixed channel. The channel utilization, C, is the ratio of the good data delivered to the new channel speed:
Channel Utilization: C = NLB/Z
Figure 2 shows the delay vs. C for the TDMA, ALOHA, and Reservation techniques. The traffic distribution is as
Figure 3: Average Delay - Sec.
previously defined; half single packets and half blocks of eight.
This type of presentation is not the best for deciding what technique to use for a specific job, but it does show the general behavior of the systems for a fixed channel size, as the traffic load varies.
In order to really compare the cost of the various techniques to do a certain job, it is necessary to set the traffic level, number of stations, and the delay permissible. Then, for each technique, the channel size required to achieve the delay constraint can be searched for. To make the presentation more meaningful the cost of this channel per
Figure 4: Individual Station Traffic In Kilobits/Sec.
megabit of traffic can then be determined using as a price basis the current tariffed price of the 50KB INTELSAT IV channel (45 KHz) used in the ARPANET between California and Hawaii. It is presumed that any bandwidth could be purchased for the same price per KHz. Converting the cost to dollars per megabit permits easy comparison with the cost in the current ARPANET where distributed leased line capacity can be achieved for 5.10 per megabit. Figures 3, 4 and 5 show communications cost as a function of the three variables; delay, traffic and number of
Figure 5: Number of stations
stations. Examining Figure 3 it is clear that if a delay of less than two round trips (.54 sec) is required, the ALOHA system is superior. However, the cost for .4 sec service is over 6 times that of .8 sec service (using the reservation technique). It is also clear that delays of more than .8 sec are not necessary and save very little money. Figure 4 shows that as the individual station traffic is increased to 50KB or higher, TDMA becomes almost as good as the reservation system since there is sufficient local averaging of traffic. Similarly, at this same traffic level FDM-Store and Forward achieves its maximum efficiency but due to sending each packet twice its asymptotic cost is twice that of TDMA or Reservation. These traffic levels for each station are unrealistically high, however, and the flat performance of ALOHA and the Reservation System is vastly preferable since the cost of data communications to small stations is the same as for large stations. Finally, Figure 5 shows the effect of adding stations to the net. With FDM the cost gro~vs out of bounds quickly whereas the reservation technique improves its efficiency until the total traffic from all stations exceeds 100KB. Below 5KB total traffic ALOHA is superior, but this is not a very important case. For large numbers of stations at 1KB traffic per station and .8 seconds delay the reservation system is 3 times cheaper than ALOHA, 6 times cheaper than TDMA, and 56 times cheaper than FDM Store and Forward.
The reservation technique presented here is one of several techniques which have been developed recently to take full advantage of the multi-access capabilities of satellites for data traffic.''0 Both the ALOHA technique and the reservation system depend for their efficiency on the total multi-station traffic rather than the individual station traffic as does TDMA and FDM Store and Forward. The performance improvement reflects this with the reservation system being up to 10 times as efficient as TDMA for small station traffic levels. The worst possible technique for data traffic' is pure FDM links between each station pair since this is only efficient if all pairs of stations have 50KB of traffic, driving the cost out of bounds for normal usage. The reservation system is also a factor of 3 more efficient than the ALOHA system and for large (100KB) traffic levels achieves almost perfect utilization of the channels.
- Roberts, L. G., Wessler, B., "Computer Network Development to Achieve Resource Sharing," AFIPS Spring Joint Computer Conference Proceedings, pp. 543-549, 1970.
- Heart, F., Kahn, R. E., Ornstein, S., Crowther, W., Walden, D., "The Interface Mesaage Processor for the ARPA Computer Network," AFIPS Spring Joint Computer Conference Proceedings, pp. 551-567, 1970.
- Roberts, L. G., "Network Rationale: A 5-Year Reevaluation," Proceedings of COMPCON 73, February 1973.
- Kahn, R. E., "Resource-Sharing Computer Communications Networks," Proceedings of IEEE, pp. 1397-1407, November 1972.
- Cacciamani, E. R., "The Spade System as Applied to Data Communications and Small Earth Station Operation," COMSA T Technical Review, Vol. 1, No. 1, Fall 1971.
- Schmidt, W. G., Gabbard, 0. G., Cacciamani, E. R., Maillet, W. G., Wu, W. W., "MAT-i: INTELSAT's Experimental 700-Channel TDMA/DA System," INTELSAT/IEE International Conference on Digital Satellite Communications Proceedings, London, November 25-27, 1969.
- Abramson, Norman, "Packet Switching With Satellites," These proceedings.
- Kleinrock, Leonard, Lam, Simon S., "Packet-Switching in a Slotted Satellite Channel," These proceedings.
- Crowther, W., Rettberg, R., Walden, B., Ornstein, S., Heart, F., "A System for Broadcast Communication: Reservation-ALOHA," Proceedings of the Sixth Hawaii International Conference on System Sciences, 1973.
- Binder, Richard, Another ALOIL4 Satellite Protocol, ARPA Satellite System Note 32, NIC 13147.
* Two KHz is the minimal possible channel separation determined by oscillator stability for current INTELSAT IV equipment based on a private communication with E. Cacciamani, COMSAT Laboratories. Actual guardbands in use are wider.
* For an accurate and more detailed solution to the effect of a fixed retransmission delay, refer to Reference 8.
Copyright © 2001 Dr. Lawrence G. Roberts