JPH0521371B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION (Field of Industrial Application) The present invention relates to a multi-access method in which one satellite channel is shared by a plurality of stations to perform packet communication.

(Prior art and its problems) Access methods in satellite packet communication networks include fixed allocation methods such as TDMA and FDMA, random access methods such as pure Aloha and slotted Aloha, and packet reservation methods such as random reservation method and sequential reservation method. A method has been proposed. For example, L. Kleinrock writes in IEE Communication Magazine Volume 17, January 1979 issue (IEEE
Communications magazine Vol.17.No.1,
1979.) “On Resource Sharing in a Distributed Communication Environment.”
Sharing in a Distributed Communication
In a paper titled ``Environmental Environment'', a comparative study of these methods was conducted.In the case of light loads, the random access method, in the case of medium to relatively high loads, the packet reservation method, and in the case of high loads. , it has been reported that a fixed allocation method is suitable. In light of such reports, adaptive or combinatory schemes have been proposed to be suitable for wide range of load fluctuations.

Incidentally, many researchers have evaluated multi-access, but in all cases the transmission speed per station (transmission speed/station) is 2 Kbps or less. Often referred to as S.S.R.A.M.
Proceedings of the International Conference on Communications (1977)
International Conference on
Satellite multiaccess schemes for data traffic
schemes for data traffic)”
50kbps, the number of stations is 50, and the transmission speed/station is
It is 1Kbps.

However, recent trends in data communication include the integration of voice, image, etc., and there is also a demand for LAN interconnection. Under these circumstances, it must be said that it is inappropriate to evaluate the transmission speed/station at several Kbps.

Here, the delay of the Aloha method and the delay of the TDMA method are compared using the transmission speed/station as a variable. Aloha style delay D _ALOHA is El Kleinrock (L.
Kleinrock) in December 1975, IEEE Transactions on Communication
The paper “Packet Switching in Radio Channels” was published on pages 1400 to 1416 of Communications.
D _ALOHA = (G/S-1) (τ ₀ +T ₀ +) +τ ₀ +T ₀ (1)′ However, τ ₀ ... Propagation delay (seconds) T ₀ ... Packet length (seconds) ... Average delay (seconds) for random retransmission S...Throughout S...Channel traffic. According to the above paper, the relationship between throughput S and channel traffic is S=G·exp(−G). In the case of satellite communication, the propagation delay τ ₀ is large compared to the packet length T ₀ etc., so equation (1)′ is D _ALOHA = (G/S−1) τ ₀ +T ₀ =Gτ ₀ /S (2) ′ can be approximated as On the other hand, the delay of the TDMA system was developed by SSLam, and in 1976, the National Telecommunications Conference Record (National
Telecommunications Conference Record)
Published paper “Delay Analysis of
Delay Analysis of a Packet Switch TDA System (Delay Analysis of a
Packet-Switched TDMA System), D _TDMA = 1/2NT ₀ /(1-S) + τ ₀ +T ₀ (3) where N...Number of stations _T0 ...Packet length (seconds) S...Throughput. The packet length T ₀ is expressed as T ₀ =l/C, where l...Packet length (bits) C...Transmission rate (bits/second). Since we are considering the case where the propagation delay τ ₀ is large, equation (3)' can also be approximated as _DTDMA = 1/2l/{(1-S)C/N}+τ ₀ (4)'.

Using equations (2)' and (4)' to compare the delay in the Aloha method and the delay in the TDMA method, the results are as shown in Figure 1. However, the packet length l is 1000 bits, and the propagation delay τ ₀ is 0.25 seconds. The horizontal axis is transmission speed/station. As you can see from the figure, if the transmission speed/station is high even when the load is light, the TDMA method is advantageous.
The packet reservation method has an average delay of at least 0.5 seconds, so it cannot be compared. Therefore,
For example, if the number of stations is 100 and the transmission speed is 1 Mbps, the TDMA method can be said to be superior to other methods. However, in this case, it is necessary that the allocation be done appropriately.

Incidentally, there is a conventional allocation method based on telephone calls, which is effective when packets arrive periodically. However, when normal data packets will arrive is stochastic, and in this case, even if there is enough line capacity to process them, queues will occur and delays will occur. Therefore, each station requests more allocations and competes with each other. That is, the conventional system has the drawback that even when there is sufficient line capacity, if a station that has already secured a line requests more allocation, it will not be possible to allocate a sufficient amount to each station.

(Objective of the Invention) The present invention provides an allocation method that is compatible with such stochastically arriving traffic.

(Structure of the Invention) According to the present invention, in a multi-access system in which a satellite channel is shared by a plurality of stations to perform packet communication, the satellite channel is observed, the traffic of each station is estimated, and the estimated value and the estimated value are The new channel allocation for each station is determined by adding the remaining channel capacity after allocating it to each station and the value obtained by equally allocating it to each station.Then, the new channel allocation is compared with the current old channel allocation, and the difference is calculated. Accordingly, a satellite packet communication allocation method is obtained, which is characterized in that the allocation is changed so that the new channel allocation amount is obtained.

(Example) The present invention will be described in detail below using the drawings. As shown in FIG. 2, a plurality of stations 100, a network management center 101 that controls allocation,
The network is composed of a satellite channel 102 having a data channel and a control channel, and the data channel is divided into slots for each transmission time of one packet, as shown in FIG. 3, and each L slot is one frame. . It is assumed that L is usually larger than the number of stations N.

