The Center for Satellite and Hybrid Communication Networks is a NASA-sponsored Commercial Space
Center also supported by the Department of Defense (DOD), industry, the State of Maryland, the
University of Maryland and the Institute for Systems Research. This document is a technical report in
the CSHCN series originating at the University of Maryland.
Web site  http://www.isr.umd.edu/CSHCN/
TECHNICAL RESEARCH REPORT
A Scheme to Improve Throughput for ARQ-Protected 
Satellite Communication 
by D. Friedman, A. Ephremides
CSHCN T.R. 97-10
(ISR T.R. 97-31)
A Scheme to Improve Throughput
for ARQ-Protected Satellite Communication
Daniel Friedman and Anthony Ephremides
#03
Center for Satellite and Hybrid Communication Networks
Institute for Systems Research
University of Maryland
College Park, MD 20742 USA
Telephone: #28301#29 405-7900 Fax: #28301#29 314-8586
Abstract
Automatic-repeat-request #28ARQ#29 error control
is often employed to assure high #0Cdelity informa-
tion transmission. However, ARQ error control
can provide poor throughput for satellite multi-
casting. The throughput in such communication
may be improved by the combination of a terres-
trial network parallel to the satellite network and
a judiciously modi#0Ced ARQ protocol. In particu-
lar, retransmitted ARQ frames can be sent terres-
trially in such a hybrid network, allowing higher
throughput than in a pure-satellite network. This
work presents analytic results to establish the po-
tential for improving the throughput of satellite
multicast communication employing ARQ error
control by the adoption of suchahybrid network
architecture.
Introduction
A satellite is excellently suited for multicast
communication. As in all communication systems,
an error control scheme is required for multicast-
ing. Suchschemesmay be broadlyclassi#0Ced as for-
ward error correction #28FEC#29 and automatic repeat
request #28ARQ#29 protocols. While numerous error
control schemes for point-to-pointcommunication
#28unicasting#29 appear in the literature, relativelyfew
for point-to-multipoint communication #28multicas-
ting#29 have been presented #28see #5B1, 2, 3, 4, 5, 6, 7, 8#5D
for a representative selection#29. Error control for
multicasting is hence fertile research territory.
#03
This work was supported by the Center for Satellite
and Hybrid Communication Networks under NASA Grant
NAGW-2777 and by the Institute for Systems Research
under National Science Foundation Grants NSFD CDR
8803012 and EEC 940234.
We havechosen to begin our venture into this
territory by examining ARQ protocols for multi-
cast delivery of data. The typical problem in a
multicast ARQ system is that since retransmis-
sions are sentover the multicast channel, those re-
quired by only one receiving station do not bene#0Ct
the other receivers. Accordingly the throughput
for the system falls drastically as the number of
receivers increases. Furthermore, if one receiving
station is a #5Cpoorer listener" than other stations,
i.e. su#0Bers a relatively high frame error rate, then
the throughput to all stations is essentially lim-
ited to the throughput achievable to that poorer
listener #5B9#5D.
If the retransmissions could somehow be sent
only to the receivers which require them, the
throughput might be improved considerably. It
is natural, then, to suggest supplementing a satel-
lite multicast system with a set of point-to-point
terrestrial links between the transmitter and each
receiver, as depicted in Figure 1. In such a system,
retransmissions may be sent terrestrially instead
of via the satellite multicast link, and an improve-
ment in throughput might be possible. Further, if
the ARQacknowledgements are sent terrestrially
as well, then the receiving stations do not require
satellite transmission capability, and the cost of
such stations may be correspondingly reduced.
In this article, we examine the throughput of-
fered by such a hybrid #28satellite and terrestrial#29
network con#0Cguration for unicast and multicast
selective-repeat ARQ operation. In the next sec-
tion we examine the throughput for unicasting and
multicasting in pure-satellite and hybrid networks.
Numerical examples are presented in the following
section. Finally,we conclude with some thoughts
for future work.
1
transmitter
receivers
satellite
terrestrial links
data
acknowledgements retransmissions
Figure 1: Multicasting in a hybrid network.
Analysis
Point-to-Point Communication
We #0Crst examine unicasting in a pure satellite
network. We make the following assumptions and
notational de#0Cnitions:
1. In#0Cnite bu#0Bering, in#0Cnite window size; ideal
selective-repeat ARQ protocol.
2. All acknowledgements are delivered without
errors.
3. The satellite frame error rate #28the probability
a frame sent via satellite arrives in error at
the receiver#29 is p
s
, while the terrestrial frame
error rate is p
t
.
4. There are ` information bits and h non-
information #28overhead#29 bits per information
frame sent either via satellite or via a terres-
trial link.
5. In the hybrid network, all retransmissions are
sent terrestrially.
6. We de#0Cne the throughput, #11, as the expected
valueof the ratioofthe numberof information
bits delivered to a receiver per bit senttothat
receiver. We will attach subscripts to #11 to
denote the number of receivers #281 or M#29and
the type of network #28satellite or hybrid#29.
We remark this last assumption can be demon-
strated by straightforward analysis to be valid for
plausible, implementable combinations of satel-
lite link and terrestrial link bandwidths and error
rates.
Let #0C denote the expected number of frames
sent to a receiver per frame delivered to that re-
ceiver. #28In point-to-point pure-satellite and hy-
brid networks, and in a pure-satellite multicast
network, #0C is equivalent to the number of frames
transmitted per frame delivered.#29 For the pure-
satellite network wehave#5B10,11#5D:
#0C
1;satellite
=
1
X
i=1
i#281,p
s
#29p
i,1
s
=
1
1,p
s
:
The throughput is then
#11
1;satellite
=
`
`+h
1
#0C
1;satellite
=
`
`+h
#281,p
s
#29:
In the hybrid network, each frame is sent ini-
tially via satellite, and all retransmissions are sent
terrestrially,sowehave:
#0C
1;hybrid
= 1#281,p
s
#29+p
s
#281,p
t
#29
1
X
i=2
ip
i,2
t
= #281,p
s
#29+
p
s
p
t
#14
1
1,p
t
,#281,p
t
#29
#15
=
1,p
t
+p
s
1,p
t
:
This yields for the throughput:
#11
1;hybrid
=
`
`+h
#14
1,p
t
1,p
t
+p
s
#15
:
Point-to-Multipoint Communication
For analyzing multicast networks, we preserve
the assumptions of the point-to-point analysis and
add the following:
1. There are M#3E1 receivers.
2. The noise processes experienced by all re-
ceivers are independent and identical.
3. There is no competition among receivers for
access to the acknowledgmentchannel.
4. The propagation delays for acknowledge-
ments traveling from the receivers to the
transmitter are the same for all acknowledge-
ments.
2
5. The transmitter maintains a history of which
stations have acknowledged which frames.
Accordingly, if receiver m #28m =1;2;:::;M#29
has positively acknowledged receipt of frame
F,anacknowledgement is not required from
m for any retransmissions of F whichmaybe
required for other receivers in the network.
In the multicast pure-satellite network, the
transmitter continuously sends frames via the
satellite multicast channel to the M receivers,
which generate respective acknowledgments to
send to the transmitter. Upon receiving acknowl-
edgments from the receivers, the transmitter re-
transmits the frame if one or more receivers so
requested through their acknowledgements. Oth-
erwise a new frame is sent.
Let m
j
denote the number of receivers which
successfully receive some frame F after exactly
j multicast transmission attempts to deliver F.
Also let #0D#28j#29 denote the probability with which
the frame F is successfully delivered to all M re-
ceivers with j or fewer transmissions. Then, by
counting all possible combinations of the number
of transmissions required to deliver F to eachof
the M receivers, given F was transmitted j times,
we obtain
#0D#28j#29 =
M
X
m
1
=0
#01#01#01
M
X
m
j
=0
P
j
h=1
m
h
=M
"
#12
M
m
1
;m
2
;#01#01#01;m
j
#13
#02
j
Y
k=1
#02
p
k,1
s
#281,p
s
#29
#03
m
k
#23
where the multinomial coe#0Ecientisgiven by
#12
M
m
1
;m
2
;#01#01#01;m
j
#13
=
M!
m
1
!m
2
!#01#01#01m
j
!
:
Suppose a random variable A assumes the value
j if the transmitter must send frame F exactly j
times to elicit positive acknowledgements for F
from all M receivers. If we de#0Cne #0D#280#29 = 0, then
#0D#28j#29 is the cumulative distribution function for the
random variable A. Then wemay calculate #0C, the
expected number of frames sent per frame deliv-
ered to all receivers, as:
#0C
M;satellite
= E#5BA#5D=
1
X
j=1
j#5B#0D#28j#29,#0D#28j ,1#29#5D
Hence the throughput for multicasting in a pure-
satellite network is
#11
M;hybrid
=
`
` +h
1
#0C
M;satellite
with #0C
M;satellite
calculated as above.
In the hybrid network, each frame is initially
sent via satellite and all retransmissions are sent
terrestrially. Hence, for multicasting in a hybrid
network, the expected number of frames senttoa
receiver per frame delivered to that receiver is the
same as for unicasting in the hybrid network:
#11
M;hybrid
= #11
1;hybrid
=
`
`+h
#14
1,p
t
1,p
t
+p
s
#15
:
Numerical Examples
We now turn to some numerical examples to
better understand the throughput expressions de-
rived above. For these examples, we will make the
following further assumptions:
1. Binary symmetric channel #28BSC#29 models
characterize the terrestrial channels and the
logical satellite channels between the trans-
mitter and each receiver. The crossover prob-
abilities #28bit-error rates, BERs#29 are q
s
for all
logical satellite channels and q
t
for all terres-
trial channels.
2. The terrestrial channel BER is q
t
=10
,5
.
3. There are ` = 2200 information bits and
h = 48 overhead bits in all ARQ informa-
tion frames, whether sent via satellite or via
a terrestrial link. #28The value of h was cho-
sen supposing the ARQ frame has a 16-bit
sequence number and a 32-bit CRC for er-
ror detection. The value of ` was chosen to
maximize the throughput in a point-to-point
satellite network, which is the reference net-
work for comparison purposes, as calculated
by a straightforward di#0Berentiation method
presented in #5B12#5D.#29
4. In #0Cnding #0C
M;satellite
, we approximated the
in#0Cnite summation by truncating the sum-
mation at the minimum j such that #0D#28j#29 #3E
1,10
,3
. #28We justify this truncation not only
as a fair approximation, but also because, in
an actual network, a station which requests
retransmissions too frequently would likely
be recognized by the transmitter as su#0Bering
from excessive noise, and would accordingly
be disconnected from the communication.#29
Calculated throughput values for point-to-point
communication are presented in Figure 2. As
shown in the #0Cgure, the throughput in the hybrid
3
0
0.2
0.4
0.6
0.8
1
1e-07 1e-06 1e-05 1e-04 1e-03
Throughput
Satellite Channel BER
Throughput in Point-to-Point Networks
Satellite Network
Hybrid Network
Figure 2: Throughput in point-to-point networks
#28` = 2200, h =48,q
t
=10
,5
#29.
0.4
0.5
0.6
0.7
0.8
0.9
1
1e-07 1e-06 1e-05 1e-04
Throughput
Satellite Channel BER
Throughput in Point-to-Multipoint Networks
Hybrid Network
Satellite Network,  2 Receivers
Satellite Network,  5 Receivers
Satellite Network, 10 Receivers
Figure 3: Throughput in point-to-multipoint net-
works #28` =2200,h =48,q
t
=10
,5
#29.
network comes to exceed that in the satellite net-
work as the satellite channel BER increases. This
is easily explained by the terrestrial link having
lower BER than the satellite link and by the shift-
ing of retransmissionsonto the terrestriallink with
the adoption of a hybrid network. Note, however,
that as the satellite channel BER increases, the
terrestrial bandwidth required to support retrans-
missions approaches the satellite channel trans-
mission rate.
Figure 3 presents throughputs for multicast net-
works of two, #0Cve, and ten receivers. As is char-
acteristic in satellite multicasting, the throughput
is seen to fall rapidly as the satellite channel BER
increases, especially as the number of receivers in-
creases. However, the hybrid network provides
throughput signi#0Ccantly superior to that available
in the satellite network. While remarks concern-
ing required terrestrial bandwidth as in the uni-
cast case apply in the multicast case as well, the
throughput improvementachievable with a hybrid
network in the multicast case can be appreciable.
Additional Considerations
The inherent problem in ARQmulticasting, as
stated in the introduction, is that retransmissions
sentover the multicast channel do not bene#0Ct sta-
tions which do not require them. Consequently
the throughput falls drastically as the number of
receiversincreases. In this work wehave suggested
a solution to this problem, namely retransmissions
be sentover a system of point-to-point terrestrial
links between the transmitter and each receiver.
However, many considerations remain to be stud-
ied.
Wehave not, for example, yet examined the ef-
fect of packet lengths on throughput. While the
frame length which maximizes throughput in a
point-to-point satellite networkis easily calculated
#28#5B12#5D#29, the optimal frame length for unicasting in
a hybrid network, and for multicasting in satel-
lite and hybrid networks, remains to be found.
Adaptively changing the frame length may o#0Ber
a throughput advantage, particularly at high bit
error rates in the satellite channel.
Wehave also not yet studied terrestrial network
topologies other than a star topology. Our pro-
posed solution does not necessarily preclude other
con#0Cgurations. On the contrary, other topologies
are not only acceptable, but perhaps even desire-
able. In particular, supposethe terrestrialnetwork
is a tree of terrestrial links, with the transmitter at
the rootnode andareceiverat eachnon-rootnode.
Such a tree could not only support multicasting in
ahybrid network as wehave described above, but
would also allow a retransmission request sentby
one receiver node to be serviced by the nearest
ancestor node having the requested frame. The
transmitter's load in servicing retransmission re-
quests would then be reduced.
Similar possibilities arise if the terrestrial net-
work is a wireless network, as in, for example,
the case of mobile receiving nodes. For example,
mobile receivers, with omnidirectional antennas,
can broadcast retransmission requests to other re-
ceivers possibly nearby and receive frames over
the terrestrial wireless channel. A terrestrial tree
for retransmissions, albeit a continuously chang-
ing tree, is perhaps applicable for mobile receivers
as well.
Hybrid ARQ schemes for multicasting, which
employ FEC techniques for improving throughput
4
have appeared in the literature recently, and these
suggest possibilities in the context of hybrid net-
works #5B7, 8, 13#5D. #28The reader is cautioned that
the term #5Chybrid ARQ," which is standard in the
literature for ARQschemes incorporating FEC, is
not related to our term of #5Chybrid network" for
a parallel arrangement of satellite and terrestrial
networks.#29 In #5B7#5D, for example, an adaptivetype-II
multicast hybrid ARQscheme is proposed. Rate-
compatible BCH codes are used for error correc-
tion in this scheme. Each time another retrans-
mission is requested for a particular frame, the
transmitter sends an increasing number of par-
ity digits, which, when combined with the origi-
nal data frame, from a series of BCH codewords
of decreasing rate. Such an FEC technique would
not only improve throughput, it would reduce the
bandwidth requiredforretransmissionsin a hybrid
network. This is particularly important since, as
we remarked in discussing our numerical exam-
ples which use a pure ARQ protocol, the band-
width required for terrestrial retransmissions in a
hybrid network approaches the satellite channel
bandwidth as the satellite channel deteriorates.
There are clearly many aspects of multicast
ARQ to explore. In addition to exploring such
aspects, we intend to also consider how to toler-
ate and#2For recover from errors in systems where
the multicasted information has delay constraints,
such as voice and video multicast systems. Be-
cause of the delay constraints, ARQ is not suited
well for error control in such settings, and other
schemes for mitigating error e#0Bects must be de-
vised.
*
References
#5B1#5D S. B. Calo and M. C. Easton, #5CA broad-
cast protocol for #0Cle transfer to multiple
sites," IEEE Transactions on Communica-
tions,vol. 29, pp. 1701#7B1707,November 1981.
#5B2#5D I. S. Gopal and J. M. Ja#0Be, #5CPoint-to-
multipoint communication over broadcast
links," IEEE Transactions on Communica-
tions,vol. 32, pp. 1034#7B1044, Sept. 1984.
#5B3#5D K. Sabnani and M. Schwartz, #5CMultidestina-
tion protocols for satellite broadcast chan-
nels," IEEE Transactions on Communica-
tions,vol. 33, pp. 232#7B240, Mar. 1985.
#5B4#5D R. H. Deng, #5CHybrid ARQschemes for point-
to-multipoint communication over nonsta-
tionary broadcast channels," IEEE Transac-
tions on Communications,vol. 41, pp. 1379#7B
1387, Sept. 1993.
#5B5#5D J. L. Wang and J. A. Silvester, #5COp-
timal adaptive multireceiver ARQ proto-
cols," IEEE Transactions on Communica-
tions,vol. 41, pp. 1816#7B1829, Dec. 1993.
#5B6#5D M. A. Jolfaei, S. C. Martin, and J. Mat-
tfeldt, #5CA new e#0Ecient selective repeat proto-
col for point-to-multipoint communication,"
in IEEE International Conference on Com-
munications #28ICC '93#29,vol. 2, pp. 1113#7B1117,
1993.
#5B7#5D A. Shiozaki, #5CAdaptivetype-II hybrid broad-
cast ARQ system," IEEE Transactions on
Communications,vol. 44, pp. 420#7B422, April
1996.
#5B8#5D H. Liu, Q. Zhang, M. E. Zarki, and S. Kas-
sam, #5CWireless video transmission with adap-
tive error control," in 1996 International
Symposium on Information Theory and its
Applications #28ISITA '96#29, Victoria, British
Columbia, pp. 371#7B374, 1996.
#5B9#5D Y. Yamauchi, #5COn the packet radio multicast
schemefor the personalcommunications era,"
in International Conference on Communica-
tion Systems #28ICCS '94#29, Singapore, pp. 576#7B
580, IEEE, 1994.
#5B10#5D S. Lin and D. J. Costello, Jr., Error Con-
trol Coding: Fundamentals and Applications.
Prentice-Hall, 1983.
#5B11#5D S. B. Wicker, Error Control Systems for Dig-
ital Communication and Storage. Prentice-
Hall, 1995.
#5B12#5D M. Schwartz, Telecommunication Networks:
Protocols, Modeling, and Analysis. Addison-
Wesley,1987.
#5B13#5D H. Zhao, T. Sato, and I. Kimura, #5CA hybrid-
ARQ protocol with optimal adaptive error
control for multidestination satellite commu-
nications," in International Conference on
Communication Systems #28ICCS '94#29, Singa-
pore, pp. 420#7B424, 1994.
5