As shown in FIG. 4, the network management center 101 observes the allocation table 103, which is a correspondence table between each station and the allocated slot, and the data channel, refers to the allocation table, and transmits one frame to each station. a channel observation device 104 that counts the number of packets transmitted in one frame by each station; a traffic estimator 105 that estimates the traffic of each station by averaging the number of packets transmitted by each station in one frame; With reference to the calculation unit 106 that calculates the number of slots and the allocation table, the calculation unit 106 calculates the number of slots currently allocated to each station and the calculation unit 106.
An allocation controller 10 that compares the obtained new number of allocated slots and, if they are significantly different, rewrites the allocation table so that it is close to the new number of allocated slots.
7, and a command generator 108 that sends a command through a control channel to a station that requires an allocation change as a result of rewriting the allocation table.

Here, an arithmetic expression for calculating the number of slots allocated to each station is derived from the traffic of each station, which is used by the arithmetic unit 106. First, let's explain the symbols.

λi...Packet arrival rate at station i (pieces/second) _T0 ...Packet length (seconds) L...Frame length (slots) N...Number of stations ηi...Number of slots assigned to one frame of station _iτ0 ...Propagation delay (seconds) Mi...Subframe length of station i (slot) In Fig. 3, the frame length L is 16, slot 1 and slot 9 are assigned to station i, and the number of slots ηi
is 2, and the subframe length Mi is 8. In reality, the slots allocated as shown in Figure 3 do not necessarily rotate at a constant cycle, and the subframe length Mi
Although it is not clear, in order to simplify the calculation here, it is assumed that the subframe length Mi is Mi=L/ηi (1) and that the allocated slots circulate at a constant period.

Under the above assumptions, the delay time Di until a packet arriving at station i is received by the destination station is calculated from Paper S.
S. Lam, “Delay Analysis of a Packet−
Switched TDMA System,”NTC 76 Conf.
Rec., IEEE, New York, pp.16.3−1 to 16.3
−6, it is expressed as Di=1/2MiT ₀ +1/2·λi(MiT ₀ ) ² / (1−λiMiT ₀ )+T ₀ +τ ₀ (2). The third and fourth terms in equation (2) have nothing to do with allocation, so they will be omitted below.

By substituting equation (1) into equation (2) and transforming it, we get the delay time Di.
is Di=1/2LT ₀ /(ηi−λiLT ₀ ) (3).

Here, we derive an arithmetic expression that minimizes the delay of the station with the largest delay.

_N 〓 Under the constraint of ⁱ⁼¹ ηi=L, the number of allocated slots ηi(i
The problem to find =1~N) is This can be replaced with a nonlinear programming problem that minimizes A under the constraint of . Literature, Konno, Yamashita,
According to "Nonlinear Programming", Japan Society of Science and Technology, 1978, if it is a solution, it satisfies the Kuhn-Tucker condition.

Now, applying the Kuhn-Tucker condition to the above problem, we get becomes. However, αi (i=0 to N) is a constant.
Transforming equation (13), we get From the two equations above equation (14), it is found that αi > 0 (i = 0 to N), and from the third equation, A-Di = 0, i
=1 to N are derived. Solving this gives ηi=ρi+{LT ₀ /(2A)} (15), and using the fourth equation in equation (15), we get ηi=ρi+(L−ρ)/N (16). However, ρ= _N 〓 ⁱ⁼¹ ρi _0As you can see, the number of slots to be allocated can be easily determined using four arithmetic operations. Equation (16) is calculated by adding the number of slots ρi, which is equal to the traffic of station i, to the number of slots (L-ρ)/N obtained by equally distributing the number of slots L-ρ to each station after allocating that number to each station. This is what I did.

(Effects of the Invention) FIG. 5 shows the difference in total average delay between the conventional fixed allocation TDMA system and the present invention, and FIG. 6 shows the difference in average delay of each station. In each figure N=
2, L = 10, ρ ₁ + ρ ₂ = 5, the horizontal axis is the traffic ratio of the two stations, the vertical axis is the average delay time, and the packet length is
It is normalized by T ₀ . In fixed allocation, slots are allocated equally to each station. As can be seen from FIGS. 5 and 6, the present invention has a low total average delay and no variation in delay between stations.

As can be seen from the above description, the present invention appropriately changes allocation in accordance with the traffic of each station.

[Brief explanation of the drawing]

Figure 1 shows the relationship between delay and transmission speed, Figure 2 shows the relationship between delay and transmission speed.
3 shows a data channel frame, FIG. 4 is a block diagram showing the network management center 101, and FIG. 5 shows the fixed allocation TDMA method and the total average of the present invention. FIG. 6 is a diagram showing the average delay of each station in the fixed allocation TDMA system and the present invention. In the figure, 100 is a plurality of stations, 101 is a network management center, 102 is a satellite channel, 1
03 is an allocation table, 104 is a channel observation device,
105 is a traffic estimator, 106 is an arithmetic unit, 1
07 is an assignment controller, and 108 is a command generator.

Claims (1)

[Claims] 1. In a multi-access system in which a satellite channel is shared by multiple stations for packet communication, the satellite channel is observed and the traffic of each station is estimated,
The new channel allocation amount for each station is determined by adding the estimated value and the value obtained by equally distributing the channel capacity remaining after the estimated value is allocated to each station, and then calculates the new channel allocation amount and the current old channel allocation amount. 2. An allocation method for satellite packet communication, characterized in that the allocation is compared and, if different, the allocation is changed so that the new channel allocation becomes the new channel allocation.